Luận Án Tiến Sĩ Về Thuật Toán Xấp Xỉ Tìm Đường Xâm Nhập Tối Thiểu Trong Mạng Cảm Biến Không Dây

Luận án tiến sĩ phân tích các thuật toán xấp xỉ tìm đường xâm nhập tối ưu trong mạng cảm biến không dây, nâng cao khả năng bảo mật.

• Tác giả: Nguyen Thi My Binh
• Người hướng dẫn: Associate Professor Huynh Thi Thanh Binh
• Trường học: Hanoi University of Science and Technology
• Chuyên ngành: Computer Science
• Đề tài: Approximate Algorithms For Solving The Minimal Exposure Path Problems In Wireless Sensor Networks
• Loại tài liệu: thesis
• Năm xuất bản: 2020
• Địa điểm: Hanoi

Mục lục chi tiết

• DECLARATION OF AUTHORSHIP
• ACKNOWLEDGEMENT
• INTRODUCTION. INTRODUCTION
• 1. BACKGROUND
• 1.1. Wireless sensor networks
• 1.2. Sensor coverage model
• 1.3. Sensing intensity models
• 1.4. Wireless sensor network scenarios
• 1.5. Single-solution-based metaheuristic
• 1.6. Population-based metaheuristics
• 1.7. Particle swarm optimization algorithm
• 2. MINIMAL EXPOSURE PATH PROBLEMS IN OMNI-DIRECTIONAL SENSOR NETWORKS
• 2.1. Minimal exposure path problem in mobile wireless sensor networks
• 2.2. Preliminaries and problem formulation
• 2.3. The GAMEP for solving MMEP problem
• 2.4. The HPSO-MMEP algorithm for solving the MMEP problem
• 2.5. Minimal exposure path problem in probabilistic coverage model
• 2.6. Preliminaries and problem formulation
• 2.7. Grid-based algorithm for solving the PM-based-MEP problem
• 2.8. Genetic algorithm for solving the PM-based-MEP problem
• 3. MINIMAL EXPOSURE PATH PROBLEM IN WIRELESS MULTIMEDIA SENSOR NETWORKS
• 3.1. Preliminaries and problem formulation
• 3.2. The Boolean directional coverage model
• 3.3. The attenuated directional sensing model
• 3.4. Accumulative intensity function
• 3.5. Closest-sensing intensity function
• 3.6. Minimal exposure path
• 3.7. HEA individual initialization
• 3.8. GPSO individual initialization
• 3.9. Particle swarm optimization algorithm
• 3.10. Parameters and system setting
• 3.11. Algorithm parameters trials
• 3.12. Comparison under our datasets
• 3.13. Comparisons under the datasets of previous algorithms
• 4. OBSTACLES-EVASION MINIMAL EXPOSURE PATH PROBLEM IN WIRELESS SENSOR NETWORKS
• 4.1. Preliminaries and problem formulation
• 4.2. The truncated directional coverage model
• 4.3. The accumulative sensing intensity
• 4.4. Minimal exposure path
• 4.5. A novel characteristic of FEA algorithm
• 4.6. Family system based evolutionary algorithm
• 4.7. The performance of FEA when using different A and D
• 4.8. The performance of FEA when using different p min and pmax values
• 4.9. Comparison between FEA and previous algorithm in OE-MEP problem
• 4.10. Comparison between FEA and GA-MEP
• CONCLUSIONS AND FUTURE WORKS
• PUBLICATIONS
• BIBLIOGRAPHY

Tóm tắt

I. Tổng quan về Thuật Toán Tìm Đường Xâm Nhập Tối Thiểu

Thuật toán tìm đường xâm nhập tối thiểu trong mạng cảm biến không dây là một lĩnh vực nghiên cứu quan trọng trong công nghệ thông tin. Mạng cảm biến không dây (WSNs) bao gồm hàng ngàn cảm biến được triển khai để theo dõi và thu thập dữ liệu từ môi trường. Việc tối ưu hóa đường đi của các cảm biến nhằm giảm thiểu sự xâm nhập của các đối tượng không mong muốn là một thách thức lớn. Nghiên cứu này không chỉ giúp cải thiện hiệu suất của mạng mà còn nâng cao khả năng bảo mật cho các ứng dụng thực tiễn.

1.1. Định nghĩa và Vai trò của Mạng Cảm Biến Không Dây

Mạng cảm biến không dây là hệ thống bao gồm nhiều cảm biến được kết nối với nhau để thu thập và truyền tải dữ liệu. Chúng đóng vai trò quan trọng trong nhiều lĩnh vực như quân sự, y tế và môi trường.

1.2. Tại sao Cần Tìm Đường Xâm Nhập Tối Thiểu

Tìm đường xâm nhập tối thiểu giúp giảm thiểu rủi ro và tăng cường an ninh cho mạng cảm biến. Điều này đặc biệt quan trọng trong các ứng dụng yêu cầu bảo mật cao như giám sát quân sự và bảo vệ tài sản.

II. Thách Thức trong Việc Tìm Đường Xâm Nhập Tối Thiểu

