無線傳感器網(wǎng)絡(luò)數(shù)據(jù)存儲(chǔ)與查詢處理算法的研究.pdf

1、無線傳感器網(wǎng)絡(luò)是由大量布置在監(jiān)測區(qū)域內(nèi)的傳感器以Ad Hoc方式構(gòu)成的無線通訊網(wǎng)絡(luò)。其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)被監(jiān)測對象的信息。由于傳感器源源不斷的產(chǎn)生各種觀測數(shù)據(jù)，可以將傳感器網(wǎng)絡(luò)視為一種特殊的數(shù)據(jù)庫，用戶通過向傳感器網(wǎng)絡(luò)下發(fā)查詢獲取所需信息。無線傳感器網(wǎng)絡(luò)具有節(jié)點(diǎn)數(shù)量多、通信距離短、各種資源有限等特點(diǎn)。其中最重要的特點(diǎn)是每個(gè)節(jié)點(diǎn)的能量有限，因此針對傳感器網(wǎng)絡(luò)設(shè)計(jì)的各種查詢處理算法必須盡量減小算法的能量消耗。數(shù)據(jù)存儲(chǔ)

2、是查詢處理算法的重要組成部分，對傳感器觀測數(shù)據(jù)的合理組織可以有效減小查詢處理過程中的能量消耗，延長網(wǎng)絡(luò)生命周期。本文對傳感器網(wǎng)絡(luò)的數(shù)據(jù)存儲(chǔ)及相關(guān)查詢處理算法進(jìn)行深入研究，主要研究成果如下：
　　第一、提出一種基于時(shí)間索引的存儲(chǔ)方法及相關(guān)查詢處理算法，解決事件在整個(gè)網(wǎng)絡(luò)分布出現(xiàn)較大偏斜情況下，傳統(tǒng)以數(shù)據(jù)為中心存儲(chǔ)方法中源節(jié)點(diǎn)對觀測事件進(jìn)行存儲(chǔ)時(shí)所造成的能量浪費(fèi)問題。在此情況下更節(jié)省能量的存儲(chǔ)方法是：源節(jié)點(diǎn)將事件保存在本地，并在事件存

3、儲(chǔ)節(jié)點(diǎn)保存一個(gè)源節(jié)點(diǎn)觀測事件發(fā)生的時(shí)間段作為索引。此時(shí)用戶查詢需要通過事件存儲(chǔ)節(jié)點(diǎn)上保存的索引到源節(jié)點(diǎn)取得查詢結(jié)果。本文分析了上述基于時(shí)間索引的存儲(chǔ)方法較傳統(tǒng)以數(shù)據(jù)為中心存儲(chǔ)方法節(jié)省能量的條件，并據(jù)此提出一種自適應(yīng)的數(shù)據(jù)存儲(chǔ)選擇算法。自適應(yīng)算法可以根據(jù)用戶查詢與事件產(chǎn)生之間的實(shí)際情況，動(dòng)態(tài)調(diào)整源節(jié)點(diǎn)的事件存儲(chǔ)方法，使其始終保持最節(jié)省能量的狀態(tài)。實(shí)驗(yàn)表明，自適應(yīng)數(shù)據(jù)存儲(chǔ)選擇算法較傳統(tǒng)的以數(shù)據(jù)為中心的存儲(chǔ)方法節(jié)省能量。
　　第二、提出

4、一種基于環(huán)的數(shù)據(jù)存儲(chǔ)方法及相關(guān)查詢處理算法，解決事件在整個(gè)網(wǎng)絡(luò)分布均勻情況下，傳統(tǒng)以數(shù)據(jù)為中心存儲(chǔ)方法存在的熱點(diǎn)問題?；诃h(huán)的存儲(chǔ)方法將傳感器網(wǎng)絡(luò)劃分成多個(gè)環(huán)，通過將各個(gè)傳感器觀測的事件分散存儲(chǔ)在某個(gè)環(huán)形區(qū)域內(nèi)的多個(gè)節(jié)點(diǎn)并使不同環(huán)之間輪換工作等方式，解決事件存儲(chǔ)過程中出現(xiàn)的熱點(diǎn)問題。同時(shí)，基于環(huán)存儲(chǔ)的查詢處理算法使環(huán)上的所有節(jié)點(diǎn)都參與到用戶查詢處理過程中，從而解決了查詢處理過程中出現(xiàn)的熱點(diǎn)問題?；诃h(huán)的數(shù)據(jù)存儲(chǔ)及查詢處理算法通過使傳感器

