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

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

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

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

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

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

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

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

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

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

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

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