车载自组织网络中节点合作行为的博弈研究①

曾熙凯,丁 箐

(中国科学技术大学 软件学院,合肥 230051)

车载自组织网络中节点合作行为的博弈研究①

曾熙凯,丁 箐

(中国科学技术大学 软件学院,合肥 230051)

在车载自组织网络中使用公共品博弈理论促进节点合作的研究表明车辆密集区域的节点会呈现不合作状态.本文通过模拟实验得知当节点平均度数较低时,节点更容易产生合作行为.为了提高车辆密集区域中合作节点的比例,本文提出了博弈度数与博弈拓扑的概念,并在此基础上构建了一种能够更改网络博弈拓扑,降低节点博弈度数的分组博弈理论模型.实验结果表明,在车辆密集区域使用该博弈模型能够显著提高网络中合作节点的比例.

公共品分组博弈; 车载自组织网; 平均度; 节点合作

1 引言

车载自组织网络中的数据传输对车辆节点的合作性有着很高的要求.然而,节点由于能耗和处理能力的限制容易出现拒绝转发数据等目光短浅的自私行为.近年来在车载自组织网络环境下采用博弈模型促进节点合作的论文呈增多趋势[1-4],研究者应用博弈论的相关知识增强节点之间的合作转发.大多数研究都建立在网络中存在中央控制器的基础上,通过激励或者惩罚策略促进节点合作,并不符合车载网络具有分布式特点的实际情况.文献[5,6]提出了一种基于消息转发的公共品博弈模型,该模型采用了无中央控制的分布式机制,并运用了这种博弈模型探究车载自组织网的网络特征对网络中合作节点数量的影响.他们发现更高的聚类系数和更高的连通性会增加合作节点的比例.但是他们强调在车载自组织网络中保持节点的合作性极其困难.其后部分作者致力于对公共品博弈模型进行优化,文献[7]构建了一种不均匀投资的公共品博弈模型.在该模型中,节点会对合作者比例更高的博弈团体投入更多的资金.张海峰等人提出理性的节点如果在某轮博弈时从以节点i为中心的博弈中得到更多的收益,那么在下一轮参加该博弈时就会投入更多的资金[8].文献[9]则根据节点度数定义了节点之间的影响强度,更高度数的节点对更低度数节点的影响越大.节点参与博弈时,根据与博弈中心中心节点之间的影响强度决定投资金额与收益分配.实验表明以上模型都能够促进节点的合作行为.在文献[10]中,节点根据自己度数的大小决定博弈时的投资金额.实验表明,当高度数节点投资更少时能促进网络中节点的合作行为.文献[11]中,学者根据节点的度数决定公共池金额的分配.实验显示分配给高度数节点或者低度数节点更多的收益都会提升网络中合作节点的比例.由于车载自组织网络中节点不停移动、邻居也相应不断变化,因此节点不知道邻居节点博弈的历史信息,博弈前也不知道自己本轮的博弈度数,这些针对无标度网的博弈优化模型并不适合车载自组织网络.

在本文的工作中,通过观察使用公共品博弈模型促进节点合作时车辆密度与合作节点比例的关系,发现较小的节点平均度能够促进网络中节点的合作行为,提出了一种适合于车载自组织网络的公共品分组博弈模型,并分析了节点平均度对于合作节点数量的影响.实验表明合理的对节点进行分组从而降低节点平均度数能够显著地提升车载自组织网络中合作节点的比例.

2 博弈基础

本文采用公共品博弈作为博弈模型的基础.在公共品博弈中,合作者选择向公共品奖池中投入一定资金c,非合作者不投入资金.一段时间后,公共资源产生r倍增值,小组所有成员平均分配公共池资源.倍增系数r代表了团队的协同效益,预示团队协同的力量大于个人独自行动.当倍增系数r越高时团队的收益越高,更能激励节点参与团队协作.

