Tổng quan luận án

Luận án tiến sĩ kỹ thuật với đề tài "Phát triển thuật toán dự đoán vị trí của thuê bao di động theo tiếp cận khai phá dữ liệu" do nghiên cứu sinh Giang Minh Đức thực hiện năm 2017 tại Trường Đại học Bách Khoa – Đại học Quốc gia Thành phố Hồ Chí Minh, thuộc chuyên ngành Kỹ thuật Điện tử (mã số: 62.01), dưới sự hướng dẫn khoa học của PGS. TS. Đỗ Hồng Tuấn và TS. Lê Mạnh.

Tính cấp thiết và khoảng trống nghiên cứu

Trong mạng truyền thông tế bào, việc quản lý di chuyển của người sử dụng thiết bị di động (Mobile Users - MUs) bao gồm các quy trình lưu trữ và cập nhật thông tin vị trí vào thanh ghi định vị tạm trú (VLR) và thanh ghi định vị thường trú (HLR). Dự báo trước đường đi được xác định là quá trình dự đoán một thuê bao di động sẽ di chuyển tới trạm tế bào (cell) nào tiếp theo trong vùng phủ sóng. Khả năng dự báo vị trí đóng vai trò thiết yếu để các nhà mạng cấp phát tài nguyên vô tuyến hợp lý, điều chỉnh băng thông tự động, thực hiện chuyển giao cuộc gọi thông minh (smart handover), phát triển dịch vụ dựa trên vị trí (Location Based Services - LBS) và giảm tỷ lệ rớt cuộc gọi (Call Dropping Probability - CDP).

Tuy nhiên, các ứng dụng quản lý tài nguyên và chuyển giao trên mạng đòi hỏi thời gian xử lý của các thuật toán khai phá mẫu di chuyển phải diễn ra tức thời. Thuật toán nền tảng UMPMining được Gokhan Yavas và các cộng sự đề xuất năm 2005 tồn tại hạn chế lớn về thời gian thực thi do độ phức tạp tính toán cao và số lượng tập ứng viên sinh ra quá lớn. Ngoài ra, các phương pháp khai phá truyền thống thường xử lý dữ liệu ngoại tuyến (offline) và phải quét lại toàn bộ cơ sở dữ liệu khi có dữ liệu mới phát sinh. Do đó, yêu cầu cấp thiết được đặt ra là phải phát triển các thuật toán khai phá mẫu di chuyển có thời gian xử lý nhanh, hỗ trợ xử lý tăng cường trực tuyến (online) và nâng cao độ chính xác dự báo.

Mục tiêu nghiên cứu

Luận án xác định 3 mục tiêu nghiên cứu cụ thể như sau:

  1. Cải tiến thuật toán UMPMining nhằm giảm độ phức tạp tính toán và giảm thời gian thực thi của thuật toán.
  2. Phát triển giải thuật khai phá tăng cường (UMP_Online) nhằm xử lý dữ liệu mới cập nhật mà không cần quét lại toàn bộ cơ sở dữ liệu.
  3. Nâng cao độ chính xác của thuật toán dự báo trước vị trí di chuyển của thuê bao di động.

Phạm vi và đối tượng nghiên cứu

  • Đối tượng nghiên cứu: Đường đi thực tế của thuê bao di động (User Actual Paths - UAPs), mẫu di chuyển của thuê bao (User Mobility Patterns - UMPs), luật di chuyển (Mobility Rules) và các thuật toán khai phá luật kết hợp/chuỗi tuần tự áp dụng trên cấu trúc mạng tế bào.
  • Phạm vi không gian và dữ liệu: Mô hình vùng phủ sóng mạng di động tế bào bao gồm 351 trạm thu phát sóng (BTS/cell). Dữ liệu thực nghiệm được trích xuất từ tệp nhật ký (log file) của thanh ghi HLR thuộc Trung tâm chuyển mạch di động (MSC). Tập dữ liệu thô ban đầu gồm 1.179.034 đường đi thực tế, sau quy trình chuẩn hóa và lọc sạch thu được 56.198 bản ghi đường đi hợp lệ.
  • Phạm vi thời gian: Dữ liệu nhật ký cuộc gọi thực tế được ghi nhận theo từng mốc thời gian xác định, phục vụ phân tích quy luật di chuyển theo các chu kỳ trong ngày (sáng, chiều, tối).

