李荥++王芳++景栋盛++朱斐

摘 要：针对传统路由算法不能很好解决无线传感器网络的能量消耗和负载均衡的问题，提出一种将路径跳数和能量消耗因素考虑在内的基于Q学习的能量负载均衡算法。通过多跳和残余能量来估计网络状态，从而找到复杂度最低的最优路由策略，得到的数据传输路径满足能量消耗最小与负载均衡两个条件，在降低网络能量消耗的同时也延长了网络的生存周期。实验结果表明了算法在节点存活个数、节点剩余能量分布和节点发送成功率方面均取得较好的效果，同时验证了算法可以降低能量消耗，延长网络的整体寿命。

关键词：无线传感器网络 ；Q学习；路由；能量负载均衡

中图分类号：TP311.5 文献标识码：A

Abstract： Aiming at dealing with the problems of energy consumption and load balancing in wireless sensor networks that traditional routing algorithm cannot solve， a new energy load balancing algorithm based on Q-learning is proposed， which takes into account the number of hops， the residual energy of sensor nodes and the node energy consumption， to estimate the state of the network through multi hop and residual energy， and find the optimal routing strategy with the lowest of the complexity. The data are transferred along routine with minimum the energy consumption and the balanced load， thus reducing network energy consumption and prolong the network life cycle. The simulation results showed that the algorithm has a good effect in survival nodes， transfer success rate and residual energy distribution and transmission， which indicates that the algorithm can effectively reduce energy consumption and prolong the network lifetime.

Key words： wireless sensor network Q learning routing energy-efficient load-balancing

1 引 言

無线传感器网络（Wireless Sensor Network， WSN）由传感器节点组成，其计算和交互信息的能力受到约束 [1]。无线传感器网络的工作方式主要是传感器节点采集环境中的信息的同时通过转发机制最终把这些信息传递到称之为Sink节点[2]的网关节点或汇聚节点，接着通过微波、卫星通信或其他方式将汇集到的信息传送到一个主要的位置，直至到达观测者的接收终端。在整个信息的传送过程中，中间的传感器节点需要根据当前的状态来选择下一跳的节点。然而，从整体和长期来看，全局信息的缺乏使得所选择的下一跳转发节点往往未必最佳的。所以，人们更加关注无线传感器网络的路由问题。

在无线传感器网络中，Sink节点附近需要比其他节点转发更多的数据包，从而引起不均匀的网络节点能量消耗。由于这个限制在传统的网络路由算法中很少被考虑到，这往往会导致靠近Sink节点或者关键路上的节点由于过早消耗完能量而提前“死亡”，进而整个网络的功能受到较大影响。另一方面，无线传感器网络较高的动态性使得节点间需要频繁交换信息以便节点了解网络的动态变化情况。

无线传感器网络路由算法是一个多目标优化问题：在保证节点能实时掌握网络动态情况的前提下，保证信息发送的正确性并尽可能发送最小数量的数据包以减少能耗，并从网络整体的角度延长网络的生命期。近年来，针对由于节点提前死亡而导致网络生存周期短的问题，很多相关的算法被研究人员所提出。算法EAMHR[3]实现了能量跳数最小路由，但未能从网络的整体角度考虑均匀分配节点能量消耗。Ileri等人[4]将货币机制引入无线传感网，节点间在通信时支付一定的“货币”作为代价，但是由于其方法要求节点频繁的协商，在加剧了链路的负担的同时也增加了节点能量的消耗。李响等人[5]提出一种基于能量感知的多路径路由算法，但是其路径维护的方法较为复杂。贾杰等人[6]提出了一种基于博弈论的路由策略。但是，由于需要掌握的全局节点信息比较多，而传感器节点的存储和计算能力有限，因此，其方法实用性有限。董国勇等人[7]提出了一种基于蚁群算法的能量均衡路由算法，但是派遣蚂蚁会造成通信开销和网络额外负载。

针对能量消耗不均衡而导致的网络生存周期短的问题，本文提出了一个基于Q学习的无线传感网络路由算法，该算法在保证把信息经过传感节点转发到Sink节点的前提下，能够找出能源消耗和性能的最优平衡点。算法以全局网络作为着眼点进行优化，网络中的节点交换剩余能量，彼此之间的状态-动作对和功能以协作的方式进行协调，使得整个网络的生存周期最长。本文余下的内容组织如下：首先，介绍强化学习一些相关工作和相关路由算法；然后，给出算法建模过程和详细描述；接着，进行仿真实验，给出结果和相关分析；最后，给出结论。

