無線傳感器網(wǎng)絡(luò)中APIT—HR定位算法*

周禮爭(zhēng)，張乙竹，唐 瑞，余 敏

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

0 引言

節(jié)點(diǎn)定位技術(shù)一直是學(xué)術(shù)界研究的重點(diǎn)。在室外，一般有基于全球定位系統(tǒng)(GPS)定位技術(shù)、基于移動(dòng)蜂窩網(wǎng)絡(luò)定位技術(shù)、基于無線傳感器網(wǎng)絡(luò)(wireless sensor networks，WSNs)定位技術(shù)［1］。在室內(nèi)，一般有基于接收信號(hào)強(qiáng)度指示(received signal strength indication，RSSI)定位技術(shù)、航位推算定位技術(shù)［2］。然而，WSNs因其具有隨機(jī)部署、網(wǎng)絡(luò)自組織、覆蓋范圍廣等優(yōu)點(diǎn)，故其應(yīng)用非常廣泛，如生態(tài)農(nóng)業(yè)檢測(cè)、智能安防、現(xiàn)代信息化作戰(zhàn)等。

WSNs節(jié)點(diǎn)定位方法分為基于測(cè)距(range-based)和基于非測(cè)距(ranged-free)兩類［3，4］?；跍y(cè)距的方法需測(cè)量彼此間的絕對(duì)距離或角度，再用相關(guān)方法估算節(jié)點(diǎn)位置信息［5，6］，如 TOA，TDOA 等。基于非測(cè)距的測(cè)量法是以節(jié)點(diǎn)間連通性、相鄰特性求解節(jié)點(diǎn)位置信息，如質(zhì)心法、近似四面體內(nèi)點(diǎn)(approximate point-in-tetrahedron，APIT)、凸規(guī)劃法等［7，8］?；跍y(cè)距的定位技術(shù)定位精度較高，但對(duì)WSNs節(jié)點(diǎn)的硬件要求較高，因此，在WSNs的現(xiàn)發(fā)展階段性價(jià)比不算高。而基于非測(cè)距的定位算法定位精度雖然不理想，但能夠滿足大多數(shù)應(yīng)用的定位需求。APIT算法相對(duì)其他基于非測(cè)距定位算法，在定位精度、硬件成本、節(jié)點(diǎn)分布等方面性能較好。

文獻(xiàn)［7］提出基于RSSI的加權(quán)質(zhì)心定位算法，定位精度有所提高。文獻(xiàn)［8］提出基于三角形角度的加權(quán)質(zhì)心算法，能較好地改善定位精度。文獻(xiàn)［9］提出基于區(qū)域的非測(cè)距APIT定位算法，但算法通信開銷大、定位精度低。文獻(xiàn)［10］提出基于垂直平分線的區(qū)域定位算法，文獻(xiàn)［11］提出改進(jìn)的APIT(IAPIT)定位算法均力圖提高定位精度。

在上述文獻(xiàn)基礎(chǔ)上，本文提出基于RSSI值折半的APIT(APIT—HR)質(zhì)心定位算法，以RSSI值比較進(jìn)行區(qū)域約束劃分，以節(jié)點(diǎn)存在區(qū)域質(zhì)心作為定位結(jié)果。

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

1.1 RSSI損耗模型

無線信號(hào)傳播較為常用的模型是Shadowing模型，該模型參考式為

其中，RSSId為接收到的信號(hào)強(qiáng)度值;d為收發(fā)端的實(shí)際距離;d0為參考距離;RSSId0為距離為d0時(shí)的信號(hào)強(qiáng)度;n為信道衰減指數(shù)，由傳輸環(huán)境決定;Xσ是方差為σ、均值為0的高斯隨機(jī)變量。由式(1)變形可得d與RSSId之間一階導(dǎo)數(shù)和二階導(dǎo)數(shù)關(guān)系

由式(1)～式(3)可知，若RSSI1值對(duì)應(yīng)的距離d1時(shí)，則值對(duì)應(yīng)的距離

1.2 APIT算法分析

