一种分布式无线传感器网络能量均衡路由算法

第37卷　第1期计算机科学Vol. 37No. 1一种分布式无线传感器网络能量均衡路由算法

刘湘雯1　薛　峰2　李　彦1　于宏毅3　胡捍英3

(空军工程大学电子科学系　西安710051) 1　(武警陕西省总队通信站　西安710054) 2

(信息工程大学通信工程系　郑州450002) 3

摘　要　针对无线传感器网络的能量均衡问题, 基于一种度量局部能量均衡性能指标, 提出了一种基于预测的分布式

能量均衡路由(Predicting 2based Distributed Energy Balancing Routing ,PDEBR ) 算法。PDEBR 基于地理位置信息, 结合功率控制, 以分布式方式达到能量有效性的目标。最后, 对PDEBR PDEBR 可以有效延长网络寿命。关键词　无线传感器网络, 能量均衡, 网络寿命中图法分类号　TN919　　　　

B R outing Algorithm in Wireless Sensor N et w orks

IU Xiang 2wen 1　XU E Feng 2　Li Yan 1　YU Hong 2yi 3　HU Han 2ying 3

(Depart ment of Electron Science ,Air Force Engineering University ,Xi ’an 710051,China ) 1(Shaanxi People ’s Armed Police Corps ,Communication Station ,Xi ’an 710054,China ) 2

(Depart ment of Communication Engineering ,Information Engineering University ,Zhengzhou 450002,China ) 3

Abstract 　Aiming at the energy balancing issue in wireless sensor network (WSN ) ,based on a local energy balancing metric ,predicting 2based distributed energy balancing routing (PDEBR ) algorithm was proposed. PDEBR gets to energy efficiency with geographic location information and power control. PDEBR was complemented with distributed style. The simulation results show PDEBR can prolong network lifetime efficiently. K eyw ords 　Wireless sensor networks , Energy balancing ,Network lifetime 　　　无线传感器网络(Wireless Sensor Network ,WSN ) 中, 传感器节点主要依靠电池供电, 因此能量是极为重要的网络资源。最大限度地提高节点及网络的能量有效性, 使网络以有限的能量工作尽可能长的时间, 是该类网络的主要设计目标之一[123]。能量消耗的不合理可以分为无效的能量消耗和不均衡的能量消耗。无效能量消耗由空闲侦听、监听等引起, 不均衡能量消耗由无线传感器网络的特性带来, 例如事件感知的不平衡、数据传输不对称(多对一) 等。提高能量有效性的方法包括:从器件角度降低数据获取、处理和通信所需要的基本能耗参数; 通过休眠机制, 降低节点在空闲状态无谓的能量消耗, 这属于休眠调度问题, 既要考虑连通性, 又要考虑网络覆盖; 能量均衡消耗机制。我们主要研究WSN 提高能量有效性的能量均衡消耗机制。

向能量不均衡, 一方面是所有数据都要传送到Sink , 另一方面是Sink 节点数量少, 通常只有一个Sink 。这种数据流的方向性以及业务的多对一特性, 导致距离Sink 近的节点的能量消耗比较大。对于能量均衡问题, 可以从多个角度来解决:功率控制的角度[527]、考虑传感器网络特点的数据压缩的角度[6]、路由的角度、多Sink 和移动Sink 的角度[8]以及节点密度控制的角度[9]等。

路由是解决能量均衡的一个重要方法, 文献[10]针对格状规则网络拓扑, 提出了边界转发策略———DSAP (Direction 2

al Source 2Aware Protocol ) , 在选择源到目的的路径时, 让边

