無線傳感器網(wǎng)絡中分布式近似計算方法的研究.pdf

1、隨著微電子技術、嵌入式技術、集成電路以及無線通信技術的日益成熟,無線傳感器網(wǎng)絡開始進入了人們的生活,并為人類低成本地觀察、認知復雜物理世界提供了一條有效途徑。目前,傳感器網(wǎng)絡已廣泛應用于環(huán)境監(jiān)測、醫(yī)療衛(wèi)生、國防軍事等各大領域。在構成傳感網(wǎng)的諸多要素之中,傳感器節(jié)點采集的感知數(shù)據(jù)是其核心部分之一,幾乎傳感網(wǎng)的所有應用都是建立在感知數(shù)據(jù)的計算(包含查詢、分析、挖掘等)基礎之上的。由于傳感網(wǎng)中感知數(shù)據(jù)的規(guī)模龐大,將其傳送至Sink節(jié)點再進行計

2、算勢必將消耗大量能量,故分布式的網(wǎng)內計算方法對傳感網(wǎng)來說十分重要。并且,由于傳感器節(jié)點在感知、計算、通信、存儲及能源等方面的能力均十分有限,故在許多情況下,傳感網(wǎng)無法給出精確的查詢分析結果。此時,正如智者亞里士多德所述,我們不必糾結于無法獲得的精確結果,具有一定誤差保證的近似結果亦是可接受的。綜上,在傳感網(wǎng)的研究中,設計低能耗的、分布式的、具有一定誤差保證的感知數(shù)據(jù)近似計算方法具有極其重要的意義。本文開展了這方面的研究,主要研究成果如下

3、:
　　首先,本文研究了靜態(tài)傳感器網(wǎng)絡中的-近似聚集算法。聚集操作是傳感網(wǎng)中的一種十分重要的操作。由于精確聚集算法的能量開銷很大,因而,近年來人們開展了對近似聚集算法的研究。然而,現(xiàn)有的網(wǎng)內近似聚集算法均具有固定的誤差界,并且很難調節(jié),所以一旦用戶所需要的誤差小于已有聚集算法所能保證的誤差界時,這些算法將失效。為了解決該問題,使得近似聚集結果能夠滿足用戶任意的精度需求,本文開展了傳感器網(wǎng)絡中的-近似聚集算法的研究,并基于均衡抽樣技

4、術,提出了靜態(tài)傳感器網(wǎng)絡中的-近似聚集算法。在該研究中,我們首先針對聚集和、平均值、無重復計數(shù)值等3種聚集操作,給出了根據(jù)來確定優(yōu)化的樣本容量的數(shù)學方法。其次,我們提出了一種分布式的均衡抽樣算法,用以完成樣本數(shù)據(jù)的抽取,并且我們對該算法的計算與通信復雜性進行了分析。第三,我們給出了估計聚集和、平均值、無重復計數(shù)值的數(shù)學方法,根據(jù)這些數(shù)學方法,提出了一種靜態(tài)傳感器網(wǎng)絡中的-近似聚集算法,并證明了該算法能夠滿足用戶的任意精確度需求。第四,鑒

5、于和感知數(shù)據(jù)的變化會影響最終的聚集結果,我們提出了兩種樣本數(shù)據(jù)信息的維護更新算法,分別用于處理和網(wǎng)絡中感知數(shù)據(jù)發(fā)生變化的情況。最后,通過模擬實驗驗證了本部分提出的算法的有效性。
　　其次,本文研究了動態(tài)傳感器網(wǎng)絡中的-近似聚集算法。雖然第一部分所給出的算法能夠滿足用戶任意的精確需求,并在靜態(tài)網(wǎng)絡中具有較高性能,但是該算法需要Sink節(jié)點頻繁地統(tǒng)計各個簇及全網(wǎng)內處于活動狀態(tài)的節(jié)點的數(shù)量,考慮到動態(tài)傳感網(wǎng)中活動節(jié)點數(shù)目是不斷變化的,故

