改进的无线传感器网络非均匀分簇路由算法*

张文梅,廖福保

(1.广东农工商职业技术学院机电系,广州 510507;2.广东农工商职业技术学院计算机系,广州 510507)



改进的无线传感器网络非均匀分簇路由算法*

张文梅1,廖福保2*

(1.广东农工商职业技术学院机电系,广州 510507;2.广东农工商职业技术学院计算机系,广州 510507)

针对无线传感器网络中不均匀分簇引起能量空洞的问题,提出了改进的无线传感器网络非均匀分簇路由算法。该算法先根据节点剩余能量、节点到基站的距离、节点“度”和节点到簇头的距离等因素选举簇头;没有成为簇头的节点选择加入到距离最近的簇头所在的簇中,从而将整个网络划分为大小不等的簇;然后簇头再根据簇头剩余能量、簇头到基站的距离构造基于最小生成树的最优传输路径;通过簇内节点单跳、树内簇头多跳通信的方式将数据最终传输到基站。仿真结果表明,该路由算法能有效节约能量和均衡节点能耗,从而延长网络的生命周期。

无线传感器网络;能量均衡;非均匀分簇;最小生成树

无线传感器网络通常包括了大量的传感器节点和用于收集和发送数据的基站组成,这些传感器节点采集监控区域的数据,通过自组网方式将采集到的数据上传给基站。由于传感器节点大多采用电池供电,很难对传感器节点进行能量补充,因此设计能量高效的路由算法是WSN研究的热点[1-2]。

LEACH[3]为最早提出的分簇路由算法,它能有效降低能耗并提高网络生命周期,但簇头到基站通过单跳方式传输会使距离基站远的簇头消耗过多能量。研究表明在簇头到基站间采用多跳方式传输更节约能量[4],然而距离基站近的簇头需要转发其他簇头的数据,必然造成离基站近的簇头消耗过快,导致能耗不均衡。针对近基站簇头能耗过大造成能耗不平衡的问题,文献[5]提出的EEUC算法、文献[6]提出的DEBUC算法均采用非均匀分簇,能有效均衡能量消耗,延长网络生命周期,但其簇头选择采用概率和门限值来决定,不能保证所选择的簇头最优。文献[7]提出EBUCA算法利用剩余能量和节点密度设置簇头选择阈值,并根据簇头密度及与基站的距离构建非均匀的簇半径,达到均衡节点能耗的目的;文献[8]提出冗余簇头并减少簇头选择的次数来延长网络生命周期;文献[9]对簇头选择与簇头更换提出了改进措施,能提高网络性能,但其簇头更换仅在簇内进行也会造成能耗不均衡。

文献[10]在非均匀分簇的基础上,簇头路由中采用蚁群算法进行优化,能延长网络生命周期,但并没有考虑链路质量,可能造成局部路径最优。文献[11-12]在非均匀分簇的基础上,簇头路由构造最小生成树,在构造树时只考虑了传输能耗以及簇头的剩余能量或只考虑了与基站的距离。

本文综合以上问题,提出了改进的非均匀分簇路由算法。算法在簇头选择时综合考虑节点剩余能量、节点“度”、簇内节点与簇头的距离、节点到基站的距离等因素,将整个网络划分为不均匀的簇,簇内节点通过单跳方式将数据发送给簇头;然后簇头与基站之间根据簇头剩余能量以及与基站的距离构造以基站为根节点的最小生成树,簇头通过最小生成树组织的路由以多跳方式将数据传送给基站。该算法能很好地均衡节点能耗,达到有效延长网络生命周期的目的。

1 相关模型

1.1 网络模型

为便于研究,本文假设传感器网络具有如下性质:①节点部署后不再移动且能量有限,基站位置固定而能量不受限;②每个节点具有相同的初始能量,且有相同的通信和数据处理能力,可自由调整发射功率;③每个节点具有唯一的标识,用Si表示第i各节点,则节点集合S={S1,S2,…,Sn};④节点可以根据接收到的信号强度RSSI来计算发出者到自己的近似距离;⑤基站能够和所有节点进行通信。

1.2 能量模型

由于无线传感器网络中节点进行数据传输时所耗的能量远大于其他的能耗[13]。本文采用文献[3]中的无线通信能耗模型,发送数据时其能耗公式如下:

(1)

节点接收k比特数据的能耗为:

ERx(k)=kEelec

(2)

为简化问题,假定通信均采用自由空间模型,簇头j内的节点数为n,则簇内成员节点i发送k比特数据到簇头j所消耗的能量为

(3)

式中:dij为成员节点i与簇头j之间的距离。

