基于偏最小二乘的無線傳感網(wǎng)多跳定位算法

竇如林,閻 浩,嚴筱永

(1.金陵科技學(xué)院軟件工程學(xué)院,江蘇 南京 211169;2.金陵科技學(xué)院智能科學(xué)與控制工程學(xué)院,江蘇 南京 211169)

基于偏最小二乘的無線傳感網(wǎng)多跳定位算法

竇如林1,閻 浩1,嚴筱永2

(1.金陵科技學(xué)院軟件工程學(xué)院,江蘇 南京 211169;2.金陵科技學(xué)院智能科學(xué)與控制工程學(xué)院,江蘇 南京 211169)

提出了一種基于偏最小二乘的多跳定位算法(ML-PLS)。算法借助偏最小二乘對已知節(jié)點間的跳數(shù)與真實距離的建模,通過跳數(shù)、距離兩者間的最大協(xié)方差共同推動節(jié)點位置的估計。ML-PLS算法對復(fù)雜部署環(huán)境具有較強的適應(yīng)性,克服了傳統(tǒng)算法只適用于各向同性網(wǎng)絡(luò)的不足。仿真結(jié)果表明,ML-PLS算法定位精確度高且性能較穩(wěn)定,并能適應(yīng)不同網(wǎng)絡(luò)環(huán)境。

多跳定位;無線傳感器網(wǎng)絡(luò);偏最小二乘

無線傳感器網(wǎng)絡(luò)[1-2](Wireless Sensor Network,WSN)是一種綜合了傳感器技術(shù)、嵌入式計算機技術(shù)、現(xiàn)代網(wǎng)絡(luò)及無線通信技術(shù)、分布式信息處理等技術(shù)的新一代網(wǎng)絡(luò)技術(shù)。與以往的網(wǎng)絡(luò)不同,無線傳感器網(wǎng)絡(luò)是一種以數(shù)據(jù)為中心的網(wǎng)絡(luò),因而數(shù)學(xué)統(tǒng)計、多元分析方法是傳感網(wǎng)中常見的問題解決手段。隨著無線傳感器網(wǎng)絡(luò)技術(shù)快速的發(fā)展,傳感器網(wǎng)絡(luò)的應(yīng)用越來越多,在各種應(yīng)用中,檢測到事件后一個重要問題就是該事件發(fā)生的位置。文獻[3]中統(tǒng)計,約80%的上下文感知信息與節(jié)點位置有關(guān),在許多傳感器網(wǎng)絡(luò)應(yīng)用中節(jié)點的位置信息起著關(guān)鍵性的作用。

目前,根據(jù)定位過程中是否用到距離測量技術(shù)可以粗略地將定位分為:基于測距定位方法和基于非測距定位方法[4-5]。基于測距的定位方法通過測量節(jié)點間的距離或方位獲取未知節(jié)點的位置,該方法定位精度高,但容易受溫度、障礙物等環(huán)境因素的影響,且測量半徑受到所帶電量限制,因此,不適合大規(guī)模定位?；诜菧y距定位方法大都是基于節(jié)點之間的連接關(guān)系(多跳關(guān)系),在假設(shè)跳數(shù)與單跳距離之間存在某種函數(shù)映射關(guān)系之上來估計節(jié)點的位置。該方法思想簡單,易于實現(xiàn),對硬件要求相對較低,非常適合大規(guī)模場景下的定位應(yīng)用。然而,與眾多關(guān)鍵技術(shù)一樣,在實際應(yīng)用中非測距多跳定位技術(shù)性能仍然受到諸多技術(shù)難題困擾,其中最致命的是多跳定位僅能在節(jié)點密度高且分布均勻的各向同性網(wǎng)絡(luò)取得較理想的定位結(jié)果,而在節(jié)點分布不均、稀疏等網(wǎng)絡(luò)環(huán)境各向異性的情況下,定位效果極差。

針對多跳定位所存在的問題,提出一種更符合實際環(huán)境下使用且計算復(fù)雜度相對較低、定位精度較高、適應(yīng)能力更強的多跳定位方法,即ML-PLS(Multihop Localization-Partial Least Squares)。ML-PLS方法嘗試利用傳感網(wǎng)本身的拓撲結(jié)構(gòu)與自身特性來進一步提高定位算法的性能,使其適應(yīng)不同的環(huán)境。

