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ế.

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.