基于博弈论能耗均衡的无线传感网络路由算法

（1.江苏联合职业技术学院 信息中心，江苏 南京211135；2.江南大学 理学院，江苏 无锡214112）


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

    关键词： 无线传感网；路由；能量均衡；进化博弈理论；贪婪

    中图分类号： TN925   

    文献标识码： 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最近的节点作为转发节点。

tx5-t1.gif

1.1 基于EGT的区域选择算法EGT-RS

tx5-1.1-x1.gif

    复制动态在每个博弈理论间隔进化一个新的数据包分布矢量[16]，不断进化，直到得到最优的分布矢量X*。实际上，计算分布矢量X*的关键在于设计适度函数FF(Fitness Function)，适度函数Fk(X)的定义如下：

    tx5-gs1.gif

其中Etr、Etx分别节点接收、发送一个数据包所需的能量。

1.2 复制动态

    从子区域l到子区域k的切换概率Pk，l(X)，其与两个子区域l、k的适度函数相关，如式(2)所示。

tx5-gs2-3.gif

    从子区域k到其他所有子区域的转换概率之和应等于1：

    tx5-gs4.gif

    因此，复制动态的差异值反映了子区域k的流入和流出的数据包净差：

     tx5-gs5-6.gif

    因此，对于仅有两个子区域的场景，利用式(2)，可计算过渡概率矩阵P：

tx5-gs7-8.gif

    当所有子区域的流入和流出数据包相等时，系统就到达稳定状态。

1.3 进化均衡

tx5-gs9-13.gif

2 性能分析

    利用OMNeT++4.22网络仿真器建立仿真平台，仿真参数如表1所示。传感节点随机分布于二维的100×100 m2区域。

tx5-b1.gif

    提出的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所示。

tx5-t2.gif

    从图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协议中的每个节点利用纳什均衡做出最优的转发决策，从能量均衡角度选择转发区域，而随机选择增加了能量消耗。

tx5-t3.gif

3 结论

    针对无线网络路由问题，本文提出了基于博弈论能耗均衡的无线传感网络路由算法EGT-EBGR。EGT-EBGR算法通过平衡网络能量消耗，提高网络寿命。EGT-EBGR首先将数据包携带节点的传输范围划分几个转发子区域，然后再利用进化博弈算法，从中选择一个子区域作为转发区域，再从选择的子区域内，利用贪婪算法选出下一跳转发节点。仿真结果表明，提出的EGT-EBGR协议的网络寿命比随机选择下一跳转发节点(Random+Random)高了近38%，能量消耗下降了64%。

谢谢楼主分享

基于博弈论能耗均衡的无线传感网络路由算法

谢谢楼主分享

基于博弈论能耗均衡的无线传感网络路由算法