摘  要： 無線傳感器網絡節點定位機制的研究中，基于距離無關的定位技術得到快速發展，其中基于重疊區域的APIT定位算法在實際環境下定位精度高，被廣泛研究和應用。對APIT定位算法及其改進措施進行了總結，并給出性能比較結果。
關鍵詞： 無線傳感器網絡；APIT；定位算法

    隨著計算機網絡技術、通信技術、嵌入式技術和傳感器技術的飛速發展和日益成熟，具有感知能力、計算能力和通信能力的微型傳感器及其構成的無線傳感器網絡WSN(Wireless Sensor Network)引起了人們的極大關注。這種傳感器網絡具有低功耗、低成本、自組織的能力，能夠自動進行配置和適應環境的變化，具有動態可重構性等特點，能夠通過協作實時監測、感知和采集網絡，分布區域內的各種環境或監測對象的信息并傳送到控制中心，因而被廣泛應用于國防軍事、國家安全、精細農業、環境監測、智能家居、城市交通以及預防與減災、人員營救、目標跟蹤等方面，適用于在人們無法接近的極端惡劣或特殊環境下監測事件發生的地點[1]。
傳感器節點通過飛行器撒播、人工埋置和火箭彈射等方式任意撒落在被監測區域內。節點的位置信息都是隨機的，節點所采集到的數據，若沒有位置信息幾乎沒有應用價值[1]。所以在無線傳感器網絡應用中，節點的定位一直是關鍵問題，同時也是人們研究的熱點。由于傳感器節點采用電池供電，節點數量巨大，成本太高，能量有限。因而利用GPS或其他方式先對網絡中的少量節點(錨節點)進行定位，其他大部分節點以錨節點位置為參考，應用各種定位算法實現自身定位。
    根據目前出現的定位算法對節點位置估測機制的不同可以分為兩大類：基于距離相關的定位算法(Range-Based Localization Schemes)和基于距離無關的定位算法(Range-Free Localization Schemes)。前者需要測量相鄰節點間的絕對距離或方位，并利用節點間的實際距離來計算未知節點的位置；后者不需要自己與錨節點之間的距離或角度信息，而是根據網絡連通性等信息估算出自己與錨節點間的距離。基于距離相關的定位算法使得傳感器節點造價增高，消耗了有限的電池資源，而且在測量距離和角度的準確性方面需要大量的研究。基于距離無關的定位算法則不需要知道未知節點到錨節點的距離或者不需要直接測量此距離，在成本和功耗方面比基于測距的方法具有優勢[1]。如質心算法、DV-Hop、Amorphous和近似三角形內點測試法APIT等。其中，APIT定位算法的基本思想簡單，實現容易。而且由于其定位功耗小、成本低、節點定位精度高等特點得到廣泛應用和研究，其中有不少改進算法的效果更優。本文將基于距離無關的定位算法APIT的相關改進算法進行綜述，以便使APIT算法的研究和應用得到進一步推廣。
1 基于區域的APIT算法
    無線傳感器網絡定位機制中，APIT算法屬于距離無關、區域相關的定位策略。其實現簡單、定位成本低、傳感器節點功耗小、定位精度高，因而得到廣泛應用。它的基本算法是從待定位節點周圍的錨節點中任意選取三個，組合成一個三角形，判斷該點是否位于該三角形內。如果在三角形內，則將其標記，依次對待定位節點周圍的錨節點進行各種不同組合并檢測，最終找出所有滿足要求的三角形重疊區域，求其質心位置以替代待定位節點在網絡中的具體位置坐標。算法原理見圖1。該算法的基本理論依據是最佳三角形內點測試法(PIT)[2]。

1.1 PIT原理介紹

    按上述命題判斷節點M是否處于三個錨節點包圍的三角形之內，條件足夠，但由于實際無線傳感器網絡中撒布的節點規模龐大，而且大部分實際網絡中，節點處于靜止或移動非常緩慢的狀況，因此上述判斷方法不能用于待定位節點的測試。在實際網絡操作中采用近似PIT原理測試。
    近似PIT原理(APIT原理)：如果在待定位節點M的鄰居節點中，沒有同時遠離或接近三個錨節點A、B、C的點，則表明節點M位于該?駐ABC內，否則節點M位于ΔABC外(見圖3)。對于具有N個錨節點的規模網絡，用錨節點間的通信能夠連成C3N個三角形。

