Information Transmission in a Drone Swarm: A Temporal Network Analysis

Abstract

We consider an ensemble of drones moving in a two-dimensional domain, each one of them carrying a communication device, and we investigate the problem of information transfer in the swarm when the transmission capabilities are short range. The problem is discussed under the framework of temporal networks, and special attention is paid to the analysis of the transmission time of messages transported within the swarm. Traditional theoretical methods of graph theory are extended to tackle the problem of time-varying networks and a numerical analysis of the detection time statistics is performed in order to evaluate the efficiency of the communication network as a function of the parameters characterizing the swarm dynamics.

1. Introduction

A drone swarm is an ensemble of drones that cooperate with a view to achieving a common goal. An important feature of a swarm is the ability of its members to operate in a coordinated way while having a wide degree of autonomy [1]. To be able to function in a fully autonomous way, to perform complex tasks, and to carry out various types of missions without external intervention, collective, if not intelligent, behavior must emerge from local interactions between entities [2]. In this respect, the sharing of information among drones is the key for taking collective decisions [3]. For that, drones must efficiently communicate with each other while maintaining the security and secrecy of the transmitted information [4]. Long-range information transfer between drones will certainly maintain the cohesion and effectiveness of the swarm, but it also makes it vulnerable to remote listening and cyber attacks [5]. To curb piracy, drones can be equipped with minimal sensing capacities and a limited communication range. Unfortunately, in some cases, such limitations, combined with the remoteness and sparseness of the drone population, can disrupt the entire information flow in the swarm. This implies that communication in the swarm is critically dependent on drone movements and positions, because drones interact only with local neighbors. The result is a communication network whose structure is constantly evolving, with links being added and deleted according to drone displacements. Such network models are called temporal or dynamical [6,7]. From this perspective, drone swarms merely reproduce real-world systems whose components interact dynamically, establishing connections that may appear and disappear over time or simply vary in strength. In nature, examples of time-varying systems forming networks abound. In biology, for example, one finds gene-regulatory networks [8,9,10], protein interaction networks [11], and brain functional networks [12]; all of these networks are inherently time-varying. New technologies also provide examples of dynamical networks, e.g., communication networks [13] and power transmission networks [14], not to mention social networks [15,16]. Clearly, networks are of primary importance for solving complex problems arising from interacting individuals. Of particular interest for our purposes here is communication, a specific form of interaction that involves the transfer of information between individuals. Knowing how information is generated and shared is of prime importance to understand cooperation and consensus problems [17,18]. In this context, understanding the interplay between the network structure and information flow is crucial; for this reason, numerous studies have been devoted to studying the impact of network structures on the dynamics taking place in them [19]. In particular, diffusive processes [20] have been successfully applied in epidemiology to understand disease dynamics and spread [21].

As noted above, in a temporal network, communication is significantly influenced by the dynamics of the group members. Widely studied examples of this are the problems of synchronization in a swarm [22] or in a sensor networks [23] and the problems of information transfer in a mobile communication network [24] and in the brain network [25]. For the same reason, we are looking in this work at the problem of communication and information transfer within a swarm of mobile drones. More specifically, our goal is to assess the efficiency and effectiveness of a communication network built from intermittent contacts between drones. The focus is very much on information transfer; search and rescue missions or coordination strategies between complex units are not being addressed here. Therefore, the simplest microscopic model of drones has been considered: drones are points that evolve individually, and their motion follows a random walk. Such a level of abstraction will not affect our findings, since our interest is in the dynamical communication network, irrespective of its constitutive units.

To assess the efficiency of the communication network, we investigate the transit time of messages between two points located in the drone operation area (see Figure 1). A key parameter of the model is the communication range of the drones, $r_c$. According to the value of $r_c$, the drones will be densely or sparsely connected, which impacts the transfer of information and, thereby, its travel time. In this work, this issue is analyzed and quantified by computing the first-passage time probability of messages sent over the communication network. The first-passage time is one case among many first-passage problems [26] which has proven to be a reliable tool to explore the dynamics of complex systems [27] and to characterize interconnections in complex systems. In the field of communication, in particular, the first-passage method has been extensively used for network security analyses [28] and for reliability analyses of systems subject to random failure [29]. In the context of this work, the value of the first-passage formalism lays in the fact that it provides a link between the parameters of a model and average times often probed in experiments. In ecology, for example, first-passage times have been used for animal movement analyses [30,31].

In Section 2, our model of drone motion is presented and the theory of single message transmission in a drone swarm is presented. A generalization of the formalism to tackle the multiple-message problem is detailed in Section 3. In Section 4, the transmission of messages in our drone swarm model is studied. Finally, Section 5 contains the concluding remarks and perspectives.

2. The Swarm and Communication Network Modeling

Consider a set of $N_d$ drones moving independently in a bounded domain. One can assume that the drones operate at a constant altitude, not necessary the same for all drones, which allows us to consider their motion as taking place in a two-dimensional domain, $\mathcal{D} = [0 ,L_x]\times [0 ,L_y]$. The motion of the drones in $\mathcal{D}$ is modeled as a correlated random walk, a stochastic process whose trajectory mimics the displacement of many animals [32,33,34,35]. The drones are equipped with sensors to compute distances and a sending and receiving device that allows them to exchange messages between each other. In the swarm, one drone, which will be called the target, serves as an access point that collects the messages sent by the other drones. To clarify the theoretical model, we will consider messages that are sent when a drone is near the information source located in $\mathcal{D}$. More specifically, we study the transmission of messages between two fixed locations; the first is where the information is found and the other is the position of the target drone. This situation represents drones that are exploring an area, and once information is found, it is transmitted via the swarm to a ground station. The situation is depicted in Figure 1, showing a message which being transmitted by a drone from the upper right corner of the domain to the receiving target drone located in the opposite lower left corner.

2.1. The Drone Motion

