基于差分演进算法的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

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

Chan算法是一种具有解析表达式解的非递归的双曲线方程组解法。该算法的特点是计算量小，在噪声服从高斯分布的环境下，定位精度高。但在非视距(NLOS)环境下，Chan算法的定位精度显著下降。下面根据参与定位的基站数目分两种情况进行讨论。

1、基站数为3时的算法

当有效测量基站数为3时，可得到两个TDOA测量值，先假定R1为己知，则MS位置(x,y)可由式(3.10)按以下形式解出：

2??X2,1Y2,1??x?1?R2,1?K2?K1????R2,1?????R????2?? (3.13) ?X??1?y?YRR?K?K2?3,1???31???3,1?3,1??3,1???1式中，

K1?X12?Y12

2K2?X2?Y22 K3?X32?Y32

将式(3.13)代入式(3.4)，令i?1，得到一个关于R1的二次方程，将其正根代入式(3.13)，就得到MS的估计位置。在某些情况下，可能有两个正根，这种模糊性可由有关先验信息进行选择。

2、基站数为4个以上时的算法

当有效测量基站数为4个以上时，该算法能利用网络提供的所有TDOA测量值并取得更好的计算结果。此时TDOA测量值数目多于未知量数目，因此，初始非线性TDOA方程组应首先转换为线性方程组，然后采用加权最小二乘算法(WLS)得到一初始解，再利用第一次得到的估计位置坐标及附加变量等已知的约束条件进行第二次WLS估计，最后便能得到改进的估计位置。

TT令za?[zTp,R1]为未知矢量，其中zp?[x,y]，从式(3.10)中求出的具有

TDOA噪声的误差矢量为：

0 (3.14) ψ?h?Gaza式中，

16

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

?R22,1?K2?K1??2?1?R3,1?K3?K1?h?

??2??2?R?K?K?M,1?M1???X2,1Y2,1?XY3,13,1?Ga??????XM,1YM,1R2,1?R3,1?? ???RM,1?0在此我们定义无噪声时?*?的表达式为?*?，故di,j?di0,j?ni,j，

000di,j?di0,j?ni,j；又由于Ri?Ri,1?R1，可得噪声的误差矢量为：

ψ?cBn?0.5c2n⊙n (3.15)

式中，

000 B?diagR2,R3,?,RM??式中，⊙代表Schur乘积。当SNR高时，由广义互相关方法(GCC)检测的TDOA测量值通常为高斯数据，服从近似的正态分布，因此噪声矢量n也服从近似的正态分布，误差矢量的协方差矩阵便可算出。在实际应用中条件cni,1??Ri0通常可以满足，因而式(3.15)中第二项可以忽略，误差矢量ψ成为具有以下协方差矩阵的高斯随机矢量:

Ψ?E[ψψT]?c2BQB (3.16)

其中，Q为TDOA协方差矩阵，za中R1与式(3.4)有关，表明式(3.14)仍然是以x和y为变量的非线性方程组。

求解该非线性方程组时首先假定x，y和R1之间无关，然后通过WLS算法进行第一次求解。最终结果可通过将已知关系(R1与x，y之间关系即式(3.4))代入第一次的结果中，再进行一次WLS计算得出。这两步是对MS位置的最大似然(ML)估计的近似。

如果假定za的元素相互独立，za的ML估计为：

za?argmin(h?Gaza)TΨ?1(h?Gaza)TT?(GaΨ?1Ga)?1GaΨ?1h?? (3.17)

17

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

该式是式(3.14)的WLS解，目前该式还不能解出，因为B中含有MS和各基站发射机之间的距离，故Ψ仍然是未知量。为此，需作进一步近似。

当MS与各BS距离很远时，Ri0(i?2,3,?M)与R0(定义距离)接近，故

B?R0I。由于Ψ的量纲没有什么影响，式(3.17)可近似为

T?1T?1za?(GaQGa)?1GaQh (3.18)

如果MS与各BS距离较近，利用上式可得到一初始解用于计算B矩阵，第一次WLS计算的结果可由式(3.17)得到。

