無(wú)線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集和查詢處理技術(shù)研究.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)極大地拓展了人類對(duì)物理世界的感知能力，在諸多方面都有著廣泛應(yīng)用，因此受到學(xué)術(shù)界的廣泛關(guān)注。無(wú)線傳感器網(wǎng)絡(luò)上的數(shù)據(jù)收集和查詢處理是其提供的基本而重要的服務(wù)，然而無(wú)線傳感器網(wǎng)絡(luò)的能量受限、自組織、可靠性差等特點(diǎn)導(dǎo)致其在支持?jǐn)?shù)據(jù)收集和查詢處理方面存在許多困難。首先，節(jié)點(diǎn)電源能量有限成為阻礙WSN應(yīng)用的嚴(yán)重問(wèn)題。而在大規(guī)模網(wǎng)絡(luò)中通常存在長(zhǎng)距離數(shù)據(jù)傳輸以及巨大的數(shù)據(jù)流，這兩個(gè)因素在很多應(yīng)用中大大加劇了某些節(jié)點(diǎn)的能量消耗速率，從而嚴(yán)重

2、影響網(wǎng)絡(luò)生命期。因此，如何在數(shù)據(jù)收集和查詢處理過(guò)程中延長(zhǎng)網(wǎng)絡(luò)生命期成為第一項(xiàng)挑戰(zhàn)。其次，用戶感興趣的檢測(cè)目標(biāo)與傳感器節(jié)點(diǎn)的感知對(duì)象不盡相同，可能對(duì)隱藏在原始數(shù)據(jù)中的有用信息和知識(shí)感興趣。在這種情況下，不需要將所有原始數(shù)據(jù)上傳到sink節(jié)點(diǎn)的網(wǎng)內(nèi)處理成為節(jié)約能耗的重要途徑。然而由于節(jié)點(diǎn)計(jì)算和存儲(chǔ)能力有限，如何在資源受限的情況下使得網(wǎng)絡(luò)能夠支持新的查詢成為第二項(xiàng)挑戰(zhàn)。最后，因?yàn)閃SN具有很強(qiáng)的動(dòng)態(tài)特性，數(shù)據(jù)傳輸路由及其所支撐的應(yīng)用可靠性相對(duì)

3、其它無(wú)線網(wǎng)絡(luò)較低。如何保障查詢處理和數(shù)據(jù)傳輸?shù)捻樌M(jìn)行成為第三項(xiàng)挑戰(zhàn)。本文針對(duì)上述三項(xiàng)挑戰(zhàn)考慮數(shù)據(jù)收集和查詢處理相關(guān)優(yōu)化問(wèn)題，提出相應(yīng)優(yōu)化策略和算法，并從理論和實(shí)驗(yàn)角度分析和驗(yàn)證所提策略和算法的有效性。本文取得如下研究成果。
　　首先，分別針對(duì)網(wǎng)絡(luò)中的數(shù)據(jù)收集以及多對(duì)多的數(shù)據(jù)聚集這兩種應(yīng)用提出最大化網(wǎng)絡(luò)生命期的優(yōu)化策略。(1)首次研究了數(shù)據(jù)收集傳感器網(wǎng)絡(luò)上的最大化生命期問(wèn)題，其中生命期被定義為數(shù)據(jù)收集的輪數(shù)，直到第一個(gè)節(jié)點(diǎn)耗盡它的

4、能量為止。證明該問(wèn)題是NP完全的，并提出一種近似最優(yōu)化算法。提出一種改進(jìn)策略，以減少巨大的計(jì)算開(kāi)銷和存儲(chǔ)整數(shù)規(guī)劃的空間。最后以大量的實(shí)驗(yàn)驗(yàn)證了算法的效率。(2)研究了如何獲得能量有效的聚集策略，以優(yōu)化傳感器網(wǎng)絡(luò)中的多對(duì)多聚集。即在網(wǎng)絡(luò)中，多個(gè)節(jié)點(diǎn)提供自己的數(shù)據(jù)，同時(shí)多個(gè)節(jié)點(diǎn)需要某一部分?jǐn)?shù)據(jù)的聚集值。證明在同時(shí)考慮路由和聚集選擇的時(shí)候，該問(wèn)題是NP完全的。所提出的三個(gè)近似算法中，兩個(gè)算法針對(duì)特殊情況，一個(gè)算法針對(duì)問(wèn)題的一般情況，其核心思想

