Multi-Radio MANET中數(shù)據(jù)緩存和數(shù)據(jù)查詢處理算法的研究.pdf

1、隨著各種技術(shù)的發(fā)展，人們能隨時隨地訪問和處理網(wǎng)絡(luò)中的數(shù)據(jù)，因而數(shù)據(jù)查詢算法的研究已成為一個重點研究問題。然而，Multi-Radio MANET的網(wǎng)絡(luò)特性給數(shù)據(jù)查詢和收集帶來了很多問題，比如增大了數(shù)據(jù)查詢時延和能量消耗等。因此，本文針對Multi-Radio MANET的網(wǎng)絡(luò)特點，重點研究了基于數(shù)據(jù)緩存的數(shù)據(jù)查詢問題，其主要研究成果有:
　　1.針對MANET環(huán)境中帶寬有限、能量有限、存儲有限和鏈路頻繁斷接性等特點，提出了基于緩存

2、的數(shù)據(jù)查詢問題，證明該問題是NP-完全問題，并給出一個多項式時間的算法，即最大節(jié)點新覆蓋數(shù)據(jù)算法。該算法采用貪心策略，查詢新覆蓋數(shù)據(jù)量最大的節(jié)點，減少了查詢次數(shù)，并最大限度地減少了網(wǎng)絡(luò)中的傳輸時延。隨后在該算法的基礎(chǔ)上，同時考慮了節(jié)點新覆蓋數(shù)據(jù)量和鏈路服務(wù)質(zhì)量問題，提出了一種改進(jìn)的高效的算法，即基于最大節(jié)點傳輸時延與新覆蓋數(shù)據(jù)比值的數(shù)據(jù)查詢算法，有效地減少了能量消耗，最小化數(shù)據(jù)傳輸時延，提高了網(wǎng)絡(luò)的吞吐量。理論分析及實驗結(jié)果表明提出的數(shù)

3、據(jù)查詢算法能夠充分利用緩存節(jié)點的數(shù)據(jù)信息，較好地完成數(shù)據(jù)查詢工作，有效地減少數(shù)據(jù)收集時延，提高查詢效率。
　　2.針對Multi-Radio MANET中鏈路服務(wù)質(zhì)量和信道沖突等問題，提出并證明了基于緩存和信道切換的數(shù)據(jù)查詢問題是一個NP-完全問題。根據(jù)數(shù)據(jù)流守恒和鏈路-信道等約束條件，建立線性規(guī)劃方程，得到該問題的最優(yōu)解模型，并提出了一個多項式時間的貪心近似算法。該算法采用動態(tài)規(guī)劃策略最小化緩存節(jié)點將單位數(shù)據(jù)包傳輸?shù)讲樵児?jié)點所需

4、要的路徑時延，再貪心選擇其具有最小路徑時延的緩存節(jié)點，收集其新覆蓋數(shù)據(jù)。理論分析和實驗結(jié)果表明，提出的方案能有效地減少數(shù)據(jù)收集時延，提高數(shù)據(jù)查詢效率。
　　3.在MANET中采用TOP-K數(shù)據(jù)查詢來獲得僅需要的數(shù)據(jù)是一種有效方法。針對Multi-Radio MANET的網(wǎng)絡(luò)特點，研究了基于緩存的TOP-K數(shù)據(jù)查詢問題。同時提出了兩種處理算法，一種為基于f-鄰近緩存節(jié)點的TOP-K數(shù)據(jù)查詢算法，另一種為基于f-隨機緩存節(jié)點的TOP-