为进行第二次WLS计算，需首先计算估计位置za的协方差矩阵。该矩

T阵可通过计算za的期望值及zaza得到。由于Ga含有随机量Ri,1，直接计算很

困难，该协方差矩阵可采用扰动方法计算。在有噪声的情况下：

Ri,1?Ri0,1?cni,1 (3.19)

0且Ga?Ga??Ga，h?h0??h。

00za?h0，式(3.14)表明： 由于Ga0ψ??h??Gaza (3.20)

0??za，由式(3.17)可得： 令za?za0TT000TT(Ga??Ga)Ψ?1(Ga??Ga)(za??za)?(Ga??Ga)Ψ?1(h0??h) (3.21)

保留线性扰动分量，再利用式(3.15)和式(3.20)，?za及其协方差矩阵为：

0T0?10T?za?c(GaΨ?1Ga)GaΨ?1Bn (3.22) 0T?10?1cov(za)?E[?za?zTa]?(GaΨGa) (3.23)

其中，忽略了式(3.15)的平方项，式(3.22)用于计算cov(za)。

上述有关za的计算过程假定x，y和Ri是相互独立的。事实上式(3.4)表明它们是相关的，因此，我们可以利用这种关系来改进定位估计。当TDOA测量误差较小时这种偏差可以忽略，矢量za为一均值为实际值，协方差矩阵由式(3.13)确定的随机矢量，因此za中各元素可表示为：

za,1?x0?e1， za,2?y0?e2， za,3?R10?e3 (3.24)

其中，e1，e2，e3为za的估计误差。za的前两个元素减去X1，Y1，再对各

18

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

元素求平方可得另一方程组：

ψ??h??Gaz?a (3.25)

式中，

?(za,1?X1)2??10??(x?X1)2??2?????01，z?h???(za,2?X2)?，Ga a??2???2?(y?Y1)???z??11a,3????这里ψ?定义为za的误差变量。将式(3.24)代入式(3.25)中得： ??2(x0?X1)e1?e12?2(x0?X1)e1ψ1020ψ?2?2(y?Y1)e2?e2?2(y?Y1)e2 (3.26) 020ψ??2Re?e?2R31331e3这里的近似只有在误差ei较小时才能成立，该过程是对ML估计的又一近似。

ψ?的协方差矩阵：

Ψ??E[ψ?ψ?T]?4B?cov(za)B? (3.27)

其中，

B??diag{x0?X1,y0?Y1,R10}

由于ψ为高斯分布，因此ψ?也为高斯分布，z?a的ML估计为：

