Timeliness of Wireless Sensor Networks With Random Multiple Access

I. INTRODUCTION

IN recent years, with the continuous development of Internet of things (IoT) technology, a growing number of emerging IoT applications appear in our daily lives, such as intelligent home, smarter healthcare, smarter city, industry 4.0 and so on [1]–[3]. In the real-time application oriented IoT systems, the remote receiver needs to perceive the physical environment and monitor the instantaneous state of the system to provide timely and effective information for intelligent decision-making and control. For example, the instantaneous acceleration and position of vehicles in auto-driving, the temperature/soil-moisture of the ambient environment in smart agriculture, network controls of decision-making systems in modern factories of industry 4.0, and so on. For such information with timeliness requirements, delivering outdated information would reduce the reliability of system decision-making significantly and cause substantial security risks. Therefore, timeliness is essential for IoT based real-time monitoring systems and status updating systems.

Traditional data communications focus more on the delay of information transmissions. The indices such as throughput and delay could not effectively characterize the timeliness of updates. For example, in a simple M/M/1 queueing system, the more frequent the packets arrive, the larger the throughput but the delay would be out of expectation, even tends to infinity (due to congestions); the sparser the packets arrive, the fewer timely update receptions there would be, which may result in delayed information transmission and wrong action with high probability. Thus, neither delay nor throughput can exactly characterize the freshness of the received information. To this end, an emerging metric called the age of information (AoI) was formally introduced in [4]. Specifically, the AoI of the system is defined as the difference between the current moment and the generation moment of the latest successfully received update packet [5].

From the definition of AoI, we see that it is essentially different from delay and throughput and reflects accurately the freshness of the latest available information at the remote receiver. Therefore, quantifying information freshness through the AoI metric has been extensively investigated. In [5], the authors analyzed the AoI of the M/M/1, M/D/1, and D/M/1 queuing systems under the first-come-first-served (FCFS) rule through the classical queueing theory approach. Subsequently, the AoI of M/G/1 and G/G/1/1 queuing models were studied in [6] and [7], respectively. There were also some works investigating the AoI of status update systems under different service strategies, such as the last-come-first-served (LCFS) policy [8], the last-generated-first-served (LGFS) policy [9], and the zero-waiting policy (i.e., provide new information as soon as the previous one is delivered) [10]. Although the service strategies mentioned above may be suitable for certain applications, none of them is optimal in a general sense.

In wireless sensor networks (WSNs) with limited spectrum resources, packet collisions may frequently occur since multiple sensors usually access the channel over the same frequency band simultaneously. This prevents the receiver from receiving information in time and wastes many channel resources. Therefore, it is critical to utilize appropriate access protocols so that multiple sensors can efficiently deliver their monitored status updates over a shared channel. Moreover, since for the networks with a large number of sensors, each sensor may work intermittently, the fixed multiple access techniques like tme division multiple access (TDMA) and frequency division multiple access (FDMA) may not be suitable for such scenarios and with low efficiency. Thus, random multiple access techniques, (e.g., carrier sense multiple access with collision avoidance (CSMA/CA) and slotted ALOHA and so on) are the promising modes for WSNs.

The CSMA/CA and the slotted ALOHA have been extensively investigated in terms of traditional performance metrics such as throughput and delay. For instance, in [11], G.Bianchi analyzed the throughput of a CSMA/CA based network by employing a two-dimensional Markov chain model. However, the model proposed by G.Bianchi is only applicable to saturated networks, i.e., all the nodes have data packets to transmit all the time. Thus, Duffy et al. have extended this Markov chain model to the unsaturated networks [12]. Slotted ALOHA stability has been studied in [13] and [14]. In [13], the authors studied the stability region for a finite user infinite cache in a slotted ALOHA system. The authors gave the precise region of system stability for the two-user case. Along a similar line, the authors in [14] analyzed the stability of the system in the case of infinite users with single buffer. The results of the drift analysis showed that when the number of users approaches infinity, the Markov chain of the channel backlog is ergodic in a collision channel if the packet rate is smaller than the expected number of successfully received packets.

There have been some works investigating the AoI for CSMA based networks, such as [4] and [15]–[19]. To be specific, in [4], the average AoI of a CSMA based vehicular network is investigated through simulations. In [17], the authors used the stochastic hybrid systems technology to analyze the AoI of the CSMA based network under the condition that no collisions occur and the channel perception delay is zero. They also derived the average AoI of a CSMA based network with a large collision probability in [18]. In our previous work, the average AoI a CSMA/CA based network was analyzed theoretically [19]. There were several applications of CSMA in CSMA based IoT LoRa networks, such as the wildlife state monitoring in transmission LoRa networks [20] and the remote sensor data transmission in IoT LoRa network [21].

For the ALOHA based networks, the information freshness was explored in [22]–[28]. Particularly, the average AoI of a slotted ALOHA-like network with all-active source nodes (i.e., generating data packets in every slot) was investigated in [22]. In [23], it analyzed the AoI of a slotted ALOHA based network with an infinite number of source nodes. To be specific, they proposed a dynamically packets discarding scheme to minimize the average AoI of the network, which may be suitable to those time sensitive scenarios. In [24], the authors studied several scheduling strategies for a multiaccess channel. They optimized the AoI of the network under the requirement of satisfying the real-time throughput of each node. In random access applications, however, adopting such strategies would consume a lot of communication. The age of an unslotted, uncoordinated, and unreliable multi-access collision channel was analyzed in [25]. The results showed that when the number of nodes and the update rate increase with a constant proportion, the limiting asymptotic age can denote as an approximation age for each node. The information age of the feedback-free slotted ALOHA transmission system using retransmission strategy has been investigated in [26]. It found that for low arrival rates, the retransmission strategy can diminish the message age with a cost of throughput. An age threshold based ALOHA protocol was proposed in [27], in which every node is allowed to access the channel with a certain probability only if its immediate AoI is larger than a predefined age threshold. The joint optimization of the transmission probability and the age threshold was investigated in [28]. They found that the optimal AoI is 1.4169n times the network size n. In practical engineering implementations, ALOHA has also been selected as the multiple access technique for the low power wide area networks (LPWAN) [29]–[31].

