基于转发效用和拥塞感知的机会网络路由算法

王希波，王 桐

(哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001)

对于移动机会网络[1]来说，选择合适的中继节点来携带数据包对于网络传输的性能至关重要，同时在节点上制定适当的数据包管理策略也能提升网络数据处理能力，而这两者都要取决于网络路由算法的性能.直接交付(Direct Delivery, DD)[2]和传染转发(Epidemic)[3]作为两类简单且各具特色的路由策略最先被学者们提出.DD算法中源节点产生的数据包只有遇到目的节点才进行传递，优势是网络资源消耗少，但存在传递时延较大和投递成功率较低的劣势.Epidemic算法属于一种洪泛算法，节点会与移动过程相遇的所有节点交换本身没有储存的数据包副本，对于网络资源比较依赖.考虑到网络资源的消耗问题，研究人员提出Spray and Wait[4]、Spray and Focus[5]等路由算法；通过记录、分析和利用节点间的历史接触信息，Prophet[6]、MaxProp[7]等路由算法被提出；在结合社会属性方面，SimBet[8]、PeopleRank[9]、BubbleRap[10]是比较具有代表性的路由算法；GeoSpray[11]、GeoDTN[12]等路由算法则将地理信息考虑到路由算法设计中，但在移动机会网络中数据包目的节点通常处于移动状态，很难确定地理位置信息.通过分析这些路由算法可知，现阶段关于路由算法的研究主要是利用网络中获取的局部节点信息分析节点属性，包括社会信息、接触信息以及地理信息，未能考虑节点数据处理能力，容易导致数据传输过程部分节点的传输压力较大，不利于提高网络整体性能.因此，本文将节点转发效用和缓存拥塞感知用于数据包的转发和缓存管理过程，提出基于转发效用和拥塞感知的机会网络路由算法(Routing Algorithm based on Forwarding Utility and Congestion Awareness in opportunistic network, RAFUCA).图1所示为路由算法的整体框架.

图1 路由算法整体框架Figure 1 Framework of routing algorithm

1 节点转发效用

移动机会网络中节点通过机会接触进行信息传播，因此通过记录节点间的接触信息并进一步分析可以为数据包转发提供信息支撑.本文利用节点接触信息提取节点转发效用，包括节点接触概率和节点接触活跃度.

1.1 节点接触概率

(1)

图2 节点接触分布Figure 2 Contact distribution between nodes

图3为Infocom2005数据集节点39与其他节点接触时刻分布，图4为Infocom2006[13]数据集节点22与其他节点接触时刻分布.通过图3、4可知，网络运行期间节点接触呈现一定时变特性.因此采用时间窗口并以平滑加权方式计算接触概率，如式(2)所示，其中Ti为第i个时间窗口，平滑系数ρ设置为0.5.

(2)

图3 Infocom2005数据集：节点39接触时刻分布Figure 3 Infocom2005 dataset: contact time distribution of node 39

图4 Infocom2006数据集：节点22接触时刻分布Figure 4 Infocom2006 dataset: contact time distribution of node 22

1.2 节点接触活跃度

节点接触概率主要用于评价转发节点与目的节点的未来接触的可能性，而在一定时间内网络区域内部分节点与目的节点接触不存在接触历史，因此在本节中提出节点接触活跃度进行节点转发效用评价，保障网络传输的可靠性.

当节点x和节点y接触时，节点间的接触亲密度更新如式(3)所示，其中：Fx,y初始值为0，Pint设置为0.7.节点间接触越频繁则节点间亲密度越高.

Fx,y=Fx,y+(1-Fx,y)×Pint

(3)

(4)

在计算节点接触活跃度时仍采用时间窗口和平滑加权方式计算接触概率，如式(5)所示，其中Ti为第i个时间窗口，平滑系数α设置为0.5.

(5)

2 节点拥塞感知

2.1 节点拥塞系数

(6)

(7)

如图5所示为，K=1，K=5，K=10，对应拥塞系数随缓存空闲比变化的趋势图.由图5可知存在一个阈值使得超过该值的缓存空闲比对应的拥塞系数基本平稳且接近零.K值越大，则拥塞系数对缓存空闲比较小的区域变化越敏感，拥塞系数接近平稳的趋势越快.而K=10对应的阈值在0.5，在剩余缓存空间超过总缓存空间一半时，节点不考虑拥塞问题，而缓存空闲比小于0.5时，缓存空闲比越接近0，拥塞系数对缓存空闲比的变化越敏感.因此在拥塞系数公式中设定K等于10.

图5 拥塞系数随缓存空闲比变化趋势Figure 5 Congestion coefficient variation trend with cache idle ratio

2.2 节点区域拥塞系数

为了分析节点邻近区域网络拥塞程度，定义节点x临近区域拥塞系数如式(8)所示，其中Nx表示x的邻居节点集合，|Nx|表示节点x的邻居节点数目.如果|Nx|等于0，则设置CNx等于1.则节点x对应的区域拥塞系数CZx如式(9)所示，其中平滑权重σ=0.5.

(8)

