机会网络研究进展

王慧强，张淯舒，吕宏武，朱金美

(哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨150001)

0 引言

随着无线通信技术的飞速发展与移动智能设备的广泛普及，人们迫切希望能够随时随地从互联网获取信息与服务。移动互联网应运而生，并迅速成为网络通信领域的热门研究方向。然而，受到网络基础设施与使用环境等因素限制，采用传统的无线接入方式往往不能满足用户的使用需求。机会网络［1］的出现为无线网络提供了一种全新的接入模式，使得在缺少网络基础设施的环境中接入互联网成为可能，极大地拓展了移动互联网的覆盖范围，为新型移动应用的出现提供了条件。

机会网络是一种面向缺乏持续端到端连接的网络环境，利用节点移动带来的相遇机会完成信息传递的无线自组织网络，其部分概念源自延迟容忍网络(Delay Tolerant Network，DTN)［2］的研究。DTN 最初的研究可追溯到上个世纪，为应对深空探测的需求，NASA 于1998年开始了针对具有长延迟、多终端以及周期性连接等特征的深空网络的研究，其目的是使地面与深空探测器间的数据通信能够像地面节点之间通信一样方便。该研究项目逐渐发展成为Internet 的IPNSIG 与IETF 的DTNRG 两个工作组。其中，IPNSIG的研究主要针对深空网络展开;而DTNRG 由于没有可以进行试验的星际网络，将研究的重点转向如何将DTN 的概念运用到地面网络中。另外，DARPA 于2004年提出了中断容忍网络(Disruption Tolerant Network)的概念，也简称为DTN，一般认为两者为同一概念的不同表述。

本文立足于机会社会网络技术，在充分总结现有研究成果的基础上，首先对机会网络的概念、模型等内容作简单介绍，然后总结该领域中的热点研究问题，最后对其发展方向进行了展望。

1 机会网络

与传统的面向连接的无线网络不同，机会网络是一种针对间歇性连接、延迟大、错误率高等无线通信特征设计的新型无线网络，能在缺乏端到端连接的网络环境中完成信息传递［3］。机会网络采用“存储—携带—转发”模式的路由协议，消息在传递过程中需要经过各中间节点的存储与携带，并等待合适的下一跳节点出现。机会网络中消息的传递过程如图1所示。节点S 中产生了一个目的节点为D 的消息M，在t1 时刻，节点S 仅能够与节点1、2 建立无线连接，并选择把消息M 传递给节点1。在t2 时刻，经过一段时间的移动，节点1 携带消息M 与节点3 相遇，并将消息M 传递给节点3。最后，在t3 时刻，携带消息M 的节点3 与目的节点D 相遇，将消息M 传递给节点D，完成了消息M 的整个传递过程。从图1中可以看出，在消息M 的传递过程中，始终不存在一条连接源节点S 与目的节点D 的无线链路，因此传统的基于连接的无线网络不能有效地完成消息的传递，而机会网络利用节点移动创造的相遇机会为消息建立了有效的传递路径。

图1 机会网络消息传递

机会网络的实质是一种通用的面向消息的覆盖层网络体系结构，在端到端应用与底层网络协议之间设置机会网络组件，为无线网络提供针对异构、大延迟以及间歇式连接网络环境的通信能力。其体系结构如图2所示。其中，机会网络相关组件为网络提供虚拟消息交换、命名与寻址、路由与转发、安全保障与QoS 等机制［4］。

图2 机会网络体系结构

2 节点移动模型

节点移动模型通过相应的算法与规则描述节点位置、速度与移动方向等运动信息。节点的移动性通常来说是对无线网络的挑战，但对于机会网络则是一种机遇。传统的无线网络协议普遍采用屏蔽底层节点运动的设计模式，而机会网络的特点使得对节点移动的研究成为其协议设计的一部分。节点移动模型主要包括随机移动模型、基于人类行为的移动模型与基于统计的真实移动模型三种［5］。

随机移动模型是一种独立同分布的理论移动模型，其中随机路点移动模型(Random Way Point，RWP)［6］、随机游走移动模型(Random Walk，RW)和随机方向移动模型(Random Direction，RD)［7］是三种比较经典的模型。在RWP 模型中，节点随机选择一个目的点，并以恒定的速度向该点运动，到达后停止一段时间再选择下一个目的点。在RW 模型中，节点通过随机选择运动方向与速度决定移动路径。在RD 模型中，节点随机选取移动方向并以恒定速度运动，当节点到达仿真区域边缘时停止一段时间，再重新选择移动方向。

基于人类行为的移动模型能够更好的模拟实际环境中节点的移动模式，主要包括基于地图的移动模型(Map－Based Mobility，MBM)、工作日移动模型(Working Day Movement Model，WDM)［8］与基于社区的移动模型(Community Based Model，CBM)［9－11］。其中，MBM 模型将节点的移动轨迹限制在地图中定义的道路上，同时提供随机、最短路径与规定路径三种移动模式;WDM 是针对工作日设计的移动模型，能够模仿生活中三种常见的场景，在家休息、在办公室工作和与朋友外出;CBM 模型则考虑节点喜好与行为时变性，主要用于模拟携带移动节点的人类具有的社会特性。

