朱报开

(广东科创工程技术有限公司，广东 东莞 523808)

WSN中基于能量感知的最小跳数路由算法

朱报开

(广东科创工程技术有限公司，广东 东莞 523808)

无线传感器网络的拓扑往往由于节点死亡而发生变化。网络拓扑的重新构建加速了剩余传感器节点的死亡，缩短了网络的生存时间。针对无线传感器网络对网络生存时间的苛刻要求，提出了一种基于能量感知的最小跳数路由算法。建立路由时，该算法综合考虑了节点剩余能量和该节点潜在的转发能力。仿真结果显示，该算法在生存时间、存活节点数和吞吐量方面的性能要远优于LEACH算法和HEED算法。

无线传感器网络;能量感知;最小跳数;生存时间;存活节点;吞吐量

0 引言

对城市供水水质的监测是保障居民用水安全、建设智慧城市的一个重要手段。当前普遍的做法是在供水管网的重要位置或区域，通过密集地布置大量传感器节点组成的无线传感器网络(Wireless Sensor Networks，WSN)对水质进行测控;甚至可以通过无线传感器网络采集到的数据，发现水质变化的趋势，达到尽早地介入、进行预处理的预警目的。由于能量限制的原因，无线传感器网络的拓扑经常会由于节点死亡而重构，重构的过程又会进一步加剧生存节点的能量消耗，文献［1－9］就如何延长无线传感器网络的生存时间这一热点问题做了一些研究。针对水质监测预警，设计了一种结合了能量感知和最小跳数的路由算法，在延长无线传感器网络生存周期的同时，又能尽快地交付数据。

1 研究背景

无线传感器网络是由大量静止的或移动的传感器节点以自组和多跳方式构成的无线网络，主要功能为感知、采集和处理网络覆盖地理区域内被感知对象的信息。无线传感器网络示意如图1所示。

图1 无线传感器网络示意

图1中，普通节点根据特定的路由协议将采集到的数据上传给簇头，然后由簇头通过sink节点发送给其他网络。由于WSN中的节点基本上采用的都是自供电方式，因此，研发简洁有效的路由协议是影响整个网络生存时间和数据交付的重要因素之一。近年来，有不少学者围绕着无线传感器网络的能量感知和最小跳数路由方面展开了研究工作。

文献［10］提出了一种用于无线传感器网络中的能量平衡分簇算法，在簇信息共享、簇头选择、簇内节点和簇间通信等方面达成能量开销的平衡，以其达到延长网络生存时间的目的;文献［11］针对LEACH(Low Energy Adaptive Clustering Hierarchy)协议中随机选择簇头的缺陷提出了能量自适应的优化措施，保证了整个网络中能耗的平衡;文献［12］提出了一种概率簇头选择方法对无线传感器网络中的能耗和生存时间进行了分析和仿真;文献［13］提出了一种无线传感器网络中错误容忍分簇的算法，当分簇失败时该算法使用了检测和重新发现2个步骤从漏选的网关中重新发现传感器节点的，从而避免了系统中重新分簇的问题;文献［14］为单跳传感器网络设计了一种能效分簇机制来解决周期性采集数据时的能耗问题，该机制通过自主地选择剩余能量更多的节点作为簇头，从而达到了在簇头间平衡负载的目的;文献［15］提出的层次型能效分簇算法通过分层次的选举簇头达到降低能耗的目的，仿真结果表明随着层次数量的增多，能耗降低越多。但是，由于基于能量感知的路由算法没有考虑路径的长短，过长的路径势必影响到数据的实时性交付。所以，以上研究并不适用于实时性很强的应用，如水质监测预警等。

文献［16］提出了一种基于最小跳数的分簇路由算法，算法优化了 HEED(Hybrid Energy-Efficient，Distributed clustering)算法中簇头的选择策略，此外，算法中节点根据其邻节点的广播信息计算最小跳数，在下一跳节点的选择过程中考虑了候选节点到基站的最小跳数、节点的能量以及节点到基站的距离，并在不同情况下令3个因素所起的作用不同，进而提高路由效率。文献［17］在节点中利用邻居表记录了所有相邻节点的信息，节点依照父节点(跳数比自身小1)、兄弟节点(跳数与自身相等)、子节点(跳数比自身大1)顺序的优先级，随机挑选下一跳节点并转发数据分组。文献［18］提出在每个节点打开时，向周围节点发送join报文，周围节点接收到该报文后，将各自的跳数值返回给新加入的节点来完成梯度的建立与更新。该算法能避免通过周期性洪泛实现网络组建而造成不必要的资源消耗并解决节点实时加入网络的问题，但同时回复 join报文也增加了周围节点的能量消耗。

