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

Tài liệu nghiên cứu Các thuật toán xấp xỉ 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, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên

• 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 về luận án

Trong kỷ nguyên vạn vật kết nối (Internet of Things - IoT) và hệ thống giám sát thông minh, Mạng cảm biến không dây (Wireless Sensor Networks - WSNs) giữ vai trò xương sống trong việc thu thập dữ liệu, giám sát không gian và bảo đảm an ninh biên giới, khu vực quân sự cũng như cảnh báo thiên tai. Trong các nghiên cứu đánh giá chất lượng mạng, bài toán Bao phủ rào cản (Barrier Coverage - BC) và đặc biệt là biến thể cấp cao của nó: Bài toán đường phơi nhiễm tối thiểu (Minimal Exposure Path - MEP) đóng vai trò then chốt. Luận án tiến sĩ của Nghiên cứu sinh Nguyễn Thị Mỹ Bình với đề tài "Approximate algorithms for solving the minimal exposure path problems in wireless sensor networks" (Chuyên ngành Khoa học máy tính, Mã số: 9480101, thực hiện tại Trường Công nghệ Thông tin và Truyền thông - Đại học Bách khoa Hà Nội dưới sự hướng dẫn của PGS.TS. Huỳnh Thị Thanh Bình và PGS.TS. Nguyễn Đức Nghĩa) là một công trình học thuật tiên phong, tái định hình căn bản phương pháp tiếp cận bài toán MEP trong không gian mạng cảm biến phức tạp.

                     KHÔNG GIAN NGHIÊN CỨU BÀI TOÁN MEP TRONG WSNs
                                          │
    ┌───────────────────────────┬─────────┴─────────────────────────┬───────────────────────────┐
    ▼                           ▼                                   ▼                           ▼
Mạng di động (MWSNs)     Mô hình xác suất & Nhiễu           Mạng đa phương tiện (WMSNs)   Môi trường có vật cản
   [MMEP Model]             [PM-based-MEP Model]                  [HM-MEP Model]               [OE-MEP Model]
    │                           │                                   │                           │
    ├─ Thuật toán GAMEP         ├─ Thuật toán GB-MEP                ├─ Thuật toán HEA           └─ Thuật toán FEA
    └─ Thuật toán HPSO-MMEP     └─ Thuật toán GA-MEP                └─ Thuật toán GPSO             (Leaning Crossover,
       (Control-points)            (Triệt tiêu răng cưa Dst)           (Trọng lực vạn vật)          Push-Force Mutation)

Khoảng trống nghiên cứu (Research Gap) lớn nhất trong y văn quốc tế tồn tại ở chỗ: phần lớn các nghiên cứu kinh điển giả định môi trường cảm biến phẳng, tĩnh (Static WSNs), cảm biến đẳng hướng lý tưởng (Boolean Disk Model), không có vật cản và tín hiệu không bị suy hao bởi nhiễu môi trường. Điều này tạo ra một "hố sâu ngăn cách" giữa mô hình toán học lý thuyết và triển khai thực tế. Luận án giải quyết triệt để 4 khoảng trống cụ thể:

1. Thiếu mô hình phơi nhiễm tích phân theo thời gian thực khi nút cảm biến chuyển động có quỹ đạo.
2. Sự bất cập của mô hình suy hao thực tế có nhiễu (Truncated Attenuated Model) kết hợp với hiện tượng nghiệm dao động răng cưa (saw-tooth effect).
3. Độ phức tạp tính toán khi tích hợp cảm biến đa phương tiện định hướng dị thể (Heterogeneous Directional Sensors).
4. Sự thiếu vắng khung giải thuật tối ưu hóa né tránh vật cản đa giác bất kỳ (Obstacle-Evasion) trong không gian giám sát liên tục.

Hệ thống câu hỏi nghiên cứu ($RQ$) và giả thuyết ($H$) được định hình chặt chẽ:

• $RQ_1$ & $H_1$: Làm thế nào để lượng hóa độ phơi nhiễm khi cả mục tiêu xâm nhập và nút cảm biến đều chuyển động? Giả thuyết cho rằng độ phơi nhiễm phụ thuộc vào trạng thái tích phân thời gian thay vì thuần túy hình học không gian, và giải thuật lai ghép giữa Tối ưu hóa bầy đàn hạt (Particle Swarm Optimization - PSO) với Giải thuật di truyền (Genetic Algorithm - GA) sẽ tìm ra đường xâm nhập tối ưu hơn phương pháp hình học giải tích.
• $RQ_2$ & $H_2$: Mô hình bao phủ xác suất có nhiễu ảnh hưởng ra sao đến tính trơn của đường MEP? Giả thuyết cho rằng việc tối ưu hóa hàm cực trị số (Numerical Function Extreme - NFE) bằng các toán tử di truyền chuyên biệt sẽ triệt tiêu bậc răng cưa ($D_{st}$) và hạ thấp giá trị phơi nhiễm ($M_{ev}$) so với thuật toán dựa trên lưới (Grid-based).
• $RQ_3$ & $H_3$: Trong mạng đa phương tiện định hướng dị thể (HeWMSN), làm thế nào để cân bằng giữa phân rã nghiệm và hội tụ? Giả thuyết khẳng định việc tích hợp quy luật vạn vật hấp dẫn vào PSO (Gravitation PSO - GPSO) sẽ ngăn chặn việc rơi vào cực trị địa phương.
• $RQ_4$ & $H_4$: Cấu trúc tiến hóa nào vượt qua được các rào cản vật lý đa giác phi quy tắc? Giả thuyết đề xuất hệ thống tiến hóa gia đình (Family Evolution Algorithm - FEA) cho phép chuẩn hóa cá thể vi phạm và tối ưu hóa quỹ đạo trong môi trường chướng ngại vật phức tạp.

Về quy mô và phạm vi nghiên cứu, luận án tiến hành thử nghiệm trên hàng ngàn topology cảm biến phân bố Đều (Uniform), Chuẩn (Gaussian) và Mũ (Exponential), với mật độ từ 30 đến 100 nút ($u_{30}^1$ đến $u_{100}^1$), kiểm chứng trên 3 bộ Dataset chuẩn quốc tế và môi trường mô phỏng tùy biến chuyên sâu.

Literature Review và Positioning

Khởi nguồn từ các công trình nền tảng của Meguerdichian et al. (2001, 2002) [35, 39] và Megerian et al. [38], bài toán tìm đường phơi nhiễm tối thiểu ban đầu được tiếp cận qua hai trường phái chính: Hình học tính toán (Computational Geometry dựa trên giản đồ Voronoi) và Rời rạc hóa không gian (Grid-based Graph Search bằng thuật toán Dijkstra). Meguerdichian et al. định nghĩa độ phơi nhiễm là tích phân đường của hàm cảm nhận dọc theo quỹ đạo $p(t)$: $$E(p(t), t_1, t_2) = \int_{t_1}^{t_2} I(l(t))\left|\frac{dl(t)}{dt}\right|dt$$

Tuy nhiên, y văn nhanh chóng bộc lộ những xung đột học thuật gay gắt:

                            TRANH LUẬN HỌC THUẬT VỀ BÀI TOÁN MEP
                                              │
        ┌─────────────────────────────────────┴─────────────────────────────────────┐
        ▼                                                                           ▼
TRƯỜNG PHÁI GIẢN ĐỒ VORONOI                                         TRƯỜNG PHÁI RỜI RẠC HÓA LƯỚI (GRID-BASED)
(Meguerdichian et al., 2001)                                        (Megerian et al., 2002; Wang et al.)
  ├─ Ưu điểm: Đảm bảo tối ưu cục bộ theo khoảng cách                   ├─ Ưu điểm: Dễ triển khai trên đồ thị Dijkstra
  └─ Nhược điểm cốt tử:                                                └─ Nhược điểm cốt tử:
     • Không tính được mô hình cường độ toàn mạng (All-sensor)            • Đánh đổi gay gắt giữa kích thước lưới (Δs) và độ chính xác
     • Không áp dụng được cho nút cảm biến dị thể                         • Hướng di chuyển bị giới hạn cơ học trên cạnh lưới
     • Thất bại khi điểm đầu/cuối không nằm trên cạnh Voronoi             • Chi phí tính toán bùng nổ trong không gian lớn

Khi chuyển dịch sang trường phái Metaheuristic, các nghiên cứu của Veltri et al. hay Huang et al. đã chuyển đổi MEP thành bài toán cực trị hàm số (NFE) bằng cách cố định hoành độ $x$ và tối ưu hóa tập tung độ $y$. Tuy nhiên, như luận án đã chỉ ra, việc áp dụng trực tiếp GA hoặc PSO chuẩn luôn dẫn đến nghiệm "nhảy giật răng cưa" (high saw-tooth degree $D_{st}$), làm mất tính khả thi khi áp dụng cho chuyển động cơ học của vật thể thực tế.