界节点完成分组转发。边界转发要比内部转发的能量均衡性能好, 这是因为边界节点的邻居节点个数少, 需要其帮助完成转发的分组个数少, 并且侦听能耗比较小。DSA P 没有路由表, 并且以边界转发提高了网络的能量均衡性能。但是边界转发会带来比较多的端到端能量消耗。而且, 边界转发的可扩展性差, 这是因为随着边界其节点个数的增加速率要低很多。文献[11]基于一种基于流量规划的路由策略, 采用线性规划的方法, 提出了一种基于线性规划的集中式能量均衡路由算法(Centralized Energy Balancing Routing ,CEBR ) 。CE 2

1　WSN 能量均衡路由技术

能量均衡可以分为横向均衡和纵向均衡[4]。导致横向能量不均衡有两方面的原因:一方面是低能量节点总是先于高能量节点中继数据, 造成不均衡的累积, 这是可以人为控制的; 另一方面是事件发生的不均衡, 这是不可控制的。导致纵

到稿日期:2009202225　返修日期:2009204230　　本文受CN GI 示范工程项目(CN GI 20421021D ) , 国家自然科学基金(60472064) 资助。刘湘雯(1977-) , 女, 博士, 讲师, 主要研究方向为无线传感器网络路由等,E 2mail :wujingkj@126. com ; 薛　峰(1976-) , 男, 工程师, 主要研究方向为视频通信等; 李　彦(1963-) , 男, 教授, 主要研究方向为信号处理等; 于宏毅(1963-) , 男, 教授, 博士生导师, 主要研究方向为信号处理、无线网络等; 胡捍英(1961-) , 男, 教授, 博士生导师, 主要研究方向为第三代移动通信技术等。

・122・

BR 的基本思想是网络中有一个中心控制节点, 中心控制节点

认为是Sink 节点, 由Sink 节点收集全网拓扑信息, 并在每一轮开始时收集所有节点的能量信息。然后利用非线性规划, 求解每条链路的最佳转发概率, 并把计算得到的链路转发概率分发到每个节点。每个传感器节点根据可达链路的概率选择一个下一跳节点进行转发分组, 使得能量均衡性能达到最佳。这种做法如果不考虑收集拓扑信息以及能量信息的开销, 就会得到接近最优的优化结果。但是,CEBR 的控制开销比较大, 需要收集全网拓扑信息; 需要在全网散播概率转发表; 每一轮开始时, 每个节点都需要向Sink 更新能量信息。CEBR 以集中式方式实现, 当网络规模比较大时, 开销会随着网络规模的增大而不断增大, 可扩展性比较差。

本文结合功率控制机制, 从路由的角度提出一种分布式基于局部拓扑信息的能量均衡路由算法PDEBR (based Distributed Energy Balancing ) 如下几个特点:首先能量均衡; 其次, 其作为当前下一跳, 是一种分布式的、基于局部网络状态信息的工作机制, 具有良好的稳定性和可扩展性, 比较适合WSN 无中心控制、节点容易失效等特点。通过对算法性能仿真分析的结果表明,PDEBR 可以有效延长网络寿命。

1) 传感器节点随机均匀分布。

2) 所有节点的地理位置信息已知。

3) 每个节点可以根据自己到下一跳节点之间的距离, 动

态调整自己的发射功率。

4) 所有传感器节点类型相同, 并且初始能量相同。采用文献[8]、文献[12]以及文献[13]等广泛采用的节点能耗模型, 即节点i 到j 发送长度为l bit 的分组消耗的能量为

(2) E t -ij =l (α12+α2d i , j )

接收长度为l bit 的分组的能耗为

E r =αl 11

(3)

αα其中, 11, 12令1α11αd i , j 为节点i 到j 的, l , k , 2～4之间的。

. 2　的基本思想

首先给出前向邻居节点的定义。定义1(前向邻居节点) 　当前节点距离目的更近的邻居节点。如图1所示, 节点1的前向邻居节点为节点2和节点3

。

2　能量均衡的度量指标

对于WSN 来说, 采用集中式方式可以达到全网能量均衡。但是, 随着网络规模的增大, 集中式方式会带来比较大的控制开销, 协议的可扩展性比较差。而利用局部信息以分布式方式实现全网能量均衡, 是提高网络可扩展性的一个重要出路。

