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

胥 琳, 林宇陽(yáng)

(浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院, 杭州 310058)

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

胥 琳, 林宇陽(yáng)

(浙江工業(yè)大學(xué) 經(jīng)貿(mào)管理學(xué)院, 杭州 310058)

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

無線網(wǎng)絡(luò); 緩存替換算法; 低能耗; 高緩存命中

無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)的自組織、無中心、健壯性等特點(diǎn)使其廣泛應(yīng)用于軍事、智能交通、環(huán)境監(jiān)測(cè)、醫(yī)療衛(wèi)生等領(lǐng)域. 由于傳感器節(jié)點(diǎn)的電源能量有限性制約著傳感器網(wǎng)絡(luò)的生命周期, 節(jié)能研究一直是無線傳感領(lǐng)域熱門的方向之一.

在多數(shù)據(jù)融合的無線傳感網(wǎng)絡(luò)中, 多個(gè)節(jié)點(diǎn)往往會(huì)向同一個(gè)數(shù)據(jù)源節(jié)點(diǎn)請(qǐng)求相同的數(shù)據(jù), 容易出現(xiàn)網(wǎng)絡(luò)擁堵、訪問延遲等問題. 通過使用緩存技術(shù), 設(shè)立緩存節(jié)點(diǎn)把高頻訪問的數(shù)據(jù)存儲(chǔ)在緩存節(jié)點(diǎn)的緩存空間內(nèi), 能夠避免用戶在下次請(qǐng)求相同的信息時(shí)再次訪問網(wǎng)絡(luò), 從而提高網(wǎng)絡(luò)數(shù)據(jù)通訊性能. 緩存策略的優(yōu)劣直接影響無線傳感器網(wǎng)絡(luò)的能量消耗和通信效率.

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

1 無線傳感網(wǎng)絡(luò)緩存替換技術(shù)研究現(xiàn)狀

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

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

綜合以上的替換緩存算法我們不難發(fā)現(xiàn), 其基本思路是在既定假設(shè)下, 合理區(qū)分組成緩存獲益函數(shù)的影響因素, 構(gòu)建替換算法模型. 目前國(guó)內(nèi)外現(xiàn)有關(guān)于無線傳感器網(wǎng)絡(luò)緩存替換算法的研究中基本采用MANET網(wǎng)絡(luò)中基于替換代價(jià)的算法思想, 即沿用性能相對(duì)較好、算法復(fù)雜度較低的替換代價(jià)算法, 只是權(quán)值函數(shù)的構(gòu)造因素有所不同.

通過整理總結(jié), 現(xiàn)有策略算法中主要的權(quán)值函數(shù)組成因素有: 數(shù)據(jù)對(duì)象大小、數(shù)據(jù)對(duì)象的訪問頻率、數(shù)據(jù)對(duì)象存儲(chǔ)時(shí)間、數(shù)據(jù)的請(qǐng)求延遲、數(shù)據(jù)對(duì)象的更新頻率.

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

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

2.1 能耗感知的替換策略

假設(shè)某一區(qū)域內(nèi)共有N個(gè)傳感器節(jié)點(diǎn)S1, S2, ……,SN, 整個(gè)網(wǎng)絡(luò)中有1個(gè)或多個(gè)sink節(jié)點(diǎn), 1個(gè)或多個(gè)源節(jié)點(diǎn). 討論sink節(jié)點(diǎn)從某個(gè)緩存節(jié)點(diǎn)中獲取數(shù)據(jù)項(xiàng)系統(tǒng)消耗的總能量, 如果sink節(jié)點(diǎn)從緩存節(jié)點(diǎn)中尋找某個(gè)數(shù)據(jù)項(xiàng)失敗, sink節(jié)點(diǎn)直接從源節(jié)點(diǎn)中獲取數(shù)據(jù)項(xiàng).

定義某個(gè)緩存節(jié)點(diǎn)為SK, 緩存總共有數(shù)據(jù)項(xiàng)M個(gè),sink請(qǐng)求數(shù)據(jù)項(xiàng)A的概率為Pa(a=1…M). da表示sink節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)項(xiàng)A, 應(yīng)答節(jié)點(diǎn)到sink節(jié)點(diǎn)的距離, 若應(yīng)答節(jié)點(diǎn)為緩存節(jié)點(diǎn)SK時(shí), 則da=dak. 應(yīng)答節(jié)點(diǎn)為數(shù)據(jù)源節(jié)點(diǎn), 則da=das.

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

