基于WSN路由節(jié)點度模型的樓宇走廊定位算法*

郝 昭,李曉卉*,丁月民

(1.武漢科技大學信息科學與工程學院,武漢 430081;2. 天津理工大學計算機與通信工程學院,天津 300384)

基于WSN路由節(jié)點度模型的樓宇走廊定位算法*

郝 昭1,李曉卉1*,丁月民2

(1.武漢科技大學信息科學與工程學院,武漢 430081;2. 天津理工大學計算機與通信工程學院,天津 300384)

針對現(xiàn)有的無線傳感器網(wǎng)絡(WSN)定位方法應用于結(jié)構(gòu)復雜的樓宇走廊時,存在定位精度較低的問題,提出一種基于WSN路由節(jié)點度模型的樓宇走廊定位算法。該算法在路由節(jié)點度模型的基礎上,先采用基于支持向量回歸(SVR)的方法,用少量錨節(jié)點定位普通路由節(jié)點,達到間接增加錨節(jié)點覆蓋率的目的;然后采用基于中垂線分割的方法定位隨機分布在區(qū)域內(nèi)的未知節(jié)點和移動終端。仿真表明:與傳統(tǒng)SVR定位算法和核嶺回歸定位算法相比,所提出的算法精度提高了定位精度,滿足室內(nèi)定位精度要求(1 m～3 m),且降低了對錨節(jié)點數(shù)量的需求,可運用于樓宇走廊WSN定位。

無線傳感網(wǎng)絡;距離無關(guān)定位;支持向量回歸;區(qū)域分割;凹形狹長空間

無線傳感器網(wǎng)絡技術(shù)WSN(Wireless Sensor Networks)由于其安裝方便,無須布線,不會對建筑進行任何改動,即插即用,低功耗等特點廣泛應用于智能樓宇中[1]。在商場,倉庫,醫(yī)院,展廳,賓館等樓宇環(huán)境中,走廊是人員頻繁移動的區(qū)域,也是WSN重點監(jiān)測區(qū)域。該區(qū)域的傳感器節(jié)點位置信息對樓宇的相關(guān)智能化服務必不可少。

大型樓宇走廊多為狹長的凹形鏈狀區(qū)域。該環(huán)境中,目前已有室內(nèi)定位方法主要有WiFi,測距RSSI[2]。其中,WiFi定位需要位置服務商頻繁采樣和更新指紋庫;測距RSSI需要在區(qū)域內(nèi)部署大量錨節(jié)點[3],且墻壁阻擋等環(huán)境因素會使信號產(chǎn)生多徑和非視距效應,從而降低其定位精度。WSN的距離無關(guān)定位方法(range-free localization)由于低能耗、低成本,受環(huán)境影響小,近年來受到較大關(guān)注[4]。對于鏈狀WSN,目前提出的距離無關(guān)室內(nèi)定位方法[4]需要覆蓋大量錨節(jié)點,算法復雜度高,且多以直線區(qū)域的WSN為定位算法的研究背景。然而,凹形區(qū)域的WSN具有各向異性[7],該性質(zhì)會大幅降低距離無關(guān)定位方法(如DV-hop等多跳算法)的定位精度[8]。對此,不少學者將機器學習算法引入到多跳定位算法中,如文獻[9]提出了支持向量回歸的方法LSVR和LMSVR,文獻[10]提出了基于核嶺回歸(KRR)的方法。這些算法既提高了各向異性WSN的定位精度,又沒有增加開銷和算法復雜度。

