吳大鵬白 娜 王汝言

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

帶有節(jié)點狀態(tài)估計的間斷連接無線網(wǎng)絡緩存管理策略

吳大鵬*白 娜 王汝言

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

針對間斷連接無線網(wǎng)絡中的節(jié)點緩存資源有限的問題，該文提出一種適用于間斷連接無線網(wǎng)絡的緩存管理機制。根據(jù)運動過程中所獲得的網(wǎng)絡狀態(tài)信息，各個節(jié)點以分布式的方式估計給定節(jié)點與其他節(jié)點直接及間接連接狀態(tài)、節(jié)點服務率以及節(jié)點連通強度，動態(tài)感知各個節(jié)點服務能力的差異，同時預測當前節(jié)點成功投遞該消息的概率以感知消息的效用值，從而執(zhí)行緩存管理操作。結果表明，與其他緩存管理機制相比，所提出的緩存管理機制不僅能夠有效降低投遞開銷，同時大幅度地提高了消息成功投遞率。

間斷連接無線網(wǎng)絡；緩存管理；消息效用值；節(jié)點服務能力

1 引言

移動自組織網(wǎng)絡(Mobile Ad hoc NETwork, MANET)[1]中，建立端到端連接是節(jié)點實現(xiàn)消息轉發(fā)的首要前提。間斷連接無線網(wǎng)絡體系架構，以更加靈活的“存儲-攜帶-轉發(fā)”模式實現(xiàn)信息傳輸[2]，解決了MANET網(wǎng)絡中源節(jié)點與目的節(jié)點之間路徑頻繁斷裂所導致的通信中斷問題。

為了保證消息傳輸?shù)目煽啃?，通常需要在網(wǎng)絡中注入多個消息副本[3,4]，各個副本通過多路徑并行的方式進行傳輸。隨著節(jié)點不斷與其他節(jié)點相遇，其所攜帶消息副本數(shù)量逐漸增加，將導致有限的緩存被冗余消息副本浪費。因此，如何在節(jié)點的處理能力及存儲能力有限的情況下，通過高效的緩存管理機制優(yōu)化網(wǎng)絡性能具有重要研究意義。

針對以上問題，文獻[5]提出了帶有消息投遞概率感知的消息替換機制，該方法根據(jù)消息投遞概率閾值將緩存空間等分為3個大小相等的區(qū)域，優(yōu)先刪除投遞概率位于最低等級區(qū)域中的消息。但是該機制需預先等分緩存區(qū)域和設定閾值，難以適應復雜的間斷連接無線網(wǎng)絡環(huán)境。文獻[6]在噴灑等待(Spray and Wait, SnW)[7]消息轉發(fā)策略的基礎上提出了相應的緩存管理策略，優(yōu)先刪除消息副本數(shù)與消息大小比值最小的消息，以保證副本數(shù)較少且占用緩存空間較大的消息優(yōu)先替換。但是該方法需要預先設定消息副本數(shù)的初始值，擴展性較差。文獻[8]認為當前節(jié)點成功投遞該消息概率與相遇節(jié)點成功投遞該消息概率的差值越大，則表明消息被成功投遞的概率越高。當緩存溢出時，優(yōu)先刪除成功投遞概率差值最大的消息。但是若當前節(jié)點與相遇節(jié)點成功投遞該消息的概率都較低，而其成功投遞概率差值卻較大，則節(jié)點優(yōu)先選擇刪除此類消息，導致消息成功投遞概率下降。

為了提高有限緩存資源的利用率，本文提出一種帶有節(jié)點狀態(tài)估計的間斷連接無線網(wǎng)絡緩存管理機制(Intermittent connectivity wireless network Cache Management mechanism with Node Status evaluation, NS-ICM)，在充分考慮節(jié)點社會屬性的基礎上[9]，根據(jù)運動過程中所獲知的連接狀態(tài)歷史信息，各個節(jié)點以分布式的方式估計自身的服務能力及當前節(jié)點成功投遞該消息的概率，繼而感知消息經(jīng)由多個中繼節(jié)點協(xié)同存儲后的效用值，從而執(zhí)行緩存管理操作。結果表明所提出的機制在提升投遞率的同時降低了網(wǎng)絡開銷。

