基于改進加權最小二乘支持向量機的UWSN定位

蔣 華，蔡 晨，王慧嬌，王 鑫,

(1.桂林電子科技大學 計算機信息與安全學院，廣西 桂林 541004；2.桂林電子科技大學 海洋工程學院，廣西 桂林 541004)

0 引言

由于地球資源不斷地消耗，世界各國對海洋資源日漸重視[1]。水下無線傳感器網絡(UWSN,underwater wireless sensor networks)在環境監測、災難預報、軍事防御等方面都具有重要的作用，而以上都需要建立在知道精確節點位置信息的基礎之上[2]。但水下環境的復雜性給水下無線傳感器網絡定位帶來了很多挑戰[3]。因此水下節點定位成為了一個亟需解決的問題。

近年研究人員與科研機構提出了許多新的節點定位算法。金磊磊[4]等基于傳統水下測距定位算法，利用最小二乘法提出適用于UWSN的多模態信息融合定位算法，有效提高節點定位精度。Ezzati[5]等基于無線傳感器網絡中的接收信號強度(RSSI)，利用深度學習、極限學習機和自動編碼器高級提取的特征來提高定位性能，可以顯著提升節點定位精度。吳艷玲[6]提出一種根據鄰居節點局部網絡塊的節點定位算法，與機器學習領域中的降維方法相結合有效解決無線傳感器網絡在錨節點密度低下定位精度低的問題。朱芳[7]等提出了基于快速支持向量機的大規模定位算法，通過引入相似性度量來構造最小跨度，分類速度明顯提高，且有效地解決了邊界問題和覆蓋孔問題。毛科技[8]等提出一種基于支持向量機“一對一”節點定位算法，通過引入分類思想來解決節點稀疏環境下的節點定位。這些算法均在某一方面提高了在未知節點的定位精度，但算法整體缺乏魯棒性和對錨節點較少情況下定位精度的考慮。

針對目前已有的機器學習定位算法，提出基于改進加權最小二乘支持向量機的水下三維節點定位算法(WSTA,underwater 3D node location algorithm based on improved weighted least squares support vector machine)。WSTA算法以加權最小二乘支持向量機為基礎，錨節點與水下空間立方體網格頂點之間的距離向量為訓練集，通過改進的多類別模式識別方法訓練分類模型。將未知節點到錨節點的距離向量作為測試集預測節點坐標類別，最終以立方體網格的質心作為未知節點的預測坐標。

1 系統模型

2 算法實現

2.1 加權最小二乘支持向量機

支持向量機[9](SVM，support vector machine)是由統計學習理論發展而來，可用于解決有效樣本學習問題，受到了越來越廣泛的關注。加權最小二乘支持向量機[10]定位算法是由SVM衍生的一種無線傳感器網絡的定位算法。這種算法求解是線性方程的求解，計算量小，通訊開銷較小可以適用于水下無線傳感器網絡節點定位。

將原SVM的不等式約束問題轉化為等式約束：

s.t.vk=wTφ(xk)+b+ek,k=1,…,N

(1)

其中:φ(xk)為非線性映射函數；b為偏差項；w為權重；ek為隨機誤差；γ為正則化參數。

由于LS-SVM以二次損失函數作為經驗風險，這會導致模型對噪聲特別敏感。因此將誤差變量ek=ak/γ引入權值μk。

構建拉格朗日函數如(2)所示：

(2)

根據KKT條件，將L(w,b,e,a)分別對w,b,e,a求偏導，由此：

(3)

將式(3)代入式(2)中，消去w和ek，可得矩陣等式(4)：

(4)

其中:Vγ為對角矩陣：

(5)

權值μk是根據誤差變量ek=ak/γ來確定。

(6)

(7)

其中:IQP是ek的25%與75%分點之間的間距,依照Mercer定理，有映射φ及核函數：

K(xk,xn)=φ(xk)Tφ(xN)

(8)

得出相應的判別函數為：

(9)

其中:a與b是通過式(4)計算所得。

由此可見，權值的引入增加了算法的魯棒性與稀疏性，且計算量并沒有增加，十分適合水下節點定位。

2.2 基于改進加權最小二乘支持向量機算法模型

2.2.1 訓練集準備階段

假定錨節點Si(i=1,2,…,k)到所有劃分立方體網格頂點Kj(j=1,2,…,l)的距離設定為hij(Si,Kj)，則錨節點Si到其他所有立方體網格頂點的距離可以組成距離向量：

di[hi1(Si,K1),hi2(Si,K2),…,hij(Si,Kj)]

對于水下三維環境節點坐標求解，需要對3個維度上的坐標進行分別求取。因此以水下環境為基礎建立坐標軸，將X、Y、Z方向上的三維空間等分為M個類別，因此X軸上存在M個分類{cx0,cx1,…,cxM-1}。假定每一個分類中包含該分類上的所有節點坐標。同理，Y、Z上同樣存在M個類別{cy0,cy1,…,cyM-1}、{cz0,cz1,…,czM-1}。此時水下無線傳感器網絡已經被我們分解成若干個立方體，每一個立方體便代表著算法中的一個類別，錨節點的類別記為[cxq,cyt,czv]。

錨節點的距離向量di與坐標類別構成訓練集：

Tx={(di,cxq)|i=1,2,…,k}

Ty={(di,cyt)|i=1,2,…,k}

Tz={(di,czv)|i=1,2,…,k}

2.2.2 核函數選取

支持向量機算法均需要合適的核函數。本文采用目前應用較多的高斯核函數，又名徑向基(RBF,radial basis function)函數作為核函數：

(10)

RBF核函數可用于線性不可分的情況?？蓪颖居成涞礁呔S的空間，且具有較寬的收斂域以及唯一最佳逼近的特征。因此，RBF函數針對不同維度與大小的樣本均可實現較好的分類效果。

2.2.3 訓練階段

由公式(9)可知判別函數y(x)可用于判斷m1、m2兩類樣本，若y(x)>0，則判x屬于m1類，記m1類一票，否則記錄m2為一票，最后根據樣本得票多的一方作為分類結果。但由于節點分類是一個多分類問題，對于多分類的支持向量機，則需要多個分類器。傳統的“一對一”分類方式需要每兩個類別的數據訓練出一個二分類器，這樣區分M個類別需要的分類器個數為：

P=M(M-1)/2

(11)

為降低運算量，對錨節點訓練集進行判別后，這里使用改進的多類別模式識別方法[11]進行分類。通過這種方法也對類別進行多輪的篩選比較，但相比“一對一”分類方法，該方法每一輪并非將所有類別都進行比較。而是進行單循環相鄰比較，每輪中均去掉得票最低的類別，留下的類別才能參加下輪比較。

如圖2(a)，相鄰的類別進行比較。設C為得票最少的類別，如圖2(b)，在第二輪只將B與D進行比較訓練，其余類別則繼續沿用上一輪的結果。在各個類別兩輪票數相加后，假設B為第二輪得票最少的類別。如圖2(c)所示，去掉B后將A與D作為比較，其他比較仍然沿用原有的結果。

若第三輪本輪累計統計票數后D被淘汰，如圖2(d)，便無需再進行新的比較。只需將之前A與E比較重得票數高的類別作為分類結果。

由此可知，若單個坐標軸方向上有M個類別，除去第一輪需要M次比較，以后每輪僅需一次比較。且由于最后一輪可根據前幾輪投票結果進行判定，最終使用多類別模式識別的分類方法判斷未知節點H的類別需要比較的次數為：

P=2M-3

(12)

由此可見，M的值越大，相比“一對一”投票的分類過程則會愈加簡便。且改進的多類別模式識別的分類方法在不降低精度的情況下減少分類次數，其結果可靠性更好，十分適用水下無線傳感器網絡的節點坐標分類。

2.2.4 測試階段

根據2.2.3節，所有錨節點訓練樣本分類完成且對水下網格類別進行編號，分類模型即構造成功。

根據訓練的模型，將測試集帶入進行預測未知節點的類別編號，并將該類別的質心作為未知節點的坐標，完成定位。

3 基于改進加權最小二乘支持向量機定位

根據多類別模式識別的分類方法對未知節點進行分類，判斷未定位節點的分類信息，從而計算未知節點的坐標信息?；诟倪M加權最小二乘支持向量機的水下三維節點定位算法(WSTA算法)的核心定位流程如下：

3.1 節點定位流程

Step1：將水下立方體環境分割為等大立方體網格，通過RSSI測距算法在每個錨節點內生成到所有立方體頂點的距離向量，生成訓練集。

Step2：在水下環境上建立三維坐標軸，并對坐標軸上的每一格進行分類。以X軸為例，設該維度上存在M個分類。其中每一分類包含X軸上，坐標在[q×D/M,(q+1)×D/M]的所有錨節點，D為區域邊長。同理Y軸與Z軸上的單一分類均包含Y、Z坐標在該分類的所有節點。記節點的分類類別為[cxq,cyt,czv]。

Step3：分別在3個維度上利用錨節點的距離向量作為訓練集來訓練分類器。并使用改進的多類別模式識別的分類方法進行分類。

