無線傳感器網(wǎng)絡(luò)查詢技術(shù)研究.pdf

1、無線傳感器網(wǎng)絡(luò)的應(yīng)用越來越廣泛，網(wǎng)絡(luò)的規(guī)模也越來越大，希望從傳感器網(wǎng)絡(luò)中進(jìn)行查詢的用戶在不斷增加。由于傳感器網(wǎng)絡(luò)在功耗等方面的諸多限制，現(xiàn)有的傳感器網(wǎng)絡(luò)查詢方法已經(jīng)不能滿足大量網(wǎng)絡(luò)用戶的各種查詢要求，迫切需要新的技術(shù)有效解決無線傳感器網(wǎng)絡(luò)的查詢問題。而查詢一般可以分為針對部分?jǐn)?shù)據(jù)的查詢和針對所有數(shù)據(jù)的查詢兩種情況，相應(yīng)的，無線傳感器網(wǎng)絡(luò)最具代表性的兩種查詢環(huán)境是針對部分?jǐn)?shù)據(jù)的top-k數(shù)據(jù)查詢和針對所有數(shù)據(jù)的數(shù)據(jù)收集查詢。長時間以來，t

2、op-k查詢一直是計(jì)算機(jī)科學(xué)各領(lǐng)域中的一個重要課題。對top-k查詢的有效執(zhí)行是信息搜索的關(guān)鍵問題之一。隨著諸如信息物理（cyber-physical)系統(tǒng)等新方向的延伸，大量的用戶將直接搜索物理世界中的信息，這對top-k查詢技術(shù)構(gòu)成了新的挑戰(zhàn)。作為無線傳感器網(wǎng)絡(luò)中最重要的功能之一，top-k查詢對許多應(yīng)用都至關(guān)重要，比如環(huán)境監(jiān)測、網(wǎng)絡(luò)測量、污染物分析等。其中一個重要應(yīng)用是用戶希望無線傳感器網(wǎng)絡(luò)能夠持續(xù)地提取原始的或融合后的歷史top

3、-k數(shù)據(jù)。而以往在持續(xù)監(jiān)視top-k查詢研究中的算法在持續(xù)歷史top-k查詢中并不合適。此外，無線傳感器網(wǎng)絡(luò)采集的數(shù)據(jù)往往是多維的，而且從用戶的角度來說，會在不同的時刻，不同的用戶以不同的優(yōu)先級對不同的數(shù)據(jù)集提出查詢請求。因此，top-k查詢不僅應(yīng)該是多維的，還應(yīng)跨越時間區(qū)域。而且，多用戶查詢是最重要的應(yīng)用場景。從系統(tǒng)的角度來看，數(shù)據(jù)的收集通常是由小的傳感設(shè)備完成的。不同于在數(shù)據(jù)庫或者有線網(wǎng)絡(luò)中用于搜索的數(shù)據(jù)中心，對于由小的傳感器節(jié)點(diǎn)構(gòu)

4、成的無線傳感器網(wǎng)絡(luò)來說，這些設(shè)備通常資源十分有限，因而系統(tǒng)的效率至關(guān)重要。數(shù)據(jù)收集查詢即將傳感器采集的所有數(shù)據(jù)都收集到基站的查詢應(yīng)用，它在無線傳感器的很多應(yīng)用中都占據(jù)了非常重要的地位。因?yàn)樾试跓o線傳感器網(wǎng)絡(luò)中是一個非常關(guān)鍵的問題，有效的收集信息對延長無線傳感器網(wǎng)絡(luò)的壽命至關(guān)重要。最近，研究者提出壓縮感知技術(shù)，它是一種新型的可以從很少的壓縮度量中恢復(fù)稀疏數(shù)據(jù)的方法。由于真實(shí)世界數(shù)據(jù)往往具有稀疏性，壓縮感知技術(shù)得到了廣泛的應(yīng)用。但是，由于

