基于動態近鄰反饋修正的室內定位算法

黨小超，黑毅力，郝占軍，李芬芳

(1.西北師范大學 計算機科學與工程學院，蘭州 730070；　2.甘肅省物聯網工程研究中心，蘭州 730070)(*通信作者電子郵箱hei_yili@163.com)

0　引言

無線傳感器網絡(Wireless Sensor Network， WSN)是一種低能耗、自組織、結構多樣、連接廣泛的網絡系統，由大量無線傳感器節點組成。其目的是實現節點間的合作，以感知、采集和處理覆蓋區域中對象的信息，并最終發送給觀察者。它在軍事國防、工農業控制、城市管理、生物醫療、環境監測、目標跟蹤、危險區域遠程控制等應用中具備良好的應用前景[1]。在這些應用中，確定無線傳感器節點的位置非常重要，定位技術也因此吸引了研究人員的廣泛關注[2]。目前世界上使用的定位系統主要是全球定位系統(Global Positioning System, GPS)[3]，但是由于室內障礙物的存在，使得GPS信號很難被接收從而導致定位失效，所以人們通過WSN節點定位算法來尋求解決方案[4]。

在現有的無線傳感器網絡定位算法中，可以將定位算法分為基于距離的定位算法和距離無關的定位算法兩大類[5]。前者需要測量待定位目標的距離或方位等位置參數以進行定位，主要測距技術有基于到達時間(Time Of Arrival, TOA)、基于到達時間差(Time Difference Of Arrival, TDOA)、基于到達角度(Angle Of Arrival, AOA)、基于接收信號強度(Received Signal Strength Indicator, RSSI)的定位等；在距離無關的定位算法中，如質心定位(Centroid)算法、距離向量-跳段定位(Distance Vector-Hop， DV-Hop)算法、自組織定位(Amorphous Positioning)算法、近似三角形內點測試法(Approximate Point-In-Triangle test， APIT)等，未知節點無須測量與鄰居節點的距離或相對角度，而是利用連接或者跳數信息計算節點的位置。其中，RSSI測距技術因其成本低廉、能耗低等優勢在無線定位技術中得到廣泛應用。但在實際室內環境中，信號易受到室內地板、墻壁、人員走動等影響，產生多徑效應，導致基于RSSI定位算法的定位精度下降。為了最大限度地消除RSSI測距誤差對無線傳感器節點自身定位精度的影響，文獻[6]提出了一種基于RSSI的無線傳感器網絡距離差分修正定位算法(Distance Difference Localization Algorithm， DDLA)。該算法以三邊定位算法為基礎，將離目標節點最近的信標節點作為參考節點對基于RSSI的測距進行差分修正，最后利用差分和質心定位方法相結合的方式實現定位，在一定程度上減少了定位誤差；但是該算法未能實現稀疏節點的定位，增加了網絡中的通信開銷。文獻[7]為了解決傳統的以蒙特卡羅為基礎的移動定位算法中定位精度差、采樣效率低的問題，提出了一種基于接收信號強度指示測距的蒙特卡羅盒定位(Monte Carlo Boxed localization， MCB)算法。該算法首先對RSSI的采樣區域進行細化，以提高樣本的成功率，最后利用估計節點運動軌跡的方法計算節點位置；然而該算法存在隨機性較強、多次迭代耗時較長的缺陷。文獻[8-9]考慮了三維空間中因接收信號的不確定性導致算法定位誤差較大的因素，提出了混合測量定位算法。該算法將傳統到達角度和接收信號強度的定位技術相結合，得到了混合測量的優化模型精確估計位置坐標，在一定程度上減少了定位誤差和網絡中的通信開銷。文獻[10]針對傳統測距定位算法中無線信號傳輸模型及模型參數對環境因素依賴性強的特點，考慮傳統的使用固定的路徑損耗參數模型代替信號強度和距離的關系會造成較大誤差，提出了一種新的動態估計路徑損耗參數的方法。該算法首先確定最小定位子區域，然后利用已知參考節點的信息估計模型參數，最后實現準確測距，達到精確定位的目的。

通過對以上算法的研究及分析，提出了一種基于動態近鄰反饋修正的室內定位算法FC-DNN(Feedback Correction of Dynamic Nearest Neighbors)。該算法為了減少環境因素帶來的測距誤差，在定位前首先通過區域劃分思想確定最小定位區域，并在該子區域中利用節點間的幾何關系估算路徑損耗參數；同時引入向量混合積的概念對選取的信標節點進行過濾，使錨節點得到充分利用，同時降低定位算法對初始錨節點數量的需求；最后，動態選取錨節點并計算其定位誤差因子來修正未知節點的坐標，進一步提高定位精度。

1　相關理論

1.1　基于信號衰減的距離估計模型及問題分析

目前，無線信號傳輸中最常用的是Shadowing模型[11]，即錨節點向未知節點廣播信息，未知節點收到廣播之后作出響應。當錨節點再次收到響應后，利用式(1)推算出與未知節點的距離。

(1)

RRSSI=ARSSI-10nplg(d)

(2)

通過多次測量RSSI平均值后，利用式(2)可以計算出兩點之間的距離RSSI。然而對數距離路徑損耗模型方法存在兩個主要缺點：一是RSSI值是高度隨機的，并且易受多徑和衰落的影響[13]；二是定位區域中路徑損耗模型參數ARSSI和n與無線信號傳輸環境密切相關，且隨著定位節點的移動參數也在不斷變化中。為了解決這些問題，可以采用損耗參數動態估計的方式，即在定位區域選取兩組已知錨節點，分別測出其距離及對應的RSSI值，并結合其已知的位置信息，借助式(2)計算定位區域中的路徑損耗模型參數，減少測距誤差，提高定位精度。

1.2　Voronoi圖劃分

Voronoi圖又叫泰森多邊形，作為計算幾何中一種基本的幾何結構，在解決無線傳感器網絡覆蓋控制、網絡定位等問題中應用廣泛。它是由連接相鄰兩點的直線的垂直平分線組成的連續多邊形組成。平面中的N個離散點按照最鄰近原則把平面劃分為幾個區，該點所在的區是到該點距離最近點的集合。

假設P是由n個離散的傳感器節點組成的集合，P={p1,p2,…pi…,pn}(2≤n<∞)平面上任意一點X(x,y)與節點pi(xi,yi)(pi∈P)的歐氏距離為：

(3)

定義生長點pi的Voronoi多邊形區域V(pi)為所有到pi距離最小點的集合：

V(pi,X)=

{x|d(pi,X)≤d(pj,X),?i≠j,j=1,2,…,n}

(4)

整個平面被n個生長點劃分為n個單元，而所有生長點pi的Voronoi多邊形集合構成了P的Voronoi圖，可以將其表示為V={V(p1),V(p2),…,V(pn)}。

1.3　Spearman等級相關系數

Spearman等級相關系數(Spearman’s rank correlation coefficientρ)是一種非線性相關測量方法，主要用于確定兩組數據之間關聯程度。假設給定兩組不重復順序樣本數據{X1,X2,…,Xn}和{Y1,Y2,…,Yn}，定義xi(1≤i≤n)在{X1,X2,…,Xn}中的秩次為Ri，yi在{Y1,Y2,…,Yn}中的秩次為Qi，秩次差為di=Ri-Qi，利用式(5)計算相關系數為：

(5)

2　FC-DNN算法描述

動態近鄰反饋修正的室內定位算法主要有三個階段：1)區域劃分判斷階段。使用Voronoi圖對定位空間中信標節點進行區域劃分，構造Voronoi多邊形，判定待定位節點所在子區域。2)區域參數動態估計階段。在室內狹小的范圍內，通信信號在傳輸過程中受到的因素影響也相似，可以充分利用錨節點的位置信息動態估計子區域中的模型參數ARSSI、n。3)節點位置計算階段。節點定位階段分為節點預估計和節點反饋修正兩個步驟，首先，利用已知信息及空間幾何向量關系對節點定位，然后引入Spearman等級相關系數動態計算鄰居錨節點反饋修正因子對初次定位結果進行修正。

2.1　區域劃分判斷階段

為了使信號衰減的距離估計模型更加符合實際環境，同時考慮到室內復雜的環境因素對測距誤差的影響程度，在實現無線定位之前，采用Voronoi圖的構建思想將整體區域進行劃分，目的是縮小被定位區域的范圍，在分割后的子區域中擬合環境參數，從而進一步提高RSSI測量值的精確度和環境適應性。

如圖1所示，假設實心五星節點代表錨節點Mi，空心圓代表未知節點U。隨機選擇k個錨作為初始節點，通過Voronoi圖將區域劃分，并且根據Voronoi圖中任何多邊形內的點到它所在區域的種子點的距離比到其他區域種子點的距離近的性質，可以計算出未知節點U與其他初始錨Mi之間的歐氏距離dui，選擇距離最小的錨節點所在的區域即為待定位子區域。

圖1　Voronoi圖的構建Fig. 1　Construction of Voronoi diagram

2.2　定位區域路徑損耗參數動態估計階段

由于基于RSSI測距模型參數ARSSI、n在實際環境中會隨著諸多因素的改變而不同，所以本文利用一種動態估計路徑損耗模型參數的方法[14]，以減小測距模型的誤差,從而提高定位精度。因為算法在第一階段對定位區域進行了有效的劃分，在一個非常小的范圍內，物理位置越接近，信號的通信環境也越相似，可以認為在定位子區域中的路徑損耗模型也近似相同。假設節點之間可以相互通信，可以充分利用錨節點的位置信息估計定位區域內路徑損耗參數。

根據式(2)可以建立方程組：

(6)

(7)

圖2　區域內路徑損耗模型參數計算Fig. 2　Parameters calculation of path loss model in each region

(8)

2.3　節點位置計算階段

假設在三維空間中分布著N個位置已知的錨節點Mi(i=1,2,…,N)，其位置坐標為(Mix,Miy,Miz),同時區域中未知節點U的位置坐標表示為(Ux,Uy,Uz)，未知節點U與錨節點Mi間的RSSI測量值表示為RSSi。節點位置計算階段具體步驟如下：

步驟1節點共線過濾。在確定未知節點定位區域后，選取最優RSSi，即未知節點在收到超過閾值m(文中m=4)個信標信息后，至少需要4個錨節點作為參考節點進行自身定位計算，其中三個錨節點用于初步幾何向量定位，其余錨節點將充當修正節點對初步定位坐標進行修正。因此至少獲取4點位置信息用以定位未知節點，但是存在兩種特殊情況無法完成定位，即當獲取的4點在同一個平面上或者其中存在3點在同一條直線上。為了解決這個問題，本文根據空間向量理論來過濾這些節點。假設對于獲取的4個錨節點M1、M2、M3和M4，利用式(9)的進行檢驗，如果存在向量M1M2，M1M3和M1M4的混合積不為0，則利用這4個不共面的點的坐標來計算待定位節點的坐標位置[15]。否則，返回繼續尋求符合條件的錨節點。

[M1M2,M1M3,M1M4]=(M1M2×M1M3)×M1M4=

(9)

通過上面的過濾處理，可以得到4個有效的錨節點來計算未知節點的位置。

然后利用已知信息及空間幾何關系對未知節點定位。

圖3　錨節點反饋的幾何定位Fig. 3　Geometric localization of anchor node feedback

(10)

又根據向量的定義可得：

(11)

所以聯合方程(10)和(11)建立方程:

(12)

同理可得：

(13)

(14)

通過式(12)、(13)、(14)得到的就是待定位節點U′的初步定位坐標，因為對節點進行了篩選過濾，同時幾何向量的算法也很好地消除了多解問題。

步驟3錨節點反饋修正。利用步驟1中節點過濾方法和Spearman等級相關系數動態判斷選定錨節點的鄰居節點及個數，根據最近錨節點通過對比其定位結果與自身實際位置得到修正因子，并將值反饋給鄰居未知節點,鄰居未知節點利用收到的修正因子對最終定位結果進行修正，得到更加精確的定位坐標。

圖4　鄰居節點示意圖Fig. 4　Illustration of neighbor nodes

(15)

(16)

3　實驗仿真與分析

為了檢驗FC-DNN算法的性能，使用Matlab 2016仿真實驗平臺進行仿真實驗,并與基于RSSI的無線傳感器網絡距離差分修正定位算法(DDLA)[6]、受限三維空間傳感器定位(CO-3D)算法[16]在誤差、能耗方面進行比較。詳細仿真參數信息如表1所示。

表1　仿真參數Tab. 1　Parameters of simulation

3.1　定位誤差率比較

為了刻畫FC-DNN算法的性能，減少實驗中隨機誤差的干擾，最終結果取30次實驗的平均值。采用均一化定位誤差來評價算法性能，均一化定位誤差定義為：

error=

