無線傳感器網(wǎng)絡(luò)中APIT
--VP三維定位算法*

陳月娥， 余 敏

(江西師范大學(xué) 計算機信息工程學(xué)院，江西 南昌 330022)

0 引 言

無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)具有隨機部署、覆蓋范圍廣、網(wǎng)絡(luò)自組織、魯棒性強等優(yōu)點，故其應(yīng)用范圍非常廣泛，如環(huán)境保護、軍事監(jiān)控、醫(yī)療護理、智能安防等領(lǐng)域[1]。在依賴于位置信息的無線傳感器網(wǎng)絡(luò)應(yīng)用中,只有掌握了傳感器節(jié)點的具體位置信息,才能夠明確感知數(shù)據(jù)的實際意義，因此，節(jié)點定位技術(shù)是眾多實際應(yīng)用的基礎(chǔ)和前提，是無線傳感器網(wǎng)絡(luò)研究的重點和難點。

目前，無線傳感器網(wǎng)絡(luò)節(jié)點定位算法根據(jù)是否需要測量節(jié)點間的距離將定位算法分為基于測距(range-based)和基于非測距(range-free)兩大類。基于測距的定位需要特定的硬件設(shè)置，通過不同的測距技術(shù)，如TOA,TDOA,AOA及RSSI等，測量相鄰節(jié)點之間的絕對距離或方位，然后再利用三邊測量法、三角測量法或極大似然估計法等計算未知節(jié)點的位置；基于非測距的定位機制則無需距離或角度信息，僅根據(jù)鄰近關(guān)系和連通性實現(xiàn)節(jié)點的定位，典型的定位算法有質(zhì)心法、凸規(guī)劃法、DV-HOP、APIT算法等[2～4]。基于測距的定位算法雖然可以取得較高的定位精度，但大都需要額外的硬件支持，使其在無線傳感器網(wǎng)絡(luò)的發(fā)展階段性價比不高；而非測距的定位算法在不需要額外添加復(fù)雜硬件設(shè)備的情況下，能夠滿足大多數(shù)應(yīng)用的定位精度，性價比高[5]。目前眾多的距離無關(guān)的三維定位算法中，最為典型并且備受關(guān)注的是劉玉恒、蒲菊華等人提出的無線傳感器網(wǎng)絡(luò)近似三角形內(nèi)點測試三維(approximate point-in-tetrahedron,APIT—3D)自身定位算法[6], 而本文正是在該算法的基礎(chǔ)上提出了改進的無線傳感器網(wǎng)絡(luò)中近似三角形內(nèi)點測試垂面(APIT—VP)分割三維定位算法。

1 算法描述

1.1 基于中垂面分割的三維定位方法

劉志強等人提出基于中垂面分割的無線傳感器網(wǎng)絡(luò)三維定位方法[7],首先根據(jù)待定位節(jié)點S周圍的錨節(jié)點坐標(biāo)，為節(jié)點S建立一個長方體，保證S周圍的所有錨節(jié)點都在這個長方體內(nèi)，然后再進行空間劃分，把該長方體劃分成一個個邊長為N的小正方體;其次利用信號強度損耗可判斷S到任意2個錨節(jié)點的距離遠近，由此得出S節(jié)點肯定在這2個錨節(jié)點確定的中垂面的一側(cè)，利用該中垂面來切割空間劃分后的若干小正方體可以不斷縮小定位區(qū)域;最后取其質(zhì)心作為定位結(jié)果。

1.2 APIT—3D算法

該算法的基本思想是:未知節(jié)點收集其所有可見信標(biāo)節(jié)點的位置信息，任意選擇 4 個信標(biāo)節(jié)點組成一個四面體，判斷自己是否在四面體內(nèi)部，如果未知節(jié)點在某個四面體內(nèi)部,則認為該四面體為該未知節(jié)點的一個可能位置區(qū)域(possible location area，PLA)。通過循環(huán)的選取不同的四面體進行測試直至窮盡組合，篩選出所有是PLA的四面體，然后用三維網(wǎng)格掃描算法獲得所有是PLA的四面體的交集空域，計算該空域的三維質(zhì)心，并以此質(zhì)心坐標(biāo)估計未知節(jié)點的位置。

APIT—3D算法的理論基礎(chǔ)是PIT—3D測試定理。如果存在一個方向，當(dāng)未知節(jié)點沿此方向運動時，會同時接近或遠離四面體的4個頂點，則此未知節(jié)點在四面體外部;否則,在四面體內(nèi)部。

在實際測試中，可以利用無線傳感器網(wǎng)絡(luò)節(jié)點密集分布的特點，未知節(jié)點選取所有鄰居節(jié)點判斷各自距離信標(biāo)節(jié)點的遠近，從而可以在最大程度上近似實現(xiàn)對所有方向進行測試。PIT—3D測試中，一般采用接收信號強度指示(received signal strength indication，RSSI)來判斷遠離還是接近信標(biāo)節(jié)點。

APIT—3D定位算法有幾個重要缺陷：

