无线传感器网络基于节点调度的双簇头路由协议

邬春学， 毕春霞， 孟其琛

（上海理工大学光电信息与计算机工程学院，上海 200093）

无线传感器网络基于节点调度的双簇头路由协议

邬春学， 毕春霞， 孟其琛

（上海理工大学光电信息与计算机工程学院，上海 200093）

为了延长无线传感器网络的生命周期，提高节点能量利用率，将分簇与节点调度相结合，提出了一种基于节点调度的双簇头的路由协议.该算法利用节点调度实现网络中冗余节点查找，减少分簇时活跃节点；考虑节点和基站的距离及能量，优化选择主、副簇头，副簇头优先选择冗余节点.主簇头用以收集和融合簇内节点的信息，副簇头负责与基站进行通信.仿真结果表明，新算法能有效节约网络能量、平衡节点能耗、延长网络生存时间.

无线传感器网络；节点调度；分簇；主副簇头

无线传感器网络（W SN）由大量具备数据处理和通信能力的传感器节点组成，其目的是协作地感知、采集和处理W SN覆盖范围内监测对象的相关信息，并通过无线的通信方式将监测数据发送到基站（Sink节点），供用户分析和处理.但W SN中节点能量有限，且不易补充能量［1］，为延长网络生命周期，在网络设计时需要采用合适的路由协议.受节点能量有限的限制，其感知和通信范围有限，所以，常在监测区域部署大量的节点以延长网络生存时间，但大量节点容易造成冗余，因此，在W SN中应采用合理的节点调度，有效利用节点能量，提高网络生存周期.

1 路由协议优化和节点调度分析

W SN的路由协议分为平面路由协议和分层路由协议两种.分层协议性能要优于平面路由协议，因为，分层协议采用了“分而治之”的思想，有效地降低了网络能耗.图1是经典低功耗自适应分簇路由协议LEACH［2］的示意图，它采用分簇机制，簇头融合簇内节点信息后再传输给Sink节点，大大降低了网络中节点的能耗.但是，LEACH算法随机选举簇头，导致能量较低的节点也能担任簇头，容易造成数据丢失；同时LEACH算法中簇头是直接与Sink节点通信，即单跳通信方式，对于距离Sink节点较远的簇头节点，能量消耗过多，容易死亡，形成网络“能量空洞”，造成网络不稳定，降低了网络的生命周期［3］.因此，在LEACH基础上有许多改进的算法，如文献［4］的LEACH-C算法，在簇头的选取过程中引入能量阈值，只有当节点的剩余能量大于阈值时，节点才有资格当选为簇头节点，避免一些低能量的节点担任簇头，同时簇头与Sink节点之间的通信采用多跳的方式，避免了簇头由于长距离通信而造成能量消耗过大的情况.文献［5］的蚁群LEACH算法，根据剩余能量和路由长度确定遗留信息素，建立簇头节点间的多跳路由，优化了网络性能.大多数改进的LEACH算法，根据节点的剩余能量，采用单簇头机制，在簇头任务过重时，造成簇头能量降低较快.文献［6］的DCHACS算法采用局部调整的方式选取双簇头，并在数据传输时采用双簇头轮流担任簇头的方式，有效地均衡了网络的能量消耗.

W SN中节点的覆盖能力和能量有限，所以，监测区域内往往部署大量的节点.节点的工作状态分为3种：工作状态、侦听状态和休眠状态.文献［7］分析说明，节点处于侦听状态时消耗的能量与工作状态消耗的能量相差不大，休眠状态节点的能耗很小，因此，对于不需要处于工作状态的节点，应尽量让其处于休眠状态.W SN中节点大规模密集部署，布置密度不均衡，某个区域往往被多个传感器节点同时覆盖，这种情况被称为冗余覆盖［8］.如果所有节点全部处于活跃状态，会导致节点通信频繁、信息冗余，增加网络能量消耗，降低网络通信效率，因此，引入节点调度，在满足任意时刻处于活跃状态的节点能够有效监控目标区域的基础上，采用轮换活跃／休眠节点的调度方式，调度部分节点进入睡眠，达到减少能量消耗和延长网络生存时间的目的［8］.图2是节点调度示意图.