(17)

式中:(xi,yi,zi)為未知節點i的實際坐標，(xki′,yki′,zki′)為第k次估計的未知節點i的坐標，N為未知節點數量，R為通信半徑，K為實驗次數。

圖5顯示了在固定節點通信半徑而錨節點個數變化時，FC-DNN算法與其他兩種算法的均一化定位誤差比較。從圖5可以看到，隨著錨節點個數的增加，定位誤差總體呈下降趨勢，這是因為在定位前期過程中隨著更多有效錨節點被引入參數和坐標計算，在一定程度上提高了定位精度。根據仿真結果的統計數據，本文算法的平均定位精度約為33%，而CO-3D、DDLA算法平均定位精度分別為48%和46%，綜合分析，在不同的錨節點個數時，FC-DNN算法的誤差相比其他兩種算法都更低。尤其在錨節點個數超過50%時，其誤差下降速度加快。這是因為FC-DNN算法是對若干個可能的節點位置利用鄰居節點進行修正計算，同時算法通過增加對錨節點的判斷、過濾操作得到了符合條件的錨節點信息，而兩種對比算法僅利用求平均值的方法得到最終坐標，誤差較大，相比之下，FC-DNN算法的定位精度更高。

圖6為定位過程中隨著節點通信半徑R的增大，不同錨節點個數時，FC-DNN算法與CO-3D和DDLA算法的均一化定位誤差比較。從圖6可以看出，當錨節點比例確定時，隨著R增大，節點定位誤差均呈下降趨勢，這是因為隨著通信半徑增大，節點覆蓋區域呈正相關，即提高了網絡連通性，定位更加準確。仿真結果顯示在相同條件下，FC-DNN算法相比CO-3D算法和DDLA算法的誤差始終最低，而且更加平緩，尤其是與CO-3D算法相比，因為錨節點的信息得到更加充分的利用，多次累計定位減少了定位誤差率(約15個百分點)，提高了節點的定位精度，說明本文的算法對通信半徑的改變并不敏感，更加穩定。

圖5　均一化誤差隨錨節點個數的變化Fig. 5　Normalized position error with different number of anchors nodes

圖6　均一化誤差隨節點通信半徑的變化Fig. 6　Normalized position error with different node communication radius

3.2　能耗比較

設置固定的節點通信半徑，當錨節點數取不同值時，FC-DNN算法與CO-3D算法和DDLA算法的能耗比較如圖7所示。圖7顯示的能耗與實際情況吻合，原因是在FC-DNN算法中，首先對區域進行了合理的劃分，在待定位區域內，通過篩選最優鄰居節點實現定位。FC-DNN算法由于對區域進行合理劃分后，將空間復雜度降為O(lbn)，而CO-3D算法的空間復雜度為O(n)，同時其不斷隨機選擇幾個可能的錨節點進行定位也導致了定位能量的消耗。而且本文算法通過過濾優選鄰居錨節點，使得在每輪計算中錨節點信息得到充分利用，使用頻率大幅度降低，同時延長了整個系統的生命周期，提高了定位的覆蓋率和成功率，所以FC-DNN算法的能耗最低。

圖7　能耗隨錨節點個數的變化Fig. 7　Energy consumption with different number of anchor nodes

4　結語

針對無線傳感器網絡中基于RSSI測距模型中可能由于反射、多徑效應和天線增益導致重大的傳播損耗而引起定位精度的問題，提出了動態鄰居錨節點反饋修正算法，引入錨節點反饋修正因子來修正未知節點的坐標，有效解決了傳統的RSSI測距技術導致定位結果誤差比較大的問題。通過仿真和實驗結果驗證，與CO-3D算法和DDLA算法相比，該算法在定位誤差、平均能耗等方面性能更優，能夠更精確地定位節點。但是，當劃分后的定位區域中錨點數比較稀疏時，定位仍存在困難，同時區域劃分判斷階段也以消耗定位時間為代價，這是以后研究需要解決的問題。

參考文獻:

[1]ZHANG R, XIA W, JIA Z, et al. The indoor localization method based on the integration of RSSI and inertial sensor [C]// GCCE 2014: Proceedings of the 2014 IEEE 3rd Global Conference on Consumer Electronics. Piscataway, NJ: IEEE, 2014: 332-336.