然而，基于最小跳数的路由算法有时会在网络中产生大量的冗余信息，同时没有考虑网络的能量消耗，从而影响到网络的生存时间。文献［19］研究了基于改进蚁群算法的无线传感器网络最小跳数路由选择方法，利用改进蚁群算法出色的全局寻优能力，对无线传感器网络中最小跳数路由选择问题进行优化，从而优化了无线传感器网络节点传播和处理数据的能力，减少了节点能量消耗。

鉴于基于能量感知和最小跳数路由存在的缺陷，本文提出了一种基于最小跳数的高效路由算法。此算法的思想是:当存在多条相同跳数的最小路径时，进行能量最优化选择，选择能效较高的路径进行数据传输。所谓的能效较高，就是在路由时选择节点能效较高地进行数据传输，这样低能效节点就可以延长其寿命，整个网络的生存时间得以延长。

2 算法设计

首先，对本文使用的几个概念进行说明:

节点剩余能量:传感器节点在任何状态下所剩下的能量，使得传感器节点能继续工作的剩余能量。

节点服务度:指的是需要经过某节点将数据转发给sink的所有节点数，即该节点可以为多少个节点提供服务。

节点能效:指的是剩余能量/节点服务度，即某节点能够为一单位服务提供的能量。单位服务所能提供的能量越高，节点能效就越高。

节点路径能效:从sink到某节点路径上最小的路径服务能效，综合了最小路径和服务能效2方面，传感器节点在传输数据过程中根据节点路径能效来选择下一跳节点。

算法的核心思想是用递归函数进行迭代运算出某节点到sink的最小路径能效，节点通过最小路径能效值寻找下一跳。整个网络通过迭代计算出某一节点到sink的最大路径能效，然后将该路径的最大路径能效值与该节点的服务能效进行比较，选出其中最小值作为路径的最小路径能效。

2．1 构建网络拓扑

① 传感器节点随机分布在某一区域，网络初始化结束后，普通节点会在网络中广播Hello分组，网络中的多个节点会收到未入网节点的 Hello分组，但只有sink或其他已入网的节点收到Hello分组后会反馈Beacon帧给该未入网的节点，使得该节点能够入网。

② Beacon帧包含节点的地址，跳数和能量信息。节点提取 Beacon的信息，通过比较节点跳数，选择跳数最小的节点。将最小跳数节点加入直连父节点邻居列表，并保存节点的位置信息和剩余能量，更新本节点到sink的最小跳数。

③节点确定自己的父节点后会发送ACK帧进行确认，表明隶属于该父节点。由于节点的父节点邻居列表中可能含有多个最小跳数的父节点，就需要发送多个 ACK帧。ACK帧包含节点的位置信息，目的节点的位置信息(父节点的信息)。当父节点收到子节点的信息后，将子节点列入子节点的邻居列表中，保存子节点的位置信息。

2．2 获取节点服务度

节点的服务度包含节点的子节点，以及子节点的所有下级节点。节点的服务度值是运用一个递归函数进行统计节点的服务度，每个节点都有自己的子节点邻居列表，通过层层计算返回每一层节点的服务度便可以计算出该节点的服务度。

2．3 计算节点能效

服务单位节点数可用的能量值，节点统计自身剩余能量和服务度后，计算出节点能效值，为计算路径能效做好准备。

2．4 计算路径能效值

节点路径能效取值是比较最小路径中所有节点的节点能效，取能效最低的那个值，称为最小路径能效。节点路径能效也是运用一个递归函数进行运算的。通过不断调用递归函数，层层递归算出每个节点的路径能效，一直推算到距离sink一跳范围内的节点(最后一跳)，最后一跳节点的路径能效值就等于最后一跳节点的能效值，这就是该递归的函数的截至条件。

2．5 路由选择

当有数据包需要转发的时候，节点会计算路径能效值，在路由选择过程中，每个节点都保存最小路径临近下一跳的信息，当每个节点有多个下一跳可供选择时，此时要比较不同路径的路径能效值，选择路径能效值最大的作为路由。依此类推，一直重复到将数据交付给sink为止。

3 算法仿真和性能分析

为了很好地评估算法的性能，选择了基于能量感知的LEACH算法和基于最小跳数的HEED算法进行对比。

LEACH协议中，为了尽可能地平衡各个节点的能耗，簇头是周期性按轮随机选举出来的。每轮可以分为簇建立和稳定工作2个阶段。在簇建立阶段，协议按照一定比例随机地选取若干个节点作为簇头。在选定簇头后，簇头向周围节点广播自己成为簇头的消息，节点根据接收到的消息强度来决定加入哪个簇，并告知相应的簇头，从而进行通信。在稳定工作阶段，节点持续采集数据，交付给簇头，进行必要的融合处理之后，发送到 sink。持续一段时间以后，整个网络进入下一轮工作周期，重新选择簇头。

