基于動態損耗因子和權重的改進質心定位算法

任曉奎 李鋒 程琳

摘 要：針對無線傳感器網絡（WSN）節點的定位精度受環境和誤差權重因子的影響問題，提出一種對路徑損耗因子和誤差權重因子動態修正的質心定位算法。前期根據實測和路徑損耗模型，加權修正得出動態損耗因子;后期通過劃分矩形區域，構造權重因子矩陣。首先，使用動態損耗因子，代入傳統加權質心定位算法估算出未知節點的位置;然后，查詢誤差權重因子矩陣，確定最優權重因子，重新計算出未知節點坐標。實驗結果表明，改進的算法降低了平均誤差和最小誤差，定位精度比普通質心算法提高了58%，比動態修正質心算法提高了21%，比動態加權質心算法提高了11%，定位精度有所提高。

關鍵詞：無線傳感器網絡;定位;動態損耗因子;誤差權重因子;動態修正

中圖分類號： TP391.9

文獻標志碼：A

文章編號：1001-9081（2019）03-0824-05

Abstract： Aiming at the problem that the positioning accuracy of wireless sensor network nodes is affected by the environment and the error weight factor， a centroid positioning algorithm was proposed to dynamically correct path loss factor and error weight factor. At earlier stage， a dynamic loss factor was obtained by weighting correction according to the actual measurement and path loss model; at later stage， the weight factor matrix was constructed by dividing rectangular region. Firstly， the location of the unknown node was estimated by introducing dynamic loss factor into the traditional weighted centroid localization algorithm. Then， the error weight factor matrix was queried to determine the optimal weight factor. Finally， the unknown node location was recalculated. The experimental results show that the improved algorithm reduces the average error and the minimum error， and the positioning accuracy is 58% higher than ordinary centroid algorithm， 21% higher than dynamic correction centroid algorithm， and 11% higher than dynamic weighted centroid algorithm.

Key words： Wireless Sensor Network （WSN）; positioning; dynamic loss factor;error weight factor;dynamic correction

0 引言

目前，定位技術早已成為國內外研究的熱點問題。在室外定位，各種導航系統已經完全滿足定位精度的需要。但在室內定位方面，定位精度仍不理想。為此，各種室內定位技術被不斷提出和發展。無線傳感器網絡（Wireless Sensor Network， WSN）技術設置靈活，且WSN定位技術[1-3]可以通過有限的已知錨點，進行未知節點的區域估算，結合彼此間的信息交換和各種算法的運行，確定未知節點的位置。WSN節點定位技術在研究領域已取得很大成果[4]。目前，常用的算法主要是質心定位算法以及質心定位算法的各種改進。其主要過程一般包括對距離的確定和對位置的估算。文獻[5]使用等邊三角形定位;文獻[6-7]通過接收信號強度（Received Signal Strength， RSS）判斷收發距離來進行定位;文獻[8]通過優選定位節點，解決了通信半徑和定位精度相矛盾的問題;文獻[9]和文獻[10]都是根據信標節點對未知節點的不同影響力，確定加權因子，并優選信標節點。這些都是利用RSS轉化成距離來進行定位，沒有充分利用每個節點接收的強度。文獻[11]針對以上缺點，將RSS進行卡爾曼濾波，并利用皮爾遜相關系數作為權重，使定位精度得到提高;文獻[12]為了提高精度，通過高斯濾波然后進行定位等。還有一些文獻研究安裝天線的類型對室內定位的影響，如文獻[13]采用定向天線，利用信號強度差定位;文獻[14]改進文獻[13]，同樣利用定向天線，但擴大了定位面積。

而在對模型參數進行改進的過程中，文獻[15]中提出了一種基于卡爾曼和線性插值濾波的改進三角質心定位算法，但也僅僅通過測量固定的1m處的接收功率A和路徑損耗因子n的值進行定位;文獻[16]提出了一種基于RSS路徑損耗因子動態修正的算法，有較好的定位效果，但在算法后期定位過程中仍是利用普通的質心算法;文獻[17]使用動態權重因子，但在測距階段沒有考慮到路徑損耗因子的動態變化。

