子圖劃分優(yōu)化WSN 節(jié)點分布式定位算法

李 斌，趙 娜

（1.東莞職業(yè)技術(shù)學院計算機工程系，廣東 東莞 523808；2.吉林大學計算機科學與技術(shù)學院，吉林 長春 130012）

1 引言

機械振動監(jiān)測及礦井提升機等系統(tǒng)通常采用有線方式傳輸其采集的信息，成本高、靈活性差且監(jiān)測范圍有限，嚴重影響信號傳輸質(zhì)量，對大型設備尤其是旋轉(zhuǎn)部件，在無振動方向及振動狀態(tài)時，限制尤為明顯[1]。隨著物聯(lián)網(wǎng)的發(fā)展和成熟運用，無線傳感器網(wǎng)絡（Wireless Sensor Network，WSN 技術(shù)被應用到提升機等設備檢測和振動監(jiān)測中，并取得良好的效果[2-3]。

WSN 自組織網(wǎng)絡已經(jīng)在環(huán)境監(jiān)測、軍事、地質(zhì)探測及空間探索等方面應用廣泛[3]，節(jié)點定位是WSN 網(wǎng)絡從固定式應用到移動式部署的關鍵技術(shù)之一，節(jié)點定位的準確性及其可靠性關系到網(wǎng)絡的監(jiān)測性能和穩(wěn)定性的重要指標，由于在移動過程中，網(wǎng)絡的拓撲是隨時變化時，傳統(tǒng)基于固定WSN 網(wǎng)絡的節(jié)點定位算法在實際應用中需要頻繁信息交互，并設置繁雜的定位校驗方法以提升定位精確性[4]。因此，WSN 中節(jié)點定位相關技術(shù)的研究對WSN移動部署應用具有重要意義[5]。

文獻[6]采用集中式信息存儲方式進行WSN 節(jié)點定位處理，采用盒式錨區(qū)和三角定位的方式對節(jié)點位置信息進行捕捉，但通信頻繁且適于節(jié)點稀疏環(huán)境下的定位，高密度節(jié)點易產(chǎn)生嚴重的鏈路抖動現(xiàn)象；文獻[7]針對高變化拓撲環(huán)境的快速移動節(jié)點定位問題，通過射頻覆蓋獲取最佳性能錨節(jié)點坐標，通過拉格朗日插值捕捉節(jié)點的軌跡矢量信息，并采用正交覆蓋進行優(yōu)化，取得較好的定位精度；文獻[8]將基于最小二乘的迭代預測引入到移動WSN 錨節(jié)點定位信息采樣中，提高了采樣有效性和定位精確度，對低密度網(wǎng)絡仍取得較好的結(jié)果，但對變化較快節(jié)點定位精度有待提高，以減少算法中待優(yōu)化參數(shù)數(shù)；文獻[9]以新設計的計跳公式計算未知節(jié)點的跳距，再通過最小二乘進行矩陣修正，最后由高斯牛頓法進行非線性方程求解，取得較好的未知節(jié)點定位精度。

分布式定位通過節(jié)點自身的計算進行定位，對計算能力要求不高，相比于依賴中央服務器的集中式定位更適于大規(guī)模WSN 中RNR 節(jié)點的定位[10]，為此，在已有算法基礎上，為減少在大規(guī)模WSN 網(wǎng)絡中已知節(jié)點的需求量，提出了基于誤差加權(quán)和修正的分布式迭代節(jié)點定位算法，算法首先根據(jù)已知節(jié)點領域?qū)SN 無向圖劃分為多個子圖，然后通過子圖內(nèi)定位循環(huán)迭代方法求解NRN節(jié)點的精確位置信息，實現(xiàn)算法的高效精確定位，仿真實驗算法的有效性及對不同節(jié)點規(guī)模的WSN 網(wǎng)絡具有較好的適應性。

2 WSN 節(jié)點定位

以xi=［x2i-1，x2i］和ai=［a2k-1，a2k］分別表示 WSN 平面內(nèi)未知位置節(jié)點LUi和已知位置的節(jié)點LAi的橫縱軸位置坐標，則包含N個已知的參考節(jié)點（Reference Node，RN）x1，x2，…，xN和M個型需實時重新定位的節(jié)點（Need to be Relocated Node，NRN）a1，a2，…，aM的 WSN 節(jié)點集為：

其網(wǎng)絡中兩NRN 節(jié)點M及NRN 節(jié)點與RN 節(jié)點間的歐氏距離可表示為：

式中：A、B、C、D—由單位矩陣生成的列矩陣，通信距離限制使得只有通信半徑內(nèi)的傳感器節(jié)點可互相通信，即互為鄰居節(jié)點，對于一個NRN 節(jié)點vi其未知鄰居節(jié)點集和已知鄰居節(jié)點集為：

