Robust design of wireless networks

Abstract

We consider the problem of robust topology control, routing and power control in wireless networks. We consider two aspects of robustness: topology control for robustness against device and link failures; routing and power control for robustness against traffic variations. The first problem is more specific to wireless sensor networks. Sensors typically use wireless transmitters to communicate with each other. However, sensors may be located in a way that they cannot even form a connected network (e.g, due to failures of some sensors, or loss of battery power). Using power control to induce a connected topology may not be feasible as the sensors may be placed in clusters far apart. We consider the problem of adding the smallest number of relay nodes so that the induced communication graph is k-connected. We consider both edge and vertex connectivity. The problem is NP-hard. We develop approximation algorithms that find close to optimal solutions. We consider extension to higher dimensions, and provide approximation guarantees for the algorithms. In addition, our methods extend with the same approximation guarantees to a generalization when the locations of relays are required to avoid certain polygonal obstacles. We also consider extension to networks with non-uniform transmission range, and provide approximation algorithms. The second problem we consider is of joint routing and transmission power assignment in multi-hop wireless networks with unknown traffic. We assume the traffic matrix, which specifies the traffic load between every source-destination pair in the network, is unknown, but always lies inside a polytope. Our goal is to find a fixed routing and power assignment that minimizes the maximum total transmission power in the network over all traffic matrices in a given polytope. In our approach, we do not need to monitor and update paths to adapt to traffic variations. We formulate this problem as a non-convex semi-infinite programming problem. We propose an efficient algorithm that computes a routing and power assignment that is schedulable for all traffic matrices in the given polytope. We perform extensive simulations to show that the proposed algorithm performs close to algorithms that adaptively optimize their solution to the traffic variations.