Artificial Bee Colony Algorithm based Multi-Objective Node Placement for Wireless Sensor Network

Published Online May 2014 in MECS

Advancements in technologies such as Sensing, Electronics and Computing have attracted tremendous research interest in the field of Wireless Sensor Networks (WSNs), apart from their enormous potential for both commercial and military smart applications. The smart environment basically relies first and foremost on sensory data from the real world. The information needed by smart environments is provided by Distributed Wireless Sensor Networks (DWSN), which are Wireless sensor networks [1] are composed of a great number of sensor nodes densely deployed in a fashion that may revolutionize information collecting, which makes it a very promising technique for surveillance in military, environmental monitoring, target tracking in hostile circumstances, and traffic monitoring. The Wireless Sensor Networks (WSN) are intended for monitoring an environment. The main task of a wireless sensor node is to sense and collect data from a certain domain, process it and transmit it to the sink where the application lies. The main characteristics of a WSN include power consumption constrains for nodes using batteries or energy harvesting, ability to cope with node failures, mobility of nodes, dynamic network topology, communication failures, heterogeneity of nodes, scalability to large scale of deployment, ease of use, unattended operation etc. However, ensuring the direct communication between a sensor and the sink may force nodes to emit their messages with such a high power that their resources could be quickly depleted. Therefore, the collaboration of nodes to ensure that distant nodes communicate with the sink is a requirement. In this way, messages are propagated by intermediate nodes so that a route with multiple links or hops to the sink is established. WSNs is more dynamic network, where nodes can break, run out of energy and the radio propagation characteristics change frequently. In this study, a novel approach to the dynamic deployment problem for WSNs is proposed. This approach is based on the artificial bee colony (ABC) algorithm, which was developed by considering the foraging behavior of honey bee swarms [2] . It is known that the ABC algorithm works well for numerical optimization problems and clustering techniques [3]. There are number of reasons for ABC algorithms to be a good fit for WSN placement problem. ABC algorithms are decentralized just as WSNs and ABC algorithms have been shown to react quickly to the changes in the network [4] . So, using the ABC algorithm is a good approach for the multi-objective placement of sensors in WSN to obtain good coverage in a 2dimensional space.

The rest of this paper is structured as follows. The review of the literature is followed in Section 2, The proposed methodology is formulated in Section 3. Section 4 discusses the multi-objective optimization using ABC. Section 5 discusses the experimental results of the proposed methodology. Finally, conclusions are given in Section 6.

• II.    Related Work

Determining the positions of the sensors is the main subject of sensor network placement, which depends on the coverage of the interest area. In global positioning systems (GPS), the sensors know their positions and may also learn their nearest neighbors’ positions. In the dynamic placement problem, sensors are initially located in the area with random positions. If the sensors are mobile, they can change their positions by using their knowledge of other positions. With these movements, they try to increase the coverage rate. On the other hand, if the sensors are stationary, they do not have the ability to change their positions.

Sensor networks are different from other networks due to the limitations on battery power, node densities, and the significant amount of desired data information. Sensor nodes tend to use energy-constrained small batteries for energy supply. Therefore, energy consumption is a vital concern in prolonging the lifetime of a network operation. Many applications, such as seismic activity tracking and traffic monitoring, expect the network to operate for a long period of time, e.g., on the order of a few years. The lifetime of a wireless sensor network could be affected by many factors, such as topology management, energy efficient MAC design, power-aware routing, and energy-favored flow control and error control schemes. Different methods for reducing energy consumption in wireless sensor networks have been explored in the literature. Some approaches [5] were suggested, such as increasing the density of sensor nodes to reduce transmission range, reducing standby power consumption via suitable protocol design, and advanced hardware implementation methodology. Algorithms for finding minimum energy disjoint paths in an all-wireless network were developed [6] . SEAD [7] was proposed to minimize energy consumption in both building the dissemination tree and disseminating data to sink nodes.

On the other hand, the use of optimization techniques in the placement of WSNs is a very hot topic for researchers. Some dynamic placement algorithms have been developed for the node placement problem in WSNs [8-15] . For improving the coverage of the network, several interesting approaches like Neural Networks, Artificial Intelligence, Swarm Optimization, and Ant Colony Optimization have been implemented to tackle such problems. One of the important approaches among this research is the virtual force (VF) algorithm to optimize resources. In real-life problems, to save energy and reduce costs, stationary sensors are widely used in networks. Wang et al. considered both stationary and mobile sensors together in WSNs and proposed a new approach based on parallel particle swarm optimization [12]. Similarly, several researchers have successfully implemented evolutionary algorithm based techniques like EA, GP, ACO, PSO, TPSMA etc in wireless sensor network design [11-32] . Most of the application-specific approaches in WSN design have been focused on a single fitness function. However, these approaches either cover limited network characteristics or fail to incorporate several application specific requirements into the performance measure of the heuristic. This work tried to integrate network characteristics and application specific requirements in the performance measure of the proposed multi-optimization algorithm based on ABC methodology. The algorithm primarily finds the operational modes of the nodes in order to meet the application specific requirements along with minimization of energy consumption by the network. The implementation of the proposed methodology results in an optimal design scheme, which specifies the operation mode for each sensor.

