三角質心迭代與Bounding-Box的定位算法

程良 張永強 王艷娥 司海峰 李璐

關鍵詞：無線傳感器網絡；PIT法則；估計矩形；質心迭代

無線傳感器網絡作為一個應用廣泛的技術，具有自組網、健壯性強等特點，備受研究者們關注[1]。現階段的定位算法主要分為兩類：基于測距以及非測距[2]。相比測距算法，非測距算法具有通信開銷小、功耗低等優點，得到了廣大研究人員的認可，是現階段研究工作的重點之一[3]。

現階段較為流行且先進的無線傳感器網絡定位算法有以下幾種。文獻[4]對邊界盒定位算法進行了改進，該算法主要是通過縮小定位區域來提高精度；文獻[5]綜合測距與非測距定位算法的特點進行定位，根據RSSI值來計算相關權重來提高定位精度。文獻[6]找出錨節點組成的三角形中最小的那一個作為閾值三角形，來進一步確定為未知節點坐標。文獻[7]采用極限分割的思想，將Bounding-box算法中形成的估計矩形進行了無限次分割來提高定位精度。本文通過分析基本Bounding-Box 算法原理，將原始矩形進行一次分割后，采用三角質心迭代的方式來極限逼近未知節點，從而減小了平均相對定位誤差，提高了定位準確度。

1 Bounding-Box 算法簡介

Bounding-Box 算法的基本工作原理：在一個二維區域內，待定位節點接收到周圍最近三個錨節點的信號強度，然后以該錨節點為圓心，通信距離為半徑畫圓，同時將三個圓的外接矩形求出，以它們重合區域的質心作為未知節點的位置[8]，可將該算法分為3個步驟。

1） 在一個二維平面內，隨機布置多個錨節點和未知節點，錨節點將自身的位置信息廣播至整個網絡。在該網絡中，錨節點發送的信號能被未知節點接收到的稱為最近錨節點。

2） 以未知節點周圍錨節點為圓心，它們的通信距離為半徑畫圓，得到圓的外切正方形。

3） 將第二步得到的各外接矩形的重合區域作為初步定位區域，即初步未知節點的預估位置為該重合區域的中心位置。如圖1所示，外接矩形的重疊部分區域是一個平行X 軸和Y 軸的矩形，分別將該矩形的左、右、上、下四個邊記為left、right、up以及down，并且求出該重合矩形的中心位置，以此作為最終估計位置。

2 算法改進

分析Bounding-box算法可知，只通過鄰居錨節點所得到的外切正方形重合區域質心作為未知節點的位置估計會造成較大誤差。文中采用分割的思想，將定位區域逐漸縮小，從而降低算法的平均相對定位誤差。

改進過程可分為三步：

第一步：估計初始位置坐標

通過定位算法求解的外切正方形所形成的重合矩形可作為初步的定位區域，求出該區域的中心點位置坐標（x0，y0 ），將該坐標作為初步的定位位置。

第二步：找到最近錨節點

對未知節點接收到周圍錨節點的信號強度值進行標記：

第三步：三角形質心迭代

1） 一次分割

Bounding-Box算法得到的最初估計區域是根據最近錨節點畫通信圓，每個圓的外接矩形形成的重合矩形部分為最初定位區域。將該定位區域的中心位置坐標記為（x0，y0 ），以該坐標為中心，將該重合矩形分成四個子矩形，分別記為B1、B2、B3 、B4且大小分別為式（3）～式（6）。

如圖2所示，其中（xi，yi ）分別作為鄰居錨節點的坐標位置，R為通信半徑。由四個子矩形得到的質心稱為偏移質心（xes，yes ），其中s 下標代表的是不同的子矩形。采用兩點距離公式求出偏移質心到最近錨節點的距離，設為dist，如式（7）所示：

找出最近距離min（dist），假設B2子矩形的質心到最近錨節點A1最近，將B2的質心（xe2，ye2 ）稱為待選質心。求初始位置坐標和待選質心的中點坐標GS1為（xs1，ys1 ），再計算該中點坐標到最近錨節點的距離dis，并且以A1為圓心，dis 為半徑畫圓，交估計矩形于Q，K 兩點。將距離dis 帶入式（8）求出對應的信號強度RSS （dis），比較RSS （dis） 與max（RSS） 大小關系，若RSS （dis）

2） PIT法則

對于WSN的拓撲網絡，各節點都屬于靜止狀態，所以不能采用PIT法則進行未知節點位置的判斷。為了達到實驗效果，采用近似PIT的方法，因為未知節點和錨節點之間可以進行信號強度的接收，所以利用這種信號強度隨距離變化的關系就可以模擬未知節點的運動情況，進而對未知節點的位置進行判斷。

由于未知節點可以探測到周圍錨節點的信號強度大小，所以可以讀出三個鄰居節點M1，M2，M3的信號強度值。假設X 運動到其中一點，就可以認為未知節點的信號強度變成了該點的信號強度，從而判斷出移動的過程中未知節點與三個頂點間信號強度的變化關系，同理遠離也一樣，進而就可以判斷出未知節點是否在三角形M1，M2，M3中。