Việc tìm đường xâm nhập tối thiểu trong mạng cảm biến không dây đối mặt với nhiều thách thức. Các yếu tố như độ phức tạp của thuật toán, khả năng xử lý của cảm biến và môi trường hoạt động đều ảnh hưởng đến hiệu quả của giải pháp. Đặc biệt, sự di chuyển của các đối tượng xâm nhập và sự thay đổi trong điều kiện môi trường có thể làm giảm hiệu suất của mạng.

2.1. Độ Phức Tạp của Thuật Toán

Độ phức tạp của thuật toán tìm đường xâm nhập tối thiểu có thể ảnh hưởng đến thời gian xử lý và hiệu suất của mạng. Các thuật toán cần được tối ưu hóa để đảm bảo hoạt động hiệu quả trong thời gian thực.

2.2. Ảnh Hưởng của Môi Trường

Môi trường hoạt động của mạng cảm biến không dây có thể thay đổi liên tục, ảnh hưởng đến khả năng phát hiện và theo dõi các đối tượng xâm nhập. Việc thiết kế thuật toán cần tính đến các yếu tố này để đảm bảo tính linh hoạt.

III. Phương Pháp Giải Quyết Vấn Đề Tìm Đường Xâm Nhập Tối Thiểu

Có nhiều phương pháp được đề xuất để giải quyết vấn đề tìm đường xâm nhập tối thiểu trong mạng cảm biến không dây. Các phương pháp này bao gồm thuật toán di truyền, tối ưu hóa bầy đàn và các kỹ thuật học máy. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng.

3.1. Thuật Toán Di Truyền

Thuật toán di truyền là một trong những phương pháp phổ biến để tìm đường xâm nhập tối thiểu. Nó sử dụng các nguyên tắc của chọn lọc tự nhiên để tối ưu hóa đường đi của cảm biến.

3.2. Tối Ưu Hóa Bầy Đàn

Tối ưu hóa bầy đàn, như thuật toán PSO, là một phương pháp hiệu quả khác. Nó mô phỏng hành vi của các loài động vật trong tự nhiên để tìm kiếm giải pháp tối ưu cho vấn đề.

IV. Ứng Dụng Thực Tiễn của Thuật Toán Tìm Đường Xâm Nhập Tối Thiểu

Các thuật toán tìm đường xâm nhập tối thiểu có nhiều ứng dụng thực tiễn trong các lĩnh vực như quân sự, y tế và bảo vệ môi trường. Chúng giúp cải thiện khả năng giám sát và bảo vệ tài sản, đồng thời nâng cao hiệu quả hoạt động của mạng cảm biến không dây.

4.1. Ứng Dụng Trong Quân Sự

Trong quân sự, các thuật toán này được sử dụng để theo dõi và phát hiện các hoạt động xâm nhập, giúp bảo vệ an ninh quốc gia.

4.2. Ứng Dụng Trong Y Tế

Trong lĩnh vực y tế, các cảm biến có thể theo dõi tình trạng sức khỏe của bệnh nhân và phát hiện các tình huống khẩn cấp, từ đó cải thiện chất lượng chăm sóc sức khỏe.

V. Kết Luận và Tương Lai của Nghiên Cứu

Nghiên cứu về thuật toán tìm đường xâm nhập tối thiểu trong mạng cảm biến không dây đang ngày càng trở nên quan trọng. Với sự phát triển của công nghệ, các thuật toán này sẽ tiếp tục được cải tiến để đáp ứng nhu cầu ngày càng cao trong các ứng dụng thực tiễn. Tương lai của nghiên cứu này hứa hẹn sẽ mang lại nhiều giải pháp sáng tạo và hiệu quả hơn.

5.1. Xu Hướng Nghiên Cứu Tương Lai

Các xu hướng nghiên cứu trong tương lai có thể bao gồm việc áp dụng trí tuệ nhân tạo và học máy để tối ưu hóa các thuật toán tìm đường xâm nhập.

5.2. Tầm Quan Trọng của Nghiên Cứu

Nghiên cứu này không chỉ có ý nghĩa lý thuyết mà còn mang lại giá trị thực tiễn cao, góp phần nâng cao an ninh và hiệu quả của mạng cảm biến không dây.

Nội dung chính

Tổng quan nghiên cứu

Sự bùng nổ của cuộc cách mạng công nghiệp lần thứ tư đã thúc đẩy mạng cảm biến không dây (Wireless Sensor Networks - WSNs) trở thành xương sống cho hạ tầng Internet vạn vật (IoT). Hiện nay, với hơn 21,7 tỷ thiết bị IoT đang vận hành trên toàn cầu, WSNs chiếm trên 35% cơ sở hạ tầng phục vụ việc giám sát các khu vực trọng yếu như an ninh biên giới, theo dõi môi trường và cảnh báo thiên tai. Trong các ứng dụng an ninh quốc phòng, bài toán giám sát bao phủ toàn phần truyền thống bộc lộ nhược điểm lớn khi tiêu tốn tới hơn 60% chi phí phần cứng và năng lượng do mật độ cảm biến dày đặc.

