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

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

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