摘 要： 提出了一种针对新型无线传感网络协义WirelessHART的低功耗分布式路由算法——DHEIRP（基于多跳的分布式能量迭代路由算法）。采用分布式的路由决策，加快了WirelessHART的网络组建和恢复速度。DHEIRP提出了一种新的能量迭代算法，选取最小跳数、接收信号强度、节点电池能量作为参数，能够最小化网络的传输消耗并平衡各节点的能量损耗。将DHEIRP同GBR以及HBRRP等已有算法进行了比较，证明DHEIRP在平衡节点能量和延长网络寿命方面有较大的优势。

　　关键词： 无线传感器网络； WirelessHART； 分布式路由算法； GBR

　　中图分类号： TN92?34 文献标识码： A 文章编号： 1004?373X（2013）13?0060?05

　　Distributed low?power dissipation routing algorithm based on WirelessHART

　　WANG Yi?neng， ZHANG Sheng， LIN Xiao?kang

　　（Department of Electronic Engineering， Tsinghua University， Beijing 100084， China）

　　Abstract： An distributed low?power dissipation routing algorithm for the new wireless sensor network protocol WirelessHART called DHEIRP（distributed hop?based energy iteration routing protocol） is proposed in this paper. As a distributed routing protocol， DHEIRP can accelerate the network construction and recovery rate of WirelessHART. In DHEIRP， an energy iteration algorithm is proposed. Choosing the minimum hop count， RSS（received signal strength） and battery energy level as parameters， this protocol can minimize energy consumption of network transmission and balance energy loss among nodes. The numerical simulations have showed that DHEIRP excels GBR and HBRRP in terms of balancing load of the nodes and extending network lifetime.

　　Keywords： wireless sensor network； WirelessHART； distributed routing algorithm； GBR

　　0 引 言

　　无线传感器网络的路由协议设计是近年来的研究热点。WSN（无线传感器网络）的路由同其他网络有许多区别[1]：由于无线传感器网络的节点是由电池供电的，能耗是无线传感器网络路由设计中的重点；由于无线传感器网络经常用于工业控制领域，路由算法需要有较好的鲁棒性；无线传感器网络主要监控领域，数据流向主要是汇聚式[2]的，即从周围的Source节点向中心的Sink节点；最后，在某些应用领域中网络的拓扑结构不是静态的，会不断的有新节点的加入和旧节点的死亡，因此路由协议需要具有一定的自适应能力。

　　WirelessHART[3]是近年来提出的一种基于已有的HART工业通信协议提出的针对工业控制和设备监控的无线网络协议。其主要的技术特点是TDMA和跳频技术，WirelessHART的鲁棒性和低功耗也远优于已有的其他无线传感器网络协议[4]。路由方面，WirelessHART没有给出路由算法，而是设定了两种路由机制。一种是图路由，另一种是源路由。这两种路由机制都是集中式管理的，路由的分析和计算是由位于Sink节点的网络管理器来完成的。问题在于，这种集中式管理在网络的拓扑结构变化时不够灵活。新节点的加入和老节点的死亡都需要通过多跳的数据传输将信息发送给网络管理器，网络管理器再将路由改动下发给其周围的相关节点，这个过程浪费时间和能量；不仅如此，集中式路由计算中，由某个节点的变动还可能影响相对较多的传输链路的路由分配。这些缺点使得WirelssHART在许多应用领域有很大的局限性。应对这种问题，本文提出了一种分布式的路由改进方案，并在功耗方面进行了进一步的优化。

　　1 相关工作

　　近年来，涌现了许多针对无线传感器网络的路由协议。Directed Diffusion[5]是最有代表性的data?centric路由协议之一，也可能是最有影响力和最常被引用的路由协议。Directed Diffusion会用一系列属性值把节点的数据进行命名。当需要某些数据时，发出一个“兴趣”信息，这个信息中含有对所需的命名数据的描述。找到信息中的描述所对应的数据后，就将这个数据沿查找路线传送回。

