机会网络中基于接触间隔时间改进的路由算法

1.1机会网路典型路由算法研究机会网络是一种节点分布稀疏、网络拓扑结构不断发生变化的间歇性通信网络。

数据以多跳方式，采用“接收-携带-转发”的机制传输给目的节点，如果中间节点没有合适的可供传输的路径或节点，则无法立刻将数据转发出去，而是保存在节点缓存中，等到出现合适的传输机会之后，再将消息转发出去。

而现有的有线网络和无线自组织网络中基于TCP/IP 协议的端到端路由协议已经不再适用于机会网络。

因此，如何在机会网络中寻找一条时延尽可能低、消耗尽可能小、传输成功率尽可能高的路径，将消息准确传递到目的节点，是机会网络中一个极具挑战性的问题。

从不同角度出发，机会网络的路由策略有不同的分类方式[27]。

按照消息传输方式可分为洪泛路由策略和转发路由策略；按照路由所使用报文的份数可分为单报文路由策略和多报文路由策略；按照节点所掌握的网络拓扑信息还可分为确定性路由策略和随机性路由策略。

本文按照消息传输方式不同将目前的路由协议分为如下几类：直接传输路由策略(Direct Transmission)、基于泛洪的路由策略(Flooding Based)、基于情景感知的路由策略(Context Based)、基于社区的路由策略(Community Based)、基于编码的路由策略(Coding Based)、基于预测的路由策略(Predicted Based)。

1.1.1基于副本或泛洪的路由策略直接传输(Direct Transmission，DT)路由在运行过程中，不产生消息副本，消息一直保存在源节点缓存中，直到源节点在运动过程中遇到目的节点，才将消息转发给目的节点。

DT 路由协议由于没有进行路由优化处理，也没有产生任何副本消息，因此传输时延很大。

为了减少网络中消息的传输时延，研究人员提出了基于泛洪的路由协议，通过消息携带节点产生大量的消息副本，转发给每一个相遇的节点，完成消息的投递。

根据网络中消息副本数量的多少，还可以将基于泛洪的路由分为两大系列：泛洪路由和限制性泛洪路由。

关 系分别为 ： ＝ Ｔ Ａ ｔ ） ， ＝ （ ； Ｃ 是 源节点 ５到 目 的节点的平均发送速率 ，机会网络的链路连接间断
特 性描 述如 图 １ 所示 。一些 相关 术语 描述 如下 ：
・
性 的研究 成果 相对 较少 。 Ａ． Ｃ ｈ ａ ｉ ｎ ｔ ｒ ｅ ａ ｕ等 人通 过对 四
在Ｂ 通信 范 围 内
在Ａ通信 范围 内
在Ａ通信 范 围内
在Ａ 通 信 范围 内
Ｉ ＿ （ ＂ ） ＿ ＋ 卜 ｒ ）
， ”、
ｃ ｒ ＋ １ ＋
Ｌ１ 、
＋１
图 １ 机会 网络的链路连接间断特性
…
…
兰 垒 曼 爨 整 墨 苎 Ｏ
Ｒ
在Ｓ Ｐ Ｍ Ｂ Ｍ 移 动模 型基 础上 ，节 点也 可 以按 照 预先
Ｖ ／ ｎ ） 可以定义为节点 Ａ和 Ｂ的第 １ １ 次接触周 期时长 ，它包括接触 间隔时间 （ 和接触持续时
间 （ ” ） 两部 分 ， 也表 示从 ｎ次 相遇 时的接 触结 束 时
设定好的路 由进行运动 ， 如公交路线 、 地铁路线和人 行道路等 ， 这就是 Ｒ Ｍ Ｂ Ｍ移动模型嘲 。
２ 机会 网络 无 线链 路 间 断 连接 特 性
在机会 网络 中 ，节点之间 的通信是通 过接触
㈣ 表示这一对移动节点 Ａ和 Ｂ第 ｎ 次接触 时的接触持续时间 ，即从第 ｎ 次接触结束时刻 ） 到第 ｎ次接触开始时刻 （ ） 之间的接触持续时间 ，
在Ｂ通信 范 围内
在Ｂ 通 信 范围 内
一
次接触能传输多大的数据包。这为研究者设计机
络采集到的数据 ，分析 了现实环境 中机会 网络的链 会 网络 的缓 存 管 理 和 拥 塞 控 制 提 供 重 要 的理 论 依 路统计 特性 ； Ｃ ｈ ｅ ｎ ｇ — Ｌ ｉ ｎ Ｔ ｓ ａ ｏ ￣ 等人在随机路径点模 据 。 型下 ，通过数学推导得 出了节点间的链路持续时间 （ Ｌ ｉ ｎ ｋ Ｄ ｕ ｒ ａ ｔ ｉ ｏ ｎ ） 的分布函数 ， 并证明了链路持续时间 由节点的相对速度和通信半径决定。 如图 ｌ 所示 ， 汀（ ｎ ） 代表 同一对移动节点 Ａ和

