潘雪峰，李腊元，，何延杰

（1.武汉生物工程学院 计算机与信息工程系，湖北 武汉430415；2.武汉理工大学 计算机科学与技术学院，湖北 武汉430063）

0 引 言

无线传感器网络的应用较为广泛，其中一个重要的研究方向就是路由协议的研究与分析［1］。路由协议对无线通信模块的能量消耗起着关键影响。路由协议的研究一般放在路由机制和数据驱动上，由此划分了阶段，并出现了一些优秀的路由算法［2－3］。

针对LEACH协议和PEGASIS协议的不足，给出了改进方案。在簇首选取的过程中经过公式推导，找出最优簇首的数量与参数间的关系；簇的建立的过程中给出了算法流程；并对簇间路由中路由树建立的过程进行了描述。最后使用NS2.27进行了仿真，并给出了数据分析及结论。

1 具有代表性的无线传感器网络路由协议的分析

无线传感器网络路由协议所包含内容较多，但其核心内容是选择簇首节点、形成簇、簇间数据的路由［4－5］。分簇方式种类较多，一个簇能够使用不同的数据交换方式［6］。同时，由于选择簇首节点机制的不同，算法也不同［7－8］。课题分析研究了两种典型的层次路由协议，它们属于分布式算法。

1.1 LEACH协议 （低功耗自适应簇分层型协议）

在LEACH协议中，形成簇时使用自我组织、自动适应性、随机选择的机制［9］。图1描述了无线传感器网络中的节点分为5个簇，使用的是LEACH协议，图中簇首节点用黑色圆圈表示，非簇首节点用白色圆圈表示。协议随机选择簇首节点，使每个传感器节点平均分配了整个网络的能量消耗［10］。

图1 低功耗自适应簇分层型协议的簇结构

低功耗自适应簇分层型协议的执行过程是周而复始的，每一个周期又分为很多轮，每轮中簇首的选择是随机的［11－12］。簇建立阶段和稳定传输阶段是一轮中的两个重要组成部分。

从以上分析看出LEACH协议具有以下不足：①使用簇首节点随机轮换法虽然能降低能量消耗，但反复重建簇还是会消耗更多的能量；②不同的簇内，簇首节点与非簇首节点的距离各不相同，通信过程中簇首的能量消耗增多；③由于簇首节点需要与汇聚节点通信、完成数据融合等工作，能量消耗增多。

1.2 PEGASIS协议

PEGASIS协议在进行链接时，节点采用链式结构。使用PEGASIS协议时，首先根据接收的信号的强度，区分邻居节点距离的远近，在寻找距离最近邻居的时，为了使信号仅有该邻居接收，还要调整发送信号的强度。接下来，每个节点向链路中邻居节点发送随机数据，并且只选择一个节点作为链首向汇聚节点传输数据［13－15］。

从以上分析看出PEGASIS协议有以下不足：①协议设计链路过于理想化，将汇聚节点与簇首节点通信时，能够直接通信，在实际情况中，簇首节点需要用多跳的方式与汇聚节点通信；②协议对各节点能量的设计有所不足，假定它们的能量基本相当，在能量耗尽的情况下，它们可能会全部脱离网络或在网络中消失；③协议对拓扑结构的设计有所不足，节点要获取周围节点的状态及能量，这样便于收发数据，但拓扑结构同时也会受到影响；④设计协议时，未引入备用链首节点，链路如果过长，就会产生数据发送接收的滞后。

2 EBLP协议的设计

2.1 改进切入点

通过对低功耗自适应簇分层型协议和低功耗传感器信息系统协议的分析，找出这两个协议的不足，从选择簇首节点、形成簇、簇间路由等方面对LEACH协议进行了改进。给出了以下改进的切入点：①减少簇重组次数，从而降低了簇多次反复形成而损失的能量；②改变选择簇首节点的算法，考虑决定能耗的参数的影响和减小簇首节点之间的距离；③调整簇和簇成员的个数，使得簇首的负载均衡，簇的划分合理；④在建立路由树的过程中，要考虑簇首节点与汇聚节点的距离远近，还要考虑簇首节点的能量，簇首节点采用多跳通信的方式，可以解决一些簇首节点因离汇聚节点过远，在采用单跳收发数据时，消耗能量太大的问题。

2.2 具体描述

2.2.1 簇首选取

