DOI: 10.11817/j.issn.1672-7207.2017.07.011
基于重复博弈的WSN节点合作性研究
张超，董颖，吕杨，苏真真
(吉林大学 通信工程学院，吉林 长春，130012)
摘要：将博弈论引入节点行为的决断中，在网络中建立1个基于节点数据传输可靠度的重复博弈模型。针对节点的行为引入最优惩罚程度的惩罚机制，在保证对自私节点产生足够震慑的同时，又避免对自私节点过度惩罚而造成节点的提早死亡，从而提升网络数据传输的整体效益。研究结果表明：采取最优惩罚轮数的惩罚策略能够在保证最少的减小网络生命周期的前提下，最大程度地提升网络的整体效益约22.83%。
关键词：无线传感器网络；能量均衡；路由；重复博弈；理性偏好
中图分类号：TP393 文献标志码：A 文章编号：1672-7207(2017)07-1762-07
Cooperative research of WSN nodes based on repeated game theory
ZHANG Chao, DONG Ying, L
Yang, SU Zhenzhen
(College of Communication Engineering, Jilin University, Changchun 130012, China)
Abstract: A repeated game model of the reliability of data transmission was proposed based on the hierarchical routing protocol. A punishment mechanism model in the game was introduced and the degree of punishment mechanism was demonstrated, which not only ensured the selfish node cooperation but also avoided the premature death of selfish nodes subjected to excessive punishment. The results show that the penalty strategy with the optimal penalty round can guarantee the minimum reduction of the network life cycle. The efficiency of the network can be improved by the penalty strategy with the optimal penalty round about 22.83%.
Key words: wireless sensor network (WSN); energy balance; routing; repeated game; rational preferences
无线传感器网络(wireless sensor network，WSN)作为物联网研究的一个重要组成部分吸引了大量科研工作者的关注。WSN由众多具有自我控制、感知、数据处理和无线通信能力的无线传感器节点通过自组织的方式构成[1-3]。由于WSN中节点的能量有限[4]，使得部分节点会以节省自身能量为主导而选择自私行为[5]，拒绝转发其他节点的数据包，从而造成整个网络吞吐量迅速下降。如何有效规范WSN内节点的行为，在尽可能保证网络能耗均衡的前提下提升网络的吞吐量成为WSN研究的一个重要内容。博弈论是研究不同决策主体间决策均衡的理论[6]，因此利用博弈论规范WSN中节点的行为就成为解决网络能耗均衡问题的有效手段[7]。近年来，利用博弈论处理无线网络能耗问题得到了较多的应用。王博等[8]建立了Ad Hoc无限重复合作转发博弈模型, 结合该模型提出了激励节点之间合作的积极性条件，并给出了一种通用的惩罚机制。JAMIN等[9]运用博弈理论在无线传感器网络中提出了一种高效的路由算法，整个过程被建模为一个动态的、合作的不完全信息博弈，根据信号干扰噪声比确定最优路径，并定义一个效用函数，在能量消耗和延迟之间实现平衡。LI等[10]构建了基于进化博弈的WSN信任策略模型，通过动态分析进化稳定状态的定理和推论，给出了信任激励和数据重传的上限。LIU[11]考虑到节点希望其他节点转发自身信息，并尽量避免中继传输其他节点的信息，导致节点表现出自私性，为避免这种情况发生，在WSN中引入非合作竞争均衡，每个节点都要经过竞争以实现数据传输，达到网络性能的提升。以上研究表明，在WSN中通过引入博弈论来规范节点行为是有效的，利用惩罚自私节点既可以均衡网络能耗，又能够提升网络的吞吐量。但是，节点自私行为的程度各不相同，某些节点可能持续采取自私行为，而某些节点只是偶尔采取自私行为。因此，研究根据节点行为的自私程度不同而采取最优的惩罚措施是非常必要的。基于此，本文作者建立了基于重复博弈的分层WSN模型，选择最优惩罚程度的机制，既保证对节点产生足够震慑，又不会对节点造成损害，从而实现在保证网络生命周期的同时，最大程度地提升网络的整体性能。
1 网络模型
WSN的层次结构能够提高节点的能量效率、改善WSN的可扩展性和有效地利用网络资源，如图1所示，因此本文基于层次网络结构建立重复博弈的模型。整个网络可分为若干簇，每簇内包含若干簇内节点和1个簇头节点，簇内节点与网络中其他簇节点的通信必须通过簇头节点，由簇头节点将数据转发到Sink节点[12]。网络的工作过程包括簇头节点的选择过程和数据的传送过程[13-14]，为方便分析，本文建立了1个理想的WSN网络模型，该网络应具有以下性质：
图1 网络模型
Fig. 1 Network model
1) 网络中节点的分布是不均匀的，且每个节点具有唯一的ID，节点具有完全理性[15]，完全可以按照自己的意愿进行策略选择以实现自身效益的最大化；
2) 节点一旦布置完成，能量有限且不能补给；
3) 网络的运行时间可划分成若干相等的时隙，即釆用离散时间模型，使用TDMA模式发送数据，且假设每个时隙每节点只发送1次数据包。
4) 假设节点发送或者转发1个数据包所消耗的能量是固定的。
2 博弈模型建立
2.1 阶段博弈与重复博弈
WSN中节点理性偏好的设计是决定博弈模型能否成功的关键性因素[16]，源节点数据能否成功传送到Sink节点以及数据传输过程中的能耗问题则是影响网络性能最关键的2个因素，所以，本文基于这2个因素对节点的理性偏好进行设定。
博弈参与者：在分簇路由协议中将节点分为簇内节点与簇头节点2类。簇内节点负责数据的发送，簇头节点在完成数据发送的同时还要进行数据的转发任务。节点的自私行为(即不转发数据)主要是发生在簇头节点处，因而本模型建立的是针对簇头节点是否转发簇内节点数据而进行的博弈。故在该模型中将博弈者设为簇头节点，由于簇头节点每轮是随机变化的，每个节点都有可能当选为簇头节点，所以，从博弈整体来看，博弈参与者即为网络中所有的传感器节点。
参与者策略空间：针对本文中节点理性偏好的设定，簇头节点的策略选择是对是否转发簇内节点的数据包到Sink节点与能耗问题的一个权衡，所以簇头节点的策略集为{转发簇内节点数据包，不转发簇内节点数据包}。
博弈参与者的效用函数
由收益
与代价
构成：
(1)
其中：
为节点i所采取的策略；
为除节点i以外的其他节点所采取的策略集；为博弈参与者的收益；为博弈参与者的代价。
由于分簇路由协议一般是在多跳范围内实现数据的通信，所以收益考虑了多跳范围内的连通性，同时基于节点的自我理性偏好分析，节点的收益取决于是否成功将自身数据包发送到Sink节点，因此，定义为
(2)
其中：G为数据包成功发送至Sink节点所获得的奖励；p为数据包一跳传输成功的概率；n为通信跳数。
当节点i当选为簇头节点时其代价[17]为
(3)
当节点i为簇内节点时其代价为
(4)
其中：
为传输1个数据包单跳所消耗的能量(包括发送能耗与接收能耗)；
为节点的总能量；
为簇头节点进行数据融合时所消耗的能量；p为数据包一跳传输成功的概率；n为通信跳数。
节点进行数据的转发是一个重复博弈的过程。假设节点重复博弈N次，那么，节点的累积效用为
, 0＜
＜1 (5)
其中：
为节点i在第n个时隙时节点的效用函数；为贴现因子，且0＜＜1。
在实际情况下，由于每个节点死亡时间是不确定的，故网络节点的整个博弈结束时间存在不确定性，这种博弈就成为可能随机结束的重复博弈，在一般情况下，这种博弈可以按无限次重复博弈进行分析，那么该博弈模型中节点的平均效用
[6]为
, 0＜＜1 (6)
其中：为节点i在第n个时隙节点的收益函数；为贴现因子，且0＜＜1。
式(1)的效用函数是节点在一次博弈中所获得的收益，从效用函数中可以看出，在阶段性博弈中对于簇头节点而言，采取不转发的策略所获得的效用值更大，从自身利益出发，会存在节点选择自私行为以节省自身能量。因此，在阶段博弈中博弈参与者采取不转发的策略即为此次博弈的纳什均衡，但博弈是一个重复过程，节点的自私行为会导致网络的整体性能的下降，为了防止这种现象的产生，本文引入惩罚机制。
2.2 惩罚机制
由节点的理性偏好可知：节点选择不合作的策略是由于其只考虑到当前单次博弈的收益，没有考虑到当前不合作行为对未来收益的影响。若不对节点采取相应的惩罚措施，则会导致某些节点不考虑长久收益，从短期收益出发采取不转发其他节点数据包的自私行为，导致网络整体性能下降。
本文对自私节点采取如下惩罚措施，以保证节点采取合作的态度：当节点在上一轮采取自私行为时，整个网络会立即标记该节点的所属ID，在其后N轮的簇头选择过程中，会将这些自私节点选为簇头节点，强制其转发簇内节点的数据包，使其付出的代价超过当前作弊所获得的短期收益，从而对节点产生足够的威慑，迫使节点在后面的数据转发中采取合作的态度。节点接受完惩罚以后在下一轮的博弈中以新的状态继续参与数据的发送/转发。
为了保证整个策略的合理性，本文重点在于研究对自私节点惩罚的最优轮数，即在保证对自私节点产生足够震慑的同时，防止节点因所受惩罚程度过大而造成节点过早死亡，影响网络的整体性能，下面对惩罚的最优轮数予以证明。
假设节点i在第一轮当选为簇头节点，一开始采取自私的行为，其获得的效用值为
，网络会标记节点i的ID，惩罚节点i在后面的N轮中作为簇头节点，此时每轮所获得的平均效用值为
，在以后节点i再次当选为簇头节点时将一直采取合作的策略，此时每轮的所获得的平均效用值为
。
(7)
(8)
(9)
其中：q为簇头节点所占比例。
由于无限重复博弈平均收益计算更加方便，所以给出此时节点i的平均效用值为
(10)
若节点始终采取合作的策略，则它的平均效用为
(11)
为了促进簇头节点选择合作策略进行数据的转发，单阶段博弈达成子博弈完美纳什均衡，则有：
＞
＜
(12)
由于＞＞，则＞0，所以＞0，从而得出
＞
对式(12)两边取自然对数，得
＜
由于0＜＜1，所以
＜0，可得
＞
(13)
式(13)给出了惩罚节点轮数N的取值范围，据此可以确定N的最佳取值，以实现对节点产生足够的震慑的同时，又不会对惩罚节点造成过多的能量损耗。
通过以上分析，可以得出当＜＜1，同时，＞时，簇头节点不会偏离合作均衡。
整个博弈过程如图2所示，假设无线传感器网络中所有节点的初始能量保持一致，首先要按照分簇路由协议进行簇头选择，选完簇头以后进入到数据传输阶段，簇内节点将数据包发送给相应的簇头节点，簇头节点要对是否转发簇内节点数据包进行策略博弈。若节点选择数据转发，则簇头节点会进行数据融合并将数据包转发给Sink节点；若簇头节点为恶意节点，选择自私行为，网络将会立即标记该簇头节点ID，在后续的N轮中对节点进行处罚，将其作为簇头节点消耗更多的能量，从而对节点产生足够的震慑，保证节点在未来的策略选择时选择合作行为。因此，本文所提出的重复博弈转发模型可以很好地应用于一般的分簇路由协议。
图2 博弈过程
Fig. 2 Game process
3 仿真实验以及结果分析
仿真实验选取分簇路由协议中最经典的LEACH协议进行实验分析，检验基于LEACH协议的重复博弈模型的性能，利用Matlab仿真工具进行仿真实验。通过对分簇路由协议LEACH[18-20]加入惩罚机制前后性能的对比以及加入不同程度的惩罚机制后网络性能的对比，证明了该模型的优越性。设网络的生命周期为出现首个死亡节点的时间。该模型参数设置如表1所示，基于文献[17]可以得出在两跳范围内节点的成功传输的概率大约0.9，所以在本文将p值设定为0.9。
表1 网络参数设置
Table 1 Network parameters
图3所示为网络模拟运行10次的网络寿命图。从图3可以看出：当采取最严苛的惩罚策略(即一旦节点采取自私行为，其将在以后的数据传输中均被惩罚作为簇头节点直至死亡)时，网络的平均寿命约为3 800轮，不采取惩罚措施网络的平均寿命约为4 600轮，不采取惩罚措施网络的寿命要高于采取惩罚措施的寿命约21.05%。
图3 采取严苛惩罚机制网络寿命
Fig. 3 Network lifetime of severe punishment mechanism
图4所示为网络模拟运行10次时网络整体效用图，网络整体效用即为网络寿命结束之前所有节点所获得效用值的总和。从图4可以看出：由于惩罚机制的引入，迫使节点之间相互合作，使得网络的整体收益有所提升。网络采取惩罚措施(最严苛)模拟运行10次所得的平均网络整体效用为7.7×105，而不采取惩罚措施所获得的平均效用为7.1×105。由此可知，即使在最严苛的惩罚措施下，网络模拟运行10次后所得的平均网络整体效用都要高于不采取惩罚措施的网络效用。
图4 采取严苛惩罚机制网络效用
Fig. 4 Network utility of severe punishment mechanism
从图3和图4可以看出：当采用最严苛的惩罚策略，即使不采取惩罚措施的网络寿命要高于采取惩罚措施的网络寿命约21.05%，但在网络寿命终止时采取惩罚措施所获得的整体效用仍会高于不采取惩罚策略的网络效用，由此可以得出采取惩罚策略虽然会减少网络寿命，但是对提升网络的数据传输性能是有效的。
图5所示为不同惩罚轮数对网络生命周期的影响，图5中离散点为不同惩罚轮数下实验10次所获得的平均数据，曲线为数据拟合的结果，前8个数据采用线性拟合方式，其后实验数据采用三阶非线性拟合。从图5可以看出：网络的生命周期在惩罚节点为250轮左右时出现跳变，生命周期明显提升，在250轮以后随着惩罚轮数的增加，网络生命周期不断下降。
图5 不同惩罚轮数下的网络生命周期
Fig. 5 Network lifetime cycle under different penalty rounds
图6所示为不同惩罚轮数对网络整体效用值的影响，采用与图5中相同的数据拟合方式。从图6可以看出：在250轮以前网络效用保持在一个较低的水平，而当节点惩罚轮数增加到250轮以后，网络效用跳变提升，惩罚轮数在250轮以后，随着惩罚轮数的增加，网络效用又会缓慢下降。
图6 不同惩罚轮数下的网络效用
Fig. 6 Network utility under different penalty rounds
从图5和图6可以看出：当惩罚轮数到达250轮时，网络的效用值与生命周期均会出现明显的变化。当惩罚轮数小于250轮时，由于惩罚程度不足以对自私节点产生足够的震慑，造成网络性能的下降；当惩罚轮数达到250轮左右时，网络的效用值与生命周期迅速提升，证明250轮左右的惩罚机制对节点已经产生了足够的震慑，抑制了节点的自私行为；当惩罚轮数超过250轮时，网络的生命周期与效用值均下降。这说明对节点的惩罚程度有1个最佳值，证明了最佳惩罚轮数存在的合理性。当超过最佳值时，网络的生命周期与网络效用不升反降。因此，对节点的惩罚必须在一定的范围之内，这样既可以达到既震慑节点的自私性，又提高网络性能的目的。
图7所示为采取最优惩罚轮数的网络寿命与不采取惩罚策略网络寿命的对比，网络模拟运行10次。从图7可以看出：不采取惩罚措施网络寿命约为4 600轮，采取最优惩罚轮数策略网络寿命约为4350轮，不采取惩罚措施的网络寿命要高于采取最优惩罚轮数策略的网络寿命约5.75%。
图7 采取最优惩罚轮数的网络寿命
Fig. 7 Network lifetime of optimal penalty rounds
图8所示为采取最优惩罚轮数策略与不采取惩罚措施的网络整体效用对比图，网络模拟运行10次。从图8可以看出：采取最优惩罚轮数策略在网络寿命终止时所获得的收益明显高于不采取惩罚策略的网络整体效用，提升约22.83%。
无线传感器网络采取最优惩罚轮数的惩罚策略，将会在保证最小的减少网络寿命的同时，最大提升网络的整体收益，从图7和图8可以看出网络的整体收益相对于不采取惩罚策略提升约22.83%。
图8 采取最优惩罚轮数网络效用
Fig. 8 Network utility of optimal penalty rounds
4 结论
1) 以无限次重复博弈理论规范网络簇头节点的行为，通过引入惩罚机制，迫使节点之间相互合作，以实现最佳网络性能。
2) 建立了基于无限次重复博弈的网络模型，针对节点的自私行为引入不同程度的惩罚机制，并发现对自私节点的惩罚程度(惩罚轮数)会极大影响网络的生命周期和网络效用。
3) 在WSN中不仅要对自私节点采用惩罚措施，而且需要确定对自私节点的最优惩罚程度，即在保证自私节点受到足够震慑的同时，又不会对自私节点产生过大的伤害，在尽量保证网络生存时间的同时，又可提升网络的整体效用。
参考文献：
[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. Wireless sensor networks: a survey[J]. Computer Networks, 2002, 38(4): 393-422.
[2] LIU Qiang, HUANG Xiaoming, LENG Supeng, et al. Deployment strategy of wireless sensor networks for Internet of Things[J]. China Communications, 2011, 8(8): 111-120.
[3] LIAO Peikai, CHANG Minkuan, JAY KUO C C. A statistical approach to contour line estimation in wireless sensor networks with practical considerations[J]. IEEE Transactions on Vehicular Technology, 2009, 58(7): 3579-3595.
[4] YONG Qidong, CHEN Yang, YE Xiwen. Lifetime of WSN research based on energy balance[J]. Applied Mechanics and Materials. 2013, 303/304/305/306: 231-235.
[5] CHEN Bo, MAO Jianlin, GUO Ning, et al. An incentive detection mechanism for cooperation of nodes selfish behavior in wireless sensor networks[C]// 25th Control and Decision Conference (CCDC). Guiyang, 2013: 4021-4024.
[6] 范如国. 博弈论[M]. 武汉: 武汉大学出版社, 2011: 221-227.
FAN Ruguo. Game theory[M]. Wuhan: Wuhan University Publishing Ceremony, 2011: 221-227.
[7] WANG Jiangtao, CHEN Zhigang, DENG Xiaoheng. A trustworthy energy-efficient routing algorithm based on game-theory for WSN[C]// IET International Communication Conference on Wireless Mobile and Computing (CCWMC 2009). Shanghai, 2009: 192-196.
[8] 王博, 黄传河, 杨文忠, 等. Ad Hoc网络中基于惩罚机制的激励合作转发模型[J]. 计算机研究与发展, 2011, 48(3): 398-406.
WANG Bo, HUANG Chuanhe, YANG Wenzhong, et al. An incentive-cooperative forwarding model based on punishment mechanism in wireless Ad Hoc networks[J]. Journal of Computer Research and Development, 2011, 48(3): 398-406.
[9] JAMIN B S, CHATTERJEE M, SAMANTA T. A game theoretic routing framework based on energy-delay conservation in WSNs[C]// 2015 IEEE Tenth International Conference on Intelligent Sensors, Sensor Networks and Information Processing (ISSNIP). Singapore, 2015: 1-5.
[10] LI Yuanjie, XU Hongyun, CAO Qiying, et al. Evolutionary game-based trust strategy adjustment among nodes in wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2015, 11(2): 1-12.
[11] LIU Yan. The application of Nash equilibrium in trust model of deterministic wireless sensor network[C]// 2014 Enterprise Systems Conference (ES). Shanghai, 2014: 284-288.
[12] AKKAYA K, YOUNIS M. A survey on routing protocols for wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(3): 325-349.
[13] SUNDARESWARAN P, VARDHARAJULU K N, RAJESH R S. DECH: equally distributed cluster heads technique for clustering protocols in WSNs[J]. Wireless Personal Communications, 2015, 84(1): 137-151.
[14] QIAN Kaiguo. A clustering routing algorithm for sensor network based on distance probability[C]// 10th International Computer Conference on Wavelet Active Media Technology and Information Processing (ICCWAMTIP). Chengdu, 2013: 113-116.
[15] SHI Haiyan, WANG Wanliang, CHEN Shengyong, et al. Game theory for wireless sensor networks: a survey[J]. Sensors, 2012, 12(7): 9055-9097.
[16] RAJA P, DANANJAYAN P. Game theory based cooperative MIMO routing scheme for lifetime enhancement of WSN[J]. International Journal of Wireless Information Networks, 2015, 22(2): 116-125.
[17] WEN Hao, LIN Chuang, REN Fengyuan, et al. Retransmission or redundancy: transmission reliability study in wireless sensor networks[J]. Science China Information Sciences, 2012, 55(4): 737-746.
[18] SINGH K. WSN LEACH based protocols: a structural analysis[C]// 2015 International Conference and Workshop on Computing and Communication (IEMCON). Vancouver, Canada: IEEE, 2015: 1-7.
[19] PASHA M A, KHAN J H, MASUD S. I-LEACH: energy- efficient routing protocol for monitoring of irrigation canals[J]. Simulation, 2015, 91(8): 750-764.
[20] TANG Gaoming, LI Layuan, GAO Jipeng. IR-LEACH: an improved LEACH protocol for WSN[J]. Applied Mechanics and Materials. 2013, 373/374/375: 388-392.
(编辑 杨幼平)
收稿日期：2016-07-16；修回日期：2016-09-19
基金项目(Foundation item)：国家自然科学基金资助项目(61107040)；吉林大学研究生创新研究计划项目(2015111) (Project(61107040) supported by the National Natural Science Foundation of China; Project(2015111) supported by Graduate Innovation Research Program of Jilin University)
通信作者：董颖，博士，副教授，从事无线网络通信研究；E-mail: dongying@ jlu.edu.cn
