第1期 高洪元，等：基于免疫算法的TDOA定位技术研究 *65· 矢量中的各分量代表待定坐标，在确定的坐标范围 R=[R1,R,R.y为， 内进行搜索.实验表明，算法性能稳定，通过合理设 n=[m.1,B,1,.1]y为. 置种群规模以及变异率，能找到逼近全局最优点的 可得 解，相对于其他算法精度更高.由于文献[8]和文献 △R=R-R+cm= [9]提出的方法性能较前述其他方法要好，文章最后 6.2+.y2.N出-2+(-y 给出了提出的算法与文献[8]和文献[9]的比较结 f指·2+指.y2.指-2+m.y 果 +m. 1TDOA双曲线数学模型 Xw -2+(Yx-y2. 为了叙述方便，考虑二维平面定位情况.所提方 (3) 法可以很容易地推广到三维情况.如图1所示，假设 文中考虑M>3时的情况，采用最大似然法估计源 M个接收机随机分布在二维平面上，(x,以为移动 点坐标(x,y以.因为R.1服从均值为(R,-R),方差 台(mobile station,MS的待估计位置，(X:,Y)为 为的高斯分布，因各测量值独立，则似然函数为 1 第i个基站(base station,BS的己知位置1.MS到 一ep △R-R+R 基站i的距离为R,令，表示MS与基站i(i判) 11 20 和基站1（服务基站）的实际距离差，测量值记作 △RR+RI△RR+R exp R1,则 2T 2 R1=cd.=R.1+cm.1= (4) R-R+cn.1,i=2,,M. (1) 求使似然函数最大的坐标值，相当于求 式中：c为电波传播速度；d.1是TDOA测量值；m.i (x.y)argf min/(AR-R+R)(AR-R+R) 是测量TDOA时引入的噪声，为方便起见，可认为 (5) 是独立同分布的方差为的高斯白噪声， 由于该方程是非线性函数，用解析法求解是比 较困难的.针对此情况，文中采用免疫算法在整个潜 (x,y) 在坐标解空间内进行搜索， R 2基于Chan IA的TDOA定位技术 X.) 免疫算法是一种采用进化策略在解空间中寻找 最优解的优化算法，将免疫概念及其理论应用于遗 传算法，在保留原算法优良特性的前提下，力图有选 择、有目的地利用待求问题中的一些特征信息或知 识来抑制其优化过程中出现的退化现象，由于文 中使用了先验知识获得了良好的初值及使用了接种 ▲：源点位置 ●：接收机位置 疫苗的方法来提高算法的收敛速度，为了克服早熟 收敛，制备疫苗时使用了局部极值搜索，然后采用退 图1二维平面示意图 火机制进行免疫选择.从而达到最佳搜索速度和精 Fig 1 Sketch map of 2-dimension plane. 度，同时还不破坏高适应度的个体 又因为 非均匀变异算子定义为则 R=NX,-x)2+(Y,-以2， Z+(UB-Z)1- 随机数为0， 所以有 R.1=NX:-x)2+(Y,-以2 +Nxxu LB)1-- T ,随机数为1. NfX-x)2+(Y-以2+cm.1,i=2,,M. (6) 2) 式中：z是抗体向量：t是迭代数；￡是第t次迭代时 记 的抗体向量；T是最大迭代数，NMxw是对角矩阵，其 △R=[R.1,R1,R.1].y为， 对角线元素是在0,11间符合均匀分布的随机数，M R=[R2,R3,RMJiM.v为， 是抗体向量的维数：UB是抗体体分量取值范围的 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved http://www.cnki.net矢量中的各分量代表待定坐标 ,在确定的坐标范围 内进行搜索. 实验表明 ,算法性能稳定 ,通过合理设 置种群规模以及变异率 ,能找到逼近全局最优点的 解 ,相对于其他算法精度更高. 由于文献[ 8 ]和文献 [9 ]提出的方法性能较前述其他方法要好 ,文章最后 给出了提出的算法与文献[ 8 ]和文献[ 9 ]的比较结 果. 1 TDOA 双曲线数学模型 为了叙述方便 ,考虑二维平面定位情况. 所提方 法可以很容易地推广到三维情况. 如图 1 所示 ,假设 M 个接收机随机分布在二维平面上 , ( x , y) 为移动 台( mobile station , MS) 的待估计位置 , ( Xi , Yi) 为 第 i 个基站( base station ,BS) 的已知位置[9 ] . MS 到 基站 i 的距离为 R i ,令 R 0 i ,1表示 MS 与基站 i( i ≠1) 和基站 1 (服务基站) 的实际距离差 , 测量值记作 Ri ,1 ,则 Ri ,1 = cd i ,1 = R 0 i ,1 + cni ,1 = Ri - R1 + cni ,1 , i = 2 , …, M. (1) 式中 :c 为电波传播速度; di ,1 是 TDOA 测量值; ni ,1 是测量 TDOA 时引入的噪声 ,为方便起见 ,可认为 是独立同分布的方差为σ2 的高斯白噪声. 图 1 二维平面示意图 Fig11 Sketch map of 22dimension plane. 又因为 Ri = ( Xi - x) 2 + ( Yi - y) 2 , 所以有 Ri ,1 = ( Xi - x) 2 + ( Yi - y) 2 - ( X1 - x) 2 + ( Y1 - y) 2 + cni ,1 , i = 2 , …, M. (2) 记 ΔR = [ R2 ,1 , R3 ,1 , …, RM ,1 ] T ( M- 1) ×1 , R = [ R2 , R3 , …, RM ] T ( M- 1) ×1 , R1 = [ R1 , R1 , …, R1 ] T ( M- 1) ×1 , n = [ n2 ,1 , n3 ,1 , …, nM ,1 ] T ( M- 1) ×1 . 可得 ΔR = R - R1 + cn = ( X2 - x) 2 + (Y2 - y) 2 - ( X1 - x) 2 + (Y1 - y) 2 ( X3 - x) 2 + (Y3 - y) 2 - ( X1 - x) 2 + (Y1 - y) 2 … ( XM - x) 2 + (YM - y) 2 - ( X1 - x) 2 + (Y1 - y) 2 + cn. (3) 文中考虑 M > 3 时的情况 ,采用最大似然法估计源 点坐标( x , y) . 因为 Ri ,1服从均值为 ( Ri - R1 ) ,方差 为σ2 的高斯分布 ,因各测量值独立 ,则似然函数为 ∏ M- 1 i =1 1 2πσ exp (ΔRi - Ri + R1 ) 2 2σ2 = 1 2πσ M- 1 exp (ΔR - R + R1 ) T (ΔR - R + R1 ) 2σ2 . (4) 求使似然函数最大的坐标值 ,相当于求 ( x , y) = arg{ min[ (ΔR - R + R1 ) T (ΔR - R + R1 ) ]} . (5) 由于该方程是非线性函数 ,用解析法求解是比 较困难的. 针对此情况 ,文中采用免疫算法在整个潜 在坐标解空间内进行搜索. 2 基于 Chan2IA 的 TDOA 定位技术 免疫算法是一种采用进化策略在解空间中寻找 最优解的优化算法 ,将免疫概念及其理论应用于遗 传算法 ,在保留原算法优良特性的前提下 ,力图有选 择、有目的地利用待求问题中的一些特征信息或知 识来抑制其优化过程中出现的退化现象[10 ] . 由于文 中使用了先验知识获得了良好的初值及使用了接种 疫苗的方法来提高算法的收敛速度 ,为了克服早熟 收敛 ,制备疫苗时使用了局部极值搜索 ,然后采用退 火机制进行免疫选择. 从而达到最佳搜索速度和精 度 ,同时还不破坏高适应度的个体. 非均匀变异算子定义为[9 ] z t+1 = z t + NM×M (UB - z t ) 1 - t T b ,随机数为 0 , z t + NM×M ( z t - LB ) 1 - t T b ,随机数为 1. (6) 式中 : z 是抗体向量; t 是迭代数; z t 是第 t 次迭代时 的抗体向量; T 是最大迭代数; NM ×M是对角矩阵 ,其 对角线元素是在[0 ,1 ]间符合均匀分布的随机数 , M 是抗体向量的维数; UB 是抗体体分量取值范围的 第 1 期 高洪元 ,等 :基于免疫算法的 TDOA 定位技术研究 ·65 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net