針對文獻[16]和文獻[17]的不足，本文提出了一種動態修正的質心定位算法。在接收到信號強度RSS后，先經高斯濾波，通過已知距離d測出實際RSS值與n的關系，進行一定的運算，求出動態n值;然后再與改進的加權質心算法結合，即在不同區域選用不同的權重因子a，結合兩種方法的優點，從而使定位更加精確。

1 質心定位

1.1 路徑損耗模型

在進行室內定位的研究中，通常使用以下室內路徑損耗模型來進行測距。即：

為了表示方便，將r仍改為d計算。

1.2 高斯濾波

由于在室內傳播時，信號不穩定，在同一位置的RSS值具有隨機性，為了減小誤差，必須對原始信號進行濾波處理。在對RSS進行濾波時，有許多優化方法，常用的有均值濾波、高斯濾波和卡爾曼濾波。在實際的應用中，當距離較近時，三者濾波效果相差不大，但超過一定界限，高斯濾波的效果較好。

高斯濾波過程如圖1所示。

2）選取概率較高值的集合：

通常為了去除相對誤差較大的數據，會加入約束條件，在概率論中當概率大于0.5而小于1時為大概率事件，可以保留，本文取0.6，即將大于0.6的RSS提取出來，放入集合RGAUSS[i]：

1.3 質心定位

在數學計算中，只要知道三個已知端點的位置，以及各端點到未知節點的距離長度，如圖2，就可以利用式（8）計算出未知節點的大概位置。

但因各種環境因素的影響，路徑損耗模型并不一定完全匹配，因此所求出的未知節點與實際位置有一定的誤差，如圖3所示，未知節點并不處于A、B、C三圓交點。為此，各種加權質心算法的提出就是為了減小估算位置與實際位置的誤差，以下為一般質心算法式（9）：

但普通的質心定位中，并沒有考慮距離遠近對定位結果的影響，因此在普通的質心定位算法的基礎上進行改進，提出各種加權質心定位算法。其中以距離和倒數的加權質心算法較為常見，如式（10）：

2 算法改進

本文實際是對文獻[16]和文獻[17]的改進。文獻[16]使用動態損耗因子后，使用普通的質心算法進行定位，因此使用普通的算法這一步還可以進行改進;文獻[17]在初次定位計算初次未知節點M時，使用一般的靜態損耗模型后，再進行動態權重計算，因此在使用損耗模型這一步可以進行改進。本文的改進實際上是在前半部分使用動態損耗因子來確定路徑損耗模型，而后在定位階段使用動態權重方法。

2.1 動態損耗因子n的選擇

方法步驟：

1）在相同距離單個參考點1m不同角度測出信號值N組，經高斯濾波式（6）后，代入式（7），取其均值為A。

2）同樣方法在距離為2m、3m等一直到10m（實際可根據現場選擇）的距離值測出信號強度RSS，根據不同的距離下的RSS值代入距離損耗式（3），其中A為1m處的信號強度，求出不同的固定n值，并將其列入表1中，表1中RSS/dBm表示接收的信號強度，nd為距離為d時的路徑損耗因子。

3）令在未知點所測的RSS信號強度為R0，對照表1中RSS值Ri，代入式（11）中，求出動態的n值，從而求出距離d。

2.2 動態權重a的選擇

由于不同區域擁有不同的相對最優權重，因此可以利用此種算法對定位精度進行改進。

其具體步驟如下：

1）在一個矩形區域頂點設置4個參考點A、B、C、D。

2）將矩形區域對半均分為4個區域如圖4所示，并分別標號1、2、3、4，由于誤差分布呈對稱關系[17]，為節省時間，可只測量區域標號1，如圖4，其他區域可進行對稱運算。