• III.    Proposed Methodology

• 3.1    Network Architecture Model

In this work a hypothetical application which involves deployment of three types of sensors (say X, Y and Z) on a two dimensional field is considered. The sensing nodes are identical and assumed to have features like; power control, sensing mode selection and transmission power control. For monitoring of hypothetical parameters, it is assumed that spatial variability Хр ϵ X, Ур ϵ Y, Zp ϵ Z are such that Хр << , Ур <<  Zp . It means that the variation of X in the 2D field is much less than Y and the variation Y is much less than Z. i.e. the density of sensor nodes monitoring Z has to be more than Y and density of sensor nodes monitoring Y has to be more than X in order to optimally monitor the field. The methodology not only takes the general network characteristics into account, but also the above described application specific characteristics.

Consider a square field of N x N Euclidian units subdivided into grids separated by a predefined Euclidian distance. The sensing nodes are placed at the intersections of these grids so that the entire area of interest is covered (See Figure 1).

Fig. 1. A grid (mesh) based wireless sensor network layout

Figure 2 shows the structure of each node. Each node consists of four main components i.e transducer, microcomputer, transceiver and power source.

Fig. 2. Simple structure of a sensor node

Both sensors and actuators are collectively known as Transducers. Transducers are devices used to convert energy of one kind into energy of another kind. Sensors are devices that responds to a physical stimulus heat, light, sound, pressure, magnetism, motion, etc , and convert that into an electrical signal. They perform an input function. Devices which perform an output function are generally called Actuators and are used to control some external device, for example movement. Transceiver contains the functionality of both transmitter and receiver. Transceivers are often lacking unique identifiers. The operational states of transceiver are; transmit, receive, idle, and sleep. Current generation transceivers have built-in state machines that perform some other operations automatically. The micro control unit performs tasks, processes data and controls the functionality of other components in the sensor node. The micro control unit can be a general purpose desktop microprocessor, digital signal processors, FPGAs and ASICs. Each node senses the environment, performs data fusion and communicates data to its neighbors.

The nodes are capable of selecting one of the three operating modes i.e. X sense, Y sense and Z sense provided they are active. The nodes operating in X sensing mode have the highest transmission range whereas nodes in Y and Z sensing modes have medium and low transmission ranges respectively. Although several cluster based sophisticated methodologies have been proposed [29,30,31], we have adopted simple mesh architecture, wherein the nodes operating in X sense mode act as cluster-in-charge and are able to communicate with the base station (sink) via multi-hop communication and the clusters are formed based on the vicinity of sensors to the cluster-in-charge. The clusterin-charge performs tasks such as data collection and aggregation at periodic intervals including some computations. So, X sense node will consume more power than the other two modes.

• 3.2    Problem Formulation

Here we explore a multi-objective algorithm for WSN design space exploration. The algorithm mainly optimizes application specific parameters, connectivity parameters and energy parameters. This fitness function gives the quality measure of each WSN topology and further optimizes it to best topology. WSN design parameters can be broadly classified into three categories [32]. The first category colligates parameters regarding sensor deployment specifically, uniformity and coverage of sensing and measuring points respectively. The second category colligates the connectivity parameters such as number of cluster-in-charge and the guarantee that no node remains unconnected. The third category colligates the energy related parameters such as the operational energy consumption depending on the types of active sensors. The design optimization is achieved by minimizing constraints such as, operational energy, number of unconnected sensors and number of overlapping cluster- in-charge ranges. Whereas the parameters such as, field coverage and number of sensors per cluster-in-charge are to be maximized. i.e

Optimize f ( FC, OCE, SOE, SPC , E )           (1)

Where FC is a field coverage and defined as

( n_x+n_y+ n_z ) ( ^OR+^intv )

^tot

Tl_x , П_у and n_x are number of sensors in X, Y and Z categories respectively in the cluster, where n_x is the number of cluster in charge.

^OR is the number of out range sensors, ^•mtv is the inactive sensors and ^•tot is the total sensing point.

OCE is an overlap per cluster in charge error and defined as

No _ _ Overlaps =

SOE is the sensor out of range error and is defined as

SoE =

^tot nintv

SPC is sensor per cluster in-charge and is defined as

• — ^пУ^{+ nz}~ ⁿ°^R

  
  
  
  

П_с is the maximum capacity of the cluster in charge. Ideally ⁿC is set to 15.

E is the energy consumption and is defined as

.fl^TZ^. ily =

