基于多目標自適應DE算法在UWB中的應用研究

尤諜, 陳勇, 張修偉, 段剛鵬

(重慶師范大學,計算機與信息科學學院,重慶 401331)

0 引言

室外定位依賴于GNSS,提供載體姿態和位置信息[1-2],具有足夠的精度,但它的工作能力僅限于能夠實現無遮蔽衛星跟蹤的室外環境。環境超出GPS的覆蓋范圍,室內定位技術不斷涌現,比如ZigBee、UWB、Wi-Fi、RFID等定位技術[3-4]。UWB技術被稱之為“超寬帶”,又稱之為脈沖無線電技術,利用納秒至微秒級的非正弦波窄脈沖傳輸數據,UWB發射功率很小,應用范圍很廣[5-6]。UWB具有高時間分辨率和良好的過障能力,能在室內區域實現高精度測距。UWB定位被視為高精度需求的最佳解決方案之一,在室內通信、高速無線LAN、家庭網絡、安全檢測、位置測定、雷達、醫療及軍事領域都有廣泛應用。室內復雜環境下超寬帶信號傳播存在非線性視距(NLOS)誤差問題[7]。室內超寬帶定位技術關鍵在于測距,測距主要取決于到達時間(TOA)的估計。TOA存在一些關鍵挑戰,如電子干擾、NLOS條件等。UWB信號在傳播過程中不可避免地產生多徑效應,從而導致明顯的NLOS定位誤差。

1 UWB定位技術原理

UWB的定位技術有多種方法,通常采用距離信息定位算法。本文采用飛行時間(TOF)的測距。TOF測距技術是UWB定位法中最常見的定位方法。

1.1 TOF測距技術

雙邊雙向測距原理如圖1所示。雙邊雙向測距分2次進行。設備A先發起第一次測距并記錄發送的時間戳,設備B收到數據,記錄接收時間戳;設備B響應,發送信號給A并記錄發送時間戳,當設備A收到數據之后,再返回數據。這樣可以得到4個時間差:Tro1、Tro2、Tre1、Tre2。

圖1 雙邊雙向測距原理圖

由設備A的時間差Tro1、Tro2,設備B的時間差Tre1、Tre2,得到無線信號飛行時間Tp:

(1)

(2)

如Tp1=Tp2=Tp,則進一步計算可得:

(3)

可得到飛行時間TP計算式:

(4)

若響應時間對稱,設Tre1=Tre2,則

(5)

2 差分進化算法

2.1 種群初始化

在目標空間中隨機產生均勻M個個體,每個個體由n維向量組成,當前世代種群的第i個個體表示方法如下:

(6)

第i個個體的第j維取值方式:

xi,j,0=xj,min+rand(0,1)×(xj,max-xj,min)

(7)

其中,rand(0,1)是介于0到1之間的隨機數,xj,min和xj,max分別為xi在第j維的最小值和最大值。

2.2 變異操作

在第G次迭代中,從種群中隨機選擇3個個體Xp1,G、Xp2,G、Xp3,G且p1≠p2≠p3,則生成的變異向量為

Vi,G=Xp1,G+F(Xp2,G-Xp3,G)

(8)

2.3 自適應交叉

(9)

CR是交叉算子,自適應調整,CRl、CRu是CR的下限和上限。fi是個體Xi的適應度,fmax、fmin分別是當前種群中最差和最優個體適應度。

CR是交叉算子,當rand(0,1)<=CR時,第i個向量的后代ui向量的第j維等于變異向量vi的第j維;否則ui,j等于xi,j;從[1,2,…,D]中隨機選擇一個數作為jrand,以保證Ui,G至少有一個維度來自Vi,G。

2.4 環境選擇

(10)

環境選擇過程會根據適應度值作出判斷,若子代優于父代則選擇子代,反之則選擇父代。

2.5 變異策略

為了防止陷入局部搜索,采用3種不同的變異策略:

Vi,G=Xbest,G-F(Xp1,G-Xp2,G)

(11)

Vi,G=Xi,G+F(Xbest,G-Xi,G)+F(Xp1,G-Xp2,G)

(12)

Vi,G=Xp1,G+F(Xp2,G-Xp3,G)+F(Xp4,G-Xp5,G)

(13)

3 多目標差分進化算法

3.1 傳統多目標差分進化算法

算法1給出了傳統的多目標差分進化算法[8-9]的總體框架。