在车载自组织网中将消耗自身资源转发数据包的节点称为合作者,由于自私性拒绝转发数据包的节点称为非合作者,认为两种节点分别拥有合作和非合作策略.合作节点的转发行为为整个网络的消息传播作出了贡献,而非合作者仅仅坐享其成.节点进行公共品博弈后,合作者和非合作者节点均匀分配公共收益,并且根据自己与邻居的收益判断是否改变自己当前的策略.

2.1 公共品博弈模型

在每轮博弈开始时,节点向自己邻居广播博弈信息,其中包括自己上一轮博弈的收益和当前的策略.接收到邻居的博弈消息后,节点会统计自己邻居中合作者和非合作数量,以自己为中心进行公共品博弈.由于车载自组织网络中车辆的不断移动,邻居的不断变化,节点无法准确的给邻居回馈博弈收益,本文只考虑单一的公共品博弈,每个节点只从以自己为中心的博弈中得到收益.

假设每轮博弈合作者的投资金额为1.在第t轮博弈时,节点i的博弈度数为ki(t),博弈的倍增系数为r,邻居当中合作者的个数为nc(t).则节点i作为合作者和非合作者在该轮的博弈收益为

2.2 策略选择

每个节点会根据自己与邻居的收益决定是否更改自己当前的策略.众所周知,具有理性和自私性的节点会更倾向于向成功的邻居学习而使自己变得更好,本文认为高收益的邻居更为成功.节点i会在它的所有邻居当中随机选择一个邻居与之比较收益,做出是否学习邻居策略的选择.本文假设在第t轮博弈时,如果节点i选择它的邻居j进行比较,则节点i选择节点j策略的概率为

其中T为噪声,代表节点选择理性程度,T越小说明节点越理性.如果T=0,且节点j的收益比节点i的收益大,那么节点i肯定会选择节点j的策略作为自己下一阶段的策略.如果T=∞,那么节点i完全随机的选择是否更改自己的策略.如果T>0,节点i也有一定的概率不会选择节点j的策略而是保留自己原有的策略.通过之前一系列的研究[9-11],设置T=0.1是最适合的选择.

3 分组博弈理论模型

节点博弈时与之交换博弈信息的邻居被称为该节点的博弈邻居.如果节点i和节点j具有相同的博弈邻居,且两个节点互为邻居,则认为节点i和j处于同一个博弈团体.

3.1 节点策略的转换

由公式(1)(2)(3)可以得知,同一个博弈团体中合作者的收益肯定会小于非合作者的收益.如果网络中只存在一个博弈团体,节点会逐渐选择不合作策略.但是当网络中存在不同的博弈团体时,会出现合作者收益高于非合作者的情况.

图1 不同博弈团体导致节点收益的差异性

如图1所示,编号为C和D的节点分别代表合作者和非合作者.图1(a)中所有节点处于一个博弈团体中,他们具有相同的博弈邻居.其中合作者会逐渐更改自己的策略向非合作者转变.图1(b)在节点总数和合作者比例相同的情况下拥有3个博弈团体.每个博弈团体由于合作者比例不同导致了节点收益的差异性.根据公式(1)(2)可知合作者比例越多的博弈团体中节点的收益越高,并且随着倍增系数r的增大,合作者比例对博弈收益的影响越大.这时会存在合作者收益高于非合作者收益的情况.由于车辆的移动性以及连接各个博弈团体的中间节点的存在,非合作者在策略选择时就有可能改变自己的策略.

假设低收益节点学习高收益节点策略的概率为1.网络中有N个随机移动的节点,节点每轮博弈的邻居完全随机.其中合作者数量为NC,非合作者数量为ND,所有节点构成一个博弈团体.则合作者与非合作者相互转变的概率为:

如果将节点分为两个博弈团体,分别具有NC1和NC2个合作节点,ND1和 ND2个非合作节点.假设两个团体中合作者比例pC1>pC2,且第一个团体中合作者的收益高于第二个团体中非合作者的收益.则合作者与非合作者相互转变的概率为:

针对这些特殊性，在将近一年的工作中，工作队始终牢固树立总目标意识，突出“维护稳定、建强组织、脱贫攻坚、群众工作、兵地融合”五项任务，按照“四句话”“4+2”工作要求，发挥工会自身优势，打好“工”字牌“农”字牌，扎实推进“访惠聚”工作深入开展，坚持用“爱心”“恒心”“耐心”，凝聚起职工群众一心向党的“民心”。

将收益高的那个博弈团体分为两个更小的博弈团体,且pC11>pC12>pC2,则合作者与非合作者相互转变的概率为:

由此可知,对具有相同节点总数和合作者比例的不同群体进行博弈时,如果群体中拥有更多合作者比例不同的博弈团体,该群体中的节点将更倾向于选择合作策略.

3.2 分组博弈模型

由公式(1)(2)可知团体成员越少时,单个成员策略的改变对团体中合作者比例以及团体收益的影响越大.本文实验4.1结果显示车载自组网中节点平均度较小时合作者比例会更高.从文献[6]中可以得知网络中存在一些被大量低度数节点围绕的高度数节点(hub节点)时更容易促进节点间的合作.在连通性越强的网络中,hub节点能与更多普通节点的进行博弈,hub节点的高合作性能够促进普通节点产生合作行为.结合相关研究和前文的分析,本文提出了一种基于分组的公共品博弈理论模型.

在分组博弈模型中,将博弈邻居的个数称为节点的博弈度数,所有节点与它们的博弈邻居组成的网络拓扑称为博弈拓扑.分组博弈模型把网络中所有节点随机分为n个小组.将第1组的节点作为博弈hub节点,它们与所有的邻居交换博弈信息而具有较高的博弈度数.其余普通节点只与邻居中同组的节点进行博弈,从而降低了普通节点的博弈度数.通过分组博弈将实际的网络拓扑改变成一种少量高度数节点被大量低度数节点围绕的博弈拓扑.

网络中的节点在每个时间单位进行一轮博弈.在每轮博弈开始时,节点向自己的邻居发送博弈信息.博弈信息中包含节点的博弈策略、博弈收益以及分组编号.hub节点接收所有收到的博弈信息,而普通节点只接收分组编号与自己相同以及hub节点发送的博弈信息.节点将收到信息的发送方作为本轮的博弈邻居.

图2 节点普通博弈和分组博弈的博弈拓扑

4 模拟实验及分析

为了探讨车载自组织网络中分组博弈的性能及进行相关的优化,本文利用SUMO仿真工具在自定义的650(m)×650(m)的地图中产生由 N(50,100,300)个节点组成的网络,模拟车辆密度大的城市交通中车辆的运行轨迹并使用NS2仿真工具实现节点博弈信息的交换.地图中共有4x3条双向道路以及交叉产生的12个十字路口,每两条平行道路之间的距离超出了车辆的传输范围,模拟地图的部分区域如图3所示.

图3 模拟实验局部地图

模拟时将每个节点看成一个车辆,随机设置每个车辆的初始位置和移动路径.在初始的时候以50%的概率随机设置每个节点的合作策略.每隔一个时间单位进行一轮博弈,当网络中合作者比例达到平衡值时,统计博弈过后合作者所占的比例.本文对不同的网络拓扑进行重复多次实验,以保证实验结果的一致性,实验统计出的所有数值都是多次实验后的平均值.为了保证模拟实验更为真实有效,本文在道路路口设置了红绿灯并且设置了道路最大速度以及车辆加速度来限制车辆的移动.车辆会在十字路口大量聚集产生高的车辆密度.各参数如表1所示.

表1 模拟实验参数

4.1 车辆密度对合作者比例的影响

