当前位置: 首页 > >

无线传感器网络优化生存时间的动态路由算法

发布时间:

 

第5期 2009 年 5 月

电          子 学 报
ACTA ELECTRONICA SINICA

Vol . 37   5 No.   May   2009

无线传感器网络优化生存时间的动态路由算法
朱艺华1 ,沈丹丹2 ,吴万登1 ,沈振伟1 ,汤一*1
     :   摘 要 节能和延长网络生存时间是无线传感器网络研究领域的热点问题 . 该文综合考虑网络中节点的剩余能 量和节点间传输数据的能耗 , 基于最短路径树算法 , 通过构造两种不同的权值函数 , 提出了 “比例权值路由算法” ( Ratio2W) 与 ( “和权值路由算法”Sum2W) . 仿真分析表明 ,所提出的算法可以延长网络生存时间 ,并使能耗经济有效 ,比 一些已有知名算法更优 . 关键词 :   无线传感器网络 ; 路由 ; 网络生存时间 ; 节能 中图分类号 :   TN92     文献标识码 :       A 文章编号 :   22112 (2009) 0521041205 0372
Abstract :   Saving energy and prolonging network lifetime are key issues of wireless sensor networks . Based on shortest path
and energy consumption for delivering packets on wireless links are considered. Simulation exhibits the Ratio2W and the Sum2W can
(11 浙江工业大学信息工程学院 ,浙江杭州 310032 ;21 浙江工业大学经贸管理学院 ,浙江杭州 310023)
( 11 College of Information Engineering , Zhejiang University of Technology , Hangzhou , Zhejiang 310032 , China ;

Dyna mic Ro uting Algorithms Optimizing Lifetime of Wirele ss Sensor Networks
ZHU Y2hua1 ,SHEN Dan2dan2 ,WU Wan2deng1 ,SHEN Zhen2wei1 ,TANG Y2ping1 i i
21 College of Business Administration , Zhejiang University of Technology , Hangzhou , Zhejiang 310023 , China)

prolong network lifetime and make energy consumed efficiently and effectively. In addition , the proposed algorithms outperform some well2known routing algorithms in terms of network lifetime and energy consumption.

1  引言

   无线传感器网络是部署在监测区域内 、 由大量微型 传感器节点通过无线电通信形成的一个多跳的自组织 网络 ,其目的是协作地感知 、 采集和处理网络覆盖区域 里被监测对象的信息 , 并发送给观察者 . 在传感器网络 中 ,当一个远离基站的节点要向基站传输所感知的数据 时 ,往往要借助于中间节点 、 以多跳的方式转发数据 . 传 感器网络具有集中式数据收集 、 多跳数据传输 、 多对一 流量模式等特征 . 由于传感器节点大多采用电池供电 ,电源能量受到 限制 ,因此 ,传感器网络的部署及路由协议都需要从节 能出发 ,最大限度地延长整个网络的生存时间[1 ] . 事实 上 ,网络生存时间的定义因应用而异 : 对于一个节点的 失效就会影响整个传感器网络正常运转的应用来说 ,网 络生存时间就是从网络开始运转到第一个节点失效这 一时间段 ; 而对于其它一些应用 , 网络生存时间可能是

收稿日期 :2008206223 ; 修回日期 :2008209209

基金项目 : 国家自然科学基金 (No160873228 ,No160673177) ; 浙江省钱江人才计划项目 (No12007R10 G2020022)

tree , ratio weight ( Ratio2W) and sum weight ( Sum2W) routing algorithms are proposed ,in which both remaining energy of nodes

Key words :   wireless sensor network ; routing ; network lifetime ; energy saving

