机会网络中基于节点相似率的概率路由算法

崔建群,吴淑庆,常亚楠,黄东升

(华中师范大学 计算机学院，武汉 430079)

1 引 言

随着无线网络的快速发展，机会网络[1]成为了近几年来无线网络研究领域的热点之一.机会网络采用存储-携带-转发的模式进行消息的传输，不存在固定的端到端传输路径，不同于传统网络.在传统网络中，源节点和目的节点处于互不连通的状态时无法进行通信.而机会网络中，由于节点不停的进行移动，因此可以将信息携带到可以进行互相通信的范围，完成消息的传输.机会网络是为了解决实际自组织网络中，由于网络无法保持长时间连通的情况下的数据通信问题，可在没有固定路由的情况下实现消息的逐跳转发，最终将消息传输到目的节点.

目前机会网络的可应用场景也越来越多.例如，在灾难应急[2]，车载网络[3，4]以及星际网络[5]等领域都具有非常广阔的市场前景和应用价值.

机会网络中的节点普遍具有较高的移动性，而且机会网络具备连接间歇性，网络延迟大等特点，因此寻求合适的中继节点将消息准确快速的投递到目的节点，是路由算法中最迫切关注的问题.传统的基于历史预测策略的概率路由(Probabilistic routing Protocol using history of encounters & transitivity,Prophet)[6]算法，没有考虑节点的相遇持续时间，只是利用节点相遇频率作为传递概率，这未免考虑不够周全，同时Prophet没有对成功传递的消息进行有效的控制，从而导致存在很多已经被成功投递的消息仍然存在网络中，使得网络开销过大，同时成功投递的消息仍然存在节点中，在节点缓存较小的情况下，这些成功投递的消息占用过多的节点缓存，导致节点无法接收新消息.本文将结合Prophet算法，分析其存在的问题，提出了一种基于节点相似率的概率路由算法(Probabilistic routing algorithm based on node similarity rate in opportunistic network，S-Prophet)算法，引入节点相似率进行消息传递概率的设计，并添加ACK确认机制删除成功投递的消息，以减轻节点缓存的负担，减少网络开销，从一定程度上弥补了Prophet算法概率计算不准确，以及节点缓存被成功投递的消息过多占用的问题.

2 相关工作

机会网络中经典算法有Direct Delivery[7]、Epidemic[8]以及Prophet等.

Direct Delivery(直接传输)算法的主要思想是，源节点只有与目的节点相遇的时候，才将消息进行转发给对方.Direct Delivery是一种单拷贝路由方式，其优点是简单直接，缺点是消息完全依赖源节点和目的节点的相互通信，若源节点始终无法遇到目的节点，则消息将永远无法送达目的节点.由于机会网络中节点是不断移动的，这将导致消息的延迟较大，消息容易在生存周期过期后仍无法传递到目的节点，从而导致较低的投递成功率.Epidemic算法则相反，通过提高副本传播的数量来提高数据成功率，不管相遇节点是否为目的节点，携带消息的节点都会将消息传递给与其相遇的所有节点，邻居节点继续通过这种方式进行下一步的传递.这种方式解决了Direct Delivery算法中依赖于源节点与目的节点相遇才将消息转发的问题，但是带来了另外一个问题，网络中存在大量冗余消息，很快便造成网络拥塞节点缓存负担过大，甚至有可能导致网络瘫痪.

Prophet算法是通过总结节点间历史相遇的规律来预测未来的传输路径，其主要工作在于提出了节点间成功传输消息概率的一个指标——投递预测值(deliver probability).与传染病路由算法(Epidemic)相比，当两个节点Va和Vb相遇时，不仅要交换两者的向量外，而且要交换投递预测值，只有在Va到目的节点的投递预测值大于Vb到目的节点的投递预测值时才将消息传递给节点Vb.本文将使用投递概率代表投递预测值这一概念.

投递概率的计算通常分3种情况讨论：更新、衰退以及传递性.当且仅当节点间相遇时，根据不同情况更新概率预测值.

