基于局部位置信息和消息投递度的受控传染路由算法

陆 芳,李建波,宋有美,王夫沭

(青岛大学 计算机科学技术学院,山东 青岛 266071)

1 引 言

容延/容断网络(Delay/Disruption Tolerant networks,DTN)是一种新型的网络体系结构[1],其概念起源于星际网络(InterPlaNetary,IPN)[2],主要目的是解决不同星球之间的数据通信问题.DTN最初主要应用在军事战场[3]和抢险救灾,现在被广泛应用于一些陆地上的挑战性网络,如移动社交网络[4,5]、车载自组网络[6,7]、湖泊环境下的水声传感器网[8]等.这些网络与星际网络一样具有非常鲜明地特点:节点密度稀疏,频繁的网络拓扑结构变化,资源有限,间断性连接[9],高延时,移动性,高误码率,异构互连等.因此,在源节点和目的节点之间始终不存在一条端到端的通路[10].在这种限制下,传统的基于TCP/IP协议很难取得高效的路由算法,所以,DTN面临很多新的困难和挑战,为了解决网络的间断性连接,DTN路由采用存储-携带-转发(store-carry and forward)的路由模式.

在DTN中,只转发一个消息副本结果往往很难令人满意.如First Contact[11],First Contact算法是整个网络中只存在每个消息的单一副本,源节点携带某个消息在做无规律的运动,直到与目的节点相遇.因此First Contact算法的表现结果不理想.然而通过增加消息副本的数量来提高与目的节点的相遇机会,虽然可以有效地改善消息投递率,但同时不可避免地增加了资源消耗和网络负载,最具有代表性的算法有Epidemic[12].还有一些典型的路由算法,例如LC-Epidemic算法[13],该算法是多拷贝的路由算法,节点利用余弦定理选择张角最大的两个一跳邻居节点进行复制,提高了消息的传输率,但是单纯地只依靠节点的张角大小做出路由决策,往往会导致很高的网络负载和投递时延.因此,如何选择较少但更优的中继节点来复制消息副本成为解决DTN路由的关键问题.

目前,很多的路由算法在实现消息的受控传染时,在消息源节点和中继节点上运用相同的路由策略.然而消息源节点和中继节点往往承担着不同的责任,一方面,消息源节点承担着目的节点最终能接收到消息的责任,而中继节点不需要确保消息的成功投递,只承担着存储、携带和转发消息的任务.另一方面,相比于中继节点,消息源节点拥有更多关于目的节点的信息.所以,在消息源节点和中继节点上采取不同的路由策略具有更加实用意义.

基于上述考虑,为了控制消息冗余,减少网络资源的消耗和有效提高缓存空间的利用,我们在消息源节点和中继节点采用不同的路由方案,在消息源节点上,我们利用局部位置信息去控制消息的扩散范围,在中继节点上,我们综合利用各种效用指标去挑选更优的下一跳节点.最后,我们提出了基于局部位置信息和消息投递度的受控传染路由算法(LPDR).

本文的剩余部分作如下安排:在第二部分,详细介绍LPDR路由算法;在第三部分,我们将LPDR与当前流行的DTN路由算法进行路由性能的比较和分析;最后第四部分得出我们的结论.

2 路由算法设计

在容迟网络中,当节点的移动范围被局限在一个局部区域,例如,在一所单位内,大多数职员更趋向于长期滞留在某一栋大楼内,在一所大学内,大多数老师和学生更趋向于待在同一座教学楼内.在这样情况下,节点的局部位置信息更加可靠.消息源节点可以选择更远距离的邻居节点作为中继节点,将消息传递出去,扩大消息的传输范围,提高消息的利用效率.

图1 LPDR流程图Fig.1 LPDR flowchart

此外,消息源节点和中继节点在通信过程中承担着不同的责任,通过在消息源节点和中继节点上运用不同的策略,进一步限制了消息源节点和中继节点携带消息的传染能力,从而更好地控制消息冗余.而且,高效的路由算法需要具备较高的消息投递率,平均时延和负载率应该控制在一个可接受的范围内等.为了达到这一目标,基于上述的研究分析,我们提出了一种基于局部位置信息和消息投递度的受控传染路由算法(LPDR).图1描述了LPDR算法的流程图.LPDR路由基于如下假设:

● 网络中的节点可以通过GPS系统和相关的定位算法获得自身当前的位置信息.