對于可人工布局節(jié)點的場景,較少研究注意到網(wǎng)絡拓撲結(jié)構(gòu)對定位算法的影響。對于走廊環(huán)境,本文設計了一種WSN路由節(jié)點度模型RNDM(Routing Node Degree Model),并在此基礎上提出一種適用于樓宇走廊WSN的距離無關(guān)定位算法RFLC(Range-Free Localization algorithm for WSN in Corridor)。本文將樓宇走廊WSN節(jié)點分為3種類型:錨節(jié)點(位置已知的路由節(jié)點),普通路由節(jié)點(位置未知的路由節(jié)點),未知節(jié)點(隨機分布的移動終端和檢測節(jié)點),在樓宇走廊布置少量錨節(jié)點,并依據(jù)節(jié)點度,在通道兩側(cè)均勻交錯布局普通路由節(jié)點,形成RNDM。RFLC算法分為兩個階段:基于支持向量回歸的普通路由節(jié)點定位RFLC-SVR(RFLC-Support Vector Regression)和基于區(qū)域分割的未知節(jié)點定位RFLC-PB(RFLC-Perpendicular Bisector division)。第一階段,依據(jù)少量錨節(jié)點信息,采用RFLC-SVR算法定位普通路由節(jié)點,進而將這些普通路由節(jié)點晉升為錨節(jié)點,從而間接增加錨節(jié)點的數(shù)量和覆蓋率。第二階段,使用分布式定位算法RFLC-PB定位走廊內(nèi)部的未知節(jié)點和移動終端。仿真證明,該算法降低了對錨節(jié)點數(shù)量的需求,更適應復雜的走廊環(huán)境,且滿足定位精度要求(1 m～3 m)[3]。

1 基于路由節(jié)點度的網(wǎng)絡模型

為了在走廊WSN中傳遞數(shù)據(jù),網(wǎng)絡拓撲邊界上需分布一些路由節(jié)點。當網(wǎng)絡當中沒有監(jiān)測盲區(qū)、達到相同的連通性時,雙邊布局的所需的節(jié)點數(shù)量要少于單邊布局[11]。本文將路由節(jié)點按圖1進行雙邊交錯均勻布局。

圖1 凹形走廊和RNDM

凹形鏈狀區(qū)域可以看作直線區(qū)域的組合。每個直線區(qū)域中,都有一個較短的內(nèi)邊界borderin和較長的外邊界borderout(若等長,都作為內(nèi)邊界)。圖1中,w、l、r、c4個參數(shù)含義如下:w是鏈狀區(qū)域的寬度。r是節(jié)點的通信半徑。l是同一邊界上相鄰節(jié)點的間距,稱為節(jié)點間距。c為將一節(jié)點投影到另一邊界后,投影點的最短節(jié)點間距,稱為交錯距離。如點O在內(nèi)邊界的投影點為O′,投影點與內(nèi)邊界節(jié)點G和F具有節(jié)點間距O′G,和O′F,即距離c和c′,交錯距離為c。圖中有c

定義1(鄰居節(jié)點):對于網(wǎng)絡中的節(jié)點,其通信半徑內(nèi)的其他節(jié)點稱為鄰居節(jié)點。

定義2(路由節(jié)點度degree):路由節(jié)點的鄰居路由節(jié)點個數(shù)稱為路由節(jié)點度。

圖1中,w、l、r、c4個參數(shù)會影響到單個節(jié)點的degree,進而形成不同連通度的網(wǎng)絡。本文以degree為指標,設計了一種路由節(jié)點度模型RNDM。

在圖1中,以外邊界上的點O為原點,O所在外邊界為x軸,建立二維坐標系。若要求O能與對應內(nèi)邊界上的節(jié)點正常通信,其鄰居節(jié)點中至少包含距離最近的點G(c,-w)。因此可以得到標準1。

標準1為了保證網(wǎng)絡的連通性[4],必須滿足:

(1)

情形1 degree<2。O的鄰居節(jié)點只有G。此時整個網(wǎng)絡無法正常通信。

(2)

情形2 degree=2。O的鄰居節(jié)點有G,F。

(3)

情形3 degree=3。O的鄰居節(jié)點有G,B,C。有:

(4)

情形4 degree=4。O的鄰居節(jié)點有G,F,B,C。

(5)

情形5 degree>4。O的鄰居節(jié)點除了G,F,B,C外,還可能包括其他路由節(jié)點A,D,E,H。

(6)

若路由節(jié)點的通信半徑r和走廊寬度w為已知條件,依照式(2)～式(6),根據(jù)實際情形調(diào)整節(jié)點間距l(xiāng)和交錯距離c,就能完成對每個路由節(jié)點的度degree的調(diào)節(jié),進而形成如圖1的RNDM。

2 基于RFLC-SVR的普通路由節(jié)點定位

考慮到樓宇走廊WSN成本,只能布局少量擁有位置信息路由節(jié)點即錨節(jié)點,錨節(jié)點布局方法:(1)兩個外邊界相交部分(外拐角)的degree低于網(wǎng)絡平均連通度,應當在這些地方布置錨節(jié)點;(2)每條邊界所在直線應至少有一個錨節(jié)點。通過這些少量錨節(jié)點,使用基于多跳和測距無關(guān)的RFLC-SVR定位方法,普通路由節(jié)點可以得到位置信息,進而也晉升為錨節(jié)點,滿足樓宇走廊鏈狀拓撲對錨節(jié)點覆蓋率的需求。其具體步驟如下:

Step 1 洪泛階段

與DV-hop[6]相同,所有路由節(jié)點在洪范階段中計算與每個錨節(jié)點之間的最小跳數(shù)h,并保證最小跳距計算是在路由節(jié)點之間進行。

Step 2 訓練階段

收集錨節(jié)點的位置信息(x,y)和h,作為訓練樣本,h作為特征,用支持向量回歸(SVR)算法[12]進行模型訓練。依據(jù)圖1的網(wǎng)絡模型,直接將x和y作為兩個標簽,訓練出如式(7)的兩個模型,并將模型發(fā)送給網(wǎng)絡中的路由節(jié)點。式(7)中的w是回歸系數(shù)向量,b是偏移項。x′和y′是預測位置,φ(h)表示將向量h映射到高維空間。

Step 3 預測階段

普通路由節(jié)點收到模型后,將自己的h輸入到模型中,預測出位置信息,從而晉升為錨節(jié)點。

(7)

3 基于RFLC-PB的未知節(jié)點定位算法

當普通路由節(jié)點的位置信息得到后,區(qū)域內(nèi)錨節(jié)點覆蓋率就會顯著提高。進一步利用RFLC-PB來定位未知節(jié)點,其原理如圖2所示。

Step 1 未知節(jié)點U向周圍路由節(jié)點發(fā)出定位請求。路由節(jié)點收到請求后,將其位置信息(x,y),通信半徑r,節(jié)點ID直接向U投遞。若U為某路由節(jié)點的鄰居節(jié)點(假設有A,B,C,D),則U可接收到該信息,同時,測出來自該路由節(jié)點的接收信號強度RSSI。若U在限定時間內(nèi)收到少于3個路由節(jié)點的響應,則定位失敗。

圖2 RFLC-PB算法示意圖

Step 2 取路由節(jié)點圍成的最小凸包Con(如ABC)為約束區(qū)域Reg。

Step 3 選取兩個Con的頂點,連成線段并做垂直平分線。若Reg被垂直平分線劃分為兩個區(qū)域。將兩頂點RSSI進行對比。取RSSI大的頂點所在區(qū)域作為新的Reg。

Step 4 兩兩選取Con的頂點,重復Step 3,最終得到的Reg的質(zhì)心作為預測位置(如點P)。

4 仿真結(jié)果分析

針對C、O、H、S4種典型的走廊結(jié)構(gòu),在MATLAB 2014a上對RFLC的兩個階段進行仿真。第一階段,觀察和分析路由節(jié)點度對RFLC-SVR算法精度的影響,并以此為依據(jù)建立合適的RNDM模型。第二階段,采用第一階段選出的RNDM模型及RFLC-PB來定位隨機分布于區(qū)域內(nèi)的未知節(jié)點,并通過誤差計算來觀測RFLC的定位精度。

4.1 仿真場景及參數(shù)

在凹形鏈狀拓撲中,橫向內(nèi)邊界長度為27 m(如圖1所示的in_length),縱向內(nèi)邊界長度為18 m,走廊寬度為3 m。路由節(jié)點度degree為2,3,4時,設路由節(jié)點通信半徑r=4.8 m,參數(shù)l,c的選取如表1所示;degree>4時,采用dergee=4的布局,并增大r來得到相應網(wǎng)絡。4種拓撲degree為2,3,4的RNDM如圖3所示,對應的節(jié)點數(shù)量如表2所示。

表1 仿真條件下的WSN模型參數(shù) 單位:m

