基于节点度和距离的WSN分簇路由算法

李 辉，刘书吉



基于节点度和距离的WSN分簇路由算法

李 辉，刘书吉

(河南理工大学电气工程与自动化学院，河南 焦作 454000)

针对无线传感器网络(WSN)中节点的负载均衡问题，提出一种基于节点度和距离的WSN非均匀分簇路由算法。该算法在首轮成簇时采用了定时机制的簇头竞争方案，定时的长短取决于节点本身的节点度和距离基站的距离，且节点根据不同的竞争半径形成不同的簇。在首轮成簇结束后，簇的结构不再发生变化，而簇头的轮换则根据簇内节点的剩余能量和距离本簇质心的通信代价在簇内进行动态轮换。采用簇间多跳路由，根据节点的剩余能量、距离基站的距离、节点间通信代价和节点的转发热度来选择中继节点。仿真结果表明，该算法的网络生命周期与LEACH协议相比延长了2倍以上，与EEUC协议相比延长了13.97%，且均衡了网络的能量消耗。

无线传感器网络；非均匀分簇；节点度；距离；转发热度；动态轮换

1 概述

无线传感器网络(Wireless Sensor Networks, WSN)是继互联网之后的又一个对人类生活产生重大影响的IT技术[1]。由于传感器节点的能量受限，因此基于分层的路由协议备受关注。基于概率的低功耗自适应分簇协议(Low-energy Adaptive Clustering Hierarchy, LEACH)[2]是最早的分簇路由协议，几乎贯穿了后来发展的大多数分簇协议。该协议通过等概率随机循环地选择簇头以此来将整个网络的能量负载平均分配到每个传感器节点上，从而达到降低网络能量耗费、延长网络生命周期的目的[3]。LEACH协议成簇时簇首选择方法简单，易于实现。但是，LEACH协议的缺点也非常明显：(1)在簇头选择时没有考虑能量因素，无论节点的剩余能量多少都有可能成为簇头，从而加速了低能量节点的死亡；(2)簇头分布不均；(3)在数据传输时采用了单跳模式数据传输，当传输相同的数据时距离基站远的簇头的节点能耗较快。文献[4]的HEED算法在簇头选择时依据主参数能量和次参数簇内通信代价，其分簇速度更快，并且产生的簇头分布比较均匀、网络的拓扑结构也更加合理。但是在成簇时通信开销大。文献[5]提出的最小ID分簇算法，方法简单易行。但是在成簇时需要相互交换ID号，带来很大的能量开销，并且选择的簇头分布不太均匀。文献[6]提出的集中式分簇算法(LEACH-C)，每轮结束时将能量信息和位置信息发送给基站，由基站来选择簇头。虽然解决了簇头分布不均问题，但是每轮都要发送能量和位置信息浪费了大量的能量。文献[7]提出的基于竞争的非均匀分簇算法(EEUC)中提出一种部分节点竞争的方式来竞争簇头。但是每轮都要进行簇头的竞争，若是参与竞争的节点多时能量浪费比较严重。文献[8]提出了CEERP协议，该协议在数据转发时利用的是代价函数。主要考虑了当前节点和成为下一跳节点之间的距离和能量的加权值。文献[9]提出的WSN中基于能量代价的能量优化路由算法在选择平面路由时利用了节点间能量代价函数和前向区域来选择下一跳节点。文献[10]提出的能量均衡的无线传感器网络非均匀分簇路由协议分簇时采用了定时机制，一定程度上减少了信息交互量。而选择路由时采用了贪婪机制和代价函数相结合的方法选择下一跳。然而，在选择中继节点时仅考虑链路代价函数，父节点在选择下一跳节点时具有明显的倾向性，即在满足条件的节点中选择最好的节点来转发数据，而没有考虑到节点间的负载均衡。文献[11]提出支持负载均衡的无线传感路由协议中为了均衡网络的能量消耗，使用了“热度声明”的策略，通过设定阈值来实现。然而，采用设定阈值的策略，会造成一些有能力承担转发任务的节点，因为阈值的原因而不再承担转发任务。

