Các Thuật Toán Tìm Đường Xâm Nhập Có Khả Năng Bị Phát Hiện Nhỏ Nhất Trong Mạng Cảm Biến Dây

Trong bối cảnh hiện đại, thuật toán tìm đường xâm nhập trong mạng cảm biến trở thành một chủ… 162 trang · Hanoi University of Science and Technology · 2020.

• 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: Thuật Toán Tìm Đường Xâm Nhập Trong Mạng Cảm Biến: Giải Pháp Ít Bị Phát Hiện
• Loại tài liệu: luận án
• Năm xuất bản: 2020
• Địa điểm: Hanoi

Mục lục chi tiết

• DECLARATION OF AUTHORSHIP
• ACKNOWLEDGEMENT
• CONTENTS
• SYMBOLS
• LIST OF TABLES
• LIST OF FIGURES
• 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 the 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 values
• 4.8. The performance of FEA when using different pmin 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. Giới thiệu về thuật toán tìm đường xâm nhập

Trong bối cảnh hiện đại, thuật toán tìm đường xâm nhập trong mạng cảm biến trở thành một chủ đề quan trọng trong lĩnh vực an ninh mạng. Mạng cảm biến không dây (WSNs) được sử dụng rộng rãi trong nhiều ứng dụng, từ giám sát quân sự đến theo dõi môi trường. Việc phát hiện xâm nhập là một thách thức lớn, đặc biệt khi các kẻ tấn công cố gắng xâm nhập mà không bị phát hiện. Các giải pháp bảo mật hiện tại thường không đủ hiệu quả trong việc phát hiện các hành vi xâm nhập tinh vi. Do đó, việc phát triển các giải pháp bảo mật mới, ít bị phát hiện là cần thiết. Các thuật toán tối ưu hóa, như thuật toán di truyền và thuật toán bầy đàn, đã được áp dụng để giải quyết vấn đề này, giúp tìm ra các đường đi tối ưu cho các kẻ xâm nhập mà không bị phát hiện.

1.1. Tầm quan trọng của việc phát hiện xâm nhập

Phát hiện xâm nhập trong mạng cảm biến là một yếu tố quan trọng để đảm bảo an ninh. Các kẻ tấn công có thể lợi dụng các lỗ hổng trong hệ thống để xâm nhập và đánh cắp dữ liệu. Việc phát hiện sớm các hành vi xâm nhập giúp ngăn chặn thiệt hại nghiêm trọng. Các nghiên cứu đã chỉ ra rằng việc sử dụng các thuật toán thông minh có thể cải thiện đáng kể khả năng phát hiện xâm nhập. Các giải pháp bảo mật hiện tại cần được cải tiến để đối phó với các phương thức tấn công ngày càng tinh vi.

II. Các phương pháp tối ưu hóa trong tìm đường xâm nhập

Các phương pháp tối ưu hóa như thuật toán di truyền và thuật toán bầy đàn đã được áp dụng để giải quyết vấn đề tìm đường xâm nhập trong mạng cảm biến. Những phương pháp này cho phép tìm kiếm các giải pháp tối ưu trong không gian lớn mà không cần phải kiểm tra từng khả năng. Tối ưu hóa không chỉ giúp tìm ra đường đi hiệu quả mà còn giảm thiểu khả năng bị phát hiện. Việc áp dụng các phương pháp này trong việc phát hiện xâm nhập đã cho thấy hiệu quả cao trong việc cải thiện an ninh mạng.

2.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 tối ưu hóa phổ biến nhất. Nó mô phỏng quá trình chọn lọc tự nhiên để tìm ra giải pháp tốt nhất cho vấn đề. Trong bối cảnh tìm đường xâm nhập, thuật toán này có thể được sử dụng để xác định các đường đi tối ưu cho kẻ xâm nhập, từ đó giảm thiểu khả năng bị phát hiện. Các nghiên cứu đã chỉ ra rằng thuật toán di truyền có thể cải thiện đáng kể hiệu suất phát hiện xâm nhập trong mạng cảm biến.

2.2. Thuật toán bầy đàn

Thuật toán bầy đàn, như thuật toán bầy đàn hạt (PSO), là một phương pháp tối ưu hóa khác được sử dụng trong tìm đường xâm nhập. PSO 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. Trong bối cảnh này, PSO có thể giúp xác định các đường đi ít bị phát hiện nhất cho kẻ xâm nhập. Việc áp dụng PSO trong các nghiên cứu đã cho thấy khả năng tìm kiếm hiệu quả và nhanh chóng, giúp cải thiện an ninh cho mạng cảm biến.

III. Đánh giá và ứng dụng thực tiễn

Việc phát triển các giải pháp bảo mật cho mạng cảm biến không dây là rất cần thiết trong bối cảnh an ninh mạng ngày càng phức tạp. Các thuật toán như thuật toán di truyền và PSO không chỉ giúp tìm ra các đường đi tối ưu mà còn giảm thiểu khả năng bị phát hiện. Các nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp này có thể cải thiện đáng kể khả năng phát hiện xâm nhập. Điều này có ý nghĩa quan trọng trong việc bảo vệ dữ liệu và thông tin nhạy cảm trong các ứng dụng thực tiễn.

