Share This Article:

Optimizing Inter Cluster Ant Colony Optimization Data Aggregation Algorithm with Rendezvous Nodes and Mobile Sink

Full-Text HTML XML Download Download as PDF (Size:1255KB) PP. 16-24
DOI: 10.4236/wsn.2017.91002    569 Downloads   764 Views  
Author(s)    Leave a comment


Energy conservation is becoming the main critical issue in wireless sensor network and also the main research area for most of the researchers. For improving the energy efficiency, sink mobility is used with constrain path in wireless sensor network. In order to solve these optimization problems, inter cluster Ant Colony Optimization Algorithm (ACO) is used with mobile sink (MS) and rendezvous nodes (RN). The proposed algorithm will improve 30% more network lifetime than the existing algorithm and prompts high accurate delivery of packets in highly dense network. a

1. Introduction

Wireless sensor networks are a special kind of Ad hoc networks that became one of the most interesting areas for researchers. Typically, a wireless sensor network comprises of hundreds or thousands of low cost sensor nodes. A sensor node consists of small sensors able to detect light, sound, temperature and motion, an intelligent computing device that enables the processing of raw data collected from the sensors and communication capabilities with other nodes through wireless networks. There are many practical applications of wireless sensor net- works. Some of the most promising application areas are environmental moni- toring, battlefield tracking and disaster recovery operation, building control sys- tems and smart entertainment devices that adjust audio and video signals based on their surroundings. A sensor node consists of four basic components: a sens- ing unit, a processing unit, a communication unit and a power unit. The sensing unit comprises one or more sensors and an analog to digital converter. Environmental parameters are sensed by the sensors and analog signals are generated. An analog to digital converter (ADC) converts analog signals to digital signals and sends them to the processing unit, which is composed of a microcontroller or microprocessor with memory and is responsible for sensor node control. The communication unit contains a short-range radio used to transmit and receive data over radio channels. The power unit includes the battery supply. To perform other tasks, systems such as a global positioning system (GPS) unit can be added to identify the sensor node location [1] .

Data Aggregation: the purpose of aggregating the data is to minimize the power consumption by reducing the number of information transmissions. Data aggregation is defined as the method of aggregating the data from multiple sensors to remove redundant transmission and provide fused information to base station. All the aggregation nodes collect data from base station. All the aggregation nodes collect data from the leaf nodes and calculate the value of aggregation. Then only the calculated aggregated values are forwarded to the data sink. The aggregate value can be average, maximum, minimum, summation, etc. It is calculated as per requirements of the application. Data generated from neigh- bouring sensors is usually redundant and highly correlated. The amount of data generated in large sensor networks is usually huge for the sink to process. The data aggregation often involves the fusion of data from multiple numbers of sensors at intermediate nodes and the transmission of the aggregated data to the base station [2] .

2. Paper Organization

The rest of the paper is organized as follows. Section 3 describes the brief introduction of related work. The problem formulation and its solution are described in Section 4. Section 5 describes the overview of ant colony optimization algorithm. Section 6 explains the proposed methodology. The simulation results and its explanation are given in the Section 7 before the conclusion in Section 8.

3. Related Work

Clustering is used in wireless network in order to collect the data from different groups of nodes. These nodes elect the cluster head, if the respected node satisfies the threshold condition. The role of cluster head is data aggregation and informs it to the base station. This technique is used to reduce the energy consumption by nodes and to improve the routing of data packets which further reduces the cost of system. From routing perspective, clustering splits into two parts intra-cluster and inter-cluster routing. a) Intra-cluster Routing: Intra clustering routing, uses a single hop communication between different nodes and elected cluster head. The clustering takes place within the cluster. b) Inter-cluster Routing: Inter cluster routing; there is a direct communication between cluster head and base station. All the nodes within a cluster collect the data and send it to the cluster head. Cluster head route the data packet to the base station with a single hop. Inter cluster routing is used for long communication.

There are two type of clustering network: first is heterogeneous sensor network and second is homogeneous sensor network. In homogeneous sensor network, all the sensor nodes are same in term of battery energy and hardware complexity while in heterogeneous network two or more different types of nodes with different batteries and functions are used [3] .

A mobile sink (MS) is an alternate way to reduce energy consumption. The MS moves inside the environment to collect node data. Sink movement may be controlled or uncontrolled. In controlled methods, the MS trajectory is pre- defined, uncontrolled MS, the sink moves randomly in a predetermined environment. Moving the sink close to normal nodes decreases the transmission distance. MSs have been studied to increase lifetimes WSNs used MS to examine total tour distance, the maximum distance between two consecutive movements, and the minimum sojourn time at each sojourn location. Therefore, one idea has been developed, which is called Rendezvous Points (RPs). The RP is a point near the trajectory of a MS and node (rendezvous node; RN) located nearby. This node transmits data to the MS as it passes nearby. Previous studies have demonstrated the effectiveness of RPs on the performance MSs studied the effect of MS movement (like a bus) on a predetermined trajectory and the use of RN for data collection. The MS sends signals called beacons that notify the RNs of the MS arrival [4] .