1. 使用Egd, 表示節(jié)點(diǎn)感知、處理、空閑和休眠時(shí)的能耗;

2. 使用Esf, 表示節(jié)點(diǎn)單位距離接收和發(fā)送數(shù)據(jù)項(xiàng)的能耗.

則我們可知對(duì)于某一緩存數(shù)據(jù)項(xiàng)A消耗的能耗Ea為:

假設(shè)某一緩存節(jié)點(diǎn)SK此時(shí)替換出數(shù)據(jù)項(xiàng)D, 新加入的數(shù)據(jù)項(xiàng)C. 數(shù)據(jù)項(xiàng)D大小用Sized表示, 數(shù)據(jù)項(xiàng)C大小用Sizec表示, 為了使新加入的數(shù)據(jù)項(xiàng)C能順利的加入緩存中, 則數(shù)據(jù)項(xiàng)D、C必須滿足以下要求:

該假設(shè)中我們先假定數(shù)據(jù)項(xiàng)大小相同, 則替換前后該節(jié)點(diǎn)的能耗差為:

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

Size表示數(shù)據(jù)項(xiàng)的大小, Time表示數(shù)據(jù)項(xiàng)占據(jù)緩存的時(shí)間, P表示數(shù)據(jù)項(xiàng)的訪問率, 當(dāng)緩存溢出時(shí), 節(jié)點(diǎn)計(jì)算各個(gè)數(shù)據(jù)項(xiàng)的gain1值, 替換出gain1值最大的數(shù)據(jù)項(xiàng).

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

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

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

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

表1 相關(guān)最近度和最近度的實(shí)例

由上表可以看出I的值越高, 說明塊未被引用的時(shí)間跨度越久, 即塊的“活躍度”越低; U的值越高, 說明塊在緩存內(nèi)的活躍周期越長(zhǎng), “活躍度”越低. 因此, 我們可以通過U和I動(dòng)態(tài)靈敏的監(jiān)測(cè)緩存內(nèi)每個(gè)塊的“活躍度”, 并構(gòu)建基于高命中的替換函數(shù):

U表示相關(guān)最近度, I表示最近度, 當(dāng)緩存溢出時(shí),替換出gain2值最大的數(shù)據(jù)項(xiàng).

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

Size表示數(shù)據(jù)項(xiàng)的大小, Time表示數(shù)據(jù)項(xiàng)占據(jù)緩存的時(shí)間, U表示相關(guān)最近度, I表示最近度, 當(dāng)節(jié)點(diǎn)緩存溢出時(shí), 計(jì)算每個(gè)數(shù)據(jù)項(xiàng)的gain3值, 并替換出gain3值最大的數(shù)據(jù)項(xiàng).

替換算法(7), 簡(jiǎn)化了文獻(xiàn)[3]高緩存命中算法中復(fù)雜的“棧剪枝”操作使用相關(guān)最近度U和最近度I兩指標(biāo)動(dòng)態(tài)靈敏的反映緩存數(shù)據(jù)項(xiàng)的活躍度, 在吸取文獻(xiàn)[9]能耗感知算法的優(yōu)點(diǎn)的基礎(chǔ)上, 實(shí)現(xiàn)算法的多目標(biāo)優(yōu)化, 構(gòu)建了兼顧低能耗和高緩存命中的緩存替換算法.下一節(jié)將對(duì)該策略進(jìn)行仿真測(cè)試.

3 仿真試驗(yàn)

本文使用NS2工具2.35版本對(duì)模型進(jìn)行仿真實(shí)驗(yàn).實(shí)例檢驗(yàn)上一節(jié)所提替換算法模型的實(shí)際優(yōu)化效果.

3.1 仿真試驗(yàn)環(huán)境設(shè)置

