一種基于凸優(yōu)化的WSN障礙環(huán)境下定位算法

程 超, 李 萌, 王久赫, 陳碧龍

(長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院, 長春 130012)

無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)以其設(shè)置的靈活性、 大規(guī)模、 無中心自組織、 動態(tài)性、 以數(shù)據(jù)為中心等特點廣泛應(yīng)用于許多領(lǐng)域, 形成了新的信息傳遞、 處理、 應(yīng)用模式, 實現(xiàn)了物聯(lián)網(wǎng)技術(shù)與真實物理世界的結(jié)合. 由于傳感器節(jié)點常分布在不便于數(shù)據(jù)收集與傳輸?shù)膹?fù)雜環(huán)境或目標(biāo)位置不斷移動的區(qū)域, 需要通過協(xié)作方式收集、 傳遞及處理網(wǎng)絡(luò)通信范圍內(nèi)目標(biāo)的數(shù)據(jù)信息, 因此在無線傳感器網(wǎng)絡(luò)中的節(jié)點位置信息成為不可缺少的重要內(nèi)容. 如何使節(jié)點的位置計算更接近實際已成為目前無線傳感器網(wǎng)絡(luò)定位研究的熱點.

目前, 定位算法主要有兩種： 基于測距的定位算法和無需測距定位算法. 基于測距的定位算法主要包括基于到達(dá)角度(angle of arrival, AOA)[1]的定位算法、 基于到達(dá)時間(time of arrival, TOA)[2]的定位算法、 基于到達(dá)時間差(time difference of arrival, TDOA)[3]的定位算法以及基于信號接收強(qiáng)度指示(received signal strength indicator, RSSI)[4]的定位算法. 無需測距的定位算法主要包括質(zhì)心算法[5]、 APIT(approximate point-in-triangulation test)算法[6-7]以及DV-hop(distance vector-hop)算法[8-9]等. 兩類算法相比, 綜合能耗、 成本、 便捷性等多方面因素考慮, 無需測距定位即可滿足人們需求的DV-hop算法應(yīng)用較廣泛.

傳統(tǒng)的DV-hop算法存在未知節(jié)點定位與實際位置偏差較大的問題, 這是由于節(jié)點隨機(jī)分布或定位環(huán)境復(fù)雜而使計算方法存在誤差所致. 針對DV-hop算法的不足, 文獻(xiàn)[10-12]提出了相應(yīng)的改進(jìn)算法. 文獻(xiàn)[10]利用最小均方差原理, 通過修改指數(shù)值改進(jìn)平均跳距, 提出了最佳指數(shù)值概念, 從而進(jìn)一步提高了定位精度; 文獻(xiàn)[11]提出了一種基于RSSI 測距技術(shù)的平均跳距計算方法, 對超過通信半徑外的節(jié)點平均跳距利用錨節(jié)點間距離的誤差值修正; 文獻(xiàn)[12]也對平均跳距進(jìn)行改進(jìn), 通過對節(jié)點通信半徑的研究, 對節(jié)點信息傳播的跳數(shù)進(jìn)行修改, 達(dá)到提高定位精度的目的. 雖然這些改進(jìn)方法在一定程度上提高了定位精度并減少了定位誤差, 但仍存在一些不足. 如沒有提到在定位環(huán)境中存在障礙物導(dǎo)致傳播的跳數(shù)與實際不符的問題. 因此, 如何減小因定位環(huán)境中存在障礙物導(dǎo)致跳數(shù)對計算產(chǎn)生的影響, 進(jìn)一步提高定位精度是本文改進(jìn)算法的目標(biāo).

1 DV-hop定位算法

1.1 算法描述

傳統(tǒng)的DV-hop算法作為一種典型的與距離無關(guān)的定位算法, 其主要內(nèi)容可概述為： 首先, 網(wǎng)絡(luò)中的每個節(jié)點以洪范的方式通過距離矢量路由獲得錨節(jié)點的最小跳數(shù)及每個錨節(jié)點的坐標(biāo)數(shù)據(jù)信息. 其次, 計算錨節(jié)點的平均跳距并將其廣播到網(wǎng)絡(luò). 將未知節(jié)點接收錨節(jié)點的平均跳距作為其平均跳距, 未知節(jié)點和錨節(jié)點之間的跳距d通過將平均跳距和跳數(shù)相乘估計, 計算公式為

