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

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

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

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

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

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

3 結(jié)論與展望
    節(jié)點定位技術(shù)是WSNs中關(guān)鍵的支撐技術(shù)之一。本文對APIT定位算法進(jìn)行改進(jìn)，提出了區(qū)域混合感知的近似三角形內(nèi)點測試(RMA_APIT)定位算法。RMA_APIT算法根據(jù)網(wǎng)絡(luò)連接情況，對未知節(jié)點的定位區(qū)域進(jìn)行調(diào)整并引入輔助節(jié)點對未知節(jié)點定位。仿真實驗結(jié)果證明，RMA_APIT算法能夠適應(yīng)無線傳感器網(wǎng)絡(luò)的特點，相比于APIT算法，在節(jié)點數(shù)目相同、錨節(jié)點比重相同的情況下，RMA_APIT算法能夠提供更加優(yōu)質(zhì)的定位服務(wù)，在獲得相同定位精度的要求下，RMA_APIT算法更能節(jié)省網(wǎng)絡(luò)部署的成本。下一步的工作是研究網(wǎng)絡(luò)模型及網(wǎng)絡(luò)部署情況對算法的影響，使算法能夠在更加真實的網(wǎng)絡(luò)環(huán)境中取得理想的定位效果。
參考文獻(xiàn)
[1] 王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報,2005,16(5):857-868
[2] 周四清,陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)[J].計算機(jī)工程,2009,35(7):87-89.
[3] 馮秀芳,崔秀鋒,祈會波.無線傳感器網(wǎng)絡(luò)中基于移動錨節(jié)點的APIT的改進(jìn)定位算法[J].傳感技術(shù)學(xué)報,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] 周勇,夏士雄,丁士飛,等.基于三角形重心掃描的改進(jìn)APIT無線傳感器網(wǎng)絡(luò)自定位算法[J].計算機(jī)研究與發(fā)
展,2009,46(4):566-574.