一种新的无线传感器网络半动态分簇路由协议

杨凌云, 冯友宏

(安徽师范大学物理与电子信息工程学院,安徽芜湖 241000)

0 引 言

无线传感器网络[1]是由部署在检测区域的大量无线传感器网络节点组成,通过无线通信方式形成的多跳的自组织网络系统,其目的是通过协作感知采集和处理网络中感知对象的信息,并发送给观察者。

在无线传感器网络中,网络层路由协议[2]具有十分重要的地位,从网络的拓扑结构进行分类,一般分为两类:平面路由协议和分簇路由协议。平面路由协议主要从数据传输的角度考虑,每个传感器节点既能搜集发生的事件产生数据,也能作为中继点进行数据转发[3]。这些算法简单,易于实现,能够很好地适应小规模的传感器网络,但是随着网络规模的增大,这些协议就出现了网络开销大和延迟长等缺点。比较常见的平面路由协议有gossiping[4],DD[5]和SAR[6]。在分簇协议中,路由算法基于大量高密度的sensor节点,重点考虑了算法的可扩展性。网络通常被划分成簇,典型的分簇路由协议有LEACH[7],TEEN[8],PEGASIS[9]等,分簇式路由在拓扑管理、节省能量、平衡网络负载、节点移动等方面具有很多优势。

1 LEACH算法

LEACH协议是由MIT的Heinzelman等人[4]提出的一种分层次算法协议,它的核心思想是将所有的节点分为若干个簇,每个簇选举一个簇头,簇头负责接收本簇内所有节点发送的数据,进行数据融合之后,把信息发送给基站。

LEACH的基本思想是通过随机循环选择簇头,将整个网络的能量负载平均分配到每个节点,从而降低网络能量消耗,延长网络生命周期,LEACH的执行是周期循环的,它把整个通信过程分为多轮,每一轮都包括簇的形成阶段和数据传输阶段。在每轮的簇头选择中,LEACH算法为每个节点设置了一个阈值T(n):

但是,LEACH算法也存在着很大缺陷:

(1)LEACH算法中簇头的产生具有极大的随机性,不能保证簇头节点的均匀分布和簇规模的合理性。

(2)簇头之间能量负载不均衡,距离基站比较近的簇头节点因信息传输量大而过早死亡。

(3)用于簇形成和簇头选择的能量消耗在整个通信过程中的消耗不可忽略,频繁的簇形成和簇头选择会使整个网络的传输速率下降,同时加速网络节点的死亡。

2 半动态路由算法描述

2.1 无线传感器网络分簇模型[11]

(1)无线传感器网络是由M个随机部署在变成为N的正方形感知区域内的传感器节点构成。

(2)基站远离传感器网络节点区域,并且不考虑能量损耗。

(3)传感器网络中的节点是同构的,具有相同的处理信息和通信能力,节点初始能量相同且有限。

2.2 算法描述

节点的初始位置是未知的,在进行分簇之前,可以根据节点接收到的基站能量的大小判断自身相对于基站的距离和现在所处位置,自身位置信息可通过某种定位算法得到,邻居位置可以通过邻居节点交换信息得到[12]。基站根据接收到节点能量的大小和确定的位置信息,确认簇的大小和簇头的位置等信息,基本原则就是距离基站较近的簇较小,防止近簇头能量的过快消耗。同时,还要考虑簇头在整个网络的均匀分布性,簇头既不能过于集中,又要防止较远节点无法正常加入簇。

2.2.1 簇头的选择

首先是在簇头个数的选择上,最优簇头选择的计算公式为:

εfs自由空间信号放大倍数;

d2簇头到基站的距离。

同时结合具体的网络实用环境,在仿真软件重进行能耗分析可以发现,在通常情况下簇头的个数占整个网络中节点综述的p=5%为最佳。在簇头选择上,文中同时考虑剩余能量、已担任簇头时间、临节点的接近程度等因素的影响。

式中:Eremain节点剩余能量;

这里产生簇头的阈值就可以变换为:

式中:Emax节点的初始能量值;

Eremain节点剩余能量值;

tch已经当选过簇头的次数;

2.2.2 簇的形成

在簇的形成过程中,要加入节点相对于基站的地理位置对簇大小的影响,文中利用非均匀的竞争半径,使得靠近汇聚点的成员数目相对较小,从而簇头能够节约能量以供数据转发使用,达到均衡簇头能量消耗的目的,节点发送m bit消息所消耗的能量公式为:

在簇内,LEACH节点加入簇的时候仅考虑节点到簇头的最优化,决定加入哪个簇。也可以使用CMMBCR协议对重叠节点和簇头节点之间建立一条能量之和最小的路由,在充分考虑了簇内邻居节点的能量和距离分布信息的前提下优化簇头的选择。

在簇的形成过程中,需要在考虑减少拓扑生成过程中的控制报文开销,以及降低拓扑结构变动的频率,减少网络通信开销的同时均衡网络能量消耗,延长无线传感器网络的寿命。文中提出的半动态分簇路由就是这种思想很好的体现。在进行完簇的形成和簇头的选择后,簇的大小范围基本保持不变,只是在固定的簇内进行簇头的选择,所有节点在簇头进行完传输轮数之后,仅更新簇头节点信息,而不必更换邻居节点信息,减少非数据信息的通信量。如果簇内有节点死亡,则允许其它节点的加入,直至簇内节点死亡个数占簇内节点总个数的30%,基站根据网络中存活节点个数等信息重新进行簇和簇头的选择。

2.2.3 簇的路由

