非視距信號(hào)路徑返回的柵格迭代掃描定位算法

杜廣周

(鄭州輕工業(yè)大學(xué)，河南 鄭州 451450)

0 引 言

無(wú)線(xiàn)傳感器網(wǎng)絡(luò)（wireless sensor network, WSN）是由大量傳感器節(jié)點(diǎn)組成的自組織網(wǎng)絡(luò)，在工業(yè)生產(chǎn)和社會(huì)生活中得到越來(lái)越廣泛的應(yīng)用[1]。在WSN中，定位技術(shù)是核心技術(shù)之一。常見(jiàn)的WSN定位技術(shù)有到達(dá)時(shí)間（TOA）、到達(dá)角（AOA）、到達(dá)時(shí)差（TDOA）、接收信號(hào)強(qiáng)度（RSS）等來(lái)估計(jì)節(jié)點(diǎn)的位置[2-3]，以上算法定位精度較好，但對(duì)于硬件的要求相對(duì)較高[4-5]。因此，對(duì)于硬件條件較低的算法得到廣泛研究，較為典型的算法為DV-Hop、Amorphous、Bounding-Box、Grid-Scan以及相關(guān)的衍生算法[6-10]。對(duì)于Grid-Scan算法，近年來(lái)已有一些研究。文獻(xiàn)[11]通過(guò)研究Grid-Scan算法與極大似然法的定位特點(diǎn)，并將二者與虛擬錨節(jié)點(diǎn)策略融合，提高了算法的定位精度。文獻(xiàn)[12]通過(guò)兩次網(wǎng)格掃描縮小定位區(qū)域，再結(jié)合錨節(jié)點(diǎn)遞減掃描進(jìn)一步降低定位誤差。文獻(xiàn)[13]在文獻(xiàn)[12]的二次柵格掃描基礎(chǔ)上結(jié)合質(zhì)心迭代算法提高定位精度。文獻(xiàn)[14]在高斯白噪聲的環(huán)境下，采用近似角匹配算法和迭代掃描算法相互作用，一定程度上抑制了定位誤差。

在WSN定位中，信號(hào)傳輸方式可分為兩種，一種是視距（LOS）傳輸，即信號(hào)可以從一個(gè)節(jié)點(diǎn)直線(xiàn)傳輸?shù)搅硪粋€(gè)節(jié)點(diǎn)；另一種是非視距（NLOS）傳輸，由于障礙物的阻礙，信號(hào)只能通過(guò)反射或折射在節(jié)點(diǎn)之間傳輸[15]。實(shí)際上，兩種傳輸方式均存在高斯白噪聲。文獻(xiàn)[11-13]在理想通信信號(hào)傳播模型下對(duì)Grid-Scan算法進(jìn)行改進(jìn)。文獻(xiàn)[14]在視距環(huán)境下提升定位精度。

文中針對(duì)Grid-Scan算法在非視距環(huán)境下提高定位精度展開(kāi)相關(guān)研究。在非視距環(huán)境下提出通信信號(hào)的路徑返回可以有效校正鄰居錨節(jié)點(diǎn)，并推算接近理想的信號(hào)強(qiáng)度。在路徑返回算法的基礎(chǔ)上，進(jìn)一步提出柵格的迭代掃描算法提高定位精度。

1 基本原理

1.1 傳播模型

在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)中，通信信號(hào)的衰減模型分為理想模型和不規(guī)則模型。在理想的信號(hào)傳播模型中，信號(hào)傳播不受噪聲影響，理想模型可表示為[14]

PL(d0)-參考距離為d0時(shí)的路徑損耗功率，一般d0=1 m；

η-路徑損耗指數(shù)；

d-發(fā)射信號(hào)節(jié)點(diǎn)與接收信號(hào)節(jié)點(diǎn)之間的距離。

在實(shí)際環(huán)境下，信號(hào)的衰減受到環(huán)境噪聲的影響。通過(guò)在理想通信模型中加入非視距環(huán)境下的信號(hào)強(qiáng)度衰減量和加高斯隨機(jī)變量，可近似建立非視距通信信號(hào)傳播模型，則

其中，δ是非視距環(huán)境下的信號(hào)強(qiáng)度衰減量與高斯隨機(jī)變量之和。

1.2 Grid-Scan算法原理

