Abstract
This paper proposes receiver-initiated X-MAC with tree topology (TRIX-MAC), an improved energy-efficient MAC protocol based on an asynchronous duty cycling for wireless sensor networks with tree topology. TRIX-MAC improves energy efficiency through utilizing short preambles and adopting the receiver-initiated approach that minimizes sender nodes' energy consumption by enabling transmitters to predict receiver nodes' wake-up times and reduces receiver nodes' energy consumption by decreasing the number of control frames. In many sensor network applications, the data flow from source nodes to a sink forms a unidirectional tree. A property of tree topology, the parent-child relation, is also exploited to reduce the likelihood of collisions between frames sent by children nodes. We use the network simulator, ns-2, to evaluate TRIX-MAC's performance. Compared to the prior asynchronous duty cycling approaches of X-MAC, RIX-MAC, and PW-MAC, the proposed protocol shows better performance in terms of throughput, energy efficiency, and end-to-end delay.
1. Introduction
Unlike the nodes in other wireless networks such as WLAN and Bluetooth, sensor nodes in wireless sensor networks (WSNs) cannot change or charge their own batteries. Therefore, energy efficiency is a fundamental and important consideration when designing a MAC protocol for sensor nodes in WSN. To reduce energy consumption in WSN, many researches have been studied ever since. The most popular mechanism for reducing energy consumption in WSN is duty cycling. The duty cycling technique saves energy by switching sensor nodes between wake-up and sleep states [1]. Existing duty cycling energy-efficient MAC protocols can be categorized into two types: synchronous and asynchronous protocols.
In the synchronous MAC protocols such as S-MAC [2] and T-MAC [3], the wake-up duration in the duty cycle of each node is synchronized by exchanging periodical control frame such as SYNC. The additional control frames cause wasted energy usage. Also, overlapped common period for accessing medium causes collision between frames. In contrast, asynchronous MAC protocols, such as B-MAC [4], X-MAC [1], and RI-MAC [5], have higher energy efficiency than synchronous protocols. These protocols use the preamble sampling instead of additional synchronized control frames. Because of the small number of control frames and low likelihood of collision, asynchronous MAC protocols are more effective in terms of energy consumption. However, it is quite difficult to match the wake-up states between the sender and receiver nodes even though asynchronous MAC protocols are designed carefully not to waste energy.
In many applications for WSNs with multiple sensors and a sink, a data gathering tree is formed from sensor nodes to the sink and sensor nodes report to the sink only when they detect an event. As shown in Figure 1, all nodes except the sink receive frames from multiple children nodes and forward them to their parent node at a higher level, which generates the situation of multiple senders having one receiver. Therefore, traffic in the event area becomes heavy, sensor nodes may suffer from higher contention, and the collision probability of frames is getting higher as frames are delivered around sink node. The collisions of frames cause the lifetime of network shorter and the throughput of network worse. Since it is remarkably important to reduce the collision probability of frames at the MAC layer in WSNs, we devise a new MAC protocol utilizing information about the number of children and the order of children in tree topology to reduce the likelihood of frame collisions and produce a better performance.
Tree topology formation in WSNs.
In this paper, we improve the energy efficiency and performance of a receiver-initiated MAC protocol, RIX-MAC, in [6] and propose a new RIX-MAC based on tree topology (TRIX-MAC). The operation of TRIX-MAC is substantially similar to one of RIX-MACs which utilizes the receiver-initiated wake-up scheme as described in RI-MAC [5]. TRIX-MAC reduces the number of the overall control frames of the sender and receiver and it prevents the collision of frames in the situation of multiple children and a receiver. As a result, TRIX-MAC can limit energy consumption unlike previous MAC protocols, such as X-MAC, PW-MAC [7], and RIX-MAC. The proposed MAC protocol in this paper, TRIX-MAC, reduces sender's energy consumption with the smaller number of control frames by receiver-initiated wake-up scheduling and removes the possibility of frame collisions by using information of a tree structure. We present the performance evaluation of the new TRIX-MAC by the simulation in ns-2 compared with previous MAC protocols.
The rest of this paper is organized as follows. Section 2 describes related work on duty cycling, synchronous and asynchronous MAC protocols for WSN. Section 3 presents the design of the TRIX-MAC protocol, and Section 4 presents its performance evaluation by the ns-2 simulator [8]. Concluding remarks are given in Section 5.
2. Related Work
2.1. Synchronized MAC Protocol Using Random Backoff
S-MAC and T-MAC are RTS/CTS-based MAC protocols that make use of loose synchronization between nodes for duty cycling in WSNs. The protocols use three techniques to achieve low-power duty cycling: periodic sleep, virtual clustering, and adaptive listening. The nodes in the network wake up periodically, receive and transmit data, and return to sleep. At the beginning of wake-up periods, a node exchanges synchronization and schedule information with its neighbors to assure that the node and its neighbors wake up concurrently. After the synchronization information is exchanged, the node transmits or receives frames using RTS/CTS until the end of wake-up periods and the node then enters the sleep mode. The biggest difference between S-MAC and T-MAC is that T-MAC improves the performance of S-MAC by shortening wake-up periods when the channel is idle.
Aside from these protocols, many synchronous MAC protocols have been studied. Among them, DPSMAC [9] proposes a differential probability selection MAC protocol which is efficient for medium access in real-time sensor networks. Meanwhile, DT-MAC [10] employs a dynamic threshold for the buffer in sensor nodes to maximize energy efficiency regardless of the network traffic condition. LO-MAC [11] proposes a protocol employing duty cycling and multiple forwarding in order to reduce idle listening and sleep latency, respectively. Synchronous MAC protocols operate in a simple manner; however, maintaining the synchronous state of nodes in the network is not quite easy. Additional control frames in synchronous MAC protocols also cause the wasting of energy at the nodes, whereas overlapped common periods for accessing medium increase the possibility of collisions in transmitting frames.
2.2. Asynchronous MAC Protocols Using Preambles
B-MAC is a CSMA-based protocol that utilizes low-power listening and an extended preamble to achieve low-energy consumption. Nodes in the network have two periods, wake-up and sleep periods, having an independent schedule for duty cycling. If a node wishes to transmit, a data frame is preceded by a preamble that is slightly longer than the sleep period of a receiver. During a wake-up period, a node samples the medium and it remains in the wake-up state to receive data if a preamble is detected. With the preamble ending, the sender transmits a data frame to the receiver. Even though B-MAC improves energy efficiency over synchronous MAC protocols, it poses the problem of wasting transmission energy due to long preambles.
On the other hand, X-MAC, which is based on B-MAC, uses the preamble sampling mechanism to achieve low-power communication without synchronization. The key features are the short preamble sampling and the early-ACK mechanism. X-MAC transmits multiple short preambles to make receiver notice instead of a long preamble at B-MAC. If the receiver detects a short preamble during its wake-up period, it transmits an early-ACK frame to the sender before receiving the actual data frame, and the sender knows that the receiver stays in the wake-up period as it transmits data frame immediately. Consequently, X-MAC saves more energy than B-MAC due to its short preamble sampling and the early-ACK mechanism.
Besides these protocols, many asynchronous MAC protocols have been researched. WTE-MAC [12], EP-MAC [13], and BoostMAC [14] improve the end-to-end delay of X-MAC protocol through virtual tunneling procedure, strobe preamble concept, and dynamic channel polling time, respectively.
2.3. Asynchronous MAC Protocols Using Receiver-Initiated Features
RI-MAC [5] employs a receiver-initiated wake-up approach from WiseMAC [15], in which wake-up beacons generated by the receiver are used to reduce energy waste from the sender. This protocol increases channel utilization and enables more efficient collision detection. In RI-MAC, each node announces its wake-up information with a beacon, and a sender starts data transmission upon receiving a beacon from its intended receiver. However, when a sender has a frame to send, it immediately wakes up to wait for the receiver, leading to a large sender duty cycle due to its idle listening until the receiver wakes up.
Compared with RI-MAC, PW-MAC [7] achieves near-optimal duty cycle at receivers and at senders. To enable a sender to accurately predict the wake-up times of a receiver, it requires every node in PW-MAC to compute its wake-up times using its pseudorandom wake-up schedule generator and calculate the hardware-level delay, operating system delay, clock drift, and so on. Therefore, PW-MAC reduces the energy consumption of sensor nodes compared to RI-MAC by enabling sensors to predict receiver wake-up times.
In addition to these protocols, many receiver-initiated MAC protocols have been researched. EM-MAC [16] enhances PW-MAC by exploiting an exponential chase algorithm for an efficient resynchronization over the clock drift. In addition, EM-MAC spreads the traffic load to different channels to minimize the collisions among multiple senders. In [17], τ-duration CCA is utilized to mitigate the collision problem in ACK-based LPL MAC protocols, while short preamble counter is used to conserve more energy by reducing unnecessary overhearing.
The key idea of these receiver-initiated MAC protocols is highly effective and powerful approach in terms of energy consumption. However, these protocols exhibit a critical disadvantage in the case of multiple senders and a receiver. In the case of multiple senders which are ready to send data frames, collisions may occur with extremely high probability because senders wake up at the time that the receiver initiates.
2.4. MAC Protocols for WSNs with Tree Topology
For sensor networks with data flows to a sink from multiple source nodes, the data delivery paths usually generate a tree topology for data gathering. EE-MAC [18] is a synchronized protocol based on the hybrid of TDMA and FDMA, which targets the improvement of the energy efficiency and packet delivery ratio by using the priority feature of tree-based MAC scheduling. D-MAC [19] is also a synchronized protocol which uses more-to-send (MTS) control frames for faster transmission in the tree structure. Since they are synchronized protocols, every node in the network should synchronize each other.
R-BOP [20] presents a reservation-based enhancement of ZigBee beacon-only period approach, which addresses energy waste caused not only by idle listening but also by overhearing and collision on the cluster-tree structure. Based on the superframe of ZigBee, it uses modified beacon frames and a dynamic superframe structure in the clustered topology. RC-MAC [21] proposes a receiver-initiated medium access scheduling and a distributed channel assignment for spatial correlated event-driven applications on the tree structure. To mitigate bursty load in the parent, nodes' wake-up schedule for a neighboring subtree and the sequential reception of children's data are exploited. A multichannel transmission is used to avoid collisions by the simultaneous transmissions from subtrees. Although the results of RC-MAC show better performance than legacy MAC protocols, its initial scheduling and channel assignment are complicated.
3. RIX-MAC with Tree Topology (TRIX-MAC)
3.1. Overview
TRIX-MAC is a simple contention-based MAC protocol with duty cycling, which employs clear channel assessment (CCA) [22] and low-power listening (LPL) [23] for accessing channel. Every node in the network has the same operational cycle which is divided into two states: the wake-up and sleep states. The wake-up state is an active state for a node to receive or transmit data with the radio turned on, and the sleep state is used when a node saves its power by turning off the radio. The wake-up state is divided into two different periods: the Sched-wake-up (scheduled wake-up) and Synch-wake-up (synchronized wake-up) periods where the Synch-wake-up period may be activated when a node wants to transmit data frames synchronized to the receiver.
Figure 2 gives an overview of TRIX-MAC's operation. Each node periodically wakes up at its own schedule, Sched-wake-up, to check if there are any incoming short preambles intended for it. If there are no incoming short preambles after Sched-wake-up, TX-node goes to sleep. When it has data frames to send, TX-node wakes up again at Synch-wake-up which is synchronized to RX-node's wake-up. When it wakes up at Synch-wake-up, TX-node starts the transmission of a short preamble and RX-node replies with an early acknowledgement after the short preamble from TX-node. Finally, TX-node transmits the data frame after the successful exchange of a short preamble and an early acknowledgement as shown in Figure 2. For control frames, time slots are divided into two parts: even slots for early-ACKs and odd slots for short preambles. Because the slots for transmitting control frames are divided into odd and even, there is no collision between short preamble and early-ACK frames. In the rest of this section, we will describe detailed operational mechanism of the proposed protocol such as the features for collision avoidance.
Overview of TRIX-MAC operation.
3.2. Receiver-Initiated Operations of TRIX-MAC
In TRIX-MAC, all nodes have their own wake-up schedule independently as well as their temporary wake-up schedule synchronized to RX-node's wake-up, where RX-node's wake-up schedule can be obtained by the wake-up time field in early-ACK frames. Therefore, TX-node using TRIX-MAC wakes up twice in a cycle when the TX-node has data to be delivered to RX-node. In TX-node, the first wake-up occurs at its own schedule to receive data frames (Sched-wake-up) while the second wake-up transpires to transmit data to RX-node (Synch-wake-up) as shown in Figure 2.
Since TX-node has no information about RX-node's wake-up schedule at the beginning, TRIX-MAC operates just like X-MAC during the first cycle of the transmission. When TX-node has data to be transmitted to RX-node, TX-node searches a wake-up schedule of designated RX-node in the table. If it cannot find the appropriate wake-up schedule of RX-node, TX-node keeps transmitting short preambles from its own schedule as X-MAC does. Upon receiving an early acknowledgement from RX-node, TX-node starts to transmit data frames immediately, extracts the wake-up information of RX-node from the wake-up time field in the early-ACK frame, and saves information on the wake-up time table as a time gap between Sched-wake-up and Synch-wake-up.
When TX-node predicts the wake-up of RX-node, Synch-wake-up is determined by the gap between last Sched-wake-up and time gap,
Timing diagram of TRIX-MAC operation.
Since TX-node attempts to transmit on the RX-node's wake-up, receiver-initiated protocols might induce a collision problem when several nodes try to deliver data to an RX-node. To avoid preamble collisions, the parent-children relation of tree topology is exploited. In tree topology, the parent (RX-node) knows the number of children (TX-nodes) and assigns different slot-counts to children if the maximum number of children tied to a parent is fixed. An assigned slot-count for each child (TX-node) means the number of time slots to wait for the next transmission of short preamble after Synch-wake-up.
When n is the maximum number of children nodes for a parent, the value of slot-count would be
To coordinate preamble transmissions, an additional field, duration, is inserted in preamble and early-ACK frames when multiple TX-nodes try to transmit data frames at the next Sched-wake-up of RX-node. The field contains information about slot-counts required to transmit data frame for each TX-node, with which others could predict the duration time of the next data transmission. RX-node employs the duration field in early-ACK frames to coordinate transmissions of short preambles from contending multiple TX-nodes. TX-nodes reading the value of duration from another TX-node or RX-node set the network allocation vector (NAV) to defer accessing the medium and stop decrementing slot-counts. After the successful transmission of data frame, TX-nodes under the virtual carrier sensing with NAV resume decrementing slot-counts and try to transmit short preambles. In Figure 4, slot-count is set to 1 for TX1 and set to 3 for TX2. TX1 grabs the medium to transmit a short preamble in the first time slot and RX replies to the preamble with an early-ACK. TX2 receives the early-ACK from RX and set the NAV to the end of data transmission. The duration in the early-ACK frame specifies the number of time slots for TX2 has to wait during the data transmission. As data transmission is completed, TX2 counts down the residual slot-count again and transmits the preamble at the next time slot.
Virtual carrier sensing and time slot coordination with multiple transmitters.
Although TRIX-MAC employs a receiver-initiated wake-up mechanism and a coordination scheme for exchanging preamble frames and early-ACK frames, it is possible that the RX-node may fail to receive the short preamble sent by the TX-node due to temporal channel impairments. Figure 5 shows the operations of TRIX-MAC in the case that RX loses the first short preamble due to channel impairments, where slot-counts are set to 1 and 3 for TX1 and TX2, respectively. Figure 5 shows that TX1 and TX2 are hidden from each other and TX1 broadcasts a short preamble which is not delivered due to channel impairment. TX2 tries to transmit a short preamble according to its assigned slot-count since TX2 does not know the first short frame of TX1. After RX replies with an early-ACK frame, TX1 sets NAV and defers its transmission until the next chance. As TX2 finishes the data transmission, TX1 tries to get the second chance to transmit a data frame after random back-off since two or more TX-nodes could wait for the second chance.
Transmission of control frames with channel impairments.
4. Performance Evaluation
We used ns-2 (version 2.32) as a network simulator in order to evaluate the performance of TRIX-MAC. Also we show how much TRIX-MAC has improved in performance compared to our previous work by utilizing properties of the tree topology. It is assumed that each node has a single omnidirectional antenna where the radio propagation model of two-way ground reflection is employed in the field of 1000 m by 1000 m. Key parameters of nodes and networks are shown in Tables 1 and 2, respectively.
Node parameters.
Network parameters.
To evaluate the performance of our proposed protocol, we measured the throughput, the energy consumption, and the end-to-end delay of frame delivery under the tree topology with two scenarios such as uniform and random distributions. For the uniform scenario, 25 nodes are evenly located and are forming a tree topology, while 30 nodes are randomly deployed based on a tree topology in the case of random distribution. With the simulation results, we are going to show the performance and the robustness of protocols in various environments.
In WSNs, sensor nodes cooperatively monitor physical states and conditions accurately in space and time to detect the events of interest. Sensor nodes encounter spatially correlated phenomenon, once an event is detected in the sensing field. The multiple nodes around the event area might sense it and try to report data to the sink. Therefore, a synchronized burst of transmissions is observed which causes severe contentions and collisions at nodes in the event area.
Considering the temporal and spatial correlation property of sensor networks in the simulation, we exploit random correlated event (RCE) traffic to evaluate the performance of the proposed protocol [24]. To generate RCE traffic, let event area be a round region of radius R with center at
Figure 6 shows the average throughput of TRIX-MAC, RIX-MAC, X-MAX, and PW-MAC protocols, where three types of traffic are applied. One is CBR static traffic, another is Poisson-distributed traffic, and the other is RCE traffic. From the results, we observe that TRIX-MAC and RIX-MAC produce better performance than others regardless of the traffic model and distribution type. MAC protocols with receiver-initiated method show better performance than the other protocol, where our proposed protocol shows a remarkable performance at various simulation scenarios. Moreover, the average throughput of TRIX-MAC is higher than that of RIX-MAC achieving about 7.6% increase. We conjecture that improved throughput of TRIX-MAC is caused by avoiding collisions between control packets and partially preventing collisions of hidden nodes as described in Section 3.
Evaluation of average throughput.
Figure 7 shows the performance of average end-to-end delay through the simulation. X-MAC has the highest end-to-end delay among MAC protocols since continuous transmission of short preambles keeps the channel busy and prohibits other transmissions. For example, while a sender keeps transmitting short preambles continuously to finish up the delivery, there may be other senders waiting for the channel in the same range. Therefore, other senders have to try the transmission again after the next wake-up. On the other hand, PW-MAC, TRIX-MAC, and RIX-MAC have TX-nodes to sleep until corresponding to the RX-node's wake-up. TRIX-MAC and RIX-MAC have lower end-to-end delay compared to PW-MAC because data frames are colliding less and back-off time to grab the channel is less in RIX-MAC. Furthermore, TRIX-MAC shows better performance than RIX-MAC at about 16.8% in aspect of the end-to-end delay.
Evaluation of average end-to-end delay.
In Figure 8, the results of total energy consumption are shown. Since a high level of energy is consumed to transmit short preambles until RX-node wakes up, X-MAC shows the highest energy consumption. In particular, a large amount of energy is wasted due to a number of short preambles in case the time gap is large between TX-node's and RX-node's wake-ups in X-MAC. The energy consumption of PW-MAC in random topologies increases remarkably since every node in PW-MAC transmits the beacon nodes irrelative to data transmission. Therefore, nodes of PW-MAC consume more at large network systems. As a result, Figure 8 shows that our proposed protocol is effective in terms of energy consumption under the various topologies and traffics. Since energy consumption in a node is highly related to the lifetime of the network, TRIX-MAC is expected to have a remarkably longer lifetime than others such as X-MAC and PW-MAC. Since TRIX-MAC consumes about 13.1% lower energy than RIX-MAC does with respect to energy saving, the proposed protocol appears suitable for the sensor networks with the tree structure.
Evaluation of total energy consumption.
To measure the channel utilization, the amount of data frames out of the total transmitted frames that make use of the channel should be considered. We denote the overhead of control frames as the ratio of transmitted/received control frames to all transmitted/received frames (the less overhead the protocol uses, the higher the utilization it achieves).
The amount of overhead that protocols use is shown in Figure 9. X-MAC holds the channel to keep transmitting short preambles until RX-node's early-ACK frame arrives and PW-MAC makes use of the channel to broadcast receiver's beacons at every Sched-wake-up. Our proposed protocol has higher channel utilization since the number of control frames is small and the likelihood of retransmission is remarkably low. With regard to utilization, TRIX-MAC uses about 6.3% lower overhead than RIX-MAC does.
Comparison of the overheads of control frames.
5. Conclusions
This paper has presented the design and evaluation of TRIX-MAC (RIX-MAC based on tree topology), an improved energy-efficient MAC protocol for sensor networks based on asynchronous duty cycling with tree topology. Energy saving has been a research issue for wireless sensor networks since the lifetime of networks is critical. TRIX-MAC is designed to minimize energy consumption, without sacrificing latency, by using short preambles and enabling senders to predict receiver's wake-ups. Transmission collisions may occur over wireless channels, especially with bursty traffic that may be usual in a sensor network. The assignment of the time slot mechanism of TRIX-MAC also reduces the likelihood of transmission collisions in the case of multiple senders.
We conducted simulation on ns-2 simulator to evaluate the performance of TRIX-MAC compared with X-MAC and PW-MAC with uniformly and randomly distributed tree topologies. As a result, TRIX-MAC reduces the energy consumption at sender and receiver nodes and increases the lifetime of sensor networks by lower collision and unnecessary wake-ups. Simulation results also show that our proposed protocol outperforms the previous protocols in terms of end-to-end delay by avoiding collision and reducing overhead.
Footnotes
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.