到一部分节点 ( 如半数节点) 失效这一时间段[2 ] . 本文采 用前者 ,即到第一个节点失效这一时间段作为网络生存 时间 [2 ,3 ] . 文献 [ 4 ] 研究了传感器网络部署策略 , 提出了 网络生存时间和代价的一般模型 ,以分析与优化这些部 署策略 . 在无线传感器网络的路由研究领域 , 已经给出 了一些路由协议 . Flooding[5 ] 和 G ossiping[6 ] 是两个传统的 路由 协 议 , 它 们 以 洪 泛 为 基 础 , 其 信 令 开 销 较 大 . LEACH[7 ] 是一种基于簇的路由协议 , 其基本思想是随机 选择簇首节点 ,将整个网络的能量负*骄峙涞矫扛 节点上 ,从而降低能耗 、 延长网络生存时间 . 最大化生存 [8 ] 时间路由协议 ,利用网络流建模 , 采用线性规划方法 解决最大生存时间问题 . 文献 [ 9 ] 从理论上分析了最大 化网络生存周期的数据收集问题 ,提出了一种*似最优 的最大化网络生存周期的数据收集算法 . 文献 [ 10 ] 在数 据收集和聚合机制下 , 提出了基于最小生成树 ( MST , Minimum Spanning Tree ) 的 路 由 算 法 —— — PEDAP 与 PEDAP2PA.

1042

            电 子 学 报

2009 年

2  系统假设与能耗模型

Dijkstra 算法得到图 G( V , E) 的一棵树根在 sink 的最短

   怎样高效利用传感器网络的节点能量以提高网络 生存时间是无线传感器网络领域中一个十分重要的研 究课题 . 我们注意到 , 一些节能路由算法 ( 如基于最小 生成树的路由算法) 虽然降低了整个网络的能耗 , 但网 络生存时间却缩短了 , 这是因为在这些算法中某几个 枢纽节点因承担了过多的数据分组转发任务导致电池 能量过早耗竭而死亡 . 因此 , 如何设计一种既能节约能 量 ,又能延长生存时间 , 还能使数据分组传递延时小的 路由对传感器网络的有效运转是极为关键的 . 此乃本 文的研究要点 . 本文的主要创新之处在于 : 综合考虑网 络中节点的剩余能量和节点间传输数据的能耗需求 , ( 基于最短路径树 , 提出了 “比例权值路由算法” Ratio2 )与 ( Sum2W) . W “和权值路由算法”    无线传感器网络中 ,节点一般分为 Sink 节点 ( 即数 据收集节点) 和普通传感器节点 ( 简*诘 ) . 我们假 设 : ( 1) Sink 节点及其它所有普通节点的位置是固定的 , 且 Sink 有整个网络*私峁剐畔 ; ( 2) 普通节点具有相 同的属性 ( 如无线电发射功率 、 通信半径 、 单位时间能 耗等) ; ( 3) 每个普通节点能量受限 , 但 Sink 能量不受限 制 ; ( 4) Sink 节点定期地进行数据收集 ,普通节点通过直 接或多跳的方式把数据传送给 Sink. 考虑到各节点主要的能耗是由无线接口发送与接 收数据产生 , 其它能耗 ( 如计算过程所消耗的能量等)    我们选取到网络中第一个节点因能量耗尽而失效 为止这段时间为网络的生存时间[ 2 , 3 ] . 因此 , 要延长网 络生存时间 , 就要尽可能降低数据收集过程中各节点 的能耗 . 如果着眼于整个网络的能耗即网络中所有节 点的能耗 , 我们应该注意到 : 在将图 G ( V , E) 的边的权 重取为沿着这条边传递数据所需的能耗 ( 即式 ( 3 ) ) 条 件下 , 各个节点均沿着图 G( V , E) 的最小支撑树将数据 汇集到 Sink 节点的路由算法 ( 如 PEDAP 算法[ 10 ] ) 不是 最优算法 , 而最优算法是基于 LET (Least Energy Tree ) 的 路由算法[ 12 ] ( 以下简称 LET 算法) . 其理由是 :LET 算法 以式 ( 3 ) 作为无线传感器网络通信链路的权值 , 再由

可忽略不计 , 因此 , 在计算能耗时 , 我们采用最常用的 first order radio 模型[11 ] ,即节点接收 k 比特数据时的能 耗为 :
ER ( k ) = k Eelec ( 1)

将 k 比特数据从一个节点发送到另一个节点所需消耗 能量为 :
ET ( k , d) = k Eelec + k Eamp d
γ γ

( 2)

其中 , Eelec 为电路上接收或发送每比特数据的能耗 ; Eamp
d 为放大器发送每比特数据的能耗 ; d 为发送节点与

