一种能量高效的无线传感器网络分簇路由协议

2014-02-23曹建玲王路路

重庆邮电大学学报(自然科学版) 2014年2期

曹建玲，余俊，王路路，任智

(重庆邮电大学移动通信技术重庆市重点实验室，重庆， 400065)

0 引言

无线传感器网络(wireless sensor networks，WSNs)是由许多价格低廉、能量有限，且具有数据采集功能的节点组成的网络［1］。它们之间通过特定的协议自组织起来，能够获取周围环境的信息并且相互协同工作，完成特定的任务，在军事、环境监测、工业控制、智能家居和城市交通等方面都有重要的使用价值，已成为热点研究领域，是21世纪新兴的、且被美国商业周刊列为改变世界的十大技术之一。无线传感器网络由于受到硬件条件的限制，使得节点只具备有限的信息处理能力和计算能力，节点通常采用电池供电，而电池的能量是有限的［2］。因此，设计能量有效的WSNs路由协议显得尤为重要。

根据网络体系结构的不同，无线传感器网络路由协议可以分为两类:平面路由协议和分簇路由协议［3］。平面路由协议简单、无需维护、易扩展，而且算法容易实现［4］。层次路由协议的主要思想是让一部分节点特殊化，使其不仅传输自己的数据，还负责协调和发送邻近节点的数据［5］。分簇路由协议是典型的层次型路由协议，在很多WSN协议中应用分簇方式也产生了很好的效果。

低功耗自适应集簇分层型(low－energy adaptive clustering hierarchy，LEACH)协议［6］是 Heinzelman等提出的第1个分簇路由协议，该协议在选举簇头时，没有考虑节点的剩余能量，缩短了网络寿命。决定性簇头选择(deterministic cluster－head selection，DCHS)［7］针对LEACH的不足提出了改进，添加了对节点当前剩余能量的考虑，但随着网络的运行，存在产生簇头数目少而影响节点入网的问题。以上2种协议在簇建立阶段，非簇头节点都是以载波侦听多路访问 (carrier sensemultiple access，CSMA)的方式发送入簇信息，增加了入簇的时延和碰撞概率。本文针对这些问题提出了一种能量高效的分簇路由(energy efficient clustering，EEC)算法，设计了一种新的簇头选举机制，不仅考虑了节点剩余能量，而且能够保证网络中簇头节点的数量，并且用CDMA机制使非簇头入簇，减少了对相邻节点的干扰，有效地延长了网络生存时间，且网络能耗更加均衡。

1 相关工作

1.1 LEACH

LEACH协议是最早提出的分簇路由协议，该协议是针对无线传感器网络设计的低功耗、自适应路由协议，该协议在选择簇头节点时，将整个网络的负载平均分配到每个节点上，从而降低能耗、延长网络的生存时间［6］。LEACH能够保证各节点等概率地担任簇头。它的执行过程是周期性的，每轮循环分为簇的建立阶段和稳定的数据通信阶段［8］。网络开始时，每个节点都会产生一个0～1的随机数，如果随机数小于阈值T(n)，则该节点就当选为本轮的簇头。T(n)的定义为

(1)式中:p值为网络中簇头节点占总节点数量的百分比，这个值是网络初始化时设定的，p为0. 05;r为网络当前运行的轮数;G是当前1/p轮没有当选过簇头的节点集合。

该协议在选举簇头时，并没有考虑节点的剩余能量，如果当选为簇头的节点的剩余能量很少，那么在当选为簇头后很快就会死亡，缩短了网络寿命。

1.2 DCHS

DCHS针对LEACH的不足，提出了2种改进方法［7］。第1种是在LEACH的基础上，添加了对节点当前剩余能量的考虑，改进后的阈值函数T(n)的表达式为(2)式中:Ec为节点的剩余能量;Ei为节点的初始能量。这在一定程度上改进了LEACH的不足，延长了网络的生存时间。但随着网络的运行，网络中节点剩余能量减少，节点每次产生的阈值变小，导致网络中簇头数目减少，甚至出现没有簇头的现象，最终导致网络能量消耗不均衡。因此，DCHS协议提出了第2种改进方法，阈值T(n)表达式为

