基于WSN路由节点度模型的楼宇走廊定位算法*

郝 昭,李晓卉*,丁月民

(1.武汉科技大学信息科学与工程学院,武汉 430081;2. 天津理工大学计算机与通信工程学院,天津 300384)

基于WSN路由节点度模型的楼宇走廊定位算法*

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

(1.武汉科技大学信息科学与工程学院,武汉 430081;2. 天津理工大学计算机与通信工程学院,天津 300384)

针对现有的无线传感器网络(WSN)定位方法应用于结构复杂的楼宇走廊时,存在定位精度较低的问题,提出一种基于WSN路由节点度模型的楼宇走廊定位算法。该算法在路由节点度模型的基础上,先采用基于支持向量回归(SVR)的方法,用少量锚节点定位普通路由节点,达到间接增加锚节点覆盖率的目的;然后采用基于中垂线分割的方法定位随机分布在区域内的未知节点和移动终端。仿真表明:与传统SVR定位算法和核岭回归定位算法相比,所提出的算法精度提高了定位精度,满足室内定位精度要求(1 m～3 m),且降低了对锚节点数量的需求,可运用于楼宇走廊WSN定位。

无线传感网络;距离无关定位;支持向量回归;区域分割;凹形狭长空间

无线传感器网络技术WSN(Wireless Sensor Networks)由于其安装方便,无须布线,不会对建筑进行任何改动,即插即用,低功耗等特点广泛应用于智能楼宇中[1]。在商场,仓库,医院,展厅,宾馆等楼宇环境中,走廊是人员频繁移动的区域,也是WSN重点监测区域。该区域的传感器节点位置信息对楼宇的相关智能化服务必不可少。

大型楼宇走廊多为狭长的凹形链状区域。该环境中,目前已有室内定位方法主要有WiFi,测距RSSI[2]。其中,WiFi定位需要位置服务商频繁采样和更新指纹库;测距RSSI需要在区域内部署大量锚节点[3],且墙壁阻挡等环境因素会使信号产生多径和非视距效应,从而降低其定位精度。WSN的距离无关定位方法(range-free localization)由于低能耗、低成本,受环境影响小,近年来受到较大关注[4]。对于链状WSN,目前提出的距离无关室内定位方法[4]需要覆盖大量锚节点,算法复杂度高,且多以直线区域的WSN为定位算法的研究背景。然而,凹形区域的WSN具有各向异性[7],该性质会大幅降低距离无关定位方法(如DV-hop等多跳算法)的定位精度[8]。对此,不少学者将机器学习算法引入到多跳定位算法中,如文献[9]提出了支持向量回归的方法LSVR和LMSVR,文献[10]提出了基于核岭回归(KRR)的方法。这些算法既提高了各向异性WSN的定位精度,又没有增加开销和算法复杂度。

对于可人工布局节点的场景,较少研究注意到网络拓扑结构对定位算法的影响。对于走廊环境,本文设计了一种WSN路由节点度模型RNDM(Routing Node Degree Model),并在此基础上提出一种适用于楼宇走廊WSN的距离无关定位算法RFLC(Range-Free Localization algorithm for WSN in Corridor)。本文将楼宇走廊WSN节点分为3种类型:锚节点(位置已知的路由节点),普通路由节点(位置未知的路由节点),未知节点(随机分布的移动终端和检测节点),在楼宇走廊布置少量锚节点,并依据节点度,在通道两侧均匀交错布局普通路由节点,形成RNDM。RFLC算法分为两个阶段:基于支持向量回归的普通路由节点定位RFLC-SVR(RFLC-Support Vector Regression)和基于区域分割的未知节点定位RFLC-PB(RFLC-Perpendicular Bisector division)。第一阶段,依据少量锚节点信息,采用RFLC-SVR算法定位普通路由节点,进而将这些普通路由节点晋升为锚节点,从而间接增加锚节点的数量和覆盖率。第二阶段,使用分布式定位算法RFLC-PB定位走廊内部的未知节点和移动终端。仿真证明,该算法降低了对锚节点数量的需求,更适应复杂的走廊环境,且满足定位精度要求(1 m～3 m)[3]。

1 基于路由节点度的网络模型

为了在走廊WSN中传递数据,网络拓扑边界上需分布一些路由节点。当网络当中没有监测盲区、达到相同的连通性时,双边布局的所需的节点数量要少于单边布局[11]。本文将路由节点按图1进行双边交错均匀布局。

图1 凹形走廊和RNDM

