# Designing a Channel Access Mechanism for Wireless Sensor Network

Authors: Basma M. Mohammad El-Basioni; Abdellatif I. Moustafa; Sherine M. Abd El-Kader; Hussein A. Konber
Journal: Wireless Communications and Mobile Computing
 (2017)

---

## Abstract

Although there are various Medium Access Control (MAC) protocols proposed for Wireless Sensor Network (WSN), there is no protocol accepted as a standard specific to it. This paper deals with completing the design of our previously proposed MAC for WSN by proposing a channel access mechanism (CAM). The CAM is based on developing a backoff mechanism which mainly differentiates nodes’ backoffs depending on their different identification numbers, and it employs a performance tuning parameter for reaching a required performance objective. The probability distribution of the backoff period is constructed and Markov chain modeling is used to analyze and evaluate the CAM against the IEEE802.15.4 slotted CSMA/CA based on single- and multihop communication with respect to the reliability, the average delay, the power consumption, and the throughput. The analysis reveals that the required performance of CAM against the IEEE slotted CSMA/CA can be obtained by choosing the maximum backoff stages number and the tuning parameter value and that CAM performs better than the IEEE with larger nodes number. The multihop scenario results in a good end-to-end performance of CAM with respect to the reliability and delay becomes better with lengthier paths at the expense of increasing the energy consumption.


---

## Body

## 1. Introduction

MAC [1–3] is the rudiment for any wireless communication system to function properly. It coordinates access to and transmission over the medium common to several nodes and puts rules to minimize interference and packet collisions among them under imposed constraints and desired performance goals.It is not highly true to say that the collision cause is the concurrent transmissions, because concurrent transmissions may not cause collision even if the transmitters reside in the same radio range. It is better not to point to the sender in clarifying the cause of the collision, but referring it to the receiver where the collision occurs at a receiver due to its reception to more than one signal at the same time because of its residence in the common transmission area of more than one transmitter whether it is the intended receiver of one or more of them.The MAC protocols can be divided into two main approaches, contention-based [4, 5] (random assignment protocols) and contention-free [6, 7] (schedule-based) of which indoors may be classified into fixed-assignment protocols and demand-assignment protocols. Far from the bad channel utilization of the fixed-assignment and its other cons and far from the additional overhead of the demand-assignment through polling and reservation, the contention-based MAC protocol is more logical for accessing the channel; however, it is more prone to fail in successful medium allocation and collision prevention. This depends on the characteristics of the contention-based MAC protocol itself and another high importance factor which is the logical topology that determines the number of talkers, who can talk to who, when and where they can talk, at what range, and so forth.Based on that, it is preferred to use a contention-based MAC with a good performance works on a logical topology paved for it especially with respect to predictability and number of contending nodes, where the condition under which these protocols may fail in preventing collisions is the sources’ number increase or the sources’ transmission rate increase.The MAC layer design intended by the work proposed in this paper is based on the physical layer of the IEEE802.15.4 standard [8–10] and composed of two techniques, a timing structure mechanism (TSM), proposed by our previous work [11], including the setup of the logical topology by dividing the network into subnetworks (sub-NWs) using multichannels and identifying the time structure of the sub-NW members’ work and the contention-based CAM proposed in this paper. The main TSM idea was to construct a receive schedule which makes, at a time, only one node from a group of nodes (sub-NW) listen to the channel, and each node takes its turn successively to listen for a small period. At any time a node wants to transmit, it can turn its radio to the transmit state and transmit directly in its maximum range or in a range suitable to the currently listening node using the CAM. The backoff periods are aligned with a reference time common to the nodes.The CAM is designed to be suitable to the proposed TSM and benefits from it, and it is based on developing a backoff mechanism, resorting to the common manner of increasing the backoff stages (i.e., repeating the trials of accessing the channel if it is found busy rather than announcing channel access failure and discarding the packet), and using a number of transmission trials to cope with the transmission failure rather than discarding the packet.The rest of this paper is organized as follows. Section2 includes a brief literature review for wireless MAC protocols. Section 3 begins with giving an overview of the beacon-enabled IEEE802.15.4 slotted CSMA/CA; then it illustrates the proposed CAM idea and its modeling. The performance assessment of CAM is depicted in Section 4, where the CAM performance is evaluated against the slotted CSMA/CA in terms of single- and multihop communication; also the effect of different parameters on CAM performance and its tuning is considered. Finally, Section 5 concludes the paper and suggests open issues for future work.


## 2. Literature Review

The wireless medium access schemes used in different types of wireless networks are based on carrier sensing, backoff algorithms and mechanisms for avoiding hidden and exposed terminal problems. The Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) with its two versions, nonpersistent andp-persistent, represents the basic form of channel access control. In nonpersistent CSMA, if the device senses the channel busy, it backs off before trying to transmit again. When the channel is idle, the device transmits immediately. In p-persistent CSMA, the device continues sensing the busy channel until it becomes idle, and in case of idle channel, it transmits or defers transmission according to a probability p. Keeping devices in the receive state when not transmitting consumes a large amount of energy. Multiple Access with Collision Avoidance (MACA) [12] uses two additional packets, Request-to-Send (RTS) and Clear-to-Send (CTS) before the transmission to reduce the occurrence of the hidden and exposed terminal problems. The RTS is sent by the sender, and the receiver willing to accept data responds with CTS; the other devices hear the RTS or the CTS and avoid interfering the involved devices until end of transmission. The RTS/CTS represents overload on the network and causes additional delay.Modifications to these schemes were then proposed, such as using acknowledgment, using Request-for-Request-to-Send packet by a busy RTS receiver after finishing its transaction, employing waiting intervals other than the backoff time providing priority levels for wireless channel access as used in the IEEE802.11 [13] distributed coordination function, and using variations in backoff time computation method such as binary exponential backoff, multiplicative increase and linear decrease, balanced backoff algorithm, and waiting time based backoff. Wireless networks do not only use contention-based schemes but also use contention-free access such as the point coordination function defined in IEEE802.11 in which a coordinator device polls other devices for data.Due to the energy constraint in WSN, the design of WSN MAC considers other mechanisms, in addition to that used in coordinating the shared medium allocation and controls nodes’ activation to allow them to sleep saving their energy wasted in idle listening and overhearing. The used medium allocation scheme itself should be energy-efficient; for example, it does not employ large overhead. The MAC protocols proposed in literature for WSN can be broadly classified according to the scheme depicted in Figure1.Figure 1
Different approaches for WSN MAC protocols.The contention-based synchronous sleep-scheduling [14] can be through having each node following a periodic active/sleep cycle; the nodes that are close to one another synchronize their active cycles together, and if the next hop of a transmission overhears it, it remains awake until receiving the forwarded data rather than sleeping and delaying data forwarding up to its next active cycle. But this is not always the case, the next-hop node may be out of the hearing range of both the sender and the receiver making data forwarding interruption problem unavoidable; the staggered wake-up scheduling [15, 16] is used to address this problem which creates a pipeline for data propagation based on the depth-level of nodes in a data-gathering tree, where the active period of one level partially overlaps with that of the lower level.In the asynchronous sender-initiated MAC [17, 18], the sender transmits a preamble to indicate a pending transmission. The receiver wakes up occasionally to listen to such a preamble for appropriately responding. In receiver-initiated schemes [19], instead of long preambles, the sender listens to the channel waiting for the receiver small beacons, transmitted in duty cycle fashion, to synchronize with the receiver. The asynchronous schemes are simpler to implement than the synchronous but it may result in very long delay. WSN MAC can be contention-free using Time Division Multiple Access (TDMA) or Frequency Division Multiple Access (FDMA) or hybrid. In multichannel MAC [20, 21], some issues are raised such as limited number of available channels, channel selection and assignment policy, and recursive channel switching overhead. Radio-triggered MAC [22, 23] and cross-layer MAC [24, 25] designs are other approaches proposed for WSN which can be employed with different types of channel access mechanisms. If radio-triggered ID [26, 27] is used, an additional wake-up hardware corresponding to each used frequency and a transmitter able to transmit at different frequencies simultaneously will be required.IEEE 802.15.4 is the de facto physical and MAC layers standard specification used for WSNs. In IEEE 802.15.4 MAC, the channel time is bounded using a superframe structure bounded by periodic transmission of a beacon frame. The superframe has active/inactive portions, a CSMA-based Contention Access Period (CAP), and an optional reservation-based Guaranteed Time Slot (GTS) scheme intended to support devices requiring dedicated bandwidth or low latency transmission through a Contention-Free Period (CFP). In our previous work [11], the channel time bounding mechanism of the proposed MAC is implemented and evaluated against the IEEE 802.15.4 MAC superframe structure in a complete network form using the same contention-based channel access mechanism used in the standard and illustrated in the next section. In this paper, a design for the proposed MAC contention-based channel access mechanism is implemented and evaluated against the standard.


## 3. CAM Idea Implementation, Evaluation, and Modeling

This section firstly gives an explanation and insight on the IEEE802.15.4 contention-based channel access mechanism, and then it proceeds to explain the new backoff method of the proposed CAM which represents the difference between it and the standard channel access mechanism. This section also includes a simple simulation-based evaluation of CAM as a proof of concept and it ends with introducing the CAM modeling.


### 3.1. Overview of the Beacon-Enabled IEEE802.15.4 Slotted CSMA/CA

The IEEE802.15.4 standard specifies the physical layer and media access control layer for low-rate wireless personal area networks (LR-WPANs), and based on it, other standards which define the upper layers of the stack are developed, such as ZigBee [28], ISA100.11a [29], WirelessHART [30], MiWi [31], and 6LoWPAN [32].The IEEE802.15.4 network can operate in two modes of operation beacon- or nonbeacon-enabled modes. In nonbeacon-enabled mode, the peer-to-peer data transfer model, in which the devices wishing to communicate need to receive constantly and simply transmit its data using unslotted CSMA/CA, is employed. Indeed, this consumes more nodes’ energy as undesirable manner for battery-powered nodes. The beacon-enabled mode is more suitable for battery-powered nodes, where in this mode, a star topology is formed between devices and a single central controller, called the coordinator; these devices are allowed to sleep most of their times, while the coordinator listens to the channel for a longer time but also is allowed to sleep periodically. The coordinator bounds its channel time using a superframe structure bounded by the transmission of a beacon frame.In beacon-enabled mode, the slotted CSMA/CA channel access mechanism, in which units of time called backoff periods (backoff slots) are aligned with the start of the beacon transmission and each time a device wishes to transmit data frames, it shall locate the boundary of the next backoff slot and then wait for a random number of backoff slots. If the channel is idle, the device can begin transmitting on the next available backoff slot boundary; otherwise, following this random backoff, the device shall wait for another random number of backoff slots before trying to access the channel again. Each device shall maintain three variables for each transmission attempt:NB, CW, and BE:N B holds the number of times the CSMA/CA algorithm attempts to access the channel to transmit the current packet and it is initialized to zero before every new transmission. The value of the attributemacMaxCSMABackoffs determines the maximum value for this variable; that is, it determines the number of allowed attempts for CSMA/CA algorithm to access the channel to send a packet before reporting channel access failure; if the value of NB is greater thanmacMaxCSMABackoffs, the CSMA/CA algorithm shall terminate with a CHANNEL_ACCESS_FAILURE status.C W defines the fixed number of backoff periods that the channel has to be idle before a node can start to transmit and in the standard it is set to 2 backoff periods. According to that, it is initialized to 2 before each transmission attempt and reset to 2 each time the channel is assumed to be busy.B E refers to the backoff exponent, a basis of two is raised to the BE power (2BE) to indicate the count of possible backoff periods number, and the CSMA/CA can randomly choose one from them to wait this chosen backoff periods number before attempting to assess the channel. This count (2BE) represents a range of consecutive numbers of backoff periods beginning from 0 backoff period and so ending with (2BE-1) backoff period. Each channel access attempt failure for a transmission, BE, is incremented by one to double the range of possible backoff periods numbers but up to a maximum value equal to the value of theaMaxBE constant beyond which its value is frozen, and also it has a minimum value,macMinBE (referred in the paper as m0).The slotted CSMA/CA purposes making the performing of the Clear Channel Assessment (CCA) and starting of packet transmission operations of nodes be aligned, consequently, overlap of CCA operations will not occur, and neither false idle channel assessment nor collisions may occur. Not only does the synchronization of backoff periods achieve that, but also the choice of the unit backoff period value affects this aim. The value of the backoff period is selected to be equal to a CCA duration plus a turnaround time for changing the transceiver to the transmit state which is the time taken by the node to be ready for the transmission start. So the backoff period equals 20 symbol as shown in Figure2.Figure 2
Illustration of the backoff period.If it is said that small backoff period is better to decrease the delay, the reply will be that if the backoff period is smaller than 20 symbols there will be an overlap among the CCA and turnaround times of nodes as shown in Figure3. Node 2 sensed the channel idle and started to turn its transmitter on; during that Node 1 was assessing the channel and its assessment ended before or on or just after the time Node 2 began to send, and it did not hear its transmission and proceeded to transmit. The same thing can happen between Node 1 and Node 3. Although the nodes started to assess the channel in different backoff periods, they collided.Figure 3
The effect of a backoff period smaller than 20 symbols.The backoff period should not also be greater than 20 symbols. A greater period, as illustrated in Figure4, increases the delay which resulted from the backoff time and from locating the next backoff slot boundary without any additional beneficial effect on preventing the channel sensing overlap and collisions.Figure 4
The effect of a backoff period greater than 20 symbols.TheCW is selected to be 2 backoff periods; that is, the node should be sure that two idle CCA operations were performed before the beginning to transmit for preventing potential collisions of acknowledgement frames. If the reception of a packet had been completed at a node before the backoff period boundary at which it began to perform its CCA and accordingly its reception had been completed at its destination node before the same backoff boundary (this packet can be undeliverable by this node which wants to transmit while its acknowledgement is deliverable; that is, the source node of the acknowledged packet can be out of the range of the node wants to transmit, but the node wants to transmit and its intended receiver fall in the range of the destination node), an overlap would occur between the delay consumed by the destination node computed starting from the time of packet reception completion and represented in the turnaround time and the backoff period boundary locating delay to start sending the required acknowledgement and the CCA of the node wants to transmit which sensed the channel idle while an acknowledgement was going to be transmitted. If this node does not perform a second CCA, it will start to transmit its packet with the destination node acknowledgement transmission and a collision would occur, as illustrated in the Figure 5.Figure 5
Illustration of the importance of performing two CCAs.


### 3.2. Backoff Method Explanation

In the proposed backoff method, the node computes the backoff time in each backoff stage from(1)bfs=ID+intuniform0,RIDmods+1mod2mb-u+∑j=0s-1bfj+ccajmodu+1,where bf(s) is the function used by a node to compute its backoff time in a backoff stage s, s is the index of the backoff stage in range 0,m, ID refers to the identification of the node computes the backoff period, RID refers to the identification of a receiving node, and cca(s) is a function which gives the time spent in channel sensing in stage s. In the analysis, the clause ∑j=0s-1bf(j)+cca(j) is referred to as “the backoff sum” and denoted by bfsum(s).The first term of the equation aims to make the backoff time of each node different from the others by making it dependent on their different identification numbers, so that if more than one node have data to send at the same time, they wait different time periods before starting to sense the channel.The integer uniform random number,intuniform0,RIDmod(s+1), used in the first term depends on the identification of the receiving node. The purpose of this is to differentiate the backoff time of a certain node with the passage of time, taking advantage of the presence of different receiving nodes, so that no node always has to wait a bigger time than its competitors; and this prevents the error repeating by backing off the same period each backoff trial after an overlapped sensing is done. But this random number is limited to a certain range by considering the modulus of RID and a certain value made to be dependent on the index of the backoff stage also in order to differentiate the backoff with time and so that the possible range to a node is allowed to become greater each backoff trial.The second term of the equation considers the fact that the nodes may have data to send already in different times but their different computed backoff delays make them start sensing the channel at the same time. Therefore, this term makes the backoff times chosen by the nodes depends on their starting time of having the data which is different among them; in this case, this is achieved by taking the sum of the delays which resulted from the previously encountered backoff stages for this data (if any).For limiting the backoff time to a certain maximum limit, regardless of the values of nodes’ IDs, the modular arithmetic is involved in the two terms of the equation, and the maximum limit is selected to be as the maximum limit of backoff in the IEEE standard which equals (2mb-1), where mb is the maximum backoff exponent.The moduli of the modular operations determine the range of each equation’s term resultant values; therefore it is made to be dependent on a parameteru which controls the maximum value of each term. The increase in u value increases the maximum value of the second term while decreasing that of the first term and vice versa; by the same logic, u is used as a tuning parameter for performance metrics. The range of u is [0,2mb-1]; the values of the two variables ID and RID fall in the range [1,N], where N is the number of nodes in the sub-NW, assumed to fall within range 2,∞.


### 3.3. Using R Language to Simulate Nodes’ Backoff

A code in R language [33] was written to simulate the nodes’ backoffs upon (1) and quickly manifest their corresponding behavior and its impact on star topology data transmission specially with respect to the eventuating of collisions and channel access overlap at different simple assumption-based scenarios.The code assumes that each node takes its turn as a star topology receiver upon a predetermined schedule for a period equal to a complete transaction (13-backoff unit). The node does not start a transmission process until it finishes its receiving slot. Packet generation is exponentially distributed over nodes with rate equal to 1 and limited to be 1 packet per node over the simulation time. The packet generation time for all nodes is limited to be within a certain period from the start time to guarantee that all nodes will have data to send during the test period. There is only one transmission trial but a number of backoff stages are allowed. The considered parameters are computed by averaging the outputs of a number of code runs (in each run the time of having data for each node is changed).By settingm to 5, mb to 5, u to 5, and the time within which each node will generate a packet to 1240 backoff unit, Figure 6 shows that the average number of collisions increases polynomially with the increase of the number of contending nodes with instantaneous rate of change linearly increases with increasing nodes number. This increase of collisions number and the inherent increase of nodes number which cause the collision’s conflict result in the increase of the loss percentage due to collisions occurrence; as shown in Figure 7, the loss percentage reached approximately 13% when nodes number is 70.Figure 6
CAM average number of collisions versus number of nodes.Figure 7
CAM loss percentage due to collision versus number of nodes.Figure8 shows the percentages of both the total number of time slots which encounter overlap in transmission attempts’ starts and the number of time slots which cause concurrent channel access and accordingly collisions with respect to the total number of channel access attempts. While Figure 9 draws the number of collision-prone transmission attempts which encounter conflict at the start of backoff computation and the number of collision-raiser time slots, this is computed with restricting the time of nodes’ start data generation to a small period to increase the chances of concurrent transmission and channel access attempts.Figure 8
CAM percentages of collision-prone and collision-raiser situations.Figure 9
CAM number of collision-prone and collision-raiser situations.It is apparent from Figure9 that the number of collisions happened is smaller with a big percentage than the number of chances that would cause them if the conflicting nodes select similar backoff periods. It could be said that the backoff method solves approximately, on average, 80.8% of the channel access conflict situations encountered; actually some of these situations are originally caused by the backoff method itself due to its incapability to perfectly prevent conflicts, but it is able to mend from this—if the channel is found busy and no collision occur—by preventing the repeating of the conflict at the following concurrent starts of transmission attempts of the conflicting nodes which decreases the number of collisions. However, generally the percentage of the total number of eventuated conflicts with respect to the total number of channel access attempts is not considered to be a big percentage, as shown in Figure 8.Figure10 indicates the fairness of the backoff method with respect to the backoff delay computed as the standard deviation of the average backoff delay encountered by each node. As indicated by Figure 10, the u value has a noticeable impact on the backoff delay fairness among nodes as it controls modulating high values computed for the backoff to lower values specially the ID-dependent values and the effect of the integer uniform random number used in the first term of the backoff equation will be more apparent when u is big or u is small and N is big. When u is small and N less than 2mb-u, the backoff delay fairness is better at lower N values, while when N exceeds 2mb-u, a worse fairness obtained changes between fall and rise with increasing N but with small amount. When u is big the ID-dependent value, which is main contributor in differentiating backoff delays, is modulated to small range of values which causes more fairness at higher u values decreases when N increases due to the effect of the second term of the equation.Figure 10
CAM fairness with respect to backoff delay.After clarifying and proving the idea using simple assumption-based simulation scenarios, the subsequent sections consider a precious general modeling and evaluation of the CAM.


### 3.4. CAM Modeling

In this section, a Markov chain [34] model for the CAM will be implemented. Regarding the IEEE802.15.4 slotted CSMA/CA, the generalized model presented in [35] is used for its implementation; also this model is used as a basis for CAM modeling; this work represents a generalized accurate model which can be used for effective analysis in terms of reliability, delay, and energy consumption. It takes into account the full functionality of the protocol, the core of IEEE802.15.4 which is the exponential backoff process which is modeled, backoff stages limit, retry limits, acknowledgements, and unsaturated traffic.The state transition model represents the proposed CAM which is depicted in Figure11. As indicated in the model, the three-dimensional Markov chain is described using three stochastic processes, g(t), c(t), and y(t) which represent the backoff stage at time t, the state of the backoff counter at time t, and the state of retransmission counter at time t, respectively. The states from (i,1,j) to (i,2mb-1,j) are the backoff states, the states (Q0,…,QL0-1) consider the idle state when the queue is empty and the node is waiting for a new packet arrival, states (i,0,j) and (i,-1,j) represent the first and second CCA, respectively, and states (-1,k,j) and (-2,k,j) model the successful transmission and packet collision, respectively.Figure 11
State transition model for CAM.The MAC queue is assumed to be a first-in-first-out M/M/1 queue for both CAM and slotted CSMA/CA. The generated packets arrive at the queue with rate ofλ packets per second (pps). The mean service rate μ of the queue packets equals the reciprocal of the mean packet service time. Some of the notations used in the analysis throughout the paper are present in Notations.