　　在Directed Diffusion的基础上，Curt Schurgers和Mani B. Srivastava 提出了另一个经典协议GBR（Gradient based routing）。GBR是一种基于梯度的路由算法，在GBR中，“兴趣”信息在发送过程中记录了它所进行的跳数，以此建立了一个梯度场。梯度场中每个节点的梯度值为这个节点到Sink节点所需要的最小跳数。在数据传输时，将数据包沿着梯度减小的方向进行路由选择就可以把数据传送到所需的Sink节点。通过这种机制，GBR能够有效的减少传输次数，从而节省网络资源并延长网络寿命。 　　在文献[6]中，Shao?Shan Chiang和Chih?Hung改进了GBR，加入了电池能量作为路由选择的参考。通过比较邻居节点的最小跳数（或者说梯度值），他们把所有邻居节点分成三类：父辈节点、兄弟节点和子辈节点。对于某个节点来说，其父辈节点为邻居节点中那些梯度值比它小的节点；子辈节点为邻居节点中梯度值比它大的节点；梯度值和它相当的节点作为其兄弟节点。具体的路由机制如下：当一个节点自身产生了数据或者作为中继节点接受从其他节点接收了数据包以后，它会优先将数据包发送给电池能量最高的父辈节点。如果发生意外，找不到正常工作的父辈节点，那么将发送给具有最高电池能量最高的兄弟节点。这种算法继承了GBR的基于跳数的机制并在此基础上进行了改进，能够平衡节点间的能量消耗。

　　Oliver Powell在文献[7]中提出在无线传感器网络中存在所谓的“瓶颈”节点。这些“瓶颈”节点通常消耗电池能量的速度很快，比其他节点更早的因能量耗尽而死亡。而这些“瓶颈”通常是距离Sink节点最近的那些节点，它们的死亡会破坏网络的拓扑，导致网络过早的中断。为了解决这个问题，文中引用了一种混合机制。在一般情况下，中继节点的选择同文献[6]中的相同。但当被选中的中继节点的能量低于某个值时，发送数据的节点不会采用多跳的传输模式，而是通过长距离的传输，将数据直接发送给Sink节点。这种混合机制能够从一定程度上节省“瓶颈”节点的能量消耗，进而延长整个网络的寿命。然而，这种从Soure节点直接到Sink节点的长距离传输会也消耗大量的能量。

　　文献[8]提出了一种鲁棒性的基于多跳的路由协议——HBRRP（Hop?based Robust Routing Protocol）。这种算法以最小跳数作为基础，并选取电池能量、LOI（链路质量）和传输成功率作为参数设计路由选择算法。这其中，LOI是由RSS（接受信号强度）等其他信息计算得来的；传输成功率是统计某条链路上，过去一定次数的传输中成功的比率。HBRRP采用代价方程来对备选链路进行评估，方程对三个参数设置不同的权重，最后选择计算结果最好的链路作为路由。

　　综上所述，在无线传感器网络方面有很多的协议和其他研究成果，但目前没有满足WirelessHART的需求的分布式方案，而且“瓶颈”节点的问题一直没有得到很好的解决。本文希望能够解决这些问题。

　　2 DHEIRP的机制

　　之前的协议通常引用电池能量作为参数来解决“瓶颈”节点的问题以及进行节点间的能耗平衡。但仅仅考虑邻居节点的电池能量是不充分的，因为一个中继节点的选择会影响之后的链路的选择。为此，DHEIRP设计了一种能量迭代算法，这种算法能够从整体上对备选的多条链路上的节点能量进行综合评估。DHEIRP可以分为三个过程：网络初始化阶段、数据发送阶段、梯度信息更新阶段。

　　2.1 网络初始化阶段

　　DHEIRP是基于多跳传输[9]的，其实现需要一个梯度场信息的支持。这里定义每个节点的梯度值为这个节点到Sink节点所要经历的最小跳数。

　　在网络初始化之前，所有节点都将其梯度值设置为“NULL”。网络管理器作为Sink节点，会向其邻居节点广播出一个“initial”的信息，这个信息中含有一个为0的HC值。接收到这个“initial”信息的邻居节点将其梯度值设置为1，并广播一个HC值为1的“initial”信息。当其他节点接收到“initial”信息时，如果这个节点的梯度值为“NULL”或者节点的梯度值减去1仍大于“initial”信息的HC值，则它需要将其梯度值设置为“initial”信息的HC值加1，然后向周围广播一个HC值同其梯度值相等的“initial”信息。反之，如果该节点的梯度值减去1等于或者小于接收到的“initial”信息的HC值，节点就不需要改变其梯度信息，只向邻居节点广播一个HC值为其梯度值的“initial”信息。这个过程可以用下面的伪代码来描述：

　　For a sensor node receiving an “inintial” message ：

　　//对于任何一个接收到“initial”信息的节点

　　If local-gradient == NULL

　　{

　　local-gradient=initial-message HC+1；

　　initial-message HC=local-gradient；

　　}