3.1. Ứng dụng trong quân sự

Trong lĩnh vực quân sự, việc phát hiện xâm nhập là rất quan trọng. Các mạng cảm biến được sử dụng để theo dõi và phát hiện các hoạt động xâm nhập. Việc áp dụng các thuật toán tối ưu hóa giúp cải thiện khả năng phát hiện và bảo vệ thông tin nhạy cảm. Các nghiên cứu đã chỉ ra rằng việc sử dụng các phương pháp này có thể giúp phát hiện kẻ xâm nhập một cách hiệu quả hơn.

3.2. Ứng dụng trong y tế

Trong lĩnh vực y tế, các mạng cảm biến được sử dụng để theo dõi sức khỏe bệnh nhân. Việc phát hiện xâm nhập có thể giúp bảo vệ thông tin y tế nhạy cảm. Các giải pháp bảo mật được phát triển từ các thuật toán tối ưu hóa có thể giúp bảo vệ dữ liệu bệnh nhân khỏi các kẻ tấn công. Điều này có ý nghĩa quan trọng trong việc đảm bảo an toàn cho thông tin y tế.

Nội dung chính

Tổng quan luận án

Luận án tiến sĩ với đề tài "Approximate algorithms for solving the minimal exposure path problems in wireless sensor networks" (Các thuật toán xấp xỉ giải quyết các bài toán đường phơi lộ tối thiểu trong mạng cảm biến không dây) được thực hiện bởi nghiên cứu sinh Nguyễn Thị Mỹ Bình, dưới sự hướng dẫn khoa học của PGS. TS. Huỳnh Thị Thanh Bình và PGS. TS. Nguyễn Đức Nghĩa, chuyên ngành Khoa học Máy tính (mã số: 9480101) tại Trường Công nghệ Thông tin và Truyền thông, Trường Đại học Bách khoa Hà Nội vào năm 2020.

Trong sự phát triển của Internet vạn vật (Internet of Things - IoTs), mạng cảm biến không dây (Wireless Sensor Networks - WSNs) đóng vai trò nền tảng thu thập dữ liệu và giám sát môi trường. Đánh giá chất lượng bao phủ là bài toán cốt lõi của mạng WSNs, được chia thành ba nhóm: bao phủ điểm (point coverage), bao phủ diện tích (area coverage) và bao phủ rào (barrier coverage). Đối với bài toán phát hiện xâm nhập trong các ứng dụng an ninh, quân sự, bảo vệ biên giới hoặc phòng chống thiên tai, bao phủ rào là giải pháp tối ưu giúp tiết kiệm số lượng nút cảm biến so với bao phủ toàn diện tích. Bài toán đường phơi lộ tối thiểu (Minimal Exposure Path - MEP) là dạng mở rộng cao cấp của bao phủ rào, nhằm tìm một đường di chuyển xuyên qua vùng cảm biến sao cho mức độ phơi lộ tích lũy của đối tượng đối với các nút cảm biến là nhỏ nhất, đồng nghĩa với xác suất bị phát hiện đạt mức thấp nhất.

Theo trình bày của tác giả, hầu hết các nghiên cứu trước đây về bài toán MEP đều đặt trong các giả định lý tưởng hóa: mạng cảm biến cố định tĩnh, mô hình cảm nhận đĩa nhị phân hình học không nhiễu, mạng đồng nhất và không gian giám sát hoàn toàn không có chướng ngại vật. Những giả định này tạo ra khoảng cách lớn giữa lý thuyết và việc triển khai thực tế. Do bài toán MEP thuộc lớp bài toán NP-Khó (NP-Hard), việc tìm kiếm đường đi tối ưu toàn cục bằng các phương pháp giải tích chính xác là không khả thi về thời gian tính toán.

Mục tiêu nghiên cứu tổng thể của luận án bao gồm 4 nội dung cụ thể:

1. Xây dựng mô hình toán học và thiết kế thuật toán metaheuristic giải quyết bài toán đường phơi lộ tối thiểu trong mạng cảm biến không dây di động (MWSNs), ký hiệu là bài toán MMEP.
2. Xây dựng định nghĩa độ phơi lộ mới và phát triển các thuật toán giải quyết bài toán đường phơi lộ tối thiểu dưới mô hình cảm nhận xác suất có nhiễu (PM-based-MEP).
3. Thiết lập mô hình bài toán tối ưu và đề xuất các thuật toán xấp xỉ giải quyết bài toán đường phơi lộ tối thiểu trong mạng cảm biến đa phương tiện định hướng không đồng nhất (HeWMSNs), ký hiệu là HM-MEP.
4. Xây dựng mô hình hình học vật cản tùy ý và phát triển giải thuật tiến hóa giải quyết bài toán đường phơi lộ tối thiểu né tránh vật cản (OE-MEP) trong môi trường thực tế.

Đối tượng và phạm vi nghiên cứu:

• Đối tượng nghiên cứu: Các mô hình toán học của bài toán đường phơi lộ tối thiểu và các thuật toán xấp xỉ metaheuristic (giải thuật di truyền, tối ưu hóa bầy đàn, thuật toán tiến hóa kết hợp tìm kiếm cục bộ).
• Phạm vi không gian: Không gian mạng cảm biến hai chiều (2-Dimension) với vùng quan tâm hình dải mở (open rectangular belt) hoặc dải đóng, có xét đến các loại nút cảm biến tĩnh, di động, cảm biến đa hướng (omni-directional), cảm biến định hướng (directional) và môi trường chứa vật cản đa giác tùy ý.
• Phạm vi thời gian: Khảo sát đối tượng xâm nhập di chuyển trong khoảng thời gian $[0, T]$ từ điểm xuất phát $B(0, y_B)$ đến điểm đích $E(L, y_E)$ trên hai biên đối diện của vùng giám sát.

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

Luận án đã hệ thống hóa các công trình nghiên cứu tiêu biểu về bài toán bao phủ rào và đường phơi lộ tối thiểu trong mạng cảm biến không dây, phân loại theo ba hướng tiếp cận chính:

1. Hướng tiếp cận hình học tính toán (Computational Geometry - Sơ đồ Voronoi): Meguerdichian và cộng sự (2001a, 2001b) là những người đầu tiên định nghĩa độ phơi lộ (exposure) bằng tích phân hàm cảm nhận dọc theo quỹ đạo di chuyển của đối tượng, đồng thời sử dụng sơ đồ Voronoi để tìm đường vi phạm tối đa (Maximal Breach Path - MBP) và đường phơi lộ tối thiểu (MEP). Megerian và cộng sự (2005) mở rộng phương pháp Voronoi cho mô hình suy hao. Hạn chế của hướng này là chỉ tính toán được đối với mô hình cảm nhận bởi cảm biến gần nhất (closest-sensor intensity), không giải quyết được mô hình tích lũy toàn bộ cảm biến (all-sensors intensity), không tối ưu khi điểm đầu và điểm cuối không thuộc cạnh Voronoi, và hoàn toàn không áp dụng được cho mạng nút cảm biến không đồng nhất (heterogeneous).

2. Hướng tiếp cận dựa trên lưới (Grid-based approach): Các tác giả trong các công trình từ [39] đến [43] đã rời rạc hóa vùng cảm biến liên tục thành lưới các ô vuông, gán trọng số cho từng cạnh của lưới tương ứng với giá trị phơi lộ, sau đó quy bài toán về tìm đường đi ngắn nhất trên đồ thị bằng thuật toán Dijkstra. Hạn chế căn bản của phương pháp lưới là sự đánh đổi giữa kích thước ô lưới và chi phí tính toán; nếu lưới mịn để tăng độ chính xác thì thời gian tính toán tăng theo cấp số nhân; ngoài ra, quỹ đạo của vật thể bị hạn chế trong các hướng cố định của lưới, không phản ánh chuyển động thực tế.

3. Hướng tiếp cận dựa trên Metaheuristic / Sinh học: Các nghiên cứu [45] (sử dụng Particle Swarm Optimization - PSO) và [46] (sử dụng Genetic Algorithm - GA) chuyển đổi MEP thành bài toán tìm cực trị hàm số thực nghiệm (Numerically Function Extreme - NFE) bằng cách cố định hoành độ $x$ và tối ưu tập tung độ $y$. Tuy nhiên, do hàm mục tiêu phi tuyến cao và không gian nhiều chiều, các thuật toán này sinh ra nghiệm có dạng răng cưa (saw-tooth jumping effect). Các toán tử điều chỉnh như toán tử chiếu (projection operator) trong PSO hay toán tử đảo ngược (upside-down operator) trong GA chưa loại bỏ triệt để độ răng cưa và đòi hỏi chi phí tính toán rất lớn.

Về phương diện mạng cảm biến di động, nghiên cứu của Zhang và cộng sự [47] là công trình hiếm hoi khảo sát bài toán MEP nhưng chỉ giới hạn trong mạng lai gồm cả nút tĩnh và nút động bằng sơ đồ Voronoi, không thể khái quát hóa cho mạng toàn bộ nút di động hoặc mạng không đồng nhất.

Công trình nghiên cứu	Phương pháp sử dụng	Mô hình mạng áp dụng
Meguerdichian và cs. [35], [37], [39], [48]	Sơ đồ Voronoi / Grid-based	Mạng tĩnh (Static WSNs)
Veltri và cs. [36]	Sơ đồ Voronoi	Mạng tĩnh và Mạng di động
Chen và cs. [41], Wang và cs. [43]	Grid-based	Mạng tĩnh (Static WSNs)
Bao và cs. [42]	Grid-based	Mạng tĩnh và Mạng di động
Li và cs. [45], Wang và cs. [46]	Metaheuristic (PSO, GA)	Mạng tĩnh (Static WSNs)
Zhang và cs. [47]	Sơ đồ Voronoi	Mạng lai tĩnh - di động

Khoảng trống học thuật mà luận án lựa chọn giải quyết là khắc phục triệt để các hạn chế của những nghiên cứu đi trước bằng cách: đưa yếu tố thời gian vào mô hình phơi lộ trong mạng di động; tích hợp nhiễu môi trường vào mô hình cảm nhận xác suất; tối ưu hóa đường phơi lộ trong mạng cảm biến đa phương tiện định hướng không đồng nhất; và mô hình hóa đường đi tránh chướng ngại vật đa giác phức tạp, kết hợp xây dựng các thuật toán metaheuristic tiên tiến nhằm triệt tiêu hiện tượng răng cưa và giảm thời gian thực thi.

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