算法1 傳統多目標差分進化算法1 Initialize the population P2 Evaluation(P)3 while gen<=Max_gen4 for each individual p in P5 select individuals to generate difference vector6 v=mutation(p)7 o=crossover(v,p)8 Evaluation(o)9 end for10 C=[P,O]11 nondominated_sorting(C)12 Calculate_crowding_distance(C)13 P=Environmental selection(C)14 end while15 Output the final population P

3.2 改進的多目標差分進化算法

傳統的多目標差分進化算法存在2個問題:

(1) 種群中的個體共用相同的參數。比如所有個體使用相同的變異策略以及交叉算子CR等參數。種群中的每個個體所處的環境是不同的,有些個體所處的環境比較擁擠,而有些個體則處于稀疏的環境中,因此對它們使用相同的參數是不合理的。

(2) 參數全局固定。進化算法在初期更側重于全局搜索、擴大搜索范圍,在后期則更側重于局部搜索。固定的變異策略、交叉算子等參數顯然會影響算法的性能。

針對上述問題,提出自適應多目標差分進化算法:

Step 1:根據種群中每個個體所處的環境為其分配參數,且所分配的參數會動態地調整以適應環境的變化。

Step 2:根據擁擠距離的大小,將個體所處的環境劃分為3個等級,每個等級使用一套參數。

Step 3:權重系數w會隨著迭代的進行逐漸降低算法的搜索能力,在不影響算法前期搜索能力的情況下增大算法后期的局部開發能力。

(14)

(15)

(16)

CD1=CDmin+(CDmax-CDmin)/3

(17)

CD2=CDmax-(CDmax-CDmin)/3

(18)

(19)

其中,gen和Max_gen分別表示當前迭代次數和最大迭代次數,CDmin和CDmax分別為種群中個體擁擠距離的最小值和最大值,CDi為種群中第i個個體的擁擠距離。

3.3 多目標差分進化精確定位模型建立

DE群體中突變和交叉操作被用于探索空間,而選擇用來確保有希望的個體可以進一步利用,通過種群不斷的迭代變異,估計出Tag的精確位置。根據估計的Tag到錨點的距離和Tag到錨點的真實距離差設置目標函數,提出UWB方法結合多目標差分進化精確定位目標函數為

(20)

(21)

(22)

(23)

其中,(xi,yi,zi)是第i個Anchor坐標,i的范圍為[1,4],(x,y,z)是使用此定位模型定位出的Tag坐標,Ri是到Anchor的真實值。目標函數f值越小,(x,y,z)越逼近Tag的精確定位。由此,定位問題可轉化為優化問題:

(24)

4 差分進化精確定位模型實驗結果

本次實驗在室內的測試環境中,分別在測試環境的4個角落A0、A1、A2、A3放置UWB錨點(Anchor),并向所有方向發送信號。Tag是需要定位的目標。其實驗場景示意圖如圖2所示。利用TOF技術,測算飛行時間,按照信號是否有遮擋分為場景1和場景2。

圖2 實驗測試環境示意圖

4.1 已知信號有無干擾定位實驗

場景1測得無干擾的正常數據與場景2測得有干擾的異常數據比較,明顯異常數據分散,如圖3所示。

(a) 場景1

利用多目標差分進化算法定位,結果如圖4所示。圖中心位置為定位出的Tag位置,四角為Anchor。

(a) 場景1無干擾

為證明此算法定位的精確性,進行誤差計算,誤差結果如表1、表2所示。表1中,場景1在無信號干擾條件下,計算出Tag坐標為(521.18,520.83,1076.2),單位為mm。

表1 無干擾下定位精度

表2 有干擾下定位精度

表2中,場景2在有信號干擾條件下,計算出Tag坐標為(516.74,525.83,1120.3),單位為mm。

4.2 未知信號有無干擾定位實驗

此定位模型可以應用于不同場景,在未知是否存在干擾時,也有良好表現。設置場景3隨機施加擾動,將測得的數據進行精確定位實驗,結果如圖5所示。

圖5 未知有無信號干擾定位效果圖

場景3在未知是否有干擾條件下,計算出Tag坐標為(518.94,526.12,1100),單位為mm。定位精確度如表3所示。

表3 未知是否有干擾下定位精度

5 總結

實驗表明,通過多目標差分算法與UWB定位技術結合,在未知干擾情況的室內環境定位實驗中,該方案有優秀表現,具有較強的環境適應性,精度可達毫米級。本算法也存在一定的改進空間,其在室外環境惡劣的條件下精度有待提高,這也將是未來繼續研究的重點。