基于分簇的无线传感器网络数据收集协议研究

王 靓，范德辉

（1.复旦大学 信息科学与工程学院，上海 200433；2.青岛职业技术学院，山东 青岛 266555）

基于分簇的无线传感器网络数据收集协议研究

王 靓1，2，范德辉2

（1.复旦大学 信息科学与工程学院，上海 200433；2.青岛职业技术学院，山东 青岛 266555）

为延长无线传感器网络（WSN）的寿命，在传统的典型分簇算法LEACH和EADEEG的基础上进行改进，提出了一种新的基于分簇结构的数据收集协议—IDCP（Improued Data Collectiou Protocot，IDCP），在簇首形成阶段和数据转发传递阶段分别提出了新的簇首形成算法和簇内数据转发算法.在簇首形成阶段，引入对节点可靠度指标的考量；在数据转发传递阶段，所有簇内普通节点对需要转发的信息首先进行判断分析，再决定是否进行信息传递.仿真实验结果表明：与传统协议相比较，改进算法在簇首选择和数据转发上都具有更好的网络处理能力和更高的效率，有效延长了网络生存周期.

无线传感器网络；分簇；数据收集；能量

无线传感器网络（WSN）是一种灵活度高、能量有限的网络，在军事国防、生物医疗、环境监测、交通管理和家庭等各个领域拥有十分广阔的应用前景，对人类发展具有十分重要的影响［1－2］.多数情况下，传感器网络中节点的供电电源能量有限，因此，如何有效利用网络能量、提高效率是WSN协议设计所面临的首要问题［3］.

从网络拓扑结构角度来看，WSN协议可以分为平面路由［4］协议和分簇路由协议［5］，平面路由协议中的节点没有层次差异［6］，级别相同；分簇路由协议将具有某种关联的网络节点划分为簇，每个簇内有一个簇首和多个簇内成员，根据等级的不同簇被划分为多层结构，基站与最高层簇首通信，最高层簇的簇内成员是低一级簇的簇首，层层关联，将整个网络划分为相连的多个区域.

在WSN分簇算法研究中，最早的分簇路由协议有LEACH（Low Energy AdaptiveClustering Hierarchy），该算法是目前比较成熟且常用的分簇路由算法［3］.LEACH算法采用随机簇首选择机制，具有实现简单、操作灵活和可扩展性好等优点，但容易形成网络内节点能量损耗不均衡的状态，个别节点过早死亡，网络的整体性能差.在国内，刘明等人［2］提出了一种基于能量感知的无线传感器网络数据收集协议—EADEEG（Energy－Aware Distributed Energy－Efficient data Gathering protocol for wireless sensor networks，EADEEG）.EADEEG算法由簇内各节点平均剩余能量的多少作为是否成为簇首的判断条件，使各节点耗能比较平均，较好地解决了网络内节点能量损耗不均衡问题.但在实际网络中，由于节点所处环境和自身设计等原因，能量并不能作为参选簇首的唯一标准，还需综合考虑节点感知数据的精确度.

本研究在前面2种协议的研究基础上，着重对EADEEG协议的簇首选取过程以及簇内通信过程进行研究、改进和仿真，提出了一种改进的基于分簇结构的数据收集协议—IDCP.一方面，在簇首形成阶段，充分考虑了簇节点的感知可靠度和 网络性能等因素，有效提高了节点加入簇的效率，从而延长网络寿命；另一方面，在簇拓扑形成后的数据转发传递阶段，对簇内普通节点要转发给簇首的数据进行“判断分析”式的转发处理，将相邻2个Δt时间内的信息做期望值分析，如果大于一个判断期望值，表明周围信息变化较大，则进行信息传递，否则表明周围信息变化不明显，将不再转发该信息到簇首节点，从而达到了减少网络无用通信、延长网络寿命的效果.同时，本研究利用Matlab仿真实验环境，对2种经典算法协议和改进的IDCP算法协议进行了模拟仿真，分别把3种算法在簇首形成算法和簇内数据转发算法两方面的节点死亡时间进行了对比.

1 基于分簇的数据收集协议

1.1 簇首形成算法

1.1.1 算法描述

