Wireless Sensor Network
Vol.4 No.2(2012), Article ID:17345,7 pages DOI:10.4236/wsn.2012.42007

Priority-Based CCA Periods for Efficient and Reliable Communications in Wireless Sensor Networks

Mounib Khanafer, Mouhcine Guennoun, Hussein T. Mouftah

School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada

Email: {khanafer, mouftah}@site.uottawa.ca, mguennou@uottawa.ca

Received November 9, 2011; revised December 16, 2011; accepted January 22, 2012

Keywords: Wireless Sensor Networks; Beacon-Enabled IEEE 802.15.4; Binary Exponent Backoff; Priority-Based Backoff; Fairness; Power Consumption; Reliability; Channel Utilization

ABSTRACT

The IEEE 802.15.4 standard utilizes the CSMA-CA mechanism to control nodes’ access to the shared wireless communication medium. CSMA-CA implements the Binary Exponential Backoff (BEB) algorithm by which a node refrains from sending any packet before the expiry of its backoff period. After that, the node is required to sense the medium for two successive time slots to assert that the medium is clear from any ongoing transmissions (this is referred to as Clear Channel Assessment (CCA)). Upon finding the medium busy, the node doubles its backoff period and repeats that process. While effective in reducing the likelihood of collisions, this approach takes no measures to preserve the priorities among the nodes contending to access the medium. In this paper we propose the Priority-Based BEB (PB-BEB) algorithm in which we enhance BEB such that nodes’ priority is preserved. We provide a simulation study to examine the performance of PB-BEB. Our simulations show that the latter not only outperforms BEB in terms of fairness, but also show promising results in terms other parameters like channel utilization, reliability, and power conservation.

1. Introduction

The specifications of the IEEE 802.15.4 standard [1] describe both the physical and MAC layers for low-rate wireless personal area networks (LR-WPANs). These specifications fit the distinguished characteristics of Wireless Sensor Networks (WSNs), which work under stringent conditions like the scarce power resources and the hostile environment of deployment. The MAC layer of the IEEE 802.15.4 standard utilizes the Carrier Sense Multiple Access with Collision Avoidance (CSMA-CA) mechanism to control nodes’ medium access. In this mechanism a node has to follow the Binary Exponent Backoff (BEB) algorithm to assert that the medium is free from ongoing transmissions before commencing its packet transmission. Although effective in reducing the likelihood of packet collisions, BEB does not take any measures to guarantee the priority of access among the nodes. Instead, all the nodes are treated the same and each node receive the same opportunity to access the medium, regardless of how long it has been attempting to gain that access.

The problem of enhancing the MAC protocol of IEEE 802.15.4, such that the priority among the nodes is preserved, has received a considerable attention in the research community. In this paper we propose the Priority-Based BEB, a modified version of BEB that can adaptively prioritize the access to the medium such that nodes are treated more fairly. The rest of this paper is organised as follows. In Section II we provide a general description of the MAC protocol of the IEEE 802.15.4 standard. In Section III we review some of the work related to prioritizing the medium access in IEEE 802.15.4- based WSNs. Section IV describes the new PriorityBased BEB algorithm. Section V presents the simulations we conducted to compare the performance of Priority-Based BEB and BEB. Finally, Section VI concludes this work.

2. Overview of the Beacon-Enabled IEEE 802.15.4

The IEEE 802.15.4 standard supports both the star and peer-to-peer topologies. The star topology requires that communications between any pair of nodes to be relayed through a designated node called the coordinator. In the peer-to-peer topology, however, although the coordinator is available, direct communications between nodes is possible. The MAC layer of the IEEE 802.15.4 may operate in either the beacon-enabled mode or the nonbeacon-enabled mode. In the former, the slotted CSMA-CA mechanism is used to manage the nodes’ access to the medium, while the latter uses the unslotted CSMA-CA mechanism. Our focus in this paper is on the beaconenabled mode. With this mode, a superframe structure is used to manage how the contending nodes can again access to the wireless medium. The structure of the superframe is shown in Figure 1 (redrawn from [1]). The superframe is bounded by two beacons that are periodically sent by the coordinator to synchronize the nodes in the network.

