A Genetic-Algorithm Based Mobile Sensor Network Deployment AlgorithmEE382C: Embedded Software SystemsFinal ReportYulai SuenDepartment of Electrical and Computer EngineeringThe University of Texas at AustinAbstract. This paper describes a genetic-algorithm (GA) based deployment algorithm of mobile sensor network. The algorithm is designed for real-time online deployment for maximum coverage of the environment. The paper presents the details on the algorithm and the implementation, including the major components in our design: recombination, mutation, and the fitness function. The algorithm considers power metrics of the nodes for real-time planning of the next movement. The algorithm was implemented with Java Genetics Algorithm Package [4] and simulated with Network Simulator 2 [5] for performance evaluation. The simulation showed that the algorithm helped the network to avoid local maxima in coverage.1. INTRODUCTIONA mobile sensor network is composed of a collection of nodes that has sensing, computation, communication, and locomotion capabilities [1]. This paper aims to describe an algorithm for mobile sensor network deployment in an unknown environment by a real-time genetic algorithm (GA). The algorithm allows the network to achieve maximum coverage with minimum energy consumption. It is applicable in both a dynamic environment and a dynamic network topology. Genetic algorithm was first proposed by Goldberg et al in 1989 [3]. It has wide applications in model checking and satisfiability (SAT) problems. The advantage of GA is that the process is completely automatic and avoids local maxima. GA consists of three important components: recombination, mutation, and fitness evaluation. In particular, the fitness function in this algorithm considers the nodes’ power metrics, which is the fundamental limitation on both embedded systems and sensor networks. The algorithm is based on the assumption that each node is equipped with a sensor, such as a scanning laser range-finder and omni-camera, which provides the node with the relative distance and bearing of the nearby nodes and obstacles. The following sections of this paper describe these components in details and the adjustments to general GA for real-time applications. At the end, the paper presents the result of simulations using a discrete-event simulator. 2. RELATED WORKThe deployment problem that this paper addresses is the blanket coverage problem described by Gage [2]. In blanket coverage, the objective is to achieve a static arrangement of nodes that maximize the total detection area. Howard et al used potential field techniques and spread the nodes over the environment by driving them with a virtual “force” [2]. The GA approach in this paper achieves a similar repulsive behavior in spreading the nodes and obstacle avoidance. However, this algorithm avoids the local optima problem faced by many other algorithms [6], [7] and [8].Other researchers also considered using artificial intelligence in sensor network deployment. For example, Haynes compared a few search algorithms including GA and measured their performance in coverage. However, like many other researchers, he assumed that the network has a complete model of the environment and that only offline-planning is required for deployment. 3. CONTRIBUTIONMobile sensor networks usually face two limitations. First of all, the environment is dynamic. The position of other mobile identities and the geographical features of the environment are usually dynamic. This makes offline planning of deployment by searching through the static map of the environment very inefficient and inaccurate. Second, sensor networks are very sensitive to power consumptions because they are usually designed for applications that run for a long time, e.g. a surveillance system. The embedded systems of the mobile nodes also constrain the available power reservation. To solve these problems, the algorithm this paper presents contributes in the following ways:1. Provision of an online GA-based deployment algorithm that is interactive with the dynamics of the environment. 2. Taking into account the power consumption known to a node itself as a consideration when deciding on the locomotion strategy to monitor the power consumption during deployment.3. Randomization at different stages allows the deployment to converge to a static global optimum in coverage.4. ALGORITHMIn our algorithm, the network consists of two domains: a server, and clusters of nodes. The server assigns a base-station in each cluster. The base-stations help to monitor the deployment processes from a global point of view. In the following sections, we will describe five important components of the algorithm in detail. Fig 1 is the overview of the algorithm.A. InitializationAt this stage, the server has to set tm which serves as an upper bound to the run-time of the algorithm. The users can also specify the target coverage. Then, the direction vector (DV) and the base station set (BSS) are chosen. From the GA point of view, the DV and the BSS are the chromosomes, which carry the genetic information over generations. The assignment to DV and BSS are random.Figure 1. Overview of GA-based mobile sensor network deploymentI. Direction VectorDV is the probabilistic model of a node moving towards different directions. It has d elements, each representing the probability of the movement to a directiond_i. The summation of the probabilities of one direction vector is 1.0. The difference in direction between each consecutive element is called direction Deployment(MANET)1. Initialization a. direction vector (DV) b. base station set (BSS) c. tm; default: infinityd. coveragetarget; default: min( ][icvbleni, field_area)2. Sensor Data Collection after tm, each node sends a sensor vector to its router sensor_vector = {id, rx_power, energy, coverage}3. Recombination base-stations sort the sensor vector by the fitness function, recombines the fittest chromosomes, and send the new chromosomes back to the nodes 4. Mutationif niricvg ]][[ -niricvg ]1][[ ≤ coveragedelta mutate DV and BSSdecrement of tm by tdelta5. Terminationif tm = 0 or niricvg ]][[ ≥ coveragetarget terminateelse repeat 2 - 5resolution (DR). DR is determined by the locomotion capability of the nodes, for example, the resolution of the steering servo-motor of the onboard odometer. II. Base Station SetThe algorithm assumes that all nodes