彭 铎,黎锁平,杨喜娟

(1.兰州理工大学,电气工程与信息工程学院,兰州 730050;2.兰州理工大学计算机与通信学院,兰州 730050)



一种能量高效的无线传感器网络非均匀分簇路由协议*

彭 铎1,2,黎锁平2*,杨喜娟2

(1.兰州理工大学,电气工程与信息工程学院,兰州 730050;2.兰州理工大学计算机与通信学院,兰州 730050)

针对无线传感器网络存在的严重的能量约束问题,提出一种能量高效的非均匀分簇路由协议(EUCP),采用限制簇规模的优化簇形成算法产生规模依次递减的簇和改进的多跳簇间转发方式,节约簇首能量,平衡簇间负载。根据监测要求采用参数可调的休眠/唤醒机制,结合最后一跳的“洒水壶”路径,有效解决了负载不均衡形成的“热区”问题。仿真结果表明,协议能有效降低网络能量消耗,延长网络生存周期。

无线传感器网络;能量高效;非均匀分簇;路由协议

由于无线传感器网络WSN(Wireless Sensor Network)中,传感器节点的运算、存储、通信能力有限[1-2],因此能量高效成为传感器网络路由协议设计的首要目标,这不仅需要对单个节点的能耗进行优化,更需要均衡网络总体能量的使用,从而延长整个网络的生存周期[3-5]。

传统的无线传感器网络分簇路由协议采用使所有节点轮流担任簇头节点的方法来达到均匀能耗的目的。LEACH(Low-Energy Adaptive Clustering Hierarchy)[6]协议是WSN中最早提出此思想的分簇路由协议,它也是第1个提出数据聚合的分簇路由协议。在LEACH协议的基础上,后来提出了很多改进型协议,文献[7-9]将单跳通信方式改为多跳通信方式,由簇头负责将邻居簇首的数据转发给Sink节点,从而解决通信能耗过大的问题,并改进了簇首选举的策略。

在采用多跳通信方式的分簇网络中,由于距离Sink节点较远的簇首需要邻居簇首充当中继节点进行数据转发,导致离Sink节点近的簇首既要承担较多的转发任务,又要负责簇内数据收集、压缩和传输,消耗过多能量,造成所谓“热区”(Hot Spots)问题[10-11]。文献[10]采用非均匀分簇的方式解决“热区”问题,但对簇间路由的选择没有详细描述。文献[11]中引入能量预测机制控制动态成簇,取得良好效果,但算法相对复杂,没有采用休眠唤醒机制。可见,在采用多跳通信方式的分簇网络中存在较显著的簇间能耗不均匀问题。

针对WSN的典型环境监控应用和简洁、高效、易于实现的设计目标,本文提出一种基于能量高效利用的控制简洁的分布式非均匀分簇路由协议EUCP。协议采用动态的分簇规模约束机制和改进型的多跳数据传输方式,使得靠近Sink节点的簇规模较小,远离Sink节点的簇规模较大,并且在Sink节点附近单跳范围内的节点都可作为路由节点,结合带有密度冗余的节点休眠机制,使得簇间能量消耗进一步均衡。

1 EUCP协议

针对本协议采用的时间驱动数据采集方式,提出了以下4点前提假设:①网络中除Sink节点外,其他普通节点都是同质的,具有相同的结构、性能和初始能量;②网络中节点随机均匀部署,部署完毕就不再移动,所有节点均具有唯一的节点编号;③节点的通信无方向性且发射功率可调,可以根据接收的信号强度来估算相对距离,每个节点周期性采集数据,并具有休眠功能;④Sink节点(基站)的处理能力和能量不受限制。

图1 EUCP协议的组织结构

在网络初始化阶段,基站(Sink节点)发送一个预先设定好的大功率初始化消息,向网络内的所用节点进行广播。每个节点在收到此消息后,根据接收信号的强度计算它到Sink节点的近似距离(RSSI),根据这个距离在以后的数据传输中节点可选择适合的发送功率和基站通信,并为非均匀分簇提供依据。在网络稳定状态,节点通过休眠/唤醒机制轮流工作,以进一步减少能量消耗。靠近Sink节点的节点将在唤醒时间内充当路由节点,来分担簇头节点的通信负担,形成在最后一跳的多条路径选择,我们将其称之为“洒水壶”路径。图1是EUCP协议的基本原理图。

