??? 摘 要： 針對cdma2000-1X網(wǎng)絡中無線信號的特點和無源定位的需要，通過將N階多項式平滑擬合及加權(quán)修正的思想融合到遺傳算法" title="遺傳算法">遺傳算法中，提出了一種改進的遺傳算法來消除NLOS誤差和多徑" title="多徑">多徑傳播誤差對載干比的影響。不僅避免了遺傳算法“早熟”的發(fā)生，而且還可以根據(jù)實際情況靈活改變搜索精度，使算法搜索達到全局最優(yōu)，從而實現(xiàn)精確估計信號到達方位的目的。經(jīng)過場外試驗和MATLAB仿真驗證該算法可以達到比較好的效果。
??? 關(guān)鍵詞： 無源定位? 信號到達時延? 信號到達方位? 非視距誤差? 載干比

?

??? 由于美國聯(lián)邦通訊委員會在E-911標準中要求無線通信網(wǎng)絡必須能夠提供基于移動用戶的位置估計的功能，無線定位越來越受到各國公司及研究人員的關(guān)注^[1]。利用各種通信標準中現(xiàn)有的資源，在復雜的無線通信環(huán)境中提高定位的精度是當前研究的重點。在CDMA系統(tǒng)中為實現(xiàn)符合E-911精度要求的定位，有兩個問題必須解決：一是怎樣減小基站與用戶間的非視距NLOS（Non-Line-of Sight）誤差、多徑傳播誤差對定位精度" title="定位精度">定位精度的影響；二是由于CDMA蜂窩系統(tǒng)是一個功率控制系統(tǒng)，當用戶發(fā)射信號只能被一個基站接收時，怎樣實現(xiàn)用戶定位，并能使定位精度盡可能得到提高^[2-3]。在此情況下，TOA/AOA（Time of Arrival/Angle of Arrival）是最為有效的方法。該方法中，信號到達角的精確估計是實現(xiàn)高精度定位的必要條件。精確的信號到達角估計必須借助于基站通過通信網(wǎng)絡來實現(xiàn)。但在無源定位系統(tǒng)中，被定位對象和基站并不參與定位過程，信號到達角是根據(jù)定位設備自身所接收的信息來估計得到的。由于受天線分辨率等因素的影響，往往并不能從測量值中精確估計出信號到達角，而是獲得信號到達方位角的范圍，即信號到達方位OOA（Orientation of Arrival）。若在定位的后期處理部分加上適當?shù)膬?yōu)化算法也能實現(xiàn)精確定位。
??? 在天線分辨率確定的前提下，信號到達方位估計得越準確，最后的定位精度也就會越高。而NLOS誤差和多徑傳播誤差是信號到達方位準確估計的主要干擾因素。這些因素的存在不僅會使信號到達方位的判斷產(chǎn)生偏差，甚至會產(chǎn)生錯誤判斷，所以要提高定位精度就必須消除這些因素的影響。
??? 遺傳算法是近年來智能算法領(lǐng)域提出的解決工程優(yōu)化問題的一種有效方法，可以用來消除NLOS誤差和多徑傳播誤差。但傳統(tǒng)的遺傳算法并不能有效地消除這些誤差的影響，需要對傳統(tǒng)的遺傳算法進行改進，以便達到比較理想的效果。
??? 用N階多項式對一段時間內(nèi)的測量值進行平滑擬合，根據(jù)擬合值與測量值之間的偏差，對平滑值進行加權(quán)修正，可以得到近似LOS環(huán)境下的測量值^[4]，但是由于受定位時間要求的限制，天線在每個角度的測量值不能太多，并且算法的搜索精度也不能根據(jù)實際情況靈活地改變，所以僅采用該方法消除非視距誤差和多徑傳播誤差的影響并不能達到理想的效果。
??? 本文提出了把上述兩種方法融合到一起使用的改進遺傳算法，經(jīng)過場外試驗和MATLAB仿真驗證，改進后的算法能夠有效地消除NLOS誤差和多徑傳播誤差對測量值的影響，實現(xiàn)準確估計信號到達方位的目的。
1 定位方法及信號到達方位的判斷
?? 在cdma2000-1x無源定位系統(tǒng)中，由于定位的過程是在被定位對象與基站正常通信的基礎(chǔ)上通過定位設備來完成的，不需要被定位對象和基站參與定位過程。本文采用的方法如圖1所示。?

