一种基于无线传感器网络分簇路由的改进算法

郭文强， 周 强， 侯勇严， 王阿娟

(陕西科技大学 电气与信息工程学院， 陕西 西安 710021)

0 引言

无线传感器网络(Wireless Sensor Network，简称WSN)是由一组传感器以自组织方式构成的无线网络,它由一定数目的传感器节点构成[1].WSN综合了传感器技术、嵌入式计算技术、分布式信息处理技术和无线通信技术，能协作地实时监测、感知和采集节点部署区域的各种环境或监测对象的信息(如光强、温度、湿度、噪音和有害气体浓度等物理现象)，并对这些数据进行处理，获得详尽而准确的信息，通过无线网络最终发送给观察者[2-4].因而WSN具有十分广阔的应用前景，在军事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、危险区域远程控制等许多领域都具有重要的科研价值和巨大的实用价值，并成为近年来公认的热点研究领域[5-8].

无线传感器网络中，节点的电源能量是有限的,所以基于能量角度设计有效的路由协议,是确保WSN网络性能的关键技术之一.本文对当前传感器网络路由算法进行了分析，针对具有不同初始能量节点的异构WSN，提出了改进型SEP(Stable Election Protocol，稳定选举协议)路由算法，通过合理加权选择簇头，使剩余能量高的成为簇头的概率加大、推迟了网络第一个节点的死亡时间，延长了网络运行的稳定期.

1 LEACH路由算法

无线传感器网络是一种由大量小型传感器所组成的网络.这些小型传感器一般称作传感器节点.网络中一般也有一个或几个基站(Sink)用来集中从小型传感器收集的数据.在WSN中，节点需要完全以自组织的形式构成自治型网络，并且能够工作在无人值守的恶劣环境当中.

LEACH(Low-energy Adaptive Clustering Hierarchy，低功耗自适应聚类分层)是一个提出较早的基于分簇思想的WSN层次路由算法[9].与传统网络中网关节点的能量较充足相比，WSN中的节点能量有限，故不能用固定簇头节点作为网关.LEACH从WSN中随机选择少数节点作簇头，考虑到网络中各节点能耗的平衡性，节点轮流作为簇头，使网络不会因少数节点先耗尽能量而造成网络瘫痪.

1.1 能耗模型

假设发送的能量包括信号处理与功率放大两部分,接收的能量仅用于信号处理, 使用接近中心的距离d0作为参考, 并且假设两节点之间的距离d小于d0时采用自由空间模型,大于等于d0时采用多径衰减模型[10].LEACH 算法的无线信道能量模型如图1所示.

图1 WSN信道能量模型

图1中当两个距离为d的节点之间发送l比特数据时, 发送和接收所消耗的能量分别为:

ETx(l,d)=ETx-ele(l)+ETx-amp(l,d)

(1)

ERx(l)=lEelec

(2)

其中，Eelec是信号处理所需能量, 由数字编码、调制、滤波和扩展信号等因素决定；εfs是自由空间信道模型下功率放大器的能量消耗常数；εmp是多径衰减信道模型下功率放大器的能量消耗常数,它们由放大器功耗、发射距离和接收误码率等决定.

1.2 路由协议的分析

LEACH定义了“轮”(round)的概念，每一轮由簇头建立和稳定工作两个阶段组成.前者是LEACH算法实现的关键，后者是数据传输的保证.LEACH主要通过随机选择聚类首领,平均分担中继通信业务来实现网络服务.为了避免额外的处理开销,稳定工作阶段一般持续相对较长的时间.

在簇头建立阶段，传感器节点生成0与1之间的随机数rand.如果随机数小于阈值T(n)，则该节点成为这一轮的一个簇头.用G表示最后的1/p轮中没有被选为簇头的节点集合，p表示簇头节点浓度(如5%)，则T(n)为：

(3)

其中，r是当前的轮数；G是在前1/p轮中未充当过簇头节点的集合.

