基于差分演进算法的TDOA定位技术

哈尔滨工程大学本科生毕业论文

摘 要

无线定位服务是一种有着广阔市场前景的移动增值业务，基本原理是利用现有蜂窝网络，通过对各种位置特征参数，包括到达时间(TOA)、到达时间差(TDOA)、到达方向(DOA)的测量和估计，来实现移动用户的定位。本论文对无线通信网络中基于TDOA的无线定位技术进行了研究。

本文分析了国内外相关研究现状，给出了移动台定位的几种基本方法，并给出了TDOA定位的双曲线数学模型，分析了基于TDOA定位的Chan算法、遗传算法(GA)和差分演进算法(DE)，并对其进行了计算机仿真。仿真结果表明，三种算法各有优缺点：Chan算法定位精度较低但运算速度很快，GA算法和DE算法定位精度高但收敛时间较长。

在上述研究的基础上，本论文提出了三种新的定位算法：基于TDOA的Chan-GA算法、Chan-DE算法和Chan-IDE算法。并在相同的仿真环境下进行比较，仿真结果表明，在保证种群数量的情况下，所提的算法性能稳定，能找到逼近全局最优点的解，相对于Chan算法精度更高,相对于以前的算法在保证收敛性能的前提下有更快的收敛速度。

关键词：移动台定位；到达时间差；遗传算法；差分演进算法；免疫算法

哈尔滨工程大学本科生毕业论文

ABSTRACT

Cellular wireless location service is a new mobile value-added service with a good market future. Its basic principle is to implement mobile user location through estimating characteristic parameters relative to position, including time-of-arrival (TOA), time-difference-of-arrival (TDOA), direction-of-arrival (DOA), etc. This thesis aims at the research of wireless location technology based on time-related measurements in Wireless Communication System.

The thesis analyzes the domestic and foreign correlation research of present situation, and gives several essential methods of mobile location. After that, the mathematical model of TDOA hyperbolic equations is established, three location algorithms based on time-difference-of-arrival (TDOA), Chan, genetic algorithm and Differential Evolution are analyzed, and have been carried on the simulation to them. The simulation results show that all the algorithms have the advantages and disadvantages. The Chan algorithm has bad location accuracy and very quick operating speed. To the contrary, the genetic algorithm and Differential Evolution have a high accuracy and a fast convergence time.

Based on the above investigation, three new location algorithms called Chan-GA algorithm, Chan-DE algorithm and Chan-IDE algorithm based on TDOA measurements are put forward. Carrying on the computer simulation to them under the same environment, the simulation results show that if the population size is big enough, the algorithm is robust and can find the coordinates. It has a higher accuracy than Chan algorithms and a faster convergence time than genetic algorithm.

Key words: Mobile location; TDOA; Genetic algorithm; Differential Evolution; Immune algorithm

哈尔滨工程大学本科生毕业论文

目 录

第1章 绪论 ····································································································· 1

1.1 课题研究背景 ························································································ 1 1.2 课题研究的目的和意义 ········································································ 2 1.3 国内外的研究现状 ················································································ 4 1.4 本文的主要工作 ···················································································· 5

第2章 移动台定位的基本方法 ································································ 7

2.1 移动台定位的两种方案 ········································································ 7

2.1.1 基于网络的定位 ········································································· 7 2.1.2 基于移动台的定位 ····································································· 7 2.2 移动台定位技术 ···················································································· 8

2.2.1 基于场强测量的定位方法 ························································· 8 2.2.2 基于传播时间测量的定位方法 ················································· 8 2.2.3 基于信号到达角度测量的定位方法 ······································· 10 2.2.4 混合定位方法 ··········································································· 10 2.3 影响移动台定位精度的主要原因 ······················································ 11 2.4 本章小结 ······························································································ 12

第3章 基于TDOA定位算法的分析及仿真 ····································· 13

3.1 TDOA定位的数学模型 ······································································ 13

3.1.1 定位问题的最小二乘(LS)表示 ················································ 13 3.1.2 TDOA双曲线模型 ··································································· 14 3.2 TDOA定位算法——Chan算法 ························································ 15 3.3 定位准确率的评价指标 ······································································ 20 3.4 本章小结 ······························································································ 21

第4章 遗传算法在TDOA定位中的应用 ·········································· 22

4.1 遗传算法简介 ······················································································ 22

哈尔滨工程大学本科生毕业论文

4.1.1 遗传算法的基本原理 ······························································· 22 4.1.2 遗传算法的特点 ······································································· 23 4.1.3 遗传算法的基本流程图和主要步骤 ······································· 24 4.1.4 遗传算法的基本操作 ······························································· 25 4.2 遗传算法在TDOA定位中的实现 ····················································· 27

4.2.1 TDOA双曲线定位模型 ··························································· 27 4.2.2 改进的遗传算法的实现 ··························································· 29 4.2.3 Chan-GA算法的实现 ······························································ 32 4.3 计算机仿真 ·························································································· 32 4.4 本章小结 ······························································································ 35

第5章 差分演进算法在TDOA定位中的应用 错误！未定义书签。

5.1 差分演进算法简介 ·············································································· 36

5.1.1 差分演进算法的基本原理 ······················································· 36 5.1.2 差分演进算法的特点 ······························································· 37 5.1.3 差分演进算法的优点 ······························································· 38 5.1.4 差分演进算法的流程 ······························································· 38 5.1.5 差分演进算法的参数选取 ······················································· 38 5.2 差分演进算法在TDOA定位中的实现 ············································· 39

5.2.1 差分演进算法的实现 ······························································· 36 5.2.2 Chan-DE算法的实现 ······························································· 40 5.3 计算机仿真 ·························································································· 41 5.4 本章小结 ······························································································ 45

第6章 基于CHAN-IDE的TDOA定位技术 ··································· 35

6.1 免疫差分算法简介 ·············································································· 36

6.1.1 免疫差分算法的基本原理 ······················································· 36 6.1.2 免疫差分算法的基本流程图 ··················································· 37 6.2 基于Chan-IDE算法的TDOA定位技术 ·········································· 39

哈尔滨工程大学本科生毕业论文

6.3 计算机仿真 ·························································································· 50 6.4 本章小结 ······························································································ 54

结论 ······················································································································ 55 参考文献 ············································································································ 56 致谢 ······················································································ 错误！未定义书签。

哈尔滨工程大学本科生毕业论文

第1章 绪论

1.1 课题研究背景

无线定位技术的研究与应用开始于20世纪60年代的自动车辆定位(AVL)系统。80年代以来，随着人们对智能交通运输系统(ITS)的需要及蜂窝移动通信系统的出现，对无线定位技术有了新的要求。蜂窝网络定位技术发展的原动力是美国联邦通信委员会(FCC)于1996年提出的E-911(Emergency call‘911’)紧急呼叫的定位需求，要求在2001年10月1日前，各种无线蜂窝网络必须能对发出E-911紧急呼叫的移动台提供精度在125m内的定位服务，而且满足此定位精度的事件概率不低于67%；在2001年以后，系统必须提供更高的定位精度及三维位置信息。1999年12月，FCC 99-245对E-911需求进一步细化，对网络设备和手机生产厂商、网络运营商等对定位技术在网络设备和手机中的实施和支持提出了明确要求和日程安排。在定位精度要求方面规定：基于蜂窝网络的定位方案(不改动终端)，要求在67%的概率下定位精度不低于150m，95%的概率下定位精度不低于300m；基于移动台的定位方案(可以改动终端)，要求在67%的概率下定位精度不低于50m，95%的概率下定位精度不低于150m。美国FCC的这一规定明确了提供E-911定位服务将是今后各种蜂窝网络，特别是3G网络必备的基本功能[1]。

