DOI: 10.11817/j.issn.1672-7207.2016.03.028

基于改进遗传算法的矿井人员定位新算法

李宁^{1, 2}，王李管^{1, 2}，贾明涛^{1, 2}，陈建宏¹

(1. 中南大学 资源与安全工程学院，湖南 长沙，410083；

2. 中南大学 数字矿山研究中心，湖南 长沙，410083)

摘要：为了提高矿井人员定位精度，根据矿井巷道基站布设的实际情况，以无线信号传输理论模型为基础，提出周期性获取信号传输路径衰减指数的加权平均值，通过分析基站与标识卡之间的通讯约束条件，并借助改进的遗传算法提出矿井人员定位新算法，再利用MATLAB软件在相同条件下与加权质心算法和直接测距算法进行仿真对比。研究结果表明：新算法定位精度较高，同时3种定位算法的定位精度受巷道宽度影响较大。新算法不仅降低了人员定位的误差，而且具有较强的稳定性，适合各类复杂的巷道环境，为矿井人员精确定位提供了新方法。

关键词：人员定位；综合路径衰减指数；信号传输模型；改进的遗传算法；定位精度

中图分类号：TD676          文献标志码：A         文章编号：1672-7207(2016)03-0929-07

New personnel localization algorithm in mine based on improved genetic algorithm

LI Ning^{1, 2}, WANG Liguan^{1, 2}, JIA Mingtao^{1, 2}, CHEN Jianhong¹

(1. School of Resources and Safety Engineering, Central South University, Changsha 410083, China;

2. Digital Mine Research Center, Central South University, Changsha 410083, China)

Abstract: In order to improve the accuracy of the mine personnel localization, the comprehensive path attenuation index which is a weighted average of the periodic signal transmission path was proposed based on the actual situation of the mine roadway base station layout and the wireless signal transmission theory model. Through the analysis on communication constraints of between reference nodes and locating node, a new algorithm of locating node coordinates was developed combined with the improved genetic algorithm. The direct approach algorithm was compared with weighted centroid algorithm in MATLAB. The results show that localization precision of the new algorithm is higher, and at the same time localization precision of three localization algorithms is greatly influenced by roadway width. The improved personnel localization algorithm greatly reduces the personnel localization error and it is suitable for complex roadway environment, which provides a new method for the mine personnel localization.

Key words: personnel localization; comprehensive path attenuation index; signal transmission model; improved genetic algorithm; positioning accuracy

由于矿产资源需求量的增加以及浅部资源的不断消耗，国内外大多数矿山逐渐进入深部开采状态，从而导致矿山企业面临的安全问题变得更加突出。岩爆、透水以及瓦斯等事故高频率的发生使得矿山企业不仅需要对开采环境做到及时预测，同时需在事故发生后能对受害人员进行准确定位，为救援工作提供可靠的信息。随着矿山数字化进程的不断推进，信息化技术、智能测控技术以及自动化等技术在矿山得到广泛应用，使得对矿井工作人员进行精确定位成为可能。针对无线信号的定位方法有很多学者进行了研究，同时提出了很多相关的定位算法。根据定位机制的不同，定位算法主要分为基于测距(range-based)和无需测距(range-free) 2类。基于距离的定位算法有到达时间(time of arrival, TOA)算法、到达时间差(time difference of arrival, TDOA)算法、到达角(angle of arrival, AOA)算法、接收信号强度指示(received signal strength indication, RSSI)算法等；无需测距的定位算法有：质心算法、MDS-PAP算法、DV-hop算法、APIT算法以及Amorphous算法。由于上述定位算法使用条件的限制以及矿山巷道的实际情况，根据无线信号在传输过程中的损耗，利用无线信号传输理论模型，计算发射节点和接收节点间的距离，再由三边测量法即可实现定位的RSSI算法运用较为普遍^[1-3]。考虑到矿井巷道狭长，使得无线信号的传输受到反射、衍射、多径传播以及非视距的影响，测得的RSSI值具有较大误差，即使在相同条件下，多次测得的RSSI值也将产生明显的波动，从而导致算法的定位精度不够，定位结果与实际位置差距较大。为了提高RSSI定位算法的定位精度，很多学者提出了改进方法。吕振等^[4]提出了基于捷联惯性导航的井下人员精确定位算法，该算法需要增加额外的硬件设备用来检测人员的三轴加速度和角速度的数据，使得定位过程更加复杂化；韩东升等^[5-6]提出了基于RSSI的加权质心定位算法，该算法根据标识卡接收到的无线信号强度综合考虑了基站对标识卡的影响权重，算法定位流程简单，一定程度上提高了定位精度。本文作者根据矿井巷道参考节点的布设方式和定位区域的实时环境，考虑到相邻基站间相互影响权重，提出周期性获取综合路径衰减指数()的策略，再根据基站无线信号传输范围建立人员定位的数学模型，利用改进的遗传算法^[7-8]进行求解，计算结果即为人员所处位置，算法可靠实用，在减少累积误差出现的同时，增加了对各类复杂矿井环境的适  应性。