LEACH算法定义了“轮”的概念，一轮由初始化和稳定工作2个阶段组成.初始化即簇准备阶段，该阶段根据相应算法选出簇首，形成自适应簇的簇拓扑结构；稳定工作阶段即就绪阶段，完成整个监测区域数据的转发和聚集［3，7］.WSN中每个节点的身份都用全网唯一的数值进行标识，这个数值定义为该节点的ID.同时，为了记录相邻节点发送来的信息，每个节点都需要储存一张邻居表.

在簇首形成算法中，节点ri在每轮（簇拓扑结构形成和数据转发、聚集的一个周期）开始时，都以规定的半径r为范围向所有邻居节点发送参加选举的信息，信息内容包括该节点的ID、剩余能量Er和节点的可靠度指标Dp，每个节点按照所有邻居节点发来的选举消息更新自身邻居表［2］，每轮更新一次.

然后，求出每个节点所有邻居节点的平均剩余能量

式（1）中，rj（1≤j≤m，j≠i）代表节点ri半径内的邻居节点，Er表示该节点的剩余能量，m表示所有邻居节点的数量.

每个节点申明成为簇首的时间（从每轮开始到本节点申明成为簇首消息的时刻对应的时间长度）定义为：

式（2）中，k是位于［0.9，1］区间的随机均匀分布的实数值；T是假设确定的簇首选择算法的持续时间；Dp为节点的可靠度指标，即节点的感知效率.

在每一轮中，如果一个节点在“申明成为簇首”的时间t前没有收到所有邻居节点发出的“申明成为簇首”的消息，那么该节点将向邻居节点广播“申明成为簇首”消息，从而成为该区域的簇首.如果该节点在其“申明成为簇首”的时间t前已经收到了邻居节点广播的“申明成为簇首”的消息，则该节点将放弃成为簇首的竞争，由发出广播“申明成为簇首”消息的邻居节点成为该区域的簇首.由此可见，每个节点申明成为簇首的时间越短，也就能越早地成为簇首，

由式（2）可知，只要满足下面2个条件，1个节点将有更高的几率成为簇首：

（2）可靠度指标Dp值越大，即节点的感知效率越高.

1.1.2 算法实现

簇首结构的生成算法如下所示：

1.2 簇内数据转发算法

1.2.1 算法描述

为判断信息量发生变化的情况，在每个Δtj里，节点持续计算其方差值DX，并与较小的δ值进行比较，若DX≥δ，则将新的信息转发给簇首节点用作数据更新；若DX＜δ，说明信息变化不大，则不将该信息向簇首节点转发，簇首节点默认选用前一时间信息进行聚集.簇内转发算法的实现有效减少了不必要的网络通信，提高了有效信息的传送效率，减低了网路损耗，延长了网络寿命.

1.2.2 算法实现

簇内数据转发算法对要转发的数据进行筛选，然后将信息发给簇中的簇头作聚合，以减少不必要的通信量，节省资源.具体算法流程为：

2 仿真实验

2.1 实验方法

分别对LEACH协议、EADEEG协议和IDCP协议进行仿真实验，从簇首结构形成算法和簇内转发算法两方面对3种算法对网络寿命和网络性能的影响进行比较，主要对3种不同算法下节点的死亡时间进行比较.实验中，随着各轮数据收集的进行，节点死亡时间出现越晚，网络寿命越长；同时，网络中各节点死亡时间相差越短，节点能量均衡性就越好，网络整体性能也就越好.

仿真实验在Matlab环境下进行，实验场景设定的监测区域面积为100m×100m，在该区域内部署100个节点，且随机分布，每个节点的初始能量服从（0，1）上的均匀分布，汇集点的位置为（50，200），默认数据分组的长度为500字节，控制消息长度为25字节.

2.2 实验结果

2.2.1 IDCP簇首形成算法对网络性能的影响