However, the aforementioned works neither provided explicitly expressions of average AoI for CSMA/CA based network nor provided a comparison on the their timeliness. In this paper, we try to discuss these two issues. The target of us is that explicitly characterize the timeliness of an unsaturated wireless sensor network in terms of AoI, for the CSMA/CA protocol and the slotted ALOHA (shown in Fig. 1). The main difference from those previous works described above is that we set up an equivalent and tractable transmission model to evaluate the AoI performance explicitly, and the results can reflect the system parameters precisely.

A. Main Contributions

The contributions of this paper are summarized as follows.

1) For the CSMA/CA based network, we develop an equivalent and universal transmission model for the transmission process and back-off process. Based on this newly developed model, we derive the transmission probability and the collision probability of the sensor nodes explicitly. In the slotted ALOHA based network, we also derive the transmission probability and the collision probability of the sensor nodes explicitly. We show that both the transmission probability and the collision probability are increasing with the arrival rate and the number of sensor nodes.

2) For both the CSMA/CA based and the slotted ALOHA based networks, we derive the maximum packet rates and the allowable numbers of sensor nodes. We also explicitly present the average AoIs of two networks in closed forms. Our results show that the average AoI of the CSMA/CA based network is always smaller than that of the slotted ALOHA based network for the same transmission probability, regardless of changes in the arrival rate and the number of sensor nodes. To the best knowledge of the authors, this is the first result explaining why the CSMA/CA outperforms the slotted ALOHA in terms of AoI in theory.

3) We investigate the transmission probability, the collision probability, and the average AoIs of heterogeneous networks through simulations. The simulation results indicate that the changes in the transmission probability, the collision probability, and the average AoIs are with similar modes to the corresponding homogeneous networks.

B. Organization

The rest of the paper is organized as follows. We present the wireless sensor network model and the definition of the AoI in Section II. In Section III, we analyze the CSMA/CA and the slotted ALOHA transmission behaviors and establish an equivalent and universal transmission model for the CSMA/CA based network to derive the transmission probability and collision probability of the sensor nodes. We also explicitly obtain closed-form expressions for the average AoIs of networks that employ the CSMA/CA protocol and the slotted ALOHA protocol. The Monte Carlo simulation results and numerical results are given in Section IV. Finally, the conclusion and future direction are presented in Section V.

II. SYSTEM MODEL

As shown in Fig. 1, we consider a single-hop wireless sensor network consisting of N identical sensor nodes and a common remote receiver, in which all sensor nodes are visible to each other (i.e., without hidden nodes). Each sensor node observes the information of interest and attempts to transmit the observed information to the remote common receiver independently. All the sensor nodes contend for the channel through the CSMA/CA protocol or the slotted ALOHA protocol. We assume that the data packet generation of each sensor node follows the Bernoulli process with a rate of p. Every sensor node stores its data packets in a buffer and delivers the data packets using the FCFS policy.

Time is divided into discrete slots of equal length and all data packets are of the same size. The start and completion of each data packet transmission occur at the slot boundaries and it takes exactly one slot for the transmission of every data packet. We assume that transmission failures occur only when two or more nodes are transmitting their data packets in the same slot. In addition, we employ the late-arriving system with delayed access. That is, the data packets are generated or received at the end of slots.

In a slotted CSMA/CA based network, every sensor node needs to wait for a random period of t slots (which is referred to as the back-off time) before attempting to transmit a data packet to avoid collisions. The back-off time t would be chosen uniformly from [TeX:] $$\left(0,1, \cdots, w_s\right)$$, where [TeX:] $$w_s=2^s w_0, w_0$$ is the minimum contention window, and s is the number of previous failed back-off stage. We assume that the number of back-offs can be infinite (i.e., [TeX:] $$s=0,1, \cdots$$). The initial back-off time t of a sensor node is recorded by its backoff counter, which would be reduced by one in each slot if all other sensor nodes are silent. Otherwise, it remains unchanged. When the back-off counter reaches zero, a sensor node has the opportunity to transmit its head-of-line packet. If the transmission is successful, the sensor node could start the back-off process of a new data packet by resetting its backoff stage s to zero and resetting its back-off counter randomly between zero and [TeX:] $$w_0-1$$. If a collision occurs, the sensor node enters the next back-off stage by doubling the contention window and initializing the back-off counter. We refer to the number of previous failed back-offs and the back-off counter of a sensor node as its state, which is denoted as (s, t).

In a slotted ALOHA based network, to reduce the randomness of sensor nodes transmitting their data packets, and sensor nodes must wait until the next slot before they can start delivering their data packets. In particular, every data packet would be transmitted with the same transmission probability in each slot. If any collisions occur, the data packet would be retransmitted with probability in the next slot, until the transmission is successful.

In this paper, both the CSMA and ALOHA protocols that we consider are slotted protocols. For the CSMA protocol, a node attempts to transmit its packet when its back-off counter reduces to zero. In case a collision occurs, the node needs to perform a new round of back-off process (cf. Section III-A). For the slotted ALOHA protocol, each node delivers its packet with a certain probability and retransmits the packet with the same probability when a collision occurs.

We evaluate the timeliness of the network by the AoI. To be specific, the AoI is defined as the difference between the current time m and the generation time [TeX:] $$U_n(m)$$ of the latest successfully transmitted packet at sensor node n. Mathematically, the AoI is expressed as

