移動Ad Hoc網(wǎng)絡(luò)下協(xié)作緩存策略研究

蔣 泉，潘沛生

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210003)

0 引 言

移動自組織網(wǎng)絡(luò)[1](mobile Ad Hoc networks,MANET)，是一種與傳統(tǒng)的有基站網(wǎng)絡(luò)相對的無中心移動網(wǎng)絡(luò)，MANET網(wǎng)絡(luò)可以應(yīng)用在無法架設(shè)基礎(chǔ)設(shè)施或者基礎(chǔ)設(shè)施昂貴的環(huán)境中，因此，開展MANET的研究具有很高的科學(xué)價值，同時也能夠產(chǎn)生較好的社會經(jīng)濟(jì)效益。目前，國內(nèi)外對于MANET的研究重心大多放在動態(tài)路由協(xié)議的開發(fā)上。例如，Maheswary A等[2]提出在路由協(xié)議中添加加密信件來確保MANET路由協(xié)議的安全；Dodke S等[3]研究了無線自組網(wǎng)按需平面向量協(xié)議(Ad Hoc on-demand distance vector routing,AODV)[4]和動態(tài)源路由協(xié)議(dynamic source routing,DSR)[5],在不同節(jié)點密度的條件下，對比了兩者在端到端延遲、能耗以及數(shù)據(jù)包傳遞率等性能上的優(yōu)劣。

作為MANET網(wǎng)絡(luò)的最終目的，保持移動節(jié)點對數(shù)據(jù)的訪問能力，保證網(wǎng)絡(luò)中數(shù)據(jù)的可用性，依然是研究MANET網(wǎng)絡(luò)的重要內(nèi)容。協(xié)作緩存[6],允許在多個節(jié)點間共享和協(xié)調(diào)緩存數(shù)據(jù)，以提高Web性能。由于無線連接的成本不同于有線連接，所以決定在哪緩存數(shù)據(jù)，如何獲得緩存數(shù)據(jù)將是研究MANET緩存的重要部分。

文中對支持MANET數(shù)據(jù)訪問的協(xié)作緩存放置策略及發(fā)現(xiàn)策略進(jìn)行設(shè)計和評估。提出了兩種基本的緩存放置方案：Data-Cache、Path-Cache，然后根據(jù)兩種基本緩存方案提出一種集基本方案優(yōu)勢于一身的Adaptive緩存放置方案；同時，也將對已有的COOP緩存策略[7]進(jìn)行改進(jìn)優(yōu)化，引入核心節(jié)點的概念，以降低緩存發(fā)現(xiàn)的響應(yīng)延遲和能量損耗，提高網(wǎng)絡(luò)吞吐量。

1 Adaptive緩存策略

1.1 系統(tǒng)模型

圖1顯示了自組織網(wǎng)絡(luò)的一部分，其中的一些移動節(jié)點具有類似于衛(wèi)星網(wǎng)絡(luò)中連接其他網(wǎng)絡(luò)的外部接口。這些接口可用作網(wǎng)關(guān)，允許其他節(jié)點與外部網(wǎng)絡(luò)進(jìn)行通信。數(shù)據(jù)中心可以駐留在MANET內(nèi)部或者外部，移動節(jié)點可以從數(shù)據(jù)中心讀取數(shù)據(jù)。

圖1 MANET網(wǎng)絡(luò)系統(tǒng)模型

在MANET網(wǎng)絡(luò)中，當(dāng)節(jié)點發(fā)出一個數(shù)據(jù)請求時，一般會通過多跳的方式傳到數(shù)據(jù)中心，由數(shù)據(jù)中心發(fā)回所需要的數(shù)據(jù)包。AODV、目標(biāo)序列距離路由矢量算法(destination sequenced distance vector，DSDV)[8]是適用于MANET網(wǎng)絡(luò)的兩種底層路由協(xié)議，它們可以在路由層尋找到達(dá)目的節(jié)點的最佳路徑，盡可能減少帶寬損耗和訪問延遲，但是本身也會存在一些限制。為此，提出兩種基本的協(xié)作緩存方案：Data-Cache和Path-Cache。

1.2 基本協(xié)作緩存

