Yehui SONG, Guoru DING, Jiachen SUN, Jinghua LI, Yitao XU

College of Communications Engineering, Army Engineering University of PLA, Nanjing 210007, China

KEYWORDS Dynamic topology inference;Event detection;Hawkes process;UAV swarm;Wireless networks

Abstract Wireless network is the communication foundation that supports the intelligentization of Unmanned Aerial Vehicle(UAV)swarm.The topology of UAV communication network is the key to understanding and analyzing the behavior of UAV swarm,thus supporting the further prediction of UAV operations. However, the UAV swarm network topology varies over time due to the high mobility and diversified mission requirements of UAVs. Therefore, it is important but challenging to research dynamic topology inference for tracking the topology changes of the UAV network,especially in non-cooperative manner.In this paper,we study the problem of inferring UAV swarm network topology based on external observations, and propose a dynamic topology inference method. First, we establish a sensing framework for acquiring the communication behavior of the target network over time. Then, we expand the multi-dimensional dynamic Hawkes process to model the communication event sequence in a dynamic wireless network. Finally, combining the sliding time window mechanism, the maximum weighted likelihood estimation is applied to inferring the network topology. Extensive simulation results demonstrate the effectiveness of the proposed method.

1. Introduction

1.1. Background and motivation

Relying on the advantages of strong maneuverability,low cost and wide load expansion,UAVs have been widely used in various fields.1–4With the continuous progress of control and networking technology, the development prospects of UAV swarm attract more attention.5–8However, from the perspective of management and confrontation, it is urgent to form an effective cyberspace situational awareness for UAV swarm.Network topology is an important part of cyberspace situational awareness, which affects the evolution mechanism and functional behavior of the network. It also serves as an effective means to describe the communication relationship and information interaction among nodes in the network. Therefore, mastering the topology of the UAV communication network is a prerequisite for understanding, explaining and predicting the behavior of UAV swarm.

In the field of network science, there is a typical network reconstruction problem9,10: inferring which two nodes in the network have edges according to the operating performance of the system(often reflected in time series)without the knowledge of evolutionary dynamics of the system. This issue has been specifically studied in biological networks,11financial networks,12and social networks.13In the past few years, the research on topology inference of communication networks has also drawn increasing attention, most of which assume that the targeted communication network is static. However,the topology of the UAV communication network generally changes rapidly due to factors such as mobility and task allocation needs,so the existing methods will not be very effective.In addition,the lack of cooperation between the UAV communication network and the sensor network usually limits the data sources and types used for network topology inference.These findings motivate us to study the non-cooperative dynamic topology inference problem for UAV communication network in this paper.

1.2. Related work

Different network topology inference methods have been proposed in the literature. From the data acquisition perspective,topology inference can generally be divided into two categories: cooperative topology inference and non-cooperative topology inference. The former usually obtains data by actively participating in network operation, and then realize topology inference based on specific protocol analysis14,15or network tomography.16,17The latter data is usually acquired through two types of methods:passive observation of network traffic and the violent method such as intruding into the network and decoding signals.

In this paper,non-cooperative topology inference based on passive observation of network traffic is mainly concerned. In a sense, this can be understood as an extension of spectrum sensing18,19in the application field. Some studies regard the task of network topology inference as learning the causal relationship between multiple time series. In particular, Granger causality20has a wide range of applications due to its operation simplicity. It plays a key role in analyzing the behavior and underlying mechanisms of complex systems in different fields, such as economics,21earth climate science,22neuroscience,23and so on. For communication networks, the authors in Ref.24uses Granger causality to model the response mechanism of general communication protocols,and infers the communication links of wireless networks based on the causality among the behaviors of communication entities. Furthermore, the authors in Ref.25proposes a directed link detection method based on asymmetric Granger causality for time division multiplexing communication networks. In addition,another way to measure causality is to transfer entropy.26Transfer entropy is a non-parametric statistic that measures the amount of information transfer between two random processes, and transfer entropy can be simplified to Granger causality27under the assumption of a vector autoregressive process. The authors in Ref.28model the data packet as the cause and ACKnowledgment (ACK) as the effect, and uses the transfer entropy for quantifying the strength of the automatic repeat request mechanism in the next-hop routing link to reconstruct the network structure.