更新：当节点Va和节点Vb相遇，根据公式(1)更新它们之间的投递概率，其中Pinit∈[0,1]，是一个人为规定的常数，是节点间传输率的初始值.

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

(1)

衰减：若节点Va和节点Vb在某段时间内未相遇，那么他们再次相遇的概率将降低，其投递概率的值按照公式(2)来进行计算：

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

(2)

公式中的γ是衰减参数，k则是表示从最后一次相遇到当前时间所经历的时间块的个数，γ∈[0,1]是常数.

传递性：节点概率的传递性是指不但节点Va经常遇到节点Vb，而且节点Vb也能经常遇到节点Vc，那节点Vc可能是转发消息到达目标节点Va的比较好的中转节点.节点间的概率传递性计算如公式(3)所示，其中β∈[0,1]是常数，它的大小是衡量传递性对投递预测概率的影响的一个重要指标.

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

(3)

通过总结节点间历史相遇的规律来预测未来的传输路径，通过计算投递概率，选取概率大的节点作为中继节点，一定程度上避免了Epidemic算法在选择中继节点的盲目性.但Prophet算法没有考虑节点的相遇持续时间，只是利用节点相遇频率作为传递概率，这未免考虑不够周全.同时，Prophet算法没有对成功传递的消息进行有效的控制，从而导致存在很多已经被成功投递的消息仍然存在网络中，使得网络开销过大，同时成功投递的消息仍然存在节点中，在节点缓存较小的情况下，这些成功投递的消息占用过多的节点缓存，导致节点无法接收新消息.

近年来，对于Prophet算法的改进有很多种形式.段宗涛[9]等提出概率路由中基于连接时间的机会转发算法，该算法考虑了相遇持续时间，在设计节点投递概率时增加了节点间连接时间占空比的影响因素，并未讨论缓存管理对投递率的影响.张峰[10]等针对上述问题进一步研究，在节点投递概率计算部分引入相遇持续时间重新设计概率计算公式，在选择中继节点时，虽然考虑了节点缓存对投递概率的影响，但是没有对已经成功投递的消息进行删除，未能从根本上解决当节点缓存被占用过大时，无法有效转发消息的问题.马慧[11]等提出基于节点的历史吞吐率的 Prophet 路由策略，在消息传递的过程中，在与目标节点相遇概率相同的节点中选择吞吐率较大的节点作为中继节点.虽然该算法考虑了消息传递过程中节点的吞吐率问题，但是在计算吞吐率的时候未能考虑到时间片对吞吐率的影响，因此在消息投递率上并未有明显提高.

本文在此基础上，提出了一种基于节点相似率的概率路由算法.在计算消息转发概率时考虑了节点历史相遇情况，引入了节点相似率的定义.由于在预估两个节点的投递概率的时候，Prophet算法中使用的参数Pinit是固定的，不能真实反映两个节点之间的动态变化关系，本文将使用节点相似率来对概率公式(1)中的参数Pinit进行设计，关于节点相似率的定义将在3.2节进行阐述.同时，使用节点相遇持续时间对衰减公式(2)中γk的参数k进行重新设计，为了减少传输成功的消息副本对网络资源的占用，本文采用了ACK删除机制，来保证及时清除已经传输成功的消息副本，然后使用ONE仿真平台进行实验，对比改进前后算法之间的性能.

3 机会网络中基于节点相似率的概率路由算法

3.1 基于节点相似率的概率路由算法S-Prophet

定义1.节点相遇持续时间

节点相遇持续时间为两个节点之间建立连接后进行通信所持续的时间，在机会网络中由于节点是移动的，因此造成节点之间每次相遇后进行通信所持续时间可能不同，在本文中，统计每个节点与其他节点之间建立连接通信的次数，以及总相遇持续时间，如图1所示.

假设节点Va与节点Vb总共建立连接n次，则它们之间的总相遇持续时间为:

T(a,b)=T1+T2+…+Tn-1

(4)

(5)

其中，T为时间间隔周期，T(a,b)表示节点Va和节点Vb总的相遇持续时间.