Data-Cache是指節(jié)點緩存流經(jīng)該節(jié)點中流行度較高的數(shù)據(jù)項。根據(jù)圖1，假設(shè)N6和N7先后向數(shù)據(jù)中心請求了數(shù)據(jù)項di，在響應(yīng)過程中都經(jīng)過了節(jié)點N5，N5判斷此數(shù)據(jù)項當(dāng)前的流行度較高，于是緩存在本地。此后如果N3、N4或者N5有同樣的請求，就可以直接由N5來服務(wù)。在數(shù)據(jù)項到達(dá)時，節(jié)點會首先判斷數(shù)據(jù)項的流行度，再決定是否緩存，但是無論在何種情況下，請求節(jié)點本身都是會緩存所請求的數(shù)據(jù)項。

Path-Cache的思想同樣可以用圖1的模型來說明。節(jié)點N1向數(shù)據(jù)中心請求了數(shù)據(jù)項di，在數(shù)據(jù)源發(fā)回數(shù)據(jù)包時經(jīng)過節(jié)點N3，如果N3緩存了節(jié)點N1的路徑，此后若N2請求di時，N3可以計算出其距離數(shù)據(jù)中心有三跳而距離N1只有短短的一跳(AODV和DSR等都具有計算源節(jié)點到目的節(jié)點跳數(shù)的功能)，這樣N3就會響應(yīng)N1，從而節(jié)省了帶寬和延遲。當(dāng)網(wǎng)絡(luò)拓?fù)湎鄬Ψ€(wěn)定，數(shù)據(jù)更新率較低時，假設(shè)節(jié)點與請求節(jié)點的距離用H(i,j)表示，與數(shù)據(jù)中心的距離用H(i,C)表示，H(i,j)應(yīng)該小于H(i,C)，表示如下:

Hsave=H(i,C)-H(i,j)

(1)

其中，Hsave為減少的跳數(shù)，系統(tǒng)的閾值稱為TH，Hsave在大于TH時可以選擇Path-Cache方案。

每個從數(shù)據(jù)中心發(fā)出的數(shù)據(jù)項都會被分配一個生存時間值[9](time to live，TTL)，并且使用TTL方案來保持客戶端緩存和數(shù)據(jù)中心緩存的一致性。只要緩存時間未超過TTL值，數(shù)據(jù)項就被認(rèn)為是有效的。

1.3 Adaptive緩存算法

Data-Cache和Path-Cache都只能適用于一種特殊的MANET環(huán)境，當(dāng)面臨它們不擅長的環(huán)境時，基本方案不僅發(fā)揮不了它們的優(yōu)勢，有時更是適得其反，增加了網(wǎng)絡(luò)的擁塞，降低網(wǎng)絡(luò)的吞吐量，增加了查詢延遲和能量損耗。

為此，在結(jié)合兩種基本緩存方案優(yōu)勢的基礎(chǔ)上，提出了一種Adaptive緩存放置策略。該策略的思想為，當(dāng)數(shù)據(jù)項到達(dá)節(jié)點時，該節(jié)點可以動態(tài)地依據(jù)某些標(biāo)準(zhǔn)來采用Data-Cache方案或者Path-Cache方案，或者是不進(jìn)行緩存而轉(zhuǎn)發(fā)。這些標(biāo)準(zhǔn)應(yīng)該包括數(shù)據(jù)項的大小Si，TTL持續(xù)時間TTLi以及Hsave。系統(tǒng)會分配給每個節(jié)點有關(guān)這三個標(biāo)準(zhǔn)的閾值[10]，分別為：Ts，TTTL，TH。

由此，提出了Adaptive緩存放置算法，見圖2。

圖2 Adaptive算法流程

2 E-COOP緩存策略

在緩存系統(tǒng)中，有一種常用的緩存發(fā)現(xiàn)策略是Hop-by-Hop策略，當(dāng)數(shù)據(jù)請求在被轉(zhuǎn)發(fā)至數(shù)據(jù)中心的過程中，轉(zhuǎn)發(fā)節(jié)點先檢查其本地的緩存，如果轉(zhuǎn)發(fā)節(jié)點本地有該請求的緩存，則響應(yīng)請求節(jié)點，否則，繼續(xù)轉(zhuǎn)發(fā)至數(shù)據(jù)中心。但是隨著請求節(jié)點與數(shù)據(jù)中心的跳數(shù)增加，網(wǎng)絡(luò)連接的可靠性和吞吐量將會下降。而COOP緩存發(fā)現(xiàn)策略，利用了興趣局部性原理，即相鄰節(jié)點間可能存在同樣的需求，請求節(jié)點先以限制性洪泛法在其鄰居節(jié)點中查找數(shù)據(jù)，如果沒有，再以Hop-by-Hop的方案查找。E-COOP緩存發(fā)現(xiàn)策略是對COOP緩存發(fā)現(xiàn)策略的改進(jìn)，它不僅發(fā)揮了協(xié)作緩存提取數(shù)據(jù)的優(yōu)勢，更是引入了核心節(jié)點，提高緩存的發(fā)現(xiàn)效率。

