基于GA-BP神經(jīng)網(wǎng)絡(luò)的超寬帶室內(nèi)定位

薛陽陽，沈 重

（海南大學信息與通信工程學院，海南?？?570228）

與主要應(yīng)用于室外場景的全球定位系統(tǒng)不同，超寬帶（Ultra Wide Band，UWB）定位主要用于復雜的室內(nèi)環(huán)境，在商場、機場、生產(chǎn)車間等大型建筑內(nèi)應(yīng)用廣泛.與傳統(tǒng)信號相比，UWB信號具有時域較窄、工作頻率極高、占空比極低、頻譜寬、能量密度低等特性，使其具有時間分辨率增強、功耗極低和隱蔽性好等優(yōu)點，故被廣泛應(yīng)用于室內(nèi)定位［1］.由于室內(nèi)環(huán)境存在人員流動、建筑、障礙物等，在定位時會產(chǎn)生非視距（Not Line Of Sight，NLOS）誤差以及多徑干擾［2］.如何降低或消除NLOS誤差成為了研究的重點.

目前，UWB室內(nèi)定位的主要技術(shù)有：基于到達角度（Angle Of Arrival，AOA）方法［3］、基于到達時間（Time Of Arrival，TOA）方法［4］、基于接收信號強度（Receive Signal Strength，RSS）方法［5］和基于到達時間差（Time Difference Of Arrival，TDOA）方法［6］.由于信道環(huán)境的復雜性，受NLOS影響，通常會產(chǎn)生較大的誤差.在此基礎(chǔ)上許多學者進行了研究，陳小斯［7］等使用差分技術(shù)對TDOA算法進行改進，提高了定位系統(tǒng)的穩(wěn)定性；Shen C［8］等人綜合了TDOA和AOA算法的優(yōu)點，結(jié)合最陡下降算法，消除了非視距誤差；Li N［9］等使用將布谷鳥搜索算法與BP神經(jīng)網(wǎng)絡(luò)進行結(jié)合，對TDOA進行校正；Niitsoo A［10］等將深度學習與定位結(jié)合起來降低多徑干擾對位置估計的影響.雖然傳統(tǒng)BP神經(jīng)網(wǎng)絡(luò)可以對通信過程中NLOS誤差進行修正，但由于BP神經(jīng)網(wǎng)絡(luò)是沿誤差函數(shù)反向傳播時梯度下降的方向搜尋，尋找到的閾值和權(quán)值有可能是局部最優(yōu)值.為避免此情況發(fā)生，筆者采用遺傳算法（Genetic Algorithm，GA）進行優(yōu)化.自然界種群的進化過程就是對個體基因的擇優(yōu)選取，在個體繁殖的過程中，基因可能發(fā)生突變、交叉從而誕生更優(yōu)秀的基因，具有優(yōu)秀基因的個體更容易存活下來.在多代繁殖后，種群中存活下的都是優(yōu)良個體.遺傳算法模仿上述過程，對BP神經(jīng)網(wǎng)絡(luò)中的參數(shù)編碼形成種群并進行種群進化.進化結(jié)束后，對種群中最優(yōu)良個體進行解碼獲取最優(yōu)參數(shù)并用其構(gòu)建BP神經(jīng)網(wǎng)絡(luò)定位模型.使用模型獲取校正過后的TOA值并代入TDOA定位中的Chan算法進行位置估計.

1 算法描述

1.1 BP神經(jīng)網(wǎng)絡(luò)BP神經(jīng)網(wǎng)絡(luò)通過計算輸出值與期望值的誤差優(yōu)化系統(tǒng)的參數(shù).網(wǎng)絡(luò)一般有一個輸入層、一個輸出層、一個或多個隱含層，參數(shù)為層與層之間的權(quán)值和閾值［11］.其拓撲結(jié)構(gòu)如圖1所示.