1)在PIT—3D測試中，當(dāng)鄰居節(jié)點數(shù)量較少或未知節(jié)點處于某些特殊位置時，會引起測試出錯，出現(xiàn)InToOut和OutToIn錯誤。

2)節(jié)點分布不均勻時，在節(jié)點密度較大的區(qū)域，鄰居節(jié)點與信標(biāo)節(jié)點數(shù)量過多引起PIT—3D測試計算量增大；而節(jié)點密度較小時，定位精度較低，更有可能出現(xiàn)未知節(jié)點周圍的信標(biāo)節(jié)點數(shù)目小于4個時，造成無法對未知節(jié)點進行定位。

3)在計算多個四面體重疊區(qū)域的重心時，采用網(wǎng)格掃描算法，計算復(fù)雜度較大，效率較低。

1.3 APIT—VP算法設(shè)計

針對APIT—3D定位算法存在的幾個重大缺陷，本文在算法上進行如下改進：1)為了減少InToOut和OutToIn錯誤，在節(jié)點上設(shè)置相應(yīng)的MAXRSS和MINRSS閾值來進一步判斷。2)在鄰居節(jié)點和信標(biāo)節(jié)點數(shù)量較多的情況下設(shè)置RSSI閾值，將設(shè)定閾值范圍內(nèi)的節(jié)點視為合法節(jié)點，低于設(shè)定法制的節(jié)點視為不可見節(jié)點。當(dāng)信標(biāo)節(jié)點少于4個時，利用加權(quán)的三維質(zhì)心定位算法對未知節(jié)點進行定位。3)利用中垂面分割法代替網(wǎng)絡(luò)掃描算法以減少計算復(fù)雜度和節(jié)點能耗。

改進后的APIT—VP定位算法工作流程如下：

1)節(jié)點部署完成后，網(wǎng)絡(luò)初始化配置。信標(biāo)節(jié)點向網(wǎng)絡(luò)廣播消息(包括信標(biāo)節(jié)點的ID、位置坐標(biāo)等)。

2)未知節(jié)點W(x,y,z)周期性地接收可見信標(biāo)節(jié)點的位置信息并記錄信標(biāo)節(jié)點的RSSI值，將可見信標(biāo)節(jié)點按RSSI值降序排列組成節(jié)點W的信標(biāo)節(jié)點隊列W-List,若信標(biāo)節(jié)點數(shù)量過多,則為信標(biāo)節(jié)點隊列設(shè)置最大長度。

3)設(shè)未知節(jié)點W從上一步獲取了N個信標(biāo)節(jié)點。若1≤N≤3，則執(zhí)行步驟(4)；若N<1，則執(zhí)行步驟(5)；否則，執(zhí)行改進的APIT—3D算法：

a.從信標(biāo)節(jié)點隊列W-list中任意選取4個信標(biāo)節(jié)點，使用PIT—3D測試方法進行測試，此時在節(jié)點上設(shè)置相應(yīng)的MAXRSS和MINRSS閾值來進一步判斷。對于初步判定為在四面體外部的節(jié)點，如果未知節(jié)點RSSI值大于設(shè)置的閾值，則認為發(fā)生IntoOut錯誤；同樣，對于判定為在四面體內(nèi)部的節(jié)點，如果RSSI小于設(shè)定的閾值，則認為發(fā)生OutToIn錯誤。將符合條件的四面體加入四面體集合；

c.若得到四面體集合為Φ，則轉(zhuǎn)到步驟(4);否則設(shè)集合中有K個四面體，這K個四面體中有M個信標(biāo)節(jié)點，基于這M個信標(biāo)節(jié)點，使用基于中垂面分割的定位算法得到未知節(jié)點的估計位置。

4)若未知節(jié)點W的可見信標(biāo)節(jié)點1≤N≤3，或者步驟(3)中得到的四面體集合為Φ，用下面的RSSI加權(quán)質(zhì)心算法公式估算其坐標(biāo)

5)N<1情況下，既未知節(jié)點周圍沒有可見的信標(biāo)節(jié)點，此時等待t時間，然后未知節(jié)點向其鄰居節(jié)點發(fā)出位置請求，此時未知節(jié)點監(jiān)聽到已知節(jié)點的個數(shù)為m,并設(shè)n=n+m，然后轉(zhuǎn)入步驟(2)開始順序往下執(zhí)行。

6)循環(huán)執(zhí)行步驟(1)～(5),以獲得所有未知節(jié)點的坐標(biāo)估計值。

整個算法的流程圖如圖1所示。

圖1 算法流程圖

2 仿真實驗與結(jié)果分析

為了檢驗定位算法的有效性，使用Matlab 7.1 對算法進行了一系列仿真實驗,主要通過定位覆蓋率和定位誤差來比較算法的性能。仿真實驗構(gòu)造邊長為100 m的正方體三維空間實驗區(qū)域，該空間區(qū)域內(nèi)隨機投放了300個節(jié)點，其中信標(biāo)節(jié)點控制在5 %～30 %以內(nèi)，所有節(jié)點的通信半徑均相同。為了減少隨機分布和偶然因素帶來的影響，仿真的結(jié)果是在相同的參數(shù)下仿真50次的平均值。通過比較APIT—VP和APIT—3D算法在不同的信標(biāo)節(jié)點比例的情況下的定位誤差和定位覆蓋率，最后來分析新算法的優(yōu)劣。

