【正文】 點(diǎn)將其與本身的數(shù)據(jù)包進(jìn)行比較，取跳數(shù)較小的一項(xiàng)，并丟棄較大的，將跳數(shù)一項(xiàng)加1，記錄下這個(gè)跳數(shù)值，等待下一個(gè)定位信息包；步驟3：移動(dòng)信標(biāo)移動(dòng)到下一個(gè)位置，將位置信息加1并廣播這個(gè)一新位置的定位信息包，同時(shí)接收各節(jié)點(diǎn)發(fā)回的廣播信息，取與前一位置最小跳數(shù)的分組，將兩位置的距離除以跳數(shù)計(jì)算出平均每跳距離(Di)并廣播到網(wǎng)絡(luò)中；步驟4：重復(fù)步驟3直到位置號(hào)達(dá)到預(yù)先設(shè)定的閾值K，K根據(jù)所需的虛擬信標(biāo)密度而定，如果網(wǎng)絡(luò)中有N個(gè)未知節(jié)點(diǎn)，根據(jù)精度要求得出虛擬信標(biāo)比例q，則；步驟5：節(jié)點(diǎn)根據(jù)接收到的各個(gè)虛擬信標(biāo)的平均跳距離按權(quán)值進(jìn)行校正，并根據(jù)記錄的跳數(shù)計(jì)算出到各個(gè)虛擬信標(biāo)的距離，挑選出最優(yōu)的虛擬信標(biāo)節(jié)點(diǎn)距離信息，按優(yōu)化的三邊測(cè)量法計(jì)算自己的位置?；谝苿?dòng)信標(biāo)節(jié)點(diǎn)算法的定位過程信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中移動(dòng)，周期性地將位置信息廣播到網(wǎng)絡(luò)中，廣播的信息格式包括當(dāng)前運(yùn)動(dòng)到第幾個(gè)點(diǎn)，當(dāng)前位置坐標(biāo)，網(wǎng)絡(luò)跳數(shù)(初始化為0)，在移動(dòng)信標(biāo)節(jié)點(diǎn)通信范圍的未知節(jié)點(diǎn)都接收到該位置的信標(biāo)節(jié)點(diǎn)的定位數(shù)據(jù)包。為此本文選擇GaussMarkov運(yùn)動(dòng)模型，該模型可以覆蓋網(wǎng)絡(luò)的大部分區(qū)域，相對(duì)于RWP模型，可以避免運(yùn)動(dòng)軌跡的突變和邊緣地帶概率減少的缺點(diǎn)[40] ，對(duì)硬件的要求也不高，其模型表示如下： () ()v(k)和d(k)表示運(yùn)動(dòng)時(shí)刻k移動(dòng)信標(biāo)的速度和方向。信標(biāo)節(jié)點(diǎn)移動(dòng)模型 移動(dòng)信標(biāo)節(jié)點(diǎn)采用什么樣的方式移動(dòng)才能盡可能的遍歷整個(gè)網(wǎng)絡(luò)，這個(gè)本身就是一個(gè)研究的熱點(diǎn)，網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)本身是隨機(jī)散布的，節(jié)點(diǎn)位置本身信息是未知的，為了使這些節(jié)點(diǎn)全部進(jìn)行定位，需要設(shè)計(jì)出一種運(yùn)動(dòng)模型，使移動(dòng)信標(biāo)的運(yùn)動(dòng)軌跡能在盡少的時(shí)間內(nèi)遍歷網(wǎng)絡(luò)，發(fā)送足夠的定位信息給未知節(jié)點(diǎn)以完成定位算法。所以為了提高定位的準(zhǔn)確性，需要增加信標(biāo)節(jié)點(diǎn)。2)、 DVHop定位算法的信標(biāo)節(jié)點(diǎn)比例分析在傳感器網(wǎng)絡(luò)中，假設(shè)某未知節(jié)點(diǎn)的坐標(biāo)記為(xn, yn)，實(shí)際的坐標(biāo)記為(Xn, Yn)，兩個(gè)位置的距離為：d= ()平均定位誤差的定義與節(jié)點(diǎn)的無線傳輸范圍有關(guān)[39] ,為： ()建立實(shí)驗(yàn)的仿真環(huán)境來分析DVHop定位算法的性能，主要分析不同的信標(biāo)比例對(duì)定位精度的影響。第三階段：未知節(jié)點(diǎn)利用第二階段中記錄的到各個(gè)信標(biāo)節(jié)點(diǎn)的跳段距離，利用三邊測(cè)量法或極大似然估計(jì)法計(jì)算自身坐標(biāo)。第二階段：計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的實(shí)際跳段距離。信標(biāo)節(jié)點(diǎn)向鄰居節(jié)點(diǎn)廣播自身位置信息的分組，其中包括跳數(shù)字段，初始化為1。 DVHop定位算法DVHop算法分析Niculescu D等人提出的DVHop定位算法不需要直接測(cè)量節(jié)點(diǎn)間的距離，該算法具有方法簡(jiǎn)單，定位精度高等優(yōu)點(diǎn)，它是利用距離矢量路由和GPS定位思想提出的一系列分布式定位方法之一[10] 。針對(duì)這種情況，本文提出了一種基于移動(dòng)信標(biāo)的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法，減少無線傳感器網(wǎng)絡(luò)定位的成本和復(fù)雜度，并且提高了定位精度。根據(jù)是否需要測(cè)距，定位算法可以分為基于測(cè)距的和無需測(cè)距的，基于測(cè)距的定位算法依賴于硬件條件，在自然環(huán)境中，還會(huì)受到各種不確定因素的干擾[38] 。比如，在跟蹤目標(biāo)和檢測(cè)突發(fā)事件中。由于只采用一個(gè)移動(dòng)信標(biāo)，降低了定位的成本和布網(wǎng)的復(fù)雜度?；谝苿?dòng)信標(biāo)動(dòng)態(tài)選擇的改進(jìn)DVHop定位算法在信標(biāo)計(jì)算網(wǎng)絡(luò)平均跳距離時(shí)采用動(dòng)態(tài)選擇算法，獲得的計(jì)算結(jié)果摒棄了導(dǎo)致誤差的因素，使網(wǎng)絡(luò)平均跳距離更接近網(wǎng)絡(luò)的真實(shí)情況。本章主要介紹常用的無需測(cè)距的定位算法，介紹了這些算法解決定位誤差問題的方法，及其還存在的問題，大多無需測(cè)距的定位算法的定位精度依賴于信標(biāo)節(jié)點(diǎn)的密度及網(wǎng)絡(luò)的連通狀況。PIT測(cè)試原理是假設(shè)存在一個(gè)方向，未知節(jié)點(diǎn)沿此方向移動(dòng)會(huì)同時(shí)遠(yuǎn)離或接近三個(gè)信標(biāo),那么未知節(jié)點(diǎn)位于三個(gè)信標(biāo)構(gòu)成的三角形外部；否則，未知節(jié)點(diǎn)位于三角形內(nèi)。節(jié)點(diǎn)收集鄰居節(jié)點(diǎn)的跳數(shù)，計(jì)算關(guān)于某個(gè)信標(biāo)局部跳數(shù)的平均值，如()式，式中hi表示節(jié)點(diǎn)i與信標(biāo)之間的跳數(shù)，hj表示鄰居節(jié)點(diǎn)j與這個(gè)信標(biāo)之間的跳數(shù)，nbsr(i)表示節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合。誤差很大。然后因?yàn)锳到L1只有一跳。A點(diǎn)到L1點(diǎn)為15，跳幀的數(shù)量為1，A點(diǎn)到L2,L3的跳幀的數(shù)量為3，平均每跳為10。而且它不需要額外信息，然而，誤差根據(jù)路由的彎曲程度的不同而不同。未知節(jié)點(diǎn)將記錄接收到的第一個(gè)校正值，轉(zhuǎn)發(fā)給鄰居節(jié)點(diǎn)。本節(jié)列出了常用的三種無需測(cè)距(Rangefree)的定位算法：DVHop定位算法，Euclidean定位算法，APIT定位算法。圖26基于TDOA定位Fig. 26 Located Based on TDOA如圖33所示，該技術(shù)的測(cè)距精度可達(dá)到厘米級(jí)，但前提是需要精確的時(shí)鐘，同時(shí)使用超聲波測(cè)量需要額外的硬件，增加了成本，而且容易受到非視距誤差的影響。根據(jù)高斯分布功率表達(dá)式，得到的接收功率為： （）其中εdB為零均值及以δ2, N(0,δ2)變化的高斯分布隨機(jī)變量。因?yàn)镽SSI在一個(gè)真實(shí)環(huán)境下的信號(hào)隨著距離的增大而減少。其中r是RSSI測(cè)距值。同時(shí)為了更好的利用RSSI值估計(jì)節(jié)點(diǎn)與鄰節(jié)點(diǎn)之間的距離，需要建立一個(gè)RSSI模型。若芯片是CC1000： （） （） （） （）其中，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í)接收到的功率值，一般來說P0取80dBm；P為功率衰減值。CC1000的工作頻帶為315MHz,868MHz,915MHz，適用于跳頻協(xié)議。前者需要測(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)位置[35] 。圖24三角測(cè)量法示意圖Fig. 24 Triangulation Method Principle對(duì)于節(jié)點(diǎn)A，C和角ADC，如果弧段AC在ABC內(nèi)，那么能夠唯一確定一個(gè)圓，設(shè)圓心為，半徑為r1，那么，并存在下列公式： ()由式()能夠確定圓心O1點(diǎn)的坐標(biāo)和半徑r1。這樣建立起來的等式方程組沒有解，根本無法實(shí)現(xiàn)對(duì)節(jié)點(diǎn)的定位。那么，存在下列公式： ∶ ()最后，使用標(biāo)準(zhǔn)的最小均方差估計(jì)方法可以得到未知節(jié)點(diǎn) D 的坐標(biāo)。本章首先介紹無線傳感器網(wǎng)絡(luò)常用的定位方式及其實(shí)現(xiàn)，然后介紹常用的基于測(cè)距和無需測(cè)距的定位算法，并根據(jù)這些算法的特點(diǎn)，分析其優(yōu)缺點(diǎn)，為下一章提出新的基于移動(dòng)信標(biāo)的定位算法奠定了理論基礎(chǔ)?；谛艠?biāo)節(jié)點(diǎn)的定位算法的一個(gè)重要特征是定位精度取決于信標(biāo)點(diǎn)密度。利用AMP所有節(jié)點(diǎn)從隨機(jī)初始坐標(biāo)分配開始，只利用局部距離估計(jì)和通過局部信息交換收斂到一個(gè)與距離估計(jì)一致的坐標(biāo)分配。節(jié)點(diǎn)域內(nèi)的所有其他從節(jié)點(diǎn)通過選擇適當(dāng)?shù)妮o助節(jié)點(diǎn)對(duì)來計(jì)算其在此局部坐標(biāo)系中的坐標(biāo)。SPA算法的主要缺點(diǎn)是網(wǎng)絡(luò)通信開銷太大。在某些無需網(wǎng)絡(luò)節(jié)點(diǎn)絕對(duì)位置的應(yīng)用中，可以采用無信標(biāo)節(jié)點(diǎn)的定位算法來實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的相對(duì)定位。結(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ì)外界干擾的抵御能力。對(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é)點(diǎn)采用MSP430低功耗單片機(jī)，芯片集成SPI，IIC，12位A/D等標(biāo)準(zhǔn)接口，可以通過SPI接口與射頻模塊CC2420進(jìn)行連接，節(jié)點(diǎn)還設(shè)計(jì)了了標(biāo)準(zhǔn)的傳感器接口，可以通過接口連接到常用的傳感器模塊。傳感器節(jié)點(diǎn)主要由低功耗的單片機(jī)，無線射頻模塊以及車載平臺(tái)等組成，它首先采集各個(gè)模擬信號(hào)，把模擬信號(hào)轉(zhuǎn)化成數(shù)字信號(hào)，經(jīng)過單片機(jī)處理后，通過無線射頻模塊把數(shù)據(jù)傳送到匯聚節(jié)點(diǎn)。當(dāng)前絕大多數(shù)節(jié)點(diǎn)定位算法均假設(shè)網(wǎng)絡(luò)中存在少量信標(biāo)節(jié)點(diǎn)，以實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)的絕對(duì)定位。第4章 結(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)路徑。文章結(jié)構(gòu)層次安排如下：第1章 闡述了本課題的研究背景、研究意義及項(xià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)精確定位。根據(jù)現(xiàn)有的路徑規(guī)劃方法，可以把路徑的規(guī)劃分為靜態(tài)和動(dòng)態(tài)規(guī)劃，靜態(tài)的路徑規(guī)劃與網(wǎng)絡(luò)的連通狀況無關(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)采用移動(dòng)信標(biāo)在網(wǎng)絡(luò)中移動(dòng)來廣播定位信息時(shí)，移動(dòng)信標(biāo)的移動(dòng)路徑及廣播時(shí)間的選取，則很大程序上決定了網(wǎng)絡(luò)定位的能量消耗及定位的效率。另外，增加普通節(jié)點(diǎn)的同時(shí)，也提高了隨機(jī)網(wǎng)絡(luò)的連通度。文獻(xiàn)[27] 則在DVHop的基礎(chǔ)上引入移動(dòng)的信標(biāo)形成一種新的MADVHop算法，實(shí)現(xiàn)在不提高硬件成本的情況下，又能達(dá)到同樣定位效果的構(gòu)想。通過移動(dòng)信標(biāo)，或者說移動(dòng)信標(biāo)來對(duì)整個(gè)網(wǎng)絡(luò)的未知節(jié)點(diǎn)進(jìn)行定位的方法是最來興起的一種新的定位方法，將節(jié)點(diǎn)裝載在移動(dòng)機(jī)器人上或是進(jìn)行節(jié)點(diǎn)撒播的飛行器上，并且該節(jié)點(diǎn)裝有GPS或其他定位裝置，這樣就構(gòu)造了移動(dòng)信標(biāo)[23] 。為此，國內(nèi)外有許多學(xué)者把移動(dòng)信標(biāo)與經(jīng)典的質(zhì)心定位算法、APIT定位算法及DVHop定位算法等相結(jié)合來改進(jìn)這些定位算法。由于網(wǎng)絡(luò)定位算法大多依賴于信標(biāo)節(jié)點(diǎn)的密度，網(wǎng)絡(luò)的聯(lián)通性。但由于沒有相應(yīng)的硬件測(cè)距支持，定位存在一定程序的誤差，當(dāng)網(wǎng)絡(luò)中存在障礙物時(shí)，節(jié)點(diǎn)間的歐氏距離會(huì)因?yàn)閺澢窂蕉a(chǎn)生較大的誤差，精度也相應(yīng)的降低[21] 。如文獻(xiàn)[19] 通過將幾個(gè)未知節(jié)點(diǎn)移動(dòng)到網(wǎng)絡(luò)節(jié)點(diǎn)密度相對(duì)稀疏的區(qū)域以彌補(bǔ)節(jié)點(diǎn)密度分布不均勻的不足。在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] 。另一種思想則是使信標(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ì)算。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] 等。在傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)能夠自主確定位置被認(rèn)為是其基本能力和系統(tǒng)的基本服務(wù)之一。節(jié)點(diǎn)必須明確自身位置才能詳細(xì)說明“在什么位置或區(qū)域發(fā)生了特定事件”，實(shí)現(xiàn)對(duì)外部目標(biāo)的定位和追蹤。無線傳感器網(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] 。 最后在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)定位效率。文章在DVHop定位算法中引入移動(dòng)信標(biāo)節(jié)點(diǎn)，并研究信標(biāo)節(jié)點(diǎn)的動(dòng)態(tài)選擇算法及移動(dòng)路徑優(yōu)化算法。廣東工業(yè)大學(xué)碩士學(xué)位論文(工學(xué)碩士)基于移動(dòng)信標(biāo)優(yōu)化路徑的定位算法研究分類號(hào)： 學(xué)校代號(hào)：11845UDC： 密級(jí)： 學(xué)號(hào)：2110704294廣東工業(yè)大學(xué)碩士學(xué)位論文（工學(xué)碩士）基于移動(dòng)信標(biāo)優(yōu)化路徑的定位算法研究指導(dǎo)教師姓名、職稱： 教授 企業(yè)導(dǎo)師姓名、職稱： 無 專業(yè) 或 領(lǐng)域 名 稱： 控制理論與控制工程 學(xué) 生 所 屬 學(xué) 院： 自動(dòng)化學(xué)院 論 文 答 辯 日 期： 65 Classified Index: School Code: 11845UDC: Security Class: Class No.:2110704294A Dissertation for Master’s Degree of Guangdong University of Technology（Master of Engineering Science）Research on Localization Algorithm Based on Mobile Beacon with Optimal pathCandidate: Xie XiaosongSupervisor: Prof. Cheng LianglunMay 2010Faculty of AutomationGuangdong University of TechnologyGuangzhou, Guangdong, , 510006摘 要摘 要無線傳感器節(jié)點(diǎn)定位技