Distributed computation in wireless ad hoc grids with bandwidth control

There are many situations in which information from a Wireless Sensor Network (WSN) must be processed to provide a meaningful summary to an external agency in the minimum amount of time, all within the constraints of the processing power and bandwidth available within the network. Our interest is in supporting emergency response for indoors incidents. At present, there are only two choices about where computation might occur within a sensor network: (i) on individual sensor nodes, with the advantage of achieving substantial data reduction, decreasing the cost of transmission, and avoiding congestion; (ii) outside the sensor network, with the sensors simply supplying sinks or more powerful nodes with the data needed for the calculation. The latter approach does not require powerful nodes but necessitates a higher bandwidth network. If applications reach a level of sophistication at which they cannot be executed on a single node, then it would seem that the only option is to have processing performed centrally. The distributed systems community has proposed another solution to limited computing power on a single node: the distribution of complex applications within grids formed by high-end processors. However, since these devices are usually linked through high-speed connections, they do not experience bandwidth restrictions or congestion that are inevitable in any WSN due to the broadcast radio medium. So far, the existing approaches in this direction are hybrid, because they use clusters of nodes that rely on more powerful clusterheads to execute their computation. They tend to focus exclusively on the load availability of nodes during the distribution process, ignoring real communication issues because of the simulated environments in which they are mainly tested. The key contribution of our work is the introduction of a novel approach, which relies on distributing computation among a homogeneous grid of nodes, in an effort to port the Grid Computing paradigm within the WSNs. Moreover, we demonstrate by practical experimentation that there are significant benefits to be gained by considering local network conditions in addition to load information during distribution. We present results from our implementation of two different algorithms on real Tmote Sky sensor testbeds running the Contiki OS [3]. The first is a novel algorithm while the second is an adaptation of an already existing distribution algorithm [2], both modified to take into account real bandwidth requirements.