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

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

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

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

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