其中: (xi,yi),(xj,yj)為錨節(jié)點i,j的坐標(biāo); Hopsizei為錨節(jié)點的平均跳距;hij為錨節(jié)點i與j之間的跳數(shù)(i≠j);h為錨節(jié)點與未知節(jié)點之間的跳數(shù);d為未知節(jié)點與錨節(jié)點之間的估計距離. 最后, 基于錨節(jié)點的位置坐標(biāo)信息及至少3個錨節(jié)點到未知節(jié)點的距離值, 使用三邊測量方法或最大似然估計方法計算未知節(jié)點坐標(biāo). 如對未知節(jié)點坐標(biāo)使用三邊測量方法： 設(shè)未知節(jié)點的坐標(biāo)為(x,y), 錨節(jié)點的坐標(biāo)為A(xa,ya),B(xb,yb),C(xc,yc), 未知節(jié)點距離3個錨節(jié)點的跳段距離分別為da,db,dc, 則

(3)

未知節(jié)點的坐標(biāo)為

(4)

1.2 算法分析

傳統(tǒng)DV-hop定位算法存在許多不足, 在實際應(yīng)用中受多種環(huán)境因素影響. 例如： 由于節(jié)點分布的隨機(jī)性, 算法的定位效果受網(wǎng)絡(luò)連通度影響； 錨節(jié)點的平均跳距作為網(wǎng)絡(luò)全局節(jié)點的平均每跳跳距, 使得計算存在誤差； 算法將未知節(jié)點與錨節(jié)點之間的跳段路徑長度作為它們之間的距離, 但事實上, 未知節(jié)點與錨節(jié)點的跳段路徑是直線的概率很低, 導(dǎo)致計算存在誤差, 以致于最終定位結(jié)果不準(zhǔn)確. 因此如何減小定位方法的誤差, 提高定位結(jié)果的精度, 使WSN定位算法在實踐中更好地運(yùn)用, 是本文改進(jìn)定位算法研究的重點.

2 改進(jìn)算法

傳統(tǒng)DV-hop算法的計算是在較理想條件下進(jìn)行的, 但實際中由于節(jié)點隨機(jī)分布, 且傳播過程中可能因存在物體阻礙使兩節(jié)點的信息不能直線傳播等原因, 導(dǎo)致計算結(jié)果與實際不符, 使得對目標(biāo)定位產(chǎn)生較大偏差. 如圖1所示,A,B,D是錨節(jié)點, 其中d是A和B之間的實際距離, 因為A和B之間信息傳播理論上只需要兩跳, 但由于存在障礙物, 實際上A需要3跳才能把信息傳播到B, 因此如果按照傳統(tǒng)的算法計算就會產(chǎn)生誤差. 傳統(tǒng)的DV-hop算法在應(yīng)對類似較復(fù)雜環(huán)境下進(jìn)行定位的情況并不適用, 如果在定位計算中直接用傳統(tǒng)方法計算節(jié)點位置, 會導(dǎo)致較大的誤差. 針對上述問題, 本文改進(jìn)算法引入了一個誤差修正值p：

其中：d是錨節(jié)點間的真實距離;R是節(jié)點的通信半徑;hAB和HAB分別是錨節(jié)點A和B間的實際跳數(shù)和理論最小跳數(shù). 理論最小跳數(shù)是在直線傳播且平均跳距是通信半徑R時的跳數(shù).p反映了實際傳播跳數(shù)偏離理論直線傳播最小跳數(shù)的誤差程度, 超過該誤差范圍時, 在計算平均跳距時就會產(chǎn)生較大誤差, 由于誤差的逐步積累, 導(dǎo)致在計算未知節(jié)點位置時產(chǎn)生較大偏離. 由文獻(xiàn)[13]知, 當(dāng)p=0.3時, 錨節(jié)點i的平均跳距為

(7)

錨節(jié)點i與j之間的估算距離為

×hij,

(8)

錨節(jié)點i與j之間的直線即實際距離為

(9)

當(dāng)網(wǎng)絡(luò)中存在N個錨節(jié)點時, 計算錨節(jié)點i的平均跳距誤差εi為

(10)

-eη×εi,

(11)

其中η<0為參數(shù)變量, 具體取值隨網(wǎng)絡(luò)環(huán)境變化而不同, 本文取η=-0.5[14]. 錨節(jié)點將Ci向整個網(wǎng)絡(luò)廣播, 從而未知節(jié)點S到錨節(jié)點i之間的跳段距離可表示為

