基于Q学习的无线传感网络自愈算法

卞 辉，范新南，巫 鹏，顾丽萍，李威龙，郑庆元

（1.河海大学 计算机与信息学院，江苏 常州 213022；2.江苏鑫源烟草薄片有限公司 江苏 南京 223002）

基于Q学习的无线传感网络自愈算法

卞 辉1，范新南1，巫 鹏1，顾丽萍1，李威龙1，郑庆元2

（1.河海大学 计算机与信息学院，江苏 常州 213022；2.江苏鑫源烟草薄片有限公司 江苏 南京 223002）

无线传感网络存在关键区域节点能量消耗过快，节点能量供应有限以及通信链路拥塞等问题，容易造成节点故障和路由破坏。为减小上述问题对网络传输造成的影响，提出一种基于Q学习的无线传感网络自愈算法，通过引入Q学习的反馈机制，动态感知网络的状态信息，当故障发生时，自适应地选择恢复路径，保证数据实时顺利传输。仿真结果表明，该算法降低了错误选择故障或拥塞路径的概率，在故障感知、故障恢复和延长网络寿命等方面，表现出了良好的性能。

无线传感网络；Q学习；自愈算法；故障恢复

无线传感器网络（Wireless Sensor Network，WSN）是由具有感知、处理和无线通信能力的传感器节点通过自组织方式形成的网络[1]，传感器节点通过采集环境变量并将它们传送给汇聚节点（也称目标节点或Sink节点）。相对于有线网络，传统的单汇聚节点无线传感网络存在诸多问题。比如传感器节点的电池能量供应与通信传输距离有限；单汇聚节点附近和关键路径上节点能量消耗过快；单汇聚节点失效将导致整个网络通信中断无法进行重路由等。因此延长无线传感网络的寿命和对故障链路进行及时恢复成为至关重要的问题，而自愈作为一种智能化的故障恢复技术，其研究也将成为一种趋势。

自愈通常是指网络在发生故障的情况下，不需要人工干预，能很快地、自发地恢复受影响的传输路径[2-3]。目前，无线传感网络的自愈技术研究还处于起步阶段，主要集中在前期的故障检测，对后续故障恢复研究的文献并不多见。故障检测旨在感知并且定位故障传感器节点，其关注的重点主要是能耗和精度，主要技术有接收信号强度指示、基于到达时间、基于到达时间差和基于到达角度等方法[4-5]。故障恢复则是将故障路径上的数据传输切换到另一条可承载这些数据传输的健康路径上，减少由于故障对数据传输所造成的影响，其涉及的关键技术主要是重路由[6-7]。重路由对于新路径的建立依赖于故障信息、网络路由的策略、预定义设置以及网络当前的状态信息，因此其收敛时间得不到保证，导致故障恢复时间不能满足无线传感网络实时有效传输的要求。

为克服自愈机制中重路由收敛时间慢和对故障信息检测要求高的特点，本文提出了一种基于Q学习的无线传感网络自愈算法。该算法通过应用Q学习的反馈机制，将无线传感网络节点和路径的状态信息融入Q学习的反馈奖赏函数中，使得该自愈算法可以动态感知可能出现的网络故障并自适应地选择恢复路径。最后进行的仿真实验结果表明该算法能有效延长无线传感网络的使用寿命，并在故障感知和故障恢复方面具有一定的优势。

1 基于Q学习的WSN自愈算法

1.1 Q学习

Q学习是一种与模型无关的强化学习算法，通过不断“试错”（trial and error）与环境进行交互来改善策略[8]。 Agent在其环境中执行某个动作时，环境都会给出一个反馈（奖赏或惩罚），Agent为从环境反馈中得到最大奖赏或最小惩罚而不断改变动作，从而最终得到适合环境的最优行为。

文中提出的算法将Q学习引入无线传感网络的故障恢复决策中，将每个传感器节点抽象成具有一定感知能力的Agent，自愈算法的路由选择过程可以看成是一个马尔科夫过程 MDP[9]，其迭代时采用状态－动作对 Q（st，at）。 令状态集S={s1，s2，…，sn，Sink1，Sink2，Sink3}表示无线传感网络中所有传感器节点的集合， A（i）={a1，a2，…，an}表示是第 i个 Agent可用的动作集（0＜i＜n，n 为最大节点数）。Agent在状态 st执行动作 at使得状态变为 st+1，收到奖赏函数 r（i）。Q（st，at）的大小决定了通过行为at到达下一状态st+1的倾向，节点Agent根据以下公式进行Q值更新[8]：