在LEACH协议中选取簇首时，存在着一定的不足，由于簇首是在簇内选取出来，所处的位置相对不固定，如果簇首节点位置相对集中，某些节点会被孤立，出现未被分到任何簇中的情况，这时候网络就会局部不连通。与此同时，簇首节点位置相对集中，还会使系统内部重复数据过多，收发这些数据需要更多的能量，如果能减少这些重复的数据，就能在降低能耗。设计的EBLP算法近似求出簇首节点个数较为合理的值，结合无线传感器网络中的节点分布、规模大小，求出簇首节点之间间隔的最小值，然后根据式 （1）中改进后的阈值T （n）来选择簇首。

式中：p——选为簇首的节点占所有总节点数的百分比，r——所经历的轮数，rs——一直没被选为簇首的轮数，En＿current——当前能量，En＿initial——初始能量。如果节点被选为簇首，rs便重置为0。

簇首节点消耗的能量会受到各种因素的影响，由于簇首节点的主要工作是与汇聚节点、簇内节点进行通信，因而簇首节点的能耗主要用于与簇内成员进行数据收发消耗的能量 （N／K－1）Eelec，以及与汇聚节点通信消耗的能量（Eelec＋εamp（）），其中簇的数量用K表示，接收或发送数据所需的能量用Eelec表示，簇首节点到汇聚节点的距离用dtoBS表示，簇首与汇聚节点通信时的无线信号传播参数为εamp。簇内成员节点在一轮中消耗的能量EnonCH为：（Eelec＋εfsE（）），其中成员节点到簇首节点的距离用dtoCH表示，成员与簇首通信时的无线信号传播参数为εfs。在一轮中每个簇消耗的能量Ecluster包括两部分，分别是一个簇首所需能量ECH，及簇内成员所需能量 （N／K－1）EnonCH。因此在一轮中K个簇消耗的能量的累加和可使用全网消耗的能量Etotal来表示，代入前面的表达式后可得到：Etotal＝KEcluster＝K （N／K－1） （2Eelec＋εfsE））＋ （KEelec＋KεampE（））；考虑到K的值较大，那么K－1的值驱近于K的值，即可得到

假设模拟区域为正方形区域，其边长为A，则无线传感器网络覆盖的面积是A2，很容易得到，网络中的一个簇得到的平均面积应是A2／K。簇内非簇首节点分布于簇首节点周围，构成一个圆形，得到半径为r＝A／的圆，根据半径的值能够算出圆心与圆内的点的距离平方的平均值，即数学期望为：E （） ＝ A2／2Kπ，同时，E（）与K无关，将其用常量L表示，因此式 （2）可变为

为了求出Etotal的最小值，对式 （3）左右两边同时对K求导数，令结果为0，这时就可以求出最优的K值

通过推导出的式 （4）找出结论：Kopt与N、A、dtoBS有关。为得到最优簇首数，可在设置网络时设置时，给出这几个具体的参数值。

2.2.2 簇的建立

当选取好簇首节点之后，为了建立簇，簇首会向周围的非簇首节点发出簇首特有的信号，周围的非簇首节点对接收到的信号的强弱进行判断，一般加入信号强的簇首节点的那一簇中，并控制节点加入的数量，控制簇的大小。如果簇首同意周围的非簇首节点加入簇中，会向该非簇首节点发送允许加入的信号，否则就发送拒绝加入信号。待簇建立完成，通过一条链路将簇首和成员节点链接，链接是采用贪婪算法，链的形成过程与PEGASIS协议相同。这样一来，在每个簇中的节点数会比要比整个网络中的节点少很多，传输的位置信息也相对较少，使得传输数据的延迟也不很明显。

2.2.3 簇间路由

汇聚节点一般在无线传感器网络外部，与无线传感器网络所在的区域有一定的距离，在簇首节点都与汇聚节点进行数据交互的过程中，根据前面的推导，系统中节点的能耗将与它们之间距离的四次方成正比。在设计LEACH协议时，有着一定的不足，体现在簇间路由中，就是簇首在与汇聚节点进行信息交换时，对簇首的当前能量考虑不足，簇首可能会因能量损耗过快，能量耗尽而停止工作。为了解决上述的不足，同时还要考虑离汇聚节点较远的簇首的能耗，在设计EBLP协议时，采用了多跳的方式，由此只需少量的簇首与汇聚节点直接通信。

