一种基于效用转交的多副本机会网络路由协议

《一种基于效用转交的多副本机会网络路由协议》由会员分享，可在线阅读，更多相关《一种基于效用转交的多副本机会网络路由协议（53页珍藏版）》请在装配图网上搜索。

1、一种基于效用转交的多副本机会网络路由协议摘要机会网络具有延时容忍网络的一般特征，它是利用节点移动带来的相遇机会实现通信的新型自组织网络模型，其目标是为了解决频繁间断网络中的数据通讯问题。机会网络中通常由于节点移动、稀疏、能量和存储受限等原因导致网络的分割，源节点和目标节点位于不同的连通域而导致传统的无线自组网路由协议无法有效运行。本文在分析机会网络关键技术和主要三种多副本路由协议的基础上，提出了一种新的路由协议基于效用转交的多副本路由协议，并用仿真平台the ONE对该路由协议的性能进行评估，仿真结果表明，相对SprayAndWait、Prophet和Epidemic这三种路由协议，该路由协议

2、具有较高的报文成功递交率和平均网络延时，以及较低的网络开销。关键词: 机会网络 路由协议 效用转交 多副本AbstractOpportunistic Networks is a novel self-organizing network model with the general characteristics of the Delay Tolerant Network and it utilizes the encounter opportunities arising from node movement to implement communications and aims at r

3、esolving the data communication problem for the frequent interruption network. In Opportunistic Networks, nodes usually form a disconnected network due to nodal mobility, low density, limited energy and storage, etc. The source node and destination node being located in different connectivity domain

4、s leads to the result that conventional communication protocol of wireless ad hoc networks can not be effectively run in Opportunistic Networks. After introducing the multiple-copy routing protocol and Key technologies in Opportunistic Networks, this paper proposes a Spray and Transfer using History

5、 of Encounters and Transitivity Routing Protocol. Then we use The Opportunistic Network Environment simulator to assess performance of this new routing protocol. Simulation results show that the improved routing protocol has better performance of delivery ratio，average latency ,routing overhead and

6、delivery utility ,compared with SprayAndWait, Prophet and Epidemic.Key Words: Opportunistic Networks、routing protocol、Transfer using History of Encounters and Transitivity、multiple-copy目录摘要IAbstractII第一章 绪论11.1 研究背景11.1.1 机会网络的提出11.1.2 机会网络的定义11.1.3 机会网络的研究现状21.2 论文选题的意义31.3 论文的组织3第二章 机会网络中路由协议的关键技术

7、42.1 概述42.2 移动模型52.2.1 随机移动模型52.2.2 基于地图限制的移动模型52.2.3 基于社区的移动模型62.3 拥塞控制72.4 缓存策略82.5 转发机制82.5.1 基于编码的转发92.5.2 基于复制的转发92.5.3 基于相遇预测的转发102.5.4 基于链路估计的转发102.5.5 基于上下文信息的转发112.5.6 效用冗余混合的转发112.5.7 基于节点主动运动的转发112.6 本章小结12第三章 机会网络中多副本路由协议133.1 单副本路由协议和多副本路由协议的比较133.2 多副本路由协议133.2.1 Epidemic133.2.2 Spray

8、and Wait143.2.3 PRoPHET173.2.4 三种协议的比较183.3 本章小结19第四章 基于效用转交的多副本路由协议204.1 路由协议的提出204.2 路由协议的具体设计214.2.1 基于时间尺度的效用路由算法214.2.1.1 递交预测值的计算214.2.1.2 基于时间尺度的参数估计244.2.2 基于期望平均效用的散发策略264.2.3 基于当前递交预测值大小的转交递交策略294.2.4 基于确认机制的冗余消息删除策略304.3 路由协议整体设计324.4 本章小结32第五章 基于效用转交的多副本路由协议性能评估335.1 仿真平台 ONE 介绍335.1.1 O

9、NE 概述335.1.2 模拟流程335.1.2 节点更新345.1.3 传输消息345.1.4 报表解读355.2 网络性能评估标准355.2.1 报文成功递交率 (delivery_prob)355.2.2 网络开销 (overhead_ratio)365.2.3 平均传递延迟(latency_avg)365.2.4 投递效用(Delivery Utility)365.3 基于效用转交的多副本路由协议性能评估375.3.1 仿真环境设置375.3.2 仿真结果分析385.4 本章小结43第六章 总结与展望446.1 研究内容总结446.2 展望44参考文献46致谢48V第一章 绪论1.1

10、研究背景1.1.1 机会网络的提出大量低成本、具备短距离无线通信能力的智能设备的出现推动了无线自组织网络用的迅速发展.例如, 放置在动物身上的传感器组成移动传感器网络收集动物迁徙数据；各种配备蓝牙或Wi-Fi接口的手持电子设备,如MP3播放器、手机、PDA等自组成网络以实现数据共享或协作访问互联网行驶；在公路上带有智能设备的车辆自组成车载网络,实现交通故预警和其他道路安全应用等。在上述的各种实际自组织网络应用中,节点移动、节点稀疏、射频关闭或障碍物造成信号衰减等多种原因都可能导致网络大多数时候不能连通。这种网络环境中,传统的MANET(mobile ad hoc network)通信模式无法有

11、效运行。因为MANET在传输用户数据之前,需要预先通过AODV(ad-hoc on-demand distance vector)或DSR(dynamic source routing)等路由算法建立通信端点之间的路由,并将数据分组按照节点路由表中确定的下一跳节点顺序转发到目标节点。这种工作模式隐含一个重要的假设:网络大部分时候是连通的,任一节点对之间存在至少一条完整的端到端通信路径。而在前述网络中,在一个特定时刻,网络可能被分割成不连通的子区域,源节点和目标节点位于不同的连通域而导致MANET路由协议不能发现去往目标节点的路由。然而,信源和目标不存在完整连通路径并不意味着不能实现通信,由于节

