DTN中基于节点邻居变化率预测的数据转发算法

苏 欣,王 琦,王青山

(合肥工业大学 数学学院,安徽 合肥 230601)

延迟容忍网络 (delay tolerant networks, DTNs)[1]是一种在特定的网络环境下,由于节点稀疏和快速移动等导致网络中往往不存在端到端的路径,有时还会伴随着高延迟、低传输速率等特征。例如星际网络[2]、传感器网络[3]、移动社交网络[4]和车载网络[5]等。因此,传统的路由算法不能应用到DTNs中,设计新的路由(转发)算法就变成一个关键问题。DTNs转发算法采用存储-携带-转发模式[6]。其中,如何度量节点的传播能力以及选择好下一跳节点,做出合理有效的数据转发策略变得很重要。文献[2]提出一种传染病(Epidemic)转发算法,其主要思想是携带包的节点遇到任何节点都进行数据转发,这样极大地提高数据包传递率,但同时也因为采用洪泛策略极大地消耗网络资源;文献[7-8]分析了节点与网络中其他节点之间的紧密度,发现紧密度高的节点传输能力比较强;文献[9]提出一种基于集成驱动的聚类不确定性估计和局部加权策略的新型聚类有效性度量方法;文献 [10]提出一种基于聚类度的算法(a novel algorithm based on clustering degree algorithm, CDA),主要思想是通过节点的聚类程度及其邻居的贡献来度量节点的传播能力;文献[11]提出一种直接传输(direct transmission, DT)方法,其主要思想是源节点只有与目标节点相遇时才转发消息,虽然开销很低,但传输成功率却较低。随着移动互联网的快速发展,转发算法可以有效地利用节点的社会属性来设计高效的数据转发算法。文献[12]提出标签传播 (label propagation, LP) 算法,它要求每一个节点都拥有唯一的标签,在同一个社区内的节点标签相同。数据包只拷贝给拥有相同标签的节点或者转发给目的节点。在一些转发算法[13-14]中,基于节点的兴趣来选择中继节点从而转发消息。文献[15]通过考虑节点对的联系时长来设计瞬时社区(transient communities,TCs),转发能力比较好的TCs作为中继社区进行数据转发。但是这些几乎没有考虑到节点转发能力随时间的变化情况。因此本文从节点邻居个数的动态变化角度来度量节点传播能力。网络拓扑结如图1所示,图1a、图1b分别表示6个节点在时间段[0,w]和[w, 2w]内的节点联系情况,其中w为窗口大小,源节点S要把数据包传送给目的节点D。如果采用Epidemic算法,根据图1a,在时间段[0,w]内,那么源节点将数据包拷贝给节点1和节点2,同时节点1将数据包拷贝给节点3。根据图1b,在时间段[w, 2w]内,节点2直接把数据包传送给目的节点D。因此产生3次拷贝。由图1可知,节点S和节点1的邻居变化个数都为0,节点2的邻居变化个数为1,在时间段[0,w]内,源节点S将数据包拷贝给邻居变化个数更大的节点2。在时间段[w,2w]内,节点2遇到目的节点D,则直接把数据包传送给目的节点D。因此产生1个数据包拷贝。与Epidemic算法相比,考虑节点邻居个数变化的方法减少了66.7%的拷贝数目。本文通过考虑节点的邻居动态变化,设计一种基于节点邻居变化率预测的数据转发算法(a node neighbor change ratio prediction-based data forwarding algorithm, NC-based)。

图1 网络拓扑结构

1 节点传输信息能力的评价

本节主要判断在相邻时间段内节点的邻居变化率,进而给出3种方法来预测节点在未来时间段内的邻居变化率。首先给出网络模型并划分时间窗口;其次从节点新增邻居和减少邻居2个方面计算节点在相邻时间窗口内的邻居变化率;最后给出3种方法预测未来时间段内节点邻居变化率。

1.1 网络模型

将延迟容忍网络模型化为一个无向图G=(V,E),其中:V为节点集合;E为节点之间联系边的集合。边集合可以用一个矩阵A={aij}来表示。假设网络存在的时间是有限的,从0到T,如图2所示。

图2 窗口划分

1.2 节点的邻居变化率

(1)

(2)

由(2)式可以看出,节点的邻居变化率反映节点在固定的时间窗口w内邻居变化的幅度。节点的邻居变化率越高,则该节点在一定时间内与其他节点相遇的概率越大,间接反映出节点的朋友就越多。

1.3 节点邻居变化率的预测

图3 邻居变化率预测示意图

(3)

(2) 最近平均预测法。为了提高预测的准确性,本文使用节点的前l个时间窗口的邻居变化率的均值作为预测节点i在时间窗口t+1邻居变化率,表示为:

(4)

