基于博弈论能耗均衡的无线传感网络路由算法 基于博弈论能耗均衡的无线传感网络路由算法 为了平衡能量消耗，延长网络寿命，提出基于博弈论能耗均衡的无线传感网络路由算法——EGT-EBGR。EGT- EBGR路由的目的是使节点能耗均衡，进而延长网络寿命。首先，将发送节点的传输范围划分几个转发子区域， 然后再结合进化博弈论EGT(Evolutionary Game Theory)，从平衡负载角度，从转发子区域内选择一个转发子区 域，再利用贪婪算法从此转发子区域内选择一个节点作为下一跳的转发节点。通过进化博弈论和贪婪算法 GA(Greedy Algorithm)平衡负载，缩短传输距离，有效地降低地能量消耗速度，进而延长网络寿命。仿真数据表 明，提出的EGT-EBGR协议能够有效地平衡能量消耗，扩延了网络寿命。 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）