A Near Optimal Communication Algorithm for Distributed Computing over Heterogeneous Sensor Networks

In this paper, we propose a novel optimization algorithm for distributed computing for target-monitoring applications with heterogeneous wireless sensor networks. In many such monitoring applications, various types of sensor nodes are used and the potential communication pattern is known in advance. We then seek to find an optimal set of routing paths to realize the communication patten, such that the communication overhead of the data gathering process is minimized, and at the same time, the extent to which the other data traffic in the network is affected by the data traffic generated by the data gathering process is also minimized. However, we prove that this combinatorial optimization problem is NP-complete indicating that it is impossible to find an optimal solution in a reasonable time unless NP = P. So, instead of finding an optimal solution, we seek a sub-optimal polynomial time solution. The proposed novel solution is based on the randomized algorithm, which yields good solutions in the sense that the objective functions yield values close to the optimums with high probability ( 1-1/m, where m is number of links in the network). The proposed randomized algorithm makes use of linear programming and is easy to implement, which makes it a potential candidate for practical implementations, even for very large networks.