面向多跳WSNs的基于LSSVR的節(jié)點(diǎn)定位算法*

王自力,鄭 鑫

(1.駐馬店職業(yè)技術(shù)學(xué)院信息工程系,河南 駐馬店 463000;2.黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

面向多跳WSNs的基于LSSVR的節(jié)點(diǎn)定位算法*

王自力1*,鄭 鑫2

(1.駐馬店職業(yè)技術(shù)學(xué)院信息工程系,河南 駐馬店 463000;2.黃淮學(xué)院信息工程學(xué)院,河南 駐馬店 463000)

多跳無(wú)線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)中的多類應(yīng)用均需要準(zhǔn)確的位置信息。為此,提出面向多跳WSNs的基于最小二乘支持向量回歸機(jī)定位算法LSSVR-LA(Least-Squares Support Vector Regression location algorithm)。LSSVR-LA算法先引用轉(zhuǎn)發(fā)區(qū)域概念,并通過(guò)轉(zhuǎn)發(fā)區(qū)域建立測(cè)距模型,然后再利用Secant 算法估計(jì)傳感節(jié)點(diǎn)與錨節(jié)點(diǎn)間距離,最后將這些距離作為L(zhǎng)SSVR輸入,建立了基于LSSVR定位算法模型。最終,估計(jì)未知節(jié)點(diǎn)的位置。實(shí)驗(yàn)數(shù)據(jù)表明,提出的LSSVR-LA算法的定位精度得到有效地提高。

無(wú)線傳感網(wǎng)絡(luò);測(cè)距;Secant 算法;最小二乘支持向量回歸機(jī);定位

隨著無(wú)線通信和低功耗集成技術(shù)的迅速發(fā)展,無(wú)線傳感網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)得到廣泛應(yīng)用。WSNs由微型、低功耗、小電池供電的傳感節(jié)點(diǎn)組成。通常,傳感節(jié)點(diǎn)以隨機(jī)方式分布于監(jiān)測(cè)區(qū)域,進(jìn)而感測(cè)環(huán)境,并收集環(huán)境數(shù)據(jù)[1-4]。

由于能量受限,傳感節(jié)點(diǎn)通常需要以多跳方式將數(shù)據(jù)傳輸至信宿。然而,任何數(shù)據(jù)必須具備相應(yīng)的位置,若離開(kāi)了位置,其數(shù)據(jù)將無(wú)任何意義[5]。因此,估計(jì)傳感節(jié)點(diǎn)位置是多跳WSNs應(yīng)用的基礎(chǔ)。

目前研究人員已對(duì)定位算法進(jìn)行了較深入研究[6-7]。為了更準(zhǔn)確地估計(jì)傳感節(jié)點(diǎn)位置,多數(shù)定位算法要求傳感節(jié)點(diǎn)需至少獲取離3個(gè)錨節(jié)點(diǎn)的距離信息。在多跳WSNs中,多數(shù)傳感節(jié)點(diǎn)難以與錨節(jié)點(diǎn)能直接通信,通常需要利用最短路徑估計(jì)傳感節(jié)點(diǎn)與錨節(jié)點(diǎn)間距離。

現(xiàn)有的定位算法可劃分為測(cè)距定位算法和非測(cè)距定位算法兩類。測(cè)距算法主要包括基于RSSI、到時(shí)時(shí)間ToA等,通過(guò)接收信號(hào)參數(shù),估計(jì)距離。而非測(cè)距定位算法主要是通過(guò)網(wǎng)絡(luò)連通性測(cè)距[7],如DV-HOP技術(shù)[8]。

目前,針對(duì)多跳WSNs的節(jié)點(diǎn)定位,分析算法(Analytical Algorithms)[9-11]得到廣泛應(yīng)用。具體思路:先估計(jì)平均跳距和跳數(shù),它們的乘積作為測(cè)距值。然而,估計(jì)平均跳距存在較大誤差,不同拓?fù)浣Y(jié)構(gòu),平均跳距不同,且差異大。

