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

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

0 引 言

在無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)應(yīng)用中，定位應(yīng)用是最熱門的應(yīng)用研究之一。WSNs 節(jié)點(diǎn)定位技術(shù)是眾多應(yīng)用得以實(shí)施的基礎(chǔ)和前提，也是研究的重點(diǎn)和難點(diǎn)。

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

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

1 相關(guān)算法描述

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

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

1.2 APIT—3D 算法分析

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

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

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

2)在節(jié)點(diǎn)分布不均勻時(shí)，節(jié)點(diǎn)密度較大的區(qū)域會引起PI—3D 測試計(jì)算量偏大。而節(jié)點(diǎn)密度較小時(shí)，定位精度較低，或當(dāng)錨節(jié)點(diǎn)數(shù)量小于4 時(shí)，無法以APIT—3D 進(jìn)行定位。

3)在窮盡PA 四面體交域時(shí)，采用網(wǎng)格掃描算法，計(jì)算量較大，效率低下。

1.3 APIT—SC 算法設(shè)計(jì)

針對APIT—3D 算法存在上述缺陷，本文提出APIT—SC定位算法，做了以下完善:1)采用四面體體積規(guī)則減少In-ToOut 和OutToIn 錯誤。2) 在節(jié)點(diǎn)密度較大時(shí)采用輪回選擇法，避免一段時(shí)間內(nèi)只在小區(qū)域內(nèi)尋找滿足PIT—3D 的鄰居節(jié)點(diǎn)。當(dāng)錨節(jié)點(diǎn)不足以構(gòu)成四面體時(shí)，以RSSI 加權(quán)三維質(zhì)心定位算法進(jìn)行定位。3) 以球切割法代替網(wǎng)絡(luò)掃描法減少計(jì)算復(fù)雜度。

體積規(guī)則:

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

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

圖1 體積規(guī)則示意圖Fig 1 Diagram of volume rule

輪回選擇法:

未知節(jié)點(diǎn)鄰居節(jié)點(diǎn)如圖2 所示，輪回選擇步驟如下:

1)將未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)分別以其感知四面體4 個(gè)錨節(jié)點(diǎn)RSSI 值進(jìn)行排序形成4 組RSSI 單調(diào)鄰居節(jié)點(diǎn)隊(duì)列。

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

3)重復(fù)步驟(2)，直到找到滿足PIT—3D 測試的鄰居節(jié)點(diǎn)或隊(duì)列為空時(shí)，返回測試結(jié)果并退出算法。

圖2 未知節(jié)點(diǎn)鄰居節(jié)點(diǎn)示意圖Fig 2 Diagram of neighbor nodes of unknown node

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

1)在空間部署節(jié)點(diǎn)形成WSNs，網(wǎng)絡(luò)初始化。

2)未知節(jié)點(diǎn)U(x，y，z)定位時(shí)，感知周圍錨節(jié)點(diǎn)，記錄可見錨節(jié)點(diǎn)信息(ID、空間坐標(biāo)、RSSI 值)，將可見錨節(jié)點(diǎn)以其返回的RSSI 值進(jìn)行降序排序存入隊(duì)列Q-list(數(shù)組構(gòu)成)，設(shè)隊(duì)列長度為LQ 且元素個(gè)數(shù)為N。

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

改進(jìn)的APIT—SC 算法:

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

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

c.重復(fù)步驟b，求方法狀態(tài)是Y，則所有四面體組合下未知節(jié)點(diǎn)存在區(qū)域，并將這些區(qū)域交集的質(zhì)心作為定位結(jié)果。

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

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

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

2 仿真實(shí)驗(yàn)和性能分析

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

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

2.1 定位覆蓋率分析

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

圖5 錨節(jié)點(diǎn)比例和定位覆蓋率關(guān)系Fig 5 Relationship between localization coverage rate and ratio of beacon nodes

2.2 定位誤差分析

定位誤差和錨節(jié)點(diǎn)比例關(guān)系如圖6 所示。當(dāng)錨節(jié)點(diǎn)比例在5%時(shí)，APIT—SC 的定位誤差比APIT—3D 大，這是因?yàn)橐氲妮o助定位算法定位精度低。當(dāng)錨節(jié)點(diǎn)比例增大到15%～20%，兩種算法定位誤差相當(dāng)。隨著錨節(jié)點(diǎn)比例增加，APIT—SC 性能優(yōu)勝于APIT—3D，這由于本文提出兩種新的規(guī)則，又采用球切割法縮小未知節(jié)點(diǎn)存在區(qū)域。

圖6 錨節(jié)點(diǎn)比例和定位誤差關(guān)系Fig 6 Relationship between localization error and ratio of beacon node

3 結(jié) 論

本文在APIT—3D 基礎(chǔ)上，提出改進(jìn)的APIT—SC 算法。仿真實(shí)驗(yàn)表明:APIT—SC 算法克服錨節(jié)點(diǎn)比例較低時(shí)無法定位問題，同時(shí)根據(jù)RSSI 值縮減未知節(jié)點(diǎn)存在區(qū)域，提高定位精度。APIT—SC 算法在定位覆蓋率和定位精度均達(dá)到預(yù)期效果，定位覆蓋率可達(dá)91%，定位誤差縮減至23%左右，是一種適應(yīng)性強(qiáng)的3D 定位算法。

［1］ 信召建，胡 屏，王 玲，等.基于RSSI 值的WSNs 節(jié)點(diǎn)測距算法改進(jìn)和定位實(shí)現(xiàn)［J］.傳感器與微系統(tǒng)，2014，33(6):133－136.

［2］ 王佩琦，李艷萍，陳相南，等.基于RSSI 距離修正的WSNs 定位算法［J］.傳感器與微系統(tǒng)，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］ 劉玉恒，蒲菊華，赫 陽，等.無線傳感網(wǎng)絡(luò)三維自身定位方法［J］.北京航空航天大學(xué)學(xué)報(bào)，2008，34(6):647－651.

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

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

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

［12］王婷婷，柯 煒，孫 超.自適應(yīng)環(huán)境變化的RSS 室內(nèi)定位方法［J］.通信學(xué)報(bào)，2014，35(10):210－217.

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