FCC的规定大大推动了蜂窝网无线定位技术的发展。在蜂窝网通信系统中实现对移动台的定位除了满足E-911定位需求外还具有以下重要用途[2]：

(1) 基于移动台位置的灵活计费，可根据移动台所处位置采取不同的收费标准。

(2) 智能交通系统(ITS)，ITS系统可以方便提供车辆及旅客位置、车辆调度、追踪等服务。

(3) 优化网络与资源管理，精确监测移动台，使网络更好决定进行小区切换的最佳时刻。同时，根据其位置动态分配信道，提高频谱利用率，对网络资源进行有效管理。

1

哈尔滨工程大学本科生毕业论文

(4) 信息服务，对移动台和旅行者定位并向其提供所在区域的信息及其它服务。

(5) 在公安侦查活动中，可用于跟踪被盗车辆及失踪人员。

1.2 课题研究的目的和意义

我们需要的最基本信息就是：时间、地点和内容。随着社会经济的发展，人们的活动范围越来越大，而且越来越不具确定性。这种移动性和不确定性给移动通信带来市场和挑战的同时，也为定位服务的开展和扩大带来了无限商机。同时，对移动通信网本身来说，移动性管理一直是难点。如果知道了移动台的精确位置，进行移动性管理就变得相对简单了，所以，无论是用户的需求，还是运营商或网络供应商的需要，都对定位服务的发展提出了迫切的要求。其主要应用有[2]：

1、紧急救援

当移动手机或车载机持有者遇到紧急情况(交通事故、车辆故障、遇劫及其它)，拨打救援中心电话(如中国的110、美国的911、日本的411等)时，报警用户往往不能提供自己的准确位置。移动通信网络就在将该紧急呼叫发送到救援中心的同时，启动位置服务并得到该用户的具体位置，将位置信息和用户的语音信息一并传送给救援中心。这样，救援中心就可以根据得到的位置信息，迅速、高效地给用户提供紧急救援服务，大大提高了救援的成功率。

2、移动黄页查询

互联网的黄页查询是一项发展比较迅速的网络增值服务。用户通过互联网查询自己所在区域的各种信息，例如，附近的饭店、商场、附近各公司的电话号码及所在位置等。移动互联网技术与位置服务相结合，便可以实现移动黄页查询。移动通信网络首先确定终端用户的位置，然后在互联网提供的信息中挑选出用户所在区域的相关信息供用户查询。

3、位置相关计费

要实现公正、有效的计费是比较困难的。移动用户在通信过程中占用了

2

哈尔滨工程大学本科生毕业论文

网络资源，运营商需要就这一部分资源向用户收取费用。用户所占网络资源的位置(是处于高速公路上正快速移动，还是在家中，是处于话务比较繁忙的商业区，还是处于郊区)不同，网络给用户提供的服务量就不同，所以相应的收费也应不同。但实际上运营商并不知道用户的确切位置，无法判断用户所处的位置特征并实行位置相关计费。但随着定位服务的发展，与位置有关的计费也必将发展起来。

4、对网络欺诈者定位和防盗打管理

对移动通信运营商来说，移动用户恶意欠费、移动电话盗打是困扰已久的问题。利用移动定位技术可以对恶意欠费用户进行定位，以迅速抓住欺诈者，并有效地监测和制止盗打。

5、车辆导航和智能运输系统(ITS)

移动通信网提供的位置服务能满足车辆导航和跟踪。为每一辆(或列)需要导航和跟踪的汽车(或列车)安装一个移动车载台，然后通信网为这些车载台提供位置信息，并将这些信息通过通信网络传输给交通管理的调度中心，便可快速地在车辆和调度中心之间建立协调的运行管理和导航。在移动蜂窝系统中提供对移动台的定位服务后ITS就可利用移动定位技术，对车队运输系统中的车辆和移动资源进行定位，提供车辆及旅客位置信息，检测交通事故和塞车，以实现智能化管理与调度。

6、优化蜂窝移动通信系统设计

移动通信网的移动性管理一直是网络的难点问题。如果网络知道移动台的精确位置，进行移动性管理就变得相对简单，也有助于对移动台进行有效的信道分配，使无线资源的利用程度更高。另外，如果能够实时地得到移动台的位置信息，就可以实现网络资源的动态、智能分配，增强网络性能，提高网络的服务质量。

可以相信，随着定位技术的发展，位置服务的其它潜在应用还将不断涌现。由于定位服务的深远影响，国际标准化组织对移动台定位非常重视，对此展开了专项研究，并加快了制定相关功能规范和信令接口标准的进程。

3

哈尔滨工程大学本科生毕业论文

1.3 国内外的研究现状

蜂窝网移动通信系统无线定位问题，迫切希望得到较完善的实用技术，但是要在移动通信网中实现移动终端的精确定位尚有许多技术难点亟待解决。在CDMA系统中，移动终端定位技术主要需要解决以下几方面的问题：

1、多径传播

无线信号的多径传播现象会使得基于角度和时间的定位方法产生较大的误差。其主要原因是多径传播会对测量代表收发双方实际距离和方位的直射路径(LOS)信号的角度和时延产生较大的干扰。传统的传播时延测量一般采用接收信号和参考信号相关的方法获得，当多径信号时延很近时，多径传播有可能导致相关函数出现多个峰值或主值的展宽，因此导致时延测量精度下降。针对多径信号的时延估计和到达角度估计，许多研究者在此方面做了大量的工作。从研究现状来看，在各种无线环境下如何进一步提高对多径的分辨率仍需要做进一步的研究。

2、非视距路径传播(NLOS)

无论是测向定位还是测距定位，视距传播信号是正确定位的基础。因此，由于移动终端和基站间的直射路径被阻挡而导致的信号非视距路径传播会对基于角度和时间的定位方法带来很大的误差，并且是误差的主要来源。迄今为止，对于非视距路径传播带来误差的抑制，国内外研究者已经做了大量的工作并提出了若干抑制方法，但仍然没有一个有效的方法来解决这一问题。

3、多址干扰

在CDMA系统中，多址干扰是影响系统性能和容量的主要因素。当对定位信号进行测量时，多址干扰的存在仍然会对测量结果产生较大的干扰。在上行链路表现为邻近基站无法得到移动终端发出的定位信号；在下行链路表现为服务基站信号会对邻近基站发出的定位信号产生强烈的干扰，使得当移动终端距离服务基站较近时，无法接收到邻近基站定位信号。因此必须对多址干扰进行抑制。CDMA系统中多用户检测算法的目的就是最大程度的降低多址干扰的影响，但是目前大多数效果较好的多用户检测算法当用户数量较

4

哈尔滨工程大学本科生毕业论文

多时，其运算量都非常大，实际实现较为困难。多址干扰也是当前CDMA蜂窝网的一个重要课题。

目前全球已经有数十家公司研究和提供移动台定位技术，爱立信公司、诺基亚公司和摩托罗拉公司于2000年9月发起成立了定位协作论坛LIF，该论坛的目的就是为了促进移动台定位业务的全球互联互通，到2000年11月大会成立时，已经有73家公司加入了该论坛。日本NTT公司和TOHOKU大学自1999年合作进行了适用于WCDMA系统的在两基站环境的基站搜索方法试验。美国高通公司开发出了两种用于A-GPS定位技术的芯片—MSM3300(for IS-95)、MSM5500(for CDMA2000 1x)，内置GPS解码，2000年下半年发布，2001年6月在国内推广。中国移动通信有限责任公司目前已经开通了移动定位实验局，研究采用TDOA(到达时间差)和CELL ID+TA(小区信息和时间提前量)等技术的移动台定位[2]。

