基于友好社区的容迟网络路由算法

曹 成, 郭清伟, 王青山, 夏茂晋, 汪丽芳

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



基于友好社区的容迟网络路由算法

曹 成, 郭清伟, 王青山, 夏茂晋, 汪丽芳

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

在容迟网络(delay tolerant networks,DTNs)中,由于节点间端到端连接的不稳定性,传统路由算法不再适合容迟网络。文章根据节点访问社区的历史信息定义节点的友好社区,并提出了一种基于友好社区的路由算法(friend community-based routing algorithm,FCR)。在该算法中,源节点首先将数据包传递给自身的友好社区访问接入点(access point,AP),然后源节点的友好社区AP选择本社区中与目的节点友好社区AP接触次数最多的节点作为中继点。从而数据包被快速地传递到目的节点的友好社区,并最终由目的节点的友好社区AP将数据包传递到目的节点。仿真实验结果表明,与著名的Epidemic、Label和SGBR算法相比,该算法在保证接近Epidemic算法达到最大传递率的情况下,仍然可以明显地节约网络拷贝数。

容迟网络;友好社区;路由算法;拷贝数;传递率

容迟网络(delay tolerant networks,DTNs)[1-2]是指由于节点密度稀疏、能量有限等原因而导致端到端连接不稳定、节点间间歇式接触的一类无线网络。DTNs广泛地应用于社交、军事战争、航天通信、灾难恢复及应急抢险等领域,使得容迟网络成为无线网络研究领域的一个热点问题。与传统网络相比,DTNs的动态拓扑变化,节点间端到端连接不稳定,所以传统的路由协议无法直接应用于DTNs。为了克服自身端到端连接的不稳定性,DTNs经常使用“存储-携带-转发”的数据转发策略。

Epidemic算法[3]作为典型的基于洪泛的路由算法,是指相遇节点之间相互交换彼此没有的数据包,快速地将数据包传递到目的节点。但是由于网络过度复制数据包从而消耗大量网络资源。Spray and Wait 算法[4]将路由算法分为2个阶段,第1阶段(Spray)利用二元喷洒在网络中产生固定数量的拷贝进行传递;第2阶段(Wait)携带数据包的节点只有遇到目的节点时才会传递数据包以完成路由算法。Spray and Focus 算法[5]是在Spray and Wait算法的基础上改变第2阶段,携带数据包的节点会主动将数据包传递给效用值比自己高的节点或者目的节点。Spray and Forward算法[6]首先利用马尔可夫链预测目的节点的位置,然后采用二元喷洒的方法将数据包传递到目的节点所在的位置,最后采用贪心算法将数据包传递给目的节点。这为有目的地传递数据包方案奠定了坚实的基础。

最近,人们的研究热点是利用节点的社会属性来设计路由算法,例如:节点的社区性、中心性、友好性及相似性等。Label算法[7]将网络中的每个节点贴上标签,同一社区的节点标签相同,数据包只传递给和目的节点有相同标签的节点,从而提高了数据包的传递率。Bubble Rap 算法[8]从社区和节点的中心性2个方面来设计算法,在该算法中,每个节点具有全局中心性和局部中心性。首先,根据全局中心性来传递数据包,直到数据包被传递到目的节点所在社区,然后根据局部中心性将数据包传递到目的节点。Dsearching算法[9]在节点经常出现的地理位置设立静态地标,该算法首先利用节点的移动轨迹来将数据包传递到目的节点所在地标,然后利用贪心算法将数据包传递到目的节点,从而大大提高了数据包的传递率和网络资源的利用率。

本文通过考虑节点和社区之间的关系,设计了基于节点与社区友好性的路由算法(friend community-based routing algorithm,FCR)。每个节点都有其经常出现的社区,如图1所示,学生B经常出现在食堂、教室和宿舍,如果学生A要传递数据包给学生B,则学生A可以将数据包分别传到食堂、教室和宿舍,通过这些途径高效地将数据包传递给学生B。根据节点之间的关系将网络划分为不同的社区,在同一个社区中,节点之间接触频繁,不同社区的节点可能很少接触,甚至从未相遇。一个节点可能会出现在不同社区,而且每个节点在不同社区出现的频率也是不同的。如果某个节点在同一个社区频繁出现,称这个社区为该节点的友好社区。如果知道目的节点所在的友好社区,源节点可以将数据包直接传递给目的节点或目的节点的友好社区中的节点,从而节约网络资源消耗。

