移動(dòng)自組網(wǎng)環(huán)境下協(xié)作緩存一致性維護(hù)機(jī)制研究.pdf

1、隨著Intemet的迅速發(fā)展，原本孤立的個(gè)人計(jì)算機(jī)被聯(lián)系起來(lái)．人們通過(guò)Intemet傳遞和交換信息，信息資源的發(fā)布與訪問(wèn)變得十分方便．如今Internet已經(jīng)深入人們的生活，這使得向用戶提供普適的Internet接入成為一個(gè)有待解決的重要問(wèn)題．無(wú)線通信技術(shù)以及移動(dòng)嵌入式設(shè)備制造技術(shù)的發(fā)展使得移動(dòng)自組網(wǎng)能夠?yàn)槠者m的Intemet接入提供有效的支持，而數(shù)據(jù)的高效分發(fā)與共享是基于移動(dòng)自組網(wǎng)的普適Intemet接入中的核心問(wèn)題．協(xié)作緩存技術(shù)被廣

2、泛地用來(lái)實(shí)現(xiàn)高效的數(shù)據(jù)分發(fā)與共享．為了保證協(xié)作緩存系統(tǒng)中有效的數(shù)據(jù)訪問(wèn)，緩存的一致性必須被合理地維護(hù)．雖然在傳統(tǒng)的有線網(wǎng)絡(luò)環(huán)境下，已有許多緩存一致性維護(hù)方面的工作，但是已有工作還沒(méi)有充分地研究移動(dòng)自組網(wǎng)環(huán)境下的協(xié)作緩存一致性問(wèn)題．移動(dòng)自組網(wǎng)中計(jì)算資源(網(wǎng)絡(luò)帶寬，移動(dòng)結(jié)點(diǎn)電池能量等)以及結(jié)點(diǎn)自主移動(dòng)的限制，使得協(xié)作緩存一致性維護(hù)成為一個(gè)更具有挑戰(zhàn)性的問(wèn)題． 本論文研究移動(dòng)自組網(wǎng)環(huán)境下的協(xié)作緩存一致性維護(hù)問(wèn)題．本文首先提出了一個(gè)緩存

3、一致性模型Probabilistic Delta Consistency(PDC)．在PDC模型中，用戶可以從兩個(gè)正交的維度(源數(shù)據(jù)和緩存拷貝之間的差異和有效緩存訪問(wèn)的比率)來(lái)設(shè)定自己的緩存一致性需求，從而在表述自己的緩存一致性需求時(shí)獲得很高的靈活性．通過(guò)靈活地表述自己的緩存一致性需求，用戶可以在動(dòng)態(tài)的移動(dòng)自組網(wǎng)環(huán)境下高效地在緩存一致性和一致性維護(hù)開(kāi)銷之間作出權(quán)衡．PDC模型還具有很高的一般性(Generality)．通過(guò)靈活的參數(shù)設(shè)置

4、，PDC模型將所有廣泛使用的緩存一致性模型包含為PDC模型的特例． 其次，本文提出了一個(gè)三維的緩存一致性維護(hù)算法設(shè)計(jì)框架．在該設(shè)計(jì)框架中，我們研究了緩存一致性維護(hù)算法設(shè)計(jì)中三個(gè)正交的關(guān)鍵子問(wèn)題． 第一，我們研究緩存一致性維護(hù)控制問(wèn)題．緩存一致性維護(hù)的基本方式包括Push策略和Pull策略．?dāng)?shù)據(jù)源結(jié)點(diǎn)和緩存結(jié)點(diǎn)何時(shí)Push和Pull將影響用戶的一致性需求能否被滿足，以及相應(yīng)的緩存一致性維護(hù)的開(kāi)銷是否合理．如何在滿足用戶的一

5、致性需求的前提下，選擇最合適的時(shí)機(jī)觸發(fā)Push或Pull，盡量減少一致性維護(hù)的代價(jià)是緩存一致性維護(hù)控制算法設(shè)計(jì)中要解決的主要問(wèn)題．而在移動(dòng)自組網(wǎng)環(huán)境下，針對(duì)這一問(wèn)題的研究工作還很不充分．本文針對(duì)移動(dòng)自組網(wǎng)環(huán)境的特點(diǎn)，提出了基于預(yù)測(cè)的緩存一致性維護(hù)控制算法Predictive Cache Consistency和基于超時(shí)值的緩存一致性維護(hù)控制算法Flexible Combination of Push and Pull，高效地在移動(dòng)自組網(wǎng)

6、環(huán)境下決定緩存一致性維護(hù)的時(shí)機(jī)． 第二，在緩存一致性維護(hù)的觸發(fā)時(shí)機(jī)決定以后，如何在網(wǎng)絡(luò)中高效地分發(fā)數(shù)據(jù)更新成為一個(gè)關(guān)鍵性的問(wèn)題．這一問(wèn)題因?yàn)橐苿?dòng)自組網(wǎng)中結(jié)點(diǎn)間的通信依靠多跳的無(wú)線連接，以及移動(dòng)自組網(wǎng)中計(jì)算資源(網(wǎng)絡(luò)帶寬，電池能量等)和結(jié)點(diǎn)自主移動(dòng)的限制，變得更具有挑戰(zhàn)性．針對(duì)移動(dòng)自組網(wǎng)環(huán)境下的數(shù)據(jù)更新分發(fā)問(wèn)題，本論文提出了層次化的數(shù)據(jù)更新協(xié)作分發(fā)算法Hierarchical Data UpdatePropagation(HDUP

7、)．HDUP算法在數(shù)據(jù)源結(jié)點(diǎn)和緩存結(jié)點(diǎn)間構(gòu)建具有樹(shù)形拓?fù)浣Y(jié)構(gòu)的Overlay網(wǎng)絡(luò)，并通過(guò)緩存結(jié)點(diǎn)在Overlay網(wǎng)絡(luò)中的協(xié)作高效地分發(fā)源數(shù)據(jù)更新． 第三，根據(jù)數(shù)據(jù)源結(jié)點(diǎn)如何維護(hù)各個(gè)緩存拷貝的狀態(tài)，緩存一致性維護(hù)算法可以分為兩大類：無(wú)狀態(tài)(Stateless)和有狀態(tài)(Stateful)．無(wú)狀態(tài)的緩存一致性維護(hù)算法主要依靠廣播機(jī)制分發(fā)源數(shù)據(jù)更新，因而會(huì)帶來(lái)較大的通信開(kāi)銷．有狀態(tài)的緩存一致性維護(hù)算法因其選擇性的數(shù)據(jù)更新分發(fā)機(jī)制而具有

8、通信代價(jià)小的特點(diǎn)．本論文提出面向移動(dòng)自組網(wǎng)的有狀態(tài)的緩存一致性維護(hù)算法GreedyWalk．based Selective Push(GWSP)．在GWSP算法中，數(shù)據(jù)源結(jié)點(diǎn)通過(guò)維護(hù)各個(gè)緩存拷貝的狀態(tài)，選擇性地向最需要數(shù)據(jù)更新的結(jié)點(diǎn)分發(fā)更新，有效地降低了緩存一致性維護(hù)開(kāi)銷． 最后，為了驗(yàn)證本論文提出的緩存一致性維護(hù)算法，我們開(kāi)發(fā)了面向移動(dòng)自組網(wǎng)的協(xié)作緩存原型系統(tǒng)P2PSim．P2PSim系統(tǒng)基于C++及標(biāo)準(zhǔn)模板庫(kù)STL開(kāi)發(fā).它實(shí)