[2]ADEWUMI O G, DJOUANI K, KURIEN A M. RSSI based indoor and outdoor distance estimation for localization in WSN [C]// ICIT 2013: Proceedings of the 2013 IEEE International Conference on Industrial Technology. Piscataway, NJ: IEEE, 2013: 1534-1539.

[3]MEHRA R, SINGH A. Real time RSSI error reduction in distance estimation using RLS algorithm [C]// IACC 2013: Proceedings of the 2013 IEEE 3rd International Advance Computing Conference. Piscataway, NJ: IEEE, 2013: 661-665.

[4]YASSIN A, NASSER Y, AWAD M, et al. Recent advances in indoor localization: a survey on theoretical approaches and applications [J]. IEEE Communications Surveys & Tutorials, 2017, 19(2): 1327-1346.

[5]錢志鴻，孫大洋，LEUNG Victor.無線網絡定位綜述[J].計算機學報，2016，39(6):1237-1256. (QIAN Z H, SUN D Y, LEUNG Victor. A survey on localization model in wireless networks [J]. Chinese Journal of Computers, 2016, 39(6): 1237-1256.)

[6]任維政，徐連明，鄧中亮，等.基于RSSI的測距差分修正定位算法[J].傳感技術學報，2008，21(7):1247-1250. (REN W Z, XU L M, DENG Z L, et al. Distance difference localization algorithm based on RSSI for wireless sensor networks [J]. Chinese Journal of Sensors and Actuators, 2008, 21(7): 1247-1250.)

[7]武曉琳，單志龍，曹樹林，等.基于接收信號強度指示測距的蒙特卡羅盒移動節點定位算法[J].計算機應用，2015，35(4):916-920. (WU X L, SHAN Z L, CAO S L, et al. Monte Carlo boxed localization algorithm for mobile nodes based on received signal strength indication ranging [J]. Journal of Computer Applications, 2015, 35(4): 916-920.)

[8]SINGH A, KUMAR S, KAIWARTYA O. A hybrid localization algorithm for wireless sensor networks [J]. Wireless Personal Communications, 2013, 71(2): 1365-1385.

[9]嚴長虹，馬靜.三維傳感網空間RSS與AOA混合測量的精確定位方法[J].傳感技術學報，2017，30(3):450-455. (YAN C H, MA J. Precise positioning method with hybrid RSS and AOA measurement in 3-D WSN space[J]. Chinese Journal of Sensors and Actuators, 2017, 30(3): 450-455.)

[10]李瑤怡，赫曉星，劉守印.基于路徑損耗模型參數實時估計的無線定位方法[J].傳感技術學報，2010，23(9):1328-1333. (LI Y Y, HE X X, LIU S Y. Wireless localization algorithm based on path loss model parameter estimated in real time[J]. Chinese Journal of Sensors and Actuators, 2010, 23(9): 1328-1333.)

[11]AWARD A, FRUNZKE T, DRESSLER F. Adaptive distance estimation and localization in WSNs using RSSI measures [C]// DSD 2007: Proceedings of the 2007 IEEE 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools. Piscataway, NJ: IEEE, 2007: 471-478.

[12]胡詠梅，張歡.一種改進的無線傳感器網絡質心定位算法[J].計算機工程與科學，2012，34(2):45-49. (HU Y M, ZHANG H. An improved algorithm for the centroid localization of wireless sensor network [J].Computer Engineering and Science, 2012， 34(2): 45-49.)

[13]XUE W, QIU W, HUA X, et al. Improved Wi-Fi RSSI measurement for indoor localization [J]. IEEE Sensors Journal, 2017, 17(7): 2224-2230.

[14]ZHENG J, WU C, CHU H, et al. An improved RSSI measurement in wireless sensor networks [J]. Procedia Engineering, 2011, 15: 876-880.

[15]戴桂蘭，趙沖沖，邱巖.一種基于球面坐標的無線傳感器網絡三維定位機制[J].電子學報，2008，36(7): 1297-1303. (DAI G L, ZHAO C C, QIU Y. A localization scheme based on sphere for wireless sensor network in 3D [J]. ACTA Electronica Sinica, 2008, 36(7): 1297-1303.)

[16]LIANG J, SHAO J, XU Y, et al. Sensor network localization in constrained 3-D spaces [C]// Proceedings of the 2006 IEEE International Conference on Mechatronics and Automation. Piscataway, NJ: IEEE, 2006: 49-54.