1 相關(guān)研究

近年來,借助多元分析對定位機制進行建模和算法設(shè)計已成為研究熱點之一[6-7]。該方法利用已知節(jié)點分布特性與測量信息之間的對應(yīng)關(guān)系,關(guān)聯(lián)并構(gòu)建一個映射模型,而后應(yīng)用該模型估計出未知節(jié)點的位置。多元分析與以往方法相比較,能有效地挖掘出數(shù)據(jù)背后所隱含的網(wǎng)絡(luò)拓撲結(jié)構(gòu)、相關(guān)性等信息。Lim等人提出了一種采用TSVD(Truncated Singular Value Decomposition)技術(shù)對跳數(shù)與真實距離建模的PDM(Proximity Distance Map)定位算法[8]。PDM方法首先將采集到的已知節(jié)點間路徑的物理距離和測量距離分別用矩陣進行標(biāo)示,而后通過TSVD方法對兩個矩陣進行線性轉(zhuǎn)換獲得一個最優(yōu)線性轉(zhuǎn)換模型,再將未知節(jié)點到信標(biāo)節(jié)點的最短跳數(shù)帶入模型,進而估計出未知節(jié)點到信標(biāo)節(jié)點的物理距離。TSVD[9]實質(zhì)上是一種線性多元規(guī)則方法,利用其獲得估計距離實質(zhì)上是未知節(jié)點所關(guān)聯(lián)的已知節(jié)點估計值的加權(quán)和,因此獲得估計值與真實值較為接近;此外TSVD方法舍棄了較小奇異值,在一定程度上減少噪聲在轉(zhuǎn)換過程的影響,從而達到避免定位中的共線性問題,增加算法的穩(wěn)定性。PDM方法能夠在一定程度上解決節(jié)點分布不均、網(wǎng)絡(luò)拓撲各向異性等原因造成的定位精度不高問題。但PDM方法仍然存在3方面的不足:1)TSVD是通過設(shè)置一個閾值k直接將奇異值中小于閾值k的設(shè)置為0,如果k值選擇合理,TSVD的解穩(wěn)定,反之則會使算法性能下降;2)PDM方法未對跳數(shù)與真實距離進行標(biāo)準(zhǔn)化處理,不同的量綱造成一定程度數(shù)據(jù)淹沒現(xiàn)象;3)TSVD建模只考慮跳數(shù)信息而未顧及真實距離信息,使獲得的模型并不能真正反應(yīng)跳數(shù)與真實距離的關(guān)系。Lee等人[10]受到PDM方法啟發(fā),提出了基于SVR的定位方法——LSVR,該定位方法能夠適應(yīng)不同網(wǎng)絡(luò)環(huán)境,且在小樣本情況下仍然能獲得較好的定位精度。但基于支持向量機(Support Vector Machines,SVM)回歸方法是一種多輸入單輸出算法[11],在實際定位中需多次建模,使得算法復(fù)雜度急劇上升,且隨著信標(biāo)節(jié)點數(shù)量的增大,定位計算所需的時間和空間資源都會成幾何級數(shù)增長。為了降低定位問題的復(fù)雜性,提高定位方法的泛化性能,簡化定位模型,非常有必要在構(gòu)建模型前對數(shù)據(jù)進行特征提取。研究人員發(fā)現(xiàn),偏最小二乘(Partial Least Squares,PLS)[12-13]方法能很好地實現(xiàn)輸入到輸出的特征提取。

PLS是一種將輸入變量與輸出變量投影到相應(yīng)的低維特征空間,在分別得到正交特征向量后,利用最大協(xié)方差共同決定預(yù)測方向。PLS預(yù)測性能強,適合處理小樣本數(shù)據(jù)、自變量之間的多重共線,抗噪能力強預(yù)測精度高且具有較好的泛化能力,PLS方法無需事先獲知樣本的分布模型,它又被稱為第2代回歸方法。本文借鑒PLS和普通的多跳定位算法(Ordinary Multihop Localization,OML)原理,將兩者相結(jié)合,提出一種新非測距定位方法,即ML-PLS。方法通過收集和利用實際距離和節(jié)點間跳數(shù)信息,關(guān)聯(lián)并構(gòu)建其間的最優(yōu)關(guān)系(模型),并用此模型預(yù)測未知節(jié)點到已知節(jié)點距離。

