s2fieldsofstudy:
Computer Science
Business

text:
Impact of LOS/NLOS Propagation and Path Loss in Ultra-Dense Cellular Networks

Most prior work on performance analysis of ultra-dense cellular networks (UDNs) has considered standard power-law path loss models and non-line-of-sight (NLOS) propagation modeled by Rayleigh fading. The effect of line-of-sight (LOS) on coverage and throughput and its implication on network densification are still not fully understood. In this paper, we investigate the performance of UDNs when the signal propagation includes both LOS and NLOS components. Using a stochastic geometry based cellular network model, we derive expressions for the coverage probability, as well as tight approximations and upper bounds for both closest and strongest base station (BS) association. Our results show that under standard singular path loss model, LOS propagation increases the coverage, especially with nearest BS association. On the contrary, using dual slope path loss, LOS propagation is beneficial with closest BS association and detrimental for strongest BS association.

I. INTRODUCTION
Network densification is foreseen as one of the key enablers to realize the vision of emerging 5th generation (5G) wireless networks [1], [2]. Heterogeneous cellular network (HetNet) deployment is a promising and effective way to provide high cellular network capacity by overlaying conventional macrocell architecture with heterogeneous architectural features, such as small cellular access points (picocells and femtocells), low-power fixed relays, and distributed antennas. Ultra-dense networks (UDNs), i.e., dense and massive deployment of small cells, are expected to achieve higher data rates and enhanced coverage by exploiting spatial reuse, while retaining at the same time seamless connectivity and low energy consumption. Supported by recent studies, UDNs are expected to achieve unprecedented data rates and power consumption reduction. Nevertheless, most prior performance analyses use spatial models, in which the base stations (BSs) are located according to a homogeneous Poisson point process (PPP) and propagation is modeled using standard power-law path loss and Rayleigh fading. For instance, using the aforementioned model with nearest BS association [3] and strongest BS association [4], throughput is shown to grow linearly with the density of BSs per area in the absence of background noise.
Recently, there has been a growing interest in devising increasingly realistic models for system-level performance evaluation of cellular networks. In this respect, [5] studies the impact of dual slope path loss on the performance of downlink UDNs and shows that both coverage and capacity strongly depend on the network density. In [6], a stochastic geometry based framework for millimeter wave (mmWave) and path loss with line-of-sight (LOS) and non-line-of-sight (NLOS) propagation is proposed. Further models and studies on the effect of LOS propagation in higher frequencies can be found in [7], [8]. However, all previous studies capture the effect of LOS on the large-scale fading (i.e., path loss), yet always assuming Rayleigh fast fading. This is a coarse simplification, mainly due to tractability, which can significantly alter coverage and throughput performance, since LOS propagation is known to be subject to Ricean fast fading.
In this work, we broaden prior studies on network densification and propose a general stochastic geometry based framework for the effect of LOS/NLOS propagation in both small-scale and large-scale fading. This allows for a practically relevant analysis of UDNs under a more realistic setting, which models LOS propagation using Ricean fading; more precisely, we approximate the Rician fading by Nakagami-m distribution for tractability. Remarkably, the proposed framework accommodates generalized distance-dependent LOS probability functions; in addition, it encompasses both closest and strongest BS association, as well as single-and multi-slope path loss. As a particular scenario, we consider the ITU-R urban microcell (UMi) LOS probability model [9] and provide a tractable approximation for the coverage probability. Our results provide crisp insights into the coverage and throughput performance and show the impact of LOS on BS association. We show that, under standard power-law path loss model, LOS propagation increases the coverage, especially with closest BS association. On the contrary, considering dual-or multi-slope path loss models, LOS propagation is beneficial for closest BS association and detrimental for strongest BS association.

II. SYSTEM MODEL
We consider a typical downlink user equipment (UE) located at the origin of the Euclidean plane. For the location distribution of the BSs, we consider the marked Poisson point where the underlying point process Φ {x i } ⊂ R 2 is a homogeneous PPP with density λ and the mark h xi ∈ R + represents the channel power fading gain from the BS located at x i to the typical UE. Let : R + → R + denote the path loss function. In the first part or unless otherwise stated, we assume the standard power-law path loss model with (r xi ) = r −α xi , where r xi x i . In Section V, we generalize our results for a multislope path loss model. Lastly, we assume that all BSs transmit with unit power.
The signal-to-interference-plus-noise ratio (SINR) when the typical UE is associated to the BS located at x is given by where I is the overall interference term defined as and σ 2 is the additive noise power. In our model, each BS is characterized by either LOS or NLOS propagation independently from the others and regardless of its role as serving or interfering BS. Assuming a distance-dependent LOS probability function p LOS (r x ), i.e., the probability that a BS located at x experiences LOS propagation, which depends on the distance r x , the distribution of the channel power gain is expressed as where f LOS (z) and f NLOS (z) are the pdfs corresponding to LOS and NLOS propagation, respectively. In the following, we assume that the channel amplitudes are Rayleigh distributed in NLOS propagation condition and Nakagami-m distributed in LOS conditions; hence, the channel power gains are distributed according to exponential and Gamma distributions, respectively. The complementary cdf of the latter is given bȳ where the last equality holds when m is an integer; note thatF NLOS (z) can be obtained from (4) simply by setting m = 1. Approximating Ricean fading with a Nakagamim distributed amplitude is common practice because of its tractability, flexibility, and good fitting performance. In the general LOS case, m is computed as m where K is the Ricean K-factor representing the ratio between the powers of the direct and scattered paths. 1 For simplicity, we focus on the interference-limited case, where I σ 2 in (1) and hence work with the signal-to-interference ratio (SIR).

III. SIR COVERAGE WITH LOS PROPAGATION
In this section, we provide our most general result, which is an expression for the coverage probability when both serving and interfering BSs independently experience either LOS or NLOS conditions, depending on their distance from the typical UE; note that we define the coverage probability as the probability that the received SIR is larger than a target θ, i.e., P cov (θ) = P(SIR > θ); both closest [3] and strongest (i.e., highest SINR) [4] BS association are considered.
The result is shown below in Theorem 1. Before, let us introduce the following preliminary definitions. We define which allow us to generalize our results for both closest and strongest BS association. Furthermore, we use P NLOS cov (θ) and L NLOS I (s) to denote the coverage probability and the Laplace transform of the interference, respectively, when there is only NLOS propagation: The coverage probability is given by (10) The expressions above are valid for any integrable p LOS (r). However, the particular characteristics of this function will determine how easily the integrals can be evaluated. Inspired by 3GPP channel models, in the following section, we propose a model for p LOS (r) that greatly simplifies the resulting expressions, while still capturing the underlying physical phenomena.

IV. TRACTABLE LOS PROBABILITY MODEL
Several LOS probability models have been proposed in the literature, most of them distance-dependent. A commonly used model is the ITU-R UMi model [9] (referred to as 3GPP model in the following), given by where the propagation is always in LOS conditions for r ≤ 18 m. In practice, this implies that, for densities above λ = 10 −2 BS/m 2 and closest BS association, the probability of LOS coverage is very close to one. As a consequence, some NLOS terms in the previous expressions could be neglected. Following this line of thought, we propose the following simplified model that preserves the flatness of the first part of the curve and can be used for analytical calculations; our numerical results will show that it approximates very accurately widely used 3GPP channel models. Its expression is given by with D > 0 being the critical distance below which all BSs are in LOS conditions. In this scenario, the coverage probability in (10) simplifies as Here, L NLOS I (s) is the Laplace transform of the interference when all the BS are in NLOS conditions introduced in (8). On the other hand, the Laplace transform comprising both LOS and NLOS conditions admits now a much simpler expression, denoted above by L LOS I (s) and given by Corollary 1. The coverage probability in (13) when λ → 0 becomes lim λ→0 P cov (θ) = P NLOS cov (θ) where P NLOS cov (θ) is the coverage probability when there is only NLOS propagation defined in (7).
Proof: See Appendix II.
These expressions can now be evaluated by resorting to numerical integration and differentiation. However, the latter can be cumbersome in practice, especially for large values of m. Thus, to make numerical evaluation more efficient, a simpler tractable upper bound with no derivatives is sometimes more practical. The following Lemma provides a result that can be used for this purpose.

V. IMPACT OF MULTI-SLOPE PATH LOSS ON NLOS/LOS COVERAGE
So far we have assumed a simple power-law path loss model with a single path loss exponent. However, the general framework provided in Section III admits a straightforward extension to multi-slope path loss models with N different path loss exponents {α n } N −1 n=0 (cf. [5]). In particular, the coverage probability is given by (17) at the top of the next page, where the values {R n } mark the transition distances between the different path loss exponents {α n }; we note that, for coherence, R 0 = 0 and R N = ∞. In (17), the Laplace transforms of the interference are given by and (19) at the top of the next page: here, we have defined an alternative set of transition distances { R n } that are equal to {R n } with the exception of R 0 = ν(r).

