# SCMC: An Efficient Scheme for Minimizing Energy in WSNs Using a Set Cover Approach
## 1 Introduction  
The term \"Wireless Sensor Network\" (WSN) refers to a large number of spatially distributed autonomous nodes that organize themselves into a multi-hop wireless network for the monitoring and recording of physical or environmental conditions. Their applications include battlefield surveillance, target tracking, security, environmental control, habitat monitoring, source localization, fire detection, oil and gas pumping, and many more. A WSN system consists of distributed nodes and a gateway that provides wireless connectivity back to the wired world (see Figure 1). They can be organized into three types of network topology as shown in Figure 2.  
Figure 1: Wireless Sensor Network (WSN) Components, Gateway, and Distributed Nodes. A star network topology consists of a single base station and multiple remote nodes. The nodes cannot communicate directly with each other, while the base station can communicate with all of the nodes. In a mesh network topology, a node can directly communicate with any other node within its transmission range. This solves the single point of failure problem of star networks by allowing what is called multi-hop communication. In a cluster network topology, nodes are grouped to form a cluster with one of the nodes elected as a \"cluster head\" (CH). Cluster topologies when employed in WSNs generally result in lower energy consumption and an increased overall lifetime of the network. Because they are usually deployed in harsh environmental scenarios, WSN nodes rely solely on their batteries most of the time. As batteries have a finite capacity, minimizing energy consumption in order to extend the lifetime of sensor nodes without compromising their functionality is an important area of study in WSN research [1; 2; 3; 4; 5]. In WSNs, all nodes usually share common sensing tasks, each covering a different target area. This implies that not all sensors that are deployed within the same target area are required to perform their task continuously throughout the system's entire lifetime. Sensor nodes consume more energy when they are in transmission mode (active) than when they are in sleeping mode (inactive). If all sensor nodes within a coverage target area are active, the data collected will be redundant and a large amount of energy will be consumed and wasted. To save the overall energy of WSNs, our approach was to activate some sensor nodes while turning off others within each target area (set cover/cluster) without losing or disrupting system connectivity. Specifically, the proposed model aims to determine a minimum set cover within a WSN, and to elect a relay node (cluster head) that will forward sensor node messages to the base station. Moreover, the model addresses the problem of finding the minimum cost routes from sensor nodes to the base station through the elected cluster heads using a min-cost flow algorithm. To achieve the best solution for expanding a WSN's lifetime, we propose a modified version of the min-cost flow algorithm by taking residual energy as a constraint value to judge different paths and choose the best one among them, i.e., the one with the highest residual energy. While most of the approaches found in literature employ a Particle Swarm Optimization (PSO) algorithm to find clusters [6; 7; 8; 9; 10], in this paper we present a novel approach based on a set cover algorithm for finding clusters and a min-cost max-flow algorithm to find paths with minimum cost (energy consumption) and maximum residual energy. There are two main motivations for finding minimum set covers and using min-cost max-flow routing. The first is the need for an efficient energy scheme in WSNs, where sensor nodes tend to use small batteries for energy supply, and which are in many cases non-replenishable. Therefore an efficient activation management scheme is needed to conserve their energy, and thus that of the whole network. The second is the need for reliability in wireless networks.