簇头j所消耗的能量包括接收簇内n个节点数据所耗能量、发送这些数据所耗的能量、接收和转发来自其他m个簇头数据所耗的能量,其公式如下(为方便研究,假如每个簇内均有n个节点数据):

Ej=(m+1)n[ETx(k,d)+ERx(k)]=

(m+1)nk(2Eelec+εfsd2)

(4)

式中:d为簇头到下一跳的距离。

由式(3)、式(4)可知,簇头的能耗由簇内节点数n、要转发的数据量k以及簇内节点与簇头的距离dij以及到下一跳的距离d决定的,因此优化簇头选择和数据传输路径能有效降低能耗。

2 改进的无线传感器网络非均匀分簇路由算法

类似于LEACH,本算法采用“轮”方式运行,每轮分为簇建立阶段和数据传输阶段。在簇建立阶段选择综合考虑剩余能量、节点与基站的距离、节点的“度”以及簇内节点与簇头距离等因素,采用时序的方式选择簇头。在数据传输阶段,根据簇头剩余能量及簇头与基站间的距离建立基于最小生成树的最优传输路径。

2.1 概念描述

为便于描述,对本文所涉及的概念说明如下:

①竞选半径。节点竞选簇头时的半径,本文采用文献[5]的公式计算竞选半径。

(5)

②邻居节点。节点Si和Sj互为邻居节点满足

dij

(6)

式中:dij节点i和节点j之间的距离。

③邻居表。每个节点保存一个邻居节点表以存储邻居节点的相关信息,如表1所示。

表1 节点的邻居表内容

④平均剩余能量Eavg。节点根据邻居表中邻居节点的剩余能量计算出平均剩余能量。

(7)

⑤平均距离davg。节点根据邻居表中邻居节点与该节点的距离计算出平均距离。

(8)

⑥簇头竞争时间t。从节点收到基站通知簇头竞争到本节点发出簇头竞争消息的等待时间。

(9)

式中:α为[0.9,1]之间的随机数,T为规定的簇头竞争持续时间,ei为节点剩余能量,β、γ为距离调节因子。从式中可以看出,簇头竞争时间t由节点剩余能量、到基站的距离以及邻居节点与该节点的距离决定,剩余能量越低、到基站越远、邻居节点平均距离越大,t的取值就越大。

2.2 簇头选举

在无线传感器网络分簇算法中,簇头选举对有效管理网络能耗至关重要。文献[5-7]均证明了非均匀分簇能有效均衡簇头能耗,缓解能量空洞。本文在非均匀分簇的基础上建立了本文的簇头选举算法,网络中所有节点都参与簇头竞争,采用时序的方式选择簇头。

簇头选择的算法步骤:

第1步 基站向全网广播一个分簇信号PAR_MSG,所有节点根据接收到的信号强度计算其到基站的距离Di,然后根据式(5)确定其竞争半径Ri。

第2步 各节点竞选半径Ri/2范围内广播竞选消息Comp_MSG,该消息包括节点的ID、剩余能量ei。

第3步 各节点收到来自另外节点的竞选消息Comp_MSG,根据接收到的信号强度计算两节点间的距离d,再根据式(6)将满足条件的节点加入到邻居节点表中。

第4步 各节点根据邻居节点表中的信息,按照式(7)、式(8)分别计算出平均剩余能量Eavg和平均距离davg。节点再根据式(9)计算出自身的簇头竞争时间t。

第5步 基站广播簇头选举信号Sel_MSG,以同步各节点的时间。

第6步 节点接收到Sel_MSG信号后,启动自身时钟开始计时并监听其他节点信号。

第7步 若节点i在本身的簇头竞争时间t到来前收到邻居表中其他节点的簇头宣告成功的消息SUC_MSG,节点i广播竞选失败的消息FAI_MSG,退出簇头竞选。

第8步 若节点i收到邻居表其他节点的FAI_MSG消息,就把这个节点从邻居表中删除。

第9步 若节点i在本身的簇头竞争时间t到之后还没有收到邻居表中其他节点的SUC_MSG消息,则该节点在竞选半径内广播SUC_MSG消息成为簇头。

第10步 选举结束后,没有成为簇头的节点选择加入到邻居表中距离最近的簇头所在的簇中。离簇头越近,簇内通信可以节省能量。

第11步 分簇完成后,各个簇头在竞选半径范围内广播簇头消息CLU_MSG,并收集其他簇头广播的消息,为后续路由做准备。CLU_MSG信息包括簇头ID、剩余能量。

算法中将整个网络划分为大小不等的簇,靠近基站的簇半径小,有利于均衡能耗;簇头竞争时间考虑了剩余能量、到基站距离以及簇内节点到簇头的平均距离等因素,能够保证选举的簇头综合性能最优。