Fig. 2 describes a sample AoI path [TeX:] $$\Delta(m)$$ of a certain sensor node n. We denote the generation (arrival) time of the kth packet status update of the sensor node as [TeX:] $$m_k(k=1,2, \cdots)$$ and the time when the remote receiver receives the k-th packet of a sensor node n as [TeX:] $$m_k^{\prime}$$. Then the inter-arrival time of the packets can be expressed as [TeX:] $$X_k=m_k-m_{k-1}$$ and the system time of kth packet is [TeX:] $$T_k=m_k-m_k^{\prime}$$. The waiting time and the service time of packet k are denoted, respectively, as [TeX:] $$W_k$$ and [TeX:] $$S_k$$. It is noted that the system time [TeX:] $$T_k$$ of packet k is the sum of the waiting time [TeX:] $$W_k$$ and the service time [TeX:] $$S_k$$. Thus we have

Without loss of generality, it is supposed that the system is observed from m = 0. At this moment, the queues are empty and the AoI at the remote receiver is [TeX:] $$\Delta_0$$. Between time [TeX:] $$m_{k-1}^{\prime}$$ and time [TeX:] $$m_k^{\prime}$$, the AoI is increased by one since the remote receiver does not receive a new data packet from sensor node n. Once the remote receiver receives an update (a data packet) from a sensor node n, the AoI of the sensor node is reset to a lower value which is equal to the latency experienced by the data packet across the transmission system.

We assume that the packet arrival process and the age process [TeX:] $$\Delta(m)$$ are ergodic. Thus, we know that the sample average AoI converges to its statistical average. During a period of M slots, we assume that K packets are successfully received by the remote receiver. Then the average AoI, in the period, can be expressed as

To calculate this average, the area [TeX:] $$\Delta(m)$$ shown in Fig. 2 is divided into a sequence of triangle-like areas [TeX:] $$A_0, A_1, A_2, \cdots,$$ and the triangle-like area with width [TeX:] $$T_K.$$ As M approaches infinity, the average AoI can be expressed as

III. TRANSMISSION BEHAVIOR AND AVERAGE AOI OF CSMA/CA AND SLOTTED ALOHA BASED NETWORKS

In this section, we first develop an equivalent transmission model for the network using the slotted CSMA/CA protocol. Based on the newly developed model, we derive the transmission probability, the collision probability, and the service rate of the sensor nodes. Likewise, in the slotted ALOHA based network, we also analyze the transmission probability, the collision probability, and the service rate of the sensor nodes. After that, the maximum arrival rate and the number of sensor nodes allowed by the network are calculated. Finally, we derive the average AoI of the CSMA/CA based network and the slotted ALOHA based network explicitly.

A. Equivalent Transmission Model of the CSMA/CA Network

Since the transmission behavior of the CSMA/CA protocol is quite complex, we shall establish an equivalent and universal transmission model to facilitate the analysis of the transmitting process.

Motivated by the approximation method proposed by G. Bianchi in [11], we assume that for each transmission, the collision probability [TeX:] $$p_{\mathrm{cl}}$$ is identical and independent among sensor nodes, regardless of the number of retransmissions experienced. In each slot, every sensor node having a non-empty buffer transmits its data packets with transmission probability [TeX:] $$p_{\mathrm{tx}}$$, which is also identical and independent, regardless of its back-off state. For every sensor node, therefore, [TeX:] $$p_{\mathrm{cl}}$$ is the probability that the transmission of a sensor node collides with some other sensor nodes; [TeX:] $$p_{\mathrm{tx}}$$ is the probability that the backoff counter of the sensor node reduces to zero and attempts to transmit a data packet.

We refer to the number s of failed back-offs, the back-off counter t of a sensor node, the number c of packets in the cache as the state of the sensor node, and thus model the threedimensional process (s, t, c) as a discrete-time Markov chain. In addition, we assume that the number of back-off stages can be infinite. Unlike the research of in [11], however, we shall investigate the network in the non-saturated case in this paper. That is, the buffer of all sensor nodes is not always non-empty, and thus is more meaningful for systems with strict timeliness requirements. In particular, we say a sensor node is in the idle state (-1,-1, 0) if its buffer is empty, i.e., c = 0.

The three-dimensional state (s, t, c) transition diagram of the discrete-time Markov chain is shown in Fig. 3, in which Fig. 3(a) describes the state transitions when the buffer length is c = k 1 is not changed by a step of transition. Fig. 3(b) describes possible transitions between neighboring layers, i.e., the buffer length is increased or decreased by one. In particular, the non-zero one-step transition probabilities of the kth layer corresponding to Fig. 3(a) are given by:

in which p is the data packet generation rate of each sensor node, [TeX:] $$i=0,1, \cdots, j \in\left(1, w_i-1\right), \text { and } k \geq 1.$$

In (5), the first equation and the second equation account for the situations that no data packet is generated. In this case, the back-off counter will be frozen if a collision is detected and will be decremented by one if no collision occurs, respectively. The third equation models situations when the back-off counter returns to zero. To be specific, if a sensor node transmits its data packet without any collisions (the data packet is removed from the buffer) and generates a new data packet in the slot (the new data packet is pushed into the buffer), the sensor node will start a new back-off process in the same layer. Finally, the fourth equation models the situation that the sensor node will go to the next back-off stage i+1 in the same layer and initial the back-off counter value (which is chosen between zero and [TeX:] $$w_{i+1}-1$$), if a collision is detected at the ith back-off stage and no data packet arrives.

When the number c of data packets in the buffer changes, the state transition diagram of the discrete-time Markov chain is shown in Fig. 3(b) and the non-zero transition probabilities are as follows:

The first equation in (6) accounts for the situation that when the buffer is empty and no data packet is generated in the slot. The second equation characterizes the case that the sensor node generates a data packet and will transit to the zeroth back-off stage by randomly initializing the backoff counter. The third equation describes the case when the sensor node successfully delivers its only (k = 1) data packet, and no new data packet arrives. Likewise, the fourth equation of (6) accounts for the situation that when the sensor node successfully transmits its head-of-line packet (k 2) and no new data packet arrives. In this case, the back-off process of the followed data packet restarts from the next layer. The fifth equation characterizes the case when the back-off counter at the ith back-off stage of the kth layer returns to zero and a collision is sensed, simultaneously, the sensor node gets a new data packet. Thus, the state will be transferred to the next back-off stage i+1 of the k +1th layer. Finally, as shown in the sixth equation and the seventh equation of (6), the backoff counter is non-zero and the sensor node gets a new data packet.

We represent the stationary distribution of the Markov chain as [TeX:] $$b_{i, j, k}=\lim _{m \rightarrow \infty} \operatorname{Pr}\{(s, t, c)=(i, j, k)\}.$$ We also denote [TeX:] $$b_{i, j, *}=\sum_{k=1}^{\infty} b_{i, j, k}.$$ In the stationary state, for each sensor node, the state update rate (i.e., the rate of packet generation) is p, and we further represent the service rate of the network using the CSMA/CA protocol as [TeX:] $$\mu_{\mathrm{CA}}$$. In particular, the stationary distribution b is explicitly given in the following proposition.

Proposition 1. Given the packet rate p and the collision probability [TeX:] $$p_{\mathrm{cl}}$$, the stationary distribution of the three-dimensional Markov chain can be expressed as

in which [TeX:] $$i \geq 1,0 \leq j \leq w_i-1$$, and [TeX:] $$w_i=2^i w_0$$. Moreover, the idle probability of the sensor nodes is given by

Proof. Since all the states are connected and the Markov chain is irreducible, the Markov chain has an unique stationary distribution. More details are shown in Appendix A.

According to the stationary distribution of the Markov chain acquired in Proposition 1, we can get the transmission probability [TeX:] $$p_{\mathrm{tx}}$$ and the collision probability [TeX:] $$p_{\mathrm{cl}}$$ of the sensor nodes, as shown in the following theorem.

Theorem 1. Given the packet rate p and the stationary distribution b of the Markov chain, the transmission probability [TeX:] $$p_{\mathrm{tx}}$$ and the collision probability [TeX:] $$p_{\mathrm{cl}}$$ of the sensor nodes in the network satisfies

in which N is the number of sensor nodes.

Proof. Note that a sensor node attempts to transmit its data packets every time when its back-off counter value is equal to zero. Therefore, the transmission probability [TeX:] $$p_{\mathrm{tx}}$$ is the total probability that the sensor node is in state (i,0,k), in which all i 0, k 1. The collision probability [TeX:] $$p_{\mathrm{cl}}$$ is the conditional probability that when a certain sensor node attempts to transmit its data packets, while at least having an interfering node transmits its data packets. Please refer to Appendix B for a detailed proof.

According to (12) and (13), we further have the following expression about the collision probability [TeX:] $$p_{\mathrm{cl}}$$

Since (14) is a nonlinear equation, we solve the collision probability [TeX:] $$p_{\mathrm{cl}}$$ with Newton’s iteration method by iteratively using [TeX:] $$p_{\mathrm{cl}}=p_{\mathrm{cl}}-f\left(p_{\mathrm{cl}}\right) / f^{\prime}\left(p_{\mathrm{cl}}\right)$$, starting from an initial value close to zero. The algorithm is shown in Algorithm 1. The proof of convergence of Newton’s iterative method can be found in [32, Chap. 7.4]. From Algorithm 1, we can obtain the collision probability [TeX:] $$p_{\mathrm{cl}}$$. The transmission probability [TeX:] $$p_{\mathrm{tx}}$$ and the idle probability [TeX:] $$p_{\text {idle }}$$ can also be acquired by using (12) and (11), respectively.

It is worth noting that a sensor node can transmit the data packet successfully in each slot only if the node gets the chance to use the channel and no collision occurs. Therefore, the probability of a sensor node successfully delivering a data packet in each slot can be expressed as

Accordingly, we can obtain the service rate of a sensor node of the network using the CSMA/CA protocol as follows

We denote the time at which a sensor node successfully transmits a data packet as the service time [TeX:] $$S_k$$ and model the service time [TeX:] $$S_k$$ as a geometric distribution with parameter [TeX:] $$\mu_{\mathrm{CA}}$$. That is,

Further, the average service time can be represented as

Equation (17) can be interpreted as follows. In each slot of the transmission, the service would be completed with probability [TeX:] $$\mu_{\mathrm{CA}}$$ at the end of that slot and would be continued in the next slot with probability [TeX:] $$1 - \mu_{\mathrm{CA}}$$.

Remark 1. Under the condition that the packet rate approaches the service rate, i.e., [TeX:] $$p \rightarrow \mu_{\mathrm{CA}},$$ we have [TeX:] $$p_{\text {idle }} \rightarrow 0$$ from (16).

Given the number N of sensor nodes, for each stable buffer, the packet rate must satisfy [TeX:] $$p\lt \mu_{\mathrm{CA}}.$$ Since [TeX:] $$\mu_{\mathrm{CA}}$$ is in fact a function of p, we can find the maximum achievable packet rate [TeX:] $$p_{\max }$$ in the process [TeX:] $$p \rightarrow \mu_{\mathrm{CA}},$$, for which we have [TeX:] $$p_{\text {idle }} = 0$$ from (16). From the expression (11) of [TeX:] $$p_{\text {idle }}$$ and by combining (13) to (11), we have

