移動機會網絡中接觸時間感知的協作緩存策略

鄭 嘯 高 漢 王修君 秦 鋒

(安徽工業大學計算機科學與技術學院 安徽馬鞍山 243002)(xzheng@ahut.edu.cn)

隨著移動智能終端設備的普及，通過此類終端設備獲取數據服務的需求也變得越來越多.如何快速高效地為移動用戶提供數據服務，降低網絡基礎設施負擔，也備受到人們的關注.協作緩存技術通過在網絡中選取一組節點作為緩存節點，并讓緩存節點持有原始數據的拷貝為后續的數據請求提供響應.通過協作緩存技術能夠有效地減少用戶訪問延遲和通信開銷，但如何有效地利用協作緩存技術提高移動環境中數據訪問效率還存在著諸多問題：

1) 移動節點所能夠緩存的數據量是不同的，每個節點緩存數據所能帶來的收益也是不同的，因此必須合理地選擇數據緩存節點來進行數據緩存.

2) 移動環境中的節點具有高度自主移動性，這使得節點間接觸時間各不相同，且具有一定的限制.當網絡中數據量較大時往往不能夠在一次接觸過程中傳輸完成，造成節點間接觸機會的浪費.

3) 移動環境中的節點往往是由手持智能終端設備扮演，因此存在緩存容量受限的問題.當節點緩存過多數據而導致無法在一次接觸中完成傳輸時，則會對緩存空間造成浪費.因此，要合理確定緩存節點的緩存邊界以限定節點的緩存數據量，從而減少緩存空間的消耗和浪費.

針對上述問題，本文提出了相應的對策：

1) 移動機會網絡中節點之間的連接是間斷的、不連續的，因此節點之間的連通性十分重要.本文根據節點聯通性提出了一個度量標準來評判節點的重要程度，并以此來解決緩存節點的選擇問題.

2) 由于接觸時間的限制，數據無法在一次接觸過程中傳輸完成.本文通過對數據進行分片處理來降低接觸時間的影響，并為每個節點確定緩存邊界來合理利用節點中有限的緩存空間.

1 相關工作

在移動機會網絡中，節點具有高度的自主移動性，使得網絡拓撲結構動態變化，如何合理有效地放置緩存數據提高用戶獲取內容資源和網絡資源的利用率得到了普遍的關注.文獻[1-3]根據節點的位置將網絡拓撲結構劃分為多個協作區域，并通過緩存控制判斷是否接納數據，最后由區域中心分配數據緩存節點.但是中心節點必須保存組內節點已緩存數據的信息，來避免組內緩存數據的重復問題.劉外喜等人[4]提出了一種在分布式緩存機制中嵌入中心式緩存決策的機制，它把內容的放置、發現、替換統一起來考慮，實現內容的有序緩存.Wei等人[5]提出了一種支持平等性感知的協作緩存協議，通過選取節點的親密節點集合來緩存數據并實現協作的功能.文獻[6]為提高命名數據網絡(named data networking, NDN)中的緩存利用率，提出了一種基于蟻群替換算法的鄰居協作緩存管理策略.文獻[7]通過對高熱度內容進行分布式緩存實現緩存節點間的協作，并在內容請求過程中利用跟蹤節點實現緩存內容的定位.文獻[8]提出一種基于緩存遷移的協作緩存機制，在緩存節點選擇時考慮節點的中心性,保證內容盡可能緩存在位置更重要的節點.Nuggehalli等人[9]和Tang等人[10]對緩存放置問題進行了數學建模,并研究了緩存放置問題的計算復雜度,最后給出了求解緩存放置問題的近似算法.文獻[11]建立了移動節點緩存容量的預測模型，并提出了基于蟻群算法的協作緩存策略.上述文獻都很好地解決了移動環境中協作緩存的問題，但都沒有考慮到節點間接觸時間對緩存的影響.文獻[12]利用已有的節點接觸模型以及節點接觸時間持續模型提出了基于社會網絡的數據協同緩存策略，在該方案中解決了節點接觸時間對緩存的影響，但沒有考慮數據恢復時遇到的贈券收集問題.文獻[13]中考慮了容遲網絡中接觸時間對接觸過程中傳輸數據量的影響，提出了自適應接觸量預測模型，并用實驗驗證了該模型在處理一次接觸中高效傳輸數據的重要性.本文分析了節點間的接觸歷史信息，充分考慮了接觸時間對緩存的影響，提出了接觸時間感知的協作緩存策略.

2 問題定義

2.1 網絡模型

2.2 主要思想及問題