2 節(jié)點服務能力估計

顯然，對于間接連接無線網(wǎng)絡中的消息轉發(fā)過程來說，中繼節(jié)點服務能力直接影響消息成功投遞的概率。利用服務能力較強的中繼節(jié)點完成消息的傳輸，將極大地降低網(wǎng)絡開銷。

目前，節(jié)點服務能力的評估方法大部分以節(jié)點之間建立連接的次數(shù)作為衡量標準。但是，此類方法單一地考慮了節(jié)點之間的直接連接次數(shù)而忽略了間接相遇狀態(tài)及消息轉發(fā)數(shù)量等因素，無法準確地衡量節(jié)點服務能力?？紤]到間斷連接無線網(wǎng)絡中節(jié)點的聚集特性，本文將節(jié)點間的相遇次數(shù)及相遇持續(xù)時間高于其歷史運動過程均值的節(jié)點定義為其鄰居節(jié)點，若當前節(jié)點與其他節(jié)點的直接連接次數(shù)較少，而其鄰居節(jié)點數(shù)量較多，則可通過鄰居節(jié)點與其他節(jié)點相遇機會完成消息轉發(fā)，即可以通過其鄰居節(jié)點的數(shù)量間接評估節(jié)點的服務能力。此外，為更精確地評估節(jié)點服務能力，本文進一步考慮了節(jié)點間相遇之后節(jié)點間的連通強度以及消息服務率。

2.1 鄰居節(jié)點度估計

鄰居節(jié)點數(shù)量直接影響給定節(jié)點的消息轉發(fā)效率。需要通過節(jié)點自身記錄的歷史信息以及與其他節(jié)點相遇時所獲取的狀態(tài)信息來估計相遇次數(shù)和鄰居節(jié)點度數(shù)。在節(jié)點的本地信息表中，每個相遇節(jié)點對應兩個表項，分別為相遇節(jié)點的ID及相遇次數(shù)，其中相遇次數(shù)呈降序排列，如圖1所示。

圖1 節(jié)點自身及相遇節(jié)點的歷史信息

節(jié)點i與鄰居節(jié)點的相遇次數(shù)總和可按照式(1)所示方式進行計算，其中NeiLi為節(jié)點i的鄰居節(jié)點集合，c(v)為節(jié)點i與節(jié)點v的相遇次數(shù)。

進而，根據(jù)式(2)可獲知節(jié)點i的鄰居節(jié)點度數(shù)之和，其中deg(v)為節(jié)點v的度數(shù)，反映了給定節(jié)點與其他節(jié)點的相遇頻繁度。由于間斷連接無線網(wǎng)絡中的節(jié)點持續(xù)地在網(wǎng)絡中移動，與其產(chǎn)生連接的節(jié)點列表最終趨于穩(wěn)定，不同節(jié)點的相遇節(jié)點列表將出現(xiàn)相同的情況，則無法判定節(jié)點之間連接的緊密程度，因此傳統(tǒng)的按照鄰居列表大小評估節(jié)點度的方法無法準確區(qū)分鄰居節(jié)點的活躍度。本文通過將鄰居節(jié)點和其他節(jié)點的相遇次數(shù)與節(jié)點的平均相遇次數(shù)進行比較獲知deg(v)。

對于節(jié)點i的鄰居列表中節(jié)點j所對應的表項來說，節(jié)點j的鄰居列表為NeiLj，將節(jié)點j與自身鄰居列表中所有節(jié)點的相遇次數(shù)記為{c(vk)|k=1, 2,…,Nj,vk∈NeiLj}，同時記節(jié)點i與其鄰居節(jié)點的相遇次數(shù)平均值為avei，若c(vk)＞avei，則deg(v)加1，依次比較，最終得到deg(v)。

2.2 節(jié)點連通強度的估計

節(jié)點間連通強度定義為節(jié)點之間的鏈路持續(xù)時間與給定時間的比值。該參數(shù)描述了給定節(jié)點為其他節(jié)點提供服務的時間長度，顯然，連通強度越大，則表明節(jié)點服務能力越強。對于給定節(jié)點i，其第n次連接持續(xù)時間tuis(n)為

