無線傳感器網絡中APIT-SC 三維定位算法*

周禮爭，唐 瑞，張乙竹，程 俊，余 敏

(1.江西師范大學 計算機信息工程學院，江西 南昌330022;2.江西師范大學 軟件學院，江西 南昌330022)

0 引 言

在無線傳感器網絡(wireless sensor networks，WSNs)應用中，定位應用是最熱門的應用研究之一。WSNs 節點定位技術是眾多應用得以實施的基礎和前提，也是研究的重點和難點。

WSNs 節點定位算法分為基于測距(range-based)和基于非測距(ranged-free)兩類［1，2］。基于測距的定位一般需要額外的硬件支持，如TOA，AOA 及RSSI 等算法［3，4］，測量彼此間的絕對距離或角度，再利用三邊測量法、三角測量法或極大似然估計法等估算位置信息。基于非測距的算法一般是利用節點間連通性、相鄰特性實現定位，如質心法、DV-Hop 及APIT 等［5～7］。

在眾多的三維(3D)定位算法中，DV-Hop 定位算法已近完善，但始終存在精度問題。而在其他方法中，引人關注的是劉玉恒等人提出的WSNs 近似四面體內點的三維(approximate point in tetrahedron 3D，APIT—3D)定位算法［8］。文獻［9］提出基于質心迭代的APIT 定位算法，以質心迭代代替網格掃描求解定位坐標。文獻［10，11］都提出基于中垂面的APIT 定位算法，以中垂面切割縮小未知節點存在區域。在上述文獻思想上，本文提出一種基于球切割的APIT(APIT-SC)定位算法，未知節點定位任務分解到周圍錨節點，自己求解各錨節點上報存在區域的交集的質心作為定位結果。

1 相關算法描述

1.1 基于中垂面的3D 定位算法

陳月娥、余敏提出的APIT—VP 定位算法［10］。首先，以PIT—3D 測試確認未知節點在四面體內。其次，任選取兩錨節點連成線段，并以該線段的中垂線形成中垂面，未知節點對其感知這2 個錨節點的RSSI 值作比較，判斷自身在中垂面的哪一側。重復上述操作，必劃分出共同區域，則以此區域質心為定位坐標。

1.2 APIT—3D 算法分析

該算法的思想: 未知節點收集可感知的錨節點，任意選4 個非共面錨節點組成四面體，以某種技術［10］判斷自身是否在四面體內，若在四面體內，則稱該四面體區域為未知節點存在區域(presence area，PA)。窮盡所有PA 的四面體組合，用3D 網格掃描算法獲得PA 的交域，并以交域質心作為定位結果。APIT—3D 算法的基礎是PIT—3D 測試原理:當未知節點在四面體外時，存在鄰居節點沿著一個方向運動，鄰居節點必同時遠離或靠近四面體4 個錨節點。若不存在，則未知節點必在四面體內。在現實中，利用WSNs 節點分布特性，未知節點的鄰居節點判斷各自與錨節點距離的遠近，很大程度上實現對球面所有方向進行測試。PIT—3D 測試中，通常以RSSI 的強弱來判斷遠離或靠近四面體的錨節點。

APIT—3D 算法有以下缺陷:

1)在PIT—3D 測試中，當未知節點的鄰居節點數量較少或處于某些特殊位置時，會引起PIT 測試出現InToOut 和OutToIn 錯誤。

2)在節點分布不均勻時，節點密度較大的區域會引起PI—3D 測試計算量偏大。而節點密度較小時，定位精度較低，或當錨節點數量小于4 時，無法以APIT—3D 進行定位。

3)在窮盡PA 四面體交域時，采用網格掃描算法，計算量較大，效率低下。

1.3 APIT—SC 算法設計

針對APIT—3D 算法存在上述缺陷，本文提出APIT—SC定位算法，做了以下完善:1)采用四面體體積規則減少In-ToOut 和OutToIn 錯誤。2) 在節點密度較大時采用輪回選擇法，避免一段時間內只在小區域內尋找滿足PIT—3D 的鄰居節點。當錨節點不足以構成四面體時，以RSSI 加權三維質心定位算法進行定位。3) 以球切割法代替網絡掃描法減少計算復雜度。

體積規則:

如圖1 所示，若未知節點E 在四面體內，則VABCE+VABDE+VBCDE+VACDE=VABCD;若E 在四面體外，即E'，則VABCE'+VABDE'+VBCDE'+VACDE'＞VABCD，其中VACDE'計算了2 次，有利于探測邊緣效應［6］。根據RSSI 對數測距模型［12］，距離值和RSSI 值是一一對應的函數關系，故可用RSSI 值代替距離值做定性分析，即dAB=|RSSIBA－RSSIAA|，其中RSSIBA為B 點感知A 點RSSI 值，RSSIAA為A 點感知自身RSSI 值。根據歐拉四面體數學模型［13］，四面體體積公式如式(1)所示

其中，l，m，n，p，q，r 為四面體6 條棱長。

圖1 體積規則示意圖Fig 1 Diagram of volume rule

輪回選擇法:

未知節點鄰居節點如圖2 所示，輪回選擇步驟如下:

1)將未知節點的鄰居節點分別以其感知四面體4 個錨節點RSSI 值進行排序形成4 組RSSI 單調鄰居節點隊列。

2)分別輪回從4 組RSSI 隊列中取元素進行PIT—3D 測試，若符合，則返回測試結果并退出算法;若不符合，則在其他3 組中標記該鄰居節點已被測試，執行步驟(3)。

3)重復步驟(2)，直到找到滿足PIT—3D 測試的鄰居節點或隊列為空時，返回測試結果并退出算法。

圖2 未知節點鄰居節點示意圖Fig 2 Diagram of neighbor nodes of unknown node

APIT—SC 算法流程如圖3 所示，步驟如下:

1)在空間部署節點形成WSNs，網絡初始化。

2)未知節點U(x，y，z)定位時，感知周圍錨節點，記錄可見錨節點信息(ID、空間坐標、RSSI 值)，將可見錨節點以其返回的RSSI 值進行降序排序存入隊列Q-list(數組構成)，設隊列長度為LQ 且元素個數為N。

3)若N ＜1，則執行步驟(4);若1≤N≤3，則執行步驟(5);否則，執行改進的APIT—SC 算法。

改進的APIT—SC 算法:

a.從錨節點隊列中Q-list 中任選4 個錨節點，進行PIT—3D 測試和體積規則判斷，將合法的四面體組合存在四面體集合Tset中，并計算每個組合兩兩錨節點間距離，若它們之間的距離極其接近(距離方差小于P)，則標記該組合球切割方法狀態為N;否則，為Y。

b.若集合Tset為空，則執行步驟(5);否則，取集合Tset一個元素，若方法狀態是N，則用RSSI 加權質心定位算法。若方法狀態是Y，則對4 個錨節點兩兩間的距離進行排序，選距離值最小兩端點的一端點作為定位發起者和球心，以球心到其他3 個錨節點距離值為半徑建立3 個球，一般最大球會被其他2 個較小球切成三部分。再分別用球心探測未知節點的RSSI 值和其探測其他3 個錨節點的RSSI 值作比較，則未知節點必在這3 個區域某一區域。然后該球殼與四面體的交域作為該組合下未知節點存在區域。如圖4所示，設錨節點B 感知未知節點U 的RSSI 值小于其感知錨節點D 的RSSI 值但又大于其感知錨節點A 的RSSI 值，所以，未知節點必在S2的球殼與四面體交集區域。

c.重復步驟b，求方法狀態是Y，則所有四面體組合下未知節點存在區域，并將這些區域交集的質心作為定位結果。

4)若未知節點周圍沒有可見錨節點，則休眠一定時間t后，再向鄰居節點發送定位請求，此時感知到的錨節點為N，則轉入步驟(3)執行。

5)若1≤N≤3 或四面體集合Tset為空，則用RSSI 加權3D 質心定位算法［12］定位。

圖3 APIT-SC 算法流程圖Fig 3 Flow chart of APIT-SC algorithm

2 仿真實驗和性能分析

為了驗證APIT—SC 算法的性能，使用Matlab 進行仿真。仿真環境如下:3D 空間為106m3的立方體內隨機部署500 個節點，錨節點控制在5%～30%，節點間通信半徑均相同。考慮隨機分布和偶然因素的影響，以仿真100 次的均值作為結果。仿真以不同的錨節點比例來對比APIT—SC 和APIT—3D 算法性能。

