基于迭代分割的無線傳感器網絡定位算法

張婧，國晶

（長春理工大學 計算機科學技術學院，長春 130022）

隨著物聯網技術的不斷發展，無線傳感器網絡（WSNs，wireless sensor networks）憑借著其低成本、微型化、低功耗和靈活的組網方式、鋪設方式以及適合移動目標等特點稱為物聯網的底層支撐技術［1］。它正被廣泛的應用在國防、醫療、環境、目標跟蹤等多個領域。明確傳感器節點的具體位置，是大多數應用服務中不可或缺的一部分。例如：在國防中只有知道突發事件（如槍聲、爆炸等）的具體位置，軍隊才能夠對事發地及時采取應對措施；對于環境監測中只有知道火災的準確方位才能指導消防人員進行撲火操作；對于入侵監控，只有知道入侵者的行動軌跡才能進行追蹤［2］。因此，無線傳感器網絡定位技術是大多數應用的基礎，如果只知道發生的事件，卻不知道具體的位置，感知的數據可能失去意義。同時，明確傳感器節點所在的位置，可以提高網絡的路由效率，實現網絡的負載均衡和網絡拓撲的自配置，使整個網絡的覆蓋質量得到提升［3］。因此，無線傳感器網絡定位是一項必不可少的關鍵技術。

目前，利用全球定位系統（GPS）來獲取節點的位置信息是比較簡單且常用的方法。然而，由于昂貴的硬件和能源問題，在每個節點上部署GPS顯然不符合WSN中普通節點成本低、體積小的要求。因此，通常利用少量已知位置信息的節點（信標節點），并通過一些定位算法來實現對未知節點的定位［2］。無線傳感器網絡的定位算法可根據是否需要測量節點間的歐氏距離或角度分為基于測距的定位算法與非測距的定位算法。其中基于測距的定位算法有TOA（基于時間的定位方法）［4］、TDOA（基于信號傳輸時間差的定位方法）［5］、AOA（基于信號角度的定位方法）［6］以及RSSI（基于信號強度的定位方法）［7-8］等。非測距定位算法主要有質心算法［9］、APIT算法［10］、DV-Hop算法［11-12］等。由于非測距的定位算法無需增加額外的硬件成本，算法簡單易實現，在能耗方面相比測距的定位算法有一定的優勢，因而針對非測距算法中的APIT進行改進將有一定意義。

國內外學者針對APIT定位算法中存在的定位精度低的問題，提出了不少改進的方法。當未知節點鄰近信標節點分布不均勻或者未知節點靠近由信標節點組成三角形的某一條邊時，APIT算法可能會產生節點誤判（內部節點誤判成外部節點或外部節點誤判成內部節點）。針對節點誤判產生的誤差，文獻［13］利用三角形面積或角度和的方法對節點產生的誤判進行修正。但由于RSSI測距具有不準確性，無法得到精確的面積或角度之和，因而使得未知節點無法準確定位。文獻［14］通過部署虛擬信標節點雖然能夠有效判斷未知節點在三角形的內部還是外部，但部署虛擬信標節點會消耗較多的計算資源以及時間。文獻［15］提出了一種協同系數APIT定位算法，利用RSSI測距和加權三角坐標的計算方法來對未知節點進行定位。雖然達到了減少定位誤差和擴展定位覆蓋率的效果，但該方法大大增加了硬件成本以及能耗。因此，綜合各個改進算法的優勢與弊端，將改進的APIT算法以及質心算法相融合，能夠有效地提高APIT算法的定位覆蓋率以及定位精度。

1 APIT定位算法

1.1 APIT算法定位原理

APIT是一種實現成本較低、操作簡單、易于實現并且定位精度較高的算法。它的基本原理是未知節點首先收集鄰近信標節點的信息，然后從這些信標節點中任意選取三個節點組成三角形。假設集合中有n個信標節點，則共有種不同的選取方法。通過這些不同的選取方法逐一判斷未知節點是否位于每個三角形的內部。最后，通過計算包含目標節點所在的三角形的重疊區域的質心，并將質心作為未知節點所在的位置。如圖1所示，P點為重疊區域的質心，即未知節點所在的位置［10，13］。

圖1 APIT定位原理

