Evolutionary Computing Approaches for Clustering and Routing in Wireless Sensor Networks

Evolutionary Computing Approaches for Clustering and Routing in Wireless Sensor Networks

Pratyay Kuila (NIT Sikkim, India) and Prasanta K. Jana (Indian School of Mines, India)
DOI: 10.4018/978-1-5225-0058-2.ch011
OnDemand PDF Download:
No Current Special Offers


With proliferation of Computational Intelligence (CI), evolutionary algorithms have drawn enormous attention among researchers. Such algorithms have been studied to solve many optimization problems. Clustering and routing are two well known optimization problems which are well researched in the field of Wireless Sensor Networks (WSNs). These problems are NP-hard. Therefore, many researchers have applied meta-heuristic approaches to develop various evolutionary algorithms to solve them. In this chapter, the authors rigorously study and present various evolutionary algorithms that include Genetic Algorithm (GA), Particle Swarm Optimization (PSO) and Differential Evolution, etc. and show how these algorithms are applied to solve clustering and routing problems in WSNs. The chapter starts with an introduction of WSNs along with clustering and routing problems in WSNs accompanied by a discussion why these problems are solved by evolutionary algorithms. The authors then give an overview of various evolutionary approaches that are applied to solve clustering and routing problems. Various evolutionary algorithms are then presented towards the solution of these problems. A comparison table is also made by highlighting strengths and weaknesses of the algorithms. Finally, the authors present new directions of future research in this domain.
Chapter Preview



Wireless sensor networks (WSNs) have drawn considerable attention for their wide range of applications in the areas of environment monitoring, surveillance systems, disaster management, health care and so on (Akyildiz, Su, Sankarasubramaniam, & Cayirci, 2002). A WSN consists of a large number of tiny and low power sensor nodes, which are randomly or manually deployed across a target area. These sensor nodes periodically collect local information of the target area, process the data and finally send it to a remote base station (called sink) either through single hop or multi hop communication. The sensor nodes are equipped with sensing, processing and transmitting component along with a power unit. They have limited sensing, processing and transmission capabilities. Most importantly they have limited power source as they are operated by small batteries. Moreover, for a harsh environment, it is hard to replace the batteries or whole sensor nodes when their energy is completely exhausted. Therefore, energy consumption of the sensor nodes is the most challenging problem for the long run operation of WSNs (Anastasi, Conti, Di Francesco, & Passarella, 2009). Various studies and researches have been carried out for this purpose which include low-power radio communication hardware (Calhoun et al. 2005; ZENG, ZOU, LIU, & LEI, 2007), energy-aware medium access control (MAC) layer protocols (Alkhatib and Baicher, 2012; Yigitel, Incel, & Ersoy, 2011) and duty-cycling (de Paz Alberola & Pesch, 2012; Carrano, Passos, Magalhaes, & Albuquerque, 2014; Chandanala, Zhang, Stoleru, & Won, 2013). Apart from all above things, energy efficient clustering and routing are the most two important topics which have been extensively addressed by research community (Kuila & Jana, 2015, 2012a, 2012b, 2011; Singh, Kuila & Jana, 2014; Azharuddin, Kuila, & Jana, 2013; Low, Fang, Ng, & Ang, 2008). In a cluster based WSN, the sensor nodes are divided into several groups called clusters and each cluster has a leader known as cluster head (CH). In this architecture, all sensor nodes sense local data and send the data to their corresponding CH. Then the CHs aggregate the collected data and finally send the aggregated data to the base station directly or using multi hop communication via other CHs. The functionality of a cluster based WSN can be seen in Figure 1.

Figure 1.

A Wireless sensor network model, red arrows show the communication between sensor nodes and their corresponding CHs and black arrows for the same between CHs to CHs/base station


A cluster based WSN has many advantages (Abbasi & Younis, 2007) as follow: 1) it enables data aggregation at cluster head to throw away the redundant, unnecessary and uncorrelated data. It is worth to note that the amount required energy for transferring one bit of data can be used in high volume of data aggregation. Thus clustering helps to reduce energy consumption of the network by preventing transmission of high volume of redundant data. 2) Routing can be more easily managed because only CHs need to maintain the local route set up of other CHs and thus require small routing information. Thus it improves the scalability of the network significantly. Furthermore, as compared to flat architecture, cluster based architecture can efficiently reduce the routing delay. Because, for a WSN with n sensor nodes and m clusters (n > m), it would be more efficient if the data are routed among m CHs rather than n sensor nodes. It is more efficient when n>>m. 3) The cluster based architecture can conserve communication bandwidth as the sensor nodes communicate with their corresponding CHs only and thus avoid exchange of redundant messages among themselves.

In many WSNs, the CHs are usually selected amongst the normal sensor nodes and they die quickly due to the extra workload to receive the sensed data from their member sensor nodes, data aggregation and frequent communication with the sink. In this context, many researchers (Bari, Wazed, Jaekel, & Bandyopadhyay, 2009; Low et al., 2008; Bari, Jaekel, & Bandyopadhyay, 2006; Gupta and Younis, 2003; Kuila and Jana, 2014a) have shown the use of some special nodes called gateway or supreme node. The gateways are provisioned with extra energy to act as cluster heads and are responsible for the same functionality of the CHs. Unfortunately, they are also battery-operated and hence power constrained. Lifetime of these supreme node is very crucial for the long run operation of the WSN.

In routing phase, CHs may use single-hop (SHDTM) (Heinzelman, Chandrakasan, & Balakrishnan, 2002) or multi-hop data transmission model (MHDTM) to communicate with the base station (BS) (Bari et al., 2009). In SHDTM, each CH transmits its data directly to the BS, assuming that the distance from each gateway to the BS is less than the transmission range of the gateway. On the other hand, in MHDTM, the CHs generally use some intermediate CHs which act as relay node(s) to forward the data to the BS (Bari, Jaekel, & Bandyopadhyay, 2008; Low et al., 2008; Bari et al., 2009). However, the CHs which are closer to the BS or on some energy efficient path are frequently used as the relay nodes and thus they may drain their energy quickly. Therefore, selection of proper next hop relay nodes is called for research while designing energy saving routing in WSNs.

Complete Chapter List

Search this Book: