帶有消息投遞概率估計的機會網絡自適應緩存管理策略

吳大鵬 張普寧 王汝言

(重慶郵電大學寬帶泛在接入技術研究所 重慶 400065)

1 引言

多樣化手持與車載終端的廣泛應用推動了移動自組織網絡(Mobile Ad hoc NETwork, MANET)的快速發展。然而，MANET網絡中的通信過程需預先建立端到端路徑[1]，但實際應用場景中存在節點分布稀疏、高速移動、通信能力受限等問題，將導致源節點和目標節點之間建立的通信路徑出現高頻度斷裂[2]。為實現復雜動態環境下的有效通信，研究人員提出了機會網絡體系架構[3]。與MANET所采用的存儲-轉發消息傳輸模式不同，機會網絡中節點轉發消息前不需建立端到端路徑，僅依靠節點相遇帶來的通信機會，以更為靈活的存儲-攜帶-轉發方式傳輸消息。

針對機會網絡特征，國內外研究人員對機會網絡中的節點緩存管理機制展開了相關研究。文獻[4]通過向鄰居節點泛洪本地節點的緩存占用狀態，從而避免緩存占用率較高的節點出現溢出。然而，此種泛洪策略極大地消耗了網絡資源，嚴重影響了正常消息的傳輸過程，此種泛洪方法不適用于資源受限的機會網絡。文獻[5]證明了刪除消息的冗余副本有利于改善消息投遞率的結論，并根據邊際效用遞減規律，提出綜合考慮消息復制數與副本傳輸速率的緩存替換策略。文獻[6]結合消息副本數，存活時間及剩余生存時間等屬性確定消息的效用值，當節點緩存占滿時優先刪除效用值最低的消息，以實現最大化消息投遞率與最小化投遞延遲。然而，上述文獻所提副本數估計方法利用節點相遇機會進行節點本地歷史信息的交互，對消息副本數的感知存在較大時延，造成對消息傳播狀態估計結果存在較大誤差。

針對上述相關研究的局限性，本文構建了通用節點連接狀態分析模型，感知各個節點間的服務能力差異，并據此估計消息經由多個中繼節點協同存儲后的投遞概率，進而執行緩存管理操作，合理分配有限的節點緩存資源，以提高網絡運行效率。

2 節點連接狀態分析模型

節點建立連接的能力越強，其為相遇節點所攜帶的消息提供轉發與緩存服務的能力就越強。按照連接的通斷狀況，節點在網絡中的運行時間可分為連接間隔時間與連接持續時間，因而，針對節點連接狀態的分析可分解為對連接間隔時間與連接持續時間的分析，如圖1所示。

圖1 節點連接狀態分析

(1)機會網絡中的節點運動具有獨立同分布的性質，節點的運動狀態并不受其它節點運動狀態的影響。因此，節點間在非重疊時間域內建立連接的事件相互獨立，即滿足式(1)所示約束條件：

綜合式(1)，式(2)和式(3)可知，給定時間內，節點之間的連接建立為隨機事件，其發生的次數可等效為泊松過程，進而可知節點相繼建立兩次連接的時間間隔服從指數分布[7]；此外，相關研究表明，節點連接持續時間同樣服從指數分布[8]。由此，本文采用M/M/ 1/1模型對節點連接過程進行建模分析。

通過上述建立的節點連接狀態分析模型，節點可近似獲知給定消息攜帶節點的服務能力，從而估計消息的投遞概率，為消息的轉發與刪除提供決策依據。

3 消息投遞概率估計方法

依托構建的節點連接狀態分析模型，本部分提出節點服務能力感知方法以估計消息的投遞概率，并實現有效的緩存管理。

3.1 節點服務能力感知方法

節點連接到達強度大小反映了節點服務能力的強弱。節點連接持續時間具有較強的隨機性，且受限于媒介共享特性，節點之間存在鏈路沖突。因而，節點的服務能力應充分考慮節點連接到達強度及平穩連接可用概率。

機會網絡中節點可由建立的分布式連接狀態分析模型感知節點自身連接狀態。對于給定節點i，其平均連接建立間隔時間ti可由本地記錄的連接建立次數Ni與當前的系統運行時間T得到，如式(4)所示。

進而，可獲知節點i的連接到達強度λi，如式(5)所示。

如前所述，節點連接間隔時間及連接持續時間均服從指數分布，則可以采用M/M/ 1 /1模型描述本文所構建的分布式節點連接狀態分析模型。節點的連接狀態流圖如圖2。

圖2 節點連接狀態流圖

綜合考慮節點連接到達強度λi及節點連接平穩可用概率Pa，即可得到任意節點i的服務能力SAi，如式(15)所示。

3.2 消息投遞概率估計方法

消息的投遞狀態與攜帶該消息的中繼節點相關，在對消息的投遞概率進行估計時，應綜合考慮存儲過該消息的中繼節點服務能力。

根據本文提出的節點服務能力感知方法，可獲知網絡中各個節點的相對服務能力，如式(16)所示。

