狭长直隧道环境中WSN的RSSI加权质心定位算法

方旺盛,高　银

(江西理工大学信息工程学院,江西 赣州 341000)

在矿井的安全生产中,依靠无线传感器网络技术[1-2]能够保证管理人员对矿井巷道中的环境、人员和车辆等实时监控,而如何设计一套有效的定位算法对巷道中的人员与车辆定位已经成为一个重要的问题[3]。

目前现有的无线传感器网络定位算法[4]主要分为基于测距的(Range-based)定位算法和无需测距的(Range-free)定位算法[5]。这些算法大多未考虑节点的可移动性[6]和异构性[7]。在实际应用中,井下人员与矿车都具有移动性,且矿下监测传感器节点多种多样,如:温度、适度、粉尘、坑壁压力、各种气体浓度参数等不同环境变量的节点,这些节点的部署随着采掘面的延伸而扩展。移动性和异构性增加了节点的定位难度,因此,井下无线传感器网络节点的移动性和异构性是井下节点定位的关键问题。

俞黎阳、王能等人提出了基于选址问题的异构节点部署算法,以优化无线传感器网络中异构节点的数量和位置[8],算法仅考虑了节点的异构性;朱晓娟、孟祥瑞等人利用固定信标节点和未知节点的接受信号强度指示值RSSI(Received Signal Strength Indication)作为依据,计算每个固定信标节点的权值,通过权值来体现固定信标节点对质心坐标决定权的大小[9],但仅考虑到了信标节点静止而待定位节点随机移动的情况。

矿井巷道和公路、铁路隧道都可看作三维狭长隧道,隧道内除少部分区域存在分支隧道外,大部分区域都可看作狭长隧道,而这些狭长隧道虽然可能存在部分弯曲,但大多数弯曲半径较大,可看成狭长直隧道。本算法重点考虑狭长直隧道内节点的异构性和移动性,在基于RSSI的加权质心定位算法的基础下,结合狭长直隧道内节点的分布模型,采用修正加权权重的方法对传统的质心定位算法[10]进行了改进,使得算法满足矿井隧道中的无线传感器节点移动性和异构性的需要,算法定位精度高、适合于狭长直隧道环境。

1　狭长直隧道内节点分布模型

井下隧道根据空间特性和功能,分为垂直巷道、倾斜巷道和水平巷道三大类[11],由于本文所研究的是狭长直隧道[12],为了研究方便,只截取这些巷道中的某一段狭长直隧道来做研究,如图1所示。

图1中子图1(a)表示的是节点在隧道底面上的投影,其中黑色圆点是信标节点,圆圈表示的是普通节点如本文中的监测节点,三角形和正方形分别表示隧道内的工作人员与矿车。图1(b)所示的是信标节点在隧道内的空间结构分布模型,其中B1、B4、B7为隧道左侧壁上的信标节点;B2、B5为隧道右侧壁上的信标节点;B3、B6为隧道顶部的信标节点。将隧道空间节点按不同平面投影,可得到信标节点分别在ZX平面与XY平面上的投影。

2　RSSI加权质心算法及改进

2.1　传统的质心定位算法

质心定位算法最初是由南加州大学Nirupama Bulusu等人提出的一种无需测距的室外定位算法[13]。具体的定位过程为:信标节点周期性地发出自身位置坐标信息(xi,yi)的信标信号,当未知节点接收到来自不同信标节点的信标分组数量超过一个门限或接收一定时间后,那么就认为未知节点和这些信标节点连通,把所有与自己连通的信标节点组成的多边形的质心作为自己的估计位置,计算公式为:

(1)

式中(x,y)是未知节点的坐标;(xi,yi)(i=1,2,…N)为未知节点能够接收到其分组的信标节点坐标。传统的质心算法的定位精度受到信标节点的分布情况和分布密度的影响很大。

2.2　基于RSSI的加权质心算法

基于RSSI的加权质心算法是以未知节点与信标节点之间的RSSI为依据,计算每个信标节点坐标对应的加权值,通过加权值来体现信标节点对质心位置的影响程度,反映他们的内在关系。加权质心算法的计算公式为:

(2)

式中ωi(i=1,2,…N)为每个信标节点对应的加权值,通常ωi为未知节点与各个信标节点之间距离d的函数。

2.3　基于RSSI的加权质心改进算法

对于质心算法和基于RSSI的加权质心算法,由于仅计算节点自身坐标与各个接收节点距离发射点的距离的加权值,因此算法计算简单,适用于对精度要求不高的大规模传感器网络的定位。且这两种算法并未考虑节点的移动与异构情况,因为无线传感器网络因其应用场景不同,节点的分布情况与运动形式也不同,节点的移动与异构情况决定了质心算法与基于RSSI的加权质心算法不适用于本文所要求的隧道中人员与矿车的定位。隧道空间是三维近似半封闭的,隧道壁分布的信标节点与隧道内壁监测节点的功能各不相同,从而导致通信半径也各不相同,且隧道中的人员与矿车是移动的。本文的算法考虑了隧道内节点的移动与异构情况,将更适合井下应用场景。