#### 3.4.1. Computation of the Backoff Probability Distribution

In this section we are going to construct the probability distribution of the backoff period generated by a node in different backoff stagespKk∣I=i in case the node communicates with its sub-NW members and in case the node communicates with the Base Station (BS). To achieve that, the following definitions are introduced which are derived from generating the set of all possible backoff period values with experiments which consider all the possible combinations of the backoff equation variables’ values under specified conditions. The R language is used to generate these experiments outcome, and the relations which describe the probability distribution are derived from observing the pattern of these outcomes.In CAM, the receiving node identification,RID value, may vary through the successive backoff stages; especially, according to the previously proposed TSM, the receiving node in each receiving slot of the time frame is different; thus, the possible RID values in different backoff stages encountered by a node can be represented by a permutation (with repetition). The effect of the RID value on the value of the backoff periods computed by a node in different stages appears in the integer uniform random number clause in the first term of the backoff equation as an added value to the node ID. This added value, referred to as ADV, falls within a range; its lower bound is 0 and its upper bound depends on the RID value in the considered backoff stage with a maximum possible value equal to the number of the backoff stage; based on that, the range of ADV is indicated in the following definitions by its variable upper bound (UB).The following definitions find the probability of a certain backoff period value computed by a node in terms of the number of times this node computes it and the total number of the backoff periods computed by the node. The mathematical formulation of the backoff period probability depends on exploiting the recurrence of the combinations of variables cause a backoff value through a calculable number of repeating times rather than iteratively computes all the backoff values and then extracts the required information from them. This treats the problem of the long time consumed in iterative computation which may be considered as an almost infinite with the huge number of iterations corresponding to the huge number of variables’ combinations which increases inflation with increasing the nodes number and the backoff stages number. Simpler expressions to take smaller time for computing the number of occurrence times of a backoff value under certain conditions are depicted in AppendixA.Definition 1.
Letr(UB,s) be a function used to compute the number of RID values which result in a specific range of the ADV in a backoff stage s. Then r(UB,s) is a function of this range UB and it can be computed as follows:(2)rUB,s=Ns+1if  condition1  and  condition2  are  both  true  or  falseNs+1+1if  condition1  is  true  and  condition2  is  falseNs+1-1if  condition1  is  false  and  condition2  is  true,where condition1 is equivalent to Nmod(s+1)≥UB>0, condition2 is equivalent to UB=IDmod(s+1), and ⋯ is the floor function.Definition 2.
Letrnum(UB,s) denote the number of occurrence times of a specific range UB in a backoff stage s. Then rnum(UB,s) equals the number of RID values which result in the UB in the backoff stage s multiplied by the number of occurrence times of a RID value in a stage, and it is computed as follows: (3)rnumUB,s=rUB,sN-1S,where S is the stage at which we want to compute the backoff period, S∈[0,m], and s∈[0,S].Definition 3.
LetC be a two-dimensional array which represents the combinations of ADV through all stages from 0 to S. The array C has number of rows equal to (S+1)! indexed by ro, one row for each combination; accordingly the number of the columns of C equals S+1 indexed by co.
LetV be a set of S+1 vectors, where V=v0,v1,…,vS. Vector vs represents the maximum range of ADV in stage s which is 0,s.
If we denote the number of occurrence times of one combination corresponding to a rowro in C by cnum(ro), then cnum(ro) equals the maximum number of occurrence times of a combination corresponding to a row in C multiplied by the probability of occurrence of the intended combination corresponding to a row ro:(4)cnumro=max⁡rnum∏z=1S+1∑e=1cro,z≤vez-1zrnumvez-1,z-1N-1S+1=N-1S+1∏z=1S+1∑e=1cro,z≤vez-1zrnumvez-1,z-1N-1S+1,where cro,z is the element of the array C at the row number ro and column number z and vez-1 is the element number e in the vector v which corresponds to stage number z-1.Definition 4.
Let the total number of occurrence times of the set of all possible backoff period values of an experiment outcome be denoted by the notationtknum(S). Then tknum(S) equals the sum of the number of occurrence times of all the ADV combinations which constitute the rows of C multiplied by the number of the combinations of the time units used to perform CCA through a number of S stages; namely,(5)tknumS=2S∑ro=1S+1!cnumro,for every ID∈1,N, u∈0,2mb-1, and S∈0,m.Definition 5.
Let the number of occurrence times of a possible backoff period valuek of an experiment outcome be denoted by the notation knum(k,S), and let the 2S-by-S matrix A represent all the combinations of the number of the time units used to perform CCA in all stages; then for every ID∈[1,N], u∈0,2mb-1, S∈0,m, and Aaro∈A,(6)knumk,S=∑ro=1k=bfroSS+1!cnumro,where(7)bfroS=ID+cro,S+1mod2mb-u+bfsumSmodu+1,bfsum0=0,bfsumS=∑co=1SID+cro,comod2mb-u+bfsumco-1modu+1+aaro,cowhenS>0.The previous definitions relate the communication within the sub-NW; the following definitions, Definitions6 and 7, consider the communication with the BS distinguished by the existence of only one possible receiver, which is the BS, identified by 0; therefore in this case, RID always equals 0.Definition 6.
Let the total number of occurrence times of the set of all possible backoff period values of an experiment outcome, due to the communication with the BS, be denoted by the notationbstknum(S); then bstknum(S) is defined as(8)bstknumS=2S,for every ID∈1,N, u∈0,2mb-1, and S∈0,m.Definition 7.
Let the number of occurrence times of a possible backoff period valuek of an experiment outcome, due to the communication with the BS, be denoted by the notation bsknum(k,S), and let the 2S-by-S matrix A represent all the combinations of the number of the time units used to perform CCA in all stages; then for every ID∈1,N, u∈0,2mb-1, S∈0,m, and Aaro∈A,(9)bsknumk,S=∑k=bfS1,where (10)bfS=IDmod2mb-u+bfsumSmodu+1,bfsum0=0,bfsumS=∑co=1SIDmod2mb-u+bfsumco-1modu+1+aaro,cowhenS>0.Definition 8.
The probability distribution of the backoff period generated by a node in different backoff stagespKk∣I=i is computed as follows: for every k∈0,2mb-1 and i∈0,m,(11)pKk∣I=i=1N∑ID=1Nknumk,itknumifor  sub-NW  communication,pKk∣I=i=1N∑ID=1Nbsknumk,ibstknumifor  communicating  BS.


#### 3.4.2. Deriving the Stationary Distribution

The nonzero state transition probabilities associated with the CAM Markov chain of Figure11 represent the state transition due to decrementing the backoff counter by one, the transition from one backoff stage to the next one due to sensing the channel busy, the transition from one transmission trail to the next one due to collision occurrence, the transition after channel access failure to the queue idle state, the transition after transmission failure to the queue idle state, the transition to the queue idle state after the maximum backoff stage in the last transmission trial, and finally the transition from the idle state to the first backoff stage in the first transmission trial; these probabilities are described by (12)–(18),(12)Pi,k,j∣i,k+1,j=1for2mb-1≥k≥0,(13)Pi,k,j∣i-1,0,j=α+1-αβpKk∣I=ifori≤m,(14)P0,k,j∣i,0,j-1=P1-α1-βpKk∣I=0forj≤n,(15)PQ0∣m,0,j=q0α+1-αβforj<n,(16)PQ0∣i,0,n=q01-α1-βfori<m,(17)PQ0∣m,0,n=q0,(18)P0,k,0∣Q0=1-q0pKk∣I=0for2mb-1≥k≥0.The following analysis is concerned with finding the closed form for the stationary distribution of the CAM Markov chain (bi,k,j), where bi,k,j=limt→∞P(g(t)=i,c(t)=k,y(t)=j), i∈(-2,m), k∈(-1,max⁡(2mb-1,Ls-1,Lc-1)), and j∈(0,n). Using (12)–(18) and due to the regularity of the chain, from (13), for 0<i≤m,0≤j≤n,2mb-1≥k≥0, we have(19)bi,k,j=bi-1,0,jα+1-αβ∑r=k2mb-1pKr∣I=i,(20)bi,0,j=α+1-αβbi-1,0,j,and then by recursive application and substitution of (20) for successive backoff stages, we can conclude that(21)bi,0,j=α+1-αβib0,0,j;let α+(1-α)β=x; from (19), (20), and (21) we have(22)bi,k,j=xib0,0,j∑r=k2mb-1pKr∣I=i.From (14) we have(23)b0,k,j=P1-α1-β∑r=k2mb-1pKr∣I=0∑i=0mbi,0,j-1=b0,0,j∑r=k2mb-1pKr∣I=0,and then from (22) and (23), for 0≤i≤m,0≤j≤n,2mb-1≥k≥0,(24)bi,k,j=xib0,0,j∑r=k2mb-1pKr∣I=i.From (14) and (21) we have(25)b0,0,j=1-xP∑i=0mxib0,0,j-1=1-xm+1Pb0,0,j-1;let (1-xm+1)P=y, and by recursive application and substitution of (25) for successive transmission trials, we can conclude that(26)b0,0,j=yjb0,0,0;then from (24) and (26), (24) can be rewritten as (27)bi,k,j=xiyjb0,0,0∑r=k2mb-1pKr∣I=i.We next derive the expression of b0,0,0 by applying the normalization condition: (28)∑j=0n∑k=02mb-1∑i=0mbi,k,j+∑i=0m∑j=0nbi,-1,j+∑j=0n∑k=0Ls-1b-1,k,j+∑k=0Lc-1b-2,k,j+∑l=0L0-1Ql=1;after deriving the expression of each term in (28) in terms of the probability b0,0,0 and substituting with them on it, we obtain(29)b0,0,0=1-yn+11-y∑k=02mb-1∑i=0mxi∑r=k2mb-1pKr∣I=i+1-α1-xm+11-x1-yn+11-y+1-xm+11-PLs+PLc1-yn+11-y+L0q01-q01-yn+11-yxm+1+P1-xm+1yn+1-P1-xm+11-yn+11-y-1.


### 3.5. Single-Hop Communication Analysis

The single-hop communication scenario considers a number of nodesN which are reachable from each other; when each node has data to transmit, it contends with the others in accessing the shared channel according to the behavior described by the employed Markov chain models for slotted CSMA/CA and CAM. This section concerns the derivation of the required performance metrics expressions, starting with finding expressions for some of the models’ related probabilities required in the performance analysis implementation.


#### 3.5.1. Deriving Expressions for the Models’ Different Associated Probabilities

The derivations ofτ, α, β, and P for both slotted CSMA/CA and CAM are the same as done in [35], where(30)τ=∑i=0m∑j=0nbi,0,j=1-xm+11-x1-yn+11-yb0,0,0,P=1-1-τN-1,α=P1st  CCA  busy  due  to  data  transmission+P1st  CCA  busy  due  to  ACK  transmission=L1-1-τN-11-α1-β+LackNτ1-τN-11-1-τN1-1-τN-11-α1-β,β=1-1-τN-1+Nτ1-τN-12-1-τN+Nτ1-τN-1.The mean packet service time E[S] takes into account the probability that the serviced packet may be transmitted successfully or discarded due to reaching transmission retry limit or channel access failure, and the average time taken in each case from the instant the packet is at the head of the queue is different, (31)∴ES=RED+Pcrn+1Lc+ETh+Pcf∑j=0n1-y1-yn+1yjjLc+ETh+∑i=0m∑r=02mb-1rpKr∣I=i+TSC∑e=12m+1Cαβem+1Nαem+1+2Nβem+1.The Matlab is used for solving the nonlinear system of equations represented by τ, α, β, and q0 expressions.


#### 3.5.2. Reliability Analysis

The derivation of the reliability, which is the probability of successful packet reception, for both slotted CSMA/CA and CAM, is the same as done in [35], where(32)R=1-Pcf-Pcr=1-xm+11-yn+11-y-yn+1.


#### 3.5.3. Delay Analysis

The average delay is defined as the time interval from the instant at which the data packet is at the head of the MAC queue ready to be transmitted until its acknowledgement is received. The derivation of the average delay expression is the same as done in [35] for both slotted CSMA/CA and CAM, except for the term in the equation of E[Th] which refers to the backoff time; in CAM case this term equals (for complete derivation see [35])(33)1∑i=0mCαβi∑i=0m∑e=12iCαβei∑l=0i∑r=02mb-1rpKr∣I=l.


#### 3.5.4. Energy Consumption Analysis

The average energy consumption is computed from (34), where Ei, Esc, Et, Er, and Esp are the average energy consumption in idle-listen, channel sensing, transmit, receive, and sleep states, respectively. Esp term is neglected: (34)E=Ei∑i=0m∑k=12mb-1∑j=0nbi,k,j+Esc∑i=0m∑j=0nbi,0,j+bi,-1,j+Et∑j=0n∑k=0L-1b-1,k,j+b-2,k,j+Ei∑j=0nb-1,L,j+b-2,L,j+∑j=0n∑k=L+1L+Lack+1Erb-1,k,j+Eib-2,k,j+Esp∑l=0L0-1Ql.


#### 3.5.5. Throughput Analysis

The throughput, which is defined as the fraction of channel time used to successfully transmit data payload bits in unit time, is computed from(35)TH=PsuccessPbusyL1-PbusySb+PsuccessPbusyLs+Pbusy1-PsuccessLc,where Pbusy is the probability that there is at least one transmission in the considered unit time and it equals 1-1-τN; Psuccess is the probability of successful data transmission conditioned by the fact that the channel is busy and it equals Nτ1-τN-1/Pbusy; the denominator of TH considers that the channel time has different probabilities of being free or busy with failed or successful transmission.


### 3.6. Multihop Communication Analysis

The aim of this section is to analyze the end-to-end performance of the proposed CAM when the packet is forwarded through intermediate node(s) to reach the final destination for comparing the CAM performance against the slotted CSMA/CA in multihop topology. The algorithmic technique of “divide and conquer” is used for finding the end-to-end performance, where the multihop path is partitioned into a number of single-hops solved using the previous analysis with adjusting the model parameters and may be with some modifications according to the employed topology; then the solutions obtained for each single-hop are appropriately merged to obtain the end-to-end multihop performance.Figure12 presents examples for the employed topology for each protocol; the topology of the slotted CSMA/CA is the logical topology for it which is the cluster-tree. The proposed CAM topology is constructed by dividing the network into subnetworks, each one works on a different frequency channel, some members are BS-neighbors, and its members work on our previously proposed TSM [11]. The time slot equals the time of one transmission, and no interaction between the sub-NWs is assumed. The number of the BS-neighbors in all the sub-NWs is approximately equal, and the number of the non-BS-neighbors in all the sub-NWs is also approximately equal. In CAM, no attention is given to a specific routing technique, that is, no determinants of the next hop; also in CSMA/CA, no determinants imposed for selecting the parent coordinator from the discovered ones.Figure 12
Multihop network topologies (a) for CAM network and (b) for slotted CSMA/CA cluster-tree network.
(a) (b)In the two topologies, when a node has a packet at the head of the queue ready to be sent, it can immediately start its transmission process to the currently listening receiver; that is, all the intended receivers in any time are available; no sleeping schedule causes deferring of a transmission process, such that only the effect of the medium access method is considered. The nodes are deployed uniformly; the nodes which have the capability of coordinator represent 25% of the total nodes number and are deployed independently uniformly throughout the area.The starts of the first packet generation of all the sub-NW members are separated by an ignorable time; accordingly the generation repetitions will be separated by an ignorable time. The cluster-tree formation and communication as well as the communication between sub-NWs’ BS-neighbors and the BS are performed using −15 dBm, while the communication among sub-NWs’ members is performed using a greater transmission power level −10 dBm for assuring the reachability of the receiving node at any time.The following sections concern deriving expressions for the multihop performance metrics for both the slotted CSMA/CA network and the CAM network. The multihop network topology imposes changes in each node variables and the communication conditions from one network to the other or may be from one hop to another in the same network, such as the existence of different degrees of neighborhood to a transmitting node which raises the existence of hidden nodes, different packet arrival rates, and different number of contended nodes. Section3.6.1 analyzes the effect of multihop communication on the two networks’ models associated probabilities. Sections 3.6.2 to 3.6.5 analyze the end-to-end reliability, delay, energy consumption, and throughput; the same definitions and computation are used for finding these slotted CSMA/CA and CAM end-to-end performance metrics except few indicated differences.


#### 3.6.1. Deriving Expressions for the Models’ Different Associated Probabilities

