周盼，張振宇

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

0 引言

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

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

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

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

1 緩存設(shè)計(jì)

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

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

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

1.2 機(jī)會(huì)路徑

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

1.3 基本策略

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

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

1.4 概率選擇算法

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

緩存數(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ù)訪問延時(shí)比較

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

3 結(jié)論

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