容迟网络中基于节点间亲密度的分组路由方法

王恩，杨永健，赵卫丹，刘林璐

（1.吉林大学 计算机科学与技术学院，吉林 长春 130012；2.吉林大学 软件学院，吉林 长春 130012）

1 引言

Fall[1]在国际会议 SIGCOMM 上最早提出了容迟网络（DTN）[2，3]这一概念。其长延时，节点资源有限，间歇性连接，不对称传输速率，信噪比低等特点使针对这种网络环境提出一种良好的路由算法[4，5]成为当前的研究热点。

早期的关于容迟网络路由算法提出了一种单副本路由协议[6]，同一时间在网络中只保留特定消息的一个副本，该路由方式开销低，资源利用率高，但通常交付延迟较大，而且网络拓扑结构不断变化导致传输不可靠。因此提出了基于多拷贝的路由协议，Epidemic[7]是一种以病毒感染的方式在网络中扩散消息的多副本路由策略，这种方式消耗了大量的网络资源而导致实际应用中该路由协议性能随时间增加而明显降低。为了控制消息泛洪带来的资源消耗，提出了基于固定配额的多拷贝路由协议[8]，其中比较经典的是spray and wait[9]路由协议。这些经典的路由协议可以直接应用到社会网络中，但是随着节点数的增加，网络中冗余副本数显著提高，导致网络负载过大，节点缓存拥塞[10]等现象时常发生。

近年来，随着无线通信技术日趋成熟，通信设备的体积不断缩小，以人携带通信设备的方式形成了诸如体域网、校园网络[11]等网络环境，由于节点的移动受人类活动的影响，节点间的通信不再单纯地依靠随机的相遇来完成，而是与彼此的社会关系（如亲人、同事、朋友）产生了密不可分的联系，这使容迟网络体现出了经典的“小世界现象”，即节点间可以依据其社会属性通过一跳或几跳与其他节点产生联系，社会关系亲密的节点间会表现出良好的数据通信能力。这样在容迟网络中挖掘出节点间的社会关系，以应用到路由的选择策略中就成了近期比较热门的研究课题，研究人员就如何划分社交网络已经提出了很多社交圈（社交簇）的挖掘方法：文献[12]通过聚类方法抽取网络的层次结构，定义了一套社会网络的标注密度估计函数，通过该函数进行网络层次上的聚合操作，进而提出了基于密度估计的社会网络特征簇挖掘方法；文献[13]通过研究Web链接结构，使用最大流—最小割定理思想对社区进行划分，将网络模型化为信息流通的信道和关节，进而划分出社区边界；文献[14]中，林友芳等人提出了边稳定系数模型和完全信息图模型，在此基础上设计和实现了一种有效的社区发现算法。

在容迟网络的路由策略中引入社交圈的挖掘方法，已经提出了很多性能较好的路由方法。文献[15]通过将移动规律相近的节点聚合成最近社交圈策略，提出了一种基于分簇的簇外喷射、簇间转发和簇内传染3阶段社交时延网络路由协议；在文献[16]中，周瑞涛等人通过对网络节点历史运动轨迹点聚类建立其热点活动区域，把热点区域重叠度较高的节点归为同一社区。在源节点和目的节点社区中以洪泛的方式加快消息扩散和传递速度。针对不同社区准确的选择中继节点。文献[17]中于海征等人利用社会网络中节点间的权值计算方法，计算出团队间的关系强度矩阵。消息源节点的团队依据关系强度矩阵选择适合节点作为中继向目的节点传递消息，考虑到了自私节点对传递的影响，提出了基于社会网络的可靠路由方法。

本文提出了以节点间相遇频率和节点间的通信时长为依据来确定节点之间亲密度的方法，克服了以往研究中只以相遇次数等[18]信息来确定节点关系的不准确性，同时本文利用节点亲密度的拓扑全图动态生成亲密关系树，能够动态适应节点之间关系的变化情况，通过对树结构的有效裁剪找到关系紧密的节点分组，应用该分组来进行容迟网络中的路由，有效地克服了以往路由算法选择下一跳的盲目性，进一步提高了基于节点间亲密度的分组路由方法PBI的性能。

2 网络模型定义

2.1 基于节点亲密度的拓扑模型

