# UAV Charging Station Placement in Opportunistic Networks
## 7 Routing Protocols
### State-Based Campus Routing (SCR) Protocol
**KAIST Dataset**: KAIST dataset contains 22 movement traces of students in KAIST campus for 83,970 s which equates to more than 23 h. The width of the simulation environment is 13,226 m by 19,208 m. We have removed the traces that are shorter than 2 h in the original KAIST dataset, leaving 22 movement traces. ### Metrics and Evaluation

Nine combinations are examined, DBSCAN with Epidemic (D_EP), DBSCAN with SCR (D_SCR), DBSCAN with Spray and Wait (D_SW), K-Means with Epidemic (K_EP), K-Mean with SCR (K_SCR), K-Mean with Spray and Wait (K_SW), Random with Epidemic (R_EP), Random with SCR (R_SCR), and Random with Spray and Wait (R_SW). In our simulation, the number of clusters for K-means and Random clustering has been set to 3, and the maximum distance between clusters for DBSCAN has been set to 900 which generates 3 cluster centers as well. The number 3 has been chosen after comparing the results of several cluster center numbers as in (2, 3, 4, and 5), and the comparison resulted in favor of 3 clusters. It is important to note here that certain parameters should be analyzed collectively to evaluate a given network. Therefore, we have used four metrics to quantitatively and qualitatively assess the effect of the aforementioned nine techniques on network performance. The metrics used are message delay, success rate, number of tours, and number of messages sent. #### 8.3.1 Message Delay

Message delay is one of the main metrics used to measure network performance, as it focuses on the time spent in the successful transfer of data packets from one point to another. Message delay is defined as the time elapsed from creation until receipt of the message. Message delay is calculated for every message created during the simulation. Figures 4 and 5 shows the cumulative distribution of message delay in the NCSU and KAIST datasets, respectively. To better visualize the message delay, we use box plots to present the data. \begin{table}
\begin{tabular}{l c c} \hline \hline
**Dataset Property** & **NCSU** & **KAIST** \\ \hline Number of nodes & 35 & 22 \\ Length of the map (in meters) & 14,628 & 19,208 \\ Width of the map (in meters) & 9713 & 13,227 \\ Data collection duration (in seconds) & 78,090 & 83,970 \\ Data collection frequency (in seconds) & 300 & 300 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Dataset properties. Regardless of the routing protocol used, the figures show that K-Means clustering (K_EP, K_SCR, K_SW) performs noticeably better than Random (R_EP, R_SCR, R_SW) and DBSCAN (D_EP, D_SCR, D_SW) clustering. When focusing on routing protocols, we see that Epidemic and SCR have very close results as both graph lines almost coincide with each other, yielding better results than Spray and Wait routing. The best message delay readings can be found when K-Means clustering is combined with Epidemic routing. It is also clear that the behavior of every clustering approach is enhanced when Epidemic or SCR Routing protocols are chosen. #### 8.3.2 Success Rate

The success rate is defined as the percentage of the nodes that received a specific message. In other words, it is the rate of successful message delivery. The higher the success rate for a message, the higher the percentage would be. The success rate is the distribution rate of the message. If a message stays in the buffer of the node, then the success rate of the message is 0%. On the other hand, if the message is distributed to every node, the success rate is 100% [57]. Figures 8 and 9 shows the complementary cumulative distribution of success rate in the NCSU and KAIST datasets, respectively. Figures 10 and 11 shows the box plots of success rate distribution for three generated cluster centers for the KAIST and NCSU datasets, respectively. Again, the K-Means clustering with Epidemic and SCR schemes appear to achieve the highest success rates among their counterparts. It can be seen that both datasets show consistent behaviors.