# SCMC: An Efficient Scheme for Minimizing Energy in WSNs Using a Set Cover Approach
## 3 Approach
### Energy Optimization
#### 3.4.2 Routing Energy Optimization  
It is to note that in order to achieve the effective collection of data, WSNs must meet two requirements. One is full coverage of the targets, and the other is complete connectivity of the network. Full coverage means that the sensors should be able to monitor all targets, and complete connectivity means that the data that originated from the monitoring targets should be able to reach the base station through multi-hop wireless communication using a minimum energy path.  
We believe that relying only on a minimum energy routing strategy has some deficiency in terms of network lifetime. Since most of the time using a relay node is more energy-efficient than direct communication with the base station, sensor nodes closer to the base station exhaust their batteries long before other nodes residing on the perimeter of the network area. Hence, network lifetime cannot be optimized with minimum energy routing alone. As a solution, we propose to take into consideration the residual energy of the nodes in the path by assigning link costs inversely proportional to the residual energy values. This way, energy consumption could be balanced throughout the whole network. In fact, such a solution can achieve maximal network lifetime using a linear programming (LP) based model.  
Network Model  
After clustering, the routing procedure is invoked during data transmission using a min-cost max-flow algorithm [51].  
The Wireless Sensor Network used in this paper is modeled as a directed graph \(G\) (\(V,E\)), where \(V\) represents the set of sensor nodes and \(E\) the set of edges.  
Each edge (\(u,v\)) \(\in E\) is associated with a cost \(c\) (\(u\),\(v\)) which represents the energy consumption when there is a flow \(f_{ij}\) going out from \(u\) to \(v\), a capacity constraint \(u_{ij}\) expressed in the number of packets per unit time, and a supplies/demands variable \(d_{ij}\). The cost of a flow is: \(f\) (\(u\),\(v\)). \(c\) (\(u\),\(v\)).  
The objective is to deliver all the data generated by the sensor nodes to the base station with minimum energy consumption and without exceeding the link capacities.  
The problem can be formulated as follows:  
Minimizing the total cost of the flow over all edges:  
\[\sum_{(u,v)\in E}f(u,v).c(u,v) \tag{10}\]  
St:  
\[f(u,v)\leq c(u,v)\ \forall\ (u,v)\in E \tag{11}\]  
\[f(u,v)=-f(v,u) \tag{12}\]\[\sum_{w\in V}f(u,v)=0\;for\;all\;u\
eq s,t \tag{13}\] \[\sum_{w\in V}f(v,w)-\sum_{w\in V}f(w,v)=d \tag{14}\]  
where (11) represents the capacity constraint, (12) the skew symmetry, (13) the flow conservation, and (14) the required flow.  
The above problem can be converted into a minimum-cost circulation problem [52] and can be solved efficiently using well-known min-cost flow algorithms [53; 54; 55; 56]. In this research we adopt a network simplex method [57] as it is considered the most practical algorithm [57]. Figure 5 shows a sample of a sensor network where \(s_{1}\) is the source and \(s_{6}\) is the destination. The flow capacities and demands are shown on the graph.  
The corresponding network simplex LP is as follows, where \(x_{ij}\) = Number of units shipped from node \(i\) to \(j\) using arc \(i\)-\(j\):  
\[\text{Min}\;z=x_{13}+2x_{21}+2x_{24}+8x_{32}+4x_{35}+3x_{54}+x_{64}+2x_{65}\]  
\[\text{Node}\;s_{1}\text{:}\;x_{13}-x_{21}=1\]  
\[\text{Node}\;s_{2}\text{:}\;x_{21}+x_{24}-x_{32}=2\]  
\[\text{Node}\;s_{3}\text{:}\;-x_{13}+x_{32}+x_{35}=3\]  
\[\text{Node}\;s_{4}\text{:}\;-x_{24}-x_{54}-x_{64}=-7\]  
\[\text{Node}\;s_{5}\text{:}\;-x_{35}+x_{54}-x_{65}=-3\]  
\[\text{Node}\;s_{6}\text{:}\;x_{64}+x_{65}=4\]  
\[x_{13}\leq 2x_{21}\leq 2x_{24}\leq 5x_{32}\leq 5x_{35}\leq 4x_{54}\leq 3x_{64} \leq 1x_{65}\leq 6\]