基于改进人工免疫算法的TDOA定位估计

宋越明， 于宏毅

（解放军信息工程大学，河南 郑州 450002）

0 引言

TDOA 定位技术又称为双曲线相交法，通过测量信号源到达多个接收机的距离差，进而求解双曲线方程组就可以得到信号源的估计位置。但求解非线性的双曲线方程组是很困难的。针对此问题已提出很多算法。文献[1]中介绍了Fang、SX、SI、Taylor级数展开法、Chan算法等比较常用的求解算法。但是它们都各自存在一些缺点，比如无法利用冗余测量数据提高测量精度，无法求得最优解，对初始解要求较高，或者最优解在测量噪声较大的情况下性能恶化比较严重。

上述定位算法的一般都假设到达时间差的测量误差服从高斯分布，且似然函数的解析表达式也是可以得到的，因此可以基于最大似然法求解上述TDOA定位问题。但是由于此时似然函数比较复杂，要对其求解必须解决复杂的非线性函数优化问题。

人工免疫算法是一种受免疫学启发，模拟免疫学功能、原理和模型来解决复杂问题的自适应系统，应用于非线性函数优化问题时具有适用性强，具有学习记忆功能，收敛性能较好等特点。本文分析了TDOA定位问题中的非线性函数优化问题，并有针对性的对人工免疫算法进行了改进，将人工免疫算法应用于TDOA定位估计问题。仿真表明改进的人工免疫算法应用于TDOA定位估计问题，性能稳定，可以保证全局收敛，且收敛速度较快，定位精度优于Chan算法。

1 TDOA双曲线定位模型

为了叙述简便，本文仅考虑二维平面情况，但文中的算法很容易推广到三维情况。以如下页图1所示定位系统为例，共有M（本文只讨论M＞3，即测量值有冗余的情况）个观测站分布在平面上，观测站i坐标为(xi, yi)，信号源坐标为(x,y)。设观测站i到信号源的距离为ri，信号源到观测站i和观测站1之间的距离差为r i1。根据基站和移动台之间的关系可以得到：

其中di1(i= 2,3…M- 1)，为到达时间差测量值，c为无线电传播速度。可认为ni1(i= 2,3…M- 1)是独立同分布，且均值为零，方差为σ的高斯随机变量。所以有：

记：

其中R1为M-1维列向量。综合式（1）、（2）得：

因为ΔR中的元素Δri均为独立同分布，且均值为ri-r1方差为c2σ2的高斯随机变量。因此似然函数为：

因此移动台位置坐标的最大似然估计为：

由于式（4）中包含很复杂的非线性函数，使用传统的求导方法求最大似然解非常困难。如果以式（5）为目标函数，搜索峰值对应坐标也可以求得最大似然估计值，但如果直接搜索会带来巨大的计算量。人工免疫算法作为一种全局优化算法，对寻优函数基本没有限制，也不要求参数的连续行和可导性，很适合用于上述非线性函数优化问题的求解。

图1 定位系统和信号源拓扑示意

2 基于改进人工免疫算法的TDOA定位

人工免疫算法借鉴了生物免疫系统的免疫原理，避免了遗传算法中的交叉操作引起的模式干扰，同时保证了抗体的多样性。文献[2]最早实际应用人工免疫算法，在后来的研究中人工免疫算法逐步发展，被广泛应用于数据挖掘、计算机安全、模式识别、优化、自动控制等领域，出现了几种不同类型的人工免疫算法[3],在国内也开始有相关研究将人工免疫算法应用于解决实际问题[4-5]。本文针对 TDOA估计中的非线性函数优化问题提出了一种改进的人工免疫算法，其主要流程如图2所示。

图2 改进的人工免疫算法流程

步骤1 初始化。随机产生Np个抗体组成的初始抗体种群Ap，每个抗体代表信号源位置的一个解(xj,yj),坐标值在信号源可能存在区域内随机取值。传统的人工免疫算法和遗传算法一样采取二进制编码，只需对0或1以一定概率取反就可以完成变异操作。但由于计算亲和度时必须使用未编码的数值，这就造成算法迭代中需要不断的进行编码和解码的过程，加大了算法的计算量，同时有限的编码长度也限制了最优解的精度。这里采取浮点数编码，直接采用浮点数表示抗体矢量的每个分量，避免了编解码过程。与之对应的抗体变异过程中也需要做出相应的改变。

步骤2 计算每个抗体的亲和度。这里亲和度根据式（5）的倒数计算，即：步骤3 选择。对所有抗体根据其亲和度从大到小排列，找出亲和度最大的Na个抗体组成集合Aa。

步骤4 根据收敛条件判断算法是否已经收敛，如果已经收敛，亲和度最大的抗体对应的坐标就是所求位置坐标；如果未收敛则继续。

步骤 5 克隆。克隆过程以一定的概率复制集合Aa中的抗体。为了在保持抗体数量不变的情况下尽量保留亲和度较高的抗体，这里采用轮盘赌策略对抗体进行克隆。首先计算克隆概率：

其中fi为抗体i的亲和度，wi为克隆概率。然后根据下式计算累积分布：

随机产生Na个在[0,1]之间均匀分布的数，若该数位于区间[ci-1,ci]，则复制抗体ai作为克隆抗体集合Ac中的抗体。通过以上的克隆策略，亲和度较大的抗体被克隆的概率较大，可以尽量保留亲和度高的抗体，防止退化现象，保证算法的收敛性。

