一种基于轨迹预测的机会网络路由协议

王桐，单欣，郑欣蕊

1. 哈尔滨工程大学 信息与通信工程学院，黑龙江 哈尔滨 150001 2. 加拿大多伦多大学 机械与工业工程系，安大略 多伦多 M5S 1A1

机会网络[1]是一种可以允许消息源和目的节点之间的通信链路不完整，甚至不具备通信链路的自组织网络。其与传统的TCP/IP 网络相比不同的是，ONs 可以解决由于缺乏基础设施而引起的通信链路频繁断开的通信问题。ONs 采用“存储−携带−转发”的消息传输模式，利用节点移动相遇中继消息，直到与目的节点相遇。

消息传递是机会网络研究的热门问题之一，较高的消息传递成功率建立在为每个消息找到最佳的中继节点之上。近年来，越来越多的研究人员提出了各类ONs 路由算法，例如基于拓扑的路由协议：Epidemic[2]、Spray and Wait[3]，这类路由协议策略比较简单，选择中继节点的盲目性较强，实现较高传递成功率的代价是较低的资源利用率；为避免盲目选择中继节点，提出基于社会性的路由协议：SimBet[4]、EBR[5]，这类路由协议结合节点的社会属性选择中继节点，具有减少网络资源消耗，限制消息副本分发等优点，但同时增大了消息的传输延时；针对现有大多数协议都忽视的消息传递过程中的能耗问题，提出基于能量效用转发策略的路由协议：EA-Prophet[6]、SPARE[7]，这类路由协议根据节点的剩余能量选择中继节点，以实现消息的有效传递，但存在着降低网络开销的同时却增加了传输延迟的风险；基于地理的路由协议：GeoDTN[8]、GeoSpray[9]，这类路由协议考虑到在不同的地理环境中，节点移动所表现的不同特征，采用最短路径的方式选择中继节点，但容易受到局部最大值的影响，从而降低成功率；基于轨迹的路由协议：TBF[10]、TDOR[11]，这类路由协议根据消息传递路线与节点位置的相关性选择中继节点，但通常需要在消息传递开始前获得消息传递路线，且消息传递性能受传递路线形状影响较大，针对该问题，本文提出通过历史数据与节点的社会性，预测节点移动轨迹选择中继节点，从而确定消息传递路线的方法，仿真结果表明了算法的有效性。

1 轨迹分析