1.4 本文的主要工作

本文的主要研究工作包括：

1、对性能较好的基于TDOA定位的Chan算法进行研究，得出其在噪声加大时，定位精度降低的原因：Chan算法忽略了二次项误差或二阶以上分量。

2、根据遗传算法的基本原理，研究目前性能较好且比较成熟的基于TDOA定位的遗传算法，直接对TDOA定位模型所推导出的似然函数进行操作，从而有效的提高了定位的精度，文中在高斯信道环境下对该算法进行仿真，并与Chan算法进行性能比较，仿真结果表明：该算法有效的提高了定位精度。

3、利用Chan算法的快速收敛特性，把Chan算法的输出作为遗传算法的输入，以缩小搜索范围，加快遗传算法的收敛速度。在高斯信道环境下对其进行仿真，仿真结果表明：与Chan算法进行性能比较，该算法提高了定位精度；与遗传算法进行性能比较，该算法大大加快了收敛速度，基本达到了定位精度与收敛速度的折衷。

5

哈尔滨工程大学本科生毕业论文

4、根据差分演进算法(DE)的基本原理，研究基于TDOA定位的差分演进算法。该算法也是直接对TDOA定位模型所推导出的似然函数进行操作。将Chan算法的运算结果加入其中，研究Chan-DE算法，使其收敛速度加快。文中在高斯信道环境下对该算法进行仿真，结果表明：Chan-DE算法比Chan算法有更高的定位精度，Chan-DE算法比GA算法有更快的收敛速度。

5、利用免疫算法、退火机制和差分演进算法的演进优势，提出快速全局收敛的免疫差分演进算法，进而结合Chan算法，设计了Chan-IDE算法。该算法首先根据移动台所处小区的半径来确定移动台坐标范围，然后采用似然函数的倒数作为适应值，浮点数编码，用抗体矢量中的各分量代表待定坐标，在确定的坐标范围内进行搜索。实验表明，算法性能稳定，通过合理设置种群规模以及变异率，能找到逼近全局最优点的解，相对于其它算法精度更高。

6

哈尔滨工程大学本科生毕业论文

第2章 移动台定位的基本方法

2.1 移动台定位的两种方案

目标移动台或者多个已知坐标位置的固定基站发送定位信号，通过对定位信号的测量，获得相应定位参数的估计后，利用适当的处理方法来获得移动台在空间的位置，这就是移动台定位技术的基本原理[3]。

根据进行定位估计位置的不同，可以将移动台的定位方案分为基于网络的定位和基于移动台的定位[4]。 2.1.1 基于网络的定位

通过移动台传来的信号计算出移动台位置的定位称为基于网络的定位，也称为上行链路定位系统。这种定位方案是依据由多个基站同时检测移动台发射的信号，对这些信号进行精确的到达时间(TOA)的测量，并把这些信息送到一个定位服务中心进行处理，以得到移动台的估计位置。基于网络的定位技术包括基于到达时间(TOA)定位技术、基于到达时间差(TDOA)定位技术、基于到达角(AOA)的技术等。 2.1.2 基于移动台的定位

移动台利用来自基站的信号计算出自己的位置的定位称为基于移动台的定位，也称为下行链路定位系统。这种定位方案是移动台根据自己接收到的多个已知位置基站发射信号携带的与移动台位置有关的特征信息来确定其与各基站之间的几何位置关系，再根据算法对移动台自己进行定位估计。基于移动台定位的系统对每个基站的数据库进行维护，把诸如基站位置和相邻频率的分配表等信息传送给移动台，构成一个定位系统。移动台定位技术包括全球定位系统(GPS)、基于到达时间的定位技术(TOA)以及起源蜂窝小区(COO)。

7

哈尔滨工程大学本科生毕业论文

2.2 移动台定位技术

各种无线电定位系统中，都是通过检测某种信号的特征测量值实现对移动台的定位估计，采用的基本定位方法和技术都是相同或相似的。从几何角度来看，确定目标在二维平面内的位置可以由两条或多条曲线相交得到。为方便叙述，本文后面章节将待定位的目标称为移动台，将参与定位的蜂窝网络基站称为基站。

在蜂窝网络中为移动台提供的地面二维定位服务，通常可供选择的基本定位方法有以下几种。

2.2.1 基于场强测量的定位方法

基于场强测量的定位方法，首先要测量出网络覆盖范围内不同位置上场强的分布，并保存在数据库中，定位时只需要将接收机所测量到的场强与数据库中的数据进行匹配，根据匹配的结果就能确定出移动台的大致位置。这种定位方法对环境的变化很敏感，而且该方法在多径衰落信道条件下的定位精度不高。因此，该方法没有得到广泛的重视和应用。 2.2.2 基于传播时间测量的定位方法

电磁波以恒速(3?108m/s)传播，显然电磁波传播的距离与传播的时间成正比。所以我们只需要测量基站与移动台之间信号的传播时间，就可以得到它们之间的距离。如果基站位置己知，就可以得到移动台的估计位置。基于传播时间测量的定位方法包括TOA(Time Of Arrival)定位、TDOA(Time Difference Of Arrival)位和TOA+TDOA定位。

所谓TOA定位就是测量出两个(或多个)基站与移动台之间的信号传播时间，从而得到两个(或多个)基站到移动台距离的估计值，以基站为圆心，到移动台的距离为半径画圆，多个圆的交点就是移动台的估计位置[4]。当出现多个圆不交于同一点时，可以采用一定的方法消除奇异解而得到一个准确的估计位置。其定位原理如图2.1(1)所示，图中B1、B2、B3代表基站，MS代

8

哈尔滨工程大学本科生毕业论文

表移动台的位置估计，R1、R2、R3分别表示基站B1、B2、B3到移动台MS的距离估计。

图2.1 各种定位方法原理图

TDOA定位法是通过测量电波从移动台(MS)传播到两个基站(BS)的传播时间差(也可以测量出两个不同基站信号到达移动台的传播时间差)来确定移动台的位置的，由该传播时间差对应的距离差可以得到一条以这两个基站为焦点的双曲线。如果能测量到两组TDOA值，那么便可以得到两条双曲线，这两支双曲线的交点即为移动台的估计位置，其定位原理如图2.1(2)所示。

TOA定位有其局限性：第一，它要求发射机和接收机之间有精确的时间同步；第二，发射信号必须用时间标识加以区分，使接收方能辨别出该信号是何时发出的。这两点都不太容易实现，尤其是很难保证精确的时间同步。相比而言，TDOA测量较好地解决了这些问题。它测量两个基站同时发出的信号到达一个移动台的时间差，因此对时间同步的要求比TOA要低，实现起来更容易，而且精度更高[2]。

9

哈尔滨工程大学本科生毕业论文

2.2.3 基于信号到达角度测量的定位方法

该定位方法的原理如图2.1(3)所示。这里所说的信号到达角度，从原理上讲，既可以是基站信号到达移动台的角度，也可以是移动台信号到达基站的角度。但实际上由于接收机通常需要通过天线阵列来测量信号的到达角度，而天线阵列技术目前还不能集成到手机上，因此通常都是由基站来完成信号到达角度的测量，从而得到一根从接收机到发射机的径向连线。当两个基站均获得了信号到达角度测量值后，便可以获得移动台的估计位置[5]。 2.2.4 混合定位方法

