基于流行度及最小訪問代價的MP2P協(xié)同緩存優(yōu)化策略＊

周欣欣，余鎮(zhèn)危

（1.中國礦業(yè)大學機電與信息工程學院，北京100083；2.東北電力大學信息工程學院，吉林 吉林132012）

1 引言

隨著無線通信技術的快速發(fā)展、移動設備性能的不斷提高與普及，移動用戶隨時隨地交換和處理信息成為現(xiàn)實，結合無線技術和點對點P2P（Peerto－Peer）計算的移動對等網(wǎng) MP2P（Mobile Peerto－Peer Networks）成為了當前無線網(wǎng)絡的研究熱點。然而，由于移動網(wǎng)絡環(huán)境所固有的缺陷和特點，如節(jié)點的頻繁移動、移動設備能量和資源的短缺、無線連接的不可靠以及有線的通信帶寬等特點，為移動P2P網(wǎng)絡帶來了巨大的技術挑戰(zhàn)，如何在移動P2P網(wǎng)絡上實現(xiàn)高效的數(shù)據(jù)存取是一個非常值得研究的問題。研究表明，高效的協(xié)同緩存策略能夠大大降低用戶的反應時間和服務延遲、減少網(wǎng)絡通信開銷、節(jié)省移動設備的電能消耗、增大網(wǎng)絡的吞吐率，既提高了移動數(shù)據(jù)訪問的性能，又增加了網(wǎng)絡的可用性。因此，有必要針對移動P2P網(wǎng)絡的特點設計適合的協(xié)同緩存策略。

鑒于此，本文針對移動P2P網(wǎng)絡，提出一種基于數(shù)據(jù)流行度的分布式協(xié)同緩存優(yōu)化策略，其主要思想是：通過計算數(shù)據(jù)的流行度以及獲取數(shù)據(jù)的訪問代價，節(jié)點優(yōu)先緩存那些具有較高流行度，并且能夠使網(wǎng)絡訪問代價最大程度降低的數(shù)據(jù)。同已有的緩存替換策略相比，該算法通過節(jié)點間的協(xié)作緩存，降低了全網(wǎng)數(shù)據(jù)訪問代價，從而提高了網(wǎng)絡數(shù)據(jù)的吞吐量，提高了網(wǎng)絡的可用性和可擴展性。

本文組織如下：第2節(jié)給出相關工作，第3節(jié)給出問題定義及分布式緩存優(yōu)化策略，第4節(jié)是仿真實驗及結果分析，第5節(jié)是結束語。

2 相關工作

所謂協(xié)同緩存（Cooperative Caching），即通過將“熱點”信息緩存于不同的節(jié)點，移動用戶可以僅通過訪問周圍最近的緩存節(jié)點獲取服務而省去了訪問信息源節(jié)點的消耗，從而大大降低網(wǎng)絡開銷，提高網(wǎng)絡數(shù)據(jù)存取效率。

Nuggehalli P等［1］證明了求解最優(yōu)緩存放置機制是一個NP完全問題。Tang B等［2］證明了在緩存空間大小的限制下，求解最優(yōu)緩存放置機制同樣是一個NP完全問題。牛新征等［3］利用蟻群算法中螞蟻通過信息素留存尋找最優(yōu)路徑的機制，構造了基于信息素的緩存替換模型。Acharya［4］提出了PIX策略，通過計算數(shù)據(jù)信息的訪問頻率和廣播頻率的關系得到數(shù)據(jù)替換函數(shù)，從而做出替換決定。Khanna［5］則基于訪問趨勢未知的假定提出了Gray替換算法，將數(shù)據(jù)訪問歷史和數(shù)據(jù)獲取時間開銷作為分析參數(shù)。文獻［6～8］討論了無線多跳網(wǎng)絡中的緩存策略，但是他們的策略沒有將數(shù)據(jù)在網(wǎng)間的流行度因素考慮進去。另外，其他緩存策略使用的類似樹形的層次結構，或者網(wǎng)絡中沒有骨干節(jié)點，但這些策略沒有充分考慮節(jié)點擾動因素，或者有些需要額外的基礎設施支持。而本文提出的策略不需要任何額外的基礎設施支持。

3 基于流行度及最小訪問代價的分布式協(xié)同緩存優(yōu)化策略

3.1 問題定義

