基于低能耗與高緩存命中并存的緩存替換算法①

胥 琳, 林宇陽

(浙江工業大學 經貿管理學院, 杭州 310058)

基于低能耗與高緩存命中并存的緩存替換算法①

胥 琳, 林宇陽

(浙江工業大學 經貿管理學院, 杭州 310058)

近年來無線傳感器被廣泛地利用在各個領域, 與之相關的優化節能研究也層出不窮. 作為信息共享、分發關鍵技術的緩存技術節能研究成為了研究熱點之一. 從緩存替換算法的角度對緩存技術節能進行研究, 先對已有的緩存替換算法進行比較分析, 在繼承二分法思想以及無線傳感器網絡中緩存替換策略的研究思想的基礎上, 整合基于低能耗和高緩存命中的兩種替換算法, 構建出兼顧低能耗和高緩存命中雙目標的緩存替換算法. 最后通過仿真驗證該算法在平均延遲時間、能量消耗以及緩存命中三個方面均有不同程度的提升.

無線網絡; 緩存替換算法; 低能耗; 高緩存命中

無線傳感器網絡(wireless sensor network, WSN)的自組織、無中心、健壯性等特點使其廣泛應用于軍事、智能交通、環境監測、醫療衛生等領域. 由于傳感器節點的電源能量有限性制約著傳感器網絡的生命周期, 節能研究一直是無線傳感領域熱門的方向之一.

在多數據融合的無線傳感網絡中, 多個節點往往會向同一個數據源節點請求相同的數據, 容易出現網絡擁堵、訪問延遲等問題. 通過使用緩存技術, 設立緩存節點把高頻訪問的數據存儲在緩存節點的緩存空間內, 能夠避免用戶在下次請求相同的信息時再次訪問網絡, 從而提高網絡數據通訊性能. 緩存策略的優劣直接影響無線傳感器網絡的能量消耗和通信效率.

目前, 緩存策略研究主要包含緩存放置策略、緩存替換策略和緩存一致性策略. 緩存放置策略主要研究解決兩個問題, 哪些節點作為緩存節點以及應該緩存怎么樣的數據信息. 緩存替換策略主要研究如何替換緩存中數據項實現有限緩存空間的最優化利用. 緩存一致性策略主要研究如何以最低的代價保持源節點數據與緩存數據之間的一致性. 由于網絡內節點間信息的高速傳輸使得緩存節點的緩存數據不斷被替換,緩存替換策略成為決定傳感網絡節點緩存性能優劣的重要因素, 因此本文從緩存替換策略角度進行研究.

1 無線傳感網絡緩存替換技術研究現狀

目前業內的研究成果, 無線環境下的緩存替換算法主要圍繞基于替換代價的思想展開, 其中具有代表性的有以下幾種:

(1) 合作緩存策略(GCCS): 通過設定收益函數, 以訪問頻率和節點間距離為變量, 選擇函數值最小項為緩存替換對象[1]. (2) 協同緩存策略: 構造一個代價函數, 引入數據項大小、延遲時間、訪問頻率以及弱一致檢測機制, 選擇函數值大的數據項進行替換[2]. (3)LIRS緩存替換策略: 以使用最近(IRR)及最近度(R)來記錄區塊歷史信息, 后使用“棧剪枝”技術實現緩存的動態替換[3]. (4) 按需緩存替換策略(BESS): 將數據項、存在時間、訪問率作為權值建立權值函數, 替換出函數值較大的數據項[4]. (5) SAIU替換策略:主要考慮緩存內數據對象的訪問率、更新率和占用空間大小等因素,構建的權值函數[5]. (6) Min-SAUD策略: SAIU替換策略的一種改進, 主要創新點在于增加了緩存數據獲取延遲驗證的參數, 考慮到緩存有效檢驗延遲對替換的影響, 因此改進的獲益函數的參數設定也更為科學, 性能上要優于SAIU[6]. (7) 基于訪問頻率的LA2U策略和LAUD策略: 在傳統的LFU算法的基礎上考慮到對象的訪問頻率和更新頻率, 很適合無線傳感器網絡節點緩存的使用[7]. (8) OUR策略: 基于數據更新頻率和數據訪問率為基礎, 給出了全新的一種緩存替換策略[8].