12、点的移动,两个节点可以进入相互通信范围而交换数据,机会网络1就是利用这种节点对之间的逐跳转发将数据从源节点传输到目标节点。机会网络不要求网络的全连通,更适合实际的自组网需求,且对于实现未来普适计算具有重大影响,因而近年来引起了科研人员的密切关注。在网络领域相关著名会议上,SIGCOMM,MOBICOM,INFOCOM,MOBIHOC等,相关的重要研究成果逐年增多。此外,还专门成立了一些研讨会,如Mobicom的CHANTS,MobiSys的MobiOPP,ICDCS的DTMN以及PERCOM的ICMAN等,供研究者交流。1.1.2 机会网络的定义目前机会网络还没有一个统一的定义,本文按照文献1

13、给出描述性定义进行描述:机会网络是一种不需要源节点和目标节点之间存在完整链路,利用节点移动带来的相遇机会实现通信的自组织网络。图 1.1 机会网络示意图图1.1是一个机会网络示意图,t1时刻源节点S希望将数据传输给目标节点D,但S和D位于不同的连通域而没有通信路径,因此,S首先将数据打包成消息发送给邻居节点3,由于3并没有合适的机会转发下一跳节点,它将消息在本地存储并等待传输机会,经过一段时间到达t2时刻,节点3运动到节点4的通信范围并转发给节点4,在t3时刻,节点4将消息传输给目标节点D,完成数据传输。机会网络的部分概念来源于早期的延迟容忍网络DTN(delay tolerant netwo

14、rk)2研究。DTN最初是容迟网络研究组(DTNRG)为星际网络IPN(interplanetary network)通信而提出来的,其主要目标是支持具有间歇性连通、延迟大、错误率高等通信特征的不同网络的互联和互操作,如互联Internet和传感器网络、移动自组织网络等3。DTN网络体系由多个底层运行独立通信协议的DTN域组成,域间网关利用“存储-携带-转发”的模式工作,当去往目标DTN域的链路存在时转发消息,否则,将消息存储在本地持久存储器中等待可用链路。机会网络可以看成是具有一般DTN网络特征的无线自组网。1.1.3 机会网络的研究现状机会网络自从出现以来得到了极大的研究关注，目前的研究热

15、点主要集中在以下几个方面1:(1)路由协议的研究。路由协议一直是机会网络中的研究重点，网络中的路由协议要完成将数据报文成功地传输到目的节点的任务，同时，还要尽可能减小传输延时，减小对网络节点内存的消耗，减小对网络带宽的消耗。研究人员正在努力研究开发满足上述要求的路由协议并取得了一定的成果。(2)移动模型的研究。移动模型是指网络中的节点移动方式，节点的移动方式对于网络中的数据通信具有重要的影响。不同的应用环境下，节点可能具有不同的移动方式，节点的移动可能是随机的，也可能是具有一定规律的。节点的移动模型对于机会网络中的路由协议的设计具有一定的指导意义。(3)安全性研究。安全性的保证是整个网络应用的

16、前提，所以随着机会网络其他方面的研究发展，以及机会网络的实际部署，安全性方面的研究得到了逐步关注。目前机会网络中的安全机制研究还处于起步阶段。1.2 论文选题的意义很多应用领域都无法建立结构化的全连通网络,导致传统的多跳自组织网络协议无法运行,而机会网络能够更好地满足这些应用需求。机会网络已经成功应用于车载网络、偏远地区网络传输、野生动物追踪、手持设备组网等领域。尽管机会网络已经取得一些应用，但当前对机会网络的研究大多处在理论和仿真的阶段。机会网络路由协议要保证在网络大多数时候不能连通的情况下数据报文能够正常传输，同时，还要尽可能减小传输延时，减小对网络节点内存的消耗，减小对网络带宽的消耗。当

17、前和将来最主要的任务是在机会网络体系特征的基础上搭建合适的机会网络，并通过真实的网络测量数据来设计和调整各种路由协议，使之能应用于现实的网络环境中。机会网络在全球移动网、军用Ad-Hoc网、长距离无线链路网、水下声学调制通信网络、自由空间光通信网、卫星通信网、传感器网络等多种现实网络中都可以应用，这对今后网络技术以及数据通信等领域研究都具有重要的意义。本文在研究了机会网络关键技术和流行路由协议的基础，提出了一种新的路由协议基于效用转交的多副本路由协议。1.3 论文的组织本论文共分为六章。第一章叙述了机会网络的技术背景、定义和研究现状。第二章对机会网络的关键技术进行综述，分析了机会网络中移动模型

18、、拥塞控制、转发机制。第三章在对机会网络的关键技术分析的基础上，分析了单副本路由协议和多副本路由协议的优劣势，并重点分析了当前主要三个多副本路由协议。第四章在分析当前主要三个多副本路由协议的优缺点的基础上，取长补短，提出了一种新的路由协议基于效用转交的多副本路由协议。第五章介绍了仿真平台ONE，并对基于效用转交的多副本路由协议进行性能评估。第六章是总结和展望。最后是致谢部分。第二章 机会网络中路由协议的关键技术2.1 概述近年来，随着对机会网络的研究，越来越多的机会网络应用在实际中出现，典型例子有：军事无线自组织网络、星际间的网络、野生动物追踪网络、人群网络等等。这些网络有相同的特点:较高的延

