董恩清,劉偉,宋洋

(山東大學(xué)(威海)機(jī)電與信息工程學(xué)院,264209,山東威海)

?

采用三角形節(jié)點(diǎn)塊處理無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位中節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法

董恩清,劉偉,宋洋

(山東大學(xué)(威海)機(jī)電與信息工程學(xué)院,264209,山東威海)

針對最小二乘法在無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)定位中產(chǎn)生的節(jié)點(diǎn)翻轉(zhuǎn)歧義問題,提出了一種基于三角形節(jié)點(diǎn)塊處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法(OPD-IP-INB)。該方法首先采用基于正交投影的節(jié)點(diǎn)翻轉(zhuǎn)歧義檢測方法對網(wǎng)絡(luò)中所需定位的節(jié)點(diǎn)進(jìn)行檢測,然后根據(jù)三角形節(jié)點(diǎn)塊具有的穩(wěn)定性,充分利用全網(wǎng)絡(luò)的連通性信息,通過坐標(biāo)變換采用逐次尋優(yōu)性的迭代方法,對發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn)進(jìn)行定位處理。仿真結(jié)果表明:OPD-IP-INB方法可以很好地處理最小二乘法中的節(jié)點(diǎn)翻轉(zhuǎn)歧義問題,而且提高了整個網(wǎng)絡(luò)的定位精度;與最小二乘法相比,隨著信標(biāo)節(jié)點(diǎn)的減少,其定位精度可以提高3%～10%;隨著測距誤差的減小,其定位精度可以提高2%～7%。

無線傳感器網(wǎng)絡(luò);節(jié)點(diǎn)定位;翻轉(zhuǎn)歧義;正交投影

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)的重要支撐技術(shù)之一[1-3]。目前,節(jié)點(diǎn)定位方法一般分為基于測距的定位方法和距離無關(guān)的定位方法[4]。相對于距離無關(guān)的方法,基于測距的方法具有較高的定位精度。由于無線傳感器網(wǎng)絡(luò)的應(yīng)用一般需要精確的節(jié)點(diǎn)位置信息[5-7],所以基于測距的節(jié)點(diǎn)定位更符合實(shí)際的應(yīng)用需求。作為基于測距的方法之一,最小二乘法具有原理簡單、定位精度高等優(yōu)點(diǎn),所以被廣泛地使用。但是,最小二乘法在定位過程中會發(fā)生節(jié)點(diǎn)的翻轉(zhuǎn)歧義問題,而且節(jié)點(diǎn)翻轉(zhuǎn)歧義還可能產(chǎn)生雪崩效應(yīng),嚴(yán)重時能導(dǎo)致整個網(wǎng)絡(luò)節(jié)點(diǎn)的定位失效。

目前已經(jīng)有研究者提出了許多翻轉(zhuǎn)歧義的檢測方法,其中Liu等人提出的基于正交投影的檢測方法[8]是目前檢測效果較好的一種方法,該方法具有檢測精度高、計算復(fù)雜度低的優(yōu)點(diǎn)。

對檢測出可能發(fā)生翻轉(zhuǎn)岐義的節(jié)點(diǎn),有2種處理手段,一種是非聯(lián)合節(jié)點(diǎn)連通信息處理,另一種是聯(lián)合多節(jié)點(diǎn)連通信息處理。文獻(xiàn)[9]提出了一種消除歧義的優(yōu)化定位策略,該策略是一種非聯(lián)合節(jié)點(diǎn)連通信息處理方法,它是利用計算出的2個節(jié)點(diǎn)位置(真實(shí)點(diǎn)位置和節(jié)點(diǎn)翻轉(zhuǎn)歧義位置)與其他鄰居節(jié)點(diǎn)的相互通信關(guān)系來消除翻轉(zhuǎn)歧義節(jié)點(diǎn);文獻(xiàn)[10]也是一種非聯(lián)合節(jié)點(diǎn)連通信息處理方法,該方法通過分析、檢測未知節(jié)點(diǎn)的鄰居節(jié)點(diǎn)是否隱性共線來選出發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn),再對選出的節(jié)點(diǎn)采用消除方法來去除歧義節(jié)點(diǎn)。

Xiao等人提出了一種新的節(jié)點(diǎn)定位方法——迭代不變體合并(Iterative Inflexible Body Merging, IIBM)算法[11]。該算法是一種基于塊拼接的定位算法,它將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分成許多個節(jié)點(diǎn)塊,然后對每個節(jié)點(diǎn)塊進(jìn)行拼接定位。由于考慮了節(jié)點(diǎn)塊可能存在的翻轉(zhuǎn)歧義,所以該算法間接地處理了節(jié)點(diǎn)翻轉(zhuǎn)歧義問題。但是,文獻(xiàn)[11]算法采用了各種形狀的節(jié)點(diǎn)塊進(jìn)行拼接,增加了定位中節(jié)點(diǎn)塊的自身形變,這樣就產(chǎn)生了多種形式的節(jié)點(diǎn)塊翻轉(zhuǎn)歧義問題,從而增加了處理的復(fù)雜度。