4. Problem Definition & Solution

4.1. The Problem

Energy conservation is becoming the major challenge for researchers. Many optimization techniques and protocols are used in order to conserve the energy and for improving the routing of data packets. The major drawback of existing technique is that the nodes dead too early. So by using the energy in good manner will help in increasing the network lifetime. Sensor nodes have negative properties which reduce the efficiency of a system and the system cannot achieve its peak values. Therefore, it becomes important to collect the complete data and transfer it to the mobile sink in order to decrease the energy consumption. Different techniques have been studied to reduce the power consumption by nodes like rendezvous leach and many other leach protocols. Rendezvous leach shows better results but it has the problem for example the use of the inter cluster data aggregation has been neglected in the most of existing protocols. The use of ACO for efficient path selection has also been neglected by the most of researchers. However the rendezvous nodes based LEACH outperforms over the LEACH in terms of the network lifetime, but has very poor stability period i.e. the first node become dead too early.

4.2. Solution

Ant Colony Optimization is used in optimizing the network lifetime. This work has focused on evaluating the performance of existing rendezvous nodes based LEACH protocol and proposed inter-cluster Ant Colony Optimization algorithm using mobile sink and rendezvous nodes. The proposed technique has been designed and implemented in the MATLAB using data analysis toolbox. The comparative analysis shows that the inter cluster ACO data aggregation performs better than the rendezvous Leach.

5. Ant Colony Optimization

Ant Colony Optimization (ACO) is a meta-heuristic used for solving the optimization problems and it is inspired by a pheromone left behind by the ant; such pheromone is used as a communication medium by the ants. Particularly important for some ant species is the trail pheromone. By sensing pheromone trails foragers can follow the path to food discovered by other ants. This collective trail-laying and trail-following behaviour whereby an ant is influenced by a chemical trail left by other ants is the inspiring source of ACO.

The sensor network modeled as weighted graph G (V, E) where multiple source src V and a single destination d V. The cost of edge indicates nodes within direct communication range and cost is an estimate measured as Euclidean distance. The input to algorithm is list of source nodes src V. The algorithm assigns ants to source nodes. The ants search the routes and communicate with other through pheromones. The node potential is an estimate of distance to destination. Each ant iterates to construct aggregation tree where internal nodes are aggregate points. The ants either try to find shortest route to destination and terminates or finds closest aggregation point of the route searched by previous ants and terminates. The algorithm converges to local best aggregation tree. In order to find the global optimal aggregation nodes, the algorithm iterates on different permutations of source nodes with cost associated with each to converge in minimum cost. The algorithm converges to minimal cost aggregation points of aggregation tree. In order to converge with early aggregation, weight is given to search the closest aggregation point.

To search shortest path to destination weight is given to the distance estimates to destination. The node potential remembers estimate closest aggregation point or shortest route to destination. The traced edges are weighted using pheromone which communicates with other ants. The optimal path edges converge with minimal weights of pheromone. The non-optimal edges gets evaporated their pheromone. Thus, algorithm is governed by pheromone trails and node potential. The algorithm runs in two passes: Ants from source moves forward to destination searching the route to destination and ants takes reverse pass from destination to source updating pheromone trails over the edges and updating node potential as estimate for reaching closest aggregation or destination. The governing equations for passes are given below: an artificial ant placed randomly in nodes and during each iteration, chooses next node which is governed by following formula:


α: relative importance of pheromone trial.

β: relative importance of the distance.

g: neighborhood of current node i.

dij: node potential, gives estimate of early aggregation or shortest route to destination [5] .

In the reverse pass each ant updates pheromone trails and node potential. The governing equations pheromone trials are follows:


where ρ and Q are ACO parameters and total cost is obtained from first pass.

For other nodes i.e. not visited in first pass pheromone evaporates more rapidly for lower values:


The node potential is weighted function of either reaching nearest aggregation point or shortest route to destination or having high correlation updated as follows:


where γ and η are weights of choosing early aggregation or choosing route to destination i.e. distance estimates and κ is the weight for choosing data correlation.

6. Inter Cluster Ant Colony Optimization Algorithm

Following are the various steps required to successfully simulate the proposed algorithm. The design and flow of implementation and step by step description of the proposed algorithm is detailed as follows.

Step 1. First of all initialize WSN with their respective characteristics.

Step 2. For each sensor node, i repeats the following steps.