1.2 APIT算法實現步驟
    在實際無線傳感器網絡中實現APIT算法可簡要分為四個步驟：
    (1)各節點獲取在其無線射程之內所有錨節點的信息，包括位置坐標、信號強度等信息。
    (2)根據PIT原理進行測試。
    (3)聚集所有滿足條件的三角形，找出其交集。
    (4)計算交集的重心，以其估計待定節點位置。
    根據實現APIT算法的四個步驟，可以寫出其偽代碼：
    Receive location beacons (Xi， Yi) from N anchors；
//取得N個錨節點的位置坐標
InsideSet =Ф；
//對設定用來存放包含待定節點區域的變量InsideSet初始化
for(each triangle Ti∈ triangles){
//窮盡錨節點組成的所有三角形
if (Point-In-Triangle-Test (Ti) == TRUE)
//判斷如果待定位節點位于該三角形內
InsideSet = InsideSet∪{Ti}；
//則將其區域標記，并調用網絡掃描算法
if (accuracy(InsideSet)>enough) break；
//如果定位精度已達要求可提前結束循環
}
Estimated Position=Center Of Gravity(∩Ti∈InsideSet)；
//計算包含待定位節點的公共區域的重心，以其代替待定
//位節點的位置
1.3 APIT算法性能分析
    通過與常見幾種基于距離無關定位算法之間的比較，發現APIT算法在定位精度、硬件成本、節點分布和錨節點密度等方面性能比較優越。性能比較見表1[2]。在錨節點密度增大或鄰居節點數目增多情況下，其定位誤差呈下降趨勢，而且相對其他幾種算法，效果比較明顯。另外，隨著錨節點無線輻射范圍增大，定位誤差上升趨勢略低于其他算法。試驗顯示[2]，在無線信號傳播模式不規則和傳感器節點隨機部署的情況下，APIT算法的定位精度高、性能穩定，測試錯誤概率相對較小(最壞情況下14%)。平均定位誤差小于節點無線射程的40%。該算法最大的優點是與其他非基于距離的算法相比，算法簡單，受節點密度影響較小且節點間通信量少，這就大大降低了功耗，對資源受限的傳感器網絡較為適用。
1.4 APIT存在的問題
    對APIT算法詳細分析發現其存在一定的問題，主要有以下幾點：
    (1)在PIT測試中，如果待定位節點靠近或完全在三角形一條邊上時，將出現OutToIn或InToOut的判斷錯誤問題。
    (2)在PIT測試中，一般采用信號強度來判斷遠離或靠近錨節點，這在實際環境中，既增加了傳感器節點的能耗，同時也增大了判斷誤差。
    (3)對重疊區域重心的計算中，采用的網格掃描算法效率低，計算精度不高。
    (4)如果錨節點或待定位節點周圍鄰居節點密度過小，往往對定位精度和定位覆蓋率造成很大影響，甚至造成一定比率的節點位置不能被定位[3]和定位覆蓋率不高。因此要達到高的性能，就要求錨節點密度和通信范圍增大。
    (5)算法在執行中不僅需要定位節點間與錨節點的信息交互，也需要與鄰居節點間進行信息協調處理，造成網絡節點通信開銷和計算量上升，使得算法的應用受到限制。
2 改進的APIT算法
    針對APIT定位算法存在的問題，人們提出了許多改進措施。這對APIT算法的推進與實際應用起到了積極的作用。
    參考文獻[4]~[7]對問題(1)、(3)進行改進，其中參考文獻[4]提出基于三角形重心掃描的改進算法，在分析APIT中InToOut和OutToIn產生的原因后提出合法三角形區域、非法三角形區域和掃描算法的支持數據集等概念，通過增加對鄰居節點合法性檢查，減少了InToOut錯誤發生次數，降低了邊界效應對APIT測試的影響；通過擴大鄰居節點定義范圍，增加了待定位節點的鄰居節點數目，從而有效減少了OutToIn錯誤的發生次數。參考文獻[5]提出隨著鄰居節點數目的改變，要求待判定節點都遠離三角形三個頂點的鄰居節點的個數要滿足≥n/m的要求(n為待定位節點的鄰居節點個數，m為權重系數)，才能判定待定位節點位于相應三角形的外部。
    參考文獻[8]針對問題(2)、(4)提出：在原有APIT算法的基礎上引入信標節點對待定位節點M坐標估計值影響系數。避免了當待定位節點M比較靠近ΔABC的一條邊，或者M周圍的信標節點分布不均勻時，APIT的判斷出現錯誤。即使APIT算法發生誤判，也可以通過計算信標節點對M坐標估計值影響因子系數來提高定位精度，同時也解決了anchors節點稀疏，APIT算法失效的問題。
