Connectivity and aggregation in multihop wireless networks

Abstract

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.