«上一篇
 文章快速检索 高级检索

 应用科技  2020, Vol. 47 Issue (3): 94-99  DOI: 10.11991/yykj.201909020 0

### 引用本文

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.

### 文章历史

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

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 轨迹分析

 $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)$

 $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}$

2 轨迹预测

2.1 单位活动区域划分

 $\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}$

 $R=\Delta D=D_{n}-D_{n-1}=\left(\frac{v_{n}+v_{n-1}}{2}\right) \cdot \Delta t$

2.2 路径选择

2.3 概率计算

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

 ${{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]$

 $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)$

3 仿真结果及分析 3.1 仿真环境

3.2 结果分析

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

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

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