19、迟、端到端的链接不存在、节点能量和存储空间受限、网络的拓扑结构呈动态性的变化、数据的差错率较大等，对于有些网络甚至在一段时间内端到端的链接都不存在。正是这些特点导致传统的无线自组织网络路由协议和传输控制协议/因特网互联协议(TCP/IP)无法在机会网络中应用，因此，机会网络的路由设计问题就变得非常关键了。机会网络的这些特点使得设计机会网络路由协议时的关键就是如何提高成功投递率，尽量减少交付延时，节约节点缓存和降低耗能，在实现相同路由性能的条件下，尽量降低协议的复杂度，提高协议的实用性。此外，针对不同的消息服务等级要求，应关注于不同的性能参数，采用满足相应要求的路由方法。机会网络路由的设计，涉及

20、到移动模型、拥塞控制、缓存策略、转发机制等方面4。机会网络路由协议的设计最主要的目的就是尽可能的提高报文的传递率，由于机会网络可能会使用一些不可靠或者不可预测的组件，为了弥补这方面的不足，许多的路由协议采用报文多副本的方式来提高传递率。由于使用了多副本的策略，报文投递率的成功率就相对来说高一些，但同时也会增加了平均传输时间，这种方法是在性能和开销之间做了一个折中方式。开销最小的办法就是在整个机会网络中只有一个报文，这样整个机会网络的开销就会非常小，但只有一个报文存在，报文的传递率就会变得非常低了。如果网络中的每一个节点都有一个报文副本存在的话，报文的传递率就会变得非常高，但是这样会大大的占用网

21、络资源，网络开销也会大大增加，因此如何在性能和开销之间折中是机会网络路由协议设计过程中的一个关键点。此外，研究还发现，机会网络中节点的移动不是随机的，存在一定的规律，如何根据这些节点的地理位置、节点之间的历史相遇信息等规律进行报文转发，也是当前的一个研究关键点。到目前为止己经有很多的学者对机会网络路由协议做了很多工作，并且提出了多种不同的路由协议，本章将会介绍国内外学者所研究的主要路由协议，并对这些不同路由协议的移动模型、拥塞控制、缓存策略、转发机制进行分析。2.2 移动模型节点的移动模型是指节点的移动路线规律，移动速度，静止时间等特征的变化模式，移动模型是自组织网络的基础研究之一，并且已经广

22、泛应用于自组织网络协议性能的分析和评价。传统的MANET一般从网络拓扑角度去分析移动模型对协议性能的影响，因为传统的MANET假设网络是全连通的，节点的移动对路由层以上的协议是“屏蔽”的，比如从拓扑连通率、节点连通度等分析移动模型对性能的影响。而机会网络中的数据传输取决于节点移动带来的相遇机会，而节点之间的相遇概率和相遇时间分布是由节点的移动模型决定的，因此机会网络中的移动模型研究是以刻画节点相遇特征为核心的。相比于传统的MANET，在机会网络中对移动模型的研究更加重要。常用节点移动模型主要有随机模型、随机地图限制模型、人类行为模型。其中随机移动模型有随机移动(RW)，随机路点(RWP)和随机

23、方向(RD)模型；为了将实际移动性模型化，可以根据实际地图数据中的预定路径来限制节点移动，例如随机地图移动(MBM)、基于最短路径的移动(SPMBM)、基于路线的移动(RMBM)；基于人类行为移动模型主要是用来模拟人们在一个工作日中从事的各种各样活动，例如工作日移动模型(WDM)。2.2.1 随机移动模型独立同分布移动模型下的节点相遇特征可用两个参数来刻画:节点相遇时间 (meetingtime，简称MT)和相遇间隔时间(intermeetingtime，简称IMT)。节点相遇时间是指两个节点从静止开始到第一次相遇(进入通信范围)经过的时间间隔。节点相遇间隔时间是指两个节点前后两次相遇的时间间

24、隔。随机移动模型是独立同分布模型，具有代表性的三个独立同分布移动模型是RandomwayPoint (RWP，随机路点)，RandomWalk(RW，随机移动)和RandomDirection (RD，随机方向)。RandomWaypoint 移动模型中节点的移动速度和到达路点停留时间保持恒定，但节点是沿着曲折的路径移动到达路点，而不是根据最短路径移动。当节点到达路点之后会随机选择另一个路点，每次的路点都不一样。上述三个移动模型的节点期望相遇时间(expected meeting time)服从指数分布或其尾部服从指数分布， RandomDirection移动模型和RandomwayPoint

25、移动模型这两种移动模型下节点相遇时间和相遇间隔时间的尾部分布具有无记忆性。2.2.2 基于地图限制的移动模型为了将实际移动性模型化，可以根据实际地图数据中的预定路径来限制节点移动，譬如，为了防止汽车节点闯入户内和人行道，限制汽车节点在公路上移动。基于地图限制的移动模型主要有：(1)MapBasedMovement(MBM，基于地图的随机移动)，(2)MapRouteMovement(MRM，基于地图的路由移动)(3)ShortestPathMapBased-Movement(SPMBM，基于地图的最短路径移动)。在最简单的基于地图限制的移动模型MBM中，节点总是沿着预先被地图数据定义的路径上随

26、机运动，这种随机移动的方式往往不是现实日常人们行走规律的准确估计。移动节点根据地图节点移动，当一个节点从一个地图节点到达另一个地图节点之后，随机选择下一个地图节点(一般不返回)。SPMBM则是一个更符合现实世界的移动模型，不同于MBM模型中的完全随机移动，它是在地图中选择任何一点作为出发地，然后沿着最短路径到达目的地。这些地点可能是完全随机选取，也可能是从兴趣集合(Point of Interest,POI)随机选取。兴趣集合中包含的都是日常人们经常去的地方，比如旅游景点、购物街或宾馆等。而RMBM模型是在SPMBM基础上，预先设定了节点的路径，这些路径可能是由去往公共汽车站点、火车站的固定路