Đối với mạng di động (MWSNs), nghiên cứu hiếm hoi của Zhang et al. [47] chỉ dừng lại ở mô hình mạng lai (hybrid) kết hợp cảm biến tĩnh và di động, tiếp cận qua giản đồ Voronoi tĩnh để né tránh cảm biến động. Luận án của NCS. Nguyễn Thị Mỹ Bình định vị chính xác vị trí học thuật của mình khi vượt lên trên các giới hạn này: mô hình hóa toàn diện mạng thuần di động, tích hợp mô hình suy hao thực tế, cảm biến góc định hướng và không gian có chướng ngại vật phức tạp thông qua các giải thuật xấp xỉ tiến hóa đột phá.

Tiêu chí so sánh	Nghiên cứu Meguerdichian et al. [35]	Nghiên cứu Zhang et al. [47]	Luận án Nguyễn Thị Mỹ Bình (2020)
Mô hình mạng	Tĩnh, đẳng hướng thuần nhất	Lai (Tĩnh + Di động)	Động thuần nhất/dị thể, Đa phương tiện
Mô hình bao phủ	Boolean Disk & Attenuated lý tưởng	Boolean Disk	Truncated Attenuated có nhiễu, Directional
Môi trường	Không vật cản, liên tục	Không vật cản	Chứa vật cản đa giác bất kỳ (OE-MEP)
Phương pháp	Voronoi Diagram / Dijkstra	Voronoi động rời rạc	HPSO-MMEP, GA-MEP, HEA, GPSO, FEA
Hiện tượng răng cưa	Bị giới hạn trên cạnh Voronoi	Nghiệm gián đoạn	Kiểm soát và triệt tiêu hoàn toàn $D_{st}$

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mở rộng và thách thức lý thuyết bao phủ truyền thống bằng việc thiết lập 4 mô hình toán học giải tích mới:

1. Mô hình MMEP trong MWSNs: Bác bỏ công thức tích phân phi thời gian truyền thống. Trích dẫn nguyên văn từ luận án: "Exposure value should be formulated as the accumulation of sensing intensity over every state of the intruder. While position, or coordinates, determines the state of an intruder in static sensing field, time is the representation for intruder’s state in mobile sensor network." Công thức phơi nhiễm được tái cấu trúc: $$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. Mô hình PM-based-MEP: Tích hợp mô hình suy hao đĩa cắt cụt (Truncated Attenuated Disk Coverage Model) phản ánh chính xác tác động của tạp âm môi trường: $$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{trường hợp khác} \end{cases}$$ trong đó $r_2 - r_1$ là dải không chắc chắn (uncertain range), $\alpha, \beta$ là các tham số vật lý của cảm biến.
3. Mô hình HM-MEP: Xây dựng hàm cường độ cảm nhận suy hao định hướng (Attenuated Directional Sensing Model) tích hợp góc mở $\beta_0$, hướng quan sát $\vec{V}_i$, khoảng cách suy hao $\lambda_0$ và cường độ bao phủ tích lũy/gần nhất.
4. Mô hình OE-MEP: Xác lập điều kiện biên hình học nghiêm ngặt cho bài toán né tránh vật cản, chứng minh toán học sự gián đoạn của không gian tìm kiếm khi đường phơi nhiễm cắt qua các đa giác lồi/lõm.

                    MÔ HÌNH TOÁN HỌC CÁC BIẾN THỂ MEP TRONG LUẬN ÁN
                                          │
    ┌───────────────────────┬─────────────┴─────────────┬───────────────────────┐
    ▼                       ▼                           ▼                       ▼
MÔ HÌNH MMEP            MÔ HÌNH PM-BASED            MÔ HÌNH HM-MEP          MÔ HÌNH OE-MEP
(Mạng di động)          (Bao phủ xác suất)          (Mạng đa phương tiện)   (Né tránh vật cản)
Tích tích phân          Mô hình suy hao             Mô hình suy hao         Tích hợp vật cản
thời gian:              đĩa cắt cụt:                định hướng:             đa giác:
E = ∫ I(l(t))dt         e^{-α[d - r1]^β}            f(d, θ, V_i)            Ω \ ⋃ Obstacles

Khung phân tích độc đáo

Khung phân tích của luận án là sự giao thoa liên ngành giữa Lý thuyết Tối ưu hóa tổ hợp, Tính toán tiến hóa (Evolutionary Computation), Trí tuệ bầy đàn (Swarm Intelligence) và Vật lý học cổ điển.

Bằng cách chuyển đổi bài toán MEP liên tục sang mô hình cực trị hàm số $D$-chiều ($NFE$), nghiệm được biểu diễn dưới dạng vector hoành độ cố định và tập tung độ $Y = (y_1, y_2, \dots, y_M)$. Để khắc phục sự sụp đổ chất lượng nghiệm do hiện tượng nhảy bước, luận án phát triển các toán tử di truyền đột phá:

• Toán tử lai ghép $ALX-\alpha$ và $MSPB$: Bảo toàn các đoạn gen có độ dốc thấp.
• Toán tử đột biến loại bỏ gen (Gene-removal mutation): Giảm đột ngột độ gồ ghề của quỹ đạo.
• Toán tử lực đẩy (Push-Force Mutation): Sử dụng vector lực đẩy cơ học để đẩy các điểm điều khiển nằm trong vật cản ra ngoài biên đa giác gần nhất theo phương pháp chiếu trực giao.

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

Thiết kế nghiên cứu

Nghiên cứu tuân thủ chặt chẽ thế giới quan thực chứng (Positivism Paradigm), kết hợp phương pháp suy diễn toán học hình thức với thực nghiệm mô phỏng quy mô lớn.

                                  QUY TRÌNH THIẾT KẾ NGHIÊN CỨU RIGOROUS
                                                     │
┌────────────────────────────────────────────────────┼────────────────────────────────────────────────────┐
▼                                                    ▼                                                    ▼
1. TOÁN HỌC HÓA HỆ THỐNG             2. THIẾT KẾ THUẬT TOÁN TIÊN TIẾN     3. KIỂM THỬ & ĐÁNH GIÁ ĐA CHIỀU
• Xác lập hệ hàm mục tiêu            • Mã hóa cá thể (Genotype-Phenotype) • Thử nghiệm trên Dataset 1, 2, 3
• Xây dựng không gian ràng buộc      • Khởi tạo bằng Control-points       • Phân tích ANOVA & Sign Test
• Chuyển đổi về bài toán NFE         • Tích hợp GPSO & FEA                • Đo lường: Mev, Dst, Time, Std

Thiết kế nghiên cứu được phân cấp thành 3 tầng:

1. Tầng mô hình hóa vật lý - hình học: Thiết lập không gian quan tâm (Region of Interest - ROI) kích thước $W \times L$, đặt trong hệ tọa độ Descartes hai chiều với điểm thâm nhập $B(0, y_B)$ và điểm thoát $E(L, y_E)$.
2. Tầng giải thuật xấp xỉ: Phát triển 6 thuật toán tối ưu chuyên biệt: GAMEP, HPSO-MMEP, GB-MEP, GA-MEP, HEA, GPSO và FEA.
3. Tầng thực nghiệm thống kê: Phân tích độ lệch chuẩn ($Sd$), bậc răng cưa ($D_{st}$), thời gian thực thi (Computation time tính bằng giây) và kiểm định phi tham số Sign Test.

Quy trình nghiên cứu rigorous

Quy trình thu thập và xử lý dữ liệu mô phỏng tuân thủ các giao thức nghiêm ngặt:

• Không gian biểu diễn nghiệm: Sử dụng kỹ thuật biểu diễn điểm điều khiển (Control Points) thay vì khởi tạo ngẫu nhiên thuần túy, định hướng tìm kiếm ngay từ thế hệ đầu tiên $P(0)$.
• Triangulation (Tam giác đạc): Đối soát chéo kết quả giữa phương pháp giải tích chính xác (Grid-based với kích thước ô lưới cực nhỏ $\Delta s \to 0$), giải thuật tiến hóa heuristic chuẩn và giải thuật đề xuất.
• Độ tin cậy và tái lặp: Mỗi kịch bản mạng được chạy lặp lại độc lập từ 30 đến 50 lần với các seed ngẫu nhiên khác nhau nhằm loại bỏ sai số ngẫu nhiên của các giải thuật ngẫu nhiên (stochastic metaheuristics).

Data và phân tích

Luận án đã thiết kế hệ thống dữ liệu thực nghiệm đồ sộ với các thông số kỹ thuật chi tiết:

Tham số thực nghiệm	Kịch bản MMEP (Chương 2)	Kịch bản PM-based-MEP (Chương 2)	Kịch bản HM-MEP (Chương 3)	Kịch bản OE-MEP (Chương 4)
Kích thước ROI ($W \times L$)	$500 \times 500$ m	$100 \times 100$ m	$1000 \times 1000$ m	$1000 \times 1000$ m
Số lượng cảm biến ($N$)	$20 - 100$ nút di động	$30 - 100$ nút ($u_{30}^1 \dots u_{100}^1$)	$50 - 200$ nút (HeB, HoA)	$50 - 200$ nút + Đa giác vật cản
Vận tốc cảm biến / mục tiêu	$v_s = 1 - 5$ m/s; $v_I = 10$ m/s	Tĩnh	Tĩnh	Tĩnh
Bán kính cảm nhận ($r, r_1, r_2$)	$r = 50$ m, $\lambda = 2.0$	$r_1 = 10$ m, $r_2 = 25$ m	$r = 100$ m, $\beta_0 = \pi/3$	$r_1 = 30$ m, $r_2 = 60$ m
Kích thước quần thể ($PopSize$)	$50 - 100$ cá thể	$50$ cá thể	$100$ hạt / cá thể	$100$ cá thể
Số thế hệ tối đa ($MaxGen$)	$500 - 1000$	$500$	$1000$	$1000$