in which [TeX:] $$p_{\mathrm{cl}}=1-\left(1-p_{\mathrm{tx}}\right)^{N-1}$$ In particular, we can solve [TeX:] $$p_{\mathrm{tx}}$$ from (19) by using some mathematical tools (e.g., Matlab). We denote the real solution of [TeX:] $$p_{\mathrm{tx}}$$ ins denoted as [TeX:] $$\overline{p_{\mathrm{tx}}}$$ and know that [TeX:] $$\overline{p_{\mathrm{tx}}}$$ is the maximum transmission probability. By substituting (13) into (12) and replacing [TeX:] $$p_{\mathrm{tx}}$$ with [TeX:] $$\overline{p_{\mathrm{tx}}}$$, the maximum packet rate can be expressed as

Likewise, for a fixed packet rate and a varying N, the idle probability [TeX:] $$p_{\text {idle }}$$ also approaches zero as N approaches the maximum available number [TeX:] $$N_{\max }$$ of the system. Thus, we have

By expressing [TeX:] $$p_{\mathrm{tx}}$$ in terms of [TeX:] $$p_{\mathrm{cl}}$$ (cf. (13)) and solving [TeX:] $$p_{\mathrm{cl}}$$ from (21) (denoting the real solution of [TeX:] $$p_{\mathrm{cl}}$$ [TeX:] $$\overline{p_{\mathrm{cl}}}$$), [TeX:] $$N_{\max }$$ can be then expressed as

in which [TeX:] $$\lfloor x\rfloor$$ represents the largest integer not exceeding [TeX:] $$x$$.

B. Transmissions of the Slotted ALOHA Based Network

In the slotted ALOHA based network, we refer to a certain sensor node arbitrarily selected from the N sensor nodes as the reference node while referring to the remaining N − 1 sensor nodes except the reference node as the other nodes.

To evaluate the interference of the other nodes on the reference node, we need to know the busy probability [TeX:] $$p_{\text {bsy }}$$ of the other nodes. Specifically, a sensor node is said to be in the busy state if its buffer is not empty and in the idle state otherwise. Thus, the idle probability [TeX:] $$p_{\text {idl }}$$ and the busy probability [TeX:] $$p_{\text {bsy }}$$ of a sensor node satisfies [TeX:] $$p_{\mathrm{idl}}+p_{\mathrm{bsy}}=1.$$

It is clear that an idle sensor node will not crowd the channel. Only when a sensor node is in busy state, the sensor node would compete for the channel. The busy probability [TeX:] $$p_{\text {bsy }}$$ and (re)transmission probability of a sensor node, therefore, have a decisive effect on crowdedness of the channel.

When the reference node performs a data packet transmission in a given slot, the probability [TeX:] $$p_{\mathrm{s}}$$ of successful transmission can be expressed as

in which [TeX:] $$p_{\mathrm{tx}}=\lambda p_{\mathrm{bsy}}$$ is the provavility that there is a data packet(s) in the buffer of the other nodes and the head-ofline data packet is transmitted with probability . When the reference node decides to deliver a data packet in the current slot, a collision occurs as long as one or more of the other nodes attempt to transmit their data packets.

According to (23), therefore, the collision probability [TeX:] $$p_{\mathrm{cl}}$$ can be expressed as

Specifically, [TeX:] $$1-p_{\mathrm{tx}}$$ is the probability that one of the other node has a data packet(s) but does not attempt to transmit a data packet and [TeX:] $$\left(1-p_{\mathrm{tx}}\right)^{N-1}$$ is the probability that none of the other N−1 nodes are transmitting. Thus, [TeX:] $$1-\left(1-p_{\mathrm{tx}}\right)^{N-1}$$ is the probability that at least one of the other N − 1 nodes try to transmit its data packet and collides with the reference node.

In each slot, every busy node would transmit their data packets with probability . The node could successfully deliver its update only if the node obtains the right to use the channel and there is no collision. Therefore, the probability of successful transmission can be expressed as

which is referred to as the service rate of the slotted ALOHA based network.

We denote the time for the reference node to successfully deliver an update k as [TeX:] $$S_k.$$ It is clear that the service time [TeX:] $$S_k$$ is a geometrically distributed random variable with parameter [TeX:] $$\mu_{\mathrm{SA}}$$. Therefore, the probability distribution of the service time and the average service time can be, respectively, written as

To solve the unknown variable [TeX:] $$p_{\text {bsy }}$$, we shall model the buffer state (i.e., the number of data packets in the buffer) of the reference node as a discrete-time Markov chain of which the state transition diagram is shown in Fig. 4.

Further, the steady-state probability distribution of the discrete-time Markov chain is given by the following proposition.

Proposition 2. The steady-state probability for the buffer state of the reference node being empty is given by

Proof. See Appendix C.

Note that [TeX:] $$p_{\text {idl }}$$ is the probability that the buffer of the reference node is empty. Based on the Proposition 2, we have

Further, by combining [TeX:] $$p_{\mathrm{idl}}+p_{\text {bsy }}=1$$ with (29), we have

By substituting (30) into (25), we have the following equation on the busy probability [TeX:] $$p_{\text {bsy }}$$

We employ Newton’s iteration method with [TeX:] $$p_{\text {bsy }}=p_{\text {bsy }}-f\left(p_{\text {bsy }}\right) / f^{\prime}\left(p_{\text {bsy }}\right)$$ and an initial value [TeX:] $$p_{\text {bsy }}^{(0)}$$ to solve the numerical solution of the busy probability [TeX:] $$p_{\text {bsy }}$$. We can find a detailed proof of the convergence of Newton’s iteration method in [32, Chap. 7.4]. The numerical solution of the busy probability [TeX:] $$p_{\text {bsy }}$$ is shown in Algorithm 2. Moreover, we can obtain the update service rate [TeX:] $$\mu_{\mathrm{SA}}$$ and the collision probability [TeX:] $$p_{\mathrm{cl}}$$ by (25) and (24), respectively.