27、线组成的。RWP、MBM、SPMBM这些移动模型比较简单，容易理解。另外在这些模型中由于不会产生节点间的连接间隔时间和连接时间分布以反映真实世界中人们间的交往频率，所以在仿真软件中能更有效地运行。2.2.3 基于社区的移动模型日常生活中，由人们所携带的手持设备组成的网络是机会网络的一个主要应用，对适用于这类场景的移动模型的研究是机会网络研究的一个重点。基于社区的移动模型(communitybasedmodel)是指由手持设备组成的机会网络节点的移动具有社区特性。该模型下的节点并不是随机选取移动位置，节点目的地的选择受到以下三种因素影响:(l)节点偏好，节点比其他节点更倾向于去往某个特定位置或遇

28、到特定节点;(2)节点异构性，某些节点能够到达所有位置或者能够遇到所有其他节点;(3)行为时变性，节点移动随着时间的推移而发生变化。基于社区移动模型最有代表性的是工作日移动模型。工作日移动模型 (WorkingDayMovement，WDM)是由芬兰赫尔辛基大学提出的一种最接近人们日常生活的社区模型。该移动模型主要目的是用来模拟人们在一个工作日中从事的各种各样活动，该模型是由多个子模型构成的。目前该移动模型实现了三个子模型，描述了日常生活中人们所处的三种状态:在上班、晚上下班之后和在家中的活动，在三个子模型可以模拟人们在一个工作日中的大部分行为。在办公活动子模型中，节点首先以一定的速度到达自己

29、的办公桌，然后静止一段时间，该静止时间服从Pareto分布，静止时间过后，节点在办公室随机选择一个目的地，移动到该目的地并且再静止一段时间，该时间也服从Pareto分布，节点重复这样的动作直至下班。在夜晚活动子模型中可能会在路上行走，节点可能会在超市购物，或者可能与朋友聚在一起。在家庭活动子模型中，节点进行短距离的移动或者静止。除了这三个活动子模型，WDM模型还包括三个不同的传输模块。节点可以独自运动也可以成群地行走或驾驶。这种单独行走或成群以不同的速度移动的功能相应地增加了移动模式的异构性，进而影响了协议的仿真性能，如路由协议等。最后，WDM模型还引入了“群体”和“社会关系”，这些概念在简单

30、移动模型如RWP中是不存在的。在WDM模型中，群体是由工作在相同办公室的节点、或晚上一起参加相同活动消遣时光的人们、或居住在一起的节点组成。2.3 拥塞控制目前机会网络中的路由协议主要采用“存储-携带-转发”机制，即网络中的节点生成或者接收到一个数据报文，而此时不存在到达目的节点的路径或者不存在合适的下一跳转发节点，则当前节点将数据报文保存在存储空间中，并随着当前节点的移动携带着数据报文寻找合适的转发机会。这种机制虽然能够克服网络分裂和端到端路径不存在的困难，依靠节点的运动和位置改变把数据报文送到目的节点。但是在许多机会路由协议实际使用时，会产生长期的存储，节点缓存受限时容易发生阻塞；另外，网

31、络中数据单元称为“捆绑(束)”，是自带的数据单元，它们常常是很大的，当移动性导致节点间短暂的接触时，可用带宽可能不足以使所有预定消息通信。因此，有效的丢弃策略是必要的。和其他网络相比,机会网络的拥塞控制5实现是相对困难的,主要因为如下两个特性:第一,在将来的一段时间可能无法建立连接(如果这样，累积的数据可能在不久的将来没有机会传出去);第二,除非在极端情况或过期后,否则已经收到的保管消息不能被丢弃.目前主要使用基于优先级的FCFS来分配保管存储.如果DTN转发器接受合同外的保管消息,那么将出现阻塞.这样,节点的长期存储可能被完全消耗掉,因此,要避免非保管消息传输.目前的研究结果主要分为两类：主

32、动方法，通过缓存管理和保管传输的相应调整起到拥塞控制的作用；被动方法，采用接入控制避免在开始处的拥塞。文献6采用主动方法的思想，提出了一种基于传染路由的拥塞控制策略(当节点缓存完全占用又需存储新分组时，遍历缓存，找出转发次数大于等于N次的分组将其删除；若缓存中没有这样的分组，则删除最后一个存入的分组)，为信息的集合建立SV索引,引入拥塞检测和拥塞避免操作，有效缓解了节点拥塞。Zhang Z.分析了缓存区受限的epidemic路由7，并评估了一些简单的丢弃策略，例如drop-front和drop-tail。HBSD采用一个基于统计学习的分布式协议，从历史学习中估计当前网络的全局状态，能被用来计算

33、message utility。另外可通过控制复本或转发数目来避免过多耗用节点缓存，一些协议中使用单个复本，如FC、DD，可有效地缓解空间和带宽，但同时使得消息交付率很小，SprayAndWait设定消息被复制的数目，有一般模式和二进制模式，通过调整复本数目来平衡分发与耗用内存。2.4 缓存策略随着普适计算技术的发展和移动应用环境的逐渐成熟，机会网络得到了广泛的关注。在机会网络中，如何针对机会网络通信特点设计有效的节点协作缓存策略是一项缓解机会网络缓存需求空间矛盾的重要技术。目前已有较多基于无线环境下的协作缓存研究。文献8讨论了缓存使用空间情况对拥塞控制协议各个关键缓存参数进行调整，实现了性能