根據(jù)本地記錄的運動過程中歷史信息，節(jié)點i可得到m個相關節(jié)點在給定時間T內處于通信鏈路持續(xù)時間總和sum為

那么，根據(jù)上述定義在給定時間T內，節(jié)點i的連通強度λi可表示為節(jié)點處于通信鏈路持續(xù)時間總和與給定時間T的比值：

在相同時間段內，節(jié)點間連接持續(xù)時間越長，則其能夠為其他節(jié)點提供更多的消息轉發(fā)機會。

2.3 節(jié)點服務速率估計

節(jié)點服務速率定義為單位時間內節(jié)點轉發(fā)的消息數(shù)目。若節(jié)點i在第n次通信鏈路持續(xù)時間為(n)，成功轉發(fā)的消息數(shù)量為an，則第n次鏈路持續(xù)時間內，每個消息的轉發(fā)時間為

那么節(jié)點i第n次建立連接時為其他節(jié)點所提供服務的速率即為τi(n)的倒數(shù)，如式(7)所示。

由于節(jié)點間的通信鏈路持續(xù)時間具有不確定性，同時成功轉發(fā)的消息數(shù)量也具有較強隨機性，因此取其統(tǒng)計平均值以衡量節(jié)點服務速率，如式(8)所示。

如前所述，間斷連接無線網(wǎng)絡中的消息轉發(fā)過程需要多個中繼節(jié)點輔助，各個節(jié)點的鄰居節(jié)點可有效地將消息擴散至網(wǎng)絡中的其他節(jié)點。因此，為了更全面地反映節(jié)點間的相遇情況，本文充分考慮直接相遇次數(shù)sumi與間接相遇次數(shù)Degi兩個方面因素來衡量節(jié)點之間的相遇次數(shù)。進而，可根據(jù)節(jié)點i處于斷開狀態(tài)的時間長度T-λiT 來確定其相遇概率。更進一步地，相遇概率參數(shù)僅僅反映了給定時間內的節(jié)點相遇次數(shù)，忽略了節(jié)點相遇之后節(jié)點服務速率。當且僅當節(jié)點具有較高的相遇頻率及服務速率的情況下，節(jié)點才具有較強的服務能力。綜合上述因素，給定時間T內任意節(jié)點i的服務能力SerAi可采用式(9)所示方法進行估計。

3 消息投遞概率估計

中繼節(jié)點的服務能力直接反映了消息的投遞狀態(tài)，消息攜帶節(jié)點的服務能力越強，網(wǎng)絡中消息的擴散程度越高，則消息成功投遞的概率越高，從而大大降低了此類消息緩存及轉發(fā)的必要性，但是，若持續(xù)地刪除此類消息副本會對其成功投遞產(chǎn)生較大的影響。因此，為合理地刪除冗余消息副本，需要考慮當前節(jié)點在消息剩余存活時間內成功投遞該消息的概率。

假設節(jié)點i與消息目的節(jié)點d之間建立連接的間隔時間可按照式(10)所示方式表示，式中，t0指節(jié)點i與消息目的節(jié)點d上次相遇時間，Xi(t)表示節(jié)點i在t時刻的坐標，R為通信范圍。

在消息存活時間內，判斷當前節(jié)點是否能夠成功投遞該消息需獲知消息在網(wǎng)絡中剩余存活時間，其計算方法如式(11)所示。其中tm指剩余存活時間，tTTL指消息的生存時間，tge指消息的產(chǎn)生時間，t指當前網(wǎng)絡運行時間。

若節(jié)點與目的節(jié)點的相遇間隔時間小于消息的剩余存活時間，則表明此節(jié)點能夠將消息成功投遞，其投遞概率定義如式(12)所示。

繼而，利用馬爾科夫不等式，通過比較消息的剩余存活時間及節(jié)點與目的節(jié)點的相遇間隔時間的期望值E(MTi,d)，可獲知當前節(jié)點未能成功投遞該消息的概率為

m P具體可表示為

4 NS-ICM緩存管理機制