针对上述算法不足，本文提出一种基于节点度和距离的无线传感器网络非均匀分簇路由算法(Unequal Clustering Routing Algorithm Based on Node Degree and Distance for WSN, UCDD)，该算法在首轮采用定时驱动机制和竞争半径相结合实现非均匀分簇。簇形成后簇的结构不变，而簇头的轮换采用簇内动态轮换。在数据传输过程中采用了多跳数据传输模式，簇头节点在选择下一跳中继节点时依据一种新的代价函数，新的代价函数不仅考虑了节点间的通信代价和节点的剩余能量，还考虑了簇头的“转发热度”。

2 相关模型的假设

2.1 网络模型的假设

在本文中，网络中有个传感器节点随机分布在一个边长为正方形区域内，并假设传感器网络具有如下性质：

(1)基站部署在正方形监测区域的外侧。传感器节点和基站部署后均不再发生位置变化，且基站唯一。

(2)所有的传感器节点都是同构的，并在网络中的地位、作用相同，具有相同的初始能量，并且都有一个且唯一一个ID号，均具备数据融合的能力。

(3)各传感器节点的能量受限，并且节点具有活动和睡眠两种状态的切换能力。

(4)链路是对称的。若已知发送方的发射功率，接收方可以根据信号的强度计算两者间距离的近似值。

(5)节点位置可以通过定位算法或GPS等方法获得。

(6)节点可根据距离的远近调节发射功率以节省能量。

2.2 网络的能量模型

2.3 数据融合模型

3 UCDD算法的基本思想

本文提出的基于节点度和距离的无线传感器网络非均匀分簇路由算法(UCDD)在首轮成簇时采用了基于定时机制的分布式竞争成簇算法，减少了在成簇时信息交互带来的能量消耗，并且在生成定时器时充分考虑了节点度和节点距离基站的距离因素。多数分簇路由协议采用的周期性成簇机制会带来一些不必要的能量消耗。因此，UCDD算法只在首轮进行成簇操作，簇一旦形成将不再发生改变，在一定程度上减少了成簇带来的能量消耗，还可以稳定簇头的个数。为了减少“热区”给网络带来的影响采用了非均匀分簇的思想，使成簇大小随着距离基站的距离的增加而增大。簇首的轮换采用簇内动态轮换，在轮换时簇头节点根据本簇的存活节点的平均能量水平来决定是否选取下一任簇头节点，并充分考虑了下一任节点的能量水平和距离本簇质心的通信代价。在稳定的数据传输阶段，簇头通过多跳的方式将本簇的数据传给基站，在建立路由时提出一种合理选择下一跳的代价函数，不仅考虑了节点间的通信代价和节点的剩余能量，还考虑了簇头的“转发热度”。在多跳传输过程中，节点通过计算满足条件的簇头的代价函数，选择代价最小的簇头作为下一跳进行数据的传输。由于在选择下一跳节点时考虑了簇头的“转发热度”，在一定程度上均衡了链路之间的能耗，延长了网络的生命周期。图1为UCDD算法的原理，图中大小圆圈代表簇和簇头，五边形是基站，带箭头的线表示簇间路由[10]。

图1 UCDD算法原理

3.1 簇的形成

UCDD算法的一种完全分布式的竞争成簇算法，最终目标是实现非均匀分簇。当节点部署结束后，节点通过广播交换信息来统计节点度信息，根据接收的基站的广播信号强度计算距离基站的距离。节点信息表见表1。

表1 节点信息表

节点的竞争规则如下：

规则在竞争过程中，节点一旦竞争胜利，将在自己的竞争半径内广播成为簇头的消息，在其竞争半径内的节点将不再参与竞争，进入休眠状态直到竞争结束。否则继续竞争。

本文的算法借鉴了EEUC算法中竞争半径的计算方法，节点的竞争半径公式如下：

