Session:

LBP - Late Breaking Papers

Title:

Ant Colony Algorithms for Routing in Sensor Networks

Authors:

Sanjoy Das
Gurdip Singh
Seep Pujar
Praveen Koduru

Abstract:

The ant systems optimization approach is a new method of solving combinatorial optimization problems. It was originally introduced as a metaheuristic approach for the well-known traveling salesman problem. But it was subsequently shown to be an equally effective algorithm for solving other optimization problems. In this paper, we present an ant colony algorithm for data-centric routing in sensor networks. In each pass of the proposed algorithm, ants are placed at the terminal nodes of the tree to be computed. They are then allowed to move towards one another, along the edges of the graph, until they merge into a single entity. In this process, the paths taken by the ants define a data distribution tree. Edges receive reinforcement in the form of pheromone deposits along the paths taken by the ant. Pheromones eventually accrue most along better edges. In addition to forward and backwork ants, we also use random ants whose purpose is to enable sharing of information pertaining to a node potential with neighboring sensors. Since ant algorithms perform computations solely through local interactions between ant-like agents by means of pheromones, they scale well for large-scale applications, and are particularly attractive for real world systems. The algorithm can easily be used in several practical applications.