5、是利用針對(duì)Steiner樹(shù)問(wèn)題的近似算法。所有算法都被證明具有常數(shù)或者多項(xiàng)式近似比。
　　其次，分別針對(duì)極值區(qū)域查詢和概率Skyline查詢這兩種WSN中的新查詢提出查詢處理和優(yōu)化算法。(1)研究了極值查詢的一種更普遍的情況—極值區(qū)域查詢，即給定查詢半徑R，極值區(qū)域查詢將返回所有半徑為R的碟形區(qū)域取值中的最大/最小值，其中一個(gè)碟形區(qū)域的值被定義為該區(qū)域內(nèi)所有傳感器讀數(shù)的某種聚集結(jié)果。針對(duì)該類查詢提出一種分布式算法EXQ，不但有效減

6、少了查詢處理過(guò)程中的能量開(kāi)銷，而且使得每個(gè)傳感器的能量消耗更平均，從而延長(zhǎng)了網(wǎng)絡(luò)的壽命。從理論和實(shí)驗(yàn)兩方面比較了EXQ和集中式算法的能量開(kāi)銷和能耗分布。(2)研究如何計(jì)算存在概率最大的skyline的問(wèn)題，稱為Pr-Skyline問(wèn)題。為此，首先給出Pr-Skyline問(wèn)題的定義，并證明其是NP完全問(wèn)題及多項(xiàng)式時(shí)間不可近似性。盡管如此，所提出的SKY-SEARCH算法結(jié)合多重剪枝策略仍然能夠保證在較大的數(shù)據(jù)規(guī)模下仍具有較高的平均計(jì)算效率

7、，并且基于過(guò)濾器的分布式優(yōu)化策略顯著減少了查詢過(guò)程中的傳輸開(kāi)銷和節(jié)點(diǎn)所需的存儲(chǔ)空間。大量的實(shí)驗(yàn)驗(yàn)證了SKY-SEARCH算法和分布式優(yōu)化策略的執(zhí)行效率和可擴(kuò)展性。
　　最后，分別針對(duì)發(fā)現(xiàn)查詢處理過(guò)程中的關(guān)鍵節(jié)點(diǎn)(割點(diǎn))，以及在低任務(wù)周期模式下的多查詢調(diào)度提出相關(guān)算法和優(yōu)化策略。(1)提出了一種高效的分布式割點(diǎn)探測(cè)算法CVD，并發(fā)地遍歷拓?fù)鋱D上的各個(gè)節(jié)點(diǎn)，并對(duì)基于區(qū)間編碼的生成樹(shù)上的邊進(jìn)行染色。該并發(fā)模式極大地減少了查詢處理過(guò)程中的

8、時(shí)間延遲，并且提出了一種優(yōu)化策略以進(jìn)一步減少能量開(kāi)銷和時(shí)間延遲。證明了CVD的正確性，并從理論和實(shí)驗(yàn)角度分析了CVD的性能。模擬實(shí)驗(yàn)和真實(shí)實(shí)驗(yàn)均表明，與其它算法相比，CVD具有更低的能量開(kāi)銷，更短的時(shí)間延遲，以及更好的可靠性。(2)為了緩解網(wǎng)絡(luò)在低任務(wù)周期(low-duty-cycle)模式下的傳輸擁塞并減少數(shù)據(jù)丟失，每個(gè)查詢需要進(jìn)行調(diào)度，以在時(shí)間和空間兩個(gè)維度上平衡各個(gè)節(jié)點(diǎn)的傳輸負(fù)載。本部分工作因而定義了負(fù)載平衡(LB)問(wèn)題，并證明其