当簇头选定之后，簇头节点主动向网络中节点广播自己成为簇头的消息(ADV_CH).接收到此消息的节点，依据接收信号的强度，选择它所要加入的簇，并发消息通知相应的簇头(JOIN_REQ).基于时分多址(Time Division Multiple Address，简称TDMA)的方式，簇头节点为其中的每个成员分配通信时隙，并以广播的形式通知所有的簇内节点.这样保证了簇内每个节点在指定的传输时隙进行数据传输，而在其他时间进入休眠状态，减少了能量消耗.在稳定工作阶段，节点持续采集监测数据，在自身传输时隙到来时把监测数据传给簇头节点.簇头节点对接收到的数据进行融合处理之后，发送到Sink节点，这是一种减小通信业务量的合理工作模式.持续一段时间以后，整个网络进入下一轮工作周期，重新选择簇头节点.

LEACH协议采用动态转换簇头的方法来平均网络节点的能量消耗，使因能量耗尽而失效的节点呈随机分布状态.因而与一般的多跳路由协议和静态簇算法相比，LEACH可以将网络生命周期延长15%.LEACH的分簇机制可降低网络的整体能耗，延长网络生存时间；在簇内节点间通常采用TDMA编码[11]，在簇头与基站间采用CDMA编码，保证信息有效传输；数据采集和簇头节点都是周期性的，网络适合监测连续变化事件.

2 SEP路由算法

LEACH路由算法假定所有的节点都配备了相同数量的能量，因此，它们不能充分利用节点异质性的存在.为了延长网络稳定期，SEP协议中路由算法对能源消耗进行约束，试图均衡能源消耗.SEP协议中高级节点(初始能量高的节点)成为簇头的概率大于普通的节点(初始能量低的节点).

SEP协议假定每个节点通过通信知道网络的总能量，然后根据节点的剩余能量计算出其成为簇头的最佳概率.运行之初根据经验值设定了最优概率Popt，并引入Pnrm为普通节点加权选举的概率，Padv为高级节点加权选举的概率[6].其中：

(4)

(5)

其中，a为高级节点的初始能量多于普通节点初始能量的倍数，m为高级节点在总节点数中所占比例.普通节点与高级节点成为簇头的阈值分别为T(snrm) 和T(sadv)，计算公式如下：

(6)

(7)

其中，r是当前轮数；G1和G2是相应的在前1/p轮中未充当过簇头节点的集合.

3 改进型SEP路由算法

在SEP路由算法中的第r轮簇头选举时，若存在关系随机数randr

(8)

其中，Er,left为第r轮时节点的剩余能量;Eini为节点的初始化能量.则第r轮簇头选举时，随机数按下式确定：

randr=rand*Cr

(9)

分析可知: 参数Cr为一个考虑节点剩余能量因素的动态变量.当节点剩余能量较大，对应的随机数randr会相应地减小，从而提高了其当选为簇头的概率，减少了普通节点当选为簇头引起的因能量过早耗尽而造成的数据丢失.

改进型SEP协议能够适用于节点能量不同的网络，可以有效避免能量过低的节点当选为簇头，协议可以延长第一个节点的死亡时间，即网络稳定期，而这对于许多网络应用来讲至关重要.

4 仿真实验与性能分析

4.1 实验环境

为了验证本文提出的改进型SEP协议的有效性，在相同无线传感器网络条件下分别采用LEACH协议、SEP协议和改进型的SEP协议进行了大量的仿真对比实验.在PC 机(奔腾 2.5GHz CPU, 2G 内存)上采用Matlab 7.1完成如下仿真实验.

具体仿真环境参数如下: 区域大小为100 m×100 m 正方形区域，节点数量为100，基站在网络区域中心.普通节点能量Eo为0.5 J；高级节点所占比例m为0.1，其所含能量为普通节点的(1+a)倍.实验中a取1.

数据包和控制包长度为4 000 byte，Eelec为50 nJ /bit，εfs为10 pJ/( bit /m2) 、εmp为0.001 3 pJ/( bit /m4)，节点数据处理能耗为5 nJ /bit /singal.

4.2 性能分析

