容迟移动传感网中基于节点活跃度的改进概率路由方法

摘要

本发明是一种容迟移动传感网中基于节点活跃度的改进概率路由方法，该方法将节点活跃度因子加入到传输概率的预测之中，提出节点本身的活跃度NA的计算公式，通过权值α对NA和原始的PROPHET算法传输预测概率值进行加权，依据节点相遇历史信息，以及节点在网络中活跃程度，计算新的传输预测概率值，节点之间通过比较传输预测概率值的大小决定消息的转发与否，利用生存时间TTL丢弃策略对缓存进行管理，仿真结果表明，NAPR算法的概率估计方法较PROPHET算法更为全面，产生的副本数较少，虽然导致消息的平均时延有所增加，但是NAPR算法降低了节点开销率，提高了报文的递交率。在未来工作中将进一步研究如何应对网络中的拥塞问题。

说明书

技术领域

本发明是一种在容迟移动传感网（Delay Tolerant Mobile Sensor Networks,DTMSN）中基于节点活跃度的改进型概率路由方法，属于延迟容忍传感器网络的概率路由算法领域。

背景技术

DTMSN属于延迟容忍网络(Delay Tolerant Networks,DTN)的范畴,DTN用于间歇连通的网络传送数据。DTN技术近几年被引入无线传感器网络,并且根据节点移动性的不同,可以把延迟容忍传感器网络（Delay Tolerant Sensor Networks,DTSN）分为传感器节点静止的网络和节点运动的传感器网络。节点运动的传感器网络即容迟移动传感网络(Delay Tolerant MobileSensor Networks,DTMSN)。DTMSN具有高延迟、低数据率、无稳定的端到端连接、节点资源有限等特点，用于广泛的数据收集,其通常由两种节点组成:汇聚点和便携的移动传感器节点。其中，传感器节点绑定在可移动的物体（如人、动物、车辆等）上,用于收集指定的信息,并形成稀疏的间断连通的无线网络,汇聚点位置固定或可移动,用来接收传感器发来的数据,并能将数据转发到骨干网络的接入点。

在DTMSN中,随机移动模型经常被拿来研究，主要有：随机路点移动模型（RandomWay-Point model,RWP）和随机方向模型（Random Direction，RD）两种。然而，在现实中，很多的传感器节点的移动模式都不是完全随机的，而往往是基于一种重复的模式在移动，是一种可以预见的移动方式，比如当某一个节点之前经常出现在某个区域内时，那么它再次出现在此区域内的概率就会很大。通过这种现象，就可以得到概率路由，它是一种先验式的路由，还是一种基于节点联系和传递历史的路由：根据节点间历史相遇信息以及传递记录，来提前预测节点可能的移动方式。概率路由中，每个节点各自维护一个概率表，这个概率表显示网络中任何两个节点相遇的概率，也就是两个节点之间传递报文的概率，这个表是动态变化的，随着时间的推移，能够动态地显示节点间传递报文概率大小的变化。

LindgrenA等人提出的PROPHET（Probabilistic Routing Protocol using History ofEncounters and Transitivity）算法是一种典型的概率路由算法。利用节点相遇或投递转移历史信息，估算每个节点成功投递数据到目的节点的概率，即传输预测值（到达概率DeliveryPredictability，DP）。两个节点相遇时，除了互相交换报文列表外，还会交换节点传输报文的到达概率表。节点之间通过比较到达概率控制消息的转发。PROPHET算法在一定程度上限制了消息副本数量，从而得到了近似于Epidemic算法的延迟，并大幅降低了资源消耗。然而，PROPHET算法仅通过到达目的节点的传输概率的高低来决定报文的转发，具有一定的盲目性，概率的估计欠缺合理性，没有考虑各节点本身的活跃度以及转发时机问题。关于PROPHET算法也有一些改进措施，但是这些改进算法并没有考虑到节点本身的活跃性对于传输预测值的影响，得到的概率的估计值欠缺合理性。

发明内容

