延迟容忍网络中带时延约束的数据融合方法

技术领域

本发明涉及的是延迟容忍网络，具体涉及的是一种延迟容忍网络中带时延约束的数据融 合方法，属于网络技术领域。

背景技术

延迟容忍网络(Delay Tolerant Networks，DTNs)是指一类特殊的网络，在该类网络中， 很难建立一条端到端持久连接的路径，网络中的消息通常都是以“carry-and-forward”的方式传 输，因而传播的延时比较大。目前延时容忍网络的应用场合比较多，例如：灾难恢复、车辆 间通信、野生生物跟踪等。

在延迟容忍网络中，由于节点的移动或者网络本身的稀疏行，导致节点间的相遇机会非 常有限，因此如何有效利用这些稀缺资源使得数据成功转发率增大变得十分重要。通过分析 MIT Reality数据集可得知，两个节点一天中的平均相遇次数为0.024次。而数据融合技术在 减少通信开销方面有着很好的表现，其实现形式有很多种，我们较为熟悉的有：max、min、 count、average等。使用数据融合方法可以去除原始数据中存在的冗余信息，从而整个网络的 通信消息也随之大大减少。

由于延迟容忍网络本身特性的局限，采用带时延约束的数据融合方法面临着许多困难， 如：1，网络延时大，节点间的相遇通常是不可以预测的。2，连接不稳定，由于节点的移动 性、休眠调度或自身能量考虑，节点之间的连接通常是间断性的。3，没有稳定的端到端的连 接路径。4，节点如何确定应该等多久才将收集到的数据转发出去，并且转发给谁。5，如何 保证融合过程中具有重复敏感性，即同一份数据不能多次出现在融合数据包里。

在静态传感器网络中，有许多有关数据融合的方法提出来，但是他们都是在网络拓扑结 构不变并且连通性很好的前提下。虽然最近在车辆网络中，也有一些有关数据融合的方法被 提出来，但是他们不考虑数据重复敏感性，也未考虑在有限的时延约束下的数据融合问题。

发明内容

本发明的目的在于克服现有技术存在的不足，提供一种延迟容忍网络中带时延约束的数 据融合方法，其针对延迟容忍网络通信资源极其有限的特性，从网络的数据传输性能出发， 结合网络节点相遇特征，实现具有高重复敏感性、不影响数据转发成功率、大大减少通宵开 销的数据融合。

本发明是通过以下技术方案来解决其技术问题的：

一种延迟容忍网络中带时延约束的数据融合方法，其特征在于，包括以下步骤：

第一步、网络部署，在延迟容忍网络的检测区域内，部署若干能够进行无线通信的可移 动的节点，其中有一个节点为用来收集其他节点所产生数据的根节点，其他节点产生的数据 都必须传输到该根节点；

第二步、网络初始化，在节点移动一段时候后，分析每两个节点间相遇的历史数据，得 到每两节点之间的相遇时间间隔的分布。

第三步、数据融合树的构造，将网络建模称一个图，图中节点之间的边为节点之间的相 遇，边的权值为节点相遇的平均时间间隔w=1/λ，其中λ为由所述第二步得到的节点间的相 遇率，使用Dijsktra算法计算每个节点到根节点的最短路径，即得到数据融合树；

第四步、确定所述数据融合树上每个节点等待接收其孩子节点数据的最佳等待时间，使 所述根节点最终收集到的信息量最大，该根节点的等待时间为系统给定的最大时延，其他节 点的等待时间必须小于根节点的等待时间；

第五步、数据的转发，一个节点如果遇到其他节点，首先查看遇到的节点是否是本节点 的父亲节点，如果是，接着检查自己的最长等待时间，若当前时间大于本节点的等待时间， 则该节点将自己本地的数据和收集到的数据做融合，转发给父亲节点；否则，继续等待其他 孩子节点的数据；每个节点重复上述过程，直到将数据转发给根节点。

第四步中所述的确定数据融合树上每个节点等待接收其孩子节点数据的最佳等待时间是 指：在有限时延约束下，给定数据融合树，目标是使得根节点收集到的信息量最大的问题存 在最优子结构，且为

$m[i,{\tau }_i]=\left(\begin{array}{cc}\underset{j\in C\left(i\right)}{\Sigma }\underset{0<{\tau }_j<{\tau }_i}{\max }\left\{m\right[j,{\tau }_j]·p_{\mathrm{ji}}\}+1,& C\left(i\right)\ne 0,\\ 1,& C\left(i\right)=0,\end{array}\right)$

其中，m[i，τ_i]表示当节点i的等待时间为τ_i时，节点i能收集到的最大信息量，这里假设每个 节点产生的信息量都是相等的，而且为1，

C(i)表示节点i的孩子节点集合，

当节点i为叶子节点，则其信息量只包含它自己的而且为1，