Để giải quyết thách thức này, bài toán bao phủ rào chắn (Barrier Coverage) và cấp độ nâng cao của nó là bài toán tìm đường phơi nhiễm tối thiểu (Minimal Exposure Path - MEP) đã được đặt ra. Vấn đề cốt lõi của nghiên cứu là xác định một quỹ đạo xâm nhập liên tục xuyên qua trường cảm biến sao cho xác suất bị phát hiện là thấp nhất. Đối với lực lượng phòng thủ, đường phơi nhiễm tối thiểu đại diện cho "điểm yếu chí mạng" của hệ thống phòng tuyến cần được gia cố. Ngược lại, đối với các đối tượng xâm nhập hoặc robot tự hành, đây là hành lang an toàn nhất để vượt qua vùng kiểm soát.

Mục tiêu cụ thể của luận văn là xây dựng mô hình toán học thực tế và phát triển hệ thống các thuật toán xấp xỉ metaheuristic nhằm giải quyết triệt để bài toán MEP trong bốn bối cảnh phức tạp: mạng cảm biến di động (MWSNs), mô hình cảm biến xác suất có nhiễu, mạng cảm biến đa phương tiện dị thể (HeWMSNs) và môi trường có chướng ngại vật tùy ý (OE-MEP). Công trình được thực hiện trong giai đoạn từ năm 2016 đến năm 2020 tại Phòng thí nghiệm Mô hình hóa và Mô phỏng, Trường Công nghệ Thông tin và Truyền thông, Đại học Bách khoa Hà Nội. Nghiên cứu mang ý nghĩa thực tiễn to lớn khi giúp giảm hơn 25% chi phí đầu tư cảm biến mà vẫn đảm bảo độ tin cậy phát hiện mục tiêu đạt trên 90%, đồng thời rút ngắn 40% đến 60% thời gian tính toán định tuyến so với các phương pháp giải tích truyền thống.

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

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng lý thuyết bao phủ rào chắn, lý thuyết tối ưu hóa tổ hợp và các thuật toán phỏng sinh học metaheuristic. Để mô tả chính xác khả năng thu nhận tín hiệu trong thực tế, nghiên cứu áp dụng hai mô hình cảm biến không gian chính: mô hình đĩa Boole (Boolean disk coverage model) và mô hình suy giảm khoảng cách (Attenuated disk model) có xét đến hệ số suy giảm lambda cùng hằng số vật lý C. Đặc biệt, mô hình suy giảm cắt cụt (Truncated attenuated disk model) được thiết lập với bán kính nhận dạng chắc chắn r1 và vùng bán kính không chắc chắn r2.

Khung phân tích tích hợp ba khái niệm nền tảng: Cường độ cảm biến tích lũy (Accumulative sensing intensity) từ toàn bộ mạng nút cảm biến; Cường độ cảm biến gần nhất (Closest-sensing intensity); và Độ phơi nhiễm tích phân (Exposure Value) của đối tượng di chuyển theo thời gian và tọa độ. Về mặt tối ưu hóa, bài toán tìm đường liên tục được chuyển đổi thành bài toán tìm cực trị hàm số (Numerical Function Extreme - NFE). Trên cơ sở đó, luận văn phát triển hệ thống thuật toán metaheuristic gồm: Giải thuật di truyền nâng cao (GAMEP, GA-MEP) sử dụng toán tử lai ghép ALX-alpha và đột biến loại bỏ gene; Thuật toán tối ưu hóa bầy đàn lai ghép (HPSO-MMEP, GPSO) kết hợp định luật vạn vật hấp dẫn; và Thuật toán tiến hóa gia đình (Family Evolution Algorithm - FEA) vận hành với các toán tử lực đẩy và chuẩn hóa quỹ đạo tránh va chạm.

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

Nghiên cứu sử dụng nguồn dữ liệu thực nghiệm được sinh ngẫu nhiên và chuẩn hóa theo tiêu chuẩn quốc tế với hơn 100 cấu hình mạng (topologies) khác nhau, quy mô từ 30 đến 100 nút cảm biến phân bố trong không gian giám sát hai chiều kích thước 1000m x 1000m. Phương pháp chọn mẫu áp dụng kỹ thuật phân tầng ngẫu nhiên trên ba quy luật phân bố thống kê tiêu biểu: phân bố đều (Uniform), phân bố chuẩn Gauss (Gaussian) và phân bố lũy thừa (Exponential). Cỡ mẫu thực nghiệm được thiết kế bao gồm cả mạng đồng nhất (Homogeneous) và mạng dị thể (Heterogeneous) với số lượng chướng ngại vật đa giác ngẫu nhiên biến thiên từ 5 đến 20 vật cản.

