# UVCS: Unit Virtual Coordinate System for UAV Intra-Swarm Routing in GPS-Denied Environment
## 5 Performance Metrics  
The development of metrics for evaluation of the effectiveness of the developed UVCS approach for self-organization and topology support in a drone swarm is a separate task, that has two aspects. On the one hand, positioning accuracy can be evaluated, while, on the other hand, the ability to maintain swarm connectivity should be estimated. The peculiarity is that graphs built on the known physical coordinates and on the calculated virtual coordinates are isomorphic [35; 36]. It should also be taken into account that different routing algorithms in the same coordinate system can give different results in terms of the route characteristics. A routing algorithm can be formally described by the rule for choosing the first vertex \(n_{k}(i)\) on the path from vertex \(i\) to vertex \(k\). Here \(n_{k}(i)\in\overline{\mathcal{S}_{i}},i,k\in\mathcal{V}\), where \(\overline{\mathcal{S}_{i}}=\mathcal{S}_{i}\cup\{i\}\) is the set of vertices containing edges originating from vertex \(i\) including a vertex \(i\) itself. For the Geo algorithm the choice of node \(n_{k}(i)\) follows the principle  
\[n_{k}(i)=\underset{j\in S_{i}}{\text{argmin}}\rho(\mathbf{s}_{j},\mathbf{s}_{ k}),i\
eq j. \tag{15}\]  
This section describes several performance metrics: topological similarity index, routing similarity index, number of discovered paths, and average discovered path length. All metrics depend on the routing algorithm that works on the top of the coordinate system--either physical or virtual. The Geo routing algorithm (15) is used by default for all metrics, and we also use [PERSON]'s algorithm for the shortest path finding as a benchmark to evaluate the last two metrics--number and mean length of discovered paths. The _topological similarity index_ compares the degree to which the virtual graph replicates the physical graph in terms of distances between vertices. We calculate by (1) the distance \(\rho(\mathbf{s}_{i},\mathbf{s}_{j})\) in all pairs \((i,j)\) of vertices, regardless of their connectivity, and, using [PERSON]'s correlation coefficient [37], compare the pairwise distances between them. The next metrics of interest are a group of routing metrics--routing similarity index, number of discovered paths, and average discovered path length. The _routing similarity index_ is based on application of the apparatus of closed queuing networks and is carried out in two steps. The first step is to develop the stochastic routing matrix \(\mathbf{P}=[P(i,j)]\) of transition probabilities, \(i,j\in\mathcal{V}\). Assuming that, from each node, a customer equiprobably chooses one of the adjacent nodes from \(\overline{\mathcal{S}_{i}}\), we obtain  
\[\sum_{j\in\overline{\mathcal{S}_{i}}}\delta_{n_{k}(i),j}=1,\qquad\sum_{k=1}^{N }\sum_{j\in\overline{\mathcal{S}_{i}}}\delta_{n_{k}(i),j}=N. \tag{16}\]  
Then, the transition probability from node \(i\) to node \(j\), \(i,j\in\overline{\mathcal{S}_{i}}\), is as the following:  
\[P(i,j)=\frac{1}{N}\sum_{k=1}^{N}\delta_{n_{k}(i),j}. \tag{17}\]  
In the second step, we solve the balance equations  
\[\mathbf{p}\mathbf{P}=\mathbf{p},\qquad\mathbf{p}\mathbf{u}=1, \tag{18}\]  
and obtain a vector \(\mathbf{p}\) with the components \(p(i)\) representing the proportion of time spent by the customer in node \(i\in\mathcal{V}\) or the frequency of usage of node \(i\) while routing. As a measure of the difference between the two routing schemes the following metric can be considered:  
\[\|\mathbf{p}_{1}-\mathbf{p}_{2}\|=\sum_{i=1}^{N}|p_{1}(i)-p_{2}(i)|. \tag{19}\]  
In case \(\mathbf{p}_{1}\) is a vector related to the physical graph, and \(\mathbf{p}_{2}\) is related to the virtual one, metric (19) shows the degree of similarity of routing in the physical and virtual graphs. The approach (19) can also be used to evaluate the degree of similarity of two routing algorithms. Finally, we define two more routing metrics--the _number of paths_ and the _average path length_ metrics.