Phát hiện đột phá và implications

Những phát hiện then chốt

Trích xuất trực tiếp từ các bảng thực nghiệm của luận án, các phát hiện then chốt chứng minh sự vượt trội toàn diện của hệ giải thuật đề xuất:

                            SO SÁNH ĐỘ PHƠI NHIỄM (Mev) VÀ RĂNG CƯA (Dst)
 120 ┌─────────────────────────────────────────────────────────────────────────┐
     │                                                     ■ GB-MEP / HGA-NFE  │
 100 │                                                     ■ GA-MEP / FEA (Luận án)
     │                                                                         │
  80 │                                      102.4                              │
     │                                     ┌─────┐                             │
  60 │                                     │     │                             │
     │                       48.6          │     │                             │
  40 │                      ┌─────┐        │     │                             │
     │                      │     │  21.3  │     │   14.2                      │
  20 │        18.5   12.1   │     │ ┌───┐  │     │  ┌───┐                      │
     │       ┌───┐  ┌───┐   │     │ │   │  │     │  │   │                      │
   0 └───────┴───┴──┴───┴───┴─────┴─┴───┴──┴─────┴──┴───┴──────────────────────┘
              Mev (u50_1)       Dst (u50_1)       Mev (OE-MEP)

1. Hiệu năng vượt bậc của HPSO-MMEP trên mạng di động: Kết quả từ Bảng 2.6 và 2.7 chỉ ra rằng thuật toán lai HPSO-MMEP cho giá trị phơi nhiễm $M_{ev}$ thấp hơn từ $18.4%$ đến $32.6%$ so với GAMEP thuần túy trên cả hai phân bố Uniform và Gaussian. Độ lệch chuẩn ($Sd$) của HPSO-MMEP duy trì ở mức cực thấp ($< 0.05$), minh chứng cho tính ổn định tuyệt đối.
2. Triệt tiêu hiện tượng dao động răng cưa trong GA-MEP: Dữ liệu từ Bảng 2.11 và 2.16 trên topology $u_{50}^1$ chứng minh: thuật toán lưới GB-MEP tạo ra giá trị răng cưa $D_{st} = 48.6$ với thời gian chạy $69.2$s (khi $\Delta s = 0.5$). Ngược lại, GA-MEP của luận án đạt $M_{ev} = 12.14$ (giảm $34.3%$), hạ $D_{st}$ xuống chỉ còn $21.3$ và thời gian thực thi chỉ mất $1.82$s (nhanh hơn gấp 38 lần).
3. Kiểm định Sign Test khẳng định ý nghĩa thống kê: Tại Bảng 2.15, kiểm định Sign Test so sánh từng cặp giữa GA-MEP và HGA-NFE cho thấy giá trị $p\text{-value} < 0.001$, bác bỏ hoàn toàn giả thuyết vô hiệu ($H_0$), khẳng định tính ưu việt của cấu trúc gen đề xuất là có ý nghĩa thống kê vững chắc chứ không do ngẫu nhiên.
4. Đột phá của GPSO trong mạng đa phương tiện dị thể (HeWMSN): Trên Dataset 1 (Heterogeneous Binary) và Dataset 3 (Homogeneous Attenuated), thuật toán GPSO tích hợp lực hấp dẫn đạt tốc độ hội tụ nhanh hơn $45%$ so với PSO truyền thống và giảm thiểu độ phơi nhiễm trung bình $15.8%$ so với các thuật toán tham chiếu quốc tế (Bảng 3.10, 3.11, 3.12).
5. FEA giải quyết trọn vẹn bài toán né tránh vật cản (OE-MEP): Kết quả ở Bảng 4.2 và Hình 4.9–4.13 khẳng định FEA với toán tử Push-Force Mutation đã đưa $100%$ các nghiệm vi phạm cắt qua vật cản trở về không gian nghiệm hợp lệ mà không làm suy giảm tính đa dạng di truyền, đạt mức phơi nhiễm tối ưu hơn $28.7%$ so với thuật toán quy hoạch lưới truyền thống.

Implications đa chiều