圖4 球分割法示意圖Fig 4 Diagram of SC method

2.1 定位覆蓋率分析

定位覆蓋率與錨節點比例關系如圖5 所示。當錨節點比例是5%時，APIT—3D 定位覆蓋率在10%左右，而APIT—SC 定位覆蓋率是APIT—3D 算法的3 倍，這說明APIT—SC 算法考慮了當錨節點個數較少特殊情況。隨著錨節點比例升高，兩種算法的定位覆蓋率明顯升高。當錨節點比例上升到20%左右，APIT—SC 定位覆蓋率達到85%左右。隨后再隨著錨節點比例的增大對覆蓋率的影響越來越小，這是由于APIT—SC 算法引入未知節點轉化為錨節點輔助定位。

圖5 錨節點比例和定位覆蓋率關系Fig 5 Relationship between localization coverage rate and ratio of beacon nodes

2.2 定位誤差分析

定位誤差和錨節點比例關系如圖6 所示。當錨節點比例在5%時，APIT—SC 的定位誤差比APIT—3D 大，這是因為引入的輔助定位算法定位精度低。當錨節點比例增大到15%～20%，兩種算法定位誤差相當。隨著錨節點比例增加，APIT—SC 性能優勝于APIT—3D，這由于本文提出兩種新的規則，又采用球切割法縮小未知節點存在區域。

圖6 錨節點比例和定位誤差關系Fig 6 Relationship between localization error and ratio of beacon node

3 結 論

本文在APIT—3D 基礎上，提出改進的APIT—SC 算法。仿真實驗表明:APIT—SC 算法克服錨節點比例較低時無法定位問題，同時根據RSSI 值縮減未知節點存在區域，提高定位精度。APIT—SC 算法在定位覆蓋率和定位精度均達到預期效果，定位覆蓋率可達91%，定位誤差縮減至23%左右，是一種適應性強的3D 定位算法。

［1］ 信召建，胡 屏，王 玲，等.基于RSSI 值的WSNs 節點測距算法改進和定位實現［J］.傳感器與微系統，2014，33(6):133－136.

［2］ 王佩琦，李艷萍，陳相南，等.基于RSSI 距離修正的WSNs 定位算法［J］.傳感器與微系統，2014，33(5):135－137.

［3］ Nasipuri A，Li K.A directionality-based location discovery scheme for wireless sensor networks［C］∥Proceedings of ACM International Workshop on Wireless Sensor Networks and Application，Atlanta，USA，2002:105－111.

［4］ Girod L，Estrin D.Robust range estimation using acoustic and multimodal sensing［C］∥Proc of IEEE International Conference on Intelligent Robots and Systems，2001:1312－1320.

［5］ 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.

［6］ Zeng Fanzhen，Yu Min，Zou Chengwu，et al.An improved point in triangulation localization algorithm based on cosine theorem［C］∥2012 8th International Conference on Wireless Communications，Networking and Mobile Computing，Shanghai，China:IEEE，2012:1652－1655.

［7］ Rong P，Sichitiu M.Angle of arrival localization for wireless sensor networks［C］∥Proc of SECON’06，Reston，USA:IEEE，2006:374－382.

［8］ 劉玉恒，蒲菊華，赫 陽，等.無線傳感網絡三維自身定位方法［J］.北京航空航天大學學報，2008，34(6):647－651.

［9］ 王長征，湯文亮，徐 燕.無線傳感器網絡中四面體三維質心定位算法［J］.傳感器與微系統，2012，31(8):141－146.

［10］陳月娥，余 敏.無線傳感器網絡中APIT—VP 三維定位算法［J］.傳感器與微系統，2014，33(5):148－150.

［11］劉志強，王行甫.基于中垂面分割的WSNs 三維定位方法［J］.計算機工程，2010，36(14):90－92.

［12］王婷婷，柯 煒，孫 超.自適應環境變化的RSS 室內定位方法［J］.通信學報，2014，35(10):210－217.

［13］王榮波.基于Mathematica 下的歐拉四面體問題［J］.數學教學與研究，2010，12(1):74.