基于效用的機會網絡緩存替換策略?

周盼，張振宇

(新疆大學 信息科學與工程學院，新疆 烏魯木齊830046)

0 引言

隨著無線自組網應用的快速發展，出現了大量短距離、低成本、智能化的無線通信設備，這些無線設備在一定的網絡環境下能夠進行接觸，機會網絡[1]是利用移動節點之間的逐跳轉發將數據從源節點傳輸到目標節點.由于節點密度較低和節點移動不可預測性，機會網絡不會一直處于連通狀態，且難以維持端到端的通信鏈路，機會網絡的數據傳輸采用了“存儲-攜帶-轉發”的方式.同時，機會網絡存在網絡資源緊張、移動節點存儲空間的局限性，因此移動節點間的協作緩存顯得十分重要.

由于機會網絡中數據傳輸延遲較大，其在網絡中滯留的時間很長，而移動節點存在緩沖區資源有限等特點，從而在數據量傳輸較大的情況下很容易產生節點緩存區溢出和緩存數據過期的情況.這將導致網絡中的存儲空間會被很快消耗掉，使得節點有限的緩存空間矛盾比傳統移動自組網環境下更為突出.因此，當節點緩存空間滿時，如何設計相應的緩存替換策略是一個關鍵問題.

在研究緩存替換策略時，要解決的問題就是網絡中的哪些節點應該緩存數據，以及這些節點應該緩存什么樣的數據.目前已經有許多基于無線自組網絡環境下提出的緩存替換研究工作：文獻[2]提出了FloodCache，其基本思想是利用有限的洪泛來查找附近節點是否緩存有其所需的數據項，從而避免頻繁遠程訪問，利用較高的通信代價來降低數據延遲，該策略主要用于對數據延遲要求較高的多媒體應用；文獻[3]提出一種可量測的緩存一致性校驗的策略，并相應地對緩存數據替換成本做了評估；文獻[4]考慮到利用節點間的協作關系來避免單個節點緩存有限的問題，并據此設計了一種相應的緩存替換策略；文獻[5]提出了Greedy-Dual-Size，該策略同時考慮了本地數據的成本、大小和延遲.然而大多數現有的緩存替換策略研究是以數據的相關訪問信息作為替換標準，如訪問次數、最后一次訪問時間、數據項尺寸大小等作為標準來對數據項替換策略進行設計，而對于數據的流行度考慮不夠，并未將其列為重要因素進行設計.目前針對機會網絡的節點緩存替換策略研究比較少，才剛剛開始起步，文獻[6]提出一種基于相遇節點和目標節點之間平均接觸頻率的策略，并采用了基于消息副本數量的刪除策略；文獻[7]提出一個分布式算法，使用統計學估計全局的網絡信息；文獻[8]提出了PSEPHOS，其基本思想是對可能緩存的數據進行“投票”，將“投票”最高的內容分布式的放入緩存，對于網絡中每個數據項，數據所緩存的位置是要通過緩存替換策略來進行動態調整.

傳統的無線自組網中的緩存替換策略不能有效的解決機會網絡中數據緩存問題，雖然目前已有機會網絡緩存替換策略研究，然而絕大多數的策略并未討論數據的流行度和機會路徑[9,10].結合機會網絡的特點，作者設計了一個基于效用的緩存替換策略，可以更好地解決節點的緩存空間緊張問題.

1 緩存設計

首先詳細說明基本設計思路，隨后討論了實現方面具體涉及的問題.本文基于數據項的效用值這一標準來對數據進行替換，通過流行度和機會路徑這兩個指標算出數據的效用值.

1.1 數據流行度

數據流行度是一個概率估計，是基于在T1?TK時間內對數據有K個請求，假設這種情況下的數據請求是遵循泊松分布的一個參數，并且數據的流行度被定義為在數據過期之前，數據在將來有再一次被請求的概率.如果di在te時間內過期，它的流行度ωi=1?e?λd(te?tk)，要計算ωi，一個節點只需要遞歸的維持已發生數據請求的兩個時間值，并可以忽略不計空間上的開銷.

1.2 機會路徑

首先定義機會接觸圖G=(V,E)，機會路徑PAB=(VP,EP),節點A和B之前包括一個節點集合V P={A,N1,N2,Nr?1,···,B}∈V，邊集EP={e1,e2,···,er}∈E，邊權重{λ1,λ2,···,λ3}，PAB(T)是在T時間內數據機會的從節點A傳輸到B的概率.節點Nk和Nk+1在PAB上的間接觸時間Xk遵循指數分布的概率密度函數因此，從A到B的傳輸時間遵循亞指數分布其中系數為機會路徑為

