程良 張永強(qiáng) 王艷娥 司海峰 李璐

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；PIT法則；估計矩形；質(zhì)心迭代

無線傳感器網(wǎng)絡(luò)作為一個應(yīng)用廣泛的技術(shù)，具有自組網(wǎng)、健壯性強(qiáng)等特點，備受研究者們關(guān)注[1]?，F(xiàn)階段的定位算法主要分為兩類：基于測距以及非測距[2]。相比測距算法，非測距算法具有通信開銷小、功耗低等優(yōu)點，得到了廣大研究人員的認(rèn)可，是現(xiàn)階段研究工作的重點之一[3]。

現(xiàn)階段較為流行且先進(jìn)的無線傳感器網(wǎng)絡(luò)定位算法有以下幾種。文獻(xiàn)[4]對邊界盒定位算法進(jìn)行了改進(jìn)，該算法主要是通過縮小定位區(qū)域來提高精度；文獻(xiàn)[5]綜合測距與非測距定位算法的特點進(jìn)行定位，根據(jù)RSSI值來計算相關(guān)權(quán)重來提高定位精度。文獻(xiàn)[6]找出錨節(jié)點組成的三角形中最小的那一個作為閾值三角形，來進(jìn)一步確定為未知節(jié)點坐標(biāo)。文獻(xiàn)[7]采用極限分割的思想，將Bounding-box算法中形成的估計矩形進(jìn)行了無限次分割來提高定位精度。本文通過分析基本Bounding-Box 算法原理，將原始矩形進(jìn)行一次分割后，采用三角質(zhì)心迭代的方式來極限逼近未知節(jié)點，從而減小了平均相對定位誤差，提高了定位準(zhǔn)確度。

1 Bounding-Box 算法簡介

Bounding-Box 算法的基本工作原理：在一個二維區(qū)域內(nèi)，待定位節(jié)點接收到周圍最近三個錨節(jié)點的信號強(qiáng)度，然后以該錨節(jié)點為圓心，通信距離為半徑畫圓，同時將三個圓的外接矩形求出，以它們重合區(qū)域的質(zhì)心作為未知節(jié)點的位置[8]，可將該算法分為3個步驟。

1） 在一個二維平面內(nèi)，隨機(jī)布置多個錨節(jié)點和未知節(jié)點，錨節(jié)點將自身的位置信息廣播至整個網(wǎng)絡(luò)。在該網(wǎng)絡(luò)中，錨節(jié)點發(fā)送的信號能被未知節(jié)點接收到的稱為最近錨節(jié)點。

2） 以未知節(jié)點周圍錨節(jié)點為圓心，它們的通信距離為半徑畫圓，得到圓的外切正方形。

3） 將第二步得到的各外接矩形的重合區(qū)域作為初步定位區(qū)域，即初步未知節(jié)點的預(yù)估位置為該重合區(qū)域的中心位置。如圖1所示，外接矩形的重疊部分區(qū)域是一個平行X 軸和Y 軸的矩形，分別將該矩形的左、右、上、下四個邊記為left、right、up以及down，并且求出該重合矩形的中心位置，以此作為最終估計位置。

2 算法改進(jìn)

分析Bounding-box算法可知，只通過鄰居錨節(jié)點所得到的外切正方形重合區(qū)域質(zhì)心作為未知節(jié)點的位置估計會造成較大誤差。文中采用分割的思想，將定位區(qū)域逐漸縮小，從而降低算法的平均相對定位誤差。

改進(jìn)過程可分為三步：

第一步：估計初始位置坐標(biāo)

通過定位算法求解的外切正方形所形成的重合矩形可作為初步的定位區(qū)域，求出該區(qū)域的中心點位置坐標(biāo)（x0，y0 ），將該坐標(biāo)作為初步的定位位置。

第二步：找到最近錨節(jié)點

對未知節(jié)點接收到周圍錨節(jié)點的信號強(qiáng)度值進(jìn)行標(biāo)記：

第三步：三角形質(zhì)心迭代

1） 一次分割

Bounding-Box算法得到的最初估計區(qū)域是根據(jù)最近錨節(jié)點畫通信圓，每個圓的外接矩形形成的重合矩形部分為最初定位區(qū)域。將該定位區(qū)域的中心位置坐標(biāo)記為（x0，y0 ），以該坐標(biāo)為中心，將該重合矩形分成四個子矩形，分別記為B1、B2、B3 、B4且大小分別為式（3）～式（6）。

如圖2所示，其中（xi，yi ）分別作為鄰居錨節(jié)點的坐標(biāo)位置，R為通信半徑。由四個子矩形得到的質(zhì)心稱為偏移質(zhì)心（xes，yes ），其中s 下標(biāo)代表的是不同的子矩形。采用兩點距離公式求出偏移質(zhì)心到最近錨節(jié)點的距離，設(shè)為dist，如式（7）所示：

