| Coverage and connectivity are two key properties of wireless networks, particularly wireless sensor networks (WSNs). Deploying sensor nodes to simultaneously achieve coverage and connectivity requirements is a fundamental problem in WSNs. It is insufficient to consider coverage alone when deploying a wireless sensor network; connectivity must also be considered. While moderate loss of coverage can be tolerated by WSN applications, loss of connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not sufficient for a wireless sensor network to just be connected, it should be k-connected (for k > 1). In this dissertation, we propose optimal deployment patterns to achieve both full coverage and k-connectivity for k = 1, 2, 3, 4, 5, and 6, respectively, and prove their optimality for all values of rc/rs, where rc is the communication radius and rs is the sensing radius. By optimal deployment patterns, we mean those patterns that can achieve desired coverage and connectivity requirements with the fewest sensor nodes. Our results' fundamentality and generality facilitate their practical applications in, e.g., wireless mesh networks and 802.15.4 networks. We discover an interesting pattern mutation phenomenon in pattern evolution as rc/rs continuously changes. This phenomenon has both theoretical and practical implications. We also study several practical issues in wireless sensor network deployment in this dissertation. |
