第2卷第1期 智能系统学报 Vol.2 Ng 1 2007年2月 CAAI Transactions on Intelligent Systems Fcb.2007 基于免疫算法的TDOA定位技术研究 高洪元，曹硕男缪善林 (哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001) 摘要：为了解决TDOA定位估计中遇到的非线性最优化问题，提出了一种联合使用Chan算法和免疫算法的混合 定位算法.针对TDOA方式进行最佳坐标搜索的问题，所设计的基于浮点数编码的免疫算法利用混沌方程产生初始 种群、改进了免疫算子，提高了算法的收敛速度和性能.仿真结果表明，在保证种群数量的情况下，该算法性能稳定， 能找到逼近全局最优点的解，相对于Chan算法精度更高，相对于遗传算法在保证收敛性能的前提下有更快的收敛 速度. 关键词：到达时间差，无线定位：免疫算法：Chan算法：最大似然估计 中图分类号：TN929.53文献标识码：A文章编号：16734785(2007)01-006405 Study of TDOA location technology based on immune algorithm GAO Hong yuan,CAO Shuo-nan,MIAO Shan-lin (College of Information and Communication Engineering,Harbin Engineering University,Harbin 150001,China) Abstract:In order to resolve the nonlinear optimization problem of TDOA Location,a hybrid method that employs a modified immune algorithm and a Chan algorithm is proposed.The modified immune algorithm is a consociation of genetic algorithm based on chaotic initial population and floating point code with modi- fied immune operator that reduces the computational complexity by providing faster convergence.Simula- tion results show that if the population size is big enough,the algorithm is robust and can find the coordi- nates of near optimization.It has a higher accuracy than Chan algorithm and a faster convergence than ge- netic al gorithm. Keywords:TDOA:wireless location;immune algorithm:chan algorithm:maximum likelihood estimation TDOA定位技术又称为双曲线相交法)，通过 余的情况，文献[46]给出了一些闭合解，然而这些 测量源信号到达多个接收机的时间差定出源信号到 解都不是最优的.文献[7]给出了采用傅里叶级数的 达多个接收机的距离差，用方程表示就是一组双曲 迭代算法，这种迭代需要一个较好的初始值，否则容 线方程.到达时间差方法不要求移动台与基站之间 易落入局部最小点，而且不能保证收敛.文献[8]提 严格同步，只要求基站间严格同步（这通常可以做 出了一种2步加权LS方法.在测量参数误差很小 到)，因此实用性较强.但多个TDOA测量值构成的 的情况下，性能逼近最优值，但是这种方法由于引入 双曲线方程组是非线性的，求解有一定困难，针对此 了测量参数的平方项，当测量误差较大时，噪声的二 问题已提出很多算法).但如果接收机在空间随机 次项不可忽视，其性能会恶化.文献[9]采用遗传算 分布则情况较为复杂，在求解双曲线方程组时会遇 法解极大似然函数，通过合理设置种群规模以及变 到非线性问题.文献[3]给出了测量参数个数与源信 异率，能找到逼近全局最优点的解，相对于其他算法 号坐标个数相同时的精确解.然而，当测量参数个数 精度更高，但由于计算量较大，实时实现很困难. 有冗余时，这种方式不能充分利用多余的测量参数 文中提出一种结合Chan算法和免疫算法的 给出统计信息来改进定位精度.针对测量参数有冗 TDOA定位算法.该算法首先根据移动台所处小区 的D号和Chan算法确定移动台坐标范围，然后采 收稿日期：200606-20. 用似然函数的倒数作为适应值，浮点数编码，用抗体 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved hutp://www.cnki.net
第 2 卷第 1 期 智 能 系 统 学 报 Vol. 2 №. 1 2007 年 2 月 CAA I Transactions on Intelligent Systems Feb. 2007 基于免疫算法的 TDOA 定位技术研究 高洪元 ,曹硕男 ,缪善林 (哈尔滨工程大学 信息与通信工程学院 ,黑龙江 哈尔滨 150001) 摘 要 :为了解决 TDOA 定位估计中遇到的非线性最优化问题 ,提出了一种联合使用 Chan 算法和免疫算法的混合 定位算法. 针对 TDOA 方式进行最佳坐标搜索的问题 ,所设计的基于浮点数编码的免疫算法利用混沌方程产生初始 种群、改进了免疫算子 ,提高了算法的收敛速度和性能. 仿真结果表明 ,在保证种群数量的情况下 ,该算法性能稳定 , 能找到逼近全局最优点的解 ,相对于 Chan 算法精度更高 ,相对于遗传算法在保证收敛性能的前提下有更快的收敛 速度. 关键词 :到达时间差 ;无线定位 ;免疫算法 ;Chan 算法 ;最大似然估计 中图分类号 : TN929153 文献标识码 :A 文章编号 :167324785 (2007) 0120064205 Study of TDOA location technology based on immune algorithm GAO Hong2yuan ,CAO Shuo2nan ,MIAO Shan2lin (College of Information and Communication Engineering , Harbin Engineering University , Harbin 150001 , China) Abstract : In order to resolve t he nonlinear optimization problem of TDOA Location , a hybrid met hod t hat employs a modified immune algorithm and a Chan algorit hm is proposed. The modified immune algorit hm is a consociation of genetic algorit hm based on chaotic initial pop ulation and floating point code wit h modi2 fied immune operator t hat reduces t he comp utational complexity by p roviding faster convergence. Simula2 tion results show t hat if the pop ulation size is big enough , t he algorit hm is robust and can find the coordi2 nates of near optimization. It has a higher accuracy t han Chan algorit hm and a faster convergence t han ge2 netic algorithm. Keywords :TDOA ; wireless location ; immune algorit hm ;chan algorit hm ; maximum likelihood estimation 收稿日期 :2006206220. TDOA 定位技术又称为双曲线相交法[1 ] ,通过 测量源信号到达多个接收机的时间差定出源信号到 达多个接收机的距离差 ,用方程表示就是一组双曲 线方程. 到达时间差方法不要求移动台与基站之间 严格同步 ,只要求基站间严格同步 (这通常可以做 到) ,因此实用性较强. 但多个 TDOA 测量值构成的 双曲线方程组是非线性的 ,求解有一定困难 ,针对此 问题已提出很多算法[2 ] . 但如果接收机在空间随机 分布则情况较为复杂 ,在求解双曲线方程组时会遇 到非线性问题. 文献[ 3 ]给出了测量参数个数与源信 号坐标个数相同时的精确解. 然而 ,当测量参数个数 有冗余时 ,这种方式不能充分利用多余的测量参数 给出统计信息来改进定位精度. 针对测量参数有冗 余的情况 ,文献[ 4 - 6 ]给出了一些闭合解 ,然而这些 解都不是最优的. 文献[ 7 ]给出了采用傅里叶级数的 迭代算法 ,这种迭代需要一个较好的初始值 ,否则容 易落入局部最小点 ,而且不能保证收敛. 文献[ 8 ]提 出了一种 2 步加权 L S 方法. 在测量参数误差很小 的情况下 ,性能逼近最优值 ,但是这种方法由于引入 了测量参数的平方项 ,当测量误差较大时 ,噪声的二 次项不可忽视 ,其性能会恶化. 文献[ 9 ]采用遗传算 法解极大似然函数 ,通过合理设置种群规模以及变 异率 ,能找到逼近全局最优点的解 ,相对于其他算法 精度更高 ,但由于计算量较大 ,实时实现很困难. 文中提出一种结合 Chan 算法和免疫算法的 TDOA 定位算法. 该算法首先根据移动台所处小区 的 ID 号和 Chan 算法确定移动台坐标范围 ,然后采 用似然函数的倒数作为适应值 ,浮点数编码 ,用抗体 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第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
·66· 智能系统学报 第2卷 上界；LB是抗体分量取值范围的下界：b是确定对 x1=x*(1-x) 13) 迭代数依赖程度的系统参数， y1=4y*(1-y (14) 为求解方程5)，该算法中，取适应度函数为 式中：k=1,2,…是迭代的次数，“是控制系统混沌 f(Z)= 行为的参数，0≤x,其混沌空间为0,1]，生成的 (△R-R+R)T(R-R+R)I 混沌序列具有随机遍历的特征，将生成的混沌序列 (7 从0,1混沌空间映射为系统状态空间，混沌序列能 抗体矢量为 够保证产生的抗体集合在系统状态空间中遍历均匀 z=[xi.y.. 8) 的分布 式中：x,y是待估计的坐标. 3)计算适应度，由当前最优抗体及其局部寻优 疫苗的制备：为了使个体抗体)以较大的概率 值制备疫苗放入疫苗库，疫苗库中制备疫苗的抗体 位于最优点附近，以当前代最优个体z为初始状 是抗体总数的0.05. 态，即zg=[xg,yg],由zg=xg,yg按式)和 4)根据适应度，使用轮盘赌选择策略进行选择」 (10)进行局部寻优生成疫苗母本. 5)采用交叉和变异等操作 x1=xg(1+店， (9) 6)疫苗接种和疫苗选择，接种后的抗体根据退 y=g1+ 10) 火机制进行取舍， 式中：？为扰动幅值参数，为服从高斯分布的随机 )判断算法迭代终止条件是否满足，如果满 变量，其方差随叠代次数增加而线性减少.由最优个 足，执行8)：否则，转向3). 体及其局部变异个体分割成不同的片断，制备疫苗 8)输出最优抗体，免疫算法运行结束」 免疫选择：这一操作分2步完成.第1步是免疫 检测，如果子代适应度优于父代，说明接种成功，如 3实验结果与比较 果子代适应度不如父代，则进行第2步处理，即对接 仿真背景和参数如下：考虑蜂窝网如图2所示， 种了疫苗的个体进行检测，若其适应度仍不如父代， 蜂窝半径为3km,有5个基站，其位置分别为(0 说明在交叉、变异的过程中出现了退化现象，这时该 0),33,3),33,-3,0,-6,（-33,-3): 个体将被父代中所对应的个体根据退火机制进行选 源点位置为(1,2.5)，0单位为km 择，使用退火机制可在一定程度上破坏局部收敛点， 使算法跳出局部收敛.选择初始温度心，设为被 接种的个体，1为接种后的个体，免疫选择操作后 的个体为z 计算f=f(z),f)=f(),△=f方-f1 z州= ,min(1,ey≥%， 11) 其他 式中：y∈0,1为均匀分布的随机变量 T41=AT,0<A<1. 12) 则求TDOA定位坐标的最优估计转化为在免疫算 法搜索全局最优个体.现把用于定位的免疫算法流 ▲：目标位置坐标(1.2.5) 程简述如下： I)根据Chan算法搜索到一个局部最优解(xh, 图2接收机与目标位置示意图 y,蜂窝网半径为r,确定免疫算法的搜索区间为 Fig 2 Sketch map of receiver position coordinary [x-C,x6+C]和[y%-C,y%+CI.在文中C= 表1中的Chan栏是Chan算法IsI的仿真结果： 千，若搜索区间超过蜂窝半径坐标区间10,1.需做 Cham IA栏是文中算法的仿真结果；GA栏是文献 [9]中改进遗传算法的仿真结果.为了便于比较，IA 钳位处理 和GA算法选定参数如下：种群数为70，杂交率 2)Chan算法搜索到一个局部最优解(x,ya作 P=0.7,变异率Pm=0.05,b=6,独立运算5000 为一个抗体，其他抗体由计算量较小、使用方便的 次；GA算法的终止迭代次数为60，ChanIA算法的 Logistic混沌方程(13)和(14)遍历产生 终止迭代次数为15，接种概率为0.1.表中第1栏 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net
上界; L B 是抗体分量取值范围的下界; b 是确定对 迭代数依赖程度的系统参数. 为求解方程(5) ,该算法中 ,取适应度函数为 f ( zi) = 1 (ΔR - R + R1 ) T (ΔR - R + R1 ) | z i . (7) 抗体矢量为 zi = [ xi , yi ] T . (8) 式中 : xi , yi 是待估计的坐标. 疫苗的制备 :为了使个体 (抗体) 以较大的概率 位于最优点附近 ,以当前代最优个体 zg 为初始状 态 ,即 zg = [ x g , y g ] T ,由 zg = [ x g , y g ] T 按式 (9) 和 (10) 进行局部寻优生成疫苗母本. x t+1 g = x t g (1 +ηξ) , (9) y t+1 g = y t g (1 +ηξ) . (10) 式中 :η为扰动幅值参数 ,ξ为服从高斯分布的随机 变量 ,其方差随叠代次数增加而线性减少. 由最优个 体及其局部变异个体分割成不同的片断 ,制备疫苗. 免疫选择 :这一操作分 2 步完成. 第 1 步是免疫 检测 , 如果子代适应度优于父代 ,说明接种成功 ,如 果子代适应度不如父代 ,则进行第 2 步处理 ,即对接 种了疫苗的个体进行检测 ,若其适应度仍不如父代 , 说明在交叉、变异的过程中出现了退化现象 ,这时该 个体将被父代中所对应的个体根据退火机制进行选 择 ,使用退火机制可在一定程度上破坏局部收敛点 , 使算法跳出局部收敛. 选择初始温度 T0 ,设z t j 为被 接种的个体 , z t + 1 j 为接种后的个体 ,免疫选择操作后 的个体为 z t + 1 j . 计算 f′j = f ( z t + 1 j ) , f j = f ( z t j) ,Δ= f j - f′j . z t+1 j = z t+1 j , min{ 1 ,e -Δ/ T t} ≥γj , z t j , 其他. (11) 式中 :γj ∈[0 ,1 ]为均匀分布的随机变量. Tt+1 =λT t ,0 <λ < 1. (12) 则求 TDOA 定位坐标的最优估计转化为在免疫算 法搜索全局最优个体. 现把用于定位的免疫算法流 程简述如下 : 1) 根据 Chan 算法搜索到一个局部最优解 ( x b , y b) ,蜂窝网半径为 r,确定免疫算法的搜索区间为 [ x b - C, x b + C] 和[ yb - C, y b + C]. 在文中 C = r 4 ,若搜索区间超过蜂窝半径坐标区间[0 , r] ,需做 钳位处理. 2) Chan 算法搜索到一个局部最优解( x b , yb ) 作 为一个抗体 ,其他抗体由计算量较小、使用方便的 Logistic 混沌方程(13) 和(14) 遍历产生. x k+1 = μx k (1 - x k ) , (13) y k+1 = μy k (1 - y k ) . (14) 式中 : k = 1 ,2 , …是迭代的次数 ,μ是控制系统混沌 行为的参数 ,0 ≤x k ≤1 ,其混沌空间为[0 ,1 ] ,生成的 混沌序列具有随机遍历的特征 ,将生成的混沌序列 从[0 ,1 ]混沌空间映射为系统状态空间 ,混沌序列能 够保证产生的抗体集合在系统状态空间中遍历均匀 的分布. 3) 计算适应度 ,由当前最优抗体及其局部寻优 值制备疫苗放入疫苗库 , 疫苗库中制备疫苗的抗体 是抗体总数的 0105. 4) 根据适应度 ,使用轮盘赌选择策略进行选择. 5) 采用交叉和变异等操作. 6) 疫苗接种和疫苗选择 ,接种后的抗体根据退 火机制进行取舍. 7) 判断算法迭代终止条件是否满足 , 如果满 足 ,执行 8) ;否则 ,转向 3) . 8) 输出最优抗体 ,免疫算法运行结束. 3 实验结果与比较 仿真背景和参数如下 :考虑蜂窝网如图 2 所示 , 蜂窝半径为 3 km ,有 5 个基站 ,其位置分别为 ( 0 , 0) , (3 3 ,3) , (3 3 , - 3) , (0 , - 6) , ( - 3 3 , - 3) ; 源点位置为(1 ,215) , cσ单位为 km. 图 2 接收机与目标位置示意图 Fig12 Sketch map of receiver position coordinary 表 1 中的 Chan 栏是 Chan 算法[8 ]的仿真结果 ; Chan2IA 栏是文中算法的仿真结果 ; GA 栏是文献 [9 ]中改进遗传算法的仿真结果. 为了便于比较 ,IA 和 GA 算法选定参数如下 :种群数为 70 ,杂交率 Pc = 017 ,变异率 Pm = 0105 , b = 6 , 独立运算5 000 次; GA 算法的终止迭代次数为 60 ,Chan2IA 算法的 终止迭代次数为 15 ,接种概率为 011. 表中第 1 栏 ·66 · 智 能 系 统 学 报 第 2 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
第1期 高洪元，等：基于免疫算法的TDOA定位技术研究 *67 101g(c)是根据蜂窝网通信系统与系统热噪声等因 沌方程产生遍历初值，以及使用了疫苗接种机制」 素确定的).评价指标为平均估计坐标MV,即 0.08 E[(x,以1：均方误差 0.07 MSE=E[(x-o2+(y-o)21.仿真所得MW 一Chan算法 ·GA算法 如表1所示，MSE如图3所示 昱0.06 +Chan-lA算法 0.05 表1Chan算法、GA算法及文中算法 0.04 Table 1 Performance comparison of Chan,GA and Chan-IA 0.03 101g(o) 44444++44年 Chan算法 GA算法 文中算法 0.02 dB 0 510152025303540 迭代次数/次 -18(1.000524997)(1.011424845(1.000524997) 图4 GA and CharIA的收敛性能曲线 ·16(0998724998)(1.007124902)(0998725014) Fig 4 Convergence performance curves of GA and Charr IA. -14(1.000424963)(1.010824863)(1.000225005) 400 -12(1.004224887(1.014924781)(1.004524923) 350 300 -10(1.003424869)(1.015324843)(1.002425010) ·GA算法 250 +Chan-lA算法 -8(1.006924471)(1.013524704)(1.005524794) 200 150 100 0.08 50 0.07 0.06 →Chan算法 0510152025303540 迭代次数/次 0.05 +GA算法 *Chan-IA算法 0.04 图5 GA and CharIA的收敛性能曲线 0.03 Fig 5 Convergence performance curves of GA and Charr IA 0.02 图5给出了适应度函数和迭代次数的关系，从 0.01 图中的曲线可以看出，GA算法不仅有收敛速度慢 当18 -16 -14-12-10 的缺点，且容易陷入局部极值，但Chan-IA算法能 10 Ig(ca)/dB 克服这个缺点，快速获得近似全局最优解。 图3Chan、GA,Charr IA的性能比较曲线 4 结束语 Fig 3 MSE performance curves of Chan,GA and Charr IA. 提出的Chan-IA算法在仿真中表现稳定，定位 从图3可以看出，在噪声方差很小时，GA容易 精度高，尤其是在噪声较大的情况下，与Chan算法 陷入局部收敛，而当噪声方差加大时，GA、ChamIA 相比有更高的稳定性，与改进的遗传算法(GA)相比 的性能要比Chan算法好，这是因为Chan算法对噪 有更快的搜索速度和更高的精度，对高精度定位技 声二次项的忽略导致的sI.CharIA的性能一直是 术的实用化研究有借鉴价值.进一步的工作可继续 最好的，计算量还不到GA的1/3，因此是快速收敛 探讨在非视距误差存在的条件下，智能计算在定位 算法 技术中的应用，进一步提高算法的精度和收敛速度 从图4可以看出，在噪声方差较大时，ChamIA 也是进一步努力的目标. 算法与Chan算法、GA算法性能相近，但ChamIA 算法的性能要好于GA算法和Chan算法，是高精 参考文献： 度收敛的算法.从图中还可以看出，ChanIA算法收 [1]FOY W H.Position location solutions by Taylor series 敛速度极快，在5次迭代就可以超过GA算法在40 estimation[J ]IEEE Trans on Aerospace and Electronic 次迭代的效果，且克服了遗传算法局部收敛的缺点， Systems,1976,12(2):187-194. 这是因为ChanIA算法使用了较小的搜索区间，混 [2]AB EL J S,SMITHJ O.Source range and depth estima- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.nei
10lg ( cσ) 是根据蜂窝网通信系统与系统热噪声等因 素确定的[9 ] . 评价指标为平均估计坐标 MV , 即 E[ ( x , y) ];均方误差 MSE = E[ ( x - x0 ) 2 + ( y - y0 ) 2 ]. 仿真所得 MV 如表 1 所示 ,MSE 如图 3 所示. 表 1 Chan 算法、GA算法及文中算法 Table 1 Performance comparison of Chan , GA and Chan2IA 10lg ( cσ) / dB Chan 算法 GA 算法 文中算法 - 18 (11000 5 ,21499 7) (11011 4 ,21484 5) (11000 5 ,21499 7) - 16 (01998 7 ,21499 8) (11007 1 ,21490 2) (01998 7 ,21501 4) - 14 (11000 4 ,21496 3) (11010 8 ,21486 3) (11000 2 ,21500 5) - 12 (11004 2 ,21488 7) (11014 9 ,21478 1) (11004 5 ,21492 3) - 10 (11003 4 ,21486 9) (11015 3 ,21484 3) (11002 4 ,21501 0) - 8 (11006 9 ,21447 1) (11013 5 ,21470 4) (11005 5 ,21479 4) 图 3 Chan、GA、Chan2IA 的性能比较曲线 Fig13 MSE performance curves of Chan ,GA and Chan2IA. 从图 3 可以看出 ,在噪声方差很小时 , GA 容易 陷入局部收敛 ,而当噪声方差加大时 , GA 、Chan2IA 的性能要比 Chan 算法好 ,这是因为 Chan 算法对噪 声二次项的忽略导致的[8 ] . Chan2IA 的性能一直是 最好的 ,计算量还不到 GA 的 1/ 3 ,因此是快速收敛 算法. 从图 4 可以看出 ,在噪声方差较大时 ,Chan2IA 算法与 Chan 算法、GA 算法性能相近 ,但 Chan2IA 算法的性能要好于 GA 算法和 Chan 算法 ,是高精 度收敛的算法. 从图中还可以看出 ,Chan2IA 算法收 敛速度极快 ,在 5 次迭代就可以超过 GA 算法在 40 次迭代的效果 ,且克服了遗传算法局部收敛的缺点 , 这是因为 Chan2IA 算法使用了较小的搜索区间 ,混 沌方程产生遍历初值 ,以及使用了疫苗接种机制. 图 4 GA and Chan2IA 的收敛性能曲线 Fig14 Convergence performance curves of GA and Chan2IA. 图 5 GA and Chan2IA 的收敛性能曲线 Fig15 Convergence performance curves of GA and Chan2IA 图 5 给出了适应度函数和迭代次数的关系 ,从 图中的曲线可以看出 , GA 算法不仅有收敛速度慢 的缺点 ,且容易陷入局部极值 ,但 Chan2IA 算法能 克服这个缺点 ,快速获得近似全局最优解. 4 结束语 提出的 Chan2IA 算法在仿真中表现稳定 ,定位 精度高 ,尤其是在噪声较大的情况下 ,与 Chan 算法 相比有更高的稳定性 ,与改进的遗传算法( GA) 相比 有更快的搜索速度和更高的精度 ,对高精度定位技 术的实用化研究有借鉴价值. 进一步的工作可继续 探讨在非视距误差存在的条件下 ,智能计算在定位 技术中的应用 ,进一步提高算法的精度和收敛速度 也是进一步努力的目标. 参考文献 : [1 ] FO Y W H. Position location solutions by Taylor series estimation[J ]. IEEE Trans on Aerospace and Electronic Systems , 1976 ,12 (2) : 187 - 194. [2 ]ABEL J S , SMITH J O. Source range and depth estima2 第 1 期 高洪元 ,等 :基于免疫算法的 TDOA 定位技术研究 ·67 · © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
·68- 智能系统学报 第2卷 tion from multi-path range difference measurements[J ] LI Lichun,RAN Chongsen,WEI Feng.An enhanced IEEE Trans Acoust Speech Signal Processing,1989,37 genetic algorithm for the nonlinear optimization in (8):1157.1165. TDOA-based location [J ]Systems Engineering and E- [3]FANG B T.Simple solutions for hypebolic and related lectronics,2003,25(8):971-973. position fixes [J].IEEE Trans Aerosp Eletron Syst, [10]王磊，潘进，焦李成.免疫算法[)1.电子学报 1990,26(5):748.753. 2000,28(7):74-78. [4]SCHAU H C,ROBINSON A Z.Passive source localiza- WANG Lei,PAN Jin,JIAO Licheng.Immune algo- tion employing intersecting spherical surfaces from time- rithm [J ]Chinese Journal of Electronica,2000,28(7): of-arrival differences[J ]IEEE Trans Acoust Speech Sig- 74.78 nal Processing,1987,35(8):1223.1225. [5]SMITH J O,ABEL J S.Closed-form least-squares 作者简介： source location estimation from range-difference measure- ments[J ]IEEE Trans Acoust Speech Signal Processing, 高洪元，男，1977年生，讲师.主要 1987,35(12):1223.1225. 研究方向为智能计算和通信信号处理， [6]ABEL J S,SMITH J O.The spherical interpolation Email :gaohongyuan @hrbeu.edu.cn. method for closed form passive source location using range difference measurements[A].In Proc ICASSP- 87 [C].Dallas,TX,1987. [7]ABEL J S.A divide and conquer approach to least- squares estimation[J].IEEE Trans Aerosp Eletron Syst, 缪善林，男，1981年生，硕士研究 1990,26(2):423-427 生.主要研究方向为宽带信号检测、处 [8]CHAN Y T,HO K C.A simple and efficient estimator 理与识别及空间谱估计. for hyperbolic location [J ]IEEE Trans on Singal Pro- cessing,1994,42(8):1905.1915. [9]李立春，冉崇森，魏峰.利用改进遗传算法解决TDOA 定位估计中的非线性优化问题[卩].系统工程与电子技 术，2003,25(8)：971-973 第2届智能计算及其应用国际会议 The 2nd International Symposium on Intelligence Computation and applications The 2nd International Symposium on Intelligence Computation and Applications(ISICA 2007)will be held on September 21-23,2007 in Wuhan,China.Following the successful ISICA 2005 sponsored by the China University of Geosciences (CUG)and the China Association Aerospace,ISICA 2007 will focus on the applications of intelligent computation in earth and space sciences for analyzing and processing massive or real-time data that are beyond the scope of traditional computation. Cross-fertilization of intelligent computation,evolvable hardware and newly emerging technologies is strongly encouraged.It will feature worldrenowned plenary speakers,state-of-the-art special sessions,regular technical sessions,poster interactions, and entertaining social activities. Important Due Dates: Paper Submission:March 31,2007 Decision Notification:May 15,2007 Camerar Read Submission:June 15,2007 (Due to a clash with the IEEE SSCI 2007,ISICA 2007 scheduled on April 6-8,2007 will be postponed till September 21 -23,2007.The new date is just before CEC 2007 that will take place on September 25-28,2007 in Singapore.Considering the short distance between Singapore and Wuhan,it is quite convenient for some people to go to both events in just one trip. ISICA'07 covers all topics in intelligent computation,including,but not limited to Evolutionary computation (genetic algorithm,evolutionary strategy,evolutionary programming genetic programming); Neural networks Fuzzy systems Ant colony,artificial immune artificial life systems Bioinformatics Biological computing &DNA computing Cognitive science Data mining&knowledge discovery Feature extraction Intelligent Control Intelligent GIS Learning memory More details please see the the following web site:http://ec.cug.edu.cn 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
tion from multi2path range difference measurements[J ]. IEEE Trans Acoust Speech Signal Processing , 1989 , 37 (8) :1157 - 1165. [3 ] FAN G B T. Simple solutions for hypebolic and related position fixes [J ]. IEEE Trans Aerosp Eletron Syst , 1990 ,26 (5) :748 - 753. [4 ]SCHAU H C , ROBINSON A Z. Passive source localiza2 tion employing intersecting spherical surfaces from time2 of2arrival differences[J ]. IEEE Trans Acoust Speech Sig2 nal Processing ,1987 ,35 (8) :1223 - 1225. [ 5 ] SMITH J O , ABEL J S. Closed2form least2squares source location estimation from range2difference measure2 ments[J ]. IEEE Trans Acoust Speech Signal Processing , 1987 ,35 (12) :1223 - 1225. [6 ] ABEL J S , SMITH J O. The spherical interpolation method for closed form passive source location using range difference measurements[ A ]. In Proc ICASSP - 87 [C] . Dallas , TX ,1987. [7 ] ABEL J S. A divide and conquer approach to least2 squares estimation[J ]. IEEE Trans Aerosp Eletron Syst , 1990 ,26 (2) :423 - 427. [8 ]CHAN Y T , HO K C. A simple and efficient estimator for hyperbolic location [J ]. IEEE Trans on Singal Pro2 cessing , 1994 ,42 (8) :1905 - 1915. [9 ]李立春 ,冉崇森 ,魏 峰. 利用改进遗传算法解决 TDOA 定位估计中的非线性优化问题[J ]. 系统工程与电子技 术 ,2003 ,25 (8) :971 - 973. L I Lichun , RAN Chongsen , WEI Feng. An enhanced genetic algorithm for the nonlinear optimization in TDOA2based location [J ]. Systems Engineering and E2 lectronics , 2003 ,25 (8) :971 - 973. [10 ]王 磊 ,潘 进 ,焦李成. 免疫算法 [J ]. 电子学报 , 2000 , 28 (7) :74 - 78. WAN G Lei , PAN Jin , J IAO Licheng. Immune algo2 rithm[J ]. Chinese Journal of Electronica , 2000 , 28 (7) : 74 - 78. 作者简介 : 高洪元 ,男 ,1977 年生 ,讲师. 主要 研究方向为智能计算和通信信号处理. E2mail :gaohongyuan @hrbeu. edu. cn. 缪善林 ,男 , 1981 年生 ,硕士研究 生. 主要研究方向为宽带信号检测、处 理与识别及空间谱估计. 第 2 届智能计算及其应用国际会议 The 2nd International Symposium on Intelligence Computation and Applications The 2nd International Symposium on Intelligence Computation and Applications (ISICA 2007) will be held on September 21 - 23 , 2007 in Wuhan , China . Following the successful ISICA 2005 sponsored by the China University of Geosciences (CU G) and the China Association Aerospace , ISICA 2007 will focus on the applications of intelligent computation in earth and space sciences for analyzing and processing massive or real - time data that are beyond the scope of traditional computation. Cross - fertilization of intelligent computation , evolvable hardware and newly emerging technologies is strongly encouraged. It will feature world2renowned plenary speakers , state2of2the2art special sessions , regular technical sessions , poster interactions , and entertaining social activities. Important Due Dates: Paper Submission : March 31 , 2007 Decision Notification : May 15 , 2007 Camera2Read Submission : J une 15 , 2007 (Due to a clash with the IEEE SSCI 2007 , ISICA 2007 scheduled on April 6 - 8 , 2007 will be postponed till September 21 - 23 , 2007. The new date is just before CEC 2007 that will take place on September 25 - 28 , 2007 in Singapore. Considering the short distance between Singapore and Wuhan , it is quite convenient for some people to go to both events in just one trip. ) ISICA′07 covers all topics in intelligent computation , including , but not limited to : Evolutionary computation (genetic algorithm , evolutionary strategy , evolutionary programming & genetic programming) ; Neural networks ; Fuzzy systems ;Ant colony , artificial immune & artificial life systems ;Bioinformatics ;Biological computing & DNA computing ;Cognitive science ;Data mining & knowledge discovery Feature extraction ;Intelligent Control ;Intelligent GIS ;Learning & memory More details please see the the following web site :http :/ / ec. cug. edu. cn ·68 · 智 能 系 统 学 报 第 2 卷 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net