HEED协议是混合的能量有效的分布式簇头选举协议，对LEACH簇头分布不均匀问题进行了改进。HEED除了把节点剩余能量作为一个参数引入算法外，还考虑到了簇内平均可达能量，在簇重叠区域中的节点根据簇内平均可达能量选择最终加入哪个簇。HEED协议能产生分布更均匀的簇头，全网能耗更加均衡。

在节点平均剩余能量、网络存活节点数和吞吐量3个方面进行了比较:

① 节点平均剩余能量是指仿真结束时，传感器网络中所有节点剩余能量的平均值;

② 网络存活节点数是指仿真结束时，网络中存活节点数;

③ 吞吐量指的是指仿真结束时，通过sink的总数据量。

仿真是在Matlab 7．0．4的环境下进行的。在一个100 m×100 m的区域中，100个传感器节点随机分布在sink周围。节点信道延迟100 μs，单个数据分组长度16 Bytes，节点丢包率5%，设置节点初始化能量为1 000个单位量，发送一个分组消耗1个单位量，接收一个分组消耗0．5单位量，节点能量小于10单位量则视为死亡，仿真时间为300 s。3种算法节点平均剩余能量的比较如图2所示。

从图2中可以看出，仿真结束时本文提出的算法节点平均剩余能量约为570个单位量，节点平均能量降低了43%;HEED的约为460个单位量，节点平均能量降低了54%;LEACH的约为320个单位量，节点平均能量降低了68%。3种算法中，本文提出的算法性能最优，HEED次之，LEACH最差，分别改善了约11%和25%。

图2 3种算法节点平均剩余能量的对比

使用3种算法网络中存活节点数量的对比如图3所示。

图3 3种算法存活节点数量的对比

从图3可以看出，仿真结束时，使用本文提出的算法性能最优，存活节点数为28个，节点生存比例达到了28%;使用HEED和LEACH的分别是10个和7个，节点生存比例分别是10%和7%。

整个仿真期间，使用3种算法WSN中吞吐量的对比如图4所示。

图4 3种算法吞吐量的对比

从图4可以看出，仿真结束时，本文提出的算法完成了约 8．2 MB的吞吐量，HEED完成了约6．9 MB，而LEACH只完成了约5．7 MB。

进行性能对比的节点平均剩余能量的多少直接决定了存活节点数量和吞吐量的大小。通过仿真结果可以看出，在节点平均剩余能量、存活节点数量和吞吐量方面，本文提出的算法性能最好，HEED的次之，LEACH的性能最差。这是因为在LEACH协议中，由于簇头是随机选择的，因此LEACH协议不能保证簇头节点的均匀分布，这将导致部分簇头节点的能耗过大，影响网络的生存时间;另外，LEACH中要频繁地选举簇头，并且每次选举的过程中所有非簇节点都要参与;多轮LEACH协议后，每个节点的剩余电量会出现较大的差异，距离簇头或基站比较远的节点耗能比较多，能量很容易耗尽，从而死亡。HEED协议综合考虑了节点剩余能量和簇内平均可达能量，使得簇头分布更均匀，全网能耗更加均衡。但是，在选择路由方面没有考虑最小跳数，而本文提出的算法兼顾了节点剩余能量和路由选择的最小跳数，所以无论在节点的平均剩余能量、存活节点数量和吞吐量方面都具有良好的表现。

4 结束语

无线传感器网络以其能够通过分布式处理大量的采集信息和冗余节点等优势在很多领域得到了应用。但是由于传感器节点都是依靠自给供电，节点能量有限，如何延长无线传感器网络的生存周期无疑成了设计无线传感器网络的首要目标。针对当前主流的路由算法缺陷，本文提出了一种基于能量感知的最小跳数路由算法，兼顾了节点剩余能量和路由选择时的最小跳数。仿真结果证明，该算法无论在节点的平均剩余能量，还是在存活节点数量以及吞吐量方面都有良好的表现。

［1］ 孙大洋，刘衍珩，杨 东，等．无线传感器网络生存期优化体系研究［J］．计算机研究与发展，2012，49(1): 193－201．

［2］ 陈 燕，张尚尚，梁俊斌，等．无线传感网中生命最大化的泛在数据收集协议［J］．计算机应用研究，2014，31 (3):866－871．

［3］ 明 勇，王华军．WSN中考虑节点磨损的分布式自稳定网络寿命优化算法［J］．计算机应用研究，2016，33 (3):827－831．

［4］ 唐 伟，郭 伟．WSN聚合数据率约束最大生命期路由［J］．电子科技大学学报，2011，40(1):30－35．