图1 L E A C H协议Fig.1 L E A C H protocol

图2 节点调度机制Fig.2 Node scheduling mechanism

文献［9］提出的M C M CC算法，将整个监测区域分为互不相交的子区域，子区域根据节点感知范围的重叠情况确定节点是否冗余.文献［10］提出了基于构造最小控制集合（M DS）的图论计算方法.M DS由一组能够保证监测区域完全覆盖的工作节点组成，各个M DS交替工作.文献［11］通过建立数学模型分析节点的冗余度，根据邻居节点判断节点是否为冗余.文献［12］提出的N D NS算法，利用节点与邻居节点的距离信息，对节点覆盖冗余判别，适应于任意分布下的网络部署方式.

本文结合分簇和节点调度的思想，提出一种基于节点调度的双簇头路由算法（D HCNS）.D HCNS算法通过有效的节点调度算法查找冗余节点，然后再对非冗余节点分簇，并采用双簇头机制，选取双簇头不仅考虑节点的剩余能量、节点与Sink节点之间的距离，还考虑到非冗余节点的影响.

2 D H C NS路由协议

2.1 模型描述

假设W SN中大量节点随机部署在一个正方形的区域内，并具有如下特点：

a.节点具有唯一的编号（ID），除Sink节点外其它节点的初始条件相同，能耗异构，感知半径固定为r；

b.节点不具备位置感知能力，但可根据从邻居节点接收信号强度估算两者之间的距离；

c.所有节点是静止的，网络为对称网络，节点间可相互通信，在一定范围内可调整节点发射功率.

2.2 无线通信能耗模型

发送消息和接收消息节点之间的距离d存在一个阈值d0.当d≤d0时采用自由空间模型，而d＞d0时采用多径衰落信道模型.在本文中，簇的覆盖区域半径为r（2r≤d0），即在簇头通信半径r内的节点才能成为簇内节点；同时簇头之间通信距离限制在2r范围内，这样网络中簇内和簇间的通信都是自由空间的通信模型.节点发送和接收消耗的能量ES和ER分别为［11］

式中，k为发送／接收的数据比特数；Ee为发送／接收电路发送／接收1 bit消耗的能量；Ef为放大电路在单位面积内传播每比特信号所消耗的能量；簇头进行数据融合和处理时；Ek为处理kbit数据消耗的能量，Eu为处理单位数据消耗的能量.

2.3 冗余节点的查找

节点调度算法主要分为两类：借助节点的精确位置信息和不依赖于节点的精确位置信息的节点的调度.后者又分为两种：a.随机调度，每个节点以一定概率独立进入休眠或工作状态；b.借助于节点间的距离、邻居节点个数等信息，计算覆盖冗余［9］.然而，为大规模的W SN网络提供精确的定位信息非常困难，成本也很高，甚至节点调度所节约的能量被定位中消耗的能量抵消［13］.随机调度不需要节点相互通信就可实现，但存在某些监测区域不被任何节点覆盖的“覆盖洞”，难以保证网络的覆盖质量［12］，因此，借助于节点间的距离、邻居节点个数等信息的节点调度是目前研究的热点.本文中所采用的节点调度算法为文献［12］中的N D NS算法，其适用的场合非常广泛.

定义节点Ni为非冗余节点，节点Mj为冗余节点，SN为节点Ni的辅助集.

依据N D NS算法冗余查找，每个冗余节点Mj向距离自己最近的非冗余节点Ni发送一个加入请求信息，节点Ni接收加入请求信息，并将冗余节点Mj加入到自身的辅助节点集SN；若节点Ni有多个辅助节点，选择距离能量比EL.最大的冗余节点作为自己的辅助节点，辅助节点集SN中其余的冗余节点进入休眠状态.非冗余节点和辅助节点作为一个整体参与簇头的竞选.

2.4 簇头竞选标准

LEACH-C算法在簇头竞选时考虑了节点的剩余能量，但没有考虑节点与Sink节点之间的距离的影响.基于此，提出一种新的簇头选取因子：距离能量比EL（distance-energy level）.

定义1假设节点为Ni，i=1，2，…，n，Ei为节点Ni的剩余能量，则