图4显示了使用公共品博弈在不同节点密度和消息传播范围下,合作者比例随倍增系数r的变化规律.由图中可知随着倍增系数r的增大,网络中合作节点比例会增多.较小的节点密度和传输范围会造成较小的节点平均度.在车辆数量为100时,相对小的传输范围能够提升合作者比例.但是当节点数量为50且传输范围较小时合作者比例反而较低.通过分析得知,低的节点平均度数能促进网络中节点的合作行为,但是过低的节点平均度数可能造成网络中孤立节点和孤立团体的存在,影响网络拓扑的连通性.网络中孤立的节点和团体由于缺乏与网络中其他节点博弈信息的交换而导致不合作行为的发生,并且很难改变自己的策略.

图4 不同网络状态下的公共品博弈

4.2 车载自组织网络中的分组博弈

图5 显示了具有100个节点,传输范围为250 m的网络中,使用分组博弈在分组不同时合作者比例随倍增系数r的变化趋势.根据与实验4.1的比较,可以明显的观察出在车载自组织网络中使用分组博弈极大地促进了节点的合作行为,特别是当分组较多的时候.将100个节点分成10个组时,在r取值很小时网络就达到了几乎全合作的状态.

图5 分组博弈中分组个数对合作者比例的影响

4.3 分组个数对合作者比例的影响

图6 显示了使用分组博弈在不同节点密度和通信范围下,倍增系数r为4时,合作者比例随着分组个数的变化趋势.从图中可知,随着分组个数的增多,合作者比例会达到一个最优值,并且上升过程变化较快.当节点密度越大时,维持最优效果的分组选择会越多.当合作者比例达到和维持最优值以后会出现下降的趋势.分析得出,过多的分组会造成网络拓扑的不连通性.在节点个数等于50,传输范围为100 m的网络中,由于网络拓扑的不连通性,节点很难呈现较好的合作行为.虽然车辆的移动性会对不连通性进行弥补,但还是应尽可能的避免这种情况的发生.

图6 不同节点密度和通信范围下的分组博弈

4.4 节点平均度数对合作者比例的影响

图7 、8、9、10显示了在分组博弈中不同节点密度和通信范围下,r为4时,节点的平均度数和合作者比例随分组个数的变化趋势.其中只计算了普通节点的平均度数,并不将hub节点的度数考虑在内.将节点平均度数与合作者比例进行对比分析可以发现,当普通节点平均度在1.8-2.2左右的时候,合作者比例能够达到最优.当节点平均度数高于这个范围时,由于过高的节点平均度,合作者比例会快速的降低.当节点平均度低于这个范围时,节点的不连通性会导致合作者比例缓缓的降低.

图7 50个节点100传输范围下的分组博弈

图8 50个节点250传输范围下的分组博弈

图9 100 个节点 100 m 传输范围下的分组博弈

图10 100 个节点 250 m 传输范围下的分组博弈

本文只在特定的高密度场景下进行了相关实验.在无红绿灯路口,高速公路,停车场等其他场景下以及使用不同车辆移动模型时,虽然车辆速度,移动行为,车辆密度均会有所不同,但是节点只需要获取通信范围内的邻居以及邻居分组编号就能进行分组博弈,故在多种场景下都可以使用本文方法,降低节点的博弈度数,促进节点进行合作.

5 结束

本文针对公共品博弈模型在高车辆密度区域中促进节点合作不理想的情况,通过实验得知较小的节点博弈度数能促进网络中节点的合作行为,基于此提出了一种分组博弈理论模型.该模型在博弈拓扑上可以降低节点博弈平均度数.实验结果表明,在车辆密度特别大的情形下,该模型有利于网络中的个体选择合作策略.通过合理的分组,将网络中节点的平均博弈度控制在1.8-2.2时能很好的促进个体之间的合作.车辆密度越大的网络对维持最优值的分组选择更多.