圖1中X i為神經(jīng)網(wǎng)絡(luò)的M個輸入，ωij為輸入層到隱含層的權(quán)值，輸入到達隱含層時需經(jīng)閾值t j判斷是否能夠激活神經(jīng)元，若輸入大于閾值t j則使用激活函數(shù)S(x)獲取Y j，同理得隱含層到輸出層的權(quán)值γjk，輸出層閾值k k，隱含層到輸出層輸出Z k.其中激活函數(shù)為便于后續(xù)計算，選用Sigmoid函數(shù)，其公式為

圖1 BP神經(jīng)網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

BP神經(jīng)網(wǎng)絡(luò)首先通過正向傳播過程獲取輸出，將輸出和期望輸出之間的誤差反向傳播，沿誤差函數(shù)梯度下降的方向求解最小值，此時神經(jīng)網(wǎng)絡(luò)的參數(shù)為梯度下降算法搜尋到的最小解.假設(shè)期望輸出為r=[r1，r2，…，r O]，則其誤差函數(shù)為

1.2 遺傳算法遺傳算法通過模擬大自然生物的自然選擇和遺傳學機理搜尋最優(yōu)解.該算法屬于全局搜索算法［12］，其對模型整體的優(yōu)化性能十分優(yōu)秀，其算法流程如圖2所示.

圖2 遺傳算法流程圖

遺傳算法的主要過程為：1）對算法中的參數(shù)設(shè)置初值，生成一代群體；2）為評價個體的優(yōu)劣，選用合適的適應(yīng)度函數(shù)計算每個個體的適應(yīng)度；3）對群體進行選擇操作，按照設(shè)置概率進行交叉操作和變異操作，在滿足設(shè)置的終止判斷條件后結(jié)束訓練.

1.3 TDOA定位算法TDOA使用基站之間的時間差信息進行定位.該算法需要基站之間嚴格地時鐘同步［8］，假設(shè)基站A，B，C的坐標為(x1，y1)，(x2，y2)，(x3，y3)，標簽的坐標為(x，y)，則其TDOA非線性方程

其中，t0表示標簽發(fā)送信號的時刻，t1，t2，t3表示基站收到標簽信號的時刻，c表示電磁波傳播速度.

式（3）可直接使用最小二乘法進行位置估計，但定位精度較差，故需采用其他位置估計算法.采用Chan算法進行位置估計，其優(yōu)勢在于無初始值要求且位置估計精度很高［13］.其計算過程為

首先對方程（4）兩邊平方得

設(shè)標簽到達A基站和到達其他基站的距離差為d i，1，可知

聯(lián)立方程（5）和（6）可得

可簡化為

其中，

聯(lián)立式（3）和（5）且取i=1可得

求解該方程可獲取d1，再將d1代入方程（8）中即可求出標簽的估計坐標(x，y).

為評估TDOA定位性能，選用均方根誤差（Root Mean Square Error，RMSE）為評價指標，其計算過程為

其中，(x'，y')為標簽的真實位置，由該式可知其統(tǒng)計的估計坐標相對于真實位置的偏差.通過對不同定位算法的RMSE分析，可獲得其定位過程的平均精度，即可評估出算法的優(yōu)劣.在TDOA定位過程，對NLOS和LOS環(huán)境的區(qū)分的依據(jù)是TDOA標準差的不同，NLOS環(huán)境的TDOA標準差較大，故可以通過提高TDOA標準差來提升NLOS對定位算的影響.

2 GA-BP神經(jīng)網(wǎng)絡(luò)算法模型

該模型的算法流程如圖3所示，具體說明：

圖3 GA-BP算法流程

1）首先確定網(wǎng)絡(luò)結(jié)構(gòu)，結(jié)構(gòu)如圖1所示.采用三基站來對標簽進行定位，網(wǎng)絡(luò)的輸入為標簽到3個基站的TOA值，輸出層為校正后的TOA值.則M=3，O=3.隱含層的數(shù)目由經(jīng)驗公式N≥log2M確定，式中N為隱含層神經(jīng)元個數(shù)，設(shè)為8.