1.1 簇首节点的产生

簇首的分布要符合动态非均匀分布,为此考虑通信距离和节点当前能量两个因素,对于剩余能量多的节点,无论其是否当选过簇头,均可参加竞选。在本协议中,节点发射功率分档可调,大部分时间处于“基本功率”档上,记为d0,节点ni的竞争半径Di的计算公式为:

(1)

其中,dmax表示网络中节点到Sink节点的最大距离,d(ni,Sink)是节点i到Sink节点的距离,a是加权系数,根据具体应用环境和节点性能设置。由式(1)可知,要竞选簇头的节点的竞争范围为d0～(1+a)d0。

阈值T(n)的取得要充分考虑节点当前剩余能量因素,使当前能量较高的节点有较高的概率当选簇头,T(n)的计算方法为:

(2)

(3)

其中,p是节点成为簇首的概率,r是目前已完成的轮数。定义系统参数u,它是反映当前节点能量对T(n)影响程度的参量,即节点能量较小时,能量因素的影响较小,这样就避免了在网络生命后期,所有节点成为簇头的概率都大大降低,导致网络不稳定的问题。Ecurrent表示节点的当前能量,E0表示节点的初始能量。

1.2 簇的形成

簇首产生后,没有当选簇头的节点将接收到的ADV消息排成一个邻居簇首列表,根据接收到的ADV消息的强度来决定加入哪个簇,并向该簇首发送加入消息ACC(Accede to Message),此消息中包含本节点的ID号、簇首节点的ID号和根据信号强度计算的离簇首的距离(RSSI),簇首接收到请求加入消息并根据消息包含的编码来决定是否允许加入本簇,并向成员节点发送确认消息ACK,至此网络的非均匀分簇完成。算法的伪代码如下:

//Cluster Formation Algorithm//

//For every node of the WSNs//

(1)m← Random(0,1)

(2)countT(n)

(3)ifm

(4)countDk//Competition radius of nodek//

(5)broadcast(ADV_msg)to Neighbor Nodes

(6)end if

(7)node j receiving ADV_msg from cluster_head k

(8)countd(j,k)

(9)for every neighbor nodes of nodejdo