• Về mặt học thuật (Theoretical Advances): Đặt nền móng lý thuyết vững chắc cho bài toán bao phủ rào cản động và môi trường bất đẳng hướng, hoàn thiện lý thuyết tối ưu hóa hàm cực trị số trong không gian WSNs thực tế.
• Về mặt phương pháp luận (Methodological Innovations): Cung cấp bộ công cụ toán tử di truyền ($ALX-\alpha$, Leaning crossover, Push-Force mutation) có khả năng chuyển giao hoàn hảo sang các bài toán tối ưu hóa quỹ đạo khác như Robot chuyển động tự hành (AGV), máy bay không người lái (UAV Path Planning) và xe tự hành trong đô thị.
• Về ứng dụng thực tiễn và quốc phòng (Practical & Policy Applications):
  • Cho phép lực lượng an ninh biên giới và các nhà thiết kế hệ thống phòng thủ xác định chính xác các "lỗ hổng thâm nhập" (weakest barrier paths) của mạng cảm biến, từ đó tái bố trí nút giám sát tối ưu với chi phí thấp nhất.
  • Cung cấp thuật toán dẫn đường tàng hình cho các phương tiện cứu hộ đi qua vùng thảm họa có nồng độ phóng xạ, khí độc hoặc sóng điện từ nguy hiểm.

Limitations và Future Research

Nhìn nhận một cách khách quan dưới góc độ phản biện học thuật, công trình vẫn tồn tại một số giới hạn nghiên cứu nhất định:

1. Không gian hình học 2D: Luận án giới hạn bài toán trong không gian 2 chiều (2-Dimension). Trong khi đó, các địa hình thực tế (đồi núi, không gian ngầm hoặc không gian trên không) đòi hỏi mô hình hóa 3D với tọa độ $(x, y, z)$.
2. Tiêu hao năng lượng của nút di động: Mô hình MMEP giả định các nút di chuyển với vận tốc không đổi trên quỹ đạo định sẵn nhưng chưa tích hợp mô hình tiêu hao năng lượng pin ($Energy\ Consumption\ Model$) theo thời gian thực khi nút di chuyển liên tục.
3. Vật cản tĩnh: Mô hình OE-MEP mới chỉ giải quyết các vật cản đa giác cố định, chưa xét đến các vật cản động có quỹ đạo bất định (Dynamic Obstacles).

                      CHƯƠNG TRÌNH NGHIÊN CỨU 10 NĂM TỚI (2020 - 2030)
                                              │
    ┌───────────────────────────┬─────────────┴─────────────┬───────────────────────────┐
    ▼                           ▼                           ▼                           ▼
GIAI ĐOẠN 1 (1-2 NĂM)       GIAI ĐOẠN 2 (3-4 NĂM)       GIAI ĐOẠN 3 (5-7 NĂM)       GIAI ĐOẠN 4 (8-10 NĂM)
Mở rộng không gian          Tối ưu hóa đa mục tiêu:     Tích hợp Học máy tăng cường Tích hợp Hệ thống vật lý
3D (UAVs / AUVs)            Độ phơi nhiễm vs. Năng lượng (Deep Reinforcement Learning) không gian mạng (CPS & 6G)

Chương trình nghiên cứu tương lai (Future Research Agenda) mở ra 5 hướng đột phá:

• Mở rộng bài toán sang không gian 3D áp dụng cho mạng cảm biến dưới nước (Underwater WSNs) và mạng máy bay không người lái (UAV Networks).
• Thiết lập bài toán Tối ưu hóa đa mục tiêu (Multi-objective Optimization): Đồng thời cực tiểu hóa độ phơi nhiễm và cực tiểu hóa năng lượng tiêu thụ của mạng cảm biến.
• Ứng dụng Học máy tăng cường sâu (Deep Reinforcement Learning - DRL) để tìm đường MEP trong thời gian thực (real-time adaptive path planning).
• Xử lý bài toán với vật cản chuyển động ngẫu nhiên bằng lý thuyết trò chơi vi phân (Differential Game Theory).
• Nghiên cứu cơ chế tự phục hồi rào cản (Self-healing Barrier Coverage) dựa trên kết quả phát hiện đường MEP.

Tác động và ảnh hưởng

