# Flying Real-Time Network to Coordinate Disaster Relief Activities in Urban Areas +
## 3 Proposed Network System
### Initial Network Deployment  
Network deployment is a key issue in emergency situations, since the communication network cannot be set-up ahead of time for two main reasons. First, most natural disasters typically destroy or damage the physical infrastructure in the affected area, thus jeopardizing the availability of these networks when required. Second, it is not clear where one should deploy the new communication network ahead of time, given that in most cases it is impossible to predict what areas will be affected by the event. Once the extreme event has taken place, the IC decides where the SAR teams should be deployed first in order to start the relief activities; in that case, a TWU is assigned to each SAR team. These units will probably not be sufficient to cover the transmission range between the teams and the IC, and therefore additional FWUs (particularly meta-TWUs or flying mules) should be used to link the SAR teams with the IC. Next we describe a solution to the problem of determining a suitable deployment for the TWUs, given a certain physical area and communication range. As expected, we would like to deploy the TWUs in a specific set of locations, so that a minimal number of TWUs are used to guarantee communication in a given geographic area. We can assume as input a squared work area specified by adjustable side parameters. This matches with the typical quadrants used in first responses to divide the scouting area during SAR activities. Figure 2 shows various TWU deployment scenarios and also their network coverage areas. The challenge of performing an appropriate deployment of TWUs can be reduced to a clustering or continuous/unconstrained location problem, where the facilities (in our case, the TWUs) can be anywhere in the plane [23], which is NP hard. This means that we can only have an approximation to the solution in polynomial time; conservatively, we can deploy extra FWUs to meet communication requirements. Thus, we can increase the network robustness (i.e., its tolerance to failures), a feature appreciated in highly dynamic and uncertain environments, such as in FANETs. We solve the initial deployment using an adaptation to the widely used \(k\)-means algorithm (Lloyd's algorithm) [24; 25], which has average running time complexity of \(O(k\times n\times i)\), were \(k\) is the number of clusters, \(n\) is the number of data points, and \(i\) is the number of iterations required for convergence. In practice, the \(k\)-means algorithm is very fast and the number of performed iterationsis effectively much less than the number of data points in the space. We chose the \(k\)-means algorithm because of its simplicity and short running time. As described in Algorithm 1, the deployment works by clustering data points in a two-dimensional Euclidean plane. Given \(P\) user locations, the goal is to choose minimal cluster centers (TWU nodes), given by \(Q\), that minimize the average distances between each data point and its closest center, while allowing nodes to communicate effectively by guaranteeing that the distance between each point (e.g., a SAR team) and its cluster is within a suitable transmission range (strong signal strength).