基于移動(dòng)錨點(diǎn)的三維無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位算法研究?

王 群陳友榮?陳 浩蘇子漪劉半藤萬(wàn)錦昊

(1.浙江樹(shù)人大學(xué)信息科技學(xué)院,浙江 杭州310015；2.常州大學(xué)計(jì)算機(jī)與人工智能學(xué)院,江蘇 常州213164)

無(wú)線傳感網(wǎng)(wireless sensor network,WSN)由在一個(gè)區(qū)域內(nèi)均勻或隨機(jī)部署的能量、容量和功能有限的大量微型低成本傳感節(jié)點(diǎn)組成。其中,定位作為WSN不可或缺的一部分,可廣泛應(yīng)用于目標(biāo)移動(dòng)監(jiān)測(cè)、核能監(jiān)測(cè)、生物攻擊監(jiān)測(cè)等軍事應(yīng)用,森林火災(zāi)監(jiān)測(cè)、洪水監(jiān)測(cè)、精準(zhǔn)農(nóng)業(yè)等環(huán)境應(yīng)用,家庭和辦公室自動(dòng)化,人體健康監(jiān)測(cè),醫(yī)院內(nèi)醫(yī)生和患者跟蹤等應(yīng)用領(lǐng)域[1]。雖然均勻部署的傳感節(jié)點(diǎn)能夠較好的實(shí)現(xiàn)定位,但是隨機(jī)部署的傳感節(jié)點(diǎn)可能會(huì)造成網(wǎng)絡(luò)的分裂,部分區(qū)域密集分布,部分區(qū)域稀疏分布甚至不存在,因此需要進(jìn)行定位,從而獲得每一個(gè)傳感節(jié)點(diǎn)的準(zhǔn)確位置坐標(biāo)[2]。

目前,二維無(wú)線傳感網(wǎng)(2D WSN)的定位算法研究成果較多,其在平坦的地形上定位精度較高[3]。但是在地上和水下的無(wú)線傳感網(wǎng)較多應(yīng)用中,需要考慮傳感節(jié)點(diǎn)的三維坐標(biāo)。2D WSN通信范圍是圓形,而三維無(wú)線傳感網(wǎng)(3D WSN)的通信范圍為球形,且定位時(shí)需要4個(gè)以上的錨點(diǎn)位置坐標(biāo),這使3D WSN的傳感節(jié)點(diǎn)定位問(wèn)題面臨新的挑戰(zhàn)。

目前,3D WSN的定位算法可分成無(wú)距離定位算法和基于距離的定位算法。無(wú)距離定位算法可包括DV-hop(distance vector-hop)[4],質(zhì)心等算法,但是該類(lèi)算法只能粗略獲知傳感節(jié)點(diǎn)分布的位置,定位精度較低。而基于距離的定位算法,利用錨點(diǎn)提供的參考位置,計(jì)算傳感節(jié)點(diǎn)的位置信息,其定位精度較高。其中,部分學(xué)者側(cè)重于研究基于靜態(tài)錨點(diǎn)的3D WSN節(jié)點(diǎn)定位算法,如文獻(xiàn)[5]提出一種用于無(wú)線傳感網(wǎng)三維定位的迭代估計(jì)算法。該算法計(jì)算三維空間的質(zhì)心坐標(biāo)和節(jié)點(diǎn)間的接收信號(hào)強(qiáng)度,利用已定位節(jié)點(diǎn)替代距離最遠(yuǎn)的錨點(diǎn)。文獻(xiàn)[6]提出一種基于多通信半徑和跳距加權(quán)的WSN三維迭代定位算法。該算法參考錨點(diǎn)數(shù)量設(shè)置跳數(shù)閾值,計(jì)算平均跳距的權(quán)值,采用最小最大法計(jì)算節(jié)點(diǎn)位置。文獻(xiàn)[7]提出一種3D WSN的分布式無(wú)范圍節(jié)點(diǎn)定位算法。該算法更新錨點(diǎn)的平均跳數(shù),減少由共面的錨節(jié)點(diǎn)引起的位置誤差,并采用輔助錨點(diǎn),提高定位范圍。文獻(xiàn)[8]考慮3D通道模型,通過(guò)氣壓傳感器和錨點(diǎn),提出基于Gauss-Newton和兩步最小二乘估計(jì)的室內(nèi)定位估計(jì)算法,從而提高定位精度。文獻(xiàn)[9]評(píng)估校正幾何稀釋度,提出三維無(wú)線傳感網(wǎng)的到達(dá)角目標(biāo)定位算法。但是在文獻(xiàn)[5－9]的3D WSN中,錨點(diǎn)位置固定不變,且每一個(gè)傳感節(jié)點(diǎn)的定位需要不共面的4個(gè)以上錨點(diǎn),因此其定位算法需要較多的錨點(diǎn),這較難應(yīng)用到傳感節(jié)點(diǎn)分布不均勻的隨機(jī)部署3D WSN中。