The superframe is constituted by a mandatory active and an optional inactive period. The active period is divided into the Contention Access Period (CAP) and the optional Contention-Free Period (CFP); both are shown in Figure 1. The latter refers to a set of time slots during which guaranteed medium access is offered to certain nodes. These time slots are referred to as guaranteed time slots (GTSs) and are allocated to nodes upon their requests. In this paper we assume that both the inactive period and the CFP are absent from the superframe.

During the CAP, the nodes follow the slotted CSMACA mechanism to gain access to the medium. That is, accessing the medium is governed by the BEB algorithm. According to BEB, a node should backoff for a period of time whenever it has a packet ready for transmission. The backoff period is randomly selected from the interval [0, 2BE-1], where BE is the backoff exponent that ranges from macMinBE (a default value of 3) to macMaxBE (a default value of 5) [1]. Upon the expiry of the backoff period, the node is required to conduct two clear channel assessments (CCAs). The transmission of the packet cannot be started unless the medium is found idle during both CCAs. If either CCA finds the channel busy, the node should backoff again (after increasing BE by 1). The maximum a node is allowed to repeat its backoff, before the packet is discarded, is set to macMaxCSMABackoffs. The latter is an IEEE 802.15.4 attribute that takes a default value of 4 [1]. Once the node asserts that the channel is idle, for two CCAs, the packet is sent. In case a packet collision occurs, the node backs off again and retries to send the packet. The maximum number of transmission retries, before the packet is discarded, is set to macMaxFrameRetries, which is defined by the standard with a default value of 3 [1]. Once the node manages send the packet, it waits for an acknowledgement (ACK) packet.

Figure 1. Superframe structure.

It is clear from the aforementioned description that BEB treats all the nodes similarly without any consideration to the number of times the node has failed to access the medium. Furthermore, the algorithm does not have any guidelines to distinguish the urgency of certain traffics and their need to be granted higher priorities than others.

3. Related Work

Enhancing IEEE 802.15.4 to support priorities among nodes has attracted the attention of research efforts.

Huang et al. proposed the Adaptive GTS Allocation (AGA) scheme to support low latency and fairness [2]. The idea of AGA is to provide an estimate of future GTS needs of the nodes. With that estimate, the coordinator gives higher priority of GTS allocation to needy nodes. AGA operates in a two-phase manner. In the first phase, nodes are classified according to their recent usage of GTSs and then assigned priority numbers (priority decreases as the priority number increases). In the second phase, GTSs are allocated with reference to the priority numbers such that nodes with low priority numbers are considered first. Although AGA shows promising results, over IEEE 802.15.4, in terms of fairness and low latency, the scheme concentrates on improving medium access during the CFP without considering the CAP.

Takaffoli et al. in [3] proposed the GTS-TDMA algorithm which targets the improvement of GTS scheduling to recognize the nodes’ different priority classes. Under GTS-TDMA, nodes do not request GTSs, GTSs are rather allocated to them using a GTS allocation scheme. The network is viewed as a multi-level tree and a TDMA schedule is constructed for it. The schedule is constructed such that maximum data rate is achieved for each node in the network. In other words, the TDMA-GTS algorithm seeks the optimal allocation of GTSs such that each node is provided with the maximum data rate it requires. Simulation results show that TDMA-GTS is capable of achieving almost twice the throughput of CSMA-CA. However, similar to AGA above, this algorithm exploits the GTS capability of IEEE 802.15.4 and does not consider solving the priority problem during the CAP.