2 偏最小二乘法簡介

偏最小二乘法是一種基于數(shù)學(xué)優(yōu)化的多元統(tǒng)計數(shù)據(jù)分析方法,由S.Wold和C.Albano[13]在1983年首先提出。PLS將多元線性回歸、主成分分析和典型相關(guān)分析有機地結(jié)合起來。PLS在進行回歸之前,利用協(xié)方差指導(dǎo)輸入變量和輸出變量的特征選取,由于在選取過程中采用了信息綜合和篩選技術(shù),因此PLS方法不僅有效克服輸入變量的相關(guān)性,從而消除了共線性問題對回歸的影響,而且在回歸時強調(diào)輸入對輸出的解釋和預(yù)測作用,因而去除了對回歸無益的噪聲,使得PLS方法具有更好的魯棒性和預(yù)測穩(wěn)定性。由于PLS方法總是將多元回歸問題轉(zhuǎn)化為若干個一元回歸問題,因此它還具有適應(yīng)小樣本的特性,正是由于有如此多的優(yōu)良特性,使其非常適合傳感網(wǎng)的定位。

線性PLS方法是綜合考慮輸入變量P和輸出變量L,通過迭代的方法對成分t、u(t是變量P的線性組合,u是變量的L線性組合)進行求解,原理見圖1。

圖1 偏最小二乘原理Fig.1 Partial least squares

從圖1可以看到,P與L之間的交叉協(xié)方差是很重要的一個信息,希望通過k對潛在變量對來刻畫這種交叉協(xié)方差,因此,PLS求解需要滿足:1)t和u應(yīng)盡可能地攜帶各自數(shù)據(jù)表中的變異信息;2)t和u的相關(guān)程度能夠達到最大。PLS表述為優(yōu)化問題的解

其中,w,c是權(quán)向量。

PLS算法的基本步驟如下:

1)首先對輸入、輸出變量進行標(biāo)準(zhǔn)化處理(包括減均值,初標(biāo)準(zhǔn)差等),以便消除輸入輸出變量的不同量綱對最終計算結(jié)果產(chǎn)生的影響;

2)分別從輸入、輸出變量P、L提取第1個主成分t1和u1,根據(jù)回歸需要,需滿足:

a)t1和u1,應(yīng)盡可能地攜帶變量P、L中的變異信息,即,使得t1和u1的方差最大:Var(t1)→max, Var(u1)→max;

b)t1和u1間的相關(guān)程度能夠達到最大,即,使得t1和u1的自相關(guān)達到最大:Corr(t1,u1)→max;

c)綜合a)和b)得到優(yōu)化目標(biāo),即,使得t1和u1的協(xié)方差達到最大

3)在第一個成分t1和u1提取后,分別實施P、L對t1上的回歸。如果回歸方程已經(jīng)達到滿意的精度,則PLS方法終止;否則,將利用P被t1解釋后的殘差以及L被u1解釋后的殘差進行第2輪的成分提取。如此往復(fù),直到提取所有的自變量成分和因變量成分。

4)偏最小二乘的預(yù)測并不需要選擇全部成分,一般僅需前k個成分,常用的成分選擇方法有交差檢驗法和經(jīng)驗法等。

在實際應(yīng)用中,數(shù)據(jù)受到很多不穩(wěn)定因素的干擾,其中不僅包含數(shù)量較多、幅度較小的測距誤差(隨機噪聲),還包含少量幅度較大的測距誤差(奇異點或粗差),偏最小二乘方法僅僅能消除隨機噪聲的干擾,而對粗差卻無能為力。為此,在偏最小二乘法中添加了異常值監(jiān)測步奏,即:

5)在確定成分個數(shù)后,獲得一成分表,隨后計算每個樣本點對k成分的累計貢獻率。根據(jù)實際情況設(shè)定判斷閾值Thre,并將貢獻率高于Thre的樣本點確定為異常。根據(jù)特雷西等人的研究[14],累計貢獻率服從以下分布:

3 ML-PLS節(jié)點定位模型建立

