{'fraction_non_alphanumeric': 0.03135711284580173, 'fraction_numerical': 0.009619424603613366, 'mean_word_length': 4.404158699808796, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 2, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Wireless Networks' Topologies Using Asymmetric Granger Causality

Sharing spectrum with a communicating incumbent user (IU) network requires avoiding interference to IU receivers. But since receivers are passive when in the receive mode and cannot be detected, the network topology can be used to predict the potential receivers of a currently active transmitter. For this purpose, this paper proposes a method to detect the directed links between IUs of time multiplexing communication networks from their transmission start and end times. It models the response mechanism of commonly used communication protocols using Granger causality: the probability of an IU starting a transmission after another IU's transmission ends increases if the former is a receiver of the latter. This paper proposes a non-parametric test statistic for detecting such behavior. To help differentiate between a response and the opportunistic access of available spectrum, the same test statistic is used to estimate the response time of each link. The causal structure of the response is studied through a discrete time Markov chain that abstracts the IUs' medium access protocol and focuses on the response time and response probability of 2 IUs. Through NS-3 simulations, it is shown that the proposed algorithm outperforms existing methods in accurately learning the topologies of infrastructure-based networks and that it can infer the directed data flow in ad hoc networks with finer time resolution than an existing method.


I. INTRODUCTION
Consider the scenario where a cognitive network is sharing spectrum with one or more incumbent networks. Spectrum sharing by opportunistic spectrum access requires that the cognitive network avoid interference to the receivers in the incumbent networks. At present, there is extensive work on the detection of transmitters in the field of spectrum sensing [1] but significantly less on identifying receivers. In particular, existing methods for coexistence in TV white space [2] and the Spectrum Access System (SAS) of the Citizen's Broadband Radio Service (CBRS) [3] detect transmissions and enforce a protection region around the transmitters where CRs are not allowed to transmit. The size of this protection region is designed such that the CRs outside the protection region do not cause harmful interference to any incumbent receivers located on the border of the incumbent transmitter's service area. On the other hand, if we can identify the potential receivers, we can enforce a smaller protection region around the receivers rather than the transmitters.
Identifying the current receivers in a network of communicating IUs is difficult because receivers are inherently The authors are with the Department of Electrical Engineering, University of California, Los Angeles (UCLA), Los Angeles CA 90095 (email: mvlaghate@ucla.edu, danijela@ee.ucla.edu).
This work has been supported by the National Science Foundation under grant 1527026. passive when they are in receiving mode and because it is costly for the cognitive network to decode the packets in the incumbent network. Instead, we can use the IUs' network topology to identify the potential receivers of currently active transmitters. This observation motivates us to learn the IUs' network topology, i.e., the directed links between IUs. Similar to existing work, we will focus on learning the network topology of time multiplexing incumbent networks.

A. Existing Work
In literature, the temporal patterns in IU transmissions have been used to learn network topology. The features used include transmission start and end times, frame durations, and interarrival times. We shall base our work on a similar input. As has been shown in [4], we do not need prior knowledge of the IUs' communication protocols to distinguish IUs and detect the transmission activities of each IU. Hence, we do not require knowledge of the IUs' communication protocol to obtain these inputs. Note that the location of the IUs is not useful in learning their network topology because the networks need not be geographically separated.
One set of existing methods to learn network topology are based on the causal nature of time multiplexing communication protocols: A transmission by an IU is likely to cause a response, say in the form of an acknowledgement, by its intended receiver after a fixed but unknown delay. Examples of such networks include the 802.11 family of protocols, Bluetooth, and TDD-LTE. Fig. 1 shows an example of the transmit-response pairs in activity sequences of 802.11n networks simulated in NS-3. Using this observation, [5], [6] model the responses as a causal structure in the IUs' transmission activity time series. They propose methods to identify pairs of communicating IUs by detecting IUs that have a higher probability of transmitting after another. This paper is also based on the same idea.
Another approach to this problem recognizes that the directed links in an ad hoc network correspond to the end-to-end routes and learns those routes directly [7]. The authors propose an algorithm that clusters IUs that have similar distributions of packet lengths and inter-arrival times to infer that these IUs participate in the same data flow. Since they do not infer the ordering of the IUs in the route, we need additional information, e.g., locations, to identify potential receivers of each IU along the route. Their method also requires the network to have the same data rates on all links. In addition, in infrastructure-based networks, receiving IUs typically do not repeat the transmission and are unlikely to have the same packet lengths as the transmitting IU.

B. Challenges and Contributions
The primary challenge with using causality to detect responses is that if two IUs are not communicating with each other but are located close enough to interfere with each other, then their collision avoidance mechanisms will ensure that their transmission activities are not independent. This implies that, unlike typical Granger causality literature, the causality between two IUs is non-zero even if they are not communicating with each other.
The second challenge is the time varying nature of network topology: the inferences of our algorithm are only useful if they are valid for some period of time. We will show that the proposed algorithm learns network topology in the order of 100ms. Since network topology does not change that frequently, cognitive radios can use the learned topology for making inferences for some period of time in the future.
Thirdly, it can be argued that inferences on the entire network should be made simultaneously through a multivariate method (such as graphical LASSO) since there will be multiple causal relationships in the incumbent network. Instead, we will use a common feature of communication protocols to argue that testing each pair of IUs independently is sufficient for learning the network topology rather than making an inference for the entire network simultaneously. Note that [5] also tests pairs of IUs independently.
To help ensure that we detect responses, we choose to detect the causality from the transmission end times of transmitter IU to the transmission start times of the receiver IU. Hence, we propose a binary hypothesis test for each ordered pair of IUs based on the asymmetric form of Granger causality as compared to the symmetric form used in [5], [6]. For this test, we propose a non-parametric test statistic that does not assume a linear model between the transmission start and end times of the pair of IUs being tested.
Since such a test may confuse frequent opportunistic spectrum access as responses, we study the response time in existing time multiplexing communication protocols to note that the response time is shorter than the idle time and is required to be roughly constant. Based on these observations and verification from NS-3 simulations, we propose an algorithm to estimate the response time from the same test statistic mentioned above. We call the combination of the test statistic and this estimation algorithm as the Asymmetric Transfer Entropy to Learn Network Topology (ATELNeT) algorithm.
To study the effects of dependent transmission activities, we propose a Markov chain model that abstracts the IUs' medium access protocol and focuses on the response time and retransmission times of a pair of IUs. From this model, we verify that the response time will be estimated correctly and show that both false alarm as well as detection probability increase as the frames become shorter and more frequent.
The rest of this paper is organized as follows. Section II describes our system model and assumptions. Section III defines Granger causality, relates different tests from literature to existing work on topology learning, and proposes a nonparametric test statistic for asymmetric Granger causality. Section IV motivates and proposes our ATELNeT algorithm. The Markov chain model for 2 IUs is discussed in Section V. NS-3 simulations of infrastructure-based and ad hoc networks are presented in Section VI. The paper is concluded in Section VII.

II. SYSTEM MODEL
We consider a scenario with M IUs indexed as 1, . . . , M. We assume that these IUs have been identified by a system such as that proposed in [4], by decoding physical layer headers, localization, or fingerprinting their radios. In addition, we assume that this system provides a time sequence of the activity of each IU, sampled periodically at T s intervals, such that the activity of the m'th IU is denoted by a m [t] = 1 if it is transmitting at time tT s and 0 otherwise. For the purpose of this work, we shall assume that these sequences are error-free and that each sequence is of length N samples.
We denote the pair-wise links between these IUs by a binary matrix L ∈ {0, 1} M×M such that L i, j = 1 if there is a link from IU i to IU j.
For a time series X[t] and positive integer τ, we use We use 1 { · } to denote an indicator variable. For developing our algorithm, we will denote the sampled time series of transmission start time indicators of the i'th IU by . We denote the sampled indicator time series of the end of transmissions of the i'th IU by

A. Assumptions about IUs' Medium Access Protocol
We define a transmit-receive link by the receiver's act of responding to a signal by the transmitter. Consider a link from IU i to IU j. Assuming a half duplex communication link, the receiver j has to wait for the transmitter i to finish transmitting before j can respond. Thus, the end of a transmission by IU i causes the start of a transmission by IU j after a short time interval. We call this time interval as the response time or causal lag and denote it by τ i, j . It consists of both processing times as well as hardware delays such as the Rxto-Tx turnaround time. For example, this is defined in the IEEE 802.11 standard [8, §10.3.7] as the Short Inter-Frame Space (SIFS) which is computed as aSIFSTime = aRxPHYDelay + aMACProcessingDelay + aRxTxTurnaroundTime.
Similarly, LTE-TDD has a fixed length guard period between downlink and uplink pilots as part of a special subframe [9, §4.2]. Bluetooth [10] has a fixed interframe space T_IFS between every Master to Slave and Slave to Master transmission. Finally, each of these standards define a maximum allowed variation in the response time. It is to be expected that such a response time will feature in future time division multiplexing communication protocols. Hence, we incorporate the response time in our system model and say that there where τ i, j is the response time of that link. Note that we do not mean to assume that j transmits a response to every transmission by i, but if j does respond to i's transmission, then it will do so τ i, j time after i's transmission ends. We also assume that the variation in response times on a link is significantly smaller than T s . Our second assumption is that the time interval between two successive transmissions by an IU is longer than the response time for any link originating from that IU. Mathematically, This assumption is based on the fact that communication protocols are designed to avoid interference to the response. For example, the 802.11 standard specifically sets the NAV field to include the acknowledgement frame's duration [8].
Finally, we assume that we know an upper bound τ max on τ i, j for all i, j ∈ {1, . . . , M } such that i → j.

III. GRANGER CAUSALITY
Similar to existing work, we are going to base our work on the idea of Granger causality. In this section, we briefly introduce the concept, theoretical models, and tests used in existing literature. We relate these methods to the existing works on learning network topology and then propose a new test statistic for testing asymmetric Granger causality.
The concept of Granger causality was first proposed for macroeconomic analysis [11]. As defined in [11], a time series and Y (∞) [t] has lower error than the MMSE estimator of The causal lag defined in [11] corresponds to the sampled response time τ ·, · in our system model. Since the causal lag is unknown, it is usually estimated from the input data by either the Akaike Information Criterion (AIC) or Bayesian Information Criterion (BIC) [13]. Thus, the problem of testing Granger causality between a pair of time series X and Y is a binary hypothesis problem where the null hypothesis (H 0 ) is that X does not Granger cause Y .

A. Models and Tests
Most methods in literature for testing Granger causality are based on regression but are modified with domain knowledge specific to the problem under consideration [13]. Specifically, a causal link from X[t] to Y [t] is modeled as a vector autoregressive model such as [11], [13] where α 1,τ and β 1,τ are the parameters of the regression and ξ 1 [t] is the residual noise. Similarly, the null hypothesis is modeled as with β 0,τ being the regression parameters and ξ 0 [t] the residual noise. Therefore, the null hypothesis is modeled by the coefficients α 1,τ in this model being zero.
In [5], the authors use this linear model for testing causality between every pair of IUs on disjoint observation windows. Their hard fusion algorithm then fuses the topologies learned in each window using the majority rule. For individual windows, the hard fusion algorithm proposed in [5] uses the test statistic have zero mean Gaussian distributions and equal variances. The threshold is chosen using (4) to satisfy a given false alarm probability. In their soft fusion algorithm, the authors compute the average causality magnitude [14] of a link for each window. The network topology is inferred as those links with average causality magnitude greater than the average of all pairs of IUs. Transmission start times have been considered as continuous time point processes and modeled as multivariate Hawkes processes in [6]. In the Hawkes process model, an event in one time series increases the probability of an event occurring on other time series for a short period of time. The support of these impact functions were recently shown to be equivalent to Granger causality [15]. There is a rich body of literature learning Hawkes point processes and might be useful for learning Granger causality in multivariate systems as done in [16]. With respect to our system model, we are using sampled activity sequences as input and not point processes.
Finally, an information theoretic non-parametric test for Granger causality has been proposed in [17]. The author of [17] proposed the conditional mutual information of as a test statistic called transfer entropy for testing whether The author proposes a binary hypothesis test with T X→Y = 0 as the null hypothesis for no causality and T X→Y > 0 as the alternate hypothesis denoting a causal relationship. We shall base our proposed method on a similar test statistic described below.

B. Asymmetric Granger Causality
In this work, we are going to use an asymmetric form of Granger causality loosely based on that proposed in [18] in this definition. Thus, we can think of X[t] and Y 1 [t] as events representing potential causes while Y 2 [t] denotes the events representing effects.
Here, Y 1 [t] and Y 2 [t] typically describe different events on an underlying common sequence while X[t] describes events on a second time sequence. For example, in our proposed algorithm, Y 1 [t] and Y 2 [t] will correspond to the end and start transmission events respectively of one IU while X[t] will denote the end transmission events of another IU.
Similar to Granger causality, we use a finite history τ while testing asymmetric Granger causality. We propose an asymmetric transfer entropy as our test statistic where the summation is over all values taken by The test statistic shall compare between the same hypotheses as described above for [17]. The motivation and use of this test statistic for learning network topology is described in the next section.

IV. PROPOSED METHOD: ASYMMETRIC TRANSFER ENTROPY TO LEARN NETWORK TOPOLOGY (ATELNET)
In this section, we will be proposing a test for detecting causal links between ordered pairs of IUs at a time. In general, 1 [18] separates events occurring on the time series as we do, but tests for conventional Granger causality between the generated time series. We propose incorporating a third time series to model a common cause for both hypotheses it is true that there may be a performance benefit in detecting all links simultaneously through a multivariate test. However, as mentioned earlier in Section II-A, communicating protocols are usually designed to avoid interfering with the response of the receiver. Hence, by focusing on the response time of each link, we expect that other IUs' transmissions will not interfere with the testing of a given link. Hence, we also propose a method for estimating the response time from the test statistic. We will also be proposing an additional linear regression based test similar to that of [5] for comparing the performance gain from the choice of nonlinear model against the linear model.

A. Proposed Test Statistic for Transmit-Receive Pair
As mentioned above, we propose testing every ordered pair i, j of IUs independently. Similar to [17], we consider two hypotheses: the null hypothesis H 0 (i, j) represents i j and the alternate hypothesis H 1 (i, j) represents i → j. To specifically detect the responses transmitted by IU j to transmissions of IU i, we test whether Fig. 2 shows the inputs that we use for testing this asymmetric causality. Since there is no reason to assume a linear model for E i [t], E j [t], and S j [t], we use the nonparametric asymmetric transfer entropy (7) that we proposed in Section III-B:Â is a threshold that depends on the response time. The response timeτ i, j will need to be estimated from the data and the threshold λ( · ) will be computed from the distribution ofÂ E i →S j |E j as described next. We derive the asymptotic distribution ofÂ E i →S j |E j in Appendix A. Our derivation is similar to that of the asymptotic distribution ofT X→Y in [19]. We show that for large N and a given causal lag τ, 2(N − τ)Â E i →S j |E j (N, τ) has distribution χ 2 d i, j under the null hypothesis H 0 (i, j) and distribution is a non-central χ 2 distribution with d degrees of freedom and non-centrality parameter c. Causal Lag τ No link, 15m apart No link, 48m apart We choose the threshold λ(τ) such that the probability of false alarm is asymptotically bounded above by a parameter P FA : where χ −2 d ( · ) is the inverse cumulative distribution function of a central χ 2 random variable with d degrees of freedom.
Note that we have assumed that A E i →S j |E j (τ) = 0 under the null hypothesis. Though this is a common hypothesis in the Granger causality literature as well as [5], [6], we will show below that Since this value is unknown a priori, we choose A E i →S j |E j (τ) = 0 to define the null hypothesis. Fortunately, both the model analyzed in Section V and simulations in Section VI show that A E i →S j |E j (τ) is sufficiently small that we can still use this typical null hypothesis of A E i →S j |E j (τ) = 0.
Next, we need to estimate the degrees of freedom d i, j . As per the derivation in Appendix A, d i, j is the difference in the number of parameters for models under the alternate hypothesis H 1 (i, j) and the null hypothesis , the number of parameters in either model is simply the number of independent values in the appropriate joint probability mass function. Next, our assumption that the retransmission time is longer than the response time Hence, the number of parameters under null hypothesis iŝ τ i, j + 1 and under the alternate hypothesis is (τ i, j + 1) 2 . Hence, the degrees of freedom are

B. Proposed Algorithm to Estimate Response Time of a Link
Estimating the response timeτ i, j depends on its invariance. In particular, if the variance in response time is significantly smaller than the sampling time of the link, then the response is likely to be received at either τ i, j or τ i, j +1 with high probability. Hence, A E i →S j |E j (τ i, j ) will be significantly higher than . This intuition will be revisited analytically in Section V. From NS-3 data of 3 pairs of 802.11n IUs, Fig. 3 Algorithm 1 Estimating response time for link i → j after SIFS of 16µs, if there is a link but not if the pair do not have a link. For the pair of IUs that do not have a link but are close to each other, Fig. 3

also shows a slight increase in
at the lags after the minimum retransmission time, i.e., after DIFS of 34µs.
Based on this discussion, we estimateτ i, j such that for a parameter α > 1. Pseudocode for estimatingτ i, j is provided in Algorithm 1. Starting from the maximum response time τ max , we keep reducing the estimated response timeτ i, j until the asymmetric transfer entropy reduces by the factor α.
For the alternate hypothesis, this finds the correct response time as will be seen from the simulations. On the other hand, the test statistic does not change rapidly under the null hypothesis and the algorithm stops at τ = 1. As we will discuss in Section V, under the null hypothesis, the asymmetric transfer entropy is minimum at τ = 1. Hence, this estimate of the response time ensures the best match with the null hypothesis assumption that

C. Linear Test for Asymmetric Causality
The ATELNeT algorithm proposed above is different from the existing work in two aspects: the choice of testing the asymmetric rather than symmetric Granger causality and the transfer entropy test statistic as opposed to the regression based approaches. In order to understand the performance gain of the two aspects separately, we propose a second test statistic based on linear regression.
Similar to the approach of [5] and with notation analogous to that of (1)-(2), we model the null hypothesis H 0 (i, j) as and the alternate hypothesis H 1 (i, j) as We use the test statistic of (3) and threshold based on (4) as per the false alarm constraint P FA : a,b is the inverse cumulative F distribution with parameters a and b. Unlike [5], we do not split the input into windows.
Note that this approach requires separate estimation of the response time τ i, j . In this section, we propose a Markov chain model of 2 IUs i and j for studying the behavior of A E i →S j |E j as we vary the causal lag τ, the frame lengths, inter-arrival times, and the probability of one IU responding to another. Ideally, this requires modeling the MAC protocol of the incumbent network. But to avoid restricting our study to a single MAC protocol and for analytical tractability, we re-use the observation in Section II-A that IUs will not interfere with each others' responses to construct a simplified discrete time Markov chain model of only 2 IUs. The Markov chain's state transitions occur every T s seconds. We make the following assumptions: Note that assumption 5 is justified in the system model described in Section II.
We will describe the model from the point of view of IU i transmitting a new frame and IU j responding (or not). The model is symmetric in i and j. The states of the model are chosen such that in each state, the indicator variables , and S j [t] take exactly one value each.
The model begins in the central state Ch[∞] that represents the unoccupied channel with no active transmissions or responses. From this state, either IU may start transmitting a new frame with probability p i or p j respectively. These parameters are related to the frame duration T i,frame and idle time T i,idle (in seconds) of the IUs as follows.
Without loss of generality, assume IU i starts transmitting. The continued transmission of IU i is modeled by the state IU i which has a self loop of probability p d i to model the frame length as 1 + G where G is a geometric random variable. The parameter p d i is related to the expected frame duration (in seconds) by When the frame ends, the channel is modeled to be vacant for two time samples in states Ch i [1] and Ch i [2]. Since we have assumed that the response time is 3 samples for both links, the model can transition from state Ch i [2] to a response state IU j,resp start with a response probability p r j or continue to a state of unoccupied channel Ch i [3] with probability 1 − p r j . If the latter transition occurs, then the system will simply transition back to the initial unoccupied channel state Ch[∞].
IU j,resp start 0 0 1 Instead, if IU j begins transmitting a response, then we model the response length T j,response by the state IU j,resp that has a self loop of probability p dr j : When the response ends, the channel is modeled as being unoccupied for at least two more time instants because of our fifth and sixth assumption above. From state Ch i j [3], either IU may start transmitting with the original probabilities p i and p j . If neither begins transmitting, then the channel is unoccupied and the system returns to the state Ch[∞]. The model for IU j transmitting is identical. It should be noted that the model in Fig. 4 defines a scenario where two users sharing the same channel always detect each other's transmissions and never collide. Hence, the causality in this model is slightly higher than a more practical scenario.
For the purposes of the following discussion, we consider the null hypothesis to be H 0 (i, j) as defined earlier. Since the model is symmetric in i and j, without loss of generality, we consider only the alternate hypothesis of H 1 (i, j). Unless mentioned otherwise, we set p r i = 0, i.e., i never responds to j's transmissions.

A. Computing Asymmetric Transfer Entropy from the Model
To compute A E i →S j |E j (τ i, j ) in this model, we first need to compute the joint probability mass function of E , and S j [t]. As mentioned above, the states of the model were designed such that each state had exactly one value for these three time series. This correspondence is listed in Table I Using this correspondence, we can write the joint probability mass function of E , and S j [t] in terms of the steady state probabilities of this Markov chain model. The joint probability mass function is listed in Table II. The steady state probabilities have been derived in Appendix B by solving the appropriate simultaneous equations. The asymmetric transfer entropy for various lags can then be expressed in terms of our model's parameters by using Table II to compute individual terms in the summation of (7). These expressions for causal lags up to 3 are derived in Appendix C. Unfortunately, the algebraic expressions themselves do not provide much insight into the behavior of the test statistic due to the large number of terms involved. Therefore, we study the behavior of the test statistic numerically by varying its various parameters, viz., the probability of starting a new transmission p i and p j , the frame lengths through p d i and p d j , the probability of IUs responding to each other p r i and p r j , and the length of the response frames through p dr i and p dr j .

B. Effect of increasing causal lag
We begin by studying the increase of asymmetric transfer entropy for the link i → j with increasing causal lag. As Fig. 5 shows, A E i →S j |E j (τ) increases with τ for all response probabilities p r j , but the rate of increase also increases with p r j . Most importantly, A E i →S j |E j (τ) increases significantly at τ = 3. This matches our intuition in Section IV-B where we expected this sudden increase due to the fact that a response is likely to occur with high probability at lag 3. We can Causal Lag Asymmetric Transfer Entropy p r j = 0 p r j = 0.01 p r j = 0.05 p r j = 0.2 p r j = 0.5 p r j = 1   Fig. 5 to choose the parameter α in Algorithm 1. Fig. 5 shows that A E i →S j |E j (3) is at least 10 times larger than A E i →S j |E j (2) for even p r j = 0.01. Hence, we suggest α = 10 is an appropriate choice for the parameter.

C. Effect of frame durations and idle time
One reason for studying this model is to understand how A E i →S j |E j (1) behaves under the null hypothesis. For this purpose, we set p r j = 0 = p r i . As discussed above, the Response probability p r j Asymmetric Transfer Entropy estimated response time for a null hypothesis link will be 1.

From Appendix C, we can express
where for the purposes of this study, let us set p i = p j and rewrite p d i and p d j using (15) in the form of a duty cycle percentage.
Then, Fig. 6 shows that A E i →S j |E j (1) increases as the frames become shorter and more frequent. It also shows that reducing the sampling interval T s reduces A E i →S j |E j (1). Intuitively, this makes sense because a shorter T s implies more samples in the interval between transmissions. We shall revisit (17) and Fig. 6 in Section VI for understanding the effect of increasing N.

D. Effect of increasing response probability
As is to be expected, the asymmetric transfer entropy increases with the probability p r j of IU j responding to IU i. Fig. 7 shows that this is true only for a sufficiently large response probability depending on the frame length when a constant idle time is maintained. Together with the discussion for Fig. 6, we infer that for short and frequent transmissions, the asymmetric transfer entropy under the null hypothesis is equivalent to that for a small response probability. Hence, Fig. 7 further highlights the difficulty of detecting causality for IUs with short frequent transmissions.

VI. SIMULATION RESULTS
In this section, we study the performance of learning the topology of 802.11n networks through NS-3 simulations 2 . Note that 802.11n uses time division multiplexing opportunistic spectrum access through its Distributed Coordination   Table III. For our Monte Carlo simulations, we present results for different infrastructure-based topologies after averaging over time. That is, each topology is simulated for up to 1000 seconds and each of the topology learning algorithms are run on non-overlapping time windows of the obtained activity sequences. The length of these windows is described for each of the scenarios below. The learning algorithms were implemented in MATLAB for ease of development. We measure the performance of the algorithms as the average fraction of links detected and the average number of extra links, i.e., pairs of IUs erroneously detected as being linked. We consider links without direction.
In this section, we will use the Monte Carlo simulations to compare our proposed ATELNeT algorithm with the hard and soft fusion algorithms proposed in [5], the Hawkes process based method proposed in [6] 3 , and the linear asymmetric test proposed in Section IV-C. Then, we will present a comparison to the algorithm proposed in [7] for learning end-to-end routes in ad hoc networks. Finally, we will compare the computational complexity of the different algorithms.

A. Comparison of Parameters
Though the input for each of the algorithms mentioned above are the same binary activity sequences a m [n], each of these methods uses a different sampling interval and causal lag. For the hard and soft fusion algorithms of [5], we input the activity sequences sampled at T s = 20µs, used a window size of 60ms, and set the causal lag to 8 samples, i.e., 160µs as per the authors recommendations. Since [6] studies the continuous time point process of the transmission start times, we input the absolute start times of each transmission. A causal lag of 160µs was used via an exponentially decaying kernel. For ATELNeT, we ensure T s τ max is greater than the minimum idle time for any IU. In general, we want T s to be shorter than the minimum response time for any pair of IUs and, as Fig. 6 indicates, T s should be as small as possible. For the 802.11 family, the minimum idle time varies from 34µs to 50µs. Hence, we choose T s = 5µs and τ max = 10, i.e., maximum causal lag of 50µs.
For the linear test for asymmetric Granger causality, we choose the same sampling interval T s = 5µs, but set the causal lag as 3 samples to match the response time of the 802.11n system being simulated.

B. Comparison of Test Statistics
We begin by studying the receiver operating characteristics (ROC) for the test statistics proposed in [5], [6] and Section IV. For the hard fusion algorithm proposed in [5], we used g i→j from (3) as the test statistic. For the soft fusion algorithm also proposed in [5], we used the causality magnitude F i→j from (5). For the algorithm proposed in [6], we used their influence matrix as the test statistic.
First, we used 60ms long observation periods to plot the ROC in Fig. 8(a). We note that both test statistics proposed in [5] have almost identical curves. On the other hand, the algorithm proposed in [6] appears to have an upper limit on the achievable detection probability. Furthermore, since the authors do not propose a minimum strength required for detecting the causal connection, their threshold is chosen to be zero, i.e., they operate at the upper limit of the detection probability as seen in Fig. 8(a). Hence, their proposed method suffers from a large false alarm rate as will be seen in the later results as well. Finally, test statistics of both ATELNeT, i.e., (N,τ i, j ), and linear asymmetric test, i.e., (3), have approximately the same ROC.
Next, Fig. 8(b) shows the ROC for observation periods of 600ms. Since both algorithms proposed in [5] use windows of length 60ms, the ROC for their test statistics do not change with increasing observation periods. However, the algorithm proposed in [6] does improve its ROC making it a viable candidate for testing the binary hypotheses. The linear asymmetric test as well as ATELNeT have almost identical and perfect ROC curves.
The perfect nature of the ROC curves in Fig. 8(b) indicates that any of the three methods -that proposed in [6] and those we propose in Section IV -should be able to achieve almost perfect detection of the network topology by an appropriate choice of thresholds. However, the simulation results below will show that the thresholds chosen for each algorithm are suboptimal. We believe this is due to two facts: the threshold is chosen to have constant false alarm and the null hypothesis in all these works models zero causality.

C. Performance vs. Observation Duration
Increasing the observation period or, equivalently, the number of samples N has multiple effects. First, the non-stationary nature of the communication protocols means that more responses are observed on each link. Secondly, with increasing number of samples, each of the methods is able to detect weaker causal relationships. Hence, the false alarm rate of each of the methods, including ATELNeT, increases with increasing observation period or number of samples. Fig. 9 shows the performance of each of these algorithm in learning the topology of the system with 2 APs and 3 STAs associated with each AP. As expected, the fraction of links detected correctly increases with the observation period. The higher detection rate of the linear tests is also associated with a higher number of extra links as seen in Fig. 9(b). Both algorithms proposed in [5] attempt to reduce the number of extra links by splitting the observed period into windows of equal duration and fusing the topologies inferred on each window. As seen in Fig. 9(b), the hard fusion algorithm of [5] is more effective at reducing the number of extra links detected than the soft fusion algorithm. Note that the maximum number of extra links detected by the hard fusion algorithm is at about 60ms, i.e., the duration of a single window.
The proposed ATELNeT algorithm detects the least number of extra links. Since the linear asymmetric test also detects significantly fewer extra links than the methods of [5], we believe this performance gain is due to testing asymmetric Granger causality instead of symmetric Granger causality. Note that the linear asymmetric test does not use windowing or fusion.
We can also see this rise from our model using (17). By the non-central χ 2 distribution ofÂ E i →S j |E j (N, 1), we can write the false alarm probability P FA as where Q 1 (·, ·) is Marcum's Q function. Hence, P FA increases with N due to the monotonic nature of the Marcum's Q function. Now, our Markov chain model has more dependencies than the actual system due to assumptions such as lack of collisions. Therefore, (18) provides an upper bound for P FA rather than an equality. For example, the system considered in Fig. 9 has A E i →S j |E j (1) of the order of 10 −7 under the null hypothesis as per Fig. 6. For a 5s observation period, i.e., N = 10 6 , (18) tells us that the false alarm probability is bounded above by 0.0653 while the simulation resulted in a false alarm probability of 0.0083.

D. Performance as Network Size Increases
In Fig. 10, we compare the performance of learning the network topology as the number of STAs associated with each AP increase. The trends are similar to that seen in Fig. 9. The linear asymmetric test detects the highest fraction of links with a slightly higher number of extra links as compared to ATELNeT. The algorithm of [6] and the soft fusion algorithm of [5] detect a high number of extra links. The hard fusion algorithm of [5] detects a large fraction of links correctly while detecting relatively fewer extra links. In summary, the ATELNeT learns the topology of varying network sizes with high probability and with almost no extra links.

E. Application: Inferring links in ad hoc networks
In ad hoc networks, the topology also corresponds to the routes of the data flow. Hence, the authors of [7] learn the endto-end routes in ad hoc networks. For each IU, they propose a hidden semi-Markov model such that it has super states reflecting data flows that it participates in. Their proposed algorithm learns the super state dependent distributions of the frame lengths and inter-arrival times for each IU using a hierarchical Dirichlet process as a prior for their super state model. IUs that have learned similar distributions are clustered together as part of the same end-to-end route.
In this section, we describe the directed links detected by our algorithm from the same data used in [7] Fig. 11, we can infer that there were two routes for the data flow from IU 25 to IU 1. At time 41s, we detect the route renegotiation and note that the new route remains in service for at most 2 seconds since the original route is active from 43s onwards. Fig. 11(e) shows the links detected for the data flow from IU 21 to IU 5. Interestingly, ATELNeT also detects links corresponding to a data flow from IU 5 to IU 21 along a separate route that [7] had missed.
In comparison, Fig. 11(f) shows that the end-to-end routing algorithm proposed in [7] learns 3 routes (shown by distinct colors): one between IU 25 and IU 1 and two between IU 21 and IU 5. It does not detect the short lived route of Fig. 11(b) nor does it detect the direction of the routes. Hence, our algorithm infers the directed links between pairs of IUs at a finer time resolution than [7] and can detect network changes faster.

F. Comparison of Computational Complexity
For a single link, ATELNeT begins by estimating the joint probability mass function of (S j [t], E (τ max )  In comparison, computing the linear MMSE estimator from W samples for the parameters in a linear regression with τ causal lag requires O(τ 2 W) computations. Hence, both fusion methods proposed in [5] have computational complexity O(τ 2 W(N/W)) = O(τ 2 N). Similarly, the proposed linear asymmetric test has the same computational complexity. For testing all pairs of IUs, the computational complexity of each algorithm is O(τ 2 N M 2 ).
The method proposed in [6] solves M convex optimization problems with a quasi-Newton descent algorithm. Each of these problems has M + 1 parameters and requires O(N 2 ) operations for evaluating their likelihood function. Therefore, each problem has O((M + 1) 2 + M N 2 ) computations. For solving all M + 1 problems, the computational complexity is O(N 2 M 2 ) since M N typically. In summary, the computational complexity of ATELNeT is similar to that of algorithms proposed in [5] and lower than [6].

VII. CONCLUSION AND FUTURE WORK
In this paper, we have proposed a method to learn the network topology of time multiplexing communicating IUs by detecting the causal relationship of two IUs' transmissions due to their response time, i.e., the time between the end of a transmitted frame and the start of the response signal. This response time is widely used in communication protocols today and is relatively invariant over time for a given link. For detecting this response, we have proposed a non-parametric test statistic called asymmetric transfer entropy that differs from existing methods in two ways: it tests asymmetric Granger causality and does not require a linear model. We have shown that the shared channel causes IUs to have nonzero causality irrespective of whether they are communicating with each other. Since this results in detecting extra links, we minimized this effect by an algorithm that estimates the response time of the link.
We also proposed a Markov chain model to analyze the behaviour of the proposed test statistic under both hypotheses for the transmissions of a pair of IUs. The model shows that both the false alarm and detection probability increase with shorter more frequent transmissions. Using NS-3 simulations of 802.11n networks, we showed that, in comparison to existing methods in literature, our proposed algorithm significantly reduces the number of extra links detected in the network while achieving comparable link detection performance. Finally, we showed that the topology learned from an ad hoc network actually consists of the directed links in the network. This is an interesting problem that may be amenable to many approaches. Forward-backward iterative algorithms, graphical approaches to inferring the entire network simultaneously, as well as supervised learning based approaches may be of interest for future study. It would also be beneficial to study the incorporation of the learned topology into channel access protocols for cognitive radios.

VIII. ACKNOWLEDGEMENT
The authors would like to thank Silvija Kokalj-Filipovic for sharing data from [7] and interesting discussions.

APPENDIX A ASYMPTOTIC DISTRIBUTION OF EMPIRICALLY ESTIMATED ASYMMETRIC TRANSFER ENTROPY
We now derive the distribution of the empirical estimatê A E i →S j |E j (N, τ) using the same logic as the derivation of the distribution of the empirical estimate transfer entropy in [19]. In short, A E i →S j |E j (τ) is reinterpreted as a log likelihood ratio and then large sample theory is used to show that the empirical estimator has a known distribution. Since where θ is the model parameter vector. Now, under our null hypothesis, S j [t] is conditionally independent of E (τ) . Let Θ 0 be the set of parameter vectors under this null hypothesis and Θ 1 be the set of parameter vectors under the alternate hypothesis. The likelihood ratio is given by whereθ 0 andθ 1 are the maximum likelihood estimators of θ under the two hypotheses. Note that as mentioned above, these are simply the empirical probability mass functions of respectively. Now, it is easy to see that (20) combined with (19) gives tells us that under the null hypothesis, the distribution of 2(N − τ)Â E i →S j |E j (N, τ) is asymptotically a central χ 2 distribution with d i, j degrees of freedom while under the alternate hypothesis, the distribution of 2(N − τ)Â E i →S j |E j (N, τ) is asymptotically a non-central χ 2 distribution with d i, j degrees of freedom and non-centrality parameter 2(N−τ)A E i →S j |E j (τ). Here, d i, j is the difference between the number of parameters in the full and null models.

APPENDIX B STEADY STATE PROBABILITIES OF MARKOV CHAIN
In this section, we derive the steady state probabilities of the Markov chain model described in Section V for a two IU system. First, we note that all the steady state probabilities in this model can be written in terms of p * is and p * js :