# Service-Aware Clustering: An Energy-Efficient Model for the Internet-of-Things
## 2 The Energy-Efficient Internet-of-Things Model
### The Service-Aware Clustering Model
#### 2.3.1 The Service-Aware Clustering Problem  
Let us consider a wireless sensor network represented by a directed graph \(\mathcal{G}=(\mathcal{N},\mathcal{L}\),\(s\)), where \(\mathcal{N}\) is the set of sensor nodes, \(\mathcal{L}\) is the set of wireless links between nodes and \(s\) is unique and selected as the network base station. Assume that \(\mathcal{R}(\mathcal{G})=\{\mathcal{R}_{i}\}\) is the set of routing configurations associated with the network \(\mathcal{G}\) where each of the routing configurations \(\mathcal{R}_{i}\) is expressed by the tuple \(\mathcal{R}_{i}=(\mathcal{N}_{c},\mathcal{N}_{n},\mathcal{L}_{c},\mathcal{L}_{ n})\) where \(\mathcal{N}_{c}\) and \(\mathcal{N}_{n}\) are the set of cluster heads, including the base station \(s\) and normal nodes, respectively, while \(\mathcal{L}_{c}\) is the set of links connecting the cluster heads that form a backbone for the sensor readings to the base station and \(\mathcal{L}_{n}\) is the set of links connecting the cluster heads to cluster member nodes. Assume a service-aware model, where each node \(x\) is allocated a service delivery level \(S(x)\). The SAC problem consists of finding an efficient routing configuration \(\mathcal{R}_{ef}\in\mathcal{R}(\mathcal{G})\), such that:\[\hat{\tau}_{egy}(\mathcal{R}_{ef}) =\max_{\mathcal{R}_{i}\in\mathcal{R}(\mathcal{G})}\hat{\tau}_{egy}( \mathcal{R}_{i}) \tag{6}\] \[subject\quad to\] \[P_{r}(x\in\mathcal{N}_{c}) \geq P_{r}(y\in\mathcal{N}_{c})\text{ if }\tau_{egy}(y)<avgE\leq\tau_{egy}(x)\] (6a) \[P_{r}(x\in\mathcal{N}_{c}) \geq P_{r}(y\in\mathcal{N}_{c})\text{ if }S(x)\leq S(y)\text{ } \forall\ x,y\in\mathcal{N}\] (6b) \[P_{r}(x\in\mathcal{N}_{n}) \geq P_{r}(y\in\mathcal{N}_{n})\text{ if }S(x)\geq S(y)\text{ } \forall\ x,y\in\mathcal{N}\] (6c) \[j\in N[x] \text{ if }\mathcal{D}_{is}(j,x)<\mathcal{D}_{is}(i,x)\text{ } \forall\ i,j,x\in\mathcal{N}_{c}\] (6d) \[j\in N[x] \text{ if }\mathcal{D}_{is}(j,x)<\mathcal{C}_{ov}\text{ } \forall\ i,j,x\in\mathcal{N} \tag{6e}\]  
where \(N[x]\) is the set of neighbors of node \(x\) and \(\mathcal{D}_{is}(j,x)\) is the Euclidean distance between nodes \(j\) and \(x\); \(\hat{\tau}_{egy}(\mathcal{R}_{ef})\) represents the residual energy of a routing configuration, while \(\tau_{egy}(x)\) expresses the residual energy of a single node \(x\); and \(\mathcal{N}=\mathcal{N}_{c}\cup\mathcal{N}_{n}\). The average residual energy \(avgE\) of all of the nodes of a network \(\mathcal{N}\) is expressed by \(avgE=\frac{\sum_{g\in\mathcal{N}}\tau_{egy}(y)}{|\mathcal{N}|}\). Note that, as formulated above, the SAC problem expresses:  
* Energy-frugal routing expressed by the routing objective Equation (6), where the most energy-efficient routing configuration is the one with the maximum residual energy. * Energy-aware clustering expressed by the constraint Equation (6a) used in the energy-aware pre-selection phase of the cluster head pre-election process described in Section 2.4. This constraint is used to assign cluster head roles to the nodes depending on the average sensor network residual energy. * Service-aware clustering expressed by the constraint Equation (6b,c) used in the service-aware pre-selection phase of the cluster head pre-election process described in Section 2.4. These constraints are used to assign cluster head or cluster member/slave roles to the nodes depending on their service level. * Neighbor selection on the multi-hop backbone network of cluster heads as expressed by the distance minimization constraint in the Equation (6d) and the neighbor selection and association constraint based on the wireless communication range in Equation (6e).