基于無線傳感器網(wǎng)絡(luò)的采樣算法

1、基于無線傳感器網(wǎng)絡(luò)的采樣算法1.無線傳感器網(wǎng)絡(luò)的研究背景及應(yīng)用現(xiàn)狀1.1 研究背景 無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，簡稱WSN) 的基本功能是將一系列在空間上分散的傳感器單元通過自組織的無線網(wǎng)絡(luò)進行連接，從而將各自采集的數(shù)據(jù)進行傳輸匯總，以實現(xiàn)對空間分散范圍內(nèi)的物理或環(huán)境狀況的協(xié)作監(jiān)控，并根據(jù)這些信息進行相應(yīng)的分析和處理。因具有成本低、范圍大、布設(shè)靈活、移動支持等特點，無線傳感器網(wǎng)絡(luò)在工業(yè)監(jiān)控、智能電力、礦山安全、醫(yī)療健康、環(huán)境監(jiān)測等行業(yè)的應(yīng)用一直廣受重視;與此同時，無線傳感器網(wǎng)絡(luò)也面臨著延長節(jié)點工作時間、增加通信距離、小型化、標(biāo)準(zhǔn)化等技術(shù)挑戰(zhàn)和尋找應(yīng)用場景等市

2、場挑戰(zhàn)。無線傳感器網(wǎng)絡(luò)的研究經(jīng)歷了以下四個階段：（1）第一代傳感器網(wǎng)絡(luò)：20世紀(jì)70年代。點對點傳輸，具有簡單信息獲取能力。（2）第二代傳感器網(wǎng)絡(luò)：獲取多種信息的綜合能力，采用串/并接口與傳感控制器相聯(lián)。（3）第三代傳感器網(wǎng)絡(luò)：20世紀(jì)90年代后期。智能傳感器采用現(xiàn)場總線連接傳感控制器構(gòu)成局域網(wǎng)絡(luò)。（4）第四代傳感器網(wǎng)絡(luò)：以無線傳感器網(wǎng)絡(luò)為標(biāo)志，正處于研究和開發(fā)階段。近年來，無線傳感器網(wǎng)絡(luò)引起了業(yè)界極大關(guān)注，其應(yīng)用環(huán)境通常是由價格便宜的傳感器節(jié)點組成的，每個節(jié)點都能夠采集、存儲和處理環(huán)境信息，并且能和鄰居節(jié)點通過無線鏈路保持通信。覆蓋問題是無線傳感器網(wǎng)絡(luò)配置首先面臨的基本問題，因為傳感器節(jié)點可

3、能任意分布在配置區(qū)域，它反映了一個無線傳感器網(wǎng)絡(luò)某區(qū)域被監(jiān)測和跟蹤的狀況。隨著無線傳感器網(wǎng)絡(luò)應(yīng)用的普及，更多的研究工作深入到其網(wǎng)絡(luò)配置的基本理論方面，其中覆蓋問題就是無線傳感器網(wǎng)絡(luò)設(shè)計和規(guī)劃需要面臨的一個基本問題之一。隨著深入研究的角度不同，覆蓋問題也表述成不同的理論模型，甚至在計算幾何里面就能找到與覆蓋相關(guān)的解決方案。盡管這些辦法并不能直接應(yīng)用到無線傳感器網(wǎng)絡(luò)中，但是研究這些問題有助于建立讀者對無線傳感器網(wǎng)絡(luò)覆蓋問題相關(guān)的理論背景。1.2 無線傳感器網(wǎng)絡(luò)的應(yīng)用現(xiàn)狀雖然無線傳感器網(wǎng)絡(luò)的大規(guī)模商業(yè)應(yīng)用，由于技術(shù)等方面的制約還有待時日，但是最近幾年，隨著計算成本的下降以及微處理器體積越來越小，已經(jīng)

4、為數(shù)不少的無線傳感器網(wǎng)絡(luò)開始投入使用。目前無線傳感器網(wǎng)絡(luò)的應(yīng)用主要集中在以下領(lǐng)域： （1）環(huán)境的監(jiān)測和保護 隨著人們對于環(huán)境問題的關(guān)注程度越來越高，需要采集的環(huán)境數(shù)據(jù)也越來越多，無線傳感器網(wǎng)絡(luò)的出現(xiàn)為隨機性的研究數(shù)據(jù)獲取提供了便利，并且還可以避免傳統(tǒng)數(shù)據(jù)收集方式給環(huán)境帶來的侵入式破壞。比如，英特爾研究實驗室研究人員曾經(jīng)將32個小型傳感器連進互聯(lián)網(wǎng)，以讀出緬因州大鴨島上的氣候，用來評價一種海燕巢的條件。無線傳感器網(wǎng)絡(luò)還可以跟蹤候鳥和昆蟲的遷移，研究環(huán)境變化對農(nóng)作物的影響，監(jiān)測海洋、大氣和土壤的成分等。此外，它也可以應(yīng)用在精細農(nóng)業(yè)中，來監(jiān)測農(nóng)作物中的害蟲、土壤的酸堿度和施肥狀況等。（2）醫(yī)療護理