Step4：根據訓練得到的分類器，將未知節點與所有錨節點之間的距離向量作為測試集預測未知節點類別。

Step5：可得未知節點類別[cxq,cyt,czv]，因此即可判斷未知節點的坐標范圍：[q×D/M,(q+1)×D/M]×[t×D/M,(t+1)×D/M]×[v×D/M,(v+1)×D/M](q,t,v∈[0,M-1])。計算該網格質心坐標，將坐標作為未知節點坐標:((q+2-1)×D/M,(t+2-1)×D/M,(v+2-1)×D/M)。

3.2 定位流程

WSTA算法定位流程如圖3所示。

3.3 節點定位誤差

4 實驗設置與仿真

實驗仿真選擇在Windows 10 PC機上通過MATLAB工具實現基于改進加權最小二乘支持向量機的水下無線傳感器網絡定位方法。對本文的WSTA算法與基于SVM的定位算法[7]和經典RSSI定位算法的平均誤差率進行比較，以及劃分立方體網格寬度t對WSTA算法定位誤差的影響。

仿真區域為邊長分別為80 m、100 m、120 m、140 m、160 m、180 m的正方形區域，隨機部署50個傳感器節點，節點通信距離R為30 m，網絡通信模型為Regular Model，實驗參數如表1所示。

表1 實驗參數設置

設節點預測坐標為(x′,y′,z′)，節點的實際坐標為(x,y,z)。因此節點定位誤差可使用如下公式進行計算：

(13)

4.1 網格寬度對算法平均定位誤差的影響

網格寬度是影響機器學習定位算法的一大因素。圖4展示了在90 M的網絡范圍內WSTA算法和SVM定位算法在不同網格寬度下的平均定位誤差的比較。由仿真實驗結果可知，在傳感器稀薄的水下無線傳感器網絡中，隨著網格寬度的逐漸增大，WSTA算法和SVM定位算法的平均定位誤差均逐漸增大。但在t=12 M時，SVM定位算法的平均定位誤差已經將近30%，增長急速。WSTA算法則較為穩定，且整體定位精度優于SVM定位算法。

4.2 不同定位算法的比較

4.2.1 網絡范圍對平均定位誤差的影響

圖5是RSSI定位算法、SVM定位算法、WSTA算法3種定位算法的平均定位誤差受網絡區域邊長的影響。在范圍廣、節點稀疏的水下無線傳感器網絡中，RSSI定位算法在80～120 m的范圍內較為平緩，但隨著區域邊長變大，定位誤差急劇增加。SVM定位算法定位誤差增長較大，對大范圍環境適應性較差。WSTA定位算法變化較為平緩，對于范圍較大的區域也能保持較好且穩定的定位精度，魯棒性較好。

4.2.2 網絡范圍對平均定位誤差的影響

圖6是RSSI定位算法、SVM定位算法、WSTA算法是3種定位算法的在不同測距誤差下的定位誤差的變化情況。在傳感器節點稀疏的水下無線傳感器網絡中，WSTA算法的節點定位率最高，且節點定位率穩定，優于其他兩種定位算法。在測距誤差為0.05時，SVM定位算法與WSTA算法較為接近，但隨著測距誤差的增加，平均定位誤差急劇增加到最高。WSTA算法在測距誤差0.2時平均定位誤差逐漸趨于平穩，受誤差影響較小。

4.2.3 錨節點比例對平均定位誤差的影響

圖7是RSSI定位算法、SVM定位算法、WSTA算法3種定位算法的在不同錨節點比例時定位誤差的對比情況。在傳感器節點稀疏的水下無線傳感器網絡中，RSSI定位算法在錨節點比例5%時，定位誤差最高。隨著錨節點比例的增加，定位精度急劇提高，逐漸接近于SVM定位算法。WSTA算法在錨節點比例較低時，與SVM定位算法較為接近。在錨節點增長到25%時，定位誤差趨于穩定，整體精度高于其他兩種算法。

在傳感器節點稀疏的水下無線傳感器網絡中，WSTA算法整體平均定位誤差低于SVM定位算法與RSSI定位算法。環境變化對WSTA算法精度影響較低，算法魯棒性高。因此，WSTA算法整體具有較好的定位性能。

5 結束語

本文基于改進加權最小支持向量機提出一種水下三維定位算法。在該算法中，引入加權最小二乘支持向量機的同時通過改進的多類別模式識別方法對節點進行快速分類，提高定位精度與算法魯棒性并降低區域大小對定位精度的影響。將WATA算法與SVM定位算法、RSSI定位算法進行仿真對比，結果證明WATA算法在水下傳感器定節點位中的確實具有較好的魯棒性，能夠有效提升水下節點定位的準確性。