Tổng quan tài liệu và vị trí của luận án

Các hướng nghiên cứu liên quan

Luận án tiến hành tổng thuật các công trình nghiên cứu trong và ngoài nước liên quan đến quản lý di chuyển và dự báo vị trí thuê bao di động:

  1. Hướng cập nhật vị trí và lưu vết: Các nghiên cứu của tác giả khác tập trung vào cơ chế cập nhật vị trí mỗi khi thuê bao di chuyển qua biên giới giữa các cell để định tuyến cuộc gọi đến vị trí gần nhất của thuê bao. Nhóm nghiên cứu này chỉ giải quyết việc lưu vết vị trí trong quá khứ mà không cung cấp giải pháp dự báo vị trí tương lai.
  2. Hướng khai phá mẫu tuần tự và thuật toán Apriori: Các nghiên cứu của Agrawal và Srikant về khai phá mẫu tuần tự giả định thuê bao di chuyển tự do giữa các cell, hoặc ứng dụng Apriori trong tính toán lưới và dự báo truy cập web. Điểm yếu của hướng tiếp cận này là không xem xét cấu trúc hình học (topology) của mạng tế bào, trong khi trên thực tế thuê bao chỉ có thể di chuyển trực tiếp giữa các cell lân cận có chung đường biên.
  3. Hướng mô hình học có giám sát trên dữ liệu mạng xã hội: Nghiên cứu của Anastasios Noulas áp dụng hồi quy tuyến tính và cây mô hình M5 trên dữ liệu "check-in" của dịch vụ Foursquare. Nghiên cứu của M. Mohamed Imran đề xuất thuật toán LB-SNAS kết hợp dữ liệu Twitter và Foursquare API để quảng cáo theo vị trí. Luận án chỉ ra các phương pháp này không thể áp dụng cho mạng di động tế bào vì người dùng Foursquare có thể check-in tại bất kỳ điểm nào trên thế giới, trong khi thuê bao di động bị ràng buộc bởi 6 cell lân cận bao quanh cell hiện tại.
  4. Hướng khai phá không gian - thời gian trong mạng không dây cục bộ: Thuy Van T. Duong và cộng sự nghiên cứu khai phá dữ liệu không gian - thời gian kết hợp gom cụm và khai phá chuỗi tuần tự để giảm trễ chuyển giao giữa các điểm truy cập (Access Point - AP) chuẩn IEEE 802.11 WLAN. Tuy nhiên, tập dữ liệu và đặc tính vô tuyến tại các nút di động WLAN khác biệt so với mạng viễn thông tế bào.
  5. Hướng mô hình Markov và phân chia ô sóng: Mohammad Sh. Daoud đề xuất thuật toán phân chia cell thành 8 sector (NCPA) và thuật toán tối ưu đàn kiến (ACO) dựa trên chuỗi Markov (MCM) trên mạng 3G/UMTS. Tuy nhiên, phương pháp chưa làm rõ cách thức lưu trữ và cập nhật việc phân chia này vào cơ sở dữ liệu thực tế của mạng.
  6. Thuật toán UMPMining và tính toán lưới: Gokhan Yavas và cộng sự (2005) đề xuất thuật toán UMPMining khai thác mẫu di chuyển tuần tự có xét đến topology mạng tế bào. Yavas đã đối sánh với hai phương pháp:
    • Phương pháp Ignorant Prediction: Chọn ngẫu nhiên $m$ cell lân cận, độ chính xác chỉ đạt khoảng 20%.
    • Phương pháp Mobility Prediction based on Transition Matrix (TM): Tính toán xác suất chuyển tiếp giữa các cell ghi vào ma trận, độ chính xác đạt khoảng 52%.
    • Thuật toán UMPMining của Yavas đạt độ chính xác khoảng 70%. Để giải quyết tốc độ của UMPMining, Sakthi và cộng sự đề xuất giải thuật KMPM trên nền tảng lưới dữ liệu Globus Toolkit 4, khi tăng số nút tính toán lên 8 thì thời gian thực hiện giảm 45%. Hạn chế của hướng này là đòi hỏi đầu tư hạ tầng phần cứng tính toán lưới tốn kém.

Bảng tổng hợp đối sánh độ chính xác của các phương pháp dự báo di chuyển theo thống kê của Mira H. Gohil (2013) được luận án trích dẫn như sau:

Phương pháp tiếp cận Năm Tác giả công trình Tập dữ liệu sử dụng Độ chính xác
Markov Model 2013 Jorge Alvarez-Lozano Đường đi của 178 thuê bao (thu thập > 4 năm) 30%
Neural Network 2012 Velmurugan L. Thu thập từ Trường Cao đẳng Dartmouth 78,50%
Neural Network 2012 Vincent Etter Nokia MDC Dataset 56,22%
Neural Network 2013 Smita Parija Không xác định 0,84%
Artificial Intelligence 2012 Jingjing Wang Nokia MDC Dataset 50%
Fuzzy Logic 2012 Ying Zhu Nokia MDC Dataset 72%
Data Mining 2005 Gokhan Yavas Dữ liệu một người dùng (Single user data) 70%
Data Mining 2012 Thuy Van T. Duong Tập dữ liệu tự thu thập (Own Dataset) 70%
Data Mining 2013 Joao Bartolo Nokia MDC Dataset 17%

Khoảng trống luận án lựa chọn giải quyết

Luận án tập trung giải quyết các khoảng trống kỹ thuật cốt lõi:

  • Giảm độ phức tạp tính toán và kích thước không gian tìm kiếm tập ứng viên trong thuật toán UMPMining mà không làm giảm tập mẫu phổ biến tìm được.
  • Xây dựng giải thuật xử lý tăng cường để cập nhật các giao tác mới vào cơ sở tri thức theo thời gian thực mà không phải quét lại dữ liệu lịch sử.
  • Khắc phục tình trạng suy giảm độ chính xác dự báo khi phân bố di chuyển thay đổi theo các thời điểm khác nhau trong ngày bằng kỹ thuật phân lớp dữ liệu thời gian.

Cơ sở lý thuyết và phương pháp nghiên cứu

Cơ sở lý thuyết và khung phân tích

Luận án sử dụng các khái niệm và công cụ hình thức sau:

  • Ngữ cảnh khai phá dữ liệu: Được định nghĩa bằng bộ ba $(O, I, R)$, trong đó $O$ là tập hợp các giao tác (đường đi thực tế UAP của thuê bao di động), $I$ là tập hợp các trạm tế bào (cell) trong mạng, và $R$ là quan hệ hai ngôi giữa $O$ và $I$.

  • Khái niệm hình thức và dàn tập cell: $B(O, I, R)$ là tập các khái niệm hình thức được sinh từ ngữ cảnh; $(P(I), \subseteq)$ là dàn các tập cell; $v(S)$ là vector biểu diễn tập cell $S$; $v(S) \cdot v(T)$ là tích vector biểu diễn giữa hai tập cell; $SPV(v(S))$ là độ phổ biến của vector biểu diễn.

  • Mô hình hóa topology mạng: Vùng phủ sóng mạng tế bào được ánh xạ thành đồ thị có hướng không trọng số $G = (V, E)$, trong đó mỗi đỉnh $v \in V$ đại diện cho một trạm BTS/cell, và mỗi cạnh nối $(u, v) \in E$ thể hiện hai cell có chung đường biên phủ sóng. Đồ thị $G$ được cài đặt trong máy tính dưới dạng ma trận kề kích thước $351 \times 351$.

  • Độ ủng hộ (Support) và khoảng cách vị trí: Để xác định tần suất xuất hiện của chuỗi mẫu $B$ trong đường đi $A$, thuật toán sử dụng hàm tăng độ ủng hộ có trọng số nghịch đảo khoảng cách:

    $$\text{suppInc} = \begin{cases} \dfrac{1}{1 + \text{totDist}} & \text{nếu } B \subseteq A \ 0 & \text{ngược lại} \end{cases}$$

    Trong đó, $\text{totDist}$ biểu thị tổng khoảng cách giữa các cell thành phần của mẫu trong chuỗi đường đi thực tế:

    $$\text{totDist} = \sum_{k=2}^{i} [(\text{vị trí } c_k - \text{vị trí } c_{k-1}) - 1]$$

  • Độ tin cậy của luật di chuyển (Confidence): Với một luật di chuyển dạng $R: (c_1, c_2, \dots, c_{i-1}) \to (c_i, c_{i+1}, \dots, c_k)$, hệ số tin cậy được tính bằng:

    $$\text{Confidence}(R) = \dfrac{\text{count}(c_1, c_2, \dots, c_k)}{\text{count}(c_1, c_2, \dots, c_{i-1})}$$