式中，d（NS，Ni）为Sink节点与Ni之间的距离.网络初始化阶段，Sink节点在整个网络广播消息，网络中的节点根据接收到的消息的信号强度估算与Sink节点之间的距离d（NS，Ni）；p为簇头的节点占节点总数的百分率；λ为当前的轮数；mod（1／p）代表这一轮循环中当选簇头的节点个数；G是在过去1／p轮中未充当簇头的节点集合.

2.5 簇的形成

非冗余节点及其辅助节点作为一个整体参与簇头竞争，簇的形成过程如下：

Step 1根据式（5）选举主簇头.若主簇头有辅助节点，进入Step 2；否则，进入Step 3.

Step 2辅助节点的剩余能量大于能量阈值Ea时，当选为副簇头；若低于Ea，辅助节点进入休眠，进入Step 3.

Step 3主簇头节点广播消息，网络中的非冗余节点根据接收信号的强弱加入该簇.

Step 4簇头给簇内发送包括簇内编号、主副簇头等信息.若簇没有副簇头，进入Step 5.

Step 5在簇内的普通节点中选择EL最大的节点为副簇头，并在簇内广播副簇头消息.

簇形成后，普通节点的辅助节点进入休眠.簇内节点在时分多址（T D M A）时隙内将采集的数据发送给主簇头，主簇头进行融合后发送给副簇头，副簇头再将数据转发给临近簇的副簇头，最后将数据传送到基站.使用主副簇头分担不同的任务，可以在一定程度上将簇头的能耗分散，实现能耗均衡，延长网络的生命周期.

2.6 簇间通信

簇形成后，簇头向其覆盖半径2r内发送簇头消息，消息包含节点ID及距离能量级EL.各簇头比较自身和收到的EL，选择EL最大的簇头节点作为父节点，并发送入簇消息通知父节点；若节点未收到任何簇头和入簇消息，将直接与基站通信，这种情况可能发生在节点绝大部分死亡的情况或距离基站近且能量足够的节点.图3是D HCNS协议的示意图.

图3 D H C N S协议Fig.3 D H C N S protocol

3 仿真与分析

仿真以Matlab软件为平台，模拟实现了LEACH-C协议、LEACH-C+N D NS协议以及D HCNS协议，对3种协议的性能进行比较，仿真环境参数为：仿真区域为100 m×100 m的正方形区域，Sink节点位置为（100，200），节点的初始能量为0.5 J，传感半径为10 m，通信半径为20 m，数据包大小为4 000 bit，控制包大小为100 bit，Ef为10 pJ／（bit·m-2），Ee为50 nJ／bit，Eu为5 nJ／bit，Ea为0.001 3 pJ／（bit·m-2）.

当节点的能量耗尽时节点死亡.由于休眠状态下节点的能耗相对发送／接收状态下的能耗很小，因此，假定此状态下节点能量消耗为0.

图4给出了2种场景下3种协议的网络生存时间情况.在场景1中节点数量为200，场景2中节点数量为300.图5给出了2种场景下3种协议的网络总能耗情况.从图4可以看出，LEACH-C出现第一个节点死亡的时间要远早于后面的2种协议，因为，LEACH没有采用冗余节点休眠机制，网络中大量节点处于活跃状态，加剧了节点的能量消耗，导致节点过早的死亡.D HCNS协议由于采用了双簇头机制，进一步降低了主簇头的能量损耗，因此，其性能要优于LEACH-C+N D NS.

从图5可以看出，LEACH-C的性能在节点数为300时要差于节点数为200时.随着节点数的增多，监测区域没有变化时，过多的活跃节点反而使得网络的性能变差，网络的生存时间变短.节点数发生变化时，其它2种协议的冗余查找方式相同，因此，2种场景下的路由协议并没有很大的差异，但D HCNS协议中采用双簇头机制，选择主簇头的冗余节点为其副簇头，随着网络节点数的增加，冗余节点增多，因此，可作为副簇头的节点也增多，进一步将簇头能耗平摊到其它节点，即节点数量为300时，D HCNS的性能要优于节点数量为200时的性能.

图4 网络生存时间Fig.4 Lifetime of network

图5 网络的总能耗Fig.5 The total energy consu m ption of network

4 结束语