在上述節(jié)點服務能力估計方法及消息投遞概率估計方法的基礎上，本節(jié)提出了帶有節(jié)點狀態(tài)估計的間斷連接無線網(wǎng)絡緩存管理機制，該機制能夠動態(tài)地估計節(jié)點服務能力及節(jié)點投遞消息的概率，進而感知消息繼續(xù)轉發(fā)的效用值。節(jié)點根據(jù)自身所獲知的網(wǎng)絡狀態(tài)信息實時更新消息效用值，進而確定緩存中各個消息的處理優(yōu)先級，以提高緩存資源的利用率。

4.1 消息轉發(fā)決策

在動態(tài)性極強的間斷連接無線網(wǎng)絡中節(jié)點無法通過單次連接完成全部消息的轉發(fā)。為了合理地選擇消息優(yōu)先轉發(fā)，所提出的緩存管理機制充分考慮了傳輸容量與消息大小之間的關系，具體如式(16)所示。

當兩節(jié)點相遇之后，將對方?jīng)]有緩存的消息根據(jù)式(17)獲知的優(yōu)先級降序排列,其中，Pm為消息m的轉發(fā)優(yōu)先級，其根據(jù)消息轉發(fā)概率和鏈路容量決定，具體定義如下：

4.2 消息攜帶決策

在消息攜帶決策過程中，所提出的機制通過比較效用值的大小決策消息是否繼續(xù)攜帶，效用值可根據(jù)消息攜帶節(jié)點的平均服務能力及消息投遞概率的估計值獲知，進而確定是否繼續(xù)緩存該消息。

攜帶節(jié)點的平均服務能力計算方法如式(18)所示。式中Qt(m)表示部分攜帶消息m節(jié)點的集合，h表示集合中節(jié)點的個數(shù)，表示此集合節(jié)點的平均服務能力。

對式(18)進行歸一化處理之后，根據(jù)當前節(jié)點未能成功投遞該消息的概率，可求得效用值V(m)。

式中，Amax指消息攜帶節(jié)點服務能力最大值，Am指存儲消息m的中繼節(jié)點的平均服務能力。α是節(jié)點服務能力對消息效用值的影響因子，β是節(jié)點成功投遞消息概率對消息效用值的影響因子。本文通過定義拉格朗日(Lagrange)函數(shù)以及約束條件確定α與β的取值，使得消息效用V(m)取得最大值。

為了分析方便，設α,β滿足單位化約束條件：

首先構造Lagrange函數(shù)，如式(20)所示。

求解方程組式(21)，并進行歸一化處理得到權重值α′與β′：

為了避免效用值較高的消息提前溢出則優(yōu)先從效用值最低的消息開始執(zhí)行刪除操作，直到可以接收該消息。接收消息m所需要的緩存空間計算方法如式(23)所示。

式中，B0指節(jié)點的空閑緩存大小，Sm指消息m的大小，Sl指節(jié)點緩存中消息l的大小，V(l)指消息l的效用值。

4.3 消息隊列管理

為了確定給定消息所屬部分，本文利用節(jié)點傳輸容量估計值設定動態(tài)閾值，考慮到消息大小及傳輸容量，所設定的閾值為式中，th指閾值的大小，Smin指當前節(jié)點緩存中消息大小的最小值，指節(jié)點i記錄的第r次可傳輸?shù)娜萘?，通過求均值獲得節(jié)點i可傳輸?shù)钠骄萘俊?/p>

節(jié)點相遇之后，對消息的具體處理過程如圖2所示：節(jié)點緩存了n個消息，按照其跳數(shù)升序排列，并將已排序閾值前的消息m1,m2,…,mi劃分為待轉發(fā)部分，且按照消息的投遞概率Pde(mi)進行降序排列；同時，將緩存中剩余的消息劃分為待刪除部分，并按照消息效用值的大小V(mi)設定消息的刪除順序。由式(24)可以看出，當節(jié)點的傳輸容量隨著網(wǎng)絡運行狀態(tài)的變化，閾值th的大小也隨之變化。該方法能夠充分利用網(wǎng)絡資源，改善了網(wǎng)絡性能。

帶有節(jié)點狀態(tài)估計的間斷連接無線網(wǎng)絡緩存管理機制的偽代碼如表1所示。

5 數(shù)值分析

圖2 消息隊列管理