在对节点轨迹进行分析时，可以把节点在不同时刻所处的位置看作是随机变量L，根据前k(0≤k

表1 节点轨迹分析的符号定义

针对某一节点i，其历史轨迹集可以由一系列的位置点表示成 Ti={L1,L2,···,Ln}，分别对应第1 ～n个时刻节点的位置。由此，我们可以得到节点i在 位置 Lm的概率以及随机变量 L的熵为

在当节点i的前一个位置 Lm−1已知的情况下，节点在位置 Lm的 概率以及随机变量 L的条件熵为

以此类推，可以得到在已知节点 i的 前 k个位置的情况下，节点在随机变量 L的条件熵为：H(L|Lm−1,Lm−2,···,Lm−k)。

利用所采集的2015 年12 月1 日—2015 年12 月31 日北京市500 辆出租车轨迹数据集，通过上述方法分析节点移动的可预测性。得到如图1 所示的仿真结果。

图1 轨迹分析仿真

我们知道随机变量的条件熵越小，则该随机变量的不确定性越小。本文中，节点随机变量 L的条件熵越小，则说明节点位置的不确定性越小，即节点轨迹的可预测性越强。如图1 所示，随机变 量 L 的 条 件 熵 H(L|Lm−1,Lm−2,···,Lm−k) 的 值 随 k的增加而减小，并逐渐趋于稳定，说明当已知节点之前的位置状态时，可以更准确地预测出节点的下一位置。

2 轨迹预测

针对城市中主干道路的分布，将城市地图中的路口、路段以网格的形式呈现，将道路网络建模为G =〈C,S〉 ， 其中C ,S分别表示路口和路段的集合。

图2 为轨迹预测流程，通过分析节点的历史轨迹数据，划分节点的单位活动区域，计算节点移动到不同位置的概率，并分别提取出不同节点的兴趣区域分布情况，从而根据节点当前及上一刻的位置预测节点下一时间单元的位置，由此串联成一段节点移动轨迹。

图2 轨迹预测流程

2.1 单位活动区域划分

节点的轨迹数据可以整理为包含N个位置、速度和时间信息的集合

式中： (si,ci)表 示节点的位置信息，即在路段 si上，并向着路口 ci的 方向； (vi,ti)表示节点的速度和时间信息。时间增量 ∆t=tn−tn−1,0 ≤n ≤N −1可以看作一个预测周期，即一个时间单元。

定义单位活动区域为以该节点在一个预测时间单元内可以移动到的位置为边界的区域。如图3(a)所示。实际上由于节点移动时具有不同的速度，该区域应呈现不规则形状，为计算简单，本文将节点在短时间内的运动近似看作是匀速运动，则该区域可看作是一个以该节点当前位置为圆心的圆形，且半径为该节点在一个预测时间单元内的移动距离，如图3(b)所示。

在道路网络上，单位活动区域所覆盖的范围可以由 G′=〈C′,S′〉表示，如图4 中的阴影部分所示。单位活动区域与路段相交的点称为出口点，由e表示。节点从当前位置Li-1到达任一出口点的轨迹可以看作是一个轨迹预测段，如Li−1→c13→e3。

图3 单位活动区域

图4 模拟城市道路网络

2.2 路径选择

在轨迹分析中可以得到结论：当已知节点的前2 个位置状态时，可以更准确地预测出节点的下一位置。因此，考虑节点的前2 个位置 Li−2、 Li−1，从而得到节点的移动方向 Li−2→Li−1，进而将Gˊ缩小，得到几种可能轨迹预测段，如图5。

图5 轨迹预测段的可能情况

2.3 概率计算

根据节点的长期历史轨迹数据推测出不同节点的兴趣点，并以R为半径划分成不同的兴趣点区域，如图6 所示。并为不同的兴趣点区域设定不同的移动概率 PI，即节点移动进入到兴趣点区域的概率。

图6 兴趣点区域分布

定义节点兴趣因子I ，表示节点单位活动区域与路段相交的出口点是否落入该节点的兴趣点区域中。

在实际场景中，节点的轨迹与日常生活息息相关。在不同时段内，轨迹的数量和位置分布有很大不同，因此，节点移动轨迹的预测考虑时间因素很有必要。本文将每天均匀划分为N=4 个时段，并分别计算4 个时段内的概率转移矩阵M(S,tN)，以达到最佳的轨迹预测效果。

式中：tN表示4 个时段，N=1,2,3,4；概率 P(Sn|S0)表示节点由路段S0到路段Sn的概率，可由在历史轨迹数据中提取的该节点在该路段处出现的次数计算：

式中： U0表示在历史轨迹数据中，该节点出现在路段S0的次数； U0,n表示在历史轨迹数据中，该节点前一路段状态为S0，下一路段状态为Sn的次数，即节点经历轨迹段 S0→Sn的次数。

定义预测参数 Y表示该路段是节点下一路段的可能性， Y越大，说明节点在下一时间单元到达该路段的可能性越大，本文选取具有 Ymax的路段作为一个预测轨迹段的终点。

式中：Sc表示当前时刻节点所在的路段，即图3 中的S11，Se表示出口点所在的路段，即图3 中出口点e1、e2、e3、e4、e5分 别 所 在 的 路 段S14、S19、S20、S21、S17。分别求]出每个Se的 Y 值，则Ymax=max[YS19,YS20,YS21,YS17

3 仿真结果及分析

3.1 仿真环境

本文基于机会网络的常用仿真工具opportunistic network environment[13](ONE)仿真平台，选用Helsinki 道路地图验证分析TPBOR 算法的性能。在仿真过程中，节点采用最短路径移动模型，同时运行了SimBet、Prophet、EA-Prophet、TDOR和TPBOR 算法，用于对比分析。各项参数设置见表2。

表2 仿真参数设置

3.2 结果分析

本文主要从投递率、网络开销和平均传输延迟3 个方面对比各个算法传输性能的优劣。投递率指仿真过程中，目的节点接收的消息总数与网络中创建的消息总数的比值。网络开销指未成功传输的消息副本数与成功传输的消息副本数的比值。平均传输延迟指消息从创建到成功被目的节点接收的时间。仿真中，分别从不同移动节点数量、不同节点缓存大小和不同消息生存周期3 个方面分析对算法性能的影响。

3.2.1 节点数量对算法性能的影响

由图7 可以看出，随着节点数量的增加，除Prophet 协议外，其他协议的传递率都有所提高，同时减少了平均传输延迟，这是因为节点数量增加，使网络密度变大，节点间相遇的概率变大，所以成功传递的消息副本数也随之增加，且传递的延迟降低。而Prophet 协议不限制消息副本数，当节点数量增加时，会导致部分消息副本被丢弃，因此传递率下降并大幅度增加网络开销。

对比其他算法，TPBOR 协议实现了较低的平均传输延迟和较高的传递率，说明TPBOR 协议适应网络密度变化的能力更强。

图7 节点数量对路由协议的影响

3.2.2 节点缓存大小对算法性能的影响

由图8 可知，随着节点缓存的增加，Prophet协议的传递率呈现上升的趋势，因为节点缓存的增加使得Prophet 协议的缓存能力增强，节点可以储存更多的消息副本，从而提高了传递率。SimBet协议的传递率在节点缓存达到20 MB 后趋于稳定，是因为在稀疏的网络环境中，节点生成的消息副本数有限，所以继续增加节点缓存大小对消息的成功传递影响不大。

图8 节点缓存对路由协议的影响

在TPBOR、EA-Prophet 协议中，网络初始化阶段节点就已经创建出多个消息副本，所以节点缓存大小并不会明显影响节点能够携带的消息副本数，因此对这2 种协议的影响不大。TDOR 属于单副本协议，在路由过程中不再生成新的消息副本，所以节点缓存大小对该协议的性能没有影响。

通过以上对比可以得出，TPBOR 协议能够稳定保持较高传递率和较低的平均传输延迟，说明TPBOR 协议对不同节点的适应能力更强。

3.2.3 不同消息生存周期对算法性能的影响

由图9 可得，SimBet 和TDOR 协议的传递率随消息生存周期的增加而增加，因为消息生存周期的增加可以使消息有更大的机会到达目的节点，从而提高了传递率，但同时也增大了平均传输延迟。在EA-Prophet 和TPBOR 协议中，中继节点的选择更为明确，所以部分生存周期较小的消息副本会被直接丢弃，因此消息生存周期对这2种协议性能的影响不大。

图9 消息生存周期对路由协议的影响

对比其他算法，TPBOR 协议实现了较低的平均传输延迟和较高的传递率，说明TPBOR 协议对不同消息的适应能力更强，TPBOR 协议应用范围更广。

4 结论

本文提出一种基于轨迹预测的机会网络通信协议，通过ONE 仿真平台，利用真实地图对路由算法进行实验仿真，以传递率、网络开销和平均传输延迟为评价指标。仿真结果说明对比其他各类型路由协议，基于轨迹预测的路由协议能够明显提高消息传递的成功率，同时降低平均传输延迟，但相对增加了网络开销，在一定程度上造成网络负载过重。未来可以针对网络开销对该协议进行优化。