混合定位方法，就是使用上面所述定位方法的组合，而不是单一的使用某种定位方法，比如使用TOA+AOA只需要一个基站即可对移动台进行定位，如图2.1(4)所示。另外，也可以使用TDOA+AOA来进行定位。

除了上面介绍的几种蜂窝网无线定位方法外，还有一种基于Cell-ID的蜂窝无线定位方法。Cell-ID是一种最简单的定位方法，它根据移动台所处的小区ID号来确定用户的位置。小区ID号是网络中已有的信息，移动台在当前小区注册后，在系统的数据库中就会将该移动台与当前的小区ID号对应起来。只要系统能够提供该小区基站的地理位置和小区的覆盖半径，并通过广播消息的形式发送给小区覆盖范围内的所有移动台，这些移动台就能知道自己所处的大致位置，其定位精度取决于小区半径。系统只要查询数据库便可获取移动台的位置。在繁华的商业区，由于无线通信系统采用了微型蜂窝小区结构，一个移动台至少可以处于一个微型蜂窝小区的覆盖之中，定位精度不超过100米；如果移动台处于多个小区交叉覆盖的地方，那么在知道这些小区的中心位置和覆盖半径的情况下，就可以很精确地得到移动台的位置，定位精度可以达到50米甚至更小。所以，在城市商业区，Cell-ID定位完全能够满足精度要求。Cell-ID是目前商业化应用最为广泛的网络定位技术。

10

哈尔滨工程大学本科生毕业论文

2.3 影响移动台定位精度的主要原因

在蜂窝网络中，非视距(NLOS)传播、多径效应和多址干扰等因素降低了定位精度，如何克服这些因素的影响是无线定位研究的关键。

1、多径传播。多径传播是移动台定位主要误差源，各种定位法均会由于多径传播引起时间测量误差。窄带系统中各多径分量重叠将造成相关峰位置偏差，宽带系统能够在一定程度上实现对各多径分量分离，据此可以改善定位精度。但是若反射分量大于直达分量、干扰影响等均会引起精度降低。目前已提出一些抗多径传播的有效方法，如高阶谱估计、最小均方估计及扩展的卡尔曼滤波(EKF)等。

2、非视距(NLOS)传播。即使在无多径效应和采用高精度定时的情况下，NLOS传播也会引起TOA或TDOA测量误差。因此，如何降低NLOS传播的影响是提高定位精度的关键。目前降低NLOS传播影响的方法有利用测距误差统计的先验信息将一段时间内的NLOS测量值调节到接近LOS的测量值；降低LS算法中NLOS测量值的权重，在LS算法中增加约束项等。

3、多址干扰。在CDMA系统中，多址干扰在基于时间的定位系统中会严重影响时间粗捕获和延时锁相环的工作。CDMA的功率控制对其通信功能来说可大大降低多址干扰，但对定位来说，采用功率控制使多个参与定位基站难于同时正确测量TOA或TDOA。因为移动台必须与多基站联合工作，而功率控制仅联系一个基站，因而作用较小。可以采用临时提高求救手机功率的办法克服远近效应，但在有多个呼叫时此法不适用。

4、基站覆盖。移动台定位一般要求有3个或3个以上基站同时进行相关处理。现有蜂窝系统用于通信时主要考虑移动台仅与一个基站联系，仅在小区边沿需要切换才与邻近几个基站联系。它尽量使移动台收到强的基站导引信号以保持相干接收，同时，在切换到另一个基站前收到相邻基站导引信号尽量小。目前的网络在有些地区如乡村地区覆盖差，在城市地区由于多径等因素有时也可能难于保证移动台与3个以上的基站的联系。

11

哈尔滨工程大学本科生毕业论文

2.4 本章小结

本章首先介绍了无线定位的两种方案——基于移动台和基于网络的定位；然后介绍了各种移动台定位方法的基本原理，指出了基于TDOA定位的优点，即不需要严格的时间同步；最后简要介绍了影响定位精度的主要原因，以待进一步研究来减弱这些因素的影响。

12

哈尔滨工程大学本科生毕业论文

第3章 基于TDOA定位算法的分析

在2.2节中介绍的几种基于蜂窝网络的移动台定位技术中，TDOA定位技术有定位精度高、算法计算复杂性低、易于实现等诸多优点，因而受到广泛的重视。本章对传统的TDOA定位算法进行分析与仿真研究。

3.1 TDOA定位的数学模型

在无线定位系统中，一旦获得TDOA的测量值，就可以得到移动台到两个基站之间的距离差。多个TDOA测量值就可以构成一组关于移动台位置的双曲线方程组，求解该方程组就可得到移动台的估计位置。但是由于双曲线方程组是非线性方程组，求解起来并不容易。 3.1.1 定位问题的最小二乘(LS)表示

无线定位系统中，对移动台进行定位估计采用最广泛的算法是最小二乘(LS)法[6]。在蜂窝网络中，只要根据某种测量值建立相应的特征方程，就能求解出移动台的位置。

假设在一个无线定位系统中，共测量了M个移动台(MS)的TDOA测量值，根据特征测量值建立的残差方程为fi(X)，当没有任何TDOA测量值误差的先验信息时，可利用使残差误差平方和最小的最小二乘算法实现对MS的位置估计，即：

??argmin?f2(X) (3.1) Xii?1M如果各特征测量值误差的先验信息为已知，可根据该信息设置一个加权因子?i对残差加权，加权最小二乘(WLS)估计器为：

??argmin??2f2(X) (3.2) Xiii?1M由于fi(X)通常为一非线性函数，以上最小二乘问题的求解可以看成一个非线性最优化问题，可通过求解最优化问题的梯度法、单形调优法、高斯牛顿法等递归算法进行求解。

13

哈尔滨工程大学本科生毕业论文

假定MS的位置坐标为(x,y)，各BS的位置坐标为(Xi,Yi)，服务BS位置坐标为(X0,Y0)，各TDOA测量值是以服务BS为参考测得，则残差函数为

fi(X)?di0?((Xi?x)2?(Yi?y)2?(X0?x)2?(Y0?y)2) (3.3)

其中di0为第i个TDOA转化的测量距离差。

按梯度法等递归算法求解式(3.1)，(3.2)时，需要一个MS的初始位置，算法的收敛速度也较慢，并且可能收敛在局部最优，而非全局最优。当MS太靠近BS或靠近以各BS为顶点的多边形圆周时则面临较严重的收敛问题，对于不收敛的情况也不能事先判断。因此，基于TDOA双曲线方程组的特殊性的研究，提出了多种TDOA定位算法。 3.1.2 TDOA双曲线模型

在蜂窝网络中，采用TDOA技术对移动台进行定位估计时，取得某个TDOA测量值，就可以得到移动台到两个基站之间的距离差，多个TDOA测量值就可以构成一组关于移动台位置的双曲线方程组，求解该双曲线方程组就可以得到移动台的估计位置。获得TDOA测量值一般有两种方法，一种是通过直接计算两个基站测量的信号到达时间(TOA)的差值，另一种是采用广义互相关(GCC)技术。

y(x,y)Ri(Xi,Yi)x：源点位置：基站位置图3.1 二维平面示意图

14

哈尔滨工程大学本科生毕业论文

我们只讨论由M个基站(BS)对移动台(MS)进行二维定位估计的问题。如图3.1所示，设M个基站随机分布在二维平面上，(x,y)为MS的待估计位置，

(Xi,Yi)为第i个BS的已知位置。MS和第i个基站之间的距离为[7]：

Ri?(Xi?x)2?(Yi?y)2 (3.4)