基于PLS方法的節(jié)點定位分兩個階段:訓(xùn)練階段和定位階段。在訓(xùn)練階段通過對已知節(jié)點間跳數(shù)和物理距離學(xué)習(xí)訓(xùn)練出測量到真實距離的映射,建立定位模型;在定位階段,未知節(jié)點通過它到信標(biāo)節(jié)點的跳數(shù),運用訓(xùn)練得出的映射模型對未知節(jié)點進行位置估計。

從式(3)易知,P中的變量間也會存在嚴重的多重相關(guān)性或者P中的樣本點數(shù)目少于變量個數(shù)情況,此時對等式(3)強行計算,估計結(jié)果將失效。此外,估計值η^的精度不僅僅與輸入變量相關(guān),還與輸出變量L有關(guān),輸入與目標(biāo)兩者共同決定著η^的預(yù)測方向。

偏最小二乘是一種集多元回歸、典型性相關(guān)分析和主成分分析于一體的多元數(shù)據(jù)分析方法,它利用輸入與輸出協(xié)方差指導(dǎo)特征的選擇,能很好適應(yīng)真實情況的建模和預(yù)測。將PLS運用到多跳定位方法中,能夠適應(yīng)不同的定位場景且能獲得較高好定位精度。此時,利用PLS對跳數(shù)-真實距離建模過程可被歸納為以下算法(ML-PLS定位方法),其步驟如下:

輸入:知節(jié)點跳數(shù)矩陣P=[p1,p2,…,pm];相應(yīng)真實距離矩陣L=[l1,l2,…,lm],預(yù)測設(shè)定的主元

初始化u:u=li,其中,li是L中的任意一列向量;

計算P的權(quán)值向量w:w=PTu;

歸一化t:t=Pw,t←t/‖t‖;

·屬性定位策略。這種定位策略主要是依據(jù)服務(wù)活動本身的特點來進行定位。它更多地是因為活動設(shè)計本身具有一定的特色或者與其他類似服務(wù)的差異化而采取的策略。

計算L的權(quán)值向量c:c=LTt;

歸一化u:u=Lc,u←u/‖u‖;

已收斂與其真值,則可以執(zhí)行步驟7;否則轉(zhuǎn)至步驟2,進行第k+1次迭代;

縮小矩陣P,L:P←P-t tTP,L←L-t tTL

根據(jù)式(2)判斷數(shù)據(jù)中是否存在粗差,并加以處理;

4 ML-PLS的性能驗證

非測距定位方法重要的特點之一是非常適合大規(guī)模部署,這就需要部署成百上千的傳感器節(jié)點,而在目前的實驗條件下很難實現(xiàn)如此大規(guī)模的真實網(wǎng)絡(luò)。因此,在大規(guī)模非測距模節(jié)點定位算法的研究中,通常采用軟件仿真的方式來評價定位算法的優(yōu)劣。

本節(jié)通過仿真實驗來分析和評價ML-PLS算法的性能。仿真在Matlab平臺上進行,所有的編碼都采用Matlab語言編寫。實驗考慮兩種節(jié)點部署策略:規(guī)則部署和隨機部署。對于信標(biāo)節(jié)點,假設(shè)它們均勻地部署在被檢測的區(qū)域內(nèi)。為了降低一次實驗結(jié)果的片面性,每種部署實驗都進行了50次仿真,每次試驗里節(jié)點都將重新隨機分布在實驗區(qū)域,取50次平均誤差的開方(RMS)[15]的均值作為評價依據(jù)。

此外,本節(jié)的實驗針對上文提出的基于PLS的定位算法、OML、基于TSVD的PDM定位算法和基于SVM回歸的定位算法進行了比較。由于TSVD方法需要設(shè)定舍棄特征值門限;LSVR方法需要設(shè)定核參數(shù)、懲罰系數(shù)C和不敏感損失函數(shù)的寬度ε,為了公平起見,實驗中TSVD方法設(shè)舍去特征值小于等于3相對應(yīng)的特征向量;LSVR方法的C和ε設(shè)置參照文獻[16],而核函數(shù)本文選擇高斯核函數(shù)[12],其核函數(shù)與訓(xùn)練樣本的距離有關(guān),因此核參數(shù)設(shè)為訓(xùn)練樣本均值的40倍。

4.1 規(guī)則部署

