基于量子遺傳算法的TDOA定位技術研究＊

王 迅 吳 濤

（91404部隊93分隊 秦皇島 066001）

1 引言

隨著移動通信技術的飛速發展，利用蜂窩網絡對移動臺進行定位將逐漸成為蜂窩網絡的一項重要功能。近年來無線通信基本的定位技術包括場強定位法、基于電波傳播時間（TOA）或時間差（TDOA）的定位法、來波角度定位法（AOA）以及各類混合定位法。其中，TDOA定位法通過電波從移動臺（MS）傳播到多個基站（BS）的傳播時間差來確定移動臺的位置，該方法由于對設備改動少并且不需要移動臺基站間進行嚴格的同步，因而是一種理想的定位方法。

對于TDOA方式，若多個接收機位于一條直線上，有許多優化處理方法。但如果接收機在空間隨機分布，在求解雙曲線方程組時會遇到非線性問題。文獻［3］給出了采用傅里葉級數的迭代算法，這種迭代需要一個較好的初始值，否則容易落入局部最小點，而且不保證收斂；文獻［4］提出了一種兩步加權LS方法，在誤差很小的情況下，性能逼近最優值，但是這種方法由于引入了測量參數的平方項，當測量誤差較大時，噪聲的二次項不可忽視；文獻［5］采用遺傳算法解極大似然函數，通過合理設置種群規模以及變異率，能找到逼近全局最優點的解相對于其它算法精度高，但由于計算量大，實時實現很困難。

本文提出一種結合Chan算法和量子遺傳算法的TDOA定位算法，該算法首先根據移動臺所在的服務區扇區來確定移動臺坐標范圍，然后采用似然函數的倒數作為目標，通過迭代，在確定的坐標范圍內進行搜索。仿真結果說明，通過合理設置量子旋轉門，能得到較高精度的解。

2 TDOA 雙曲線數學模型［1，3～5］

圖1 二維平面示意圖

如圖1所示，假設M個接收機分布在二維平面上，（x，y）為移動臺的待估位置，（xi，yi）為第i個基站的已知位置。移動臺到基站i的距離為Ri，令R0i，1表示移動臺與基站i（i≠1）和基站1（服務基站）的實際距離差，測量值記作為Ri，1，則

式中：c為電波傳播速度；di，1是 TDOA 測量值；ni，1是測量TDOA時引入的噪聲，為方便起見，可認為是獨立同分布的方差為σ2的高斯白噪聲。

又因為

所以有

可得

文中考慮M＞3時的情況，采用最大似然法估計源點坐標（x，y）。因為Ri，1服從均值為（Ri－R1），方差為σ2的高斯分布，因各測量值獨立，則似然函數為

求使似然函數最大的坐標值，相當于求

該方程式非線性函數，用解析法求解時比較困難。針對此情況，文中應用量子遺傳算法來求解，采用似然函數的倒數作為個體適應度來選取優良個體，確定量子旋轉門，用二進制數對個體進行編碼，然后在確定的坐標范圍內搜索移動臺的位置。

3 量子遺傳算法［8～9，11］

量子遺傳算法（quantum genetic algorithm，QGA）是量子計算理論和遺傳算法原理相結合的產物。主要以量子理論和量子計算為基礎，采用量子比特實現染色體編碼，通過量子門對其進行更新，產生種群的多樣性。QGA具有種群規模小、尋優能力強、收斂速度快和計算時間短的特點。

3.1 量子比特編碼

在量子信息論中，信息的載體不再是經典的比特，而是量子比特或量子位。量子比特可以處于0和1這兩個基態的任意疊加狀態。一個量子計算比特可以表示為：

其中，α和β是兩個復數，分別表示狀態｜0〉和狀態｜1〉的概率幅。｜α｜2和｜β｜2分別表示量子比特處于｜0〉和｜1〉的概率。

一個m位量子比特的編碼形式如下：

其中，｜α｜2＋｜β｜2＝1，一個m位量子比特編碼可表示2m個不同的狀態。

3.2 量子旋轉門

量子旋轉門是演化操作的執行機構，其調整操作如下式：