其中n= N Path，為消息傳輸路徑列表Path中存儲的路徑數量。Pd越大則該消息投遞概率就越高，繼續轉發與存儲該消息的必要性就越小。

與機會網絡消息傳輸基本原理相同，本文利用節點相遇帶來的通信機會，在節點之間交互消息傳播路徑與節點服務能力信息，經過較短的收斂時間當網絡狀態趨于穩定后，節點可近似獲知本地消息的傳輸路徑及各個節點的服務能力。

4 自適應緩存管理策略

為了提高節點緩存利用率，優化網絡性能，應優先刪除投遞概率較高的消息，為投遞概率較低的消息分配相應的節點緩存資源。

4.1 輕量級冗余副本刪除方法

機會網絡中的消息投遞成功之后，網絡中依然存在該消息的大量冗余副本，嚴重影響網絡運行效率。因此，本文提出輕量級冗余副本刪除機制，通過在相遇的節點間交換消息信標列表ib，確定消息投遞狀態，從而以分布式的方式刪除已成功投遞消息的副本，減少網絡中的消息冗余副本數量，以緩解當前網絡的擁塞狀況。具體實施步驟如下：

步驟 1 任意節點i在本地維持已成功投遞到目標節點的消息信標列表ib(由已成功投遞消息的ID號及對應消息的剩余生存時間TR構成)；

步驟 2 建立連接的節點間通過交換彼此信標列表內的信息實現信標列表的更新；

步驟 3 節點在本地緩存內將信標列表中對應的消息依次刪除。

由于所采用的信標列表僅需存儲極少量的信息，其相比正常消息的大小可忽略不計，因此，消息信標列表在網絡中的擴散并不會給網絡帶來嚴重的控制開銷。

4.2 自適應隊列排序與消息刪除方法

當網絡負載較為嚴重時，僅刪除節點本地的冗余副本已無法為新到達的消息提供有效服務。基于前述消息投遞概率估計方法，本文提出適用于機會網絡的緩存管理機制。節點建立連接之后，需交換各自的狀態信息，以獲知消息傳輸路徑及網絡中各個節點的服務能力，進而估計節點緩存內部消息的投遞概率，并據投遞概率的大小，對節點緩存隊列內的消息進行排序。

若新消息到達時，節點尚有足夠的緩存空間，則直接接收該消息，反之，則將新消息與緩存隊列尾部消息的投遞概率進行比較，若新到達的消息投遞概率較低，則刪除緩存隊列尾部消息，以接收新到達的消息，并對緩存隊列中消息按照投遞概率進行自適應排序，否則，拒絕接收該消息。

本文所提自適應緩存管理策略偽代碼如下表 1所示。

表1 自適應緩存管理策略偽代碼

5 仿真驗證與結果分析

本部分采用機會網絡環境[9,10](Opportunistic Networks Environment, ONE)驗證帶有消息投遞概率估計的自適應緩存管理策略(Adaptive Buffer management strategy with Message Delivery Probability Estimating, ABMDPE)的有效性，并與機會網絡中典型的緩存管理機制(Message Transmission Status Buffer Replacement schemes,MTSBR)[5]及傳統緩存管理策略 First-In First-Drop (FIFD), Last-In First-Drop (LIFD)[11], Drop Least Remaining Life (DLRL), Drop Most Remaining Life (DMRL)進行對比。

5.1 不同網絡負載狀態下的性能分析

合理的緩存管理機制需具有對于不同網絡負載狀態的適應性，為驗證所提ABMDPE機制在真實移動模型下的性能，本文采用INFOCOM2006會議的實測數據對上述各個機制的性能進行了驗證。INFOCOM2006會議期間，研究人員通過為與會人員配備 iMotes來模擬會議期間人員的通信情況，iMote采用藍牙作為通信模塊，會場內總共部署了98個節點，其中 78個節點分配給參會人員，另外20個節點固定地放置在給定位置并采用外接天線的方式以作為無線接入點使用[12]。本文通過向 ONE平臺中導入INFOCOM2006中的實測數據，進行了實測模型下的驗證，驗證結果如下所示。

隨著消息產生時間間隔逐漸增大，上述6種算法的投遞率均呈現上升趨勢。由圖 3可知，相比MTSBR及DLRL, ABMDPE機制在投遞率方面可分別實現21%與42%的性能增益。

由圖4可知，隨著消息產生時間間隔逐漸增大，消息的平均轉發次數逐漸增多，上述6種算法的投遞率均呈現上升趨勢。與MTSBR及DLRL兩種機制相比較，ABMDPE機制可分別降低42%與57%的網絡負載。

圖5結果表明，隨著消息產生時間間隔逐漸增大，消息的平均投遞時延逐漸降低。ABMDPE機制的時延相比MTSBR機制降低了約7%，比FIFD低9%。

5.2 不同緩存空間下的性能分析

機會網絡中節點緩存容量受限，而如何合理配置有限的節點緩存資源，實現網絡性能的有效提升是本文的研究重點。因此，本小節主要驗證所提ABMDPE機制在各種緩存資源設置下的性能。