Luận án sử dụng các hệ thống lý thuyết, mô hình và công cụ phân tích sau:

1. Khung lý thuyết và mô hình cảm nhận:

• Mô hình cảm nhận đĩa nhị phân (Boolean disk coverage model): $f(d(s_i, l)) = 1$ nếu khoảng cách Euclid $d(s_i, l) \le r$, ngược lại bằng $0$.
• Mô hình cảm nhận đĩa suy hao (Attenuated disk coverage model): $f(d(s_i, l)) = C / d^\lambda(s_i, l)$, với $\lambda$ là số mũ suy hao và $C$ là hằng số.
• Mô hình cảm nhận đĩa suy hao bị cắt (Truncated attenuated disk coverage model): $$f(d(s_i, l)) = \begin{cases} 1 & \text{nếu } d(s_i, l) \le r_1 \ e^{-\alpha [d(s_i, l) - r_1]^\beta} & \text{nếu } r_1 < d(s_i, l) \le r_2 \ 0 & \text{ngược lại} \end{cases}$$ trong đó $r_1$ là bán kính cảm nhận chắc chắn, $r_2$ là bán kính cảm nhận cực đại, $r_2 - r_1$ là vùng không chắc chắn, $\alpha$ và $\beta$ là các hệ số đặc tính vật lý.
• Mô hình cảm nhận định hướng (Directional sensing model): Góc mở cảm nhận (Field of View - FoV) giới hạn bởi góc hướng $2\theta$ và vector hướng cảm nhận $\vec{V}_i$.
• Mô hình cường độ cảm nhận trường: Cường độ tích lũy toàn bộ nút $I(l) = \sum_{i=1}^N f(d(s_i, l))$ và cường độ cảm biến gần nhất $I(l) = f(d(s_i^*, l))$.
• Mô hình phơi lộ tích lũy theo thời gian trong mạng di động: $$E(\wp, T) = \int_0^T I(l(t)) dt \approx \sum_{k=1}^{T/\Delta t} \sum_{i=1}^N f(d(s_i(k\Delta t), l(k\Delta t)))$$

2. Phương pháp nghiên cứu thực tế:

• Phương pháp mô hình hóa toán học: Chuyển đổi các bài toán hình học liên tục thành bài toán tối ưu hóa tổ hợp và tối ưu cực trị hàm số thực nghiệm (NFE) có ràng buộc biên và hướng di chuyển.
• Phương pháp thiết kế thuật toán xấp xỉ: Ứng dụng các nguyên lý tối ưu hóa dựa trên quần thể (Population-based metaheuristics) gồm Giải thuật di truyền (Genetic Algorithm - GA) và Tối ưu hóa bầy đàn (Particle Swarm Optimization - PSO), kết hợp với kỹ thuật tìm kiếm cục bộ (Local Search) và lý thuyết hấp dẫn vật lý.
• Phương pháp thực nghiệm mô phỏng số: Xây dựng môi trường mô phỏng trên máy tính, tạo lập các tập dữ liệu thử nghiệm chuẩn (benchmarks) với các phân bố nút cảm biến: phân bố đều (Uniform distribution), phân bố chuẩn Gauss (Gaussian distribution) và phân bố mũ (Exponential distribution). Số lượng nút cảm biến thử nghiệm biến thiên từ 30 đến 100 nút; kích thước vùng quan sát $L \times W$; kiểm tra các bước rời rạc $\Delta s$ và các ngưỡng phân đoạn $A, D$.

3. Nguồn tư liệu và kỹ thuật đánh giá:

• Nguồn dữ liệu: Bộ dữ liệu đồ hình mạng cảm biến được sinh tự động theo các phân bố thống kê chuẩn trong miền 2D và các tập dữ liệu kiểm thử chuẩn từ các công trình công bố trước đây.
• Kỹ thuật phân tích: Đo lường giá trị phơi lộ tối thiểu tốt nhất (Best Minimal Exposure Value - BMev), giá trị phơi lộ trung bình (Average Minimal Exposure Value - AMev), độ lệch chuẩn (Standard Deviation - Sd), thời gian tính toán thực thi (Computation Time tính bằng giây), độ răng cưa của đường đi ($D_{st}$ - Saw-tooth Degree), và kiểm định thống kê phi tham số Sign Test để đánh giá mức độ tin cậy của các so sánh theo cặp.

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

Chương 1: Background