图1 利用友好社区传递数据包示意图

1 网络模型

在生活中,人们通常因为兴趣爱好、职业以及一些社会属性经常往返多个社区。本文将DTNs划分成N个地理社区,每个社区都有一个固定的访问接入点(access point,AP)配置无线访问设备。n个携带无线访问设备的人可以在网络中随意行走。

AP设备之间可以通过人群的流动性来交换数据包,并且每个人都有其经常往返的地理社区,同一个时刻位于同一个地理社区的2个人之间能够建立联系并且交换数据包。根据节点i在不同社区访问的历史信息,可以计算出在一定时间t内节点i访问社区j的次数在其所有访问社区总次数中所占的比例,即

(1)

其中,Ci,j为节点i访问社区j的次数。

定义1 节点i访问社区j,当且仅当λi,j(t)>λ(1≤i≤n,1≤j≤N)时,社区j为节点i的友好社区,其中λ为阈值。同时,定义一个自由变量,即

(2)

对应不同的阈值λ,每个节点i可能会有不同的友好社区。而且,每个节点访问其友好社区的频率也是不同的。

根据定义1,可以得到每个节点的友好社区，见表1所列。编号为1的节点有2个编号为1、2的友好社区,编号为2的节点有3个编号为2、3和12的友好社区。

表1 网络中节点的友好社区

2 基于友好社区的路由算法及分析

在给出基于友好社区的路由算法之前,首先介绍如何计算节点的友好社区。节点每次访问一个社区都会计算该时刻访问该社区的次数以及访问其他所有社区的总次数,从而判断该社区是否是友好社区。每对节点相遇时都会交换彼此的友好社区关系图G=(V1,V2,E),其中，V1为网络中的节点集合；V2为网络中的社区集合,E为边的集合。如果社区j为节点i的友好社区,则边(i,j)存在。

根据友好社区关系图可以得到源节点的友好社区以及目的节点的友好社区,即源节点和目的节点经常访问的社区。

2.1 基于友好社区的路由算法

在本文提出的FCR算法中,希望节点间可以通过友好社区AP协助传递数据包。假设携带数据包的源节点s要传递数据包给目的节点d,将源节点s的友好社区AP组成的集合记作:

将目的节点d的友好社区AP组成的集合记作:

FCR算法步骤如下:

(1) 源节点s遇到自己的友好社区AP集合Ms中的节点、目的节点的友好社区AP集合Md中的节点以及目的节点,源节点都会拷贝数据包给这些节点。

(2)Ms中的AP根据友好社区关系G=(V1,V2,E),对于Md中每个社区,选择同该社区接触次数最多并且该AP代表的社区是该节点的友好社区的节点作为中继点,并传递数据包给对应的社区Md。称该中继点为r,r满足(3)式，即

(3)

其中,Md,k为Md中第k个友好社区;Ms,j为Ms中第j个友好社区。然后节点r将数据包传递给目的节点的友好社区中的AP。

(3) 当目的节点友好社区Md中的AP接收到数据包之后,只会传递数据包给目的节点d。

(4) 算法传递过程中,如果某个数据包携带节点遇到目的节点,则直接传递数据包给目的节点,算法结束。

2.2 算法分析

根据本文提出的FCR算法,数据包从源节点最多经过四跳到达目的节点。根据数据包从源节点到达目的节点经过中继点数的不同,分为如下4种情况:

(1) 源节点s直接将数据包传递到目的节点,并且只产生一个拷贝数。

(2) 源节点s经过两跳将数据包传递到目的节点,首先源节点选择自身的友好社区集合中的AP点或者目的节点友好社区集合的AP作为中继点,然后这些节点直接将信息传递到目的节点。该情况最多产生的拷贝数为max{(|Ms|+1),(|Md|+1)}。

