Page 317 - 《软件学报》2021年第8期

张棋飞 等:基于节点运动的机会网络路由算法 2599

DataMULEs [11] 引入了 MULE 节点,在移动过程中收集传感器数据,实现稀疏传感器网络环境下的数据采集.
Message Ferrying [12] 协议在区域内部署 Ferry 节点,按预定义路径或普通节点的通信请求,在移动过程中实现数
据的转发.Zhao 等人 [13] 在 Message Ferrying 的基础上,提出使用多个 Ferry 节点以提高系统的可靠性和传输效率.
(3) 基于效用的路由
基于效用的路由策略通过引入效用值评估选择合适的下一跳节点,避免消息的盲目转发.PQBCF [14] 算法设
计了一个中间中心度指标,用来描述节点在信息传输过程中的参与度和重要度.Zhao 等人 [15] 从延长网络存活时
间的角度出发,提出了一种差分概率转发机制,以节点的剩余能量为度量设计转发策略,以最大化网络生存时
间.SMART [16] 协议通过在邻居节点之间交换朋友关系,将节点接触概率的计算放在发送端进行,降低节点间信
息交换次数.PeopleRank [17] 协议基于经典的 PageRank 算法分布式计算节点中心度,降低传统社会化网络分析方
法的复杂性.BUBBLE [18] 协议考虑节点的社会地位,对节点进行聚类后,利用节点所在的社区信息及中心度信息
转发数据.SCOR [19] 算法利用网络中的社会上下文信息,通过 BP 神经网络模型预测节点的移动行为.针对机会网
络数据转发模式带来的较为严重的流量分配不公以及投递成功率不公问题,FSMF [20] 算法引入用户社会关系马
尔科夫链模型对用户的社会关系进行评价;同时,为了提高公平性,根据用户的社会关系限制消息副本的数量并
限制转发副本的数量.PICD [21] 针对节点循环运动的场景,考虑节点与汇聚点间存在间歇多跳路径的情况,将消
息容忍的延迟与传输概率的计算相结合,利用节点间的周期间歇连通性改善路由性能.PROPHET [22] 协议为网
络中的每一对节点计算投递概率,利用接触概率的传递性更新投递预测概率值,实现数据从低概率节点向高概
率节点的转移,直至抵达目标节点.TOR [23] 算法针对恶意的网络环境设计基于信任机制的路由算法,对参与转发
的中间节点进行信任度评估,利用信任广播周期性地将最新信任路由表反馈给其他节点,从而简化传统信任关
系评估和传播的复杂性.在消息转发过程中,采用沿着信任度递增的梯度转发,提高转发成功率.
以上路由机制中,基于副本的路由策略通过在网络中生成多个消息副本来保证数据的传输.这种消息的复
制对网络资源要求很高,会在网络中产生大量冗余,导致资源浪费.基于主动运动的路由通过引入某些具有移动
功能的特殊节点来辅助数据的传输.此类节点往往具有较强的运动能力、通信能力以及存储能力,与普通节点
差别很大.而且算法假设目标节点的位置是固定的,并没有考虑到移动节点间的数据通信.而基于效用的路由策
略主要利用相遇预测、链路状态以及上下文等信息计算效用值,并没有充分考虑数据传输的不同要求以及节点
自身的运动特质对路由的影响.
机会网络的部分概念来源于早期的间歇式连通网络和延迟容忍网络,这两种网络着重强调应用的延迟容
忍特性.但随着机会网络研究的不断深入,其内涵覆盖更为广泛,承载的业务类型日渐丰富,数据传输的要求也
越来越多样化.在这种情况下,如果还是按照传统模式依靠节点随机运动带来的有限连接机会来传输数据,势必
[7]
无法满足应用多样化的传输需求 .既然机会网络是利用节点移动带来的接触机会传输数据,就应该充分利用
节点的运动特性更好地为数据通信服务.某些情况下,为了满足应用的要求,甚至可以牺牲节点的独立性来保障
传输的质量.我们知道,机会网络中的节点在运动过程中寻找转发机会,正是节点的运动为数据交换提供了可
能.运动独立性从运动的角度反映了节点保障传输任务的能力.一般来说,当前传输任务的优先级越高,节点的
运动独立性越强,在传输过程中越不易受到外来任务的干扰.节点的任务调度按照优先级顺序从高到低依次执
行.当节点承担的新的传输任务优先级高于其原有的任务调度时,应该牺牲节点的运动独立性,将其原有任务暂
时挂起,通过调整节点的运动路线来保障高优先级任务的执行.基于此,本文研究机会网络路由机制的关键技
术,以机会网络的运动特性为切入点,以提高分组路由性能为基本目标,从应用的需求及网络资源的调度出发,
设计了基于运动的机会路由算法 MBOR(motion based opportunistic routing),通过调整节点的运动轨迹,在满足
不同数据传输要求的同时提高分组投递率,降低传输时延.

2 MBOR 路由算法

2.1 数据传输机制
数据在路由到目的地的过程中,一般要经历中继转发和直接交付两个阶段.通常而言,为了获得稳定的数据