对于网络中某一个节点来说, 若以局部信息实现能量均衡, 只能最小化与自己一跳的邻居节点的均方差, 这可以认为是一种局部能量均衡方式。如果网络中所有节点都能够达到局部能量均衡, 也就能够接近全网能量均衡的目的。采用节点剩余能量的均方差φ来衡量网络能量均衡的程度, 即局部能量均衡的度量指标为

φlocal =

∑(E i -E k ) 2

图1　PDEBR 基本思想

PDEBR 的基本思想为:①利用地理位置信息约束最小能

量路径。根据邻居节点的地理位置信息, 分组只发送给前向

节点, 这些节点构成下一跳备选集Ω。这使得分组不断向距离Sink 更近的方向前进, 从而保证了端到端传输能耗比较小。②以式(1) 的φlocal 为度量指标达到局部能量均衡。分别预计算Ω中各个元素作为下一跳后的局部能量均衡性能φlocal , 选择使得局部能量均衡性能最好的节点作为下一跳。

下面以图1为例说明PDEBR 路由过程。本例中, 节点1要向Sink 发送一个数据分组, 节点的基本处理过程如下:

1) 节点1根据自己以及邻居节点与Sink 之间的距离确定下一跳备选集Ω, Ω={2,3}。

2) 节点1分别估算把分组发送给备选集中的节点2或者节点3之后的局部能量均衡性能。E e 表示估计的节点剩余能量, E c 表示节点的当前剩余能量。节点1以自己发送分组后估计的剩余能量E e 1、选择节点2或者节点3之后估计的剩余能量E e 2或者E e 3, 以及邻居节点4的当前剩余能量E c 4, 计算局部能量均衡性能。根据式(1) , 节点1把分组发送给节点

2后的局部能量均衡性能为

2222

, i =1, 2, …, k (1)

其中, k 为节点的邻居节点个数加1。E k 是k 个节点能量的

∑E i

均值, E k =

, i =1, 2, …, k 。

定理1　当网络中节点发送功率不能调整时, 选择剩余能量最多的邻居节点作为下一跳, 即可达到局部能量均衡性能最好。

证明略。

3　分布式能量均衡路由PDEBR

在节点发送功率可以调整的情况下, 以该节点作为下一跳后导致的局部能量均衡性能作为选择下一跳的标准, 这就是本文提出的基于预测的分布式能量均衡路由算法PDEBR 的依据。局部能量均衡性能用式(1) 度量。

3. 1　网络模型及能耗模型

φ　local -2=

其中, E k 2为节点1选择节点2作为下一跳后一跳邻居节点的

能量均值, E k 2=。节点1把分组发送给

4节点3后的局部能量均衡性能为

2222

φ　local -3=

首先给出WSN 的网络模型:

・123・

其中, E k 3为节点1选择节点3作为下一跳后一跳邻居节点的能量均值, E k 3=

。节点1比较φlocal -2和

φlocal -3, 如果φlocal -2

则选择节点3作为下一跳。

3) 下一跳节点接收到分组后, 回到第1) 步。重复以上步骤, 直到分组到达Sink 。

4) 在选择下一跳节点的过程中, 应当遵循前进距离为正的原则, 以有效避免环路。如果在自己的一跳范围内不能找到满足该要求的下一跳节点, 则说明发生了“局部最大”问题。但是, 由于PDEBR 已知两跳邻居信息, 可以进一步在两跳范围内找到使得局部能量均衡性能最好的前向节点, 以努力摆脱“局部最大”的困境。

3. 3　PDEBR 的关键技术

φ3. 3. 1　local 的估算

PDEBR 中, 表及其地理位置信息。这样做带来的另外一个好处是, 可以