為此,本文針對(duì)多跳WSNs網(wǎng)絡(luò),提出基于最小二乘支持向量回歸機(jī)定位算法LSSVR-LA(Least-Squares Support Vector Regression location algorithm)。首先,分析了Analytical Algorithms的不足,然后再討論LSSVR-LA算法。LSSVR-LA算法先引入轉(zhuǎn)發(fā)區(qū)域概念,并建立測(cè)距模型,然后由Secant 算法測(cè)距,最后由LSSVR系統(tǒng)估計(jì)傳感節(jié)點(diǎn)位置,實(shí)驗(yàn)數(shù)據(jù)表明,提出的LSSVR-LA算法降低了定位誤差。

1 網(wǎng)絡(luò)模型及問(wèn)題描述

1.1 網(wǎng)絡(luò)模型

圖1顯示了M個(gè)錨節(jié)點(diǎn)和N個(gè)傳感節(jié)點(diǎn)分布于2-D平方區(qū)域S。菱形表示錨節(jié)點(diǎn),正方形表示傳感節(jié)點(diǎn)。錨節(jié)點(diǎn)已知自己位置,而傳感節(jié)點(diǎn)對(duì)自己位置信息未知。假定傳感節(jié)點(diǎn)均勻分布于S。所有錨節(jié)點(diǎn)和傳感節(jié)點(diǎn)具有相同的通信半徑,且表示為R。當(dāng)節(jié)點(diǎn)在自己通信范圍內(nèi)時(shí),節(jié)點(diǎn)就能與其直接通信,否則只能通過(guò)多跳通信。

圖1 網(wǎng)絡(luò)模型

1.2 問(wèn)題描述

本文提出基于錨節(jié)點(diǎn)的傳感節(jié)點(diǎn)定位算法。因此,此類算法要求傳感節(jié)點(diǎn)至少獲取離3個(gè)錨節(jié)點(diǎn)間的距離。為此,每個(gè)錨節(jié)點(diǎn)廣播自己的位置。假定第k個(gè)錨節(jié)點(diǎn)的位置(ak,bk)。如果第i個(gè)傳感節(jié)點(diǎn)離錨節(jié)點(diǎn)距離小于或等于R,它就接收此錨節(jié)點(diǎn)位置,且跳數(shù)nh=1。否則,要以nh≥1跳數(shù)才能收到些錨節(jié)點(diǎn)位置信息。

目前,多數(shù)定位算法均采用,式(1)估計(jì)第i個(gè)傳感節(jié)點(diǎn)離第k個(gè)錨節(jié)點(diǎn)的距離di,k:

(1)

式中:hav為預(yù)定平均跳數(shù)尺寸。

實(shí)際上,式(1)依賴于密集的WSNs,且依賴于式(2)的成立:

(2)

式中:h表示第個(gè)跳距離。

然而這類算法存在不足。通常,有兩種算法計(jì)算hav。第一種就是通過(guò)泊松限制理論的分析[9-11],如hav=E{h};第二種是利用錨節(jié)點(diǎn)間短路徑計(jì)算均值:

(3)

式中:nk,表示第k個(gè)和第個(gè)錨節(jié)點(diǎn)間的跳數(shù)。很明顯,hav并不等于跳距均值,即

因此,跳距可能存在誤差,這降低了定位精度。為此,本文通過(guò)尋找更準(zhǔn)確的hav,進(jìn)而提高定位精度。

2 LSSVR-LA

LSSVR-LA算法先利用Secant算法測(cè)距,然后引用LSSVR定位算法估計(jì)未知節(jié)點(diǎn)位置。

2.1 基于Secant測(cè)距

首先引用變量:轉(zhuǎn)發(fā)區(qū)域F。假定Dk(R)和Di(R)分別表示第k個(gè)錨節(jié)點(diǎn)和第i個(gè)傳感節(jié)點(diǎn)的通信區(qū)域,如圖2所示。

圖2 轉(zhuǎn)發(fā)區(qū)域示意圖

而第k個(gè)錨節(jié)點(diǎn)與第i個(gè)傳感節(jié)點(diǎn)間的轉(zhuǎn)發(fā)區(qū)域F等于它們通信區(qū)域的交集,即F=Dk(R)∩Di(R)。位于F內(nèi)的節(jié)點(diǎn)負(fù)責(zé)將消息從第k個(gè)錨節(jié)點(diǎn)轉(zhuǎn)發(fā)至第i個(gè)傳感節(jié)點(diǎn)。