1  Zigbee人员定位系统架构

矿山井下环境复杂，主要有运输大巷、穿脉、重点硐室以及采区等区域。根据各区域的不同特点，采用有线和无线混合架构的网络模式，构成矿山的人员定位系统。Zigbee是基于IEEE标准的802.15.4无线标准研制开发的，Zigbee人员定位系统由监控中心、定位服务器、数据交换机、基站和标识卡等组成^[9-10]，如图1所示。

数据交换机是整个网络中数据传输及交换的关键，首先把由定位软件系统配置的各参考节点相关数据准确发送到对应的基站；其次需要反馈标识卡获得的有效数据(例如标识卡位置信息)，并在定位软件系统中进行显示。其性能须满足整个矿山人员定位系统及监测监控系统的需要。

基站是人员定位系统中井下固定设备，安装在巷道两帮及其他重点定位区域，具有各自静态IP，位置信息已知，由信号收发模块、数据交换模块和电源模块组成，具备有线和无线2种通信模式。

图1  Zigbee人员定位系统架构

Fig. 1  Architecture of Zigbee personnel localization system

标识卡是人员定位系统中井下移动设备，配备给每位下井工作人员，由信号收发模块、数据处理模块和电源模块组成，通过无线方式与基站进行通讯，获取基站的位置信息和RSSI值，根据相关算法确定本身位置信息，并由基站与数据交换机发送至定位服务器，实时显示井下工作人员所处地点。

2  井下人员定位问题描述

2.1  巷道人员定位基站布设

由于受到矿井巷道狭小断面的限制，Zigbee基站需根据其信号覆盖范围采用交叉链式方式布设，将基站以已知的距离安装在巷道的两帮，距离底部1.5 m左右，坑道、岔道等信号不易到达区域适当减少基站间距离，保证多个基站间能相互通讯，巷道内基站布设如图2所示。每个下井工作人员配备一张标识卡，根据标识卡的位置对工作人员进行精确定位。

图2  巷道内基站布设

Fig. 2  Deployment of base station in roadway

2.2  无线信号传输模型

无线信号传输模型有自由空间模型、双向地面反射模型和屏蔽模型，屏蔽模型将理想的圆形模型扩展为更合适的统计模型，更具有一般性而被广泛应用，因此，采用比较适合矿井巷道的屏蔽模型(Shadowing模型)^[11-13]来表述人员定位无线信号的传输衰减，其公式为

             (1)

式中：为距离信号发射端r₀处接收到的信号功率；为距离信号发射端处接收到的信号平均功率；为接收信号功率的变化修正，对数正态随机变量；为综合路径衰减指数，受环境、障碍物等影响。

通过实验研究表明，对计算结果影响不大，为了便于计算，式(1)可简化为

         (2)

式中： 为距离信号发射端r处接收到的RSSI强度，dBm；为距离信号发射端r₀处接收到的RSSI强度，dBm。

由式(2)可知：

            (3)

由式(3)即可计算基站与相应标识卡之间的距离，井下人员定位过程可以描述为通过基站坐标以及标识卡与基站之间的距离r_ij(,)来估计标识卡的坐标 ()。由于矿山巷道环境变化频繁，使得信号路径衰减指数处于动态变化过程中，导致距离r_ij并不是标识卡与基站间的实际距离，存在一定的误差。

3  基于改进遗传算法的定位算法