5、無線傳感器網(wǎng)絡(luò)在醫(yī)療研究、護理領(lǐng)域也可以大展身手。羅徹斯特大學(xué)的科學(xué)家使用無線傳感器創(chuàng)建了一個智能醫(yī)療房間，使用微塵來測量居住者的重要征兆（血壓、脈搏和呼吸）、睡覺姿勢以及每天24小時的活動狀況。英特爾公司也推出了無線傳感器網(wǎng)絡(luò)的家庭護理技術(shù)。該技術(shù)是做為探討應(yīng)對老齡化社會的技術(shù)項目Center for Aging Services Technologies（CAST）的一個環(huán)節(jié)開發(fā)的。該系統(tǒng)通過在鞋、家具以家用電器等家中道具和設(shè)備中嵌入半導(dǎo)體傳感器，幫助老齡人士、阿爾茨海默氏病患者以及殘障人士的家庭生活。利用無線通信將各傳感器聯(lián)網(wǎng)可高效傳遞必要的信息從而方便接受護理。而且還可以減輕護理人員的

6、負擔(dān)。英特爾主管預(yù)防性健康保險研究的董事Eric Dishman稱，在開發(fā)家庭用護理技術(shù)方面，無線傳感器網(wǎng)絡(luò)是非常有前途的領(lǐng)域。 （3）軍事領(lǐng)域 由于無線傳感器網(wǎng)絡(luò)具有密集型、隨機分布的特點，使其非常適合應(yīng)用于惡劣的戰(zhàn)場環(huán)境中，使其非常適合應(yīng)用于惡劣的戰(zhàn)場環(huán)境中，包括偵察敵情、監(jiān)控兵力、裝備和物資，判斷生物化學(xué)攻擊等多方面用途。美國國防部遠景計劃研究局已投資幾千萬美元，幫助大學(xué)進行智能塵埃傳感器技術(shù)的研發(fā)。哈伯研究公司總裁阿爾門丁格預(yù)測：智能塵埃式傳感器及有關(guān)的技術(shù)銷售將從2004年的1000萬美元增加到2010年的幾十億美元。 （4）其他用途 無線傳感器網(wǎng)絡(luò)還被應(yīng)用于其他一些領(lǐng)域。比如一些危

7、險的工業(yè)環(huán)境如井礦、核電廠等，工作人員可以通過它來實施安全監(jiān)測。也可以用在交通領(lǐng)域作為車輛監(jiān)控的有力工具。此外和還可以在工業(yè)自動化生產(chǎn)線等諸多領(lǐng)域，英特爾正在對工廠中的一個無線網(wǎng)絡(luò)進行測試，該網(wǎng)絡(luò)由40臺機器上的210個傳感器組成，這樣組成的監(jiān)控系統(tǒng)將可以大大改善工廠的運作條件。它可以大幅降低檢查設(shè)備的成本，同時由于可以提前發(fā)現(xiàn)問題，因此將能夠縮短停機時間，提高效率，并延長設(shè)備的使用時間。盡管無線傳感器技術(shù)目前仍處于初步應(yīng)用階段，但已經(jīng)展示出了非凡的應(yīng)用價值，相信隨著相關(guān)技術(shù)的發(fā)展和推進，一定會得到更大的應(yīng)用。但就目前的技術(shù)水平來說，讓無線傳感器網(wǎng)正常運行并大量投入使用還面臨著許多問題： （1

8、）網(wǎng)絡(luò)內(nèi)通信問題。無線傳感器網(wǎng)絡(luò)內(nèi)正常通信聯(lián)系中，信號可能被一些障礙物或其他電子信號干擾而受到影響，怎么安全有效的進行通信是個有待研究的問題。（2）成本問題。在一個無線傳感器網(wǎng)絡(luò)里面，需要使用數(shù)量龐大的微型傳感器，這樣的話成本會制約其發(fā)展。（3）系統(tǒng)能量供應(yīng)問題。目前主要的解決方案有：使用高能電池；降低傳感功率；此外還有傳感器網(wǎng)絡(luò)的自我能量收集技術(shù)和電池?zé)o線充電技術(shù)。其中后兩者備受關(guān)注。（4）高效的無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)。無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)是組織無線傳感器的成網(wǎng)技術(shù)，有多種形態(tài)和方式，合理的無線傳感器網(wǎng)絡(luò)可以最大限度的利用資源。在這里面，還包括網(wǎng)絡(luò)安全協(xié)議問題和大規(guī)模傳感器網(wǎng)絡(luò)中的節(jié)點移動性