Grid-Scan算法是采用規(guī)定的通信半徑對(duì)網(wǎng)格化定位區(qū)域內(nèi)的柵格進(jìn)行掃賦值，以最大賦值柵格的質(zhì)心作為位置估計(jì)[11]。通信圓產(chǎn)生估計(jì)矩形的四邊分別與X軸和Y軸平行，得到估計(jì)矩形的四邊可分別為max(xi-r), min(xi-r), max(yi-r), min(yi-r)。其中，r為鄰居錨節(jié)點(diǎn)的通信半徑，i為表示鄰居錨節(jié)點(diǎn)下標(biāo)，(xi，yi)為錨節(jié)點(diǎn)的坐標(biāo)。在估計(jì)矩形覆蓋的定位區(qū)域內(nèi)，得到柵格的集合G，如圖1所示，則[14]

圖1 Grid-Scan算法原理

式中：l——柵格邊長(zhǎng)；

q——柵格標(biāo)號(hào)。

最大賦值的柵格為Vq，柵格質(zhì)心Cq坐標(biāo)為 (xCq,yCq)，擁有最大賦值的柵格總數(shù)為n，最大賦值的柵格質(zhì)心坐標(biāo)的平均值作為位置估計(jì)(x,y)。

2 信號(hào)路徑返回的柵格迭代算法

由于實(shí)際的環(huán)境噪聲會(huì)影響定位精度，文中提出信號(hào)路徑返回算法減小視距和非視距噪聲的影響。結(jié)合信號(hào)路徑返回算法，進(jìn)一步提出柵格迭代定位算法提高定位精度。

由于受到非視距環(huán)境下的信號(hào)強(qiáng)度衰減量的影響，未知節(jié)點(diǎn)接收到的錨節(jié)點(diǎn)的信號(hào)強(qiáng)度難以達(dá)到最大傳輸。非視距環(huán)境使得信號(hào)強(qiáng)度存在衰減，未知節(jié)點(diǎn)可能無(wú)法采集鄰居錨節(jié)點(diǎn)的通信信號(hào)。如圖2所示，非視距錨節(jié)點(diǎn)A通過(guò)多徑方式傳播信號(hào)，由于多徑傳播對(duì)信號(hào)強(qiáng)度的衰減，未知節(jié)點(diǎn)接收到較大衰減的信號(hào)，甚至無(wú)法接收錨節(jié)點(diǎn)信號(hào)。定位前需要增強(qiáng)未知節(jié)點(diǎn)的信號(hào)發(fā)射功率，在規(guī)定的通信半徑內(nèi)，接收到未知節(jié)點(diǎn)的非視距錨節(jié)點(diǎn)通過(guò)不斷增強(qiáng)發(fā)射信號(hào)來(lái)響應(yīng)未知節(jié)點(diǎn)，從而使得未知節(jié)點(diǎn)與非視距錨節(jié)點(diǎn)建立通信關(guān)系。此時(shí)，非鄰居錨節(jié)點(diǎn)可能被誤判為鄰居錨節(jié)點(diǎn)，而非鄰居錨節(jié)點(diǎn)的介入會(huì)影響定位性能。文中采用信號(hào)強(qiáng)度的路徑返回算法來(lái)消除視距和非視距的噪聲影響，并去除非鄰居錨節(jié)點(diǎn)。

圖2 非視距定位

如圖2所示，當(dāng)非視距錨節(jié)點(diǎn)不斷增強(qiáng)信號(hào)強(qiáng)度時(shí)，將傳播信號(hào)的路徑視為傳播最強(qiáng)信號(hào)強(qiáng)度的路徑，則未知節(jié)點(diǎn)接收到第i個(gè)錨節(jié)點(diǎn)的最強(qiáng)信號(hào)強(qiáng)度可表示為

當(dāng)錨節(jié)點(diǎn)向未知節(jié)點(diǎn)廣播信息時(shí)，廣播信號(hào)攜帶錨節(jié)點(diǎn)坐標(biāo)和信號(hào)強(qiáng)度，未知節(jié)點(diǎn)通過(guò)標(biāo)記信號(hào)強(qiáng)度和坐標(biāo)信息對(duì)錨節(jié)點(diǎn)進(jìn)行區(qū)分。由于非視距環(huán)境對(duì)信號(hào)強(qiáng)度的影響，當(dāng)未知節(jié)點(diǎn)以接收到錨節(jié)點(diǎn)的信號(hào)強(qiáng)度為信號(hào)發(fā)射強(qiáng)度時(shí)，錨節(jié)點(diǎn)可能接收不到路徑返回信號(hào)，未知節(jié)點(diǎn)需要再次增強(qiáng)信號(hào)強(qiáng)度以保持與錨節(jié)點(diǎn)的通信。因此，對(duì)發(fā)射的信號(hào)強(qiáng)度設(shè)置增強(qiáng)系數(shù)ωi保證非視距環(huán)境下信號(hào)強(qiáng)度的采集，則

同理，錨節(jié)點(diǎn)對(duì)接收到未知節(jié)點(diǎn)的信號(hào)強(qiáng)度設(shè)置增強(qiáng)系數(shù)，使得未知節(jié)點(diǎn)可以接收到錨節(jié)點(diǎn)的信號(hào)強(qiáng)度，則

未知節(jié)點(diǎn)通過(guò)P1(xi,yi)，P2(xi,yi)，P1(xi,yi)和 ωi計(jì)算接收到第i個(gè)錨節(jié)點(diǎn)的信號(hào)強(qiáng)度，即

當(dāng)P0(xi,yi)滿(mǎn)足設(shè)定的通信半徑要求，判定第i個(gè)錨節(jié)點(diǎn)為鄰居錨節(jié)點(diǎn)。節(jié)點(diǎn)間的信號(hào)增強(qiáng)系數(shù)ωi以數(shù)字信息的方式相互傳輸，當(dāng)錨節(jié)點(diǎn)發(fā)送信號(hào)時(shí)，將上一次接收未知節(jié)點(diǎn)的增強(qiáng)系數(shù)傳輸給未知節(jié)點(diǎn)，從而使得未知節(jié)點(diǎn)估計(jì)出P0(xi,yi)的值。

信號(hào)路徑返回對(duì)于視距錨節(jié)點(diǎn)同樣適用，從而減小視距噪聲對(duì)信號(hào)強(qiáng)度的影響。因此，信號(hào)路徑返回可優(yōu)化整體WSN網(wǎng)絡(luò)鄰居節(jié)點(diǎn)的關(guān)系，并計(jì)算接近理想通信信號(hào)傳播模型的信號(hào)強(qiáng)度。

通過(guò)信號(hào)路徑返回優(yōu)化節(jié)點(diǎn)的鄰居關(guān)系，采用原始的Grid-Scan算法得到相對(duì)縮小的定位區(qū)域，并得到估計(jì)位置點(diǎn)F。如圖2所示，通過(guò)優(yōu)化錨節(jié)點(diǎn)A，B與未知節(jié)點(diǎn)U的信號(hào)強(qiáng)度，由式(1)將信號(hào)強(qiáng)度轉(zhuǎn)化為距離，得到四邊形AUBF，則由四邊形對(duì)角線(xiàn)得到三角形的內(nèi)角為

假設(shè)四邊形AUBF為凸四邊形，則內(nèi)角關(guān)系為其中，α1和β2可直接由式(11)和式(12)計(jì)算得到，則對(duì)式(9)和式(10)進(jìn)行變換可得

當(dāng)最大賦值的柵格Vq滿(mǎn)足|CqF-UF|≤l/2時(shí)，將增加一次賦值Vq。如圖2所示，陰影部分為新的最大賦值柵格。將初始位置估計(jì)點(diǎn)F替換為柵格質(zhì)心Cq坐標(biāo)為 (xCq,yCq)，采用式 (9)～式 (23)的算法得到CqU，則 min{CqU}所對(duì)應(yīng)的柵格質(zhì)心Cq(xCq,yCq)為最終的位置估計(jì)。

3 算法仿真及對(duì)比分析

在100 m×100 m的監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)產(chǎn)生k次節(jié)點(diǎn)網(wǎng)絡(luò)，設(shè)置路徑損耗系數(shù)η=4，k=100。控制節(jié)點(diǎn)總數(shù)，錨節(jié)點(diǎn)數(shù)，通信半徑，在Matlab 2014a上對(duì)算法的定位性能進(jìn)行仿真，節(jié)點(diǎn)網(wǎng)絡(luò)中的未知節(jié)點(diǎn)的平均定位誤差[14]為：

非視距環(huán)境下對(duì)算法的節(jié)點(diǎn)關(guān)系的校正性能和定位精度測(cè)試。設(shè)網(wǎng)絡(luò)中節(jié)點(diǎn)的通信半徑設(shè)置為r=50 m。如圖3所示，以C型網(wǎng)絡(luò)模型仿真非視距廊道環(huán)境，隨機(jī)部署節(jié)點(diǎn)，*表示錨節(jié)點(diǎn)，○表示未知節(jié)點(diǎn)。將Grid-Scan算法記為GS算法，將采用路徑返回的Grid-Scan算法記為T(mén)GS算法，將采用路徑返回的柵格迭代算法記為T(mén)GSI算法。

圖3 網(wǎng)絡(luò)部署