● 当节点互相进入通信范围时,会以广播的方式在其一跳邻居范围内扩散其位置信息.

● 节点在通信范围内与其他节点相遇时,可以收集节点间相遇的信息.

2.1 消息源节点上的路由策略

提高路由性能的一种方法是增加副本的数量,增加消息副本虽然可以有效地改善投递率,但在实际情况下,网络中的节点缓存和能量等都是有限的,无限制的增加消息副本的数量,会降低路由的性能.为了提高单个消息副本的利用率,源节点会有目标的把消息传递给中继节点.源节点尽可能选取可以形成最大张角(图2)的一跳邻居节点来复制消息,以此来增加所投消息在网络中的覆盖范围,获得更广的分布,因此我们用到了LC-Epidemic算法[13]中的根据邻居节点位置信息来选取最大张角的知识.

如图3所示,假设当前消息源节点Na可用的一跳邻居节点数量不超过3个时,这意味着源节点与其他节点之间的接触机会不多,此时我们应该向所有的邻居节点都传递消息的副本,而不先考虑邻居节点是否适合作为下一跳节点,当消息源节点可用邻居节点数目大于2个时,选择与当前节点形成张角最大的两个邻居节点作为下一跳节点,以实现消息副本的快速扩散.

图2 节点Na与3个邻居节点之间夹角关系Fig.2 Relationship between Na and 3 neighbor nodes

我们利用公式(1)、公式(2)计算出节点间夹角的大小.

(1)

β(b,c)=arccos (cosβ(b,c))

(2)

其中,Vab代表节点Na和Nb所确定的向量,|Vab|代表节点Na和Nb的距离.

2.2 消息中继节点上的路由策略

消息中继节点上的路由策略用到了Prophet[14]的知识,我们利用(3)来计算节点间相遇的可能性,用式(4)的衰减函数来更新节点间相遇的可能性,用式(5)的传递性来更新节点间相遇的可能性.

P(a,b)=P(a,b)old+(1-P(a,b)old)·Pinit

(3)

P(a,b)=P(a,b)old·γk

(4)

P(a,c)=P(a,c)old+(1-P(a,c)old)·P(a,b)·P(b,c)·β

(5)

图3 节点Na与小于3个邻居节点之间的传递关系Fig.3 Relationship between Na and less than 3 neighbor nodes

Prophet算法是对Epidemic算法的一种改进,中继节点根据与目的节点的相遇概率来决定是否转发消息,实现了消息的有效转发.但是Prophet算法没有考虑节点之间的连接强度和投递的可能性,这显然是不合理的.下面我们借鉴Prophet优点,结合节点间接触频率,提出了一种更加全面的方法.

定义1.节点间的投递概率

假设节点a是当前节点,节点a在向目的节点d发送消息的过程中与节点b相遇,我们用公式(6)来更新节点间的投递概率,两个节点相遇次数越频繁,他们的相遇概率就越大,节点间投递可能性就越大,节点间的投递概率公式如下:

(6)

定义2.消息投递度

我们定义了消息投递度这一度量标准,去评估邻居节点是否可以作为下一跳中继节点.如当节点a与节点b相遇,我们可以计算节点a和b的消息投递率,当Dm(b)>Dm(a)时,节点b被认为最有可能与目的节点相遇,成功投递消息的可能性很大,节点b是更好的下一跳节点.我们定义的消息投递度包含两部分内容,一是当前节点与目的节点的相遇概率,二是当前节点与其他节点的投递概率.具体公式如下:

Dm=∂P(a,d)+(1-∂)Fn(a,b)

(7)

其中,∂∈[0,1]为加权系数,P(a,d)代表节点a和目的节点d的投递概率,Fn(a,b)代表节点a和节点b之间的投递概率.

定义3.节点相似系数

在某些应用场景中,例如校园、公司等某个局部小范围内,节点互相之间的相遇次数和概率都比较高,节点之间的移动范围和所遇到的节点大部分重叠,在这种情况下,我们就称节点是相似的,在这里我们定义节点相似系数来判断两个节点是否相似.我们还定义了节点相似系数的阈值τ,用来表示节点相似的门限,当节点相似系数超过阈值τ时,则称这两个节点是相似的,否则就称这两个节点是不相似的.节点相似系数具体公式如下:

(8)

图4 消息Ma在源节点Na上的路由决策Fig.4 Routing strategy of Ma on source nodeNa

