基于博弈论的QoS协作WSNs路由算法

郝贵和，张天娇，伍红英，林家泉

（中国民航大学 航空自动化学院，天津　300300）

基于博弈论的QoS协作WSNs路由算法

郝贵和，张天娇，伍红英，林家泉

（中国民航大学 航空自动化学院，天津300300）

摘要：针对无线传感器网络中各个节点之间通信路由单一、无法充分调动合适的路由节点用于下一跳协作通信而浪费不必要的带宽、时延和能耗，提出一种基于博弈论的QoS协作路由算法（QACR），通过研究各个传感器节点的距离、能耗速度与QoS需求量之间的博弈关系，建立基于QoS需求的博弈模型。将协作通信和路由机制相结合，在博弈模型的理论基础上为中心节点选择一个或者多个中继节点，共同协作将数据包发送至目的地址。仿真验证结果表明，这种方法可以减少节点通信的能量消耗和网络延迟，避免网络由于能耗过快、节点死亡率过高而导致的网络断层或瘫痪，保证网络的可靠性QoS需求。

关键词：博弈论；QoS；协作通信；无线传感器网络；路由协议

0　引　言

在人机交互愈加频繁的现代科技世界中，人类对事物感知的精确度和实时性需求越来越高，环境监测、交通管理、国防军事和国家安全以及一些应急通信应用需要优良先进的网络部署和业务承载方案。无线传感器网络（WSNs）能够实现传感器节点在监控区域内检测数据，并能自由地组网通信，具有广阔的应用前景。由于无线自组织网络节点能量有限，WSNs现在面临最重要的问题是如何在不影响其自身通信性能的前提下有效延长网络的生命周期，保证网络的QoS需求。

目前有大量学者在对改进WSNs性能方面做出了很大的贡献。文献［1］首次提出了著名的LEACH算法，利用分布式方法在传感器节点群中以一定的概率竞争簇首节点（CHs），极大降低了节点在数据通信中耗费的能量，但无法在全局协同的情况下确定合适的CHs数量，维持CHs与成员节点数量、网络能量消耗速度以及节点寿命的平衡稳定。博弈论用来研究某些活动参与者的行为在一些主动或被动作用的影响下的决策方式与均衡问题。它已被广泛的应用在WSNs的优化和配置中，李明欣等人对非合作博弈的无线资源分配中的纳什均衡点的存在性和惟一性进行论证［2］，用接入控制算法动态地调整网络中某一区域分配的连接数量，保证通信的可靠性。鄢旭等人针对WSNs功率分配优化需求［3］，利用非合作博弈原理，将功率分配问题转换为信干噪比收益，利用节点移动特征在转发过程中减少消息的复制转发次数，为节点提供发射功率策略，提高消息递交率并降低网络能耗。

本文提出一种基于博弈论的QoS协作路由算法（QACR），针对无线传感器网络中各个节点之间通信路由单一、无法充分调动合适的下一跳节点用于协作通信而浪费不必要的带宽、时延和能量等问题，研究各个传感器节点的距离、能耗速度、协作传输能力与QoS需求量之间的博弈关系，建立基于QoS需求的博弈模型；并将协作通信和路由机制相结合，通过为路由上的节点选择一个或者多个中继节点协助发送数据包，以减少节点的能量消耗和网络延迟，避免网络由于能耗过快、节点死亡率过高而导致的网络断层或瘫痪，保证网络可靠性和QoS需求。

1　网络协作通信架构

WSNs节点通常随机散布于广阔的监测区域中，采用分簇协作的网络模型，如图1所示。

图1　网络协作通信架构

簇内节点将采集到的信息发送到CHs经数据融合后统一发送至基站（Sink），当CHs无法与Sink直接通信时，就必须建立中继节点连接CHs之间的通信。本文将协作通信与路由机制相结合，通过为路由中的节点选择一个或者多个中继节点协助转发数据包，实现CHs间的协作通信。采用的WSNs模型具有以下特点：

（1）WSNs中的N个传感器节点随机分布在边长为L的正方形区域中，无线传感器网络G（N，E，W）中存在节点ni及其邻居节点mi；

（4）CHs负责数据融合和外界通信；Sink节点是固定的、可维护的并且有足够的能量供应；

（5）所有节点具有相同的规格和有限的能源供应，都可以充当CHs和成员节点。节点初始能量为Estart，并且所有节点的能量阈值都为Ethres，在经过每轮的数据传输之后节点剩余能量为Eremain。

在数据传输之前，每个簇群需确定自己的协作传输单元来协调数据的汇聚和发送。作为协作传输单元的成员节点（中心节点）在网络簇群中有大量的邻居节点（数目为n），当n越大时，该中心节点就具有很强的能力来为内部节点传送数据，因此中心节点就必须保证自己有足够的剩余能量，用于维持作为协作传输单元的成员节点的能量消耗和生存时间。根据节点的舒适能量和剩余能量得出节点协作传输能力的评估公式为：

采用人工神经网络学习算法中的Sigmoid函数，实现网络中不同节点的QoS统一量化［4］：

通过对QoS的统一量化，可以将QoS需求从一个抽象的概念转化为形象具体的数据量用于之后建立准确的博弈模型。

2　基于博弈论的路由算法

网络模型中的节点都有自私理性的偏向，每个传感器节点都想使自身用于数据通信的能量最小化，以达到最长的寿命，对于自身检测到的或中途转发的数据都会进行丢弃或者转发的选择。本文的路由协作算法在网络协作通信的过程中对传输单元和邻居协作传输单元进行不断的博弈，最终为节点找到合适的路由，确定各个网络元素的性质，在满足网络QoS需求的前提下尽可能延长网络的生存时间和QoS需求。

2.1博弈模型

博弈论用来研究某些活动参与者的行为在一些主动或被动作用的影响下的决策方式，或者某种行为的均衡问题，它以数学为基础研究行为活动中的参与者如何做出决断从而获得最大利益。传感器节点的能耗、感知传输数据总量，以及网络的生命周期和可靠度等都是衡量WSNs性能的标准。本文研究的主要对象是基于博弈论的思想设计出网络中节点相互协作的路由算法，目的是使节点在合作路由的过程中能联合优化网络性能，保证其QoS效果，尽可能地延长网络的生命周期。因此设定节点理性偏好为：

（1）尽可能保证网络的运行周期和QoS效果［5］，防止节点过早死亡造成网络瘫痪，发生通信断层；

（2）在保证自身能量消耗最低的前提下，将足够多的感知数据量传输到基站。

针对上述WSNs节点的理性偏好，结合节点位置、能耗情况、节点协作传输能力以及网络的协同架构等方面，给出路由博弈模型：

网络行动顺序：当节点被随机部署在环境中开始感知数据便是一轮网络博弈的开始，源节点选择合适的路由将数据传输到下一跳节点或者CHs，通过多跳传输到基站，每个参与者都根据前面节点的策略，找到收益最高的路由策略，周而复始直至节点自身能量被消耗殆尽而中断使用。

网络策略：策略是指博弈成员可选择的行为集合，当节点接收到网络中其他节点传输的数据包时，可以放弃转发数据或选择邻居节点转发数据两种策略，用集合的形式表示为：Ti=｛ti1，ti2，…，tii-1，tii，…，tim｝。

网络效益函数：同所有博弈模型一样，网络需要在花费一定代价的前提下才会有效益出现，因此必须权衡最优的路由选择作为博弈策略，以将数据发送到目的地址为效益体现。

设需转发数据的CHs对QoS的需求量为Q=（Q1，Q2，…，Qi，…，Qk），不同节点QoS之间的竞争因子为η，η∈（0，1］时，备选节点QoS无差异；η=0时则说明这个节点的QoS具有极强的路由优势［6］。计算出节点ni对应QoS需求向量的效率因子为：

网络中的成员节点进行通信时能量消耗速度越大，则节点的生命强度就越弱，容易导致整个无线传感器网络过早衰竭或瘫痪。而中心节点ni与中继节点nj之间的距离也是决定网络节点协作通信性能的重要原则之一，选择合适的中继节点可以避免不必要的数据冗余和延迟。本文提出的博弈模型的效用函数基于网络QoS需求量Qi、节点的能耗速度vi，ni与nj之间的距离dij以及节点协作传输能力C，路由选择博弈模型中的总效用函数为：

当P（Q）的值最大时便可得到最佳的QoS需求量，对式（5）中的Qi求导得：

令式（6）为零，当式（7）成立时，路由选择博弈模型的总效用函数达到最大，此时，WSNs中的节点可以在能量消耗、通信延迟以及数据冗余最小的情况下，成功传输数据至目的地址。这样便可延长网络的生命周期，满足网络QoS需求。路由选择发生时，中心节点与中继节点之间就会开始一场选择与判断转发的博弈过程。此时发送协作传输的节点与每一个邻居协作传输节点成为博弈的参与者，根据节点的QoS需求量以及博弈效用值判断路由决策，选择合适的路由传送数据。

2.2路由选择机制

