子圖融合修正WSN節(jié)點分布式定位算法*

趙 娜 劉松迪

遼東學院信息工程學院 丹東 118000

0 引言

隨著航空航天技術(shù)的發(fā)展，航天設(shè)備的高性能、集成化和低功耗等要求以及航天作業(yè)環(huán)境的特殊性，使得傳統(tǒng)有線電纜網(wǎng)絡(luò)通信不僅影響設(shè)備的設(shè)計集成，還給系統(tǒng)的線纜布設(shè)、功耗帶來巨大壓力，無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSNs)技術(shù)的出現(xiàn)恰好迎合航空航天發(fā)展的新需求，為設(shè)備通信、環(huán)境參量與健康狀態(tài)監(jiān)測、信息采集共享與協(xié)同作戰(zhàn)開辟了新的思路[1]。

早在2003年美國在火箭動力系統(tǒng)中提出了分布式傳感器網(wǎng)絡(luò)，這些傳感器能夠?qū)崟r地采集壓力、溫度等信息，并節(jié)點間協(xié)同運算完成檢測與數(shù)據(jù)處理[2]；ESA和 NASA對多種應(yīng)用于航天器WSNs的無線通信協(xié)議進行比較研究，得出適于航天器內(nèi)部WSNs網(wǎng)絡(luò)通信協(xié)議標準[3]；空間CCSDS在進行大量航天器WSNs網(wǎng)絡(luò)技術(shù)的實驗研究后，進一步驗證了該協(xié)議[4]；國內(nèi)在航天器WSN應(yīng)用方面的研究起步較晚，哈爾濱工業(yè)大學等幾個研究所共同設(shè)計了星內(nèi)無線網(wǎng)絡(luò)協(xié)議[5]；中國科學院設(shè)計了一個WSNs到總線的網(wǎng)關(guān)系統(tǒng)，應(yīng)用于航天器內(nèi)的環(huán)境監(jiān)測[6]，并提出1553B-to-ZigBee網(wǎng)關(guān)設(shè)計[7]。目前WSNs已經(jīng)在航天器上廣泛應(yīng)用，以美國為代表的發(fā)達國家已經(jīng)在航天WSNs具體應(yīng)用中取得巨大成果[2]，但我國WSNs在航天航空設(shè)置上的應(yīng)用與研究還有很大差距，為此，航空航天設(shè)備WSNs技術(shù)也是我國現(xiàn)階段航天技術(shù)的研究熱點之一[8]。

實際航空航天應(yīng)用中，節(jié)點感知可靠性及其自身定位精度是關(guān)系網(wǎng)絡(luò)性能的重要指標，因此節(jié)點定位技術(shù)是WSNs在實際航天監(jiān)控、預(yù)報和目標識別等應(yīng)用環(huán)境的技術(shù)基礎(chǔ)，影響著其采集信息的有用價值[9]。為此，僅部分節(jié)點加裝定位模塊，這些節(jié)點被作為位置信息已知的參考節(jié)點(Reference Node, RN)，而其他需實時定位的節(jié)點(Need to be Relocated Node，NRN)則通過最大似然估計等方法借助參考節(jié)點進行實時定位[10]。Kaur等[11]通過集中式的中央服務(wù)器對節(jié)點位置信息進行存儲處理，具有較高的定位精度；葉娟等[12]通過設(shè)置多通信半徑廣播縮小重疊匹配及角度修正改進傳統(tǒng)凸規(guī)劃非測距定位算法；劉偉等[13]將正則項引入半正定規(guī)劃松弛算法中，以減少算法中待優(yōu)化參數(shù)的數(shù)量，同時通過梯度下降對松弛算法的位置信息進行細化；Slavisa等[14]將錐規(guī)劃引入到分布式節(jié)點定位算法中，其每個NRN節(jié)點根據(jù)鄰居位置二階錐規(guī)劃自身定位。Soares等[15]在最大似然估計算法中加入非凸松弛約束來描述節(jié)點定位，并通過共軛梯度法進行快速收斂定位。