簇首间层次路由树的建立过程如图2所示，其中M为汇聚节点，A、B、C、D均为无线传感器网络中的簇首节点。①M首先向整个WSN发出一个消息，能量设为∞，设置跳数为0。②收到这个消息的簇首，加上汇聚节点一起构造路由树，路由树中的根节点是汇聚节点，路由树中叶子节点是簇首节点，将自身的剩余能量的值保存为包中的能量值，将收到的数据包经过的跳数值增加1，并转发此广播包给周围的簇首。③由于B、C两个簇首节点距离近，B会先收到来自于C的广播包 （1，EC），后收到来自于A的广播包 （1，EA）。但是由于A、C两节点剩余能量不同，且EA＞EC，虽然两者的跳数值都为1，但是节点B会选择剩余能量较大的节点作为其父节点，因此构造路由树时，节点A是节点B的父节点。依照上述规则可构造出路由树的结构。

图2 簇首间路由树

3 仿真实验和结果分析

3.1 仿真环境

为了验证EBLP协议的有效性，在Linux下进行仿真实验，实验环境为：NS2.27。选取99m＊99m的正方形区域为仿真实验区域，在仿真区域中随机地分布着99个节点，设置汇聚节点位置在坐标 （59，179）处。如图3所示。

图3 EBLP算法的网络拓扑

3.2 设置仿真参数

在测试EBLP协议的仿真前，应构建仿真环境、设置仿真参数，以上工作需要写入脚本文件。主要脚本如下：

.／ns tclfile／eblp／wsn.tcl－sc setting／nodescen

－rp eblp＼

－x 99＼

－y 99＼

－nn 99＼

－stop 1200

－eq＿energy 1 ＼－init＿energy 2＼－filename result－bs＿x 59＼－bs＿y 179＼

3.3 仿真结果及分析

3.3.1 最优簇首数的仿真

在无线传感器网络区域中，在 （59，99）和 （0，0）的位置的簇首结点，距离汇聚节点 （59，179）的距离dtoBS的值分别是80至188.4，同样也选取99m＊99m的正方形区域为仿真实验区域，在仿真区域中随机地分布着99个节点，εfs为10pJ／bit／m2将，εamp为0.0013pJ／bit／m4，将以上参数代入网络最优簇首个数的计算式 （4）中，可得最优簇首数的值在2到5.5间。仿真后，得出了簇首数目与平均每轮能耗的关系如图4所示。

图4 簇首数与能耗的关系

3.3.2 能量消耗的仿真

在图5中可以看到全网的能耗的比较，可以看出：实线为EBLP协议，两条虚线分别是LEACH协议和PEGASIS协议；在网络在前180轮，使用EBLP协议的无线传感器网络能耗高于LEACH和PEGASIS；在180轮后，使用EBLP协议的无线传感器网络能耗略低于LEACH和PEGASIS。

根据图5可以得出以下结论：由于EBLP协议要进行簇首选择、簇的建立和簇间路由树的建立，而该过程都与簇首有关，其它非簇首节点协同工作，因此前180轮EBLP协议消耗的能量较多；但是网络运行稳定后，由于簇间使用了路由树来多跳通信，能量消耗相对较少。

4 结束语

通过对LEACH协议和PEGASIS协议进行了重点的分析，总结出这两种协议各自的优缺点，针对LEACH协议生成非均匀的簇造成能量损耗的问题，以降低能量损耗为研究目的，结合PEGASIS协议的特点，从选择簇首节点、形成簇、簇间路由等方面对LEACH协议进行了改进。经过理论分析和仿真实验，对该协议的性能进行测试。可以得出结论，整个无线传感器网络的能量消耗上，EBLP路由算法要优于LEACH协议和PEGASIS协议。

图5 全网能耗比较

［1］LI Shuhua，LIU Zhenyu，LI Yingqiu.Energy adaptive clustering in wireless sensor network routing protocol［J］.Computer Engineering and Design，2010，31 （3）：504－507 （in Chinese）.［李树华，刘振宇，李迎秋.能量自适应的无线传感器网络分簇路由协议 ［J］.计算机工程与设计，2010，31 （3）：504－507.］

［2］LI Chengfa，CHEN Guihai，YE Mao，et al.A clustering based on non－uniform routing protocol for wireless sensor networks ［J］.Journal of Computers，2007，30 （1）：27－36 （in Chinese）.［李成法，陈贵海，叶懋，等.一种基于非均匀分簇的无线传感器网络路由协议 ［J］.计算机学报，2007，30（1）：27－36.］

［3］GONG Haigang，LIU Ming.DEED：A wireless sensor network energy－efficient data communication protocol ［J］.Chinese Journal of Electronics，2005，33 （8）：1392－1396 （in Chinese）.［龚海刚，刘明.DEED：一种无线传感器网络中高效节能的数据通信协议 ［J］.电子学报，2005，33 （8）：1392－1396.］