?????????????????????
??? 當基站與被定位對象通信時，定位設備可以獲取信號從基站經(jīng)被定位對象到達定位設備所需的時延和。由于定位設備和基站的位置是確定的，并且可以通過定位設備利用GPS測量獲得。由圖1可知，通過定位設備，可得到x+y和z的值，由余弦定理可知：只要得到角度?茲的值，就可以求出x的值。由于基站和定位設備位置是可以直接測得的，若能準確估計出信號從被定位對象到定位設備的到達角，就可以得到被定位對象的具體位置。
??? 在上述定位過程中，OOA信息的準確獲得是實現(xiàn)精確定位的必要前提，而OOA信息是通過對定位設備測得的載波干擾比即載干比CIR（Carrier to Interference Ratio）進行分析獲得的。
??? 在LOS環(huán)境下，由于天線有主瓣和旁瓣，當天線正對著信號到達方位時，主瓣也正對信號到達方位，則測量所得到的信號的載干比的均值比較大，而方差則普遍比較小，即載干比的分布比較集中；而當天線偏離信號到達方位時，主瓣也偏離信號到達方位，則測量得到的信號載干比的均值比較小，而方差則普遍較大，即載干比的分布比較分散。上述特點在多次場外試驗中也得到了充分驗證。針對以上特點，可以把載干比的均值和方差兩個量作為判斷標準，進而判斷天線所對方向與信號的到達方位的偏離程度。由于載干比的值是負值（單位dB），所以可以利用載干比的均值和方差的乘積作為判斷指標。若兩者的乘積值越大，則表明定位設備的天線所對的方向就越接近信號到達方位；反之，就越偏離信號的到達方位。
??? 在NLOS環(huán)境中，定位設備在各個角度接收到的信號載干比受NLOS誤差和多徑傳播誤差的影響比較大，甚至會被這些干擾所淹沒，所以直接利用測量所得的載干比的均值和方差進行判斷就很難準確地估計天線所對的方向與信號到達方位的偏離程度，甚至會帶來很大的偏差。要想使定位設備在各種通信環(huán)境中均能實現(xiàn)精確定位，就必須采用一些優(yōu)化算法消除NLOS誤差和多徑傳播誤差的影響。
2 傳統(tǒng)遺傳算法優(yōu)缺點分析
??? 遺傳算法(Genetic Algorithm) 是一類借鑒生物界進化規(guī)律演化而來的隨機搜索方法，是模擬達爾文的遺傳選擇和自然淘汰的生物進化過程的計算模型。作為一種新的全局最優(yōu)化搜索算法，它以其簡單通用、魯棒性強、適于并行處理以及高效、實用等顯著特點，在各個領(lǐng)域得到廣泛的應用^[5]。
??? 由于該算法搜索過程不直接作用在變量上，而是對參數(shù)集進行個體編碼，所以采用合適的編碼方法可以靈活改變搜索精度。采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應地調(diào)整搜索方向，不需要確定的規(guī)則,并且算法是從串集開始搜索，覆蓋面積大，利于全局擇優(yōu)。即使算法的初始串集本身帶有大量與最優(yōu)解甚遠的信息，通過選擇、交叉、變異操作也能迅速排除與最優(yōu)解相差極大的串，因此該算法是一個強烈的濾波過程，具有很強的容錯能力^[5]。正是由于遺傳算法的上述優(yōu)點，使得遺傳算法可以用來消除非視距誤差對信號載干比的影響。
??? 但傳統(tǒng)的遺傳算法也有其致命的缺點，如“早熟”和局部搜索" title="局部搜索">局部搜索能力差?！霸缡臁比菀讓е滤阉飨萑刖植孔顑?yōu)解，而局部搜索能力差可能導致搜索后期效率不高，甚至陷入隨機搜索的誤區(qū)。初始化群體的選擇和編碼方法的選擇也會給遺傳算法帶來很大的影響。因此為了充分發(fā)揮遺傳算法的性能，就必須對遺傳算法進行改進，以達到發(fā)揮其優(yōu)越性而克服其缺陷的目的。
3 N階多項式平滑及加權(quán)修正算法
??? 該方法的主要思想是：首先對天線在每個角度下的測量值利用N階多項式進行平滑擬合（N階多項式的系數(shù)是根據(jù)測量值用泰勒級數(shù)來獲得的，采用的最優(yōu)化準則是最小二乘法）；然后對平滑曲線進行采樣，根據(jù)平滑曲線采樣點與該點所在曲線段的均值的偏差，進行加權(quán)修正平滑曲線。加權(quán)系數(shù)的選取遵循偏差絕對值大加權(quán)系數(shù)小，偏差絕對值小加權(quán)系數(shù)大的原則。
??? 采用該方法可以把NLOS環(huán)境下測量得到的測量值通過擬合、平滑加權(quán)修正得到近似LOS環(huán)境下的測量值，達到消除NLOS誤差和多徑傳播誤差的效果，但是該方法也受測量值數(shù)量的限制，即在測量值比較少的情況下，采用該方法效果也并不理想^[3]。該方法的修正是在平滑值基礎(chǔ)上進行加權(quán)修正的，加權(quán)系數(shù)的選擇對算法的性能影響也比較大。加權(quán)系數(shù)的選取不能太大，否則會引來額外的誤差；如果加權(quán)系數(shù)選取的過小，則不能達到完全消除NLOS誤差和多徑傳播誤差的目的，并且該方法的搜索精度不能根據(jù)實際情況做適當?shù)母淖?。因此在測量值受誤差影響比較嚴重或者影響不斷變化的情況下并不能有效消除NLOS誤差和多徑傳播誤差的影響。
4 改進遺傳算法
??? 改進遺傳算法是把N階多項式平滑及加權(quán)修正法與遺傳算法融合一起使用。該算法主要是利用N階多項式擬合加權(quán)修正的思想來彌補遺傳算法的“早熟”和局部搜索能力差的缺陷；利用遺傳算法全局搜索能力強和容錯能力強及搜索精度可以靈活改變的優(yōu)勢來彌補加權(quán)系數(shù)選擇的局限對N階多項式擬合加權(quán)修正算法性能的影響，并且有效降低了測量值數(shù)量對算法性能的影響，使改進算法的性能在實際應用中得以充分發(fā)揮。
??? 改進遺傳算法如下：
??? (1)在初始化群體選擇時，把N階多項式平滑、擬合的方法融入其中，實現(xiàn)初始化群體在搜索空間的均勻分布，從而有效避免早熟現(xiàn)象的發(fā)生，減小搜索陷入局部最優(yōu)解得可能性，并且可以降低測量值數(shù)量對算法性能的影響。
??? 實現(xiàn)思路：在測量值的基礎(chǔ)上利用最小二乘法和泰勒級數(shù)的方法對測量值進行N階多項式平滑、擬合，形成擬合曲線；然后利用均勻采樣的方法對曲線進行采樣，把采樣所得的值作為測量值的有效補充。假設在每個角度下的測量值個數(shù)為N，則經(jīng)過擬合后的曲線可以分為N-1段。若在改進遺傳算法中選擇的初始化群體中元素的個數(shù)為W=a(N-1),則在選擇遺傳算法的初始群體時，在平滑曲線的每一段隨機選取a個值作為初始化群體的元素，通過上述方法就實現(xiàn)了初始化群體在搜索空間的均勻分布，可以有效避免搜索陷入局部最優(yōu)的發(fā)生。
??? (2)在進行編碼之前，先對采樣點進行等級劃分，把采樣值均勻劃分為2 000個等級，等級劃分規(guī)則如下：令最小的采樣值為Mmin，其等級值Smin=1，最大的采樣值為Mmax，其等級值Smax=2001，等級間隔為scale。則：?
???

