基于博弈论的QoS协作WSNs路由算法
摘 要： 针对无线传感器网络中各个节点之间通信路由单一、无法充分调动合适的路由节点用于下一跳协作通信而浪费不必要的带宽、时延和能耗，提出一种基于博弈论的QoS协作路由算法（QACR），通过研究各个传感器节点的距离、能耗速度与QoS需求量之间的博弈关系，建立基于QoS需求的博弈模型。将协作通信和路由机制相结合，在博弈模型的理论基础上为中心节点选择一个或者多个中继节点，共同协作将数据包发送至目的地址。仿真验证结果表明，这种方法可以减少节点通信的能量消耗和网络延迟，避免网络由于能耗过快、节点死亡率过高而导致的网络断层或瘫痪，保证网络的可靠性QoS需求。
关键词： 博弈论； QoS； 协作通信； 无线传感器网络； 路由协议
中图分类号： TN915?34； TP393 文献标识码： A 文章编号： 1004?373X（2016）16?0108?04
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 relationship between energy consumption rate and distance of each sensor node， and demand of QoS. In combination with the cooperative 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
0 引 言
在人机交互愈加频繁的现代科技世界中，人类对事物感知的精确度和实时性需求越来越高，环境监测、交通管理、国防军事和国家安全以及一些应急通信应用需要优良先进的网络部署和业务承载方案。无线传感器网络（WSNs）能够实现传感器节点在监控区域内检测数据，并能自由地组网通信，具有广阔的应用前景。由于无线自组织网络节点能量有限，WSNs现在面临最重要的问题是如何在不影响其自身通信性能的前提下有效延长网络的生命周期，保证网络的QoS需求。
目前有大量学者在对改进WSNs性能方面做出了很大的贡献。文献[1]首次提出了著名的LEACH算法，利用分布式方法在传感器节点群中以一定的概率竞争簇首节点（CHs），极大降低了节点在数据通信中耗费的能量，但无法在全局协同的情况下确定合适的CHs数量，维持CHs与成员节点数量、网络能量消耗速度以及节点寿命的平衡稳定。博弈论用来研究某些活动参与者的行为在一些主动或被动作用的影响下的决策方式与均衡问题。它已被广泛的应用在WSNs的优化和配置中，李明欣等人对非合作博弈的无线资源分配中的纳什均衡点的存在性和惟一性进行论证[2]，用接入控制算法动态地调整网络中某一区域分配的连接数量，保证通信的可靠性。鄢旭等人针对WSNs功率分配优化需求[3]，利用非合作博弈原理，将功率分配问题转换为信干噪比收益，利用节点移动特征在转发过程中减少消息的复制转发次数，为节点提供发射功率策略，提高消息递交率并降低网络能耗。
本文提出一种基于博弈论的QoS协作路由算法（QACR），针对无线传感器网络中各个节点之间通信路由单一、无法充分调动合适的下一跳节点用于协作通信而浪费不必要的带宽、时延和能量等问题，研究各个传感器节点的距离、能耗速度、协作传输能力与QoS需求量之间的博弈关系，建立基于QoS需求的博弈模型；并将协作通信和路由机制相结合，通过为路由上的节点选择一个或者多个中继节点协助发送数据包，以减少节点的能量消耗和网络延迟，避免网络由于能耗过快、节点死亡率过高而导致的网络断层或瘫痪，保证网络可靠性和QoS需求。
1 网络协作通信架构
WSNs节点通常随机散布于广阔的监测区域中，采用分簇协作的网络模型，如图1所示。
簇内节点将采集到的信息发送到CHs经数据融合后统一发送至基站（Sink），当CHs无法与Sink直接通信时，就必须建立中继节点连接CHs之间的通信。本文将协作通信与路由机制相结合，通过为路由中的节点选择一个或者多个中继节点协助转发数据包，实现CHs间的协作通信。 采用的WSNs模型具有以下特点： （1） WSNs中的N个传感器节点随机分布在边长为L的正方形区域中，无线传感器网络[G（N，E，W）]中存在节点[ni]及其邻居节点mi；
（2） 节点ni可以通过某条路由[eij=ni，nj]将自己的数据转发，总的路由集合为E；
（3） 节点ni与nj之间的距离为dij，最大距离为R，由此得：[?ni，nj∈N，dij≤R?ni，nj∈E]；
（4） CHs负责数据融合和外界通信；Sink节点是固定的、可维护的并且有足够的能量供应；
（5） 所有节点具有相同的规格和有限的能源供应，都可以充当CHs和成员节点。节点初始能量为[Estart]，并且所有节点的能量阈值都为[Ethres]，在经过每轮的数据传输之后节点剩余能量为Eremain。
在数据传输之前，每个簇群需确定自己的协作传输单元来协调数据的汇聚和发送。作为协作传输单元的成员节点（中心节点）在网络簇群中有大量的邻居节点（数目为n），当n越大时，该中心节点就具有很强的能力来为内部节点传送数据，因此中心节点就必须保证自己有足够的剩余能量，用于维持作为协作传输单元的成员节点的能量消耗和生存时间。根据节点的舒适能量和剩余能量得出节点协作传输能力的评估公式为：
[C=λn+（1-λ）EstartEremain] （1）
QoS用来衡量网络路由效用的可靠标准。通过研究网络链路质量中各参数的影响程度，计算出每个节点ni的偏移度参数θi和敏感度因子[φi0< φi≤1]，若网络的最大参数偏移度为Ti，则网络的总偏移度系数为：
[Pi=i=1kφiTi-θi] （2）
采用人工神经网络学习算法中的Sigmoid函数，实现网络中不同节点的QoS统一量化[4]：
[Qi=A1+exp-BPi] （3）
通过对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需求向量的效率因子为：
[ei=C21-i=1kφiθii=1kφi] （4）
网络中的成员节点进行通信时能量消耗速度越大，则节点的生命强度就越弱，容易导致整个无线传感器网络过早衰竭或瘫痪。而中心节点ni与中继节点nj之间的距离也是决定网络节点协作通信性能的重要原则之一，选择合适的中继节点可以避免不必要的数据冗余和延迟。本文提出的博弈模型的效用函数基于网络QoS需求量Qi、节点的能耗速度vi，ni与nj之间的距离dij以及节点协作传输能力C，路由选择博弈模型中的总效用函数为：
[P（Q）=Ci=1KQiEi-i=1KQi22-i=1KQidijvi-ηi≠jQiQj] （5）
当[P（Q）]的值最大时便可得到最佳的QoS需求量，对式（5）中的Qi求导得：
[?PQ?Qi=eiC-Qi+ηi≠jQj-dijvi] （6）
[Qi=eiC+ηi≠jQj-dijvi] （7）
令式（6）为零，当式（7）成立时，路由选择博弈模型的总效用函数达到最大，此时，WSNs中的节点可以在能量消耗、通信延迟以及数据冗余最小的情况下，成功传输数据至目的地址。这样便可延长网络的生命周期，满足网络QoS需求。路由选择发生时，中心节点与中继节点之间就会开始一场选择与判断转发的博弈过程。此时发送协作传输的节点与每一个邻居协作传输节点成为博弈的参与者，根据节点的QoS需求量以及博弈效用值判断路由决策，选择合适的路由传送数据。 [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 topologies and routing algorithms of some WSNs in high?speed railway [C] // Proceedings of 2015 27th Chinese Control and Decision 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 energy efficiency in wireless sensor networks： latest trends [J]. Journal 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.