為了提高協作緩存的效率，應當優先選擇具有較高緩存能力的節點作為緩存節點，然而在計算節點的緩存能力時，傳統的解決方案大都假定緩存數據能夠在緩存節點與請求節點間的一次接觸過程中傳輸完成.但是由于節點之間有限的接觸時間使得每次接觸所能傳輸的數據量存在限制，因此這一假設并不存在普適性.由于節點的數據傳輸無法全部完成，當在節點中緩存的數據較多時就會降低緩存的效能.圖1表明了接觸時間對緩存的影響.圖1中節點A為數據請求節點，并且其所請求的數據包含8個數據分片.同時節點A在移動過程中會相繼接觸節點B，C，D，并且在接觸的過程中分別能夠傳輸5個、3個和2個數據分片.在圖1(a)所示的場景中，整個數據被作為一個緩存單元，同時節點B被選擇作為緩存節點.在這種情況下，節點A僅僅能夠通過在與節點B的接觸過程中獲取5個數據分片，另外緩存的3個數據分片并不能獲取，同時由于節點C，D上沒有緩存數據，節點A與節點C，D之間的接觸機會都被浪費，降低了緩存的效率.然而，如圖1(b)所示，若將一個數據分片作為緩存單元并假定節點B緩存5個數據分片，節點C緩存2個，節點D緩存1個，那么整個數據所有的8個數據分片都能夠獲取到，從而能夠恢復所請求的數據.在這種情況下節點的緩存空間以及節點之間接觸機會都得到了更好的利用.基于這一思想，本文必須解決2個問題：

1) 如何根據節點的緩存能力合理地選擇緩存節點.

2) 如何確定緩存節點所能緩存的數據量.

本文提出了一個新的評價標準來計算節點的緩存能力，在此基礎上解決了緩存節點的選擇問題；然后根據每個節點的接觸歷史確定節點的緩存上限，有效地利用節點的緩存空間，同時限定數據在網絡中的副本數量，減少同一數據占用的緩存資源.

Fig. 1 The impact of contact duration on cache nodes圖1 接觸時間對緩存的影響

3 緩存協議設計

本文首先對研究問題進行了分析及形式化描述，并在此基礎上提出了移動環境中接觸時間感知的協作緩存協議.

3.1 問題分析

在移動機會網絡環境中，節點獲取網絡數據大都存在時延，本文假定用戶容忍的最大時延為T.為了有效地評價緩存效率，本文定義在時間限制T內，節點能夠向數據請求者發送的數據包數量為該節點所能獲得的緩存收益.

定義1. 節點緩存收益.節點i為節點j提供數據而獲得的收益Bij定義為

Bij=gsij，

(1)

其中，g為數據包的大小，sij是節點i在時間T內能夠向節點j發送的數據包的個數.

定義2. 區域緩存收益.社區中所有緩存節點在時間T內獲得的緩存收益之和Bcom定義為

(2)

當網絡中區域緩存收益越大時，節點需要從AP上下載數據包的可能性就越小，并能夠減少獲取數據的延遲，提高數據訪問的命中率.

定義3. 緩存代價.網絡中緩存的編碼后的數據包數目與該數據包含的原始數據包數目的比值定義為緩存代價γ.

假設某數據包含8個原始數據包，同時在整個網絡中緩存了16個該數據的編碼數據包，那么該數據的緩存代價γ=16/8=2.

協作緩存的目標是為每個緩存節點確定緩存的數據分片數目以使得區域緩存收益最大，即：

?i,si≤sdata，

(3)

其中,sdata表示數據data所包含的原始數據包數量，si(i=1,2,…,M)表示節點i緩存的編碼數據包的數量.

網絡節點間的數據傳輸發生在節點的接觸過程中，而節點間的接觸往往是間斷性的.為了評價網絡中節點的緩存能力，本文提出了一個新的度量標準來計算節點在整個網絡中的重要程度，該標準不僅表明了節點的連通性，還暗示了節點具有更多的接觸時間用于數據傳輸.

定義4. 節點重要度.將節點的連通性作為衡量節點重要程度的標準并記為I，那么

I=E(TC)/(E(TC)+E(TI))，

(4)

其中,E(TC)為節點與其他節點接觸時間的均值，E(TI)為節點與其他節點接觸間隔時間的均值.

(5)

(6)

式(6)表明節點間所傳輸的數據量不能超過該節點緩存的數據總量.因此在接觸時間限制條件下，節點i為節點j提供數據而獲得的緩存收益為

Bij=E(Uij)=

(7)

