機會網絡中考慮緩存的路由算法

摘 要：機會網絡是一種通過節點移動建立通信鏈路的無線自組織網絡，一般通過消息復制的路由策略傳遞信息。但該方式將導致鏈路中存在大量消息副本，對節點緩存形成巨大壓力，造成網絡擁塞。針對該情況，結合Prophet算法，充分考慮節點緩存對鏈路狀態及傳輸概率的影響，設計限制消息最大副本數量與及時刪除節點緩存中不必要數據包的緩存管理機制，同時在Prophet算法中考慮了緩存比因素。仿真結果表明，該算法可以有效提高消息投遞率，降低網絡消耗。

關鍵詞：機會網絡;Prophet算法;緩存區管理;擁塞控制

DOI：10. 11907/rjdk. 182515 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）007-0080-04

Buffer Aware Routing Algorithm for Opportunistic Network

CHEN Wei-jie

（School of Optical-Electrical and Computer Engineering，University of Shanghai for Science and Technology，Shanghai 200093，China）

Abstract：The opportunistic network is a wireless ad hoc network that establishes a communication link through node movement. Generally， the information is transmitted through a routing policy that uses message replication. This method results in a large number of message replicas in the link， which puts tremendous pressure on the node cache and causes network congestion. Aiming at this situation， combined with the Prophet algorithm， we fully considered the influence of the node cache on the link state and the transmission probability. Two mechanisms for buffer management are designed， including limiting the maximum number of copies of the message and deleting the node cache in time. The data packet is considered in the Prophet algorithm. The simulation results show that the algorithm can effectively improve the delivery rate of the message and reduce the network consumption.

Key Words：opportunistic network;Prophet algorithm;buffer management;congestion control

作者簡介：陳偉潔（1995-），女，上海理工大學光電信息與計算機工程學院碩士研究生，研究方向為無線網絡和機會路由。

0 引言

如何在不需要提前建立端到端鏈路的情況下，利用設備的移動性快速形成自組織網絡，達到在網絡中進行消息傳遞的目標，是目前無線自組織網絡研究中的熱點。在緊急情況下，經常會遇到原有鏈路被破壞，需要通過現有設備建立一條新鏈路的情況，如何在該情況下進行有效的數據傳輸是目前需要解決的一個難題。為此，研究人員結合MANET（Mobile and Ad Hoc Network）與DTN[1]（Delay-tolerant Network）的特點，提出機會網路（Opportunistic Network）的概念[2]。機會網絡是一種不需要源節點與目的節點之間存在一條完整鏈路，而是通過節點移動過程中形成的相遇機會建立通信的自組織網絡。機會網絡相對于傳統網絡表現出更好的適應性，更加符合自組織網絡的要求，因此近年來引起國內外研究者的廣泛關注，并開展了大量應用研究，如在災難發生的緊急狀況下構建自組織網絡[3]，以及可用于觀察海洋生物種群[4]與監察自然環境下放牧系統 [5]的移動自組織網絡等。由于機會網絡是以“存儲—攜帶—轉發”的路由機制模式開展工作的，在該模式下要求網絡提供節點的可靠性保證，節點在未選取好下一跳轉發節點時，中間節點不能丟棄數據[6-7]。當網絡中的大量數據需要被傳輸時，節點的緩存利用率較高，易造成網絡擁塞，影響數據正常傳輸。因此，在機會網絡中，擁塞控制是保證網絡穩定性與可靠性的關鍵因素。

機會網絡中針對擁塞控制情況有以下兩種解決方法：①限制消息副本數量，避免生成不必要的數據包。消息在鏈路中一般采用消息復制方式傳輸給下一跳節點，對于未對消息副本進行合理控制的路由算法而言，在消息傳輸過程中，網絡中會存在大量消息副本，因而極大地影響了網絡性能[7]。針對該問題，文獻[8]、[9]提出限制消息副本數量的路由機制，以減少因生成大量不必要數據包對網絡造成的壓力;②及時刪除不必要的數據包。當網絡中的數據包已傳輸成功或不需要傳輸時，數據包若還滯留在節點緩存中，易造成節點緩存溢出，不僅導致數據無法得到及時傳輸，更極大地浪費了網絡資源。因此，針對不必要的數據包，可以使用DLR、DL、DOA、DY等刪包方式進行處理[9-10]。