?T??1Ga?)?1Ga?TΨ??1h? (3.28) z?a?(GaΨ矩阵Ψ?由于含有MS真实位置，因此为一未知量。不过，B?能通过使

0用za值计算出，式(3.22)和式(3.23)中的Ga可以使用Ga近似，式(3.16)中的B能使用式(3.18)的计算结果进行近似。如果MS处在较远距离，za协方差矩阵可近似表示为：

0T0?1cov(za)?c2R0(GaQ?1Ga) (3.29)

2式(3.28)可简化为：

?T??1T?1??1??1?T??1T?1??1)h? (3.30) z?a?(GaBGaQGaBGa)(GaBGaQGaB?为常量，代入z???T矩阵Gaa和z?aza后，za的协方差矩阵为：

?T???1cov(z?a)?(GaΨGa) (3.31)

最终MS定位计算结果为：

19

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

?X1??X1???zp?za??? 或 zp??za??? (3.32) ?Y1??Y1?选择位于定位区域内的zp作为问题的解。如果z?a的某个坐标接近于零，式(3.32)中的平方根为虚数，这种情况可将其设为零，定位估计的协方差矩阵可

00由式(3.25)中的z?a加上x?x?ex，y?y?ey得到：

0202z?a,1?(x?X1)?2(x?X1)ex?ex0202z?a,2?(y?Y1)?2(y?Y1)ey?ey (3.33)

22与x0，y0相比，ex，ey很小，可省略ex，ey，利用式(3.16)、(3.22)、(3.27)、

和(3.32)进行定位估计，估计值zp的协方差矩阵Φ为：

Φ?cov(zp)?1?1???1B??cov(z?a)B (3.34) 40T?1?1?10?TB??1Ga?B??)?1?c2(B??GaBQBGaB??1Ga式中，

?(x0?X1)?0B????? 00(y?Y1)??4个以上基站的Chan算法可归纳为：远距离MS的位置可通过式(3.18)、(3.30)和式(3.32)进行估计，定位估计的协方差矩阵可由式(3.34)计算；定位近距离MS时，由式(3.18)可计算出一近似B矩阵，再分别采用式(3.17)、(3.28)和式(3.32)计算出定位结果，定位估计的协方差矩阵可由式(3.34)计算。在TDOA距离差误差较小时该算法给出了能达到CRLB的表达式解，但也需要有关MS位置的先验信息以解决式(3.32)中存在的不确定性。在文献中该算法的推导过程都是基于TDOA误差较小且为理想的零均值高斯随机变量这个前提，因此可以预计，对于实际信道环境中误差较大的TDOA测量值，该算法的性能将受到较大影响。

3.3 定位准确率的评价指标

双曲线定位的准确率需要一系列指标进行评价，文中将定位解的平均估计坐标(MV)和均方误差(MSE)作为算法性能的评价标准。

20

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

在二维定位估计中计算MV和MSE的方法为：

MV?E[(x,y)] (3.35)

?)2?(y?y?)2] (3.36) MSE?E[(x?x?,y?)为MS估计位置。 其中，(x,y)为MS实际位置，(x3.4 本章小结

本章主要给出了TDOA定位的数学模型，研究了基于TDOA的常见算法——Chan算法。综合分析可见，Chan算法为非递归算法，其解为明确的解析表达式，但需要一些有关MS位置的先验信息以解决其解存在的模糊性。在蜂窝网络信道环境中，Chan算法是定位性能很好的一种算法。因此，Chan算法是一种比较适合在蜂窝网络环境中对MS进行定位估计的算法[2]。在本章最后给出了定位准确率的评价指标：平均估计坐标和均方误差。平均估计坐标与实际位置越接近，均方误差越小，定位准确率越高，性能越好。

21

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

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

本章根据遗传算法的基本优化原理，研究了适用于TDOA定位的改进的遗传算法[8]。该算法首先根据移动台所在服务区来确定移动台的坐标范围，然后采用似然函数的倒数作为个体适应度值来选取优良个体并进行遗传操作，在服务台所确定的坐标范围内搜索移动台位置。仿真结果说明，算法的性能稳定，能得到较高精度的解。

4.1 遗传算法简介

4.1.1 遗传算法的基本原理

遗传算法(Genetic Algorithm，GA)是建立在自然选择和群体遗传学基础上的搜索方法，是由美国Michigan大学的Holland教授首先提出并发展起来的[9]。

遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现(即基因型)是某种基因组合，它决定了个体形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射，即编码工作。初始种群产生之后，按照“适者生存”和“优胜劣汰”的原理，逐代演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合、交叉和变异，产生出代表新的解集的种群。这个过程将导致种群像自然进化的一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，可以作为问题近似最优解[10]。

遗传算法是自然遗传学和计算机科学相互结合渗透的产物，借用了许多自然进化的基础术语。下面我们对一些术语进行简单的介绍：

(1) 群体和个体

遗传算法处理的是染色体，或者叫基因型个体，通常以一维串结构数据

22

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

来表示；一定数量的个体组成群体。

(2) 适应度函数

各个个体对环境的适应程度叫做适应度。遗传算法对适应度函数并不要求可导等条件，只要求适应度函数是非负函数，同时要求把待解优化问题表达为最大化问题，即目标函数的优化方向为适应度函数的增大方向，所以有广泛的应用。在解决TDOA问题中，适应度函数就是目标函数。

(3) 编码和解码

遗传算法必须包含两个必须的数据转换操作，即把搜索空间中的参数或解转换成遗传空间中的染色体或个体，称为编码；反之，称之为解码。

(4) 遗传操作

遗传操作中包括三种主要操作，分别是选择、交叉和变异操作(详细在4.1.4节介绍)。 4.1.2 遗传算法的特点

遗传算法的特点[11]可以从它和传统搜索方法对比可以充分体现出来： 1、遗传算法不是直接作用在参变量集上，而是利用参变量集的某种编码 遗传算法的处理对象不是参数本身，而是对参数集进行了编码的个体。此编码操作，使遗传算法可直接对结构对象进行操作。这一特点，使得遗传算法具有广泛的应用领域。

2、遗传算法不是从单个点，而是从多个点的群体开始搜索

传统方法都是单点搜索，从一点移到另一点。这种点对点的搜索常常会陷入局部最优解；而遗传算法采用同时处理多个点的方法，对多个解进行评估，具有全局搜索性能，同时也易于并行化。

3、遗传算法利用适应值信息，无需导数和其他辅助信息

遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，对于输入可计算出正的函数值。这使得该算法的应用范围大大扩展。

23

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

4、遗传算法利用概率转移规则，而非确定性规则

遗传算法采用概率作为一种工具来引导其搜索过程朝着搜索空间的更优化的解移动，因此具有明确的搜索方向。

上述特点，表明遗传算法适于解决维数很高，总体很大的复杂的非线性问题。这使遗传算法具有以下优点：

(1) 应用广泛性：易于写出通用算法，求解不同优化问题；

(2) 非线性性：其他多数算法都需与可导、线性、凸性等性质相联系，遗传算法只需适应度函数值非负，适合具有高度非线性问题的寻优；

(3) 易于修改性：遗传算法只需少量改变算法，即可适用于不同问题； (4) 易于并行实现。

4.1.3 遗传算法的基本流程图和主要步骤

标准遗传算法(SGA)的基本流程[7]如图4.1所示：

开始产生初始种群计算适应度值是否满足优化原则否选择是输出最佳个体结束交叉变异 图4.1 遗传算法的流程图

24

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

算法主要步骤如下：

第1步：设置运行参数：群体大小N、终止进化代数T、交叉概率Pc、变异概率Pm；

第2步：随机产生初始群体；

第3步：计算个体的适应度，并判断是否符合优化准则。若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3步；

第4步：依据适应度选择个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；

第5步：按照一定的交叉概率和交叉方法，生成新的个体； 第6步：按照一定的变异概率和变异方法，生成新的个体； 第7步：由交叉和变异产生新一代的种群，返回到第3步。 4.1.4 遗传算法的基本操作

1、编码与解码

应用遗传算法解决问题的关键步骤就是编码。由问题空间向遗传算法空间的映射称为编码，由遗传算法空间向问题空间的映射称为解码[10]。由于遗传算法并不直接作用于待求变量本身，而是先将待求问题的变量进行编码，表示成适于遗传算法求解的码串形式，然后进行遗传操作，故相应地应该有解码过程，也就是将编码变回数字变量，从而找到所求问题的最优解。

编码的方法有很多，比如有二进制编码法和浮点数编码法。由于二进制数占用的位数较多，解码时延增加，故本文中采用浮点数编码。

2、种群初始化

在应用遗传算法之前，要对一定群体规模的个体进行初始化，这些经过初始化后的个体将作为遗传进化的祖先(下一代的父代)。作为祖先的初始群体，这些给定数量的个体是通过随机方法生成的，以保证搜索空间中的每个可能解在初始群体中都有相同的出现机会。

3、个体适应度的评价[5]

25

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

在遗传算法中评价值被称为个体适应度值，定义一个适应性函数是遗传算法中评价个体优劣的手段，评价的标准因所研究问题的不同而异，它通常由目标函数转化而来，并要求与目标函数有相同的极值点和可行解域，且值域非负，这样就可以将目标函数的极小值问题，转化为求适应函数的极大值问题，便于遗传操作。本文将目标函数的倒数作为适应度函数[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

本文来源：https://www.bwwdw.com/article/8ul7.html