接收节点之间的距离 ;γ 是路径损耗系数 , 一般取值范 ( 围在 [ 2 , 4 ] 之间 . 于是 , 根据式 ( 1) 、2) 可知 , 两个距离为 dij 的节点 i , j 之间传输 k 比特数据的总能耗为 :
γ Cij ( k , dij ) = ER ( k) + ET ( k , d) = k ( 2 Eelec + Eamp dij )

( 3)

3  算法描述    在无线传感器网络中 , 如果节点 j 在节点 i 的通信 范围之内 , 则*诘 j 是节点 i 的邻居 . 由上节第 ( 2) 个 假设可知 , 这时 , 节点 i 也是节点 j 的邻居 . 以 ( i , j) 表示 邻居节点 i 与 j 的通信链路 , N ( i ) 表示节点 i 邻居的集 合 . 此外 , 以无向图 G ( V , E) 表示传感器网络 , 其中 V 为所有传感器节点的集合 , E 为图中所有边即通信链 路的集合 . 易知 , 式 ( 3) 就是在链路 ( i , j ) 传输 k 比特数 据所需的能耗 .

路径树即 LET , 然后图 G( V , E) 的所有节点均沿着 LET 将数据传送到 Sink , 因而各个节点均以最小能耗将数据 发送到 Sink , 故而整个网络的能耗最小 . 例如 , 对图 1 所 示的传感器网络 , 其中 , 节点 1 是 Sink 节点 , 边上所注 数字表示边的权值 ( 如能耗) , 易知 : 图 2 是它的最小支 撑树 , 图 3 是它的最短路树 . 可以看出 : 节点 2 , 3 , …, 6 沿着图 2 所示的最小支撑树将数据汇集到 Sink 即节点 1 , 总的权值是 ( 5 + 1) + 1 + ( 2 + 4 + 1) + ( 3 + 5 + 1) + ( 4
+ 1) = 28 ; 但这些节点沿着图 3 所示的最短路树 ( LET)

将数据汇集到 Sink , 总的权值是 6 + 1 + 5 + ( 6 + 1) + ( 4 + 1) = 24 . 因此 , 后者比前者更优 . 然而 ,LET 算法存在着一个缺点 : 它忽视了节点的

第    5 期

朱艺华 : 无线传感器网络优化生存时间的动态路由算法

1043

4  算法的实现

剩余能量 , 容易导致一些关键节点因承担过多的数据 转发任务 , 过早耗尽能量而失效 . 为了弥补这一缺点 , 除了考虑式 ( 3 ) 的能耗之外 , 我们考虑节点的剩余能 量 , 通过引入新的链路权值 , 将 LET 算法推广为以下两 种算法 “比例权值 ( Ratio2W) 算法” “和权值 ( Sum2W) : 与 算法” . 以 Re ( i ) 表示节点 i 的剩余能量 , 以 wij 表示链路 ( i , j) 的权值 . 在 Ratio2W 算法中 , 取
wij = [ Cij ( k , dij) ]
α

1 Re ( i )

β

( 4)

β 其中 ,α、 为正常数 , 分别称为 “能耗因子” “剩余能 与 量因子”在 Sum2W 算法中 , 取 ;
C wij = λ ij ( k , dij) + δ

1 Re ( i )

( 5)

其中 ,λ 与δ 为正常数且λ + δ = 1 , 分别称为 “能耗权 重” “剩余能量权重” 可以看出 : 当 α = 1 ,β= 0 ( 或 λ 与 . = 1 ,δ= 0 ) 时 , Ratio2W 算法 ( 或 Sum2W 算法 ) 变为 LET 算法 . Ratio2W 与 Sum2W 算法均采用 Dijkstra 算法构建路 由树 ( 最短路树) , 具体算法如下[ 12 ] :
T = { s} , L = V - { s}

5  仿真结果与分析

for each v ∈L

{ if ( v , s) ∈E , then

   p ( v) = s , Dpath ( v) = wv , s } {

else
}

   p ( v) = - 1 , Dpath ( v) = ∞ { }

do while L ≠