值得注意的是,参数l(0

最近平均预测法的一个最主要缺点是没有考虑到不同的时间窗口的邻居变化率与当前预测的时间窗口内邻居变化率相关性大小的差异，因此，本文提出下一个预测法。

(3) 最近加权平均预测法。在最近平均预测法中,根据时间窗口距离预测时间窗口的大小,赋予每个窗口相应的权重,距离越小赋予的权重就越大。节点i在时间窗口t+1邻居变化率可以表示为:

(5)

下面验证3种预测方法的准确性。本文采用Infocom 06[16]作为节点移动轨迹数据集。该数据集有78位志愿者全都携带有蓝牙接口的iMote设备参加IEEE INFOCOM 2006会议。蓝牙设备iMote不仅可以定期记录相遇志愿者(节点)之间的联系时间以及联系时长,还可以记录它们之间的联系数目。本文在数据集Infocom 06上来评估3个预测方法随时间窗口w的变化情况,其中令参数l=4。为度量每个预测方法,本文使用平均误差:

(6)

3种预测方法的平均误差随着时间窗口w的变化情况如图4所示。从图4可以看出,随着时间窗口w的增加,3种预测方法对应的平均误差都相对较小,其中最近加权平均预测法所达到的误差最小。因此,本文将最近加权平均预测法作为预测节点未来时刻邻居变化率的方法。

图4 3种预测方法的平均误差

2 NC-based

NC-based主要思想是根据预测的节点邻居变化率来度量节点传播消息能力。在NC-based算法中,假设包携带者为节点i,目的节点为D。若在时间窗口t+1内节点i遇到节点v,当节点i把数据包转发给没有该数据包拷贝的节点v,当且仅当满足下列2种情况之一:

(1) 节点v是目的节点,那么节点i直接把数据包转发给节点v。

3 性能评价

本节使用数据集Infocom 06对提出的NC-based算法与Epidemic[2]、DT[11]和TC-based算法[15]进行性能比较。选择的性能评价标准主要包括:

(1) 传输成功率(delivery rate)。成功传递到目的节点的消息数与网络中生成的消息总数之间的比率。

(2) 开销(overhead)。在数据包的寿命时间TTL内网络中消息副本的总数量。

(3) 平均延迟(average delay)。消息从源节点到达目的节点所用的平均时间。

将数据包的TTL从2 h增加到14 h,比较NC-based算法与Epidemic、DT和TC-based算法的性能,其中l=4。实验结果如图5所示。

图5 4种算法在不同TTL下的性能

从图5a可以看出,本文提出的NC-based算法传输成功率比DT、TC-based分别高出20%和35%,非常接近Epidemic。Epidemic算法采用洪泛策略而具有最高的传输成功率。另外,DT算法具有最低的传输成功率,因为其转发策略算法是源节点仅在遇到目的节点时才转发消息。

图5b比较了NC-based与Epidemic、DT和TC-based算法的开销。在数据包的TTL范围内,NC-based算法的开销比Epidemic、DT算法的开销分别降低38%和30%。这是因为算法只将数据包拷贝给邻居变化率预测比较大的节点,明显地减少了拷贝数目。

从图5c可以看出,NC-based算法的平均延DT平均低大约11%,比TC-based平均低大约8%。

然后研究时间窗口大小w对NC-based算法性能的影响。设置TTL=8 h,w的值从0.39 h增加0.72,w对NC-based算法性能的影响结果如图6所示。

图6 w值对NC-based算法性能的影响

根据图6,可以将时间窗口大小分成2类。第1类是w为0.39 、0.61 h;第2类是w为0.44、0.50、0.56、0.67、0.72 h。对于第1类时间窗口大小对NC-based算法性能的影响,从图6a可以看出虽然成功传输率比较高,但是平均时延比较大,同时也很大地消耗了网络资源;对于第2类时间窗口大小来说,它们对成功传输率和平均延迟的影响不大,但是从图6b中可以看出,当w=0.56 h时,NC-based算法的拷贝数目最少,相对于其他窗口产生的拷贝数最多减少32%。而对于数据集Infocom 06来说,所有节点联系的平均时间大约为0.56 h。因此,当时间窗口大小w为数据集Infocom 06中所有节点联系的平均时间时,NC-based算法的成功传递率、拷贝数目以及平均时延都相对达到一个比较好的结果。

4 结 论

本文根据节点在相邻时间窗口内新增的和减少的邻居数目,定义其邻居变化率,并提出最近预测法、最近平均预测法和最近加权平均预测法3种方法来预测节点在未来时间段内邻居变化率。基于节点邻居变化率的预测,提出数据转发算法NC-based。仿真结果表明,本文提出的NC-based算法在明显降低网络资源消耗的情况下,保证了传输成功率和较小的延迟。最后得到时间窗口大小的最优取值。今后应将邻居变化率思想应用到社区划分算法中。