Khảo sát các thuật toán đinh vị bằng kỹ thuật sai lệch thời gian đến

Nội dung text: Khảo sát các thuật toán đinh vị bằng kỹ thuật sai lệch thời gian đến

1. KHẢO SÁT CÁC THUẬT TOÁN ĐINH VỊ BẰNG KỸ THUẬT SAI LỆCH THỜI GIAN ĐẾN SURVEY POSITIONING ALGORITHMS USING TIME DIFFERENCE OF ARRIVAL TECHNOLOGY TS. Đỗ Hồng Tuấn - Trường ĐH Bách Khoa tp Hồ Chí Minh Nguyễn Tiến Lên - Trường Đại học Sư phạm Kỹ thuật Tp. HCM TÓM TẮT: Định vị bằng kỹ thuật sai lệch thời gian đến có nhiều ưu điểm so với các phương pháp khác và cũng có nhiều thuật toán định vị sai lệch thời gian đến khác nhau, mỗi phương pháp có ưu điểm riêng, nhưng một trong những yều cầu rất quan trọng là độ chính xác khi có sai số TDOA do tác động của nhiễu. Trong bài báo này sẽ khảo sát ba thuật toán xác định vị trí là thuật toán chuỗi Taylor, Bertrand T.Fang và Chan-Ho trong không gian hai chiều với số trạm tham gia định vị khác nhau, va với mức nhiễu sai lệch TDOA khác nhau, làm cơ sở để so sánh và đánh giá các thuật toán trên. Abtract: Technical location due to time difference of arrival (TDOA) to have several advantages over other methods, and also many false positioning algorithm to different time, each method has its own advantages, but a request for a accuracy is important when TDOA error due to the noise. This article will examine three algorithms to locate by Taylor series method, Bertrand T.Fang and Chan-Ho method in two-dimensional space with the number of stations are different, and TDOA noise at different bias, it’s to compare and evaluate algorithms 1 ĐẶT VẤN ĐỀ Từ kết quả sai lệch thời gian đến, ta tính được Bài toán định vị bằng kỹ thuật sai lệch thời gian khoảng cách sai lệch từ MS đến đến các BSi so đến (TDOA) gồm hai bước, bước thứ nhất ta đi tìm với BS1 như sau: TDOA của tín hiệu từ nguồn (MS) đến các trạm định Ri,1 c i,1 Ri R1 ( i=2,3 N) vị (BS), sau khi có được thông số TDOA ta đi ước 2 2 2 2 (Xi x) (Yi y) (X1 x) (Y1 y) (1.2) lượng vị trí của MS. Vì tín hiệu luôn bị tác động của Trong đó  là lượng thời gian sai lệch nhiễu dẫn đến có sai số TDOA, vì vậy ta phải tìm 1 i,1 thuật toán có thể ước lượng vị trí có độ chính xác cao (TDOA) giữa BSi và giữa trạm thu thứ nhất là khi có sai số TDOA. Để xem xét ưu nhược diểm của BS1, c là vận tốc truyền tín hiệu trong môi các thuật toán ta khảo sát và mô phỏng các thuật toán trường. để đánh giá. Trong bài báo này ta xem xét và khảo Giải hệ (1.2) cho ta tọa độ của nguồn. Tuy sát và mô phỏng ba thuật toán là: thuật toán Taylor, nhiên giải hệ phương trình phi tuyến này là một Bertrand T.Fang và phương pháp Chan-Ho. vấn đề tương đối phức tạp, nhất là khi các tham Mô hình bài toán định vị TDOA. số sai lệch về thời gian đến  i,1 có tác động của Ta xét trường hợp ước lượng tọa độ 2 chiều cho MS nhiễu thì phương pháp giải trực tiếp sẽ cho sai (Mobile Station). Số trạm BS (Base Station) để tham số xác định vị trí lớn. Vì vậy ta dùng các gia ước lượng vị trí là N. Sử dụng BS1 là BS tham phương pháp tuyến tính hóa các biểu thức này. chiếu, các tọa độ XY, (với iN 1: ) là vị trí biết ii Các phương pháp thường gặp như phương trước của BS thứ i. Tọa độ của nguồn cần phải xác pháp Taylor, phương pháp của Friedlander. định (MS) là (,)xy. Khoảng cách chưa biết giữa nguồn Ta thực hiện một vài phép biến đổi như sau. Từ và giữa nguồn và bộ thu thứ i là: (1.2) ta suy ra: 22 Ri ()() X i x Y i y (i=1,2, ,N) (1.1) 1
2. 2 2 22 X x X x Y y Y y Ri (Ri,1 R1 ) RRRR 2 (1.3) 1 0 2 0 1 0 2 0 i,1 ii,1 1 1 ,1 RRRR Từ các giá trị ở (1.1) thay vào (1.3) ta có: 1 2 1 2 A  (2.4) 2 2 2 2 2 2 R 2 RRRXYxy 2 XxYy 2 (1.4) i,1 i ,1 1 1 i i i i X x X x Y y Y y 1 0 NN 0 1 0 0 Lấy (1.4) trừ (311) và với i 1 ta được: RRRR 11NN 2 2 2 2 2 Ri,1 2Ri,1R1 Xi Yi X1 Y1 2Xi,1x 2Yi,1 y (1.5) Áp dụng phương pháp bình phương nhỏ nhất, Vơi: và ta tính được như sau: ́ Xi,1 Xi X1 Yi,1 Yi Y1 TT 1 Ta có hệ phương trình (1.5) tuyến tính theo (,)xy. ()AAAY (2.5) 2 CÁC THUẬT TOÁN ĐỊNH VỊ. Thực tế luôn có ảnh hưởng của nhiễu, do đó ta 2.1 Thuật toán Taylor thêm ma trận trọng lượng Q (ma trận Phương pháp này áp dụng khai triển chuỗi Taylor covariance của nhiễu) vào (2.5), khi đó ta có: để tuyến tính hóa biểu thức (1.2). Sau khi khai triển ()AQAAQYTT 1 1 1 (2.6) chuỗi Taylor, loại bỏ các thành phần bậc cao, chỉ giữ Trong các biểu thức trên (,)xy00 là giá trị lại thành phần bậc nhất để có hệ phương trình tuyến ban đầu, sau lần lặp đầu tiên thì sẽ tính như sau: chuyển thành (,)x x y y và giá trị này R ()() X x22 Y y 00 i,1 i i lại là vị trí ban đầu của bước lặp tiếp (X x )22 ( Y y ) X (0, ) (2.1 ) 11  di theo. Quá trình này được lặp lại cho tới khi Ở đây X (0, ) biểu diễn sai số TDOA của R được  di i,1 xy, , đủ nhỏ. tính ra khoảng cách. Ở đây ta xét nhiễu là nhiễu - Nếu giá trị ban đầu (,)xy00 chọn không gần Gaussian, do đó X có trung bình bằng không và độ  với giá trị thực thì sẽ khó hội tụ được. Do đó, lệch chuẩn là  di . Khai triển Taylor cho (2.1) ta đối với phương pháp này ta cần tìm ra phương được: pháp để ước lượng được giá trị ban đầu càng chính xác càng tốt. R ( X ( x  ))22 ( Y ( y )) i,1 i o x i o y 2.2 Thuật toán Friedlander 22 - (X11 ( xo  x )) ( Y ( y o y )) Thuật toán Friedlander xác định vị trí nguồn bằng cách sử dụng tiêu chuẩn lỗi bình phương (X ( x  ))22 ( Y ( y )) i o x i o y bé nhất và bình phương bé nhất có trọng lượng. 22 (X11 ( xo  x )) ( Y ( y o y )) Ta biến đổi (1.5) về dạng tuyến tính theo (x, y): fi(,) x00  x y y 1 2 2 2 2 2 XxYyi,1 i ,1 2 () XYXYR i i 1 1 i ,1 RR i ,1 1 (2.7) ffx x00 x x f(,) x y xii y i 00 || vớ i: X X X và YYYii,1 1 xyy y00 y y i,1 i 1 Ta suy ra : Sử dụng BS1 làm tham chiếu. Ta viết (2.7) ở dạng ma trận như sau: x x x x ffii00 Rii,1 f(,) x 0 y 0 x y (2.2) ||y y y y SX  R p (2.8) xy00 1 1 Từ (2.2) ta có hệ phương trình như sau: Với các thành phần trong (2.8) được tính như Y   (2.3) sau: X Y R f(,) x y x 2,1 2,1 2,1 2 0 0 X , , x S   Trong đó: , Y  y X X y N ,1 N ,1 d2,1 f 2(,) x 0 y 0 2
3. 2 2 2 2 2 TTTT 1 (X 2 Y2 ) (X1 Y1 ) R2,1 X () S M QMS S M QM (2.12) 1   2 Ma trận trọng lượng Q là ma trận hiệp phương 2 2 2 2 2 (X N YN ) (X1 Y1 ) RN ,1 sai covariance của các Ri, j , Q có dạng: và: p R ,R ,R T 1 2,1 3,1 N ,1 1 0.5 0.5 Trong biểu thức trên, S,, p là các thông số đã 0.5 1 0.5 1 Q  2 (2.13) biết, X là vector tọa độ nguồn mà ta cần xác định.     22 0.5 0.5 1 R1 ()() X 1 x Y 1 y là thông số phụ thuộc vào tọa độ nguồn cần xác định vị trí, do đó ta chưa biết 2.3 Thuật toán Y.T.Chan và K.C.Ho Trong bài báo: Một ước lượng đơn giản và R1 , ta tìm cách loại bỏ hệ số này. Để loaị bỏ hê ̣số hiệu quả cho định vị heperbol (A Simple and này ta nhân công thức (2.8) với ma trận M sao cho Efficient Estimator for Hyperbolic Location) tích của Mp 0 . Ma trận M được định nghĩa 1 tháng 8 năm 1994, Y.T.Chan và K.C.Hoo đã như sau: đưa ra một phương pháp không lặp để có thể MIZD () (2.9) ước lượng vị trí một cách chính xác, và phương Trong đó, ma trận I là ma trận đơn vị, ma trận D pháp này có thể đạt được hiệu quả tối ưu với được tính như sau: các bộ thu đặt ở vị trí bất kì, và có thể khắc 1 R 0 phục các nhược điểm của phương pháp chuỗi 2 ,1 1 D diag p   Taylor là phải thực hiện các phép toán lặp và  1  0 R có thể không hội tụ nếu chọn vị trí ban đầu của N ,1 MS không chính xác. Theo Chan và Ho, khi và các lỗi ước lượng là nhỏ thì phương pháp này 0 1 0 sẽ tiến tới ước lượng ML (maximum  Z likelihood). 01 Trước tiên thực hiện biến đổi biểu thức (1.5), 10 ta đặt KXY 22, khi đó (1.5) được viết Ma trận Z có được bằng cách: hàng trên dịch vòng i i i sang phải một vị trí thì sẽ thu được hàng bên dưới. như sau: 2 Từ các ma trận được định nghĩa như trên ta có: Ri,1 2 R i ,1 R 1 K i K 1 2 X i ,1 x 2 Y i ,1 y (2.14) T D p1 1 [1,1, ,1] Sau đó xét 2 trường hợp: khi chỉ có 3 BS và và (IZZ )  1 1  1 1 1 0 khi có nhiều hơn 3 BS tham gia định vị. 2.3.1 Khi chỉ có ba trạm BS Ta suy ra: M R  p R ( I Z )  D  p 0 1 1 1 1 Khi có 3 BS tham gia định vị, ta có được 2 Do đó, nhân ma trận M này vào phương trình (2.8) TDOA, tọa độ nguồn: (,)xy có thể giải theo ta được: R ở (3.34), ta biến đổi để viết dưới dạng ma MM X  (2.10) 1 trận như sau: Tọa độ nguồn X có thể được ước lượng bằng phương XYR 1 2 x 2,1 2,1  2,1 1 RKK2,1 2 1 pháp LS (least squares) cho phương trình tuyến tính R (2.15) 1 2 y XYR 2 RKK (2.10), kết quả vector tọa độ nguồn được ước lượng 3,1 3,1  3,1 3,1 3 1 bằng công thức: Thay (2.15) vào (1.1), với i 1 ta được biểu TTTT 1 X (SMMSSMM )  (2.11) thức bậc 2 của ẩn số R1 , thay lại vào trong Trong thực tế có sai số TDOA do nhiễu, để tối ưu (2.15) ta sẽ có kết quả cuối cùng. Ta có thể có việc ước lượng ta thêm một ma trận trọng lượng Q 2 nghiệm. Thông thường hai giá trị của nghiệm vào (2.11). Biểu thức ước lượng cuối cùng có dạng: ở cách khá xa nhau, ta chọn nghiệm nằm trong 3
4. phạm vi bán kính R của các BS tham gia định vị. khoảng cách, I là ma trận đơn vị có kích 2.3.2 Khi có nhiều hơn 3 BS (N≥4) thước (N-1)x(N-1). Lúc này ta có thể xấp xỉ Trong trường hợp số BS tham gia xác định vị trí (2.18) như sau: T 1 1 T 1 lớn hơn 3, hệ biểu thức TDOA ban đầu được biến đổi Za (Ga Q Ga ) Ga Q h (2.19) sang dạng tuyến tính với biến phụ thêm vào. Ta áp Khi nguồn ở gần các BS, ta dùng (2.19) để dụng phương pháp bình phương bé nhất có trọng ước lượng vị trí ban đầu. Sau đó dùng (2.18) để lượng lần thứ nhất để có kết quả tọa độ ban đầu. Sau ước lượng cho kết quả cuối cùng. mà không đó ta tiếp tục dùng phương pháp bình phương bé nhất cần dùng lặp lại phép toán, ta vẫn có kết quả có trọng lượng lần thứ hai, ta có ước lượng vị trí chính xác. được cải thiện, thông qua vị trí ước lượng ban đầu ở Ma trận covariance của Za đạt được bằng cách lần ước lượng thứ nhất và biến phụ như sau: đánh giá kì vọng của và ZZT từ (2.18), và T aa -Ta đặt z zT R là vector chưa biết, với ap 1 được tính: T , với nhiễu TDOA, vector lỗi (sai số) từ zp x, y 0T 1 0 1 cov(za ) ( G a G a ) (2.20) công thức (3.34) là: Khi tính za ở trên ta giả sử là xy, và R1 là  h G z0 (2.16) aa độc lập, nhưng thực tế chúng có liên quan với RKK2 2,1 2 1 nhau bởi (1.1) khi i 1. Để nâng cao hơn độ 2 1 RKK Với: h 3,1 3 1 chính xác của ước lượng, ta biểu diễn các thành 2  2 phần của vector của za như sau: RKKNN,1 1 0 0 z x e ; za,2 y e 2 XYR2,1 2,1 2,1 a,1 1 và XYR3,1 3,1 3,1 0 G zea,3 R1 3 (2.21) a XYR Với ee, và e là các lỗi ước lượng của z . NNN,1 ,1 ,1 12 3 a -TDOA tìm được bằng cách lấy tương quan chéo với Trừ hai thành phần đầu tiên của za cho X 1 và dữ liệu Gaussian sẽ xấp xỉ phân phối chuẩn nếu như Y1 (tọa độ của BS tham chiếu), sau đó bình tỉ số tín hiệu trên nhiễu SNR cao. Ma trận covariance phương sẽ cho ta kết quả: của  vì vậy cũng có thể được ước lượng bởi:  '''' h Gaa z (2.22) T 2 0 0 0  E []  c BQB (2.17) (2.17)''' Với: B diag{,,,} R12 R RN vàQ là ma trận covariance của TDOA. Trong đó h,, G  za được tính như sau: -Thành phần Z trong (2.16) vẫn là một tập biểu a 2 (za,1 X1) 1 0 thức không tuyến tính của hai biến (,)xy. Để tính h' (z X )2 , G' 0 1 a,2 1 a Z , trước tiên ta coi 3 biến x, y,R là độc lập. Ta có 2 a 1 za,3 1 1 2 thể ước lượng Maximum Likehood lần 1 của Za như (x X ) và z' 1 (2.23) sau: a 2 ( y Y1 ) T 1 Za arg min{( h G a z a ) ( h G a z a )} Vector  ' biểu diễn cho sự không chính xác T 1 1 T 1 (Ga Ga ) Ga h (2.18) trong za . Khi các lỗi ee12, , và e3 là nhỏ. Ma Vì  không biết trước và vì B có chứa khoảng cách trận covariance của  ' được tính: thực giữa nguồn và các BS. Vì vậy ta cần phải xấp xỉ ' E ['   ']T 4'cov( B z )' B (2.24) thêm một lần nữa. a 0 0 0 0 0 Với : B'{,,} diag x X1 y Y 1 r 1 Khi nguồn ở xa các BS, mỗi Ri R , do đó ta ước lượng sơ bộ cho B : B R0I , với R0 biểu diễn cho Theo giả sử ở trên thì  là quá trình Gaussian, dẫn đến cũng là quá trình Gaussian 4
5. 2 "TT 1 0 1 1 1 (Gaussian). Do đó ước lượng Maximum Likehood c B G'''')a B G a B G a B G a (2.31) của z'a là: Trong đó: 0 TT 1 1 1 (xX ) 0 z'(''')''' G G G h (2.25) " 1 a a a a B 0 0 (yY 1 ) Ma trận  ta chưa biết, vì nó chứa đựng các giá trị Từ các tính toán ở trên, ta có thể tóm tắt thực cần xác định. Tuy nhiên, B ' có thể được xấp xỉ thuật toán Chan-Hoo khi số trạm BS tham gia 0 bằng cách dùng các giá trị za , Ga trong (2.20) được xác định vị trí lớn hơn 3 như sau: phương trình xấp xỉ bởi Ga , và B trong (2.17) được xấp xỉ bởi các (2.18), (2.25) và (2.29) là các phương trình cho giá trị đã được tính từ (2.19). Nếu nguồn ở xa, ta có: lời giải của thuật toán Chan-Ho. Vì ma trận 0 20T 1 0 1 trọng lượng trong (2.18) và (2.25) ta chưa biết, cov(za ) ( cR ) (GQGaa ) (2.26) nên ta cần một xấp xỉ hợp lý để có thể có được Và lúc này (2.25) trở thành: lời giải cho phương pháp này. z'('''')('''')' GBGQGBGTT 1 1 1 1 GBGQGBGh 1 1 1 a a a a a a a a a (2.27) - Khi nguồn ở xa các BS, các công thức Lưu ý rằng trong công thức trên, ma trận G 'a là (2.19), (2.27), và (2.29) được sử dụng để ước lượng. hằng số. Bằng cách lấy kì vọng của z' và z' z'T ta a a a - Khi MS ở gần các BS, trước tiên ta dùng có ma trận covariance của là: (2.19) để có được một xấp xỉ cho ma trận B. T 11 Sau đó sử dụng các biểu thức (2.18), (2.25) và cov(')za ( G ' a ' G ') a (2.28) (2.29) để ước lượng cho kết quả cuối cùng. Kết quả ước lượng vị trí cuối cùng có được được từ Ma trận covariance  cov(zp ) trong (2.31) là: được dùng để đánh giá độ chính xác của vị trí ước x zz ' 1 (2.29) lượng. pa y 1 Ta chọn nghiệm nằm trong bán kính ước lượng của 3. KẾT QUẢ MÔ PHỎNG CÁC THUẬT TOÁN các BS. Nếu một trong các tọa độ của z'a gần với Kết quả mô phỏng các thuật toán như trong zero, thành phần căn bậc hai trong (2.29) có thể trở hình 3.1 đến hình 3.3. thành số ảo, trong trường hợp này, thành phần số ảo - Ta thấy thuật toán Taylor cho ước lượng khá sẽ được đưa về 0. Để tìm ma trận covariance của ước chính xác và ổn định ngay khi số BS là 3. lượng vị trí này, ta biểu diễn kết quả cuối cùng ở -Thuật toán Chan-Ho khi N=3, cho ước lượng có sai số lớn, khi N=4 thì kết quả chính xác khá dạng x x0 e và y y0 e . Từ giá trị của x y cao, khi N≥4 thì sai số ước lượng không giảm trong (2.22) ta có: nhiều. - Ta thấy khi N≥ độ chính xác hai thuật toán z' ( x 0 X ) 2 2( x 0 X ) e e 2 a,1 1 1 x x Chan-Ho và Taylor gần giống nhau. (Nhưng, ở z' ( y 0 Y ) 2 2( y 0 Y ) e e 2 (2.30) đây giá trị đầu của Taylor được lấy bằng với a,2 1 1 y y giá trị của MS, trong khi đó đối với Chan-Ho 0 thì ta không cần phải thiết lập giá trị đầu). Các lỗi ex và e y là tương đối nhỏ so với x và - Khi chỉ dùng 3 BS định vị, thì thuật toán 0 2 2 y . Ta bỏ qua ex và e y , bằng việc dùng (2.17), Taylor luôn cho kết quả tốt hơn thuật toán Chan-Ho. (2.20), (2.24) và (2.28), ma trận covariance của z p là: 1  cov(z ) B" 1 cov( z ' ) B " 1 pa4 5
6. Thuat toan Taylor -Thuật toán Friedlander chỉ ước lượng được 250 N=3 khi N=≥4, khi N tăng thì độ chính xác tăng rõ N=4 N=5 rệt hơn các phương pháp khác. N=6 200 N=7 - Khi sai số TDOA lớn thì thuật toán Taylor và Friedlander luôn cho kết quả tốt hơn thuật toán 150 Chan-Ho. RMS(m) 100 50 TÀI LIỆU THAM KHẢO 50 100 150 200 250 [1] David Munoz, Frantz Bouchereau, César E(Rtdoa) (m) Vargas, Rogerio Enriquez – Caldera. Hình 3.1 - Thuật toán Taylor "Position location techniques and applications”. Academic press (an imprint Thuat toan Chan-Hoo of Elsevier), 2009. 350 N=3 N=4 300 N=5 [2] Peter Clarke. “Cell phone positioned for N=6 N=7 new services”. Electronic Times, vol. 30, 250 no. 25, pp. 6, Jan. 20, 1997. 200 [3] Chan Y.T, Ho K.C. “A simple and efficient RMS(m) 150 estimator for hyperbolic location”. IEEE Transactions on Signal Processing, vol. 42, 100 no. 8, pp. 1905-1915, Aug 1994. 50 [4] Wade H.Foy. “Position-Location Solutions 50 100 150 200 250 by Taylor-Series Estimation”. IEEE E(Rtdoa) (m) Transactions on Aerospace and Electronic Hình 3.2 - Thuật toán Chan-Ho. Systems, vol. 12, no. 2, pp. 187-194, March 1976. Thuat toan Friedlander [5] Bertrand T.Fang. “Simple solutions for N=4 140 N=5 hyperbolic and related position ”. IEEE N=6 120 N=7 Transactions on Aerospace and Electronic Systems, vol. 26, no. 5, pp. 748-753, Sep 100 1990. 80 RMS(m) 60 40 20 50 100 150 200 250 E(Rtdoa) (m) Hình 3.3- Thuật toán Friedlander. 6
7. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam. Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh. ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN! Thực hiện theo MTCL & KHTHMTCL Năm học 2016-2017 của Thư viện Trường Đại học Sư phạm Kỹ thuật Tp. Hồ Chí Minh.