無線傳感器網(wǎng)絡(luò)的錨節(jié)點(diǎn)優(yōu)化布設(shè)算法

, ,,

(1.解放軍理工大學(xué) 指揮信息系統(tǒng)學(xué)院,南京 210007; 2.94860部隊(duì),南京 210018; 3.94789部隊(duì),南京 210018)

0 概述

在無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)應(yīng)用中,針對(duì)微型傳感器節(jié)點(diǎn)監(jiān)測(cè)、感知和采集的各種環(huán)境或?qū)ο笮畔?只有與特定的節(jié)點(diǎn)位置相結(jié)合才能為相關(guān)應(yīng)用提供有效的決策支持。無線傳感器網(wǎng)絡(luò)在戰(zhàn)場(chǎng)偵查[1]、環(huán)境生態(tài)監(jiān)測(cè)[2-3]、人員跟蹤定位[4]等方面應(yīng)用廣泛。除了錨節(jié)點(diǎn)通過配備GPS接收機(jī)或人工手動(dòng)配置等方法獲得自身位置外,剩余的大量節(jié)點(diǎn)通過測(cè)量與錨節(jié)點(diǎn)的距離信息,并使用某些定位算法來間接獲得自身的位置。由于靜態(tài)錨節(jié)點(diǎn)一經(jīng)布設(shè)其位置便不再移動(dòng),且所有節(jié)點(diǎn)的位置解算都要以錨節(jié)點(diǎn)的位置為參考,因此,錨節(jié)點(diǎn)的位置對(duì)節(jié)點(diǎn)的定位效果具有直接影響,進(jìn)而影響網(wǎng)絡(luò)的應(yīng)用性能,例如提高監(jiān)測(cè)區(qū)域的覆蓋率[5]、降低網(wǎng)絡(luò)壽命[6]等。

本文研究單跳定位的場(chǎng)景,從理論分析入手,研究分析錨節(jié)點(diǎn)幾何形狀對(duì)定位精度的影響,以到達(dá)時(shí)間(Time of Arrival,TOA)測(cè)距為例,給出幾何精度因子(Geometric Dilution of Precision,GDOP)[7]的計(jì)算公式,揭示同一種定位算法下,當(dāng)測(cè)距誤差相同時(shí),節(jié)點(diǎn)定位精度不同的本質(zhì)原因。本文提出區(qū)域定位的概念,并給出區(qū)域定位精度的評(píng)價(jià)指標(biāo),即區(qū)域定位誤差均界。通過仿真分析研究錨節(jié)點(diǎn)布設(shè)因素(錨節(jié)點(diǎn)質(zhì)心、幾何形狀、幾何面積)對(duì)區(qū)域定位精度的影響,據(jù)此設(shè)計(jì)錨節(jié)點(diǎn)優(yōu)化布設(shè)的啟發(fā)式(Heuristic Optimization Anchor node Deployment,HOAD)算法。

1 相關(guān)工作

關(guān)于錨節(jié)點(diǎn)布設(shè)的工作較多。文獻(xiàn)[8]提出了以每個(gè)節(jié)點(diǎn)至少被3個(gè)錨節(jié)點(diǎn)覆蓋為約束,在一個(gè)規(guī)則網(wǎng)絡(luò)中計(jì)算定位所需的最少錨節(jié)點(diǎn)數(shù)目。文獻(xiàn)[9-10]給定一些已布設(shè)的錨節(jié)點(diǎn),并在此基礎(chǔ)上利用人或移動(dòng)的機(jī)器人增加額外的錨節(jié)點(diǎn),以擴(kuò)大錨節(jié)點(diǎn)的覆蓋區(qū)域。這些工作主要著眼于確保節(jié)點(diǎn)的可定位,未考慮錨節(jié)點(diǎn)布設(shè)的幾何形狀對(duì)定位精度的影響。相關(guān)定位算法的研究大多著眼于給定錨節(jié)點(diǎn)的數(shù)量和在網(wǎng)絡(luò)中的布設(shè)位置后,如何盡可能地提高算法的定位精度[11]。然而從定位系統(tǒng)架構(gòu)的角度上看,當(dāng)錨節(jié)點(diǎn)布設(shè)不佳時(shí),例如錨節(jié)點(diǎn)與待定位節(jié)點(diǎn)構(gòu)成的幾何形狀較差時(shí),無論采用何種定位算法,節(jié)點(diǎn)定位精度的提高都將受限。

