摘 要： 针对cdma2000-1X网络中无线信号的特点和无源定位的需要，通过将N阶多项式平滑拟合及加权修正的思想融合到遗传算法" title="遗传算法">遗传算法中，提出了一种改进的遗传算法来消除NLOS误差和多径" title="多径">多径传播误差对载干比的影响。不仅避免了遗传算法“早熟”的发生，而且还可以根据实际情况灵活改变搜索精度，使算法搜索达到全局最优，从而实现精确估计信号到达方位的目的。经过场外试验和MATLAB仿真验证该算法可以达到比较好的效果。
    关键词： 无源定位  信号到达时延  信号到达方位  非视距误差  载干比

    由于美国联邦通讯委员会在E-911标准中要求无线通信网络必须能够提供基于移动用户的位置估计的功能，无线定位越来越受到各国公司及研究人员的关注^[1]。利用各种通信标准中现有的资源，在复杂的无线通信环境中提高定位的精度是当前研究的重点。在CDMA系统中为实现符合E-911精度要求的定位，有两个问题必须解决：一是怎样减小基站与用户间的非视距NLOS（Non-Line-of Sight）误差、多径传播误差对定位精度" title="定位精度">定位精度的影响；二是由于CDMA蜂窝系统是一个功率控制系统，当用户发射信号只能被一个基站接收时，怎样实现用户定位，并能使定位精度尽可能得到提高^[2-3]。在此情况下，TOA/AOA（Time of Arrival/Angle of Arrival）是最为有效的方法。该方法中，信号到达角的精确估计是实现高精度定位的必要条件。精确的信号到达角估计必须借助于基站通过通信网络来实现。但在无源定位系统中，被定位对象和基站并不参与定位过程，信号到达角是根据定位设备自身所接收的信息来估计得到的。由于受天线分辨率等因素的影响，往往并不能从测量值中精确估计出信号到达角，而是获得信号到达方位角的范围，即信号到达方位OOA（Orientation of Arrival）。若在定位的后期处理部分加上适当的优化算法也能实现精确定位。
    在天线分辨率确定的前提下，信号到达方位估计得越准确，最后的定位精度也就会越高。而NLOS误差和多径传播误差是信号到达方位准确估计的主要干扰因素。这些因素的存在不仅会使信号到达方位的判断产生偏差，甚至会产生错误判断，所以要提高定位精度就必须消除这些因素的影响。
    遗传算法是近年来智能算法领域提出的解决工程优化问题的一种有效方法，可以用来消除NLOS误差和多径传播误差。但传统的遗传算法并不能有效地消除这些误差的影响，需要对传统的遗传算法进行改进，以便达到比较理想的效果。
    用N阶多项式对一段时间内的测量值进行平滑拟合，根据拟合值与测量值之间的偏差，对平滑值进行加权修正，可以得到近似LOS环境下的测量值^[4]，但是由于受定位时间要求的限制，天线在每个角度的测量值不能太多，并且算法的搜索精度也不能根据实际情况灵活地改变，所以仅采用该方法消除非视距误差和多径传播误差的影响并不能达到理想的效果。
    本文提出了把上述两种方法融合到一起使用的改进遗传算法，经过场外试验和MATLAB仿真验证，改进后的算法能够有效地消除NLOS误差和多径传播误差对测量值的影响，实现准确估计信号到达方位的目的。
