蔡卫红，朱永平

（湖南邮电职业技术学院，湖南长沙410015）

基于自适应遗传的E-CID定位算法研究

蔡卫红，朱永平

（湖南邮电职业技术学院，湖南长沙410015）

针对LTE系统NLOS（非视距）环境下基于传统遗传的E-CID（增强小区识别）定位算法过早收敛于某局部最优解而非全局最优,文章提出了一种改进的自适应遗传E-CID定位算法，该算法通过对LTE终端位置数据进行加权最小二乘估算,利用遗传算法进行非线性最优解全局搜索,自适应的改变交叉及变异概率，避免了传统遗传算法过早收敛于局部最优解缺点。仿真结果表明：自适应遗传法比传统遗传算法优势更明显,定位精度更准确。

LTE；NLOS；自适应遗传；E-CID；定位

随着LTE用户对移动定位业务需求的快速发展及LTE移动系统数据处理能力的增强，基于用户所处位置的定位服务已成为当前最具发展潜力的移动互联网业务之一。无线通信和终端定位两大系统正相互融合、相互促进。

1 移动终端定位技术概述

通过检测移动终端与某移动通信系统中的一个或多个固定位置的收发信机(如卫星站、基站等)之间传播信号参数的不同来预估移动终端的大概位置。移动终端定位技术大致可分为以下两大类。

1.1 基于移动网络的定位技术

基于移动网络的定位技术即移动系统中一个或多个基站对移动终端信号进行联合检测,再将这些联合检测信息传送给移动系统中的终端位置服务中心统一进行检测信息的处理以便估算出终端大概位置的定位技术。基于移动网络的定位技术又可分为：基于移动网络小区Cell ID标识的定位技术、基于终端信号到达角的AOA定位技术、基于终端信号到达时间的TOA定位技术、基于终端信号到达时间差的TDOA定位技术以及以上两种或两种以上定位技术综合运用的混合定位技术。

1.2 基于移动终端的定位技术

基于移动终端的定位技术即移动终端通过主动检测卫星定位信号等来预估自己位置的定位技术。基于移动终端的定位技术可分为:基于GPS辅助A-GPS定位技术、基于增强观测时间差E-OTD定位技术。

在2G/3G移动系统中，移动终端定位业务主要通过控制平面来实现，通过控制信道来传递定位信息，即定位主要是指通过控制信令来进行定位相关信息的传输。在LTE移动系统中，移动终端定位业务既可通过控制面来实现，也可通过用户面来实现。因此，LTE移动系统终端定位信息可通过用户面的SUPL协议进行传输,从而节省了对LTE系统控制信令资源的占用。

2 LTE移动终端定位系统结构及定位技术

2.1 LTE移动终端定位系统结构

LTE移动系统终端定位系统结构如图1所示。

图1 LTE移动系统终端定位系统结构图

LTE系统移动终端定位系统中与定位相关的网元实体包括:

1）E-SMLC：演进的服务移动位置中心

2）GMLC：网关移动位置中心

3）LRF：位置获取功能实体

4）RDF：路由功能实体

5）PPR：私密信息存储器

6）MME：移动性管理实体

7）SLP：SUPL定位业务平台

2.2 LTE移动终端定位系统技术

3GPP LTE Release9协议规定的3种手机定位技术分别为：ECID（增强型小区标识定位技术）、A-GNSS（辅助全球导航卫星系统定位技术）和OTDOA（到达时间观测差定位技术）。以上3种LTE终端定位技术方法及分类如表1所示。

表1 3GPP LTE协议终端定位方法及分类表

3 LTE系统E-CID定位技术

3.1 E-CID定位技术原理

由于基于Cell ID的终端定位精度与小区的覆盖半径有很大关系,因而其定位误差通常较大。其改进的LTE系统E-CID终端定位技术由于在原有技术上增加考虑对应终端定时提前量及终端信号到达角参数,因而其定位精度更高。E-CID终端定位技术的原理如图2所示。

图2中eNode B通过智能天线测量到LTE终端上行信号的来波方向cp以及通过终端对应定时提前量计算出的终端与eNode B之间的的距离d,从而确定了终端位置。

图2 E-CID终端定位原理图

3.2 E-CID定位技术流程

基于E-CID技术的LTE终端定位基本流程为:获取LTE终端的测量能力,定位服务器网元确定本次LTE终端定位所需的测量量,eNode B网元启动定位终端相关数据测量,eNode B网元向定位服务器网元上报测量结果和位置信息,定位服务器网元进行位置计算。基于E-CID定位技术的TATypel定位流程如图3所示。

图3 基于E- CID技术的TA Typel定位流程图

其主要步骤如下：

1）LTE移动终端或定位客户端向MME网元发起定位请求,以期获得LTE终端的位置信息。

2）MME网元向E-SMLC网元发起定位请求。

3）E-SMLC网元通过LPP协议查询LTE终端的定位能力，LTE终端向E-SMLC网元上报自己的定位能力信息。