因此,部分學(xué)者側(cè)重于研究基于移動(dòng)錨點(diǎn)的3D WSN節(jié)點(diǎn)定位算法,如文獻(xiàn)[10]將定位過(guò)程分為位置估計(jì),坐標(biāo)轉(zhuǎn)換,位置優(yōu)化和位置校正四個(gè)主要步驟,提出用于3D移動(dòng)定位的動(dòng)態(tài)多維縮放算法。文獻(xiàn)[11]提出基于移動(dòng)信標(biāo)的定位算法,即選擇信標(biāo)點(diǎn)集和合適錨點(diǎn)的最佳集合,并通過(guò)決策規(guī)則提高定位算法。但是文獻(xiàn)[10－11]沒(méi)有考慮移動(dòng)錨點(diǎn)的移動(dòng)路徑。部分學(xué)者側(cè)重于研究移動(dòng)錨點(diǎn)的路徑規(guī)劃算法,如文獻(xiàn)[12]比較隨機(jī)選擇網(wǎng)格中心的隨機(jī)移動(dòng)算法,讓移動(dòng)節(jié)點(diǎn)隨機(jī)選擇距離最近的未經(jīng)過(guò)網(wǎng)格中心作為下一時(shí)刻的停留位置,提出貪婪移動(dòng)路徑選擇算法(greedy moving path selection algorithm,GREED)。文獻(xiàn)[13]利用節(jié)點(diǎn)的三維位置信息,提出一種移動(dòng)節(jié)點(diǎn)的線性移動(dòng)路徑選擇算法(Linear moving path selection algorithm for mobile nodes,LMPS),但是文獻(xiàn)[12－13]只是考慮移動(dòng)節(jié)點(diǎn)的移動(dòng)路徑選擇,沒(méi)有考慮傳感節(jié)點(diǎn)的定位問(wèn)題。

綜上所述,目前基于靜態(tài)錨點(diǎn)的3D WSN節(jié)點(diǎn)定位算法需要較多的錨點(diǎn),基于移動(dòng)錨點(diǎn)的3D WSN節(jié)點(diǎn)定位算法較少考慮移動(dòng)錨點(diǎn)的3D移動(dòng)路徑。因此在上述文獻(xiàn)的基礎(chǔ)上,考慮3D環(huán)境下移動(dòng)錨點(diǎn)的移動(dòng)路徑,提出一種基于移動(dòng)錨點(diǎn)的三維無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位算法(node localization algorithm of 3D wireless sensor networks based on mobile anchor,NLA_3D)。在NLA_3D算法中,隨機(jī)分布的傳感節(jié)點(diǎn)通過(guò)無(wú)線通信,獲知所有鄰居傳感節(jié)點(diǎn)的距離等連接信息,自組織成多個(gè)傳感節(jié)點(diǎn)全連接的連接樹(shù)。移動(dòng)錨點(diǎn)在隨機(jī)移動(dòng)探測(cè)監(jiān)測(cè)區(qū)域的過(guò)程中,如果發(fā)現(xiàn)未定位傳感節(jié)點(diǎn),則獲知該傳感節(jié)點(diǎn)所在連接樹(shù)的所有傳感節(jié)點(diǎn)連接信息,采用混合海洋掠食者算法,計(jì)算自身的最優(yōu)移動(dòng)路徑,并在該移動(dòng)路徑的每一個(gè)停留位置上,提供四個(gè)不共面的錨點(diǎn)位置信息,幫助周?chē)鷤鞲泄?jié)點(diǎn)定位。傳感節(jié)點(diǎn)接收錨點(diǎn)和已定位傳感節(jié)點(diǎn)的參考位置信息,采用極大似然估計(jì)算法計(jì)算自身位置,并發(fā)送給移動(dòng)錨點(diǎn)。NLA_3D算法可定位監(jiān)測(cè)區(qū)域內(nèi)所有傳感節(jié)點(diǎn),增加傳感節(jié)點(diǎn)的平均錨點(diǎn)位置個(gè)數(shù)和降低平均節(jié)點(diǎn)定位誤差。

1 算法原理

NLA_3D算法假設(shè):在3D WSN中,存在隨機(jī)部署且未知自身位置的靜止傳感節(jié)點(diǎn)和一個(gè)可移動(dòng)的錨點(diǎn)。移動(dòng)錨點(diǎn)能夠通過(guò)GPS(global positioning system)和北斗等衛(wèi)星定位模塊獲知自身的位置坐標(biāo)。

如圖1所示,傳感節(jié)點(diǎn)隨機(jī)分布在三維立體監(jiān)測(cè)區(qū)域內(nèi)且需要獲知自身的位置,同時(shí)為降低系統(tǒng)成本和能耗,采用一個(gè)移動(dòng)錨點(diǎn)輔助定位傳感節(jié)點(diǎn)。但是NLA_3D算法仍需要解決以下二個(gè)問(wèn)題:一是移動(dòng)錨點(diǎn)如何為其通信范圍內(nèi)的傳感節(jié)點(diǎn)提供錨點(diǎn)位置信息,傳感節(jié)點(diǎn)如何利用移動(dòng)錨點(diǎn)的位置信息和已定位傳感節(jié)點(diǎn)位置信息,計(jì)算自身的位置坐標(biāo)；二是移動(dòng)錨點(diǎn)如何在三維立體監(jiān)測(cè)區(qū)域內(nèi)移動(dòng),從而為其通信范圍內(nèi)的傳感節(jié)點(diǎn)提供不共面的4個(gè)以上錨點(diǎn)位置。這二個(gè)問(wèn)題的具體解決如下。

圖1 NLA_3D算法原理

1.1 傳感節(jié)點(diǎn)的定位