34、的优化。如文献9提出了FloodCache其基本思想是利用有限的洪泛查找附近节点缓存的数据块。该策略主要用于对数据延迟要求较高的多媒体应用。文献10利用节点间的协作关系避免单个节点缓存有限的问题，并据此设计了一种相应的ACA缓存替换协议。文献11基于单个节点设计了2种缓存策略CacheData和CachePath，这2种策略分别基于数据内容本身与数据传输的路径进行缓存,并提出了一种面向存储服务的缓存管理模型。然而上述研究大多采用随机行走模型模拟节点在网络中的整个运动过程，并未把节点的移动列为影响缓存性能的重要因素。文献12提出一种改进的节点协作缓存策略HMP-Cache，该策略根据节点运动状态

35、与相对静止状态的特点相应分为两部分，分别针对数据在传播过程中需要缓存的情况与节点收到数据后缓存的策略进行了设计。2.5 转发机制根据转发策略的不同，将目前的转发机制主要分为4类：基于冗余(redundancy-based)的转发、基于效用(utility-based)的转发、效用冗余混合(hybrid)协议和基于主动运动(node movement)的转发。其中，基于冗余的转发通常采用复制(replication)或基于编码(coding)的方式，基于效用的转发又分为基于相遇预测(meeting prediction)、基于链路状态(link state)和基于上下文信息(context)转发

36、1，如图1所。图 1 机会网络路由的转发机制2.5.1 基于编码的转发基于编码的转发将待传输消息编码成多个小消息，目标节点仅需要接收到一部分消息，即可通过消息之间的编码规则重建原消息。路由协议EC(erasure-coding)是基于擦除编码的。源节点将消息分成m个消息块，然后将这些消息块利用编码技术变成k个小消息，目标节点只需要接收到k个消息中的任意m(1+)个小消息就可以进行消息重建，其中是常数，其值根据具体的编码协议来确定。该机制的源节点将小消息编码后分配给k个中继节点，k个中继节点携带消息块直到与目标节点相遇。EC协议中，节点每次相遇时传送小消息的数目是固定的，它不考虑每次连接持续的时

37、间，因此网络连接情况足够好的时候连接机往往得不到充分利用，但该协议能保证网络连接最差时候的性能。另一种基于编码的路由协议是混合式路由协议H-EC，它结合EC协议和复制策略，将每个小消息经编码后再生成两个副本，与邻居节点相遇时，首先将1份小消息副本传送给该相遇的节点，然后根据节点相遇的持续时间，将消息的第2份副本发送给该相遇节点，充分利用每一次相遇机会。2.5.2 基于复制的转发基于复制的转发将同一消息的多个副本注入网络，只要其中一个副本到达目标节点，则消息传输成功。这类协议的核心问题是如何确定注入网络中的最大消息副本数和产生消息副本的方式。蔓延路由协议(epidemic forwarding，

38、简称EF)是典型的基于复制的路由协议，每个节点将要传送的消息保存在缓存当中，并为其拥有消息的集合建立名为SV(summary vector)的索引，当两个节点相遇时交换彼此的SV。节点根据对方的SV确定对方缓存中缺少哪些消息，然后双方彼此进行交换。这种路由方式意味着：只要节点的缓存足够大，随着节点之间的不断相遇，消息会从源端开始传播到网络中的其它节点。EF机制可以保证找到到达目标节点的最短路径，而由于实际网络节点带宽和缓存等资源有限，随着网络节点数的增大，其性能由于广播导致的拥塞会急剧下降。2-HOP协议中，源节点将消息副本给最先遇到的L个中继节点，源节点和L个中继节点只将消息转发给目标节点，

39、消息需要两跳到达目标节点。相比一跳的直接传输(directtransmission，简称DT)，2-HOP协议提高了传输成功率。相比EF协议，2-HOP协议固定网络中的每个消息的副本数，节约了网络资源，具有较好的可扩展性。2.5.3 基于相遇预测的转发在基于相遇预测的转发中，节点维护一个相遇概率，用来表示该节点与目标节点的相遇情况。相遇概率可以通过节点的历史移动轨迹来获得。Seek And Focus协议是一种相遇概率估算方法，它把随机策略的简单性和基于效用策略的复杂性结合起来，节点记录与网络中其他节点的连接时长，以此作为估算和预测节点间相遇概率的依据。LeBrun等人针对车载网络根据节点位置

40、和运动方向估算节点相遇概率，文中提出的协议假设每个车辆都配置有全球定位导航设备GPS，因此可实时获取节点运动方向和位置等信息。2.5.4 基于链路估计的转发基于链路估计的转发考察节点之间的“端到端”的链路状态来选择转发节点。尽管机会网络中不一定存在端到端的完整路径，但通过收集单跳链路状态估算出的端到端路径的有用性仍可作为转发决策依据，单跳链路状态可利用链路的平均可用性来估算。在最短期望路径路由(shortest expected path routing protocol，简称SEPR)协议中，每个节点都维护到达已知节点的链路概率值，两个节点i和j之间的链路概率Pi，j=Tconn/Tw，Tc

41、onn是时间窗口Tw内节点对维持连通的时长。每次节点相遇时，该概率值被更新。SEPR假定穿越一条链路的时间与链路概率值成反比，并使用穿越时间作为链路长度，当节点获得所有已知节点本地链路概率后，利用Di1jkstra协议计算当前节点到达目标节点的最短路径。优先Epidemic(prioritized epidemic)协议则利用计算出的最短路径长度来赋予消息被抛弃的优先级，距离目的节点的路径长度越大，被抛弃的优先级越低，通过抛弃无用消息降低网络负载，提高传染转发机制的性能。链路延迟也可以用来估计链路的效用值。2.5.5 基于上下文信息的转发基于上下文信息的转发使用节点位置信息、能量、密度以及移动