目前從提高定位精度角度優(yōu)化錨節(jié)點(diǎn)的布設(shè)大多基于搜索方法[12-14]。給定待布設(shè)的錨節(jié)點(diǎn)個(gè)數(shù)M,先設(shè)定優(yōu)化目標(biāo)函數(shù),再將待定位區(qū)域進(jìn)行離散劃分,將離散點(diǎn)作為錨節(jié)點(diǎn)的候選位置,從中任選M個(gè)進(jìn)行窮盡組合,計(jì)算每種組合下的目標(biāo)函數(shù)值,將最小值對(duì)應(yīng)的位置組合作為錨節(jié)點(diǎn)的最終位置。這類基于搜索的方法雖能確保定位精度,但計(jì)算復(fù)雜度非常高,在錨節(jié)點(diǎn)個(gè)數(shù)多、網(wǎng)絡(luò)布設(shè)區(qū)域大、形狀復(fù)雜時(shí),難以實(shí)現(xiàn)準(zhǔn)確的定位。因而有必要提出一種復(fù)雜度低、易于實(shí)現(xiàn)的啟發(fā)式錨節(jié)點(diǎn)優(yōu)化布設(shè)策略,在給定待布設(shè)的錨節(jié)點(diǎn)個(gè)數(shù)和區(qū)域形狀的情況下,從區(qū)域中選擇錨節(jié)點(diǎn)的優(yōu)化位置,在確保待定位節(jié)點(diǎn)定位精度的前提下降低計(jì)算復(fù)雜度。

2 錨節(jié)點(diǎn)對(duì)定位精度的影響

2.1 定位誤差界和幾何精度因子

定位誤差的克拉美羅下界(Cramer-Rao Lower Bound,CRLB)[15]是節(jié)點(diǎn)位置無偏估計(jì)的誤差協(xié)方差下界,通常用于衡量定位算法所能達(dá)到的性能。GDOP表征了當(dāng)存在測(cè)量誤差時(shí),錨節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的幾何排列Ψ對(duì)定位誤差的影響。本文基于TOA測(cè)距進(jìn)行定位問題的描述和定位誤差界及GDOP的推導(dǎo)。

圖1 二維中的定位情形

由于在測(cè)量中受環(huán)境噪聲、時(shí)鐘同步誤差等因素的影響,錨節(jié)點(diǎn)i與目標(biāo)節(jié)點(diǎn)之間的信號(hào)TOA測(cè)量值τi含有誤差,表示為:

其中,v表示信號(hào)傳播速度,ni表示信號(hào)的TOA測(cè)量誤差。

假設(shè)TOA的測(cè)量誤差n服從均值為零的高斯分布,并且n的協(xié)方差矩陣C滿秩,那么TOA的測(cè)量值τ的概率密度函數(shù)(Probability Density Function,PDF)可以表示為[16]:

(2)

據(jù)此可以求出對(duì)應(yīng)的費(fèi)希爾信息矩陣J:

J=E{[lnf(τ;p)][lnf(τ;p)]T}

(3)

其中,▽表示對(duì)p求梯度,E(·)表示對(duì)τ求期望。

根據(jù)定義及式(2)、式(3),單目標(biāo)節(jié)點(diǎn)的定位誤差CRLB可以表示為:

其中:

gi是單位長(zhǎng)度矢量,‖gi‖=1,方向從錨節(jié)點(diǎn)qi指向目標(biāo)節(jié)點(diǎn)p,G是D×M矩陣,由目標(biāo)節(jié)點(diǎn)和錨節(jié)點(diǎn)的幾何位置決定,tr(·)表示求跡運(yùn)算。

將式(4)開根號(hào)可得到定位誤差的CRLB:

GDOP概念來自衛(wèi)星幾何學(xué)[17],定義為:

σGDOP=σp/σm

(7)