diS=Ci×hiS.

(12)

為了獲得圖1中未知節(jié)點C的坐標(biāo), 本文改進(jìn)算法在考慮了錨節(jié)點的信息傳播受物體阻礙的情況下, 對節(jié)點的平均跳距進(jìn)行優(yōu)化改進(jìn)計算. 并且在求解未知節(jié)點到錨節(jié)點之間的距離時, 因為節(jié)點B,C,D不共線,dBC,dBD,dCD三邊將構(gòu)成三角形, 所以可根據(jù)三角函數(shù)原理求得dCD. 近似用三邊的跳數(shù)比表示三邊的關(guān)系, 得出如下關(guān)系式:

(13)

其中:α表示BC與BD兩條邊的夾角;H1表示節(jié)點B,C之間的跳數(shù);H2表示節(jié)點B,D之間的跳數(shù);H3表示節(jié)點C,D之間的跳數(shù);dBD表示錨節(jié)點B,D之間的距離;H1,H2,H3均為可確定的數(shù)值. 又因為未知節(jié)點C到最近的錨節(jié)點B之間的跳段距離dBC可通過式(12)求得, 所以計算可得

因此, 本文改進(jìn)定位算法在考慮到節(jié)點間數(shù)據(jù)信息傳播受阻礙的情況下, 先改進(jìn)節(jié)點B,C之間的距離計算方法, 再結(jié)合錨節(jié)點B,D間的準(zhǔn)確距離, 共同計算未知節(jié)點C到錨節(jié)點D之間的距離. 同理, 可求得其他未知節(jié)點到最近錨節(jié)點的距離, 進(jìn)而最終求得未知節(jié)點的坐標(biāo). 本文算法結(jié)合實際, 考慮了當(dāng)無線信號傳播被阻擋時如何減小其對計算造成的誤差, 以及進(jìn)一步對求未知節(jié)點到錨節(jié)點跳段距離時, 兩錨節(jié)點間的準(zhǔn)確距離對其的校正. 為了更好地定位未知節(jié)點位置, 可對計算出的未知節(jié)點坐標(biāo)進(jìn)行優(yōu)化處理. 本文對改進(jìn)算法中的未知節(jié)點坐標(biāo)進(jìn)行凸優(yōu)化處理, 優(yōu)化信息傳播過程, 使未知節(jié)點的坐標(biāo)更接近實際位置.

3 對未知節(jié)點優(yōu)化

3.1 凸優(yōu)化

凸優(yōu)化是指目標(biāo)函數(shù)為凸函數(shù), 且變量所屬集合屬于凸集的優(yōu)化問題. 連接屬于集合中的任意兩點, 得到兩點間的直線段, 若直線段上的所有點全部位于該集合內(nèi), 則稱該集合為凸集. 即設(shè)集合D?n, 若對于任意兩點x,y∈D以及實數(shù)α(0≤α≤1), 都有

αx+(1-α)y∈D,

則稱集合D為凸集. 設(shè)集合S?n為凸集, 若滿足

f((1-α)x+αy)≤(1-α)f(x)+αf(y),

(16)

則稱函數(shù)f(x)是凸集S上的凸函數(shù). 因此, 若滿足：

且f(x)為定義在D(D為凸集)上的凸函數(shù), 則該優(yōu)化問題即為凸優(yōu)化.

3.2 無需測距的分布式(ESOCP)優(yōu)化

假設(shè)WSN網(wǎng)絡(luò)中共N個節(jié)點, 有m個錨節(jié)點和(N-m)個未知節(jié)點, 且m

超出通信半徑, 需一個中繼節(jié)點才可通信的節(jié)點即為兩跳鄰居節(jié)點. 對于兩跳節(jié)點i和j, 它們之間的距離滿足

R<‖xi-xj‖≤2R.

相應(yīng)地, 這些節(jié)點組成的集合用N2表示. 因此, 對于未知節(jié)點定位的凸優(yōu)化問題, 可用公式表示為

其中S是N1和N2的集合, 若S=N1, 則0≤tij≤R2; 若S=N2, 則R2≤tij≤4R2.

根據(jù)WSN定位情況, 上述問題可轉(zhuǎn)化為

(20)

設(shè)k表示優(yōu)化過程中迭代的次數(shù), 則以分布式的方式利用順序貪婪優(yōu)化算法解得：

4 仿真結(jié)果與分析

