Một cách tiếp cận trong việc mô hình hóa tham số động cho bài toán kiểm tra tắc nghẽn trên mạng cảm biến không dây - NCS. Lê Ngọc Kim Khánh

Đề tài nghiên cứu: Một cách tiếp cận trong việc mô hình hóa tham số động cho bài toán kiểm tra tắc nghẽn trên mạng cảm biến không dây
Chuyên ngành: Khoa học máy tính
Mã số chuyên ngành: 64.48.01.01
Họ và tên nghiên cứu sinh: Lê Ngọc Kim Khánh
Tập thể hướng dẫn: PGS. TS. Quản Thành Thơ, PGS. TS. Bùi Hoài Thắng
Cơ sở đào tạo: Trường Đại học Bách Khoa – ĐHQG TP. HCM
1. Tóm tắt luận án 
Một trong những vấn đề thu hút sự quan tâm của cộng đồng làm việc trong lĩnh vực mạng cảm biến không dây là phát hiện nghẽn. Nghẽn được phát hiện sớm làm giảm sự mất gói tin, giúp cảm biến tiết kiệm năng lượng từ đó kéo dài tuổi thọ của mạng. Một trong hai phương pháp phát hiện nghẽn là hướng mô phỏng (simulation-based) và hướng mô hình (model-based).
Với định hướng mô hình hóa, kỹ thuật mô hình hóa hình thức được sử dụng để phân tích thuộc tính nghẽn trên mô hình. Mô hình trong luận án sẽ được xây dựng bằng hai ngôn ngữ Place Transition Nets và Coloured Petri Net. Cả hai ngôn ngữ này đều tận dụng sức mạnh của ngôn ngữ Petri Net là ngôn ngữ mô hình hóa được sử dụng phổ biến các hướng nghiên cứu. Mô hình sẽ xây dựng các tham số cũng như các thuộc tính của các phần tử trong mạng (gồm cảm biến và kênh truyền). Sau đó, thuộc tính nghẽn sẽ được tìm kiếm trong không gian trạng thái.
Ngoài ra, để làm giảm sự bùng nổ không gian trạng thái cũng như tăng tốc độ phát hiện nghẽn, thuật toán gom cụm hướng nghẽn nghĩa là các cảm biến sẽ được gom thành nhóm và kiểm tra trước. Bên cạnh đó, thuật toán tìm kiếm nghẽn heuristic được đề xuất giúp cho việc phát hiện nghẽn nhanh chóng tránh làm lãng phí tài nguyên của máy tính.
Hơn nữa, xác suất nghẽn cũng được thêm vào mô hình nhằm tăng độ chính xác khi phát hiện nghẽn, tránh tình trạng nghẽn giả.
2. Những kết quả mới của luận án 
 Đề xuất mô hình WSN-PN: một mô hình mạng cảm biến không dây với hai thành phần là cảm biến và kênh truyền bằng ngôn ngữ Place Transition Nets.
Luận án đề xuất việc mô hình hóa mạng cảm biến không dây theo phương pháp hình thức. Ngôn ngữ được lựa chọn để mô hình hóa là Place Transition Nets, đây là một loại ngôn ngữ Petri Net sơ cấp, đơn giản với cách định nghĩa một mô hình khá giống cách thể hiện một sơ đồ mạng cảm biến không dây. Từ mô hình này, việc phát hiện nghẽn sẽ được biểu diễn thành một thuộc tính để có thể kiểm tra bằng kỹ thuật Kiểm tra mô hình (Model Checking).
 Đề xuất mô hình WSN-CPN: một mô hình mạng cảm biến không dây bằng ngôn ngữ Coloured Petri Net.
Ngôn ngữ Coloured Petri Net sẽ mang đến cho bài toán của luận án sự thể hiện tường minh các tham số bên trong mạng cảm biến không dây, từ đó người mô hình mạng sẽ dễ dàng tích hợp thêm những tính năng nâng cao hơn của mạng.
 Đề xuất hai thuật toán tăng tốc độ tìm kiếm nghẽn trên mô hình mạng cảm biến không dây: tăng tốc dựa vào gom cụm và tăng tốc dựa vào thuật toán tìm kiếm heuristic.