通常意义上的容迟网络模型很难用以往的如G=(V，E)的形式来表示，其中V是网络中的节点集合，E为边集。主要原因是其中节点的高移动性导致网络拓扑结构不断变化，点和点之间的边连接不够稳定，权值很难准确表示。但在社会网络下由于节点间存在某种社会关系，他们之间确实存在某种特定且相对稳定的联系[19]，如同事之间会在同一时间来到单位，在同一时间吃午饭，在同一时间下班。公交车司机会沿着固定的路线，有周期地在地图上移动。校园中老师每周的课时不变，每节课上课的时间都会与特定的学生相遇等。由于这些人所带有的特定社会属性，导致他们之间的相遇并非偶然，存在着极强的规律性，挖掘出这样的社会关系对在社会时延网络下的路由算法有很大帮助，基于以上考虑定义网络拓扑模型如下。

定义1G=(V，E)为网络拓扑图，其中V为网络中的节点集合，E为定义在G上的边集。节点u，v∈V，eu，v∈E表示节点u和v之间的边，W(eu，v)表示eu，v的大小，在此特殊定义为节点间的亲密度。

通常对容迟网络中节点之间关系的研究只是将其简单地定义为相遇次数，或者直接将其简化为如果有联系就将边的权值设置为 1，否则为 0，这些对边权值的简化必然会导致模型表达的准确性下降，如图1所示。

图1 相遇情况

图1中表示了网络中2个节点在T时间内的4种相遇情况，如果单纯地用相遇次数来定义节点之间的联系强度，则4种情况对应的边的权值分别为2、4、1、1。即做如下判断：情况2下节点之间联系最紧密，情况3和情况4节点联系强度相同，显然这样的判断不够准确，没有考虑每次节点之间的通信时长，在某种情况下相遇的节点未必通信，而通信时间的长短往往更能够反应两节点社会关系的紧密强弱，故提出节点之间亲密度模型。

定义 2节点u，v∈V，eu，v∈E表示节点u和v之间的边，W(eu，v)表示表示节点u和v的节点间亲密度，n表示在统计的T时间内u和v的相遇总次数，Tk表示第K次相遇的通话时长，Bk表示第K次断开的时间长度。W(eu，v)的计算通过图2所示，Ok表示第K次通话开始时所对应的节点间通信能力，Yk表示第K次通话结束时节点间的通信能力。其中增长和下降的斜率定义为增长系数α和阻尼系数β，为了简化模型，将α和β值设置为1。

图2 节点间通信能力

本文认为节点间持续的通信说明节点间有着较强的通信能力，长时间的通信断开会导致通信能力下降，当下降为0时就停止下降，等待下一次通信的开始，而图2中阴影部分的面积即表示节点间的亲密度可由式(3)得到，Tk和Bk均由统计量得到，O1=0，Y1=T1。

应用以上节点间亲密度模型，对图1数据进行分析得到4种相遇情况所对应的通信能力如图3所示，根据图3计算得到节点间亲密度在这4种情况下分别为，从数据可以看出这样的节点间亲密度定义更能准确地反应出节点之间的社会关系，情况3下由于其长时间通信而导致其亲密性最高，而情况4的通信时间较短，且断开时间较长，导致其亲密性最低。

图3 不同相遇情况下的通信能力

2.2 亲密关系树模型

为了简化网络模型，以 5个节点的网络为例，根据定义 1，网络中可以生成一张完全带权拓扑图（如图4所示），其中节点之间的边的权值表示亲密度，由定义2得到。依据这样的拓扑图，通过算法1[20]可以生成一棵亲密关系树（如图5所示），该算法与文献[20]的分组算法执行流程相同,但是分组的依据有截然的区别,即本文提出的带权拓扑图中的权重能很好地显示节点间通信的能力,进而帮助容迟网络环境下报文的路由,在这里特殊强调的是其中特殊标注的节点为算法中每次随机选取获得的节点。

海明威在其创作中一直遵循年轻时形成的“电报体风格”，在其作品《午后之死》中也正式提出了他在创作上的“冰山原则”。海明威以冰山为喻，表达了作者只应描写冰山露出水面的一小部分，而隐藏于水下的则应该通过文字的延伸由读者去想象补充这一主张。本文通过解读《老人与海》，分析小说的文体风格及人物塑造来探究“冰山原则”的独特之处。

