一種多傳感器信息融合的緩存替換策略_第1頁
一種多傳感器信息融合的緩存替換策略_第2頁
一種多傳感器信息融合的緩存替換策略_第3頁
一種多傳感器信息融合的緩存替換策略_第4頁
一種多傳感器信息融合的緩存替換策略_第5頁
全文預覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

一種多傳感器信息融合的緩存替換策略

在過去兩年中,基于人類載體的通用網(wǎng)絡已成為普通算計領域最受關(guān)注的焦點之一,因為它覆蓋了不同的元素(如房屋、車輛、行人、各種傳感器和相應的人類行為)。特別是在一般網(wǎng)絡背景下,大量相關(guān)數(shù)據(jù)被節(jié)點感知、移動、通信、存儲,并利用所需的地理位置、連接模式和可能的運動方向進行流動通信。對于各種不同類型的數(shù)據(jù)流傳方式,節(jié)點實體面臨著如何緩慢更新最具價值的數(shù)據(jù)問題,以及如何設計相應的緩存數(shù)據(jù)轉(zhuǎn)換率是一個重要的研究主題。研究人員在無線網(wǎng)絡的背景下進行了大量的研究工作,并根據(jù)數(shù)據(jù)輸入成本和延遲訪問目標設計了替換數(shù)據(jù)的成本計算策略。為了降低單節(jié)點間的訪問有限的缺點,研究人員使用節(jié)點間的合作關(guān)系設計了一種aca緩沖器替換算法。在文獻中,flood泵是一種用于計算和延遲數(shù)據(jù)訪問延遲的多媒體協(xié)議策略。該策略使用更高的通信成本來減少數(shù)據(jù)延遲。為了確定大約需要的數(shù)據(jù)單位是否在相鄰的節(jié)點上存儲,以避免頻繁訪問。在文獻中,我們提出了標準驗證緩沖區(qū)的設計方法,并根據(jù)最小下載成本目標設計了邊坡緩沖器的優(yōu)化方案。對于移動社會應用的背景下,本文分析并討論了基于共同因素的系統(tǒng)緩解策略,并提出了基于此的系統(tǒng)緩解優(yōu)化方案。例如,文獻使用通常接近緊密的群體具有類似于移動和數(shù)據(jù)訪問模式的堆棧策略,以降低服務請求的數(shù)量和數(shù)據(jù)訪問的損失率。在此基礎上,建立了基于網(wǎng)絡的移動社區(qū)協(xié)議模型。然而,在目前的軟系統(tǒng)層面上的研究方法基于相關(guān)數(shù)據(jù)的訪問信息,如訪問時間最終訪問時間數(shù)據(jù)元素的大小作為參考,然后設計了數(shù)據(jù)元素的替換策略。事實上,同一組數(shù)據(jù)可以具有完全不同的價值。因此,我們需要探討如何使用合作關(guān)系機制來設計相應的數(shù)據(jù)有效性成本估算函數(shù)和緩沖盤狀態(tài)化策略?;谏鲜龇治?,本文提出了節(jié)點合作協(xié)議策略:ctrp。該策略充分考慮了移動規(guī)律對數(shù)據(jù)元素的“有用性”,并將數(shù)據(jù)的訪問頻率作為影響緩存數(shù)據(jù)有效性的重要因素。本文組織結(jié)構(gòu)如下:第二節(jié)對緩存替換策略設計所涉及的相關(guān)問題進行討論,并說明CTRP的設計思路;第三節(jié)給出了CTRP與其他同類策略比較的性能評估與實驗結(jié)果并進行相應分析;第四節(jié)總結(jié)全文并提出下一步工作的方向.1ctrp的基本原理節(jié)點緩存數(shù)據(jù)替換流程如圖1所示,為方便描述,圖中符號定義如下:Si:數(shù)據(jù)項i的大小;V:節(jié)點已緩存數(shù)據(jù)項集合;Phit:緩存區(qū)中數(shù)據(jù)項i的緩存命中率;基于圖1流程,CTRP在選擇緩存數(shù)據(jù)項替換時的目標是使得替換后的數(shù)據(jù)項集合滿足如下表達式:Val(i)為CTRP用于評價數(shù)據(jù)項i“價值性”大小的函數(shù),CTRP對數(shù)據(jù)項價值性高低是通過特定數(shù)據(jù)項與特定節(jié)點的相關(guān)度標準進行判斷.該標準是基于我們之前的工作來進行設計的,其基本思想是若數(shù)據(jù)項與節(jié)點相關(guān)度越高,則說明數(shù)據(jù)項對該節(jié)點而言其價值性越高;在相關(guān)度判定的基礎上CTRP通過訪問頻率與更新頻率的比值大小來進一步對要替換的數(shù)據(jù)項集合進行篩選.下面具體說明這兩部分選擇數(shù)據(jù)項替換標準的設計思路.1.1頻繁往來節(jié)點設置本文的節(jié)點與數(shù)據(jù)相關(guān)度通過目標地址匹配標志(DM,Destination-Matching)和節(jié)點信任度(NTD,Node-trustDegree)來進行判定.NTD和DM值越高,則該數(shù)據(jù)與節(jié)點相關(guān)度越高,說明如下:在以人為載體的普適網(wǎng)絡中,數(shù)據(jù)緩存在節(jié)點內(nèi),主要依靠節(jié)點移動來協(xié)助傳輸數(shù)據(jù),若中繼節(jié)點移動過程中緩存數(shù)據(jù)項目的地與節(jié)點自身頻繁往返地點記錄匹配,則表明該節(jié)點經(jīng)過該數(shù)據(jù)項目的地的幾率較高,從而有利于協(xié)助數(shù)據(jù)較快到達目的地,降低網(wǎng)絡延遲.本文假設在以人為載體的普適網(wǎng)絡中每個節(jié)點可以獲取當前自身的位置坐標(利用GPS等技術(shù)),每個節(jié)點可以維護一張自身頻繁往返的地點位置記錄的數(shù)據(jù)表.考慮到現(xiàn)實情況,與目的地的交互匹配機率直接分為兩種情況,若該節(jié)點的頻繁往返地點記錄表中有數(shù)據(jù)目標坐標地址,則設置其值為1,否則為0,并用目標地址匹配因素DM進行標識.本文將每個節(jié)點頻繁往返地點的數(shù)目設置為4;整個數(shù)據(jù)記錄可放在一個數(shù)據(jù)包內(nèi)完成,因此造成的查詢性能開銷非常小,通過上述設定后,CTRP按照DM標志將節(jié)點的緩存區(qū)劃分為Mt與Mf兩個部分,Mt部分用于存放目標地址匹配數(shù)據(jù)項集合,Mf部分用于儲存目標地址不匹配數(shù)據(jù)項集合,在實現(xiàn)中,考慮到每個節(jié)點的頻繁往返地點數(shù)目有限,因此匹配成功的數(shù)據(jù)項較少,緩存區(qū)的空間比例初始劃分大致為1:4左右,并根據(jù)節(jié)點實際情況動態(tài)調(diào)整.當進行緩存數(shù)據(jù)項替換時,CTRP將先替換Mf區(qū)的數(shù)據(jù)項.在同一區(qū)內(nèi)的數(shù)據(jù)項,CTRP按照數(shù)據(jù)NTD值進行隊列的降序排序.對于節(jié)點信任度NTD值具體設置,CTRP采用一個權(quán)重連通圖T來描述人類的社會交互網(wǎng)絡,其中T的頂點集U由用戶組成,頂點之間的邊集H{h12,h23,h34,…,hnn}表示各用戶之間的社會聯(lián)系緊密程度.而NTD是一個實數(shù),取值范圍在[0,1]之間.CTRP用特定兩個用戶間的邊權(quán)重來表示,邊權(quán)重越大表示兩個用戶之間信任與交互度越高,當值為0時說明兩者為陌生人.NTD參數(shù)值的設置取決于兩個節(jié)點間的社會接觸度.社會接觸度越高,NTD值則越高.為便于設計,在具體的實現(xiàn)中,CTRP參照現(xiàn)實社會關(guān)系中的陌生人,同事,朋友,親人等關(guān)系將接觸度分為為沒有﹑較少﹑平均﹑頻繁﹑親密5個級別.與其相對應的NTD值劃分為{0,0.4,0.6,0.8,1}.CTRP設置每個用戶只需維護自己的NTD記錄表(類似于手機中的通訊簿),NTD記錄的更新維護在用戶間的社會關(guān)系發(fā)生變化時進行.由于人與人之間的社會關(guān)系一般較為穩(wěn)定,并且每個人的社交網(wǎng)絡由有限個用戶組成,因而維護NTD記錄表的開銷可以接受.當節(jié)點在緩存相鄰節(jié)點發(fā)送來的數(shù)據(jù)時,會相應地將發(fā)送節(jié)點的NTD值作為一個附加屬性賦予給數(shù)據(jù).若有多個節(jié)點發(fā)送了同一數(shù)據(jù),則該數(shù)據(jù)的NTD值設置取發(fā)送節(jié)點集中的最高值.1.2節(jié)點sda的運行如前所述,以人為載體的普適網(wǎng)絡中,數(shù)據(jù)項的有效性是緩存替換策略要考慮的關(guān)鍵因素.在判定節(jié)點與數(shù)據(jù)相關(guān)度基礎上,本文用數(shù)據(jù)項訪問與更新頻率比值來衡量確定數(shù)據(jù)有效性的大小;其中數(shù)據(jù)項訪問頻率是一個局部數(shù)據(jù),由緩存該數(shù)據(jù)項的單個節(jié)點獨立確定,而數(shù)據(jù)項更新頻率是一個全局數(shù)據(jù),由數(shù)據(jù)生成節(jié)點或者服務器來進行統(tǒng)一設置.若節(jié)點所緩存數(shù)據(jù)項i的更新頻率用φi表示,則有如下兩種邊界情況:1)limφi→∞,此時表示數(shù)據(jù)項i實時性極高,持續(xù)有效性時間極短.此時則表明該數(shù)據(jù)緩存價值很小(如股票波動實時價格),可以選擇直接替換.2)limφi→0,此時表示數(shù)據(jù)項i無需更新,永久有效;在CTRP中,表明該數(shù)據(jù)項緩存價值較高;然而直接屬于這兩種邊界情況的應用極少,絕大多數(shù)應用處于這兩者區(qū)間之內(nèi).此時,節(jié)點緩存區(qū)內(nèi)數(shù)據(jù)訪問與更新頻率比值與節(jié)點緩存命中率緊密相關(guān).具體而言總共有如下三種情況:(1)數(shù)據(jù)項i在兩次更新間隔周期內(nèi)訪問次數(shù)為0;由于數(shù)據(jù)項i沒有訪問次數(shù),這種情況對計算緩存有效命中率沒有影響;(2)數(shù)據(jù)項i在兩次更新間隔周期內(nèi)只有一次訪問次數(shù);由于只有一次訪問次數(shù),說明該次訪問是兩次更新間隔時間內(nèi)的第一次訪問,而在計算緩存命中率時,數(shù)據(jù)項i經(jīng)過首次訪問后才有可能被節(jié)點緩存,在這種情況下后續(xù)的訪問次數(shù)才能看作數(shù)據(jù)項i的有效命中次數(shù).因此這種情況對計算緩存命中率也沒有影響;(3)數(shù)據(jù)項i在兩次更新間隔周期內(nèi)有n次的數(shù)據(jù)訪問,其中n值大于等于2.這種情況下表明數(shù)據(jù)項i已被節(jié)點緩存,其至多會有n-1次有效命中次數(shù);在這三種情況下,若令δi表示單位時間內(nèi)緩存區(qū)某數(shù)據(jù)項i的訪問頻率,fi表示緩沖區(qū)內(nèi)數(shù)據(jù)項i在連續(xù)兩次更新間隔時間內(nèi)訪問次數(shù),則有下式成立:進一步,若令P(fi=n)表示連續(xù)兩次更新間隔時間內(nèi)i的訪問次數(shù)為n的概率,Uhit表示兩次訪問間隔時間內(nèi)i的有效命中次數(shù),則Uhit上界為:通過上式,可以看出fi(即δi/φi)成為影響緩存數(shù)據(jù)項有效命中率的關(guān)鍵因素,若令Sr表示節(jié)點緩存數(shù)據(jù)項需要的空間大小,則CTRP將基于上節(jié)判斷節(jié)點與數(shù)據(jù)項相關(guān)性條件下替換掉V的子集VR,其中VR滿足如下條件:2性能與模擬結(jié)果的分析2.1實驗環(huán)境設置我們對CTRP、OPT、LRU(leastrecentlyused)、ON-CRP進行了仿真結(jié)果分析比較.考慮到目前應用普及率,本文采用藍牙作為無線MAC通訊協(xié)議,仿真實驗平臺為UCBT,UCBT是一個開源的藍牙模擬器,在NS2上經(jīng)過編譯安裝后可以仿真藍牙的關(guān)鍵協(xié)議層,包括BaseBand、L2CAP、LMP和BNEP.實驗環(huán)境:本文在300m×300m的矩形區(qū)域內(nèi)隨機放置200個移動節(jié)點,區(qū)域兩端放置兩個固定的基站Sevr0與Sevr1.實驗數(shù)據(jù)規(guī)模為2000個數(shù)據(jù)項.每種算法查詢數(shù)據(jù)項請求為[200,800]個.其中數(shù)據(jù)項分配方法為Sevr0放置id號為偶數(shù)的數(shù)據(jù)項,Sevr1內(nèi)放置id號為奇數(shù)的數(shù)據(jù)項.查詢數(shù)據(jù)項請求由節(jié)點生成,其間隔時間段值為0.5秒,服從泊松分布.數(shù)據(jù)項的TTL值由基站在其Timestamp字段內(nèi)設置.每次仿真均進行20次,取其平均值作為結(jié)果.2.2不同存儲容量的緩沖系統(tǒng)的緩沖系統(tǒng)的緩沖系統(tǒng)的緩沖系統(tǒng)的緩沖系統(tǒng)的性能比較本節(jié)通過緩存命中率,平均數(shù)據(jù)訪問延遲對算法進行比較分析.其中平均數(shù)據(jù)訪問延遲定義為從節(jié)點發(fā)出請求到收到該數(shù)據(jù)的時間間隔.實驗分別基于節(jié)點緩存大小為0.5MB、1.0MB、1.5MB、2MB、2.5MB、3MB的情況對性能指標進行考察.實驗結(jié)果數(shù)據(jù)均為運行20次得到的平均值.圖2顯示了四種算法的平均數(shù)據(jù)訪問延遲,可以看出緩存容量增加各種算法的平均延遲均趨向一個較小的值,即緩存容量與數(shù)據(jù)訪問延遲呈現(xiàn)出一個反比關(guān)系,主要原因是緩存容量增加,可存放的數(shù)據(jù)項增多,使得數(shù)據(jù)項訪問時本地命中率有所上升,遠程數(shù)據(jù)查詢訪問次數(shù)降低,因而訪問延遲有效減少.其中LRU算法主要針對數(shù)據(jù)訪問次數(shù)和頻率這一單項指標來進行數(shù)據(jù)選擇替換,因此在移動環(huán)境下性能一般.而CTRP在數(shù)據(jù)替換過程中考慮了機會網(wǎng)絡數(shù)據(jù)傳輸特點,并采用特定節(jié)點與數(shù)據(jù)的相關(guān)度進行數(shù)據(jù)項替換選擇,保留了有可能較快到達目的地數(shù)據(jù).因此其平均延遲相應處于一個較小值的區(qū)間內(nèi).緩存命中率代表了緩存替換算法的關(guān)鍵性能,我們分別在不同緩存容量和不同數(shù)據(jù)項尺寸情況下進行了各種算法性能的比較.圖3(上)為不同緩存容量條件下算法的緩存命中率性能.為了與實際情況相符合,在實驗中設置緩存了的數(shù)據(jù)項在緩存空間所占比重上限為80%,在這個比例之上繼續(xù)增加緩存空間的大小對于提高性能來說效果不再明顯.從圖可以看出在緩存空間充足的情況下,四種算法緩存命中率基本上是隨緩存容量的增大而增加的,然而可以看到緩存容量空間增加到一定幅度(大于2.5M)后,所有算法緩存命中率增加幅度放緩.總體而言,CTRP結(jié)合考慮了節(jié)點信任度與頻繁往返目標匹配這兩個關(guān)鍵因素的影響,并且對已過有效期的數(shù)據(jù)項采取及時替換的措施,因而其緩存命中率處于一個較優(yōu)的值范圍內(nèi).圖3(下)比較了不同數(shù)據(jù)項大小的情況下各種算法的緩沖命中率.為比較各個算法真實表現(xiàn),我們在系統(tǒng)趨于穩(wěn)定的狀態(tài)下(即節(jié)點緩存已達到80%,開始運行替換算法時)開始收集實驗數(shù)據(jù);從圖中可以看出在小尺寸的數(shù)據(jù)項情況下各種算法緩存命中率表現(xiàn)較為優(yōu)異.CTRP緩存命中率始終要略優(yōu)于其他算法,隨著數(shù)據(jù)項尺寸的變大,不同算法的緩存命中率呈現(xiàn)出一個下降的趨勢.但總體來看,由于考慮了數(shù)據(jù)項替換是從目標地址匹配和節(jié)點協(xié)作關(guān)系角度出發(fā),因而CTRP算法下降趨勢比其他算法要緩慢,如在250K尺寸的數(shù)據(jù)項中,CTRP與OPT和LRU相比其命中率仍約有15%左右的提升.3節(jié)點信任度判定目前普適計算網(wǎng)絡研究成為當前的

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論