2 相关工作

2.1 无线传感器路由

路由的选择是无线传感网络的基础。根据无线传感网络自身的特点而进行的路由优化通常需要针对以下几点：（1）寻找路由中距离最短的传输路径；（2）均衡、调节节点负载，延长网络寿命；（3）使节点能及时了解网络的动态变化；（4）即使一条传输线路中断，节点仍然可以将信息传输到目的节点。为了提高能量受限的无线传感网络的生存周期来实现网络的均衡负载，通常把负载调整到不同的路径或者节点，这样能量消耗在各节点中得到平衡。通常，路由算法既要使传输所消耗的能量最小，又要尽可能避开那些剩余能量较少的节点，从而延長其寿命，达到最大化网络生存时间的目的。总的来看，无线传感网络的路由算法主要可以分为以下两类。

3 基于Q学习的能量负载均衡路由

当前的节能路由模型很少把降低能耗和负载均衡很好的综合起来考虑，并且解决问题的思路相对比较片面，往往需要通过计算整条路径上的消耗值来实现路由的选择。为了解决当前路由模型的不足即实现最小化能量消耗的同时也考虑均衡节点的负载，本文提出一种基于Q学习的能量负载均衡的路由算法（Q-learning based energy-efficient load-balancing routing，Q-E2LBR）。Q-E2LBR算法利用强化学习的思想建模，充分考虑多跳和残余能量来达到最小化整体能量开销和最大化网络的生存周期。Q-E2LBR算法使数据包沿一个接近最优的路径转发到Sink节点并使用一个节点不断地记录它相邻节点的Q值且能够在获得包的时候立即更新它，当前节点的Q值在其相邻节点的副本中评估，由于无需反馈数据包，减少了数据通信量并延长了网络的生命周期。

3.1 模型和算法描述

无线传感网中每个传感器节点都具有一定的计算能力和存储能力，将这些特点考虑进来，就可以得到与之前的算法不同的方法。在本文所提出的算法中，无线传感网络中的每一个传感器节点都被视为一个agent，这样整个无线传感网络就可以建模成一个多agent系统；每个agent在其邻居节点中选择不同的节点，作为下一跳节点，从而构造出最优路径。通过不断地取样和学习，Q值将会最终收敛到一个稳定的值。将整个无线传感器网络作为一个多agent系统。为了找到最优路径，每一个agent选择一个最优的邻接节作为下一个路由目标。

无线传感器网络可以被描述为多个agent的强化学习问题。在某种意义上来说，学习网络路由的最优控制可以被视为和其他agent迭代并行的学习一个情节的任务。假设有多个节点的无线传感器网络随机部署在一个特定的区域具有以下特点：（1）所有传感器有能量限制；（2）任何传感器和接收器之间需要通过一跳或者多跳通信；（3）传感器的发射功率保持稳定；（4）传感器可以获得自身的信息和相邻节点的信息。

3.2 模型设计

强化学习算法需要对状态、动作和奖赏函数进行建模。接下来介绍算法各元素的建模过程。

在无线传感器网络中，状态是指某个节点ni的自身信息及其所有邻接节点的信息。一个无线传感器网络由多个节点所构成，其网络状态 是所有节点状态的集合。在t时刻，无线传感器网络处于状态S，则传感器节点ni选择动作 ，表示其选择节点nj作为信息接收点，传输路径为节点ni直接连接到节点nj的信道。由于强化学习方法采用Q值评估状态-动作，所以此时选择最高的Q值所对应的动作。

本文提出的Q-E2LBR算法在能量消耗最小化的同时均衡网络节点的负载均衡。因此在设计奖赏函数时，需要考虑在路径REt的剩余能量，从源节点到目标节点的跳数H以及在节点ni和节点nj之间传输所耗费的能量 。一个节点获得一个立即奖赏并转发一些数据包之后，对于剩余能量的值、能量消耗和必要的Q值进行编码，使得在其数据包到达目标节点后得到一个额外的目标奖励。

3.3 算法描述

