Spanning Tree Backbone in Multihop Wireless Networks
Mukesh M. Hira, Fouad A. Tobagi · 2006
In this paper, we present an approach to routing critical data in multihop wireless networks over the most reliable links in the network. We present the concept of a Maximum SNR Spanning Tree (MSST) in multihop wireless networks, a Spanning tree with the maximum sum of Signal to Noise ratios of links that form the tree. We show that such a backbone has certain properties that would be of interest in multihop wireless network deployments where reliability of links over which data is routed is of critical concern. The minimum SNR along the path on the MSST between any pair of nodes is the highest among all paths between the pair of nodes. Also, the minimum value of SNR among the SNRs of links that form the MSST is the highest among all Spanning Trees of the network. SNRs of the links that form the Spanning Tree. We show that such a backbone has the highest value of minimum average SNR on the tree among all spanning trees, and the minimum average SNR along the path between any pair of nodes on the MSST is higher than that along any other path between the pair of nodes. We assume the average SNR of a wireless link to be the same in both directions as would typically be the case with identical receivers at both ends with equal transmit powers, since signals transmitted from both endpoints of the link would experience symmetrical path loss, shadowing and fading. Henceforth, we refer to SNR averaged over a certain period of time as simply the SNR. We assume fixed average SNR at each link to study the qualities of the MSST given a