受到文獻(xiàn)[11]迭代不變體合并算法的啟發(fā),根據(jù)三角形節(jié)點(diǎn)塊具有的穩(wěn)定性,并充分利用全網(wǎng)絡(luò)的連通性信息,本文提出了一種基于三角形節(jié)點(diǎn)塊的處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法(after orthogonal projection detection, iterative processing method based on triangular node blocks, OPD-IP-TNB)。該方法是在本課題組所提出的基于正交投影的節(jié)點(diǎn)翻轉(zhuǎn)歧義檢測方法[9]的基礎(chǔ)上,對網(wǎng)絡(luò)中需要定位的節(jié)點(diǎn)進(jìn)行檢測,再用文獻(xiàn)[11]提出的迭代方法處理節(jié)點(diǎn)翻轉(zhuǎn)歧義。本文方法具有比較好的系統(tǒng)性和完整性,能夠很好地處理網(wǎng)絡(luò)中節(jié)點(diǎn)的翻轉(zhuǎn)歧義問題,具有一定的實(shí)際應(yīng)用價值。

1 節(jié)點(diǎn)翻轉(zhuǎn)歧義

節(jié)點(diǎn)定位中的節(jié)點(diǎn)翻轉(zhuǎn)歧義問題是指未知節(jié)點(diǎn)在利用鄰居已知節(jié)點(diǎn)進(jìn)行定位時,如果鄰居節(jié)點(diǎn)共線或近似共線,則可能得到2個關(guān)于某一條直線成鏡像關(guān)系的估計位置。假設(shè)未知節(jié)點(diǎn)P有3個鄰居信標(biāo)節(jié)點(diǎn)A、B、C,該未知節(jié)點(diǎn)到這3個鄰居信標(biāo)節(jié)點(diǎn)的測量距離分別為d1、d2、d3。分別以信標(biāo)節(jié)點(diǎn)A和B為圓心,以測量距離d1和d2作圓,如圖1所示,那么未知節(jié)點(diǎn)必定為2個圓交點(diǎn)P和P′中的一個,且這2個交點(diǎn)關(guān)于直線AB對稱。

圖1 節(jié)點(diǎn)翻轉(zhuǎn)歧義示意圖

假設(shè)所求未知節(jié)點(diǎn)的真實(shí)位置為P,信標(biāo)節(jié)點(diǎn)C到P和P′的距離為dCP和dCP′。根據(jù)未知節(jié)點(diǎn)P到鄰居信標(biāo)節(jié)點(diǎn)C的測量距離d3來判斷,dCP和dCP′中的哪一個與d3比較接近就選擇哪一個為節(jié)點(diǎn)的定位位置。當(dāng)A、B和C幾乎共線時,dCP和dCP′相差不大,由于測距誤差的存在,就有可能錯誤地將P′作為未知節(jié)點(diǎn)的定位位置,如果這種錯誤定位位置再參與其他未知節(jié)點(diǎn)的定位,將導(dǎo)致整個網(wǎng)絡(luò)無法正確定位。

2 基于三角形節(jié)點(diǎn)塊處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法

2.1 迭代不變體合并算法

在迭代不變體合并算法[11]中,令2個節(jié)點(diǎn)塊之間的約束集合為C={li},li=[mi,ni,di,ωi]。其中l(wèi)表示約束,i表示約束的索引,mi表示信標(biāo)節(jié)點(diǎn)塊所在坐標(biāo)系Φm中的節(jié)點(diǎn)坐標(biāo),ni表示未知節(jié)點(diǎn)塊所在坐標(biāo)系Φn中的節(jié)點(diǎn)坐標(biāo),di表示mi與ni的測量距離,ωi為測量距離的約束權(quán)重。

根據(jù)上面的定義,迭代不變體合并算法就是構(gòu)建一個坐標(biāo)變換方程和誤差約束方程如下

TP,R(p*)=P+Rp*

(1)

ei(TP,R)=ωi(di-‖pi-TP,R(p*)‖)

(2)

