基于自適應遺傳的E-CID定位算法研究

蔡衛(wèi)紅，朱永平

（湖南郵電職業(yè)技術(shù)學院，湖南長沙410015）

基于自適應遺傳的E-CID定位算法研究

蔡衛(wèi)紅，朱永平

（湖南郵電職業(yè)技術(shù)學院，湖南長沙410015）

針對LTE系統(tǒng)NLOS（非視距）環(huán)境下基于傳統(tǒng)遺傳的E-CID（增強小區(qū)識別）定位算法過早收斂于某局部最優(yōu)解而非全局最優(yōu),文章提出了一種改進的自適應遺傳E-CID定位算法，該算法通過對LTE終端位置數(shù)據(jù)進行加權(quán)最小二乘估算,利用遺傳算法進行非線性最優(yōu)解全局搜索,自適應的改變交叉及變異概率，避免了傳統(tǒng)遺傳算法過早收斂于局部最優(yōu)解缺點。仿真結(jié)果表明：自適應遺傳法比傳統(tǒng)遺傳算法優(yōu)勢更明顯,定位精度更準確。

LTE；NLOS；自適應遺傳；E-CID；定位

隨著LTE用戶對移動定位業(yè)務需求的快速發(fā)展及LTE移動系統(tǒng)數(shù)據(jù)處理能力的增強，基于用戶所處位置的定位服務已成為當前最具發(fā)展?jié)摿Φ囊苿踊ヂ?lián)網(wǎng)業(yè)務之一。無線通信和終端定位兩大系統(tǒng)正相互融合、相互促進。

1 移動終端定位技術(shù)概述

通過檢測移動終端與某移動通信系統(tǒng)中的一個或多個固定位置的收發(fā)信機(如衛(wèi)星站、基站等)之間傳播信號參數(shù)的不同來預估移動終端的大概位置。移動終端定位技術(shù)大致可分為以下兩大類。

1.1 基于移動網(wǎng)絡的定位技術(shù)

基于移動網(wǎng)絡的定位技術(shù)即移動系統(tǒng)中一個或多個基站對移動終端信號進行聯(lián)合檢測,再將這些聯(lián)合檢測信息傳送給移動系統(tǒng)中的終端位置服務中心統(tǒng)一進行檢測信息的處理以便估算出終端大概位置的定位技術(shù)。基于移動網(wǎng)絡的定位技術(shù)又可分為：基于移動網(wǎng)絡小區(qū)Cell ID標識的定位技術(shù)、基于終端信號到達角的AOA定位技術(shù)、基于終端信號到達時間的TOA定位技術(shù)、基于終端信號到達時間差的TDOA定位技術(shù)以及以上兩種或兩種以上定位技術(shù)綜合運用的混合定位技術(shù)。

1.2 基于移動終端的定位技術(shù)

基于移動終端的定位技術(shù)即移動終端通過主動檢測衛(wèi)星定位信號等來預估自己位置的定位技術(shù)?；谝苿咏K端的定位技術(shù)可分為:基于GPS輔助A-GPS定位技術(shù)、基于增強觀測時間差E-OTD定位技術(shù)。

在2G/3G移動系統(tǒng)中，移動終端定位業(yè)務主要通過控制平面來實現(xiàn)，通過控制信道來傳遞定位信息，即定位主要是指通過控制信令來進行定位相關(guān)信息的傳輸。在LTE移動系統(tǒng)中，移動終端定位業(yè)務既可通過控制面來實現(xiàn)，也可通過用戶面來實現(xiàn)。因此，LTE移動系統(tǒng)終端定位信息可通過用戶面的SUPL協(xié)議進行傳輸,從而節(jié)省了對LTE系統(tǒng)控制信令資源的占用。

2 LTE移動終端定位系統(tǒng)結(jié)構(gòu)及定位技術(shù)

2.1 LTE移動終端定位系統(tǒng)結(jié)構(gòu)

LTE移動系統(tǒng)終端定位系統(tǒng)結(jié)構(gòu)如圖1所示。

圖1 LTE移動系統(tǒng)終端定位系統(tǒng)結(jié)構(gòu)圖

LTE系統(tǒng)移動終端定位系統(tǒng)中與定位相關(guān)的網(wǎng)元實體包括:

1）E-SMLC：演進的服務移動位置中心

2）GMLC：網(wǎng)關(guān)移動位置中心

3）LRF：位置獲取功能實體

4）RDF：路由功能實體

5）PPR：私密信息存儲器

6）MME：移動性管理實體

7）SLP：SUPL定位業(yè)務平臺

2.2 LTE移動終端定位系統(tǒng)技術(shù)

3GPP LTE Release9協(xié)議規(guī)定的3種手機定位技術(shù)分別為：ECID（增強型小區(qū)標識定位技術(shù)）、A-GNSS（輔助全球?qū)Ш叫l(wèi)星系統(tǒng)定位技術(shù)）和OTDOA（到達時間觀測差定位技術(shù)）。以上3種LTE終端定位技術(shù)方法及分類如表1所示。

表1 3GPP LTE協(xié)議終端定位方法及分類表

3 LTE系統(tǒng)E-CID定位技術(shù)

3.1 E-CID定位技術(shù)原理

由于基于Cell ID的終端定位精度與小區(qū)的覆蓋半徑有很大關(guān)系,因而其定位誤差通常較大。其改進的LTE系統(tǒng)E-CID終端定位技術(shù)由于在原有技術(shù)上增加考慮對應終端定時提前量及終端信號到達角參數(shù),因而其定位精度更高。E-CID終端定位技術(shù)的原理如圖2所示。

圖2中eNode B通過智能天線測量到LTE終端上行信號的來波方向cp以及通過終端對應定時提前量計算出的終端與eNode B之間的的距離d,從而確定了終端位置。

圖2 E-CID終端定位原理圖

3.2 E-CID定位技術(shù)流程

基于E-CID技術(shù)的LTE終端定位基本流程為:獲取LTE終端的測量能力,定位服務器網(wǎng)元確定本次LTE終端定位所需的測量量,eNode B網(wǎng)元啟動定位終端相關(guān)數(shù)據(jù)測量,eNode B網(wǎng)元向定位服務器網(wǎng)元上報測量結(jié)果和位置信息,定位服務器網(wǎng)元進行位置計算?；贓-CID定位技術(shù)的TATypel定位流程如圖3所示。

圖3 基于E- CID技術(shù)的TA Typel定位流程圖

其主要步驟如下：

1）LTE移動終端或定位客戶端向MME網(wǎng)元發(fā)起定位請求,以期獲得LTE終端的位置信息。

2）MME網(wǎng)元向E-SMLC網(wǎng)元發(fā)起定位請求。

3）E-SMLC網(wǎng)元通過LPP協(xié)議查詢LTE終端的定位能力，LTE終端向E-SMLC網(wǎng)元上報自己的定位能力信息。

4）E-SMLC網(wǎng)元通過LPPa協(xié)議請求eNode B網(wǎng)元上報對應LTE終端相關(guān)測量數(shù)據(jù)及服務小區(qū)信息, eNode B網(wǎng)元向E-SMLC網(wǎng)元響應該請求。

5）在E-SMLC網(wǎng)元的請求下,eNode B網(wǎng)元觸發(fā)對應LTE終端的TA Typel和AOA測量,從而確定其接收信號定時偏差及來波方向。

6）eNode B網(wǎng)元通過LPPa協(xié)議向E-SMLC網(wǎng)元上傳對應LTE終端測量數(shù)據(jù)信息。

7）E-SMLC網(wǎng)元根據(jù)對應LTE終端的測量結(jié)果以及其它相關(guān)信息,從而計算出LTE終端的位置。

8）E-SMLC網(wǎng)元將LTE終端的位置定位結(jié)果發(fā)送給MME網(wǎng)元。

9）MME網(wǎng)元將LTE終端的定位結(jié)果發(fā)送給LTE終端或定位服務器,到此定位過程完成。

4 NLOS環(huán)境下基于自適應遺傳算法的E-CID定位算法

由于常規(guī)E-CID定位算法在NLOS環(huán)境下受獲得LTE終端的信號到達時間(TOA)和信號到達角(AOA)影響存在一定的誤差,故這里提出一種NLOS環(huán)境下改進的E-CID定位算法即自適應遺傳E-CID定位算法。

4.1 遺傳算法基本原理

遺傳算法最先由John Holland本人提出,通過不斷改進,己成為當前解決多目標、非線性復雜問題常用算法。遺傳算法基本步驟如下:

1）編碼：將待搜索的空間數(shù)據(jù)表示成遺傳算法空間的基因型串結(jié)構(gòu)數(shù)據(jù)的轉(zhuǎn)換就稱為編碼。

2）產(chǎn)生初始群體：隨機產(chǎn)生的n個初始串結(jié)構(gòu)數(shù)據(jù)所構(gòu)成的一個群體。遺傳算法將會以這n個串結(jié)構(gòu)數(shù)據(jù)作為初始點開始迭代。

3）個體適應性評估檢測：先算出個體對環(huán)境的適應情況,再通過選取合適的適應度函數(shù)來對個體的性能進行優(yōu)劣性評估。

4）選擇：即從當前群體中選出優(yōu)良的個體來作為父代為下一代繁殖子孫。

5）交換：由父輩的兩個個體分別提供一組染色體來產(chǎn)生新個體,交換操作如圖4所示。

圖4 交換操作圖

6）變異：通過在群體中隨機選擇某個個體，對此個體以一定概率隨機地改變其串結(jié)構(gòu)數(shù)據(jù)中某個串的值，從而產(chǎn)生新的個體時。通常遺傳算法中發(fā)生變異的的典型值為0.001～0.01。變異操作如圖5所示。

圖5 變異操作圖

7）將生成的新的子代數(shù)據(jù)再次代入回適應度函數(shù)并計算出該子代個體的適應度值,依此輪回直到達到預先規(guī)劃好的遺傳算法進化代數(shù)后停止。

4.2 基于自適應遺傳算法的E-CID定位算法

自適應遺傳算法基本策略是在目標區(qū)域內(nèi)搜尋滿足移動終端位置誤差最小的最優(yōu)解,并根據(jù)個體的適應度自適應地調(diào)整交換和變異概率,從而提高算法的全局搜索能力,減小NLOS環(huán)境對定位誤差的影響。4.2.1染色體編碼與解碼

遺傳算法通過對群體中各個體位置采用定長二進制編碼,假設(shè)LTE終端在以eNode B為圓心,半徑為R的圓外接正方形區(qū)域，通過對其進行編碼分析,則LTE終端x(橫坐標)和y(縱坐標)的取值范圍為[-R,R],假設(shè)對x和y都用k位長度的二進制編碼來表示,應有2k種不同編碼值,所以相鄰兩碼字所表示參數(shù)的位置距離為:

所以,如果某LTE終端所處位置的橫坐標（或縱坐標）的編碼為bkbk-1bk-2…b2b1,則對應的橫坐標（或縱坐標）值為：

這樣每個個體的橫坐標及縱坐標編碼合并為一個2k位的碼字（前k位為個體橫坐標編碼,后k位為個體縱坐標編碼）。

4.2.2 適應度函數(shù)選取方法

適應度函數(shù)的選取應依據(jù)定位誤差來確定,定位誤差小的個體其對應的適應度函數(shù)有較高值。反之，定位誤差大的個體其對應的適應度函數(shù)有較低值。當LTE基站坐標為(0,0),當僅知LTE終端TOA及AOA值的情況下,可計算其對應的加權(quán)殘差值為:

為使LTE終端位置的加權(quán)二乘估計最小，應使以下f(x,y)值最小,即選F(x,y)的倒數(shù)為適應度函數(shù)，即:

因此，先對LTE個體位置編碼進行解碼可得LTE個體坐標(x,y),如果個體的坐標(x,y)能使得F(x,y)越小，即其適應度函數(shù)值越大，則計算出來的終端位置與實際位置越接近。

4.2.3 選擇操作方法

選擇操作采用輪盤賭選擇法,即任一個體其適應度值與所有個體總適應度值比例類似輪盤中對應單個扇形區(qū)域面積與圓盤總面積的比例。輪盤賭選擇法中圓盤被隨機撥動停止后其指針最大概率所指位置為面積最大區(qū)域,類似對應個體位置數(shù)據(jù)也最容易被選中。假如個體1其適應度值最大,則其被隨機選中的機率最大,而其它個體適應度低的個體被選中的機率都要小。第m個個體位置數(shù)據(jù)被選中的機率是:

其它個體的選擇相同，依此重復,直到所有個體被選中。

4.2.4 交叉操作方法

交叉操作方法具體過程如下:

1）從種群中隨意選擇個體來兩兩配對。

2）對每一個體組,隨機選定基因串某比特位后為交叉位置點。

3）對每一選定交叉點的個體組,按交叉機率交換它們等比特位的基因序列值,從而產(chǎn)生兩個新個體。

4.2.5 變異操作方法

變異操作即對個體編碼串中的基因以變異概率做變異運算,其過程如下:

1）對個體基因序列以變異概率來確定其是否為變異點。

2）對需進行變異基因位進行取反操作運算來產(chǎn)生新的個體。