图2所示为WSN运行LEACH协议初始节点状态.图中“x”代表基站，“+”代表高级节点，“o”代表普通节点，“*”代表节点为簇头，“·”代表已经死亡节点.

图2 LEACH协议运行初始网络节点状态

WSN分别运行LEACH协议、SEP协议和改进型SEP协议至第1 050轮时节点状态如图3至5所示.

图3 LEACH协议运行1 050轮时网络节点状态

图4 SEP协议运行1 050轮时网络节点状态

图5 改进型SEP协议运行1 050轮时网络节点状态

对比可知：协议至第1 050轮时，SEP协议存活节点的数量明显多于LEACH协议(“·”节点相对较少).这是由于在LEACH协议中每个节点成为簇头的概率是完全一样的，而普通节点由于初始能量较少所以死亡的可能性也更大；改进型SEP协议存活节点明显多于SEP协议，是因为改进型SEP算法能够在能量异构的网络模式下，使剩余能量较高的节点当选为簇头的概率得以增加，有效地均衡了网络中的节点能耗.

图6 不同协议下网络节点存活数量对比

WSN分别运行LEACH协议、SEP协议和改进型SEP协议10次，网络中平均存活节点数对比情况如图6所示.分别采用LEACH算法、SEP算法和改进型SEP算法后，网络中出现第1 个死亡节点的代数分别为902、1026和1078.实验表明，改进型算法明显地延长了网络中出现第1 个死亡节点的时间，延长了网络的生命周期，从而提高了网络的性能.

5 结束语

通过对无线传感器网络路由协议中的LEACH算法和SEP算法的机理分析，提出了改进型SEP算法.大量实验结果表明，改进型SEP算法在能量异构的网络模式下，通过改进选举簇头机制，提高了剩余能量较高的节点当选为簇头的概率，增加了选举簇头节点的合理性，有效地均衡了网络中的节点能耗，提高了网络中能量的利用效率，从而更好地延长了网络的生命周期.

[1] K.W.Chin.Pairwise:A time hopping medium access control protocol for wireless sensor networks[J].IEEE Transactions on Consumer Electronics,2009,55(4):1 898-1 906.

[2] P.Baldi,L.D.Nardis,M.D.Benedetto.Modeling and optimization of UWB communication networks through a flexible cost function[J].IEEE Journal on Selected Areas in Communications,2006,20(9):1 733-1 744.

[3] N.Saputro,K.Akkaya,S.Uludag.A survey of routing protocols for smart grid communications[J].Computer Networks,2012,56(11):2 742-2 771.

[4] A.A.Cardenas,T.Roosta,S.Sastry.Rethinking security properties, threat models, and the design space in sensor networks:A case study in SCADA systems[J].Ad Hoc Networks,2009,7(8):434-1447.

[5] 陶志勇，胡 明，方宁.无线传感器网络的分簇时间同步算法研究[J].计算机测量与控制,2012,20(7):2 010-2 013.

[6] 郭文强,张玉杰,侯勇严,等.无线传感器网络在环境监测系统中的设计与应用[J].陕西科技大学学报，2012,30(4):81-84,89.

[7] 蹇 强，龚正虎，朱培栋，等.无线传感器网络MAC 协议研究进展[J].软件学报,2008,19(2):389- 403.

[8] T. Westeyn,G.Abowd,T.Starner,et al.Monitoring children′s developmental progress using augmented toys and activity recognition[J].Personal and Ubiquitous Computing,2012,16(2):169-191.

[9] 吕 涛，朱清新，张路桥.一种基于LEACH协议的改进算法[J].电子学报, 2011,39(6)：1 405-1 409.

[10] W.B.Heinzelman，A.P.Chandrakasan，H．Balakrishnan. An application-specific protocol architecture for wireless micro-sensor networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660- 670．

[11] S.Coleri-Ergen,P.Varaiya.Pedamcs:Power efficient and delay aware medium access protocol for sensor networks[J].IEEE Trans.on Mobile Computing,2006,5(7):920-930.