找出最近距離min（dist），假設(shè)B2子矩形的質(zhì)心到最近錨節(jié)點A1最近，將B2的質(zhì)心（xe2，ye2 ）稱為待選質(zhì)心。求初始位置坐標(biāo)和待選質(zhì)心的中點坐標(biāo)GS1為（xs1，ys1 ），再計算該中點坐標(biāo)到最近錨節(jié)點的距離dis，并且以A1為圓心，dis 為半徑畫圓，交估計矩形于Q，K 兩點。將距離dis 帶入式（8）求出對應(yīng)的信號強(qiáng)度RSS （dis），比較RSS （dis） 與max（RSS） 大小關(guān)系，若RSS （dis）

2） PIT法則

對于WSN的拓?fù)渚W(wǎng)絡(luò)，各節(jié)點都屬于靜止?fàn)顟B(tài)，所以不能采用PIT法則進(jìn)行未知節(jié)點位置的判斷。為了達(dá)到實驗效果，采用近似PIT的方法，因為未知節(jié)點和錨節(jié)點之間可以進(jìn)行信號強(qiáng)度的接收，所以利用這種信號強(qiáng)度隨距離變化的關(guān)系就可以模擬未知節(jié)點的運動情況，進(jìn)而對未知節(jié)點的位置進(jìn)行判斷。

由于未知節(jié)點可以探測到周圍錨節(jié)點的信號強(qiáng)度大小，所以可以讀出三個鄰居節(jié)點M1，M2，M3的信號強(qiáng)度值。假設(shè)X 運動到其中一點，就可以認(rèn)為未知節(jié)點的信號強(qiáng)度變成了該點的信號強(qiáng)度，從而判斷出移動的過程中未知節(jié)點與三個頂點間信號強(qiáng)度的變化關(guān)系，同理遠(yuǎn)離也一樣，進(jìn)而就可以判斷出未知節(jié)點是否在三角形M1，M2，M3中。

一次分割完成后，以最近錨節(jié)點A1 為圓心，A1 到GS1 為半徑畫圓，得到與B2區(qū)域的兩個焦點設(shè)為Q，K，連接Q，K，A1 構(gòu)成三角形。通過PIT法則判斷，如果未知節(jié)點在三角形內(nèi)部，則求其質(zhì)心P1，否則以Q，K，P1為三個頂點組成新的三角形繼續(xù)迭代，直到未知節(jié)點不在三角形Q，K，Pn內(nèi)部，迭代終止。算法流程如下：

步驟1：計算未知節(jié)點到Q，K，P1，P2...Pn的距離

如果在一個二維區(qū)域內(nèi)，存在一個未知節(jié)點O（x，y ），它周圍的鄰居錨節(jié)點分別為A1，A2...An，設(shè)第n 個信標(biāo)節(jié)點的坐標(biāo)為（xn，yn ），則未知節(jié)點到鄰居錨節(jié)點距離dn為：

通過兩點間距離公式可得質(zhì)心坐標(biāo)到未知節(jié)點的距離，記為ds。

因此，由公式推導(dǎo)可得：若知道dn，則可以求出未知節(jié)點O 到質(zhì)心S的距離ds。以質(zhì)心S 為圓心，ds 為半徑作一個圓MO 的方程。過質(zhì)心S 分別與Q 和K 連接形成的直線交于圓MO，設(shè)交點坐標(biāo)分別為U 和V，將QU 與KV 之間的距離近似當(dāng)作Q到未知節(jié)點和K到未知節(jié)點的距離。

步驟2：三角形質(zhì)心迭代定位

進(jìn)行三角形質(zhì)心迭代定位之前，要先確定未知節(jié)點是否在相應(yīng)的三角形內(nèi)。由步驟1知道未知節(jié)點分別到Q、K的距離后，利用PIT法則判斷出未知節(jié)點是否處于三角形A1，Q，K 內(nèi)，因為Q，K 處于未知節(jié)點和最近錨節(jié)點形成的同心圓內(nèi)，所以將Q，K 固定不變并且與質(zhì)心P1 形成新的三角形，然后通過PIT法則判斷。若未知節(jié)點在三角形QKP1 內(nèi)，則繼續(xù)進(jìn)行迭代運算，直到未知節(jié)點不在新構(gòu)成的三角形Q，K，Pn 內(nèi)，否則算法迭代終止。

設(shè)未知節(jié)點到Q，K，P1，P2...Pn的距離為d3。

