文獻標識碼： A
DOI：10.16157/j.issn.0258-7998.19０５０４
中文引用格式： 高媛，陽媛. 基于指紋量化的改進加權質心定位算法[J].電子技術應用，2019，45(9)：77-80，84.
英文引用格式： Gao Yuan，Yang Yuan. An improved weighted centroid location algorithm based on fingerprint quantization[J]. Application of Electronic Technique，2019，45(9)：77-80，84.
0 引言
在無線傳感器網絡[1]技術的應用中，目標定位至關重要。為了獲得更加精確的定位，國內外研究人員提出了多種定位的算法[2-3]，如基于測距的定位算法和基于非測距的定位算法[4-5]。目前研究最廣泛的算法是基于接收信號強度(Received Signal Strength Indication，RSSI)的測距算法，該類算法軟硬件實現起來簡單，功耗和成本都較低，很適合室內的短距離無線定位[6]。將基于RSSI的測距算法與非測距定位算法中的質心算法相結合進行目標定位是目前研究的熱點，但RSSI受環境及節點間距的影響，測距誤差大[7-8]，質心定位算法受到測距誤差的影響，導致定位不準確。為了提高定位精度，文獻[9]提出了一種改進的加權質心迭代算法，將已定位節點升級為參考節點進行后續定位，對不同類型的節點使用不同的權值，然后利用誤差修正因子對定位誤差進行校正。文獻[10]在RSSI測距階段采取卡爾曼濾波平滑優化，之后對定位坐標進行加權和補償。文獻[11]提出基于節點相關系數的RSSI定位算法，利用約束條件選出相關系數較大的區域，在區域內估算RSSI值，同時修改權值。文獻[12]以RSSI值解算的距離值的倒數和作為權重,同時通過實例得出權值修正系數n=6時定位精度最高的結論。
本文在上述算法的基礎上提出了基于指紋量化的改進加權質心定位算法，在一跳范圍內采集實際測量值建立指紋數據庫，避免信號強度衰減造成的測距誤差，然后將目標定位時接收到的一跳范圍內較大的3個信號強度值在指紋數據庫中進行比對，獲得量化距離及量化RSSI值，進一步利用改進的交集三角形加權質心算法對未知節點進行定位，提高了定位的精度。
1 算法實現
指紋量化加權質心定位算法的實現步驟如下：(1)指紋數據庫的建立，通過實際測試，選擇等間隔距離設置若干采樣點，采集適量樣本數據，構建指紋數據庫；(2)量化距離及量化RSSI值的確定：根據參考節點布放的間隔設定量化域，劃分若干量化區間，將指紋數據庫中的樣本數據作為量化區間的端點，目標定位時，將未知節點接收到的RSSI值在量化域中進行比對，確定所在區間，選擇鄰近的量化區間端點，將該端點對應的樣本距離作為未知節點到參考節點的量化距離，對應的樣本RSSI值作為量化RSSI值；(3)交集三角形質心定位算法改進：改進傳統加權質心定位算法權值的選取方式，考慮量化誤差以及未知節點與參考節點的距離，以獲取更加合理有效的權值，提高定位精度。
1.1 指紋數據庫的建立
室內環境下一般障礙物多，環境復雜，造成干擾因素多，RSSI信號衰減嚴重，導致測距模型計算的誤差加大。RSSI理論值與實際值的對比數據如圖1所示。在0～15 m的測試區間內，將發射端AP位置固定，接收端從距離AP 1 m的地方向后移動，每隔任意距離(均小于1 m)測量10個數據，求出信號強度的平均值。可以看到，RSSI測距的實際測量值與理論值之間存在較大的誤差。所以，本文直接選用實際測量值建立指紋數據庫，避免因信號衰減嚴重而造成的理論誤差問題。
在室內選擇N個位置布放參考節點，距離每個參考節點每遠離相同的距離D，以參考節點為圓心，以逐漸增加的距離為半徑，在圓周上不同位置采集N′次RSSI值。為保證定位精度，D值應小于0.5 m。計算N個位置處的以參考節點為圓心、半徑相同的圓周上的RSSI值的平均值作為各個采樣點的RSSI值，該RSSI值與采樣點距離參考節點的實際距離（即圓周的半徑）一起作為該采樣點的指紋樣本，如圖2所示。
設每個采樣點采集的RSSI數據和指紋樣本RSSI數據分別為RSi和RFi，兩者的關系如式(1)所示：
則確定該點的指紋樣本為(RFi，dFi)。
為保證定位精度，設定未知節點定位時僅選用一跳范圍內的參考節點，室內實際參考節點的布放保證未知節點可在一跳范圍內至少接收到3個參考節點的信號。據統計分析，未知節點到可用參考節點的最遠距離小于間距最大的相鄰兩參考節點間的距離，將相鄰兩參考節點間的最大間隔記為Smax，根據上述指紋樣本的確定原則，可得到指紋數據庫如式(2)所示：
1.2 量化距離及量化RSSI值的確定
在目標定位時，未知節點與參考節點間的實際距離是任意數且有無窮多個取值。為快速獲取到兩者間的實際距離，本文采用數字通信技術中的量化思想[13]，設定量化域，劃分量化區間，獲得量化距離。
將指紋數據庫中的指紋樣本數據(RF1，dF1)與(RFi，dFi)之間構成整個量化域，在量化域中根據指紋樣本的數量劃分等量的量化區間，取指紋數據庫中各個指紋樣本(RFi，dFi)作為各量化區間的端點，樣本中的距離值dFi作為量化距離，RSSI值RFi作為量化RSSI值。dFi與dFi-1間的距離為D，RFi與RFi-1間的差值無規律，為任意量。量化的物理過程如圖3所示。
目標定位時，將未知節點接收到的來自參考節點信號的RSSI平均值RA與指紋數據庫中的指紋樣本數據進行比較，當RFi<RA<RFi+1時，RA落在(RFi，dFi)與(RFi+1，dFi+1)確定的量化區間內，此時比較RA分別與RFi、RFi+1的距離差，選擇差值小的指紋樣本數據并作記錄，將該指紋樣本數據中的指紋樣本距離作為此未知節點到參考節點的量化距離，指紋樣本RSSI值作為量化RSSI值。設RA與RFi、RFi+1的差的絕對值分別為RAFi與RAFi+1，計算公式如下：
比較RAFi與RAFi+1的大小，如果RAFi>RAFi+1，說明RA更接近于RFi+1的值，此時選擇指紋樣本(RFi+1，dFi+1)；如果RAFi<RAFi+1，則選擇指紋樣本(RFi，dFi)，未知節點到參考節點的量化距離以及量化RSSI值即可確定。
按照以上方法，未知節點到一跳范圍內的3個參考節點AP1、AP2、AP3的量化距離都能確定，分別記作d1、d2、d3。
當量化距離已確定，則通過交集三角形加權質心算法確定目標位置。
1.3 交集三角形質心定位算法改進
在傳統質心算法的基礎上，為提高定位精度，許多學者針對該算法的原理，對權值進行了改進，提出了一種加權質心算法[14]，將未知節點接收到的RSSI值作為權值，通過這種方式可以反映出參考節點對未知節點的影響程度，從而達到提高定位精度的目的，如式(6)所示：
其中，wi為權值，(x，y)為未知節點坐標，(xi，yi)為參考節點坐標。在實際環境中，單純使用RSSI值作為權值可能會使定位誤差較大，RSSI值隨著距離的增大會不斷減小。
本文提出了一種改進的交集三角形加權質心定位算法，如圖4所示。設參考節點AP1、AP2、AP3的坐標為(xAP1，yAP1)、(xAP2，yAP2)、(xAP3，yAP3)，分別以AP1、AP2、AP3為圓心，量化距離d1、d2、d3為半徑作圓，由式(7)計算3個圓相交的3個點B1、B2、B3的坐標(xB1，yB1)、(xB2，yB2)、(xB3，yB3)。
同理可得B2、B3點的坐標。
由于本文對未知節點到參考節點的實際距離進行了量化，一定會產生相應的量化誤差，參考節點AP1、AP2、AP3與未知節點間的量化距離以及量化誤差的大小同時影響著未知節點的定位，本文對于權值的選擇有以下考慮：
(1)參考節點距離未知節點越近，對未知節點的定位影響越大，故選取
作為權值的參數；
(2)量化誤差越小，對應的參考節點對未知節點的定位影響越大，將量化RSSI值和實際測得的RSSI均值間的差值記為ε，計算式如式(8)所示。
2 算法流程
算法流程如圖5所示。
3 實驗仿真
3.1 實驗環境
本文的實驗選擇在一個10 m×15 m的辦公環境內進行，基于ZigBee定位系統，硬件采用6個CC2530射頻芯片，其中4個作為參考節點，1個作為未知節點，1個作為網關。本文將參考節點位置固定，分別放置在(0.00，0.00)、(9.75，0.00)、(0.00，14.50)、(9.75，14.50)，對未知節點隨機選擇20個位置進行實驗，如圖6所示。星形點“*”表示參考節點，空心圓“o”表示未知節點。
3.2 算法性能估計
3.3 仿真結果與分析
本文首先與基于RSSI的三角加權質心算法進行對比，在相同的實驗環境及實驗參數下，測得數據擬合出兩種算法的誤差對比圖如圖7所示。
從圖6可以看出，三角加權質心算法最大定位誤差為2.3 m，平均定位誤差Err=0.78 m，有40%的未知節點定位誤差在1 m以下，有15%的未知節點定位誤差在0.5 m以下；利用本文算法得到的最大定位誤差為1.6 m，平均定位誤差Err=0.68 m，有70%的點定位誤差在1 m以下，有45%的未知節點定位誤差在0.5 m以下。比較兩種算法，本文算法的定位精度大大高于三角加權質心算法。
文獻[6]的定位算法也是基于RSSI的改進三角加權質心算法，實驗的環境與本文相似。為了進一步測試本文改進定位算法的性能，將其與文獻[6]的定位算法進行測試對比。本文的定位算法與文獻[6]算法的測試對比結果如圖8所示。
從圖8可以看出，在多數點上本文的定位精度都是高于文獻[6]，僅在個別點上定位精度低于文獻[6]，但是差別也很小。所以本文算法的定位精度從總體上來說要高于文獻[6]的算法。
4 結束語
本文提出了一種改進的基于指紋量化的三角加權質心定位算法，采集實際測量值建立指紋數據庫，在量化域內對未知節點接收到的RSSI值進行量化獲得相應量化距離及量化RSSI值，同時考慮將量化距離及量化誤差作為權值參數。實驗結果表明，該算法可以有效避免因信號衰減嚴重而造成的理論誤差問題，提高了定位精度，有一定的實用價值。
參考文獻
[1] 壽向晨，徐宏毅．無線傳感器網絡中RSSI定位算法的設計與實現[J].武漢大學學報(工學版)，2015，48(2)：284－288.
[2] 李銀，汪洋，陳冬明．基于RSSI的無線傳感器網絡定位系統設計與實現[J]．計算機測量與控制，2015，23(3)：1061-1064．
[3] 胡斌斌，倪小軍．基于RSSI測距室內定位改進質心算法[J]．計算機技術與發展，2017，27(8)：133-136．
[4] 楊潤豐，駱春波．基于無線信號接收強度定位的無人機群避碰[J]．電子技術應用，2017，43(4)：117-120.
[5] 孔范增，任修坤，鄭娜娥.基于GDOP權值交點的魯棒AOA定位算法[J].電子技術應用，2016，42(9)：107-110．
[6] 王亞民，王海英，何佩倫.基于RSSI的改進加權質心定位算法[J].計算機工程與設計,2016(11)：2865-2868.
[7] 王群，李宗骍，李千目，等.基于實時運動狀態的RSSI測距室內定位算法[J].南京理工大學學報(自然科學版)，2015，39(2)：229-235.
[8] 羅健宇，張衛強，徐艇.基于RSSI優化模型的室內定位系統[J].無線通信技術，2018(3)：25-30.
[9] 謝樺.基于RSSI的無線傳感網絡加權質心定位算法[D].贛州：江西理工大學，2017.
[10] 劉玉龍.基于RSSI的無線傳感器網絡定位算法的研究與實現[D].沈陽：沈陽航空航天大學，2017.
[11] 王曉彬.基于多維標度與RSSI的室內定位算法研究[D].太原：太原理工大學，2018.
[12] 路澤忠，盧小平，付睢寧.一種改進的RSSI加權質心定位算法[J].測繪科學，2019(1)：26-31.
[13] 陳愛軍.深入淺出通信原理[M].北京：清華大學出版社，2018.
[14] Bai Yun，Li Chunming，Xue Yuan.A centroid localization algorithm for wireless sensor networks based on RSSI[C].Applied Mechanics and Materials，2013：197-200.
作者信息:
高 媛1，陽 媛2
(1.徐州工業職業技術學院，江蘇 徐州221000；2.東南大學 儀器科學與工程學院，江蘇 南京210096)