2. 加拿大多伦多大学 机械与工业工程系,安大略 多伦多 M5S 1A1
2. Department of Mechanical and Industrial Engineering, University of Toronto, Toronto M5S 1A1, Canada
机会网络[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 轨迹分析在对节点轨迹进行分析时,可以把节点在不同时刻所处的位置看作是随机变量
针对某一节点
$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的前一个位置
$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} $ |
以此类推,可以得到在已知节点
利用所采集的2015年12月1日—2015年12月31日北京市500辆出租车轨迹数据集,通过上述方法分析节点移动的可预测性。得到如图1所示的仿真结果。
Download:
|
|
我们知道随机变量的条件熵越小,则该随机变量的不确定性越小。本文中,节点随机变量
针对城市中主干道路的分布,将城市地图中的路口、路段以网格的形式呈现,将道路网络建模为
图2为轨迹预测流程,通过分析节点的历史轨迹数据,划分节点的单位活动区域,计算节点移动到不同位置的概率,并分别提取出不同节点的兴趣区域分布情况,从而根据节点当前及上一刻的位置预测节点下一时间单元的位置,由此串联成一段节点移动轨迹。
Download:
|
|
节点的轨迹数据可以整理为包含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} $ |
式中:
定义单位活动区域为以该节点在一个预测时间单元内可以移动到的位置为边界的区域。如图3(a)所示。实际上由于节点移动时具有不同的速度,该区域应呈现不规则形状,为计算简单,本文将节点在短时间内的运动近似看作是匀速运动,则该区域可看作是一个以该节点当前位置为圆心的圆形,且半径为该节点在一个预测时间单元内的移动距离,如图3(b)所示。
Download:
|
|
$ R=\Delta D=D_{n}-D_{n-1}=\left(\frac{v_{n}+v_{n-1}}{2}\right) \cdot \Delta t $ |
在道路网络上,单位活动区域所覆盖的范围可以由
Download:
|
|
在轨迹分析中可以得到结论:当已知节点的前2个位置状态时,可以更准确地预测出节点的下一位置。因此,考虑节点的前2个位置
Download:
|
|
根据节点的长期历史轨迹数据推测出不同节点的兴趣点,并以R为半径划分成不同的兴趣点区域,如图6所示。并为不同的兴趣点区域设定不同的移动概率
Download:
|
|
定义节点兴趣因子
$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_e}|{S_c}} \right) = \frac{{{U_{0,n}}}}{{{U_0}}}$ |
式中:
定义预测参数
$Y = \frac{1}{3}I \cdot {P_I} + \frac{2}{3}P\left( {{S_e}|{S_c}} \right)$ |
式中:Sc表示当前时刻节点所在的路段,即图3中的S11,Se表示出口点所在的路段,即图3中出口点e1、e2、e3、e4、e5分别所在的路段S14、S19、S20、S21、S17。分别求出每个Se的
本文基于机会网络的常用仿真工具opportunistic network environment[13](ONE)仿真平台,选用Helsinki道路地图验证分析TPBOR算法的性能。在仿真过程中,节点采用最短路径移动模型,同时运行了SimBet、Prophet、EA-Prophet、TDOR和TPBOR算法,用于对比分析。各项参数设置见表2。
本文主要从投递率、网络开销和平均传输延迟3个方面对比各个算法传输性能的优劣。投递率指仿真过程中,目的节点接收的消息总数与网络中创建的消息总数的比值。网络开销指未成功传输的消息副本数与成功传输的消息副本数的比值。平均传输延迟指消息从创建到成功被目的节点接收的时间。仿真中,分别从不同移动节点数量、不同节点缓存大小和不同消息生存周期3个方面分析对算法性能的影响。
3.2.1 节点数量对算法性能的影响由图7可以看出,随着节点数量的增加,除Prophet协议外,其他协议的传递率都有所提高,同时减少了平均传输延迟,这是因为节点数量增加,使网络密度变大,节点间相遇的概率变大,所以成功传递的消息副本数也随之增加,且传递的延迟降低。而Prophet协议不限制消息副本数,当节点数量增加时,会导致部分消息副本被丢弃,因此传递率下降并大幅度增加网络开销。
Download:
|
|
对比其他算法,TPBOR协议实现了较低的平均传输延迟和较高的传递率,说明TPBOR协议适应网络密度变化的能力更强。
3.2.2 节点缓存大小对算法性能的影响由图8可知,随着节点缓存的增加,Prophet协议的传递率呈现上升的趋势,因为节点缓存的增加使得Prophet协议的缓存能力增强,节点可以储存更多的消息副本,从而提高了传递率。SimBet协议的传递率在节点缓存达到20 MB后趋于稳定,是因为在稀疏的网络环境中,节点生成的消息副本数有限,所以继续增加节点缓存大小对消息的成功传递影响不大。
Download:
|
|
在TPBOR、EA-Prophet协议中,网络初始化阶段节点就已经创建出多个消息副本,所以节点缓存大小并不会明显影响节点能够携带的消息副本数,因此对这2种协议的影响不大。TDOR属于单副本协议,在路由过程中不再生成新的消息副本,所以节点缓存大小对该协议的性能没有影响。
通过以上对比可以得出,TPBOR协议能够稳定保持较高传递率和较低的平均传输延迟,说明TPBOR协议对不同节点的适应能力更强。
3.2.3 不同消息生存周期对算法性能的影响由图9可得,SimBet和TDOR协议的传递率随消息生存周期的增加而增加,因为消息生存周期的增加可以使消息有更大的机会到达目的节点,从而提高了传递率,但同时也增大了平均传输延迟。在EA-Prophet和TPBOR协议中,中继节点的选择更为明确,所以部分生存周期较小的消息副本会被直接丢弃,因此消息生存周期对这2种协议性能的影响不大。
Download:
|
|
对比其他算法,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) |