Performance Analyses and Improvements for IEEE 802.15.4 CSMA/CA Scheme in Wireless Multihop Sensor Networks Based on HTC Algorithm

Abstract

Most of analyses for the IEEE 802.15.4 Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) scheme for multi-hop wireless sensor networks (WSNs) focus on how to avoid the impacts of hidden terminal problems rather than how to derive the exact multi-hop characters. In this paper, we propose a novel analysis model to analyze and improve the behaviors of multi-hop WSNs touching upon both avoiding the impacts of hidden terminals and acquiring the exact multi-hop behaviors. At first, a novel Hidden Terminal Couple (HTC) algorithm is proposed to avoid the impacts of hidden terminals, and a parallel access scheme is proposed to dispense with taking the routing overhead into account. Along with these two strategies, the accurate statistical performance metrics of throughput and delay of unsaturated, unacknowledged IEEE 802.15.4 beacon-enabled networks for 1-hop and 2-hop scenarios are then predicted based on the models which contains n modified semi-Markov chains and one macro-Markov chain, in which nodes are assumed to locate randomly over a circle plane according to Poisson distribution. Moreover, performance comparisons between our scheme (called HTC scheme) and other multi-hop CSMA/CA schemes which involve hidden terminal avoiding are also proposed. Comprehensive NS-2 simulations demonstrate that the analysis results of these models match well the simulation results, especially for larger transmission range and relatively higher node density. Besides, the analysis and comparison results show that delay behavior of HTC is improved largely relatively to other schemes, while throughput performance is improved in some cases of more node density and larger transmission range.

1. Introduction

In recent years, wireless sensor networks (WSNs) have revolutionized the world of distributed systems and enabled many new applications. WSNs play more and more decisive roles in various aspects such as wide-range environmental surveillance, short-range health monitoring, inventory tracking, military locating, and so forth and almost touch upon all aspects of our life, especially after successful release of the IEEE 802.15.4 standard [1]. Besides energy efficiency requirements in WSNs that withdraw energy from batteries, other performance metrics such as service time, throughput, and so forth need to satisfy actual requirements of many real-time applications. In particular, it should take two or more hop communications into account when node transmission range is not enough to cover the entire network area for remote environmental monitoring of reserved areas which are important fields of wireless sensor networking techniques.

For multihop WSNs, the performance behaviors such as throughput, service delay energy efficiency, and so forth can be sharply deteriorated by two main reasons: the one is the impact of the “hidden terminal problem,” and the other is the establishment and maintenance of multihop routings. In contention-based wireless sensor networks, a node is not guaranteed to hear the signals from other nodes. If signals being transmitted from node A to node C cannot be sensed by node B, node B thinks that the channel is clear. As a result, node B might transmit packages to node C at the current transmitting. These two overlapped signals result in the failure of node C to capture either of the signals transmitted by node A or node B. This is called the hidden terminal problem, and node A can be considered as the hidden terminal of node B based on receiver C [2]. The hidden terminal problems bring about a large number of simultaneous transmissions or collisions, which must be eliminated or mitigated for guaranteeing network behaviors in multihop WSNs. In this paper, a novel algorithm HTC is proposed to eliminate or mitigate the impact of the hidden terminal problems.

In addition, packets should go through one or more relay nodes transmitted from the sender to the sink, and these relay nodes should be well chosen for the energy-constrained WSNs. Correct selection of the relay node plays an important role in performance behaviors, and this selection process is called the routing establishment. Packets transmitted through the same transmission path can exhaust the energy of the nodes in this path soon, and the communicating path should be altered adaptively according to the energy condition of the nodes. And also, new routings should be reestablished in the cases that any node is discarded when it exhausts its energy or a new node is joining into the communicating network. The routing establishment or maintenance can consume the overwhelming majority of energy in WSNs, even up to 80% [3]. In our energy-saving time-critical applications, a parallel access scheme is proposed to dispense with taking the routing overhead into account for multihop transmissions.

Furthermore, the existing performance analyses of CSMA/CA schemes in multihop wireless networks focus on how to mitigate the impacts of the hidden terminals [4–7] rather than how to derive the exact multihop behaviors or derive the multihop performance through the simple character superposition of several hops [8]. In this work, we propose a novel analysis model for CSMA/CA scheme based on a hidden terminal avoiding scheme HTC to analyze and improve the performance of multihop WSNs touching upon both avoiding the impacts of hidden terminals and acquiring the exact multihop behaviors, without taking the routing establishment or maintenance into account.

The rest of this paper is structured as follows. Section 2 gives a summary of related works and analysis premise of our model. A novel algorithm HTC is proposed in Section 3 to eliminate or mitigate the impact of the hidden terminal problems. Performance analysis models of multihop WSNs using semi-Markov chain models for CSMA/CA scheme and macro-Markov chain model for channel transitions are proposed in Section 4, along with a brief description of CSMA/CA scheme for IEEE 802.15.4. In Section 5, accurate analyses of throughput and delay are presented. Then, our model validations and comparisons of our model with other models using NS-2 simulator are provided in Section 6. Finally, concluding remarks and future work are presented in Section 7.

2. Related Works

Literature reviews presented here are threefold: (1) references related to the means used for avoiding the problem of hidden terminals for multihop WSNs, (2) references related to MAC schemes accompanied with routing for multihop WSNs, (3) references related to performance analyses of CSMA/CA schemes for multihop WSNs.

Many solutions have been proposed to eliminate or reduce the impact of the hidden-node problem in wireless networks [9], which can be roughly categorized as: (1) busy tone schemes; (2) Request-To-Send/Clear-To-Send (RTS/CTS) schemes, (3) carrier-sense tuning schemes, (4) hidden overhearing scheme, (5) node grouping schemes, (6) cross-layer schemes. Busy-tone multiple access method (BTMA) is proposed to evaluate and eliminate the hidden terminal problem in 1-persistent, non-persistent, and p-persistent CSMA schemes for the first time in [2], which introduces much control overhead for such a BTMA scheme. The handshake control message RTS/CTS is proposed to reserve the channel for a pair of a sender and a receiver, which can mitigate the impact of the hidden terminal problems greatly. The idea of RTS/CTS handshake is the widespread use of improving the performance of wireless networks for its simplification and efficiency such as [7, 10], and yet it is not an efficient solution for hidden terminal problems in wireless sensor networks [9]. A spatial-temporal analysis is presented in [7] to derive the real-world impact in multihop saturated and unsaturated throughput and then RTS/CTS is adopted to avoid the hidden terminal problems, in which the average number of hidden terminals is derived based on the distance between the sender and the receiver. RTS validation scheme is introduced in [10] to resolve the multihop false blocking process in which neighbors withdraw their transmissions for an entire DATA period without inquiring whether this DATA transmission is actually taking place, which can mitigate the multihop false blocking largely, but twice control messages can consume much energy in case of the relative small packet capacity. Two distributed adaptive power control algorithms which are adopted to minimize mutual interferences among links are proposed to avoid hidden terminals in [11]. Hidden overhearing is adopted in CR-MAC [12] which exchanges channel-reservation information to mitigate the impacts of hidden terminal problems and which achieves much higher throughput than RTS/CTS mode under saturated traffic. Grouping strategy [13] is a simple and efficient method to solve the IEEE 802.15.4 hidden terminals, which groups nodes according to their hidden terminal relationship and separates the transmission period into several nonoverlapping subperiods one for a group. H-NAMe scheme, a node-initiated grouping strategy, is proposed to solve the hidden terminals in [9], which is the improved strategy of [13]. A cross-layer detection and allocation (CL-DNA) scheme is proposed to solve the hidden terminal problems in IEEE 802.15.4 without the cost of extra control overhead in [14], which detects relationships of hidden nodes based on the overlapped signals and then allocates the hidden nodes into distinct sub-periods for transmissions.

In multihop wireless sensor networks, performance analyses and improvements cannot be achieved only depending on one layer schemes such as the hidden terminal avoiding strategies related above. Cross-layer designs combining MAC with routing play an important role in performance analyses and improvements of multihop networks for IEEE 802.15.4 standards, such as [15–19]. Delay Guaranteed Routing and MAC (DGRAM) protocol is proposed to reduce latency for delay-sensitive WSNs in [15], whose routes of data packets are integrated into DGRAM without considering a separate routing protocol based on slot reuse for using TDMA-based MAC. An adaptive and cross-layer framework is proposed for reliable and energy-efficient data collection in WSNs in [16], which involves an energy-aware adaptation module that captures the application's reliability requirements and autonomously configures the MAC layer based on the network topology and the traffic conditions in order to minimize the power consumption for both single-hop and multihop networking scenarios. Hybrid protocol combining contention-based and TDMA-based MAC with an embedded cross-layer optimization solution to provide routing-layer coarse-grained QoS support for latency-sensitive traffic is proposed in [17], in which a novel channel-reservation technique is proposed to significantly reduce delay by allowing packets to go through multiple hops within a single MAC frame and by also giving them higher priority channel access to reduce possible queuing delay. A transient analysis is proposed to obtain the delivery delay distribution which combines unslotted MAC with routing protocol in [18], whose nodes deploy to provide k-coverage for real-time applications. C-MAC, an optimized MAC layer based on CSMA/CA scheme for a topology of traffic destining to sink, is proposed in [19] to improve throughput for giving a larger priority to the k-tree core nodes which refer to the shortest paths to the sink containing exact k-leaves and coordinating among them to avoid collisions. Cross-layer designs are also adopted to evaluate and improve the performance of IEEE 802.11 networks, such as [20–22]. Interference level and the degree of spatial reuse of a frequency band can be controlled by varying the combination of the physical carrier-sensing (CS) range of the transmitter node and the target signal-to-interference ratio (SIR) set by the receiver node in [20], which improves throughput performance by the tradeoff between the CS range and SIR. Fairness for CSMA/CA scheme is derived by adopting only local information and performing localized operations without relying on overhearing in [21], which combines several novel rate control mechanisms including synchronized multiplicative decrease, proportional increase, and background transmission. A global optimality is derived through taking together individual optimality derived by local information for which different layers carry out distributed computation on different subsets of the decision variables in [22], which integrates three functions, congestion control, routing, and scheduling, in transport, network, and link layer into a coherent framework.

