基于UAV的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法*

高美鳳，尹持俊

(江南大學(xué)輕工過程先進控制教育部重點實驗室，江蘇 無錫214122)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks，WSN)是由大量傳感器節(jié)點分布在監(jiān)控區(qū)域組成的網(wǎng)絡(luò)，具有感知、計算和通信能力[1]。在無線傳感器網(wǎng)絡(luò)應(yīng)用中，確定了位置信息后的數(shù)據(jù)信息才會有意義，因此定位問題是無線傳感器網(wǎng)絡(luò)研究的關(guān)鍵問題之一[2]。無人機(Unmanned Aerial Vehicle，UAV)是一種自動駕駛、可重復(fù)使用、可操控并可以攜帶一定設(shè)備完成多種任務(wù)的航空器[3]。隨著無人機的應(yīng)用逐漸從軍事領(lǐng)域擴展到民用領(lǐng)域，無人機的研究備受關(guān)注，無人機在WSN領(lǐng)域的應(yīng)用也應(yīng)運而生。由于其低成本，不受空間約束和使用靈活的優(yōu)勢，無人機在WSN節(jié)點定位也有很好的發(fā)展前景[4]。目前，在無線傳感器網(wǎng)絡(luò)節(jié)點定位中，根據(jù)是否需要測量節(jié)點間的距離分為兩類:一類是需要測距的定位算法，測距方法有RSSI、TOA、TDOA等，基于此類測距方法的定位算法有極大似然估計法、三邊測量法、三角測量法[5]；另一類是不需要測距的定位算法，有質(zhì)心算法、DV-hop算法、APIT算法等[6]。在無需測距的定位算法中，基于RSSI值的加權(quán)質(zhì)心定位算法(RSSI-Weighted Centroid Localization，R-WCL)直接采用RSSI值作為加權(quán)質(zhì)心定位算法的權(quán)值，計算過程較為簡單，容易實現(xiàn)[7]。文獻[8]提出基于RSSI比值的加權(quán)質(zhì)心定位算法(RSSI-RSSI-Weighted Centroid Localization，RRWCL)，將未知節(jié)點接收到的各鄰居錨節(jié)點的信號強度比值作為每個錨節(jié)點的權(quán)值，在一定程度上提高了定位精度。文獻[9]提出改進的基于RSSI極大似然估計定位算法(Taylor-Maximum Likelihood Estimation，T-MLE)，使用基于泰勒級數(shù)展開的最小二乘法求解方程組，改善了基于RSSI極大似然估計定位算法的穩(wěn)定性，提高了定位精度。文獻[10]以極大似然定位算法解得坐標后的誤差倒數(shù)作為權(quán)值的加權(quán)質(zhì)心定位算法(Error-Weighted Centroid Localization，E-WCL)，具有定位精度高等優(yōu)勢。另外在上述算法中，為了達到較好的定位結(jié)果，需要在網(wǎng)絡(luò)內(nèi)布置大量的錨節(jié)點，定位成本較高，限制了算法在無線傳感器網(wǎng)絡(luò)中的應(yīng)用。文獻[11]提出基于單個移動錨節(jié)點輔助的加權(quán)質(zhì)心定位算法，該算法采用單個移動錨節(jié)點沿著既定的軌跡在監(jiān)測區(qū)域移動，并在規(guī)定位置廣播數(shù)據(jù)包，降低了定位成本。但是當移動錨節(jié)點無法在未知節(jié)點所在平面移動時，利用無人機充當移動錨節(jié)點則是一個很好的選擇。

針對在監(jiān)控區(qū)域內(nèi)，移動錨節(jié)點無法處于未知節(jié)點平面的情況，本文采用無人機作為移動錨節(jié)點，以既定的航跡在整個無線傳感器網(wǎng)絡(luò)的監(jiān)測區(qū)域飛行，在降低定位成本的情況下，對加權(quán)質(zhì)心定位算法進行了改進，提出了基于信號強度比值并結(jié)合指數(shù)函數(shù)作為權(quán)值的加權(quán)質(zhì)心定位算法(Exponent RSSIRSSI-Weighted Centroid Localization，ERR-WCL)。最后，對T-MLE、RR-WCL、E-WCL和ERR-WCL四種算法進行了仿真對比實驗，仿真結(jié)果表明本文所提出的ERR-WCL算法利用無人機作為移動錨節(jié)點，能有效地降低未知節(jié)點的定位誤差。

1 基于UAV的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法

1.1 無人機飛行航跡

無人機在網(wǎng)絡(luò)內(nèi)按照一定的時間間隔廣播信息包，當未知節(jié)點收集到多個航跡點位置信息后，利用定位算法對自身進行位置估計。常用的無人機航跡規(guī)劃方法有四種，其中Dimitrios提出了Scan、Double Scan、Hilbert三種航跡規(guī)劃方法[12]，文獻[13]提出正三角形航跡，如圖1所示。Scan的飛行航跡長度較短，但共線問題較為嚴重。Double Scan算法很好地解決了Scan算法的共線問題，但是飛行航跡長度相比增加了一倍，而且區(qū)域邊緣節(jié)點的定位精度較低。Hilebert算法很好地解決了上述問題，但其飛行航跡長度比Scan算法多很多。文獻[13]分析證明，當三個錨節(jié)點對稱放置時，可以達到最優(yōu)部署。也就是為了獲得更精確的未知節(jié)點位置信息，可以將三個錨節(jié)點放置成一個等邊三角形。這種正三角形的飛行廣播方式，最大程度的保證了監(jiān)測區(qū)域內(nèi)的未知節(jié)點處于至少三個航跡點構(gòu)成的多邊形內(nèi)部，進而達到較好的定位結(jié)果。

圖1 四種航跡規(guī)劃方法示意圖

本文根據(jù)正三角形航跡思想，采用無人機沿正三角形的飛行航跡遍歷整個傳感器網(wǎng)絡(luò)區(qū)域，設(shè)計了無人機立體正三角形航跡如圖2所示(*表示無人機的航跡點，即虛擬錨節(jié)點；→表示無人機飛行航跡；o表示未知節(jié)點)。

圖2 無人機正三角形航跡圖

在飛行的過程中，無人機在每個三角形頂點停留一定時間，感知周圍鄰近的未知節(jié)點并廣播數(shù)據(jù)包，接收到數(shù)據(jù)包的未知節(jié)點將該虛擬錨節(jié)點標記為鄰居虛擬錨節(jié)點。無人機廣播的數(shù)據(jù)包需包含有自身移動位置坐標、標號和信號強度。

1.2 改進加權(quán)質(zhì)心定位算法權(quán)值

加權(quán)質(zhì)心算法的主要思想是利用錨節(jié)點和未知節(jié)點之間的接收信號強度指示值作為權(quán)值，利用權(quán)值來體現(xiàn)錨節(jié)點對質(zhì)心位置的影響程度。加權(quán)質(zhì)心定位算法的計算公式為:

式中:P(x，y)為未知節(jié)點估計位置；B i(x，y)為錨節(jié)點i的位置坐標；N為未知節(jié)點的鄰居錨節(jié)點數(shù)；w i為鄰居錨節(jié)點i對未知節(jié)點的權(quán)重值，其通?？梢允俏粗?jié)點和錨節(jié)點間距離的函數(shù)、或者是未知節(jié)點接收到的RSSI的函數(shù)。