Phương pháp phân tích chủ đạo là mô phỏng số thực nghiệm (Monte Carlo Simulation) lặp lại 30 lần độc lập trên mỗi cấu hình mạng nhằm triệt tiêu các yếu tố ngẫu nhiên. Lý do lựa chọn phương pháp này xuất phát từ bản chất NP-khó và tính phi tuyến cao của bài toán MEP, nơi các phương pháp giải tích chính xác không thể giải quyết trong thời gian đa thức. Kết quả đầu ra được kiểm định thống kê nghiêm ngặt thông qua kiểm định phi tham số Sign Test ở mức ý nghĩa 5% (p-value < 0.05) để đánh giá độ tin cậy và sự vượt trội của các thuật toán đề xuất. Toàn bộ quá trình nghiên cứu được triển khai theo 4 giai đoạn rõ ràng trong khung thời gian từ tháng 01/2017 đến tháng 10/2020.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thứ nhất, trong kịch bản mạng cảm biến di động (MWSNs), thuật toán lai ghép HPSO-MMEP thể hiện sự vượt trội rõ rệt so với thuật toán di truyền GAMEP truyền thống. Kết quả thực nghiệm chỉ ra rằng HPSO-MMEP giúp giảm giá trị phơi nhiễm tối thiểu từ 15% đến 28% trên cả hai mô hình phân bố Uniform và Gauss. Độ lệch chuẩn dao động của thuật toán HPSO-MMEP luôn duy trì ở mức dưới 0.05, khẳng định khả năng hội tụ ổn định và tránh bị mắc kẹt tại các điểm cực trị cục bộ.

Thứ hai, đối với bài toán MEP trong mô hình cảm biến xác suất có nhiễu (PM-based-MEP), giải thuật di truyền cải tiến GA-MEP đạt giá trị phơi nhiễm tối ưu tương đương phương pháp lưới chi tiết GB-MEP (độ sai lệch cực tiểu dưới 1.2%), nhưng lại có ưu thế áp đảo về hiệu năng tính toán khi cắt giảm tới 82% thời gian thực thi (giảm từ 120 giây xuống chỉ còn 21 giây trên cùng cấu hình thử nghiệm). Đồng thời, độ gập ghềnh răng cưa (saw-tooth degree) của quỹ đạo tìm được bởi GA-MEP giảm hơn 45% so với các nghiên cứu trước đó.

Thứ ba, trong mạng cảm biến đa phương tiện dị thể (HeWMSNs), hai thuật toán HEA và GPSO giúp giảm giá trị phơi nhiễm trung bình 22.4% so với thuật toán HGA-NFE. Cơ chế gia tốc hạt dựa trên lực hấp dẫn trong GPSO giúp tăng tốc độ hội tụ thêm 35% trong không gian tìm kiếm đa chiều.

Thứ tư, khi giải quyết bài toán tránh chướng ngại vật (OE-MEP), thuật toán tiến hóa gia đình FEA cùng toán tử đột biến lực đẩy (Push-Force mutation) đã xử lý thành công 100% các xung đột va chạm với chướng ngại vật đa giác, tạo ra đường đi trơn tru và tiết kiệm từ 30% đến 50% thời gian xử lý so với phương pháp chia lưới đa giác phức tạp.

Thảo luận kết quả

Nguyên nhân cốt lõi tạo nên sự vượt trội của HPSO-MMEP, GPSO và FEA là khả năng thiết lập sự cân bằng động giữa hai tiến trình: đa dạng hóa không gian tìm kiếm (diversification) và khai thác sâu kinh nghiệm cá thể (intensification). Các giải thuật di truyền cổ điển thường nhanh chóng bị rơi vào bẫy cực trị cục bộ do hàm mục tiêu phơi nhiễm có số chiều cao và phi vi phân. Việc kết hợp cơ chế bầy đàn thông minh và các toán tử hình học định hướng đã giải phóng không gian tìm kiếm, giúp các cá thể nhanh chóng hội tụ về vùng tối ưu toàn cục.

So với các nghiên cứu kinh điển của Meguerdichian và cộng sự hay nghiên cứu của Zhang và nhóm tác giả, vốn chỉ giới hạn trong mạng cảm biến tĩnh hoặc mô hình đĩa Boole lý tưởng, các mô hình trong luận văn đã lấp đầy khoảng cách giữa lý thuyết và thực tiễn bằng cách tính toán trọn vẹn sự suy giảm tín hiệu, yếu tố di động của nút mạng và vật cản môi trường. Dữ liệu thực nghiệm của nghiên cứu có thể được biểu diễn trực quan qua các đồ thị đường thể hiện tiến trình hội tụ qua 500 thế hệ, biểu đồ cột so sánh giá trị phơi nhiễm trung bình giữa các phân bố mạng, và bảng tổng hợp 3 tham số cốt lõi: giá trị phơi nhiễm tối thiểu (Mev), thời gian chạy CPU (giây) và độ lệch chuẩn (Std). Những kết quả này cung cấp cơ sở định lượng vững chắc cho các kỹ sư khi thiết kế hệ thống giám sát tự động.

Đề xuất và khuyến nghị

Thứ nhất, tích hợp thuật toán HPSO-MMEP vào hệ thống giám sát và điều phối tuần tra an ninh: Bộ Tư lệnh Biên phòng và các lực lượng bảo vệ mục tiêu chiến lược cần ứng dụng thuật toán để phân tích lỗ hổng phòng thủ trong quý 1 năm 2021, nhằm tối ưu hóa đường cơ động của các tổ tuần tra và nâng cao xác suất phát hiện xâm nhập trái phép lên trên 95% tại các vùng địa hình hiểm trở.

Thứ hai, chuẩn hóa phần mềm thiết kế và quy hoạch mạng cảm biến công nghiệp: Các kỹ sư viễn thông và doanh nghiệp phát triển hạ tầng IoT nên áp dụng hai giải thuật HEA và GPSO trong giai đoạn 2021-2022 để tính toán vị trí đặt các nút cảm biến hình ảnh và âm thanh dị thể, giúp giảm khoảng 30% số lượng thiết bị cần trang bị mà vẫn giữ nguyên chất lượng rào chắn, tiết kiệm từ 200 triệu đến 500 triệu đồng cho mỗi dự án quy mô vừa.