假設(shè)網(wǎng)絡(luò)中存在錨點(diǎn)定位傳感節(jié)點(diǎn),鄰居定位傳感節(jié)點(diǎn)和未定位傳感節(jié)點(diǎn)三類(lèi)傳感節(jié)點(diǎn)。其中,錨點(diǎn)定位傳感節(jié)點(diǎn)是根據(jù)錨點(diǎn)提供的4個(gè)以上參考位置信息,獲知自身位置的傳感節(jié)點(diǎn)。該傳感節(jié)點(diǎn)的定位位置較準(zhǔn)確。鄰居定位傳感節(jié)點(diǎn)是根據(jù)錨點(diǎn)和已定位傳感節(jié)點(diǎn)的4個(gè)以上參考位置信息,獲知自身位置的傳感節(jié)點(diǎn)。由于鄰居傳感節(jié)點(diǎn)的位置信息存在一定的誤差,因此鄰居定位傳感節(jié)點(diǎn)的定位位置誤差較大。未定位傳感節(jié)點(diǎn)是未知自身位置坐標(biāo)的傳感節(jié)點(diǎn)。如圖2所示,當(dāng)移動(dòng)錨點(diǎn)移動(dòng)到一個(gè)停留位置(xr,yr,zr)后,在每一個(gè)停留位置周?chē)恢?(xr＋dmax/2,yr＋dmax/2,zr＋3dmax/4),位置2(xr＋3dmax/4,yr＋dmax/2,zr＋dmax/2),位置3(xr＋dmax/2,yr＋3dmax/4,zr＋dmax/2),位置4(xr＋dmax/2,yr＋dmax/2,zr＋dmax/4)四個(gè)位置上停留,發(fā)送自身的ID、位置坐標(biāo)等信息,其中dmax表示節(jié)點(diǎn)最大通信半徑。未定位傳感節(jié)點(diǎn)接收到參考位置信息包后,首先讀取其位置信息和鏈路通信的RSSI(received signal strength indication)值。接著采用Kalman濾波器降低信號(hào)噪聲,并根據(jù)RSSI值計(jì)算當(dāng)前傳感節(jié)點(diǎn)到參考位置的距離。最后傳感節(jié)點(diǎn)獲知4個(gè)以上不共面參考位置坐標(biāo)和到各個(gè)位置的距離,采用極大似然估計(jì)算法(maximum likelihood estimate,MLE)計(jì)算自身的位置坐標(biāo)[14]。

圖2 傳感節(jié)點(diǎn)的定位示意圖

1.2 移動(dòng)錨點(diǎn)的移動(dòng)路徑規(guī)劃

移動(dòng)錨點(diǎn)將整個(gè)監(jiān)測(cè)區(qū)域分成多個(gè)邊長(zhǎng)相同的小正方體網(wǎng)格。首先,移動(dòng)錨點(diǎn)在未探測(cè)的小正方體網(wǎng)格間隨機(jī)移動(dòng),當(dāng)在其通信范圍內(nèi)發(fā)現(xiàn)存在傳感節(jié)點(diǎn)時(shí),則加入傳感節(jié)點(diǎn)所在的連接樹(shù),獲得該連接樹(shù)中所有傳感節(jié)點(diǎn)連接關(guān)系。移動(dòng)錨點(diǎn)為了提供自身的參考位置給所有的傳感節(jié)點(diǎn),需要所有的傳感節(jié)點(diǎn)出現(xiàn)在移動(dòng)錨點(diǎn)停留的任一位置的單跳通信范圍內(nèi)。

圖3 移動(dòng)錨點(diǎn)的移動(dòng)位置選擇

令xj表示傳感節(jié)點(diǎn)j,則兩個(gè)傳感節(jié)點(diǎn)的連接關(guān)系為

式中:L(xj)表示傳感節(jié)點(diǎn)xj所在位置的父節(jié)點(diǎn),link(xj,xk)表示傳感節(jié)點(diǎn)xj和xk的連接關(guān)系。令Path表示移動(dòng)錨點(diǎn)的移動(dòng)路徑,即為傳感節(jié)點(diǎn)的位置集合{p1,p2,…,pi}。pi表示Path中第i個(gè)位置,即傳感節(jié)點(diǎn)j的位置。令link(pi,pi＋1)表示位置pi和pi＋1的鄰居關(guān)系指示符,當(dāng)其為1,則表示位置pi＋1是位置pi上傳感節(jié)點(diǎn)同一個(gè)父節(jié)點(diǎn)單跳通信范圍內(nèi)的其他傳感節(jié)點(diǎn)位置或者其子節(jié)點(diǎn)位置。因此移動(dòng)路徑中的每一個(gè)位置元素需要滿足鄰居位置選擇約束,即為

令C(xj)表示傳感節(jié)點(diǎn)xj是否被覆蓋的指示符。如果為1,則其至少在一個(gè)移動(dòng)錨點(diǎn)的停留位置的單跳通信范圍內(nèi)。為保證移動(dòng)錨點(diǎn)可提供有效的參考位置信息,提高傳感節(jié)點(diǎn)的定位精度,要求所有傳感節(jié)點(diǎn)必須在移動(dòng)路徑任一停留位置的單跳通信范圍內(nèi),則單跳覆蓋范圍約束為

移動(dòng)錨點(diǎn)的移動(dòng)路徑優(yōu)化目標(biāo)是最小化移動(dòng)路徑長(zhǎng)度和定位誤差,即

