信號強度反演的質心迭代定位算法

高淼 王迪 魯國陽 李景偉 王東方 李松杰

摘要：針對無線傳感器網絡節點定位精度會受環境噪聲影響的問題，提出信號強度反演算法和三角形質心迭代定位算法。首先，將未知節點接收到鄰居錨節點的信號強度作為反演信號強度，反演信號強度被轉化為未知節點的發射功率，鄰居錨節點將接收到未知節點的信號強度轉化為錨節點的發射功率，再將信號強度反演給未知節點，通過循環的反演關系降低環境噪聲對信號強度的影響，并求出接近理想傳播模型下的信號強度，從而校正鄰居節點關系。由未知節點與鄰居錨節點之間的信號強度關系得到迭代的三角形質心。通過不斷迭代，使得三角形質心逼近未知節點的真實位置，并結合信號強度的反演算法得到較好的定位精度。仿真結果表明，信號強度反演算法有效優化節點鄰居關系，在此基礎上采用質心迭代算法提高定位精度。

關鍵詞：無線傳感器網絡;信號強度;反演算法;質心迭代定位

中圖分類號： TP212.9文獻標志碼： A文章編號：1674–5124（2021）12–0092–06

Centroid iterative localization algorithm with signal strength reversal

GAO Miao1，WANG Di1，LU Guoyang1，LI Jingwei1，WANG Dongfang1，LI Songjie2

（1. China Tobacco Henan Industrial Co.， Ltd.， Zhengzhou 450016， China;

2. School of Software， Zhengzhou University， Zhengzhou 450001， China）

Abstract： Aiming at the problem that the node positioning accuracy of Wireless Sensor Network （WSN） will be affected by the environmental noise， the signal strength reversal algorithm and the triangle centroid iteration localizationalgorithmare proposed. Firstly，thesignalstrengthreceived bythe unknownnodefromthe neighbor anchor node is regarded as the inversion signal strength which is converted into the transmission power of the unknown node. Then， the signal strength received by the neighbor anchor node from the unknown node can be converted into the transmission power of the neighbor anchor. The cyclic reversal can reduce the influence of environmental noise on the signal strength， which can get the signal strength close to the ideal propagationmodelforcorrectingtheneighbor noderelationship. Finally，thesignalstrengthrelationship between the unknown node and the neighbor anchor node can generate iterative triangle centroid and the continuous iteration makes the centroid approach the real position of unknown node， which combines with the signalstrength reversalalgorithmtogeta better positioningalgorithm. Simulation resultsshowthatthe centroid iteration algorithm can be used to improve the positioning accuracy based on the neighbor noderelationship optimized by the signal strength reversal algorithm.

Keywords： wireless sensor network; signal strength; reversal algorithm; centroid iterative localization

0引言

定位技術在無線傳感器網絡（wireless sensornetwork， WSN）的實際應用中起著至關重要的作用，為了提供準確的位置信息，傳感器節點必須能夠實現自定位來估計位置信息[1]。目前，衛星定位系統在許多領域得到了廣泛的應用[2]，但由于成本高，在一些特殊應用中安裝維護相對困難，不適合大規模部署。因此，在傳感器網絡中，只有少數節點配備了衛星定位系統來獲取位置信息，而大多數節點仍然需要采用自定位技術來估計位置信息。近年來，研究人員提出了一些定位算法來估計節點設備的位置信息[3]。根據定位機制的不同，定位方案可分為兩類：基于測距定位和非測距定位。基于距離的定位方法相對精確，包括 TOA[4]、TDOA[5]、AOA[6]、 RSSI[7]算法等。非測距方案基于網絡連通性信息，常用的無距離定位算法，包括質心算法[8]、DV-hop算法[9]、Amorphous 算法[10]、APIT 算法[11]以及一些相應的改進算法。

盡管目前有很多對于定位算法的研究，但大多數的定位技術是在理想的通信信號傳播模型下進行改進。實際上，在 WSN 定位算法的研究中，各向異性的物理層非理想特性會導致定位精度下降[12]，這種現象相對普遍，也不容忽視。隨著定位算法越來越多，在理想通信信號傳播模型下對定位算法的研究難以滿足實際應用的需要[13]。因此，在有環境噪聲的情況下，如何抑制定位誤差已成為無線傳感器網絡定位的一個重要課題。文獻[14]采用質心迭代定位算法提高節點的定位精度。在文獻[14]的基礎上，文獻[15]將兩次的柵格掃描與三角形質心迭代算法相結合，在理想通信信號傳播模型下提高了定位精度，且兩種算法不考慮未知節點位于三角形外部的定位情況。