其中,σp和σm分別表示位置估計(jì)和距離測(cè)量的均方根(Root Mean Square,RMS)誤差。當(dāng)TOA的測(cè)量誤差n服從均值為零、方差為σ2的高斯獨(dú)立同分布時(shí),σm=vσ,且n的協(xié)方差矩陣C具有如下形式:

C=σ2IM×M

(8)

其中,σ2表示高斯分布的方差,I表示單位方陣。

對(duì)于無偏估計(jì)的定位算法而言,σp可以用定位誤差下界σCRLB來近似表示[16,18]:

將σm=vσ和式(8)、式(9)代入式(7)可得到GDOP的表達(dá)式:

對(duì)式(7)進(jìn)行變形得到式(11):

由式(10)可知,GDOP僅由矩陣G決定,G由幾何排列Ψ決定。從式(11)可以更直觀地看出定位誤差與幾何精度因子的關(guān)系:GDOP表征了當(dāng)存在測(cè)距誤差σm時(shí),在定位誤差σp中幾何排列Ψ對(duì)σm的放大作用。

2.2 區(qū)域定位問題和搜索布設(shè)算法

第2.1節(jié)研究了錨節(jié)點(diǎn)和單個(gè)目標(biāo)節(jié)點(diǎn)構(gòu)成的幾何形狀對(duì)定位精度的影響,下面研究區(qū)域定位問題,即多個(gè)目標(biāo)節(jié)點(diǎn)在凸區(qū)域A內(nèi)隨機(jī)均勻布設(shè)時(shí),錨節(jié)點(diǎn)對(duì)多個(gè)目標(biāo)節(jié)點(diǎn)平均定位精度的影響。給定錨節(jié)點(diǎn)的個(gè)數(shù)M,從區(qū)域A內(nèi)選出M個(gè)錨節(jié)點(diǎn)的位置qi,i=1,2,…,M,使得隨機(jī)布設(shè)的目標(biāo)節(jié)點(diǎn)在A內(nèi)的平均定位精度最高。

從第2.1節(jié)可知單個(gè)目標(biāo)節(jié)點(diǎn)的定位精度可用定位誤差CRLB表示。對(duì)于區(qū)域定位問題,A內(nèi)隨機(jī)布設(shè)的每個(gè)目標(biāo)節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)幾何排列和CRLB,因此,平均定位精度可用CRLB均值來表示,稱該均值為區(qū)域定位誤差均界。

當(dāng)錨節(jié)點(diǎn)位置qi改變時(shí),對(duì)于目標(biāo)節(jié)點(diǎn)(x,y)而言,CRLB(x,y)會(huì)發(fā)生變化,對(duì)應(yīng)的目標(biāo)函數(shù)F值亦發(fā)生變化。為了在區(qū)域內(nèi)尋找錨節(jié)點(diǎn)的最優(yōu)布設(shè)位置,使目標(biāo)函數(shù)F值最小,最直觀的方法是搜索法,將區(qū)域A離散化,將其均勻劃分為N個(gè)小格,小格的端點(diǎn)代表錨節(jié)點(diǎn)的位置候選點(diǎn),從中任選M個(gè)位置組合Bt作為錨節(jié)點(diǎn)的坐標(biāo),然后計(jì)算在該組合Bt下,N個(gè)點(diǎn)的平均CRLB值,作為區(qū)域定位誤差均界,從而將式(12)的積分轉(zhuǎn)化為式(13)的求和:

算法1錨節(jié)點(diǎn)搜索布設(shè)算法

Bopt= null; %最優(yōu)的錨節(jié)點(diǎn)位置組合

Fopt= inf; %最優(yōu)的目標(biāo)函數(shù)值為無窮大

用式(13)計(jì)算區(qū)域內(nèi)N個(gè)點(diǎn)的平均CRLB值Ft;

If Ft< Fopt

Bopt= Bt;

Fopt= Ft;

End

End

3 啟發(fā)式優(yōu)化布設(shè)算法

鑒于錨節(jié)點(diǎn)搜索布設(shè)算法的計(jì)算復(fù)雜度較高,有必要提出啟發(fā)式的布設(shè)方式。對(duì)錨節(jié)點(diǎn)布設(shè)的構(gòu)成因素,例如錨節(jié)點(diǎn)質(zhì)心、錨節(jié)點(diǎn)幾何形狀、錨節(jié)點(diǎn)幾何面積等進(jìn)行仿真分析,給出定性結(jié)論,并在此基礎(chǔ)上提出錨節(jié)點(diǎn)的啟發(fā)式優(yōu)化布設(shè)算法。