從圖2可知,轉(zhuǎn)發(fā)區(qū)域F依賴于錨節(jié)點(diǎn)ak與傳感節(jié)點(diǎn)si的距離di,k。接下來(lái),通過(guò)轉(zhuǎn)發(fā)區(qū)域F估計(jì)di,k。

從圖2可知,距離di,k越大,轉(zhuǎn)發(fā)區(qū)域F越小。利用解析幾何和三角轉(zhuǎn)換,可計(jì)算轉(zhuǎn)發(fā)區(qū)域F:

(4)

圖3 兩跳轉(zhuǎn)發(fā)HELLO包的示意圖

(5)

(6)

2.2 錨節(jié)點(diǎn)信息廣播

錨節(jié)點(diǎn)周期地廣播HELLO包,其包含了錨節(jié)點(diǎn)位置和跳數(shù)以及距離項(xiàng)。假定錨節(jié)點(diǎn)ak的坐標(biāo)位置為(xk,yk),其跳數(shù)和距離值分別表示為n、d。n和d的初始值均為零。

當(dāng)傳感節(jié)點(diǎn)接收來(lái)自錨節(jié)點(diǎn)廣播的HELLO包后,首先確認(rèn)之前是否已接收同樣的包。若沒(méi)有,則存儲(chǔ)該錨節(jié)點(diǎn)位置信息和跳數(shù),并估計(jì)距離,再將跳數(shù)加1,將估計(jì)距離加入HELLO包,再轉(zhuǎn)發(fā)出去。如果已接收HELLO包,則將已存在的跳數(shù)nold和現(xiàn)在所接收的跳數(shù)n進(jìn)行比較。如果nold大于n,則更新nold,即nold←n。否則,對(duì)HELLO包不進(jìn)行任何處理,直接轉(zhuǎn)發(fā)。處理HELLO包流程圖,如圖4所示。

圖4 處理HELLO包的流程圖

2.3 最小二乘支持向量回歸機(jī)LSSVR定位算法

在獲取與錨節(jié)點(diǎn)間的測(cè)距信息后,再利用LSSVR估計(jì)節(jié)點(diǎn)位置。LSSVR算法定位步驟如下:①先估計(jì)樣本網(wǎng)格節(jié)點(diǎn)離錨節(jié)點(diǎn)距離;②利用距離與樣子節(jié)點(diǎn)坐標(biāo)間關(guān)系,建立回歸模型;③利用式(6)估計(jì)的距離作為L(zhǎng)SSVR的輸入,其輸出就為未知節(jié)點(diǎn)位置。LSSVR的定位算法框圖如圖5所示。

圖5 基于LSSVR的定位算法流程圖

LSSVR定位算法主要由核函數(shù)選取、樣本節(jié)點(diǎn)位置的抽樣、樣本集的訓(xùn)練、定位模型的建立、測(cè)距和定位6個(gè)階段組成。

首先,引用徑向基函數(shù)RBF(Radial Basis Function)作為核函數(shù)[12],定義如式(7)所示:

(7)

(8)

第五步,測(cè)距。利用式(6)進(jìn)行測(cè)距,并作為L(zhǎng)SSVR的輸入;

最后,定位。將已估算的距離數(shù)據(jù)輸入到LSSVR,系統(tǒng)輸出則為傳感節(jié)點(diǎn)位置估計(jì)值。

3 仿真與分析

本小節(jié)分析LSSVR-LA定位算法性能。在定位區(qū)域A=100 m×100 m內(nèi)隨機(jī)分布100個(gè)傳感節(jié)點(diǎn),錨節(jié)點(diǎn)數(shù)M從10～50變化,通信半徑R從15 m～50 m變化。為了更好地分析LSSVR-LA性能,選擇基于粒子群優(yōu)化的加權(quán)質(zhì)心定位算法RSSI-WP[13]和基于RSSI差分校正的最小二乘-擬牛頓定位算法[14]進(jìn)行參照。

同時(shí),選擇歸一化平均定位誤差作為性能指標(biāo),其定義如式(11)所示。

(9)

圖6 歸一化平均定位誤差

