基于节点剩余能量和最大角度的无线传感器网络路由算法*

曹海英，元 元，刘志强

(1.内蒙古工业大学 信息工程学院，内蒙古 呼和浩特010051;2.河套学院 理学系，内蒙古 巴彦淖尔015001)

0 引 言

无线传感器网络(wireless sensor networks，WSNs)可以感知，采集与处理监测对象的信息，并将其传递给信息获取方，因此，在环境监测、灾害污染监测、智能家居等领域都具有很高的应用价值［1］。网络路由主要完成信息从源节点传送到目标节点的任务，是实现网络高效通信的基础，因此，路由优化成为一个具有挑战性的问题［2］。为了解决传感器路由优化难题，国内外学者对其进行了深入的研究，提出了许多的路由算法［3］。早期传感器网路由算法一般将网络划分为均匀的簇，采用随机分簇和周期性轮换策略，簇头与基站采用单跳通信，距离基站越远的簇头消耗的能量越大，易造成网络生存时间缩短［4］。文献［5］提出了非均匀分簇的思想，簇间采用多跳方式达到减少节点能耗的目的;文献［6］提出基于蚁群算法的无线传感器网络路由机制，选择找代价最小的多跳路由;文献［7］提出基于据概率分层的无线传感器路由算法，距离基站越近，族内节点数越多;反之，相对较少，减少簇内节点通信的能量开销;文献［8］提出了基于拓扑优化控制的无线传感器网络路由算法，通过加权概率方式选择簇头，达到节点间的能量平衡。在无线传感器网络路由过程中，经常会出现因节点能量不足而死亡现象，为此，要求一个好的路由协议必须具备良好的可靠性和容错性［9］。文献［10］提出了基于路由修复机制的路由算法，提高了数据传输的可靠性。

本文提出一种基于节点剩余能量和最大角度相融合的无线传感器网络路由算法，结合初始路由路径的信息，通过设计的代价函数对出现故障的初始路由路径进行局部自适应修复，仿真结果表明:本文路由算法延长了整个网络的存活时间。

1 无线传感器网络能耗模型

在无线传感器网络路由过程中，除了发送和接收数据包消耗的能量之外，其它能量消耗相对较小，因此，路由算法的节点能耗只考虑节点传送(ETX)数据包和接收(ERX)数据包所消耗的能量［11］。因此当两个距离为d 的节点接收和发送l bit 数据时，ETX和ERX计算公式分别如下

其中，d0为距离阈值;Eelec为每接收、发送单位bit 所消耗的能量，εfx，εmp分别为功率放大所消耗的能量。

传感器节点i 在所有状态下的能量消耗为

2 无线传感器路由算法设计

2.1 节点与汇聚节点的最大角度计算

在无线传感器路由过程中，路由上的中间节点S 在选择下一跳节点时，传统方法忽略相邻传感器节点之间的角度关系，选择的传感器节点不一定最优，因此，本文考虑相邻节点之间的关系，在汇聚节点(Sink)一侧选择角度最大的传感器节点，具体如图1 所示。

图1 最大角度计算的示意图Fig 1 Diagram of the maximum angle calculation

从图1 可知，无线传感器网络节点的角度计算方式具体如下

式中 i 为下一跳候选节点的序号;n 为通信范围内的相邻节点的个数;θ1表示夹角大小。

2.2 角度和节点剩余能量联合设计

无线传感器网络中，传感器节点能量十分有限，如何提高能量的利用率，尽量保持剩余能量最大化，是无线传感器网络路由算法设计的关键［12］。因此，本文路由算法把节点剩余能量作为路由选择一个关键指标，若路由的某个传感器节点的剩余能量Eresidual小于预先设置的能量阈值Ethreshold，那么就需要替换该节点，重新初始无线传感器的路由

式中 Einitial和E 分别为节点初始和消耗的能量。

在无线传感器路由重新初始过程中，下一跳传感器节点的路由选择准则具体如下

式中 i 为候选节点的序列号。

在无线传感器路由开始阶段，选择剩余能量最大的节点作为下一跳节点，如果有多个剩余能量相同的节点，那么就选择与汇聚角度最大的传感器节点作为下一跳节点。