依次為C形、O形、H形、S形區(qū)域,每種區(qū)域RNDM的degree依次為2,3,4,三角形為錨節(jié)點圖3 RNDM網(wǎng)絡拓撲模型

形狀節(jié)點度節(jié)點數(shù)量錨節(jié)點數(shù)量錨節(jié)點比率23170.23C33690.2543870.1823680.22O344120.2744680.17251110.22H360110.18461110.18244110.25S354130.24456150.27

容易發(fā)現(xiàn),對于同一種拓撲,路由節(jié)點數(shù)量和degree呈正比?？傻萌缦陆Y(jié)論:

結(jié)論1同一凹形鏈式區(qū)域內(nèi),若通信半徑r不變,degree越大,覆蓋整個區(qū)域所需的路由節(jié)點數(shù)量越多,成本越高。

4.2 節(jié)點度對路由節(jié)點定位誤差的影響

在仿真場景中,運行RFLC-SVR,LSVR[9],KRR算法。由于樣本是錨節(jié)點,仿真中沒有樣本誤差,RFLC-SVR和LSVR采用硬間隔,核函數(shù)選擇RBF核,如式(8)。在參數(shù)選擇上,懲罰因子C=100,不敏感參數(shù)ε=0,γ=0.1。KRR的嶺回歸系數(shù)λ=0.1[10]。誤差計算采用均方根誤差RMS[10]如式(9):

k(xi,x)=exp(-γ‖x-xi‖2)

(8)

(9)

仿真結(jié)果圖如圖4所示?？梢钥吹?對于4種拓撲,RFLC-SVR的誤差在整體上小于另外兩種方法。degree為3和4時,RFLC-SVR的RMS<1。同時,3種方法的定位誤差曲線在degree<3時單調(diào)遞減,在degree>3時單調(diào)遞增。這是因為,3種方法都是以到每個錨節(jié)點的最小跳數(shù)h為特征。當degree<3時,大多數(shù)節(jié)點為不良節(jié)點(節(jié)點度小于3的節(jié)點)[7],h所提供的信息不足以反映出網(wǎng)絡中節(jié)點分布信息。degree>4時,個體的差異會減小,甚至不同位置的節(jié)點具有相同的h。因此有如下兩個結(jié)論:

結(jié)論2在走廊WSN網(wǎng)絡模型中,RFLC-SVR算法優(yōu)于LSVR和KRR。

結(jié)論3路由節(jié)點度degree對RFLC算法具有影響。RFLC適用于degree為3或4的RNDM。

圖4 degree對機器學習算法精度的影響

4.3 整體定位效果

由以上3個結(jié)論得知,應在4種走廊拓撲建立degree=3或4的RNDM,并在第一階段采用RFLC-SVR定位路由節(jié)點。對于第二階段,采用RFLC-PB算法定位100個隨機分布在區(qū)域內(nèi)的未知節(jié)點。定位誤差如表3所示。圖5是表3中RMS(RFLC-PB)分別為最小和最大時所對應的整體定位效果圖。表3和圖5表明,對于4種典型的走廊拓撲,RFLC達到的定位精度較高,滿足定位精度要求,適用于結(jié)構(gòu)多變的走廊環(huán)境。

表3 整體定位誤差表

三角形是錨節(jié)點,灰色正方形是普通路由節(jié)點的預測位置,空心圓圈是未知節(jié)點實際位置,每條線段連接著未知節(jié)點的實際位置和預測位置圖5 整體定位效果

5 結(jié)束語

針對凹形狹長空間中節(jié)點的定位問題,本文提出了基于RNDM網(wǎng)絡模型的RFLC定位算法。RNDM以degree為指標,在通道兩側(cè)交錯布置路由節(jié)點。RFLC采用degree為3或4的RNDM模型,先依據(jù)錨節(jié)點的位置信息,用RFLC-SVR定位路由節(jié)點,再利用路由節(jié)點的位置信息,用分布式算法RFLC-PB定位未知節(jié)點。仿真表明,degree對基于多跳的機器學習定位算法精度有較大影響;所提出的RFLC布設成本和復雜度較低,降低了錨節(jié)點數(shù)量需求,同時滿足了定位精度要求。未來將進一步拓展RFLC在更多走廊拓撲結(jié)構(gòu)中的性能分析。