式中：ρij、ρik—節(jié)點間直接通信的通信半徑。

無線傳感器網(wǎng)絡可以通過節(jié)點的發(fā)射功率和接收功率差異在無額外測試設備輔助的情況下通過RSS 測距算法計算兩節(jié)點之間的距離，但受多徑及陰影等衰減特性的影響，功率差異測距并不很準確，為此，將衰減特征引入到距離計算，即：

式中：εij、εik—隨機噪聲，即通過隨機噪聲的疊加來描述發(fā)射信號在傳播過程中的衰減特征；τ∈［0，1］—噪聲強度控制因子。降低部署成本和功耗，在保證滿足定位需求情況下，已知參數(shù)的傳感器節(jié)點的部署量通常盡可能減少。

3 節(jié)點分布式定位

以已知具有計算能力的節(jié)點為中心，將與其構(gòu)成鄰居節(jié)點的所有節(jié)點組成圖G的子圖Gm，Gm=（Vm，Em），則M個 RN 節(jié)點可以形成M個子圖，根據(jù)節(jié)點的通信半徑可調(diào)整RN 節(jié)點數(shù)及位置，使得每個NRN 節(jié)點至少落入兩個子圖中，以保證子圖間的有效重疊，從而減少RN 節(jié)點的需求量。

3.1 子圖定位算法

根據(jù)傳統(tǒng)跳距計算試，WSN 的兩節(jié)點間在通信半徑內(nèi)實現(xiàn)正常通信，則計其跳數(shù)為1，但根據(jù)RSS 測距原理，傳感器節(jié)點之間通信距離相對越遠，其通信信號受噪聲干擾越大，測距精度相對越低，傳統(tǒng)計數(shù)方式不合理，為此，將其修改為：

式中：N—WSN 網(wǎng)絡中錨節(jié)點數(shù)量；（xi，yi）、（xz，yz）—錨節(jié)點與未知節(jié)點坐標。根據(jù)修改跳數(shù)計算式，文中子圖內(nèi)節(jié)點定位歸結(jié)為一個距離誤差加權(quán)值的無約束優(yōu)化問題，其目標函數(shù)為：

式（7）的求解可以作為非線性方程組采用高斯牛頓法[9]進行求解，但直接使用高斯牛頓法會由于Dij誤差導致定位精度不高，為此，采用最小二乘對未知節(jié)點到錨節(jié)點距離進行距離修正，修改后的距離計算誤差為：

式中：（xls_z，yls_z）—最小二乘計算的距離值，則經(jīng)過最小二乘修正后的錨節(jié)點距離值為：

根據(jù)式（9）的修正距離計算可以構(gòu)建WSN 網(wǎng)絡中未知節(jié)點xz=（xz，yz）到錨節(jié)點xi=（xi，yi）的距離求解迭代式為：

式中：‖·‖—求矩陣范數(shù)。根據(jù)式（10）可得到修改后的比較精確的節(jié)點距離，則子圖內(nèi)未知節(jié)點定位目標函數(shù)式（7）可以轉(zhuǎn)化最式（11）所示的非線性方程求解問題，即：

式中：dz—最小二乘對式（10）計算的距離值的進一步優(yōu)化值，則未知道節(jié)點的坐標值為：

式中：λ—迭代步長；J—雅克比矩陣。其定位方法，如圖1 所示。圖中A、B、C為三個已知信息的節(jié)點，其坐標分別為（xA，yA）、（xB，yB）和（xC，yC），P為待定位的 NRN 節(jié)點。

圖1 基于RN 節(jié)點的初始定位示意圖Fig.1 Schematic Diagram of Initial Positioning Based on RN Nodes

進而根據(jù)節(jié)點間的位置相對關系，可以求解坐標（x，y）值。可以看出，（x，y）的計算需要最鄰近的三個RN 節(jié)點的RSS 距離信息，但其值不精確，距離誤差的存在使得圖2 中三圓難以保證恰好交于一點，因而其計算的定位坐標僅作為初始值，以便進一步迭代計算更精確值，為避免NRN 節(jié)點內(nèi)僅有兩個RN 節(jié)點情況的存在，將兩RN 節(jié)點中心連線的中點作為精確定位算法的初始值。其計算過程為：

（1）以圖2 所示方法計算NRN 節(jié)點的初始值，即xm.0，設置迭代初始值p=0；

（2）判斷一階參數(shù)是否滿足‖△Jm，p‖＞ε，其中 ε，為一個非常小的值，文中取ε=10-10，如果滿足，則進行一維迭代搜索，并計算搜索步長λp；

