摘 要: 分析了無線傳感器網(wǎng)絡(luò)分布邊緣地帶可能存在錨節(jié)點密度過小而造成的未知節(jié)點不能利用APIT法定位情況,有選擇地將定位精度較高的已定位節(jié)點升級為錨節(jié)點,繼續(xù)采用APIT定位,擴(kuò)大APIT算法適用范圍并防止誤差過度積累。通過仿真,在對定位精度影響不大的情況下提高了定位覆蓋率。
關(guān)鍵詞: 無線傳感器網(wǎng)絡(luò);節(jié)點;定位;APIT
隨著通信技術(shù)、嵌入式計算技術(shù)和傳感器技術(shù)的飛速發(fā)展和日益成熟,無線傳感器網(wǎng)絡(luò)節(jié)點技術(shù)得到快速發(fā)展。根據(jù)定位機(jī)制可將無線傳感器網(wǎng)絡(luò)WSN(Wireless Senor Network)節(jié)點自身定位算法分為兩類[1]:基于距離的(Range-Based)定位算法和不基于距離的(Range-Free)定位算法。Range-Free主要有基于接收信號強(qiáng)度衰減的定位(RSSI)及其改進(jìn)算法[2]、基于到達(dá)時間的定位(TOA)和基于到達(dá)時間差的定位[3]、基于角度的定位(AOA)[4]。Range-Free定位算法無需節(jié)點間的距離和角度信息,僅根據(jù)網(wǎng)絡(luò)連通性等信息實現(xiàn)定位,在成本、功耗等方面具有很大優(yōu)勢,對硬件要求較低,主要有質(zhì)心算法、DV-HOP算法、Amorphou算法[5]、HOP-TERRAIN算法、APIT算法等[6],特別是APIT算法備受關(guān)注。然而,無線傳感器節(jié)點的分布具有隨機(jī)性,當(dāng)錨節(jié)點密度過小時,傳統(tǒng)APIT算法定位覆蓋率下降。本文通過將已定位節(jié)點有選擇地升級為錨節(jié)點,繼續(xù)應(yīng)用APIT算法定位,在防止定位誤差過度積累的同時提高了節(jié)點定位覆蓋率。
1 APIT定位算法
1.1 PIT算法定位基本原理
最佳三角形內(nèi)點測試法PIT(Perfect Point-In-Triangulation Test)原理如圖1所示,假如存在一個方向,M點沿著這個方向會同時遠(yuǎn)離或接近A、B、C,則M位于△ABC外,否則M位于△ABC內(nèi)。
1.2 APIT算法定位原理
為了能在靜態(tài)網(wǎng)絡(luò)中執(zhí)行PIT測試,定義APIT(Approximate Point-In-Triangulation Test):假如節(jié)點M的鄰居節(jié)點中沒有同時遠(yuǎn)離或者靠近三個錨節(jié)點A、B、C的節(jié)點,則節(jié)點M就在△ABC內(nèi),否則M在△ABC外。利用無線傳感器較高的節(jié)點密度來模擬節(jié)點移動,在給定方向上,距離錨節(jié)點越遠(yuǎn)接收信號越弱,利用這一無線傳播特性來判斷與錨節(jié)點的遠(yuǎn)近。通過鄰居節(jié)點之間的信息交換,仿效PIT測試,如圖2(a)所示,節(jié)點M通過與鄰居節(jié)點1交換信息,得知如果自身移動到節(jié)點1將遠(yuǎn)離錨節(jié)點B和C,但會接近A,與鄰居節(jié)點2、3、4的通信和判斷過程類似,最終確定自身位于△ABC內(nèi);而圖2(b)中,節(jié)點M可知若自身運(yùn)動至節(jié)點4,則同時遠(yuǎn)離錨節(jié)點A、B、C,最終判斷出自身在△ABC外。
在APIT算法中,一個未知節(jié)點在其通信半徑內(nèi)任選3個錨節(jié)點,測試自己是否位于它們所組成的三角形中,使用不同錨節(jié)點的組合重復(fù)測試,直到窮盡所有組合或達(dá)到所需的定位精度。最后計算包含目標(biāo)節(jié)點的所有三角形重合區(qū)域的質(zhì)心,將這一點作為未知節(jié)點的位置。
1.3 in-to-out error與out-to-in error
在某些情況下,APIT算法也存在誤判情況。如圖3(a)所示,當(dāng)未知節(jié)點靠近三角形的一邊,且鄰居節(jié)點2位于三角形內(nèi)時,根據(jù)APIT定義,若未知節(jié)點M移動至節(jié)點2,則同時遠(yuǎn)離錨節(jié)點A、B和C,從而做出M位于△ABC外的錯誤判斷,稱為in-to-out error;當(dāng)節(jié)點M的鄰居節(jié)點分布如圖3(b)所示時,就會做出M在△ABC內(nèi)的錯誤判斷,稱為out-to-in error。
1.4 未知節(jié)點的鄰居錨節(jié)點少于三個的情況
因為未知節(jié)點和錨節(jié)點的分布具有很大的隨機(jī)性,所以在網(wǎng)絡(luò)覆蓋區(qū)域的邊緣地帶未知節(jié)點很可能擁有比較少的鄰居錨節(jié)點,致使無法滿足APIT算法定位條件,甚至當(dāng)鄰居錨節(jié)點少于3時,未知節(jié)點將不能被定位。如圖4所示,無論節(jié)點B旁邊的錨節(jié)點怎么組合都無法將B包含在內(nèi),而節(jié)點C在通信半徑范圍內(nèi)的錨節(jié)點數(shù)量甚至少于3個。有文獻(xiàn)提出將已定位節(jié)點升級為錨節(jié)點參與定位,但是,這將會帶來積累誤差[7]。
試驗顯示[7],在無線信號傳播模式不規(guī)則和傳感器節(jié)點隨機(jī)部署的情況下,APIT算法定位精度高、性能穩(wěn)定、測試錯誤概率相對較小(最壞情況下14%),平均定位誤差小于節(jié)點無限射程的40%。與其他Range-Free算法相比本算法最大的優(yōu)點是更為簡單,節(jié)點密度影響小且節(jié)點間通信量少,大大降低了功耗,相對于資源受限的傳感器網(wǎng)絡(luò)比較合適。但是在同一錨節(jié)點比例下,隨著未知節(jié)點數(shù)目的增加,定位覆蓋率急劇下降,說明APIT算法不具有很好的擴(kuò)展性。隨著網(wǎng)絡(luò)部署規(guī)模擴(kuò)大,將會有更多的節(jié)點得不到有效利用。
2 APIT算法改進(jìn)
參考文獻(xiàn)[8]提出了信標(biāo)節(jié)點可遷移的方法,本文將該方法與APIT結(jié)合,提出IAPIT算法。算法的主要思想是,當(dāng)未知節(jié)點在通信半徑內(nèi)錨節(jié)點不足3個時,使未知節(jié)點在其通信范圍內(nèi)的已定位節(jié)點Mj(j∈{1,2,…,N})有選擇地升級為錨節(jié)點,然后再繼續(xù)運(yùn)用APIT算法定位。已定位節(jié)點有選擇地升級為錨節(jié)點的方法如下:
(1)已定位節(jié)點Mj向其通信半徑內(nèi)所有錨節(jié)點廣播包含其ID的數(shù)據(jù)包;
(2)已定位節(jié)點Mj的所有鄰居錨節(jié)點根據(jù)各自收到的數(shù)據(jù)包值計算出錨節(jié)點和已定位節(jié)點間的距離,由凸規(guī)法可知,僅當(dāng)不等式組(1)成立時,已定位節(jié)點的范圍可以確定,此時未知節(jié)點升級為候選錨節(jié)點,若不等式組無解,則已定位節(jié)點無法升級。
同時,利用質(zhì)心加權(quán)法和信號強(qiáng)度定位的結(jié)果間的誤差為:
(4)網(wǎng)絡(luò)中的未知節(jié)點通信半徑范圍內(nèi)若有符合條件的升級錨節(jié)點,則可以被未知節(jié)點利用,以滿足APIT算法。
3 算法流程圖
算法流程圖如圖5所示。
4 性能仿真
4.1 仿真環(huán)境和參數(shù)
仿真環(huán)境采用Visul C++和Matlab,每次仿真都運(yùn)行算法50次,然后求平均值得到結(jié)果,仿真相關(guān)參數(shù)如下:
(1)節(jié)點部署的網(wǎng)絡(luò)區(qū)域為40 m×40 m的正方形,節(jié)點總數(shù)為100、150、200和300四種情況,所有節(jié)點都隨機(jī)分布在該區(qū)域;
(2)未知節(jié)點和錨節(jié)點通信半徑取為10 m;
(3)測距誤差取為0~30%真實距離的隨機(jī)分布,以接近最壞情況;
(4)定位結(jié)果誤差門限ε=5 m,δ=5 m,σ=3 m。
4.2 IAPIT仿真結(jié)果
以相同的錨節(jié)點與未知節(jié)點密度比列對定位覆蓋率和定位精度進(jìn)行仿真。如圖6(a)所示,IAPIT算法定位覆蓋率最高可達(dá)到90%,較傳統(tǒng)APIT算法有所提高。從圖6(b)可知,未知節(jié)點定位精度變化不大。
總體而言, 新算法通過有選擇地將已定為節(jié)點升級為錨節(jié)點,在降低定位誤差積累、對定位精度影響不大的情況下,提高了定位覆蓋率。由于無限傳感器網(wǎng)絡(luò)的各種應(yīng)用差別很大,沒有普遍適合各種應(yīng)用的定位算法,因此應(yīng)綜合考慮,本文提出的算法具有較強(qiáng)的擴(kuò)展性,對于大規(guī)模無線傳感器網(wǎng)絡(luò)節(jié)點定位具有參考價值。
參考文獻(xiàn)
[1] 孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005.
[2] 余義斌.傳感器網(wǎng)絡(luò)定位算法及相關(guān)技術(shù)研究[D].重慶:重慶大學(xué),2006.
[3] 于海斌,曾鵬,智能無線傳感器網(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ǎng)絡(luò)中的自身定位系統(tǒng)和算法[J].軟件學(xué)報,2005(16):857-868.
[6] 段渭軍,黃曉利,王福豹,等.無線傳感器網(wǎng)絡(luò)測距技術(shù)的研究[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ǎng)絡(luò)中一種信標(biāo)節(jié)點可遷移的協(xié)作定位方法[J],電子學(xué)報,2010,38(11):2624-2629.