{ find v0 ∈L such that Dpath ( v0) ≡v ∈L { Dpath ( v) } min

 T = T ∪ v0} , L = L - { v0} {   each u ∈N ( v0) for    Dpath ( v0) + wu , v < Dpath ( u) , then if
0 0

    Dpath ( u) = Dpath ( v0) + wu , v , p ( u) = v0} ; {

}

( 从式 ( 4) 、5) 式可知 , 随着节点 i 剩余能量 Re ( i ) 的 减少 , 节点 i 与邻居节点的链路的权值就会增加 , 因而 , 在 Dijkstra 算法中 , 它就会推迟被加入到路由树中 ( 即它 离树根节点 —— — Sink 节点的跳数增大) , 从而它转发其 他节点的数据量就减少 , 这样就延长了这个节点的生 存时间 , 同时也延长网络生存时间 .

   Ratio2W 与 Sum2W 算法是集中式算法 , 用在 Sink 节 点 . Sink 节点开始数据收集时 , 采用洪泛 (flooding) 方式 向所有节点发一个数据分组 REQ , 通知这些节点收集 数据即将开始 . 各节点收到 REQ 之后 , 回复一个数据分

初始能量 1000J , 节点每次发给 Sink 节点的数据量 1Mb . 根据给定的节点数 , 在 1000 × 1000m2 的正方形区域内 随机 产 生 50 个 拓 扑 结 构 图 , 并 对 每 个 拓 扑 图 计 算 PEDAP、 PEDAP2PA 、 、 2W 、 2W 的网络生存时 LET Ratio Sum 间、 *均能耗和*均时延 , 然后计算其*均值 . 其中 , 网 络生存时间以 Sink 所完成的数据收集周期 ( DGC ,Data gathering cycle) 个数来表示 , 一个 DGC 是指从 Sink 节点 开始收集数据到它收集到网络中每个节点的数据所需 的时间 ; *均能耗 = 在网络生存时间内所有节点的总 能耗/ ( DGC 个数 3 节点个数) ; *均时延 = 在网络生存 时间内所有数据分组到达 Sink 节点的总跳数/ ( DGC 个 数 3 节点个数) . 图 4 比较了各算法的网络生存时间 . 其中 , 权值函 ( ( 4) 、5) 中的参数分别取为 α= 1 ,β= 1 和 λ= 0101 ,δ 数

组 REP 给 Sink 节点 ,REP 包括 : 节点的剩余能量 Re ( i ) 以及所要发送的数据量 k ( 比特) . Sink 在收到各节点的 REP 分组之后 , 运行 Ratio2W 算法 ( 或 Sum2W 算法) , 以 构建路由树 ( 由此可见 , 路由树是根据当时的节点剩余 能量及所要发的数据量动态构建出来的) . 在算法完成 ( 即路由树构建完成) 之后 ,Sink 节点采用洪泛方式将路 由树告诉网络中的所有节点 , 之后 , 所有节点根据收到 的路由树发送数据 . 由第 2 节假设 ( 1) ,Sink 节点知道整个网络的* 结构包括节点间的距离 , 于是在 Sink 收到所有节点发 来的剩余能量 Re ( i ) 、 所要发送的数据量 k 之后 , 可以 ( 计算出式 ( 4) 、5 ) 的权值 . 因此 , Ratio2W 算法与 Sum2W 算法可以在 Sink 节点实现 .

  为 验 证 算 法 有 效 性 , 我 们 将 Ratio2W 、 2W 、 Sum PEDAP 、 PEDAP2PA 、 等算法进行比较 . 我们不考虑节 LET 点竞争信道 、 数据分组出错 、 超时重发 、 信令传递 、 计 算、 数据融合等能耗 , 仅考虑无线通信能耗 . 在仿真时 , 取与文献 [ 11 ] 相同的参数 : Eelec = 50 ( nJ/ bit ) , Eamp = 100 (pJ/ bit/ m2) ,γ = 2 , 节点无线电通信半径为 200m , 节点

1044

            电 子 学 报

2009 年