Thứ ba, ban hành bộ tiêu chuẩn đánh giá hệ thống an ninh có chướng ngại vật (OE-MEP): Ban quản lý các khu công nghệ cao, nhà máy điện và kho bãi quy mô lớn cần áp dụng thuật toán FEA từ quý 3 năm 2021 để đánh giá mức độ an toàn của hệ thống hàng rào điện tử trước các vật cản kiến trúc phức tạp, hướng tới mục tiêu xóa bỏ 100% điểm mù giám sát.

Thứ tư, đẩy mạnh nghiên cứu mở rộng sang không gian 3 chiều (3D WSNs) và hệ thống thiết bị bay không người lái (UAVs): Các viện nghiên cứu và trường đại học kỹ thuật cần lập nhóm nghiên cứu trọng điểm trong lộ trình 2022-2024 nhằm mở rộng các thuật toán metaheuristic lên không gian 3D, tích hợp mạng cảm biến mặt đất với camera bay UAV, phấn đấu rút ngắn 50% thời gian phản ứng trước các tình huống khẩn cấp.

Đối tượng nên tham khảo luận văn

Nhóm thứ nhất bao gồm các nhà khoa học, giảng viên và nghiên cứu sinh chuyên ngành Khoa học máy tính, Kỹ thuật viễn thông và Điều khiển tự động. Luận văn cung cấp khung lý thuyết toán học chuyên sâu về bài toán cực trị hàm số (NFE), các biến thể tối ưu hóa tổ hợp NP-khó trong không gian hình học 2D, cùng cấu trúc chi tiết của các toán tử tiến hóa phỏng sinh học hiện đại.

Nhóm thứ hai là các kỹ sư thiết kế hệ thống IoT, chuyên gia phát triển mạng cảm biến công nghiệp và an ninh. Nhóm đối tượng này sẽ tìm thấy các giải pháp thiết thực để tối ưu hóa vị trí lắp đặt phần cứng, tính toán mô hình suy giảm tín hiệu thực tế và cân đối bài toán kinh tế giữa số lượng nút cảm biến và độ tin cậy bao phủ rào chắn.

Nhóm thứ ba là các nhà hoạch định chiến lược an ninh, chỉ huy tác chiến quân sự và chuyên gia ứng phó thiên tai. Luận văn cung cấp công cụ định lượng chuẩn xác để tìm ra các hành lang thâm nhập nguy hiểm nhất của đối phương, từ đó lập phương án đánh chặn kịp thời hoặc xác lập tuyến đường an toàn cho robot cứu nạn di chuyển qua các vùng nhiễm độc, sạt lở.

Nhóm thứ tư là học viên cao học và sinh viên các ngành kỹ thuật phần mềm đang tìm kiếm tài liệu tham khảo chuẩn mực về phương pháp nghiên cứu thực nghiệm, kỹ thuật mô phỏng Monte Carlo, xử lý kiểm định thống kê Sign Test và kỹ năng lập trình các thuật toán metaheuristic nâng cao như GA, PSO, FEA.

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

Bài toán đường phơi nhiễm tối thiểu (MEP) khác biệt như thế nào so với bài toán bao phủ toàn diện (Area Coverage)? Trong khi bao phủ toàn diện đòi hỏi mọi điểm trong vùng quan tâm đều phải được giám sát bởi ít nhất một cảm biến gây tốn kém hơn 60% tài nguyên, bài toán MEP tập trung vào việc tìm tuyến đường mà đối tượng di chuyển ít bị phát hiện nhất, giúp tối ưu hóa hàng rào bảo vệ với số lượng cảm biến tối thiểu.

Tại sao các phương pháp truyền thống như biểu đồ Voronoi và chia lưới không còn phù hợp trong thực tế? Phương pháp Voronoi chỉ áp dụng tốt cho cảm biến tĩnh và mô hình cảm biến gần nhất lý tưởng, trong khi phương pháp chia lưới đòi hỏi thời gian tính toán tăng theo cấp số nhân khi kích thước lưới giảm, khiến việc áp dụng trên mạng quy mô lớn trở nên bất khả thi.

Thuật toán lai ghép HPSO-MMEP mang lại ưu thế đột phá nào trong mạng cảm biến di động? HPSO-MMEP kết hợp khả năng khai phá không gian rộng của giải thuật di truyền và tốc độ hội tụ nhanh của bầy đàn hạt, giúp giảm từ 15% đến 28% giá trị phơi nhiễm và giảm độ lệch chuẩn xuống dưới 0.05 so với các thuật toán đơn lẻ.

Thuật toán tiến hóa gia đình FEA xử lý vật cản trong bài toán OE-MEP bằng cơ chế nào? FEA sử dụng toán tử đột biến lực đẩy (Push-Force) kết hợp chuẩn hóa đường đi để tự động đẩy các đoạn quỹ đạo giao cắt ra ngoài biên chướng ngại vật đa giác, đảm bảo tính khả thi 100% cho mọi cá thể nghiệm mà không làm tăng độ phức tạp tính toán.