协作通信可以产生空间分集以抵抗信道衰落，提高信息发送成功率。本文将协作通信和路由机制相结合，通过为路由上的节点选择一个或者多个中继节点用于协助发送数据包至目的地址，减少节点的能量消耗和网络延迟，提高系统可靠性，保证其QoS效用。在前文研究WSNs协作通信模型和博弈效益模型的基础上，综合考虑协作节点ni，nj之间距离、网络QoS需求量以及博弈效用值等信息，提出一种基于博弈论的QoS协作路由算法（QACR），路由选择机制的设计思路如下：

Step1：建立网络博弈模型。包括元素主要有：参与者节点集合N、节点ni在每一轮选择的路由策略集合Ti，以及博弈效用值 Pij；ni广播自己的效用值消息P_msg给邻居节点，建立邻居节点信息集合；

Step2：簇内通信的CHs选择过程。所有的节点产生随机数c，当节点的随机数小于T值时，该节点成为候选CHs，自己广播成为候选CHs的消息Candi_msg给通信范围内的所有节点；候选CHs比较自己和邻居节点效用值Pij的大小，为保证博弈模型的效用最大，选择Pij值较大的节点作为正式CHs，广播成为正式CHs的消息；

Step3：选择合适的下一跳CHs。作为中心节点的CHs，如果必须通过中继节点间协作才能将数据送到目的地址，就首先需要评估与各个邻居节点之间的博弈效用值Pij，以获得最大的收益［7］。距离较近且Pij值越大的邻居节点转发数据的可能性更大，更有可能成为合适的协作传输单元；

Step4：簇间通信后的路由转发过程，接收到数据的协作传输节点发送接收消息Recis_msg给中心节点，表示同意搭建路由协作传输上一跳的信息；

Step5：通过路由正式发送数据。CHs广播建簇消息Estab_msg给簇成员节点和协作节点，节点ni接收CHs的确认和时间表，准备发送数据；CHs加入时分多址（TDMA）表，开始接收簇内成员节点发来的感知数据，融合数据并将结果传送给Sink。

以上步骤之后进入稳定传输阶段，节点将数据传输给CHs，再由CHs发送给下一跳的中继节点，期间自身的能量慢慢减少直至消耗殆尽，节点死亡。网络中的节点数量减少，没有被检测到数据或者被遗漏的区域越来越多，最后网络瘫痪，博弈代价体现。

2.3能耗分析

WSNs中的每个节点都是自私理性的，都想节约自己的能量实现自身效益的最大化。假设消息传输中电路发射端消耗的能量为Etrans，Eenlar为前一轮路径衰减之后的功率放大能量，CHs之间直接通信k b数据所需的能量为：

簇间协作通信时，若源CHs选择了（m-1）（m≥1）个协作节点向目标地址发送数据，将源CHs看作第m个协作节点［8］。采用协作路由的办法进行数据传输时，发送k b的通信量所需的总能量为：

式中：Ec是在给定误码率条件下接收端正确接收1 b数据所需的最低能量；Ecs，Ecr分别表示发送电路损耗和接收电路损耗。由式（9）可以得出，只有减少用于数据传输的发送和接收电路，即减少数据传输量或路由跳转次数［9］，才能减小网络能耗，延伸生命周期。

3　仿　真

本文在通过仿真实验对算法性能进行评估，仿真环境为模拟监控网络中100个节点随机分布在200单位的区域中，假设传输环境完全并且不受其他干扰因素影响，监测网路能在除自身因素之外可靠运行［10］。MAC层采用IEEE 802.15.4协议，具体网络参数如表1所示。

表1　网络参数表

图2是将文献［8］中的GARA算法、AODV算法、LEACH算法同QACR算法的平均跳数进行比较，当源节点与目的节点之间的距离一定时，节点都是通过多跳将数据传输到目的节点，每个算法的平均跳数都在随着距离的增加而增加。由图2可以看出AODV，LEACH算法从一开始节点相距最近的时候跳数较大，QACR算法则一直保持基本稳定的跳数并稍高于GARA算法。在距离最大的时候节点的跳数也达到极值，但QACR算法明显低于其余三种算法，这是由于WSNs节点之间的协同通信以及通过博弈效用公式得到了非常合适的中继节点。在多跳数据传输时，QACR通过博弈选择协同中继节点可以减少节点跳转次数，降低网络通信时延。

图2　节点平均跳数

