傳感器網(wǎng)絡(luò)的構(gòu)想最早由DARPA于上世紀(jì)70年代末提出，但大規(guī)模研究的興起是在2000年以后。在這個(gè)時(shí)候，無線傳感器網(wǎng)絡(luò)所涉及的微電機(jī)系統(tǒng)、嵌入式系統(tǒng)、微處理器、無線通信技術(shù)等都取得了巨大的進(jìn)步，已經(jīng)能夠制造出體積小、重量輕的傳感器節(jié)點(diǎn)。但近兩年由于大規(guī)模實(shí)際應(yīng)用的困難，這股研究熱潮正在逐漸消退，研究人員正在重新審視它的應(yīng)用設(shè)想，一部分研究力量開始轉(zhuǎn)向物聯(lián)網(wǎng)。目前傳感器網(wǎng)絡(luò)的研究重點(diǎn)不在各種具體的技術(shù)，而是應(yīng)用。要尋找最適合它的應(yīng)用，并建立實(shí)際的應(yīng)用示范系統(tǒng)。無線傳感器網(wǎng)絡(luò)概述無線傳感器網(wǎng)絡(luò)是在自組網(wǎng)基礎(chǔ)上發(fā)展起來的一項(xiàng)技術(shù)。不同于一般的通信網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)的任務(wù)不是通信，而是要監(jiān)視周圍環(huán)境。無線傳感器網(wǎng)絡(luò)由具有感知、計(jì)算及通信能力的一群微小節(jié)點(diǎn)組成。這些節(jié)點(diǎn)部署在要監(jiān)視的區(qū)域中，采集指定的環(huán)境參數(shù)，如溫度、振動(dòng)、化學(xué)濃度等，并將數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)供分析。傳感器節(jié)點(diǎn)的特點(diǎn)由于傳感器網(wǎng)絡(luò)常部署于地面，受地面障礙物、植被等干擾，無線通信的距離一般較短，通信干擾大，鏈路質(zhì)量差，傳輸速率低。可見，每個(gè)傳感器節(jié)點(diǎn)的能力（資源）是非常有限的，單個(gè)傳感器節(jié)點(diǎn)的作用很小，但是如果將大量這樣的節(jié)點(diǎn)以適當(dāng)方式組成網(wǎng)絡(luò)，并將它們的輸出有機(jī)地關(guān)聯(lián)與融合，整個(gè)網(wǎng)絡(luò)可提供遠(yuǎn)高于單個(gè)節(jié)點(diǎn)的強(qiáng)大功能。傳感器網(wǎng)絡(luò)的特點(diǎn)放置在野外環(huán)境的傳感器節(jié)點(diǎn)很容易受惡劣環(huán)境影響而失效，或因?yàn)殡姵睾谋M而死亡，而替換失效的節(jié)點(diǎn)往往不可能或代價(jià)很高，因此人們一般會(huì)在監(jiān)視區(qū)域中放置大量的節(jié)點(diǎn)，通過節(jié)點(diǎn)的冗余部署來提高網(wǎng)絡(luò)的生存能力和可用性。以下各種原因都可能導(dǎo)致無線傳感器網(wǎng)絡(luò)的拓?fù)浒l(fā)生改變：(1)出于節(jié)能和減少傳輸沖突的考慮，傳感器節(jié)點(diǎn)定期在工作狀態(tài)和睡眠狀態(tài)之間切換；(2)節(jié)點(diǎn)可能因故障、電源耗盡、鏈路中斷等原因與其它節(jié)點(diǎn)斷連；(3)網(wǎng)絡(luò)中可能會(huì)補(bǔ)充一些新的節(jié)點(diǎn)；(4)部分節(jié)點(diǎn)具備移動(dòng)的能力。由于傳感器網(wǎng)絡(luò)通常缺乏集中式控制機(jī)制，因此傳感器節(jié)點(diǎn)必須具有自組織能力，能夠自動(dòng)完成網(wǎng)絡(luò)的初始化過程并適應(yīng)網(wǎng)絡(luò)拓?fù)涞母淖儭４蟛糠謧鞲衅鞴?jié)點(diǎn)靠電池供電，能量非常有限，而龐大的節(jié)點(diǎn)數(shù)目以及節(jié)點(diǎn)部署的環(huán)境（如野外、內(nèi)嵌建筑物內(nèi)）往往使得更換電池不可能，因此傳感器節(jié)點(diǎn)的能量水平?jīng)Q定了網(wǎng)絡(luò)的壽命。傳感器節(jié)點(diǎn)微小的體積也導(dǎo)致了它的計(jì)算能力和存儲(chǔ)容量很有限，不能進(jìn)行復(fù)雜的計(jì)算和存儲(chǔ)大量的數(shù)據(jù)，節(jié)點(diǎn)的無線通信帶寬通常也只有幾百Kbps。傳感器網(wǎng)絡(luò)中各種協(xié)議及算法的設(shè)計(jì)都必須以節(jié)能為第一要旨，其中特別重要的是要盡量減少網(wǎng)絡(luò)中的通信量，因?yàn)橥ㄐ畔牡哪芰孔畲蟆２渴馃o線傳感器網(wǎng)絡(luò)的目的是監(jiān)視物理環(huán)境，從中獲得用戶感興趣的信息，因此用戶關(guān)心的是從網(wǎng)絡(luò)中獲取的信息而不是網(wǎng)絡(luò)本身。以數(shù)據(jù)為中心是無線傳感器網(wǎng)絡(luò)區(qū)別于傳統(tǒng)通信網(wǎng)絡(luò)的最大特點(diǎn)。另外，為減少冗余傳輸、數(shù)據(jù)融合等需要，節(jié)點(diǎn)具有數(shù)據(jù)處理的能力，這也是不同于傳統(tǒng)通信網(wǎng)絡(luò)的特點(diǎn)。應(yīng)用相關(guān)也是傳感器網(wǎng)絡(luò)區(qū)別于傳統(tǒng)網(wǎng)絡(luò)的一個(gè)重要特點(diǎn)。傳感器節(jié)點(diǎn)有限的能力及電源供應(yīng)決定了傳感器網(wǎng)絡(luò)不適宜作為一個(gè)提供通用服務(wù)的網(wǎng)絡(luò)系統(tǒng)，加上監(jiān)視應(yīng)用嚴(yán)格的實(shí)時(shí)性要求，傳感器網(wǎng)絡(luò)必須與特定應(yīng)用緊密耦合才能設(shè)計(jì)出一個(gè)高效的應(yīng)用系統(tǒng)。因此，跨層設(shè)計(jì)在傳感器網(wǎng)絡(luò)中是一個(gè)必然的選擇。傳感器網(wǎng)絡(luò)與移動(dòng)自組網(wǎng)的不同雖然無線傳感器網(wǎng)絡(luò)在一定程度上類似于無線自組網(wǎng)，但是兩者在規(guī)模、節(jié)點(diǎn)密度、網(wǎng)絡(luò)拓?fù)浼盁o線通信方式等方面有著很大的不同。無線自組網(wǎng)的節(jié)點(diǎn)數(shù)量通常是幾十或上百，而無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)目往往要高出好幾個(gè)數(shù)量級(jí)，節(jié)點(diǎn)密度很大，而且容易受到環(huán)境影響。無線自組網(wǎng)的拓?fù)渥兓饕晒?jié)點(diǎn)的運(yùn)動(dòng)引起，而傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)大部分是固定不動(dòng)的，拓?fù)渥兓饕晒?jié)點(diǎn)的休眠調(diào)度、環(huán)境干擾或者節(jié)點(diǎn)故障引起。另外，和無線自組網(wǎng)中的節(jié)點(diǎn)相比，傳感器節(jié)點(diǎn)的處理能力、存儲(chǔ)能力和通信能力都十分有限。所以，移動(dòng)自組網(wǎng)中的協(xié)議與算法往往并不適合無線傳感器網(wǎng)絡(luò)。傳感器網(wǎng)絡(luò)與移動(dòng)自組網(wǎng)的不同雖然無線傳感器網(wǎng)絡(luò)在一定程度上類似于無線自組網(wǎng)，但是兩者在規(guī)模、節(jié)點(diǎn)密度、網(wǎng)絡(luò)拓?fù)浼盁o線通信方式等方面有著很大的不同。傳感器網(wǎng)絡(luò)應(yīng)用舉例小氣候是指森林、城市、洞穴等局部地區(qū)的氣候。紅杉樹非常高大，成熟的紅杉樹可以高達(dá)60-100米，樹干直徑巨大。在加利福尼亞有一株遠(yuǎn)在耶穌誕生以前就生存于叢林之中的北美紅杉樹，年齡已超過2200年，樹干直徑達(dá)4米，單株材積700多立方米，可供建造30多幢農(nóng)村住房。所以單棵紅杉樹就可以形成一個(gè)小氣候，監(jiān)視這個(gè)小氣候可以得到森林氣候的一個(gè)樣本。傳統(tǒng)方法是將一套重約30磅的測量設(shè)備用絞車吊在樹冠下，在不同的高度上測量和收集數(shù)據(jù)，每隔一定時(shí)間收集一次數(shù)據(jù)。這種方法只能在一個(gè)較短的時(shí)間內(nèi)收集數(shù)據(jù)。無線氣象站圖示為研究人員使用的傳感器節(jié)點(diǎn)。一個(gè)無線氣象站裝進(jìn)一個(gè)膠卷盒子大小的空心圓柱體中，外面的包裝是防雨的。頂上是兩個(gè)入射光傳感器，測量總的太陽輻射，特別是可見光和葉綠素敏感的波段；底部有一對(duì)相同的傳感器對(duì)，測量輻射的光。底部還有環(huán)境傳感器，測量相對(duì)濕度、氣壓和溫度。中間的mote板上有處理器、存儲(chǔ)器和低功耗無線收發(fā)器，可以收集數(shù)據(jù)、處理數(shù)據(jù)，并將數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)。使用傳感器網(wǎng)絡(luò)可以在樹的許多不同位置上同時(shí)采集數(shù)據(jù)，而且可以在較長的一段時(shí)間內(nèi)持續(xù)收集數(shù)據(jù)。利用相同的方法，可以在森林的不同地方部署傳感器網(wǎng)絡(luò)，如森林的中心處、迎風(fēng)面、背風(fēng)面、向陽面等，然后利用長距離的上行鏈路將這些數(shù)據(jù)發(fā)送到匯聚節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果片段圖示為三天內(nèi)從一棵35米高的紅杉樹上、四個(gè)高度的16個(gè)節(jié)點(diǎn)處采集到的數(shù)據(jù)。節(jié)點(diǎn)每隔5分鐘采樣一次，對(duì)每一高度計(jì)算一個(gè)平均值。測量數(shù)據(jù)顯示，在每天的變化周期中，樹頂比森林底部經(jīng)歷更大的氣候波動(dòng)。其它示范性應(yīng)用包括：精確農(nóng)業(yè)、橋梁或建筑物的健康狀況監(jiān)測、煤礦巷道的位移監(jiān)測、戰(zhàn)場監(jiān)視、野生動(dòng)物遷徙、目標(biāo)定位與跟蹤、智能交通等。人居環(huán)境監(jiān)視利用plug節(jié)點(diǎn)的多模式感知能力，可以較準(zhǔn)確地推斷發(fā)生的事件。比如，將一個(gè)臺(tái)燈插到插線板上并擰亮臺(tái)燈，通過電流傳感器可以知道臺(tái)燈打開的時(shí)刻，通過聲音傳感器、光傳感器（插插頭時(shí)手遮住了光源）、振動(dòng)傳感器等可以推斷出臺(tái)燈插入插線板的時(shí)間。另外，不同的電器設(shè)備具有不同的啟動(dòng)電流圖，稱電流特征，據(jù)此可以識(shí)別不同類型甚至不同個(gè)體的電器在。有些推斷僅從電流啟動(dòng)圖還不能做出，節(jié)點(diǎn)可將提取的信號(hào)特征發(fā)送到某個(gè)節(jié)點(diǎn)進(jìn)行融合。將整個(gè)plug網(wǎng)絡(luò)看成一個(gè)整體，可以了解到plug網(wǎng)絡(luò)所在環(huán)境的活動(dòng)情況。比如，辦公室中電燈的開/關(guān)、聲音、電器的開/關(guān)及工作、各電器的電源消耗等。本文還設(shè)計(jì)了一個(gè)手持設(shè)備，當(dāng)它靠近一個(gè)plug節(jié)點(diǎn)時(shí)，屏幕上會(huì)顯示出該節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置、節(jié)點(diǎn)上各個(gè)傳感器的圖標(biāo)、各個(gè)傳感器的最大值/最小值/平均值等。本文采用虛擬現(xiàn)實(shí)的方法建立了一個(gè)shadowlab。Shadowlab由整個(gè)建筑物的實(shí)際大小平面圖組成，從傳感器網(wǎng)絡(luò)中得到的數(shù)據(jù)寫入虛擬世界，用火苗的大小表示能源消耗的高低。節(jié)點(diǎn)定位對(duì)于大規(guī)模隨機(jī)部署（飛機(jī)或火箭彈播撒）的傳感器網(wǎng)絡(luò)來說，節(jié)點(diǎn)定位是一項(xiàng)重要的基礎(chǔ)功能，因?yàn)槿魏苇h(huán)境數(shù)據(jù)如果沒有位置信息的話，都是沒有意義的。手工為每個(gè)節(jié)點(diǎn)設(shè)定位置是不可能的（數(shù)量多，無法預(yù)先確定位置，更不可能到現(xiàn)場設(shè)置），GPS定位系統(tǒng)無法大規(guī)模應(yīng)用到傳感器節(jié)點(diǎn)上（代價(jià)、體積、能耗、受環(huán)境影響），因此必須依靠節(jié)點(diǎn)之間的相互協(xié)作來估計(jì)各自的位置。節(jié)點(diǎn)定位算法的分類研究得較多的是絕對(duì)定位。在相對(duì)定位中，如果給定了三個(gè)參考點(diǎn)的絕對(duì)位置，則相對(duì)定位可以轉(zhuǎn)化為絕對(duì)定位?；跍y量的定位算法利用了傳感器節(jié)點(diǎn)測量距離或測量角度的能力。硬件配置不同的節(jié)點(diǎn)可使用的測量方法不同，有些配置了無線電、紅外線、激光等可以測量距離的設(shè)備，有些配備了可以測量信號(hào)到達(dá)方向（角度）的設(shè)備，測量精度高的設(shè)備較復(fù)雜，測量精度低的設(shè)備較簡單。下面我們介紹的幾個(gè)定位算法均為絕對(duì)定位算法。假設(shè)網(wǎng)絡(luò)中存在一定數(shù)量的參考節(jié)點(diǎn)，這些節(jié)點(diǎn)的位置在部署時(shí)即已知（比如通過GPS或手工配置），其余節(jié)點(diǎn)為待定位節(jié)點(diǎn)（也稱未知節(jié)點(diǎn)），未知節(jié)點(diǎn)依據(jù)參考節(jié)點(diǎn)的位置，通過某種測距手段及相互之間的協(xié)作來確定自己的位置。衡量定位算法的性能指標(biāo)平均定位誤差是最重要的性能指標(biāo)，算法復(fù)雜度及收斂速度涉及耗能，健壯性是指定位算法抵御噪聲、攻擊的能力。2.1測距技術(shù)大多數(shù)已有的位置發(fā)現(xiàn)方法由兩個(gè)基本的階段組成：距離（或角度）估計(jì)，距離（或角度）融合。RSSI：該方法測量接收端收到的信號(hào)強(qiáng)度，根據(jù)已知的發(fā)送功率計(jì)算路徑損耗，然后根據(jù)某個(gè)理論模型或經(jīng)驗(yàn)?zāi)Ｐ蛯⒙窂綋p耗轉(zhuǎn)化成距離估計(jì)。該方法主要用于射頻信號(hào)?；跁r(shí)間的方法：記錄信號(hào)的到達(dá)時(shí)間或兩種信號(hào)的到達(dá)時(shí)間差，根據(jù)已知的信號(hào)傳播速度直接換算成距離。該方法可用于多種信號(hào)，如射頻、聲音、紅外和超聲波等。AoA：接收節(jié)點(diǎn)估計(jì)信號(hào)的到達(dá)角度，然后使用簡單的幾何關(guān)系來計(jì)算節(jié)點(diǎn)位置。RSSI該方法使用射頻信號(hào)衰減與傳輸距離之間的關(guān)系模型，接收節(jié)點(diǎn)根據(jù)已知的信號(hào)發(fā)射功率和接收到的信號(hào)強(qiáng)度估算路徑損耗，然后根據(jù)射頻信號(hào)傳輸模型將路徑損耗轉(zhuǎn)換成距離。PT為發(fā)送功率，PL（d0）為參考距離d0的路徑損耗，η為路徑損耗指數(shù)，Xσ為零均值、方差為σ2的高期隨機(jī)變量。對(duì)射頻信號(hào)傳輸特性的大量研究表明，射頻信號(hào)的傳輸特性受環(huán)境變化（天氣、城市或郊區(qū)、室內(nèi)或室外）影響很大。[1]使用實(shí)驗(yàn)的方法研究RSSI與距離的關(guān)系，發(fā)現(xiàn)無法得到信號(hào)衰減與距離之間的一致模型。原因主要有以下幾個(gè)方面：（1）環(huán)境的影響：多路徑、衰落、遮蔽效應(yīng)。（2）天線高度：若節(jié)點(diǎn)放置于地面，使用最大發(fā)射功率等級(jí)，信號(hào)傳輸距離大約為30米；若將節(jié)點(diǎn)放置于離地面1.5米處，信號(hào)傳輸距離可達(dá)100米。（3）節(jié)點(diǎn)未精確校準(zhǔn)：廉價(jià)的傳感器節(jié)點(diǎn)沒有精確的校準(zhǔn)單元，當(dāng)不同節(jié)點(diǎn)的使用相同的發(fā)射功率等級(jí)發(fā)送時(shí)，實(shí)際的發(fā)射功率差異很大，差異經(jīng)?？梢赃_(dá)到幾個(gè)dB。對(duì)于發(fā)射功率的差異，一種可能的解決方案是在使用前將所有的節(jié)點(diǎn)與一個(gè)參考節(jié)點(diǎn)進(jìn)行校準(zhǔn)，將增益因子存儲(chǔ)在非易失性存儲(chǔ)器中。如果要部署成百上千的節(jié)點(diǎn)，這種手工校準(zhǔn)方法很費(fèi)時(shí)。對(duì)于節(jié)點(diǎn)高度差異，如果采用飛機(jī)播撒的方法進(jìn)行大規(guī)模部署，則這個(gè)差異無法預(yù)先獲知，只能在節(jié)點(diǎn)部署后進(jìn)行自動(dòng)校準(zhǔn)。基于以上原因，RSSI的測距精度只能達(dá)到幾米，無法提供精確的定位。但該技術(shù)對(duì)硬件要求較低，利用節(jié)點(diǎn)的無線電收發(fā)裝置便能測量接收信號(hào)強(qiáng)度，對(duì)于廉價(jià)的傳感器節(jié)點(diǎn)來說是最理想的測試方法。TDoA該方法精度較高，[4]使用TDoA測量相距3米的兩個(gè)節(jié)點(diǎn)之間的距離，測距精度達(dá)到2cm。超聲信號(hào)的傳輸也受環(huán)境變化的影響，如多徑效應(yīng)，但較容易檢測。接收節(jié)點(diǎn)只測量第一個(gè)到達(dá)的信號(hào)脈沖（直線傳輸），而忽略隨后到來的信號(hào)脈沖。環(huán)境改變對(duì)信號(hào)強(qiáng)度的影響很大，但TDoA依賴的是信號(hào)到達(dá)時(shí)間差，這個(gè)影響比較小。由于超聲信號(hào)的傳輸距離較小，一般節(jié)點(diǎn)只提供幾米到十幾米的距離。增大傳輸距離要求更多更高的成本，并消耗更多的能量。該方法與RSSI相比，需要增加超聲收發(fā)裝置，增加了成本和功耗。RSSI與TDoA的比較[4]比較了RSSI和TDoA兩種測距方法，如表所示。實(shí)驗(yàn)發(fā)現(xiàn)，使用射頻信號(hào)和超聲信號(hào)的TDoA比RSS更可靠。但由于超聲信號(hào)的傳輸距離較短，TDoA要求的節(jié)點(diǎn)密度較大，在較稀疏的網(wǎng)絡(luò)中適宜采用RSS測距技術(shù)。AoA通常使用天線陣列或多個(gè)接收器來得到信號(hào)到來的方向。一個(gè)具有這種能力的傳感器節(jié)點(diǎn)是由MIT的CricketCompass項(xiàng)目開發(fā)的，同時(shí)使用到達(dá)信號(hào)的時(shí)間差和相位差。為獲得到達(dá)角度，每個(gè)節(jié)點(diǎn)使用兩個(gè)超聲波接收器，放置間隔為L。利用TDoA得到距離x1和x2，利用x1、x2和L可以計(jì)算出到發(fā)送節(jié)點(diǎn)的角度θ。箭頭方向?yàn)楣?jié)點(diǎn)的主軸，所有角度都是相對(duì)主軸報(bào)告的。該方法的硬件設(shè)備較復(fù)雜，體積和功耗都較大，要求兩節(jié)點(diǎn)之間存在可視通路2.2距離（角度）融合最基本和最直觀的方法是三邊測量法，它通過計(jì)算3個(gè)圓的交點(diǎn)來定位節(jié)點(diǎn)，如圖所示。若使用AoA測量角度，可使用三角測量法計(jì)算位置，也可以將三角測量問題轉(zhuǎn)化成三邊測量問題。通過最小化測量距離和估計(jì)距離之間的差異來估計(jì)節(jié)點(diǎn)位置。當(dāng)測距有誤差的時(shí)候，三個(gè)圓或多個(gè)圓不交于一點(diǎn)，常采用這種方法。原子多邊測量當(dāng)未知節(jié)點(diǎn)位于至少三個(gè)參考節(jié)點(diǎn)的通信距離內(nèi)時(shí)，可以估計(jì)自己的位置。如果有四個(gè)或更多個(gè)參考節(jié)點(diǎn)，還可以估計(jì)本地的超聲信號(hào)傳播速度。方程中s為估計(jì)的超聲信號(hào)傳播速度，t為射頻信號(hào)與超聲信號(hào)到達(dá)的時(shí)間差。協(xié)同多邊測量原子多邊測量需要滿足的條件是：未知節(jié)點(diǎn)位于至少3個(gè)參考節(jié)點(diǎn)的一跳距離內(nèi)。如圖(a)所示。如果不足3個(gè)參考節(jié)點(diǎn)，或者3個(gè)參考節(jié)點(diǎn)在一條直線上，則必須使用協(xié)同多邊測量。在協(xié)同多邊測量中，未知節(jié)點(diǎn)使用多跳距離之外的參考節(jié)點(diǎn)位置，并且可以估算出本節(jié)點(diǎn)及一個(gè)或多個(gè)其它未知節(jié)點(diǎn)的位置。圖(b)是可以運(yùn)用協(xié)同多邊測量的典型拓?fù)浣Y(jié)構(gòu)之一。參與節(jié)點(diǎn)與參與節(jié)點(diǎn)對(duì)按照這種描述，參與協(xié)同多邊測量的節(jié)點(diǎn)形成一個(gè)子圖，對(duì)于每一條連接了一對(duì)參與節(jié)點(diǎn)的邊可以給出一個(gè)類似（7）的方程。為獲得一個(gè)唯一解，所考慮的所有節(jié)點(diǎn)必須是參與節(jié)點(diǎn)。在圖(b)中，有5條邊，可以列出5個(gè)方程。有時(shí)，對(duì)于n個(gè)變量我們可以列出n個(gè)方程，如圖(c)所示。然而，節(jié)點(diǎn)X有兩個(gè)可能的位置，解不唯一，因此X不是參與節(jié)點(diǎn)。如果以上條件滿足，非線性方程組可以使用像梯度下降法或模擬退火法等優(yōu)化方法來求解。不基于測距的定位算法基于測距的算法提高了傳感器節(jié)點(diǎn)的造價(jià)，消耗了有限的能量，而且在測量的準(zhǔn)確性方面需要大量的研究。對(duì)于一類非常廉價(jià)的、微小的低功率節(jié)點(diǎn)，需要輕量級(jí)的定位算法。不基于測距的算法只需要節(jié)點(diǎn)內(nèi)置的射頻單元，不需要知道待定位節(jié)點(diǎn)到參考節(jié)點(diǎn)的距離，或者不需要直接測量此距離，成本和功耗較低。質(zhì)心法（續(xù)）該算法簡單，計(jì)算量小。增大參考節(jié)點(diǎn)的重疊區(qū)域，即增大R/d（R為通信半徑，d為參考節(jié)點(diǎn)之間的距離），可以提高定精度。因此，該方法需要較多的參考節(jié)點(diǎn)。幾何約束法（續(xù)）該算法要求參考節(jié)點(diǎn)部署在網(wǎng)絡(luò)邊緣，否則節(jié)點(diǎn)的估算位置會(huì)向網(wǎng)絡(luò)中心偏移?；贒V的定位算法前面介紹的各種定位算法大都要求未知節(jié)點(diǎn)附近有參考節(jié)點(diǎn)，能直接接收到參考節(jié)點(diǎn)的信標(biāo)消息。但是考慮到通信沖突、功率消耗等問題，參考節(jié)點(diǎn)的發(fā)射功率不能太大。如何在參考節(jié)點(diǎn)比較稀疏的網(wǎng)絡(luò)中進(jìn)行節(jié)點(diǎn)定位？[8]提出利用網(wǎng)絡(luò)的逐跳傳播能力，各節(jié)點(diǎn)將其估計(jì)的到參考節(jié)點(diǎn)的距離傳播給其它節(jié)點(diǎn)，以解決較遠(yuǎn)的節(jié)點(diǎn)收聽不到參考節(jié)點(diǎn)的問題。比如，參考節(jié)點(diǎn)附近的節(jié)點(diǎn)可以通過直接測量的方法獲得到參考節(jié)點(diǎn)的距離，并傳播給其鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)據(jù)此可以估計(jì)自己到參考節(jié)點(diǎn)的距離，依次類推。類似于距離矢量路由算法中的距離傳播，因此稱這一類方法為基于DV的方法。DV-HOP傳播模式DV-HOP是一個(gè)最基本的方法，它采用經(jīng)典的距離矢量交換方法傳播到參考節(jié)點(diǎn)的距離。未知節(jié)點(diǎn)只使用第一次收到的平均每跳距離，而丟棄隨后到來的，從而保證未知節(jié)點(diǎn)只使用最近的參考節(jié)點(diǎn)發(fā)來的距離修正。DV-HOP的優(yōu)點(diǎn)是簡單，不依賴于測距誤差，缺點(diǎn)是必須工作于各向同性網(wǎng)絡(luò)，即各個(gè)方向上圖的特性是相同的，從而估計(jì)的每跳平均距離基本反映實(shí)際的情況。Euclidean傳播模式在圖中，A也可能與L位于BC的同側(cè)，這需要做出一個(gè)判斷。如果A有滿足以上條件的其它鄰居節(jié)點(diǎn)，可以根據(jù)其它條件進(jìn)行判斷。如果無法做出判斷，則不能計(jì)算AL。2.5安全定位目前大多數(shù)通用的定位算法主要關(guān)注定位精度與成本、功耗的關(guān)系，未考慮安全問題。由于傳感器網(wǎng)絡(luò)采用分布式計(jì)算且資源嚴(yán)重受限，很容易受到攻擊。一般的定位算法均假設(shè)監(jiān)聽到的參考節(jié)點(diǎn)位置及測量到的距離（角度）是正確的，最多有一些測量誤差。攻擊者很容易通過在網(wǎng)絡(luò)中散布虛假的參考節(jié)點(diǎn)位置，或者通過某些手段來誤導(dǎo)未知節(jié)點(diǎn)得到錯(cuò)誤的距離或角度信息，達(dá)到攻擊目的。文獻(xiàn)中介紹了許多針對(duì)節(jié)點(diǎn)定位的攻擊和防御策略。比如，針對(duì)基于RSSI測距的定位算法，可以通過改變發(fā)送功率或增加信道噪聲的方法改變測量距離；針對(duì)基于AoA的定位算法，可以使用反射物改變?nèi)肷浣牵会槍?duì)基于跳數(shù)測距的定位算法，可以通過制造蟲洞或阻塞某個(gè)方向的通信造成節(jié)點(diǎn)間跳數(shù)的減小或增大，等等。文獻(xiàn)中也介紹了不少針對(duì)這些攻擊手段的防御措施。比如，利用距離限制技術(shù)判定另一個(gè)節(jié)點(diǎn)是否在其觀測范圍內(nèi)；利用若干節(jié)點(diǎn)的地理位置或節(jié)點(diǎn)之間的數(shù)據(jù)包傳播時(shí)間來防止蟲洞攻擊，等等。多數(shù)安全策略需要額外的復(fù)雜設(shè)備，且大多針對(duì)一個(gè)或一類攻擊，不具有通用性。能否找到一種統(tǒng)一的方法來抵御所有這些針對(duì)節(jié)點(diǎn)定位的攻擊呢？從統(tǒng)計(jì)的角度看節(jié)點(diǎn)定位問題由于定位算法不外乎是利用參考位置、距離、角度等信息來進(jìn)行位置估計(jì)，以上種種攻擊手段只是實(shí)施方法不同而已，目的都是要欺騙未知節(jié)點(diǎn)得到錯(cuò)誤的參考位置、距離、角度等信息，使得位置估計(jì)發(fā)生很大的偏差。事實(shí)上，除了安全攻擊之后，節(jié)點(diǎn)出現(xiàn)異常、局部環(huán)境干擾等因素也會(huì)導(dǎo)致未知節(jié)點(diǎn)獲得錯(cuò)誤信息，影響位置估計(jì)的精度。從定位的角度來看，安全攻擊、節(jié)點(diǎn)異常、環(huán)境干擾沒有什么本質(zhì)的差別，它們都是提供了錯(cuò)誤的或者極不準(zhǔn)確的信息。事實(shí)上，正常節(jié)點(diǎn)產(chǎn)生的測量樣本也是有誤差的，只是誤差相對(duì)小一些。如果將錯(cuò)誤及誤差都看成噪聲的話，那么由安全攻擊、節(jié)點(diǎn)異常、環(huán)境干擾產(chǎn)生的測量樣本有很大的噪聲，而正常節(jié)點(diǎn)產(chǎn)生的測量樣本噪聲較小，但都是有噪聲的測量樣本。未知節(jié)點(diǎn)的任務(wù)就是要根據(jù)給定的一組有噪聲的測量樣本，進(jìn)行盡可能準(zhǔn)確的位置估計(jì)。按照這樣的描述，我們就可以用一些統(tǒng)計(jì)的方法來處理這個(gè)樣本集，基本思想就是設(shè)法去除噪聲大的樣本，僅利用噪聲小的樣本進(jìn)行位置估計(jì)。這樣我們就將應(yīng)對(duì)定位攻擊、節(jié)點(diǎn)異常和環(huán)境干擾的問題統(tǒng)一轉(zhuǎn)化為在測量樣本集中去除大噪聲樣本的問題，從而可以運(yùn)用各種統(tǒng)計(jì)學(xué)的方法來求解。目前有一些去除異常點(diǎn)的統(tǒng)計(jì)方法，有的復(fù)雜度較高，有的精度不夠。根據(jù)這個(gè)思想，我們提出了一個(gè)安全健壯的定位算法，稱為Bilateration。雙邊測量法Bilateration我們采用另一種方法求解方程組。每次只計(jì)算兩個(gè)方程，一般可以得到兩個(gè)實(shí)數(shù)解。這兩個(gè)實(shí)數(shù)解稱為候選位置，即未知節(jié)點(diǎn)可能的位置。如果選擇另外兩個(gè)參考節(jié)點(diǎn)進(jìn)行計(jì)算，可以得到另兩個(gè)候選位置。如果不存在攻擊和噪聲，這四個(gè)侯選位置中至少有兩個(gè)點(diǎn)是重疊的，這個(gè)重疊的點(diǎn)便是未知節(jié)點(diǎn)的位置。在實(shí)際環(huán)境中，由于噪聲的影響可能沒有重合點(diǎn)。但是我們有理由相信，如果誤差范圍有限的話，合理的位置應(yīng)相互靠近。雙邊測量法的基本思想就是找出合理的位置，并利用這些合理位置來進(jìn)行位置估計(jì)。δ及測距誤差對(duì)算法性能的影響在這個(gè)算法里，門限δ決定了對(duì)合理候選位置的定義，因而對(duì)算法性能影響較大。取值太小，算法需要較多次迭代搜索候選位置；取值太大，過濾能力就會(huì)下降。在不存在攻擊的環(huán)境中，合理候選位置的接近程度取決于測量誤差，可以根據(jù)測量誤差的方差決定。 影響算法性能的主要因素是測距誤差，如果測距誤差很大，則正常樣本和攻擊樣本的差別就會(huì)縮小，導(dǎo)致算法過濾能力下降，定位誤差增大。 我們還做了其它實(shí)驗(yàn)，測試了參考節(jié)點(diǎn)數(shù)量、惡意參考節(jié)點(diǎn)比例對(duì)算法性能的影響，分析了算法的計(jì)算復(fù)雜度和通信復(fù)雜度，并與另外三個(gè)統(tǒng)計(jì)學(xué)方法進(jìn)行了比較。模擬結(jié)果表明本算法在定位精度和計(jì)算復(fù)雜度方面有較好的平衡，噪聲適中和參考節(jié)點(diǎn)數(shù)目較小的環(huán)境中性能好于另外的算法。3.傳感器網(wǎng)絡(luò)中的射頻傳播模型由于部署大規(guī)模傳感器網(wǎng)絡(luò)的成本及困難，目前大多數(shù)研究工作都是在仿真環(huán)境中進(jìn)行的，包括算法性能評(píng)估。仿真就涉及到建模，選擇正確的模型成為研究工作的第一步，也是研究工作是否有意義的重要前提。為了分析上的方便，研究人員常使用一些理想的模型，如無線通信中的協(xié)議模型。但理想模型與實(shí)際問題是否相符一直受到質(zhì)疑。在傳感器網(wǎng)絡(luò)中受質(zhì)疑最多的是射頻信號(hào)傳播模型及感知模型。已有一些研究工作在研究傳感器網(wǎng)絡(luò)中的射頻信號(hào)模型，我們將介紹兩個(gè)這樣的工作。研究例子—洪泛源節(jié)點(diǎn)啟動(dòng)消息的發(fā)送；每個(gè)節(jié)點(diǎn)在收到第一個(gè)這樣的消息時(shí)，將消息的源節(jié)點(diǎn)設(shè)為自己的父節(jié)點(diǎn)，修改消息中的source域和hopcount域后，重新發(fā)送消息。該算法最終構(gòu)成一棵以消息源頭為根的樹，所有參與洪泛的節(jié)點(diǎn)都連接到這棵樹中。在一個(gè)理想的環(huán)境中，我們期望洪泛像水波一樣從源節(jié)點(diǎn)開始有序、均勻地向外擴(kuò)散，那么在真實(shí)的網(wǎng)絡(luò)中又是什么樣的呢？洪泛快照這是利用實(shí)驗(yàn)中收集的trace數(shù)據(jù)形成的洪泛快照，可以看到一個(gè)洪泛是如何逐跳傳播的。實(shí)驗(yàn)使用了160個(gè)節(jié)點(diǎn)，這些節(jié)點(diǎn)放置在地面上一個(gè)12*13的正方形網(wǎng)格中，洪泛從節(jié)點(diǎn)（5,0）開始。當(dāng)節(jié)點(diǎn)收到洪泛的消息時(shí)，立即轉(zhuǎn)發(fā)一次，并抑制隨后的重傳。有幾個(gè)值得注意的現(xiàn)象：洪泛并不像我們期望的那樣總是逐跳向外傳播，在某些區(qū)域洪泛朝著靠近源節(jié)點(diǎn)的方向延伸，比如圖(b)中的鏈路(6,3)—(6,2)，圖(c)中也有大量的后向鏈路。在有些情況下，數(shù)據(jù)包在相距很遠(yuǎn)（超出預(yù)期）的兩個(gè)節(jié)點(diǎn)間也能正常傳輸，如圖(a)中的(5,0)—(1,1)和(5,0)—(2,3)。某些節(jié)點(diǎn)未像期望的那樣參與到洪泛傳輸中，如圖(c)中的(3,4)。隨著時(shí)間的推進(jìn)，樹結(jié)構(gòu)呈現(xiàn)出一種高度群集的現(xiàn)象，即樹中的大部分節(jié)點(diǎn)只有很少的后代或沒有后代，而少量節(jié)點(diǎn)卻有許多孩子節(jié)點(diǎn)。以上這些現(xiàn)象均和我們預(yù)期的洪泛行為不符，表現(xiàn)出洪泛的不均勻性。為此，[9]定義了以下的洪泛測度，用于描述洪泛的不均勻性。洪泛的非均勻性測度 離群節(jié)點(diǎn)（straggler）：理論上應(yīng)當(dāng)收到洪泛消息，實(shí)際上卻并沒有參與洪泛傳輸?shù)墓?jié)點(diǎn)。 后向鏈路：洪泛消息的接收者比傳輸者更靠近源節(jié)點(diǎn)。 長鏈路：在給定的發(fā)送功率等級(jí)下，比預(yù)期長度長得多的鏈路。 聚類：在數(shù)據(jù)收集樹上，連接到單一節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量。 這個(gè)簡單的例子說明了真實(shí)環(huán)境中的洪泛是如何表現(xiàn)出復(fù)雜行為的。有許多因素影響洪泛的行為，這些因素可能位于協(xié)議棧的不同層次上。比如，長鏈路表明每個(gè)節(jié)點(diǎn)的通信范圍完全不是一個(gè)簡單的圓盤形狀，這是由物理鏈路的特性造成的（鏈路層面上的因素）；離群節(jié)點(diǎn)很可能是由于MAC層沖突產(chǎn)生的。[9]將影響洪泛行為的因素劃分到不同的層上進(jìn)行分析研究。實(shí)驗(yàn)平臺(tái)實(shí)驗(yàn)中使用的傳感器節(jié)點(diǎn)為RenoMote。為使每個(gè)節(jié)點(diǎn)的發(fā)射功率盡可能相同，在做每一個(gè)實(shí)驗(yàn)時(shí)，每個(gè)節(jié)點(diǎn)都是使用新的AA電池。而且，所有節(jié)點(diǎn)的天線均具有相同的長度和一致的垂直方向。需要指出的是，由于對(duì)Reno節(jié)點(diǎn)的射頻硬件進(jìn)行精確校準(zhǔn)的難度很大，即使所有節(jié)點(diǎn)的具有相同的標(biāo)稱硬件設(shè)置，不同節(jié)點(diǎn)的實(shí)際發(fā)射功率還是有差異的。節(jié)點(diǎn)上運(yùn)行的TinyOS系統(tǒng)提供了基本的運(yùn)行時(shí)支持，它包括一個(gè)完整的網(wǎng)絡(luò)協(xié)議棧，具有比特級(jí)前向糾錯(cuò)、16比特CRC檢錯(cuò)、媒體訪問控制、網(wǎng)絡(luò)消息傳輸層、非易失性存儲(chǔ)器和定時(shí)能力。所使用的MAC層協(xié)議是CSMA的一個(gè)變種：在每次傳輸前等待一個(gè)隨機(jī)時(shí)間，信道忙時(shí)進(jìn)入隨機(jī)回退，等待及回退的時(shí)間值均從[6ms,100ms]的固定間隔中隨機(jī)選取。為節(jié)省能耗，在回退階段射頻收發(fā)器是關(guān)閉的，因此這個(gè)時(shí)間段內(nèi)沒有通信發(fā)生。與一般的MAC協(xié)議不同，這里使用的MAC協(xié)議不設(shè)最大重傳次數(shù)，節(jié)點(diǎn)將不斷嘗試，直至消息發(fā)送成功。實(shí)驗(yàn)一：理解鏈路特性為理解洪泛行為，[2]設(shè)計(jì)了兩組實(shí)驗(yàn)。第一組實(shí)驗(yàn)重點(diǎn)理解大規(guī)模傳感器網(wǎng)絡(luò)測試床中節(jié)點(diǎn)間鏈路的特性，第二組實(shí)驗(yàn)重點(diǎn)研究在類似的測試床上洪泛的動(dòng)力學(xué)行為。實(shí)驗(yàn)一：將169個(gè)節(jié)點(diǎn)放置于一個(gè)平坦、開闊的停車場上，形成一個(gè)13*13的網(wǎng)格網(wǎng)絡(luò)，每個(gè)網(wǎng)格的邊長為2英尺。實(shí)驗(yàn)前對(duì)所有節(jié)點(diǎn)都進(jìn)行了診斷測試，以確保每個(gè)節(jié)點(diǎn)都工作正常。該實(shí)驗(yàn)的目的是繪制出在16個(gè)射頻功率設(shè)置下節(jié)點(diǎn)之間的連通特性。該實(shí)驗(yàn)由基站控制節(jié)點(diǎn)的發(fā)送，基站每次向一個(gè)節(jié)點(diǎn)發(fā)送命令，節(jié)點(diǎn)響應(yīng)基站的命令進(jìn)行發(fā)送，確保每次只有一個(gè)節(jié)點(diǎn)發(fā)送以避免沖突的發(fā)生。因此該實(shí)驗(yàn)隔離了MAC層及以上各層的影響，只研究鏈路層面上的影響因素。在每個(gè)功率設(shè)置下，每個(gè)節(jié)點(diǎn)每次發(fā)送20個(gè)包，所有數(shù)據(jù)包按照100ms的間隔依次發(fā)送。接收節(jié)點(diǎn)記錄發(fā)送節(jié)點(diǎn)的ID、包序號(hào)和發(fā)送功率（包含在包的載荷中），保存在自己的存儲(chǔ)器中。利用這些數(shù)據(jù)，繪制出每一個(gè)發(fā)送功率下數(shù)據(jù)包接收的統(tǒng)計(jì)圖。整個(gè)這一組實(shí)驗(yàn)持續(xù)4個(gè)小時(shí)。實(shí)驗(yàn)二：研究洪泛的行為這一組實(shí)驗(yàn)使用156個(gè)節(jié)點(diǎn)，場地與第一組實(shí)驗(yàn)同，形成13*12的網(wǎng)格網(wǎng)絡(luò)，每個(gè)網(wǎng)格的邊長為2英尺，無障礙物。基站放置于網(wǎng)格底邊的中點(diǎn)上。每個(gè)節(jié)點(diǎn)有一個(gè)全局唯一的ID。基站周期性地啟動(dòng)洪泛傳輸過程，該周期足夠長，以確保前一次洪泛已結(jié)束，每個(gè)節(jié)點(diǎn)只在第一次收到一個(gè)新的消息時(shí)轉(zhuǎn)發(fā)一次。實(shí)驗(yàn)中共設(shè)置了8個(gè)不同的射頻功率，在每一個(gè)射頻功率設(shè)置下啟動(dòng)10次不重疊的洪泛傳輸。應(yīng)用層和MAC層均記錄必要的信息，以便實(shí)驗(yàn)結(jié)束后重建消息的傳播過程。應(yīng)用層記錄所收到消息的發(fā)送節(jié)點(diǎn)ID（前一跳節(jié)點(diǎn)），這些信息可用于為消息傳播進(jìn)行排序，從而建立起消息傳播樹。在MAC層上，時(shí)間信息對(duì)于我們提取諸如回退時(shí)間、沖突等測度非常重要。為獲得時(shí)間信息，MAC層記錄兩個(gè)本地生成的時(shí)間戳（精度為16微秒）。第一個(gè)時(shí)間戳記錄消息被重傳之前在節(jié)點(diǎn)中存放的總時(shí)間，第二個(gè)時(shí)間戳記錄節(jié)點(diǎn)處于回退狀態(tài)的時(shí)間間隔。實(shí)驗(yàn)分析方法對(duì)射頻特性、有效通信距離、包接收行為、非對(duì)稱程度和MAC層行為的全面理解可以為類似大規(guī)模傳感器網(wǎng)絡(luò)中的算法設(shè)計(jì)提供指導(dǎo)。鏈路層分析評(píng)估鏈路層連通性的一個(gè)重要測度是包吞吐量。在本實(shí)驗(yàn)中，沒有通過CRC檢驗(yàn)的包被認(rèn)為是丟失了。圖示為某個(gè)發(fā)送功率下，來自某個(gè)中央節(jié)點(diǎn)的數(shù)據(jù)包接收概率的等值線，可以看到包接收率隨距離的分布非常不均勻。事實(shí)上，每一條等值線都清楚地顯示出方向性，即在某些方向上的傳輸情況好于其它方向。包接收率隨距離的分布曲線從這張圖也可以看到包接收率隨距離分布的不均衡性。盡管隨著距離的增大，包接收率迅速下降，但是曲線有一個(gè)很長的拖尾，即在長距離上存在一個(gè)非零的包接收概率。這指示長鏈路的存在，長鏈路導(dǎo)致在某些方向上傳輸情況好于其它方向。從這些曲線觀察到的另一個(gè)現(xiàn)象是，哪怕在一個(gè)很短的距離上，包吞吐率也低于100%。這是因?yàn)椋海?）節(jié)點(diǎn)部署在地面上引起信道衰落，（2）由于節(jié)點(diǎn)資源有限，信號(hào)處理及前向糾錯(cuò)能力不夠。非對(duì)稱鏈路非對(duì)稱鏈路在稀疏無線網(wǎng)絡(luò)（如典型的802.11LAN）中出現(xiàn)較少，通常在協(xié)議的層面上被過濾掉。然而，在由低功率無線節(jié)點(diǎn)組成的大規(guī)模傳感器網(wǎng)絡(luò)中，即使所有節(jié)點(diǎn)的發(fā)射功率都設(shè)為相同值，非對(duì)稱鏈路也非常普遍。圖示為雙向鏈路和非對(duì)稱鏈路隨距離的分布曲線，圖中給出了在每一個(gè)距離上，雙向鏈路及非對(duì)稱鏈路數(shù)量在所有鏈路中占的比例。從圖中可以看到，距發(fā)射節(jié)點(diǎn)距離較近時(shí)，非對(duì)稱鏈路的比例極小，可以忽略；但這個(gè)比例隨著距離的增大而明顯增大，尤其當(dāng)發(fā)射功率較低時(shí)。在全部的鏈路中，大約5-15%的鏈路為非對(duì)稱鏈路。垂直虛線表示按前面方法計(jì)算的連通半徑。在連通區(qū)域的邊界附近，節(jié)點(diǎn)在發(fā)射功率和接收靈敏度（硬件）上的細(xì)小差異變得非常重要，是非對(duì)稱鏈路產(chǎn)生的主要原因。（2）MAC層分析以上關(guān)系式有一個(gè)簡單的解釋：洪泛結(jié)束至少等到回退時(shí)間最長的節(jié)點(diǎn)重傳一個(gè)包，或最后一個(gè)節(jié)點(diǎn)接收到一個(gè)包；其最大值的情況是最后一個(gè)收到洪泛消息的節(jié)點(diǎn)選擇了最大回退時(shí)間。三個(gè)測度的實(shí)驗(yàn)數(shù)據(jù)表中給出了不同傳輸功率下這三個(gè)測度的檢測值。從表中可以看到，最大回退時(shí)間隨發(fā)射功率的增大而增大。接收延遲與結(jié)束時(shí)間的差異也隨發(fā)射功率的增大而增大。這兩個(gè)現(xiàn)象與沖突有關(guān)：在較高的發(fā)射功率下，每個(gè)節(jié)點(diǎn)具有較大的通信區(qū)域，從而沖突概率增大，最大回退時(shí)間也增大；而根據(jù)以上不等式，接收延遲與結(jié)束時(shí)間的差異也增大。沖突節(jié)點(diǎn)、離群節(jié)點(diǎn)和后向鏈路這兩張圖給出了沖突節(jié)點(diǎn)個(gè)數(shù)、離群節(jié)點(diǎn)個(gè)數(shù)和后向鏈路的關(guān)系，解釋了離群節(jié)點(diǎn)和后向鏈路產(chǎn)生的原因。在洪泛的起始階段沖突很頻繁，產(chǎn)生許多離群節(jié)點(diǎn)。這些離群節(jié)點(diǎn)錯(cuò)過了早期階段的洪泛，并因?yàn)殡S后的消息接收形成后向鏈路。在較高的發(fā)射功率下，每個(gè)節(jié)點(diǎn)具有較大的通信區(qū)域，沖突概率增大，從而產(chǎn)生較多的離群節(jié)點(diǎn)，最終形成較多的后向鏈路。測量沖突是很困難的，因?yàn)閿?shù)據(jù)包可能因?yàn)槌鲥e(cuò)而丟棄，而不是因?yàn)闆_突。為了區(qū)分沖突與其它丟包可能，論文采用了一種結(jié)合鏈路測度和MAC層測度的近似測量方法。特定發(fā)射功率下的連通半徑大致給出了通信區(qū)域的大小，利用該測度可以估計(jì)位于每個(gè)發(fā)射器通信范圍內(nèi)的節(jié)點(diǎn)個(gè)數(shù)，這些節(jié)點(diǎn)應(yīng)當(dāng)收到發(fā)射節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包。MAC層上的時(shí)間信息提供了發(fā)送時(shí)間重疊的節(jié)點(diǎn)，這些節(jié)點(diǎn)的傳輸可能產(chǎn)生沖突。利用這些測度可以估計(jì)出發(fā)生沖突的節(jié)點(diǎn)個(gè)數(shù)，即那些應(yīng)當(dāng)能夠收到數(shù)據(jù)包，但因位于沖突傳輸?shù)闹丿B區(qū)域內(nèi)而沒有收到數(shù)據(jù)包。（3）應(yīng)用層分析這里使用兩個(gè)測度來描述由洪泛構(gòu)造的樹的應(yīng)用層特性：節(jié)點(diǎn)層次和簇大小。節(jié)點(diǎn)層次定義為基站到樹上某個(gè)節(jié)點(diǎn)的跳數(shù)。圖中給出了節(jié)點(diǎn)層次的分布，可以看出其分布圍繞均值的波動(dòng)很大。有些物理上靠近基站的節(jié)點(diǎn)有較大的跳數(shù)，而一些離基站很遠(yuǎn)的節(jié)點(diǎn)跳數(shù)卻很少。這兩個(gè)現(xiàn)象都可以用鏈路層和MAC層上的觀察來解釋，前者由后向鏈路形成，而后者由長鏈路引起。應(yīng)用層分析（續(xù)）簇大小：連接到樹上某個(gè)特定父節(jié)點(diǎn)的孩子節(jié)點(diǎn)個(gè)數(shù)，與父節(jié)點(diǎn)的選擇算法有關(guān)。父節(jié)點(diǎn)的選擇：每個(gè)節(jié)點(diǎn)選擇第一個(gè)到來的洪泛消息的發(fā)射節(jié)點(diǎn)為父節(jié)點(diǎn)。圖中給出了某個(gè)發(fā)射功率下簇大小的柱狀圖分布（對(duì)數(shù)），可以看到在些簇特別大。這個(gè)現(xiàn)象可以用鏈路層和MAC層行為進(jìn)行解釋：長鏈路導(dǎo)致洪泛沿某個(gè)方向傳播較遠(yuǎn)，長鏈路端節(jié)點(diǎn)附近的信道很干凈，更重要的是周圍節(jié)點(diǎn)尚未收到洪泛消息。干凈的信道使得MAC層回退時(shí)間很短，相應(yīng)地沿著長鏈路的洪泛傳播更快；后者使得傳輸?shù)竭_(dá)大量未被覆蓋的節(jié)點(diǎn)。這兩個(gè)原因使得應(yīng)用層上觀察到高聚集現(xiàn)象。高聚集現(xiàn)象既有好處也有壞處。一方面，它意味著網(wǎng)絡(luò)中大多數(shù)節(jié)點(diǎn)離基站只有很少的跳數(shù)，在路由數(shù)據(jù)時(shí)可以節(jié)省能量；另一方面，這些長鏈路很有可能是非對(duì)稱鏈路，導(dǎo)致脆弱的數(shù)據(jù)收集樹?？偨Y(jié)（續(xù)）有些影響可以用現(xiàn)有的模型來描述，比如，使用高噪聲方差的射頻傳播模型可以產(chǎn)生非均勻的包接收等值線。但其它特性，如傳輸?shù)姆较蛐?，就無法用高斯噪聲模型來描述。在高代價(jià)、高功率系統(tǒng)中無關(guān)緊要的參數(shù)在廉價(jià)、低功率的系統(tǒng)中可能非常重要，比如射頻硬件、不同節(jié)點(diǎn)間的同步、能量差異等常常產(chǎn)生巨大的差異。這些參數(shù)在目前的模型中無法描述，其對(duì)協(xié)議行為的影響也沒有被仿真。論文研究表明，運(yùn)行于低功率的大規(guī)模傳感器網(wǎng)絡(luò)，細(xì)小的環(huán)境影響和對(duì)正常值的偏離，都可能對(duì)協(xié)議行為產(chǎn)生巨大的影響。因此，協(xié)議設(shè)計(jì)者應(yīng)當(dāng)記住，圓形模型或概率模型對(duì)于充分理解復(fù)雜系統(tǒng)的相互作用是不充分的。本文研究還表明，非對(duì)稱鏈路在大規(guī)模傳感器網(wǎng)絡(luò)中是很重要的，協(xié)議必須恰當(dāng)?shù)靥幚磉@種情況。RIM[10]根據(jù)大量的實(shí)驗(yàn)數(shù)據(jù)，提出了無線傳感器網(wǎng)絡(luò)中的射頻信號(hào)不規(guī)則模型。該模型描述了不同節(jié)點(diǎn)的硬件差異、電源差異，以及信號(hào)傳輸過程中的方向差異。第一部分表示不同節(jié)點(diǎn)的硬件校準(zhǔn)和電源狀況，SP為額定發(fā)送功率，VSP是不同節(jié)點(diǎn)發(fā)送功率差異的最大百分比，R是一個(gè)正態(tài)分布的變量，用于表示由硬件引起的差異。第二部分表示路徑損耗的各向異性，PL為自由空間的路徑損耗，Ki代表不同方向上的損耗因子。DOI定義為在方向上變化1度引起的最大差異，Rand是一個(gè)服從韋伯分布的隨機(jī)變量。第三部分表示環(huán)境噪聲，X為一個(gè)服從標(biāo)準(zhǔn)正態(tài)分布的變量。這項(xiàng)研究啟示我們，需要重新審視已有定位算法在實(shí)際網(wǎng)絡(luò)中的適用性。4.傳感器網(wǎng)絡(luò)中的數(shù)據(jù)管理 部署傳感器網(wǎng)絡(luò)的目的是采集環(huán)境數(shù)據(jù)，進(jìn)行適當(dāng)處理后傳輸給用戶，使用戶得到感興趣的信息，因此用戶感興趣的是傳感器網(wǎng)絡(luò)中的數(shù)據(jù)，而不是網(wǎng)絡(luò)本身。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，網(wǎng)絡(luò)中產(chǎn)生的數(shù)據(jù)量也非常龐大，這些數(shù)據(jù)分散在各個(gè)節(jié)點(diǎn)中，如何從分布在網(wǎng)絡(luò)各處的大量數(shù)據(jù)中提取有用的數(shù)據(jù)成為傳感器網(wǎng)絡(luò)需要解決的重要問題。在IP風(fēng)格的網(wǎng)絡(luò)通信模式中，節(jié)點(diǎn)以IP地址進(jìn)行標(biāo)識(shí)，訪問數(shù)據(jù)必須指出數(shù)據(jù)存放的位置（節(jié)點(diǎn)地址）。然而在傳感器網(wǎng)絡(luò)中，通過引用節(jié)點(diǎn)標(biāo)識(shí)來訪問數(shù)據(jù)一般是不可行的。這是因?yàn)椋?）用戶只對(duì)數(shù)據(jù)感興趣，并不關(guān)心到底是哪個(gè)節(jié)點(diǎn)采集了這個(gè)數(shù)據(jù)；2）在隨機(jī)部署的傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)標(biāo)識(shí)與物理位置的對(duì)應(yīng)關(guān)系在部署前并不知道，在部署后獲取全部節(jié)點(diǎn)的位置開銷很大，因此節(jié)點(diǎn)標(biāo)識(shí)對(duì)于數(shù)據(jù)訪問的用處不大。因此，傳感器網(wǎng)絡(luò)中的數(shù)據(jù)訪問需要采用不同的通信模式。4.1定向擴(kuò)散 目標(biāo)識(shí)別和定位不是本文討論的內(nèi)容。簡單地說，節(jié)點(diǎn)將檢測到的波形（如振動(dòng)）與本地保存的四足動(dòng)物的典型波形進(jìn)行匹配，以判斷是哪一種動(dòng)物。信號(hào)強(qiáng)度可以粗略表示目標(biāo)的距離，置信度表示波形匹配的程度。該區(qū)域的節(jié)點(diǎn)也可以協(xié)同進(jìn)行檢測、識(shí)別及定位，然后發(fā)送一個(gè)事件報(bào)告。（1）任務(wù)描述（興趣） 類型屬性區(qū)分不同的移動(dòng)對(duì)象，如汽車、動(dòng)物、人等，類型屬性的取值范圍為代表移動(dòng)對(duì)象的編碼集合。Interval屬性指出了事件數(shù)據(jù)的速率，Duration屬性指出任務(wù)持續(xù)的時(shí)間。為方便起見，子區(qū)域R用某個(gè)坐標(biāo)系中的矩形來表示。數(shù)據(jù)命名[12]選擇了一種簡單的基于<屬性，值>對(duì)的命名方案來命名興趣和數(shù)據(jù)。應(yīng)該還有其它的命名方案。從某種程度上說，命名方案的選擇影響任務(wù)的表述能力，并可能影響擴(kuò)散算法的性能。本文的重點(diǎn)在擴(kuò)散模式，在命名方案方面沒有做更深入的研究。（2）梯度 興趣通常由某個(gè)特定節(jié)點(diǎn)注入網(wǎng)絡(luò)，稱這個(gè)節(jié)點(diǎn)為sink。在我們考慮的任務(wù)例子中，任務(wù)在匯聚節(jié)點(diǎn)啟動(dòng)后，匯聚節(jié)點(diǎn)記錄該任務(wù)，并在duration屬性指定的時(shí)間（10分鐘）之后清除該任務(wù)的狀態(tài)。 對(duì)于每個(gè)活躍的任務(wù)，匯聚節(jié)點(diǎn)周期性地向其鄰居廣播一個(gè)興趣消息。在初始發(fā)送的興趣中，interval屬性的取值較大。該初始興趣可以看成是一個(gè)探測消息，它試圖確定網(wǎng)絡(luò)中是否有節(jié)點(diǎn)檢測到四足動(dòng)物，為此使用較低的數(shù)據(jù)速率，比如將interval設(shè)為1秒。 興趣由sink節(jié)點(diǎn)周期性地刷新，時(shí)間戳指示每個(gè)興趣的發(fā)送時(shí)間。刷新速率是一個(gè)協(xié)議設(shè)計(jì)參數(shù)，需要權(quán)衡興趣傳輸?shù)目煽啃约坝纱嗽斐傻拈_銷。興趣緩存 每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)興趣緩存，其中每一項(xiàng)對(duì)應(yīng)一個(gè)不同的興趣。兩個(gè)興趣認(rèn)為是不同的，如果它們的類型屬性不同、間隔屬性不同或范圍屬性不完全重疊。緩存的興趣項(xiàng)不包含sink節(jié)點(diǎn)的信息，某些情況下不同的興趣可以聚合，如兩個(gè)具有相同類型和完全重疊范圍的興趣，在緩存中可以只用一個(gè)興趣項(xiàng)表示。 當(dāng)節(jié)點(diǎn)收到一個(gè)興趣時(shí)，檢查緩存中是否有匹配的項(xiàng)。如果沒有匹配的項(xiàng)，創(chuàng)建一個(gè)興趣項(xiàng)，該興趣項(xiàng)有一個(gè)梯度域，指向傳播該興趣的鄰居節(jié)點(diǎn)。在我們的例子中，sink的鄰居節(jié)點(diǎn)將建立起一個(gè)興趣項(xiàng)，其梯度域指向sink，數(shù)據(jù)速率為每秒一個(gè)事件?？梢允褂萌魏文軌騾^(qū)分不同鄰居節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識(shí)方案，比如802.11MAC地址，藍(lán)牙的簇地址等。如果存在匹配的興趣項(xiàng)，但沒有指向興趣發(fā)送節(jié)點(diǎn)的梯度，在興趣項(xiàng)中添加一個(gè)梯度域，并更新timestamp和duration域。如果存在匹配的興趣項(xiàng)及梯度域，則只是更新timestamp和duration域。 當(dāng)一個(gè)梯度過期時(shí)，將其從興趣項(xiàng)中刪除；當(dāng)一個(gè)興趣項(xiàng)的所有梯度都過期時(shí)，將興趣項(xiàng)從緩存中刪除。不是所有的梯度都在相同的時(shí)間過期。比如，如果兩個(gè)不同的sink表示了相同的興趣，但具有不同的過期時(shí)間，則網(wǎng)絡(luò)中的有些節(jié)點(diǎn)就可能會(huì)有梯度過期時(shí)間不同的興趣項(xiàng)。興趣的擴(kuò)散收到一個(gè)興趣后，節(jié)點(diǎn)可以決定再將其發(fā)送給自己的一些鄰居。對(duì)它的鄰居來說，這個(gè)興趣看上去是從該節(jié)點(diǎn)發(fā)出的，盡管它可能來自很遠(yuǎn)的sink節(jié)點(diǎn)，這種方式稱為本地交互。按照這種方式，興趣被擴(kuò)散到網(wǎng)絡(luò)中。并不是收到的所有興趣都要重發(fā)，節(jié)點(diǎn)如果最近已經(jīng)重發(fā)過相匹配的興趣，它可以不發(fā)送收到的興趣。一般來說，有好幾種選擇鄰居的方法。最簡單的方法是轉(zhuǎn)發(fā)給所有的鄰居，這相當(dāng)于擴(kuò)散。當(dāng)不知道哪些節(jié)點(diǎn)可能滿足興趣時(shí)，這是唯一的選擇。在本文所舉的例子中，第二種可能的方法是使用地理路由。它可以限制興趣擴(kuò)散的拓?fù)浞秶瑥亩?jié)省能量。在一個(gè)節(jié)點(diǎn)不移動(dòng)的網(wǎng)絡(luò)中，第三種方法是使用緩存的數(shù)據(jù)。比如，在響應(yīng)一個(gè)較早的興趣時(shí)，節(jié)點(diǎn)從A收聽到從子區(qū)域R的傳感器節(jié)點(diǎn)發(fā)來的數(shù)據(jù)，它可以將興趣發(fā)送給A，而不是向所有鄰居廣播。（3）數(shù)據(jù)生成和傳播 指定區(qū)域內(nèi)的傳感器節(jié)點(diǎn)使用相同的方法處理興趣，除此之外，指令節(jié)點(diǎn)的傳感器開始采集數(shù)據(jù)。[12]沒有詳細(xì)討論目標(biāo)識(shí)別算法，簡單地說，每個(gè)節(jié)點(diǎn)預(yù)先存儲(chǔ)了所要識(shí)別的目標(biāo)的聲音或振動(dòng)波形，節(jié)點(diǎn)將檢測到的波形與這些波形進(jìn)行比對(duì)，找出最匹配的波形。波形匹配的程度可能不同，算法通常會(huì)用一個(gè)置信度來表示匹配的程度。采樣到的信號(hào)強(qiáng)度粗略指示出信號(hào)源的距離。 檢測到目標(biāo)的傳感器節(jié)點(diǎn)從其興趣緩存中尋找匹配的興趣項(xiàng)，興趣項(xiàng)匹配是指興趣項(xiàng)的rect域指示的區(qū)域包括節(jié)點(diǎn)位置，同時(shí)type域匹配檢測到的目標(biāo)類型。當(dāng)節(jié)點(diǎn)發(fā)現(xiàn)一個(gè)匹配的興趣項(xiàng)時(shí)，計(jì)算所有梯度中的最高事件速率，然后令其傳感器子系統(tǒng)按照最高數(shù)據(jù)速率生成事件樣本，單播發(fā)送給每個(gè)梯度指示的鄰居。在本文的例子中，起始數(shù)據(jù)速率為每秒一個(gè)事件，節(jié)點(diǎn)每秒鐘向每個(gè)梯度指示的鄰居節(jié)點(diǎn)發(fā)送一個(gè)事件描述。數(shù)據(jù)傳播 接收到數(shù)據(jù)消息的節(jié)點(diǎn)從其興趣緩存中尋找匹配的興趣項(xiàng)。如果沒有找到匹配的興趣項(xiàng)，丟棄數(shù)據(jù)消息。如果找到一個(gè)匹配的興趣項(xiàng)，檢查與其關(guān)聯(lián)的數(shù)據(jù)緩存。數(shù)據(jù)緩存保存了最近收到的數(shù)據(jù)條目，如果接收到的數(shù)據(jù)消息在緩存中有一個(gè)相匹配的緩存項(xiàng)，數(shù)據(jù)消息被丟棄；否則將數(shù)據(jù)消息添加到數(shù)據(jù)緩存中，并發(fā)送給鄰居節(jié)點(diǎn)。通過檢查數(shù)據(jù)緩存，節(jié)點(diǎn)可以確定接收事件的數(shù)據(jù)速率（通過timestamp域）。 為轉(zhuǎn)發(fā)收到的數(shù)據(jù)消息，節(jié)點(diǎn)檢查興趣項(xiàng)的梯度列表。如果所有梯度的數(shù)據(jù)速率大于等于接收到的事件速率，節(jié)點(diǎn)只是將收到的數(shù)據(jù)消息發(fā)送給適當(dāng)?shù)泥従?。如果某些梯度的?shù)據(jù)速率小于收到的事件速率，節(jié)點(diǎn)需要降頻。比如，節(jié)點(diǎn)收到的事件速率為每秒100個(gè)事件，而某個(gè)梯度的的數(shù)據(jù)速率為每秒50個(gè)事件，則節(jié)點(diǎn)每收到兩個(gè)事件后只發(fā)送一個(gè)，比如發(fā)送置信度較高的那個(gè)事件。 （4）路徑鞏固 Sink節(jié)點(diǎn)起始時(shí)擴(kuò)散的是對(duì)低速率事件的興趣。一旦傳感器節(jié)點(diǎn)檢測到匹配的目標(biāo)，它們就發(fā)送低速率事件，事件消息可能沿著多條路徑向sink發(fā)送。Sink收到這些事件消息后，通過鞏固某個(gè)鄰居來接收高質(zhì)量（高速率）事件。 路徑鞏固是利用數(shù)據(jù)驅(qū)動(dòng)的本地規(guī)則來實(shí)現(xiàn)的。比如，從某個(gè)鄰居收到一個(gè)之前未見過的新事件，則鞏固該鄰居。為鞏固該鄰居，sink向其重新發(fā)送一個(gè)興趣，但該興趣具有較小的interval值。 當(dāng)鄰居節(jié)點(diǎn)接收到這個(gè)興趣時(shí)，它注意到該興趣項(xiàng)中已經(jīng)有了一個(gè)指向該節(jié)點(diǎn)的梯度，且當(dāng)前收到的興趣指定了較高的數(shù)據(jù)速率。如果這個(gè)新的數(shù)據(jù)速率高于任何存在的梯度，它必須鞏固至少一個(gè)鄰居。 它選擇哪個(gè)（些）鄰居鞏固呢？節(jié)點(diǎn)可以使用數(shù)據(jù)緩存和數(shù)據(jù)驅(qū)動(dòng)的本地規(guī)則來確定，比如，它可以選擇第一個(gè)發(fā)來最新匹配事件的鄰居節(jié)點(diǎn)進(jìn)行鞏固，也可以對(duì)發(fā)來最新匹配事件的所有鄰居進(jìn)行鞏固，或者對(duì)發(fā)來最多事件的鄰居節(jié)點(diǎn)進(jìn)行鞏固，或者對(duì)一向較早發(fā)送事件的鄰居節(jié)點(diǎn)進(jìn)行鞏固。后面兩種規(guī)則可以提高路徑的穩(wěn)定性，但比較復(fù)雜。通過這一系列的本地交互，就建立起一條從源節(jié)點(diǎn)到sink節(jié)點(diǎn)的高數(shù)據(jù)速率傳輸路徑。 取消鞏固 以上算法可能會(huì)導(dǎo)致多條路徑被鞏固。比如，sink先鞏固了某個(gè)鄰居A，然后從鄰居B收到了一個(gè)新的事件，于是又鞏固通過B的路徑。如果經(jīng)過B的路徑一直比較好，我們需要一個(gè)機(jī)制來取消對(duì)通過A的路徑的鞏固。 一種方法是利用超時(shí)機(jī)制，所有高事件速率的梯度必須被顯式地鞏固，否則在規(guī)定的時(shí)間后被取消鞏固。為此，sink必須周期性地鞏固B，并停止鞏固A，這樣通過A的路徑最終被降級(jí)到低事件速率。另一種方法是通過發(fā)送低數(shù)據(jù)速率的興趣來顯式地降級(jí)通過A的路徑。當(dāng)A收到這樣的興趣后，會(huì)降級(jí)指向sink的梯度。如果所有梯度均為低數(shù)據(jù)速率，A取消鞏固那些向其發(fā)送高速率事件的鄰居。這一系列的本地交互確保通過A的路徑迅速降級(jí)。節(jié)點(diǎn)如何選擇取消鞏固的鄰居節(jié)點(diǎn)？一種方法是選擇那些沒有新事件到來的鄰居節(jié)點(diǎn)，即在一個(gè)給定的時(shí)間窗口T內(nèi)，其它鄰居總是先于它發(fā)送。另一種方法是選擇那些較少發(fā)送新事件的鄰居節(jié)點(diǎn)。4.2數(shù)據(jù)存儲(chǔ)與訪問 前面介紹的例子讓我們了解了傳感器網(wǎng)絡(luò)的數(shù)據(jù)訪問模式，下面我們更深入地介紹傳感器網(wǎng)絡(luò)的數(shù)據(jù)存儲(chǔ)與訪問技術(shù)。 傳感器網(wǎng)絡(luò)中的數(shù)據(jù)存儲(chǔ)研究節(jié)點(diǎn)產(chǎn)生的數(shù)據(jù)在網(wǎng)絡(luò)中的存儲(chǔ)策略，包括如何將數(shù)據(jù)存放到網(wǎng)絡(luò)中合適的位置，以及查詢請(qǐng)求如何路由到存儲(chǔ)位置。實(shí)際上這是一個(gè)信息中介過程，所謂信息中介是指生產(chǎn)者（傳感器節(jié)點(diǎn)）將產(chǎn)生（采集）的數(shù)據(jù)按照某種策略存放在特定的位置上，而消費(fèi)者（匯聚節(jié)點(diǎn)或傳感器節(jié)點(diǎn)）將數(shù)據(jù)訪問請(qǐng)求按照相應(yīng)的策略路由到相關(guān)數(shù)據(jù)的存儲(chǔ)位置，然后滿足查詢條件的結(jié)果反饋給消費(fèi)者。 當(dāng)一個(gè)節(jié)點(diǎn)產(chǎn)生了數(shù)據(jù)后，數(shù)據(jù)的存放位置有三種選擇：存儲(chǔ)在網(wǎng)絡(luò)外部，存儲(chǔ)在本節(jié)點(diǎn)，存儲(chǔ)在網(wǎng)絡(luò)中的其它節(jié)點(diǎn)上。相應(yīng)地，數(shù)據(jù)存儲(chǔ)策略分為集中式存儲(chǔ)、本地存儲(chǔ)和分布式存儲(chǔ)三種。4.3分布式數(shù)據(jù)存儲(chǔ)與訪問分布式存儲(chǔ)需要有效的信息中介機(jī)制協(xié)調(diào)數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)訪問之間的關(guān)系，目前使用的機(jī)制有哈希映射、建立索引、數(shù)據(jù)和查詢請(qǐng)求按一定規(guī)則路由等。（1）GHT 考慮到傳感器網(wǎng)絡(luò)中用戶感興趣的是數(shù)據(jù)，而不是采集或存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)，[14]提出了以數(shù)據(jù)為中心的存儲(chǔ)（data-centricstorage，DCS）。家鄉(xiāng)節(jié)點(diǎn)和家鄉(xiāng)周界 在移動(dòng)自組網(wǎng)中，節(jié)點(diǎn)用一個(gè)地理位置無關(guān)的地址進(jìn)行標(biāo)識(shí)，發(fā)送節(jié)點(diǎn)首先要利用位置服務(wù)將目的節(jié)點(diǎn)的地址映射到節(jié)點(diǎn)的當(dāng)前位置，然后使用GPSR進(jìn)行路由。在GHT中，調(diào)用put()和get()的節(jié)點(diǎn)并不知道最終要存儲(chǔ)數(shù)據(jù)的節(jié)點(diǎn)標(biāo)識(shí)，它只是對(duì)關(guān)鍵字k進(jìn)行散列，得到一個(gè)地理坐標(biāo)。哈希函數(shù)并不知道每個(gè)節(jié)點(diǎn)的放置位置，它只是將關(guān)鍵字名字均勻地分布到網(wǎng)絡(luò)所部署的地理區(qū)域中，因此很有可能在哈希函數(shù)得到的位置上并沒有節(jié)點(diǎn)存在。 定義GHT分組的家鄉(xiāng)節(jié)點(diǎn)為在地理位置上最接近分組目的坐標(biāo)的節(jié)點(diǎn)，攜帶或查詢<k,v>值對(duì)的GHT分組最終到達(dá)其家鄉(xiāng)節(jié)點(diǎn)。 由于GHT分組只是尋址到一個(gè)特定的位置而不是一個(gè)節(jié)點(diǎn)，因此沒有一個(gè)接收者會(huì)在分組中看到自己的節(jié)點(diǎn)標(biāo)識(shí)。GHT使用GPSR周邊模式來找到家鄉(xiāng)節(jié)點(diǎn)。 當(dāng)網(wǎng)絡(luò)拓?fù)洳蛔儠r(shí)，以上機(jī)制可以工作得很好。然而，當(dāng)發(fā)生節(jié)點(diǎn)失效、部署新節(jié)點(diǎn)或節(jié)點(diǎn)移動(dòng)時(shí)，網(wǎng)絡(luò)拓?fù)浒l(fā)生改變，目的位置的家鄉(xiāng)節(jié)點(diǎn)和家鄉(xiāng)周界可能發(fā)生變化。在網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化的情況下，保證家鄉(xiāng)節(jié)點(diǎn)的一致性非常關(guān)鍵。周界刷新協(xié)議PRP GHT使用周界刷新協(xié)議復(fù)制<k,v>對(duì)并將它們放置在一致的節(jié)點(diǎn)上?？紤]到GHT沿著家鄉(xiāng)周界路由分組，PRP將<k,v>對(duì)保存在家鄉(xiāng)周界的每一個(gè)節(jié)點(diǎn)上。 PRP區(qū)分家鄉(xiāng)節(jié)點(diǎn)和家鄉(xiāng)周界上的其它節(jié)點(diǎn)（稱為復(fù)制節(jié)點(diǎn)），一個(gè)節(jié)點(diǎn)成為關(guān)鍵字k的家鄉(xiāng)節(jié)點(diǎn)，如果put()分組圍繞家鄉(xiāng)周界一圈后又到達(dá)該節(jié)點(diǎn)。 PRP周期性地產(chǎn)生刷新分組。每隔Th秒，家鄉(xiāng)節(jié)點(diǎn)對(duì)其保存的關(guān)鍵字k生成刷新分組，發(fā)送到k的哈希位置上，刷新分組中包含以關(guān)鍵字k存儲(chǔ)的值。刷新分組就像put()和get()分組一樣被路由，因此刷新分組將圍繞目的位置當(dāng)前的家鄉(xiāng)周界轉(zhuǎn)一圈。拓?fù)涓淖兒蟾录亦l(xiāng)節(jié)點(diǎn) 當(dāng)刷新分組到達(dá)一個(gè)節(jié)點(diǎn)時(shí)有兩種可能：（1）接收節(jié)點(diǎn)比啟動(dòng)節(jié)點(diǎn)更靠近目的位置：接收節(jié)點(diǎn)使用該刷新分組，并啟動(dòng)自己的刷新過程。（2）接收節(jié)點(diǎn)不比啟動(dòng)節(jié)點(diǎn)更靠近目的位置：繼續(xù)使用周界模式轉(zhuǎn)發(fā)刷新分組。以上兩種情況下，接收節(jié)點(diǎn)都會(huì)將本節(jié)點(diǎn)存儲(chǔ)的、刷新分組中沒有的<k,v>對(duì)添加到刷新分組中。當(dāng)刷新分組返回啟動(dòng)節(jié)點(diǎn)、且該節(jié)點(diǎn)并不是原來的家鄉(xiāng)節(jié)點(diǎn)時(shí)，該節(jié)點(diǎn)使用刷新分組，并成為該關(guān)鍵字的家鄉(xiāng)節(jié)點(diǎn)。也就是說，這個(gè)新的家鄉(xiāng)節(jié)點(diǎn)設(shè)置自己的刷新定時(shí)器，并周期性啟動(dòng)刷新。這個(gè)機(jī)制保證在拓?fù)浒l(fā)生變化后，最靠近k的哈希位置的節(jié)點(diǎn)成為k的家鄉(xiāng)節(jié)點(diǎn)，并存儲(chǔ)k的數(shù)據(jù)。家鄉(xiāng)節(jié)點(diǎn)失效每當(dāng)復(fù)制節(jié)點(diǎn)收到一個(gè)不是自己啟動(dòng)的刷新分組時(shí)，它緩存刷新分組中的數(shù)據(jù)，并設(shè)置一個(gè)接管定時(shí)器。當(dāng)定時(shí)器超時(shí)時(shí)，復(fù)制節(jié)點(diǎn)啟動(dòng)一次刷新，將刷新分組發(fā)往k的哈希位置。復(fù)制節(jié)點(diǎn)和接管定時(shí)器用于解決家鄉(xiāng)節(jié)點(diǎn)失效的問題，當(dāng)家鄉(xiāng)節(jié)點(diǎn)失效時(shí)，其復(fù)制節(jié)點(diǎn)將發(fā)現(xiàn)刷新分組的缺失，并啟動(dòng)刷新過程。復(fù)制節(jié)點(diǎn)也許不會(huì)成為家鄉(xiāng)節(jié)點(diǎn)，但GHT的路由過程會(huì)使得刷新分組到達(dá)新的家鄉(xiāng)節(jié)點(diǎn)。圖例 圖中給出了PRP操作的例子，K哈希到位置L。在對(duì)<k,v>進(jìn)行put()操作后，節(jié)點(diǎn)a成為家鄉(xiāng)節(jié)點(diǎn)，并發(fā)送一個(gè)到L的刷新分組。圖4為刷新分組返回到節(jié)點(diǎn)a之后，圍繞L的家鄉(xiāng)周界。 假設(shè)節(jié)點(diǎn)a失效，在d的接管定時(shí)器超時(shí)后，d發(fā)送一個(gè)到L的刷新分組，如圖5所示。該刷新分組傳輸?shù)焦?jié)點(diǎn)f，f成為<k,v>的家鄉(xiāng)節(jié)點(diǎn)。圖6為f發(fā)送的刷新分組返回f時(shí)，圍繞L的家鄉(xiāng)周界。PRP產(chǎn)生的網(wǎng)絡(luò)流量一般很小，尤其在密集部署的傳感器網(wǎng)絡(luò)中，圍繞一個(gè)位置的家鄉(xiāng)周界很短（多數(shù)只有三個(gè)節(jié)點(diǎn)）。PRP還有一個(gè)加入優(yōu)化，用以提高動(dòng)態(tài)拓?fù)湎碌男阅?。?dāng)節(jié)點(diǎn)A感知到一個(gè)新鄰居B時(shí)，A會(huì)將其本地?cái)?shù)據(jù)庫中的以下數(shù)據(jù)項(xiàng)發(fā)送給B：B離這些數(shù)據(jù)項(xiàng)的目的位置比A更近，且A比其鄰居更靠近這些位置。這個(gè)優(yōu)化可以在節(jié)點(diǎn)失效或移動(dòng)時(shí)，加快家鄉(xiāng)節(jié)點(diǎn)的建立。（2）DIMENSIONS [15]考慮一類長期觀測的科學(xué)應(yīng)用，傳感器網(wǎng)絡(luò)要進(jìn)行長時(shí)間的工作來獲取之前未觀察過的現(xiàn)象，如微氣候、棲息地、動(dòng)物遷徙規(guī)律等，將數(shù)據(jù)交給相關(guān)領(lǐng)域的專家進(jìn)行仔細(xì)分析。這一類應(yīng)用通常產(chǎn)生大量的數(shù)據(jù)，數(shù)據(jù)分析涉及非常復(fù)雜的信號(hào)處理，不是由傳感器節(jié)點(diǎn)能夠完成的。將所有數(shù)據(jù)傳輸?shù)交緯?huì)消耗大量的能量，縮短網(wǎng)絡(luò)的使用壽命。將原始數(shù)據(jù)全部保存在本地，則節(jié)點(diǎn)的存儲(chǔ)空間不夠，表中列出了三種應(yīng)用產(chǎn)生的數(shù)據(jù)量及期望的運(yùn)行時(shí)間。龐大的數(shù)據(jù)量及有限的節(jié)點(diǎn)存儲(chǔ)空間要求必須進(jìn)行存儲(chǔ)優(yōu)化。DIMENSIONS的基本思想 前面介紹的定向擴(kuò)散和DCS適合對(duì)已知事件的監(jiān)視，這些事件的特性已知（如動(dòng)物的聲音），檢測到的事件存放在網(wǎng)絡(luò)中的指定位置，查詢和相關(guān)的處理也都是預(yù)先定義好的。然而[15]考慮的一類應(yīng)用不滿足這個(gè)條件，比如確定建筑物中一個(gè)不正常的振動(dòng)事件需要對(duì)以往事件的統(tǒng)計(jì)。對(duì)于這類應(yīng)用，更有效的方法是將數(shù)據(jù)存儲(chǔ)在網(wǎng)絡(luò)中并進(jìn)行適當(dāng)?shù)念A(yù)處理，以方便多種查詢。[15]的基本思想是利用數(shù)據(jù)壓縮和索引技術(shù)，提供多分辨率的數(shù)據(jù)存儲(chǔ)與訪問。節(jié)點(diǎn)對(duì)傳感器數(shù)據(jù)生成不同分辨率的摘要，存放在網(wǎng)絡(luò)中一個(gè)為高效查詢而優(yōu)化的分布式存儲(chǔ)結(jié)構(gòu)上。DIMENSIONS的組成 數(shù)據(jù)摘要和數(shù)據(jù)老化是周期性處理的，處理周期與具體應(yīng)用有關(guān)。比如，如果微氣候監(jiān)視網(wǎng)絡(luò)的用戶希望每個(gè)月底查詢數(shù)據(jù)，則這個(gè)周期可以是一個(gè)月。事實(shí)上，每個(gè)周期必須足夠長，以便有足夠多的原始數(shù)據(jù)進(jìn)行摘要處理。多分辨率數(shù)據(jù)摘要圖中解釋了DIMENSIONS搜索樹的構(gòu)造。每個(gè)父節(jié)點(diǎn)利用其4個(gè)子節(jié)點(diǎn)在某個(gè)周期內(nèi)較細(xì)粒度的時(shí)空摘要形成該周期內(nèi)較粗粒度的時(shí)空摘要。因此，從樹根到樹葉，數(shù)據(jù)摘要的精度逐漸下降。較高層上的數(shù)據(jù)摘要包括更大的空間尺度，但壓縮率和失真度更大，在最高層上一個(gè)或少數(shù)幾個(gè)節(jié)點(diǎn)具有對(duì)網(wǎng)絡(luò)中所有數(shù)據(jù)計(jì)算的摘要。下鉆查詢 在分布式小波摘要上進(jìn)行下鉆查詢可以極大地減小搜索的代價(jià)。下鉆這個(gè)術(shù)語來自于數(shù)據(jù)挖掘領(lǐng)域，下鉆查詢使用一個(gè)較粗粒度的摘要來指示下一步應(yīng)查詢哪一個(gè)更細(xì)粒度的摘要，通過將搜索限制在一個(gè)較小的范圍，可以極大地減小處理開銷。數(shù)據(jù)管理 節(jié)點(diǎn)的存儲(chǔ)空間是有限的，當(dāng)有新的數(shù)據(jù)到來時(shí)，就要選擇一些老的數(shù)據(jù)丟棄。為兼顧歷史數(shù)據(jù)和新數(shù)據(jù)，以及數(shù)據(jù)存儲(chǔ)的時(shí)間長度和精度，一種較好的做法是提供一個(gè)使數(shù)據(jù)精度隨時(shí)間逐漸降低的數(shù)據(jù)老化方法。較近的數(shù)據(jù)提供較高的精度，從而使用較多的內(nèi)存；而較老的數(shù)據(jù)提供較低的精度，消耗較少的內(nèi)存。 每一層上的數(shù)據(jù)摘要都代表了一個(gè)空間區(qū)域在某個(gè)周期的視圖，存儲(chǔ)管理要考慮到存儲(chǔ)空間在不同新、老程度的數(shù)據(jù)之間的分配。數(shù)據(jù)老化問題可以描述為一個(gè)約束優(yōu)化問題，[15]使用一個(gè)離線的算法來確定系統(tǒng)參數(shù)，包括分配給不同層次數(shù)據(jù)摘要的存儲(chǔ)空間比例、每個(gè)節(jié)點(diǎn)上存儲(chǔ)的數(shù)據(jù)摘要層數(shù)、分配給每一層數(shù)據(jù)摘要的存儲(chǔ)空間等。 分布式四叉樹DQT 分布式四叉樹用來將不同層次的數(shù)據(jù)摘要分配給網(wǎng)絡(luò)中的節(jié)點(diǎn)，構(gòu)成DIMENSIONS搜索樹。DQT將網(wǎng)絡(luò)空間進(jìn)行遞歸劃分，每一次劃分都將一個(gè)空間分為四個(gè)象限，并采用DHT的方法給每個(gè)象限指定一個(gè)存儲(chǔ)代理。DQT按照以下方法構(gòu)造：給定一個(gè)矩形區(qū)域R和一個(gè)全局可知的常數(shù)c，使用哈希函數(shù)h(R,c)將c散列成R中的一個(gè)位置（x,y），最靠近（x,y）的節(jié)點(diǎn)選為R的存儲(chǔ)代理，該節(jié)點(diǎn)即為樹根。當(dāng)使用R作為h的輸入時(shí)，得到這個(gè)節(jié)點(diǎn)。將每個(gè)父節(jié)點(diǎn)的矩形空間劃分成四等分，使用每個(gè)象限的矩形作為h的輸入，可以得到每個(gè)象限的存儲(chǔ)代理，它們即為父節(jié)點(diǎn)的四個(gè)孩子。這個(gè)過程遞歸進(jìn)行，直至達(dá)到預(yù)定的樹高。使用位置哈希來選擇各個(gè)區(qū)域的存儲(chǔ)代理，可消除簇頭選舉和全局協(xié)同的開銷。（3）Comb-Needle 這是數(shù)據(jù)和查詢按一定規(guī)則路由的例子。[16]考慮一個(gè)戰(zhàn)場感知的應(yīng)用例子，戰(zhàn)場上部署的傳感器網(wǎng)絡(luò)幫助士兵在能見度較低的情況下（如夜晚、霧天）感知戰(zhàn)場態(tài)勢。比如圖中，某個(gè)士兵可能感興趣敵人坦克在什么地方。 預(yù)期到士兵的需要，檢測到坦克的傳感器節(jié)點(diǎn)可以周期性地將信息推送（廣播）到網(wǎng)絡(luò)中，如圖所示?；谕频男畔鞑ゲ呗?當(dāng)網(wǎng)絡(luò)中有許多士兵一直需要這個(gè)信息時(shí)，基于推的信息傳播策略很有效。但是當(dāng)信息需求很低時(shí)，這種策略導(dǎo)致很高的通信開銷，許多帶寬被浪費(fèi)。系統(tǒng)可以選擇另一種策略?；诶男畔鞑ゲ呗?士兵需要信息時(shí)廣播一個(gè)查詢請(qǐng)求，滿足查詢條件的節(jié)點(diǎn)發(fā)送數(shù)據(jù)。在查詢頻率較低時(shí)，這個(gè)策略比較高效。 那么一個(gè)自然的想法是，我們能否結(jié)合這兩種策略的優(yōu)點(diǎn)，建立一個(gè)能夠適應(yīng)查詢和事件頻率的查詢支持機(jī)制呢？Comb-Needle查詢支持模型[16]提出了一種稱為comb-needle的查詢支持模型，它吸收了推和拉兩種數(shù)據(jù)傳播策略的優(yōu)點(diǎn)。每個(gè)傳感器節(jié)點(diǎn)將數(shù)據(jù)推送到自己的一個(gè)鄰域，形成針狀的復(fù)制結(jié)構(gòu)（在經(jīng)過的每個(gè)節(jié)點(diǎn)上保留副本），查詢過程則動(dòng)態(tài)地建立一個(gè)梳子狀的路由結(jié)構(gòu)（先沿垂直方向傳播，然后沿著水平方向具有一定間隔的多條路徑同時(shí)傳播），這個(gè)過程就像梳子尋找沙子或草堆里的針一樣。這個(gè)過程也可以相反，即數(shù)據(jù)先沿著垂直方向傳播，然后沿著水平方向具有一定間隔的多條路徑同時(shí)傳播，并在經(jīng)過的路徑上保留副本，而查詢請(qǐng)求只需沿著垂直方向傳播，便能夠和存儲(chǔ)路徑相交。這取決于數(shù)據(jù)產(chǎn)生速率和查詢發(fā)生速率。論文分析了算法的通信代價(jià)、查詢覆蓋、可靠性等問題。 有一種稱為cross-line的數(shù)據(jù)存儲(chǔ)與訪問策略也是采用類似的方法。生產(chǎn)者將產(chǎn)生的數(shù)據(jù)沿著水平方向傳播，并在經(jīng)過的路徑上保留數(shù)據(jù)副本；消費(fèi)者發(fā)布的查詢請(qǐng)求沿著垂直方向傳播，消費(fèi)者在兩條路徑相交的節(jié)點(diǎn)獲得所需的數(shù)據(jù)。5.傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合 部署傳感器網(wǎng)絡(luò)的目的是為了監(jiān)視環(huán)境，每個(gè)傳感器節(jié)點(diǎn)都有一個(gè)或多個(gè)感知物理環(huán)境的傳感器，每個(gè)傳感器都是一個(gè)獨(dú)立的數(shù)據(jù)源，產(chǎn)生由傳感器ID、位置、傳感器類型、時(shí)間戳和數(shù)據(jù)等若干域組成的數(shù)據(jù)記錄。由不同節(jié)點(diǎn)的同一種傳感器產(chǎn)生的數(shù)據(jù)記錄具有相同的schema，所有這些數(shù)據(jù)記錄形成一個(gè)分布式表。因此，可將傳感器網(wǎng)絡(luò)看成是由多個(gè)傳感器表組成的一個(gè)分布式數(shù)據(jù)庫系統(tǒng)。 傳感器產(chǎn)生的數(shù)據(jù)是有噪聲的，即其讀數(shù)相對(duì)于真值來說是有偏差的（由硬件差異引起）。其次，觀察同一物理現(xiàn)象的幾個(gè)傳感器，由于位置不同產(chǎn)生的數(shù)據(jù)也可能不同，比如放置于空調(diào)送風(fēng)口的溫度傳感器的讀數(shù)高于其它位置的傳感器。因此，單個(gè)傳感器的測量值不是很可靠，原始數(shù)據(jù)的聚合結(jié)果（aggregation）會(huì)比單個(gè)測量數(shù)據(jù)更有用，因?yàn)檫@個(gè)結(jié)果更穩(wěn)定，也更能反映該區(qū)域的統(tǒng)計(jì)特性，實(shí)際上用戶感興趣的也是這個(gè)結(jié)果。 那么由誰來進(jìn)行聚合運(yùn)算呢？最簡單的方法是將原始數(shù)據(jù)全部發(fā)送到基站進(jìn)行聚合計(jì)算，這種方法能量消耗很大。利用傳感器節(jié)點(diǎn)的計(jì)算能力，可以將部分計(jì)算推到網(wǎng)絡(luò)中進(jìn)行，由傳感器節(jié)點(diǎn)過濾不相關(guān)的記錄，執(zhí)行聚合計(jì)算，然后將結(jié)果返回給基站。有人對(duì)傳感器節(jié)點(diǎn)各功能模塊的耗能進(jìn)行了測試，發(fā)現(xiàn)通信消耗的能量要遠(yuǎn)遠(yuǎn)高于計(jì)算消耗的能量，因此在網(wǎng)絡(luò)內(nèi)進(jìn)行計(jì)算可以大大節(jié)省能量。這表明，在網(wǎng)絡(luò)內(nèi)進(jìn)行聚合計(jì)算非常必要。分布式查詢處理架構(gòu) [17]認(rèn)為斷言式查詢是最適合傳感器網(wǎng)絡(luò)的，即用戶和應(yīng)用程序發(fā)布查詢時(shí)，并不需要知道數(shù)據(jù)在網(wǎng)絡(luò)中是如何產(chǎn)生的，又是如何處理來得到查詢結(jié)果的。用戶不需要知道如何與相關(guān)傳感器節(jié)點(diǎn)接觸、處理數(shù)據(jù)和得到結(jié)果的細(xì)節(jié)。為了實(shí)現(xiàn)這種查詢，[17]提出一個(gè)松耦合的分布式架構(gòu)來支持聚合運(yùn)算和更復(fù)雜的網(wǎng)絡(luò)內(nèi)計(jì)算。其想法是在網(wǎng)絡(luò)層和應(yīng)用層之間引入一個(gè)查詢層，查詢層由運(yùn)行于每個(gè)節(jié)點(diǎn)上的查詢代理組成。一個(gè)例子 下面用一個(gè)簡單的例子解釋該架構(gòu)中的每個(gè)組件。頭節(jié)點(diǎn)可能是網(wǎng)絡(luò)中一個(gè)具有較多剩余資源的固定節(jié)點(diǎn)，也可以是由某種分布式頭節(jié)點(diǎn)選舉算法選出來的節(jié)點(diǎn)。計(jì)算計(jì)劃左圖為參與查詢的非頭節(jié)點(diǎn)的查詢計(jì)劃。非頭節(jié)點(diǎn)用scan操作周期性地從本地傳感器讀溫度值，然后發(fā)送給頭節(jié)點(diǎn)。它們的計(jì)劃還包含一個(gè)聚合操作，用于聚合其它傳感器來的數(shù)據(jù)（這些數(shù)據(jù)需要通過它路由到頭節(jié)點(diǎn)）。 右圖為頭節(jié)點(diǎn)的查詢計(jì)劃。包含一個(gè)平均操作，用于計(jì)算在最近一輪查詢中收到的傳感器測量值的平均；還有一個(gè)選擇操作，用于檢查計(jì)算結(jié)果是否超過門限。 網(wǎng)絡(luò)內(nèi)查詢處理的研究問題 從這個(gè)例子可以看到，實(shí)現(xiàn)網(wǎng)絡(luò)內(nèi)查詢處理需要解決以下問題。聚合是指將數(shù)據(jù)從分散的源節(jié)點(diǎn)傳遞到一個(gè)執(zhí)行計(jì)算的中心節(jié)點(diǎn)。這是傳感器網(wǎng)絡(luò)中最常見的計(jì)算和通信模式，剛才介紹的查詢Q即是一個(gè)聚合查詢。 聚合涉及兩個(gè)重要問題：1）從計(jì)算的角度說，聚合必須在一個(gè)頭節(jié)點(diǎn)上完成，除非最終的聚合計(jì)算由基站或網(wǎng)絡(luò)外完成，因此需要確定一個(gè)頭節(jié)點(diǎn)；2）數(shù)據(jù)記錄必須從源節(jié)點(diǎn)傳輸?shù)街付ǖ念^節(jié)點(diǎn)。 如果計(jì)算指定由頭節(jié)點(diǎn)完成，這個(gè)頭節(jié)點(diǎn)需要從傳感器節(jié)點(diǎn)中選舉出來。頭節(jié)點(diǎn)選擇策略有幾個(gè)基本要求：頭節(jié)點(diǎn)應(yīng)當(dāng)是動(dòng)態(tài)可維護(hù)的（應(yīng)對(duì)節(jié)點(diǎn)或鏈路失效），目前已經(jīng)有許多文獻(xiàn)提出了各種頭節(jié)點(diǎn)選擇算法。（這個(gè)要求是從可靠性角度出發(fā)的）頭節(jié)點(diǎn)應(yīng)具有有利的物理位置，應(yīng)使得整個(gè)查詢的通信開銷（源節(jié)點(diǎn)到頭節(jié)點(diǎn)、頭節(jié)點(diǎn)到基站）最小。（這個(gè)要求是從性能的角度出發(fā)） 第二個(gè)問題，如何將數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)筋^節(jié)點(diǎn)？顯然需要建立合適的通信結(jié)構(gòu)來傳輸這些數(shù)據(jù)。從前面的例子可以看到，一個(gè)聚合查詢的查詢計(jì)劃從功能上可以劃分成兩個(gè)組件：通信組件和計(jì)算組件。通信組件用于將數(shù)據(jù)從源節(jié)點(diǎn)傳輸?shù)筋^節(jié)點(diǎn)，計(jì)算組件執(zhí)行聚合計(jì)算。有三種方法來集成計(jì)算組件和通信組件：1）最簡單的方法是將所有數(shù)據(jù)記錄沿著多跳路由直接發(fā)送到頭節(jié)點(diǎn)，對(duì)于小規(guī)模網(wǎng)絡(luò)而言這是一種合理的方法，但對(duì)于大范圍的聚合查詢計(jì)算會(huì)產(chǎn)生大量的消息，消耗很多能量。2）在無線網(wǎng)絡(luò)中，考慮到信道獲取和包頭開銷，發(fā)送多個(gè)小分組比發(fā)送一個(gè)大分組代價(jià)高。由于一個(gè)數(shù)據(jù)記錄通常較小，較小區(qū)域內(nèi)的許多節(jié)點(diǎn)可能同時(shí)發(fā)送分組來響應(yīng)查詢，為此可以將幾個(gè)數(shù)據(jù)記錄合并到一個(gè)較大的分組中，這樣每組記錄只需承擔(dān)一個(gè)分組的開銷。3）部分聚合。對(duì)于可增量計(jì)算的聚合操作，如平均、最大、最小等，可將部分計(jì)算從頭節(jié)點(diǎn)推到中間節(jié)點(diǎn)完成。每個(gè)中間節(jié)點(diǎn)計(jì)算部分結(jié)果，頭節(jié)點(diǎn)從這些部分結(jié)果中計(jì)算出最終結(jié)果。這些中間結(jié)果的記錄規(guī)模通常與原始數(shù)據(jù)的記錄規(guī)模一樣，因此這種方法可以減少需要傳輸?shù)臄?shù)據(jù)量。第2、第3兩種方法需要協(xié)調(diào)通信路徑上傳感器節(jié)點(diǎn)之間的傳輸（同步），因?yàn)橐粋€(gè)節(jié)點(diǎn)必須從其它節(jié)點(diǎn)收集數(shù)據(jù)或中間結(jié)果。為此，每個(gè)節(jié)點(diǎn)必須知道哪些節(jié)點(diǎn)會(huì)通過它路由數(shù)據(jù)記錄，以及它需要等待多長時(shí)間收集數(shù)據(jù)。（1）確定哪些節(jié)點(diǎn)通過它路由：實(shí)際上是要確定從源節(jié)點(diǎn)到頭節(jié)點(diǎn)的通信結(jié)構(gòu)，這與聚合操作的類型有關(guān)。對(duì)于復(fù)制敏感的聚合操作，如SUM和AVG，使用部分聚合的前提條件是每個(gè)數(shù)據(jù)記錄只允許發(fā)送一次，這時(shí)使用以頭節(jié)點(diǎn)為根的生成樹是比較合適的。如果不是復(fù)制敏感的聚合操作，如求最小值、最大值等，以可以使用以頭節(jié)點(diǎn)為根的有向無環(huán)圖，允許使用多條路徑傳輸。確定了通信結(jié)構(gòu)后，每個(gè)節(jié)點(diǎn)記錄需要經(jīng)過它路由的節(jié)點(diǎn)。（2）等待多長時(shí)間：每個(gè)節(jié)點(diǎn)需要知道從其子節(jié)點(diǎn)收集數(shù)據(jù)需要多長時(shí)間，但這個(gè)時(shí)間很難估計(jì)。這是因?yàn)椴煌?jié)點(diǎn)在處理數(shù)據(jù)、調(diào)度數(shù)據(jù)包、獲取信道、重傳數(shù)據(jù)包等方面存在很大的差異，其次因鏈路失效而重路由也會(huì)造成通信結(jié)構(gòu)的拓?fù)涓淖?。這個(gè)時(shí)間對(duì)于聚合查詢的性能影響很大，時(shí)間短了數(shù)據(jù)收集不充分，時(shí)間大了造成查詢延遲太大。網(wǎng)絡(luò)內(nèi)查詢處理的研究問題（續(xù)） （1）傳感器網(wǎng)絡(luò)可能被部署在不同的環(huán)境中，被不同的應(yīng)用使用。通過使用不同類型的傳感器，很容易擴(kuò)展傳感器網(wǎng)絡(luò)的功能支持更多的應(yīng)用。有些應(yīng)用已經(jīng)提出較長時(shí)間，也已實(shí)現(xiàn)了原型系統(tǒng)，如物理環(huán)境監(jiān)視、移動(dòng)目標(biāo)跟蹤等；有些應(yīng)用剛剛出現(xiàn)，如生物和地質(zhì)領(lǐng)域的應(yīng)用；還有些應(yīng)用將來會(huì)出現(xiàn)。因此，查詢語言設(shè)計(jì)面臨的困難是，有些查詢類型我們已經(jīng)知道是非常有用的（如聚合查詢），任何查詢語言都應(yīng)該支持它們，其它一些方面還不太清楚，隨著時(shí)間的推移和新應(yīng)用的出現(xiàn)，我們才能知道哪些功能是需要的。（從應(yīng)用需求的角度來設(shè)計(jì)通用的查詢語言）。另一種方法是觀察傳感器數(shù)據(jù)本身的特性，然后抽象出對(duì)這些數(shù)據(jù)類型可能的計(jì)算模式。（從數(shù)據(jù)的角度） （2）網(wǎng)絡(luò)內(nèi)查詢處理可以減少能量消耗，從而延長網(wǎng)絡(luò)壽命。一個(gè)復(fù)雜的查詢可能包含大量的參數(shù)和操作，以及用戶對(duì)查詢結(jié)果的各種要求（最大允許的延遲、查詢精度等）。這樣的復(fù)雜查詢通常有很多可能的查詢執(zhí)行計(jì)劃，查詢優(yōu)化器的任務(wù)就是從中選擇一個(gè)好的查詢計(jì)劃。一個(gè)好的計(jì)劃可能是消耗能量最少的，或是在給定資源限制下能夠最好滿足各種要求的。由于傳感器網(wǎng)絡(luò)的高度動(dòng)態(tài)性，查詢計(jì)劃需要反映網(wǎng)絡(luò)拓?fù)?、?jié)點(diǎn)能量水平等的變化。 （3）為了生成一個(gè)好的計(jì)劃，查詢優(yōu)化器需要一些網(wǎng)絡(luò)元數(shù)據(jù)來評(píng)估不同查詢計(jì)劃的代價(jià)和收益（延遲和精度）。為此，需要在服務(wù)器上建立和維護(hù)一個(gè)目錄，保存重要的信息，如傳感器位置、密度和連通度、當(dāng)前系統(tǒng)工作負(fù)載、網(wǎng)絡(luò)穩(wěn)定度等。系統(tǒng)生成的查詢計(jì)劃可以用來周期性地更新目錄，或者從網(wǎng)絡(luò)中收集信息來動(dòng)態(tài)地更新目錄。由于元數(shù)據(jù)的規(guī)模及網(wǎng)絡(luò)的動(dòng)態(tài)性，要集中式地收集和實(shí)時(shí)維護(hù)全部的元數(shù)據(jù)是不可能的。需要定義有效的綱要數(shù)據(jù)結(jié)構(gòu)，使得創(chuàng)建和維護(hù)的開銷既小，同時(shí)又包含足夠的信息用于查詢優(yōu)化。 （4）多查詢優(yōu)化是另一個(gè)挑戰(zhàn)性的問題。傳感器網(wǎng)絡(luò)被許多用戶共享，網(wǎng)絡(luò)中有多個(gè)基站連接到不同的用戶。多個(gè)查詢通過不同的基站節(jié)點(diǎn)流入網(wǎng)絡(luò)，有可能許多用戶發(fā)布類似的查詢，這些查詢可以共享中間結(jié)果。 下面我們只重點(diǎn)介紹數(shù)據(jù)聚合的研究問題。能量有效的數(shù)據(jù)聚合算法數(shù)據(jù)聚合的目的是以能量有效的方式收集數(shù)據(jù)、消除冗余傳輸以及提供融合信息給基站同，以延長網(wǎng)絡(luò)壽命。稱一個(gè)數(shù)據(jù)聚合方案是能量有效的，如果它能夠最大化網(wǎng)絡(luò)效能（功能？functionality）。如果假定所有傳感器節(jié)點(diǎn)都是同等重要的，這意味著應(yīng)當(dāng)最小化每個(gè)節(jié)點(diǎn)的能量消耗，通常用網(wǎng)絡(luò)壽命來量化算法的能量有效性。衡量數(shù)據(jù)聚合算法的重要性能指標(biāo)包括：網(wǎng)絡(luò)壽命：從網(wǎng)絡(luò)開始運(yùn)行至比例為α的傳感器節(jié)點(diǎn)死亡時(shí)，所允許的數(shù)據(jù)聚合回合數(shù)，其中α為系統(tǒng)設(shè)計(jì)者指定的一個(gè)值。若某個(gè)應(yīng)用要求所有節(jié)點(diǎn)必須同時(shí)工作，則網(wǎng)絡(luò)壽命定義為從網(wǎng)絡(luò)開始運(yùn)行至第一個(gè)傳感器節(jié)點(diǎn)耗盡能量時(shí)，所允許的數(shù)據(jù)聚合回合數(shù)。因此，數(shù)據(jù)聚合應(yīng)當(dāng)使得網(wǎng)絡(luò)中的能量消耗是均勻的。數(shù)據(jù)精度：數(shù)據(jù)精度取決于傳感器網(wǎng)絡(luò)所要實(shí)現(xiàn)的應(yīng)用。對(duì)于目標(biāo)定位來說，數(shù)據(jù)精度就是基站得到的目標(biāo)位置精度。延遲：從數(shù)據(jù)包在網(wǎng)絡(luò)中產(chǎn)生至基站收到該數(shù)據(jù)包所用的時(shí)間，包括數(shù)據(jù)包傳輸、路由和聚合所花費(fèi)的所有時(shí)間。設(shè)計(jì)能量有效的數(shù)據(jù)聚合算法是一個(gè)困難的問題，在這方面已經(jīng)進(jìn)行了大量的研究工作，下面介紹其中的一些工作。網(wǎng)絡(luò)架構(gòu)與數(shù)據(jù)聚合協(xié)議 傳感器網(wǎng)絡(luò)的結(jié)構(gòu)對(duì)于數(shù)據(jù)聚合協(xié)議的性能有重要影響。傳感器網(wǎng)絡(luò)的結(jié)構(gòu)有平面結(jié)構(gòu)和層次結(jié)構(gòu)兩大類。在平面結(jié)構(gòu)的網(wǎng)絡(luò)中，數(shù)據(jù)聚合依靠以數(shù)據(jù)為中心的路由實(shí)現(xiàn)（如定向擴(kuò)散），基站將查詢消息發(fā)送到傳感器節(jié)點(diǎn)，符合條件的節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)?；蛘卟樵?cè)诰W(wǎng)絡(luò)中洪泛（拉模式），或者數(shù)據(jù)在網(wǎng)絡(luò)中洪泛（推模式），或者兩種模式結(jié)合。平面結(jié)構(gòu)的網(wǎng)絡(luò)可能使基站承擔(dān)過多的通信和計(jì)算負(fù)擔(dān)，消耗鄰近節(jié)點(diǎn)的能量（漏斗效應(yīng)）。在層次結(jié)構(gòu)的網(wǎng)絡(luò)中，數(shù)據(jù)聚合涉及在特殊節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合，從而減少向基站發(fā)送的數(shù)據(jù)量，提高網(wǎng)絡(luò)的能量有效性。下面介紹幾個(gè)應(yīng)用于不同分層結(jié)構(gòu)的傳感器網(wǎng)絡(luò)中的數(shù)據(jù)聚合協(xié)議。5.1基于簇的數(shù)據(jù)聚合--LEACH 節(jié)點(diǎn)組織成簇，簇內(nèi)節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給本地簇頭，簇頭對(duì)本簇?cái)?shù)據(jù)進(jìn)行聚合后，將結(jié)果發(fā)送給基站。LEACH是最早提出的一個(gè)能量有效的簇形成協(xié)議。 LEACH對(duì)于節(jié)點(diǎn)和網(wǎng)絡(luò)有以下兩個(gè)假設(shè)：節(jié)點(diǎn)：節(jié)點(diǎn)是同構(gòu)的，（需要的話）所有節(jié)點(diǎn)都能夠直接與基站通信。即每個(gè)節(jié)點(diǎn)通過調(diào)節(jié)發(fā)送功率都可以直接與基站通信，也都能夠執(zhí)行信號(hào)處理功能，都有能力履行簇頭的職責(zé)。網(wǎng)絡(luò)：節(jié)點(diǎn)總是有數(shù)據(jù)要發(fā)送給基站，相互鄰近的節(jié)點(diǎn)采集的數(shù)據(jù)是相關(guān)的。在LEACH中，節(jié)點(diǎn)被組織成簇，有一個(gè)節(jié)點(diǎn)擔(dān)當(dāng)簇頭。簇內(nèi)節(jié)點(diǎn)將數(shù)據(jù)發(fā)送給本地簇頭，簇頭對(duì)本簇內(nèi)節(jié)點(diǎn)采集的數(shù)據(jù)進(jìn)行聚合計(jì)算，將結(jié)果直接發(fā)送給基站。因此，簇頭消耗的能量比普通節(jié)點(diǎn)多得多。為避免擔(dān)當(dāng)簇頭的節(jié)點(diǎn)消耗能量過快，LEACH采用隨機(jī)輪換簇頭的方法，將承擔(dān)簇頭的責(zé)任均勻分布到網(wǎng)絡(luò)中。為此，LEACH的運(yùn)行劃分為一系列回合。每一個(gè)回合開始于一個(gè)建立階段，在這個(gè)階段建立簇；然后是穩(wěn)定階段，在這個(gè)階段傳輸數(shù)據(jù)（普通節(jié)點(diǎn)-簇頭-基站）。 簇頭選舉 簇頭選舉算法有兩個(gè)目標(biāo)：1）每個(gè)回合選出k個(gè)簇頭；2）每個(gè)節(jié)點(diǎn)成為簇頭的機(jī)會(huì)均等。 在第(r+1)個(gè)回合（從時(shí)間t開始），節(jié)點(diǎn)i以概率Pi(t)選舉自己成為簇頭，Pi(t)應(yīng)使得該輪選出的簇頭節(jié)點(diǎn)個(gè)數(shù)的期望值為k（公式2）。 為保證每個(gè)節(jié)點(diǎn)成為簇頭的次數(shù)相同，要求每個(gè)節(jié)點(diǎn)在N/k個(gè)回合中平均成為簇頭一次。用Ci(t)表示節(jié)點(diǎn)i在最近（rmod(N/k)）次回合中當(dāng)過簇頭的指示函數(shù)（Ci(t)=0表示當(dāng)過簇頭），則每個(gè)節(jié)點(diǎn)在第（r+1）個(gè)回合選舉自己為簇頭的概率如公式3所示。因此，只有那些最近沒有成為簇頭的節(jié)點(diǎn)可能會(huì)在第（r+1）個(gè)回合成為簇頭。 公式4：等式左邊是第(r+1)個(gè)回合有資格成為簇頭的節(jié)點(diǎn)的總數(shù)。 利用公式3和公式4可以推得公式2。 節(jié)點(diǎn)i生成一個(gè)0~1之間的隨機(jī)數(shù)，與Pi(t)進(jìn)行比較，若大于Pi(t)，則選舉自己成為簇頭。基于剩余能量的簇頭選舉 以上公式假設(shè)所有節(jié)點(diǎn)起始時(shí)具有相同的能量，并且所有節(jié)點(diǎn)都有數(shù)據(jù)發(fā)送。如果節(jié)點(diǎn)具有不同的能量（或者使用事件驅(qū)動(dòng)模型），則具有較多剩余能量的節(jié)點(diǎn)應(yīng)比剩余能量較少的節(jié)點(diǎn)有更多的機(jī)會(huì)成為簇頭。為此，可用公式6計(jì)算節(jié)點(diǎn)選舉自己成為簇頭的概率，其中Ei(t)為節(jié)點(diǎn)i的當(dāng)前能量。 為使用公式6，需要知道網(wǎng)絡(luò)中所有節(jié)點(diǎn)的剩余能量之和，節(jié)點(diǎn)可用本簇中節(jié)點(diǎn)的平均剩余能量乘以N來估計(jì)。簇形成算法 節(jié)點(diǎn)選舉自己成為簇頭后，使用非堅(jiān)持CSMA協(xié)議廣播一個(gè)廣告消息ADV，該消息包含簇頭節(jié)點(diǎn)的ID。非簇頭節(jié)點(diǎn)可能會(huì)收到多個(gè)ADV消息，它選擇RSS最大的節(jié)點(diǎn)作為自己的簇頭節(jié)點(diǎn)。如果采用無線信號(hào)的理想傳播模型，這意味著選擇距離最近（從而通信耗能最少）的節(jié)點(diǎn)作為簇頭。 在確定了自己所屬的簇后，非簇頭節(jié)點(diǎn)使用非堅(jiān)持CSMA發(fā)送一個(gè)加入消息，消息中包含節(jié)點(diǎn)自己的ID及簇頭ID。 簇頭負(fù)責(zé)協(xié)調(diào)本簇內(nèi)的傳輸。為此，簇頭在本簇內(nèi)建立一個(gè)TDMA調(diào)度，發(fā)送給本簇內(nèi)所有節(jié)點(diǎn)，至此建立階段完成，穩(wěn)定階段開始。穩(wěn)定階段 穩(wěn)定階段的運(yùn)行劃分為一系列的幀，每個(gè)節(jié)點(diǎn)在每一幀分配給自己的時(shí)間片里最多向簇頭發(fā)送數(shù)據(jù)一次。每個(gè)時(shí)間片的長度是固定的，因此一幀的時(shí)間長度取決于簇中節(jié)點(diǎn)的個(gè)數(shù)。 簇頭接收完所有的數(shù)據(jù)后，執(zhí)行聚合計(jì)算，將結(jié)果發(fā)送給基站。 為減少簇間通信干擾，LEACH使用擴(kuò)頻通信。每個(gè)簇內(nèi)部使用一種擴(kuò)頻碼，簇頭與基站通信時(shí)使用基站的擴(kuò)頻碼，因此簇頭與基站通信前先要監(jiān)聽信道。5.2基于鏈的數(shù)據(jù)聚合--PERASIS 該方法試圖從以下方面節(jié)省能量：節(jié)點(diǎn)只與鄰近節(jié)點(diǎn)通信：發(fā)送功率隨通信距離的增大而成指數(shù)增大每個(gè)回合只指定一個(gè)頭節(jié)點(diǎn)與基站通信：在LEACH中每個(gè)簇頭都直接與基站通信每個(gè)節(jié)點(diǎn)輪流成為頭節(jié)點(diǎn)：使網(wǎng)絡(luò)中的能量消耗均勻。 鏈可以由基站集中式地計(jì)算，然后通知各節(jié)點(diǎn)；也可以由各節(jié)點(diǎn)利用全局位置信息計(jì)算。由于每個(gè)節(jié)點(diǎn)都知道全局位置信息，且采用相同的算法計(jì)算，因此每個(gè)節(jié)點(diǎn)計(jì)算出來的鏈?zhǔn)且粯拥摹．?dāng)某個(gè)節(jié)點(diǎn)死亡時(shí)，鏈需要重新計(jì)算。數(shù)據(jù)收集 在構(gòu)造這個(gè)鏈的過程中，有些節(jié)點(diǎn)在鏈上可能會(huì)有相對(duì)較遠(yuǎn)的鄰居。與其它節(jié)點(diǎn)相比，這些節(jié)點(diǎn)在每一輪數(shù)據(jù)收集中會(huì)消耗較多的能量，PEGASIS不允許這些節(jié)點(diǎn)成為頭節(jié)點(diǎn)。為此，設(shè)定一個(gè)門限，當(dāng)與鄰居節(jié)點(diǎn)的距離超過該門限時(shí)，這些節(jié)點(diǎn)不能成為頭節(jié)點(diǎn)。也可以設(shè)定一個(gè)剩余能量門限，當(dāng)節(jié)點(diǎn)的剩余能量低于該門限時(shí)，不能成為頭節(jié)點(diǎn)。當(dāng)由于節(jié)點(diǎn)死亡重新構(gòu)造鏈時(shí)，這個(gè)門限可以改變。基于鏈的分層方案 以上算法的能量消耗比較小，每次只有一個(gè)節(jié)點(diǎn)發(fā)送，沒有沖突，也沒有其它信號(hào)干擾，但數(shù)據(jù)收集時(shí)間較長。為此，[19]設(shè)計(jì)了兩個(gè)基于鏈的分層方案來提高數(shù)據(jù)收集速度，允許多對(duì)節(jié)點(diǎn)同時(shí)傳輸。為了減少因干擾或沖突造成過多的能量消耗（在有干擾的情況下，節(jié)點(diǎn)需要增