(3) 源节点s经过三跳将数据包传递到目的节点。源节点首先将信息传递到自身友好社区集合中的AP,然后该AP选择中继点r,最终中继点r将数据包直接传递给目的节点。该情况最多产生的拷贝数为|Ms|+|Md|+1。

(4) 源节点s经过四跳将数据包传递到目的节点。源节点首先选择自己的友好社区集合中的AP作为中继点,然后携带数据包的AP选择满足(3)式的节点作为中继点将数据包传递到目的节点所在社区集合的AP,最终该AP将数据包直接传递给目的节点。该情况最多产生的拷贝数为|Ms|+|Md|+|Md|+1。因此,可以计算出总的拷贝数的上界为O(|Ms|+|Md|)。因此得出结论1。

结论1 数据包从源节点到达目的节点最多经过四跳,最多产生拷贝数为|Ms|+2|Md|+1。

当λ越小,源节点s的友好社区和目的节点d的友好社区越多,源节点选择中继点传递数据包的路径越多。因此,源节点s将数据包传递到目的节点产生的拷贝数越多,得出结论2。

结论2 网络中的拷贝数与阈值λ负相关。

3 性能评价

本文使用C++开发了一个模拟器来比较FCR算法、著名的Epidemic[3]、Label[7]和SGBR[12]算法的性能。在Epidemic算法中,携带数据包的节点会将数据包传递给所有相遇且没有存储该数据包的节点。Label算法中携带数据包的节点只将数据包传递给目的节点所在社区的节点。SGBR算法提出了一种利用节点间社会团体的网络模型,该模型是在最小化网络消耗前提下最大化数据包传递率。从3个方面来衡量上述4个算法的性能:① 传递率,网络中被成功传递的数据包占所有发送数据包的比例;② 平均延迟,数据包从源节点到达目的节点所需要的平均时间;③ 拷贝数,每个数据包在网络中传递所拷贝的数据包数目,又称为网络消耗。

模拟实验采用Infocom 06[13]的真实跟踪数据作为节点的移动模式,它是由2006年在西班牙巴塞罗那召开的Infocom 会议上78个学生通过携带imote设备采集得到的。会场布置20个固定的imote设备作为 AP,分布在不同区域形成社区。

(1) FCR、Epidemic、Label和 SGBR算法的路由性能。在DTNs中,由于网络端到端连接的不稳定性,如果数据包生存时间(time-to-live,TTL)过低,路由算法可能无法完成大部分数据包传递。因此,将数据包存活时间TTL从6 h增加到20 h,来比较FCR算法与Epidemic、Label、SGBR算法的路由性能,其中λ=0.04。

FCR算法与Epidemic、Label、SGBR算法的路由性能比较结果如图2所示。

由图2a可知,随着TTL的增加,4个算法的传递率都有所增加,并且趋于稳定。在传递率上,FCR算法的传递率比Label平均高4%左右,比SGBR平均高大约2%,接近Epidemic。

由图2b可知,FCR算法的拷贝数比Epidemic平均低大约75%,比Label平均低大约59%,比SGBR平均低大约30%。

由图2c可知,FCR算法的平均延迟比SGBR低大约5%,比Epidemic平均高29%左右,比Label平均高大约20%。

(2) 阈值λ对FCR算法性能的影响。为了研究λ值对FCR算法的影响,控制TTL=16 h不变,λ从0.02增加到0.1,λ值对FCR算法性能的影响如图3所示。

由图3可以发现，随着λ值的增加,FCR的传递率和平均延迟都在缓慢的变化,传递率有所减小,平均延迟相对增大。而拷贝数变化比较明显,λ值从0.02变化到0.1,FCR算法的拷贝数减少了大约50%。这些结果进一步证明了结论2的正确性。

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

图3 λ值对FCR算法性能的影响

4 结 论

本文利用节点与社区AP之间的友好性,提出了一个基于社区友好性的路由算法FCR。源节点通过自身的友好社区AP和目的节点的友好社区AP将数据包传递给目的节点,从而可以有效地减少网络资源消耗。通过模拟实验发现，该算法在提高传递率的同时大大节约了网络资源消耗。

[1] BALASUBRAMANIAN A,LEVINE B N,VENKATARAMANI A.DTN routing as a resource allocation problem[C]//Proceedings of SIGCOMM′ 2007.Kyoto,2007:373-384.

