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