在已有算法基礎(chǔ)上，提出子圖劃分融合修正的分布式WSNs節(jié)點定位算法，算法在WSN無向圖劃分的基礎(chǔ)上，首先在子圖內(nèi)通過相位搜索粗定位和遺傳蟻群算法精定位提高單子圖內(nèi)未知節(jié)點的定位精度，然后通過子圖間融合對位置進行修正，從而進一步提高節(jié)點定位精度，仿真實驗驗證了算法的有效性及其對不同規(guī)模的WSN網(wǎng)絡(luò)的適應(yīng)性。

1 WSNs節(jié)點定位算法

WSNs為多跳的自組織傳感器網(wǎng)絡(luò)，通常采用無向圖G來表示，對于N個節(jié)點分布于[0,1]×[0,1]平面內(nèi)的WSNs，其拓撲圖可表示為G=(V,E)，式中，V={v1,v2,…,vN}為傳感器節(jié)點集，其由隨機部署的WSN節(jié)點的位置pi∈Rn決定，V為通信鏈路邊集。

(1)

式中，(xi,yi)與(xj,yj)為參考節(jié)點坐標值，WSNs網(wǎng)絡(luò)的各節(jié)點之間的歐氏距離可近似為

(2)

式中，列矩陣A，B，C和D可由單位矩陣派生，結(jié)合式(1)及RN節(jié)點的最小跳數(shù)nik，WSNs網(wǎng)絡(luò)中的任意NRN節(jié)點k到RN節(jié)點i的距離為dik：

(3)

當RN節(jié)點數(shù)在3個或以上時，通過極大似然估計法或三邊測量可估計出NRN節(jié)點位置。

傳統(tǒng)RSS測距離通常根據(jù)WSNs節(jié)點發(fā)射和接收的信號的功率差計算[14]，但由于信號傳輸過程中存在多徑效應(yīng)等干擾存在，傳統(tǒng)RSS測距并不準確，為此，將外界干擾導(dǎo)致的信號衰減合并到距離計算中，即

(4)

式中，εij和εik為用于描述信號衰減特性的隨機噪聲，其強度由τ∈[0,1]控制。

2 WSN節(jié)點分布式定位

在已有傳感器節(jié)點分布式定位算法[11-12]中，通常為將定位算法分布到各未知參數(shù)節(jié)點中，由節(jié)點根據(jù)其鄰居信息執(zhí)行定位算法，這一方面不能充分發(fā)揮RN節(jié)點的性能，另一方面NRN節(jié)點的獨立計算也增加了對RN節(jié)點的需求量，為此，文中將定位算法執(zhí)行任務(wù)分布到各已知具有計算能力的節(jié)點中，根據(jù)連通和粗測距計算未知節(jié)點的精確位置。

2.1 子圖內(nèi)定位算法

根據(jù)RSS測距原理，傳感器節(jié)點之間通信距離相對越遠，其通信信號受噪聲干擾越大，測距精度相對越低，因此，RSS測得的距離為一個估計值，存在誤差，為此，在計算子圖內(nèi)節(jié)點定位時，主要目標為最小化原始RSS測距誤差，根據(jù)節(jié)點通信距離計算加權(quán)權(quán)重值為：

(5)

式中，dij與dik為WSN網(wǎng)絡(luò)中節(jié)點間距離。根據(jù)節(jié)點距離及通信距離權(quán)重，改進子圖內(nèi)節(jié)點定位歸結(jié)為一個距離誤差加權(quán)值的無約束優(yōu)化問題，其目標函數(shù)為：

(6)

式中，amk與xmi分別表示RN節(jié)點與NRN節(jié)點在子圖Gm中的坐標位置，將節(jié)點歐氏距離計算式dik與dij代入式(6)后，采用初始定位與精確優(yōu)化相結(jié)合的兩步法對目標函數(shù)進行優(yōu)化求解。

2.2 基于相位搜索的初始粗定位