在這組實驗中,分別有441個和333個節(jié)點規(guī)則地部署在600×600的正方形區(qū)域或C形區(qū)域內(nèi)(方形區(qū)域內(nèi)置一個300×260障礙物),實驗在這些節(jié)點中選取30到40個節(jié)點作為信標(biāo)節(jié)點。首先,考察兩個ML-PLS方法的最終定位結(jié)果(圖中信標(biāo)節(jié)點數(shù)為36),如圖2所示,圓圈表示未知節(jié)點,方塊表示信標(biāo)節(jié)點,直線連接未知節(jié)點的真實坐標(biāo)和它的估計坐標(biāo),直線越長,定位誤差越大。

圖2 規(guī)則部署定位結(jié)果Fig.2 The positioning results of rule deploy

圖3描述的是規(guī)則部署網(wǎng)絡(luò)中信標(biāo)節(jié)點數(shù)量對定位精度的影響。理論上在監(jiān)測區(qū)域內(nèi)信標(biāo)節(jié)點越多,定位誤差越小。由圖3顯示的結(jié)果可以看出,OML的RMS值最大且曲線上下起伏,其它3種方法的RMS值隨著信標(biāo)節(jié)點數(shù)目的增加而單調(diào)遞減,且本文所提出ML-PLS方法定位精度最高。此外,還可以看出ML-PLS和LSVR方法在兩種部署區(qū)域內(nèi)的RMS曲線值相差不大,而其余方法相差較大,這也說明ML-PLS和LSVR方法具有較強的環(huán)境適應(yīng)能力,能夠適應(yīng)網(wǎng)絡(luò)拓撲的各向異性。由于PLS是多元回歸方法,因此在計算過程中考慮了節(jié)點間的相關(guān)性,所以定位精度更高。從圖3還可以看出ML-PLS隨信標(biāo)節(jié)點數(shù)量增加單調(diào)遞減,但這種趨勢非常弱,這也就說明了信標(biāo)節(jié)點數(shù)量對其精度影響小,ML-PLS方法適應(yīng)少信標(biāo)節(jié)點環(huán)境,從圖中可以看出在兩種規(guī)則部署區(qū)域內(nèi),ML-PLS方法的平均定位性能分別相對于LSVR方法提高17.6%和10.5%。

4.2 隨機部署

在這組實驗中,500個節(jié)點隨機地部署在600×600的二維正方形區(qū)域C內(nèi),并從這450個節(jié)點中規(guī)則地選取30到40個節(jié)點作為信標(biāo)節(jié)點。圖4顯示的是含有36信標(biāo)節(jié)點某次ML-PLS方法在兩種形狀下隨機部署的定位結(jié)果。

圖3 規(guī)則部署RMS曲線Fig.3 The RMS curve of rule deploy

圖4 隨機部署定位結(jié)果Fig.4 The positioning results of random deploy

圖5描述的是隨機部署網(wǎng)絡(luò)中,信標(biāo)節(jié)點的數(shù)目和RMS誤差的關(guān)系。同規(guī)則部署一樣,OML的RMS值最大且曲線上下起伏,且在C形區(qū)域定位誤差大于方形區(qū)域,這都說明OML方法不穩(wěn)定,對網(wǎng)絡(luò)拓撲的各向異性明感。PDM方法雖然去除了部分小特征值相對應(yīng)的數(shù)據(jù),但由于舍棄都是人為設(shè)定,且未考慮跳數(shù)和真實距離量綱問題,雖定位精度較OML方法有所改進,但改進力度較小。LSVR方法與本文所提及的方法定位精度較為接近,但由于LSVR是一種多輸入單輸出方法,對于構(gòu)建跳數(shù)與真實距離這樣的矩陣關(guān)系,它顯得有些力不從心,LSVR方法需要多次建模隨經(jīng)過優(yōu)化但未考慮數(shù)據(jù)間的相關(guān)性,因此基于LSVR方法定位精度低于本文所提出的ML-PLS方法。從圖5可以看出,ML-PLS方法相對于ML-PLS方法性能分別平均提高了3.3%和6.6%。

圖5 隨機部署RMS曲線Fig.5 The RMS curve of random deploy

5 結(jié) 語