图3是网络能量消耗情况，网络总能耗随着通信轮数增大而增大，当轮数到达极限时网络能量消耗达到顶峰，出现节点死亡或网络瘫痪等情况。由图像的斜率可以得出QACR算法的能量消耗速率低于AODV，LEACH 和GARA。这是通过博弈模型选择出合适协作节点可以降低网络通信跳数，减少不必要的能量消耗和数据冗余，从而延长网络的生命周期，保证网络的QoS质量。

图3　网络节点总耗能

4　结　语

本文提出了基于博弈论的QoS协作路由算法，首先分析了传感器节点的距离、能耗速度与QoS需求量之间的博弈关系，建立基于QoS需求的博弈模型；其次将协作通信和路由机制相结合，在博弈模型的理论基础上为中心节点选择一个或者多个中继节点，共同协作将数据包发送至目的地址。最后仿真验证，这种方法可以减少节点通信的能量消耗和网络延迟，避免网络由于能耗过快、节点死亡率过高而导致的网络断层或瘫痪，为网络可靠性和QoS需求提供很好的保证。

注：本文通讯作者为张天娇。

参考文献

［1］HEINZELMAN W R，CHANDRAKASAN A，BALAKRISH⁃NAN H.Energy⁃efficient communication protocol for wireless microsensor networks［C］//Proceedings of the 33rd Annual Ha⁃waii International Conference on System Sciences.Hawaii：IEEE，2000：1⁃10.

［2］李明欣，陈山枝，谢东亮，等.异构无线网络中基于非合作博弈论的资源分配和接入控制［J］.软件学报，2010，21（8）：2037⁃2049.

［3］鄢旭，陈晶，杜瑞颖，等.基于博弈论的无线网络功率优化模型［J］.计算机应用研究，2012，29（4）：1483⁃1485.

［4］赵昕，张新.基于博弈论的无线传感器网络簇间路由选择算法［J］.计算机应用，2013，33（7）：1813⁃1815.

［5］SHI T，HAN Z，YANG B.QoS evaluation for several typical to⁃pologies and routing algorithms of some WSNs in high⁃speed railway［C］//Proceedings of 2015 27th Chinese Control and De⁃cision Conference（CCDC）.China：IEEE，2015：1402⁃1407.

［6］孙庆中，余强，宋伟.基于博弈论能耗均衡的WSN非均匀分簇路由协议［J］.计算机应用，2014，34（11）：3164⁃3169.

［7］ALSKAIF T，ZAPATA M G，BELLALTA B.Game theory for en⁃ergy efficiency in wireless sensor networks：latest trends［J］.Jour⁃nal of network and computer applications，2015，11（54）：33⁃61.

［8］杨云，孔秀平，颜然，等.面向博弈的无线传感器网络自适应路由算法［J］.小型微型计算机系统，2013，34（10）：2281⁃2285.

［9］RANI S，MALHOTRA J，TALWAR R.Energy efficient chain based cooperative routing protocol for WSN ［J］.Applied soft computing，2015，9（35）：386⁃397.

［10］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.

中图分类号：TN915⁃34；TP393

文献标识码：A

文章编号：1004⁃373X（2016）16⁃0108⁃04

doi：10.16652/j.issn.1004⁃373x.2016.16.029

作者简介：郝贵和（1971—），男，辽宁阜新人，讲师。主要研究方向为航空设备的在线检测和智能控制。张天娇（1993—），女，陕西宝鸡人，硕士研究生。主要研究方向为无线传感器网络。

收稿日期：2015⁃12⁃14

基金项目：天津市应用基础与前沿技术研究计划（自然科学基金）（13JCYBJC42300）；国家自然科学基金委中国民航局联合基金项目（U1333111）

QoS cooperative routing algorithm based on game theory

HAO Guihe，ZHANG Tianjiao，WU Hongying，LIN Jiaquan
（Aviation Automation College，Civil Aviation University of China，Tianjin 300300，China）

Abstract：In wireless sensor networks，the communication route among nodes is single，can not be fully mobilized，and cause the unnecessary waste of bandwidth，delay and energy consumption.Therefore，a QoS cooperative routing algorithm based on game theory is presented in this paper.A game model based on QoS demand is established by studying the game rela⁃tionship between energy consumption rate and distance of each sensor node，and demand of QoS.In combination with the coopera⁃tive communication and routing mechanism，one or more relay node is selected for the central node on the basis of the game model theory to transmit data packets to the destination address.The simulation results show that this method can reduce the energy consumption and network delay of the node communication，and avoid network fault and paralysis caused by excessive energy consumption，high node mortality caused，so as to improve network reliability.

Keywords：game theory；QoS；cooperative communication；wireless sensor network；routing protocol