«上一篇
文章快速检索     高级检索
下一篇»
  应用科技  2020, Vol. 47 Issue (3): 94-99  DOI: 10.11991/yykj.201909020
0

引用本文  

王桐, 单欣, 郑欣蕊. 一种基于轨迹预测的机会网络路由协议[J]. 应用科技, 2020, 47(3): 94-99. DOI: 10.11991/yykj.201909020.
WANG Tong, SHAN Xin, ZHENG Xinrui. An opportunistic network routing protocol based on trajectory prediction[J]. Applied Science and Technology, 2020, 47(3): 94-99. DOI: 10.11991/yykj.201909020.

基金项目

国家自然科学基金项目(51779050)

通信作者

王桐,E-mail:wangtong@hrbeu.edu.cn

作者简介

王桐,男,副教授,博士;
单欣,女,硕士研究生

文章历史

收稿日期:2019-09-29
网络出版日期:2020-05-28
一种基于轨迹预测的机会网络路由协议
王桐1, 单欣1, 郑欣蕊2    
1. 哈尔滨工程大学 信息与通信工程学院,黑龙江 哈尔滨 150001;
2. 加拿大多伦多大学 机械与工业工程系,安大略 多伦多 M5S 1A1
摘要:为解决机会网络(opportunistic networks, ONs)中链路的频繁断开、节点的高速移动以及稀疏的网络密度等问题,提出了基于节点移动的历史数据和节点的社会性预测节点轨迹的方法,选取中继节点完成消息传递的机会网络路由协议。首先利用条件熵分析节点轨迹的可预测性;然后根据速度和预测单元,对节点进行单位活动区域的划分;最后利用节点移动概率及其社会性,对节点的下一位置进行预测。仿真结果表明:轨迹预测可以有效解决因节点高速移动,位置不断变化而导致的网络连通性时好时坏、极易断开的问题;基于轨迹预测的通信协议达到了较好的传递成功率,实现了对消息的高效传递。
关键词机会网络    轨迹预测    历史数据    条件熵    网格划分    社会性    概率计算    消息传递    
An opportunistic network routing protocol based on trajectory prediction
WANG Tong1, SHAN Xin1, ZHENG Xinrui2    
1. College of Information and Communication Engineering, Harbin Engineering University, Harbin 150001, China;
2. Department of Mechanical and Industrial Engineering, University of Toronto, Toronto M5S 1A1, Canada
Abstract: According to the characteristics such as frequent disconnection of links, the high-speed movement of nodes and the density of sparse network in opportunistic networks (ONs), this paper proposes a method based on the historical data of node movement and the nodes’ sociality to predict trajectory of nodes, and then to select relay nodes to complete the routing protocol of the opportunity network for message transmission. First, conditional entropy is used to analyze the predictability of node trajectories. Then, the node’s unit active area is divided according to the node’s speed and prediction unit. Finally, using the node movement probability and its sociality, the next position of the node is predicted. The simulation results show that the trajectory prediction can effectively solve the problem that the network connectivity is easily disconnected due to the high-speed movement of the nodes and the constant change of nodes’ position. The communication protocol based on trajectory prediction has a good delivery success rate and achieves high-efficiecy delivery of messages.
Keywords: opportunity network    trajectory prediction    historical data    conditional entropy    meshing    sociality    probability calculation    message delivery    