技术问题：本发明针对上述问题，提出在计算传输预测值的过程中，利用节点活跃度因子和原始传输概率的预测因子的加权平均值作为新的传输预测值。基于此，提出了一种基于节点活跃度的改进型概率路由算法NAPR（Node Activity-based Probabilistic RoutingAlgorithm）,将节点活跃度因子加入到传输概率的预测之中。

技术方案：本发明的一种容迟移动传感网中基于节点活跃度的改进概率路由方法是，将节点活跃度因子加入到传输概率的预测之中，提出节点本身的活跃度NA的计算公式，通过权值α对NA和原始的PROPHET算法传输预测概率值进行加权，依据节点相遇历史信息，以及节点在网络中活跃程度，计算新的传输预测概率值，节点之间通过比较传输预测概率值的大小决定消息的转发与否，利用生存时间TTL丢弃策略对缓存进行管理，其步骤如下：

1）初始化：节点初始化自己的传输概率信息表，将所有节点的传输概率初始化为初始传输概率常量P_init，P_init在[0,1]之间取值，

2）计算各节点的节点活跃度：依据节点接触过的节点数以及和上一个节点接触时间，计算各节点本身的活跃度，

3）结合节点活跃度和相遇记录，更新各节点传输预测概率值，

4）利用生存时间TTL丢弃策略进行队列管理，当TTL小于等于0时，将消息从队列中丢弃；当TTL大于0时，依据传输概率进行消息转发。

所述的将节点活跃度因子加入到传输概率的预测之中，提出节点本身的活跃度NA的计算公式，节点本身的活跃度NA的计算公式定义如下：

NA_i表示节点i的活跃度，NA_i的大小与该节点所接触过的其他节点的数量成正比，而和该节点与上一个节点接触时间的长短成反比，即：

$>{\mathrm{NA}}_i=\underset{i=1}{\overset{n_i}{\Sigma }}{e}^{-{\mathrm{\lambda t}}_i}---\left(1\right)$>

其中，n_i表示节点i所接触过的其他节点的数量，t_i表示节点i与上一个节点的接触时间，λ为常数，为了实现归一化，λ设为10，即0≤NA_i≤1；对于不同的节点，NA越大，表示这个节点在网络中越活跃，该节点所携带的消息传递到汇聚点的概率越大。

通过权值α对NA和原始的PROPHET算法传输预测概率值进行加权，具体描述如下：

传输预测概率值P(a,b)：消息从节点A传输到节点B的传输概率参数，常把P(a,b)作为概率路由度量标准；节点之间的每次相遇都增加他们之间的概率值，相遇次数多的节点之间的概率值就高，这个概率值叫做传递概率，传输预测P(a,b)的取值有以下两种情况：

情形1：当节点A和节点B相遇时：

P(a,b)＝α×[P(a,b)_old+(1-P(a,b)_old)×P_init]+(1-α)×(NA_b-NA_a)      （2）

其中，α为权值，调整权值α可以改变节点活跃度因子对于传输概率预测值的影响，P(a,b)_old是从节点相遇历史记录中获取的节点A、B的上一次的传输预测，P_init∈(0,1]为初始常量，所有的P(a,b)初始化都设置为P_init；

情形2，当节点A和节点B不相遇时：

P(a,b)＝α×P(a,b)_old×γ^k      （3）

其中，γ∈[0,1]表示衰减因子，k表示节点A和节点B上一次接触以后所经过的时间，节点的传输可预测性以向量形式存储，且可在节点间进行交换，随着时间的流逝，两个节点的相遇概率数值会逐步的减少，这个过程又可以叫做衰减过程。

利用生存时间TTL丢弃策略对缓存进行管理，具体描述如下：

基于报文的生存时间TTL丢弃策略考虑报文剩余的生存时间，每个报文在产生的时候，都有一个初始值的TTL，节点缓存中的报文按照其剩余生存时间排序,生存时间短的消息排在前面并得到优先发送权,在这个报文每次被转发时，TTL值不断减小，直到TTL等于或小于0时，该报文会被自动丢弃，避免无限制得占用网络资源。