式中:ei(TP,R)表示第i個約束的轉(zhuǎn)換誤差;P表示轉(zhuǎn)換變量;p*表示節(jié)點(diǎn)塊所在坐標(biāo)系Φn中的節(jié)點(diǎn)坐標(biāo);R表示旋轉(zhuǎn)變量矩陣;pi表示信標(biāo)節(jié)點(diǎn)塊所在坐標(biāo)系Φm中的節(jié)點(diǎn)坐標(biāo)。迭代不變體合并算法是構(gòu)建一個目標(biāo)函數(shù),如下式所示

(3)

式中:|C|表示約束集C的個數(shù)。

迭代不變體合并算法的主要計算步驟如下。

(1)已知約束集C,選取算法迭代的初始變量值P、R。

(2)給定時刻t的初始值,通過式(4)和式(5)來求得t+1時刻的P、R值,如此反復(fù)迭代更新P、R值,即

(4)

(5)

式中

(6)

(7)

式中:δ表示迭代步長;M表示未知節(jié)點(diǎn)塊中的節(jié)點(diǎn)數(shù)(本文基于三角形節(jié)點(diǎn)塊方法,M為3);Rrod表示羅德里格旋轉(zhuǎn)矩陣;TP(t),R(t)表示t時刻的坐標(biāo)轉(zhuǎn)換矩陣。

迭代不變體合并算法把將節(jié)點(diǎn)定位過程類比為彈簧受力,最終達(dá)到平衡的過程。它將每個約束集Ci中的2個節(jié)點(diǎn)看作被一個彈簧相連,式(7)中的Fi(t)相當(dāng)于第i個約束施加在彈簧上的力。式(6)中的F(t)則表示所有的約束施加在彈簧上的合力。

(8)

式中:P(t+n)和R(t+n)表示t+n時刻的P、R值;ε為一很小的正數(shù)。

2.2 三角形節(jié)點(diǎn)塊迭代處理方法

當(dāng)節(jié)點(diǎn)定位過程可能發(fā)生翻轉(zhuǎn)歧義時,處理翻轉(zhuǎn)歧義的主要方法就是利用網(wǎng)絡(luò)中更多的其他節(jié)點(diǎn)信息來參與定位?；谶@種思想,對可能發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn)找到其所有的鄰居非信標(biāo)節(jié)點(diǎn),然后在這些鄰居非信標(biāo)節(jié)點(diǎn)中每次選出3個節(jié)點(diǎn)(其中必須含有本次所需定位的未知節(jié)點(diǎn))構(gòu)成一個三角形節(jié)點(diǎn)塊。

假設(shè)所求未知節(jié)點(diǎn)P有3個鄰居信標(biāo)節(jié)點(diǎn)B1、B2、B3,用集合Ω1來表示;S、Q、U、V、M、N為P點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn),用集合γ來表示;B4,B5,B6,…為集合γ中節(jié)點(diǎn)的鄰居信標(biāo)節(jié)點(diǎn),用集合Ω2表示。首先,對未知節(jié)點(diǎn)P定位時進(jìn)行正交投影檢測,判斷出該節(jié)點(diǎn)可能會發(fā)生節(jié)點(diǎn)翻轉(zhuǎn)歧義。然后,將未知節(jié)點(diǎn)P與集合γ中的任意2個節(jié)點(diǎn)組成多個不同的三角形節(jié)點(diǎn)塊,此處僅列舉出4個三角形節(jié)點(diǎn)塊,如圖2中的三角形節(jié)點(diǎn)塊PSQ、PUV、PSM和PVN所示。

圖2 三角形節(jié)點(diǎn)塊示意圖

在找到包含未知節(jié)點(diǎn)P的多個三角形節(jié)點(diǎn)塊之后,構(gòu)建2個坐標(biāo)系,此處以三角形節(jié)點(diǎn)塊PSQ為例進(jìn)行說明。將三角形節(jié)點(diǎn)塊PSQ的所有鄰居信標(biāo)節(jié)點(diǎn)所在的坐標(biāo)系記為Φm,由未知節(jié)點(diǎn)P、S、Q構(gòu)成的三角形節(jié)點(diǎn)塊所在的坐標(biāo)系記為Φn。通過采用迭代不變體合并算法的坐標(biāo)變換公式(本文中約束誤差方程中的系數(shù)ωi取為1),求出三角形節(jié)點(diǎn)塊的坐標(biāo)。

基于三角形節(jié)點(diǎn)塊迭代處理方法,首先使用文獻(xiàn)[9]中的基于正交投影的方法對未知節(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)歧義檢測,如果檢測后節(jié)點(diǎn)不會發(fā)生翻轉(zhuǎn)歧義,那么仍舊采用最小二乘法進(jìn)行定位。如果檢測后節(jié)點(diǎn)可能會發(fā)生翻轉(zhuǎn)歧義,那么采用本文方法進(jìn)行處理。