3.1  路径衰减指数的周期性获取算法

巷道内基站布设见图2，基站间距离已知，且具有唯一识别性，再周期性记录基站之间通讯的无线信号强度。路径衰减指数求解过程如图3所示，以基站C₁为基准，其他节点以此类推，假设与基准基站可相互通讯的参考基站有()，在一个周期(T)内，参考基站到基准基站的RSSI值表示为，根据式(3)即可得到对应参考基站与基准基站间的路径衰减指数，再根据参考节点对基准节点的影响权重，计算对应的综合路径衰减指数：

            (4)

图3  路径衰减指数求解过程

Fig. 3  Solving process for path attenuation index

由此可知，权重可表示为

                 (5)

算法中周期性计算综合路径衰减指数，比较准确地反映了两基站间的巷道环境对无线信号传输的影响，经信号传输衰减模型公式计算可较准确获得基站与相应标识卡之间的距离。

3.2  定位过程建模

定位^[14]模型如图4所示。设标识卡为()，基站为()，且基站无线信号的传输半径为R，当标识卡接收到基站的无线信号后，即开始进行定位计算。

图4  定位模型示意图

Fig. 4  Sketch map of localization model

由图4可知，标识卡能与对应基站通信的约束方程表示为

        (6)

式中：，。

由式(3)和(4)可知：标识卡与对应基站间的距离可用r_ij(，)近似表示，则式(6)可变换为

        (7)

通过改变获取综合路径衰减指数的方法，提高基站与标识卡间距离的计算精度，但是仍然不可避免地存在误差，因此，需以式(7)为依据，通过改进参数优化算法的方法，最大限度地降低由于测量距离产生的误差的影响。

针对任意基站，可定义：

       (8)

为测量距离与实际距离的误差方程，从而可知任意标识卡的总约束条件为

                (9)

使得L_j=0的解即为最优解，其目标函数为

            (10)

3.3  基于改进遗传算法的定位算法

3.3.1  编码方式

算法采用二进制编码，每个标识卡坐标被编码为2组二进制码，二进制码的首位为符号位，“0”表示二进制码对应的基因型为正数，“1”表示二进制码对应的基因型为负数，初始种群随机生成。

3.3.2  适应度函数设计

各标识卡二进制编码的取值范围肯定大于能与其通信的基站所在区域，所以适应度函数必须包含惩罚函数项，采用如下公式：

   (11)

     (12)

式中：为惩罚系数。

由式(11)和(12)可知：若满足约束条件，则=0，否则使用惩罚函数。

3.3.3  选择算子设计

选择操作在子种群内部进行，用轮盘式选择进行下一代复制的操作，同时使用最佳个体保留策略，确保算法的收敛^[15-16]。由适应度函数的定义，个体适应度为正值，不需要考虑个体适应度之间的数值差异，避免种群空间占满优秀个体而导致算法过早收敛。

3.3.4  改进的交叉算子设计

在运用传统遗传算法交叉算子时，会出现基因重复、父代的优秀基因子代不能保留和编码条件需改动子代的缺点。遗传交叉的主要目的是子代尽可能继承父代的优秀基因，为使交叉后的子代保留父代更多的优秀基因，可用贪心交叉算子加以改进。

贪心算法在求解问题时，以当前看来是最好的选择为标准，省去了为找最优解要穷尽所有可能所要耗费的大量时间，充分利用染色体的局部信息指导遗传进化搜索。

3.3.5  变异算子设计

变异可以保持群体的多样性，避免求解过程陷入局部最优，采用二进制编码中符号位变异与数值位变异相结合的方式^[17-18]。符号位变异采用单点基本变异算子，数值位变异采用倒位变异算子。

3.3.6  终止条件

为了确保算法的收敛性，采用最大进化代数与设定收敛条件相结合的终止条件。

4  仿真实验及结果分析

为了检验算法的性能，用Matlab软件进行定位仿真实验，并与加权质心算法、直接测距法进行对比。根据矿井巷道的实际情况，设置如下的仿真环境：巷道宽度分别设置为3，5和7 m，长度为400 m，便于对照分析。假设基站的无线信号传输半径R=50 m，用8个标识卡进行定位仿真，参考节点沿巷道两帮每隔一定距离进行布设，分别进行1 000次仿真实验。