Phương pháp nghiên cứu

  • Phương pháp phân tích lý thuyết: Phân tích thuật toán khai phá mẫu tuần tự UMPMining, áp dụng lý thuyết đại số tập hợp và lý thuyết đồ thị để tái cấu trúc ma trận kề thành ma trận đường đi ($M_{dd}$) và ma trận nhị phân.
  • Phương pháp thực nghiệm định lượng: Xây dựng phần mềm cài đặt các thuật toán đề xuất, chạy thử nghiệm trên cơ sở dữ liệu trích xuất từ mạng thực tế, thu thập số liệu về số lượng ứng viên ($C_k$), số lượng mẫu phổ biến ($L_k$), thời gian thực thi, bộ nhớ sử dụng, hệ số Recall và độ chính xác Precision.

Nguồn tư liệu và dữ liệu

Dữ liệu đầu vào là file text log lấy từ thanh ghi định vị thường trú HLR của tổng đài MSC. Mỗi dòng bản ghi chứa các trường thông tin: số thứ tự, số chủ gọi, số bị gọi, ngày gọi, giờ gọi, thời lượng cuộc gọi, mã bộ điều khiển trạm gốc (BSC), mã trạm thu phát gốc (BTS). File danh mục trạm BTS (ds_BTS) cung cấp bảng ánh xạ giữa số hiệu BTS và mã định danh cell khu vực.

Nội dung chính theo từng chương

CHƯƠNG 1: TỔNG QUAN

Chương 1 giới thiệu lịch sử phát triển của các thế hệ thông tin di động tế bào từ 1G đến 5G, cấu trúc hệ thống mạng 3G (gồm BSS, UTRAN, MSC, SGSN, GGSN, HLR, VLR) và đặt vấn đề về quản lý tính di động của người dùng trong môi trường tính toán di động. Tác giả phân tích bảng so sánh đặc tính kỹ thuật giữa mạng 4G và 5G:

Kỹ thuật / đặc tính Mạng 4G Mạng 5G
Bắt đầu / Triển khai 2010 / 2015 2015 / 2020
Băng thông dữ liệu 200 Mbps – 1 Gbps $\ge$ 1 Gbps (dải tần 3 – 300 GHz)
Tiêu chuẩn Single unified standard Single unified standard
Kỹ thuật mạng Unified IP, kết hợp LAN/WAN/PAN/WLAN Unified IP, kết hợp LAN/WAN/PAN/WLAN và www
Dịch vụ Dynamic information access, thiết bị đeo AI Dynamic information access, thiết bị đeo AI
Điều chế CDMA CDMA
Chuyển mạch Toàn bộ gói (All packet) Toàn bộ gói (All packet)
Mạng lõi Internet Internet
Chuyển giao (Handoff) Horizontal and Vertical Horizontal and Vertical

Chương này trình bày các ứng dụng then chốt của việc dự báo trước vị trí thuê bao di động: tối ưu hóa việc phân bổ tài nguyên, điều chỉnh băng thông cho các dịch vụ đa phương tiện thời gian thực, giảm xác suất rớt cuộc gọi CDP và giảm chuyển giao không cần thiết trong mạng Macro/Femto-cell. Tác giả phân tích điểm mạnh và điểm yếu của các công trình liên quan trên thế giới, xác định mục tiêu nghiên cứu, phạm vi đề tài và cấu trúc 5 chương của luận án.

CHƯƠNG 2: MÔ HÌNH DỰ BÁO TRƯỚC VỊ TRÍ CỦA THUÊ BAO DI ĐỘNG THEO TIẾP CẬN KHAI PHÁ DỮ LIỆU