在無線傳感器網(wǎng)絡(luò)中，環(huán)境對未知節(jié)點接收到的RSSI值是有一定影響的。文獻[8]提出了RRWCL算法采用接收信號強度比值作為加權(quán)值，從而抑制環(huán)境對未知節(jié)點接收到的RSSI值的差異影響。依據(jù)文獻[8]的思想，本文提出了ERR-WCL算法，該算法在采用信號強度比值作為權(quán)值的同時，為了擴大個體信號強度值差異對節(jié)點間實際位置坐標的影響程度，結(jié)合以e為底的指數(shù)函數(shù)y＝ex，即自然對數(shù)進行修正，擴大個體信號強度值差異影響，對未知節(jié)點的估計位置進行修正。顯然，當未知節(jié)點接收到的虛擬錨節(jié)點信號強度越強，則該鄰居虛擬錨節(jié)點的坐標對未知節(jié)點的定位結(jié)果影響越大；反之，則影響越小。據(jù)此，首先運用權(quán)重的概念，定義R ji為未知節(jié)點M分別從鄰居虛擬錨節(jié)點B j、B i接收到的信號強度比值:

式中:i＝1，…，N，j＝1，…，N。當無人機發(fā)射功率為0 dBm時，RSSIi為負數(shù)，故RSSIi的絕對值越大，則說明未知節(jié)點離鄰居虛擬錨節(jié)點越遠。

定義式(1)中鄰居錨節(jié)點i對未知節(jié)點的權(quán)重值為

在x>0的情況下，由exp(x)－x恒大于等于1且隨x的增大單調(diào)遞增可知，對于未知節(jié)點M的鄰居虛擬錨節(jié)點B k，k∈[1，N]的權(quán)值始終大于從而擴大了不同鄰居虛擬錨節(jié)點的權(quán)值影響程度，使距離較近的鄰居虛擬錨節(jié)點所占的權(quán)重比例更大，估算的質(zhì)心位置更加趨近于未知節(jié)點的實際位置。

1.3 權(quán)值變化對未知節(jié)點定位坐標的影響分析

當要研究未知節(jié)點到某一鄰居虛擬錨節(jié)點RSSI值變化對該鄰居虛擬錨節(jié)點權(quán)重值的影響時，就要把權(quán)值當變量。

定義鄰居虛擬錨節(jié)點B i(x，y)對最終未知節(jié)點定位結(jié)果的貢獻大小為P i(x，y)，即:

則式(1)則可以表示為:

取權(quán)值作為變量，B i(x，y)為鄰居虛擬錨節(jié)點i的坐標，其為常數(shù)可以忽略，將w i代入式(4)中作為變量，即可得:

這里假定未知節(jié)點接收到鄰居虛擬錨節(jié)點k的信號強度值RSSIk增大，其絕對值減小，推導(dǎo)P k(w k)的變化。在式(6)的分母中，將w k單獨列出，則:

對式(7)中w k求導(dǎo)可得:

即RSSIk增大，其絕對值減小，增大，增大，而P′k(w k)恒大于零，故可得到P k(w k)增大，P k(w k)相對于P(x，y)所占的比例越大，即鄰居虛擬錨節(jié)點k對未知節(jié)點的估計位置坐標貢獻大。反之，鄰居虛擬錨節(jié)點k對未知節(jié)點的估計位置坐標貢獻小。

1.4 基于UAV的節(jié)點定位

當移動錨節(jié)點無法在未知節(jié)點所處平面移動時，可以用無人機來代替移動錨節(jié)點在監(jiān)測區(qū)域飛行，形成許多航跡點(虛擬錨節(jié)點)，以協(xié)助未知節(jié)點實現(xiàn)定位。若未知節(jié)點均在同一高度平面，即處于(x，y，z0)位置，而無人機在另一高度平面飛行，即無人機所處位置為(x，y，z1)，其中z0和z1是已知的。此時，無人機在z1高度飛行過程中，定時發(fā)布位置信息，以形成虛擬錨節(jié)點，同時考慮未知節(jié)點和無人機所處監(jiān)測區(qū)域媒質(zhì)是各向同性且均勻的，則可以將三維空間的定位問題簡化為二維空間的定位。

根據(jù)式(1)、式(2)和式(3)求得未知節(jié)點的橫縱坐標估計值:

式中:

通常用相對平均定位誤差來表示定位效果，即節(jié)點的定位誤差和節(jié)點最大傳播距離的比值，即