Step 3. If given node has energy more than 0 that means it is alive node only then repeat upcoming steps else move back to Step 2.

Step 4. Select node as a CH if it holds the properties of improved node waiting based cluster head selection.

Step 5. Now association of the nodes will be done with their nearest CHs by using ACO.

Step 6. Update the remaining energy of each node i.

Step 7. Check if there is any dead node, if NO, then move to the Step 2 else count the no of dead nodes and show the network lifetime.

Step 8. Evaluate energy dissipation and move to Step 2.

7. Simulation Results & Discussion

The Inter cluster ACO data aggregation based rendezvous and mobile sink algorithm is simulated in MATLAB R2013a by varying the number of nodes and fixing the number of rounds. The figures below are showing the comparison of LEACH, rendezvous nodes based LEACH and inter cluster ACO based data aggregation algorithm.

First Node Dead and Last Node Dead

Figure 1 below is showing the comparison of existing RZ LEACH & proposed ACO RZ LEACH algorithm. In case of existing RZ LEACH the first node dead at 31 round and last node dead at 60 round while in proposed ACO RZ LEACH the first node dead at 56 round and last node dead at 92 round. Therefore, the first node dead time is improved in the proposed algorithm.

Average Remaining Energy

Average remaining energy means the residual energy left behind in each sensor node. Figure 2 below is showing the comparison of existing RZ LEACH & proposed ACO RZ LEACH algorithm. The average remaining energy in case of proposed algorithm is 2.7 × 10−3 Joules while in existing technique the remaining energy is 1 × 10−3 Joules. Therefore, the remaining energy in proposed ACO RZ LEACH is more as compared to the existing RZ LEACH.

Average Throughput

Average Throughput means the large number of packets send to base station at high speed. Figure 3 below is showing the comparison of existing RZ LEACH & proposed ACO RZ LEACH algorithm. The number of packets send to base station in proposed ACO RZ LEACH is more as compared to the existing RZ LEACH.

8. Conclusion and Future Scope

Inter-cluster Ant Colony Optimization algorithm has been used along with rendezvous nodes for transferring the data packets in the wireless sensor network. The improvement has been made in order to reduce the efforts wasted in routing the data packets sent by the nodes, which lies very close to each other in a densely deployed network. This work has not considered any compression algorithm to enhance the results further, so in near future, we will use Huffman coding, run length coding, LZW compression etc., algorithms to find best suitable compression technique for WSNs. The proposed technique has been designed and implemented in the MATLAB using data analysis toolbox. The comparative analysis shows that the inter cluster ACO data aggregation performs better than the rendezvous Leach.

Figure 1. First node & last node dead evaluation in existing RZ LEACH & proposed ACO RZ LEACH (1000 nodes vs. no of rounds).

Figure 2. Average remaining energy evaluation in existing RZ LEACH & proposed ACO RZ L E LEACH (1000 nodes vs. energy in Joules).

Figure 3. Average throughput evaluation in existing RZ LEACH & proposed ACO RZ LEACH (1000 nodes vs. no of packets send to BS).

Cite this paper

Ghotra, A. (2017) Optimizing Inter Cluster Ant Colony Optimization Data Aggregation Algorithm with Rendezvous Nodes and Mobile Sink. Wireless Sensor Network, 9, 16-24. doi: 10.4236/wsn.2017.91002.


[1] Munjal, R. and Malik, B. (2012) Approach for Improvement in LEACH Protocol for Wireless Sensor Network. Proceedings of 2nd IEEE International Conference on Advanced Computing & Communication Technologies, Rohtak, 7-8 January 2012, 517-521.
[2] Virmani, D., Sharma, T. and Sharma, R. (2013) Adaptive Energy Aware Data Aggregation Tree for Wireless Sensor Networks. International Journal of Hybrid Information Technology, 6, 26-36.
[3] Singhal, S., Gankotiya, A., Kumar, A. and Shikha, V. (2012) An Investigation of Wireless Sensor Network: A Distributed Approach in Smart Environment. Proceedings of 2nd IEEE International Conference on Advanced Computing & Communication Technologies, Rohtak, 7-8 January 2012, 522-529.
[4] Saeid, M. and Zahabi, M.R. (2015) Optimizing LEACH Clustering Algorithm with Mobile Sink and Rendezvous Nodes. AEU-International Journal of Electronics and Communications, 69, 507-514.
[5] Dorigo, M., Birattari, M. and Stutzle, T. (2006) Ant Colony Optimization. Published in IRIDIA, Institut de Recherches Interdisciplinaires et de D’eveloppements en Intelligence Artificielle UNIVERSITE’ LIBRE DE BRUXELLES Av F. D. Roosevelt 50, CP 194/6 1050 Bruxelles, Belgium.

comments powered by Disqus

Copyright © 2018 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.