An Interactive Genetic Algorithm for
Mobile Sensor Networks
Ali NOROUZI, Faezeh Sadat BABAMIR, A. Halim ZAIM
Department of Computer Engineering, Istanbul University,
Avcilar, Istanbul, Turkey
Abstract: In this paper, we describe an interactive approach to design mobile sensor networks. The node-mobility aspect requires an online or interactive algorithm to determine the optimal network-coverage solution for a given area of interest. Hence, we develop a real-time genetic algorithm to find the suitable direction of node locomotion, considering either coverage of the target area or estimation of the optimum energy consumption. The main purpose is to provide a solution that can extend the network lifetime. The simulation results indicate that the proposed fitness function achieves our objectives.
Keywords: Mobile Sensor Networks, WSN, Genetic Algorithm, Network Life time, Optimum Energy Consumption.
CITE THIS PAPER AS:
Ali NOROUZI, Faezeh Sadat BABAMIR, A. Halim ZAIM, An Interactive Genetic Algorithm for Mobile Sensor Networks, Studies in Informatics and Control, ISSN 1220-1766, vol. 22 (2), pp. 213-218, 2013.
Wireless sensor networks (WSNs) include numerous unsupervised devices capable of sensing, computation and communication. These energy-restrained devices are expected to be used for many different kinds of applications . For instance, WSNs can be used for environment and habitat monitoring, traffic measurement on roads, vehicle tracking and personnel tracking inside buildings. Even though WSNs have a variety of applications, their deployment usually has two common objectives: (a) obtaining the maximum area coverage for a specific number of nodes and (b) prolonging the operational life of the individual nodes .
A mobile sensor network is a WSN with locomotion capabilities, consisting of several nodes with sensing, computation and communication functions . This mobility aspect presents a design challenge in unknown environments. A genetic algorithm (GA) could be an innovative approach to simultaneously optimise coverage and lifetime problems. Network lifetime could be defined as the period of time it takes for the first node, or a fraction of all the nodes in the network, to be depleted of their energy.
The aforementioned GA method is applicable for the optimisation of both dynamic environments and dynamic network topologies . In this paper, we develop a real-time GA in order to design a network with maximum coverage and minimum energy consumption, which results in extended network lifetime. In most cases, a basic sensor node consists of five main components: (a) a power supply that is considered to be the only energy source, (b) a controller with memory, (c) a sensing device, (d) a communications system and (e) a mobile platform for mobile wireless sensor nodes. All these constituent parts of the architecture consume energy; especially during the spreading procedure of mobile sensor nodes, which adjusts node position with a trade-off between area coverage and energy usage .
A GA is a heuristic search technique that is used to automatically find optimal solutions, while trying to avoid local maxima . This method is inspired from nature and has numerous applications in model checking . Also, it is suitable for solving non-linear optimisation problems and for finding the probable global optimisation value of a fitness function.
Fundamentally, a GA comprises three important components: recombination, mutation and a fitness function. Many researchers have concentrated on the fitness function, which operates on chromosomes. In our paper, as in , we also propose a fitness function (the main procedure of GAs) to estimate an optimal solution. The optimal solution(s) is selected according to two important parameters.
Energy consumption is one the most important parameters for measuring the efficiency of network positioning and can be divided into three parts: the energy usage of transmission for each node, receiving packets by cluster head and data transmission from cluster head to sink. In this paper, we assume that the energy consumption of transmission for each node represents the energy usage. Network coverage is another important parameter to consider in measuring the size of a chromosome. In this work, the size of a chromosome depends on its energy consumption and network coverage .
The remainder of this paper is organised as follows: (a) Section 2 reviews related work, (b) Section 3 shows our contribution, (c) in Section 4 we propose a solution and elaborate on details of our algorithm, (d) Section 5 presents our simulation and an analysis of our results and (e) Section 6 summarises the conclusions.
- POURKABIRIAN, A., A. T. HAGHIGHAT, Energy-Aware, Delay-Constrained Routing in Wireless Sensor Networks through Genetic Algorithm, IEEE.
- QU, Y., S. V. GEORGAKOPOULOS, Relocation of Wireless Sensor Network Nodes Using a Genetic Algorithm, 978-1-61284-080-2/11/IEEE, 2011.
- SUEN, Y., A Genetic Algorithm based Mobile Sensor Network Deployment Algorithm, Technical report, Department of Electrical and Computer Engineering, The University of Texas at Austin, 2004.
- NOROUZI, A., A. SERTBAS, An Integrated Survey in Efficient Energy Management for WSN using Architecture Approach, International Journal of Advanced Networking and Applications, vol. 3, no. 1, 2011, pp. 968-977.
- GOLDBERG, D., B. KORB, K. DEB, Messy Genetic Algorithms: Motivation, Analysis, and First Results, The Clearinghouse for Genetic Algorithms (TCGA), Report 89003, 1989.
- CANTU-PAZ, E., A Survey of Genetic Algorithms, Calculateurs Paralleles, Reseaux et Systems Repartis, vol. 10(2), 2002.
- ROMOOZI, M., M. VAHIDIPOUR, M. ROMOOZI, S. MAGHSOODI, Genetic Algorithm for Energy Efficient and Coverage-preserved Positioning in Wireless Sensor Networks, in Proceedings of IEEE Conference, ICICCI 2010, pp. 22–25, DOI:10.1109/ICICCI.2010.10
- D GAGE, Command Control for Many-Robot Systems, Unmanned Systems Magazine, vol. 10, no. 4, 1992, pp. 28-34.
- HOWARD, A., M. MATARÍC, G. SUKHATME, Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem, in International Symposium on Distributed Autonomous Robotics Systems (DARS02), June 2002.
- KALPAKIS, K., K. DASGUPTA, P. NAMJOSHI, Maximum Lifetime Data Gathering and Aggregation in Wireless Sensor Networks, in IEEE International Conference on Networking, August 2002, pp. 685-696.
- DASGUPTA K., K. KALPAKIS, P. NAMJOSHI, An Efficient Clustering-based Heuristic for Data Gathering and Aggregation in Sensor Networks, in IEEE Wireless Communications and Networking Conference, vol. 1, 2003, pp. 1948-1954.
- HUSSAIN, S., A. W. MATIN, O. ISLAM, Genetic Algorithm for Energy Efficient Clusters in Wireless Sensor Networks, in Fourth International Conference on Information Technology: New Generations (ITNG 2007), April 2007, pp. 147-154.
- LINDSEY, S. C. S. RAGHAVENDRA, PEGASIS: Power-efficient Gathering in Sensor Information Systems, in Proceedings of the IEEE Aerospace Conference, vol. 3, March 2002, pp. 1125-1130.
- PAN, J., L. CAI, Y. T. HOU, Y. SHI, S. X. SHEN, Optimal Basestation Locations in Two-Tiered Wireless Sensor Networks, IEEE Transactions on Mobile Computing (TMC), vol. 4, no. 5, 2005, pp. 458-473.
- BABAMIR, F. S., A. HATAMIZADE, S. M. BABAMIR, M. DABBAGHIAN, A. NOROUZI, Application of Genetic Algorithm in Automatic Software Testing, in Second International Conference on Network Digital Technology, Charles University, Prague, vol. 2, July 2010, pp. 545-552.