（3）判斷p與維度n之間大小：（1）當p＜n時，計算dm，p+1=-△Jm，p+1+βdm，p，其中 βp=‖△Jm，p+1‖2/‖△Jm，p‖2為兩次迭代之間的目標函數(shù)差異，令p：=p+1，轉(zhuǎn)到（2）；（2）當p≥n時，令xm，0=xm，p+1，dm，0=-△Jm，p+1及p=0，轉(zhuǎn)到（2）；

在（2）中，步長 λp應滿足：

令 φ（λ）=J（xm，p+λp dm，p），則 φ（λ）取極小值即時的 λ，為所要計算的 λp。計算式（9）在xm，p+1=xm，p+λpdm，p處的梯度并取△φ（λ）=0，可得到λp值，如式（13）所示。

3.2 分布式算法流程總結(jié)

文中分布式節(jié)點定位算法，通過以RN 節(jié)點為中心構(gòu)建其領域子圖而將整個無線傳感器網(wǎng)絡無向圖劃分為多個子圖，并通過構(gòu)建合適的誤差加權(quán)和目標函數(shù)將節(jié)點定位轉(zhuǎn)換為子圖內(nèi)距離誤差的無約束優(yōu)化問題；在目標函數(shù)迭代優(yōu)化過程中，采用共軛梯度法及粗定位信息作為迭代初始值，以確保算法迭代時以最速方向漸近局部最優(yōu)解。其過程，如圖2 所示。

4 仿真分析

為驗證文中算法有效性，采用定位距離的均方根（RMSD）作為評價指標，采用松弛SOCP 算法[9]、同步凸松弛算法[10]及異步凸松弛算法[10]作為性能比較算法，實驗環(huán)境HQ CPU@2.9G Hz，內(nèi)存32G，仿真軟件為matlab 2016a，WSNs采用正方形區(qū)域，包含M個已知節(jié)點和N個待定位的節(jié)點，添加強度為τ=0.25 的隨機均勻噪聲。

圖2 分布式節(jié)點定位算法流程圖Fig.2 Flow Chart of Distributed Node Positioning Algorithm

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

為驗證文中算法在不同占比下的定位性能，實驗過程中，節(jié)點總數(shù)固定為M+N=800，節(jié)點間的通信半徑設置為固定值dmax=0.30，實驗已知節(jié)點不同占比下各算法得到的RMSD，如圖3 所示。圖中為多次實驗結(jié)果的平均值。

圖3 不同占比下各算法的RMSDFig.3 RMSD of Each Algorithm Under Different Proportions

圖3 距離均方根均值可以看出，隨著η 增大，松弛SOCP 算法的RMSD 變化最為劇烈，一直在在減小，這里算法與凸松弛算法的變化不大，而文中算法的穩(wěn)定性最好，這主要因為算法初始定位時，只需要三個RN 節(jié)點計算初始值即可，而后期則更多領先迭代優(yōu)化，因而節(jié)點比的增大、RN 節(jié)點數(shù)量的增加，對初始定位和后續(xù)迭代優(yōu)化影響不明顯。

4.2 節(jié)點規(guī)模對算法性能影響

固定WSN 中參考節(jié)點比例為η=0.25，不斷增大網(wǎng)絡節(jié)點規(guī)模，分析各算法的定位性能，實驗結(jié)果均值，如表1 所示。

表1 不同節(jié)點規(guī)模下算法的定位性能Tab.1 Localization Performance of the Algorithm

表1 實驗結(jié)果可以看出，文中算法在不同節(jié)點規(guī)模，取得較好的RMSD，這與3.1 和3.2 兩節(jié)實驗結(jié)果相似，而松弛SOCP 算法與凸松弛算法隨著節(jié)點規(guī)模增大，其參考節(jié)點數(shù)據(jù)增多，RMSD 減少，但當節(jié)點達到4000 以上時，由于節(jié)點規(guī)模太大，算法的RMSD 反而開始增大，且凸松弛算法計算量增大而出現(xiàn)定位時間過長或無法定位情況。整體結(jié)果表明，文中算法在大規(guī)模節(jié)點WSN 網(wǎng)絡中，仍能取得較好的定位精度和定位時間。

5 結(jié)語

針對大規(guī)模WSN 節(jié)點定準精度和效率不高的問題，提出子基于誤差加權(quán)和修正的分布式節(jié)點定位算法，算法首先根據(jù)參考節(jié)點鄰域范圍將WSN 無向圖劃分為多個子圖，然后在子圖內(nèi)構(gòu)建距離誤差加權(quán)和目標函數(shù)，以迭代計算節(jié)點位置信息。仿真實驗表明，與現(xiàn)有算法相比，文中算法在較少的參考節(jié)點需求下可以取得最優(yōu)的定位精度和時間，且對不同節(jié)點規(guī)模的WSN 網(wǎng)絡具有較好的適應性。