Accurate and Efficient Modeling of 802.15.4
Unslotted CSMA/CA through Event Chains
Computation
Domenico De Guglielmo, Francesco Restuccia, Giuseppe Anastasi, Marco Conti, and Sajal K. Das
Abstract—Many analytical models have been proposed for evaluating the performance of event-driven 802.15.4 Wireless Sensor Networks (WSNs), in Non-Beacon Enabled (NBE) mode. However, existing models do not provide accurate analysis of large-scale WSNs, due to tractability issues and/or simplifying assumptions. In this paper, we propose a new approach called Event Chains Computation (ECC) to model the unslotted CSMA/CA algorithm used for channel access in NBE mode. ECC relies on the idea that outcomes of the CSMA/CA algorithm can be represented as chains of events that subsequently occur in the network. Although ECC can generate all the possible outcomes, it only considers chains with a probability to occur greater than a pre-defined threshold to reduce complexity. Furthermore, ECC parallelizes the computation by managing different chains through different threads. Our results show that, by an appropriate threshold selection, the time to derive performance metrics can be drastically reduced, with negligible impact on accuracy. We also show that the computation time decreases almost linearly with the number of employed threads. We validate our model through simulations and testbed experiments, and use it to investigate the impact of different parameters on the WSN performance, in terms of delivery ratio, latency, and energy consumption.
Index Terms—Wireless Sensor Networks, IEEE 802.15.4, Non-Beacon Enabled mode, unslotted CSMA/CA, Performance Analysis. 3
1
1 INTRODUCTION
The IEEE 802.15.4 standard is currently the reference communication technology for wireless sensor networks (WSNs) [1] and is expected to be a major enabling technology for the future Internet of Things (IoT) [3]. The 802.15.4 standard addresses the physical and medium access control (MAC) layers of the networking stack and is complemented by the ZigBee specifications [2] that cover the network and application layers.
Due to the wide range of potential applications, rang- ing from environmental monitoring to smart grids, from urban mobility to healthcare, from industrial applica- tions to mobile ticketing and assisted driving, and so on, the 802.15.4 standard leverages a number of different access methods to cope with different quality of service (QoS) requirements. In particular, the standard defines a Beacon-Enabled (BE) mode and a Non-Beacon-Enabled (NBE) mode. The BE mode relies on a periodic super- frame bounded by beacons, which are special synchro- nization messages generated by coordinator nodes. Each sensor node waits for the reception of a beacon, and then, starts transmitting its data packets using a slotted carrier sense multiple access with collision avoidance (CSMA/CA) algorithm. Conversely, in the NBE mode
• D. De Guglielmo and G. Anastasi are with the Department of Infor- mation Engineering, University of Pisa, Italy (email: {d.deguglielmo, g.anastasi}@iet.unipi.it).
• F. Restuccia and S.K. Das are with the Department of Computer Science, Missouri University of Science and Technology, Rolla, MO, United States (e-mail: {frthf, sdas}@mst.edu).
• M. Conti is with the Institute of Informatics and Telematics (IIT), National Research Council, Pisa, Italy (e-mail: marco.conti@iit.cnr.it).
there is no superframe; nodes are not synchronized, and use an unslotted CSMA/CA algorithm for packet transmissions.
The performance of 802.15.4 WSNs has been thor- oughly investigated in the past [6]-[21]. However, most of the previous studies have focused on the BE mode and, hence, they have considered the slotted CSMA/CA algorithm. Although the NBE mode is the most suit- able access method for applications generating sporadic and/or irregular traffic (e.g. event-driven WSN applica- tions and upcoming IoT applications), significantly less attention has been devoted to it.
The most challenging aspect in analyzing the 802.15.4 unslotted CSMA/CA algorithm lies in its remarkable complexity, mainly due to its random nature and the multitude of parameters regulating its behavior. Nev- ertheless, having an accurate (yet tractable) model is imperative to investigate the QoS that can be provided to applications. The majority of previous models of unslot- ted CSMA/CA algorithm assume that packets are gen- erated according to a specific stochastic distribution (e.g. Poisson). However, this assumption is not valid for WSN applications where nodes generate traffic according to an event-driven pattern (e.g. query-based applications, neighbor discovery, data aggregation). Although some works [16], [18] have proposed analytical models of the unslotted CSMA/CA algorithm for event-driven WSNs, literature still lacks models that are both accurate and tractable. For this reason, in this paper we present a new model of unslotted CSMA/CA, for event-driven WSNs, that is both accurate and tractable. We use it to derive performance metrics of interest such as delivery ratio,
delay, and energy consumption. In order to deal with the significant complexity of the algorithm, we use an approach called Event Chains Computation (ECC).
ECC relies on the idea that outcomes of the CSMA/CA algorithm can be represented as a sequence (chain) of transmissions (events) that subsequently occur in the network. ECC is able to iteratively build all the possible sequences of events that can be experienced by sensor nodes while transmitting a data packet. However, to re- duce complexity, only the event chains whose probability to occur is above a predefined threshold are considered. By appropriate selection of the threshold, it is possible to reduce the model complexity and, hence, the compu- tational resources needed to calculate the performance metrics, with a limited loss of accuracy. In addition, it is possible to parallelize the algorithm, which further reduces the computation time.
To summarize, this paper makes the following contri- butions.
• We introduce the ECC modeling approach that lever- ages both the analysis of the most likely events and parallel computation, to reduce drastically the model computation time.
• We use ECC to derive performance metrics of in- terest such as delay, energy consumption, and packet delivery probability.
• We validate our model through simulation and ex- periments in a real testbed. Also, we analyze the perfor- mance of the unslotted 802.5.4 CSMA/CA algorithm as a function of different operating parameters. Our results demonstrate that the ECC approach allows to reduce drastically the computation time, while guaranteeing a good accuracy for the computed performance metrics.
The paper is organized as follows. Section 2 presents related work. Section 3 describes the unslotted 802.15.4 CSMA/CA algorithm. Section 4 presents the model as- sumptions. Section 5 and 6 detail the ECC algorithm and derive performance metrics. Section 7 presents the obtained results. Finally, Section 8 draws conclusions.
2 RELATED WORK
The 802.15.4 MAC protocol has been thoroughly in- vestigated through analysis [6]-[18], simulations [19], [20] and real experiments [20], [21]. However, most of these studies have focused on the BE mode (i.e., slotted CSMA/CA), while significantly less attention has been devoted to the NBE mode. In this paper, we focus on the latter mode and, hence, on the unslotted CSMA/CA, hereafter referred to as CSMA/CA for brevity.
One of the first models for CSMA/CA was due to Goyal et al. [15], who proposed a stochastic model as- suming that packet inter-arrival times follow an expo- nential distribution, and considering the effect of packet retransmissions. More recently, Di Marco et al. [13] ana- lyzed the CSMA/CA algorithm in single and multi-hop scenarios, through an accurate model based on Discrete
Time Markov Chains (DTMCs). In [14] the authors im- proved the work in [13] by proposing an extended model considering the effect of a fading channel.
In [13]-[15] it is assumed that sensor nodes generate data packets according to a Poisson distribution. How- ever, this assumption does not apply to a large number of WSN scenarios where sensor nodes typically follow an event-driven reporting paradigm [11]. In this paper, we consider event-driven applications and assume that, when an event is detected, all (or a large number of) sen- sor nodes in the network start reporting data simultane- ously (the event-driven paradigm can be easily extended to model periodic traffic as well). A similar scenario is considered in [11] where the authors provide an accurate model of the 802.15.4 CSMA/CA (that considers both the case with and without retransmissions) and validate it through extensive simulations. We point out that, differ- ently from this paper, [11] focuses on the slotted version of 802.15.4 CSMA/CA and this completely changes the analytical model. In addition, no real experiments are provided to validate the model.
Regarding event-driven WSNs and the unslotted CSMA/CA, the closest to our work are [16]-[18]. In [16] the authors derive the packet latency and delivery ratio experienced by N sensor nodes that attempt to transmit a single packet simultaneously to the sink node. The work was further extended in [17] by taking into account the hidden node problem using the theory of stochastic geometry. However, conversely from us, both [16] and [17] do not consider the effects of acknowledge- ments and retransmissions. In [18], Gribaudo et al. pro- vide a very accurate and complete analytical model of CSMA/CA using stochastic automata networks (SANs) [22]. The analysis is mainly aimed at deriving the packet delay distribution and on-time delivery ratio (percentage of packets received by the sink node within a pre- defined threshold). As in [16] and [17], the analysis of the energy consumption of sensor nodes is neglected. Fur- thermore, although the use of SANs makes the analysis very accurate, it also raises serious complexity issues. In fact, the analysis in [18] is limited to WSNs with a low number of nodes (i.e. less than 6). This is because the size of the WSN global descriptor (i.e., a matrix) increases exponentially with the network size. Hence, the computation time and memory needed to solve the model increases accordingly.
Likewise the model proposed in [18], our analysis is very accurate. It considers acknowledgements and re- transmissions, and no over-simplifying assumptions are made on the CSMA/CA algorithm. In terms of perfor- mance metrics, we derive delivery ratio, packet latency, and energy consumption of sensor nodes. However, our most important contribution is to provide an accurate analytical model of CSMA/CA which is able to analyze WSNs with a large number of nodes. This is because we do not use a matrix-based analytical model (like DTMCs or SaNs). Instead we undertake an approach called Event Chains Computation (ECC), that makes the analysis very
2
accurate yet computationally tractable. As we will show in Section 6, ECC is scalable and, unlike previous tech- niques, is particularly suitable for parallelization, due to its intrinsic concurrent structure. This contributes to drastic reduction of computation time. To the best of our knowledge, ours is the first accurate analytical model of the (unslotted) CSMA/CA algorithm for event-driven scenarios investigating the performance of WSNs with a large number of sensor nodes. In addition, we present a comparison of analytical and experimental results.
3 CSMA/CA ALGORITHM
According to the IEEE 802.15.4 standard, in WSNs oper- ating in the NBE mode, sensor nodes must associate with a coordinator node and send their packets to it, using the (unslotted) CSMA/CA algorithm. Unlike regular sensor nodes, coordinator nodes are energy-unconstrained de- vices that form a higher-level network aimed at forward- ing data to the final destination. Specifically, coordinator nodes are always on and, thus, sensor nodes are allowed to start a packet transmission at any time. In addition, no synchronization is required. Below, we provide a short description of the CSMA/CA algorithm used by sensor nodes to transmit data to their coordinator node.
Upon receiving a data packet, the MAC layer at the sensor node performs the following steps.
1) A set of state variables is initialized, namely the number of backoff stages carried out for the on- going transmission (NB = 0) and the backoff expo- nent (BE = macMinBE).
2) A random backoff time is generated and used to initialize a timer. The backoff time is obtained by multiplying an integer number uniformly dis- tributed in [0, 2BE−1] by the the duration of the backoff-period (Dbp). As soon as the timer expires the algorithm moves to step 3.
3) A Clear Channel Assessment (CCA) is performed to check the state of the wireless medium.
a) If the medium is free, the packet is immedi- ately transmitted.
b) If the medium is busy, state variables are updated as follows: NB = NB+1 and BE = min(BE+1,macMaxBE). If the number of back- off stages has exceeded the maximum allowed value (i.e. NB > macMaxCSMABackoffs), the packet is dropped. Otherwise, the algorithm falls back to step 2.
The CSMA/CA algorithm supports an optional re- transmission scheme based on acknowledgements and timeouts. When the retransmissions are enabled, the destination node must send an acknowledgement upon receiving a correct data packet. On the sender side, if the acknowledgment is not (correctly) received within a pre-defined timeout, the packet is retransmitted, un- less the maximum number of allowed retransmissions (macMaxFrameRetries) has been reached. Otherwise, the packet is dropped.
4 MODEL ASSUMPTIONS
In the following, we focus on the communication be- tween sensor nodes and the coordinator node they are associated with. We assume that there are N nodes associated with the considered coordinator node. We refer to event-driven applications in which all sensor nodes start transmitting a data packet simultaneously to their coordinator, to report a detected physical event. This is one of the most challenging scenarios in terms of performance and energy consumption. We assume that each sensor node is in the carrier sensing range of each other and there are no obstacles in the sensing field. This assures that the hidden node problem never arises. In addition, we assume that the time between two consecutive physical events ph1 and ph2 is long enough to assure that the execution of the CSMA/CA algorithm, started by sensor nodes to report ph1, is surely terminated before ph2 occurs. Hence, in the following, we focus on a single physical event ph. We indicate as t = 0 the time at which ph occurs and, hence, the time at which all the N nodes start executing the CSMA/CA algorithm. Finally, we make the following assumptions:
5
• Each sensor node transmits a single packet to report the detected event ph.
• Data packets transmitted by different sensor nodes have the same size. In particular, we assume that the packet size is such that the corresponding trans- mission time can assume a value Dtx such that Dtx =Dmax−k·Dbp, fork≥0,whereDmax isthe time required to transmit a maximum-size packet (133 bytes) and Dbp is the duration of the backoff period.
• The communication channel is ideal, i.e.,
data/acknowledgement packets are never corrupted, or lost, due to transmission errors.
EVENT CHAINS COMPUTATION
The CSMA/CA algorithm is a random access algorithm whose goal is to minimize the probability of collision between packets transmitted by different sensor nodes. Due to its random nature, different executions of the algorithm can yield completely different outcomes. For instance, if we consider N nodes simultaneously trans- mitting a single data packet to their coordinator node, a run of the algorithm can result in a transmission schedule such that all the N data packets are success- fully transmitted to the coordinator (and, hence, 100% reliability is achieved) while another run can result in no successful transmissions at all (e.g. due to repeated collisions). Obviously, different outcomes have, in gen- eral, different probabilities to occur.
The ECC algorithm is able to generate all the possible outcomes an execution of CSMA/CA algorithm can yield, and the corresponding probabilities. However, to reduce the complexity of the analysis, it is possible to instruct the ECC algorithm to generate only the outcomes having a probability to occur greater than or equal to a certain
3
threshold θ (0 ≤ θ < 1). The set of possible outcomes produced by the algorithm is then used to calculate the performance metrics of interest such as delivery ratio, latency and energy consumption.
o3
o5
e6 P(o1) = P( e1 ^ e4 ^ P(o2) = P( e2 ^ e5 ^
4
)
e1
e2
e3 e4
o1
e5
) P(o3)=P(e1 e3 )
e7 ^^
o4 ^^^ P(o4)=P(e1 e3 e7 )
P(o5) = P( e1 ^ e3 ^ e6^
)
e1 e2
CC CC AA
0 t1 f1 t2 ox
ph occurs and nodes start the CSMA/CA algorithm
o2
Tx
Tx
Ack
Fig. 2: Possible outcomes of the CSMA/CA.
f2
t
Figure 2 represents a case where a CSMA/CA ex- ecution can produce five possible outcomes, namely o1, o2, o3, o4, o5. Initially (i.e. just after time t = 0), two possible events can occur, namely e1 and e2. The ECC algorithm calculates that, with probability P{e1}, e1 is the first event to occur in the network while, with probability P{e2}, e2 occurs. Then, the algorithm checks if there are cases in which no other events occur in the network after e1 or e2 have occurred, i.e. if there are outcomes of the algorithm composed only of event e1 or e2. To this end, both P{no txs | e1} and P{no txs | e2} are calculated. Since in this example there are no outcomes terminating with e1 or e2 , both P{no txs | e1 } and P{no txs | e2} are equal to 0.
ECC then derives the events that can occur after e1 or e2. It discovers that, with probability P{e3 | e1}, e3 will follow e1, while with probability P{e4 | e1}, e4 will follow e1. Also, event e5 is the only event that can occur in the netwok after e2, i.e. P{e5 | e2} = 1. As before, ECC checks if there are cases in which no other events occur in the network after e3, e4 or e5 by computing P{no txs | e1 ∧ e3}, P{no txs | e1 ∧ e4}, P{no txs | e2 ∧ e5}. It discovers that both P{no txs | e1 ∧e4} and P{no txs | e2 ∧e5} are equal to 1, since no events can occur after e4 and e5, while 0 < P{no txs | e1 ∧e3} < 1, i.e. there are cases in which no other events occur in the network after e1 and e3. Thus, the algorithm stores three different outcomes namely o1 , o2 , o3 and the corresponding probabilities P{o1 }, P{o2 }, P{o3 } given by eq. 3.
Since P{no txs | e1 ∧ e3} is less than 1, there are also cases in which other events may occur in the network after e1 and e3. Specifically, e6 occurs with probability P{e6 | e1 ∧e3} while e7 occurs with probability P{e7 | e1 ∧ e3}. Also, since no other events can occur after e6 and e7 both P{no txs | e1 ∧e3 ∧e6} and P{no txs | e1 ∧e3 ∧e7} are equal to 1. Hence, the algorithm stores outcomes o4 and o5 with P{o4 } and P{o5 } calculated according to eq. 3. Then, it terminates.
As mentioned above, to reduce the complexity of the analysis, the ECC algorithm can generate only outcomes with probability greater than, or equal to, a certain threshold θ (0 ≤ θ < 1). In this case, the algorithm stops to analyze a certain sequence of events as soon as it discovers that its probability to occur is lower than θ. For instance, let us assume that P{e1} = 0.95 while P{e2} = 0.05. In case θ = 0.1, the algorithm analyzes only the sequences composed of events highlighted in red in figure 2, i.e. the outcomes starting with event e1. This is because, since P{e2} = 0.05, all the outcomes starting with event e2 will have a probability to occur lower than or equal to 0.05 < θ.
Fig. 1: ox, a possible outcome of the CSMA/CA.
The ECC algorithm is based on the observation that an outcome of the CSMA/CA execution can always be represented as a series (chain) of successful/failure trans- missions (events) occurring subsequently in the network. Figure 1 shows a possible outcome ox of the CSMA/CA algorithm representing the case when a transmission fail- ure (time t = t1) followed by a successful transmission (time t = t2) occur. Please note that time t = 0 is the time at which all the nodes start the CSMA/CA execution and that, in this specific example, no more transmissions
occur in the network after those shown in the figure. Let us indicate as e1 and e2, respectively, the transmis- sion failure and the successful transmission depicted in
Figure 1. Then, the probability of outcome ox is:
P{ox}=P{e1 ∧e2 ∧no txs} (1) where no txs indicates that no more events (success-
ful/failure transmissions) occur in the network after e2. By recursively applying the Bayes’ theorem, eq. 1 can
be rewritten as:
P{ox} = P{e1 ∧ e2 ∧ no txs}
=P{e1 ∧e2}P{no txs | e1 ∧e2} (2)
= P{e1}P{e2 | e1}P{no txs | e1 ∧ e2}
More generally, the probability of an outcome oi, rep-
no more transmissions occur
resenting the series of events e1 , e2 , ..., en , can calculated as follows:
P{oi}=P{e1 ∧e2 ∧...∧en ∧no txs}
=P{e1 ∧ ...∧en}P{no txs | e1 ∧...∧en} = P{e1}P{e2 | e1}P{e3 | e1 ∧ e2} · ...
be
(3)
· P{no txs | e1 ∧...∧en}
Eq. 3 suggests that, in order to calculate the probability of outcome oi , n + 1 different steps have to be performed. First, P{e1} has to be computed, i.e. the probability that e1 is the first event occurring in the network. Then, at each subsequent step k, 2 ≤ k ≤ n, the probability P{ek | e1∧...∧ek−1} that event ek occurs, given that all the previous k − 1 events have occurred, has to be derived. Finally, P{no txs | e1∧...∧en} has to be calculated, i.e. the probability that no other events will occur in the network after en. The ECC algorithm follows exactly these n + 1 steps to compute the probability of an outcome.
Now, by means of a simple example, we give an overview of the actions performed by ECC to generate all the possible outcomes of a CSMA/CA execution and the corresponding probabilities.
Dcca Dtat Dtx Dtat Dack
Dcca Dtat
Dtx Ddiff
tion, and the related probability, ECC follows an iterative
approach summarized in Figure 4. Initially, ECC creates
two empty sets, namely Lc and Fc. At a given point
in time, Lc contains the chains still to be analyzed by
the algorithm, while Fc contains chains representing
possible outcomes of the CSMA/CA execution. ECC
starts analyzing the network at time t = 0 and derives
all the possible events ei that can occur just after t = 0.
For each such event ei, the chain c : sc = {ei} is added
to set Lc, iff pc = P{ei} ≥ θ. Then, the ECC algorithm
enters a loop that ends when there are no more chains
to be analyzed, i.e., Lc = {∅}. At each iteration, a chain
c : sc = {e1, e2,..., em} is extracted from set Lc to
be analyzed. First, the algorithm checks if c can be a
possible outcome of the CSMA/CA execution, i.e. if
P{no txs | c} > 0. If so, the following operations are
performed. First, a copy cx of chain c is created. Second,
since no more events have to occur in the network to
consider cx an outcome, the probability of chain cx is
updated as pcx = pc · P{no txs | c}. Finally, if pcx ≥ θ, the
average energy en spent by the nodes in the network ea eb cx
The steps performed by the ECC algorithm are re- ported by the flowchart in Figure 4. Before describing it we define the concept of event and chain of events.
Definition 1. An event ei = {Ti, ti} represents a transmis- sion occurring in the network, where Ti indicates the type of the event and ti denotes its starting time. The event type can be either a success (Ti = S) or a failure (Ti = F ). A success occurs whenever a node successfully transmits its packet, while a failure happens when two or more nodes transmit their packets simultaneously and, therefore, a collision occurs. The starting time ti of an event ei is defined as the time instant at which the node(s) causing ei start their CCA. Each event ei is also associated with a finish time fi, defined as the first time instant, following ei, at which a new event can occur, i.e. as the time t∗ > ti such that a (new) successful CCA can be performed.
5
CC CC AA
0 ta
Tx
Ack
Tx
fa t0 tb
fb t
Fig. 3: Events ea and eb.
Figure 3 depicts two possible events, i.e., a successful
transmission ea and a transmission failure eb (time is divided in slots of duration equal to the backoff period, Dbp). In Figure 3, Dcca is the duration of CCA, Dtat is the turnaround time (i.e., the time needed to switch the radio from receive to transmission mode, or vice versa), Dack is the time to transmit/receive an acknowledgement and Ddiff = Dbp−(Dtx mod Dbp) is the time between the end of a packet transmission and the beginning of the next slot. In this example, the starting time of event ea is 0, while the starting time of event eb is tb = 2 · Dbp . Hence, we can refer to ea as {S, 0} and to eb as {F, 2Dbp}.
Definition 2. A chain of events c = {sc, pc, enc} represents a sequence of events that occur subsequently in the network. It is characterized by:
• the event sequence sc = {e1 , …, em }, where m denotes the total number of events occurred;
• the aggregate probability pc = P{e1 ∧ e2 … ∧ em} = P{e1}P{e2 | e1} … P{em | e1 ∧ e2 … ∧ em−1} that the event sequence sc occurs;
• the average total energy enc spent by all the nodes in the
network during the time interval [0, fm], where fm is
the finish time of the last event in sequence s . c
Please note that a chain c : sc = {e1, …, em}
sents a possible outcome of the CSMA/CA execution iff P{no txs | e1 ∧…∧em}>0.
Hereafter, for brevity, we indicate as P{ex | c} = P{ex | e1 ∧ … ∧ em} the probability that event ex oc- curs in the network, given that the sequence of events sc = {e1 , …, em } has occurred. Also, we denote by P{no txs | c} = P{no txs | e1 ∧ … ∧ em} the probability that no other events will occur in the network after the sequence represented by chain c.
when the events reported by cx occur is calculated and cx is added to Fc since it represents an outcome of the CSMA/CA execution with a probability to occur ≥ θ.
If P{no txs | c} ̸= 1, it means that other events can START
Lc ={∅},Fc ={∅}
Initialization of Lc with the initial chains
is
Lc = {∅}
? YES
NO
Extract event chain
c: sc ={e1, e2, …, em} from Lc
P{no txs | c}
> 0? YES
NO
P{no txs | c} ̸= 1?
YES
Derivation of performance metrics using set Fc
END
1) cx = c.
2) pcx =pc ·P{no txs | c}. 3) If pcx ≥ θ, calculate encx and add cx to Fc since
it represents an outcome
repre-
NO
Derive all the possible events ex that can occur after c, and their probability P{ex | c}. For each ex, add cx : scx ={e1, e2, …, em, ex} to Lc iff pcx ≥θ.
To derive all the outcomes of the CSMA/CA execu-
Fig. 4: Steps performed by the ECC algorithm.
occur in the network after those in c. In this case, the algorithm derives all the events ex (and their probabil- ity P{ex |c}) that can occur after the last event em in chain c. For each such event ex, the chain cx : scx = {e1, e2,…, em, ex} is added to set Lc, provided that the corresponding probability pcx = P{ex |c} · pc is greater than, or equal to, θ. When the set Lc becomes empty it means that ECC has generated all the possible outcomes having a probability to occur greater than, or equal to, θ. Hence, the ECC algorithm proceeds with deriving the performance metrics of interest, using the chains in set Fc. Then, it terminates its execution.
6 MODEL DERIVATION
Now we detail each single step of the ECC algorithm. After a preliminary analysis in section 6.1, in Section 6.2 we focus on the ECC initialization phase and derive all the possible events that can occur in the network just after time t = 0 and the corresponding probabilities. In Section 6.3, we focus on the actions performed by ECC inside the loop (chains examination phase). Finally, in Section 6.4 we show how to parallelize ECC while in Section 6.5 we derive performance metrics of interest.
6.1 Preliminaries
Before proceedings into the details of the ECC algorithm, we derive a general formula for the probability that a sensor node performs a CCA (Clear Channel Assess- ment) at a given time t. To this end, we first derive the possible time instants at which a sensor node could start a CCA. Next, we compute the probability that it actually performs a CCA in one of these time instants.
As a preliminary step, we need to consider all the
actions that may lead a node to start a CCA at a given
time t. Let Bmax = macMaxCSMABackoffs + 1 denote the
maximum number of consecutive CCAs allowed for each
transmission attempt, and Tmax = macMaxFrameRetries+
1 be the maximum number of transmission attempts
allowed per data packet. In addition, let us indicate by
W,1≤i≤B ,thebackoffwindowsizeatthei-th i max
backoff stage. For simplicity, hereafter we will use the expression ”the sensor node is in state Bij” to indicate that a sensor node is performing a CCA during the i-th backoff stage of the j-th transmission attempt. Now we
derive the set Λ
sensor node could start a CCA while in state B .
Λ11 = {0,Dbp,··· ,(W1 − 1) · Dbp}. Then, a sensor node can start a CCA after one of the two following events: (i) a previous CCA during which the channel was found busy (see Figure 5a), or (ii) an unsuccessful transmission attempt (see Figure 5b). In case (i), the sets Λij , 2 ≤ i ≤ Bmax , 1 ≤ j ≤ Tmax , can be recursively derived from Λi−1j as follows:
ij
Rand Backoff w in [0, Wi-1]
Dcca Dtat
of all the possible instants at which a
{t∈Λ′ ,1≤i≤B | ij−1 max
Dcca Dtat Dtx
Dto
ij
Rand Backoff w in [0, W1-1]
∃w∈[0,W −1]:t=t +D +w·D }, 1rtxbp
t Ωij =
Λij ={t | ∃w ∈ [0, Wi − 1] ∧ ∃t∗ ∈ Λi−1j ∧t=t∗+D +D +w·D } (4)
cca tat bp
Equation 4 derives CCA instants in set Λij by con- sidering all the CCA instants t∗ ∈ Λi−1j and all the possible random backoff values w ∈ [0, Wi − 1] a node can generate when it is in the i-th backoff stage and has
found the channel busy.
In case (ii) the sensor node performs a CCA due to a
previous unsuccessful transmission attempt and, hence, it is in one of the states B1j,2 ≤ j ≤ Tmax. Let us denote by Drtx Dcca + Dtat + Dtx + Dto the total time needed to perform a CCA (Dcca), turn the radio in TX mode (Dtat ), transmit a data packet (Dtx ), and wait for the timeout (Dto ). We indicate as Rij −1 the set of instants at which a node could perform a CCA after an unsuccessful transmission started at any t∗ ∈ Λij−1,1 ≤ i ≤ Bmax. It can be expressed as follows.
Rij−1 ={t | ∃w ∈ [0, W1 − 1] ∧ ∃t∗ ∈ Λij−1
∧t=t∗ +Drtx +w·Dbp}
Equation 5 calculates Rij−1 considering all time instants t∗ ∈ Λij −1 and all possible backoff values w ∈ [0, W1 − 1] the node can generate at the first backoff stage. Since a retransmission can occur during every backoff stage, the set Λ1j,2 ≤ j ≤ Tmax, is computed as the union of all
the sets Rij −1 , i.e., Λ1j = Bmax Rij −1 . i=1
Let Ωtij denote the set of all time instants t∗ at which a node can perform a CCA before performing a CCA at time t during state Bij. The following claim holds.
Claim 1. The set Ωtij can be derived as
{∅}, ifi=1,j=1
∗
if 2≤i≤Bmax, 1≤j ≤Tmax ∗′
{t∈Λ |∃w∈[0,W−1]∧ i−1j i
∗
∗
ifi=1, 2≤j≤T max
t=t+D +D +w·D}, cca tat bp
(5)
6
CCCC C C C Tx C AAAA
(6)
t*
CCA at stage i-1
t*
Proof: The set Ωt11 is empty since no CCA can be performed before those occurring at time instants in set Λ11. If 2 ≤ i ≤ Bmax, it means that the node performs a CCA at time t due to a previous failed CCA. In this case, all the CCA instants t∗ ∈ Λi−1j that can result in a CCA at t are selected (second term of Equation 6). In the last case, a CCA at time t is due to a previous unsuccessful transmission. Therefore, the set Ωt1j , 2 ≤ j ≤ Tmax , is
CCA at stage i (a)
CCA of transmission attempt j-1 (b)
CCA of transmission attempt j
Fig. 5: CCA due to a failed CCA (a) and a failed transmission (b). According to the CSMA/CA algorithm, at t = 0, each sensor node waits for a random number w ∈ [0, W1 − 1] of backoff periods and, then, it performs a CCA. Hence,
composed by all the t∗ ∈ Λi′j−1,1 ≤ i′ ≤ Bmax, which could cause the node to perform a CCA at t due to an unsuccessful transmission (third term of Equation 6).
Let us now derive the probability P{CCAt} that a
sensor node performs a CCA at time t. To this end, we
calculate the probability P{CCAtij } that a node performs
a CCA at time t while in state Bij and, then, we compute
P{CCAt } based on P{CCAt }. Let us denote by P{CBt } ij
the probability to find the channel busy during a CCA started at time t, and by P{Ft} the probability that a transmission whose CCA started at time t fails. The following claims hold.
Claim 2. The probability P{CCAtij} that a sensor node performs a CCA at t while in state Bij is
P{CCAtij} =
A successful transmission occurs at time i · Dbp (i = 0, .., W1 − 1) when one node generates a backoff time equal to i · Dbp, and all the other N − 1 nodes extract a backoff time larger than i · Dbp. Therefore,
1 W1−i−1N−1 P{esi}=N·W · W (9)
11
In Equation (9), the term 1/W1 is the probability that one
node picks up a backoff time equal to i · Dbp, while the third term gives the probability that all the remaining N − 1 nodes generate a backoff time larger than i · Dbp. Conversely, a failure occurs at time i · Dbp when two or more nodes generate the same backoff time i · Dbp and, thus, experience a collision. Hence,
7
0 ift̸∈Λij
1
N k N 1
N − k
(10)
, ifi=1,j=1 W1
P{e }= fi
·
B ∗ max t
t∗ ∈Ωt ij
i′ =1 P{CCAi′ j −1 }·
t∗ t∗ 1
·(1−P{CB })·P{F }· , W1
W1 − i − 1 kWW
t∗ t∗1 t∗∈Ωt P{CCAi−1j}·P{CB }·Wi,
The sum in Equation (10) takes into account that more
than two nodes may collide. The term inside the sum
gives the probability that exactly k nodes randomly pick
up a backoff time of i·D , while N −k nodes choose a bp
backoff value larger than i · Dbp.
Using Equations (9) and (10), ECC initializes Lc by
addingchainsc:s ={e }(s ={e })andp =P{e } c si c fi c si
(pc = P{efi}). Note that a chain is added to Lc iff pc ≥ θ. Then, ECC enters the chains examination phase.
6.3 Chains examination
k=2 1 1
ij
if 2≤i≤Bmax,1≤j ≤Tmax
if i=1, 2≤j ≤Tmax Proof: See Appendix A.
(7)
Claim 3. The probability that a sensor node performs a CCA at a certain time t can be calculated as:
Bmax Tmax P{CCAt}=P{CCAt} (8)
i=1 j=1
In the chains examination phase, ECC executes a loop during which, at each step, a chain c ∈ L with s :
Proof: P{CCAt} is equal to the probability that a sensor node performs a CCA at time t in any state Bij . Therefore, Equation 8 calculates P{CCAt } as the sum of P{CCAtij},1 ≤ i ≤ Bmax,1 ≤ j ≤ Tmax. Since events ”performing a CCA at time t while in state Bab” and ”performing a CCA at time t while in state Bcd”, a ̸= c | b ̸= d, are always mutually exclusive, it is possible to sum probabilities P{CCAtij}.
6.2 ECC Initialization
As shown in Figure 4, the first step of the ECC algorithm consists in initializing the set Lc with chains derived from events occurring immediately after t = 0. In this section, we will refer to esi (efi ) as the success (failure) event starting at time i · Dbp, i ∈ N. Also, we denote by P{esi } (P{efi }) the probability that event esi (efi ) occurs.
According to the CSMA/CA algorithm, at t = 0 each sensor node waits for a random number w ∈ [0, W1 − 1] of backoff periods and, then, it performs a CCA. There- fore, the first event occurring in the network can be either a success or a failure with starting time in the set {0, Dbp, 2Dbp,…, (W1 −1)·Dbp}.
P{esi | c}(pc · P{efi | c}) ≥ θ.
In the following we will show the computation of both
P{no txs | c} and P{esi | c} (P{efi | c}). However, before deriving them, we perform two preliminary steps. First, we derive P{C C At | c}, i.e. the probability that a node, that has not experienced a success until fm, will perform (has performed) a CCA at a certain time t ≥ fm (t < fm), given that the events in c occurred. Second, we compute the exact number of nodes that are still active in the network at time t = fm (i.e. that have not yet terminated the CSMA/CA execution).
ij
cc {e1 , ..., em } is examined. The goal of the examination is twofold. First, the algorithm checks if c represents a possible outcome of the CSMA/CA execution by com- puting P{no txs | c} and, if so (i.e. P{no txs | c} > 0), itaddsctoFc.IfP{no txs|c}̸=1itmeansthatnew events may occur after c. Hence, as a second step, all the events that may occur after em (i.e. after the last event in c) are derived. Hereafter, for simplicity, we will indicate as esi (efi ) a success (failure) event occurring attimeti=fm+i·Dbp,i∈N,wherefmisthe finish time of event em and as P{esi | c} (P{efi | c}) its corresponding probability. For any esi (efi ) a new chain cx : scx = {e1, …, em, esi} (scx = {e1, …, em, efi}) is added to Lc by the ECC algorithm iff pcx = pc ·
Derivation of P{CCAt | c}
Hereafter, we take into consideration a generic chain
c: s ={e, …, e }anddenotebyN thenumber c1m s
of successful transmissions occurred in chain c (Ns =
|{ei ∈ sc : Ti = S}|). Since each sensor node has to trans-
mit just one data packet, at most N = N −N nodes may rs
be still active in the network after time fm. Our goal is to derive the probability P{C C At | c} that any of the Nr nodes will perform (has performed) a CCA at time t, given that the sequence of events in c occurred.
First of all, we denote by NPij , 1 ≤ i ≤ Bmax, 1 ≤ j ≤ Tmax, the set of all time instants t < fm at which it is not possible, for any of the Nr sensor nodes, to have performed a CCA while in state Bij, if the events in c occurred. The derivation of NPij is shown in Appendix B, due to the sake of space.
Second, we derive, for time instants t < fm 1 , the probability P{CBt | c} for any of the Nr to have found the channel busy during a CCA started at time t. We also derive P{F t | c}, i.e. the probability for any of the same nodes to have experienced a failure for a transmission whose CCA started at time t. Equations 11 and 12 hold.
em
DccaDtat
Backoff w=(WBmax-1) Dbp
8
Tx
Ack
CCC CCC AAA
fm chainc Backoff w=(WBmax-1)Dbp
Dcca Dtat
fm-Dbp fm Smax NodeA
CCA at stage Bmax-1 CCA at stage Bmax
em Backoff w= (W1-1) Dbp Dto
CCCC C C CTx C AAAA
fm-D
bp fm
CCA at stage Bmax-1 (a)Tm=S
NodeA
tm
fm fm+2Dbp
(b)Tm=F
NodeB
Smax
1 if ∃e ∈ s : t ∈ [t + D , f ) P{CBt|c}= i c i bp i (11)
1 , |Λ11\N 11|
(12) nel busy during a CCA started at time t only depends on
CCA at stage Bmax
Fig. 6: Derivation of Smax
which has experienced the collision represented by em, waits for the retransmission timeout Dto and extracts a backoff time equal to (W1 − 1) · Dbp. Hence, we need to consider the largest value for Smax in the two cases, i.e. Smax =fm +max((WBmax −1), 2+(W1 −1))·Dbp.
Now, we can show the computation of P{CCAt | c} for time instants t ∈ [0, Smax]. The following claim holds.
Claim 5. The probability P{CCAtij | c} that any of the Nr nodes has performed a CCA at time t ∈ [0, fm] or will perform a CCA at a time t ∈ [fm, Smax], while in state Bij, provided that all the events in chain c have occurred, is
0
if t̸∈Λij ∨t∈NP if i = 1, j = 1
ij
0 otherwise
1 if∃e∈s:t=t∧T=F
P
i c i i
∗ ∗ tt1
P{Ft |c}=
The probability that a generic node has found the chan-
t∗∈(Ωtij\NPi−1j)P{CCAi−1j |c}·P{CB |c}·|ht∗|, ij
0 otherwise
if 1
Claim 4. Smax = fm + Mw · Dbp, where
Proof: If Tm = S, Smax is derived by considering the worst case shown in fig. 6a where a node (node A) performs a CCA at time t = fm − Dbp during its (Bmax − 1)-th backoff stage, finds the channel busy, and extracts a value for the backoff time equal to (WBmax − 1) · Dbp. Hence, Smax is given by fm + (WBmax − 1) · Dbp. Conversely, if Tm = F, two cases must be considered. A node (node A in fig. 6b) may perform a CCA at time t = fm − Dbp during the (Bmax − 1)-th backoff stage, and extract a backoff time value equal to (WBmax − 1) · Dbp. At the same time, another node (node B in fig. 6b),
1. We assume that both P{CBt | c} and P{Ft | c} are equal to 0 ∀t ≥ fm. This allows to calculate the probability that a node will directly perform a CCA at a time t ≥ fm.
Pi j−1 ·P{Ft |c}· 1∗ ,
the specific events in chain c. Specifically, P{CB
if a success or failure event has occurred at time t, and zero otherwise. Similarly, P{Ft | c} = 1 if a failure occurred at time ti = t, and zero otherwise.
| c} = 1
|ht | 1j
Bmax ′
∗ ∗
t
) P{CCAi′j−1 | c} · (1 − P{CB
t
(15)
i =1
t∗∈(Ωt \N
ij ′
∗
| c})·
(14)
Mw =
Tm = S max{WBmax −1, 2+(W1 −1)} Tm =F
WBmax − 1
i=1 j=1
Estimating the number of active nodes at time t = fm
Since Ns nodes experienced a success during the chain c, at most Nr = N − Ns nodes can be potentially active attimet=fm.EachoftheseNrnodescanbeinone of the following states at time t = fm: (i) the node has reached the maximum number Bmax of consecutive CCAs for a data packet transmission; or (ii) the node has reached the maximum number Tmax of retransmissions for a data packet; (iii) the node is really active, i.e. it has not yet finished the CSMA/CA execution. Indeed, in the first two cases the sensor node drops its data packet, according to the CSMA/CA algorithm and, thus, it is no longer active at time t = fm. To derive the number of sensor nodes that are really active at time t = fm, we need to calculate the probability, for each of the Nr nodes, to be in state (i), (ii) or (iii), respectively. The following claims hold.
Claim 6. Let P{FCCA | c} denote the probability that any of the Nr sensor nodes has exceeded the maximum number
(13)
if i=1, 2≤j≤Tmax Proof: See Appendix C.
Finally, we can derive P{CCAt | c} as follows
Bmax Tmax
P{CCAt | c} = P{CCAtij | c}
Bmax of consecutive CCAs allowed for the transmission of a data packet before time t = fm. It is
fm−Dbp Tmax
P{FCCA | c} = P{CCAtBmaxj | c}·P{CBt | c}
probability that exactly Nnp nodes are still active in the network, and the probability that Nd nodes are no more active, respectively. Obviously, all possible combinations are taken into consideration.
The calculation of N for the case Tm = F follows the same line of reasoning and is shown in Appendix H.
Claim 10. The probability P{no txs | c} that no other events occur in the network after em is:
P{no txs | c}=P{N =[0, 0, Nr] | c} (21) Proof: The probability P{no txs | c} that no events
Claim 7. Let P{FRtx | c} denote the probability that any of the Nr sensor nodes has exceeded the number of retransmis- sions allowed for a data packet before time t = fm. It is
9
t=0 j=1
Proof: See Appendix D.
(16)
fm−Dbp Bmax ttm
P{FRtx | c} = P{CCAiTmax | c} · P{F | c}
occur after e , is equal to the probability that all nodes have finished their CSMA/CA execution before fm, i.e. P{N =[0, 0, Nr] | c}.
(17)
t=0 i=1
Proof: See Appendix E.
Derivation of new events after em
When P{no txs | c} ≠ 1, it means that there are cases when at least one node is still active at time fm and, hence, other events may occur in the network. We con- sider all the events that may occur after em and calculate the corresponding probability. To this end, we first derive the probability for an active sensor node to perform a CCA at a time t ∈ [fm, Smax]. We need to discriminate between active nodes that have participated to event em, and active nodes that have not participated.
In the former case, after participating to em, sensor nodes are in one of the states B1j,2 ≤ j ≤ Tmax, i.e. the first backoff stage of a retransmission attempt. Hence, according to CSMA/CA, they will perform a CCA after waiting for both the retransmission timeout Dto and a random number w ∈ [0, W1 −1] of backoff periods. Since w is uniformly distributed in [0, W1 − 1], the probability P{C C Atp | c} that any of the considered sensor nodes will perform a CCA at time t ∈ [fm, Smax] is equal to
1 for t ∈ [fm +2Dbp, fm +2Dbp +(W1 −1)Dbp], and W1
zero otherwise (see also figure 6b).
In the second case, we consider nodes that have not
participated to em. First, we correct the computation of P{CCAt1j | c}, 2≤j ≤Tmax, for time instants t∈[fm + 2·Dbp, fm +2·Dbp +(W1 −1)·Dbp], in equation 14 as
Claim 8. Let P{Ap | c} denote the probability that any of the Nr nodes: (i) is still active at t = fm and (ii) it has participated to the last event em in chain c, i.e. it has performed a CCA at time t = tm. It is
Tm = S
= F (18)
Claim 9. Let P{Anp | c} denote the probability that any of the Nr sensor nodes: (i) is still active at time t = fm, and (ii) it has not participated to the last event em in chain c, i.e. it has not performed a CCA at time t = tm. Hence,
0
Bmax Tmax−1 P{CCAtm | c}
P{Ap | c} =
Proof: See Appendix F.
T
i=1 j=1 ij m
Smax
P{Anp | c}= P{CCAt | c}−P{Ap | c}
t=fm Proof: See Appendix G.
(19)
Let us denote by N = [Np, Nnp, Nd] a composition of sensor nodes, where (i) Np indicates the number of nodes that are still active at fm and have participated to event em (i.e. have performed a CCA at time t = tm), (ii) Nnp is the number of nodes that are still active at fm but have not participated to em (i.e. have not performed a CCA at time t = tm), and (iii) Nd is the number of sensor nodes that have dropped their packet and, hence, are no more active at fm. By definition, ∀N, ∀c, Np +Nnp +Nd = Nr. We now compute the probability of N, P{N | c}, both when em is a success and when it is a failure.
If em is a success Tm =S, then P{Ap | c}=0. This is because it is not possible for a node to be still active after experiencing a success (each node has a single packet to transmit). Hence, Np = 0, ∀N, and P{N | c} is equal to:
Nr N N
P{N | c} = N · P{Anp | c} np · P{D} d (20)
np
In Equation 20 P{D} = P{FCCA | c} + P{FRtx | c}
is the probability that a sensor node has dropped its data packet due to either exceeded number of backoff stages or exceeded number of retransmissions, before fm. In addition, the second and third terms provide the
Bmax 1 P{CCAt | c} = P{CCAt | c}− P{CCAtm | c}·
1j 1j ij−1W i=1 1 (22)
This is to exclude those cases that lead the sensor node to perform a CCA at time t after performing a CCA at time tm. Thus, P{CCAtnp | c}, for t ∈ [fm, Smax], is:
P{CCAtnp | c} =
P{CCAt | c} P{Anp }
(23)
Equation 23 can be explained as follows. Since we are considering an active sensor node, it will surely perform a CCA at a time t ≥ fm. Hence, for such a node, the probability to perform a CCA at a specific time t ∈ [fm , Smax ] can be calculated by normalizing P{C C At | c} with probability P{Anp }, i.e., the probability that the node will perform a CCA at any instant t ≥ fm.
10
Now, we derive both P{esi | N} and P{efi | N}, i ∈ {0, 1, …, Mw} where P{esi | N} (P{efi | N}) denotes the probability that the first event that occurs after em, given the composition of nodes N, is a success (failure) occuring at time ti = fm + i · Dbp. Claim 11 holds.
6.4 Parallelization of ECC algorithm
As shown in Figure 4, ECC continuously performs the following steps:
1) extracts a chain c : sc = {e1, e2, …, em} from Lc; 2) generates all the events ex that can occur after em. 3) ∀ex, adds cx : scx = {e1, e2, …, em, ex} to Lc.
During the execution of the three steps above only information associated with chain c is used by the al- gorithm. Hence, it is possible to speed-up the execution by allowing more threads to manage different chains in parallel. In section 7 we show, through experimental measurements, that the execution time of the ECC algo- rithm decreases almost linearly with the number of used threads. This drastically reduces the computation time needed to generate all the possible outcomes and makes the analysis of large networks computationally feasible.
6.5 Derivation of performance metrics
When Lc becomes empty, Fc contains all chains c repre- senting possible outcomes of the CSMA/CA execution with a probability to occur greater than, or equal to, θ. By using chains c ∈ Fc, we derive the following metrics:
Claim 11.
fm +i·Dbp P{esi | N} = Nnp ·P{CCAnp |c}
j =i+1 Proof: See Appendix I.
• •
•
•
Coverage (C): portion of event space covered by chains in Fc; it characterizes the ECC accuracy. Packet delivery ratio (R): fraction of data packet suc- cessfully transmitted to the coordinator node; it measures the reliability provided by CSMA/CA. Packet latency (L): delay experienced by a sensor node to successfully transmit its data packet to the coordinator node; it indicates the timeliness allowed by CSMA/CA in reporting an event.
Energy consumption (E): average total energy con- sumed by all sensor nodes in the network to report an event to the coordinator node; it measures the energy efficiency of CSMA/CA.
Mw
·
j =i+1 Mw
·
fm+j·Dbp P{CCAnp
fm+j·Dbp P{CCAp
Nnp−1 | c}
Np | c}
j =i+1
+ Np · P{CCAp
Np−1 | c}
Nnp | c}
Let us focus now on probability P{efi
failure can occur only if Nnp + Np ≥ 2 it follows that P{efi | N}=0, ∀i∈[0, Mw] if Np +Nnp <2. Below, we will focus on cases where Np + Nnp ≥ 2. We denote by comp(m) the set of compositions (m1 , m2 ) of an integer m in two distinct parts m1 and m2 with m1 +m2 = m.
Claim 12.
Np +Nnp
P{efi |N}= N
p
m
Mw
Mw
·
j =i+1 Mw
·
fm+j·Dbp P{CCAp
fm+j·Dbp P{CCAnp
fm +i·Dbp
| c}·
1
j =i+1 Nnp m2
Mw
fm +i·Dbp P{CCAnp
m
·
|c} 2 Nnp−m2
j =i+1
Proof: See Appendix J.
m=2
· P{CCAp
(m1, m2)∈comp(m):m1≤Np∧m2≤Nnp
m1 | c}
Np−m1 | c}
| c}
Letc : s ={e , e , ..., e }beaspecificchaininset i ci 1 2 m
Fc, and pci its associated probability. Then, the coverage
C can be calculated as follows:
C= pci (26) ci ∈Fc
To derive the delivery ratio R we compute, for each chain ci, the fraction of successful transmissions Ri occurred in ci. Since there are N nodes in the network and each node transmits one data packet, Ri can be easily calculated as Ri = Ns i/N where Ns i is the number of successful transmissions in ci. Since each chain ci has probability pci to occur, the delivery ratio R is given by
R= pci ·Ri (27)
C
ci ∈Fc
To calculate the average latency L we first derive
the probability density function (PDF) of packet latency. Specifically,theprobabilityP(t)tosuccessfullyreceivea data packet with a delay equal to t is
P(t) = pci (28) ci∈Fc:∃ej∈sci|Tj=S∧fj=t
fm+i·Dbp
fm+j·Dbp P{CCAp
fm+j·Dbp P{CCAnp
| N}. Since a
Finally, using the law of total probability, we derive both P{esi | c} and P{efi | c}, i ∈ [0, Mw] as follows.
P{esi |c}=P{N|c}·P{esi |N} N
P{efi | c}=P{N | c}·P{efi | N} N
(24) (25)
P(t) is the sum of the probabilities of all chains ci containing a successful transmission at t. Then, by de- noting as tmax the largest instant at which a successful transmission can occur, we compute L as:
Figures 7-9 compare simulation results with the an- alytical results provided by the ECC algorithm, and the models in [16] and [18], in terms of delivery ra- tio, average latency and average energy consumption, respectively, for different network sizes (i.e., number of sensor nodes). We anticipate that the graphs also show the results related to the experimental evaluation described in Section 7.4 (Testbed label). Finally, Figures 10-12 compare the probability density function (PDF) of packet latency for three different network sizes (i.e, with 5, 30, and 50 sensor nodes). Figure 9 reports the analyt- ical results of ECC only since the other two considered models do not provide the energy consumption. Also, in all the presented graphs, results related to SAN model are only available for networks composed of at most 5 nodes. This is due to the very high complexity of this model (that increases exponentially with the network size) that prevented us to run the analysis with higher network sizes. Finally, we want to point out that the analytical results of ECC have been obtained using θ = 0.
In general, we observe that ECC results and simulation results almost overlap in all the considered scenarios. We studied additional scenarios, with different parameter values, and observed a similar agreement. Some of these results are presented in section 7.3.
Focusing on the Tagged node model [16], we observe a good match between analysis and simulations for small network sizes. Conversely, the gap between analysis and simulations becomes significant with high network sizes. This is because the impact of retransmissions, which was not considered in [16], becomes more apparent as the number of nodes increases (i.e. when the collision probability is high). Specifically, by looking at Figures 10-12 we can observe that the percentage of packets with high delays significantly increases with higher network sizes. However, the Tagged node model is not able to capture at all the contribution of such long-latency packets (since it neglects retransmissions). Finally, we can observe a perfect match between the SAN model results and simulations. However, we remark that the high complexity of the model allows to study only very small networks. Also, we recall that, unlike ECC, the con- sidered models do not provide the energy consumption of nodes, that is a fundamental metric for WSNs.
Figure 7 shows that the delivery ratio drastically re- duces with the number of sensor nodes and it is very low even with a limited number of sensor nodes. This is because the 802.15.4 CSMA/CA is not able to manage contention efficiently even when the number of contend- ing nodes is relatively low, due to its random nature. In the considered event − driven scenario this limitation is more apparent as all sensor nodes in the network start reporting data simultaneously, upon detecting an event.
Figures 8 and 9 show that both the average latency and energy consumption increase with the network size, as expected. This is because when the number of sensor nodes contending for channel access increases, the colli- sion probability increases as well. Hence, sensor nodes
tmax t·P(t) t=0
L= tmax P(t) (29) t=0
Finally, we calculate the average total energy con- sumption E. Let enci be the total energy consumed by all sensor nodes when the events of chain ci occur. Hence,
E=pci ·enci (30)
11
C
The derivation of enci is reported in [28].
ci ∈Fc
7 RESULTS
In this section, we evaluate the accuracy and tractability of our analytical model. We also use the model to investigate the performance of CSMA/CA in the con- sidered event-driven scenario. Furthermore, we compare the results obtained using the ECC algorithm with those of the following two analytical models:
• Tagged node model [16]. It focuses on a single node of the network (tagged-node), and provides delivery ratio, average packet latency and delay distribution. The effects of acknowledgments and retransmis- sions are not considered.
• SAN model [18]. It makes use of stochastic automata networks (SANs) and considers the entire WSNs (i.e. all nodes altogether). It provides delivery ratio, average packet latency and delay distribution but not energy consumption.
These models are the state-of-the-art models for event- driven WSNs using the unslotted 802.15.4 CSMA/CA.
7.1 Model validation
We validate our analytical model through simulations implemented on the ns2 simulation tool [23], which includes the 802.15.4 module. In our simulations we consider a star network topology with sensor nodes located in a circle of radius 10m centered at the coor- dinator node. The transmission range was set to 15m, while the carrier sensing range was set to 30m. In all the simulations we assume that the 802.15.4 MAC protocol is operating in NBE mode with a 250 Kbps bit rate. Power consumption values are derived from the Chipcon CC2420 radio transceiver [24]. Unless stated otherwise, we use the following set of CSMA/CA parameter values: macMinBE = 3, macMaxBE = 4, macMaxBackoffs = 2, macMaxFrameRetries = 1.
For each simulation experiment, we performed 10 independent replications, each of which consists of 10000 cycles. In each cycle, it is assumed that all sensor nodes have to transmit one packet. We derived confidence intervals by using the independent replications method and a 95% confidence level. However, they are typically very small and cannot be appreciated in the plots below.
90 80 70 60 50 40 30 20 10
0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05
ECC
Tagged node model
SAN model
Simulation Testbed
5 10 15 20 25 30 35 40 45 50
Number of Nodes
Fig. 7: Delivery Ratio.
Latency PDF, 5 nodes
ECC
Tagged node model 0.2
SAN model
Simulation 0.15 Testbed
0.1 0.05
4
ECC ECC
Delivery Ratio
Avg. Packet Latency
Avg. Energy Consumption
25 20 15 10
5
0.35
0.3
0.25
3 2.5 2 1.5 1 0.5 000
Tagged node model
SAN model
Simulation Testbed
5 10 15 20 25 30 35 40 45 50
Number of Nodes
Fig. 8: Average Packet Latency.
3.5 Simulation Testbed
5 10 15 20 25 30 35 40 45 50
Number of Nodes
Fig. 9: Average Energy Consumption.
12
Probability
Delivery ratio (%)
Probability
Avg. packet latency (ms)
Probability
Avg. energy consumption (mJ)
000
Latency PDF, 30 nodes
Latency PDF, 50 nodes
Tagged node model
Simulation Testbed
0.005 0.01 0.015 0.02 0.025 0.03 0.005 0.01 0.015 0.02 0.025 0.03 0.005 0.01 0.015 0.02 0.025 0.03
ttt
Fig. 10: Latency PDF, 5 nodes. Fig. 11: Latency PDF, 30 nodes. Fig. 12: Latency PDF, 50 nodes. TABLE 1: Analytical results, R(%), L (ms), E (mJ), Time (s), with different values of θ.
θ = 0 θ = 10−7 θ = 10−5
C Chains R L(ms) E(mJ) Time(s) C Chains R L(ms) E(mJ) Time(s) C Chains R L(ms) E(mJ) Time(s)
N
10 1 1842355 19.94 12.33 0.822 14407 0.999 27590 19.94 12.32 0.822 398 0.970 3814 19.88 12.17 0.811 93
30 1 1842355 6.07 17.81 1.970 24768 0.999 19536 6.07 50 1 1842355 3.40 20.36 3.130 33264 0.999 11509 3.40
consume more energy. In addition, they take more time to transmit their packets. Specifically, successful trans- missions tend to occur some time after the beginning, when the level of contention is lower because some nodes have already given up, due to exceeded number of backoff stages or retransmissions (see Section 3). This behavior is confirmed by Figures 10-12, where the highest spikes in the latency PDF shift to the right side of the graphs as the number of sensor nodes increases.
7.2 Impact of θ and multithreading
In order to evaluate the trade-off between tractability and accuracy of our model, Table 1 summarizes the analytical results obtained with different values of θ (the network parameter values are the same as in Section 7.1). Specifically, Table 1 shows the number of chains gener- ated by the ECC algorithm, the coverage of the event space (C), the performance metrics defined in Section 6.5 (i.e., R, L and E) and, finally, the computation time (in seconds) required to compute the same performance metrics. When using θ = 0, a coverage of 100% and, hence, the maximum accuracy of results is obtained. However, the number of generated chains is very large (more than 1800000), which requires a high computation time (33264s in the case of 50 sensor nodes, i.e. 9 hours).
As expected, the coverage of the event space decreases as the value of θ increases. With θ = 10−5, it reduces to 97 − 98%, however the model still obtains nearly the same accuracy as with θ = 0. Moreover, the computation
17.81 1.970 922 0.978 3224 6.04 17.75 1.966 267 20.36 3.130 875 0.987 2253 3.39 20.34 3.136 316
time reduces by a factor larger than 100, and the number of generated chains reduces by a factor larger than 500, with respect to θ = 0, when N = 50. These results can be explained as follows. As mentioned in Section 6, ECC analyzes only events that are most likely to occur in the network, which are the events that will influence most the performance metrics. This way, ECC achieves approximately the same accuracy as when θ = 0 while analyzing a much lower number of events. Therefore, it saves a tremendous amount of computation time.
Surprisingly, Table 1 shows that, when θ > 0, the number of chains generated by ECC decreases as the network size increases. In addition, the coverage in- creases although the number of chains decreases. This apparently counterintuitive behavior can be explained as follows. When the number of sensor nodes increases, some events become significantly more likely to occur than others. For instance, if N = 50, collisions are more likely to occur than successful transmissions. Therefore, when N = 50, ECC will select, at each step, fewer (yet very likely) events with respect to the case N = 5. Hence, the number of considered chains decreases (and the coverage increases), as the number of nodes increases. This property of ECC reduces the computation needed to calculate the metrics of interest when the network size increases, making the analysis of large networks easier.
Finally, to further assess the model tractability, we measured the average computation time of the analytical model as a function of the number of threads that are activated. Figure 13 shows that the computation time
ECC
0.35
0.3
0.25
0.2
0.15
0.1
0.05
ECC
Tagged node model
Simulation Testbed
decreases almost linearly with the number of threads. This is because the algorithm is implemented in such a way to assign the computation of the various chains to different threads. Since threads synchronize only to modify a global data structure (i.e. the list of chains Lc), each thread is almost independent from the others. Hence, the almost linear decrease of computation time.
7.3 Impact of CSMA/CA parameters
In this section we evaluate the impact of each single CSMA/CA parameter on the overall performance. To this end, we focus on a network with 30 sensor nodes. For the sake of space, we only show the delivery ratio, however, we also derived the average latency and energy consumption (see [28] for the complete set of results). We also report the analytical results obtained by Tagged node model. We do not consider the SAN model due to its high complexity with the considered network size.
In general, we can observe a quite good match be- tween ECC results and simulation results. Conversely, there is a significant gap between simulation results and the Tagged node model results. This is due to the semplifications introduced by this model.
Figure 14 shows that increasing the maximum allowed number of retransmissions (i.e. macM axF rameRetries) does not provide any significant effect on the delivery ratio, for values larger than one. This is because the majority of packets are dropped by the MAC proto- col because of exceeded number of backof stages (i.e., consecutive CCAs). Indeed, increasing the maximum number of backoff stages (i.e. the macM axBackof f s) results in an increase of the delivery ratio, as shown in Figure 15. Furthermore, we also observed an increase in both the average latency and energy consumption. This is because a larger number of packets is successfully transmitted, which takes more time and more energy. Finally, Figure 16 shows that increasing the minimum backoff window size (i.e. macMinBE) also causes an increase of the delivery ratio. The motivation is that a larger initial backoff window size reduces the collision probability at the first backoff stage, thus increasing the probability of successful transmission. Again, we observed an increase in the average latency. Instead, the energy consumption decreases since less collisions occur.
The above results show that increasing the CSMA/CA parameter values is beneficial in terms of increased communication reliability. However, it also increases the energy consumption and packet latency, which may not be good for time-critical applications. Hence, the most appropriate parameter setting depends on the specific application scenario.
7.4 Experimental evaluation
To verify the ability of our analytical model to predict the performance of the WSN in a real environment, we im- plemented the 802.15.4 unslotted CSMA/CA algorithm in the Contiki OS [26]. For experimental measurements
we used a testbed composed of Tmote-sky motes [25]. As in the analysis, all nodes simultaneously start trans- mitting a data packet to a common coordinator node. We repeat this experiment 1000 times.
We performed different sets of experiments varying the number of nodes in the network (from 2 up to 50) as well as the MAC parameter values. The obtained results are reported in Figures 7-12 and Figures 14-16 (Testbed label). In general, we can observe that experimental and ECC results are very close in all the considered scenarios. In some cases we noticed that the performance of the real WSN is slightly better than what predicted by the analysis (e.g. lower latency in experiments with respect to analysis (Figure 8) and higher spikes of PDF in experiments with respect to analysis (Figures 10-12)). We found that this apparently counterintuitive behavior is due to the capture effect that occurs in the real testbed, i.e. the ability of the radio to correctly receive a strong signal from one transmitter, despite significant interfer- ence from other transmitters [27].
8 CONCLUSIONS
In this paper, we have presented an analytical model of the unslotted CSMA/CA algorithm used in 802.15.4 WSNs operating in NBE mode. The proposed model is both accurate and efficient. It leverages an approach called Event Chains Computation (ECC), that reduces com- plexity, with a limited loss of accuracy, by removing event sequences whose probability to occur is below a given threshold. We have shown that the computation time required for deriving the performance metrics of interest can be reduced by a factor larger than 100, or more, with a negligible impact on the accuracy of the obtained results. Also, our model can exploit a multi- threading approach, thus taking advantage of a parallel execution. Our model allows an accurate analysis of 802.15.4 WSNs in NBE mode, even when there is a large number of sensor nodes. As a matter of fact, we have used our model to investigate the impact of dif- ferent CSMA/CA parameters on the WSN performance. We have observed that, in the considered scenario, the delivery ratio is very low even when the number of contending nodes is relatively low. It can be improved by increasing the initial backoff-window size and/or the maximum number of backoff stages allowed for each packet. However, this also increases the energy consumption and packet latency.
9 ACKNOWLEDGMENTS
We thank the AE and the reviewers for their insight- ful comments. This material is based upon work sup- ported by the National Science Foundation under Grant No. CNS-1355505, CNS-1545037, and CNS-1545050. This work has been also partially supported by the University of Pisa, in the framework of the PRA 2015 program.
13
Delivery ratio, 30 nodes Delivery ratio, 30 nodes Delivery ratio, 30 nodes 16 16 16
14 14 14 12 12 12 10 10 10
888
666
444
222
000 123412341234
macMaxFrameRetries macMaxCSMABackoffs macMinBE
Fig. 14: Delivery ratio vs. Fig. 15: Delivery ratio vs. Fig. 16: Delivery ratio vs.
macMaxFrameRetries macMaxCSMABackoffs macMinBE
14
ECC
Tagged node model
Simulation Testbed
ECC
Tagged node model
Simulation Testbed
ECC
Tagged node model
Simulation Testbed
Fig. 13: Avg. computation time vs. number of threads.
REFERENCES
[1] IEEE Standard for Information technology, Part 15.4; Wireless Medium Access Control (MAC) and Physical Layer (PHY) Spec- ifications for Low-Rate Wireless Personal Area Networks (LR- WPANs), IEEE Computer Society, 2006.
[2] The ZigBee Specification version 2.0, December 2006.
[3] ABIResearch.https://www.abiresearch.com/press/more-than-30-
billion-devices-will-wirelessly-conne
[4] Y. Li, My T. Thai, W. Wu, “Wireless Sensor Networks Applica-
tions”, Springer, Feb. 2008.
[5] L.Atzori,A.Iera,G.Morabito,“TheInternetofThings:Asurvey”,
Computer Networks, Vol. 54, No. 15, pp. 2787-2805, 2010.
[6] I. Ramachandran, A. K. Das, S. Roy, “Analysis of the Contention Access Period of IEEE 802.15.4 MAC”, ACM Transactions on
Sensor Networks, Vol. 3, No. 1, March 2007.
[7] P. Park, C. Fischione, and K.H. Johansson, “Modeling and Stability
Analysis of Hybrid Multiple Access in the IEEE 802.15.4 Protocol”,
ACM Transactions on Sensor Networks, Vol. 9, No. 2, April 2013.
[8] P. Park, P. Di Marco, C. Fischione, K.H. Johansson, “Modeling and Optimization of the IEEE 802.15.4 Protocol for Reliable and Timely Communications”, IEEE Transactions on Parallel and Distributed
Systems, Vol. 24, No. 3, pp.550–564, March 2013.
[9] C. Gezer, A. Zanella, and R. Verdone, “An Analytical Model for the Performance Analysis of Concurrent Transmission in IEEE
802.15.4”, Sensors, Vol. 14, No. 3, pp. 5622–5643, March 2014.
[10] D. Striccoli, G. Boggia, and L.A. Grieco, “A Markov Model for Characterizing IEEE 802.15.4 MAC Layer in Noisy Environments”,
IEEE Transactions on Industrial Electronics, August 2015.
[11] X. Cao, J. Chen, Y. Cheng, S. Shen, and Y. Sun, “An Analytical MAC Model for IEEE 802.15.4 Enabled Wireless Networks with Periodic Traffic”, IEEE Transactions on Wireless Communications,
to appear. DOI: 10.1109/TWC.2015.2435006
[12] M.S. Haghighi, Yang Xiang, V. Varadharajan, and B. Quinn, “A
Stochastic Time-Domain Model for Burst Data Aggregation in IEEE 802.15.4 Wireless Sensor Networks”, IEEE Transactions on Computers, Vol. 64, No. 3, pp. 627–639, March 2015.
[13] P. Di Marco, P. Park, K.H. Johansson, “Analytical Modeling of Multi-hop IEEE 802.15.4 Networks”, IEEE Transactions on Vehicu- lar Technology, Vol.61, No.7, pp.3191-3208, 2012.
[14] P. Di Marco, C. Fischione, F. Santucci, K.H. Johansson, “Modeling IEEE 802.15.4 Networks Over Fading Channels”, IEEE Transactions on Wireless Communications, Vol.13, No. 10, pp. 5366–5381, 2014.
[15] M. Goyal, D. Rohm, W. Xie, S.H. Hosseini, K.S. Trivedi, Y. Bashir, and A. Divjak, “A Stochastic Model for Beaconless IEEE 802.15.4 MAC Operation”, Computer Communications, 2011.
[16] C. Buratti, R. Verdone, “Performance Analysis of IEEE 802.15.4 Non Beacon-Enabled Mode”, IEEE Transactions on Vehicular Tech- nology, Vol. 58, No.7, pp. 3480-3493, 2009.
[17] F. Martelli, C. Buratti, and R. Verdone, “Modeling Query-Based Wireless CSMA Networks Through Stochastic Geometry”, IEEE Transactions on Vehicular Technology, Vol. 63, No. 6, July 2014.
[18] M. Gribaudo, D. Manini, A. Nordio, C.F. Chiasserini, “Transient Analysis of IEEE 802.15.4 Sensor Networks”, IEEE Transactions on Wireless Communications, Vol. 10, No. 4, 2011.
[19] C. K. Singh, A. Kumar, P. M. Ameer, “Performance Evaluation of an IEEE 802.15.4 Sensor Network With a Star Topology”, Wireless Networks, Vol. 14, N. 4, August 2008.
[20] G. Anastasi, M. Conti, M. Di Francesco, “A Comprehensive Ana- lysis of the MAC Unreliability Problem in IEEE 802.15.4 Wireless
Sensor Networks”, IEEE Transactions on Industrial Informatics,
Vol.7, N.1, pp.52-65, February 2011.
[21] Petrova, M., Riihijarvi, J., Mahonen, P. and Labella, S., “Perfor-
mance Study of IEEE 802.15.4 Using Measurement and Simula-
tions”, in Proc. of IEEE WCNC, Las Vegas, NV, USA, 2006.
[22] B.D.Plateau,K.Atif,“StochasticAutomataNetworkofModeling Parallel Systems”, IEEE Transactions on Software Engineering, Vol.
17, No. 10, 1991.
[23] Network Simulator Ns2. http://www.isi.edu/nsnam/ns/.
[24] Chipcon CC2420 Website, http://www.ti.com/product/cc2420. [25] J. Polastre, R. Szewczyk, D. Culler. Telos: Enabling Ultra-low
Power Wireless Research. In ACM/IEEE IPSN, 2005.
[26] A.Dunkels,B.Gro ̈nvall,T.Voigt,“Contiki-alightweightandflex- ible operating system for tiny networked sensors”, Local Computer
Networks, 29th Annual IEEE International Conference on, 2004. [27] K. Whitehouse, A. Woo, F. Jiang, J. Polastre, and D. Culler, “Ex- ploiting the capture effect for collision detection and recovery”, in Proceedings of the 2nd IEEE workshop on Embedded Networked
Sensors, 2005, pp. 4552.
[28] D. De Guglielmo, http://hdl.handle.net/2158/1004238. Domenico De Guglielmo is a Postdoctoral Researcher in the Dept. of Information Engineering at the University of Pisa. His research interests
are in the field of WSNs and Internet of Things.
Francesco Restuccia is a Ph.D candidate in the Department of Com- puter Science at the Missouri University of Science and Technology. His research interests include pervasive and mobile computing and WSNs. Giuseppe Anastasi is a Full Professor at the Dept. of Information Engineering at the University of Pisa, Italy. He is also the Director of the CINI National Smart Cities Lab. His research interests include pervasive computing, sensor networks, sustainable computing, and ICT or smart cities. He has contributed to many research programs funded by both national and international institutions. He has co-edited two books and published more than 120 papers in international journal and conferences. Dr. Anastasi is an Associate Editor of Sustainable Computing, and Pervasive and Mobile Computing. He has served as General Co-chair and Program Chair of many international conferences. Marco Conti is Research Director of the Italian National Research Council (CNR) and Director of the CNR department of Engineering, ICT and Technologies for Energy and Transports. He published in journals and conference proceedings more than 300 papers related to design, modelling, and performance evaluation of computer-network architectures and protocols. He is the Editor-in- Chief of Elseviers Computer Communications Journal, and Associate Editor-in-Chief of Elseviers Pervasive and Mobile Computing (PMC) Journal. He served as general/program chair for several conferences, including IEEE Per- Com, IEEE WoWMoM, IEEE MASS, ACM MobiHoc, and IFIP TC6 Networking.
Sajal K. Das is the Chair and Daniel St. Clair Chair Professor of Computer Science Department at the Missouri University of Science and Technology. During 2008-2011, he served the US National Science Foundation as a Program Director in the division of Computer Networks and Systems. He has published over 500 papers in journals and conferences, 47 book chapters, and holds five US patents. He has also coauthored three books. Dr. Das is a recipient of the IEEE Computer Society Technical Achievement Award for pioneering contributions in sensor networks and mobile computing. He is the Founding Editor-in- Chief of Elseviers Pervasive and Mobile Computing (PMC) journal, and an Associate Editor of IEEE Transactions on Mobile Computing, ACM Transactions on Sensor Networks, ACM/Springer Wireless Networks, Journal of Parallel and Distributed Computing, and Journal of Peer-to- Peer Networking and Applications.
Delivery ratio (%)
Delivery ratio (%)
Delivery ratio (%)