基于效用的機會網(wǎng)絡緩存替換策略?

周盼，張振宇

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

0 引言

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

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

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

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

1 緩存設計

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

1.1 數(shù)據(jù)流行度

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

1.2 機會路徑

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

1.3 基本策略

當兩個緩存節(jié)點A和B接觸時，機會的發(fā)生緩存替換，兩個節(jié)點通過交換緩存數(shù)據(jù)來優(yōu)化所累計的數(shù)據(jù)訪問延遲，并制定以下緩存策略：

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

1.4 概率選擇算法

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

緩存替換策略只優(yōu)化了兩個接觸的緩存節(jié)點在本地范圍內(nèi)的數(shù)據(jù)訪問延遲.機會網(wǎng)絡中，全局范圍優(yōu)化具有挑戰(zhàn)性，因為維持網(wǎng)絡中的緩存數(shù)據(jù)副本的數(shù)量是很困難的，從而提出了一個概率策略來控制全局范圍的緩存數(shù)據(jù)的副本數(shù)量.通過提出概率策略，在緩存選擇中，我們?nèi)匀粌?yōu)先考慮效用值高的流行數(shù)據(jù)，同時確保低流行度的數(shù)據(jù)能有機會被緩存.以下為概率數(shù)據(jù)選擇算法

2 實驗結(jié)果與分析

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

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

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

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

圖1 緩存成功率比較

圖2 緩存數(shù)據(jù)訪問延時比較

圖3 緩存數(shù)據(jù)替換次數(shù)比較

3 結(jié)論

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