綜合以上的替換緩存算法我們不難發現, 其基本思路是在既定假設下, 合理區分組成緩存獲益函數的影響因素, 構建替換算法模型. 目前國內外現有關于無線傳感器網絡緩存替換算法的研究中基本采用MANET網絡中基于替換代價的算法思想, 即沿用性能相對較好、算法復雜度較低的替換代價算法, 只是權值函數的構造因素有所不同.

通過整理總結, 現有策略算法中主要的權值函數組成因素有: 數據對象大小、數據對象的訪問頻率、數據對象存儲時間、數據的請求延遲、數據對象的更新頻率.

2 兼顧低能耗與高緩存命中的替換算法

文本依次分析追求低能耗的緩存替換算法的影響因素和追求高緩存命中的緩存替換算法的影響因素,進而推導得出兼顧低能耗與高緩存命中的替換算法.

2.1 能耗感知的替換策略

假設某一區域內共有N個傳感器節點S1, S2, ……,SN, 整個網絡中有1個或多個sink節點, 1個或多個源節點. 討論sink節點從某個緩存節點中獲取數據項系統消耗的總能量, 如果sink節點從緩存節點中尋找某個數據項失敗, sink節點直接從源節點中獲取數據項.

定義某個緩存節點為SK, 緩存總共有數據項M個,sink請求數據項A的概率為Pa(a=1…M). da表示sink節點請求數據項A, 應答節點到sink節點的距離, 若應答節點為緩存節點SK時, 則da=dak. 應答節點為數據源節點, 則da=das.

文獻[9]研究表明在工作狀態下節點感知、處理、空閑和休眠的能耗恒定的情況下, 節點能耗主要來源于節點發送和接收數據的消耗[9], 由此可以分析出, 降低節點發送和接收數據時候的能耗是能耗感知緩存替換算法的核心目的. 則我們做一下假設:

1. 使用Egd, 表示節點感知、處理、空閑和休眠時的能耗;

2. 使用Esf, 表示節點單位距離接收和發送數據項的能耗.

則我們可知對于某一緩存數據項A消耗的能耗Ea為:

假設某一緩存節點SK此時替換出數據項D, 新加入的數據項C. 數據項D大小用Sized表示, 數據項C大小用Sizec表示, 為了使新加入的數據項C能順利的加入緩存中, 則數據項D、C必須滿足以下要求:

該假設中我們先假定數據項大小相同, 則替換前后該節點的能耗差為:

Ec-d為能耗差, Pc、Pd表示sink節點請求數據項C、D的概率, dc、dd表示sink節點請求數據C、D時應答節點到sink節點的距離. 由于數據項C與數據項D的替換發生在一個緩存節點上, 根據da的定義, 上式中dc=dd=d, 則:其中d和Esf都是定值. 為了使替換前后緩存節點的耗能最優, 則Ec-d的值要最大, 那么(Pc-Pd)的值必須最大, 即替換入的數據項C的訪問率要大于替換出的數據項D的訪問率. 結合文獻[9]研究成果, 考慮到數據項大小、數據項產生時間, 我們可以得到能耗角度的替換函數:

Size表示數據項的大小, Time表示數據項占據緩存的時間, P表示數據項的訪問率, 當緩存溢出時, 節點計算各個數據項的gain1值, 替換出gain1值最大的數據項.

基于能耗感知的緩存替換函數(5), 從分析工作狀態下的能量消耗角度出發, 有利于降低整個網絡能耗.但是也存在不足, 對于新存入緩存的數據項, 它的訪問率P的值很小, 按照其策略, 新存入的數據項可能很快就會被替換出緩存. 根據數據緩存的時間局部性規律[10,11], 如果一個數據項被訪問, 則可能很快被再次訪問. 由此可知訪問率P無法全面的體現數據項的熱度.

另一方面, 傳輸單個bit數據消耗的能量和處理上千條命令消耗的能量相同[12], 可以運用相對完整的運算來全面的體現數據項的熱度. 因此, 算法(5)存在緩存節點緩存命中不高的缺點, 必須引入高緩存命中率這一概念.

2.2 低能耗和高緩存命中共存的替換算法

