【www.zhangdahai.com--实习报告】
摘 要：为改进面向社会环境的延迟容忍网络中的路由策略，引入亲密度关系的概念.基于人与人相处的时间呈幂率分布这一规律，提出基于节点间亲密度的路由策略（HumanIntimateDegree BasedRouteing，HIDBR）.根据人与人相处时间较为稳定的特征确定人与人之间的亲密度，再用亲密度辅助路由.基于节点真实移动轨迹的实验表明：与延迟容忍网络中现有的几种路由策略相比，这一路由策略可更好地实现数据传输的成功率与传输能耗、传输延迟之间的平衡.
关键词：延迟容忍网络；路由策略；社会网路；亲密度
中图分类号：TP393.027 文献标志码：A
DTNrouteingstrategybasedonintimatedegreeamongnodes
FENGTao，LIUGuangzhong
（InformationEngineeringCollege，ShanghaiMaritimeUniv.，Shanghai201306，China） Abstract：Inordertoimproverouteingstrategyofthesocialorienteddelaytolerantnetworks，theconcep�tionofhumanintimatedegreeisintroduced.Basedontherulethatthetimepeoplestayingtogetherfol�lowspower�lawdistributions，aHumanIntimateDegreeBasedRouteing（HIDBR）isproposed.Basedon thecharacteristicthatthetimepeoplestayingtogetherisstable，theintimatedegreeamongpeopleiscon�firmed，andthentheintimatedegreeisusedtosupportrouteing.Experimentsbasedontherealmobility tracesoftherealnodesshowthatthestrategyachievesbettertradeoffbetweenthedatadeliveryratioand thedeliveryoverhead／delay，incomparisonwiththecurrentrouteingstrategyindelaytolerantnetworks. Keywords：delay�tolerantnetwork；routeingstrategy；socialnetwork；intimatedegree
1 相关工作
DTN现有的研究虽有一定成果，但仍处于初步阶段.也可能是适用性的限制，大家都热衷于研究一些比较热门的网络模型和通信机制，如对等网络资源搜索算法［3］和移动Agent组通信机制［4］.但是，DTN的研究无论是在理论还是面向实际应用方面都有很大的研究空间.
在DTN的研究过程中，网络的路由协议被人关注最多.几种比较典型的DTN路由算法：VAHDAT等［5］提出的蔓延路由协议（epidemicrouteing）、基于概率的路由协议（probabilisticrouteing）［6］和PAN等［7］提出的基于社会网络的Bubble路由算法.
蔓延路由协议的思想是把所要发送的报文给它所有的邻居节点.这种路由方式意味着：只要节点的缓存足够大，随着节点之间的不断“接触”，数据就会从源端开始像病毒那样传播到网络中的其他节点，从而大大增加网路负担，造成网络拥塞.所以，现实情况下，由于缓存空间、能量、带宽等资源的限制，传染路由性能会严重降级，很难适应现实环境.
PROPHET（ProbabilisticRouteingProtocolusing
HistoryofEncountersandTransitivity）［6］是一种基于概率估计的路由，与传染路由盲目地向所有邻居节点转发消息不同，概率路由中的每个节点将会估计到达目的节点的概率.如果所遇节点的转发概率比自己的大，则将报文转发给它，否则将自己传输或等待其他节点.与蔓延路由相比，网络开销降低，但与此同时，延迟会增加，报文递交率会降低.
基于社会网络的Bubble路由算法主要利用社会网络的社区性和集中性现象.它的消息传递分为两步，并且有全局等级和本地活跃度等级两个等级信息.首先源节点根据全局等级信息将信息发送到具有更高集中度的节点，直到该节点与目标节点又属于同一个社区，然后在同一社区内部再根据本地活跃度等级信息将信息转发到目标节点.
本文在上述基础上提出一个基于节点亲密度的路由策略.利用人与人相处时间较为稳定的特征确定人与人之间的亲密度，再根据亲密度的大小辅助路由，最后利用实验与现有的路由进行分析比较，证明其有效性.
4 实验与分析
4.1 实验所用数据集和实验工具
选择基于人类真实移动轨迹的MITReality数据集［8］作为实验基础，用VC＋＋作为实验工具验证上述方法的有效性.在MITReality项目中，收集的数据包括节点访问地点记录、节点间的接触记录（接触开始和结束时间）和通话记录等.
选择2004年10月和11月的数据进行实验.其中，10月的数据指对相关信息的获取，11月根据已获得的信息，基于节点间的亲密度进行数据递交.首先要抽离数据集，创建每个人的活动记录（即保存每个节点与哪些节点有过接触），然后统计各节点与其他节点的相处时长，最终获得每个节点的亲密度.初始节点数目为100，初始消息生存时间（TTL）为7d.
4.2 实验结果与分析
4.2.1 与其他协议的比较
本实验将HIDBR与DTN中现有的几种路由协议从传输率（deliveryratio）、传输延迟（latency）、传输开销（transmissionconsumption）几个方面进行比较，可以采用网络中传输报文的平均副本数量评估路由算法的资源消耗.
4.2.2 TTL的影响
通过变化消息在网络中的生存时间观察其对网络性能产生的影响.
消息都具有生命周期，超过生命周期都将被删除.本实验的使用数据为1个月，实验设置TTL波动为1～7d，实验结果见图1～3. 时，网络中的副本数在增加，资源开销也在增加.由于一些原先在TTL到期前不能到达目的地的消息在TTL增大后能到达目的地，参与计算平均延迟的消息数量增加，所以平均传输延迟也呈上升趋势.
（2）在这些协议中，由于蔓延路由协议穷举所有可能的传输路径，因此具有最高的消息传输成功率，且延迟最小，但其也具有最大开销.HIDBR和基于社会网络的Bubble路由算法有针对性地发送信息，虽然消息传输成功率比蔓延路由协议稍低，但其传输开销也大大降低.
（3）基于社会网络的Bubble路由算法中虽然把节点划分了社区，但社区内仅根据节点的活跃等级高低进行消息复制，节点间的亲疏远近关系却没有反映出来，有可能导致节点须经过较长的时间才能把消息递交给目的点，使得延迟相对较高，这也证实HIDBR策略的有效性. 4.2.3 节点数量的影响
实验中的TTL固定为7d，通过变化实验节点数量观察其对网络性能的影响.设定初始节点数为10：
（1）从图4中看出，随着参与节点数量的增加，各协议的消息传输成功率呈上升趋势.这是因为随着参与节点的增加，节点之间接触的机会增多，数据传输机会增加，使得数据传输成功率及消息副本数量总体呈上升趋势（图5），延迟总体呈下降趋势（图6）.
（2）在所有协议中，蔓延路由协议的传输成功率最高.这是因为其充分利用节点间的连接机会，传输成功率比HIDBR和基于社会网络的Bubble路由算法都高，但是其开销也最大.随着参与节点的增加，后两种算法的传输成功率较为接近.
（3）由图6可知，基于社会网络的Bubble路由算法的延迟偏高.这是因为在消息传递过程中所选择的下一跳与目的节点的社会距离还不够近，导致延迟偏高.随着参与节点的增加，蔓延路由协议和HIDBR的延迟总体呈下降趋势，特别是参与节点的数量较以后下降越明显.
5 结束语
本文通过实验验证HIDBR的有效性.与现有的相关工作比较，HIDBR在获得与蔓延路由协议接近的消息传输成功率的同时，传输开销大大降低，同时与基于社会网络的Bubble路由算法等社会网络中的路由策略相比，可更好地实现数据传输成功率和传输开销、传输延迟之间的平衡.总体而言，DTN的路由算法虽已取得一定的研究成果，但仍然处于初步阶段，特别是在理论研究及面向实际应用方面还有很大的研究空间，路由问题依旧是DTN的关键难点问题之一.
感谢刘帮等同学的帮助，使得本文顺利完成.
参考文献：
［1］FALLK.Adelay�tolerantnetworkarchitectureforchallengedInternets［C］／／ProcACMSIGCOMM’03.Karlsruhe：ACMPr，2003：27�34.
［2］JAINS，FALLK，PATRAR.Routeinginadelay�tolerantnetwork［C］／／ProcConfonapplications，Technologies，Architectures＆Protocolsfor ComputCommun（SIGCOMM’04）.NewYork：ACMPr，2004：145�158.
［3］张欣璐，刘广钟.无结构对等网络资源搜索算法［J］.上海海事大学学报，2008，29（2）：78�81.
［4］熊桦，刘广钟.基于Sama协议的移动Agent组通信机制［J］.上海海事大学学报，2008，29（3）：55�59.
［5］VAHDATA，BECKERD.EpidemicrouteingforpartiallyconnectedAdHocnetworks［D］.Durham，UK：DukeUniv，2000.
［6］LINDGRENA，DORIAA，SCHELENO.Probabilisticrouteinginintermittentlyconnectednetworks［J］.LectNotesinComputSci，2004：239�254.
［7］PANH，CROWCROFTJ，YONEKIE.BubbleRap：social�basedforwardingindelay�tolerantnetworks［C］／／Proc9thACMIntSymponMobi�HOC.NewYork：ACMPr，2008：241�250.
［8］EAGLEN，PENTLANDA，LAZERD.Inferringsocialnetworkstructureusingmobilephonedata［C］／／ProcNationalAcadofSci（PNAS）.Mas�sachusetts：MassachusettsInstofTechnol，2009：15274�15278.
（编辑 廖粤新）
