摘  要： 分析了無線傳感器網絡分布邊緣地帶可能存在錨節點密度過小而造成的未知節點不能利用APIT法定位情況，有選擇地將定位精度較高的已定位節點升級為錨節點，繼續采用APIT定位，擴大APIT算法適用范圍并防止誤差過度積累。通過仿真，在對定位精度影響不大的情況下提高了定位覆蓋率。
關鍵詞： 無線傳感器網絡；節點；定位；APIT

　隨著通信技術、嵌入式計算技術和傳感器技術的飛速發展和日益成熟，無線傳感器網絡節點技術得到快速發展。根據定位機制可將無線傳感器網絡WSN（Wireless Senor Network）節點自身定位算法分為兩類[1]：基于距離的(Range-Based)定位算法和不基于距離的(Range-Free)定位算法。Range-Free主要有基于接收信號強度衰減的定位(RSSI)及其改進算法[2]、基于到達時間的定位(TOA)和基于到達時間差的定位[3]、基于角度的定位(AOA）[4]。Range-Free定位算法無需節點間的距離和角度信息，僅根據網絡連通性等信息實現定位，在成本、功耗等方面具有很大優勢，對硬件要求較低，主要有質心算法、DV-HOP算法、Amorphou算法[5]、HOP-TERRAIN算法、APIT算法等[6]，特別是APIT算法備受關注。然而，無線傳感器節點的分布具有隨機性，當錨節點密度過小時，傳統APIT算法定位覆蓋率下降。本文通過將已定位節點有選擇地升級為錨節點，繼續應用APIT算法定位，在防止定位誤差過度積累的同時提高了節點定位覆蓋率。
1 APIT定位算法
1.1 PIT算法定位基本原理
    最佳三角形內點測試法PIT（Perfect Point-In-Triangulation Test）原理如圖1所示，假如存在一個方向，M點沿著這個方向會同時遠離或接近A、B、C，則M位于△ABC外，否則M位于△ABC內。

1.2 APIT算法定位原理
    為了能在靜態網絡中執行PIT測試，定義APIT（Approximate Point-In-Triangulation Test）：假如節點M的鄰居節點中沒有同時遠離或者靠近三個錨節點A、B、C的節點，則節點M就在△ABC內，否則M在△ABC外。利用無線傳感器較高的節點密度來模擬節點移動，在給定方向上，距離錨節點越遠接收信號越弱，利用這一無線傳播特性來判斷與錨節點的遠近。通過鄰居節點之間的信息交換，仿效PIT測試，如圖2（a）所示，節點M通過與鄰居節點1交換信息，得知如果自身移動到節點1將遠離錨節點B和C，但會接近A，與鄰居節點2、3、4的通信和判斷過程類似，最終確定自身位于△ABC內；而圖2（b）中，節點M可知若自身運動至節點4，則同時遠離錨節點A、B、C，最終判斷出自身在△ABC外。

    在APIT算法中，一個未知節點在其通信半徑內任選3個錨節點，測試自己是否位于它們所組成的三角形中，使用不同錨節點的組合重復測試，直到窮盡所有組合或達到所需的定位精度。最后計算包含目標節點的所有三角形重合區域的質心，將這一點作為未知節點的位置。
1.3 in-to-out error與out-to-in error
    在某些情況下，APIT算法也存在誤判情況。如圖3(a)所示，當未知節點靠近三角形的一邊，且鄰居節點2位于三角形內時，根據APIT定義，若未知節點M移動至節點2，則同時遠離錨節點A、B和C，從而做出M位于△ABC外的錯誤判斷，稱為in-to-out error；當節點M的鄰居節點分布如圖3(b)所示時，就會做出M在△ABC內的錯誤判斷，稱為out-to-in error。

1.4 未知節點的鄰居錨節點少于三個的情況
    因為未知節點和錨節點的分布具有很大的隨機性，所以在網絡覆蓋區域的邊緣地帶未知節點很可能擁有比較少的鄰居錨節點，致使無法滿足APIT算法定位條件，甚至當鄰居錨節點少于3時，未知節點將不能被定位。如圖4所示，無論節點B旁邊的錨節點怎么組合都無法將B包含在內，而節點C在通信半徑范圍內的錨節點數量甚至少于3個。有文獻提出將已定位節點升級為錨節點參與定位，但是，這將會帶來積累誤差[7]。

    試驗顯示[7]，在無線信號傳播模式不規則和傳感器節點隨機部署的情況下，APIT算法定位精度高、性能穩定、測試錯誤概率相對較小(最壞情況下14%)，平均定位誤差小于節點無限射程的40%。與其他Range-Free算法相比本算法最大的優點是更為簡單，節點密度影響小且節點間通信量少，大大降低了功耗，相對于資源受限的傳感器網絡比較合適。但是在同一錨節點比例下，隨著未知節點數目的增加，定位覆蓋率急劇下降，說明APIT算法不具有很好的擴展性。隨著網絡部署規模擴大，將會有更多的節點得不到有效利用。
2 APIT算法改進
    參考文獻[8]提出了信標節點可遷移的方法，本文將該方法與APIT結合，提出IAPIT算法。算法的主要思想是，當未知節點在通信半徑內錨節點不足3個時，使未知節點在其通信范圍內的已定位節點Mj(j∈{1，2，…，N})有選擇地升級為錨節點，然后再繼續運用APIT算法定位。已定位節點有選擇地升級為錨節點的方法如下：
    (1)已定位節點Mj向其通信半徑內所有錨節點廣播包含其ID的數據包；
    (2)已定位節點Mj的所有鄰居錨節點根據各自收到的數據包值計算出錨節點和已定位節點間的距離，由凸規法可知，僅當不等式組（1）成立時，已定位節點的范圍可以確定，此時未知節點升級為候選錨節點，若不等式組無解，則已定位節點無法升級。

    同時，利用質心加權法和信號強度定位的結果間的誤差為：
    
    (4)網絡中的未知節點通信半徑范圍內若有符合條件的升級錨節點，則可以被未知節點利用，以滿足APIT算法。
3 算法流程圖
    算法流程圖如圖5所示。

4 性能仿真
4.1 仿真環境和參數
    仿真環境采用Visul C++和Matlab，每次仿真都運行算法50次，然后求平均值得到結果，仿真相關參數如下：
    (1)節點部署的網絡區域為40 m×40 m的正方形，節點總數為100、150、200和300四種情況，所有節點都隨機分布在該區域；
    (2)未知節點和錨節點通信半徑取為10 m；
    (3)測距誤差取為0～30%真實距離的隨機分布，以接近最壞情況；
    (4)定位結果誤差門限ε=5 m，δ=5 m，σ=3 m。
4.2 IAPIT仿真結果
    以相同的錨節點與未知節點密度比列對定位覆蓋率和定位精度進行仿真。如圖6（a）所示，IAPIT算法定位覆蓋率最高可達到90%，較傳統APIT算法有所提高。從圖6（b）可知，未知節點定位精度變化不大。

　總體而言, 新算法通過有選擇地將已定為節點升級為錨節點，在降低定位誤差積累、對定位精度影響不大的情況下，提高了定位覆蓋率。由于無限傳感器網絡的各種應用差別很大，沒有普遍適合各種應用的定位算法，因此應綜合考慮，本文提出的算法具有較強的擴展性，對于大規模無線傳感器網絡節點定位具有參考價值。
參考文獻
[1] 孫利民，李建中，陳渝，等.無線傳感器網絡[M].北京：清華大學出版社，2005.
[2] 余義斌.傳感器網絡定位算法及相關技術研究[D].重慶：重慶大學，2006.
[3] 于海斌，曾鵬，智能無線傳感器網絡系統[M].北京：科學出版社，2006.
[4] NICULESCU D，NATH B.Ad Hoc positioning system(APS) using AOA[A].Proc.of the IEEE INFOCOM2003[C].Vol.3，San Francisco：IEEE Computer and Communications Societies，2003.
[5] 王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報，2005(16)：857-868.
[6] 段渭軍，黃曉利，王福豹，等.無線傳感器網絡測距技術的研究[J].計算機科學，2007(9)：51-62.
[7] HE T，HUANG C D，BLUM B M，et al.Range-free localization schemes in large scale sensor networks[C].In Proc. ACM/IEEE 9th Annu.Int.Conf.Mobile Computing and Networking(MobiCom’03)，2003.
[8] 沙超，王汝傳，孫力娟，等.無線傳感器網絡中一種信標節點可遷移的協作定位方法[J]，電子學報，2010，38(11)：2624-2629.