VI. SIMULATION RESULTS
In this section, we numerically evaluate the derived expressions of the coverage probability and assess the impact of LOS propagation under the assumption of both closest and strongest BS association.
The reported numerical results are obtained by means of Monte Carlo simulations for 10 5 realizations of the PPP with  The coverage probabilities in these two settings are compared with the tractable upper bound obtained using the result in Lemma 1. In the following, we plot both the SIR and the SINR coverage probabilities, where for the latter we assume SNR 1/σ 2 = 10 dB; furthermore, we use θ = −5 dB and θ = 0 dB as SIR/SINR thresholds. All channels in LOS conditions are characterized by Ricean fading with K-factor K = 15 dB: their amplitude is approximated with a Nakagamim distribution with m = (K + 1) 2 /(2K + 1) rounded to the nearest integer (this corresponds to having m = 17). We examine both single-and dual-slope path loss models, with α = 4 for the former and α 0 = 2.1, α 1 = 4, and R 0 = 10 m for the latter. Figure 1 plots the coverage probability with the 3GPP model in (11). When closest BS association is considered, taking into account the LOS propagation implies a substantial increase of the coverage probability; on the other hand, under strongest BS association, no noticeable difference is observed. This behavior lies in the fact that, with closest BS association, the serving BS is likely to be in LOS conditions, which results in higher SINR as the interferers lie further than the distance from the closest BS; on the contrary, with strongest BS association, the signal from the serving BS is not necessarily in LOS condition and grows at the same rate as the interference. A general and important result is that the impact of LOS propagation with closest BS association is comparable to the effect of switching to strongest BS association in NLOS.
From Figure 2, which focuses only on the SIR coverage probability, it is evident that the simplified 3GPP model resembles very closely the 3GPP model for densities above approximately λ = 10 −3 . On the other hand, the tractable upper bound on the coverage probability is remarkably close to the simplified 3GPP model in the decreasing part of the curve, whereas it is less accurate in the flat part and becomes tighter for decreasing SIR threshold. Furthermore, we note that the limit in Corollary 1 holds already at densities as low as λ = 10 −4 .
Lastly, we evaluate the coverage probability using a dualslope path loss model in Figure 3. In this setting, LOS propagation is beneficial for closest BS association and detrimental for strongest BS association. This contrasting behavior can be explained as follows. With closest BS association, the link between the typical UE and the serving BS experiences LOS propagation and path loss exponent α 0 with high probability in general and with probability one in the ultra-dense regime; on the other hand, the closest interfering BS, which is located further than the nearest neighbor distance, can be either NLOS or LOS conditions depending on the density, and its power is generally lower than the received signal power. Otherwise stated, for low-to-moderate BS densities, the UE is likely to have LOS propagation with the serving BS and NLOS with most of the interfering BS, i.e., the received power is higher than the interference power. With strongest BS association, most of the interfering BS experience LOS and are in the near-field (with path loss exponent α 0 ), while the serving BS is not necessarily in the near-field for low-to-moderate densities. Nevertheless, the detrimental effect of LOS on the coverage vanishes in the ultra-dense regime.

VII. CONCLUSIONS
In this paper, we propose a stochastic geometry based framework to study the effect of LOS/NLOS propagation on network densification. In particular, we model the LOS propagation as Ricean fading, in contrast to prior work that only assumes Rayleigh fading: this allows for practically relevant performance analysis of UDNs under a more realistic setting. Remarkably, the proposed framework accommodates generalized distance-dependent LOS probability functions; in addition, it encompasses both closest and strongest BS association, as well as single-and multi-slope path loss models. As a particular scenario, we consider the 3GPP LOS probability model and provide a tractable approximation of the coverage probability. Our results provide useful insights into the coverage and throughput performance and show the impact of LOS propagation on BS association. We show that under a standard power-law path loss model, LOS propagation increases the coverage, especially with closest BS association. Moreover, considering dual-or multi-slope path loss models, LOS propagation proves to be beneficial for closest BS association and detrimental for strongest BS association.

APPENDIX I PROOF OF THEOREM 1
We start by obtaining the expression of the Laplace transform of the interference as By sequentially applying Bayes theorem and the PGFL of a PPP, we obtain (22)-(23) at the top of the next page, where the operator E h∼LOS [ · ] denotes the expectation when h is subject to LOS fading, which gives E h∼LOS exp(−sht −α ) = (1 + st −α /m) −m , and we note that the corresponding expectation with NLOS conditions is obtained by setting m = 1. Note that the lower limit of the integral changes according to the type of BS association (i.e., closest or strongest). After substituting this expression into (23), we just need to write the coverage probability as a function of the Laplace transform of the interference. We can show that closest BS and strongest BS associations converge to a similar formulation.


extfieldsofstudy:
Computer Science
Mathematics

text:
Coverage and capacity scaling laws in downlink ultra-dense cellular networks

Driven by new types of wireless devices and the proliferation of bandwidth-intensive applications, data traffic and the corresponding network load are increasing dramatically. Network densification has been recognized as a promising and efficient way to provide higher network capacity and enhanced coverage. Most prior work on performance analysis of ultra-dense networks (UDNs) has focused on random spatial deployment with idealized singular path loss models and Rayleigh fading. In this paper, we consider a more precise and general model, which incorporates multi-slope path loss and general fading distributions. We derive the tail behavior and scaling laws for the coverage probability and the capacity considering strongest base station association in a Poisson field network. Our analytical results identify the regimes in which the signal-to-interference-plus-noise ratio (SINR) either asymptotically grows, saturates, or decreases with increasing network density. We establish general results on when UDNs lead to worse or even zero SINR coverage and capacity, and we provide crisp insights on the fundamental limits of wireless network densification.

I. INTRODUCTION
With exponential increase in data traffic driven by a new generation of wireless devices, data is expected to overwhelm cellular network capacity in the near future. Heterogeneous cellular network (HetNet) deployment is a promising and effective way to provide high cellular network capacity by overlaying conventional macrocell cellular architecture with heterogeneous architectural features, such as small cellular access points (picocells and femtocells), low-power fixed relays, and distributed antennas. Ultra-dense networks (UDNs) are expected to achieve higher data rates and enhanced coverage by exploiting spatial frequency reuse, while retaining at the same time seamless connectivity and mobility. Inspired by the attractive features and potential advantages of UDNs, their development and deployment has been gaining momentum in both wireless industry and research community during the last few years. It has also attracted the attention of standardization bodies, e.g. 3GPP LTE-Advanced.
Existing cellular network analyses have focused on stochastic geometry based models, in which base stations (BSs) are located according to a Poisson point process (PPP). Most prior results have considered a standard singular power-law path loss model and Rayleigh fading, as a means to provide tractable analysis of coverage probability and other key performance metrics in downlink cellular networks. For instance, recent results using the aforementioned models with closest BS [1] and strongest BS association [8] show that the coverage probability does not depend on the network density when thermal noise is negligible. However, the singular single-slope path loss model used therein leads to unrealistic results in certain scenarios and fails to accurately capture the dependence of path loss exponent on the link distance. In [20], the authors study the impact of dual slope path loss on the performance of downlink UDNs under closest BS association and show that both coverage and capacity performance strongly depends on the network density. More precisely, it is shown that the network coverage in terms of signal-to-interference-plus-noise ratio (SINR) is maximized at some finite density and there exists a phase transition in the near-field path loss exponent with ultra densification (i.e. network density goes to infinity). In [6], the authors consider strongest BS association with bounded path loss and lognormal fading and show that the coverage attains a maximum point before going down when the network densifies. Based on system-level simulations, [13] shows that there is a fundamental limit of 1 cell/user in UDNs, although such deployments are neither cost nor energy efficient. Despite shedding light on the performance limits of UDNs and the optimal network density, previous work has mainly focused on the effect of path loss singularity [11], [12], [16] or boundedness [20]. The effect of fast fading has been only investigated in some particular contexts, e.g. [11], [16,Chap. 8]. Furthermore, emerging utilization of advanced communication and signal processing techniques is expected to enhance the channel gain, which in some cases may have a regularly varying tail [19] or a diffuse power component [9].
In this work, we analyze the SINR, coverage probability and capacity of downlink UDNs under multi-slope path loss and general fading distributions, considering strongest BS association in PPP networks. In particular, using general fading distributions, we provide the ability to capture the effect of either fast fading, shadowing, or composite fast fadingshadowing. We study the tail behavior of the received signal power, as well as the SINR, coverage and capacity scaling in the ultra-dense regime. Our results provide useful insights on the fundamental limits of network densification with the following main conclusions: • Under the Poisson field assumption, the most affecting component of the path loss is its near-field exponent β 0 . Bounded path loss (obtained for β 0 = 0) is just a special case of β 0 < d with d being the network dimension. • The effect of fading on the performance scaling is as significant as path loss, and regularly varying fading distributions have the same effect as path loss singularity. • In more conventional cases when the near-field path loss exponent is greater than the free-space dimension (i.e. β 0 > d), or when fading is heavy tailed (i.e.F m ∈ R −α , α ∈ (0, 1)), the coverage and capacity saturate at a limiting bound when the network density increases. • In more realistic cases with β 0 < d (in particular β 0 = 0) and fading being less heavy tailed or even truncated, both coverage and capacity exhibit an 'inverse U' behavior w.r.t. network density, i.e. both are maximized at finite density then vanish when the network further densifies. • Finally, all standard fading models, such as Rayleigh, lognormal, Gamma, and their composite forms, belong to the same class of fading distributions, which leads to coverage and capacity maximization at a certain finite network density.