1 定位方法及信号到达方位的判断
   在cdma2000-1x无源定位系统中，由于定位的过程是在被定位对象与基站正常通信的基础上通过定位设备来完成的，不需要被定位对象和基站参与定位过程。本文采用的方法如图1所示。 

                     
    当基站与被定位对象通信时，定位设备可以获取信号从基站经被定位对象到达定位设备所需的时延和。由于定位设备和基站的位置是确定的，并且可以通过定位设备利用GPS测量获得。由图1可知，通过定位设备，可得到x+y和z的值，由余弦定理可知：只要得到角度?兹的值，就可以求出x的值。由于基站和定位设备位置是可以直接测得的，若能准确估计出信号从被定位对象到定位设备的到达角，就可以得到被定位对象的具体位置。
    在上述定位过程中，OOA信息的准确获得是实现精确定位的必要前提，而OOA信息是通过对定位设备测得的载波干扰比即载干比CIR（Carrier to Interference Ratio）进行分析获得的。
    在LOS环境下，由于天线有主瓣和旁瓣，当天线正对着信号到达方位时，主瓣也正对信号到达方位，则测量所得到的信号的载干比的均值比较大，而方差则普遍比较小，即载干比的分布比较集中；而当天线偏离信号到达方位时，主瓣也偏离信号到达方位，则测量得到的信号载干比的均值比较小，而方差则普遍较大，即载干比的分布比较分散。上述特点在多次场外试验中也得到了充分验证。针对以上特点，可以把载干比的均值和方差两个量作为判断标准，进而判断天线所对方向与信号的到达方位的偏离程度。由于载干比的值是负值（单位dB），所以可以利用载干比的均值和方差的乘积作为判断指标。若两者的乘积值越大，则表明定位设备的天线所对的方向就越接近信号到达方位；反之，就越偏离信号的到达方位。
    在NLOS环境中，定位设备在各个角度接收到的信号载干比受NLOS误差和多径传播误差的影响比较大，甚至会被这些干扰所淹没，所以直接利用测量所得的载干比的均值和方差进行判断就很难准确地估计天线所对的方向与信号到达方位的偏离程度，甚至会带来很大的偏差。要想使定位设备在各种通信环境中均能实现精确定位，就必须采用一些优化算法消除NLOS误差和多径传播误差的影响。
2 传统遗传算法优缺点分析
    遗传算法(Genetic Algorithm) 是一类借鉴生物界进化规律演化而来的随机搜索方法，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。作为一种新的全局最优化搜索算法，它以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点，在各个领域得到广泛的应用^[5]。
    由于该算法搜索过程不直接作用在变量上，而是对参数集进行个体编码，所以采用合适的编码方法可以灵活改变搜索精度。采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则,并且算法是从串集开始搜索，覆盖面积大，利于全局择优。即使算法的初始串集本身带有大量与最优解甚远的信息，通过选择、交叉、变异操作也能迅速排除与最优解相差极大的串，因此该算法是一个强烈的滤波过程，具有很强的容错能力^[5]。正是由于遗传算法的上述优点，使得遗传算法可以用来消除非视距误差对信号载干比的影响。
    但传统的遗传算法也有其致命的缺点，如“早熟”和局部搜索" title="局部搜索">局部搜索能力差。“早熟”容易导致搜索陷入局部最优解，而局部搜索能力差可能导致搜索后期效率不高，甚至陷入随机搜索的误区。初始化群体的选择和编码方法的选择也会给遗传算法带来很大的影响。因此为了充分发挥遗传算法的性能，就必须对遗传算法进行改进，以达到发挥其优越性而克服其缺陷的目的。
3 N阶多项式平滑及加权修正算法
    该方法的主要思想是：首先对天线在每个角度下的测量值利用N阶多项式进行平滑拟合（N阶多项式的系数是根据测量值用泰勒级数来获得的，采用的最优化准则是最小二乘法）；然后对平滑曲线进行采样，根据平滑曲线采样点与该点所在曲线段的均值的偏差，进行加权修正平滑曲线。加权系数的选取遵循偏差绝对值大加权系数小，偏差绝对值小加权系数大的原则。
    采用该方法可以把NLOS环境下测量得到的测量值通过拟合、平滑加权修正得到近似LOS环境下的测量值，达到消除NLOS误差和多径传播误差的效果，但是该方法也受测量值数量的限制，即在测量值比较少的情况下，采用该方法效果也并不理想^[3]。该方法的修正是在平滑值基础上进行加权修正的，加权系数的选择对算法的性能影响也比较大。加权系数的选取不能太大，否则会引来额外的误差；如果加权系数选取的过小，则不能达到完全消除NLOS误差和多径传播误差的目的，并且该方法的搜索精度不能根据实际情况做适当的改变。因此在测量值受误差影响比较严重或者影响不断变化的情况下并不能有效消除NLOS误差和多径传播误差的影响。
