基于博弈论的ALM协议改进算法

蔡媛媛，曹自平，张金娅

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

1 概 述

目前的传统网络配置技术已经受到来自软件定义网络的冲击，只有不断地突破自我才是一项技术可以长久存在的根本。传统ALM协议(NICE和CPBM)在网络拓扑的构建上进行了较为深入的研究[1]，但在用户自私性方面存在着诸多空缺,就其数据传输过程的考量是相对比较薄弱的，因此文中主要针对网络拓扑构建下的数据传输过程进行考量，综合考率了多方面因素，引入博弈论的思想以及改进传统ALM协议算法，目的则在于通过市场的激励机制来控制用户的自私性行为。

博弈论提供了当利益代表者之间发生利益冲突时可能出现的行为选择，是一组有助于解决交互决策问题的建模工具[2]。其三大要素包括：参与者、行为策略以及收益[3]。在ALM中参与者是指加入到组播树中的节点主机[4]，其目的是为了获取资源，而资源转发则是为其他主机服务，因而出现了主机在追求自身收益最大化时与因整体收益而不得不让渡自身收益的矛盾。行为策略，是参与者出于理性而做出的应对策略。节点主机在面对最大化自身收益时，常因为协议漏洞或非法行为而使自身策略获得额外收益，即用户自私性行为[5]。当组播树中有部分节点采用自私行为时，不仅会影响到其他正常节点主机的收益，还可能引起整个组播树的振荡，明显降低组播树的传输效率。因此制定一种合理的组播协议，规范组播节点行为是十分必要的。收益，是指行为策略对应的结果。节点主机的收益是指合理获取数据，并尽可能合理地使节点自愿将自身性能贡献出来，从而达到整体收益的最大化。

在ALM中当主机节点进行行为决策时，其目的非常明确—最大限度地满足自身收益的最大化，但是这种自私行为破坏了网络的全局利益。在ALM中，目前采用的博弈论思想的主要应用场景有以下两种：

数据收集阶段：主机节点为了在形成虚链路时在组播树中获得更优势的地位，会采用诸如距离欺骗、吞吐量欺骗、中继代价欺骗等欺骗行为[6]。而激励机制的出现则是为了克服主机节点进行吞吐量欺骗行为而采用的方法。

在ALM模型当中，存在自私节点通过吞吐量欺骗的方式，既占据了近源节点的有利位置，又有效减少了转发数据所带来的自身资源消耗。有实验结果表明，当主机节点之间的合作率低于30%时，整个组播树的会话质量会变得相当差，组播之间的会话近乎不可用[7]。Habib等针对主机节点吞吐量欺骗的行为，采用一种基于分区服务的鼓励用户贡献转发的资源激励机制[8]，有研究表明在引入该机制后，ALM会话的总体性能有明显提升，然而该种激励机制存在的弊病是当主机节点得到了自身传输所需的服务质量后便没有任何理由再驱使其进行转发行为，因而存在明显的局限性。Yuen等根据博弈论中的VCG机制，提出了一种基于补偿的激励制度[9]，较为有效地解决了主机节点的吞吐量欺骗问题。

数据结构构造阶段：在此阶段，就网状结构而言，节点会选用其相邻的节点作为数据请求的目标；就树状结构而言，节点会向其父节点发送数据请求的报文，此时收到数据请求报文的主机节点则会发送相应报文给请求节点，如果此时存在着激励机制，那么被请求节点则可以获得相应的转发收益。Tan等在激励机制的基础上，利用每一个主机节点通过转发数据和请求数据所获得的总收益，并引入了市场机制[10]。

研究表明，在激励机制的基础上引入市场机制以后，可以明显促进主机节点之间的良性竞争。

2 模型构建

2.1 囚徒困境模型

囚徒困境是博弈论中著名的数学模型：两个囚徒为了追求各自利益最大化而两败俱伤。囚徒困境实际上是个人利益和集体利益的矛盾体现，每一个体利益最大的总和并不代表着集体利益的最有效分配，在ALM中每一个参与传输的节点都是一个独立个体，在其做出利己行为时，对于个体而言是理智行为，但对于全局拓扑来讲并不是最优结果。事实上，在实际拓扑中如果有用户产生自私行为，所造成的影响是十分恶劣的。有数据表明，在部分节点进行了自私行为之后组播树中有50%的虚链路发生了变化，严重影响了组播树的稳定。

2.2 激励制度

在节点信息收集阶段自私节点会通报给中心节点虚假信息，以提高自己在组播树中的有利位置，如距离欺骗，即在自私节点向Leader节点发送自身参数时，一般是跳数(Hop)，修改自身与Leader节点之间的Hop为0，而与其子节点发送参数时，在延时参数加上一个随机数，降低自身作为父节点的可能性，从而在组播树中最大化地接收资源并最小化地作为中继节点传输资源。Mathy等通过模拟实验得知，存在大量距离欺骗的组播树的稳定性远小于只存在少量距离欺骗的组播树[11]。Li等的后续实验进一步表明，在某些情况下存在距离欺骗的组播树，会使得整个拓扑中50%以上的虚链路发生变化[12]。

自私用户进行距离欺骗是为了在组播树中得到更有利的位置，即更快更好地接收资源的同时利用更少的自身资源进行他人数据的转发。可利用大多情况下闲置的个人计算机，当节点每转发一次数据时，会得到相应的奖励，奖励会在Leader节点处保留，当此节点加入到组播树中时，由于之前的优良记录，将会得到一个有利的位置。相反，如果此节点存在着不良记录，如距离欺骗等行为，其可信性将会在Leader节点处受到质疑，即使其自身拥有优良的参数，也很难得到一个有利位置。

在此给出激励制度的选择依据，按照多劳多得的原则，一个节点i的贡献值(Contri)由两部分组成：一是自身转发的积累值(Fori)，二是自身请求其他节点进行数据转发的支付值(Payi)，与节点i所处的域的半径为Dij，则节点i的贡献为：

(1)

Leader节点将会根据Contri判断节点i的行为表现，Contri越高说明节点的贡献越多。当此节点进行资源请求时，Leader节点将优先向其传输，同时兄弟节点也会优先向其进行资源交换。当其他节点进行资源请求时，也会优先选择贡献值高的节点进行资源接受[13]。

引入激励机制后，节点之间的数据传输已然变成了有偿服务，通过进一步借鉴货币在市场中的作用，引入货币机制。在方才定义的任意节点i的Contri只是就单个节点的转发数据和获取资源而言，将市场思维引入之后，每一个节点在索取资源时，可以充分利用自身已有的贡献值，将自己的贡献值作为价码出售给拥有资源的节点，此时资源拥有者可以根据自身情况选择一个最合适的节点进行传输。

2.3 动态传输协议

文中选用六个参数来进行资源节点的选择。第一个参数是带宽，即发出资源请求的节点到达目的节点直接所经过的路由器中带块最小的值。第二个参数是时延，即在整个传输路径上经过所有路由器的时延的总和。第三个参数是节点资源拥有量，即拥有资源节点所拥有请求者所需资源的数量。资源拥有的多可能是因为在整个拓扑当中停留的时间长，或者其节点传输速度较快，二者皆是理想的资源节点的属性[14]。第四个参数是节点存在时间，即资源节点在整个拓扑中存在的时长。一般认为在此环境中停留时间越长的节点在接下来的时间内退出的可能性越小，其稳定性就会越高。第五个参数为跳数，如果主机之间经过路由器跳数越少，可以粗略认为这条链路上的时延越短，网络抖动越小，丢包率越低。第六个参数为贡献值。

(2)

(3)

(4)

在这里定义概念活性(Activetrans)，考虑资源(Src)与时间(Time)作为参考度量，且用其比值的形式出现，Activetrans越大，节点的活性越高，同时稳定性也越强。如果一个节点的资源占比越高，其被选为候选资源节点的可能性应当是提升的，但是也确定此节点拥有资源皆为本次传输所得，于是还考虑将此节点所在整个拓扑中的时间作为参考对象，以其处在的时间与整个拓扑所存在时间的比值为表现形式。式中的0<α,β<1，作为参数权重出现，也保可证Activetrans是一个真分数。只有在资源和时间的比重达到最优时，才可能选出最稳定且活性最高的节点进行资源传输。

当s节点或者Leader节点收到下级节点发来的数据请求之后，会将相似的数据请求分类并编号，随后将同一类资源分段传输到不同的请求节点。数据分段的依据是以Costtrans公式为基础的，开销越小的节点会获得越多越大的资源分段。

(5)

当同层中Leader节点之间形成邻居关系时，如果计算得到的Costtrans值比Leader节点与s节点之间的Costtrans小，则使用这条路径进行资源传输，如果没有，则将这条路径放入备用的资源路径数据库，以便在下次通信时可快速地形成邻接关系，也起到了链路备份的作用。同层的Member节点之间的数据请求与传输也是类似的。

3 实验仿真

采用Myns进行仿真[15]，与文中提出的T-M模型进行对比的模型为NICE，通过对控制开销、平均数据传输率、协议稳定性这三个定向指标的仿真模拟，实验中的节点数从100开始，并且以线性方式增长。旨在观察在网络拓扑变复杂，组成员变多的情况下两种协议之间的优劣。

图1 控制开销对比曲线

