机会网络路由协议综述.doc

机会网络路由协议综述摘要：机会网路是最近涌现的一个新的研究热点，有着广泛的应用前景。相近的概念有间歇性连接ad hoc 网络，延迟容忍网络，稀疏ad hoc 网络，本质上都是同一类网络场景。路由协议是机会网络互联的关键，目前已提出了多种机会网络场景下的路由协议。本文主要对这些协议进行了分类介绍：确定性网络路由和随机网络路由。随机网络中的路由方案进一步分为传染性方案、基于历史或估计的方案、基于编码的方案、基于模型的方案和控制节点移动的方案。通过对这些协议方案的介绍，对比分析，总结了机会网络路由协议研究现状，提出了未来的研究方向。关键词：机会网络，ad hoc ，路由协议，间歇性连接1. 引言随着移动 ad hoc 网络（MANET）技术的不断发展，越来越被广泛地应用于各个领域。机会网络（opportunistic network）是一种特殊的移动ad hoc 网络。由于部署范围、无线通信技术的限制以及节点的动态移动，网络分割存在，网络连接频繁中断，移动ad hoc 网络中源结点和目的节点之间可能不存在同时的端到端的路径，这就是机会网络，又被叫做稀疏ad hoc 网络、ICN(Intermittently Connected Network)或DTN（Delay/Disruption ToleratedNetwork）1。机会网络的应用涉及到多种领域：军事应用、灾难恢复、水下传感器网络、无线传感器网络、Pocket Switched Network（PSN）、运输网络（Transportation Network）、野生动物监控、不发达地区网络部署等。对机会网络的研究正日益开展，例如1998 年启动的IPN（InterPlanetary Network）项目2，IRTF 的DTNRG 研究组3，欧盟FP6 的Haggle 项目4，普林斯顿大学的ZebraNet 项目5等，都对机会网络的协议与机制进行了广泛的研究。机会网络研究的关键的问题是路由转发。在机会网络中，移动节点稀疏分布，移动速度快，网络连接机会性地出现，源结点和目的节点之间可能始终不存在同时的端到端路径，传统的Internet 路由协议与MANET 路由协议都不再适用。因此需要设计机会网络路由，能使没有端到端路径的节点相互通信。本文主要对当前机会网络路由协议的研究进行分析和综述，第2 节描述了机会网络的特性，设计机会网络路由协议面临的问题，第3 节分类阐述了各种主要的机会网络路由协议的设计思路和特点，第4 节主要对现有方案进行分析总结，提出了新的研究方向，最后是本文的结束语。2. 面临的问题与挑战机会网络中节点分布较稀疏，且高速移动，节点之间偶然性地相互接触。网络拓扑动态变化，源节点与目的节点之间的连接间歇性地存在，甚至不存在。而传统ad hoc 网络的路由协议运行的前提是持续的端到端连通路径、较低的传输延迟、很小的丢包率，因此不能满足机会网络通信需求。而传统ad hoc 网络面临的限制如节点资源有限、通信信道不稳定等在机会网络中依然存在。所以机会网络路由协议面临的问题主要有：间歇性的网络连接；机会性的节点接触；网络分割；节点资源限制；无线通信链路。为了解决机会网络场景中的通信，必须利用节点移动产生的机会性的相互接触，所以把这种网络叫做机会网络。机会网络利用移动节点之间的机会性地接触，交换数据，最终将消息转发到目的节点。典型的通信流程如图1 所示，在时刻t1 源节点S 与目的节点D 之间不存在端到端路径，先转发给节点1，在t2 时刻节点1 移动到与节点2 接触，将消息转发给节点2，t3 时刻节点2 移动到与目的节点D 接触，消息发送到节点D，转发成功。机会路由中，为了处理间歇性连接，中间节点在没有合适的下一跳转发节点时，需要缓存消息较长的时间，移动等待传输机会出现之后再进一步转发，机会路由的模式由传统路由的存储-转发（store and forward）模式扩展为存储-携带-转发（store-carry-forward）1。机会网络路由协议设计的关键是，选择合适的转发节点和转发时机，将消息成功高效地转发，当出现网络分割时，选择具有最大可能成功转发的携带节点转发。3. 协议分类介绍目前对于机会网络的研究，已经提出了许多种路由协议如：传染性路由（EpidemicRouting）11、PROPHET（Probabilistic ROuting Protocol using History of Encounters andTransitivity）22、上下文感知的路由（Context Aware Routing）24、基于网络编码的路由31-32、Message Ferrying36-37等。这些协议采用不同的策略，都能实现机会网络中的路由。从不同的角度可以将这些路由协议分成不同的类别：根据基础设施有无可以分为有基础设施的和无基础设施的，有基础设施的有可以分为固定基础设施的与移动基础设施的，无基础设施的可以分为基于分发的和基于上下文信息的；根据采用的基本技术策略可以分为基于副本的和基于编码的6；根据网络特性可以分为确定性网络（deterministic）路由协议、随机网络（stochastic）路由协议，随机网络路由协议根据具体技术又可以分为基于传染性路由的方案、基于历史或估计的方案、基于模型的方案、基于编码的方案、控制节点移动的方案7。其中确定性网络应用场景具有一定的特殊性，随机网络路由协议更具有一般性。本文主要按照网络特性及具体技术对这些路由协议进行了分类介绍。3.1 确定性路由协议确定性网络指节点移动具有一定的规律，按照特定的路线移动的网络，如卫星网络。确定性路由方案，假定将来的节点移动和拓扑连接是已知的或可预测的，数据的发送路径从某种程度上是预先确定的，消息被转发之前就确定了转发路径。3.1.1MED 等几种路由协议MED 等协议8将DTN 中的网络信息定义成抽象的知识数据库（knowledge oracle），这些数据库用于封装特定的网络信息。网络信息可以分为4 个知识数据库：接触概括数据库，记录接触的总体统计信息；接触数据库，节点之间的实时接触信息；排队数据库，节点在任意时刻的缓存使用情况；流量需求数据库，记录现在和未来的流量需求。这类协议可以不使用网络信息数据库，可以使用部分或全部网络信息数据库，假定通信机会都是可预见性的，根据网络信息数据库计算得来的每段链路的开销函数，开销可能是随时间变化的，基于Dijkstra 算法，选择最小开销的路径。3.1.2Tree ApproachTree Approach9提出根据主机的移动信息，选择消息发送路径。分三种情况，第一种情况假定有全局的网络描述信息即主机移动性和可用性的时间函数，路径的选择通过建立一棵树，从源结点添加子节点，每个节点记录该路径上消息所经过的节点，最终的路径选择从树里面选择到目的节点时间最短（或跳数最小）的路径。第二种情况没有全局的信息时，节点之间相互交换信息，根据部分信息选择路径。第三种情况，在消息中存储消息传输的主机序列来改进第二种情况。3.1.3 Space time routing时空路由（Space time routing）10在空间和时间两个维度内探索路由信息。时空路由框架假定网络中的节点移动模式是可预测的，在无限或有限的时间范围内有一定的周期性。时空路由的基本思想是建立一个时空图模型，反映网络连接和拓扑随时间的动态演化。根据时空图模型，使用改进的Floyd-Warshall 算法来解决间歇性连接的动态网络中的最小延迟路由问题。建立一个时空路由表，考虑目的节点和时间来选择合适的下一跳转发节点。模拟结果表明时空路由能以最少的资源消耗，很高的概率选择时空中最小延迟路径。3.1.4 小结确定性路由主要适用于随时间演化的网络拓扑是确定性的，或者可预测的，如行星网络、公交车网络，可以事先调度选择最优路径，大多根据一定的网络信息，利用改进的最短路径算法实现。当网络拓扑的演化是随机的、动态的，确定性路由不再适用，应使用随机的路由协议，主要有基于传染性路由的方案、基于历史或估计的方案、基于编码的方案、基于模型的方案、控制节点移动的方案等。3.2 随机网络路由协议随机网络指网络拓扑随时间的演化是随机的、不可预知的。随机网络路由协议将消息逐跳向靠近目的节点的方向转发。这类路由协议更具有一般性，有更广的应用场景。现阶段针对机会网络路由协议大多属于这类协议。协议的关键是选择合适的下一跳转发节点，达到尽可能大的转发成功率，同时减小网络资源消耗。根据协议使用的具体技术可以分为基于传染性路由的方案、基于历史或估计的方案、基于模型的方案、基于编码的方案、控制节点移动的方案。3.2.1 基于传染性路由的方案传染性路由协议（epidemic routing）传染性路由协议（epidemic routing）11采用“存储-携带-转发”的模式，结点存储接收到的数据包，并在移动时携带，到遇到新的结点时转发数据包。与传染性疾病的传播类似，每次携带数据包的结点遇到新的不包含该数据包的结点，携带结点就传送一份数据报，“感染”这个新的结点，类似地，新感染的结点继续感染其它结点。目的结点第一次遇到感染结点时，接收数据包。每个节点都维护消息的缓存，建立一张消息的 hash 索引表，与每条消息关联，节点存储一个大向量，叫做概括矢量（summary vector），提示hash 表中的表项。当两个节点移动到传输范围之内后，首先交换概括矢量，对比概括矢量信息，请求不在自己缓存中的消息。如图所示，为节点A、B 交换数据过程，A 的概括矢量与B 的概括矢量取反，按位比较得到A 携带的B 没有的消息，向A 请求相应的消息。传染性路由协议能以较高的概率成功转发消息，但是消息按照范洪的方式转发，网络资源消耗大，比须采取一定的策略限制传染范围。改进的传染性路由基本的传染性路由协议，在网络资源足够的情况下，能够以最大的概率、最小的延迟将消息成功发送。但网络中资源以及节点资源往往是有限的，传染性路由资源消耗大，容易发生拥塞，引起丢包，不具有扩展性。必须对传染性路由进行改进，设计合适的机制限制消息的传染，寻求资源消耗与转发延迟的折衷。已提出了两种改进的传染性路由：分优先级的传染性路由（Prioritized Epidemic Routing,，PREP）12，自我限制的传染性转发（Self-LimitingEpidemic Forwarding）13。许多其它路由协议如概率路由1，spray 系列路由14-18等采取特定的策略限制传染，都是基于传染性路由的改进。PREPPREP12的基本思想是对待转发和删除的消息进行部分排序，主要基于4 个输入：到目的节点的开销、到源结点的开销、过期时间、产生时间，区分消息的优先级，按照优先级对消息进行转发、删除。模拟显示，PREP 的性能显着强于传染性路由协议和MANET 的路由协议代表AODV。SELFSELF13的设计目标是支持不同环境中应用（密集或者稀疏的），主要问题是适应性地控制传染范围、消息速率来防止拥塞。自我限制的传染性路由主要有如下元素： 1）通过适应性的衰减机制来控制TTL，2) 通过自我抑制（self-inhibition）和相互抑制（inter-inhibition）机制来控制转发速率，3) 控制源节点的消息产生速率。自我限制的传染性路由结合三种衰减机制，根据网络状态适应性地限制数据传染，通过vRate 控制数据发送速率，控制新数据包的产生。vRate 计算公式如下。vRate R arcvCountbsendCount 0 R0 为MAC 层接口发送数据包的速率，a 为相互抑制常数，b 为自我抑制常数，a、b 为小于1 的正数，rcvCount 与sendCount 根据特定的算法计算。vRate 随着收到或者发送的副本数量增加，指数衰减。Spray 类协议Spray routing14-18是引入的一类新的路由方案，向网络中注入“spray”一些消息副本，然后每个副本独立地向目的结点路由，设计机制限制副本的传输，同时保证消息发送成功率。提出了两种spray routing 方案：spray and wait 和 spray and focus 。spray and wait 包括两个阶段：spray 阶段，源节点产生的每条消息，传输L 个消息副本，被源节点或者可能是接收到备份的中间节点转发到L 条不同的中继上；wait 阶段，如果目的节点没有在spray 阶段找到，L 个携带消息备份的节点执行直接转发（只有当碰到目的节点才转发）。spray and focus方案的区别是将wait 阶段改进为focus 阶段，使用可用性这一度量来选择节点转发，结点A携带到目的结点D 的副本，当碰到新的结点B 时，只有当UB(D) UA(D) + Uth 时才向结点B 转发，其中Uth 为可用性门限，是算法参数。其它改进方案基于基本传染性路由方案的其它改进方案有 BIONET 项目提出的K-copy 转发19，参数K 定义了节点能够产生和分发的备份数量。Infostation 模型20提出了以类似基站的固定基础设施为基础的无线通信模型。 SWIM（The Shared Wireless Infostation Model）模型结合Infostation 模型与ad hoc 技术，允许移动节点之间相互通信21。小结基于传染性路由的方案基本不需要网络信息，适合于动态的随机网络。不同的方案提出了不同的策略限制传染范围，对基本的传染性路由进行了改进，限制了资源消耗，各种协议的比较如下表所示。其中spray and focus 路由结合了基于可用性的路由，也是一种基于估计的方案。Infostation 模型和SWIM 模型是利用的基础设施的基于传染性路由的方案。3.2.2 基于历史或估计的方案基于历史或基于估计的方案主要是根据节点移动、通信历史信息或其它上下文信息，估计或计算链路或端到端路径的转发概率，选择合适的下一跳节点转发，而不是盲目地向邻居节点转发，从而可以保证一定的转发概率，同时减少网络中消息副本数量，限制资源消耗。PROPHETPROPHET（Probabilistic ROuting Protocol using History of Encounters and Transitivity）22是一种使用历史记录的概率路由协议。PROPHET 定义了发送概率，代表结点能够将消息发送到目的结点的可能性。PROPHET 的操作与传染性路由相似，当两个结点相遇时，交换概括矢量和发送概率矢量，消息被转发给具有到目的结点的更高的发送概率的结点。发送概率有一定的计算方法，与结点的相遇历史记录相关，具有传递性。HiBOpHiBOp (History Based Routing Protocol for Opportunistic Networks) 25也是一种机会网络中基于上下文的路由协议，是一个通用的路由框架，管理和使用上下文信息来进行转发决策。CAR 主要先验式地探索节点能感知的目的节点的发送概率，HiBOp 更通用，不需要底层路由的支持，能够探索到节点未知的目的结点的发送概率；CAR 没有处理上下文信息的定义和管理，而上下文信息的定义与管理是HiBOp 的核心部分，CAR 更侧重于组合上下文信息来计算转发概率。MobySpace 路由MobySpace routing26-27是一个使用基于节点移动性模式建立的多维（high-imensional）Euclidean 空间（MobySpace）的通用路由框架。所引入的欧几里德虚拟空间或MobySpace 是DTN 领域中的一个广义的概念。MobySpace 路由方案的基本思想是使用MobySpace 作为工具来进行路由决策，决策的依据是与目的结点有相似的移动模式的节点为合适的下一跳节点。路由的过程是将数据包向移动模式与目的节点越来越相似的节点转发。在MobySpace 中节点的移动模式确定了在空间中的坐标MobyPoint，因此数据包的转发是向MobyPoint 与目的节点的MobyPoint 更近的节点转发。其它基于估计的协议MV28是一种学习节点的移动模式的来将消息从移动源节点转发到静止的目的节点。它维护节点之间的相遇（meetings）频率信息和节点访问（visits）特定位置的信息，使用这些信息来路由和分配缓存。过去的相遇频率用来计算通过一条路径的转发概率，根据转发概率在缓存中对消息进行排序转发。SEPR（Shortest Expected Path Routing）29建立了一个分布式的随机网络模型，提出了一个新的路由参数期望路径长度（Expected Path Length），基于期望路径长度，SEPR以类似链路状态协议的方式路由。SEPR 中的随机网络模型为一个带权图，如下图所示，边的权重代表两个节点接触的概率，概率的值为节点之间存在连接的时间与取样窗口时间的比值，实线表示有线连接，概率为1。每个节点都维护链路概率表，与其它节点交换信息。期望路径长度定义为路径上每段链路概率的倒数的和，采用Dijkstra 算法计算。MEED30（Minimum Estimated Expected Delay）是一种基于传统的链路状态协议的改进的路由协议。MEED 是一种MED 协议，使用节点之间的接触历史来预测节点的移动性，即每次接触的接触历史窗口时间内的连接时间和断开时间等信息。小结基于历史或基于估计的方案主要是利用不同的上下文信息，按照特定的公式，计算转发概率，选择相应的下一跳节点。不同方案的比较如下表所示。与基于传染性路由的方案相比，基于历史或估计的路由方案增加了计算开销或者网络信息的交换，但转发更有针对性，减少了资源消耗，有更好的扩展性、实用性。3.2.3 基于编码的方案机会网络路由协议根据基本策略可以分为基于副本的（replication based）和基于编码的(coding based)。基于副本的路由方案是最常用的机会路由方案，基本思想是在网络中注入一个或多个消息副本，依靠节点的移动性向目的节点分发数据。这类协议的缺点是范洪消息副本引起的开销，由于网络资源有限，基于副本的路由容易引起拥塞，降低性能，可靠性。基于编码的路由方案，消息发送前被转换成另一种形式，基本思想是在编码块中嵌入额外信息（冗余或解码算法），通过一定数量的编码块就能恢复出原消息。基于网络编码的路由基于网络编码的路由31-32基本思想是对转发的数据包应用网络编码进行编码产生新的数据包，和相应的编码向量，编码向量与数据包一起传输，当收到足够数量的数据包以后，目的结点就能解码，恢复出原数据包。基于网络编码的路由能以很小的开销向网络中的结点以较高的概率发送消息，特别适用的移动性，即使在极限情况下，如有较大的丢包率的稀疏网络，结点休眠时间较长的网络，在这些情况下概率路由效率较低。基于 EC（erasure coding）的路由基于 EC 的路由33的基本思想是，对消息进行erasure 编码，将产生的编码块分布在大量的中继上传输。每次中继只传输消息的一部分而不是整个消息的一个副本。这样分片传输可以控制每比特消息的传输开销。erasure coding 方案能使用固定的开销提供好的延迟保证，消除了由于不好的转发选择导致的大延迟，对于链路失效有更好的健壮性。基于 EC 的转发可以看作spray 路由的改进。基于EC 的路由适用于多种不同的环境，当节点接触时间分布服从重尾分布时，路由效率更高。H-EC6是一种混合的路由协议，结合了基于EC 路由的健壮性，保持了基于副本技术的性能优势。H-EC 能保持最坏延迟性能的稳定性，实现小延迟情景的高性能。小结基于编码的方案主要是基于网络编码和基于 erasure coding,。虽然基于编码的方案提高了健壮性，能适用于极限情况下，即节点移动程度低，网络延迟特别大的情景，但在网络延迟较小的情况下效率较低，且编码、解码增加了路由开销。3.2.4 基于模型的方案现实生活中节点移动都按照特定的模式，具有一定的社会属性，如高速公路上的汽车，人的日常生活，基于模型的方案主要是考虑节点移动的特点轨迹信息，描述节点的移动模式，这样中继节点的选择更精确，到达目的节点的概率更高。SOLAR 协议SOLAR（sociological orbit aware location approximation and routing）34协议是间歇性连接的移动ad hoc 网络中探索用户的移动性的路由协议。无线用户的移动记录研究表明用户移动主要集中在一些少量的有社会意义的地方（叫做hub），这些地方形成所谓的“社会轨迹”，如学生的日常生活轨迹一般为学校、家、商场等之间，学校内部又可分为教室、图书馆、食堂，家下一层次可分为卧室、起居室等。通过探索这方面的移动性描述，提出了一个hub 层次的路由方案SOLAR-HUB，两种用户层次的路由方案Static SOLAR-KSP 和DynamicSOLAR-KSP。其它基于模型的方案有 Model Based Routing（MBR）7，一种高速公路移动模型。利用世界模型来选择更好的中继节点，决定接收者的位置。3.2.5 控制节点移动的方案控制节点移动的方式主要根据通信需要通过主动地控制某些节点或特定节点的移动来进行路由，从而减小端到端延迟，提高系统性能。Data MULEs35是一种稀疏传感器网络收集传感器数据的节省能量的架构。Data MULEs引入了一种叫做MULE 的移动实体，负责从周围的传感器收集数据，缓存收集到的数据，最终转发给无线AP。这种架构可以大大减少传感器能量消耗，是一种经济有效的稀疏传感器网络互联方案。其它多种控制节点移动的方式如：Message Ferrying（MF）36-37，Virtual Mobile Node38，Li and Rus39，Snake 协议40，Runner 协议41。不同的方案有不同的控制方式，被控制的节点名称不一样。控制节点移动的方式，能够通过在网络中加入受控制的节点，相当于一种移动基础设施，来使间歇性连接的网络互联，提高网络性能。但这类协议需要部署受控的节点，适合特定的应用场景。4. 协议比较分析针对机会网络这一特殊的网络场景，已提出了上述多种机会网络路由协议。可以对这些协议从不同的角度进行分类，本