Remark 2. In order to obtain the maximum data packet rate [TeX:] $$p_{\max }$$ and the maximum allowable number of sensor nodes [TeX:] $$N_{\max }$$ in the slotted ALOHA based network, we set the data packet rate to be close to the service rate (i.e., [TeX:] $$p \rightarrow \mu_{\mathrm{SA}}$$) for a fixed (re)transmission probability of each sensor node. In this cases, we have [TeX:] $$p_{\text {bsy }} \rightarrow 1(\text {cf. (30)) }.$$ For each stable buffer, the packet rate must satisfy [TeX:] $$p\lt\mu_{\mathrm{SA}} .$$

Given the number N of sensor nodes, by combining (25), we can get approximately the maximum packet rate as follows:

Given the packet rate p, according to (25), the maximum allowable number of sensor nodes can be expressed by

in which [TeX:] $$\lfloor x\rfloor$$ denotes the largest integer that is not greater than [TeX:] $$x$$

C. Average AoI of the Networks

For each node, we note that the arrival of data packets follows the Bernoulli process with the parameter p and the service time [TeX:] $$S_k$$ obeys the geometric distribution with the parameter [TeX:] $$\mu .$$ Thus, the transmission process of each node can be modeled by a Geom/Geom/1 queue. Moreover, we model the queuing process as a late-arriving system with delayed access. Under this model, the probability generating function (PGF) of the system time [TeX:] $$T_k$$ of a packet is given by the following lemma.

Lemma 1. For a given the data packet arrival rate p, the PGF of the system time [TeX:] $$T_k$$ is given by

in which

Proof. A detailed proof of the probability generation function of the system time [TeX:] $$T_k$$ of the Geom/Geom/1 queuing model can be found in [33, Chap. 3.1.2].

Equation (34) shows that the system time [TeX:] $$T_k$$ obeys the geometric distribution of parameter . Thus, the probability distribution of the system time and the average system time of data packets are expressed, respectively, as

Based on this Geom/Geom/1 queuing model, the average AoI of the network can be obtained, which is given by the following theorem.

Theorem 2. Given the generation rate p of data packets, the average AoI of the network is given as follows:

Proof. See Appendix D.

From Theorem 2, we can obtain the average AoIs of the two networks using the CSMA/CA protocol and the slotted ALOHA protocol, in which the service rate [TeX:] $$\mu$$ are given, respectively, by (16) and (25).

In the following, we study two extreme cases of the network using two random multiple access strategies and obtain the subsequent results.

First, as the generation rate of data packets approaches zero (i.e., [TeX:] $$p \rightarrow 0$$), according to (39), it is clear that the average AoIs of the network goes to infinity.

In this situation, due to the sparse arrival of data packets, the shared channel is rarely occupied by transmissions and the inter-arrival time would be large. Therefore, in most circumstances, the data packets received by the remote receiver are not fresh.

Second, when the packet generation rate reaches the maximum allowable packet rate (i.e., [TeX:] $$p \rightarrow p_{\max },$$ at this time, [TeX:] $$p_{\max } \rightarrow \mu$$), it is seen from (39) that the average AoIs of the network also is infinity.

In this situation, since the high packet arrival rate leads to frequent collisions occurring, the shared channel is always congested. Therefore, the service time of the data packet may be arbitrarily long, making the average AoIs infinite.

IV. SIMULATION RESULTS

In this section, we investigate the average AoI of the networks via the numerical and the Monte Carlo simulation results. We set the minimum competition window as [TeX:] $$w_0=8.$$ We assume that both the networks using the CSMA/CA and slotted ALOHA protocols are homogeneous. That means that the packet rates of all the nodes are the same. For the fairness of comparison, we also ensure that the transmission probability [TeX:] $$p_{\mathrm{tx}}$$ of the network employing the CSMA/CA protocol and the slotted ALOHA protocol are equal, which can be realized by adjusting the (re)transmission probability .

First, we observe from Figs. 5(a) and 5(b) that the transmission probabilities [TeX:] $$p_{\mathrm{tx}}$$ of the networks using the CSMA/CA protocol is increasing with both the packet rate p and the number N of nodes. This is because the increase in packet rate p leads to a larger probability of non-empty buffer, which further leads to a larger transmission probability [TeX:] $$p_{\mathrm{tx}}$$. Likewise, an increase in the number of nodes leads to more attempts of transmitting and thus a larger transmission probability [TeX:] $$p_{\mathrm{tx}}$$. It is also observed in Fig. 5(a) and Fig. 5(b) that the Monte Carlo simulation (MC) results match our theoretical results (TH) very well.

It is observed from Fig. 6(a) and Fig. 6(b) that the collision probability [TeX:] $$p_{\mathrm{cl}}$$ of the networks using the CSMA/CA protocol increases with the packet rate p and the number N of nodes. This is because as the packet rate and the number N of nodes increases, there will be more contentions in the transmissions. Moreover, according to the derivations, we also find that with packet rate and the number of nodes increase both transmission and collision probabilities increase in polynomial with an order of three.

In Fig. 7(a), we show how the average AoIs of the CSMA/CA and slotted ALOHA based networks varies with the packet rate p, in which the number of sensor nodes is set to N = 20. First, we observe that as the packet rate p increases, the average AoI is decreasing first and then increasing. When the packet rate p is relatively small or large, the average AoIs are quite large. This is because the waiting time for the new updates are large when the packet rate is small while collisions occur more frequently and thus the service time is larger when the packet rate is large. Second, for the CSMA/CA based network, the average AoI reaches the minimum when the packet rate p is close to 0.014; in the slotted ALOHA based network, the average AoI is minimized when the packet rate p is close to 0.011. With the increase in packet rate p, the CSMA/CA based network performs better than the slotted ALOHA based network. Third, we observe that the Monte Carlo simulation results and theoretical results of the slotted ALOHA based network match well while the Monte Carlo simulation results and theoretical results of the CSMA/CA based network slightly diverges when p > 0.013. For the CSMA/CA protocol, the mismatch between analysis and simulation is because the distribution of the real service time deviates from the geometric distribution as the packet rate and the number of nodes increase.

