MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF SCIENCE AND TECHNOLOGY NGUYEN THI MY BINH APPROXIMATE ALGORITHMS FOR SOLVING THE MINIMAL EXPOSURE PATH PROBLEMS IN WIRELESS SENSOR NETWORKS Major : Computer Science Code : 9480101 SUPERVISORS: 1. Associate Professor Huynh Thi Thanh Binh 2. Associate Professor Nguyen Duc Nghia Hanoi, 2020 DECLARATION OF AUTHORSHIP I assure that this dissertation ”Approximate algorithms for solving the minimal exposure path problems in wireless sensor networks” is my own work under the guidance of my supervi-sors, Associate Professor Huynh Thi Thanh Binh and Associate Professor Nguyen Duc Nghia. All the research results are presented in the dissertation which are honest and have not pub-lished by any other author or work.
Hanoi, 12 December 2020 PhD Student Nguyen Thi My Binh SUPERVISOR Huynh Thi Thanh Binh i ACKNOWLEDGEMENT This dissertation was completed during my doctoral course at the School of Information Communication and Technology (SoICT), Hanoi University of Science and Technology (HUST). I am so grateful for all the people who always support and encourage me to complete this study. First, I would like to express my sincere gratitude to my supervisors, Associate Professor Huynh Thi Thanh Binh and Associate Professor Nguyen Duc Nghia. I am indebted to have had advisors who gave me all the freedom, resources, guidance and support during the period that led up to this dissertation.
Their broad knowledge in different areas inspired me and helped me overcome many di fficulties in my research. Furthermore, I would like to thank all the members of Modeling and Simulation Lab, Computer Science Department, SoICT, HUST, as well as all of my colleagues in the Faculty of Information Technology, Hanoi University of Industry. They assisted me a lot in the research process and gave me helpful advice to overcome my own di fficulties. Furthermore, attending at scientific conferences has always been a great opportunity for me to receive many useful comments from the academic community.
Last but not least, I would like to express my utmost gratitude to my family, my par- ents, my husband and my children, for their unconditional love, support, understanding and encouragement. I would not be able to achieve this accomplishment without their love and support. Hanoi, 12 December 2020 Ph. Student Nguyen Thi My Binh ii CONTENTS DECLARATION OF AUTHORSHIP i ACKNOWLEDGEMENT ii CONTENTS vi SYMBOLS vii LIST OF TABLES x LIST OF FIGURES xv INTRODUCTION 1 1 BACKGROUND 10 1.1 Wireless sensor networks .3 Sensor coverage model .4 Sensing intensity models .6 Wireless sensor network scenarios .1 Single-solution-based metaheuristic .2 Population-based metaheuristics .2 Particle swarm optimization algorithm.
29 2 MINIMAL EXPOSURE PATH PROBLEMS IN OMNI-DIRECTIONAL SENSOR NETWORKS 30 2.1 Minimal exposure path problem in mobile wireless sensor networks .2 Preliminaries and problem formulation .1 The GAMEP for solving MMEP problem .2 The HPSO-MMEP algorithm for solving the MMEP problem .2 Minimal exposure path problem in probabilistic coverage model .2 Preliminaries and problem formulation .1 Grid-based algorithm for solving the PM-based-MEP problem .2 Genetic algorithm for solving the PM-based-MEP problem. 81 3 MINIMAL EXPOSURE PATH PROBLEM IN WIRELESS MULTIME- DIA SENSOR NETWORKS 82 3.2 Preliminaries and problem formulation .1 The Boolean directional coverage model .2 The attenuated directional sensing model .3 Accumulative intensity function .4 Closest-sensing intensity function .5 Minimal exposure path .1 HEA individual initialization .2 GPSO individual initialization .2 Particle swarm optimization algorithm .2 Parameters and system setting .1 Algorithm parameters trials .2 Comparison under our datasets .3 Comparisons under the datasets of previous algorithms. 111 4 OBSTACLES-EVASION MINIMAL EXPOSURE PATH PROBLEM IN WIRELESS SENSOR NETWORKS 112 4.2 Preliminaries and problem formulation .1 The truncated directional coverage model .2 The accumulative sensing intensity .4 Minimal exposure path .1 A novel characteristic of FEA algorithm .7 Family system based evolutionary algorithm .1 The performance of FEA when using different A and D .2 The performance of FEA when using different p min and pmax values .3 Comparison between FEA and previous algorithm in OE-MEP problem .4 Comparison between FEA and GA-MEP. 133 CONCLUSIONS AND FUTURE WORKS 134 PUBLICATIONS 137 BIBLIOGRAPHY 138 vi ABBREVIATIONS No.
Abbreviation Meaning 1 WSNs Wireless Sensor Networks 2 IoT Internet Of Thing 3 ROI Region Of Interest 4 BC Barrier Coverage 5 MEP Minimal Exeposure Path 6 PSO Particle Swarm Optimization 7 NFE Numerically Function Extreme 8 MWSN Mobile Wireless Sensor Networks 9 GPSO Gravitation Partical Swarm Optimization 10 HGA Hybrid Genetic Algorithm 11 FEA Family Evolution Algorithm 12 HoWSNs Homogeneous Wireless Sensor Networks 13 HeWSNs Heterogeneous Wireless Sensor Networks 14 SWSN Static Wireless Sensor Networks 15 CO Combinatorial Optimization 16 TSP Travelling Salesman Problem 17 QAP Quadratic Assignment Problem 18 ACO Ant Colony Optimization 19 EC Evolution Computation 20 ILS Iterated Local Search 21 TS Tabu Search 22 GA Genetic Algorithm 23 LS Local Search 24 HeWMSN Heterogeneous Wireless Multimedia Sensor Networks 25 GAMEP Genetic Algorithm Minimal Exposure Path 26 HPSO-MMEP Hybrid Particle Swarm Mobile MEP 27 GA-MEP Genetic Algorithm for Minimal Exposure Path 28 GB-MEP Grid Based Algorithm for Minimal Exposure Path 29 HEA Hybrid Evolution Algorithm 30 MMEP Mobile Minimal Exposure Path vii LIST OF TABLES Table 1 Comparative table of related works on MEP problem .1 Evolution process versus solving an optimization problem .1 Experimental parameters for attenuated disk model and truncated atten- uated disk model .2 Parameters setting for GAMEP .3 Experimental parameters for HPSO-MMEP algorithm .4 Parameters setting for HPSO .5 Different version of HPSO-MMEP using different genetic operators .6 Computation results of HPSO-MMEP in comparison with GAMEP in uniform distribution of sensors (Mev: minimal exposure value, Sd: standard deviation) .7 Computation results of HPSO-MMEP in comparison with GAMEP in Gauss distribution of sensors (Mev: minimal exposure value, Sd: standard devi- ation) .8 Experimental parameters of probabilistic .9 Experimental parameter of GA-MEP .10 Experimental Parameter of HGA-NFE .11 The comparison minimal exposure value, computation time and saw-tooth degree between GA-MEP and GB-MEP when using different subinterval Δs, the topology used is u 50 1 (Mev: minimal exposure value; Time(s): computation time per unit second; Dst: saw-tooth degree) .12 The minimal exposure value obtain from GB-MEP and the best solution of GA-MEP when threshold A varies from 3 to 7 on the topology used is u 50 1 (GB- Mev: the minimal exposure value obtains by GB-MEP; GA-Mev: the minimal exposure value obtains by GA-MEP) .13 Computation time comparison of OGB and GB-MEP when subinterval Δs varies from 5 down-to 0.14 The best minimal exposure value, running time and saw-tooth degree obtained from GA-MEP1, GA-MEP2 and GA-MEP on topology u 30 1, u 40 1, u 50 1, u 60 1, u 70 1, u 80 1, u 90 1 and u 100 1.15 Result on Sign test for pairwise comparisons between Minimal Exposure values obtained by GA-MEP and HGA-NFE (Mev: the minimal exposure value) 76 Table 2.16 Comparison of experimental results between GB-MEP and GA-MEP (Num: number of sensors, Ord: the order of the topology, Mev: the minimal exposure value, Time: the computation time, Sd: standard deviation, Dst: the saw-tooth degree, BMev: best minimal exposure value, AMev: Average minimal exposure value) .1 Experiment instance for homogeneous binary - Dataset 1 .2 Experiment instance for heterogeneous binary - Dataset 2 .3 Experimental instances for homogeneous network using attenuated model - Dataset 3 .4 Parameters for HEA .5 Parameters setting for GPSO .6 Operators setting for four versions of HEA .7 Comparison between four HEA versions when running on the Dataset 1 (Heterogeneous, Binary) (Mev - Minimal exposure value, Time - Computation time (second)) .8 Parameters setting for four versions of GPSO .9 Comparison between four versions of GPSO when running on the Dataset 3 (Heterogeneous, Binary) (Mev - Minimal exposure value, Time - Computation time (second)) .10 Comparison between HEA, GPSO and previous algorithms when running on Dataset 1 (Homogeneous - Binary) (Mev- Minimal exposure value, Time- Computational time (second)) .11 Comparison between HEA, GPSO and previous algorithms when running on Dataset 2 (Heterogeneous - Binary) (Mev- Minimal exposure value, Time- Computational time (second)) .12 Comparison between HEA, GPSO and previous algorithms when run-ning on Dataset 3 (Homogeneous - Attenuated) (Mev - Minimal exposure value, Time - Computational time (second)) .13 Comparison between HEA and HGA-NFE when using di fferent Δ x values (Mev - Minimal exposure value, Time - Computational time (second)) .14 Comparison between HPSO and GPSO when using di fferent Δ x values (Mev - Minimal exposure value, Time - Computational time (second)) .1 Parameters for FEA .2 The Minimal exposure value (Mev), the computational time (sec) and the standard deviation (Std) of FEA when using di fferent p min and pmax values with topology Data 3 0. 128 x LIST OF FIGURES Figure 1 Examples of area coverage (a), point coverage (b), and barrier coverage (c) 2 Figure 2 Illustration of a general minimal exposure problem in WSNs .1 Demonstration of acoustic sensor .2 Illustration of an sensor node .3 Illustration of (a) the Boolean disk coverage model in which the red stars are the target points respectively belonging inner and outer the green sensing area of a sensor, (b) the truncated attenuated coverage model .4 Demonstration of region of interest and crossing path .5 Illustration of crossing path types .6 Demonstration of sensor network scenarios: (a) single-hop, heterogeneous, stationary network; (b) multi-hop, homogeneous, stationary network; (c) multi- hop, heterogeneous, stationary network; (d) single-hop, homogeneous, stationary network with a mobile sink .7 Illustration of local search using a binary representation of solutions, a flip move operator, and the best neighbor selection strategy. The objective function 3 2 to maximize is x − x + x. The final local optima found is x = (11110), starting from the solution x0 = (11010).8 Illustration of local search behavior in a given landscape .9 Demonstration of main principles of P-metaheuristic .10 A generation in evolutionary algorithms .11 Genotype versus phenotype in evolutionary algorithms.12 Illustration of particle swarm with their associated positions and veloc- ities.
At each iteration, a particle moves from one position to another in the decision space. PSO uses no gradient information during the search.13 Demonstration of movement of a particle and the velocity update.1 Illustration of (a) the attenuated disk model; (b) the truncated attenuated disk model .2 Demonstration of input and output data .3 Illustration of individual representation of GAMEP .4 Illustration of the single-point crossover .5 Illustration of the mutation operator .6 Individual representation for HPSO-MMEP .7 Red stars are the control points that drives the path .8 Illustration of the crossover operator of HPSO-MMEP .9 Mutation operators: (a) Inverse mutation; (b) Symmetric mutation .10 Sensor trajectory: (a) Rectangle trajectory; (b) Random point trajectory 43 Figure 2.11 Effect of Δs on minimal exposure value (a); computation time (b) of HPSO-MMEP.12 Effect of the genetic operators on the minimal exposure value and the computation time among different versions of HPSO-MMEP .13 Comparison of the minimal exposure value between random and control- point initialization methods: (a) Gauss distribution (b) Uniform distribution .14 Comparison between HPSO-MMEP and HPSO algorithm .15 Effects of the speed of intruder on the minimal exposure value from GAMEP (a) and HPSO-MMEP (b) .16 Movement of an intruder on grids .18 Execution of creating an individual in sensor field < .19 Demonstration of executing ALX − α crossover operator .20 An example of the M SP B crossover operator .21 Demonstration of the Gene-removal mutation operator .22 The computation of the saw-tooth degree .23 The chart presents the minimal exposure values, the computation times and the saw tooth degrees of GB-MEP and GA-MEP when using di fferent subin- terval Δs values on topology u 50 1.24 The chart presents the minimal exposure values obtained from GA-MEP when using different values of threshold A on topology u 50 1 .25 Comparison of minimal exposure values between GA-MEP and GB-MEP when using: (a) Uniform distribution method, (b) Gaussian distribution method, (c) Exponential distribution method .