利用两跳邻居的地理位置信息有效避免“局部最大”问题。3. 3. 2　估算φlocal 的范围可以知道, 估算φlocal 的范围越大, 越接近全网范围, 就能够达到越好的全网能量均衡性能。估算φlocal 范围的极限情况就是以全网所有节点的剩余能量进行估算, 这显然可以达到最好的全局能量均衡性能, 但这是需要付出开销的, 包括计算开销和控制开销。尤其是对于节点分布密集、网络规模大的WSN 网络, 其开销更不容忽视。

对于PDEBR 来说, 在一跳范围内预测φlocal 要用到两跳邻居信息。同理, , 就要用到第三跳节。因此, 考虑到协议。

仿真条件如下。

1) 网络范围:X ×Y 的矩形拓扑。

2) 节点数:若干个WSN 节点,1个Sink 节点。

3) 节点位置分布:每个WSN 节点在网络范围内服从均匀、独立分布,Sink 节点固定在[X , Y ]位置。

4) 节点最大有效通信距离:R =100m 。

5) 节点初始能量配置:WSN节点0. 1J ,Sink 节点100J 。6) 业务模型:每个WSN 节点每一轮向Sink 节点发送1个长度为20bytes 的分组。

7) 节点能耗参数:如表1[12]所列。取k =4时的能耗参数。

8) 仿真性能指标:分组递交率; 平均端到端能耗; 能量均衡性能; 网络寿命(以网络中第一个节点失效的轮数计算) 。

表1　收发信机能耗参数

信道衰减指数收发信机能耗参数

k =2

α11=135nJ/bit

k =4

α11=135nJ/bit

E c 量E e , φ, E c 和E e 的获取是local 。估算φlocal 的关键。

根据式(2) , 当前节点i 把分组发送给节点j 后, 其估计的剩余能量为

(4) E ei =E ci -l (α12+α2d i , j )

E ei 只需要已知邻居节点的地理位置信息即可得到。邻

居节点的位置信息通过Hello 消息即可获知。

Ω) 转发该分组后估计的剩余能量为第j 个邻居节点(j ∈

(5) E ej =E cj -E r -e j

其中, E cj 为第j 个邻居节点的当前剩余能量; E r 为节点接收该分组需要消耗的能量, 可由式(3) 得到; e j 为第j 个邻居节点转发该分组可能要消耗的能量。

下面分别介绍如何得到E cj 以及如何估算e j 。

1) E cj 的估算:采用数据分组捎带和Hello 携带能量信息相结合的方式跟踪节点的能量E cj 。在发送数据分组时, 携带节点的能量信息, 其它接收或侦听到数据分组的节点更新有关该节点的能量信息。另外, 由于环境因素的影响以及无线链路的不可靠性, 链路通常会发生时通时断的情况, 导致节点间的连接关系发生变化, 因此通常以Hello 消息周期性地通告节点的存在性。由此, 可以在Hello 消息中增加节点的剩余能量域。通过这两种机制的结合, 降低能量跟踪的能量消耗。

2) e j 的估算:假设从节点i 看来, 节点j 选择每个前向邻居节点的概率都相同, 为p 0, 且p 0=

n j

α12=45nJ/bit α12=45nJ/bit