The motion of the drones is modeled as a succession of directed movements, with a fixed velocity $v_d$ along a selected orientation, interrupted by sudden scatterings that change the orientation of the velocity. A displacement along any given direction occurs for a random amount of time, and the lengths of the straight-line segments are assumed to be independent and identically distributed. To specify the persistence of the velocity direction, we introduce $\psi \left(t\right)$, defined such that $\psi \left(t\right) dt$ is the probability of the velocity having the same direction in the time interval $(t , t+dt)$ [36]. Then, $\mathrm{\Psi }\left(t\right) = {\int }_t^{\infty } \psi \left(\tau \right) d\tau$ is the probability of a change in orientation after time t. Here, we choose the exponential $\psi \left(t\right) = \lambda exp(-\lambda t)$, so that the probability of time $t_s$ between successive scatterings is

$$\mathrm{\Psi }\left(t_s\right) = \exp (-\lambda t_s) ,$$

(1)

where $\lambda$ is the scattering frequency.

Let $\theta$ be the angle between a single line segment and the x axis. The succession of the angles of the segments of the walk is specified by $\beta \left(\theta \right|{\theta }^{\prime })$, defined such that $\beta \left(\theta \right|{\theta }^{\prime }) d\theta$ is the probability that a segment with orientation ${\theta }^{\prime }$ is followed by a segment with orientation in the angular interval $(\theta ,\theta +d\theta )$. We will assume that $\beta \left(\theta \right|{\theta }^{\prime })$ depends only on the scattering angle $d\theta = \theta -{\theta }^{\prime }$.

The positions and orientations of the drones are updated at time interval $\Delta t$ according to

$$\begin{array}{ccc}\hfill x_i(t+\Delta t)& =& x_i\left(t\right) + v_d \cos \left({\theta }_i\left(t\right)\right) \Delta t ,\hfill \\ \hfill y_i(t+\Delta t)& =& y_i\left(t\right) + v_d \sin \left({\theta }_i\left(t\right)\right) \Delta t ,\hfill \end{array}$$

(2)

and

$${\theta }_i(t+\Delta t) = {\theta }_i\left(t\right) + d{\theta }_i\left(t\right) ,$$

(3)

where $(x_i\left(t\right) ,y_i\left(t\right))$ are the positions of the drones $i=1,\dots ,N_d$, in the domain $\mathcal{D}$ at time t, and $d{\theta }_i\left(t\right)$ are random scattering angles. Let us stress that $\Delta t$ is not the time increment used for a numerical integration of the equations of motion; since the velocity $v_d$ is constant, the only restriction on $\Delta t$ is $\Delta t<t_s$, where $t_s$ is the random time interval between two scattering events. Equation (2) updates the position of a drone between scatterings. Similarly, the orientations ${\theta }_i\left(t\right)$ are constant most of the time, and the scattering angles $d{\theta }_i\left(t\right)$ take non-zero values only at scattering time $t_s$. Most importantly, $\Delta t$ should be regarded as a parameter, integrated into the drone software, that punctuates the drone activity; in practice, with a frequency ${(\Delta t)}^{-1}$, a drone attempts to modify the orientation of its velocity with a probability of success p. Then, the probability of maintaining the same orientation k times is ${(1-p)}^k$, where $k\ge 0$. Since ${\sum }_{k=0}^{\infty }{(1-p)}^k = p^{-1}$, the normalized probability distribution for the duration $k\Delta t$ of a linear trajectory is given by the geometric distribution

$$P_{\mathrm{geom}}\left(k\right) = p {(1-p)}^{k-1} ,$$

(4)

where $k\ge 1$. Since the drone velocity is constant on each segment line, the length $l=k v_d\Delta t$ of the segment is also distributed according to Equation (4). When the scattering frequency is small, one can compute the continuous limit of the time between scatterings, $t_s=k \Delta t$. If $p=\lambda \Delta t$, then the probability of a duration $t_s$ is $P\left(t_s\right) = p\left(t_s\right) \Delta t$, where $p\left(t_s\right)$ is the probability density

$$p\left(t_s\right) = \underset{\Delta t\to 0}{\lim } \frac{\lambda }{1-\lambda \Delta t}{(1-\lambda \Delta t)}^{t_s/\Delta t}= \lambda exp(-\lambda t_s).$$

(5)

Therefore, since $t_s=l/v_d$, the density distribution for the segment length l is,

$$p\left(l\right) = \frac{v_d}{l_p} \exp (-\frac{v_d}{l_p} \frac{l}{v_d}) = l_p^{-1} \exp (-\frac{l}{l_p}) ,$$

(6)

where $l_p=v_d/\lambda$ is the average segment length, also called yjr persistence length. Figure 2a shows a typical drone trajectory, with random segments of length $l_i$ and scattering angle $d{\theta }_i$. At the boundaries of the domain $\mathcal{D}$, a specific scattering process is implemented such that the conditions $0\le x\left(t\right)\le L_x$ and $0\le y\left(t\right)\le L_y$ are satisfied. More specifically, when the trajectory reaches a boundary of $\mathcal{D}$, the velocity direction is first set perpendicular to the boundary, i.e., ${\theta }_i = [{\theta }_W,{\theta }_E,{\theta }_D,{\theta }_U] = [0,\pi ,\pi /2,3\pi /2]$, for west, east, down, and up boundaries, and then a random scattering angle is added to ${\theta }_i$. Figure 2b illustrates the boundary scattering process in the case of an east boundary crossing. In this work, the scattering angle $d{\theta }_i$ in Equation (3) (see Figure 2) is a random quantity uniformly distributed in an angular interval, $d\theta \in [-{\theta }_s,{\theta }_s]$. In the case of an isotropic scattering, ${\theta }_s=\pi$, and $\beta \left(\theta \right|{\theta }^{\prime }) = 1/2\pi$, so that the successive velocity orientations are independent of each other.

2.2. The Communication Network and Message Transportation

