【正文】 理論信號(hào)強(qiáng)度與實(shí)際信號(hào)強(qiáng)度曲線對(duì)比如下圖 23 所示： 1 0 09 59 08 58 07 57 06 56 05 55 00 2 0 4 0 6 0 8 0 1 0 0 1 2 0 1 4 0 1 6 0 1 8 0 2 0 0實(shí) 際 環(huán) 境 曲 線自 由 空 間 曲 線 圖 25 RSSI 自由空間模型 Fig. 25 RSSI Free Space Model 基于 TDOA 定位 在基于到達(dá)時(shí)間差 (TDOA)的定位機(jī)制中，發(fā)射節(jié)點(diǎn)同時(shí)發(fā)射兩種傳播速度不同的信號(hào)，接收節(jié)點(diǎn)根據(jù)兩種信號(hào)到達(dá)的時(shí)間差及 已知的信號(hào)傳播速度，計(jì)算節(jié)點(diǎn)間距。對(duì)于所有 d0=1 米的室內(nèi)環(huán)境下以及距離的信號(hào)可以由自由空間路徑損耗方程得到，路徑的損 耗指數(shù) n 由環(huán)境變量和周圍的結(jié)果決定。 ]|[)( rRdErf ?? （ ） brad ?? *~ （ ） arrd /)0( ?? （ ） 大多數(shù)情況下， RSSI 的測(cè)距采用自由空間模型，它是理論模型的一種。 最簡(jiǎn)單的 RSSI 模型就是線性模型，它使用一對(duì)參數(shù) a 和 ｂ 估計(jì)節(jié)點(diǎn)之間的距離，如式 ()。本文采用的射頻芯片是CC2420，它相對(duì)于 CC1000，使用的范圍更廣。它是通過 A/D 轉(zhuǎn)換器轉(zhuǎn)換而來的，芯片不同， RSSI 的轉(zhuǎn)換方式也是不同的。目前， WSN 網(wǎng)絡(luò)中無線通信芯片主要有兩種： CC1000 和 CC2420。 第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究 13 常用的節(jié)點(diǎn)定位算法 常用 的 Rangebase 節(jié)點(diǎn)定位算法 根據(jù)定位過程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，定位算法可分為：基于距離(RangeBased)的定位算法和距離無關(guān) (RangeFree)的定位算法 [34] 。 廣東工業(yè)大學(xué)碩士學(xué)位論文 12 三角測(cè)量定位法 三角測(cè)量法原理如圖 22 所示，已知 A、 B、 C 三個(gè)節(jié)點(diǎn)的坐標(biāo)分別為(xa,ya),(xb,yb)， (xc,yc)，節(jié)點(diǎn) D 相對(duì)于節(jié)點(diǎn) A、 B、 C 的角度分別為： ? ADB，? ADC， ? BDC，假設(shè)節(jié)點(diǎn) D 的坐標(biāo)為 (x， y)， D 為圖 22 中三個(gè)圓的交點(diǎn)。 P 1P 2P 3P 圖 23 三邊測(cè)量法原理 Fig. 23 Trilateration Method Principle 但是在真實(shí)環(huán)境下三邊測(cè)量法存在巨大的缺陷，如圖 36 所示，實(shí)際上測(cè)量得到的 3 個(gè)距離 RP1， RP2， RP3 存在著誤差，導(dǎo)致以 RP1， RP2， RP3 為半徑建立的3 個(gè)圓并不是相 交于一點(diǎn)，而是相交于一個(gè)區(qū)域。 極大似然估計(jì)多邊測(cè)量 [33] 就采用了上面的方法， 已知 n 個(gè)節(jié)點(diǎn)的坐標(biāo)分別為 (X1,Y1)， (X2,Y2)，(X3,Y3)， … .， (Xn ,Yn )，它們到未知節(jié)點(diǎn) D 的距離分別為 dl， d2， d3， … .，dn，假設(shè)節(jié)點(diǎn) D 的坐標(biāo)為 (X， Y)。所以基于移動(dòng)信標(biāo)節(jié)點(diǎn)的定位算法成為近年來研究的一個(gè)熱點(diǎn)。這種定位算法需要預(yù)先定位 信標(biāo)節(jié)點(diǎn) ，否則無法正常運(yùn)行，另外為了減小定位誤差， 信標(biāo)節(jié)點(diǎn)的數(shù)目還須足夠多。 AFL 算法是完全分布式的節(jié)點(diǎn)定位方法。這些節(jié)點(diǎn)構(gòu)成一個(gè)以主節(jié)點(diǎn) i為坐標(biāo)原點(diǎn)的節(jié)點(diǎn)域，并隨掃 A 擇兩個(gè)與 i相鄰的從節(jié)點(diǎn)為輔助節(jié)點(diǎn)對(duì)，構(gòu)建一個(gè)局部坐標(biāo)系。首先根據(jù)節(jié)點(diǎn)間的測(cè) 距結(jié)果在各個(gè)節(jié)點(diǎn)上建立局部坐標(biāo)系統(tǒng)，通過節(jié)點(diǎn)間的信息交換與協(xié)調(diào)，以參考點(diǎn)為基準(zhǔn)通過坐標(biāo)變換逐步建立全局坐標(biāo)系統(tǒng)。 但研究發(fā)現(xiàn) ， 在相對(duì)定位的基礎(chǔ)上也能夠?qū)崿F(xiàn)部分路由協(xié)議 ， 尤其是基于地理位置的路由 (georouting)， 而且相對(duì)定位不需要 信標(biāo)節(jié)點(diǎn) 。仿真證明，相對(duì)于 MCL 算法，基于 VWMC 的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法提高了移動(dòng)節(jié)點(diǎn)定位的精度和效率 。 圖 22 傳感器網(wǎng)絡(luò)節(jié)點(diǎn) Fig. 22 Sensor Network Nodes 第二章 傳感器網(wǎng)絡(luò)常用節(jié)點(diǎn)定位算法相關(guān)研究 9 黎大鵬在文獻(xiàn) [29] 中研究了基于信標(biāo)節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的移動(dòng)節(jié)點(diǎn)的定位算法。 微 處 理 器傳 感 器接 口溫 度濕 度壓 力車 載 平 臺(tái)射 頻 模 塊光 強(qiáng) 度電 源 模 塊 圖 21 傳感器移動(dòng)節(jié)點(diǎn)結(jié)構(gòu) Fig. 21 Sensor Network Mobile Nodes Structure 根據(jù)此模型設(shè)計(jì)制作的移動(dòng)節(jié)點(diǎn)如下圖 22 所示。 構(gòu)建無線傳感器網(wǎng)絡(luò) 應(yīng)用 系統(tǒng)， 需要考慮網(wǎng)絡(luò)在應(yīng)用中 的成本、數(shù)量、通信方面存在的諸多問題， 主要 需要考慮以下幾個(gè)方面： 低成本：系統(tǒng)必須是低成本，不僅從節(jié)點(diǎn)硬件、軟件考慮，而且傳感器也必須采用相對(duì)價(jià)格低的產(chǎn)品 ； 低功耗：系統(tǒng)中采用普通 AAA 電池供電，所以要求網(wǎng)絡(luò)必須是低功耗的，保證網(wǎng)絡(luò)的生命周期盡量長(zhǎng) ； 實(shí)時(shí)監(jiān)測(cè)：監(jiān)測(cè)信息需實(shí)時(shí)傳輸?shù)焦芾矸?wù)器，方便用戶實(shí)時(shí)查詢 ； 網(wǎng)關(guān)無線通信：由于監(jiān)測(cè)區(qū)域的特殊性，不一定存在有線網(wǎng)絡(luò)，例如：Inter、有線局域網(wǎng)等，故網(wǎng)關(guān)具有把采集的環(huán)境信息無線傳輸?shù)椒?wù)器的功能，不受監(jiān)測(cè)區(qū)域的影響 ； 精度：傳感器決定了采集數(shù)據(jù)的精度，傳感器采集數(shù)據(jù)的精度可以在規(guī)定范圍內(nèi)存在一定程度的誤差 ； 傳感器接口靈活：系統(tǒng)根據(jù)環(huán)境參數(shù)的不同采用不相同的接口，傳感器的類型也需根據(jù)實(shí)際需要而定，因此節(jié)點(diǎn)的傳感器接口需靈活設(shè)定。 不基于信標(biāo)節(jié)點(diǎn)的定位方法屬于相對(duì)定位，基于信標(biāo)的定位算法可以得出未知節(jié)點(diǎn)的絕對(duì)坐標(biāo)。 第 3 章 研究基于移動(dòng) 信標(biāo) 的 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的 定位算法 ， 將移動(dòng) 信標(biāo)引入到 DVHop 定位 算法中， 提出了基于 移動(dòng) 信標(biāo) 的 DVHop 定位 算法 和基于移動(dòng) 信標(biāo) 動(dòng)態(tài)選擇的 改進(jìn) DVHop 定位算法 ，同時(shí) 分析了 改進(jìn)算法在特定移動(dòng) 模型下的 定位 精度 。 結(jié)合基于 移動(dòng) 信標(biāo) 改進(jìn)的 DVHop 定位算法，提出了基于 ROI(region of interest)的移動(dòng) 信標(biāo) 的路徑規(guī)劃方法，并把圖論引入 信標(biāo) 移動(dòng)路徑規(guī)劃 ， 獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化 信標(biāo) 移動(dòng)路徑，提高算法的定位精度，減少算法定位過程的通信開銷，提高 算法 的效率 。研究的內(nèi)容主要如下： 分析 歸納常用的 無需測(cè)距的定位算法和基于信標(biāo)的定位算法，研究基于信標(biāo)的定位算法的定位機(jī)制 ， 研究利用移動(dòng)信標(biāo)的信息來進(jìn)行定位計(jì)算 。這樣 的算法顯然不能最大限度的節(jié)約節(jié)點(diǎn)的能耗，對(duì)于嚴(yán)格要求能源的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)來說，必然需要更為優(yōu)化及適用于當(dāng)前網(wǎng)絡(luò)的路徑規(guī)劃算法來使節(jié)點(diǎn)移動(dòng)路徑盡可以少，減少?gòu)V播的信息來減少網(wǎng)絡(luò)節(jié)點(diǎn)的通信消耗。 對(duì)于移動(dòng)信標(biāo)的移動(dòng)路徑的規(guī)劃也是一個(gè)重要的問題，本文進(jìn)行了初步的研究。它們就等同于 信標(biāo) 。 國(guó)內(nèi)外對(duì)于移動(dòng) 信標(biāo) 的定位方法及 信標(biāo) 的移動(dòng)路徑的規(guī)劃研究處于起步階段，相關(guān)的文獻(xiàn)并不多，提出的算法也不夠成熟，文獻(xiàn) [25] 和 [26] 提出的定位方法只需要一個(gè)可以移動(dòng)的 信標(biāo) ，其中文 獻(xiàn) [25] 利用 TOA 測(cè)距技術(shù)和質(zhì)心法來計(jì)算待定位節(jié)點(diǎn)位置，文 獻(xiàn) [26] 不需要復(fù)雜的測(cè)距技術(shù)，而是通過 信標(biāo) 的不斷運(yùn)動(dòng)并利用幾何限制關(guān)系來計(jì)算待定位節(jié)點(diǎn)位置。典型的無需測(cè)距的定位算法有 DVHop 定位算法， APIT 定位算法、質(zhì)心定位算法、 Amorphous 定位算法等，它們所需的網(wǎng)絡(luò)模型都是由參考節(jié)點(diǎn)和未知位置的節(jié)點(diǎn)組成 。所以移動(dòng)信標(biāo)的定位算法近來成為新的研究熱點(diǎn)，國(guó)內(nèi)外許多學(xué)者進(jìn)行了許多的研究，基于移動(dòng)信標(biāo)的定位算法 主要研究問題是如何將移動(dòng)信標(biāo)與現(xiàn)在的定位算法結(jié)合，研究構(gòu)造的虛擬信標(biāo)的動(dòng)態(tài)選擇算法及移動(dòng)信標(biāo)的移動(dòng)路徑的規(guī)劃。 國(guó)內(nèi)外研究現(xiàn)狀 基于移動(dòng)信標(biāo)的定位算法是近年來的研究熱點(diǎn)。 免測(cè)距的定位算法不需要測(cè)量節(jié)點(diǎn)間的距離，而是利用距離矢量路由、網(wǎng)絡(luò)連通情況或者 GPS 定位等思想提出的一種分布式定位方法，無需測(cè)距，這無疑降低了組網(wǎng)成本。而在無線傳感器網(wǎng)絡(luò)中引入移動(dòng)節(jié)點(diǎn)，可以增強(qiáng)其功能。 雖然節(jié)點(diǎn)的移動(dòng)性使定位過程復(fù)雜化，但是利用節(jié)點(diǎn)的移動(dòng)性可提高定位精度，減少定位代價(jià)。 目前基于距離的定位算法都是利用靜態(tài)的幾何關(guān)系來確定節(jié)點(diǎn)位置，且對(duì)信標(biāo)節(jié)點(diǎn)的布置和密度要求高，如三邊、多邊測(cè)量定位、基于角度測(cè)量定位等算法，都需要移動(dòng)節(jié)點(diǎn)至少獲得 3 個(gè)或者 3 個(gè)以上信標(biāo)節(jié)點(diǎn)提供的坐標(biāo)和距離 [13] 。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或方位，然后利用該實(shí)際距離來確定未知目標(biāo)節(jié)點(diǎn)位置；后者則僅利用節(jié)點(diǎn)間距離關(guān)聯(lián)關(guān)系計(jì)算目標(biāo)節(jié)點(diǎn)位置。 傳感器節(jié)點(diǎn)自身定位就是一種通過估計(jì)至鄰居節(jié)點(diǎn)的距離或鄰居數(shù)目，利用節(jié)點(diǎn)間的信息交換來確定各節(jié)點(diǎn)自身位置的機(jī)制。只有在傳感器節(jié)點(diǎn)自身正確定位后，才能確定傳感器節(jié)點(diǎn)監(jiān)測(cè)到的事件及信息發(fā)生的具體位置 [3] 。它打破了傳統(tǒng)的點(diǎn)對(duì)點(diǎn)的數(shù)據(jù)信息交互方式，帶來了一種全新的信息獲取和處理模式 [1] 。 結(jié)合 基于 移動(dòng) 信標(biāo) 改進(jìn)的 DVHop 定位算法 ，提出了面向無線傳感器網(wǎng)絡(luò) 的移動(dòng) 信標(biāo) 的路徑規(guī)劃方法，把圖論引入 信標(biāo) 移動(dòng) 路徑規(guī)劃 ， 獲取針對(duì)所處網(wǎng)絡(luò)連通狀況的優(yōu)化 信標(biāo) 移動(dòng)路徑，提高算法的定位精度，減少算法定位過程的通信開銷，提高 算法 的效率 。 針對(duì)這種情況， 本論文 對(duì) 基于 移動(dòng) 信標(biāo) 優(yōu)化路徑的無線 傳感器網(wǎng)絡(luò)節(jié)點(diǎn) 算法進(jìn)行了研究 ，該 定位算法 能夠?qū)崿F(xiàn) 節(jié)點(diǎn)的高效率定位。 廣東工業(yè)大學(xué)碩士學(xué)位論文 ( 工學(xué)碩士 ) 基于移動(dòng) 信標(biāo) 優(yōu)化路徑的 定位算法研究 Classified Index: School Code: 11845 UDC: Security Class: Class No.:2110704294 A Dissertation for Master’s Degree of Guangdong University of Technology （ Master of Engineering Science） Research on Localization Algorithm Based on Mobile Beacon with Optimal path Candidate: Xie Xiaosong Supervisor: Prof. Cheng Lianglun May 20xx Faculty of Automation Guangdong University of Technology Guangzhou, Guangdong, , 510006摘 要 I 摘 要 無線傳感器節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò) 的 關(guān)鍵技術(shù)之一， 是無線傳感器網(wǎng)絡(luò)大多數(shù)應(yīng)用的基礎(chǔ)。文章 在 DVHop 定位算法中引入移動(dòng)信標(biāo)節(jié)點(diǎn) ， 并研究信標(biāo)節(jié)點(diǎn)的動(dòng)態(tài)選擇算法及 移動(dòng)路徑優(yōu)化算法 。 最后 在 OMNeT++仿真環(huán)境下，仿真基于移動(dòng) 信標(biāo) 的定位算法， 建立包括 移動(dòng)智能節(jié)點(diǎn) 和 普通節(jié)點(diǎn)的仿真模型，通過定位過程的通信和數(shù)據(jù)處理計(jì)算未知節(jié)點(diǎn)的位置，仿真表明 ，基于 移動(dòng) 信標(biāo) 優(yōu)化路徑的定位算法 既改善了定位的精度，又減少了定位 算法 的 通信開銷 ， 提高無線 傳感器網(wǎng)絡(luò)節(jié)點(diǎn) 定位效率 。 無線傳感器網(wǎng)絡(luò) (Wireless Sensor Networks， WSN)是由部署在監(jiān)測(cè)區(qū)內(nèi)大量的廉價(jià)微型傳感器節(jié) 點(diǎn)組成，通過無線通信方式形成的一個(gè)多跳的自組織的網(wǎng)絡(luò)系統(tǒng)，其目的是協(xié)作地感知、采集和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對(duì)象的信息，并傳送給觀察者 [2] 。節(jié)點(diǎn)必須明確自身位置才能詳細(xì)說明“在什么位置或區(qū)域發(fā)生了特定事件”，實(shí)現(xiàn)對(duì)外部目標(biāo)的定位和追蹤。在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)能夠自主確定位置被認(rèn)為是其基本能力和系統(tǒng)的基本服務(wù)之一。 Rangebased算 法通過測(cè)量相鄰節(jié)點(diǎn)間的實(shí)際距離或方位進(jìn)行定位，測(cè)量距離的具體的方法有Time of Arrival(TOA) [6] ， Time Difference of Arrival(TDOA)[7] ， Radio Signal Strength(RSSI)[8] 和 Angle of Arrival(AOA)[9] 等。另一種思想則是使信標(biāo)或者 信標(biāo) 運(yùn)動(dòng)起來，通過帶有 GPS 的已知位置的移動(dòng) 信標(biāo)按某一規(guī)劃好的路徑或運(yùn)動(dòng)模型遍歷未知節(jié)點(diǎn)的區(qū)域，并發(fā)送定位信號(hào)，其它節(jié)點(diǎn)獲取這些信號(hào)來進(jìn)行定位計(jì)算。在 Bergamo 等的研究中，網(wǎng)絡(luò)中有 2 個(gè)固定的 信標(biāo) 向全網(wǎng)傳送坐標(biāo)信息，其余處于運(yùn)動(dòng)狀態(tài)的節(jié)點(diǎn)根據(jù)接收到的信號(hào)強(qiáng)度進(jìn)行自身定位[16] 。如文獻(xiàn) [19] 通過將幾個(gè)未知節(jié)點(diǎn)移動(dòng)到網(wǎng)絡(luò)節(jié)點(diǎn)密度相對(duì)稀疏的區(qū)域以彌補(bǔ)節(jié)點(diǎn)密度分布不均勻的不足。但由于沒有相應(yīng)的硬件測(cè)距支持，定位存在一定程序的誤差，當(dāng)網(wǎng)絡(luò)中存在障礙物時(shí)，節(jié)點(diǎn)間的歐氏距離會(huì)因?yàn)閺澢窂蕉a(chǎn)生較大的誤差，精度也相應(yīng)的降低 [21] 。由于網(wǎng)絡(luò)定位算法大多依賴于信標(biāo)節(jié)點(diǎn)的密度，網(wǎng)絡(luò)的聯(lián)通性。為此，國(guó)內(nèi)外有許多學(xué)者把移