2.3 簇间路由

分簇及簇头选举结束后,簇间通信采用多跳路由,以基站为树根,簇间路由采用最小生成树方式来组织。先将每个簇抽象为一个点,用边把相邻的簇连接起来,构造一个带权的连通图G=(V,E)表示无线传感器网络,其中V是点集(包括所有簇头和基站的集合),E为边集。

发送和接收同样长度的数据,通信能耗由节点间距离决定,因此权值计算时综合考虑簇头间距离和簇头剩余能量,权值计算如式(10)所示:

(10)

式中:wij为簇头i、j的边的权值,dij簇头i、j之间的距离,ei、ei为簇头i、j的剩余能量,ρ为可变参数,不能相互接收信息的两个簇头的边的权值w设为无穷大。从式中可以看出,权值由簇头间距离和簇头的剩余能量决定,剩余能量越低、簇头间距离越远,wij的取值就越大,则簇头要负责数据转发的概率降低,从而节省自身能量,延长生命周期,达到整个网络能量均衡。

根据簇头选择过程中计算得到的簇头到基站的距离Di以及相邻簇头的广播信息CLU_MSG,簇间路由利用Prim构造最小生成树的具体算法步骤:

第1步 各簇头根据本身到基站的距离Di及剩余能量ei,计算Di/ei的值,若Di/ei值小于h(h为常量)的簇头集合为C={C1,C2,…},集合C中的簇头可以直接将数据传输给基站。

第2步 在有向连接图G=(V,E)中,将集合C中的簇头节点和基站加入到集合U中,将集合C中的簇头到基站的边加入到集合T中。

第3步 各簇头根据接收到的CLU_MSG信息,依照接收到的信号强度计算两节点间的距离d,再依据式(10)计算出簇头间每条边的权值w(不包括集合C中簇头到基站的边)。

第4步 从所有u∈U,v∈V-U的边中选择权值wuv最小的边,将簇头v加入到U中,将边(u,v)加入到集合T中。

第5步 重复执行第4步,直到U=V为止。此时集合T中的所有边就构造了一棵最小生成树。

第6步 依据已确定的最小生成树的结构,节点调整传输功率,调整为能够到达其最小生成树的所有一跳邻居,从而节省能量。

当节点数据到达簇头时,簇头根据以上生成的最小生成树,以多跳方式将数据传输到基站。

2.4 算法分析

假定无线传感器网络中共有个N节点,产生了M个簇头,则算法时间复杂度为O(N2)。

证明 成簇开始时,基站广播PAR_MSG信息,各节点计算竞选半径,时间复杂度为O(N);每个节点计算节点间距离并加入到对应邻居表中,时间复杂度为O(N2);每个节点计算自身的簇头竞争时间,时间复杂度为O(N2);基站广播簇头选举信号Sel_MSG,各节点启动时钟计时,时间复杂度为O(N);各节点计时开始根据簇头竞争时间来进行簇头选举,时间复杂度为O(N2)。因此非均匀分簇及簇头选举的成簇算法时间复杂度为O(N+N2+N2+N+N2),即O(N2)。

簇间路由中,算法开始时构造带权的连通图的时间复杂度为O(M2);各簇头计算Di/ei值的时间复杂度为O(M);计算簇头间距离和权值w的时间复杂度为O(M2);依照权值w构造最小生成树的时间复杂度为O(M2)。因此簇间路由算法的时间复杂度为O(M2+M+M2+M2),即O(M2)。

根据以上分析,因为N≫M,因此整个算法的时间复杂度为O(N2)。

3 实验仿真

采用OPNET仿真软件对本文算法、EEUC协议和EBUCA协议进行比较仿真模拟。实验仿真参数如表2所示,传感器节点随机分布,簇点融合数据的能量忽略不计。为了比较,本实验相关参数与文献[5]的相同,取c=0.5,而ρ=0.5。图1为存活节点数随运行轮数的变化情况,图2为剩余总能量随运行轮数的变化情况。

表2 实验仿真参数表

图1 生命周期对比

图2 剩余总能量对比

由图1可以看出,本文算法从第1个节点失效到最后一个节点死亡的时间都比EEUC和EBUCA算法滞后,这说明本文算法能够很好的均衡网络能耗从而延长网络生命周期。不管是以首个节点死亡时间还是以最后一个节点死亡时间作为判断标准,本文算法都更优。

图2对比了3种算法每轮过后的剩余总能量,可以看出本文算法具有较小的坡度,波动较小且生存时间更长,表明本文算法相对于EEUC和EBUCA算法能耗速度较慢且能耗较 小,更能有效地节约能量。

4 结语

本文对已有的无线传感器网络路由算法及其存在的问题,借鉴非均匀分簇的思想,提出了改进的无线传感器网络非均匀分簇路由算法。改进的算法在簇头选择阶段综合考虑剩余能量、节点到簇头的距离、节点“度”以及节点到基站距离等因素,通过时序方式选择簇头;在数据传输阶段,综合考虑剩余能量和簇头到基站距离建立最小生成树,通过多跳方式进行数据传输。实验结果表明,本文算法可以延长节点的死亡时间,有效均衡网络能耗,从而延长网络生命周期。

[1] 李亚男,徐夫田,陈金鑫. 基于LEACH的WSNs分簇优化策略[J]. 传感技术学报,2014,27(5):670-674.

[2]李建洲,王海涛,陶安. 一种能耗均衡的WSN分簇路由协议[J]. 传感技术软件学报,2013,26(3):396-401.

[3]Heinzelman W,Chandrakasan A,Balakrishnam H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Proc of the 33rd Conf on System Sciences.Piscataway. NJ:IEEE.2000:3005-3014.

[4]Mhatre V,Rosenberg C. Design Guidelines for Wireless Sensor Networks:Commnunication,Clustering and Aggregation[J]. Ad Hoc Networks,2004,2(1):45-63.

[5]李成法,陈贵海,叶懋,等. 一种基于非均匀分簇的无线传感器网络路由协议[J]. 计算机学报,2007,30(1):27-36.

[6]蒋畅江,石为人,唐贤伦,等. 能量均衡的无线传感器网络非均匀分簇路由协议[J]. 软件学报,2012,23(5):1222-1232.

[7]卢先顺,王莹莹,王洪斌,等. 无线传感器网络能量均衡的非均匀分簇算法[J]. 计算机科学,2013,40(5):78-81.

[8]冯冬芹,李光辉,全剑敏,等. 基于簇头冗余的无线传感器网络可靠性研究[J]. 浙江大学学报:工学版,2009,43(5):849-854.

[9]姚光顺,温卫敏,张永定,等. 改进的无线传感器网络簇首选择策略及其路由算法[J]. 计算机应用,2013,33(4):908-911,915.

[10]张荣博,曹建福. 利用蚁群优化的非均匀分簇无线传感器网络路由算法[J]. 西安交通大学学报,2010,44(6):33-38.

[11]陆晶,马悦,吴晓军. 一种基于最小生成树的非均匀分簇路由算法[J]. 小型微型计算机系统,2012,33(10):2293-2296.

[12]邹杰,史长琼,姬文燕. 基于粒子群优化的非均匀分簇路由算法[J]. 计算机应用,2012,32(1):131-133.

[13]Estrin D. Wireless Sensor Networks Tutorial Part Ⅳ:Sensor Network Protocols[C]//Proc of the ACM Mobil Computing and Networking. New York:ACM,2002.1-5.

Improved Uneven Clustering Routing Algorithm for Wireless Sensor Networks*

ZHANGWenmei1,LIAOFubao2*

(1.Department of Mechanics and Electronics,Guang Dong AIB Polytechnic College,Guangzhou 510507,China;2.Department of Computer,Guang Dong AIB Polytechnic College,Guangzhou 510507,China)

In order to solve the problem of energy hole in wireless sensor networks caused by uneven clustering protocol,an improved uneven clustering routing algorithm is proposed. In the cluster heads selection stage,the algorithm selects the cluster heads based on several factors,including the residual energy of node,the distance between node and base station,the "degree" of the node,and the distance between node and cluster head. Other nodes that can’t be cluster heads select to join the cluster nearest to complete the process of clustering and the network is divided into clusters with different size. In the stage of data transmission,the algorithm constructs the optimal transmission path based on minimum spanning tree,according to the residual energy of cluster heads,and the distance between cluster heads and base station as well. The ordinary nodes of a cluster sends the data to cluster head through a single jump,and cluster heads send the data to base station through the nodes of the tree by the more jumping communication. The simulation shows that the routing algorithm can efficiently reduce and balance the energy consumption,and prolong the wireless sensor network survival period.

wireless sensor networks;energy balance;uneven clustering;minimum spanning tree

张文梅(1978-),女,硕士,副教授,研究方向为计算机应用、物联网,zwm200718@126.com;

廖福保(1976-),男,硕士,副教授,研究方向为计算机应用、无线传感器网络与路由,fbliao2000@163.com。

项目来源:科技部国家星火计划项目(2013GA780003)

2014-11-28 修改日期:2015-01-26

C:6150P

10.3969/j.issn.1004-1699.2015.05.021

TP3931

A

1004-1699(2015)05-0739-05