An Improved Ant Colony Broadcasting Algorithm for Wireless Sensor Networks

Abstract

Recent advances in nano-technology have made it possible to develop a large variety of Micro Electro-Mechanical Systems (MEMS)–miniaturized low-power devices that integrate sensing, special-purpose computing, and wireless communications capabilities. A sensor network is a collection of many small devices, each with sensing, computation, and communication capability. It has many potential applications, such as building surveillance and environmental monitoring. Broadcasting is defined that communications between one source and all receiver in networks, and it is widely used in Wireless Sensor Networks. Therefore, how to design an efficient and scalable broadcast protocol is challenging and meaningful work.

Ant Colony Algorithm is a bionic optimization algorithm which simulated insect behavior of ants swarm intelligence. It is robust, has excellent advantages of distributed computation mechanism, and it has been widely applied to the solution of TSP, production scheduling, Graph Coloring Problem, and other combinatorial optimization problems. Broadcasting in wireless sensor networks is very similar with the ants routing problem. The target nodes and source nodes for broadcasting can be respectively compared to food and ant nests, and broadcasting problem can be regarded as the issue that ants find the optimal path between food and nests. When using ant colony algorithm for broadcasting, ants pheromone is calculated to select the path in accordance with the transition probability, and each ant in the path does not need access to all the information before starting, thus this will avoid the calculation of overhead of the initialization of parameters information in all nodes and the paths, and achieve the goal of multi-path data broadcasting in large-scale sensor networks.

In this paper, we describe the broadcasting problem in sensor networks and introduce a network model, and after considering energy efficient broadcast in such networks, combined the characteristic of Wireless Sensor Networks and the properties of ant algorithm to quickly identify an optimal path, we introduce and evaluate an improved ant colony broadcasting algorithm (IACBA), which can adaptively find the optimal broadcasting path without global network information. In our simulation, the notion of network density is introduced in order to identify classes of network topologies with similar characteristics. We mainly analyze energy depletion, minimum distance, and network lifetime, and the results show that out algorithm can reduce energy depletion dramatically and decrease communication distances in broadcasting, and our algorithms can prolong network lifetime by about 10%–20% compared with BIP, and about 30%–50% compared with flooding.