6、該算法不適合應用于動態(tài)傳感網(wǎng)之中。進而,本文開展了動態(tài)傳感網(wǎng)中的-近似聚集算法的研究,并基于Bernoulli抽樣技術,提出了4種-近似聚集算法。在該研究中,我們首先針對活動節(jié)點計數(shù)值、感知數(shù)據(jù)聚集和、平均值等3種聚集操作,給出了跟據(jù)來確定優(yōu)化的抽樣概率的數(shù)學方法。其次,我們給出了適應動態(tài)網(wǎng)絡環(huán)境的、分布式的Bernoulli抽樣方法,用以獲取樣本數(shù)據(jù),并對該算法計算與通信復雜度進行了分析。第三,我們給出了估計活動節(jié)點計數(shù)值、感知數(shù)據(jù)聚

7、集和與平均值的數(shù)學方法。第四,在上述數(shù)學方法基礎上,我們給出了4種基于Bernoulli抽樣的-近似聚集算法,分別用以處理Snapshot查詢與連續(xù)查詢。我們證明了上述4種算法能夠滿足用戶任意的精度需求,并且能夠適應動態(tài)的網(wǎng)絡環(huán)境。最后,通過詳盡的模擬實驗驗證了本部分提出的算法的性能。
　　第三,本文研究了傳感器網(wǎng)絡中的地理位置敏感的極值點查詢算法。在傳感網(wǎng)收集的大量數(shù)據(jù)中,感知數(shù)據(jù)的極值點(例如,感知數(shù)據(jù)的最大值)及其所出現(xiàn)的地

8、理位置有助于用戶識別與定位異常區(qū)域,對于用戶來說十分重要。雖然傳統(tǒng)的top-k查詢亦能夠返回最大的k個感知值及其發(fā)生位置,但是由于在傳統(tǒng)top-k查詢處理過程中未考慮感知數(shù)據(jù)的空間相關性,所以其返回的結果(包括感知值及其位置)往往集中于一個小區(qū)域,為用戶提供的異常信息也極其有限。并且,由于傳統(tǒng)top-k查詢結果包含著大量的冗余數(shù)據(jù),從而使得傳輸上述結果的能量消耗過大。鑒于上述原因,本文提出了一種新的查詢,稱之為地理位置敏感的極值點查詢(

9、Location Aware Peak Value Query),簡記為LAP-(D,k)查詢,并對LAP-(D,k)查詢處理算法進行了研究。在該研究中,我們首先對LAP-(D,k)查詢處理問題進行了嚴格定義,并證明了該問題是NP-難的。其次,我們分別給出了兩種分布式近似算法用以解決LAP-(D,k)查詢處理問題。第三,我們證明了這兩種算法均具有常數(shù)近似比,同時,我們亦對上述兩種算法的計算和通信復雜度進行了詳細的分析。最后,通過真實和模

10、擬實驗驗證了本部分提出的算法在精確性及能量消耗方面均具有較高的性能。
　　第四,本文研究了傳感器網(wǎng)絡中物理過程近似逼近算法。目前,幾乎所有的感知數(shù)據(jù)計算技術均是建立在等頻數(shù)據(jù)采集之上的,并且假設通過等頻數(shù)據(jù)采集而獲得的感知數(shù)據(jù)能夠精準地反映物理過程的變化情況。但是,現(xiàn)實中物理過程往往是連續(xù)變化的,而等頻數(shù)據(jù)采集僅是對連續(xù)變化物理過程的離散化,故等頻數(shù)據(jù)采集存在著關鍵點丟失和曲線失真等問題。鑒于上述原因,本文開展了傳感網(wǎng)中物理過程近

11、似逼近算法的研究。在該研究中,我們首次提出了面向物理可高精度逼近的數(shù)據(jù)采集問題,并分別基于Hermit插值和三次樣條插值技術提出了兩種面向物理可高精度逼近的數(shù)據(jù)采集算法。上述算法可根據(jù)真實物理過程的變化情況及用戶的誤差需求,自適應地調整傳感器節(jié)點的數(shù)據(jù)采集頻率。其次,我們對上述算法的性能進行了分析與比較,包括算法輸出的曲線光滑程度、在計算一階、二階導數(shù)時的誤差、算法的數(shù)據(jù)采集次數(shù)及復雜性等。第三,我們改進了傳統(tǒng)意義上的感知數(shù)據(jù)的概念,在