將100個節(jié)點隨機(jī)部署在(100×100)m2的正方形感知區(qū)域內(nèi)構(gòu)成實驗環(huán)境, 采用MATLAB2012a軟件對傳統(tǒng)DV-hop算法、 文獻(xiàn)[15]算法及本文改進(jìn)算法進(jìn)行仿真實驗, 驗證算法的定位效果. 實驗測試由通信半徑和錨節(jié)點作為變量對不同算法定位精度的影響, 并對導(dǎo)致實驗結(jié)果的原因進(jìn)行分析. 為了降低隨機(jī)產(chǎn)生的誤差, 取得更準(zhǔn)確的實驗數(shù)據(jù), 在同等參數(shù)條件下進(jìn)行100次仿真, 取其均值作為實驗結(jié)果.

(25)

歸一化平均定位誤差為

(26)

圖2 錨節(jié)點數(shù)對定位誤差的影響Fig.2 Effects of number of anchor nodes on positioning error

圖2為在相同實驗環(huán)境下, 通信半徑不變而錨節(jié)點增加時, 傳統(tǒng)DV-hop算法、 文獻(xiàn)[15]算法及本文改進(jìn)算法的仿真結(jié)果. 由圖2可見, 當(dāng)節(jié)點通信半徑不變時, 3種定位算法的平均定位誤差均隨錨節(jié)點增多而降低, 且相互之間的差距越來越大, 這是由于WSN網(wǎng)絡(luò)中錨節(jié)點的增多不僅直接影響算法的定位精度, 且信息傳遞路徑可通過錨節(jié)點而使得其趨于直線的概率增大, 減少了數(shù)據(jù)傳播過程中還需計算跳段距離導(dǎo)致的誤差. 本文改進(jìn)算法相比于傳統(tǒng)DV-hop算法和文獻(xiàn)[15]算法, 總體上實現(xiàn)了在不增加額外支出的條件下, 達(dá)到提高定位精度的目的.

在相同條件下, 節(jié)點通信半徑和錨節(jié)點個數(shù)逐漸增大時, 傳統(tǒng)DV-hop算法、 文獻(xiàn)[15]算法及本文改進(jìn)算法的仿真結(jié)果如圖3所示. 由圖3可見, 傳統(tǒng)DV-hop算法和文獻(xiàn)[15]算法與本文改進(jìn)算法在相同錨節(jié)點個數(shù)下, 定位誤差之間的差距隨通信半徑的增大而增大. 表明除錨節(jié)點個數(shù)外, 通信半徑也能決定算法的定位效果. 這是因為隨著通信半徑的增大, 未知節(jié)點到錨節(jié)點的跳數(shù)減少, 數(shù)據(jù)信息從一個節(jié)點傳播到下一個節(jié)點時可選擇的范圍變大, 能選出更合理的路由, 優(yōu)化信息傳播過程. 本文改進(jìn)算法比傳統(tǒng)DV-hop算法與文獻(xiàn)[15]算法定位誤差小很多. 當(dāng)R=10 m時, 減少約20%和9%； 當(dāng)R=20 m時, 減少約24%和11%； 當(dāng)R=30 m時, 減少約30%和13%. 仿真結(jié)果表明本文改進(jìn)算法定位性能最優(yōu).

圖3 節(jié)點通信半徑對算法誤差的影響Fig.3 Effects of node communication radii on algorithmic error

綜上所述, 針對傳統(tǒng)DV-hop算法在實際應(yīng)用中存在受環(huán)境影響使得定位結(jié)果偏差較大的問題, 本文提出了一種改進(jìn)算法. 該算法首先考慮了在定位測試環(huán)境中存在障礙物的情況下對節(jié)點信息傳播的影響, 進(jìn)而改進(jìn)了錨節(jié)點的平均跳距計算, 使其更適于距離的計算； 然后在此基礎(chǔ)上結(jié)合三角函數(shù)進(jìn)一步優(yōu)化未知節(jié)點與錨節(jié)點距離的計算, 使最終的定位更接近真實位置； 最后對未知節(jié)點位置進(jìn)行凸優(yōu)化, 優(yōu)化信息傳播過程, 減小不合理傳播導(dǎo)致的誤差, 提高定位性能. MATLAB仿真結(jié)果表明, 本文改進(jìn)算法比傳統(tǒng)DV-hop算法具有更好的定位性能, 實現(xiàn)了提高WSN網(wǎng)絡(luò)定位精度的目標(biāo).