5、任一時間的空間數(shù)據(jù)稀疏度往往不足夠低，現(xiàn)有的壓縮感知數(shù)據(jù)收集解決方案效果并不好。本文的工作圍繞無線傳感器網(wǎng)絡(luò)查詢技術(shù)研究這一中心展開，取得的研究成果包括如下幾個方面：
　　 ⑴提出了一個能夠高效處理持續(xù)歷史top-k數(shù)據(jù)查詢的架構(gòu)和查詢算法ECHT。采用基于數(shù)據(jù)融合的top-k提取算法用于用戶查詢，通過設(shè)置合適的濾波器，使傳感器節(jié)點(diǎn)不必報(bào)告自己所有的讀取數(shù)據(jù)，從而進(jìn)一步減少通信開銷。仿真實(shí)驗(yàn)結(jié)果表明，無論相對于持續(xù)監(jiān)測top-k

6、查詢或者它的直接改進(jìn)，或者是集中式數(shù)據(jù)收集方法，該方案不僅能夠大量減少總的通信開銷，而且系統(tǒng)的壽命也得到了指數(shù)性的延長。
　　 ⑵提出了一個多維數(shù)據(jù)top-k查詢系統(tǒng)架構(gòu)，能有效滿足資源有限的系統(tǒng)和大量查詢用戶的要求。多維數(shù)據(jù)top-k查詢即對多個用戶分別提出的各維數(shù)據(jù)的線性凸函數(shù)值的top-k查詢，凸函數(shù)是賦予一定權(quán)重的多個未知數(shù)的和函數(shù)。該架構(gòu)可以與許多種具有先進(jìn)特點(diǎn)的查詢要求相適應(yīng)，并且展示了如何進(jìn)行近似查詢和數(shù)據(jù)老化查詢

7、。為此，傳感器網(wǎng)絡(luò)中的傳感器讀數(shù)被組織成一個有效的支配圖數(shù)據(jù)結(jié)構(gòu)，支配圖是一種用于快速比較對各維數(shù)據(jù)賦予一定權(quán)重的和值大小的數(shù)據(jù)結(jié)構(gòu)。論文首先提出一個簡單的用于用戶top-k查詢的提取算法，該方法能夠適應(yīng)用戶所提出的任何線性凸函數(shù)top-k查詢。仿真結(jié)果顯示，相比于集中式收集方案和對以前一維數(shù)據(jù)top-k查詢算法的簡單擴(kuò)展，該方案能夠減少高達(dá)90％的通信開銷。
　　 ⑶提出了一個利用矩陣完成技術(shù)進(jìn)行數(shù)據(jù)收集的方法：有效數(shù)據(jù)收集方

8、法(EDCA)。該方法降低了采樣比，減少了傳輸?shù)陌臄?shù)量，因此極大地減少了能量消耗，從而增大了整個網(wǎng)絡(luò)的工作壽命。有效數(shù)據(jù)收集方法首先從該傳感器網(wǎng)絡(luò)中隨機(jī)地選取一部分節(jié)點(diǎn)進(jìn)行采樣，然后把采集到的數(shù)據(jù)通過路由樹直接發(fā)送到基站。為了精確地恢復(fù)出缺失的數(shù)據(jù)，該方法將屬于NP-hard問題的秩最小化問題轉(zhuǎn)化成為一個凸優(yōu)化問題。仿真實(shí)驗(yàn)結(jié)果表明在能量消耗方面，該方法比現(xiàn)有的集中式數(shù)據(jù)收集方法有顯著的減少，而且恢復(fù)的誤差也很小。同時，網(wǎng)絡(luò)的整體能耗

9、得到了大幅度的降低，網(wǎng)絡(luò)壽命得到了很大的延長。
　　 ⑷利用傳感器數(shù)據(jù)矩陣的低秩和瞬時穩(wěn)定性的特點(diǎn)，提出了一個能量有效的時空壓縮數(shù)據(jù)收集方法(STCDG)，它適用于均勻的或任意網(wǎng)絡(luò)拓?fù)?。時空壓縮數(shù)據(jù)收集方法能夠減少全局通信量，并極大延長了網(wǎng)絡(luò)的壽命。同時，該方法數(shù)據(jù)誤差可控，計(jì)算量小，傳輸控制簡單。另外，證明了網(wǎng)絡(luò)傳輸可以達(dá)到很高的網(wǎng)絡(luò)容量。基于真實(shí)的和合成數(shù)據(jù)，仿真了恢復(fù)誤差。為了論證該方法的網(wǎng)絡(luò)效率，仿真了在網(wǎng)格拓?fù)湎碌木W(wǎng)絡(luò)