2.1 定位覆蓋率

定位覆蓋率隨信標(biāo)節(jié)點比例變化關(guān)系如圖2所示。由圖2可以看出：當(dāng)信標(biāo)節(jié)點比例為5 %時，APIT—3D定位覆蓋率約為10 %,而APIT—VP定位覆蓋率約為30 %，這說明新算法由于考慮到信標(biāo)節(jié)點數(shù)量較少時的特殊情況，此時定位覆蓋率高于APIT—3D算法。隨著信標(biāo)節(jié)點比例的增加，2種算法的定位覆蓋率都明顯提高，當(dāng)信標(biāo)節(jié)點比例約為20 %時，APIT—VP算法定位覆蓋率已達85 %左右，隨后信標(biāo)節(jié)點比例的增加對覆蓋率的影響大大降低。這是因為APIT—VP算法中，將已知節(jié)點當(dāng)做信標(biāo)節(jié)點輔助定位，當(dāng)信標(biāo)節(jié)點達到一定數(shù)量即可實現(xiàn)絕大部分節(jié)點的定位。而APIT—3D算法的覆蓋率隨信標(biāo)節(jié)點比例的增加一直處于穩(wěn)定的上升趨勢，說明APIT—3D算法對信標(biāo)節(jié)點比例的依賴程度較高。

圖2 定位覆蓋率與信標(biāo)節(jié)點比例變化圖

2.2 定位誤差

定位誤差隨信標(biāo)節(jié)點比例變化關(guān)系如圖3所示。由圖3可以看出：當(dāng)2種算法的定位誤差達到35 %左右時，定位精度很難再得到改善。在信標(biāo)節(jié)點比例為5%左右時，APIT—VP算法的定位誤差明顯大于APIT—3D算法，因為在信標(biāo)節(jié)點數(shù)量較少時，APIT—VP定位過程中利用已知節(jié)點輔助定位，已知節(jié)點本身就有誤差，使得定位誤差得到了累加，故定位誤差較大。當(dāng)信標(biāo)節(jié)點比例在20%左右時，2種算法的定位誤差變化不明顯，此時增加信標(biāo)節(jié)點比例時，APIT—VP算法略優(yōu)于APIT—3D算法，因為APIT—VP算法在一定程度上避免了OutToIn和InToOut這2種錯誤，并且中垂面分割法在減少計算復(fù)雜度的同時，提高定位精度。

圖3 定位誤差與信標(biāo)節(jié)點比例變化圖

3 結(jié) 論

本文基于無線傳感網(wǎng)絡(luò)中經(jīng)典的APIT—3D算法，提出了改進的APIT—VP三維定位算法。在分析APIT—3D算法誤差來源的基礎(chǔ)上，對其進行了相應(yīng)的改進,改進后的APIT—VP算法能夠精確有效地實現(xiàn)三維空間中節(jié)點的定位。仿真實驗表明：APIT—VP算法能達到理想的定位覆蓋率和定位精度，定位覆蓋率可達90 %，定位誤差控制在25 %左右，是一種低功耗的三維定位算法。

參考文獻:

[1] Zhang Ke,Zou Chengwu,Zhang Jianping,et al. RBDV—HOP:A novel improved DV—Hop licalization algorithm for wireless sensor networks based on RSSI[C]∥The 3rd International Conference on Information Science and Engineering, Yangzhou,China:IEEE,2011:5438-5441.

[2] Zhang Jianping,Yu Min,Zhang Ke,et al.An improved weighted triangle centroid localization algorithm of APIT for wireless sensor networks[C]∥2012 International Conference on Computer and Information Science, Safety Engineering, Wuhan,China:IEEE,2012:18-21.

[3] Zeng Fanzhen,Yu Min,Zou Chengwu,et al.An improved point-in-triangulation localization algorithm based on cosine theore-m[C]∥2012 8th International Conference on Wireless Communications,Networking and Mobile Computing, Shanghai,China:IEEE,2012:1652-1655.

[4] Rong P,Sichitiu M. Angle of arrival localization for wireless sensor networks[C]∥Proc of SECON′06, Reston, USA:IEEE,2006:374-382.

[5] Zhou Yong, Xia Shixiong, Ding Shifei.An improved APIT node self-localization algorithm in WSNs based on triangle-center scan[J].Journal of Computer Research and Development,2009,16(4):566-574.

[6] 劉玉恒,蒲菊華,赫 陽,等.無線傳感網(wǎng)絡(luò)三維自身定位方法[J].北京航空航天大學(xué)學(xué)報,2008,34(6):647-651.

[7] 劉志強,王行甫.基于中垂面分割的WSNs三維定位方法[J].計算機工程,2010,36(14):90-92.