本文算法在簇头竞争阶段采用定时广播代替了协商机制。传统的算法如EEUC在簇头竞争过程中节点的剩余能量大于所有的候选簇头时竞选才成功，并且要广播通知信息和接收其他候选簇头的放弃竞争的广播信息。如果节点密度较大时每个候选簇头都要接收和广播大量信息，浪费很多能量。若采用定时驱动机制在一定程度上减少算法的迭代次数和信息交互带来的能量消耗。本文定时公式如下：

其中，是均匀分布在之间的随机数，用于减小广播消息时间冲突的可能性；为设定的簇头最大竞争时间；为节点的节点度；是网络中布撒的节点个数；是节点与基站之间的距离；是网络中节点到基站的最大距离。由式(7)可知，节点度越高，距离基站的距离越小，生成的定时时间就越短，成为最终簇的概率就越大。簇的形成流程见图2。在成簇时，节点根据接收到簇首的信号强度选择信号强度最大的加入，若节点接收的簇头的信号强度相同，选择簇头节点度低的簇头加入。成簇结束后簇头节点为每个簇成员分配一个TMDA时隙，簇内节点根据分配的时隙与各自的簇头进行通信。

3.2 簇间路由的建立

UCDD算法采用了簇内单跳和簇间多跳的方式进行数据的传输。簇头节点只是在其邻居簇首集合中选择一个合适的簇头中继来转发数据到基站。和PEGASIS算法[13]不同，UCDD算法中的中继簇头只是简单的转发并不融合转发的数据。

定义3转发热度就是利用该簇头作为中继节点的所有子簇头的个数，簇头初始转发热度为0。

在建立簇间路由时，每个簇首节点以3倍[10]于自身竞争半径进行广播簇间通信信息。并且路由的发起从最远端发起，簇头节点根据距离基站的距离依次建立路由。簇头节点广播信息包括簇头的ID、簇首与基站之间的距离、簇头剩余能量，簇首节点通过接收的簇头广播信息计算相互间的距离。簇头节点根据收到的广播信息，建立邻居簇首集合。邻居簇头集合分为子节点集合和父节点集合。

3.3 簇头的轮换机制

(14)

由式(11)可知，在进行簇头轮换时利用节点的剩余能量和距离簇质心的距离来选择下一任簇头，使得越靠近质心能量越高的节点当选簇头权值就越大。当簇头靠近质心时，簇内节点在传输数据时簇内消耗的能量就越少，降低了簇内能量消耗，在一定程度上延长了网络的生命。簇头轮换流程如图3所示。

图3 簇头轮换流程

4 仿真与结果分析

4.1 仿真参数的设定

本文采用Matlb软件对提出的算法进行了验证，并在相同的条件下与LEACH协议和EEUC协议进行了对比分析。相关参数设置如表2所示。

表2 网络环境的参数设定

4.2 簇头的特性

在分层的路由协议中，成簇时的簇头个数对网络的性能将产生很大的影响。一个好的分簇路由协议，当网络的参数一定时，产生的簇头个数应该在一定的期望范围内。本文对UCDD算法和LEACH协议都进行了100次的仿真并统计了簇头的分布情况，如图4、图5所示。从图4可以看出，LEACH协议产生的簇头个数范围波动比较大，其主要的原因是LEACH协议采用了等概率选择簇头的模型，通过随机数和阈值来决定该节点是否当选为簇头节点。而UCDD协议产生的簇头个数相对集中在一定的范围之内，产生的簇头相对比较稳定。主要原因是在簇头选举的时采用了节点度和局部竞争相结合的方式，在一定程度上控制了产生的簇头数量。从整体上来看，UCDD算法产生的簇头个数相对稳定，可靠性较好。

图4 LEACH算法簇头数量分布

图5 UCDD算法簇头数量分布