找出d3 中最小的距離記為min（d3 ），則對應(yīng)的質(zhì)心為最終位置估計。隨著迭代次數(shù)的增加，若未知節(jié)點處于Q，K 所構(gòu)成的直線附近，那么會有無限次的迭代，因此需要設(shè)置迭代閾值。

設(shè)dpn 與通信半徑r 的比值為誤差ξ，如果ξ 小于設(shè)定閾值，則迭代終止，如式（16）所示。

3 仿真實驗

3.1 實驗設(shè)計

該實驗利用Matlab 為仿真工具，來模擬仿真這幾種算法分別在不同環(huán)境下的平均定位誤差精度。文中新設(shè)計的算法記作TCIBounding - Box 算法，文獻(xiàn)[4-7]中所提到的定位算法分別記為RBounding - Box、RSSI - Centroid、APIT - Minimum 以及DBounding - Box。監(jiān)測區(qū)域設(shè)計為100m × 100m，其中設(shè)節(jié)點數(shù)個數(shù)為N，錨節(jié)點的個數(shù)為M，節(jié)點通信半徑為R，其中設(shè)PT=0dB，d0=1m，PT（d0）=55dB，?=4，ξ=0.1。設(shè)網(wǎng)絡(luò)中定位算法的平均相對定位誤差為E，計算公式如式（17）。

其中（xr，yr）是未知節(jié)點的估計坐標(biāo)，（xt，yt）是未知節(jié)點的真實坐標(biāo)，k為拓?fù)浯螖?shù)，nr 參與定位的未知節(jié)點個數(shù)。

為了使實驗結(jié)果更具有說服性，將每次實驗產(chǎn)生的拓?fù)鋱鼍胺謩e提供給以上算法進(jìn)行對比。

3.2 節(jié)點數(shù)對定位精度的影響

節(jié)點總數(shù)是衡量一個拓?fù)渚W(wǎng)絡(luò)整體性能的重要參數(shù)，節(jié)點過多會提高成本，錨節(jié)點過少會影響實驗精度。因此，本實驗設(shè)錨節(jié)點數(shù)為0.2N，通信半徑為30m，仿真結(jié)果如圖5所示。

分析圖5可得，隨著節(jié)點數(shù)越來越多，TCIBounding- Box 算法相比于傳統(tǒng)算法、RBounding - Box、RSSI - Centroid、APIT - Minimum 以及DBounding - Box 算法的定位誤差分別降低了14.12%，6.72%，5.09%，3.53% 以及2.68%。

3.3 錨節(jié)點數(shù)的影響

錨節(jié)點作為整個WSN網(wǎng)絡(luò)位置信息的參考點，數(shù)量決定著定位精度。實驗中設(shè)N為100，R為30m，k= 100次。如圖6是錨節(jié)點數(shù)量從20增至80的仿真圖。

由圖6可得，錨節(jié)點越多，算法的平均定位誤差越小。文中TCIBounding-Box 分別較傳統(tǒng)算法，文獻(xiàn)[4-7]提到的算法，在平均定位誤差上分別降低了6.19%，5.42%，4.22%，3.77%以及2.68%。

3.4 通信半徑對定位精度的影響

由分析得，通信半徑對外接矩形區(qū)域大小有影響。如果通信半徑距離過小，會導(dǎo)致部分節(jié)點不能參與定位。實驗中節(jié)點個數(shù)和錨節(jié)點個數(shù)按照一定比例投放，保證其他條件都不變的情況下，通信半徑對實驗的影響。圖7為仿真圖。

分析圖7可知，文中提出的TCIBounding-Box 算法相比于傳統(tǒng)的算法在平均定位誤差上減少15.42%。文獻(xiàn)[4]中的算法在平均定位誤差上相比于傳統(tǒng)算法有所降低，但與文中所提算法相比，定位精度降低了7.15%。文獻(xiàn)[5]中的定位算法，在精度上與文中所提算法相比降低了5.25%。文獻(xiàn)[6]中的算法降低了3.60%。文獻(xiàn)[7]中的算法降低了2.66%。

4 結(jié)束語

本文先對Bounding-Box算法進(jìn)行了研究分析，并在該基礎(chǔ)上利用最近錨節(jié)點將產(chǎn)生的外接矩形區(qū)域進(jìn)行一次分割，以此進(jìn)一步縮小定位區(qū)域。通過判斷未知節(jié)點是否在最近錨節(jié)點的通信圓內(nèi)，對定位區(qū)域進(jìn)一步縮小，然后通過三角形質(zhì)心迭代思路不斷縮小定位區(qū)域。仿真實驗表明，在不同節(jié)點個數(shù)，錨節(jié)點個數(shù)以及通信半徑下，本文所提出的TCIBounding- Box算法均有效減小了平均定位誤差。