A State-Space Search Approach for Optimizing Reliability and Cost of Execution in Distributed Sensor Networks

Sensor networks are increasingly being used for applications which require fast processing of data, such as multimedia processing. Distributed computing can be used on a sensor network to reduce the completion time of a task and distribute the energy consumption equitably across all sensors. The distribution of task modules to sensors should consider not only the time and energy savings, but must also improve reliability of the entire task execution. We formulate the above as an optimization problem, and use the

A

*

algorithm with improvements to determine an optimal static allocation of modules among a set of sensors. We also suggest a faster but suboptimal algorithm, called the greedy

A

*

algorithm. Both algorithms have been simulated, and the results have been compared in terms of energy savings, decrease in completion time of the task, and the deviation of the sub-optimal solution from the optimal one. The sub-optimal solution required 8-35% less computation, at the cost of 2.5-15% deviation from the optimal solution in terms of average energy spent per sensor node. Both the

A

*

and greedy

A

*

algorithms have been shown to distribute energy consumption more uniformly across sensors than centralized execution. The greedy

A

*

algorithm is found to be scalable, as the number of evaluations in determining the allocation increases linearly with the number of sensors.