节点之间的每次相遇都增加他们之间的概率值,相遇次数多的节点之间的概率值就高，也就是传递概率，具体描述如下：

若节点A常与节点B连接，而节点B又常与节点C连接，这就意味着可以认为节点C与节点A能够以高成功率转发消息，概率传递性可表示为：

P(a,c)＝α×[P(a,c)_old+(1-P(a,c)_old)×P(a,b)×P(b,c)×β]+(1-α)×[(NA_b-NA_a)+(NA_c-NA_b)]化简后得到：

P(a,c)＝α×[P(a,c)_old+(1-P(a,c)_old)×P(a,b)×P(b,c)×β]+(1-α)×(NA_c-NA_a)      （4）

其中，β∈[0,1]为常量，是传递影响因子，P(a,b)为节点A和节点B之间的传输预测概率值，类似地，P(b,c)为节点B和节点C之间的传输预测概率值，P(a,c)节点A和节点C之间的传输预测概率值。

有益效果：本发明对DTMSN中基于节点相遇或投递转移历史信息的概率路由PROPHET算法进行了研究，并提出了一种基于节点活跃度的改进型概率路由方法,即NAPR算法。将节点活跃度因子加入到传输概率的预测之中，完善了节点的传输概率的估计。仿真结果表明，NAPR算法的概率估计方法较PROPHET算法更为全面，产生的副本数较少，虽然导致消息的平均时延有所增加，但是NAPR算法降低了节点开销率，提高了报文的递交率。在未来工作中将进一步研究如何应对网络中的拥塞问题。

附图说明

图1NAPR算法流程图，

图2不同权值时传递率随节点数量变化，

图3不同权值时消息的平均延迟随节点数量变化，

图4不同权值时传递率随仿真时间变化，

图5不同权值时消息的平均延迟随仿真时间变化，

图6成功递交的消息数随缓存空间变化，

图7消息的平均延迟随缓存空间变化，

图8传递率随节点数量变化，

图9平均副本数随节点数量变化，

图10消息平均延迟随节点数量变化，

图11传递率随仿真时间变化，

图12消息平均延迟随仿真时间变化，

图13开销率随仿真时间变化。

具体实施方式

基本思想：本发明针对DTMSN中的路由算法PROPHET转发报文传输概率估计的盲目性问题，定义了节点本身活跃度NA（node active）的计算公式，引入权值α对NA和原始的PROPHET算法预测传输概率进行加权，得到的加权平均值作为传输预测DP（DeliveryPredictability）。依据节点相遇或投递转移历史信息，以及节点在网络中活跃程度，计算每个节点成功投递数据到目的节点的新的传输预测概率值。当节点相遇时，将依据新的传输预测值判断是否进行数据转发。当节点不相遇时，依据PROPHET算法中的衰减过程衰减。最后和PROPHET算法一样利用TTL丢弃策略对缓存进行管理，依据传输概率进行消息转发。

变量定义：

定义1：活跃度（NA）：NA_i表示节点i的活跃度。NA_i的大小与该节点所接触过的其他节点的数量成正比，而和该节点与上一个节点接触时间的长短成反比，即：

$>{\mathrm{NA}}_i=\underset{i=1}{\overset{n_i}{\Sigma }}{e}^{-{\mathrm{\lambda t}}_i}---\left(1\right)$>

其中，n_i表示节点i所接触过的其他节点的数量，t_i表示节点i与上一个节点的接触时间。λ为常数（为了实现归一化，设为10，即0≤NA_i≤1）。对于不同的节点，NA越大，表示这个节点在网络中越活跃，该节点所携带的消息传递到汇聚点的概率越大。

定义2：传输预测概率值P(a,b)：消息从节点A传输到节点B的传输概率参数，常把P(a,b)作为概率路由度量标准。节点之间的每次相遇都增加他们之间的概率值,相遇次数多的节点之间的概率值就高。传输预测P(a,b)的取值有以下两种情况：

情形1：当节点A和节点B相遇时：