On the whole, the causal inference method mentioned above is to directly detect the causal relationship between the time series data without specific timestamp information.Another way is to transform the passive observation results of network traffic into event sequences,and uses the timestamp information for statistical analysis to achieve link detection.The authors in Ref.29uses the Hawkes process to model the point process of events that can reflect the interaction of network information.Then they determine the links among nodes by mining the interaction between events, and proposes an algorithm named low cost paths for acyclic graphs to identify source/sink pairs. The authors in Ref.30conduct a more indepth study on learning network topology, topology change detection and other issues. Consistent with the use of Hawkes process modeling in Refs.29,30,the authors in Ref.31propose a cooperative topology sensing scheme with distributed sensors for more practical wireless network scenarios, and uses multi-sensor spatial diversity to deal with the randomness of the wireless channel. Recently, machine learning begins to be applied to the research of topology inference in communication wireless networks. Compared with the previous work,the authors in Refs.32,33consider the characteristics of wireless communication networks more practically, and propose a solution based on a Neural Network (NN) that uses timebased features to identify the directional data flow between nodes via binary classification. However, it should be noted that the premise of this method is based on the existing data set, thus the actual application may be limited.

Additionally, the authors in Ref.34improves the densitybased spatial clustering method to realize communication relationship mining. This work achieves the identification of the communication relationship between the communication entities through clustering analysis of the frequency hopping period, signal power and signal appearance time and other characteristics. Ref.35proposes a method based on the association rule of signals to infer the communication relationship between interference sources. The authors in Ref.36infer the connectivity based on the distance between nodes: if the distance between two nodes is less than the critical transmission distance, it is considered that there is a physical link between the two nodes. However, in reality, the existence of a physical link between two nodes does not necessarily mean that the two nodes will use the link for information transfer,so the location information does not faithfully reflect the network communication structure in the current communication state.Structural Equation Modeling (SEM) is also often used to identify the connectivity of directed graphs. Under the framework of SEM,the work in Ref.37proposes a directed network topology inference method based on tensor decomposition. To track dynamic network, the framework is further extended to facilitate the real-time sequence estimation of the network topology,and the exponentially weighted least squares estimator is introduced to the topology tracking algorithm.

The authors in Ref.38research the dynamic topology inference problem in the multi-robot formation control system and propose a novel Dynamic Window Least Square algorithm(DWLS) to identify dynamic changing topology. For the dynamic changes of power network topologies, the authors in Ref.39propose a dynamic topology awareness method based on limited measurement, that is, using the statistical inference model that considering non-Gaussian noise to capture the perturbations of the voltage amplitude covariance matrix. The authors in Ref.40study the problem of dynamic diffusion network extraction in online media.They use the Hidden Markov Model (HMM) to discover the most probable diffusion links based on the current observation of the diffusion process of online media. The authors in Ref.41believes that the ‘‘social signals” generated by social networks implicitly depend on the underlying topology,and these topologies usually‘‘jumps”between discrete states.Based on this understanding,they propose a switched dynamic structural equation model to capture topology-dependent cascading evolution, and develops a recursive two-step topology tracking algorithm to track the state and topology of the network.

Notably, most of the existing studies on wireless network topology inference assume that the topology is static, where the time-varying nature of some networks has not been considered in the literature.

1.3. Contributions and organization

In this work, we mainly consider the dynamics of the UAV swarm network topology and study the inference and tracking of the dynamic topology.

The main contributions of this paper are summarized as follows:

(1) We propose a sensing framework for externally acquiring the communication behavior of the noncooperative UAV swarm network over time. Therefore,our inference method is only based on these behaviors without prior knowledge about the wireless network,such as specific communication protocol, modulation and demodulation mode, etc.

(2) A dynamic topology inference problem is formulated for UAV swarm network. To address it, we expand the multi-dimensional dynamic Hawkes process to model the communication event sequence, and propose a dynamic topology inference method combining the mechanism of sliding time window and the maximum weighted likelihood estimation.