該算法的核心思想:任取3個(gè)錨節(jié)點(diǎn)組成三角形，再以某種方法［10］判斷未知節(jié)點(diǎn)是否在該三角形內(nèi)部，若在，則稱三角形約束區(qū)域包含未知節(jié)點(diǎn)。以此類推，求所有符合要求的三角形約束區(qū)域交集的質(zhì)心作為未知節(jié)點(diǎn)近似坐標(biāo)。APIT算法的基礎(chǔ)是PIT測(cè)試定理［10］。PIT測(cè)試中，通常以RSSI的強(qiáng)弱來判斷遠(yuǎn)離或靠近錨節(jié)點(diǎn)。

APIT算法存在以下缺陷:

1)在判斷未知節(jié)點(diǎn)是否在三角形區(qū)域內(nèi)部時(shí)，易產(chǎn)生InToOut和OutToIn錯(cuò)誤。如圖1(a)，當(dāng)節(jié)點(diǎn)M從位置1模擬移動(dòng)到位置2時(shí)，收到來自A，B，C的信號(hào)強(qiáng)度同時(shí)變?nèi)?，?jié)點(diǎn)M同時(shí)遠(yuǎn)離A，B，C點(diǎn)，就判定為M在三角形外，即In-ToOut error。同理，圖1(b)，當(dāng)節(jié)點(diǎn)M從位置1模擬移動(dòng)到位置2時(shí)，根據(jù)信號(hào)強(qiáng)度測(cè)得節(jié)點(diǎn)M就遠(yuǎn)離了B，并靠近了A，C點(diǎn)，就判定為M在三角形內(nèi)，即OutToIn error。

2)在節(jié)點(diǎn)密度低時(shí)，定位精度較低，當(dāng)未知節(jié)點(diǎn)可感知的錨節(jié)點(diǎn)數(shù)小于3或節(jié)點(diǎn)數(shù)不小于3且不存在符合PIT測(cè)試的三角形時(shí)，無法進(jìn)行APIT定位。故在錨節(jié)點(diǎn)稀疏時(shí)APIT算法的定位覆蓋率是很低的。

圖1 兩種誤判情況Fig 1 Two situations of misjudgement

3)在求三角形約束區(qū)域交集質(zhì)心時(shí)，算法復(fù)雜度高，效率低下。

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

針對(duì)APIT算法存在上述缺陷，本文提出APIT—HR質(zhì)心定位算法。算法做以下完善:1)以面積規(guī)則定性的判斷是否存在InToOut和OutToIn錯(cuò)誤;2)以圓交域質(zhì)心定位算法提高定位覆蓋率;3)以RSSI值折半?yún)^(qū)域法代替三角形約束區(qū)域交集質(zhì)心法，降低計(jì)算復(fù)雜度。

1.3.1 面積規(guī)則

針對(duì)判斷一個(gè)點(diǎn)是否在三角形內(nèi)部，本文采用面積規(guī)則來判斷，即外部較大三角形面積等于3個(gè)內(nèi)部較小三角形面積和。由信號(hào)損耗模型可知距離值和RSSI差值是一一對(duì)應(yīng)的正函數(shù)關(guān)系，故可用RSSI差值代替距離值作定性分析。設(shè)三角形3個(gè)頂點(diǎn)為A，B，C，未知節(jié)點(diǎn)為U，則它們之間距離值 dAB=|RSSIBA-RSSIAA|，dAC=|RSSICARSSIAA|，dBC=|RSSIBC-RSSICC|，其中，RSSIij表示 i節(jié)點(diǎn)感知 j節(jié)點(diǎn)的RSSI值，若i=j，則根據(jù)功率和RSSI關(guān)系轉(zhuǎn)換求得，WSNs中節(jié)點(diǎn)是同規(guī)格的。

由△ABC的面積SABC如式(4)所示

類似的，可求SABU，SACU，SBCU，若滿足面積規(guī)則，判定 U點(diǎn)在△ABC內(nèi)，否則，在△ABC外。