In this section, the derivations ofα, β, and P for both slotted CSMA/CA and CAM will be introduced.(1) Slotted CSMA/CA End-to-End Analysis. In the cluster-tree slotted CSMA/CA network and by assuming that the number of each cluster end devices members Id is approximately equal and the number of children coordinators Ic varies from 0 to a constant maximum limit for each coordinator, the packet arrival rate at the MAC queue differs from the end device λd to the coordinator λc; also if no aggregation is assumed, it will differ for coordinators at different levels, but it may differ in case of aggregation employed from coordinator to another one if their Ic values are different. The packet generation rate λ at each node is equal, in each time unit the network will have the number of packets described by λ generated from each node, and in computing the approximate value of the packet arrival rate at a node, it is assumed that all the transmitted packets to this node will be delivered successfully. The packet arrival rates are computed as follows:(36)λd=λ,λci=λ1+Id+Iciif  aggregation  is  assumed,λci=λ1+Id+Icitotal1+Idif  no  aggregation  is  assumed,where Icitotal represents the number of the coordinators below the coordinator i in its tree branch, its children coordinators, its grandchildren coordinators, the children of its grandchildren coordinators, and so on.According to the packet arrival rate and the different neighborhood of each node and its neighbors, the node will have its own probabilities ofτ,α,β, and P. The neighborhood of a transmitting node, its receiver’s neighborhood, and the neighborhood of its receiver’s neighbors are distinguished by defining some sets of nodes, each one has an effect on the transmitting node packet; these sets are Φt,Φtc,Φtr,Φhtr,Φhctr,ψc,Ct, and C.The setΦt defines the neighborhood of a node t, which are the nodes surrounding this node that can hear its transmissions and likewise it can hear their transmissions (the neighbor coordinators are discriminated by Φtc and incorporate the BS), the set Φtr defines the common neighborhood of the nodes t and r (Φtr=(Φt∩Φr)), the set Φhtr defines the hidden nodes from the node t with respect to the transmission to node r including the BS, the set Φhctr defines the hidden coordinators from the node t with respect to the transmission to node r including the BS, the set ψc defines the set of coordinator c children from devices and coordinators, the set Ct is a set of one element corresponding to the coordinator of node t, and the set C defines the set of all coordinators in the network.(a) The Collision Probability. The collision probability related to node t is the probability that node t encounters a collision on a transmitted packet to its coordinator, and it is denoted by Pt. The collision probability Pt is given by (37)Pt=PCsenset+1-PCsensetPChDatat+1-PCsenset1-PChDatatPChAckt,where PCsenset is the collision probability of a transmitted packet from t to r due to concurrent channel sensing, PChDatat is the collision probability of a transmitted packet from t to r due to hidden data transmission starts before or after the beginning of the packet transmission, and PChAckt is the collision probability of a transmitted packet from t to r due to hidden acknowledgement transmission starts before or after the beginning of the packet transmission.The probabilityPCsenset considers the probability that at least one node from the common neighborhood of the transmitter and the receiver (except the BS) transmits at the same time slot. If each node in the common neighborhood senses the channel with its own probability τ, PCsenset is computed from(38)PCsenset=1-∏j∈Φtr,j≠BS1-τj.Hidden acknowledgements to the transmittert resulted from successful data reception at the hidden coordinators from t upon which they transmit acknowledgements received at its receiver r and collide with its data. The probability PChAckt is given by(39)PChAckt=PSRht1-∏k∈⋃h∈Φhctrψh1-τk∑q=1⋃h∈Φhctrψh∑m=1Cq⋃h∈Φhctrψh∏i∈dmdm=dm,1,dm,2,…,dm,qτi∏j∈⋃h∈Φhctrψh∖dm1-τj1-∏n∈dmdm=dm,1,dm,2,…,dm,qαn+1-αnβn,where ⋃h∈Φhctrψh stands for the size of the set of nodes which represents the union of all the sets which contain the children of the hidden coordinators from t, Cq⋃h∈Φhctrψh represents the number of combinations of size q from the set ⋃h∈Φhctrψh, dm represents the combination number m of size q, and they are used in (39) to calculate the probability of at least one node from the set ⋃h∈Φhctrψh which begins a transmission. The notation PSRht represents the probability of successful data reception at the hidden coordinators from t and it is defined in Appendix B.The probabilityPChDatat is the probability of at least one from the hidden nodes to t which begins a transmission in any time unit of a time duration equal to the average channel occupation of a data transmission before the beginning of t transmission and one after it. The probability PChDatat is calculated from (40)PChDatat=2L∑q=1Φhtr∖BS∑m=1CqΦhtr∖BS∏i∈kmkm=km,1,km,2,…,km,qτi∏j∈Φhtr∖km∪BS1-τj1-∏n∈kmkm=km,1,km,2,…,km,qαn+1-αnβn,where CqΦhtr∖BS represents the q-combinations from the hidden nodes to t excluding the BS and it equals the number of rows of the matrixK where each row contains one different combination.(b) Probability of Finding the 1st CCA Busy. The equation of αt which is the probability of node t finds the 1st CCA busy which comprises the probability to find it busy due to data transmission (α1t) and the probability to find it busy due to acknowledgement transmission α2t, (41)αt=α1t+1-α1tα2t,α1t=L∑q=1Φt∖BS∑m=1CqΦt∖BS∏i∈kmkm=km,1,km,2,…,km,qτi∏j∈Φt∖km∪BS1-τj1-∏n∈kmkm=km,1,km,2,…,km,qαn+1-αnβn,α2t=PSRt1-∏k∈⋃h∈Φtcψh∖t1-τk∑q=1⋃h∈Φtcψh∖t∑m=1Cq⋃h∈Φtcψh∖t∏i∈dmdm=dm,1,dm,2,…,dm,qτi∏j∈⋃h∈Φtcψh∖dm∪t1-τj1-∏n∈dmdm=dm,1,dm,2,…,dm,qαn+1-αnβn,where CqΦt∖BS and Cq⋃h∈Φtcψh∖t represent the q-combinations from all the neighbors of t excluding the BS and all the children of the neighbor coordinators of t excluding t itself, respectively. The notation PSRt represents the probability of successful data reception at the coordinators of node t neighborhood and it is defined in Appendix B.(c) Probability of Finding the 2nd CCA Busy. The probability βt, which is the probability of node t finding the 2nd CCA slot (denoted as CCA2) busy given that the 1st CCA slot (denoted as CCA1) was idle, is derived in the same fashion used in [36] but with considering the different neighborhood and other different values the nodes have.The node can assess its 2nd CCA busy in two cases, the first one occurs if some other nodes in the medium were sensing their 2nd CCA during this node 1st CCA and started a new transmission in the node’s 2nd CCA slot. This can only happen if the other node started sensing in the slot just before the intended node 1st CCA slot (denoted as slot1) and the channel was then idle. The second case of assessing the 2nd CCA busy occurs when the 1st CCA idle slot was the slot between data transmission and acknowledgement (the probability of the second case occurrence is denoted byPbetaACK); then(42)βt=PIslot1∣ICCA1PSslot1+PbetaACK,where Islot1 and ICCA1 are the events of finding slot1 and CCA1 idle, respectively; the event Sslot1 is the event of start sensing in slot1.The conditional probabilityP(Islot1∣ICCA1) is the probability that a given idle slot is preceded by another idle slot,(43)PIslot1∣ICCA1=1-PBslot1∩ICCA1PICCA1=1-PBslot1∩ICCA1PBslot1∩ICCA1+PIslot1∩ICCA1,where Bslot1 it the event of finding slot1 busy; then βt can be rewritten as(44)βt=1-PBslot1∩ICCA1PBslot1∩ICCA1+PIslot1∩ICCA1PSslot1+PbetaACK.The eventICCA1 occurs in four cases.Case 1.
A busy slot before the idleCCA1 because of a failed packet transmission due to collision: this is represented by the probability PbusyFt for node t.Case 2.
A busy slot before the idleCCA1 because of an acknowledgement following a successful data transmission: this is represented by the probability PbusyAt for node t.Case 3.
A busy slot before the idleCCA1 because of a successful packet transmission where the idle slot is the interframe space in between data and acknowledgement: this is represented by the probability PbusySt for node t.Case 4.
An idle slot before the idleCCA1 happened after an acknowledged successful transmission or an unacknowledged unsuccessful transmission: this is represented by the probability Pidlet for node t.Substituting with these probabilities in (44), we have(45)βt=1-PbusyFt+PbusyAt+PbusyStPbusyFt+PbusyAt+PbusySt+Pidlet1-∏j∈Φt,j≠BS1-τj+PbusyAtPbusyFt+PbusyAt+PbusySt+Pidlet,and the expressions which define these probabilities are presented in Appendix B.(2) CAM End-to-End Analysis. In CAM, the packet generation rate λ at each node is equal, in each time unit the network will have the number of packets described by λ generated from each node, the time unit described by λ equals multiples of the TSM frame greater than λ multiplied by maximum number of allowed hops through a sub-NW, and in computing the approximate value of the packet arrival rate at a node it is assumed that all the transmitted packets to this node will be delivered successfully. It is assumed that if the BS-neighbors number does not represent the larger share in a sub-NW, they transmit their packets directly to BS and are not allowed to use multihops. The topology does not imply a specific form of doing aggregation; the routing may determine that, so no aggregation is assumed.The number of the sub-NW non-BS-neighbor members is denoted byIo and the number of the BS-neighbor members is denoted by IBS. The average packet arrival rate at the BS-neighbors λBS is greater than that of the non-BS-neighbors λo as they represent the critical zone around the BS and it depends on both Io and IBS. The whole path taken by a transmitted packet lies in a specific sub-NW, except the last hop where the last hop source, which is a BS-neighbor, switches its working channel to the working channel of the BS.Assume that a one hop of packets transmitted from each non-BS-neighbor node is completed approximately within a TSM frame time and when each node succeeds to send its packet, whether generated or forwarded, it sends it to a receiver different from whom its peers send to, whether this receiver is a BS-neighbor or not. According to that, at the completion of one packet transmission from each node, the non-BS-neighbor node will receive a number of packets ranges from 0 to(lmax-2), where lmax is the maximum path length. The final intermediate node is a BS-neighbor and the average number of packets received by a BS-neighbor in a completion of each non-BS-neighbor nodes one packet transmission is approximately equal to the number of non-BS-neighbors divided by the number of BS-neighbors in the sub-NW. Based on the previous considerations, the average packet arrival rates λo and λBS are computed as follows:(46)λo=λ1+∑x=0lmax-2xlmax-1,λBS=λ1+IoIBS.(a) Deriving Non-BS-Neighbor Different Associated Probabilities. The probability of collision of a non-BS-neighbor transmitted packet depends on the number of non-BS-neighbors in its receiver neighborhood in its sub-NW and their values of τ. For simplicity and to encounter the problem of hidden nodes to the transmitter, it is assumed that all the non-BS-neighbor members always transmit with its full range (or a range enough for covering the whole employed field), therefore no hidden nodes to the transmitter. In case the receiving node is a BS-neighbor, the number of competing nodes Ncp with a node tries to transmit will be equal to (Io-1), and in case of its being a non-BS-neighbor, Ncp equals (Io-2). Under the previous assumptions, the derivation of α, β, and P for a non-BS-neighbor is turned to be the same as followed in the single-hop communication analysis with notations and values of variables indicate a non-BS-neighbor in a sub-NW: (47)Po=1-1-τoNcp,αo=L+LackIoτo1-τoIo-11-1-τoIo1-1-τoIo-11-αo1-βo,βo=1-1-τoIo-1+Ioτo1-τoIo-12-1-τoIo+Ioτo1-τoIo-1.(b) Deriving BS-Neighbor Different Associated Probabilities. The probability of collision of a BS-neighbor transmitted packet depends on the number of BS-neighbors in all the sub-NWs and their values of τ. If the number of sub-NWs is denoted by Ns, then the number of BS-neighbors equals IBSNs; some of them may be hidden to others, where ΦtBS represents the common neighbors between the BS-neighbor t and the BS and ΦhtBS represents the hidden BS-neighbors to the BS-neighbor t. The probabilities α, β, and P are derived in the same fashion as they are derived in case of slotted CSMA/CA; except here there is no hidden acknowledgement; the set of all the children of the neighbor coordinators contains only the BS-neighbors and is defined by ΦtBS∪ΦhtBS; and successful concurrent transmissions from even two nodes do not exist.


#### 3.6.2. End-to-End Reliability Analysis

The end-to-end reliabilityRe-to-e is the ANDing and in other words, the product of the probabilities of successful packet reception at each intermediate node in the considered path then to the BS,(48)Re-to-e=∏n=1lRn,where l is the path length in terms of its incorporated nodes number excluding the final destination which is the BS, Rn is the single-hop reliability of the transmitted packet by the node number n in the path, then R1 is corresponding to the first node in the path which is the source node, and Rl is corresponding to the last node in the path which is a BS child coordinator.


#### 3.6.3. End-to-End Delay Analysis

By ignoring the processing delay, the average end-to-end delayDe-to-e is the summation of the average delays for successfully delivering the packet (D) at each node in the path including the PAN coordinator (BS) and the average queuing delay (w=λ/μ/μ-λ) at each intermediate node in the path, where λ here refers to the queue packet arrival rate and μ is the packet service rate.(49)De-to-e=∑n=1lwn+Dn.The channel switching time is added to the end-to-end delay in CAM case to incorporate the effect of a BS-neighbor switching to the BS channel to send its data to it (channel switching time is approximately the transmission time of a 32 byte (~1 ms) [37]).


#### 3.6.4. End-to-End Energy Consumption Analysis

The total energy consumed to relay the packet through the path towards the BS is assumed to be the summation of the total energy consumed by each node in transmitting the packet to the next-hop node. For simplicity, the switching between frequency channels is assumed to consume ignorable energy:(50)Ee-to-e=∑n=1lEn.


#### 3.6.5. Network Throughput Analysis

The normalized system throughput is defined and calculated here in the same way used for single-hop analysis; the difference is in the definition ofPbusy and Psuccess. If we denote the set of all nodes in the network (except BS and PAN coordinator) by Φtotal, here(51)Pbusy=1-∏i∈Φtotal1-τi,Psuccess=∑i∈ΦtotalPSTiPbusy,where PSTk, as defined in Appendix B, is the probability of successful transmission by a node.Another metric used to measure the network productivity is the goodput defined as the data bits successfully received at the BS in one time unit. The network goodputG (in bits/sec) is the summation of all nodes goodputs; let On be the set of all possible paths for delivering data from node n to the BS; then(52)G=L×20×4∑n∈Φtotal∑r∈OnRe-to-en,rDe-to-en,r.


## 3.1. Overview of the Beacon-Enabled IEEE802.15.4 Slotted CSMA/CA

The IEEE802.15.4 standard specifies the physical layer and media access control layer for low-rate wireless personal area networks (LR-WPANs), and based on it, other standards which define the upper layers of the stack are developed, such as ZigBee [28], ISA100.11a [29], WirelessHART [30], MiWi [31], and 6LoWPAN [32].The IEEE802.15.4 network can operate in two modes of operation beacon- or nonbeacon-enabled modes. In nonbeacon-enabled mode, the peer-to-peer data transfer model, in which the devices wishing to communicate need to receive constantly and simply transmit its data using unslotted CSMA/CA, is employed. Indeed, this consumes more nodes’ energy as undesirable manner for battery-powered nodes. The beacon-enabled mode is more suitable for battery-powered nodes, where in this mode, a star topology is formed between devices and a single central controller, called the coordinator; these devices are allowed to sleep most of their times, while the coordinator listens to the channel for a longer time but also is allowed to sleep periodically. The coordinator bounds its channel time using a superframe structure bounded by the transmission of a beacon frame.In beacon-enabled mode, the slotted CSMA/CA channel access mechanism, in which units of time called backoff periods (backoff slots) are aligned with the start of the beacon transmission and each time a device wishes to transmit data frames, it shall locate the boundary of the next backoff slot and then wait for a random number of backoff slots. If the channel is idle, the device can begin transmitting on the next available backoff slot boundary; otherwise, following this random backoff, the device shall wait for another random number of backoff slots before trying to access the channel again. Each device shall maintain three variables for each transmission attempt:NB, CW, and BE:N B holds the number of times the CSMA/CA algorithm attempts to access the channel to transmit the current packet and it is initialized to zero before every new transmission. The value of the attributemacMaxCSMABackoffs determines the maximum value for this variable; that is, it determines the number of allowed attempts for CSMA/CA algorithm to access the channel to send a packet before reporting channel access failure; if the value of NB is greater thanmacMaxCSMABackoffs, the CSMA/CA algorithm shall terminate with a CHANNEL_ACCESS_FAILURE status.C W defines the fixed number of backoff periods that the channel has to be idle before a node can start to transmit and in the standard it is set to 2 backoff periods. According to that, it is initialized to 2 before each transmission attempt and reset to 2 each time the channel is assumed to be busy.B E refers to the backoff exponent, a basis of two is raised to the BE power (2BE) to indicate the count of possible backoff periods number, and the CSMA/CA can randomly choose one from them to wait this chosen backoff periods number before attempting to assess the channel. This count (2BE) represents a range of consecutive numbers of backoff periods beginning from 0 backoff period and so ending with (2BE-1) backoff period. Each channel access attempt failure for a transmission, BE, is incremented by one to double the range of possible backoff periods numbers but up to a maximum value equal to the value of theaMaxBE constant beyond which its value is frozen, and also it has a minimum value,macMinBE (referred in the paper as m0).The slotted CSMA/CA purposes making the performing of the Clear Channel Assessment (CCA) and starting of packet transmission operations of nodes be aligned, consequently, overlap of CCA operations will not occur, and neither false idle channel assessment nor collisions may occur. Not only does the synchronization of backoff periods achieve that, but also the choice of the unit backoff period value affects this aim. The value of the backoff period is selected to be equal to a CCA duration plus a turnaround time for changing the transceiver to the transmit state which is the time taken by the node to be ready for the transmission start. So the backoff period equals 20 symbol as shown in Figure2.Figure 2
Illustration of the backoff period.If it is said that small backoff period is better to decrease the delay, the reply will be that if the backoff period is smaller than 20 symbols there will be an overlap among the CCA and turnaround times of nodes as shown in Figure3. Node 2 sensed the channel idle and started to turn its transmitter on; during that Node 1 was assessing the channel and its assessment ended before or on or just after the time Node 2 began to send, and it did not hear its transmission and proceeded to transmit. The same thing can happen between Node 1 and Node 3. Although the nodes started to assess the channel in different backoff periods, they collided.Figure 3
The effect of a backoff period smaller than 20 symbols.The backoff period should not also be greater than 20 symbols. A greater period, as illustrated in Figure4, increases the delay which resulted from the backoff time and from locating the next backoff slot boundary without any additional beneficial effect on preventing the channel sensing overlap and collisions.Figure 4
The effect of a backoff period greater than 20 symbols.TheCW is selected to be 2 backoff periods; that is, the node should be sure that two idle CCA operations were performed before the beginning to transmit for preventing potential collisions of acknowledgement frames. If the reception of a packet had been completed at a node before the backoff period boundary at which it began to perform its CCA and accordingly its reception had been completed at its destination node before the same backoff boundary (this packet can be undeliverable by this node which wants to transmit while its acknowledgement is deliverable; that is, the source node of the acknowledged packet can be out of the range of the node wants to transmit, but the node wants to transmit and its intended receiver fall in the range of the destination node), an overlap would occur between the delay consumed by the destination node computed starting from the time of packet reception completion and represented in the turnaround time and the backoff period boundary locating delay to start sending the required acknowledgement and the CCA of the node wants to transmit which sensed the channel idle while an acknowledgement was going to be transmitted. If this node does not perform a second CCA, it will start to transmit its packet with the destination node acknowledgement transmission and a collision would occur, as illustrated in the Figure 5.Figure 5
Illustration of the importance of performing two CCAs.


## 3.2. Backoff Method Explanation

In the proposed backoff method, the node computes the backoff time in each backoff stage from(1)bfs=ID+intuniform0,RIDmods+1mod2mb-u+∑j=0s-1bfj+ccajmodu+1,where bf(s) is the function used by a node to compute its backoff time in a backoff stage s, s is the index of the backoff stage in range 0,m, ID refers to the identification of the node computes the backoff period, RID refers to the identification of a receiving node, and cca(s) is a function which gives the time spent in channel sensing in stage s. In the analysis, the clause ∑j=0s-1bf(j)+cca(j) is referred to as “the backoff sum” and denoted by bfsum(s).The first term of the equation aims to make the backoff time of each node different from the others by making it dependent on their different identification numbers, so that if more than one node have data to send at the same time, they wait different time periods before starting to sense the channel.The integer uniform random number,intuniform0,RIDmod(s+1), used in the first term depends on the identification of the receiving node. The purpose of this is to differentiate the backoff time of a certain node with the passage of time, taking advantage of the presence of different receiving nodes, so that no node always has to wait a bigger time than its competitors; and this prevents the error repeating by backing off the same period each backoff trial after an overlapped sensing is done. But this random number is limited to a certain range by considering the modulus of RID and a certain value made to be dependent on the index of the backoff stage also in order to differentiate the backoff with time and so that the possible range to a node is allowed to become greater each backoff trial.The second term of the equation considers the fact that the nodes may have data to send already in different times but their different computed backoff delays make them start sensing the channel at the same time. Therefore, this term makes the backoff times chosen by the nodes depends on their starting time of having the data which is different among them; in this case, this is achieved by taking the sum of the delays which resulted from the previously encountered backoff stages for this data (if any).For limiting the backoff time to a certain maximum limit, regardless of the values of nodes’ IDs, the modular arithmetic is involved in the two terms of the equation, and the maximum limit is selected to be as the maximum limit of backoff in the IEEE standard which equals (2mb-1), where mb is the maximum backoff exponent.The moduli of the modular operations determine the range of each equation’s term resultant values; therefore it is made to be dependent on a parameteru which controls the maximum value of each term. The increase in u value increases the maximum value of the second term while decreasing that of the first term and vice versa; by the same logic, u is used as a tuning parameter for performance metrics. The range of u is [0,2mb-1]; the values of the two variables ID and RID fall in the range [1,N], where N is the number of nodes in the sub-NW, assumed to fall within range 2,∞.


## 3.3. Using R Language to Simulate Nodes’ Backoff

A code in R language [33] was written to simulate the nodes’ backoffs upon (1) and quickly manifest their corresponding behavior and its impact on star topology data transmission specially with respect to the eventuating of collisions and channel access overlap at different simple assumption-based scenarios.The code assumes that each node takes its turn as a star topology receiver upon a predetermined schedule for a period equal to a complete transaction (13-backoff unit). The node does not start a transmission process until it finishes its receiving slot. Packet generation is exponentially distributed over nodes with rate equal to 1 and limited to be 1 packet per node over the simulation time. The packet generation time for all nodes is limited to be within a certain period from the start time to guarantee that all nodes will have data to send during the test period. There is only one transmission trial but a number of backoff stages are allowed. The considered parameters are computed by averaging the outputs of a number of code runs (in each run the time of having data for each node is changed).By settingm to 5, mb to 5, u to 5, and the time within which each node will generate a packet to 1240 backoff unit, Figure 6 shows that the average number of collisions increases polynomially with the increase of the number of contending nodes with instantaneous rate of change linearly increases with increasing nodes number. This increase of collisions number and the inherent increase of nodes number which cause the collision’s conflict result in the increase of the loss percentage due to collisions occurrence; as shown in Figure 7, the loss percentage reached approximately 13% when nodes number is 70.Figure 6
CAM average number of collisions versus number of nodes.Figure 7
CAM loss percentage due to collision versus number of nodes.Figure8 shows the percentages of both the total number of time slots which encounter overlap in transmission attempts’ starts and the number of time slots which cause concurrent channel access and accordingly collisions with respect to the total number of channel access attempts. While Figure 9 draws the number of collision-prone transmission attempts which encounter conflict at the start of backoff computation and the number of collision-raiser time slots, this is computed with restricting the time of nodes’ start data generation to a small period to increase the chances of concurrent transmission and channel access attempts.Figure 8
CAM percentages of collision-prone and collision-raiser situations.Figure 9
CAM number of collision-prone and collision-raiser situations.It is apparent from Figure9 that the number of collisions happened is smaller with a big percentage than the number of chances that would cause them if the conflicting nodes select similar backoff periods. It could be said that the backoff method solves approximately, on average, 80.8% of the channel access conflict situations encountered; actually some of these situations are originally caused by the backoff method itself due to its incapability to perfectly prevent conflicts, but it is able to mend from this—if the channel is found busy and no collision occur—by preventing the repeating of the conflict at the following concurrent starts of transmission attempts of the conflicting nodes which decreases the number of collisions. However, generally the percentage of the total number of eventuated conflicts with respect to the total number of channel access attempts is not considered to be a big percentage, as shown in Figure 8.Figure10 indicates the fairness of the backoff method with respect to the backoff delay computed as the standard deviation of the average backoff delay encountered by each node. As indicated by Figure 10, the u value has a noticeable impact on the backoff delay fairness among nodes as it controls modulating high values computed for the backoff to lower values specially the ID-dependent values and the effect of the integer uniform random number used in the first term of the backoff equation will be more apparent when u is big or u is small and N is big. When u is small and N less than 2mb-u, the backoff delay fairness is better at lower N values, while when N exceeds 2mb-u, a worse fairness obtained changes between fall and rise with increasing N but with small amount. When u is big the ID-dependent value, which is main contributor in differentiating backoff delays, is modulated to small range of values which causes more fairness at higher u values decreases when N increases due to the effect of the second term of the equation.Figure 10
CAM fairness with respect to backoff delay.After clarifying and proving the idea using simple assumption-based simulation scenarios, the subsequent sections consider a precious general modeling and evaluation of the CAM.