P(a,b)＝α×[P(a,b)_old+(1-P(a,b)_old)×P_init]+(1-α)×(NA_b-NA_a)      （2）

其中，α为权值。调整权值α可以改变节点活跃度因子对于传输概率预测值的影响。P(a,b)_old是从节点相遇历史记录中获取的节点A、B的上一次的传输预测，P_init∈(0,1]为初始传输概率常量，所有的P(a,b)初始化都设置为P_init。

情形2，当节点A和节点B不相遇时：

P(a,b)＝α×P(a,b)_old×γ^k      （3）

其中，γ∈[0,1]表示衰减因子，k表示节点A和节点B上一次接触以后所经过的时间。节点的传输可预测性以向量形式存储，且可在节点间进行交换。随着时间的流逝,两个节点的相遇概率数值会逐步的减少,这个过程又可以叫做衰减过程。

定义3：概率传递：若节点A常与节点B连接，而节点B又常与节点C连接，这就意味着可以认为节点C与节点A能够以高成功率转发消息，概率传递性可表示为：

P(a,c)＝α×[P(a,c)_old+(1-P(a,c)_old)×P(a,b)×P(b,c)×β]+(1-α)×[(NA_b-NA_a)+(NA_c-NA_b)]化简后得到：

P(a,c)＝α×[P(a,c)_old+(1-P(a,c)_old)×P(a,b)×P(b,c)×β]+(1-α)×(NA_c-NA_a)      （4）

其中，β∈[0,1]为常量，是传递影响因子。

根据算法思想可以得到算法步骤如下所示。

1)初始化。节点初始化自己的传输概率信息表，将所有节点的传输概率初始化为P_init，P_init在[0,1]之间取值。

2)计算各节点的节点活跃度。依据节点接触过的节点数以及和上一个节点接触时间，按照公式（1）计算得到各节点本身的活跃度。

3)结合节点活跃度和相遇记录，按照公式（2）、（3）更新各节点传输预测概率值。

4)利用TTL进行队列管理。当TTL小于等于0时，将消息从队列中丢弃；当TTL大于0时，依据传输概率进行消息转发。

工作原理：

此算法所描述的工作原理是指将节点活跃度因子加入到传输概率的预测之中，具体是指依据节点相遇历史信息，以及节点在网络中活跃程度，计算新的传输预测概率值，节点之间通过比较传输预测概率值的大小决定消息的转发与否，利用TTL丢弃策略对缓存进行管理。

在ONE（Opportunistic Networking Environment）仿真平台上对NAPR算法进行仿真分析，并与Epidemic算法和PROPHET算法进行对比实验。

仿真环境配置如表1所示：仿真场景采用赫尔辛基市城市地图作为移动区域，大小为4500m*3400m，节点数量分别为3*10，3*20，3*30，3*40，3*50，3*60，3*70，3*80，3*90，3*100个，分为行走、开车和骑车三种节点，每种100个，节点的无线通信范围（传输半径）为10m，带宽为250kbps，缓存大小分别为2M，4M，…，30M，移动模型采用ONE默认的赫尔辛基城市地图模型，节点的移动速度分别为1.34m/s、8.94m/s、4.0m/s，分别表示行走、开车和骑车三种不同活动的平均速度。数据包大小为50KB，生成时间间隔为50s。仿真运行时间为2，4，…,30ks。

表3ONE仿真环境

NAPR算法仿真过程中，采用如下4个性能指标：

1）传递率：成功传递的消息数与消息总数之比。

Delivery probability=delivered messages/created messages

2）开销率：被转发但没有成功传递的消息数量与成功传递的消息数量之比。

Overhead ratio=(relayed messages-delivered messages)/delivered messages

3）平均副本数：消息产生的副本总数与消息总数之比。消息i产生的副本数记为c_i，消息总数记为n。

>

4）平均延迟：递交成功的所有数据包从源端到目的端的时间之和与总的数据包个数之比。消息i接收时间记为t_ir，消息i发送时间记为t_is，消息总数记为n。

>