个数) 最优 , Sum2W 的网络生存时间比 PEDAP2PA 略差 , 但超过了 PEDAP 、 . 从图 5 可知 , LET 能耗最小 , Ra2 LET tio2W 与 Sum2W 次之 , PEDAP 和 PEDAP2PA 的能耗相对 增大到一定程度 , 它的变化对网络生存时间与*均能    综上所述 , 在 Ratio2W 算法中 , 如果强调优化网络

   下面研究 Ratio2W 与 Sum2W 中各参数对网络指标 的影响 . 首先 ,研究 Ratio2W. 固定 β= 1 , 并让 α≥ , 分别 1 取 α= 1 , 3 , 5 , 7 , 9 , 得到图 7 与图 8 . 可以看出 : 在节点数 给定后 ,α越大 , 相应的网络生存时间 ( DGC 个数) 越小 ( 图 7) , 且*均能耗越大 ( 图 8) . 这是因为 : ( 1) 在 α≥ 1 α的增大 , 权值函数 ( 4 ) 中链路能耗的作用变 时 , 随着 大 , 相应地削弱了节点剩余能量在权值函数 ( 4 ) 中的作 用 , 从而降低了网络生存时间 ; ( 2) DGC 个数的减小 , 使 得每个 DGC 的能耗增加 . 从图 7 及图 8 可以看出 , 当 α