凹形链状区域可以看作直线区域的组合。每个直线区域中,都有一个较短的内边界borderin和较长的外边界borderout(若等长,都作为内边界)。图1中,w、l、r、c4个参数含义如下:w是链状区域的宽度。r是节点的通信半径。l是同一边界上相邻节点的间距,称为节点间距。c为将一节点投影到另一边界后,投影点的最短节点间距,称为交错距离。如点O在内边界的投影点为O′,投影点与内边界节点G和F具有节点间距O′G,和O′F,即距离c和c′,交错距离为c。图中有c

定义1(邻居节点):对于网络中的节点,其通信半径内的其他节点称为邻居节点。

定义2(路由节点度degree):路由节点的邻居路由节点个数称为路由节点度。

图1中,w、l、r、c4个参数会影响到单个节点的degree,进而形成不同连通度的网络。本文以degree为指标,设计了一种路由节点度模型RNDM。

在图1中,以外边界上的点O为原点,O所在外边界为x轴,建立二维坐标系。若要求O能与对应内边界上的节点正常通信,其邻居节点中至少包含距离最近的点G(c,-w)。因此可以得到标准1。

标准1为了保证网络的连通性[4],必须满足:

(1)

情形1 degree<2。O的邻居节点只有G。此时整个网络无法正常通信。

(2)

情形2 degree=2。O的邻居节点有G,F。

(3)

情形3 degree=3。O的邻居节点有G,B,C。有:

(4)

情形4 degree=4。O的邻居节点有G,F,B,C。

(5)

情形5 degree>4。O的邻居节点除了G,F,B,C外,还可能包括其他路由节点A,D,E,H。

(6)

若路由节点的通信半径r和走廊宽度w为已知条件,依照式(2)～式(6),根据实际情形调整节点间距l和交错距离c,就能完成对每个路由节点的度degree的调节,进而形成如图1的RNDM。

2 基于RFLC-SVR的普通路由节点定位

考虑到楼宇走廊WSN成本,只能布局少量拥有位置信息路由节点即锚节点,锚节点布局方法:(1)两个外边界相交部分(外拐角)的degree低于网络平均连通度,应当在这些地方布置锚节点;(2)每条边界所在直线应至少有一个锚节点。通过这些少量锚节点,使用基于多跳和测距无关的RFLC-SVR定位方法,普通路由节点可以得到位置信息,进而也晋升为锚节点,满足楼宇走廊链状拓扑对锚节点覆盖率的需求。其具体步骤如下:

Step 1 洪泛阶段

与DV-hop[6]相同,所有路由节点在洪范阶段中计算与每个锚节点之间的最小跳数h,并保证最小跳距计算是在路由节点之间进行。

Step 2 训练阶段

收集锚节点的位置信息(x,y)和h,作为训练样本,h作为特征,用支持向量回归(SVR)算法[12]进行模型训练。依据图1的网络模型,直接将x和y作为两个标签,训练出如式(7)的两个模型,并将模型发送给网络中的路由节点。式(7)中的w是回归系数向量,b是偏移项。x′和y′是预测位置,φ(h)表示将向量h映射到高维空间。

Step 3 预测阶段

普通路由节点收到模型后,将自己的h输入到模型中,预测出位置信息,从而晋升为锚节点。

(7)

3 基于RFLC-PB的未知节点定位算法

当普通路由节点的位置信息得到后,区域内锚节点覆盖率就会显著提高。进一步利用RFLC-PB来定位未知节点,其原理如图2所示。

Step 1 未知节点U向周围路由节点发出定位请求。路由节点收到请求后,将其位置信息(x,y),通信半径r,节点ID直接向U投递。若U为某路由节点的邻居节点(假设有A,B,C,D),则U可接收到该信息,同时,测出来自该路由节点的接收信号强度RSSI。若U在限定时间内收到少于3个路由节点的响应,则定位失败。

图2 RFLC-PB算法示意图

Step 2 取路由节点围成的最小凸包Con(如ABC)为约束区域Reg。

Step 3 选取两个Con的顶点,连成线段并做垂直平分线。若Reg被垂直平分线划分为两个区域。将两顶点RSSI进行对比。取RSSI大的顶点所在区域作为新的Reg。

Step 4 两两选取Con的顶点,重复Step 3,最终得到的Reg的质心作为预测位置(如点P)。

4 仿真结果分析

针对C、O、H、S4种典型的走廊结构,在MATLAB 2014a上对RFLC的两个阶段进行仿真。第一阶段,观察和分析路由节点度对RFLC-SVR算法精度的影响,并以此为依据建立合适的RNDM模型。第二阶段,采用第一阶段选出的RNDM模型及RFLC-PB来定位随机分布于区域内的未知节点,并通过误差计算来观测RFLC的定位精度。