Assume the drones are equipped with sensors that allow them to sniff and detect the presence of other drones in the neighborhood of their location, which is here a circular domain of radius $r_c$ (see Figure 1). When two drones lie within their mutual detection region, drone-to-drone communication can be established, and information, i.e., a message, can be transferred between them. The topology of the drone communication system is modeled by a communication network built from the positions of the drones and the communication range $r_c$. The communication network is described by an $N_d\times N_d$ adjacency matrix $\mathbf{A}$, defined as $A_{ij}=1$ if drones $(i,j)$ are connected and $A_{ij}=0$ otherwise. Since the drones are in motion, the communication network is not frozen in time; it is a temporal network constructed from chronologically ordered snapshots of the drone positions taken in the time interval $\Delta t$. A temporal network is therefore represented by a sequence of adjacency matrices ${\mathbf{A}}^{\left[1\right]},{\mathbf{A}}^{\left[2\right]},\dots$. Here, ${\mathbf{A}}^{\left[k\right]}$ is the adjacency matrix of the network at time $t = k \Delta t$, and k is the number of time intervals elapsed since the initial time. Thereafter, $\Delta t$ will be used as the unit of time; time will be measured in time steps and is thus an integer number.

The dynamic aspect of drone interactions drastically changes the way information is transferred between drones [37,38]. In order to assess the efficiency of the communication network, we will address the issue of information transfer from the point of view of a message and use a random walk process to study how fast a signal propagates from one point in the domain to another.

The random walk process is defined by a walker, i.e., the message, that is carried by a drone and that at regular time intervals $\Delta t$ attempts to hop to another drone. A central quantity of our analysis of the problem is the message propagator $K(i,t_i|j,t_j)$, which is the probability density of finding the message at drone i at time $t_i$ under the condition it was at drone j at time $t_j\le t_i$. Then, the probability of finding the message at drone i at time $t_i$ is:

$$P_{t_i}\left(i\right) = \sum _{j}K(i,t_i|j,t_j) P_{t_j}\left(j\right).$$

(7)

The propagator K is a time-dependent quantity intertwined with the drone interaction network; the message hops from drone i to drone j if a connection exists between them at time k, i.e., $A_{ij}^{\left[k\right]}\ne 0$. At each time step k, the message hops from a drone j to another drone i, chosen uniformly at random among the $k_j$ drones connected to j. The probability of a transfer $j\to i$ at time step k is:

$$p^{\left[k\right]}(j\to i) = \frac{1}{k_j} A_{ij}^{\left[k\right]} ,$$

(8)

where $k_j={\sum }_i{A}_{ij}^{\left[k\right]}$. If at time k there are no connections between drone j and the other drones, the message stays at drone j, which implies that $p^{\left[k\right]}(j\to j)=1$. Let us stress that a message can be trapped on a drone for a while because the connection with other drones is lost; this situation is in contrast with the problem of a message propagating on a static network, where a message can always leave the drone from which it came from. However, even when trapped on a drone, a message will propagate through the carrying drone, although this propagation is not explicit. The drone dynamics that underlie the message transfer only emerge through the edges’ temporality; the variability of the matrix element $A_{ij}^{\left[k\right]}$ with time k is the only indication that something happens “behind the scenes”.

Another specificity of temporal networks is that a connection between a pair of drones $(i,j)$ is possible even if the drones are far apart. In this case, a connection can be established through a temporal path of length n, which is a time-ordered sequence of n edges $A_{i,s_1}^{\left[k_1\right]} A_{s_1,s_2}^{\left[k_2\right]} \dots A_{s_{n-1},j}^{\left[k_n\right]}$ with $k_1<k_2\dots <k_n$. In practice, a long temporal path may contain very few drones. The path $i\to 1\to 1\to \dots \to 1\to j$, for example, corresponds to the situation in which a message is transported from i to j by the single drone 1; in this case, only two message hops occur, and the duration of the transmission will depend on the distance traveled by the carrier drone 1. Thereafter, we will focus on $t_f$, the time required for information collected by a drone $d_0$ at some location in the domain to reach a target drone $d_f$, whose position in the domain is fixed. To be specific, we will analyze the statistics of the first-passage time, $t_f\left(d_0\right)$, of a message transmitted through the communication network from a drone $d_0$ to another drone $d_f$. Since the message can follow different paths to reach the target destination from its initial position, the first-passage time is a random quantity whose probability distribution is $P\left(t_f\left(d_0\right)\right)$. To compute $P\left(t_f\left(d_0\right)\right)$, it is appropriate the treat the target drone $d_f$ as a trap, absorbing messages, so that the probability of the message leaving $d_f$ is zero, or similarly, that the probability of staying at $d_f$ once reached is one. Therefore, we impose that

$$p^{\left[k\right]}(d_f\to j) = {\delta }_{fj}.$$

(9)

From now on, we will assume that the target is drone one, i.e., $d_f=1$. The probability of the message being on drone i at time k obeys the master equation

$$P_{k+1}\left(i\right) = \sum _j{M}_{ij}^{\left(k\right)} P_k\left(j\right) ,$$

(10)

where $M_{ij}^{\left(k\right)}=K(i,k+1|j,k)$ is the one-step propagator at time k. Using the transition probabilities (8) and (9) with $d_f=1$:

$$$$

(11)

where the transition probabilities $p_{i\leftarrow j}$ are computed from the drone network configuration at time k. The first column of the matrix ${\mathbf{M}}^{\left(k\right)}$ contains the probability of leaving the target; since $d_f$ is a trap, the transition probabilities of this column are time-independent. The first row of ${\mathbf{M}}^{\left(k\right)}$ contains the probabilities of reaching the target; their values depend on the number of drones within the detection area of drone 1 at time k. Iterating the relation (10) gives:

$$P_{k+2}\left(i\right) = \sum _j\sum _l{M}_{il}^{(k+1)} M_{lj}^{\left(k\right)} P_k\left(j\right) = \sum _j{( M^{(k+1)}\circ M^{\left(k\right)})}_{ij} P_k\left(j\right) ,$$

(12)

where $(M^{(k+1)}\circ M^{\left(k\right)})$ denotes a matrix that is the product of two successive one-step propagators. Considering that at the initial time, the probability of the message being at drone j is $P_0\left(j\right)$, we can write:

$$P_n\left(i\right) = \sum _j{\mathcal{L}}_{ij}^{\left[n\right]}{P}_0\left(j\right) ,$$

(13)

