文献标识码：A
DOI：10.16157/j.issn.0258-7998.2017.07.029
中文引用格式：朱亚东，高翠芳. 基于博弈论能耗均衡的无线传感网络路由算法[J].电子技术应用，2017，43(7)：114-116，126.
英文引用格式：Zhu Yadong，Gao Cuifang. Energy-balanced routing algorithm based on Game-Theory for WSNs[J].Application of Electronic Technique，2017，43(7)：114-116，126.
0 引言
提高节点能量利用率、扩延网络寿命成为无线传感网络(Wireless Sensor Networks，WSNs)的研究热点[1]。通过协调节点间通信来平衡网络能量消耗，是提高网络寿命最为有效的技术之一[2-3]。在这些技术中，路由决策起着重要作用，因为路径的选择直接影响到节点能量消耗[4-5]。
由于地理路由协议(Geographical Routing Protocols，GRPs)无需建立路由表，也无需进行路由发现和路由维护，使得GRPs非常适用于无线传感网络。典型的地理路由协议有GPSR(Greedy Perimeter Stateless Routing)[6]、GOAFR[7]、GRR[8]、GAR[9]、BVGF[10]、GEAR(Geographical and Energy Aware Routing)[11]、OVCR[12]、VAA[13]。地理路由协议GRPs的不足之处在于它没有从全局考虑网络信息，对于无线传感网络而言，能量利用率是非常重要的性能指标[14]。
为此，本文针对地理路由协议GRPs的特性及其不足，利用进化博弈理论(Evolutionary Game Theory，EGT)，平衡了网络能量消耗。通过EGT建立平衡能量消耗的方案，进而扩延网络寿命。此外，EGT能够在全局信息未知的环境下进行正确的决策。
1 EGT-EBGR算法
EGT-EBGR算法目的是平衡网络能量消耗，使得节点的能量消耗速度相近。依据节点密度，源节点S将其传输范围划分为K个子区域。首先利用基于EGT的区域选择算法(EGT-based Regions Selection，EGT-RS)选择下一个转发子区域，然后再利用贪婪地理算法选择转发节点。
如图1所示，源节点S将它向目的节点D的传输方向的邻居节点划分了4个区域，分别为R1、R2、R3、R4。然后，利用EGT-RS算法，为当前数据包选择了一个转发区域。假定选择了R2作为当前数据包的转发区域，最后，再在R2区域，利用贪婪转发算法选择离目的节点D最近的节点作为转发节点。
1.1 基于EGT的区域选择算法EGT-RS
复制动态在每个博弈理论间隔进化一个新的数据包分布矢量[16]，不断进化，直到得到最优的分布矢量X*。实际上，计算分布矢量X*的关键在于设计适度函数FF(Fitness Function)，适度函数Fk(X)的定义如下：
其中Etr、Etx分别节点接收、发送一个数据包所需的能量。
1.2 复制动态
从子区域l到子区域k的切换概率Pk，l(X)，其与两个子区域l、k的适度函数相关，如式(2)所示。
从子区域k到其他所有子区域的转换概率之和应等于1：
因此，复制动态的差异值反映了子区域k的流入和流出的数据包净差：
因此，对于仅有两个子区域的场景，利用式(2)，可计算过渡概率矩阵P：
当所有子区域的流入和流出数据包相等时，系统就到达稳定状态。
1.3 进化均衡
2 性能分析
利用OMNeT++4.22网络仿真器建立仿真平台，仿真参数如表1所示。传感节点随机分布于二维的100×100 m2区域。
提出的EGT-EBGR协议与3种随机选择方案进行比较。这3种随机选择方案分别为：(1)随机+随机（Random+Random）：表示随机选择转发区域，并且也随机地选择转发节点；(2)（EGT-RS+Random）：利用EGT-RS算法选择转发区域，然后再从转发区域内随机地选择转发节点；(3)随机+GA（Random+GA）：随机地选择转发区域，然后再利用贪婪算法从区域内选择转发节点。
2.1 网络寿命
本次实验中，数据包产生率为2 packets/s，节点数从120～520变化，仿真结果如图2所示。
从图2可知，网络寿命随节点数的增加呈上升趋势。正如预期的，Random+Random方案的寿命最短，依次为Random+GA、EGT-RS+Random，而提出的EGT-EBGR协议最高。原因在于EGT-RS+Random方案利用EGT-RS算法选择转发区域，平衡网络能量消耗速度。此外，从图1可知，提出的EGT-EBGR协议的网络寿命比Random+Random、EGT-RS+Random分别提高了近38%、9%。
2.2 平均每个数据包的能量消耗
本次实验分析向目的节点传输一个数据包所消耗的平均能量，实验数据如图3所示。从图3可知，提出的EGT-EBGR的能量消耗比Random+Random下降了约64%。原因在于：EGT-EBGR协议中的每个节点利用纳什均衡做出最优的转发决策，从能量均衡角度选择转发区域，而随机选择增加了能量消耗。
3 结论
针对无线网络路由问题，本文提出了基于博弈论能耗均衡的无线传感网络路由算法EGT-EBGR。EGT-EBGR算法通过平衡网络能量消耗，提高网络寿命。EGT-EBGR首先将数据包携带节点的传输范围划分几个转发子区域，然后再利用进化博弈算法，从中选择一个子区域作为转发区域，再从选择的子区域内，利用贪婪算法选出下一跳转发节点。仿真结果表明，提出的EGT-EBGR协议的网络寿命比随机选择下一跳转发节点(Random+Random)高了近38%，能量消耗下降了64%。
参考文献
[1] ZHANG H，SHEN H.Balancing energy consumption to maximize network lifetime in data-gathering sensor networks[J].IEEE Trans.Parallel Distrib.Syst.，2009，20(10)：1526-1539.
[2] 罗四维，侯孟书，周益民.一种新的基于能量消耗速率模型的分簇路由协议[J].计算机科学，2012，39(6)：46-50.
[3] IYER G，AGRAWAL P，MONNERIE E，et al.Performance analysis of wireless mesh routing protocols for smart utility networks[C].In Proc.IEEE Int.Conf.Smart Grid Commun.，Oct.2011：114-119.
[4] PANTAZIS N A，NIKOLIDAKIS S A，VERGADOS D D.Energy-efficient routing protocols in wireless sensor networks：A survey[J].IEEE Commun.Surv.Tuts.，2013，15(2)：551-591.
[5] ZHANG D，LI G，ZHENG K，et al.An energy balanced routing method based on forward-aware factor for wireless sensor networks[J].IEEE Trans.Ind.Informat.，2014，10(1)：766-773.
[6] SEADA K，HELMY A，GOVINDAN R.On the effect of localization errors on geographic face routing in sensor networks[C].In：Proc.of the 3rd International Symposium on Information Processing in Sensor Networks，IPSN’04，2004：71-80.
[7] KUHN F，WATTENHOFER R，ZHANG Y，et al.Geometric ad-hoc routing：of theory and practice[C].Proc.of the Twenty-Second Annual Symposiumon Principles of Distributed Computing，PODC’03，2003：63-72.
[8] KERMARREC A M，TAN G.Greedy geographic routing in large-scale sensor networks：a minimum network decomposition approach[C].Proc.of the Eleventh ACM International Symposium on Mobile Ad Hoc Networking and Computing，MobiHoc’10，2010：161-170.
[9] LIU W J，FENG K T.Greedy routing with anti-void traversal for wireless sensor networks[J].IEEE Trans.Mob.Comput.，2009，8(7)：910-922.
[10] Xing Guoliang，Lu Chenyang，PLESS R，et al.Impact of sensing coverage on Greedy geographic routing algorithms[J].IEEE Trans.Parallel Distrib.Syst.2006，17(4)：348-360.
[11] YU Y，GOVINDAN R，ESTRIN D.Geographical and energy aware routing: a recursive data dissemination protocol for wireless sensor networks[J].Technical Report CSD-TR-01-0023，UCLA Computer Science Department，2011，3(6)：36-42.
[12] HSU M T，LIN F Y S，CHANG Y S，et al.Reliable Greedy forwarding in obstacle-aware wireless sensor networks[J].Proc.of the 9th International Conference on Algorithms and Architectures for Parallel Processing，ICA3PP’09，2009：797-808.
[13] JOSHI G P，KIM S W.A distributed geo-routing algorithm for wireless sensor networks[J].Sensors，2009，9(6)：4083-4103.
[14] TEMBINE H，ALTMAN E，EL-AZOUZI R，et al.Evolutionary games in wireless networks[J].IEEE Trans.Syst.，Man，Cybern.B，Cybern.，2010，40(3)：634-646.
[15] ABD M A，SINGH B K，AL RUBEAAI S F，et al.Game theoretic energy balanced(GTEB) routing protocol for wireless sensor networks[C].In Proc.IEEE Wireless Commun.Netw.Conf.(WCNC)，2014：2564-2569.
[16] MEHMMOD A，SARAB F.Extending wireless sensor network lifetime with global energy balance[J].IEEE Sensors Journal，2015，15(9)：5053-5064.
[17] BROUWER L E J.Uber abbildung von mannigfaltigkeiten[J].Math.Ann.，2012，71(4)：32-43.
作者信息：
朱亚东1，高翠芳2
（1.江苏联合职业技术学院 信息中心，江苏 南京211135；2.江南大学 理学院，江苏 无锡214112）