A. Network Model
Consider a typical downlink user located at the origin and that the network is composed of cell sites located at positions {x i , i = 0, 1, . . .}. For convenience, cell sites are referred to as nodes, whereas the typical user is simply referred to as user. Unless otherwise stated, {x i } are assumed to be random variables independently distributed on the network domain according to a homogeneous Poisson point process (PPP) of intensity λ, denoted by Φ. In prior work, the entire d-dimensional Euclidean space R d , where d = 2 is usually assumed as network domain. Since network domain is in reality limited, and far-away nodes are less relevant to the typical user due to path loss, we assume that the distance from the user to any node is upper bounded by some constant 0 < R ∞ < ∞, which can be arbitrarily large. Each node transmits with some power that is independent to the others but is not necessarily constant.

B. Propagation Model
Let l : R + → R + represent the path loss function. The receive power P rx is related to the transmit power P tx by P rx = P tx /l(r) with r being the transmitter-receiver distance. Physics laws require that l(r) ≤ 1, ∀r. However, in the literature, l(·) has been usually assumed to admit a powerlaw model, i.e. l(r) ∼ r β where β is the path loss exponent satisfying β ≥ d. This far-field propagation model has been widely used mainly due to its tractability. However, for short ranges, especially when r → 0, this model is no longer relevant and becomes singular at the origin. In the context of network densification where the inter-site distance becomes smaller, the above singular model may be unsuitable. Moreover, the dependence of the path loss exponent on the distance in emerging millimeter wave (mmWave) communications [7], [20] advocates the use of a more generic path loss function. In this work, the path loss is modeled as follows where 1(·) is the indicator function, K ≥ 1 is a given constant characterizing the number of path loss slopes, R k are constants satisfying β k denotes the path loss exponent satisfying and A k are constants to maintain continuity of l(·), i.e.
for k = 0, . . . , K − 2. For notational simplicity, we also use the following notation The above model (cf. (1)) captures that the path loss exponent varies with the distance while remaining unchanged within a certain range. In principle, free-space propagation in R 3 has path loss exponent equal to 2 (i.e. β = d − 1), whereas in realistic scenarios, path loss models often include antenna imperfections and empirical models usually result in the general condition (3b) for far-field propagation. Condition (3c) models the physical property that the path loss increases faster as the distance increases. Notice, however, that this condition is not important in the subsequent analytical development. Finally, condition (3a) is related to the near field (i.e. it is applied to the distance range [0, R 1 ]). The multi-slope path loss function, as defined above, has the following widely used special cases: • K = 1, β 0 ≥ d: l(r) = A 0 r β0 , which is the standard unbounded path loss, • K = 2, β 0 = 0: l(r) = max(A 0 , A 1 r β1 ), which is the bounded path loss recommended by the 3GPP standard, in which A 0 is referred to as the minimum coupling loss. Due to the particular importance of path loss boundedness so as to have a realistic model, we have the following definitions: Definition 1. A path loss function l : R + → R + is said bounded if and only if 1/l(r) < ∞, ∀r ∈ R + , and unbounded otherwise. Furthermore, the path loss function l(·) is said physical if and only if 1/l(r) ≤ 1, ∀r ∈ R + .
It is clear that the path loss function (1) is bounded if and only if (iff) β 0 = 0, and is physical iff β 0 = 0 and A 0 ≥ 1.
Besides path loss, shadowing and fast fading are also sources of wireless link variations, which are commonly referred to as fading in the sequel. Let m i be a variable containing transmit power, fading, and any gains or attenuation other than path loss from i-th node to the user. Given node location {x i }, the variables {m i } are assumed not identical to zero and independently distributed according to some distribution F m . To this end, the signal power, say P i , that the user receives from i-th node is expressed as where || · || is the Euclidean distance.

C. Performance Metrics
The quality of the signal received from i-th node is expressed in terms of its SINR as where I i = j =i P j is the aggregate interference with respect to i-th node's signal, and thermal noise at the user's receive antenna is assumed Gaussian with average power W . In addition, we define I = j P j to be the total interference. The main metrics used in this paper are the coverage probability and the average rate that the user experiences from its serving cell. Let Y denote the SINR that the user receives from its serving cell. The SINR coverage probability, denoted by P y , is defined as the probability that Y is larger than a given target y, and the capacity, denoted by C, is defined as the Shannon rate (in nats/s/Hz) assuming Gaussian codebooks, i.e.

D. User Association
The above performance metrics are defined with respect to the user's serving cell, which in turn depends on the underlying user association scheme. Strongest cell association is used in this work, i.e. the user is connected to the cell that provides the best/strongest signal quality (in practice, time averaging of the signal is usually performed to avoid frequent handover due to fast fading). In a longer version of this work, we also investigate the case of nearest cell association and show the effect of user association on performance scaling. Under strongest cell association, the SINR of the user is given by Y = max i SINR i and can be expressed as [15]

E. Notation
Quantities whose dependence on the network density λ is important, are denoted as ·(λ), e.g. Y (λ), I(λ), and M (λ). We also denote by r, m, and P , the distance, associated fading, and received power from a random node, respectively. Let F P be the distribution of P , andF P = 1−F P . In addition, for real functions f and g, we say → to denote the convergence in distribution, convergence in probability, and almost sure (a.s) convergence, respectively. Finally, for two random variables X 1 and X 2 defined on the same probability space, we say that X 1 is statistically greater than X 2 , denoted by X 1 h(x) = t α for t > 0. In particular, h is called slowly varying (rapidly varying, resp.) (at ∞) if α = 0 (if α = −∞, resp.). We denote by R α the class of regularly varying functions with index α.
Note that if h is a regularly varying function with index α at ∞, it can be represented as h(x) = x α L(x) as x → ∞ for some slowly varying function L ∈ R 0 . Definition 3 (Tail-equivalence). Two distributions F and H are called tail-equivalent if they have the same right endpoint, say x ∞ , and lim x↑x∞F (x)/H(x) = c for 0 < c < ∞.

III. TAIL BEHAVIOR OF RECEIVED SIGNAL POWER
The network performance mainly depends on the received SINR and hence is a function of Y , which in turn depends on M and I (cf. (7)). The behavior of the maximum M and the sum I is totally determined by that of the received power P i . Therefore, we first study the signal power P i , in particular its tail behavior using tools from extreme value theory. Proposition 1. If R ∞ < ∞, then the distance from the user to a random node admits a non-degenerate distribution given as Proof: Under the assumption that BSs are distributed according to a homogeneous PPP, the nodes of a realization φ of Φ are uniformly distributed. Thus, given φ and the assumption that R ∞ < ∞, the distance distribution to a random node of φ, say G(·; φ), is G(r; φ) = (r/R ∞ ) d for 0 ≤ r ≤ R ∞ , and G(r; φ) = 1 for r ≥ R ∞ . Then, taking G(r) = E φ (G(r; φ)), the result follows.
Remark. First, note that the distribution G is different from the usual void probability, which is the distance to the closest node (nearest neighbor). Second, we can see that for unbounded network domains (R ∞ = ∞), the distance to a random node does not have a non-degenerate distribution. This is because under the PPP assumption, nodes at equal distance increases with the circumference, which tends to infinity when the outer distance tends to infinity, leading to an absorption of nodes. Therefore, using a limited network domain is not only more realistic, but also useful to have a normally behaving distribution of the distance.
Proof: See Appendix B. Theorem 1 shows that the tail behavior of the wireless link depends not only on whether path loss is bounded or not, but also on the tail behavior of the fading. More precisely, a key implication of Theorem 1 is that path loss and fading have interchangeable effects on the tail behavior of the wireless link. This can also be shown using Breiman's Theorem [5] and results from large deviation and product distributions. In particular, when the fading distribution is a regularly varying function, the wireless link is also regularly varying regardless of the path loss function's boundedness. For lighter-tailed fading, the regular variation property of the wireless link is solely imposed by the path loss singularity.
More importantly, Theorem 1 is a general result and covers all tail behaviors for the fading: case (1) covers the heaviest tails (i.e. R −α with 0 ≤ α < ∞, e.g. Pareto distributions), as well as the moderately heavy tails (i.e. the class R −∞ , e.g. exponential, normal, lognormal, Gamma distributions). Case (2) covers all remaining tails (e.g. truncated distributions). Therefore, for any realistic statistical model and distribution of fast fading and shadowing, Theorem 1 enables us to characterize the tail behavior of the wireless link, which is essential to understand the behavior of the interference, the maximum received power, and their asymptotic relationship. In wireless communications, the signal distributionF m often involves lognormal or Gamma shadowing and Rayleigh fading, which all belong to the class R −∞ , and the path loss is bounded, thusF P ∈ R −∞ . As a result, it can be shown that in most relevant cases in wireless UDNs,F P belongs to the maximum domain of attraction of a Gumbel distribution [17].
Finally, the above result generalizes prior results: [11] showed that the interference is tail-equivalent with the fading if path loss is bounded and if E(m) < ∞, which is not applicable forF m ∈ R −α , α ∈ [0, 1]. [16,Chap. 8] showed that under lognormal fading,F P is regularly varying for unbounded path loss, and behaves like a lognormal tail for bounded path loss.
The following result, which is a direct consequence of Theorem 1, can be provided in order to better understand the signal power scaling and the interplay between path loss function boundedness and fading.

IV. SCALING LAWS
In this section, we provide the main results of this paper, namely the SINR, coverage probability and capacity scaling, when the network density is asymptotically large. Using results from Section III, we investigate and provide insights on the performance limits of network densification. First, we start by showing that in sparse networks, the signal quality improves for increased node density.

A. SINR Scaling
We provide here the scaling of the received SINR under strongest BS association in the asymptotically large node density regime.
IfF P ∈ R −α with 0 < α < 1, M/I d → R as λ → ∞ where R has a non-degenerate distribution [3]. As a result, where D is a non-degenerate distribution. [18]. Moreover, ∀y ∈ (0, ∞) → 0 as λ → ∞. Let us have a closer look at Theorem 2 and on its implications in the interplay between multi-slope path loss and fading. According to Corollary 1,F P ∈ R 0 due to the fact thatF m ∈ R 0 . Recall that m contains the transmit power and all potential channel powers (including fading). Therefore, F m ∈ R 0 implies that the channel powers take large values with non negligible probability. As a result, m dominates and compensates the path loss, resulting in maximum power that grows at the same rate as the aggregate interference. This provides a theoretical justification to the fact that network densification always enhances the signal quality Y . WhenF P ∈ R −α with 0 < α < 1, Y d → D implies that the SINR distribution converges to a non-degenerate distribution. Moreover, from Corollary 1, this convergence is due to either large near-field exponent or heavy-tailed fading. In that case, for any SINR target y, the coverage probability P(Y > y) flattens out starting from some large value of node density. This means that further increasing the network density by deploying more BSs does not improve the network performance. In Figure 1 we show the convergence of Y to a steady distribution for two cases: β 0 > d orF m ∈ R −α with α ∈ (0, 1), where 'Composite' represents the case of composite Rayleigh-lognormal fading, which belongs to the rapidly varying class R −∞ , and Pareto(α) stands for Pareto fading distribution of shape 1/α and some scale σ > 0, i.e.
In practically relevant network settings, the path loss is bounded and fading is moderately heavy tailed (i.e. R −∞ as in the case of lognormal shadowing and Rayleigh fading) or even truncated (i.e.F m = o(H) where H ∈ R −∞ ). As a result, based on Theorem 1, we have thatF P ∈ R −∞ , hence Y a.s. → 0. In other words, the SINR is proven to be asymptotically decreasing with the infrastructure density. This means that there is a fundamental limit on network densification and the network should not operate in the ultra-dense regime. In other words, deploying too many BSs would decrease the network performance due to the fact that the increased signal power cannot compensate for the faster growing aggregate interference. Figure 2 confirms that withF P ∈ R −α with α > 1 (i.e. either α 0 = 2/β 0 = 2 orF m ∼ Pareto(4)), the tail of Y vanishes and converges to zero when λ increases (ultra-dense regime). This convergence to zero of the SINR in the ultra-dense regime further emphasizes the importance of local spatial scheduling among BSs since near-field interferers generate much stronger interference than far-field ones.

B. Coverage and Capacity Scaling
To provide a complete characterization of the network performance in the ultra-dense regime, we further study the scaling of coverage probability and capacity. By the definition of the aforementioned two metrics and Theorem 2, we obtain the following result.
For case (3), given the conditions and Theorem 2, we have Y a.s → 0. Hence, lim λ→∞ P y (λ) = 0 and by Lemma 1, ∃λ p > 0 s.t. P y (λ p ) > P y (0) = 0. For C(λ), we first note that C(λ) = ∞ 0 P(Y (λ) > y)/(1 + y) dy. Thus, lim λ→∞ C(λ) = 0 by Lebesgue's dominated convergence theorem and by the fact that Y The following observations can be made based on Corollary 2: First, both the coverage probability (cf. Figure 1) and the capacity (cf. Figure 3) saturate (ceiling effect) when the fading is regularly varying with index in (−1, 0) or the nearfield path loss exponent is large (i.e. β 0 > d). Second, when the fading is less heavy-tailed (F m ∈ R −α with α > 1) and when the near-field path loss exponent is smaller (i.e. β 0 < d), both performance metrics are maximized at a finite network density, then decrease and go to zero in the ultra-dense regime (cf. 'inverse U' curves in Figure 4 and Figure 5). This suggests that there is an optimal point of network density to aim for. Furthermore, fading and path loss have equivalent and somehow interchangeable effects on the network performance. Additionally, the most affecting element of the path loss is    its near-field exponent β 0 ; bounded path loss function (i.e. β 0 = 0) is just a special case of the class β 0 < d. The impact of the near-field exponent was also observed in [20] for nearest cell association. Table I summarizes the behavior of network performance according to Corollary 2.

V. CONCLUSION
This paper analyzes the scaling regimes of the coverage probability and average rate under multi-slope path loss model and general fading distributions, considering strongest cell association in a Poisson field network. We show that when the fading distribution is regularly varying with index in (−1, 0) or the near-field path loss exponent β 0 is larger than the network dimension d, both coverage and capacity saturate to a constant value in the ultra-dense regime. When the fading distribution is less heavy-tailed and when β 0 < d, both coverage and capacity are maximized at some finite density. Finally, our results show that path loss and fading have interchangeable effects on the tail behavior of SINR, coverage probability and capacity, extending previous results using dual slope path loss model and Rayleigh fading.

APPENDIX A PROOF OF PROPOSITION 2
Using l(r) given in (1), we havē where I k (t) := R k+1 R kF m A k r β k t G(dr). (i) For β k > 0: integration by parts withF m (A k r β k t) and G(dr) for I k yields , which reduces to (8) after change of variable u = A k r β k t and applying the condition A k R β k k+1 = A k+1 R β k+1 k+1 = a k+1 due to (4). On the other hand, applying again (4), Hence, substituting (12) back to (11) yields (9) with k 0 = 0.

APPENDIX B PROOF OF THEOREM 1
Due to space limitations, we only give the proof for the case ofF m ∈ R −α for α ∈ [0, ∞). The proof for the cases F m ∈ R −∞ andF m = o(H), H ∈ R −∞ are similar and would be provided in a longer version of this paper.
F m can be represented asF m (x) ∼ x −α L(x) for some L ∈ R 0 . Then, by the monotone density theorem [4], [10], the density function f m of F m can be written as f m (t) ∼ αt −α−1 L(t) as t → ∞.


extfieldsofstudy:
Computer Science
Medicine

text:
Beyond connectedness: why pairwise metrics cannot capture community stability

Abstract The connectedness of species in a trophic web has long been a key structural characteristic for both theoreticians and empiricists in their understanding of community stability. In the past decades, there has been a shift from focussing on determining the number of interactions to taking into account their relative strengths. The question is: How do the strengths of the interactions determine the stability of a community? Recently, a metric has been proposed which compares the stability of observed communities in terms of the strength of three‐ and two‐link feedback loops (cycles of interaction strengths). However, it has also been suggested that we do not need to go beyond the pairwise structure of interactions to capture stability. Here, we directly compare the performance of the feedback and pairwise metrics. Using observed food‐web structures, we show that the pairwise metric does not work as a comparator of stability and is many orders of magnitude away from the actual stability values. We argue that metrics based on pairwise‐strength information cannot capture the complex organization of strong and weak links in a community, which is essential for system stability.

2015; Neutel & Thorne, 2014;Neutel et al., 2002Neutel et al., , 2007. Various studies have suggested alternative connectance measures which incorporate the strength of interactions (Banašek-Richter et al., 2009;Bersier et al., 2002;Ulanowicz, 1997;Van Altena, Hemerik, & de Ruiter, 2016). Furthermore, it has been argued that in order to understand community stability, we need to look at the feedback structure formed by the interactions (Levins, 1974) and quantify critical feedback loops (Neutel et al., 2002). Feedback loops are cycles of causal effects (Levins, 1974). In particular, the strength of three-link loops has been shown to be key to stability (Mitchell & Neutel, 2012;Neutel et al., 2007), and recently, a metric has been proposed that compares the stability of observed trophic networks in terms of the strength of the three-link relative to two-link feedback loops in a system (Neutel & Thorne, 2014). The two-link loops in trophic networks represent the product of the effect of a predator on a prey (negative link) and the reciprocal effect of this prey on its predator (positive link). The three-link loops are loops in the smallest omnivorous structures [also called intraguild predation (Holt & Huxel, 2007), between a predator, an intermediate prey-predator, and the shared prey of this intermediate and its predator]. These structures form positive (one positive and two negative links) and negative (one negative and two positive links) three-link loops, quantified as products of the three effects (Levins, 1974). The understanding in terms of key feedback loops has revealed that it is not network complexity (the number of species or their connectance) which puts constraints on system stability, but the energy-flow and biomass distribution in the trophic pyramid (Neutel et al., 2002). Specifically, it has shown how increased predation pressure over trophic levels leads to less stability (Neutel & Thorne, 2014;Neutel et al., 2007).
However, it has also been suggested that in order to capture the stability of empirical trophic networks, one does not need to go beyond the pairwise interactions (Smith, Sander, Barabás, & Allesina, 2015;Tang, Pawar, & Allesina, 2014). Commenting on Neutel and Thorne (2014), Smith et al. (2015) argue that the metric proposed by Tang et al. (2014), which is based on random matrix theory (Allesina & Tang, 2012;May, 1972) and uses pairwise information of the interaction strengths, in the form of the correlation between effects of predators on prey and vice versa, will be a better estimator of stability.
They imply that the match between the feedback metric and system stability found by Neutel and Thorne (2014) depends on the particular data set, obtained using a scaling procedure to make the interaction strengths dimensionless.
Here, we compare the ability of these two recently proposed metrics to explain local stability of the observed food-web structures studied by Neutel and Thorne (2014). First, we take the original, observed interaction strengths (Jacobian matrix elements, sensu May (1972); see also Berlow et al., 2004, table 1) and apply the feedback metric and the pairwise metric to these data. We then apply both metrics to the scaled data set used by Neutel and Thorne (2014). The scaling was introduced by Neutel and Thorne (2014) to translate the observed structure in the intraspecific interaction strengths (diagonal matrix elements) into the off-diagonal structure, in order to analyze the feedback structure without losing the intraspecific information. Next, we parameterize the same observed food-web structures with synthetic interaction strengths, first with an asymmetry within predator-prey pairs of interaction strengths, and then with completely random (symmetric) strengths, to investigate to what extent the results depended on the empirical parameterizations. Finally, we perform a disturbance experiment with the empirical data, in the example of Yodzis (1981), where we disrupt the empirical patterning of interaction strengths by randomly swapping pairs of predator-prey interaction strengths in the matrices. We do this to show to what extent the metrics are able to explain the impact of the empirical organization of interaction strengths on community stability.