CZx=σCFx+(1-σ)CNx

(9)

3 数据包转发策略

RAFUCA路由算法转发节点的选取可以分为两个策略，基于节点接触概率的选择策略和基于节点接触活跃度的选择策略.其中，基于节点接触概率的选择策略优先级高于基于节点接触活跃度的选择策略.图6所示为RAFUCA路由算法中数据包转发过程.

(10)

(11)

4 数据包管理策略

4.1 数据包副本初始化

(12)

4.2 数据包转发队列管理

RAFUCA路由算法转发节点选择策略中包含节点接触概率的选择策略和节点接触活跃度的选择策略两种数据包转发策略，因此按照转发策略的不同将数据包转发队列分为数据包接触概率转发队列和节点接触活跃度转发队列.

(13)

(14)

图6 数据包转发过程Figure 6 Packet forwarding process

5 仿真结果分析

为了分析路由算法在真实接触场景下的性能，本文在仿真平台ONE[14]中引入Infocom2006节点接触数据集.Infocom2006数据集观测时间为334 860 s，共98个节点，其中78个节点为普通节点，通信接口速率设置为4 Mbps；20个节点为超级节点，通信接口速率为8 Mb/s；数据包大小为500KB，生存时间默认为300 min，产生间隔默认为40 s；节点缓存默认为20 M.其中：对比算法包括Prophet、Spray and Wait(SaW)、Epidemic、EBRR[15]和EURR[16].EURR、SaW、RAFUCA初始副本数设置为节点总数的30%，EBRR算法的最大转发跳数设置为7.RAFUCA算法的时间窗口按照文献[17]选择300s.其中，路由算法性能主要从投递率、转发代价和平均投递时延三方面进行评价[18].

5.1 节点缓存对网络性能的影响

由图7可知，随着节点缓存的增长所有路由算法的数据包投递率都呈增长趋势，转发代价呈下降趋势，除Prophet算法外其他算法平均投递时延呈现上升趋势.因为节点缓存资源的增加使得节点可以携带更多的数据包，从而使得数据包副本的覆盖面更广，数据包投递成功率随之增加，同时节点缓存的增长使得部分传输时延较长的数据包得以被传输，所以大部分算法的平均投递时延呈增长趋势.由于Epidemic的洪泛特性使其转发代价远高于其他算法.RAFUCA算法的动态初始副本特性和转发队列管理策略使其在数据包投递率和转发代价方面均优于其他算法.

通过比较投递率、转发代价和平均投递时延三方面的性能，RAFUCA算法在节点缓存变化过程中，整体性能优于其他算法.

图7 节点缓存vs网络传输性能Figure 7 Node cache vs network transmission performance

5.2 数据包生存时长对网络性能的影响

由图8可知，随着数据包生存时间的增长，所有路由算法的投递率呈现上升趋势，平均投递时延呈增长趋势，除Prophet算法外其他算法的转发代价基本呈现下降趋势，Epidemic的洪泛特性使其转发代价远高于其他算法.在数据包生存时间小于60 min时，EBRR和Epidemic算法投递率高于其他算法，这是因为EBRR算法在数据包生存时间较短时，以较大概率采用限制转发跳数的洪泛转发策略，而Epidemic算法采用洪泛策略，所以EBRR投递率高于Epidemic算法.在数据包生存时间大于180 min时，RAFUCA算法在投递率、转发代价方面优于其他算法.

通过比较投递率、转发代价和平均投递时延三方面的性能，RAFUCA算法在数据包生存时间变化过程中，整体性能优于其他算法.

5.3 数据包生成间隔对网络性能的影响

由图9可知，RAFUCA算法的投递率在数据生成间隔的变化过程中都处于较高位置，仅在数据包生成间隔100 s时低于Prophet算法.RAFUCA算法采用动态有限副本且转发节点选择过程采用双转发节点选择策略使得保持数据包投递率的前提下数据包转发代价仍处于较低水平.RAFUCA算法整体呈现平稳趋势，且平均投递时延整体处于较低位置.

通过比较投递率、转发代价和平均投递时延三方面的性能，RAFUCA算法在数据包生成间隔变化过程中，整体性能优于其他算法.

图8 数据包生存时长vs网络传输性能Figure 8 Packet lifetime vs network transmission performance

图9 数据包生存时长vs网络传输性能Figure 9 Packet generation interval vs network transmission performance

6 结 语

本文提出的基于转发效用和拥塞感知的机会网络路由算法RAFUCA利用转发效用进行节点转发能力判定，并建立拥塞模型进行数据包管理.在ONE仿真平台中，通过Infocom2006节点接触数据集验证RAFUCA算法的性能，并在投递率、转发代价和平均投递时延三个性能指标方面与Epidemic、Prophet、SaW、EBRR和EURR路由算法进行对比.仿真结果表明，RAFUCA相比其他算法在投递率、转发代价和平均投递时延方面均表现较为出色，对移动机会网络的环境变化具有较强适应能力.未来的研究将会引入更多网络节点移动模型和真实数据集来验证该协议的性能.