图1是簇首形成算法在3种协议下全部节点死亡时间的比较.由图1可以看出，LEACH协议第1个节点的死亡时间和最后1个节点的死亡时间相差达到200轮，各节点能量消耗严重不平衡，个别节点过早消耗掉，只有剩余节点工作，导致网络整体的性能变差.同时，图1中IDCP协议和EADEEG协议全部节点的死亡时间都非常接近，说明在真实环境中，每个节点在上述2种协议情况下，都能够平均承担网路整体的能量消耗，整个网络的寿命也得到延长.IDCP协议和EADEEG协议的性能非常接近，这主要是因为IDCP协议和EADEEG协议的目标都是期望达到均匀的簇内分布.但IDCP协议以t作为簇首竞争的参数，与EADEEG协议相比能够更快、更精准地选择到合适的簇首，并减少了由于簇首选举时间等待而造成的能量消耗.

图1 簇首形成算法节点死亡时间的比较Figure 1 Timing of nodes'death（algorithm of cluster head selection）

2.2.2 IDCP簇内转发算法对网络性能的影响

图2是簇内转发算法节点死亡时间的比较.由图2可以看出，IDCP协议、LEACH协议和EADEEG协议对应的3种算法的第1个节点死亡时间非常接近，但随着时间的增加，IDCP协议中等量节点的死亡时间比LEACH协议要推迟近100～200轮，而比EADEEG协议要推迟几十甚至一百轮，时间越久效果越明显.这主要是因为IDCP协议簇内转发算法将节点感知到的数据进行了筛选，只将更新的数据进行转发，冗余数据则不转发.因此，节点转发的数据量相对减少，有效降低了网路损耗，延长了整个网络的寿命.

图2 簇内转发算法节点死亡时间的比较Figure 2 Timing of nodes'death（forwarding algorithm of cluster）

3 结论

对传统的分簇算法进行改进，提出了IDCP协议，在簇首竞争上，引入改进机制，在实现成本不增加的前提下，能够保证簇首在网络中的均匀分布；同时有效提高了节点加入簇的效率，在簇内数据转发上，引入筛选机制，转发有用数据，屏蔽冗余数据，减少无谓的通信损耗，从而提高了网络的工作效率，延长了网络的生命周期.

［1］ Akyildiz I F，Su W，Sankarasubramanian Y.Wireless sensor networks：A survey［J］.Computer Networks Joumal，2002，38（4）：393－422.

［2］ 刘明，曹建农，陈贵海，等.EADEEG：能量感知的无线传感器网络数据收集协议［J］.软件学报，2007，18（5）：1092－1109.

［3］ 林楠，史苇杭.无线传感器LEACH算法的优化及仿真［J］.计算机仿真，2011，28（1）：178－181.

［4］ Liu Z H，Ma J F.Asymmetric key pie—distribution scheme for sensor networks ［J］.IEEE Transactions on Wireless，2009，3：1366－1372.

［5］ 刘庆，王培康.无线传感器网络的安全分簇路由协议［J］.计算机仿真，2009，26（4）：167－171.

［6］ 孙奎杰.无线传感器网络分簇路由协议研究［D］.吉林：吉林大学，2007：4－10.

［7］ 卿利，朱清新，王明文.异构传感器网络的分布式能量有效成簇算法［J］.软件学报，2006，17（3）：481－489.

Research on data collection protocol based on clustering for wireless sensor network

WANGLiang1，2，FANDehui2
（1.School of Information Science and Engineering，Fudan University，Shanghai 200433，China；
2.Qingdao Technical College，Qingdao 266555，Shandong Province，China）

In order to extend the lifetime of WSN，based on the studying of the traditional typical clustering algorithms of LEACH and EADEEG，a novel data collection protocol named IDCP is proposed by making improvement，and new clustering topology formation algorithm and new data forwarding algorithm are proposed during clustering formation and data forwarding stage.In setting stage，the introduction of the reliability index of the node is proposed.In data forwarding stage，all forwarded information is analyzed by all common nodes in clusters and the information is analyzed according to the expected value.If the analysis result is less than the expected value，information will not be transmitted，otherwise information will be transmitted.Experiments and results analysis show that，the improved algorithm considers the effects on node energy and sense reliability factor properly，it is better than the traditional algorithms in cluster head selection and data forwarding and its network processing ability and performance are both better.

wireless sensor network；clustering；data collection；energy

TP393

A

1671－1114（2011）03－0063－04

2010－10－04

王 靓（1979—），女，讲师，主要从事RFID无限传感器网络方面的研究.

（责任编校 纪翠荣）