42、速度等参数来计算节点效用值。Context-Aware Routing(CAR)协议考虑了节点剩余能量、移动速度、到达目标连通域的概率以及拓扑变化等上下文属性，综合利用时间序列分析理论来计算节点效用值。CAR协议中扩充了DSDV(destination seque-nced distance-vector routing)协议的路由表项，每个表项包括了目标节点、下一跳、费用、节点效用值等信息，节点在连通域内周期性地交换路由表信息。当要转发消息的节点与目标节点位于同一连通域，直接转发消息，否则，把消息转发给连通域内与目标节点效用值最高的中间节点。使用节点上下文属性计算效用值比较复杂，不同参数的权

43、重对传输性能影响很大。2.5.6 效用冗余混合的转发效用冗余混合转发结合使用并行传输和基于效用的转发决策提高传输性能。SCAR(sensor context-aware daptive routing)协议用于传感器网络数据收集，采用时间序列分析理论估计节点效用结合使用BSW中在源节点限制消息最大副本数的思想。每个消息产生多个副本，消息副本沿节点效用增大的方向传输到sink节点。而在DFT-MSN数据传输方案中，每个传感器节点维持一个到达sink节点的传递概率值，该值使用与PROPHET协议类似的方法来估算，每个消息关联一个容错因子，用以动态调整网络中消息冗余度，该协议中消息容错因子较难精确计

44、算，以致消息转发与蔓延转发相似。还有一些相似的机制提出的综合相遇预测与基于擦除编码的转发机制以及由微软研究院提出的EBEC协议。2.5.7 基于节点主动运动的转发基于节点主动运动转发利用一些特殊节点为其他节点提供服务，网络中的特殊节点主动移动以提供通信服务。MF(Message Ferrying)协议，使用摆渡(Ferry)节点在稀疏移动自组网中传输数据。Ferry是区域内的特殊节点，通过有规律的移动为网络中其他普通无线节点提供数据通信服务。根据Ferry与普通节点间关系的不同，MF协议的实现分为两种方式：FIMF(Ferry-Initiated MF)和NIMF(Node-Initiated

45、 MF)。在FIMF方式中，普通无线节点向摆渡节点发起通信请求，通过使用长距离无线电方式来“召唤”Ferry，Ferry根据节点的“召唤”产生运动，并采用短距离无线电传送方式与之进行通信；而在NIMF方式中，Ferry按固定轨迹在网络中运动，需要与Ferry进行通信的节点主动获知Ferry的运动轨迹并周期性向其靠拢以进行数据通信。Ferry机制采用Ferries节点中转数据，可以有效避免过多的能量损耗和网络资源负担。但是该机制中需要预先规划节点运动路径或要求节点移动可控，在实际应用中这些假设往往无法得到满足，所以该机制应用范围有限。2.6 本章小结本章综述了机会网络中移动模型、拥塞控制、缓存策

46、略、转发机制等关键技术。机会网络频繁的网络中断、随机的或可预测的连接，导致其路由协议的设计面临很大的困难。设计高效的机会网络路由协议需要充分考虑到机会网络及其具体应用环境的特点。总结设计过程中的关键技术是有必要的，以下的研究也是要从这些关键点出发，提出新的思路和解决方法，设计出一个通用的性能良好的路由机制，克服网络的受限特性，从而实现机会网络中有效可靠的通信。第三章 机会网络中多副本路由协议3.1 单副本路由协议和多副本路由协议的比较单副本路由协议主要有直接递交(DirectDelivery)和首次接触(FirstContact)路由协议，多副本路由协议主要有三类:基于蔓延的多副本路由协议(E

47、pidemic)，固定数量副本的多副本路由协议(SprayAndWaitRouter)，条件蔓延的多副本路由协议(Prophet)。以下从三个方面将对单副本路由协议和多副本路由协议进行比较13。(1)报文成功递交率:单幅本路由协议中只存在源节点生成的原始的数据报文，而在机会网络这样的网络环境中，难以依赖仅有的一个数据报文实现数据报文的成功传输，很难保证这仅有的一个数据报文副本被成功地传输到目的节点。而多副本路由协议利用冗余的数据报文副本能够提高报文成功递交率，只要有一个副本成功到达目的节点，目的节点就能成功接收到数据信息。这极大地提高了报文成功到达目的地的概率。因此，从整体上来讲，在相同的网络

48、环境下，多副本路由协议的报文成功递交率大于单副本路由协议。(2)平均传递延时:在单副本路由协议中，平均传递延时决定于仅有的原始数据报文，难以为一个数据报文计算一条最短的传输路径。而在多副本路由协议中，由于存在多个数据副本，数据报文就存在多条传输路径，而多条路径中有可能存在最短路径，因此，在相同的网络环境下，多副本路由协议的平均传递延时小于单副本路由协议。(3)网络资源的消耗:在单副本路由协议中，每个数据报文只有一个原始数据报文，相对于多副本路由协议，单副本路由协议占用更少的存储空间，并且相同的网络环境下，单副本路由协议中节点之间数据转发量少于多副本路由协议，在链路带宽与能量方面，单副本路由协议