??? 假設采樣值M的等級值為S_M，則有：
???
??? 然后把初始化群體中的元素也轉(zhuǎn)換成相應的等級值，參與遺傳算法的編碼。
??? (3)為了使算法能隨通信環(huán)境的改變而靈活改變搜索精度，在對初始化群體的元素等級進行編碼時，采用格雷碼" title="格雷碼">格雷碼進行編碼。這樣，在通信環(huán)境惡劣的情況下，就可以自動增大搜索精度；而在通信環(huán)境理想時，就可以自動減小搜索精度，從而使算法能更有效地消除NLOS誤差和多徑傳播誤差。
??? 在本改進算法中，采用格雷碼進行個體編碼，該碼是由自然二進制碼轉(zhuǎn)換而來，其轉(zhuǎn)換方法如下：假設自然二進制編碼為B=b_mb_m-1…b₂b₁,其對應的格雷碼的轉(zhuǎn)換公式為：
???

??? 格雷碼的特點是連續(xù)的兩個整數(shù)所對應的編碼值之間只有一個碼位是不相同的，任意兩個整數(shù)的差是這兩個整數(shù)所對應的格雷碼之間的海明距離，這使得在遺傳算法中的一次交叉、變異操作也僅使其對應的參數(shù)發(fā)生微小的變化，有助于提高遺傳算法的局部搜索能力，也便于交叉、變異操作，并且可以根據(jù)測量值的實際情況對搜索精度做靈活的改變^[5]。
??? (4)為了保持樣本的多樣性，本改進算法采用單點交叉的方法，交叉概率為0.4。這樣既可以滿足產(chǎn)生新個體的要求，又不會破壞個體的適應度，使算法很容易地搜索到最優(yōu)解附近，具有很強的全局搜索能力。
??? 在本文的改進算法中，選取的變異概率為0.001，變異方法是非均勻變異，它相當于整個解向量在解空間作了一個輕微的變動，可以重點搜索原個體附近的微小區(qū)域，更有利于搜索到最優(yōu)解，使算法只需花費很小的代價就可以從最優(yōu)解附近搜索到達最優(yōu)解。
??? (5)在適應函數(shù)選取前把交叉前后的串先進行解碼，把等級值轉(zhuǎn)換為載干比值。
實現(xiàn)思路如下：先把格雷碼轉(zhuǎn)換為自然二進制碼，假設格雷碼為：G=g_mg_m-1…g₂g₁，則轉(zhuǎn)化為自然二進制的方法為：
???