為避免出現網絡擁塞狀況，保證網絡即使在高吞吐量的環境中也能正常傳輸數據是本文的研究重點。Prophet（Probabilistic Routing Protocol Using History of Encounters and Transitivity）算法通過比較節點之間的相遇概率，選擇是否將消息轉發給中間節點。該工作機制可大幅減少網絡中的副本數量，但沒有完全考慮到消息副本數量對節點緩存的影響。本文結合Prophet算法特點，提出控制消息副本數量以及考慮節點剩余緩存以避免擁塞的機制，從而有效提高消息投遞率。

1 相關工作

機會網絡中的節點是具有移動性且不穩定的，源節點與目的節點之間不存在一條已連接好的端到端的路徑，即使在鏈路斷開的情況下，也可以實現消息的逐跳轉發，并成功傳輸消息。因此，其可以看成是具有一般DTN網絡特征的無線自組織網絡，更加符合自組織網絡的需求[11-12]。

目前，基本的機會路由算法可以分為兩大類[13]：基于復制的路由算法與基于效用的路由算法。基于復制的路由算法是通過復制消息副本傳輸數據，在網絡中形成多消息存儲的路由策略，典型路由算法有Epidemic算法等[9];基于效用的路由算法以一個效用值為衡量標準，為中間轉發節點的選取提供參考因素。本文討論的Prophet算法即是根據節點之間的轉發概率篩選節點，進行數據轉發[10]。

在基于復制與基于效用的經典算法中，未考慮到消息副本數量過多對節點緩存的影響，導致網路性能下降，因此具有一定局限性[11-12]。Prophet是一種基于概率轉發的路由算法，節點在選擇下一跳節點時會根據相遇概率傳輸消息，節點之間的概率在相遇時升高，分開時則隨著時間延長而降低。Prophet算法的工作機制是只要遇到比自己傳輸概率大的節點則會復制一個消息副本給對方。基于效用的轉發方式雖然在一定程度上控制了消息的轉發副本數，但還沒有減少不必要消息對節點緩存的影響。當節點接收新消息時，會判斷自己是否有足夠的緩存區，如果緩存區不夠，則根據消息在緩存區的時間長短刪除數據包，在緩存區中時間越長的數據包越容易被刪除。因此，需要設置一個消息的生存期時間以控制消息生命長短，以便于刪除不必要的數據包。

傳統Prophet算法是通過比較相遇節點與目的節點的概率值決定是否將消息傳輸給相遇節點，假設a、b兩點相遇，a、b兩節點的概率值通過式（1）進行更新。

[P（a，b）=P（a，b）old+（1-P（a，b）old）*Pinit] （1）

[P（a，b）=P（a，b）old*γk]? ? ? ? （2）

式中，[Pinit]是預先設置的兩節點之間的初始概率，γ是老化因子，γ∈[0，1]，k表示距離上一次更新的時間長度。

Prophet算法的概率還具有傳遞性，即a節點與b節點經常接觸，b節點與c節點也經常接觸，則節點b可作為節點a和節點c消息轉發的中間節點，節點a、b、c的傳遞概率可按照公式（3）進行更新。

[P（a，c）=P（a，c）old+（1-P（a，c）old）*P（a，b）*P（b，c）*β] （3）

式中，β是一個常數，β∈（0，1），其決定了消息經過中間節點傳遞后對整體數據傳輸成功概率的影響。

雖然Prophet算法中概率的傳遞性可以有效減少數據廣播引起的擁塞現象，但一旦擁塞現象發生，會極大地影響算法性能。如圖1所示，若節點a、b與節點b、c都可以經常保持連接，根據Prophet算法的傳遞性，b節點即可作為a、c節點傳輸鏈路上的中間節點，并保持較高的投遞率，但若b節點的緩存此時正處于擁塞狀態，a、c節點鏈路上的數據包則無法正常轉發。所以即使Prophet算法根據概率值的傳遞性選取了最好的中間轉發節點，但若未考慮到中間節點的緩存情況，則無法合理地發揮該算法優點。如果此時a節點將消息轉發給b節點，該消息則會溢出，否則a節點只能將消息保存在本地中，等待下一個合適節點進行轉發。

圖1 節點b在擁塞狀態下的鏈路

2 Prophet算法改進

雖然Prophet算法根據概率效用值選擇轉發節點的工作機制已在一定程度上減輕了網絡中的擁塞情況，但仍未考慮節點緩存對算法性能的影響。機會網絡是一個以“存儲—攜帶—轉發”模式工作的自組織網絡，一個節點如果處于鏈路中的關鍵位置，則其需要轉發的消息更多，而消息數量及大小與該節點緩存情況密切相關。如果節點緩存情況可以得到有效管理，則會提高消息傳輸的成功率。在網絡中，消息數量及大小都是隨機的，但節點緩存卻是固定的，只有對節點緩存情況進行有效控制，才能保證后續消息得到正常轉發[11]。