2α=10pJ/bit ・m αm 4) =0. 001pJ/(bit ・

图2是网络范围为300m ×300m , 节点最大有效通信范围为100m 时, 网络中节点个数对GPSR 和PDEBR 性能影响

的比较曲线图

。

, 其中, n j 为邻居节点

j 的前向邻居节点个数。节点j 把分组发送给第k 个前向邻

居节点消耗的能量为e jk , 那么邻居节点j 发送分组可能要消

n j

耗的能量为e j =

∑e jk

n j

。

图2　节点个数对GPSR 和PDEBR 的性能影响

可以看出, 节点i 估算邻居节点j 发送分组的能耗e j 要已知两跳邻居节点信息———邻居节点j 的前向邻居节点个数

n j 以及邻居节点j 把分组发送给第k 个前向邻居节点所消耗的能量e jk 。

因此, 在PDEBR 中, 为了让节点i 获得自己的两跳邻居节点信息n j 和e jk , Hello 消息还需要携带节点的邻居节点列

图2(a ) 是PDEBR 与GPSR 的分组递交率比较曲线图。从图中可以看出, 随着网络中节点个数的增多, 分组递交率增大。这是因为, 节点个数越多, 节点密度越大, 节点的邻居节点个数越多, 找到下一跳的可能性越大, 分组端到端成功递交率也就越大。

・124・

图2(b ) 是PDEBR 与GPSR 的端到端平均能耗比较曲线图。从图中可以看出, 在开始时, 随着网络中节点个数的增多,PDEBR 和GPSR 的端到端平均跳数和能耗增大。这是因为, 节点密度很低时, 距离Sink 远的节点的分组大部分被丢弃, 这可以从图2(a ) 看到。只有距离Sink 比较近、跳数比较少的分组才能成功递交, 从而使得端到端跳数和能耗比较小。而节点密度增大后, 距离Sink 远的节点的分组也能够成功递交, 故使得端到端平均能耗增大。

当分组递交率非常接近1时, 随着节点个数的继续增多,

GPSR 的端到端平均能耗减小, PDEBR 的端到端平均能耗依

一种简单的结合方式。但是,PDEBR 达到网络寿命最大化还

是有一定距离的。因此, 我们需要进一步研究如下问题。

1) 在考虑能量均衡的基础上进一步考虑最小能量路径, 并在此基础上, 进一步研究无线传感器网络的寿命问题。

2) 研究能量均衡、端到端最小能量与网络寿命的关系。能量均衡希望所有节点轮流消耗能量, 最小能量路径每次转发分组都用同样的路径, 网络寿命与这二者之间具有一定的关系。在研究这个问题的基础上, 理论分析网络寿命的寿命限, 并研究能够延长网络寿命的度量指标。

参考文献

[1]

Akyildiz I F ,Su W Y ,et al. Wireless sen 2sor :a survey , 2002, 38(4) :2Chee , :evolution , op 2].Proc. of t he IEEE. 2003,91(8) :[3][4]

Karly H ,Willig A. Protocols and architectures for wireless sen 2sor networks[M ].Editorial John Wiley &Sons ,Ltd ,2006Lee Dong 2Wook , K im J ai 2Hoon , K o Y oung 2Bae. An energy ba 2lanced data dissemination scheme for lifetime extension in wire 2less sensor networks[C ]∥Proc. of t he Wireless Networks and Emerging Technologies (WN ET 2005) . Banff ,Alberta ,Canada :ACTA press ,J ul. 2005[5]

Mhatre V , Rosenberg C. Design guidelines for wireless sensor networks communications clustering and aggregation [J].Jour 2nal of Ad Hoc Networks ,2004,2(1) :45263[6]

Haenggi M. Energy 2balancing st rategies for wireless sensor net 2works[C]∥Proc. of IEEE International Symposium on Circuit s and Systems (ISCAS ’03) . Bangkok , Thailand :IEEE CS Press , May 2003:25228[7]

Olariu S , Stojmenovic I. Design guidelines for maximizing life 2time and avoiding energy holes in sensor networks wit h uniform distribution and uniform reporting [C ]∥Proc. IEEE IN FO 2COM. Barcelona ,Spain ,April 2006:1212[8]

Gao J L. Analysis of energy consumption for ad hoc wireless sensor networks using a bit 2meter 2per 2joule metric [R ].IPN Progress Report. August 2002:422150

[9]Lian J ,Naik K,Agnew G B. Data capacity im provem ent of w ireless sens or

netw orks us ing non 2uniform sens or distribution[J].International Journal of D istributed S ens or Netw orks ,2006,2(2) :1212145

[10]Salhieh A ,Weinmann J , K ochhal M ,et al. Power efficient topolo 2

