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

?

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

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

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

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

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

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

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

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

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

?

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

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

參考文獻(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] 周明,孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社,1999.

?