【正文】 alization algorithms base on beacon.2. Improving DVHop localization algorithm based on mobile beacon, the algorithm use a mobile beacon node to move in the network according to a predetermined path and broadcast it’s location information that create virtual beacons. We study the weighted average hop distance algorithm and the dynamic beacon node selection algorithm to reduce localization costs and plexity of distribution networks and improve accuracy and efficiency of node localization. 3. Combined with the improved DVHop localization algorithm based on mobile beacon, we proposed mobile beacon path planning method for wireless sensor networks. Graph theory is introduced into the mobile path planning。它打破了傳統(tǒng)的點(diǎn)對(duì)點(diǎn)的數(shù)據(jù)信息交互方式，帶來(lái)了一種全新的信息獲取和處理模式[1] 。傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在部署時(shí)往往是不可控制的，比如在大型的無(wú)線傳感器網(wǎng)絡(luò)應(yīng)用中，通常將節(jié)點(diǎn)撒播在很廣的區(qū)域里，網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)的位置是未知的，事先不能確定，但無(wú)線傳感器網(wǎng)絡(luò)的大多數(shù)應(yīng)用都需要知道網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，才可能獲取到網(wǎng)絡(luò)中事件的發(fā)生位置和信息來(lái)源位置。只有在傳感器節(jié)點(diǎn)自身正確定位后，才能確定傳感器節(jié)點(diǎn)監(jiān)測(cè)到的事件及信息發(fā)生的具體位置[3] 。此外，在設(shè)計(jì)路由協(xié)議時(shí)利用節(jié)點(diǎn)位置信息還可以提高路由效率，為網(wǎng)絡(luò)提供命名空間，向網(wǎng)絡(luò)部署者報(bào)告網(wǎng)絡(luò)的覆蓋質(zhì)量，實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡以及網(wǎng)絡(luò)拓?fù)涞淖耘渲肹4] 。傳感器節(jié)點(diǎn)自身定位就是一種通過估計(jì)至鄰居節(jié)點(diǎn)的距離或鄰居數(shù)目，利用節(jié)點(diǎn)間的信息交換來(lái)確定各節(jié)點(diǎn)自身位置的機(jī)制。對(duì)于WSN來(lái)說，人工部署或?yàn)樗芯W(wǎng)絡(luò)節(jié)點(diǎn)配置GPS裝置都會(huì)受到成本、功耗、拓展性等問題的限制，因此，尋求WSN 自身定位機(jī)制成為許多研究機(jī)構(gòu)和學(xué)者共同探討的問題[4] 。前者需要測(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)位置。Rangebased算法能夠?qū)崿F(xiàn)精確定位，但由于需要在節(jié)點(diǎn)中加入GPS或其它附加的測(cè)距的硬件設(shè)備，在實(shí)際應(yīng)用中所需的成本較高。目前基于距離的定位算法都是利用靜態(tài)的幾何關(guān)系來(lái)確定節(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] 。動(dòng)態(tài)算法的研究是最近興起的一個(gè)熱點(diǎn)，理論還不完善，有別于靜態(tài)算法所涉及的都是固定節(jié)點(diǎn)，其主要是討論對(duì)傳感網(wǎng)中移動(dòng)節(jié)點(diǎn)定位的方法[14] ，包括待測(cè)節(jié)點(diǎn)的運(yùn)動(dòng)和信標(biāo)節(jié)點(diǎn)的運(yùn)動(dòng)。雖然節(jié)點(diǎn)的移動(dòng)性使定位過程復(fù)雜化，但是利用節(jié)點(diǎn)的移動(dòng)性可提高定位精度，減少定位代價(jià)。國(guó)內(nèi)外學(xué)者對(duì)定位問題進(jìn)行了大量研究，提出了幾種比較典型的定位算法[17] 。而在無(wú)線傳感器網(wǎng)絡(luò)中引入移動(dòng)節(jié)點(diǎn)，可以增強(qiáng)其功能。文獻(xiàn)[20] 提到利用移動(dòng)參考節(jié)點(diǎn)和RSSI(接收信號(hào)強(qiáng)度指示)方法對(duì)未知節(jié)點(diǎn)進(jìn)行定位，但是在現(xiàn)實(shí)環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得RSSI技術(shù)在實(shí)際應(yīng)用中仍然存在困難。免測(cè)距的定位算法不需要測(cè)量節(jié)點(diǎn)間的距離，而是利用距離矢量路由、網(wǎng)絡(luò)連通情況或者GPS定位等思想提出的一種分布式定位方法，無(wú)需測(cè)距，這無(wú)疑降低了組網(wǎng)成本。因此如何提高這種免測(cè)距定位算法的精度也成為了一個(gè)研究的熱點(diǎn)方向。 國(guó)內(nèi)外研究現(xiàn)狀基于移動(dòng)信標(biāo)的定位算法是近年來(lái)的研究熱點(diǎn)。而信標(biāo)節(jié)點(diǎn)的造價(jià)數(shù)倍甚至十幾倍于普通節(jié)點(diǎn)，所以其定位成本較高。所以移動(dòng)信標(biāo)的定位算法近來(lái)成為新的研究熱點(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ī)劃。而質(zhì)心定位算法及DVHop定位算法因?yàn)闊o(wú)需測(cè)距有著更多的優(yōu)勢(shì)也得到更多的研究。典型的無(wú)需測(cè)距的定位算法有DVHop定位算法，APIT定位算法、質(zhì)心定位算法、Amorphous定位算法等，它們所需的網(wǎng)絡(luò)模型都是由參考節(jié)點(diǎn)和未知位置的節(jié)點(diǎn)組成。它可以在移動(dòng)的過程中實(shí)時(shí)獲得其當(dāng)前的位置信息。國(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ì)心法來(lái)計(jì)算待定位節(jié)點(diǎn)位置，文獻(xiàn)[26] 不需要復(fù)雜的測(cè)距技術(shù)，而是通過信標(biāo)的不斷運(yùn)動(dòng)并利用幾何限制關(guān)系來(lái)計(jì)算待定位節(jié)點(diǎn)位置。其定位的主要思想是：當(dāng)移動(dòng)信標(biāo)在定位區(qū)域內(nèi)移動(dòng)時(shí)，移動(dòng)到若干個(gè)新位置，立即在該位置補(bǔ)充一個(gè)普通節(jié)點(diǎn)。它們就等同于信標(biāo)。引入移動(dòng)信標(biāo)的優(yōu)勢(shì)是即使只有一個(gè)信標(biāo)也可以實(shí)現(xiàn)對(duì)未知節(jié)點(diǎn)的定位。對(duì)于移動(dòng)信標(biāo)的移動(dòng)路徑的規(guī)劃也是一個(gè)重要的問題，本文進(jìn)行了初步的研究。故研究信標(biāo)的移動(dòng)路徑規(guī)劃，使網(wǎng)絡(luò)中的節(jié)點(diǎn)以最小的代價(jià)獲得足夠多用于自身定位的信息成為一個(gè)重要的研究?jī)?nèi)容。這樣的算法顯然不能最大限度的節(jié)約節(jié)點(diǎn)的能耗，對(duì)于嚴(yán)格要求能源的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)來(lái)說，必然需要更為優(yōu)化及適用于當(dāng)前網(wǎng)絡(luò)的路徑規(guī)劃算法來(lái)使節(jié)點(diǎn)移動(dòng)路徑盡可以少，減少?gòu)V播的信息來(lái)減少網(wǎng)絡(luò)節(jié)點(diǎn)的通信消耗。而國(guó)外有根據(jù)網(wǎng)絡(luò)的聯(lián)通狀況來(lái)進(jìn)行路徑規(guī)劃的動(dòng)態(tài)算法，文獻(xiàn)[28] 提出幾條最優(yōu)路徑的選擇原則，本文主要進(jìn)行動(dòng)態(tài)路徑優(yōu)化研究。研究的內(nèi)容主要如下：分析歸納常用的無(wú)需測(cè)距的定位算法和基于信標(biāo)的定位算法，研究基于信標(biāo)的定位算法的定位機(jī)制，研究利用移動(dòng)信標(biāo)的信息來(lái)進(jìn)行定位計(jì)算。并研究移動(dòng)信標(biāo)的動(dòng)態(tài)選擇算法來(lái)選擇能獲得最大計(jì)算精度的移動(dòng)信標(biāo)節(jié)點(diǎn)進(jìn)行定位計(jì)算。結(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)路徑，提高算法的定位精度，減少算法定位過程的通信開銷，提高算法的效率。通過對(duì)國(guó)內(nèi)外相關(guān)領(lǐng)域的研究現(xiàn)狀進(jìn)行探討，確立傳感器網(wǎng)絡(luò)定位算法的研究的方向。第3章 研究基于移動(dòng)信標(biāo)的無(wú)線傳感器網(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)模型下的定位精度。第5章 在OMNeT++仿真平臺(tái)上進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)算法的仿真，設(shè)計(jì)移動(dòng)信標(biāo)節(jié)點(diǎn)的模型和移動(dòng)模型，并通過仿真論證優(yōu)化路徑對(duì)定位算法的影響。不基于信標(biāo)節(jié)點(diǎn)的定位方法屬于相對(duì)定位，基于信標(biāo)的定位算法可以得出未知節(jié)點(diǎn)的絕對(duì)坐標(biāo)。基于信標(biāo)節(jié)點(diǎn)的定位算法在研究集中在移動(dòng)信標(biāo)的選擇、移動(dòng)路徑、定位計(jì)算方法及移動(dòng)節(jié)點(diǎn)的研究。構(gòu)建無(wú)線傳感器網(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)無(wú)線通信：由于監(jiān)測(cè)區(qū)域的特殊性，不一定存在有線網(wǎng)絡(luò)，例如：Internet、有線局域網(wǎng)等，故網(wǎng)關(guān)具有把采集的環(huán)境信息無(wú)線傳輸?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è)定。匯聚節(jié)點(diǎn)的處理器采用ARM9 S3C2410，它還包括GPRS模塊，無(wú)線射頻模塊，網(wǎng)絡(luò)接口等，它的功能主要是接收附近所有傳感器節(jié)點(diǎn)發(fā)送過來(lái)的數(shù)據(jù)，并且通過Internet或者GPRS模塊上傳到上層監(jiān)控軟件。圖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所示。為了實(shí)驗(yàn)方便，節(jié)點(diǎn)集成了DS18B20溫度傳感器，TSL2561光強(qiáng)度傳感器。圖22傳感器網(wǎng)絡(luò)節(jié)點(diǎn)Fig. 22 Sensor Network Nodes 黎大鵬在文獻(xiàn)[29] 中研究了基于信標(biāo)節(jié)點(diǎn)動(dòng)態(tài)調(diào)整的移動(dòng)節(jié)點(diǎn)的定位算法。文章分別從嵌入式硬件平臺(tái)的硬件設(shè)計(jì)，移動(dòng)節(jié)點(diǎn)定位算法，以及定位系統(tǒng)的程序設(shè)計(jì)與實(shí)現(xiàn)三方面來(lái)對(duì)該系統(tǒng)進(jìn)行研究。仿真證明，相對(duì)于MCL算法，基于VWMC的傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位算法提高了移動(dòng)節(jié)點(diǎn)定位的精度和效率。相對(duì)定位通常是以網(wǎng)絡(luò)中部分節(jié)點(diǎn)為參考，建立整個(gè)網(wǎng)絡(luò)的相對(duì)坐標(biāo)系統(tǒng)。但研究發(fā)現(xiàn)，在相對(duì)定位的基礎(chǔ)上也能夠?qū)崿F(xiàn)部分路由協(xié)議，尤其是基于地理位置的路由(georouting)，而且相對(duì)定位不需要信標(biāo)節(jié)點(diǎn)。典型的無(wú)信標(biāo)節(jié)點(diǎn)的定位算法包含SPA[30] 、SDGPS[31] 、AFL[32] 等定位算法。首先根據(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)。SDGPSN算法在SPA算法的基礎(chǔ)上，提出了基于聚類的定位思想。這些節(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)系。然后相鄰的節(jié)點(diǎn)域依靠?jī)蓚€(gè)域的共同邊際節(jié)點(diǎn)的相關(guān)坐標(biāo)信息，以主節(jié)點(diǎn)ID較小的局部坐標(biāo)系為參照，進(jìn)行相鄰局部坐標(biāo)系間的坐標(biāo)轉(zhuǎn)換，直至建立一個(gè)全局坐標(biāo)系。AFL算法是完全分布式的節(jié)點(diǎn)定位方法。在給定一個(gè)未知坐標(biāo)的節(jié)點(diǎn)集合和一種節(jié)點(diǎn)可以估測(cè)它到其鄰居節(jié)點(diǎn)距離機(jī)制的條件下，通過局部節(jié)點(diǎn)間的通信決定每個(gè)節(jié)點(diǎn)的位置坐標(biāo)。這種定位算法需要預(yù)先定位信標(biāo)節(jié)點(diǎn)，否則無(wú)法正常運(yùn)行，另外為了減小定位誤差，信標(biāo)節(jié)點(diǎn)的數(shù)目還須足夠多。為了解決基于信標(biāo)節(jié)點(diǎn)的定位算法對(duì)信標(biāo)節(jié)點(diǎn)的密度的依賴，近年來(lái)許多學(xué)者進(jìn)行了移動(dòng)信標(biāo)節(jié)點(diǎn)定位算法的研究，通過在引入移動(dòng)信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中按預(yù)定軌跡漫游并廣播自己的位置分組在構(gòu)成虛擬信標(biāo)節(jié)點(diǎn)，可以大大減少信標(biāo)節(jié)點(diǎn)的投入。所以基于移動(dòng)信標(biāo)節(jié)點(diǎn)的定位算法成為近年來(lái)研究的一個(gè)熱點(diǎn)。傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)中節(jié)點(diǎn)有可能和多于3個(gè)的不同信標(biāo)相連。極大似然估計(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)。三邊測(cè)量法是通過 RSSI值得出未知節(jié)點(diǎn)到 3 個(gè)信標(biāo)的距離，通過這3個(gè)距離值計(jì)算出未知節(jié)點(diǎn)的位置。圖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ū)域。有些文章提出了以區(qū)域的質(zhì)點(diǎn)作為節(jié)點(diǎn)的位置，這種方法也不好，節(jié)點(diǎn)定位的誤差會(huì)隨著相交區(qū)域的增大而大大地提高。三角測(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)。同理對(duì)A，B，ADB和B，C，BDC分別確定相應(yīng)的圓心、半徑r圓心和半徑r3。 常用的Rangebase節(jié)點(diǎn)定位算法根據(jù)定位過程中是否測(cè)量實(shí)際節(jié)點(diǎn)間的距離，定位算法可分為：基于距離(RangeBased)的定位算法和距離無(wú)關(guān)(RangeFree)的定位算法[34] ?；谛盘?hào)強(qiáng)度（RSSI）定位RSSI(Received Signal Strength Indicator)是接收到的信號(hào)強(qiáng)度指示器，是一種利用信號(hào)衰減推測(cè)距離的測(cè)距技術(shù)[36]。目前，WSN網(wǎng)絡(luò)中無(wú)線通信芯片主要有兩種：CC1000和CC2420。采用的是OQPSK調(diào)制方式，數(shù)據(jù)速率在250kbit/s，具有較高的抗干擾能力。它是通過A/D轉(zhuǎn)換器轉(zhuǎn)換而來(lái)的，芯片不同，RSSI的轉(zhuǎn)換方式也是不同的。（）式是由（），（），（）聯(lián)合而得的，表明在當(dāng)前發(fā)射功率下，發(fā)送到最遠(yuǎn)的距離處，接收到的最大RSSI值，若超過該值的一定范圍，認(rèn)為節(jié)點(diǎn)間通信不合理，丟棄該數(shù)據(jù)包。本文采用的射頻芯片是CC2420，它相對(duì)于CC1000，使用的范圍更廣。最常用的RSSI有三種：最優(yōu)模型、線性模型和理論模型。最簡(jiǎn)單的RSSI模型就是線性模型，它使用一對(duì)參數(shù)a和ｂ估計(jì)節(jié)點(diǎn)之間的距離，如式()。因?yàn)樾盘?hào)強(qiáng)度和距離之間并不是簡(jiǎn)單的線性關(guān)系，因此，線性模型和理論模型之間還有一定的誤差。 （） （） （） 大多數(shù)情況下，RSSI的測(cè)距采用自由空間模型，它是理論模型的一種。收發(fā)器之間各種各樣的阻礙影響能量的損失，從而直接影響接收器接收