## 3.4. CAM Modeling

In this section, a Markov chain [34] model for the CAM will be implemented. Regarding the IEEE802.15.4 slotted CSMA/CA, the generalized model presented in [35] is used for its implementation; also this model is used as a basis for CAM modeling; this work represents a generalized accurate model which can be used for effective analysis in terms of reliability, delay, and energy consumption. It takes into account the full functionality of the protocol, the core of IEEE802.15.4 which is the exponential backoff process which is modeled, backoff stages limit, retry limits, acknowledgements, and unsaturated traffic.The state transition model represents the proposed CAM which is depicted in Figure11. As indicated in the model, the three-dimensional Markov chain is described using three stochastic processes, g(t), c(t), and y(t) which represent the backoff stage at time t, the state of the backoff counter at time t, and the state of retransmission counter at time t, respectively. The states from (i,1,j) to (i,2mb-1,j) are the backoff states, the states (Q0,…,QL0-1) consider the idle state when the queue is empty and the node is waiting for a new packet arrival, states (i,0,j) and (i,-1,j) represent the first and second CCA, respectively, and states (-1,k,j) and (-2,k,j) model the successful transmission and packet collision, respectively.Figure 11
State transition model for CAM.The MAC queue is assumed to be a first-in-first-out M/M/1 queue for both CAM and slotted CSMA/CA. The generated packets arrive at the queue with rate ofλ packets per second (pps). The mean service rate μ of the queue packets equals the reciprocal of the mean packet service time. Some of the notations used in the analysis throughout the paper are present in Notations.


### 3.4.1. Computation of the Backoff Probability Distribution

In this section we are going to construct the probability distribution of the backoff period generated by a node in different backoff stagespKk∣I=i in case the node communicates with its sub-NW members and in case the node communicates with the Base Station (BS). To achieve that, the following definitions are introduced which are derived from generating the set of all possible backoff period values with experiments which consider all the possible combinations of the backoff equation variables’ values under specified conditions. The R language is used to generate these experiments outcome, and the relations which describe the probability distribution are derived from observing the pattern of these outcomes.In CAM, the receiving node identification,RID value, may vary through the successive backoff stages; especially, according to the previously proposed TSM, the receiving node in each receiving slot of the time frame is different; thus, the possible RID values in different backoff stages encountered by a node can be represented by a permutation (with repetition). The effect of the RID value on the value of the backoff periods computed by a node in different stages appears in the integer uniform random number clause in the first term of the backoff equation as an added value to the node ID. This added value, referred to as ADV, falls within a range; its lower bound is 0 and its upper bound depends on the RID value in the considered backoff stage with a maximum possible value equal to the number of the backoff stage; based on that, the range of ADV is indicated in the following definitions by its variable upper bound (UB).The following definitions find the probability of a certain backoff period value computed by a node in terms of the number of times this node computes it and the total number of the backoff periods computed by the node. The mathematical formulation of the backoff period probability depends on exploiting the recurrence of the combinations of variables cause a backoff value through a calculable number of repeating times rather than iteratively computes all the backoff values and then extracts the required information from them. This treats the problem of the long time consumed in iterative computation which may be considered as an almost infinite with the huge number of iterations corresponding to the huge number of variables’ combinations which increases inflation with increasing the nodes number and the backoff stages number. Simpler expressions to take smaller time for computing the number of occurrence times of a backoff value under certain conditions are depicted in AppendixA.Definition 1.
Letr(UB,s) be a function used to compute the number of RID values which result in a specific range of the ADV in a backoff stage s. Then r(UB,s) is a function of this range UB and it can be computed as follows:(2)rUB,s=Ns+1if  condition1  and  condition2  are  both  true  or  falseNs+1+1if  condition1  is  true  and  condition2  is  falseNs+1-1if  condition1  is  false  and  condition2  is  true,where condition1 is equivalent to Nmod(s+1)≥UB>0, condition2 is equivalent to UB=IDmod(s+1), and ⋯ is the floor function.Definition 2.
Letrnum(UB,s) denote the number of occurrence times of a specific range UB in a backoff stage s. Then rnum(UB,s) equals the number of RID values which result in the UB in the backoff stage s multiplied by the number of occurrence times of a RID value in a stage, and it is computed as follows: (3)rnumUB,s=rUB,sN-1S,where S is the stage at which we want to compute the backoff period, S∈[0,m], and s∈[0,S].Definition 3.
LetC be a two-dimensional array which represents the combinations of ADV through all stages from 0 to S. The array C has number of rows equal to (S+1)! indexed by ro, one row for each combination; accordingly the number of the columns of C equals S+1 indexed by co.
LetV be a set of S+1 vectors, where V=v0,v1,…,vS. Vector vs represents the maximum range of ADV in stage s which is 0,s.
If we denote the number of occurrence times of one combination corresponding to a rowro in C by cnum(ro), then cnum(ro) equals the maximum number of occurrence times of a combination corresponding to a row in C multiplied by the probability of occurrence of the intended combination corresponding to a row ro:(4)cnumro=max⁡rnum∏z=1S+1∑e=1cro,z≤vez-1zrnumvez-1,z-1N-1S+1=N-1S+1∏z=1S+1∑e=1cro,z≤vez-1zrnumvez-1,z-1N-1S+1,where cro,z is the element of the array C at the row number ro and column number z and vez-1 is the element number e in the vector v which corresponds to stage number z-1.Definition 4.
Let the total number of occurrence times of the set of all possible backoff period values of an experiment outcome be denoted by the notationtknum(S). Then tknum(S) equals the sum of the number of occurrence times of all the ADV combinations which constitute the rows of C multiplied by the number of the combinations of the time units used to perform CCA through a number of S stages; namely,(5)tknumS=2S∑ro=1S+1!cnumro,for every ID∈1,N, u∈0,2mb-1, and S∈0,m.Definition 5.
Let the number of occurrence times of a possible backoff period valuek of an experiment outcome be denoted by the notation knum(k,S), and let the 2S-by-S matrix A represent all the combinations of the number of the time units used to perform CCA in all stages; then for every ID∈[1,N], u∈0,2mb-1, S∈0,m, and Aaro∈A,(6)knumk,S=∑ro=1k=bfroSS+1!cnumro,where(7)bfroS=ID+cro,S+1mod2mb-u+bfsumSmodu+1,bfsum0=0,bfsumS=∑co=1SID+cro,comod2mb-u+bfsumco-1modu+1+aaro,cowhenS>0.The previous definitions relate the communication within the sub-NW; the following definitions, Definitions6 and 7, consider the communication with the BS distinguished by the existence of only one possible receiver, which is the BS, identified by 0; therefore in this case, RID always equals 0.Definition 6.
Let the total number of occurrence times of the set of all possible backoff period values of an experiment outcome, due to the communication with the BS, be denoted by the notationbstknum(S); then bstknum(S) is defined as(8)bstknumS=2S,for every ID∈1,N, u∈0,2mb-1, and S∈0,m.Definition 7.
Let the number of occurrence times of a possible backoff period valuek of an experiment outcome, due to the communication with the BS, be denoted by the notation bsknum(k,S), and let the 2S-by-S matrix A represent all the combinations of the number of the time units used to perform CCA in all stages; then for every ID∈1,N, u∈0,2mb-1, S∈0,m, and Aaro∈A,(9)bsknumk,S=∑k=bfS1,where (10)bfS=IDmod2mb-u+bfsumSmodu+1,bfsum0=0,bfsumS=∑co=1SIDmod2mb-u+bfsumco-1modu+1+aaro,cowhenS>0.Definition 8.
The probability distribution of the backoff period generated by a node in different backoff stagespKk∣I=i is computed as follows: for every k∈0,2mb-1 and i∈0,m,(11)pKk∣I=i=1N∑ID=1Nknumk,itknumifor  sub-NW  communication,pKk∣I=i=1N∑ID=1Nbsknumk,ibstknumifor  communicating  BS.


### 3.4.2. Deriving the Stationary Distribution

The nonzero state transition probabilities associated with the CAM Markov chain of Figure11 represent the state transition due to decrementing the backoff counter by one, the transition from one backoff stage to the next one due to sensing the channel busy, the transition from one transmission trail to the next one due to collision occurrence, the transition after channel access failure to the queue idle state, the transition after transmission failure to the queue idle state, the transition to the queue idle state after the maximum backoff stage in the last transmission trial, and finally the transition from the idle state to the first backoff stage in the first transmission trial; these probabilities are described by (12)–(18),(12)Pi,k,j∣i,k+1,j=1for2mb-1≥k≥0,(13)Pi,k,j∣i-1,0,j=α+1-αβpKk∣I=ifori≤m,(14)P0,k,j∣i,0,j-1=P1-α1-βpKk∣I=0forj≤n,(15)PQ0∣m,0,j=q0α+1-αβforj<n,(16)PQ0∣i,0,n=q01-α1-βfori<m,(17)PQ0∣m,0,n=q0,(18)P0,k,0∣Q0=1-q0pKk∣I=0for2mb-1≥k≥0.The following analysis is concerned with finding the closed form for the stationary distribution of the CAM Markov chain (bi,k,j), where bi,k,j=limt→∞P(g(t)=i,c(t)=k,y(t)=j), i∈(-2,m), k∈(-1,max⁡(2mb-1,Ls-1,Lc-1)), and j∈(0,n). Using (12)–(18) and due to the regularity of the chain, from (13), for 0<i≤m,0≤j≤n,2mb-1≥k≥0, we have(19)bi,k,j=bi-1,0,jα+1-αβ∑r=k2mb-1pKr∣I=i,(20)bi,0,j=α+1-αβbi-1,0,j,and then by recursive application and substitution of (20) for successive backoff stages, we can conclude that(21)bi,0,j=α+1-αβib0,0,j;let α+(1-α)β=x; from (19), (20), and (21) we have(22)bi,k,j=xib0,0,j∑r=k2mb-1pKr∣I=i.From (14) we have(23)b0,k,j=P1-α1-β∑r=k2mb-1pKr∣I=0∑i=0mbi,0,j-1=b0,0,j∑r=k2mb-1pKr∣I=0,and then from (22) and (23), for 0≤i≤m,0≤j≤n,2mb-1≥k≥0,(24)bi,k,j=xib0,0,j∑r=k2mb-1pKr∣I=i.From (14) and (21) we have(25)b0,0,j=1-xP∑i=0mxib0,0,j-1=1-xm+1Pb0,0,j-1;let (1-xm+1)P=y, and by recursive application and substitution of (25) for successive transmission trials, we can conclude that(26)b0,0,j=yjb0,0,0;then from (24) and (26), (24) can be rewritten as (27)bi,k,j=xiyjb0,0,0∑r=k2mb-1pKr∣I=i.We next derive the expression of b0,0,0 by applying the normalization condition: (28)∑j=0n∑k=02mb-1∑i=0mbi,k,j+∑i=0m∑j=0nbi,-1,j+∑j=0n∑k=0Ls-1b-1,k,j+∑k=0Lc-1b-2,k,j+∑l=0L0-1Ql=1;after deriving the expression of each term in (28) in terms of the probability b0,0,0 and substituting with them on it, we obtain(29)b0,0,0=1-yn+11-y∑k=02mb-1∑i=0mxi∑r=k2mb-1pKr∣I=i+1-α1-xm+11-x1-yn+11-y+1-xm+11-PLs+PLc1-yn+11-y+L0q01-q01-yn+11-yxm+1+P1-xm+1yn+1-P1-xm+11-yn+11-y-1.


## 3.4.1. Computation of the Backoff Probability Distribution

In this section we are going to construct the probability distribution of the backoff period generated by a node in different backoff stagespKk∣I=i in case the node communicates with its sub-NW members and in case the node communicates with the Base Station (BS). To achieve that, the following definitions are introduced which are derived from generating the set of all possible backoff period values with experiments which consider all the possible combinations of the backoff equation variables’ values under specified conditions. The R language is used to generate these experiments outcome, and the relations which describe the probability distribution are derived from observing the pattern of these outcomes.In CAM, the receiving node identification,RID value, may vary through the successive backoff stages; especially, according to the previously proposed TSM, the receiving node in each receiving slot of the time frame is different; thus, the possible RID values in different backoff stages encountered by a node can be represented by a permutation (with repetition). The effect of the RID value on the value of the backoff periods computed by a node in different stages appears in the integer uniform random number clause in the first term of the backoff equation as an added value to the node ID. This added value, referred to as ADV, falls within a range; its lower bound is 0 and its upper bound depends on the RID value in the considered backoff stage with a maximum possible value equal to the number of the backoff stage; based on that, the range of ADV is indicated in the following definitions by its variable upper bound (UB).The following definitions find the probability of a certain backoff period value computed by a node in terms of the number of times this node computes it and the total number of the backoff periods computed by the node. The mathematical formulation of the backoff period probability depends on exploiting the recurrence of the combinations of variables cause a backoff value through a calculable number of repeating times rather than iteratively computes all the backoff values and then extracts the required information from them. This treats the problem of the long time consumed in iterative computation which may be considered as an almost infinite with the huge number of iterations corresponding to the huge number of variables’ combinations which increases inflation with increasing the nodes number and the backoff stages number. Simpler expressions to take smaller time for computing the number of occurrence times of a backoff value under certain conditions are depicted in AppendixA.Definition 1.
Letr(UB,s) be a function used to compute the number of RID values which result in a specific range of the ADV in a backoff stage s. Then r(UB,s) is a function of this range UB and it can be computed as follows:(2)rUB,s=Ns+1if  condition1  and  condition2  are  both  true  or  falseNs+1+1if  condition1  is  true  and  condition2  is  falseNs+1-1if  condition1  is  false  and  condition2  is  true,where condition1 is equivalent to Nmod(s+1)≥UB>0, condition2 is equivalent to UB=IDmod(s+1), and ⋯ is the floor function.Definition 2.
Letrnum(UB,s) denote the number of occurrence times of a specific range UB in a backoff stage s. Then rnum(UB,s) equals the number of RID values which result in the UB in the backoff stage s multiplied by the number of occurrence times of a RID value in a stage, and it is computed as follows: (3)rnumUB,s=rUB,sN-1S,where S is the stage at which we want to compute the backoff period, S∈[0,m], and s∈[0,S].Definition 3.
LetC be a two-dimensional array which represents the combinations of ADV through all stages from 0 to S. The array C has number of rows equal to (S+1)! indexed by ro, one row for each combination; accordingly the number of the columns of C equals S+1 indexed by co.
LetV be a set of S+1 vectors, where V=v0,v1,…,vS. Vector vs represents the maximum range of ADV in stage s which is 0,s.
If we denote the number of occurrence times of one combination corresponding to a rowro in C by cnum(ro), then cnum(ro) equals the maximum number of occurrence times of a combination corresponding to a row in C multiplied by the probability of occurrence of the intended combination corresponding to a row ro:(4)cnumro=max⁡rnum∏z=1S+1∑e=1cro,z≤vez-1zrnumvez-1,z-1N-1S+1=N-1S+1∏z=1S+1∑e=1cro,z≤vez-1zrnumvez-1,z-1N-1S+1,where cro,z is the element of the array C at the row number ro and column number z and vez-1 is the element number e in the vector v which corresponds to stage number z-1.Definition 4.
Let the total number of occurrence times of the set of all possible backoff period values of an experiment outcome be denoted by the notationtknum(S). Then tknum(S) equals the sum of the number of occurrence times of all the ADV combinations which constitute the rows of C multiplied by the number of the combinations of the time units used to perform CCA through a number of S stages; namely,(5)tknumS=2S∑ro=1S+1!cnumro,for every ID∈1,N, u∈0,2mb-1, and S∈0,m.Definition 5.
Let the number of occurrence times of a possible backoff period valuek of an experiment outcome be denoted by the notation knum(k,S), and let the 2S-by-S matrix A represent all the combinations of the number of the time units used to perform CCA in all stages; then for every ID∈[1,N], u∈0,2mb-1, S∈0,m, and Aaro∈A,(6)knumk,S=∑ro=1k=bfroSS+1!cnumro,where(7)bfroS=ID+cro,S+1mod2mb-u+bfsumSmodu+1,bfsum0=0,bfsumS=∑co=1SID+cro,comod2mb-u+bfsumco-1modu+1+aaro,cowhenS>0.The previous definitions relate the communication within the sub-NW; the following definitions, Definitions6 and 7, consider the communication with the BS distinguished by the existence of only one possible receiver, which is the BS, identified by 0; therefore in this case, RID always equals 0.Definition 6.
Let the total number of occurrence times of the set of all possible backoff period values of an experiment outcome, due to the communication with the BS, be denoted by the notationbstknum(S); then bstknum(S) is defined as(8)bstknumS=2S,for every ID∈1,N, u∈0,2mb-1, and S∈0,m.Definition 7.
Let the number of occurrence times of a possible backoff period valuek of an experiment outcome, due to the communication with the BS, be denoted by the notation bsknum(k,S), and let the 2S-by-S matrix A represent all the combinations of the number of the time units used to perform CCA in all stages; then for every ID∈1,N, u∈0,2mb-1, S∈0,m, and Aaro∈A,(9)bsknumk,S=∑k=bfS1,where (10)bfS=IDmod2mb-u+bfsumSmodu+1,bfsum0=0,bfsumS=∑co=1SIDmod2mb-u+bfsumco-1modu+1+aaro,cowhenS>0.Definition 8.
The probability distribution of the backoff period generated by a node in different backoff stagespKk∣I=i is computed as follows: for every k∈0,2mb-1 and i∈0,m,(11)pKk∣I=i=1N∑ID=1Nknumk,itknumifor  sub-NW  communication,pKk∣I=i=1N∑ID=1Nbsknumk,ibstknumifor  communicating  BS.


## 3.4.2. Deriving the Stationary Distribution

The nonzero state transition probabilities associated with the CAM Markov chain of Figure11 represent the state transition due to decrementing the backoff counter by one, the transition from one backoff stage to the next one due to sensing the channel busy, the transition from one transmission trail to the next one due to collision occurrence, the transition after channel access failure to the queue idle state, the transition after transmission failure to the queue idle state, the transition to the queue idle state after the maximum backoff stage in the last transmission trial, and finally the transition from the idle state to the first backoff stage in the first transmission trial; these probabilities are described by (12)–(18),(12)Pi,k,j∣i,k+1,j=1for2mb-1≥k≥0,(13)Pi,k,j∣i-1,0,j=α+1-αβpKk∣I=ifori≤m,(14)P0,k,j∣i,0,j-1=P1-α1-βpKk∣I=0forj≤n,(15)PQ0∣m,0,j=q0α+1-αβforj<n,(16)PQ0∣i,0,n=q01-α1-βfori<m,(17)PQ0∣m,0,n=q0,(18)P0,k,0∣Q0=1-q0pKk∣I=0for2mb-1≥k≥0.The following analysis is concerned with finding the closed form for the stationary distribution of the CAM Markov chain (bi,k,j), where bi,k,j=limt→∞P(g(t)=i,c(t)=k,y(t)=j), i∈(-2,m), k∈(-1,max⁡(2mb-1,Ls-1,Lc-1)), and j∈(0,n). Using (12)–(18) and due to the regularity of the chain, from (13), for 0<i≤m,0≤j≤n,2mb-1≥k≥0, we have(19)bi,k,j=bi-1,0,jα+1-αβ∑r=k2mb-1pKr∣I=i,(20)bi,0,j=α+1-αβbi-1,0,j,and then by recursive application and substitution of (20) for successive backoff stages, we can conclude that(21)bi,0,j=α+1-αβib0,0,j;let α+(1-α)β=x; from (19), (20), and (21) we have(22)bi,k,j=xib0,0,j∑r=k2mb-1pKr∣I=i.From (14) we have(23)b0,k,j=P1-α1-β∑r=k2mb-1pKr∣I=0∑i=0mbi,0,j-1=b0,0,j∑r=k2mb-1pKr∣I=0,and then from (22) and (23), for 0≤i≤m,0≤j≤n,2mb-1≥k≥0,(24)bi,k,j=xib0,0,j∑r=k2mb-1pKr∣I=i.From (14) and (21) we have(25)b0,0,j=1-xP∑i=0mxib0,0,j-1=1-xm+1Pb0,0,j-1;let (1-xm+1)P=y, and by recursive application and substitution of (25) for successive transmission trials, we can conclude that(26)b0,0,j=yjb0,0,0;then from (24) and (26), (24) can be rewritten as (27)bi,k,j=xiyjb0,0,0∑r=k2mb-1pKr∣I=i.We next derive the expression of b0,0,0 by applying the normalization condition: (28)∑j=0n∑k=02mb-1∑i=0mbi,k,j+∑i=0m∑j=0nbi,-1,j+∑j=0n∑k=0Ls-1b-1,k,j+∑k=0Lc-1b-2,k,j+∑l=0L0-1Ql=1;after deriving the expression of each term in (28) in terms of the probability b0,0,0 and substituting with them on it, we obtain(29)b0,0,0=1-yn+11-y∑k=02mb-1∑i=0mxi∑r=k2mb-1pKr∣I=i+1-α1-xm+11-x1-yn+11-y+1-xm+11-PLs+PLc1-yn+11-y+L0q01-q01-yn+11-yxm+1+P1-xm+1yn+1-P1-xm+11-yn+11-y-1.