(3)式中，rs表示节点没有当选为簇头节点的轮数。在网络当前运行的1/p轮中，(3)式等价于(2)式，能量大的节点成为簇头的概率大。当节点在当前1/p轮中还没有当选簇头，(3)式等价于(1)式，没有当选簇头的节点按照网络设置的簇头选举概率随机自举为簇头。随着网络的运行，当节点能量较低时，若节点在当前1/p轮中还没有当选簇头，则节点在自举时不再考虑当前剩余能量，而是按照网络设置的概率值随机自举簇头，保证网络中簇头节点的数目。但在(3)式中，节点只有在当前1/p轮中没有当选过簇头节点，才能随机自举。当网络运行若干周期后，节点剩余能量小于初始能量，在该周期的1/p轮中，阈值函数产生的值变小，网络中的簇头数目一直很少。

2 EEC分簇路由协议

2.1 网络模型

网络模型中，K个节点随机均匀分布在方形监测区域。该网络用于周期性、小规模的数据采集，如温度、光照等。网络中所对应的无线传感器节点集合为 N={n1，n2，…，nk}，|N|=K。现做如下假设:在EEC中，sink节点位于监测区域的边缘。在网络中，节点经部署后，位置不会发生改变;每一个节点都有一个唯一的标识;所有节点都具有数据融合能力。节点可以根据发送节点的功率和接收信号的强度确定与发送节点之间的距离，且可以根据节点之间的距离自由调节发射功率来节省能量。每个节点知道自己的位置信息。

2.2 能耗模型

文中采用和文献［9］相同的无线通信能量消耗模型。节点发送l比特数据给距离为d的节点，消耗的能量由发射电路损耗和功率放大损耗两部分组成，即［10］

(4)式中:Eelec表示发射机的电路损耗能量;εfs和εmp分别为2种能量模型中功率放大器的能耗因子;d0表示功率放大器采用不同模型的阈值，如果发射机和接收机之间的距离小于d0，则功率放大器采用自由空间模型;如果发射机和接收机之间的距离大于等于d0，则功率放大器采用多径衰减模型。

接收机接收l比特数据的能量消耗为

(5)式中，用于接收的电路损耗的能量Eelec和发射机的发射电路损耗相同。

2.3 EEC协议的执行步骤

EEC协议的执行步骤如下。

1 )簇头自举。每个节点均匀分布，生成一个随机数，将其与阈值进行比较，确定是否在该轮担任簇头节点;

2 )当选为簇头的节点以一定的发射功率广播CH_MSG消息，消息中包含簇头ID、当前剩余能量以及随机选取的扩频码。簇头节点广播CH_MSG后，把自己的扩频码设为随机选取的扩频码，准备接受入簇信息;

3 )非簇头节点收到CH_MSG消息后，选取强度最大的节点作为自己的簇头节点，从CH_MSG消息中获得扩频码，并以CDMA的方式向簇头节点发送JOIN_MSG消息，消息中包含节点的ID;

4 )所有非簇头节点加入簇后，簇头节点为簇成员节点分配时隙，并把时隙信息在簇内进行广播;

5 )簇内节点在自己的时隙内把采集到的数据发送给簇头节点。簇头节点将数据进行融合，并把融合后的数据通过多跳的方式发送给sink;

6 )每个节点每t s进行一次簇头轮换，循环进行1)到5)的步骤。

2.4 簇头选举

通过分析LEACH和DCHS协议的不足之处，EEC对阈值函数T(n)进行了如下改进。

(7)式中:M是监控区域的大小;N是网络中节点的数目;dtobs是sink节点到监测区域的距离。p值的大小和LEACH，DCHS中的p值的大小都取0.05。

(6)式分以下3种情况考虑。

由此可见，剩余能量多的节点集中在当前周期的前半轮，自举为簇头节点。为了避免网络中簇头数目少的问题，在当前周期的后半轮，节点随机自举为簇头。和LEACH一样，当网络运行至当前周期的最后一轮时，没有当选过簇头的节点以概率1成为簇头节点，将网络能量消耗分配到每个节点上，均衡网络能量消耗。

