【正文】
分析可知,為了提高定位精度,需要增加信標(biāo)節(jié)點(diǎn),但信標(biāo)節(jié)點(diǎn)造價高。為了提高定位精度,降低布網(wǎng)復(fù)雜度,本文提出一種基于移動信標(biāo)的定位方法。帶有定位裝置的信標(biāo)節(jié)點(diǎn)裝載在可移動的平臺或移動機(jī)器人上,就構(gòu)造了一個移動信標(biāo),移動信標(biāo)在一定規(guī)律的移動過程中,可實(shí)時獲取自身位置,并周期性的廣播自身的位置信息,以幫助未知節(jié)點(diǎn)進(jìn)行定位。信標(biāo)節(jié)點(diǎn)移動模型 移動信標(biāo)節(jié)點(diǎn)采用什么樣的方式移動才能盡可能的遍歷整個網(wǎng)絡(luò),這個本身就是一個研究的熱點(diǎn),網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)本身是隨機(jī)散布的,節(jié)點(diǎn)位置本身信息是未知的,為了使這些節(jié)點(diǎn)全部進(jìn)行定位,需要設(shè)計(jì)出一種運(yùn)動模型,使移動信標(biāo)的運(yùn)動軌跡能在盡少的時間內(nèi)遍歷網(wǎng)絡(luò),發(fā)送足夠的定位信息給未知節(jié)點(diǎn)以完成定位算法。目前應(yīng)用于無線傳感器網(wǎng)絡(luò)的移動模型有S型、RWP(Random Way Point)模型和GaussMarkov模型等。這些模型是自組織網(wǎng)絡(luò)中廣泛應(yīng)用的模型,RWP模型對信標(biāo)的硬件要求小,路徑的隨機(jī)性大,并且隨著運(yùn)動速度逐漸減小,運(yùn)動軌跡出現(xiàn)在網(wǎng)絡(luò)中心區(qū)域的概率偏大。S模型則對硬件的要求相對較高。為此本文選擇GaussMarkov運(yùn)動模型,該模型可以覆蓋網(wǎng)絡(luò)的大部分區(qū)域,相對于RWP模型,可以避免運(yùn)動軌跡的突變和邊緣地帶概率減少的缺點(diǎn)[40] ,對硬件的要求也不高,其模型表示如下: () ()v(k)和d(k)表示運(yùn)動時刻k移動信標(biāo)的速度和方向。a是方向隨機(jī)調(diào)節(jié)參數(shù),取值為0到1(0=a=1),vmean, dmean為平均速度和平均運(yùn)動方向,,代表高斯隨機(jī)變量。移動的下一時刻的速度和方向從當(dāng)前的速度和方向求出: () ()信標(biāo)節(jié)點(diǎn)按照GaussMarkov模型計(jì)算每個時刻的運(yùn)動速度和方向,并由定位裝置獲取當(dāng)前運(yùn)動位置的坐標(biāo)信息,將其廣播到網(wǎng)絡(luò)中。因?yàn)樾艠?biāo)節(jié)點(diǎn)要周期性的廣播坐標(biāo)信息,還要接收網(wǎng)絡(luò)中未知節(jié)點(diǎn)廣播回來的跳數(shù)累加的廣播分組,故在GaussMarkov模型中,設(shè)置一個計(jì)時器,計(jì)時周期為信標(biāo)節(jié)點(diǎn)廣播坐標(biāo)的周期,每當(dāng)計(jì)時器時間到,移動暫停,廣播當(dāng)前位置信息,并接收各未知節(jié)點(diǎn)返回的跳數(shù)廣播分組,記錄在列表中,再繼續(xù)移動?;谝苿有艠?biāo)節(jié)點(diǎn)算法的定位過程信標(biāo)節(jié)點(diǎn)在網(wǎng)絡(luò)中移動,周期性地將位置信息廣播到網(wǎng)絡(luò)中,廣播的信息格式包括當(dāng)前運(yùn)動到第幾個點(diǎn),當(dāng)前位置坐標(biāo),網(wǎng)絡(luò)跳數(shù)(初始化為0),在移動信標(biāo)節(jié)點(diǎn)通信范圍的未知節(jié)點(diǎn)都接收到該位置的信標(biāo)節(jié)點(diǎn)的定位數(shù)據(jù)包。每個節(jié)點(diǎn)接收到定位信息后,將其中的跳數(shù)值加1后繼續(xù)廣播。每個節(jié)點(diǎn)接收到多個鄰居節(jié)點(diǎn)的廣播值都與本身記有的值比較,如果小于自身記有的跳數(shù)值,則丟棄這個廣播分組。這一過程與DVHop定位算法相似,不同的是,未知節(jié)點(diǎn)判斷接收到的是第幾號位的信標(biāo)節(jié)點(diǎn)廣播,如果為第一個就暫不廣播,直到接收到第二號位的信標(biāo)廣播時,再把一號位的定位信息包廣播出去,并保存接收到的二號位廣播,等待下一位的廣播后再發(fā)送,以此類推。廣播定位信息的過程分為以下幾步:步驟1:移動信標(biāo)在第一個位置取得當(dāng)前位置信息,封裝位置信息廣播信息包{LIDi, xi, yi, HOPs},LIDi表示當(dāng)前是第幾號位置的廣播包,xi,yi表示當(dāng)前位置坐標(biāo),HOPs為經(jīng)歷的跳數(shù),初始為0;步驟2:移動信標(biāo)在第一個位置的通信范圍內(nèi)所有鄰居節(jié)點(diǎn)接收到定位信息包,接收到信息包的節(jié)點(diǎn)將其與本身的數(shù)據(jù)包進(jìn)行比較,取跳數(shù)較小的一項(xiàng),并丟棄較大的,將跳數(shù)一項(xiàng)加1,記錄下這個跳數(shù)值,等待下一個定位信息包;步驟3:移動信標(biāo)移動到下一個位置,將位置信息加1并廣播這個一新位置的定位信息包,同時接收各節(jié)點(diǎn)發(fā)回的廣播信息,取與前一位置最小跳數(shù)的分組,將兩位置的距離除以跳數(shù)計(jì)算出平均每跳距離(Di)并廣播到網(wǎng)絡(luò)中;步驟4:重復(fù)步驟3直到位置號達(dá)到預(yù)先設(shè)定的閾值K,K根據(jù)所需的虛擬信標(biāo)密度而定,如果網(wǎng)絡(luò)中有N個未知節(jié)點(diǎn),根據(jù)精度要求得出虛擬信標(biāo)比例q,則;步驟5:節(jié)點(diǎn)根據(jù)接收到的各個虛擬信標(biāo)的平均跳距離按權(quán)值進(jìn)行校正,并根據(jù)記錄的跳數(shù)計(jì)算出到各個虛擬信標(biāo)的距離,挑選出最優(yōu)的虛擬信標(biāo)節(jié)點(diǎn)距離信息,按優(yōu)化的三邊測量法計(jì)算自己的位置。加權(quán)值法計(jì)算平均跳距離為了更準(zhǔn)確的計(jì)算出估計(jì)的平均跳距離值,本文引入權(quán)值的概念,運(yùn)用加權(quán)值對平均跳距離進(jìn)行校正是基于網(wǎng)絡(luò)并非完全的均勻分布,各個節(jié)點(diǎn)接收到多個虛擬節(jié)點(diǎn)的平均跳距離值,越是靠近未知節(jié)點(diǎn)其平均跳距離值更能反映出未知節(jié)點(diǎn)所在的網(wǎng)絡(luò)區(qū)域的情況,對其平均跳距離的影響也越大,所以應(yīng)當(dāng)占有更大的權(quán)值,這樣比只計(jì)算平均值更接近真實(shí)值,計(jì)算出來的未知節(jié)點(diǎn)位置更精確。為了方便表達(dá),我們假設(shè)網(wǎng)絡(luò)中的未知節(jié)點(diǎn)Nj接收到多個虛擬信標(biāo)的平均跳距離值,虛擬信標(biāo)Ai計(jì)算的平均跳距離記為Di,節(jié)點(diǎn)Nj到信標(biāo)Ai的跳數(shù)為Hi。加權(quán)因子體現(xiàn)的是各個虛擬信標(biāo)節(jié)點(diǎn)計(jì)算出來的平均跳距離值對未知節(jié)點(diǎn)計(jì)算平均跳距離值的影響力,假設(shè)未知節(jié)點(diǎn)N1接收到三個虛擬信標(biāo)節(jié)點(diǎn)(A1,A2,A3)的平均跳距離值(D1,D2,D3),而該節(jié)點(diǎn)查找表中所記的跳數(shù)值知道其距離三個虛擬信標(biāo)的跳數(shù)分別為:H1,H2,H3。那么節(jié)點(diǎn)計(jì)算其平均距離值如下式: ()各個平均跳距離的權(quán)值相加為1,反映的是各個平均跳距離值對最終計(jì)算的跳距離值的影響程度,這樣計(jì)算節(jié)點(diǎn)Nj的平均跳距離值就為: ()至此,各未知節(jié)點(diǎn)已得到與各個虛擬信標(biāo)的跳數(shù),并可據(jù)此求出適合自己網(wǎng)絡(luò)區(qū)域內(nèi)的平均跳距離值,因此可利用三邊測量法計(jì)算出未知節(jié)點(diǎn)Nj的坐標(biāo)。 仿真分析為了驗(yàn)證算法的性能,將提出的算法在OMNeT++平臺進(jìn)行仿真,并用MATLAB進(jìn)行實(shí)驗(yàn)數(shù)據(jù)的輔助分析,在OMNeT++平臺上,將100個傳感器節(jié)點(diǎn)隨機(jī)分布在一個5050的區(qū)域中,節(jié)點(diǎn)通信半徑為10。網(wǎng)絡(luò)中還有一個可獲得自身位置的移動信標(biāo)按GaussMarkov模型移動,平均速度為5,初始方向角設(shè)為90o,在邊緣區(qū)域時轉(zhuǎn)變系數(shù),即式(4,5)中=,移動信標(biāo)的廣播計(jì)算器設(shè)置為2秒,即移動信標(biāo)節(jié)點(diǎn)每移動2秒后即在網(wǎng)絡(luò)中進(jìn)行定位信息的廣播。為了使仿真結(jié)果更接近實(shí)際的情況,仿真結(jié)果是經(jīng)過20次獨(dú)立仿真結(jié)果平均值獲得。定位精度與定位覆蓋率分析移動信標(biāo)以預(yù)定的運(yùn)動模型運(yùn)動,并周期性的廣播定位信息包, 即虛擬信標(biāo)的增長速度,虛擬信標(biāo)越多,定位精度越高,所花的定位時間也越多,他們存在圖33中的關(guān)系。圖中所示的關(guān)系是顯然的,隨著時間的推移,移動信標(biāo)在網(wǎng)絡(luò)中移動的距離越遠(yuǎn),廣播的定位信息越多,虛擬信標(biāo)也越多,定位的誤差也隨之減小。同樣的,隨著移動信標(biāo)的軌跡覆蓋了越多的地方,越來越多的未知節(jié)點(diǎn)獲得定位信息包而計(jì)算自己的位置,定位的覆蓋率也不斷增加。圖33定位誤差與定位覆蓋率 Localization error and Localization ratio信標(biāo)節(jié)點(diǎn)廣播定位信息周期T的影響當(dāng)移動信標(biāo)節(jié)點(diǎn)以參數(shù)一定的GaussMarkov模型運(yùn)動時,廣播周期越小,則虛擬信標(biāo)越密,即單位區(qū)域內(nèi)虛擬信標(biāo)越多,必然導(dǎo)致節(jié)點(diǎn)通信消耗的增大,誤差也增大。當(dāng)周期T增大到一定程序時,再增大,則廣播的定位信息大少,用于定位的虛擬信標(biāo)大少,也會導(dǎo)致定位誤差的增大。最優(yōu)的定位周期的大小由節(jié)點(diǎn)由通信半徑?jīng)Q定,當(dāng)通信半徑越大時,廣播的周期也應(yīng)相應(yīng)的增大。在同樣的移動模型下,當(dāng)廣播周期T變化時,定位誤差與其關(guān)系如下圖34所示:圖34移動信標(biāo)廣播周期T與平均定位誤差 Broadcast Period T for Mobile Beacon and Average Positioning Error定位誤差比較算法的性能主要以定位的誤差來評價,移動信標(biāo)以2秒的周期廣播定位信息包,即在網(wǎng)絡(luò)中構(gòu)造一個虛擬信標(biāo)。仿真結(jié)果的比較如圖35所示。圖35移動信標(biāo)廣播周期T與平均定位誤差 Relationship between mobile beacon brocasting period and average position error 如圖35中可見,兩種定位算法的誤差隨著信標(biāo)節(jié)點(diǎn)的增加都會減少,在信標(biāo)節(jié)點(diǎn)越多的時候,本文提出的算法誤差減少更明顯,這是因?yàn)椴捎昧思訖?quán)處理來求各未知節(jié)點(diǎn)的平均跳距離,當(dāng)一個節(jié)點(diǎn)獲得越多其周圍的虛擬信標(biāo)計(jì)算的平均跳距離,加權(quán)處理后的平均跳距離就越接近真實(shí)的網(wǎng)絡(luò)情況。DVHop是一種經(jīng)典的無需測距的定位算法,具有定位算法簡單,定位精度較高的優(yōu)點(diǎn),但其定位精度依賴于網(wǎng)絡(luò)連通狀況,對于各向同性的網(wǎng)絡(luò),可以獲得較適當(dāng)?shù)亩ㄎ痪?,而對于不?guī)則拓?fù)涞木W(wǎng)絡(luò)定位誤差則較大[41] 。DVHop算法在獲得平均每跳距離的計(jì)算過程中,節(jié)點(diǎn)之間的通信量過大,將網(wǎng)絡(luò)作為一個整體考慮,所有節(jié)點(diǎn)在計(jì)算自己與參考節(jié)點(diǎn)的距離時使用同一個平均跳距離,導(dǎo)致平均定位誤差較大。DVHop算法在網(wǎng)絡(luò)平均連通度為10,參考節(jié)點(diǎn)比例為10%的各向同性網(wǎng)絡(luò)中定位精度約為33%。該算法的缺點(diǎn)是僅僅在各向同性的密集網(wǎng)絡(luò)中,才能合理地估算平均每跳的距離[10] 。針對這種情況,提出了一種基于移動信標(biāo)動態(tài)選擇的改進(jìn)DVHop定位算法(DSBDVHop),通過引入移動信標(biāo)在網(wǎng)絡(luò)中按預(yù)定軌跡漫游,并在每個虛擬信標(biāo)節(jié)點(diǎn)的位置單獨(dú)計(jì)算網(wǎng)絡(luò)各部位的平均跳距離后廣播其位置分組,未知節(jié)點(diǎn)記錄到每個虛擬信標(biāo)的跳數(shù),動態(tài)選擇能獲得最高計(jì)算精度的信標(biāo)節(jié)點(diǎn)來進(jìn)行三邊測量法計(jì)算自己的位置,減少無線傳感器網(wǎng)絡(luò)定位的成本,并且提高了定位精度。最后通過仿真證明此算法可以提高定位精度,減少算法的計(jì)算量,提高了定位的效率。 DVHop定位算法平均跳距離計(jì)算誤差來源分析在運(yùn)行DVHop定位算法時,會先預(yù)定在網(wǎng)絡(luò)中進(jìn)行洪泛的數(shù)據(jù)包的跳數(shù),包含信標(biāo)節(jié)點(diǎn)位置信息的數(shù)據(jù)包只經(jīng)過預(yù)定的跳數(shù)。節(jié)點(diǎn)每接到一個數(shù)據(jù)包會在表示其生命周期的跳數(shù)加1,當(dāng)達(dá)到預(yù)定的跳數(shù)時,則不再轉(zhuǎn)發(fā)這一數(shù)據(jù)包。在上述的DVHop定位算法的過程中,信標(biāo)節(jié)點(diǎn)會根據(jù)他接收到的所有信標(biāo)節(jié)點(diǎn)發(fā)來的數(shù)據(jù)包的信息計(jì)算平均每跳距離。當(dāng)信標(biāo)節(jié)點(diǎn)計(jì)算好自身網(wǎng)絡(luò)的平均跳距離后,把這個跳距離廣播到自己的網(wǎng)絡(luò)中,同樣制定了表示其生存周期的預(yù)定跳數(shù)。即在其指定跳數(shù)范圍內(nèi)的未知節(jié)點(diǎn)會接收到這個平均跳距離的數(shù)據(jù)包。未知節(jié)點(diǎn)只記錄其接收到的第一個信標(biāo)節(jié)點(diǎn)發(fā)來的平均跳距離,作為自己計(jì)算與信標(biāo)節(jié)點(diǎn)的距離的依據(jù)。如圖36所示的情況中,我們可以看到:當(dāng)某未知節(jié)點(diǎn)N接收到來自其周圍3跳距離內(nèi)的信標(biāo)節(jié)點(diǎn)的定位信息時,其列表中將有5個信標(biāo)節(jié)點(diǎn)的位置及跳數(shù)。由圖中所示情況我們可以看到,信標(biāo)節(jié)點(diǎn)A4和A5與未知節(jié)點(diǎn)的距離經(jīng)過中間節(jié)點(diǎn)時“彎曲”的比其它信標(biāo)節(jié)點(diǎn)要厲害些。如果按同樣的平均跳距離計(jì)算時,未知節(jié)點(diǎn)N與A4和A5的距離是要小于它到其它節(jié)點(diǎn)的距離。因此,在定位計(jì)算中,如果把A1, A2, A3, A4, A5都計(jì)算在內(nèi),其得到的誤差必然會增大,因?yàn)锳4和A5兩個信標(biāo)節(jié)點(diǎn)雖然都在A節(jié)點(diǎn)的兩跳通信距離內(nèi),在其實(shí)際距離并沒有平均跳距離的兩倍,從節(jié)點(diǎn)A到這兩個節(jié)點(diǎn)時傳輸?shù)姆纸M數(shù)據(jù)包是“曲折”的,而A1, A2和A3都是近似直線的。在定位計(jì)算過程中,當(dāng)這種節(jié)點(diǎn)增多時,對于定位誤差的影響顯而易見。文獻(xiàn)[42] 通過實(shí)驗(yàn)發(fā)現(xiàn)在這種條件下分析每一個未知節(jié)點(diǎn)定位的精度時,有些誤差達(dá)到200%。假設(shè)從圖36中得到的5個信標(biāo)節(jié)點(diǎn)的列表中選擇三個信標(biāo)節(jié)點(diǎn)的數(shù)據(jù)包分組來進(jìn)行三邊定位計(jì)算,如果選擇不同的信標(biāo)節(jié)點(diǎn),對計(jì)算的誤差是顯而易見的。我們可以從中選取兩種組合來比較,如A3,A4和A5的組合和A1,A2和A3的組合。圖37是兩種組合下的計(jì)算情況的示意圖,從圖中我們可以看到,當(dāng)A4和A5這兩個節(jié)點(diǎn)參與三邊定位計(jì)算時,其定位的誤差明顯增加。因此,設(shè)計(jì)移動信標(biāo)的動態(tài)選擇算法來選擇最佳的虛擬信標(biāo)的數(shù)據(jù)參與三邊定位計(jì)算,將直接影響其定位計(jì)算的精度。圖36 DVHop定位算法誤差來源分析 The resource of Localization error of DVHop (a). 選擇A1,A2和A3計(jì)算(a). Select A1, A2 and A3 to run trilateration algorithm(b) 選擇A3,A4和A5計(jì)算(b). Select A3, A4 and A5 to run trilateration algorithm圖37 選擇不同的信標(biāo)節(jié)點(diǎn)進(jìn)行三邊定位計(jì)算示意 Select diffirent beacon nodes for trilateration calculating帶有定位裝置的信標(biāo)節(jié)點(diǎn)裝載在可移動的平臺或移動機(jī)器人上,就構(gòu)造了一個移動信標(biāo),移動信標(biāo)在一定規(guī)律的移動過程中,可實(shí)時獲取自身位置,并周期性的廣播自身的位置信息,以幫助未知節(jié)點(diǎn)進(jìn)行定位。當(dāng)未知節(jié)點(diǎn)獲得足夠多的虛擬信標(biāo)的信息時,我們需要動態(tài)選擇最優(yōu)的虛擬信標(biāo)參與三邊定位計(jì)算來提高計(jì)算精度,本文接下從信標(biāo)節(jié)點(diǎn)的移動模型,虛擬信標(biāo)的動態(tài)選擇算法來分析如何選擇進(jìn)行基于移動信標(biāo)動態(tài)選擇的改進(jìn)型DVHop定位算法。信標(biāo)節(jié)點(diǎn)移動模型移動信標(biāo)節(jié)點(diǎn)采用什么樣的方式移動才能盡可能的遍歷整個網(wǎng)絡(luò),這個本身就是一個研究的熱點(diǎn),網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)本身是隨機(jī)散布的,節(jié)點(diǎn)位置本身信息是未知的,為了使這些節(jié)點(diǎn)全部進(jìn)行定位,需要設(shè)計(jì)出一種運(yùn)動模型,使移動信標(biāo)的運(yùn)動軌跡能在盡少的時間內(nèi)遍歷網(wǎng)絡(luò),發(fā)送足夠的定位信息給未知節(jié)點(diǎn)以完成定位算法。目前應(yīng)用于無線傳感器網(wǎng)絡(luò)的移動模型有S型、RWP(Random Way Point)模型和GaussMarkov模型等。這些模型是自組織網(wǎng)絡(luò)中廣泛應(yīng)用的模型,RWP模型對信標(biāo)的硬件要求小,路徑的隨機(jī)性大,并且隨著運(yùn)動速度逐漸減小,運(yùn)動軌跡出現(xiàn)在網(wǎng)絡(luò)中心區(qū)域的概率偏大。S模型則對硬件的要求相對較高。,該模型可以覆蓋網(wǎng)絡(luò)的大部分區(qū)域,相對于RWP模型,可以避免運(yùn)動軌跡的突變和邊緣地帶概率減少的缺點(diǎn)[6],對硬件的要求也不高。信標(biāo)節(jié)點(diǎn)按照GaussMarkov模型計(jì)算每個時刻的運(yùn)動速度和方向,并由定位裝置獲取當(dāng)前運(yùn)