本文提出的基于三角形節(jié)點(diǎn)塊迭代方法的計算復(fù)雜度和三角形節(jié)點(diǎn)塊的數(shù)量有關(guān),也就是與未知節(jié)點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn)的數(shù)量有關(guān)。假設(shè)未知節(jié)點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn)的個數(shù)為k。由于任意2個未知節(jié)點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn)都可以和該未知節(jié)點(diǎn)組成一個三角形節(jié)點(diǎn)塊,所以本文方法的計算復(fù)雜度為O(k2)。由此可見,當(dāng)未知節(jié)點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn)的數(shù)量較大時,本文方法的計算復(fù)雜度較高。不過一般來說,未知節(jié)點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn)的數(shù)量越大,則網(wǎng)絡(luò)的連通度越大,未知節(jié)點(diǎn)發(fā)生翻轉(zhuǎn)歧義的概率則越低,因此這種情況下處理翻轉(zhuǎn)歧義的概率也越低。本文提出的基于三角形節(jié)點(diǎn)塊迭代方法在使用過程中,主要遇到的還是未知節(jié)點(diǎn)的鄰居非信標(biāo)節(jié)點(diǎn)的數(shù)量較小時的情況,而此時算法的計算復(fù)雜度并不大。

本文利用了上文2.1節(jié)迭代不變體合并算法的坐標(biāo)變換公式,但在計算處理過程中與迭代不變體合并算法有明顯區(qū)別。

2.2.1 網(wǎng)絡(luò)中處理的節(jié)點(diǎn)數(shù)量差異 在迭代不變體合并算法中,所有未知節(jié)點(diǎn)的定位均采用塊拼接的思想方法,而本文的迭代處理方法只是處理正交投影檢測后可能發(fā)生翻轉(zhuǎn)歧義的那部分節(jié)點(diǎn),對不會發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn)仍采用最小二乘法。由于迭代不變體合并算法利用了塊拼接方法的優(yōu)點(diǎn),即可以充分利用網(wǎng)絡(luò)的信標(biāo)節(jié)點(diǎn)信息,所以該方法可以定位的節(jié)點(diǎn)數(shù)量較大,但定位精度不高。本文基于三角形節(jié)點(diǎn)塊迭代的處理方法是以最小二乘法為基礎(chǔ)的,首先通過正交投影檢測法進(jìn)行翻轉(zhuǎn)歧義節(jié)點(diǎn)的檢測,因此處理的節(jié)點(diǎn)數(shù)由正交投影檢測后可能發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn)數(shù)決定。

2.2.2 算法中節(jié)點(diǎn)塊存在形狀差異 迭代不變體合并算法中的節(jié)點(diǎn)塊具有多種形狀。隨著節(jié)點(diǎn)塊所含節(jié)點(diǎn)數(shù)的增多,節(jié)點(diǎn)塊的形狀有更多的變化,因此定位中就需要考慮節(jié)點(diǎn)塊的更多變化位置。一般情況下,這將會產(chǎn)生更多的節(jié)點(diǎn)塊翻轉(zhuǎn)歧義,增加節(jié)點(diǎn)塊變化的復(fù)雜性。本文所采用的節(jié)點(diǎn)塊只是三角形節(jié)點(diǎn)塊,是選取可能會發(fā)生翻轉(zhuǎn)歧義的未知節(jié)點(diǎn)與其鄰居非信標(biāo)節(jié)點(diǎn)所能構(gòu)成的三角形節(jié)點(diǎn)塊,使得每個三角形節(jié)點(diǎn)塊均由未知節(jié)點(diǎn)所構(gòu)成。此外,迭代不變體合并算法中節(jié)點(diǎn)塊之間可以共享一個或多個節(jié)點(diǎn)(如圖2中節(jié)點(diǎn)P既是Ω1中的節(jié)點(diǎn),又是γ中的節(jié)點(diǎn)),而本文中的三角形節(jié)點(diǎn)塊與由信標(biāo)節(jié)點(diǎn)構(gòu)成的節(jié)點(diǎn)塊之間只是靠測量距離的邊連接(如圖2中三角形節(jié)點(diǎn)塊PSQ和其鄰居信標(biāo)節(jié)點(diǎn)B1,B2,B3,…所構(gòu)成的節(jié)點(diǎn)塊之間是靠彼此間的相互通信進(jìn)行連接的)。