图4 网络带权拓扑

图5 树结构

这样通过算法1自底向上生成了一棵亲密关系二叉树，网络中的总节点数为n，则这棵亲密关系树的非叶子节点个数为n-1，这样就应用节点间亲密度模型找到了网络中n-1个关系紧密的分组集合，特别注意的是第6)和8)步中每次选取剩余集合中内部平均亲密度最高的集合成为Gk，这主要是考虑让社会关系紧密的圈子尽可能多地吸纳进节点，以保证算法得到的集合内部社会关系强度远高于集合外部，从某种意义上也防止由于过分随机选取集合而导致分组的差异行和不合理性，为了防止内部亲密度过高的分组较多，这些分组不愿意和外部集合成组，而导致算法在 2)、3)、4)、6)中循环，无法建立起一颗完整二叉树，所以在3)中加入了亲密度W(Gi，Gj)均小于W(Vk)的判断，然后跳到9)中完成亲密关系树的建立。

2.3 基于节点亲密关系树的分组裁剪模型[20]

根据算法 1，亲密关系树中的所有非叶子节点均存放在M集合中，因为通过算法1得到了大量具有亲密关系的节点分组，所以这些集合中不免存在一些相互之间亲密关系较弱的分组，同时也存在着一些彼此之间具有包含关系的分组，因此需要对得到的集合进行裁剪，以挑选出那些彼此之间没有包含关系，并且集合内部具有较强亲密度的分组。

将集合M中的所有元素（集合）内部的关系亲密度值进行由大到小排序，将后一半亲密度比较小的分组从集合M中删除出去，这里选择删除后一半主要是通过多次实验发现亲密度较高的前一半分组即可覆盖网络中多数节点，所以删除后一半既能保证留下的分组都具有较高的关系亲密度，同时又能保证网络覆盖度。接下来遍历剩余的集合M，如果M中的某一个分组M1被M中其他某一分组所包含，则将M1从M中删除，则剩余的集合M中分组之间不存在包含关系，利用基于节点间亲密度的分组方法得到了网络中亲密度较高的所有分组。

3 基于节点间亲密度的分组路由方法PBI

文中借鉴基于配额的经典路由方法 spray and wait，该路由方法将消息传输过程分为spray 和wait阶段，在消息产生的时候就确定了消息的固定配额数，在spray阶段每当携带报文的节点遇到其他没有该消息的节点时，就将自己报文总数的一半分给这个节点，自己保留一半，当节点剩余的报文数量为1时spray阶段结束，该节点进入wait阶段，即等待该报文的目标节点出现，否则一直携带该报文。为了克服spray 阶段的盲目性，和wait阶段的保守性，结合基于节点亲密关系树的分组裁剪模型得到的分组，提出了基于节点间亲密度的分组路由方法(PBI)。

算法2基于亲密度的路由算法

基于节点间亲密度的分组路由方法源节点A，相遇节点B，目的节点C

基于节点间亲密度的分组路由方法与spray and wait算法一样分为2个阶段，在散发阶段首先判断相遇节点B和目的节点C是否在一个分组中，如果在则将源节点A本身的拷贝数的一半分给B，这样做加强了不同分组之间的报文散发，防止由于传统spray and wait中，具有相同运动规律的节点间形成的封闭性，导致一些报文在一些固定的节点间传播而无法发送到目的节点。另外将报文散发给与目的节点在一个分组内的节点，也有效增强了报文的投递概率。在等待阶段，不是被动地等待目的节点的出现，当遇到和目的节点在一个分组内的节点时，首先判断自己和目的节点是否在一个分组，如果不在，则将自己的唯一一份报文交付给相遇节点，如果自己和目的节点在一个分组内，则将自己的唯一一份报文复制一份给相遇节点，自己也留一份，这样做主要是为了增强主动路由过程，通过将报文迅速地投递到目的节点的分组，尽力交付报文。实验证明基于节点间亲密度的分组路由方法 PBI增强了投递成功率，减小了平均网络时延，更说明亲密度的计算模型以及依据亲密度的分组方法的准确性。