網(wǎng)絡模型定義為圖G＝ （V，E），其中V ＝｛v1，v2，…，vn｝為網(wǎng)絡節(jié)點集合，E是邊的集合，邊e＝ （vi，vj）∈E ，其中 （vi，vj）∈E表示節(jié)點vi、vj彼此在對方的無線發(fā)射范圍內(nèi)，其中每個節(jié)點v∈V有一定的緩存空間Cv（Cv為緩存片段個數(shù)）。

將文件分劃為n個片段，記為S＝ （s1，s2，…，sn），其中：

定義1 定義流行度函數(shù)p（i）。設每個片段的流行度分別為p（1），p（2），…，p（n）。設To為系統(tǒng)的起始時間；T1（i）為片段i被首次訪問的時間；Tr為系統(tǒng)當前時間；Ni為片段i自To以來被訪問的總次數(shù)，則定義片段i的流行度p（i）＝Ni／（Tr－T1（i））。

定義2 定義節(jié)點v獲取片段si的代價函數(shù)dv（i）。如果si存儲在本地緩存中，dv（i）是0；如果某一節(jié)點w緩存了si，則dv（i）是從節(jié)點v到節(jié)點w的跳數(shù)；如果si是由內(nèi)容服務器提供，則dv（i）等于內(nèi)容服務器接入代價。

重新寫出公式（1），定義K，令：

其中，D（i）是網(wǎng)絡中所有節(jié)點獲得片段si的平均代價。

定義3 定義標志函數(shù)Xv，w（i）。當節(jié)點v發(fā)現(xiàn)節(jié)點w 緩存有片段si，則Xv，w（i）＝1；否則為0。

定義4 定義標志函數(shù)Yv（i）。若節(jié)點v從內(nèi)容服務器上獲得片段si時，則Yv（i）＝1；否則為0。

定義5 定義代價函數(shù)zv，w是由節(jié)點v到節(jié)點w的跳數(shù)。

因此，重新給出D（i）：

由于每個節(jié)點要么從某一個節(jié)點獲取特定片段，要么從內(nèi)容服務器上獲得，因此有：

緩存優(yōu)化問題就轉變成在約束條件下求最小片段訪問代價函數(shù)，即：

3.2 分布式協(xié)同緩存優(yōu)化策略

本節(jié)提出的協(xié)同緩存優(yōu)化策略能夠根據(jù)數(shù)據(jù)的流行度分布式地緩存數(shù)據(jù)。每個節(jié)點保持一個段路由表，類似于網(wǎng)絡路由表，每個段路由表包含SEGMENT、NEXT＿HOP和COST 字段，如表1所示。SEGMENT是數(shù)據(jù)片段的ID。NEXT＿HOP是到達該片段的最短路徑上的下一跳節(jié)點ID，如果該段是本地緩存，就記做LOCAL。如果該段在一定跳數(shù)范圍內(nèi)不能查詢到，記為SERVER。COST是與路由相關聯(lián)的代價花費：當下一跳是LOCAL（即片段在本地緩存中）時，COST為0；當下一跳是節(jié)點時，COST是到達數(shù)據(jù)提供者的總跳數(shù)（即緩存該段的最近的節(jié)點）；當下一跳是SERVER時，COST是一個常數(shù)，表示服務器訪問成本。例如，在表1中，獲取片段ID為2和3的成本分別是1和6。

Table 1 NODE 1segment routing table表1 NODE 1段路由表

當新節(jié)點加入網(wǎng)絡時，要執(zhí)行以下步驟：

步驟1 廣播一個“加入”消息，通過收到鄰居節(jié)點的應答消息，建立鄰居節(jié)點列表，廣播節(jié)點的段路由表。

步驟2 節(jié)點根據(jù)已知的段路由表計算到每個數(shù)據(jù)片段的最短路徑，創(chuàng)建自己的段路由表，即若該節(jié)點的某一鄰居節(jié)點以代價K獲得片段si，則加入節(jié)點將以K＋1的代價獲取si，并將下一跳設置為該鄰居。除此之外，加入節(jié)點也可能通過訪問內(nèi)容服務器來獲取該片段，服務器接入代價為α。加入節(jié)點只需在所有選擇中找出最便宜的訪問代價，并建立路由表項。

步驟3 加入節(jié)點也可能根據(jù)已知信息創(chuàng)建新的最短路徑，在新的路由表中，若片段si相對應的成本為K，那么該節(jié)點的鄰居節(jié)點將以代價K＋1獲取si，并將下一跳設置為該加入節(jié)點，同時將更新信息發(fā)送給它的所有鄰居節(jié)點。