Ndih et al. observe that IEEE 802.15.4 offers a priority-independent functionality [4]. This is resulting from having the nodes use the same contention access parameters. Therefore, the authors in [4] develop a Markov-based analytical model for the CAP in which different sets of access parameters are permitted for the nodes with different priority classes. Two priority classes are recognized: high-priority (Class 1) and low-priority (Class 2). A node-state Markov-chain is developed for each priority class, beside a Markov-chain for the channel state. The priorities or service differentiation is based on assigning a contention window of 1 for Class 1 nodes and 2 for Class 2 nodes. Using these settings of the contention window, while maintaining the other backoff parameters at their standard-defined defaults, gives high-priority nodes higher opportunity to access the medium. This is because their small contention window size reduces the duration of their idle channel sensing.

Severino et al. work in differentiating traffic classes within the CAP such that differentiated services are offered to time-critical messages [5]. Their approach is based on the proper tuning of the IEEE 802.15.4 parameters macMinBE, macMaxBE, and CWinit (the initial size of the contention window). The tuning depends on whether the frame is identified as a high-priority or not. Data frames are considered of low priority while command frames, like alarm reports and GTS requests, are considered of high priority. Therefore, nodes use different parameter settings depending on their traffic type. Similar to [4], the settings are chosen such that the backoff periods of high-priority frames are made shorter than those for the low-priority frames. Furthermore, while a queue of different frames is building up, a Priority Queuing is used such that higher-priority frames are selected first for transmission.

Jardosh et al. in [6] propose an explicit priority scheme for IEEE 802.15.4. According to this scheme, nodes are categorized into critical nodes and normal nodes. Critical nodes are the ones that have important information to send to the coordinator while normal nodes that send routine information, which can tolerate some delay. Critical nodes are considered of high-priority while normal nodes are considered of low-priority. The coordinator can learn about this categorization using a secondary beacon. Basically, critical nodes send the coordinator this beacon to indicate their high priority traffic. With that information, the coordinator restricts the contention during the CAP to only those critical nodes. That is, the coordinator includes the priority information in the primary beacon that it periodically broadcasts to all the nodes. Once notified, the normal nodes will refrain from attempting to access the medium during the CAP. This way traffic priority is preserved and critical information is given preference over regular information.

4. The Priority-Based BEB Algorithm

From the description of the IEEE 802.15.4’s MAC layer, we can see that it implicitly recognizes two classes of priority. In particular, the first class is given to the data packets while the second class is given to their associated ACK packets. This can be noticed by observing that CCA1 is firstly needed to avoid any collision with an ongoing data packet transmission. After that, CCA2 is imposed such that the ACK for that packet is transferred successfully. However, this functionality does not consider the number of attempts that certain nodes have been committing to access the medium, but without any success. These nodes are more prone to deplete their power resources at a higher pace without utilizing these resources in useful activities. Different nodes should be treated fairly such that those that experience repeated access failures are given higher priority to access the medium.

In the Priority-Based BEB (PB-BEB) algorithm we propose to extend the BEB algorithm such that the number of CCAs is not confined to only two. Instead, the number of CCAs will be dictated by the level of collisions over the communication medium. In other words, after a node conducts its regular BEB-defined CCAs, it will be required to conduct more CCAs before being able to start its transmission. The total number of CCAs conducted by a node will be determined by the following formula:

(1)

where, Pc is the probability of collision and A is a constant value. The first term in Equation (1) indicates that PB-BEB keeps the two CCAs of BEB without modification. This is required in order preserve the aforementioned functionality of BEB in which the highest priority is assigned to the ACK packet. The second term in Equation (1) indicates that the addition of the extra CCAs will be dependent on the collisions experienced by the packets. That is, we adapt the number of extra CCAs undergone by a node depending on the activities over the wireless channel. Pc is computed as follows:

(2)

where, is the total number of successfully transmitted packets and is the total number of failed packets. The latter refers to packets discarded due to either channel access failure (when exceeding macMaxCSMABackoffs) or transmission failures (when exceeding macMaxFrameRetries). Equation (2) is computed locally at each node. In Equation (1), A is a constant that is set to the value macMaxCSMABackoffs. We use the latter value to indicate that we need the number of extra CCAs to be below the maximum number of backoff stages allowed. In Figure 2 we illustrate the CAA timeslots of our system.