Chương 2 thiết lập quy trình tổng thể dự báo vị trí gồm 5 giai đoạn liên hoàn:

  • Giai đoạn 1: Lấy dữ liệu từ file log của thanh ghi HLR: Dữ liệu nhật ký thô được xuất từ MSC dưới dạng văn bản không cấu trúc.
  • Giai đoạn 2: Chuẩn hóa dữ liệu đầu vào: Thực hiện qua 4 bước:
    1. Bước 1: Chuyển đổi dữ liệu từ file text sang cơ sở dữ liệu có cấu trúc (chitiet_CG.mdb).
    2. Bước 2: Ghép mã cell bằng cách so sánh trường cell_ID với file ds_BTS, đồng thời loại bỏ các bản ghi của thuê bao chuyển vùng (roaming) không có mã BTS trong mạng nội hạt.
    3. Bước 3: Gom các vị trí di chuyển của cùng một số điện thoại vào một bản ghi, rút trích hai trường cốt lõi là UAP_ID và đường đi UAP, lưu vào bảng UAP_table.
    4. Bước 4: Lọc bỏ các bản ghi có chiều dài chuỗi cell nhỏ hơn 2 (thuê bao đứng yên tại một trạm), lưu kết quả vào bảng UAP_table2. Từ 1.179.034 đường đi ban đầu, dữ liệu được rút gọn còn 56.198 bản ghi di chuyển thực tế.
  • Giai đoạn 3: Khai thác UAPs để được UMPs: Mô hình hóa mạng lưới 351 cell bằng đồ thị $G$ và ma trận kề $351 \times 351$. Thực thi thuật toán UMPMining (Thuật toán 2.5) kết hợp hàm sinh ứng viên CandidateGeneration (Thuật toán 2.6) và hàm tính totDist (Thuật toán 2.7). Với ngưỡng $\text{minsupp} = 2.5$, chương trình tìm ra số lượng ứng viên $C_1 = 351$ và tập mẫu phổ biến chiều dài 1 là $L_1 = 348$.
  • Giai đoạn 4: UMPs $\to$ Mobility Rules: Sinh tập các luật di chuyển từ các mẫu phổ biến có chiều dài $k > 1$. Lọc các luật có độ tin cậy thỏa mãn ngưỡng $\text{minconf}$. Kết quả chạy thực nghiệm tại giai đoạn này trích xuất được 661 luật di chuyển.
  • Giai đoạn 5: Dự báo trước đường đi của thuê bao di động: Khi thuê bao di chuyển qua các cell hiện tại, hệ thống đối sánh với tập luật di chuyển đã thiết lập để dự báo cell kế tiếp mà thuê bao sẽ tới.

CHƯƠNG 3: CẢI TIẾN THUẬT TOÁN UMP MINING VÀ KẾT QUẢ THỰC NGHIỆM

Chương 3 trình bày chi tiết các đề xuất cải tiến kỹ thuật nhằm tối ưu hóa thời gian thực thi của thuật toán UMPMining:

  • Cải tiến 1 (Thuật toán CandidateGeneration_Improved): Áp dụng kỹ thuật tự kết giữa các mẫu phổ biến trong tập $L_k$ để tạo tập ứng viên $C_{k+1}$, loại bỏ việc duyệt toàn bộ các cell lân cận trong đồ thị $G$. Kết quả cho thấy số lượng ứng viên $C_n$ giảm đáng kể và thời gian xử lý nhanh hơn thuật toán gốc.
  • Cải tiến 2 (Thuật toán Find_UMP_Reduce_Complexity): Giảm độ phức tạp tính toán bằng cách chuyển đổi đồ thị mạng từ ma trận kề sang ma trận đường đi ($M_{dd}$) và thiết lập ma trận nhị phân đại diện cho các thuê bao di động. Thuật toán Find_L1 và Find_Lk mới tính toán trực tiếp độ hỗ trợ thông qua các phép toán vector, rút ngắn thời gian quét dữ liệu.
  • Cải tiến 3 (Thuật toán Find_UMP_Reduce_Transaction): Ứng dụng lý thuyết đại số tập hợp để thu nhỏ số lượng giao tác trong cơ sở dữ liệu đường đi. Bắt đầu từ vòng lặp thứ hai ($k \ge 2$), các giao tác không chứa tập phổ biến của bước trước sẽ bị loại bỏ khỏi không gian tìm kiếm, giúp giảm mạnh số phép toán kiểm tra chuỗi con.
  • Thuật toán tăng cường UMP_Online: Xây dựng giải thuật xử lý gia tăng dành riêng cho các giao tác mới được bổ sung vào cơ sở dữ liệu. Thuật toán tận dụng tập mẫu phổ biến và tập luật đã khai phá từ trước, chỉ cập nhật độ hỗ trợ dựa trên dữ liệu mới, loại bỏ thao tác quét lại toàn bộ cơ sở dữ liệu lịch sử.
  • Kết quả thực nghiệm: Chương trình so sánh số lượng ứng viên $C_n$, số tập phổ biến $L_n$, thời gian thực thi và dung lượng bộ nhớ sử dụng giữa thuật toán gốc và các phiên bản cải tiến (Cải tiến 1, Cải tiến 2, Cải tiến 3 và UMP_Online). Kết quả chứng minh các thuật toán cải tiến giữ nguyên số lượng tập mẫu phổ biến tìm được ($L_n$) trong khi giảm rõ rệt thời gian thực hiện.