步驟4 通過貪心算法，加入節(jié)點決定緩存哪些片段對自己及鄰居最有利，即加入節(jié)點會選擇那些能夠最大程度降低網(wǎng)絡訪問代價的片段緩存。在計算緩存片段si后所降低的網(wǎng)絡訪問代價中，也考慮到片段si在網(wǎng)絡中的流行度p（i）因素。

步驟5 如果一個加入節(jié)點決定緩存片段si，那么它能夠以代價0來獲取該段，并且它的直接鄰居以代價1獲取該片段。假設加入節(jié)點有m個直接鄰居，則在加入節(jié)點本身以及它的鄰居節(jié)點表中si的代價記做Ki0，Ki1，…，Kim。當計算完片段的流行度權重后，加入節(jié)點緩存si可以節(jié)省的訪問代價為：

然而，如果一個鄰居節(jié)點已經(jīng)緩存了片段si，它的代價不應當再被進一步減少變成－1，而應當是0。將這種鄰居節(jié)點的數(shù)目記做θi，則緩存si實際減少的代價Ri應當為：

公式（6）中的各個分量都能夠從段路由表中得到，緩存每個片段所降低的代價都能夠通過計算得到。目標是通過計算Ri，找到Maxmize Ri的片段進行緩存，從而達到降低網(wǎng)絡整體訪問代價，提高網(wǎng)絡吞吐量和可用性的目的。

加入階段和緩存階段之后，節(jié)點定期發(fā)布它的段路由表。當其他節(jié)點偵聽到這一發(fā)布信息后，以類似步驟3的方式通過交叉對比自己的表以及接收到的表來更新自己的本地段路由表，從而各節(jié)點做出緩存策略。

如果節(jié)點超過發(fā)布周期仍然偵聽不到某一鄰居節(jié)點，則認為該鄰居節(jié)點失效或者已經(jīng)離開網(wǎng)絡。如果失效的鄰居節(jié)點是該節(jié)點段路由表中的下一跳節(jié)點，則該節(jié)點通過重新計算形成新的段路由表。

節(jié)點的離開或失效可能導致段路由表的沖突。例如，當節(jié)點v偵聽到節(jié)點w的發(fā)布信息，對于節(jié)點v的段路由表中NEXT＿HOP是節(jié)點w并且代價為K，但是在節(jié)點w發(fā)布的段路由表中，同樣的片段代價可能會出現(xiàn)K－1或者更少的代價。在這種情況下，節(jié)點v中導致沖突的表項失效，需要重新計算并形成新的段路由表。

通過以上分析可以看出，無論是節(jié)點加入階段還是發(fā)布階段，節(jié)點的每個緩存決策對于整個網(wǎng)絡來講，都有一個至少是1的代價的降低。因此，作為節(jié)點的加入和通信，網(wǎng)絡花費將會達到一個本地最小。另一方面，文中提出的分布式緩存策略不依賴于任何路由協(xié)議，可以在路由請求和應答消息中捎帶段路由表信息，因此可以進一步減少整個網(wǎng)絡的通信開銷。

4 仿真結果分析

4.1 仿真環(huán)境

為了驗證緩存優(yōu)化策略的有效性，利用網(wǎng)絡仿真軟件NS－2對其進行了仿真實驗。實驗中，所有節(jié)點隨機加入網(wǎng)絡，并且節(jié)點的通信范圍是固定的，每個節(jié)點的發(fā)布周期是固定的，網(wǎng)絡規(guī)模為400m×400m的正方形區(qū)域，節(jié)點的移動符合隨機?？奎c（Random Waypoint）模型［9］，節(jié)點數(shù)目為100，節(jié)點的通信距離為30m，廣播周期為1秒，節(jié)點平均生命周期為100分鐘，每個文件分割片段數(shù)為15個，節(jié)點緩存片段數(shù)為4個，服務器獲取數(shù)據(jù)代價為6。下面將文中提出的緩存優(yōu)化策略與LRU和LFU算法進行分析比較。

4.2 仿真結果分析