9、管理等諸多問題有待解決。2. 無線傳感器網(wǎng)絡(luò)相關(guān)技術(shù)2.1無線傳感器網(wǎng)絡(luò)節(jié)點構(gòu)成無線傳感器網(wǎng)絡(luò)由大量體積小、成本低、具有無線通信、傳感、數(shù)據(jù)處理的傳感器節(jié)點以自組織方式構(gòu)成。傳感器節(jié)點構(gòu)成了網(wǎng)絡(luò)的硬件基礎(chǔ)。節(jié)點具備三個功能：首先，作為現(xiàn)場信息采集單元要完成信息的采集并按要求對采集到的信息進行適當(dāng)?shù)念A(yù)處理，因此節(jié)點包括數(shù)據(jù)采集模塊及數(shù)據(jù)預(yù)處理模塊；其次，傳感器節(jié)點還具有信息轉(zhuǎn)發(fā)功能，將采集到的現(xiàn)場信息通過一定的方式傳輸?shù)狡渌?jié)點或信息處理中心，因此節(jié)點還必須包括通信模塊來完成信息的接收、傳遞等；第三，當(dāng)節(jié)點處要實現(xiàn)某種控制作用時，還需要有控制模塊。一般來說，無線傳感器節(jié)點由以下幾個物理部分構(gòu)成：

10、（1）由微處理器或微控制器構(gòu)成的計算子系統(tǒng)，負責(zé)控制傳感器、執(zhí)行通信協(xié)議及處理傳感數(shù)據(jù)的算法；（2）用于無線通信的短距離無線收發(fā)電路，即通信子系統(tǒng)；（3）由一組傳感器和激勵裝置構(gòu)成的傳感子系統(tǒng)。實際應(yīng)用中，并不是所有的節(jié)點都需要控制模塊。傳感器節(jié)點的一種基本模型如圖2-1所示。包括傳感器、ADC、CPU及存儲器、通信模塊、控制模塊及電源（能量）等，當(dāng)不需要控制作用時，節(jié)點組成如圖2-1中粗線內(nèi)部分所示。所有這些模塊組裝成一個火柴盒大小甚至更小的傳感器節(jié)點，各模塊相互協(xié)作以完成一項共同的任務(wù)。圖2-1 傳感器節(jié)點基本模型除此之外，根據(jù)具體應(yīng)用的需要，節(jié)點可能還會有定位系統(tǒng)、電源再生單元和移動單元

11、等。其中電源再生單元是重要的模塊之一，有的系統(tǒng)可能采用太陽能電池等方式來補充能量，但是大多數(shù)情況下傳感器節(jié)點的電池是不可補充的。定位系統(tǒng)對傳感器網(wǎng)絡(luò)的路由是很重要的，有些傳感器節(jié)點采用GPS進行定位，但是GPS模塊價格昂貴且體積難以減少，所以不可能全部節(jié)點都使用GPS來進行定位。此外，GPS定位還受到其他限制，如網(wǎng)絡(luò)放置于建筑物內(nèi)部等。通常情況下是在整個網(wǎng)絡(luò)中會有某些傳感器節(jié)點配有GPS系統(tǒng)，其他節(jié)點通過局部定位算法得到它們與配有GPS的節(jié)點之間的相對位置，這樣所有節(jié)點都能知道各自的具體位置了。除借助GPS的定位方式外，還有離散梯度法等間接定位方式。無線傳感器網(wǎng)絡(luò)中的節(jié)點不但要完成信息的采集、

12、傳輸、預(yù)處理等，有時還涉及到較為復(fù)雜的任務(wù)調(diào)度及管理，因此在傳感器網(wǎng)絡(luò)中節(jié)點還可能帶有嵌入式操作系統(tǒng)以進行更有效的管理，嵌入式操作系統(tǒng)可以是通用的如uCOSII等，也可以是專門針對傳感器網(wǎng)絡(luò)開發(fā)的操作系統(tǒng)，如UC Berkeley開發(fā)的TinyOS。目前，無線傳感網(wǎng)絡(luò)的節(jié)點設(shè)計主要有兩種方法：一種是利用市場上可以獲得的商業(yè)元器件構(gòu)建傳感器節(jié)點，如圍繞TinyOS項目設(shè)計的系列硬件平臺；另一種方法是采用MEMS和集成電路技術(shù)，設(shè)計包含微處理器、通信電路、傳感器等模塊的高度集成化傳感器節(jié)點，如Smart Dust、WINS等。2.2 無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)如圖2-2所示,傳感

13、器網(wǎng)絡(luò)通常包括傳感器節(jié)點，匯聚節(jié)點和管理節(jié)點。傳感器節(jié)點任意的分布在某一監(jiān)測區(qū)域內(nèi)，節(jié)點以自組織的形式構(gòu)成網(wǎng)絡(luò)，通過多跳中繼方式將監(jiān)測數(shù)據(jù)傳送到匯聚節(jié)點，最后通過Internet或其他網(wǎng)絡(luò)通訊方式將監(jiān)測信息傳送到管理節(jié)點。同樣的，用戶可以通過管理節(jié)點進行命令的發(fā)布，告知傳感器節(jié)點收集監(jiān)測信息。 圖2-2 無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)圖傳感器節(jié)點是一個具有信息收集和處理能力的微系統(tǒng)，集成了傳感器模塊、信息處理模塊、無線通訊模塊和能量供應(yīng)模塊。其結(jié)構(gòu)體系如圖2-3所示。圖2-3 傳感器節(jié)點體系結(jié)構(gòu)傳感器模塊負責(zé)監(jiān)測區(qū)域內(nèi)信息的采集和轉(zhuǎn)換，信息處理模塊負責(zé)管理整個傳感器節(jié)點、存儲和處理自身采集的數(shù)據(jù)或者其

