We show that the first phase of the Linial-Saks network decomposition algorithm gives a randomized distributed O(nε)-approximation algorithm for the maximum independent set problem that operates in O(1/ε) rounds, and we give a matching lower bound that holds even for bipartite graphs.

Efficient spectrum use in wireless sensor networks through spatial reuse requires effective models of packet reception at the physical layer in the presence of interference. Despite recent progress in analytic and simulations research into worst-case behavior from interference effects, these efforts generally assume geometric path loss and isotropic transmission, assumptions which have not been borne out in experiments.

Signal-strength models of wireless communications capture the gradual fading of signals and the additivity of interference. As such, they are closer to reality than other models. However, nearly all theoretic work in the SINR model depends on the assumption of smooth geometric decay, one that is true in free space but is far off in actual environments. The challenge is to model realistic environments, including walls, obstacles, reflections and anisotropic antennas, without making the models algorithmically impractical or analytically intractable.

We present randomized distributed algorithms for connectivity and aggregation in multi-hop wireless networks under the SINR model. The connectivity problem asks for a set of links that strongly connect a given set of wireless nodes, along with an efficient schedule. Aggregation asks for a spanning in-arborescence (converge-cast tree), along with a schedule that additionally obeys the partial order defined by the tree. Here we treat the multi-hop case, where nodes have limited power that restricts the links they can potentially form. We show that connectivity is possible for any set of n nodes in O(\log n) slots, which matches the best centralized bound known, and that aggregation is possible in O(D + log n) time (D being the maximum hop-distance), which is optimal.