移動Ad Hoc網絡下協作緩存策略研究

蔣 泉，潘沛生

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

0 引 言

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

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

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

1 Adaptive緩存策略

1.1 系統模型

圖1顯示了自組織網絡的一部分，其中的一些移動節點具有類似于衛星網絡中連接其他網絡的外部接口。這些接口可用作網關，允許其他節點與外部網絡進行通信。數據中心可以駐留在MANET內部或者外部，移動節點可以從數據中心讀取數據。

圖1 MANET網絡系統模型

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

1.2 基本協作緩存

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

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

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

(1)

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

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

1.3 Adaptive緩存算法

Data-Cache和Path-Cache都只能適用于一種特殊的MANET環境，當面臨它們不擅長的環境時，基本方案不僅發揮不了它們的優勢，有時更是適得其反，增加了網絡的擁塞，降低網絡的吞吐量，增加了查詢延遲和能量損耗。

為此，在結合兩種基本緩存方案優勢的基礎上，提出了一種Adaptive緩存放置策略。該策略的思想為，當數據項到達節點時，該節點可以動態地依據某些標準來采用Data-Cache方案或者Path-Cache方案，或者是不進行緩存而轉發。這些標準應該包括數據項的大小Si，TTL持續時間TTLi以及Hsave。系統會分配給每個節點有關這三個標準的閾值[10]，分別為：Ts，TTTL，TH。

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

圖2 Adaptive算法流程

2 E-COOP緩存策略

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

COOP方案中節點的協作區域由1-Hop范圍內的鄰節點組成。其執行過程如下：請求節點發出請求，若本地緩存持有請求數據，則會直接響應；否則請求節點在1-Hop區域內廣播請求信息；如果請求數據不在協作區域內，請求節點進行Hop-by-Hop方案將請求消息發往數據中心。

2.1 E-COOP系統架構

E-COOP系統架構如圖3所示，它駐留在網絡層與應用層之間，為應用層的用戶請求和網絡層的通信提供代理作用。

圖3 E-COOP系統架構

E-COOP的執行過程如下：當節點發出一個數據請求時，其先在本地緩存中查找，如果本地緩存能夠提取數據，則用戶直接訪問，否則，請求節點在協作區域內廣播數據請求，如果數據不在協作區域內，請求信息以Hop-by-Hop方案轉發至數據中心。如果在轉發過程中，節點為核心節點，則查詢該節點1-Hop范圍內鄰節點的緩存目錄，發現請求數據時，響應請求節點并停止轉發。

2.2 核心節點選擇模型

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

(2)

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

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

2.3 E-COOP緩存替換策略

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

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

(3)

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

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

3 仿真與性能分析

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

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

(4)

其中，n為數據中心的第n個數據項，當θ=1時，訪問模型遵循嚴格的Zipf分布，當θ=0時，訪問模型遵循均勻分布，θ越大，分布函數越“扭曲”。

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

圖4 平均響應延遲的比較

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

圖5 平均能耗的比較

4 結束語

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

參考文獻：

[1] 張 鵬,孫 磊,崔 勇，等.移動自組網安全技術研究[J].計算機科學,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網絡AODV路由協議的改進[J].計算機應用,2010,30(2):333-336.

[5] 王北光,李立新,謝 濤.移動Ad Hoc網絡DSR路由協議的改進[J].計算機技術與發展,2011,21(8):121-124.

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

的協作緩存策略[J].通信學報,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典型路由協議的性能分析與仿真[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] 楊春貴,吳產樂,彭鴻雁.一種有效的Web代理緩存替換算法[J].計算機工程,2007,33(3):43-44.

[12] 陳亞軍,肖建華.基于NS-2的網絡仿真與擴展[J].計算機系統應用,2005,14(5):84-87.

[13] 王 輝.NS-2網絡模擬器的原理和應用[M].西安:西北工業大學出版社,2008.

[14] 李 浩,高澤華,高 峰,等.IEEE802.11無線局域網標準研究[J].計算機應用研究,2009,26(5):1616-1620.

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