^tot

• IV.    Artificial Bee Colony (ABC) Algorithm

The artificial bee colony algorithm is a new population-based meta-heuristic approach, initially proposed by Karaboga [33,34] and further developed by Karaboga and Akay [35]. It has been used in various complex problems. The algorithm simulates the intelligent foraging behavior of honey bee swarms. The algorithm is very simple and robust. In the ABC algorithm, the colony of artificial bees is classified into three categories: employed bees, onlookers, and scouts. Employed bees are associated with a particular food source that they are currently exploiting or are “employed” at. They carry with them information about this particular source and share the information to onlookers. Onlooker bees are those bees that are waiting on the dance area in the hive for the information to be shared by the employed bees about their food sources and then make decision to choose a food source. A bee carrying out random search is called a scout. In the ABC algorithm, the first half of the colony consists of the employed artificial bees, and the second half includes the onlookers. For every food source, there is only one employed bee. In other words, the number of employed bees is equal to the number of food sources around the hive. The employed bee whose food source has been exhausted by the bees becomes a scout. The position of a food source represents a possible solution to the optimization problem, and the nectar amount of a food source corresponds to the quality (fitness) of the associated solution represented by that food source. Onlookers are placed on the food sources by using a probability-based selection process. As the nectar amount of a food source increases, the probability value with which the food source is preferred by onlookers increases too [33,34] . The main steps of the algorithm are given in Algorithm Basic [33] .

Algorithm Basic ( )

Initialization Phase

Repeat

Employed Bees Phase Onlooker Bees Phase Scout Bees Phase

Memorize the best solution achieved so far

Until (Maximum Cycle or Maximum CPU time)

In Initial phase, All the vectors of the population of food are initialized. In Employed Bees Phase Employed bees search for new food sources having more nectar within the neighborhood of the food source They find a neighbour food source and then evaluate its profitability (fitness). In Onlooker Bees Phase, employed bees share their food source information with onlooker bees waiting in the hive and then onlooker bees probabilistically choose their food sources depending on this information. In ABC, an onlooker bee chooses a food source depending on the probability values calculated using the fitness values provided by employed bees. For this purpose, a fitness based selection technique can be used, such as the roulette wheel selection method etc. In Scout Bees Phase, the unemployed bees who choose their food sources randomly are called scouts. Employed bees whose solutions cannot be improved through a predetermined number of trials, specified by the user of the ABC algorithm and called “limit” or “abandonment criteria” herein, become scouts and their solutions are abandoned. Then, the converted scouts start to search for new solutions, randomly.

• 4.1    Multi-Objective Optimization using ABC

As opposed to single-objective optimization, Multiobjective Optimization (MO) usually maintain a nondominated solutions set. In multi-objective optimization, for the absence of preference information, none of the solutions can be said to be better than the others. Therefore, in our algorithm, an External Archive (EA) is created to keep a historical record of the non-dominated vectors found along the search process. In the initialization phase, the external archive will be initialized. After initializing the solutions and calculating the value of every solution they are sorted based on nondomination. Then each solution is compared with every other solution in the population to find which one is nondominated solution. Then put all non-dominated solutions into the external archive.

In the onlooker bees’ phase, a comprehensive new learning strategy is used to produce the new solutions v / . For each bee x , , it randomly chooses m dimensions and learns from a non-dominated solution which is randomly selected from EA. The other dimensions learn from the other non-dominated solutions. The new solution is produced by using the following expression:

^vi,/(m) = ^xiJ^m+ ^{+ 0(}ТП⁾⁽ЕA k,f(m)   ^xl((m)       ⁽⁷⁾

where k e (1,2,_,p) is randomly chosen index and p is the number of solution in the EA. f(m) is the first m integers of a random permutation of the integers 1 to n, and f(m) defines, which xd dimensions should learn from EA_k . 0(m) produce m random numbers which are all between [0,2]. The m random numbers correspond to the m dimensions. Each remaining dimension learns from the other non-dominated solutions by using:

Vtj = ^xu+ ⁰ц⁽Е^Ац-^xu )                   (8)

where l^k, j e (1, 2, 3,^,p) and j not e f(m)

The external archive will be updated at each generation. As the evolution progresses, more and more new solutions enter the external archive. Considering that each new solution will be compared with every non-dominated solution in the external archive to decide whether this new solution should stay in the archive. As the computational time is directly proportional to the number of comparisons, the size of external archive must be limited. Finally, if the number of non-dominated solutions exceeds the allocated size of EA, then the crowding distance [36] is used to remove the crowded members crowding distance. The detail algorithm (ABCMO) is presented below:

Algorithm ABCMO ( )

Cycle = 1

Initialize the food source positions (solutions)xt, i = 1,2,3 ...m

Evaluate the nectar amount (fitness) of food sources

The initialized solutions are sorted based on nondomination

Store non-dominated solutions in the external archive (EA)

repeat

Onlooker Bees’ Phase

For each onlooker bee

Randomly choose a solution from EA

Produce new solution v by using equation (7)

Apply Algorithm Greedy Selection( ) to decide which solution enters EA

EndFor

The solutions in the EA are sorted based on nondomination

Keep the non-domination solutions of them staying in the EA

If the number of non-dominated solutions exceeds the allocated the size of EA,

Use crowding distance to remove the crowded members cycle = cycle + 1.

until cycle = Maximum Cycle Number

Algorithm Greedy Selection( )

If vi dominates Xi vt added to EA

Else if Xi dominates Vi

No action

Vj added to EA

Generate random number(r ϵ[0,1] )

If r < 0.5

xt is replaced by V[

Else

No action

End if

End if

Each solution represents an array that has m items.

Table 1 shows the solution array. Items of the solution array are ( x , y ) positions of the sensors in the network. Each position is associated with a bit string of two bits. These two bits decide the type of node. i.e ‘00’ being inactive, ‘01’ being X mode, ‘10’ being Y mode and ‘11’ represents Z mode.

Ш 0.9

5 0.8

> 0.7

E 0.6 о 0.5 z 0.4 м 0.3 5 0.2 < 0.1 0

100 500 1500 2000 2500 3000

No of Cycles

Fig. 3. Convergence rate of different algorithm

Table 1. Solution Array

1	2		m
( хг , У1 )	( x2 , y2 )		( Xm , Ут )

• V.    Experimental Results

  A wireless sensor network including 100 mobile sensors was simulated. The colony size was 30, and the limit parameter for the scou t was 100. The detection radius of each sensor was 2√2. The ABCMO algorithm was run with different numbers of iterations: 100, 500, 1000, 1500, 2000 and 3,000 iterations. To observe the performance of the algorithm, each scenario was run 20 times, starting with random seeds. The proposed ABCMO algorithm is applied in a field of 10 x 10 sensing nodes assuming full battery capacity. The algorithm was started, having available all sensor nodes of the grid at full battery capacities. The result of ABCMO is compared with ACO[26], PSO[37] and Territorial Predator Scent Marking Algorithm[38]. The average coverage rates with different iteration numbers are given in Figure 3.

It is clear from the above figure that the rate of convergence of ABCMO is faster than all other algorithms.

The Figures-4, 5, 6 show the optimal values of the different objective functions. Figure-4 shows the performance of different algorithm with respect to field coverage. The performance of ABCMO is comparable to other algorithms.

Figure-5 shows that in energy consumption, ABCMO outperforms all other algorithms. Figure-6 shows the performance of different algorithm with respect to sensor per cluster of WSN. The figure shows that the performance of ABCMO is better than others.

Cycles

Fig. 4. Performance of ABCMO algorithm for Field coverage of WSN

^^^^^w PSO

^^^^^™ ACO

^^^^^TPSMA

^^^^^™ABCMO

Cycles

Fig. 5. Performance of ABCMO algorithm for Energy consumption of WSN

Cycles

Fig. 6. Performance of ABCMO algorithm for Sensor Per Cluster (SPC) of WSN

Putting all together, the figure below (Figure 7) shows, how different objectives i.e FC, SOE, E, OCE and SPE are behaving during the execution of ABCMO. This figure also shows that the values of different objectives are settling through cycle 500 to 3000.

Fig. 8. Final nose placement using ABCMO algorithm

• VI.    Conclusion

In this paper, a node placement methodology for a wireless sensor network using ABCMO based multiobjective methodology is demonstrated. In ABCMO algorithm, Pareto concept and external archive strategy were used to make the algorithm converge to the true Pareto optimal front and use comprehensive learning strategy to ensure the diversity of population. The best advantage of ABCMO is that it could use less control parameters to get the most competitive performance. In order to demonstrate the performance of the proposed algorithm, we compared the performance of ABCMO with those of PSO, ACO and TPSMA based approaches. A fixed wireless network of sensors of different operating modes was considered for a 2D grid based deployment. ABCMO algorithm decided which sensors should be active, which ones should operate as cluster-in-charge and whether each of the remaining active normal nodes should have medium or low transmission range. The network layout design was optimized by considering various parameters like application specific parameter, connectivity parameters and energy related parameters. From the evolution of different network characteristics during the ABCMO optimization process, it was concluded that it is preferable to operate a relatively high number of sensors and achieve lower energy consumption for communication purposes than having less active sensors with consequently larger energy consumption.

The network optimized by the algorithm is represented by Figure 8, wherein the large red circle, medium blue circle, small green circle represents the X mode sensor (cluster-in-charge), Y mode sensor and the Z mode sensor positions respectively. Blue circles with a cross mark represent an out of range sensor node and a cross mark represents an inactive sensor node.