本文簡化整個高緩存命中的過程, 提取保持高緩存命中的兩個函數權值, 即相關最近度U, 表示介于數據項最后一次和倒數第二次引用之間訪問的其它數據項的數量, 和最近度I, 表示數據項從最后一次引用到當前訪問的其它數據項的數量. 如表1所示, 表中虛擬時間是基于引用序列定義的, 其中一次引用代表一個基準時間單位, 符號“X”表示在一個虛擬時間單位內被訪問. 如, 數據項A在時間單位9時被訪問. 表中已標明在時間單位10時各數據項的U、I值. 當某個數據項在一個時間序列內只被引用一次的時候, 將U取值為緩存的數據項容量M的兩倍, 取2M是一種相對無窮大得思想, 為了算法計算更加方便[3].

表1 相關最近度和最近度的實例

由上表可以看出I的值越高, 說明塊未被引用的時間跨度越久, 即塊的“活躍度”越低; U的值越高, 說明塊在緩存內的活躍周期越長, “活躍度”越低. 因此, 我們可以通過U和I動態靈敏的監測緩存內每個塊的“活躍度”, 并構建基于高命中的替換函數:

U表示相關最近度, I表示最近度, 當緩存溢出時,替換出gain2值最大的數據項.

綜上, 根據函數(5), 從能耗的角度, 緩存需要替換出本身較大且占據緩存較長時間的數據項. 而從函數(6)可知, 緩存需要替換出“活躍度”較低的數據項. 由于函數(5)中的訪問率P無法全面的體現數據項的熱度, 因此使用最近度I與相關最近度U乘積即函數(6)替換訪問率P, 由此綜合考慮能耗和緩存命中率兩個方面, 得到了兼顧能耗和緩存命中率的緩存替換算法:

Size表示數據項的大小, Time表示數據項占據緩存的時間, U表示相關最近度, I表示最近度, 當節點緩存溢出時, 計算每個數據項的gain3值, 并替換出gain3值最大的數據項.

替換算法(7), 簡化了文獻[3]高緩存命中算法中復雜的“棧剪枝”操作使用相關最近度U和最近度I兩指標動態靈敏的反映緩存數據項的活躍度, 在吸取文獻[9]能耗感知算法的優點的基礎上, 實現算法的多目標優化, 構建了兼顧低能耗和高緩存命中的緩存替換算法.下一節將對該策略進行仿真測試.

3 仿真試驗

本文使用NS2工具2.35版本對模型進行仿真實驗.實例檢驗上一節所提替換算法模型的實際優化效果.

3.1 仿真試驗環境設置

根據前文論述, 網絡中需數據源節點、sink節點和中間節點三種類型的節點. 數據源節點只采集數據信息, 不轉發來自鄰居節點的數據信息, sink節點請求感興趣的數據信息, 中間節點轉發數據信息. 在緩存發現方法上, 采用二分法的思想在定向路由擴散協議下建立的sink節點到數據源節點的路徑在尋找緩存節點, 使選擇的緩存節點分散在網絡中, 并用跳數來衡量節點間的距離. 本文的仿真試驗環境如圖1所示, 30個節點隨機分布在某一區域中自發組網, 并在該區域內隨機選擇源節點和sink節點, 圖中比較分散的藍色的圈表示sink節點發出的興趣請求信息的傳播路徑, 集中的紅色圈表示源節點采集到數據信息并返回給sink節點的路徑.

圖1 仿真環境下的網絡節點分布圖

3.2 仿真試驗參數設置

仿真過程采用的是定向擴散路由協議, 此外,sink節點請求數據的速率不能大于數據源節點感知數據的速率, 因此在本文的仿真試驗中, 設置sink節點平均每0.5 s發送一次興趣請求, 數據源節點平均每1 s感知1個數據信息, 并且計算得到了仿真中需要設置的能量閥值為105.5 J. 本文的仿真試驗參數設置如表2所示[13].

3.3 仿真實驗結果及分析

根據前面分析, 為了得到新算法相較于其它現存算法對網絡系統的性能改善效果, 本文的仿真試驗選擇了平均延遲時間、平均能量消耗和緩存命中率這三個仿真目標, 將本文的核心算法分別同BESS和LIRS算法做比較, 具體實現如下.

3.3.1 平均延遲時間

