帶有消息投遞概率估計的機會網(wǎng)絡(luò)自適應(yīng)緩存管理策略

吳大鵬 張普寧 王汝言

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

1 引言

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

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

針對上述相關(guān)研究的局限性，本文構(gòu)建了通用節(jié)點連接狀態(tài)分析模型，感知各個節(jié)點間的服務(wù)能力差異，并據(jù)此估計消息經(jīng)由多個中繼節(jié)點協(xié)同存儲后的投遞概率，進而執(zhí)行緩存管理操作，合理分配有限的節(jié)點緩存資源，以提高網(wǎng)絡(luò)運行效率。

2 節(jié)點連接狀態(tài)分析模型

節(jié)點建立連接的能力越強，其為相遇節(jié)點所攜帶的消息提供轉(zhuǎn)發(fā)與緩存服務(wù)的能力就越強。按照連接的通斷狀況，節(jié)點在網(wǎng)絡(luò)中的運行時間可分為連接間隔時間與連接持續(xù)時間，因而，針對節(jié)點連接狀態(tài)的分析可分解為對連接間隔時間與連接持續(xù)時間的分析，如圖1所示。

圖1 節(jié)點連接狀態(tài)分析

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

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

通過上述建立的節(jié)點連接狀態(tài)分析模型，節(jié)點可近似獲知給定消息攜帶節(jié)點的服務(wù)能力，從而估計消息的投遞概率，為消息的轉(zhuǎn)發(fā)與刪除提供決策依據(jù)。

3 消息投遞概率估計方法

依托構(gòu)建的節(jié)點連接狀態(tài)分析模型，本部分提出節(jié)點服務(wù)能力感知方法以估計消息的投遞概率，并實現(xiàn)有效的緩存管理。

3.1 節(jié)點服務(wù)能力感知方法

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

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

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

如前所述，節(jié)點連接間隔時間及連接持續(xù)時間均服從指數(shù)分布，則可以采用M/M/ 1 /1模型描述本文所構(gòu)建的分布式節(jié)點連接狀態(tài)分析模型。節(jié)點的連接狀態(tài)流圖如圖2。

圖2 節(jié)點連接狀態(tài)流圖

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

3.2 消息投遞概率估計方法

消息的投遞狀態(tài)與攜帶該消息的中繼節(jié)點相關(guān)，在對消息的投遞概率進行估計時，應(yīng)綜合考慮存儲過該消息的中繼節(jié)點服務(wù)能力。

根據(jù)本文提出的節(jié)點服務(wù)能力感知方法，可獲知網(wǎng)絡(luò)中各個節(jié)點的相對服務(wù)能力，如式(16)所示。

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

與機會網(wǎng)絡(luò)消息傳輸基本原理相同，本文利用節(jié)點相遇帶來的通信機會，在節(jié)點之間交互消息傳播路徑與節(jié)點服務(wù)能力信息，經(jīng)過較短的收斂時間當(dāng)網(wǎng)絡(luò)狀態(tài)趨于穩(wěn)定后，節(jié)點可近似獲知本地消息的傳輸路徑及各個節(jié)點的服務(wù)能力。

4 自適應(yīng)緩存管理策略

為了提高節(jié)點緩存利用率，優(yōu)化網(wǎng)絡(luò)性能，應(yīng)優(yōu)先刪除投遞概率較高的消息，為投遞概率較低的消息分配相應(yīng)的節(jié)點緩存資源。

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

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

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

步驟 2 建立連接的節(jié)點間通過交換彼此信標(biāo)列表內(nèi)的信息實現(xiàn)信標(biāo)列表的更新；

步驟 3 節(jié)點在本地緩存內(nèi)將信標(biāo)列表中對應(yīng)的消息依次刪除。

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

4.2 自適應(yīng)隊列排序與消息刪除方法

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

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

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

表1 自適應(yīng)緩存管理策略偽代碼

5 仿真驗證與結(jié)果分析

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

5.1 不同網(wǎng)絡(luò)負載狀態(tài)下的性能分析

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

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

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

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

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

機會網(wǎng)絡(luò)中節(jié)點緩存容量受限，而如何合理配置有限的節(jié)點緩存資源，實現(xiàn)網(wǎng)絡(luò)性能的有效提升是本文的研究重點。因此，本小節(jié)主要驗證所提ABMDPE機制在各種緩存資源設(shè)置下的性能。

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

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

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

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

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

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

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

6 結(jié)束語

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

圖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] 熊永平, 孫利民, 牛建偉, 等. 機會網(wǎng)絡(luò)[J]. 軟件學(xué)報, 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.