其中，（αi／βi）為種群個體第i個量子位，（α′i／β′i）為更新后的形式，θ為量子門的旋轉角，θ＝Δθ·s（αi，βi），Δθ調整的步長值影響收斂速度，如果太大，算法易出現早熟現象而陷入局部最優解；如果太小，可能出現停滯狀態，因此，需要自適應調整搜索。本文Δθ取10e－t／maxt，t為進化代數，maxt為最大進化代數，s（αi，βi）是搜索方向函數，主要使算法向最優解的方向進行搜索，s（αi，βi）的取值如表1所示。

表1 函數s（α，β）的查詢表

4 基于Chan-QGA的TDOA定位技術

用于定位的量子遺傳算法流程簡述如下：

1）根據Chan算法搜索到一個局部最優解（xa，ya），蜂窩的半徑為r，確定量子遺傳算法的搜索區間為［xa－C，xa＋C］和［ya－C，ya＋C］。在文中C＝r／4，若搜索區間超過蜂窩半徑區間［0，r］，需做鉗位處理。

2）根據給定的定位精度要求進行二進制編碼產生初始種群，Chan算法搜索到的一個局部最優解（xa，ya）作為算法初始種群的一個個體，其他個體隨機產生。

3）把似然函數的倒數作為當代種群適應度來計算，對種群的適應度進行評價，找出最優的個體保存起來。

4）用量子旋轉門對種群進行更新。

5）判斷算法迭代終止條件是否滿足，如果滿足，執行6）；否則，轉向3）。

6）輸出最優個體，Chan-QGA算法運行結束。

5 實驗仿真及結果比較

圖2 接收機與目標位置示意圖

表2中的Chan欄是Chan算法［1］的仿真結果；GA欄是文獻［2］中改進算法的仿真結果；第一欄10lg（cσ）是根據蜂窩網通信系統與系統熱噪聲等因素確定的，評價指標為平均估計坐標MV，即E［（x，y）］；均方誤差MSE＝E［（x－x0）2＋（y－y0）2］，仿真所得MV如表2所示，MSE如圖3所示

表2 Chan算法、GA算法及Chan-QGA算法

圖3 Chan、GA、Chan-QGA的性能比較曲線

從圖中可以看出，在噪聲方差很小時，Chan-QGA與Chan、GA性能相近，但GA算法容易陷入局部收斂，而當噪聲方差大時，GA、Chan-QGA的性能比Chan好，主要原因是Chan算法對噪聲二次項的忽略導致的。另外還可以看出Chan-QGA算法性能好于GA算法，因為Chan-QGA算法引入了Chan算法的最優解，加快收斂速度。

6 結語

本文提出的Chan-QGA算法在仿真中表現穩定，定位精度高，特別在噪聲較大的情況下，與Chan、GA算法相比，具有更高的穩定性、搜索速度和定位精度，對一些高精度的定位技術的研究有一定的應用價值。

［1］CHAN Y T，HO K C.A simple and efficient estimator for hyperbolic location［J］.IEEE Trans on Singal Processing，1994，42（8）：1905～1915

［2］李麗春，冉崇森，魏峰.利用改進遺傳算法解決TDOA定位估計中的非線性優化問題［J］.系統工程與電子技術，2003，25（8）：971～973

［3］范平志，鄧平，劉林.蜂窩網無線定位［M］.北京：電子工業出版社，2002

［4］FANG B T.Simple solutions for hyperbolic and related position fixes［J］.IEEE Trans Aerosp Eletron Syst，1990，26：748～753

［5］SMITH J O，ABEL J S.Closed-form least-spuarens source location estimation from range2difference measurements［J］.IEEE Trans Acoust Speech，Singnal Processing，1987：ASSP-35：1661～1669

［6］叢琳，沙宇恒，焦李成.基于免疫克隆選擇算法的圖像分割［J］.電子與信息學報，2006，28（7）：1169～1173

［7］孫勝，李輝，韓崇昭，等.基于TDOA定位技術的仿真研究［J］.無線通信技術，2002，11（4）

［8］吳濤，葉曉慧，王紅霞，等.基于量子遺傳算法測試選擇問題的研究［J］.計算機測量與控制，2010，18（11）

［9］趙知勁，彭振，鄭仕鏈，等.基于量子遺傳算法的認知無線電頻譜分配［J］.物理學報，2009（2）：1358～1359

［10］劉信新，陳鯤.基于RSSI與TDOA的混合測距加權定位算法［J］.計算機與數字工程，2011，39（4）

［11］羅紅明，王家映，朱培民，等.量子遺傳算法在大地電磁反演中的應用［J］.地球物理學報，2009（1）：261～263