本文只限定于分组个数固定的分组博弈模型研究,网络中的节点拥有相同的分组选择,实验表明在车辆密集区域能取得很好的博弈效果.事实上,车载自组织网络的网络拓扑具有更丰富的结构,从乡村网络拓扑到高速公路拓扑都具有各自的特性.在未来的工作中,本文希望能够在多场景下进行模拟和优化分组博弈模型,使得节点根据自身博弈度数的变化动态地调整适合于自己的分组个数.

1刘伎昭,王泉.车载自组网中联盟博弈的虚假数据检测策略.西安交通大学学报,2015,49(2):69–73,134.[doi:10.7652/xjtuxb201502012]

2Chai R,Lv Y,Yang B,et al.Cooperative game based relay vehicle selection algorithm for VANETs.Proc.of the 14th International Symposium on Communications and Information Technologies.Incheon,South Korea.2014.30–34.

3Kapade N.TLC:Trust point load balancing method using coalitional game theory for message forwarding in VANET.Proc.of 2014 IEEE Global Conference on Wireless Computing and Networking.Lonavala,India.2014.160–164.

4Zhang L,Jia SC,Liu ZS,et al.Bus-Ads:Bus trajectorybased advertisement distribution in Vanets using coalition formation games.IEEE Systems Journal,2015,PP(99):1.

5Shivshankar S,Jamalipour A.Effect of altruism and punishment on selfish behavior for cooperation in vehicular networks.Proc.of the 1st IEEE International Conference on Communications in China.Beijing,China.2012.653–658.

6Shivshankar S,Jamalipour A.An evolutionary game theorybased approach to cooperation in VANETs under different network conditions.IEEE Trans.Vehicular Technology,2015,64(5):2015–2022.[doi:10.1109/TVT.2014.2334655]

7Gao J,Li Z,Wu T,et al.Diversity of contribution promotes cooperation in public goods games.Physica A:Statistical Mechanics and its Applications,2010,389(16):3166–3171.[doi:10.1016/j.physa.2010.04.018]

8Zhang HF,Shi DM,Liu RR,et al.Dynamic allocation of investments promotes cooperation in spatial public goods game.Physica A:Statistical Mechanics and its Applications,2012,391(8):2617–2622.[doi:10.1016/j.physa.2011.12.005]

9Lei C,Wu T,Jia JY,et al.Heterogeneity of allocation promotes cooperation in public goods games.Physica A:Statistical Mechanics and its Applications,2010,389(21):4708–4714.[doi:10.1016/j.physa.2010.06.002]

10Cao XB,Du WB,Rong ZH.The evolutionary public goods game on scale-free networks with heterogeneous investment.Physica A:Statistical Mechanics and its Applications,2010,389(6):1273–1280.[doi:10.1016/j.physa.2009.11.044]

11Zhang HF,Yang HX,Du WB,et al.Evolutionary public goods games on scale-free networks with unequal payoff allocation mechanism.Physica A:Statistical Mechanics and its Applications,2010,389(5):1099–1104.[doi:10.1016/j.physa.2009.11.029]

Research on Evolutionary Game Theory for Cooperative Behavior of Node in VANETs

ZENG Xi-Kai,DING Qing
(School of Software Engineering,University of Science and Technology of China,Heifei 230051,China)

Studies in vehicular ad hoc networks using public goods game theory to enhance the cooperation show that the performance of cooperation in those types of network would have been poor in the areas with high vehicle density.In this paper,the result of simulation shows that the certain range of degrees of vehicle will enhance the cooperation in network.Therefore,we propose a grouping game model with the concept of the game degree and game topology to enhance the cooperation in the areas with high vehicle density.This model can change the game topology and reduce the game degree of nodes.The experimental results show that using this model in any high density regions of vehicles can significantly enhance the performance of cooperation in the network.

grouping public goods game; vehicular ad hoc network; average degree; cooperation of node

曾熙凯,丁箐.车载自组织网络中节点合作行为的博弈研究.计算机系统应用,2017,26(10):270–275.http://www.c-s-a.org.cn/1003-3254/6029.html

2017-02-05; 采用时间:2017-03-02