【正文】 分析第一章提到的無線傳。為提高定位系統(tǒng)的適應(yīng)能力，提出了基于測距與不測距的混合定位方法，此方法可以在保證節(jié)點(diǎn)定位精度的前提下，根據(jù)需要?jiǎng)討B(tài)的調(diào)整定位算法。而基于不測距(Rangefree)的定位機(jī)制則是在無需測量節(jié)點(diǎn)間的絕對距離或方位的情況下能夠提供一般精度要求的位置估計(jì)，該技術(shù)降低了對節(jié)點(diǎn)硬件的要求，在成本方面比基于測距技術(shù)的定位機(jī)制具有優(yōu)勢。二次定位的一個(gè)限定條件是在發(fā)動(dòng)第二次定位之前，必須要有足夠的時(shí)間延遲，以確保處于基于測距定位邊緣的節(jié)點(diǎn)(注：與基于不測距的定位節(jié)點(diǎn)相鄰的節(jié)點(diǎn))位置已經(jīng)確定，否則，基于不測距定位過基于復(fù)合定位的無線傳感器網(wǎng)絡(luò)層次路由協(xié)議設(shè)計(jì)與實(shí)現(xiàn)32程將會(huì)因?yàn)檎也坏藉^節(jié)點(diǎn)而失敗。節(jié)點(diǎn)首先啟動(dòng)延時(shí)觸發(fā)器，在第一個(gè)觸發(fā)時(shí)間到來時(shí)，所有節(jié)點(diǎn)啟動(dòng)基于測距的定位程序，此時(shí)節(jié)點(diǎn)保持對基站測距信號(hào)的偵聽狀態(tài)，如果收到基站測距信標(biāo)則啟動(dòng)基于測距的定位程序。3．2．2．3 兩種定位算法的融合控制 混合定位法的一個(gè)關(guān)鍵問題是如何確定哪些節(jié)點(diǎn)是通過測距法來定位，哪些節(jié)點(diǎn)又是通過不測距的方法定位，如果控制不當(dāng)，網(wǎng)絡(luò)節(jié)點(diǎn)不能選擇合適的定位方法，會(huì)造成節(jié)點(diǎn)定位和組網(wǎng)失敗?；趶?fù)合定位的無線傳感器網(wǎng)絡(luò)層次路由協(xié)議設(shè)計(jì)與實(shí)現(xiàn)302)平均每跳的距離是這樣得到的：假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)在布置時(shí)是服從一樣的分布密度，因此在基于測距定位過程中得到的平均每跳距離同樣也適合于這些位置還未確定的節(jié)點(diǎn)，此距離參數(shù)可由基站根據(jù)已定位節(jié)點(diǎn)位置計(jì)算得到。以此類推，在 D 與 E 的位置確定之后，可繼續(xù)對 D、E 外圍節(jié)點(diǎn)進(jìn)行定位。如圖 33 所示，在圖中處于陰影區(qū)域的節(jié)點(diǎn)(F、G、H)是已經(jīng)通過測距定位過程獲ABCDEFGH洪泛消息應(yīng)答消息圖 33　基于不測距定位示意圖知自身位置的節(jié)點(diǎn)，在陰影區(qū)域外的節(jié)點(diǎn) A、B、C、D、E 是需進(jìn)行不測距定位的節(jié)點(diǎn)。經(jīng)過一段時(shí)間的信標(biāo)轉(zhuǎn)發(fā)過程，所有與邊緣區(qū)域相鄰的錨節(jié)點(diǎn)均會(huì)收到一個(gè)或多個(gè)查找錨節(jié)點(diǎn)的信標(biāo)。鄰接表建立流程如圖 32 所示：　　　開始應(yīng)答 觸發(fā)器 ＝ 0 ？有應(yīng)答信息包 ？此信息包是來自外圍節(jié)點(diǎn) ？將此節(jié)點(diǎn)插入到本節(jié)點(diǎn)鄰接表與發(fā)送緩沖區(qū)中此信息包是來自外圍節(jié)點(diǎn) ？組織本節(jié)點(diǎn)信息進(jìn)行信息發(fā)送信道空閑設(shè)置隨機(jī)退避值退避時(shí)間 ＝ 0 ？結(jié)束Y e sY e sY e sY e sY e sY e sN oN oN oN oN oN o圖 32　鄰接表建立流程南京航空航天大學(xué)碩士學(xué)位論文293．2．2．2　基于不測距定位的改進(jìn)方法對于測距信號(hào)輻射區(qū)域外的節(jié)點(diǎn)，采取與 DVHop 算法類似的定位算法。應(yīng)答信息包格式為：節(jié)點(diǎn)ID+節(jié)點(diǎn)位置+ 當(dāng)前節(jié)點(diǎn)能量剩余量(power)＋轉(zhuǎn)發(fā)信息（子節(jié)點(diǎn)信息） 。節(jié)點(diǎn)應(yīng)答過程：由于節(jié)點(diǎn)的通信能力受限，只有信號(hào)有效半徑之內(nèi)的節(jié)點(diǎn)能收到應(yīng)答信息包，因此數(shù)據(jù)包需經(jīng)多級傳遞才能到達(dá)基站。此時(shí)間差 t 將通過應(yīng)答信息包返回到基站。定位過程可分為兩個(gè)階段，即信息廣播過程和節(jié)點(diǎn)應(yīng)答過程。圖 31 定位原理圖設(shè)錨點(diǎn)坐標(biāo)分別為：A(x 1,y1),B(x2,y2),C(x3,y3)， (x,y)為目標(biāo)點(diǎn) X 的坐標(biāo)，通過解方程組：　　　　　　　　 (x 1?x)2 +　(y 1?y)2　 =R12(x2?x)2 +　(y 2?y)2　 =R22(x3?x)2 +　(y 3?y)2　 =R32可以得到目標(biāo)節(jié)點(diǎn)坐標(biāo)值，為了便于路由計(jì)算，將直角坐標(biāo)轉(zhuǎn)換成相對于基站的極坐標(biāo)（ρ, θ） 。如圖 31 所示，節(jié)點(diǎn) X 的坐標(biāo)未知，參考點(diǎn)的坐標(biāo)以及它們到 X 的距離已知。它通過三個(gè)以上的點(diǎn)與目標(biāo)之間的距離來計(jì)算目標(biāo)的坐標(biāo)位置。通過時(shí)間差測距法獲得三個(gè)錨點(diǎn)到未知節(jié)點(diǎn)的距離之后，就可對節(jié)點(diǎn)進(jìn)行目標(biāo)定位。V2為測算未知節(jié)點(diǎn)的位置，至少需要設(shè)置三個(gè)錨點(diǎn)信源，通過這三個(gè)錨點(diǎn)依次向網(wǎng)絡(luò)中所有節(jié)點(diǎn)同時(shí)發(fā)送兩種速度不一的信號(hào)，其中第一個(gè)信號(hào)為同步起始標(biāo)識(shí)（速度為 V1） ，第二個(gè)可為速度較慢的聲波或超聲波（速度為 V2） 。3．2．2 復(fù)合定位法在下文提出的復(fù)合定位法中，基于測距的定位部分采用了時(shí)間差測距法，它的主要思想是：對基站的測距信號(hào)范圍之內(nèi)的節(jié)點(diǎn)，接收由基站發(fā)射兩種速度不一的信號(hào)，然后各自計(jì)算出自己的位置；對于處于測距范圍之外的節(jié)點(diǎn)，則采用類似 DVHop 的南京航空航天大學(xué)碩士學(xué)位論文27定位法，通過計(jì)算跳數(shù)來確定節(jié)點(diǎn)位置。同時(shí)，在無線傳感器網(wǎng)絡(luò)的應(yīng)用中，因?yàn)榈匦蔚孛驳拳h(huán)境因素的影響，不可避免地有部分節(jié)點(diǎn)可能處于測距信號(hào)不可達(dá)區(qū)域，但節(jié)點(diǎn)仍能通過多跳路由采集數(shù)據(jù)，如果放棄這部分節(jié)點(diǎn)，無疑會(huì)縮小探測范圍，如果不放棄這部分節(jié)點(diǎn)，也會(huì)因?yàn)槿鄙傥恢眯畔⒃斐蓴?shù)據(jù)的不完整，降低所采集數(shù)據(jù)的可用性。雖然目前已經(jīng)提出各種各樣的技術(shù)以期達(dá)到錨節(jié)點(diǎn)的最優(yōu)布置，但在大多數(shù)情況下，都會(huì)因不可預(yù)料的自然環(huán)境影響就引起這樣或那樣的問題，這就要求在節(jié)點(diǎn)定位系統(tǒng)要有必須要有能根據(jù)具體環(huán)境動(dòng)態(tài)的、自適應(yīng)的調(diào)整定位算法的能力，為此本文提出了基于測距與不測距復(fù)合定位方法。3．2　改進(jìn)的節(jié)點(diǎn)定位機(jī)制正如在前面提到過的，不管采用何種定位方式，無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位通常都是利用傳感器網(wǎng)絡(luò)中少量已知位置的節(jié)點(diǎn)來獲得其他未知位置節(jié)點(diǎn)的位置信息，錨節(jié)點(diǎn)位置的布置和選擇將會(huì)影響到定位的精度及覆蓋率。APIT 算法最關(guān)鍵的步驟是測試未知節(jié)點(diǎn)是在 3 個(gè)錨節(jié)點(diǎn)所組成的三角形內(nèi)部還是外部，這一測試的理論基礎(chǔ)是三角形內(nèi)的點(diǎn)(PIT)測試。APIT 算法：在 APIT 算法中，一個(gè)未知節(jié)點(diǎn)從它所有能夠與之通信的錨節(jié)點(diǎn)中選擇 3 個(gè)節(jié)點(diǎn)，測試它自身是在這 3 個(gè)錨節(jié)點(diǎn)所組成的三角形內(nèi)部還是在其外部；然后再選擇另外 3 個(gè)錨節(jié)點(diǎn)進(jìn)行同樣的測試，直到窮盡所有的組合或者達(dá)到所需的精度。與 DVHop 算法不同的是：Amorphous 算法假定預(yù)先知道網(wǎng)絡(luò)的密度，然后離線計(jì)算網(wǎng)絡(luò)的平均每跳距離，最后當(dāng)獲得 3 個(gè)或更多錨節(jié)基于復(fù)合定位的無線傳感器網(wǎng)絡(luò)層次路由協(xié)議設(shè)計(jì)與實(shí)現(xiàn)26點(diǎn)的梯度值后，未知節(jié)點(diǎn)計(jì)算與每個(gè)錨節(jié)點(diǎn)的距離，并使用三邊測量法和最大似然估計(jì)法估算自身位置。首先，采用與 DVHop 算法類似的方法獲得距錨節(jié)點(diǎn)的跳數(shù)，稱為梯度值。經(jīng)過計(jì)算，一個(gè)錨節(jié)點(diǎn)得到網(wǎng)絡(luò)的平均每跳距離，并將此估計(jì)值廣播到網(wǎng)絡(luò)中，稱作校正值，任何節(jié)點(diǎn)一旦接收到此校正值，就可以估計(jì)自己到這個(gè)錨節(jié)點(diǎn)的距離。為了將跳數(shù)值轉(zhuǎn)換成物理距離，系統(tǒng)需要估計(jì)網(wǎng)絡(luò)中平均每跳的距離。接收節(jié)點(diǎn)在它收到的關(guān)于某一個(gè)錨節(jié)點(diǎn)的所有信標(biāo)中保存具有最小跳數(shù)值的信標(biāo)，丟棄具有較大跳數(shù)值的同一錨節(jié)點(diǎn)的信標(biāo)。在 DVHop 算法中，錨節(jié)點(diǎn)向網(wǎng)絡(luò)廣播一個(gè)信標(biāo)，信標(biāo)中包含有此錨節(jié)點(diǎn)的位置信息和一個(gè)初始值為 1 的表示跳數(shù)的參數(shù)。 DVHop 算法：DVHop 算法是由 和 等人提出的。質(zhì)心定位算法的最大優(yōu)點(diǎn)是它非常簡單，計(jì)算量小，完全基于網(wǎng)絡(luò)的連通性，但是需要較多的錨節(jié)點(diǎn)。具體過程為：錨節(jié)點(diǎn)每隔一段時(shí)間向鄰居節(jié)點(diǎn)廣播一個(gè)信標(biāo)信號(hào)，信號(hào)中包含有錨節(jié)點(diǎn)自身的 ID 和位置信息。質(zhì)心法：質(zhì)心法是南加州大學(xué) Nirupama Bulusu 等學(xué)者提出的一種僅基于網(wǎng)絡(luò)連通性的室外定位算法。目前比較重要的基于不測距的算法主要有：質(zhì)心法、基于測距矢量計(jì)算跳數(shù)的算法(DV Hop)、無定形的(Amorphous)算法和以三角形內(nèi)的點(diǎn)近似定位(APIT)算法。下面介紹基于不測距的定位算法。AOA 定位法的硬件系統(tǒng)設(shè)備復(fù)雜，并且需要兩節(jié)點(diǎn)之間存在視距傳輸，因此不適合用于無線傳感器網(wǎng)絡(luò)的定位。另外，AOA 信息還可以與 TOA、TDOA 信息一起使用成為混合定位法。到達(dá)角定位法：到達(dá)角(AOA)定位法通過陣列天線或多個(gè)接收器結(jié)合來得到相鄰節(jié)點(diǎn)發(fā)送信號(hào)的方向，從而構(gòu)成一根從接收機(jī)到發(fā)射機(jī)的方位線。由于這種方法不是采用到達(dá)的絕對時(shí)間來確定節(jié)點(diǎn)的位置，降低了對時(shí)間同步的要求。在二維平面上的，雙曲線的幾何意義是到兩個(gè)定點(diǎn)的距離之差為一個(gè)常數(shù)的所有點(diǎn)的集合，兩個(gè)定點(diǎn)稱作焦點(diǎn)。時(shí)間差定位法：TDOA 測距是通過計(jì)算兩種不同無線信號(hào)到達(dá)未知節(jié)點(diǎn)的時(shí)間差，再根據(jù)兩種信號(hào)傳播速度來計(jì)算得到未知節(jié)點(diǎn)與錨節(jié)點(diǎn)之間的距離。在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)間的距離較小，采用 TOA 測距難度較大，同時(shí)節(jié)點(diǎn)硬件尺寸、價(jià)格和功耗的限制也決定了 TOA 技術(shù)對無線傳感器網(wǎng)絡(luò)是不可行的。TOA 要求接收信號(hào)的錨節(jié)點(diǎn)或未知節(jié)點(diǎn)知道信號(hào)開始傳輸?shù)臅r(shí)刻，并要求節(jié)點(diǎn)有非常精確的時(shí)鐘。到達(dá)時(shí)間測距法：到達(dá)時(shí)間(TOA)技術(shù)通過測量信號(hào)傳播時(shí)間來測量距離。還有一些其他算法：如文獻(xiàn)[52]提出了一種節(jié)點(diǎn)位置推測算法，該算法通過一種判決節(jié)點(diǎn)，利用收集到的錨節(jié)點(diǎn)的位置信息和節(jié)點(diǎn)間的距離信息，執(zhí)行節(jié)點(diǎn)位置推測算法，推測出所有位置可確定的待測節(jié)點(diǎn)的位置。因此這種方法的主要誤差來源是環(huán)境影響所造成的信號(hào)傳播模型的復(fù)雜性。然而，實(shí)際應(yīng)用中的情況要復(fù)雜的多，尤其是在分布密集的無線傳感器網(wǎng)絡(luò)中。三邊計(jì)算的理論依據(jù)是，在三維空間中，知道了一個(gè)未知節(jié)點(diǎn)到三個(gè)以上錨節(jié)點(diǎn)的距離，就可以確定該點(diǎn)的坐標(biāo)。3．1．1 基于測距的定位方法 常用的定位方法是基于測距定位方法，在這種定位機(jī)制中需要先得到兩個(gè)節(jié)點(diǎn)之間的距離或者角度信息，通常采用以下方法：錨節(jié)點(diǎn)根據(jù)自身位置建立本地坐標(biāo)系，未知節(jié)點(diǎn)根據(jù)錨節(jié)點(diǎn)計(jì)算出自己在本地坐標(biāo)系里的相對位置。已知位置的節(jié)點(diǎn)稱作錨節(jié)點(diǎn)，它們可能是被預(yù)先放置好的，或者采用 GPS 或其他方法得知自己的位置。但是，在無線傳感器網(wǎng)絡(luò)中使用 GPS 來獲得所有節(jié)點(diǎn)的位置受到價(jià)格、體積、功耗以及可擴(kuò)展性等因素限制，存在著一些困難。3．1　節(jié)點(diǎn)定位機(jī)制分析關(guān)于無線傳感器網(wǎng)絡(luò)的定位問題可分為兩類，一類是無線傳感器網(wǎng)絡(luò)對自身傳感器節(jié)點(diǎn)的定位，另一類是無線傳感器網(wǎng)絡(luò)對外部目標(biāo)的定位,本文主要討論前者。此外，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自身的定位還可以在外部目標(biāo)的定位和追蹤以及提高路由效率等方面發(fā)揮作用。由于節(jié)點(diǎn)工作區(qū)域或者是人類不適合進(jìn)入的區(qū)域，或者是敵對區(qū)域，傳感器節(jié)點(diǎn)有時(shí)甚至需要通過飛行器拋撒于工作區(qū)域，因此節(jié)點(diǎn)的位置都是隨機(jī)并且未知的。2．4 本章小節(jié)本章主要從網(wǎng)絡(luò)結(jié)構(gòu)、節(jié)點(diǎn)構(gòu)成以及網(wǎng)絡(luò)協(xié)議分層三個(gè)方面介紹了無線傳感器網(wǎng)絡(luò)體系結(jié)構(gòu)，用 PIC18LF4620 處理器和 CC2420 RF 芯片的完成了傳感器節(jié)點(diǎn)硬件設(shè)計(jì)開發(fā)，搭建了路由實(shí)現(xiàn)的硬件平臺(tái)，列舉了目前傳感器網(wǎng)絡(luò)相關(guān)的關(guān)鍵技術(shù)，并針對本文內(nèi)容特點(diǎn)，著重對網(wǎng)絡(luò)拓?fù)淇刂?、網(wǎng)絡(luò)協(xié)議、節(jié)點(diǎn)定位以及時(shí)間同步技術(shù)方面的相關(guān)內(nèi)容作了必要介紹。無線通信技術(shù)：傳感器網(wǎng)絡(luò)需要低功耗短距離的無線通信技術(shù)，目前已有統(tǒng)一標(biāo)準(zhǔn) 。以數(shù)據(jù)庫的方法在傳感器網(wǎng)絡(luò)中進(jìn)行數(shù)據(jù)管理，可將存儲(chǔ)在網(wǎng)絡(luò)中的數(shù)據(jù)的邏輯視圖與網(wǎng)絡(luò)中的實(shí)現(xiàn)進(jìn)行分離，使得傳感器網(wǎng)絡(luò)的用戶只需關(guān)心數(shù)據(jù)查詢的邏輯結(jié)構(gòu)，不用關(guān)心實(shí)現(xiàn)細(xì)節(jié)?；趶?fù)合定位的無線傳感器網(wǎng)絡(luò)層次路由協(xié)議設(shè)計(jì)與實(shí)現(xiàn)222．3．5 其他關(guān)鍵技術(shù)DMTS 機(jī)制是通過選擇一個(gè)節(jié)點(diǎn)作為時(shí)間主節(jié)點(diǎn)廣播同步時(shí)間，所有接收節(jié)點(diǎn)測量這個(gè)時(shí)間廣播分組的延遲，設(shè)置它的時(shí)間為接收到分組攜帶的時(shí)間加上這個(gè)廣播分組的傳輸延遲，這樣所有接收到廣播分組的節(jié)點(diǎn)都與主節(jié)點(diǎn)進(jìn)行時(shí)間同步。RBS 機(jī)制是基于接收者之間的時(shí)間同步，一個(gè)節(jié)點(diǎn)廣播發(fā)送時(shí)間參考分組，廣播域內(nèi)的兩個(gè)節(jié)點(diǎn)分別采用本地時(shí)鐘記錄參考分組的到達(dá)時(shí)間，然后交換記錄時(shí)間來確定它們之間的時(shí)間偏移量，實(shí)現(xiàn)它們之間的時(shí)間同步?，F(xiàn)有的網(wǎng)絡(luò)時(shí)間同步機(jī)制往往關(guān)注最小化同步誤差來達(dá)到最大的同步精度，較少考慮計(jì)算和通信的開銷，因而不適合在傳感器網(wǎng)絡(luò)中應(yīng)用，需要修改或重新設(shè)計(jì)以滿足傳感器網(wǎng)絡(luò)的要求。傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)造價(jià)不能太高，節(jié)點(diǎn)的微小體積不能安裝除本地振蕩器和無線通信模塊外更多的用于同步的器件，因此，價(jià)格和體積成為傳感器網(wǎng)絡(luò)時(shí)間同步的重要約束條件。2．3．4 時(shí)間同步技術(shù)南京航空航天大學(xué)碩士學(xué)位論文21時(shí)間同步技術(shù)在傳統(tǒng)網(wǎng)絡(luò)中已經(jīng)得到廣泛應(yīng)用，如網(wǎng)絡(luò)時(shí)間協(xié)議 NTP ( Network Time Protocol) 是 Inter 采用的時(shí)間同步協(xié)議，GPS、無線測距等技術(shù)也用來提供網(wǎng)絡(luò)的全局時(shí)間同步。由于無須測量節(jié)點(diǎn)間的絕對距離或方位，因而降低了對節(jié)點(diǎn)硬件的要求，使得節(jié)點(diǎn)成本更適合于大規(guī)模傳感器網(wǎng)絡(luò)。由于節(jié)點(diǎn)定位依賴實(shí)際的角度或距離，通常定位精度相對較高，但對節(jié)點(diǎn)的硬件也提出了較高的要求。基于測距的定位機(jī)制就是通過測量相鄰節(jié)點(diǎn)間的距離或方位來確定未知節(jié)點(diǎn)的位置，通常通過測距、定位和修正等步驟來實(shí)現(xiàn)。在傳感器網(wǎng)絡(luò)定位過程中，通常會(huì)使用三邊測量法、三角測量法或極大似然估計(jì)法確定節(jié)點(diǎn)位置。根據(jù)節(jié)點(diǎn)位置是否確定，傳感器節(jié)點(diǎn)分為錨節(jié)點(diǎn)和位置未知節(jié)點(diǎn)。由于傳感器節(jié)點(diǎn)存在資源有限、隨機(jī)部署、通信易受環(huán)境干擾甚至節(jié)點(diǎn)失效等特點(diǎn)。確定事件發(fā)生的位置或采集數(shù)據(jù)的節(jié)點(diǎn)位置是傳感器網(wǎng)絡(luò)最基本的的功能之一。需要指出的是，由于傳感器網(wǎng)絡(luò)是與應(yīng)用相關(guān)的網(wǎng)絡(luò)，網(wǎng)絡(luò)協(xié)議往往需要根據(jù)應(yīng)用類型或應(yīng)用目標(biāo)環(huán)境特征定制，從目前的研究成果來看，沒有任何一個(gè)協(xié)議能夠適應(yīng)所有不同應(yīng)用。為了減少能量的消耗，MAC 協(xié)議通常采用“偵聽/睡眠”交替的無線基于復(fù)合定位的無線傳感器網(wǎng)絡(luò)層次路由協(xié)議設(shè)計(jì)與實(shí)現(xiàn)20信道偵聽機(jī)制，傳感器節(jié)點(diǎn)在需要收發(fā)數(shù)據(jù)時(shí)才偵聽無線信道，沒有數(shù)據(jù)需要收發(fā)時(shí)就盡量進(jìn)入睡眠狀態(tài)。傳感器網(wǎng)絡(luò)的 MAC 協(xié)議首先要考慮節(jié)省能源和可擴(kuò)展性，其次才考慮公平性、利用率和實(shí)時(shí)性等。同時(shí)，無線傳感器網(wǎng)絡(luò)是以數(shù)據(jù)為中心的，這在路由協(xié)議中表現(xiàn)得最為突出，每個(gè)節(jié)點(diǎn)沒有