Packet transmission process using CSMA/CA scheme regardless of IEEE 802.11 or IEEE 802.15.4 can be modeled as Markov process, and most performance analyses adopt this model. The relatively early and comprehensive analysis of CSMA/CA scheme using Markov chain is presented in [23]. Other similar analyses for CSMA/CA scheme with single-hop WSNs use Markov model such as [24–27]. Two assumptions different from usual ones, which refers to the sensing of the channel probability differently from the backoff stages and the obtaining the channel probability depending on the node numbers, are proposed to improve delay and throughput and collision probability, respectively, in [28]. Similar Markov chains for performance analyses of multihop networks are presented in [29–33]. Node is assumed according to two-dimensional Poisson distribution and packet collision probability depends on the distance between the source and the destination in [29] whose two Markov chains are used for the throughput analysis, but it takes the transmission probability as the same value regardless of hops. Multihop transmission adopts master-slave manner in [30] in which GTS slots of bridge modes are allocated by the sink. Simple character superposition of several hops is presented in [31] based on assumption that arrival process at the relay is linear combination of the output processes of the source nodes, in which one Markov chain for the node CSMA/CA scheme and one Markov chain for the physical channel transition are used to analyze multihop throughput and delay. Collision domain for each node is determined based on both the interference range and routing, and the optimal flow over a given set of routes for any number of classes is derived by a flow-deviation algorithm but its Markov chain is not based on CSMA/CA scheme in [32]. A linear feedback model is introduced to evaluate characters of CSMA/CA under a general assumption about the traffic for the first time in [33].

In this work, we propose analysis models to analyze and improve the performance of CSMA/CA scheme for multihop WSNs, accompanied with a novel HTC algorithm to eliminate or mitigate the impact of the hidden terminal problem and a parallel access scheme to dispense with taking the routing overhead into account. Routing establishment and maintenance consume much energy, which is analyzed elaborately in [34, 35]. At first, the HTC algorithm is presented, in which a transmitter in 2-hop circle can randomly choose a receiver in its transmission range just the nodes in 1-hop to establish HTC pair. A parallel access scheme is proposed, in which nodes regardless of hops are bestowed on the fair chance to transmit packets to its neighbor of close upper hop circle adopting CSMA/CA scheme, until packets to sink. Then, the comprehensive models adopting n semi-Markov chains to describe the behaviors of CSMA/CA scheme for the nodes in n hops contending to the channel and one macro-Markov chain to describe the channel behaviors are proposed to analyze and improve the performance of multihop IEEE 802.15.4 CSMA/CA scheme. n denotes the number of hops which refers to the ratio of the distance from a source to the sink to the transmission range which can be denoted by $n=\lceil d/R\rceil$ , d is the distance from a transmitter to the sink, and R is the transmission range. And then, the accurate statistical performance metrics of throughput and delay of unsaturated, unacknowledged IEEE 802.15.4 beacon enabled networks for 1-hop and 2-hop scenarios are predicted based on these models and improved strategies, in which nodes are assumed to locate randomly uniformly over a circle plane according to Poisson distribution with a density of λ. Moreover, comprehensive NS-2 simulations demonstrate that the analysis results of these models match well with the simulation results, especially for larger transmission range, and relative higher node density which is refers to large-scale multihop WSNs [35]. Besides, performance comparisons between our scheme (which can simply be denoted HTC scheme) and other multihop HTC-like schemes are also proposed based on the network parameters of node density λ, transmission range R, and traffic rate γ. Analysis and simulation results show that the delay behavior of HTC scheme is obviously improved compared to other schemes, while the throughput performance is improved in some cases of more node density and larger transmission range. We can consequently extend our models to analyze 3-hop or even higher hop networks. An important character of HTC scheme is that the multihop traffic has nonpreemptive priority over each other, meaning that the traffic regardless of hops has no priority over each other and with fair opportunity to be transmitted to receivers of its upper hop rather than its peers in the same hop. And the other character is that a HTC algorithm and a parallel access scheme are adopted in the CSMA/CA scheme analyses of multihop WSNs to improve the system behaviors. To our best knowledge, this is the first analysis of the IEEE 802.15.4 CSMA/CA unsaturated scheme which touches on both how to avoid the impacts of hidden terminal problems accompanied with bringing down energy consumption of the routing establishment or maintenance and how to derive the exact multihop behaviors.

The main contributions in this paper are threefold. Firstly, a novel algorithm HTC is proposed to eliminate or mitigate the impacts of the hidden terminal problems, and a parallel access scheme to dispense with taking the routing overhead into account. Secondly, comprehensive and accurate models adopting Markov chains, combing the HTC algorithm and the parallel access scheme, are presented to analyze and improve the performance behaviors of time-critical large-scale multihop WSNs. Finally, comprehensive performance comparisons between HTC scheme and other hidden terminal avoiding schemes are proposed to validate the superiority of this time-critical scheme HTC based on the network parameters of node density, transmission range and traffic rate.

3. HTC Algorithm

As references in Section 2, the universal method to mitigate the effects of hidden terminal problems for WSNs and WLANs is the RTC/CTS handshake scheme. RTS/CTS-based methods are particularly suitable for the IEEE 802.11 networks but unsuitable for the modified CSMA/CA scheme in IEEE 802.15.4 standard for several reasons. First, data frame length is nearly identical to that of RTS/CTS frames, which leads to the same collision cost. In addition, RTS/CTS message exchanges are energy consuming for both sender and receiver. RTS/CTS is only limited to use in unicast transmissions but not in broadcast. Moreover, extra throughput degradation is introduced to WSNs according to the exposed terminal problems. And also, the relative simple and effective method to mitigate the effects of hidden terminal problems for wireless sensor networks is the grouping strategy presented in [9, 13]. Grouping algorithm has several limitations used for large-scale sensor networks. First, the maximal number of groups in WLAN is six, which is not enough for so many pending grouping sensor nodes in large-scale networks. Second, grouping establishment or maintenance consumes much more energy in large-scale sensor networks for more handshake information exchanges are needed [9, 13, 35]. Third, grouping algorithm is developed for the case of one-hop networks and consumes much energy in the case of multihop networks. Finally, nodes should participate in a special group no matter whether they have frames to transmit or not, which consumes unnecessary energy if they have no frames to be transmitted. This passive grouping algorithm is not suitable for the large-scale sensor networks.

For the large-scale multihop senor networks, the handshake information exchanges among sensor nodes can be sharply toned down through the establishment of Hidden Terminal Couple (HTC) between only two nodes. Moreover, nodes can only couple their hidden terminals when they have frames to be transmitted. This active HTC algorithm can consume much less energy for so many sensor nodes in large-scale networks.

In our large-scale multihop senor networks, nodes can eliminate or mitigate their hidden terminal effects by establishing and maintaining their Hidden Terminal Couple (HTC) pairs. We propose the HTC establishment process based on the nodes in 2-hop circle elaborately and then easily extend to the nodes in higher hop circle. HTC establishment in HTC pair establishment consists of four phases as follows.

3.1. Step 1: HTC Pair Request

After the network initialization completing, each node can be aware which hop is belong to knows its hop circle. Also, all nodes in the network can establish their one-hop neighbor list (NL) and update this NL every run stage. As the HTC request phase starts up, a transmitter T in 2-hop circle ( $R<d<\mathrm{2}R$ ) can randomly choose a receiver R in its transmission range just in 1-hop circle, and then node T will send a HTC pair request frame, Couple.request, to node R. That is to say, node T desires to establish the HTC coupled pairs with node R. This request message contains its one-hop neighbor information of node T. Node T contends the channel for this request with this request message, Couple.request, following the CSMA/CA scheme. If node T is within one-hop circle ( $d<R$ ), the coupled hidden terminal of node T is the sink, and node T transmits its Couple.request frame to the sink and establishes the HTC with the sink directly.

3.2. Step 2: HTC Information Exchange

After the Couple.request message sent from node T is correctly received by node R, node R can acquire and fuse the one-hop neighbor information of node R and node T. At the end of this fusion, node R can also derive the hidden terminals between node R and node T. Then, an acknowledgement (ACK) message is broadcast by node R. This ACK message contains the information of one-hop neighbors of R and T, following the information of hidden terminals between node R and node T. After the ACK frame is correctly received by node T, node T can start up its data fusion process. At the end of this fusion, node T can also acquire the one-hop neighbor information of node R and node T, following the hidden terminals of node R and node T.

The nodes within the one-hop circle of node R but not within the one-hop circle of node T are the hidden terminals of node T when node T transmits frames to node R, and the nodes within the one-hop circle of node T but not within the one-hop circle of node R are the hidden terminals of node R. Therefore, the nodes which are encircled by the pitch arc surrounded by, four points A, C, B, and E (i.e., $\widehat{\text{ACBEA}}$ ) that are the hidden terminals of node T. The nodes which cover the one-hop neighbors of node T except for the ones in the common area of one-hop circle between node T and node R are the hidden terminals of node R. The nodes which cover both the one-hop neighbors of node T and node R except for the ones in the common circle are the hidden terminals of HTL pair of node T and node R. Whenever node T transmits frames to node R, the hidden terminals of node T can shut off the transceivers to avoid the collisions.

After this HTC information exchange, node T and node R know the hidden terminals of each other. That is to say, the HTC coupled pairs are preliminarily established between node T and node R. Node T can choose the relay node R randomly, and the hidden terminals of node T and other relay nodes are also obtained through a similar way.

3.3. Step 3: HTC Information Notification

The relay node R can send the fused HTC message couple.notify to the sink after the HTC information is exchanged. The message couple.notify contains the hidden terminal information of the coupled pair of node T and node R. Node R notifies the sink that it establishes the HTC coupled pairs with node T, and the hidden terminals shut off their transceivers when node T transmits its packages to node R. After the HTC information is received by the sink correctly, the sink can update its HTC list, which contains the hidden terminal information of all HTC coupled pairs.

Also, the sink will exchange its one-hop neighbors with node R, and the nodes within the one-hop circle of the sink except for the common nodes of the circle centered R and the circle centered the sink are the hidden terminals of node R. These hidden terminals should shut off their transceivers when node R transmits frames to the sink. The sink is assumed to be the central node that manages all the HTC lists, and the sink fuses this hidden terminal information with the received HTC coupled information of node R and node T and establishes the HTC convergecast link list. The sink updates this link list after each transmission link buildup, such as the convergecast link of the transmission from node T and node R to the sink.

If the node T is in the one-hop ( $d<R$ ), the sink and node T are coupled each other, and the HTC list in the sink also can be regarded as the HTC convergecast link list which is actually the HTC list. In this step, the sink stores two lists which refer to the HTC list and HTC convergecast link list and updates these two lists after each transmission link build up.

3.4. Step 4: HTC Information Confirmation

After the HTC list and the HTC convergecast link list are established, the hidden terminals of the sink when node R transmits messages to the sink and the hidden terminals of node T when node T transmits messages to node R shut off their transceivers. The sink can send a message couple.confirm to node R to confirm this couple process, which contains the hidden terminal information of node R when it transmits its relayed packages to the sink and the hidden terminal information of node T when node T transmits its packages to node R. After node R receives this couple.confirm message correctly, node R can send the message couple.confirm to node T to confirm this HTC couple process. The HTC couple establishment is finished with node T receiving this couple.confirm message correctly. Collisions can be avoided or mitigated since the hidden terminals of node T in the 2-hop circle can shut off their transceivers when node T chooses a random node R in upper hop to transmit packages.

