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

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

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

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

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

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

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

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

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