　　Else if local-gradient>initial-message HC+1；

　　{

　　local-gradient=initial-message HC+1；

　　initial-message HC=local-gradient；

　　}

　　Else

　　End

　　flooding out initial-message； //向邻居节点广播“initial”信息

　　通过这个阶段，网络中所有节点的初始梯度值被确定了。

　　2.2 数据发送阶段

　　在这个阶段，各个节点会把自己产生的数据包通过多跳传输上传给Sink节点。作为分布式的路由协议，在DHEIRP中，每个节点只需要将自己产生或者接收到的数据包有选择性的发送给自己的一个邻居节点，并确保这次发送会使数据包更接近Sink节点。

　　对于某个节点，其所有的邻居节点可以被分成三类：邻居节点中梯度值比其小的作为父辈节点；邻居节点中梯度值同其相等的作为兄弟节点；邻居节点中梯度值比其大的作为子节点。为了保证最小跳数原则并避免loop传输，发送数据时优先选择所有的父辈节点作为候选中继节点，如果在通信范围内没有正常工作的父辈节点，则选取所有的兄弟节点作为候选中继节点。建立下面的方程来对所有的候选节点逐个进行质量评估。对于某候选节点[x]： 　　[Routequality=α？Efun（x）+β？RSS] （1）

　　式中：[Efun（x）]是一个能量迭代函数；RSS（Received Signal Strength）是需要发送数据的节点同节点[x]间的信号强度；[α]和 [β]是两个参数，来确定[Efun（x）]和RSS在式（1）中的权重。

　　能量迭代函数[Efun（x）]能够综合评估候选节点自身能量和候选节点的中继节点的电池能量，其定义如下：

　　[Efun（x）=（1-k）？Einitial?energy+k?Efun（y）， 当节点x的梯度值大于1时Efun（x）=Einitial?energy， 当节点x的梯度值等于1时] （2）

　　式中：[E]代表节点[x]的当前电池能量；initial?energy表示电池未使用之前的初始能量；[k]是一个0.5～1之间的小数；节点[y]是[x]发送数据时的中继节点。

　　显然，[Efun（x）]是一个迭代计算的结果，取值范围是从0～1。对于梯度为1的节点来说，[Efun（x）]的值为电池剩余能量的百分比。而对于梯度值为2的节点来说，[Efun（x）]为两个电量百分比的和。由于[k]是一个0.5～1之间的数，因此式中路由梯度值更小的节点能量的影响更大。这种设定是合理的，因为梯度更小的节点距离Sink节点更近，电池电量消耗的更快更早死亡。通过这种迭代计算，一条路由上的多个中继节点的整体能耗可以用一个数值来表示。路由质量公式的另一个度量参考是RSS。RSS表示候选的中继节点和发送数据节点间的信号强度。RSS的值越高，说明这条路径上的信道干扰越小。选择这种干扰小的信道不仅能够更好的保证传输的可靠性。更重要的是，在功率可调的传感器网络中，数据发送节点可以根据RSS来调整发射功率，从而节省电池能量。

　　有了之前的计算结果，选择Routequality值最高的候选节点作为中继节点。多次测试的结果显示，当[α？β]时，网络会有较长的寿命。实际操作中，并不给 [α]和[β]具体的数值，而是采用下面的方法来比较Routequality的大小：

　　[Efun（x1）-Efun（x2）ΔEinitial?energy] （3）

　　式中：[ΔE]是根据具体情况而设定的一个阈值。当两个备选节点[x1]和[x1]在比较它们的Routequality 大小时，如果[Efun（x1）]和[Efun（x2）]不能满足式（3）中的条件，则判断具有较大Efun值的节点的Routequality更大；反之，若满足式（3）中的条件，则判断具有较大RSS值的节点的Routequality更大。

　　2.3 梯度信息更新阶段

　　节点的梯度信息是由网络的拓扑结构来决定的。因此，随着网络的运行，任何拓扑结构的变化都可能影响节点的梯度值分布。这其中，新节点的加入和老节点的死亡是影响网络拓扑结构改变的两个主要原因。这里不单独把节点的移动考虑成第三种情况，因为某个节点的移动可以被看成两个情况的组合：一个老节点的死亡和另一个新节点的加入。当某个节点离开它的原有位置时，系统认定这个节点失去联系。然后当这个节点移动到一个新的位置并保持相对静止以后，系统将其作为一个新生节点加入网络中。这个过程如图1所示。当节点不停地移动时，不对其进行任何数据传输。

