85 Applying data fragmentation in IEEE 802.15.4: modeling and analysis under unsaturated traffic Mouloud Atmani Djamil Aı̈ssani Yassine Hadjadj-Aoul LaMOS research unit LaMOS research unit IRISA Laboratory Faculty of Exact Sciences Faculty of Exact Sciences University of Rennes 1 University of Bejaia University of Bejaia 35042 Rennes 06000 Bejaia, Algeria 06000 Bejaia, Algeria France atmanimouloud@yahoo.fr djamil aissani@hotmail.com yhadjadj@irisa.fr The IEEE 802.15.4 standard, which is developed for low rate applications, offers low latency and energy consumption for wireless sensor networks. The use of the standardized slotted Carrier Sense Multiple Access (CSMA/CA), as a channel access mechanism, can, however, lead to a wastage of the bandwidth utilization and an additional transmission delay. This drawback is mainly caused by deferred transmission in the CSMA/CA algorithm at the end of the superframe, when there is not sufficient time to complete the frame transmission. We propose in this paper to fragment a data frame into a short frame and attempt its transmission in the current frame and transmit the remaining frame in the next superframe. The data fragmentation mechanism is modeled using a Markov chains. A non-saturated traffic and acknowledgement transmission are considered in our analysis. The analytical results of the normalized throughput demonstrate the improvement of the bandwidth occupation when using the proposed data fragmentation mechanism in the IEEE 802.15.4 slotted CSMA/CA protocol. IEEE 802.15.4 slotted CSMA/CA, data fragmentation, Markov chains, Modeling and Analysis. 1. INTRODUCTION in the Personal Area Network (PAN). The superframe contains an active period (for communication) and Before the development of the IEEE 802.15.4 an inactive period (for energy conservation). The standard, several standards offering high data rates active period includes a Contention Access Period were proposed for local and personal wireless (CAP) and an optional Contention Free Period (CFP) area networks (IEEE 802.11, IEEE 802.15.1, etc.). for deterministic channel accesses. During the CAP Such standards were not, however, adapted to period, the slotted CSMA/CA algorithm is executed miniature devices with limited energy capacities. by each node desiring to access the channel. The IEEE 802.15.4 (IEEE std 802.15.4 (2006)) standard was developed and proposed for Low- Several researchers have modeled the slotted Rate Wireless Personal Area Networks (LR-WPANs) CSMA/CA protocol with the Markov chains, by with low energy resources, such as wireless referring generally to the Bianchi’s model (Bianchi sensor networks. The IEEE 802.15.4 defines the (2000)). A simple model of the slotted CSMA-CA specifications of the physical layer and the Medium protocol is given by (Pollin et al (2008)) using Access Control (MAC) sublayer of the ZigBee stack. Markov chains. A generalized Markov chain of IEEE In the MAC sublayer, the IEEE 802.15.4 standard 802.15.4 slotted CSMA/CA is given by (Park et defines two access modes: non-beacon mode and all (2013)). The deferment of the transmission, beacon mode. In the non-beacon mode, unslotted when there is not sufficient remaining time in the CSMA/CA is used for attempting the channel CAP to complete the transmission, is modeled and access. However, slotted CSMA/CA algorithm is evaluated by (Rehman et al (2011)). used in the beacon mode. In the beacon mode, the mode considered in this work, the coordinator In IEEE 802.11 standard, the fragmentation tech- sends regularly beacons frames to delimitate the nique is implemented and many studies have men- superframe and to synchronize the wireless sensors tioned that this technique improves the network 86 throughput (see, the works of IEEE Part 11 (2007), Yazid et al (2013) and Li et al (2009)). The authors, in Yoon, Kim and Ko (2007), have proposed the fragmentation mechanism in IEEE 802.15.4 wireless sensor network to improve the bandwidth utilization. However, in this work, the risk of data collisions is possible when a competitive node pulls a backoff number equal to zero while the transmitter node at- tempts to send the remaining frame, in the beginning of the superframe. This paper talk about the problem of the deferred transmission that causes a significant bandwidth loss in IEEE 802.15.4 wireless sensor networks. For this reason, we propose to send a short frame (equal to 18 bytes as defined by IEEE 802.15.4 standard) when a long frame can not be sent due to an insufficient time in the current superframe. The data fragmentation mechanism is modeled, under non saturation traffic with transmission’s acknowledgment, using a Markov chain. The analytical results show that the fragmentation mechanism clearly allows improving the network performance in terms of throughput. The remainder of this paper is organized as fol- lows. Section 2 gives an overview of the slotted Figure 1: Flowshart of IEEE 802.15.4 slotted CSMA/CA CSMA/CA. Section 3 presents our motivations for algorithm this work and describes the applied data fragmenta- tion mechanism in IEEE 802.15.4 slotted CSMA/CA Once the three variables are initialized, the node algorithm. Section 4 presents the proposed math- waits during a period of backoff randomly chosen in ematical model based on Markov chains of IEEE the range [0, 2BE − 1]. If the pulled number is greater 802.15.4 standard with the proposed data fragmen- than the remaining number of backoff periods in tation mechanism. Section 5 gives a comprehensive the CAP, the MAC sublayer shall pause the backoff performances analysis of our proposal. Finally, we countdown at the end of the CAP and resume it at conclude in Section 6. the start of the CAP in the next superframe. 2. OVERVIEW OF IEEE 802.15.4 SLOTTED At the expiration of the random backoff delay, CSMA/CA the MAC sublayer ensures that the remaining CSMA/CA operations can be undertaken and the In this section, we describe the behavior of the IEEE entire transaction can be completed before the end 802.15.4 slotted CSMA/CA protocol. Each node of the CAP. Two cases are possible: aiming to transmit a data frame or a control frame, Case 1: The remaining time in the CAP is as indicated in IEEE 802.15.4 standard, initializes sufficient: three variables (N B, BE and CW ). The variable N B The MAC sublayer requests the physical layer to describes the number of times that the CSMA/CA perform two CCA: algorithm is executed for attempting to access the channel (i.e. Number of Backoff). The variable BE 1. The channel is assessed to be busy during is used to generate a random backoff duration that one of the CCA: both N B and BE are a node shall wait before attempting the first carrier incremented by one (BE shall be no more than sensing (i.e. Backoff Exponent), its value depend on macM axBE), CW is reset to two. If N B is less the value of BLE (Battery Life Extension) sent by than or equal to macM axCSM ABackof f s, the PAN coordinator. The variable CW indicates the which is equal to 4 by default, a new BE is number of time that a channel must be clear before pulled randomly in the range [0, 2BE − 1]. If beginning the data transmission (i.e. Contention N B is greater than macM axCSM ABackof f s, Window). Its value is set to two, as shown in figure 1. the CSMA/CA algorithm shall terminate with a channel access failure status. 87 2. The channel is assessed to be idle during the frame (less than or equal to 18 bytes). In our first CCA: CW is decremented by one and work, we propose to add the following test in the checked whether it is equal to zero. slotted CSMA/CA algorithm: before deferring the The same procedure is considered for the transmission of a long frame due to insufficient second CCA, If CW is equal to zero, the data remaining time in the CAP period, slotted CSMA/CA frame is transmitted. checks if the remaining time is sufficient to complete the transmission of a short frame. In this case, the Case 2: The remaining time in CAP is insuffi- rest of the frame will be transmitted in the new cient: superframe. The transmission will be deferred to the next super- frame and a new slotted CSMA/CA is executed at the beginning of the CAP, as depicted on the yellow rectangle of the Figure 1 3. MOTIVATIONS AND PROPOSAL In this section, we give our motivations behind applying the data fragmentation mechanism in IEEE 802.15.4 slotted CSMA/CA protocol. Then, we describe our solution and we give its main interest in the IEEE 802.15.4 wireless sensor networks. Figure 3: Applying data fragmentation in Slotted CSMA/CA 3.1. Motivations Given the critical nature of the applications in which Figure 3 shows that the data fragmentation the sensor networks are applied, it is important to increases the bandwidth occupation and reduces the optimize the use of all resources (bandwidth, battery, data transmission time. To ensure the transmission ...) together with the time of communication. As of the remaining frame without collision, at the explained in the section 2, a node using slotted beginning of the superframe, our technique avoids CSMA/CA to transmit a data frame must estimate the channel listening (CCA1 2 and CCA) for the the remaining time in the ion, it sends the frame, node which transmitted a short frame in the previous otherwise it differs the transmission for the new superframe. superframe (see figure 2). 4. ANALYTICAL MODEL In this section, we model and analyze the proposed data fragmentation mechanism in the IEEE 802.15.4 with acknowledgment of the transmitted data under unsaturated traffic conditions. We assume N nodes connected with a PAN coordinator in a star topology. 4.1. Markov chain model In the following, we model the behavior of a single Figure 2: Deferred transmission in Slotted CSMA/CA node using IEEE 802.15.4 slotted CSMA/CA with the data fragmentation mechanism, using a three The delay caused by the deferred transmission dimensional Markov chain in order to analyze the of a data frame increases more when the size network performances. Three stochastic processes of a packet increases. The long frame and the are used to describe the state of the node at each frequent deferments lead to a bandwidth misuse. time when executing slotted CSMA/CA with data These problems can be avoided by applying the fragmentation mechanism. data fragmentation mechanism. Thus, a rational management of the bandwidth and a minimum time Let S(t), B(t) and T (t) be the stochastic processes of transmission will be achieved. representing the backoff stage, the state of the backoff counter and the packet type to transmit at 3.2. Slotted CSMA/CA with data fragmentation time t, respectively. Their values are given as follows: S(t) = (0..m), B(t) = (−2..Wi − 1) and T (t) = IEEE 802.15.4 describes two types of data frames: {−1, 0, 1, 2}, where m = macM axCSM ABackof f s, a long frame (greater than 18 bytes) and a short 88 and Wi = 2i W0 , the initial value of W0 = 2BE − The transition probabilities associated with the 1, where the value of BE is defined in figure 1. Markov chain of figure 4 are: We note that, the backoff counter B(t) is divided into two periods, the backoff period pulled between P (i, k, j|i, k − 1, j) = 1, k > 0 (2) h i {0, 2BE } and the second period represent the two P (i, −1, j|i, 0, j) = (1 − α) (1 − Pd ) + Pd Pf , clear channel assessment (CCA) periods (-2 and - 1). j = {0, 1}, i 6 m (3) P (i, −2, j|i, −1, j) = 1 − β, j = {0, 1}, i 6 m (4) The Idle state in figure 4 indicates wether the node has a data frame to transmit. In other words, this α + (1 − α)β P (i, k, j|i − 1, 0, j) = (1 − Pd ) , i6m state models the queue of a node. To satisfy the Wi condition of non-saturated network (i.e. a node has (5) not always a frame to transmit), we consider that the Pd P (0, k, 0|i, 0, 0) = [(1 − Pf ) + Pf [α + (1 − α)β]], events arrive to the nodes according to the poisson W0 process with the rate λ. Hence, the probability q that j = {0, 1}, i 6 m (6) a data packet (event) arrives to a node during one P (i, 0, 1|i, 0, 0) = Pd Pf , i 6 m (7) backoff period T s is given as follows: q Z Ts P (0, k, 0|Idle) = ,k > 0 (8) W0 −λt q= λe dx (1) 0 Equation (2) defines the decrement probability of the backoff counter. Equation (3) and (4) describes the probability to find the channel idle for the first CCA and second CCA, respectively. Equation (5) denotes that the channel is busy, the node in this case selects a new delay backoff in the new stage. Equation (6) represent the probability to defer the transmission to the next superframe when the remaining time in the CAP is either insufficient to transmit a packet or a fragment, or the fragmentation is possible but the channel is busy. Equation (7) describes the possibility of fragmentation when the remaining delay of CAP is not enough to assure a successful transmission of the original frame. The probability to pull a data frame in the queue of a node to transmit is given in the equation (8). Let bi,k,j = limt→+∞ P {S(t) = i, B(t) = k, T (t) = j}, be the stationary distribution of our Markov chain. Using equation (5), we get the probability to find a node in any stage at the steady state:  h ii bi,0,0 = (1−Pd ) α+(1−α)β b0,0,0 , f or 1 6 i 6 m (9) The probability to be in any state of the first stage is given as follows:  W0 − k h iXm b0,k,0 = (1 − α)(1 − β)(1 − Pd ) bi,0,0 W0 i=0 Figure 4: Markov chain model for Slotted CSMA/CA with  fragmentation h i +(1 − Pd ) α + (1 − α)β bm,0,0 (10) 89 The probability to be in any backoff state in any stage B) Probability β: is defined as the probability to find is given by: the channel busy in the CCA2, given that it is free in the CCA1 period. Wi − k bi,k,0 = bi,0,0 , f or1 6 i 6 m, 1 6 k 6 Wi − 1 Wi 1 − (1 − τ )N −1 + N τ (1 − τ )N −1 (11) β= . (16) 2 − (1 − τ )N + N τ (1 − τ )N −1 In the normalization conditions, the probabilities must sum to 1. So: C) Probability of deferment (Pd ): is defined as the X X m Wi −1 X −1 m X X m X 0 probability that the remaining time in the CAP is 1 = bi,k,0 + bi,k,0 + bi,k,1 not sufficient to complete the transmission of a i=0 k=0 i=0 k=−2 i=0 k=−2 data frame and its acknowledgment. Hence, after X m X LF −1 X SF −1 the completion of the backoff decrementation, the + bi,0,−1 + b−1,k,0 + b−1,k,1 current time of the node must be in the interval i=0 k=0 k=0 ]CAP − TLF + 2 ∗ Tcca + Tack wait + TACK , CAP ] to X RF −1 defer the transmission. This interval is illustrated by + b−1,k,2 + bIdle . (12) the blue stripes part as shown in the figure 5. k=0 Therefore, the formula of b0,0,0 is given as follows : 1 ab0,0,0 = " 3 + Pd Pf (2 − α) + (1 − α)(1 − Pd ) − x Figure 5: Insufficient remaining time in CAP for a complete 2 transmission h +(1 − Pc )(1 − α)(1 − β) (1 − Pd )(1 + LF ) # The probability of deferment is formulated by the 1 i 1 − xm+1 xm+1 following expression: +Pd Pf (SF + RF + ) + q 1−x q TLF + 2 ∗ Tcca + Tack wait + TACK + ε , (13) Pd = , (17) 1 − (2x)m+1 TCAP + w0 2(1 − 2x) where Tack wait is the time to wait before beginning   the ACK transmission. While ε is introduced in the where, x = (1 − Pd ) α + (1 − α)β and LF , SF , and RF represent, respectively, a longue frame, a equation (17) to indicate that the time, in the CAP, to short frame (fragment) and a remaining frame. The complete the frame transmission is insufficient. probability that a node attempts to sense the channel D) Probability of fragmentation (Pf ): is the probability for the first time (τ ) in any stage of the Markov chain to find, in the remaining time of the CAP, is expressed as follows: sufficient time to transmit a short frame and X m any acknowledgment. Assuming that when the τ= bi,0,0 . (14) backoff counter of a sensor is zero its current i=0 time is in the interval ]TCAP − TLF + 2 ∗ Tcca + Tackw ait + TACK , TCAP − TSF + 2 ∗ Tcca + Tack wait + To compute the performance of the network, we TACK ], the blue stripes in figure 6. In this express all the probabilities in interaction with the case, the data fragmentation is applied. Otherwise, probability τ . the fragmentation is not possible and the data transmission will be deferred to the next superframe, A) Probability α: is the probability to find the channel as depicted by the red stripes in figure 6. busy during CCA1 due to data (or acknowledgment) frame transmission. Similarly to Park et all (2013), we express this probability as follows:   h N τ (1 − τ )N −1 i α = 1−(1−τ )N −1 (1−α)(1−β) T +TACK , 1 − (1 − τ )N (15) where T and TACK represent the number of backoff Figure 6: Possibility of fragmentation in the CAP delay required for the frame transmission and the acknowledgment frame, respectively. 90 The probability of fragmentation is given in the 5. ANALYTICAL RESULTS following expression: In this section, we evaluate the performance of TLF − TSF + ε the data fragmentation mechanism in improving Pf = , (18) TCAP the network throughput. The analytical parameters taken into account in the performance analysis are where ε is introduced in equation (18) to express the presented in table 1. impossibility of transmitting the original frame (LF ). Table 1: Analytical parameters 4.2. Throughput The unsaturation throughput (noted S), as defined Parameters Initial in Bianchi (2000), as the fraction of time that Value the channel is used to successfully transmit the Max packet length 127 data frame. Therefore, S depends, on the following Bytes probabilities: Max packet transfert delay 4 ms Radio transmission power 52.2 mw A) Transmission probability (Ptr ): represents the Radio reception power 59.1 mw probability that at least one node (among N nodes) Radio idle power 1.28 mw is in the beginning of the first clear sensing (CCA1) Battery Capacity 2500 with probability τ , the channel sensed free in CCA1 mAh and CCA2 and the transmission will not be deferred. Voltage 3.0 V   Ptr = 1 − (1 − τ )n (1 − α)(1 − β)(1 − Pd ). (19) Figure 7 shows the results of network throughput for 10 nodes under different traffic load. It B) Successful transmission probability (Ps ): is the illustrates the throughput improvement using the probability that exactly one transmission occurred data fragmentation mechanism (IEEE 802.15.4 in the channel, conditioned by the transmission Frag), comparing it with IEEE 802.15.4 standard probability (as defined in Bianchi (2000)). (IEEE 802.15.4). We show that when the length of the original frame is just greater than the short frame nτ (1 − τ )n−1 (1 − α)(1 − β)(1 − Pd ) Ps = . (20) (L = 3 slots and shortf rame = 2 slots) the gain Ptr is not large enough. However, when increasing the frame size, the gain in throughput becomes very Now, we can express the unsaturation throughput (S) important (see the case of L = 7 slots). as follows: Ptr Ps Tpload 0.11 S = (1 − Ptr )σ + Ptr Ps Ts + (1 − Ps )Tc 0.1 . (21) +Pd (1 − Pf )TDef 0.09 0.08 Normalized Throughput where, Tpload is the time occupied by the packet transmission, σ is the duration of an empty time 0.07 slot, Ts is the time of a successful transmission of 0.06 a packet, Tc is the time during which the channel is 0.05 busy due to a collision and TDef is the average time wasted when deferring the current transmission. 0.04 IEEE 802.15.4 Frag L=3 0.03 IEEE 802.15.4 Std L=3 0.02 IEEE 802.15.4 Frag L=7  IEEE 802.15.4 Std L=7  Ts = TP HY + TM AC + Tpload + 2TCCA + TLIF S ,   0.01   +Tack + TACK . 0 0.02 0.04 0.06 0.08 0.1   Arrival Rate λ (packet/time slot)   Tc = TP HY + TM AC + Tpload + 2TCCA + TLIF S , +Tack .  Figure 7: Throughput versus traffic load with number of   TSF + TP HY + TM AC + TSIF S + 2Tcca   TDef = nodes = 10   2   Tack + TACK − ε + , Figure 8 illustrates the cases of a dense network 2 (22) (number of nodes = 50). When the frame is long where ε indicates that there is not sufficient time to (L = 7 slots) and the traffic load (λ) is less than 0, 01, complete the short frame transmission in the current the network throughput is better than when using superframe. a small frame (L = 3 slots), independently from 91 considering or not the fragmentation mechanism. in term of throughput under non saturated traffic with However, when the traffic load increases, it causes acknowledgment. The results shows the interests in frequent collisions and deferred transmissions. That applying the data fragmentation mechanism in the is why, the small frames give better results. In IEEE 802.15.4 standard. all cases, we show that, the data fragmentation mechanism offers a better throughput. 0.12 IEEE 802.15.4 Frag L=3 IEEE 802.15.4 Std L=3 IEEE 802.15.4 Frag L=7 0.1 0.1 IEEE 802.15.4 Std L=7 IEEE 802.15.4 Frag L=3 0.09 IEEE 802.15.4 Std L=3 Normalized Throughput IEEE 802.15.4 Frag L=7 0.08 IEEE 802.15.4 Std L=7 0.08 Normalized Throughput 0.07 0.06 0.06 0.04 0.05 0.04 0.02 0.03 0 0 10 20 30 40 50 0.02 Number of Nodes 0.01 0 0.02 0.04 0.06 0.08 0.1 Arrival Rate λ (packet/time slot) Figure 10: Throughput versus number of nodes with λ = 0, 05 Figure 8: Throughput versus traffic load with number of nodes = 50 In the figure 10, we analyzed an average traffic (λ = 0, 05) to see the contribution of the data fragmentation mechanism when the number of 0.1 nodes increases. The throughput decreases when 0.09 IEEE 802.15.4 Frag L=3 the number of nodes increases, due to collisions and IEEE 802.15.4 Std L=3 IEEE 802.15.4 Frag L=7 frequent transmission deferrement. 0.08 IEEE 802.15.4 Std L=7 0.07 Normalized Throughput 6. CONCLUSION 0.06 0.05 In this paper, the data fragmentation mechanism is proposed to be applied in IEEE 802.15.4 0.04 slotted CSMA/CA protocol. The principle of the 0.03 mechanism is simple to implement, without changing 0.02 the operating principles of IEEE 802.15.4 slotted CSMA/CA. The data fragmentation is applied when 0.01 the transmission of a long frame is impossible due to 0 0 10 20 30 40 50 insufficient remaining time in the contention access Number of Nodes period. Our proposal privileges the transmission of the remaining frame in the new superframe and Figure 9: Throughput versus number of nodes with λ = avoid its collision. In our future works, we will 0, 001 evaluate the impact of other parameters on the overall network performance and we will analyze Figure 9 clearly shows the contribution of the data how to improve the energy consumption using the fragmentation mechanism, when the network traffic data fragmentation mechanism. is low (λ = 0, 001). The difference between the throughput of the IEEE 802.15.4 with the proposed fragmentation mechanism and the IEEE 802.15.4 REFERENCES standard becomes clear when the frame length IEEE std 802.15.4, Part 15.4. (2006) Wireless increases. Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless we presented a Markov chain-based model of Personal Area Networks (WPANs). the slotted CSMA/CA protocol, which includes data fragmentation mechanism. Using the proposed Bianchi, G. (2000) Performance analysis of the IEEE model, we have evaluated the system performance 802.11 distributed coordination function. IEEE 92 Journal on Selected Areas in Communications, volume 18, issue 3, 535?547. Pollin, S. Ergen, M. Ergen, S. C. Bougard, B. Perre, L. V. Moerman, I. Bahai, A. Varaiya, P. and Catthoor, F. (2008) Performance Analysis of Slotted Carrier Sense IEEE 802.15.4 Medium Access Layer. IEEE Transactions on Wireless Communications, volume 7, issue 9, 3359-3371. Park, P. Di Marco, P. Fischione, C. and Johansson, K.H. (2009) Modeling and Optimization of the IEEE 802.15.4 Protocol for Reliable and Timely Communications. IEEE Transactions on Parallel and Distributed Systems, volume 24, issue 3, 550- 564. Rehman, S. U. Bhatti, F. A. Iqbal, M. Y. Sabir, Z. (2011) Modeling the Impact of Deferred Transmission in CSMAICA Algorithm for IEEE 802.15.4 using Markov Chain Model. IEEE Region 10 Conference ,Fukuoka, Japan. IEEE Part 11. (2007) Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Std 802.11. Yazid, M. Bouallouche-Medjkoune, L. Aı̈ssani, D. Ziane-Khodja, L. (2013) Analytical analysis of applying packet fragmentation mechanism on IEEE 802.11b DCF network in non ideal channel with infinite load conditions. Wireless Network, DOI 10.1007/s11276-013-0653-2. Li, T. Ni, Q. Malone, D. Leith, D. (2009) Aggre- gation With Fragment Retransmission for Very High-Speed WLANs. IEEE/ACM transactions on networking, volume 17, issue 2, 591-604. Yoon, J. Kim, H. Ko, J. G. (2007) Data Fragmenta- tion Scheme in IEEE 802.15.4 Wireless Sensor Networks. IEEE 65th Vehicular Technology Con- ference, Dublin, Ireland.