## 2 System Model and Problem Statement
### Power Consumption Model and Problem Formulation
\begin{split}&\sum_{q\in\mathcal{Q}:\mathcal{J}\to\rho_{q}}\phi_{y,f,q}r_{q} \leq N_{f,y}\pi_{f},\quad\forall\,f\in\mathcal{F},\;\forall\,y\in\mathcal{V} _{c},\\ &\sum_{f\in\mathcal{F}}N_{f,y}w_{f}\leq c_{y},\quad\forall\,y\in \mathcal{V}_{c},\\ &\sum_{f\in\mathcal{F}\setminus\mathcal{F}_{dum}}N_{f,y}\leq C_{ 1}\xi_{y},\quad\forall\,y\in\mathcal{V}_{c},\end{split}  \tag{12}\]  
ensures that the number of deployed VNF instances on a node is sufficient to meet the data processing requirements for the incoming traffic and does not exceed the amount of available CPU resources, while ensuring that the computational node is deployed only when needed. The link and BS capacity constraints are captured as follows:  
\[ \begin{split}&\sum_{q\in\mathcal{Q}}\sum_{e^{\prime}\in \mathcal{E}^{(\rho_{q})}}\theta_{e}^{e^{\prime},q}r_{q}\leq c_{e},\;\forall\,e \in\mathcal{E},\\ &\sum_{j\in\mathcal{S}^{(a)}}N_{a,j}^{(RB)}\leq\bar{N}_{a}^{(RB)},\;\forall\,a\in\mathcal{A}\end{split}  \tag{13}\]which restricts the total amount of traffic flowing through any link and the total number of Resource Blocks allocated by any BS, while  
\[ \begin{split}\sum_{v:(u,v)\in\mathcal{E}}\theta_{u,v}^{\ell^{\prime},\theta}-\sum_{w:(w,u)\in\mathcal{E}}\theta_{w,u}^{\ell^{\prime},\theta}=\phi_{ u,h(e^{\prime}),\mathcal{J}}-\phi_{u,t(e^{\prime}),\mathcal{J}},\\ \forall\,q\in\mathcal{Q},\;\forall\,e^{\prime}\in\mathcal{E}^{( \rho_{q})},\;\forall\,u\in\tilde{\mathcal{V}},\end{split}  \tag{14}\]  
is a flow conservation and routing condition, which ensures that the packets of each requested SFC meet the corresponding VNFs in the correct order as they are routed through the selected path. The above equation essentially ensures the \"proper\" embedding of the virtual graph \(\mathcal{G}^{(\rho_{q})}\), for each request \(q\in\mathcal{Q}\), into the physical graph (see Figure 2). Finally, E2E delay constraint is captured by  
\[\sum_{ \begin{subarray}{c}y\in\mathcal{V}_{e},\\ f\in R_{q_{j}}\end{subarray} }\phi_{y,f,q_{j}}\tau_{f}+\sum_{ \begin{subarray}{ c}e\in\mathcal{E},\\ \ell^{\prime}\in\mathcal{E}^{(\rho_{q})}\end{subarray} }\theta_{e}^{\ell^{ \prime},\mathcal{J}_{i}}\delta_{e}+\sum_{a\in\mathcal{A}^{(i)}}x_{j,a}\delta_{ (a,j)}\leq\delta_{q_{j}},\;\forall\,j\in\mathcal{J}. \tag{15}\]  
Hence, the total power expenditure in the network is  
\[P_{total}\triangleq\sum_{n\in\mathcal{S}_{uv}}P_{n}^{(suc)}+\sum_{y\in \mathcal{V}_{e}}P_{y}^{(CPU)}+\sum_{e\in\mathcal{E}_{ul}}P_{e}^{(mmW)}+\sum_{a \in\mathcal{A}}P_{a}^{(sNB/SC)} \tag{16}\]  
and we formulate our problem as the following NP-hard MILP  
\[ \begin{split}\text{minimize}&\quad P_{total},\\ \text{s.t.}&\quad\eqref{eq:P_total},\end{split}  \tag{17}\]  
where the control variables in (17) are \(N_{f,\
u}\), \(\xi_{y}\), \(z_{m,\mu}\), \(w_{m,n}\), \(\psi_{n},\theta_{e}^{e^{\prime},q}\), \(\chi_{e}\), \(\sigma_{e}\), \(\mu_{a}\), \(\
u_{a}\), \(\phi_{\tilde{y},f,q}\), \(x_{j,a}\), \(N_{a,j}^{(RB)}\) with index semantics as previously described. The MILP property of (17) follows from the simple observation (by visual inspection) that **all** of the above control variables appear as linear terms in the constraints (2), (3), (8)-(15) and as linear (in (1), (4), (6), (7)) or piecewise linear terms (in (5)) in the components of (16) comprising the objective function of (17), combined with the fact that the control variables take only integer or Boolean values. Note that a piecewise linear objective function can be readily converted into a purely linear form by introducing auxiliary variables (see Section 4.3.1 of [30]). Due to the high complexity of solving (17), we next propose a low-complexity heuristic algorithm and use (17) as a yardstick against which the heuristic's performance is evaluated. For the reader's convenience, we have collected all introduced notation into Table 1 at the end of the paper. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline