Optimization in wireless networks: Lifetime, relay, and broadcast schedules

In this dissertation, four optimization problems in wireless networks are explored. The first two are to compute a schedule to maximize the sensor network lifetime which is measured by total time during which the network performs its monitoring duties without recharging batteries.;First, considering the wireless sensor networks where sensors are assumed to be on all the time, the previously proposed exact polynomial-time algorithm has O(n15logn) running time. We demonstrate an alternative approach giving a solution at least 1 -- epsilon times the optimum lifetime, with running time O(n3 1e 7 log1+epsilon n), for any epsilon > 0. Second, assuming a sensor network model in which sensors can interchange idle and active statuses both for monitoring and communicating, we propose centralized approximation algorithms for lifetime maximization. Also, a distributed Deterministic Energy-Efficient Protocol for Sensing (DEEPS) to prolong lifetime is proposed. The experimental results reveal an increase in the lifetime for DEEPS over known protocols.;Third, we study the problem of Relay Nodes in Wireless Sensor Networks. Given a set S of wireless sensor nodes as a set of points in the two-dimensional plane, we must place a minimum-size set Q of relay nodes to connect S. The nodes of S can communicate to nodes within distance r and the relay nodes of Q can communicate within distance R. We improve the analysis of the 7-approximation algorithm based on Minimum Spanning Tree (MST) to 6 and propose a post-processing heuristic to improve the performance of the approximation algorithms.;Fourth, we study the Interference-Aware Broadcast Scheduling problem, where all nodes in the Euclidean plane have a transmission range and an interference range equal to r and stir for alphar ≥ 1, respectively. Minimizing latency is known to be NP-hard even when alpha = 1. We present integer programs for the problem and compare the optimum solution to that obtained from our newly proposed heuristics. The experiments reveal that our best heuristics give the solutions 13-20% exceeding the optimums. We additionally demonstrate that an O (alphaD) schedule exists and therefore O (alpha) approximation algorithm is attained.