基于统计的真实移动模型收集实际环境中的节点运动轨迹。MIT 的Reality Mining 项目［12］在9 个月的时间里记录了106 个智能蓝牙设备的移动轨迹与相遇数据;UCSD 的Wireless Topology Discovery 项目［13］在11 周的时间里记录了300 个无线设备与Wi－Fi 接入点的相遇数据;剑桥大学的Haggle 项目［14］记录了校园中多个蓝牙设备的相遇情况。基于统计的真实移动模型能够完美的描述人类的活动规律，然而数据的搜集往往需要耗费大量的人力物力与时间。

3 消息转发机制

机会网络中节点运动导致网络拓扑不断变化，往往不存在完整的链路可供选择，因此其路由决策可以简化为消息转发过程中下一跳节点的选择与消息副本分配的问题。机会网络的消息转发机制可以多个角度进行分类。从消息向网络中注入的副本数量的角度可以将消息转发机制分为基于转发策略的转发机制与基于复制策略的转发机制。其中，采用基于转发策略转发机制的机会网络中，每个消息存在一个副本，而采用基于复制策略转发机制的机会网络中，每个消息存在多个副本。从是否需要基础设施的角度可以将消息转发机制分为不依赖基础设施的转发机制与依赖基础设施的转发机制。其中，不依赖基础设施的转发机制包括基于传播的转发机制与基于上下文的转发机制，而依赖基础设施的转发机制包括依赖固定基础设施的转发机制与依赖移动基础设施的转发机制。另外还可以按照转发策略将消息转发机制分为基于机会的转发制作、基于预测的转发机制与基于计划的转发机制［15］。其中，基于机会的转发机制是最常见的形式，不判断中间节点是否是最佳选择，基于预测的转发机制通过对历史信息的分析来预测最佳的转发节点，而基于计划的转发机制通过可自主移动的摆渡节点完成消息的转发。

下面对几种典型的路由算法做简要介绍:

Fist Contact［16］与Direct Delivery 算法都是基于转发的策略的路由算法，在消息的传递过程中，网络中只包含一个有效的消息副本。两种算法的区别是:First Contact 算法将消息传递给遇到的第一个节点，而Direct Delivery 算法仅在与目的节点相遇时才将消息转发出去。

Epidemic［17］算法是一种基于复制的路由算法，其本质是一种洪泛算法，每个节点都将消息转发给所遇到的所有节点。在缓存容量不受限制的情况下，该算法能够最大限度的提高消息投递率、降低网络时延。其缺点是对网络资源的需求过大。

Spray and Wait［18］算法也是一种基于洪泛策略的算法，节点在相遇时向对方复制消息，与Epidemic 不同的是Spray and Wait 通过限定消息副本数量的方式避免洪泛现象的产生。Spray and Wait 算法分为Spray 与Wait 两个阶段。在Spray 阶段，源节点向网络中注入固定数目的消息副本，然后进入Wait 阶段，若消息副本在上一阶段没有被送达目标节点，则携带消息的节点通过Direct Delivery 方式完成消息的传递。

PRoPHET［19］算法是一种基于预测的路由算法，该算法定义了一种预测节点间成功传输概率的方法。节点在相遇时更新传输预测值，并以此为依据决定是否转发数据分组。

MaxProp［20］算法是一种基于调度策略的路由算法，其核心机制是节点维护的消息队列，该队列按照消息优先级排序，并将其作为消息传输与丢弃的依据。其中，消息的优先级主要由链路的历史数据确定。

4 拥塞控制

与传统IP 网络不同，机会网络适用的环境一般具有延迟长、抖动严重、间歇性连接、数据流非对称以及资源受限等特征，传统的拥塞控制机制不能达到理想的效果。同时，“存储—携带—转发”的路由模式也给机会网络的拥塞控制带来了新的挑战。根据引起拥塞的资源不同，可以将机会网络中出现的拥塞现象分为三种类型:节点级拥塞、链路级拥塞与区域级拥塞。

节点级拥塞是由于节点计算、通信或存储等能力不足引起的，通常情况下表现为节点在与其他节点相遇的有限时间内不能完成消息的处理、传输，或节点接收的消息超出其缓存容量而被迫丢弃部分消息。产生节点级拥塞的原因是节点能力不足，在不增加节点能力的条件下，可以通过设计合理的缓存管理策略，选择成功投递几率较大的消息优先处理，以达到整体上提升投递率的目的。

链路级拥塞是由无线信道资源不足引起的，通常情况下表现为多个节点持续竞争使用无线信道，产生访问冲突现象，极大的降低了链路的利用率，从而影响网络吞吐量。产生链路级拥塞的原因是节点缺乏高效信道感知与动态频谱接入的能力，可通过引入认知无线电的相关研究内容，为机会网络提供智能的频谱感知、分配与接入能力。

区域级拥塞是由网络吞吐量不足引起的，通常表现为一个地理区域的流量过载。在不提高网络容量条件下，为网络提供有效的负载均衡策略，能够在一定层度上缓解区域级拥塞的程度。

5 机会网络面临的挑战