文中提出信號強度反演算法來降低加性高斯白噪聲對信號強度的影響，從而校正鄰居節點關系，使得節點網絡的鄰居節點關系更接近于理想情況下的節點關系。通過信號強度的反演算法求出接近理想通信信號傳播模型下的信號強度，文中進一步提出新的三角形質心迭代算法，并提出未知節點位于三角形外部的定位方法。

1 WSN 通信信號傳播模型

在 WSN 中，信號強度的衰減模型分為理想模型和不規則模型。在不規則模型的下研究定位算法具有一定的應用價值。在理想模型中，節點所形成的通信區域是一個圓形，理想模型可表示為[16]

式中：P（d）——接收信號的功率;

PT——發送信號的功率;

PL（d0）——參考距離為 d0時的路徑損耗功率，一般 d0=1 m;

η——路徑損耗指數;

d——發射信號的節點與接收信號的節點之間距離。

如圖1所示，在通信半徑內，節點 B 為節點 A 的鄰居節點，而節點 C 不是節點A 的鄰居節點。

可將式（1）寫成

其中，Pc=PT?PL（d0），則信號強度與距離的關系可以寫成

Log-normal 模型是通過在理想通信模型中加入高斯白噪聲而建立的不規則通信信號傳播模型， Log-normal 模型可表示為[16-17]

其中σ是由陰影衰落引起的高斯隨機變量，即加性高斯白噪聲。如圖2所示，在通信半徑內，受加性高斯白噪聲的影響，節點 C 被誤判為節點 A 的鄰居節點，而屬于節點 A 的鄰居節點 B 被誤判成非鄰居節點。

2信號強度反演的質心迭代算法

文中針對 Log-normal 模型對定位精度的影響提出信號強度的反演算法還原理想的信號強度，從而達到抗噪聲的目的。結合反演算法，進一步提出質心迭代定位算法提高定位精度。

2.1信號強度反演算法

將鄰居錨節點的信號強度由強到弱排序作為為反演信號強度序列。實際上，由于受到加性高斯白噪聲的影響，未知節點接收到的最大信號強度不一定來自最近錨節點，但不影響信號強度的反演。未知節點接收的信號強度會受加性高斯白噪聲σ的影響，則未知節點接收到的信號強度為

不失一般性，設到達未知節點處的最大理想信號強度為 P（Am，1），未知節點將接收的信號強度 P（Am，2）反演給各鄰居錨節點，則錨節點接收到未知節點的反演信號強度為

將式（6）中的鄰居錨節點接收反演信號強度再反演給未知節點，則未知節點接收到鄰居錨節點的反演信號強度為

如圖3所示為未知節點與鄰居錨節點之間信號強度的反演關系。

由反演關系得到最大信號強度的鄰居錨節點和未知節點之間的加性高斯白噪聲σ與未知節點接收的反演信號強度關系。

從而得到鄰居錨節點與未知節點之間相對接近理想通信信號傳播模型下的信號強度。

因此，信號強度的反演可以優化未知節點在通信半徑內對鄰居錨節點成員的判決。

2.2質心迭代定位算法

將信號強度反演得到的 P（Am，1）代入式（2），從從而將信號強度轉化為距離，鄰居錨節點之間的距離可通過坐標直接轉化。如圖4（a）所示，設AmAm+1=a， AmAm+2=b，Am+1Am+2=c，Am U=e0，Am+1 U=e1，Am+2 U= e2。在定位時，節點的通信半徑相等，判定未知節點是否位于三個錨節點所在的三角形內部，則

質心判定條件為：當∠Am UAm+1+∠Am UAm+2+∠Am+1 UAm+2=360°，則未知節點位于三角形內部;反之，判定未知節點位于三角形外部。

設錨Am 的坐標為（xam，yam），當未知節點位于三角形內部時，三角形的質心 C1為

將質心 C1與三個錨節點組合成三個子三角形，由質心坐標可得 Am C1=f1，Am+1 C1=f2，Am+2 C1=f3，則

計算質心與未知節點間的距離，即