Fig. 7(b) presents how the average AoIs of the networks change with the number N of the sensor node when the packet rate is set to p = 0.01. As is shown, the average AoI is increasing with the number N of the sensor nodes. This is because as the population of nodes grows, the frequency of collisions becomes larger, and the service time would also be longer. In particular, the change in the average AoI of the CSMA/CA based network is relatively flat compared to the change in the average AoI of the slotted ALOHA based network. We also observe that the performance of the CSMA/CA based network is better than the slotted ALOHA based network as the number N of sensor nodes is increased. Moreover, it is seen from Fig. 7(b) that the Monte Carlo simulation results of the slotted ALOHA based network match well with the theoretical results, while the Monte Carlo simulation results of the CSMA/CA based network deviate slightly from the theoretical results when N > 24.

From Figs. 7(a) and 7(b), we also see that the average AoI of the CSMA/CA based network is always smaller than that of the slotted ALOHA based network, regardless of the packet rate p and the number N of nodes. Note that for comparison fairness, the attempt probability of the slotted ALOHA protocol is chosen in such a way that the transmission probabilities of the two scheme are equal for given the packet rate p. For example, we have = 0.03 when the number of sensor nodes is set to N = 20; we have = 0.0186 when the packet rate is set to p = 0.01. From (13) and (24), it is clear that the collision probabilities [TeX:] $$p_{\mathrm{cl}}$$ of the two networks using the CSMA/CA protocol and the slotted ALOHA protocol are equal when their transmission probabilities [TeX:] $$p_{\mathrm{tx}}$$ are the same. According to Theorem 2, we can see that the average AoI of the network is related to the packet rate p and the service rate [TeX:] $$\mu .$$ For a given same packet rate p case, it is the service rate that determines the average AoI of the network. Therefore, the difference in network performance by using the CSMA/CA protocol and the slotted ALOHA protocol AoI comes from their different service rates. We observe from Fig. 8 that the service rate of the network using the CSMA/CA protocol is always much larger than that of the slotted ALOHA protocol. From Fig. 8 and Theorem 2, the difference in AoI performance when the network uses these two protocols can be explained. This suggests that CSMA/CA is superior to slotted ALOHA and maybe is the most promising mode in the design of WSN systems.

In addition, we investigate how the average AoI varies with packet rate p in the finite buffer and finite retransmission cases (for CSMA, i.e., the maximum number of back-off stages) through Monte Carlo simulations, in which the buffer size is set to 30 packets, the number of retransmission is set to 8, and we use ‘finite’ to denote finite buffers and retransmission. It is observed from Fig. 7(a) that the average AoI with packet rate p for the finite buffer and retransmission cases remains consistent with that for the infinite buffer and retransmission cases. That is, a 30 packets buffer and 8 retransmissions are enough for the network.

In practical wireless sensor networks, since the data packet generation rates of the sensor nodes are not necessarily the same, we also study the performance of heterogeneous networks by Monte Carlo simulations. That is, the packet rates of the nodes are different from each other. In particular, the packet rates of the nodes are randomly chosen in a finite range [TeX:] $$\left[0,2 p_{\max }\right]$$ while ensuring their average is equal to the packet rate p of the corresponding homogeneous network. From Figs. 5(b), 6(b) and 7(b), the changes in transmission probability [TeX:] $$p_{\mathrm{tx}}$$, [TeX:] $$p_{\mathrm{tx}}$$ the collision probability [TeX:] $$p_{\mathrm{cl}}$$, and the average AoIs are with similar modes to the corresponding homogeneous networks.

V. CONCLUSION

In this paper, we investigated the timeliness of two wireless sensor networks using the CSMA/CA protocol and the slotted ALOHA protocol. We showed that the average AoI would be larger when the packet rate is small or relatively large. With the same transmission probability, the average AoI of the network employing the CSMA/CA protocol is always smaller than that one using the slotted ALOHA protocol, irrespective of the packet rate and the growth in the number of nodes. In addition, we also found that the effects of variation of the transmission probability [TeX:] $$p_{\mathrm{tx}}$$, the collision probability [TeX:] $$p_{\mathrm{cl}}$$, and the average AoIs of the heterogeneous networks are basically similar to that in the homogeneous networks. It is noted that the limitation of methods developed in this paper assumes that each update takes one slot. In future work, we shall consider where multiple slots are required for each update and there exist some hidden nodes.

APPENDIX

A. Proof of Proposition 1

Proof. First, for a given data packet arrival rate [TeX:] $$p\lt\mu_{\mathrm{CA}},$$ it is clear that each data packet in the node buffer will be successfully delivered within a certain period. Especially, in the zeroth back-off stage, the back-off counter will definitely return to zero eventually and stay at state (0, 0, k) for some k 1 for exactly one slot. Therefore, we have [TeX:] $$b_{0,0, *}=p.$$

Second, a state will transfer from the [TeX:] $${0,0, *}$$ to the (i+1)th back-off stage if a collision occurs in the current slot. In this case, the state returns to and stays at state (i+1, 0) for exactly one slot, and thus we have

in which i 0. Further, we have

in which i 0. In fact, we are able to use the dynamic equilibrium property of the stationary Markov chains to prove the (40). To this end, we shall divide the state space into two parts: The states [TeX:] $$\left(i^{\prime}, j, k\right) \text { with } i^{\prime} \leq i$$ and the states [TeX:] $$\left(i^{\prime \prime}, j, k\right) \text { with } i^{\prime \prime} \geq i$$. Since the total transiting probability from the left part to right part is equal to the total transiting probability from the right part to the left part, thus we have