2.5 非簇头节点入簇方式

LEACH协议和DCHS协议在簇建立阶段，当普通节点接收到簇头节点的宣告信息后，非簇头节点根据接收信号的强弱，选择信号强的簇头节点作为自己的簇头节点，并以CSMA的方式发送入簇信息。采用CSMA的方式增加了入簇的时延，且由于传感器节点分布密度大，碰撞的概率大。

EEC协议采用的是CDMA方式发送入簇信息。当节点自举为簇头节点后，簇头节点就向网络广播自己是簇头的消息，消息中包含簇头节点随机选取的扩频码。当簇头节点广播宣告信息后，簇头节点进入CDMA模式，簇内节点根据接收到的宣告信息中的扩频码，以CDMA的方式发送入簇信息。采用CDMA方式可以避免簇间普通节点入簇时的干扰，减少入簇时延。

3 仿真及性能分析

3.1 仿真环境

仿真采用OPNET14.5软件，在仿真中，100个节点随机均匀分布在100 m×100 m的方形区域中，汇聚节点位于监测区域的外部。

仿真中假定:当节点剩余能量低于初始能量的5%时，节点死亡;当网络中死亡节点数大于20%时，网络寿命结束;网络每轮运行的时间设为30 s。仿真参数设置如表1所示。

表1 OPNET网络仿真参数Tab.1 OPNET simulation parameters

3.2 仿真结果分析

文中提出的EEC协议对DCHS协议进行了多处改进，并设计出了完整的仿真代码，将EEC与DCHS协议和LEACH协议在网络生存时间、首个节点死亡时间、网络平均能量消耗速率以及网络中平均簇头数量等4个方面分别进行了仿真分析。

3.2.1 网络生存时间

图1为汇聚节点到网络边缘距离不同时的网络生存时间对比图。图1显示，当网络到sink节点的距离逐渐增大时，3种协议的网络生存时间均减少，但是EEC协议的生存时间均比DCHS和LEACH协议的生存时间长。这是由于EEC在选举簇头时，考虑了节点的当前剩余能量，剩余能量多的节点以更大概率成为簇头，并保证网络中簇头节点的数量。从而达到能量消耗均衡，延长了网络生存时间。在EEC中，簇头在发送数据时采用多跳无线通信方式，也极大降低了簇头节点的能量消耗。随着汇聚节点sink距离网络越来越远，EEC协议和另外2种协议的网络生存时间相差也变得越来越大。

图1 网络生存时间比较Fig.1 Comparison of network lifetime

3.2.2 首个节点死亡时间

图2为汇聚节点距离网络边缘位置不同时的首个节点死亡时间的仿真结果图。图2显示，当汇聚节点距离网络边缘位置相同时，EEC的首个节点死亡最晚，随着汇聚节点距离网络边缘距离的增大，3种协议的首个节点死亡时间都变早，但EEC协议依然表现最好。这是由于EEC协议进行簇头选举时，节点考虑自身的当前剩余能量进行自举，且在簇头发送数据时采用多跳的通信方式，而LEACH协议和DCHS协议都采用单跳的方式，因此，簇头能量消耗远远低于另外2种协议，首个节点死亡的时间也最晚。

图2 首个节点死亡时间比较Fig.2 Comparison of the first node death time

3.2.3 网络平均能耗速率

图3为汇聚节点位置不同时，3种协议的网络平均能耗速率仿真图。图3显示，当汇聚节点距离网络边缘的距离相等时，LEACH协议的能量消耗速率最大，EEC协议的能量消耗速率最小。当汇聚节点距离网络边缘的距离增大时，靠近汇聚节点的簇头节点能量消耗增大，3种协议的网络平均能量消耗速率均增大，但LEACH协议和DCHS协议随全网簇头节点的发送距离增大，簇头节点能量消耗也增大，而EEC协议簇间采用多跳模式，减少了网络能量消耗，EEC协议网络平均能量消耗速率低于LEACH协议和DCHS协议。DCHS协议在选取簇头时，考虑节点的当前剩余能量，网络能耗均衡，延长了网络生存时间，网络平均能耗速率低于LEACH协议。

