基于半監督拉普拉斯映射的移動定位算法

,,

(南京航空航天大學 計算機科學與技術學院,南京 211106)

0 概述

微機電系統、數字電子技術和無線通信產業的逐漸成熟促進了無線傳感器網絡(Wireless Sensor Network,WSN)的長足發展。WSN是通過部署大量的傳感器節點至目標區域,形成一個分布式傳感器網絡,自主地感知外部的世界。WSN廣泛地應用于智能交通、環境監控、軍事、醫療衛生等多個領域,其中定位技術是無線傳感器網絡中的研究難點和關鍵技術之一[1]。

典型的無線傳感器定位方式主要分為基于測距和非測距的方式,其中基于測距的定位技術在障礙物少、干擾少,較理想的環境中具有較好的定位精度,應用較為廣泛,主要分為RSSI[2]、TOA[3]、TDOA[4]和AOA[5]等。文獻[6]提出了一種基于RSSI測距的二維對數分布式搜索算法。基于非測距的定位技術無需測量節點間的絕對距離或方位,對硬件依賴低,并且粗精度能滿足實際需求,主要分為DV-Hop[7]、凸規劃[8]、MDS-MAP[9]等。文獻[10]選舉共線度較低的節點作為錨節點,提出了一種分布式協作的DV-Hop算法。

以上這些傳統的定位技術穩定性差、功耗高、需要外部設備的支持或定位精度易受外界環境的影響。近些年,隨著機器學習的發展,學術界提出了眾多基于機器學習的節點定位算法。該類算法首先訓練出信號空間和物理空間的映射模型,然后基于該映射模型對未知節點進行定位[11-12]。基于機器學習的定位算法,定位穩定,且定位精度較高。

本文提出的基于拉普拉斯映射的正則化算法即是機器學習中降維和流形學習的一種。在考慮非信標節點的不足和網絡拓撲結構不斷更新的基礎上,將定位問題放在半監督框架中進行研究。首先在半監督學習中提出流形正則化框架,基于局部光滑性假設對定位在標記樣本上的損失函數進行正則化,防止在建模的過程中,特征值過多,建模效率低。然后在建模的過程中,分析節點的分布符合流形的特點,挖掘網絡的局部空間特性。最后引入高斯核,構建Gram矩陣,更好地反映信號空間的非線性拓撲結構。

1 問題描述

考慮一個二維的節點定位問題,人手持移動設備在一個L×L大小的室內進行移動,室內有n個信標節點布置在預定的位置上,可以周期性地發送和接收信號。在某個時刻ti,移動設備接收到一組向量si=[si1,si2,…,sin]∈n。人手持移動設備按照預定的路線行走結束后,得到一組m×n的信號量矩陣S=T。這里m個n維的向量包括已知節點和未知節點接收的信號向量。

如圖1所示,在一個16 m×16 m的室內,布置8個信標節點。假設人手持cc2530傳感器,按照下面的軌跡進行移動。移動設備將經過A、B、C、D、E、F等點,相應的一個6×8的信號向量矩陣如表1所示。

圖1 移動設備的運動軌跡示意圖

時刻AP1AP2AP3AP4AP5AP6AP7AP8tA-45-36-75-88-92-127-163-192tB-162-129-63-69-73-173-42-123tC-128-89-158-58-51-44-143-48tD-54-24-74-73-79-119-152-183tE-158-80-103-46-39-70-67-42tF-61-26-89-42-51-87-159-143

依據無線傳感器網絡流形的局部拓撲結構,信號強度和物理坐標之間存在著潛在的相關聯系,一般具有以下3個特性[13]:

1)如果信號空間中不同時刻的信號向量是相似的,則物理空間中2個移動節點的物理坐標是相近的。例如表1中tA和tD時刻2行信號向量是相似的,由圖1可知實際物理位置也是相近的。

2)如果信號空間中2個信標節點接收的信號向量是相似的,則物理空間中2個信標節點部署的位置是相近的。例如在圖1中AP4和AP5節點是相近的,其相應的信號向量也是相似的。

3)如果信號強度值接近于0,則該移動節點與相應的信標節點位置較近。例如圖1中,節點在tD時刻離AP2節點較為接近,可以發現其信號強度值接近于0。

2 相關工作

2.1 流形結構上的正則化半監督學習