由于在無線傳感器網絡中大多數節點都是靜止的，所以APIT利用網絡中相對較高的節點密度來模擬節點移動，利用無線信號的傳播強弱來描述是否遠離或靠近信標節點。其判定原理如圖2所示，如果節點P運動至1的位置，將同時遠離信標節點A、B、C，則P點在DABC外。另外，如果節點P運動至節點1的位置，將靠近A遠離B、C，并依次對2、3、4進行相同的判斷，則可判定未知節點P在DABC內。

圖2 PIT原理

1.2 APIT算法存在的誤差

（1）In-To-Out和Out-To-In錯誤

在APIT定位算法中，當節點的密度較低時，可能會產生內部節點錯判成外部節點（In-To-Out）和外部節點錯判成內部節點（Out-To-In）的錯誤。如圖3（a）所示，當未知節點P模擬運動2或3的位置時，未知節點P沒有同時靠近或遠離三個信標節點A、B、C，則可能發生Out-To-In錯誤［15］。同理，圖3（b）未知節點P模擬運動到4的位置時，同時遠離三個信標節點，則被判定未知節點在三角形外，可能產生 In-To-Out錯誤［15］。

（2）重疊區域過大引起的誤差

當節點分布不均勻或部分未知節點鄰近的信標節點數量較少時，可能會導致包含目標節點所在的三角形的重疊區域過大，進而將其重疊區域的質心作為未知節點的坐標會造成較大的誤差。

圖3 誤差分析

2 改進的APIT算法

2.1 三角形內點的判定

為了盡量減少APIT算法中的In-To-Out和Out-To-In引起的誤差以及盡可能的提高定位精度。判定內點的方法如下：

根據同向法對節點進行判定。同向法的基本原理為：假設存在一個點P以及DABC。判斷P點是否在DABC內。則需判斷：

（1）P點和A點在BC這條直線的同一側；

（2）P點和B點在AC這條直線的同一側；

（3）P點和C點在AB這條直線的同一側。

同時滿足上述三種條件，則證明P點在DABC內，否則，P點在DABC外。

如圖4所示，判斷P點和A點在BC這條直線的同一側，則過A點作BC的垂線交于F點，即∠AFB=∠AFC=90°。

若P點和A點在同一側，

則∠AFP＜∠AFB，∠AFP＜∠AFC

故∠AFP＜90°

否則，∠AFP＞90°

圖4 同側判定方法

通過上述證明，同理如圖5所示，可得到如下命題：

命題1：若未知節點P在由三個信標節點組成的DABC內，則∠AFP，∠BHP，∠CMP的角度均小于90°。

命題2：若未知節點P在由三個信標節點組成的DABC外，則∠AFP，∠BHP，∠CMP中必然存在一個角大于90°。

其中F、H、M分別為A點、B點、C點到對邊的垂足。

圖5 角度判定

相應角度的計算方式如下：

（1）通過RSSI測距的數學模型公式［9］：

式中，d0為參考距離；Pr(d0)表示無線信號對應的接收功率；Pr(d)為接收機接收到的無線射頻信號功率；n為傳播因子；d表示信號的發射機器與接收機器之間的距離，即未知節點與信標節點之間的距離。

（2）如圖6所示，通過兩點間的距離公式求出三個信標節點A（x1，y1），B（x2，y2），C（x3，y3）之間的距離為：

（3）由點到直線的距離公式求出AF的距離：

其中已知A、C的坐標，則a=y3-y2，b=x2-x3，c=x3×y2-x2×y3。

由余弦定理可得：

（4）求出判定角度：

圖6 角度計算

如果存在某一個三角形包含未知節點，則該三角形被定義為有效三角形。為了得到更精確的定位結果，即對有效三角形可進行區域的劃分與迭代，最終求出未知節點的坐標。

2.2 有效三角形的劃分與迭代

為了進一步提高未知節點的定位精度，在判定未知節點在三個信標節點所組成的三角形內之后，可以通過作垂線的方法來縮小未知節點所在區域。如圖7所示，A，B，C為信標節點。在DABC內，角度由小到大的排列順序為∠A，∠B，∠C，過C點作AB的垂線交于F點，即可求出最小角度A、垂足F以及未知節點P組成的角度∠AFP的大小。若∠AFP＞90°，則未知節點P在DBCF內，否則，未知節點P在DACF內。

圖7 區域劃分

通過上述方法進行迭代分割，可得到如圖8所示的迭代示意圖。P點為未知節點，三個信標節點組成的三角形為DABC，最大角度為∠C，最小角度為∠A。迭代過程如下：

（1）過A點作BC的垂線交于F點，求出F點的坐標以及通過RSSI測距得到AP、BP、CP的距離；

（2）利用余弦定理可求出∠AFP角度。

（3）若 ∠AFP＞90°，則P點在DABF區域。否則，P點在DACF區域并保留P點所在的區域。假設P點在DABF區域，即令DABF中的最大角度為∠A，最小角度為∠C。

（4）重復以上步驟，直到P點所在的三角形區域為網格所能查找到的最小定位的區域（利用網格掃描法［16］所能探測到的最小單元格區域）為止。

（5）迭代結束。

圖8 迭代示例圖

綜上，改進APIT算法的流程圖如圖9所示。

圖9 APIT算法流程圖

3 算法仿真

為了驗證算法的有效性，通過MATLAB分別利用原始APIT算法、文獻［13］提出基于角度和改進的APIT算法以及基于迭代分割的無線傳感器網絡定位算法進行仿真實驗，并結合實驗數據對三個算法進行性能分析與比較。實驗場景設定在1 000 m×1 000 m的二維平面內，節點隨機分布在監測區域內。

在仿真實驗中，RSSI的各個參數值如表1所示。

表1 實驗參數

場景1：設定通信半徑R=100，節點總數N=300。平均運行50次，可得到如表2所示數據。

通過對實驗數據表2的分析，可得出當節點總數不變時，待定位節點的平均定位誤差和信標節點比例之間的關系，如圖10所示。

圖10 節點比例與定位誤差對比圖

原始APIT算法和文獻［13］利用角度和改進的APIT算法的平均定位誤差隨著信標節點比例的增加而減小。這是因為信標節點比例增加的同時，包含未知節點所在的三角形的重疊區域會隨之減小，使得定位誤差越來越小。如圖10所示，基于迭代分割的無線傳感器定位算法隨著信標節點比例的增加，定位誤差趨于穩定且一直保持較高的精度。因為基于迭代分割的無線傳感器定位算法運用最小三角形迭代思想求出包含未知節點的最小區域代替原始算法中多個三角形的重疊區域。總之，兩種改進算法的定位精度均高于原始APIT算法的定位精度，并且基于迭代分割的無線傳感器定位算法的定位精度最高。

場景2：設定通信半徑R=100，信標節點的個數為：anchors=nodes·ρ，ρ=0.3。平均運行50次，可得到如表2所示數據。

通過對實驗數據表3的分析，得到待定位節點的平均定位誤差和節點數量之間的關系，如圖11所示。

圖11 節點數量與定位誤差對比圖

表2 實驗數據

表3 實驗數據

當信標節點比例不變時，隨著區域內節點數量的增加，使得待定位節點鄰近信標節點的數量不斷增加，故節點的平均定位誤差的變化趨勢同樣會隨著節點數量的增加而減小。基于迭代分割的無線傳感器網絡定位算法的定位精度明顯優于原始APIT算法和文獻［13］利用角度和改進的APIT算法的定位精度。

通過場景1與場景2的比較分析，基于迭代分割的無線傳感器網絡定位算法的定位精度比利用角度和改進的APIT算法平均提高15.1%，較原始APIT算法平均提高24.6%。

4 結論

針對APIT定位算法存在的誤差，基于迭代分割的無線傳感器定位算法主要從兩個方面進行了誤差修正。首先，對于APIT算法存在的兩種典型錯誤In-To-Out和Out-To-In錯誤，引入了一種新的判斷內部節點的方法，該方法能夠有效的避免上述兩種錯誤的產生；其次，當未知節點被判定在三角形內部的情況下，利用迭代分割方法進一步縮小三角形區域，從而確定最終定位區域。通過上述兩種方法進行了多次仿真實驗，結果表明，基于迭代分割的無線傳感器定位算法可有效降低定位誤差，且當信標節點比例不高或者節點密度變大時能夠保持算法的穩定性。