Date Added: Aug 2012
In this paper, the problem is how to obtain a path with minimum distance cost and effectively organize the network to ensure the availability of this path. The authors present a distributed algorithm to construct a path planning infrastructure by uniting the neighbors' information of each sensor node into an improved connected dominating set. Then, a path planning algorithm is proposed which could produce a path with its length at most c times the shortest Euclidean length from initial position to destination. They prove that the distributed algorithm has low time and message complexity and c is no more than a constant. The results show that factor c is within the upper bound proved in this paper and their distributed algorithm achieves a smaller infrastructure size.