# Recharging Schedule for Mitigating Data Loss in Wireless Rechargeable Sensor Network
## 3 Network Model and Charging Scheme
### Problem Formulation  
The mobile charger's scheduling problem can be defined as follow. We model the location of potential charging tasks in terms of a complete graph \(G=(V,E)\). For achieving high charging efficiency, the charger can only charge one node each time and stay close to the node when performing charging task. For the sake of simplicity, we assume that the locations of the charging task are coinciding with locations of nodes. Therefore, the vertex \(v_{i}\in V(0\leq i\leq\mid\mid\mid N\mid)\) is the location of node \(i\), and \(v_{0}\) is the base station's location where the tour starts and ends. Each vertex \(v_{i}\) has a positive reward, which is equal to the weighted criticality index \(\hat{r}_{i}\) of node \(i\). We assume each node can be  
Figure 3: Example of network. (**a**) The original network; (**b**) The network of node E removed; (**c**) The network of node B removed.  
visited only once at most, therefore, the reward at a node can be collected only once. \(E=\left\{(v_{i},v_{j})\right\}\) denotes the set of edges and presents potential paths between tasks. We define binary variables \(x_{i}\in\left\{0,1\right\}\left(0\leq i\leq\left|N\right|\right)\) to be 1 if \(v_{i}\) is visited in the tour and 0 otherwise. Define binary variables \(y_{ij}\in\left\{0,1\right\}\left(0\leq i,j\leq\left|N\right|\right)\) to be 1 if the edge from \(v_{i}\) to \(v_{j}\) is traveled and 0 otherwise. Each edge \((v_{i},v_{j})\) has an edge cost \(c_{ij}\), which represents the Euclidean distance between \(v_{i}\) and \(v_{j}\), and \(c_{ij}=c_{ji}\).  
There is only one mobile charger with traveling distance constraint \(L\) in the network, which may not be able to visit and perform charging task on entire nodes. To maintain the network connectivity as long as possible, the mobile charger should preferentially visit the nodes with higher weighted criticality index and lower traveling cost during each charging tour. In other words, the sum of weighted criticality indexes of the nodes selected to be visited in a charging tour should be maximized, which can be treated as a maximization problem subject to the total traveling distance of the mobile charger is upper bounded by \(L\). We formulate the maximization problem as an integer programming problem, which is shown as follow:  
\[\max\sum_{i=1}^{\left|N\right|}x_{i}\hat{r}_{i} \tag{5}\]  
Subject to  
\[\sum_{v_{j}\in V\backslash\{v_{i}\}}y_{ij}=x_{i}\quad v_{i}\in V \tag{6}\]  
\[\sum_{v_{i}\in V\backslash\{v_{j}\}}y_{ij}=x_{j}\quad v_{j}\in V \tag{7}\]  
\[\sum_{i\
eq j}y_{ij}\cdot c_{ij}\leq L\quad v_{i},v_{j}\in V \tag{8}\]  
\[2\sum_{v_{i}\in S}x_{k}\leq\left|S\right|(\sum_{v_{j}\in S,v_{j}\
otin S}y_{ij }+\sum_{v_{i}\
otin S,v_{j}\in S}y_{ij})\quad S\subset V\backslash\{v_{0}\}; \left|S\right|\geq 2 \tag{9}\]  
\[x_{0}=1 \tag{10}\]  
\[x_{i}\in\{0,1\}\quad v_{i}\in V \tag{11}\]  
\[y_{ij}\in\{0,1\}\quad(v_{i},v_{j})\in E \tag{12}\]  
In the above formulation, constraint (6) and (7) ensure that each vertex is visited at most once, where \(\backslash\) denotes the set difference. Constraint (8) guarantees the edges traveled by the mobile charger would not exceed the distance limit. Constraint (9) is a sub-tour elimination constraint [27], where \(S\) is an arbitrary subset of \(V\). Constraint (10) states that the base station must be selected. Constraint (11) and (12) impose the decision variables \(x_{i}\) and \(y_{ij}\) to be 0-1 valued, respectively.  
Let \(L\) denote the budget and \(\hat{r}_{i}\) denote the vertex reward, this formulation can be regarded as a kind of traveling salesman problem with profits, which is also called orienteering problem [28]. The goal of the orienteering problem is to design a closed path, or a tour, to visit a subset of vertices that maximizes the total reward collected, which has ingredients of both the traveling salesman problem (TSP) and the knapsack problem and is proved to be NP-hard [29].