Chương 1 trình bày hệ thống kiến thức nền tảng về mạng cảm biến không dây, các kiến trúc mạng (mạng đồng nhất HoWSN, mạng không đồng nhất HeWSN, mạng tĩnh SWSN, mạng di động MWSN, truyền thông đơn chặng Single-Hop và đa chặng Multi-Hop), cũng như các định nghĩa cơ bản về vùng quan tâm (ROI), đường xuyên cắt (crossing path). Chương này phân tích chi tiết bản chất toán học của các bài toán tối ưu hóa liên tục và tối ưu hóa rời rạc (Combinatorial Optimization), chỉ rõ tính chất NP-Khó đòi hỏi việc tiếp cận bằng các thuật toán xấp xỉ. Nội dung chương đi sâu vào nguyên lý hoạt động của các thuật toán metaheuristic đơn lời giải (S-metaheuristic như Local Search) và dựa trên quần thể (P-metaheuristic như GA, PSO), cấu trúc nhiễm sắc thể (Genotype) và kiểu hình (Phenotype), các toán tử lai ghép, đột biến, chiến lược chọn lọc, cập nhật vận tốc và vị trí hạt theo công thức: $$v_i(t) = v_i(t-1) + \rho_1 C_1 (p_i - x_i(t-1)) + \rho_2 C_2 (p_g - x_i(t-1))$$ $$x_i(t) = x_i(t-1) + v_i(t)$$ trong đó $C_1, C_2$ là các hệ số học tập nhận thức và xã hội, $\rho_1, \rho_2$ là các biến ngẫu nhiên trong đoạn $[0, 1]$.

Chương 2: Minimal Exposure Path Problems in Omni-Directional Sensor Networks

Chương 2 tập trung giải quyết hai bài toán lớn trong mạng cảm biến đa hướng:

1. Bài toán MEP trong mạng cảm biến di động (MMEP): Tác giả đề xuất mô hình tính toán phơi lộ phụ thuộc thời gian $E(\wp, T)$ khi các nút cảm biến di chuyển theo quỹ đạo định trước (quỹ đạo chữ nhật hoặc quỹ đạo ngẫu nhiên) với vận tốc $v_s$, còn đối tượng xâm nhập di chuyển với vận tốc cực đại $v_I$. Để giải quyết bài toán, tác giả đề xuất hai thuật toán:

• Thuật toán GAMEP: Giải thuật di truyền với toán tử lai ghép một điểm cắt và đột biến ngẫu nhiên.
• Thuật toán lai HPSO-MMEP: Kết hợp PSO với các toán tử di truyền, sử dụng phương pháp khởi tạo cá thể dựa trên các điểm điều khiển (control-point initialization), toán tử đột biến nghịch đảo (inverse mutation) và đột biến đối xứng (symmetric mutation). Kết quả thực nghiệm trên các phân bố nút cảm biến đều và Gauss chứng minh HPSO-MMEP vượt trội hơn GAMEP về giá trị phơi lộ tối thiểu và độ ổn định khi thay đổi kích thước bước rời rạc thời gian $\Delta s$ cũng như vận tốc kẻ xâm nhập.

2. Bài toán MEP dưới mô hình cảm nhận xác suất có nhiễu (PM-based-MEP): Tác giả định nghĩa hàm cảm nhận xác suất thực tế và phát triển hai giải thuật:

• Thuật toán GB-MEP: Cải tiến thuật toán dựa trên lưới truyền thống (OGB), tối ưu hóa việc phân chia lưới và giảm đáng kể thời gian chạy khi bước chia lưới $\Delta s$ thay đổi từ $5$ xuống $0.5$.
• Thuật toán GA-MEP: Thiết kế biểu diễn cá thể mới, sử dụng hai toán tử lai ghép chuyên biệt $ALX-\alpha$ và $MSPB$, kết hợp toán tử đột biến loại bỏ gen thừa (Gene-removal mutation).

Thuật toán	Đồ hình kiểm thử ($u_N^1$)	Giá trị phơi lộ ($Mev$)	Thời gian chạy (giây)	Độ răng cưa ($D_{st}$)
GA-MEP	$u_{50}^1$ ($\Delta s = 0.5$)	1.8241	14.28	0.0412
GB-MEP	$u_{50}^1$ ($\Delta s = 0.5$)	2.1053	48.91	0.1580
HGA-NFE	$u_{50}^1$ ($\Delta s = 0.5$)	2.3418	86.52	0.4219
GA-MEP	$u_{100}^1$	3.4120	28.64	0.0521
HGA-NFE	$u_{100}^1$	4.8912	165.30	0.5187

Kết quả kiểm định Sign Test giữa GA-MEP và HGA-NFE trên các phân bố Đều, Gauss và Mũ với quy mô mạng từ 30 đến 100 nút khẳng định GA-MEP đạt giá trị phơi lộ thấp hơn có ý nghĩa thống kê và triệt tiêu hầu như hoàn toàn độ răng cưa $D_{st}$.

Chương 3: Minimal Exposure Path Problem in Wireless Multimedia Sensor Networks

Chương 3 mở rộng bài toán MEP cho mạng cảm biến đa phương tiện không dây không đồng nhất (HeWMSNs), ký hiệu là bài toán HM-MEP. Các nút cảm biến có góc mở cảm nhận hình nón (FoV), hướng cảm nhận thay đổi và thông số kỹ thuật khác nhau, áp dụng cả mô hình nhị phân (Boolean) và mô hình suy hao định hướng (Attenuated directional sensing model).

Để tìm đường phơi lộ tối thiểu trong không gian trạng thái phức tạp này, tác giả đề xuất hai thuật toán metaheuristic tiên tiến:

• Thuật toán HEA (Hybrid Evolutionary Algorithm): Kết hợp giải thuật tiến hóa với kỹ thuật tìm kiếm cục bộ (Local Search), tích hợp cơ chế khởi tạo cá thể HEA và hai toán tử lai ghép chuyên dụng $LC$ (Linear Crossover) và $\gamma C$ (Gamma Crossover).
• Thuật toán GPSO (Gravitation Particle Swarm Optimization): Thuật toán tối ưu bầy đàn mới kết hợp lý thuyết lực hấp dẫn vạn vật, trong đó gia tốc và vận tốc dịch chuyển của hạt bị chi phối bởi các vector lực hấp dẫn phát ra từ vị trí các nút cảm biến lân cận.

Bộ dữ liệu kiểm thử	Thuật toán	Giá trị phơi lộ ($Mev$)	Thời gian tính toán (s)	Độ lệch chuẩn ($Sd$)
Dataset 1 (Homogeneous - Binary)	HEA	0.0000	12.45	0.0000
Dataset 1 (Homogeneous - Binary)	GPSO	0.0000	15.10	0.0000
Dataset 1 (Homogeneous - Binary)	HGA-NFE	0.4125	62.80	0.1240
Dataset 2 (Heterogeneous - Binary)	HEA	0.1524	18.32	0.0115
Dataset 2 (Heterogeneous - Binary)	GPSO	0.1601	21.40	0.0142
Dataset 2 (Heterogeneous - Binary)	HPSO	0.5890	85.12	0.0890
Dataset 3 (Heterogeneous - Attenuated)	HEA	1.1240	25.60	0.0310
Dataset 3 (Heterogeneous - Attenuated)	GPSO	1.1450	28.95	0.0354
Dataset 3 (Heterogeneous - Attenuated)	HGA-NFE	2.8710	142.30	0.2150

Kết quả so sánh trên 3 bộ dữ liệu (Dataset 1, 2, 3) khẳng định HEA và GPSO đạt giá trị $Mev$ thấp hơn, tốc độ hội tụ nhanh hơn và độ lệch chuẩn nhỏ hơn rõ rệt so với các thuật toán tham chiếu trước đó (HGA-NFE, HPSO).

Chương 4: Obstacles-Evasion Minimal Exposure Path Problem in Wireless Sensor Networks

Chương 4 nghiên cứu bài toán tìm đường phơi lộ tối thiểu né tránh vật cản trong mạng cảm biến định hướng bị cắt (Truncated directional sensor network), ký hiệu là bài toán OE-MEP. Khi môi trường xuất hiện các vật cản đa giác tùy ý, tín hiệu cảm nhận của nút cảm biến bị hấp thụ và che khuất hoàn toàn bởi các cạnh của đa giác.

Tác giả đề xuất thuật toán FEA (Family System Based Evolutionary Algorithm - Thuật toán tiến hóa dựa trên hệ gia đình) với các cơ chế đặc thù:

• Toán tử chuẩn hóa (Normalization operator): Kiểm tra và sửa chữa cá thể; nếu đoạn đường đi cắt qua đa giác vật cản, toán tử sẽ tự động thay thế bằng đường vòng qua các đỉnh ngoài của vật cản để đảm bảo tính khả thi hình học.
• Toán tử lai ghép Leaning (Leaning crossover): Kết hợp các đoạn gen từ cá thể bố và cá thể mẹ để tạo ra cá thể con nằm gọn trong vùng an toàn giữa các vật cản.
• Toán tử đột biến lực đẩy (Push-Force mutation): Tác động các vector lực đẩy lên các gen (điểm điều khiển) để dịch chuyển đường đi ra xa các nút cảm biến và bề mặt vật cản.

Thực nghiệm đánh giá ảnh hưởng của các tham số $A, D$ (ngưỡng khoảng cách phân đoạn) và $p_{min}, p_{max}$ (xác suất đột biến) trên cấu trúc dữ liệu $Data_3^0$ cho thấy:

• Khi $p_{min} = 0.05, p_{max} = 0.2$, FEA đạt giá trị $Mev$ nhỏ nhất với độ lệch chuẩn $Std$ thấp nhất.
• So sánh trên các đồ hình chuẩn giữa FEA, GA-MEP và Grid-based method chứng minh: Grid-based method mất thời gian tính toán rất lớn và nghiệm thô; GA-MEP thường tạo ra đường đi va chạm vật cản nếu không có cơ chế sửa chữa; trong khi đó FEA luôn tìm được đường đi trơn tru, không va chạm, có giá trị phơi lộ $Mev$ thấp nhất và thời gian xử lý nhanh vượt bậc.

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

Luận án đã đạt được những kết quả và đóng góp mới về mặt lý luận khoa học cũng như thực tiễn ứng dụng như sau:

1. Đóng góp về lý thuyết và mô hình hóa:

• Xây dựng thành công 4 mô hình toán học mới mở rộng cho bài toán đường phơi lộ tối thiểu trong WSNs: MMEP (mạng cảm biến di động), PM-based-MEP (mô hình cảm nhận xác suất có nhiễu), HM-MEP (mạng cảm biến đa phương tiện định hướng không đồng nhất) và OE-MEP (môi trường chứa vật cản đa giác tùy ý).
• Đưa ra định nghĩa chính xác về mức độ phơi lộ tích lũy theo thời gian $E(\wp, T)$ trong mạng cảm biến di động, giải quyết triệt để sự thiếu hụt trong các nghiên cứu truyền thống vốn chỉ tích lũy theo chiều dài hình học.
• Chuyển đổi thành công các bài toán hình học liên tục phức tạp sang các bài toán tối ưu hóa phi tuyến nhiều chiều có ràng buộc, tạo cơ sở cho việc áp dụng các phương pháp metaheuristic hiện đại.

2. Đóng góp về thuật toán và kỹ thuật tối ưu:

• Đề xuất và cài đặt 7 thuật toán xấp xỉ metaheuristic chuyên biệt: GAMEP, HPSO-MMEP, GB-MEP, GA-MEP, HEA, GPSO và FEA.
• Thiết kế các toán tử di truyền và cơ chế tìm kiếm mới: toán tử lai ghép $ALX-\alpha$, $MSPB$, $LC$, $\gamma C$, Leaning crossover; toán tử đột biến nghịch đảo, đột biến đối xứng, Gene-removal mutation và Push-Force mutation; thuật toán tối ưu bầy đàn dựa trên lực hấp dẫn GPSO; toán tử chuẩn hóa tránh vật cản Normalization operator trong FEA.
• Khắc phục thành công hiện tượng nghiệm dạng răng cưa ($D_{st}$) và nâng cao đáng kể độ ổn định, tốc độ hội tụ so với các thuật toán công bố trước đây (như HGA-NFE, HPSO, OGB).

3. Đề xuất ứng dụng và giải pháp thực tiễn:

• Cung cấp công cụ tính toán và chỉ số đo lường giá trị phơi lộ tối thiểu giúp các nhà thiết kế mạng đánh giá chính xác chất lượng bao phủ rào, xác định "vùng yếu nhất" của hệ thống giám sát an ninh để bố trí bổ sung nút cảm biến tối ưu chi phí.
• Ứng dụng trực tiếp thuật toán FEA và HPSO-MMEP vào việc lập lộ trình xâm nhập an toàn cho các thiết bị tự hành (robot, UAV) di chuyển qua các vùng giám sát có chướng ngại vật phức tạp.

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

Hạn chế của luận án:

• Toàn bộ các mô hình bài toán và thuật toán chỉ mới được khảo sát trong không gian hai chiều (2D), chưa mở rộng cho không gian ba chiều (3D) của địa hình đồi núi hay không gian ngầm dưới nước.
• Trong bài toán MMEP, chuyển động của các nút cảm biến di động được giả định theo các quỹ đạo cố định định trước với vận tốc không đổi, chưa phản ánh đầy đủ các mô hình di chuyển ngẫu nhiên hoặc phản ứng thích nghi trong thực tế.
• Chưa tính toán đến yếu tố tiêu hao năng lượng truyền thông và chu kỳ bật/tắt (duty-cycling) của các nút cảm biến trong quá trình duy trì bao phủ rào.

Hướng phát triển tiếp theo được tác giả nêu ra:

• Mở rộng bài toán đường phơi lộ tối thiểu và phát triển các thuật toán metaheuristic cho mạng cảm biến không dây trong không gian 3 chiều (3-Dimension WSNs).
• Khảo sát bài toán MEP trong mạng cảm biến di động với các mô hình di chuyển tự do, ngẫu nhiên và tương tác thích nghi theo thời gian thực.
• Nghiên cứu bài toán tối ưu hóa đa mục tiêu: vừa tối thiểu hóa độ phơi lộ của đường xâm nhập, vừa tối ưu hóa mức tiêu thụ năng lượng và kéo dài tuổi thọ của toàn mạng cảm biến.

Giá trị tham khảo

Luận án là tài liệu tham khảo có giá trị cao cho các đối tượng học thuật và kỹ thuật:

• Nghiên cứu sinh, học viên cao học, giảng viên chuyên ngành Khoa học Máy tính, Kỹ thuật Mạng và Tối ưu hóa: Có thể tham khảo phương pháp mô hình hóa bài toán hình học liên tục sang bài toán NFE, kỹ thuật thiết kế các toán tử lai ghép/đột biến chuyên dụng và phương pháp phân tích thực nghiệm thống kê (Sign Test). Các chương 2, 3, 4 là nguồn tư liệu phong phú về giải thuật di truyền lai và tối ưu bầy đàn nâng cao.
• Kỹ sư phát triển hệ thống IoTs và mạng cảm biến không dây: Tham khảo mã giả và nguyên lý của các thuật toán GB-MEP, HEA, FEA để áp dụng trực tiếp vào việc đánh giá chất lượng bao phủ rào, kiểm định độ tin cậy của mạng cảm biến trong các dự án an ninh, quốc phòng và quan trắc môi trường.
• Chuyên gia điều khiển và lập lộ trình tự hành: Ứng dụng các thuật toán né tránh vật cản (FEA) và bầy đàn hấp dẫn (GPSO) trong việc xây dựng quỹ đạo di chuyển tối ưu cho robot hoặc phương tiện tự hành trong môi trường có chướng ngại vật và cảm biến giám sát.

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

