近年来，针对建筑物倒塌、城镇火灾、地震等灾害场景应急定位难题，基于传统定位精度因子的单因子静态基站组网方式已难以兼顾灾害场景和环境信息的自组网体系^[1]。然而灾情空间分布情况及不同灾情程度的发生位置，是搜救人员实施任务的主导环节，因此导航定位技术在灾害状况分布图的制作和救援决策中具有不可替代的作用^[2]。基于传感器的室内定位原理与全球定位系统伪距定位原理相似，终端至少需要接收4个基站传输的信号才能完成定位^[3]。在矿井、失火大楼等灾害环境中，由于该方式定位涉及信号多重覆盖、区域信号的连续性、信号延迟等问题^[4]，基站位置的确定将直接影响区域内的定位效果。因为受上述因素的影响，基站坐标确定问题属于优化问题中的组合优化问题。当前主要组网方式有星型布设、方形布设和菱形布设^[5]，但其设计方案过于理想化，没有考虑定位区域的空间特征，在实际应用中难以满足实际需求，一般不是最佳布站方案。

曾有学者提出，将生物学中的遗传模型应用于雷达网的优化布设^[6]。遗传算法(genetic algorithm，GA)作为现代智能优化算法，最大特点是可以针对非线性优化问题快速挑出局部最优解^[7]。由于GA算法容易发生过早收敛现象，算法的最优解依赖于初始种群现象较严重，使得算法需经过长时间才能得到最优解^[8]。应急组网属于动态组网，目前还没有一套综合的组网理论。鉴于此，本文提出应急组网遵循的基本原则，并结合IAGA模型将其应用到基站组网优化部署中，该模型从种群的选取，到遗传过程操作中均有改良。试验证明，该算法能够较大提高组网效率，为实施决策提供一定的参考价值。

1 优化组网的数学模型 1.1 测距定位算法 1.1.1 时间差定位(TDOA)算法

假定灾区中一点的空间三维坐标为(X，Y，Z)，它到第一个固定基站(X₀，Y₀，Z₀)与移动站(X_i，Y_i，Z_i)的传播时间和距离差分别为t₀、t_i和ΔR_i(i=1，2，3)，则有如下关系方程组成立，以ΔR_i作为观测值得到观测方程

以灾区点的空间位置作为未知量，对式(1) 进行一阶泰勒级数展开，TDOA测量可以写为

写成矩阵形式有

式中

其中，ΔR_k⁰为观测值；ΔR′_k为推算的观测值近似值。

根据间接平差原理：其中，为传感器测距单位误差估值，r为观测值的自由度，Q为观测值构成的协因数阵，由文献[9]得

, 其中D_xx为位置参数的方差阵，₀为传感器单位测距误差。

1.1.2 精度评定

(1) 定义平面位置精度因子^[3]

(2) 高程精度因子^[3]

(3) 空间位置精度因子^[3]

1.2 组网部署原则

一个具体的现场组网部署任务，事故现场的自然条件(地物、地貌)已经确定。如多层式的办公楼可以将受灾区域分为重点定位区域、一般定位区域和较安全区域。火势较重、人口密集的危险楼层可设置为重点定位区域；受灾程度较轻、人口稀少的楼层可设置为一般定位区域；暂时安全、无人区的楼层可以设置为较安全区域。基站优化部署应该遵循连续性、区域重叠性、可靠性、探测区域最大化原则^[10]。优化部署基站原则量化如下^[11]：

(1) 连续性：终端处于目的基站接发射信号的有效半径内，才能保证数据的可靠性。假设每个基站的通信半径为R_i，终端位置点j至基站i的距离为d_ij，则有

(2) 区域重叠性：终端只有获得其与足够数目的基站之间的距离测量值，才能完成定位，实现应急组网的功能，即有

式中，表示目标点能够接发收到基站信号的个数；N₀表示定位解算必要观测个数。

(3) 可靠性：为了提高终端定位跟踪进度，要求区域中任一点DOP值小于相应阈值，即有

式中，DOP可以是HDOP (平面精度因子)、VDOP (高程精度因子)或PDOP(空间位置精度因子)，对应F_DOP分别为F_HDOP(平面精度因子阈值)、F_VDOP(高程精度因子阈值)或F_PDOP(空间位置精度因子阈值)。

(4) 探测区域最大化：基站组网对责任区的覆盖范围也尽可能大，整体覆盖层数尽可能多。

覆盖区网络由N部基站组成，改变基站放置位置，网络的性能将会发生较大程度的变化，寻求一组合适的基站坐标对网络进行优化，使得在该区域中加权DOP值达到最小，以最差DOP值点位个数最少为目标，使其达到定位设计要求。目标函数可表示为

式中，m为分区域的类型数目；n_i为对应的区中特征点个数；k_i为区域DOP加权值；num (DOPⁱ>F_DOP)表示区域i中特征点DOP值超越F_DOP的个数；w_i为区域中DOP越值的加权值，即目标函数越小，个体的适应度越大。

2 改进的自适应遗传算法组网优化部署 2.1 编码方式

一般来说，染色体编码方式有浮点编码、二进制编码、格雷码编码、符号编码法^[12]。鉴于浮点数编码可表示的数值较大、精度高且便于较大空间的遗传搜索，可以较好地应用于本问题，依次将基站的空间坐标设置为染色体，采用浮点编码方式^[13]，各基站的三维坐标分别由n_x、n_y和n_z位的十进制编码表示，多基站组成的染色体编码表示如图 1所示。