我们给出公式(8)相应的推理过程.

1)推理

常用的计算节点之间相似的方法是利用节点的共有邻居节点来计算相似度.我们用N(vi)和N(vj)分别表示节点vi和vj的邻居节点集合,则节点的相似度可以定义为:

σ(vi,vj)=|N(vi)∩N(vj)|

(9)

图5 图和其对应的邻接矩阵Fig.5 Graph and its corresponding adjacency matrix

在这里我们运用另一种计算节点vi和vj之间相似度的方法是,比较σ(vi,vj)和σ(vi,vj)的期望值.对于节点vi和vj,邻居节点集数分别为ni和nj,所以期望值就是ninj/N,其中N是节点数.这是因为每个节点成为vi的邻居节点的概率是ni/N,并且vj的邻居节点数量为nj,所以期望值是ninj/N.我们将节点与其他节点的关系用如图5(a)来表示,其相对应的邻接矩阵5(b)表示,邻接矩阵通常可以表示为:

(10)

所以,我们可以进一步将σ(vi,vj)改写为:σ(vi,vj)=|N(vi)∩N(vj)|=∑kAi,kAj,k,因此,相似度的度量方法如下表示:

(11)

(12)

我们的相似系数来源于上面的推导,它的取值介于[-1,1]之间,我们定义了相似系数阈值τ,如果两个节点的相似系数超过阈值τ时,就说明这两个节点接触到的节点大部分相同,我们就称之为节点相似,否则就认为是不相似的.

算法2.消息Ma在中继节点Na上的路由策略Input: Na meets Nb Threshold parameter:τoutput:1. d← destination node of Ma;2. ifNa finds the d3. relayMa to the d;4. DeleteMa from Na's buffer cache;5.else6. ifDmNa

消息在中继节点上的路由策略不同于在消息源节点上的路由策略,中继节点携带的消息副本的传染能力受到严格的控制,并且中继节点利用式(7)计算节点的消息投递度,去选择投递度更高的节点,作为下一跳节点,以此来提高消息的投递度.但是在某些场景中,例如校园、教室等小范围内,节点之间会频繁的相遇,假设当前中继节点为Na,携带的消息为Mi,当节点Na遇到消息投递度比它高的节点时,节点Na就将消息Mi复制给这个节点,如果所有节点都比当前节点的消息投递度高,那么在这个小范围内,会存在大量的多余消息Mi,增加了网络的负载,降低了网络的性能.然而这种范围内的节点会存在相似的地方,例如节点之间的活动范围和接触到的节点等,而这两节点都携带消息Mi,只会更加浪费节点的缓存,进而导致网络拥塞.在这样情况下,是没有必要都携带消息副本Mi,我们只让消息投递度更大的携带消息副本.从而在保证高投递率前提下,进一步降低了网络的负载.具体的中继节点上的路由策略在算法2中(见图6).

算法2-4行是当前中继节点Na如果遇到目的节点,就把消息直接传递给目的节点,然后删除中继节点中的消息.算法6-7行中,当前消息中继节点Na如果遇到消息投递度比自己大的邻居节点Nb时,就把消息传递给邻居节点Nb.算法8-9行是用来判断Na与Nb是否相似,如果两个节点是相似的,就把节点Na中消息Ma删除,只在Nb中留有消息.

3 路由算法性能分析

本节中,我们使用The ONE(Opportunity Networking Environment)[15]模拟器来进行仿真实验,基于Random Waypoint节点移动模型,对LPDR、LC-Epidemic、Prophet和Epidemic进行仿真实验.研究分析这些路由算法在节点缓存空间、消息生存周期不同场景下的路由性能表现.具体仿真参数如表1所示.

表1 仿真参数设置Table 1 Simulation parameter setting

在节点缓存空间、消息生存周期这两个不同的仿真场景,采取的测评指标有:消息投递率、网络负载率、平均时延、平均跳数.评测指标的定义如下:

1)消息投递率(message delivery_ratio)

2)网络负载率(overhead_ratio)

overhead_ratio

3)平均时延(average_latency)

4)平均跳数(average hop_count)

average hop count

3.1 不同缓存空间下的性能表现

图7描述了在改变节点缓存空间大小时四种算法路由性能的仿真结果.从中可以看出LPDR在投递率、负载率、平均时延、平均跳数上都取得了一定优势,这证明了我们提出的路由算法可以显著提高网络的传输性能.