本文的算法将定位过程分为两个阶段。第1个阶段是隧道内信标节点的分布和选择。隧道内人员与矿车的移动所组成的未知节点在移动过程中可能会接收到来自隧道四周安置的信标节点的信息,这些节点在某一时间内处于信标节点的连通范围内,但是随着节点的移动,其所处的范围也会随着变化。本文将信标节点按图1(b)所示分布,隧道左右侧壁与顶部分别安置一定数量的信标节点,这些信标节点组成了三边或多边的网络格型,当未知节点在某一时刻处于某一位置时,与未知节点连通的信标节点组成多边形,对未知节点进行定位。由于隧道是空间立体结构的,分布其中的节点都具有三维坐标,本文需定位的是处于隧道中的工作人员与矿车,这些未知节点在隧道中Z轴的坐标位置无实用价值,只需考虑在隧道XY平面上的坐标位置,即仅考虑图1(b)中节点投影在XY平面上的节点坐标位置,如图2所示。设N个固定的信标节点在XY平面上投影的坐标分别为B1(x1,y1),B2(x2,y2),…,BN(xN,yN),未知节点M(xest,yest)到各信标节点的距离分别为d1,d2,d3,…,dn。

图2　节点定位算法示意图

第2个阶段主要是根据选择的信标节点确定权值并进行定位。加权质心算法主要是利用固定的信标节点和未知节点的接收信号强度指示值(RSSI)来计算每个固定信标节点的权值。在本文中,隧道中信标节点与监测节点各具有不同的通信半径,不同的通信半径对应不同的RSSI值。本文的算法主要参考杨新宇、孔庆茹等人提出的方法[14],把未知节点接收到各个信标节点的信号强度的比值作为每个信标的权值,这样体现不同信标节点对于未知节点的影响力的同时,也可以做到环境改变时权值保持不变,因此提高了算法的精度。未知节点M分别从信标节点Bj、Bi接受到的RSSI信号强度比值为Rji,权值为ωi,有:

Rji=Rj/Ri,i=1,2…N,j≠i

(3)

(4)

式(4)的权值是基于同类的信标节点上获取的,本文中的隧道存在非同类的信标节点,对于隧道中存在M类信标节点,设与未知节点通信的同类信标节点个数分别有K1,K2,K3,…KM个。因此非同类信标节点总数有N=K1+K2+…+KM,这些节点的通信半径组成的集合为Sr={r1,r2,r3,…,rN},因此本文的修改算法中,将未知节点与信标节点间通信半径平方的倒数考虑在内修正后的权值ωi为:

(5)

式中ri(i=1,2,…N)为是未知节点分别与这N个信标节点间的最大通信半径,修正后的权值能很好地体现隧道内节点的异构性对于未知节点定位的决定权,能更好的适用于隧道内节点的定位,使得节点定位更精确。

根据权值ωi与信标节点的坐标求出加待定位节点的坐标M(xest,yest):

(6)

(7)

当r1=r2=r3=…=rN时,即各个信标节点通信半径相同,为同类的信标节点,此时节点的定位算法与同类节点定位算法相同。

由于狭长隧道的高度一般不超过10 m,隧道壁和顶部的节点作为信标节点,隧道内为各种未知的节点,即将一个区域划分为若干个三角形或多边形,多边形的顶点为信标节点,质心作为未知节点(x,y)。定位算法步骤如下:

(1)信标节点周期性地广播信息,信息中包括节点ID和自身的位置坐标;

(2)待定位节点接收各信标节点的信息,在某一时刻记录各个信标节点的RSSI值,当所得的信标节点数大于等于4时,取RSSI值较大的4个信标节点,即保证信标节点组由离待定位节点最近的4个信标节点组成;

(3)根据第(2)步中得到的4个信标节点建立2个集合:通信半径集合Sr={r1,r2,r3,r4};坐标集合P={(x1,y1),(x2,y2),(x3,y3),(x4,y4)};

(4)根据式(5)计算出每一个信标节点的加权值ωi;

(5)将得到的权值ωi与信标节点的坐标根据式(6)、式(7)计算出未知节点的坐标(x,y),该坐标是未知移动节点的估计坐标。

算法分析如下:

由于本文所研究的是半封闭的狭长直隧道环境中的节点定位,无线信号在传播过程中存在多径衰落,因狭长直隧道内壁的凹凸不平及信号吸收等原因,多径反射和散射信标节点的信号强度一般较弱,如果根据这些信标节点来计算待定位节点的位置会增大定位误差。对于视距信标节点,信号强度较小的信标节点距离越远,当距离达到某一阈值时不能用距离较小时的信号散射模型,否则会增大定位误差。因此本文算法选取的信标节点是4个RSSI值较大的信标节点,这些信标节点是距离较近的视距节点,从而基本剔除了由多径反射和散射信标节点造成的定位误差。根据式(6)和式(7),当信标节点数为N时,其计算量均为N(N-1);本文算法取RSSI值较大的4个信标节点作为参与定位的节点,其计算量为4×3=12,能显著地减小计算量。

3　仿真结果及分析