49、优于多副本路由协议。3.2 多副本路由协议多副本路由协议主要有三类:基于蔓延的多副本路由协议(Epidemic)，固定数量副本的多副本路由协议(SprayAndWaitRouter)，条件蔓延的多副本路由协议(Prophet)。本节将具体介绍这三种路由协议。3.2.1 EpidemicEpidemic协议中文称作蔓延协议或者传染转发协议。在这种路由协议方案中，每个网络节点维护一个消息队列，在两个节点移动到相互可通信的区域范围之内时，彼此交换对方尚未缓存的消息。每个节点都将所携带的消息转发给所有相遇的邻居节点，其本质是一种洪泛协议。EPidemic路由协议是设计目的有三个:有效的散播消息、最小化

50、时延和最大化递交率。如图3.1所示。图 3.1 Epidemic路由协议在图3.1中，白圆圈表示节点，节点周围散播小点的区域表示通信范围，字母S和D分别代表信源和信宿，A表示中继节点。I所示，在t1时刻信源S遇到两个可通信的中继节点A1和A2，那么此时S将报文传递给A1和A2，两个中继节点携带报文移动。所示，在t2时刻A，遇到A3并将报文传递给A3，此时A3又正好在信宿D的通信范围内，最终报文通过A3顺利到达信宿，完成信息的传输。所示，是B和B两个节点相遇时B将所携带的报文传递给B的情形，分为三个步骤:(1) B将所携带报文的摘要向量(summary vector)传送给B，摘要向量是报文的简

51、单表示。(2) B把收到的摘要向量与自己携带报文的摘要向量进行比较，找到自己没有携带的报文，然后请求B发送这些报文。(3) B在收到B的请求之后，将B所没有携带的报文发送给B。3.2.2 Spray and Wait散发等待(Spray and Wait)1415 路由协议结合了Epidemic协议中数据报文的扩散速度和DirectDelivery单副本直接传输路由协议的简单特性。协议首先将数据报文的多个副本向网络扩散，当扩散的数据报文副本数量能够保证至少有一个数据副本被成功传输时，协议停止扩散过程，使每个携带数据副本的节点执行直接传输过程，由此SprayandWait协议也可以看作是单副本与

52、多副本路由协议的结合。sprayandwait协议总体上分为两个阶段:扩散阶段和等待阶段。(1) 扩散阶段:对于某个数据报文，源节点为该数据报文生成L个副本，网络中任何一个节点A(源节点或者是其他节点)如果携带有该数据报文的x(x1)个数据副本，当它遇见节点B(节点B没有该数据报文的副本)时，节点A向节点B转发1个副本，而自身保留(x一y)个副本。不同的y值(默认y值为1)决定了不同的扩散策略。(2) 等待阶段:扩散节点完成之后，L个数据报文副本被扩散到了网络中的L各不同节点，如果在扩散阶段数据报文没有被成功传输到最终目的节点，网络中携带有数据报文副本的节点进入等待阶段，即只有遇到数据报文的最

53、终目的节点，才进行数据报文的转发，中间过程中遇到其他非最终目的节点时，并不向非最终目的节点转发该数据报文。可以使用多种扩散策略将L个数据副本扩散到L个不同的节点，最简单的策略是由产生数据报文的源节点完成扩散，即每当源节点与另外一个节点相遇时，转发一个数据副本给其他节点，这种简单的扩散策略也被称为“源扩散”。如图3.2所示。S（M，4）N1N2N3N4（M，1）（M，1）（M，1）（M，1）D图 3.2 “源扩散”散发等待路由协议在图3.2中，信源产生L个报文副本M(假设L为4)，然后每遇见一个节点就传递一个报文副本，使得这些相遇节点都携带一个报文副本M(l)，这样的节点共有L个。这L个节点将不

54、再转发这个报文副本，直到遇见信宿D在SprayAndWait协议中经常使用一种称为“二分扩散”的扩散策略，即Binary Spray and Wait 路由协议。该协议在Wait阶段跟“源扩散”一样。二分扩散:对于某个数据报文，源节点为该数据报文生成L个副本，网络中任何一个节点A(源节点或者是其他节点)如果携带有该数据报文的n(nl)个数据副本，当它遇见节点B(节点B没有该数据报文的副本)时，节点A向节点B转发(n/2)个副本，而自身保留(n/2)个副本，如图3.3所示。S（M，4）N1N2（M，1）（M，1）（M，1）（M，2）N3N4N5N6（M，1）（M，2）图 3.3 “二分扩散”散发

55、等待路由协议在图3.3中， BinarySPrayandWait协议首先在信源产生L个报文副本M(L)，在遇到目的节点D之前，任何一个节点，只要携带超过一个报文副本，那么在遇到下一跳节点时就将携带报文副本的一半(二分)传送给对方，自己携带剩下的另一半副本。当节点携带的报文数只剩下一个时，就执行DirectDelivery路由协议。文献15给出详细的理论说明和仿真结果，可以知道，尽管SprayandWait路由协议看上去很简单，但在传输次数和递交时延方面表现出很好的性能，甚至可以算是一种最优方案。但是，散发等待是采用首先散发报文，然后等待报文到达目的节点的方式，如果所选择的中继节点的活动还没有源

56、节点更容易达到目的节点，或者当那些更容易达到目的节点的中继节点不能得到报文副本，这样的话，散发等待路由就会增大报文传递的延迟和减少报文的传递率的。这也是散发等待路由协议的不足之处，本论文主要对散发等待协议的这些不足之处提出改进，解决这些影响报文等待过程产生的延迟问题，从而能提高报文的传递率和减少报文的传递延迟。3.2.3 PRoPHET虽然在DTN中节点的随机移动模式是常被拿来研究的，但是，现实中的节点并非以一种随机的形式在移动，在看似随机胜背后有一定的规律性。比如当一个节点以前曾反复多次访问过一个区域，那么它就有可能再次访问这个区域。分析这种现象并利用这个信息，通过估算相遇预测值来路由消息，