COOP方案中節(jié)點的協(xié)作區(qū)域由1-Hop范圍內(nèi)的鄰節(jié)點組成。其執(zhí)行過程如下：請求節(jié)點發(fā)出請求，若本地緩存持有請求數(shù)據(jù)，則會直接響應(yīng)；否則請求節(jié)點在1-Hop區(qū)域內(nèi)廣播請求信息；如果請求數(shù)據(jù)不在協(xié)作區(qū)域內(nèi)，請求節(jié)點進(jìn)行Hop-by-Hop方案將請求消息發(fā)往數(shù)據(jù)中心。

2.1 E-COOP系統(tǒng)架構(gòu)

E-COOP系統(tǒng)架構(gòu)如圖3所示，它駐留在網(wǎng)絡(luò)層與應(yīng)用層之間，為應(yīng)用層的用戶請求和網(wǎng)絡(luò)層的通信提供代理作用。

圖3 E-COOP系統(tǒng)架構(gòu)

E-COOP的執(zhí)行過程如下：當(dāng)節(jié)點發(fā)出一個數(shù)據(jù)請求時，其先在本地緩存中查找，如果本地緩存能夠提取數(shù)據(jù)，則用戶直接訪問，否則，請求節(jié)點在協(xié)作區(qū)域內(nèi)廣播數(shù)據(jù)請求，如果數(shù)據(jù)不在協(xié)作區(qū)域內(nèi)，請求信息以Hop-by-Hop方案轉(zhuǎn)發(fā)至數(shù)據(jù)中心。如果在轉(zhuǎn)發(fā)過程中，節(jié)點為核心節(jié)點，則查詢該節(jié)點1-Hop范圍內(nèi)鄰節(jié)點的緩存目錄，發(fā)現(xiàn)請求數(shù)據(jù)時，響應(yīng)請求節(jié)點并停止轉(zhuǎn)發(fā)。

2.2 核心節(jié)點選擇模型

假設(shè)V={v1,v2,…,vN}是MANET網(wǎng)絡(luò)中節(jié)點的集合，λuv為節(jié)點u和節(jié)點v之間最短路徑的條數(shù)，λuv(ω)為從節(jié)點u到節(jié)點v最短路徑且經(jīng)過節(jié)點w∈V的條數(shù)。節(jié)點w∈V的重要程度為：

(2)

其中，Ew為節(jié)點w剩余的能量；γ為大于等于0的常數(shù)，對于能量敏感的MANET網(wǎng)絡(luò)，γ的值可以設(shè)得較大。一個節(jié)點的重要程度越大，說明這個節(jié)點可以以相對短的路徑到達(dá)其他節(jié)點并且這個節(jié)點的剩余能量相對較高。

在MANET中，每個節(jié)點都可以獲取其一跳范圍內(nèi)的其他鄰節(jié)點信息(通過周期性的請求數(shù)據(jù)包獲得)，包括周圍節(jié)點所持有的數(shù)據(jù)項ID、數(shù)據(jù)項的TTL值、節(jié)點的剩余能量等。節(jié)點會周期性計算周圍節(jié)點和本節(jié)點的重要程度K，如果本節(jié)點與周圍其他節(jié)點相比重要度較大，則該節(jié)點是核心節(jié)點，否則為普通節(jié)點。

2.3 E-COOP緩存替換策略

由于緩存空間的有限性，當(dāng)一個新的數(shù)據(jù)項要被緩存，而緩存空間不足時，必然要有舊的緩存被踢出，緩存替換策略[11]就是研究如何替換舊的緩存。緩存替換的目的是增加系統(tǒng)緩存的命中率，這很大程度上取決于緩存的容量，對于協(xié)作緩存而言，緩存替換考慮的不僅僅是本地緩存的命中率，而是整個MANET緩存系統(tǒng)。因此，E-COOP緩存替換策略試著減少協(xié)作區(qū)域中緩存數(shù)據(jù)的副本數(shù)量，從而最優(yōu)化緩存系統(tǒng)。由于在Adaptive緩存放置算法中，當(dāng)節(jié)點需要緩存的數(shù)據(jù)項事先存在于節(jié)點時，節(jié)點只會更新其TTL值而不會實際再次緩存數(shù)據(jù)副本，這樣做的好處之一就是節(jié)省了緩存控件，減少冗余。

