周盼,張振宇
(新疆大學 信息科學與工程學院,新疆 烏魯木齊830046)
隨著無線自組網(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é)點的緩存空間緊張問題.
首先詳細說明基本設計思路,隨后討論了實現(xiàn)方面具體涉及的問題.本文基于數(shù)據(jù)項的效用值這一標準來對數(shù)據(jù)進行替換,通過流行度和機會路徑這兩個指標算出數(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ù)請求的兩個時間值,并可以忽略不計空間上的開銷.
首先定義機會接觸圖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ù)為機會路徑為
當兩個緩存節(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ī)劃方法解決.
在緩存替換過程中,緩存數(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ù)選擇算法
用本文提出的緩存替換策略(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ù)比較
目前機會網(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ù)訪問延遲.