2.1 節點緩存比

本文不僅針對節點緩存提出了有效的管理機制，還添加了緩存比效用因素，即算法在基于相遇概率選擇轉發節點基礎上，同時考慮了節點緩存情況，選擇轉發成功率較高與緩存壓力較小的節點作為轉發節點。該方法能更加有效地避免擁塞現象產生，增加數據包投遞率。節點緩存比定義如下：

[R=i=1nmi*SiBtotal]? ? ? ? ? （4）

式中，[mi]表示消息數量，[Si]表示消息大小，[Btotal]表示節點緩存大小。

2.2 節點緩存管理機制

本文提出的控制節點緩存數據包數量的管理機制主要包括以下兩方面：

（1）限制消息在傳輸過程中的最大副本數。由于Prophet算法在傳輸消息時是通過復制消息副本的方式工作的，沒有限制消息的最大副本數，當消息在網絡中傳遞且數量足夠多時，可以推測該消息已成功傳輸，此時再復制該消息副本無疑將給網絡帶來更大壓力。因此，為每一個消息設置最大副本數量，當達到該上限時則停止復制消息，可以減少網絡冗余。

（2）及時刪除已傳輸成功的消息。已傳輸成功的數據包在網絡中是無用的，并且會極大地占用緩存。其不一定是長期滯留在緩存中的老數據包，也可能是新包傳輸成功，但未被及時刪除。及時刪除已傳輸成功的數據包可以有效改善緩存情況，減少資源浪費。

3 路由算法設計

本文提出的改進Prophet算法的核心思想在于控制節點緩存區，包括限制消息最大副本數目與及時刪除網絡中不必要的數據包。針對以上兩點操作可以有效降低緩存區壓力，保證節點不會因緩存區溢出導致消息無法正常傳輸。在此基礎之上，Prophet算法在選擇轉發節點時進一步考慮了緩存比因素，其改進算法步驟如下：

（1）a、b節點通過移動進入彼此通信范圍，建立連接。

（2）兩節點交換彼此在本地保存的與鏈路中其它節點的傳遞概率。

（3）根據式（2）計算節點a、b的傳遞概率，并考慮此時節點b緩存比Rb的情況。

（4）節點a中有傳輸到目的節點s的消息，但該消息并不存在于節點b中，此時比較P（a，s）與P（b，s）*Rb大小，若P（a，s）

4 實驗仿真與性能分析

4.1 實驗仿真設置

本文使用仿真工具ONE[12]（Opportunistic Network Environment Simulator）對改進算法進行實驗分析及性能比較，驗證本文提出的改進算法是否可以有效改善網絡性能、解決擁塞情況。

本文模擬了一些經典場景下節點移動的消息傳遞情況，如學校、社區及工作區，這些場景的節點移動范圍都存在一定規律性，但節點移動速度和方向是隨機的。采用移動模型模擬這些移動場景，實驗參數如表1所示。

表1 仿真配置參數

在上述場景下，本文分別對原Prophet算法、改進后的Prophet算法和Epidemic算法從網絡性能的3個方面進行比較，分別是傳輸成功率、網絡開銷和傳輸延遲，比較在節點數量逐漸增加時網絡性能的差異。

4.2 仿真結果與分析

本文對原Prophet算法、改進后的Prophet算法和Epidemic算法在不同節點數量時表現出的網絡性能進行測試，仿真結果如圖2-圖4所示。

圖2 傳輸成功率與節點數量關系

在圖2中，隨著節點數量的增加，由于原Prophet算法和Epidemic是通過復制消息的方式在網絡中傳輸的，節點數量較多會增加節點之間的接觸概率，導致消息副本在網絡中的數量不斷增加。當緩存溢出時，消息則無法得到正常傳輸。改進后的Prophet算法考慮到了緩存情況，假設節點緩存已經溢出，則該節點不會被選為下一跳節點，而是尋找其它適合的節點進行傳遞，使消息可以正常傳輸。

圖3 網絡開銷與節點數量關系

在圖3中，隨著節點數量的增加，改進后的Prophet算法由于對緩存進行了管理，避免了消息在轉發時選擇緩存使用率高的節點，從而降低了算法開銷，所以其網絡開銷一直保持在一個較低水平。但其它兩個算法都是基于消息復制的路由算法，隨著網絡中消息副本的數量不斷增多，并且沒有解決節點緩存問題，因此易造成網絡擁塞，增加網絡開銷。

圖4 傳輸延遲與節點數量關系