在分簇的路由协议中，由于簇头的特殊位置，簇头消耗的能量占据了网络能耗的主要部分，因此本文对比了 3种协议簇首在一轮中所消耗的总能量。本文随机选取了10轮，统计了每轮中所有簇头消耗的能量，如图6所示。本文UCDD算法和EEUC算法消耗的能量较小，主要的原因是在进行数据传输时采用了多跳通信的方式，节约了能量消耗。而LEACH协议每轮簇首消耗的能量明显多于UCDD算法和EEUC算法，不仅因为LEACH协议是在进行数据传输时采用了单跳进行传输，还有LEACH协议产生的簇头个数也比较多，增加了与基站通信的次数，从而增加了能量消耗。另外，LEACH协议在进行簇头选举时没有控制簇头在网络中的分布，而且簇头的数量也不确定，因此每轮簇首消耗的能量之和有较大的波动。UCDD协议在一定程度上克服了LEACH协议的不足，降低了网络的能量消耗。

图6 簇头的每轮能耗之和

4.3 能量效率

对网络的能量效率的证明中，网络的生命周期是一个重要指标。本文首先对比了3种协议的网络生命周期。然而，网络的生命周期目前也没有统一的定论，有的以第一个节点死亡的时间作为网络的生命周期(FND)，有的以一半节点死亡的时间作为网络生命周期(HND)，还有以最后一个节点死亡作为网络生命周期的(LND)[14]。

从图7和图8可以看出，3种协议中网络存活节点个数随着仿真时间的变化逐步减少。显然，首个节点死亡的时间、半数节点死亡的时间、最后一个节点死亡的时间，UCDD协议均优于EEUC协议。只有最后一个节点死亡的时间UCDD协议略微低于LEACH协议。从第一个节点开始死亡到最后一个节点死亡的时间可以反映出网络中节点的能量均衡情况，跨度越短说明网络的能量使用越高效。UCDD协议不仅在一定程度上延长网络的生命周期，而且时间跨度也远小于LEACH协议，略小于EEUC协议。说明UCDD协议很好地均衡了网络中所有节点的能量消耗。LEACH协议在进行簇头选择时采用了等概率模型，没有考虑节点的剩余能量，并且在数据传输时采用了单跳模式，所以第一个节点死亡较早。EEUC协议虽然考虑了节点的剩余能量，但是在进行簇头选择时采用部分节点竞争机制，由于每轮都要进行簇头的选举消耗了部分能量，并且在进行数据传输时只考虑了下一跳节点的剩余能量和距离，这样会出现多个节点选择一个簇首作为中继的现象，会造成能耗均衡性降低。如果以第一个节点死亡的时间进行对比，LEACH协议出现首个节点死亡的轮数是268轮，EEUC协议出现的首个节点死亡的轮数是766轮，而UCDD协议是873轮。

本文提出的协议在生命周期方面比LEACH协议提高了2倍多，比EEUC协议提高了13.97%。

图7 节点存活个数与轮数之间的关系

图8 网络的存活时间

图9对比了网络的整体能耗变化的趋势，曲线的坡度越小代表着较慢的能耗速度和较长的网络生命周期。从图中可以看出，UCDD协议的坡度要小于EEUC协议和LEACH协议。当网络都运行到500轮时，LEACH协议消耗了161.12 J，而EEUC协议消耗了119.15 J，而UCDD算法只消耗了108.9 J，比LEACH协议提高32.4%，比EEUC提高8.6%。

图9 网络的总能耗与轮数之间的关系

5 结束语

本文在对现有路由协议研究的基础上，针对周期性成簇、周期性选举簇头和利用代价函数，建立路由时容易出现多个节点同时选择一个节点作为中继的问题，从簇头选举、簇头的动态轮换和簇间路由的建立3个方面进行了改进，UCDD算法不仅充分利用了节点的能量，而且缓解了“热区”对网络的影响。仿真实验表明，该算法能更好地均衡网络的能量消耗，有效延长网络的生命周期。下一步将以网络编码为基础对节点发送的数据进行编码，以此减少数据的发送量，降低节点的能耗。