1.3.2 APIT—HR定位算法

APIT—HR算法流程圖如圖2所示，步驟如下:

1)初始化網(wǎng)絡(luò)，錨節(jié)點(diǎn)返回自己被未知節(jié)點(diǎn)感知確認(rèn)消息。

2)未知節(jié)點(diǎn)將可感知的錨節(jié)點(diǎn)存入錨節(jié)點(diǎn)集合M_set(數(shù)組構(gòu)成)中。從M_set任取不重復(fù)的3個(gè)錨節(jié)點(diǎn)組成三角形，并執(zhí)行PIT測(cè)試［10］，若未知節(jié)點(diǎn)在三角形內(nèi)，則把該組合存入三角形集合T_set中;否則，舍棄。

3)若T_set為空，執(zhí)行圓交域質(zhì)心定位算法;否則，從T_set中取出一個(gè)元素，執(zhí)行區(qū)域縮減與質(zhì)心坐標(biāo)求解，步驟如下:

a.取T_set一個(gè)元素，設(shè)三角形頂點(diǎn)為A，B，C，未知節(jié)點(diǎn)為U，然后取A，B，C的3個(gè)頂點(diǎn)中的1個(gè)(設(shè)為A)作為圓心，同時(shí)，余下的2個(gè)頂點(diǎn)B，C和未知節(jié)點(diǎn)U分別把各自感知圓心處錨節(jié)點(diǎn)的RSSI值(設(shè)為RSSIBA，RSSICA，RSSIUA)報(bào)送給圓心錨節(jié)點(diǎn)，再分別用與 RSSIUA比 較。若 RSSIUA＞，則說明U在以A點(diǎn)為圓心，半徑為的圓與三角形交匯區(qū)域;若，則說明U在以A點(diǎn)為圓心，半徑為的圓與三角形交匯區(qū)域;若，則說明以該點(diǎn)為圓心的圓約束不了U。

b.重復(fù)步驟(a)，其他2個(gè)錨節(jié)點(diǎn)進(jìn)行類似處理。若約束圓個(gè)數(shù)為0，如圖3(a)所示，則將三角形質(zhì)心作為初步定位坐標(biāo);若約束圓數(shù)等于1，則把該圓與三角形交匯區(qū)域的質(zhì)心作為初步定位坐標(biāo)。如圖3(b)所示，未知節(jié)點(diǎn)被1個(gè)圓約束，求Sa1或Sa2區(qū)域質(zhì)心。若約束圓數(shù)(圓心不同的圓)等于2，則求這2個(gè)約束圓交域與三角形的交域的質(zhì)心作為初步定位坐標(biāo)，如圖3(c)所示。

圖2 APIT—HR算法流程圖Fig 2 Flow chart of APIT—HR algorithm

4)由步驟(3)中的初步定位坐標(biāo)組成多邊形，然后求多邊形質(zhì)心作為未知節(jié)點(diǎn)定位結(jié)果。

2 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證APIT—HR算法的性能，以Matlab對(duì)算法進(jìn)行仿真。仿真環(huán)境為200 m×200 m的正方形區(qū)域隨機(jī)部署500節(jié)點(diǎn)，隨機(jī)選派未知節(jié)點(diǎn)。為降低偶然性誤差，以100次實(shí)驗(yàn)均值為結(jié)果。以錨節(jié)點(diǎn)個(gè)數(shù)變化來對(duì)比分析APIT—HR和原始的APIT算法性能。

圖3 約束圓示意圖Fig 3 Diagram of constraint circles

2.1 定位覆蓋率分析

定位覆蓋率與錨節(jié)點(diǎn)數(shù)關(guān)系如圖4所示。當(dāng)錨節(jié)點(diǎn)數(shù)小于100時(shí)，而 APIT—HR定位覆蓋率比 APIT算法高出20%左右。當(dāng)錨節(jié)點(diǎn)數(shù)大于100時(shí)，APIT—HR的定位覆蓋率達(dá)到86%左右，比APIT高出約17%。這說明APIT—HR算法的定位覆蓋率總體上都要比原APIT算法好。

