Particle Swarm Optimization for the Static and Dynamic Minimum Energy Broadcast Problem in Wireless Ad-Hoc Networks

100

In this thesis, we addressed the NP-complete minimum energy broadcast (MEB) problem in wireless ad-hoc networks (WANETs). The researches in WANETs have attracted significant attentions because of their convenient deployment and a variety of applications including wireless sensor networks (WSNs). One of the most critical issues in WSNs is lifetime maximization and energy consumption minimization because each node in the network is only equipped limited energy resource. The MEB problem is one of the most important scenarios in WSNs, where the packets have to be transported from a given source node to all other nodes in the network. The objective of the MEB problem is to minimize the total transmission power consumption. A hybrid algorithm based on particle swarm optimization (PSO) and local search was presented to solve the MEB problem. We proposed a power degree encoding to reflect the extent of transmission power level, and it was used to define the particle position in PSO. We also analyzed a well-known local search mechanism, r-shrink, and proposed an improved version, the intensified r-shrink. In order to deal with the dynamic MEB problem, which runs into node removal/insertion, this thesis provided a framework for rapidly linking up disconnected components and presented an effective simple heuristic, Conditional Incremental Power, to repair the network. The promising results indicated the potential of proposed method to be applied to practical use.