图1 节点相遇持续时间统计Fig.1 Node encounter duration statistics

定义2.节点的相似率

节点Va和节点Vb的相似率是指节点Va与节点Vb拥有的共同相遇节点个数与它们两个节点分别相遇的节点总数的比值.令集合Na={Vc|na,c≠0,1≤c≤n}表示节点Va在时间间隔周期T内所遇到的相遇节点集合，其中na,c表示节点Va与节点Vc的相遇次数，其初始值为0，每当节点Va与节点Vc相遇，则次数加1.同理集合Nb表示节点Vb在时间间隔周期T内的相遇节点集合.当统计的时间超过时间间隔T则会将原先的集合清空并重新开始统计，节点Va与节点Vb的相似率计算方法见公式(6)：

(6)

本文使用公式(7)作为两个节点之间的传输概率公式，不再使用公式(1).

图2 节点相似率的统计Fig.2 Statistics of node similarity rate

(7)

3.2 消息转发策略

接下来我们将介绍S-Prophet路由算法的消息转发步骤以及消息转发流程.

消息转发流程，如图3所示.

步骤1.在携带消息的节点Va遇到节点Vb时，首先要判断Vb是否为目的节点，是则转步骤4，否则转步骤2.

图3 基于节点相似率的概率路由算法消息转发流程Fig.3 Probability routing algorithm based on node similarity rate message forwarding process

步骤2.计算节点Va遇到节点Vb同目的节点之间的相遇概率.

步骤3.要判断节点Vb和目的节点的概率P(Vb)是否大于节点Va和目的节点的概率P(Va)，是则转步骤4，否则结束.

步骤4.将消息转发给节点Vb，结束.

表1 S-Prophet算法Table 1 S-Prophet algorithm

表1中算法第1行表示任意两个节点Va与Vb相遇并且建立连接，算法第2行，记录节点Va与节点Vb相遇的开始时间，算法3～7行进行判断，如果节点Va与Vb的相遇时间间隔大于设定的时间周期阈值T，则将Va的相遇节点列表清空，否则将该相遇节点添加到相遇节点列表中.因为本文只记录时间周期T内的相遇节点信息.算法第8行，记录节点Va与Vb断开连接的时间.算法第12行，统计集合Na和Nb中节点相遇持续时间.算法第13行，计算集合中节点相似率.算法第14行，根据节点相似率来进行节点投递率的计算，在计算之前会根据节点相遇持续时间先更新节点衰减概率.算法第15行，计算节点传递概率.算法第17～21行，遍历节点转发列表，根据节点传递概率将消息转发给比当前节点概率大的节点.由于本算法需要进行节点相遇持续时间的统计以及节点相似率计算，因此本算法时间主要耗费在11～16行，假设共有n个节点，则S-Prophet算法的时间复杂度为O(n2).

3.3 ACK删除机制

为了减少冗余副本在网络长时间保留造成节点缓存占用过多的不良影响，降低网络开销，本文将使用ACK删除机制来删除已经成功传递的消息副本.给每个节点设置一个ACK列表，当消息成功传输到目的节点时，该消息就被加入到ACK列表中，当两个节点相遇时，交换它们的ACK列表，然后从缓存中删除对应的消息.具体算法如表2所示，算法第1～3行表示，当消息成功投递之后，判断消息是否已经到达目的节点，如果消息到达目的节点，则将消息添加到ackMessage列表中.算法4～9行表示当任意两个节点Va与节点Vb相遇，首先互相交换其ackMessage列表中的信息，然后删除ackMessage列表中已经被成功投递到目的节点的消息.假设ackMessage列表中的消息共有n个，则本文的ACK删除机制时间复杂度为O(n).

表2 ACK删除机制Table 2 ACK deletion mechanism

4 仿真实验及结果分析

4.1 仿真的参数设置