综上所述，基于节点间亲密度的分组路由方法PBI在spray and wait路由方法的基础上进行改进，首先定义节点间亲密度的概念，依据节点间亲密度生成整个网络的带权拓扑图，在其上引入之前的分组方法得到彼此之间亲密度较高的节点分组，进而在将spray and wait路由方法与节点分组结合得到效率更高的基于节点间亲密度的分组路由方法。在 ONE模拟器中对PBI、spray and wait以及Epidemic 3种路由方法进行测试，实验结果表明在不同的报文副本数，本地缓存以及报文生成速率的条件下PBI在投递成功率和平均时延方面取得了更好的路由性能。

4 实验结果与数据分析

4.1 实验环境设置

表1 参数说明

本文实验部分分为2个阶段：热启动阶段和路由阶段。故将仿真时间设置为10 000 s，前5 000 s节点在地图上遵循既定的移动模型，运用基于节点亲密度的拓扑模型生成亲密关系树，通过分组裁剪方法裁剪出有利于路由算法的亲密关系分组。从第5 000 s开始产生报文，将文中提出的基于节点间亲密度的分组路由方法PBI应用到仿真环境中，通过分别改变节点本地缓存的大小、报文初始副本数以及报文的生成速率这3个参数来观测路由算法的性能，与Epidemic、spray and wait 2种经典路由协议对比，从以下2个方面评估PBI协议。

投递概率=成功投递到目的节点的报文数量/网络中产生的报文总数

时延均值=消息到达目的节点的平均时间

4.2 实验结果分析

本文的仿真部分主要进行3组实验，分别在不同的本地缓存、报文副本数以及报文生成速率的网络环境下测试 PBI、Epidemic以及 spray and wait的路由性能。之所以选择更改这3个网络条件主要是基于以下考虑：本地缓存的大小能够影响路由算法的性能，准确的路由方法即使在较小的缓存空间下依然能够取得很好的投递效果。报文副本数能够影响spray and wait和PBI的感染范围。报文生成速率可以影响网络拥塞程度，进而影响路由结果。

第1组实验，将报文的初始副本数设为4，报文的生成速率为[15，25]即每隔(15～25) s的时间生成一个报文，改变节点本地缓存大小，在10 MB、20 MB、30 MB、50 MB、100 MB情况下，与spray and wait和Epidemic 2种路由协议相比，投递成功率变化情况如图6所示，平均时延变化情况如图7所示。

图6 不同缓存下的投递成功率

图7 不同缓存下的平均时延

图6中数据显示，在缓存较小的情况下（10 MB，20 MB），PBI表现出良好的投递性能，这主要是因为文中提出的分组方法大幅度减小了由于spray and wait盲目投递所造成的缓存和带宽的浪费。尤其是缓存不足的时候这种提升会更加明显，这主要是因为缓存空间有限时，节点能够携带的报文数量有限，因此容易发生报文的丢弃现象，只有提升路由方法的准确性才能得到投递成功率的提升。当缓存增大到50 MB以后，Epidemic的投递成功率显著提升，这主要是缓存大小趋于理想化，即使通过泛洪方式路由，网络也不会发生拥塞，导致Epidemic有很高的投递成功率，同时也容易看出PBI随着缓存增大依然保持着很好的投递效果，在100 MB缓存的情况下依然可以拥有和Epidemic持平的投递成功率。图7中数据显示PBI的平均时延小于另外2种路由方法，差值平均在100 s左右，尤其是在缓存较小时效果明显，更说明PBI很好地改善了路由性能。

第2组实验，将节点的缓存大小设置为100 MB，报文的生成速率同样为[15， 25]，改变报文的初始副本数，在2、4、6、8这4种情况下，与spray and wait和Epidemic 2种路由协议相比，投递成功率变化情况如图8所示，平均时延变化情况如图9所示。

图8 不同报文副本数下的投递成功率

从图8中数据可以得出如下结论：在缓存较大情况下，PBI有着与Epidemic不分伯仲的投递成功率，并且这个概率值平均比 spray and wait高出20%，当节点的初始copies数越小的时候，PBI的路由性能越明显，经分析这主要是因为在wait阶段PBI中引入了主动路由过程，抛弃了被动等待目的节点出现的保守行为，取得了路由性能上的提高。另外准确的分组方法，能够使持有报文的节点更清楚哪些节点能够很好地帮助路由过程，避免无意义的报文传输，因此能够通过组内和组间的合作完成报文的投递。图9中数据表明PBI在不同的报文初始副本数的情况下，其网络平均时延均小于另外 2种路由方法，并且其时延均值稳定在一个较低的范围内，不会大幅度波动。