①錨節(jié)點(diǎn)數(shù)對(duì)歸一化平均定位誤差的影響

假定通信半徑R=30 m,錨節(jié)點(diǎn)數(shù)從10～50變,步長(zhǎng)為5 m,實(shí)驗(yàn)數(shù)據(jù)如圖6所示。

從圖6可知,歸一化平均定位誤差隨錨節(jié)點(diǎn)數(shù)增加而下降。原因在于:錨節(jié)點(diǎn)數(shù)越多,獲取的距離信息越多,這越有利于提高定位精度。與RSSI-WP和RSSI-DLN相比,LSSVR-LA算法的歸一化平均定位誤差分別下降了近28%～36%、16%。這主要是因?yàn)?LSSVR-LA算法通過(guò)Secant迭代算法提高了測(cè)距精度,并利用LVSSR算法進(jìn)行定位,通過(guò)訓(xùn)練樣本,提高了定位精度。而RSSI測(cè)距易受外界環(huán)境影響,誤差較大。

②通信半徑R對(duì)歸一化平均定位誤差的影響

本小節(jié)分析通信半徑R對(duì)歸一化平均定位誤差的影響,且錨節(jié)點(diǎn)數(shù)為20,通信半徑R從15 m～50 m變化,實(shí)驗(yàn)數(shù)據(jù)如圖7所示。

圖7 歸一化平均定位誤差隨節(jié)點(diǎn)通信半徑的變化曲線

從圖7可知,歸一化平均定位誤差隨通信半徑呈U型變化趨勢(shì)。當(dāng)通信半徑處于較小區(qū)間時(shí),通信半徑的增加有利于提高定位精度,降低誤差。而當(dāng)通信半徑R大于30 m后,半徑的增加反而提高了歸一化平均定位誤差。從圖7可知,當(dāng)R=33 m時(shí),歸一化平均定位誤差最低。此外,與RSSI-WP和RSSI-DLN相比,LSSVR-LA算法的定位精度得到提高。與RSSI-WP算法相比,LSSVR-LA算法的歸一化平均定位誤差下降了近36%。

③算法復(fù)雜度

為了表述算法復(fù)雜度,記錄了算法運(yùn)行時(shí)間。在同等條件下,算法運(yùn)行時(shí)間越長(zhǎng),復(fù)雜度越高。3個(gè)算法的運(yùn)行時(shí)間如表1所示,其中R=30 m,錨節(jié)點(diǎn)數(shù)為35。從表1可知,LSSVR-LA算法的定位誤差最低,但運(yùn)行時(shí)間并非最低,略高于RSSI-WP。原因在于:LSSVR-LA算法需要采集樣本,并對(duì)樣本進(jìn)行訓(xùn)練,這增加了運(yùn)行時(shí)間。

表1 算法的運(yùn)行時(shí)間

4 總結(jié)

針對(duì)多跳無(wú)線傳感網(wǎng)絡(luò)的定位問(wèn)題,提出基于最小二乘支持向量回歸機(jī)定位算法LSSVR-LA。LSSVR-LA算法先分析了傳統(tǒng)的多跳測(cè)距的不足,然后利用Secant算法測(cè)距,最后由LSSVR估計(jì)傳感節(jié)點(diǎn)位置。通過(guò)定位精度和算法復(fù)雜度實(shí)驗(yàn),實(shí)驗(yàn)數(shù)據(jù)表明,LSSVR-LA算法提高了多跳WSNs的定位精度,并沒(méi)有增加算法復(fù)雜度。后期,將進(jìn)一步提高定位精度,并優(yōu)化算法,降低算法復(fù)雜度。

[1] 李娟,劉禹,錢志鴻,等. 基于雙通信半徑的傳感器網(wǎng)絡(luò)DV-Hop定位算法[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版),2014,44(2):502-508.

[2] 金純,葉誠(chéng),韓志斌. 無(wú)線傳感器網(wǎng)絡(luò)中DV-Hop定位算法的改進(jìn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì),2013,34(2):401-405.

[3] 王新生,趙衍靜,李海濤. 基于DV-Hop算法的改進(jìn)研究[J]. 計(jì)算機(jī)科學(xué),2011,38(2):76-78.

