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

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

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

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

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

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

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

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