摘要:现有煤矿无线传感器网络节点定位存在定位精度差、功耗高等问题，提出一种基于信标节点规则部署的煤矿井下无线传感器网络节点三维定位算法，根据井下巷道特征成对部署信标节点，在定位估算时先将信标节点投影到与未知节点同一高度的水平面，再利用三边测量法进行平面定位，然后结合未知节点与信标节点的高度差即可实现三维定位。理论分析和仿真结果表明，该算法具有计算量小、通信量小、定位精度较高以及稳定性较好等特点。
关键词:无线传感器网络；煤矿；三维定位；定位精度；能耗；
稳定性中图分类号: TP393 文献标志码:A
3D localization algorithm for wireless sensor networks in underground coal mine
ZHU Xiao.juan1*, WANG Jun.hao1, MENG Xiang.rui2
1. School of Computer Science and Engineering, Anhui University of Science and Technology, Huainan Anhui 232001, China; 2. School of Energy and Safety, Anhui University of Science and Technology, Huainan Anhui 232001, ChinaAbstract:
Most existing algorithms for wireless sensor networks localization in underground coal mine have low accuracy and high cost problems. A novel 3D localization algorithm is proposed for underground coal mine based on the beacon nodes regular deployment. First, the beacon nodes is deployed according to the characters of the underground tunnel , second, the beacon nodes and unknown node are projected onto the same high level when location estimation, third, 2D position is calculated by trilateration ,at last the 3D position is obtained by means of combining with the height difference between unknown nodes and beacon nodes .Theoretical analysis and simulation results show that the algorithm has less calculation, low communication, higher positioning accuracy and good stability characters.
Most of the existing algorithms for Wireless Sensor Networks (WSN) localization in underground coal mine have problems of low accuracy and high cost. A new 3D localization algorithm was proposed for underground coal mine based on the regular deployment of beacon nodes. First, the beacon nodes were deployed according to the characteristics of the underground tunnel; second, the beacon nodes and unknown node were projected onto the same high level while doing location estimation; third, 2D position was calculated by trilateration; at last the 3D position was obtained by means of combining the height difference between unknown nodes and beacon nodes. The theoretical analysis and simulation results show that the algorithm is of less calculation, low communication, higher positioning accuracy and good stability.
Key words:
Wireless Sensor Networks (WSN); coal mine; 3D localization; positioning accuracy; energy consumption; stability
0引言
无线传感器网络已被应用于煤矿井下人员定位、环境监测和机电装备状态检测与定位中，由传感器采集到的数据在不知道相应位置信息的情况下，往往是没有意义的。因此研究可靠实用的煤矿井下无线传感器网络节点定位算法，不仅能进行较为精确的监控，当矿难发生时还能够提供位置信息便于及时展开救援，对煤矿的安全生产有着重要的现实意义。
在煤矿井下定位算法的相关研究领域，许多的节点定位算法已被提出。文献［1］提出了一种信标节点链式部署结构下的动态接收信号强度指示(Received Signal Strength Indication,RSSI)测距算法,计算巷道内实际环境下的路径衰落指数,以提高RSSI测距算法对环境的适应性；文献［2］提出了基于RSSI的对角差分修正定位算法，利用差分原理对测量距离进行修正，从而改善了定位精度；文献［3］将RSSI测距法与切球球心法相结合，提出了接收信号强度指示与切球球心法混合定位算法(RSSI and Sphere centre Mixed localization，RSM)；文献［4］提出了一种基于球面坐标的动态定位机制,将定位问题抽象为多元线性方程组求解问题；文献［5］将井下巷道网络分割成多个以网关为中心的分布式定位单元，当移动节点经过定位单元时，首先计算其在局部定位单元内的位置坐标，并将该位置信息通过多跳传递给网关，再由网关传送到井上计算机，由井上计算机通过坐标变换计算出该节点在井下巷道网络的三维位置坐标。
文献［1-2］是对基于RSSI测距定位算法的一些改进，克服RSSI在井下受环境影响大的缺点，提高了定位的精度，但都只局限于二维空间定位。煤矿井下的无线传感器网络是部署在三维空间的，三维空间定位与二维平面定位相比，环境因素更加复杂，增加了定位难度。文献［3-4］是一种建立在立体坐标系的三维定位算法，需要四个信标节点辅助定位，计算量较大，当进行定位求精时进一步增大了计算量。另外信标数量的增加也将导致测距误差的累积从而影响全局的定位误差。文献［5］提出的定位算法增加了网关附近的通信压力，会造成网关附近的节点生命周期的快速耗尽。现有研究表明［11-12］，传感器节点的能量消耗主要发生在通信模块上，因此文献［5］提出的定位方法在通信能耗的缺点不容忽视。
本文提出了一种基于信标节点规则部署的煤矿井下无线传感器网络节点三维定位算法(3D Localization based on beacon nodes Regular Deployment in underground coal mine,3DL.RD)。本算法结合煤矿井下巷道的特点规则放置信标节点，定位时先将信标节点投影到与未知节点同一高度的水平面，利用三边测量法(Trilateration)［6］计算未知节点在投影平面的坐标，然后结合其与信标节点的高度差即可实现井下未知节点的三维定位。理论分析和仿真结果均表明，本算法具有计算量小、通信量小、定位精度好以及稳定性好等特点。
1相关原理
未知节点在通过RSSI获得距离的估计之后，可采用三边测量法来估算自己的位置。三边测量法的原理如图1所示。假设节点A,B,C坐标已知，分别为(x1,y1),(x2,y2),(x3,y3);节点U的坐标未知，设为(x,y)；与节点A,B,C的距离分别是d1,d2,d3。那么式(1)［6］成立：
(x－xi)2+(y－yi)2=d2i; i=1,2,3(1)
可求解出未知节点的坐标为：
因此运用式(2)计算二维平面下未知节点坐标所花费的时间为3t,而利用式(4)计算三维空间下未知节点的坐标所花费的时间则为(3t+ω)×4。其中ω是用来对这些2×2行列式进行乘法、加法和减法计算时带来的额外开销。为了提高定位精度，通常还需要更多的信标节点，用这些信标节点的组合或组合的子集进行定位，定位结果最终取其平均值。通过分析可以看出三维空间下利用四个非共面的信标节点对未知节点进行定位所需计算量远远大于在二维平面下三个信标节点辅助定位的计算量。
2煤矿井下无线传感器网络节点三维定位算法
通常对三维空间里的未知节点进行定位时都是利用四个非共面的信标节点来辅助定位。本文提出的3DL.RD算法，通过规则放置信标节点，计算时将三维空间转化成二维平面，利用三边测量法就可以估计出未知节点的平面坐标；再结合信标节点与未知节点的高度差就可实现三维空间里的未知节点定位。与现有的三维定位算法相比具有计算量小、通信量小、定位精度好以及稳定性好等特点。
2.1算法原理
本文提出的3DL.RD算法应用于煤矿井下巷道的节点定位，煤矿井下巷道基本上是狭长型，顶部多存在微弧形或者侧面存在少许的凹凸，可近似地考虑成长方体［15］。信标节点部署在长方体的棱边上且成对放置，即每对信标节点的X,Y轴坐标相同，只有Z轴坐标不同，如图2所示。
图片图2巷道内信标节点的放置规则将成对信标节点记为Ai(xi,yi,zi)和Ai′(xi,yi,z′i)。假设未知节点S的坐标为(x,y,z)，3个信标节点对的坐标分别为A1 (x1 ,y1 ,z1 ),A1′ (x1 ,y1 ,z1 ′),A2 (x2 ,y2 ,z2 ),A2 ′(x2 ,y2 ,z2 ′),A3(x3,y3,z3),A3′(x3,y3,z′3)通过坐标投影，可以将信标节点投影到与未知节点S同一高度的水平面上，得到3个新的信标节点坐标即A1(x1,y1,z),A2(x2,y2,z),A3(x3,y3,z)，然后利用三边测量法即可得到未知节点的平面坐标。如图3所示，h代表未知节点到巷道地面的高度；d1,d2分别表示未知节点到信标节点A1,A1′的距离；r1,r2,r3分别表示将信标节点投影到同一平面后，未知节点与投影节点A1、A2、A3的距离；角度θ表示投影平面与SA1′的夹角。可将信标节点A1(x1,y1,z1)投影到与未知节点同一高度的横截面上，得到A1(x1,y1,z)，则有：
其中Δz是已知数，代表每对信标节点Z轴坐标差即巷道的高度。利用同样方法可求出r2,r3。已知r1,r2,r3，运用式(2)即可求出未知节点的X,Y轴坐标。同时得出未知节点的Z轴坐标z=z1′+h，综合以上，即可得到未知节点S的坐标S(x,y,z)。3DL.RD算法的基本步骤如下。
步骤1信标节点以固定的发射功率周期性地发送自身信息：节点ID、自身三维坐标。
步骤2未知节点收到信息后，对于同一个信标节点，只记录其最大RSSI值；并将信标节点按其RSSI值由大到小排序，并建立以下集合：
1)信标节点集合Beacon_set={A1,…,Ai,Aj,…,An},其中Ai的RSSI值≥Aj的RSSI值;
2)根据RSSI值估算出的未知节点到信标节点距离的集合 Dis_set={d1,d2,…,dn};
3)信标节点的三维坐标集合Position_set={(x1,y1,z1),(x2,y2,z2),…,(xn,yn,zn)}
步骤3选择信标节点集合中的前m个成对信标节点，生成C3m集合，对未知节点的坐标进行估计。
1)根据式(6)计算出未知节点与投影节点的距离r1,r2,r3以及与信标的高度差h。
2)利用式(2)即可得出未知节点的X,Y轴坐标；再利用未知信标与多个信标的高度差的平均值即可求出未知节点的Z轴坐标。
步骤4位置求精。为了求出准确的未知节点坐标，可重复步骤3，多次计算取平均值。
2.2误差分析
本算法的误差主要由测距误差和定位误差两部分组成，下面分别加以分析。
2.2.1测距误差
由于煤矿井下多为狭长空间,多径效应明显,信号衰落快,RSSI受环境的影响较大，无线传输应采用屏蔽模型。为减小测距误差，参考文献［1］中动态路径损耗指数获取算法来计算巷道内实际环境下的路径衰落指数η,以提高RSSI测距算法对环境的适应性，将测距误差降低到15%～20%。
2.2.2定位误差
假设在二维平面下未知节点S的实际坐标为(x,y)，定位估算的坐标为(x′,y′)，实际坐标与估算坐标的偏差用(Δx,Δy)表示。未知节点与某一信标节点的实际距离为di,根据RSSI估算出的距离为di′,实际距离与估算距离的误差Δdi=di－di′。
3仿真与分析
为了验证提出的3DL.RD算法在定位精度、能耗方面的优点，本文进行了仿真实验，并与极大似然算法(maximum likelihood estimation)以及文献［5］提出的带盲区巷道网络人员全局定位算法（以下简称分布式全局定位）进行了对比。本文采用网络仿真工具OMNET++进行仿真，由于煤矿井下巷道的长度通常在几百米甚至几千米，巷道的宽度和高度在不同的地方略有不同，但是大都在10m左右，因此将仿真区域大小设置为200m×10m×5m。未知节点总数为80个，信标节点按照2.1节介绍过的规则进行部署，通过编写NED文件，利用OMNeT++中的子模块、门、参数、链接、网络等建立规则的网络拓扑结构，编译后生成拓扑结构文件。节点通信半径取50m（参照TelosB mote），这样可以降低信标节点的密度，对硬件的要求不高，同时达到良好的三维网络覆盖率，具有较好的综合效果。节点的连通度为10，仿真的MAC协议采用的是802.15.4，无线信号传输采用屏蔽模型，路径损耗指数参考了文献［1］中动态路径损耗指数获取算法来计算巷道内实际环境下的路径衰落指数η,参考距离d0=1m，高斯分布随机变量Xσ的标准差取值为4.0。实验结果是重复50次运行的平均值。实验主要根据以下指标进行性能评估。
1)定位精度。定位精度一般用估计坐标和实际坐标之间的误差与节点的通信半径的比例表示，数值越小说明定位精度越高。
2)算法稳定性。节点定位时需要利用RSSI进行测距，由于环境的影响，测距误差不可避免。如果定位算法随着测距误差的累积使得定位误差失去控制，则该算法是不稳定的。
3）算法的能耗。能耗是对无线传感器网络的设计和实现影响最大的因素之一。由于传感器节点电池能量有限，因此在保证定位精度的前提下，与功耗密切相关的定位所需的计算量、通信开销是一组关键性指标。
图4显示了未知节点的定位精度与信标节点密度的关系。信标节点密度指一跳通信范围内平均信标节点数。图4显示的是平均测距误差为15%时，信标节点的数量取10、12、14、20、26个时三个算法定位精度的比较。图片
图4未知节点的定位精度与信标节点密度的关系
从图4可以看出3DL.RD算法的平均定位精度优于另外两种算法。信标节点在初期规则部署时需要较大的人工，但是与信标节点的随机放置策略相比，在定位精度上具有明显优势。此外，煤矿井下巷道内不同位置对传感器节点的覆盖和通信要求是不同的，不同的传感器节点具有显著的位置特征，如果采用随机放置策略，很难保证煤矿井下监控的位置要求。因此，本文提出的规则部署策略，能较好地满足煤矿井下不同监控对节点位置的需求。
图5分别显示了不同测距误差对三种算法的定位误差的影响，由图5中可以看出随着测距误差的增加,三种定位算法的定位精度都有增大的趋势。但是与极大似然算法相比，测距误差对3DL.RD算法定位精度的影响较小。原因是3DL.RD算法简化了计算步骤，减少了运算次数，因此减少了误差积累，保证了算法具有较好的稳定性。具体在2.2.2节已做过理论分析。与3DL.RD算法相比，测距误差对分布式全局定位算法的定位精度影响较小，原因是该算法只对节点做局部（即各个水平面）定位，未知节点Z轴坐标是根据信标节点已知的Z轴坐标变换计算得出的，Z轴坐标不受测距误差的影响。图片
图5测距误差对定位误差的影响
节点的能耗主要从节点通信量与节点计算量来分析。本文提出的定位算法只需在单跳模式下，假设某一周期内(传送1b数据),未知节点只需要接收信标节点发送过来的位置信息，相邻节点之间不需要通信，因此网络上总的能耗为:ES=ESS+ESR
ESS=(Eelec+Eampdk)m
ESR=Eelecm其中：ESS是信标节点发送数据的能耗；ESR是未知节点接收数据的能耗；Eelec是发送器或接收器的功耗；Eamp为发送放大器的功耗；d为传输距离；k为由环境决定的无线传输损耗指数；m为参与定位的信标节点个数。文献［5］提出的分布式全局定位算法，首先在一跳范围内计算出局部坐标，通过多跳路由方式将自身位置信息传送到网关(sink节点)。sink节点把得到的原始位置信息经过初步处理后通过总线传送到基站，再传送给上位计算机进行三维坐标变换。这里只分析该算法未知节点到sink节点之间的通信能耗，由于其sink节点到上位机之间通过总线连接，其通信能耗可忽略。
对于多跳通信模式,在以通信半径形成的圆形域内,第i层环内的每一个传感器节点中继的数据包数量ki［8］为:
ki=［R2－(ir)2］［r2(2i－1)］; i=1,2,…，n其中：R为通信半径；r为多跳通信模式中每一层环的厚度。此时,第i层环上的每个传感器节点不仅要中继ki个数据包,还要传输自身的数据包。对于某一周期(传送1b数据)内,其发送能耗为:EMS=ki(2Eelec+Eampdk)+(Eelec+Eampdk)其中第一层（sink节点附近）的节点发送能耗最大,即:
EMS(1,R)=(R2－r2)(2Eelec+Eampdk)r2+
(Eelec+Eampdk)
其接收能耗则为：
EMR=k1Eelec
分布式全局定位算法中，第一层（sink附近节点）的总能耗=EMS(1,R)+EMR。由此可以看出，文献［5］提出的算法会使sink节点附近的通信压力增大，使周围节点生命周期快速耗尽。
极大似然估计算法由于需要更多的信标辅助定位，其通信能耗也高于3DL.RD算法。与两者相比3DL.RD算法在通信能耗上具有明显优势。
节点的计算量在本文第1章里已经做了分析，图6显示了不同信标节点密度下三种算法的时间开销。图片
图6三种算法的计算量对比
4结语
本文分析了二维平面和三维空间下节点定位在计算复杂度、定位误差方面的差异，提出了一种基于信标节点规则部署的煤矿井下无线传感器网络节点三维定位算法(3DL.RD)。理论分析和仿真实验均表明，该算法具有计算量小、通信量
小、定位精度好以及稳定性好等特点，克服了目前煤矿井下无线传感器网络节点三维定位精度差、功耗高等问题。参考文献:［1］
乔钢柱，曾建潮.信标节点链式部署的井下无线传感器网络定位算法［J］.煤炭学报，2010,35（7）：1229-1233.
［2］
田丰,秦涛,刘华艳,等.煤矿井下线型无线传感器网络节点定位算法［J］.煤炭学报，2010,35(10)：1760-1764.
［3］
张共会,邓志东.基于无线传感器网络的地下矿工定位算法［J］.计算机测量与控制,2008,16(12):2003-2005.
［4］
戴桂兰,赵冲冲,邱岩.一种基于球面坐标的无线传感器网络三维定位机制［J］.电子学报, 2008, 36(7):1297-1303.
［5］
刘志高,李春文,耿少博,等. 带盲区巷道网络人员全局定位系统［J］.煤炭学报，2010,35(8):236-242
［6］
LIU ZHIGAO, LI CHUNWEN, WU DANCHEN, et al.A wireless sensor network based personnel positioning scheme in coal mines with blind areas［J］. Sensors， 2010, 10（11）:9891-9918.
［7］
王雪.无线传感网络测量系统［M］.北京：机械工业出版社，2008.
［8］
武俊,胡敏,朱继华. 基于传感器网络通信环境的节点覆盖控制分析与研究［J］.计算机应用，2006,26（12）：2820-2868.
［9］
成小良,邓志东,董志然.基于无线通信和计算特征分析的能耗模型［J］.计算机研究与发展，2009,46（12）：1985-1993.
［10］
孙利明.无线传感器网络［M］.北京:清华大学出版社, 2005.
［11］
HAZAS M, WARD A. A high performance privacy.oriented location system［C］// Proceedings of the 1st IEEE International Conference on Pervasive Computing and Communications. Washington, DC: IEEE Computer Society,2003:216-233.
［12］
CAPKUN S, HAMDI M, HUBAUX J P. GPS.free positioning in mobile Ad.Hoc networks［J］. Cluster Computing,2002,5(2):157-167.
［13］
SEIDEL S Y, RAPPAPORT T S. 914 MHz path loss prediction models for indoor wireless communications in multifloored buildings[J].IEEE Transactions on Antennas and Propagation, 1992,40(2):209-217.
［14］
汪摇炀,黄刘生,肖明军,等. 一种基于RSSI 校验的无线传感器网络节点定位算法［J］. 小型微型计算机系统,2009,30(1):59-62.
［15］
周公博.面向窄长空间的无线传感器网络可靠性关键技术研究［D］.徐州:中国矿业大学,2010.
［16］
DEBORAH E. Wireless sensor networks tutorial Part Ⅳ:Sensor network protocols［R］. Atlanta,Georgia,USA:WPP,2002:23-28.