1.3 基本策略

當兩個緩存節點A和B接觸時，機會的發生緩存替換，兩個節點通過交換緩存數據來優化所累計的數據訪問延遲，并制定以下緩存策略：

公式(1)表示替換后數據di是否被分別緩存在節點A和節點B中，Si表示數據di的大小，SA和SB是A和B的緩存大小，μi=ωi.pA和νi=ωi.pB表示數據di在節點A和B的緩存性能的效用值，ωi是數據di的流行度，PA和PB表示距離目的節點最短機會路徑.假設PA>PB，節點A優先從選擇池S中選擇數據緩存，之后節點B緩存S中剩下的數據，通過以上公式，此問題能夠使用動態規劃方法解決.

1.4 概率選擇算法

在緩存替換過程中，緩存數據的刪除基于流行數據優先，但可能削弱數據的可達性.數據可達性并不是隨著網絡中緩存副本數量增加而呈線性增加.具體來說，如果緩存數據的副本數量從1增加到2，數據可達性將大大增加，但如果是從10增加到11，數據可達性增加的會很少，例如數據d1的流行度很高，它就有可能在網絡中其他地方緩存許多副本，數據d2的流行度很低，在緩存替換中容易被刪除，刪除會造成數據d2不可獲取， 如何控制副本的數量也是要解決的問題.

緩存替換策略只優化了兩個接觸的緩存節點在本地范圍內的數據訪問延遲.機會網絡中，全局范圍優化具有挑戰性，因為維持網絡中的緩存數據副本的數量是很困難的，從而提出了一個概率策略來控制全局范圍的緩存數據的副本數量.通過提出概率策略，在緩存選擇中，我們仍然優先考慮效用值高的流行數據，同時確保低流行度的數據能有機會被緩存.以下為概率數據選擇算法

2 實驗結果與分析

用本文提出的緩存替換策略(CRPBOU)與傳統的緩存替換策略FIFO、LRU和GreedyDualSize相比較，我們使用了MATLAB做仿真，在800m×400m的矩形區域里隨機放置了50個移動節點,節點的移動模式符合隨機停靠點模型,兩個移動之間移動節點停留5s，移動節點的移動速度為0～20m/s，每個移動節點的信道帶寬為2Mbps，MAC層為藍牙，每個節點對數據項的訪問服從Zipf分布,θ=0181.實驗分別基于節點的緩存大小為2MB、3MB、4MB、5MB、6MB、7MB、8MB、9MB、10MB的情況對性能指標進行測試.

緩存成功率的比較：圖1反映了各種算法在不同緩存下緩存成功率，當數據比較小和緩存空間比較緊張時，緩存替換不會很頻繁的進行.因此，傳統的緩存替換策略成功率只比本文提出的策略低10%～20%.然而，隨著緩存變大，如在緩存大小為5M時，其緩存成功率比LRU高出約12%，比FIFO高出約14%左右，而在緩存大小為10M時CRPBOU緩存成功率比LRU與FIFO分別約高出18%～20%，與GreedyDualSize相比性能大約提高5%～8%.

緩存數據訪問延時的比較：圖2反映了各種算法數據訪問延時.隨著緩存大小不斷增加時，LRU、FIFO和GreedyDualSize的數據訪問延遲也不斷的增加，而CRPBOU則基本沒有太大的波動.

緩存數據替換次數的比較：圖3反映了各種算法數據替換次數.CRPBOU的數據替換次數介于LRU和FIFO之間，隨著緩存變大，數據替換逐步遞減，CRPBOU在數據替換次數上沒有GreedyDualSize出色，但是仍然高于FIFO和LRU.

圖1 緩存成功率比較

圖2 緩存數據訪問延時比較

圖3 緩存數據替換次數比較

3 結論

目前機會網絡受到了廣大研究者的關注，并且在國外已出現了一些基于機會網絡的具體應用[11,12].本文對機會網絡中緩存替換策略進行了深入研究，現有大多數緩存替換策略并未考慮節點流行度和機會路徑.與之不同的是，本文針對機會網絡中緩存空間不足，提出一個基于效用的概率緩存替換策略，仿真數據分析表明與目前常用緩存替換策略相比，表現出對機會網絡數據通信特點具有良好的適應能力，能夠有效地提高數據項的緩存命中率，并降低端到端的數據訪問延遲.