【正文】 con, study the positioning mechanism of localization 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。傳感器網(wǎng)絡(luò)節(jié)點(diǎn)在部署時(shí)往往是不可控制的，比如在大型的無線傳感器網(wǎng)絡(luò)應(yīng)用中，通常將節(jié)點(diǎn)撒播在很廣的區(qū)域里，網(wǎng)絡(luò)中大部分的節(jié)點(diǎn)的位置是未知的，事先不能確定，但無線傳感器網(wǎng)絡(luò)的大多數(shù)應(yīng)用都需要知道網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息，才可能獲取到網(wǎng)絡(luò)中事件的發(fā)生位置和信息來源位置。此外，在設(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] 。對于WSN來說，人工部署或?yàn)樗芯W(wǎng)絡(luò)節(jié)點(diǎn)配置GPS裝置都會(huì)受到成本、功耗、拓展性等問題的限制，因此，尋求WSN 自身定位機(jī)制成為許多研究機(jī)構(gòu)和學(xué)者共同探討的問題[4] 。Rangebased算法能夠?qū)崿F(xiàn)精確定位，但由于需要在節(jié)點(diǎn)中加入GPS或其它附加的測距的硬件設(shè)備，在實(shí)際應(yīng)用中所需的成本較高。動(dòng)態(tài)算法的研究是最近興起的一個(gè)熱點(diǎn)，理論還不完善，有別于靜態(tài)算法所涉及的都是固定節(jié)點(diǎn)，其主要是討論對傳感網(wǎng)中移動(dòng)節(jié)點(diǎn)定位的方法[14] ，包括待測節(jié)點(diǎn)的運(yùn)動(dòng)和信標(biāo)節(jié)點(diǎn)的運(yùn)動(dòng)。國內(nèi)外學(xué)者對定位問題進(jìn)行了大量研究，提出了幾種比較典型的定位算法[17] 。文獻(xiàn)[20] 提到利用移動(dòng)參考節(jié)點(diǎn)和RSSI(接收信號強(qiáng)度指示)方法對未知節(jié)點(diǎn)進(jìn)行定位，但是在現(xiàn)實(shí)環(huán)境中，溫度、障礙物、傳播模式等條件往往都是變化的，使得RSSI技術(shù)在實(shí)際應(yīng)用中仍然存在困難。因此如何提高這種免測距定位算法的精度也成為了一個(gè)研究的熱點(diǎn)方向。而信標(biāo)節(jié)點(diǎn)的造價(jià)數(shù)倍甚至十幾倍于普通節(jié)點(diǎn)，所以其定位成本較高。而質(zhì)心定位算法及DVHop定位算法因?yàn)闊o需測距有著更多的優(yōu)勢也得到更多的研究。它可以在移動(dòng)的過程中實(shí)時(shí)獲得其當(dāng)前的位置信息。其定位的主要思想是：當(dāng)移動(dòng)信標(biāo)在定位區(qū)域內(nèi)移動(dòng)時(shí)，移動(dòng)到若干個(gè)新位置，立即在該位置補(bǔ)充一個(gè)普通節(jié)點(diǎn)。引入移動(dòng)信標(biāo)的優(yōu)勢是即使只有一個(gè)信標(biāo)也可以實(shí)現(xiàn)對未知節(jié)點(diǎn)的定位。故研究信標(biāo)的移動(dòng)路徑規(guī)劃，使網(wǎng)絡(luò)中的節(jié)點(diǎn)以最小的代價(jià)獲得足夠多用于自身定位的信息成為一個(gè)重要的研究內(nèi)容。而國外有根據(jù)網(wǎng)絡(luò)的聯(lián)通狀況來進(jìn)行路徑規(guī)劃的動(dòng)態(tài)算法，文獻(xiàn)[28] 提出幾條最優(yōu)路徑的選擇原則，本文主要進(jìn)行動(dòng)態(tài)路徑優(yōu)化研究。并研究移動(dòng)信標(biāo)的動(dòng)態(tài)選擇算法來選擇能獲得最大計(jì)算精度的移動(dòng)信標(biāo)節(jié)點(diǎn)進(jìn)行定位計(jì)算。通過對國內(nèi)外相關(guān)領(lǐng)域的研究現(xiàn)狀進(jìn)行探討，確立傳感器網(wǎng)絡(luò)定位算法的研究的方向。第5章 在OMNeT++仿真平臺(tái)上進(jìn)行無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)算法的仿真，設(shè)計(jì)移動(dòng)信標(biāo)節(jié)點(diǎn)的模型和移動(dòng)模型，并通過仿真論證優(yōu)化路徑對定位算法的影響。基于信標(biāo)節(jié)點(diǎn)的定位算法在研究集中在移動(dòng)信標(biāo)的選擇、移動(dòng)路徑、定位計(jì)算方法及移動(dòng)節(jié)點(diǎn)的研究。匯聚節(jié)點(diǎn)的處理器采用ARM9 S3C2410，它還包括GPRS模塊，無線射頻模塊，網(wǎng)絡(luò)接口等，它的功能主要是接收附近所有傳感器節(jié)點(diǎn)發(fā)送過來的數(shù)據(jù)，并且通過Internet或者GPRS模塊上傳到上層監(jiān)控軟件。為了實(shí)驗(yàn)方便，節(jié)點(diǎn)集成了DS18B20溫度傳感器，TSL2561光強(qiáng)度傳感器。文章分別從嵌入式硬件平臺(tái)的硬件設(shè)計(jì)，移動(dòng)節(jié)點(diǎn)定位算法，以及定位系統(tǒng)的程序設(shè)計(jì)與實(shí)現(xiàn)三方面來對該系統(tǒng)進(jìn)行研究。相對定位通常是以網(wǎng)絡(luò)中部分節(jié)點(diǎn)為參考，建立整個(gè)網(wǎng)絡(luò)的相對坐標(biāo)系統(tǒng)。典型的無信標(biāo)節(jié)點(diǎn)的定位算法包含SPA[30] 、SDGPS[31] 、AFL[32] 等定位算法。SDGPSN算法在SPA算法的基礎(chǔ)上，提出了基于聚類的定位思想。然后相鄰的節(jié)點(diǎn)域依靠兩個(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)系。在給定一個(gè)未知坐標(biāo)的節(jié)點(diǎn)集合和一種節(jié)點(diǎn)可以估測它到其鄰居節(jié)點(diǎn)距離機(jī)制的條件下，通過局部節(jié)點(diǎn)間的通信決定每個(gè)節(jié)點(diǎn)的位置坐標(biāo)。為了解決基于信標(biāo)節(jié)點(diǎn)的定位算法對信標(biāo)節(jié)點(diǎn)的密度的依賴，近年來許多學(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)的投入。傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位系統(tǒng)中節(jié)點(diǎn)有可能和多于3個(gè)的不同信標(biāo)相連。三邊測量法是通過 RSSI值得出未知節(jié)點(diǎn)到 3 個(gè)信標(biāo)的距離，通過這3個(gè)距離值計(jì)算出未知節(jié)點(diǎn)的位置。有些文章提出了以區(qū)域的質(zhì)點(diǎn)作為節(jié)點(diǎn)的位置，這種方法也不好，節(jié)點(diǎn)定位的誤差會(huì)隨著相交區(qū)域的增大而大大地提高。同理對A，B，ADB和B，C，BDC分別確定相應(yīng)的圓心、半徑r圓心和半徑r3?；谛盘枏?qiáng)度（RSSI）定位RSSI(Received Signal Strength Indicator)是接收到的信號強(qiáng)度指示器，是一種利用信號衰減推測距離的測距技術(shù)[36]。采用的是OQPSK調(diào)制方式，數(shù)據(jù)速率在250kbit/s，具有較高的抗干擾能力。（）式是由（），（），（）聯(lián)合而得的，表明在當(dāng)前發(fā)射功率下，發(fā)送到最遠(yuǎn)的距離處，接收到的最大RSSI值，若超過該值的一定范圍，認(rèn)為節(jié)點(diǎn)間通信不合理，丟棄該數(shù)據(jù)包。最常用的RSSI有三種：最優(yōu)模型、線性模型和理論模型。因?yàn)樾盘枏?qiáng)度和距離之間并不是簡單的線性關(guān)系，因此，線性模型和理論模型之間還有一定的誤差。收發(fā)器之間各種各樣的阻礙影響能量的損失，從而直接影響接收器接收信號的對數(shù)分布[37]。基于這個(gè)模型，距離估算為： （）總的來說，僅依靠RSSI方法的定位系統(tǒng)，應(yīng)用在實(shí)時(shí)系統(tǒng)定位時(shí)非常方便。計(jì)算公式如式（）所示： D=V1*V2*(T2T1)/(V1V2) （）無需測距的定位技術(shù)不需要額外的硬件，與基于測距的定位算法相比，具有成本低、功耗小、抗測量噪聲能力強(qiáng)等優(yōu)勢特點(diǎn)，并能獲得一定的定位精度，因此有許多學(xué)者進(jìn)行了大量的研究。并分析了這三種算法的特點(diǎn)。這個(gè)策略可以保證絕大多數(shù)節(jié)點(diǎn)從最近的信標(biāo)接收平均每跳距離。由于一個(gè)未知節(jié)點(diǎn)只能通過一條路徑得到跳數(shù)，所以它需要通過每跳平均距離來計(jì)算自身的位置，這樣導(dǎo)致計(jì)算出位置的誤差量很大。首先，信標(biāo)廣播包括位置信息以及開始位為1的標(biāo)志的數(shù)據(jù)包，當(dāng)信號傳輸?shù)搅硪粋€(gè)節(jié)點(diǎn)，跳幀的數(shù)量自動(dòng)加一，所以每個(gè)節(jié)點(diǎn)將可以計(jì)算出離信標(biāo)的距離，信標(biāo)接收到另一信標(biāo)的信號后可以計(jì)算平均每跳的距離。然后它計(jì)算出到LLL3三點(diǎn)的距離，AL1=、AL2=AL3=7*3=21。所以經(jīng)過三邊測量法后，計(jì)算出的位置和實(shí)際上的位置差別很大[11] 。 （）與DVHop不同的是，它假設(shè)網(wǎng)絡(luò)平均連通度nlocal已知，使用Kleinrock and Slivers Formula在網(wǎng)絡(luò)部署前離線計(jì)算平均每跳距離，如（）式，式中r表示節(jié)點(diǎn)的通信半徑，nlocal表示網(wǎng)絡(luò)平均連通度，即網(wǎng)絡(luò)中節(jié)點(diǎn)的平均鄰居節(jié)點(diǎn)數(shù)。如圖26所示。這些算法的優(yōu)缺點(diǎn)為基于移動(dòng)信標(biāo)優(yōu)化路徑的傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法的提出提供良好的基礎(chǔ)。解決傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位精度低，定位效率低等問題。最后通過仿真證明此算法可以提高定位精度，降低定位成本，提高了定位的效率。通常無線傳感器節(jié)點(diǎn)都被隨機(jī)地布置在不同的區(qū)域中，由于傳感器節(jié)點(diǎn)受成本，能量和體積的限制，隨機(jī)布放的節(jié)點(diǎn)無法預(yù)先知道自身的位置，他們只能根據(jù)其它已知位置的節(jié)點(diǎn)，按照某種定位的機(jī)制來確定自身的位置。無需測距的定位算法主要有質(zhì)心算法、DVHop算法，Amorphous算法、APIT算法等。該算法在DVHop定位算法的基礎(chǔ)上，利用一個(gè)帶有GPS定位裝置的移動(dòng)信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中按預(yù)定的路徑移動(dòng)并不斷的廣播自己的位置信息，形成多個(gè)虛擬信標(biāo)，未知節(jié)點(diǎn)記錄到每個(gè)虛擬信標(biāo)的跳數(shù)，并將移動(dòng)信標(biāo)廣播的平均跳距離通過加權(quán)處理來重新計(jì)算適用于其所在區(qū)域的網(wǎng)絡(luò)平均跳距離，再與跳數(shù)相乘得出其與各虛擬信標(biāo)的距離，最后利用改進(jìn)的三邊測量法計(jì)算其位置信息，實(shí)現(xiàn)節(jié)點(diǎn)精確定位。該算法的基本思想是將未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離用網(wǎng)絡(luò)中節(jié)點(diǎn)平均每跳距離和到信標(biāo)節(jié)點(diǎn)間的跳數(shù)的乘積來計(jì)算，再使用三邊測量法來得出節(jié)點(diǎn)的位置信息。接收節(jié)點(diǎn)記錄具有到每個(gè)信標(biāo)節(jié)點(diǎn)的最小跳數(shù)，忽略來自同一個(gè)信標(biāo)節(jié)點(diǎn)的較大跳數(shù)的分組。每個(gè)信標(biāo)節(jié)點(diǎn)根據(jù)第一個(gè)階段中記錄的其它信標(biāo)節(jié)點(diǎn)的位置信息和相距跳數(shù)，利用式()估算平均每跳的實(shí)際距離： ()其中(xi+yi)、(xj+yj)是信標(biāo)節(jié)點(diǎn)i、j的坐標(biāo)，hj是信標(biāo)節(jié)點(diǎn)i與j(j≠i)之間的跳段數(shù)。 圖31 DVHop定位算法舉例 DVHop localization algorithm DVHop定位算法誤差分析1)、 DVHop定位算法的假設(shè)在DVHop定位算法中，未知節(jié)點(diǎn)在通信范圍內(nèi)獲得的信標(biāo)節(jié)點(diǎn)數(shù)量不多，但通過多跳傳播可以獲得通信范圍外的多個(gè)信標(biāo)節(jié)點(diǎn)的估計(jì)距離，利用大量的信息獲得該節(jié)點(diǎn)的位置，在網(wǎng)絡(luò)平均連通度為8，信標(biāo)比例為10%時(shí)，算法的定位誤差大約是節(jié)點(diǎn)射頻通信距離的1/3左右[10] 。在Matlab平臺(tái)上建立實(shí)驗(yàn)仿真環(huán)境，在一個(gè)邊長為50m的正方形區(qū)域中分布有100個(gè)未知節(jié)點(diǎn)，射頻通信距離為10m。圖32信標(biāo)節(jié)點(diǎn)個(gè)數(shù)對定位誤差的影響 beacon nodes number affecting從以上分析可知，為了提高定位精度，需要增加信標(biāo)節(jié)點(diǎn)，但信標(biāo)節(jié)點(diǎn)造價(jià)高。目前應(yīng)用于無線傳感器網(wǎng)絡(luò)的移動(dòng)模型有S型、RWP(Random Way Point)模型和GaussMarkov模型等。a是方向隨機(jī)調(diào)節(jié)參數(shù)，取值為0到1(0=a=1)，vmean, dmean為平均速度和平均運(yùn)動(dòng)方向,，代表高斯隨機(jī)變量。每個(gè)節(jié)點(diǎn)接收到定位信息后，將其中的跳數(shù)值加1后繼續(xù)廣播。加權(quán)值法計(jì)算平均跳距離為了更準(zhǔn)確的計(jì)算出估計(jì)的平均跳距離值，本文引入權(quán)值的概念，運(yùn)用加權(quán)值對平均跳距離進(jìn)行校正是基于網(wǎng)絡(luò)并非完全的均勻分布，各個(gè)節(jié)點(diǎn)接收到多個(gè)虛擬節(jié)點(diǎn)的平均跳距離值，越是靠近未知節(jié)點(diǎn)其平均跳距離值更能反映出未知節(jié)點(diǎn)所在的網(wǎng)絡(luò)區(qū)域的情況，對其平均跳距離的影響也越大，所以應(yīng)當(dāng)占有更大的權(quán)值，這樣比只計(jì)算平均值更接近真實(shí)值，計(jì)算出來的未知節(jié)點(diǎn)位置更精確。 仿真分析為了驗(yàn)證算法的性能，將提出的算法在OMNeT++平臺(tái)進(jìn)行仿真，并用MATLAB進(jìn)行實(shí)驗(yàn)數(shù)據(jù)的輔助分析，在OMNeT++平臺(tái)上，將100個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)5050的區(qū)域中，節(jié)點(diǎn)通信半徑為10。圖中所示的關(guān)系是顯然的，隨著時(shí)間的推移，移動(dòng)信標(biāo)在網(wǎng)絡(luò)中移動(dòng)的距離越遠(yuǎn)，廣播的定位信息越多，虛擬信標(biāo)也越多，定位的誤差也隨之減小。最優(yōu)的定位周期的大小由節(jié)點(diǎn)由通信半徑?jīng)Q定，當(dāng)通信半徑越大時(shí)，廣播的周期也應(yīng)相應(yīng)的增大。DVHop是一種經(jīng)典的無需測距的定位算法，具有定位算法簡單，定位精度較高的優(yōu)點(diǎn)，但其定位精度依賴于網(wǎng)絡(luò)連通狀況，對于各向同性的網(wǎng)絡(luò)，可以獲得較適當(dāng)?shù)亩ㄎ痪?，而對于不?guī)則拓?fù)涞木W(wǎng)絡(luò)定位誤差則較大[41] 。針對這種情況，提出了一種基于移動(dòng)信標(biāo)動(dòng)態(tài)選擇的改進(jìn)DVHop定位算法(DSBDVHop)，通過引入移動(dòng)信標(biāo)在網(wǎng)絡(luò)中按預(yù)定軌跡漫游，并在每個(gè)虛擬信標(biāo)節(jié)點(diǎn)的位置單獨(dú)計(jì)算網(wǎng)絡(luò)各部位的平均跳距離后廣播其位置分組，未知節(jié)點(diǎn)記錄到每個(gè)虛擬信標(biāo)的跳數(shù)，動(dòng)態(tài)選擇能獲得最高計(jì)算精度的信標(biāo)節(jié)點(diǎn)來進(jìn)行三邊測量法計(jì)算自己的位置，減少無線傳感器網(wǎng)絡(luò)定位的成本，并且提高了定位精度。在上述的DVHop定位算法的過程中，信標(biāo)節(jié)點(diǎn)會(huì)根據(jù)他接收到的所有信標(biāo)節(jié)點(diǎn)發(fā)來的數(shù)據(jù)包的信息計(jì)算平均每跳距離。如圖36所示的情況中，我們可以看到：當(dāng)某未知節(jié)點(diǎn)N接收到來自其周圍3跳距離內(nèi)的信標(biāo)節(jié)點(diǎn)的定位信息時(shí)，其列表中將有5個(gè)信標(biāo)節(jié)點(diǎn)的位置及跳數(shù)。在定位計(jì)算過程中，當(dāng)這種節(jié)點(diǎn)增多時(shí)，對于定位誤差的影響顯而易見。圖37是兩種組合下的計(jì)算情況的示意圖，從圖中我們可以看到，當(dāng)A4和A5這兩個(gè)節(jié)點(diǎn)參與三邊定位計(jì)算時(shí)，其定位的誤差明顯增加。信標(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)以完成定位算法。，該模型可以覆蓋網(wǎng)絡(luò)的大部分區(qū)域，相對于RWP模型，可以避免運(yùn)動(dòng)軌跡的突變和邊緣地帶概率減少的缺點(diǎn)[6]，對硬件的要求也不高。每個(gè)節(jié)點(diǎn)接