Efficient solution techniques for the integrated coverage, sink location and routing problem in wireless sensor networks
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.
Section snippets
Problem definition and mathematical programming formulations
The objective of the CSLRP is to design a WSN such that the total available battery energy of the sensors in the WSN is spent in the most efficient way for transmitting (routing) data packets from sensors to sinks. This also helps to prolong the lifetime of the WSN as much as possible. Before we present the mathematical programming formulations for the CSLRP, we describe the problem while defining the decision variables common for both formulations.
The CSLRP is defined in a two-dimensional
A hybrid solution procedure
CSLRP is computationally very difficult and solving any of the proposed formulations by a general-purpose MILP solver usually generates an optimal solution only for small instances. For medium and large instances there is a need for efficient heuristic methods. In this paper, we propose a hybrid solution procedure for the solution of the CSLRP which utilizes the CSLRP-2 formulation. The outer loop of this procedure uses tabu search to identify the best sensor locations satisfying the coverage
Computational experiments
In this section, we report the accuracy and efficiency of the TS-LH, TS-NDH, and TS-GH heuristics. As the basis of our comparisons, we take the objective value of the best feasible solution provided by CPLEX 11.2 when solving the CSLRP-1 within the allowed time limit of 4 h (14,400 s). By letting to denote the best objective value CPLEX computes for an instance and representing the best objective value obtained by the proposed methods for the same instance, we can measure the
Conclusion
In this work, we study the joint optimization of point coverage, sink location, and data routing problems in wireless sensor networks. Two new MILP formulations are developed for the integrated model. The first one involves data routing variables defined on the arcs of the network, while the second one uses data routing variables based on sensor-to-sink assignments. Since the solution of these formulations by means of commercial MILP solvers is inefficient for medium and large-sized problems,
Acknowledgments
This research has been supported by TÜBİTAK (The Scientific and Technological Research Council of Turkey) under Grant no. 107M250 and by Boğaziçi University Research Fund under Grant no. 05HA303.
References (27)
- et al.
A survey on wireless multimedia sensor networks
Computer Networks
(2007) - et al.
Binary integer programming formulations and heuristics for differentiated coverage in heterogeneous sensor networks
Computer Networks
(2008) - et al.
Coverage and connectivity issues in wireless sensor networks: a survey
Pervasive and Mobile Computing
(2008) - et al.
Efficient integer programming formulations for optimum sink location and routing in heterogeneous wireless sensor networks
Computer Networks
(2010) - et al.
Energy-aware routing in sensor networks: a large system approach
Ad Hoc Networks
(2007) - et al.
‘Multidimensional’ extensions and a nested dual approach for the m-median problem
European Journal of Operational Research
(1985) - et al.
Wireless sensor network survey
International Journal of Computer and Telecommunications Networking
(2008) - et al.
Strategies and techniques for node placement in wireless sensor networks: a survey
Ad Hoc Networks
(2008) - et al.
Power-aware base station positioning for sensor networks
- et al.
Multi-sensor fusion: fundamentals and applications with software
(1998)
Wireless sensor networks: architectures and protocols
Handbook of sensor networks, coverage in wireless sensor networks
Energy-efficient target coverage in wireless sensor networks
Cited by (36)
Efficient configuration of heterogeneous multistatic sonar networks: A mixed-integer linear programming approach
2024, Computers and Operations ResearchNetwork sensor location problem with monitored lanes: Branch-and-cut and clustering search solution techniques
2020, Computers and Industrial EngineeringMaximizing the lifetime in wireless sensor networks with multiple mobile sinks having nonzero travel times
2020, Computers and Industrial EngineeringFuzzy single-commodity model in wireless sensor networks
2019, Procedia Computer ScienceFuzzy approach for locating sensors in industrial internet of things
2019, Procedia Computer Science