2）確定需要通過網(wǎng)絡(luò)優(yōu)化的參數(shù)，該網(wǎng)絡(luò)需要優(yōu)化的參數(shù)有：w i=[w i，1，wi，2，…，wi，8]T，t i=[t1，t2，…，t8]，γj，k=[g j，1，g j，2，g j，3]T，k k=[k1，k2，k2].選取［-1，1］之間的隨機數(shù)進行參數(shù)初始化.

3）遺傳算法無法對上述的參數(shù)直接進行運算，需要對上述參數(shù)進行編碼.采用浮點數(shù)編碼，主要有2點優(yōu)勢：①上述參數(shù)為類型浮點數(shù)，利于編碼計算；②在交叉、變異操作后，依然在選定浮點數(shù)的范圍，提高了精度.本文中的參數(shù)個數(shù)可用式（9）計算，計算可得浮點數(shù)編碼的染色體長度為59.

4）對獲取的訓練樣本數(shù)據(jù)進行歸一化處理并訓練網(wǎng)絡(luò)，計算輸出誤差，將誤差代入適應(yīng)度函數(shù)計算適應(yīng)度f.適應(yīng)度函數(shù)的選擇對遺傳算法有著很大的影響，在式（2）中已經(jīng)獲取誤差函數(shù)，為方便后續(xù)獲取最大適應(yīng)度，使用誤差函數(shù)的倒數(shù)作為適應(yīng)度，公式

5）進行選擇操作：常用的選擇算子有輪盤賭選擇算子、隨機競爭選擇算子和最佳保留選擇算子等［14］，在實際測試中輪盤賭選擇的誤差較大，隨機競爭選擇周期較長，最佳保留選擇性能相對均衡.選取最佳保留選擇進行選擇操作.在輪盤賭選擇的基礎(chǔ)上增加對一次選擇，降低了誤差.選擇概率公式為

其中，f i為第i個個體的適應(yīng)度；L為該種群個體數(shù)目.

6）進行交叉操作：常用的交叉算子有高概率下的單點交叉和低概率下的多點交叉，在實驗進行過程發(fā)現(xiàn)多點交叉產(chǎn)生的優(yōu)良染色體較少，故采用高概率下的單點交叉.假設(shè)需要進行交叉操作的基因為第i個染色體的第k個基因g ik和第j個染色體的第k個基因g jk，則其交換過程

其中，e是一個［0，1］之間的隨機數(shù).

7）進行變異操作：浮點數(shù)編碼要求變異后的基因仍在域內(nèi)，故需考慮變異操作的邊界問題.將基因設(shè)為2個方向變異，假設(shè)基因的最大值為gmax，最小值為gmin，當向最大值方向變異時，變異幅度不超過gmax-g，當向最小值方向變異時，變異幅度不超過g-gmin，故可得

其中，I是加速后期變異的函數(shù)，I c為當前迭代次數(shù)，Imax最大迭代次數(shù).

8）判斷性能是否滿足要求，若不滿足要求則解碼后進行4）～7）操作，若達到最大迭代次數(shù)也結(jié)束訓練，對適應(yīng)度最高個體進行解碼，得到BP神經(jīng)網(wǎng)絡(luò)的最優(yōu)權(quán)值和閾值.使用最優(yōu)參數(shù)構(gòu)建網(wǎng)絡(luò)模型，對輸入的TOA值校正并使用Chan算法進行位置估計.

3 仿真實驗及結(jié)果

3.1 實驗環(huán)境本文實驗工具為Matlab2018a.為了進行對比實驗，選取了Chan算法、BP-Chan算法和GA-BP-Chan算法進行TDOA定位，分別建立Chan算法定位模型、BP-Chan算法定位模型和GA-BP-Chan算法定位模型.在進行實驗前首先測試了基站半徑對4種定位模型RMSE的影響，如圖4所示.

從圖4可知，基站半徑對3種算法的影響趨勢比較相似，當基站半徑為10 m時，3種算法的R M S E均取得較小值.故本文采用的基站半徑為10 m.

圖4 基站半徑對不同算法的影響

