The ease of use and re-configuration in a wireless network has played a key role in their widespread growth. The node deployment problem deals with an optimal placement strategy of the wireless nodes. This paper models a wireless sensor network, consisting of a number of nodes, and a unique sink to which all the information is transmitted using the shortest connecting path. Traditionally the systems have used Genetic Algorithms for optimal placement of the nodes that usually fail to give results in problems employing large numbers of nodes or higher areas to be covered. This paper proposes a hybrid Genetic Programming (GP) and Genetic Algorithm (GA) for solving the problem. While the GP optimizes the deployment structure, the GA is used for actual node placement as per the GP optimized structure. The GA serves as a slave and GP serves as master in this hierarchical implementation. The algorithm optimizes total coverage area, energy utilization, lifetime of the network, and the number of nodes deployed. Experimental results show that the algorithm could place the sensor nodes in a variety of scenarios. The placement was found to be better than random placement strategy as well as the Genetic Algorithm placement strategy.
TopIntroduction
From the last few years, Wireless Sensor Networks (WSN) have come out as the most important networking paradigm, both in terms of their viable prospective and also from a scientific point of view. WSNs are important because of their numerous applications; vary from military use to environmental monitoring (measuring temperature, humidity, & solar radiation etc.) and from wildlife to disaster management. Efficient sensor node deployment is essential to sense, gather and process the data. Therefore, in the last few years there is a shift in research activities in this field. Traditionally sensors nodes were distributed randomly or uniformly due to ease and effortlessness. But random or uniform allotment of sensor nodes is sub-optimal and further leads to the Sink Routing-Hole Problem (SRHP).
Sensor nodes transmit the information to the sink via multiple hops as shown in Figure 1. A node near the sink gets data transmitted by farther nodes as well, in addition to its own data, which is finally transmitted to the sink. Thus a node closer to the sink transmits more data than the ones farther from it. The problem with these networks is maximized if some node near the sink fails (Yunhuai, Ngan, & Ni, 2007). The restriction with WSN is their limited source of energy (as they are composed by battery supplied nodes), concern of the coverage constraint, and the trustworthiness and life-time of network. Whenever WSN designers plan WSN they have to consider these considerations along with number of sensor nodes to wrap the region since wireless sensors are still expensive.
Figure 1. Passage of information from sensor nodes to sink
The problem of sensor deployment for an optimal sensor network layout can be solved using either of the two strategies: (i) find the minimum number of sensor nodes of given energy to cover the region with appropriate reliability and a good life time, and (ii) for a given number of sensor nodes, find out a set of points and the power levels which give the best trade-off between coverage area, lifetime and energy utilization of the network with appropriate reliability.
While the first strategy limits the maximum area to be covered, keeping the number of sensor nodes variable; the second strategy keeps the number of sensor nodes fixed, making the other parameters variable. In this paper we propose an algorithm for optimizing the number of nodes, as well as the area, lifetime and energy, by using a hybrid of Genetic Programming (GP) and Genetic Algorithms (GA).
Evolutionary Algorithms are an inspiration from the natural species that develop along with generations. The generation of higher generation by the lower generation is done by the application of Evolutionary operators (Melanie, 1999). The Evolutionary Algorithms may be fundamentally categorized into three heads. These are Genetic Algorithms, Genetic Programming and Evolutionary Strategies (Schwefel, 1975; & Rechenberg, 1973). In Genetic Programming (GP) the individual is usually given a tree-based representation and represents a program, solving the fitness of the individuals may be determined (Fogel, 1992). The Genetic Algorithm (GA) makes use of a bit string or a double vector representation where the various properties of the individual are encoded in a contiguous manner to make a vector or string.
Both GP and GA are widely used for a variety of problems. These algorithms however fail to give good results if the fitness landscapes are very complex or highly dimensional in nature. The inability of a single evolutionary technique to solve the optimization problem, gives rise to hybridization of two or more evolutionary techniques (Hou, Chen, & Jeng, 2010) for better convergence and optimization (Baffo & Confessore, 2010). In this hybrid algorithm, evolutionary algorithms assist each other to achieve a high degree of optimization in a finite amount of time. Here two evolutionary techniques work in master slave mode (Edwin, Thierens, & Watson, 2004).