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

趙 娜 劉松迪

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

0 引言

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

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

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

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

1 WSNs節點定位算法

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

(1)

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

(2)

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

(3)

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

傳統RSS測距離通常根據WSNs節點發射和接收的信號的功率差計算[14]，但由于信號傳輸過程中存在多徑效應等干擾存在，傳統RSS測距并不準確，為此，將外界干擾導致的信號衰減合并到距離計算中，即

(4)

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

2 WSN節點分布式定位

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

2.1 子圖內定位算法

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

(5)

式中，dij與dik為WSN網絡中節點間距離。根據節點距離及通信距離權重，改進子圖內節點定位歸結為一個距離誤差加權值的無約束優化問題，其目標函數為：

(6)

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

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

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

圖1 基于RN節點的初始定位示意圖

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

(7)

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

(8)

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

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

(9)

式中，Re{·}為取復數值的實部。根據未知節點的聯通參考節點情況，將真實信號與虛擬像素單元信號重寫為：

(10)

則基于余弦相似性的NRN節點粗定位目標函數可設置為：

(11)

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

(12)

2.3 未知節點迭代精確定位

(13)

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

(14)

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

(15)

(16)

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

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

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

(17)

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

2.4 子圖間定位融合修改

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

圖2 分布式節點定位算法流程圖

3 仿真校驗分析

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

(18)

3.1 RN節點占比對算法性能影響

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

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

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

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

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

圖4 不同通信半徑下的RMSD

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

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

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

4 結束語

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