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

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

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

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

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

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

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

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

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