式中:Len(path)表示移動(dòng)路徑Path的長(zhǎng)度,N1表示移動(dòng)路徑Path中元素的數(shù)量。D表示傳感節(jié)點(diǎn)到移動(dòng)錨點(diǎn)提供的參考位置的平均距離。當(dāng)平均距離較近時(shí),RSSI的誤差較小,其定位精度較高。

由于采用最優(yōu)化理論直接求解優(yōu)化模型(4)的時(shí)間復(fù)雜度較高,無(wú)法適用于計(jì)算資源有限的移動(dòng)錨點(diǎn),因此采用啟發(fā)式算法求解。而海洋捕食者算法(marine predators algorithm,MPA)作為最新的啟發(fā)式算法,通過(guò)模擬布朗運(yùn)動(dòng)和萊維運(yùn)動(dòng)的方式來(lái)尋找最優(yōu)解,比PSO(particle swarm optimization)等傳統(tǒng)算法具有更好的尋優(yōu)精度。但在上述模型中需要針對(duì)移動(dòng)錨點(diǎn)的移動(dòng)路徑進(jìn)行優(yōu)化,若直接采用海洋捕食者算法,則難以執(zhí)行布朗運(yùn)動(dòng)和萊維運(yùn)動(dòng),計(jì)算運(yùn)動(dòng)步長(zhǎng)。因此引入遺傳算法的交叉和變異操作,提出一種混合海洋捕食者算法(hybrid marine predators algorithm,HMPA),將遺傳算法的變異操作認(rèn)為是布朗運(yùn)動(dòng),增加移動(dòng)路徑的多樣性,將遺傳算法的交叉操作認(rèn)為是萊維運(yùn)動(dòng),逐漸靠近最優(yōu)移動(dòng)路徑。

為了尋找到最優(yōu)移動(dòng)路徑,HMPA算法首先從移動(dòng)錨點(diǎn)發(fā)現(xiàn)的未定位傳感節(jié)點(diǎn)開(kāi)始,根據(jù)式(4)從未停留且已定位的傳感節(jié)點(diǎn)中隨機(jī)選擇下一個(gè)停留位置,重復(fù)尋找停留位置直到初始化ξ條移動(dòng)路徑,并判斷每條路徑是否滿足式(3)。如果不滿足式(3),則執(zhí)行移動(dòng)路徑的修正。將符合式(2)和式(3)的移動(dòng)路徑均作為獵物,并通過(guò)式(5)計(jì)算每個(gè)獵物的適應(yīng)度,從中選擇適應(yīng)度最小的獵物作為掠食者。

式中:fi表示獵物i的適應(yīng)度。由于獵物需要在迭代過(guò)程中進(jìn)行不同階段的切換,因此令和分別表示最大迭代次數(shù)的兩個(gè)閾值,且,則每個(gè)獵物的具體更新如下:

①當(dāng)?shù)螖?shù)k≤ρyu1時(shí),由于獵物與最優(yōu)移動(dòng)路徑存在較大差距,因此需要考慮單跳通信范圍內(nèi)的節(jié)點(diǎn)數(shù)量與節(jié)點(diǎn)距離和,執(zhí)行變異操作來(lái)更新獵物,從而增加移動(dòng)路徑的多樣性。首先計(jì)算每個(gè)獵物中移動(dòng)錨點(diǎn)停留位置數(shù)量,并對(duì)其每一個(gè)位置,執(zhí)行如下變異操作:產(chǎn)生一個(gè)[0,1]范圍內(nèi)的隨機(jī)數(shù)。若該隨機(jī)數(shù)小于變異概率κ,則根據(jù)式(6)計(jì)算當(dāng)前位置下一步中可選擇移動(dòng)位置的評(píng)價(jià)值。

式中:scorel表示下一步中第l個(gè)可選擇移動(dòng)位置的評(píng)價(jià)值,nl表示下一步中第l個(gè)可選擇移動(dòng)位置在單跳通信范圍內(nèi)的節(jié)點(diǎn)數(shù)量,el表示下一步中l(wèi)個(gè)可選擇移動(dòng)位置到其單跳通信范圍內(nèi)的節(jié)點(diǎn)距離和,η1表示節(jié)點(diǎn)數(shù)量的權(quán)重參數(shù),η2表示節(jié)點(diǎn)距離和的權(quán)重參數(shù)。根據(jù)式(7)計(jì)算選擇概率,同時(shí)結(jié)合輪盤(pán)賭思想選擇需要插入的移動(dòng)位置。針對(duì)經(jīng)過(guò)上述操作的獵物,保留與原來(lái)獵物相同位置數(shù)量的移動(dòng)路徑,最終獲得新的獵物。

式中:Pl表示下一步中第l個(gè)可選擇移動(dòng)位置的選擇概率,N2表示下一步中可選擇移動(dòng)位置數(shù)量。