仿真过程中进行四组实验，分别测试在不同的权值α、缓存大小、节点数量和仿真运行时间的情况下，三种算法的路由性能的变化情况。仿真实验中，首先经过实验确定α的取值，然后利用本文提出的NAPR算法与Epidemic算法、PROPHET算法进行对比实验，得到最终的实验结果。

（1）在第一组实验中，通过调整权值α，改变节点活跃度因子在传输预测中所占比重，观察权值α的改变对NAPR算法的性能指标产生的影响。当α取值为0.1,0.3,0.5,0.7,0.9时，NAPR算法的性能指标的变化结果如图2-5所示。

（a）消息生成时间间隔设置为50s，节点缓存空间为设置为2M，仿真时间设置为30ks，节点数量从30逐渐增加为300个，表示网络中节点密集程度逐渐增加，测试NAPR算法在α=0.1、α=0.3、α=0.5、α=0.7、α=0.9时的性能变化情况。结果如图2、3所示。

由图2可以看出，随着节点数量逐渐增加，能够成功到达汇聚点的消息逐渐减少，NAPR算法的传递率逐渐降低。当节点数量固定时，随着α值的增加，相遇历史记录在NAPR算法中的影响逐渐增加，能够成功到达汇聚点的消息逐渐减少，因而算法的传递率逐渐降低。

由图3可以看出，随着节点数量逐渐增加，网络中的节点密度逐渐增加，NAPR算法的平均延迟也逐渐增加。当节点数量固定时，随着α值增大，相遇历史记录在NAPR算法中的影响逐渐增加，消息到达汇聚点的速度加快，NAPR算法的平均延迟逐渐减小。

（b）消息生成时间间隔设置为50s，节点缓存空间为设置为2M，仿真时间设置为30ks，节点数量设置为150个，仿真时间从2ks逐渐增加到30ks，测试NAPR算法在α=0.1、α=0.3、α=0.5、α=0.7、α=0.9时的性能变化情况。结果如图4、5所示。

从图4可以看出，随着仿真时间的逐渐增加，能够到达汇聚点的消息数量逐渐增加，所以，NAPR算法的递交率在逐渐增加。当仿真时间固定为某一个确定值时，随着α值增大，相遇历史记录在NAPR算法中的影响逐渐增加，能够成功到达汇聚点的消息逐渐减少，因而算法的传递率逐渐降低。

从图5可以看出，随着仿真时间的逐渐增加，能够到达汇聚点的消息所花的时间逐渐增加，所以，NAPR算法的消息平均延迟在逐渐增加。当仿真时间固定为某一个确定值时，随着α值增大，相遇历史记录在NAPR算法中的影响逐渐增加，消息到达汇聚点的速度加快，NAPR算法的平均延迟逐渐减小。

由第一组实验，我们可以发现：随着α值增大，相遇历史记录在NAPR算法中的影响逐渐增加，能够成功到达汇聚点的消息逐渐减少，因而算法的传递率逐渐降低；但是，消息到达汇聚点的速度加快，NAPR算法的平均延迟逐渐减小。权衡利弊，综合考虑到传递率和平均延迟两个因素，权值α取值为0.5。

（2）在第二组实验中，消息生成时间间隔设置为50s，节点数量设置为3*50=150个，仿真时间设置为30ks，α取值为0.5。观察当节点缓存空间从2M增加到30M时，成功递交的消息数和消息平均延迟的变化情况。仿真结果如图6、7所示。

图6为当节点缓存空间从30M减小到2M时，NAPR、Epidemic和PROPHET三种算法的成功递交的消息数的变化情况。Epidemic算法成功递交的信息最少，这是因为洪泛机制会产生大量冗余副本占用缓存空间。NAPR算法和PROPHET算法都减少了副本数量，因此成功递交的信息数多于Epidemic算法。随着缓存空间不断减小，会产生拥塞情况，节点需要通过丢包释放缓存空间，因此三种算法的传递率都逐渐下降。Epidemic和PROPHET算法采用随机丢包策略，因此可能发生把最有可能被成功传递的消息丢弃的情况。而NAPR算法采用基于TTL的丢包策略，丢弃传递概率最低的消息，因此在缓存很小的情况下可以保持较高的传递率。