圖4 錨節(jié)點(diǎn)個(gè)數(shù)和定位覆蓋率關(guān)系Fig 4 Relationship between localization coverage rate and number of beacon nodes

2.2 定位誤差分析

定位誤差和錨節(jié)點(diǎn)數(shù)關(guān)系如圖5所示。當(dāng)錨節(jié)點(diǎn)數(shù)在25左右時(shí)，APIT—HR算法的定位誤差比APIT大，這是因?yàn)橐氲膱A交域質(zhì)心定位算法定位精度差。當(dāng)錨節(jié)點(diǎn)數(shù)在50左右時(shí)，兩種算法定位誤差相當(dāng)。而隨著錨節(jié)點(diǎn)數(shù)繼續(xù)增加，APIT—HR算法優(yōu)勝于APIT，這是由于使用了本文提出改進(jìn)措施減少了InToOut和OutToIn error出現(xiàn)，同時(shí)又以RSSI值折半比較對(duì)未知節(jié)點(diǎn)存在區(qū)域進(jìn)行縮小。從圖6看出:在錨節(jié)點(diǎn)個(gè)數(shù)較少時(shí)，APIT—HR算法的定位最大誤差比APIT算法大，而后最大誤差都漸漸減小，并明顯優(yōu)于APIT，這得益于區(qū)域縮減方案。

圖5 定位平均誤差Fig 5 Location average error

圖6 定位最大誤差Fig 6 Location maximum error

3 結(jié)論

本文以經(jīng)典的APIT質(zhì)心定位算法為基礎(chǔ)，針對(duì)該算法存在的問題進(jìn)行改進(jìn)，提出APIT—HR算法。通過仿真實(shí)驗(yàn)，對(duì)比原始的APIT算法在計(jì)算復(fù)雜度和定位誤差方面的優(yōu)劣。結(jié)果顯示:APIT—HR克服錨節(jié)點(diǎn)數(shù)量較低情況下無法定位問題，同時(shí)根據(jù)RSSI值縮減未知節(jié)點(diǎn)存在區(qū)域，提高定位精度。APIT—HR算法在計(jì)算復(fù)雜度和定位精度均達(dá)到理想效果，計(jì)算復(fù)雜度明顯降低，定位誤差縮減了22.8%，是一種性能優(yōu)良的質(zhì)心定位算法。

［1］金 輝.位置服務(wù)和移動(dòng)定位技術(shù)研究［D］.南京:東南大學(xué)，2006.

［2］趙 銳，鐘 榜，朱祖禮，等.室內(nèi)定位技術(shù)及應(yīng)用綜述［J］.電子科技，2014(3):154-157.

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

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

［5］肖 竹，譚光華，李仁發(fā)，等.無線傳感器網(wǎng)絡(luò)中基于超寬帶的TOA/AOA聯(lián)合定位研究［J］.計(jì)算機(jī)研究與發(fā)展，2013，50(3):453-460.

［6］楊小鳳，陳鐵軍，劉 峰.基于TOA-DOA聯(lián)合估計(jì)的無線定位新方法［J］.數(shù)據(jù)采集與處理，2014，29(6):1036-1040.

［7］花 超，吉小軍，蔡 萍，等.基于RSSI差分修正的加權(quán)質(zhì)心定位算法［J］.傳感器與微系統(tǒng)，2012，31(5):139-144.

［8］劉 瑾.基于測(cè)距的無線傳感器網(wǎng)絡(luò)的定位算法的研究［J］.航空計(jì)算技術(shù)，2009，39(6):124-126.

［9］陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT質(zhì)心定位算法研究［D］.廣州:暨南大學(xué)，2008:24-32.

［10］戴佩華，薛小平，邵玉華.基于垂直平分線的區(qū)域定位算法［J］.計(jì)算機(jī)工程，2009，35(2):105-108.

［11］周四清，陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進(jìn)［J］.計(jì)算機(jī)工程，2009，35(7):87-89.