当i为中间节点，则其收集到的最大信息量是所有孩子节点最大信息量的期望总和，

0＜τ_i＜τ_i保证孩子节点的等待时间小于父亲节点的等待时间；

继而，确定节点j在时间窗口[τ_j，τ_i]内，将数据成功转发给i的概率p_ji：

$p_{\mathrm{ij}}=F(w_{\mathrm{ij}},{\lambda }_{\mathrm{ij}})=1-e^{-{\lambda }_{\mathrm{ij}}{w}_{\mathrm{ij}}},,$

其中，w=τ_i-τ_j为时间窗口的长度。

本发明的优点在于：

(1)本发明所述的数据融合方法，可以在延迟容忍网通信资源很紧张的情况下，在保 证网络通信质量的同时，降低网络通信开销。

(2)本发明具有很好的重复敏感性，能够保证所有的数据最多只被融合一次。

附图说明

图1是本发明的网络模型。

图2是本发明的方法流程图。

具体实施方式

下面对本发明的实施做详细说明，本实施例以发明技术方案为前提，给出了详细的实施 方法和具体操作过程，但本发明的保护范围不限于下述的实施例。

本发明针对延迟容忍网络通信资源极其有限，从网络的数据传输性能出发，结合网络节 点相遇特征，实现了一种不影响数据转发成功率、大大减少通信开销的数据融合方法。设定 网络中每两个节点之间的相遇时间间隔为指数分布，这在其他文献中已被证实过。所述延迟 容忍网络中带时延约束的数据融合方法的详细步骤如下：

第一步、网络部署：在延迟容忍网络的检测区域内，部署若干可移动的、能进行无线通 信的节点(比如传感器节点)，其中有一个节点用来收集其他节点产生的数据，称为根节点(收 集节点)，也就是说其他节点产生的数据都必须传输到该根节点。

第二步、网络初始化：在节点移动一段时候后，分析每两个节点间相遇的历史数据，得 到每两节点之间的相遇时间间隔的分布。

第三步、数据融合树的构造：数据融合树也就是节点路由的拓扑结构，收集节点为根节 点；将网络建模称一个图，图中节点之间的边为节点之间的相遇，边的权值为节点相遇的平 均时间间隔w=1/λ，其中λ为节点间的相遇率，通过第二步步骤可以得到；接下来，使用 Dijsktra算法计算每个节点到根节点的最短路径，这样就得到了一棵最短路径树，即所述的数 据融合树。

第四步、确定数据融合树上每个节点等待接收其孩子节点数据的最佳等待时间，使最终 根节点收集到的信息量最大；根节点的等待时间为系统给定的最大时延，其他节点的等待时 间必须小于根节点；下面给出如何估算每个节点的最佳等待时间的过程：经分析得，在有限 时延约束下，使得根节点收集到的信息量最大的问题存在最优子结构，且为

$m[i,{\tau }_i]=\left(\begin{array}{cc}\underset{j\in C\left(i\right)}{\Sigma }\underset{0<{\tau }_j<{\tau }_i}{\max }\left\{m\right[j,{\tau }_j]·p_{\mathrm{ji}}\}+1,& C\left(i\right)\ne 0,\\ 1,& C\left(i\right)=0,\end{array}\right)$

其中，m[i，τ_i]表示当节点i的等待时间为τ_i时，节点i能收集到的最大信息量，这里假设每个 节点产生的信息量都是相等的，而且为1，

C(i)表示节点i的孩子节点集合，

当节点i为叶子节点，则其信息量只包含它自己的而且为1，

当i为中间节点，则其收集到的最大信息量是所有孩子节点最大信息量的期望总和，

0＜τ_i＜τ_i保证孩子节点的等待时间小于父亲节点的等待时间。

接下来是如何求节点j在时间窗口[τ_j，τ_i]内，将数据成功转发给i的概率p_ji。如果节点j 和它的父亲节点i的等待时间分别为τ_j，τ_i，这样节点j的允许的发送消息的时间窗口为 [τ_j，τ_i]，因为节点j只有在时间超过自己的等待时间才可以给将自己的数据转发出去，并且节 点i等待自己孩子的最长时间也不超过τ_i。因为节点的相遇时间间隔为指数分布，故节点j 在时间窗口[τ_j，τ_i]内将数据成功转发给i的概率p_ji为w=τ_i-τ_j为时间窗口的长度。

第五步、数据的转发过程：一个节点如果遇到其他节点，首先查看遇到的节点是否是自 己的父亲节点，如果是，接着检查自己的最长等待时间，如果当前时间大于自己的等待时间， 那么节点将自己本地的数据和收集到的数据做融合，转发给父亲节点；否则，继续等待其他 孩子节点的数据。每个节点重复上述过程，直到将数据转发给根节点。