3.2 數據分片與編碼策略

如果節點在時間T內的每次接觸過程中都能夠傳輸最大的數據量，那么在整個傳輸過程中傳輸的數據量將是最大的.為了使得每次傳輸的數據量最大，本文根據節點的接觸歷史，計算出節點與其他節點接觸的最短時間tmin以及最長時間tmax.并以最短時間的均值E(tmin)為單位對數據進行分片，使得每次接觸都能夠傳輸數據，并盡可能地利用節點間的接觸機會.同時根據節點的tmax與E(tmin)的比值來限定節點的緩存界限，記為CB.因為超過該比值數量的數據包在任何一次接觸中都不能傳輸完成，從而造成緩存資源的浪費.

由于接觸時間的限制，本文根據節點的接觸歷史信息，采用上述的分片大小對數據進行分片處理.如果僅僅簡單地將數據分割為多個連續的數據片，那么為了恢復數據就必須收集所有的數據片，而這就會導致贈券收集問題的出現.

假設將數據分割為n個不同的數據片，并且每個數據片被請求者接收到的概率相同，那么數據請求者為了恢復原始數據就必需收集到n個不同的數據包.為了收集n個不同的數據包，數據請求者所需要收集數據包的數目往往遠大于原始數據片的數目n.

定理1. 若原始數據具有n個不同數據分片，且每個分片收集到的概率相同，那么恢復數據所需要收集的總數據分片數目為Θ(nlbn).

證明. 假設n個數據片收集到的概率相同，并從收集到i-1個不同的數據分片到i個所需要收集的數據分片數目為ni，比如從收集到0個數據分片到收集到1個不同的數據分片需要收集n1=1個數據分片.現假設節點收集到i-1個不同的數據分片，那該節點收集到的下一個數據分片是第i個不同的數據分片的概率p為

(8)

那么，該數據分片不是第i個的概率q=1-p.因此從第i-1個不同的數據分片到第i個所需要收集的數據片期望為

(9)

那么收集n個不同的數據分片所需要收集的數據分片數目E(n)為

E(n)=E(n1)+E(n2)+…+E(nn)=

n(lbn+o(1)).

(10)

證畢.

為了解決簡單分片所帶來的問題，本文采用了隨機線性網絡編碼技術.首先，在AP上將數據P分割成大小相同的n個數據包，即P=(p1,p2,…,pn)，并從伽羅瓦域中隨機生成編碼系數向量集αj=(αj 1,αj 2,…,αj n)，最終計算數據P的隨機線性組合：

(11)

然后AP將編碼后的數據包發送給數據請求者.通過隨機線性網絡編碼技術，網絡中的每個數據包的地位都是等同的，數據請求者只需要收集n個線性無關的數據包就可以恢復原始的數據.

(12)

式(12)又可表示為

(13)

最后可解方程得出原始的數據分片pi(i=1,2,…,n)為

(14)

通過這種編碼方式能夠有效地減少數據恢復時所需要收集的數據包數量，減少了網絡的負載，提高了數據訪問的效率.

3.3 緩存節點選擇

網絡中每個移動節點都維持一張緩存信息表，該信息表記錄了網絡中的緩存節點信息.緩存信息表包含移動節點ID、節點重要度I、節點緩存邊界CB、節點當前緩存的數據量Cached、以及表示數據更新的時間戳t等表項.其可以被定義為一個五元組，即CacheInfoTab=(ID,I,CB,Cached,t).

當網絡中2個節點接觸時，它們互相交換所維持的緩存信息表，并基于所收到的信息更新各自所維持的信息表.具體地說，節點首先更新本地信息表中的數據信息，然后將接收到的信息表剩余部分與本地信息表進行合并.在合并時以具有較新時間戳的數據條目替換時間戳較早的數據條目.

本文通過貪心算法得到初始緩存節點.首先根據本文提出的節點重要度I對網絡節點進行降序排序，然后迭代選取I值最大的節點來緩存數據直到達到該節點的緩存上限值.整個迭代過程一直當達到整個網絡的最大緩存代價為止.

本文緩存協議中，移動節點在下面2種情況下有可能成為緩存節點：1)當節點是路由節點或數據請求節點時，將會被動地緩存數據成為緩存節點；2)當節點與具有較低重要性的緩存節點相遇時，將會主動地從該緩存節點獲取數據成為新的緩存節點.