式（1）中，α∈（0，1）是学习速率，γ∈（0，1） 为折扣系数。为了得到节点的最优Q值，Agent需要不断尝试每个状态动作对，本文应用Boltzmann动作选择策略[10]，动作a被选取的概率函数为：

由式（2）可以看出，行为的选择取决于该状态－行为对的Q（s，a）函数和参数 τ，参数 τ是一个正的参数，称为退火温度参数，用来控制搜索率。大的退火参数可以使各个行为有着近似相等的被选择概率，小的退火温度参数使得较大的Q值函数有较大的被选择概率。

1.2 改进的Q学习奖惩函数

传统的Q学习奖赏函数在定义时只考虑单一因素的约束，例如跳数最少或者路径最短，这样带来的问题是不能动态感知节点的能量变化。为了更加均衡的消耗能量，我们选择下一跳中通信能量与剩余能量之比（P能耗比）最小的邻节点进行路由；同时，本文加入网络质量的Qos参数，选择其中的时延（delay）和丢包率（P丢包率）作为自愈技术恢复连接实时性和有效性的参数。将这些约束参数融入Q学习的奖赏函数中。当节点i通过动作选择策略到达下一节点时，定义收到的立即反馈函数为：

式（3）中 w1、w2和w3为权系数，其中丢包率与节点的剩余能量呈指数关系。WSN中，有些数据业务传输实时性要求高，有些数据业务传输要求能耗少，调整权系数的大小可以响应不同业务数据传输的需求，奖赏函数越大，说明向该节点路由的“趋势”就越强。

1.3 算法流程

Step1路径建立过程：在传输数据之前，源节点不断向邻居节点广播学习消息，各个邻节点不断地向下一个邻节点发送学习消息直到抵达汇聚节点。学习消息中记录节点的奖赏值、Q评估值、传输延迟以及能量信息，考虑到这些网络状态的特征信息可以人为定义，那么可以把其定义为一个数值，这样广播学习消息传送需要的能量可以忽略不计。

Substep1汇聚节点将收到的网络状态信息反馈给源节点，源节点根据Q学习公式（1）记录并更新各个节点的Q值，这样从源节点到汇聚节点间各节点的Q值就逐步迭代出来，建立Q表。

Substep2源节点根据Q表定制路径传输路径的优先级顺序表格，选择节点最大Q值所对应的动作建立最优传输路径。

Step2业务传输过程：源节点按照最优路径进行数据传输，数据在传输过程中记录所经过节点的能耗和时延信息。数据到达汇聚节点后，将记录的路径节点信息进行整合并反馈给源节点。源节点根据公式（1）和公式（3）更新Q表，从而对下一次传输的路径优先级顺序进行更新。

Step4故障恢复过程：在传输时选择的最优路径出现故障节点或者发生路径拥塞时，源节点依据路径优先级顺序选择次优的路径作为数据传输的恢复连接；如果优先级次优的传输路径也无法进行有效传输，那么按优先级顺序选择下一个通信链路进行恢复连接，以此类推。

2 仿真与实验分析

2.1 网络模型

本文将提出的基于Q学习的无线传感网络自愈算法应用于多汇聚节点的无线传感网络[11]，网络模型如图1所示。

图1 WSN网络拓扑示意图Fig.1 Network topology of WSN

图1中，为方便计算将每个传感器节点的剩余能量标示在节点的旁边，用Ri表示；同时假设链路上的值为两节点间传输所需要消耗的能量，比如源节点和V2节点之间传输的能量消耗为2。

2.2 建立动态路由表

文中用Visual Studio 2010对该算法进行仿真。通过基于Q学习的无线传感网络自愈算法，在第一个周期我们得到15条路径，依据传感器节点Q值大小建立路径传输的优先级表格，仿真参数与结果如表1所示。

表1 路径传输参数以及优先级顺序Tab.1 Parameters of path transmission and Priority order

查询优先级表格可知，源节点在第一周期依据优先级表格选择“1-4-6-7-Sink3”作为最优路径传输；假设数据传输过程中，V6节点发送故障或者发生拥塞，那么源节点将自适应地选择Q值次优的链路进行恢复连接，即以1-4-3-Sink3作为恢复连接。