[2] 刘艳萍,王青山,王琦,等.移动社交网络中基于影响力的数据转发算法 [J].合肥工业大学学报(自然科学版),2014,37(3):295-300.

[3] VAHDAT A,BECKER D.Epidemic routing for partially-connected ad hoc networks[EB/OL].(2015-01-04).http://cseweb.ucsd.edu/～vahdat/papers/epidemit.pdf..

[4] SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Spray and wait:an efficient routing scheme for intermittently connected mobile networks[C]//Proceedings of the 2005 ACM SIGCOMM Workshop on Delag-tolerant Natworking.New York:ACM Press,2005:252-259.

[5] SPYROPOULOS T,PSOUNIS K,RAGHAVENDRA C S.Spray and focus:efficient mobility-assisted routing for heterogeneous and correlated mobility[C]//Fifth Annual IEEE International Conference on Pervasive Computing and Comwnication Workshops.New York:IEEE Press,2007:79-85.

[6] DANG F,YANG X L,LONG K P.Spray and forward:efficient routing based on the markov location prediction model for DTNs[J].Science China Information Sciences,2012,5(2):433-440.

[7] PAN Hui,CROWCROFT J.How small labels creat big improvements [C]//Fifth Annual IEEE International Conference.on Pervasive and Comwnication Workshops.New York:IEEE Press,2007:65-70.

[8] PAN Hui,CROWCROFT J,YONEKI E.Bubble rap:social-based forwarding in delay tolerant networks[J].IEEE Transactions on Mobile Computing,2011,10(11):1576-1589.

[9] CHEN K,SHEN H Y.DSearching:Distributed searching of mobile nodes in DTNs with floating mobility information[C]//IEEE INFOCOM 2014-IEEE conference on Computer Communications,2014:2283-2291.

[10] ERRAMILLI V,CHAINTREAU A,CROVELLA M,et al.Diversity of forwarding paths in pocket switched networks[C]//Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement(IMC),2007:161-174.

[11] LINDGREN A,DORIA A,SCHEIEN O.Probabilistic routing in intermit tently connected networks[C]//LNCS3126.Berlin:Springer,2004:239-254.

[12] ABDELKADER T,NAIK K,NAYAK A.SGBR:a routing protocol for delay tolerant networks using social grouping[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12):472-481.

[13] SCOTT J,GASS R,CROWCROFT J,et al.A CRAWDAD data set cambridge/haggle[EB/OL].[2009-05-29].http://crawdad.org/keyword-DTN.html.

(责任编辑 张 镅)

Friend community-based routing algorithm in delay tolerant networks

CAO Cheng, GUO Qingwei, WANG Qingshan, XIA Maojin, WANG Lifang

(School of Mathematics, Hefei University of Technology, Hefei 230009, China)

Due to the intermittent and uncertain network connectivity in delay tolerant networks(DTNs), the traditional routing algorithms are not suitable for DTNs. In this paper, according to the history information of node contacting with communities, the friend community of nodes is defined, and a friend community-based routing algorithm(FCR) is proposed. In FCR, the source node firstly selects the access point(AP) of its friend community, and then the AP of the friend community of the source node selects the node which has contacted with the AP of the friend community of the destination node most as the relay node to forward the packet to the AP of the friend community of the destination node efficiently. Finally, the AP of the friend community of the destination node forwards the packet to the destination node directly. The simulation results show that compared with Epidemic, Label and SGBR routing algorithms, the proposed routing algorithm greatly reduces the copy numbers under the premise of closing to the maximum delivery ratio obtained by Epidemic algorithm.

delay tolerant networks(DTNs); friend community; routing algorithm; copy number; delivery ratio

2015-05-29；

2015-11-02

曹 成(1990-),女,安徽宿州人,合肥工业大学硕士生;

郭清伟(1968-),男,安徽淮北人,博士,合肥工业大学副教授,硕士生导师;

10.3969/j.issn.1003-5060.2016.09.012

TP301.6

A

1003-5060(2016)09-1211-05

王青山(1975-),男,安徽合肥人,博士,合肥工业大学副教授,硕士生导师.