## 3.5. Single-Hop Communication Analysis

The single-hop communication scenario considers a number of nodesN which are reachable from each other; when each node has data to transmit, it contends with the others in accessing the shared channel according to the behavior described by the employed Markov chain models for slotted CSMA/CA and CAM. This section concerns the derivation of the required performance metrics expressions, starting with finding expressions for some of the models’ related probabilities required in the performance analysis implementation.


### 3.5.1. Deriving Expressions for the Models’ Different Associated Probabilities

The derivations ofτ, α, β, and P for both slotted CSMA/CA and CAM are the same as done in [35], where(30)τ=∑i=0m∑j=0nbi,0,j=1-xm+11-x1-yn+11-yb0,0,0,P=1-1-τN-1,α=P1st  CCA  busy  due  to  data  transmission+P1st  CCA  busy  due  to  ACK  transmission=L1-1-τN-11-α1-β+LackNτ1-τN-11-1-τN1-1-τN-11-α1-β,β=1-1-τN-1+Nτ1-τN-12-1-τN+Nτ1-τN-1.The mean packet service time E[S] takes into account the probability that the serviced packet may be transmitted successfully or discarded due to reaching transmission retry limit or channel access failure, and the average time taken in each case from the instant the packet is at the head of the queue is different, (31)∴ES=RED+Pcrn+1Lc+ETh+Pcf∑j=0n1-y1-yn+1yjjLc+ETh+∑i=0m∑r=02mb-1rpKr∣I=i+TSC∑e=12m+1Cαβem+1Nαem+1+2Nβem+1.The Matlab is used for solving the nonlinear system of equations represented by τ, α, β, and q0 expressions.


### 3.5.2. Reliability Analysis

The derivation of the reliability, which is the probability of successful packet reception, for both slotted CSMA/CA and CAM, is the same as done in [35], where(32)R=1-Pcf-Pcr=1-xm+11-yn+11-y-yn+1.


### 3.5.3. Delay Analysis

The average delay is defined as the time interval from the instant at which the data packet is at the head of the MAC queue ready to be transmitted until its acknowledgement is received. The derivation of the average delay expression is the same as done in [35] for both slotted CSMA/CA and CAM, except for the term in the equation of E[Th] which refers to the backoff time; in CAM case this term equals (for complete derivation see [35])(33)1∑i=0mCαβi∑i=0m∑e=12iCαβei∑l=0i∑r=02mb-1rpKr∣I=l.


### 3.5.4. Energy Consumption Analysis

The average energy consumption is computed from (34), where Ei, Esc, Et, Er, and Esp are the average energy consumption in idle-listen, channel sensing, transmit, receive, and sleep states, respectively. Esp term is neglected: (34)E=Ei∑i=0m∑k=12mb-1∑j=0nbi,k,j+Esc∑i=0m∑j=0nbi,0,j+bi,-1,j+Et∑j=0n∑k=0L-1b-1,k,j+b-2,k,j+Ei∑j=0nb-1,L,j+b-2,L,j+∑j=0n∑k=L+1L+Lack+1Erb-1,k,j+Eib-2,k,j+Esp∑l=0L0-1Ql.


### 3.5.5. Throughput Analysis

The throughput, which is defined as the fraction of channel time used to successfully transmit data payload bits in unit time, is computed from(35)TH=PsuccessPbusyL1-PbusySb+PsuccessPbusyLs+Pbusy1-PsuccessLc,where Pbusy is the probability that there is at least one transmission in the considered unit time and it equals 1-1-τN; Psuccess is the probability of successful data transmission conditioned by the fact that the channel is busy and it equals Nτ1-τN-1/Pbusy; the denominator of TH considers that the channel time has different probabilities of being free or busy with failed or successful transmission.


## 3.5.1. Deriving Expressions for the Models’ Different Associated Probabilities

The derivations ofτ, α, β, and P for both slotted CSMA/CA and CAM are the same as done in [35], where(30)τ=∑i=0m∑j=0nbi,0,j=1-xm+11-x1-yn+11-yb0,0,0,P=1-1-τN-1,α=P1st  CCA  busy  due  to  data  transmission+P1st  CCA  busy  due  to  ACK  transmission=L1-1-τN-11-α1-β+LackNτ1-τN-11-1-τN1-1-τN-11-α1-β,β=1-1-τN-1+Nτ1-τN-12-1-τN+Nτ1-τN-1.The mean packet service time E[S] takes into account the probability that the serviced packet may be transmitted successfully or discarded due to reaching transmission retry limit or channel access failure, and the average time taken in each case from the instant the packet is at the head of the queue is different, (31)∴ES=RED+Pcrn+1Lc+ETh+Pcf∑j=0n1-y1-yn+1yjjLc+ETh+∑i=0m∑r=02mb-1rpKr∣I=i+TSC∑e=12m+1Cαβem+1Nαem+1+2Nβem+1.The Matlab is used for solving the nonlinear system of equations represented by τ, α, β, and q0 expressions.


## 3.5.2. Reliability Analysis

The derivation of the reliability, which is the probability of successful packet reception, for both slotted CSMA/CA and CAM, is the same as done in [35], where(32)R=1-Pcf-Pcr=1-xm+11-yn+11-y-yn+1.


## 3.5.3. Delay Analysis

The average delay is defined as the time interval from the instant at which the data packet is at the head of the MAC queue ready to be transmitted until its acknowledgement is received. The derivation of the average delay expression is the same as done in [35] for both slotted CSMA/CA and CAM, except for the term in the equation of E[Th] which refers to the backoff time; in CAM case this term equals (for complete derivation see [35])(33)1∑i=0mCαβi∑i=0m∑e=12iCαβei∑l=0i∑r=02mb-1rpKr∣I=l.


## 3.5.4. Energy Consumption Analysis

The average energy consumption is computed from (34), where Ei, Esc, Et, Er, and Esp are the average energy consumption in idle-listen, channel sensing, transmit, receive, and sleep states, respectively. Esp term is neglected: (34)E=Ei∑i=0m∑k=12mb-1∑j=0nbi,k,j+Esc∑i=0m∑j=0nbi,0,j+bi,-1,j+Et∑j=0n∑k=0L-1b-1,k,j+b-2,k,j+Ei∑j=0nb-1,L,j+b-2,L,j+∑j=0n∑k=L+1L+Lack+1Erb-1,k,j+Eib-2,k,j+Esp∑l=0L0-1Ql.


## 3.5.5. Throughput Analysis

The throughput, which is defined as the fraction of channel time used to successfully transmit data payload bits in unit time, is computed from(35)TH=PsuccessPbusyL1-PbusySb+PsuccessPbusyLs+Pbusy1-PsuccessLc,where Pbusy is the probability that there is at least one transmission in the considered unit time and it equals 1-1-τN; Psuccess is the probability of successful data transmission conditioned by the fact that the channel is busy and it equals Nτ1-τN-1/Pbusy; the denominator of TH considers that the channel time has different probabilities of being free or busy with failed or successful transmission.


## 3.6. Multihop Communication Analysis

The aim of this section is to analyze the end-to-end performance of the proposed CAM when the packet is forwarded through intermediate node(s) to reach the final destination for comparing the CAM performance against the slotted CSMA/CA in multihop topology. The algorithmic technique of “divide and conquer” is used for finding the end-to-end performance, where the multihop path is partitioned into a number of single-hops solved using the previous analysis with adjusting the model parameters and may be with some modifications according to the employed topology; then the solutions obtained for each single-hop are appropriately merged to obtain the end-to-end multihop performance.Figure12 presents examples for the employed topology for each protocol; the topology of the slotted CSMA/CA is the logical topology for it which is the cluster-tree. The proposed CAM topology is constructed by dividing the network into subnetworks, each one works on a different frequency channel, some members are BS-neighbors, and its members work on our previously proposed TSM [11]. The time slot equals the time of one transmission, and no interaction between the sub-NWs is assumed. The number of the BS-neighbors in all the sub-NWs is approximately equal, and the number of the non-BS-neighbors in all the sub-NWs is also approximately equal. In CAM, no attention is given to a specific routing technique, that is, no determinants of the next hop; also in CSMA/CA, no determinants imposed for selecting the parent coordinator from the discovered ones.Figure 12
Multihop network topologies (a) for CAM network and (b) for slotted CSMA/CA cluster-tree network.
(a) (b)In the two topologies, when a node has a packet at the head of the queue ready to be sent, it can immediately start its transmission process to the currently listening receiver; that is, all the intended receivers in any time are available; no sleeping schedule causes deferring of a transmission process, such that only the effect of the medium access method is considered. The nodes are deployed uniformly; the nodes which have the capability of coordinator represent 25% of the total nodes number and are deployed independently uniformly throughout the area.The starts of the first packet generation of all the sub-NW members are separated by an ignorable time; accordingly the generation repetitions will be separated by an ignorable time. The cluster-tree formation and communication as well as the communication between sub-NWs’ BS-neighbors and the BS are performed using −15 dBm, while the communication among sub-NWs’ members is performed using a greater transmission power level −10 dBm for assuring the reachability of the receiving node at any time.The following sections concern deriving expressions for the multihop performance metrics for both the slotted CSMA/CA network and the CAM network. The multihop network topology imposes changes in each node variables and the communication conditions from one network to the other or may be from one hop to another in the same network, such as the existence of different degrees of neighborhood to a transmitting node which raises the existence of hidden nodes, different packet arrival rates, and different number of contended nodes. Section3.6.1 analyzes the effect of multihop communication on the two networks’ models associated probabilities. Sections 3.6.2 to 3.6.5 analyze the end-to-end reliability, delay, energy consumption, and throughput; the same definitions and computation are used for finding these slotted CSMA/CA and CAM end-to-end performance metrics except few indicated differences.


### 3.6.1. Deriving Expressions for the Models’ Different Associated Probabilities

In this section, the derivations ofα, β, and P for both slotted CSMA/CA and CAM will be introduced.(1) Slotted CSMA/CA End-to-End Analysis. In the cluster-tree slotted CSMA/CA network and by assuming that the number of each cluster end devices members Id is approximately equal and the number of children coordinators Ic varies from 0 to a constant maximum limit for each coordinator, the packet arrival rate at the MAC queue differs from the end device λd to the coordinator λc; also if no aggregation is assumed, it will differ for coordinators at different levels, but it may differ in case of aggregation employed from coordinator to another one if their Ic values are different. The packet generation rate λ at each node is equal, in each time unit the network will have the number of packets described by λ generated from each node, and in computing the approximate value of the packet arrival rate at a node, it is assumed that all the transmitted packets to this node will be delivered successfully. The packet arrival rates are computed as follows:(36)λd=λ,λci=λ1+Id+Iciif  aggregation  is  assumed,λci=λ1+Id+Icitotal1+Idif  no  aggregation  is  assumed,where Icitotal represents the number of the coordinators below the coordinator i in its tree branch, its children coordinators, its grandchildren coordinators, the children of its grandchildren coordinators, and so on.According to the packet arrival rate and the different neighborhood of each node and its neighbors, the node will have its own probabilities ofτ,α,β, and P. The neighborhood of a transmitting node, its receiver’s neighborhood, and the neighborhood of its receiver’s neighbors are distinguished by defining some sets of nodes, each one has an effect on the transmitting node packet; these sets are Φt,Φtc,Φtr,Φhtr,Φhctr,ψc,Ct, and C.The setΦt defines the neighborhood of a node t, which are the nodes surrounding this node that can hear its transmissions and likewise it can hear their transmissions (the neighbor coordinators are discriminated by Φtc and incorporate the BS), the set Φtr defines the common neighborhood of the nodes t and r (Φtr=(Φt∩Φr)), the set Φhtr defines the hidden nodes from the node t with respect to the transmission to node r including the BS, the set Φhctr defines the hidden coordinators from the node t with respect to the transmission to node r including the BS, the set ψc defines the set of coordinator c children from devices and coordinators, the set Ct is a set of one element corresponding to the coordinator of node t, and the set C defines the set of all coordinators in the network.(a) The Collision Probability. The collision probability related to node t is the probability that node t encounters a collision on a transmitted packet to its coordinator, and it is denoted by Pt. The collision probability Pt is given by (37)Pt=PCsenset+1-PCsensetPChDatat+1-PCsenset1-PChDatatPChAckt,where PCsenset is the collision probability of a transmitted packet from t to r due to concurrent channel sensing, PChDatat is the collision probability of a transmitted packet from t to r due to hidden data transmission starts before or after the beginning of the packet transmission, and PChAckt is the collision probability of a transmitted packet from t to r due to hidden acknowledgement transmission starts before or after the beginning of the packet transmission.The probabilityPCsenset considers the probability that at least one node from the common neighborhood of the transmitter and the receiver (except the BS) transmits at the same time slot. If each node in the common neighborhood senses the channel with its own probability τ, PCsenset is computed from(38)PCsenset=1-∏j∈Φtr,j≠BS1-τj.Hidden acknowledgements to the transmittert resulted from successful data reception at the hidden coordinators from t upon which they transmit acknowledgements received at its receiver r and collide with its data. The probability PChAckt is given by(39)PChAckt=PSRht1-∏k∈⋃h∈Φhctrψh1-τk∑q=1⋃h∈Φhctrψh∑m=1Cq⋃h∈Φhctrψh∏i∈dmdm=dm,1,dm,2,…,dm,qτi∏j∈⋃h∈Φhctrψh∖dm1-τj1-∏n∈dmdm=dm,1,dm,2,…,dm,qαn+1-αnβn,where ⋃h∈Φhctrψh stands for the size of the set of nodes which represents the union of all the sets which contain the children of the hidden coordinators from t, Cq⋃h∈Φhctrψh represents the number of combinations of size q from the set ⋃h∈Φhctrψh, dm represents the combination number m of size q, and they are used in (39) to calculate the probability of at least one node from the set ⋃h∈Φhctrψh which begins a transmission. The notation PSRht represents the probability of successful data reception at the hidden coordinators from t and it is defined in Appendix B.The probabilityPChDatat is the probability of at least one from the hidden nodes to t which begins a transmission in any time unit of a time duration equal to the average channel occupation of a data transmission before the beginning of t transmission and one after it. The probability PChDatat is calculated from (40)PChDatat=2L∑q=1Φhtr∖BS∑m=1CqΦhtr∖BS∏i∈kmkm=km,1,km,2,…,km,qτi∏j∈Φhtr∖km∪BS1-τj1-∏n∈kmkm=km,1,km,2,…,km,qαn+1-αnβn,where CqΦhtr∖BS represents the q-combinations from the hidden nodes to t excluding the BS and it equals the number of rows of the matrixK where each row contains one different combination.(b) Probability of Finding the 1st CCA Busy. The equation of αt which is the probability of node t finds the 1st CCA busy which comprises the probability to find it busy due to data transmission (α1t) and the probability to find it busy due to acknowledgement transmission α2t, (41)αt=α1t+1-α1tα2t,α1t=L∑q=1Φt∖BS∑m=1CqΦt∖BS∏i∈kmkm=km,1,km,2,…,km,qτi∏j∈Φt∖km∪BS1-τj1-∏n∈kmkm=km,1,km,2,…,km,qαn+1-αnβn,α2t=PSRt1-∏k∈⋃h∈Φtcψh∖t1-τk∑q=1⋃h∈Φtcψh∖t∑m=1Cq⋃h∈Φtcψh∖t∏i∈dmdm=dm,1,dm,2,…,dm,qτi∏j∈⋃h∈Φtcψh∖dm∪t1-τj1-∏n∈dmdm=dm,1,dm,2,…,dm,qαn+1-αnβn,where CqΦt∖BS and Cq⋃h∈Φtcψh∖t represent the q-combinations from all the neighbors of t excluding the BS and all the children of the neighbor coordinators of t excluding t itself, respectively. The notation PSRt represents the probability of successful data reception at the coordinators of node t neighborhood and it is defined in Appendix B.(c) Probability of Finding the 2nd CCA Busy. The probability βt, which is the probability of node t finding the 2nd CCA slot (denoted as CCA2) busy given that the 1st CCA slot (denoted as CCA1) was idle, is derived in the same fashion used in [36] but with considering the different neighborhood and other different values the nodes have.The node can assess its 2nd CCA busy in two cases, the first one occurs if some other nodes in the medium were sensing their 2nd CCA during this node 1st CCA and started a new transmission in the node’s 2nd CCA slot. This can only happen if the other node started sensing in the slot just before the intended node 1st CCA slot (denoted as slot1) and the channel was then idle. The second case of assessing the 2nd CCA busy occurs when the 1st CCA idle slot was the slot between data transmission and acknowledgement (the probability of the second case occurrence is denoted byPbetaACK); then(42)βt=PIslot1∣ICCA1PSslot1+PbetaACK,where Islot1 and ICCA1 are the events of finding slot1 and CCA1 idle, respectively; the event Sslot1 is the event of start sensing in slot1.The conditional probabilityP(Islot1∣ICCA1) is the probability that a given idle slot is preceded by another idle slot,(43)PIslot1∣ICCA1=1-PBslot1∩ICCA1PICCA1=1-PBslot1∩ICCA1PBslot1∩ICCA1+PIslot1∩ICCA1,where Bslot1 it the event of finding slot1 busy; then βt can be rewritten as(44)βt=1-PBslot1∩ICCA1PBslot1∩ICCA1+PIslot1∩ICCA1PSslot1+PbetaACK.The eventICCA1 occurs in four cases.Case 1.
A busy slot before the idleCCA1 because of a failed packet transmission due to collision: this is represented by the probability PbusyFt for node t.Case 2.
A busy slot before the idleCCA1 because of an acknowledgement following a successful data transmission: this is represented by the probability PbusyAt for node t.Case 3.
A busy slot before the idleCCA1 because of a successful packet transmission where the idle slot is the interframe space in between data and acknowledgement: this is represented by the probability PbusySt for node t.Case 4.
An idle slot before the idleCCA1 happened after an acknowledged successful transmission or an unacknowledged unsuccessful transmission: this is represented by the probability Pidlet for node t.Substituting with these probabilities in (44), we have(45)βt=1-PbusyFt+PbusyAt+PbusyStPbusyFt+PbusyAt+PbusySt+Pidlet1-∏j∈Φt,j≠BS1-τj+PbusyAtPbusyFt+PbusyAt+PbusySt+Pidlet,and the expressions which define these probabilities are presented in Appendix B.(2) CAM End-to-End Analysis. In CAM, the packet generation rate λ at each node is equal, in each time unit the network will have the number of packets described by λ generated from each node, the time unit described by λ equals multiples of the TSM frame greater than λ multiplied by maximum number of allowed hops through a sub-NW, and in computing the approximate value of the packet arrival rate at a node it is assumed that all the transmitted packets to this node will be delivered successfully. It is assumed that if the BS-neighbors number does not represent the larger share in a sub-NW, they transmit their packets directly to BS and are not allowed to use multihops. The topology does not imply a specific form of doing aggregation; the routing may determine that, so no aggregation is assumed.The number of the sub-NW non-BS-neighbor members is denoted byIo and the number of the BS-neighbor members is denoted by IBS. The average packet arrival rate at the BS-neighbors λBS is greater than that of the non-BS-neighbors λo as they represent the critical zone around the BS and it depends on both Io and IBS. The whole path taken by a transmitted packet lies in a specific sub-NW, except the last hop where the last hop source, which is a BS-neighbor, switches its working channel to the working channel of the BS.Assume that a one hop of packets transmitted from each non-BS-neighbor node is completed approximately within a TSM frame time and when each node succeeds to send its packet, whether generated or forwarded, it sends it to a receiver different from whom its peers send to, whether this receiver is a BS-neighbor or not. According to that, at the completion of one packet transmission from each node, the non-BS-neighbor node will receive a number of packets ranges from 0 to(lmax-2), where lmax is the maximum path length. The final intermediate node is a BS-neighbor and the average number of packets received by a BS-neighbor in a completion of each non-BS-neighbor nodes one packet transmission is approximately equal to the number of non-BS-neighbors divided by the number of BS-neighbors in the sub-NW. Based on the previous considerations, the average packet arrival rates λo and λBS are computed as follows:(46)λo=λ1+∑x=0lmax-2xlmax-1,λBS=λ1+IoIBS.(a) Deriving Non-BS-Neighbor Different Associated Probabilities. The probability of collision of a non-BS-neighbor transmitted packet depends on the number of non-BS-neighbors in its receiver neighborhood in its sub-NW and their values of τ. For simplicity and to encounter the problem of hidden nodes to the transmitter, it is assumed that all the non-BS-neighbor members always transmit with its full range (or a range enough for covering the whole employed field), therefore no hidden nodes to the transmitter. In case the receiving node is a BS-neighbor, the number of competing nodes Ncp with a node tries to transmit will be equal to (Io-1), and in case of its being a non-BS-neighbor, Ncp equals (Io-2). Under the previous assumptions, the derivation of α, β, and P for a non-BS-neighbor is turned to be the same as followed in the single-hop communication analysis with notations and values of variables indicate a non-BS-neighbor in a sub-NW: (47)Po=1-1-τoNcp,αo=L+LackIoτo1-τoIo-11-1-τoIo1-1-τoIo-11-αo1-βo,βo=1-1-τoIo-1+Ioτo1-τoIo-12-1-τoIo+Ioτo1-τoIo-1.(b) Deriving BS-Neighbor Different Associated Probabilities. The probability of collision of a BS-neighbor transmitted packet depends on the number of BS-neighbors in all the sub-NWs and their values of τ. If the number of sub-NWs is denoted by Ns, then the number of BS-neighbors equals IBSNs; some of them may be hidden to others, where ΦtBS represents the common neighbors between the BS-neighbor t and the BS and ΦhtBS represents the hidden BS-neighbors to the BS-neighbor t. The probabilities α, β, and P are derived in the same fashion as they are derived in case of slotted CSMA/CA; except here there is no hidden acknowledgement; the set of all the children of the neighbor coordinators contains only the BS-neighbors and is defined by ΦtBS∪ΦhtBS; and successful concurrent transmissions from even two nodes do not exist.


