第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