在仿真實驗中，分別對網(wǎng)絡代價開銷、平均時延、平均跳數(shù)以及緩存容量等進行性能上的分析比較。圖1是三種算法的平均網(wǎng)絡代價比較。從圖1可以看出，隨著網(wǎng)絡節(jié)點數(shù)目的增多，文中所提策略的平均網(wǎng)絡代價要小于另外兩種算法，這是由于隨著網(wǎng)絡節(jié)點數(shù)量的增多，有更多的用戶緩存和共享數(shù)據(jù)段。圖2是數(shù)據(jù)訪問平均時延的比較，可以看出，LRU和LFU兩種算法的平均時延均要高于本文提出的算法。

Figure 1 Comparison of network cost圖1 網(wǎng)絡代價比較

圖3 是獲取緩存片段的平均跳數(shù)，結果顯示，90%以上的緩存片段可以在本地或者一跳鄰居處獲得，因此可以大大減小網(wǎng)絡開銷以及延遲。圖4是節(jié)點緩存容量對網(wǎng)絡代價的影響，如圖4顯示，隨著緩存容量的增大，網(wǎng)絡平均代價開銷顯著降低，這表明文中提出的緩存策略具有較高的靈活性。

Figure 2 Comparison of average latency圖2 網(wǎng)絡延遲比較

本文提出的算法在緩存時考慮到片段的流行度以及所產(chǎn)生的網(wǎng)絡代價最小等因素，能夠將流行度高的數(shù)據(jù)優(yōu)先緩存，并且要緩存那些能夠最大限度減少網(wǎng)絡代價花費的數(shù)據(jù)，因此在網(wǎng)絡開銷、訪問時延等方面均獲得了較好的結果。

5 結束語

本文提出了移動P2P網(wǎng)絡協(xié)同緩存優(yōu)化策略，該策略能夠綜合考慮數(shù)據(jù)在網(wǎng)絡中的流行度因素，并且能夠使全網(wǎng)數(shù)據(jù)訪問代價最低，提高了節(jié)點數(shù)據(jù)獲取效率，降低了數(shù)據(jù)訪問時延，提高了網(wǎng)絡可用性及可擴展性。仿真實驗結果表明，文中提出的策略具有高效率、低成本及高可擴展性的特點，取得了較好的結果。

本文提出的算法對服務器獲取數(shù)據(jù)代價采取了固定值，并沒有對該服務器代價進行系統(tǒng)研究；另外，實驗中沒有考慮節(jié)點的任意加入和退出等網(wǎng)絡的不穩(wěn)定性對算法造成的影響，因此下一步的工作主要著重解決以上幾個問題。

［1］ Nuggehalli P，Srinivasan V，Chiasserini C.Energy－efficient caching strategies in ad hoc wireless networks［C］∥Proc of the 4th ACM International Symposium on Mobile Ad Hoc Networking＆Computing，2003：25－33.

［2］ Tang B，Gupta H，Das S.Benefit－based data caching in ad hoc networks［J］.IEEE Transcations on Mobile Computing，2008，3（7）：289－304.

［3］ Niu Xin－zheng，She Kun，Qin Ke，et al.A cooperative caching optimized policy of mobile peer－to－peer networks［J］.Journal of Computer Research and Development，2008，45（4）：656－665.（in Chinese）

［4］ Acharya A，Alonso R，F(xiàn)ranklin M，et al.Broadcast disks：Data management for asymmetric communications environments［C］∥Proc of ACM SIGMOD Conference on Management of Data，1995：199－210.

［5］ Khanna S，Liberatore V.On broadcast disk paging［J］.SIAM Journal on Computing，2000，29（5）：1683－1702.

［6］ Ting Y－W，Chang Y－K.A novel cooperative caching scheme for wireless ad hoc networks：Groupcaching［C］∥Proc of International Conference on NAS，2007：62－68.

［7］ Yin L，Cao G.Supporting cooperative caching in ad hoc networks［J］.IEEE Transcations on Mobile Computing，2006，5（1）：77－89.

［8］ Dogar F R，Phanishayee A，Pucha H，et al.Ditto：A system for opportunistic caching in multi－h(huán)op wireless networks［C］∥Proc of the 14th ACM International Conference on Mobile Computing and Networking，2008：279－290.

［9］ Burgess J，Gallagher B，Jensen D，et al.Maxprop：Routing for vehicle－based disruption tolerant networks［C］∥Proc of IEEE Infocom Bacelona，2006：1－11.

附中文參考文獻：

［3］ 牛新征，佘堃，秦科，等.移動P2P網(wǎng)絡的協(xié)作緩存優(yōu)化策略［J］.計算機研究與發(fā)展，2008，45（4）：656－665.