Ý tưởng và cách kiểm tra thuộc tính với kỹ thuật Model Checking tuy không quá phức tạp nhưng lại làm nảy sinh vấn đề rất lớn cho bài toán này đó là việc bùng nổ không gian trạng thái. Không gian trạng thái bị bùng nổ khi số lượng trạng thái sinh ra quá nhiều do bài toán có quá nhiều tham số hay các tham số thay đổi liên tục dẫn đến việc máy tính không đủ tài nguyên xử lý. Bùng nổ trong bài toán phát hiện nghẽn của luận án còn gây ra sự chậm trễ trong việc trả lời mạng có nghẽn hay không. Để vượt qua vấn đề này một cách gián tiếp, luận án đã đề xuất hai thuật toán tăng tốc phát hiện nghẽn dựa vào thuật toán gom cụm hướng nghẽn và thuật hoán tìm kiếm heuristic.
Thuật toán gom cụm hướng nghẽn sẽ gom các cảm biến có nguy cơ xảy ra nghẽn vào các cụm và luận án sẽ kiểm tra các cụm này để tìm nghẽn trước thay vì kiểm tra lần lượt từng cảm biến hay kênh truyền với cách làm của kỹ thuật kiểm tra mô hình. Đối với thuật toán tăng tốc dựa vào thuật toán tìm kiếm heuristic thì luận án lại đề xuất một cách duyệt trên không gian trạng thái dưới sự điều phối của hàm heuristic nhằm hướng việc tìm thấy nút nghẽn một cách nhanh nhất.
 Đề xuất mô hình động cho phép người dùng tùy chỉnh các thông số trong mạng và đề xuất thêm phát hiện nghẽn để phát hiện nghẽn chính xác hơn, tránh tình trạng nghẽn giả.
Mô hình động là mô hình cho phép người dùng dễ dàng cập nhật lại các tham số trong mạng mà không cần mô hình lại từ đầu. Ngoài ra, các tham số trong mô hình động cũng phải được cập nhật lại giá trị thường xuyên trong suốt quá trình vận hành của mạng.Xác suất nghẽn được đưa vào mô hình để giúp người mô hình mạng có thông tin chính xác hơn về việc nghẽn có thể xảy ra thật sự trên mạng hay không, từ đó sẽ có sự điều chỉnh phù hợp.
3. Các ứng dụng/ khả năng ứng dụng trong thực tiễn hay những vấn đề còn bỏ ngỏ cần tiếp tục nghiên cứu
Kết quả nghiên cứu của luận án đã đưa ra được hướng tiếp cận hình thức với bài toán mô hình hóa mạng cảm biến không dây và thuộc tính phát hiện nghẽn trên mạng.
Tuy nhiên, vẫn có thể thực hiện các nghiên cứu thêm để mô hình hóa bài toán gần sát với yêu cầu thực tế nhất.
 Đóng góp thêm yếu tố thời gian vào mô hình nhằm phản ánh đúng mô hình thực tế hơn. Yếu tố thời gian đã được một số công trình tích hợp vào mô hình WSNCPN của luận án nhưng đa số vẫn dưới dạng các sự kiện, chưa phản ánh đúng bản chất thời gian thực.
 Mô hình của luận án có thể mở rộng với nhiều loại tham số ảnh hưởng đến xác suất nghẽn khác bên cạnh yếu tố độ tin cậy của cảm biến hay kênh truyền, ví dụ như độ nhiễu của môi trường.
 Cải tiến thêm thời gian phát hiện nghẽn để nghẽn có thể được phát hiện sau vài giây vận hành hệ thống. Điều này nhằm tăng tính ứng dụng cao của các mô hình mà luận án đã đề xuất.