Coverage Optimization in Sensor and Cellular Networks

An important requirement for a wireless network is to guarantee coverage in any point inside the serviced area. In this thesis, we study several problems related to coverage that arise in the context of sensor and cellular networks.;Coverage assumes slightly different meanings depending on the context. For a sensor network, a point is covered if it is within the sensing range of some sensor. Sensors' deployment is often redundant, and the same location can be monitored by different sensors. Since sensors rely on limited battery power, the system's lifetime can be prolonged by keeping some sensor inactive, while the others perform all the tasks. In order to offer better robustness, we consider k-coverage, whereas each point is covered by at least k sensors. We first study the k-coverage problem with general/omnidirectional sensors and provide a logarithm-approximation algorithm based on an extension of the classical ϵ-net technique. Then, we consider directional sensors, which are sensors equipped with a "directional" sensing device (such as a camera) that senses a physical phenomenon in a certain direction depending on the chosen orientation. This poses an additional challenge because the k-coverage problem now requires to choose which sensors to activate as well as which direction to orient the active ones. We study coverage problems with both static directional sensors and continuously rotating ones. After proving that these problems are NP-hard to approximate, we provide double-approximation algorithms.;In addition to sensor network, we also study three types of problems with the common trend of guaranteeing full coverage while optimizing certain features. In this case, coverage means that a user in any location can successfully connect/transmit to a base station. We start by addressing the problem of minimizing the energy across a cellular network by deactivating certain cellular towers and optimizing the power assigned to the active ones. We present an algorithm with proven performance guarantees and demonstrate its effectiveness by performing extensive simulations using real data (tower locations and traffic traces) of a large service provider. We also consider a network of femtocells, which are short-range devices deployed to increase coverage and capacity in a small area. We provide an approximation algorithm for the problem of optimizing the overall capacity by assigning transmission power and channels to the femtocells. We also design an algorithm to maximize the minimum capacity. Finally, we study the problem of reducing peak consumption for Internet service providers, that applies to both cellular providers and land-line providers. We provide a game theoretical formulation, wherein the game is played by two entities: (i) the users each of whom has a data demand distribution over a day and (ii) a pricing authority who has the authority to set different data-usage pricing for different hours within a day. We design a dynamic pricing strategy for the pricing authority such that the users will spontaneously shift their demand to off-peak hours. We prove that this algorithm has fast convergence and support it with extensive simulations.