where

$${\mathcal{L}}_{ij}^{\left[n\right]} = \mathcal{L}(i,n|j,0) = {(\prod _{k=1}^n{M}^{\left(k\right)})}_{ij} ,$$

(14)

is the n−step propagator, defined as the probability of finding the message at drone i at time n under the condition that the message was at drone j at the initial time. One can observe that, since for $i=d_f=1$ the message stays trapped on the drone, the element ${\mathcal{L}}_{1j}^{\left[n\right]}$ of the n−step propagator can only increase with n. Consequently, ${\mathcal{L}}_{1j}^{\left[n\right]}$ contains the probability of a message sent by drone j at time zero being detected by the target at any time up to n. As an illustration of this, consider the situation depicted in Figure 3a, where information found by drone B is transferred to drone C, which will take it to drone A. The temporal network corresponding to this scenario is displayed in Figure 3b. The one-step message propagators $M^{\left(k\right)}$ at time $k=0,1,\dots 6$ are shown in Figure 3c, together with the n−step propagators ${\mathcal{L}}^{\left[n\right]}$ at time $n=4,5,6$. The matrix element highlighted in red is ${\mathcal{L}}_{AB}^{\left[n\right]}$, the cumulative probability of finding the message at the target A at different times. As explained, this probability is zero for $n\le 4$, while for $n\ge 5$, its value is equal to one.

2.3. The Communication Probability

The transmission probability $P_{trans}$ is the probability that a message sent by drone j will ultimately reach the target drone. This probability is obtained from the n−step propagator as:

$$P_{trans} = \underset{n\to \infty }{lim}{\mathcal{L}}_{1j}^{\left[n\right]} .$$

(15)

As, except for in some specific situations, the transmission probability is equal to one, it is more informative when comparing different situations to put a limit on the transmission time and to consider:

$$P_{trans}\left(n_l\right) = {\mathcal{L}}_{1j}^{\left[n_l\right]} ,$$

(16)

instead, where $n_l$ is a threshold time beyond which no transmission shall be considered valid.

The probability distribution of the transmission time $t_f\left(j\right)$ between j and 1 is obtained from the cumulative distribution ${\mathcal{L}}_{1j}^{\left[n\right]}$ as:

$$\mathrm{Pr}(t_f=n) \equiv \mathcal{G}(1,n|j,0) = {({\mathcal{L}}^{\left[n\right]}-{\mathcal{L}}^{[n-1]})}_{1j} ,$$

(17)

and the average transmission time is:

$${\langle t_f\rangle }_j = \sum _{n=1}^{\infty } n {\mathcal{G}}_{1j}^{\left[n\right]} ,$$

(18)

where ${\mathcal{G}}_{1j}^{\left[n\right]}=\mathcal{G}(1,n|j,0)$. The average average transmission time can also be obtained from the n−step propagator as:

$${\langle t_f\rangle }_j = \sum _{n=1}^{\infty } (1 -{\mathcal{L}}_{1j}^{[n-1]}) .$$

(19)

It is important to stress that in this expression, $\langle ·\rangle$ represents the average of paths that a message can take in a single realization of the drone trajectory. The randomness of the transmission time $t_f\left(j\right)$ is caused by the unpredictable nature of a message transfer when a choice between different drones is possible. Because the motion of the drones is also random, a message sent at a later time will travel on a different temporal network. As a consequence, ${\langle t_f\rangle }_j$ is itself also a random quantity whose probability depends on the specific realization of drone motion. The transmission time averaged over the random motion of the drones is denoted by ${\langle \langle t_f\rangle \rangle }_j$. More specifically, $\langle \langle ·\rangle \rangle$ means that an average is taken over different configurations of the adjacency matrices ${\mathbf{A}}^{\left[k\right]}$.

3. The Multiple Message Problem

So far, we have considered the transmission of a unique message over a temporal network. We shall now consider how to deal with several messages, still with the aim of computing the detection time at a target. A distinction must be drawn here between the transmission of information with or without message cloning. In the former case, a copy of the message is transferred to every drone in contact with the drone carrying the message. Therefore, the number of messages increases at every contact between carrier and non-carrier drones. In this case, we will assume that, at the initial time, a unique message is to be transmitted by a drone $d_0$. In the latter case, there is no message cloning but several messages can be sent simultaneously at the initial time; each message will perform its own random walk on the temporal network and the number of messages is constant.

3.1. Transmission with Message Cloning

In the transmission with cloning, when a drone carrying a message interacts with another drone, the latter receives a copy of the message; in this situation, the message is like a virus being transmitted in a population. Let $n_k\left(i\right)$ be the variable that specifies the state of drone i at time k: $n_k\left(i\right)=1$ if i is carrying a message (infected), otherwise $n_k\left(i\right)=0$ (healthy). We will assume that when there is contact between infected and healthy drones, the probability of message transmission is equal to one. According to the definition of the adjacency matrix, $A_{ij}^{\left[k\right]}{n}_{k-1}\left(j\right)$ is the probability that, at time k, i is in contact with an already infected drone j. Then, the probability that all drones in contact with i are healthy is:

$$H^{\left[k\right]}\left(i\right) = \prod _{j=1}^{N_d} (1 - A_{ij}^{\left[k\right]}{n}_{k-1}\left(j\right)).$$

(20)

Therefore, the drone state $n_k\left(i\right)$ is the solution of the dynamical equation

$$n_k\left(j\right) = 1 + (n_{k-1}\left(j\right)-1) H^{\left[k\right]}\left(i\right).$$

(21)

In other words, a drone is infected unless it and all its contacts are healthy. Note that $n_k\left(i\right)$ is also a cumulative probability, whose value is 0 or 1.

3.2. Transmission of Several Messages

