# Energy and Environment-Aware Path Planning in Wireless Sensor Networks with Mobile Sink
## 4 Formulation for Optimal Solution
### Optimal Routing Problem
The relaying latency for each candidate node is determined by Equation (58):  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]  
For every cluster head \(x\), the cluster heads in its candidate neighbor set \(CCHN_{x}\) that have relaying delays less than the desired delay are added to the final candidate neighbor set \(FCHN_{x}\); formally, as in Equation (59):  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]  
As can be seen in Equations (60) and (61), the overall end-to-end delay and packet loss ratio of the routing paths from all cluster heads that have urgent messages \(CHU^{t}\) to the mobile sink \(MS\) in a graph \(G\) are defined as the summation of all edge contributions along the routing path:  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]  
\[Total\ end-to-end\ delay\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}D_{xy}. \tag{61}\]  
Based on these calculations, the problem is formulated as follows:  
\[Z_{IP_{1}}=\textbf{min}\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{62}\]  
\[Z_{IP_{2}}=\textbf{min}\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}D_{xy} \tag{63}\]  
subject to:  
\[\sum_{y\in CCHN_{x}}c_{y}Rd_{y}<Dd_{x}\ \ x,CCHN_{x}\in FCH^{t},FCH^{t}\in CH^{t}, CH^{t}\in V \tag{64}\]  
\[\sum_{y\in CCHN_{x}}c_{y}\geq 1\ \ \ x,CCHN_{x}\in FCH^{t},FCH^{t}\in CH^{t}, CH^{t}\in V \tag{65}\]\[\sum_{y\in FCHN_{x}}o_{y}\left(\sum_{p\in P_{y}^{t}}\alpha_{y}^{p}\right)>0\ \ FCHN_{x}\in FCH^{t}\in CH^{t},CH^{t}\in V,t\in T \tag{66}\]  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]0  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]1  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]2  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]3  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]4  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]5  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]6  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]7  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]8  
\[Rd_{y}(t)=delay_{xy}. \tag{58}\]9  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]0  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]1  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]2  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]3  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]4  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]5  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]6  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]7  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]8  
\[FCHN_{x}=\left\{y\middle|y\in CCHN_{x},Rd_{y}\,<Dd_{x}\right\}. \tag{59}\]9  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]0  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]1  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]2  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]3  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]4  
\[Total\ packet\ loss\ ratio\ (G,FCH^{t})=\sum_{t\in T}\sum_{s\in CHU^{t}}\sum_{u\in UIM^{t}_{x}} \sum_{x,y\in FCH^{t}}d^{su}_{xy}PLR_{xy} \tag{60}\]5Constraints in (64) and (65) are utilized to ensure that the forwarding candidate set \(FCHN_{x}\) contains only the cluster heads that have a relay delay less than the desired delay; it often has less members than \(CCHN_{x}\).