現實世界中對于機器學習問題,標記樣本的數量是有限的,而未標記的樣本數據是巨大的,樣本之間存在著潛在的流形結構。假設所有的數據都在高維表示空間的一個低維嵌入子流形上,那么算法可以利用大量的未標記樣本學習出數據的內在結構或規律,并在此基礎上利用少量的標記樣本進行分類或回歸。流形學習是通過學習出隱含在數據中的流形結構和相應的低維坐標來實現對高維數據的非線性約簡。此時未標記樣本能用來提高學習性能,這使得流形上機器學習成為半監督學習的一種研究方法。文獻[14]提出了使用一種新的流形正則化形式,結合有監督的數據和無監督數據,挖掘數據分布的幾何形狀。

在再生核希爾伯特空間HK中,假設存在一個Mercer核K:X×X→R,X→R函數必然存在一個相應的‖‖K。現在給出l個標記和u個未標記的數據(xi,yi),i=1,2,…,l,…,l+u。標準的框架如式(1)所示。

(1)

其中,函數V是平方損失函數,在正則化最小二乘法中函數V可表示為(yi-f(xi))2,在支持向量機中可表示為max[0,1-yif(xi)],γ是控制函數在再生核希爾伯特空間中的過擬合參數。

基于正則化的最小二乘法半監督學習中,最優的f可表示為:

(2)

將式(2)代入式(1)中,可化簡為:

(3)

其中,K是一個(l+u)×(l+u)的Gram矩陣,Kij=K(xi,xj),Y是一個標記的向量,Y=[y1,y2,…,yl+u]T。

2.2 拉普拉斯映射算法

流形結構上的降維算法是近年來的熱門研究領域之一,大量專家學者投入其中研究出眾多的降維算法。降維算法主要分為線性降維算法和非線性降維算法。線性降維算法包括PCA、LDA、LPP等;非線性降維算法基于核,包括ISOMAP、LLE、LE等。拉普拉斯映射算法是典型的局部降維算法,在降維的過程中保證數據分布的局部結構,降維后數據的整體分布發生變化,但計算復雜度較低。文獻[15]將拉普拉斯映射引入到無線傳感器網絡節點定位過程中。

本文提出的基于拉普拉斯映射的正則化定位算法主要分為2個階段:訓練階段和定位階段。在訓練階段中,通過拉普拉斯正則化的最小二乘法對信號空間和物理空間進行擬合,考慮空間中的局部結構特性,訓練出信號空間和物理空間中的映射模型。在定位階段,通過映射模型對未知節點進行位置估計。

假設現在有N個數據樣本,其相鄰的樣本間構成了一個拉普拉斯圖,嵌入映射就通過求解拉普拉斯映射的特征向量得到,算法過程如下:

1)構建鄰域圖

采用k-近鄰算法,如果節點i是節點j的k個近鄰之一,或者節點j是節點i的k個近鄰之一,則認為節點i和j是相連的。遍歷完所有節點,構造好鄰域圖。

2)確定鄰域圖的邊權重

確定點和點之間的權值大小,可以選擇熱核函數來確定,如果節點i和節點j相連,那么它們的權重可設定為:

(4)

否則,Wij=0。

3)拉普拉斯特征映射

在d維空間中用各個樣本的近鄰重構該樣本數據,使任意Xi的近鄰在降維后仍然盡可能靠近Xi,即所有點與其近鄰的距離和最小:

(5)

3 LP-LapRLS算法

在無線傳感器網絡定位機制中,基于流形結構的機器學習逐漸成為熱點之一。節點的定位過程一般分為訓練階段和定位階段,訓練階段主要對少量的已知節點和大量的未知節點進行拉普拉斯正則化分析,訓練出物理坐標到信號空間的映射。定位階段,通過映射對移動的目標進行實時的定位。

在原始的高維空間中,包含冗余信息以及噪音信息,在實際的傳感器定位過程中造成了誤差,降低了定位準確率。本文引入拉普拉斯特征映射,揭示了數據的局部特性,反映了決策函數的平滑性。LP-LapRLS算法主要最優化下列等式:

(6)

考慮流形的結構,對任意的f(xi)有:

(7)

其中,αj是全局的映射函數,K(xi,xj)是半正定核函數。

在復雜的傳感器網絡中,由于路徑損失、障礙物、環境等外部因素的影響,導致采集的數據模型非線性且含有噪聲。一般采用核函數的方法構建模型,使得原始空間中的非線性問題轉變為線性問題進行研究[16]。相比線性核函數、多項式核函數和感知器核函數等,高斯核函數能夠更好地擬合信號空間非線性的結構特性。因此在定位過程中,一般選擇高斯核函數反映信號強度的拓撲結構,如式(8)所示:

(8)

因此形成了一個凸可微的目標函數:

(9)

通過對上式中的α求偏導,得到如下最優解:

(10)

通過不斷地調節參數rA和rI,可以達到更好的定位效果。經過大量的實驗驗證,當參數γA取值在0.03～0.05范圍之間,定位誤差在26%左右;參數γI取值在0.89～1.03范圍之間,定位誤差在25%左右,定位精度達到85%。

在訓練階段,通過式(10)求得信號空間和物理空間的映射模型α。在定位階段,移動節點接收到信號向量si。用模型α對其進行線性變化,求得相鄰節點坐標集合Loc=α×si。通過歐式距離的計算,選出k個最相近的節點,通過質心算法求得未知節點的坐標。

LP-LapRLS算法描述如下:

步驟1采集l個信標節點和u個未知節點,通過k-近鄰的方法構建鄰域圖,計算邊的權重wij。

步驟2計算拉普拉斯矩陣L=D-W。

步驟3選擇一個合適的核函數K(xi,yj),計算Gram矩陣。

步驟4選擇一個合適的參數γA和γI。

步驟5通過式(10)計算映射矩陣α。

步驟6在定位階段,通過映射矩陣α求得未知節點的相鄰節點坐標的集合Loc,通過歐式距離的計算選出k個相鄰的節點,利用質心算法求得未知節點的坐標。

4 仿真及結果分析

4.1 實驗描述

為了驗證算法的有效性,采用一組由香港科技大學提供的數據集對算法進行驗證。實驗由Cross-bow MICA2 傳感器節點構成,其中包括8個AP節點,分別部署在該校大樓的不同位置。每個傳感器節點接收到的信號強度為8維的向量。所有數據均由IBM筆記本電腦鏈接一個外部的無線USB網絡適配器采集得到。

香港科技大學提供的數據集包括2組數據,一組數據為移動節點在不同時刻不同位置采集到的8個AP節點的信號強度值,另一組數據為移動節點對應的物理坐標值,一共均勻采集了2 999個樣本數據,將其中一部分數據用作訓練數據,學習定位模型,其余用作測試數據,計算定位精度。

圖2是從2 999個樣本中隨機選取出1 500個樣本的隨機分布效果圖。香港科技大學的數據集信標節點的位置是固定的,未知節點的位置是隨機的。

圖2 節點分布效果圖

為了進行對比實驗,同時運行了基于相同高斯核函數的LE-LPCCA算法[17]和半監督共定位算法Co-Localization[18],半監督共定位算法采用SVD分解和半監督流形學習對未知節點同時進行定位和修正。實驗環境為Matlab2013a,為了驗證算法的有效性,在數據集中各運行50次,取平均值作為評價的標準。

4.2 實驗結果分析

圖3是訓練樣本集比例分別取20%～80%時,LP-LapRLS算法和LE-LPCCA算法、Co-Localization算法定位精度的對比圖。

圖3 不同的訓練集比例下的誤差對比

由圖3可以看出,LP-LapRLS算法相比于其他2種算法具有較大的優勢,樣本訓練集達到60%時,已經具有較穩定的定位效果,定位精度在84%左右。隨著樣本訓練集的增加,定位結果更加穩定。LE-LPCCA算法在訓練樣本集達到60%時,定位精度可達82%以上,定位精度較高。但是訓練樣本集較低時,相比Co-Localization算法和LP-LapRLS算法,定位精度較差,因為LE-LPCCA算法并沒有充分地利用非信標節點對定位模型進行修正。Co-Localization采取了雙重定位進行目標位置的確定,當已知的信標節點較少時,具有較大的優勢,相比其他2種算法,提高了3～5個百分點。對于Co-Localization算法,當訓練樣本集數量較大,定位精度提升減緩。主要由于定位過程中奇異值分解和流學習的雙重定位,不能充分地反映節點的拓撲結構,影響了定位的準確度。

4.3 參數對定位的影響

在LP-LapRLS算法中,參數γA和γI的選擇對傳感器節點的定位精確度有著重要的影響。文獻[14]通過大量的仿真實驗論證了當γA=0.031 25和γI=1時,拉普拉斯映射更加符合無線傳感器網絡的流形結構。

在圖4和圖5中,訓練樣本集比例均為60%,信標節點樣本的數量l為500,非信標節點的樣本數量u為1 000。在圖4中,假設γI為1,設置不同的值,觀察參數γA對定位誤差的影響。同時,在圖5中設置γA=0.031 25,觀察參數γI對定位誤差的影響。

圖4 參數γA對定位的影響

圖5 參數γI對定位的影響