14、他節(jié)點發(fā)送來的數(shù)據(jù)，無線通訊模塊負責(zé)與其他傳感器節(jié)點進行通訊，能量供應(yīng)模塊負責(zé)對整個傳感器網(wǎng)絡(luò)的運行進行能量的供應(yīng)。傳感器節(jié)點能量的供應(yīng)是采用電池，節(jié)點能量有限，考慮盡可能的延長整個傳感器網(wǎng)絡(luò)的生命周期，在設(shè)計傳感器節(jié)點時，保證能量供應(yīng)的持續(xù)性是一個重要的設(shè)計原則。傳感器節(jié)點能量消耗的模塊主要是包括傳感器模塊、信息處理模塊和無線通訊模塊，而絕大部分的能量消耗是集中在無線通訊模塊上，約占整個傳感器節(jié)點能量消耗的80%。因此，目前提出的傳感器節(jié)點通訊路由協(xié)議主要是圍繞著減少能量消耗延長網(wǎng)絡(luò)生命周期而進行設(shè)計的。在無線傳感器網(wǎng)絡(luò)中，路由協(xié)議不僅關(guān)心單個節(jié)點的能量消耗，更關(guān)心整個網(wǎng)能量的均衡消耗，這樣

15、才能延長整個網(wǎng)絡(luò)的生存期。同時，無線傳感器網(wǎng)絡(luò)是以數(shù)據(jù)為中心的，這在路由協(xié)議中表現(xiàn)的最為突出，每個節(jié)點沒有必要采用全網(wǎng)統(tǒng)一的編址，選擇路徑可以不用根據(jù)節(jié)點的編址，更多的是根據(jù)感興趣的數(shù)據(jù)建立數(shù)據(jù)源到匯聚節(jié)點之間的轉(zhuǎn)發(fā)路徑。目前提出了很多類型的傳感器網(wǎng)絡(luò)路由協(xié)議，就是基于上述的目的。3. 無線傳感器網(wǎng)絡(luò)協(xié)同采樣路由算法性能指標(biāo)WSN協(xié)同采樣路由算法的應(yīng)用，有助于網(wǎng)絡(luò)節(jié)點能量的有效利用、感知服務(wù)質(zhì)量的提高和整體生存時間的延長，但另一方面也會帶來網(wǎng)絡(luò)相關(guān)傳輸、管理、存儲和計算等代價的提高。因此，WSN信息采樣的性能評價標(biāo)準(zhǔn)對于分析一個信息采樣策略及算法的可用性與有效性至關(guān)重要。通過從不同的角度總結(jié)出

16、信息采樣算法所面臨的挑戰(zhàn)，有助于清楚地比較出各種算法之間的優(yōu)缺點。這里歸納出以下幾點：(1) 信息采樣能力以環(huán)境感知、目標(biāo)監(jiān)測、信息獲取和有效傳輸為主要目標(biāo)的WSN需要關(guān)心對傳感區(qū)域或監(jiān)測目標(biāo)的信息采樣能力，無線傳感器網(wǎng)絡(luò)信息采樣問題也正是由此而來。因此，網(wǎng)絡(luò)對目標(biāo)區(qū)域或是目標(biāo)點的采樣覆蓋程度是衡量一個WSN信息采樣算法是否優(yōu)劣的首要標(biāo)準(zhǔn)。(2) 能量有效性(即延長網(wǎng)絡(luò)生存時間)由于WSN節(jié)點硬件平臺資源受限、網(wǎng)絡(luò)節(jié)點數(shù)量巨大、實際應(yīng)用的環(huán)境條件復(fù)雜且大多不允許對“失效”節(jié)點進行電池更換，因此，如何節(jié)約各節(jié)點有限的電池能量并盡力延長整體網(wǎng)絡(luò)的生存時間已成為WSN的重要性能指標(biāo)。能量的有效性將是

17、WSN信息采樣所面臨的一個主要挑戰(zhàn)。(3) 網(wǎng)絡(luò)的連通性由于WSN是一種無基礎(chǔ)設(shè)施的網(wǎng)絡(luò)，大量節(jié)點采用自組織方式協(xié)同完成指令中心的查詢、搜集等指令，網(wǎng)絡(luò)節(jié)點之間需要通過無線多跳方式或直接或間接地相互通信來協(xié)同工作。網(wǎng)絡(luò)的連通性將有效保證自身無線多跳自組織通信的開展，并直接決定了WSN感知、監(jiān)視、傳感、通信等各種服務(wù)質(zhì)量的達到。(4) 算法精確性由于受實際部署條件差異、網(wǎng)絡(luò)資源有限和覆蓋目標(biāo)特性等多方面的影響，況下是一個NP完全問題，只能達到近似優(yōu)化采樣。勢必會造成采樣控制算法執(zhí)行結(jié)果產(chǎn)生誤差，甚至不能使得WSN在很多情況下保證算法的有效執(zhí)行。如何減小誤差，提高算法的精確性成為優(yōu)化采樣控制算法的