[1] Bangali J,Shaligram A. Energy Efficient Smart Home Based on Wireless Sensor Network Using Labview[J]. American Journal of Engineering Research(AJER),2013,12(2):409-413.

[2] 張晉升,孫健,李勝廣,等. 狹長空間基于人體穿透損耗模型的組合定位方法[J]. 傳感技術(shù)學報,2016,29(4):601-605.

[3] 劉志平,朱丹彤,楊磊,等. 狹長受限空間錨節(jié)點定位的測距儀雙側(cè)自由設站法[J]. 傳感技術(shù)學報,2017,30(2):272-277.

[4] Chen G,Bao J,Zhang L. A Node Division Location Detection Scheme for Chain-Type Wireless Sensor Networks[J]. Wireless Communications and Mobile Computing,2016,16(1):79-93.

[5] Guo P,Jiang T,Zhang K. Novel Energy-Efficient Miner Monitoring System with Duty-Cycled Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2012,2012(1):1-12.

[6] 彭繼慎,楊慕紫,馬冰. 一種改進的無線傳感器網(wǎng)絡DV-Hop定位算法在煤礦井下漏電事故中的應用[J]. 傳感技術(shù)學報,2014,27(10):1431-1436.

[7] Liu X,Zhang S,Bu K. A Locality-Based Range-Free Localization Algorithm for Anisotropic Wireless Sensor Networks[J]. Telecommunication Systems,2015,62(1):3-13.

[8] Shahzad F,Sheltami T R. Effect of Network Topology on Localization Algorithm’s Performance[J]. Journal of Ambient Intelligence and Humanized Computing,2016,7(3):1-10.

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

[10] Yan X,Song A,Yang Z,et al. An Improved Multihop-Based Localization Algorithm for Wireless Sensor Network Using Learning Approach[J]. Computers and Electrical Engineering,2015,48(C):247-257.

[11] Chen Guangzhu,Meng Qingchun,Zhang Lei. Chain-Type Wireless Sensor Network Nodes Cheduling Strategy[J]. 系統(tǒng)工程與電子技術(shù)(英文版),2014,25(2):203-210.

[12] Cherkassky V,Ma Y. Practical Selection of SVM Parameters and Noise Estimation for SVM Regression[J]. Neural Networks,2004,17(1):113.

郝昭(1994-),男,湖北十堰人,碩士研究生,研究方向為無線傳感器網(wǎng)絡,504489929@qq.com;

李曉卉(1978-),女,湖北紅安人,博士、教授、碩士導師,研究方向為復雜網(wǎng)絡理論,無線傳感器網(wǎng)絡技術(shù),智能家居控制,智能電網(wǎng)需求響應理論及應用等,lixiaohui@wust.edu.cn。

ABuildingCorridorLocalizationAlgorithmBasedonWSNRoutingNodeDegreeModel*

HAOZhao1,LIXiaohui1*,DINGYuemin2

(1.College of Information Science and Engineering,Wuhan University of Science and Technology,Wuhan 430081,China;2.College of computer and communication engineering,Tianjin University of Technology,Tianjin 300384,China)

Considering the poor localization accuracy when applying the existing localization algorithm to complicated building corridor,a localization algorithm based on WSN routing node degree model is proposed. On the basis of the routing node degree model,the proposed algorithm firstly uses support vector regression to locate the routing node based on a few beacon’s location,so as to improve the rate of beacon coverage indirectly. Then,the proposed algorithm uses a way of perpendicular bisector division to locate the unknown nodes and the mobile terminals. Simulation shows that the proposed algorithm improves the localization accuracy compared with LSVR and KRR,satisfy the requirement of indoor localization(1 m～3 m),reduce the demand of anchor number,so it can be used in the localization of WSN for the building corridor.

wireless sensor network;range free localization;support-vector regression;region division;concave long-narrow space

TP393

A

1004-1699(2017)11-1700-06

項目來源:國家自然科學基金項目(61105070);天津市科委面上項目(15JCYBJC52400);國家國際科技合作專項項目(2013DFG72850)

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

10.3969/j.issn.1004-1699.2017.11.015