(3) We propose a dynamic threshold selection method for topology decision-making, which can be effectively applied to time-varying topology scenarios.Our analysis considers factors such as the topology change rate of the target UAV network, the sensing error rate (including signal detection error and UAV recognition error) and the number of sliding windows, etc.

The rest of this paper is organized as follows.System overview and problem formulation are given in Section 2,while the dynamic topology inference method is illustrated in Section 3.Section 4 presents the corroborating numerical results.Finally,Section 5 draws conclusions and a discussion of future directions.

Notation. Uppercase italic boldface letters represent matrices,lowercase italic boldface letters represent vectors,bold curlicue letters represent tensors, while ‖.‖pdenotes ?p-norm.

2. System model and problem formulation

In this section, we first describe the system model, then introduce the relevant theories, and further formulate the problem of topology inference.

2.1. System model

For presentation simplicity, in the following sections, the target network refers to the UAV swarm, and nodes are UAVs with the omnidirectional antenna and same transmission power,and the transmission of a signal is expressed as a communication event. In addition, it demands that the communication network must ensure stable and reliable information interaction, so it can be assumed that the packet loss rate between UAVs is low.

The existing network topology inference methods25,28,31,33are generally based on the logic: the signal transmission of a node is likely to induce a response at its intended receiver after a fixed but unknown delay,such as respond in the form of confirmation or forwarding. Examples of such networks include Carrier Sense Multiple Access with Collision Avoidance(CSMA/CA)protocol,Automatic Repeat reQuest(ARQ)protocol, or 802.11 family of protocols, and so on. Similarly, we will work on the basis of similar logic, so we assume that the communication behavior of the UAVs will be responded to by the potential node in its neighbors.

If time variation is not considered, the target network containing U nodes can be modeled as a directed graph G（V，E),with its topology captured by the associated adjacency matrix A ?RU×U.V represents the node set and E represents the edge set.If the information flows from node j to node i,then we set the entry aijin A to 1,otherwise,set it to 0.When the strength of the connection between nodes is considered,the topology of the target network can be represented by a weighted adjacency matrix W, and wijcan also be used to represent the entry （i，j )of W.The larger wijis,the more frequently the link is used,and the busier the traffic would be. To extend the time-varying property of the directed graph,the target network can be modeled as G（V，E，t). Similarly, its topology at time t can be represented by an unknown adjacency matrix At?RU×U.

Fig. 1 shows a sensing system and a target UAV network containing U nodes. After the target network enters the range of interest, the sensing system will continuously monitor its communication behavior. The sensing system consists of multiple distributed sensors and a fusion center (in the following,the sensing system is divided into two modules:sensing module and inference module according to the performance). Now,assuming that the sensing system has the following functions:

(1) Identify each node as a unique ID and track the nodes,which can be achieved through technologies such as UAV detection,42,43location,44and emitter identification.45

(2) Achieve effective energy detection.31

(3) Blind source separation46–48and measure correlation(shown in Ref.33for details).

Fig. 1 Scenario diagram of UAV swarm network and sensing system.

Fig. 2 Framework for selecting event sequence.

2.2. Hawkes process

2.3. Problem formulation

At present, most of the existing related works are run in batch offline mode, and the materials used for inference are all historical data sensed over a period of time. But in fact,the communication behavior data about the UAV swarm is obtained by the sensing system in a stream. It is also important that the topology of UAV swarm will evolve over time:new links may appear or original links may be disconnected during the observation period. Therefore, the topology inferred by the batch processing method can only represent a single aggregate perspective of the evolving network topologies in a certain period of time. Therefore, in this section, we propose a dynamic topology inference problem for UAV swarm networks.

As mentioned in Section 2.1, we can see that the sensing system periodically collects and processes event sequences.Given a static target network G（V，E)with a constant link relationship aij, the sensing system can obtain the network’s communication behavior event sequence externally over time during the observation interval （0，T], then the network inference problem can be simplified to the maximum likelihood estimation problem of the event sequence29–31:

Now, we extend this network inference problem to the target dynamic network G（V，E，t) with a time-varying link relationship aij（t ). For this purpose, at any given time t, we should implement dynamic topology inference by the maximum weighted likelihood estimation55,56:

3. Dynamic network topology inference

3.1. Dynamic network with piecewise-stable topologies

As mentioned in Section 2.3, we assume that the topology of the target network exhibits segmental-constant characteristics.In order to facilitate the modeling and expression, when

Fig. 3 Schematic diagram of tracking topology over time:Example at current moment ˙tm.

3.2. Maximum weighted likelihood estimation

First,following two modes are considered.The first is the Full Input Mode(FIM):the sensing module continuously perceives the communication behaviors of the target network over time,and inputs all received event data to the inference module for topology inference at the current moment. The second is the Single Window Mode (SWM): the inference module only uses the event sequence in the current sensing window for topology inference at the current moment.

Combining these two modes, we naturally think of using the sliding window mechanism to process historical data with trade-offs,and weighting the data in the sliding windows at the same time.Therefore,the dynamic topology inference problem will be equivalent to the maximum weighted likelihood estimation problem.

Fig. 4 Dynamic network with piecewise-stable topologies: An example of a UAV network containing three drones.

3.3. Binary decision

Fig.5 Schematic diagram of weighting under the sliding window mechanism.

For the estimated weighted adjacency matrix,it is necessary to make a decision to obtain a binary topological representation.Previous work is generally based on a fixed global threshold strategy. If the value estimated is greater than the threshold,it is determined that the corresponding link exists, and vice versa. However, in dynamic scenarios, a dynamic threshold selection scheme is needed to consider.

Normalizing the weighted adjacency matrix is helpful for us to compare and process on the same order of magnitude. In this paper, each weighted likelihood function is solved independently, so we can consider row normalization processing on the weighted adjacency matrix:

The dynamic topology inference algorithm is summarized in Algorithm 1. The main components of the algorithm are:maximum weighted likelihood estimation (lines 3–7), parameter initialization for the next estimation (line 8), binary decision (lines 9–14), tensor output (line 16).

Algorithm 1. Dynamic topology inference algorithm Input:Number of nodes in the target network,U;Event Sequence of the target network, SM; Number of sliding windows, Nsw;Length of the window, L; Penalty weight, ps （m ); Dynamic threshold for binarization, α（m )Output: Tensor containing inferenced topologies, ︿Am 1. Initialize μ, W, α.2. for m=1，2，...，M do 3. if m ≤Nsw then 4. Estimate w^um, ^μum via Eq. (14), for u=1，2，...，U 5. else 6. Estimate w^um, ^μum via Eq. (15), for u=1，2，...，U 7. end if 8. Initialize μ= ^μum■ ■, for u=1，2，...，U 9. (A) Normalization:■ ■, W= w^um

10. Calculation w～um via Eq. (16), for u=1，2，...，U 11. (B) Binary decision:12. Calculation α（m ) via Eq. (17)13. wij （m )=1 if wij （m )>α（m )14. otherwise wij （m )=0, ?（i，j )15. Update ︿Am = ～Wm 16. Return ︿Am = ︿Ak{ }m k=1 17. end for

4. Simulation and discussion

In order to evaluate the effectiveness of the proposed method in dynamic network scenarios, this section introduces the test results on simulated data and discusses the impact of various parameter configurations.

4.1. Simulation preparation

4.2. Performance comparison

This paper uses the following two indicators to evaluate the performance of the algorithm. It should be noted that the following results are the average of multiple Monte Carlo simulations.

(1) Accuracy. The identification accuracy rates of link and non-link are respectively defined as:where the operator ‖.‖0represents the number of non-zero items of its parameter,TPmrepresents the number of correctly identified links at ˙nm, and FPmrepresents the number of correctly identified non-links at ˙nm.

(2) Edge Identification Error Rate (EIER).37In order to comprehensively evaluate the identification performance and exclude the influence of link sparsity on performance display,EIER is defined as follows:

The greater EIER, the lower the identification accuracy rate.

4.3. Results and analysis

This section mainly simulates the proposed Dynamic Topology Inference algorithm (DTI), and methods added into comparison are FIM and SWM. FIM realizes topology inference with all received event data at the current moment, while SWM only uses the event sequence in the current sensing window for topology inference at the current moment.