3.1 仿真分析

以3個(gè)錨節(jié)點(diǎn)為例,在100 m×100 m的正方形區(qū)域內(nèi)進(jìn)行布設(shè),假設(shè)測(cè)距誤差σ=1 m,探討錨節(jié)點(diǎn)質(zhì)心的位置、錨節(jié)點(diǎn)的面積、錨節(jié)點(diǎn)的幾何形狀3個(gè)因素對(duì)區(qū)域定位誤差均界的影響。

3.1.1 質(zhì)心因素

仿真配置為:由錨節(jié)點(diǎn)構(gòu)成正三角形,極徑20 m,保持幾何形狀和角度不變,僅改變錨節(jié)點(diǎn)在區(qū)域內(nèi)的質(zhì)心。錨節(jié)點(diǎn)和質(zhì)心的移動(dòng)示意圖如圖2所示。

圖2 錨節(jié)點(diǎn)和質(zhì)心的移動(dòng)

將正方形區(qū)域離散化,使其劃分為5 m×5 m的小格,每個(gè)小格的端點(diǎn)作為待定位點(diǎn)的位置,然后利用式(13)計(jì)算錨節(jié)點(diǎn)、質(zhì)心位于不同位置處的區(qū)域定位誤差均界,仿真結(jié)果如圖3所示。

圖3 錨節(jié)點(diǎn)質(zhì)心對(duì)定位誤差的影響

從圖3可知,錨節(jié)點(diǎn)幾何質(zhì)心從區(qū)域中心向區(qū)域邊緣移動(dòng)的過程中,定位誤差均界呈單調(diào)增加的趨勢(shì),當(dāng)錨節(jié)點(diǎn)幾何質(zhì)心與區(qū)域中心(0,0)重合時(shí),區(qū)域定位誤差均界達(dá)到最小值。因此,為了降低區(qū)域定位誤差, 錨節(jié)點(diǎn)的幾何中心要盡量與區(qū)域中心重合。

3.1.2 幾何形狀因素

仿真配置為:錨節(jié)點(diǎn)位于以區(qū)域中心為原點(diǎn)的圓周上,圓半徑20 m,其中一個(gè)錨節(jié)點(diǎn)位于x軸正方向上,坐標(biāo)為(20,0)不變,第2個(gè)錨節(jié)點(diǎn)保持極角為120°不變,改變第3個(gè)錨節(jié)點(diǎn)對(duì)應(yīng)的極角θ,在[150°,330°]范圍內(nèi)每隔30°變化一次θ。錨節(jié)點(diǎn)的幾何形狀如圖4所示。

圖4 錨節(jié)點(diǎn)的幾何形狀

將正方形區(qū)域離散化,使其劃分為5 m×5 m的小格,每個(gè)小格的端點(diǎn)作為待定位點(diǎn)的位置,然后利用式(13)計(jì)算第3個(gè)錨節(jié)點(diǎn)對(duì)應(yīng)的極角θ在[150°,330°]范圍內(nèi)每隔30°變化一次時(shí)的區(qū)域定位誤差均界。幾何形狀對(duì)定位誤差的影響結(jié)果如圖5所示。其中,x軸表示第3個(gè)錨節(jié)點(diǎn)的極角θ,對(duì)應(yīng)三角形的幾何形狀,y軸表示區(qū)域定位誤差均界。

圖5 幾何形狀對(duì)定位誤差的影響

從圖5可知,當(dāng)錨節(jié)點(diǎn)間的夾角(120°,θ-120°,360°-θ)越接近時(shí),區(qū)域定位誤差越小。當(dāng)θ=240°時(shí),區(qū)域定位誤差均界達(dá)到最小值,此時(shí)錨節(jié)點(diǎn)呈均勻等角布設(shè)。因此,為了降低區(qū)域定位誤差, 錨節(jié)點(diǎn)間的夾角要盡量接近;在同等條件下,當(dāng)夾角相等時(shí),區(qū)域定位誤差均界最小。

