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

吳大鵬 張普寧 王汝言

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

1 引言

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

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

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

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

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

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

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

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

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

3 消息投遞概率估計(jì)方法

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

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

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

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

進(jìn)而，可獲知節(jié)點(diǎn)i的連接到達(dá)強(qiáng)度λi，如式(5)所示。

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

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

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

3.2 消息投遞概率估計(jì)方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

本部分采用機(jī)會網(wǎng)絡(luò)環(huán)境[9,10](Opportunistic Networks Environment, ONE)驗(yàn)證帶有消息投遞概率估計(jì)的自適應(yīng)緩存管理策略(Adaptive Buffer management strategy with Message Delivery Probability Estimating, ABMDPE)的有效性，并與機(jī)會網(wǎng)絡(luò)中典型的緩存管理機(jī)制(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)進(jìn)行對比。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)束語

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

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

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

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

[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ī)會網(wǎng)絡(luò)[J]. 軟件學(xué)報(bào), 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.