### 3.6.2. End-to-End Reliability Analysis

The end-to-end reliabilityRe-to-e is the ANDing and in other words, the product of the probabilities of successful packet reception at each intermediate node in the considered path then to the BS,(48)Re-to-e=∏n=1lRn,where l is the path length in terms of its incorporated nodes number excluding the final destination which is the BS, Rn is the single-hop reliability of the transmitted packet by the node number n in the path, then R1 is corresponding to the first node in the path which is the source node, and Rl is corresponding to the last node in the path which is a BS child coordinator.


### 3.6.3. End-to-End Delay Analysis

By ignoring the processing delay, the average end-to-end delayDe-to-e is the summation of the average delays for successfully delivering the packet (D) at each node in the path including the PAN coordinator (BS) and the average queuing delay (w=λ/μ/μ-λ) at each intermediate node in the path, where λ here refers to the queue packet arrival rate and μ is the packet service rate.(49)De-to-e=∑n=1lwn+Dn.The channel switching time is added to the end-to-end delay in CAM case to incorporate the effect of a BS-neighbor switching to the BS channel to send its data to it (channel switching time is approximately the transmission time of a 32 byte (~1 ms) [37]).


### 3.6.4. End-to-End Energy Consumption Analysis

The total energy consumed to relay the packet through the path towards the BS is assumed to be the summation of the total energy consumed by each node in transmitting the packet to the next-hop node. For simplicity, the switching between frequency channels is assumed to consume ignorable energy:(50)Ee-to-e=∑n=1lEn.


### 3.6.5. Network Throughput Analysis

The normalized system throughput is defined and calculated here in the same way used for single-hop analysis; the difference is in the definition ofPbusy and Psuccess. If we denote the set of all nodes in the network (except BS and PAN coordinator) by Φtotal, here(51)Pbusy=1-∏i∈Φtotal1-τi,Psuccess=∑i∈ΦtotalPSTiPbusy,where PSTk, as defined in Appendix B, is the probability of successful transmission by a node.Another metric used to measure the network productivity is the goodput defined as the data bits successfully received at the BS in one time unit. The network goodputG (in bits/sec) is the summation of all nodes goodputs; let On be the set of all possible paths for delivering data from node n to the BS; then(52)G=L×20×4∑n∈Φtotal∑r∈OnRe-to-en,rDe-to-en,r.


## 3.6.1. Deriving Expressions for the Models’ Different Associated Probabilities

In this section, the derivations ofα, β, and P for both slotted CSMA/CA and CAM will be introduced.(1) Slotted CSMA/CA End-to-End Analysis. In the cluster-tree slotted CSMA/CA network and by assuming that the number of each cluster end devices members Id is approximately equal and the number of children coordinators Ic varies from 0 to a constant maximum limit for each coordinator, the packet arrival rate at the MAC queue differs from the end device λd to the coordinator λc; also if no aggregation is assumed, it will differ for coordinators at different levels, but it may differ in case of aggregation employed from coordinator to another one if their Ic values are different. The packet generation rate λ at each node is equal, in each time unit the network will have the number of packets described by λ generated from each node, and in computing the approximate value of the packet arrival rate at a node, it is assumed that all the transmitted packets to this node will be delivered successfully. The packet arrival rates are computed as follows:(36)λd=λ,λci=λ1+Id+Iciif  aggregation  is  assumed,λci=λ1+Id+Icitotal1+Idif  no  aggregation  is  assumed,where Icitotal represents the number of the coordinators below the coordinator i in its tree branch, its children coordinators, its grandchildren coordinators, the children of its grandchildren coordinators, and so on.According to the packet arrival rate and the different neighborhood of each node and its neighbors, the node will have its own probabilities ofτ,α,β, and P. The neighborhood of a transmitting node, its receiver’s neighborhood, and the neighborhood of its receiver’s neighbors are distinguished by defining some sets of nodes, each one has an effect on the transmitting node packet; these sets are Φt,Φtc,Φtr,Φhtr,Φhctr,ψc,Ct, and C.The setΦt defines the neighborhood of a node t, which are the nodes surrounding this node that can hear its transmissions and likewise it can hear their transmissions (the neighbor coordinators are discriminated by Φtc and incorporate the BS), the set Φtr defines the common neighborhood of the nodes t and r (Φtr=(Φt∩Φr)), the set Φhtr defines the hidden nodes from the node t with respect to the transmission to node r including the BS, the set Φhctr defines the hidden coordinators from the node t with respect to the transmission to node r including the BS, the set ψc defines the set of coordinator c children from devices and coordinators, the set Ct is a set of one element corresponding to the coordinator of node t, and the set C defines the set of all coordinators in the network.(a) The Collision Probability. The collision probability related to node t is the probability that node t encounters a collision on a transmitted packet to its coordinator, and it is denoted by Pt. The collision probability Pt is given by (37)Pt=PCsenset+1-PCsensetPChDatat+1-PCsenset1-PChDatatPChAckt,where PCsenset is the collision probability of a transmitted packet from t to r due to concurrent channel sensing, PChDatat is the collision probability of a transmitted packet from t to r due to hidden data transmission starts before or after the beginning of the packet transmission, and PChAckt is the collision probability of a transmitted packet from t to r due to hidden acknowledgement transmission starts before or after the beginning of the packet transmission.The probabilityPCsenset considers the probability that at least one node from the common neighborhood of the transmitter and the receiver (except the BS) transmits at the same time slot. If each node in the common neighborhood senses the channel with its own probability τ, PCsenset is computed from(38)PCsenset=1-∏j∈Φtr,j≠BS1-τj.Hidden acknowledgements to the transmittert resulted from successful data reception at the hidden coordinators from t upon which they transmit acknowledgements received at its receiver r and collide with its data. The probability PChAckt is given by(39)PChAckt=PSRht1-∏k∈⋃h∈Φhctrψh1-τk∑q=1⋃h∈Φhctrψh∑m=1Cq⋃h∈Φhctrψh∏i∈dmdm=dm,1,dm,2,…,dm,qτi∏j∈⋃h∈Φhctrψh∖dm1-τj1-∏n∈dmdm=dm,1,dm,2,…,dm,qαn+1-αnβn,where ⋃h∈Φhctrψh stands for the size of the set of nodes which represents the union of all the sets which contain the children of the hidden coordinators from t, Cq⋃h∈Φhctrψh represents the number of combinations of size q from the set ⋃h∈Φhctrψh, dm represents the combination number m of size q, and they are used in (39) to calculate the probability of at least one node from the set ⋃h∈Φhctrψh which begins a transmission. The notation PSRht represents the probability of successful data reception at the hidden coordinators from t and it is defined in Appendix B.The probabilityPChDatat is the probability of at least one from the hidden nodes to t which begins a transmission in any time unit of a time duration equal to the average channel occupation of a data transmission before the beginning of t transmission and one after it. The probability PChDatat is calculated from (40)PChDatat=2L∑q=1Φhtr∖BS∑m=1CqΦhtr∖BS∏i∈kmkm=km,1,km,2,…,km,qτi∏j∈Φhtr∖km∪BS1-τj1-∏n∈kmkm=km,1,km,2,…,km,qαn+1-αnβn,where CqΦhtr∖BS represents the q-combinations from the hidden nodes to t excluding the BS and it equals the number of rows of the matrixK where each row contains one different combination.(b) Probability of Finding the 1st CCA Busy. The equation of αt which is the probability of node t finds the 1st CCA busy which comprises the probability to find it busy due to data transmission (α1t) and the probability to find it busy due to acknowledgement transmission α2t, (41)αt=α1t+1-α1tα2t,α1t=L∑q=1Φt∖BS∑m=1CqΦt∖BS∏i∈kmkm=km,1,km,2,…,km,qτi∏j∈Φt∖km∪BS1-τj1-∏n∈kmkm=km,1,km,2,…,km,qαn+1-αnβn,α2t=PSRt1-∏k∈⋃h∈Φtcψh∖t1-τk∑q=1⋃h∈Φtcψh∖t∑m=1Cq⋃h∈Φtcψh∖t∏i∈dmdm=dm,1,dm,2,…,dm,qτi∏j∈⋃h∈Φtcψh∖dm∪t1-τj1-∏n∈dmdm=dm,1,dm,2,…,dm,qαn+1-αnβn,where CqΦt∖BS and Cq⋃h∈Φtcψh∖t represent the q-combinations from all the neighbors of t excluding the BS and all the children of the neighbor coordinators of t excluding t itself, respectively. The notation PSRt represents the probability of successful data reception at the coordinators of node t neighborhood and it is defined in Appendix B.(c) Probability of Finding the 2nd CCA Busy. The probability βt, which is the probability of node t finding the 2nd CCA slot (denoted as CCA2) busy given that the 1st CCA slot (denoted as CCA1) was idle, is derived in the same fashion used in [36] but with considering the different neighborhood and other different values the nodes have.The node can assess its 2nd CCA busy in two cases, the first one occurs if some other nodes in the medium were sensing their 2nd CCA during this node 1st CCA and started a new transmission in the node’s 2nd CCA slot. This can only happen if the other node started sensing in the slot just before the intended node 1st CCA slot (denoted as slot1) and the channel was then idle. The second case of assessing the 2nd CCA busy occurs when the 1st CCA idle slot was the slot between data transmission and acknowledgement (the probability of the second case occurrence is denoted byPbetaACK); then(42)βt=PIslot1∣ICCA1PSslot1+PbetaACK,where Islot1 and ICCA1 are the events of finding slot1 and CCA1 idle, respectively; the event Sslot1 is the event of start sensing in slot1.The conditional probabilityP(Islot1∣ICCA1) is the probability that a given idle slot is preceded by another idle slot,(43)PIslot1∣ICCA1=1-PBslot1∩ICCA1PICCA1=1-PBslot1∩ICCA1PBslot1∩ICCA1+PIslot1∩ICCA1,where Bslot1 it the event of finding slot1 busy; then βt can be rewritten as(44)βt=1-PBslot1∩ICCA1PBslot1∩ICCA1+PIslot1∩ICCA1PSslot1+PbetaACK.The eventICCA1 occurs in four cases.Case 1.
A busy slot before the idleCCA1 because of a failed packet transmission due to collision: this is represented by the probability PbusyFt for node t.Case 2.
A busy slot before the idleCCA1 because of an acknowledgement following a successful data transmission: this is represented by the probability PbusyAt for node t.Case 3.
A busy slot before the idleCCA1 because of a successful packet transmission where the idle slot is the interframe space in between data and acknowledgement: this is represented by the probability PbusySt for node t.Case 4.
An idle slot before the idleCCA1 happened after an acknowledged successful transmission or an unacknowledged unsuccessful transmission: this is represented by the probability Pidlet for node t.Substituting with these probabilities in (44), we have(45)βt=1-PbusyFt+PbusyAt+PbusyStPbusyFt+PbusyAt+PbusySt+Pidlet1-∏j∈Φt,j≠BS1-τj+PbusyAtPbusyFt+PbusyAt+PbusySt+Pidlet,and the expressions which define these probabilities are presented in Appendix B.(2) CAM End-to-End Analysis. In CAM, the packet generation rate λ at each node is equal, in each time unit the network will have the number of packets described by λ generated from each node, the time unit described by λ equals multiples of the TSM frame greater than λ multiplied by maximum number of allowed hops through a sub-NW, and in computing the approximate value of the packet arrival rate at a node it is assumed that all the transmitted packets to this node will be delivered successfully. It is assumed that if the BS-neighbors number does not represent the larger share in a sub-NW, they transmit their packets directly to BS and are not allowed to use multihops. The topology does not imply a specific form of doing aggregation; the routing may determine that, so no aggregation is assumed.The number of the sub-NW non-BS-neighbor members is denoted byIo and the number of the BS-neighbor members is denoted by IBS. The average packet arrival rate at the BS-neighbors λBS is greater than that of the non-BS-neighbors λo as they represent the critical zone around the BS and it depends on both Io and IBS. The whole path taken by a transmitted packet lies in a specific sub-NW, except the last hop where the last hop source, which is a BS-neighbor, switches its working channel to the working channel of the BS.Assume that a one hop of packets transmitted from each non-BS-neighbor node is completed approximately within a TSM frame time and when each node succeeds to send its packet, whether generated or forwarded, it sends it to a receiver different from whom its peers send to, whether this receiver is a BS-neighbor or not. According to that, at the completion of one packet transmission from each node, the non-BS-neighbor node will receive a number of packets ranges from 0 to(lmax-2), where lmax is the maximum path length. The final intermediate node is a BS-neighbor and the average number of packets received by a BS-neighbor in a completion of each non-BS-neighbor nodes one packet transmission is approximately equal to the number of non-BS-neighbors divided by the number of BS-neighbors in the sub-NW. Based on the previous considerations, the average packet arrival rates λo and λBS are computed as follows:(46)λo=λ1+∑x=0lmax-2xlmax-1,λBS=λ1+IoIBS.(a) Deriving Non-BS-Neighbor Different Associated Probabilities. The probability of collision of a non-BS-neighbor transmitted packet depends on the number of non-BS-neighbors in its receiver neighborhood in its sub-NW and their values of τ. For simplicity and to encounter the problem of hidden nodes to the transmitter, it is assumed that all the non-BS-neighbor members always transmit with its full range (or a range enough for covering the whole employed field), therefore no hidden nodes to the transmitter. In case the receiving node is a BS-neighbor, the number of competing nodes Ncp with a node tries to transmit will be equal to (Io-1), and in case of its being a non-BS-neighbor, Ncp equals (Io-2). Under the previous assumptions, the derivation of α, β, and P for a non-BS-neighbor is turned to be the same as followed in the single-hop communication analysis with notations and values of variables indicate a non-BS-neighbor in a sub-NW: (47)Po=1-1-τoNcp,αo=L+LackIoτo1-τoIo-11-1-τoIo1-1-τoIo-11-αo1-βo,βo=1-1-τoIo-1+Ioτo1-τoIo-12-1-τoIo+Ioτo1-τoIo-1.(b) Deriving BS-Neighbor Different Associated Probabilities. The probability of collision of a BS-neighbor transmitted packet depends on the number of BS-neighbors in all the sub-NWs and their values of τ. If the number of sub-NWs is denoted by Ns, then the number of BS-neighbors equals IBSNs; some of them may be hidden to others, where ΦtBS represents the common neighbors between the BS-neighbor t and the BS and ΦhtBS represents the hidden BS-neighbors to the BS-neighbor t. The probabilities α, β, and P are derived in the same fashion as they are derived in case of slotted CSMA/CA; except here there is no hidden acknowledgement; the set of all the children of the neighbor coordinators contains only the BS-neighbors and is defined by ΦtBS∪ΦhtBS; and successful concurrent transmissions from even two nodes do not exist.


## 3.6.2. End-to-End Reliability Analysis

The end-to-end reliabilityRe-to-e is the ANDing and in other words, the product of the probabilities of successful packet reception at each intermediate node in the considered path then to the BS,(48)Re-to-e=∏n=1lRn,where l is the path length in terms of its incorporated nodes number excluding the final destination which is the BS, Rn is the single-hop reliability of the transmitted packet by the node number n in the path, then R1 is corresponding to the first node in the path which is the source node, and Rl is corresponding to the last node in the path which is a BS child coordinator.


## 3.6.3. End-to-End Delay Analysis

By ignoring the processing delay, the average end-to-end delayDe-to-e is the summation of the average delays for successfully delivering the packet (D) at each node in the path including the PAN coordinator (BS) and the average queuing delay (w=λ/μ/μ-λ) at each intermediate node in the path, where λ here refers to the queue packet arrival rate and μ is the packet service rate.(49)De-to-e=∑n=1lwn+Dn.The channel switching time is added to the end-to-end delay in CAM case to incorporate the effect of a BS-neighbor switching to the BS channel to send its data to it (channel switching time is approximately the transmission time of a 32 byte (~1 ms) [37]).


## 3.6.4. End-to-End Energy Consumption Analysis

The total energy consumed to relay the packet through the path towards the BS is assumed to be the summation of the total energy consumed by each node in transmitting the packet to the next-hop node. For simplicity, the switching between frequency channels is assumed to consume ignorable energy:(50)Ee-to-e=∑n=1lEn.


## 3.6.5. Network Throughput Analysis

The normalized system throughput is defined and calculated here in the same way used for single-hop analysis; the difference is in the definition ofPbusy and Psuccess. If we denote the set of all nodes in the network (except BS and PAN coordinator) by Φtotal, here(51)Pbusy=1-∏i∈Φtotal1-τi,Psuccess=∑i∈ΦtotalPSTiPbusy,where PSTk, as defined in Appendix B, is the probability of successful transmission by a node.Another metric used to measure the network productivity is the goodput defined as the data bits successfully received at the BS in one time unit. The network goodputG (in bits/sec) is the summation of all nodes goodputs; let On be the set of all possible paths for delivering data from node n to the BS; then(52)G=L×20×4∑n∈Φtotal∑r∈OnRe-to-en,rDe-to-en,r.


## 4. Performance Assessment

This section assesses the performance of the proposed CAM. First, it tests the effect of different parameters on its performance, then the performance of the proposed CAM is compared to the beacon-enabled IEEE802.15.4 slotted CSMA/CA based on single-hop communication, and finally the multihop communication performance is considered. The tests’ results were analyzed for better understanding for different behaviors and getting observations and conclusions can be used for modifications and optimizations.


### 4.1. Effect of Parameters on the Proposed CAM Performance

The effect of the parametersm, traffic load represented by λ, and the tuning parameter u on the average delay, the reliability, and the power consumption of the proposed CAM is studied in this section considering a sub-NW communication example with number of nodes equal to 50 node, mb=5, and m0=3.Figures13 and 14 show that both the average delay and the reliability increase with the increase in m value, while tuning u to a higher value decreases both of them. For example, when the value of m is increased from 1 to 4 at λ=5 and u=5, the reliability increased by about 167.81%; at the same time, the delay is increased by about 107.7%; with adjusting the value of u, the delay increment percentage could be reduced to be 55.3% while the reliability still higher but with a smaller percentage about 20% when u equals 25.Figure 13
m, u, and λ effect on CAM reliability.Figure 14
m, u, and λ effect on CAM avg. delay.The change ofu value affects the possible values range of the backoff equation first term and causes the inverse effect to the range of the second term. When u is small, the first term range is bigger than the second term range which results in higher reliability because the events of modulating the value of this ID-dependent term of the 50 different nodes to the same value are smaller in this case and a greater space is left for different nodes’ IDs to differentiate their backoffs, the main principle that the backoff equation used to improve reliability, even though the sum of the delays encountered in backoff and channel sensing during the previous stages (the backoff sum) is modulated in the second term to a small range of possible values resulting in a higher percentage of recurrence for this term value. This is at the expense of increasing the delay.Changingu to higher values reduces the range of the first term value and increases the second term range which according to the previously mentioned illustration decreases both reliability and delay by a percentage decreases with m increase. The reduction percentage is decreased with m increase due to the salience of the second term effect of improving reliability at higher m values; also the delay is increased in this case because the sum of the delays which resulted from the previously encountered backoff stages is increased and the modulus of the modulo operation determines its range becomes greater.Changingu to higher values increases the first term value recurrence percentage and decreases the second term value recurrence percentage. When the second term recurrence percentage approaches the first term recurrence percentage and then becomes less than it, the reliability changes its behavior from the decrease to the increase; this appears as a convex curvature in the decayed reliability and delay curves. When the maximum backoff sum is decreased behind the modulus of the second term and continues to decrease with increasing u, at this point, the reliability continues to decrease. As shown in Figures 13 and 14, the increase of the traffic load slightly decreases the reliability and very slightly increases the delay (almost no effect on the delay appears in the figure).With regard to the energy consumption, the proposed CAM energy consumption takes the inverse behavior of the reliability with respect tou, such that, under the conditions of higher probability of collisions, higher traffic load, and higher number of retransmissions, the main components which affect the total energy consumption are of the packet transmission stage which cause its increase. The effect of the idle backoff state energy consumption appears when the time spent in backoff highly decreases when m is small (m equals 1 or less), u is high, and the traffic load is low.Generally from Figure15, the energy consumption increases when m increases from 1 to 2 due to the considerable increase of the backoff time (as m0=3 and mb=5, the third backoff stage results in double the range of possible backoff periods of the second stage, while the backoff periods are maintained on that range in the subsequent backoff stages) and the increase in the number of transmissions/retransmissions especially when the traffic load is low. The increase of the m value from the value 2 increases the reliability and decreases the power consumed in the transaction states while increasing the backoff power consumption (with lower rate) making the total energy consumption amount tend to have converged magnitudes and become approximately steady with increasing m regardless of the traffic load and u.Figure 15
m, u, and λ effect on CAM power consumption.