Epidemic没有采取任何优化策略,只是单纯地将消息洪泛给每个相遇的节点.在网络资源充足的情况下,增加副本数量能改善路由算法的表现.因为Epidemic是基于洪泛策略的路由算法,因而他不可避免地增加了消息副本的数量,增加节点负担.当缓存空间较小时,它的网络负载会明显增大.如图7(b)所示,随着节点缓存的增加,进一步减少了消息的丢包,它的网络负载在逐渐下降.此外,如图7(c)和图7(d)所示,由于Epidemic没有评估中继节点性能的优劣,其下一跳节点选择的准确性较差,这导致消息需要经过更多的跳数才能到达目的节点,因而其平均跳数最高,这也明显增加了消息的传递时延.

图7 不同缓存空间下的路由性能Fig.7 Routing performance under different buffer size

LC-Epidemic是基于节点位置信息的受控传染路由算法.节点每次只是简单的将消息复制给张角最大的两个一跳邻居节点,而不进一步考虑节点的好坏,如图7(a)和图7(d)所示,因而其消息投递率较差,平均跳数较高.虽然是受控传染路由算法,LC-Epidemic也会增加消息的副本,在缓存资源紧张时,会降低路由的性能.LC-Epidemic需要计算节点对之间的张角大小来选择下一跳节点,这极大地增加了消息传输的平均时延.当节点的缓存空间增大时,其平均时延也随之增大.

Prophet是通过捕获节点间相遇的历史信息,并利用节点的传递性预测节点间的相遇概率,将消息复制给相遇概率值更高的节点,以此来控制消息冗余,取得了较好的路由性能.其更少的平均跳数说明其路由选择的有效性更高,在一定程度上降低了消息传输的成本.但只利用节点间的相遇历史信息仍然会导致有较高的网络负载率.

我们提出的LPDR既利用节点的局部位置信息,又考虑到节点不同的性能,并进一步限制中继节点携带消息的复制能力,在一定程度上控制了消息的冗余.因此缓存空间低于30MB时,LPDR取得了最高的消息投递率,其网络负载只有不到LC-Epidemic的35%、Epidemic的20%和Prophet的15%.这充分表明我们的路由算法可以极大地降低网络负载.与此同时,LPDR的平均跳数最少,说明我们的路由算法更加高效.

3.2 不同消息生存周期下的性能表现

图8描述了在不同消息生存时间下四种算法路由性能的仿真结果.从中可以看出,LPDR在投递率、负载率、平均跳数上仍然能够取得一定的优势.这再次证明了我们提出的路由算法可以显著提高网络的传输性能.

随着消息生存周期的增大,四种算法的投递率都有所提高,但是Epidemic和LC-Epidemic的投递率要高于Prophet,其原因在于当缓存资源不是瓶颈时,Epidemic和LC-Epidemic能够有效利用快速增加消息并行性的洪泛策略,及时完成消息的投递.从本质上看,Prophet是多拷贝的路由策略,但是不同于Epidemic,他利用节点间的相遇概率来选择下一跳中继节点,而不是盲目的洪泛,一定程度上控制了消息冗余,从图8(b)可以看出,Prophet的负载率远远低于Epidemic的负载率,并保持在一个较低的水平,这表明路由选择更加高效.Epidemic没有采取任何优化策略,只是盲目的洪泛消息副本,其路由选择的准确性较低,因此其平均时延和平均跳数最高.相比于Epidemic,LC-Epidemic通过选择张角最大的两个邻居节点来进行消息复制,明显提高了下一跳节点选择的准确性,因而其平均时延和平均跳数比Epidemic的低.

与其他三种算法不同,LPDR既能将其网络负载、平均时延和平均跳数维持在一个很低的水平,也能让其消息投递率保持在最高的水平.导致这种不同表现的原因是,LPDR进一步限制了中继节点上消息的复制能力,因此,即使消息的生存周期在不断增加,LPDR仍能避免生成过多的冗余消息.

图8 不同消息生存周期下的路由性能Fig.8 Routing performance under different TTL(min)

4 总结与展望

