基于节点间亲密度的DTN 路由策略

冯涛，刘广钟

(上海海事大学 信息工程学院，上海 201306)

0 引言

延迟容忍网络(Delay-Tolerant Network，DTN)是从空间网络互联抽象出来的一种网络体系结构，源于FALL［1］在2003 年发表的一篇论文，但至今定义仍然模糊.一般认为，DTN是一种新型的“存储—携带—转发”网络体系结构和协议族，用来实现恶劣或受干扰环境下的无线数据传输.

可以将DTN 看作是一种特殊的ad hoc 网络，主要针对端到端连接和节点资源都有限的网络解决方案，用于满足随意的异步消息的可靠传递.［1-2］由于网络中的节点数目比较少，节点之间联系不是很频繁，会经常出现网络断开的现象，导致报文在传输过程中不能确保端到端的路径.DTN 的研究和发展为军事战争、航天通信、灾难恢复等领域的消息交互提供有力的科学理论和技术支持.

1 相关工作

DTN 现有的研究虽有一定成果，但仍处于初步阶段.也可能是适用性的限制，大家都热衷于研究一些比较热门的网络模型和通信机制，如对等网络资源搜索算法［3］和移动Agent 组通信机制［4］.但是，DTN 的研究无论是在理论还是面向实际应用方面都有很大的研究空间.

在DTN 的研究过程中，网络的路由协议被人关注最多.几种比较典型的DTN 路由算法:VAHDAT等［5］提出的蔓延路由协议(epidemic routeing)、基于概率的路由协议(probabilistic routeing)［6］和PAN等［7］提出的基于社会网络的Bubble 路由算法.

蔓延路由协议的思想是把所要发送的报文给它所有的邻居节点.这种路由方式意味着:只要节点的缓存足够大，随着节点之间的不断“接触”，数据就会从源端开始像病毒那样传播到网络中的其他节点，从而大大增加网路负担，造成网络拥塞.所以，现实情况下，由于缓存空间、能量、带宽等资源的限制，传染路由性能会严重降级，很难适应现实环境.

PROPHET(Probabilistic Routeing Protocol using History of Encounters and Transitivity)［6］是一种基于概率估计的路由，与传染路由盲目地向所有邻居节点转发消息不同，概率路由中的每个节点将会估计到达目的节点的概率.如果所遇节点的转发概率比自己的大，则将报文转发给它，否则将自己传输或等待其他节点.与蔓延路由相比，网络开销降低，但与此同时，延迟会增加，报文递交率会降低.

基于社会网络的Bubble 路由算法主要利用社会网络的社区性和集中性现象.它的消息传递分为两步，并且有全局等级和本地活跃度等级两个等级信息.首先源节点根据全局等级信息将信息发送到具有更高集中度的节点，直到该节点与目标节点又属于同一个社区，然后在同一社区内部再根据本地活跃度等级信息将信息转发到目标节点.

本文在上述基础上提出一个基于节点亲密度的路由策略.利用人与人相处时间较为稳定的特征确定人与人之间的亲密度，再根据亲密度的大小辅助路由，最后利用实验与现有的路由进行分析比较，证明其有效性.

2 节点亲密度

在Reality 数据集中记录节点与节点的相遇信息.如两个节点相遇时，互相发送信号获知对方节点信息，一定周期内未收到对方信息即认为对方离开，结束相遇.获取相遇信息主要是为确定节点间的相遇时长，进而确定节点间亲密度.

2.1 亲密度定义

提出亲密度的定义如下:

节点与某个节点频繁相遇，使得周期T 内两个节点累计相处总时长达到一定限度，称该节点的亲密度高.

节点每次与另一节点nk相处的时长tk可通过式(1)获得，即用节点离开nk的时间lk减去节点与nk相遇的时间mk.

若在周期T 内节点对nk重复访问，累计时长

2.2 获知亲密度的方式

在获知节点亲密度时，可根据周期统计信息进行，并基于上一周期获知的统计数据指导下一周期的消息传递并辅助未来的路由.为此提出以下获知亲密度的方式:

设节点x 在最近1个周期T 内接触的其他m个节点的集合为Sx={n1，n2，…，nm}，集合中任意1个元素ni为节点x 最近1个周期接触时间大于零的节点，与Sx对应，节点x 与其他节点接触时长所组成的集合为ΔtSx={Δt1，Δt2，…，Δtm}，其中Δti为节点x 最近1个周期与节点ni接触的时长.那么节点x 与ni的亲密度C(x，ni)=Δ(ti/Δ(t1+Δt2+…+Δtm)).

根据人类的活动规律，文中设定1个周期为1周，统计节点在最近1个月(4 周)通信的节点信息，并求取亲密度.

3 基于节点亲密度的路由策略

3.1 社会网络模型

在现实生活中，人与人之间的亲密度具有较强的稳定性，即虽然会在生活中认识很多不同的人，但是与大部分人的亲密度都不高，如路人;而与少部分的人亲密度较高且相对稳定，如家人.

社会网络模型:例如，对于一个城市的社会网络，可以分为无数个人，那么抽象为社会网络模型，可以将这种网络的每个人看成是网络中的每个节点，网络之间的通信利用所携带的通信设备进行.可以看出，某些时刻社会网络内各节点之间通信可能具有间歇，所有这种网络表现出DTN 的特点.本课题就是对这样的社会网络进行抽象，将携带移动通信设备的人看作网络中的节点.利用亲密度的不同辅助节点间数据的传输，提出在DTN 社会网络环境中基于节点亲密度的路由策略(Human Intimate Degree Based Routeing，HIDBR).

3.2 HIDBR 路由策略中的消息传递

首先介绍下面所用到的数据结构.

其中:id为当前节点号;connectNode为该节点的接触节点集合Sx;c表示与本节点的亲密度C(x，ni).

设节点x 携带消息m，m 的目的节点为d，x 对下一节点y 的消息递交方法如下:(1)当y 节点即为目的节点d 时，x 节点将消息m 发送给y 节点并删除x 上的m，目的节点收到消息，消息传递结束.(2)当y 节点不是目的节点d 时，分别比较x和y 与d 的亲密度，若C(x，d)＜C(y，d)，x 节点将消息m 发送给y 节点，说明与x 相比，y 与目的节点的亲密度更高，y 与d 在上1个周期内相处的时间更长，能把消息传递给d 的可能性也更大.(3)当y 节点不是目的节点d 且C(x，d)≥C(y，d)时，不用传递消息，因为节点y 与节点d 的亲密度不高，传递的意义不大.(4)当C(x，d)=0，C(x，y)=0 时，x 与目的节点d 不相识且x 与y 也不相识，这种情况下y 与目的节点d 相识的可能性要大于x，但为了控制副本数量，暂不将这种情况列入消息传递.(5)每次消息传递前都要检查下一节点是否已收到相同的消息，若下一节点已经有相同的消息则不再重复发送，以便控制副本数量.

4 实验与分析

4.1 实验所用数据集和实验工具

选择基于人类真实移动轨迹的MIT Reality 数据集［8］作为实验基础，用VC++作为实验工具验证上述方法的有效性.在MIT Reality 项目中，收集的数据包括节点访问地点记录、节点间的接触记录(接触开始和结束时间)和通话记录等.

选择2004 年10 月和11 月的数据进行实验.其中，10 月的数据指对相关信息的获取，11 月根据已获得的信息，基于节点间的亲密度进行数据递交.首先要抽离数据集，创建每个人的活动记录(即保存每个节点与哪些节点有过接触)，然后统计各节点与其他节点的相处时长，最终获得每个节点的亲密度.初始节点数目为100，初始消息生存时间(TTL)为7 d.

4.2 实验结果与分析

4.2.1 与其他协议的比较

本实验将HIDBR 与DTN中现有的几种路由协议从传输率(delivery ratio)、传输延迟(latency)、传输开销(transmission consumption)几个方面进行比较，可以采用网络中传输报文的平均副本数量评估路由算法的资源消耗.

4.2.2 TTL 的影响

通过变化消息在网络中的生存时间观察其对网络性能产生的影响.

消息都具有生命周期，超过生命周期都将被删除.本实验的使用数据为1个月，实验设置TTL 波动为1～7 d，实验结果见图1～3.

结果分析:

(1)从图中可见，随着TTL 的增加，各个协议的消息传输成功率都呈上升趋势.这是因为随着消息TTL 的增加，将有更多的消息到达目的地.但与此同时，网络中的副本数在增加，资源开销也在增加.由于一些原先在TTL 到期前不能到达目的地的消息在TTL 增大后能到达目的地，参与计算平均延迟的消息数量增加，所以平均传输延迟也呈上升趋势.

(2)在这些协议中，由于蔓延路由协议穷举所有可能的传输路径，因此具有最高的消息传输成功率，且延迟最小，但其也具有最大开销.HIDBR和基于社会网络的Bubble 路由算法有针对性地发送信息，虽然消息传输成功率比蔓延路由协议稍低，但其传输开销也大大降低.

(3)基于社会网络的Bubble 路由算法中虽然把节点划分了社区，但社区内仅根据节点的活跃等级高低进行消息复制，节点间的亲疏远近关系却没有反映出来，有可能导致节点须经过较长的时间才能把消息递交给目的点，使得延迟相对较高，这也证实HIDBR 策略的有效性.

4.2.3 节点数量的影响

实验中的TTL 固定为7 d，通过变化实验节点数量观察其对网络性能的影响.设定初始节点数为10:

(1)从图4中看出，随着参与节点数量的增加，各协议的消息传输成功率呈上升趋势.这是因为随着参与节点的增加，节点之间接触的机会增多，数据传输机会增加，使得数据传输成功率及消息副本数量总体呈上升趋势(图5)，延迟总体呈下降趋势(图6).

(2)在所有协议中，蔓延路由协议的传输成功率最高.这是因为其充分利用节点间的连接机会，传输成功率比HIDBR和基于社会网络的Bubble 路由算法都高，但是其开销也最大.随着参与节点的增加，后两种算法的传输成功率较为接近.

(3)由图6可知，基于社会网络的Bubble 路由算法的延迟偏高.这是因为在消息传递过程中所选择的下一跳与目的节点的社会距离还不够近，导致延迟偏高.随着参与节点的增加，蔓延路由协议和HIDBR 的延迟总体呈下降趋势，特别是参与节点的数量较以后下降越明显.

5 结束语

本文通过实验验证HIDBR 的有效性.与现有的相关工作比较，HIDBR 在获得与蔓延路由协议接近的消息传输成功率的同时，传输开销大大降低，同时与基于社会网络的Bubble 路由算法等社会网络中的路由策略相比，可更好地实现数据传输成功率和传输开销、传输延迟之间的平衡.总体而言，DTN 的路由算法虽已取得一定的研究成果，但仍然处于初步阶段，特别是在理论研究及面向实际应用方面还有很大的研究空间，路由问题依旧是DTN 的关键难点问题之一.

［1］FALL K.A delay-tolerant network architecture for challenged Internets［C］// Proc ACM SIGCOMM’03.Karlsruhe:ACM Pr，2003:27-34.

［2］JAIN S，FALL K，PATRA R.Routeing in a delay-tolerant network［C］// Proc Conf on applications，Technologies，Architectures ＆ Protocols for Comput Commun (SIGCOMM’04).New York:ACM Pr，2004:145-158.

［3］张欣璐，刘广钟.无结构对等网络资源搜索算法［J］.上海海事大学学报，2008，29(2):78-81.

［4］熊桦，刘广钟.基于Sama 协议的移动Agent 组通信机制［J］.上海海事大学学报，2008，29(3):55-59.

［5］VAHDAT A，BECKER D.Epidemic routeing for partially connected Ad Hoc networks［D］.Durham，UK:Duke Univ，2000.

［6］LINDGREN A，DORIA A，SCHELEN O.Probabilistic routeing in intermittently connected networks［J］.Lect Notes in Comput Sci，2004:239-254.

［7］PAN H，CROWCROFT J，YONEKI E.Bubble Rap:social-based forwarding in delay-tolerant networks［C］// Proc 9th ACM Int Symp on Mobi-HOC.New York:ACM Pr，2008:241-250.

［8］EAGLE N，PENTLAND A，LAZER D.Inferring social network structure using mobile phone data［C］// Proc National Acad of Sci (PNAS).Massachusetts:Massachusetts Inst of Technol，2009:15274-15278.