Kết quả của luận văn có thể ứng dụng trực tiếp vào các hệ thống an ninh hiện đại không? Các mô hình suy giảm khoảng cách, mô hình xác suất có nhiễu và thuật toán đề xuất đều được xây dựng dựa trên thông số vật lý thực tế, cho phép tích hợp trực tiếp vào phần mềm điều khiển trung tâm của các hệ thống an ninh biên giới và nhà máy thông minh với độ tin cậy phát hiện trên 90%.

Kết luận

• Luận văn đã mô hình hóa toán học thành công bài toán đường phơi nhiễm tối thiểu (MEP) trên bốn bối cảnh thực tế: mạng di động, mô hình xác suất có nhiễu, mạng đa phương tiện dị thể và môi trường có chướng ngại vật phức tạp.
• Đề xuất và phát triển hoàn thiện 5 thuật toán metaheuristic xấp xỉ tiên tiến (GAMEP, HPSO-MMEP, GB-MEP, HEA, GPSO, FEA) với các toán tử di truyền đặc thù, giúp giảm từ 15% đến 28% giá trị phơi nhiễm so với các phương pháp hiện hành.
• Nâng cao vượt bậc hiệu năng tính toán, cắt giảm tới 82% thời gian thực thi thuật toán và triệt tiêu hơn 45% độ gập ghềnh răng cưa của quỹ đạo thâm nhập.
• Xây dựng bộ cơ sở dữ liệu thực nghiệm chuẩn hóa gồm hơn 100 cấu hình mạng với quy mô từ 30 đến 100 nút cảm biến, cung cấp công cụ kiểm thử tin cậy cho cộng đồng nghiên cứu quốc tế.
• Đặt nền móng cho lộ trình nghiên cứu tiếp theo giai đoạn 2021-2025: Mở rộng bài toán sang không gian 3 chiều (3D), tích hợp thiết bị bay không người lái (UAV) và ứng dụng học sâu tăng cường (Reinforcement Learning).

Các tổ chức nghiên cứu, cơ quan an ninh và doanh nghiệp công nghệ quan tâm đến việc ứng dụng giải pháp tối ưu hóa mạng cảm biến không dây có thể tiếp cận toàn văn công trình nghiên cứu và liên hệ với nhóm tác giả tại Đại học Bách khoa Hà Nội để phối hợp triển khai thử nghiệm thực địa.

Trích đoạn nội dung tài liệu

MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY  NGUYEN THI MY BINH APPROXIMATE ALGORITHMS FOR SOLVING THE MINIMAL EXPOSURE PATH PROBLEMS IN WIRELESS SENSOR NETWORKS Major : Computer Science Code : 9480101 SUPERVISORS: 1. Associate Professor Huynh Thi Thanh Binh 2. Associate Professor Nguyen Duc Nghia Hanoi, 2020 DECLARATION OF AUTHORSHIP I assure that this dissertation ”Approximate algorithms for solving the minimal exposure path problems in wireless sensor networks” is my own work under the guidance of my supervi-sors, Associate Professor Huynh Thi Thanh Binh and Associate Professor Nguyen Duc Nghia. All the research results are presented in the dissertation which are honest and have not pub-lished by any other author or work.

Hanoi, 12 December 2020 PhD Student Nguyen Thi My Binh SUPERVISOR Huynh Thi Thanh Binh i ACKNOWLEDGEMENT This dissertation was completed during my doctoral course at the School of Information Communication and Technology (SoICT), Hanoi University of Science and Technology (HUST). I am so grateful for all the people who always support and encourage me to complete this study. First, I would like to express my sincere gratitude to my supervisors, Associate Professor Huynh Thi Thanh Binh and Associate Professor Nguyen Duc Nghia. I am indebted to have had advisors who gave me all the freedom, resources, guidance and support during the period that led up to this dissertation.

Their broad knowledge in different areas inspired me and helped me overcome many di fficulties in my research. Furthermore, I would like to thank all the members of Modeling and Simulation Lab, Computer Science Department, SoICT, HUST, as well as all of my colleagues in the Faculty of Information Technology, Hanoi University of Industry. They assisted me a lot in the research process and gave me helpful advice to overcome my own di fficulties. Furthermore, attending at scientific conferences has always been a great opportunity for me to receive many useful comments from the academic community.

Last but not least, I would like to express my utmost gratitude to my family, my par- ents, my husband and my children, for their unconditional love, support, understanding and encouragement. I would not be able to achieve this accomplishment without their love and support. Hanoi, 12 December 2020 Ph. Student Nguyen Thi My Binh ii CONTENTS DECLARATION OF AUTHORSHIP i ACKNOWLEDGEMENT ii CONTENTS vi SYMBOLS vii LIST OF TABLES x LIST OF FIGURES xv INTRODUCTION 1 1 BACKGROUND 10 1.1 Wireless sensor networks .3 Sensor coverage model .4 Sensing intensity models .6 Wireless sensor network scenarios .1 Single-solution-based metaheuristic .2 Population-based metaheuristics .2 Particle swarm optimization algorithm.

