帶有節點狀態估計的間斷連接無線網絡緩存管理策略

吳大鵬白 娜 王汝言

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

帶有節點狀態估計的間斷連接無線網絡緩存管理策略

吳大鵬*白 娜 王汝言

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

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

間斷連接無線網絡；緩存管理；消息效用值；節點服務能力

1 引言

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

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

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

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

2 節點服務能力估計

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

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

2.1 鄰居節點度估計

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

圖1 節點自身及相遇節點的歷史信息

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

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

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

2.2 節點連通強度的估計

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

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

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

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

2.3 節點服務速率估計

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

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

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

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

3 消息投遞概率估計

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

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

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

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

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

m P具體可表示為

4 NS-ICM緩存管理機制

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

4.1 消息轉發決策

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

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

4.2 消息攜帶決策

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

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

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

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

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

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

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

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

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

4.3 消息隊列管理

為了確定給定消息所屬部分，本文利用節點傳輸容量估計值設定動態閾值，考慮到消息大小及傳輸容量，所設定的閾值為式中，th指閾值的大小，Smin指當前節點緩存中消息大小的最小值，指節點i記錄的第r次可傳輸的容量，通過求均值獲得節點i可傳輸的平均容量。

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

帶有節點狀態估計的間斷連接無線網絡緩存管理機制的偽代碼如表1所示。

5 數值分析

圖2 消息隊列管理

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

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

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

表1 間斷連接無線網絡緩存管理機制偽代碼

表2 仿真參數表

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

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

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

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

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

6 結束語

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

[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年生，副教授，博士，研究方向為泛在無線網絡、社會計算、互聯網服務質量控制.

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

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

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)，重慶市青年科技人才培養計劃(CSTC2014KJRC-QNRC40001)和重郵青年自然科學基金(A2012-93)資助課題

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