在分层路由协议中,簇的路由主要分为簇内路由和簇间路由,簇内路由一般采用单跳形式,便于管理,对于簇半径较大的簇,可以采用两跳形式实现。在簇间、簇头之间的传送一般采用多跳形式,节约簇能量的消耗。但无论是簇内路由还是簇间路由,所有与基站的数据信息传送都要通过簇头进行传送,特别是靠近基站的簇头,通信量非常大容易死亡。

文中提出在路由通信采用双簇头形式(分为主簇头和副簇头,Head=0,Head=1),分别进行簇内节点信息的数据融合和簇头之间的信息传送,前面在簇的形成过程中,我们仅说明了如何进行主簇头的选择,在主簇头确定之后,主簇头根据节点距离自己的远近选举最近的节点作为副簇头,并通知簇内节点。节点间的簇头(包括主簇头和副簇头)组成类似与双环的路由结构,主簇头主要负责簇内节点的信息处理和传送,副簇头负责簇间节点信息的传送,同时在主簇头出现死亡或者不能正常工作等情况后,副簇头能暂时直接代替主簇头工作,保证通信的流畅性和信息的不丢失。这不仅能减少主簇头的能量消耗,也能保证网络信息传送的安全性,减少第一个节点的死亡时间,延长整个网络的寿命。

3 算法分析和仿真

为了比较LEACH及其改进算法的性能,将这两个算法在Matlab中仿真实现。仿真假设无线传感器网络为一个边长M=100 m的正方形区域,节点数N=100个,每个节点的初始能量E0=2 J,基站远离无线传感器网络中的所有节点。每个信号的长度为1 000 bit,模型能量参数为:Eelec=50 nJ/bit。Efs=10 pJ/bit/m2,Emp=0.001 3 pJ/bit/m4。在仿真实验中,若节点的剩余能量为0,则我们认为节点已经死亡。随着工作轮数的变化,两种路由算法的网络能量消耗以及网络死亡节点数的性能比较如图1和图2所示。

在无线传感器网络中,第一个死亡节点出现的时间是衡量网络寿命的一个重要参数,为了提高网络性能,应尽量推迟第一个死亡节点出现的时间。

图1 网络生命时间比较

图2 网络总能耗比较

从图1中可以看出,LEACH算法的第一个死亡节点在368轮,在1 700轮之后节点全部死亡。而改进后的半动态路由算法的第一个死亡节点出现在840轮,节点全部死亡出现在2 450轮,可以看出,半路由协议有效地延长了整个无线传感器网络的寿命。

改进后的算法每一轮的总能量变化趋势都比LEACH算法慢,这是由于半动态路由算法减少了网络拓扑结构变化的能量消耗。同时,根据节点的分布情况,建立更有效、更合理的分簇方式,保证簇头在整个网络中的均匀分布,簇间通信采用副簇头协助传输的通信方式,有效节省了总能耗。

4 结 语

LEACH算法是无线传感器网络中分层路由的一个很具有代表性的算法,它使资源有限的无线传感器网络得到了广泛的应用,文中就是在LEACH算法的基础上提出了半动态路由算法,改进了LEACH算法中簇的形成,簇头在网络中的均衡分布,同时尽量减少网络拓扑结构的变化损耗等非信息损耗,均衡网络节点能量消耗,延长网络使用寿命。仿真结果表明,新算法基本达到了预想的目的。

[1] 崔 莉,鞠海玲.无线传感器网络研究进展[J].计算机研究与发展,2005,42(1):163-174.

[2] 高传善,杨 珉,毛迪林.无线传感器网络路由协议研究综述[J].世界科技研究与发展,2005(8):1-8.

[3] 郭永玲,王潜平.无线传感器网络分簇路由协议的研究[J].计算机与信息技术,2007(9):57-58.

[4] Hedetniemi S,Liestman A.A survey of gossiping and broadcastingin communication networ-ks[J].Networks,1988,18(4):319-349.

[5] Intanagonwiwat C,Govindan R,Estrin D,et al.Directed diffusion for wireless sensor networking[J].IEEE/ACM Trans.On NetWworking,2003,11(1):2-16.

[6] Sohrabi K,GAO J,Ailawadhi V.Protoco-ls for self-organization of a wireless sensor network[J].IEEE Personal Communications,2000,7(5):16-27.

[7] A Kyildizif,Suw Sankara Subramaniamy,Ca Yirc E.A survey on senso r netwo rk s[J].IEEE Communi2cations Magazine,2002,40(8):32-35.

[8] M anjeshwar A,Grawal D P.TEEN:a protocol for enhanced efficiency in wireless sensor networks[C].//Proc.of the 15th Parallel and Distributed Processing Symp.San Francisco:IEEE Computer Society,2001.

[9] Lindsey S,Raghavendr A C S.PEGASIS:Power-Efficient gathering in sensor information systems[C].//Pro.of the IEEE Aerospace Conference Proceedings,2002.

[10] WendiRabinerHeinzelman,Anantha Chandrakasan,Hari Balakrish2nan.Energy-efficient communication protocol for wireless microsensor network[C].//The proceedings of the Hawaii International Conference on Sys2tem Science,IEEE,2000:14-17.

[11] Ding W,Iyengar S S,Kannan R,et al.Energy equivalenceroutingin wireless sensornetworks[J].Microprocessors and Microsystems,2004,28(8):467-475.

[12] Chang J H,Tassiulas L.Maximum lifetime routing in wireless sensor networks[J].IEEE/ACM Transactions on Networking,2004,12(4):609-610.