　　图1 移动节点的梯度更新

　　节点可能因为能量耗尽或者其他原因与网络失去联系而死亡。在DHEIRP的设计中，给定一个电池剩余能量的百分比（比如5%），如果电池剩余能量低于这个值，这个节点就会进入“休眠”模式，并向周围节点广播一个“dead”信息。其他节点接收到这个信息以后就会把这个节点从邻居表中删除。如果碰巧一个节点的所有父辈节点都死亡了（这时所有活跃的邻居节点的梯度值都比它自身大），则需要重新选取剩余的活跃邻居节点中梯度值最低的作为新的父辈节点，并调节自身的梯度值为父辈节点的梯度值加上1。

　　当一个新的节点加入网络时，首先进入申请模式，寻找周围活跃的邻居节点。通过申请模式这个阶段，新节点建立了一个邻居表，这个邻居表中包含了所有邻居节点的梯度值、电池剩余能量和RSS。通过邻居表，正在加入的新节点找到具有最小值的邻居节点作为父辈节点，并设置自身的梯度值为父辈节点的梯度值加1。然后，这个新节点可以进入正常工作模式，进而采用2.2中的机制来选择中继节点上传数据。某些新加入节点的邻居可能也需要调整自己的梯度值，因为网络拓扑结构可能已经发生了变化。

　　从前面的内容可以了解，集中式的路由协议在更新路由信息时需要网络管理器的参与。需要所有节点将自身相关信息上传到网络管理器，然后管理器在将计算好的路由选择结果发送给各个分散的节点，这个过程在网络信息的更新中反应较慢。在本文提出的分布式路由协议中，每个节点能够根据周围网络拓扑的变化，自主而独立的更新自己的路由信息。在分布式机制下，新节点不需要将它的相关邻居表和其他数据通过多跳传输发送给网络过管理器就可以加入系统，这大大加快了新节点加入网络的速度。这种机制在网络结构相对复杂，某些节点离网络管理器较远时意义重大。

　　3 仿真结果及分析

　　在Matlab环境下对提出的方案进行了测试，比较DHEIRP同GBR和HBRRP两种协议在能量消耗方面的优劣。

　　仿真假设网络由在一个正方形范围内的大量随机分布的节点组成，具体的模型设置如下：正方形区域的变长为500～700单位长度；节点间的最远通信距离为100个单位长度；网络中节点的数量为[N]；每个节点的电池初始能量为[E]个单位；发送一个数据包需要2个单位的能量，接收一个数据包需要3个单位的能量。

　　在仿真中，假定网络的Sink节点位于正方形网络的中心。每个Source传感器节点平均每分钟产生一个数据包，并通过多跳的方式将数据包上传给Sink节点。本文进行了多次的仿真测试，改变网络中节点的数目和梯度值的分布，观察不同测试结果的变化趋势。由于鲁棒性并不是本文的研究对象，仿真中并不考虑丢包的情况。仿真设定网络中的节点在两种情况下被认定为死亡：节点的电池能量低于5个单位；某节点成为孤立奇点，即在通信距离内找不到活跃的邻居节点。 　　这里使用两种指标来衡量和比较各种算法的能量效率。第一个指标是网络中死亡的节点数目随时间的变化。这个曲线可以描述网络拓扑结构变化的趋势。另一个指标是网络中第一个节点的死亡时间FDN（First Dead Node）。由于第一个死亡的节点是“瓶颈”节点，它的死亡对整个网络的影响很大，因此FDN是一个很重要的衡量指标。

　　当电池初始能量为3 000，节点数目[N]为400，正方形区域边长为500时的节点死亡数量随时间变化的情况如图2所示。此时的网络中，节点最多需要经过6次多跳来将数据发送到Sink节点。由图2可以看出，相比其GBR的节点死亡速度远大于其他两种曲线，这是因为其在多跳的路由选择中不考虑节点电池能量，致使那些“瓶颈”节点过早死亡造成的。而相比HBRRP，DHEIRP算法在同一时间内的节点死亡数量更少，说明综合考虑多个节点的电池能量可以平衡能耗并延长网络的寿命。

　　图2 区域边长为500时的死亡曲线

