9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 理学 >>

基于邻居信息交换的机会网络低时延路由算法

基于邻居信息交换的机会网络低时延路由算法


第 9卷   第2期 3 2 1 年  2月   01

华 中 科 技 大 学 学 报 ( 然 科 学 版) 自 J uz o g U i . fSi .H ah n   nv o c.& T c ( aua c neE i o ) eh. N trlSi c  d in e t

V l3 o 2 o .9N . e . 01  F b  2 1

基于邻居信息交换的机会网络低时延路由算法
任   智   黄   勇   曹建玲   祖   力
( 重庆邮电大学 a 通信与信息工程学院; 移动通信技术重庆市重点实验室,重庆 4 0 6 ) b 005

— 摘要   提出一种以 E ie i ot g 为基础、 用 两 跳 邻 居 信 息 交 换 方 式 的 机 会 网 络 低 时 延 路 由 算 法— — 采 n pd mcR ui 并优先发送位于最 后 两 跳 L R N, D E 在分组索引的交换过程中交换两跳邻居信息从而增强对本地拓扑的掌握, 的数据分组; 同时在节点相遇感知过程中借助 E 性 CHO 消息从节点缓存中删除已到达目的节点 的 分 组 . 能 分 析结果表明, 经 典 的 E ie i 路 由 算 法 及 其 改 进 算 法 A E 相 比, D E 在 分 组 端 到 端 时 延、 组 传 送 与 分 R R L R N pd mc 成功率、 存储空间占用等方面的性能得到整体提升 . 关键词   无线网络;机会网络;路由算法;两跳邻居信息;交换 中图分类号  T 3 3.4   文献标志码  A   文章编号  1 7 - 5 2 2 1 )20 9 - 4 P9 0 6 14 1 (0 1 0 - 0 40

L wdlyru n   gr h  o p otns cnt ok o - e  ot ga oi mfro prui i ew rs a i l t t t i i b xh nig h e h or o d no m t n g yec a gn  eni b uh o  fr a o
R nZ i H a g  n  C oJa ln  Z   e  h u n Y g a   ni g uL o i i
( c ol fC mm n a o  n no m t nE gneig b K yL brtr f M bi o uia o aS h o   o ui t na dIfr a o  nier ;  e  a oaoyo   oieC mm n t n o ci i n l ci T c nlg  fC o gig C o gig U ies yo ot n  e c m-m n a o s C o gig4 0 6 , hn ) eh oo yo h n qn , h n qn   nvri  fP ssa dTl o t e ui t n , h n qn  0 0 5 C ia ci

A s at D E ( w dlyr uigbsdo  x h n eo w - o  eg b r o difr a o )w s bt c  L R N l - ea o t  ae  ne c a g  f oh pnih oh o no m t n a r o n t i n n t i i w- r p sdbsdo  pd mcR ui  d pi  x h n eo  oh pnih oh o  fr a o po oe  ae  nE ie i o t ga ot ge c a g  f w - o  eg b r o d no m t n.T o h pnih oh o no m t nw s x h n e    epoes f akt n e e x h n e oe h ne h o  eg b r o d fr a o  a  c a g d n h   cs    c e id xs c a g   n a c  e i i e it r op e t t   m seyo  clnt ok, n  e dt epc esa pocigt e  et a o sls w  o sf s y atr f oa e w r a dsn  h  akt p rahn  hi ds nt n att oh p  rt . l r i i i l r os t t M ro e ,nt epoes f e sn  no nee  o e , c om sa e  eeue   eee h  akt oe vr i h   cs    nige c u trdn ds eh  esgsw r sd odlt  epc es w ihh v ec e  et a o sfo  o e′b fe . efr a c eut h wt a  D E  upr hc  a erah dds nt n r m n ds ufr Pro m nersl s o  htL R N o te - i i s (d piern o ie  pd mcr uig) n fr s h  as a pd mcr uigag r h  n   E a at  a d mzdeie i o t o m   ec si l ie i o t  loi m a d AR R t l c e n t v n i tr so e vr ae e dt - n  ea , n   e oyo eha . e m  fdl eyrt , n - oe ddly a d m m r vr ed i K yw rs ieesnt ok ; p ot ns cnt ok ; o t gag r h s t oh p nih oh o e  od  wrls e w r s o p ruit  e w r s r ui  loi m ; w - o  eg b r o d i n t ifr a o ; x h n e no m t n e c a g i
[2 1 ]    机会网络 - 是 一 种 不 需 要 源 节 点 和 目 的 节 点之间存在完整 路 径, 用 节 点 的 移 动 带 来 的 相 利 4 泛, 本文选取的 E ie i 路由算法 [ ]就是 基于 此 pd mc

种机制 . 关 于 路 由 算 法, 多 学 者 做 了 大 量 的 研 许 究
[- ] 57

遇机会来实现网络通信的时延和分裂可容忍的自 组织网络, 对未来普适计算 具有重要意义 . 为了 解决因网络分裂和连接中断造成无法进行路由问 “ 题, 人们提 出 了 3 种 路 由 新 机 制: 接 收 -携 带 -转 发” 机制; 多次转 发 机 制; 点 两 两 成 对 交 换 信 息 节 机制 . 中 “ 收 -携 带 -转 发” 制 应 用 得 较 为 广 其 接 机
收稿日期  2 1 - 81 0 00 - 9.
[] 3

, 并取得了 一 些 有 价 值 的 研 究 成 果, 也 存 但

在不足 . 为此, 本文提出一种基于两跳邻居信息交 换的路由 算 法 L R N, 入 对 两 跳 范 围 内 可 用 D E 引 的本地拓扑信息, 首先当节点相遇时, 将对方写入 自 己 的 邻 居 链 表 并 对 其 进 行 维 护 管 理, 后 在 然

作者简介   任智(9 1 ) 男, 1 7 - , 教授, a : ezi q p . u c . E-m i rnh @c u te . l d n 基金项目   国家自然科学基金 资 助 项 目 (0 7 0 8) 6 9 2 6 ;教 育 部 留 学 回 国 人 员 科 研 启 动 基 金 资 助 项 目 (0 01 6 ) 21 - 51 ; 重庆市自然科学基金资助项目 (0 9 B 0 5 ;重庆市教委科研项目 ( J9 5 4 . 20 B 28 ) K002 )

第2期

 

 

任智, 等:基于邻居信息交换的机会网络低时延路由算法   

  

·9 · 5

E CHO 消息中 加 入 已 到 达 目 的 节 点 的 消 息 索 引 以消除网络中冗 余 副 本, 少 无 用 数 据 分 组 的 传 减 送. 同时通过相 互 交 换 邻 居 信 息 来 判 断 是 否 优 先 转发数据分组, 从而加快数据分组的传送过程, 降 低时延 .

步骤 6  节 点 接 收 到 R q et 消 息 后, 取 提 e us 邻居链表, 先将 目 的 地 为 对 方 节 点 的 邻 居 节 点 的 再发送剩余的请求分组 . 数据分组发送给对方, 1. 2 L R N 算法中的新机制 D E 两 a 两跳邻居信息交换 . 跳 邻居 信 息 交 换 机 . 增加了 对 两 跳 范 围 内 的 本 地 拓 扑 信 息 制的引入, 的利用, 使节点 能 够 获 取 对 方 节 点 的 局 部 网 络 拓 扑信息, 有助于节点更好地完成分组索引交换, 不 仅避免了节点 盲 目 地 发 送 数 据 分 组 给 相 遇 节 点, 加快了数据分组的传送过程, 也提高路由性能 . 当 b 数据分组发送顺序优化 . 2 个节点相遇 . 时, 节点会将目 的 地 为 对 方 节 点 的 数 据 分 组 发 送 给对方, 然后将对方写入自己的邻居链表 . 当节点 接收到 R q et消 息 时, 据 所 接 收 到 的 邻 居 链 根 e us 表, 把目的地为 对 方 节 点 的 邻 居 节 点 的 数 据 分 组 优先发送给对方, 便 在 随 机 的 连 接 次 数 和 短 暂 以 的连接间隔下, 高 分 组 传 送 成 功 率 和 降 低 分 组 提 的端到端时延 . 经 c 节点数据 分 组 缓 存 按 需 管 理 . 典 的 E i . p- d mc路由算法由于 没 有 对 已 到 达 目 的 地 的 数 据 ei 分组进行删除, 此 造 成 了 不 必 要 的 数 据 分 组 在 因 网络中传送, 不仅增大存储开销, 而且增大网络中 的负载 . 目前在 关 于 删 除 已 到 达 目 的 节 点 的 数 据
8 包方面, 已有用 HE L 消 息 携 带 信 息 [ ]和 创 建 L O [] 但 A K 消 息 传 递 信 息 9 等 方 法, 周 期 性 广 播 C

1  基于两跳邻居信息交换的路由算 法
D E   L R N 路 由 算 法 以 E ie i 路 由 算 法 为 pd mc 基础, 通过重新设计节点交换和缓存管理机制, 从 而达到降低时延和消除网络中冗余副本的目的 . 定义 1  消息索引指每个数据分组的唯一标 志信息 . 本文采 用 源 节 点 地 址 和 序 列 号 来 表 示 消 息的索引 . 定义 2  交 换 指 在 节 点 之 间 相 互、 向 传 递 双 结构或意义相同的信息 . 定义 3  邻居链表指每个节点记录本节点的 邻居节点信息, 它主要由目的地址、 下一跳地址和 生存周期组成 . 每个节点维护本节点的邻居链表, 其中生存周期值的设定需要结合节点通信范围和 运动模型 . 综合考虑节点相遇时的相对位置、 角度 和运动速度, 设置邻居链表的生存周期的计算为:

珔 珔 Tiei e= (3 / ) 式中 R 和v 分别为节点的通信 l tm f 槡R v ,
范围和节点相遇时的平均相对运动速率 . 1. 1 L R N 路由算法 D E L R N 路由算法具体步骤如下 . D E 步骤 1  每 个 节 点 周 期 性 地 广 播 H l 消 eo l 息, 该消息中包含本节点的网络层地址 . 步骤 2  当节点接收到对方节点广播的 H l e- 查找对 方 节 点 是 否 已 处 在 本 节 点 的 邻 l 消息时, o 若 则 即 居链 表 中, 是, 重 新 计 算 生 存 周 期, 当 前 时 间加 Tiei e; 否则, 对 方 写 入 邻 居 链 表, 算 生 将 计 l tm f 存周期 . 同时节点会维护本节点的邻居链表, 删除 然后 该 节 点 会 立 即 将 目 的 地 为 对 方 节 过期表项 . 点的数据分组发送给对方, 若没有相应的分组, 则 无该操作 . 接着将 已 到 达 目 的 节 点 的 数 据 分 组 的 消息索引装入 E 发送给对方节点 . CHO 消息中, 步骤 3  节点接收 到 E 将 CHO 消 息 后, 已 到 达目的节点的数 据 分 组 从 缓 存 中 删 除, 没 有 相 若 应的分组, 则直接执行步骤 4. 步骤 4  节 点 发 送 S 消 息, 消 息 中 包 含 该 V 本节点缓存的数据分组的消息索引 . 步骤 5  节 点 接 收 到 S 消 息 后, 过 比 较 通 V 确定自己没有而 对 方 拥 有 的 数 据 分 组, 将 这 些 并 数据分组 的 消 息 索 引 和 本 节 点 的 邻 居 链 表 装 入 R q et消息中发送给对方 . e us

而使用 A K 消 息 HE L 消息会增加控制开销, L O C 同样增大网络的开销和负载 . L R N 算法 采 用 在 E D E CHO 消 息 中 加 入 已 到达目的节点的数据分组索引来减少不必要数据 分组的传送, 同时减小传送 S 消息的开销 . 体 具 V 方式如下: 当判断节点相遇时, 只有当收到对方节 点广 播 的 H l 消 息, 前 后 2 次 收 到 H l 消 且 eo l eo l 息的时间间隔大 于 设 置 的 阈 值 时, 发 送 E 才 CHO 消息, 定 此 次 为 相 遇; 则 不 进 行 相 关 处 理 . 判 否 其 珔 中阈值 Tt 设 置 为: t = ( / ) 通 过 这 样 操 作, Th Rv , h 能够减少因周期性广播携带已到达目的地数据分 组索 引 的 HE L 消 息 所 带 来 的 开 销, 没 有 增 且 L O 加新的控制分组来传送 .

2  性能分析
2. 度量值定义 1  平均 端 到端 时 延 是 所 有 a 平均端到端时延 . . 数据分组到达目 的 节 点 时 的 平 均 时 延, 算 式 为 计

珡 T= ∑T ∑D , 中: i 表 示 第i 个 到 达 目 的 节 T i i 式
i =1 i =1

·9 · 6

  

华 中 科 技 大 学 学 报 ( 然 科 学 版) 自

 

第3 卷 9

点的数据分组的时 延; i 表 示 已 到 达 目 的 节 点 的 D 数据分组个数 . 平均跳数是所有数据分组成功 b 平均跳数 . .

间也不同, 这将涉及到节点通信范围、 运动模型等 因素 . 如图 1 所 示, D E 算 法 的 分 组 平 均 端 到 L R N 端时延在每个场景中均低于 E ie i 路由 算法, pd mc 只有在 节 点 运 动 间 歇 时 间t=5 稍 0s 时, 微 高 于 随着节点运动间歇时间越长, 种 算 AR R 算法 . E 3 珡 法的平均 时 延 T 在 总 体 上 都 有 上 升 的 趋 势, 当 E ie i 路由算法 间 歇 时 间 从 0s 上 升 到 2 0s 5 pd mc 时, 分组平均 时 延 由 3 9 8s 上 升 到 6 9 4s 7.1 1.4 , AR R 算法的分 组 平 均 时 延 由 3 3 6s 上 升 到 E 4.5 6 59 , L R N 算 法 的 分 组 平 均 时 延 由 1.2 s 而 D E 3 1 6s上 升 到 5 5 2s L R N 算 法 能 够 减 2.1 9.8 . D E 小时延的原因主要是优先发送目的地址为对方节 点和对方邻居节 点 的 数 据 分 组, 少 了 分 组 的 等 减 待时间 .

珨 到达目 的 节 点 的 平 均 跳 数, 算 式 为 H = ∑Hi 计
i =1 i =1

∑D , i 式中 H 表示到达目的节点的数据分组所经 i 节 c 节点平均缓存分组 数 . 点 平 均 缓 存 分 组 .

历的跳数 . 数是节点存储空 间 的 使 用 情 况 的 体 现, 算 公 式 计

珚 为 S= ∑S N , 中:i 表 示 节 点i 缓 存 的 分 组 式 S i
i V ∈

数; 为节点个数 . N 传送成功率是数据分组成功 d 传送成功率 . . 到达目的节点的个数占网络中源节点发送的总个 数的比例, 计算公式为

Drt = ae
2. 仿真分析 2 



∑Di
i =1

0 ∑Sj ×1 0%.
j=1



选取经典的 E ie i 路 由 算 法 和 AR R 算 E pd mc 法作为比较对象, 相 同 的 仿 真 条 件 下 比 较 分 析 在 它们和 L R N 路 由 算 法 的 时 延、 组 缓 存 使 用 分 D E 等性能 . 2. 1  仿真设置 2. 本 文 使 用 的 仿 真 软 件 平 台 是 O N T 4. P E 1 5. 5 个节点随机均匀分布在 15 0 m×3 0 m 的矩 0 0  0 1 形区 域 中; 动 模 型 为 R n o Ti 模 型 [0], 移 为 a d m r p 了避免节点 速 度 最 终 趋 向 于 0, 率 随 机 均 匀 取 速 值区间设为[ ,9 ( / ) 节点 MA 层和物理层 1 1 ]m s ; C 采用I E 8 2.1 标准, 最大 数 据 速 率 Vma =5 E E 0 1a 4 x M yes 节点的业务模型 为 随机选取 4 个节 点 bt/ . 5 作为源和目的节点, 其中每个节点向其他 4 个节 4 点发送 1 个 数 据 分 组, 数 据 分 组 发 送 间 隔 为 1 各 , 当通信范围大于 1 0 s 共发送 19 0 个数据分组 . 0  8 , 时节点都位于连通 节 m 时, 点 的 度 大 于 3.9 此 4 分区内 . 因此, 仅当 通 信 范 围 为 1 0 m 以 下 时, 才 0 是机会性网络环 境, 以 仿 真 中 节 点 的 通 信 范 围 所 , 设置为 5 邻居链 表 中 生 存 周 期 Tiei e为 4s 0m, l tm f 仿真时间为 40 0s  0 . 2. 2  仿真结果及分析 2. 以节点运动 状 况 作 为 自 变 量, 较 分 析 3 种 比 算法的分组平均 端 到 端 时 延、 组 平 均 跳 数 和 平 分 均缓存分组数性 能, 考 察 缓 存 空 间 的 大 小 对 数 并 据分组传送成功率的影响 . A.节点运动状况的影响 分组的 端 到 端 时 延 a 分组平均端到端时延 . . 包括分组在节点内存储、 携带和转发的时间, 这与 节点路由方式有关, 选择中继节点不同, 经历的时
图 2  分组平均跳数比较

图 1  分组平均端到端时延比较

珨 分 b 分 组 平 均 跳 数. 组 平 均 跳 数 H 可 以 反 .
映出分组平均 到 达 目 的 节 点 所 经 历 的 转 发 次 数, 因此选择合适的中继节点显得至关重要 . 从图 2 可 以 看 出, D E 算 法 的 分 组 平 均 L R N 跳数在每个场景中均低于 E ie i 路由 算法, 只 pd mc

有在少数情况下高于 AR R 算法 . 说明分组在 传 E 送过程中经历的 转 发 次 数 更 少, 而 有 利 于 分 组 从 更快地被送达目的节点 . 随着节点运动性减弱, 节 点之间的相遇机 会 减 少, 样 可 能 造 成 分 组 时 延 这 和丢包率增大, L R N 算 法 通 过 优 先 发 送 数 而 D E

第2期

 

 

任智, 等:基于邻居信息交换的机会网络低时延路由算法   

  

·9 · 7

据分组来降低分组平均跳数, 缩短时延, 使分组能 更快地被传送到目的节点 . 由 c 节点平均缓存分组 数 . 于 机 会 网 络 的 节 . 点需要储存和携 带 缓 存 中 的 数 据 分 组 运 动, 此 因 缓存分组数意味 着 储 存 开 销 数 量 越 少 越 好, 主 它 要受到业务模型、 存 管 理 策 略 和 数 据 分 组 传 输 缓 状况的影响 . 图 3 显 示, D E 算 法 的 节 点 平 均 缓 存 分 L R N 珚 组数( ) E ie i 路 由 算 法 和 AR R 算 法 均 S 较 pd mc E

存入 缓 存, 而 造 成 传 送 成 功 率 下 降, E 算 从 AR R 法也是这种原 因, 见 L R N 算 法 更 适 合 于 在 可 D E 节点缓存限制的情况下使用 . 仿真 结 果 验 证 了 L R N 相 对 于 E ie i D E pd mc 路由算法和 AR R 算 法 具 有 较 低 分 组 时 延 和 较 E 少的分组缓存占用 .
参 考 文 献

[ ]H a gC  , a     , siCZ.  uvyo p o - 1 u n   H L nK C T a   Asre   o pr f t n t  ew rs C] rceig    e 2 d ne - ui i nt ok [ ∥Poedn so t   n  tr sc fh 2 I nt nl C neec  n A v ne  no m t n N t a o a  ofrne o   d a cd Ifr a o   e- i i w rig a d A p ct n .Gn w n I E   rs , okn   n   pl a o s io a : E E Pes i i 2 0 : 7 -  7 0 8 16 216 7. [ ]熊永 平, 利 民, 建 伟, .机 会 网 络 [ ] 软 件 学 孙 牛 等 2 J. 报, 0 9, 0 1 : 2 - 3 2 0 2 ( ) 1 41 7. [ ]K m rS. hl n e o bqi u o p t g C] 3 u a  C a e gs ruiu o sc m ui [ ∥ l f t n Poedn s o  h  t  nent nl C neec  n rceig fte 5h Itra o a  ofrne o i N t okn   n   ev e . V lni :I E   rs , ew rig a d Sri s c a c e a E E Pes 20 : 2 - 3 0 9 5 65 5. [ ]V h a   ,Bc e   il 4 a dt A ekrD.E ie i ot gfrpr a y n pd mcrui  o at l

图 3  节点平均缓存分组数比较

c n etd a   o  ew rs C - 0 0 6[ ] u - o nce   d h c nt ok , S2 0 0 R .D r h m: u eU ies y 2 0 a D k   nvri , 0 0. t [ ] M n u   ,Sl m n M,L e G.E ie i ot g 5 u d rP e g a   i e  n pd mcrui i ui  ndl  oeatnt ok C ∥Po t a wt mm n yi e ytlrn ew rs[ ] r - ih ceig f 2 0 Ml ay C mm n a o s C ne - edn s o  0 8 itr   o ui t n   ofr i ci ec . a  ig : E E Pes 2 0 : - ne S nDe o I E  rs , 0 8 17. [ ]F n X  ,C e   6 a   M h n H.A y crn u p ot n yru s nho o so prui  o - t t gfrdlytlrn ew rs J .C ieeJ unl i  o e  oeatnt ok [ ] hns o ra n a c o lcrn s 2 0 , 7 4 : 9 - 0 fEetoi , 0 8 1 ( ) 6 87 2. [ ]W n   , h   T,i    ,t l A at e a d m- 7 a gX S uY  J Z G e  . d pi   n o n a vr ie  pd mcruigfrd r pintlrn ew rs zdeie i ot     su t   eatnt ok n o i o o [ ] rceig f h t nent nlC neec C ∥Poedn so  e5hItra o a ofrne t i o  M b e dh c n  S no  N t ok . Wui n oi  A - o a d esr ew rs l y M u ti : E E Pes 2 0 : 2 - 2 o nan I E  rs , 0 9 4 44 9. [ ] M tu a T,T kn   ( , ) pd mcruigfr 8 as d   aie T. p q - ie i ot  o e n s asl o uae   oi  dh cnt ok [] I E l preyp pltd m b ea  o ew rsJ . E E J unl nSlce  ra nC mm n a o s 2 0 , o ra   e td A es  o ui t n , 0 8 o e i ci 2 ( ) 7 37 3. 65 : 8 - 9

得到明显降低, 要 原 因 是 L R N 算 法 通 过 使 主 D E 用缓存管理策略, 除 已 到 达 目 的 节 点 的 数 据 分 删 从而减少了存储开销和控制信息的传递 . 组, B.节点缓存空间的影响 从图 4 可以看出, 当节点缓存空间比较小时, L R N 算法在传送成功率 上明显高于 E ie i D E pd mc

图 4  分组传送成功率比较

[ ]H ra   A, l eohK C, edn - o e  M. e 9 arsK  A m rt     BligryrE  D - lytlrn   oi   ew rs ( TMN ) c nrl d a oeat m b e nt ok D l s : oto e l f oig ns as   oi  ew rs C] rceig l dn   pre m b ent ok [ ∥Poedn s o i l i o h t nent nlC neec  n N t okn . fte4hItra o a  ofrneo   ew rig R uin I E  rs , 0 5: 1 01 9 e no : E E Pes 2 0 1 8 - 1 2. [0 B u e     , on v   T e a d mt pm dl 1 ] o dc Y L V joi M. h  n o   i  o e : J c r r sait , tt nr ei e a d pretsm lt n tbi sa o ayrgm , n  efc i ua o ly i i [] E EA J .I E / CM T a sc o s n ew rig rnat n o  N t okn , i 2 0 , 4 6 : 1 31 6 0 6 1 ( ) 1 5 - 1 6.

路由 算 法 和 AR R 算 法 . 节 点 缓 存 空 间 w 为 当 E 10 0时, pd mc 路 由 算 法 和 AR R 算 法 的 传 E ie i E  0 送成 功 率 Drt 分 别 为 5 9 3.9% 和 5 9 , 3.4% 而 ae L R N 算法的传送成功率为 7 5 , D E 1.6% 和前 二者 相比分 别 高 出 1 5 7.7% 和 1 6 7.2%. pd mc 路 E ie i 主 由算法的传送成 功 率 之 所 以 低, 要 原 因 是 该 算 法盲目地传送消 息 副 本 给 其 相 遇 到 的 节 点, 时 此 由于节点缓存空间受到限制,许多新的分组不能


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com