图9 不同报文副本数下的平均时延

第3组实验，同样将节点的缓存大小设置为100 MB，报文的初始副本数同样设为4，改变报文的生成速率，在[5，15]、[15，25]、[25，35]、[35，45]这4种情况下，与spray and wait 和Epidemic 2种路由协议相比，投递成功率变化情况如图10所示，平均时延变化情况如图11所示。

图10 不同报文生成速率下的投递成功率

图11 不同报文生成速率下的平均时延

图 10中数据表明，在报文生成速率较高的情况下([5～15])，PBI的投递成功率比另外2种都要高，主要是因为过多的报文导致了 Epidemic的拥塞发生，过多的报文因为缓存溢出而丢弃，因此报文生成速率越高，溢出发生的可能性就越大，进而使其投递率随时间增长而下降，当报文的生成速率较低时，缓存拥塞得到了缓解，因此此时PBI和Epidemic的投递成功率相近。图 11中数据同样可以看出在报文生成速率较高情况下，Epidemic的平均时延最高，同样是因为报文的大量丢弃延长了报文到达的平均时间，进而证明确实发生了严重的拥塞，随着报文生成速率的下降，Epidemic的平均时延平稳降低，但是PBI的平均时延一直低于另外2种路由方法。

综上所述，PBI路由方法提高了路由的投递成功率，减小了网络的平均时延。在不同的报文副本数、本地缓存以及报文生成速率的条件下与Epidemic和spray and wait相比均得到了较好的路由性能。经过分析主要是因为Epidemic局限于缓存的约束，当缓存较小时会发生拥塞现象，而spray and wait路由方法的spray阶段存在盲目性，wait阶段的被动等待使其损失了大量的投递机会，而PBI很好地解决了以上问题，首先PBI在spray and wait上进行改进，就已经限制了报文的蔓延上限，而PBI通过节点亲密度的计算结果进行分组，使彼此通信机会良好的节点进入同一分组，依据该分组结果进行组内和组间的报文散发，因此取得了最好的投递效果。

5 结束语

容迟网络环境下由于节点的移动性较强，节点间连接频繁中断，导致该网络环境下节点以“存储-携带-转发”的方式进行报文投递，传统的TCP/IP协议不再适用于该网络环境，因而在该网络环境下的报文路由问题一直是当今研究领域的前沿问题。本文在容迟网络环境中通过定义节点之间的亲密度模型形成了一张整个网络的带权拓扑图，依据亲密关系树生成模型挖掘出一些内部有亲密关系的分组，通过裁剪方法得到了互相之间没有包含关系的节点分组，利用该分组信息进行容迟网络中的路由算法决策，提出了基于节点间亲密度的分组路由方法 PBI，实验表明 PBI与 spray and wait 和Epidemic 2种路由方法相比大幅度提高投递成功率，并且减小网络平均时延。在接下来的工作中，计划取消热启动阶段，将节点的分组挖掘过程渗透进路由方法中，动态地完成亲密关系分组的挖掘，即通过网络信息的搜集动态地进行路由决策，进而通过实验验证想法的可行性。

[1] FALL K. A delay-tolerant network architecture for challenged Internets[A]. Proc of the ACM SIGCOMM[C]. 2003.27-34.

[2] BURLEIGH S， HOOKE A， TORGERSON L，et al. Delay tolerant networking： an approach to interplanetary internet[J]. IEEE Communications Magazine， 2003.41(6)：128-136.

[3] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y，et al. A survey on sensor networks[J]. IEEE Communications Magazine， 2002，40(8)： 102-114.

[4] JONES E， WARD P. Routing strategies for delay-tolerant networks[A]. Proc of International Conference on Wireless Communications and Mobile Computing[C].2006.

[5] 熊永平， 孙利民， 牛建伟等. 机会网络[J]. 软件学报， 2009， 20(1)：124-137.XIONG Y P， SUN L M， NIU J W，et al. Opportunistic networks[J].Journal of Software， 2009， 20(1)： 124-137.