同時(shí),在每一次獵物初始化、交叉操作、變異操作等操作后,獵物有可能不滿足約束條件(2)和(3)或存在重復(fù)的移動(dòng)位置,因此需要執(zhí)行以下修正策略:(a)如果獵物存在重復(fù)的移動(dòng)位置,則在路徑中尋找不是首次出現(xiàn)的移動(dòng)位置,并刪除該移動(dòng)位置。(b)如果獵物無(wú)法滿足式(3),則從中選擇一個(gè)鄰居節(jié)點(diǎn)數(shù)量最多的節(jié)點(diǎn),通過(guò)最近鄰插入算法將該節(jié)點(diǎn)加入到已獲知該節(jié)點(diǎn)位置的路徑后[14],直到滿足式(3)。(c)如果獵物中下一跳傳感節(jié)點(diǎn)不在當(dāng)前移動(dòng)錨點(diǎn)的未停留且已定位的傳感節(jié)點(diǎn)中,則根據(jù)式(2)重新初始化1條移動(dòng)路徑進(jìn)行替換,并判斷每條路徑是否滿足式(3)。如果滿足式(3),則完成該連接樹(shù)中所有節(jié)點(diǎn)的覆蓋和移動(dòng)路徑的修正,否則重新執(zhí)行移動(dòng)路徑的修正,直到滿足移動(dòng)路徑的約束。

在完成移動(dòng)路徑修正策略后,考慮到新產(chǎn)生的獵物可能會(huì)比原來(lái)的獵物要差,因此需要執(zhí)行海洋記憶操作,即重新結(jié)合式(5)計(jì)算每個(gè)獵物的適應(yīng)度,從而選擇適應(yīng)度最小的移動(dòng)路徑作為掠食者,并根據(jù)適應(yīng)度從小到大的原則選擇前ξ條獵物作為下一次迭代所需的獵物。為了避免陷入局部最優(yōu)解,需要結(jié)合每個(gè)獵物的適應(yīng)度,根據(jù)式(8)計(jì)算其確認(rèn)值。對(duì)每個(gè)獵物,執(zhí)行以下操作:產(chǎn)生一個(gè)[0,ξ]范圍內(nèi)的隨機(jī)數(shù),其中ξ表示范圍閾值。若該隨機(jī)數(shù)小于確認(rèn)值,則根據(jù)式(2)重新初始化1條移動(dòng)路徑進(jìn)行替換,否則保留該路徑。

式中:τi表示獵物i的值,λ表示適應(yīng)度的權(quán)重參數(shù)。

2 算法實(shí)現(xiàn)

NLA_3D算法是分布式算法,移動(dòng)錨點(diǎn)和傳感節(jié)點(diǎn)各自執(zhí)行不同的步驟。其中,如圖4所示,傳感節(jié)點(diǎn)的具體實(shí)現(xiàn)步驟如下:

步驟1 網(wǎng)絡(luò)啟動(dòng)后,初始化延時(shí)時(shí)間范圍等參數(shù)。

步驟2 傳感節(jié)點(diǎn)隨機(jī)延時(shí)一段時(shí)間。在延遲時(shí)間內(nèi),如果接收到其他傳感節(jié)點(diǎn)的連接樹(shù)組建信息包,則加入到連接樹(shù),將自身ID加入到連接樹(shù)組建信息包中,并廣播發(fā)送更新的連接樹(shù)組建信息包,同時(shí)將自身信息通過(guò)多跳路由發(fā)送給根節(jié)點(diǎn),并接收根節(jié)點(diǎn)的所有傳感節(jié)點(diǎn)的連接信息,跳到步驟4,否則跳到步驟3。

步驟3 沒(méi)有接收到其他傳感節(jié)點(diǎn)的連接樹(shù)組建信息包,則以自身為根節(jié)點(diǎn),發(fā)送包括自身ID等信息的連接樹(shù)組建信息包,收集所有傳感節(jié)點(diǎn)的ID、節(jié)點(diǎn)間距離等連接信息,并廣播通知所有的傳感節(jié)點(diǎn)。

步驟4 監(jiān)聽(tīng)周?chē)?jié)點(diǎn),接收這些節(jié)點(diǎn)提供的位置坐標(biāo),如果接收到的不共面參考位置坐標(biāo)數(shù)量大于3個(gè),則跳到步驟5,否則重新跳到步驟4,繼續(xù)監(jiān)聽(tīng)。

步驟5 采用極大似然估計(jì)算法計(jì)算自身的位置坐標(biāo),并廣播通知移動(dòng)錨點(diǎn)。

如圖5所示,移動(dòng)錨點(diǎn)的具體實(shí)現(xiàn)步驟如下:

圖4 傳感節(jié)點(diǎn)的工作流程圖

步驟1 網(wǎng)絡(luò)啟動(dòng)后,初始化最大迭代次數(shù)K和當(dāng)前迭代次數(shù)k＝1等參數(shù)。將整個(gè)監(jiān)測(cè)區(qū)域分成多個(gè)大小相同的小正方體網(wǎng)格。

步驟2 移動(dòng)錨點(diǎn)從當(dāng)前位置,隨機(jī)探測(cè)未訪問(wèn)的周?chē)≌襟w網(wǎng)格,廣播發(fā)送自身的信息,并將該網(wǎng)格標(biāo)記為已探測(cè)。如果發(fā)現(xiàn)未定位的傳感節(jié)點(diǎn),則與該節(jié)點(diǎn)通信,獲知該傳感節(jié)點(diǎn)所在連接樹(shù)中所有傳感節(jié)點(diǎn)的連接信息,跳到步驟3,否則重新跳到步驟2,繼續(xù)探測(cè)下一個(gè)未訪問(wèn)的周?chē)≌襟w網(wǎng)格。