As the node starts conducting its extra CCAs, it may find the medium busy, and therefore, it will backoff again. Once the backoff counter expires, the node will not restart the CCAs from CCA1. Instead, it will continue from exactly the same CCA it stopped at. The only exception of this rule is if the node stopped previously at CCA2. In that case, the node will have to restart from CCA1. Again, this keeps unchanged the original functionality of BEB to give priority to the ACK packet over all other packets. In brief, PB-BEB applies the following formula to find the next CCA the node will conduct:

Figure 2. PB-BEB uses the original CCAs of BEB and adds extra CCAs, the number of which is dynamically changing.

(3)

where, refers to the next CCA to start at and is the last at which the node found the medium busy. The result of imposing Equation (3) is that the node that has been experiencing multiple backoffs while trying to send a packet is given a higher priority to access the medium than those nodes that started their contention at a later time. This means that we are able to integrate a degree of priority into CSMA-CA that has been absent in BEB. In Figure 3 we show the flow diagram of PB-BEB.

5. Simulations

In this section we conduct simulations to compare the performance of PB-BEB and BEB. The performance parameters we concentrate on are fairness, channel utilization, reliability, average power consumption, channel collision time, delay, and channel idle time. Our simulations are run over a C-based simulator that we have developed. The network we study is of a peer-to-peer topology. We list in Table 1 the simulation parameters we use in our performance evaluation (some parameters are adopted from the work of Pollin et al. in [7]).

In Table 1, CCA power is the power consumed while sensing the medium during the clear channel assessment states. The network operates under the beacon-enabled IEEE 802.15.4 with the superstructure constituted by only the CAP. The traffic used is assumed to be both saturated (i.e., nodes has always packets to send). In the following sub-sections we show and discuss the results of our simulations.

5.1. Fairness

Testing the fairness of any backoff algorithm is essential to assert that nodes are getting equal opportunity to access the wireless medium. In measuring the fairness, we depend on Jain’s fairness index [8], which is expressed as follows:

(4)

Figure 3. Flow diagram of PB-BEB.

Table 1. Simulation Parameters.

where, N is the total number of nodes available in the network and xi is the ith node’s share of the medium. A backoff algorithm is deemed fair if it can achieve a fairness index close 1. In Figure 4 we show the fairness index for both PB-BEB and BEB. The graph clearly shows that as the network’s size grows beyond 100 nodes, BEB falls behind PB-BEB in treating the nodes fairly. In fact, we can see that PB-BEB is achieving a significant improvement over BEB. For example, at N = 200, BEB achieves a fairness index of 0.77 while PB-BEB achieves

Figure 4. Fairness of PB-BEB compared to BEB.

a fairness index of 1. This behavior is consistent with other studies that highlighted and proved the short-term unfairness of BEB (see [9] for example).

5.2. Channel Utilization

Channel Utilization (U) is the proportion of time the wireless channel is being used to successfully transmit packets. We define U as follows:

(5)

where, L is the packet length and T is the total duration spent to deliver the packet to its destination. This duration includes the backoff periods, packet transmission time, and the time wasted while retrying (due to experiencing multiple collisions) to send the packet. In Figure 5 we show the performance in terms of U for both BEB and PB-BEB. We can quite observe that PB-BEB is significantly outperforming BEB. At a network size of 100 nodes, for instance, PB-BEB achieves a U of 53.3% while BEB utilizes the channel by as low as 4.3%.

5.3. Reliability

Reliability (R) is the probability of transmitting a packet successfully. Stated differently, R is the probability of not discarding a packet. The latter reflects the fact that nodes may backoff multiple times and/or suffer from multiple collisions before managing to send the packet. An algorithm of high R is one that can reduce the possibility of repetitive backoffs and/or collisions while attempting to send a packet. We illustrate in Figure 6 the performance of PB-BEB and BEB in terms of R. PB-BEB is able to achieve higher R than BEB as the size of the network grows. At a network size of 50 nodes, PB-BEB achieves a reliability of 10% while BEB’s reliability is only 4.4%.

5.4. Average Power Consumption