路由節點或數據請求節點接收到數據后，將會被動地判斷是否緩存數據.如果緩存節點的當前緩存數據量Cached小于所能緩存的最大數據量CB時，該緩存節點就緩存該數據包；反之就舍棄該數據包不進行緩存.由于這種被動緩存節點的節點重要度可能并不高，當網絡中具有較高重要度的節點與該緩存節點相遇時，將主動從緩存節點上獲取數據進行緩存來提高整體的緩存效益，即緩存數據主動重新分配.

4 實驗分析

為了驗證本文所述的緩存協議，對其進行了實驗仿真.本文實驗數據采用了Haggle Project[18]收集的Infocom2006數據，其中包含了節點間接觸歷史信息：接觸節點的信息、接觸開始時間以及接觸持續的時間.

4.1 實驗對比方案

為了證明本文所述緩存協議在協作緩存上的優勢，選擇了No-Cache策略和Cache-NoFrag策略作為本協議的比較對象.No-Cache即在網絡中不提供協作緩存策略，數據請求節點需從AP點獲取數據；Cache-NoFrag是指網絡中節點提供協作緩存但不對數據進行分片處理.在實驗中本文所提出的協議表示為Cache-Frag.從Cache與No-Cache對比反映出緩存對數據訪問性能的影響，從Cache-Frag與Cache-NoFrag對比反映出數據分片對數據訪問性能的影響，也就是接觸時間限制對數據訪問的影響.

本文采用的主要性能評估指標有：

1) 交付延遲(delivery delay).定義為從用戶請求開始直到接收到完整數據所花費的時間.

2) 緩存命中率(hit ratio).定義為用戶的數據請求由緩存節點而非原始內容服務器響應的概率.

4.2 實驗結果

1) 緩存代價的影響.

圖2表明了緩存代價γ對協作緩存中緩存數據交付延遲以及緩存命中率的影響.從實驗結果可知，當節點提供緩存策略時,數據交付延遲隨著緩存代價的增加而逐漸降低；緩存命中率則隨著緩存代價的增加而上升.同時當緩存代價較小時，這種變化越明顯；隨著緩存代價逐步增大,這種變化就表現得不夠明顯.在這種情況下節點間有限的接觸機會將是緩存性能提升的一個瓶頸，緩存數據交付時間和緩存命中率并不會因為網絡中數據副本的增加而出現顯著的變化.因此在接下來的實驗中，將限制γ=5來驗證容忍延遲時間對緩存性能的影響.

Fig. 2 Performance comparison with different cache cost γ圖2 不同緩存代價下的比較

Fig. 3 Performance comparison with different tolerance duration圖3 不同容忍時間下的比較

2) 容忍延遲時間的影響.

圖3表明了容忍延遲時間對協作緩存中緩存數據交付延遲以及緩存命中率的影響.當將緩存代價限定后，隨著容忍延遲的時間從8 ks逐步遞增到12 ks時，網絡中提供緩存服務比不提供緩存服務的效果要好；而本文所提出的緩存協議比不考慮接觸時間限制的緩存協議效果要好.這是因為在Cache-NoFrag中緩存數據作為一個整體存放于某一緩存節點，但由于節點間接觸時間的限制使得在一次接觸過程中數據無法傳輸完成，從而限制了緩存性能的提升，浪費了節點的緩存空間.在本文協議中，網絡上的緩存數據根據節點間的接觸時間分割為多個數據分片存放于多個緩存節點中，這增加了節點獲取數據的可能性，有效地利用了節點間的接觸機會；同時本文為每個節點確定了緩存上限，合理地利用了節點的緩存空間.

5 總 結

由于節點間的間斷性連接以及有限的接觸時間的限制,使得傳統網絡的數據緩存機制不能夠在移動機會網絡環境中得到有效應用.本文指出了接觸時間對協作緩存的影響，并為每個節點確定了緩存邊界來限制每個節點的緩存數據量，最后提出了數據分片策略和編碼方案，設計了緩存協議，并在實驗中驗證了該協議能夠有效地提高數據訪問的效率.本文主要解決接觸時間限制情況下的數據分片問題，沒有涉及到緩存替換，而緩存替換策略能夠更好地提高緩存的效率.本文的下一步工作將考慮如何將緩存替換策略納入本文提出的緩存協議之中.

[1]Han Ke. Cooperative caching algorithm based on grouping nodes in mobile ad hoc networks[C] //Proc of IEEE Int Conf on Information and Automation. Piscataway, NJ: IEEE, 2010: 1294-1298

[2]Rao A, Kumar P, Chauhan N. Energy efficient dynamic group caching in mobile ad hoc networks for improving data accessibility[C] //Proc of Int Conf on Recent Trends in Information Technology. Piscataway, NJ: IEEE, 2012: 372-376