一次分割完成后，以最近錨節點A1 為圓心，A1 到GS1 為半徑畫圓，得到與B2區域的兩個焦點設為Q，K，連接Q，K，A1 構成三角形。通過PIT法則判斷，如果未知節點在三角形內部，則求其質心P1，否則以Q，K，P1為三個頂點組成新的三角形繼續迭代，直到未知節點不在三角形Q，K，Pn內部，迭代終止。算法流程如下：

步驟1：計算未知節點到Q，K，P1，P2...Pn的距離

如果在一個二維區域內，存在一個未知節點O（x，y ），它周圍的鄰居錨節點分別為A1，A2...An，設第n 個信標節點的坐標為（xn，yn ），則未知節點到鄰居錨節點距離dn為：

通過兩點間距離公式可得質心坐標到未知節點的距離，記為ds。

因此，由公式推導可得：若知道dn，則可以求出未知節點O 到質心S的距離ds。以質心S 為圓心，ds 為半徑作一個圓MO 的方程。過質心S 分別與Q 和K 連接形成的直線交于圓MO，設交點坐標分別為U 和V，將QU 與KV 之間的距離近似當作Q到未知節點和K到未知節點的距離。

步驟2：三角形質心迭代定位

進行三角形質心迭代定位之前，要先確定未知節點是否在相應的三角形內。由步驟1知道未知節點分別到Q、K的距離后，利用PIT法則判斷出未知節點是否處于三角形A1，Q，K 內，因為Q，K 處于未知節點和最近錨節點形成的同心圓內，所以將Q，K 固定不變并且與質心P1 形成新的三角形，然后通過PIT法則判斷。若未知節點在三角形QKP1 內，則繼續進行迭代運算，直到未知節點不在新構成的三角形Q，K，Pn 內，否則算法迭代終止。

設未知節點到Q，K，P1，P2...Pn的距離為d3。

找出d3 中最小的距離記為min（d3 ），則對應的質心為最終位置估計。隨著迭代次數的增加，若未知節點處于Q，K 所構成的直線附近，那么會有無限次的迭代，因此需要設置迭代閾值。

設dpn 與通信半徑r 的比值為誤差ξ，如果ξ 小于設定閾值，則迭代終止，如式（16）所示。

3 仿真實驗

3.1 實驗設計

該實驗利用Matlab 為仿真工具，來模擬仿真這幾種算法分別在不同環境下的平均定位誤差精度。文中新設計的算法記作TCIBounding - Box 算法，文獻[4-7]中所提到的定位算法分別記為RBounding - Box、RSSI - Centroid、APIT - Minimum 以及DBounding - Box。監測區域設計為100m × 100m，其中設節點數個數為N，錨節點的個數為M，節點通信半徑為R，其中設PT=0dB，d0=1m，PT（d0）=55dB，?=4，ξ=0.1。設網絡中定位算法的平均相對定位誤差為E，計算公式如式（17）。

其中（xr，yr）是未知節點的估計坐標，（xt，yt）是未知節點的真實坐標，k為拓撲次數，nr 參與定位的未知節點個數。

為了使實驗結果更具有說服性，將每次實驗產生的拓撲場景分別提供給以上算法進行對比。

3.2 節點數對定位精度的影響

節點總數是衡量一個拓撲網絡整體性能的重要參數，節點過多會提高成本，錨節點過少會影響實驗精度。因此，本實驗設錨節點數為0.2N，通信半徑為30m，仿真結果如圖5所示。

分析圖5可得，隨著節點數越來越多，TCIBounding- Box 算法相比于傳統算法、RBounding - Box、RSSI - Centroid、APIT - Minimum 以及DBounding - Box 算法的定位誤差分別降低了14.12%，6.72%，5.09%，3.53% 以及2.68%。

3.3 錨節點數的影響

錨節點作為整個WSN網絡位置信息的參考點，數量決定著定位精度。實驗中設N為100，R為30m，k= 100次。如圖6是錨節點數量從20增至80的仿真圖。

由圖6可得，錨節點越多，算法的平均定位誤差越小。文中TCIBounding-Box 分別較傳統算法，文獻[4-7]提到的算法，在平均定位誤差上分別降低了6.19%，5.42%，4.22%，3.77%以及2.68%。

3.4 通信半徑對定位精度的影響

由分析得，通信半徑對外接矩形區域大小有影響。如果通信半徑距離過小，會導致部分節點不能參與定位。實驗中節點個數和錨節點個數按照一定比例投放，保證其他條件都不變的情況下，通信半徑對實驗的影響。圖7為仿真圖。

分析圖7可知，文中提出的TCIBounding-Box 算法相比于傳統的算法在平均定位誤差上減少15.42%。文獻[4]中的算法在平均定位誤差上相比于傳統算法有所降低，但與文中所提算法相比，定位精度降低了7.15%。文獻[5]中的定位算法，在精度上與文中所提算法相比降低了5.25%。文獻[6]中的算法降低了3.60%。文獻[7]中的算法降低了2.66%。

4 結束語

本文先對Bounding-Box算法進行了研究分析，并在該基礎上利用最近錨節點將產生的外接矩形區域進行一次分割，以此進一步縮小定位區域。通過判斷未知節點是否在最近錨節點的通信圓內，對定位區域進一步縮小，然后通過三角形質心迭代思路不斷縮小定位區域。仿真實驗表明，在不同節點個數，錨節點個數以及通信半徑下，本文所提出的TCIBounding- Box算法均有效減小了平均定位誤差。