基于UAV的無線傳感器網絡加權質心定位算法*

高美鳳，尹持俊

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

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

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

1 基于UAV的無線傳感器網絡加權質心定位算法

1.1 無人機飛行航跡

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

圖1 四種航跡規劃方法示意圖

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

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

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

1.2 改進加權質心定位算法權值

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

式中:P(x，y)為未知節點估計位置；B i(x，y)為錨節點i的位置坐標；N為未知節點的鄰居錨節點數；w i為鄰居錨節點i對未知節點的權重值，其通常可以是未知節點和錨節點間距離的函數、或者是未知節點接收到的RSSI的函數。

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

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

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

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

1.3 權值變化對未知節點定位坐標的影響分析

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

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

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

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

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

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

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

1.4 基于UAV的節點定位

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

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

式中:

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

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

1.5 改進的加權質心定位算法步驟

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

?

2 仿真與分析

2.1 仿真環境設置

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

表1 仿真環境

2.2 通信半徑的影響分析

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

圖3 通信半徑為5 m的鄰居關系圖

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

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

圖4 T-MLE定位效果圖

圖5 RR-WCL定位效果圖

圖6 E-WCL定位效果圖

圖7 ERR-WCL定位效果圖

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

相同的仿真環境下，改變節點的通信半徑后，節點的相對平均定位誤差由式(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算法可以得到較小的定位誤差，定位效果較好。

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

2.3 UAV高度的影響

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

圖9 飛行高度為0.5 m的鄰居關系圖

圖10 飛行高度為1.5 m的鄰居關系圖

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

圖11 飛行高度為2.5 m的鄰居關系圖

點的位置坐標；飛行高度為2.5 m時，未知節點可以接收6或7個鄰居虛擬錨節點的位置坐標。這是由于節點的通信半徑固定為5 m，當無人機飛行高度越高，未知節點周圍的鄰居虛擬錨節點的數目就越少。相同的仿真環境下，改變無人機的飛行高度后，根據式(11)求節點的相對平均定位誤差，得到節點的相對平均定位誤差如圖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算法可以得到較小的定位誤差，定位效果較好。表示無人機可以靈活的在飛行范圍內飛行，不受到空間約束，并結合所提ERR-WCL定位算法可以得到較好的定位結果。

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

3 結束語

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