利用节点位置信息进行下一跳节点选择,在一定程度上可以控制消息副本的数量,降低网络负载,但是单纯地只依靠节点位置信息作出路由决策往往较难取得令人满意的消息投递率.除此之外,消息源节点和中继节点承担着不同的责任,在这种情况下,在消息的源节点和中继节点上采取不同的路由策略,从而可以更好地提高路由性能.在本文中,结合上面的思想,我们提出了一种基于局部位置信息和消息投递率的受控传染路由算法(LPDR),该算法在消息源节点和中继节点上采取不同的策略.在消息源节点上运用局部位置信息,利用节点的局部位置信息来控制消息的扩散范围.在中继节点上,综合利用多种效用信息筛选出最优的节点进行消息复制,从而更好地控制了消息的冗余.大量的仿真结果表明,LPDR是一种高效的路由算法,与LC-Epidemic、Epidemic、Prophet相比能达到更高的消息投递率、更低的跳数和网络负载.在未来的工作中,在保证高投递率的前提下对LPDR的时延进一步缩小,进一步完善LPDR.

：

[1] Soelistijianto B,Howarth M P.Transfer reliability and congestion control strategies in opportunistic networks:a survey [J].IEEE Communications Surveys & Tutorials,2014,16(1):538-555.

[2] Chen Heng-yi,Zheng Zeng-wei.A review of the research on the protocol of interplanetary network communication [J].Application Research of Computers,2011,28(2):407-412.

[3] Tauil M,kant L,McAuley A,et al.Capacity estimation and waveform assignment in military network[C].MILCOM 2012,Military Communications Conference.Orlando,FL:IEEE Press,2012:1-6.

[4] Mao Zhi-fei,Jiang Yu-ming,Min Ge-yong,et al.Mobile social networks:design requirements,architecture,and State-of-the-art technology [J].Computer Communications,2016,100(1):1-19.

[5] Nikolaos V,Kun Y.Mobile social networks:architecture,social properties,and key research challenges [J].IEEE Communications Surveys & Tutorials,2013,15(3):1136-1149.

[6] Zhang L,Peng L,Zhang Y,et al.Urban bus transport network optimization from complex network[C].2012 Proceedings of International Conference on Modelling,Identification & Control (ICMIC),Wuhan,Hubei,China:IEEE Press,2012:1159-1164.

[7] VNGJ Soares,JJPC Rodrigues,F Farahmand.GeoSpray:A geographic routing protocol for vehicular delay-tolerant networks [J].Information Fusion,2014,15(1):102-113.

[8] Guo Z,Wang B,Cui J H.Generic prediction assisted single-copy routing in underwater delay tolerant sensor networks [J].Ad Hoc Networks,2013,11(3):1136-1149.

[9] Kang Zong-xu,Lei Wen-hu,Li Guang-zhi,et al.Data transmission and routing in intermittently connected networks [J].Communications Technology,2016,49(5):593-598.

[10] Philip G,Vattier N,Jorg O.Fragmentation algorithms for DTN links [J].Computer Communications,2013,36(3):279-290.

[11] Cao Yue,Sun Zhi-li.Routing in delay/disruption tolerant networks:a taxonomy,survey and challenges [J].IEEE Communications Surveys and Tutorials,2013,15(2):654-677.

[12] Ren Zhi,Peng Shuang,Chen Hong,et al.Epidemic routing based on adaptive compression of vectors:efficient low-delay routing for opportunistic networks based on adaptive compression of vectors [J].International Journal of Communication Systems,2015,28(3):560-573.

[13] Li Jian-bo,You Lei,Jiang Shan,et al.Controlled epidemic routing algorithm in DTN based on neighbor node location [J].Computer Engineering,2014,40(8):77-85.

[14] Payne,Allison Ann.A prophet of school-based delinquency prevention research [J].Criminology & Public Policy,2017,16(1):29-33.

[15] Ker,Nen A,Ott J,et al.The ONE simulator for DTN protocol evaluation[C].International Conference on Simulation TOOLS and Techniques for Communications,Networks and Systems,Simutools 2009,Rome,Italy,March.DBLP,2009:55.

附中文参考文献：

[2] 陈恒毅,郑增威.星际网络通信协议研究进展综述[J].计算机应用研究,2011,28(2):407-412.

[9] 康宗绪,雷文虎,李广志,等.间歇性连通网络数据传输与路由技术研究[J].通信技术,2016,49(5):593-598.

[13] 李建波,由 磊,姜 山,等.基于邻居节点位置信息的受控传染DTN路由算法 [J].计算机工程,2014,40(8):77-85.