1. Tại sao công thức tính độ phơi lộ truyền thống $E(\wp) = \int I(l) dl$ không thể áp dụng cho mạng cảm biến di động (MWSNs)? Trong mạng cảm biến tĩnh, cường độ cảm nhận tại một vị trí chỉ phụ thuộc tọa độ không gian hình học. Trong mạng di động, các nút cảm biến liên tục di chuyển khiến cường độ cảm nhận tại cùng một tọa độ thay đổi theo thời gian. Nếu áp dụng công thức cũ, khi một đối tượng đứng yên tại một điểm trong một khoảng thời gian $\phi$, giá trị phơi lộ tính ra sẽ bằng 0 (do vi phân quãng đường $dl = 0$), điều này hoàn toàn phi lý trong thực tế. Vì vậy, độ phơi lộ trong mạng di động bắt buộc phải tích lũy theo thời gian: $E(\wp, T) = \int_0^T I(l(t)) dt$.

2. Hiện tượng nghiệm răng cưa (saw-tooth effect) trong bài toán MEP là gì và giải thuật GA-MEP khắc phục bằng cách nào? Hiện tượng răng cưa xảy ra khi chuyển bài toán MEP sang dạng cực trị hàm số thực nghiệm (NFE), do hàm mục tiêu phi tuyến cao và nhiều chiều, các giá trị tung độ $y$ kế tiếp nhau trên đường đi bị dao động, nhảy bậc đột ngột tạo thành đường gấp khúc ziczac không tối ưu. GA-MEP khắc phục hiện tượng này bằng cách thiết kế biểu diễn cá thể mới, phối hợp hai toán tử lai ghép $ALX-\alpha$ và $MSPB$ cùng toán tử đột biến loại bỏ gen thừa (Gene-removal mutation), giúp làm trơn đường đi và giảm chỉ số $D_{st}$ xuống mức xấp xỉ 0.04.

3. Thuật toán GPSO trong Chương 3 hoạt động dựa trên nguyên lý vật lý nào? GPSO (Gravitation Particle Swarm Optimization) tích hợp định luật vạn vật hấp dẫn của Newton vào mô hình bầy đàn PSO. Vị trí của các nút cảm biến trong mạng đóng vai trò như các nguồn tạo ra lực hấp dẫn (hoặc lực đẩy). Khi các hạt tìm kiếm đường đi di chuyển trong không gian, vận tốc và gia tốc của hạt được cập nhật dựa trên tổng hợp các vector lực hấp dẫn từ các cảm biến lân cận, giúp hạt nhanh chóng thoát khỏi vùng có cường độ cảm nhận cao để tìm đường có mức phơi lộ thấp nhất.

4. Thuật toán FEA trong Chương 4 xử lý điều kiện đường đi cắt qua vật cản đa giác bằng cơ chế cụ thể nào? FEA sử dụng toán tử chuẩn hóa (Normalization operator). Khi kiểm tra một cá thể đường đi có các đoạn thẳng giao cắt với các cạnh của đa giác vật cản (khiến cá thể không hợp lệ), toán tử này sẽ tìm các đỉnh biên ngoài của vật cản gần nhất và thay thế đoạn giao cắt bằng chuỗi các đoạn thẳng vòng qua các đỉnh đó. Kết hợp với toán tử đột biến lực đẩy (Push-Force mutation), các điểm điều khiển của đường đi liên tục bị đẩy xa khỏi bề mặt vật cản và các nút cảm biến, đảm bảo đường đi luôn hợp lệ về mặt hình học.

Kết luận

Luận án tiến sĩ của tác giả Nguyễn Thị Mỹ Bình đã giải quyết một cách toàn diện bài toán đường phơi lộ tối thiểu (MEP) trong mạng cảm biến không dây thông qua 4 mô hình mở rộng sát thực tế: mạng di động, mô hình cảm nhận xác suất có nhiễu, mạng đa phương tiện định hướng không đồng nhất và môi trường có vật cản đa giác. Hệ thống các thuật toán metaheuristic xấp xỉ được đề xuất (nổi bật là HPSO-MMEP, GA-MEP, HEA, GPSO và FEA) đã thể hiện tính ưu việt rõ rệt về chất lượng nghiệm, độ mịn của đường đi và thời gian tính toán so với các phương pháp truyền thống. Công trình là tài liệu khoa học hoàn chỉnh, có giá trị học thuật và thực tiễn cao trong lĩnh vực tối ưu hóa mạng cảm biến và công nghệ IoTs.

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 Hanoi, 2020 luan an 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 luan an 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 co- supervisors, Associate Professor Huynh Thi Thanh Binh and Associate Professor Nguyen Duc Nghia. All the research results are presented in the dissertation which have never been published by others.

Hanoi, October 16, 2020 Ph. Student Nguyen Thi My Binh SUPERVISOR Asso. Huynh Thi Thanh Binh i luan an 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 co-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 difficulties 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 difficulties. 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, October 16, 2020 Ph. Student Nguyen Thi My Binh ii luan an 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 the MMEP problem. 34 iii luan an 2.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. 98 iv luan an 3.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 values .2 The performance of FEA when using different pmin and pmax values .