图1表明T-M算法的控制开销高于NICE算法，这是因为T-M算法加入了报文分割和节点资源列表。在资源请求时，请求节点会与周围的节点进行资源占比、节点活跃度等参数的交互，选取它认为最安全的节点进行数据请求，这样虽然增加了节点控制开销，但提升了节点间资源传输的稳定性；在节点请求数据时，将请求资源分段分别发送给基于本片段资源的最优节点，以提高资源传输成功率。

图2清楚地显示出T-M协议的传出效率高于NICE协议。因为随着拓扑中节点数的不断增加，T-M协议因采用的是树网混合型结构的拓扑模型，每个节点所需维护的节点关系较少，同时由于此协议在数据传输时采用了动态分布式传输方式，就同一个资源而言，每个授信节点只需传输其中的一部分，同时这些授信节点的可靠性是相对较高的，因此其传输成功率与效率会明显提高。

图2 传输效率对比曲线

图3显示T-M协议的稳定性高于NICE协议，因为T-M协议采用的分布式传输方式在其中一个节点失效后，会有后备节点接替，且在选取资源节点时采用了较为复杂但更为有效和稳定的选取规则，保证了资源节点的稳定性，也提高了协议的稳定性。

图3 协议稳定性对比曲线

4 结束语

该协议针对传统的ALM协议进行改进，传统的ALM协议，如NICE、CPBM，在数据传输过程中主要以跳数(Hop)为单一参考，然而由于网络结构的异构性，各个数据链路之间的带宽、延时等差异较大，因此通过综合考量节点贡献值、跳数、带宽、延时等，将博弈原理加入到组播算法当中。虽然此算法在控制开销方面相比CPBM、NICE协议要大，但是在传输效率和稳定性方面有所提升，在目前终端处理能力大幅度提升的情况下，提高数据的传输准确率，才是更为紧要的课题[16]。

参考文献：

[1] 叶保留,李春洪,姚 键,等.应用层组播研究进展[J].计算机科学,2005,32(6):6-10.

[2] 刘期烈,刘茂松,李 云.基于博弈论的机会网络激励机制的研究[J].计算机应用研究,2015,32(7):2128-2132.

[3] FELDMAN M, PAPADIMITRIOU C, CHUANG J,et al.Free-riding and whitewashing in peer-to-peer systems[C]//ACM SIGCOMM workshop on practice and theory of incentives in networked systems.[s.l.]:ACM,2004:228-236.

[4] BURAGOHAIN C,AGRAWAL D,SURI S.A game theoretic framework for incentives in P2P systems[C]//Proceedings of the third international conference on peer-to-peer computing.[s.l.]:IEEE,2003:48-56.

[5] LIU Zhengye, SHEN Yanming, ROSS K W,et al.Layer P2P:using layered video chunks in P2P live streaming[J].IEEE Transactions on Multimedia,2009,11(7):1340-1352.

[6] MA R T B,LEE S C M,LUI J C S,et al.Incentive and service differentiation in P2P networks:a game theoretic approach[J].IEEE/ACM Transactions on Networking,2006,14(5):978-991.

[7] BASAR T,SRIKANT R.Revenue-maximizing pricing and capacity expansion in a many-users regime[C]//Joint conference of the IEEE computer and communications societies.New York,NY,USA:IEEE,2002.

[8] SENTINELLI A,MARFIA G,GERLA M,et al.Will IPTV ride the peer-to-peer stream? [peer-to-peer multimedia streaming][J].IEEE Communications Magazine,2007,45(6):86-92.

[9] HABIB A,CHUANG J.Service differentiated peer selection:an incentive mechanism for peer-to-peer media streaming[J].IEEE Transactions on Multimedia,2006,8(3):610-621.

[10] TAN G,JARVIS S A.A payment-based incentive and service differentiation mechanism for peer-to-peer streaming broadcast[C]//IEEE international workshop on quality of service.New Haven,CT,USA:IEEE,2006:41-50.

[11] MA R T B,LEE S C M,LUI J C S,et al.An incentive mechanism for P2P networks[C]//International conference on distributed computing systems.[s.l.]:IEEE,2004:516-523.

[12] 卫萌菡.基于博弈论的无线多媒体网络协作资源管理研究[D].成都:西南交通大学,2007.

[13] 姚 霖.基于博弈论的对等网络节点自私性研究[D].济南:山东大学,2012.

[14] 许建真,马彩玲,谢川川.基于节点综合性能的总线型应用层组播模型[J].计算机应用,2009,29(11):2884-2886.

[15] 徐 超,张祖平.应用层组播协议仿真研究[J].计算机工程与应用,2006,42(1):112-114.

[16] 苏金树,曹继军,张博锋.应用层组播稳定性提高技术综述[J].计算机学报,2009,32(3):576-590.