??? 再把解碼后的等級值轉(zhuǎn)換成載干比值，轉(zhuǎn)換方法如下：假設采樣點N的等級值為S_N，則采樣點N的初始值為：
??? ?

??? (6)在適應函數(shù)選取及復制操作中，把交叉、變異操作前的初始化群體的值和操作后的值按照它們與所在曲線段的均值的偏差的大小進行加權(quán)疊加，產(chǎn)生新的初始化群體元素。
??? 實現(xiàn)思路為：①先找出搜索點所在曲線段，然后求出該曲線段的載干比的平均值;②計算搜索點在交叉、變異操作前的載干比值與所在曲線段的載干比均值的標準偏差，令為f₁;③計算搜索點在交叉、變異操作后的載干比值與所在曲線段的載干比的平均值的標準偏差，令為f₂;④若設搜索點的載干比為CIR1,交叉變異操作后的載干比為CIR2，選擇復制后的載干比為new_CIR；令:a₁=f₁/(f₁+f₂), a₂=f₂/(f₁+f₂)則：?
???
??? 在原來初始化群體元素的基礎(chǔ)上,該方法利用交叉、變異操作，對元素附近區(qū)域進行搜索，然后根據(jù)偏差的大小進行加權(quán)修正，充分利用各個曲線段內(nèi)相鄰點之間的相關(guān)性，可以更為有效地消除NLOS和多徑傳播的影響。
??? 為了減小算法搜索隨機性對優(yōu)化結(jié)果的影響，本文采用多次迭代、求平均值的方法。
5 仿真結(jié)果及性能分析
??? NLOS和多徑傳播是載干比測量值產(chǎn)生偏差的主要因素，它既可使載干比的測量值產(chǎn)生正向偏差，也可使載干比測量值產(chǎn)生負向偏差，并且偏差的統(tǒng)計特性也是未知的。
??? 為了充分驗證算法在各種通信環(huán)境下的性能，本文分兩部分進行驗證：第一部分是對一般的通信環(huán)境（受NLOS誤差和多徑傳播誤差影響比較?。y量結(jié)果進行驗證，第二部分是對通信環(huán)境比較復雜情況下（受NLOS誤差和多徑傳播誤差影響比較大且不斷變化）測量結(jié)果進行驗證。由于對信號達到方位信息的判斷是通過載干比的均值和方差兩個指標來衡量的，所以在驗證算法性能時，主要也是從優(yōu)化前后載干比的均值和方差的變化情況來綜合衡量算法的性能。
??? 本文采用MATLAB做仿真驗證。仿真結(jié)果如圖2～圖7及表1和表2所示。在圖2、4、6中的橫坐標表示在每個角度下獲得的測量值的個數(shù)，在圖3、5、7中橫坐標表示優(yōu)化后輸出的載干比個數(shù)；在圖2 、3、4、5中縱坐標表示載干比值（單位dB），在圖6、7中縱坐標表示載干比方差。

