1
On Capacity and Delay of Wireless Networks with Node Failures
arXiv:2605.12080v1 [cs.IT] 12 May 2026
Wei Li, Min Sheng, Fellow, IEEE, Junyu Liu, Member, IEEE and Jiandong Li, Fellow, IEEE State Key Laboratory of Integrated Service Networks, Xidian University, Xi’an, Shaanxi, 710071, China Email: [email protected], {junyuliu, yangzheng}@xidian.edu.cn, {msheng,jdli}@mail.xidian.edu.cn
Abstract—One key challenge in designing resilient large-scale wireless ad hoc networks is to understand how random node failures affect fundamental network performance. In this work, q we show that both network capacity and delay scale as Θ n(1−q) , log n where n is the total number of nodes and q is the node failure probability. The network capacity degenerates to the classical result given by P. Gupta and P. R. Kumar when q = 0. Based on these results, we find that even with the same number of nonfaulty nodes, a network with n nodes and node failure probability q has lower network capacity than a failure-free network with n(1 − q) nodes. To compensate for the network capacity loss caused by random node failures, at least ϵ(n, q)nq redundant nodes are required, where ϵ(n, q) > 1. We further prove that the optimal trade-off between network capacity and delay remains O(1) regardless of node failures, implying that high network capacity and low delay cannot be achieved simultaneously. These results demonstrate robustness against stochastic variations in wireless channels. Index Terms—Network capacity, delay, node failures, redundancy node, network topology.
I. I NTRODUCTION Wireless ad hoc networks with self-configuration, selfoptimization, and self-healing capabilities are crucial in emergency response, disaster rescue and military applications, etc [1], [2]. In wireless ad hoc networks, data packets are transported with high probability through the multi-hop transmission strategy, which effectively mitigates intra-network interference and enhances spatial reuse ratio by avoiding longdistance transmissions [3]. One of the necessary conditions for implementing the multi-hop transmission is that the network topology should be connected with probability one, i.e., there is at least one path between any two nodes. In practice, however, the network topology may experience intermittent connectivity due to deteriorating channel conditions, malicious interference, node failures, node mobility, and other factors [4]–[6]. Among these factors, the impact of node failures on the connectivity of network topology is irreversible, which can deteriorate the network traffic-carrying capacity and increase delay. Based on the above analysis, modeling and quantifying the impact of node failures on network capacity, delay, and the trade-off among them is the cornerstone of designing a wireless ad hoc network with resilience. Accurately characterizing the network capacity region and delay of wireless ad hoc networks is challenging, espeically when the number of nodes increases. As an alternative, analyzing the asymptotic scaling behavior of network capacity and delay can also provide insights into the fundamental performance limit of wireless ad hoc networks. Specifically, given that an optimal space-time scheduling strategy is pro√ vided, the network capacity is Θ ( n) bits/s, where n is
the number of nodes [3]. This means that the rate at which all source nodes can successfully transmit data packets to their corresponding destination nodes in the same time slot is √ Θ (1/ n) bits/s. Compared to the direct transmission strategy, the data rate between each source-destination pair can be √ improved from Θ (1/n) to Θ (1/ n) with the help of the multi-hop transmission strategy. Furthermore, the mobilityassisted two-hop scheduling strategy can achieve linear growth in network capacity with respect to the number of nodes, i.e., Θ (n), which would yet result in intolerable delay [7]. This is undesirable for most applications. Following these works, a number of researchers have conducted in-depth studies on the relationship between network capacity and delay from various perspectives. The main results are summarized in Table I. The core is to investigate the asymptotic scaling behavior of network capacity and delay under various networking schemes. Compared to the results in Table I, the networking scheme is the key factor that constrains the asymptotic behavior of network capacity and delay. Designers can enhance network capacity and reduce delay by designing networking schemes that incorporate new dimensions, such as node mobility, redundancy, coding and geometric information, etc. All the aforementioned studies are conducted under the assumption that nodes could always operate well. The results fail to reveal the impact of node failures on network capacity and delay, thereby hindering the design of wireless ad hoc networks with resilience. Recently, the network capacity of wireless ad hoc networks after experiencing zone node failures has been studied in [8]–[10]. It is demonstrated that increasing the connectivity of network topology to combat node failures is feasible √ only when the number of failure regions is less than Θ ( n). It is also pointed out that the order of network capacity, when the network encounters node failures, follows the same asymptotic scaling law as in [3]. From the statistical average perspective, the result obtained using the proof method in [3] is correct. However, those results do not capture the impact of random node failures on the network connectivity and network capacity. To this end, we will quantify this subtle difference from the perspective of network connectivity. We show that this overestimates the network capacity when the deployed wireless ad hoc networks encounter random node failures. Meanwhile, the delay and the optimal trade-off between network capacity and delay are given. The contributions are summarized as follows. •
We derive the asymptotic scaling laws for both network capacity and delay in wireless ad hoc networks with node q . The upper bound on failure probability q as Θ network capacity can be achieved by utilizing multi-hop n(1−q) log n
2
TABLE I N ETWORK C APACITY AND D ELAY IN D IFFERENT N ETWORKING S CHEMES
Networking Scheme
Delay
Ref.
Multi-hop + Mobility
Capacity Θ min{m,n} log3 n
Θ v1
[11]
Multi-hop + Redundant
Θ(1/ log n)
Θ(log n)
[12]
√ Θ( n)
Θ(n2β )
Two-hop
[13]
0≤β≤0.5
Multi-hop + Coding Multi-hop Geometric multi-hop
√ Θ( Dn) √ Θ( n)
n1/3 < D < n [14] √ Θ( n) [15] n Θ log n log Θ v1 [16] log n
transmission strategy. When q = 0, our results degenerate into the classical results in [3]. Based on the above conclusions, increasing redundant nodes is a feasible strategy for both restoring the connectivity of network topology and mitigating node failure randomness. In particular, to q in wireless ad maintain the network capacity at Θ hoc networks with node failures, at least n1 = ϵ(n, q)nq redundant nodes should be deployed, where ϵ(n, q) > 1. • It is shown that the wireless ad hoc networks with n nodes and node failure probability q have lower network capacity than one with n(1−q) nodes without considering node failures, even though both networks contain the same number of non-faulty nodes. For the case with node failures, the loss of network capacity is utilized to mitigate the impact of node failure randomness on the connectivity of network topology, as the expected number of non-faulty nodes is n(1 − q). The numerical results indicate that when q = 0.85, the network capacity loss rates corresponding to n = 100, 1000, and 10,000 are 24%, 15%, and 11% respectively, compared to scenarios where node failures are not considered. • The ratio of network capacity to delay is O(1), which is also order-optimal in the presence of node failures. This reveals that enhancing network capacity comes at the cost of increased delay and this relationship is independent of the node failure probability and spatial dimension. In other words, it is not possible to simultaneously achieve high network capacity and low delay in multihop wireless ad hoc networks. For scenarios with lower delay, using one hop or fewer for data transmission may be a preferable strategy. Conversely, for scenarios with high traffic load, the multi-hop transmission is the optimal strategy. n log n
Notations: f (n) = O(g(n)) if there exist c > 0 and n0 > 0 such that f (n) < cg(n) for n > n0 . f (n) = Ω(g(n)) if g(n) = O(f (n)). f (n) = Θ(g(n)) if f (n) = O(g(n)) and g(n) = O(f (n)). ρ(x, y) is the Euclidean distance between positions x and y. Card(A) denotes the cardinality of the set A.
II. S YSTEM MODEL AND DEFINITIONS We consider a wireless ad hoc network consisting of n nodes. All the nodes are uniformly and independently distributed in unit square A = [0, 1]2 . The coordinate of node i is denoted as xi , where i ∈ I = {1, 2, 3, · · ·, n}. All nodes use the same transmission power P , i.e., they have the same transmission radius, which is a function of the number of nodes. Each node is equipped with either an omnidirectional or a directional antenna based on scheduling constraints and practical requirements. All transmissions use the full bandwidth W . N (n) = n2 unicast data streams are generated by using a random, uniformly matching method. Each node serves as either a source or a destination for one data stream and also relays data packets from other data streams. Time is slotted for packetized transmission. In most mobility scenarios, moreover, nodes move much more slowly than the time it takes to transmit a data packet. Therefore, it is reasonable to model mobile networks as static when analyzing capacity. A. Network topology Due to the factors including physical disruptions and both external and internal interference, etc., the state of the nodes becomes highly unreliable, which results in intermittent connectivity in the network topology. To describe the random failure behavior of nodes, we define the node failure probability, denoted as q. Let χ denote the set of non-faulty nodes and χc denote the set of faulty nodes. Card(χ) + Card(χc ) = n, where Card(χ) = (1 − q)n. The non-faulty nodes can form a random geometric graph G(n, rq (n)), where rq (n) is the critical transmission radius, which is the minimum transmission radius that ensures G(n, rq (n)) is connected with probability 1. In G(n, rq (n)), the rule for establishing a link between two nodes is given by 1, ρ(xi , xj ) ≤ rq (n), (1) w(xi , xj ) = 0. otherwise. where ρ(x, y) is the Euclidean distance between point x and point y. When wireless channel conditions are taken into account, a link between node xi and node xj is established with a certain probability. This implies that nodes separated by a distance greater than rq (n) may also form a link. Such minor random fluctuations do not fundamentally affect the scaling behavior of the network capacity (see Appendix A). G(n, rq (n)) is connected if and only if there exists a path between any pair of nodes. In other words, the random geometric graph contains no isolated nodes with probability 1 as n → +∞. The definition of the connectivity of network topology is given from [17] as follows. Definition 1. The random geometric graph G(n, rq (n)) formed by all non-faulty nodes is connected, if a) For any xi , xj ∈ χ, i ̸= j, there exists at least one data path between the two nodes; b) For any xt ∈ χc , N + (xt ) ∩ χ ̸= ∅, where N + (xt ) = {xi | ρ(xi , xt ) ≤ rq (n), xi ∈ χ} is the set of neighbor nodes of the faulty node xt .
3
(a) Omnidirectional
(b) Directional
Fig. 2. Geometric conditions of single-hop successful transmission
Fig. 1. The connectivity of communication topologies varies with the transmission radius under different the node failure probabilities—q = .9, .5, .3 (n = 1000, each sampling point is simulated 10,000 times)
After the deployment of a wireless ad hoc network, node failures occur randomly and instantaneously. Therefore, to ensure network connectivity, condition b) in Definition 1 requires that each failed node be located within the transmission range of at least one non-faulty node. In addition, condition b) effectively ensures that a failed node once recovered to a nonfaulty state can rejoin the network structure formed by the non failed nodes with probability one. We conducted simulations on the connectivity of network structure for different node failure probabilities as the node transmission radius varies, as shown in Fig. 1. The network topology is connected with probability 1 when the transmission radius is greater than the critical transmission radius. Otherwise, the network topology is not connected with probability one. B. Geometric conditions for successful transmission Using the protocol model, we model the single-hop successful transmission conditions for nodes operating with different antenna types [18], [19]. Let H = {(i, R(i)) | i ∈ J} denote the set of transmitter-receiver pairs in the same time slot, where J is the set of indices of active nodes and R(i) is the receiving node corresponding to node i. The size of the set H is determined by the spatial distribution of nodes and the traffic pattern. Definition 2. A data packet is successfully transmitted in one hop if either of the following conditions is satisfied. C1: Omnidirectional antenna. Node xi successfully transmits a data packet to node xR(i) if ρ(xi , xR(i) ) < rq (n) and the distance between transmitting nodes xk and xRi satisfies ρ(xk , xR(i) ) ≥ (1 + △)ρ(xi , xR(i) ),
(2)
where k ∈ J − {i} 1 and △ is the in-network interference parameter. C2: Directional antenna. Under the constraint of a minimum beamwidth θ, node xi successfully transmits a data 1 J − {x} is defined as the set of all y such that y is an element of J and y is not an element of {x}, i.e., J − {x} = { y | y ∈ J and y ∈ / {x} }.
packet to node xR(i) if ρ(xi , xR(i) ) ≤ rq (n) and node xR(i) is either outside the beam of simultaneously transmitting nodes xk or equation (2) holds. To illustrate the protocol model, the geometric interpretations of C1 and C2 are given in Fig. 2. Combining Definition 2 and the triangle inequality, we know that, for multiple transmitter-receiver pairs to simultaneously succeed in transmitting data packets, the disks centered at the receiver node ′ xR(i) with radii ∆2 ρ(xi , xR(i) ) should not overlap (see Fig. 3). This geometric condition holds for both omnidirectional and directional antennas [19]. For the unified analysis, we use the in-network interference parameter ∆′ , which is given by
′
∆ =
∆,
omnidirectional, (3)
min ∆, sin θ2 , directional.
According to (3), the impact of different antenna types on the in-network interference parameter is a constant and is independent of the number of nodes. Therefore, we do not distinguish the antenna types in analyses. In general, the signal-to-interference-plus-noise ratio (SINR) is also used to determine whether a communication link is successfully established between two nodes. This is called the physical model. Specifically, node R(i) can successfully receive a data packet from node i within time slot t if the following condition is satisfied: Pi ℓ(xi , xR(i) ) P ≥β N + k∈H Pk ℓ(xk , xR(i) )
(4)
k̸=i
where N denotes the additive noise power level and β is the SINR threshold required for successful decoding, which depends on the transmitter hardware and the signal strength −α level rather than being a constant value. ℓ(x, y) = (ρ(x, y)) is the path loss function, where ρ(x, y) ≥ ρ0 > 0, and α (> 2) is the path loss exponent. In comparison with Definition 2, the key parameters in the physical model defined by (4) are the demodulation threshold β and the path loss exponent α, whereas those in the protocol model is the in-network interference parameter ∆′ . These key parameters essentially measure the impact of in-network
4
Fig. 4. The division mode of unit squares
Fig. 3. Many nodes successfully transmit data packets simultaneously (ri ≤ rq (n), i = 1, · · ·, 7)
interference caused by simultaneous transmissions on links. These two models are equivalent, as shown in Remark 1. Remark 1. According to Theorem 4.1 in [18], if ∆′ > α−1 α−2 ∆(β) := 48β 2α−2 , then any set of simultaneous transmitter-receiver pairs H allowed under the protocol model can also be supported under the physical model with SINR threshold β, given a suitable power assignment {Pi , 1 ≤ i ≤ n}. This means that the capacity obtained using the protocol model is robust to both in-network interference and path loss. As the path loss exponent increases, the value of ∆(β) decreases, and the area consumed by successful link establishment becomes smaller.
edge between the corresponding vertices. The failure probability for non-empty small squares is q ′ , which is determined by the number of non-faulty nodes within each small square. When q ′ is less than the critical probability qc , the connectivity of the site percolation graph increases sharply to one with probability 1 (forming a unique connected component). Conversely, the site percolation graph is disconnected with probability 1 (forming multiple connected components). In discrete percolation theory, this sharp change in connectivity is known as the phase transition and its strict definition is given as follows [21]. Definition 3. The probability that the connectivity of the site percolation graph approaches one is denoted as ψ(q ′ ). The condition is given by ( 1, q ′ ≤ qc , ′ ψ(q ) = . (5) 0, q ′ > qc .
C. Network protocols
where qc is the critical failure probability2 .
The key issues in using multi-hop transmission scheme are selecting the data paths for transporting data packets and avoiding in-network interference caused by multiple nodes transmitting in the same time slot. The former is the routing problem and the latter is the link scheduling problem. Since we aim to focus on the fundamental performance limit of wireless ad hoc networks, we outline the basic principles of multi-hop transmission scheme. The standard proof framework in [20] is employed to establish the relationship between key parameters and network capacity. 1) Mapping relationship between site percolation graph and random geometric graph: To extract the critical parameters ensuring the network topology is connected with probability 1, we tile the unit square region with small squares r (n) of side length aq (n) ≜ q√2 , as shown in Fig. 4. On one hand, this method ensures that each small square contains at least one node, which indicates that each small square has the capability to relay data packets from other nodes. On the other hand, it transforms a random geometric graph formed by nonfaulty nodes into a site percolation graph, where each vertex has at most four neighbors. Each small square can be equivalently considered as a vertex in the site percolation graph. if each of two adjacent small squares contains at least one non-faulty node, there exists an
2) Interference-free scheduling: To enhance spatial reuse and minimize in-network interference, interference-free scheduling is employed. We divide all small squares into clusters, where each cluster contains M 2 small squares, as shown in Fig. 4. Small squares within each cluster are numbered from left to right and from top to bottom. During the scheduling process, all small squares within each cluster that share the same number are activated simultaneously, and then the nonfaulty nodes within each small square transmit data packets in sequence. Interference-free scheduling ensures that multiple non-faulty nodes can transmit successfully in the same time slot, thereby increasing spatial reuse. Combining the protocol model in Definition 2, M is given by & ' rq (n) + (1 + ∆′ )rq (n) √ M ≥ 1+ rq (n)/ 2 (6) l m √ = 1 + 2(2 + ∆′ ) ≥ 3, where ⌈x⌉ denotes the smallest integer greater than x. From equation (6), it is clear that M is determined only on ∆′ . From Remark 1, the value of ∆′ is determined solely by β and α, 2 Through simulation in [21], it is found that q ≈ 0.4073. c
5
III. N ETWORK CAPACITY AND DELAY Before analyzing network capacity and delay, we first give the critical transmission radius and the number of non-faulty nodes in each small square. Lemma 1. When the node failure probability is q, the critical transmission radius that ensures the network topology remains q n+ξ connected with probability 1 is given by rq (n) = log (1−q)n , where ξ > 0. When node failureqis not considered, the critical transmission radius is r(n) = log n+ξ , where ξ ′ > 0. n ′
(a) Routing strategy
(b) Rerouting strategy
Proof. This proof is provided in [17].
Fig. 5. Multi-hop transmission strategy ′
independent of the network size. Therefore, the value of ∆ does not affect the order of network capacity and delay. 3) Multi-hop transmission strategy: A multi-hop transmission strategy is used to transport data packets between a source node and a destination node. For each source-destination pair i, the corresponding S-D line is constructed by connecting the source node Si and the destination node Ri . Subsequently, data packets generated by the source node Si are relayed through the small squares along the S-D line to the destination node Ri , as shown in Fig. 5(a). If the relaying process encounters an empty small square, a rerouting strategy is employed, as shown in Fig. 5(b). There are two cases that can lead to a small square being empty: i) it contains no nodes at all; ii) it contains nodes, but failures occur for all the nodes. Assume that the coding and queue scheduling algorithms at each hop are optimal and independent of the number of nodes. D. Definitions of Network Capacity and Delay Definition 4. Network capacity is defined as Sq (n) = Nq (n)λq (n), where Nq (n) is the number of source-destination pairs. The feasible data transmission rate λq (n) is defined as follows [3]. λq (n) ≜
min
lim inf
1≤i≤Nq (n) t→∞
B(i, t) bits/s, t
where B(i, t) is the cumulative number of bits successfully transmitted for source-destination pair i. q is the node failure probability.
Remark 2. In real communication scenarios, wireless channel conditions such as fading, shadowing, and path loss affect instantaneous link quality. However, prior studies (e.g., [22], [23]) show that wireless network connectivity is generally not sensitive to these factors. Specifically, shadowing can enhance connectivity by increasing the likelihood of long-range links, whereas fading and path loss can slightly degrade it. These variations do not impact the scaling behavior of the critical transmission radius, as established in Lemma 1. Consequently, the capacity scaling laws derived in the subsequent analysis remain robust to the random fluctuations of wireless channel. Some simulation results on the impact of channel randomness on network structural connectivity are provided in Appendix A. According to Definition 3, if the failure probability of a nonempty small square is below the critical failure probability, the site percolation graph is connected with probability 1. Otherwise, it is disconnected with probability 1. Whether a non-empty small square fails is determined by the number of non-faulty nodes it contains and the node failure probability. In Proposition 1, we provide the number of non-faulty nodes in each small square. r (n)
Proposition 1. For aq (n) ≥ q√2 , the number of non-faulty nodes in each small square is Θ(log(n)). Proof. The detailed proof can be found in Appendix B. Combining Proposition 1 and the conditions in Definition 3, the condition for ensuring the site percolation graph is connected with probability 1 is 1
Definition 5. Delay is defined as Nq (n) X h i i 1 Dq (n) = E D (n) , Nq (n) i=1 h i i where E D (n) , the average delay for transmitting data packets for source-destination pair i, is defined as follows [15]. k h i i X 1 Di (n) , E D (n) ≜ E lim sup k→∞ k j=1 j
where Dji (n) is the total time required for the the j-th data packet of source-destination pair i to travel from the source node to the destination node. q is the node failure probability.
1
q ′ = q c1 log n < qc ⇒ q < qcc1 log n ≈ 0.4073 c1 log n ,
(7)
where c1 > 0. According to (7), when the number of nodes is fixed, the node failure probability should be less than a certain critical value to ensure the site percolation graph is connected with probability 1. This indicates that increasing the number of nodes can enhance the resilience of the network topology. In the subsequent analysis, assume that condition (7) and Proposition 1 both hold, meaning the site percolation graph is connected with probability 1. A. Network capacity In this section, we will present the network capacity of wireless ad hoc networks with node failures.
6
Theorem 1. The network capacity of wireless ad hoc networks is s ! n(1 − q) Sq (n) = Θ bits/s, log n where q is theq node failure probability. As p → 0, this result n reduces to Θ bits/s. log n Proof. We are going to provide the proofs for the upper and lower bounds of network capacity, respectively. ➀ Lower bound. The lower bound on network capacity ensures there exist interference-free scheduling and routing strategies enabling the network to achieve at least the given capacity. According to Section II-C, specifically, interference-free scheduling ensures that each small square within a cluster can only be activated once within M 2 time slots. This means that fewer small squares are activated in the same time slot when M is larger, resulting in less interference. The degradation in network ca W . During pacity due to interference-free scheduling is Θ M 2 the multi-hop routing process, nodes within each small square not only transmit and receive data packets corresponding to their own source nodes but also relay data packets from other source-destination pairs. Therefore, the total number of data packets forwarded is proportional to the total number of S-D lines crossing the small square. This essentially limits the lower bound of the achievable network capacity, i.e., there exists a feasible multi-hop strategy that can achieve the corresponding lower bound of the network capacity. Firstly, we provide the number of S-D lines served by each small square. Let Hi be the total number of hops required from the source to the destination for pair i, i = 1, · · ·, Nq (n). Since nodes are uniformly distributed, we have E[Li ] E[Hi ] = Θ , (8) aq (n) where E[Li ] be the distance between the source node and destination node of pair i. Let Yij be the indicator variable for whether the S-D line of source-destination pair i passes through small square j. Yij = 1 indicates that the S-D line of source-destination pair i passes through small square j and Yij = 0 indicates that the S-D line of source-destination pair i does not passes through small square j. Separately summing Yij and Hi over the indices i and j, we have Nq (n) m q (n) X X j NX Yi = Hi , (9) i=1 j=1
i=1
. where Nq (n) = n(1−q) 2 Taking the expectation of both sides of (9), we obtain h i h i mNq (n)E Yij = Nq (n)E [Hi ] ⇐⇒ mE Yij = E [Hi ] . (10) Combining (8) and (10), we have Pr{Yij = 1} = Θ(rq (n)).
(11)
According to (11), the number of S-D lines passing through the small square j is Nq (n)
X
j
Y =
Yij .
(12)
i=1
From (12), the expectation of Y j is given by p E[Y j ] = Θ (Nq (n)rq (n)) = Θ n(1 − q) log n .
(13)
By applying Chebyshev’s inequality, we get Pr{Y j > (1 + σ)E[Y j ]} ≤ e−
E[Y j ]σ 2 4
.
(14)
Substituting (13) into (14), we have 1 Pr{Y j > (1 + σ)E[Y j ]} ≤ 2 , n q log n where σ = 2 2E[Y j] . 1 Since lim n2 = 0, we get
(15)
n→+∞
(1 − q)n log n , j = 1, · · · , m. (16) Pm Using the inequality Pr{∪m i=1 Ai } ≤ i=1 Pr{Ai }, the probability that any small square serves more than (1 + σ)E[Y j ] S-D lines converges to 0, i.e., the number of S-D p (1 − q)n log n . lines served by each small square is O Using (16), the feasible data transmission rate is given by Y j ≤ (1 + σ)E[Y j ] = O
p
λq (n) ≥ p
c (1 − q)n log n
,
(17)
W where c = Θ M 2 . According to Definition 4 and Nq (n) = n(1−q) , the lower 2 bound of network capacity is s ! n(1 − q) . (18) Sq (n) = Ω log n ➁ Upper bound The upper bound on network capacity asserts that no interference-free scheduling and routing scheme can achieve a capacity beyond this bound. According to the protocol model in Section II-B, the area consumed for a single-hop successful 2 π (∆′ rq (n)) transmission is at least . Thus, the total number of 4 transmitter-receiver pairs that can successfully transmit in the same time slot, denoted by F u (n), is at most F u (n) =
4 π (∆′ rq (n))
2.
(19)
Let d be the average Euclidean distance between source node and destination node. Since nodes are uniformly distributed in the unit square, each data packet requires at least d−o(1) rq (n) hops to reach the destination node. Therefore, the number of bits that the network needs to successfully transmit is at least F (n) ≥ n(1 − q)λq (n)
d − o(1) . rq (n)
(20)
7
Each node successfully transmit W bits per time slot. Combining (19) and (20), we have F (n) ≤ W F u (n) ⇐⇒ λq (n) ≤
4W
n(1 − q)(d − o(1)) rq (n)
(21)
2.
π (∆′ rq (n))
(a) n = 100
(b) n = 1000
(c) n1 vs. q
(d) ϵ(1000, q) vs. q
where λq (n) is the feasible q data transmission rate. Substituting rq (n) = we get
log n+ξ π(1−q)n
from Lemma 1 into (21),
c1 λq (n) ≤ p , (1 − q)n log n
(22)
4W where c1 = π∆′ (d−o(1)) . Combining Definition 4, the upper bound of network capacity is s ! n(1 − q) Sq (n) = O . (23) log n
From the above proof, for any network scheduling strategy and network topology, (23) holds. Combining (18) and (23), the network capacity is given by s ! n(1 − q) bits/s. (24) Sq (n) = Θ log n As q → 0, Equation (24) reduces to Θ which is the classical result in [3].
q
n log n
bits/s,
We have the following important insights from Theorem 1. • The degradation of network capacity due to node √ failures is proportional to Θ 1 − q . This is because the minimum transmission radius required to maintain the connectivity of the network topology increases, thereby reducing the total number of active transmitter-receiver pairs in the same time slot and the number of hops from the source node to the destination node. • The feasible data transmission rate is p λq (n) = Θ 1/ (1 − q) log n bits/s.
When n is fixed, the feasible data transmission rate increases with the node failure probability. This is because the interference within the network decreases, thereby reducing the intensity of competition for communication resources. Moreover, λq (n) converges to zero as the number of nodes increases, indicating that the feasible data transmission rate is not scalable under node failures. • Increasing the number of redundancy nodes to improve network capacity is not feasible. Let n1 redundancy nodes be deployed in the network and are responsible only for relaying data packets from other nodes. Assume all redundancy nodes do not fail, i.e., they are available with probability 1 for constructing the
Fig. 6. The number of redundancy nodes varies with the node failure probability.
network topology. From Theorem 1, the network capacity after adding redundancy nodes is s ! n(1 − q) + n1 bits/s. (25) Sq (n + n1 ) = Θ log(n + n1 ) The feasible data transmission rate after adding redun q dancy nodes is Θ bits/s. A very large number of redundancy nodes is required to increase the network capacity to ω + 1 times its original value. We provide an numerical example as shown in Fig. 6. For example, when q = 0.2, it requires 6657 redundancy nodes to achieve three times the network capacity of a wireless ad hoc network with 1000 nodes. This number is much greater than the initial node scale. In other words, it can be seen that adding redundancy nodes enhances the connectivity of the network topology rather than improving the network capacity. 1 n(1−q)
np+n1 log (n+n1 )
B. Some corollaries Based on the previous analysis, some important corollaries are given as follows. q
Corollary 1. To maintain the network capacity at Θ logn n bits/s in wireless ad hoc networks with node failure probability, at least n1 = ϵ(n, q)nq redundant nodes should be deployed, where ϵ(n, q) > 1 is the ratio of the number of redundant nodes to nq. Proof. Combining with (25), we have S(n) = Sq (n + n1 ) =⇒
n n(1 − q) + n1 = bits/s, log n log(n + n1 )
where n1 = ϵ(n, q)nq. ϵ(n, q) > 1 can be verified by a simple numerical computation.
8
expected number of non-faulty nodes is n(1 − q). Based on the above results, Corollary 2 is given.
(a) ϵ(n, 0.2) vs. n
η ≤ 1 holdsqbecause the critical transmission radius is given n(1−q) by r(n(1 − q)) = logn(1−q) when node failures are not considered (see Lemma 1). When node failures areqconsidered, however, log n . By combining the critical transmission radius is rq (n) = n(1−q) the protocol model from Section II-B, the number of simultaneous transmit-receive node pairs supported by the network in our work is less than that reported in [3]. This means that the loss of network capacity is the cost incurred to overcome the randomness of node failures. Under the same node failure probability, a greater number of nodes results in reduced the loss of network capacity, as shown in Fig. 7b. When q = 0.85, for example, the network capacity loss rates corresponding to node scales of 100, 1000, and 10,000 are 24%, 15%, and 11% respectively, compared to scenarios where node failures are not considered. Using the same proof technique as Theorem 1, we can derive the network capacity of wireless ad hoc networks in the three-dimensional space. Corollary 3. The network capacity of wireless ad hoc networks deployed in three-dimensional space is s ! 3 n(1 − q) bits/s, Sq (n) = Θ 2 log n
(b) Fig. 7. Network capacity loss vs. node failure probability.
For n = 1000, the number of redundant nodes under varying node failure probabilities is greater than 1000q, as demonstrated in Fig. 6(c). ϵ(n, q) is a monotonically decreasing function of the node failure probability—see Fig. 6(d). Given the node failure probability q > 0, the number of redundant nodes decreases non-linearly as the number of nodes (n). The relationship between ϵ(n, 0.2) and n under q = 0.2 is shown in Fig. 7a. When n is sufficiently large or q is sufficiently small, deploying approximately nq redundant nodes is sufficient to q maintain the network capacity at Θ logn n bits/s. Corollary 2. The wireless ad hoc networks with n nodes and node failure probability q have lower network capacity than one with n(1 − q) nodes without considering node failures, i.e., s log n(1 − q) η≜ ≤ 1. log n
where q is the node failure probability. When q = 0, our result degenerates to the classical result established in [19]. With the same node failure probability, from Corollary 3 and Theorem 1, wireless ad hoc networks in three-dimensional space achieve higher network capacity than those in twodimensional planes. C. Delay Theorem 2. The delay of wireless ad hoc networks is given by s ! n(1 − q) Dq (n) = Θ , log n where q is the node failure probability. Proof. According to the law of large numbers, the average distance between source node and destination node is Pn(1−q) d(i) d = i=1 = Θ(1), n(1 − q) where di is the distance between source-destination pair i. Since each hop distance is Θ (rq (n)), the average number of hops is Θ . The delay is proportional to the average number of hops because the delay required for each hop is constant and independent of the number of nodes. Summarizing the above analysis, the delay is given by s ! n(1 − q) Dq (n) = Θ , log n 1 rq (n)
Proof. If node failures is not considered, the network capacity corresponding to deploying n(1 − q) nodes is q n(1−q) S(n(1 − q)) = Θ bits/s , which can be derived using the log n(1−q) proof method from [3]. From Theorem 1, the network capacity of wireless ad hoc networks with q node size n and the node bits/s. In this case, the failure probability q is Sq (n) = Θ n(1−q) log n
where q is the node failure probability.
9
To reduce the delay, reducing the number of hops is a feasible strategy by increasing the transmission radius. Meanwhile, the number of transmitter-receiver pairs that can successfully transmit within the same time slot can also decrease (see Fig. 3). This can degrade the network capacity. Thus, there exists an inherent trade-off between delay and network capacity. IV. O PTIMAL TRADE - OFF BETWEEN NETWORK CAPACITY AND DELAY
Combining Theorems 1 and 2 in Section III, the ratio of network capacity to delay is given by Sq (n) = O (1) . Dq (n)
(26)
In terms of order, is the trade-off relationship given by Eq. (26) optimal? To answer this fundamental question, the definition of the optimal trade-off between network capacity and delay is given as follows [15]. Definition 6. Let the network capacity and delay of wireless networks be denoted by Sq (n) and Dq (n), respectively. The S (n) ratio Dqq (n) is optimal if the following conditions are satisfied. a) There exists a multi-hop transmission strategy M such that the network capacity and delay satisfy SqM (n) = Θ (Sq (n)) and DqM (n) = Θ (Dq (n)). ′ b) For any multi-hop transmission strategy M′ , SqM (n) = ′ Ω (Sq (n)) and DqM (n) = Ω (Dq (n)), where q is the node failure probability. In Definition 6, condition (a) ensures that there exists some strategy capable of achieving the corresponding network capacity and delay, while condition (b) indicates that for all strategies with multi-hop transmission properties, the network capacity and delay are Sq (n) and Dq (n), respectively. Theorem 3. For all multi-hop transmission strategies, the optimal trade-off between network capacity and delay is given by Sq (n) = O (1) , Dq (n) where q is the node failure probability. Proof. Let the average distance of S-D lines be d and the feasible data transmission rate be λq (n). After T time slots, the total number of bits carried by the wireless network is e = λq (n)Nq (n)T . The total number of hops required for bit b from source to destination be h(b) and the h-th hop distance Ph(b) for bit b be rb (h). Based on h=1 rb (h) ≥ d, we have e h(b) X X
rb (h) ≥ ed.
(27)
b=1 h=1
Combining the protocol model from Section II-B, the area consumed for the successful transmission of each bit b in the ′ 2 h-th hop is π(∆ r4b (h)) . The number of bits transmitted from a source node within T time slots is at most W T , where W
is the number of bits transmitted per time slot by each source node. Hence, we have e h(b) X X π(∆′ rb (h))2 b=1 h=1
4
≤ W T × 1.
(28)
Let the total number of hops P taken for the successful e transmission of all bits be H = b=1 h(b). Since f (x) = x2 , x > 0 is a convex function, we obtain 2 e h(b) e h(b) X X 1 X X 1 2 rb (h) ≤ (rb (h)) . (29) H H b=1 h=1
b=1 h=1
Combining (27)-(29), the inequality is given by λq (n)Nq (n)T d
2
≤
4W T H. π(∆′ )2
(30)
From the above proof, it can be seen that for all multihop transmission strategies, Eq. (30) holds with probability 1. Furthermore, the average number of hops taken for each bit to successfully transmit from the source node to the destination node be h = He . Substituting h into (30), we have λq (n)Nq (n) ≤
4W h. π(∆′ d)2
(31)
Taking the expectation of both sides of (31), we obtain 4W h = ch, (32) λq (n)E [Nq (n)] ≤ E π(∆′ d)2 4W where c = π(∆ , which is independent of n. ′ d)2 By the condition (a) of Definition 6, there exists a multihop transmission strategy M such that the following equation holds, i.e., Sq (n) = Θ (E[Nq (n)]λq (n)) . (33)
Using (32) and (33), we have Sq (n) = O(1). (34) h Since the delay for each hop is constant, the delay is pro portional to the average number of hops, i.e., Dq (n) = Θ h . Combining the above results, the optimal trade-off between network capacity and delay is Sq (n) ≤ ch ⇐⇒
Sq (n) = O (1) . Dq (n)
In the sense of order, Theorem 3 holds for any multihop transmission strategy. This indicates that increasing the network capacity comes at the cost of increasing the delay and is independent of the node failure probability and spatial dimension. For the scenarios with lower delay, using one-hop or fewer transmissions may be a preferable strategy. For the scenarios with high traffic load, multi-hop transmission represents the optimal strategy. Using the multi-hop transmission strategy cannot simultaneously achieve both lower delay and higher network capacity.
10
According to Theorem 3, increasing the network capacity by adding redundancy relay nodes can also increase the delay. This further indicates that the primary role of adding redundancy relay nodes is to enhance the connectivity of the network topology. Additionally, the conclusion of Theorem 3 holds regardless of the spatial dimension. Remark 3. Compared with [8]– [10], Theorems 1, 2 and 3 respectively establish the network capacity, delay and their optimal trade-off in wireless ad hoc networks subject to random node failures after deployment. Specifically, they quantitatively characterize the impact of random node failures on both network capacity and delay. We also prove that the optimal trade-off between network capacity and delay is Θ(1), which is independent of the node failure probability.
condition (see (1)). By integrating key parameters of the wireless channel, we perform simulations to evaluate the network connectivity under different parameter settings (see Fig. 8). Simulation results indicate that the set of links successfully established under the geometric rule is a subset of those formed under more realistic wireless channel conditions, including path loss, shadowing, and Rayleigh fading. This confirms that the analysis based on Lemma 1 is robust to the random fluctuations of wireless channel. As a result, the corresponding capacity results remain valid under practical wireless environments. As shown in Fig. 8 (c) and 8 (d), a higher path loss exponent corresponds to lower network connectivity. Moreover, the randomness of the wireless channel does not affect the asymptotic scaling of the critical transmission radius as stated in Lemma 1.
V. C ONCLUSIONS In this paper, the network capacity, delay and their optimal trade-off relationship are provided when wireless ad hoc networks encounter node failures. We find that at least ϵ(n, q)nq redundant nodes need to be added to maintain the q network capacity at Θ logn n bits/s, where ϵ(n, q) > 1. It is also shown that any strategy with multi-hop properties cannot simultaneously achieve high network capacity and low delay. These results provide a preliminary theoretical explanation of how node failures affect the fundamental performance of large-scale wireless ad hoc networks. In future work, we will design networking protocols by considering specific requirements, including network status, application scenarios and task requirements.
(a) σ = 5 dBm
(b)
(c)
(d)
A PPENDIX A. Network connectivity under realistic wireless channel conditions In the sensitivity analysis of network connectivity, the key wireless channel parameters considered are as follows: • Path loss: Large-scale attenuation of signal power as the distance between transmitter and receiver increases. The path loss function is typically modeled as ℓ(x) = x−α , where α is the path loss exponent. • Log-Normal shadowing: Slow variations in signal strength caused by obstacles, resulting in fluctuations around the average path loss. The lognormal spread σ follows a log-normal distribution N (0, σ 2 ). • Rayleigh fading: Rapid small-scale fluctuations in signal amplitude due to multipath scattering in non-line-of-sight environments. The power gain G follows an exponential distribution, G ∼ Exponential(1), Based on the above parameters, the received power at a distance d from a transmitting node is given by Pr (d) = Pt − 10α log10 (d) + σ + G,
(35)
where Pt is the transmission power and Pmin is the minimum required received power for successful communication. A communication link can be successfully established if Pr (d) > Pmin ; otherwise, it cannot. When σ = 0, G = 0 and α = 2, the connection rule reduces to a geometric
Fig. 8. Network connectivity under different combinations of path loss exponent (α) and lognormal spread (σ). Pmin = −80 dBm, n = 1000, α = 2.5
B. Proof of proposition 1 Let the number of non-faulty nodes in the small square i be Zn0 . Since each node independently participates in the construction of the network topology with probability p = 1 − q, the number of non-faulty nodes is n0 = n(1 − q). Let Ij be the indicator for whether node j falls within the small square i, which is defined by 0, node j falls within small square i, Ij = , (36) 1, otherwise. where j = 1, . . . , n0 . According to the geometric probability model, Pr{Ij = 1} = a2q (n) and Pr{Ij = 0} = 1 − a2q (n). Using (36), Zn0 is given by n0 X Z n0 = Ij . (37) j=1
11
From the above analysis, Zn0 follows a binomial distribution with parameters (pn , n0 ), where pn = Pr{Ij = 1}. Using Chebyshev’s inequality, we obtain c0 σ 2
c0 σ 2
Pr{Zn0 ≥ (1 + σ)c0 log n} ≤ e− 1+σ log n = n− 1+σ , (38) 1 where c0 = π(1−q) and 0 < σ < 1. Let Q denote as the event that at least one small square contains more than Pm (1 + σ)c0 log n non-faulty nodes. Using Pr{∪m A } ≤ i=1 i i=1 Pr{Ai } and (38), we have
Pr{Q} ≤
m X
Pr{Zn1 ≥ (1 + σ)c0 log n} (39)
i=1
= mn
c0 σ 2 − 1+σ
(a)
c0 σ 2 1− 1+σ
≤ cn
,
where m = a21(n) and c = πp. (a) holds using the inequality p
πn(1−q) < πn(1 − q). For any sufficiently small σ > 0, c0 > log n 1+σ holds. Hence, lim Pr{Q} = 0. Similarly to (39), F 2 σ n→∞
represents the event that at least one small square contains fewer than c0 (1 + σ) log n non-faulty nodes. We have Pr{F } ≤
m X
Pr{Zn1 ≤ (1 − σ)c0 log n} (40)
i=1
= mn
c σ2
− 02
c σ2
1− 02
≤ cn
.
Let c0 > σ22 > 1, lim Pr{F } = 0. Using (39) and (40), n→∞ we obtain Zn1 = Θ (log n). R EFERENCES [1] B. Y. Zheng, C. Song, and L. Liu, “Cyclic-pursuit-based circular formation control of mobile agents with limited communication ranges and communication delays,” IEEE-CAA J. Autom. Sin., vol. 10, pp. 1860–1870, 2023. [2] H. Yin, J. B. Wei, H. T. Zhao, J. Zhang et al., “Intelligent communication and networking key technologies for manned/unmanned cooperation: State-of-the-art and trends,” J. Commun., vol. 45, no. 1, pp. 1–17, 2024, in Chinese. [3] P. Gupta and P. R. Kumar, “The capacity of wireless networks,” IEEE Trans. Inf. Theory, vol. 46, pp. 388–404, 2000. [4] H. Yin, J. B. Wei, H. T. Zhao et al., “An intelligent adaptive architecture for wireless communication in complex scenarios,” Sci. China Inf. Sci., vol. 51, pp. 294–304, 2021, in Chinese. [5] H. J. Wang, H. T. Zhao, B. Q. Ren et al., “Cyber-physical framework for uav intelligent communications,” Sci. China Inf. Sci., vol. 52, pp. 2141–2154, 2022, in Chinese. [6] T. Abdelzaher, N. Ayanian, T. Basar et al., “Toward an internet of battlefield things: A resilience perspective,” Computer, vol. 51, pp. 24– 36, 2018. [7] M. Grossglauser and D. N. C. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Trans. Netw., vol. 10, pp. 477–486, 2002. [8] W. Li, J. Y. Liu, M. Sheng et al., “Robust capacity of wireless networks under cascading failures,” in Proc. IEEE GLOBECOM, Rio de Janeiro, Brazil, 2022, pp. 6013–6018. [9] ——, “The capacity of k-connectivity d-dimensional wireless networks with node failure,” Sci. China Inf. Sci., vol. 66, p. 209302, 2023. [10] M. Sheng, W. Li, J. Liu, and J. Li, “Robust throughput capacity of multi-connectivity wireless networks,” IEEE Trans. Commun., vol. 73, pp. 4228–4240, 2025. [11] N. Bansal and Z. Liu, “Capacity, delay and mobility in wireless ad-hoc networks,” in Proc. IEEE INFOCOM, San Francisco, CA, USA, 2003, pp. 1553–1563. [12] M. J. Neely and E. Modiano, “Capacity and delay tradeoffs for ad hoc mobile networks,” IEEE Trans. Inf. Theory, vol. 51, pp. 1917–1937, 2005.
[13] G. Sharma, R. Mazumdar, and N. Shroff, “Delay and capacity trade-offs in mobile ad hoc networks: A global perspective,” IEEE/ACM Trans. Netw., vol. 15, pp. 981–992, 2007. [14] L. Ying, S. Yang, and R. Srikant, “Optimal delay-throughput tradeoffs in mobile ad hoc networks,” IEEE Trans. Inf. Theory, vol. 54, pp. 4119– 4143, 2008. [15] A. El Gamal, J. Mammen, B. Prabhakar et al., “Optimal throughputdelay scaling in wireless networks part i: The fluid model,” IEEE Trans. Inf. Theory, vol. 52, pp. 2568–2592, 2006. [16] P. Jacquet, S. Malik, B. Mans, and A. Silva, “On the throughput-delay tradeoff in georouting networks,” IEEE Trans. Inf. Theory, vol. 62, pp. 3230–3242, 2016. [17] C. W. Yi, P. J. Wan, X. Y. Li et al., “Asymptotic distribution of the number of isolated nodes in wireless ad hoc networks with bernoulli nodes,” IEEE Trans. Commun., vol. 54, pp. 510–517, 2006. [18] F. Xue and P. R. Kumar, “Scaling laws for ad-hoc wireless networks: An information theoretic approach,” Found. Trends Netw., pp. 1–125, 2006. [19] P. Gupta and P. R. Kumar, “Internets in the sky: The capacity of three dimensional wireless networks,” Commun. Inf. Syst., vol. 1, pp. 33–50, 2001. [20] S. R. Kulkarni and P. Viswanath, “A deterministic approach to throughput scaling in wireless networks,” IEEE Trans. Inf. Theory, vol. 50, pp. 1041–1049, 2004. [21] M. Franceschetti and R. Meester, Random Networks for Communication: From Statistical Physics to Information Systems. Cambridge Univ. Press, 2008. [22] D. Miorandi, E. Altman, and G. Alfano, “The impact of channel randomness on coverage and connectivity of ad hoc and sensor networks,” IEEE Trans. Wireless Commun., vol. 7, pp. 1062–1072, 2008. [23] L. Booth, J. Bruck, M. Cook et al., “Ad hoc wireless networks with noisy links,” in Proc. IEEE ISIT, 2003, p. 386.