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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、等差別。同樣，它們也是我們設計、分析具體協(xié)議和算法時要考察的容。4. 基于無線傳感器網(wǎng)絡分簇構架的協(xié)同采樣算法描述與其MATLAB仿真分析4.1無線傳感器網(wǎng)絡中的分簇架構與算法介紹4.1.1無線傳感器網(wǎng)絡中的分簇架構在采用分簇結構的無線傳感器網(wǎng)絡中，網(wǎng)絡節(jié)點被劃分為若干個簇。每個簇通常由一個簇頭節(jié)點(CH)以與多個成員節(jié)點(MN)組成。成員節(jié)點只與簇頭通信，簇頭與簇頭構成高一級的虛擬骨干網(wǎng)，負責簇的數(shù)據(jù)融合和簇間數(shù)據(jù)轉發(fā)。因為簇頭節(jié)點的能量消耗較大，通常采用周期性選擇簇頭節(jié)點的方法均衡網(wǎng)絡中節(jié)點能量的消耗。簇頭的集合形成連通統(tǒng)治集(CDS)，因為獲得最優(yōu)CDS是NPC問題，因此實際提出的算法均

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

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

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

23、于地理位置的算法有GAF等，其他大部分常見的分簇算法，如LEACH算法等，都不需要借助于地理位置信息。基于地理位置的算法有的需要獲得全局信息，有的只需要通過廣播包獲得相鄰節(jié)點的位置信息。因為傳感器網(wǎng)絡節(jié)點數(shù)量大，單個節(jié)點造價低、能量有限，而GPS模塊不但成本高而且會額外消耗節(jié)點能量，因此為每個節(jié)點都配備GPS模塊是不經(jīng)濟的。通常的做法是在網(wǎng)絡中設置少量信標節(jié)點，一般是通過攜帶GPS定位設備獲得自身的精確位置，然后其他傳感器節(jié)點通過信標節(jié)點的位置信息根據(jù)一定的定位算法獲得自身的位置。常用的定位算法有到達時間(TOA)、到達時間差(TDOA)、接收信號強度指示(RSSI)、到達角度(AOA)和距離

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

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

26、) 單層/多層算法 根據(jù)算法產(chǎn)生的最終拓撲結構，可分為單層和多層算法。單層算法只進行一次分簇，目前提出的大部分分簇算法，如LEACH、HEAD、GAF等都屬于此類，而多層算法在前一次分簇選舉出的簇頭基礎上繼續(xù)進行分簇，選舉出第二層簇頭和簇成員節(jié)點，隨后可以進行第三層、第四層等簇頭選舉。多層算法一般只用于超大規(guī)模WSN，算法較為復雜。文獻提出了一種多層算法(層數(shù)從1到5)，該算法以最小化系統(tǒng)整體能量消耗為目標，推導出系統(tǒng)整體能量消耗的解析式，然后通過數(shù)值計算求出不同節(jié)點密度條件下的最優(yōu)解。(5) 簇單跳/多跳算法 根據(jù)簇MN到CH的跳數(shù)，可分為簇單跳與簇多跳算法，也可采用單跳算法的MN直接與CH

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

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

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

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

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

32、法是測量預測讀物和實際讀物的誤差，這只適用于每個節(jié)點上的差異。如果我們定義作為第K次報告被傳播的節(jié)點的子集，那么從一個最優(yōu)化的觀點，這個問題能夠被闡述這樣，任給一個誤差準則：不行的是，在大多數(shù)情形下，這個解決方案和1,2,3.，k采樣的組合只能通過一個耗盡的組合整體得到。然而，如果我們采取貪婪的觀點，那么我們在這最優(yōu)化的方式中選擇（k+1）次的報告。在我們的情形中，在第(k+1)次報告中的最優(yōu)節(jié)點用表示并被定義為在所有可能的傳感器節(jié)點中的最高網(wǎng)絡收益。由于我們假設每一個節(jié)點的傳播能量耗損一樣，最優(yōu)化的焦點就會聚集在報告的收益上。如果我們被允許選擇下一個的節(jié)點，理論上，我們會考慮一個解決方案來選

33、擇節(jié)點報告，來達到所有節(jié)點間全部誤差的最小化。之前的工作已經(jīng)顯示在一些特定的情況下，在這種結構區(qū)域中選擇報告給下一個的節(jié)點實質上獲得過量的消極采樣。大量的研究針對和它們的影響在性能上的區(qū)別。大多數(shù)工作涉與到維持和更新的概率模型，針對分布式傳感器節(jié)點讀物和尋找傳感器節(jié)點，使得該模型有最小的信心或者有最高的熵。最終的結果是非常密集的計算和通訊工作。那么這些節(jié)點如何在仍然協(xié)同的工作的同時以一種分布式的方式來指定它們的傳播延遲呢。對于計算和通訊來說，計算或者是非常密集的，尤其在融合中心。然而，我們建議每一個傳感器以它們自己的方程來執(zhí)行這個任務：。在這里是的局部版本，其中是利用節(jié)點從信道和傳感器自己位置

34、來估計局部的。注意到對任何來說局部估計并不能預測，但是僅僅可用于第i個傳感器節(jié)點。有一個重要的區(qū)別需要強調一下：既不感興趣也不代表全局估計，它僅僅是在傳感器位置上的局部版本。這樣，如果FC希望的話它就能執(zhí)行更復雜的運算，但這不需要計算這些信息反饋給每一個傳感器，傳感器也不需要計算它自己的估計給FC，這樣就節(jié)省了時間和通信成本了。我們假設傳感器的傳播圍足夠大，傳感器i傳播圍之外的傳感器讀物相關性很小或者對傳感器i的影響很小，反之亦然。那么那些竊聽到在傳播圍之報告的傳感器節(jié)點同樣有局部版本，定義為。此外，每一個傳感器節(jié)點i同樣知道它精確的讀物并且有對它們自己有用的信息而這些信息FC卻不能得到，特別

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