目前，尽管学术界对机会网络的研究取得了一定的成果，但随着机会网络应用环境的不断扩展，其自身发展与需求也呈现出了多样化的趋势。因此，未来机会网络的研究将面临高效、通用、安全与节能等方面的挑战:

(1)设计高效的机会网络路由算法一直是机会网络研究的热点问题。如何利用社会网络分析理论提高机会网络路由效率将成为机会网络路由设计的重要方向。

(2)机会网络是一种典型的覆盖网络，设计通用的机会通信中间件能够扩展机会网络的使用范围与应用场景。

(3)与传统无线网络一样，机会网络也面临着各种安全威胁，而机会网络的特殊性又使得常规的安全机制不能达到理想的防范效果。因此，适用于机会网络的安全保障机制必将成为研究的热点问题。

(4)绿色节能是网络研究的新方向，机会网络中节点能量有限，为其设计高效节能的协议是机会网络大规模部署的基础。

另外，基于机会网络的应用开发与部署也将成为未来重要的研究方向。

6 结 语

机会网络是一种面向缺乏端到端连接通信环境的移动自组织网络，能够在缺乏网络基础设施的条件下，为用户提供移动互联网的接入能力。本文从概念、结构、节点运动模型、消息传递机制以及拥塞控制几方面对机会网络作了简要介绍，并对未来可能存在的挑战进行了展望。从中可以看出，虽然机会网络的相关研究已经取得了一定的成就，但还有很多问题需要进一步研究。期望通过对现有机会网络研究成果的总结与分析，为本领域研究人员的深入研究探明方向。

［1］Pelusi L，Passarella A，Conti M.Opportunistic networking:data forwarding in disconnected mobile ad hoc networks［J］.Communications Magazine，IEEE，2006，44(11):134－141.

［2］Fall K.A delay－tolerant network architecture for challenged internets［C］//Proceedings of the 2003 conference on Applications，technologies，architectures，and protocols for computer communications.ACM，2003:27－34.

［3］熊永平，孙利民，牛建伟，等.机会网络［J］.软件学报，2009，20(1):124－137.

［4］林闯，董扬威，单志广.基于DTN 的空间网络互联服务研究综述［J］.计算机研究与发展，2014，51(5):931－943.

［5］Ker nen A，Ott J，Krkkinen T.The ONE simulator for DTN protocol evaluation［C］//Proceedings of the 2nd international conference on simulation tools and techniques.ICST (Institute for Computer Sciences，Social－Informatics and Telecommunications Engineering)，2009:55.

［6］Broch J，Maltz D A，Johnson D B，et al.A performance comparison of multi－hop wireless ad hoc network routing protocols［C］//Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking.ACM，1998:85－97.

［7］Bettstetter C.Mobility modeling in wireless networks:categorization，smooth movement，and border effects［J］.ACM SIGMOBILE Mobile Computing and Communications Review，2001，5(3):55－66.

［8］Ekman F，Kernen A，Karvo J，et al.Working day movement model［C］//Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models.ACM，2008:33－40.

［9］Musolesi M，Mascolo C.A community based mobility model for ad hoc network research［C］//Proceedings of the 2nd international workshop on Multi－hop ad hoc networks:from theory to reality.ACM，2006:31－38.

［10］Spyropoulos T，Psounis K，Raghavendra C S.Performance analysis of mobility－assisted routing［C］//Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing.ACM，2006:49－60.

［11］Hsu W，Spyropoulos T，Psounis K，et al.Modeling time－variant user mobility in wireless mobile networks［C］//INFOCOM 2007.26th IEEE International Conference on Computer Communications.IEEE.IEEE，2007:758－766.

［12］Eagle N，Pentland A.Reality mining:sensing complex social systems［J］.Personal and ubiquitous computing，2006，10(4):255－268.

［13］UCSD.Wireless topology discovery project，［EB/OL］.http://sysnet.ucsd.edu/wtd/wtd.html.

［14］Diot C，et al.Haggle project.［EB/OL］.http://www.haggleproject.org.

［15］Tang L，Zheng Q，Liu J，et al.SMART:A selective controlled－flooding routing for delay tolerant networks［C］//Broadband Communications，Networks and Systems，2007.BROADNETS 2007.Fourth International Conference on.IEEE，2007:356－365.

［16］Jain S，Fall K，Patra R.Routing in a delay tolerant network［M］.ACM，2004.

［17］Vahdat A，Becker D.Epidemic routing for partially connected ad hoc networks［R］.Technical Report CS－200006，Duke University，2000.

［18］Spyropoulos T，Psounis K，Raghavendra C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks［C］//Proceedings of the 2005 ACM SIGCOMM workshop on Delay－tolerant networking.ACM，2005:252－259.

［19］Marfia G，Pau G，De Sena E，et al.Evaluating vehicle network strategies for downtown Portland:opportunistic infrastructure and the importance of realistic mobility models［C］//Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking.ACM，2007:47－51.

［20］Burgess J，Gallagher B，Jensen D，et al.MaxProp:Routing for Vehicle－Based Disruption－Tolerant Networks［C］//INFOCOM.2006，6:1－11.