2.3 无线传感器路由算法的工作步骤

1)在无线传感器网络的初始化阶段，源传感器节点向自己通信半径范围内的全部邻居节点发布相关信息，并根据式(4)和式(5)计算节点与汇聚节点的角度，然后根据计算结果选择下一跳路由节点。

2)从当前传感器节点出发，然后根据式(4)和式(5)再次计算计算节点与汇聚节点的角度，并从候选传感器节点集中选择下一跳节点，不断重复该操作，直到发布的相关信息到达汇聚节点。

3)根据已经建立的路由路径，汇聚节点将确认信息发送到源节点，这样就建立了无线传感器网络的初始路由路径。

4)当源节点有数据包需要传输时，那么就可以通过已经建立好的初始路由路径将数据包传送至汇聚节点，并通过确认机制提高数据包传输的可靠性。

2.4 无线传感器路由的修复

随着无线传感器网络工作时间的延长，节点能量慢慢被消耗，初始路由路径上的一些传感器节点会因为能量耗尽而失效，影响信息传输的可靠性［13］。因此，本文采用路由修改算法对路由进行重新初始化，提高数据传输的可靠性，具体步骤如下:

1)当某个传感器节点的剩余能量小于预先设定的能量时，那么就从该传感器节点的上一跳节点出发，利用公式(7)计算节点选择的代价函数，并根据计算结果从邻居节点集中选择出最优的传感器节点对失效传感器节点进行替换，其它节点不做处理，完成初始无线传感器路由路径的第一次修复。

2)随着通信时间的不断增加，无线传感器路由过程中，继续会出现一些能量低于预先设置能量阈值的传感器节点，采用步骤(1)的方式对路由进行修改，直到初始无线传感器网络路由路径所有低于能量阈值的传感器节点均被替换掉。

3)路由修复完成。

无线传感器路由修复过程具体如如图2 所示。

3 仿真实验

3.1 仿真场景参数

图2 无线传感器网络路由的修复过程Fig 2 Repairing process of WSNs routing

为了测试本文无线传感器路由算法的整体性能、有效性和实用性，在PIV 4 核2.80GHz CPU，4GRAM，Windows 7的操作系统上，采用Matlab 2012 仿真工具实现仿真实验。为了使仿真实验的结果更具说服力，选择文献［14，15］的无线传感器路由算法进行对比实验，从初始路由的节点跳数、节点的平均能耗、网络生存时间等方面对它们性能进行综合分析。不考虑无线通信链路的信号冲突和噪声等因素，仿真参数如表1 所示。

表1 仿真场景参数Tab 1 Parameters of simulation scene

3.2 结果与分析

3.2.1 初始路由路径选择的比较

源节点和汇聚节点采用随机方式部署，在给定的条件下，采用本文算法、文献［14，15］的无线传感器路由算法对初始路由路径进行选择，建立相应的初始路由，结果如图3所示，其中，□表示文献［14］路由算法所建立的路径;◇表示文献［15］路由算法建立的路径;○表示本文算法所建立的路径，由图3 可知，不同路由算法建立的路由路径截然不同，本文初始路径的跳数相对较少，可以加快数据传输速度，具有一定的优势。

图3 不同算法建立的初始路由路径Fig 3 Initial routing paths established by different algorithms

在传感器节点数目为25～200 的情况，所有无线传感器网络路由算法的路径跳数变化结果如图4 所示。从图4 可知，随着传感器节点数目逐渐增加，各路由算法的跳数也发生相应的变化，但跳数并不一定增加，本文路由算法建立的路由跳数小于对比算法建立的路由路径跳数，获得更加理想的数据路由。

图4 不同算法路由跳数的对比Fig 4 Comparison of routing hops of different algorithms

3.2.2 节点的平均能耗

不同无线传感器路由算法的节点平均能量消耗变化趋势如图5 所示。从图5 可知，随着传感器节点数量的增加，网络节点的平均能耗发生相就的波动，文献［14，15］的节点平均能耗变化幅度比较大，极不稳定，对整个无传感器网络的生命时间产生不利影响。而本文路由算法的节点平均能耗变化比较平稳，网络节点平均能远远小于对比算法的平均节点能耗，这主要是由于本文算法对数据传输路径进行了修复，当一些剩余能量低于阈值的传感器节点进行替换，并重新初始化路由，保证了网络通信的可靠性和稳定性。