3）將區域1均分為若干相同矩形區域，如圖4所示，長寬隨實際場地再具體確定定值（長寬值越小，所分網格越密，定位時精度越高，但相應復雜度增大），如圖5、圖6;測量出每個網格頂點距離A、B、C、D最近3個距離值d1、d2、d3，代入式（10），遍歷每個點上誤差的權重因子（-15～15，步長為0.1），選取最優的權重值，將權重值放入矩陣，構成權重因子矩陣A，如式（12）所示：

2.3 定位

1）通過測量未知節點M從4個參考點接收的RSS值，將所得到的RSS值與表1中進行比較，通過式（11）求出動態損耗因子，然后代入路徑損耗公式（3），計算出4個距離d1、d2、d3和d4，如圖5所示，選取最短的3個距離重新定義為d1、d2、d3。

2）將權重因子a先設置為1，再次代入式（10）進行粗定位，計算出未知節點M′的位置。

3）根據M′計算出實際M點位置。

①當M′點位于矩形區域內部時：

②當正好位于頂點時，直接取此點坐標。

③當位于分界處時，取分界線所在兩個頂點的權重，反求新的兩個未知點，再求均值。

考慮到在此步仍可用三角質心定位，但若劃分區域很小，就可以不用，以節省時間，因此本文最后采用均值計算。

2.4 程序流程

改進算法的主要流程如下。

1）取出在1m處測的RSS值N組，高斯濾波后取其均值，得出A值。

2）將A代入路徑模型，求出在已知固定距離和RSS值下的路徑損耗因子n。

3）將在未知節點M所測的RSS值代入式（11），得出動態的n值。

4）將RSS值和動態n值代入式（3），得出4個距離，取其最小的3個，記為d1、d2、d3。

5）將權重因子a設為1，代入式（10），進行粗定位，求出此時M′點坐標。

6）在權重矩陣中取出M′點所在網格中的4個頂點的權重a，分別代入式（10），得出4個未知節點坐標。

7）將所求4個未知節點坐標取均值，最終得出未知節點M的坐標。

3 實驗分析

3.1 實驗過程

在空曠的室內場地，選取10m×10m矩形區域進行實驗。在矩形的4個頂點位置設置參考點，設置4個相同型號的路由器斐訊FWR-706，其中A（0，10）、B（10，10）、C（0，0）、D（10，0）。本文RSS測試軟件選用Homedate 1.74，軟件接收信號強度如圖7所示。算法運行于Matlab 2014a版本。

按上述步驟所測不同距離RSS值與n的對應關系填入表1，數據如表1所示。為了表示直觀方便，繪制圖8、圖9，直觀地表現RSS和nd與接收距離之間的關系。從表2和圖8中可以發現，隨著距離的增加，信號強度RSS和路徑損耗因子隨距離的增加呈現不同的變化。

在所分割的4個區域中，僅當測試誤差最小時，填入裝載最小權重a的矩陣A，如式（14）：

剩下3個區域，2區為1區的左右翻轉，3區為1區的上下翻轉，4區為3區的左右翻轉。

通過測量未知節點M的RSS值，將其代入式（3），求出M點距離4個參考點的距離值，選取其中最小的3個，分別作為d1、d2、d3。其實際計算如式（15）：

3.2 實驗分析

由于實驗環境的不同，實驗數據不可能與文獻[16]和文獻[17]完全相同，為了進行準確率的對比，隨機進行實驗。

本文采用實際位置與估算位置之間的相對距離進行誤差分析，如式（16）：

在實際環境中，隨機挑選15個位置對幾種方法依次進行定位分析，最終得到實驗結果數據如表2所示。

但從表中無法直觀地看出各算法的優劣，依據表中數據畫出誤差折線圖9。

從圖9中可以看出，普通的質心定位效果較差，動態損耗因子質心定位和動態加權質心定位效果相差不大，而改進算法盡管有些點比動態損耗因子質心定位和動態加權質心定位效果差，但從總體上看，還是有很大優勢。

