| The limited energy supply and constrained capacities of individual devices raise many technical challenges in the efforts to implement an effective and efficient Wireless Sensor Network (WSN). In this thesis, we conduct an in-depth study on one of the fundamental design issues, namely network planning, in which types, numbers, and locations of heterogeneous devices are determined so that the total system cost is minimized while the requirements of lifetime, coverage, and connectivity are satisfied. To tackle this intricate problem, we propose a comprehensive and modular network planning framework, which is decomposed into a sensing domain and a communication domain.; In the sensing domain, we introduce the novel concept of information-oriented coverage, which measures the sensing quality by the information utility obtained from the sensing devices. We propose a couple of heuristic schemes to deploy a minimum number of sensing devices to achieve a desirable sensing quality.; The communication domain, formed by relaying devices, must ensure accurate delivery of all sensed information to the base station over a desirable lifespan. Due to the complexity of the general relaying device placement problem, we split the design of the communication domain into two phases.; In the first phase, we use a minimum set covering model to characterize the problem of placing a minimum number of relaying devices to ensure connectivity and lifetime requirements of each sensing device, and propose a recursive algorithm to obtain the optimal solution.; In the second phase, we propose Far-Near and Max-Min principles to make locally optimal decisions to place a minimum number of extra relaying devices, such that all data collected at the first phase relaying devices can be forwarded to the BS for a given duration. We envision two scenarios---either a relaying device has fixed or variable transmission range. Several schemes are proposed for the placement of the relaying devices in each scenario. Furthermore, a lower bound on the minimum number of second phase relaying devices is derived for each case above. Extensive simulations over different scenarios verify the effectiveness of our proposed schemes.; The network planning problems introduced in this work have not been considered previously and their formulations are novel. The devised techniques can serve as guidelines for WSN designers, solution providers, and system integrators of WSN applications. |