[1] 景 博, 张 劼, 孙 勇. 智能网络传感器与无线传感器网络[M]. 北京: 国防工业出版社, 2011.

[2] Heinzelman W, Chandrakasan A, Balakrishnan H. Energy- Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc. of the 33rd Hawaii International Conference on System Sciences. Cambridge, USA: IEEE Press, 2000: 8020-8030.

[3] 沈 波, 张世永, 钟亦平. 无线传感器网络分簇路由协 议[J]. 软件学报, 2006, 17(7): 1588-1600.

[4] Younis O, Fahmy S. HEED: A Hybrid Energy-efficient Distri- buted Clustering Approach for Ad-hoc Sensor Networks[J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366- 379.

[5] Lin C H R, Gerla M. A Distributed Architecture for Multi-

media in Dynamic Wireless Networks[C]//Proc. of IEEE GLOBECOM’95. Los Angeles, USA: [s. n.], 1995: 1468- 1472.

[6] Heinzelman W R, Chandrakasan A P, Balakrishnan H. An Application-specific Protocol Architectures for Wireless Microsensor Networks[J]. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-669.

[7] 李成法, 陈贵海. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报, 2007, 30(1): 28-36.

[8] 刘星成, 袁东升. 基于代价函数的WSN能效路由协议性能分析[J]. 软件学报, 2011, 32(6): 133-140.

[9] 江海峰, 钱建生. WSN中基于能量代价的能量优化路由算法[J]. 计算机科学, 2012, 39(1): 73-76.

[10] 蒋畅江, 石为人. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报, 2012, 23(5): 1222-1232.

[11] 尹 安, 汪秉文. MintRoute-HNLB: 一种支持负载均衡的无线传感器网络路由协议[J]. 计算机科学, 2010, 37(5): 77-80.

[12] 李成岳, 申铉京. 无线传感器网络中LEACH路由算法的研究与改进[J]. 传感技术学报, 2010, 23(8): 1164-1167.

[13] Lindsey S, Raghavendra C S. PEGASIS: Power-efficient Gather in Sensor Information Systems[C]//Proc. of IEEE Aerospace Conferwnce. [S. 1.]: IEEE Press, 2002: 1125-1130.

[14] 胡 平.基于节能的无线传感器网络分簇路由协议研究[D]. 南京: 南京理工大学, 2009.

编辑 索书志

Clustering Routing Algorithm Based on Node Degree and Distance for Wireless Sensor Networks

LI Hui, LIU Shu-ji

(School of Electrical Engineering and Automation, Henan Polytechnic University, Jiaozuo 454000, China)

Aiming at the problem of unnecessary energy consumption caused by periodic clustering and the load balance problem in the Wireless Sensor Networks(WSN), an Unequal Clustering routing algorithm based on node Degree and Distance for WSN(UCDD) is proposed. UCDD algorithm adopts the time competitive mechanism in the first round of clustering. The length of time depends on the nodes’ node degree and the distance from the base station, and different clusters are formed according to the different radius of competition. After the first round, the clusters’ structure does not change any more. Cluster head dynamically choose next cluster head according to the residual energy and the communication costs. Inter-cluster multihop routing is used in UCDD algorithm, and the relay node is selected according to node residual energy, distance from the base station, communication cost of nodes and relay hot. Simulation results show that the algorithm can prolong the networks lifetime by more than two times compared with LEACH protocol and by 13.97% compared with EEUC protocol. Besides, it balances the energy dissipation of the networks.

Wireless Sensor Networks(WSN); unequal clustering; node degree; distance; relay heat; dynamic rotation

1000-3428(2014)03-0113-07

A

TP391

李 辉(1976－)，男，副教授，主研方向：无线传感器网络；刘书吉，硕士研究生。

2013-03-04

2013-04-18 E-mail：li20042007@163.com

10.3969/j.issn.1000-3428.2014.03.023