隨著緩存空間的逐漸增大，6種算法的投遞率都呈現上升趨勢。由圖6可知，與MTSBR及DLRL機制相比，所提ABMDPE在投遞率方面可分別提高24%與35%。

圖3 6種算法在不同消息產生時間間隔下投遞率的比較

圖4 6種算法在不同消息產生時間間隔下負載率的比較

圖5 6種算法在不同消息產生 時間間隔下時延的比較

緩存空間增大使得 6種算法的負載率逐漸降低。相比MTSBR及DLRL機制，ABMDPE可分別降低約53%, 46%的網絡負載，結果如圖7所示。

由圖8可知，隨著緩存空間的逐漸增大，消息的投遞時延呈現逐漸降低趨勢。由統計結果可知，ABMDPE機制相對MTSBR及DLRL，在時延性能方面可實現平均達25%與19%的增益。

通過構建節點連接狀態分析模型，所提ABMDPE機制綜合考慮了消息各個中繼節點的服務能力，進而估計消息的投遞概率，實現了網絡資源的合理分配。MTSBR機制所提消息傳播狀態被動感知方法具有一定的滯后性。FIFD和LIFD兩種機制僅依據消息在隊列中的位置，進行簡單的頭部刪除或尾部刪除操作；DLRL和DMRL機制則分別刪除最長已存活時間及最短已存活時間的消息。上述4種傳統緩存管理算法缺乏有效的網絡狀態感知方法，對副本的刪除選擇具較大的盲目性。因而，所提ABMDPE機制相對上述5種算法在投遞率、負載率、延遲方面均可取得較大的性能增益。

6 結束語

為充分利用機會網絡有限的網絡資源，進一步改善網絡性能，本文提出一種消息投遞概率估計的自適應緩存管理策略。通過構建節點連接狀態分析模型，以分布式的方式感知節點服務能力，進而估計消息的投遞概率，從而指導緩存隊列的自適應管理過程。結果表明，本文提出的ABMDPE緩存管理機制能夠大幅降低網絡負載，提高消息成功投遞率，并降低消息平均時延，實現了資源受限場景下節點緩存的合理配置。

圖6 6種算法在不同緩存空間下投遞率的比較

圖7 6種算法在不同緩存空間下負載率的比較

圖8 6種算法在不同緩存空間下時延的比較

[1] Khabbaz M J, Assi C M, and Fawaz W F. Disruption-tolerant networking: a comprehensive survey on recent developments and persisting challenges[J].IEEE Communications Surveys and Tutorials, 2012, 14(2): 607-640.

[2] Milena R and Andrew G. Efficient and adaptive congestion control for heterogeneous delay-tolerant networks[J].Ad hoc Networks, 2012, 10(7): 1322-1345.

[3] 熊永平, 孫利民, 牛建偉, 等. 機會網絡[J]. 軟件學報, 2009,20(1): 124-137.Xiong Y P, Sun L M, Niu J W,et al.. Opportunistic networks[J].Journal of Software, 2009, 20(1): 124-137.

[4] Jani L, Mikko P, and J?rg O. Using buffer space advertisements to avoid congestion in mobile opportunistic DTNs[C]. Proceedings of the 9th IFIP TC 6 International Conference, Vilanovala Geltru, Spain, 2011: 386-397.

[5] Yao L, Jianxin W, Shigeng Z,et al.. A buffer management scheme based on message transmission status in delay tolerant networks[C]. IEEE Globecom proceedings, Houston,USA, 2011: 1-5.

[6] Shin K and Kim S. Enhanced buffer management policy that utilises message properties for delay-tolerant networks[J].IET Communications, 2011, 5(6): 753-759.

[7] Chen Y D, Li L, Zhang Y,et al.. Fluctuations and pseudo long range dependence in network flows:a non-stationary Poisson process model[J].Chinese Physics B, 2012, 18(4):112-132.

[8] Thrasyvoulos S, Konstantinos P, and Cauligi S R.Performance analysis of mobility-assisted routing[C].Proceedings of the 7th ACM International Symposium,Florence, Italy, 2006: 49-60.

[9] Ker?nen A, Ott J, and K?rkk?inen T. The ONE simulator for DTN protocol evaluation[C]. The 2nd International Conference on Simulation Tools and Techniques, Rome, Italy,2009: 1-10.

[10] Vascon G J, Farid F, and Joel P C. Impact of vehicle movement models on VDTN routing strategies for rural connectivity[J].International Journal of Mobile Network Design and Innovation, 2009, 3(2): 103-111.

[11] Zhang X L, Neglia G, Kurose J,et al.. Performance modeling of epidemic routing[J].Computer Networks, 2007, 51(10):2867-2891.

[12] James S, Richard G, Jon C,et al.. CRAWDAD metadata structure[DB/OL]. http://crawdad.cs.dartmouth.edu/cambridge/haggle/imote/infocom, 2006, 2009-05.