在学习阶段，Sink节点在特定的时间内传播启动数据包并在其中封装了能量信息和跳计数，初始化Q值为0；然后，每个节点从相邻的节点得到学习信息，包括了相邻节点的Q值、无线传感网络中的跳数、节点能量消耗情况；接着，以满足Boltzmann分布的概率选择动作；随后，将跳数信息、奖赏信息和剩余能量信息存入模型中并在模型中进行动作值函数的迭代更新；Sink节点周期性地向邻居节点发送学习消息使得每个节点可以转发接收到的学习消息并且更新模型；最后，Sink节点周期性地向邻居节点发送学习消息，各邻居节点不断地向下一个节点发送学习消息的同时各节点不断更新内部模型，通过不断的迭代，评估值就逐步接近收敛。具体如算法1所示。

算法1 基于Q学习的能量负载均衡的路由算法（Q-learning based energy-efficient load-balancing routing，Q-E2LBR）

输入：能量信息E

输出：路由路径R

1： 初始化：Q←0，路由R←null，跳数hop←0，RE←0

2： for all 节点

3： for节点 i 的所有相邻节点

4： 节点i 从相邻节点j获得的Q值

5： 计算得到节点i到下一Sink节点的跳数hop（i）

6： 计算从节点i的开始的总跳数H

7： 计算跳数关于节点i能量的消耗

8： 计算奖赏函数

9： 采取动作a，观察a和s

10：

11：

12： for节点 i 的所有相邻节点

13： 计算节点i选择节点j的作为下一个发送节点的概率

14： end for

15： 选择pi，j最大的节点j作为下一个发送节点

16： 更新能量E←E - Eh

17： if 节点j加入后不会有环

18： 将节点j加入到路由R中

19： end if

20： end for

21： return R

本文的算法在传统算法的基础上综合考虑了跳数、节点能量消耗等情况，由于传统的考虑能量的算法仍需要计算能量值，因此，本文的算法并没有过多的增加计算量，计算复杂度没有明显增加。

4 仿真实验与结果

本文使用NS2网络[15]评估算法。模拟环境是一个长宽都为100米的矩形区域，且存在100个传感器节点被随机部署在这个区域中。传感器的最大通信距离是15米，每个节点最初的能量均服从均匀分布区间[6000，10000]。平均实验结果从100次模拟的不同拓扑结构中获得。

在无线传感器网络中，GT算法是一种效果比较好的经典算法[16]，因此本文实验从3个方面将Q-E2LBR算法和GT算法进行比较：节点的生存数，剩余能量分布和节点和传输成功率。

图1显示了在5分钟内Q-E2LBR算法和GT算法的存活下来的节点。Q-E2LBR算法存活的节点数量明显多于GT算法并且随时间的推移差距越来越大。图1的结果说明在节点生存数方面，Q-E2LBR算法优于GT算法。从图1还可以看出，Q-E2LBR算法在给定的300秒时间内的节点存活量高于GT算法，因此可以分析得出，Q-E2LBR算法所需额外的计算能量在各节点所能提供的计算能量的范围之内。

图2给出了5分钟内Q-E2LBR算法和GT算法运行了一段时间后的结果。Q-E2LBR算法的能量传播比GT算法在整个网络过程中要更加均匀，这表明了在Q-E2LBR算法中路径选择更加合适。Q-E2LBR算法从节点的剩余能量的改变中选择了路由路径。尽管GT算法也考虑了能量的均匀性，但其能量流失速度高于Q-E2LBR算法。由于无线传感器网络中，节点的计算量越大，其存活时间越短，图2的结果说明在剩余能量分布方面，Q-E2LBR算法好于GT算法。从图2还可以看出，Q-E2LBR算法在给定的300秒时间内的节点剩余能量高于GT算法，因此可以分析得出，Q-E2LBR算法優化了网络所节省的节点所需的计算能量，大于其所需要增加的计算量所需的能量。