机会网络[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\left( {0 \leqslant k < n} \right)$ 个状态计算 $L$ 的熵及条件熵[12],并依据条件熵的定义判断随机变量的不确定性,揭示节点轨迹的可预测性。节点轨迹有关变量定义如表1所示。

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

针对某一节点 $i$ ,其历史轨迹集可以由一系列的位置点表示成 ${T_i} = \left\{ {{L_1},{L_2}, \cdots ,{L_n}} \right\}$ ,分别对应第 $1 \sim n$ 个时刻节点的位置。由此,我们可以得到节点 $i$ 在位置 ${L_m}$ 的概率以及随机变量 $L$ 的熵为

$P\left( {{L_m}} \right) = \frac{{{n_m}}}{{{n_0}}}$
$H\left( L \right) = - \sum\limits_{m = 1}^n {P\left( {{L_m}} \right) \cdot {{{\rm{lb}} }}} P\left( {{L_m}} \right)$

在当节点i的前一个位置 ${L_{m - 1}}$ 已知的情况下,节点在位置 ${L_m}$ 的概率以及随机变量 $L$ 的条件熵为

$P\left( {{L_m},{L_{m - k}}} \right) = \frac{{{n_{m - 1,m}}}}{{{n_1}}}$
$ \begin{array}{l} H\left( {L|{L_{m - 1}}} \right) = H\left( {L,{L_{m - 1}}} \right) - H\left( {{L_{m - 1}}} \right) = \\ - \displaystyle\sum\limits_{m = 1}^n {P\left( {{L_m},{L_{m - 1}}} \right) \cdot {{{\rm{lb}} }}} P\left( {{L_m},{L_{m - 1}}} \right) + \\ \displaystyle\sum\limits_{m = 1}^n {P\left( {{L_{m - 1}}} \right) \cdot {{{\rm{lb}} }}} P\left( {{L_{m - 1}}} \right) \\ \end{array} $

以此类推,可以得到在已知节点 $i$ 的前 $k$ 个位置的情况下,节点在随机变量 $L$ 的条件熵为: $H\left( {L|{L_{m - 1}},{L_{m - 2}}, \cdots ,{L_{m - k}}} \right)$

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

Download:
图 1 轨迹分析仿真

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

2 轨迹预测

针对城市中主干道路的分布,将城市地图中的路口、路段以网格的形式呈现,将道路网络建模为 $G = \left\langle {C,S} \right\rangle $ ,其中 $C,S$ 分别表示路口和路段的集合。

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

Download:
图 2 轨迹预测流程
2.1 单位活动区域划分

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

$ \begin{split} T =& \left\{ {\left[ {\left( {{s_0},{c_0}} \right),\left( {{v_0},{t_0}} \right)} \right], \cdots ,} \right.\left[ {\left( {{s_i},{c_i}} \right),\left( {{v_i},{t_i}} \right)} \right], \cdots ,\\ &\left[ {\left( {{s_{N - 1}},{c_{N - 1}}} \right),} \right. \left. {\left. {\left( {{v_{N - 1}},{t_{N - 1}}} \right)} \right]} \right\} \end{split} $

式中: $({{s_i},{c_i}})$ 表示节点的位置信息,即在路段 ${s_i}$ 上,并向着路口 ${c_i}$ 的方向; $({{v_i},{t_i}})$ 表示节点的速度和时间信息。时间增量 $\Delta t=t_{n}-t_{n-1}, 0 \leqslant n \leqslant N-1$ 可以看作一个预测周期,即一个时间单元。

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

Download:
图 3 单位活动区域
$ R=\Delta D=D_{n}-D_{n-1}=\left(\frac{v_{n}+v_{n-1}}{2}\right) \cdot \Delta t $

在道路网络上,单位活动区域所覆盖的范围可以由 $G'=\langle C', S'\rangle$ 表示,如图4中的阴影部分所示。单位活动区域与路段相交的点称为出口点,由e表示。节点从当前位置Li-1到达任一出口点的轨迹可以看作是一个轨迹预测段,如 $L_{i-1} \rightarrow c_{13} \rightarrow e_{3}$

Download:
图 4 模拟城市道路网络
2.2 路径选择

在轨迹分析中可以得到结论:当已知节点的前2个位置状态时,可以更准确地预测出节点的下一位置。因此,考虑节点的前2个位置 $L_{i-2}$ $L_{i-1}$ ,从而得到节点的移动方向 $L_{i-2} \rightarrow L_{i-1}$ ,进而将缩小,得到几种可能轨迹预测段,如图5

Download:
图 5 轨迹预测段的可能情况
2.3 概率计算

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

Download:
图 6 兴趣点区域分布

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

$I = \left\{ \begin{array}{l} 0,{\rm{ }}{\text{出口点不在兴趣点区域}}{\rm{ }}\\ 1,{\rm{ }}{\text{出口点落入兴趣点区域}} \end{array} \right.$

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

$ {{M}}\left(S, t_{N}\right)=\left[\begin{array}{cccc} P\left(S_{0} | {S}_{0}\right) & P\left(S_{1} | {S}_{0}\right) & \cdots & P\left(S_{n} | {S}_{0}\right) \\ P\left(S_{0} | {S}_{1}\right) & P\left(S_{1} | {S}_{1}\right) & \cdots & P\left(S_{n} | {S}_{1}\right) \\ \vdots & \vdots & & \vdots \\ P\left(S_{0} | {S}_{n}\right) & P\left(S_{1} | {S}_{n}\right) & \cdots & P\left(S_{n} | {S}_{n}\right) \end{array}\right] $

式中:tN表示4个时段,N=1,2,3,4;概率 $P\left(S_{n} | {S}_{0}\right)$ 表示节点由路段S0到路段Sn的概率,可由在历史轨迹数据中提取的该节点在该路段处出现的次数计算:

$P\left( {{S_e}|{S_c}} \right) = \frac{{{U_{0,n}}}}{{{U_0}}}$

式中: ${U_0}$ 表示在历史轨迹数据中,该节点出现在路段S0的次数; ${U_{0,n}}$ 表示在历史轨迹数据中,该节点前一路段状态为S0,下一路段状态为Sn的次数,即节点经历轨迹段 $S_{0} \rightarrow S_{n}$ 的次数。

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

$Y = \frac{1}{3}I \cdot {P_I} + \frac{2}{3}P\left( {{S_e}|{S_c}} \right)$

式中:Sc表示当前时刻节点所在的路段,即图3中的S11Se表示出口点所在的路段,即图3中出口点e1e2e3e4e5分别所在的路段S14S19S20S21S17。分别求出每个Se $Y$ 值,则 ${Y_{\max }} = \max \left[ {{Y_{{S_{14}}}},} \right. \left. {{Y_{{S_{19}}}},{Y_{{S_{20}}}},{Y_{{S_{21}}}},{Y_{{S_{17}}}}} \right]$

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协议不限制消息副本数,当节点数量增加时,会导致部分消息副本被丢弃,因此传递率下降并大幅度增加网络开销。

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

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

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

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

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

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

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

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

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

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

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

4 结论

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

参考文献
[1] 马华东, 袁培燕, 赵东. 移动机会网络路由问题研究进展[J]. 软件学报, 2015, 26(3): 600-616. (0)
[2] DE RANGO F, AMELIO S, FAZIO P. Enhancements of epidemic routing in delay tolerant networks from an energy perspective[C]//Proceedings of the 2013 9th International Wireless Communications and Mobile Computing Conference, Sardinia, Italy, 2013: 731–735. (0)
[3] HUANG Wei, ZHANG Sihai, ZHOU Wuyang. Spray and wait routing based on position prediction in opportunistic networks[C]//Proceedings of the 2011 3rd International Conference on Computer Research and Development, Shanghai, 2011: 232–236. (0)
[4] DALY E M, HAAHR M. Social network analysis for routing in disconnected delay-tolerant MANETs[C]//Proceedings of the 8th ACM International Symposium on Mobile ad Hoc Networking and Computing. Montreal, Quebec, 2007: 32–40. (0)
[5] NELSON S C, BAKHT M, KRAVETS R. Encounter-based routing in DTNs[C]//Proceedings of IEEE INFOCOM 2009, Rio de Janeiro, Brazil, 2009: 846–854. (0)
[6] BISTA B B, RAWAT D B. EA-PRoPHET: an energy aware prophet-based routing PRoTOCOL for delay tolerant networks[C]//Proceedings of the 2017 IEEE 31st International Conference on Advanced Information Networking and Applications, Taipei, China, 2017: 670–677. (0)
[7] WANG Tong, TANG Mengbo, SONG Houbing, et al. Opportunistic protocol based on social probability and resources efficiency for the intelligent and connected transportation system[J]. Computer networks, 2019, 149: 173-186. DOI:10.1016/j.comnet.2018.11.034 (0)
[8] LINK J A B, SCHMITZ D, WEHRLE K. GeoDTN: geographic routing in disruption tolerant networks[C]//Proceedings of 2011 IEEE Global Telecommunications Conference, Houston, USA, 2011: 1–5. (0)
[9] SOARES V N G J, RODRIGUES J J P C, FARAHMAND F. GeoSpray: a geographic routing protocol for vehicular delay-tolerant networks[J]. Information fusion, 2014, 15: 102-113. DOI:10.1016/j.inffus.2011.11.003 (0)
[10] NICULESCU D, NATH B. Trajectory based forwarding and its applications[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networking, San Diego, USA, 2003: 260–272. (0)
[11] CAO Yue, KAIWARTYA O, ASLAM N, et al. A trajectory-driven opportunistic routing protocol for VCPS[J]. IEEE transactions on aerospace and electronic systems, 2018, 54(6): 2628-2642. DOI:10.1109/TAES.2018.2826201 (0)
[12] 陈思静, 张可. VANETs中的车辆移动规律性及轨迹预测研究[J]. 计算机工程与应用, 2016, 52(18): 139-143. DOI:10.3778/j.issn.1002-8331.1410-0313 (0)
[13] SPAHO E, BAROLLI L, KOLICI V, et al. Performance evaluation of different routing protocols in a vehicular delay tolerant network[C]//Proceedings of 2015 10th International Conference on Broadband and Wireless Computing, Communication and Applications, Krakow, Poland, 2015: 157–162. (0)