In the transmission of several messages without cloning, N messages, belonging to the same drone at initial time, are sent over the network. Each message performs its own random walk on the temporal network; our objective is to obtain the counting statistics, also called the order statistics, for the messages reaching the target [39,40]. More specifically, we are interested in the distribution function of the arrival time of the first message among N. Order statistics have been used in wireless communication system analyses, e.g., to improve the performance of communication [41], where order statistics help to select the best transmission technique or the best multi-user scheduling technique. In this study, order statistics are used as a theoretical tool to compute multi-message transmission time statistics. For this, we assume that at the initial time, N messages are sent by the same drone $d_0$, and we record $t_i$, $i=1,\dots N$, the time of arrival of each message at the target $d_f$. Since the messages start from the same drone at the initial time, the $t_i$ values are identically distributed random variables with cumulative distribution ${\mathcal{L}}_{1j}^{\left[n\right]}$ and probability distribution ${\mathcal{G}}_{1j}^{\left[n\right]}$. Consider first $t_{1:N}$, the time for a message among N to reach the target; that is, $t_{1:N}$ is the smallest os the t_is, and it is called the 1-order statistic. $t_{1:N}$ is a random variable whose cumulative distribution function is [39]:

$$\mathrm{Pr}(t_{1:N}\le n) \equiv F_{1:N}(1,n | j,0) = 1 - {[1-{\mathcal{L}}_{1j}^{\left[n\right]} ]}^N ,$$

(22)

and its probability distribution is:

$$\begin{array}{ccc}\hfill f_{1:N}(1,n|j,0)& =& F_{1:N}(1,n | j,0)-F_{1:N}(1,n-1 | j,0)\hfill \\ & =& N {\mathcal{G}}_{1j}^{\left[n\right]} {[1-{\mathcal{L}}_{1j}^{\left[n\right]} ]}^{N-1}.\hfill \end{array}$$

(23)

Simply put, this means that for a first detection time to be equal to n, the first message must be detected at time n and the others $N-1$ must arrive later. According to Equation (22), since ${\mathcal{L}}_{1j}^{\left[n\right]}\le 1$, we find that ${\lim }_{N\to \infty }\mathrm{Pr}(t_{1:N}\le n)=1$, so that, as expected, the first detection time decreases when the number of messages sent increases. Usually, it is assumed that the path took by the fastest message is the shortest path. As we shall see later, this assumption may be incorrect in the present situation. Again, it is worth stressing that the present statistic pertains to a single realization of the drone trajectories.

A message can also be split into N messages prior to being sent. In this case, the time it takes to receive all pieces of the original message is the N-order statistic $t_{N:N}$, and its cumulative distribution is:

$$F_{N:N}(1,n | j,0) = {[{\mathcal{L}}_{1j}^{\left[n\right]} ]}^N .$$

(24)

The probability distribution for the time $t_{N:N}$ is:

$$f_{N:N}(1,n | j,0) = N {\mathcal{G}}_{1j}^{\left[n\right]} {[{\mathcal{L}}_{1j}^{\left[n\right]} ]}^{N-1}.$$

(25)

These results concerning order statistics are usually applied in static network theory, i.e., when the one-step propagator ${\mathbf{M}}^{\left[k\right]}$ is time-independent. Temporal networks and the underlying drone motion raise new questions regarding the efficiency of the network. In particular, the question here is the extent to which changes in the drone motion can result in a measurable transmission performance gain.

4. Results

The theoretical formalism detailed in the previous sections has been applied to compare, with regard to information transfer, two models of drone deployment. In the first model, the drones are allowed to fly everywhere within the boundaries of the domain $\mathcal{D}$. In the second model, each drone is confined within a sub-region inside $\mathcal{D}$; the sub-regions are arranged to form a $N_x\times N_y = N_d$ grid pattern. Hereafter, we will refer to these deployment models as the no-grid and grid models, respectively. Figure 4 displays a swarm of $N_d=16$ drones deployed according to the two deployment models. In the grid deployment, adjacent sub-regions can overlap to some extent; the parameter $l_o$ controls the overlap by fixing the width of the strip shared by two drones. We have numerically evaluated the distribution functions of different detection times by considering a swarm of $N_d=16$ drones moving with velocity $v_d=1$ in domain $\mathcal{D}$ within area $L_x\times L_y=100\times 100$. The time step chosen is $\Delta t=1$. One should note that units are arbitrary; the values chosen for the parameters can be converted, if necessary, to specific units without modifying the results of the study if the relation $L_x/v_d = 100 \Delta t$ between space and time units is maintained.

We shall assume that the information to be transmitted by the swarm is found by drone $d_0=N_d$ in the upper right corner of $\mathcal{D}$ at position $(L_x-L_x/N_x+r_c/2,L_y-L_y/N_y+r_c/2)$, which is also the position of drone $N_d$ at the initial time; all times will therefore be evaluated from that instant. The message should be transmitted to the target drone $d_t=1$, located in the lower left corner of $\mathcal{D}$ at position $(L_x/N_x-r_c/2,L_y/N_y-r_c/2)$, which is fixed. The position of the information and that of the target depend on the communication range $r_c$, to ensure that, in both types of deployment models, the sending and the target drones are able to communicate with the rest of the swarm.

At the initial time, the positions of drones $i=2,\dots ,N_d-1$, are chosen at random inside $\mathcal{D}$ or inside each drone sub-region. The scattering times $t_s\left(i\right)$ are initialized at random according to the distribution $P_{\mathrm{geom}}\left(k\right)$, given by Equation (4), with $p=v_d \Delta t/l_p=1/l_p$. Here, the persistence length $l_p$ is a parameter of the comparative study. The drones operate independently of the message transmission. At each time step, the positions $(x_i\left(t\right),y_i\left(t\right))$ are updated according to the equations of motion (2), and the total time t increases by one time step. Then, if $t=t_s\left(i\right)$, a scattering event occurs for drone i; the orientation ${\theta }_i$ is modified according to Equation (3), with a random scattering angle $0\le d{\theta }_i\le 2\pi$. In this study, the velocity scattering is chosen to be isotopic. Once scattering is performed, $t_s\left(i\right)$ is updated, i.e., $t_s\left(i\right)=t+k$, where k is a random waiting time.

