# Energy Aware and Quality of Service Routing Mechanism for Hybrid Internet of Things Network
## 4 Problem Formulation and Optimum Solution  
In this paper, we study how to reduce the energy consumption in the mesh-connected visual sensor nodes in the hybrid IoT network without compromising performance. We do not focus on reducing energy consumption on each visual sensor node but rather on the global energy consumption of the network. This is done by concentrating flows to a few visual sensor nodes as much as possible while guaranteeing bandwidth and at the same time not allowing each of the set of flows to take a path length longer than a maximum desired value so as to guarantee the delay as well. This allows as many visual sensor nodes as possible that are not used and involved in the video surveillance to be selectively turned off. Therefore, the objective of this paper was to design an optimal routing mechanism that could minimize the number of active visual sensor nodes involved in routing a set of flows \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Reference** & \
\begin{tabular}{c} **Global Energy** \\ **Consumption Reduction** \\ \end{tabular} & **Increase Life Time** &
\begin{tabular}{c} **Interference** \\ **Considerations** \\ \end{tabular} & **QoS Guarantees** \\ \hline [PERSON] et al. [16] & Not considered & Yes & No & Not specified \\ [PERSON] et al. [15] & Not considered & Yes & No & Limited delay, Packet loss ratio \\ [PERSON] et al. [17] & Not considered & Yes & No & Not specified \\ [PERSON] et al. [18] & Not considered & Yes & No & Not specified \\ [PERSON] et al. [11] & Yes & Not considered & Yes & Throughput \\ [PERSON] et al. [20] & Yes & Not considered & Yes & Throughput \\ The proposal & Yes & Not considered & Yes & Throughput, Limited delay \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Related work overview and our proposal. to gateways, while complying with QoS constraints in terms of bandwidth and delay (in terms of path length). We formulated the problem as an integer linear program (ILP) [24]. The objective was to find the minimum number of visual sensor nodes needed (activated) under QoS constraints in terms of bandwidth and delay. To describe the model, we introduce the notation for the parameters and variables as follows. \(E\): the set of links  
\(V\): the set of visual sensor nodes  
\(C_{l}\): the set of cliques  
\(K\): the set of flows in the network  
\(d_{i,j}\): the capacity reserved on link \((i,j)\)  
\(C_{i,j}\): the total capacity available on link \((i,j)\)  
\((S_{k},G_{k})\): the source and the gateway of flow \(k\)  
\(B_{k}\): the minimum capacity requested by flow \(k\)  
\(x_{i}\): equal to 1 if the node is used to route flow, 0 otherwise  
\(x_{i,j}^{k}\): equal to 1 if \((i,j)\) is used to route flow \(k\), 0 otherwise  
\(\mathsf{p}_{m}\): path lenth limit of each of the flows  
The objective function:  
\[\text{Min }\sum_{i\in V}x_{i} \tag{1}\]  
Subject to the following constraints:  
\[\sum_{(i,j)\in c_{l}}(d_{i,j}/C_{i,j})\leq 1,\;\forall c_{l}\;\epsilon\;C_{l} \tag{2}\]  
\[\sum_{(i,j)\in E}x_{i,j}^{k}-\sum_{(j,k)\in E}x_{j,k}^{k}=0,\;\forall k\; \epsilon\;K,\;\forall j\;\epsilon\;V-\{S_{k},G_{k}\} \tag{3}\]  
\[\sum_{(i,S_{k})\in E}x_{i,S_{k}}^{k}=0,\;\forall k\;\epsilon\;K \tag{4}\]  
\[\sum_{(S_{k},i)\in E}x_{S_{k},i}^{k}=1,\;\forall k\;\epsilon\;K \tag{5}\]  
\[\sum_{(G_{k},i)\in E}x_{G_{k},i}^{k}=0,\;\forall k\;\epsilon\;K \tag{6}\]  
\[\sum_{(i,G_{k})\in E}x_{i,G_{k}}^{k}=1,\;\forall k\;\epsilon\;K \tag{7}\]  
\[\sum_{(i,j)\in E}x_{i,j}^{k}\leq 1,\;\forall k\;\epsilon\;K,\;\forall i\; \epsilon\;V-\{G_{k}\} \tag{8}\]  
\[\sum_{k\in K}x_{i,j}^{k}\cdot B_{k}\;=d_{i,j},\;\forall(i,j)\;\epsilon\;E \tag{9}\]  
\[\text{Min }\sum_{i\in V}x_{i} \tag{1}\]0  
\[x_{i}=\left\{ \begin{array}{cc}1,&if\;\;d_{i,j}+d_{j,j}>0\\ 0,&\text{otherwise}\end{array} \right.\;\;\forall i\;\epsilon\;V, \tag{11}\]  
\[ \begin{array}{cc}x_{i}\in\{0,\;1\}\;,\;\forall i\in V\\ x_{i,j}^{k}\in\{0,1\},\;\forall(i,j)\in E,\forall k\in K\end{array}