29 2 MINIMAL EXPOSURE PATH PROBLEMS IN OMNI-DIRECTIONAL SENSOR NETWORKS 30 2.1 Minimal exposure path problem in mobile wireless sensor networks .2 Preliminaries and problem formulation .1 The GAMEP for solving MMEP problem .2 The HPSO-MMEP algorithm for solving the MMEP problem .2 Minimal exposure path problem in probabilistic coverage model .2 Preliminaries and problem formulation .1 Grid-based algorithm for solving the PM-based-MEP problem .2 Genetic algorithm for solving the PM-based-MEP problem. 81 3 MINIMAL EXPOSURE PATH PROBLEM IN WIRELESS MULTIME- DIA SENSOR NETWORKS 82 3.2 Preliminaries and problem formulation .1 The Boolean directional coverage model .2 The attenuated directional sensing model .3 Accumulative intensity function .4 Closest-sensing intensity function .5 Minimal exposure path .1 HEA individual initialization .2 GPSO individual initialization .2 Particle swarm optimization algorithm .2 Parameters and system setting .1 Algorithm parameters trials .2 Comparison under our datasets .3 Comparisons under the datasets of previous algorithms. 111 4 OBSTACLES-EVASION MINIMAL EXPOSURE PATH PROBLEM IN WIRELESS SENSOR NETWORKS 112 4.2 Preliminaries and problem formulation .1 The truncated directional coverage model .2 The accumulative sensing intensity .4 Minimal exposure path .1 A novel characteristic of FEA algorithm .7 Family system based evolutionary algorithm .1 The performance of FEA when using different A and D .2 The performance of FEA when using different p min and pmax values .3 Comparison between FEA and previous algorithm in OE-MEP problem .4 Comparison between FEA and GA-MEP. 133 CONCLUSIONS AND FUTURE WORKS 134 PUBLICATIONS 137 BIBLIOGRAPHY 138 vi ABBREVIATIONS No.

Abbreviation Meaning 1 WSNs Wireless Sensor Networks 2 IoT Internet Of Thing 3 ROI Region Of Interest 4 BC Barrier Coverage 5 MEP Minimal Exeposure Path 6 PSO Particle Swarm Optimization 7 NFE Numerically Function Extreme 8 MWSN Mobile Wireless Sensor Networks 9 GPSO Gravitation Partical Swarm Optimization 10 HGA Hybrid Genetic Algorithm 11 FEA Family Evolution Algorithm 12 HoWSNs Homogeneous Wireless Sensor Networks 13 HeWSNs Heterogeneous Wireless Sensor Networks 14 SWSN Static Wireless Sensor Networks 15 CO Combinatorial Optimization 16 TSP Travelling Salesman Problem 17 QAP Quadratic Assignment Problem 18 ACO Ant Colony Optimization 19 EC Evolution Computation 20 ILS Iterated Local Search 21 TS Tabu Search 22 GA Genetic Algorithm 23 LS Local Search 24 HeWMSN Heterogeneous Wireless Multimedia Sensor Networks 25 GAMEP Genetic Algorithm Minimal Exposure Path 26 HPSO-MMEP Hybrid Particle Swarm Mobile MEP 27 GA-MEP Genetic Algorithm for Minimal Exposure Path 28 GB-MEP Grid Based Algorithm for Minimal Exposure Path 29 HEA Hybrid Evolution Algorithm 30 MMEP Mobile Minimal Exposure Path vii LIST OF TABLES Table 1 Comparative table of related works on MEP problem .1 Evolution process versus solving an optimization problem .1 Experimental parameters for attenuated disk model and truncated atten- uated disk model .2 Parameters setting for GAMEP .3 Experimental parameters for HPSO-MMEP algorithm .4 Parameters setting for HPSO .5 Different version of HPSO-MMEP using different genetic operators .6 Computation results of HPSO-MMEP in comparison with GAMEP in uniform distribution of sensors (Mev: minimal exposure value, Sd: standard deviation) .7 Computation results of HPSO-MMEP in comparison with GAMEP in Gauss distribution of sensors (Mev: minimal exposure value, Sd: standard devi- ation) .8 Experimental parameters of probabilistic .9 Experimental parameter of GA-MEP .10 Experimental Parameter of HGA-NFE .11 The comparison minimal exposure value, computation time and saw-tooth degree between GA-MEP and GB-MEP when using different subinterval Δs, the topology used is u 50 1 (Mev: minimal exposure value; Time(s): computation time per unit second; Dst: saw-tooth degree) .12 The minimal exposure value obtain from GB-MEP and the best solution of GA-MEP when threshold A varies from 3 to 7 on the topology used is u 50 1 (GB- Mev: the minimal exposure value obtains by GB-MEP; GA-Mev: the minimal exposure value obtains by GA-MEP) .13 Computation time comparison of OGB and GB-MEP when subinterval Δs varies from 5 down-to 0.14 The best minimal exposure value, running time and saw-tooth degree obtained from GA-MEP1, GA-MEP2 and GA-MEP on topology u 30 1, u 40 1, u 50 1, u 60 1, u 70 1, u 80 1, u 90 1 and u 100 1.15 Result on Sign test for pairwise comparisons between Minimal Exposure values obtained by GA-MEP and HGA-NFE (Mev: the minimal exposure value) 76 Table 2.16 Comparison of experimental results between GB-MEP and GA-MEP (Num: number of sensors, Ord: the order of the topology, Mev: the minimal exposure value, Time: the computation time, Sd: standard deviation, Dst: the saw-tooth degree, BMev: best minimal exposure value, AMev: Average minimal exposure value) .1 Experiment instance for homogeneous binary - Dataset 1 .2 Experiment instance for heterogeneous binary - Dataset 2 .3 Experimental instances for homogeneous network using attenuated model - Dataset 3 .4 Parameters for HEA .5 Parameters setting for GPSO .6 Operators setting for four versions of HEA .7 Comparison between four HEA versions when running on the Dataset 1 (Heterogeneous, Binary) (Mev - Minimal exposure value, Time - Computation time (second)) .8 Parameters setting for four versions of GPSO .9 Comparison between four versions of GPSO when running on the Dataset 3 (Heterogeneous, Binary) (Mev - Minimal exposure value, Time - Computation time (second)) .10 Comparison between HEA, GPSO and previous algorithms when running on Dataset 1 (Homogeneous - Binary) (Mev- Minimal exposure value, Time- Computational time (second)) .11 Comparison between HEA, GPSO and previous algorithms when running on Dataset 2 (Heterogeneous - Binary) (Mev- Minimal exposure value, Time- Computational time (second)) .12 Comparison between HEA, GPSO and previous algorithms when run-ning on Dataset 3 (Homogeneous - Attenuated) (Mev - Minimal exposure value, Time - Computational time (second)) .13 Comparison between HEA and HGA-NFE when using di fferent Δ x values (Mev - Minimal exposure value, Time - Computational time (second)) .14 Comparison between HPSO and GPSO when using di fferent Δ x values (Mev - Minimal exposure value, Time - Computational time (second)) .1 Parameters for FEA .2 The Minimal exposure value (Mev), the computational time (sec) and the standard deviation (Std) of FEA when using di fferent p min and pmax values with topology Data 3 0. 128 x LIST OF FIGURES Figure 1 Examples of area coverage (a), point coverage (b), and barrier coverage (c) 2 Figure 2 Illustration of a general minimal exposure problem in WSNs .1 Demonstration of acoustic sensor .2 Illustration of an sensor node .3 Illustration of (a) the Boolean disk coverage model in which the red stars are the target points respectively belonging inner and outer the green sensing area of a sensor, (b) the truncated attenuated coverage model .4 Demonstration of region of interest and crossing path .5 Illustration of crossing path types .6 Demonstration of sensor network scenarios: (a) single-hop, heterogeneous, stationary network; (b) multi-hop, homogeneous, stationary network; (c) multi- hop, heterogeneous, stationary network; (d) single-hop, homogeneous, stationary network with a mobile sink .7 Illustration of local search using a binary representation of solutions, a flip move operator, and the best neighbor selection strategy. The objective function 3 2 to maximize is x − x + x. The final local optima found is x = (11110), starting from the solution x0 = (11010).8 Illustration of local search behavior in a given landscape .9 Demonstration of main principles of P-metaheuristic .10 A generation in evolutionary algorithms .11 Genotype versus phenotype in evolutionary algorithms.12 Illustration of particle swarm with their associated positions and veloc- ities.