运用MATLAB进行算法仿真,仿真实验的初始条件为10 m×2 000 m的矩形区域,即设定隧道的长度为2 000 m,宽度为10 m。传感器节点的部署如图1所示,为了易于验证,未知节点的坐标初始化为原点(0,0),无线信号的载频为2.4 GHz。在信标节点数从5到25变化的基础上对算法进行仿真分析,每个实验运行500次,仿真结果取500次的平均值。结合隧道中节点的实际应用环境,分别从固定在隧道壁上信标节点数和节点的通信半径进行仿真和分析,为了易于仿真计算,当通信半径不同时,假设存在3类信标节点,且这3类信标节点的通信半径为(r-5)、r、(r+5)。仿真结果如图3～图5所示。其中定位误差的计算公式如式(8)所示

(8)

式中x,y为实际距离,x′,y′为测量值,若未知节点个数为k,则平均误差为∑ei/k。

图3所示的是信标节点的个数变化对定位误差的影响,在相同条件下,信标节点个数由5个变化到20个时,修改后的算法的误差大大低于传统的质心算法和基于RSSI值的加权质心算法;当信标节点的数目增多,未知节点收到的信标节点信息较均匀,3种算法误差的差距减小。图4图5所示的是信标节点通信半径的变化对定位误差的影响。当信标节点的初始通信半径相同时,随着节点的通信半径增加,可以看到相较于传统质心算法与基于RSSI值的加权质心算法,本算法能有效的减小定位误差,但节点通信半径的增加,对其定位误差影响不是很大;当初始通信半径不同的时候,与同类的节点定位算法相比,异构信标节点的定位误差较小,定位算法的精度有了很大的提高。

图5　非同类信标节点时通信半径的变化对定位误差的影响

图3　信标节点数对定位误差的影响

图4　同类信标节点的通信半径变化对定位误差的影响

4　总结

综上所述,本文提出的狭长直隧道内基于RSSI的质心定位算法在井下人员与矿车的定位上有着明显的优势,克服了传统质心加权算法在此环境下出现的较大误差,第1步通过对隧道内节点分布的分析,选择合适的信标节点,确保了信标节点的有效性,第2步根据选择的信标节点确定权值从而进行定位,考虑了隧道内节点的异构性与移动性特点。本文研究的是狭长直隧道内的节点定位,如何对弯曲和分支隧道内节点定位是下一步工作的重点。

参考文献:

[1]Yick J,Mukherjee B,Ghosal D.Wireless Sensor Network Survey[J].Computer Networks,2008,52(12):2292-2330.

[2]Rahman K C.A Survey on Sensor Network[J].Journal of Computer and Information Technology,2010(1):76-87.

[3]杨大明.煤矿井下紧急避险系统的建设与发展[J].煤炭科学技术,2010(11):6-9.

[4]Mao G,Fidan B,Anderson B.Wireless Sensor Network Localization Techniques[J].Computer Networks,2007,51(10):2529-2553.

[5]Chen C C,Chang C Y,Li Y N.Range-Free Localization Scheme in Wireless Sensor Networks Based on Bilateration[J].International Journal of Distributed Sensor Networks,2013,2013.

[6]Zhu Y,Zhang B,Yu,et al.A RSSI Based Localization Algorithm Using a Mobile Anchor Nodefor Wireless Sensor Networks[C]//Computational Sciences and Optimization,2009.CSO 2009.International Joint Conference on.IEEE,2009,1:123-126.

[7]Li X Y,Song W Z,Wang Y.Localized Topology Control for Heterogeneous Wireless Sensor Networks[J].ACM Transactions on Sensor Networks(TOSN),2006,2(1):129-153.

[8]俞黎阳,王能,张卫.异构无线传感器网络中异构节点的部署与优化[J].计算机科学,2008(9):48-51.

[9]朱晓娟,孟祥瑞.基于加权质心的无线传感器网络移动节点定位算法[J].计算机工程与科学,2011,33(11):15-19.

[10]陈维克,李文锋,首珩,等.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报,2006,30(12):265-268.

[11]Han Guorui,Zhang Wenmei,Zhang Y P.An Experiment Study of the Propagation of Radio Waves in a Scaled Model of Long-Wall Coal Mining Tunnels[J].IEEE Antennas and Wireless Propagation Letters,2009(8):502-504.

[12]Kavitha K,Teja C R,Gururaj R.Workload-Aware Tree Construction Algorithm for Wireless Sensor Networks[J].International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks,2012,4(1):1-14.

[13]Bulusu N,Heidemann J,Estrin D.GPS-Less Low Cost Outdoor Locali-zation for Very Small Devices[J].IEEE Personal Communications,2000,7(5):28-34.

[14]杨新宇,孔庆茹,戴湘军.一种改进的加权质心定位算法[J].西安交通大学学报,2010,44(8):1-4.

方旺盛(1963-),男,教授,硕士研究生导师。主要研究方向为无线传感器网络,数字水印,基因表达式编程等,fangwangsheng@163.com;

高银(1987-),男,硕士研究生,主要研究方向为无线传感器网络。