gies for wireless sensor networks [C ]∥Proc. of International Conference on Parallel Processing. Valencia , Spain :IEEE Com 2puter Society ,Sep. 2001:1562163

[11]Gandham S , Dawande M , Prakash R , et al. Energy efficient

schemes for wireless sensor networks wit h multiple mobile base stations [C ]∥IEEE G lobal Telecommunications Conference (G LOB ECOM ’2003) . San Fransico ,California :IEEE Communi 2cations Society ,Dec. 2003:3772381

[12]Bhardwaj M , Garnett T , Chandrakasan A P. Upper bounds on

t he lifetime of sensor networks[C]∥Proc. of IEEE Internatio 2nal Conference on Communications (ICC ’01) . Helsinki , Fin 2land ,2001:7852790

[13]侯惠峰, 刘湘雯, 于宏毅, 等. 一种基于地理位置信息的无线传感

然继续增大。这是因为, GPSR 能够选择到距离自己更远、距离Sink 更近的邻居节点作为下一跳, 使得端到端平均能耗减小。而对于PDEBR , 其以局部能量均衡性能选择下一跳节点, 由于WSN 业务的方向性以及目的节点的唯一性, Sink 比较远、较多, 。, 。

图2(c ) 是PDEBR 与GPSR 的网络能量均衡性能φ的比较曲线图。从图中可以看出, 在节点密度比较低时, 网络的能量均衡性能比较好。随着网络中节点个数的增多, 能量均衡性能变差。当节点个数增多到使得网络分组递交率为98%以上时, 随着节点个数的增多, PDEBR 的网络能量均衡性能又不断变好, 而GPSR 的网络能量均衡性能基本保持不变。这是因为, 网络的能量均衡性能最主要是由距离Sink 一跳的节点的能量以及距离Sink 最远的节点的差异决定的, 当节点个数比较少时, 距离Sink 最远的节点的分组被中途丢弃的可能性比较大, 使得距离Sink 一跳的节点的能量消耗减小, 网络能量均衡性能比较好。随着网络中节点个数的增多, 距离

Sink 比较远的分组也成功递交, 增大了距离Sink 一跳的节点

的能耗, 使得网络的能量均衡性能变差。当网络中节点个数增多到可以使得分组递交率保持在98%以上时, PDEBR 的能量均衡性能变好。这是因为, 节点个数越多, 节点越能够找到使得局部能量均衡性能更好的下一跳节点, 使得全网的能量均衡性能得到提高。而GPSR 的能量均衡性能基本保持不变, 这是因为, GPSR 总选择距离Sink 最近的节点作为下一跳, 与能量均衡性能无关。

另外, 从图2(c ) 还可以看出, PDEBR 要优于GPSR 的能量均衡性能。这是因为PDEBR 是以能量均衡性能为准则选择下一跳, 而GPSR 并没有考虑能量均衡性能, 而是根据距离选择下一跳。

图2(d ) 是PDEBR 与GPSR 的网络寿命的比较曲线图。从图中可以看出, 随着节点个数的增多, 网络寿命缩短。这是因为, 节点个数越多, 节点接收的邻居发现消息越多, 能耗越大, 网络寿命越短。另外, PDEBR 的寿命比GPSR 的寿命长很多, 这说明追求能量均衡可以有效延长网络寿命。

结束语　从本文研究结果可以看到, 能量均衡是延长网络寿命的有效手段。但是, 纯粹考虑能量均衡, 而不考虑最小能量路径, 有可能导致分组端到端消耗更多的能量, 进而影响网络寿命。PDEBR 在前向邻居节点集合中寻找使局部能量均衡性能最好的节点作为下一跳, 以比较粗略的方式考虑了最小能量路径, 这可以看作最小能量路由和能量均衡路由的

器网最小能耗路由算法[J].电子与信息学报,2007,29(1) :1772

181

・125・