Regardless of the signal detection error rate and node recognition error rate for the time being,an intuitive visual display of the inference effect of DTI is shown in Fig. 6 and Fig.7.They are both heat maps depicting the actual adjacency matrix and the inferred weighted adjacency matrix at different times.The difference is that Fig.6 is derived under the smooth pattern,while Fig.7 is derived under the abrupt pattern.In the heat map,the horizontal axis represents the source node index,the vertical axis represents the destination node index,and the value in the grid represents the strength of the directed link between the corresponding nodes. The larger the value is, the greater the link strength will be. Correspondingly, the closer the color in the grid is to yellow (bright), the stronger the link strength of the corresponding directed link, and vice versa,while the blue represents that the corresponding link does not exist.

(1) When the topology keeps unchanged for a long time,FIM has the best inference effect over the time (see Fig. 7(b)), because FIM fully utilizes all the valid data obtained during this period.Meanwhile,this feature also causes that when the topology changes over time,FIM is still insensitive to the timeliness of the data, resulting in a sharp drop in the inference performance (see Fig. 6(f)and Fig. 7(f)).

Fig. 6 A visualization example in smooth pattern.

Fig. 7 A visualization example in abrupt pattern.

(2) Compared with FIM, SWM show more robustness in dynamic topology scenarios(see Fig.7(g)),but its weakness is that it only uses the data of the most recent sensing window and gives up the potential of historical data.This shortcoming renders SWM’s inference performance more sensitive to the size of the sensing window and window and the rate of change of the target network topology.As shown in Fig.6(c),the inference result by SWM is not enough stable under such circumstance.

(3) Through comprehensive comparison, DTI can not only better adapt to dynamic topology scenarios, but also effectively utilize historical data. This strength enables DTI to reduce the background noise so as to drop the false alarm rate.

Fig. 8 Performance comparison in smooth pattern.

Fig. 9 Performance comparison in abrupt pattern.

The simulation environments of Fig. 8 and Fig. 9 are the same as that of Fig. 6 and Fig. 7, respectively, and the results are all average values obtained from repeated experiments for 100 times.It can be seen from Fig.8 that except for SWM,the performance of FIM and DTI both has obvious periodic oscillation characteristics. This is because that once the topology begins to change, the amount of new samples is not enough to support the inference of the new topology,while the historical data still confuses the audience to a certain extent.And the sensing period is smaller than the actual change period of the topology in the simulation, when the topology is stable, inference performance will be improved with more data collected over time. EIER of FIM decreases first and then increases.This is caused by that the target network topology is sparse.Then, even if the topology changes, the improvement of NLR in the first period of time still comes from the increase of sample size. As time goes on, the performance of FIM will continue to deteriorate on the whole. However, the performance of DTI will basically maintain a relatively stable state,which is significantly better than SWM. This is because that SWM has too few samples available for inference and lacks information mining on historical data. Further, Fig. 9 can be understood as a detailed display of Fig. 8. Combining Fig. 8 and Fig.9,we can find the characteristics of the three methods:FIM lacks sensitivity to the timeliness of events,and the result of inference will be a snapshot of the global topology in the entire observation interval;SWM only relies on the latest samples, performance of which will be greatly limited by the sample size; DTI is a relatively compromise method that not only highlights the importance of sample timeliness,but also makes use of historical data.

The following compares the performance of the proposed algorithm under different parameters.The simulation environment is in smooth pattern,and other common parameters are:Tw=6250Ts, M=400, Tacm =25000Ts， ?m, U=25 and the number of repeated experiments is 100. It can be seen from all the simulation diagrams that the variance of the obtained EIER is relatively small in different simulation environments.Therefore, the inference performance is relatively stable, and it has high robustness.

(1)The impact of topology change rate ρ.Fig.10 shows the impact of topology change rate on inference performance,where Figs. 10(a) and 10(c) use the fixed threshold decision method, and Figs. 10(b) and 10(d) use the proposed dynamic threshold decision method. The range of ρ is from 0.05 to 0.45,and the step size is 0.2.This simulation does not consider the influence of the sensing error rate, and Nsw=4.