4 改进遗传算法
    改进遗传算法是把N阶多项式平滑及加权修正法与遗传算法融合一起使用。该算法主要是利用N阶多项式拟合加权修正的思想来弥补遗传算法的“早熟”和局部搜索能力差的缺陷；利用遗传算法全局搜索能力强和容错能力强及搜索精度可以灵活改变的优势来弥补加权系数选择的局限对N阶多项式拟合加权修正算法性能的影响，并且有效降低了测量值数量对算法性能的影响，使改进算法的性能在实际应用中得以充分发挥。
    改进遗传算法如下：
    (1)在初始化群体选择时，把N阶多项式平滑、拟合的方法融入其中，实现初始化群体在搜索空间的均匀分布，从而有效避免早熟现象的发生，减小搜索陷入局部最优解得可能性，并且可以降低测量值数量对算法性能的影响。
    实现思路：在测量值的基础上利用最小二乘法和泰勒级数的方法对测量值进行N阶多项式平滑、拟合，形成拟合曲线；然后利用均匀采样的方法对曲线进行采样，把采样所得的值作为测量值的有效补充。假设在每个角度下的测量值个数为N，则经过拟合后的曲线可以分为N-1段。若在改进遗传算法中选择的初始化群体中元素的个数为W=a(N-1),则在选择遗传算法的初始群体时，在平滑曲线的每一段随机选取a个值作为初始化群体的元素，通过上述方法就实现了初始化群体在搜索空间的均匀分布，可以有效避免搜索陷入局部最优的发生。
    (2)在进行编码之前，先对采样点进行等级划分，把采样值均匀划分为2 000个等级，等级划分规则如下：令最小的采样值为Mmin，其等级值Smin=1，最大的采样值为Mmax，其等级值Smax=2001，等级间隔为scale。则： 
   

    假设采样值M的等级值为S_M，则有：
   
    然后把初始化群体中的元素也转换成相应的等级值，参与遗传算法的编码。
    (3)为了使算法能随通信环境的改变而灵活改变搜索精度，在对初始化群体的元素等级进行编码时，采用格雷码" title="格雷码">格雷码进行编码。这样，在通信环境恶劣的情况下，就可以自动增大搜索精度；而在通信环境理想时，就可以自动减小搜索精度，从而使算法能更有效地消除NLOS误差和多径传播误差。
    在本改进算法中，采用格雷码进行个体编码，该码是由自然二进制码转换而来，其转换方法如下：假设自然二进制编码为B=b_mb_m-1…b₂b₁,其对应的格雷码的转换公式为：
   

    格雷码的特点是连续的两个整数所对应的编码值之间只有一个码位是不相同的，任意两个整数的差是这两个整数所对应的格雷码之间的海明距离，这使得在遗传算法中的一次交叉、变异操作也仅使其对应的参数发生微小的变化，有助于提高遗传算法的局部搜索能力，也便于交叉、变异操作，并且可以根据测量值的实际情况对搜索精度做灵活的改变^[5]。
    (4)为了保持样本的多样性，本改进算法采用单点交叉的方法，交叉概率为0.4。这样既可以满足产生新个体的要求，又不会破坏个体的适应度，使算法很容易地搜索到最优解附近，具有很强的全局搜索能力。
    在本文的改进算法中，选取的变异概率为0.001，变异方法是非均匀变异，它相当于整个解向量在解空间作了一个轻微的变动，可以重点搜索原个体附近的微小区域，更有利于搜索到最优解，使算法只需花费很小的代价就可以从最优解附近搜索到达最优解。
    (5)在适应函数选取前把交叉前后的串先进行解码，把等级值转换为载干比值。