在10×10的區(qū)域設(shè)置3個位置為（0，0），（10，0），（5，5 5）的UWB定位基站構(gòu)建定位場景.BP神經(jīng)網(wǎng)絡(luò)設(shè)置3個輸入、3個輸出，輸入的是待測位置與基站的有誤差TOA值，輸出為校正后的TOA值.有誤差的TOA值由UWB信號經(jīng)過與信道沖擊響應(yīng)卷積之后加入高斯白噪聲獲取.BP神經(jīng)網(wǎng)絡(luò)的最大訓練次數(shù)設(shè)置為4 000，學習效率設(shè)為0.02.GA-BP網(wǎng)絡(luò)中的交叉概率設(shè)置為0.60，變異概率設(shè)置為0.01，進化的迭代次數(shù)為100.

3.2 仿真試驗結(jié)果將標簽以1 m·s-1的速度做勻速直線運動，每隔0.1 s獲取一次數(shù)據(jù).將獲取到的數(shù)據(jù)分別輸入Chan算法定位模型、BP-Chan算法定位模型和GA-BP-Chan算法定位模型，得到如圖5所示的不同算法的運動軌跡預(yù)測圖.

由圖5可知，Chan算法和BP-Chan算法運動軌跡與真實軌跡之間偏離較遠，而GA-BP-Chan算法的軌跡與真實軌跡比較接近.即在相同環(huán)境下，GA-BP-Chan算法的優(yōu)化效果最優(yōu).測試3種算法的抗NLOS能力，在上文提到可以提升TDOA標準差模擬NLOS對定位的影響越來越大，依舊使用RMSE作為評價指標，仿真如圖6所示.

圖5 算法數(shù)據(jù)軌跡預(yù)測圖

由圖6可知，當TDOA標準差較小時，3種算法的定位精度都比較理想.當TDOA標準差開始增大時，Chan算法的RMSE快速上升，BP-Chan算法的R M S E也出現(xiàn)了明顯的上升，但波動幅度較小，GABP-Chan算法基本是在一個值范圍來回波動.由此可知，Chan算法的抗NLOS能力最差，BP神經(jīng)網(wǎng)絡(luò)算法的抗NLOS能力其次，且其定位精度在Chan算法上提高了12.82%，GA-BP-Chan算法的抗NLOS能力最強，定位精度相比于BP-Chan提高了16.12%.

圖6 不同環(huán)境下3種算法的R M S E

在對模型分析后可知，Chan算法的定位誤差急劇下降是由于Chan算法在計算過程中將噪聲的分布近似于理想高斯分布，而隨著TDOA標準差的提升，Chan算法還是將其作為理想高斯分布處理，但此時其方差和期望都與理想高斯分布偏差較大，故R M S E開始急劇上升.BP-Chan算法中，由于BP神經(jīng)網(wǎng)絡(luò)對非線性方程的強大處理能力，其對偏差的校正能力極強，但由于BP神經(jīng)網(wǎng)絡(luò)中搜尋的參數(shù)可能是局部最優(yōu)解，其對誤差的校正能力有限.GA-BP-Chan算法中，使用遺傳算法優(yōu)化了對BP神經(jīng)網(wǎng)絡(luò)參數(shù)的搜尋，搜尋BP神經(jīng)網(wǎng)絡(luò)的全局最優(yōu)解，提升了其對誤差的校正能力，故其定位性能最好.

4 結(jié)束語

為了提高復雜室內(nèi)環(huán)境下UWB定位的抗NLOS能力，將GA-BP神經(jīng)網(wǎng)絡(luò)應(yīng)用于UWB室內(nèi)定位中，使用BP神經(jīng)網(wǎng)絡(luò)提升UWB定位系統(tǒng)的抗NLOS能力，利用遺傳算法可以將全體解搜索出來的特性，對局部最優(yōu)解問題進行優(yōu)化，從而提高了算法的定位精度.實驗表明，使用GA-BP-Chan算法進行定位時，算法預(yù)測軌跡和實際軌跡基本吻合.對3種算法不在同環(huán)境下的RMSE進行分析可知，GA-BP-Chan算法的抗NLOS能力最強，且相比于BP-Chan算法，定位精度提升16.12%.將該方法在三維空間的定位是下一步研究重點.