2.3 实验分析

需要特别说明的是，相对于传统以故障检测为前提的故障恢复模式[12]，本文提出的算法根据Q学习的反馈机制，在感知故障的同时进行重路由传输，并不需要对故障进行精确的定位，因此缺少同类的自愈机制进行比较。在仿真中，本文将采用静态路由中的最小能量消耗路由算法作为自愈机制中重路由的比较算法进行性能分析。

2.3.1 网络使用寿命

我们增加对最小能量消耗路由算法的性能分析，根据网络拓扑图2，在传输过程中路径能量的传输消耗为：

Cost（源->Sink1）=cost（源->V5）+cost（V5-Sink1）=5+2=7；

Cost（源->Sink2）=cost（源->v4）+cost（V4->V6）+cost（V6->V9）+cost（V9->Sink2）=1+1+3+1=6；

Cost（源->Sink3）=cost（源->V2）+cost（V2->Sink3）=2+3=5。

根据该算法，我们选择“源-2-Sink3”作为该算法传输数据的最优路由。由于节点V2的剩余能量限制，数据传输的次数为。先考虑第一个周期T=1，基于Q学习的自愈算法传输最优路径为“源-4-6-7-Sink3”，若一直沿该路径发送数据，数据传输的次数为10/1=10。相比最小能量消耗路由算法，传输的次数增加了，延长了节点的使用寿命。该实例只是分析一个周期的路由结果，随着Agent继续进行数据传输，节点的剩余能量将发生变化，本文算法反馈给下一周期传感器节点计算得到的Q值也将自适应变化。为了更直观地比较两种算法对无线传感网络寿命的影响，我们观察从无线传感网络开始工作直至第一个无线传感器节点失效所经过的传输次数。图2所示显示两种算法在不同汇聚节点数目时的传输轮次。

图2 两种算法网络使用寿命Fig.2 The network operation life of two algorithms

由图2可以看出，当汇聚节点唯一时，两种算法的使用寿命相同，这是因为单汇聚节点无线传感网络的最优路径是唯一的。随着汇聚节点的增加，每个传感器节点到达汇聚节点的平均距离逐渐减少，则传输所消耗的能量也相应减少，从而延长了网络的使用寿命。本文算法在源节点选择路径时，根据上一周期传输结束时网络的状态信息更新节点的Q值，一定程度上避免了使用剩余能量较少的传感器节点进行数据传输，因此网络的能量消耗更加均衡。而最小能量消耗路由算法只根据静态路由表进行路由，缺少对路径剩余能量和传输消耗的感知能力，导致各路径的能量消耗不均衡，网络资源利用率偏低。

2.3.2 故障恢复

文中提出的自愈算法，在每次数据传输之后，汇聚节点与源节点之间通过反馈机制来感知网络当前的状态，因此，本文算法具备故障感知的能力。令:

φ值越小说明自愈算法感知故障的能力越强，反之则越弱。静态路由算法没有引入反馈机制，缺少对网络实时状态的感知能力。仿真结果如图3所示。其中，AF业务代表有效性要求高的数据传输，BF业务代表实时性要求高的数据传输。可以明显看出本文算法故障感知能力更强。

在传输过程中，当数据传输失败即选择了故障路径时，源节点会按照路径优先级重新选择路径进行恢复连接。如果重新选择的路径不能满足数据传输的要求或者仍然选择了故障路径，则认为传输恢复失败，反之认为数据传输恢复成功。因此，传输恢复失败率可以表示为：

图3 两种算法的故障感知性能Fig.3 Performance of two algorithms in fault-aware

仿真结果如图4所示，当单汇聚节点无线传感网络的汇聚节点失效或故障时，网络无法进行重路由，两种算法的恢复失败率是相同的；随着汇聚节点个数的增加，无线传感网络的恢复连接有更多的路径选择，因此恢复失败率迅速下降。同时，本文算法加入Q学习的反馈机制，具备感知故障的能力，降低了选择发生故障和拥塞路径的概率，使得故障恢复率显着降低。

图4 两种算法的恢复失败率Fig.4 Fault recovery rate of two algorithms

3 结 论

