Multi-Objective Topology Control in Wireless Networks

Topology control is the task of establishing an efficient underlying graph for ad-hoc networks over which high level routing protocols are implemented. The following design goals are of fundamental importance for wireless topologies: (1) low level of interference; (2) minimum energy consumption; (3) high spatial reuse; (4) connectivity; (5) planarity; (6) sparseness; (7) symmetry; (8) small nodal degree; (9) communication-efficient and localized construction. Previous topology control algorithms have usually been designed to provide good performance guarantees in the worst case. Yet, since design goals often conflict, it is usually impossible to construct a single structure that concurrently addresses a large number of goals efficiently. On the other hand, in this paper we show that a substantially larger number of design goals can concurrently be addressed when "pathological" worst case scenarios are ignored. Accordingly, we focus on average performance and establish a protocol that satisfies all the above design goals. Specifically, we formally prove the efficiency of our protocol with respect to all design goals except for high spatial reuse and small nodal degree, for which this is demonstrated by way of simulations. We note that minimum energy consumption and low level of interference have been the main targets of topology control, and our protocol is proven to offer salient performance guarantees with respect to both.