Đánh giá hiệu năng xác suất dừng mạng thông tin vệ tinh chuyển tiếp hai chiều sử dụng mã Fountain

chiều (two-way relaying) sử dụng mã Fountain. Trong mô hình nghiên cứu, hai thiết bị mặt đất truyền thông với nhau thông qua một thiết bị vệ tinh đóng vai trò là nút chuyển tiếp trung gian. Để giảm số khe thời gian truyền dữ liệu, kỹ thuật mã hoá mạng ba-pha (three-phase network coding) được áp dụng. Chúng tôi đưa ra các biểu thức tính xác suất dừng của hệ thống trên kênh truyền Shadowed-Rician. Cuối cùng, các biện luận và nhận xét cho các kết quả phân tích sẽ được trình bày nhằm nêu lên những đặc tính của hệ thống. Từ khóa—Thông tin vệ tinh, chuyển tiếp hai chiều, xác suất dừng, mã Fountain. I. GIỚI THIỆU Trong thời gian gần đây, lĩnh vực thông tin vệ tinh nhận được sự chú ý đặc biệt từ các nhà nghiên cứu trong nước và quốc tế bởi khả năng cung cấp dịch vụ cho các hệ thống cố định và di động trên mặt đất [1]. Ưu điểm của truyền thông vệ tinh là khả năng cung cấp dịch vụ với vùng bao phủ rộng, nên rất phù hợp trong những ứng dụng về quảng bá và định vị. Công nghệ vô tuyến dựa vào thông tin vệ tinh (satellite communications) có khả năng cung cấp các hình thức liên lạc cần thiết, cho phép việc thực hiện trao đổi thông tin nhanh chóng, liên tục, ổn định trong một phạm vi địa lý rất rộng và có thể được triển khai với các điều kiện địa hình phức tạp khác nhau. Liên lạc qua thông tin vệ tinh nhằm hỗ trợ việc sử dụng các công nghệ phát triển hiện có, cụ thể như mạng tế bào (cellular networks), các mạng diện rộng (wide area networks), mạng Internet, truyền hình hội nghị (video teleconferencing),. . . đang được ứng dụng rộng rãi như một nguồn thông tin quan trọng trong quá trình chia sẻ thông tin, phục vụ nhiều lĩnh vực trong đời sống, xã hội như thương mại, quân sự, y tế, giáo dục. . . Một vệ tinh sử dụng một bộ lặp (repeater) tần số vô tuyến, cung cấp như một trạm chuyển tiếp (relay station) giữa máy phát và máy thu. Để liên lạc thông qua vệ tinh, trước tiên máy phát chuyển đổi tín hiệu (dữ liệu, âm thanh, hình ảnh,. . . ) thành tín hiệu điện từ. Dữ liệu được phát đến vệ tinh sử dụng các bộ khuếch đại công suất cao hoặc thiết kế ănten để hướng tín hiệu về phía vệ tinh. Do đó, yêu cầu về độ tin cậy, ổn định, đáp ứng chất lượng dịch vụ, chia sẻ và sử dụng hiệu quả tài nguyên tần số trong liên lạc thông tin vệ tinh là rất quan trọng trong việc kết nối kênh thông tin đường lên và được xuống trong mạng. Xuất phát từ đặc điểm trên, hiện nay đã có nhiều công trình công bố liên quan đến thông tin vệ tinh ở nhiều góc độ khác nhau. Cụ thể, trong công trình [2], các tác giả đánh giá hiệu năng xác suất dừng (Outage Probability - OP) của hệ thống chuyển tiếp hai chặng thông qua vệ tinh. Cụ thể, một thiết bị mặt đất gửi dữ liệu đến một thiết bị mặt đất khác ở khoảng cách địa lý xa, nhờ vào sự chuyển tiếp của vệ tinh. Các tác giả của công trình [3] nghiên cứu hệ thống chuyển tiếp lai ghép giữa vệ tinh và mặt đất (Hybrid Satellite-Terrestrial Relay Systems), ở đây các trạm chuyển tiếp được triển khai để giúp vệ tinh chuyển tiếp dữ liệu đến đầu cuối dưới mặt đất. Trong tài liệu [4], mô hình truyền dữ liệu giữa nhiều người dùng di động và một trạm cố định mặt đất thông qua vệ tinh đã được nghiên cứu và phân tích. Tài liệu [5] giới thiệu mô hình truyền thông vệ tinh hai chiều (two-way satellite communication), trong đó vệ tinh GEO (Geostationary Earth Orbit) đóng vai trò là nút chuyển tiếp AF (Amplify-and-Forward) trung gian cho hai thiết bị mặt đất muốn gửi dữ liệu đến nhau. Thật vậy, kỹ thuật truyền thông hai chiều giúp hệ thống giảm bớt số khe thời gian truyền, do đó nâng cao tốc độ dữ liệu và giảm thời gian trễ. Các tác giả của bài báo số [6] phát triển mô hình truyền thông vệ tinh hai chiều trong [5] với các trạm mặt đất được trang bị nhiều ănten. Công trình [7] đề xuất kỹ thuật điều chế vi sai (differential modulation) ứng dụng trong chuyển tiếp hai chiều sử dụng vệ tinh. Trong công trình [8], phương pháp ước lượng kênh truyền tại các trạm mặt đất được đề xuất nhằm áp dụng hiệu quả cho mô hình chuyển tiếp vệ tinh hai chiều. Tác giả trong bài báo [9] đưa ra giải pháp truyền chùm tia (beamforming) và kỹ thuật vector kết hợp (combining vector) cho các trạm nhiều ănten tại mặt đất. Mã Fountain (Fountain Codes) [10] gần đây cũng thu hút nhiều sự quan tâm của cộng đồng nghiên cứu bởi ưu điểm dễ triển khai và thích ứng trong các điều kiện kênh truyền khác nhau. Máy phát sử dụng mã Fountain có thể phát số 152 lượng các gói tin được mã hóa không giới hạn cho đến khi máy thu nhận đủ thông tin để khôi phục dữ liệu gốc [11], [12]. Như đã được chứng minh trong công trình [12], năng lượng tiêu thụ và thời gian truyền của các mạng sử dụng mã Fountain giảm đáng kể bởi khả năng tích lũy thông tin (information accumulation) tại các đầu thu. Các tác giả trong tài liệu [13] đề xuất mô hình chuyển tiếp cộng tác sử dụng mã Fountain. Trong mô hình này, nút chuyển tiếp nào nhận đủ thông tin đầu tiên sẽ trở thành nguồn mới, và tiếp tục truyền tin về đích và các nút chuyển tiếp giữa nút này và đích. Các công trình [14], [15] nghiên cứu ứng dụng mã Fountain trong các hệ thống thông tin vệ tinh. Trong [14], các tác giả thiết kế mô hình lớp chéo (cross-layer) với mã Fountain LT (Luby Transform) và mã LDPC (Low Density Parity Check) cho các hệ thống quảng bá vệ tinh đa phương tiện. Tài liệu [15] giới thiệu hai ứng dụng của mã Fountain cho các hệ thống thông tin vệ tinh, sử dụng các thuật toán giải mã lặp mềm (soft iterative decoding algorithms). Trong bài báo này, chúng tôi đề xuất mạng thông tin vệ tinh chuyển tiếp hai chiều ba pha sử dụng mã Fountain. Trong mô hình này, hai nguồn (hai thiết bị mặt đất) gửi dữ liệu cho nhau với sự giúp đỡ của một vệ tinh. Trong hai pha đầu tiên, hai nguồn sẽ lần lượt gửi thông tin lên vệ tinh. Tiếp theo, vệ tinh sẽ kết hợp (XOR) các dữ liệu nhận được, và cùng lúc gửi dữ liệu này đến hai nguồn. Chúng tôi đánh giá hiệu năng xác suất dừng (Outage Probability - OP) của hệ thống trên kênh truyền Shadowed-Rician bằng các biểu thức toán học. Phần còn lại của bài báo được tổ chức như sau: trong phần II, chúng tôi miêu tả mô hình đề xuất và nguyên lý hoạt động của mô hình này. Trong phần III, chúng tôi đánh giá hiệu năng dừng của mô hình bằng các biểu thức toán học. Phần IV cung cấp các kết quả phân tích lý thuyết và các nhận xét, biện luận. Cuối cùng, kết luận và hướng phát triển của bài báo được đưa ra trong phần V. II. MÔ HÌNH HỆ THỐNG Hình 1, mô tả chuyển tiếp hai chiều ba pha trong thông tin vệ tinh. Trong Hình 1, hai thiết bị mặt đất S1 và S2 muốn gửi dữ liệu cho nhau. Do khoảng cách vị trí địa lý, hai nguồn này không thể gửi dữ liệu trực tiếp cho nhau, mà phải cần sự giúp đỡ của hệ thống vệ tinh (ký hiệu R trên Hình 1). Cụ thể, nguồn S1 cần gửi dữ liệu x1 đến nguồn S2, và ngược lại nguồn S2 muốn gửi dữ liệu x2 đến nguồn S1. Giả sử, các thiết bị S1; S2 và R chỉ sử dụng 01 ănten phát và thu. Theo phương thức chuyển tiếp thông thường, hệ thống phải cần 04 khe thời gian để truyền dữ liệu. Ví dụ, hai khe thời gian đầu S1 gửi x1 đến R, và R chuyển tiếp x1 đến S2. Tương tự, trong hai khe thời gian kế tiếp, S2 gửi x2 đến R, và R chuyển tiếp x2 đến S1. Như vậy, tốc độ truyền dữ liệu của hệ thống chỉ là 02/04 (hai dữ liệu trên bốn khe thời gian). Nhằm nâng cao tốc độ truyền dữ liệu, cũng như để giảm thời gian truyền, chúng tôi đề xuất sử dụng kỹ thuật chuyển tiếp hai chiều ba pha như sau: trong Hình 1. Mô hình chuyển tiếp hai chiều ba pha trong thông tin vệ tinh. khe thời gian đầu tiên, S1 gửi x1 đến R và trong khe thời gian thứ hai, S2 gửi x2 đến R. Nếu sau hai khe thời gian này, R có thể giải mã thành công cả hai dữ liệu x1 và x2; R sẽ XOR chúng lại để đạt được x = x1  x2: Kế tiếp, R sẽ quảng bá x đến cả S1 và S2 trong khe thời gian thứ ba. Nếu S1 giải mã thành công x; nút này có thể đạt được dữ liệu x2 bằng cách XOR x với chính dữ liệu của S1 : x  x1 = x2: Một cách tương tự, S2 cũng có được x1 nếu S2 giải mã thành công x: Do đó, mô hình đề xuất sẽ đạt được tốc độ truyền dữ liệu là 02/03 (hai dữ liệu trên ba khe thời gian). Xét sự truyền dữ liệu giữa S1 và R trong khe thời gian thứ nhất. Tỷ số SNR (Signal-to-Noise Ratio) giữa S1 và R được xác định như sau: S1!R = PS1 S1!R 2R =
1 S1!R; (1) với PS1 là công suất phát của S1;  2 R là phương sai của nhiễu cộng tại R;
1 = PS1= 2 R; và S1!R là độ lợi kênh Shadowed-Rician giữa S1 và R: Như đã được đưa ra trong [3], [4], hàm mật độ xác suất (PDF: Probability Density Function) của S1!R được viết ra như sau: f S1!R (x) = 1 2b1  2m1b1 2m1b1 + 1 m1 exp  x 2b1  1F1  m1; 1; 1x 2b1 (2m1b1 + 1)  : (2) Trong công thức (2), 1 là công suất trung bình của thành phần LOS (Line Of Sight), 2b1 là công suất trung bình của thành phần đa đường (multi-path), m1 là tham số đặc trưng Nakagami của kênh truyền, và 1F1 (:; :; :) là hàm confluent hypergeometric [16]. Như đã được đưa ra trong các tài liệu [12], [13], thời gian cần thiết để nút R nhận đủ lượng tin 1 để khôi phục dữ liệu gốc của S1 được xác định như sau: 153 t1 = 1 log2 (1 + S1!R) = 1 log2 (1 +
1 S1!R) : (3) Tiếp đến, ta xét khe thời gian thứ hai, ở đây S2 gửi x2 lên R: Tỷ số SNR của liên kết S2 ! R được tính như sau: S2!R = PS2 S2!R 2R =
2 S2!R; (4) với PS2 là công suất phát của S2;
2 = PS2= 2 R; và S2!R là độ lợi kênh truyền giữa S2 và R: Tương tự, hàm PDF của S2!R được viết ra như sau: f S2!R (x) = 1 2b2  2m2b2 2m2b2 + 2 m2 exp  x 2b2  1F1  m2; 1; 2x 2b2 (2m2b2 + 2)  ; (5) với 2 là công suất trung bình của thành phần LOS, 2b2 là công suất trung bình của thành phần đa đường, và m2 là tham số đặc trưng Nakagami của kênh truyền. Do đó, thời gian cần thiết để R nhận đủ lượng tin 2 nhằm khôi phục dữ liệu gốc của S2 sẽ là t2 = 2 log2 (1 + S2!R) = 2 log2 (1 +
2 S2!R) : (6) Tiếp theo, ta xét đến sự truyền dữ liệu x từ vệ tinh R đến hai trạm mặt đất S1 và S2 trong khe thời gian thứ ba. Cũng vậy, tỷ số SNR nhận được tại S1 và S2 lần lượt là R!S1 = PR R!S1 2S1 =
3 R!S1 ; R!S2 = PR R!S2 2S2 =
4 R!S2 ; (7) với PR là công suất phát của R; 2S1 và  2 S2 lần lượt là phương sai của nhiễu cộng tại S1 và S2;
3 = PR= 2 S1 ;
4 = PR= 2 S2 ; R!S1 và R!S2 lần lượt là độ lợi kênh truyền giữa R và S1; giữa R và S2: Do đó, thời gian cần thiết để S1 và S2 nhận đủ lượng tin 3 để giải mã được dữ liệu x lần lượt được viết ra như sau: t3 = 3 log2 (1 + R!S1) = 3 log2 (1 +
3 R!S1) ; t4 = 3 log2 (1 + R!S2) = 3 log2 (1 +
3 R!S2) : (8) III. XÁC SUẤT DỪNG HỆ THỐNG Trong phần này, xác suất dừng (OP) của hệ thống sẽ được định nghĩa và phân tích. Đầu tiên, ta định nghĩa xác suất dừng của sự truyền dữ liệu giữa máy phát X và máy thu Y là xác suất mà thời gian truyền giữa X và Y lớn hơn một khoảng thời gian cho phép. Với định nghĩa này, xác suất dừng của liên kết S1 ! R sẽ được viết như sau: OP1 = Pr (t1 > 1) ; (9) với 1 là thời gian trễ tối đa cho phép. Thay công thức (3) vào công thức (9), ta có: OP1 = Pr  log2 (1 +
1 S1!R) < 1 1  = Pr ( S1!R < 1) = F S1!R (1) ; (10) với 1 = 2  1 1  1
1 : (11) Trong công thức (11), F S1!R (1) là hàm phân phối tích lũy (CDF) của S1!R; và được xác định như sau: F S1!R (1) = Z 1 0 f S1!R (x) dx: (12) Thay hàm PDF của f S1!R (x) trong công thức (2) vào trong (12), và sử dụng MATHEMATICA để tính tích phân, ta sẽ đạt được giá trị của OP1. Một cách tương tự, ta có thể tính được xác suất dừng của sự truyền dữ liệu giữa S2 và R trong khe thời gian thứ hai như sau: OP2 = Pr (t2 > 2) = Pr F S2!R (2)
= Z 2 0 f S2!R (x) dx; (13) với 2 là thời gian trễ tối đa cho phép, và 2 = 2  2 2  1
2 : (14) Tuy nhiên, ta lưu ý rằng OP1 và OP2 chỉ là xác suất dừng tại R trong khe thời gian thứ nhất và thứ hai. Đối với hệ thống đề xuất, ta định nghĩa xác suất dừng của hệ thống là xác suất mà một trong hai nút S1 và S2 bị dừng, hoặc cả hai nút này bị dừng. Thật vậy, OP của hệ thống sẽ được viết ra như sau: OPht =1 Pr (t1  1) Pr (t2  2)  Pr (max (t3; t4)  3) =1 (1OP1) (1OP2)OP3; (15) Trong biểu thức (15), OP3 = Pr (max (t3; t4)  3) là xác suất mà cả hai nút S1 và S2 đều có thể giải mã thành công x; và do đó có thể đạt được x2 và x1; ở đây 3 là thời gian trễ tối đa cho phép ở khe thời gian thứ ba. Ta có thể thấy (1OP1)  (1OP2)  P3 là xác suất mà cả hai nút S1 và S2 nhận dữ liệu thành công. Vì vậy, 1 (1OP1) (1OP2)P3 sẽ là xác suất dừng của hệ thống. Bởi vì OP1 và OP2 đã được tính trong các công thức (12) và (13) nên bây giờ chúng ta chỉ tập trung tính OP3: Thực hiện một số phép biến đổi, ta có thể đạt được: OP3 = Pr (max (t3; t4)  3) = Pr (t3  3) Pr (t4  3) = [1 Pr (t3 > 3)] [1 Pr (t4 > 3)] : (16) 154 Tiếp theo, thay các công thức của (8) vào trong (16), ta đạt được: OP3 =  1 F R!S1 (3)   1 F R!S2 (3)  =  1 Z 3 0 f R!S1 (x) dx   1 Z 3 0 f R!S2 (x) dx  ; (17) với 3 = 2  3 3  1
3 : (18) IV. KẾT QUẢ LÝ THUYẾT Trong phần này, các kết quả lý thuyết sẽ được đưa ra nhằm đánh giá và phân tích xu hướng hiệu năng của hệ thống. Để dễ dàng quan sát sự biến thiên của xác xuất dừng hệ thống (OPht) ; ta có thể giả sử rằng: m1 = m2 = m3 = m4 = m; b1 = b2 = b3 = b4 = b; 1 = 2 = 3 = 4 = ;
1 =
2 =
3 =
; 1 = 2 = 3 =  và 1 = 2 = 3 = : Trong tất cả các kết quả, các tham số kênh truyền sẽ được thiết lập như sau: m = 10:1; b = 0:126 và = 0:835 [3], [6]. Chúng tôi sử dụng phần mềm máy tính MATHEMATICA để tính các giá trị của OP1; OP2 và OP3; sau đó đạt được giá trị của OPht dựa vào công thức (15). Để vẽ các kết quả, chúng tôi sử dụng phần mềm MATLAB. ∆ (dB) 0 5 10 15 20 25 OP ht 10-3 10-2 10-1 100 τ = 0.5 τ = 1 τ = 1.5 Hình 2. Xác suất dừng hệ thống vẽ theo
(dB) khi  = 1. Hình 2 vẽ xác suất dừng hệ thống OPht theo giá trị của
(dB) khi  = 1. Ta có thể thấy rằng xác suất dừng giảm khi tăng
(hay tăng công suất phát). Hơn nữa, khi thời gian trễ tối đa  càng thấp thì OPht càng lớn. Vậy nên, khả năng giải mã thành công dữ liệu của các thiết bị đầu cuối phụ thuộc rất lớn vào thời gian trễ cho phép và công ∆ (dB) 0 5 10 15 20 25 OP ht 10-3 10-2 10-1 100 χ = 1 χ = 1.5 χ = 2 Hình 3. Xác suất dừng hệ thống vẽ theo
(dB) khi  = 1. suất phát của toàn hệ thống. Do đó, để bảo đảm yêu cầu chất lượng dịch vụ và tốc độ truyền dữ liệu thì hệ thống nên được thiết kế có độ trễ phù hợp, cũng như tăng công suất phát. Hình 3 vẽ xác suất dừng hệ thống OPht theo giá trị của
(dB) khi  = 1. Tương tự như Hình 2, ta nhận thấy rằng OPht giảm khi công suất phát của các thiết bị tăng. Hơn nữa, khi lượng tin cần thiết để khôi phục dữ liệu gốc  càng lớn thì xác suất dừng hệ thống càng lớn. Vậy nên, hiệu năng hệ thống phụ thuộc vào số lượng gói mã hóa nhận được yêu cầu tại máy thu, do đó, cần phải thiết kế hệ thống phù hợp bảo đảm độ tin cậy và khả năng giải mã thành công dữ liệu gốc. V. KẾT LUẬN Trong bài báo này, chúng tôi đề xuất và đánh giá hiệu năng của hệ thống chuyển tiếp hai chiều trong thông tin vệ tinh, thông qua thông số xác suất dừng hệ thống. Việc áp dụng kỹ thuật chuyển tiếp hai chiều ba pha sẽ giúp hệ thống giảm thời gian truyền, và do đó có thể nâng cao tốc độ truyền dẫn. Hơn nữa, tồn tại một sự đánh đổi về tốc độ truyền dẫn và chất lượng dịch vụ của toàn hệ thống. Do đó, để bảo đảm hiệu năng của hệ thống truyền dẫn thì cần thiết kế hệ thống có độ trễ và số gói mã hóa yêu cầu nhận được tại máy thu một cách thích hợp để có thể giải mã thành công dữ liệu gốc. Trong tương lai, chúng tôi sẽ tiếp tục phát triển mô hình hệ thống trong bài báo với các trạm mặt đất được trang bị với nhiều ănten, và đánh giá các hiệu năng khác của hệ thống như tỷ lệ lỗi bít, dung lượng kênh trung bình, v.v. LỜI CẢM ƠN Nghiên cứu này được tài trợ bởi Học viện Công nghệ Bưu chính Viễn thông cơ sở tại thành phố Hồ Chí Minh 155 năm 2019 với mã số 05-HV-2019-RD_VT2. TÀI LIỆU THAM KHẢO [1] B. Evans, M. Werner, E. Lutz, M. Bousquet, G. E. Corazza, G. Maral, and R. Rumeau, “Integration of satellite and terrestrial systems in future multimedia communications,” IEEE Wireless Com- mun., vol. 12, no. 5, pp. 72–80, Oct. 2005. [2] K. Guo, D. Guo, Y. Huang, X. Wang, and B. Zhang, “Performance analysis of a dual-hop satellite relay network with hardware im- pairments,” in Proc. of 25th Wireless and Optical Communication Conference (WOCC), Chengdu, China, May 2016, pp. 1–5. [3] H. Wu, Y. Zou, W. Cao, Z. Chen, T. A. Tsiftsis, M. R. R. Bhatnagar, and R. C. De Lamare, “Impact of hardware impairments on outage performance of hybrid satellite-terrestrial relay systems,” IEEE Access, vol. 7, p. 35103 – 35112, Mar. 2019. [4] X. Wu, M. Lin, H. Kong, Q. Huang, J.-Y. Wang, and P. K. Upadhyay, “Outage performance for multiuser threshold-based df satellite relaying,” IEEE Access, vol. 7, pp. 103 142 – 103 152, Jul. 2019. [5] B. Ji, Y. Huang, H. Wang, and L. Yang, “Performance analysis of two-way relaying satellite mobile communication,” in Proc. of 6th International ICST Conference on Communications and Networking in China (CHINACOM), Harbin, China, Aug. 2011, p. 1099 – 1103. [6] M. K. Arti and M. R. Bhatnagar, “Making two-way satellite relaying feasible: A differential modulation based approach,” IEEE Commun. Lett., vol. 18, no. 7, p. 1187 – 1190, Jul. 2014. [7] M. R. Bhatnagar, “Making two-way satellite relaying feasible: A differential modulation based approach,” IEEE Trans. Commun., vol. 63, no. 8, pp. 2836 – 2847, Aug. 2015. [8] M. K. Arti, “Two-way satellite relaying with estimated channel gains,” IEEE Trans. Commun., vol. 64, no. 7, p. 2808 – 2820, Jul. 2016. [9] ——, “A novel beamforming and combining scheme for two-way af satellite systems,” IEEE Trans. Veh. Technol., vol. 66, no. 2, pp. 1248 – 1256, Feb. 2017. [10] D. J. C. MacKay, “Fountain codes,” IEE Proceedings - Communi- cations, vol. 152, no. 6, pp. 1062–1068, Dec. 2005. [11] J. Castura and Y. Mao, “Rateless coding for wireless relay channels,” IEEE Trans. Wireless Commun., vol. 6, no. 5, pp. 1638–1642, May 2007. [12] A. F. Molisch, N. B. Mehta, J. S. Yedidia, and J. Zhang, “Per- formance of fountain codes in collaborative relay networks,” IEEE Trans. Wireless Commun., vol. 6, no. 11, pp. 4108 – 4119, Nov. 2007. [13] T. T. Duy, A. Anpalagan, and H. Y. Kong, “Multi-hop cooperative transmission using fountain codes over rayleigh fading channels,” J. Commun. Networks, vol. 14, no. 3, pp. 267–272, Jun. 2012. [14] W. Zhenbang, W. Zhenyong, G. Xuemai, and G. Qing, “Cross-layer design of lt codes and ldpc codes for satellite multimedia broad- cast/multicast services,” Chinese Journal of Aeronautics, vol. 26, no. 5, pp. 1269–1275, Oct. 2013. [15] M. Zhang, S. Chan, and S. Kim, “Soft iterative decoding algorithms for rateless codes in satellite systems,” Algorithms, vol. 12, no. 8, (151), Jul. 2019. [16] I. S. Gradshteyn and I. M. Ryzhik, “Table of Intergals,” Series, and Products. 7th ed. Academic Press, 2007. 156 Phân tích dữ liệu số chiều lớn bằng một số phương pháp học máy Vũ Việt Vũ Viện Công nghệ Thông tin, Đại học Quốc gia Hà Nội Hà Nội, Việt Nam vuvietvu@vnu.edu.vn Lê Thị Kiều Oanh Khoa Công nghệ Thông tin Trường Đại học Kinh tế - Kỹ thuật Công nghiệp, Hà Nội, Việt Nam ltkoanh@uneti.edu.vn Abstract—Dữ liệu số chiều lớn luôn là một thách thức trong quá trình xử lý đối với các thuật toán trong khai phá dữ liệu và phát hiện tri thức về dữ liệu. Với sự bùng nổ về Internet và các hệ thống sinh dữ liệu như mạng xã hội, báo chí, văn bản dữ liệu mới được sinh ra hàng ngày là rất lớn. Hơn nữa những loại dữ liệu này thường phi cấu trúc, số chiều lớn đòi hỏi phải có các thuật toán hiệu quả để xử lý. Trong nghiên cứu này, chúng tôi tập trung vào thử nghiệm phân tích các bộ dữ liệu số chiều lớn hay gặp trên thực tế (KDD’99, Dữ liệu văn bản) bằng các thuật toán học máy cơ bản như: K-Means, DBSCAN, hay Support Vector Machine. Kết quả thực nghiệm sẽ là tiền đề cho các nghiên cứu tiếp theo và sâu hơn về lĩnh vực khai phá và phân tích dữ liệu với số chiều lớn. Keywords—phân cụm, K-Means, DBSCAN, phân tích dữ liêu, dữ liệu số chiều lớn. I. GIỚI THIỆU Công nghệ thông tin hiện này là một trong các lĩnh vực chủ chốt quyết định đến sự phát triển kinh tế xã hội của mỗi quốc gia. Sự hiện diện của CNTT trong rất nhiều các lĩnh vực đã đem lại những hiệu quả rất lớn. Cuộc cách mạng công nghiệp lần thứ 4 đang diễn ra mạnh mẽ cũng chính là cuộc cách mạng liên qua đến CNTT với các trụ cột nghiên cứu là Trí tuệ nhân tạo, dữ liệu lớn và Internet vạn vật (IoT). Tại Việt nam hiện nay nghiên cứu về ứng dụng CNTT, Trí tuệ nhân tạo cũng như các hệ thống xử lý dữ liệu đang rất sôi động thu hút một lượng lớn các nhà nghiên cứu, các chuyên gia, các kỹ sư về CNTT. Hàng loạt những ứng dụng CNTT ra đời như các hệ thống khai phá dữ liệu phục vụ trong y tế, các hệ thống giám sát an ninh mạng, camera thông minh, các hệ thống khai phá dữ liệu văn bản cũng như phân tích dữ liệu đã cho thấy tầm quan trọng của việc nghiên cứu và ứng dụng công nghệ thông tin. Trong bài báo này chúng tôi sẽ nghiên cứu thực nghiệm một số tập dữ liệu số chiều lớn sử dụng thuật học máy cơ bản như K-Means [1,2], DBSCAN [3], hay Support Vector Machine (SVM) [4,7]. Loại dữ liệu thứ nhất chúng tôi sử dụng là dữ liệu kiểu văn bản, đây là loại dữ liệu phi cấu trúc, cần biến đổi sang dạng vector số (sử dụng BoW, TF-IDF), dữ liệu thứ hai chúng tôi sử dụng là dữ liệu trong bài toán phát hiện tấn công mạng KDD’991. Cả hai loại dữ liệu này đều có nhiều ứng dụng trong thực tiễn trong lĩnh vực khai phá dữ liệu và phát hiện tri thức cũng như trong bài toán an ninh mạng. Dữ liệu số chiều lớn trong một số nghiên cứu hiểu là dữ liệu có số lượng thuộc tính lớn hơn khoảng 20 [3]. Phần tiếp theo của bài báo được trình bày như sau: phần II trình bày một số thuật toán học máy cơ bản, phần III trình bày kết quả thực nghiệm và cuối cùng phần IV là kết luận của bài báo. II. MỘT SỐ THUẬT TOÁN HỌC MÁY CƠ BẢN Học máy là một lĩnh vực rất quan trọng của Trí tuệ nhân tạo. Các thuật toán học máy được phát triển nhằm mục đích học được từ các dữ liệu mẫu thu được bằng thực nghiệm. Học máy có các dạng cơ bản như học có giám sát, học không giám sát, học bán giám sát, học tăng cường. Hai dạng cơ bản nhất là học có giám sát và học không giám sát. Học có giám sát cần phải có tập mẫu để xây dựng mô hình học cho các bài toán dự đoán, phân lớp, nhận dạng, Trong khi học không giám sát chỉ dựa vào tập dữ liệu cho bởi người sử dụng để phân tích cấu trúc, phân cụm, phát hiện dị thường, Trong phần tiếp theo chúng tôi sẽ trình bày hai thuật toán không giám sát cơ bản là K-Means và DBSCAN và một thuật toán học có giám sát là Support Vector Machine. II.1 Thuật toán phân cụm K-Means Thuật toán K-Means là một trong những thuật toán ra đời sớm nhất và được được xếp hạng một trong mười thuật toán hiệu quả và được dùng nhiều nhất trong lĩnh vực khai phá dữ liệu và phát hiện tri thức từ dữ liệu [1]. Ý tưởng cơ bản của thuật toán như sau: với tập dữ liệu với n điểm và số cụm k cho trước, sử dụng một hàm độ đo khoảng cách, thuật toán sẽ chia các điểm vào k cụm sao cho hàm mục tiêu F sau đây đạt giá trị nhỏ nhất: 1 https://archive.ics.uci.edu/ml/index.php 157  p      k j n i j j i cxF 1 1 2 Trong công thức trên cj là trọng tâm của cụm thứ j. Thuật toán 1: Thuật toán K-Means; Input: Tập dữ liệu X = {x1, x2,,xn}, xiR n, số lượng cụm k, Output: k cụm của X Begin - Lấy ngẫu nhiên k trọng tâm từ tập dữ liệu X Repeat - Gán mỗi điểm x X vào cụm gần nó nhất - Tính toán lại các trọng tâm cjcủa mỗi cụm: Until (Hàm F hội tụ - các trọng tâm của cụm không thay đổi được nữa) End; Độ phức tạp của thuật toán K-Means là O(n.k) trong đó n là số điểm của dữ liệu và k là số cụm của dữ liệu. Đây là thuật toán hiệu quả vì có độ phức tạp nhỏ.Tuy nhiên hạn chế của thuật toán K-Means là chất lượng phân cụm sẽ phụ thuộc vào việc lựa chọn k trọng tâm đầu tiên cũng như thuật toán K- Means chỉ tìm được các cụm có dạng hình cầu. II.2 Thuật toán phân cụm DBSCAN Một trong những thuật toán thu hút được nhiều nhà nghiên cứu (có lẽ chỉ sau thuật toán K-Means) quan tâm trong khoảng 20 năm trở lại đây là thuật toán phân cụm dựa trên mật độcó tên DBSCAN [3]. Thuật toán được đề xuất năm 1996 bởi giáo sư Ester và các cộng sự. Thuật toán DBSCAN có khả năng phát hiện được các cụm có hình dạng bất kỳ và khả năng phát hiện dị thường sau quá trình phân cụm. Hình 1. Ví dụ về điểm lõi p với MinPts = 5 Thuật toán DBSCAN dựa trên ý tưởng cơ sở sau đây: mỗi cụm sẽ gồm các điểm dữ liệu có mật độ cao và phân tách giữa các cụm là các vùng có mật độ thấp. Thuật toán DBSCAN sử dụng hai tham số là MinPts và . DBSCAN đưa ra khái niệm điểm lõi (core) như sau: với một điểm dữ liệu p bất kỳ, p được gọi là điểm lõi nếu trong siêu cầu có tâm là p với bán kính  có ít nhất MinPts điểm dữ liệu (xem hình 1). Với định nghĩa điểm lõi như trên, quá trình xây dựng một cụm của thuật toán DBSCAN sẽ là sự kết nối liên tục của các siêu cầu mới được tạo nên từ các điểm nằm trong siêu cầu cũ và phải chứa các điểm lõi. Quá trình xây dựng các cụm sẽ dừng lại cho đến khi không tìm thêm được siêu cầu mới nào nữa. Khi đó ta sẽ thu được các điểm thuộc cùng một cụm và sẽ gán nhãn cho chúng. Chú ý rằng sẽ còn một số điểm dữ liệu không thuộc cụm nào và cũng phải là điểm lõi, các điểm này gọi là các điểm dị thường của dữ liệu. Độ phức tạp của thuật toán DBSCAN là O(n2) hoặc O(nlogn) trong trường hợp dự liệu có số chiều nhỏ. Thuật toán DBSCAN sử dụng hai tham số MinPts và ; hai thuật toán này trên thực tế được lựa chọn dựa trên tập dữ liệu được phân cụm. Hình 2 minh họa quá trình tìm kiếm các cụm của thuật toán DBSCAN. Hình 2. Quá trình xây dựng các cụm của thuật toán DBSCAN II.3 Thuật toán phân lớp Support Vector Machine Support Vector Machine (SVM), được nghiên cứu và giới thiệu bởi Vapnik năm 1995 [4], là một phương pháp học có giám sát dựa trên lý thuyết thống kê sử dụng cho bài toán phân lớp và nhận dạng đối tượng. Ý tưởng cơ bản của thuật toán như sau: cho một tập huấn luyện được biểu diễn trong không gian d chiều {x1, x2, , xn}, không mất tính tổng quát, xét bài toán 2 lớp, mỗi phần tử dữ liệu xi sẽ thuộc về một trong hai lớp kí hiệu là +1 hoặc -1. Phương pháp SVM sẽ tìm ra một siêu phẳng tốt nhất để có thể chia các điểm trên không gian này thành hai lớp riêng biệt tương ứng lớp +1 và lớp -1. Với dữ liệu huấn luyện trong không gian d chiều thì hàm biểu diễn siêu phẳng sẽ là một đa thức d biến. Chúng ta sẽ lần lượt nghiên cứu các trường hợp cơ bản của phương pháp SVM trong các mục tiếp theo sau đây. a) Trường hợp dữ liệu có thể phân tách tuyến tính Hình 3. Dữ liệu huấn luyện phân tách tuyến tính wx+b>0 wx+b<0 wx+b=0 wx+b>0 wx+b<0 wx+b=0 158 Trường hợp đơn giản nhất đối với phương pháp SVM là khi dữ liệu huấn luyện có thể phân tách tuyến tính tức là giữa hai lớp bất kỳ luôn tồn tại siêu phẳng phân tách sao cho dữ liệu ở mỗi lớp sẽ nằm về một phía của siêu phẳng đó (xem hình 3). Với tập dữ liệu huấn luyện X, giả sử tồn tại một siêu mặt phẳng phân tách các dữ liệu mẫu thành hai loại +1 và -1. Điểm x (trong không gian d chiều) nằm trên siêu mặt thỏa mãn w. x + b = 0, trong đó w là pháp tuyến của siêu mặt, |b|/ ||w|| là khoảng cách từ siêu mặt đến gốc toạ độ, và ||w|| là độ lớn (theo khoảng cách Ơcơlit) của w. Đặt (d+) và (d_) là khoảng cách ngắn nhất tương ứng từ siêu mặt phân cách đến điểm mẫu dương và mẫu âm gần nhất. Định nghĩa lề (margin) của siêu phẳng phân cách (kí hiệu là r) là d+ và d_. Rõ ràng với một tập dữ liệu phân tách tuyến tính sẽ tồn tại nhiều siêu phẳng thỏa mãn yêu cầu, mục tiêu của thuật toán SVM là sẽ tìm siêu mặt có khoảng cách lề là cực đại. Hình 4. Siêu mặt phân tách tuyến tính Chúng ta có thể mô hình hóa ý tưởng trên đây bằng toán học như sau: Giả sử mọi điểm trong tập mẫu thỏa các ràng buộc: xiw + b ≥ + 1 với yi = + 1 (1) và xiw + b ≤ - 1 với yi = - 1 (2) Kết hợp hai bất đẳng thức (1) và (2) thành một bất đẳng thức ràng buộc như sau: yi(xiw + b) – 1 ≥ 0  i (3) Các mẫu dữ liệu thỏa mãn công thức (1) nằm trên siêu mặt H1: xiw + b =1 có vector pháp tuyến là w, và khoảng cách đến gốc tọa độ là |1 − b|/||w||. Tương tự, các mẫu thỏa mãn công thức (2) nằm trên siêu phẳng H2: xiw + b = - 1, có pháp tuyến là w và khoảng cách đến gốc tọa độ là |-1 - b|/ ||w||. Khi đó, d+ = d_ = 1 / ||w|| và độ lớn của lề là r =2 /||w||. Chú ý rằng H1 và H2 song song với nhau và không có điểm dữ liệu nào nằm giữa chúng. Vì vậy, ta có thể tìm cặp siêu phẳng có lề là cực đại, bằng việc cực tiểu hóa ||w|| với ràng buộc (3). Những điểm huấn luyện thoả mãn phương trình (3) (tức những điểm nằm trên một trong hai siêu mặt H1, H2), và việc loại bỏ chúng sẽ làm thay đổi lời giải, được gọi là các vector hỗ trợ, đó là các điểm được bao bằng các hình tròn trong hình 4 và kí hiệu các support vector (các điểm được bao bằng viền tròn). Việc tìm siêu mặt sẽ tương ứng với việc giải bài toán sau: min P(w,b)= 2 1 w 2 (4) (w ( ) ) 1i iy x b    (5) Sử dụng phương pháp Lagrange, bài toán trên chuyển về việc tìm các điểm yên ngựa của hàm sau:        n i iii bxwywbwL 1 2 1. 2 1 ,,  (6) với i là các hệ số Lagrange. Phương trình trên trở thành cực đại L(w, b, ) với i  0 với mọi i. Lấy vi phân từng phần của L ta có: 1 ( , , ) 0 n i i i i L y x              (7) 1 ( , , ) 0 n i i i L y b        