CHƯƠNG 4: ĐỘ CHÍNH XÁC DỰ BÁO

Chương 4 tập trung đánh giá hiệu năng dự báo thông qua hai chỉ số định lượng: hệ số Recall và độ chính xác Precision.

  • Đánh giá trên tập dữ liệu chuẩn: Tác giả tiến hành thực nghiệm trên 3 tập dữ liệu huấn luyện (Training set 1, Training set 2, Training set 3). Kết quả ghi nhận:
    • Khi tăng giá trị ngưỡng $\text{minsupp}$, hệ số Recall có xu hướng giảm do số lượng luật sinh ra ít hơn.
    • Khi tăng giá trị ngưỡng $\text{minconf}$, độ chính xác Precision tăng lên do các luật được chọn có mức độ tin cậy cao hơn.
  • Phương pháp phân lớp dữ liệu theo thời gian: Nhận thấy hành vi di chuyển của thuê bao di động có tính chu kỳ gắn liền với nhịp sinh hoạt trong ngày, tác giả đề xuất phân chia tập dữ liệu đầu vào thành 3 lớp thời gian riêng biệt:
    1. Lớp sáng: Khung giờ buổi sáng.
    2. Lớp chiều: Khung giờ buổi chiều.
    3. Lớp tối: Khung giờ buổi tối.
  • Hiệu quả của việc phân lớp: Thực nghiệm so sánh giữa mô hình không phân lớp và mô hình có phân lớp thời gian trên cả 3 tập dữ liệu. Kết quả cho thấy ở cả ba khung giờ (sáng, chiều, tối), hệ số Recall và độ chính xác Precision sau khi phân lớp đều cao hơn so với khi sử dụng chung tập dữ liệu không phân chia.

CHƯƠNG 5: KẾT LUẬN

Chương 5 tổng kết toàn bộ nội dung nghiên cứu, khẳng định việc hoàn thành các mục tiêu đề ra về mặt lý thuyết và thực nghiệm. Chương này đồng thời trình bày các vấn đề còn tồn đọng và định hướng nghiên cứu tiếp theo nhằm hoàn thiện giải thuật trong các môi trường mạng phức tạp hơn.

Kết quả và những đóng góp mới

Các đóng góp mới về mặt khoa học và kỹ thuật

  1. Đóng góp thứ nhất (Cải tiến 1 và Cải tiến 2): Giảm thời gian thực thi của thuật toán UMPMining bằng kỹ thuật tự kết trong quá trình sinh tập ứng viên (CandidateGeneration_Improved). Đồng thời, giảm độ phức tạp tính toán thông qua việc chuyển đổi biểu diễn cấu trúc mạng từ ma trận kề sang ma trận đường đi ($M_{dd}$) và ma trận nhị phân, tối ưu hóa các thao tác tìm độ ủng hộ.
  2. Đóng góp thứ hai (Cải tiến 3): Đề xuất giải pháp thu nhỏ số lượng giao tác trong cơ sở dữ liệu đường đi (Find_UMP_Reduce_Transaction). Bằng cách ứng dụng lý thuyết tập hợp, thuật toán loại bỏ dần các giao tác không thỏa mãn điều kiện bắt đầu từ lần lặp thứ hai trở đi, giảm tải bộ nhớ và số chu kỳ xử lý của bộ vi xử lý.
  3. Đóng góp thứ ba (Thuật toán UMP_Online): Phát triển thuật toán khai phá tăng cường UMP_Online. Thuật toán cho phép hệ thống chỉ khai phá trên các khối dữ liệu mới phát sinh để cập nhật cơ sở tri thức mẫu di chuyển, tránh việc phải quét lại toàn bộ cơ sở dữ liệu lớn. Giải pháp này cho phép hệ thống vận hành trực tuyến theo thời gian thực tại các tổng đài viễn thông.
  4. Đóng góp thứ tư (Phân lớp dữ liệu theo thời gian): Đề xuất phương pháp phân lớp dữ liệu đầu vào theo ba khung thời gian trong ngày (sáng, chiều, tối). Phương pháp đã được kiểm chứng thực nghiệm giúp nâng cao đồng thời hệ số Recall và độ chính xác Precision của việc dự báo vị trí thuê bao di động.