Ri2?(Xi?x)2?(Yi?y)2?Ki?2Xix?2Yiy?x2?y2 (3.5)

其中，

Ki?Xi2?Yi2

令Ri,1表示MS与基站i(i?1)和基站1(服务基站)的实际距离差，则

Ri,1?cdi,1?Ri?R1?(Xi?x)2?(Yi?y)2?(X1?x)2?(Y1?y)2 (3.6)

其中，c为电波传播速度，di,1为TDOA测量值。为求解该非线性方程组可以先进行线性化处理。因为：

Ri2?(Ri,1?R1)2 (3.7)

式(3.7)可以展开表示为：

222Ri2,1?2Ri,1R1?Ri?Ki?2Xix?2Yiy?x?y (3.8)

在i?1时，式(3.5)为：

R12?K1?2X1x?2Y1y?x2?y2 (3.9)

式(3.8)减去式(3.9)可得：

Ri2,1?2Ri,1R1?Ki?2Xi,1x?2Yi,1y?K1 (3.10)

其中，

Xi,1?Xi?X1 (3.11) Yi,1?Yi?Y1 (3.12)

将x，y，R1视为未知数，则式(3.10)成为线性方程组，求解该方程组便可以得到MS的坐标位置。

3.2 TDOA定位算法——Chan算法

在蜂窝网络中采用TDOA技术对移动台进行定位估计时，有多种算法可用于求解双曲线方程组，下面介绍一种比较常见的算法——Chan算法。

15

哈尔滨工程大学本科生毕业论文

在遗传算法中评价值被称为个体适应度值，定义一个适应性函数是遗传算法中评价个体优劣的手段，评价的标准因所研究问题的不同而异，它通常由目标函数转化而来，并要求与目标函数有相同的极值点和可行解域，且值域非负，这样就可以将目标函数的极小值问题，转化为求适应函数的极大值问题，便于遗传操作。本文将目标函数的倒数作为适应度函数[12]。在评价中，取其倒数是因为习惯上按从大到小的顺序排列适应值，计算出群体中每个解相应的适应度函数，适应度函数值越大，表示该个体适应度越高，亦即该个体的质量较好，更适应于目标函数所定义的生存环境，因此也应该较其它个体有更多的机会参与遗传操作，并将其优良性能遗传给更多的子代，适应函数为群体进化的选择提供了依据。

4、选择

选择运算是从群体中选择优良的个体、淘汰劣质个体的操作，用于模拟生物界去劣存优的自然选择现象。选择的目的是把优异的个体特性直接遗传到下一代或通过配对交叉将其部分优良特性遗传给新的个体，再遗传到下一代群体。

选择方法有轮盘赌选择法、随机遍历抽样、锦标赛选择等，其中轮盘赌选择法较为常用。首先计算所有个体的适应度值总和和每个个体的适应度值所占适应度值总和的比重。它把种群中所有个体适应度的总和看成一个轮子的圆周，每个个体按其适应度值在总和中的比重占据轮子的一个扇区，每次个体的选择可以看作轮子的一次随机转动，它转到哪个扇区停下来，那个扇区对应的个体就被选中。比重越大，能参与繁殖的概率越大，此概率与其个体适应度的大小成正比。即适合于生存环境的优良个体将有更多的繁殖后代的机会，从而使得优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中“适者生存”的思想。本文中采用轮盘赌法进行个体的选择。

5、交叉

交叉操作利用了来自不同符号串的基因经由交换而混合以产生新符号串的概念，它是根据交叉概率在种群中选取两个个体做为父体和母体，再依交

26

哈尔滨工程大学本科生毕业论文

叉概率将两个个体中位于交叉位后的符号串互换，保留交叉位前的各基因位符号不变，形成两个下一代新个体的遗传操作[10]。由此可以看出，适应度值大的个体参与交叉的机率大，通过交叉把遗传信息传给了子代，使优良的性状更易继承下去。根据交叉点的不同，交叉运算有单点交叉、多点交叉、均匀交叉等多种不同的交叉方法。

6、变异

为了避免落入局部最优，遗传算法中引入了变异算子，变异是为了避免“近亲繁殖”，它可以保持群体的多样性，以避免局部收敛，同时还可以恢复丢失的或寻找未找到的优良信息，在当前解的附近找到更好的解[10]。变异操作可使适应度值小的个体或群体素质趋于一致的个体发生变化，同时防止适应值大的个体变异，从而使每一代保持新鲜个体，避免进化停滞，过早收敛，确保群体能继续优化。

4.2 遗传算法在TDOA定位中的实现

遗传算法在开发最好解和探求搜索空间两方面同时努力，即在探究搜索空间的同时，维持一个潜在解的群体。这一特性对于寻找全局最优点是非常有利的。下面我们将遗传算法用于TDOA定位中。 4.2.1 TDOA双曲线定位模型

如图4.2所示，假设M个接收机随机分布在二维平面上，(x,y)为移动台MS的待估计位置，(Xi,Yi)为第i个基站BS的已知位置。MS到基站i的距离为Ri，令Ri0,1表示MS与基站i(i?1)和基站1(服务基站)的实际距离差，测量值记作Ri,1，则

Ri,1?cdi,1?Ri0,1?cni,1?Ri?R1?cni,1,i?2,?,M (4.1) 式中：c为电波传播速度；di,1是TDOA测量值；ni,1是测量TDOA时引入的噪声，为方便起见，可认为是独立同分布的方差为?2的高斯白噪声。 又因为

Ri?(Xi?x)2?(Yi?y)2 (4.2)

27

哈尔滨工程大学本科生毕业论文

y6kmx：源点位置，坐标（x，y）图4.2 基站与源点位置示意图

所以有

Ri,1?(Xi?x)2?(Yi?y)2?(X1?x)2?(Y1?y)2?cni,1,i?2,3,?,M(4.3)

记作

?R?[R2,1,R3,1,?,RM,1]T(M?1)?1R?[R2,R3,?,RM]T(M?1)?1R1?[R1,R1,?,R1]T(M?1)?1n?[n2,1,n3,1,?,nM,1]T(M?1)?1可得

?(X?x)2?(Y?y)2?(X?x)2?(Y?y)2?2211??2222?(X3?x)?(Y3?y)?(X1?x)?(Y1?y)??R?R?R1?cn???cn (4.4) ????2222??(XM?x)?(YM?y)?(X1?x)?(Y1?y)??本文考虑M?3时的情况。为了充分利用统计信息，采用最大似然法估计源点坐标(x,y)。因为Ri,1服从均值为(Ri?R1)，方差为?2的高斯分布，又因各测量值独立，则似然函数

28

哈尔滨工程大学本科生毕业论文

?1??(?Ri?Ri?R1)2???exp??????22?2??i?1??????M?1?1?????2???M?1?(?R?R?R1)T(?R?R?R1)?exp???2?2?? (4.5)

求使似然函数最大的坐标值，相当于求

??(?R?R?R1)T(?R?R?R1)????(x,y)?arg?max?exp(?)? (4.6) ?22???????也就是求

T(x,y)?argmin?(?R?R?R)(?R?R?R1)?1?? (4.7)

??式(4.7)表明要求解出坐标值，必须求非线性函数的最小值[8]。用解析法求解式(4.7)的非线性函数的最小值是比较困难的。可将式(4.7)的倒数用作适应度函数，在这一章和下一章中应用，用于评价遗传算法和差分进化算法中个体的适应度。

4.2.2 改进的遗传算法的实现

本节对基本遗传算法进行了改进，并根据4.2.1节的数学模型给出了具体的实现方法。

1、染色体编码

由于我们解决的定位问题是二维的，并且采用浮点数编码，所以我们考虑的染色体由两个基因组成。首先根据移动台所处服务基站小区确定移动台的坐标范围：

?xmin?x?xmax (4.8) ?y?y?ymax?min式中，xmin，xmax分别表示基站覆盖区域的横坐标范围的最小值和最大值，

ymin，ymax分别表示基站覆盖区域的纵坐标范围的最小值和最大值。

将待优化的x变量和y变量通过式(4.9)进行归一化处理：

?x?xmin?v(1)[xmax?xmin] (4.9) ??y?ymin?v(2)[ymax?ymin] 29

哈尔滨工程大学本科生毕业论文

将x和y转换为[0,1]区间上的实数v(i),i?1,2，称v(i)为基因，x，y变量对应的基因v(1)和v(2)一起构成该实数编码的染色体，记v?[v(1),v(2)]T。

2、初始化种群

设群体规模为N，在[0,1]区间上生成2?N维均匀随机数矩阵V，

V?{v1,v2,?vN}，作为初始群体的父代个体值。

3、个体适应度值

根据4.2.1节的内容，本文算法中我们取适应度函数[8]为：

1 (4.10) f(zi)?T(?R?R?R1)(?R?R?R1)|zi式中，zi?[xi,yi]T，其中xi和yi为染色体向量v所对应的移动台的坐标。它可以通过将染色体向量v代入公式(4.9)中得到。

4、个体的选择

本文采用轮盘赌选择法，以保证适应度较大的个体能够被遗传到下一代群体中，即

(1) 计算个体的相对适应度

个体的相对适应度pi也可以称为选择概率，它是某个个体被选中的概率，定义[9]为：

pi?fi?fi?1N,i?1,2,?N (4.11)

i从式(4.11)可以看出个体适应度越大，则该个体的相对适应度pi越大，我们可以利用相对适应度pi将最优个体选择进入下一代群体。

(2) 依据选择概率pi生成下一代群体

根据选择概率pi,i?1,2,?N把一个圆盘分成N份，其中第i扇形的中心角为2?pi，如图4.3所示。在进行选择时，假想转动一下圆盘，若某参照点落入到第i个扇形内，则选择个体i。这种选择策略可以通过以下方式实现：在[0,1]内的生成一随机数r，若p0?p1???pi-1?r?p1?p2???pi，则选择个体i，此处假设p0?0。小扇区的面积越大，就越有可能选择该个体，所

30

哈尔滨工程大学本科生毕业论文

以该方法可以将适应度大的个体以较大的概率遗传到下一代群体中[9]。

p1pNp2?2?pi?pi 图4.3 轮盘赌选择法

5、交叉算子

由于本文采用浮点数编码系统，一个基因代表一个优化变量，为保持群体的多样性，采用如下的非一致算术交叉算子[9][10]：

假设在两个父代个体v1和v2之间进行交叉，则交叉运算所产生的新个体

?和v?v12分别为：

??λv1?(1?λ)v2v1 (4.12)

v??λv?(1?λ)v221式中，?为0到1之间的随机数。

6、变异算子

变异操作的目的是为了引进新的基因，增强群体的多样性。

本文采用非均匀变异算子[9][10]，设v，v??分别是要变异的和变异后的个体，则

tb?v?N(B?v)(1?),随机数为0M?MU?T (4.13) v????tb?v?NM?M(v－BL)(1?),随机数为1T?式中，t是迭代次数；T是最大迭代数；v是第t次迭代时的染色体向量，v??是第t?1次迭代时的染色体向量；NM?M是对角矩阵，其对角线元素是在[0,1]间

31

哈尔滨工程大学本科生毕业论文

符合均匀分布的随机数；M是染色体向量的维数；BU是染色体向量取值范围的上界；BL是染色体向量取值范围的下界；b是确定对迭代数依赖程度的

tbN(B?v)(1?)系统参数。从式(4.13)能看出，随着迭代次数的增加， M?MUTtbN(v－B)(1?和 这说明初始搜索在大范围均匀M ?ML ) 项靠近零的概率增加，

T进行，随着迭代次数增加，新产生的染色体靠近父代的概率增加，即强化了对局部空间的搜索，局部微调有助于提高精度。

7、产生新的种群

经过上述选择、交叉和变异操作的个体作为父代，生成下一代种群。 8、评价新种群

根据第3步，计算新种群中每个染色体的适应度值。并判断是否满足终止条件，如果满足则终止；否则重复步骤4~8，直到满足终止条件。本文中将最大迭代次数T作为终止条件。 4.2.3 Chan-GA算法的实现

基于TDOA定位的遗传定位算法虽有好的收敛性能，定位精度很高，但由于搜索范围大，计算时间较长，我们可以利用Chan算法的快速收敛特性，把Chan算法的输出运用到GA算法中，有效缩小最优解的搜索范围，加快遗传算法的收敛速度，达到收敛速度和定位精度的折衷。

根据Chan算法搜索到的局部最优解(xb,yb)，确定Chan-GA算法的搜索区间为[xb?C,xb?C]和[yb?C,yb?C]，即移动台的坐标范围为：

?xb?C?x?xb?C (4.14) ??yb?C?y?yb?C在此基础上对染色体进行编码，其余的选择、交叉和变异过程与改进的遗传算法相同。

4.3 计算机仿真

上面对基于TDOA定位的算法进行了详细的推导分析，本节在前面的基

32

哈尔滨工程大学本科生毕业论文

础上讨论分析不同算法在高斯噪声环境下的性能。

仿真背景和参数设置如下：考虑蜂窝网如图4.2所示，蜂窝半径为3km，有5个基站，其位置分别为(0,0),(33,3),(33,?3),(0,?6),(?33,?3)；源点位置为(1,2.5)。

改进的遗传算法中，种群数为70，交叉概率Pc为0.15，变异概率Pm为0.25，迭代次数为60，系统参数b取6。独立运行1000次，评价指标采用3.3节给出的平均估计坐标MV和均方误差MSE。便于比较，Chan-GA算法的参数与改进的遗传算法取相同值。仿真所得平均估计坐标MV如表4.1所示。图4.4给出了不同算法均方误差与测量误差(dB)之间的关系。

表4.1 三种算法的MV比较

10lg(c?) /dB ?20 ?18

Chan算法 的MV （0.9998，2.5001） （0.9995，2.5004） （1.0000，2.4972） （1.0016，2.4955） （1.0014，2.4919） （1.0012，2.4807）

GA算法 的MV （1.0118，2.4835） （1.0101，2.4860） （1.0112，2.4838） （1.0128，2.4817） （1.0105，2.4859） （1.0115，2.4856）

Chan-GA算法 的MV （1.0037，2.4957） （1.0032，2.4963） （1.0029，2.4957） （1.0044，2.4941） （1.0033，2.4965） （1.0020，2.4996）

?16

?14 ?12 ?10

表4.1中的Chan算法栏是Chan算法的仿真结果(独立运行1000次)；GA算法栏是文献[8]中改进的遗传算法的仿真结果；Chan-GA算法栏是本文提出的Chan-GA算法的仿真结果，其选取的参数与GA算法一致，只是将Chan算法的定位结果上下浮动0.5km。表中第1栏10lg(c?)是根据蜂窝网通信系统与系统热噪声等原因确定的[8]。

从图4.4可以看出，当测量误差很小时，Chan算法和Chan-GA算法的性能优于GA算法；但是当测量误差加大时，Chan算法的性能恶化，GA算法

33

哈尔滨工程大学本科生毕业论文