　　图3比较了三种算法的FND情况。选用正方形区域的边长为500，测试当节点数目分别为150，200，300和400时的FND。图中的每个FND的值是100次计算结果的平均值。从图3中可以看出，DHEIRP的FDN曲线一直处于GBR和HBRRP的上方。这说明DHEIRP能通过平衡节点能量消耗来延迟“瓶颈”节点的死亡。不仅如此，从图3中可以观察到，对于GBR和HBRRP两种算法，随着节点的数目增多，FDN的值会不断降低。这是因为节点的数目越多，距离Sink节点最近的节点的负担越重（需要给更多节点作为中继节点）。这些节点很容易成为“瓶颈”节点而过早的死亡。而对于DHEIRP来说，由于在路由选择中的迭代算法能够避免对某一节点的过度消耗，因此FND值不会随着节点数目增长而明显下降。

　　图2和图3的仿真基本是在相对简单的网络中进行的，节点的数据最多需要6跳就可以将数据上传到Sink节点。图4和图5是针对更加复杂的网络的测试结果。图4是当区域变长为800，节点数目为700时死亡节点数量随时间的变化情况，这里数据最多需要11跳才能到达Sink节点。对应的节点初始电量为15 000个单位能量。图4中的曲线证明DHEIRP在大型网络中的性能比GBR和HBRRP要更加出色。

　　图3 区域边长为500时FND的均值

　　图4 区域边长为800时的死亡曲线

　　图5比较了三种协议的FND在更大更复杂的网络中的变化。图中设定网络的区域边长为700，节点的数量分别为400，500，600，700和800，数据最多需要经过11跳来到达Sink节点。

　　图5 区域边长为800时的FND均值

　　从图5中可以看出，DHEIRP的FND值明显大于其他两个协议。在图3中，相比其他两种算法，DHEIRP的FND值分别平均增大了44%（HBRRP）和322%（GBR）；而在图5中，这两个数值为94%和377%，对比可以看出，在较为复杂和大量节点的网络中，DHEIRP的有着更大的优势。因为当网络越大或者越复杂时，“瓶颈”节点的传输负担会越重，如果没有合适的机制，“瓶颈”节点就会很快的死亡，而DHEIRP的能量迭代算法能够准确的判断潜在的“瓶颈”节点的剩余能量，在路由选择时避开这些节点，延长其网络寿命。

　　4 结 语

　　本文分析了以往无线传感器网络的路由协议的发展。针对WirelessHART集中式设计的缺陷，提出了一种分布式的解决方案DHEIRP。并针对“瓶颈”节点问题，设计了一种能量迭代公式。通过仿真，比较DHEIRP与GBR，HBRRP的性能，证明其能够降低能耗并延长网络的寿命。在以后的研究中会继续改进这种算法，使其在无线传感器网络领域有更广泛的适用性。

　　参考文献

　　[1] AL?KARAKI J N， CAMAL A E. Routing techniques in wireless sensor network： a survey [J]. IEEE Wireless Communications， 2004， 11（6）： 6?28.

　　[2] 许毅。无线传感器网络原理及方法[M].北京：清华大学出版社，2012.

　　[3] IEC. IEC 62591?2010 industrial communication networks?wireless communication network and communication profile?WirelessHART [S]. London： IEC， 2010.

　　[4] 缪学勤。WirelessHART无线传感器网络及其应用[J].自动化博览，2012（3）：34?38.

　　[5] INTANAGONWIWAT C， GOVINDAN R， ESTRIN D. Directed diffusion： a scalable and robust communication paradigm for sensor networks[C]// Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. New York： ACM， 2000： 56?67.

　　[6] CHIANG Shao?shan， HUANG Chih?hung. A minimum hop routing protocol for home security systems using wireless sensor networks [J]. IEEE Transactions on Consumer Electronics， 2007， 53（4）： 1483?1489.

　　[7] POWELL O， JARRY A， LEONE P， et al. Gradient based routing in wireless sensor networks： a mixed strategy [EB/OL]. [[2008?02?07]]. http：//www. wenku.baidu.com/view/3619dbb565ce050876321366.html.

　　[8] ZANG Zhe， QI Jian?dong， CAO Yong?jie. A robust routing protocol in wireless sensor network [C]// 2010 IET International Conference on Wireless Sensor Network. [S.l.]： IET， 2010： 276?279.

　　[9] 文芳，齐建东。无线传感器网络最小跳数路由算法的研究[J].计算机工程与应用，2010，46（22）：88?91.

　　[10] SCHURGERS C， SRIVASTAVA M B. Energy efficient routing in wireless sensor networks[C]// 2001 IEEE Military Communications Conference. [S.l.]： IEEE， 2001， 1： 357?361.