Kiến nghị và giải pháp đề xuất

Luận án đề xuất giải pháp kiến trúc đưa phân hệ dự báo trước sự di chuyển của thuê bao di động vào vận hành thực tế tại tổng đài MSC. Phân hệ phần mềm này được bố trí nằm giữa thanh ghi HLR và hệ thống điều khiển băng thông, điều khiển chuyển giao (handover), hỗ trợ nhà mạng cấp phát băng thông động và giảm tỷ lệ rớt cuộc gọi cho các dịch vụ 3G/4G thời gian thực.

Hạn chế và hướng nghiên cứu tiếp

Hạn chế của nghiên cứu

  • Phạm vi dữ liệu thực nghiệm mới được thu thập và đánh giá trên phạm vi một khu vực địa lý cụ thể thuộc một tỉnh, với quy mô 351 trạm BTS.
  • Nghiên cứu tập trung giải quyết bài toán di chuyển trên mạng di động 2G/3G tế bào truyền thống, chưa tích hợp thử nghiệm đầy đủ trên các kiến trúc mạng không đồng nhất mật độ cao (HetNet) hoặc mạng 5G với tế bào siêu nhỏ (small cell).

Hướng nghiên cứu tiếp theo

Luận án xác định các vấn đề cần tiếp tục nghiên cứu trong tương lai:

  1. Mở rộng thử nghiệm thuật toán trên các tập dữ liệu có quy mô lớn hơn với phạm vi liên tỉnh hoặc toàn quốc.
  2. Tiếp tục tối ưu hóa cấu trúc lưu trữ của ma trận đường đi và thuật toán UMP_Online để đáp ứng các mạng di động thế hệ mới có mật độ cell dày đặc và tốc độ thay đổi lưu lượng cao.
  3. Nghiên cứu kết hợp yếu tố không gian - thời gian chi tiết hơn (như ngày trong tuần, ngày cuối tuần, ngày lễ) để tinh chỉnh độ chính xác của các luật di chuyển.

Giá trị tham khảo

Luận án có giá trị tham khảo chuyên môn đối với các nhóm đối tượng:

  • Nghiên cứu sinh và học viên cao học chuyên ngành Kỹ thuật Viễn thông và Khoa học Máy tính: Cung cấp tài liệu tham khảo về phương pháp kết hợp kỹ thuật khai phá dữ liệu (chuỗi tuần tự, luật kết hợp) với bài toán tối ưu mạng vô tuyến; phương pháp tiền xử lý và chuẩn hóa dữ liệu lớn từ file log viễn thông.
  • Kỹ sư vận hành và tối ưu hóa mạng di động tại các doanh nghiệp viễn thông: Cung cấp giải thuật UMP_Online và quy trình phân lớp thời gian có thể ứng dụng trực tiếp để xây dựng các phân hệ tự động dự báo lưu lượng, phục vụ công tác điều chỉnh tham số chuyển giao (handover) và quản lý tài nguyên vô tuyến tại trung tâm chuyển mạch MSC.
  • Các phần đáng chú ý trong luận án: Quy trình chuẩn hóa 4 bước từ dữ liệu nhật ký thô (Chương 2); kỹ thuật ma trận đường đi $M_{dd}$ và mã giả các thuật toán cải tiến (Chương 3); phương pháp phân chia khung giờ thực nghiệm (Chương 4).

Câu hỏi thường gặp

1. Dữ liệu thực nghiệm của luận án được lấy từ đâu và có quy mô như thế nào sau khi làm sạch?
Dữ liệu được trích xuất từ file log của thanh ghi định vị thường trú HLR thuộc Trung tâm chuyển mạch di động (MSC) trên mạng lưới gồm 351 trạm thu phát sóng (BTS). Tập dữ liệu thô ban đầu có 1.179.034 đường đi thực tế của thuê bao di động (UAPs). Sau quy trình chuẩn hóa và lọc sạch qua 4 bước (loại bỏ thuê bao chuyển vùng roaming không có mã BTS và thuê bao đứng yên chỉ ở 1 cell), dữ liệu hợp lệ còn lại là 56.198 bản ghi đường đi.