[4] Lachowski R,Pellenz M E,Penna M C,et al. An Efficient Distributed Algorithm for Constructing Spanning Trees in Wireless Sensor Networks[J]. Sensors,2015,15(1):1518-1536.

[5] Tomic S,Mezei I. Improved DV-Hop Localization Algorithm for Wireless Sensor Networks[C]//Process IEEE 10th Jubilee Int Symp Intell Syst Inform,2012:389-394.

[6] Elgamel M S,Dandoush A. A Modified Manhattan Distance with Application for Localization Algorithms in Ad-Hoc WSNs[J]. Ad Hoc Netw,2015(33):168-189.

[7] Zou D B,Wang Y B. Adaptive Energy-Aware Routing Framework in Transmission Cost Constrained Wireless Sensor Networks[C]//Proc IEEE Global Commun Conf(GLOBECOM),2013:534-538.

[8] 張佳,吳延海,石峰,等. 基于DV-Hop無(wú)線傳感網(wǎng)絡(luò)定位算法[J]. 計(jì)算機(jī)應(yīng)用,2010,30(2):323-326.

[9] Huang B,Yu C,Anderson B D O,et al. Estimating Distances Via Connectivity in Wireless Sensor Networks[J]. Wireless Commun. Mobile Comput,2014,14(5):541-556.

[10] El Assaf A,Zaidi S,Affes S,et al. Efficient Range-Free Localization Algorithm for Randomly Distributed Wireless Sensor Networks[C]//Proc IEEE GLOBECOM,Atlanta,GA,USA,2013:201-206.

[11] El Assaf A,Zaidi S,Affes S,et al. Range-Free Localization Algorithm for Heterogeneous Wireless Sensor Networks[C]//Proc IEEE WCNC,Istanbul,Turkey,2014:2805-2810.

[12] 張曉蓮,唐加山. 基于改進(jìn)RSSI測(cè)距的LSSVR三維WSN定位算法[J]. 電視技術(shù),2014,38(19):131-135.

[13] 王新芳,張冰,馮友兵. 基于粒子群優(yōu)化的改進(jìn)加權(quán)質(zhì)心定位算法[J]. 計(jì)算機(jī)工程,2012(1):90-92.

[14] 程秀芝,朱達(dá)榮,張申,等. 基于RSSI差分校正的最小二乘法-擬牛頓定位算法[J]. 傳感技術(shù)學(xué)報(bào),2014,27(1):123-128.

王自力(1978-),男,漢族,河南駐馬店人,碩士,副教授,研究方向?yàn)橛?jì)算機(jī)應(yīng)用及物聯(lián)網(wǎng)技術(shù);

鄭鑫(1977-),女,漢族,河南駐馬店人,碩士,副教授,研究方向?yàn)橛?jì)算機(jī)應(yīng)用及物聯(lián)網(wǎng)技術(shù)。

Least-SquaresSupportVectorRegression-BasedLocalizationAlgorithminMulti-HopWirelessSensorNetworks*

WANGZili1*,ZHENGXin2

(1.Department of Information Engineering,Zhumadian Career Technical College,Zhumadian He’nan 463000,China;2.Information Engineering Institute,Huanghuai University,Zhumadian He’nan 463000,China)

In multi-hop wireless networks,location based applications require an accurate localization algorithm. Therefore,Least-Squares Support Vector Regression-based Localization Algorithm(LSSVR-LA)is proposed in this paper. LSSVR-LA introduces a forwarding area,and construct ranging model by forwarding area. Then,the distance between sensors and anchor nodes are estimated by Secant algorithm. The distance is used as the input vector of LSSVR machine,and localization model-based LSSVR is constructed. Numerous simulation results show that LSSVR-GF-RSSI algorithm reduces at least 12% in average localization error compared with traditional localization algorithm.

wireless sensor network;ranging;secant algorithm;least-squares support vector regression;localization

TPT393

A

1004-1699(2017)11-1747-05

項(xiàng)目來(lái)源:河南省高等學(xué)校青年骨干教師計(jì)劃項(xiàng)目(2015GGJS-300)

2017-04-05修改日期2017-07-17

10.3969/j.issn.1004-1699.2017.11.022