# A Hybrid Metaheuristic Algorithm for the Efficient Placement of UAVs
## 3 System Model and Problem Formulation
### System Model  
In this section, we describe how we model the UAV placement problem as an uncapacitated single allocation \(p\)-hub median problem. We seek to find the locations of \(p\) UAVs that maximize the total (sum) link capacity, while ensuring that each of the \(n\) users are assigned to only one UAV, as mentioned before. Thus, because we target the application of the UAV-assisted relay infrastructure to scenarios, such as disaster relief, rescue operations, remote or hostile environments, etc., no minimum requirements are imposed on data link rates (i.e., we seek to provide the best possible data link rates under given circumstances). For that, we consider the Shannon capacity to express the maximum data rate (expressed in b/s) that can be achieved at either air-to-ground (A2G) or air-to-air (A2A) data link between two nodes \(i\) and \(k\), i.e.,  
\[C_{ik}=B\log_{2}\left(1+\frac{S_{ik}}{N}\right), \tag{6}\]  
where \(B\) denotes the channel bandwidth (Hz), \(N\) is the noise power within the channel bandwidth \(B\), and \(S_{ik}\) denotes the signal power received on either side of the A2G link (user \(i\) and UAV \(k\)), or in either side of the A2A link (UAV \(i\) and UAV \(k\)). In this scenario, the UAVs act as \"base stations\" to users on the ground, relaying data packets to or from any user assigned to it. Consequently, every transfer of data packets between a pair of users has to go through either two hops (one UAV assigned to both users) or three hops (two UAVs, each assigned to a distinct user in the pair). Additionally, the UAVs are responsible for the scheduling of all transmissions among users assigned to them, and they do so in a way that no interference occurs (i.e., all transmissions are assumed to be collision-free). Note that we are only concerned with establishing the aerial relay infrastructure by focusing on determining the optimal placement of UAVs that render the highest total (sum) rate capacity. Therefore, we do not consider flows of data packets between pairs of users, i.e., we are not concerned with data throughput in this work. This also means that signal interference due to the activity of other (distant) users or UAVs is not taken into account and, therefore, only thermal background noise is considered (assumed to be additive white Gaussian noise (AWGN)). As far as the channel propagation model is concerned, we assume that all of the UAVs are placed at a constant altitude \(h\) from the ground (defined beforehand), and they are all in Line-of-Sight (LOS) to each other and to every other user on the ground. Consequently, the Friis path-loss propagation model is assumed [30] for both A2G and A2A channels, which means that the received signal power \(S_{ik}\) (in dBm) between a node \(i\) and a node \(k\) will be given by  
\[S_{ik}=P_{t}+G_{t}+G_{r}-20\log_{10}\left(\frac{4\pi f_{c}}{c}\right)-20\log_{ 10}(d_{ik}), \tag{7}\]  
where \(P_{t}\) is the transmit power (measured in dBm), \(G_{t}\) and \(G_{r}\) are the transmit and receive antenna gains, respectively (expressed in dBi), \(f_{c}\) is the carrier frequency (in Hz), \(c\) is the speed of light (\(3\times 10^{8}\) m/s), and \(d_{ik}\) is the absolute distance (or LOS distance) between node \(i\) and node \(k\). Thus, for an A2G link, the absolute distance between user \(i\) and UAV \(k\) will be given by \(d_{ik}=\sqrt{h^{2}+r_{ik}^{2}}\), where \(r_{ik}\) denotes the Euclidean distance between user \(i\)'s location on the ground and the \((x,y)\) coordinates of UAV \(k\) on the ground (i.e., its projection on the ground). Likewise, because all of the UAVs are located at the same altitude \(h\), the absolute distance between UAV \(i\) and UAV \(k\) is simply given by \(d_{ik}=r_{ik}\). We first need to note that we are not dealing with specific flows of data packets between users in order to cast the problem of placing UAVs as aerial relays to users on the ground within the framework of a \(p\)-median optimization problem, as mentioned previously.