參考文獻[9]進一步考慮到網絡中節點通信的安全性而提出改進的SAPIT算法。該算法利用節點通信加密、錨點身份驗證、APIT測試結果安全匯總等方法，實現了APIT算法中的安全定位思想，為今后進一步研究APIT提出了新的思路。
    參考文獻[10]針對問題(4)、(5)，提出環形區域疊加定位算法ROCRSSI(Ring overlapping based on Comparison of Received Signal)，算法所需網絡通信量較低。其優點體現在：(1)不需要未知節點參與發送控制信號，僅需錨節點發送相應的定位控制信息，從而使得其通信代價相對較低；(2)未知節點只是收集相關的錨節點信息，與網絡的連通度和鄰居節點密度無關；(3)采用的圓環疊加方式比三角形疊加范圍更小，提高了定位精度；(4)在不規則的無線通信模式下工作比較正常。
    在對于定位精度方面，參考文獻[11]利用APIT算法中三條邊的中垂線將APIT算法中的三角形分割為4個或6個可用小區域，并以檢測信號的強弱進一步來判定未知節點的位置，從而縮小APIT算法的定位區域，提高定位精度，提出基于中垂線分割的PB-APIT。參考文獻[12]引入網格的思想，將整個監測區域劃分為若干部分，在每個網格范圍內采用隨機的方式放置節點，從而接近節點的均勻分布，因而提出基于網格分布的定位算法。
在定位覆蓋率不足的問題上，參考文獻[13]~[15]分別進行了改進。參考文獻[13]的改進算法增大了anchor節點的覆蓋度，降低了InToOut與OutToIn發生的概率。參考文獻[14]將測距用的接收信號強度指示器RSSI與APIT相結合，引入限定距離的概念，提出改進算法RAPIT(RSSI and APIT)，將引起誤差的節點的位置限定在以錨節點為圓心、以限定距離為半徑的圓的重疊區域內，從而達到減少誤差、提高定位覆蓋度的目的。參考文獻[15]從不同的錨節點比例、節點通信半徑以及同一錨節點比例等方面提出改進的IAPIT算法，提高了定位覆蓋率。
目前，在無線傳感器網絡定位技術中，將多種定位方法混合在一起的作法已經成為一種新的研究方式。參考文獻[16]將APIT和基于信號到達時間差(TDOA)的泰勒級數展開算法(TSE)混合應用，仿真發現其定位精度要高于兩個算法單一定位的情況。
    此外，在三維空間定位方法的研究中，參考文獻[17]提出三維空間內傳感器節點自身定位方法APIT-3D(Approximate-Point-In-Tetrahedron)。通過判斷傳感器節點是否位于由錨節點組成的四面體的內部，篩選出可能的位置區域，并最終計算這些區域交集部分的重心，作為待定位節點的位置。仿真實驗表明，作為一種不基于測量設備的定位方法，APIT-3D可以達到節點通信半徑的40%以下的較高精度的三維定位，而且通信開銷相比于二維定位方法增幅不明顯。APIT-3D定位方法無需復雜的測距設備和昂貴的外部設施，且通信協議相對簡單，因此是一種低成本、低功耗的無線傳感器網絡三維自身定位方法。
    總之，自APIT算法問世以來，人們對其進行了廣泛研究，從二維平面到三維空間，從解決算法存在的問題到改進算法，以及提出定位精度、效能更高的新算法。目前，利用APIT和其他定位算法混合定位的技術更進一步得到人們的青睞。