E-COOP策略會將緩存數(shù)據(jù)標(biāo)記為主要副本和次要副本。當(dāng)節(jié)點獲取到數(shù)據(jù)時，如果該數(shù)據(jù)來自協(xié)作區(qū)域以外，則該數(shù)據(jù)標(biāo)記為主要副本。否則，如果該數(shù)據(jù)來自協(xié)作區(qū)域內(nèi)，需要進(jìn)一步考慮其主次性：如果在之前的請求，該數(shù)據(jù)已經(jīng)被標(biāo)記為主要副本，考慮到減少副本的數(shù)量，所以這次的請求標(biāo)記其為次要副本。另一方面，該數(shù)據(jù)前一次請求時被標(biāo)記為次要副本，則本次請求被標(biāo)記為主要副本。E-COOP區(qū)分緩存數(shù)據(jù)的原因是減少緩存缺失的成本，跟隨節(jié)點的流行趨勢而應(yīng)需緩存。E-COOP緩存替換執(zhí)行過程如下：(1)當(dāng)緩存空間滿時，先踢出空間中的次要副本，如果剩余空間能夠滿足新的緩存數(shù)據(jù)，則進(jìn)行緩存，否則進(jìn)入(2)；(2)節(jié)點為每個緩存空間中的主要副本i計算成本函數(shù)cost(i)，如下：

(3)

其中，Si為數(shù)據(jù)項i的大小;TTLi為數(shù)據(jù)項的生存值;Tkth-access為主要副本i第k次被訪問的時間戳。

選擇cost(i)值最大的副本進(jìn)行替換。將該副本被替換的消息發(fā)送給核心節(jié)點，由核心節(jié)點更新1-Hop鄰節(jié)點緩存目錄。

3 仿真與性能分析

在Linux平臺上使用NS-2[12]仿真器中的CMU無線擴(kuò)展模型[13]進(jìn)行網(wǎng)絡(luò)仿真，仿真區(qū)域為500 m×1 500 m，50個節(jié)點在區(qū)域內(nèi)隨機(jī)移動，節(jié)點移動速度范圍在0～20 m/s，信道的帶寬為2 Mb/s，節(jié)點的通信范圍為250 m，無線傳播模型為Two Ray Ground，節(jié)點采用全向天線(OmniAntenna)，隊列為PriQueue，底層路由協(xié)議為AODV，MAC層協(xié)議為IEEE802.11[14]，數(shù)據(jù)項的大小范圍在1～10 KB之間，鄰節(jié)點范圍為1-Hop。Adaptive緩存的閾值設(shè)置為：TH=2，Ts=4.4，TTTL=5 000(閾值根據(jù)相同環(huán)境仿真得來)。

客戶端訪問模型基于Zifp-like[15]函數(shù)，每個節(jié)點產(chǎn)生一個可讀查詢，產(chǎn)生時間服從均值為Tquery的指數(shù)分布。Zifp-like經(jīng)常用來模擬不均勻的分布模型，在Zifp-like模型中，節(jié)點緩存第i(1≤i≤n)個來訪數(shù)據(jù)項的概率遵循：

(4)

其中，n為數(shù)據(jù)中心的第n個數(shù)據(jù)項，當(dāng)θ=1時，訪問模型遵循嚴(yán)格的Zipf分布，當(dāng)θ=0時，訪問模型遵循均勻分布，θ越大，分布函數(shù)越“扭曲”。

從圖4可以看出，隨著緩存空間的增大，所有方案的平均延遲都會減小，因為緩存空間可以存儲更多的數(shù)據(jù)項，在請求發(fā)往數(shù)據(jù)中心的過程中，更加容易命中，所以響應(yīng)的延遲就會縮短。同時，由于引入核心節(jié)點，E-COOP緩存策略要優(yōu)于其他三種方案。E-COOP與COOP緩存策略兩條曲線近似平行，說明在E-COOP緩存策略中引入核心節(jié)點，緩存系統(tǒng)整體平均延遲有所降低，而并非在特定的某個點。

圖4 平均響應(yīng)延遲的比較

從圖5可以看出，緩存空間越大，能量的消耗就越小，因為節(jié)點可以緩存更多的數(shù)據(jù)項，高概率地在本節(jié)點或者轉(zhuǎn)發(fā)節(jié)點處獲得請求數(shù)據(jù)。同時，E-COOP緩存策略能耗低于COOP緩存策略的能耗，前者的響應(yīng)延遲又比后者低，所以經(jīng)過仿真表明，E-COOP緩存策略的確比現(xiàn)有的COOP緩存策略更具有優(yōu)越性。

