Evolutionary Algorithms for Mobile Ad Hoc Networks

BERNABÉ DORRONSORO, PHD, earned his PhD in computer science from the University of Málaga (Spain) in 2007. His main research interests include metaheuristics and mobile networks, among others.PATRICIA RUIZ, PHD, earned her PhD in computer science at the University of Luxembourg and her degree in telecommunication engineering from the University of Málaga (Spain).GRÉGOIRE DANOY, PHD, earned his PhD from University of St Etienne (Ecole des Mines) on the optimization of real-world problems using co-evolutionary genetic algorithms, including topology management problems in mobile ad hoc networks.YOANN PIGNÉ, PHD, obtained his PhD from the University of Le Havre, France, on Modelling and Processing Dynamic Graphs, Applications to Mobile Ad Hoc Networks.PASCAL BOUVRY, PHD, earned his PhD in computer science from the University of Grenoble (INPG), France, in 1994.

• Preface xiii PART I BASIC CONCEPTS AND LITERATURE REVIEW 11 INTRODUCTION TO MOBILE AD HOC NETWORKS 31.1 Mobile Ad Hoc Networks 61.2 Vehicular Ad Hoc Networks 91.2.1 Wireless Access in Vehicular Environment (WAVE) 111.2.2 Communication Access for Land Mobiles (CALM) 121.2.3 C2C Network 131.3 Sensor Networks 141.3.1 IEEE 1451 171.3.2 IEEE 802.15.4 171.3.3 ZigBee 181.3.4 6LoWPAN 191.3.5 Bluetooth 191.3.6 Wireless Industrial Automation System 201.4 Conclusion 20References 212 INTRODUCTION TO EVOLUTIONARY ALGORITHMS 272.1 Optimization Basics 282.2 Evolutionary Algorithms 292.3 Basic Components of Evolutionary Algorithms 322.3.1 Representation 322.3.2 Fitness Function 322.3.3 Selection 322.3.4 Crossover 332.3.5 Mutation 342.3.6 Replacement 352.3.7 Elitism 352.3.8 Stopping Criteria 352.4 Panmictic Evolutionary Algorithms 362.4.1 Generational EA 362.4.2 Steady-State EA 362.5 Evolutionary Algorithms with Structured Populations 362.5.1 Cellular EAs 372.5.2 Cooperative Coevolutionary EAs 382.6 Multi-Objective Evolutionary Algorithms 392.6.1 Basic Concepts in Multi-Objective Optimization 402.6.2 Hierarchical Multi-Objective Problem Optimization 422.6.3 Simultaneous Multi-Objective Problem Optimization 432.7 Conclusion 44References 453 SURVEY ON OPTIMIZATION PROBLEMS FOR MOBILE AD HOC NETWORKS 493.1 Taxonomy of the Optimization Process 513.1.1 Online and Offline Techniques 513.1.2 Using Global or Local Knowledge 523.1.3 Centralized and Decentralized Systems 523.2 State of the Art 533.2.1 Topology Management 533.2.2 Broadcasting Algorithms 583.2.3 Routing Protocols 593.2.4 Clustering Approaches 633.2.5 Protocol Optimization 643.2.6 Modeling the Mobility of Nodes 653.2.7 Selfish Behaviors 663.2.8 Security Issues 673.2.9 Other Applications 673.3 Conclusion 68References 694 MOBILE NETWORKS SIMULATION 794.1 Signal Propagation Modeling 804.1.1 Physical Phenomena 814.1.2 Signal Propagation Models 854.2 State of the Art of Network Simulators 894.2.1 Simulators 894.2.2 Analysis 924.3 Mobility Simulation 934.3.1 Mobility Models 934.3.2 State of the Art of Mobility Simulators 964.4 Conclusion 98References 98PART II PROBLEMS OPTIMIZATION 1055 PROPOSED OPTIMIZATION FRAMEWORK 1075.1 Architecture 1085.2 Optimization Algorithms 1105.2.1 Single-Objective Algorithms 1105.2.2 Multi-Objective Algorithms 1155.3 Simulators 1215.3.1 Network Simulator: ns-3 1215.3.2 Mobility Simulator: SUMO 1235.3.3 Graph-Based Simulations 1265.4 Experimental Setup 1275.5 Conclusion 131References 1316 BROADCASTING PROTOCOL 1356.1 The Problem 1366.1.1 DFCN Protocol 1366.1.2 Optimization Problem Definition 1386.2 Experiments 1406.2.1 Algorithm Configurations 1406.2.2 Comparison of the Performance of the Algorithms 1416.3 Analysis of Results 1426.3.1 Building a Representative Subset of Best Solutions 1436.3.2 Interpretation of the Results 1456.3.3 Selected Improved DFCN Configurations 1486.4 Conclusion 150References 1517 ENERGY MANAGEMENT 1537.1 The Problem 1547.1.1 AEDB Protocol 1547.1.2 Optimization Problem Definition 1567.2 Experiments 1597.2.1 Algorithm Configurations 1597.2.2 Comparison of the Performance of the Algorithms 1607.3 Analysis of Results 1617.4 Selecting Solutions from the Pareto Front 1647.4.1 Performance of the Selected Solutions 1677.5 Conclusion 170References 1718 NETWORK TOPOLOGY 1738.1 The Problem 1758.1.1 Injection Networks 1758.1.2 Optimization Problem Definition 1768.2 Heuristics 1788.2.1 Centralized 1788.2.2 Distributed 1798.3 Experiments 1808.3.1 Algorithm Configurations 1808.3.2 Comparison of the Performance of the Algorithms 1808.4 Analysis of Results 1838.4.1 Analysis of the Objective Values 1838.4.2 Comparison with Heuristics 1858.5 Conclusion 187References 1889 REALISTIC VEHICULAR MOBILITY 1919.1 The Problem 1929.1.1 Vehicular Mobility Model 1929.1.2 Optimization Problem Definition 1969.2 Experiments 1999.2.1 Algorithms Configuration 1999.2.2 Comparison of the Performance of the Algorithms 2009.3 Analysis of Results 2029.3.1 Analysis of the Decision Variables 2029.3.2 Analysis of the Objective Values 2049.4 Conclusion 206References 20610 SUMMARY AND DISCUSSION 20910.1 A New Methodology for Optimization in Mobile Ad Hoc Networks 21110.2 Performance of the Three Algorithmic Proposals 21310.2.1 Broadcasting Protocol 21310.2.2 Energy-Efficient Communications 21410.2.3 Network Connectivity 21410.2.4 Vehicular Mobility 21510.3 Global Discussion on the Performance of the Algorithms 21510.3.1 Single-Objective Case 21610.3.2 Multi-Objective Case 21710.4 Conclusion 218References 218INDEX 221