A Near Optimal Periodic Transmission Schedule in Bounded Degree Wireless Sensor Network

Co-operative computations in a network of sensor nodes rely on an established, interference free and repetitive communication between adjacent sensors. This paper analyzes a simple randomized and distributed protocol to establish a periodic communication schedule S where each sensor broadcasts once to communicate to all of its neighbors during each period of S. The result obtained holds for any bounded degree network. The existence of such a randomized protocol for a basic interference model is not new but it fails for a generalized interference model considered in this paper. In addition, for a network with n sensor nodes, our protocol reduces the number of random bits and the number of transmissions per sensor from Θ(log² n) to O(logn). These reductions conserve power which is a critical resource. Both protocols assume upper bound on the number of nodes n and the maximum number of neighbors \({\mathcal{B}}\). For a small multiplicative (i.e., a factor ω(1)) increase in the resources, our algorithm can operate without an upper bound on \({\mathcal{B}}\).

There is a major advantage in establishing a periodic schedule. Any traditional distributed protocol on regular (non-wireless) network can be applied in conjunction with a periodic schedule to derive an interference free protocol for a wireless network. The penalty is proportional to the length of the period of the periodic schedule.