4.1 仿真场景及参数

在凹形链状拓扑中,横向内边界长度为27 m(如图1所示的in_length),纵向内边界长度为18 m,走廊宽度为3 m。路由节点度degree为2,3,4时,设路由节点通信半径r=4.8 m,参数l,c的选取如表1所示;degree>4时,采用dergee=4的布局,并增大r来得到相应网络。4种拓扑degree为2,3,4的RNDM如图3所示,对应的节点数量如表2所示。

表1 仿真条件下的WSN模型参数 单位:m

依次为C形、O形、H形、S形区域,每种区域RNDM的degree依次为2,3,4,三角形为锚节点图3 RNDM网络拓扑模型

形状节点度节点数量锚节点数量锚节点比率23170.23C33690.2543870.1823680.22O344120.2744680.17251110.22H360110.18461110.18244110.25S354130.24456150.27

容易发现,对于同一种拓扑,路由节点数量和degree呈正比。可得如下结论:

结论1同一凹形链式区域内,若通信半径r不变,degree越大,覆盖整个区域所需的路由节点数量越多,成本越高。

4.2 节点度对路由节点定位误差的影响

在仿真场景中,运行RFLC-SVR,LSVR[9],KRR算法。由于样本是锚节点,仿真中没有样本误差,RFLC-SVR和LSVR采用硬间隔,核函数选择RBF核,如式(8)。在参数选择上,惩罚因子C=100,不敏感参数ε=0,γ=0.1。KRR的岭回归系数λ=0.1[10]。误差计算采用均方根误差RMS[10]如式(9):

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

(8)

(9)

仿真结果图如图4所示。可以看到:对于4种拓扑,RFLC-SVR的误差在整体上小于另外两种方法。degree为3和4时,RFLC-SVR的RMS<1。同时,3种方法的定位误差曲线在degree<3时单调递减,在degree>3时单调递增。这是因为,3种方法都是以到每个锚节点的最小跳数h为特征。当degree<3时,大多数节点为不良节点(节点度小于3的节点)[7],h所提供的信息不足以反映出网络中节点分布信息。degree>4时,个体的差异会减小,甚至不同位置的节点具有相同的h。因此有如下两个结论:

结论2在走廊WSN网络模型中,RFLC-SVR算法优于LSVR和KRR。

结论3路由节点度degree对RFLC算法具有影响。RFLC适用于degree为3或4的RNDM。

图4 degree对机器学习算法精度的影响

4.3 整体定位效果

由以上3个结论得知,应在4种走廊拓扑建立degree=3或4的RNDM,并在第一阶段采用RFLC-SVR定位路由节点。对于第二阶段,采用RFLC-PB算法定位100个随机分布在区域内的未知节点。定位误差如表3所示。图5是表3中RMS(RFLC-PB)分别为最小和最大时所对应的整体定位效果图。表3和图5表明,对于4种典型的走廊拓扑,RFLC达到的定位精度较高,满足定位精度要求,适用于结构多变的走廊环境。

表3 整体定位误差表

三角形是锚节点,灰色正方形是普通路由节点的预测位置,空心圆圈是未知节点实际位置,每条线段连接着未知节点的实际位置和预测位置图5 整体定位效果

5 结束语

针对凹形狭长空间中节点的定位问题,本文提出了基于RNDM网络模型的RFLC定位算法。RNDM以degree为指标,在通道两侧交错布置路由节点。RFLC采用degree为3或4的RNDM模型,先依据锚节点的位置信息,用RFLC-SVR定位路由节点,再利用路由节点的位置信息,用分布式算法RFLC-PB定位未知节点。仿真表明,degree对基于多跳的机器学习定位算法精度有较大影响;所提出的RFLC布设成本和复杂度较低,降低了锚节点数量需求,同时满足了定位精度要求。未来将进一步拓展RFLC在更多走廊拓扑结构中的性能分析。

[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]. 传感技术学报,2016,29(4):601-605.

[3] 刘志平,朱丹彤,杨磊,等. 狭长受限空间锚节点定位的测距仪双侧自由设站法[J]. 传感技术学报,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] 彭继慎,杨慕紫,马冰. 一种改进的无线传感器网络DV-Hop定位算法在煤矿井下漏电事故中的应用[J]. 传感技术学报,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]. 系统工程与电子技术(英文版),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-),男,湖北十堰人,硕士研究生,研究方向为无线传感器网络,504489929@qq.com;

李晓卉(1978-),女,湖北红安人,博士、教授、硕士导师,研究方向为复杂网络理论,无线传感器网络技术,智能家居控制,智能电网需求响应理论及应用等,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