which yields

By combining (41) with (42), (39) can be obtained readily.

We denote the initial back-off counter of the i-th back-off stage as J and have

in which [TeX:] $$0 \leq j \leq w_i-1.$$ We know that a node has a opportunity to stay at state [TeX:] $$(i, j, *)$$ only if the initial backoff counter J is no less than j. As the back-off counter has been decreased to j, the expected sojourn time at the state would be

Afterwards, the state eventually transits to the state [TeX:] $$(i, 0, *)$$ and stay for exactly one slot. Therefore, the stationary probability for the node to be in state [TeX:] $$(i, j, *)$$ can be expressed as

in which [TeX:] $$i \geq 0,0 \leq j \leq w_i-1,$$ and we use (39). Moreover, we also can apply the dynamic equilibrium equation to the Markov chain to prove (45).

Finally, by the normalized condition of the stationary distribution, we have

This completes the proof of the Proposition 1.

B. Proof of Theorem 1

Proof. Based on Proposition 1 and the fact that every attempted transmission occurs when the back-off counter is zero, the transmission probability [TeX:] $$p_{\mathrm{tx}}$$ can be expressed as

It is seen from (47) that the transmission probability [TeX:] $$p_{\mathrm{tx}}$$ depends on the collision probability [TeX:] $$p_{\mathrm{cl}}$$, which is also unknown. To address the unknown collision probability, it is worth noting that the collision probability refers to the probability that at least one of the remaining N − 1 nodes in the same slot will interfere. Consequently, the collision probability [TeX:] $$p_{\mathrm{cl}}$$ can be expressed by the transmission probability [TeX:] $$p_{\mathrm{tx}}$$,

in which, [TeX:] $$p_{\mathrm{tx}}$$ is the transmission probability of the data packets, [TeX:] $$\left(1-p_{\mathrm{tx}}\right)$$ is the non-transmission probability of the data packets, [TeX:] $$\left(1-p_{\mathrm{tx}}\right)^{N-1}$$ is the probability that none of the remaining N − 1 nodes transmits, and [TeX:] $$\left(1-\left(1-p_{\mathrm{tx}}\right)^{N-1}\right)$$ is the probability that at least one of the remaining N −1 nodes transmits, i.e., the collision probability [TeX:] $$p_{\mathrm{cl}}$$.

This completes the proof of the Theorem 1.

C. Proof of Proposition 2

Proof. According to the state transition diagram of the discrete-time Markov chain given in Fig. 4, when the steadystate is reached, the transfer in is equal to the transfer out, we have the following balance equations

in which, [TeX:] $$\bar{p}=1-p, \overline{\mu_{\mathrm{SA}}}=1-\mu_{\mathrm{SA}}.$$ It is assumed that [TeX:] $$b_0$$ is a undetermined constant.

From (49), we further obtain

Thus, it is concluded that

Moreover, we know that the sum of total probabilities is equal to one, i.e.,

By substituting (53) into (55), we have

In order to maintain the stability of the system, the rate of the packets generation must be no longer than the mean service rate, i.e., [TeX:] $$p\lt \mu_{\mathrm{SA}}$$. Thus, we have

According to (56) and (57), [TeX:] $$b_0$$ can be expressed by the following expression

in which [TeX:] $$b_0$$ is the probability that the buffer is empty.

Thus, the proof of Proposition 2 has been accomplished.

D. Proof of Theorem 2

Proof. Since as M approaches infinity, [TeX:] $$A_0 \text { and } T_k\left(T_k+1\right) / 2$$ are finite with respect to [TeX:] $$\sum_{k=1}^{K-1} A_k, A_0 \text { and } T_k\left(T_k+1\right) / 2$$ could be neglected. Therefore, the average AoI (cf. (4)) could be rewritten as

in which [TeX:] $$p=\lim _{M \rightarrow \infty} K / M$$ is the rate of node state update generation (packet arrival rate) and [TeX:] $$\mathbb{E}[\cdot]$$ is the expectation operator. In addition, we could use the inter-arrival time [TeX:] $$X_k$$ and the system time [TeX:] $$T_k$$ to represent the average area of [TeX:] $$A_k$$, as shown in the following expression.

Since the generation of packets (the arrivals of packets) is a Bernoulli process with rate p, the probability distribution of the inter-arrival time [TeX:] $$X_k$$ of a packet would be [TeX:] $$\operatorname{Pr}\left\{X_k=j\right\}=p(1-p)^{j-1}, j=1,2, \cdots .$$ Therefore, the first and second moments of the inter-arrival time [TeX:] $$X_k$$ of a packet are given, respectively, by

Note that in (60), the only part is [TeX:] $$\mathbb{E}\left[X_k T_k\right]$$ unknown. Furthermore, when the kth update arrives, the waiting time [TeX:] $$W_k$$ is equal to zero if the k − 1 update has completed the service, and it is [TeX:] $$T_{k-1}-X_k$$ if the k−1 update is being served or waiting. Therefore, we have [TeX:] $$W_k=\max \left(T_{k-1}-X_k\right) .$$ Because the inter-arrival time [TeX:] $$X_k$$ and the service time [TeX:] $$S_k$$ are independent of one another while the inter-arrival time [TeX:] $$X_k$$ and the waiting time [TeX:] $$W_k$$ are related with each other, [TeX:] $$\mathbb{E}\left[X_k T_k\right]$$ could be written as (cf. (2))

In order to obtain [TeX:] $$\mathbb{E}\left[X_k W_k\right]$$, we introduce the auxiliary function H (z) as follows (cf. [34])

where

Moreover, [TeX:] $$\mathbb{E}\left[X_k W_k\right]$$ can be represented as

By replacing in (66) with (35), we further have

According to (59) to (63) and (67), the average AoI can be expressed as

Thus, the proof of Theorem 2 has been completed.