As ρ increases, EIER of Fig. 10(a) shows a very small downward trend, while EIER of Fig. 10(b) goes up significantly. Besides, compared with Fig. 10(a), the oscillation amplitude of EIER shown in Fig. 10(b) has a more obvious tendency to become larger as ρ. These show that the dynamic threshold scheme is more sensitive to ρ. The larger ρ means that the algorithm requires more time-sensitive samples, once the data is not updated in time, EIER will rise sharply. However, it needs to be pointed out that the EIER under the dynamic threshold scheme is still far lower than that under the fixed threshold scheme, so the fixed threshold method is not suitable for time-varying scenarios. Compared with Figs. 10(a) and 10(b), Figs. 10(c) and 10(d) add the display of variance. It can be seen that the variance of EIER has no obvious change in the time domain or the parameter domain, and the value keeps small, which can show that DTI is robust.

(2) The impact of sensing error rates σ1, σ2. Fig. 11 shows the impact of sensing error rates on inference,mainly concerning signal detection error rate σ1and node recognition error rate σ2.During this simulation,we consider influences of these two parameters separately. σ1and σ2both range from 0.05 to 0.45,and the step size is 0.1.In addition,ρ=0.2 and Nsw=4.

Fig. 10 EIER for different topology change rates ρ.

Fig. 11 EIER for different the signal detection error rates σ1 and node recognition error rates σ2.

Fig. 12 EIER for different numbers of sliding windows Nsw.

As shown in Figs. 11(a) and 11(b), when σ2=0, EIER keeps rising with the increase of σ1.Figs.11(c)and 11(d)both show:when σ1=0,with the increase of σ2,EIER will also goes up. By comparing Figs. 11(a) and 11(c), it can be found that inference performance is more sensitive to σ2than σ1.

(3) The impact of the number of sliding windows Nsw.Fig. 12 shows the influence of the number of sliding windows on inference. The range of Nswis [1，7 ], with a step size of 2.when Nsw=1,DTI can be seen as SWM.The simulation does not consider the influence of the sensing error rate, setting ρ=0.2.

As shown in Figs.12(a)and 12(b),DTI shows a better performance than SWM.It can be seen from Fig.12(a)that with the growth of Nswfrom 3 to 7, EIER will roughly decrease from 0.20 to 0.15. Under the dynamic threshold scheme, the impact of Nswon EIER is not evident. Then, EIER grows in a cyclical manner, but it still stabilizes at 0.04 in the end.

5. Conclusions and outlook

In this paper, we investigate the dynamic topology inference problem in the UAV swarm scenario. Firstly, we propose a sensing framework for acquiring communication behaviors of the target network over time. Then, we expand the multidimensional dynamic Hawkes process to model the communication event sequence.Finally,combining the sliding time window mechanism,we transform the dynamic topology inference problem to that of the maximum weighted likelihood estimation. In addition, the accuracy and EIER are used to evaluate the performance of the proposed algorithm. Simulation shows that the dynamic inference method proposed can more effectively realize the tracking of the UAV swarm network topology. Although it may be affected by the performance of various prerequisite technologies, it still has a certain degree of robustness and relatively high dynamic inference ability.

The dynamic topology inference problem in the UAV swarm scenario is still extremely challenging, and our work is only a small step forward in this direction.There are several interesting research directions:

(1) Adaptive weight design. The weight selection in our work is still relatively fixed and rigid, lacking flexibility.Facing more complex dynamic scenes, the maximum weighted likelihood estimation may have a greater advantage in choosing adaptive weights.

(2) Data set establishment. Almost all existing works are based on simulation data,and there is a lack of a reliable actual data set. It is extremely difficult to design and obtain the data set for UAV swarm topology inference,but it has great practical significance for promoting the development of this direction.

(3) Dynamic topology data mining. How to mine the key information hidden in the dynamic topology inferred is a ponderable direction, which will help us to deepen the dynamic characterization and protocol design of the UAV swarm network.

Declaration of Competing Interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Nos. U20B2038, 61871398, 61901520 and 61931011), and the Natural Science Foundation for Distinguished Young Scholars of Jiangsu Province, China(No. BK20190030).