［4］SHEN Bo，ZHANG Shiyong.Wireless sensor network clustering routing protocol ［J］.Journal of Software，2006，17（7）：1588－1600 （in Chinese）.［沈波，张世永.无线传感器网络 分 簇 路 由 协 议 ［J］. 软 件 学 报，2006，17 （7）：1588－1600.］

［5］SUN Yugeng，ZHOU Yin，BIAN Guinian，et al.Wireless sensor networks a network of energy efficient clustering algorithm ［J］.Chinese Journal Sensors and Actuators，2007，20（2）：377－381 （in Chinese）.［孙雨耕，周寅，边桂年，等.无线传感器网络中一种能量有效的分簇组网算法 ［J］.传感技术学报，2007，20 （2）：377－381.］

［6］Muruganathan S D，MA D C F，Bhasin R I，et al.A centralized energy－efficient routing protocol for wireless sensor networks［J］.IEEE Communications Magazine，2005，43（3）：8－13.

［7］WANG Chunlei，CHAI Qiaolin，WANG Hua，et al.Based on cluster energy efficient routing algorithm for wireless sensor networks ［J］.Journal of Computer Applications，2007，27 （2）：342－345（in Chinese）.［王春雷，柴乔林，王华，等.基于分簇的无线传感器网络节能路由算法 ［J］.计算机应用，2007，27 （2）：342－345.］

［8］TAO Xiaoling，WANG Guifeng，WANG Yong.Dijkstra for wireless sensor networks based on clustering routing algorithm［J］.Computer Engineering and Design，2010，31 （17）：3807－3811（in Chinese）.［陶晓玲，王桂凤，王勇.基于Dijkstra的无线传感器网络分簇路由算法 ［J］.计算机工程与设计，2010，31 （17）：3807－3811.］

［9］WU Zhenhua，YIN Zhijun.WSNs based on optimization of non－uniform cluster radius clustering routing ［J］.Computer Engineering and Design，2010，31 （15）：3374－3378 （in Chinese）.［吴振华，尹志军.基于优化簇半径的 WSNs非均匀分簇路由 ［J］.计算机工程与设计，2010，31（15）：3374－3378.］

［10］NIU Kang，DENG Yaping，MAN Wen.Low－latency data fusion algorithms for wireless sensor networks ［J］.Computer Engineering and Design，2010，31 （12）2710－2712 （in Chinese）.［牛康，邓亚平，满文.低时延的无线传感器网络数据融合 算 法 ［J］.计 算 机 工 程 与 设 计，2010，31 （12）2710－2712.］

［11］TANG Yong，ZHOU Mingtian，ZHANG Xin.Routing protocol for wireless sensor networks research progress ［J］.Journal of Software，2006，17 （3）：410－421 （in Chinese）.［唐勇，周明天，张欣.无线传感器网络路由协议研究进展［J］.软件学报，2006，17 （3）：410－421.］

［12］WU Chenwen，WANG Tiejun.NS2－based model of wireless sensor network routing protocol design and study ［J］.Journal of Lanzhou Jiaotong University，2007，26 （1）：1－5 （in Chinese）.［吴辰文，王铁君.基于NS2无线传感器网络路由协议模型的设计与研究 ［J］.兰州交通大学学报，2007，26（1）：1－5.］

［13］FU Jun，ZHANG Xiaofeng.A cluster head selection model based on wireless sensor network clustering algorithm ［J］.Journal of Computer Applications，2007，20 （8）：1856－1859（in Chinese）.［傅军，张晓锋.一种基于簇头选择模型的无线传感器网络分簇算法 ［J］.传感技术学报，2007，20 （8）：1856－1859.］

［14］LIU Qin，WANG Fubao，MA Junyan，et al.A wireless sensor network effective distributed clustering ［J］.Computer Application，2007，27 （1）：4－6（in Chinese）. ［刘琴，王福豹，马峻岩，等.无线传感器网络中一种有效的分布式簇划分算法 ［J］.计算机应用，2007，27 （1）：4－6.］

［15］JIANG Shaofeng，YANG Minghua，SONG Hantao，et al.Sensor networks centroid－based distributed clustering algorithm ［J］.Journal of Computer Applications，2007，27（1）：1－3 （in Chinese）.［姜少峰，杨明花，宋瀚涛，等.传感器网络中一种基于质心的分布式成簇算法 ［J］.计算机应用，2007，27 （1）：1－3.］