At each iteration, a particle moves from one position to another in the decision space. PSO uses no gradient information during the search.13 Demonstration of movement of a particle and the velocity update.1 Illustration of (a) the attenuated disk model; (b) the truncated attenuated disk model .2 Demonstration of input and output data .3 Illustration of individual representation of GAMEP .4 Illustration of the single-point crossover .5 Illustration of the mutation operator .6 Individual representation for HPSO-MMEP .7 Red stars are the control points that drives the path .8 Illustration of the crossover operator of HPSO-MMEP .9 Mutation operators: (a) Inverse mutation; (b) Symmetric mutation .10 Sensor trajectory: (a) Rectangle trajectory; (b) Random point trajectory 43 Figure 2.11 Effect of Δs on minimal exposure value (a); computation time (b) of HPSO-MMEP.12 Effect of the genetic operators on the minimal exposure value and the computation time among different versions of HPSO-MMEP .13 Comparison of the minimal exposure value between random and control- point initialization methods: (a) Gauss distribution (b) Uniform distribution .14 Comparison between HPSO-MMEP and HPSO algorithm .15 Effects of the speed of intruder on the minimal exposure value from GAMEP (a) and HPSO-MMEP (b) .16 Movement of an intruder on grids .18 Execution of creating an individual in sensor field < .19 Demonstration of executing ALX − α crossover operator .20 An example of the M SP B crossover operator .21 Demonstration of the Gene-removal mutation operator .22 The computation of the saw-tooth degree .23 The chart presents the minimal exposure values, the computation times and the saw tooth degrees of GB-MEP and GA-MEP when using di fferent subin- terval Δs values on topology u 50 1.24 The chart presents the minimal exposure values obtained from GA-MEP when using different values of threshold A on topology u 50 1 .25 Comparison of minimal exposure values between GA-MEP and GB-MEP when using: (a) Uniform distribution method, (b) Gaussian distribution method, (c) Exponential distribution method .