2.2.3 算法的迭代處理步驟差異 迭代不變體合并算法的主要步驟是:首先將網(wǎng)絡(luò)中滿足一定約束條件的2個節(jié)點(diǎn)塊進(jìn)行拼接定位,其他節(jié)點(diǎn)塊再與上述的節(jié)點(diǎn)塊繼續(xù)進(jìn)行塊拼接定位,這樣使得節(jié)點(diǎn)塊的容量(含有節(jié)點(diǎn)的數(shù)量)不斷增加。在整個的定位過程中,迭代不變體合并算法是將成功定位的節(jié)點(diǎn)轉(zhuǎn)化為新的信標(biāo)節(jié)點(diǎn)參與其他節(jié)點(diǎn)塊的拼接過程,而本文方法則是對每個三角形節(jié)點(diǎn)塊(如圖2中的節(jié)點(diǎn)塊PSQ、PUV、PSM和PVN等)都進(jìn)行坐標(biāo)變換的迭代計算,并且可以保證所有的三角形節(jié)點(diǎn)塊的迭代處理過程互不干擾,即每一個三角形節(jié)點(diǎn)塊的迭代處理過程不受上一次三角形節(jié)點(diǎn)塊迭代處理過程的影響。此外,本文中迭代處理方法只利用了網(wǎng)絡(luò)中的信標(biāo)節(jié)點(diǎn)信息,因此不會引入累積誤差。本文方法的缺點(diǎn)是需要更多的參考節(jié)點(diǎn),而且網(wǎng)絡(luò)規(guī)模較大時,計算會比較復(fù)雜。因此,本文方法在網(wǎng)絡(luò)規(guī)模較小時能發(fā)揮更好的作用。

迭代不變體合并算法主要是對整個網(wǎng)絡(luò)中的節(jié)點(diǎn)塊進(jìn)行拼接定位。該算法優(yōu)先對包含信標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)塊進(jìn)行拼接,再對不包含信標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)塊進(jìn)行拼接,并且該算法對節(jié)點(diǎn)塊的拼接順序也有選擇性要求,具體表現(xiàn)為:在整個網(wǎng)絡(luò)節(jié)點(diǎn)塊的拼接過程中,節(jié)點(diǎn)塊根據(jù)節(jié)點(diǎn)塊的約束度(Degree-of-Constraint, DOC)與節(jié)點(diǎn)塊的自由度(Degree-of-Freedom, DOF)差值由大到小的順序進(jìn)行拼接。本文所采用的策略以圖2所示為例加以表述。首先,找出包含所求未知節(jié)點(diǎn)P構(gòu)成的所有三角形節(jié)點(diǎn)塊,如節(jié)點(diǎn)塊PSQ、PUV、PSM和PVN等(本文僅以三角形節(jié)點(diǎn)塊PSQ為例進(jìn)行說明),并且將節(jié)點(diǎn)S、Q的鄰居信標(biāo)節(jié)點(diǎn)用集合Ω3來表示;其次,判斷集合Ω3中的元素與集合Ω1中不同元素的數(shù)量,如果其數(shù)量在1～5之間,那么此三角形節(jié)點(diǎn)塊PSQ就正常參與迭代計算,否則不參與迭代計算;最后,對所有三角形節(jié)點(diǎn)塊均采用上述的處理方法,將滿足條件的三角形節(jié)點(diǎn)塊正常參與迭代計算,這樣就可以保證所選取的三角形節(jié)點(diǎn)塊能夠最大限度地利用更多不同的鄰居信標(biāo)節(jié)點(diǎn)信息來參與定位。

2.3 采用鄰居節(jié)點(diǎn)信息的三角形節(jié)點(diǎn)塊修正

在基于三角形節(jié)點(diǎn)塊處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法中,會出現(xiàn)一些嚴(yán)重影響算法定位精度的三角形節(jié)點(diǎn)塊特例,因此本文提出加入基于正交投影檢測判別模塊和鄰居節(jié)點(diǎn)信息檢測模塊,以去除這些嚴(yán)重影響算法精度的三角形節(jié)點(diǎn)塊,完善基于三角形節(jié)點(diǎn)塊處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法。

圖3～圖6列出了幾種嚴(yán)重影響本文迭代處理方法定位精度的特殊三角形節(jié)點(diǎn)塊PSQ。

圖3 塊中未知節(jié)點(diǎn)的鄰居信標(biāo)節(jié)點(diǎn)與另外2個節(jié)點(diǎn)近似共線

圖4 塊中3個節(jié)點(diǎn)的鄰居信標(biāo)節(jié)點(diǎn)近似共線

圖5 塊中未知節(jié)點(diǎn)沒有足夠鄰居信標(biāo)節(jié)點(diǎn)

圖6 塊中3個節(jié)點(diǎn)近似共線

