# Mobile Data-Mule Optimal Path Planning for Wireless Sensor Networks
## 3 Optimization Problem Formulation  
Let \(G=(V,E)\) be an edge-weighted graph with profits on its nodes. Profit assignment on nodes is used in the OP, where the goal is to determine a path, that visits some vertices and maximizes the sum of the collected profits. Thus, profits are used as a motivation for the MoEl to visit the static nodes. Given a node acting concurrently as starting node (source) and terminal (sink, or noted as depot), a positive time limit (budget) \(B\) and an inter-visit duration \(e_{j}\) for each node \(j\), the goal is to find sequential routes starting and ending at the depot node with maximum duration \(B\) while respecting the imposed inter-visit duration, such that the defined cost is maximized. Let \(N\) be the number of nodes labeled by \(1,\ldots,N\), where node '1' is selected as the source and sink node as well, with \(M\) MoEls. Assume that \(p_{j}\) is the profit of visiting node \(j\), \(v_{t_{j}}\) the visiting/service time at visiting node \(j\), and \(c_{ij}\) the cost (traveling time) of traveling from \(i\) to \(j\) node using constant speed. Furthermore, let \(P_{r}\) be the set of nodes that have to be visited/serviced by the MoEl in the extracted route, in order to avoid nodes' buffer overflow. Priority can also be given to a set of nodes that collect critical data. For every route, if node \(i\) is followed by node \(j\), the variable \(x_{ij}\) is set to 1; otherwise, it is set to 0. The MILP optimization problem [32] is:  
\[\max\sum_{m=1}^{M}\sum_{i=1}^{N}\sum_{j=1}^{N}(p_{j}-c_{ij}-v_{t_{j}})x_{ijm}\]  
The objective function consists of three parts: (a) the first refers to the profit that is collected by the \(M\) MoEls when they visit the static nodes. The profit that is assigned to the static nodes is not the same within a cycle of the \(m\) concurrent trajectories, which are to be followed by the \(M\) MoEls. Each static node's profit varies in correspondence with the priority that is assigned to this node. This priority is defined based mainly on the nodes' consecutive visit intervals that are imposed by the importance of the stored sensors' measurements and nodes' hardware constraints; (b and c) the second and third elements of the objective function penalize the exported trajectories. These respectively refer to the travel costs between the couple of vertices, and the visiting time to a vertex that is actually a delay for the MoEl during its trip. The constraints in the MILP problem are:  
**Equalities**  
\[\sum_{m=1}^{M}\sum_{j=2}^{N}x_{1 jm}=M, \tag{1}\]  
\[\sum_{m=1}^{M}\sum_{i=2}^{N}x_{i1m}=M. \tag{2}\]  
(1) and (2) ensure that each MoEl's path starts and ends at node 1 (depot). \[\sum_{m=1}^{M}\sum_{ \begin{subarray}{c}j=1\\ p\
eq j\end{subarray} }^{N}x_{pjm}=1,\quad\forall\text{ nodes }p\in P_{r}\subseteq N, \tag{3}\]  
\[\sum_{m=1}^{M}\sum_{ \begin{subarray}{c}i=1\\ i\
eq p\end{subarray} }^{N}x_{ipm}=1,\quad\forall\text{ nodes }p\in P_{r}\subseteq N. \tag{4}\]  
(3) and (4) ensure that nodes \(j\in P_{r}\) are included once in any of the extracted \(m\) routes. \[\sum_{ \begin{subarray}{c}i=1\\ i\
eq j\end{subarray} }^{N}x_{ijm}-\sum_{ \begin{subarray}{c}k=1\\ k\
eq j\end{subarray} }^{N}x_{jkm}=0,\forall\text{ nodes }j=1,\ldots,N,\ \ \forall\text{ MoEl's }m=1,2,\ldots,M. \tag{5}\]  
(5) ensures that a visit to node \(j\) by the \(m\)th-MoEl has a corresponding departure. **Inequalities**  
\[\sum_{m=1}^{M}(x_{ijm}+x_{jim})\leq 1,\quad\forall\text{ nodes }i,j=1,\ldots,N,\quad i\
eq j. \tag{6}\]  
(6) indicates the existence of a complete directed graph between the WSN's static nodes. \[\sum_{i\in\mathcal{J}}\sum_{ \begin{subarray}{c}j\in\mathcal{J}\\ j\
eq i\end{subarray} }x_{ijm}\leq|\mathcal{I}|-1,\quad\forall\text{ subset }\mathcal{J}\subseteq N,\quad|\mathcal{J}|>2,\quad\forall\text{ MoEl's }m=1,2,\ldots,M, \tag{7}\]  
where the symbol \(|\mathcal{J}|\) refers to the cardinality of set \(\mathcal{J}\). (7) is formed separately for each MoEl and eliminates sub-tours.