如圖4（b）所示，通過將 UC1的值與式（11）的計算原理結合，由質心判定條件得到未知節點位于其中的一個子三角形中。以此方式迭代 n 次，使得UCn的距離逐漸減小。當 n 為無窮大時，UCn為0，則 Cn 的坐標為未知節點的實際位置。對迭代算法設置所需的定位精度指標可使得算法停止迭代，定位精度指標為

其中 r 表示網絡中節點的通信半徑。

當未知節點位于三角形外部時，以未知節點為圓心，以其中一個錨節點為與未知節點的距離為半徑，形成圓 U。如圖4（c）所示，在圓 U 上尋找軌跡點 Bm，使得軌跡點與兩個鄰居錨節點形成三角形。采用平均分割圓的方法尋找軌跡點 Bm，將圓分別進行2，3， ··· ， n 等分后分別存在2，3， ··· ， n 個圓上的點，n 為正整數，n 最小時可取到未知節點在軌跡點與錨節點形成的三角形內時停止對圓的等分，并確定該軌跡點 Bm 為形成三角形所需的定點。與未知節點在三角形內部時的判定方法和迭代方法相同，當判定未知節點在三角形內部時，確定軌跡點，并停止尋找軌跡點，降低算法的復雜度，采用質心迭代求解未知節點的坐標。

3算法仿真及對比分析

在200 m×200 m 的監測區域內隨機產生 k 個不同的節點網絡，設置路徑損耗系數η=4，k=100。控制節點總數，錨節點數，通信半徑，在Matlab上對算法的定位性能進行仿真，節點網絡中的未知節點的平均定位誤差為[15]

式中：（xu， yu）——第 u 個未知的位置估計;

（xtu， ytu）——第 u 個未知節點的實際位置;

ij——網絡中可定位未知節點的個數。

在有加性高斯白噪聲的 Log-normal 模型下對算法的節點關系的校正性能和定位精度測試。

設網絡中的總節點數為150個，其中錨節點為總節點數的0.3倍，通信半徑設置為30 m。如圖5所示，星形表示錨節點，圓圈表示未知節點。由于受到加性高斯白噪聲的影響，節點的鄰居關系與理想的節點鄰居關系差異較大，而采用信號強度的反演算法使得鄰居節點關系與理想的鄰居節點關系相近，從而到達校正網絡中節點關系的效果。因此，未知節點的鄰居錨節點一定程度上得到修正。

將三角形質心迭代算法標記為 TC 算法，結合信號強度反演的三角形質心定位算法標記為 SRTC算法，且定位精度指標 Ind 分別設置為0.1和0.2。在有加性高斯白噪聲的 Log-normal 模型下對算法的定位誤差進行仿真。當錨節點數為總節點數的0.3倍，通信半徑為30m 時，節點總數由50個遞增到400個，定位精度如圖6（a）所示。在 Log-normal模型下不采用信號強度反演算法時，定位誤差較大，約為52.28%，將質心迭代算法結合信號強度反演算法時，定位精度指標 Ind 分別為0.1和0.2時的定位誤差分別為10.92%和20.85%。將節點總數設置為200個，通信半徑為30 m，錨節點數由20個增加到100個，算法定位誤差如圖6（b）所示。在 Log-normal 模型下不采用信號強度反演算法時，定位誤差較大，約為53.06%，將質心迭代算法結合信號強度反演算法時，定位精度指標 Ind 分別為0.1和0.2時的定位誤差分別為13.99%和25.66%。當網絡中的節點總數為200個，錨節點數為60個，通信半徑由20 m 增大到80 m，定位誤差如圖6（c）所示。在Log-normal 模型下不采用信號強度反演算法時，定位誤差較大，約為 55.09%，將質心迭代算法結合信號強度反演算法時，定位精度指標 Ind 分別為0.1和0.2時的定位誤差分別為11.49%和21.14%。

當設置定位精度指標來停止算法迭代時，網絡中的定位誤差基本在定位精度指標值的基礎上存在較小程度的波動。因此，定位精度指標可以用來調節未知節點的所需要滿足的定位精度。文獻[15]中的算法定位精度在改變節點總數，錨節點數和通信半徑時，定位誤差的曲線變化幅度較大，與文獻[15]的定位算法相比，文中 SRTC 算法的定位精度曲線隨著節點總數，錨節點數和通信半徑變化較為平穩。文獻[15]的算法是在理想模型下進行仿真，定位精度的測試效果難以滿足實際環境下的需求，而文中在 Log-normal 模型下通過信號強度反演有效提高了定位精度，因此，文中的定位算法一定程度上優于文獻[15]的定位算法。