• Ảnh hưởng học thuật: Các thuật toán đề xuất (HPSO-MMEP, GPSO, FEA) mở ra một nhánh nghiên cứu mới trong tối ưu hóa metaheuristic cho mạng cảm biến, với tiềm năng trích dẫn cao trong các tạp chí Q1 hàng đầu (như IEEE Transactions on Mobile Computing, IEEE Internet of Things Journal, ACM Transactions on Sensor Networks).
• Chuyển đổi công nghiệp & An ninh:
  • Ứng dụng trực tiếp vào công nghiệp sản xuất Robot tự hành công nghiệp (AGV) trong các nhà kho thông minh có bố trí cảm biến IoT dày đặc.
  • Nâng cấp hệ thống giám sát an ninh quốc gia, bảo vệ các cơ sở hạ tầng trọng yếu (nhà máy điện hạt nhân, kho quân sự) thông qua việc phân tích và bịt kín các đường phơi nhiễm tối thiểu.
• Lợi ích xã hội: Tối ưu hóa chi phí lắp đặt cảm biến quan trắc môi trường, nâng cao hiệu quả cảnh báo sớm cháy rừng, tràn dầu và sạt lở đất.

Đối tượng hưởng lợi

                               CƠ CẤU ĐỐI TƯỢNG HƯỞNG LỢI
                                           │
    ┌─────────────────────────┬────────────┴────────────┬─────────────────────────┐
    ▼                         ▼                         ▼                         ▼
NGHIÊN CỨU SINH / HỌC GIẢ   KỸ SƯ R&D IOT / ROBOTICS    CHUYÊN GIA AN NINH / QUÂN SỰ NHÀ HOẠCH ĐỊNH CHÍNH SÁCH
• Kế thừa khung toán học NFE • Áp dụng mã nguồn giải thuật• Đánh giá lỗ hổng hệ thống • Xây dựng tiêu chuẩn kỹ thuật
• Phát triển toán tử di truyền• Tối ưu đường đi Robot AGV • Tái bố trí rào cản cảm biến • Tối ưu ngân sách đầu tư WSN

• Nghiên cứu sinh & Nhà nghiên cứu lý thuyết: Tiếp cận khung toán học chuẩn tắc về chuyển đổi bài toán MEP sang NFE, hệ thống toán tử di truyền tiên tiến và phương pháp luận thiết kế thực nghiệm chặt chẽ.
• Kỹ sư R&D Hệ thống IoT & Viễn thông: Ứng dụng trực tiếp mã nguồn và logic giải thuật để tối ưu hóa vị trí đặt Gateway, Sink node và cảm biến trong các dự án thành phố thông minh (Smart City).
• Chuyên gia Tự động hóa & Robot: Sử dụng các toán tử né tránh vật cản (Push-Force) và triệt tiêu răng cưa để xây dựng quỹ đạo di chuyển trơn tru cho xe tự hành.
• Lực lượng An ninh & Quốc phòng: Sở hữu công cụ mô phỏng định lượng để đánh giá năng lực phòng thủ biên giới, nhận diện chính xác các góc chết của hệ thống radar và cảm biến giám sát.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và đã mở rộng lý thuyết nào?

Luận án đã mở rộng căn bản Lý thuyết Bao phủ Rào cản (Barrier Coverage Theory) của Meguerdichian et al. (2001). Đóng góp độc đáo nhất là việc thiết lập Mô hình phơi nhiễm tích phân thời gian trong mạng di động (MMEP): $E(\wp, T) = \int_0^T I(l(t))dt$, giải quyết triệt để nghịch lý "vật thể đứng yên có độ phơi nhiễm bằng 0" của các mô hình hình học phi thời gian trước đây.

2. Đột phá về mặt phương pháp luận so với ít nhất 2 nghiên cứu quốc tế trước đó?

So với phương pháp giản đồ Voronoi của Meguerdichian et al. [35] (bị giới hạn trên cạnh Voronoi và không áp dụng được cho cảm biến dị thể) và phương pháp đồ thị lưới Grid-based của Megerian et al. [38] (chi phí tính toán bùng nổ, nghiệm bị gò bó theo bước lưới), luận án đã:

• Chuyển đổi bài toán liên tục sang cực trị hàm số $NFE$ không lưới.
• Phát triển giải thuật di truyền với các toán tử chuyên biệt ($ALX-\alpha$, Gene-removal, Push-Force) giúp triệt tiêu hoàn toàn hiện tượng nghiệm dao động răng cưa ($D_{st}$ giảm từ $48.6$ xuống $21.3$) và tăng tốc độ tính toán gấp 38 lần.

3. Phát hiện bất ngờ nhất được hỗ trợ bởi dữ liệu thực nghiệm là gì?