4）E-SMLC网元通过LPPa协议请求eNode B网元上报对应LTE终端相关测量数据及服务小区信息, eNode B网元向E-SMLC网元响应该请求。

5）在E-SMLC网元的请求下,eNode B网元触发对应LTE终端的TA Typel和AOA测量,从而确定其接收信号定时偏差及来波方向。

6）eNode B网元通过LPPa协议向E-SMLC网元上传对应LTE终端测量数据信息。

7）E-SMLC网元根据对应LTE终端的测量结果以及其它相关信息,从而计算出LTE终端的位置。

8）E-SMLC网元将LTE终端的位置定位结果发送给MME网元。

9）MME网元将LTE终端的定位结果发送给LTE终端或定位服务器,到此定位过程完成。

4 NLOS环境下基于自适应遗传算法的E-CID定位算法

由于常规E-CID定位算法在NLOS环境下受获得LTE终端的信号到达时间(TOA)和信号到达角(AOA)影响存在一定的误差,故这里提出一种NLOS环境下改进的E-CID定位算法即自适应遗传E-CID定位算法。

4.1 遗传算法基本原理

遗传算法最先由John Holland本人提出,通过不断改进,己成为当前解决多目标、非线性复杂问题常用算法。遗传算法基本步骤如下:

1）编码：将待搜索的空间数据表示成遗传算法空间的基因型串结构数据的转换就称为编码。

2）产生初始群体：随机产生的n个初始串结构数据所构成的一个群体。遗传算法将会以这n个串结构数据作为初始点开始迭代。

3）个体适应性评估检测：先算出个体对环境的适应情况,再通过选取合适的适应度函数来对个体的性能进行优劣性评估。

4）选择：即从当前群体中选出优良的个体来作为父代为下一代繁殖子孙。

5）交换：由父辈的两个个体分别提供一组染色体来产生新个体,交换操作如图4所示。

图4 交换操作图

6）变异：通过在群体中随机选择某个个体，对此个体以一定概率随机地改变其串结构数据中某个串的值，从而产生新的个体时。通常遗传算法中发生变异的的典型值为0.001～0.01。变异操作如图5所示。

图5 变异操作图

7）将生成的新的子代数据再次代入回适应度函数并计算出该子代个体的适应度值,依此轮回直到达到预先规划好的遗传算法进化代数后停止。

4.2 基于自适应遗传算法的E-CID定位算法

自适应遗传算法基本策略是在目标区域内搜寻满足移动终端位置误差最小的最优解,并根据个体的适应度自适应地调整交换和变异概率,从而提高算法的全局搜索能力,减小NLOS环境对定位误差的影响。4.2.1染色体编码与解码

遗传算法通过对群体中各个体位置采用定长二进制编码,假设LTE终端在以eNode B为圆心,半径为R的圆外接正方形区域，通过对其进行编码分析,则LTE终端x(横坐标)和y(纵坐标)的取值范围为[-R,R],假设对x和y都用k位长度的二进制编码来表示,应有2k种不同编码值,所以相邻两码字所表示参数的位置距离为:

所以,如果某LTE终端所处位置的横坐标（或纵坐标）的编码为bkbk-1bk-2…b2b1,则对应的横坐标（或纵坐标）值为：

这样每个个体的横坐标及纵坐标编码合并为一个2k位的码字（前k位为个体横坐标编码,后k位为个体纵坐标编码）。

4.2.2 适应度函数选取方法

适应度函数的选取应依据定位误差来确定,定位误差小的个体其对应的适应度函数有较高值。反之，定位误差大的个体其对应的适应度函数有较低值。当LTE基站坐标为(0,0),当仅知LTE终端TOA及AOA值的情况下,可计算其对应的加权残差值为:

为使LTE终端位置的加权二乘估计最小，应使以下f(x,y)值最小,即选F(x,y)的倒数为适应度函数，即:

因此，先对LTE个体位置编码进行解码可得LTE个体坐标(x,y),如果个体的坐标(x,y)能使得F(x,y)越小，即其适应度函数值越大，则计算出来的终端位置与实际位置越接近。

4.2.3 选择操作方法

选择操作采用轮盘赌选择法,即任一个体其适应度值与所有个体总适应度值比例类似轮盘中对应单个扇形区域面积与圆盘总面积的比例。轮盘赌选择法中圆盘被随机拨动停止后其指针最大概率所指位置为面积最大区域,类似对应个体位置数据也最容易被选中。假如个体1其适应度值最大,则其被随机选中的机率最大,而其它个体适应度低的个体被选中的机率都要小。第m个个体位置数据被选中的机率是:

其它个体的选择相同，依此重复,直到所有个体被选中。

4.2.4 交叉操作方法

交叉操作方法具体过程如下:

1）从种群中随意选择个体来两两配对。

2）对每一个体组,随机选定基因串某比特位后为交叉位置点。

3）对每一选定交叉点的个体组,按交叉机率交换它们等比特位的基因序列值,从而产生两个新个体。

4.2.5 变异操作方法