圖3和圖4是所求未知節(jié)點(diǎn)P具有大于等于3個鄰居信標(biāo)節(jié)點(diǎn)的情況。圖3中所選三角形節(jié)點(diǎn)塊中的其他2個未知節(jié)點(diǎn)Q、S與節(jié)點(diǎn)P的鄰居信標(biāo)節(jié)點(diǎn)近似共線。圖4中所選三角形節(jié)點(diǎn)塊PSQ的所有鄰居信標(biāo)節(jié)點(diǎn)近似共線。

圖5和圖6是未知節(jié)點(diǎn)P沒有足夠鄰居信標(biāo)節(jié)點(diǎn)的情況。經(jīng)分析可知圖5是圖3的一種特例情況,它表示所求未知節(jié)點(diǎn)P沒有足夠鄰居信標(biāo)節(jié)點(diǎn)。圖6中所選三角形節(jié)點(diǎn)塊中的3個頂點(diǎn)近似共線。由于節(jié)點(diǎn)間的測量距離受測距誤差的影響,所以當(dāng)選取的三角形節(jié)點(diǎn)塊PSQ存在如圖3～圖6所示的幾種特殊情況時,本文提出的處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的迭代方法會產(chǎn)生很大的定位誤差,應(yīng)給予排除。因此,利用本文基于三角形節(jié)點(diǎn)塊的迭代處理方法時,需要對所使用的三角形節(jié)點(diǎn)塊加入一定的限制約束條件,其主要修正步驟如下。

(1)利用正交投影檢測法對所選取的三角形節(jié)點(diǎn)塊進(jìn)行判斷。如果存在一條直線與以節(jié)點(diǎn)P、Q、S為圓心,以測距誤差為半徑的誤差圓相交,則這樣的三角形節(jié)點(diǎn)塊將不會參與迭代處理方法。

(2)如果所選三角形節(jié)點(diǎn)塊的3個節(jié)點(diǎn)利用步驟(1)的方法進(jìn)行判斷后不近似共線,那么就采用文中提出的迭代處理方法計算出所選取三角形節(jié)點(diǎn)塊的估計坐標(biāo)。

(3)分別對步驟(2)中所得的若干三角形節(jié)點(diǎn)塊的估計坐標(biāo),按照下面準(zhǔn)則進(jìn)行鄰居節(jié)點(diǎn)信息檢測判斷。以所得未知節(jié)點(diǎn)定位位置坐標(biāo)為圓心,以節(jié)點(diǎn)的通信半徑作圓、判斷該圓內(nèi)是否存在實(shí)際不與該節(jié)點(diǎn)通信的其他節(jié)點(diǎn)。如果存在這樣的節(jié)點(diǎn),那么就對該估計坐標(biāo)予以刪除處理。

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

為了驗(yàn)證本文提出的OPD-IP-INB方法的性能,采用仿真實(shí)驗(yàn)進(jìn)行分析。仿真實(shí)驗(yàn)參數(shù)如表1所示。

表1 網(wǎng)絡(luò)參數(shù)的配置

3.1 信標(biāo)節(jié)點(diǎn)數(shù)對處理翻轉(zhuǎn)歧義效果的影響

不同的信標(biāo)節(jié)點(diǎn)數(shù)決定最小二乘法中節(jié)點(diǎn)發(fā)生翻轉(zhuǎn)歧義的可能性,并直接影響著節(jié)點(diǎn)的定位精度。因此,本文通過模擬仿真來驗(yàn)證各種處理節(jié)點(diǎn)翻轉(zhuǎn)歧義效果與信標(biāo)節(jié)點(diǎn)數(shù)的變化關(guān)系。仿真的測距誤差假設(shè)是一個均值為0、方差為0.15的高斯白噪聲。

下面采用3種定位方法與本文方法進(jìn)行比較,其中:OPD-LS(after using orthogonal projection detection, least squares)表示正交投影檢測后用最小二乘法進(jìn)行定位的方法;OPD-PSO(after using orthogonal projection detection, particle dwarm optimization)表示正交投影檢測后用PSO算法進(jìn)行定位的方法;IIBM(iterative inflexible body merging)表示用迭代不變體合并算法進(jìn)行定位的方法;OPD-IP-TNB為本文定位方法。采用4種方法對不同信標(biāo)節(jié)點(diǎn)數(shù)的仿真結(jié)果如圖7所示。

(a)定位誤差曲線

(b)定位數(shù)曲線圖7 4種算法對不同信標(biāo)節(jié)點(diǎn)數(shù)的仿真結(jié)果

從圖7中可以看出:本文方法在定位誤差和定位節(jié)點(diǎn)數(shù)2個方面均優(yōu)于OPD-PSO方法;盡管在定位節(jié)點(diǎn)數(shù)方面,本文方法不如IIBM方法和OPD-LS方法,但是本文方法可以明顯提高節(jié)點(diǎn)的定位精度,而且在信標(biāo)節(jié)點(diǎn)數(shù)較少時,提高得更明顯。因此,本文方法對于處理最小二乘法中節(jié)點(diǎn)翻轉(zhuǎn)歧義具有明顯的優(yōu)勢。