步骤6 超变异（Hyper-mutation）。超变异过程保证了抗体的多样性，保证算法向最优解收敛。由于采用了浮点数编码，这里采用高斯变异，变异抗体由克隆抗体得到。假设第i个克隆抗体中的横坐标为，对应变异抗体中的横坐标为，则变异根据下式进行：

其中β和r为可控参数，与搜索区域大小和变异的程度有关，可以影响算法收敛的速度，n为均值为零，方差为1的高斯变量。为克隆抗体的变异率，针对求最大值问题，其计算公式如下：

其中fmax为当前最优解对应抗体的亲和度。同理可得到变异抗体中的纵坐标。变异后的抗体组成变异抗体集合Am。上述变异过程中亲和度高的抗体其变异率较低，可以避免变异抗体出现退化现象。

步骤7 调整免疫网络。重新计算变异抗体集合中所有抗体的亲和度，和Aa集合中的抗体一起重新进行选择，找出最优的Na个抗体进入下一代抗体集合。同时，淘汰当前亲和度最低的d个抗体，为了保持抗体数量和多样性，重新初始化含d个新抗体的集合 ，并将它加入下一代抗体集合。在这个过程中优势抗体被保留，退化的抗体被淘汰。

步骤8 返回步骤2继续迭代直到算法收敛。

上述改进的人工免疫算法具有记忆学习功能，抗体的进化和变异过程可以保证优势抗体得到保留，避免退化现象，且每次迭代中最优抗体都能进入下一次迭代，可以确保算法的全局收敛[6]。

3 仿真结果及分析

为了验证上述改进算法的性能，根据如下的仿真环境进行了计算机仿真。考虑蜂窝网系统的基站分布，其位置坐标分别为(0,0)，(-5000,3000)，(-5000,-3000), (0,-6000)，信号源位置为(1000，2500)，cσ取值根据实际应用环境设定为30～150 m（例如在GSM系统中，到达时间差测量可以达到的精度约135 m[7]，在第三代cdma网络中到达时间差的测量精度约78 m）。为了加快收敛速度，将Chan算法的估计结果作为初始解，初始抗体在初始解附近随机取值。仿真中Np= 30,Na= 24,d= 6。搜索参数r= 500,β= 0.05；收敛条件设定为最优解在连续 10次迭代后保持不变，最大迭代次数为 100。较严格的收敛条件有效的避免了算法过早收敛于局部最值点。在cσ的每个取值下进行 500次独立试验，分别采用Chan算法[8]和本文提出的改进的人工免疫算法进行定位估计。分别取实验结果的均值与真实值的误差和均方根误差作为评价指标。其中均方根误差由下式确定：

其中N为试验次数。两种算法的估计均值和和真实值之间的误差如表1所示，单位为m。

表1 两种算法估计均值与真实值的误差

在不同的到达时间差测量噪声下，两种算法定位估计结果的均方根误差的比较如图3所示。由表1和图3可以看出，在测量噪声cσ较小的情况下，两种算法的性能基本一致。随着噪声的增大，Chan算法的性能迅速恶化，其估计结果的均值和真实值的偏差迅速增大，而改进的人工免疫算法给出的估计位置均值始终较接近真实位置；同时改进的人工免疫算法估计结果的均方根误差也小于 Chan算法，性能则明显优于前者。在cσ为120时，Chan算法估计结果横坐标和纵坐标均值的误差已达-72.2和92.9，而改进人工免疫算法对应的误差仅为 4和-5.6。后者的均方根误差也比 Chan算法小120左右。

图3 两种算法的均方根误差比较

这是由于Chan算法在进行第一次最小二乘法中计算加权系数时忽略了噪声的二次项，导致该算法只能在噪声较小的情况下逼近最优解；随着噪声的增大，噪声的二次项的影响也越来越大，无法忽略，造成算法性能下降。而改进的人工免疫算法直接搜索最大似然解，不存在上述现象，性能较Chan算法有很大改善。

4 结语

本文利用最大似然法求解TDOA定位问题，并提出了一种改进的人工免疫算法解决由此产生的非线性优化问题，采用有指导的进化策略，在编码方式、克隆策略、变异率的设置等方面进行了改进，用于解决TDOA定位估计问题，定位精度较好，性能稳定，在较小的种群规模下仍能较快收敛到全局最优解，与Chan算法相比在噪声较大的情况下更具优势。

[1] 范志平，邓平，刘林. 蜂窝网无线定位[M].北京:电子工业出版社，2002:62-69.

[2] Bersini H, Varela F J. Hints for Adaptive Problem Solving Gleaned from Immune Networks[C]. Dortmod, German: Proceedings of the 1st workshop on Parallel Problem Solving from Nature,1990:343-354.

[3] Castro L N de, Fernando J. Von Zuben. Recent Developments in Biologically Inspired Computing[M]. Hershey, USA: Idear Group Inc., 2004:270-300.

[4] 陈艳玲, 蔡祥宝. 人工免疫算法在光交换网络分组调度中的应用[J].通信技术,2007,40(12):272-273.

[5] 孙名松,郑春光,魏欣南.一种基于人工免疫的垃圾邮件过滤算法[J].通信技术,2009,42(02):85-86.

[6] 汤放奇，李茂军，罗安.人工免疫算法的全局收敛性分析[J].长沙电力学院学报:自然科学版,2004,19(03):1-4.

[7] Silventoinen M I, Rantalainen T. Mobile Station Emergency Locating in GSM[C]. India: IEEE International Conference on Personal Wireless Communications,1996:232-238.

[8] Chan Y T, Ho K C. A Simple and Efficient Estimator for Hyperbolic Location[J].IEEE Trans. on Signal Processing,1994(42):1905-1915.