式中:m、n、r分別是虛擬錨節(jié)點數(shù)量、節(jié)點總數(shù)量和節(jié)點的通信半徑，P(x，y)r為未知節(jié)點的實際位置的橫縱坐標。

1.5 改進的加權(quán)質(zhì)心定位算法步驟

無人機沿正三角形航跡飛行結(jié)束后，未知節(jié)點根據(jù)記錄的信號強度值和鄰居虛擬錨節(jié)點的位置坐標，用改進的加權(quán)質(zhì)心定位算法ERR-WCL計算未知節(jié)點自身的位置，具體的算法偽代碼如下:

?

2 仿真與分析

2.1 仿真環(huán)境設(shè)置

以室內(nèi)環(huán)境為例，室內(nèi)部署的無線傳感器網(wǎng)絡(luò)節(jié)點，無法通過GPS(Global Positioning System)等方法進行定位[14]。無人機的位置由即時定位與地圖構(gòu)建(Simultaneous Localization and Mapping，SLAM)獲得[15]。為驗證本文所提的ERR-WCL算法的有效性，在Window10操作系統(tǒng)下利用MATLAB R2019a進行仿真分析。仿真環(huán)境的設(shè)置如表1所示。

表1 仿真環(huán)境

2.2 通信半徑的影響分析

無人機初始的坐標為(0，0，3)，且按圖1正三角形航跡飛行，設(shè)置節(jié)點通信半徑r＝5 m。未知節(jié)點與通信半徑內(nèi)的鄰居虛擬錨節(jié)點進行通信，生成鄰居關(guān)系圖如圖3所示(*表示無人機的航跡點位置，即虛擬錨節(jié)點位置，○表示未知節(jié)點位置，－表示將未知節(jié)點與鄰居虛擬錨節(jié)點連接在一起)。

圖3 通信半徑為5 m的鄰居關(guān)系圖

由圖3可以看出，每個未知節(jié)點可以接收5或6個鄰居虛擬錨節(jié)點的位置坐標，且這些位置坐標不都在一條直線上，能夠連接成多邊形進行定位。

圖4 、圖5、圖6和圖7分別是T-MLE、RR-WCL、E-WCL和ERR-WCL算法在通信半徑r＝5 m，未知節(jié)點同分布的定位結(jié)果(○表示未知節(jié)點的實際位置，－表示未知節(jié)點估計位置與實際位置的偏差)。

圖4 T-MLE定位效果圖

圖5 RR-WCL定位效果圖

圖6 E-WCL定位效果圖

圖7 ERR-WCL定位效果圖

對比圖4、圖5、圖6和圖7，根據(jù)未知節(jié)點估計位置到其真實位置連線的長短，可以看出:當通信半徑為5 m時，ERR-WCL算法的定位誤差最小，E-WCL也較小，RR-WCL和T-MLE較大。

相同的仿真環(huán)境下，改變節(jié)點的通信半徑后，節(jié)點的相對平均定位誤差由式(11)計算得出，如圖8所示。

圖8 不同通信半徑下相對平均定位誤差

從圖8中可以看出隨著通信半徑增加，T-MLE的相對平均定位誤差在11.26%~15.33%波動；RRWCL的相對平均定位誤差在10.22%~12.51%波動；E-WCL的相對平均定位誤差在7.63%~11.52%波動；ERR-WCL的相對平均定位誤差在6.81%~9.15%波動。ERR-WCL的定位精度較T-MLE算法提高了4.45%~6.18%，較RR-WCL算法提高了3.36%~3.41%，較E-WCL算法提高了0.82%~2.37%。ERR-WCL算法可以得到較小的定位誤差，定位效果較好。

同時可以看出，當無人機廣播位置不變時，隨著節(jié)點的通信半徑增加，節(jié)點的相對平均定位誤差逐漸減小。這是由于在一定范圍內(nèi)，節(jié)點通信半徑的增大會提高網(wǎng)絡(luò)的連通度，使得未知節(jié)點可以接收的無人機的數(shù)據(jù)包數(shù)量增多，其位置也可以越來越趨近于鄰居虛擬錨節(jié)點位置所構(gòu)成的多邊形中心，從而使得未知節(jié)點的相對平均定位誤差有所降低。

