Constant Approximation Algorithm for MST in Resource Constrained Wireless Sensor Networks

We consider lightweight wireless sensor networks constructed from low-profile and resource constrained wireless embedded systems. Each individual unit in these networks has limited computation, memory and power resources. Traditional models of computation and algorithms will no longer be suitable for such systems since each node in the network does not have the luxury of unbounded computations, storage and communication. In this paper a new model of computation has been introduced, in which computation of each processing unit is bounded by a value independent of the network size. Furthermore, based on this model, a fully distributed algorithm is presented to construct the minimum spanning tree with bounded degree in a network. As opposed to previous approximation results, in this algorithm the computation and message exchanging of each node is O(d) where d is the degree of the node and therefore is independent of network size. Moreover, our developed algorithm yields a constant approximation ratio in which the weight of the constructed spanning tree is O(weight(MST)). We evaluated out algorithm through simulation and observed that the approximation ratio is about 1.2 on average.