(10) {ifd(j,k)

(11) min_distance[j]=d(j,k)

(12) end if

(13)ifd(k,j)=min_distance then

(14) send ACC_msg to cluster_headk

(15)end if

(16)on receiving ACC_msg for cluster_headk

(17)if ACC_msg is TURE then

(18) send ACK_msg to nodej

(19)end if

(20)Broadcast(TDMA_msg)to every cluster_member

节点在部署时要根据任务要求确定部署密度,一般部署密度大于基本的任务要求的节点数,即有适当冗余。为进一步节省网络容量,节点采用休眠∕唤醒机制轮流工作,假设网络要求的最小节点分布密度是Nm,节点根据自己的邻居列表和竞争半径计算出自己所处位置的节点密度Nc,当(Nc≥Nm)时即可应用休眠唤醒机制。假设节点B的邻居数为b,节点根据以下规则进行休眠∕唤醒操作:

规则1节点本身状态为唤醒状态时,如果b≤p,则节点下一状态为唤醒,如果节点b>p,则节点下一状态为休眠。

规则2节点本身状态为休眠状态时,如果b≤q,则节点下一状态为唤醒,如果节点b>q,则节点下一状态为休眠。

其中,p和q为规则条件参数,其取值为正整数,可根据网络工作技术要求调整,当每个节点明确了它的状态,网络就进入了稳定工作(数据传输)阶段。

1.3 数据传输阶段

每个簇成员在给定的时隙内将采集的数据发送给簇首,为单跳形式。在本协议中,簇首将数据融合后,以改进的多跳方式将数据传递到Sink节点。当簇头到基站的距离小于d0时,簇头直接将数据发送到基站无需转发,否则只能以多跳的方式把数据转送到基站。显然可选的路由簇首应满足如下关系:

{CHi|d(CHi,Sink)d(CHj,Sink)>d(CHj,CHi)}

(4)

以两跳路由为例,假设数据由簇头CHi发出经过路由节点CHj转发至Sink节点,所消耗的总能量Ei-Sink为:

Ei-Sink=Ei-j-Tx(l)+Ej-Rx(l)+Ej-Sink-Tx(l)

(5)

其中,Ei-j-Tx(l)表示节点CHi发送l比特数据到节点CHj所消耗的能量,Ej-Rx(l)表示节点CHj接收l比特数据所消耗的能量,Ej-Sink-Tx(l)表示节点CHj发送l比特数据到Sink节点所消耗的能量。Ei-Sink(l)可表示为:

(6)

一个簇首或节点是否作为中继节点除了需考虑它与基站的距离外还要考虑它自身当前的能量,应该优先选择剩余能量多的节点作为中继节点,因此定义一个转发条件参数Fc(j):

(7)

其中Ej-current是候选路由节点CHj到汇聚点的距离,β和γ是加权系数。这样选择Fc(j)较小的节点作为中继节点既节省能量又均衡了节点负载。

2 分析及其仿真

2.1 消息复杂度

在EUCP算法中,WSN网络广播的消息复杂度为O(N),证明如下:

证明:网络中有N个节点,在簇头选举阶段有N×T个簇头参与选举,共广播N×T条CAM(Campaign Message)消息,假设其中有M个节点竞选成功,将发送M条ADV(Advertisement Message)消息。其他节点收到后经过对比,向该簇首发送加入消息ACC(Accede to Message)共N-M条,簇首将确认消息ACK及分配时隙发回申请节点,共N-M条。在簇建立过程中总的消息开销为:

N×T+M+N-M+N-M=(T+3)N-M

(8)

因此,消息的复杂度为O(N)。

2.2 能量模型及仿真环境参数设置

我们采用与文献[5]相同的无线通信能量消耗模型,发送lbit的数据到距离为d的接收方所消耗的能量为:

(9)

Eelec表示发射电路与接收电路的基本能耗,与编码、调制、虑波等相关,εfs、εmp分别为这两种模型中功率放大系数。

节点接收lbit的数据消耗的能量为:

ERx(l)=lEelec

(10)

仿真实验中所用的参数如表1所示。

表1 仿真实验参数

2.3 仿真结果分析

我们用MATLAB软件对EUCP协议与LEACH协议和EEUC[12]协议进行了仿真比较。主要从网络能量消耗和网络生存时间等方面进行了比较,以此来评价EUCP协议的性能。

①剩余节点与生存周期的对比分析

图2为3种协议的网络剩余节点数随时间的变化情况(节点初始能量为0.5 J),从图3中可以看出,LEACH协议在73轮开始就出现节点死亡,到325轮,节点几乎全部失效。

图2 剩余节点与生存周期的关系

EEUC和EUCP协议的首个节点死亡和节点全部失效的时间都远远大于LEACH协议,且EUCP协议的生存周期更长一些。这是由于EUCP协议采用非均匀分簇和考虑能量因素的簇首选举方式使节点的能耗减少并得到均衡使用。

②能量效率

网络能耗随时间的变化曲线如图3所示。在相同的时间里,EUCP算法的网络能耗远小于LEACH算法,也比EEUC算法好。而且,网络能耗随时间的增长率比较稳定,说明EUCRP算法的能量消耗比较均匀,而LEACH算法由于能耗相对较快,在后期频繁选举簇头导致网络不稳定。在图4中我们分别比较在不同的节点初始能量情况下,EUCP与LEACH和EEUC的网络生命周期,可以看出EUCP比LEACH算法和EEUC算法在不同初始能量下,网络运行的轮数都有所延长,比LEACH协议分别延长29%、33%、39%,比EEUC协议分别延长6%、7%、9%,节点初始能量越大,网络生存周期的延长越明显。这是由于EUCP算法优先选择能量较高的节点作为簇首,平衡了节点的能耗,稳定工作时间加长。

图3 网络能量消耗

图4 不同初始能量时的网络生存周期

图5 网络覆盖度与时间的关系

③网络覆盖度

协议的网络覆盖度和生存周期的关系如图5所示,在73轮后,LEACH协议的覆盖度就开始下降,EEUC在447轮后,覆盖度也开始下降,但变化较缓,EUCP协议在整个生命周期内,覆盖度始终比较平稳,直到500轮后才下降明显。由此可见,虽然EUCP协议在开始时网络覆盖度稍低,但出现首个节点失效的时间要远低于LEACH协议和EEUC协议,且覆盖度处于稳定状态,这说明在启用休眠∕唤醒机制时EUCP协议以牺牲网络覆盖度来换取了网络生存周期的延长。

3 结论

针对典型的大规模监控应用领域,本文提出了一种基于能量的非均匀分簇路由协议EUCP。采用限制簇规模的非均匀成簇算法和优化的多跳路由选择机制有效的节约了簇头能量,并首次提出在路径的最后一跳采用新颖的“洒水壶”路径,结合参数可调的节点休眠∕唤醒机制,最大限度的节约网络能量,平衡了簇间负载,有效解决了WSN的“热区”问题。仿真试验表明,所提算法可靠稳定,对节点性能要求低,有效的降低了网络能量消耗,明显延长了网络生存周期。

[1] 王营冠,王智. 无线传感器网络[M]. 北京:电子工业出版社,2012:1-5.

[2]赵丽霞,纪松波. 无线传感器网络在智能交通中的应用[J]. 物联网技术,2012,2(6):25-27.

[3]林蔚,祝启龙. 无线传感器网络节能型数据融合算法[J]. 哈尔滨工程大学学报,2011,32(10):1386-1390.

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

[5]Ashtar A M,Nahai M R,Aghvami A H. Power Aware Cooperative Routing in Wireless Mesh Networks[J]. IEEE Communications Letters,2012,16(5):670-673.

[6]陈晓娟,王卓,吴洁. 一种基于LEACH的改进WSN路由算法[J]. 传感技术学报,2013,26(1):116-121.

[7]Zhang R B,Cao J F. Uneven Clustering Routing Algorithm for Wireless Sensor Networks Based on Ant Colony Optimization[J]. Journal of Xi’an Jiaotong University,2010,44(6):33-38.

[8]Sun Yanqing,Peng Jian,Liu Tang,et al. Uneven Clustering Routing Protocol Based on Dynamic Partition for Wireless Sensor Network[J]. Journal on Communication,2014,35(1):198-206.

[9]Liao Y,Qi H,Li W. Load-Balanced Clustering Algorithm with Distributed Self-Organization for Wireless Sensor Networks. IEEE Sensors Journal,2013,13(5):1498-1506.

[10]屈斌,胡访宇. 高效节能的无线传感器网络路由协议研究[J]. 计算机仿真,2008,25(5):113-116.

[11]Lin M,Yang D,Zhengwei G. An Uneven Cluster-Based Routing Protocol for Wireless Sensor Networks[C]//2009 1st International Conference on Information Science and Engineering(ICISE),IEEE,2009:5320-5324.

[12]Li C F,Ye M,Chen G H,et al. An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks[C]//Proc of the IEEE Int’l Conf on Mobile Ad Hoc and Sensor Systems. Washington,DC,USA,2005:597-604.

彭铎(1976-),男,甘肃省兰州市人,副教授,博士研究生,主要研究方向为计算机网络与通信,无线通信,pengduo7642@163.com;

黎锁平(1965-),男,甘肃省合水县人,兰州理工大学教授,博导,主要研究方向为通信系统与信息处理,lsuop@163.com。

AnEnergyEfficientUnevenCluster-RoutingProtocolforWirelessSensorNetworks*

PENGDuo1,2,LISuoping2*,YANGXijuan2

(1.School of Electrical Engineering and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China;2.School of Computer and Communication,Lanzhou University of Technology,Lanzhou 730050,China)

For severe energy constraint problem of wireless sensor networks,a non-uniform energy efficient clustering routing protocol(EUCP)is proposed. Its core is the use of a limiting cluster size optimization formation algorithm to produce clusters in descending order of the size of the cluster. Improved multi-hop inter-cluster data forwarding,saving energy cluster head and energy consumption of inter-cluster is balanced. According to the monitoring requirements,use of adjustable parameters of sleep/wake-up mechanism,combined with the last hop of the “watering pot path”to effectively solve the“hot zone”problem caused by uneven load energy. Simulation results show that the protocol can effectively reduce network energy consumption and prolong the network lifetime.

wireless sensor network;energy efficient;uneven clustering;routing protocol

项目来源:国家自然科学基金项目(61363078);甘肃省自然科学基金项目(1308RJZA104)

2014-07-03修改日期:2014-10-21

TP393

:A

:1004-1699(2014)12-1687-05

10.3969/j.issn.1004-1699.2014.12.019