18、一項重要內(nèi)容。(5) 算法復(fù)雜性 不同WSN采樣控制策略及算法其實現(xiàn)方式不同導(dǎo)致算法復(fù)雜程度也有較大差別。衡量一個WSN采樣算法是否優(yōu)化的一項重要標(biāo)準(zhǔn)就是其算法的復(fù)雜性程度。算法的復(fù)雜性程度通常包括時間復(fù)雜度、通信復(fù)度以及實現(xiàn)復(fù)雜度等，需要綜合考慮。 (6)算法實施策略 WSN采樣控制算法的執(zhí)行可以有分布式、集中式以及兩者的混合式3種方式。通常來說，由于WSN自身的能量消耗、協(xié)議操作代價、網(wǎng)絡(luò)性能和精度等要求，使得利用本地信息執(zhí)行的分布式算法更為適用。在一些特殊的網(wǎng)絡(luò)操作環(huán)境下，分布式、集中式兩種方式混合執(zhí)行則更為有效。除了上面列出的一些所面臨的挑戰(zhàn)之外，WSN采樣控制協(xié)議算法還會存在是否需要

19、知道網(wǎng)絡(luò)節(jié)點位置、是否需要專門的采樣控制消息等差別。同樣，它們也是我們設(shè)計、分析具體協(xié)議和算法時要考察的內(nèi)容。4. 基于無線傳感器網(wǎng)絡(luò)分簇構(gòu)架的協(xié)同采樣算法描述及其MATLAB仿真分析4.1 無線傳感器網(wǎng)絡(luò)中的分簇架構(gòu)及算法介紹4.1.1 無線傳感器網(wǎng)絡(luò)中的分簇架構(gòu)在采用分簇結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)節(jié)點被劃分為若干個簇。每個簇通常由一個簇頭節(jié)點(CH)以及多個成員節(jié)點(MN)組成。成員節(jié)點只與簇頭通信，簇頭與簇頭構(gòu)成高一級的虛擬骨干網(wǎng)，負責(zé)簇內(nèi)的數(shù)據(jù)融合和簇間數(shù)據(jù)轉(zhuǎn)發(fā)。因為簇頭節(jié)點的能量消耗較大，通常采用周期性選擇簇頭節(jié)點的方法均衡網(wǎng)絡(luò)中節(jié)點能量的消耗。簇頭的集合形成連通統(tǒng)治集(CDS)，

20、因為獲得最優(yōu)CDS是NPC問題，因此實際提出的算法均為啟發(fā)式的。圖4-1給出了分簇結(jié)構(gòu)以及簇內(nèi)與簇間的數(shù)據(jù)流向。圖4-1 WSN中的分簇結(jié)構(gòu)及其簇內(nèi)與簇間的數(shù)據(jù)流向WSN采用分簇結(jié)構(gòu)具有如下一些顯著的優(yōu)點：(1)在滿足一定約束條件情況下(例如覆蓋范圍與采樣精度要求等)，簇成員節(jié)點可以在某些時間段內(nèi)關(guān)閉通信模塊，大幅度減少空閑等待狀況的能量消耗，因此可節(jié)省能量。 (2)簇頭通常負責(zé)采集簇成員發(fā)送來的數(shù)據(jù)，這些數(shù)據(jù)具有較大的相關(guān)性，因此可以采用數(shù)據(jù)融合算法，在保證信息量的情況下降低數(shù)據(jù)通信量，降低數(shù)據(jù)轉(zhuǎn)發(fā)的能量開銷。 (3)因為采用層次結(jié)構(gòu)，簇成員只需了解到所屬簇頭的路由信息，簇頭只需了解簇頭間的

21、路由信息，因此可降低路由協(xié)議的復(fù)雜度，減少路由表項數(shù)目，路由維護開銷也隨之降低。 (4)具有較好的可擴展性能，更加適合于大規(guī)模WSN的應(yīng)用場景。4.1.2 無線傳感器網(wǎng)絡(luò)分簇算法介紹(1)集中式/分布式算法 根據(jù)是否存在一個中心控制節(jié)點負責(zé)整個網(wǎng)絡(luò)的簇劃分，分簇算法可分為集中式與分布式兩類。典型的集中式算法有LEACH-C、APTEEN等。我們提出的基于徑向基函數(shù)(RBF)的分簇算法也屬于此類。中心控制節(jié)點通常有持續(xù)的電源供應(yīng)、較高的存儲與計算能力，并能獲得網(wǎng)絡(luò)的全局信息，因此可以采用復(fù)雜的算法獲得優(yōu)化的分簇結(jié)果。但是由于普通無線傳感器節(jié)點能量有限，計算與通信能力不強，因此對于大型的WSN，集