2.2 用Hamilton优化初始种群

初始种群规模应足够大，以增加取得最优解的概率，但规模过大易造成搜索范围过大，遗传过程时间变长。文献[14]提出一种基于星型布站方式实现三维定位的方法，其基站组网方式可以作为初始种群的预选值，并结合Hamilton算法获得一个较合适的初始种群。

2.3 基于Logistic的随机交叉操作

这里的交叉操作采取“门当户对”的形式，即适应度接近的父代个体相互配对。交叉点位置通过Logistic序列确定，对需要配对的父代进行交叉操作。在实际操作时，是通过产生一个服从(0, 1) 均匀分布的随机数，如果该值大于交叉概率P_c，则在相应个体的Logistic点位上进行交叉配对。

2.4 基于种群规模的变异操作

在进行交叉过程之后，从新个体中选择变异个体，变异个体和个体基因位置采取随机的方式进行。变异数量由群体中的群体个数N和变异概率P_m决定，并有

与交叉操作方式类似，在实际操作时，通过产生一个服从(0, 1) 均匀分布的随机数，若该值小于变异概率P_m，则在相应个体的Logistic点位上进行变异操作。

2.5 交叉概率和变异概率的自适应优化

对交叉概率和变异概率进行自适应修正，使得变异和交叉操作随着子代适应度自适应调整^[15]，其表达式如下

式中，p_c0和p_m0为常数，分别表示初始交叉概率和初始变异概率；α和β为区间[0,1]的常量；f_c为交叉个体适应度大的个体适应度；f_m表示变异个体的适应度；f_aver表示所有个体中的平均适应度；f_max表示所有个体中的最大适应度。

2.6 算法流程

灾害优化组网布设的改进自适应遗传算法的主要步骤流程如图 2所示。

3 模拟与仿真

假定布设区域为100 m×100 m×20 m的长方体空间，3类不同的等级定位区域。定位系统共由4个基站组成，其中1个固定基站、3个可移动基站。3类不同等级定位区域的高度不同，分别为2.5~7.5 m、7.5~12.5 m、12.5~17.5 m。基站最大感应半径为200 m，其中固定站坐标为(150，150，20)，3个移动站分布于空间外侧。

改进自适应遗传算法参数设置如下：染色体长度L=30，种群规模值取N=50，初始交叉概率值p_c0为0.95，初始变异系数值p_m0取为0.1，在适应度函数中，F_PDOP取为12，区域DOP加权值k={1, 2, 3}，区域DOP越值的加权值w={1, 2, 3}。通过改进自适应遗传算法对移动基站坐标进行优化计算，运算结果见表 1。

图 3为经过算法优化之后的组网效果图，其中“+”形状图样为固定基站，“*”形状图样为移动基站，深灰色区域为较安全区域(高度2.5~7.5 m)，黑色区域为一般定位区域(高度7.5~12.5 m)，浅灰色区域为重点定位区域(高度12.5~17.5 m)。

同时，将表 1迭代30次结果与蚁群算法迭代60次及传统遗传算法迭代30次得到的结果进行比较。蚁群算法的优化结果为：移动基站1位置(48.5，105.8，0.9)，移动基站2位置(197.2，234.9，2.0)，移动基站3位置(211.2，45.6，0.5)，目标函数值f_p为4.703。传统遗传算法的优化结果为：移动基站1位置(54.4，140.9，1.4)，移动基站2位置(159.2，239.9，2.3)，移动基站3位置(224，86.8，0.80)，目标函数值f_p为5.602。

分别选取区域中的高度为5、10和15 m的区域面作为3类不同等级区域特征面，经过改进的自适应遗传算法迭代30次运算得到基站坐标，组成的基站网在不同类型等级定位区域的PDOP值分布如图 4所示。使用蚁群算法和传统遗传算法得到的在不同类型等级定位区域的PDOP值分布，如图 5和图 6所示。

表 2为3种算法在3个特征面上的平均PODP值(aver)、最小PDOP值(min)和最大PDOP值(max)3个指标的比较。

由图 4—图 6和表 2可知，改进的自适应遗传算法相较于蚁群算法从效率上有较大程度的提升，性能也有所提高。相较于传统的遗传算法，由于初始种群的改良、交叉变异的改进，使得搜索速率加快，大大节省了寻求最优解的运算时间，提高了应急网络综合性能。

4 结语

本文提出了一种改进的自适应遗传算法，并将其应用于应急定位组网的基站优化部署。根据应急定位的特殊性，结合基站组网的特点，总结出优化组网的概念、遵循的原则及组网的评价指标。试验结果表明，该算法能够达到应急定位精度的要求，满足灾害环境下的定位要求，符合组网基本原则。为了加快算法收敛速度，提高组网强度，通过改良圈算法和Logistic混沌序列改良父代种群，以及遗传操作中的变异与交叉自适应调整，其效果优于蚁群算法和传统遗传算法。

然而，在组网部署的过程中，灾害环境等自然环境因素不同，对于信号传输的非视距问题、信号干扰等因素，本文未考虑，只对其进行了简化。对于地形复杂、条件烦琐的情况还需要进一步考虑遗传模型中的参数设置、适应度函数的确定等问题。