# Optimizing Charging Pad Deployment by Applying a Quad-Tree Scheme
## 3 Optimizing the Charging Pad Deployment Problem by Applying the Quad-Tree Scheme
### Problem, Notation and System Model
#### 3.1.3 Problem Definition  
In the network model section, the use of pads can extend the drone charging range. Therefore, in a large-area WRSN, the proper configuration of the pads will undoubtedly determine the performance of the network. Based on construction cost considerations, the number of pads should be as small as possible. Since the purpose of using pads is to expand the range of drone sensor charging services, for any sensor \(X\) in the network, after building a suitable pad, the drone can find at least one path from the BS to \(X\) to complete the charging task. The problem discussed in this article can therefore be defined as follows. Given a _size_\(\times\)_size_ two-dimension WRSN network \(N\), \(n\) sensors \(S\) = {\(s_{1}\), \(s_{2}\),..., \(s_{n}\)} located at {(\(s_{1,v}\), \(s_{1,v}\)), (\(s_{2,v}\), \(s_{2,y}\)),..., (\(s_{n,x}\), \(s_{n,y}\))} respectively, a base station \(B\) located at (\(p_{0,x}\), \(p_{0,y}\)) = (\(size/2\), \(size/2\)), and a drone \(U\), the problem is to find out how to place the minimum number \(m\) of charging pads \(P\) = {\(p_{1}\), \(p_{2}\),..., \(p_{m}\)} located at {(\(p_{1,x}\), \(p_{1,y}\)), (\(p_{2,x}\), \(p_{2,y}\))..., (\(p_{m,x}\), \(p_{m,y}\))} to satisfy coverage and connectivity constraints as stated in [6]. Let \(d(s_{i}\), \(p_{j})\) represent the distance between sensor \(s_{i}\) and pad \(p_{j}\) and let \(d\left(p_{i},p_{j}\right)\) represent the distance between pad \(p_{i}\) and pad \(p_{j}\), \(p^{\prime}\) = \(\left\{B\right\}\cup P\) = {\(p^{\prime}_{0}\) = \(B\), \(p^{\prime}_{1}\), \(p^{\prime}_{2}\),..., \(p^{\prime}_{m}\)}, and \(\Omega\) be a permutation of a subset Q of \(P^{\prime}\). A two-tuple (x, y) is called a point in two-dimension Euclidean plane \(R^{2}\); that is, we have (x, y) \(\in R^{2}\). Thus, the objective is to minimize the number of pads located at the two-dimension Euclidean plane \(R^{2}\), subject to the constraints specified by Equations (8)-(14). \[\text{Minimize}\sum\
olimits_{\text{every point }(x,y)\text{ in }R^{2}}\left(\Phi_{x,y}\right) \tag{7}\]  
Subject to:  
\[\Phi_{x,y}=\left\{ \begin{array}{ll}1&\text{if a pad has been deployed at the point }(x,y)\in R^{2},\\ &0<x\leq\text{size and }0<y\leq\text{size}\\ 0&\text{otherwise}\end{array} \right. \tag{8}\]  
\[P=\left\{p_{i}\Big{|}\,p_{i}=(x_{i},y_{i})\text{ and }\Phi_{x_{i},y_{i}}=1, where(x_{i},y_{i})\in R^{2},0<x_{i}\leq\text{size},0<y_{i}\leq\text{size}\right\} \tag{9}\]  
\[P^{\prime}=\left\{B\right\}\cup P \tag{10}\]\[ \begin{split}\exists\text{i}\ \Omega\ \text{such that}\underset{\Omega}{\sum}\Bigg{(}a_{0,\Omega(1)}\times\prod\limits_{k=1}^{|Q|-1}a_{\Omega(k), \Omega(k+1)}\times a_{\Omega(|Q|),j}\Bigg{)}\geq 1,\ \ \forall p_{j}\in P^{\prime},\\ \text{Where}\ \Omega\ \text{is a permutation of a subset}\ Q\ P-\{p_{j}\} \\ a_{i,j}=\left\{\begin{array}{ll}1&if\ d\left(p^{\prime}_{i},p^{ \prime}_{j}\right)\leq D_{max,pd},\ \ p^{\prime}_{i}\
eq p^{\prime}_{j},\ p^{\prime}_{i}\ \text{and}\ p^{\prime}_{j}\in P^{\prime}\\ 0&\text{otherwise}\end{array}\right.\\ \text{When}\ \mathrm{i}\ >\ 0,\ \mathrm{j}\ >\ 0,\ \text{we have}\ p^{\prime}_{i},p^{\prime}_{j}\
i P ;\ \text{and we have}\ p^{\prime}_{0}=B\\ \sum\limits_{p_{j}\in P^{\prime}}b_{i,j}\geq 1,\ \forall s_{i}\in S \\ b_{i,j}=\left\{\begin{array}{ll}1&if\ d\Big{(}s_{i},p^{\prime}_{i}\Big{)} \leq D_{max,charging},s_{i}\in S,\ p^{\prime}_{j}\in P^{\prime}\\ 0&\text{otherwise}\end{array}\right.\end{split}  \tag{12}\]  
Where \(a_{i,j}\) and \(b_{i,j}\), respectively, represent whether the distance between pad \(i\) and \(j\) is not greater than \(D_{max,pad}\), and whether the distance between sensor \(i\) and pad \(j\) is not greater than \(D_{max,charging}\). As for Figure 2, the displayed edges represent the distances that meet the requirements.