Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks

Abstract

Sensors are tiny electronic devices having limited battery energy and capability for sensing, data processing and communicating. They can collectively behave to provide an effective wireless network that monitors a region and transmits the collected information to gateway nodes called sinks. Most of the applications require the operation of the network for long periods of times, which makes the efficient management of the available energy resources an important concern. There are three major issues in the design of sensor networks: sensor deployment or the coverage of the sensing area, sink location, and data routing. In this work, we consider these three design problems within a unified framework and develop two mixed-integer linear programming formulations. They are difficult to solve exactly. However, it is possible to compute good feasible solutions of the sink location and routing problems easily, when the sensors are deployed and their locations in the sensor field become known. Therefore, we propose a tabu search heuristic that tries to identify the best sensor locations satisfying the coverage requirements. The objective value corresponding to each set of sensor locations is calculated by solving the sink location and routing problem. Computational tests carried out on randomly generated test instances indicate that the proposed hybrid approach is both accurate and efficient.

Introduction

Advances in micro-electromechanical systems, digital electronics and wireless communications have enabled the development of low-cost, low-power multi-functional tiny devices called sensors. They use battery power as the energy source and can communicate through wireless channels over relatively small distances. Each sensor is usually equipped with one or more sensing units, one or more transceivers, actuators, processors and storage units. As a result of significant resource limitations such as limited memory, battery power, signal processing, computation and communication capability, an individual sensor can only sense a small portion of its environment. However, when a large number of these devices work in a collaborative fashion to carry out a certain task, they form a wireless sensor network (WSN). WSNs give rise to a wide range of real-life applications in areas such as military, homeland security, health care, environment, agriculture, logistics, smart home or office design and other areas [26], [5].

WSNs can be homogeneous consisting of identical sensors, or heterogeneous consisting of sensors with possibly different technical characteristics and costs. Sensors that collectively form a WSN are deployed over an area of interest called the sensor field. The energy source provided for a sensor is usually the battery power which has not yet reached the stage to operate for a very long time without being recharged. Moreover, in a large number of applications sensors are intended to work in remote or hostile environments, and it is undesirable or impossible to recharge or replace their batteries. The lifetime of a WSN is measured by the time until it is disconnected; namely there exist holes that do not collect or transmit any information. In other words, the WSN cannot provide an acceptable level of operating quality beyond its lifetime. Therefore, conserving energy and prolonging the network lifetime is an important issue in the design of WSNs [27].

The transmission range of sensors is restricted as a consequence of their energy and size limitations, hence they cannot communicate through large distances. Therefore, each sensor needs to transmit its data to a central unit called “base station” or “sink”, which is a larger device with a comparatively large energy supply and long-range transmission capabilities such as internet or satellite communication.

There are various design issues in the construction of a WSN. One of the most important problems addressed in the literature is the sensor coverage problem (CP). This problem is centered around a fundamental question: “How well do the sensors observe the physical space?” As pointed out by Meguerdichian et al. [23], coverage can be regarded as a measure of the quality of service of the sensing function in WSNs. Therefore, the CP is studied thoroughly and there are many exact or approximate methods to solve it (e.g., [6], [14]). Also an interesting line of research has emerged, where the CP is modeled as a mixed-integer linear programming (MILP) formulation [7], [2].

In a typical WSN, each sensor collects and processes data, and tries to send this information to a sink. Since sensors' communication ranges are limited, the data packets carrying the sensed information usually have to follow multi-hop paths. The routing problem (RP), which involves finding the most energy efficient sensor-to-sink routes for a given set of sensor and sink locations, is an essential problem in WSNs because data transmission is an energy consuming task [1].

Determining the optimal sink locations is also an important design issue to extend the lifetime of a WSN. The average number of hops to reach a sink becomes a critical factor that is affected by the sink locations. In a significant number of research studies, the sink locations are assumed to be determined a priori [18], [20]. However, the energy consumption and thus the lifetime of the WSN can be improved by finding the best location(s) of the sink(s) since these locations have an impact upon the sensor-to-sink data transmission routes [3]. The joint optimization of sink locations and data routing is addressed in the sink location and routing problem (SLRP) that has received considerable attention in the literature as it results in a more efficient network design [13], [25], [17].

In this work, we jointly consider the coverage, sink location, and data routing problems in heterogeneous WSNs. We refer to this integrated problem as the coverage, sink location and routing problem (CSLRP), and develop two mathematical programming formulations by unifying these three design issues within a single model. Unfortunately, the resulting MILP formulations can only be solved for small-sized instances using commercial solvers. For medium and large-sized instances, we propose a hybrid solution procedure. In the outer loop, tabu search is employed to find near-optimal sensor locations satisfying the coverage requirements. In the inner loop, the remaining sink location and routing problems are solved using various methods for the sensor locations fixed in the outer loop. This integrated problem is also addressed in a very recent work [16]. However, the proposed benchmark model has a major flaw, which makes the results given in that work unreliable. The flaw stems from the fact that the data flow balance equations in the MILP formulation are erroneous.

The rest of the paper is organized as follows. In the next section, we introduce the CSLRP and its mathematical programming formulations. The hybrid solution approach is explained in Section 3, while experimental results are reported in Section 4. We conclude the paper in Section 5 with some remarks.