0 引言
煤矿井下无线精确定位技术可为矿山物联网各种应用提供基础信息[1-2]。实现无线精确定位的手段比较多，如可利用超声波[3]、图像[4]、超宽带信号[5]等。这些定位方法可以达到米级、厘米级甚至更高的定位精度。然而，这些方法有的需要定位信号接收机和定位基站(锚节点)严格时间同步，有的需要布置专用的定位基站并铺设连接定位基站的专用通信线缆，因此，存在造价高、维护量较大的问题。
基于井下无线网络信号强度指示(Receive Signal Strength Index, RSSI)的定位系统是井下精确定位的研究热点之一。在各种定位方法中，获取RSSI的软硬件实现成本最低，因此，使用RSSI作为定位依据是最经济的方法。但是，当未知节点离基站相对较远时，该方法定位精度较差。特别是在定位基站较少的情形下，不仅定位精度较差，定位结果也不稳定。已有不少提高定位精度的算法，但这些算法只利用了定位基站和未知节点之间的距离信息，而未知节点和未知节点之间的距离(特别是未知节点和邻居节点之间的距离)是较准的测距信息，将该部分信息充分利用，将有助于提高定位精度和稳定性。因此，本文提出了一种基于节点协作的煤矿井下无线精确定位算法，利用未知节点之间的距离来提高定位基站密度不高条件下的定位精度和鲁棒性。
1 无线精确定位算法研究进展
1.1 定位算法分类
利用无线网络信号进行定位的方式分为测距式和非测距式2种[6]。非测距式定位算法不直接计算未知节点位置，而是通过某种映射关系获得被测节点位置。该算法首先建立无线网络信号特征的“指纹”数据库，通过“指纹”预测模型来预测节点位置[7]。非测距式定位算法与定位场景关系密切，当场景转换时需要重新建立映射关系。测距式定位算法主要是通过计算特定的信息值建立未知节点和已知节点的关系，从而得出未知节点的位置。测距式定位算法在煤矿井下的应用范围相对更宽。
1.2 经典多边定位算法
假设位置信息已知的定位基站有M个，第k个定位基站的二维坐标为ak=[ak,1,ak,2]T，未知节点二维坐标为x=[x1,x2]T，未知节点到基站之间的距离为dk。基于测距的多边定位问题可描述为根据式(1)求解x。
经典的多边定位算法是通过减某个等式的方法将式(1)转换为线性方程：
Ax=b
(2)
式中A,b为系数。
利用最小二乘法可得未知节点坐标为
当定位基站为3个时，该算法即为经典三边定位算法，未知节点坐标公式退化为
指数路径损耗模型为
式中：P为距离d处的接收功率；P0为参考距离d0处的接收功率；γ为路径损耗；d为接收节点与发送节点之间的距离；n为信道噪声。
从式(4)可看出，节点间距越大，信号衰减曲线越平坦。这就意味着，在相同噪声情况下，节点间距越大，测距误差越大。文献[8-9]理论分析结果表明，测距误差越大，定位误差越大，定位误差概率分布越散，即定位的稳定性越差。
1.3 煤矿定位算法研究现状
针对煤矿的特殊情况，文献[10]提出一种计算巷道环境内实际电磁环境路径衰落指数的方法，提高了RSSI算法对环境的适应性。文献[11]考虑到路径损耗受环境参数影响，利用加权质心定位算法来计算节点位置坐标，增强了定位的自适应性和鲁棒性。文献[12]设计了将路径损耗指数和RSSI进行加权处理的加权质心混合定位算法。文献[13]针对巷道狭窄严重影响非线性测量误差的问题，对RSSI值进行优化处理，提出动态RSSI相似度定位算法。文献[14]利用网络链路质量指示作为定位基站的相似性度量指示，提出了一种矿井巷道三阶段定位方法。文献[15]将固定的2个信标节点之间的距离作为距离约束条件，提出一种基于距离约束的矿井目标定位算法。
上述算法的出发点是提高测距精度或降低定位误差概率分布。这些算法要求布置比较密集的定位基站，成本较高。另外，上述算法没有利用未知节点之间的距离信息实现定位。事实上，将未知节点同时视为其他未知节点的定位基站，意味着某个未知节点周围有很多的距离较近(测距准)的虚拟定位基站。本文算法的核心思想就是利用未知节点间的距离信息来提高定位精度。
2 基于节点协作的无线精确定位算法
2.1 算法模型
假设未知节点有N个，第i个未知节点坐标为xi，所有未知节点定位误差和最小的定位模型为
式中
表示求2-范数。
令第i个节点与第j个节点的距离为di,j，将未知节点之间的信息利用起来，则定位模型可设计为
式(6)所示的定位模型不仅利用了未知节点之间的距离信息，还实现了一次求解所有节点位置。进一步，考虑各个测量距离的可能误差不同，将式(6)修正为加权模型：
式中αi,k和βj,i表示测量距离的权重。
2.2 模型求解
式(7)所示的定位模型是一个非凸优化问题，利用鱼群算法等进化算法可以求解。但进化算法往往需要多次迭代计算，计算时间较长，同时解还不一定收敛。本文利用Canonical Duality[16-18]理论求解式(7)。
Canonical Duality理论主要解决形如式(8)的全局最优化问题：
式中：C为对称不定矩阵；f为二阶连续可微函数；W为关于y的函数。
Canonical Duality理论求解思路：利用几何变换ζ=Λ(y)构造Canonical函数V(ζ)，将W(y)拓展为Rn上的广义函数:
利用次微分包含定义Canonical对偶变量ζ，并构造V(ζ)的Canonical共轭函数，进而导出原问题的对偶函数Pd(ζ,σ)。理论上可证明，该解存在并且对偶函数的解就是原问题的解。
具体到求解式(7)，可构造如下对偶问题：
F(σ)=
(11)
G(ζ,σ)=2(Diag(F1(ζ))+Diag(F2(σ))+G3(ζ))
(12)
式中:d为由dk组成的矩阵;a为由ak组成的矩阵;e为单位向量;INN为单位矩阵元素。
2.3 算法描述
算法步骤如下：
(1) 获取未知节点和定位基站之间的距离di,k，同时获取未知节点之间的距离di,j。
(2) 利用获得的di,k和di,j，构造序列α′={di,k/∑∑di,k}(k=1,2，…,N)}和β′={di,j/∑∑di,j}(j=1,2，…,N;i≠j)}。将α′和β′按照距离进行反序构造序列α和β。
(3) 利用式(13)—式(15)构造F1(ζ)，F2(σ)和G3(ζ)。利用所构造的构造F1(ζ)，F2(σ)和G3(ζ)代入式(12)构造出G(ζ,σ)。
(4) 将已知的定位基站位置ak代入式(11)构建F(σ)。
(5) 将第(2)步、第(3)步和第(4)步构建的α，β，G(ζ,σ)和F(σ)代入式(10)，求解式(10)，获得
和
(6) 将
代入式(11)得到
将和代入式(12)得到
进而求出逆矩阵
利用式(16)求出各未知节点的位置值。
算法本身并不依赖测距的具体方法，因此算法第(1)步可利用任何测距方法。本文在后续的仿真及实验中利用式(4)实现所测量的信号强度值到距离的转换。
3 实验与分析
3.1 数值仿真实验
3.1.1 算法的定位精度
仿真场景设定：巷道长为50 m、宽为5 m，有3个位置固定的定位基站，并随机产生15个未知节点，如图1所示。
图1 仿真场景
Fig.1 Simulation scenario
本文算法定位精度和经典三边定位算法的比较如图2所示。从图2看出，经典三边定位算法的平均定位误差为4.9 m，本文算法的平均定位误差为2.5 m。式(7)所表示的算法模型的目标函数就是定位误差和最小，这也就决定了本文算法的整体效果最优。
图2 仿真得到的定位效果对比
Fig.2 Comparison of location accuracy of different algorithms got by simulation
从图2还可看出，单个未知节点的定位效果不一定最优。对于1号和8号未知节点，本文算法定位精度稍低于经典三边定位算法。这是因为测距误差会在各个节点之间分担。本次仿真中，1号和8号未知节点分担了其他节点的测距误差。
从图1可看出，1号未知节点和13号未知节点位置接近。但图2仿真结果显示，采用经典三边定位算法时这2个节点的定位精度差别大，而采用本文算法时这2个节点的定位精度接近。这是因为仿真时定位基站到2个未知节点的测距误差不同。与1号节点相比，13号未知节点到定位基站的测距误差较大，经典三边定位算法只利用定位基站到13号未知节点的距离信息，所以定位精度低。而本文算法不仅考虑了13号未知节点与定位基站之间的距离关系，还加权利用了其他未知节点的距离信息，提高了定位精度。
3.1.2 节点个数对定位精度的影响
在未知节点个数不同的情况下,本文算法的平均定位误差如图3所示。仿真时，节点位置和测量误差随机产生,平均定位误差值为500次仿真结果的平均值，共进行了500×19=9 500次仿真。
图3 节点个数对定位精度的影响
Fig.3 Influence of number of nodes on location accuracy
从图3可看出，随着未知节点个数的增加，平均定位误差呈明显下降趋势。该现象是合理的。未知节点个数越多，意味着定位误差被更多的节点分担，因此，平均定位误差自然下降。
图3还表明，平均定位误差不可能无限下降，当定位节点大于一定个数(本文设为16)时,平均定位误差趋向定值。多次仿真实验表明，定位误差的下限数值和仿真时噪声方差大小相关。
3.1.3 稳定性比较
仿真场景设定：巷道长为50 m、宽为5 m，有3个位置固定的定位基站，3个未知节点，具体布置如图4所示。其中，未知节点的位置主要根据文献[8]的理论和仿真结果选择。
图4 节点布置
Fig.4 Nodes arrangement
1号未知节点和2号未知节点的定位结果概率分布较好，而3号未知节点的定位结果概率分布较差。本次仿真中，三点三边定位误差的标准差为5.28，5.36和10.62。
图5是1号未知节点、2号未知节点和3号未知节点在噪声随机情况下的定位误差对比情况。从图5(a)可看出，本文算法提升了定位精度，而定位鲁棒性仅稍优于三边定位算法鲁棒性。图5(b)表明本文算法不仅定位精度高于三边定位算法，鲁棒性也高于三边定位算法。图5(c)清晰地表明本文算法的定位精度和鲁棒性都远优于多边定位算法。
(a) 1号未知节点
(b) 2号未知节点
(c) 3号未知节点
图5 未知节点定位误差
Fig.5 Locating error of unknown nodes
经过多次仿真可知，在质心附近，本文算法的定位精度和鲁棒性与三边定位算法基本相同；在其他位置，本文算法表现优于三边定位算法。
3.2 实验室测试
3.2.1 实验场景
实验使用CC2530节点作为定位基站和未知节点(如果是WiFi网络，将节点设置为AP模式，即可实现任意两点之间的信号强度值的采集)。实验时，定位基站、未知节点布置如图6所示，其中3号定位基站的位置取为坐标原点。
3.2.2 测距信息的获得
对距离节点1 m处的接收功率进行校准，路径损耗γ取2；然后对采集的RSSI进行预处理；最后利用式(4)将预处理后所得值映射成距离。
数据预处理分两步。第1步是对所采集到的原始数据进行高斯滤波处理，根据实验室实际环境设置置信区间，将置信区间内的数据值保留，并取其均值作为测量值。理论上，2个节点之间的收发RSSI值应对称。但实际应用中，由于无线芯片的个体差异，导致测量数据出现表1所示的不对称现象。因此，数据预处理的第2步是取两端测量均值作为两点之间的RSSI值。
图6 实验场景
Fig.6 Experiment scenario
表1 节点间信号强度实测数据
Table 1 Measured data of signal strength between nodes
根据所测得的信号强度值换算的距离见表2，本文算法与三边定位算法的误差比较结果如图7所示，未知节点个数对平均定位误差的影响如图8所示。
从图7和图8可以看出，实验结果和仿真结果一致。本文算法的定位误差被所有未知节点分担，实现了总体定位精度的提升和鲁棒性的提高；随着未知节点数目的增加，每个未知节点的平均定位误差减少，同时，平均定位误差下降趋势变缓。
3.3 算法复杂度分析
本文算法和三边定位算法一样，其算法复杂度决定于算法中的矩阵运算量。对于三边定位算法，根据式(3)可看出定位运算的规模和未知节点无关，仅和定位基站相关，因此，在基站个数为M时算法复杂度为O(M3)。本文算法利用了节点之间的信息，在基站个数为M、未知节点基站个数为N时算法复杂度为min{O((2M)3),O((2N)3)}。
表2 未知节点间的距离数据
Table 2 Distance data between unknown nodes m
图7 实验得到的定位效果对比
Fig.7 Comparison of location accuracy of different algorithms got by experiment
图8 未知节点个数对平均定位误差的影响
Fig.8 Influence of number of unknown nodes on average location error
本文算法的复杂度远大于三边定位算法。但仿真和实验结果表明，未知节点数为6时，定位误差就降为原来的一半。此时，所付出的计算成本约为1.6 s(计算平台：英特尔酷睿i7 7700HQ CPU，16 G内存)，所付出的计算成本是可接受的。
4 结论
(1) 提出了基于节点协作的无线精确定位算法，给出了未知节点误差和最小的加权非凸定位模型，并提出相应的不需要多次迭代计算的定位算法。
(2) 该算法利用所有节点之间的距离信息实现定位，与其他算法相比，单个未知节点定位精度未必最佳，但总体定位效果最优。
(3) 在定位基站布置稀疏的情况下(如定位基站数目为3)，该算法和其他算法相比，在定位结果精度和稳定性上具有明显优势。
(4) 该算法的复杂度较高，在M个基站、N个未知节点的情况下，复杂度为min{O((2M)3),O((2N)3)}。如何在定位精度和计算复杂度之间平衡，是笔者拟继续研究的内容。
参考文献(References)：
[1] 孙继平.煤矿物联网特点与关键技术研究[J].煤炭学报,2011,36(1):167-171.
SUN Jiping.Research on characteristics and key technology in coal mine Internet of things[J].Journal of China Coal Society,2011,36(1):167-171.
[2] 吴立新,汪云甲,丁恩杰,等.三论数字矿山——借力物联网保障矿山安全与智能采矿[J].煤炭学报,2012,37(3):357-365.
WU Lixin,WANG Yunjia,DING Enjie,et al.Thirdly study on digital mine:serve for mine safety and intellimine with support from IoT[J].Journal of China Coal Society,2012,37(3):357-365.
[3] SAINJEON F,GABOURY S,BOUCHARD B.Real-time indoor localization in smart homes using ultrasound technology[C]//Proceedings of the 9th ACM International Conference on Pervasive Technologies Related to Assistive Environments,Corfu,2016.
[4] ZAMIR A R,SHAH M.Accurate image localization based on google maps street view[C]//ECCV'10 Proceedings of the 11th European Conference on Computer Vision:Part IV,Heraklion,Crete,2010.
[5] 田子建,王宝宝,张向阳.一种基于非视距鉴别加权拟合的矿井超宽带定位方法[J].煤炭学报,2013,38(3):512-516.
TIAN Zijian,WANG Baobao,ZHANG Xiangyang.Mine ultra-wideband positioning method based on non line-of-sight identification weighted fitting[J].Journal of China Coal Society,2013,38(3):512-516.
[6] 胡青松,张申,吴立新,等.矿井动目标定位:挑战、现状与趋势[J].煤炭学报,2016,41(5):1059-1068.
HU Qingsong,ZHANG Shen,WU Lixin,et al.Localization techniques of mobile objects in coal mines:challenges,solutions and trends[J].Journal of China Coal Society,2016,41(5):1059-1068.
[7] NARZULLAEV A,PARK Y,YOO K,et al.A fast and accurate calibration algorithm for real-time locating systems based on the received signal strength indication[J].International Journal of Electronics and Communications,2011,65(4):305-311.
[8] YANG Z,LIU Y.Quality of trilateration:confidence-based iterative localization[J].IEEE Transactions on Parallel and Distributed Systems,2010,21(5):631-640.
[9] 孙波,刘冬阳,徐奉,等.基于RSSI的煤矿井下巷道定位技术误差分析[J].煤炭学报,2014,39(增刊2):609-614.
SUN Bo,LIU Dongyang,XU Feng,et al.Error analysis of RSSI-based location technology in coal mine[J].Journal of China Coal Society,2014,39(S2):609-614.
[10] 乔钢柱,曾建潮.信标节点链式部署的井下无线传感器网络定位算法[J].煤炭学报,2010,35(7):1229-1233.
QIAO Gangzhu,ZENG Jianchao.Localization algorithm of beacon nodes chain deployment based on coal mine underground wireless sensor networks[J].Journal of China Coal Society,2010,35(7):1229-1233.
[11] YI X,LIU Y,DENG L.A novel environment self-adaptive localization algorithm based on RSSI for wireless sensor networks[C]//IEEE International Conference on Wireless Communication,Networking and Information Security,Beijing,2010.
[12] 韩东升,杨维,刘洋,等.煤矿井下基于RSSI的加权质心定位算法[J].煤炭学报,2013,38(3):522-528.
HAN Dongsheng,YANG Wei,LIU Yang,et al.A weighted centroid localization algorithm based on received signal strength indicator for underground coal mine[J].Journal of China Coal Society,2013,38(3):522-528.
[13] TIAN F,DONG Y,SUN E,et al.Nodes localization algorithm for linear wireless sensor networks in underground coal mine based on RSSI-similarity degree[C]// 7th International Conference on Wireless Communications,Networking and Mobile Computing,Wuhan,2011.
[14] 裴忠民,邓志东,巫天华,等.矿井无线传感器网络三阶段定位方法[J].中国矿业大学学报,2010,39(1):87-92.
PEI Zhongmin,DENG Zhidong,WU Tianhua,et al.A novel three-phase localization method in coal mine wireless sensor networks[J].Journal of China University of Mining & Technology,2010,39(1):87-92.
[15] 刘晓阳,李宗伟,方轲,等.基于距离约束的井下目标定位方法[J].煤炭学报,2014,39(4):789-794.
LIU Xiaoyang,LI Zongwei,FANG Ke,et al.Underground target location method based on distance constraint[J].Journal of China Coal Society,2014,39(4):789-794.
[16] GAO D Y.Duality principles in nonconvex systems:theory,methods and applications[M].Boston:Springer,2000.
[17] 朱经浩,谭素娥.Canonical对偶理论在一类多项式全局优化中的应用[J].同济大学学报(自然科学版),2011,39(9):1373-1376.
ZHU Jinghao,TAN Su'e.Application of Canonical duality theory to global optimization with polynomials[J].Journal of Tongji University(Natural Science),2011,39(9):1373-1376
[18] GAO D Y,WU C.On the triality theory for a quartic polynomial optimization problem[J].Journal of Industrial and Management Optimization,2017,8(1):229-242.