無線傳感器網絡(WSNs)的大量應用都需要網絡中節點的地理位置信息。另外，了解傳感器節點位置信息還可以提高路由效率，為網絡提供命名空間，向部署者報告網絡的覆蓋質量，實現網絡的負載均衡及網絡拓撲的自配置[1]。無線傳感器網絡的定位問題主要分為兩類：(1)無線傳感器網絡對自身傳感器節點的定位； (2)利用傳感器節點對外部目標的跟蹤定位，而節點自身的定位是實現外部目標跟蹤定位的基礎[2]。參考文獻[1]對目前存在的部分定位算法的原理及特點做了詳盡的分析和描述，并給出了定位系統和定位算法的性能評價參數。到目前為止，現有的無線傳感器網絡節點定位算法都有各自的特點和應用范圍，根據定位的需求，各算法在性能評價參數上各有取舍,沒有哪一種算法是絕對優秀的。綜合考慮算法的各個性能評價參數，使節點的定位精度最優是定位算法的主要目標。定位算法的分類有很多種,根據定位過程中是否測量實際節點間的距離，可以把現有的定位算法主要分為兩類:基于距離(Range-based)的定位算法和與距離無關(Range-free)的定位算法[3]。基于距離的定位算法利用RSSI、TDOA、TOA和AOA等技術測量節點之間的距離,然后用數學方法計算節點的坐標,該定位算法能夠實現節點的精確定位，但對節點的硬件要求比較高。由于硬件成本、能耗等原因，人們提出了與距離無關的定位技術。與距離無關的定位算法對硬件要求比較低，定位精度隨之降低，但是能夠滿足大多數應用的要求，典型的與距離無關定位算法主要有MDS算法、DV-HOP算法、Amorphous算法、Centroid算法等。

    本文首先深入分析現有近似三角形內點測試(APIT)[4]定位算法的原理和性能，針對目前該算法仍然存在的問題，并充分考慮無線傳感器網絡的特點，提出一種區域混合感知的近似三角形內點測試(RMA_APIT)定位算法。其核心思想是節點根據網絡的連接情況應用不同的方法感知節點定位區域，目的是為了自動調整節點的定位區域， 從而提高定位精度。通過一系列的仿真實驗證明，RMA_APIT算法能夠很好地適應WSNs的特點,相比于APIT算法, RMA_APIT算法能夠提供更加精確的定位服務。
1 RMA_APIT理論模型和算法描述
1.1 APIT算法
　    APIT定位算法是一種基于區域的定位算法[5]，其核心思想是把鄰居錨節點組成的多個三角形的交疊區域的質心作為節點的估計位置。APIT算法假設網絡中的節點具有獲取鄰居節點信息的能力，未知節點在通信傳播過程中獲取所有鄰居錨節點的信息以及所有鄰居節點的信息，信息包括鄰居錨節點的位置信息、未知節點及鄰居節點到達錨節點的能量信息。假設未知節點i共有n個鄰居錨節點,則n個鄰居錨節點可以組成Cn3個三角形,對所有包含該未知節點i的三角形求交疊區域,交疊區域的質心即為未知節點i的估計位置。
    APIT算法具有定位精度高、通信開銷小等優點[6]，它能夠很好地適應WSNs中的節點定位，但深入研究APIT算法原理及其流程后，可以發現APIT算法也有不足之處：
    (1)未知節點的鄰居錨節點數小于3時，未知節點就成為不可定位節點；
    (2)未知節點具有3個或者3個以上鄰居錨節點，但節點在任何3個鄰居錨節點組成的三角形外部時，未知節點就成為不可定位節點；
    (3)未知節點的鄰居錨節點數較少，如只有3個鄰居錨節點時，鄰居錨節點能組成的三角形數較少，InToOut錯誤或OutToIn錯誤對節點的定位有較大影響；
    (4)未知節點在部署區域的邊緣時，未知節點的某一側不會出現鄰居錨節點，這樣會使得未知節點不在鄰居錨節點組成的三角形內部，導致未知節點成為不可定位節點。
    針對APIT存在的諸多弊端，本文提出一種改進算法，即區域混合感知的APIT定位算法(RMA_APIT)。該算法根據網絡連接情況，對節點的定位區域進行了調整，以減少不可定位節點數目及提高節點定位精度。
1.2 網絡模型及假設
    為方便對RMA_APIT算法進行理論闡述,假設網絡中的所有節點部署在邊長為R的正方形區域內。網絡中普通節點的通信半徑γ，錨節點的通信半徑是普通節點的α(α＞1)倍，節點的鄰居錨節點數閾值為K。網絡中的所有節點都可以獲得鄰居節點的信息。另外，根據無線傳感器網絡在應用中的特點，模型假設節點的通信區域不一定為理想的圓形區域。