All nodes can carry out the HTC couple scheme in similar way when they have pending packages to transmit. Nodes receiving the frame can trigger the HTC of the transmission nodes and the corresponding received nodes. This active HTC algorithm can consume much less energy and can avoid or mitigate the effects of hidden terminals effectually. The sequence chart of the HTC scheme is demonstrated as Figure 2. Transmitter T in 2-hop circle can randomly choose a receiver R (relay node) in its transmission range just the node in 1-hop and send a message couple.request to node R. Node T and node R can exchange their one hop neighbors, and then the hidden terminals of each one can be derived. The HTC pair of node T and node R can be established. Node R sends this HTC establishment message couple.notify containing their hidden terminals to the sink. Sink fuses this HTC information accompanying the hidden terminal information of node R and then transmits a message couple.confirm to node R. Node R sends this couple.confirm to node T to confirm the HTC of node R and node T.

4. System Models

4.1. Slotted CSMA/CA Scheme in IEEE 802.15.4

First, we briefly explain the slotted CSMA/CA mechanism of the IEEE 802.15.4 MAC [1]. For the beacon-enabled mode, a superframe is bounded by the transmission of a beacon frame and consists of an active part and an optional inactive part in which the coordinator may go to a low-power (sleep) mode. The active part consists of three parts: beacon, contention access period (CAP), and contention-free period (CFP). Beacons, which commence at the beginning of the first slot, are used to synchronize attached nodes, identify Personal Area Networks (PANs), and describe the structure of the superframes. The CAP shall start immediately following the beacon and complete before CFP on a superframe slot boundary. All activities for nodes contending to access the channel are within this stage. The CFP, whose slots are referred to as guaranteed time slots (GTS), is reserved by the PAN coordinator for dedicated access by some devices to ensure time-critical transmission, that is, the contention-free activities. The basic time unit of the MAC protocol is the duration of the so-called backoff period. Backoff slot boundaries of every node in the PAN are aligned with superframe slot boundaries of the PAN coordinator. MAC sublayer shall ensure that the physical (PHY) commences all of its transmissions on the boundary of a backoff period. That is, each time a node wishes to transmit data frames during the CAP, it must locate the boundary of the next slot period. Moreover, before accessing the channel, it should wait a random number of backoff slots. During this period, the node is in a sleeping state to save energy. After a random delay, two slot CCAs are carried out. In this work, we only take the CAP behavior of IEEE 802.15.4 superframe into account for performance analyses.

The scheme to be implemented before accessing the channel is presented as follows when a node has pending packets to transmit. In the slotted CSMA/CA of the IEEE 802.15.4, the MAC sublayer initializes the number of backoff stage to 0 (denoted by $\text{NB}=\mathrm{0}$ ), the contention window to 2 (denoted by $\text{CW}=\mathrm{2}$ ), the retransmission stages to 0 ( $\text{RT}=\mathrm{0}$ ) and the backoff exponent to 3 (denoted by $\text{BE}={\text{BE}}_{\min }$ ). The MAC sublayer delays for a random number of periods uniformly distributed in the first backoff range [0, $W_{\mathrm{0}}-\mathrm{1}$ ]. When the backoff counter is decreased to 0, the node performs the first CCA1. If the channel is sensed idle after CCA1, CW decreases by one. If the channel is sensed idle after both consecutive CCAs, the node can access the channel successfully and then transmit packets. When the channel is sensed busy after either of the two CCAs, MAC sublayer will increase the values of $\text{NB}$ and $\text{BE}$ by one, respectively, and $\text{CW}$ is reset to 2. Backoff counters $W_i$ in which nodes randomly choose is increased exponentially accordingly ( $W_i=W_{\mathrm{0}}{\mathrm{2}}^{(\text{BE}+\mathrm{1})}$ ). If $\text{NB}$ is less than its max. value ${\text{NB}}_m(m)$ , the scheme must return to delay for a random number of periods uniformly distributed in the first backoff range $[0,W_{\mathrm{0}}-\mathrm{1}]$ ; otherwise, the node will access the channel unsuccessfully and drop the packet. $\text{NB}$ and $\text{BE}$ values depend on the number of a packet's CCA failures. If the transmitting packet is in collision or transmitted unsuccessfully, the retransmission number of $\text{RT}$ is increased by one. If $\text{RT}$ exceeds its max. value ${\text{RT}}_m$ (r), the packet is discarded due to transmission failure. This access process can be considered as the process of Markov chain, and so, we can regard this access event as a Markov model, which is shown in the following section. Our system can monitor and detect objects periodically with enough nodes which transmit a lot of collected redundant information to coordinator without acknowledgment (ACK). The impacts of ACKs on the access behaviors can be ignored adopting the extra waiting time after a transmission, which is validated in simulation results.

4.2. Markov Chains for CSMA/CA Scheme

Several assumptions are presented before deriving the analytical models.

• (1)

Nodes are randomly located in the circle plane with the sink at the center, according to a two-dimensional Poisson distribution with a density of λ, which is also elaborately analyzed in [36, 37]. We assume identical range R of the communication, interference, and carrier sensing.

(2)

Nodes regardless of hops are bestowed on the fair chance to transmit packets to its neighbor of close upper hop with CSMA/CA scheme, until packets to sink, which enable the beacon access mode available. We evaluate the hop-to-hop characters of CSMA/CA rather than end-to-end behaviors [38], without considering routing overhead. Also, propagation delay can be ignored in our multihop networks, not similar to that which takes propagation model into account in [39].

(3)

Nodes go to sleep going through a transient idle state at any of the following three situations: end of successful transmission, reaching retry limits, and reaching maximum backoff stage. Each packet length regardless of hops has the same value of L backoff units for packets transmitted from upper hop are fused by its receiver, and MAC-level ACKs can be left out of account.

(4)

Together with relayed packets from previous hops, packet arrivals of nth hop follow an average arrival rate of ${\gamma }_{\mathrm{1}},{\gamma }_{\mathrm{2}},\dots ,{\gamma }_n$ , respectively. We can only approximate the arrival process at relay nodes appropriately so that the arrival rate for $(n-\mathrm{1})$ th hop ${\gamma }_{n-\mathrm{1}}=\gamma +P_{sn}{\gamma }_n(\mathrm{2}n-\mathrm{1})/(\mathrm{2}n-\mathrm{3})$ ( $n=\mathrm{2},\dots ,\lceil d/R\rceil$ ) can be derived through an iterative method with the initial condition of ${\gamma }_n=\gamma$ according to the analysis of [40], in which $P_{sn}$ refers to the success transmission probability for nodes of nth hop.

(5)

We assume that all nodes regardless of hops contending for the channel should decrease their backoff counter to the initial values once one of them transmits successfully or packets are dropped because of accessing the channel unsuccessfully and collision [41].

In this section, n semi-Markov chain models of slotted CSMA/CA scheme of beacon enabled IEEE 802.15.4 with retry limits and one Markov chain model have shown macroscopic state transitions are presented to evaluate the metrics of throughput and packet service time which are uniquely determined by network operating points, ${\alpha }_n$ , ${\beta }_n$ , and ${\tau }_n$ of nth hop, which refer to the probability of channel sensed busy for Clear Channel Assessments (CCA1), the probability of channel sensed busy for CCA2, and the probability of nodes starting to sense the channel, respectively. We denote the hop remark n by $n=\lceil d/R\rceil$ .

First, we study CSMA/CA behavior of one node using a three-dimensional Markov chain because each node regardless of hops is bestowed on the fair chance to transit packets. We define $s(t)(s(t)\in (\mathrm{0},\dots ,m))$ as stochastic processes standing for backoff stage, in which the integer time t is corresponding to the beginning of slot times. We denote by $s=-\mathrm{1}$ and $s=-\mathrm{2}$ the status of successful transmission and failure one, respectively, which only appears at the derivation of the normalized transmission probability. When backoff stage increases over m, node accesses the channel unsuccessfully and goes to sleep state. Define $c(t)(c(t)\in (-\mathrm{2},\dots ,W_i-\mathrm{1}))$ as stochastic processes standing for backoff counter. When backoff counter is decreased to 0, the node senses the channel with probability ${\tau }_n$ for nth hop. Value $c=-\mathrm{1}$ and $c=-\mathrm{2}$ stand for CCA1 and CCA2, respectively. Define $r(t)(r(t)\in (\mathrm{0},\dots ,r))$ as states of retransmission counter. Once transmitted unsuccessfully or when a collision occurs, pending packets can be retransmitted once more and RT is increased by one. When RT increases to r, the node goes into a sleep state.

We denote actual state transition adopting solid ovals and solid arrows for IEEE 802.15.4 CSMA/CA scheme of one hop node using Markov chain. In order to demonstrate the access procedure, we can show state transitions of other hop nodes using the same Markov scheme paralleled to the actual one with dashed ovals and dashes arrows which do not exist in actual state transition seen from Figure 3. The subscript of outputs refers to node states intuitively. Variables ${\text{OF}}_{n0}~{\text{OF}}_{nr}$ are accessing failure outputs of reaching the limited backoff stage of nth hop. Variables ${\text{OC}}_{nr0}~{\text{OC}}_{nrm}$ are collision outputs of reaching the maximal retry stage for nth hop. Variables ${\text{OS}}_{n00}~{\text{OS}}_{n0m}$ to ${\text{OS}}_{nr0}~{\text{OS}}_{nrm}$ are successful transmission outputs from the first retry stage to the maximal retry stage of nth hop. All nodes regardless of hops can sense the channel after random backoff periods, and then they access the channel with respective probability after two successive idle backoff periods. In view of the process for accessing the channel, node's behavior of adopting CSMA/CA scheme can be expressed as Markov characteristics [23–27]. State transition probabilities associated with Markov chain of Figure 3 are

$$\begin{array}{cc}& P\left(\mathrm{0},k,\mathrm{0}\right)=\frac{P_{\text{in}}}{W_{\mathrm{0}}},\hspace{1em}k=\mathrm{0},\dots ,W_{\mathrm{0}},\end{array}$$

(1)

$$\begin{array}{cc}& P\left(i,k,j\mid i,k+\mathrm{1},j\right)=\mathrm{1},\end{array}$$

(2)

$$\begin{array}{cc}& P\left(i,k,j\mid i-\mathrm{1},-\mathrm{2},j\right)=\frac{\left({\alpha }_n+\left(\mathrm{1}-{\alpha }_n\right){\beta }_n\right)}{W_i},\end{array}$$

(3)

$$\begin{array}{cc}& P\left(\mathrm{0},k,j\mid i,-\mathrm{2},j-\mathrm{1}\right)=\frac{\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)P_{cn}}{W_{\mathrm{0}}},\end{array}$$

(4)

$$\begin{array}{cc}& \left(i=\mathrm{0},\dots ,m,k=\mathrm{0},\dots ,W_i,j=\mathrm{0},\dots ,r,n=\mathrm{1},\dots ,\lceil \frac{d}{R}\rceil \right).\end{array}$$

(5)

