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

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

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

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

1.4 未知節(jié)點(diǎn)的鄰居錨節(jié)點(diǎn)少于三個(gè)的情況
    因?yàn)槲粗?jié)點(diǎn)和錨節(jié)點(diǎn)的分布具有很大的隨機(jī)性，所以在網(wǎng)絡(luò)覆蓋區(qū)域的邊緣地帶未知節(jié)點(diǎn)很可能擁有比較少的鄰居錨節(jié)點(diǎn)，致使無(wú)法滿足APIT算法定位條件，甚至當(dāng)鄰居錨節(jié)點(diǎn)少于3時(shí)，未知節(jié)點(diǎn)將不能被定位。如圖4所示，無(wú)論節(jié)點(diǎn)B旁邊的錨節(jié)點(diǎn)怎么組合都無(wú)法將B包含在內(nèi)，而節(jié)點(diǎn)C在通信半徑范圍內(nèi)的錨節(jié)點(diǎn)數(shù)量甚至少于3個(gè)。有文獻(xiàn)提出將已定位節(jié)點(diǎn)升級(jí)為錨節(jié)點(diǎn)參與定位，但是，這將會(huì)帶來(lái)積累誤差[7]。

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

    同時(shí)，利用質(zhì)心加權(quán)法和信號(hào)強(qiáng)度定位的結(jié)果間的誤差為：
    
    (4)網(wǎng)絡(luò)中的未知節(jié)點(diǎn)通信半徑范圍內(nèi)若有符合條件的升級(jí)錨節(jié)點(diǎn)，則可以被未知節(jié)點(diǎn)利用，以滿足APIT算法。
3 算法流程圖
    算法流程圖如圖5所示。

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

　總體而言, 新算法通過(guò)有選擇地將已定為節(jié)點(diǎn)升級(jí)為錨節(jié)點(diǎn)，在降低定位誤差積累、對(duì)定位精度影響不大的情況下，提高了定位覆蓋率。由于無(wú)限傳感器網(wǎng)絡(luò)的各種應(yīng)用差別很大，沒(méi)有普遍適合各種應(yīng)用的定位算法，因此應(yīng)綜合考慮，本文提出的算法具有較強(qiáng)的擴(kuò)展性，對(duì)于大規(guī)模無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位具有參考價(jià)值。
參考文獻(xiàn)
[1] 孫利民，李建中，陳渝，等.無(wú)線傳感器網(wǎng)絡(luò)[M].北京：清華大學(xué)出版社，2005.
[2] 余義斌.傳感器網(wǎng)絡(luò)定位算法及相關(guān)技術(shù)研究[D].重慶：重慶大學(xué)，2006.
[3] 于海斌，曾鵬，智能無(wú)線傳感器網(wǎng)絡(luò)系統(tǒng)[M].北京：科學(xué)出版社，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] 王福豹，史龍，任豐原.無(wú)線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報(bào)，2005(16)：857-868.
[6] 段渭軍，黃曉利，王福豹，等.無(wú)線傳感器網(wǎng)絡(luò)測(cè)距技術(shù)的研究[J].計(jì)算機(jī)科學(xué)，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] 沙超，王汝傳，孫力娟，等.無(wú)線傳感器網(wǎng)絡(luò)中一種信標(biāo)節(jié)點(diǎn)可遷移的協(xié)作定位方法[J]，電子學(xué)報(bào)，2010，38(11)：2624-2629.