基于Q学习的多Sink节点无线传感网路由机制研究*

周淑俐，章 韵，陈 志，2，3，* ，扈罗全，岳文静

(1.南京邮电大学计算机学院，南京 210003; 2.南京大学计算机软件新技术国家重点实验室，南京 210093; 3.江苏省无线传感网高技术研究重点实验室，南京 210003; 4.宽带无线通信与传感网技术教育部重点实验室，南京 210003; 5.苏州出入境检验检疫局 江苏苏州 ，215104)

无线传感网节点一般能量供应、计算和通信能力有限，在部署节点和设计各种协议时要考虑有效利用各种资源［1］。在无线传感网中，传感器节点采集环境变量并将它们传送给Sink节点(网关节点或汇聚节点)，Sink节点通过无线方式接收各传感器节点的数据并以有线或无线的方式将数据传送给最终用户。无线传感网在许多领域都得到了很好的应用，但在传统的单Sink传感网中存在许多问题，比如靠近Sink节点或者关键路径上的节点能量消耗过快，会引起节点的能量消耗不均衡;单Sink节点的失效会引起整个无线传感网的通信中断，当传感网的规模不断增加，节点数目不断扩充，靠近Sink节点的传感节点比其他节点消耗的能量更快，因为他们需要传递大量的消息，因此延长整个传感网的寿命成了一个至关重要的问题。针对单Sink传感网路由中存在的缺点，本文研究了多Sink传感网的路由协议。多Sink节点传感网特别适应于大规模的传感网，多Sink节点会减少传感节点到Sink节点的平均距离，减少相应的跳数，能更加均衡地消耗能量。本文在研究了多Sink传感网路由协议的基础上提出了一种具有一定的智能学习和适应能力的路由机制，应用增强学习［2－6］来达到寻求在多Sink传感网中节点使用寿命最长、能量消耗均衡的最优路径的目的。

本文介绍Q学习算法的路由选择机制，通过实例分析说明Q学习路由机制对于延长节点寿命的作用。Q算法工作时只需利用各个节点的能量状态信息，不增加网络通信量，均衡了节点的能量消耗，延长了网络的使用寿命。

1 相关工作

多Sink无线传感网路由协议的研究目前还处于起步阶段，相比单Sink路由协议具有更大的优势:能够避免单Sink节点失效时造成的整个传感网的通信中断、减轻Sink节点附近能量消耗不均衡的压力、可在不同Sink节点间采用不同的路由算法通过不同路径传送数据、能够根据不同用户的需求控制好网络中的数据流(图像、声音、视频数据流)等。多Sink节点传感网中，路由可以有不同的选择，数据能够沿不同路径传输。Pietro Ciciriello［7］提出周期性的消耗适应路由协议PAMR，设想每个数据源节点到相应的Sink节点具有相互独立的树状结构，从而建立源节点到相应Sink节点的路径，该协议借鉴了多商品流网络设计问题来解决传感器网络设计高效性、分散性问题，但是该协议适合于数据量较少的应用场合，而且算法过于复杂，主要解决了多源到多Sink的传感网的分散性问题，当网络规模较大，而且数据量比较多的情况不太适用;Meng Min提出PBR路由协议［8］，基于能量级别传送数据，能量级别定义为节点在当前所剩能量，能够向邻节点传输数据的次数，路径能量级别定义为一个节点到目标Sink节点整个路径的最小能耗。该协议解决了能量均衡消耗的问题，延长了网络的寿命，但是它适合于网络拓扑比较简单且Sink节点固定的情况;Chen Yue-quan 提出了 MRMS［9］多Sink节点路由协议，针对传输路径选择、高能效的动态分簇维持以及路径切换问题，提出了一种新的基于邻节点间距离到相应Sink的跳数以及节点剩余能量信息的路径开销度量算法，该协议主要应用于大规模分簇传感网中，在传感网的规模不大且不分层的情况算法有点复杂，不太实用。由此可见以前的很多多Sink节点传感网路由协议都是从某一个角度来研究多Sink路由涉及的问题，考虑得更多的是节点的剩余能量，没有很好地解决Sink节点间协调问题，以及能量的均衡消耗，或者是算法过于复杂造成能量开销较大。它们考虑因素不全面或者计算复杂度过高，没有考虑节点失效或者移动时的路径选择，而Q学习方法适合于任何规模的传感器网络，算法不太复杂，考虑的因素较全，如节点的剩余能量、跳数、距离等，有效的均衡了节点的能量消耗，延长了网络的使用寿命。

2 Q学习算法

在无线传感网中，节点在寻求最优路径时，每个Agent都要有初始的Q值。通过信息交互基于增强学习机制寻找下一个Agent，在Q值更新过程中是基于以下方法的:

这里，γ为延迟回报与立即回报的相对比例因子(0≤γ≤1)，α(0≤α≤1)为学习因子。不同无线传感网络可能具有不同的资源，调控α将使Q评估值更新方法收敛。当α=1时，为确定性回报情形下的规则。此时上式变为:

第i个Agent在时间t采取的动作是确定将数据发送给哪个邻居Agent，所得的回报就来自该邻居Agent，一般不同的Agent具有不同的回报值，Agent在发送信息时是选择具有最大回报值的邻居Agent发送。从数据源节点到Sink节点能通过不断的迭代产生具有最大Q评估值的路径，该路径即是最优路径。

3 基于Q学习的多Sink网路由机制

多Sink无线传感网路由考虑的是如何把采集到的数据根据能量有效的原则传送到最佳的Sink节点。多Sink路由协议研究还处于起步阶段，目前研究的路由协议大多存在考虑因素不全面，如未考虑关键路径上节点能量消耗过快，路由算法过于复杂、节点移动或失效等，基于Q学习的路由机制能比较有效地解决能量消耗不均衡的问题。下面利用Q学习方法机制来实现能量感知路由协议，从而实现路由选择［12－13］。

假定学习因子γ=1，为了方便讨论只考虑确定性的情况，即α=1的情形。Agent综合考虑路径上节点的剩余能量和节点间能量消耗、跳数，每次选择较优的Agent来传送数据，并在每次的选择后根据获得的回报值选择下一个较优的Agent。这样从源节点到每个Sink节点都能通过不断的迭代找到一条最佳的路径，然后通过比较不同Sink节点的Q值，Q值高的Sink节点即为应选择的Sink节点。学习过程如下:

(1)汇聚节点Sinkk(在这里1≤k≤3)以一定的周期向邻居Agent广播学习评估消息，启动路径建立过程。学习评估消息中包含Agent的回报值、Q评估值及能量信息，回报值的初始值设为0。

(2)Agenti收到邻居Agentj发送的学习消息时，相对发送该消息的Agentj，只有当自己距离源节点更近而距Sinkk更远的情况下，才需进行学习训练，否则放弃学习。其中相关定义如下:

①定义一个D集合来存放本周期内已学习过的Agent以免出现路由环路现象;

②在WSN无线通信模型中，能量的消耗主要是进行数据传输。发送lbit数据包到距离为d的接收方的能量消耗为Ei，j。

在WSNs中，跳数对于节点的能量消耗也是有很大的影响的。跳数关于节点能量消耗的公式:Eh=ehop(i)/H，其中 hop(i)表示下一跳 Agentj到 Sinkk的跳数，Agenti到Sinkk的总跳数为H。

在本文中，Ei，j假定已知，故只要考虑跳数对节点能量消耗的影响即可，即只计算Eh=ehop(i)/H即可。

③Sinkk周期性地不断向邻居节点发送学习消息，各个邻节点不断地向下一个节点发送学习消息，这样从各个Sink节点到源节点的Q评估值就逐步的迭代出来。源节点通过比较到不同路径上的Q值，选择Q值最大的作为通信的下一个节点把数据发送出去，从而最终把源节点的数据传送到Sink节点，最后通过Sink节点把数据发送到计算机处理系统。该Q学习机制中，节点间通信的每一步选择都综合考虑了节点的通信能力、跳数、剩余能量，能从中选择最能均衡能量、节省能量、延长节点寿命的路径选择路由，因而具有一定的实用价值和现实意义。

4 实例分析

假设网络拓扑如图1所示，用有向图G(V，E)来表示，V代表传感网中的各个Agent节点，V=(源节点，V1，V2，…，V9，Sink1，Sink2，Sink3)，E 代表着相邻Agent间可通信的一条链路e。每个节点的剩余能量标注在每个节点的旁边，Rj表示Agent j的剩余能量。为方便计算，我们假设链路e上的值表示两节点间数据传送所消耗的能量值(跳数因素对节点能量消耗不包含在内，另外考虑)。比如源节点和V2之间的数据传输的能量消耗是2，另外还要考虑跳数对节点能量的影响。为了进行性能比较，增加了多Sink传感网中的最小能量消耗路由算法的能量消耗分析。

图1 节点拓扑能量示意图

基于最小能量消耗路由算法:

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。

根据该算法，我们选择源－V2－Sink3作为传送数据的路由。数据传送的次数为20/3=6。

下面具体分析多Sink传感网中基于Q学习算法的路由选择机制。

Agent不必知道网络的拓扑结构，只须获得每个节点的Q值和到达下个节点的回报值，就能通过不断地迭代找到最优路径。通过Sink节点周期性的向源节点发送学习训练消息更新节点的Q值表，更新规则为式(2)，Sink节点的剩余能量始终保持在40，Q的初始值设为40。

先考虑第一个周期T=1。表1所示为T=1时源节点到各个Sink节点路径上的Q值。

表1 建立路由的Q表项＜T=1＞

π*=maxaQ(s，a)。根据Q学习算法应该选择Q值最大的作为目标传送的Sink节点。故应该选择路径为:源－V4－V6－V7－Sink3。若一直沿该路径发送数据，传送的次数为10/1=10。与最小能量消耗路由算法相比，数据传送的次数增多了，网络的寿命得到了延长。该实例只是分析了一个周期的路由选择。随着Agent继续进行数据传送，各Agent节点的能量会发生变化，这个时候源节点又会根据路由算法寻找新的路由。对于增强学习算法而言，当第二周期开始寻找路径时，节点的剩余能量为节点原来的能量减去节点间通信消耗的能量。确定了各节点的能量后，就可以根据Q算法重新寻找最优路径。如此循环往复，节点每次都能找到一条达到Sink节点的最优路径。