設(shè)置柵格邊長(zhǎng)l=0.2r，節(jié)點(diǎn)總數(shù)從50個(gè)增加至150個(gè)，錨節(jié)點(diǎn)數(shù)為節(jié)點(diǎn)總數(shù)的0.4倍，如圖4(a)所示，算法的定位誤差均呈下降趨勢(shì)，誤差平均值為 0.46，TGS算法較 GS算法誤差降低約 0.09，TGSI算法較GS算法誤差降低約0.19。設(shè)置節(jié)點(diǎn)總數(shù)為100個(gè)，柵格邊長(zhǎng)l=0.2r，錨節(jié)點(diǎn)數(shù)由20個(gè)增至60個(gè)，如圖4(b)所示，算法的定位誤差隨著錨節(jié)點(diǎn)增大逐漸下降，誤差平均值為0.46，TGS算法較GS算法誤差降低約0.10，TGSI算法較GS算法誤差降低約0.18。設(shè)置節(jié)點(diǎn)總數(shù)為100個(gè)，錨節(jié)點(diǎn)數(shù)為40個(gè)，如圖4(c)所示，改變定位區(qū)域內(nèi)柵格邊長(zhǎng)對(duì)GS算法和TGS算法定位誤差沒(méi)有明顯影響。由于柵格迭代掃描算法，柵格邊長(zhǎng)較小時(shí)，TGSI算法定位精度相對(duì)較高，TGS算法較GS算法誤差降低約0.09，TGSI算法較GS算法誤差降低約0.26。

圖4 定位誤差

由圖4的定位誤差對(duì)比可知，在通信信號(hào)路徑返回算法基礎(chǔ)上采用Grid-Scan算法較非視距環(huán)境下直接采用Grid-Scan算法的定位精度有一定程度的提高。因此，路徑返回算法提高了非視距環(huán)境下Grid-Scan算法的定位性能。在路徑返回算法基礎(chǔ)上采用Grid-Scan算法和柵格迭代掃描算法時(shí)，迭代掃描一定程度上降低了定位誤差。相比于文獻(xiàn)[11-14]，文中的算法在非視距環(huán)境下優(yōu)化了Grid-Scan算法的定位性能。

文獻(xiàn)[12-13]中的算法是在理想通信信號(hào)傳播模型下對(duì)柵格掃描算法進(jìn)行改進(jìn)，難以克服定位區(qū)域內(nèi)視距和非視距噪聲的影響時(shí)。分析文獻(xiàn)[11]中的數(shù)據(jù)結(jié)果可知，該算法在視距噪聲環(huán)境下的平均定位誤差約為0.42。因此，該算法在存在噪聲環(huán)境下的定位性能是大幅度降低的。文獻(xiàn)[14]采用雙迭代算法一定程度上提高了視距環(huán)境下的定位精度。數(shù)據(jù)分析采用原算法的定位性能為對(duì)比標(biāo)準(zhǔn)，使得文中算法和文獻(xiàn)[14]算法的實(shí)驗(yàn)數(shù)據(jù)具有基本參考的可比性。如表1所示，在視距和非視距混合的環(huán)境下，文中算法在三種控制條件下較原算法的平均定位誤差分別降低了0.19，0.18和0.26。在視距環(huán)境下，文獻(xiàn)[14]中算法的在三種控制條件下較原算法的平均定位誤差分別降低了0.19，0.18和0.18。文中算法在視距和非視距混合的環(huán)境下的定位精度優(yōu)于文獻(xiàn)[14]在單一視距環(huán)境下的定位精度。由于非視距環(huán)境比視距環(huán)境更加復(fù)雜，因此，文中的定位算法總體優(yōu)于文獻(xiàn)[14]的定位算法。

表1 算法平均定位誤差

4 結(jié)束語(yǔ)

文中首先提出無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的通信信號(hào)路徑返回算法來(lái)抑制非視距環(huán)境下的噪聲，在信號(hào)路徑返回算法和Grid-Scan算法的基礎(chǔ)上提出網(wǎng)格迭代掃描算法進(jìn)一步提高定位精度。信號(hào)路徑返回算法可以同時(shí)抵消視距和非視距環(huán)境下的噪聲，從而判定正確的鄰居錨節(jié)點(diǎn)。由于定位區(qū)域的網(wǎng)格化，為減少每個(gè)柵格迭代的計(jì)算量，通過(guò)Grid-Scan算法縮小定位區(qū)域，選取滿(mǎn)足條件的柵格進(jìn)行賦值迭代估計(jì)，得到接近真實(shí)位置的一個(gè)柵格質(zhì)心，完成位置估計(jì)。在無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的非視距定位技術(shù)中，文中提出的算法一定程度上提高了定位精度。