3.1.3 幾何面積因素

仿真配置為:由錨節(jié)點(diǎn)構(gòu)成正三角形,質(zhì)心與正方形的中心重合,逐步增大三角形對(duì)應(yīng)的半徑r。錨節(jié)點(diǎn)幾何面積變化示意圖如圖6所示,通過改變?nèi)切蔚膸缀蚊娣e,將正方形區(qū)域離散化,使其劃分為5 m×5 m的小格,每個(gè)小格的端點(diǎn)作為待定位節(jié)點(diǎn)的位置,然后利用式(13)計(jì)算錨節(jié)點(diǎn)半徑r取不同值時(shí)對(duì)應(yīng)的區(qū)域定位誤差均界。仿真結(jié)果如圖7所示。

圖6 錨節(jié)點(diǎn)幾何面積的變化

圖7 幾何面積對(duì)定位誤差的影響

從圖7可知,隨著錨節(jié)點(diǎn)面積的增大,區(qū)域定位誤差逐漸變小。因此,為了降低區(qū)域定位誤差, 錨節(jié)點(diǎn)的幾何面積要盡量大,覆蓋盡可能廣的待定位區(qū)域。

當(dāng)錨節(jié)點(diǎn)不構(gòu)成正三角形時(shí),考察錨節(jié)點(diǎn)幾何形狀與幾何面積對(duì)區(qū)域定位誤差均界的影響。錨節(jié)點(diǎn)間的夾角保持120°不變,為保持錨節(jié)點(diǎn)三角形(正三角形、非正三角形)的幾何面積相等,非正三角形的極徑設(shè)置如圖8所示。

圖8 不同的錨節(jié)點(diǎn)形狀

改變極徑r值大小,使不同形狀三角形的幾何面積同步增大,計(jì)算不同r值對(duì)應(yīng)的區(qū)域定位誤差均界,仿真結(jié)果如圖9所示。

圖9 幾何面積相等時(shí)極徑對(duì)錨節(jié)點(diǎn)形狀的影響

從圖9可知,不管是正三角形還是非正三角形,隨著錨節(jié)點(diǎn)幾何面積的增大,區(qū)域定位誤差逐漸變小。將正三角形和非正三角形進(jìn)行對(duì)比發(fā)現(xiàn),當(dāng)幾何面積相等時(shí),區(qū)域定位誤差亦相差不大。雖然非正三角形的幾何形態(tài)不如正三角形,但當(dāng)其面積更大時(shí),對(duì)應(yīng)的誤差均界更小。因此,為了提高區(qū)域定位精度,相較于錨節(jié)點(diǎn)的幾何形狀,錨節(jié)點(diǎn)的幾何面積起到了更大的作用,因而在錨節(jié)點(diǎn)優(yōu)化布設(shè)時(shí),要優(yōu)先考慮幾何面積的大小,使之覆蓋的待定位區(qū)域盡可能大。

3.2 算法設(shè)計(jì)

從上述仿真結(jié)果可知,錨節(jié)點(diǎn)幾何中心的位置、幾何形狀和幾何面積對(duì)區(qū)域定位誤差均界存在影響,且錨節(jié)點(diǎn)幾何中心與區(qū)域質(zhì)心越接近、錨節(jié)點(diǎn)幾何形狀越接近均勻等角、錨節(jié)點(diǎn)幾何面積越大時(shí),區(qū)域定位誤差均界越小。與幾何形狀相比,幾何面積的影響更大,因此,應(yīng)該優(yōu)先考慮錨節(jié)點(diǎn)的幾何面積。據(jù)此,設(shè)計(jì)啟發(fā)式的錨節(jié)點(diǎn)布設(shè)算法(Heuristic Optimized Anchor Deployment,HOAD)。

算法2HOAD算法

輸入給定一個(gè)凸區(qū)域A和待布設(shè)的錨節(jié)點(diǎn)個(gè)數(shù)M

輸出將夾角αmax對(duì)應(yīng)的交點(diǎn){b1,b2,…,bM}max作為M個(gè)錨節(jié)點(diǎn)的布設(shè)位置

步驟1選取區(qū)域A的質(zhì)心c。