在圖4中，改進Prophet算法在傳輸時間上多于其它兩種算法，主要是因為改進Prophet算法控制了網絡中的消息副本數量，從而減少了與目的節點的相遇機會，在一定程度上也增加了消息傳輸到目的節點的時間，所以傳輸過程中比其它兩個在網絡中消息副本較多的算法花費時間更多。還有一個原因是在沒有找到合適的轉發節點時，節點會將消息保存在本地，直到遇到合適的下一跳節點才開始傳輸，從而導致傳輸延遲。

5 結語

本文分析了機會網絡中存在的消息冗余情況，提出了設置消息最大副本數量與及時刪除不必要數據包的節點緩存管理機制，并在Prophet算法基礎上考慮了緩存比因素，設計了一個考慮節點緩存的改進Prophet算法。仿真結果表明，在相同條件下，改進算法相比于原Prophet算法及Epidemic算法，具有更高的消息投遞率，可以有效防止網絡擁塞情況發生，提高網絡吞吐量。

參考文獻：

[1] FALL K. A delay-tolerant network architecture for challenged Internets[C]. Conference on applications，technologies，architectures，and protocols for computer communication，2003：27-34.

[2] DAVIES E. DTN-the state of the art[EB/OL]. http：//www.n4c.eu/Download/n4c-wp2-012-state-of-the-art-101.pdf，2009.

[3] LILIEN L，GUPTA A，YANG Z. Opportunistic networks for emergence applications and their standard implementation framework[C]. Proceedings of 2007 IEEE International Conference on Wireless and Mobile Computing，Networking and Communications.IEEE，2007：588-593.

[4] SMALL T，HAAS Z J. The shared wireless info station model：a new ad hoc networking paradigm[C]. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking&Computing. ACM，2003：233-244.

[5] JUANG P，OKI H，YONG W，et al. Energy-efficient computing for wildlife tracking[J]. ACK Sigops Operation Systems Review，2002，36（10）：96-107.

[6] 熊永平，孫利民，牛建偉. 機會網絡[J]. 軟件學報，2009，20（1）：124-137.

[7] PUNEET K B，SHIPRA S，VANDANA D. Comparative analysis of reactive and proactive protocol of mobile ad-hoc network[J]. International Journal on Computer Science and Engineering，2012，4（7）：1281-1288.

[8] 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 Delay-tolerant Networking. New York， USA： ACM Press， 2005.

[9] NELSON S C， BAKHT M， KRAVETS R. Encounter based routing in DTNs[J]. Mobile Computing and Communications Review， 2009，13（1）： 56-59.

[10] LINDGREN A， PHANSE K S. Evaluation of queuing policies and forwarding strategies for routing in intermittently connected networks[C]. Proceedings of IEEE COMSWARE06，IEEE Press，2006.

[11] DAVIS J A， FAGG A H， LEVINE B N. Wearable computers as packet transpor mechanisms in highly partitioned ad-hoc networks[C]. Proceedings of the 5th IEEE International Symposium on Wearable Computers， USA： IEEE Press， 2001.

[12] MOTA VFS，CUNBA FD，MACDO DF，et al.Protocols，mobility models and tools in opportunistic networks：a survey[J]. Computer Communication，2014，48：5-19.

[13] QIANG Z，JING Y，MINGHUI W.Formal taxonomy research on opportunistic networks[C]. Proceeding of the 2nd IEEE International Conference on Broadband Network&Multimedia Technology，2009：854-857.

[14] HSU CJ，LIU HI，SEAH WKG. Opportunistic routing-a review and the challengers ahead[J]. Computer Networks，2011，55（15）：3592-3603.

[15] BECKER V D.Epidemic routing for partially connected ad hoc network [R]. Durhan，NC：Duke University，2000.

[16] HUANG T，LEE C，CHEN L. PRoPHET+：an adaptive PRoPHET-based routing protocol for opportunistic network[C]. 24th IEEE International Conference on Advanced Information Networking and Application，2010：112-119.

[17] 任智，黃勇，陳前斌. 機會網絡路由協議[J]，計算機應用，2010，30（3）：723-728.

[18] 段鵬瑞，馬華東，羅紅. 基于梯度的DTN路由算法[J]. 北京郵電大學學報，2011，34（2）：63-66.

[19] SHEN J，ZHENG W. An improvement of buffer scheme for delay tolerant network[J]. International Journal of Future Generation Communication&Network，2013，6（4）：263-271.

[20] KERANEN A. Opportunistic network environment simulator [R]. Helsinki：Helsinki University of Technology，2008.

（責任編輯：黃 健）