本文設置仿真環境為: 1個源節點, 分別對應1、2、3、4、5個sink節點, 那么平均延遲時間=網絡總延時時間/數據項的總個數, 其中網絡總延遲時間等于各sink節點的延遲時間之和. 具體結果如圖2顯示, 平均時延隨仿真網絡中節點數量變化而變化的情況, 本文算法相較于BESS算法, 平均時延降低15.07%～23.18%; 相較于LIRS算法, 平均時延降低11.01%～18.46%. 仿真設置各算法選擇的緩存節點在sink節點5跳范圍內, 隨著sink節點數量的不斷增加, 網絡中的信息傳輸密度更高, 導致節點間數據傳輸通路堵塞, 從而增加信息的反饋時間, 進而增加sink節點獲取數據的時間不斷提高.本文算法中的緩存放置策略采用BESS算法中基于二分法思想的按需緩存放置策略, 所選擇的緩存節點可以分散在網絡中, 這樣的好處在于sink節點在獲取緩存數據時有不同路徑的多種選擇, 從而一定程度上緩解網絡堵塞的情況.

表2 仿真試驗參數設置

圖2 平均時延隨sink節點數量的變化

3.3.2 平均能量消耗

本文設置仿真環境為: 2個sink節點, 2個源節點, 整個網絡節點數量為30到80個之間. 平均消耗能量=網絡總消耗能量/節點總個數; 網絡總消耗能量=網絡初始能量-仿真結束時網絡的剩余能量. 圖3顯示節點的平均能耗隨網絡密度變化而變化的情況, 相較于BESS算法, 本文算法節點的平均能耗降低4.71%～8.95%; 相較于LIRS算法, 本文算法節點的平均能耗降低20.31%～21.36%. LIRS算法采用傳統的緩存發現策略, 選擇的緩存節點集中在sink節點附近, 雖能縮短sink節點緩存發現的距離, 但同質緩存節點的密集容易導致網絡能量空洞, 影響網絡生命周期的同時, 也造成維持空閑緩存節點的能量浪費. 本文算法采用的緩存發現策略, 能夠將緩存節點較為合理的分散到整個網絡中, 避免LIRS算法緩存發現的弊端, 同時去除了LIRS算法為動態維持LIR集和HIR集而進行復雜的“棧剪枝”操作, 因此節點的平均能耗較LIRS算法有較大幅度的減少.

圖3 平均能耗隨網絡節點數量的變化

3.3.3 緩存命中率

本文設置仿真環境為: 1個sink節點, 2個源節點, 網絡中節點個數恒定為30個, 緩存節點的緩存大小為100-300 KB. 那么緩存命中率=sink節點收到來自緩存節點的信息數量/sink節點發出的請求數量. 圖4顯示sink節點的緩存命中率隨緩存節點緩存空間大小變化而變化的情況. 相較于BESS算法, 本文算法的緩存命中率提高5.33%～12.70%; 相較于LIRS算法, 本文算法的緩存命中率提高1.71%～4.94%. 緩存空間越大, 意味著能夠緩存更多的數據對象, 進而緩存命中的概率越高. 相較于LIRS算法, 本文算法不僅考慮了最近度和相關最近度, 還綜合考慮了數據對象的大小和緩存一致性有效下的緩存時間, 仿真結果表明本文算法的緩存命中率有小幅度提升; 相對于BESS算法, 本文算法使用最近度和相關最近度這兩個能更好刻畫緩存對象“熱度”的因素來取代BESS算法中的數據對象訪問率和更新頻率, 仿真結果表明本文算法的緩存命中率有較大幅度的提升.

圖4 緩存命中率隨緩存空間大小的變化

3 結語

本文主要研究無線傳感器網絡緩存技術中的緩存替換策略. 在總結當前研究現狀的基礎上, 以能耗感知緩存替換算法為切入點, 針對其中的不足, 引入高緩存命中思想. 使用最近度I與相關最近度U這兩個更能刻畫緩存數據“熱度”的函數因素來取代能耗感知算法中同樣刻畫緩存數據“熱度”的訪問率P, 同時移除了復雜的“棧剪枝”操作[14], 得到全新的追求低能耗和高緩存命中共存的緩存替換算法. 仿真實驗表明新算法在平均延遲時間、平均能量消耗和緩存命中率三個方面均有所提高.

本文所研究的緩存替換策略的網絡節點功耗管理模型為動態功耗管理(DMP)策略下的電池理想模型.但是現實中電池的最大壽命不完全與節點最小能耗對等, 實際電池釋放能量有著非線性的特點, 可以繼續研究電池模型對于緩存節點的選擇和能量閥值設定的影響. 另一方面, 本文采用的是替換算法中基于二分法思想的能量按需緩存放置策略研究成果[15], 因此如何選擇更加動態適合網絡傳輸情況的緩存放置策略是今后需要進一步研究的課題.

