【正文】 動(dòng)信標(biāo)與經(jīng)典的質(zhì)心定位算法、 APIT 定位算法及 DVHop 定位算法等相結(jié)合來(lái)改進(jìn)這些定位算法。 通過(guò)移動(dòng) 信標(biāo) ，或者說(shuō)移動(dòng)信標(biāo)來(lái)對(duì)整個(gè)網(wǎng)絡(luò)的未知節(jié)點(diǎn)進(jìn)行定位的方法是最來(lái)興起的一種新的定位方法，將節(jié)點(diǎn)裝載在移動(dòng)機(jī)器人上或是進(jìn)行節(jié)點(diǎn)撒播的飛行器上，并且該節(jié)點(diǎn)裝有 GPS 或其他定位裝置，這樣就構(gòu)造了移動(dòng) 信標(biāo) [23] 。 文獻(xiàn) [27] 則在 DVHop 的 基礎(chǔ) 上 引入 移 動(dòng) 的 信標(biāo) 形成 一 種新 的MADVHop 算法，實(shí)現(xiàn)在不提高硬件成本的情況下 ，又能達(dá)到同樣定位效果的構(gòu)想。另外，增加普通節(jié)點(diǎn)的同時(shí)，也提高了隨機(jī)網(wǎng)絡(luò)的連通度。當(dāng)采用移動(dòng)信標(biāo)在網(wǎng)絡(luò)中移動(dòng)來(lái)廣播定位信息時(shí)，移動(dòng)信標(biāo)的移動(dòng)路徑及廣播時(shí)間的選取，則很大程序上決定了網(wǎng)絡(luò)定位的能量消耗及定位的效率。 根據(jù)現(xiàn)有的路徑規(guī)劃方法，可 以把路徑的規(guī)劃分為靜態(tài)和動(dòng)態(tài)規(guī)劃，靜態(tài)的路徑規(guī)劃與網(wǎng)絡(luò)的連通狀況無(wú)關(guān)，根據(jù)需要定位的 ROI 區(qū)域，規(guī)劃以盡可能短的路徑覆蓋區(qū)域?yàn)槟繕?biāo)，目前靜態(tài)的路徑主要有隨機(jī)移動(dòng)模型，高斯馬爾可夫移動(dòng)模型，螺線移動(dòng)模型和 SCAN 移動(dòng)模型。 提出基于 移動(dòng) 信標(biāo) 改進(jìn)的 DVHop 定位算法 ， 該算法在 DVHop 定位算法的基礎(chǔ) 上，利用一個(gè)移動(dòng)的信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中按預(yù)定的路徑移動(dòng)并不斷的廣播自己的位置信息，形成多個(gè)虛擬信標(biāo)，未知節(jié)點(diǎn)采用加權(quán)處理的方法計(jì)算平均跳距及其與各虛擬信標(biāo)的距離，最后利用三邊測(cè)量法計(jì)算未知節(jié)點(diǎn)的位置信息，實(shí)現(xiàn)節(jié)點(diǎn)精確定位 。 文章結(jié)構(gòu)層次安排如下： 第 1 章 闡述 了本課題的研究背景、研究意義及項(xiàng)目來(lái) 源。 第 4 章 結(jié)合基于 移動(dòng) 信標(biāo) 改進(jìn)的 DVHop 定位算法，提出了 面向無(wú)線傳感器網(wǎng)絡(luò) 的移動(dòng) 信標(biāo) 的路徑規(guī)劃方法，把圖論引入 信標(biāo) 移動(dòng)路徑規(guī)劃 ， 獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化 信標(biāo) 移動(dòng)路徑。 當(dāng)前絕大多數(shù)節(jié)點(diǎn)定位算法均假設(shè)網(wǎng)絡(luò)中存在少量 信標(biāo) 節(jié)點(diǎn)，以實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的絕對(duì)定位。 廣東工業(yè)大學(xué)碩士學(xué)位論文 8 傳感器節(jié)點(diǎn)主要由低功耗的單片機(jī)，無(wú)線射頻模塊以及車載平臺(tái)等組成，它首先采集各個(gè)模擬信號(hào)，把模擬信號(hào)轉(zhuǎn)化成數(shù)字信號(hào)，經(jīng)過(guò) 單片機(jī)處理后，通過(guò)無(wú)線射頻模塊把數(shù)據(jù)傳送到匯聚節(jié)點(diǎn)。節(jié)點(diǎn) 采用 MSP430 低功耗單片機(jī)，芯片集成 SPI， IIC， 12 位 A/D 等標(biāo)準(zhǔn)接口，可以通過(guò) SPI 接口與射頻模塊 CC2420 進(jìn)行連接，節(jié)點(diǎn)還設(shè)計(jì)了了標(biāo)準(zhǔn)的傳感器接口，可以通過(guò)接口連接到常用的傳感器模塊。 對(duì)基于錨節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)進(jìn)行了研究，該系統(tǒng)能夠?qū)崿F(xiàn)移動(dòng) 節(jié)點(diǎn)的高效率定位。 結(jié)合基于 VWMC 的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法以及 錨節(jié)點(diǎn)動(dòng)態(tài)調(diào)整策略，提出了基于錨節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法，提高了算法對(duì)外界干擾的抵御能力 。 在某些無(wú)需網(wǎng)絡(luò)節(jié)點(diǎn)絕對(duì)位置的應(yīng)用中，可以采用無(wú) 信標(biāo)節(jié)點(diǎn)的 定位算法來(lái)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的相對(duì)定位。 SPA 算法的主要缺點(diǎn)是網(wǎng)絡(luò)通信開(kāi)銷太大。節(jié)點(diǎn)域廣東工業(yè)大學(xué)碩士學(xué)位論文 10 內(nèi)的所有其他從節(jié)點(diǎn)通過(guò)選擇適當(dāng)?shù)妮o助節(jié)點(diǎn)對(duì)來(lái)計(jì)算其在此局部坐標(biāo)系中的坐標(biāo)。利用 AMP 所有節(jié)點(diǎn)從隨機(jī)初始坐標(biāo)分配開(kāi)始，只利用局部距離估計(jì)和通過(guò)局部信息交換收斂到一個(gè)與距離 估計(jì)一致的坐標(biāo)分配。 基于信標(biāo)節(jié)點(diǎn)的定位 算法的 一個(gè) 重要特征是定位精度取決于 信標(biāo) 點(diǎn)密度 。 本章 首先介紹無(wú)線傳感器網(wǎng)絡(luò)常用的定位方式及其實(shí)現(xiàn)，然后 介紹常用的 基于測(cè)距和無(wú)需測(cè)距的 定位算法，并根據(jù)這些算法的特點(diǎn)，分析其優(yōu)缺點(diǎn)，為下一章提出新的 基于移動(dòng)信標(biāo)的 定位算法奠定了理論基礎(chǔ)。那么，存在下列公式： 第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究 11? ? ? ? 222 111 dYYXX ???? ? ? ? ? 222 222 dYYXX ???? ∶ ? ? ? ? 222 dnYYnXXn ???? () 最后，使用標(biāo)準(zhǔn)的最小均方差估計(jì)方法可以得到未知節(jié)點(diǎn) D 的坐標(biāo)。這樣建立起來(lái)的等式方程組沒(méi)有解，根本無(wú)法實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的定位。 圖 24 三角測(cè)量法示意圖 Fig. 24 Triangulation Method Principle 對(duì)于節(jié)點(diǎn) A， C 和角 ? ADC，如果弧段 AC 在 ? ABC 內(nèi)，那么能夠唯一確定一個(gè)圓，設(shè)圓心為 ? ?111 ,ooO x y ，半徑為 r1，那么 ? ?1 22A O C A D C??? ? ? ? ?，并存在下列公式： ? ? ? ?? ? ? ?? ? ? ?111122122122 22112 2 c o so a o ao b o ba c a cx x y y rx x y y rx x y y r r ?? ? ? ? ????? ? ? ???? ? ? ? ? ??? () 由式 ()能夠確定圓心 O1 點(diǎn)的坐標(biāo)和半徑 r1。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，然后利用該實(shí)際距離來(lái)確定未知目標(biāo)節(jié)點(diǎn)位置；后者則僅利用節(jié)點(diǎn)間距離關(guān)聯(lián)關(guān)系計(jì)算目標(biāo)節(jié)點(diǎn)位置 [35] 。 CC1000的工作頻帶為 315MHz,868MHz,915MHz，數(shù)據(jù)傳送速率可達(dá) ，適用于跳頻協(xié)議。若芯片是 CC1000： BATR S S I VVR S S I /)1 0 2 4*(? （ ） ][ d B mVP R S S I ??? （ ） ][0 d B mPPP c u r r e n t?? （ ） B a tc u r r e n t VPPR S S I /1 0 2 4*)())(( 0 ???? （ ） 其中， RSSI 是寄存器值，也就是節(jié)點(diǎn)接收到的信號(hào)強(qiáng)度值， VRSSI 是 A/D 轉(zhuǎn)換前的 RSSI 電壓值，單位為 (V)； Vbat 為電源電壓，該值為一個(gè)常數(shù)值 3V； Pcurrent是當(dāng)前節(jié)點(diǎn)的發(fā)射功率，單位為 dBm； P0 為當(dāng)節(jié)點(diǎn)與源節(jié)點(diǎn)足夠遠(yuǎn)時(shí)接收到的功率值，一般來(lái)說(shuō) P0 取 80dBm； P 為功率衰減值。同時(shí)為了更好的利用 RSSI 值估計(jì)節(jié)點(diǎn)與鄰節(jié)點(diǎn)之間的距離 ，需要建立一個(gè) RSSI 模型。其中 r 是 RSSI 測(cè)距值。因?yàn)?RSSI 在一個(gè)真實(shí)環(huán)境下的信號(hào)隨著距離的增大而減少。根據(jù)高斯分布功率表達(dá)式，得到的 接收 功率為： ? ? ? ? dBr ddndPdP ???? ?? )(l o g10 0100 （ ） 其中 ε dB為零均值及以δ 2,N(0,δ 2)變化的高斯分布隨機(jī)變量。 T 1T 2超 聲 波射 頻 信 號(hào)D 圖 26 基于 TDOA 定位 Fig. 26 Located Based on TDOA 如圖 33 所示，該技術(shù)的測(cè)距精度可達(dá)到 厘米 級(jí)，但前提是需要精確的時(shí)鐘，同時(shí)使用超聲波測(cè)量需要額外的硬件，增加了成本，而且容易受到非視距誤差的影響。但由于受到地板、墻壁和人體等各種物體等障礙物的阻攔，電磁波會(huì)存在著反射及衍射，使得 RSSI 值隨機(jī)變化較大，因此無(wú)法準(zhǔn)確判斷某一個(gè)距離對(duì)應(yīng)的 RSSI值。所以距離d 與 接收 到的信號(hào)強(qiáng)度的關(guān)系可以表示為： ? ? ? ? )(l o g10 0100 ddndPdP r ?? ?? （ ） 其中 P(d0)為參考距離 d0 接收到的信號(hào)。 RSSI 的理論模型是根據(jù)信號(hào)強(qiáng)度隨著距離的變化成對(duì)數(shù)衰 減的原理，如式（ ） ,其中 r0 是 1m距離處對(duì)應(yīng)的 RSSI 測(cè)距值， a 是信號(hào)的衰減率，理論值為 2。最優(yōu)模型如式 ()，根據(jù)給定 RSSI 的距離值r，對(duì)具有相同 RSSI 測(cè)量值的觀測(cè)數(shù)據(jù)來(lái)計(jì)算實(shí)際距離的平均值，這個(gè)模型可以很好地從收集到的數(shù)據(jù)中統(tǒng)計(jì)出有效的距離估計(jì)值。若芯片為 CC2420： ][2 5 6_ d B mR S S IV A LR S S I ?? （ ） 廣東工業(yè)大學(xué)碩士學(xué)位論文 14 ][__ d B mO F F S E TR S S IV A LR S S IP ?? （ ） 其中， RSSI 是一個(gè) 8 位的寄存器值； RSSI_VAL 為轉(zhuǎn)換前 RSSI 功率值，單位為 dBm， RSSI_OFFSET 是一個(gè)常數(shù)，約為 45dBm。對(duì)于 CC1000 通信芯片， RSSI值是一個(gè) 10 位的寄存器值，而對(duì)于 CC2420，該值卻是一個(gè) 8 位的寄存器值。 目前 很多定位算法都是利用 RSSI 技術(shù)實(shí)現(xiàn)的。最后根據(jù)已知的 r1， ? ?11,ooxy ， r2， ? ?22,ooxy ， r3， ? ?33,ooxy ，采用三邊測(cè)量法確定 D 點(diǎn)坐標(biāo)。 總的來(lái)說(shuō)，針對(duì)節(jié)點(diǎn)的定位算法都是在理想的仿真環(huán)境下進(jìn)行研究的 ，當(dāng)節(jié)點(diǎn)處于存在干擾或者移動(dòng)的情況下，這些算法或不能夠?qū)崿F(xiàn)節(jié)點(diǎn)精確的定位，或算法的計(jì)算量太大 。如下圖 21 所示，當(dāng)節(jié)點(diǎn) P1， P2， P3 未知節(jié)點(diǎn)P 發(fā)出的定位信號(hào)時(shí)，根據(jù) RSSI 值，可以得到 P1 到 P， P2 到 P， P3 到 P 的距離 d1， d2， d3；分別以 P1， P2， P3 為圓心， d1， d2， d3 為半徑作圓，通 過(guò)這 3 個(gè)圓相交區(qū)域定出未知節(jié)點(diǎn)的位置。因此可以使用更多的節(jié)點(diǎn)以獲得冗余信息來(lái)計(jì)算未知節(jié)點(diǎn)的位置。因?yàn)樾艠?biāo)節(jié)點(diǎn)造價(jià)往往比普通節(jié)點(diǎn)高，在許多固定的傳感器網(wǎng)絡(luò)中，定位成功后信標(biāo)節(jié)點(diǎn)將轉(zhuǎn)為普通節(jié)點(diǎn)使用，極大的浪費(fèi)了資源。 基于信標(biāo)節(jié)點(diǎn)的定位 算法依賴于某些已知坐標(biāo)位置的節(jié)點(diǎn)。 SDGPSN 算法和 SPA 算法相比，通信開(kāi)銷明顯 降低 ，這使得它更適于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)的部署?；舅枷?:網(wǎng)絡(luò)部署完后，每個(gè)傳感器節(jié)點(diǎn)開(kāi)始運(yùn)行一個(gè)隨機(jī)的定時(shí)器，如果與鄰居節(jié)點(diǎn)相比，節(jié)點(diǎn) i的定時(shí)器最先到期且沒(méi)有收到任何鄰居節(jié)點(diǎn)的消息，則 i升級(jí)為主節(jié)點(diǎn)，并向鄰居節(jié)點(diǎn)廣播此消息，所有接收到該消息的鄰居節(jié)點(diǎn)中止其定時(shí)器并成為該主節(jié)點(diǎn)的從節(jié)點(diǎn)。 SPA 算法選擇網(wǎng)絡(luò)中密度最大處的一組節(jié)點(diǎn)作為建立網(wǎng)絡(luò)全局坐標(biāo)系統(tǒng)的參考點(diǎn)，并在其中選擇連通度最大的一個(gè)節(jié)點(diǎn)作為坐標(biāo)系統(tǒng)的原點(diǎn)。絕對(duì)定位可為網(wǎng)絡(luò)提供唯一的命名空間 ， 受節(jié)點(diǎn)移動(dòng)性影響較小 ， 有更廣泛的應(yīng)用領(lǐng)域 。 提出基于 VWMC（ Voronoi and Weight Monte Carlo Method）的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法，該算法在 MCL（ Monte Carlo Localization）算法的基礎(chǔ)上加入 Voronoi圖和權(quán)值分析技術(shù)。同時(shí)，把節(jié)點(diǎn)放在車載平臺(tái)上，實(shí)現(xiàn)節(jié)點(diǎn)的移動(dòng) 。 無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)的硬件系統(tǒng)需要根據(jù)上面所述的要求建立合適的傳感器系統(tǒng)， 為此設(shè)計(jì)的 傳感器移動(dòng)節(jié)點(diǎn)主要由低功耗的微處理器，射頻模塊，傳感器接口 ， 電源模塊 以及車載平臺(tái) 5 部分組成，如圖 21 所示 ，普通節(jié)點(diǎn)則沒(méi)有車載平臺(tái)。由于信標(biāo)節(jié)點(diǎn)需要移動(dòng)，其在網(wǎng)絡(luò)中的作用更為重要，需要根據(jù)傳感器網(wǎng)絡(luò)的特點(diǎn) 進(jìn)行 移動(dòng)信標(biāo) 節(jié)點(diǎn)的設(shè)計(jì)及 無(wú)線傳感器網(wǎng)絡(luò)的應(yīng)用系統(tǒng)的研究 。 第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究 7 第 二 章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法 相關(guān)研究 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位 方法的 不同，分成兩種定位類型： 基于信標(biāo)節(jié)點(diǎn)和不基于信標(biāo)節(jié)點(diǎn) (也有論著將其分為無(wú)錨節(jié)點(diǎn)和有錨節(jié)點(diǎn) 的定位算法，信標(biāo)節(jié)點(diǎn)也可稱為錨節(jié)點(diǎn) )。 第 2 章 介紹了信標(biāo)節(jié)點(diǎn)定位算法的相關(guān)工作， 闡述了常用的 基于移動(dòng) 信標(biāo)的 無(wú)線傳感器節(jié)點(diǎn)定位算法，并分析了 這幾 種 常用 算法的 特點(diǎn) 。仿真證明，相對(duì)于 DVHop 算法， 基于 移動(dòng) 信標(biāo) 改進(jìn)的 DVHop 定位算法 降低了定位的成本和布網(wǎng)的復(fù)雜度 ， 提高節(jié)點(diǎn)定位的精度和效率。 本論文的主要研究?jī)?nèi)容與結(jié)構(gòu) 針對(duì) 無(wú)線 傳感器網(wǎng)絡(luò) 基于信標(biāo)節(jié)點(diǎn)的 無(wú)需測(cè)距 定位 算法 精度低， 定位效率低的情況，本文提出基于 移動(dòng) 信標(biāo) 優(yōu)化路徑 的 無(wú)線 傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位 算法 。 目前國(guó)內(nèi)外主要的路徑規(guī)劃均為靜態(tài)的路徑，研究如何使移動(dòng)節(jié)點(diǎn)的移動(dòng)軌跡可以盡量覆蓋網(wǎng)絡(luò)區(qū)域。 本 論文 針對(duì) 基于信標(biāo)的定位算法需要較高的信標(biāo)節(jié)點(diǎn)密度導(dǎo)致定位成本提高的情況，引入移動(dòng)信標(biāo)在網(wǎng)絡(luò)中移動(dòng)并廣播自己的位置分組 信息在網(wǎng)絡(luò)中構(gòu)成虛擬信標(biāo) 的方法來(lái)定位未知節(jié)點(diǎn)， 在 DVHop 定位算法的基 礎(chǔ)上將移動(dòng)信 標(biāo)構(gòu)成第一章 緒 論 5 的虛擬信標(biāo)來(lái)計(jì)算平均跳距離并結(jié)合跳數(shù)信息來(lái)對(duì)未知節(jié)點(diǎn)定位， 通過(guò) 規(guī)劃優(yōu)化的路徑來(lái)提高定位效率。根據(jù) 信標(biāo) 的即時(shí)位置信息，新位置的普通節(jié)點(diǎn)知道自身的位置。 通過(guò)移動(dòng) 信標(biāo) 來(lái)定位的主要思想是：移動(dòng) 信標(biāo) 在“感興趣的區(qū)域內(nèi)（ Region of interest，簡(jiǎn)稱 ROI）” [24] 移動(dòng)的過(guò)程中，不斷的廣播包含其當(dāng)前位置信息的分組，在其通信半徑內(nèi)的節(jié)點(diǎn)將接收到這些廣播分組，當(dāng)未知節(jié)點(diǎn)接收到三個(gè)或者三個(gè)以上的與其距離為 R 的位置信息時(shí)，就可以利用三邊測(cè)量法或極大似然估計(jì)法 [17] 計(jì)算該未知節(jié)點(diǎn)的位置。 無(wú)需測(cè)距（ rangefree）的定位算法不需要直接測(cè)量距離信息，而是根據(jù)網(wǎng)絡(luò)的連通性確定網(wǎng)絡(luò)中節(jié)點(diǎn)之間的跳數(shù)，同