57、这就是PROPHET。基于历史相遇信息和可传递的概率路由协议(Probabilistic Routing Protocol using History of Encounters and Transitivity,PRoPHET)16是一种基于效用的协议，所使用的效用函数是概率函数，该函数根据两个节点自从上次相遇后经过的时间而更新，并且该协议实现了效用值的传递特性。在ProPhet协议中，网络中每个节点A，对于除自身之外的其他节点B，都维护一个递交预测值P(A，B)任(0，l，用来指示节点A再次与节点B相遇的概率，或者节点A能够将某个数据报文成功传输到节点B的概率，该概率值为，称为递交预测值(

58、delivery predictability)，初始化值为。ProPhet基于这样的理论:如果某个节点在一定的时间内多次访问同一个位置，则节点在最近的将来一段时间，将以较大的概率再次访问该位置，具有一定规律性的移动模型(比如社区模型)符合该理论。描述这个路由协议，跟蔓延(EPidemic)协议相似，当两个节点相遇，它们互换彼此携带报文的预测向量，其中预测向量包含了该节点到达其它所有节点的递交预测值信息。下面分两部分来详细阐述这个协议。(1)计算递交预测值，计算递交预测值要分三步走。 更新相遇的两节点a,b之间的递交预测值。当两个节点相遇的时候，他们要更新自己的递交预测值，这样才能保证经常相遇

59、的节点彼此拥有很高的递交预测值， 在a节点上： (3.2.3-1)在b节点上： (3.2.3-2)是初始化常数，文献16已经证明只的最优值为0.75；、为节点在本次相遇之前的递交预测值。 如果一对节点在一段时间内没有相遇，它们之间相互转发消息的可能性降低，因此递交预测值应该随着间断时间的增大而衰减，计算衰减的递交预测值公式为：在a节点上： (3.2.3-3)其中是衰减常数，表示衰减的时间间隔，并且文献16指出, 的最优值为0.98; 是从上次衰减开始计算所流失的时间单元个数, 时间单位u的定义可以是各种各样的，但都应该基于目标网络的期望时延和应用来定义。比如可以选择10s作为个时间单元。 递交

60、预测值的传递，利用递交预测值的传递性更新。例如，如果a经常遇到b，b又经常遇到c，则可以这么说，a通过b传递，a能够发送信息到节点c的概率也不会低。具体的传递方程如下：在a节点上，针对于其他任何一个节点c：(c不包含相遇节点b) (3.2.3-4)在b节点上，针对于其他任何一个节点c：(c不包含相遇节点a)(3.2.3-5)其中是传递系数，反映了传递对于递交预测值的影响大小,文献16指出的最优取值为0.25。(2)转发策略进行完以上三步预测向量更新后，两节点开始进行传送数据。在传统的路由协议中，总是以一种简单的策略来选择转发节点，报文被传递给一个邻居节点，一般情况下，如果路径可靠性足够高，那么

61、报文只是被发送给一个转发节点。然而，在ProPhet中则采用完全不同的转发策略，就是当两个节点相遇，选择到达目的节点递交预期值高的节点来转发报文。发送策略如下：针对于本节点a上的每一条信息的目的节点d，如果P(b,d)P(a,d),则节点a将发送该信息到相遇节点b。信息根据发送策略不断转发，直到该信息到达目的节点。文献16给出了PROPHET协议的性能仿真结果，结果表明PROPHET比EPidemic协议有更好的性能表现。3.2.4 三种协议的比较 Epidemic、PRoPHET、SPrayandwait路由协议是三种多副本路由协议中最基本的协议，同类别中的其他协议都是基于这三种路由协议在不

62、同方面的改进，并且这三种路由协议是当前机会网络中普遍使用的路由协议。本文从以下几个方面对这三种路由协议进行比较。(1)每个数据报文生成的副本数量。三种路由协议中Epidemic协议为每个数据报文生成的副本数量最多，PRoPHET协议生成的副本数量取决于网络节点的移动特性，而SPrayandwait协议总是会为每个数据报文生成固定数量的副本。 (2)报文成功递交率。报文成功递交率在一定程度上取决于数据报文副本的数量，但并不是说使用的副本数量越多，报文成功递交率就越大，当数据报文副本数量过多时，会造成网络拥塞等问题，从而使报文成功递交率下降，因此在某些情况下，Epidemic协议的报文成功递交率不

63、一定比其他两种协议高。对于SPrayandWait协议，关键在于选取正确的副本数量，如果副本数量能够正确地反映当前网络的特性，则SPrayandWait能够依靠有限的副本达到一定的报文成功递交率。(3) 网络资源消耗。由于Epidemic是一种无限制的泛洪路由协议，因此Epidemic对网络资源的消耗最大PRoPHET协议在Epidemic协议的基础上对泛洪做了限制，因此资源消耗小于PRoPHET协议。而SPrayandwait协议对网络资源的消耗取决于生成的副本数量，大部分网络环境中，SPrayandwait协议消耗的网络资源最少。3.3 本章小结根据以上分析，多副本路由协议在报文成功递交率、数据报文传输延时性能上优于单副本路由协议，在网络资源的消耗性能上劣于单副本路由协议。但只要控制报文的副本数量，可以折中多副本路由协议的网络资源消耗。因此在本文提出的作者设计的路由协议采用多副本的路由协议。同时比较了主要的三种多副本路由协议的每个数据报文生成的副本数量、数据报文的成功传递概率、网络资源消耗情况，为本文提出新的路由协议打下基础。第四章 基于效用转交的多副本路由协议4.1 路由协议的提出尽管在相同的条件下，Epidemic能够保证数据报文沿最短路径到达最终目的节