第二周期的Q评估值的计算是在第一周期基础上进行的，这时节点的剩余能量为第一周期节点剩余能量减去第一周期发送信息消耗的能量，即源、V4、V6、V7的节点能量有变化，其余节点能量不变。

表2 建立路由的Q表项＜T=2＞

表2表明第二周期内源－V4－V6－V7－Sink3的Q评估值仍然是最大的，故第二周期选择的路径没有变。

为了比较两个算法对传感网网络使用寿命的影响，需要定义一种和数据收集相关的度量标准。实例采用协作寿命来进行度量。协作寿命定义为从传感器网络开始工作时起到第一个传感器节点失效时所经过的传送数据的轮次。图2所示是两种算法在不同Sink节点数目时协作寿命。横轴表示Sink节点数目，纵轴表示传感器的协作寿命。

图2 两种算法生命周期比较

从图2可以看出，在单Sink节点时采用两种算法的传感器网络寿命一样，因为单Sink节点所形成的路由路径是唯一确定的。随着Sink节点数目的增加传感网的寿命有显著的提高，因为随着Sink节点数量的增加，每个传感器节点到达Sink节点的平均距离就会减少，那么传送数据所消耗的能量就会减少，从而网络寿命要增加。另外，由于采用Q学习方法的路由机制使数据始终沿着能量消耗代价最小的路径进行数据传输，在一定程度上避免了使用剩余能量少的节点转发数据，而最小能量消耗路由路径始终选择的是能量消耗最少的节点发送数据，根本没有考虑到节点的剩余能量。

Q学习算法具有衡量各节点的能量的作用，这是因为该算法具有周期性和即时性，且不以路径上的节点能量消耗少作为唯一择路标准，而是综合考虑了Agent节点能量消耗、节点剩余能量值、跳数、距离等，因而相对而言考虑较为全面，能发掘出更合适的路径出来。

5 结束语

本文研究基于Q学习的多Sink无线传感网路由机制。该机制综合网络节点的剩余能量和节点间消耗能量值以及跳数、距离，通过不断迭代找到到达各Sink节点的最优路径。Sink节点周期性的向源节点发出学习训练消息，各节点根据自己当时所处的状态不断的学习训练，使Q值表在不断的更新，不断地选择最优的路径，因而每次传送数据都能很好的平衡能量。该机制还能防止由于节点故障导致的路径失效。通过实例分析，我们看出该机制相比于最小能量消耗路由算法大大延长了网络的生命周期，并且随着Sink节点数目的增加，Q学习方法的优势性越来越明显。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京;清华大学出版社，2005.1－57.

［2］姚怡，覃华，苏一丹.基于Q-learning的自适应容错路由算法的研究［J］.计算机工程与应用，2006(10):123－125.

［3］薛丽华，殷苌茗.多智能体协作学习方法的研究［D］:［硕士学位论文］.长沙:长沙理工大学，2008.

［4］褚建华，李大字.Q-learning强化学习算法改进及其应用研究［D］:［硕士学位论文］.北京:北京化工大学，2009.

［5］Anna Egorova-Forster，Amy L Murphy.Exploiting Reinforcement Learning for Multiple Sink Routing in WSN［C］//2007 IEEE International Conference on Mobile Ad hoc and Sensor Systems(MASS 2007)，8 October－11 October 2007:1－3.

［6］Ping Wang，Ting Wang.Adaptive Routing for Sensor Networks using Reinforcement Learning［C］//2006 The Sixth IEEE International Conference on Computer and Information Technology(CIT 2006)，September 2006:219－225.

［7］Pietro Ciciriello，Luca Mottola，Gian Pietro Picco.Efficient Routing from Multiple Sources to Multiple Sinks in Wireless Sensor Networks［J］.Computer Science，2007，4373(10):34－50.

［8］Min Meng，Xiaoling Wu，Hui Xu，et al.Energy Efficient Routing in Multiple Sink Sensor Networks［C］//2007 the Fifth International Conferenceon computerScience and Applications，Berlin:Springer.26－29 August 2007:561－566.

［9］Chen Yue-quan，Chane，Han Song.Energy Efficient Multipath Routing in Large Scale Sensor Networks with Multiple Sink Nodes［C］//Cao J，W Neidl，M Xu，des.Proc of the 6th International Workshop on Advanced Parallel Processing Techniques，Berlin:Springer.2005:390－399.

［10］Tom M Mitchell著，曾华军，张银奎，等译.机器学习［M］.北京:机械工业出版社，2003.263－280.

［11］陈志，王汝传，孙力娟.一种无线传感器网络的多Agent系统模型［J］.电子学报，2007.35(2):240－243.

［12］章韵，王静玉，陈志.基于Q学习的无线传感器网络自组织方法研究［J］.传感技术学报，2010.23(11):1623－1626.

［13］汪琼，张锋.无线传感器网络中的节点协作算法研究［J］.传感技术学报，2006.19(2):481－485.