通過節(jié)點拓撲結(jié)構(gòu)設(shè)計，可以保證每個未知信息的節(jié)點領(lǐng)域內(nèi)至少有3個RN節(jié)點，NRN節(jié)點可以接收其領(lǐng)域內(nèi)各節(jié)點的粗位置信息和粗略距離信息。這樣，在進行NRN節(jié)點定位時，根據(jù)粗略位置，選取其領(lǐng)域內(nèi)最接近的3個RN節(jié)點進行初始定位，其定位方法如圖2所示，圖中A、B、C為3個已知信息的節(jié)點，其坐標分別為(xA,yA)、(xB,yB)和(xC,yC)，P為待定位的NRN節(jié)點，設(shè)其坐標為(x,y)。

圖1 基于RN節(jié)點的初始定位示意圖

不失一般性，設(shè)參考節(jié)點信號初始相位均為0，當網(wǎng)絡(luò)中噪聲干擾較少可忽略時，RN與NRN節(jié)點間的連通信號為[12]：

(7)

式中，dn為節(jié)點間物理距離，其可由式(4)給出。由式(7)可見，在不考慮噪聲干擾時，WSNs節(jié)點間信號相位與距離成正比。然而，當根據(jù)實測信號進行相位提取時，受相位纏繞影響，其會被限制在以波長λ為周期的主值(-λ/2,λ/2]內(nèi)，影響未知節(jié)點定位準確性。當參考節(jié)點已知時，WSNs圖任意虛擬像素單元(xi,yi,zi)與參考節(jié)點之間的信號可計算為：

(8)

式中，1≤n≤N，N≥3為未知節(jié)點相聯(lián)通的參考節(jié)點數(shù)，可以看出，在存在噪聲干擾情況下，當WSNs圖中所計算的像素單元與真實未知節(jié)點越接近，計算的信號與真實信號越相似，為此，文中基于余弦相似性建立目標粗定位的目標函數(shù)。

余弦相似性基于向量模型的相似度分析方法，當向量夾角為0時，余弦值為1，兩向量的完全相似。虛擬像素單元的信號相位與真實信號相位的夾角余弦值為

(9)

式中，Re{·}為取復(fù)數(shù)值的實部。根據(jù)未知節(jié)點的聯(lián)通參考節(jié)點情況，將真實信號與虛擬像素單元信號重寫為：

(10)

則基于余弦相似性的NRN節(jié)點粗定位目標函數(shù)可設(shè)置為：

(11)

式中，H為共軛轉(zhuǎn)置符。當且僅當WSNs圖中搜索虛擬單元與NRN節(jié)點重合時，式(11)存在最大值，NRN節(jié)點的粗定位轉(zhuǎn)換為最大化目標函數(shù)的迭代優(yōu)化問題，其初始值設(shè)置為N個聯(lián)通RN節(jié)點的質(zhì)心，即

(12)

2.3 未知節(jié)點迭代精確定位

(13)

1)根據(jù)式(1)和式(4)估計參考節(jié)點的平均跳變及距離，然后根據(jù)粗定位結(jié)果，確定未知節(jié)點的種群可行域，初始種群在該域中隨機生成，則未知節(jié)點坐標(x,y)的上下界為：

(14)

式中，(xi,yi)i∈[1,…,N]為與未知節(jié)點聯(lián)通的參考節(jié)點的坐標。

(15)

(16)

式中:α≥0為路徑參數(shù)，取值為α=1，β≥0為螞蟻的可見性相關(guān)參數(shù)，其值為β=2;τij為t時刻節(jié)點(xi,yi)的殘留信息量;ηij為節(jié)點(xi,yi)可見性，s∈{0,1}為下一選擇狀態(tài)。

3) 蟻群在WSNs的節(jié)點中遍歷，并按式(15)更新各個可行路徑的信息素τij，則遍歷一次后

τij(t+1)=ρ·τij(t)+Δτij

(17)

4)根據(jù)式(15)和式(16)不斷迭代，直接滿足迭代終止條件，則可以得到式(6)最優(yōu)解，即得到未知節(jié)點的精確值。