22、中式算法在靈活性、可擴展性以及健壯性等方面存在缺陷，例如很多集中式算法要求獲得節(jié)點的剩余能量，因為傳感器節(jié)點運行中能量不斷下降，所以必須隔一段時間就得通知中心控制點更新剩余能量信息，這就造成大量額外數(shù)據(jù)包的傳輸，使算法的開銷過大。與集中式算法不同，分布式算法一般只需要相鄰節(jié)點之間互相交換信息，甚至不考慮相鄰節(jié)點獨立作出判斷，這類算法簡單、高效、靈活，因此更適用于大規(guī)模WSN。目前大部分經(jīng)典的WSN分簇算法如LEACH、HEED等，都屬于分布式算法，Hausdorff算法、響應(yīng)式分布分簇算法(RDCA)也屬于這一類。 (2) 基于地理位置/地理位置無關(guān)算法根據(jù)是否需要借助GPS獲得節(jié)點的地理位置

23、，可以將分簇算法分為基于地理位置的算法與地理位置無關(guān)算法兩類。典型的基于地理位置的算法有GAF等，其他大部分常見的分簇算法，如LEACH算法等，都不需要借助于地理位置信息?；诘乩砦恢玫乃惴ㄓ械男枰@得全局信息，有的只需要通過廣播包獲得相鄰節(jié)點的位置信息。因為傳感器網(wǎng)絡(luò)節(jié)點數(shù)量大，單個節(jié)點造價低、能量有限，而GPS模塊不但成本高而且會額外消耗節(jié)點能量，因此為每個節(jié)點都配備GPS模塊是不經(jīng)濟的。通常的做法是在網(wǎng)絡(luò)中設(shè)置少量信標(biāo)節(jié)點，一般是通過攜帶GPS定位設(shè)備獲得自身的精確位置，然后其他傳感器節(jié)點通過信標(biāo)節(jié)點的位置信息根據(jù)一定的定位算法獲得自身的位置。常用的定位算法有到達時間(TOA)、到達時間

24、差(TDOA)、接收信號強度指示(RSSI)、到達角度(AOA)和距離向量-跳數(shù)等。不過在室內(nèi)、水下或森林等有障礙環(huán)境中無法使用GPS系統(tǒng)，使其應(yīng)用受到一定限制?；诘乩砦恢玫姆执厮惴ㄒ话慵僭O(shè)節(jié)點已知自身的精確位置，而如何獲得自身位置信息則不包括在算法內(nèi)。 (3)確定性/隨機性算法 在網(wǎng)絡(luò)拓撲結(jié)構(gòu)與每個節(jié)點的剩余能量不變的情況下，根據(jù)分簇算法是否能取得確定結(jié)果，可將其分為確定性與隨機性算法。在確定性算法中，節(jié)點必須等待某個特定事件發(fā)生或某些特定節(jié)點已宣布自己的角色(CH還是MN)后，才能做出決定。例如DCA算法必須等待所有權(quán)值高于自己的相鄰節(jié)點宣布成為CH或者加入到某個簇后，才能確定自身是成為

25、CH還是MN。確定性算法的一個不足之處就是收斂時間依賴于網(wǎng)絡(luò)規(guī)模，DCA算法的時間復(fù)雜度為O(d)，d為網(wǎng)絡(luò)直徑(通常用跳數(shù)來定義)，在最差情況下(節(jié)點線性分布)，d可達到n -1(n為節(jié)點個數(shù))。此外網(wǎng)絡(luò)的魯棒性不好，如果一個節(jié)點在拓撲發(fā)現(xiàn)階段后失效，可能造成其相鄰節(jié)點陷入無限期等待。為消除這種現(xiàn)象，一些算法，例如ACE算法限制節(jié)點在一定次數(shù)(如5次后)結(jié)束循環(huán)等待。隨機性算法根據(jù)一定的概率確定節(jié)點是否成為簇頭。LEACH算法中節(jié)點成為簇頭的概率僅與過去若干輪次中節(jié)點自身的狀態(tài)有關(guān)，HEED算法中的概率與剩余能量有關(guān)，還有一些算法同時考慮了節(jié)點度等多種參數(shù)。隨機性算法分簇結(jié)果的優(yōu)化程度通常不

26、如確定性算法，但是收斂速度較快，開銷較小，魯棒性好，特別適合大規(guī)模網(wǎng)絡(luò)。 (4) 單層/多層算法 根據(jù)算法產(chǎn)生的最終拓撲結(jié)構(gòu)，可分為單層和多層算法。單層算法只進行一次分簇，目前提出的大部分分簇算法，如LEACH、HEAD、GAF等都屬于此類，而多層算法在前一次分簇選舉出的簇頭基礎(chǔ)上繼續(xù)進行分簇，選舉出第二層簇頭和簇成員節(jié)點，隨后可以進行第三層、第四層等簇頭選舉。多層算法一般只用于超大規(guī)模WSN，算法較為復(fù)雜。文獻提出了一種多層算法(層數(shù)從1到5)，該算法以最小化系統(tǒng)整體能量消耗為目標(biāo)，推導(dǎo)出系統(tǒng)整體能量消耗的解析式，然后通過數(shù)值計算求出不同節(jié)點密度條件下的最優(yōu)解。 (5) 簇內(nèi)單跳/多跳算法