### 4.2. Performance Assessment Based on Single-Hop Communication

Figure16 shows the reliability of the proposed CAM and the IEEE802.15.4 slotted CSMA/CA at different backoff stages drawn versus the number of nodes, N. Also Figures 19, 20, and 21 represent the same comparison but with respect to the average delay, the average energy consumption, and the throughput of the two protocols. All values are corresponding to u=5, mb=5, m0=3, n=3, L=7Sb, and Lack=1.7Sb. As shown in Figure 16, the reliability of CAM which resulted from a certain value of m is greater than the slotted CSMA/CA reliability which resulted from the same m value with a big percentage, on average, 177%; this percentage increases when N increases. For example, at m equal to 3, the reliability is increased by about 68.3% when N is 30; this percentage increases until it becomes greater than 200% when N exceeds 60. Also, it could be noticed that, lower m values cause in CAM network more reliability than that caused by higher m values in slotted CSMA/CA, but rather as the number of nodes increases the reliability of high m values in the slotted CSMA/CA is turned to be not only smaller than its lower m values CAM reliability but also smaller than the reliability of the two backoff stages CAM.Figure 16
Slotted CSMA/CA and CAM reliability versus number of nodes.It is expectable to achieve more reliable communication using the proposed CAM as the implemented backoff mechanism is designed to decrease the channel sensing overlap among contending nodes. The CAM actually reduces the first carrier sensing probability in a randomly chosen time slot (τ); therefore the collision probability is reduced and accordingly the probability of a packet being discarded due to reaching retry limits is reduced.Regarding the probability of discarding packets due to channel access failure, as shown in Figure17, at a certain m value, it is also reduced in CAM case with percentage decreases with N increase. The approaching of the CAM and slotted CSMA/CA collision probability and probability of unsuccessful channel access (x) in a backoff stage at higher N values causes the approaching of the CAM and CSMA/CA probability of discarding packets due to channel access failure at higher N values. As shown in Figure 18, x in CAM turns to be greater than its CSMA/CA peer at higher N values. This is referred to the approaching of both of them, α value at higher N, while the β of CAM is greater than CSMA/CA due to higher occurrence of acknowledgement transmissions.Figure 17
P c f of slotted CSMA/CA and CAM versus number of nodes.Figure 18
Slotted CSMA/CA and CAM probability of unsuccessful channel access versus number of nodes.Figure 19
Slotted CSMA/CA and CAM avg. delay versus number of nodes.Figure 20
Slotted CSMA/CA and CAM energy consumption versus number of nodes.Figure 21
Slotted CSMA/CA and CAM throughput versus number of nodes.Figures19 and 20 reveal that, besides the increase of CAM reliability, with fixing m value, the energy consumption which resulted from CAM network is smaller than CSMA/CA by on average 11%, except for m equal to 1 where CSMA/CA consumes the less energy, but this is at the expense of increase in the CAM average delay over CSMA/CA by, on average, 42.6%. The range of backoff values the nodes pick from in CSMA/CA is doubled each backoff stage until its maximum limit reaches 2mb-1 and then it stabilizes on this range. In CAM, the range of backoff values possible for nodes has the upper limit 2mb-1 from the first stage (the same mb value is reinvolved in both of them) which increases its average delay over CSMA/CA average delay corresponding to the same m value. However, the decrease of CAM loss percentage appears in improving the throughput of the CAM network even though its delay is greater as shown in Figure 21, with fixing m value, and the CAM network throughput is greater than CSMA/CA by on average 117.4%,The increase percentage of the CAM average delay could be reduced by choosing them and u values. For example, considering m equal to 3 for slotted CSMA/CA in the previous comparison setup, as the reliability due to using 4 backoff stages CAM is greater than the reliability of slotted CSMA/CA in the considered case by on average 195.8% as shown in Figure 16, also the 3 backoff stages CAM results in reliability greater than it. Then from Figures 16, 19, and 20, setting m equal to 2 in CAM results in greater reliability, greater average delay, and lower power consumption than m equal to 3 slotted CSMA/CA by on average 136.3%, 8.4%, and 14.5%, respectively; this means setting m equal to 2 in the CAM results in small percentage of average delay increase while the reliability is high with a big percentage.Furthermore, tuning theu parameter via increasing its value could reduce the delay more. Figures 22, 23, 24, and 25 compare the CSMA/CA performance and CAM performance computed for different higher values of u at mb=5, m0=3, n=3, L=7Sb, and Lack=1.7Sb. From Figure 22, it could be noticed that when u is set to 8, the CAM delay is, on average, greater by 4.9%, and this percentage is reduced to be 2.25% when u equals 11, while the average reliability in this case is still greater by about 98.4% and the average energy consumption is 13.17% lower. Setting u to 14 results in reducing the average delay of the CAM by about 2.12% while the CAM reliability is still greater by 72.5% and CAM energy consumption is less by 11.94%. Further increasing u more decreases CAM average delay as well as reliability; for example, at u equal to 17, we can obtain with CAM on average a 61.35% greater reliability, 4.5% less delay, 11.4% less power consumption, and 87.8% greater throughput.Figure 22
Slotted CSMA/CA and CAM avg. delay at differentu values versus number of nodes.Figure 23
Slotted CSMA/CA and CAM reliability at differentu values versus number of nodes.Figure 24
Slotted CSMA/CA and CAM power consumption at differentu values versus number of nodes.Figure 25
Slotted CSMA/CA and CAM throughput at differentu values versus number of nodes.Also the CAM delay which resulted from settingm equal to 3 could be tuned to be close to CSMA/CA delay, but the rest of CAM performance would be worse than that reached from tuning CAM two backoff stages performance because the delay in this case is higher with a bigger percentage about 37.6%. When u is set to 23, the delay reaches 4.9% increase percentage and the CAM reliability increase and energy consumption reduction percentages are 21.2% and 2.12%, respectively. Setting u to 26 decreases both the delay and the reliability and increases the energy consumption of the CAM over the CSMA/CA.


### 4.3. Tuning theu Value

For finding the bestu value to a given performance objective, the following analysis describes with more details the effect of the whole range of possible u values, which is [0,31] for mb=5, on the performance of CAM at different parameters’ values, and compares it to the CSMA/CA performance under the same conditions. Each subfigure in Figure 26 sketches one performance metric for both CAM, indicated by solid lines, and the slotted CSMA/CA, indicated by dashed lines, computed for different values of u and m at certain value of N. The variability of the backoff time values has the biggest effect in determining the behavior of CAM reliability and accordingly the delay and energy consumption. For the communication not to BS, there is no recurrence of the possible values of the backoff equation first term without modulation due to the modulation used in it up to a certain limit uL equal to (32-N-m). After this limit, the range of the possible values for the first term decreases and the recurrence of backoff values among nodes increases.Figure 26
CAM and slotted CSMA/CA performance over the whole range of theu value.The recurrence in the second term of the equation is maximal atu=0; then it takes to decrease as u increases up to a certain limit uL′ equal to the minimum value greater than the maximum backoff sum minus one, subtracted from it one. Thus for N less than or equal to 32-m, the general tendency of the reliability curve is to increase with increasing u at lower u values and decreases with increasing u at higher u values.Between the start with increase and the ending with decrease, the reliability behavior at intermediateu values depends on uL and uL′. If uL′ is less than uL, the reliability increases up to uL′, then over the values of u between the two limits, the reliability stabilizes on a constant value because in this case there is no recurrence neither in the first term value nor in the second term value, and the maximum backoff sum is constant; after uL, the reliability decreases. This could be noticed in the constant reliability between uL′ and uL for N less than or equal to 15 at m equal to 1 and N less than or equal to 6 at m equal to 2.WhenuL is less than uL′, the interval between them encounters an increase in first term value recurrence and a decrease in the second term value recurrence; this causes, with general decaying behavior, the previously mentioned curvatures in the reliability curve, depending on the relative values of the recurrence percentage in the two terms and the maximum backoff sum values, or in better words, depending on the probability of being in the backoff state.Them=1 backoff stage causes the existence of uL; its value decreases by 1 for each N increment until it reaches 0 at N equal to 31. The value of uL in each subsequent value of m is less by one than its value at the direct previous m value; that is, the uL value reaches 0 at N equal to 30 when m equals 2, N equal to 29 when m equals 3, and so forth. uL′ value increases with N increase and up to a certain N, it stabilizes on its reached value. When m equals 1, uL′ increases until N equals 15; then it takes a constant value of 16. At m equal to 2 and N equal to 6, uL′ stabilizes on the value of 24. The limit uL′ at m equal to 3 and 4 is always constant on the values 28 and 30, respectively.Exception to the previously mentioned general behavior, it is noticed that, at highu values when m equals 1 (also when m=2 but with feeble emergence), the reliability increases rather than its expected decrease. As stated before, the backoff state is the dominant factor which determines the reliability behavior; when it increases, the first carrier sensing probability in a randomly chosen time slot decreases; as a result the sensing overlap decreases and the reliability of the transmitting node increases and vice versa. This is especially when m is higher; that is, the node stays more time in backoff states. The staying in the idle state at the queue, in contrary to the staying in the backoff state, increases with increasing u as the mean packet service times of the nodes are decreased. At high u values, low m values (m=1), and small λ (this exception is vanishing with increasing λ), the queue idle state dominates affecting the first carrier sensing probability in a randomly chosen time slot; therefore, this probability is decreased even though the backoff times variability is decreased; this illustrates the exceptional increase behavior of the reliability at high u values and m equal to 1 which gives the possibility in some cases to have higher reliability while both the delay and energy consumption are highly decreasing.The CAM performance behavior can be described for the nodes to be used as an indication for the expected performance under certain conditions to help for dynamically changing performance settings, by using lookup tables, curve fitting, approximation based on the determinable behavior mentioned before for the reliability with the backoff time values, or by some other means. For example, letN equal 10, and reliability, delay, and energy consumption curves can be fitted to construct their representative mathematical functions; for best fit, each curve can be considered upon more than one interval of u values. For example, the whole u range is divided into four intervals; each curve corresponding to an interval is fitted in a separate equation with a low degree. From these equations, the node computes the performance indications corresponding to certain m and u and optimizes the performance upon given requirements such as a reference performance values, a specific metric to be optimized, and percentages for optimizing the specified metric and permitting for resultant degradation in the other metrics.Let the reference performance be the correspondent to the current values ofm=2 and u=20, and for some reasons such as frequent loss of acknowledgements, a need for increasing reliability becomes desirable with a specified percentage 5% on condition that the delay and energy consumption do not increase with more than the same percentage; other performance variations and tolerances can be employed to deal with the situation where the mainly required performance specification cannot be achieved. In this case, the resultant values of m and u which achieve the required or the acceptable performance are 3 and 25, respectively. When the delay is the parameter to be optimized utilizing the same previous percentages, the resultant values of m and u in this case are 3 and 27, respectively. Also for some reasons such as the falling of the battery level below a threshold or the occurrence of a deviation from a determined power consumption behavior, the optimization could be directed, for example, to reach the lesser energy consumption value possible regardless of the other metrics values, which in this case is corresponding to m=1 and u=31.


### 4.4. Performance Assessment Based on Multihop Communication

The previous evaluation reveals that the required single-hop performance of CAM against the slotted CSMA/CA can be obtained by choosing them and u values and that CAM performs more better than slotted CSMA/CA in larger number of nodes. The comparisons performed in this section are based on the analysis presented in Section 3.6 for multihop performance and on the small network examples of Figure 12. For example, Node 16 in the cluster-tree network is corresponding to the following sets:(53)Φ16=1345891213141517192022,Φ16c=1345,Φ164=135891213141517192022,Φh164=0221,Φhc164=02,C16=4,ψ0=14,ψ1=121415,ψ2=71118,ψ3=6132224,ψ4=581617,ψ5=2391920.The transmission level used in the employed network example for the sub-NWs’ BS-neighbors communication with the BS results in the existence of no hidden nodes. No aggregation is assumed. The nodes were deployed randomly; therefore their IDs are randomly distributed throughout the area; ditto the aliases of a sub-NW’s members are also randomly distributed throughout its area. The CAM backoff periods are computed within a sub-NW using the aliases rather than the IDs while the IDs are used in backoff computation for the communication with the BS to cope with the repetition of aliases in different sub-NWs. It is worth noting that the communication to the BS in the CAM has a different backoff probability distribution as indicated in Section3.4.1 in Definitions 6 and 7.The following analysis compares the end-to-end performance of CAM and the slotted CSMA/CA. In CSMA/CA network, different samples of the whole network members (14, 15, 16, or 17 node) are considered in computing its performance for decreasing computation time and coping with the limitation of the used function, nchoosek, for computing neighbors’ different combinations, which is only practical for situations where the input vector length is less than about 15; then for each node, the performance corresponding to the lowest reliability is taken into account.The value ofm in the CSMA/CA network is randomly selected to be 2; the CAM network needs identification of m and u values which achieve a required performance with respect to this setting of the CSMA/CA network. According to the network example, the values of Io, IBS, and Ns are 6, 2, and 3, respectively, lmax was chosen to be 4 and λ was set to 3 pps. Other parameters were set like that mb=5, n=3, L=7Sb, and Lack=1.7Sb. By setting these parameters to these values in the analysis, computing, and comparing the performance of CSMA/CA and CAM over the whole range of possible u values based on one-hop communication as done in Section 4.3, that is, the same number of competing nodes used in CAM is used for CSMA/CA, the same λ is used, and no hidden terminal is considered for both. The obtained results are used as guiding values for determining the values of m and u for the employed example which incorporates variations on the communication parameters not only between the two networks, but also for different nodes in each network due to the nature of multihop communication.For the communication between the BS-neighbors and the BS, two combinations ofm and u are chosen to achieve the acceptable CAM performance with respect to CSMA/CA regarding the reliability and delay, 4 and 31, respectively; this combination is found to increase CAM reliability by about 13% over CSMA/CA while its delay is greater by only about 2.2%. The other combination is 6 and 31; this combination is found to increase CAM reliability by about 43.4% but at the same time increases CAM delay by about 40.9%; this can be considered to be acceptable as the reliability metric at the BS is more important and this large delay can be dealt with decreasing the previous hops delay along the remaining multihop path. For the communication among the sub-NW members when the receiver is a BS-neighbor, six combinations for m and u are chosen, 1 and 31, 4 and 31, 4 and 30, 3 and 29, 3 and 26, and 2 and 22. When the receiver is a non-BS-neighbor, four combinations for m and u are chosen, 1 and 31, 4 and 31, 4 and 30, and 3 and 30. The effects of these combinations vary among reducing both CAM reliability with small percentage and delay with high percentage, increasing both with a relatively higher percentage for the reliability, very slightly increasing reliability while decreasing delay with a relatively higher percentage, and very slightly decreasing delay with increasing reliability by a relatively higher percentage. This optimization is only based on the reliability and delay, regardless of the power consumption.Mixtures of thesem and u combinations were used in the considered example analysis and the following figures were obtained which represent the different variations of their behavior for one-hop path up to four-hop path. Each value corresponding to n-hop path represents the average of values of all the possible n-hop paths in the network.As mentioned before, the CAM offers communication reliability greater than IEEE slotted CSMA/CA exposed to the same conditions, while the multihop communication introduces additional loads on the IEEE network represented by a wider neighborhood; even though the used transmission range is smaller than CAM and the collisions due to hidden terminals. These factors participate in decreasing the IEEE slotted CSMA/CA reliability more than the estimated when the values ofm and u were being selected. The one-hop path delay of CAM is greater than its value of slotted CSMA/CA, as the concentration was on increase the reliability at the BS even at the expense of the delay; also the channel switching time at the BS-neighbor contributes in increasing CAM delay. As the length of the path in terms of hops number becomes greater, the CAM end-to-end delay falls below the slotted CSMA/CA; the start and percentage of this falling depend on the m and u combinations used for sub-NW members’ communication.As shown in Figure27, CAM 6,31-4,30-1,31, where each pair represents m and u for BS-neighbor, to BS-neighbor, and not BS-neighbor communications, respectively, results in the higher reliability percentage over all path lengths, starting with a percentage greater than 100% for one-hop path increases for lengthier paths. But the CAM delay in this case is also greater by about 54% for one-hop path; this percentage decreases until it reaches 20% less than IEEE slotted CSMA/CA delay. From Figures 27 and 28, the CAM 4,31-1,31-1,31 could be chosen to be the combinations which achieve the most preferable CAM performance with respect to end-to-end reliability and delay, where the reliability of the one-hop path is greater by about 46% and this percentage increases more than 100% for more lengthier paths; at the same time, the CAM end-to-end delay is greater only by 14.7% for the one-hop path; from the two-hop path, it starts to decrease with percentage which reaches 41% for the four-hop path.Figure 27
End-to-end reliability versus number of hops.Figure 28
Avg. end-to-end delay versus number of hops.Also under the selectedm and u values for best performance, Figures 29 and 30 declare that CAM network utilizes, on average, 80% of the channel time in transmitting useful data, while slotted CSMA/CA network utilizes about 42% of the time; besides that the CAM multihop network delivers data bits to the BS with rate equal to multiples of the CSMA/CA network data delivery rate. The subnetworking nature of CAM network and its support for multipath communication aid more in improving its performance with respect to throughput and goodput.Figure 29
Multihop network throughput.Figure 30
Multihop network goodput.The CAM exhausts more energy to achieve this performance in channel sensing, waiting acknowledgement, receiving acknowledgement, and longer backoff time at the BS-neighbors. The most important factor which increases CAM energy consumption over the IEEE slotted CSMA/CA as shown in Figure31 is the energy consumed in transmission; in IEEE network the probability of successful channel access is smaller which decreases transmission chances and accordingly the energy consumed in the transmit state. Also, the refuge of the non-BS-neighbors in CAM to transmit with a greater transmission level contributes in increasing its end-to-end energy consumption.Figure 31
Avg. end-to-end power consumption versus number of hops.


## 4.1. Effect of Parameters on the Proposed CAM Performance

The effect of the parametersm, traffic load represented by λ, and the tuning parameter u on the average delay, the reliability, and the power consumption of the proposed CAM is studied in this section considering a sub-NW communication example with number of nodes equal to 50 node, mb=5, and m0=3.Figures13 and 14 show that both the average delay and the reliability increase with the increase in m value, while tuning u to a higher value decreases both of them. For example, when the value of m is increased from 1 to 4 at λ=5 and u=5, the reliability increased by about 167.81%; at the same time, the delay is increased by about 107.7%; with adjusting the value of u, the delay increment percentage could be reduced to be 55.3% while the reliability still higher but with a smaller percentage about 20% when u equals 25.Figure 13
m, u, and λ effect on CAM reliability.Figure 14
m, u, and λ effect on CAM avg. delay.The change ofu value affects the possible values range of the backoff equation first term and causes the inverse effect to the range of the second term. When u is small, the first term range is bigger than the second term range which results in higher reliability because the events of modulating the value of this ID-dependent term of the 50 different nodes to the same value are smaller in this case and a greater space is left for different nodes’ IDs to differentiate their backoffs, the main principle that the backoff equation used to improve reliability, even though the sum of the delays encountered in backoff and channel sensing during the previous stages (the backoff sum) is modulated in the second term to a small range of possible values resulting in a higher percentage of recurrence for this term value. This is at the expense of increasing the delay.Changingu to higher values reduces the range of the first term value and increases the second term range which according to the previously mentioned illustration decreases both reliability and delay by a percentage decreases with m increase. The reduction percentage is decreased with m increase due to the salience of the second term effect of improving reliability at higher m values; also the delay is increased in this case because the sum of the delays which resulted from the previously encountered backoff stages is increased and the modulus of the modulo operation determines its range becomes greater.Changingu to higher values increases the first term value recurrence percentage and decreases the second term value recurrence percentage. When the second term recurrence percentage approaches the first term recurrence percentage and then becomes less than it, the reliability changes its behavior from the decrease to the increase; this appears as a convex curvature in the decayed reliability and delay curves. When the maximum backoff sum is decreased behind the modulus of the second term and continues to decrease with increasing u, at this point, the reliability continues to decrease. As shown in Figures 13 and 14, the increase of the traffic load slightly decreases the reliability and very slightly increases the delay (almost no effect on the delay appears in the figure).With regard to the energy consumption, the proposed CAM energy consumption takes the inverse behavior of the reliability with respect tou, such that, under the conditions of higher probability of collisions, higher traffic load, and higher number of retransmissions, the main components which affect the total energy consumption are of the packet transmission stage which cause its increase. The effect of the idle backoff state energy consumption appears when the time spent in backoff highly decreases when m is small (m equals 1 or less), u is high, and the traffic load is low.Generally from Figure15, the energy consumption increases when m increases from 1 to 2 due to the considerable increase of the backoff time (as m0=3 and mb=5, the third backoff stage results in double the range of possible backoff periods of the second stage, while the backoff periods are maintained on that range in the subsequent backoff stages) and the increase in the number of transmissions/retransmissions especially when the traffic load is low. The increase of the m value from the value 2 increases the reliability and decreases the power consumed in the transaction states while increasing the backoff power consumption (with lower rate) making the total energy consumption amount tend to have converged magnitudes and become approximately steady with increasing m regardless of the traffic load and u.Figure 15
m, u, and λ effect on CAM power consumption.


