1
Throughput Characterization of Wireless CSMA Networks With Arbitrary Sensing and Interference Topologies
arXiv:2604.12400v1 [cs.NI] 14 Apr 2026
Xinghua Sun, Member, IEEE, Wenhai Lin, Graduate Student Member, IEEE, Ruike Zhou
Abstract—The performance analysis of wireless CSMA networks is notoriously difficult due to the intricate sensing and interference relationships among links. Even the fundamental problem of throughput characterization remains open when sensing and interference topologies are both arbitrary. In this paper, we develop a new analytical framework for throughput characterization in wireless CSMA networks with arbitrary sensing and interference topologies. The proposed framework yields explicit throughput expressions without relying on the commonly adopted zero-propagation-delay assumption. The key idea is to exploit the clique structure of the sensing graph to transform the original CSMA network into an equivalent multichannel network, and then model its dynamics through a discretetime Markov renewal process. In this way, the framework explicitly captures global coupling among links and enables analytical evaluation of how access parameters affect network performance. The proposed analysis is applied to several representative CSMA scenarios, including networks with multi-BSS IEEE 802.11 networks with universal frequency reuse, and adhoc topologies exhibiting hidden-terminal, exposed-terminal, and flow-in-the-middle effects. Simulation results show that, in dense deployments and in scenarios with strong coupling among link behaviors, the proposed model significantly outperforms existing analytical approaches in throughput estimation and enables more accurate determination of access parameters. Index Terms—Carrier Sense Multiple Access (CSMA), wireless networks, throughput analysis, hidden terminals, multi-BSS IEEE 802.11 networks, Markov renewal process.
I. I NTRODUCTION ARRIER Sense Multiple Access (CSMA) is a fundamental random-access mechanism that has been widely adopted in modern wireless networks. Under CSMA, a transmitter senses the channel before initiating transmission and defers its access if an ongoing transmission is detected [1]. A wireless CSMA network typically consists of multiple transmitter–receiver pairs, each forming a communication link. Such networks arise in a wide range of practical settings. For example, in Wi-Fi networks, multiple stations contend for access to a common access point, whereas in ad-hoc networks, each station may communicate with a different receiver. Despite its practical success, the performance analysis of wireless CSMA networks remains notoriously difficult. The
C
Xinghua Sun, Wenhai Lin and Ruike Zhou are with the School of Electronics and Communication Engineering, Sun Yat-sen University, Shenzhen 518107, China (e-mail: [email protected]; [email protected]; [email protected]). This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible.
T
Carrier sensing
Transmitter
Interfere R
Receiver
Link 1 Link 2 Link 3
Link Link 1
Link 2
Link 1
Link 2
R
R
R
R
R
R
R
T
T
T
T
T
T
T
(a)
(b)
(c)
Fig. 1: Representative topological scenarios in wireless CSMA networks: (a) flow-in-the-middle, (b) hidden-terminal, and (c) exposedterminal.
main challenge lies in the intricate sensing and interference relationships among links. In particular, due to the limited carrier-sensing range, not all transmitters can detect one another. As a result, each transmitter observes only a local subset of network activity, and the medium-access behavior of different links becomes strongly coupled. A representative example is the flow-in-the-middle problem shown in Fig. 1a. In this topology, link 2 is the flow-inthe-middle link: its transmitter is within the carrier-sensing range of the transmitters of both links 1 and 3, whereas links 1 and 3 cannot sense each other directly. Consequently, link 2 must defer whenever either of the other two links transmits, while links 1 and 3 may still access the channel independently. This asymmetric contention relationship puts link 2 at a disadvantage and may lead to severe throughput starvation. The example also shows that even links without direct sensing relationships may still be statistically coupled through the network topology. The analysis becomes even more involved because sensing relationships generally do not coincide with interference relationships. Since the transmitter and receiver of a link are geographically separated, whether two links can sense each other does not necessarily determine whether they interfere with each other. This mismatch gives rise to the well-known hidden-terminal and exposed-terminal problems. As shown in Fig. 1b, the transmitters of links 1 and 2 cannot sense each other, yet their simultaneous transmissions collide at the receivers, resulting in a hidden-terminal problem. In contrast, Fig. 1c illustrates an exposed-terminal scenario, in which the transmitters of links 1 and 2 can sense each other, although the transmission of link 2 does not interfere with the receiver
2
of link 1. Under such topologies, even when the classical collision model is adopted, i.e., a transmission succeeds if and only if no interfering link transmits concurrently, throughput characterization remains highly nontrivial. The success probability of a link depends on the joint activity of multiple other links. Because these links may be indirectly coupled through carrier sensing, the probability of simultaneous transmissions cannot, in general, be factorized into independent marginal probabilities. Therefore, accurate throughput analysis requires a model capable of capturing such global coupling across the network. These challenges are common in CSMA-based ad-hoc networks, where nodes are geographically distributed and only partially aware of ongoing transmissions. Similar complexity also arises in infrastructure networks. In dense multi-BSS WLANs, for example, different stations may observe different subsets of ongoing transmissions, and their access behavior may be strongly correlated through overlapping sensing domains. In such scenarios, the mismatch between carrier sensing and actual interference becomes increasingly pronounced, rendering the analytical characterization of practical mediumaccess behavior much more challenging. A fundamental and still open problem is therefore how to characterize the throughput of CSMA networks under arbitrary sensing and interference relationships. In this paper, we develop a new analytical model for wireless CSMA networks to address this problem. The key idea of the proposed analysis is to represent the network topology using a sensing graph and an interference graph, and then transform the original singlechannel CSMA network into an equivalent multi-channel network by exploiting the clique structure of the sensing graph1 . Based on this transformation, we establish a discrete-time Markov renewal process to model the activity of the equivalent multi-channel network. Since the model directly tracks network-wide state evolution, it can explicitly capture global coupling among links. From the steady-state probabilities of network states, we further derive explicit expressions for link throughput and use them to analyze the impact of access parameters on network performance. Building upon the proposed framework, we examine several representative CSMA scenarios, including multi-BSS IEEE 802.11 networks and ad-hoc topologies exhibiting hiddenterminal, exposed-terminal, and flow-in-the-middle effects. These case studies demonstrate how the proposed framework can be applied to practical wireless networks with strong spatial coupling and sensing–interference mismatch. We also analyze the computational complexity of the proposed framework and discuss techniques to enhance tractability. The remainder of this paper is organized as follows. Section II reviews related work on the modeling of wireless CSMA networks. Section III introduces the system model. Section IV presents the proposed analytical framework. Section V derives the link-throughput expressions. Section VI pro1 The terms single-channel and multi-channel refer to whether the network has one or multiple available channels for nodes to access. In this paper, all nodes operate on the same frequency band; hence, the original CSMA network is single-channel.
vides case studies and simulation results. Section VII discusses the computational complexity of the proposed model. Finally, Section VIII concludes the paper. II. R ELATED W ORK Early studies on wireless CSMA networks mainly focused on multi-access scenarios [1]–[6], in which all nodes communicate with a common receiver and lie within each other’s carrier-sensing range. Under this fully connected topology, all nodes observe essentially the same channel state, which greatly simplifies the analysis. As a result, the behavior of singleAP IEEE 802.11 networks is relatively well understood. In particular, Bianchi’s seminal Markov-chain model established the canonical saturation-throughput analysis of IEEE 802.11 DCF under ideal channel conditions [2], and subsequent studies extended this framework to non-saturated operation [3], non-ideal channels with capture effects [4], and performance analysis and optimization in buffered WLANs [5], [6]. While these studies substantially improved the understanding of CSMA/CA in homogeneous single-cell WLANs, they mainly assess performance under given access parameters. To further reveal performance limits and optimal parameter settings, analytical models based on the access behavior of head-ofline (HOL) packets were developed [5], [6]. When the network topology becomes more general, however, different links may observe different subsets of ongoing transmissions, and the access behavior of links becomes strongly coupled. This additional spatial heterogeneity makes throughput analysis substantially more difficult than in the single-AP case and has motivated extensive research on analytical modeling for wireless CSMA networks with general topologies. Existing approaches can be broadly classified into two categories: set-centric and node-centric. In set-centric approaches, the global network behavior is characterized by sets of simultaneously active links. A seminal contribution in this direction is due to Boorstyn et al. [7], who modeled a CSMA wireless network as a continuous-time Markov chain (CTMC) whose states correspond to independent sets of concurrently active links. Under saturated traffic and exponentially distributed backoff timers, they showed that the steady-state distribution admits a product-form solution. Building on this framework, Wang and Kar [8] and Durvy et al. [9] studied fairness issues in saturated CSMA networks, while Bellalta et al. [10] and Faridi et al. [11] analyzed overlapping WLANs under static and dynamic channel bonding, respectively. More recently, Tarzjani and Krishnamachari [12] developed a Markov-chain-based computational approach for exact saturation-throughput characterization in heterogeneous p-CSMA networks over arbitrary conflict graphs. The backof-the-envelope (BoE) method in [13], derived from the ideal CSMA network model, further provides a simple throughput estimation rule. Because set-centric approaches model the network at a global level, they can capture coupling across the topology. However, they typically rely on idealized assumptions, most notably the zero-propagation-delay assumption, under which simultaneous transmission attempts do not lead to collisions.
3
Sensing Graph
Network topology : T
Transmitter
R
Receiver Link 1
Carrier Sensing Interfere Link
:
Interference Graph
:
The -th link
R
Link 3
T
T
T
R
R
maximal clique
Link 2
Link 2 transmits on
maximal clique
channel channel
Link 1 transmits on
and
channel
time channel time
Link 3 transmits on
channel
Fig. 2: Illustration of the sensing graph GS , the interference graph GI , and the equivalent multi-channel network.
This limitation becomes increasingly pronounced in dense networks, where non-negligible propagation delay and synchronous access attempts can substantially affect throughput. Moreover, many set-centric formulations are built on conflictgraph abstractions or aligned sensing/interference assumptions, and therefore do not directly capture the mismatch between carrier sensing and actual interference. Finally, these methods often suffer from high computational complexity because they require explicit enumeration or manipulation of large sets of feasible concurrent transmissions. In node-centric approaches, each node or link is taken as the basic modeling unit, and its throughput is expressed as a function of the activities or throughputs of neighboring links. Ng and Liew [14] analyzed a single multihop flow over a linear chain, but their framework ignores collisions caused by simultaneous access attempts within the carrier-sensing range and is not readily extendable to arbitrary nonlinear topologies. Gao et al. [15] studied throughput characteristics under general network topologies, but relied on an exponential approximation for packet service time, which makes it difficult to accurately capture the non-memoryless service process induced by realistic backoff and collision dynamics. Jindal and Psounis [16] characterized the achievable rate region of 802.11 multihop networks through a decomposeand-combine approach, which depends on the assumption that a complex topology can be decomposed into multiple bilateral sub-topologies and may introduce significant error in dense networks. For multi-BSS IEEE 802.11 networks with universal frequency reuse, Gao et al. [17] grouped nodes according to spatial regions and established a discrete-time Markov renewal process to model HOL-packet behavior. However, their model assumes independence among channel-idle probabilities across APs and therefore neglects the coupling introduced by transmissions of nodes in overlapping regions. Garetto et al. [18] decomposed a multihop wireless network into embedded two-
flow subgraphs, but multi-flow dependencies beyond pairwise interactions were not explicitly characterized. Compared with set-centric methods, node-centric approaches avoid independent-set enumeration and therefore usually have lower complexity. However, because they do not explicitly model the network as a whole, they often rely on idealized assumptions, such as perfect carrier sensing, independence among transmitters, or simplified service processes, in order to keep the analysis tractable. These assumptions become increasingly inaccurate in dense multi-AP deployments, where local sensing differences and cross-AP coupling play a central role. As will be shown in Section VI, their accuracy degrades noticeably when link behaviors are highly correlated. Another closely related line of research concerns the mismatch between carrier sensing and actual interference. Classical studies have long recognized that hidden-terminal and exposed-terminal effects can severely degrade CSMA/CA performance [1], [19]. More recently, this issue has become increasingly important in dense WLAN deployments and spatial-reuse-oriented standards such as IEEE 802.11ax. For example, Wilhelmi et al. [20] provided a comprehensive treatment of spatial reuse in IEEE 802.11ax, and Lanante and Roy [21] analyzed OBSS PD-based spatial reuse. These studies highlight the importance of sensing–interference mismatch, but they are largely tailored to specific mechanisms or deployment structures. A general analytical framework that directly captures arbitrary sensing and interference topologies remains largely unavailable. The analytical model developed in this paper differs from the above lines of research in several key aspects. Compared with existing single-AP models [2]–[6], it is not restricted to fully connected contention scenarios with a common receiver and is applicable to wireless CSMA networks with arbitrary sensing and interference topologies. Compared with set-centric approaches [7]–[9], [22], [23], it does not rely on the zero-
4
propagation-delay assumption and therefore remains effective in dense-network regimes where simultaneous transmissions and collisions are non-negligible. Compared with node-centric approaches [14]–[17], [24], it explicitly captures global coupling among links rather than relying on local independence or decoupling assumptions. Compared with studies tailored to specific manifestations of sensing–interference mismatch, such as hidden terminals or OBSS PD-based spatial reuse [19]– [21], it provides a unified framework that directly models arbitrary sensing and interference topologies. As a result, the proposed framework offers a general analytical tool for throughput characterization and access-parameter optimization in strongly coupled wireless CSMA networks. III. S YSTEM M ODEL Consider a wireless network consisting of K links sharing the same spectrum, where each link is formed by a transmitter– receiver pair. Each transmitter employs carrier sense multiple access (CSMA) for medium access. Specifically, before transmitting a packet, transmitter i senses the channel and accesses the medium with probability qi if the channel is sensed idle; otherwise, it defers transmission. Throughout this paper, we focus on the saturated regime, in which every transmitter always has packets available for transmission. We consider a slotted CSMA network, where time is divided into equal-length slots. Each transmitter requires one slot to sense the channel and is allowed to initiate a transmission only at the beginning of a slot. In practical wireless CSMA networks, not all transmitters lie within each other’s carriersensing range. The sensing relationship among links is therefore described by an undirected graph GS (V, ES ), referred to as the sensing graph, where V is the set of links and (i, j) ∈ ES if the transmitters of links i and j can sense each other. For each link i, let Hi denote the set of links that can sense link i, i.e., Hi = {j : (i, j) ∈ ES } . (1) At the receiver side, we adopt a noise-free channel and the classical collision model. Under this model, a packet transmitted on link i is successfully received if and only if no interfering link transmits concurrently. Let Ri denote the set of links whose transmissions can interfere with link i. For example, for the topology shown in Fig. 2, we have R2 = {1, 3}. We further assume that both successful and failed packet transmissions occupy τ time slots2 . The interference relationship among links is represented by a directed graph GI (V, EI ), referred to as the interference graph, where EI ⊆ V ×V. A directed edge (i, j) ∈ EI indicates that the transmission of link i can interfere with the reception of link j. Unlike the sensing graph, the interference graph is 2 In CSMA systems, acknowledgement (ACK) frames are used to indicate whether a packet transmission succeeds. Under the basic access mechanism, a successful transmission lasts slightly longer than a failed one because of the ACK exchange and the short inter-frame space. Since the ACK duration is typically much smaller than the payload-transmission duration, this difference is often negligible. In contrast, under the request-to-send/clearto-send (RTS/CTS) mechanism, the difference between successful and failed transmission durations can be significantly larger [2]. Extending the model to unequal success and failure durations is left for future work.
generally asymmetric because interference is determined by the transmitter–receiver geometry of the links. The above model naturally captures both the hiddenterminal problem and the flow-in-the-middle problem. These two effects coexist in the topology shown in Fig. 2. In particular, link 3 is outside the carrier-sensing range of link 2, yet its transmission can still interfere with the receiver of link 2, which gives rise to a hidden-terminal effect. At the same time, link 1 can sense both links 2 and 3, whereas links 2 and 3 cannot sense each other. Consequently, links 2 and 3 may repeatedly transmit in an overlapping manner, which prevents link 1 from gaining channel access and leads to the flow-inthe-middle phenomenon. Such topologies have a pronounced impact on throughput and fairness, and they will serve as representative scenarios in the subsequent analysis. IV. M ULTI -C HANNEL M ODELING A. Equivalent Multi-Channel Network In this subsection, we establish an equivalent multi-channel representation for a single-channel CSMA network. The basic intuition is as follows. If two links can sense each other, then they contend for access in a manner analogous to sharing the same channel. Conversely, if two links cannot sense each other, they behave as if they were operating on different logical channels. This observation motivates a graph-based transformation from the original CSMA network to an equivalent multi-channel network. From the viewpoint of the sensing graph GS , each set of mutually sensing links forms a clique3 . In this paper, we use maximal cliques4 to construct logical channels. Specifically, each maximal clique in GS is mapped to one logical channel in the equivalent network. For the topology shown in Fig. 2, links 1 and 2 form one maximal clique and are therefore regarded as sharing the first logical channel, whereas links 1 and 3 form another maximal clique and are regarded as sharing the second logical channel. Since link 1 belongs to both maximal cliques, its transmission occupies both logical channels simultaneously. We now formalize this transformation. Consider a CSMA network whose sensing graph contains N maximal cliques. The network is equivalently represented as an N -channel network. For each link i, let Ui denote the set of maximal cliques to which it belongs. In the equivalent multi-channel network, link i is treated as a multi-channel device that adopts the following access rule: it can initiate transmission only when all channels in Ui are idle, and once transmission starts, it occupies all channels in Ui for τ time slots. It is important to emphasize that this equivalent multichannel representation is determined solely by the sensing graph GS . The transformation provides the basis for the analytical framework developed next, in which the activity of the resulting multi-channel network is modeled explicitly. 3 In graph theory, a clique is a subset of vertices such that every pair of distinct vertices is connected by an edge. 4 A maximal clique is a clique that cannot be extended by adding any adjacent vertex. The Bron–Kerbosch algorithm [25] is a widely used method for enumerating all maximal cliques, and its complexity will be discussed in Section VII.
5
Busy B
Idle I
time
Fig. 3: States of the logical channels. The -transition occurs
Channel 1 begins
starts at
The +1-transition occurs
Busy B time
Channel 2 begins
starts at
Busy B time Channel 3 begins
starts at
Busy B time (i)
Fig. 4: Definition and calculation of Dj .
B. Multi-Channel Model
process (X , V ) are then given by
The channel dynamics of the equivalent multi-channel network are modeled by a discrete-time Markov renewal process (X , V ) = {(Xj , Vj ) , j = 0, 1, . . .}, where Vj denotes the epoch of the j-th state transition and Xj denotes the network state immediately after that transition. The state Xj is defined as (1) (N −1) (1) (2) (N ) , (2) Xj = Xj , Xj , . . . , Xj , Dj , . . . , Dj {z } | {z } | Xjs
Algorithm 1: Determination of state-transition probabilities Input: The set of states of interest I Output: The transition probabilities pµ,ν of the embedded Markov chain 1 Initialize pµ,ν ← 0 for all µ, ν ∈ S; 2 for each state µ ∈ I do 3 Determine the set of links eligible for transmission in state µ, denoted by Kµ ; 4 Enumerate all feasible link-transmission combinations from Kµ ; 5 for each feasible transmission combination do 6 Compute its occurrence probability p; 7 Determine the next state ν; 8 pµ,ν ← pµ,ν + p; 9 end 10 end
Xjc
which consists of two components, namely Xjs and Xjc . The first component, Xjs , describes the states of the N logical (i) channels, where Xj denotes the state of channel i after the jth transition. As shown in Fig. 3, each channel has two possible states: busy (B) and idle (I). The busy state lasts for τB = τ time slots, whereas the idle state lasts for τI = 1 time slot. When a link belonging to multiple maximal cliques starts transmitting, all corresponding logical channels become busy simultaneously. Therefore, the state transitions of different channels are generally coupled rather than independent. To capture this coupling, the second component Xjc is introduced (i) as a set of time-offset variables. Specifically, Dj is defined as the difference between the starting times of the states of channel i + 1 and channel 1 at the j-th transition. Fig. 4 (i) illustrates the definition and calculation of Dj . Let S denote the state space of X , and let pν,µ denote the one-step transition probability from state ν ∈ S to state µ ∈ S. Algorithm 1 outlines the procedure for constructing these transition probabilities. The steady-state distribution of the embedded Markov chain X = {Xj } is obtained from P πν = µ∈S pµ,ν πµ , P (3) 1 = ν∈S πν , where πν denotes the steady-state probability of state ν in the embedded chain. The limiting state probabilities of the Markov renewal
πµ τµ π̃µ = P , πν τν
(4)
ν∈S
where τµ is the holding time of state µ ∈ S, measured in time slots. For a state X (1) , X (2) , . . . , X (N ) , D(1) , . . . , D(N −1) , the holding time is τ(X (1) ,X (2) ,...,X (N ) ,D(1) ,...,D(N −1) ) = min τX (1) , τX (2) + D(1) , . . . , τX (N ) + D(N −1) − max 0, D(1) , . . . , D(N −1) .
(5)
Given the sensing graph GS , the limiting state probabilities can be expressed explicitly as functions of the transmission probabilities q and the packet-transmission duration τ by using (3) and (4). As an illustrative example, consider the sensing graph in Fig. 2. The limiting state probabilities are 1 , D (1 − q1 )q2 π̃(I,B,k) = , D (1 − q1 )q3 π̃(B,I,k) = , D π̃(I,I,0) =
k = 0, . . . , 1 − τ,
(6)
k = 0, . . . , τ − 1.
2 respectively, where D = 1 + (1 − q1 )q2 q3 τ + 1 + (q2 + q3 − 1)(1 − q1 ) τ . The detailed derivation is provided in Appendix A. Based on these explicit expressions of the limiting state probabilities, the throughput of each link can be derived in a closed form in the next section.
V. L INK T HROUGHPUT In this section, we derive the throughput of each link as an explicit function of the transmission probabilities q.
6
A. Link Throughput The throughput of link i is given by X qi ϕi (µ) π̃µ , λ̂i = τ
(7)
µ∈Yi
where Yi denotes the set of network states in which link i is eligible to transmit, namely, n o Yi = X ∈ S : X (j) = I, ∀j ∈ Ui . (8) Here, ϕi (µ), referred to as the interruption-free probability, is the probability that a transmission initiated by link i at time t completes successfully without interruption, given that the network state at time t − 1 is µ. The term π̃µ is the limiting probability that the network is in state µ at time t − 1. The interruption-free probability can be computed by enumerating all interference-free transmission evolutions and evaluating their probabilities. To illustrate this computation, consider the topology in Fig. 2 and focus on link 2. Assume that τ = 3. Since link 2 belongs only to the first logical channel, it is eligible to transmit whenever that channel is idle. Therefore, Y2 = {(I, I, 0), (I, B, 0), (I, B, −1), (I, B, −2)}.
(9)
According to the interference graph in Fig. 2, links 1 and 3 can interrupt the transmission of link 2. Hence, a successful transmission of link 2 requires that neither link 1 nor link 3 transmits during the entire transmission interval. We next evaluate ϕ2 (µ) for each state in Y2 . 1) State (I, I, 0): When the network is in state (I, I, 0), all links are eligible to transmit in the next slot. The probability that neither link 1 nor link 3 transmits is (1 − q1 )(1 − q3 ). If only link 2 starts transmitting, the network moves to state (B, I, 0). In state (B, I, 0), only link 3 still senses an idle channel and may transmit in the next slot. The probability that link 3 remains silent is (1 − q3 ), which leads to state (B, I, −1). Repeating the same argument over the remaining slots of the transmission yields ϕ2 (I, I, 0) = (1 − q1 )(1 − q3 )3 .
(10)
2) States (I, B, 0) and (I, B, −1): In either of these states, link 3 is already transmitting and will remain active in the next slot. Therefore, any transmission initiated by link 2 is immediately subject to interference from link 3, and hence ϕ2 (I, B, D) = 0,
D ∈ {0, −1}.
(11)
3) State (I, B, −2): In this state, the ongoing transmission of link 3 ends in the next slot. The network then enters state (B, I, 0). To ensure that link 2 completes its transmission without interruption, link 3 must remain silent during the following two slots. Therefore, ϕ2 (I, B, −2) = (1 − q3 )2 .
(12)
Fig. 5: Illustration of the calculation of the probability that a transmission experiences no interruption during its entire duration.
The above calculation is illustrated graphically in Fig. 5. Substituting (10)–(12) into (7), the throughput of link 2 is obtained as λ̂2 = τ q2 (1 − q1 )(1 − q3 )3 π̃(I,I,0) (13) + (1 − q3 )2 π̃(I,B,−2) . Since the limiting state probabilities π̃ have already been expressed as explicit functions of q in Section IV-B, the throughput of link 2 can be further written explicitly as 3q2 (1 − q1 )(1 − q3 )2 (1 + q2 − q3 ) . 1 + 9(1 − q1 )q2 q3 + 3 1 + (q2 + q3 − 1)(1 − q1 ) (14) The same procedure applies to other links and other sensing/interference topologies. More importantly, the above derivation has a recursive structure and can therefore be implemented algorithmically. In particular, the interruptionfree probability can be computed via a depth-first search, as summarized in Algorithm 2. B. Link Throughput Approximation λ̂2 =
The exact evaluation of (7) requires computing the interruption-free probability over the entire transmission interval. Although Algorithm 29 yields an exact characterization by explicitly tracking the network evolution after transmission begins, the resulting computational complexity can be high. As pointed out in [26], there is generally a tradeoff between modeling accuracy and complexity. To reduce the computational burden5 , we derive a lower bound on the interruption-free probability and use it as a throughput approximation: n o Y ϕi (µ) ≥ Pr link j does not transmit during τ − gjµ j∈Ri
=
Y
µ
(1 − qj )τ −gj ,
j∈Ri
(15) where gjµ is the minimum number of time slots required for all channels sensed by link j to become idle when the network is in state µ. Again consider link 2 in the topology of Fig. 2, with τ = 3. According to the interference graph, both links 1 and 3 can interrupt the transmission of link 2. To illustrate the lower bound, consider the contribution of link 3. Since link 3 belongs only to the second maximal clique, it senses only the 5 The resulting complexity reduction is discussed in Section VII.
7
Algorithm 2: Depth-first search for exact throughput evaluation Input: Target link i Output: Throughput λ̂i 1 Initialize λ̂i ← 0; 2 Function DFS(µ, i) µ,i 3 Initialize Pno ← 0; 4 if the transmission of link i has ended in state µ then 5 return 1; 6 else 7 Find Kµ , the eligible links in state µ; 8 Enumerate all feasible transmission combinations from Kµ ; 9 Select the subset Siµ in which no interrupting link transmits; 10 for each transmission combination in Siµ do 11 Compute its occurrence probability p; 12 Determine the next state ν; µ,i µ,i 13 Pno ← Pno + p · DFS(ν, i); 14 end µ,i ; 15 return Pno 16 end 17 for each state µ ∈ Yi do µ,i 18 Compute Pnt , the probability that no link in Ri is transmitting; µ,i 19 if Pnt ̸= 0 then 20 Find Kµ , the eligible links in state µ; 21 Enumerate all feasible transmission combinations from Kµ ; 22 Select the subset Siµ in which link i transmits and no interrupting link transmits; 23 for each transmission combination in Siµ do 24 Compute its occurrence probability p; 25 Determine the next state ν; µ,i p DFS(ν, i) π̃µ ; 26 λ̂i ← λ̂i + Pnt 27 end 28 end 29 end second logical channel. When the network is in state (I, I, 0), (I,I,0) the second channel is already idle, and hence g3 = 0. Therefore, for link 2 to succeed, link 3 must remain silent (I,I,0) for the next τ − g3 = 3 slots, which gives the factor (I,I,0) τ −g3 (1 − q3 ) . When the network is in state (I, B, −2), the second channel (I,B,−2) becomes idle in the next slot, and thus g3 = 1. In this case, the probability that link 3 remains silent for the (I,B,−2) (I,B,−2) subsequent τ −g3 = 2 slots is at least (1−q3 )τ −g3 . Accordingly, a lower bound on the throughput of link 2 is 3 3 2 λ̂2 ≥ λ̂LB 2 = τ q2 (1 − q1 ) (1 − q3 ) π̃(I,I,0) + (1 − q3 ) π̃(I,B,−2) .
(16) The corresponding approximation procedure is summarized in Algorithm 3.
Algorithm 3: Approximate evaluation of link throughput Input: Target link i Output: Lower bound λ̂LB i LB 1 Initialize λ̂i ← 0; 2 for each state µ ∈ Yi do µ,i 3 Compute Pnt , the probability that no link in Ri is transmitting; µ,i 4 if Pnt ̸= 0 then 5 Compute gjµ for each j ∈ Ri ; µ,i Q τ −gjµ ← λ̂LB π̃µ ; 6 λ̂LB i + Pnt i j∈Ri (1 − qj ) 7 end 8 end C. Special Case: Interference Graph as a Subgraph of the Sensing Graph We next consider a special case in which the interference graph is a subgraph of the sensing graph. A typical practical example is the request-to-send/clear-to-send (RTS/CTS) mechanism, which is widely used to mitigate the hiddenterminal problem. Under RTS/CTS, before transmitting a data packet, the transmitter first sends an RTS frame, and the intended receiver responds with a CTS frame. Nodes that hear either the RTS or the CTS defer their own transmissions for the announced duration. As a result, hidden terminals are prevented from interrupting an ongoing transmission once the RTS/CTS exchange has been successfully completed. Under this mechanism, the effective interference relationship is restricted by the sensing relationship, and the interference graph GI becomes a subgraph of the sensing graph GS . Indeed, if link i can interfere with link j, then the transmitter of link i lies within the reception range of the receiver of link j. Hence, when link j successfully initiates transmission, the transmitter of link i can hear the CTS sent by the receiver of link j and will defer its own access. Note, however, that RTS/CTS does not eliminate collisions entirely. Due to non-negligible propagation delay, two links within hearing range may still initiate transmission simultaneously, causing a collision at the beginning of the transmission. The key effect of RTS/CTS is that collisions can only occur at transmission initiation, rather than during an ongoing transmission. Therefore, the interruption-free probability in (7) is greatly simplified and can be written as ϕi (µ) =
Y
(1 − qj ),
(17)
j∈Kµ ∩Ri
where Kµ ∩ Ri denotes the set of links that are both eligible to transmit in state µ and capable of interfering with link i at transmission initiation. Again consider link 2 in the topology of Fig. 2. Under RTS/CTS, the hidden-terminal interference from link 3 to link 2 is removed, and only collisions occurring at transmission initiation need to be considered. Since Appendix A expresses the limiting state probabilities π̃ explicitly as functions of the packet duration τ , the throughput of link 2 can be written as
8
Network topology:
coverage regions of multiple BSSs can sense transmissions from more than one BSS and therefore experience a lower probability of finding the channel idle. This gives rise to strong coupling among the medium-access behaviors of different BSSs. Consider the uplink of an IEEE 802.11 DCF network with M BSSs, where multiple stations in each BSS transmit to a AP 1 AP 2 common AP. Each station therefore forms one link with its associated AP, and all BSSs share the same spectrum. We define the coverage of a BSS as the region centered at its AP within which the AP can hear the transmissions of all associated nodes. Since the coverage regions of different BSSs Aggregation Link Sensing graph: Aggregation Link Contention graph: may overlap, some nodes may be heard by multiple APs and The aggregation link of Group associate with one of them. For carrier sensing, we assume that nodes infer channel availability from AP feedback rather than relying solely on direct sensing. In practice, this feedback can be realized through RTS/CTS: after receiving an RTS frame, the AP broadcasts a maximal clique maximal clique CTS frame indicating the channel occupation duration, and all nodes that hear the AP defer their transmissions accordingly, Equivalent Multi-Channel Network even if they cannot directly hear the transmitting node. Under this mechanism, nodes in overlapping coverage regions can obAggregation link transmits on the channel channel tain channel availability information from multiple APs, while time their own transmissions may affect not only the associated BSS Aggregation and Link transmits on the and channel channel but also neighboring BSSs. time To characterize channel occupancy, let τT denote the duraAggregation link transmits on the channel tion of a successful transmission, measured in slots. For IEEE Fig. 6: Illustration of link aggregation. 802.11, τT can be written as [27] an explicit function of both τ and q: λ̂2 = τ q2 (1 − q1 )π̃(I,I,0) + π̃(I,B,0) + π̃(I,B,−1) + π̃(I,B,−2) ACK LP + MAC header + SIFS + τT = R Basic Rate τ q2 (1 − q1 )(1 + τ q2 ) . = ! (19) 1 + τ 2 (1 − q1 )q2 q3 + τ 1 + (q2 + q3 − 1)(1 − q1 ) . (18) + DIFS + PHY preamble σ, VI. C ASE S TUDY In this section, we apply the proposed analytical framework to two representative CSMA scenarios: multi-BSS IEEE 802.11 networks with universal frequency reuse, and adhoc networks. These two scenarios cover both infrastructurebased and decentralized wireless networks and highlight the capability of the proposed model to handle strong spatial coupling, hidden terminals, exposed terminals, and flow-inthe-middle effects. A. Multi-BSS IEEE 802.11 Networks with Universal Frequency Reuse 1) System Model An important application of CSMA networks is IEEE 802.11, in which the network consists of multiple basic service sets (BSSs). Each BSS has a star topology centered at an access point (AP), and multiple stations access the medium through the distributed coordination function (DCF). Due to the limited availability of unlicensed spectrum, multiple BSSs often operate on the same frequency band, i.e., under universal frequency reuse. In such deployments, nodes at different locations may observe different carrier-sensing environments. In particular, as illustrated in Fig. 6, nodes located in overlapping
where σ is the slot duration. We further assume that the channel occupancy in collision, denoted by τF , satisfies τF = τT = τ . This corresponds to a conservative setting in which a collision occupies the channel for the same duration as a successful transmission. Let M = {1, 2, . . . , M } denote the set of BSSs. Since a node may be heard by multiple APs, we group the links according to two attributes: the BSS i with which the node is associated, and the subset S ⊆ M of APs that can hear that node. The corresponding group is denoted by Gi,S . Let |Gi,S | = n(i,S) be the number of nodes in this group, and let qi denote the transmission probability of a node associated with BSS i. Links in the same group Gi,S have identical sensing and interference relationships and can sense one another. Therefore, all links in the same group can be aggregated into a single equivalent link. As illustrated in Fig. 6, after aggregating nodes into group-level links, the multi-BSS IEEE 802.11 network can be represented as an equivalent multi-channel network. The throughput analysis then follows directly from the framework developed in Section IV. Let λ̂A (i,S) denote the throughput of the aggregation link corresponding to group Gi,S . The
9
throughput of an individual node in that group is given by (i,S)
λ̂(i,S) =
−1 qi (1 − qi )n λ̂A (i,S) (i,S) , n 1 − (1 − qi )
(20)
where the prefactor is the probability that, conditioned on a successful transmission of the aggregation link, exactly one node in the group transmits. The total network throughput is then given by X X n(i,S) λ̂(i,S) . (21) λ̂out = i∈M S⊆M
2) Simulation Results We next validate the proposed analysis through eventdriven simulation. In all simulations, each transmitter is saturated. A transmitter selects its backoff counter uniformly from {0, 1, . . . , Wi }, where Wi is the backoff window, senses the channel at the beginning of each slot, and decrements its counter by one whenever the channel is sensed idle. A transmission starts when the backoff counter reaches zero. The simulated throughput is computed as τ N/T , where N is the number of successfully transmitted packets over an observation interval of T = 109 slots. The system parameter setting follows [27], except that the payload length is set to LP = 18432 bits, with τ computed according to (19), yielding τ = 27. We first consider the two-BSS topology shown in Fig. 6. In this network, nodes are divided into four groups: G1,{1} , G2,{2} , G1,{1,2} , and G2,{1,2} . Nodes in Gi,{i} belong to BSS i and can be heard only by AP i, whereas nodes in Gi,{1,2} belong to BSS i but are within the coverage of both AP 1 and AP 2. For each node in BSS i, the backoff window is Wi , and the corresponding transmission probability after sensing an idle channel is qi = 2/(Wi + 1) [5]. To benchmark the proposed model, we compare it with three representative baselines. • HOL: We use the analytical model in [28] as the representative node-centric baseline. In that model, a discrete-time Markov renewal process is established for the head-ofline (HOL) packet of a node in group Gi,S . The service rate of a node in that group is (i,S)
π̃T
=
α(i,S) τ (i)
α(i,S) τ + τ 1−p p(i)
1 i + p(i) · 1+W 2
,
(22)
where α(i,S) is the probability that a node in group Gi,S senses the channel idle, and p(i) is the probability of successful transmission of a HOL packet in BSS i. • CTMC: We use the model in [23] as the representative set-centric baseline. It characterizes the network by the independent sets of simultaneously active links and is known to be accurate when collisions caused by simultaneous transmission attempts are negligible. • BOE: We also consider the Back-of-the-Envelope (BOE) method in [13]. BOE computes normalized link throughput from the maximum independent sets (MISs) of the contention graph. Specifically, if nBOE is the number of MISs and nBOE is the number of MISs containing link i, i then the normalized throughput of link i is nBOE /nBOE . i
Fig. 7a shows how the network throughput changes with the number of nodes in the overlapping region, n(1,{1,2}) . The proposed model consistently agrees well with simulation across the entire range of n(1,{1,2}) . In contrast, the HOL baseline underestimates the throughput, while both the CTMC and BOE baselines significantly overestimate it. The reasons for the loss of accuracy in the HOL and CTMC baselines are different. For the HOL model [28], a key parameter is α(i,S) , the probability that a node in Gi,S senses the channel idle. To obtain a tractable model, this quantity is approximated as Y α(i,S) = α(j,{j}) . (23) j∈S
Equation (23) assumes that the idle-sensing events seen by different BSSs are independent. This approximation becomes increasingly inaccurate when transmissions in the overlapping region become more frequent, because those transmissions induce common busy periods observed by multiple BSSs and therefore introduce strong correlation in channel sensing. The CTMC model [23] tends to be optimistic, as shown in Fig. 7a. Although it captures contention interactions at the network-state level, it still relies on a continuous-time abstraction with independent exponential backoff timers. This approximation becomes inaccurate under high contention, where synchronized transmission attempts are no longer negligible, and therefore leads to overly optimistic throughput predictions. The BOE method also deviates noticeably from simulation in Fig. 7a. This is expected because BOE is derived from the ideal CSMA network model, which assumes zero propagation delay and zero duration for failed transmissions, whereas both effects are non-negligible in the simulations considered here. By contrast, the proposed model maintains high accuracy in dense overlapping regions and under high transmission probability. This is because the model represents the network state jointly across multiple logical channels and explicitly includes timedomain variables that capture their coupling. As a result, the correlation induced by shared overlapping nodes is preserved rather than approximated away. Fig. 7b shows the total network throughput as a function of the backoff window W in a dense overlapping region with n(1,{1,2}) = n(2,{1,2}) = 20. The figure indicates that the backoff window has a strong impact on network performance: both overly small and overly large values of W reduce the total throughput, and hence careful tuning is necessary. Indeed, the optimal backoff window predicted by the proposed model, denoted by Wm , differs substantially from that obtained by HOL the HOL model, denoted by Wm . The throughput achieved by using Wm yields a 25.1% improvement over that obtained HOL using Wm . These results show that the proposed model can accurately characterize multi-BSS performance across a wide range of node densities and can provide more reliable guidance for backoff-window optimization. 6 B. Ad-hoc Networks Another important class of CSMA networks is the ad-hoc network. As illustrated in Fig. 8, an ad-hoc network consists 6 The CTMC baseline is omitted due to its prohibitive computational complexity in dense scenarios.
10
1.8
9
1.6
8
1.4
7
1.2
6
Simulation Analysis in this paper Analysis of HOL method Analysis of CTMC method Analysis of BOE
5 4
Simulation Analysis in this paper Analysis of HOL method
^ out jW =W = 1:23 6 m ^ out jW =W HOL = 0:983 6 m
1 0.8 0.6
3
0.4
2
0.2
6
7
8 9 n(1;f1;2g)
10
11
12
13
14
15
(a)
92
96
48
24
2
6
8
64
32
81
5
40
4
20
3
WmHOL
51
2
X
25
1
16
0
6 8
2
X
10
Wm
0
12
1
4
Total Network Throughput
10
W (b)
Fig. 7: Total network throughput performance in a two-BSS network with τ = 27. (a) Network throughput versus n(1,{1,2}) . W (1) = W (2) = 32, n(1,{1}) = n(2,{2}) = n(2,{1,2}) = 4 (b) Network throughput versus the backoff window W . W (1) = W (2) = W , n(1,{1}) = n(2,{2}) = n(1,{1,2}) = n(2,{1,2}) = 20.
Fig. 8: Illustration of ad-hoc scenarios.
of multiple autonomous nodes that communicate directly with one another without centralized infrastructure. Due to the absence of coordinating entities such as APs, ad-hoc networks are more vulnerable to interference-related phenomena. In this subsection, we consider a representative topology that simultaneously exhibits the hidden-terminal problem, the exposedterminal problem, and the flow-in-the-middle effect. These phenomena are known to degrade network performance by increasing collisions and introducing unfair access opportunities. The system assumptions are the same as those in Section III and are not repeated here. We evaluate the nine-link ad-hoc topology shown in Fig. 9. This topology simultaneously exhibits hidden-terminal, exposed-terminal, and flow-in-the-middle effects. In particular, link 6 cannot sense link 8, while the transmission of link 8 can still interfere with link 6, which gives rise to a hidden-terminal effect. In addition, link 2 can sense link 5 even though link 5 does not interfere with the reception of link 2, corresponding to an exposed-terminal effect. Meanwhile, in the sensing graph, link 2 is coupled with links 1, 3, 4, and 5, and thus serves as the flow-in-the-middle link in this topology. In Fig. 10a, the exact analysis is compared with simulations, whereas Fig. 10b presents the lower-bound approximation together with the simulation results. The exact analysis matches the simulated throughput of all links closely over the entire range of W . The approximation is also accurate for most links, and its visible deviation is concentrated on link 6, i.e.,
the link affected by the hidden terminal. In this case, the approximate result is slightly lower than the exact one, but it still remains close to the simulation. In Fig. 10c, the CTMC baseline is compared with simulations. As W decreases and the transmission probability increases, the CTMC prediction departs increasingly from the simulated results because collisions caused by simultaneous transmission attempts are not properly captured. Moreover, the CTMC baseline fails to distinguish the asymmetric hidden-terminal impact on links 6 and 7, and therefore predicts the same throughput for these two links, whereas the simulation shows that link 6 achieves lower throughput than link 7 due to the interference from link 8. Overall, the proposed model captures both nonzerodelay collisions and hidden-terminal effects, and therefore provides a much more accurate characterization of per-link throughput in this strongly coupled ad-hoc topology.
Fig. 11 further shows the total network throughput for the same topology. We compare the optimal backoff window obtained from the proposed exact model, denoted by Wm , the CTMC CTMC baseline, denoted by Wm , and the approximation, Approx denoted by Wm . Because the predicted throughput of the CTMC model keeps increasing as W decreases, and the resulting optimization would incorrectly favor an excessively small backoff window. In other words, based on the CTMC analysis, the optimal W would be driven toward the smallest possible value, which is clearly inconsistent with the simulation results. By contrast, the proposed model captures the throughput degradation caused by collisions in the small-W regime and therefore provides a more accurate characterization of the system. More importantly, the optimal backoff window predicted by the approximation coincides with that predicted by the exact analysis, which indicates that the approximation is effective for parameter optimization even when hidden terminals are present.
11
Fig. 9: Sensing graph and interference graph of an ad-hoc network with nine links.
Sim
Ana
Sim Ana Approx
Sim
CTMC
1
1
1
2
2
2
3
3
3
4
4
4
5
5
5
6
6
6
7
7
7
8
8
9
9
8 9
(a)
(b)
(c)
Fig. 10: Throughput performance of the ad-hoc network in Fig. 9 with τ = 3.
Total Network Throughput
2.5
Sim Ana Ana Approx CTMC
2
1.5
^ out jW =W = 1:291 6 m
1
0.5
WmCTMC 0X 2
Wm = WmApprox X
4
6
8
16
32
64
128
W
Fig. 11: Total network throughput for the topology in Fig. 9, with τ = 3.
VII. C OMPUTATIONAL C OMPLEXITY A NALYSIS In the previous sections, we showed that the proposed analytical framework can derive explicit throughput expressions for a given CSMA topology. In this section, we analyze its computational complexity. The overall complexity arises from three main components: the construction of the equivalent multi-channel network, the solution of the Markov steadystate equations, and the evaluation of the interruption-free probability in the presence of hidden terminals. The first source of complexity comes from transforming the original CSMA network into the equivalent multi-channel network. This step requires identifying all maximal cliques in the sensing graph GS . To this end, we employ the Bron– Kerbosch algorithm, which recursively explores candidate cliques while pruning infeasible branches, as summarized in Algorithm 11. The worst-case time complexity of this algorithm is O(3K/3 ) [25], where K is the number of vertices in the graph. On the other hand, for certain sparse graph families, such as planar graphs and graphs with low arboricity, the number of maximal cliques grows only linearly with the number of vertices. In such cases, all maximal cliques can be
Algorithm 4: Bron–Kerbosch Algorithm Input: Graph GS (V, ES ) Output: All maximal cliques in GS 1 Initialize R ← ∅, P ← V, X ← ∅; 2 Function BronKerbosch(R, P, X) 3 if P = ∅ and X = ∅ then 4 Output R as a maximal clique; 5 end 6 foreach v ∈ P do 7 BronKerbosch(R ∪ {v}, P ∩ N (v), X ∩ N (v)); 8 P ← P \ {v}; 9 X ← X ∪ {v}; 10 end 11 BronKerbosch(R, P, X); enumerated in linear time [29], [30]. The second component of complexity arises from solving the steady-state linear system associated with the embedded Markov chain, namely (3). If this linear system is solved by Gaussian elimination, the computational complexity is O(n3 ), where n is the number of variables, equivalently the number of network states. Before simplification, the number of states is on the order of 2N τ 2(N −1) , where N is the number of logical channels, i.e., the number of maximal cliques, and τ is the packet-transmission duration. Therefore, this part of the complexity increases exponentially with both the number of channels and the packet duration. For example, when τ = 4 and N = 4, the total number of states is 8192. However, by applying the state-space reduction procedure described in Appendix A, the number of variables can be reduced substantially. After simplification,Pthe number of N effective variables becomes approximately i=1 Ni , which
12
corresponds to the number of states in I and depends only on the number of channels. For example, when N = 5, the number of reduced states is only 31. This reduction greatly improves the tractability of the steady-state analysis. The third source of complexity appears in scenarios where hidden terminals are present. In this case, one must compute the interruption-free probability appearing in (7). The complexity of this computation grows exponentially with τ , because all non-interfering transmission evolutions over the τ -slot transmission interval must be enumerated and their probabilities accumulated. The resulting complexity is O τ 2K 2N τ 2(N −1) , where 2K accounts for all possible linktransmission combinations, and 2N τ 2(N −1) accounts for all possible network states. The key reason for this complexity is that the exact computation requires a recursive exploration of future network states throughout the entire transmission interval. For each state, all feasible link-transmission combinations must be examined in order to determine whether the tagged transmission remains uninterrupted. By contrast, the lower-bound approximation introduced in Section V-B avoids this state-by-state recursion and instead estimates the interruption-free probability directly from the earliest channel-access opportunities of the interfering links. Consequently, neither the detailed dynamics over the last τ slots nor the exhaustive set of link-transmission combinations needs to be enumerated. The resulting computational complexity is reduced to O(KN ). Overall, the proposed framework incurs higher complexity than simplified node-centric approximations, but this additional cost enables it to capture global coupling, nonzero-delay collisions, and hidden-terminal effects more accurately. Moreover, the state-space reduction and lower-bound approximation substantially improve the computational tractability of the framework, especially when the number of maximal cliques in the sensing graph and the packet transmission duration are not excessively large. VIII. C ONCLUSION In this paper, we developed a new analytical framework for throughput characterization in wireless CSMA networks with arbitrary sensing and interference topologies. By explicitly modeling sensing and interference through two distinct graphs, and by transforming the original CSMA network into an equivalent multi-channel network modeled via a discrete-time Markov renewal process, the proposed framework captures global coupling among links and enables explicit throughput characterization. The proposed analysis was applied to several representative CSMA scenarios, including multi-BSS IEEE 802.11 networks with universal frequency reuse, and ad-hoc topologies exhibiting hidden-terminal, exposed-terminal, and flow-in-the-middle effects. Simulation results showed that the proposed model achieves more accurate throughput estimation than existing analytical approaches, especially in dense deployments and in scenarios with strong coupling among link behaviors. The resulting explicit expressions also provide useful insight into access-parameter optimization, such as backoff-window selection. Finally, we analyzed the computational complexity of
the framework and discussed practical complexity-reduction methods. A PPENDIX A E XPLICIT F UNCTIONS OF THE L IMITING S TATE P ROBABILITIES In Section IV-B, the limiting state probabilities were expressed as explicit functions of the transmission probabilities q. In this appendix, we further derive these probabilities as explicit functions of the packet-transmission duration τ . A main difficulty is that the number of equations in (3) depends on τ , which makes it difficult to solve the resulting linear system analytically and obtain closed-form expressions in terms of τ . To address this issue, we transform (3) into an equivalent system whose dimension is independent of τ . We first rewrite (3) as a system involving only the limiting state probabilities of the states in I. Using the transformation procedure described in Appendix B, (3) and (4) can be organized into the matrix form y = Ay + b,
(24)
where y is the vector of limiting state probabilities associated with the states in I, and b is a constant vector. Specifically, T y = π̃(I,I,...,I,0,...,0) , · · · (25) and b=
1 , 0, · · · , 0 τ
T .
(26)
It can be observed that, for different values of τ , some states in I have identical limiting state probabilities. This property can be formalized as follows. For a state µ ∈ S, let Iµ denote the set of indices of idle channels: n o Iµ = i : X (i) = I, i ∈ {1, . . . , N } . (27) For the busy channels, group together the indices of channels that become busy simultaneously. Let these subsets be denoted by C1 , C2 , . . ., and collect them into the set Bµ = {C1 , C2 , . . . } .
(28)
Then, for two states µ, ν ∈ S, if Iµ = Iν
and
Bµ = Bν ,
we have π̃µ = π̃ν . By merging states with identical limiting state probabilities, the system (24) can be compressed into a reduced system whose dimension is independent of τ . Consequently, the limiting state probabilities can be derived explicitly as functions of both τ and q. We next illustrate this reduction procedure using the topology in Fig. 6. Following Appendix B, (3) can first be transformed into a system involving only the limiting state probabilities of the states in I, namely y = Ay + b,
(29)
13
where h iT y = π̃(I,I,0) , π̃(I,B,0) , · · · , π̃(I,B,1−τ ) , π̃(B,I,0) , · · · , π̃(B,I,τ −1)
(30) and b=
T 1 , 0, · · · , 0 . τ
(31)
The coefficient matrix A is shown in Fig. 12. Here, ρ1 = 1 − q1 ,
ρ2 = 1 − q2 ,
A PPENDIX B T RANSFORMATION OF (3) This appendix explains how to transform (3) into a system involving only the limiting state probabilities of the states in I. The key idea is to eliminate the limiting state probabilities of the states in B and express them in terms of those in I. The transformation consists of two steps. First, we transform the limiting state probabilities of all states in B except the state (B(1) , B(2) , . . . , B(N ) , 0, . . . , 0),
ρ3 = 1 − q3 ,
in which all channels are busy and start their busy periods simultaneously. This is done by using the embedded 1 h(i) = − 1+(τ −i)(1−ρ3 )Markov . chain to identify all paths from idle states to the τ target busy state and then accumulating the corresponding Note that the dimension of (29) depends on τ . We now transition probabilities along these paths. In this way, each reduce this system by merging states with equal limiting state non-synchronized busy-state probability can be represented as probabilities. For the state (I, B, k), where k ∈ {0, . . . , 1 − τ }, a linear combination of the limiting state probabilities of the we have idle-state set. Second, we transform the remaining limiting state probabilI(I,B,k) = {1}, B(I,B,k) = {{2}}. (33) ity of the fully synchronized busy state
1 g(i) = − 1+(τ −i)(1−ρ2 ) , τ
µ0 = (B(1) , B(2) , . . . , B(N ) , 0, . . . , 0).
Therefore,
To do so, we use the normalization condition X Pr{the network state is µ at time t} = 1.
π̃(I,B,0) = π̃(I,B,−1) = · · · = π̃(I,B,1−τ ) = π̃(I,B) . Similarly,
This condition states that, at any slot t, the network must be in one of the states in S. Therefore, X π̃µ0 = 1 − Pr{the network state is µ at time t}. (42)
π̃(B,I,0) = π̃(B,I,1) = · · · = π̃(B,I,τ −1) = π̃(B,I) . Hence, (29) can be compressed into yc = Ac yc + bc ,
(34)
where T yc = π̃(I,I,0) , π̃(I,B) , π̃(B,I) , " Ac =
(41)
µ∈S
ρ1 ρ2 ρ3 − τ1 ρ1 ρ2 (1 − ρ3 ) ρ1 ρ3 (1 − ρ2 )
τ +1 (ρ2 − 1) 2
τ +1 (ρ3 − 1) 2 1 − ρ3
0 1 − ρ2
(35) # ,
(36)
0
µ∈S µ̸=µ0
Hence, the limiting state probability of the fully synchronized busy state can also be represented in terms of the limiting state probabilities of the idle-state set. Combining the above two steps yields a reduced linear system involving only the limiting state probabilities of the states in I. This reduced system is then used in Appendix A to derive explicit expressions for the limiting state probabilities.
and bc =
1 , 0, 0 τ
R EFERENCES
T .
(37)
The reduced system (34) has a dimension independent of τ , which allows the limiting state probabilities to be derived analytically as explicit functions of τ . Solving (34) yields π̃(I,I,0) =
1 , 1 + ρ1 (ρ3 − 1)(ρ2 − 1)τ 2 + 1 + (−ρ2 − ρ3 + 1)ρ1 τ
(38) −ρ1 (ρ2 − 1) , π̃(I,B) = 1 + ρ1 (ρ3 − 1)(ρ2 − 1)τ 2 + 1 + (−ρ2 − ρ3 + 1)ρ1 τ
(39) and π̃(B,I) =
−ρ1 (ρ3 − 1) , 1 + ρ1 (ρ3 − 1)(ρ2 − 1)τ 2 + 1 + (−ρ2 − ρ3 + 1)ρ1 τ
(40) respectively.
[1] L. Kleinrock and F. Tobagi, “Packet switching in radio channels: Part i-carrier sense multiple-access modes and their throughput-delay characteristics,” IEEE Transactions on Communications, vol. 23, no. 12, pp. 1400–1416, 1975. [2] G. Bianchi, “Performance Analysis of the IEEE 802.11 Distributed Coordination Function,” IEEE Journal on selected areas in communications, vol. 18, no. 3, pp. 535–547, 2000. [3] D. Malone, K. Duffy, and D. J. Leith, “Modeling the 802.11 distributed coordination function in nonsaturated heterogeneous conditions,” IEEE/ACM Transactions on Networking, vol. 15, no. 1, pp. 159– 172, 2007. [4] F. Daneshgaran, M. Laddomada, F. Mesiti, and M. Mondin, “Unsaturated throughput analysis of IEEE 802.11 in presence of non ideal transmission channel and capture effects,” IEEE Transactions on Wireless Communications, vol. 7, no. 4, pp. 1276–1286, 2008. [5] L. Dai and X. Sun, “A unified analysis of IEEE 802.11 DCF networks: Stability, throughput, and delay,” IEEE Transactions on Mobile Computing, vol. 12, no. 8, pp. 1558–1572, 2013. [6] ——, “Backoff design for IEEE 802.11 DCF networks: Fundamental tradeoff between throughput performance and delay,” IEEE/ACM Transactions on Networking, vol. 23, no. 4, pp. 1196–1209, 2015.
14
ρ1 ρ2 ρ3 − τ1 ρ1 ρ2 (1 − ρ3 ) 0 A= 0 ρ1 ρ3 (1 − ρ2 ) 0
0
g(1) 0 ρ2 .. . 0 0 0 .. . 1 − ρ2
··· ··· .. . ··· ··· . .. ···
g(τ − 1) 0 0 .. . ρ2 0 1 − ρ2 .. . 0
ρ2 + g(τ ) 0 0 .. . 0 1 − ρ2 0 .. . 0
h(1) 0 0 .. . 1 − ρ3 0 ρ3 .. . 0
··· ··· . .. ··· ··· .. . ···
h(τ − 1) 0 1 − ρ3 .. . 0 0 0 .. . ρ3
ρ3 + h(τ ) 1 − ρ3 0 0 0 0 0
,
(32)
((2τ +1)×(2τ +1))
Fig. 12: Coefficient matrix A in (29).
[7] R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin, “Throughput analysis in multihop csma packet radio networks,” IEEE Transactions on Communications, vol. 35, no. 3, pp. 267–274, 1987. [8] X. Wang and K. Kar, “Throughput modelling and fairness issues in csma/ca based ad-hoc networks,” in Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., vol. 1. Ieee, 2005, pp. 23–34. [9] M. Durvy, O. Dousse, and P. Thiran, “On the fairness of large csma networks,” IEEE Journal on Selected Areas in Communications, vol. 27, no. 7, pp. 1093–1104, 2009. [10] B. Bellalta, A. Checco, A. Zocca, and J. Barcelo, “On the interactions between multiple overlapping wlans using channel bonding,” IEEE Transactions on Vehicular Technology, vol. 65, no. 2, pp. 796–812, 2015. [11] A. Faridi, B. Bellalta, and A. Checco, “Analysis of dynamic channel bonding in dense networks of wlans,” IEEE Transactions on Mobile Computing, vol. 16, no. 8, pp. 2118–2131, 2016. [12] F. D. Tarzjani and B. Krishnamachari, “Computing the saturation throughput for heterogeneous p-csma in a general wireless network,” in 2025 34th International Conference on Computer Communications and Networks (ICCCN). IEEE, 2025, pp. 1–7. [13] S. C. Liew, C. Kai, J. Leung, and B. Wong, “Back-of-the-envelope computation of throughput distributions in csma wireless networks,” in 2009 IEEE International Conference on Communications, 2009, pp. 1– 6. [14] P. C. Ng and S. C. Liew, “Throughput analysis of ieee802. 11 multihop ad hoc networks,” IEEE/ACM Transactions on networking, vol. 15, no. 2, pp. 309–322, 2007. [15] Y. Gao, D.-M. Chiu, and J. C. Lui, “Determining the end-to-end throughput capacity in multi-hop networks: methodology and applications,” in Proceedings of the joint international conference on Measurement and modeling of computer systems, 2006, pp. 39–50. [16] A. Jindal and K. Psounis, “The achievable rate region of 802.11scheduled multihop networks,” IEEE/ACM Transactions on Networking, vol. 17, no. 4, pp. 1118–1131, 2009. [17] Y. Gao, L. Dai, and X. Hei, “Throughput optimization of multi-bss ieee 802.11 networks with universal frequency reuse,” IEEE Transactions on Communications, vol. 65, no. 8, pp. 3399–3414, 2017. [18] M. Garetto, J. Shi, and E. W. Knightly, “Modeling media access in embedded two-flow topologies of multi-hop wireless networks,” in Proceedings of the 11th annual international conference on Mobile computing and networking, 2005, pp. 200–214. [19] B.-J. Jang and M. L. Sichitiu, “IEEE 802.11 saturation throughput analysis in the presence of hidden terminals,” IEEE/ACM Transactions on Networking, vol. 20, no. 2, pp. 557–570, 2012. [20] F. Wilhelmi, S. Barrachina-Muñoz, C. Cano, I. Selinis, and B. Bellalta, “Spatial reuse in IEEE 802.11ax WLANs,” Computer Communications, vol. 170, pp. 65–83, 2021. [21] L. Lanante and S. Roy, “Performance analysis of the IEEE 802.11ax OBSS PD-based spatial reuse,” IEEE/ACM Transactions on Networking, vol. 30, no. 2, pp. 616–628, 2022. [22] M. Garetto, T. Salonidis, and E. W. Knightly, “Modeling per-flow throughput and capturing starvation in csma multi-hop wireless networks,” IEEE/ACM Transactions on Networking, vol. 16, no. 4, pp. 864–877, 2008. [23] B. Nardelli and E. W. Knightly, “Closed-form throughput expressions for csma networks with collisions and hidden terminals,” in 2012 Proceedings IEEE INFOCOM. IEEE, 2012, pp. 2309–2317. [24] K. Medepalli and F. A. Tobagi, “Towards performance modeling of ieee 802.11 based wireless networks: A unified framework and its applica-
tions,” in Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications. IEEE, 2006, pp. 1–12. [25] C. Bron and J. Kerbosch, “Algorithm 457: finding all cliques of an undirected graph,” Commun. ACM, vol. 16, no. 9, p. 575–577, Sept. 1973. [Online]. Available: https://doi.org/10.1145/362342.362367 [26] I. Tinnirello and G. Bianchi, “Rethinking the ieee 802.11 e edca performance modeling methodology,” IEEE/ACM transactions on networking, vol. 18, no. 2, pp. 540–553, 2009. [27] J. Zhang, Y. Gao, X. Sun, W. Zhan, P. Liu, and Z. Guo, “Synchronous Multi-Link Access in IEEE 802.11 be: Modeling and Network Sum Rate Optimization,” in Proc. IEEE ICC, 2022, pp. 2309–2314. [28] Y. Gao, L. Dai, and X. Hei, “Throughput optimization of multi-bss ieee 802.11 networks with universal frequency reuse,” IEEE Transactions on Communications, vol. 65, no. 8, pp. 3399–3414, 2017. [29] N. Chiba and T. Nishizeki, “Arboricity and subgraph listing algorithms,” SIAM Journal on computing, vol. 14, no. 1, pp. 210–223, 1985. [30] M. Chrobak and D. Eppstein, “Planar orientations with low out-degree and compaction of adjacency matrices,” Theoretical Computer Science, vol. 86, no. 2, pp. 243–266, 1991.