定义标识卡的点位误差e和横向误差e₁，假设标识卡的实际坐标为D₀(x₀, y₀)，而通过定位算法计算得到的坐标为()，则有：

         (13)

               (14)

通过3种不同定位算法仿真得到的定位结果见表1~3。

根据式(13)~(14)以及定位仿真结果得到定位误差如表4所示。

由表1~4可知：标识卡的横向坐标误差比纵向坐标误差大，且随着巷道宽度的增加，无线信号传输过程中的反射、衍射等现象的减少，使得定位的整体误差逐渐降低。为了直观表达3种不同定位算法的性能差异，根据表4相关数据，绘制出不同巷道宽度下3种定位算法的定位误差曲线如图5所示。

表1  本文改进算法仿真结果

Table 1  Simulation results of this paper improved algorithm

表2  加权质心算法仿真结果

Table 2  Simulation results of weighted centroid algorithm

表3  直接测距算法仿真结果

Table 3  Simulation results of direct approach algorithm

表4  3种不同算法定位误差

Table 4  Localization error of three different algorithms

图5  定位误差对比

Fig. 5  Comparison of localization error

由图5可知：本文改进算法定位精度较加权质心算法和直接测距算法有很大提高，且波动性不明显，降低了巷道复杂情况对定位精度的影响；且第1个标识卡的定位误差都较大，主要是因为参与定位的基站较少，随着基站数的增加，定位精度明显提高。同时，本文改进算法不需要升级任何硬件设备，更能满足实际的需求，而且节点通信量较小，能耗低。

5  结论

1) 以无线信号传输理论模型为基础，提出了周期性获取信号传输路径衰减指数的加权平均值，即综合路径衰减指数，再根据改进的遗传算法计算标识卡坐标的新算法，通过与加权质心算法以及直接测距法仿真实验对比发现，定位精度明显提高，且较为稳定。

2) 巷道宽度对无线信号的传输影响较大，随着巷道宽度的增加，3种定位算法的定位精度逐渐提高；当巷道宽度d=7 m时，本文改进算法使得定位误差平均降到1 m以下，适用性较高。

3) 矿井巷道内人员定位基站的布设一定在视距范围内，而本文改进的定位算法在非视距条件下，对矿井人员进行定位时结果存在较大误差，所以非视距的矿井人员精确定位将是下一步研究的重点。

参考文献：

[1] 张治斌, 徐小玲, 阎连龙. 基于Zigbee井下无线传感器网络的定位方法[J]. 煤炭学报, 2009, 34(1): 129-132.

ZHANG Zhibin, XU Xiaoling, YAN Lianlong. Underground localization algorithm of wireless sensor network based on Zigbee[J]. Journal of China Coal Society, 2009, 34(1): 129-132.

[2] 龙铁光, 黄廷磊. 无线传感器网络中基于RSSI算法的优化[J]. 计算机系统应用, 2013, 22(1): 107-110.

LONG Tieguang, HUANG Tinglei. Optimization of RSSI algorithm in wireless sensor network[J]. Computer System and Applications, 2013, 22(1): 107-110.

[3] 章坚武, 张璐, 应瑛, 等. 基于Zigbee的RSSI测距研究[J]. 传感技术学报, 2009, 22(2): 285-288.

ZHANG Jianwu, ZHANG Lu, YING Ying, et al. Research on distance measurement based on RSSI of Zigbee[J]. Journal of Transduction Technology, 2009, 22(2): 285-288

[4] 吕振, 刘丹, 李春光. 基于捷联惯性导航的井下人员精确定位系统[J]. 煤炭学报, 2009, 34(8): 1149-1152.

L Zhen, LIU Dan, LI Chunguang. The precise positioning system of the mine personnel in coal pit based on strap down inertial navigation[J]. Journal of China Coal Society, 2009, 34(8): 1149-1152.

[5] 韩东升, 杨维, 刘洋, 等. 煤矿井下基于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.

[6] 赵昭, 陈小惠. 无线传感器网络中基于RSSI的改进定位算法[J]. 传感技术学报, 2009, 22(3): 391-394.