為了不失一般性，因此隨機抽取這15個位置進行定位，取100組數據求其誤差均值，繪制折線圖如圖10，從圖中可以看出，改進算法的誤差小于以上三種定位算法。

從表3中可以看出，在隨機挑選100組未知節點進行計算時，動態損耗因子質心算法和動態加權質心算法的最小誤差值相似，但都比普通的質心算法精確，而最大誤差值后三者相似，但還是優于普通質心算法，而在結合兩種算法的基礎上進行的改進算法在精度上是最好的，比質心算法提高了0.44，提高58%，比動態修正質心算法提高了0.09，提高21%，比動態加權質心算法提高了0.04，提高11%，改進算法平均誤差值最小。

本文從算法運行時間對算法進行分析，從表7中看出，相比于普通質心定位算法，動態損耗因子質心算法在定位前期不斷的調整損耗因子，動態加權質心算法構造權重因子矩陣，從而導致兩種算法的運行時間都比普通的質心定位長。而改進算法是動態損耗因子和動態權重因子的結合，因此在前期的運行時間和動態損耗因子算法相近，而在后期的定位階段，由于則需要查詢權重矩陣，所以在提升精度的同時，對運行時間有所增加。因此下一步的工作要進行算法時間的減少方向研究。

4 結語

本文在傳統質心定位的基礎上，綜合考慮了文獻[16]損耗因子的動態變化和文獻[17]權重因子的不同對定位精度的影響，將路徑損耗模型的動態損耗因子和加權質心定位算法的動態權重因子相結合，提出一種改進的質心定位算法，提升了定位的精度。新的算法將實際測量的RSS代入動態損耗因子計算公式，從而使不同的距離對應相應的路徑損耗因子，減小質心定位算法因距離造成的誤差;將定位區域劃分網格，引入動態權重因子，減小因不同區域權重因子而造成的誤差。改進的定位算法考慮了文獻[16]和文獻[17]的優點，經過實驗驗證，在定位精度上得到了提高。但由于算法的復雜，導致相應的運算時間延長，之后的工作將對算法進行精簡改進，提高算法的運算速度;且本文主要是在沒有遮擋物的情況下進行的實驗，下一步將研究在室內條件下，有遮擋物時的定位問題。

參考文獻 （References）

[1] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey[J]. Computer Networks， 2008， 52（12）： 2292-2330.

[2] MAO G， FIDAN B， ANDERSON B D O. Wireless sensor network localization techniques [J]. Computer Networks， 2007， 51（10）： 2529-2553.

[3] RUDAFSHANI M， DATTA S. Localization in wireless sensor networks [C]// Proceedings of the 2007 6th International Symposium on Information Processing in Sensor Networks. New York： ACM， 2007： 51-60.

[4] 鄧中亮，余彥培，徐連明，等.室內外無線定位與導航[M].北京：北京郵電大學出版社，2013：43-54.（DENG Z L， YU Y P， XU L M， et al. Indoor and Outdoor Wireless Positioning and Navigation [M]. Beijing： Beijing University of Posts and Telecommunications Press， 2013： 43-54.）

[5] 朱劍，趙海，孫佩剛，等.基于RSS均值的等邊三角形定位算法[J].東北大學學報（自然科學版），2007，28（8）：1094-1097.（ZHU J， ZHAO H， SUN P G， et al. Equilateral triangle localization algorithm based on average RSSI [J]. Journal of Northeastern University （Natural Science）， 2007， 28（8）：1094-1097.）

[6] 趙昭，陳小惠.無線傳感器網絡中基于RSSI的改進定位算法[J].傳感技術學報，2009，22（3）：391-394. （ZHAO Z， CHEN X H. An improved localization algorithm based on RSSI in WSN [J]. Chinese Journal of Sensors and Actuators， 2009， 22（3）： 391-394.）