2.3 UAV高度的影響

無人機仍然按正三角形航跡飛行，且設(shè)置通信半徑為定值r＝5 m。未知節(jié)點與通信半徑內(nèi)的鄰居虛擬錨節(jié)點進行通信，無人機在不同飛行高度時，生成鄰居關(guān)系圖分別如圖9、圖10和圖11所示(*表示無人機的航跡點位置，即虛擬錨節(jié)點位置，○表示未知節(jié)點位置，－表示將未知節(jié)點與鄰居虛擬錨節(jié)點連接在一起)。

圖9 飛行高度為0.5 m的鄰居關(guān)系圖

圖10 飛行高度為1.5 m的鄰居關(guān)系圖

由圖9、圖10和圖11可以看出，通信半徑一定時，無人機飛行高度為0.5 m時，未知節(jié)點可以接收7~10個鄰居虛擬錨節(jié)點的位置坐標；飛行高度為1.5 m時，未知節(jié)點可以接收6~9個鄰居虛擬錨節(jié)

圖11 飛行高度為2.5 m的鄰居關(guān)系圖

點的位置坐標；飛行高度為2.5 m時，未知節(jié)點可以接收6或7個鄰居虛擬錨節(jié)點的位置坐標。這是由于節(jié)點的通信半徑固定為5 m，當無人機飛行高度越高，未知節(jié)點周圍的鄰居虛擬錨節(jié)點的數(shù)目就越少。相同的仿真環(huán)境下，改變無人機的飛行高度后，根據(jù)式(11)求節(jié)點的相對平均定位誤差，得到節(jié)點的相對平均定位誤差如圖12所示。

圖12 不同飛行高度的相對平均定位誤差

從圖12中可以看出，隨著無人機的飛行高度增加，T-MLE的相對平均定位誤差在9.98%~14.37%波動；RR-WCL的相對平均定位誤差在9.51%~11.94%波動；E-WCL的相對平均定位誤差在7.99%~11.25%波動；ERR-WCL的相對平均定位誤差在6.45%~7.95%波動。ERR-WCL的定位精度較T-MLE算法提高了3.53%~6.72%，較RR-WCL算法提高了3.06%~4.01%，較E-WCL算法提高了1.54%~4.30%。ERR-WCL算法可以得到較小的定位誤差，定位效果較好。表示無人機可以靈活的在飛行范圍內(nèi)飛行，不受到空間約束，并結(jié)合所提ERR-WCL定位算法可以得到較好的定位結(jié)果。

同時可以看出，當無人機通信半徑不變時，隨著無人機飛行高度的增加，節(jié)點的相對平均定位誤差逐漸增大。這是由于在通信半徑一定的情況下，無人機飛行高度越高，使得未知節(jié)點可以接收的無人機的數(shù)據(jù)包數(shù)量減少，從而使得未知節(jié)點的相對平均定位誤差有所增加。

3 結(jié)束語

加權(quán)質(zhì)心定位算法對錨節(jié)點數(shù)量和分布有比較高的要求，本文在不增加硬件資源的前提下，提出ERR-WCL算法。該算法采用無人機以既定的合理航跡飛行在整個監(jiān)測區(qū)域，在充分考慮了不同鄰居虛擬錨節(jié)點位置對未知節(jié)點的影響情況下，利用了未知節(jié)點的接收信號強度比值并結(jié)合指數(shù)函數(shù)對未知節(jié)點的位置進行估計。仿真實驗表明ERR-WCL算法可以得到較小的定位誤差，同時使用無人機降低了定位成本并解決了二維移動錨節(jié)點受到空間約束，移動不靈活等問題。接下來的工作依據(jù)定位結(jié)果優(yōu)化無人機的航跡，對未知節(jié)點進行進一步精確定位。