变异操作即对个体编码串中的基因以变异概率做变异运算,其过程如下:

1）对个体基因序列以变异概率来确定其是否为变异点。

2）对需进行变异基因位进行取反操作运算来产生新的个体。

4.2.6 自适应遗传算法

传统遗传算法,通过选择操作、交叉操作、变异操作后其解结果将非常接近高适应度值时可能停止进化,但可能该值并非全局最优解,即传统遗传算法有过早收敛局部最优解缺点。

所以M.Srinivas提出了一种改进遗传算法即自适应遗传算法,该算法可使交叉概率与变异概率能随种群变化而变化。

在新的遗传算法中,交叉与变异概率分别按以下公式进行自适应调整:

以上公式中，fmax表示群体最大适应度值，favg表示每代群体平均适应度值，f表示需交叉两个体中适应度值较大者，f'表示需变异个体的适应度值。k1、k2、k3、k4的变化范围都在(0,1)区间。

从Pc和Pm两表达式可以看出，当某个体适应度值小于个体平均适应度值时，说明其个体性能并不太好，本个体需用较大交叉和变异概率才使其有较大可能产生变化；反之，如果某个体适应度值大于个体平均适应度值，说明其个体性能非常优良，本个体只需选取较小的交叉和变异概率就可保证其个体性能。一般Pc取值范围为0.5～1.0，Pm取值范围为0.001～0.05，同时使k1、k3两个都取较小值，k2、k4两个都取较大值。

4.3 仿真结果与分析

为了验证基于E-CID的LTE自适应遗传算法定位性能,通过MATLAB仿真对比自适应遗传算法与传统遗传算法定位性能差异,仿真条件如表2所示:

表2 仿真条件表

分别选择闹市区、—般市区、郊区三种不同区域环境，对比三种NLOS环境下基于自适应遗传与传统遗传两种E-CID定位算法的定位精度仿真情况，其对比情况如图6—图8所示。

图6 闹市区NLOS环境两种算法对RMSE(均方根误差)影响图

图7 —般市区NLOS环境两种算法对RMSE(均方根误差)影响图

图8 郊区NLOS环境两种算法对RMSE(均方根误差)影响图

从图6—图8可看出,随着仿真环境由闹市区→—般市区→郊区,因NLOS误差逐渐减小,故两种算法的定位精度都逐渐提升,而且相同区域自适应遗传算法的定位精度都要高于传统遗传算法。

自适应遗传算法的定位精度高于传统遗传算法的原因：传统遗传算法虽然能收敛某局部最优解但不是全局最优,而自适应遗传算法能根据个体的适应度值差异来动态的改变交叉与变异的概率,故其种群能进化到全局最优解。

5 总结

文章提出的基于NLOS环境的自适应遗传E-CID定位算法,该算法比传统遗传算法优势明显,定位精度更准确。

[1]阎龙，高泽华，高峰.一种适用于NLOS环境的LTE终端迭代定位算法[J].计算机应用研究，2014(3)：876-878.

[2]王忠，周旋，王会，游智胜.一种改进的NLOS消除算法[J].电子测量技术，2007(12)：29-31，36.

[3]阎龙.LTE终端定位研究[D].北京：北京邮电大学，2014.

[4]李学斌.第四代移动通信系统终端定位技术简述[J].电脑与电信，2015(8)：51-53.

[5]姜杰,魏民.LTE网络下定位实现方案研究[J].互联网天地，2015(10)：24-27.

[6]武晓琳，单志龙，曹树林，曹楚裙.基于接收信号强度指示测距的蒙特卡罗盒移动节点定位算法[J].计算机应用，2015 (4)：916-920.

[7]许艳英，包宋建.NLOS环境下移动台位置与速率估计[J].电讯技术，2010(11)：53-57.

[8]解全颖.基于智能手机的移动定位算法研究[D].成都：电子科技大学，2013.

E-CID location algorithm based on adaptive genetic algorithm

CAI Wei-hong,ZHUYong-ping
(Hunan Post and Telecommunication College,Changsha,Hunan,China 410015)

In viewof the traditional genetic algorithm for E-CID localization algorithm based on the traditional genetic algorithm in NLOS environment,it converges to a local optimal solution rather than the global optimum.The paper proposes an improved adaptive genetic E-CID algorithm which uses weighted least squares estimation for LTE terminal location data,genetic algorithm for nonlinear global searching optimal solution,the change of the adaptive crossover and mutation probability.It avoids the premature convergence of traditional genetic algorithm in local optimal solution.The simulation results showthat the adaptive genetic algorithmis better re than the traditional genetic algorithmand is more accurate in positioning.

LTE;NLOS;adaptive genetic;E-CID;positioning

10.3969/j.issn.2095-7661.2016.04.001】

TN929.5

A

2095-7661（2016）04-0001-05

2016-08-03

蔡卫红（1971-），男，湖南益阳人，湖南邮电职业技术学院教授，高级实验师，研究方向：移动终端、移动通信系统。