2. Thuật toán UMPMining của Gokhan Yavas gặp phải nhược điểm gì mà luận án cần cải tiến?
Thuật toán UMPMining truyền thống có thời gian thực thi dài do độ phức tạp tính toán lớn và sinh ra số lượng mẫu ứng viên ($C_k$) quá nhiều trong quá trình duyệt đồ thị. Thuật toán này cũng hoạt động theo chế độ xử lý ngoại tuyến (offline) và bắt buộc phải quét lại toàn bộ cơ sở dữ liệu mỗi khi có dữ liệu mới phát sinh, không đáp ứng được yêu cầu phản hồi tức thời của các ứng dụng quản lý di động thời gian thực.

3. Luận án đã đề xuất những thuật toán cụ thể nào để giảm thời gian xử lý của UMPMining?
Tác giả đề xuất ba thuật toán cải tiến chính:

  • CandidateGeneration_Improved (Cải tiến 1): Sử dụng kỹ thuật tự kết để giảm số lượng ứng viên $C_n$.
  • Find_UMP_Reduce_Complexity (Cải tiến 2): Biến đổi ma trận kề thành ma trận đường đi ($M_{dd}$) và ma trận nhị phân để giảm độ phức tạp tính toán độ hỗ trợ.
  • Find_UMP_Reduce_Transaction (Cải tiến 3): Áp dụng lý thuyết tập hợp để thu nhỏ số lượng giao tác cần duyệt từ lần lặp thứ hai trở đi. Ngoài ra, tác giả phát triển thuật toán UMP_Online để khai phá tăng cường trên các giao tác mới cập nhật mà không quét lại cơ sở dữ liệu cũ.

4. Vì sao việc phân lớp dữ liệu theo thời gian (sáng, chiều, tối) lại nâng cao được độ chính xác dự báo?
Do hành vi di chuyển của người sử dụng điện thoại mang tính chu kỳ sinh hoạt rõ rệt (buổi sáng đi làm, buổi chiều về nhà, buổi tối giải trí hoặc nghỉ ngơi). Khi gom chung toàn bộ dữ liệu cả ngày, các mẫu di chuyển khác hướng nhau sẽ làm giảm độ hỗ trợ và độ tin cậy của các luật đặc thù. Việc phân lớp theo 3 buổi sáng, chiều, tối giúp các luật di chuyển phản ánh chính xác hành vi theo từng khung giờ, từ đó nâng cao đồng thời cả hệ số Recall và độ chính xác Precision.

5. Kết quả thực nghiệm ở giai đoạn sinh luật di chuyển (Mobility Rules) thu được bao nhiêu luật?
Sau khi áp dụng quy trình khai thác mẫu di chuyển thường xuyên (UMPs) với ngưỡng $\text{minsupp} = 2.5$ trên cơ sở dữ liệu 56.198 bản ghi và 351 trạm BTS, chương trình ở Giai đoạn 4 đã tính toán hệ số tin cậy và trích xuất được tổng cộng 661 luật di chuyển thỏa mãn ngưỡng $\text{minconf}$.

Kết luận

Luận án tiến sĩ kỹ thuật của tác giả Giang Minh Đức đã giải quyết bài toán dự báo vị trí thuê bao di động trong mạng truyền thông tế bào bằng hướng tiếp cận khai phá dữ liệu chuỗi tuần tự. Tác giả đã xây dựng quy trình chuẩn hóa dữ liệu thực tế từ thanh ghi HLR và đề xuất các thuật toán cải tiến (CandidateGeneration_Improved, Find_UMP_Reduce_Complexity, Find_UMP_Reduce_Transaction, UMP_Online) giúp giảm độ phức tạp tính toán, thu hẹp không gian tìm kiếm và cho phép cập nhật gia tăng theo thời gian thực. Đồng thời, giải pháp phân lớp dữ liệu theo thời gian (sáng, chiều, tối) đã được kiểm chứng thực nghiệm giúp cải thiện rõ rệt hệ số Recall và độ chính xác Precision của hệ thống dự báo. Các kết quả nghiên cứu cung cấp cơ sở kỹ thuật phục vụ việc tối ưu hóa cấp phát băng thông, điều khiển chuyển giao và nâng cao chất lượng dịch vụ (QoS) cho các mạng di động tế bào.