Yunan Gu

Document Type


Date of Award



College of Science, Engineering, and Technology (COSET)

Degree Name

MS in Computer Science

First Advisor

Miao Pan


Recent years have witnessed the advent of wireless sensor technologies and proliferating applications of wireless sensor networks (WSNs) in various fields. Network lifetime has been a critical design goal of any battery operated large scale WSNs. Especially for delay-sensitive WSNs, it is challenging to prolong the network lifetime, while meeting the delay requirements of different applications. In this thesis, we fisrt investigate how to prolong the lifetime of large scale WSNs via optimal placement of base stations (BSs). With multiple BSs placed, the sensor nodes can send their data to nearby sinks and may reduce energy consumption ofrelaying packets for other sensor nodes. Due to the high cost of BSs and geographical constraints in WSNs, we can only place a limited number of BSs in a few candidate locations. Considering wireless transmission features and flow routing, we formulate this base station placement (BSP) problem in WSNs into a mixed integer nonlinear programming (MINLP) problem. In view of the NP-hardness of the formulated problem, we develop the heuristic algorithm to pursue feasible solutions. Through extensive 1 2 simulations, we show that the solutions found by the proposed algorithm are close to the optimal one and the proposed scheme is effective in prolonging the lifetime of large scale WSNs. In addition, we investigate how to optimize the network lifetime of delay-sensitive WSNs with respect to energy efficient routing and sleep scheduling. Instead oftreating routing and sleep scheduling as two separate approaches, we have ajoint consideration of them, and mathematically formulate the lifetime maximization problem under multiple constraints (i.e., routing, end-to-end delay bounds, sleep scheduling, energy consumption of transmission, receiving and listening, etc.). Since the formulated problem is a MINLP problem and NP-hard to solve, we relax it into a LP problem and solve the relaxed problem for the upper bound. We also develop a heuristic algorithm for the feasible solution, which yields a lower bound of WSNs' lifetime. Through extensive simulations, we show that the solution found by the proposed algorithm is close to the optimal one and the proposed scheme is effective in prolonging the lifetime of delay-sensitive WSNs