图5 网络节点平均能耗的比较Fig 5 Comparison of average energy consumption of network nodes

3.2.3 无线传感器网络生存时间的比较

无线传感器网络的生存时间定义为网络中第一个传感器节点的死亡时间，用轮数来表示，不同路由算法的无线传感器网络的生存时间变化情况如图6 所示。从图6 可以看出:相对于对比路由算法，本文路由算法有效延长了无线传感器网络的生存时间，较好地解决了当前无线传感器网络路由算法存在的不足，使得网络的能耗更加均衡，提高了数据传输的可靠性，具有更高的实用价值。

4 结束语

针对当前无线传感器网络路由算法存在的缺陷，本文提出了一种综合考虑节点剩余能量和最大角度的无线传感器网络路由优化算法。首先根据能量、角度等准则建立无线传感器网络的初始路由路径，然后对网络中的失效节点进行替换，修复相应的路由路径，最后采用仿真实验测试算法的有效性和优越性，仿真结果表明:本文可以更加均衡传感器节点的能量消耗，延长了网络的生存时间，显著改善了网络的性能，更加适应适合规模较大的无线传感器网络。

图6 不同算法的网络生存时间对比Fig 6 Comparison of network survival time of different algorithms

［1］ Giuseppe A，Marco C，Mario D F.Energy conservation in wireless sensor networks:A survey［J］.Ad Hoc Networks，2009，7(3):537－568.

［2］ Baumgartner K，Ferrari S.A geometric transversal approach to analyzing trunk coverage in sensor network［J］.IEEE Transactions on Computers，2008，57(8):1113－1128.

［3］ Liang H F，Qian J S，Sun Y L，et al.Energy optimal routing for long chaintype wireless sensor networks in under ground mines［J］.Mining Science and Technology(China)，2011(17):17－21.

［4］ Younis O，Fahmy S.A hybrid，energy－efficient distributed clustering approach for Ad－Hoc sensor networks［J］.IEEE Transaction on Mobile Computing，2011，3(4):366－379.

［5］ Li Q，Zhu Q X，Wang M W.Design of a distributed energy－efficient clustering algorithm for heterogeneous wireless sensor networks［J］.Computer Communications，2006，29(12):2230－2237.

［6］ Li Q，Zhang B H，Cui L G，et al.Immunizations on small worlds of tree－based wireless sensor networks［J］.Chinese Phys B，2012，21(5):1－9.

［7］ 江禹生，李 萍，马 超.一种能量高效的无线传感器网络拓扑控制算法［J］.传感器与微系统，2014，33(2):146－149.

［8］ Hoon O，Han T D.A demand－based slot assignment algorithm for energy－aware reliable data transmission in wireless sensor networks［J］.Wireless Networks，2012，18(5):523－534.

［9］ Lindsey S，Raghavendra C，Krishna M.Data gathering algorithms in sensor networks using energy metrics［J］.IEEE Transactions on Parallel and Distributed Systems，2011，13(9):924－935.

［10］朱全政，杨 乐.能量角度联合自适应路由修复新算法［J］.计算机应用研究，2014，31(6):1779－1783.

［11］Lu X J，Ding Y S，Hao K R.Immune colonel selection algorithm for target coverage of wireless sensor networks［J］.Int’l J Modeling，Identification and Control，2011，12(1):119－124.

［12］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application－specific protocol architecture for wireless micro－sensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660－670.

［13］Helio M S，Claudio M，Paula L，et al.Intrusion detection system for wireless sensor networks using danger theory immune－inspired techniques［J］.International Journal of Systems Science，2012，23(10):1－28.

［14］Nam C S，Han Y S，Shin D R.Multi－hop routing based optimization of the number of cluster heads in wireless sensor networks［J］.Sensors，2011，11(3):2875－2884.

［15］Zytoune O，Fakhri Y，Aboutajdine D.A fairly balanced clustering algorithm for routing in wireless sensor networks［J］.Sensor Review，2010，30(3):242－249.