步驟3 隨機(jī)初始化移動(dòng)路徑。若移動(dòng)路徑不滿足式(3),則執(zhí)行修正策略。同時(shí)通過(guò)式(5)計(jì)算每個(gè)獵物的適應(yīng)度,從中選擇適應(yīng)度最小的獵物作為掠食者；

步驟4 根據(jù)當(dāng)前迭代次數(shù),執(zhí)行全部變異操作、一半變異一半交叉操作和全部交叉操作,更新每一個(gè)獵物。

步驟5 移動(dòng)錨點(diǎn)執(zhí)行移動(dòng)路徑的修正,并通過(guò)式(5)計(jì)算每個(gè)獵物的適應(yīng)度,選擇適應(yīng)度最小的獵物作為掠食者。根據(jù)適應(yīng)度從小到大的原則選擇前ξ條獵物作為后續(xù)操作所需的獵物。

步驟6 移動(dòng)錨點(diǎn)根據(jù)獵物的適應(yīng)度計(jì)算其確認(rèn)值,并根據(jù)其值隨機(jī)選擇獵物,重新初始化該獵物,從而避免陷入局部最優(yōu)解。若當(dāng)前迭代次數(shù)k小于最大迭代次數(shù)K,k＝k＋1,直接跳到步驟4,否則跳到步驟7。

步驟7 移動(dòng)錨點(diǎn)沿著最優(yōu)路徑移動(dòng),獲知當(dāng)前位置周?chē)膫鞲泄?jié)點(diǎn),提供4個(gè)不共面的參考位置,接收鄰居傳感節(jié)點(diǎn)的位置坐標(biāo)。

步驟8 完成最優(yōu)移動(dòng)路徑的移動(dòng),獲知傳感節(jié)點(diǎn)的位置坐標(biāo)后,將傳感節(jié)點(diǎn)所在的正方體網(wǎng)格標(biāo)記為已探測(cè),跳到步驟2。

圖5 移動(dòng)錨點(diǎn)的工作流程圖

3 算法仿真

3.1 仿真參數(shù)和算法性能參數(shù)

在算法仿真中,選擇以下參數(shù)進(jìn)行仿真:三維監(jiān)測(cè)區(qū)域?yàn)?000 m×1000 m×1000 m,正方體網(wǎng)格邊長(zhǎng)為200 m,節(jié)點(diǎn)最大通信距離半徑為250 m,最大迭代次數(shù)為40,不同優(yōu)化階段切換閾值和為13和26,節(jié)點(diǎn)數(shù)量的權(quán)重參數(shù)η1為1,節(jié)點(diǎn)距離和的權(quán)重參數(shù)η2為0.5,變異概率κ為0.3,初始化移動(dòng)路徑數(shù)量ξ為25,適應(yīng)度的權(quán)重參數(shù)λ為2。其中,平均節(jié)點(diǎn)定位誤差定義為所有傳感節(jié)點(diǎn)計(jì)算的自身位置坐標(biāo)和真實(shí)坐標(biāo)的誤差平均值,可表示為:

式中:(xl,c,yl,c,zl,c)表示傳感節(jié)點(diǎn)l通過(guò)算法計(jì)算所得的自身位置坐標(biāo),(xl,r,yl,r,zl,r)表示傳感節(jié)點(diǎn)l的真實(shí)坐標(biāo),ο表示傳感節(jié)點(diǎn)的總數(shù)。已定位傳感節(jié)點(diǎn)個(gè)數(shù)比定義為能計(jì)算自身位置的傳感節(jié)點(diǎn)個(gè)數(shù)與其總個(gè)數(shù)的比值,可表示為:

式中:ζ表示能計(jì)算自身位置的傳感節(jié)點(diǎn)數(shù)量。傳感節(jié)點(diǎn)的平均錨點(diǎn)位置個(gè)數(shù)定義為移動(dòng)錨點(diǎn)沿著其移動(dòng)路徑提供參考位置時(shí),所有傳感節(jié)點(diǎn)可獲知的錨點(diǎn)位置總個(gè)數(shù)和傳感節(jié)點(diǎn)總個(gè)數(shù)的比值,可表示為:

式中:σ表示所有傳感節(jié)點(diǎn)可獲知的錨點(diǎn)位置總個(gè)數(shù)。

3.2 仿真結(jié)果分析

首先,選擇3.1節(jié)中的參數(shù),選擇傳感節(jié)點(diǎn)總數(shù)100,分析NLA_3D算法的收斂性。如圖6所示,NLA_3D算法引入遺傳算法的變異操作和交叉操作,改進(jìn)海洋捕食者算法,在迭代過(guò)程中增加移動(dòng)路徑的多樣性,并可快速趨向于最優(yōu)移動(dòng)路徑,從而提高收斂效率,因此當(dāng)?shù)螖?shù)大于20時(shí),NLA_3D能尋找到最優(yōu)移動(dòng)路徑,其算法是收斂的。