27、根據(jù)簇內(nèi)MN到CH的跳數(shù)，可分為簇內(nèi)單跳與簇內(nèi)多跳算法，也可采用單跳算法的MN直接與CH進行通信，而多跳算法中的MN可通過其他MH中繼與CH進行通信。LEACH、HEED等算法采用單跳方式，而Max-min D等算法使用多跳方式。4.2 基于無線傳感器網(wǎng)絡(luò)協(xié)同采樣算法的描述及其MATLAB仿真分析協(xié)同采樣是一種分布式主動采樣制度，該制度要求每一個傳感器合作完成任務(wù)數(shù)據(jù)采樣并且利用簡潔的合作方式通過相鄰傳感器節(jié)點實現(xiàn)數(shù)據(jù)的傳播。這可以通過利用在相鄰傳感的內(nèi)部聯(lián)系實現(xiàn)。該制度的目標(biāo)是在確保收集數(shù)據(jù)的質(zhì)量的前提下將發(fā)送冗余信息通過無線信道的能量浪費降到最低。協(xié)同采樣需要兩個關(guān)鍵操作部分：在單個傳感器

28、節(jié)點，一個傳感器測量模型作為一個基于當(dāng)?shù)貍鞲衅鳒y量的空時坐標(biāo)的函數(shù)，這些通過竊聽鄰近傳感器無線傳播而獲得的。傳感器協(xié)同通過向其相鄰節(jié)點聲明它的當(dāng)?shù)販y量以幫助建立覆蓋全部傳感器域的全局函數(shù)逼近。為了減少冗余信息的傳播，每一個傳感器節(jié)點需要判斷。在Slepian和Wolf的開創(chuàng)性工作中顯示：如果知道兩個傳感器節(jié)點關(guān)聯(lián)的先驗知識，那么相互之間所需的通信量將會大大減少；然而這種先驗知識很少知道。因此需要在沒有傳感器之間聯(lián)系說明的先驗知識的情況下進行大量的工作來匯總在傳感器之間傳播信息的特定數(shù)據(jù)。一個好的數(shù)據(jù)子集應(yīng)該提供一定覆蓋范圍概念的觀點被提了出來，并且關(guān)于這種觀點已經(jīng)有了許多不同的形式。一些基于這

29、種理念所提出的方法涉及到讓節(jié)點選擇一個代表節(jié)點來代表相鄰節(jié)點區(qū)，但這是以在選擇代表節(jié)點時架高節(jié)點并且在選擇一個節(jié)點來代表整個區(qū)域出現(xiàn)錯誤為代價的。另一個觀點是去估計優(yōu)先函數(shù)而不是無線傳感網(wǎng)絡(luò)的節(jié)點值。然而這個工作被限制在將傳感器區(qū)域劃分為一系列的Voronoi胞區(qū)，或者僅僅是最鄰近算法。有人建議：一些特定的增益能夠通過計算當(dāng)?shù)氐乃@得數(shù)據(jù)的時間線和更新來獲得，一個節(jié)點通過延遲這些對稱的平衡達到一個政策，走向一個更加分布的形式。我們建議在傳感器遠距離傳播中采用這種分布式形式。這個隱含在協(xié)同采樣（CS）的想法是用了一個傳播政策：不僅僅在當(dāng)?shù)孛恳粋€節(jié)點上有效率，同樣適用于網(wǎng)絡(luò)，或者至少是廣播范圍中傳

30、感器區(qū)域組成的網(wǎng)絡(luò)中。舉個例子：如果在這個網(wǎng)絡(luò)中的一個節(jié)點有關(guān)于模型的知識，該模型是FC最大的利用其讀物。那么這個節(jié)點就可以利用它竊聽到的信息去建立一個初步的估計，該估計是關(guān)于FC自己讀物可以達到的最大值。如果FC的最大值不遠，那么這個節(jié)點所擁有的信息就會有冗余并且這個節(jié)點不會傳播或報告它的讀物。通過保持靜默，這個節(jié)點同樣向這個網(wǎng)絡(luò)的剩余節(jié)點做出表示并且向FC發(fā)送節(jié)點自己的對當(dāng)前估計的認可度。我們在估計一個傳感器網(wǎng)絡(luò)的隱藏物理函數(shù)中應(yīng)用CS的觀點來展示CS在實際中的應(yīng)用。在仿真之前我們對傳感器傳播聲明一些假設(shè)：（1）傳播線路是對稱的，這就是說如果傳感器節(jié)點能夠聽到傳感器 的廣播，那么傳感器同樣

31、能夠聽到傳感器的廣播。（2）每個傳感器的傳播范圍是一樣的。（3）所有傳感器節(jié)點傳播代價是相同的。（4）傳播時間相對于退避時間可忽略不計。（5）FC沒有功率約束。（6）在每次傳播之前沒有握手。（7）所有傳播都能被FC聽到并正確解碼。 我們個節(jié)點用來表示，同時用來表示節(jié)點在時刻的瞬時讀物。這個讀物是通過一個未知的函數(shù)來得到。為了簡化，在本論文中我們只關(guān)注時間為常數(shù)的函數(shù)，就是說。這篇論文是跟隨尋找實際函數(shù)f的步伐。因為只有我們估計在傳感器位置的函數(shù)f，估計也是個同樣的過程。在第K次報告之后：這里 是一個速記符號適用于所有傳感器節(jié)點，這些節(jié)點已經(jīng)向上面節(jié)點傳過報告包括第K次報告。是一個估計值用來近似