圖8和圖9分別為最小二乘法(least squares,LS)和本文OPD-IP-TNB方法在處理節(jié)點(diǎn)翻轉(zhuǎn)歧義時所能達(dá)到的節(jié)點(diǎn)定位精度和定位節(jié)點(diǎn)數(shù)。由圖9可以看出,在利用最小二乘法進(jìn)行網(wǎng)絡(luò)中的節(jié)點(diǎn)定位時,確實(shí)存在節(jié)點(diǎn)翻轉(zhuǎn)歧義問題。根據(jù)本文模擬仿真的參數(shù)設(shè)置,并由圖9中可能發(fā)生節(jié)點(diǎn)翻轉(zhuǎn)歧義的數(shù)目柱狀圖可知,在節(jié)點(diǎn)定位中可能發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn)數(shù)大約為10～12。此外,由圖8可以明顯得出結(jié)論,IP-TNB處理方法比LS處理方法效果要好,可以大幅減小定位誤差,提高定位精度,隨著信標(biāo)節(jié)點(diǎn)數(shù)的減小,定位精度可以提高3%～10%。

圖8 本文方法與LS方法處理翻轉(zhuǎn)歧義后的定位誤差

圖9 本文方法與LS方法處理翻轉(zhuǎn)歧義后的節(jié)點(diǎn)數(shù)

3.2 測距誤差對處理翻轉(zhuǎn)歧義效果的影響

無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間的測距誤差直接決定節(jié)點(diǎn)發(fā)生翻轉(zhuǎn)歧義的概率,并最終關(guān)系到整個網(wǎng)絡(luò)的定位精度。所以,文中通過模擬仿真實(shí)驗(yàn)來驗(yàn)證測距誤差對OPD-IP-TNB方法性能的影響。本次仿真中信標(biāo)節(jié)點(diǎn)數(shù)是15。

不同測距誤差的仿真結(jié)果如圖10所示。由圖10可以看出,本文OPD-IP-TNB方法在定位誤差和定位節(jié)點(diǎn)數(shù)2個方面均優(yōu)于OPD-PSO方法,盡管在定位節(jié)點(diǎn)數(shù)方面,本文方法不如IIBM方法和OPD-LS方法,但是本文方法可以明顯提高節(jié)點(diǎn)的定位精度。

(a)定位誤差曲線

(b)定位數(shù)曲線圖10 不同測距誤差下的仿真結(jié)果

本文方法的缺點(diǎn)是其受測距誤差的影響比較敏感,當(dāng)測距誤差較大時,其能夠定位的節(jié)點(diǎn)數(shù)急劇下降,因此本文方法只適用于測距誤差較小的情況。

圖11和圖12分別表示2種方法處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的定位精度和數(shù)量。從圖12的柱狀圖可以明顯看出,隨著測距誤差的增大,網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)生翻轉(zhuǎn)歧義的數(shù)量不斷增加。與最小二乘法相比,雖然文中的迭代方法處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的數(shù)量稍微有減少,但從圖11中可以看出本文的方法可以明顯提高處理節(jié)點(diǎn)翻轉(zhuǎn)歧義的定位精度,隨著測距誤差的減小,定位精度可以提高2%～7%左右,即可以有效地修正翻轉(zhuǎn)歧義節(jié)點(diǎn)。

圖11 不同測距誤差下處理翻轉(zhuǎn)歧義后的定位誤差

圖12 不同測距誤差下處理翻轉(zhuǎn)歧義節(jié)點(diǎn)數(shù)的對比

4 結(jié) 論

本文提出了一種基于三角形節(jié)點(diǎn)塊的迭代方法處理節(jié)點(diǎn)翻轉(zhuǎn)歧義。該方法首先采用正交投影檢測,找出定位中可能發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn),然后采用坐標(biāo)變換逐次尋優(yōu)性的迭代方法對發(fā)生翻轉(zhuǎn)歧義的節(jié)點(diǎn)進(jìn)行處理。仿真分析說明,本文提出的方法可以很好地處理最小二乘法中的節(jié)點(diǎn)翻轉(zhuǎn)歧義問題,提高了節(jié)點(diǎn)的定位精度。然而,本文方法對測距誤差比較敏感,當(dāng)測距誤差比較大時,本文方法雖然也可以處理節(jié)點(diǎn)翻轉(zhuǎn)歧義問題,但要犧牲很大一部分節(jié)點(diǎn)定位數(shù),因此還需要對該方法做進(jìn)一步的研究。