## 4.2. Performance Assessment Based on Single-Hop Communication

Figure16 shows the reliability of the proposed CAM and the IEEE802.15.4 slotted CSMA/CA at different backoff stages drawn versus the number of nodes, N. Also Figures 19, 20, and 21 represent the same comparison but with respect to the average delay, the average energy consumption, and the throughput of the two protocols. All values are corresponding to u=5, mb=5, m0=3, n=3, L=7Sb, and Lack=1.7Sb. As shown in Figure 16, the reliability of CAM which resulted from a certain value of m is greater than the slotted CSMA/CA reliability which resulted from the same m value with a big percentage, on average, 177%; this percentage increases when N increases. For example, at m equal to 3, the reliability is increased by about 68.3% when N is 30; this percentage increases until it becomes greater than 200% when N exceeds 60. Also, it could be noticed that, lower m values cause in CAM network more reliability than that caused by higher m values in slotted CSMA/CA, but rather as the number of nodes increases the reliability of high m values in the slotted CSMA/CA is turned to be not only smaller than its lower m values CAM reliability but also smaller than the reliability of the two backoff stages CAM.Figure 16
Slotted CSMA/CA and CAM reliability versus number of nodes.It is expectable to achieve more reliable communication using the proposed CAM as the implemented backoff mechanism is designed to decrease the channel sensing overlap among contending nodes. The CAM actually reduces the first carrier sensing probability in a randomly chosen time slot (τ); therefore the collision probability is reduced and accordingly the probability of a packet being discarded due to reaching retry limits is reduced.Regarding the probability of discarding packets due to channel access failure, as shown in Figure17, at a certain m value, it is also reduced in CAM case with percentage decreases with N increase. The approaching of the CAM and slotted CSMA/CA collision probability and probability of unsuccessful channel access (x) in a backoff stage at higher N values causes the approaching of the CAM and CSMA/CA probability of discarding packets due to channel access failure at higher N values. As shown in Figure 18, x in CAM turns to be greater than its CSMA/CA peer at higher N values. This is referred to the approaching of both of them, α value at higher N, while the β of CAM is greater than CSMA/CA due to higher occurrence of acknowledgement transmissions.Figure 17
P c f of slotted CSMA/CA and CAM versus number of nodes.Figure 18
Slotted CSMA/CA and CAM probability of unsuccessful channel access versus number of nodes.Figure 19
Slotted CSMA/CA and CAM avg. delay versus number of nodes.Figure 20
Slotted CSMA/CA and CAM energy consumption versus number of nodes.Figure 21
Slotted CSMA/CA and CAM throughput versus number of nodes.Figures19 and 20 reveal that, besides the increase of CAM reliability, with fixing m value, the energy consumption which resulted from CAM network is smaller than CSMA/CA by on average 11%, except for m equal to 1 where CSMA/CA consumes the less energy, but this is at the expense of increase in the CAM average delay over CSMA/CA by, on average, 42.6%. The range of backoff values the nodes pick from in CSMA/CA is doubled each backoff stage until its maximum limit reaches 2mb-1 and then it stabilizes on this range. In CAM, the range of backoff values possible for nodes has the upper limit 2mb-1 from the first stage (the same mb value is reinvolved in both of them) which increases its average delay over CSMA/CA average delay corresponding to the same m value. However, the decrease of CAM loss percentage appears in improving the throughput of the CAM network even though its delay is greater as shown in Figure 21, with fixing m value, and the CAM network throughput is greater than CSMA/CA by on average 117.4%,The increase percentage of the CAM average delay could be reduced by choosing them and u values. For example, considering m equal to 3 for slotted CSMA/CA in the previous comparison setup, as the reliability due to using 4 backoff stages CAM is greater than the reliability of slotted CSMA/CA in the considered case by on average 195.8% as shown in Figure 16, also the 3 backoff stages CAM results in reliability greater than it. Then from Figures 16, 19, and 20, setting m equal to 2 in CAM results in greater reliability, greater average delay, and lower power consumption than m equal to 3 slotted CSMA/CA by on average 136.3%, 8.4%, and 14.5%, respectively; this means setting m equal to 2 in the CAM results in small percentage of average delay increase while the reliability is high with a big percentage.Furthermore, tuning theu parameter via increasing its value could reduce the delay more. Figures 22, 23, 24, and 25 compare the CSMA/CA performance and CAM performance computed for different higher values of u at mb=5, m0=3, n=3, L=7Sb, and Lack=1.7Sb. From Figure 22, it could be noticed that when u is set to 8, the CAM delay is, on average, greater by 4.9%, and this percentage is reduced to be 2.25% when u equals 11, while the average reliability in this case is still greater by about 98.4% and the average energy consumption is 13.17% lower. Setting u to 14 results in reducing the average delay of the CAM by about 2.12% while the CAM reliability is still greater by 72.5% and CAM energy consumption is less by 11.94%. Further increasing u more decreases CAM average delay as well as reliability; for example, at u equal to 17, we can obtain with CAM on average a 61.35% greater reliability, 4.5% less delay, 11.4% less power consumption, and 87.8% greater throughput.Figure 22
Slotted CSMA/CA and CAM avg. delay at differentu values versus number of nodes.Figure 23
Slotted CSMA/CA and CAM reliability at differentu values versus number of nodes.Figure 24
Slotted CSMA/CA and CAM power consumption at differentu values versus number of nodes.Figure 25
Slotted CSMA/CA and CAM throughput at differentu values versus number of nodes.Also the CAM delay which resulted from settingm equal to 3 could be tuned to be close to CSMA/CA delay, but the rest of CAM performance would be worse than that reached from tuning CAM two backoff stages performance because the delay in this case is higher with a bigger percentage about 37.6%. When u is set to 23, the delay reaches 4.9% increase percentage and the CAM reliability increase and energy consumption reduction percentages are 21.2% and 2.12%, respectively. Setting u to 26 decreases both the delay and the reliability and increases the energy consumption of the CAM over the CSMA/CA.


## 4.3. Tuning theu Value

For finding the bestu value to a given performance objective, the following analysis describes with more details the effect of the whole range of possible u values, which is [0,31] for mb=5, on the performance of CAM at different parameters’ values, and compares it to the CSMA/CA performance under the same conditions. Each subfigure in Figure 26 sketches one performance metric for both CAM, indicated by solid lines, and the slotted CSMA/CA, indicated by dashed lines, computed for different values of u and m at certain value of N. The variability of the backoff time values has the biggest effect in determining the behavior of CAM reliability and accordingly the delay and energy consumption. For the communication not to BS, there is no recurrence of the possible values of the backoff equation first term without modulation due to the modulation used in it up to a certain limit uL equal to (32-N-m). After this limit, the range of the possible values for the first term decreases and the recurrence of backoff values among nodes increases.Figure 26
CAM and slotted CSMA/CA performance over the whole range of theu value.The recurrence in the second term of the equation is maximal atu=0; then it takes to decrease as u increases up to a certain limit uL′ equal to the minimum value greater than the maximum backoff sum minus one, subtracted from it one. Thus for N less than or equal to 32-m, the general tendency of the reliability curve is to increase with increasing u at lower u values and decreases with increasing u at higher u values.Between the start with increase and the ending with decrease, the reliability behavior at intermediateu values depends on uL and uL′. If uL′ is less than uL, the reliability increases up to uL′, then over the values of u between the two limits, the reliability stabilizes on a constant value because in this case there is no recurrence neither in the first term value nor in the second term value, and the maximum backoff sum is constant; after uL, the reliability decreases. This could be noticed in the constant reliability between uL′ and uL for N less than or equal to 15 at m equal to 1 and N less than or equal to 6 at m equal to 2.WhenuL is less than uL′, the interval between them encounters an increase in first term value recurrence and a decrease in the second term value recurrence; this causes, with general decaying behavior, the previously mentioned curvatures in the reliability curve, depending on the relative values of the recurrence percentage in the two terms and the maximum backoff sum values, or in better words, depending on the probability of being in the backoff state.Them=1 backoff stage causes the existence of uL; its value decreases by 1 for each N increment until it reaches 0 at N equal to 31. The value of uL in each subsequent value of m is less by one than its value at the direct previous m value; that is, the uL value reaches 0 at N equal to 30 when m equals 2, N equal to 29 when m equals 3, and so forth. uL′ value increases with N increase and up to a certain N, it stabilizes on its reached value. When m equals 1, uL′ increases until N equals 15; then it takes a constant value of 16. At m equal to 2 and N equal to 6, uL′ stabilizes on the value of 24. The limit uL′ at m equal to 3 and 4 is always constant on the values 28 and 30, respectively.Exception to the previously mentioned general behavior, it is noticed that, at highu values when m equals 1 (also when m=2 but with feeble emergence), the reliability increases rather than its expected decrease. As stated before, the backoff state is the dominant factor which determines the reliability behavior; when it increases, the first carrier sensing probability in a randomly chosen time slot decreases; as a result the sensing overlap decreases and the reliability of the transmitting node increases and vice versa. This is especially when m is higher; that is, the node stays more time in backoff states. The staying in the idle state at the queue, in contrary to the staying in the backoff state, increases with increasing u as the mean packet service times of the nodes are decreased. At high u values, low m values (m=1), and small λ (this exception is vanishing with increasing λ), the queue idle state dominates affecting the first carrier sensing probability in a randomly chosen time slot; therefore, this probability is decreased even though the backoff times variability is decreased; this illustrates the exceptional increase behavior of the reliability at high u values and m equal to 1 which gives the possibility in some cases to have higher reliability while both the delay and energy consumption are highly decreasing.The CAM performance behavior can be described for the nodes to be used as an indication for the expected performance under certain conditions to help for dynamically changing performance settings, by using lookup tables, curve fitting, approximation based on the determinable behavior mentioned before for the reliability with the backoff time values, or by some other means. For example, letN equal 10, and reliability, delay, and energy consumption curves can be fitted to construct their representative mathematical functions; for best fit, each curve can be considered upon more than one interval of u values. For example, the whole u range is divided into four intervals; each curve corresponding to an interval is fitted in a separate equation with a low degree. From these equations, the node computes the performance indications corresponding to certain m and u and optimizes the performance upon given requirements such as a reference performance values, a specific metric to be optimized, and percentages for optimizing the specified metric and permitting for resultant degradation in the other metrics.Let the reference performance be the correspondent to the current values ofm=2 and u=20, and for some reasons such as frequent loss of acknowledgements, a need for increasing reliability becomes desirable with a specified percentage 5% on condition that the delay and energy consumption do not increase with more than the same percentage; other performance variations and tolerances can be employed to deal with the situation where the mainly required performance specification cannot be achieved. In this case, the resultant values of m and u which achieve the required or the acceptable performance are 3 and 25, respectively. When the delay is the parameter to be optimized utilizing the same previous percentages, the resultant values of m and u in this case are 3 and 27, respectively. Also for some reasons such as the falling of the battery level below a threshold or the occurrence of a deviation from a determined power consumption behavior, the optimization could be directed, for example, to reach the lesser energy consumption value possible regardless of the other metrics values, which in this case is corresponding to m=1 and u=31.


## 4.4. Performance Assessment Based on Multihop Communication

The previous evaluation reveals that the required single-hop performance of CAM against the slotted CSMA/CA can be obtained by choosing them and u values and that CAM performs more better than slotted CSMA/CA in larger number of nodes. The comparisons performed in this section are based on the analysis presented in Section 3.6 for multihop performance and on the small network examples of Figure 12. For example, Node 16 in the cluster-tree network is corresponding to the following sets:(53)Φ16=1345891213141517192022,Φ16c=1345,Φ164=135891213141517192022,Φh164=0221,Φhc164=02,C16=4,ψ0=14,ψ1=121415,ψ2=71118,ψ3=6132224,ψ4=581617,ψ5=2391920.The transmission level used in the employed network example for the sub-NWs’ BS-neighbors communication with the BS results in the existence of no hidden nodes. No aggregation is assumed. The nodes were deployed randomly; therefore their IDs are randomly distributed throughout the area; ditto the aliases of a sub-NW’s members are also randomly distributed throughout its area. The CAM backoff periods are computed within a sub-NW using the aliases rather than the IDs while the IDs are used in backoff computation for the communication with the BS to cope with the repetition of aliases in different sub-NWs. It is worth noting that the communication to the BS in the CAM has a different backoff probability distribution as indicated in Section3.4.1 in Definitions 6 and 7.The following analysis compares the end-to-end performance of CAM and the slotted CSMA/CA. In CSMA/CA network, different samples of the whole network members (14, 15, 16, or 17 node) are considered in computing its performance for decreasing computation time and coping with the limitation of the used function, nchoosek, for computing neighbors’ different combinations, which is only practical for situations where the input vector length is less than about 15; then for each node, the performance corresponding to the lowest reliability is taken into account.The value ofm in the CSMA/CA network is randomly selected to be 2; the CAM network needs identification of m and u values which achieve a required performance with respect to this setting of the CSMA/CA network. According to the network example, the values of Io, IBS, and Ns are 6, 2, and 3, respectively, lmax was chosen to be 4 and λ was set to 3 pps. Other parameters were set like that mb=5, n=3, L=7Sb, and Lack=1.7Sb. By setting these parameters to these values in the analysis, computing, and comparing the performance of CSMA/CA and CAM over the whole range of possible u values based on one-hop communication as done in Section 4.3, that is, the same number of competing nodes used in CAM is used for CSMA/CA, the same λ is used, and no hidden terminal is considered for both. The obtained results are used as guiding values for determining the values of m and u for the employed example which incorporates variations on the communication parameters not only between the two networks, but also for different nodes in each network due to the nature of multihop communication.For the communication between the BS-neighbors and the BS, two combinations ofm and u are chosen to achieve the acceptable CAM performance with respect to CSMA/CA regarding the reliability and delay, 4 and 31, respectively; this combination is found to increase CAM reliability by about 13% over CSMA/CA while its delay is greater by only about 2.2%. The other combination is 6 and 31; this combination is found to increase CAM reliability by about 43.4% but at the same time increases CAM delay by about 40.9%; this can be considered to be acceptable as the reliability metric at the BS is more important and this large delay can be dealt with decreasing the previous hops delay along the remaining multihop path. For the communication among the sub-NW members when the receiver is a BS-neighbor, six combinations for m and u are chosen, 1 and 31, 4 and 31, 4 and 30, 3 and 29, 3 and 26, and 2 and 22. When the receiver is a non-BS-neighbor, four combinations for m and u are chosen, 1 and 31, 4 and 31, 4 and 30, and 3 and 30. The effects of these combinations vary among reducing both CAM reliability with small percentage and delay with high percentage, increasing both with a relatively higher percentage for the reliability, very slightly increasing reliability while decreasing delay with a relatively higher percentage, and very slightly decreasing delay with increasing reliability by a relatively higher percentage. This optimization is only based on the reliability and delay, regardless of the power consumption.Mixtures of thesem and u combinations were used in the considered example analysis and the following figures were obtained which represent the different variations of their behavior for one-hop path up to four-hop path. Each value corresponding to n-hop path represents the average of values of all the possible n-hop paths in the network.As mentioned before, the CAM offers communication reliability greater than IEEE slotted CSMA/CA exposed to the same conditions, while the multihop communication introduces additional loads on the IEEE network represented by a wider neighborhood; even though the used transmission range is smaller than CAM and the collisions due to hidden terminals. These factors participate in decreasing the IEEE slotted CSMA/CA reliability more than the estimated when the values ofm and u were being selected. The one-hop path delay of CAM is greater than its value of slotted CSMA/CA, as the concentration was on increase the reliability at the BS even at the expense of the delay; also the channel switching time at the BS-neighbor contributes in increasing CAM delay. As the length of the path in terms of hops number becomes greater, the CAM end-to-end delay falls below the slotted CSMA/CA; the start and percentage of this falling depend on the m and u combinations used for sub-NW members’ communication.As shown in Figure27, CAM 6,31-4,30-1,31, where each pair represents m and u for BS-neighbor, to BS-neighbor, and not BS-neighbor communications, respectively, results in the higher reliability percentage over all path lengths, starting with a percentage greater than 100% for one-hop path increases for lengthier paths. But the CAM delay in this case is also greater by about 54% for one-hop path; this percentage decreases until it reaches 20% less than IEEE slotted CSMA/CA delay. From Figures 27 and 28, the CAM 4,31-1,31-1,31 could be chosen to be the combinations which achieve the most preferable CAM performance with respect to end-to-end reliability and delay, where the reliability of the one-hop path is greater by about 46% and this percentage increases more than 100% for more lengthier paths; at the same time, the CAM end-to-end delay is greater only by 14.7% for the one-hop path; from the two-hop path, it starts to decrease with percentage which reaches 41% for the four-hop path.Figure 27
End-to-end reliability versus number of hops.Figure 28
Avg. end-to-end delay versus number of hops.Also under the selectedm and u values for best performance, Figures 29 and 30 declare that CAM network utilizes, on average, 80% of the channel time in transmitting useful data, while slotted CSMA/CA network utilizes about 42% of the time; besides that the CAM multihop network delivers data bits to the BS with rate equal to multiples of the CSMA/CA network data delivery rate. The subnetworking nature of CAM network and its support for multipath communication aid more in improving its performance with respect to throughput and goodput.Figure 29
Multihop network throughput.Figure 30
Multihop network goodput.The CAM exhausts more energy to achieve this performance in channel sensing, waiting acknowledgement, receiving acknowledgement, and longer backoff time at the BS-neighbors. The most important factor which increases CAM energy consumption over the IEEE slotted CSMA/CA as shown in Figure31 is the energy consumed in transmission; in IEEE network the probability of successful channel access is smaller which decreases transmission chances and accordingly the energy consumed in the transmit state. Also, the refuge of the non-BS-neighbors in CAM to transmit with a greater transmission level contributes in increasing its end-to-end energy consumption.Figure 31
Avg. end-to-end power consumption versus number of hops.


## 5. Conclusion and Future Work

This paper deals with completing the design of our previously proposed MAC by designing a contention-based channel access mechanism (CAM) suitable to the previously established logical topology and timing structure mechanism. The CAM is based on developing a backoff mechanism which can be performed via multiple stages and allowing multiple transmission trials. The backoff equation differentiates nodes’ backoff times depending on their different identification numbers (IDs) bearing a consideration for achieving fairness among nodes and taking into account the avoidance of error repeating after a sensing overlap, increasing the possible backoff values range each backoff stage and the possible occurrence of sensing overlap due to the computed backoff values themselves while the times of having data are different, and limiting the backoff time to a certain maximum limit regardless of the IDs and other incorporated variables’ values. A performance tuning parameter “u” which controls the maximum value of each term of the backoff equation is employed.This backoff idea is clarified using simple assumption-based simulation scenarios; then the probability distribution of the backoff period generated by a node in different backoff stages is constructed; and the Markov chain modeling is used to analyze and evaluate the CAM against the IEEE802.15.4 slotted CSMA/CA based on single-hop and multihop communication with respect to the reliability, the average delay, the power consumption, and the throughput.Changing the value of the parameteru is already found to tune these mentioned performance metrics tradeoffs, making it possible to reach a required performance objective or set different modes of operation, for example, a direct transmission mode, a zero-backoff mode, and a highest-reliability mode, by choosing variables’ values such as backoff stages number, u, and CCAs number. Likewise, adaptability and dynamic performance adjustment could be achieved by describing the computed CAM performance to nodes in some way.The CAM analysis reveals that the required performance of CAM against the IEEE slotted CSMA/CA can be obtained by choosing the backoff stages number andu values and that CAM performs richly better than the IEEE with larger number of nodes. In the single-hop communication scenario, selecting the backoff stages number to be 3 for slotted CSMA/CA and selecting the CAM backoff stages number and u to be 2 and 11, respectively, and with increasing nodes number achieve average of 98.4% higher reliability and 13.17% smaller energy consumption of CAM, while CAM delay is greater by 2.25%. Tuning u to higher values further reduces the delay; when u is 17, we can obtain with CAM a 61.35% greater reliability, 4.5% less delay, and 11.4% less power consumption.New analysis implementation is derived for the multihop network considering the effect of different classes of neighborhood, the probability of collision due the hidden terminals data and acknowledgements, and different packet arrival rate for each node. The solutions obtained for each single-hop are appropriately merged to obtain the end-to-end multihop performance. Mixtures of chosen backoff stages number andu combinations are used in the multihop scenario for the communication between the BS-neighbors and the BS and the communication among subnetwork members. One of these mixtures is chosen to be of the most preferable CAM performance where the reliability of one-hop path is greater by about 46% and this percentage increases more than 100% for more lengthier paths; at the same time, the CAM end-to-end delay is greater only by 14.7% for one-hop path; from two-hop path, it starts to decrease with percentage reaches 41% for four-hop path, but this is achieved at the expense of consuming more energy.Other optimizations on the proposed CAM can be directions for future work. The formulation of the backoff equation itself can be optimized for offering better performance. The modeling and analysis of CAM can be enhanced to consider, for example, different values for themb variable. The tests’ conditions would be varied. The devised model supports using different u values only per single-hop; supporting different u values per node which would be a possible future optimization enhances the dynamism of performance adjustment. Also, more accurate, comprehensive, and simple representation to the nodes of the derived performance tuning schemes is an enhancement which needs to be researched.



---

*Source: 7493269-2017-01-17.xml*