Using adaptive range control to optimize 1-hop broadcast coverage in dense wireless networks.
Xiaoyan Li, Thu Duc Nguyen, Richard P. Martin · 2003
We present a simple distributed algorithm for maximizing 1 hop broadcast coverage in dense ad-hoc wireless networks, which is important because broad classes of routing, localization, and discovery protocols rely on periodic broadcasts. Our strategy for maximizing coverage is based on spatial reuse, where each node sets its radio range to maximize coverage using only locally observed packet arrival rate and device density. We derive and use a geometric-based, probabilistic model, which describes the expected coverage as a function of range, arrival rate and density. Because we can only numerically solve the resulting model, we develop a set of extrapolations which derive the optimum range for any rate and density given a single precomputed optimum. We then present a distributed range setting algorithm based on these extrapolations. Our algorithm is critically dependent on the empirical determination of the surrounding density but does not require any extra message exchanges. Rather, we show that the problem of incomplete density observations can be addressed by expanding the transmission range for just 2 % of the broadcasts. We show using simulation that our algorithm converges in under 15 broadcast adjustment rounds and provides ranges accurate to within 20 % of optimal across a wide variety of rates and densities for uniform networks. Using measured position data from our laboratory, we also show that our algorithm quickly converges and provides good coverage for highly non-uniform networks. Finally, we demonstrate the utility of our algorithm for a higher layer protocol by showing how it significantly improves the accuracy of a distributed localization protocol, particularly in the case where nodes are distributed non-uniformly. 1