2.4 子圖間定位融合修改

以無向圖表示的WSN拓撲結(jié)構(gòu)被劃分為多個具有重疊區(qū)域的子圖Gm，各子圖分別計算其NRN節(jié)點定位信息后，對重疊區(qū)域采用子圖節(jié)點均值的方法進一步計算定位信息，以進一步修正NRN節(jié)點位置，并以修正值參與迭代子圖內(nèi)優(yōu)化定位與子圖間融合修正，其整個過程如圖2所示。

圖2 分布式節(jié)點定位算法流程圖

3 仿真校驗分析

為驗證算法的有效性和定位準確性，實驗采用仿真數(shù)據(jù)方法進行算法性能驗證，采用定位距離的均方根(RMSD)[12]作為評價指標，其計算式為

(18)

3.1 RN節(jié)點占比對算法性能影響

為驗證算法在不同節(jié)點占比η=M/(M+N)下的定位性能，實驗中通信半徑dmax=0.60km，實驗中不同占比下各算法得到的RMSD和時間如圖3所示，圖中結(jié)果為多次實驗結(jié)果的平均值。

圖3 不同占比下各算法的RMSD

從圖3實驗結(jié)果可以看出，隨著η增大，松弛SOCP算法的實驗結(jié)果變化最大，且隨著RN節(jié)點占比的增加而減少，而文中算法與凸松弛算法的實驗結(jié)果較為穩(wěn)定，但如果RN節(jié)點過小，初始定位粗差過大，仍會影響文中算法的定位性能。同時算法在仿真實驗過程中取得最小的平均RMSD值，說明文中算法的定位精度更好，這主要是因為文中算法每次迭代尋優(yōu)過程中，計算子圖內(nèi)節(jié)點定位的同時，通過重疊區(qū)域的融合修正不斷提高每次迭代的定位精度，從而保證最終精度最優(yōu)。

3.2 不同通信半徑對算法性能影響

在3.1節(jié)實驗基礎(chǔ)上，固定RN節(jié)點占比η=0.25，分析節(jié)點間的不同通信半徑dmax對算法的定位性能影響，實驗結(jié)果的平均值如圖4～5所示。

圖4 不同通信半徑下的RMSD

圖5 不同通信半徑下的平均定位時間

從圖4～5所示結(jié)果可以看出，dmax的增大，文中算法的RMSD變化不明顯，且始終保持最小值，而另外3種算法的RMSD都有不同程度增大，說明4種算法對通信半徑變化具有較好的適應(yīng)性，而dmax的增大，文中算法及2種凸松弛算法的定位時間隨之增大，這主要是通信半徑增大，節(jié)點間的RSS定位粗差增大，算法需要更多的迭代來彌補，同時節(jié)點的鄰居節(jié)點也增多，通信量以及粗定位計算量也隨之增大，因而定位時間隨之增加。從圖7整體看，在通信半徑dmax<0.25km時，文中算法的定位時間依然最優(yōu)，說明文中算法對RSS計算的粗定位有一定依賴性，實際使用時，應(yīng)避免節(jié)點間通信半徑過大。

綜合實驗結(jié)果可以看出，文中算法在滿足計算要求的情況下，需要較少的RN節(jié)點或設(shè)置較小的通信半徑即可獲得較準確的定位精度。

4 結(jié)束語

針對大規(guī)模WSNs網(wǎng)絡(luò)中節(jié)點的定準效率和定位精度問題，提出基于子圖劃分與圖間融合修正的分布式定位算法，算法在WSNs子圖劃分基礎(chǔ)上，首先在子圖內(nèi)通過相位搜索粗定位和遺傳蟻群算法精定位提高單子圖內(nèi)未知節(jié)點的定位精度，然后通過子圖間融合對位置進行修正，進一步提高節(jié)點定位精度。仿真實驗驗證了算法的有效性及其對不同規(guī)模的WSN網(wǎng)絡(luò)的適應(yīng)性。