Coverage, sink location and routing problems in wireless sensor networks

Abstract

Recent advances in electronics and telecommunications have enabled the development of low-cost, low-power multifunctional sensor devices that are powered by batteries and communicating through wireless channels over small distances. When a large number of these devices work collaboratively for certain purposes, they form a network which is called a wireless sensor network (WSN). Due to their benefits and inherent characteristics, WSNs give rise to a broad-range of many real-life applications. There are various design issues in the construction of WSNs. In this study, we focus on three important classes of problems, which are Point Coverage, Sink Location and Data Routing Problems. We propose a Binary Integer Programming (BIP) formulation to model the coverage problem and develop various heuristics to solve it. Both the Routing Problem (RP), which involves finding the most energy efficient sensor-tosink routes and Sink Location Problem (SLP), which is determining the optimal sink locations are important design issues to extend the lifetime of a WSN. However, the joint optimization of these two problems results in a more efficient network design, so we develop several Mixed Integer Linear Programming (MILP) formulations and propose optimum solution techniques and heuristics to solve them. Finally, we solve the complete integrated model, which consists of the coverage, sink location and data routing problems simultaneously. We call this hard problem as the Coverage, Location and Routing Problem (CLRP) and develop new mathematical programming formulations. We propose a nested solution procedure, where in the first level of this approach, good sensor locations are sought by using some metaheuristics. In the second level, we solve the remaining sink location and routing problem using efficient heuristics.