［5］ 张 霞，周 刚，于宏毅．一种协作和中继混合的传感网寿命最大化路由算法［J］．软件学报，2013，24(12): 2 859－2 870．

［6］ 路 纲，周明天，佘 堃，等．无线传感器网络路由协议的寿命分析［J］．软件学报，2009，20(2):375－393．

［7］ ALFIERI A，BIANCO A，BRANDIMARTE P，et al．Maximizing System Lifetime in Wireless Sensor Networks［C］∥USA:in Proceeding of the fourth International Conference on Information Processing in Sensor Networks，2005: 390－402．

［8］ EMRE K M，KUBAN A I，NECATI A，et al．Wireless Sensor Network Lifetime Maximization by Optimal Sensor Deployment，Activity Scheduling，Data Routing and Sink Mobility［J］．Ad Hoc Networks，2014(17):18－36．

［9］ KUMARA A，THOMAS A．Energy Efficiency and Network Lifetime Maximization in Wireless Sensor Networks Using Improved Ant Colony Optimization［J］．Procedia Engineering，2012(38):3 797－3 805．

［10］NAZIR B，HASBULLAH H．Energy Balanced Clustering in Wireless Sensor Network［C］∥USA:in Proceeding of 2010 IEEE International Conference on Information Technology，2010(2):569－574．

［11］LIANG Ying，YU Hai-bin．Energy Adaptive Cluster-Head Selection forWirelessSensorNetworks［C］∥ USA:in Proceeding of Sixth International Conference on Parallel and Distributed Computing，Applications and Technologies，2005: 634－638．

［12］CHOI J，LEE C．Energy Consumption and Lifetime Analysis in Clustered Multi-Hop Wireless Sensor Networks Using the Probabilistic Cluster-Head Selection Method［J］．Eurasip Journalon WirelessCommunications＆ Networking，2011(1):1－13．

［13］GAURAV G，MOHAMED Y．Fault-Tolerant Clustering of Wireless Sensor Network［C］∥USA:in Proceeding of IEEE International Conference on Wireless Communications and Networking，2003:1 579－1 584．

［14］YE Mao，LI Ceng-fa，CHEN Gui-hai，et al．ECCS:An Energy Efficient Clustering Scheme in Wireless Sensor Networks［C］∥USA:in Proceeding of 24th IEEE International Conference on Performance，Computing and Communications，2005:535－540．

［15］SEEMA B，EDWARD J．An Energy Efficient Hierarchical Clustering Algorithm for Wireless Sensor Networks［C］∥USA:in Proceeding of Twenty-Second Annual Joint Conference of the IEEE Computer and Communications，2003:1 713－1 723．

［16］范书平，马宝英，高晨光，等．一种分簇WSN最小跳数路由算法研究［J］．小型微型计算机系统，2014，35 (8):1 775－1 779．

［17］CHANG S S，HUANG C H，CHANG K C．A Minimum Hop Routing Protocol for Home Security System Using WirelessSensorNetworks［J］．ConsumerElectronics，2007，53(4):1 483－1 489．

［18］段文芳，齐建东．无线传感器网络最小跳数路由算法的研究［J］．计算机工程与应用，2010，46(22):88－90．

［19］赵 晗，黄少卿．基于改进蚁群算法的无线传感器网络最小跳数路由选择方法［J］．电信科学，2016，32(3): 113－117．

朱报开 男，(1972—)，工程师。主要研究方向:计算机应用与自动化控制。

A Minimum-hop Routing Algorithm Based on Energy Awareness for Wireless Sensor Networks

ZHU Bao-kai

(Guangdong Forcon Engineering Technology Co．，Ltd，Dongguan Guangdong 523808，China)

The network topology usually varies due to the death of nodes in wireless sensor networks．And，the network lifetime is reduced because the residual nodes will die earlier due to the reconstruction of network topology．Focusing on the strict requirement of wireless sensor networks on the lifetime，a minimum-hop routing algorithm based on energy awareness is proposed．While establishing the routes，the residual energy and the transferring capacity are simultaneously taken into account．Simulation results show that the proposed algorithm can achieve an outstanding performance in terms of lifetime，the number of nodes alive and the throughput compared with LEACH and HEED．

wireless sensor networks;energy awareness;minimum hop;lifetime;node alive;throughput

TP391.4

A< class="emphasis_bold">文章编号 1

1003－3106(2017)02－0015－05

10．3969/j．issn．1003－3106．2017．02．04

朱报开．WSN中基于能量感知的最小跳数路由算法［J］．无线电工程，2017，47(2):15－19．

2016-11-08

广东省社会公益及能力建设基金资助项目(2015A010103020)。