本文提出了一種非測距定位方法——ML-PLS,該方法通過構(gòu)建跳數(shù)與真實距離關(guān)系,建立測量距離與物理距離的模型,可以有效的處理無線傳感器網(wǎng)絡(luò)中拓撲結(jié)構(gòu)復(fù)雜的問題,同時通過貢獻率的判斷算法能有效的鑒別出粗差數(shù)據(jù)。與同類算法相比,ML-PLS算法不僅繼承了OML方法的優(yōu)點,通過仿真實驗表明在多種部署環(huán)境下,ML-PLS算法都能夠取得較高的定位精度,并且受信標(biāo)節(jié)點數(shù)目的影響較小。

[1]Emary I M M E,Ramakrishnan S.Wireless Sensor Networks:from Theory to Applications[M].United Kingdom:CRC Press,2013

[2]Khan S,Pathan A-S K,Alrajeh N A.Wireless Sensor Networks Current Status and Future Trends[M].United Kingdom: CRC Press,2013

[3]周艷.智能空間中定位參考點的優(yōu)化選擇及誤差分析[D].沈陽:東北大學(xué),2009

[4]Sand S,Dammann A,Mensing C.Positioning in Wireless Communications Systems[M].[s.l.]:wiley,2014

[5]Liu Y,Yang Z.Location,Localization,and Localizability Location-awareness Technology for Wireless Networks[M]. [s.l.]:Springer,2011

[6]陳祠,牟楠,張晨,等基于主成分分析的室內(nèi)指紋定位模型[J].軟件學(xué)報,2013,24(s1):98-107

[7]Afzal S,Beigy H.ALocalization Algorithm for Large Scale Mobile Wireless Sensor Networks:a Learning Approach[J]. The Journal of Supercomputing,2014,69(1):98-120

[8]Lim H,Hou J C.Distributed Localization for Anisotropic Sensor Networks[J].ACM Transactions on Sensor Networks (TOSN),2009,5(2):1-26

[9]Hogben L.Handbook of Linear Algebra[M].United Kingdom:CRC Press,2007

[10]Lee J,Chung W,Kim E.A New Kernelized Approach to Wireless Sensor Network Localization[J].Information Sciences,2013,243(2013):20-38

[11]Vazquez E,Walter E.Multi-output Support Vector Regression[C].13th IFAC Symposium on System Identification,2003: 1820-1825

[12]Shawe-Taylor J,Cristianini N.Kernel Methods for Pattern Analysis[M].London:Cambridge University Press,2004

[13]王桂增,葉昊.主元分析與偏最小二乘法[M].北京:清華大學(xué)出版社,2012

[14]肖磊.異常數(shù)據(jù)檢測及其在神經(jīng)模糊建模中的應(yīng)用[D].廈門:廈門大學(xué),2006

[15]Chen J,Wang C,Sun Y,et al.Semi-supervised Laplacian Regularized Least Squares Algorithm for Localization in Wireless Sensor Networks[J].Computer Networks,2011,55(10):2481-2491

[16]Cherkassky V,Ma Y.Practical Selection of SVM Parameters and Noise Estimation for SVM Regression[J].Neural Networks 2004,17:113-126

(責(zé)任編輯:馬金玉)

Multihop Localization Algorithm Based on Partial Least Squares for Wireless Sensor Network

DOU Ru-lin,YAN Hao,YAN Xiao-yong
(Jingling Institute of Technology,Nanjing 211169,China)

An improved multihop localization algorithm(ML-PLS)based on partial least squares is proposed.This algorithm uses the partial least squares to build the localization model of hop-count and the real distances between beacons,and employs the maximun covariance of hop-count matrix and distance matrix to jointly promote the estimation of node location.MLPLS has strong adaptability for complicated deployment environment,and overcomes the shortage of traditional multihop algorithm which is only suitable for isotropic networks.Simulation results show that ML-PLS algorithm has high estimate precision and stable performance,and can adapt to different network environments.

multihop localization;wireless sensor network;partial least squares

TP393.08

A

1672-755X(2014)03-0019-07

2014-09-11

金陵科技學(xué)院博士啟動基金(jit-b-201411)

竇如林(1979-),男,江蘇南京人,實驗師,碩士,主要從事無線傳感器網(wǎng)和信息安全的研究。