实现思路如下：先把格雷码转换为自然二进制码，假设格雷码为：G=g_mg_m-1…g₂g₁，则转化为自然二进制的方法为：
   

    再把解码后的等级值转换成载干比值，转换方法如下：假设采样点N的等级值为S_N，则采样点N的初始值为：
     

    (6)在适应函数选取及复制操作中，把交叉、变异操作前的初始化群体的值和操作后的值按照它们与所在曲线段的均值的偏差的大小进行加权叠加，产生新的初始化群体元素。
    实现思路为：①先找出搜索点所在曲线段，然后求出该曲线段的载干比的平均值;②计算搜索点在交叉、变异操作前的载干比值与所在曲线段的载干比均值的标准偏差，令为f₁;③计算搜索点在交叉、变异操作后的载干比值与所在曲线段的载干比的平均值的标准偏差，令为f₂;④若设搜索点的载干比为CIR1,交叉变异操作后的载干比为CIR2，选择复制后的载干比为new_CIR；令:a₁=f₁/(f₁+f₂), a₂=f₂/(f₁+f₂)则： 
   
    在原来初始化群体元素的基础上,该方法利用交叉、变异操作，对元素附近区域进行搜索，然后根据偏差的大小进行加权修正，充分利用各个曲线段内相邻点之间的相关性，可以更为有效地消除NLOS和多径传播的影响。
    为了减小算法搜索随机性对优化结果的影响，本文采用多次迭代、求平均值的方法。
5 仿真结果及性能分析
    NLOS和多径传播是载干比测量值产生偏差的主要因素，它既可使载干比的测量值产生正向偏差，也可使载干比测量值产生负向偏差，并且偏差的统计特性也是未知的。
    为了充分验证算法在各种通信环境下的性能，本文分两部分进行验证：第一部分是对一般的通信环境（受NLOS误差和多径传播误差影响比较小）测量结果进行验证，第二部分是对通信环境比较复杂情况下（受NLOS误差和多径传播误差影响比较大且不断变化）测量结果进行验证。由于对信号达到方位信息的判断是通过载干比的均值和方差两个指标来衡量的，所以在验证算法性能时，主要也是从优化前后载干比的均值和方差的变化情况来综合衡量算法的性能。
    本文采用MATLAB做仿真验证。仿真结果如图2～图7及表1和表2所示。在图2、4、6中的横坐标表示在每个角度下获得的测量值的个数，在图3、5、7中横坐标表示优化后输出的载干比个数；在图2 、3、4、5中纵坐标表示载干比值（单位dB），在图6、7中纵坐标表示载干比方差。

                          
    其中，表1和表2中的角度偏差是天线所对方向与信号到达方位的偏差，指标是判断角度偏差大小的衡量指标，即载干比的均值与方差的乘积。平均指标是天线在每个角度下所有测量值产生的指标的总和与测量值个数的比值。从图2~3分析可知优化后载干比的均值变化不大，而分布相对比较集中，既方差普遍变小，并且各个角度之间的方差区别更加明显。从表1可以看出，优化后每个测量值的平均指标有所提高，并且区分更为明显。

    场外试验和仿真实验表明，该算法不仅能避免遗传算法“早熟”现象的发生，而且克服了N阶多项式拟合及加权修正的方法不能根据实际情况灵活调整搜索精度的缺陷，并且有效抑制了测量值的数量对误差消除程度的影响，可以有效消除NLOS误差和多径传播误差对测量值的影响，避免错误判断的发生，实现精确估计信号到达方位的目的。

参考文献
[1] 范平志,邓平,刘林.蜂窝网无线定位[M].北京:电子工业出版社,2002.
[2] CAFFERY J. Wireless location in CDMA celluar radio systems [M].Boston:Kluwer Academic Publishers,2000.
[3] CAFFERY J. STUBER L. Subecriber location in CDMA celluar networks [J]. IEEE Trans,on Vehicular Technology,1998,47(2):406-415.
[4] WYLIE M P, HOLTZMAN J. The non-line-of sight problem in mobile location estimate [A].IEEE International  conference on universal person communication Cambridge,Massachusetts,USA, 1996: 827-831.
[5] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,1999.