32、隱含在當(dāng)前信息下的函數(shù)值，它可能是個核心函數(shù)或者是一個最鄰近映射。一個獲得估計值與實際值之間測量誤差的方法是測量預(yù)測讀物和實際讀物的誤差，這只適用于每個節(jié)點上的差異。如果我們定義作為第K次報告被傳播的節(jié)點的子集，那么從一個最優(yōu)化的觀點，這個問題能夠被闡述這樣，任給一個誤差準(zhǔn)則： 不行的是，在大多數(shù)情形下，這個解決方案和1,2,3.，k采樣的組合只能通過一個耗盡的組合整體得到。然而，如果我們采取貪婪的觀點，那么我們在這最優(yōu)化的方式中選擇（k+1）次的報告。在我們的情形中，在第(k+1)次報告中的最優(yōu)節(jié)點用表示并被定義為在所有可能的傳感器節(jié)點中的最高網(wǎng)絡(luò)收益。由于我們假設(shè)每一個節(jié)點的傳播能量耗損相

33、同，最優(yōu)化的焦點就會聚集在報告的收益上。如果我們被允許選擇下一個的節(jié)點，理論上，我們會考慮一個解決方案來選擇節(jié)點報告，來達到所有節(jié)點間全部誤差的最小化。之前的工作已經(jīng)顯示在一些特定的情況下，在這種結(jié)構(gòu)區(qū)域中選擇報告給下一個的節(jié)點實質(zhì)上獲得過量的消極采樣。大量的研究針對和它們的影響在性能上的區(qū)別。大多數(shù)工作涉及到維持和更新的概率模型，針對分布式傳感器節(jié)點讀物和尋找傳感器節(jié)點，使得該模型有最小的信心或者有最高的熵。最終的結(jié)果是非常密集的計算和通訊工作。那么這些節(jié)點如何在仍然協(xié)同的工作的同時以一種分布式的方式來指定它們的傳播延遲呢。對于計算和通訊來說，計算或者是非常密集的，尤其在融合中心。然而，我們

34、建議每一個傳感器以它們自己的方程來執(zhí)行這個任務(wù)：。在這里是的局部版本，其中是利用節(jié)點從信道和傳感器自己位置來估計局部的。注意到對任何來說局部估計并不能預(yù)測，但是僅僅可用于第i個傳感器節(jié)點。有一個重要的區(qū)別需要強調(diào)一下：既不感興趣也不代表全局估計，它僅僅是在傳感器位置上的局部版本。這樣，如果FC希望的話它就能執(zhí)行更復(fù)雜的運算，但這不需要計算這些信息反饋給每一個傳感器，傳感器也不需要計算它自己的估計給FC，這樣就節(jié)省了時間和通信成本了。 我們假設(shè)傳感器的傳播范圍足夠大，傳感器i傳播范圍之外的傳感器讀物相關(guān)性很小或者對傳感器i的影響很小，反之亦然。那么那些竊聽到在傳播范圍之內(nèi)報告的傳感器節(jié)點同樣有局

35、部版本，定義為。此外，每一個傳感器節(jié)點i同樣知道它精確的讀物并且有對它們自己有用的信息而這些信息FC卻不能得到，特別是節(jié)點i精確的當(dāng)?shù)卣`差。表1對比了不同的當(dāng)?shù)刈兞糠弦约斑@些局部變量所對應(yīng)的全局變量。表1理想情況下，如果我們對所有的節(jié)點設(shè)定了一個確定性退避延遲這個延遲在每一個節(jié)點上與預(yù)測誤差是成反比例的，那么有最大預(yù)測誤差的節(jié)點會最先傳播，。因為每一個傳感器能夠計算它們自己的，它們就可以決定它們自己的傳播的時刻。在網(wǎng)絡(luò)中每一個傳播后。如果傳感器節(jié)點在延遲時間內(nèi)的任意時刻接收到新的信息或者需要傳播，那么該節(jié)點就需要更新它的誤差并且重新計算它的延遲。一旦節(jié)點已經(jīng)等待了它自己的延遲時間，它就會傳播它自己的讀物。如果再一段時間T內(nèi)沒有傳播給FC中心，那么過程就會停止這種事件就會發(fā)生就像沉默預(yù)示著一種共識：進一步的貢獻所獲得的利益是有限的。算法1和2展示了Pseudo碼被全局或局部利用的算法的例子。為了測量我們算法的性能，我們將它與稱之為“貪婪Oracle”分離器進行對比。一個Oracle在選擇下一個采樣的最好的傳感器讀物時會有關(guān)于和的全部信息。這個Oracle的性能可以被認為是一個最好的可能的性能。我們自適應(yīng)方法的性