其次,選擇3.1節(jié)中的參數(shù),選擇傳感節(jié)點(diǎn)個(gè)數(shù)100,分別計(jì)算NLA_3D、RAND[12]、GREED[12]、LMPS[13]算法中移動(dòng)錨點(diǎn)的移動(dòng)路徑,獲得如圖7～圖10所示的各個(gè)算法移動(dòng)錨點(diǎn)的移動(dòng)路徑。其中,RAND算法的移動(dòng)錨點(diǎn)選擇正方體網(wǎng)格中心作為下一個(gè)停留位置,GREED算法的移動(dòng)錨點(diǎn)從周?chē)唇?jīng)過(guò)的網(wǎng)格中心中隨機(jī)選擇距離最近的網(wǎng)格中心作為下一個(gè)停留位置,LMPS算法的移動(dòng)錨點(diǎn)采用文獻(xiàn)中的算法獲得移動(dòng)路徑。

圖6 NLA_3D算法的收斂圖

圖7 RAND算法錨點(diǎn)的移動(dòng)路徑

圖8 GREED算法錨點(diǎn)的移動(dòng)路徑

圖9 LMPS算法錨點(diǎn)的移動(dòng)路徑

圖10 NLA_3D算法錨點(diǎn)的移動(dòng)路徑

如圖7所示,RAND算法的移動(dòng)錨點(diǎn)在網(wǎng)格中心間隨機(jī)移動(dòng),其移動(dòng)路徑局限于右下區(qū)域,沒(méi)有遍歷整個(gè)監(jiān)測(cè)區(qū)域。如圖8所示,GREED算法的移動(dòng)錨點(diǎn)只選擇未經(jīng)過(guò)的網(wǎng)格中心,整個(gè)移動(dòng)路徑經(jīng)過(guò)監(jiān)測(cè)區(qū)域,停留位置分布較分散,但是沒(méi)有考慮傳感節(jié)點(diǎn)的分布。如圖9所示,LMPS算法的移動(dòng)錨點(diǎn)按照線性移動(dòng)的方式,從初始位置開(kāi)始,沿著算法規(guī)定的路徑移動(dòng),遍歷經(jīng)過(guò)移動(dòng)路徑上的所有網(wǎng)格中心。如圖10所示,NLA_3D算法根據(jù)傳感節(jié)點(diǎn)的連接信息,建立最小化移動(dòng)路徑長(zhǎng)度和定位誤差的優(yōu)化模型,并采用混合海洋捕食者算法求解模型,獲得最優(yōu)移動(dòng)路徑。該移動(dòng)路徑經(jīng)過(guò)整個(gè)監(jiān)測(cè)區(qū)域,能出現(xiàn)在每一個(gè)傳感節(jié)點(diǎn)周?chē)?為其提供參考位置信息,讓所有傳感節(jié)點(diǎn)都能定位自身位置。

接著,選擇3.1節(jié)中的參數(shù),選擇傳感節(jié)點(diǎn)個(gè)數(shù)100,分析移動(dòng)錨點(diǎn)的移動(dòng)次數(shù)對(duì)未定位傳感節(jié)點(diǎn)個(gè)數(shù)的影響。如圖11所示,隨著移動(dòng)次數(shù)的增加,NLA_3D、RAND、GREED和LMPS算法的未定位傳感節(jié)點(diǎn)個(gè)數(shù)都下降。但是NLA_3D算法在獲知周?chē)鷤鞲泄?jié)點(diǎn)所在的連接樹(shù)信息后,以移動(dòng)路徑長(zhǎng)度和定位誤差作為適應(yīng)度值,并增加移動(dòng)路徑的多樣性,逐漸靠近最優(yōu)移動(dòng)路徑,從而獲得最優(yōu)移動(dòng)路徑。該移動(dòng)路徑有效覆蓋所有的傳感節(jié)點(diǎn),導(dǎo)致其未定位傳感節(jié)點(diǎn)個(gè)數(shù)下降最快,而RAND算法具有隨機(jī)性,LMPS算法按照固定軌跡移動(dòng),GREED算法沒(méi)有考慮傳感節(jié)點(diǎn)分布,因此當(dāng)移動(dòng)次數(shù)大于10次時(shí),NLA_3D的未定位傳感節(jié)點(diǎn)個(gè)數(shù)都小于RAND、GREED和LMPS算法,且其最終趨向于0。

圖11 各算法的未定位傳感節(jié)點(diǎn)個(gè)數(shù)

最后,選擇3.1節(jié)中的參數(shù),傳感節(jié)點(diǎn)80,100,120,140,160,180,200,隨機(jī)分布在三維監(jiān)測(cè)區(qū)域內(nèi),隨機(jī)產(chǎn)生同一傳感節(jié)點(diǎn)數(shù)量下的10個(gè)拓?fù)浣Y(jié)構(gòu),分別計(jì)算NLA_3D、RAND、GREED、LMPS算法的已定位傳感節(jié)點(diǎn)個(gè)數(shù)比、傳感節(jié)點(diǎn)的平均錨點(diǎn)位置個(gè)數(shù)和平均節(jié)點(diǎn)定位誤差,并取其平均值作為仿真結(jié)果值。RAND算法、GREED算法和LMPS算法選擇與NLA_3D算法相同的傳感節(jié)點(diǎn)定位方法。