1.3 RMA_APIT算法
    仔細分析APIT算法存在的問題可以發現，應用APIT算法不能進行定位的節點可以分為兩類：第一類，鄰居錨節點數大于等于3而不能進行定位的未知節點；第二類,鄰居錨節點數小于3而不能進行定位的未知節點。
    為有效減少第一類不可定位節點的數目，不是直接判斷未知節點i是否在錨節點組成的三角形MNP內部，而是在節點進行定位前判斷未知節點的鄰居錨節點數是否大于閾值K，若大于則用APIT進行定位；若節點的鄰居錨節點數小于等于閾值K，如圖1所示，圖中設K=3，則采用下述區域混合感知技術進行定位。

    首先，如圖1所示，圖中三角形實心點表示錨節點，圓形實心點表示普通節點，錨節點的通信區域是以錨節點為圓心、錨節點通信半徑αγ為半徑的圓形區域，且未知節點一定在其鄰居錨節點的通信區域內，所以未知節點i一定在其鄰居錨節點M、N、P通信區域的交疊區域內，即圖中A區域。
    然后判斷未知節點是否在錨節點M、N、P組成的三角形內部。若未知節點i不在三角形MNP內部或InToOut錯誤時，則A區域即為未知節點i的定位區域，即A區域的質心位置為未知節點i的估計位置，如圖1(a)所示。若未知節點i在三角形MNP的內部，則用三角形MNP與A區域的交疊區域作為未知節點i的定位區域，即圖1(b)中的B區域，B區域的質心即為未知節點i的估計位置。通過區域混合感知技術可對鄰居錨節點數小于閾值K的未知節點進行更加精確的定位。
    針對第二類不能定位節點，本文引入輔助節點進行定位。首先對整個網絡中的節點進行第一輪定位，記錄下不能定位的節點j；然后判斷未知節點j的鄰居錨節點數與已經被定位的鄰居節點數之和是否大于等于3個，如果未知節點j的鄰居錨節點數與已經被定位的鄰居節點數之和大于等于3個,則把已經定位的鄰居節點當做輔助錨節點,應用RMA_APIT算法對未知節點j進行第二輪定位，否則未知節點視為不可定位節點，如圖2所示，圖中三角形空心點表示輔助錨節點。

    基于以上描述，給出RMA_APIT定位算法的執行流程圖，如圖3所示。
2 仿真結果及分析
    為了有效評估RMA_APIT算法的性能，本文通過仿真實驗的方法將其與APIT算法進行比較分析。
2.1 仿真實驗設計
    影響節點定位精度的因素很多，本實驗主要選擇節

2.2 仿真結果分析
    圖4和圖5分別給出了節點數目對節點定位精度及ELR的影響。從圖4中可以看出，隨著節點數目的增加，兩種算法的定位精度都在提高，但在相同節點數目的情況下，RMA_APIT算法的定位精度比APIT算法的定位精度高。圖5仿真結果顯示節點有效定位比隨著節點數目增加而增加；在節點數目很低或很高時，兩種算法的節點有效定位比很接近，節點數目在100~350之間時，RMA_APIT算法的節點有效定位比明顯高于APIT算法的節點有效定位比，這是因為在節點數目很低時，未知節點的鄰居節點數目都很少，RMA_APIT算法的區域混合感知技術受到限制，能夠引入輔助節點進行定位的節點數少，故節點有效定位比不會有明顯提高；在節點數目很高時，兩種定位算法的節點有效定位比都接近1，因此也比較接近；當節點數目在100~350之間時，RMA_APIT算法能夠很好地調整未知節點的定位區域，并引入輔助節點進行定位，可以很好地減少不能定位的節點數，故RMA_APIT算法的節點有效定位比要明顯高于APIT算法的節點有效定位比。

    圖6和圖7顯示了錨節點比重對節點定位精度和ELR的影響。仿真的節點數目為200時，錨節點比重從0.05逐漸增加到0.4。從仿真結果可以看出，隨著錨節點比重的增加，RMA_APIT算法和APIT算法的定位精度與節點有效定位比ELR都在增加。在錨節點比重相同的情況下，RMA_APIT算法的節點有效定位比全部大于APIT算法的節點有效定位比，RMA_APIT算法的定位精度也普遍比APIT算法的定位精度高，只有在錨節點比重很小(Ar=0.05)時，RMA_APIT算法的定位精度比APIT算法的定位精度稍低，這是因為錨節點數太少會導致節點定位誤差較大，若再引入輔助節點進行定位，會使誤差累積太大，從而影響RMA_APIT算法在低錨節點比重場景下的整體性能。

3 結論與展望
    節點定位技術是WSNs中關鍵的支撐技術之一。本文對APIT定位算法進行改進，提出了區域混合感知的近似三角形內點測試(RMA_APIT)定位算法。RMA_APIT算法根據網絡連接情況，對未知節點的定位區域進行調整并引入輔助節點對未知節點定位。仿真實驗結果證明，RMA_APIT算法能夠適應無線傳感器網絡的特點，相比于APIT算法，在節點數目相同、錨節點比重相同的情況下，RMA_APIT算法能夠提供更加優質的定位服務，在獲得相同定位精度的要求下，RMA_APIT算法更能節省網絡部署的成本。下一步的工作是研究網絡模型及網絡部署情況對算法的影響，使算法能夠在更加真實的網絡環境中取得理想的定位效果。
參考文獻
[1] 王福豹,史龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-868
[2] 周四清,陳銳標.無線傳感器網絡APIT定位算法及其改進[J].計算機工程,2009,35(7):87-89.
[3] 馮秀芳,崔秀鋒,祈會波.無線傳感器網絡中基于移動錨節點的APIT的改進定位算法[J].傳感技術學報,2011,24(2):269-274.
[4] HE T, HUANG C, BLUM B M, et al. Range-free localization schemes for large scale sensor networks[C]. Proceedings of ACM MobiCom, San Diego, California, USA,2003:81-95.
[5] MA D, Meng J E, Wang Bang,et al. Range-free wireless sensor networks localization based on hop-count quantization[J]. Springer,2010, DOI:10.1007/s11235-010-9395-y.
[6] 周勇,夏士雄,丁士飛,等.基于三角形重心掃描的改進APIT無線傳感器網絡自定位算法[J].計算機研究與發
展,2009,46(4):566-574.