ZHAO Zhao, CHEN Xiaohui. An improved localization algorithm based on RSSI in WSN[J]. Chinese Journal of Sensors and Actuators, 2009, 22(3): 391-394.

[7] 刘荷花, 崔超, 陈晶. 一种改进的遗传算法求解旅行商问题[J]. 北京理工大学学报, 2013, 33(4): 390-393.

LIU Hehua, CUI Chao, CHEN Jin. An improved genetic algorithm for solving[J]. Transactions of Beijing Institute of Technology, 2013, 33(4): 390-393.

[8] 汪波, 薛磊. 基于遗传算法的TDOA定位系统的最优布站算法[J]. 系统工程与电子技术, 2009, 31(9): 2125-2128.

WANG Bo, XUE Lei. Station arrangement strategy of TDOA location system based on genetic algorithm[J]. Systems Engineering and Electronics, 2009, 31(9): 2125-2128.

[9] KIM W H, LEE S, HWANG J. Real-time energy monitoring and controlling system based on Zigbee sensor networks[J]. Procedia Computer Science, 2011, 5: 794-797.

[10] WANG Longkang, NIE Baisheng, ZHANG Ruming, et al. Zigbee-based positioning system for coal miners[J]. Procedia Engineering, 2011, 26: 2406-2414.

[11] 乔钢柱, 曾建潮. 信标节点链式部署的井下无线传感器网络定位算法[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.

[12] 周小艳, 何为, 胡国辉. 基于Zigbee无线传感器网络的变电站人员定位的改进算法研究[J]. 电力系统保护与控制, 2013, 41(17): 56-62.

ZHOU Xiaoyan, HE Wei, HU Guohui. Research on the improved personnel localization method in transformer substation based on Zigbee wireless sensor network[J]. Power System Protection and Control, 2013, 41(17): 56-62.

[13] 王金鑫, 赖旭芝, 吴敏, 等. 基于遗传算法的三维无线传感器网络定位新算法[J]. 高技术通讯, 2008, 18(6): 579-584.

WANG Jinxin, LAI Xuzhi, WU Min, et al. New positioning algorithm for three-dimension wireless sensor networks based on genetic algorithm[J]. High Technology Letters, 2008, 18(6): 579-584.

[14] 刘平, 李国民. 一种用于井下人员定位的TOA定位算法研究[J]. 西安科技大学学报, 2007, 27(3): 439-442.

LIU Ping, LI Guomin. A TOA-based people locating algorithm in coal mine[J]. Journal of Xi’an University of Science and Technology, 2007, 27(3): 439-442.

[15] 雷霖, 李伟峰, 王厚军. 基于遗传算法的无线传感器网络路径优化[J]. 电子科技大学学报, 2009, 38(2): 227-230.

LEI Lin, LI Weifeng, WANG Houjun. Path optimization of wireless sensor network based on genetic algorithm[J]. Journal of University of Electronic Science and Technology of China, 2009, 38(2): 227-230.

[16] RABAEY J M. Roundy picorodio supports Ad Hoe ultra-low power wireless networking[J]. Computer, 2000, 33(7): 42-48.

[17] BULUSU N. GPS-less low cost outdoor localization for very small devices[J]. IEEE Personal Communications Magazine, 2000, 7(5): 28-34.

[18] 章磊, 段莉莉, 钱紫鹃, 等. 基于遗传算法的WSN节点定位技术[J]. 计算机工程, 2010, 36(10): 85-87.

ZHANG Lei, DUAN Lili, QIAN Zijuan, et al. WSN node localization technology based on genetic algorithm[J]. Computer Engineering, 2010, 36(10): 85-87.

(编辑  赵俊)

收稿日期：2015-03-20；修回日期：2015-05-13

基金项目(Foundation item)：国家高技术研究发展计划(863计划)项目(2011AA060407)；国家自然科学基金资助项目(51374242)；国家留学基金委资助项目(201306370143) (Project(2011AA060407) supported by the National High Research Development Program (863 Program) of China; Project(51374242) supported by the National Natural Science Foundation of China; Project(201306370143) supported by China Scholarship Council Foundation)

通信作者：李宁，博士研究生，从事数字矿山及智能采矿技术研究；E-mail:13875910191@163.com