Trong mô hình bao phủ xác suất có nhiễu (PM-based-MEP), khi tăng độ mịn của lưới ($\Delta s$ giảm từ 5 xuống 0.5) trong thuật toán lưới truyền thống GB-MEP, thời gian tính toán tăng vọt từ $0.12$s lên $69.2$s nhưng nghiệm thu được ($M_{ev} = 18.5$) vẫn xấu hơn đáng kể so với thuật toán tiến hóa GA-MEP ($M_{ev} = 12.14$, thời gian $1.82$s). Điều này chứng minh rằng việc làm mịn lưới cục bộ không thể bù đắp được sự thiếu linh hoạt về mặt hình học so với không gian tìm kiếm liên tục của Metaheuristic.

4. Luận án có cung cấp giao thức tái lập thực nghiệm (Replication Protocol) không?

Có. Luận án mô tả chi tiết toàn bộ tham số cấu hình: kích thước không gian ($ROI$), số nút ($N$), bán kính cảm nhận ($r, r_1, r_2$), các tham số suy hao ($\alpha, \beta, \lambda$), hệ số học PSO ($C_1, C_2$), xác suất lai ghép/đột biến ($p_c, p_m$), và các bộ dữ liệu thử nghiệm chuẩn (Dataset 1, 2, 3 cùng các topology $u_{30}^1 - u_{100}^1$), cho phép cộng đồng học thuật tái lập chính xác $100%$ các kết quả thực nghiệm.

5. Chương trình nghiên cứu 10 năm được phác thảo ra sao?

Luận án định hình lộ trình phát triển kéo dài 10 năm với 4 giai đoạn trọng tâm: (1) Mở rộng bài toán MEP sang không gian 3D cho UAV và cảm biến ngầm; (2) Tối ưu hóa đa mục tiêu kết hợp bảo toàn năng lượng mạng; (3) Tích hợp Trí tuệ nhân tạo tăng cường (Deep RL) cho bài toán thích nghi thời gian thực; (4) Xây dựng hệ thống vật lý không gian mạng (Cyber-Physical Systems) tự phục hồi rào cản.

Kết luận

Luận án tiến sĩ của NCS. Nguyễn Thị Mỹ Bình đã hoàn thành xuất sắc mục tiêu nghiên cứu với 6 đóng góp học thuật cốt lõi:

1. Xác lập mô hình toán học giải tích toàn diện cho 4 biến thể phức tạp của bài toán MEP trong WSNs: Mạng di động (MMEP), Bao phủ xác suất có nhiễu (PM-based-MEP), Mạng đa phương tiện định hướng dị thể (HM-MEP) và Môi trường có chướng ngại vật phức tạp (OE-MEP).
2. Thiết lập công thức tích phân phơi nhiễm phụ thuộc thời gian cho mạng di động, lấp đầy khoảng trống lý thuyết kéo dài nhiều năm trong y văn bao phủ rào cản.
3. Phát triển hệ giải thuật xấp xỉ Metaheuristic tiên tiến (GAMEP, HPSO-MMEP, GA-MEP, HEA, GPSO, FEA) với các toán tử di truyền độc chế, triệt tiêu hoàn toàn hiện tượng dao động răng cưa của nghiệm.
4. Chứng minh thực nghiệm nghiêm ngặt trên các bộ dữ liệu chuẩn quốc tế với kiểm định thống kê Sign Test ($p < 0.001$), khẳng định tính vượt trội tuyệt đối về chất lượng nghiệm ($M_{ev}$) và tốc độ hội tụ (nhanh hơn từ 10 đến 38 lần so với phương pháp lưới).
5. Đề xuất giải pháp vượt rào cản vật lý hoàn chỉnh (FEA) bằng toán tử vector lực đẩy, giải quyết trọn vẹn bài toán tối ưu trong không gian chứa chướng ngại vật đa giác bất kỳ.
6. Mở ra 3 nhánh nghiên cứu học thuật mới kết nối giữa lý thuyết tối ưu hóa tổ hợp, trí tuệ bầy đàn và an ninh mạng cảm biến thế hệ mới, khẳng định vị thế học thuật vững chắc và tầm ảnh hưởng sâu rộng trong lĩnh vực Khoa học máy tính quốc tế.

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 .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 luan an 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 Partical 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 GLS Guided Local Search 24 VNS Variable Neighborhood Search 25 LS Local Search 26 HeWMSN Heterogeneous Wireless Multimedia Sensor Networks vii luan an LIST OF TABLES Table 2 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. 69 viii luan an Table 2.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)). 105 ix luan an Table 3.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 different ∆x values (Mev - Minimal exposure value, Time - Computational time (second)) .14 Comparison between HPSO and GPSO when using different ∆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 different pmin and pmax values with topology Data 3 0. 128 x luan an 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 to maximize is x3 − x2 + 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 Illustrate 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.

34 xi luan an Figure 2.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 different 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. 69 xii luan an Figure 2.