[7] 杜佳星，陳亞偉，張靜.基于聚類分析優化的距離修正室內定位算法[J].計算機工程與科學，2018，40（2）： 246-254. （DU J X， CHEN Y W， ZHANG J. Distance rectification indoor localization based on cluster analysis optimization [J]. Computer Engineering and Science， 2018， 40（2）： 246-254.）

[8] 谷廣，游峰.基于接收信號強度指示的改進質心定位算法[J].傳感器與微系統，2018，37（2）：147-153. （GU G， YOU F. Improved centroid localization algorithm based on RSSI [J]. Transducer and Microsystem Technologies， 2018， 37（2）： 147-153.）

[9] 陳維克，李文鋒，首珩，等.基于RSSI的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報（交通科學與工程版），2006，30（2）： 265-268.（CHEN W K， LI W F， SHOU H， et al. Weighted centroid localization algorithm based on RSSI for wireless sensor networks [J]. Journal of Wuhan University of Technology （Transportation Science and Engineering Edition）， 2006， 30（2）： 265-268.）

[10] 楊博雄，倪玉華，劉琨，等.基于加權三角質心RSSI算法的ZigBee室內無線定位技術研究[J].傳感器世界，2012（11）：31-35. （YANG B X， NI Y H， LIU K， et al. Study on ZigBee wireless location technology based on weighting triple centroid RSSI algorithm [J]. Sensor World， 2012（11）： 31-35.）

[11] 姚碧超.室內WiFi定位技術研究[D].成都：電子科技大學，2017：41-43.（YAO B C. Research on indoor location technology based on WiFi [D]. Chengdu： University of Electronic Science and Technology of China， 2017： 41-43.）

[12] 朱玲玲，程學云，魏曉寧.基于高斯修正測距模型的節點改進加權質心定位算法設計[J].計算機測量與控制，2012，20（11）： 3089-3091.（ZHU L L， CHENG X Y， WEI X N. Design for improved weighted centroid localization algorism based on Gaussian correction ranging model for sensor node [J]. Computer Measurement and Control， 2012， 20（11）： 3089- 3091.）

[13] 李新春，蘭根.基于定向天線信號強差的定位方法[J].計算機應用與軟件，2016，33（8）：167-171.（LI X C， LAN G. Localisation based on RSSI difference of directional antennas [J]. Computer Applications and Software， 2016， 33（8）： 167-171.）

[14] 任曉奎，張永旺.一種基于正交定向天線的節點定位算法[J].測控技術，2017，36（8）： 107-110.（REN X K， ZHANG Y W. A node localization algorithm based on orthogonal directional antenna [J]. Measurement and Control Technology，2017， 36（8）： 107-110.）

[15] 趙大龍，白鳳山，董思宇，等.一種基于卡爾曼和線性插值濾波的改進三角質心定位算法[J].傳感技術學報，2015，28（7）：1086-1090. （ZHAO D L， BAI F S， DONG S Y， et al. An improved triangle centroid location algorithm based on Kalman filtering and linear interpolation [J]. Chinese Journal of Sensors and Actuators， 2015， 28（7）： 1086-1090.）

[16] 張宏剛，黃華.基于RSSI路徑損耗因子動態修正的三邊質心定位算法[J].傳感技術學報，2016，29（11）：1731-1736. （ZHANG H G， HUANG H. Dynamic correction algorithm for trilateral centroid localization based on RSSI path loss factor [J]. Chinese Journal of Sensors and Actuastors， 2016， 29（11）： 1731-1736.）

[17] 王飛，童敏明，白琪，等.基于RSSI的ZigBee動態加權質心四點定位算法[J].計算機應用研究，2018，35（9）：2663-2665. （WANG F，TONG M M， BAI Q， et al. ZigBee dynamic weighted centroid four points location algorithm based on RSSI[J].Application Research of Computers，2018， 35（9）： 2663-2665.）