????????????????????????

??????????????????????????
??? 其中，表1和表2中的角度偏差是天線所對方向與信號到達方位的偏差，指標是判斷角度偏差大小的衡量指標，即載干比的均值與方差的乘積。平均指標是天線在每個角度下所有測量值產(chǎn)生的指標的總和與測量值個數(shù)的比值。從圖2~3分析可知優(yōu)化后載干比的均值變化不大，而分布相對比較集中，既方差普遍變小，并且各個角度之間的方差區(qū)別更加明顯。從表1可以看出，優(yōu)化后每個測量值的平均指標有所提高，并且區(qū)分更為明顯。

?????????????????????????????

?

?????????????????????????????

????場外試驗和仿真實驗表明，該算法不僅能避免遺傳算法“早熟”現(xiàn)象的發(fā)生，而且克服了N階多項式擬合及加權(quán)修正的方法不能根據(jù)實際情況靈活調(diào)整搜索精度的缺陷，并且有效抑制了測量值的數(shù)量對誤差消除程度的影響，可以有效消除NLOS誤差和多徑傳播誤差對測量值的影響，避免錯誤判斷的發(fā)生，實現(xiàn)精確估計信號到達方位的目的。

參考文獻
[1] 范平志,鄧平,劉林.蜂窩網(wǎng)無線定位[M].北京:電子工業(yè)出版社,2002.
[2] CAFFERY J. Wireless location in CDMA celluar radio?systems [M].Boston:Kluwer Academic Publishers,2000.
[3] CAFFERY J. STUBER L. Subecriber location in CDMA?celluar networks [J]. IEEE Trans,on Vehicular Technology,1998,47(2):406-415.
[4] WYLIE M P, HOLTZMAN J. The non-line-of sight?problem in mobile location estimate [A].IEEE International ?conference on universal person communication Cambridge,Massachusetts,USA, 1996: 827-831.
[5] 周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,1999.

?