本文采用網(wǎng)絡環(huán)境(Opportunistic Network Environment, ONE)[10]對所提出的緩存管理機制NS-ICM進行了網(wǎng)絡性能的驗證。其中節(jié)點間的路由協(xié)議采用泛洪算法Epidemic，仿真參數(shù)具體設置如表2所示。

本文以基于消息傳輸狀態(tài)緩存管理機制(MTSBR)[11]以及基于刪除頭部Prophet算法[12]作為對比算法。其中MTSBR機制中，節(jié)點以副本數(shù)量為依據(jù)，優(yōu)先刪除網(wǎng)絡中副本數(shù)量較多的消息，以達到為其他消息預留緩存資源的目的。此外，對于采用頭部刪除的Prophet機制來說，節(jié)點選擇接收時間最早的消息進行刪除。

由圖3可知，與MTSBR及Prophet-FIFO機制相比，本文所提NS-ICM機制在投遞率方面可分別提高25.9%與31.2%。Prophet-FIFO機制由于未考慮節(jié)點間連接的時序特性，其相遇概率預測的準確性得不到保障，導致其投遞概率較低。NS-ICM機制根據(jù)當前消息傳輸狀態(tài)、相遇節(jié)點服務能力等因素確定其緩存內各個消息的優(yōu)先級，使得中繼節(jié)點的選擇更具合理性，其投遞率較高。MTSBR機制受節(jié)點緩存能力及消息傳輸方式的影響，獲得消息副本的時間相對滯后，導致其投遞概率在緩存較小的情況下并不理想。

表1 間斷連接無線網(wǎng)絡緩存管理機制偽代碼

表2 仿真參數(shù)表

圖4描述了3種機制在不同緩存容量下的投遞開銷性能。由結果可知，3種機制的投遞開銷隨著節(jié)點緩存容量不斷增加均呈下降趨勢。Prophet-FIFO機制在節(jié)點緩存被占用之后，其單純地根據(jù)接收時間刪除消息，容易導致節(jié)點將重要程度較高的消息錯誤地刪除，使得其開銷大于NS-ICM機制。與之相比，NS-ICM機制優(yōu)先刪除具有高服務能力節(jié)點所攜帶過的消息，使得消息冗余度保持在較低的水平。因此，投遞開銷始終維持在85%～105%之間。MTSBR機制無法準確獲得當前網(wǎng)絡中給定消息的副本數(shù)量，難以進一步判定其冗余程度并合理地刪除消息副本，導致消息的轉發(fā)次數(shù)增加。NSICM與其他兩種機制相比，開銷分別降低了12.1 %和25.2 %，有效地改善了網(wǎng)絡性能。

圖3 不同緩存空間下投遞率的比較

圖4 不同緩存空間下投遞開銷的比較

圖5 不同緩存空間下投遞時延的比較

圖5給出了所提出的緩存管理機制與其他兩種機制在不同緩存容量下的消息平均投遞時延，由結果可知，Prophet-FIFO機制比本文所提出的緩存管理機制NS-ICM在時延方面低24.2%。本文的NS-ICM在消息轉發(fā)時考慮了攜帶消息節(jié)點的平均服務能力及投遞概率等綜合信息，進而更加合理地選擇中繼節(jié)點。與Prophet-FIFO機制相比，NS-ICM中的節(jié)點需要執(zhí)行中繼節(jié)點選擇過程，導致消息需要在節(jié)點處的等待時間增加。但是與MTSBR機制相比，NS-ICM的時延降低了14.3 %。其原因在于MTSBR機制單純地根據(jù)消息在網(wǎng)絡中副本數(shù)目選擇所要刪除的消息，容易造成較重要消息的數(shù)量迅速地減少，導致其投遞時延增大。

6 結束語

本文提出了節(jié)點服務能力以及消息投遞概率估計方法，進而設計了帶有節(jié)點狀態(tài)估計的間斷連接無線網(wǎng)絡緩存管理機制，充分利用消息攜帶節(jié)點的服務能力合理地選擇中繼節(jié)點，并根據(jù)當前網(wǎng)絡中的消息傳輸狀態(tài)刪除效用值較低的消息，從而為重要程度較高的消息預留緩存資源。仿真結果表明，本文提出的緩存管理機制不僅能有效降低投遞開銷，同時提高了消息的成功投遞率。

