Cellular Automaton Based Localized Algorithms for Mobile Sensor Networks

Mobile wireless sensor networks involve many aspects not dealt with in traditional networks, and therefore, can be viewed as an unconventional computational model. We design algorithms for mobile wireless sensor networks based on another unconventional model of computation, namely, the biologically-inspired cellular automaton. The main advantage of using cellular-automaton-based algorithms is that they are strictly local algorithms, and as such are more suitable for sensor networks. We design cellular-automaton-based algorithms for three optimization problems in connection with mobile wireless sensor networks. The first problem involves a set of connected sensors that are deployed randomly in a network. The goal of the algorithm is to gather all the sensors at a single location. In the second problem, we are given a set of sensors which form a chain. All sensors except for the two end points of the chain are connected to their two neighbors, right and left. The two end points are fixed and can directly communicate with only one neighbor. Other sensors can move autonomously. At an initial configuration of the network, the chain can be winding and even overlap with itself. Our goal is to move the sensors so that they can come as close as possible to the direct line between the two end points, and while the sensors move the network should remain connected. In the third problem, a number of mobile sensors and mobile objects are deployed randomly in a dense area of the network and are allowed to move within the network. Our main goal is to monitor the mobile objects by the mobile sensors as long as possible. We show that our algorithms perform better than existing algorithms for all three problems.