ABSTRACT

CONTENTS 8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178 8.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

8.2.1 Target Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.2.2 Other Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 8.2.3 Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

8.3 Network Model and Related Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 8.3.1 Network Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 8.3.2 Related Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 8.3.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

8.4 Our Proposed Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 8.4.1 α-RMSC Heuristic Algorithm Overview . . . . . . . . . . . . . . . . . . . 187 8.4.2 Contribution Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 8.4.3 Relation between MSC and α-RMSC . . . . . . . . . . . . . . . . . . . . . . 189

8.5 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 8.5.1 Simulation 1: Control Failure Probability . . . . . . . . . . . . . . . . . . . 189 8.5.2 Simulation 2: Comparison between α-RMSC and MSC . . . . . 191

8.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

Wireless sensor networks (WSNs) consist of a large number of ad hoc networked, low-power, short-lived and unreliable micro-sensors, which are limited in computation, memory capacity and radio range [120]. Many sensors are deployed in regions of interest to collect related information or report that some event has taken place in that area. Therefore, WSNs are widely applied to battlefield surveillance, health care applications, environment and habitat monitoring, home appliance, smart space, and inventory tracking [52]. A basic and important function of WSNs is to monitor areas or targets for a long period. Since sensors are often deployed in remote or inaccessible environments where replenishing energy is usually impossible, a critical issue in WSN applications is conserving sensors’ energy and prolonging the network lifetime while guaranteeing the coverage of desired areas or targets, which is called the coverage problem.