如圖12所示,不管傳感節(jié)點(diǎn)個(gè)數(shù)如何變化,NLA_3D算法的已定位傳感節(jié)點(diǎn)個(gè)數(shù)比為100%,遠(yuǎn)高于RAND算法、GREED算法和LMPS算法的已定位傳感節(jié)點(diǎn)個(gè)數(shù)比。這是因?yàn)?NLA_3D算法的移動(dòng)錨點(diǎn)獲知周?chē)嬖谖炊ㄎ粋鞲泄?jié)點(diǎn)時(shí),可直接獲知該傳感節(jié)點(diǎn)所在的連接樹(shù)中各個(gè)傳感節(jié)點(diǎn)的連接關(guān)系,并采用混合海洋捕食者算法計(jì)算移動(dòng)錨點(diǎn)的最優(yōu)路徑。該路徑可以讓移動(dòng)錨點(diǎn)移動(dòng)到每一個(gè)傳感節(jié)點(diǎn)的周?chē)?提供參考位置坐標(biāo),從而輔助所有的傳感節(jié)點(diǎn)計(jì)算自身的位置。RAND算法的移動(dòng)錨點(diǎn)路徑具有隨機(jī)性,定位效果較差。GREED算法雖然讓移動(dòng)錨點(diǎn)探測(cè)未經(jīng)過(guò)的區(qū)域,但是沒(méi)有考慮傳感節(jié)點(diǎn)的分布,具有一定的盲目性。LMPS算法按照固定的軌跡移動(dòng),在有限的移動(dòng)距離情況下,其定位到的傳感節(jié)點(diǎn)較少。

圖12 各算法的已定位傳感節(jié)點(diǎn)個(gè)數(shù)比

如圖13所示,NLA_3D算法的平均錨點(diǎn)位置個(gè)數(shù)最多,高于RAND算法、GREED算法和LMPS算法的平均錨點(diǎn)位置個(gè)數(shù)。這是因?yàn)?NLA_3D算法根據(jù)未定位傳感節(jié)點(diǎn)的連接關(guān)系,盡量讓其移動(dòng)錨點(diǎn)停留位置在每一個(gè)傳感節(jié)點(diǎn)的周?chē)?在有限移動(dòng)距離下可覆蓋更多的傳感節(jié)點(diǎn),而其他算法移動(dòng)路徑往往只經(jīng)過(guò)一部分監(jiān)測(cè)區(qū)域或者雖然路徑經(jīng)過(guò)整個(gè)區(qū)域,但是其停留位置分布不合理。

圖13 各算法的傳感節(jié)點(diǎn)的平均錨點(diǎn)位置個(gè)數(shù)

如圖14所示,NLA_3D算法的平均節(jié)點(diǎn)定位誤差最低,小于RAND算法、GREED算法和LMPS算法的平均節(jié)點(diǎn)定位誤差。這是因?yàn)?在NLA_3D算法中,移動(dòng)錨點(diǎn)在探測(cè)監(jiān)測(cè)區(qū)域中,獲知未定位傳感節(jié)點(diǎn)的連接信息后,將傳感節(jié)點(diǎn)到移動(dòng)錨點(diǎn)停留位置的平均距離作為混合海洋捕食者算法的優(yōu)化目標(biāo)之一,在其最優(yōu)移動(dòng)路徑尋找中盡量能出現(xiàn)在每一個(gè)未定位傳感節(jié)點(diǎn)的附近,提供自身較精確的參考位置信息,幫助未定位傳感節(jié)點(diǎn)計(jì)算自身的位置。RAND算法、GREED算法和LMPS算法都沒(méi)有考慮未定位傳感節(jié)點(diǎn)的分布情況,且其傳感節(jié)點(diǎn)的平均錨點(diǎn)位置個(gè)數(shù)較少。

圖14 各算法的平均節(jié)點(diǎn)定位誤差

4 總結(jié)

本文提出一種基于移動(dòng)錨點(diǎn)的三維無(wú)線傳感網(wǎng)節(jié)點(diǎn)定位算法。首先,提出傳感節(jié)點(diǎn)的定位算法,即根據(jù)移動(dòng)錨點(diǎn)或已定位傳感節(jié)點(diǎn)位置,采用極大似然估計(jì)算法計(jì)算自身位置坐標(biāo)。其次,根據(jù)傳感節(jié)點(diǎn)間的無(wú)線通信,提出自組織的連接樹(shù)劃分算法,并考慮移動(dòng)錨點(diǎn)的移動(dòng)路徑選擇,建立最小化移動(dòng)路徑長(zhǎng)度和定位誤差的優(yōu)化模型,并引入遺傳算法思想,提出一種混合海洋捕食者算法(HMPA)求解優(yōu)化模型,獲得移動(dòng)錨點(diǎn)的最優(yōu)移動(dòng)路徑。最后給出算法的仿真參數(shù)和性能參數(shù),比較NLA_3D、RAND、GREED和LMPS算法的性能。

總之,NLA_3D算法是一種分布式算法,可獲得適合當(dāng)前傳感節(jié)點(diǎn)連接關(guān)系的移動(dòng)路徑,從而增加傳感節(jié)點(diǎn)的平均錨點(diǎn)位置個(gè)數(shù),增加已定位傳感節(jié)點(diǎn)個(gè)數(shù)比,降低平均節(jié)點(diǎn)定位誤差。但是NLA_3D算法沒(méi)有考慮移動(dòng)錨點(diǎn)的停留位置選擇對(duì)傳感節(jié)點(diǎn)定位的影響,因此下一階段目標(biāo)是考慮RSSI距離計(jì)算誤差,尋找一種移動(dòng)錨點(diǎn)自身位置坐標(biāo)提供方法,降低傳感節(jié)點(diǎn)的定位誤差。