[6] JAIN S， FALL K， PATRA R. Routing in delay tolerant network[A].Proc of SIGCOMM[C]. New York： ACM Press， 2004.145-157.

[7] VAHDAT A， BECKER D. Epidemic routing for partially connected ad hoc networks[R]. Duke University， 2000.

[8] TANG L， ZHENG Q， LIU J，et al. SMART： A selective controlled-flooding routing for delay tolerant networks[A]. Fourth International Conference on IEEE Broadband Communications， Networks and Systems[C]. 2007.356-365.

[9] SOYROPOULOS T， PSOUNIS K， RAGHAVENDRA C S. Spray and wait： an efficient routing scheme for intermittently connected mobile networks[A]. Proc of the ACM SIGCOMM Workshop on Delay-Tolerant Networking[C]. 2005.252-259.

[10] 王恩， 杨永健， 李莅. DTN 中基于生命游戏的拥塞控制策略[J]. 计算机研究与发展， 2014， 51(11)： 2393-2407.WANG E， YANG Y J， LI L. Game of life based congestion control strategy in delay tolerant networks[J]. Journal of Computer Research and Development， 2014， 51(11)： 2393-2407

[11] SU J， CHIN A， POPIVANOVA A，et al. User mobility for opportunistic ad-hoc networking[A]. Proc of the 6th IEEE Workshop on Mobile Computing System and Applications[C]. 2004.41-50.

[12] 韩毅， 方滨兴， 贾焰等. 基于密度估计的社会网络特征簇挖掘方法[J]. 通信学报， 2012， 33(5)： 38-48.HAN Y， FANG B X， JIA Y，et al. Mining characteristic clusters： a density estimation approach[J]. Journal on Communications， 2012，33(5)：38-48.

[13] ZENG Z P，WANG J Y，ZHOU L Z，et al. Coherent closed quasi-clique discovery from large dense graph databases[A]. Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， KDD '06[C]. 2006. 797-802.

[14] 林友芳， 王天宇， 唐锐等. 一种有效的社会网络社区发现模型和算法[J]. 计算机研究与发展， 2012， 49(2)： 337-345.LIN Y F， WANG T Y， TANG R，et al. An effective model and algorithm for community detection in social networks[J]. Journal of Computer Research and Development， 2012， 49(2)： 337-345.

[15] 李陟， 李千目， 张宏. 基于最近社交圈的社交时延容忍网络路由策略[J]. 计算机研究与发展，2012， 49(6)： 1185-1195.LI Z， LI Q M， ZHANG H. Closely social circuit based routing in social delay tolerant networks[J]. Journal of Computer Research and Development， 2012， 49(6)： 1185-1195.

[16] 周瑞涛， 曹元大， 胡晶晶. 基于社区的容迟网络路由方法[J]. 北京理工大学学报， 2012， 32(009)： 966-970.ZHOU T R， CAO Y D， HU J J. Community based routing in delay and tolerance networks[J]. Transaction of Beijing Institute of Technology，2012， 32(009)： 966-970.

[17] 于海征， 马建峰， 边红. 容迟网络中基于社会网络的可靠路由[J].通信学报， 2010， 31(12)： 21-26.YU H Z， MA J F， BIAN H. Social network-based trustworthy routing in delay tolerant networks[J]. Journal on Communication， 2010，31(12)： 21-26.

[18] VELLAMBI B N， SUBRAMANIAN R， FEKRI F，et al. Reliable and efficient message delivery in delay tolerant networks using rateless codes[A]. Proc of the 1st International Mobisys Workshop on Mobile Opportunistic Networking[C]. ACM， 2007.91-98.

[19] EAGLE N， PENTLAND A S， LAZER D. Inferring friendship network structure by using mobile phone data[J]. Proceedings of the National Academy of Sciences， 2009， 106(36)： 15274-15278.

[20] 王恩， 杨永健， 李莅. 基于动态半马尔可夫路径搜索模型的 DTN分 簇 路 由 方 法 [EB/OL]. http：//cjc.ict.ac.cn/online/bfpub/we-20141216123501.pdf.WANG E， YANG Y J， LI L. A Clustering Routing Method Based on Semi-Markov Process and Path-finding Strategy in DTN[EB/OL].http：//cjc.ict.ac.cn/online/bfpub/we- 20141216123501.pdf.