4.2.6 自適應遺傳算法

傳統(tǒng)遺傳算法,通過選擇操作、交叉操作、變異操作后其解結(jié)果將非常接近高適應度值時可能停止進化,但可能該值并非全局最優(yōu)解,即傳統(tǒng)遺傳算法有過早收斂局部最優(yōu)解缺點。

所以M.Srinivas提出了一種改進遺傳算法即自適應遺傳算法,該算法可使交叉概率與變異概率能隨種群變化而變化。

在新的遺傳算法中,交叉與變異概率分別按以下公式進行自適應調(diào)整:

以上公式中，fmax表示群體最大適應度值，favg表示每代群體平均適應度值，f表示需交叉兩個體中適應度值較大者，f'表示需變異個體的適應度值。k1、k2、k3、k4的變化范圍都在(0,1)區(qū)間。

從Pc和Pm兩表達式可以看出，當某個體適應度值小于個體平均適應度值時，說明其個體性能并不太好，本個體需用較大交叉和變異概率才使其有較大可能產(chǎn)生變化；反之，如果某個體適應度值大于個體平均適應度值，說明其個體性能非常優(yōu)良，本個體只需選取較小的交叉和變異概率就可保證其個體性能。一般Pc取值范圍為0.5～1.0，Pm取值范圍為0.001～0.05，同時使k1、k3兩個都取較小值，k2、k4兩個都取較大值。

4.3 仿真結(jié)果與分析

為了驗證基于E-CID的LTE自適應遺傳算法定位性能,通過MATLAB仿真對比自適應遺傳算法與傳統(tǒng)遺傳算法定位性能差異,仿真條件如表2所示:

表2 仿真條件表

分別選擇鬧市區(qū)、—般市區(qū)、郊區(qū)三種不同區(qū)域環(huán)境，對比三種NLOS環(huán)境下基于自適應遺傳與傳統(tǒng)遺傳兩種E-CID定位算法的定位精度仿真情況，其對比情況如圖6—圖8所示。

圖6 鬧市區(qū)NLOS環(huán)境兩種算法對RMSE(均方根誤差)影響圖

圖7 —般市區(qū)NLOS環(huán)境兩種算法對RMSE(均方根誤差)影響圖

圖8 郊區(qū)NLOS環(huán)境兩種算法對RMSE(均方根誤差)影響圖

從圖6—圖8可看出,隨著仿真環(huán)境由鬧市區(qū)→—般市區(qū)→郊區(qū),因NLOS誤差逐漸減小,故兩種算法的定位精度都逐漸提升,而且相同區(qū)域自適應遺傳算法的定位精度都要高于傳統(tǒng)遺傳算法。

自適應遺傳算法的定位精度高于傳統(tǒng)遺傳算法的原因：傳統(tǒng)遺傳算法雖然能收斂某局部最優(yōu)解但不是全局最優(yōu),而自適應遺傳算法能根據(jù)個體的適應度值差異來動態(tài)的改變交叉與變異的概率,故其種群能進化到全局最優(yōu)解。

5 總結(jié)

文章提出的基于NLOS環(huán)境的自適應遺傳E-CID定位算法,該算法比傳統(tǒng)遺傳算法優(yōu)勢明顯,定位精度更準確。

[1]閻龍，高澤華，高峰.一種適用于NLOS環(huán)境的LTE終端迭代定位算法[J].計算機應用研究，2014(3)：876-878.

[2]王忠，周旋，王會，游智勝.一種改進的NLOS消除算法[J].電子測量技術(shù)，2007(12)：29-31，36.

[3]閻龍.LTE終端定位研究[D].北京：北京郵電大學，2014.

[4]李學斌.第四代移動通信系統(tǒng)終端定位技術(shù)簡述[J].電腦與電信，2015(8)：51-53.

[5]姜杰,魏民.LTE網(wǎng)絡下定位實現(xiàn)方案研究[J].互聯(lián)網(wǎng)天地，2015(10)：24-27.

[6]武曉琳，單志龍，曹樹林，曹楚裙.基于接收信號強度指示測距的蒙特卡羅盒移動節(jié)點定位算法[J].計算機應用，2015 (4)：916-920.

[7]許艷英，包宋建.NLOS環(huán)境下移動臺位置與速率估計[J].電訊技術(shù)，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

蔡衛(wèi)紅（1971-），男，湖南益陽人，湖南郵電職業(yè)技術(shù)學院教授，高級實驗師，研究方向：移動終端、移動通信系統(tǒng)。