| Empirical food webs
Our local stability analysis was performed on Jacobian community matrix models (linearizations of systems of differential equations) of the same food-web structures as were used for the feedback analysis in Neutel and Thorne (2014). These were 23 observed food webs (Neutel & Thorne, 2014, table S3): two Antarctic food webs with interaction strengths quantified from independent flux observations (Neutel & Thorne, 2014, 2016b and 21 soil food webs with interaction strengths quantified from inferred fluxes based on time-averaged biomass observations (de Ruiter et al., 1995;de Ruiter, Neutel and Moore 2016;Neutel et al., 2007Neutel et al., , 2016. Our analysis was on the 23 trophic networks (+/− structure, consumer-resource, or predatorprey interactions) in these food webs, obtained by removing the detritus row and column from the matrices.

| Underlying dynamics of the populations
The fluxes between the populations X i (with X referring to its biomass) of each population i = 1 ··· n in a food web were described by: where f i (X h ) is the functional response in a consumer, r i is the intrinsic growth rate, m i is the intrinsic loss rate (we assume net intrinsic growth for basal species and r i = 0 for nonbasal species), c ii is a proportionality constant referring to intraspecific competition, and e hi is a biomass conversion efficiency.
We assumed linear functional responses in this study (following Neutel & Thorne, 2014). However, the community matrices with underlying linear functional responses can be easily translated into ones based on nonlinear responses, and the results are robust to these other types of functional response (see Neutel & Thorne, 2016a).

| Parameterization of Jacobian community matrices
The interaction strengths between the populations are the elements of the Jacobian community matrix, a linearization of the system around the nontrivial equilibrium (where each species has a positive population density). Thus, they are the partial derivatives of the population growth equations (dimension per time) evaluated at equilibrium (May, 1973). Using equation (2), the elements of the community matrix Α are effects of predator j on prey i, ij = −c ij X * i ; effects of prey h on consumer i, ih = e hi c hi X * i ; and intraspecific effects, . Thus, the negative effects of predators on prey are the feeding rates of a predator on its prey divided by predator biomass, and the positive effects of prey on their predators are predator growth rates divided by prey biomass (Pimm, 1982;de Ruiter et al., 1995;Yodzis, 1989).
The interspecific interaction strengths of the Antarctic food webs were quantified from direct flux observations (Neutel & Thorne, 2014, 2016b, and those of the 21 soil food webs were quantified from inferred fluxes based on time-averaged biomass observations (de Ruiter et al., 1995;de Ruiter et al. 2016;Neutel et al., 2007Neutel et al., , 2016. The intraspecific interaction strengths (diagonal elements) were not obtained from directly observed fluxes, but the observations provided upper bounds. The rationale is as follows: For a given food web in equilibrium, total loss for each population equals total gain. Growth rates and predatory loss rates of each population were known; hence, nonpredatory loss rates were also known, because the systems were in equilibrium. This total nonpredatory loss rate consists of intrinsic death and intraspecific competition: The amount of intraspecific competition is hence contained within the energetic boundaries of the system 0 ≥ c ii X * i ≥ d i . The upper bounds were used to quantify the diagonal elements of (un-normalized) community matrix Following Neutel & Thorne, 2014; interaction strengths were scaled by dividing each row in community matrix Α by the absolute value of its respective diagonal element, ij ∕ | | ii | | , which resulted in timeindependent and dimensionless matrices Γ. This scaling procedure was introduced by Neutel and Thorne (2014) to translate the diagonal structure of the matrix into the off-diagonal structure, and obtain an eigenvalue which, for their observed food webs, was equivalent to a critical value of intraspecific competition for stability [specifically, it represents the proportion of total nonpredatory loss needed for stability; see Neutel et al. (2002)].

| Determination of stability
The diagonal elements of the Jacobian and scaled matrices were then set at zero, obtaining matrices Α 0 and Γ 0 . System stability was determined as the largest real part of the eigenvalues of these matrices, λ d .
By definition, with all diagonal elements set at zero, then λ d ≥ 0; that is, the systems need some level of self-damping in order to be stable, and −λ d is the amount of self-damping needed for stability. In the case of the normalized matrix Γ 0 , λ d has a biological meaning and indicates a tipping point. It represents a critical level of intraspecific competition of the populations as a proportion of the maximum possible intraspecific competition (the upper bound of the diagonal elements) (Neutel & Thorne, 2014). In the case of the Jacobian matrix Α 0 , λ d is related to the timescales of the systems and is not easily interpretable biologically given the different intraspecific interaction strengths of the populations. It is the opposite of a system's resilience. The inverse of λ d of Α 0 is the time with which the system moves away from the equilibrium, after a very small disturbance.

| Synthetic parameterization of community matrices
For the synthetic parameterization of the community matrices, the empirical values of the nonzero off-diagonal elements were first replaced by values randomly drawn from uniform distributions (−10, 0) for effects of predators on prey and (0, 0.1) for effects of prey on predators (following Pimm & Lawton, 1978; see also Neutel & Thorne, 2014). This procedure was then repeated without the asymmetry in size ranges, drawing values from uniform distributions (−1, 0) and (0, 1) (following May, 1972; see also Neutel & Thorne, 2014).

| Pairwise disturbance experiment
To show the effect of the patterning of interaction strengths on stability, we performed a disturbance experiment, following Yodzis (1981).
For each empirical community matrix Α 0 , the pairs of nonzero offdiagonal elements were randomly permuted. This preserved the sign structure and the pairwise structure of the interaction strengths of the original matrix.

| Feedback metric
The metric proposed by Neutel and Thorne (2014) expresses a ratio between three-link and two-link feedback: 3 , where a 2 and a 3 are coefficients of the characteristic polynomial of the community matrix.
In a matrix with zero-diagonal elements, the second coefficient, a 2 , represents the sum of all the two-link feedback loops (F 2 ), resulting from the pairs of predator-prey interactions, which are by definition negative: In community matrix Α 0 , F 2 = ∑ ij ji (the same holds for normalized matrix Γ 0 ). The third coefficient, a 3, in zero-diagonal matrices,

| Pairwise metric
The metric proposed by Tang et al. (2014) quantifies the overall correlation between effects of predators on prey and vice versa: where S is the number of "species," E is the mean of the off-diagonal elements of the community matrix, V is their variance, and ρ is the overall pairwise correlation between the elements of the community matrix (α ij , α ji ) i≠j (Tang et al., 2014).

| RESULTS
We found a strong correlation between our feedback metric and stability for the 23 empirical food webs parameterized with the original interaction strengths (observed Jacobian community matrices) (Fig. 1A). The pairwise metric showed no relation with food-web stability, neither for the original, nor for the scaled interaction strengths, and underestimated the stability by many orders of magnitude ( Fig. 1B and D), while the feedback metric explained both data sets equally well ( Fig. 1A and C).
When we parameterized the same interactions in these food webs with random-type values, imposing a simple asymmetry between negative and positive interaction strengths (Pimm & Lawton, 1978; see also Neutel & Thorne, 2014), both metrics showed a relation with food-web stability, but the feedback metric outperformed the pairwise metric ( Fig. 2A and B). We then calculated system stability for different parameterizations (sampling from the two size distributions, as above) of the same food-web structure. Thus, we removed the effect of system size and connectance on stability. This made clear that the pairwise metric was not able to explain the relation between the structure and stability of a system, in contrast to the feedback metric ( Fig. 2C and D).
Next, we repeated this procedure, using a symmetry between negative and positive interaction strengths (following May, 1972; see also Neutel & Thorne, 2014). For these random parameterizations drawn from symmetric intervals, the feedback metric did not show any relation with food-web stability, neither for the 23 webs, nor for different parameterizations of a single web structure ( Fig. 3A and C), while the pairwise metric showed some correlation ( Fig. 3B and D).
Finally, we analyzed the effect of the empirical organization of the interaction strength values on stability, by disturbing this organization through randomly permuting pairs of interaction strengths (following Yodzis, 1981). The feedback metric was unable to explain the resulting loss of organization in a satisfactory way, although it did show some correlation with stability, within a diversity of pattern (Fig. 4A).
However, by definition the pairwise metric could not explain any difference in organization (Fig. 4B). Stability (λ d ) of the Antarctic dry (closed circle) and wet (closed square) tundra ecosystems and 21 soil food webs (cross signs) (see Neutel & Thorne, 2014, table S3;de Ruiter, Neutel, & Moore, 2016;Neutel & Thorne, 2016b;Neutel et al., 2016).  Paine, 1988Paine, , 1992Polis & Strong, 1996;de Ruiter et al., 1995;Wootton, 1994;Yodzis, 1981) merits the question of how much of the organization of interaction strengths has to be taken into account to capture community stability. Smith et al. (2015) argue that the metric proposed by Tang et al. (2014), which quantifies pairwise connectedness, will provide a better estimate of food-web stability than the metric proposed by Neutel and Thorne (2014), which quantifies three-link and two-link feedback loops and imply that we do not F I G U R E 2 Comparison as in Fig. 1, for synthetic, asymmetric parameterizations of the interaction strengths. (A, B) Food-web structures as in Fig. 1, but with nonzero matrix element values randomly drawn from asymmetric intervals (−10, 0) and (0, 0.1) (following Pimm & Lawton, 1978), For food-web structures in the size range for which empirical data are available, Neutel and Thorne's feedback metric (Neutel & Thorne, 2014) is a good comparator of stability, whether the interaction strengths are scaled, as analyzed by Neutel and Thorne (2014), or not. Furthermore, even for synthetic parameterizations with an asymmetry between effects of predators on prey and vice versa, the feedback metric is a better comparator and estimator of stability than the pairwise metric. This is remarkable, because the pairwise metric has been particularly aimed at dealing with this type of synthetic parameterizations (Tang et al., 2014). Our application of both metrics to different parameterizations of a single food-web structure shows that the pairwise metric is not able to capture the structure of a system (Fig. 2C). The correlation between the pairwise metric and comparative stability of the different food-web structures is an artifact of the synthetic parameter values-the metric effectively measures system size. Furthermore, this comparison of different synthetic asymmetric parameterizations of a single web (Fig. 2C) also shows that Neutel and Thorne's feedback metric cannot be approximated by a connectance-based analogue, such as suggested by Smith et al. (2015). Their approximation is a simplification of the feedback metric resulting from assumptions on random parameter values. It cannot, by definition, explain the differences in stability shown in Fig. 2C, because all these model samples share the same connectance.

| DISCUSSION
Only parameterizations sampled randomly from symmetric intervals for predator-prey and prey-predator effects are not captured by the feedback metric. This confirms the findings of Neutel and Thorne (2014), who show that it is the dominance of positive feedback in the three-link loops, which underlies the relation between the feedback metric and system stability. As they show, this dominance of positive feedback is brought about by the well-known asymmetry within pairs of predator-prey interaction strengths (see Pimm &Lawton, 1978 andde Ruiter et al., 1995).
When we performed a pairwise disturbance of the empirically parameterized food webs (following Yodzis, 1981), the feedback metric, while showing some correlation within a diversity of pattern, was unable to explain the effects on stability in a satisfactory way, indicating that more understanding is needed. However, pairwise metrics do not provide an alternative, because they cannot capture the complex organization of strong and weak links in a trophic network. It is logically impossible for any pairwise metric (Allesina & Tang, 2012;May, 1972;Tang et al., 2014) to explain the effect on stability of a pairwise disturbance experiment (Yodzis, 1981). For a better understanding of how organization affects stability, it may be necessary to look at the spectrum of strengths of three-and two-link loops, instead of just the total strength of three-link versus two-link loops (see Neutel & Thorne, 2014;Neutel et al., 2002).
Quantifying the feedback structure of ecological networks is not only necessary to compare the stability of ecological systems, but also provides a way forward to understand the underlying assumptions on the functionality and adaptive strategies of populations (Neutel & Thorne, 2016a).
It should be emphasized that the empirical data on biomass and energy flow for each of the food webs in this study are of the highest quality available, and were obtained not with one specific method for all the webs, but with different methodologies (Neutel & Thorne, 2014).
At present, such data only exist for systems in the size range presented here, of 10-30 trophic groups. There is a pressing need to obtain realistic, empirical, data for a wider and larger range of systems, to test the feedback metric and, if needed, make further improvements. This heuristic approach will prevent us from being wrong-footed by an artificial generality brought about by a random parameter space (Neutel & Thorne, 2014). It is already clear from the existing empirical evidence, however, that in order to capture the "organized complexity" of communities which characterizes the functioning of real ecosystems, the only way forward is to take the step beyond pairwise interactions.
F I G U R E 4 Stability (λ d ) after disruption of the empirical patterning of interaction strengths by random permutation of the nonzero matrix element pairs ( ij , ji ) of Α 0 (following Yodzis, 1981), using the Jacobian matrix of the Antarctic dry tundra ecosystem (for stability of the intact pattern, see closed circle in Fig. 1A SV(1 + ) − E (Tang et al., 2014). Note that in these randomly permuted webs, the topology, sign structure, and pairwise structure of the empirical food web stayed intact


Hardware-in-Loop-Simulator for InnoSAT Attitude Control System

After launching, the initial condition of satellite is unknown and tends to be in a tumbling state. At this moment, the satellite needs to reduce the tumbling rate so that the satellite can enter a stable and unruffled state. The satellite also must maintain a certain attitude while orbiting in order to allow precise pointing of the antenna toward the earth. In this study, a hardware-in-loopsimulator was devised for the purpose of improving the design and verifying attitude control concepts for Innovative Satellite (InnoSAT) system. A new software architecture and algorithm was developed based on the controller, InnoSAT plant, actuator and sensor. Firstly, the controller, actuator and sensor was modelled in the MATLAB program together with InnoSAT plant. The actuator and sensor were assumed to be ideal. However, some properties of the actuator and sensor were simulated in the software simulator. If the software simulation performed satisfactorily, the control algorithm will be embedded into Rabbit Micro Controller (RCM4100) using Dynamic C language. This is the part where the hardware simulation is developed which is creating hardware-inloop-simulation technique for verification of InnoSAT Attitude Control System (ACS) performance. The satellite simulator was tested using simulated data in order to observe the performances of the controller in real time simulation. The results show that the InnoSAT ACS simulator can produce as good result as a MATLAB simulation for the InnoSAT plants. From the results, it is adequate to verify that the developed protocol working satisfyingly and seems to be possible to be implemented on the actual flight. Keywords— innovative satellite, attitude control system, rabbit micro controller, hardware-in-loop-simulation.

I. INTRODUCTION
Nowadays simulations are widely used in the science and technology research, because they provide the ability to complete virtual experiments approximately same as the real ones. It also requires low cost in building simulation systems whose environment can be reconstructed many times. The satellite attitude control simulator (ACS) is a test bench used to evaluate the performance and robustness of the attitude control design. Typically, different simulators are developed throughout the satellite development to support validation and verification activities. There are many advancements that have been made in this research field and many constraints have been dealt with. Even so, there is still room for improvement in the development of the satellite attitude control systems. Therefore, many universities and research centres have developed similar facilities in the study of satellite control. For example, the development of 3-axis motion simulator [1], [2], autonomous docking [3]- [7], real-time hardware simulator [8]- [11] and spacecraft attitude dynamics simulator [12], [13].
This research proposes a novel approach of satellite simulator design where the simulator will be in the form of both software and hardware. A software simulator will represent the satellite dynamics model, incorporating all the operating conditions of the satellite in orbit. The control algorithm for ACS will be implemented on microcontroller unit using Rabbit Micro Controller (RCM4100). This as a whole acts as a hardware simulator that will control the Innovative Satellite (InnoSAT) plant which is presented in the software simulator. The hardware simulator design includes all necessary interfaces function as well as a communication link to the other parts of InnoSAT. Hardware-in-the-loop simulation technique allows testing a controller within a simulated environment, thereby rastically reducing restrictions on cost, duration, safety and feasibility [14]. The control system is the main part in HILS (hardwarein-loop-simulation), which is in-charge of combining hardware and software and making them work together in pace [15], [16].

A. Hardware-in-Loop-Simulation Technique
Hardware-in-loop-simulation (HILS) is a real-time test technology which is used to test one or a set of remaining system components in a comprehensive, cost effective and repeatable manner. HILS is often used in the development and testing of embedded systems, when those systems cannot be tested easily thoroughly and repeatedly in their operational environments. Instead of being connected to the real equipment, it is actually connected to the real time simulation. HILS test concept can be applied to a wide variety of systems, from relatively simple devices such as a room temperature controller to complex systems like an aircraft flight control system. HILS has historically been used in the development and testing of complex and costly systems such as military tactical missiles, aircraft flight control systems, satellite control systems and nuclear reactor controllers [15].
In this research, a Rabbit Micro Controller (RCM4100) was used to implement an attitude control algorithm for InnoSAT system as a hardware simulator. A computer on the other hand, simulated the attitude dynamics of the satellite as a software simulator. The software simulator integrates the dynamics equations and sends the output responses of the satellite to the RCM4100 using serial communication. The output responses were used in the control algorithm to generate necessary control signals. Closed loop simulations can be made to work in real time to simulate the dynamic behaviour of the satellite system with the ACS to control its attitude. It is important that the ANC controller can work properly with the RCM4100 microcontroller board because it will be used for attitude control system of the InnoSAT plant. Fig. 1 shows a general block diagram of HILS technique for InnoSAT plant that consists of sensor and actuator. A software simulator represents the satellite dynamics model, incorporating all the operating conditions of the satellite in orbit. Fig. 2 shows the connection of satellite simulator for InnoSAT ACS system.

B. Requirements
The RCM4100 series is the first of the next-generation core modules that takes advantage of the new Rabbit® 4000 features such as hardware DMA, clock speeds of up to 60 MHz, I/O lines shared with up to six serial ports and four levels of alternate pin functions. It has a generous memory size (512K flash memory, 256K data SRAM) that allows large programs with tens of thousands of lines of code and substantial data to be stored. In this HILS technique, there is a need of a standard Personal Computer (PC) to be used as a satellite model that represents the InnoSAT dynamic behaviour. This PC will act as a software simulator in order to perform the function of InnoSAT attitude control simulator. Communication between the computer and RCM4100 takes place in the beginning of every sample period (1 s) of the system. Thus, both the computer and the RCM4100 must be able to complete necessary computations in less than this time. Since the given sample time is quite large, both the RCM4100 and computer fulfil this requirement. They rely on serial communication for transmission of bytes, representing state variables and actuator signals.

C. RCM4100 and Computer Interface
The computer and the RCM4100 use the standard RS232 protocol to send and receive data during simulation. Both these devices have a Universal Asynchronous Receiver Transmitter (UART). An important aspect concerning the simulation is the baud rate used to transmit data. The RCM4100 may operate at many different baud rates. In this simulation, the baud rate used for data transmission is 115,200 bits per second (bps). High speed data transmission is needed to support the wide range data, which is in a floating point form. The RCM4100 and the computer will perform a wide range data which are in bidirectional data transmission and need a data management system in order to send/receive to/from the determined destination. To prevent the losses or mismatches of the transmitted data, the data are managed using a match-pattern procedure where the concept of header and footer are used along with the actual data which is in between them. Fig. 3 shows the concept of match-pattern procedure. The microcontroller or computer will start sending a different header before sending the real data which represent the data for satellite orientation and closed with a special character for the footer. For example, header using character 'R' for roll data, 'P' for pitch data and 'Y' for yaw data and character '#' is used for the footer. This procedure is used in order to make sure the RCM4100 and computer receive the correct data to be processed. where K_p (t) is a varying gain, u_s's(t) are the controller output and u_d's(t) are the constant disturbance torque. Meanwhile, x(t),y(t)and z(t) are the outputs from InnoSAT plant for Roll, Pitch and Yaw axes.
The InnoSAT plants has been tested in condition of unity gain by using step input as shown in Fig. 4. In order to evaluate the performance of the controller and to test the capability of the controller to adapt sudden changes due to the satellite rotation, the InnoSAT plant was excited by a square wave input reference with the amplitude of one and a frequency corresponding to 1000 number of data as shown in Fig. 5. Fig. 4 shows the zoom out output response of MATLAB simulation and HILS for step input, while Fig. 5 shows the output response and model following error for square wave input. Based on the two figures, it can be clearly seen that the output response of HILS for all axes has almost the same response as MATLAB simulation. It is quite difficult to see the difference in the output response between MATLAB simulation and HILS. Therefore, the performance analyses of the output responses have been done by plotting the residual error and calculating the Mean Square Error (MSE) value. Residual errors are plotted in order to see whether the MSE calculations have misleading values. Based on the value of the MSE as shown in Table I and Table II and residual error plotting in Fig. 5, it is clearly proved that there is a close match between the two simulations. The differential value of MSE for the both simulations is small thus proving satisfactory performance of the ACS operating in real time environment for InnoSAT plant.

IV. CONCLUSIONS
The ACS control algorithm in RCM4100 and the dynamics model of InnoSAT plant in PC have been tested using real-time hardware-in-loop-simulation (HILS) technique. The performance of each part of the hardware simulator were tested and modified repeatedly until the results were similar to the MATLAB simulation results. Finally, it serves (after adaptation) as a hardware-in-the-loop simulator and test platform for full system verification and on-orbit operations support tool. The results show that the InnoSAT ACS HIL simulator can produce as good result as MATLAB simulation of InnoSAT plants. The calculated MSE values also show that there are a close match between HILS and MATLAB simulation, where the MSEs different value are small. From both results, it is enough to verify that the developed protocol working satisfyingly and seems to be possible to be implemented on the actual flight. Now, the controller can be 'plug and play' in the real InnoSAT plant.


Beyond Caption To Narrative: Video Captioning With Multiple Sentences

Recent advances in image captioning task have led to increasing interests in video captioning task. However, most works on video captioning are focused on generating single input of aggregated features, which hardly deviates from image captioning process and does not fully take advantage of dynamic contents present in videos. We attempt to generate video captions that convey richer contents by temporally segmenting the video with action localization, generating multiple captions from multiple frames, and connecting them with natural language processing techniques, in order to generate a story-like caption. We show that our proposed method can generate captions that are richer in contents and can compete with state-of-the-art method without explicitly using video-level features as input.

INTRODUCTION
Image captioning task has gained an increasing amount of attention with successful application of convolutional neural networks (CNN) and recurrent neural networks (RNN), setting new benchmarks that are frequently comparable to human-written captions [1][2][3][4]. Successes in image captioning task have inevitably led to an increasing amount of interests in video captioning task. Previous works dealing with video captioning task have attempted to utilize various type of features that are unique to videos. However, most of them were focused on generating caption from single input vector of aggregated features, which hardly deviates from image captioning process and does not take full advantage of richer contents present in videos.
Visual elements are hardly stationary in videos, which inevitably leads to a series of events, and as such, caption generated from single aggregated input can be insufficient for fully conveying the dynamic contents of videos. It consequently follows that we need to account for each event that is happening in the video with multiple sentences. Segmentation of videos is an intuitive method through which we can generate multiple sentences, provided that we have a reasonable criteria for segmentation. One feasible way is to make use  [5,6]. Thus, while effective in highly edited videos such as movie clips, it is difficult to exert an equal amount of efficiency in videos of other domains where scene or shot transition is less frequent. Even in videos with frequent editing, shot or scene transition does not always correspond to transition of events. For example, it is counter-intuitive to segment repeated counter-shot editing of two people talking to each other and refer to it as separate events. We thus attempt a segmentation of videos based on action localization, as change of action can be a strong indicator of a distinct event.
Segmentation of videos allows us to work with multiple frames, with which we can generate separate captions following the conventional image captioning procedures. However, these captions are initially independent of each other, bearing no contextual relevance. Thus, simply concatenating the sentences leads to a highly awkward and artificial-looking passage. We employ a series of simple natural language processing techniques to connect the sentences smoothly, enabling a generation of more natural, human-like captions, resembling the characteristics of narratives. Fig. 1 shows the overall workflow of our proposed method. We demonstrate through experiments that our method, even without explicitly using video-level features as input, can generate captions conveying richer contents, with comparable performance to current state-of-the-art on evaluation metrics.

RELATED WORK
Human action recognition in videos has been actively studied. The typical pipeline to obtain video features is to extract local features and aggregate them. Rich descriptors, such as HOG [7], HOF [8], and MBH [9], and aggregating these local features with Fisher Vector [10] have demonstrated successful performances. Extracting local features along improved Dense Trajectory (iDT) [11], which compensates for camera motion, can obtain impressive results in action recognition. Recently, deep CNN features have been employed in a variety of fields and demonstrated successes [12,13]. Yet, while the state-of-the-art method [14] in action recognition uses CNN, it also depends on iDT. Spatio-temporal localization has also been attempted using such representations of videos. Most of the state-of-the-art works on action localization use temporal sliding window approach [15,16]. In our case, it suffices to temporally segment the videos based on actions, and we thus localize the actions in temporal axis only.
Works on video captioning have attempted to directly apply a variety of features uniquely present in videos to caption generation. Pan et al. [17] introduced LSTM-E, which simultaneously takes learning of LSTM and visual-semantic embedding into account. Shetty et al. [18], winner of Describing and Understanding Video & The Large Scale Movie Description Challenge (LSMDC) at ICCV 2015, extracted features at three levels. At video level, they extract Dense Trajectory (DT) [19], HOG, HOF, MBH (x and y) and generate five histograms of 1000 dimensions. Then, the keyframe features from the middle frame of the video are extracted via VGG-16, VGG-19 [20], and GoogLeNet [21]. Finally, content features are extracted by training a SVM on MS COCO 80-object classification. While competitive, a few potential drawbacks can be pointed out. First, the video representation becomes highdimensional. Also, it is questionable whether middle frame is always representative of the entire video. It may be true for short videos, but as the duration of video gets longer, its representativeness is inevitably prone to decline. Lastly, in spite of the relatively complex overall pipeline, its caption generation process hardly differs from image captioning in that it ends up with a single representation, which may not reflect rich contents unique in videos.
In terms of the story-like characteristic of the outcome, Zhu et al. [22] are more intimate to our motivation. By aligning scenes with subtitles, and subtitles with passages in the books, they were able to generate story-like description of the scenes. This, however, has an obvious drawback that both books and movies should exist, along with subtitles. Alternatively, one may be able to rely on story-like, human-written ground truth captions for images or videos, but such data are not yet sufficiently available in the research community, and are expensive to collect. Since our work treats the frames from each segment independently, we do not need to rely on additional textual data to generate a story-like caption.

PROPOSED METHOD
We first describe our mechanism of temporal segmentation based on action localization in Sec. 3.1. Middle frames are extracted from each resulting segment, and captions are generated for each frame. These captions are connected via two steps of natural language processing, namely coreference resolution and connective word generation, which we explain in Sec. 3.2 and Sec. 3.3, respectively.

Temporal Segmentation with Action Localization
It has been argued that features extracted from pre-trained CNN [23,24] or color channels [25] are more appropriate for capturing contextual information rather than localizing actions precisely. We thus employ a sliding window method and motion features only for temporal localization, following the winner's approach in the temporal action detection task of THUMOS 2014 challenge [26]. In order to extract motion features, we use improved Dense Trajectories (iDT) [11]. Since datasets we work on (Montreal [27] and MPII [28]) do not contain time information, it is difficult to learn the actions directly from these datasets. However, since our goal is simply to segment the videos, predicting the action class is not a prerequisite. We thus rely on UCF 101 [29] to learn the actions. Although it cannot be said that action classes in UCF 101 cover all actions (and verbs in ground truths) in Montreal or MPII, it is still possible to obtain class scores using a classifier trained on UCF 101. Since our goal is to temporally segment the video based on action change, rather than specifying the action, we apply the classifier trained on UCF 101 training data to test data of our target datasets.
Following [15], we employ a temporal sliding window approach and non-maximum suppression for temporal action localization. We first use temporal sliding windows of length 30, 60, 90, and 120 frames, and slide the windows in steps of 30 frames. We then re-score the detected windows with nonmaximum suppression to remove overlapping. Note that if we were to use all detected windows, then minor movements that do not quite constitute a clear action will be localized as well, leading to unnecessary, redundant generation of captions. We thus set a score threshold so that windows with score below it are not considered to contain any action. We segment the videos so that each segment consists of adjacent windows of the same action class. Fig. 2 shows the average number of segments per video depending on the score threshold. Although we want to extract multiple frames from each video, too many frames will result in excessively wordy and repetitive caption. We thus set our score threshold as -0.5 for Montreal dataset, which is just over 2 segments per video. MPII dataset is relatively shorter in length compared to Montreal, and all of our thresholds did not exceed 2 segments per video. We choose threshold of -1.0 for MPII as it closely approaches 2 frames per video. Note that, since we assumed the number of segments to be zero when no action was detected, the actual number of segments is a bit higher than shown on the graph. In case no action was detected in the entire video, we simply used the middle frame.

Backward Coreference Resolution
As was discussed in Sec. 1, generated captions from multiple frames of a video are initially independent of each other with no contextual relevance. As the first step to smoothly connect them, we first apply backward coreference resolution. In usual coreference resolution, given a passage A man is with a plate. He is sitting with it. anaphors are resolved to their corresponding antecedents so that 'he' is linked to a 'a man,' and 'it' to 'a plate.' In our case, on the contrary, there are no anaphora but repeated appearances of to-be-antecedent noun phrases. Thus, given a passage A man is with a plate. A man is sitting with a plate. we want to link the coreferences, and convert the later ones to appropriate pronouns.
Such task is rare even in natural language processing field, and to our knowledge, there exists no tool to specifically perform this task. We implement the task by using gender annotator from Stanford CoreNLP [30], which assigns likely gender to tokens, in order to deal with singular human subjects. Then we run coreference resolution for non-singular or non-human references, with part-of-speech tagger to deal with plurals (NNS/NNPS), and with lemmatization, in order to avoid conflicts with tenses [31]('watches' for noun plural vs. 'watches' as a third person verb), aided by WordNet [32].

Connective Word Generation
Another key point to generating human-like 'narrative' from multiple sentences is to find appropriate transition, or connective words, such as 'then.' One way to accomplish this may be to train a classifier for the connective word based on vectorized adjacent sentences. This, however, is not very practical as it is hard to determine the number of classes, and collecting

Ground Truth
With the table gone, all of the girls sit in their same seats, their trays on their laps.

Mid-frame
A man and a woman standing next to each other.   training data is expensive, requiring an extensive usage of a parser. We thus tackle the task in an unsupervised way. We collected 500 instances of adjacent sentences from tagged version of Wikicorpus [33], in which the second sentence starts with a connective word. Specifically, we ran a CKY parser for PCFG trained on Penn Treebank [34], and retained the cases in which the second sentence starts with a single word of adjective (JJ) or adverb (RB) tag as a part of an adjective phrase (AJP), followed directly by full sentence (S) consisting of noun phrase (NP) and verb phrase (VP). Collected instances, excluding the connective word, are converted to 300-dimensional vector by Sentence2Vec [35]. The rest is a simple matching of vectorizing the adjacent sentences of generated captions in the same way, finding the closest instance by L2 distance, and inserting the connective word present in the instance to the captions.

EXPERIMENT
We first apply our method to test split of Montreal dataset and MPII dataset, which amount to 11,529 video clips. Note that train and validation splits of both datasets were never used throughout our experiment. As our first baseline, we simply generate captions from CNN features of single middle frame of the videos. In order to obtain motion features, we first extract HOG, HOF, and MBH along iDT and encode obtained local descriptors by Fisher Vector (FV) [10]. We reduce the dimension of each descriptor by a factor of 2 with PCA. We then assign descriptors to 256 components of FV and obtain video features. Finally, we apply power and L2-normalization to video features. As classifier, we employ one-vs-rest linear SVM and set C = 100.
After segmentation according to action localization is complete, we extract the middle frame from each segment, and extract 4096-dimensional CNN features from the second fully-connected layer (fc7) of VGG trained on ImageNet [36] using Caffe framework [37]. These features are passed onto LSTM [38] trained on MS COCO dataset [39] with beam size 1, so that descriptive caption for each frame can be generated. Once the captions are generated, the remaining step is simply to connect them smoothly according to the method specified in Sec. 3.2 and Sec. 3.3 Note that video-level features are used only for the sake of temporal segmentation, and the inputs for captioning are simply CNN features from multiple frames. Neither were there any need for additional textual data accompanying the videos. Table 1 shows our method's performance on automatic evaluation metrics [40][41][42] for each dataset along with baseline. Our method clearly outperforms the baseline across all datasets and all metrics. Fig. 3 shows an example of generated story-like caption, along with ground truth and singleframe captions. We also compare our method to one of the state-of-the-art methods in video captioning, the winner of LSMDC challenge [18], as shown in Table 2. It should be first noted that, in our case, the average length actually refers to the average length of the entire caption consisting of multiple sentences. It is thus natural that ours is about 4 times longer than the compared method, consequently containing more contents. The question is whether having more contents implies more reflection of the original contents present in the video, or simply more noise and less precision. Results on the metrics show that our method is comparable to the stateof-the-art, in spite of the increased lengths and risk for noises. Although we were not able to outperform the state-of-the-art method, this shows that our longer caption reflects the contents of the video with roughly the same ratio as the state-ofthe-art method, thus reflecting more of the video contents.
In order to examine how our method performs on video clips of non-movie domain, we applied our method to a subset (138 videos) of Youtube videos listed in Microsoft Video Description Corpus [43]. Since these videos are usually minutes long, we set our score threshold higher at -0.1. Note that ground truth captions are written only on sub-interval of the videos in this dataset, so direct comparison cannot be made. We thus extracted our captions from sub-interval specified in the corpus and compared it to 5 ground truths per video. As shown in Table 1, we were able to outperform single frame approach in most metrics, in spite of longer captions generated. This confirms that our method based on action localization can be applied to videos in which shot or scene transitions occur much less frequently than movie clips. Fig. 4 presents an example caption on one of the videos from MS Video Description Corpus along with ground truth.

CONCLUSION & FUTURE WORK
We proposed a method that generates a story-like video caption from multiple frames by temporal segmentation using action localization, and natural language processing techniques. We demonstrated that our method outperforms single-frame method, while being comparable to current state-of-the-art method, even with longer captions that contain more contents. This was made possible even without explicit usage of videolevel features as input for captioning.
Working on the task, we have come across a few concrete ideas that can potentially improve the result. First, since training an action classifier from an existing dataset limits the number of action classes, it may be a better idea to localize the actions in an unsupervised manner, so that actions not present in the action classes of dataset can also be segmented.
Another potential improvement can be made with face identification. With current pipeline, it is impossible to know whether 'a man' from two different frames refers to the same person or not. In fact, there were cases in which a new character appears, yet our pipeline treats the new character as the the original character who already appeared. Adding face identification to our pipeline can generate a more robust caption, in which a new character is referred to as 'another man' or such.
Finally, applying our method to recently published video annotation datasets [44] will also be an interesting challenge.