Equation (1) shows the connection between single CSMA/CA backoff procedure block and macroscopic states. Backoff counter decreases by one unit with probability one in every interval regardless of channel state shown as (2). Equation (3) stands for the probability that a node goes to next backoff stage after either failed CCA1 or CCA2 and selects a random counter. As long as $RT$ is less than r, node chooses to retransmit pending packets after any collision shown in (4).

4.3. Macroscopic State Transition

Macroscopic state transition is shown in Figure 4 with n hops of nodes. Macroscopic states which involve backoff procedures of n hops follow the same CSMA/CA algorithm from Figure 3, and we consider them as blocks. Channel macroscopic state transitions can be considered as several blocks resisted of many parallel CSMA/CA access processes in that each node regardless of hops can contend the channel to transmit its packets simultaneously, without access priority. That is to say, nodes in 2-hop circle can contend to access the channel with CSMA/CA scheme when nodes in other hop circles just contend to access the channel. We can present transition probabilities from Figures 3 and 4:

$$\begin{array}{cc}& P\left(\text{idle}\mid m,\mathrm{0},j\right)={\alpha }_n+\left(\mathrm{1}-{\alpha }_n\right){\beta }_n,\end{array}$$

(6)

$$\begin{array}{cc}& P\left(\text{idle}\mid i,\mathrm{0},r\right)=P_{cn}\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right),\end{array}$$

(7)

$$\begin{array}{cc}& P\left(\text{idle}\mid i,\mathrm{0},j\right)=\left(\mathrm{1}-P_{cn}\right)\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right),\end{array}$$

(8)

$$\begin{array}{cc}& P\left(\text{idle}\mid \text{idle}\right)=P_{\mathrm{0}},\end{array}$$

(9)

$$\begin{array}{cc}& \left(i=\mathrm{0},\dots ,m,j=\mathrm{0},\dots ,r,n=\mathrm{1},\dots ,\lceil \frac{d}{R}\rceil \right).\end{array}$$

(10)

Equations (6)–(8) stand for the probabilities that node in nth hop goes to sleep after unsuccessful access of the channel at each retry, collision at the maximal retry, and successful transmission, respectively. Equation (9) stands for the probability that the channel remains in idle state at a random time. A packet is discarded if it accesses the channel unsuccessfully or reaches retry limit. In order to obtain operating points of our multihop system, we derive expressions of ${\alpha }_n$ , ${\beta }_n$ , and ${\tau }_n(n=\mathrm{1,2},\dots ,\lceil d/R\rceil )$ for nth hop from the formulas mentioned above. Denote steady-state probabilities of Markov chain by $b_{i,k,j}=P\{s(t),c(t),r(t)=i,k,j\}$ , for $i\in (-\mathrm{2},\dots ,m)$ , $k\in (-\mathrm{2},\dots ,W_i-\mathrm{1})$ , and $j\in (\mathrm{0},\dots ,r)$ . By normalized condition of Markov chain and steady-state probability according to each hop of nodes, we obtain.

$$\begin{array}{cc}& b_{i,k,j}^n=\frac{W_i-k}{W_i}{b}_{i,\mathrm{0},j}^n,\end{array}$$

(11)

$$\begin{array}{cc}& \mathrm{1}={\displaystyle \sum }{b}^{\mathrm{1}}+{\displaystyle \sum }{b}^{\mathrm{2}}+\cdots +{\displaystyle \sum }{b}^n+b_{\text{idle}}.\end{array}$$

(12)

Then, we can derive probability expressions of each block as follows. We assume there is no maximal delay stage limitation for consideration of evaluation simplification:

$$\begin{array}{l}{b}_{i,\mathrm{0},j}^n={\left({\alpha }_n+\left(\mathrm{1}-{\alpha }_n\right){\beta }_n\right)}^i{b}_{\mathrm{0,0},j}^n,\end{array}$$

(13)

$$\begin{array}{l}{b}_{\mathrm{0,0},j}^n=\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)P_{cn}{{\displaystyle \sum }}_{i=\mathrm{0}}^m{b}_{i,\mathrm{0},j-\mathrm{1}}^n\\ \hspace{1em}\hspace{0.17em}\hspace{0.17em}={\left(\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)P_{cn}{{\displaystyle \sum }}_{i=\mathrm{0}}^m{\left({\alpha }_n+\left(\mathrm{1}-{\alpha }_n\right){\beta }_n\right)}^i\right)}^j{b}_{\mathrm{0,0},\mathrm{0}}^n,\end{array}$$

(14)

$$\begin{array}{l}{\displaystyle \sum }{b}^n={\displaystyle \sum }_{i=\mathrm{0}}^m{\displaystyle \sum }_{k=\mathrm{0}}^{W_i-\mathrm{1}}{\displaystyle \sum }_{j=\mathrm{0}}^r{b}_{i,k,j}^n+{\displaystyle \sum }_{i=\mathrm{0}}^m{\displaystyle \sum }_{j=\mathrm{0}}^r{b}_{i,-\mathrm{1},j}^n\\ \hspace{1em}\hspace{1em}\hspace{1em}+{\displaystyle \sum }_{i=\mathrm{0}}^m\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{0}}^r{b}_{i,-\mathrm{2},j}^n+{\displaystyle \sum }_{j=\mathrm{0}}^r\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{0}}^{L-\mathrm{1}}{b}_{-\mathrm{1},k,j}^n+{\displaystyle \sum }_{j=\mathrm{0}}^r\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{0}}^{L-\mathrm{1}}{b}_{-\mathrm{2},k,j}^n,\end{array}$$

(15)

$$\begin{array}{l}{b}_{\text{idle}}=P_{\mathrm{0}}+{\displaystyle \sum }_{n=\mathrm{1}}^{\lceil d/R\rceil }{\displaystyle \sum }_{i=\mathrm{0}}^m{\displaystyle \sum }_{j=\mathrm{0}}^r\left(\mathrm{1}-P_{cn}\right)b_{i,-\mathrm{2},j}^n+{\displaystyle \sum }_{n=\mathrm{1}}^{\lceil d/R\rceil }{\displaystyle \sum }_{i=\mathrm{0}}^m{P}_{cn}{b}_{i,-\mathrm{2},r}^n\\ \hspace{1em}\hspace{1em}+{\displaystyle \sum }_{n=\mathrm{1}}^{\lceil d/R\rceil }{\displaystyle \sum }_{j=\mathrm{0}}^r\left({\alpha }_n+\left(\mathrm{1}-{\alpha }_n\right){\beta }_n\right)b_{m,\mathrm{0},j}^n.\end{array}$$

(16)

Equation (15) contains probabilities of backoff process, CCA1, CCA2, successful transmission process, and failure one for nth hop. From (16) and Figure 4, idle probability consists of four parts which refer to the probability of no packet presenting in any node, successful transmission probability of each hop node, unsuccessful transmission probability for retry limits of each hop node, and unsuccessful access probability for backoff stage limits of each hop node, respectively [23–25]:

$$\begin{array}{ll}& {\displaystyle \sum }{b}^n=b_{\mathrm{0,0},\mathrm{0}}^n[\frac{\mathrm{1}-Y_n^{r+\mathrm{1}}}{\mathrm{1}-Y_n}(\frac{\mathrm{1}}{\mathrm{2}}\left(\frac{\mathrm{1}-{\left(\mathrm{2}{X}_n\right)}^{m+\mathrm{1}}}{\mathrm{1}-\mathrm{2}{X}_n}{W}_{\mathrm{0}}+\frac{\mathrm{1}-X_n^{m+\mathrm{1}}}{\mathrm{1}-X_n}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+\left(\mathrm{2}-{\alpha }_n\right)\frac{\mathrm{1}-X_n^{m+\mathrm{1}}}{\mathrm{1}-X_n}+L\left(\mathrm{1}-{\alpha }_n\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \left(\mathrm{1}-{\beta }_n\right)\left(\mathrm{1}-X_n^{m+\mathrm{1}}\right)\phantom{\frac{\mathrm{1}-{\left(\mathrm{2}{X}_n\right)}^{m+\mathrm{1}}}{\mathrm{1}-\mathrm{2}{X}_n}})\phantom{\frac{\mathrm{1}-Y_n^{r+\mathrm{1}}}{\mathrm{1}-Y_n}}],\end{array}$$

(17)

$$\begin{array}{l}{b}_{\text{idle}}=P_{\mathrm{0}}+{\displaystyle \sum }_{n=\mathrm{1}}^{\lceil d/R\rceil }{b}_{\mathrm{0,0},\mathrm{0}}^n\left(\frac{X_n^{m+\mathrm{1}}\left(\mathrm{1}-Y_n^{r+\mathrm{1}}\right)}{\mathrm{1}-Y_n}+P_{cn}\left(\mathrm{1}-X_n^{m+\mathrm{1}}\right)Y_n^r\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}+{\displaystyle \sum }_{n=\mathrm{1}}^{\lceil d/R\rceil }{b}_{\mathrm{0,0},\mathrm{0}}^n\left(\mathrm{1}-P_{cn}\right)\frac{\left(\mathrm{1}-X_n^{m+\mathrm{1}}\right)\left(\mathrm{1}-Y_n^{r+\mathrm{1}}\right)}{\mathrm{1}-Y_n},\end{array}$$

(18)

$$\begin{array}{l}{X}_n={\alpha }_n+\left(\mathrm{1}-{\alpha }_n\right){\beta }_n,\hspace{1em}n=\mathrm{1},\dots ,\lceil \frac{d}{R}\rceil ,\end{array}$$

(19)

$$\begin{array}{l}{Y}_n=P_{cn}\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)\frac{\mathrm{1}-X_n^{m+\mathrm{1}}}{\mathrm{1}-X_n}.\end{array}$$

(20)

In unsaturated conditions, a node will try to transmit only when new packets arrive at this node from upper layers. Substituting (15) and (16) into (12), we obtain that the normalized probability is related to variables $b_{\mathrm{0,0},\mathrm{0}}^n$ shown as (17). Node has a packet to transmit at the next backoff slot with the probability $P_n$ for nth hop. For example, the node in 1-hop can start to transmit at the boundary of next slot with the probability of $({\gamma }_{\mathrm{1}}/L{)}^{N_{\mathrm{1}}}$ in condition that the other hop nodes have no new packet arrivals with the probability of $(\mathrm{1}-{\gamma }_{\mathrm{2}}/L{)}^{N_{\mathrm{2}}}(\mathrm{1}-{\gamma }_{\mathrm{3}}/L{)}^{N_{\mathrm{3}}}\cdots (\mathrm{1}-{\gamma }_n/L{)}^{N_n}$ , and the node in 2-hop can start to transmit at the boundary of next slot with the probability of $({\gamma }_{\mathrm{2}}/L{)}^{N_{\mathrm{2}}}$ in condition that the other hop nodes have no new packet arrivals with the probability of $(\mathrm{1}-{\gamma }_{\mathrm{1}}/L{)}^{N_{\mathrm{1}}}(\mathrm{1}-{\gamma }_{\mathrm{3}}/L{)}^{N_{\mathrm{3}}}\cdots (\mathrm{1}-{\gamma }_n/L{)}^{N_n}$ , and so on, in which $N_{\mathrm{1}}=\lambda \pi R^{\mathrm{2}}$ , $N_{\mathrm{2}}=\mathrm{3}\lambda \pi R^{\mathrm{2}},\dots$ , and $N_n=(\mathrm{2}n-\mathrm{1})\lambda \pi R^{\mathrm{2}}$ are the number of nodes in nth hop, respectively. Probability $P_{\mathrm{0}}$ in Figure 4 shows that there is no pending packet in random slot time that can be simply expressed as $(\mathrm{1}-{\gamma }_{\mathrm{1}}/L{)}^{N_{\mathrm{1}}}(\mathrm{1}-{\gamma }_{\mathrm{2}}/L{)}^{N_{\mathrm{2}}}\cdots (\mathrm{1}-{\gamma }_n/L{)}^{N_n}$ . According to Markov blocks of macroscopic state transition in (1) and Figure 4, we can derive relations between semi-Markov model blocks of single CSMA/CA scheme and macro-Markov model of integral channel, that is, probability $P_{\text{in}}$ in Figure 1 and (1) can be presented as one of $P_{\mathrm{1}},P_{\mathrm{2}},\dots ,P_n$ in Figure 2. We can express all components of (12) as the functions of the variable $Q_{L_{\mathrm{0}}}$ which refers to idle state length in the state transition. In such way, we can derive all parameters in the system using numerical method that solves the nonlinear equations given by (21) and (12):

$$\begin{array}{l}{b}_{\mathrm{0,0},\mathrm{0}}^n=Q_{L_{\mathrm{0}}}{\left(\mathrm{1}-\frac{{\gamma }_{\mathrm{1}}}{L}\right)}^{N_{\mathrm{1}}}\cdots {\left(\frac{{\gamma }_n}{L}\right)}^{N_n}\cdots {\left(\mathrm{1}-\frac{{\gamma }_{\lceil d/R\rceil }}{L}\right)}^{N_{\lceil d/R\rceil }},\\ \phantom{b_{\mathrm{0,0},\mathrm{0}}^n=Q_{L_{\mathrm{0}}}{\left(\mathrm{1}-\frac{{\gamma }_{\mathrm{1}}}{L}\right)}^{N_{\mathrm{1}}}\cdots {\left(\frac{{\gamma }_n}{L}\right)}^{N_n}\cdots \text{ddd}}n=\mathrm{1},\dots ,\lceil \frac{d}{R}\rceil .\end{array}$$

(21)

Figure 1

The establishment of HTC algorithm.

Figure 2

Sequence chart of the establishment of HTC algorithm.

Figure 3

Markov chain model for slotted IEEE 802.15.4 CSMA/CA scheme.

Figure 4

Macroscopic states transition. Outputs within blocks are those one-to-one corresponding outputs in Figure 3.

5. Performance Analysis

Probability that a node in nth hop attempts to sense the channel for the first time (CCA1) in a randomly chosen time slot is denoted by ${\tau }_n$ , representing backoff counter decreased to 0. It is a fact that the collisions occur at the receiver, whereas the CSMA/CA scheme checks the status of the medium at the transmitter [42]. We can analyze the channel contending behaviors at the viewpoint of the source rather than receivers, which simplifies the metric predictions but does not undermine the accurateness shown in the simulations later. This approximate method is usually adopted to analyze channel behaviors, such as [25–27]:

$$\begin{array}{l}{\tau }_n={\displaystyle \sum }_{i=\mathrm{0}}^m{\displaystyle \sum }_{j=\mathrm{0}}^r{b}_{i,\mathrm{0},j}^n=\frac{\mathrm{1}-X_n^{m+\mathrm{1}}}{\mathrm{1}-X_n}\frac{\mathrm{1}-Y_n^{r+\mathrm{1}}}{\mathrm{1}-Y_n}{b}_{\mathrm{0,0},\mathrm{0}}^n,\\ \phantom{{\tau }_n={\displaystyle \sum }_{i=\mathrm{0}}^m{\displaystyle \sum }_{j=\mathrm{0}}^r{b}_{i,\mathrm{0},j}^n=\frac{\mathrm{1}-X_n^{m+\mathrm{1}}}{\mathrm{1}-X_n}d}n=\mathrm{1},\dots ,\lceil \frac{d}{R}\rceil .\end{array}$$

(22)

We analyze the exact behaviors of separate hop, and the operating points of nth hop are denoted by ${\alpha }_n$ , ${\beta }_n$ and ${\tau }_n$ . Transmission characteristics for the case of 1-hop and 2-hop are elaborately considered in this section. Shown in Figure 1, a source node T in 2-hop circle area $S_{\mathrm{3}}$ randomly chooses a receiver R in the 1-hop circle area $S_{\mathrm{2}}$ . Assume that d ( $d\in (R,\mathrm{2}R]$ ) is the distance of node T from the sink, l ( $l\in [\mathrm{0},R]$ ) is the distance of node R from the sink, and θ is the deflection angle of node R deflected from the direction of node T and the sink.

The hidden terminals of node T when the source node T transmits, denoted by the nodes in the area encircled by the pitch arc $\widehat{\text{ACBEA}}$ , can be left out simply adopting the algorithm HTC. Denote area symbols of $S_{\mathrm{1}},S_{\mathrm{2}},\dots ,S_{\mathrm{6}}$ which are the abbreviations of $S_{\mathrm{1}}(d),S_{\mathrm{2}}(d),\dots ,S_{\mathrm{6}}(d)$ by the respective average number of sensor nodes for simple expressions, which are products of node density and the respective actual area for our first assumption:

$$\begin{array}{l}{\alpha }_{\mathrm{2}}=\left(L+L_{\text{ex}}\right)\\ \hspace{1em}\hspace{1em}\times \{\left(\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{3}}-\mathrm{1}}\right)\left(\mathrm{1}-{\alpha }_{\mathrm{2}}\right){\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}}\\ \hspace{1em}\hspace{1em}\hspace{1em}+{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{3}}-\mathrm{1}}\left(\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}}\right)\left(\mathrm{1}-{\alpha }_{\mathrm{1}}\right)\},\end{array}$$

(23)

$$\begin{array}{l}{\beta }_{\mathrm{2}}=\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{3}}}{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{5}}},\end{array}$$

(24)

in which nodes in area of $S_{\mathrm{5}}$ refer to the receive area and the coupled area of node T and node R. Channel is sensed busy after CCA1 with the probability ${\alpha }_{\mathrm{2}}$ for 2-hop can be expressed as the contending relations of two parts $S_{\mathrm{3}}$ and $S_{\mathrm{5}}$ . Nodes in hidden terminal area $\widehat{\text{ACBEA}}$ can be left out of account for adopting HTC algorithm, and nodes in 3-hop area can also be ignored for only considering the 2-hop network performance. When the channel is sensed busy after CCA1 with probability ${\alpha }_{\mathrm{2}}$ for 2-hop due to data transmission of other nodes, it means that at least one of $S_{\mathrm{3}}$ remaining nodes transmits in the same slot with the current transmitting node and none of $S_{\mathrm{5}}$ transmits, or none of remaining $S_{\mathrm{3}}$ transmits and at least one of $S_{\mathrm{5}}$ transmits [24]. We can present as a simplified form of (23) illustrated in Figure 3. And the area of $S_{\mathrm{3}}$ and $S_{\mathrm{5}}$ can be derived as follows:

$$\begin{array}{l}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}{S}_{\mathrm{3}}\left(d\right)=\lambda \pi R^{\mathrm{2}}-S_{\mathrm{2}}\left(d\right)-S_{\mathrm{4}}\left(d\right),\\ S_{\mathrm{5}}\left(d\right)=S_{\widehat{\text{EBDE}}}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}=\mathrm{2}\lambda {{\displaystyle \int }}_{d/\mathrm{2}}^R\left(\sqrt{R^{\mathrm{2}}-{\left(d-x-l\cos \theta \right)}^{\mathrm{2}}}-l\sin \theta \right)dx\\ \hspace{1em}\hspace{1em}\hspace{1em}+\mathrm{2}\lambda {{\displaystyle \int }}_{d/\mathrm{2}}^R\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}dx,\\ S_{\mathrm{4}}\left(d\right)=\mathrm{2}\lambda ({{\displaystyle \int }}_{\left(\mathrm{3}{R}^{\mathrm{2}}-d^{\mathrm{2}}\right)/\mathrm{2}d}^R\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}dx\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}-{{\displaystyle \int }}_{d+\left(\mathrm{3}{R}^{\mathrm{2}}-d^{\mathrm{2}}\right)/\mathrm{2}d}^{\mathrm{2}R}\sqrt{\mathrm{4}{R}^{\mathrm{2}}-x^{\mathrm{2}}}dx),\\ \hspace{1em}\hspace{1em}{S}_{\mathrm{2}}\left(d\right)=\mathrm{4}\lambda {{\displaystyle \int }}_{d/\mathrm{2}}^{\mathrm{2}R}\sqrt{\mathrm{4}{R}^{\mathrm{2}}-x^{\mathrm{2}}}dx.\end{array}$$

(25)

We can derive the numbers of $S_{\mathrm{2}}$ , $S_{\mathrm{3}}$ , $S_{\mathrm{4}}$ , and $S_{\mathrm{5}}$ from a spatial viewpoint. Since a homogeneous Poisson point process can be regarded as the limiting uniform distribution on the condition of large area and high node density [29, 43], a source T randomly chosen in the sink transmission range can be approximated as following uniform distribution, and the probability density function (PDF) of the distance d can be denoted by $f(d)$ ( $f(d)=\mathrm{2}d/R^{\mathrm{2}}$ ). We can derive the average statistical medium behavior based on the average value of $d={\int }_{\mathrm{0}}^{R}f(x)x\hspace{0.17em}dx$ . Probability ${\beta }_{\mathrm{2}}$ which refers to the channel sensed busy after CCA2 can be derived a similar way to ${\alpha }_{\mathrm{2}}$ .

We can derive the operating points of 1-hop in a similar way to that of 2-hop. We can refer the hidden terminal area of node R to the circle area with center at the sink except for the common area between node R and the sink, denoted by $(\pi R^{\mathrm{2}}-S_{\widehat{\text{CBDEC}}})$ which can be left out of account in deriving ${\alpha }_{\mathrm{1}}$ and ${\beta }_{\mathrm{1}}$ for the operating points of 1-hop. Channel is sensed busy after CCA1 with the probability ${\alpha }_{\mathrm{1}}$ for 1-hop can be expressed as the contending relations of two parts $S_{\mathrm{5}}$ and $S_{\mathrm{6}}$ , which is similar to ${\alpha }_{\mathrm{2}}$ . We can present as a simplified form of (26) illustrated in Figure 3, in which is taken into account because none of the receiving area including the receiver can transmit when node R transmits:

$$\begin{array}{l}{\alpha }_{\mathrm{1}}=\left(L+L_{\text{ex}}\right)\\ \hspace{1em}\hspace{1em}\times \{\left(\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}-\mathrm{1}}\right)\left(\mathrm{1}-{\alpha }_{\mathrm{1}}\right){\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{6}}}\\ \hspace{1em}\hspace{1em}\hspace{1em}+{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}-\mathrm{1}}\left(\mathrm{1}-{\alpha }_{\mathrm{2}}\right)\left(\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{6}}}\right)\},\end{array}$$

(26)

$$\begin{array}{l}{\beta }_{\mathrm{1}}=\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}}{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{6}}}.\end{array}$$

(27)

We can derive the operating points of 1-hop in similar way to that of 2-hop. We can denote the hidden terminal area of node R by $(\pi R^{\mathrm{2}}-S_{\widehat{\text{CBDEC}}})$ . There are four parts of nodes that can influence the transmission of node R, which refer to nodes in area $\widehat{\text{EBDE}}$ , nodes in area $\widehat{\text{CBEC}}$ , nodes in area $\widehat{\text{CEAC}}$ , and nodes in area $\widehat{\text{EADE}}$ . The nodes in area $\widehat{\text{ACBEA}}(\widehat{\text{CBEC}}+\widehat{\text{CEAC}})$ are the hidden terminals of node T which are left out of account for the established hidden terminals using HTC scheme. So, channel is sensed busy after CCA1 with the probability ${\alpha }_{\mathrm{1}}$ for 1-hop can be expressed as the contending relations of two parts $S_{\mathrm{5}}$ and $S_{\mathrm{6}}$ , which is similar to ${\alpha }_{\mathrm{2}}$ . We can explain the equation 26 with a simplified form as illustrated in Figure 1, in which one of $S_5$ remaining nodes transmits in the same slot with the current transmitting node and none of $S_6$ transmits, or none of remaining $S_5$ transmits and at least one of $S_6$ transmits.

$$\begin{array}{l}{S}_{\mathrm{6}}\left(d\right)=S_{\widehat{\text{EDAE}}}=S_{\widehat{\text{AEBDA}}}-S_{\mathrm{5}}\left(d\right),\\ \hspace{1em}{S}_{\widehat{\text{AEBDA}}}=\mathrm{4}\lambda {{\displaystyle \int }}_{d^{\prime }/\mathrm{2}}^R\sqrt{R^{\mathrm{2}}-x^{\mathrm{2}}}dx,\\ \hspace{1em}{d}^{\prime }=\sqrt{l^{\mathrm{2}}+d^{\mathrm{2}}-\mathrm{2}ld\cos \theta }.\end{array}$$

(28)

5.1. Throughput Analysis

We denote by S the normalized system throughput defined as the fraction of time for the channel is used to successfully transmit payload bits. A random chosen slot consists of three fractions: the time for successful transmission, the time for collision and the time for idle or sleeping. Collision probability $P_{c\mathrm{2}}$ of 2-hop can be denoted as (29), in which $P_{tr2}$ is the transmission probability of 2-hop which means at least one node in $S_{\mathrm{3}}$ transmits, while none of $S_{\mathrm{5}}$ transmits:

$$\begin{array}{l}{P}_{c\mathrm{2}}={\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}}{\displaystyle \sum }_{k=\mathrm{2}}^{S_{\mathrm{3}}}\left(\begin{array}{l}{S}_{\mathrm{3}}\\ k\end{array}\right)P_{tr\mathrm{2}}^k{\left(\mathrm{1}-P_{tr\mathrm{2}}\right)}^{S_{\mathrm{3}}-k}\\ \hspace{1em}\hspace{1em}+{\displaystyle \sum }_{m=\mathrm{1}}^{S_{\mathrm{3}}}\left(\begin{array}{l}{S}_{\mathrm{3}}\\ k\end{array}\right)P_{tr\mathrm{2}}^m{\left(\mathrm{1}-P_{tr\mathrm{2}}\right)}^{S_{\mathrm{3}}-\mathrm{1}-k}\\ \hspace{1em}\hspace{1em}\times {\displaystyle \sum }_{l=\mathrm{1}}^{S_{\mathrm{5}}}\left(\begin{array}{l}{S}_{\mathrm{5}}\\ k\end{array}\right)P_{tr\mathrm{1}}^l{\left(\mathrm{1}-P_{tr\mathrm{1}}\right)}^{S_{\mathrm{5}}-l},\end{array}$$

(29)

$$\begin{array}{l}{P}_{s\mathrm{2}}=\frac{S_{\mathrm{3}}{\tau }_{\mathrm{2}}{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{3}}-\mathrm{1}}}{\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{3}}}}\end{array}$$

(30)

The probability $P_{c\mathrm{1}}$ and $P_{tr\mathrm{1}}$ can be derived in a similar way to $P_{c\mathrm{2}}$ and $P_{tr\mathrm{2}}$ shown as follows:

$$\begin{array}{l}{P}_{c\mathrm{1}}={\left(\mathrm{1}-{\tau }_{\mathrm{2}}\right)}^{S_{\mathrm{6}}}{\displaystyle \sum }_{k=\mathrm{2}}^{S_{\mathrm{5}}}\left(\begin{array}{l}{S}_{\mathrm{5}}\\ k\end{array}\right)P_{tr\mathrm{1}}^k{\left(\mathrm{1}-P_{tr\mathrm{1}}\right)}^{S_{\mathrm{5}}-k}\\ \hspace{1em}\hspace{1em}+{\displaystyle \sum }_{m=\mathrm{1}}^{S_{\mathrm{5}}}\left(\begin{array}{l}{S}_{\mathrm{5}}\\ k\end{array}\right)P_{tr\mathrm{1}}^m{\left(\mathrm{1}-P_{tr\mathrm{1}}\right)}^{S_{\mathrm{5}}-\mathrm{1}-k}\\ \hspace{1em}\hspace{1em}\times {\displaystyle \sum }_{l=\mathrm{1}}^{S_{\mathrm{6}}}\left(\begin{array}{l}{S}_{\mathrm{2}}\\ k\end{array}\right)P_{tr\mathrm{2}}^l{\left(\mathrm{1}-P_{tr\mathrm{2}}\right)}^{S_{\mathrm{6}}-l},\\ \hspace{1em}\hspace{1em}\hspace{1em}{P}_{s\mathrm{1}}=\frac{S_{\mathrm{5}}{\tau }_{\mathrm{1}}{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}-\mathrm{1}}}{\mathrm{1}-{\left(\mathrm{1}-{\tau }_{\mathrm{1}}\right)}^{S_{\mathrm{5}}}}.\end{array}$$

(31)

Thus, throughput expression S of nth hop is derived through these parts:

$$\begin{array}{l}{S}_n=\frac{P_{trn}{P}_{sn}{E}_n\left[P\right]}{\left(\mathrm{1}-P_{trn}{P}_{sn}-P_{cn}\right)\sigma +P_{trn}{P}_{sn}{T}_s+P_{cn}{T}_c},\\ \phantom{{\displaystyle \sum }_{l=\mathrm{1}}^{S_{\mathrm{6}}}\left(\begin{array}{l}{S}_{\mathrm{2}}\\ k\end{array}\right)P_{\mathrm{tr}\mathrm{2}}^l{\left(\mathrm{1}-P_{\mathrm{tr}\mathrm{2}}\right)}^{S_{\mathrm{6}}-l},d}n=\mathrm{1,2},\dots ,\lceil \frac{d}{R}\rceil .\end{array}$$

(32)

Average packet payload size is $E[P]$ in number of slots for each node of nth hop. Time $T_s$ and $T_c$ are the channel sensed busy duration due to a successful transmission and collision, respectively. For no ACKs of our CSMA/CA scheme, the channel remains awake after successful or failed state for extra two slot durations. We can derive the time in (32) with assumption $t_s=t_c=t_L$ , where $t_{\text{CCA}}$ , $t_s$ , $t_c$ , and $t_{\text{ex}}$ are the time for performing CCA, successful transmission, data collision, and keeping waiting for extra slots, respectively:

$$\begin{array}{l}{T}_s=\mathrm{2}\lceil t_{\text{CCA}}\rceil +\lceil t_s\rceil +\lfloor t_{\text{ex}}\rfloor ,\\ T_c=\mathrm{2}\lceil t_{\text{CCA}}\rceil +\lceil t_c\rceil +\lfloor t_{\text{ex}}\rfloor \end{array}$$

(33)

5.2. Delay Analysis

Access delay is also an important metric in low-rate wireless applications, especially for our time-critical systems. Define access delay, or packet service time, as the instant from the moment when packet arrives at a node to be transmitted to the moment when the receiver receives the packet. Packet service time is independent of the hop circle because the independent parallel access scheme is proposed for different hops and the hop-to-hop delay is taken into account only. We present all time consumption in backoff period. Define $T_t(Z)$ as the PGF (probability generating function) of packet service time and we can derive each component of it. Since the packet size is fixed and owing to the assumption that every node sees the same long-term channel condition, packet service time is the same for nodes in the same hop circle:

$$\begin{array}{l}{T}_{tr}^n\left(Z\right)=Z^{L+L_{\text{ex}}}\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)\left(\mathrm{1}-P_{cn}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\times {\displaystyle \sum }_{j=\mathrm{0}}^r{\left({\displaystyle \sum }_{i=\mathrm{0}}^m{\left(\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)\right)}^i{P}_{cn}{Z}^{L+L_{\text{ex}}}\right)}^j\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\times {\left(Z^{\mathrm{2}+T_{\text{ta}}}{\displaystyle \sum }_{i=\mathrm{0}}^m{B}_i\left(Z\right)F_i\left(Z\right)\right)}^{j+\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+{\displaystyle \sum }_{j=\mathrm{0}}^r{\left({\displaystyle \sum }_{i=\mathrm{0}}^m{\left(\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)\right)}^i{P}_{cn}{Z}^{L+L_{\text{ex}}}\right)}^j{X}^{m+\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\times {\left(Z^{\mathrm{2}+T_{\text{ta}}}{\displaystyle \sum }_{i=\mathrm{0}}^m{B}_i\left(Z\right)F_i\left(Z\right)\right)}^j{B}_{m+\mathrm{1}}\left(Z\right)F_{m+\mathrm{1}}\left(Z\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+{\displaystyle \sum }_{i=\mathrm{0}}^m{\left({\left(\left(\mathrm{1}-{\alpha }_n\right)\left(\mathrm{1}-{\beta }_n\right)\right)}^i{P}_{cn}{Z}^{L+L_{\text{ex}}}\right)}^{r+\mathrm{1}}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\times {\left(Z^{\mathrm{2}+T_{\text{ta}}}{\displaystyle \sum }_{i=\mathrm{0}}^m{B}_i\left(Z\right)F_i\left(Z\right)\right)}^{r+\mathrm{1}}.\end{array}$$

(34)

PGF for the effective durations of the backoff period and sensing failure in (34) are derived as follows:

$$\begin{array}{l}{B}_i\left(Z\right)={\displaystyle \prod }_{k=\mathrm{0}}^i\hspace{0.17em}{\displaystyle \sum }_{l=\mathrm{0}}^{W_k}\frac{\mathrm{1}}{W_k}{Z}^l={\displaystyle \prod }_{k=\mathrm{0}}^i\frac{\mathrm{1}}{W_k}\frac{\mathrm{1}-Z^{W_k}}{\mathrm{1}-Z},\\ F_i^n\left(Z\right)={\displaystyle \sum }_{k=\mathrm{0}}^i{\alpha }_n^k{Z}^k{\displaystyle \sum }_{k=\mathrm{0}}^i{\left(\left(\mathrm{1}-{\alpha }_n\right){\beta }_n\right)}^k{Z}^{\mathrm{2}k}.\end{array}$$

(35)

PGF of access delay consists of three factions as shown in (34): PGF for successful transmission, PGF for access failure, and PGF for reaching retry limits. Transmission commences as the channel being sensed idle for two CCAs, as factor $Z^{\mathrm{2}}$ in each part of (34) Each backoff stage is followed by a short turnaround period $T_{\text{ta}}$ for we consider nodes sleeping in backoff decrement process. So, access delay can be derived through solving the PGF: $\overline{T_{tr}^n}=T_{tr}^{\prime }(\mathrm{1})$ ,   $\overline{T_{tr}^{n(\mathrm{2})}}=T_{tr}^{\mathrm{\prime \prime }}(\mathrm{1})+T_{tr}^{\prime }(\mathrm{1})$ .

6. Model Validations

We present extensive simulations of slotted CSMA/CA of IEEE 802.15.4 to validate the accuracy of evaluated metrics for throughput and delay of HTC scheme using NS-2 simulator according to previous analyses. NS-2 is a popular discrete-event simulator which was originally designed for wired networks and has been subsequently extended to support wireless simulations [44]. The accuracy of evaluated expressions for throughput and delay is validated through extensive comprehensive simulations which are derived based on analyses of different parameters such as packet arrival rate, packet size, node density, transmission range, and so forth.

Nodes are randomly located in the circle according to a two-dimensional Poisson distribution with the sink at the center to simplify both the closed form expressions and the model of the hidden terminals. Node can be aware of its own hop number once it is presented in the system through the data header. Packet length is normalized as backoff period including the PHY header and MAC header. We assume that the entire superframe duration is active. Moreover, impacts of the beacon concluded in data packet can be neglected in this issue for the beacon order is set to 4. Each turnaround process is assumed to consume the same time and energy for simplification. Parameters used in simulations are listed in Table 1, and packet length and some of MAC parameters touched upon simulations are listed in the head of result figures. Experimental setups of NS-2 simulator used to conduct validations are similar to presentations in [45] in detail, and the propagation delay can be ignored in our scheme simulations. We validate the performance of our analyses firstly, considering 2-hop and 1-hop behaviors. Then, we compare the performance of our schemes with that of previous schemes such as Koubâa's [9] and Tseng's [14]. Besides, we can derive the characters of multihop networks by extending our analyses to higher hops. Our simulation results are mean values derived from 30 experience values for each scenario.

Table 1

The parameters of our simulations.

aNumSuperframeSlots	960 symbols	$L_{\text{data}}$ (packet length)	1600  $\mu s$
aUnitBackoffPeriod	20 symbols	$T_{\text{CCA}}$ (time for CCA)	640  $\mu s$
aBaseSlotDuration	60 symbols	$T_{\text{slot}}$ (slot duration)	320  $\mu s$
DataRate	250 kbps	$T_{\text{ta}}$ (turnaround time)	12 symbols

Network operating points determined by carrier sensing probability ${\tau }_n$ ( $n=\mathrm{1,2},\dots ,\lceil d/R\rceil$ ) and busy channel probabilities ${\alpha }_n$ and ${\beta }_n$ are derived from the non-linear expressions of (22)–(27) using a numerical fixed point method. Figures 5(a)–5(c) illustrate the characteristics of parameters ${\alpha }_{\mathrm{1,2}}$ , ${\beta }_{\mathrm{1,2}}$ and ${\tau }_{\mathrm{1,2}}$ .

Figure 5

The behavior of parameters $\alpha ,\hspace{0.17em}\beta$ , and τ ( $n=\mathrm{1,2}$ ) in multihop wireless sensor system. (a) Relations of α with node density λ based on traffic rate γ. (b) Relations of β with node density λ based on traffic rate γ. (c) Relations of τ node density λ based on traffic rate γ.

We can analyze the performance of parameters ${\alpha }_{\mathrm{1,2}}$ , ${\beta }_{\mathrm{1,2}}$ , and ${\tau }_{\mathrm{1,2}}$ separately according to 1-hop and 2-hop for 1-hop nodes and 2-hop nodes can access the channel separately and these behaviors are only related to the exact contending packets in the medium. We analyze the performance of parameters ${\alpha }_{\mathrm{1,2}}$ , ${\beta }_{\mathrm{1,2}}$ , and ${\tau }_{\mathrm{1,2}}$ relating to node density λ based on traffic rate γ, and these behaviors relating to other network parameters such as packet size L and transmission range R are not analyzed in this paper. According to Figure 5, we can see that ${\alpha }_{\mathrm{1,2}}$ and ${\beta }_{\mathrm{1,2}}$ are sensitive to traffic rate γ and node density λ, increasing with γ and λ which stand for the number of pending packets and neighbor nodes, respectively. Probability ${\alpha }_{\mathrm{1,2}}$ increases slowly when γ is less than 0.21, whereas it increases sharply when γ is more than 0.21 and less than 0.65 and then increases slowly when γ is more than 0.65. Probability ${\beta }_{\mathrm{1,2}}$ increases rapidly when γ is less than 0.55 and then reaches a stable value with the increasing of γ. For the same node density, ${\alpha }_{\mathrm{2}}$ for 2-hop is higher than ${\alpha }_{\mathrm{1}}$ for 1-hop, and ${\beta }_{\mathrm{1,2}}$ is the similar to ${\alpha }_{\mathrm{1,2}}$ as shown in Figures 5(a) and 5(b). Although the arrival rate of 1-hop is higher than that of 2-hop presented in [34], the pending packets in 2-hop are much more than those of 1-hop for much more nodes in 2-hop. Transmission probabilities ${\tau }_{\mathrm{1,2}}$ increase with the increasing of γ until arriving at the saturated peaks and then decrease with the increasing of γ after that shown in Figure 5(c). Analytical results are match well with simulation results shown in Figures 5(a)–5(c).

6.1. Throughput Validations

According to (32) in Section 5.1, system throughput is determined by packet length L, traffic arrival rate γ, node Poisson distribution density λ, transmission range R, and transmission probability $P_{tr}$ . Analytical model is convenient for determining the optimal throughput.

Throughput is sensitive to values of γ and λ at the same packet length, increasing rapidly with the increasing of γ and λ before arriving at saturated values because offered load increases largely at these cases. Shown in Figure 6(a), throughput arrives at peak value at traffic $\gamma =\mathrm{0.51}$ for Poisson density $\lambda =\mathrm{0.02}$ and $\gamma =\mathrm{0.41}$ for $\lambda =\mathrm{0.04}$ of 1-hop, respectively, while it arrives at peak value at traffic $\gamma =\mathrm{0.54}$ for $\lambda =\mathrm{0.02}$ and $\gamma =\mathrm{0.43}$ for $\lambda =\mathrm{0.04}$ of 2-hop, respectively. With the data length increasing shown in Figure 6(b), throughput increases when γ is less than 0.42 and decreases when γ is more than 0.42 for 1-hop when $L=\mathrm{10}$ , and increases when γ is less than 0.45 and decreases when γ is more than 0.45 for 1-hop. Throughput increases smoothly at $\gamma >\mathrm{0.53}$ for 1-hop and at $\gamma >\mathrm{0.44}$ for 2-hop when $L=\mathrm{5}$ .

Figure 6

Throughput as a function of traffic arrival rate γ, node density λ, packet length L, transmission range R, and transmission range. (a) Normalized throughput related to node density λ based on traffic rate γ. (b) Normalized throughput related to data length L based on traffic rate γ. (c) Normalized throughput related to transmission range R based on node density λ.

Throughput is also sensitive to transmission range as related before that the analysis results are consistent with the simulation results for larger transmission range. We emphasize that transmission range is fixed once a node model is chosen, but we can experience diverse transmission range to derive its great influence on system performance. We can see from Figure 6(c) that throughput decreases with increasing the range when λ is less than 0.06, whereas increases when λ is more than 0.06 for 1-hop. After arriving at its saturation value, throughput decreases slowly until arriving at a trimmed value. Throughput decreases rapidly with increasing hops for much more packet collisions take place among vast number of nodes. Moreover, throughput for a node in $(n-\mathrm{1})$ th hop is higher than that of a node in nth hop in that the node in $(n-\mathrm{1})$ th hop not only transmits its own pending packets but also transmits the relay packets from $(n-\mathrm{1})$ th hop. Demonstrated in Figures 6(a)–6(c), analysis results are consistent with simulation results.

6.2. Delay Validations

Delay is the most important character in our time-critical system, and we always attempt to improve the behavior of delay in order to obtain the real-time monitoring. From (34) in Section 5.2, mean delay of transmitting a packet is sensitive to γ, λ, and L. We take the hop-to-hop delay into account. This delay refers to the time in which a node in nth hop accesses the channel to transmit the packet to a node in $(n-\mathrm{1})$ th hop.

Delay increases rapidly with increasing traffic rate when traffic rate is low and increases slowly when traffic rate is high; for example, delay increases rapidly when γ is less than 0.42 for 1-hop, and the increasing rate slows down when γ is more than 0.42, shown in Figure 7(a). Data length exerts a tremendous influence on delay performance shown in Figure 7(b). In the same hop, access delay for nodes that contained long data differs little from that of short data when traffic rate is relatively low and traffic rate is relative high, while they differ appreciably from each other when traffic rate is a intermediate value. For example, access delay for $L=\mathrm{10}$ is much higher than that of $L=\mathrm{5}$ when $\mathrm{0.35}<\gamma <\mathrm{0.78}$ in 1-hop, while is sizable for two cases of data length when $\gamma <\mathrm{0.35}$ and $\gamma >\mathrm{0.78}$ as shown in Figure 7(b). Delay results deflect a lot when data length increases, and the duration to transmit longer packets in the same hop is longer than that of shorter ones. Transmission range exerts a greater impact on packet delay when the number of system nodes is relative high, and a smaller impact on fewer nodes. We find that analysis results match well simulation results.

Figure 7

Delay as a function of traffic arrival rate γ, node density λ, packet length L, transmission range R, and transmission range. (a) Delay related to node density λ based on traffic rate γ. (b) Delay related to data length L based on traffic rate γ. (c) Delay related to transmission range R based on node density λ.

6.3. Performance Comparisons

Analysis and simulation results shown above are comprehensive for applications, and we can compare the performance metrics of our mechanism with those of other hidden terminal avoiding schemes. Our HTC scheme is used for time-critical monitoring and detection application, in which minimized delay is the most important target. We can derive the separate performance of each hop for nodes in different hops contending for the channel adopt the fair parallel access mechanism. Our scheme HTC excels in contending WSN networks with hidden terminals and routing establishment for adopting the distinguished improvement of two strategies, which refer to leaving the hidden terminals out of account once the HTC pair establishment and dispensing with taking the routing overhead into account for using the parallel access scheme. Through the comprehensive comparisons, we can derive that the delay performance metric of our scheme is obviously improved over other schemes such as [9, 14], while throughput is improved over others in some cases of more node density and larger transmission range.

A simple yet efficient hidden terminal avoidance mechanism for unslotted CSMA/CA of IEEE 802.15.4, H-NAMe, is proposed by Koubâa et al. H-NAMe relies on a grouping strategy that splits each cluster of a WSN into disjoint groups of nonhidden terminals that scale to multiple clusters via a cluster grouping strategy that guarantees no interference between overlapping clusters. H-NAMe scheme is a hidden-terminal avoiding scheme but has several limitations in large-scale sensor networks as related in Section 3. That are, the permissible number of groups can not support so many pending sensors in large-scale networks. Grouping algorithm is a passive algorithm which is not suitable for the large-scale sensor networks. Grouping algorithms in [9, 13] is developed for the case of one hop networks which can consumes much energy at the case of multihop networks. So, besides consuming much energy, the passive grouping process of H-NAMe scheme consumes much time in large-scale multihop networks. We can slightly adjust network parameters and MAC parameters for H-NAMe scheme in order to compare the performance metrics with our model, which is illustrated in later simulation figures such as Figures 8–11.

Figure 8

(a) Throughput comparisons for different hops based on traffic rate when node density is relatively low $\lambda =\mathrm{0.02}$ . (b) Throughput comparisons for different hops based on traffic rate when node density is relatively high $\lambda =\mathrm{0.04}$ . The throughput behaviors of 1-hop nodes can be demonstrated using the upper lines, and those of 2-hop circle using lower lines.

Figure 9

(a) Throughput comparisons for different hops based on node density when transmission range is relatively low $R=\mathrm{20}$ . (b) Throughput comparisons for different hops based on node density when transmission range is relatively high $R=\mathrm{40}$ . The throughput behaviors of 1-hop nodes can be demonstrated using the upper lines, and those of 2-hop using lower lines.

Figure 10

(a) Delay comparisons for different hops based on traffic rate when node density is relatively low $\lambda =\mathrm{0.02}$ ; (b) Delay comparisons for different hops based on traffic rate when node density is relatively high $\lambda =\mathrm{0.04}$ . The delay behaviors of 2-hop nodes can be demonstrated using the upper lines, and those of 1-hop using lower lines.

Figure 11

(a) Delay comparisons for different hops based on node density when transmission range is relatively low $R=\mathrm{20}$ . (b) Delay comparisons for different hops based on node density for transmission range is relatively high $R=\mathrm{40}$ . The delay behaviors of 2-hop nodes can be demonstrated using the upper lines, and those of 1-hop nodes using lower lines.

The first cross-layer technique CL-DNA (cross-layer detection and allocation) to solve the hidden terminal problem for CSMA/CA of IEEE 802.15.4 is proposed by Tseng et al. CL-DNA scheme combines the PHY layer and MAC layer. The PHY layer is responsible for detecting the device addresses from the collided signals to identify the hidden terminals upon the occurrence of frame collision. In the MAC layer, the dubious hidden terminals are double-checked via hidden terminal problem address verification procedure, and the confirmed addresses of the hidden terminals are then added to a hidden terminal address list. A hidden terminal is scheduled to access the channel by exclusively allocating time slots in different subperiods according to the number of hidden terminal pairs it belongs to and the size of hidden terminal address list, to eliminate the effect of the hidden terminal problem. The hidden terminals are detected actively by CL-DNA scheme, which consumes much less energy. However, the time allocation algorithm of CL-DNA consumes much energy in two-hop or multihop scenarios. Moreover, great confusion can be introduced into the address detection procedure in multihop networks if nodes in different hop access the channel adopting the parallel mode.

We compare the behaviors of these two hidden terminal avoiding IEEE 802.15.4 schemes of [9, 14] with our HTC scheme under low traffic rates and modify the backoff counters as no limitation when increasing the backoff stages for all three schemes. The simulation parameters are presented as in the same way as our above simulations.

Node density λ plays an important role in throughput performance of all three schemes, which can be seen from Figure 8. Nodes are passively grouped into a certain group whether they have packets to be transmitted or not, leading to nodes which have no pending packets contend to the channel in a certain group. And so, throughput is brought down. Throughput behavior of Koubâa's scheme is inferior to other two schemes in case of 1-hop when $\lambda =\mathrm{0.02}$ as shown in Figure 8(a). With traffic arriving rate increasing, throughput of HTC scheme is superior to other two schemes for more valid packets access the channel successfully. Throughput increases gently with the traffic rate increasing in low node density $\lambda =\mathrm{0.02}$ , while it decreases a little after arriving at a peak value in high node density $\lambda =\mathrm{0.04}$ shown in Figures 8(a) and 8(b). Throughput behavior of Tseng's scheme is superior to other two schemes in low traffic rate such as $\gamma <\mathrm{0.486}$ for 2-hop of $\lambda =\mathrm{0.02}$ , $\gamma <\mathrm{0.324}$ for 1-hop of $\lambda =\mathrm{0.02}$ , $\gamma <\mathrm{0.297}$ for 2-hop of $\lambda =\mathrm{0.04}$ , and $\gamma <\mathrm{0.604}$ for 1-hop of $\lambda =\mathrm{0.04}$ .

Transmission range R also plays an important role in throughput performance seen in Figures 9(a) and 9(b). Throughput of Koubâa’ shows the worst performance in larger transmission range $R=\mathrm{40}$ and only has some superiority in low node density $\lambda <\mathrm{0.054}$ of 1-hop when $R=\mathrm{20}$ . Fewer nodes are involved for contending to the channel in the case of low transmission range $R=\mathrm{20}$ , so, throughput shows pretty much the same for these three schemes. Throughput of HTC scheme is superior to that of other two schemes with the transmission range increasing, which demonstrates the superiority of HTC scheme for many nodes in large-scale networks.

We find that delay metric of HTC scheme is superior to those of Koubâa's and Tseng's schemes from Figures 10(a), 10(b), 11(a), and 11(b) in three aspects. Firstly, nodes having pending packets to be transmitted can establish the HTC couple pairs. This active coupled algorithm consumes much less time without scheduling to couple each and every node in so much nodes of large-scale network. And then, all nodes regardless hops can access the channel adopting a parallel CSMA/CA scheme. Nodes in higher hop circle dispense with waiting for nodes in lower hop completing their transmissions, which consumes much time. Moreover, all nodes regardless of hops can transmit their packets in an independent mechanism without taking the point of global view, while the scheme of Koubâa's needs to coordinate the operations of nodes in a whole group at least, and the scheme of Tseng's must take all addresses in the network into consideration.

Shown in Figures 10(a) and 10(b), delay increases slowly with the traffic rate increasing for 1-hop scenarios, while it increases acutely with the traffic rate increasing for 2-hop scenarios. Transmission range plays a great important role in delay performance shown in Figures 11(a) and 11(b). For the schemes of Koubâa's and Tseng's, delay increases to some enormous values, while delay of HTC scheme increases smoothly with the node density increasing.

We can find that the delay performance is improved greatly by adopting the novel scheme of HTC, in which the contending traffic, regardless of hops, has no priority over each other. Delay of HTC is superior to those of other schemes, while throughput is superior to others for the cases of more node density and larger transmission range. In such a time-critical system, the scheme of HTC supplies the satisfactory performance.

Moreover, calculations for throughput and access delay presented an exponential increase with the number of hops, and we analyze the behaviors of 1-hop and 2-hop comprehensively as above. Standing feature of our method is that performance analyses can be scaled easily to higher hop without enormous complexity. Compared to the establishment consumption of the HTC within node T and node R, the increased part of the overall consumption is the part of the consumption for the HTC information exchange between the node in the highest hop and the node in its lower hop near to it. The computational complexity just increases a little. We extend our analyses to higher hop, deriving the characters of multihop networks. Shown in Figure 12(a), throughput decreases rapidly with increasing hops until to a small trimmed value. For instance, throughput is decreased to 0.011 from 5-hop. Delay increases sharply with increasing hops, which shows the similar behavior as the throughput illustrated in Figure 12(b).

Figure 12

Multihop performance by extending above analyses to higher hops. (a) Normalized throughput related to node density based on hops. (b) Delay related to hops based on node density.

7. Conclusions

In this paper, we have presented a slotted CSMA/CA scheme HTC scheme, for multihop IEEE 802.15.4 networks using accurate and comprehensive n semi-Markov models and one macro-Markov model. At first, two strategies are performed to improve the performance of multihop WSNs: the HTC algorithm and a parallel access scheme. Then, the comprehensive models adopting n semi-Markov chains to describe the behaviors of CSMA/CA scheme for the nodes in n hops contending to the channel and one macro-Markov chain to describe the channel behaviors are proposed to analyze and improve the performance of multihop IEEE 802.15.4 CSMA/CA scheme. And then, the accurate statistical performance metrics of throughput and delay of unsaturated, unacknowledged IEEE 802.15.4 beacon enabled networks for 1-hop and 2-hop scenarios are predicted based on these models and improved strategies, in which nodes are assumed to locate randomly uniformly over a circle plane according to Poisson distribution with a density of λ. We consequently extend our models to analyze 3-hop or even higher hop networks.

Comprehensive NS-2 simulations demonstrate that the analysis results of these models match well the simulation results, especially for larger transmission range and relative higher node density. Moreover, performance comparisons between our HTC scheme and other multihop schemes with hidden terminal avoiding are also proposed. Besides, the analysis and comparison results show that the delay behavior of this time-critical scheme HTC is improved largely relatively to other schemes, and the throughput performance is improved in some cases of more node density and larger transmission range.

In multihop wireless sensor networks, the position of the sink has significant impact on the networks behaviors which is elaborately analyzed in [45]. And the distance between the transmitter and the sink plays an important role in network performance if the propagation model is taken into account. Moreover, heterogeneous nodes or heterogeneous access schemes can be the open questions in multihop networks. In the recent future, we can also extend our analysis to these pending problems.