[1]SALMAN N, GHOGHO M, KEMP A H.Optimized low complexity sensor node positioning in wireless sensor networks [J].IEEE Sensors Journal, 2014, 14(1):39-46.

[2]VEMPATY A, OZDEMIR O, AGRAWAL K, et al.Localization in wireless sensor networks:Byzantines and mitigation techniques [J].IEEE Transactions on Signal Processing, 2013, 61(6):1495-1580.

[3]JIANG J A, ZHENG X Y, CHEN Y F, et al.A distributed RSS-based localization using a dynamic circle expanding mechanism [J].IEEE Sensors Journal, 2013, 13(10):3754-3766.

[4]GUO Z W, GUO Y, HONG F, et al.Perpendicular intersection:locating wireless sensors with mobile beacon [J].IEEE Transactions on Vehicular Technology, 2010, 59(7):3501-3509.

[5]董恩清, 鄒宗駿, 張德敬, 等.基于動態(tài)路徑列表的無線傳感器網(wǎng)絡(luò)時間同步協(xié)議 [J].光學(xué)精密工程, 2013, 21(11):2951-2959.DONG Enqing, ZOU Zongjun, ZHANG Dejing, et al.Time synchronization protocol based on dynamic route list for wireless sensor network [J].Optics and Precision Engineering, 2013, 21(11):2951-2959.

[6]CENEDESE A, ORTOLAN G, BERTINATO M.Low-density wireless sensor networks for localization and tracking in critical environments [J].IEEE Transactions on Vehicular Technology, 2010, 59(6):2951-2962.

[7]汪志偉, 曹建福, 鄭輯光.一種面向分簇?zé)o線傳感器網(wǎng)絡(luò)的多信道跨層協(xié)議 [J].西安交通大學(xué)學(xué)報, 2013, 47(6):61-67.WANG Zhiwei, CAO Jiaufu, ZHENG Jiguang.Multi-channel multi-path cross-layer protocol for clustered wireless sensor networks [J].Journal of Xi’an Jiaotong University, 2013, 47(6):61-67.

[8]LIU W, DONG E Q, SONG Y, et al.An improved flip ambiguity detection algorithm in wireless sensor networks node localization [C] ∥Proceedings of 2014 International Conference on Telecommunications.Piscataway, NJ, USA:IEEE, 2014:206-212.

[9]WANG X P, LIU Y H, YANG Z, et al.OFA:an optimistic approach to conquer flip ambiguity in network localization [J].Computer Networks, 2013, 57(6):1529-1544.

[10]BU K, XIAO Q J, SUN Z X, et al.Toward collinearity-aware and conflict-friendly localization for wireless sensor networks [J].Computer Communications, 2012, 35(13):1549-1560.

[11]XIAO Q J, XIAO B, BU K, et al.Iterative localization of wireless sensor networks:an accurate and robust approach [J].IEEE/ACM Transactions on Networking, 2014, 22(2):608-621.

(編輯 劉楊)

An Iterative Method for Using Triangular Node Blocks to Process Node Flip Ambiguity of Node Localization in Wireless Sensor Networks

DONG Enqing,LIU Wei,SONG Yang

(School of Mechanical, Electrical & Information Engineering, Shandong University, Weihai, Shandong 264209, China)

An iterative method based on triangular node blocks (OPD-IP-TNB) is proposed to solve the problem of the node flip ambiguity generated in using least squares method to locate nodes in wireless sensor networks.First, the orthogonal projection detection method is adopted to detect unknown nodes to be positioned.Then the iterative method based on coordinate transformation and recursive optimization is applied to process the flip ambiguity nodes by using the stability of triangle node blocks and the whole network connectivity information.Simulation results show that the proposed method can effectively deal with the node flip ambiguity in using the least squares method, and improve localization accuracy of the whole network.Comparison with the least squares method shows that the localization accuracy improves by 3%-10% when the number of anchor nodes decreases, and by 2%-7% when the range errors decreases.

wireless sensor networks; node localization; flip ambiguity; orthogonal projection

2014-08-29。 作者簡介:董恩清(1965—),男,教授,博士生導(dǎo)師。 基金項目:國家自然科學(xué)基金資助項目(81371635);教育部高等學(xué)校博士學(xué)科點(diǎn)專項科研基金資助項目(20120131110062);山東省科技發(fā)展計劃資助項目(2013GGX 10104)。

時間:2015-01-16

http:∥www.cnki.net/kcms/detail/61.1069.T.20150116.1510.001.html

10.7652/xjtuxb201504014

TP212;TN92

A

0253-987X(2015)04-0084-07