图7为节点缓存空间从2M增加到30M时，NAPR、Epidemic和PROPHET三种算法的消息平均时延的变化情况。随着缓存空间逐渐增大，消息在缓存中有更长的存储时间等待被转发，因此三种算法的时延逐渐增加。Epidemic算法的时延最小，因为消息副本数量最多，消息成功传递到汇聚点的速度最快。PROPHET算法副本数量有所减少，因此时延也有所增加。本文提出的NAPR算法将节点活跃度因子加入到传输概率的预测之中，完善了节点的传输概率的估计，因而转发的消息副本数量最少，因此消息平均时延大于PROPHET算法。

（3）在第三组实验中，消息生成时间间隔设置为50s，节点缓存空间为设置为2M，仿真时间设置为30ks，α取值为0.5，节点数量从30逐渐增加为300个，表示网络中节点密集程度逐渐增加，测试三种路由算法的性能变化情况。仿真结果如图8-10所示。

图8所示为三种算法的传递率随节点数量的变化情况。当节点数量从30逐渐增加为300个，网络中的节点密度不断增加，在节点的缓存空间仅为2M的情况下，随着拥塞情况的发生，传递率将不断降低。Epidemic算法中存在大量冗余副本占用缓存空间，因此传递率最低。PROPHET算法的情况与Epidemic算法类似，传递率也不高。NAPR算法中转发的消息副本数量最少，可以避免产生过多的冗余副本，并且没有采用随机丢包策略，因此传递率明显高于另外两种算法。

图9为当节点数量从30逐渐增加为300个，网络中的节点密度不断增加时，三种算法的平均副本数的变化情况。Epidemic算法是flooding算法的一种演化，产生的平均副本数最多；PROPHET算法近似于Epidemic，也是多副本复制传输，产生的平均副本数仅次于Epidemic算法；而NAPR算法完善了PROPHET算法的传输概率估计，减少了副本的数量，节省了成本开销。

如图9、10所示，当节点数量从30逐渐增加为300个，网络中的节点密度不断增加，三种算法的时延略有增加。Epidemic的时延最短因为消息副本数最多，传递速度最快，PROPHET算法与Epidemic类似，副本数较NAPR算法的多，时延较小，而NAPR算法产生的副本数最少，故而NAPR算法的平均时延最长。

（4）在第四组实验中，消息生成时间间隔设置为50s，节点数量设置为3*50=150个，节点缓存空间为设置为2M，α取值为0.5，仿真时间从2ks增加到30ks，测试三种路由算法的性能变化情况。仿真结果如图11-13所示。

从图11可以看出，随着仿真时间的增加，消息经过复制转发，成功传递到汇聚点的数量逐渐增加，三种算法的传递率都有所增加。NAPR算法的增幅较大，Epidemic算法次之，PROPHET算法增幅最小。NAPR算法考虑了节点本身活跃度的因素，传输概率估计更加全面，成功传递到汇聚点的消息数量更多，故而NAPR算法的传递率最高。

如图12所示，当仿真时间从2ks增加到30ks，Epidemic、PROPHET和NAPR三种算法中，Epidemic消息副本数最多，传递到汇聚点的速度最快，所需的时延最短，PROPHET算法时延次之；随着仿真时间的增加，NAPR算法的概率估计方法较PROPHET算法更为全面，NAPR算法产生的副本数少于PROPHET算法，故而传递到汇聚点所需的平均时延大于PROPHET算法。

由图13可以看出，随着仿真时间的增加，消息经过复制转发，所需的副本数逐渐增加，三种算法的开销率不断增加。Epidemic消息产生许多毫无用处的副本，带来传输成本的增加。PROPHET算法与Epidemic类似，副本数较NAPR算法的多，所以，PROPHET算法所需的开销仅次于Epidemic算法。而NAPR算法产生的副本数最少，所以，NAPR算法所需的开销最低。