和Chan-GA算法的性能明显好于Chan算法，其主要原因是此时噪声的二次项带来的影响越来越大，变得不可忽视，导致Chan算法性能下降，而另外两种算法都是对最大似然函数进行移动台位置搜索，避免了这种影响。

图4.4 三种算法的MSE的比较

下面我们来进行一下收敛速度的仿真比较，为了便于比较，我们将GA和Chan-GA两种算法的终止迭代次数定为40。图4.5给出了两种算法的MSE收敛性能曲线。

图4.5 两种算法的MSE收敛曲线的比较

34

哈尔滨工程大学本科生毕业论文

图4.5是GA算法和Chan-GA算法是在测量误差为?16dB的条件下的MSE收敛曲线，通过比较可以看出，Chan-GA算法的收敛速度很快，在30代时就比GA算法45代的结果要好，这是因为Chan-GA算法引入了Chan算法的快速收敛特性，将Chan算法的结果运用到GA算法中，使GA算法解的搜索范围大大减小了，在不影响定位精度的同时有效提高了搜索解的速度。

4.4 本章小结

本章主要介绍了遗传算法的基本原理、改进的遗传算法在TDOA定位中的实现过程以及Chan-GA算法在TDOA中的实现。综合本章算法分析和计算机仿真可见，当测量误差很小时，Chan算法和Chan-GA算法的性能优于GA算法；当测量误差加大时，Chan-GA算法、GA算法与Chan算法相比，能够得到更准确的定位估计。这是因为遗传算法直接根据似然函数进行求解，而没有引入二次项误差。而与GA算法相比，Chan-GA算法由于引入Chan算法快速收敛的特性，将Chan算法的仿真结果直接运用到GA算法中，在不影响算法定位精度的同时，有效提高了搜索速度，达到定位精度和收敛速度的折衷。

35

哈尔滨工程大学本科生毕业论文

第5章 差分演进算法在TDOA定位中的应用

根据差分演进算法的基本原理，从另一个角度研究了一种适用于TDOA定位的差分演进算法，并进行了计算机仿真，与Chan算法和GA算法进行了性能比较，证明了方法的可行性和有效性。

5.1 差分演进算法简介

差分演进算法[11](Differential Evolution，DE)是由Storne等人于1995年提出的，最初的设想是用于解决切比雪夫多项式问题，后来发现DE也是解决复杂优化问题的有效技术。DE与人工生命，特别是进化算法有着极为特殊的联系。

5.1.1 差分演进算法的基本原理

DE是一种基于群体进化的算法，具有记忆个体最有解和种群内信息共享的特点，即通过种群内个体间的合作与竞争来实现对优化问题的求解，其本质是一种基于实数编码的具有保优思想的贪婪遗传算法。差分演进算法与标准的遗传算法一样，都包含有选择，交叉和变异三个操作。于遗传算法不同的是，DE采用的是由变异到交叉再到选择的操作顺序[12]。

算法的基本思想是[13]：首先在问题的可行解空间随机初始化种群

000Np为种群规模。个体xi0?[xi0,1,xi0,2,?,xi,DX0?{x1,x0]用于表征问2,?,xNp}，

题解，D为优化问题的维数。算法的基本思想是：对当前种群进行变异和交叉操作，产生另一个新种群；然后利用基于贪婪思想的选择操作对这两个种群进行一对一的选择，从而产生最终的新一代种群。具体而言，首先通过式(5.1)对每一个时刻的个体xit实施变异操作，得到与其相对应的变异个体vit?1，即

ttt vit?1?xr. (5.1)?Fx?xrr123tt其中，r1,r2,r3??1,2,?,Np?互不相同且与i不同；xrt1为父代基向量；xr?xr23????称作父代差分向量；F为缩放比例因子。然后利用式(5.2)对xit和由式(5.1)生

36

哈尔滨工程大学本科生毕业论文

成的变异个体vit?1实施交叉操作，生成试验个体uit?1，即

ut?1i?vit?1,If?rand?j??CR?or??t?xi,Otherwise.j?rnbr?i?; (5.2)

rand?j?为?0,1?之间的随机数；rnbr?i?其中：CR为范围在?0,1?之间的交叉概率；

1,2?D?之间的随机量。利用式(5.3)对试验个体uit?1和xit的目标函数进行为?比较，对于最小化问题，则选择目标函数低的个体最为新种群的个体xit?1，即

x其中f为目标函数。

5.1.2 差分演进算法与传统进化算法的不同

综上所述，DE算法与传统的进化算法有三点明显的不同[14]：

(1)DE算法中都是使用实数编码，而传统的二进制编码多以二进制编码为主，但是近期的进化算法也慢慢改用实数编码作为个体编码方式。

(2)在进化算法中，通常是选择两个个体进行交叉操作重组产生子代，而在DE算法中，子代的产生式通过三个母体的扰动作用而产生的。步：进行选择操作，得到新种群。

(3)在DE算法中新产生的个体保留与否是通过与被选出来进行比较替换的标志向量进行优劣对比而决定的。 5.1.3 差分演进算法的优点

相对于其他进化算法，DE保留了基于种群的全局搜索策略，采用实数编码，基于差分的简单变异操作和一对一的竞争生存策略，降低了遗传操作的复杂性。同时，DE特有的记忆能力使其可以动态跟踪当前的搜索情况，以调整其搜索策略。

归纳起来，DE算法具有如下优点[12]： (1)算法通用，不依赖于问题信息；

37

t?1i?uit?1,Iffuit?1?fxit; (5.3) ??t?xi,Otherwise.????哈尔滨工程大学本科生毕业论文

(2)算法原理简单，容易易实现； (3)群体搜索，具有记忆个体最优解的能力；

(4)协同搜索，具有利用个体局部信息和群体全局信息指导算法进一步搜索的能力；

(5)易于与其他算法混合，构造出具有更优性能的算法。 5.1.4 差分演进算法的流程

DE算法可以按照下面的流程进行计算[15]：

第1步：确定DE控制参数及采用的具体策略，DE控制参数包括：种群规模Np，交叉因子CR，最大进化代数T，终止条件等。

第2步：随机产生初始种群。

第3步：对初始种群进行评价，即计算初始种群中每个个体的目标函数值。

第4步：判断是否达到终止条件或进化代数达到最大，若是，则进化终止，将此时的最佳个体作为解输出；若不是，则继续。

第5步：进行变异操作 第6步：进行交叉操作

第7步：对边界条件进行处理，得到临时种群，并对临时种群进行评价，计算临时种群中，每个个体的目标函数值。

第8步：进行选择操作，得到新种群。 第9步：进化代数T?T?1，转第4步。 5.1.5 差分演进算法的参数选取

影响差分演进算法性能的三个主要参数[16]：种群规模Np，缩放比例因子F，交叉概率CR。试验表明：在给定最大进化代数情况下，种群规模要适中，才能很好的保持多样性和收敛速度的平衡，如果种群规模较大，就要付出较大的进化代数为代价。缩放比例因子对算法的局部搜索和全局搜索起

38

哈尔滨工程大学本科生毕业论文

到了一定的调节作用， 缩放比例因子较大时，有利于保持种群多样性和全局搜索能力，较小时，有利于局部搜索和提高收敛速度。所以，缩放比例因子的取值既不能太大，又不能小于某一特定值，取值在?0.5,1?之间时算法才能取得较好的效果。交叉概率较小时，收敛速度较慢，但成功率较高，算法稳定性好，较大时，常常会加速收敛，但易于陷入局部最优，发生早熟现象，成功率差，算法的稳定性差。可见，成功率和收敛速度是一对矛盾。