A communication network is constructed on top of the drone dynamics; after each update of the drone positions, the distances $d_{ij}\left(k\right) = {({(x_i\left(k\right)-x_j\left(k\right))}^2+{(y_i\left(k\right)-y_j\left(k\right))}^2)}^{\frac{1}{2}}$ are evaluated for each pair of drones ($i,j)$, and a link is established when $d_{ij}\le r_c$, which translates into $A_{ij}^{\left[k\right]}=1$ in the network adjacency matrix. From ${\mathbf{A}}^{\left[k\right]}$, the transition matrix ${\mathbf{M}}^{\left[k\right]}$ is computed according to Equation (11), and the new n−step propagator is computed from the previous propagator using ${\mathbf{L}}^{\left[n\right]}={\mathbf{M}}^{\left[n\right]}\circ {\mathbf{L}}^{[n-1]}$. According to Equation (14), the starting point of this iteration is ${\mathbf{L}}^{\left[1\right]}={\mathbf{M}}^{\left[1\right]}$. Since we assumed the initial position of the message is drone $d_0=N_d$ and that of the target drone is $d_t=1$, the main outcome of the numerical computation is the matrix element ${\mathcal{L}}_{1N_d}^{\left[n\right]}$, giving the cumulative probability of detection at the target, that is, $\mathrm{Pr}(t_f\le n)$.

4.1. One-Message Transmission

In this section, we consider a message transmitted by a swarm of $N_d=16$ drones. The motion of the drones is characterized by a persistence length $l_p=10$, and the communication range is set to $r_c=15$. The two models of drone deployment were studied. For the grid model, we considered two values of the overlap parameter: $l_o=0$ and $l_o=10$. Figure 5 (upper panel) shows the cumulative distribution of the detection time, $P(t_f\le n)={\mathcal{L}}_{1N_d}^{\left[n\right]}$, computed for different types of drone deployment. Jumps in the cumulative distribution correspond to arrival times at the target that, via Equation (17), translate into peaks in the detection time distributions, $P(t_f=n)$, as shown in Figure 5 (bottom panel), which displays the corresponding time distribution functions. As mentioned previously, these results refer to a single configuration of the drone trajectory; each arrival time corresponds to different paths taken by the random walk of the message. When looking at the cumulative distribution, one can observe that, with respect to the no-grid situation, $t_f$ increases when the drones are confined in sub-regions and, even at time $t=$ 5000, there is a probability of $1-P(t_f\le 5000)\simeq 0.06$ that a message has not yet been detected.

Interestingly, the travel times are not evenly distributed in time but rather they tend to form groups, as can be observed in Figure 5 (bottom panel). The origin of this clustering is in the contact dynamics between drones, as highlighted in Figure 6, which shows $N_e$, the number of contacts between drones within the swarm, as a function of time. Here, $N_e\left(n\right) = \frac{1}{2}{\sum }_{i,j} A_{ij}^{\left[n\right]}$; the adjacency matrix ${\mathbf{A}}^{\left[n\right]}$ was evaluated for the three drone deployment scenarios considered in Figure 5. One can observe that the number of contacts increases with the overlap, with an average of $\langle N_e\rangle =(3.5,5.3,7.8)$ contacts per drone configuration in the swarm when $l_o=(0,10,L_x)$ (the no-grid situation is equivalent to $l_o\simeq L_x$).

The observed correlations in the number of contacts over time correspond to periods of high contact rates, followed by periods of low contact rates. These patterns of temporal interactions, called bursts, have been observed in the dynamics of many phenomena in relation to human activity and, as has been shown, are the reflection of human behavior [42]. Bursts are consequences of the way people organize their activity, prioritizing some tasks in a queuing process [42,43]. Studies suggest a general relationship between temporal network bursts and connectivity levels, with bursts often occurring alongside periods of increased interaction or information exchange within a network [44,45]. For example, network neuroscience research has documented similar burst-like activity patterns in brain networks during cognitive tasks [46]. In the swarm, periods of high activity, i.e., when interactions are numerous, originate from the displacements of drones inside the detection region of another drone. For large values of $r_c$, drones will spend more time inside the interaction region; this will increase the number of hops performed by a message, which tends to be correlated, since when drones start interacting, a message will be transferred as long as the interaction persists. Let us stress that drones evolve completely independently, which should imply that their interaction or activity, in the same way as their motion, can be modeled as a Poisson process. Therefore, the time interval between two consecutive interactions with the same drone should follow an exponential distribution. The appearance of bursts in the transmission time of a message indicates that the timing of drone interactions deviates from the Poisson model. To highlight the non-Poissonian nature of drone activity, Figure 7 (top panel) shows the temporal behavior of $N_e\left(i\right)={\sum }_j{A}_{ij}^{\left[n\right]}$, the number of interactions between a single drone i and the group. In the same figure, the waiting time, $\tau$, between two consecutive interactions is displayed. In the figure, black regions correspond to bursts, where the waiting time between successive interactions is very small, i.e., $\tau =1$. Evidence of the non-Poisson behavior of the activity is shown in Figure 7 (bottom panel), which displays the probability distribution function of the waiting time, $P\left(\tau \right)$, plotted on a logarithmic scale. The departure from the exponential distribution, which corresponds to the red line, is clearly evident for small waiting times, $\tau \le 25$, which are statistically over-represented in comparison to larger values of $\tau$, whose distribution follows an exponential. This demonstrates that correlations in the transmission time of a message are directly linked to the activity of the drones in a swarm; this activity, measured in terms of exchanges between drones, will be greater if the interaction range, $r_c$, is large.

4.2. Multiple-Message Transmission

The transmission time statistics presented in the previous section were specific to paths taken by a message in a single drone trajectory, that is, for a single realization of the temporal network and associated adjacency matrices ${\mathbf{A}}^{\left[n\right]}$. In practice, such statistics are obtained by sending several messages at the same time and by performing a statistical analysis of the ensemble of the transmission times. When messages are sent at consecutive times, each message will be transmitted via a different temporal network. In this case, the transmission times are not or poorly correlated; this will depend on the time interval between successive message sending. Therefore, the distribution of transmission times for messages sent at different times is an average distribution computed over an ensemble of distributions, each pertaining to a single drone trajectory. Figure 8 (left panel) displays the transmission time statistics measured over an ensemble of ${10}^4$ drone trajectories: $N_d=16$, $l_p=10$, and $r_c=15$. The corresponding single drone trajectory distributions are displayed in Figure 5. As a consequence of the weak correlation between drone trajectories, the transmission times of messages sent at different instants are distributed according to an exponential distribution, as shown in Figure 8 (right panel), which displays the transmission time statistics on a log scale.