3 改進算法性能分析總結
    通過以上各種算法的改進措施分析，對原APIT算法存在的有關問題得到不同程度的改進，其性能有一定的提高，部分文獻提出的改進措施經過MatLab仿真，其性能的確優于APIT算法。參考文獻[4]、[8]在網絡規模不大，錨節點分布比較規則且均勻情況下，效果比較明顯，但在節點分布不規則環境下，其算法有待提高。
    分析以上各種改進算法，不難發現各自對APIT中存在的某個或某幾個問題給予了一定的解決，但其中仍然有一些問題，如傳感器規模特大、節點分布隨機而雜亂情況下，傳感器網絡邊緣節點定位情況仍未得到更多關注。另外，在實際環境中，隨機分布的節點受到風力等氣候影響，以及對隨機分布呈三維立體形式的整個網絡節點定位等方面還有待進一步研究，以提高算法執行效率和節點定位精度。
    本文回顧了APIT定位算法的基本原理，分析APIT存在的問題并綜述后期關鍵文獻對不同問題分析和解決的方法，同時對改進算法中存在的問題進行分析并提出一些個人看法，希望在今后的工作中能夠進一步探討這些問題，使APIT算法真正在實際中得以廣泛應用。
參考文獻
[1] 孫利民.無線傳感器網絡[M].北京：清華大學出版社，2008.
[2] He Tian， Huang Chengdu， Blum B M， et al. Range-free localization schemes in large scale sensor networks[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Net-working， MOBICOM’ 2003， San Diego(CA，USA)， 2003.New York( NY，USA) ： ACM Press， 2003： 81- 95.
[3] NAGPAL R， SHROBE H. BACHRACH J. Organizing a global coordinate system from local information on an ad hoc sensor network. In Information Processing in Sensor Networks： Second International Workshop， IPSN2003(Palo Alto， April 2003)， no. 2634 in Lecture Notes in Computer Science， Springer-Verlag.
[4] 周勇，夏士雄.基于三角形重心掃描的改進APIT無線傳感器網絡自定位算法[J].計算機研究與發展，2009，46(4)：566-574.
[5] 曹磊，徐晨.無線傳感器網絡近似三角形內點測試定位算法改進[J].電子技術應用，2007，33(11).
[6] Ji Zeng， Wang Hong， Xu Jin. Improvement on APIT localization algorithms for wireless sensor networks[J]. Proceedings of the 2009 International Conference on Networks Security， Wireless Communications and Trusted Computing， 2009(1)： 719-723.
[7] 張寧，王越，王東.無線傳感器網絡中APIT定位算法的改進[J].工業控制計算機，2009，22(3)：42-43.
[8] 韓彪，徐昌彪，袁海，等.無線傳感器網絡中一種改進的APIT定位算法[J].計算機工程與應用，2008，44(4)：122-124.
[9] 孫庭波，屈玉貴，趙保華.一種無線傳感器網絡安全定位的新方法[J].小型微型計算機系統，2009，130(9)：1738-1741.
[10] 蔣小蘭，鄧平.基于區域重疊的WSN節點自定位新算法[C].信息、電子與控制技術學術會議，2006.
[11] 楊驥，劉鋒.無線傳感器網絡基于中垂線分割的APIT的改進定位算法[J].傳感技術學報，2008，21(8)：1453-1457.
[12] 裴慶祺，趙軍.基于網格分布的三角形內點測試定位算法[J].計算機工程與設計，2008，29(18)：4657-4661.
[13] 趙軍，裴慶祺，徐展琦.無線傳感器網絡近似三角形內點測試定位算法[J].計算機工程，2007，33(5)：109-111.
[14] 馮秀芳，曹美麗，孫超.無線傳感器網絡基于APIT的混合定位算法[J].微電子學與計算機，2009，29(6)：58-61.
[15] 周四清，陳銳標.無線傳感器網絡APIT定位算法及其改進[J].計算機工程，2009，35(7)：87-89.
[16] 謝亞琴，張業榮.基于APIT和TSE算法的混合定位方法[J].南京郵電大學學報(自然科學版)，2007，27(6)：68-71.
[17] 劉玉恒，蒲菊華，赫陽，等.無線傳感器網絡三維自身定位方法[J].北京航空航天大學學報，2008，34(6)：647-651.