步驟2以點(diǎn)c為中心,均勻等角布設(shè)M個(gè)錨節(jié)點(diǎn),第1個(gè)錨節(jié)點(diǎn)與水平正方向的夾角為α。相鄰錨節(jié)點(diǎn)的夾角等于2π/M,第i個(gè)錨節(jié)點(diǎn)與區(qū)域邊界的交點(diǎn)記為bi。

步驟3改變?chǔ)恋拇笮?使之在0～2π/M間變換。計(jì)算α=αk時(shí),錨節(jié)點(diǎn)位置{b1,b2,…,bM}k構(gòu)成的幾何面積Sk,從中選出最大面積Smax對(duì)應(yīng)的角度,將其標(biāo)記為αmax。

算法2的原理如圖10所示。

圖10 HOAD算法原理示意圖

3.3 算法性能分析

為評(píng)價(jià)HOAD算法的性能,與算法1窮盡式搜索方法進(jìn)行定位精度和運(yùn)行時(shí)間的比較。考慮在一個(gè)不規(guī)則凸區(qū)域內(nèi),布設(shè)3個(gè)錨節(jié)點(diǎn)的情形。仿真使用Matlab7.0,PC機(jī)的CPU為2.33 GHz雙核,內(nèi)存為4 GB。假設(shè)節(jié)點(diǎn)間的測(cè)距誤差服從獨(dú)立同高斯分布N(0,σ2),其中σ=5 m,隨機(jī)布設(shè)的節(jié)點(diǎn)數(shù)N=1 000,搜索步長(zhǎng)在20 m～40 m之間變化。

定位精度的評(píng)價(jià)指標(biāo)為區(qū)域均方根定位誤差rRMS,定義如下:

圖11表示采用啟發(fā)式錨節(jié)點(diǎn)優(yōu)化布設(shè)算法HOAD選取的錨節(jié)點(diǎn)位置,其中,實(shí)線表示區(qū)域邊界。采用搜索法時(shí)首先將區(qū)域均勻劃分為1 m×1 m的小格,然后使用不同的搜索步長(zhǎng)在離散的小格內(nèi)窮盡式搜索錨節(jié)點(diǎn)的最優(yōu)位置,比較HOAD算法和搜索法的定位精度和計(jì)算復(fù)雜度,結(jié)果如圖12和圖13所示。

圖11 HOAD算法運(yùn)行結(jié)果

圖12 2種算法定位精度對(duì)比

圖13 2種算法運(yùn)行時(shí)間對(duì)比

從圖12、圖13看出,對(duì)于搜索法本身而言,隨著搜索步長(zhǎng)的增大,算法運(yùn)行時(shí)間下降很快。從圖13可以看出,HOAD的運(yùn)行時(shí)間與搜索法存在3個(gè)～5個(gè)數(shù)量級(jí)的差異。綜合上述仿真分析可知,HOAD算法兼具定位精度高、計(jì)算開銷小的優(yōu)勢(shì),更能適用于實(shí)際應(yīng)用場(chǎng)景。

4 結(jié)束語

在無線傳感器網(wǎng)絡(luò)中,本文基于定位誤差CRLB的推導(dǎo),揭示了錨節(jié)點(diǎn)與待定位節(jié)點(diǎn)構(gòu)成的幾何形狀對(duì)節(jié)點(diǎn)定位精度的影響。從提高區(qū)域平均定位精度和降低計(jì)算復(fù)雜度的角度研究了錨節(jié)點(diǎn)優(yōu)化布設(shè)問題,提出了錨節(jié)點(diǎn)布設(shè)性能的評(píng)價(jià)標(biāo)準(zhǔn),即區(qū)域定位誤差均界。采用仿真手段研究了錨節(jié)點(diǎn)質(zhì)心、幾何形狀、幾何面積對(duì)區(qū)域定位性能的影響,據(jù)此提出了啟發(fā)式的錨節(jié)點(diǎn)優(yōu)化布設(shè)算法HOAD,并與經(jīng)典的搜索法進(jìn)行了定位精度和計(jì)算復(fù)雜度的比較。仿真結(jié)果表明,HOAD算法的計(jì)算開銷明顯小于搜索法,因而實(shí)用價(jià)值更高。