• / 3
  • 下载费用:2.98 积分  

MANET网络中一种节约能量的负载平衡路由.pdf

关 键  词:
manet 网络 一种 节约 节俭 勤俭 能量 负载 平衡 路由
资源描述:
MA N E T网络 中一种节约能量的负载平衡路 由 余雄伟黄传河周浩张媛媛罗瑛 ( 武 汉 大学计 算机 学 院 , 武 汉 4 3 0 0 7 9 ) E - ma i l : y u x w1 9 7 9 1 6 3 c o rn 摘 要 节 约 能 量 的 负裁 平 衡 路 由( P E L BR) 协 议 是 针 对 无 线 Ad h o c网络 提 出 的 一 种路 由 协 议 。P EL B R 定 义 了一 种 称 为节点活动度的标准, 节点活动度定义 了节点的通信 负载 。 在 P E L B R中, 路由发现 过程 中 目标 节点从候选路径 中寻找 负 裁最 小。 即路 径上 活动度之和最 小的路径 ; 而节点在传送数据 时适 当调 节能量 以保证 网络拓扑 结构 的连接 性 , 同时节约 电池 能 量 从 而 延 长 节 点 的 工作 时 间 。 关 键 词 无 线 A d h o c网络 能 量调 节 负裁 平 衡 活 动 路 径 文章编号1 0 0 2 8 3 3 1 - ( 2 0 0 5 ) 2 7 0 1 4 1 0 3 文献标 识码 A 中图分类号 m9 3 A P o we r - Ef fi c i e n t Lo a d - Ba l a n c e d Ro u t i n g f 0 r W i r e l e s s Ad Ho c Ne t wo r ks Yu Xi o n g we i Hu a n g Ch u a n h e Zh o u Ha o Zh a n g Yu a n y u a n Lu o Yi n g ( S c h o o l o f Co mp u t e r S c i e n c e , Wu h a n Un i v e r s i t y , Wu h a n 4 3 0 0 7 9) Ab s t r a c t :T h i s p a p e r p r o p o s e s a n o v e l r e a c t i v e P o we r - E ffic i e n t L o a d - B a l a n c e d Ro u ti n g ( P E L BR)p r o t o c o l f o r wi r e l e s s mo b i l e Ad h o e P EL B R d e f i n e s a me t r i c f o r rou t i n g k n o wn a s t h e d e g r e e o f n o d al a c t i v i ty t h a t d e fi n e s the c o mmu n i c a ti o n - l o a d o f a n o d e , I n P EL BR ro u t e d i s c o v e r y t a k e s c h a r g e o f s e a r c h i n g rou t e s a n d t h e n s e l e c t i n g a rou t e t h a t h as t h e l e ast t r a ff i c l o a d a n d a c t i v i ty o f n ode s Wh e n t r ans mi t t i n g , a n ode a d j u s t s i ts t r a n s m i s s i o n p o w e r t o k e e p the c o n n e c t i v i ty o f the n e t wo r k t o po l o g y and s a v e b a t t e ry powe r t o p r o l o n g t h e n od e s l i f e t i me , Ke y w o r d s :w i r e l e s s A d h o c n e two r k s , p o w e r a d j u s t m e n t , l o a d b a l a n c e , a c t i v e p a t h 1 引言 无线 A d h o c网络没有固定网络设施 。完全由移动 主机 构 成。这 种网络的建立快捷 、 灵活 。 不受有线网络的约束 , 可广 泛 用于灾难救助 、 偏 远地 区等无法得到有线 网络支持或某些 只是 临时需要通信但建立有线网络代价太大的环 境 具有广泛 的应 用 前景 。 A d h o c网络节点要 与其发射范围外的节点通信 。必须借 助中间节点 的路 由转发 即 A d h o c网络 的节点一方 面可以是 通信的发起或接收者 、 同时 又需要充 当路 由器 、 负责发现 、 维 护 到其他节点的路 由并为其转发数据 。A d h o c网络 的特征可 概 括 如下 【 l J ( 1 ) 动态拓 扑 : A d h o c网络 中节点的任意移 动 、 电池 耗尽 关机或损毁 、 节点间连接链路 由于信号干扰或传输条件变化 变 得不可用等都会造成网络拓扑的动态变化。 ( 2 ) 多跳通信 : 受 A d h o c网络信号传输 范围小的 限制 , 如 果 目标节点不在发起 节点的传输 范围之内则必须进 行多跳通 信, 借助其他节点进行 中继转发 。 ( 3 ) 带宽受限 、 链路容量动态变 化 : 无线链路的容量 比有线 容量低 , 且多接人 、 多径衰落 、 信号干扰及噪声又使无线链路 的 容量随时间而动态变化 , 链路的有效吞吐量 比空 中接 口的最 大 传输容量小得多 。 ( 4 ) 节点 能量受限 : 移 动节点是依赖 电池正常 的操 作 , 网络 中的节点要充当其他节点 的路 由器 , 节点能量耗尽将会改变 网 络 拓扑 。 进 而改变 网络性 能及网络寿命 , 因而实现节点 的低能 耗 非常重要 。 ( 5 ) 有限的安全性和服务质量 : 由于 A d h o c网络缺乏 固定 的网络基础设施进 行用户鉴权 和认 证 ,因此其安 全性很难 保 证 。多跳 网络 、 动态拓扑及动态链路容量使 服务 质量的保证变 得 也很 困难 。目前大 多数 A d h o c网络都 只能提供 b e s t e ff o r t 服务 。 2相 关 背景 设计无线 A d h o e网络的一个重要的问题是如何设计有效 的路由协议 以保证两个节点间的高质量通信 。 目前 已经有很多 针对无线 A d h o e网络的协议 , 这些协议基本上可 以分为两类 : 表格驱 动( t a b l e d r i v e n ) 的和基于需求 ( o n d e m and ) 的。基于表 格驱动 的路 由协议口 中, 每个节点都维护整 个网络最新的路 由 信息表 , 即使用 路径之前 就已经计算好 。 这一类协议 , 虽然到其 他所有节点 的路径都可 以直接从路 由表中获得 , 但 是会面临信 号拥塞 和能量消耗 问题 。因为无线 A d h o c网络 中网络带宽和 移 动节点的 电池 能量 都是极其 有限的 。而基 于需 求的路 由协 议p 卅 克服 了这些 局限 , 不是所有节点 都维护路 由信 息表 , 而是 在 源节点需要发送数据时才建立路 由路径。从 目前来看 , 无线 A d h o e网络中主要采用基于需 求的路由协议 。 在无线 A d h o e网络路 由协议 中最著名的是动态源路 由 ( D S R) t4 和按需式距离向量( A O D V) 协议翻 。 D S R t4 J 在源节点需要 作者简介 : 余雄 伟 ( 1 9 7 9 -) , 男 , 硕 士 , 主要 研究方 向为计算 机网络。黄传河 , 教授 , 博 士生导师 , 主要研究方 向为计算机 网络 、 分布并行处 理等 。 周浩 , 张嫒嫒 , 罗瑛 , 硕士研究生。 计算机工程与应用 2 0 0 5 2 7 1 4 1 维普资讯 发送 数据的时候通过源 路 由发现机制 找到从源到 目标 节点 的 路径 。A O D V 四 中源节点只维 护它们需要 的路 由信息表 , 当某条 路径失效 即 目标节点或某个中间节点不 可到达时 , 源节点必 须 通过路 由发现机制重新找到到达相应 目标节点的路径 , 同时更 新路 由表 在 D S R和 A O D V协议 中 当无 线 A d h o c网络 中节点的移 动减少时 从数据包 发送 率和和路 由开 销来看 。 网络 的通信 性 能会 提高 但数据包延时反而增 大19 1 , 这是因为这些 协议 有在大 量路径中重复使用少数相 同节点的趋势 。 从 而导致 媒体接入控 制( MA C ) 层 的拥塞 。 少数 节点承受 负载过重 , 结果 就是数 据包 延 时增大 。如果考虑到能量消耗 , 这些节点 的电池 能量 消耗 将 非常大 , 不仅使节点有效 工作时间缩短 , 而且 影响 了整个 网络 拓扑结构 的连接性 。实际上 , 现有 的协议 的一个 主要缺 点是在 路由建立 过程 中没有考虑负载平衡。 本文提 出了一种有效的路 由协议 采用 了负载平衡 的概念 , 同时考虑节 点电池能量 的节 约 , 即节约能量 的负 载平 衡路 由( P E L B R) 以减 少 网络 拥塞 、 平 衡网络负载并 降低端到端 ( e n d - t o e n d ) 延时 。 3系统 模型 与 问题定 义 对于给定的网络用无向图 G( , E ) 来表示 。 其 中 为节点 集合 , E为全部链路 的集合 。同时做如下定义 : 活动路径 : 从源节点 s向 目标节点 d发送数据包的路径 。 节点活动度 : 表示通过节点 的活动路径数 。 负载开销 : 路径P 上所有节点的节点活动度之和, 即: =A I EI 那么 P E L B R的路 由发现过 程的 目标 就是对于给定的源节 点 s和 目标节点 d 。 s V, d V, s d , 从 找到的候选路 径集合 P 中 , 选择具有最小负载开销的路径 P, 使得 : = mi n C A I k P l iEk 4 PELBR 4 1基本 思想 在 D S R和 A O D V协议 中 , 当无线 A d h o c网络中节点的移 动减少时 , 数据包延时反而增大19 1 , 这是因为这些 协议有 在大量 路径 中重复使用少数相 同节点的趋势 , 从 而导致媒 体接入控制 ( MA C ) 层 的拥 塞 , 少数节 点承受负 载过 重 , 结 果就是数据包 延 时增 大。因此 , P E L B R的基本思想就是记 录每个节点的负载情 况 , 在路 由选择时通过计算 候选路径上所有节 点的负载开销之 和 , 从 中选择具有最小负载开销的路径 。 另一方 面 。 在数据发送 过程 中。 P E L B R通过运用发送 能量 调节机制 在保证 网络拓扑 连接性的前提下节约 了节点 电池能量 。 4 2 P E L B R的具体 描述 在 P E L B R协议 中每个节点需要维护 2张表 : 路 由表 , 相邻 节 点表 。 ( 1 ) 路由表( R o u t i n g T a b l e ) : 存储接收到的路 由应答 ( R R E P ) 信息 。每条记录 由目标节 点 I D、 路 由计时器和到 目标节点的路 径三个部分组成 。 ( 2 ) 相邻节点表 ( N e i g h b o r T abl e ) : 存储本 节点所能 收听到 的节点 的信息 。每条 记录 由相邻节 点 I D和相邻 节点 计时 器 ( Ne i g h bor T i me r ) 组 成 。 l 4 2 2 0 0 5 2 7计算机工程与应用 并且还要维护 3个计时器 : 路 由计时器 , 邻接点计时器 , 节 点模式计时器 。 ( 1 ) 路 由计 时器( R o u t e T i m e r ) 记 录空闲路 由时 间 , 控制 路 由的生命期 ( L i f e T i m e ) 。 ( 2 ) 邻 接点计 时器 ( N e i g h bor T i m e r ) 记 录相邻节 点有 效时 间 控制相邻节点的生命期 。 ( 3 ) 模式计时器( Mo d e T i me r ) 。 P E L B R由 3个部分构成 : 路 由发现 路由维护 和能量控制。 4 - 2 1 路 由 发现 当源节点需 要发送数据包且 在它的路 由表 中没有有 效路 径 时 , 就调用路由发现过程。 源节点广播一个路 由请求( R R E Q) 消息 , 中间节点接收到 R R E Q后 , 将执行 以下操作。 i f( 路 由表中有到 目标节点的路径 )t h e n b e g i n 反向向 8发送路 由应答 ( RR EP ) 消息 ; 删除该请 求包, 不再往 前发送 ; e n d e l s e begin i f( 本 节点 I D在 R R E Q记 录的 I D序列 中)t h e n 删除该请 求包 , 不再往前 发送; e l s e begin 计算本节点的 A与 R R E Q中的负载开销之 和: 用计算 结果更新 RR E Q中的负载开销 : 将本节点 I D加入 RR E Q记录 的 I D序列继续广播该请求包 : e n d e n d 当 目标节点 d收到第 一个 R R E Q时, 在一个预定的路由选 择等待时间 内收集来 自同一 源节 点的 R R E Q从中选择一 个负载开销最小的路径活 动路径 。 d沿活动路径 的反向向 源节点 s发送路 由应答 ( R R E P ) 消息 。在 此过程 中 。 若链路 断 开 , 则在 断开点 R R E Q将被 放弃 , 下游节点 向 d发送路 由错误 ( R R E R ) 消息 , 收到 R R E R后 , d将再选择另一条不包含断开链 路 的负载开 销最小的路径 。s收到 R R E P后 , 按 活动路径发送 数据。 4 2 2路 由维 护 在无线 A d h o c网络中由于节点可 以 自由移动 网络拓 扑 结构的动态变化会导致路 由失效 。一旦源节点 、 活动路径上 的 中间节点或 目标 节点 移出了通信覆盖范 围 就必须找到一条替 代路径 。在 P E L B R中 , 节 点通过周期性地广播 h e l l o 消息探测 本地连接状 态。 在通信过程中 , 若源节点离开活动路径 则数据 包无法发送 到下游邻居节点 , 这 种情况下 , 源节点重 新调用路 由发现过 程, 重新 建立路径 ; 若 中间节 点或 目标节点 移出活 动 路径 。 则运用路 由维护机制修 复断开的链路 : 一旦下 一跳节点 不可达 , 上游节点广播一个 R R E R, 目标 节点收到 R R E R后 , 选 择另一条不 包含断开链路 的负载开销 最小的路径作 为活动路 径 , 源节点用新的活动路径继续发送数据 , 最 坏的情况下 , 即没 有 其 它替 代 路 径可 用 时 , 目标 节点 广 播 一个 R R E R。收到 R R E R后 。 源节点调用路 由发现过 程。 重新建立路径。 4 2 3能量 控 制 假设节 点能够调节发送能量 。在 P E L B R 中节点根据度 ( 邻居节点数 ) 来调节发送能量 。当节点为源或 目标节点 时 能 量 调节 至最大 : 当为中间节点时 , 调节能量以保证需要 的度 : 当 维普资讯 节点空闲超过一段时间 。 能量 调节 至最低 。 ( 1 ) 基 本 理 论 R a ma n a t h a n和 Ro s a l e s Ha i n提 出 了 L o c a l I n f o r ma t i o n No T o p o l o g y ( L I N T ) t 。在 L I N T中 , 他们得到 了如何 获得 在网络拓 扑中保持较好连接性 的结果 。 式 ( 1 ) 是传输丢 失函数 , 其中 n为 路 径丢失指数 。 与网络环境相关 , 通常的取值范围是 2 - 5 。r 是 距 离 , 是距 离阈值 。当距离小于 r th 时传 输丢失为常数 。 Z ( r ) = Z ( )i f r ( Z ( r ) = Z ( ) +1 0 n l o g l o ( ,r )i f r ( 1 ) t h 和 只 代表 目标传 输能量和 当前传 输能量 , 、 分别 表 示 目标 度和当前度 。假设节点均匀分布 , 则有 : 2 d c - -d en 叮 r d d = d e n 订 , : ( 2 ) d e n表示 节点分布密度 表示接收到的能量 , 则有 : P 一 ( z ( ) +1 o n l o g l o ( ) ) t h 一 ( z ( ) +1 0 n o g lo ( ) ) = 昭 ( 3) 由 ( 2 ) ( 3) 得 到 : P d + 5 川 。 g 。 ( ) ( 4 ) ( 2 ) 能量调节方 法 初始化都调到最小 源节点要发送数据或 目标节点接收数 据 时 , 调 至最 大。 中间节点 收到 R R E Q时根据( 4 ) 调节能量发 送 。 节点发送任何数据包( 不包括 R R E Q、 R R E P和 R R E R) U 将 模 式计时器 置 0 。 当模 式计时器 的值超过 阈值时 , 表示节 点 已 经 长时 间处于空 闲状态 , 则转入最小能量模式。 5性 能分 析 表 1 列 出了 D S R、 A O D V和 P E L B R时间复杂度 、 通信 复杂 度 和路 由选择方式的对 比。表中所列值均代表 最坏情况 。d表 示 网络直径 。 表示 网络 中的节点数 。 衰 l DS R、 A O D V、 P E L B R的性能对比 P E L B R的路 由发现过程与 D S R类似 只是 在 R R E Q 中记 录了负 载开销 ,所需 要维护的表格也只 比 D S R多一个邻居节 点表 通过 目标 节点选择负载开销最小的路径达到 了平衡负载 的 目的 能量调节机制在保证连接性的前提下节约 了节点 电池 能量 。 6结 论 本 文针对现有 的协议 在路 由建立过 程中没有 考虑负载平 衡 的缺点 , 提出了一种有效 的路 由协议 P E L B R。 P E L B R协议是 一 种按需式路 由协议 。适用于对延时要求 较严格的应用环境 , 同时延长整个网络的有效工作时 问。P E I R在通信过程 中采 取了能量调节机制 。 从局 部节约 了网络能量 消耗 : 节点活动度 的使 用平衡 了网络 负载 。 减少了网络拥塞 , 从 整体 上延长整个 网络 的有效工作时 间。 在节点移动不频繁的情况下降低 了端到 端延 时。( 收稿 日期 : 2 0 0 5年 1 月 ) 参考 文献 1 J Ma c k e r , S C o r s o n Mo b i l e A d h o e n e t w o r k s ( MA N E T) h t t p: w w w i e ff o r g h t m1 c h a r t e r s ma ne t -c h a r te r h t ml , I ET F Wo r k i n g Gr u p Ch a r t e r , 1 9 9 7 2 T I I s W e i Ch e n, Ma r i o Ge da Gl o b a l S t a t e Ro u t i ng: A Ne w Ro u t i n g S c h e me f o r Ad h o c Wi r e l e s s N e two r k s C I n : I E E E I n t e r n a t i o n a l C o n - f e r e n c e o n C o m mu n i c a t i o n s ( I C C) , l 9 9 8 3 Vi nc e nt D P a r k, M Sc o t Co r s o nTe mp o r a l l y -o r d e r e d r o u t i n g alg o r i t h m ( T O R A) v e r s i o n l f u n c t i o n al s p e c if i c a t i o n, I n t e rne t D r a f t d r a f t i n e ma n e t t o r a - s p e c o o t e x 1 9 9 7 一l l 4 D a v i d B H o h n son , D a vis A Malt s 1 1 Ie D y n a mi c S o u r c e mu t i n g P r o - t oe o for Mo b i l e Ad Ho c Ne tw o r k s 5 C E P e r ki n s E M Ro y e r Ad - Hoe On - De ma n d Di s t an c e Ve c t o r Ro u t - i n g C Mo b i l e C o m p u t i n g S y s t e m s and A p p l i c a t i o n s , P r o c e e d i n g s , WM- CS A 9 9, S e c o n d I EEE W o rks h o p o n, 1 9 9 9 0 2: 9 0 1 o o 6 I -S h y an Hwang, Ch e n g -Ch i n g Ye h, C hi u n g - Yi n g Wang L i n k s t a b i l i t y 1 o a d i n g b alanc e an d p o w e r c o n t m l b a s e d m u l ti p a th mu t i n g ( S B P MR) al g o ri t h m i n a d h oe w i t e l e s s n e two r k s C I n : T e l e c o m mu n i c a t i o n s , I C T 2 0 o 3, 1 0 t h I n t e rn a t i o n al Co n f e r e n c e o n 2 0 o 3; l: 4 O6 41 3 7 S ant a s h i l P alC h a u d h u r i D a v i d B J o h n s o n P o w e r Mo d e Sc h e d u l i n g for A d Hoe N e t w o rks C I n: P r o c e e d i n gs o f the 1 0 I E E E I n t e rna t i o n al C o n f e r e n c e o n N e two r k P m t o c o l s ( I C NP 0 2 ) 8 Y u Liu J a c k L 蛐 Mo b i l e and Wi r e l e s s C o m mu n i c a t i o n s N e two r k e 1 I n: 4t h I n t e rna t i o n a l Wo r k s h o p o n 2 o o 2 o 9: 3 6 3 3 6 7 9 I ETF MANE T W o r k i n g Gr u p Ch a r t e r h t t p: wwwi e t f o r g h t m1 c h a r t e r s ma n e t c h a r te r h t ml 1 0 R a m R a ma na t h an , Re g i n a Ro s ale s -Ha i nTo p o l o g y c o n t r o l o f mu l t i - h o p w i r e l e s s a d h oe n e two rks L 玎 E l e c t r n i c s l e t t e r s , 2 0 0 0; 3 6 ( 1 8 ) ( 上接 9 6页 ) 2 G Br a d s k i J Da v i s Mo t i o n S e g me n t a t i o n a n d P o s e Re c o g n i t i o n wi t h Mo t i o n Hi s t o r y G r a d i e n t s C I n: I E E E WA C V 1 0 0 2 0 0 0 3 Gr e g o r y D Ha g e r, W e n -Ch u n g Ch an g, A S Mo rse Ro b o t Ha n d -Ey e C o o r d i n a t i o n B a s e d o n S t e r e o V i s i o n J I E E E C o n t r 1 S y s t e ms Ma g a - z i n e , l 9 9 5 ; 1 5 ( 1 ) : 3 0 - 3 9 4 马颂德 , 张正友计算 机视觉【 M】 科学 出版社 , 1 9 9 8 5 He i k o Hi r s c h mu l l e r , P e r t e r R I n n o c e n t J o n Ga r i b a l d i Re al T i me C0 r e l a t i o n - B a s e d S t e r e o Vi s i o n w i th R e d u c e d B o r d e r E r r o rs J I n t e r n a t i o n a l J o u rnal o f C o mp u t e r Vi s i o n , 2 0 0 2 ; 4 7 ( 1 2 3 ) : 2 2 9 2 4 6 6 P A1 l e n B Yo s h i mi A T i mc e n k o Han d e y e c oo r d i n a t i o n for r bo ti c t rac k i n g and g r a s p i n g C I n: K H a s h i mo t o e d Vi s u al Scr v o i n g W0 r l d Sc l e n t i fic 1 9 9 4: 3 3 7 0 7 Gr e g o r y D Ha g e r, W e n-Ch u n g Ch an g, A S Mo r s e Ro bo t Han d -Ey e C oor d i n a t i o n B a s e d o n S t e r e o V i s i o n J I E E E C o n t r 1 S y s t e m s Ma g a - z i n e , l 9 9 5 ; 1 5 ( 1 ) : 3 0 - 3 9 计算机工程与应用 2 0 o 5 2 7 1 4 3 维普资讯
展开阅读全文
 温馨提示:
1、本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2、本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3、有的文档阅读时显示本站(www.999doc.com)水印的,下载后是没有本站水印的(仅在线阅读显示),请放心下载。
4、三九文库网仅提供信息存储空间,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
5、未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
6、本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
关于本文
本文标题:MANET网络中一种节约能量的负载平衡路由.pdf
链接地址:https://www.999doc.com/doc/3801.html
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

copyright © 2016-2020 999doc网站版权所有

经营许可证编号:苏ICP备2020069977号


本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。三九文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知三九文库网,我们立即给予删除!


收起
展开