[1] Darshana P and Vandana V. Security enhancement of AODV protocol for mobile Ad hoc network[J]. International Journal of Application or Innovation in Engineering and Management, 2013, 2(1): 317-321.

[2] Li Z and Shen H Y. SEDUM: exploiting social networks in utility-based distributed routing for DTNs[J]. IEEE Transactions on Computers, 2013, 62(1): 83-97.

[3] Ayub Q, Rashid S, and Zahid M S M. MinHop (MH) transmission strategy to optimized performance of epidemic routing protocol[J]. Journal of Computer Science and Technology, 2011, 11(9): 35-42.

[4] Wang Y S, Yang W S, and Wu J. Analysis of a hypercube-based social feature multipath routing in delay tolerant networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(9): 1706-1716.

[5] Rashid S, Hanan A A, Ayub Q, et al.. Dynamic prediction based multi queue (DPMQ) drop policy for probabilistic routing protocols of delay tolerant network[J]. Journal of Network and Computer Applications, 2013, 36(5): 1395-1402.

[6] Prodhan A T, Das R, Kabir H, et al.. TTL based routing in opportunistic networks[J]. Journal of Network and Computer Applications, 2011, 34(5): 1660-1670.

[7] Pan D R, Lin M, Chen L J, et al.. An improved spray and wait with probability choice routing for opportunistic networks[J]. Journal of Networks, 2012, 7(9): 1486-1492.

[8] Ayub Q, Rashid S, Soperi M Z M, et al.. Contact quality based forwarding strategy for delay tolerant network[J]. Journal of Network and Computer Applications, 2014, 39(3): 302-309.

[9] Pan H, Jon C, and Eiko Y. BUBBLE rap: social-based forwarding in delay-tolerant networks[J]. IEEE Transactions on Mobile Computing, 2011, 10(11): 1576-1589.

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

[11] Liu Y, Wang J X, Zhang S G, et al.. A buffer management scheme based on message transmission status in delay tolerant networks[C]. Globecom2011, Houston, 2011: 1-5.

[12] Lindgren A, Doria A, and Schelen O. Probabilistic routing in intermittently connected networks[J]. ACM SIGMOBILE Mobile Computing and Communications Review, 2003, 7(3): 19-20.

吳大鵬： 男，1979年生，副教授，博士，研究方向為泛在無線網(wǎng)絡、社會計算、互聯(lián)網(wǎng)服務質量控制.

白 娜： 女，1988年生，碩士，研究方向為機會網(wǎng)絡.

王汝言： 男，1969年生，教授，博士，研究方向為空間光通信、光網(wǎng)絡理論與技術、光信息處理、通信網(wǎng)絡可靠性與故障管理.

Cache Management Mechanism with Node Status Evaluation for Intermittently Connected Wireless Networks

Wu Da-peng Bai Na Wang Ru-yan
(Broadband Ubiquitous Network Research Laboratory, Chongqing University of Posts and Telecommunication, Chongqing 400065, China)

Considering the limited cache resources of nodes in intermittently connected wireless networks, a cache management mechanism is proposed based on node state estimate. The direct and indirect connection status, service rate and connectivity degree between the given nodes can be evaluated in a distributed manner, according to the network state monitored during the movement. Further, the difference of service ability of each node can be determined dynamically. Furthermore, the probability of message successfully delivered by the current node and the utility for the given message can be estimated. Consequently, cache management operations are executed reasonably. Simulation results show that the proposed mechanism does not only constrain the overhead ratio effectively but also enhance the message delivery ratio, compared with other mechanisms.

Intermittently connected wireless network; Cache management; Message utility; Nodeservice ability

TP393

A

1009-5896(2015)02-0443-06

10.11999/JEIT140333

2014-03-13收到，2014-05-30改回

國家自然科學基金(61371097)，重慶市自然科學重點基金(CSTC2013JJB40001, CSTC2013JJB40006)，重慶市青年科技人才培養(yǎng)計劃(CSTC2014KJRC-QNRC40001)和重郵青年自然科學基金(A2012-93)資助課題

*通信作者：吳大鵬 wudapengphd@gmail.com