在研究分簇算法和节点调度算法的基础上，提出了一种无线传感器网络节点调度优化分簇算法（D HCNS）.D HCNS算法可以运用于任何大量节点部署的W SN中，该算法先查找网络冗余节点，减少活跃节点的数量，然后在活跃节点中选取主副簇头.主簇头根据节点的剩余能量和距离能量比选取，副簇头主要在主簇头的冗余节点中选取，从而更加有效地提高网络性能.通过双簇头分担网络任务，主簇头主要负责簇内通信，副簇头则是簇间通信，将网络能耗均分到网络节点中，实现延长网络生存周期的目的.

［1］ 李凌，周兴社，李士宁，等.基于无线传感器网络的拥塞控制算法的研究与比较［J］.计算机应用研究，2006，23（3）：11-13.

［2］ Heinzelman W B，Chandrakasan A P，Balakrishnan H.An appl ication-specif ic protocol architecture forwireless microsensor networks［J］.Wireless Com munications，IEEE Transactions，2002，1（4）：660-670.

［3］ 于林峰，肖丽.一种基于W SN的协议改进算法分析［J］.上海理工大学学报，2009，31（4）：406-408.

［4］ Muruganathan S D，Ma D C F，Bhasin R I，et al.A central ized energy-eff icient routing protocol for wireless sensor networks［J］.Com munications Magazine，IEEE， 2005，43（3）：S8-13.

［5］ 邬春学，肖丽.基于蚁群算法的低能耗LEACH协议分析［J］.上海理工大学学报，2010，32（1）：99-102.

［6］ 赵小川，周正，秦智超.基于双簇头交替和压缩感知的W SN路由协议［J］.软件学报，2012，23（1）：17-24

［7］ 魏剑平，樊勇，李英奇，等.一种基于能量均衡的无线传感器网络协议［J］.小型微型计算机系统，2011，32（1）：133-136.

［8］ 包旭，巨永锋.保持覆盖的无线传感器网络簇内节点调度方法［J］.计算机工程与应用，2011，47（15）：12-14.

［9］ Sl i jepcevic S，Potkonjak M.Power eff icient organization of wireless sensor networks［C］∥IEEE International Conference on Com munications.2001：472-476.

［10］ Pazand B，DattaA.Minimumdominating sets for solving the coverage probleminwireless sensor networks［C］∥Ubiquitous Computing Systems.2006：454-466.

［11］ Gao Y，W u K，Li F.Analysis on the redundancy of wireless sensor networks［C］／／Proceedings of the 2nd AC M International Conference onWireless Sensor Networks and Appl ications.2003：108-114.

［12］ 凡高娟，孙力娟，王汝传，等.非均匀分布下无线传感器网络节点调度机制［J］.通信学报，2011，32（3）：10-17.

［13］ Younis O，Fahmy S.HEED：a hybrid，energy-efficient，distributed clusteringapproachforAdhocsensor networks［J］.Mobi le Computing，IEEE Transactions，2004，3（4）：366-379.

（编辑：石 瑛）

Double Head Clustering Algorith m Based on N ode Scheduling in W ireless Sensor Netw orks

W U Chun-xue， BI Chun-xia， MENG Qi-chen
（School of Optical-Electrical and Com puter Engineering，University of Shanghai for Science and Technology，Shanghai 200093，China）

In order to prolong the lifetime of wireless sensor network（W SN）and improve the energy efficiency，a double cluster head routing protocol based on node schedulingmethod（D HCNS）for W SN was proposed by combining the techniques of cluster and node scheduling.In the algorithm the node scheduling was used to reduce the number ofactive nodes before clustering. The master and vice cluster-head were selected according to both on node energy and distance to base station and the redundant nodes were selected as the vice cluster-head in priority.The master cluster-head was used for collecting and integrating data.The vice cluster-head was in charge of transporting data to base station.The simulation results show that D HCNS can effectively reduce energy consumption，balance the energy of nodes，and prolong the network lifetime.

wireless sensor network；node scheduling；clustering；m aster-vice cluster head

TP 393

A

1007-6735（2013）05-0501-05

2012-12-30

国家自然科学基金资助项目（61202376）

邬春学（1964-），男，教授.研究方向：无线传感器网络、网络控制系统.E-mai l：tyfond＠126.com