Exact and Heuristic Algorithms for Data-Gathering Cluster-Based Wireless Sensor Network Design Problem

Data-gathering wireless sensor networks (WSNs) are operated unattended over long time horizons to collect data in several applications such as those in climate monitoring and a variety of ecological studies. Typically, sensors have limited energy (e.g., an on-board battery) and are subject to the elements in the terrain. In-network operations, which largely involve periodically changing network flow decisions to prolong the network lifetime, are managed remotely, and the collected data are retrieved by a user via internet. In this paper, we study an integrated topology control and routing problem in cluster-based WSNs. To prolong network lifetime via efficient use of the limited energy at the sensors, we adopt a hierarchical network structure with multiple sinks at which the data collected by the sensors are gathered through the clusterheads (CHs). We consider a mixed-integer linear programming (MILP) model to optimally determine the sink and CH locations as well as the data flow in the network. Our model effectively utilizes both the position and the energy-level aspects of the sensors while selecting the CHs and avoids the highest-energy sensors or the sensors that are well-positioned sensors with respect to sinks being selected as CHs repeatedly in successive periods. For the solution of the MILP model, we develop an effective Benders decomposition (BD) approach that incorporates an upper bound heuristic algorithm, strengthened cuts, and an ε-optimal framework for accelerated convergence. Computational evidence demonstrates the efficiency of the BD approach and the heuristic in terms of solution quality and time.