一种容迟网络中基于节点移动轨迹的路由决策方法

摘要

本发明公开一种容迟网络中基于节点移动轨迹的路由决策方法。首先，利用半马尔科夫模型获得节点在各社区稳态分布，提出节点移动轨迹热度概念。其次，利用半马尔科夫模型预测节点未来位置分布，提出节点之间移动轨迹相似度概念。再次，提出基于节点移动轨迹路由决策方法，它选择移动轨迹热度较高或者与数据包携带者移动轨迹相似度较低的节点作为中继节点参与数据传播。最后，在真实节点移动轨迹数据上对路由方法进行性能评价，实验结果表明，与最近著名的喷射等待路由方法和基于社会群体路由方法相比，路由方法整体性能优于它们，同时，与经典的传染病路由方法相比，可以明显地降低网络开销，同时接近该方法达到的最大数据包传递率和最低传递延迟。

主权项

一种容迟网络中基于节点移动轨迹的路由决策方法，通过半马尔科夫链模型来建立节点的移动模型，在此模型上得到节点在各社区的稳态分布和未来位置分布，在此基础上，分别计算反映节点访问某一社区的移动轨迹的热度和反映与数据包携带者在未来同时访问相同社区几率的移动轨迹相似度，接着，基于节点移动轨迹的路由决策方法充分利用具有高移动轨迹热度和低移动轨迹相似度的节点作为中继节点，参与数据扩散，并对数据传递扩散效果进行评估，其特征在于，包括以下步骤：(1)、建立节点的移动模型，将节点的移动模型网络划分为若干个社区，根据节点在各社区累计停留时间比例得到节点的社区分布；(a)、假设节点的移动模型网络被分成M‑1个地理位置不重叠的社区C₁,C₂,…,C_M‑1，定义一个虚拟社区C₀，其中C₀表示节点离开网络状态，则社区集合C＝{C₀,C₁,…,C_M‑1}；(b)、假设网络中共有N个节点，它们可以在社区集合C内自由移动，在相邻社区之间转换不耗费时间；(c)、当且仅当任一节点u在社区C_i停留时间占它在所有社区累积时间的比例不低于β₁时，节点u(1≤u≤N)属于社区C_i(1≤i≤M‑1)；(2)、根据节点u历史移动轨迹数据获得转移概率矩阵P^u和由状态i转换到状态j概率分布然后计算节点u在各社区的平稳分布和未来出现在各个社区的概率；(a)、定义马尔科夫更新过程和状态空间S＝{0,1,...,M‑1}，其中状态空间S表示节点u属于哪个社区，表示第n次转换后的状态，表示发生第n次状态转换的时刻，初始值T₀＝0；(b)、假设转移概率矩阵其中表示当前在状态i则下次转移到状态j的概率，根据节点u的移动跟踪数据计算如下：$p_{\mathrm{ij}}^u=\frac{{\mathrm{num}}_{\mathrm{ij}}^u}{{\mathrm{num}}_i^u},---\left(1\right)$其中，表示节点u从状态i到状态j的转移次数，表示节点u从状态i转移出去但下一个状态不一定是状态j的次数；(c)、结合转移概率矩阵P^u，计算稳态转移概率过程如下：${\bar{\pi }}^u={\bar{\pi }}^u{P}^u,\underset{i=0}{\overset{M-1}{\Sigma }}{\bar{\pi }}_i^u=1;---\left(2\right)$(d)、计算节点状态i转换到状态j概率分布时间被离散化为大小为Δt的时间片，用表示下一个状态是j时的节点在当前状态i逗留时间分布，根据节点u的移动轨迹数据，具体计算公式如下：$H_{\mathrm{ij}}^u\left(k\right)=P(t_{\mathrm{ij}}^u<k)=\underset{w=0}{\overset{k-1}{\Sigma }}P(t_{\mathrm{ij}}^u=w),---\left(3\right)$其中表示当下一个状态是j时节点在当前状态i的逗留时间；假定节点u在状态逗留时间变量独立于状态转换过程得齐次半马尔科夫链核Q^u：$\begin{array}{c}{Q}_{\mathrm{ij}}^u\left(k\right)=P(X_{n+1}^u=j,T_{n+1}^u-T_n^u\le k|X_n^u=i)\\ =P(X_{n+1}^u=j|X_n^u=i)·P(T_{n+1}^u-T_n^u\le k|X_{n+1}^u=j,X_n^u=i)\\ =p_{\mathrm{ij}}^u{H}_{\mathrm{ij}}^u\left(k\right),\end{array}---\left(4\right)$其中，是状态i和j之间的转移概率，表示在不迟于时间k节点u由状态i转换到状态j概率；设表示节点u在状态i的逗留时间分布，因此可得，$D_i^u\left(k\right)=\underset{j=1}{\overset{M}{\Sigma }}{Q}_{\mathrm{ij}}^u\left(k\right)---\left(5\right)$由等式(5)和随机变量期望的定义可以计算得到节点u在状态i的平均逗留时间(e)、根据$d_i^u(0\le i\le M-1),$计算用户稳态分布${\pi }^u=[{\pi }_0^u,{\pi }_1^u,...,{\pi }_{M-1}^u];$${\pi }_i^u=\frac{d_i^u{\bar{\pi }}_i^u}{\underset{j=1}{\overset{M}{\Sigma }}{d}_j^u{\bar{\pi }}_j^u},---\left(6\right)$其中，表示节点u在任何时刻位于状态i的概率；(f)、定义齐次半马尔科夫链通过齐次半马尔科夫链来预测节点u未来时刻移动轨迹概率分布情况；该链的瞬态分布用来预测节点u未来kΔt秒时所处的状态，具体定义如下：${\phi }_{\mathrm{ij}}^u\left(k\right)=P(Z_k=j|Z_0=i)=d_{\mathrm{ij}}^u\left(k\right)+\underset{w=0}{\overset{M-1}{\Sigma }}\underset{\tau =1}{\overset{k}{\Sigma }}{v}_{\mathrm{iw}}^u\left(\tau \right){\phi }_{\mathrm{wj}}^u(k-\tau ),$其中，如果i＝j则δ_ij＝1否则为0，由下列公式给出：$v_{\mathrm{ij}}^u\left(k\right)=\left\{\begin{array}{c}{Q}_{\mathrm{ij}}^u\left(1\right),k=1\\ Q_{\mathrm{ij}}^u\left(k\right)-Q_{\mathrm{ij}}^u(k-1),k>1\end{array}\right..---\left(8\right)$如果节点u现在状态i中且已经停留了s个时间片，则预测节点u未来时刻k位于状态j的概率可由下列条件概率公式得到，$\begin{array}{c}{\hat{\phi }}_{\mathrm{ij}}^u(k,s)=\frac{\mathrm{Pr}(Z_{s+k}=j,t_{\mathrm{sojourn}}=s|Z_0=i)}{\mathrm{Pr}(t_{\mathrm{sojourn}}=s|Z_0=i)}\\ =\frac{d_{\mathrm{ij}}^u(s+k)+\underset{w=0}{\overset{M-1}{\Sigma }}\underset{\tau =s+1}{\overset{s+k}{\Sigma }}{v}_{\mathrm{iw}}^u\left(\tau \right){\phi }_{\mathrm{wj}}^u(s+k-\tau )}{1-D_i\left(s\right)}\end{array},---\left(9\right)$其中t_sojourn表示在状态i的逗留时间；(3)、定义节点移动轨迹热度；(a)、定义社区i(1≤i≤M‑1)的热度Chd_i，Chd_i为属于该社区的节点个数，节点访问热度高的社区可能更易传播数据，进而带来由于节点的移动轨迹不同导致数据传播能力的差别；(b)、假设节点u在各状态的稳态分布为则该节点移动轨迹热度Thd_u定义为：${\mathrm{Thd}}_u=\underset{i=1}{\overset{M-1}{\Sigma }}{\mathrm{Chd}}_i·{\pi }_i^u;---\left(10\right)$(4)、定义节点移动轨迹相似度；(a)、引用向量空间余弦相似度测量方法定义两节点在kΔt秒间隔后的位置相似度：对于M维向量和余弦相似度定于如下：$\mathrm{sim}(\overrightarrow{p},\overrightarrow{q})=\frac{\underset{i=1}{\overset{M}{\Sigma }}{p}_i{q}_i}{\left(\sqrt{{\Sigma }_{i=}^M{p}_i^2}\right)\left(\sqrt{{\Sigma }_{i=1}^M{q}_i^2}\right)}=\frac{\overrightarrow{p}·\overrightarrow{q}}{\left|\overrightarrow{p}\right|\left|\overrightarrow{q}\right|};$(b)、假设节点u和v当前时刻都在状态cur中，且在该状态中已经停留的时间分别为s₁、s₂，kΔt秒后可能的位置分布分别为${\hat{\phi }}_{\mathrm{cur}}^u(s_1,k)=\{{\hat{\phi }}_{\mathrm{cur},1}^u(s_1,k),{\hat{\phi }}_{\mathrm{cur},2}^u(s_1,k),...,{\hat{\phi }}_{\mathrm{cur},M-1}^u(s_1,k)\},$${\hat{\phi }}_{\mathrm{cur}}^v(s_1,k)=\{{\hat{\phi }}_{\mathrm{cur},1}^v(s_1,k),{\hat{\phi }}_{\mathrm{cur},2}^v(s_1,k),...,{\hat{\phi }}_{\mathrm{cur},M-1}^v(s_1,k)\},$此两节点kΔt秒后位置相似度Lsim(u,v,cur,s₁,s₂,k)如下：$\mathrm{Lsim}(u,v,\mathrm{cur},s_1,s_2,k)=\mathrm{sim}({\hat{\phi }}_{\mathrm{cur}}^u(s_1,k),{\hat{\phi }}_{\mathrm{cur}}^v(s_2,k));---\left(12\right)$(c)、假设每个数据包都有一个生存时间TTL(time‑to‑live)，设当前值为T_cur·Δt秒，将T_cur·Δt划分为δ个区间，每隔δ·Δt秒，计算一次节点u和v的位置相似度，因此得到的位置相似度值分别为：(d)、定义节点u和v移动轨迹相似度；假设节点u和v都在状态cur中，且在该社区中已经停留的时间分别为s₁、s₂，数据包生存时间当前值为T_cur·Δt时，此两节点移动轨迹相似度MTsim(u,v,cur,s₁,s₂,T_cur)由下面等式给出：(5)、根据节点移动轨迹热度以及节点移动轨迹相似度的特点，提出基于节点移动轨迹数据转发策略(Data Forwarding based on node moving trajectory，DFNMT)，在DFNMT策略中，与携带数据包的节点相遇节点满足移动轨迹热度高和与之携带数据包的节点的移动轨迹相似度低的条件，则携带数据包的节点将拷贝数据包给相遇节点。