It is essential to study the power requirements of any algorithm devised for WSNs. This is because of that sensor nodes are battery-powered and we need to be conservative

Figure 5. Channel utilization of PB-BEB compared to BEB.

Figure 6. Reliability of PB-BEB compared to BEB.

in power usage in order to prolong the lifetime of the sensor node, and thus the network. In Figure 7 we show the average power consumption required by PB-BEB and BEB. The graph shows that the performance of both PB-BEB and BEB is generally comparable. Therefore, it is interesting to investigate the activities during which the nodes’ power resources are consumed to see what activities are contributing more to that consumption. In Figure 8 we show the power wasted due to collisions when the network operates under PB-BEB or BEB. It is quite evident that BEB is wasting a large amount of power in collisions. For instance, at a network size of 45 nodes, the average power consumption of BEB is 1.34 W/s (Figure 6). From Figure 7, we observe that 0.38 W/s is wasted due to collisions, which contributes to 28.4% of the average power consumed.  The contribution becomes 30.6% at N = 100. However, under PB-BEB, the power wasted due to collisions contributes to only 10% (at N = 45) and 6% (at N = 100) of the average power consumption.

5.5. Channel Collision Time

Channel Collision Time (TCC) refers to the proportion of time the channel is busy due to collisions. This parameter measures the percentage of time the channel is being utilized in useless activities, and therefore, should be reduced as much as possible. We illustrate the performance in terms of TCC in Figure 9. This figure demonstrates the significant reduction in TCC that PB-BEB can

Figure 7. Average power consumed under PB-BEB compared to BEB.

Figure 8. Power wasted in collisions with PB-BEB compared to BEB.

Figure 9. Channel collision time with PB-BEB compared to BEB.

achieve compared to BEB. For example, at N = 100, PB-BEB and BEB result in a TCC of 27.7% and 83.1%, respectively. This means that PB-BEB can considerably reduce the percentage of time during which the wireless channel is wasted due to collisions.

5.6. Delay

The delay encountered to deliver a packet to its destination is an important metric that gives more insight into the performance of PB-BEB. The delay is measured starting from the instant the packet is available at the node till it is finally received at its destination. That is, the time spent in backoff stages, transmission retries, and CCAs is included in this measurement. In Figure 10 we can see that PB-BEB is causing an increase in the delay.

Figure 10. Delay under PB-BEB compared to BEB.

At N = 200, PB-BEB increases the delay by 22.3% compared to BEB. This outcome is expected since PB-BEB is introducing extra CCA states, and therefore, the node is forced to spend more time before accessing the medium.

5.7. Channel Idle Time

Channel idle time (TCI) refers to the proportion of time the channel is free of any packet transmissions of collisions. This metric measures the percentage of time during which all nodes are either in backoff or CCA states. Therefore, TCI should be reduced as much as possible because it indicates that the wireless channel is not being used. From the definition of TCI we can see that it is the complement of both U and TCC. That is, we compute TCI as follows:

(7)

In Figure 11 we show the performance of PB-BEB and BEB in terms of TCI. It comes as no surprise that PB-BEB is resulting in excessive amount of idle time. Again, this behavior is due to that we are introducing extra CCAs with which nodes are encountering additional waiting periods before being able to send their packets. However, although BEB results in lower TCI, it is causing excessive collisions, as is evident in Figure 9.

5.8. Discussion

Our simulation results showed a superior performance for PB-BEB over BEB, except for the delay. The reason behind these enhancements in the performance is that as we preserve the priority of certain nodes, we basically increase their likelihood of medium access. That is, as different nodes commence their channel sensing at different CCAs, the number of nodes contending to access the channel is reduced and therefore the probability of collision is reduced. This is reflected in improved U, R, and TCC as well as reduced power consumption due to collisions. The fact that introducing extra CCAs does not result in increased power consumption is a direct result of making nCCA change probabilistically. This is because of that the second term in Equation (1) will be eliminated

Figure 11. Channel idle time with PB-BEB compared to BEB.