3.2.4 平均簇头个数

图4为网络范围不同时，3种协议的平均簇头个数的仿真结果图。由图4可见，当网络范围增大时，网络中簇头数目增多。对于 LEACH协议和EEC协议，虽然网络的平均簇头数目增加，但簇头数目与总节点数的比值基本不变。可见，EEC协议在改进簇头选举概率的前提下，保证了网络中的簇头数目。由于DCHS协议在选举簇头时仅考虑节点当前剩余能量，当网络运行若干轮后，节点剩余能量减少，节点自举的阈值变小，导致网络中簇头数目减少。

图3 网络平均能量消耗速率比较Fig.3 Comparison of the network energy consumption rate

图4 平均簇头个数比较Fig.4 Comparison of the average number of cluster heads

4 结束语

在分析已有分簇路由协议DCHS的基础上，提出了能量高效的分簇路由协议EEC，在选举簇头时，不仅考虑了节点当前的剩余能量，还保证了整个网络中簇头节点的数目，避免了网络中簇头数目少的问题。在非簇头节点加入簇时，该协议采用的是CDMA方式，这与LEACH和DCHS协议采用的CSMA不同，CDMA方式可以减少簇间的干扰，能有效地均衡网络中的能量消耗，从而达到延长网络生存时间的目的。

［1］DAIShijin，LI Lemin.A High Energy－Efficient Data Collecting and Routing Protocol forWireless Sensor Networks［J］.ACTAELECTRONICA，2010，38(10):23－36.

［2］胡刚，谢冬梅，吴元忠.无线传感器网络路由协议LEACH的研究与改进［J］.传感技术学报，2007，20(6):1392－1393.

HU Gang，XIEDongmei，WU Yuanzhong.The research and improvement of LEACH for Wireless Sensor Networks［J］.Chinese Journal of Sensors and Actuators，2007，20(6):1392－1393.

［3］任丰原，黄海宋，林闯.无线传感器网络［J］.软件学报，2003，14(7):1282－1291.

REN Fengyuan，HUANG Haisong，LIN Chuang.Wireless Sensor Networks［J］.Journal of Software，2003，14(7):1282－1291.

［4］郑军，张宝贤.无线传感器网络技术［M］.北京:机械工业出版社，2012:15－28.

ZHENG Jun，ZHANG Baoxian.Wireless Sensor Network Technology［M］.Beijing:Mechanical Industry Press，2012:15－28.

［5］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1589.

SHEN Bo，ZHANG Shiyong，ZHONG Yiping.Clustering Routing Protocol for Wireless Sensor Networks［J］.Journal of Software，2006，17(7):1589.

［6］HEINZELMANW R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－Efficient Communication Protocol forWireless Microsensor Networks［C］//IEEE.Proceedings of the Hawaii International Conference on System Sciences.Maui:IEEE Los Alamitos，2000:1－10.

［7］HEINZELMANW R，CHANDRAKASAN A，BALAKRISHNAN H.Energy－Efficient Communication Protocol forWireless Microsensor Networks［C］//IEEE.Proceedings of the Hawaii International Conference on System Sciences.Maui:IEEE Los Alamitos，2000:325－349.

［8］CHEN X J，WANG Z，WU J.The Improved Wireless Sensor Network Routing Algorithm Based on LEACH［J］.CHINESE JOURNAL OF SENSORSAND ACTUATORS，2013，26(1):116－120.

［9］ZHANG Y，LIY.Cluster－head selection enhancing algorithm based on energy for wireless sensor networks［J］.Journal of Chongqing University of Posts and Telecommunications:Natural Science Edition，2007，19(5):1－5.

［10］张怡，李云，刘占军.无线传感器网络中基于能量的簇首选择改进算法［J］.重庆邮电大学学报:自然科学版，2007，19(5):614－615.

ZHANG Yi，LIYun，LIU Zhanjun.Cluster－head selection enhancing algorithm based on energy for wireless sensor networks［J］.Journalof Chongqing University of Posts and Telecommunications:Natural Science Edition，2007，19(5):614－615.