,,

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

0 概述

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

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

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

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

1 問題描述

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

如圖1所示,在一個16 m×16 m的室內(nèi),布置8個信標節(jié)點。假設人手持cc2530傳感器,按照下面的軌跡進行移動。移動設備將經(jīng)過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

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

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

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

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

2 相關工作

2.1 流形結構上的正則化半監(jiān)督學習

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

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

(1)

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

基于正則化的最小二乘法半監(jiān)督學習中,最優(yōu)的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等。拉普拉斯映射算法是典型的局部降維算法,在降維的過程中保證數(shù)據(jù)分布的局部結構,降維后數(shù)據(jù)的整體分布發(fā)生變化,但計算復雜度較低。文獻[15]將拉普拉斯映射引入到無線傳感器網(wǎng)絡節(jié)點定位過程中。

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

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

1)構建鄰域圖

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

2)確定鄰域圖的邊權重

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

(4)

否則,Wij=0。

3)拉普拉斯特征映射

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

(5)

3 LP-LapRLS算法

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

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

(6)

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

(7)

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

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

(8)

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

(9)

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

(10)

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

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

LP-LapRLS算法描述如下:

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

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

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

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

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

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

4 仿真及結果分析

4.1 實驗描述

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

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

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

圖2 節(jié)點分布效果圖

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

4.2 實驗結果分析

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

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

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

4.3 參數(shù)對定位的影響

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

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

圖4 參數(shù)γA對定位的影響

圖5 參數(shù)γI對定位的影響

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

5 結束語

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

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

[1] 王福豹,史 龍,任豐原.無線傳感器網(wǎng)絡中的自身定位系統(tǒng)和算法[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二維對數(shù)搜索定位算法[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] 陳 迅,唐紅雨,涂時亮,等.無線傳感器網(wǎng)絡主動分布式節(jié)點定位算法[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的無線傳感器網(wǎng)絡節(jié)點定位算法[J].計算機工程,2015,41(1):82-86.

[11] 顧晶晶.基于局部拓撲結構的無線傳感器網(wǎng)絡定位研究和應用[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.