图3展示了Q-E2LBR算法和GT算法成功传输率情况。在最初30秒内，Q-E2LBR算法传播的成功率低于GT算法。主要原因在于Q-E2LBR算法使用了强化学习的“试错”机制，在最初的阶段，Q-E2LBR算法会有意识的尝试“试错式”的学习并在很短的时间内算法学习到足够的经验之后出现性能的一次较大提高。Q-E2LBR算法有5次传输质量的提高，前3次质量提高出现在100秒内，并且提高幅度较大，后2次的质量提高耗时较长，并且提高幅度不大，这说明Q-E2LBR算法在传输质量这一指标上能很快的向最优值收敛后慢慢逼近。同时，从图3中也可以看出，在给定的300秒时间内，Q-E2LBR算法传输的量和GT算法相当，因此可以看出，Q-E2LBR算法并没有过多的增加计算量。整体而言，Q-E2LBR算法优于GT算法。

4 结 论

无线传感器网络中传感器节点的能耗问题不统一导致节点在关键路径中的Sink节点和其他节点过早死亡而导致了网络的生命周期缩短。本文提出了一种高效节能、负载平衡的路由算法Q-E2LBR，通过Q学习计算行动状态值函数，并通过Boltzmann分布计算行动的概率。经过充分考虑剩余能量、能量消耗和跳数等因素后，Q-E2LBR算法能够平衡能量消耗并延长网络生命周期。模拟实验表明，Q-E2LBR算法可以在均匀地分布网络流量，改善网络生命周期的同时保证有较高的传输成功率。

参考文献

[1] 程红举， 黄行波， XIONG Naixue. 不可靠通信环境下无线传感器网络最小能耗广播算法[J]. 软件学报， 2014（5）：1101-1112.

[2] 韩凯州， 马福昌. 无线传感器网络中多Sink节点位置部署研究[J]. 传感器与微系统， 2014， 33（3）：37-39.

[3] Jiang H， Sun Y， Sun R， et al. Fuzzy-Logic-Based Energy Optimized Routing for Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks， 2013， 9（2）：264-273.

[4] Ileri O， Mau S C， Mandayam N B. Pricing for enabling forwarding in self-configuring ad hoc networks[J]. IEEE Journal on Selected Areas in Communications， 2005， 23（1）：151-162.

[5] 李响， 孙华志. 基于能量感知的无线传感器网络路由算法[J]. 计算机科学， 2016， 43（6）：291-294.

[6] 贾杰， 张桂园， 陈剑，等. 无线传感器网络中基于潜在博弈的分布式节点定位[J]. 电子学报， 2014， 42（9）：1724-1730.

[7] 董国勇， 彭力， 吴凡，等. 一种采用蚁群优化的WSN能量均衡非均匀分簇路由算法[J]. 小型微型计算机系统， 2015， 36（7）：1565-1568.

[8] Chandane M M， Bhirud S G， Bonde S V. Energy Optimization in Wireless Sensor Network[M]// Mobile Communication and Power Engineering. Springer Berlin Heidelberg， 2013：321-331.

[9] 朱斐， 许志鹏， 刘全，等. 基于可中断Option的在线分层强化学习方法[J]. 通信学报， 2016， 37（6）：65-74.

[10] Auer B P， Cesabianchi N， Sutton P F， et al. Reinforcement learning， an introduction[J]. Trabajos Y Comunicaciones， 2010：114-135.

[11] Lo B F， Akyildiz I F. Reinforcement learning for cooperative sensing gain in cognitive radio ad hoc networks[J]. Wireless Networks， 2012， 19（6）：1237-1250.

[12] Russell B， Littman M L， Trappe W. Integrating machine learning in ad hoc， routing： A wireless adaptive routing protocol[J]. International Journal of Communication Systems， 2011， 24（7）：950-966.

[13] Oddi G， Pietrabissa A， Liberati F. Energy balancing in multi-hop Wireless Sensor Networks： an approach based on reinforcement learning[C]// Nasa/esa Conference on Adaptive Hardware and Systems. 2014：262-269.

[14] 孫彦清， 彭舰， 刘唐，等. 基于动态分区的无线传感器网络非均匀成簇路由协议[J]. 通信学报， 2014（1）：198-206.

[15] 张小庆， 李春林， 张恒喜. 无线传感器网络的NS2扩展与仿真机制研究[J]. 计算机科学， 2011， 38（8）：117-120.

[16] Kulkarni R V， Forster A， Venayagamoorthy G K. Computational Intelligence in Wireless Sensor Networks： A Survey[J]. IEEE Communications Surveys & Tutorials， 2011， 13（1）：68-96.