根據(jù)前文論述, 網(wǎng)絡(luò)中需數(shù)據(jù)源節(jié)點(diǎn)、sink節(jié)點(diǎn)和中間節(jié)點(diǎn)三種類型的節(jié)點(diǎn). 數(shù)據(jù)源節(jié)點(diǎn)只采集數(shù)據(jù)信息, 不轉(zhuǎn)發(fā)來自鄰居節(jié)點(diǎn)的數(shù)據(jù)信息, sink節(jié)點(diǎn)請(qǐng)求感興趣的數(shù)據(jù)信息, 中間節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)信息. 在緩存發(fā)現(xiàn)方法上, 采用二分法的思想在定向路由擴(kuò)散協(xié)議下建立的sink節(jié)點(diǎn)到數(shù)據(jù)源節(jié)點(diǎn)的路徑在尋找緩存節(jié)點(diǎn), 使選擇的緩存節(jié)點(diǎn)分散在網(wǎng)絡(luò)中, 并用跳數(shù)來衡量節(jié)點(diǎn)間的距離. 本文的仿真試驗(yàn)環(huán)境如圖1所示, 30個(gè)節(jié)點(diǎn)隨機(jī)分布在某一區(qū)域中自發(fā)組網(wǎng), 并在該區(qū)域內(nèi)隨機(jī)選擇源節(jié)點(diǎn)和sink節(jié)點(diǎn), 圖中比較分散的藍(lán)色的圈表示sink節(jié)點(diǎn)發(fā)出的興趣請(qǐng)求信息的傳播路徑, 集中的紅色圈表示源節(jié)點(diǎn)采集到數(shù)據(jù)信息并返回給sink節(jié)點(diǎn)的路徑.

圖1 仿真環(huán)境下的網(wǎng)絡(luò)節(jié)點(diǎn)分布圖

3.2 仿真試驗(yàn)參數(shù)設(shè)置

仿真過程采用的是定向擴(kuò)散路由協(xié)議, 此外,sink節(jié)點(diǎn)請(qǐng)求數(shù)據(jù)的速率不能大于數(shù)據(jù)源節(jié)點(diǎn)感知數(shù)據(jù)的速率, 因此在本文的仿真試驗(yàn)中, 設(shè)置sink節(jié)點(diǎn)平均每0.5 s發(fā)送一次興趣請(qǐng)求, 數(shù)據(jù)源節(jié)點(diǎn)平均每1 s感知1個(gè)數(shù)據(jù)信息, 并且計(jì)算得到了仿真中需要設(shè)置的能量閥值為105.5 J. 本文的仿真試驗(yàn)參數(shù)設(shè)置如表2所示[13].

3.3 仿真實(shí)驗(yàn)結(jié)果及分析

根據(jù)前面分析, 為了得到新算法相較于其它現(xiàn)存算法對(duì)網(wǎng)絡(luò)系統(tǒng)的性能改善效果, 本文的仿真試驗(yàn)選擇了平均延遲時(shí)間、平均能量消耗和緩存命中率這三個(gè)仿真目標(biāo), 將本文的核心算法分別同BESS和LIRS算法做比較, 具體實(shí)現(xiàn)如下.

3.3.1 平均延遲時(shí)間

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

表2 仿真試驗(yàn)參數(shù)設(shè)置

圖2 平均時(shí)延隨sink節(jié)點(diǎn)數(shù)量的變化

3.3.2 平均能量消耗

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

圖3 平均能耗隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的變化

3.3.3 緩存命中率

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

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

3 結(jié)語(yǔ)

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

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

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李欠欠. 無線傳感器網(wǎng)絡(luò)中基于能量有效的按需緩存策略研究[碩士學(xué)位論文]. 杭州: 中國(guó)計(jì)量學(xué)院, 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程莉, 劉建毅, 王樅. 計(jì)算機(jī)網(wǎng)絡(luò). 北京: 科學(xué)出版社, 2012.

10趙國(guó)棟, 顧峰. 對(duì)Cache命中率優(yōu)化的探討. 寧夏師范學(xué)院學(xué)報(bào), 2007, 28(6): 54–57.

11席紅旗. 計(jì)算機(jī)高速緩沖存儲(chǔ)器(Cache)命中率的分析. 河南教育學(xué)院學(xué)報(bào)(自然科學(xué)版), 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仿真實(shí)驗(yàn)——多媒體和無線網(wǎng)絡(luò)通信. 北京: 電子工業(yè)出版社, 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

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

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

2016-10-27; 收到修改稿時(shí)間: 2016-12-05