Now consider the case where N copies of a message are sent at the initial time and one records the time of the first detection. As explained in Section 3.2, the first-order statistics can be computed from the one-message statistics according to Equation (23). Another situation consists of splitting the information into N pieces and sending as many messages; then, one records the time it takes to receive the N pieces of information. Also, the N-order statistics are related to the one-message statistics, as shown by Equation (25). It is important to stress that the basic assumption underpinning relations (23) and (25) is that the detection times of different messages are identically distributed; their cumulative distribution is $F_{1:1}$. Therefore, these relations are valid only for messages transmitted by the same trajectory of the drones, i.e., the same temporal network. More specifically, $〈〈F_{N:N}〉〉\ne {〈〈F_{1:1}〉〉}^N$, since in the situation considered here, the averages, 〈〈·〉〉 and $\langle ·\rangle$, do not commute.However, the order statistics averaged over different temporal networks may still be obtained from $〈〈F_{1:1}〉〉$ as:

$$〈〈F_{N:N}〉〉=〈〈F_{1:1}^N〉〉,$$

(26)

where $F_{1:1}$ is an average pertaining to different message paths in a single realization of the temporal network. To illustrate this, the trajectory-averaged one-order and N-order statistics have been computed in the case of $N=5$ messages sent simultaneously. The average was taken over $2\times {10}^4$ trajectories of $N_d=16$ drones moving in a no-grid deployment. The motion and interaction parameters are $l_p=15$, $r_c=10$. Figure 9 shows the one-order, $〈〈f_{1:5}〉〉$ (red curve), and five-order, $〈〈f_{5:5}〉〉$ (blue curve), statistics, together with the average single-message statistics, $〈〈f_{1:1}〉〉$ (black curve).

As expected, the mean transmission time $〈〈t_{1:5}〉〉$ is shifted toward smaller values with respect to the single message mean transmission time $〈〈t_{1:1}〉〉$. The respective average values are $〈〈t_{1:5}〉〉=554$ and $〈〈t_{1:1}〉〉=1290$, which agrees with the fact that when the number N of messages increases, the value of the first arrival time $t_{1:N}$ decreases. Note that in the limit $N\to \infty$, the first detection time will converge toward a value equal to that corresponding to the situation where a message is transmitted with cloning. We also point out that in a static network, in the limit $N\to \infty$, $t_{1:N}$ would give the time taken by a message to join the sending and receipting locations along the shortest path. In a time-varying network, such correspondence between the path size and transmission time is lost. Interestingly, for $t_{5:5}$, there is a clear bimodal distribution, i.e., $f_{5:5}\left(t_f\right)$ (blue curve in the figure), with two groups of arrival times. As shown in the next section, this feature can be explained by the bimodal nature of the transmission process.

4.3. Impact of Drone Motion on Communication

In order to assess the efficiency of the communication network, we will discuss the transmission of a message as a function of the factors on which it depends. Communication inside the swarm can be judged by the average time for a message to reach the target. However, in some cases, the large transmission time makes such analysis computationally expensive. To avoid such numerical complications, we computed $P_{trans}\left(n_l\right)$, the probability of a message being transmitted before time $t_l=n_l\Delta t$, whose expression is given by Equation (16). The result was averaged over different drone trajectories.

Since the motion of the drones is a persistent random walk, one can assume that a message can be transferred via two modes of transmission: ballistic motion and diffusion. A message is transmitted by directly translating a carrier drone in ballistic motion. In diffusion, message propagation occurs via hopping from drone to drone when drones are close to each other. Different factors affect these transmission modes: the persistence length of the drone motion ($l_p$), the range of the interaction between drones ($r_c$), and the way drones are deployed (grid versus no-grid).

We computed $P_{trans}\left(n_l\right)$ at time $n_l=5\times {10}^3$ as a function of the persistence length $l_p$, considering grid and no-grid deployment, for a value of the drone interaction range fixed at $r_c=10$. The result is displayed in Figure 10. As it can be observed, for all values of $l_p$, no-grid deployment (black symbols) gives better results in terms of the transmission probability than grid deployment (red symbols). It appears that, for all values of $r_c$ and all types of deployment, the transmission probability at a fixed time $P_{trans}\left(n_l\right)$, when evaluated as a function of $l_p$, can be expressed as:

$$P_{trans}\left(n_l\right) = a_0 + a_1 l_p^{-1/2}+a_{2}x l_p^{-1} .$$

(27)

As it can be observed, the data and the analytical expression (27) exhibit a good quantitative agreement. To explain this agreement, one must remember that two transmission modes contribute to the propagation of a message by drones to varying degrees; the linear motion of a carrier drone results in ballistic transportation of the message, while the hopping of a message between drones gives rise to diffusive transport. Therefore, the motion of a message is akin to a persistent random walk, whose characteristic feature is a mean-square displacement that varies as a function of the travel time according to the relationship [36,47,48]:

$$\langle r^2\left(t\right)\rangle = \frac{4 D}{\lambda } [exp(-\lambda t) + \lambda t - 1 ] ,$$

(28)

where the scattering frequency $\lambda =v_d/l_p$, and the diffusion constant $D = v_d^2/2\lambda$. For $\lambda t\ll 1$, one finds $\langle r^2\left(t\right)\rangle \sim t^2$, which corresponds to ballistic motion, while for $\lambda t\gg 1$, one finds $\langle r^2\left(t\right)\rangle \sim t$, which corresponds to diffusive transport. By the same token, the $l_p^{-1}$ and $l_p^{-1/2}$ terms in Equation (27) can, respectively, be attributed to ballistic and diffusion modes of transmission. To substantiate this argument, we consider the average time (18), now defined with an upper limit on the transmission time:

$$\langle t_f\left(n_l\right)\rangle = \sum _{n=1}^{n_l} n {\mathcal{G}}_{1j}^{\left[n\right]} ,$$

(29)

with similar expressions for $\langle t_{1:N}\left(n_l\right)\rangle$ and $\langle t_{N:N}\left(n_l\right)\rangle$. The time $\langle t_f\left(n_l\right)\rangle$ can be read as the expected time needed to reach a given transmission probability $P_{trans}\left(n_l\right)$.

The trajectory-averaged time $\langle \langle t_f\left(n_l\right)\rangle \rangle$, corresponding to the transmission probabilities shown Figure 10, that is, with $n_l=5\times {10}^3$, was computed as a function of the persistence length $l_p$, in the case of an interaction range $r_c=10$. The results are displayed in the left panel of Figure 11, together with the analytical expression (27), whose parameters have been adjusted to fit the numerical data. Once again, there is a clear difference in the transmission time between the no-grid (black symbols) and the grid (red symbols) types of deployment. On the right panel of the same figure, the travel time is shown as a function of $l_p^{-1/2}$; it appears that $\langle \langle t_f\left(n_l\right)\rangle \rangle$ increases linearly with $l_p^{-1/2}$, thus clearly highlighting that within a swarm of drones interacting within a distance $r_c=10$, the transmission of a message is mainly characterized by diffusion. However, the dominance of diffusion over ballistic motion, as the main transmission mode, is not a characteristic of the model. In fact, ballistic motion can become the main transmission mode by increasing the interaction range $r_c$, without changing the motion of the drones. To illustrate this, we repeated the computation of $\langle \langle t_f\left(n_l\right)\rangle \rangle$, with a larger value of the interaction range, i.e., $r_c=20$, and the results are displayed in Figure 12 for the two deployments considered—the color codes are the same as in Figure 11. On the left panel of the figure, $\langle \langle t_f\left(n_l\right)\rangle \rangle$ is shown as a function of the persistence length $l_p$ for the no-grid and the grid types of deployment, while on the right panel of the figure, $\langle \langle t_f\left(n_l\right)\rangle \rangle$ is shown as a function of $l_p^{-1}$. Clearly, there is a change in the transmission mode of the message, which is now mainly dominated by ballistic transport, since $〈〈t_f(n_l)〉〉\sim l_p^{-1}$. Interestingly, the interaction range also impacts the efficiency of drone deployment, since now, when $l_p\le 7$, grid deployment of the drones results in faster transmission of messages. The reason for this transition is that the range of ballistic motion is determined by the persistence length, while a message can hop over a distance similar to the interaction range $r_c$. Therefore, grid deployment, where the message is allowed to hop between sub-regions, is more efficient when the value of $l_p$ is small and, at the same time, the interaction range $r_c$ is large.

In a persistent random walk, the ballistic or diffusive nature of motion refers to the average displacement of the walker (see Equation (28)). However, in an ensemble of displacements, there are trajectories of both types, even when diffusion dominates the motion as a whole. This also applies in the situation detailed above, where the interaction range $r_c=10$ coincides with transport dominated by diffusion. Here, there are also some trajectories that are more representative of a ballistic transmission mode. Interestingly, these minority displacements can be probed by sending several messages simultaneously and then recording the transmission time of the fastest message, that is, $t_{1:N}$. We have computed the one-order statistics of the transmission time when $N=5$ messages are sent at the initial time, i.e., $〈〈t_{1:5}〉〉$, under the same conditions as those used to produce Figure 11. The result is displayed in Figure 13. In the left panel, one sees that, compared to the same panel in Figure 11, $〈〈t_{1:5}〉〉\ll 〈〈t_f〉〉$. In the right panel, the one-order transmission time shown as a function of $l_p^{-1}$ highlights the change in transmission mode, which is now dominated by ballistic motion, in clear contrast with $〈〈t_f〉〉$ shown in Figure 11 (right panel).

5. Conclusions

A theoretical framework to compute the transmission time of messages sent over a drone swarm is presented. It is shown how the first passage time formalism, developed for static networks, can be extended to tackle time-varying networks. To demonstrate the practical relevance of the theory, we compute the statistics of the transmission time of the message when transferred by drones between two locations inside a domain. Two models of drone deployment are discussed: a no-grid model, without constraints on the drone motion, and a grid model, where each drone is constrained to move within its sub-region of the domain. A comparative analysis of the efficiency of these models, assessed in terms of transmission time, has been performed according to the parameters characterizing the motion, the interaction, and the deployment of the drones. Based on the results of this analysis, we can conclude that the no-grid deployment model is the most efficient, mainly because this kind of deployment allows direct transfers of messages between two distant locations without any message exchange. Let us stress that the fast transfer of information is most often executed to the detriment of the drones’ search mission. This conclusion is supported by the fact that the fastest messages are transferred by drones moving ballistically, while slower messages are carried by drones whose motion is dominated by diffusion. Diffusion and its associated random walk are known for their efficiency in space exploration missions [49,50].

To demonstrate the link between transmission efficiency and a particular type of message motion, we computed the statistics of the transmission time in terms of the persistence length, a quantity that characterizes the motion of the drones. The results confirm this relationship and, in addition, provide a method to control the importance of the various transmission modes.

The presented results call for a more thorough analysis of the transmission time in terms of the parameters controlling the swarm, e.g., the number of drones, the ratio between the size of the domain and the interaction range, and the overlap between sub-regions. This work is focused on the transmission of messages without cloning, while the theory of transmission with cloning has been mentioned but not investigated. We must stress that these two types of message transmission are not mutually exclusive but overlap and are complementary; in transmission with message cloning, the tagging and tracing of some messages can provide a lot of information about the interaction between drones. In this respect, it should be emphasized that the theory of the transmission time detailed in this paper can be recast in terms of the numbers of hops, instead of the number of time steps.

Finally, the theory presented here should be useful to tackle more complex situations; synchronization dynamics [51], the selection of good search methods, and the control of collective behavior are particularly good examples.