[3]Gao Wei, Cao Guohong, Iyengar A, et al. Supporting cooperative caching in disruption tolerant networks[C] //Proc of the 31st Int Conf on Distributed Computing Systems. Piscataway, NJ: IEEE, 2011: 151-161

[4]Liu Waixi, Yu Shunzheng, Cai Jun. Scheme for cooperative caching in ICN[J]. Journal of Software, 2013, 24(8): 1947-1962 (in Chinese)(劉外喜, 余順爭, 蔡君. ICN中的一種協作緩存機制[J]. 軟件學報, 2013, 24(8): 1947-1962)

[5]Wei Dongsheng, Zhu Konglin, Wang Xin. Fairness-aware cooperative caching scheme for mobile social networks[C] //Proc of IEEE Int Conf on Communications. Piscataway, NJ: IEEE, 2014: 2484-2489

[6]Dong Lili, Wang Yong, Dong Yongqiang. Collaborative cache management strategy based on ant-colony replacement algorithm in named data networking[J]. Telecommunications Science, 2014, 30(9): 45-52 (in Chinese)(董利利, 王勇, 董永強. NDN中基于蟻群替換算法的鄰居協作緩存管理策略[J]. 電信科學, 2014, 30(9): 45-52)

[7]Hu Qian, Wu Muqing, Liu Hongbao. Distributed cooperative caching strategy in content centric networking[J]. Journal of Beijing University of Posts and Telecommunications, 2015, 38(2): 98-103 (in Chinese)(胡騫, 武穆清, 劉紅寶. 內容中心網絡中基于分布式協作的緩存策略[J]. 北京郵電大學學報, 2015, 38(2): 98-103)

[8]Luo Xi, An Ying, Wang Jianxin, et al. Cooperative caching mechanism with content migration in content-centric networking[J]. Journal of Electronics and Information Technology, 2015, 37(11): 2790-2794 (in Chinese)(羅熹, 安瑩, 王建新, 等. 內容中心網絡中基于內容遷移的協作緩存機制[J]. 電子與信息學報, 2015, 37(11): 2790-2794)

[9]Nuggehalli P, Srinivasan V, Chiasserini C F. Energy-efficient caching strategies in ad hoc wireless networks[C] //Proc of the 4th ACM Int Symp on Mobile Ad Hoc Networking & Computing. New York: ACM, 2003: 25-34

[10]Tang Bin, Gupta H, Das S. Benefit-based data caching in ad hoc networks[J]. IEEE Trans on Mobile Computing, 2008, 7(3): 289-304

[11]Niu Xinzheng, 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)(牛新征, 佘堃, 秦科, 等. 移動P2P網絡的協作緩存優化策略[J]. 計算機研究與發展, 2008, 45(4): 656-665)

[12]Zhuo Xuejun, Li Qinghua, Cao Guohong, et al. Social-based cooperative caching in DTNs: A contact duration aware approach[C] //Proc of the 8th IEEE Int Conf on Mobile Ad-Hoc and Sensor Systems. Piscataway, NJ: IEEE, 2011: 92-101

[13]Neto J B P, Lima M M, Mota E, et al. Adaptive contact volume prediction in delay tolerant networks[C] //Proc of the IEEE Symp on Computers and Communications. Piscataway, NJ: IEEE, 2013: 372-376

[14]Gao Wei, Li Qinghua, Zhao Bo, et al. Multicasting in delay tolerant networks: A social network perspective[C] //Proc of the 10th ACM Int Symp on Mobile Ad Hoc Networking and Computing. New York: ACM, 2009: 299-308

[15]Conan V, Leguay, J, Friedman T. Characterizing pairwise inter-contact patterns in delay tolerant networks[C] //Proc of the 1st Int Conf on Autonomic Computing and Communication Systems. Brussels, Belgium: ICST, 2007: No.19

[16]Wang Wei, Srinivasan V, Motani M. Adaptive contact probing mechanisms for delay tolerant applications[C] //Proc of the 13th Annual ACM Int Conf on Mobile Computing and Networking. New York: ACM, 2007: 230-241

[17]Chaintreau A, Hui Pan, Crowcroft J, et al. Pocket switched networks: Real-world mobility and its consequences for opportunistic forwarding, UCAM-CL-TR-617[R]. Cambridge, UK: University of Cambridge Computer Laboratory, 2005

[18]Lab for Communications and Applications, EPFL. Haggle Project[OL]. [2016-05-08]. http://ica1www.epfl.ch/haggle/