= 0199 . 由图 4 可以看出 , Ratio2W 的网络生存时间 ( DGC

耗的影响越来越不明显 . 此外 , 当 α< 1 时 , 我们得到 : 在节点数给定后 ,α越大 ( 即 α越接*于 1 ) , 相应的网 络生存时间越大 , 且*均能耗越小 ( 此处 , 我们省略实 验结果图) . 固定 α = 1 , 并让 β < 1 , 分别取 β = 011 , 013 , 015 , 017 , 019 , 得到图 9 与图 10 . 可以看出 :在节点数给定后 , β越接*于 1 , 网络生存时间越大 ( 图 9) , 但能耗也越大 ( 图 10) . 在取 β≥ 的情况下 ,β越大 , 网络生存时间越 1 小 , 且能耗越大 ( 此处省略实验结果图) .

较大 . 网络时延的比较如图 6 所示 , Sum2W 、 2W 的 Ratio 时延较低 ,比 PEDAP 、 PEDAP2PA 优 ; 与 LET 相比 ,Sum2W 更优 ,但 Ratio2W 的时延与 LET 接* . β 生存时间 , 则选择 α、 接*于 1 ; 如果强调优化能耗 , 则 选择 α接*于 1 ,β接*于 0 . 下面研究 Sum2W 的参数变 化对网络指标的影响 . 由于式 ( 5 ) 的参数是归一化的 , 即 λ+ δ= 1 , 因此 , 只对其中一个参数 λ对网络生存时 间、 能耗和时延方面的影响进行研究即可 . 固定网络中 的节点数为 25 , 令 λ取值 0101 , 0102 , …, 012 , 得到图 11 与图 12 . 可以看出 , 随着 λ的增大 , 网络生存时间出现 波动并呈缓慢下降趋势 ( 图 11 ) , 同时能耗也随着波动 ( 图 12) . 因此 , 在用 Sum2W 算法时 , 如果侧重于网络生 存时间 , 应该让 λ 取较小的值 ( 即接*于 0 的值) ; 否 则 , 取较大的值 ( 即接*于 1 的值) .

第    5 期

朱艺华 : 无线传感器网络优化生存时间的动态路由算法

1045

[ A ] . Proc. of the 33rd Annual Hawaii International Conference er Society , 2000 . 3005 - 3014 . on Systems Science [ C ] . Washington DC , USA : IEEE Comput2 [J ] . J ournal of Software , 2005 , 16 ( 11) : 1946 - 1957 . gregation in wireless sensor networks [ J ] . ACM SIGMOD Record , 2003 , 32 ( 4) : 66 - 71 . plication2specific protocol architecture for wireless microsensor networks [J ] . IEEE Trans . Wireless Commu , 2002 , 1 ( 4 ) : 660

[ 8 ] Chang J H , Tassiulas L . Maximum lifetime routing in wireless sensor networks [J ] . IEEE/ ACM Trans . on Networking , 2004 ,

12 ( 4) : 609 - 619 .

[ 9 ] Zhang Q , Xie Z P , Ling B , Sun W W , Shi B L . A maximum lifetime data gathering algorithm for wireless sensor networks

6  结束语    本文基于最短路径树 , 通过构造不同的权值函数 , 提出了 Ratio2W 与 Sum2W 两种路由算法 ,这两种路由算 法 ,能够延长网络生存时间并将能耗维持在一个经济 的水* . 同时 , 通过对算法参数的调整 , 可以*衡网络 生存时间与能耗 .
参考文献 :
[ 1 ] Tubaishat M , Madria S. Sensor networks : An overview [ J ] . IEEE Potentials , 2003 , 22 ( 2) : 20 - 23 . [ 2 ] Wang J , Howitt I. Optimal traffic distribution in minimum ener2 Communications Society , 2005 . 3274 - 3278 . [ 3 ] Liang W ,Liu Y. Online data gathering for maximizing network lifetime in sensor networks [ J ] . IEEE Transactions on Mobile Computing , 2007 , 6 ( 1) : 2 - 11 . [ 4 ] Cheng Z , Perillo M , Heinzelman W B . General network lifetime strategies[J ] . IEEE Trans . on Mobile Computing , 2008 , 7 ( 4) : and cost models for evaluating sensor network deployment

作者简介 :

IEEE 高级会员 , 中国计算机学会高级会员 , 中国电子学会高级会员 ,

[ 5 ] Hedetniemi S , Liestman A . A survey of gossiping and broad2 casting in communication networks [ J ] . Networks , 1998 , 18 ( 4) : 319 - 349 . [ 6 ] Haas Z J , Halpern J Y , Li L . Gossip2based Ad hoc Routing Communications Society , 2002 . 1707 - 1716 . cient communication protocol for wireless microsensor networks [A ] . Proc. of the IEEE INFOCOM [ C ] . New York : IEEE [ 7 ] Heinzelman W , Chandrakasan A , Balakrishnan H. Energy2effi2

gy wireless sensor networks [ A ] . 2005 IEEE Global Telecom2 munications Conference [ C ] . Washington DC , USA : IEEE

主要研究方向为移动计算 、 无线网络的协议 、 算法 、 性能分析与优化 , 在 IEEE Transactions on Wireless Communications》 IEEE Communications 《 《 、
Letters》 IEEE Transactions on Vehicular Technology》 Journal of Computer 《 、 《 、 Science and Technology》 电子学报》 计算机研究与发展》 IEEE 国 《 、 《 、 及

际会议论文集上发表学术论文 100 余篇 .
E2mial :yhzhu @zjut . edu. cn

为无线传感器网络路由算法 、 最优化理论与算法 .

484 - 497 .

为移动自组织网络及无线传感器网络路由算法 .

为无线传感器网络路由算法 .

全方位视觉传感器 、 普适计算技术 , 已经授权和公开的国家发明专利
70 多项 ,发表学术论文 90 余篇 .

[ 10 ] Tan H O , Korpeoglu I. Power efficient data gathering and ag2 [ 11 ] Heinzelman W B , Chandrakasan A P ,Balakrishnan H. An ap 2

- 670 .

[ 12 ] Zhu Y2H , Wu W , Leung V C M , Yang L . Energy2efficient sor networks [ A ] . ChinaCom 2008 [ C ] . Hangzhou , Zhejiang , China ,Aug. 25 - 28 , 2008 .
朱艺华  男 , 1961 年生于浙江玉环 , 博士 , 教授 , 博士生导师 , 沈丹丹   ,1983 年生于浙江杭州 , 硕士研究生 , 主要研究方向 女 吴万登   ,1983 年生于浙江瑞安 , 硕士研究生 , 主要研究方向 男 沈振伟   ,1982 年生于浙江嘉兴 , 硕士研究生 , 主要研究方向 男

汤一*   ,1958 年生于浙江杭州 , 博士 , 教授 , 主要研究方向为 男

tree2based message ferrying routing schemes for wireless sen2




友情链接: 时尚网 总结汇报 幼儿教育 小学教育 初中学习资料网