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

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

(青島大學 計算機科學技術學院,山東 青島 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.