1Chauhan N, Awasthi LK, Chand N. Global cooperative caching for wireless sensor networks. 2011 World Congress on Information and Communication Technolgies. Mumbai,India. 2011. 235–239.

2Dimokas N, Katsaros D, Tassiulas L, et al. High performance, low complexity cooperative caching for wireless sensor networks. Wireless Networks, 2011, 17(3):717–737. [doi: 10.1007/s11276-010-0311-x]

3Jiang S, Zhang XD. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cacheperformance. Proc. of the 2002 ACM SIGMETRICS International Conference on Measurements and Modeling of Computer Systems. Marina Del Rey, California, USA. 2002.31–42.

4李欠欠. 無線傳感器網絡中基于能量有效的按需緩存策略研究[碩士學位論文]. 杭州: 中國計量學院, 2014.

5Xu JL, Hu QL, Lee DL, et al. SAIU: An efficient cache replacement policy for wireless on-demand broadcasts. Proc.the 9th International Conference on Information and Knowledge Management. McLean, VA, USA. 2000. 46–53.

6Xu JL, Hu QL, Lee WC, et al. Performance evaluation of an optimal cache replacement policy for wireless data dissemination. IEEE Trans. on Knowledge and Data Engineering, 2004, 16(1): 125–139. [doi: 10.1109/TKDE.2004.1264827]

7Chen H, Xiao Y, Shen XM. Update-based cache access and replacement in wireless data access. IEEE Trans. on Mobile Computing, 2006, 5(12): 1734–1748. [doi: 10.1109/TMC.2006.188]

8Akon M, Islam MT, Shen XM, et al. OUR: Optimal updatebased replacement policy for cache in wireless data access networks with optimal effective hits and bandwidth requirements. Wireless Communication and Mobile Computing, 2013, 13(15): 1337–1352.

9程莉, 劉建毅, 王樅. 計算機網絡. 北京: 科學出版社, 2012.

10趙國棟, 顧峰. 對Cache命中率優化的探討. 寧夏師范學院學報, 2007, 28(6): 54–57.

11席紅旗. 計算機高速緩沖存儲器(Cache)命中率的分析. 河南教育學院學報(自然科學版), 2012, 21(3): 31–32.

12Min R, Bhardwaj M, Cho SH, et al. Low-power wireless sensor networks. Proc. 14th International Conference on VLSI Design. Bangalore, India. 2001. 205–210.

13柯志亨, 程榮祥, 鄧德雋. NS2仿真實驗——多媒體和無線網絡通信. 北京: 電子工業出版社, 2009.

14Pant S, Chauhan N, Kumar P. Effective cache based policies in wireless sensor networks: A survey. International Journal of Computer Applications, 2010, 11(10): 17–21. [doi:10.5120/ijca]

15Srivastava JR, Sudarshan TSB. Energy-efficient cache node placement using genetic algorithm in wireless sensor networks. Soft Computing, 2015, 19(11): 3145–3158. [doi:10.1007/s00500-014-1473-8]

Cache Replacement Algorithm Based on Low Energy Consumption and High Cache Hit

XU Lin, LIN Yu-Yang
(College of Economics and Management, Zhejiang University of Technology, Hangzhou 310023, China)

In recent years, wireless sensors are widely used in various fields, and the research about energy-efficiency strategies is emerging in an endless stream. As a key technology of information sharing and distribution, the energyefficiency research about caching technologies has been one of research hot spots. Based on the cache replacement algorithm and the basic thought that adopts the replacement cost study, this research analyses the existing cache replacement algorithm firstly, then integrates the two cache replacement algorithms based on low energy consumption or high cache hit and refines one cache replacement algorithm that combines both advantages, which follows the on-demand cache placement policy based on dichotomy and the cache replacement strategy in wireless sensor network. At last, the simulation proves that, this algorithm has varied degrees of advancement in the following three aspects: the average delay time, energy consumption and cache hit.

wireless network; cache replacement algorithm; low energy consumption; high cache hit

胥琳,林宇陽.基于低能耗與高緩存命中并存的緩存替換算法.計算機系統應用,2017,26(7):189–194. http://www.c-s-a.org.cn/1003-3254/5849.html

浙江省自然科學基金(LY13F020031)

2016-10-27; 收到修改稿時間: 2016-12-05