in case of having relatively low level of collisions. In fact, this term will make PB-BEB highly adaptive to the level of activities in the network, which is associated with the size of the network. As the network’s size increases, the probability of collision increases, and thus the number of CCAs will increase, which plays a role in reducing collisions and therefore enhancing the overall performance.

6. Conclusion

In this paper we tackle the problem of prioritizing the CSMA-CA mechanism in the IEEE 802.15.4 standard. CSMA-CA applies the binary exponent backoff (BEB) algorithm to manage the contention among the nodes attempting to access the wireless medium. The problem with BEB is that it treats all the nodes equally without giving any consideration to the repeated channel access failures or transmission failures experienced by some nodes. We propose the Priority-Based BEB (PB-BEB) to fill that hole in the design of BEB. In PB-BEB, the number of CCAs is controlled probabilistically according to the collision level over the communication medium. As the node finds the medium busy at a certain CCA, beyond the mandatory CCAs of BEB, the node will backoff. At the end of the last backoff, the node will start its clear channel assessment at exactly the last CCA where it stopped. This means that the node that has been experiencing multiple backoffs while trying to send a packet is given a higher priority to access the medium than those nodes that started their contention at a later time. Our simulations show that PB-BEB is able to outperform BEB in terms of fairness. Also, PB-BEB shows superior performance, over BEB, in terms channel utilization, reliability, power wasted in collisions, and channel collision time. However, the main drawback of PB-BEB, compared to BEB, is that it leads to increased delay. The latter is an expected outcome since nodes are forced to conduct extra number of CCAs, which delays the transmission of a packet.

REFERENCES

  1. LAN/MAN Standards Committee of the IEEE Computer Society, Part 15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for LowRate Wireless Personal Area Networks (LR-WPANs), October 2003, pp. 1-679,
  2. Y.-K. Huang, A.-C. Pang and H.-N. Hung, “An Adaptive GTS Allocation Scheme for IEEE 802.15.4,” IEEE Transactions on Parallel and Distributed Systems, Vol. 19, No. 5, 2008, pp. 641-651. doi:10.1109/TPDS.2007.70769
  3. M. Takaffoli, E. Elmallah and W. Moussa, “Scheduled Access Using the IEEE 802.15.4 Guaranteed Time Slots,” Proceedings of IEEE International Conference on Communications (ICC’10), Cape Town, South Africa, 23-27 May, 2010, pp. 1-5.
  4. E. D. N. Ndih, N. Khaled and G. D. Micheli, “An Analytical Model for the Contention Access Period of the Slotted IEEE 802.15.4 with Service Differentiation,” Proceedings of IEEE International Conference on Communications (ICC’09), Dresden, Germany, 14-18 June 2009, pp. 1-6.
  5. R. Severino, M. Batsa, M. Alves and A. Koubaa, “A Traffic Differentiation Add-On to the IEEE 802.15.4 Protocol: Implementation and Experimental Validation over a Real-Time Operating System,” Proceedings of 13th Euromicro Conference on Digital System Design: Architectures, Methods, and Tools (DSD’10), Lille, France, 1-3 September 2010, pp. 501-508.
  6. S. Jardosh, P. Ranjan and D. Rawal, “Prioritized IEEE 802.15.4 for Wireless Sensor Networks,” Proceedings of the 6th Conference on Wireless Advanced (WiAD’10), London, UK, 27-29 June 2010, pp. 1-7.
  7. S. Pollin, M. Ergen, S. C. Ergen, B. Bougard, L. Van derPerre, I. Moerman, A. Bahai, P. Varaiya and F. Catthoor, “Performance Analysis of Slotted Carrier Sense IEEE 802.15.4 Medium Access Layer,” IEEE Transactions on Wireless Communications, Vol. 7, No. 9, 2008, pp. 3359-3371.
  8. R. Jain, D. Chiu and W. Hawe, “A Quantitative Measure of Fairness and Discrimination for Resource Allocation in Shared Computer Systems,” DEC-TR-301, September 1984.