圖5 平均能耗的比較

4 結(jié)束語

Adaptive緩存放置策略很好地結(jié)合了Data-Cache以及Path-Cache的優(yōu)勢，同時規(guī)避了它們的缺點，在緩存放置方面，充分考慮了相鄰節(jié)點可能具有相同需求的實際情況，各移動節(jié)點相互協(xié)作，數(shù)據(jù)共享，推進(jìn)整體網(wǎng)絡(luò)性能的提升，其中包括網(wǎng)絡(luò)吞吐量的提升、鏈路斷裂概率的降低等。E-COOP緩存發(fā)現(xiàn)策略在現(xiàn)有的COOP緩存發(fā)現(xiàn)策略的基礎(chǔ)上引進(jìn)了核心節(jié)點，提升普通節(jié)點發(fā)現(xiàn)請求數(shù)據(jù)的概率。在保證不增加能量的前提下，盡可能地降低緩存發(fā)現(xiàn)的延遲。同時，E-COOP緩存替換策略通過減少數(shù)據(jù)項副本的方法，減少冗余，提高請求響應(yīng)效率。兩種方案相結(jié)合，在緩存放置和發(fā)現(xiàn)過程都充分利用了鄰節(jié)點資源，提升了移動Ad Hoc網(wǎng)絡(luò)的緩存性能。

參考文獻(xiàn)：

[1] 張 鵬,孫 磊,崔 勇，等.移動自組網(wǎng)安全技術(shù)研究[J].計算機(jī)科學(xué),2009,36(7):1-7.

[2] MAHESWARY A,BASKAR S.Letter to shape encryption for securing MANET routing protocols[C]//IEEE international conference on computational intelligence and computing research.Chennai,India:IEEE,2016.

[3] DODKE S,MANE P B,VANJALE M S.A survey on energy efficient routing protocol for MANET[C]//2nd international conference on applied and theoretical computing and communication technology.Bangalore,India:IEEE,2016:160-164.

[4] 王忠恒,張曦煌.移動Ad Hoc網(wǎng)絡(luò)AODV路由協(xié)議的改進(jìn)[J].計算機(jī)應(yīng)用,2010,30(2):333-336.

[5] 王北光,李立新,謝 濤.移動Ad Hoc網(wǎng)絡(luò)DSR路由協(xié)議的改進(jìn)[J].計算機(jī)技術(shù)與發(fā)展,2011,21(8):121-124.

[6] 劉銀龍,汪 敏,馬 偉,等.PSP緩存系統(tǒng)中總開銷最小

的協(xié)作緩存策略[J].通信學(xué)報,2015,36(3):86-93.

[7] DU Yu,GUPTA S K S.COOP:a cooperative caching service in MANETs[C]//Joint international conference on autonomic and autonomous systems and international conference on networking and services.Papeete,Tahiti,French Polynesia:IEEE，2005.

[8] 許重球,李臘元.MANET典型路由協(xié)議的性能分析與仿真[J].計算機(jī)工程,2008,34(12):97-99.

[9] KARAULIA D S,BHAROT N.Dynamic TTL variance foretelling based enhancement of AODV routing protocol in MANET[C]//Fourth International conference on communication system and network technologies.Bhopal,India:IEEE,2014:244-248.

[10] YIN Liangzhong,CAO Guohong.Supporting cooperative ca-ching in Ad Hoc networks[J].IEEE Transactions on Mobile Computing,2006,5(1):77-89.

[11] 楊春貴,吳產(chǎn)樂,彭鴻雁.一種有效的Web代理緩存替換算法[J].計算機(jī)工程,2007,33(3):43-44.

[12] 陳亞軍,肖建華.基于NS-2的網(wǎng)絡(luò)仿真與擴(kuò)展[J].計算機(jī)系統(tǒng)應(yīng)用,2005,14(5):84-87.

[13] 王 輝.NS-2網(wǎng)絡(luò)模擬器的原理和應(yīng)用[M].西安:西北工業(yè)大學(xué)出版社,2008.

[14] 李 浩,高澤華,高 峰,等.IEEE802.11無線局域網(wǎng)標(biāo)準(zhǔn)研究[J].計算機(jī)應(yīng)用研究,2009,26(5):1616-1620.

[15] 游榮彥.Zipf定律與漢字字頻分布[J].中文信息學(xué)報,2000,14(3):60-65.