5.2 差分演进算法在TDOA定位中的实现

5.2.1 差分演进算法的实现

本节中，我们将差分演进算法应用到TDOA定位中。本节的算法是建立在小节4.2.1所建立的TDOA双曲线定位模型上。根据5.1.1和5.1.4节，可以很方便的实现差分演进算法在TDOA定位中的应用。

1、个体编码

由于我们解决的定位问题是二维的，并且采用实数编码，所以我们考虑的个体由两个基因组成。首先根据移动台所处服务基站小区确定移动台的坐标范围：

?xmin?x?xmax (5.4) ??ymin?y?ymax式中，xmin，xmax分别表示基站覆盖区域的横坐标范围的最小值和最大值，

2、初始化种群

根据式(5.4)确定的坐标范围，生成2?N维均匀随机数矩阵V，

V?{v1,v2,?vN}，作为初始种群，初始种群的种群规模是Np。个体

vi?(vi,1,vi,2,?,vi,D)用于表征待估计得坐标，因为所研究是在二维的平面上所以D?2。vi,1和vi,2分别表示个体向量vi所对应的移动台的坐标xi和yi。

3、计算个体适应度值

根据4.2.1节的内容，我们取适应度函数[8]为：

39

哈尔滨工程大学本科生毕业论文

f(zi)?1 (5.5) T(?R?R?R1)(?R?R?R1)|zi式中，zi?[vi,1,vi,2]T,其中vi,1和vi,2分别表示个体向量vi所对应的移动台的坐标xi和yi。

4、变异操作

根据（5.1）式的原理，对每一个时刻的个体vit实施变异操作，得到与其相对应的变异个体xit?1，即

ttt xit?1?vr (5.6) ?Fv?vrr123??式中xit?1表示变异个体

5、交叉操作

利用式（5.7），把vit和由式（5.6）生成的变异个体xit?1实施交叉操作，生成试验个体uit?1，即

u6、选择操作

分别计算个体vit和试验个体uit?1的适应度值，对个体vit和试验个体uit?1的适应度值进行比较，选择适应度值高的个体最为新种群的个体vit?1，即

?uit?1,Iffuit?1?fvit;t?1 vi??t (5.8)

?vi,Oherw .iset?1i?xit?1,If?rand?j??CR?orj?rnb?ir?; (5.7) ??t. i s e ?vi,Otherw????其中fuit?1为试验个体uit?1的适应度，fvit为个体vit的适应度。

7、产生新的种群

经过上述变异、交叉和选择操作的个体作为父代，生成下一代种群。 8、评价新种群

根据第3步，计算新种群中每个染色体的适应度值。若新种群的平均适应度值较高，则选择新种群，淘汰原种群；若原种群的适应度值较高，则选择原种群，淘汰新种群。并判断是否满足终止条件，如果满足并判断是否满足终止条件，如果满足则终止；否则重复步骤4~8，直到满足终止条件。本文中将最大迭代次数作为终止条件。

40

????

哈尔滨工程大学本科生毕业论文

5.2.2 Chan-DE算法的实现

同Chan-GA算法类似，我们将Chan算法的输出结果运用到DE算法，来缩小最优解的搜索范围，加快DE算法的收敛速度，达到收敛速度和定位精度的折衷。

根据Chan算法搜索到的局部最优解，确定Chan-DE算法的搜索区间为和，即移动台的坐标范围为：

?x?C?x?xb?C ?b (5.9)

y?C?y?y?Cb?b在此基础上产生初始种群，其余具体过程与DE算法类似，此处不再赘述。

5.3 计算机仿真

上面对基于TDOA定位的DE算法进行了推导分析，本节对该算法在高斯噪声条件下进行了仿真，并与其他算法进行了性能比较。

为了便于比较，仿真背景与4.3节相同。参数设置如下：种群数为70，迭代次数为60，缩放比例因子F?0.5，交叉概率CR?0.2，仿真所得平均估计坐标MV如表5.1所示。图5.1给出了不同算法定位均方误差与高斯噪声方差(dB)之间的关系。表5.1中的Chan算法栏是Chan算法的仿真结果；GA算法栏是GA算法的仿真结果；Chan-DE是本文提到的算法的仿真结果。表中第1栏的10lg(c?)是根据蜂窝网通信系统与系统热噪声等原因确定的。

41

哈尔滨工程大学本科生毕业论文

表5.1 Chan算法、GA算法及Chan-DE算法MV

10lg(c?)

/dB

Chan算法 的MV (1.0001,2.5000) (0.9995,2.4998) (0.9995,2.5010) (1.0011,2.4931) (0.9994,2.4914) (0.9989,2.4878)

GA算法 的MV (1.0119,2.4837) (1.0107,2.4844) (1.0103,2.4864) (1.0115,2.4816) (1.0110,2.4806) (1.0086,2.4895)

Chan-DE算法

的MV (1.0004,2.4992) (0.9991,2.5002) (0.9998,2.5012) (1.0005,2.4974) (0.9986,2.4984) (0.9994,2.5005)

?20 ?18 ?16 ?14 ?12

?10

图5.1 Chan算法，GA算法和Chan-DE算法得MSE比较

从图5.1可以看出，在测量误差很小时，Chan算法、Chan-DE算法性能优于GA算法，GA算法容易陷入局部收敛，而当测量误差加大时，GA算法、Chan-DE算法的性能要比Chan算法好，这是因为Chan算法对噪声二次项的忽略导致的。我们还能看出Chan-DE算法性能要好于GA算法，并且其计算量远远少于GA算法，是一种快速收敛的算法。因为Chan-DE算法在解的搜索过程中引入了Chan算法的局部最优解。

42

哈尔滨工程大学本科生毕业论文

下面我们来进行一下收敛速度的仿真比较，为了便于比较，我们将GA和Chan-DE两种算法的终止迭代次数定为40。图5.2~图5.5给出了三种算法在不同测量误差环境下的MSE收敛性能曲线。

图5.2 ?16dB时Chan、GA与Chan-DE的MSE收敛性能曲线

图5.3 ?14dB时Chan、GA与Chan-DE的MSE收敛性能曲线

43

哈尔滨工程大学本科生毕业论文

图5.4 ?12dB时Chan、GA与Chan-DE的MSE收敛性能曲线

图5.5 ?10dB时Chan、GA与Chan-DE的MSE收敛性能曲线

由图5.2~图5.5三种算法在不同测量误差环境下的 MSE 收敛性能曲线可以看出，在测量误差很小时，Chan-DE算法与Chan算法性能相近，但都优于GA算法。当测量误差加大时，Chan-DE算法和GA算法优于Chan算法。但是Chan-DE算法的性能一直好于GA算法和Chan算法，是高精度收敛的算法。从图中还可以看出，Chan-DE算法的收敛速度极快，在5代左右就可达到近似全局收敛，而GA算法要在30代才能收敛，且克服了遗传算法局部收敛的缺点，这是因为Chan-DE算法使用了较小的搜索区间。

44

哈尔滨工程大学本科生毕业论文

5.4 本章小结

综合本章算法分析和仿真的结果可见，所提出的Chan-DE算法在仿真中表现稳定，与Chan算法相比有更高的稳定性，与GA算法相比有更快的搜索速度和更高的搜索精度。这是因为该算法直接根据似然函数进行求解，没有引入二次项误差，所以提高了定位精度。同时将Chan算法的快速收敛性引入其中，有效提高了DE算法的定位速度。

45

本文来源：https://www.bwwdw.com/article/0wfa.html