由圖4可知,當參數γA取值在0.03～0.05范圍之間,定位誤差在26%左右,定位精度達到最高。隨著參數的不斷增大,估計位置逐漸偏離出真實物理位置。由圖5可知,當參數γI取值在0.89～1.03范圍之間,定位誤差在25%左右,定位精度達到85%。參數取值接近于0,對定位精度影響較大,因為映射模型的修正幾乎可以忽略不計,等同于用少量的信標節點通過質心算法求未知節點的坐標。

5 結束語

本文提出的算法綜合考慮了非信標節點信息和無線傳感器網絡結構的局部信息,將節點定位問題轉化為半監督回歸問題,建立了信號空間和物理空間之間的映射模型。通過對香港科技大學數據集進行仿真實驗表明,LP-LapRLS算法相比于同類算法精確度和穩定性更加優異。

本文在建立預測模型的過程中,并沒有考慮外部環境的影響,例如溫度、濕度或者節點的非正常死亡等,不能動態地自適應現場的環境。下一步的工作是建立一個動態自適應的預測模型。

[1] 王福豹,史 龍,任豐原.無線傳感器網絡中的自身定位系統和算法[J].軟件學報,2005,16(5):857-868.

[2] DANG Xiaochao,HEI Yili,HAO Zhanjun.An Improved Indoor Localization Based on RSSI and Feedback Correction of Anchor Node for WSN[C]//Proceedings of International Conference on Computer,Information and Telecommunication Systems.Washington D.C.,USA:IEEE Press,2016:1-5.

[3] TAHERI M,MOTAMEDI S A.Transceiver Optimization for ToA-based Localization of Mobile WSN[J].Journal of Circuits System & Computers,2016,25(9).

[4] RAN Qiu,FENG Renjian,YU Ning,et al.A Weighted Least Squares Source Localization Algorithm Using TDOA Measurements in Wireless Sensor Networks[C]//Proceedings of the 6th International Conference on Electronics Information and Emergency Communication.Washington D.C.,USA:IEEE Press,2016:10-13.

[5] MOHAPATRA S,BEHERA S,TRIPATHY C R.A Comparative View of AoA Estimation in WSN Positioning[M].Berlin,Germany:Springer,2015.

[6] 朱 莉,顧能華,姚英彪,等.基于RSSI的WSN二維對數搜索定位算法[J].計算機工程,2014,40(4):87-90.

[7] GUI Linqing,VAL T,WEI A,et al.Improvement of Range-free Localization Technology by a Novel DV-hop Protocol in Wireless Sensor Networks[J].Ad Hoc Networks,2014,24(2):55-73.

[8] 陳 迅,唐紅雨,涂時亮,等.無線傳感器網絡主動分布式節點定位算法[J].計算機工程與設計,2008,29(7):1664-1667.

[9] ZHOU C,XU T,DONG H.Distributed Locating Algorithm MDS-MAP (LF) Based on Low-frequency Signal[J].Computer Science & Information Systems,2015(12):55.

[10] 王景琿.一種基于DV-Hop的無線傳感器網絡節點定位算法[J].計算機工程,2015,41(1):82-86.

[11] 顧晶晶.基于局部拓撲結構的無線傳感器網絡定位研究和應用[D].南京:南京航空航天大學,2011.

[12] 張興福.基于流形學習的局部降維算法研究[D].哈爾濱:哈爾濱工程大學,2012.

[13] PAN J J,PAN S J,YIN Jie,et al.Tracking Mobile Users in Wireless Networks via Semi-supervised Colocali-zation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(3):587-600.

[14] BELKIN M,NIYOGI P,SINDHWANI V.Manifold Regularization:A Geometric Framework for Learning from Labeled and Unlabeled Examples[J].Journal of Machine Learning Research,2004,7(1):2399-2434.

[15] PAN J J,YANG Qiang,CHANG Hong,et al.A Manifold Regularization Approach to Calibration Reduction for Sensor-network Based Tracking[C]//Proceedings of National Conference on Artificial Intelligence.New York,USA:ACM Press,2006:988-993.

[16] 孫艷娜.基于2DPCA的人臉識別方法[D].西安:西安電子科技大學,2013.

[17] GU Jingjing,CHEN Songcai.Manifold-based Canonical Correlation Analysis for Wireless Sensor Network Localization[J].Wireless Communications & Mobile Computing,2012,12(15):1389-1404.

[18] PAN J J,PAN S J,YIN Jialin,et al.Tracking Mobile Users in Wireless Networks via Semi-supervised Colocalization[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2012,34(3):587-600.