摘  要： 無線傳感器網(wǎng)絡(luò)節(jié)點定位機制的研究中，基于距離無關(guān)的定位技術(shù)得到快速發(fā)展，其中基于重疊區(qū)域的APIT定位算法在實際環(huán)境下定位精度高，被廣泛研究和應(yīng)用。對APIT定位算法及其改進措施進行了總結(jié)，并給出性能比較結(jié)果。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)；APIT；定位算法

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

1.1 PIT原理介紹

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

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