文中提出的基于Q学习的无线传感网络自愈算法，加入了Q学习的反馈机制，不仅优化了数据传输时的路由选择和节点能量消耗，还可以动态地感知网络状态信息的变化和可能发生故障的链路.当网络出现故障时，本文算法可以自适应地选择次优路径进行恢复传输，一定程度上缓解了传统自愈机制对故障检测技术依赖过高的问题。仿真结果表明，该算法有效地延长了网络寿命，提高了无线传感网络自愈机制的智能性与实时性，在故障感知和故障恢复方面具有一定的优势。

[1]孙利民，李建中，陈渝，等．无线传感器网络[M]．北京：清华大学出版社，2005.

[2]Salaha A，Ahmed E，Osameh M.Network protection codes:Providing self-healing in autonomic networks using network coding[J].Computer Networks，2012:99-111.

[3]Jorgr L，Gomes T．Survey of recovery schemes in MPLS networks[C]//2006 International Conference on Dependability of Computer Systems，Szklarska Poreba，Poland，2006．

[4]RaoA，RatnasamyS，PapadimitrouC．Geographicroutingwithout location information [C]//Proceedings of ACM MOBICOM 2003，2003：96-108.

[5]Doherty L，Pister K S J，Elghaoui L.Convex position estimation in wireless sensor networks[C]//INFOCOM2001．Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies，IEEE，2001，3：1655-1663.

[6]Grerin R，William D，Orda A．QoS routing mechanisms and 0SPF extensions[C]//1997 Global Telecommunications Conference，Phoenix，1997．

[7]Ke Y，Copeland G A．Scalability of routing advertisement for QoS routing in an IP network with guaranteed QoS[C]//2000 Global Telecommunications Conference，IEEE，2000:605-610．

[8]章韵，王静玉，陈志．基于Q学习的无线传感器网络自组织方法研究[J]．传感技术学报，2010，23（11）：1623-1626．

ZHANG Yun，WANG Jing-yu，CHEN Zhi.A self-organizing method based on Q-learning for wireless sensor network[J].Journal of Transduction Technology，2010，23（11）:1623-1626.

[9]陈志，王汝传，孙力娟．一种无线传感器网络的Agent系统模型[J]．电子学报，2007，35（2）：240-243．

CHEN Zhi，WANG Ru-chuan，SUN Li-juan.An agent system model for wireless sensor network[J].Chinese Journal of Electronics，2007，35（2）:240-243.

[10]Sutton R S，Barto A G．Reinforcement learning：an introduction[M].IEEE Transactions on neural networks，1998:1054．

[11]CHUANG Shun-yu，CHEN Chien，JIANG Chang-jie.Minimumdelay energy-efficient source to multisink routing in wireless sensor networks[J].Journal of Systems and Software，2012:2459-2469．

[12]刘一田，孔震，李萌.Web应用中故障检测机制的研究与改进[J].陕西电力，2012（11）：66-69.

LIU Yi-tian,KONG Zhen,LI Meng. Research and improvementoffailure detection mechanism forWeb applications[J].Shaanxi Electric Power，2012（11）：66-69.

A self-healing algorithm based on Q-learning for wireless sensor network

BIAN Hui1， FAN Xin-nan1， WU Peng1， GU Li-ping1， LI Wei-long1， ZHENG Qing-yuan2
（1.Computer and Information College， Hohai University， Changzhou 213022， China；2.Jiangsu Xinyuan Tobacco Sheet LTD， Nanjing 223002， China）

Wireless Sensor Network has some disadvantages，such as excessive energy consumption of nodes on the key path ，limited energy supply of nodes，and communication link congestion.These problems will cause the fault of nodes and damage of routing.To reduce the influence on network transmission，a self-healing algorithm based on Q-learning is proposed for wireless sensor network.In this algorithm，a feed back mechanism of Q-learning is introduced，to perceive the status of network dynamically and select a recovery routing automatically，which can ensure the data transmission is successful.The experimental results show that the proposed algorithm can reduce the probability of selecting the failure and congestion path.The proposed algorithm has some good performances in fault-aware， fault recovery， and extending network life.

wireless sensor network；Q-learning；self-healing algorithm；fault recovery

TP393

A

1674－6236（2013）04-0044-04

2012-10-22稿件编号201210142

卞 辉（1986—），男，江苏苏州人，硕士。研究方向：物联网信息安全。