本文的所有实验都是采用机会网络环境仿真平台ONE(Opportunistic Network Environment)来进行，本文对经典路由算法Epidemic、Prophet以及本文算法S-Prophet利用ONE仿真平台分别从节点缓存空间、消息生存周期、仿真时间、消息产生间隔4个不同角度对算法性能的影响进行比较分析，主要将消息投递率、传输延迟、平均跳数、网络开销作为路由算法的衡量指标，表3为本文仿真时设置的具体参数.

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

4.2 仿真结果分析

4.2.1 节点缓存对算法性能的影响

图4是3种算法的路由性能随着节点缓存空间的变化情况，从图中可以看出本文提出的S-Prophet路由算法在投递率、网络开销和平均跳数及传输延迟等方面都取得了较好的仿真结果，从而证实了考虑节点间相似率在路由选择方面发挥的主观作用.图4(a)的仿真结果表明，当节点缓存为2MB时，S-Prophet算法比Prophet算法提高了20%，比Epidemic算法提高了66%.当节点缓存为10MB时，S-Prophet算法比Prophet算法提高了58%，比Epidemic算法提高了48%.随着缓存空间的增加，Epidemic、Prophet、S-Prophet算法的消息投递率一直在持续增长，由于缓存空间的增加，可携带的消息也增多，从而提高了总的消息成功投递率.

图4 节点缓存对算法性能的影响Fig.4 Effect of node caching on algorithm performance

图4(b)中的仿真结果表明，当节点缓存从2MB变化到4MB时，3种算法的传输延迟都有降低，特别是S-Prophet算法有明显的降低，这是因为在缓存为2MB时，S-Prophet需要统计节点的相遇记录用于计算节点相似率，会因此占用一部分节点缓存，从而导致消息传输延迟会比较高.当节点缓存从4MB开始增加到10MB的过程中，S-Prophet算法传输延迟逐渐增加，但仍然比Epidemic、Prophet要低，这是因为在S-Prophet算法中利用了节点相似率改进了两个节点间传输概率更合理的决策出下一跳中继节点.

图4(c)的仿真结果表明，S-Prophet路由算法在网络开销方面表现最优，S-Prophet比Epidemic要小83%～85%，比Prophet要小64%～81%，这是因为在S-Prophet算法中不仅增加了节点相似率作为节点传输概率的影响因素，而且增加了ACK删除机制，有效的减少了网络中冗余副本的数量，从而降低了网络开销.

从图4(d)中可以看出，当缓存空间加大时，消息在网络中的平均传输跳数会随此降低，这是因为节点可存放的消息数量增多.对于Epidemic越有利，对S-Prophet和Prophet算法的平均跳数影响并不大.其中S-Prophet算法始终维持在2～3跳之间，而Prophet算法始终维持在3～4跳之间.跳数越少说明路由算法更有效，从图中可以直观看出S-Prophet算法性能略优于Prophet，因为S-Prophet在选择下一跳的指标上利用到了节点相似率这一因素.

4.2.2 消息生存周期对算法性能的影响

图5描述了各个算法在不同消息生存周期下的路由表现.从图5(a)中可以看出，随着消息生存周期从100min增加

图5 消息生存周期对算法性能的影响Fig.5 Effect of message lifetime on algorithm performance

到300min的过程中，Epidemic算法和Prophet算法的投递率在降低，这是因为当节点缓存空间较小的情况下，如果消息生存周期比较高，会使大量已经成功投递的消息仍然存在网络中，这对于Epidemic和Prophet算法来说是非常不利的，Epidemic和Prophet算法并没有采取有效的措施来控制消息冗余数量，不可避免的产生更多的消息副本，而S-Prophet算法的投递率在逐渐上升，且S-Prophet算法的投递率在消息生存周期大于150min之后一直比Prophet和Epidemic算法的投递率高，这是因为在S-Prophet算法中有ACK删除机制，一定程度上减少了冗余副本的数量，从而提高消息投递率.此外，从图5可以看出，随着消息生存周期的增加，S-Prophet算法仍然保持了它在传输延迟、平均跳数、网络开销上的优势，均低于Prophet算法和Epidemic算法.

4.2.3 仿真时间对算法性能的影响

图6描述了各个算法在不同仿真时间下的路由表现.从图6(a)中可以看到，在随着仿真时间的增多，S-Peophet、Prophet以及Epidemic算法的投递率也在逐渐的提高，但是当仿真时间为8h的时候，S-Prophet算法已经达到饱和状态，本文所提出的S-Prophet算法相较于Epidemic算法和Prophet算法更为稳定，且S-Prophet算法的投递率一直高于其他两种算法.在仿真时间为6h的时候，S-Prophet算法比Epidemic算法的投递率高53.2%，比Prophet算法的投递率高65%，当仿真时间达到8h的时候，S-Prophet算法比Epidemic算法投递率高53.3%，比Prophet算法投递率高74%.

图6 仿真时间对算法性能的影响Fig.6 Influence of simulation time on algorithm performance

从图6(b)中可以看出，当仿真时间在6h时候，S-Prophet算法的传输延迟介于Prophet与Epidemic之间，当仿真时间从10h开始，S-Prophet算法的传输延迟就一直低于Prophet与Epidemic，这是由于随着仿真时间的增加，S-Prophet算法收集到的节点信息越来越多，更能够准确的预估下一跳节点，将消息准确送达目的地.

从图6(c)中可以看出，随着仿真时间的增加，S-Prophet算法的网络开销越来越低，且均低于25，而Prophet算法和Epidemic算法两者都比较高，虽然Prophet算法网络开销比Epidemic的要稍微低一些，但是由于Prophet算法没有进行消息冗余控制，因而S-Prophet算法在路由性能的表现上更具优势.

从图6(d)中可以看出，随着仿真时间的增S-Prophet算法的平均跳数均在3以下，而Prophet算法与Epidemic算法的平均跳数均在3～4之间，平均跳数越少，说明路由性能越好.

4.2.4 消息产生间隔对算法性能的影响

图7比较了改变消息产生间隔时各个算法的4项评估指标.在不考虑消息传输延迟的情况下，从图7(a)中可以看出，S-Prophet算法的路由性能是最优的，且稳定的保持较高的消息投递率，而Epidemic和Prophet算法投递率都比较低，且两者都比较接近.S-Prophet算法的投递率比Epidemic的高53%～57%，比Prophet的高62%～67%.从图7(b)中可以看出，在传输延迟方面，S-Prophet算法与Prophet相比，在消息产生间隔为60s～70s的过程中两者较为接近，当消息产生间隔为75s时，S-Prophet的传输延迟比Prophet要低，而此时Prophet的传输延迟比Epidemic高，就图7(b)图而言，总体来说S-Prophet的传输延迟始终比Epidemic要低.

图7 消息产生间隔对算法性能的影响Fig.7 Influence of message generation interval on algorithm performance

从图7(c)和图7(d)中可以看出，S-Prophet算法的性能更加稳定，网络开销和平均跳数一直保持较低水平，其网络开销只有Epidemic的17%、Prophet的19%.导致这些路由性能差异的关键原因是，在消息生存时间间隔较小的情况下，整个网络会产生较多的消息，由于缺乏控制消息冗余的机制和受限的缓存空间，Epidemic会丢弃大量的消息包，Prophet利用节点间传输概率来筛选更有的中继节点，一定程度上比Epidemic的盲目性要好一些，因而路由性能上要由于Epidemic，但仍然要弱于S-Prophet.因为S-Prophet借助节点相似率来设计节点传输概率，从而筛选出更好的中继节点，以此获得了更好的路由性能，并且通过ACK删除机制，有效避免过多的冗余消息副本，从而提高网络资源的利用率.

5 结束语

本文结合Prophet路由算法的优势，针对其中存在的问题，提出了一种考虑相遇节点历史连接情况以及ACK确认机制的路由算法，并进行了仿真实验.实验证明，相对于传统的Prophet算法和Epidemic算法而言，本文提出的S-Prophet算法在路由性能上更好一些，但仍然存在一些不足的地方，比如整体而言，传输延迟均偏大，在这方面仍有较大的改进空间，这是下一步研究工作的重点.