Multiobjective optimal positioning of the cluster heads in the heterogeneous geosensor networks
A geosensor network embedded in a geographic space is a distributed ad-hoc wireless network of sensor-enabled miniature computing platforms that monitors environmental phenomena (Nittel et al., 2004, Worboys and Duckham, 2006). It can be employed in diverse application domains each with different application requirements. Optimization approaches, techniques and strategies at different design levels help meet these application requirements (Munir and Gordon-Ross, 2011).
Geosensor networks pose various optimization problems which consider investigation and search for new optimization techniques. The techniques can be at different design levels (e.g. architecture, network topology, node component level) depending of problem type and application requirements (e.g. dynamic or static). One of the resarch problems (covered by this work) is multiobjective optimal positioning of cluster heads or the high powered relay heads (HPRH) serving clusters of the sensor nodes in a heterogeneous geosensor network for data transfer to the base station. This problem is known to belong the NP-Hard class of optimization problems (de Smith et.al., 2010). To address this problem we can use the Pareto based multiobjective genetic algorithm (PBMOGA) as a search technique. The PBMOGA is suitable to provide good solutions for optimization problems assuming competitive and conflict objectives (e.g. quality of area detection and density of sensor network, in order to find the minimum tolerable density with maximum efficiency (Xiao, 2010), or sensors coverage, cardinality and survivability in surveillance applications (Yourdan and de Weck, 2004)).
Research Statement and Objectives:
This study concerns the development and testing of the multiobjective genetic algorithm applied to clustering of sensor nodes in a heterogeneous wireless ad-hoc geosensor network. The aproach will be tested on problems in which the various classes of sensor nodes are randomly distributed over a geographical area. The multiobjective GA based mechanism will be used to search for the pareto optimum positions of cluster heads represented as artificial chromosomes within a pre-specified number of node clusters which belong to two or more various sensor types.
Research objective is to examine potential and efficiency of PBMOGA as a searching tool for alternative sets of cluster head positions in heterogeneous geosensor networks. The research also considers some questions related to the optimization, geosensor network heterogenity and in-network data processing.
Performance optimization in wireless geosensor networks can be achieved through proper physical layers design for energy savings and increased throughput. It considers application of various configuration scenarios with objectives for surveillance applications, power allocation strategies for networks lifetime maximization, throughput and lifetime maximization in clustered networks, and integration of radio control technology for high energy efficiency (Medagliani and Ferrari,2011). Various perspectives, approaches and objects of in-network processing optimization have been considered e.g. development localization algorithms (Kealy and Duckham, 2009), dynamic query optimization (Galpin et al., 2008), distributed algorithms (Rabbat and Nowak, 2005), cross-layer (Cui and Goldsmith, 2006.) and multi-query algorithms (Trigoni et al., 2005.), environmental monitoring aproaches (Worboys and Duckham, 2006) and many others.
There are few examples with multiobjective algorithm application in real-world spatial optimiziation problems, including geosensor networks field, which are characterized with the complexity of the multiple conflict objectives and large searching space. Related to sensor networks and the optimization problems, the genetic algorithm applications have been considered for clustering dynamic geosensor networks to minimize the total communication distance and prolong the network life (K.Raman and P.Vaidya, 2006), for clustering of the nodes into groups and forming a backbone for data transfer (R. Sachdev and K. Nygard, 2009), in multiobjective optimization of wireless geosensor network layouts (D. Jourdan and O. de Weck, 2005), for multiobjective placement of water quality sensors in water distribution systems (Z. Yi Wu and T. Walski, 2006) and others. Generally, this area of multiobjective GA application is not broader covered and this represents a motivation reason for more research efforts.
To detect the conditions or events in a wide-area geographic space, a monitoring application requires a large-scale geosensor network including various kinds of sensors. As well, many large, autonomous sensor platforms will be integrated with the deployment of small-form sensor networks providing rapid rates of real-time sensor data of various type, scale and location. The application of domain knowledge is also necessary in order to interpret and understand an environmental condition, based on the collected data (Jung and Nittel, 2008).
The deployed geosensors fulfill sensing, communication andcomputation functions. The sensing can be of different types (chemical, seismic, optical, acoustic, temperature and humidity statistics,..), and the communication is performed wirelessly (within a shorter or longer range) (Jourdan and de Weck, 2004).
To transmit their data to the base station (central monitoring server), for a specific network arhitecture, all the sensors are required to be connected to one or more high powered relay heads (cluster heads). The sensors are assumed to have different computation and communication abilities, i.e. properties which can significantly vary depending on the type of sensing performed. The criterial properties (e.g. environmental affects to communication or sensing rang) can be formulated by fuzzy aproach as well, and involved in the modelling.
This framework can be used to test a Pareto based multi objective genetic algorithm (PBMOGA) for the cluster head placement, where the competing objectives considered are the objectives (e.g. minimized total power consumption) related to the clusters of different type sensor nodes sharing the same geographic area. The objectives should be conflicted, and their evaluation should meet the requirements of the iterative process of searching solutions.
The algorithm aims at minimizing or maximizing all the objectives of the heterogenous geo-network simulatously, yielding Pareto front (PF) from which the user can choose the prefered alternative solution. The number of cluster heads (hubs) can be investigated as a design variable, as well as different sensing objectives.
The research methodology is based on theoretical considerations, modeling, simulation of different variants of the problem by using test examples, implementation of the proposed mechanism and analysis of the results.
The steps of the research are as follows:
review and analysis of genetic algorithm applications in the field of geosensor networks;
define the clustering problem in heterogeneous geosensor networks and develop a detailed research methodology;
define the approach in the application of genetic algorithm for multiobjective optimization through the presentation of its building blocks (crossing, mutation, selection…) and consideration of its specific parameters;
modeling the test problem environment and defining the objective functions;
initial application PBMOGA and its parametric adaptation in order to improve its performance;
final PBMOGA implementation;
testing and evaluation of the results and
drawing conclusions and directions for further research.
Software tools and laboratory resources:
resources available at the Civil Engineering Faculty in Sarajevo and Mining, Geology and Civil Engineering Faculty in Tuzla (tools for spatial data analysis),
available lab resources at the Laboratory for Intelligent Management of Electrical Engineering in Sarajevo (MatLab, GA Tools, GAOP; tools for the creation, development and application of genetic algorithm)
Abraham, A., Jain, L., and Goldberg, R. (2005): Evolutionary Multiobjective Optimization, Theoretical Advances and Applications, Springer-Verlag London Ltd.
Coello Coello, C., Veldhuizen, D., and Lamont, G. (2002): Evolutionary Algorithms for Solving Multi-Objective Problems, Kluwer Academic / Plenum Publishers, New York
Cui, S., and Goldsmith, A. (2006): Cross-layer Design in Energy-constrained Networks Using Cooperative MIMO Techniques, EURASIP Journal on Applied Signal Processing, Special Issue on Advances in Signal Processing-based Cross-layer Designs, Vol. 86, No. 8, pp. 1804-1814
de Smith, M., Goodchild, M., and Longley, P. (2010): Geospatial Analysis – Comprehensive Guide to Priciples, Techniques and Software Tools, Matador, UK
Galpin, I., Brenninkmeijer, C., Jabeen, F., Fernandes, A., and Paton, N. (2009): Comprehensive Optimization of Declarative Sensor Network Queries, Proceeding SSDBM
Gowri, A., Valli, R.,and Muthuramalingam, K. (2010): A Review: Optimal Path Selection in Ad hoc Networks using Fuzzy Logic, International journal on applications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC JOURNAL) Vol.2, No.4,
Jourdan, D. and de Weck, O. (2004): Layout Optimization for a Wireless Sensor Network Using a Multi-Objective Genetic Algorithm, Proceedings of the IEEE Semiannual Vehicular Technology Conference, Volume 5. 2466-2470
Jung, Y., Nittel, S. (2008): Geosensor Data Abstraction for Environmental Monitoring Application, GIScience 2008: pp 168-180
Kealy, A. and Duckham, M. (2009): Optimizing Localization Algorithms within Wireless Sensor Networks: An Australian Case Study in Environmental Monitoring,” in Proc. 22nd International Meeting of the Satellite Division of The Institute of Navigation, pp. 1042-1049.
Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. (2001): Coverage Problems in Wireless Ad-hoc Sensor Networks, INFOCOM
Krzanowski, R., Raper, J. (2001): Spatial Evolutionary Modeling, Oxford University Press, Inc. NewYork
Medagliani, P., Ferrari, G. (2011): Performance Optimization in Wireless Sensor Networks: Analysis and Simulation Perspectives, LAP LAMBERT Academic Publishing
Munir, A., and Gordon-Ross, A. (2010): Optimization Approaches in Wireless Sensor Networks, Sustainable Wireless Sensor Networks, Edited by: W. Seah and Y. Tan, InTech
Ng, K., Wang, Z., Muntz, R., and S. Nittel (1999): Dynamic Query Re-Optimization, International Conference on Scientific and Statistical Databases (SSDBM99), Cleveland, Ohio
Nittel, S., Duckham, M., Kulik, L. (2004): Information Dissemination in Mobile Ad-Hoc Geosensor Networks, GIScience 2004: pp. 206-222
Nittel, S., Leung, K., Braverman, A. (2004): Scaling Clustering Algorithms for Massive Data Sets using Data Streams, ICDE 2004: pp. 830
Nittel, S., Leung, K. (2004): Parallelizing Clustering of Geoscientific Data Sets using Data Streams, SSDBM 2004: pp. 73-84
Rabbat, M.and Nowak, R. (2004): Distributed Optimization in Sensor Networks, IEEE/ACM Symp. on Information Processing in Sensor Networks
Raman, K. and Vaidya, P.(2006): Clustering Sensor Network using Genetic Algorithm, ECE695 Project
Sachdev, R., and Nygard, K. (2009): Genetic Algorithm for Clustering in Wireless Adhoc Sensor Networks, GSN ’09 Proceedings of the 3rd International Conference on GeoSensor Networks , Springer-Verlag
Trigoni, N., Yao ,Y., Demers, A., Gehrke, J., and Rajaraman, R. (2005): Multi-query Optimization for Sensor Networks, In Proceedings of the IEEE/ACM International Conference on Distributed Computing in Sensor Systems (DCOSS)
Whittle, P. (2007): Networks: Optimisation and Evolution, Cambridge University Press, UK
Worboys, M.and Duckham, M. (2006): Monitoring qualitative spatiotemporal change for geosensor networks, International Journal of Geographic Information Science, vol. 20, iss. 10, pp. 1087-1108
Wu, Z. and Walski, T. (2006): Multi objective optimization of sensor placement in water distribution systems, 2006 Annual Symposium on Water Distribution Systems Analysis, Cincinnati, Ohio