5、網(wǎng)絡(luò)中的所有節(jié)點(diǎn)均勻的消耗能量，達(dá)到延長網(wǎng)絡(luò)壽命的目的。實(shí)驗(yàn)表明，基于環(huán)的數(shù)據(jù)存儲(chǔ)及查詢處理算法可以解決傳統(tǒng)以事件為中心存儲(chǔ)方法中出現(xiàn)的熱點(diǎn)問題，延長網(wǎng)絡(luò)壽命。
　　第三、提出一種基于Filter存儲(chǔ)的查詢處理算法，解決傳感器網(wǎng)絡(luò)一種新的連續(xù)查詢——連續(xù)動(dòng)態(tài)范圍查詢。該查詢與一般范圍查詢的關(guān)鍵區(qū)別在于：一般范圍查詢都是“靜態(tài)”的，即查詢范圍由常數(shù)構(gòu)成。本文提出的動(dòng)態(tài)范圍查詢則是以傳感器網(wǎng)絡(luò)中某個(gè)傳感器的實(shí)時(shí)觀測值作為比較對象。具體

6、的，連續(xù)動(dòng)態(tài)范圍查詢的含義是：以網(wǎng)絡(luò)中某個(gè)傳感器當(dāng)前周期的觀測值作為比較對象，返回連續(xù)若干個(gè)周期內(nèi)網(wǎng)絡(luò)中觀測值大于等于目標(biāo)節(jié)點(diǎn)當(dāng)前周期觀測值的節(jié)點(diǎn)ID及其觀測值。本文提出的基于Filter存儲(chǔ)的查詢處理算法為每個(gè)節(jié)點(diǎn)分配一個(gè)Filter作為閾值。節(jié)點(diǎn)根據(jù)當(dāng)前周期的觀測值與Filter值之間的關(guān)系決定將該觀測值保存在本地或傳遞給sink?；贔ilter存儲(chǔ)算法的關(guān)鍵是為傳感器網(wǎng)絡(luò)中的各個(gè)節(jié)點(diǎn)設(shè)定合適的Filter值。本文通過分析基于Fi

7、lter存儲(chǔ)算法的能量消耗，選擇使算法能量消耗最小的Filter值作為閾值?；贔ilter存儲(chǔ)的查詢處理算法在減少基于局部存儲(chǔ)查詢處理算法廣播次數(shù)的同時(shí)，還可以減少基于外部存儲(chǔ)算法中不滿足查詢條件的無關(guān)節(jié)點(diǎn)向sink傳遞消息的數(shù)量。最后通過實(shí)驗(yàn)驗(yàn)證了本文提出的基于Filter存儲(chǔ)算法較其他算法的能量節(jié)省性。
　　第四、提出一種基于局部存儲(chǔ)的能量有效查詢處理算法，解決傳感器網(wǎng)絡(luò)一種新的snapshot查詢——節(jié)點(diǎn)個(gè)數(shù)約束查詢。節(jié)點(diǎn)

8、個(gè)數(shù)約束查詢指滿足查詢的一部分節(jié)點(diǎn)向用戶返回結(jié)果，并使返回結(jié)果的節(jié)點(diǎn)個(gè)數(shù)占網(wǎng)絡(luò)中滿足查詢節(jié)點(diǎn)總數(shù)的比例達(dá)到用戶精度要求。與其他采用局部存儲(chǔ)的查詢處理算法相比，本算法的核心是利用節(jié)點(diǎn)個(gè)數(shù)約束查詢的特點(diǎn)進(jìn)行相關(guān)節(jié)點(diǎn)選擇，不但減少了將查詢在整個(gè)網(wǎng)絡(luò)洪泛產(chǎn)生的能量浪費(fèi)，還可以節(jié)省結(jié)果回收的能量消耗。具體的，算法由三部分構(gòu)成：相關(guān)節(jié)點(diǎn)選擇、能量有效的查詢下發(fā)和能量有效的結(jié)果回收。相關(guān)節(jié)點(diǎn)選擇算法用于從網(wǎng)絡(luò)中尋找與用戶查詢相關(guān)的一部分節(jié)點(diǎn)，同時(shí)保證