［ ｂｔａｔ ａｅ ｎ ｅ ｉ ｕａ ｏ ｆ ｕ ａ ｏ ｅ ｎ ｈ ｖ ｒｎ ｅｌ ｉ ， ｉ ｐ ｐｒ ｕ ｔ ｔ ｅ ａ ｚｓ ｉ ｏ ｐ ｒ ｎ ｔ ｔ ｏｋ ｏ ｔ ｇ Ａｓ ｃ ｒ ］Ｂ ｓｄ ｍ ｌ ｉｎ ｍ ｍ ｖｍｅｔ ｅａ ｉ ａ ｃ ｙｔ ｓ ａ ｅ ｑ ａ ｉ ｉ ｌ ａ ｌ ｅ ｘ ｐ ｏｔ ｉ ｃ ｅ ｒ ｕ ｎ ｏｔ ｓ ｈ ｔ ｏｈ ｎ ｂ ｏ ｉｒ ｔ ｈ ｎ ｔ ｖ ｙ ｎ ｙ ｓ ａ ｕｓ ｎｗ ｒｉ ｉ
１ 概述
机会 网络 是一种不需要在源 节点和 目的节点之间存在 完
Ｄｒ ｔ ｅ ｖｒ ｉｃ Ｄ ｌ ｅ ｅ ｉ ｙ算法源节点仅在遇到 目 标节点 时将报文
交付给下一个节点 ，而 Ｆｒ ｏ ｔｃ 算法源节点将报文交付 ｉ ｔＣ ｎａｔ ｓ 给它遇到的第 １ 个节点。
整路径 ，利 用节点移动 带来 的相遇机 会实现 网络通 信的、时 延和 分裂可容忍的 自组织 网络 ｕ。机 会 网络不 同于传 统的多 Ｊ
Ｐｅ ｆ ｒ ａ ｅＡｎａ ｙ ｉ ｆ ｐ ｃ ｌ ｒ ｏ ｍ ｎｃ ｌ ｓｓｏ Ｔｙ ｉａ ｕ ｉ ｇＡｌ ｏ ｉｈ Ｒｏ ｔ ｇ ｒｔ ｍ ｎ ｉ ｐ ｏ ｔ ｎ ｓ ｉ ｔ ｒ ｎ Ｏ ｐ ｒ ｕ ｉｔｃＮｅ ｗｏ ｋ
Ｓ ＵＮ ｉ ｎｚ ＬＩ Ｎａ －ｕ Ｚ Ｊａ ．ｈｉ ， Ｕ ｉｒ ｉ ＨＡＮＧ ｎ －ｉ ＨＡＮ ｏ ｇ ｍｉ ｇ ， ， Ｙｉｇ ｘｎ ， Ｚｈ ｎ － ｎ ＣＨＥＮ ｎ Ｄａ
［ ｅ ｏ ｄ ］ｏ ｐｒ ｎ ｔ ｔ ｏ ； ｕ ｎ ｇ ｒｈ ｎ ｄ ｏ ｉｔ ｍｏ ｅ ｍ ｔｃ Ｋ ｙｗ ｒ ｓ ｐ ｏ ｕ ｉ ｃ ｅ ｒ ｒ ｔ ｇ ｌ ｉ ｍ；ｏ ｅ ｂｌ ｄｌ ｅ ｔ ｓ ｎ ｗ ｋ ｏｉ ａ ｏ ｔ ｉ ｍ ｉ ｙ ； ｒ ｉ

2013年9月Journal on Communications September 2013 第34卷第9期通信学报V ol.34No. 9 基于网络编码的机会网络高效路由算法任智，刘智虎，姚玉坤，陈前斌（重庆邮电大学移动通信技术重庆市重点实验室，重庆400065）摘要：针对采用Epidemic机制的机会网络路由算法在数据分组传送阶段存在通信冗余的问题，提出了一种基于网络编码的高效路由算法——NCBER(network-coding-based epidemic routing）。

NCBER在传送数据分组的过程中使用主动异或网络编码和多播，并取消了Request（请求）控制分组，从而减少数据分组的转发次数和控制分组数量，降低网络开销，缩短分组传输时延。

理论分析和仿真结果表明，NCBER算法在网络开销和数据分组端到端时延性能方面优于经典的Epidemic路由算法及其改进算法MRRMR（message redundancy removal of multi-copy routing），并且使数据传送成功率保持在100%。

关键词：机会网络；路由算法；网络编码；多播；网络开销中图分类号：TP393.4 文献标识码：A 文章编号：1000-436X(2013)09-0016-08 Efficient routing algorithm for opportunisticnetworks based on network codingREN Zhi, LIU Zhi-hu, YAO Yu-kun, CHEN Qian-bin(Chongqing Key Lab of Mobile Communications Technology, Chongqing University of Posts and Communications, Chongqing 400065, China) Abstract: To address the problem in opportunistic network that the existing epidemic-mechanism-based routing algo-rithms incur redundant communication overhead during the transmission of data packets, an efficient routing algorithm based on network coding, called NCBER (network-coding-based epidemic routing), was proposed. During the transmis-sion of data packets, NCBER adopts an active XOR coding operation and multicast, and cancels the transmission of the Request control packets, so as to reduce the time used to transmit data packets, as well as the number of control packets.As a result, NCBER cuts down the network overhead and shortens the end-to-end delay of data packets. Theoretical analysis and extensive simulation results show that NCBER outperforms the classical epidemic routing algorithm and its improvement called MRRMR (message redundancy removal of multi-copy routing) in terms of the network overhead and the end-to-end delay, while still keeping the delivery rate at 100%.Key words: opportunistic network; routing algorithm; network coding; multicast; network overhead1引言机会网络(opportunistic network)[1]是一种具有间断或部分连接的网络拓扑，利用节点移动带来的相遇机会实现通信的时延和断裂可容忍的无线移动自组织网络。