4結束語

文中首先提出信號強度的反演算法來抗加性高斯白噪聲，在反演算法的基礎上提出三角形質心迭代算法來提高無線傳感器網絡節點在 Log-normal 模型下的定位精度。通過信號強度的反演有效修正了網絡中的鄰居節點關系，達到校正未知節點的鄰居錨節點成員的效果，有利于節點定位誤差的抑制。通過反演算法求解節點之間的信號強度，推導出對未知節點的位置估計與實際位置之間的偏移距離，從而使得迭代質心不斷靠近真實位置。文中提出的算法對實際環境下的定位精度具有一定程度上的提高。

參考文獻

[1]危華明. WSN 雙迭代柵格掃描定位算法[J].中國測試， 2020，46（12）：135-141.

[2]曹志斌， 楊衛， 邵星靈， 等.基于眾數判定的 PIR 傳感器網絡目標定位方法[J].中國測試， 2018， 44（7）：110-115.

[3]彭臻， 王田， 王文華， 等.傳感網中目標的移動式定位跟蹤研究綜述[J].中南大學學報（自然科學版）， 2017， 48（3）：701-711.

[4] SHI Q， CUI X， ZHAO S， et al. Sequential TOA-based moving targetlocalizationinmulti-agentnetworks[J]. IEEE Communications Letters， 2020， 24（8）：1719-1723.

[5] ZOUY，LIUH. Semidefiniteprogrammingmethodsfor alleviating clock synchronization bias and sensor position errors inTDOAlocalization[J]. IEEESignalProcessingLetters，2020， 27：241-245.

[6] ZHANG F， SUN Y， WAN Q. Calibrating the error from sensorpositionuncertaintyinTDOA-AOAlocalization[J]. Signal Processing， 2020， 166：107213-107213.

[7]LAM? K? H，? CHEUNG? C? C，? LEE? W? C.? RSSI-Based? LoRaLocalization? Systems? for? Large-Scale? Indoor? and? OutdoorEnvironments[J]. IEEE? Transactions? on? VehicularTechnology， 2019， 68（12）： 11778-11791.

[8]KWANG-YUL K， YOAN S. A distance boundary with virtualnodes? for? the? weighted? centroid? localization? algorithm[J].Sensors， 2018， 18（4）： 1-10.

[9]SHARMA? G，? KUMAR? A.? Improved? DV-Hop? localizationalgorithm? using? teaching? learning? based? optimization? forwireless? sensor? networks[J].? Telecommunication? Systems，2018， 67（8）： 1-16.

[10]LI S， DING X， YANG T. Analysis of five typical localizationalgorithms? for? wireless? sensor? networks[J]. Wireless? SensorNetwork， 2015， 7（4）： 27-33.

[11]LIU? J，? WANG? Z，? YAO? M，? et? al.? VN-APIT：? virtual? nodesbased? range-free? APIT? localization? scheme? for? WSN[J].Wireless Networks， 2016， 22（3）： 867-878.

[12]HUANG J F， CHANG G Y， CHEN G H. A Historical-beaconaided? localization? algorithm? for? mobile? sensor? networks[J].IEEE Transactions on Mobile Computing， 2015， 14（6）： 1109-1122.

[13]HE? D，? MUJICA? G，? LIANG? G，? et? al.? Radio? propagationmodeling and real test of ZigBee based indoor wireless sensornetworks[J]. Journal? of? Systems? Architecture，? 2014，? 60（9）：711-725.

[14]蔣銳， 楊震. 基于質心迭代估計的無線傳感器網絡節點定位算法[J]. 物理學報， 2016， 65（3）： 9-17.

[15]宋海聲， 周浩， 朱長駒， 等. 二次柵格掃描與三角形質心迭代的定位算法[J]. 計算機工程與科學， 2019， 41（2）： 268-274.

[16]宋海聲 ，? 朱長駒 ，? 吳佳欣 ，? 等 .? 基于 RSS 閾值模型的Amorphous 算法定位誤差抑制[J]. 計算機工程與科學，2018， 40（5）： 821-828.

[17]劉三陽， 胡亞靜， 張朝輝. 基于 RSSI 測距的 DV-Hop 算法[J]. 控制與決策， 2017， 32（10）： 1900-1904.

（編輯：劉楊）