Advanced
An Exposed-Terminal-Eliminated Dual-Channel MAC Protocol for Exploiting Concurrent Transmissions in Multihop Wireless Networks
An Exposed-Terminal-Eliminated Dual-Channel MAC Protocol for Exploiting Concurrent Transmissions in Multihop Wireless Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Mar, 8(3): 778-798
Copyright © 2014, Korean Society For Internet Information
  • Received : December 26, 2012
  • Accepted : March 05, 2014
  • Published : March 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Kai Liu
National Key Laboratory of CNS/ATM Beijing 100191 - China
Yupeng Zhang
National Key Laboratory of CNS/ATM Beijing 100191 - China
Feng Liu
National Key Laboratory of CNS/ATM Beijing 100191 - China

Abstract
This paper proposes a novel exposed-terminal-eliminated medium access control (ETE-MAC) protocol by combining channel reservation, collision avoidance and concurrent transmissions to improve multi-access performance of the multihop wireless networks. Based on the proposed slot scheduling scheme, each node senses the control channel (CCH) or the data channel (DCH) to accurately determine whether it can send or receive the corresponding packets without collisions. Slot reservation on the CCH can be simultaneously executed with data packet transmissions on the DCH. Therefore, it resolves the hidden-terminal type and the exposed-terminal type problems efficiently, and obtains more spatial reuse of channel resources. Concurrent packet transmissions without extra network overheads are maximized. An analytical model combining Markov model and M/G/1 queuing theory is proposed to analyze its performance. The performance comparison between analysis and simulation shows that the analytical model is highly accurate. Finally, simulation results show that, the proposed protocol obviously outperforms the link-directionality-based dual-channel MAC protocol (DCP) and WiFlex in terms of the network throughput and the average packet delay.
Keywords
1. Introduction
I n wireless networks, medium access protocol (MAC) protocols are mainly used to handle the dynamic, efficient and fair medium access and channel sharing to exchange information for all nodes according to application scenarios, network features and quality-of-service (QoS) requirements of various traffics [1] . Due to the features of infrastructureless multihop network architecture, wireless broadcasting and bursty traffic, most of MAC protocols usually adopt random access mechanism with reservation, such as request-to-send/clear-to-send (RTS/CTS) handshake-like mechanism. However, in the single-channel MAC protocols, the control and data packet transmissions with different directions (such as the RTS or data packet transmissions from a sender to its recipient versus the CTS or acknowledgment (ACK) packet transmissions from a recipient to its sender) between any adjacent communication node pairs on the same channel may cause serious packet collisions, resulting in lower channel utilization, larger packet delays and higher packet dropping rates. Recently, to better solve this problem, multichannel MAC protocols have attracted considerable interest for their higher overall network performance than that of single-channel MAC protocols [2 - 8] . The main reason of their advantages lies in that multichannel MAC protocols can allow adjacent communication node pairs to concurrently exchange control or data packets on different channels without collisions and thus make spatial reuse of channel resources more sufficient.
However, on the one hand, they incur the multichannel hidden-terminal type problem [2 - 6] , which greatly increases the collision probability between the ongoing packet transmissions and the incoming packet transmissions of hidden sending terminals or exposed receiving terminals due to the lack of timely channel usage information. On the other hand, they incur the multichannel exposed-terminal type problem [7] [9] , which causes channel wastage by restricting exposed sending terminals or hidden receiving terminals from reusing available channels. In essence, the multichannel hidden-terminal type and exposed-terminal type problems are caused by the possible collisions between the packet transmissions with different directions on the same channel in the case of multihop network architecture and wireless broadcasting. This occurs, for example, between the transmissions of RTS or data packets from a sender to its recipient and those of CTS or acknowledgment (ACK) packets from a recipient to its sender in a RTS/CTS handshake-like MAC protocol. If there are packet collisions between them, the problem is called the multichannel hidden-terminal type problem. If a collision avoidance mechanism is adopted in the case of no packet collisions, this results in the multichannel exposed-terminal type problem. In addition, multichannel coordination in multichannel MAC protocols needs more complex hardware and protocol design. In most cases, compared to the single-channel MAC protocols, they needs more network overheads (including communicating, computing and storing overheads) to allocate channels efficiently. Therefore, their multi-access performance averaged over the number of channels is generally lower than that of the single-channel MAC protocols [2] .
To obtain more spatial reuse of channel resources without consuming extra network overheads, an exposed-terminal-eliminated MAC (ETE-MAC) protocol is presented, which completely eliminates the exposed-terminal type problem and efficiently mitigates the impact of the hidden-terminal type problem. Based on the Markov theory [10 - 12] as well as the M/G/1 queuing theory [13 - 15] widely employed for analyzing the performance of MAC protocols, an analytical model for the ETE-MAC protocol is proposed, and based on this the performance of the ETE-MAC protocol is analyzed.
The contributions of this paper can be summarized as follows:
  • ‧ Propose a dual-channel MAC protocol with a slot scheduling and default channel/slot selection scheme to completely eliminate the exposed-terminal type problem and support concurrent, conflict-free packet transmissions between a sender and its exposed-terminal type nodes.
  • ‧ Design an instantaneous channel sensing mechanism to greatly alleviate the transmission interference caused by useless RTS transmission and the packet collisions caused by the hidden-terminal type nodes without using extra network overheads.
  • ‧ Incorporate a reservation backoff mechanism to greatly reduce the impact of useless RTS transmission on limiting the channel reservation and data packet transmissions of the neighboring nodes.
  • ‧ Develop an analytical model to analyze the performance of the proposed protocol by considering the impacts of hidden terminals and exposed terminals.
The remainder of the paper is organized as follows. Related work is discussed in Section 2. Section 3 describes the ETE-MAC protocol and Section 4 analyzes its performance by using the proposed analytical model, which is validated via simulations. Section 5 gives the performance comparison of the ETE-MAC protocol with the WiFlex [5] and the link-directionality-based dual-channel MAC protocol (DCP) [16] . Finally, we conclude the paper in Section 6.
2. Related Work
To resolve the multichannel hidden-terminal type and exposed-terminal type problems for the multichannel MAC protocols, four general approaches have been employed as follows:
(1) A dedicated control channel (CCH) is specially used for control packet transmissions avoiding the transmission collisions between the control packets and data packets [7] [9] [17] . In [7] , two CCHs for the independent transmissions of RTS/CTS handshakes and ACK packets are adopted to eliminate the impact of CTS and ACK packet transmissions on data packet transmissions. In [9] , one CCH is employed to transmit RTS/CTS packets, and the recipient sends a busy tone on a busy channel to decrease the impact of hidden-terminals and extends the busy tone to indicate a negative ACK (NACK) if it does not correctly receive the data packet from its sender. In a dual channel MAC protocol [17] , the transmissions of the delay-to-send (DTS) packets on the CCH are used to indicate the data channel (DCH) busy for all possible hidden terminals using two network interface cards (NICs).
(2) Packet collisions can be avoided according to the channel usage information obtained by indicating packet transmissions, overhearing the channel and recording the channel status. This can be achieved by three methods. Firstly, a busy tone is adopted to indicate the channel status and the data packet transmission [9] [18 - 20] . Secondly, multiple half-duplex transceivers or multiple NICs are used to simultaneously overhear and transmit packets on multiple channels and sense the channel usage in real-time [2] [17] [21] . Thirdly, based on the channel state tables constructed by the overhearing of RTS/CTS packets, unused channels can be selected to use or active collision avoidance can be employed [2 - 4] [7] [16] [22] . The former two methods need extra hardwares. The last one generally needs to revise RTS and CTS packets to designate the selected DCHs [2 - 5] [7] [22] . In addition, constructing and updating the channel state table consumes a lot of network overheads.
(3) The channel hopping of each node is arranged according to a fixed channel hopping scheme [6] [23] or a pseudo-random channel hopping scheme [8] [24 - 26] . In this approach, each sender needs to switch to the reception channel of its recipient for transmitting its reservation packet and thus this may easily incur reservation collisions due to the simultaneous reservation from multiple senders to the same recipient.
(4) Packet transmission direction between the sender and its recipient is considered for channel selection. In the DCP protocol [16] , according to a simultaneous transmission table constructed by overhearing RTS and CTS packets, each sender uses one of two channels to transmit RTS and data packets, and its recipient uses another channel to transmit CTS and ACK packets. Based on this, the DCP with a signal-to-interference ratio (SIR) comparison algorithm (DCPwSCA) [27] uses SIR comparison to distinguish the channel selection among communication node pairs within the virtual carrier-sensing range but outside the transmission range of data packets in order to obtain more concurrent transmission opportunities. However, selecting different channel pairs between different communication node pairs lead to a greater likelihood of a node missing a reservation invitation for it, causing severe channel wastage. Actually, this problem can only be solved by equipping each node with two half-duplex transceivers or NICs.
For the applications of employing a half-duplex transceiver at each node, we propose the slotted dual-channel ETE-MAC protocol to efficiently resolve multichannel hidden-terminal type and exposed-terminal type problems in multihop wireless networks without using the busy tone scheme and the channel state tables.
3. ETE-MAC Protocol
- 3.1 Basic Assumptions
In a multihop wireless network, each node exchanges RTS, CTS and ACK packets on one CCH and data packets on another DCH using a half-duplex transceiver. If there is no packet to send on the CCH or DCH, each node tunes its transceiver to the CCH and keeps sensing. For simplicity, we assume that the packet transmission range of each node is the same as its virtual carrier-sensing range (VCSRange). In addition, global or local time synchronization is assumed in the network, possibly through the application of the satellite navigation systems, such as the global positioning system (GPS) [28] .
- 3.2 Timing Structure
As shown in Fig. 1 , in the ETE-MAC protocol, the channel is divided into one CCH and one DCH. The CCH is further divided into reservation slots (RSs) and the DCH into data packet transmission slots (TSs). In a RS, each node exchanges RTS/CTS packets to reserve the predefined TS on the DCH. Once achieved, it tunes to the DCH to send its data packet in the TS and receive the corresponding ACK packet on the CCH at the beginning of next RS just after the TS. Each RS includes N CMS contention minislots (CMSs) of length T CMS , the transmission times of RTS, CTS and ACK packets and three short interframe spaces (SIFS). SIFS includes the signal round-trip propagation time, transceiver processing time, transmitting-to-receiving turnaround time and other guard time. We assume that the length of a TS (i.e. T TS ) is N RS times that of an RS (i.e. T RS ), i.e.
PPT Slide
Lager Image
where L RTS , L CTS , L DATA and L ACK represent the lengths of the RTS, CTS, data and ACK packets, respectively, and R CCH and R DCH represent the data rates of CCH and DCH, respectively.
PPT Slide
Lager Image
Timing structure of the ETE-MAC protocol
- 3.3 Protocol Description
The entire transmission process of a data packet in the ETE-MAC protocol includes three steps, i.e. RS selection, channel reservation, and data packet transmission. Each sender firstly selects a RS without transmission interference for channel reservation based on the results of sensing N RS -1 RSs. If it does not need to backoff due to the transmission interference, it contends to reserve the DCH in its selected RS by sending an RTS packet. If successful, it completes the data packet transmission on the DCH and the corresponding confirmation on the CCH with its recipient.
- (1) RS selection
Each node determines in which RS on the CCH it initiates its reservation if it has data packets to send. For the first transmission of a newly-generated data packet, a sender tries to send its RTS packet in the N RS th RS after it generates the packet or successfully completes the transmission of last data packet. For reservation retry of a data packet, the sender backoffs one or more TS after the reservation failure to initiate its retry attempt.
Before the selected RS, it senses N RS -1 RSs in order to ensure that its recipient is not sending or receiving a data packet during its selected RS, and there is no transmission interference with other already-existed data packet transmissions during its incoming data packet transmission. If its recipient does not send an RTS or CTS packet and it does not receive any CTS packets during the previous N RS -1 RSs, it begins its reservation process in the selected RS immediately. Otherwise, it backoffs N RS -1 RSs after the interfered RS before it retries its reservation.
For example, for the network topology shown in Fig. 2 , a sender S 1 is transmitting its data packet to its recipient D 1 on the DCH and another sender S 2 is one hop away from D 1 . As shown in Fig. 3 , if the sender S 2 successfully reserves the DCH on the CCH, its data packet transmission will collide with that of the sender S 1 at D 1 . Therefore, the sender S 2 needs to backoff for collision avoidance. If the sender S 2 overhears that there are n RS RSs between its preselected RS and the RS of RTS/CTS handshakes of the sender S 1 and its recipient D 1 , it needs to backoff N RS - n RS RSs to begin its channel reservation.
PPT Slide
Lager Image
Typical network topology with transmission collisions
PPT Slide
Lager Image
RS selection approach for collision avoidance
- (2) Channel reservation
Channel reservation process includes two steps, i.e. CMS selection and RTS/CTS handshaking. As shown in Fig. 4 , in the selected RS, the sender randomly selects one CMS from all N CMS CMSs to begin its RTS transmission. Before the CMS, it senses the former CMSs. If there is no RTS or CTS packet received during the CMSs, it can send its RTS packet starting from its selected CMS. Otherwise, if its data packet transmission does not collide with that of the sensed RTS/CTS reservation (i.e., the case of exposed sending terminal and hidden receiving terminal) and there is enough time for it to exchange RTS/CTS packets, it backoffs to the end of the sensed RTS/CTS transmission and randomly selects one of the rest CMSs to begin to send its RTS packet. Otherwise, it backoffs to the next RS to make a channel reservation. In Fig. 4 , the neighboring sender S 2 of the sender S 1 backoffs to avoid reservation collisions after its reception of RTS packet from S 1 , and the sender S 3 that is two hops away from the sender S 1 backoffs after its reception of the corresponding CTS packet.
PPT Slide
Lager Image
Channel reservation process
On successfully receiving the RTS packet, the recipient immediately senses the DCH. If the DCH is idle, it replies with a CTS packet on the CCH and turns to the DCH to receive upcoming data packet in the corresponding TS. Otherwise, it replies nothing.
- (3) Data packet transmission
If the sender receives the CTS packet correctly, it can send its data packet in the corresponding TS of the DCH without collisions and its recipient will confirm the successful data packet reception by replying with an ACK packet at the beginning of next RS. If fails, it needs to backoff one TS to initiate another transmission attempt.
- 3.4 Solutions to Exposed-Terminal Type and Hidden-Terminal Type Problems
Exposed-terminal type and hidden-terminal type problems are the main factors that limit the improvement in the multi-access performance of multihop wireless networks. As shown in Fig. 5 , it is assumed that a sender A is initiating its data packet transmission attempt to its recipient B. In the traditional MAC protocols, node C or node D cannot communicate with other nodes in order to avoid possible packet collisions because of the hidden-terminal type and exposed-terminal type problems. By using different channels for transmitting control packets and data packets, adopting slot scheduling between RSs and TSs, and sensing the CCH or DCH to determine to backoff or transmit packets, the ETE-MAC protocol can resolve the problems.
PPT Slide
Lager Image
Exposed-terminal and hidden-terminal type problems and their solutions
- (1) Classification of hidden-terminal type and exposed-terminal type problems
In Fig. 5 , referring to the data packet transmission attempt from the sender A to its recipient B, the shadow area is the receiving-limited area. In that area, the data packet transmission of the sender A can result in the problem that its neighboring node C (i.e. the exposed receiving terminal at this moment) cannot correctly receive data packet on the same channel. The sender C in the receiving-limited area, called the exposed sending terminal, can transmit its data packet to its recipient E that is two hops away from the sender A while the node A is transmitting. If they make successful RTS/CTS handshakes and the data packet transmission of the sender C cannot cause the reception failure of ACK packet from the recipient B to the sender A, both their data packets can be successfully transmitted.
As shown in Fig. 5 , referring to the data packet transmission attempt from the sender A to its recipient B, in the sending-limited area, the data packet transmission of the sender D (i.e. the hidden sending terminal) at this moment can result in the problem that its neighboring node B cannot correctly receive the data packet from the sender A on the same channel. The recipient D in the sending-limited area, called the hidden receiving terminal, can receive the data packet from its sender F that is two hops away from the recipient B without packet collisions. After their successful RTS/CTS handshakes, if the ACK packet transmission of the recipient B to its sender A does not cause the reception failure of the data packet from F to D, both data packets can be successfully transmitted.
Based on the above cases, the exposed-terminal type problem includes both cases from the exposed sending terminals and the hidden receiving terminals. The hidden-terminal type problem includes those from the hidden sending terminals (i.e. the sending-limited nodes) and the exposed receiving terminals (i.e. the receiving-limited nodes).
- (2) Solution to the exposed-terminal type problem
According to the ETE-MAC protocol, as shown in Fig. 5 (a), if the exposed sending terminal C overhears the RTS packet of the sender A and then postpones its RTS transmission for its recipient E to the end of CTS transmission from the recipient B to its sender A or to the next RS, these two communication node pairs can concurrently transmit the data packets and the ACK packets without collisions. If the exposed sending terminal C and the sender A simultaneously transmit their RTS packets, they can correctly receive their corresponding CTS packets on the CCH, and then transmit their data packets on the DCH and receive their ACK packets on the CCH without packet collisions.
For the hidden receiving terminal D, if the RTS transmission from its sender F and the CTS transmission from the recipient B to its sender A do not collide at the terminal, and it can correctly receive the RTS packet, both their data packet transmissions succeed.
As mentioned above, the ETE-MAC protocol employs different channels to transmit control packets and data packets and adopts slot scheduling between RSs and TSs to avoid the transmission interference among packet transmissions with different direction and eliminate the impact of CTS and ACK transmission on the data packet transmission. Therefore, it can allow the concurrent packet transmissions among the neighboring node pairs and completely eliminate the above exposed-terminal type problem.
- (3) Solution to the hidden-terminal type problem
As shown in Fig. 5 (b), according to the ETE-MAC protocol, a sender senses N RS -1 RSs before its channel reservation and if there are no data packet transmission collisions, it begins its RTS transmission attempt. Otherwise, it postpones its RTS transmission to the associated RS. In the case that the hidden sending terminal D and the sender A contend to transmit their RTS packets in the same RS, if it transmits its RTS packet before the CTS transmission from the recipient B to its sender A, the data packet transmission from the sender A to the recipient B fails and the node F that is two hops away from the sender A can correctly receive both the RTS packet and data packet of the hidden sending terminal D. If the hidden sending terminal D receives the CTS packet of the recipient B for the sender A before its RTS transmission, it cancels its predefined RTS transmission to avoid the incoming data packet collisions at the recipient B. Therefore, the ETE-MAC protocol can greatly decrease the probability that the data packet transmissions of the hidden sending terminals cause a reception failure of the data packets from the sender to the recipient.
On receiving the RTS packet, the corresponding recipient senses the DCH to determine whether there is an ongoing data packet transmission on the DCH. If there does not exist the ongoing data packet transmission, it replies with a CTS packet. Otherwise, it indicates that the corresponding recipient is an exposed receiving terminal and located in the receiving-limited area. Thus it does not reply with a CTS packet, which avoids the transmission collisions of the data packets of the sender A and E at the exposed receiving terminal C.
As mentioned above, the ETE-MAC protocol always let the hidden-terminal type nodes (i.e. the hidden sending terminals and the exposed receiving terminals) backoff for the already-existed data packet transmission attempts in order to avoid the failures of the ongoing data packet transmission or their incoming data packet transmission. Therefore, it can greatly reduce the interference range of useless transmissions and improve spatial reuse efficiency.
Compared to other MAC protocols, the ETE-MAC protocol exploits better multi-access performance from three aspects. Firstly, it takes full advantages of the RS and CMS backoff mechanisms to greatly reduce the contention interference between different communication node pairs and only allow a very few senders with collisions to make simultaneous channel reservation. Therefore, the impact of useless RTS transmissions on limiting the channel reservation and data packet transmissions of neighboring nodes is greatly reduced. Secondly, by adopting the proposed slot scheduling scheme, it supports concurrent conflict-free data packet transmissions of the exposed-terminal type nodes (i.e. the hidden receiving terminals and the exposed sending terminals) with the corresponding sender, and increases the chances of concurrent data packet transmissions. Thirdly, it greatly alleviates the transmission interference caused by useless RTS transmission and the packet collisions caused by the hidden-terminal type nodes (i.e. hidden sending terminals and exposed receiving terminals) by adopting the instantaneous channel sensing method, i.e. each sender senses NRS-1 RSs before its RTS transmission attempt and its corresponding recipient senses the DCH to decide whether to reply with a CTS packet after receiving the RTS packet.
4. Performance Analysis
In this section, we present an analytical model to analyze the throughput and average packet delay of the ETE-MAC protocol. We first model a Markov chain to describe and analyze the behavior of nodes taking full account of the interaction between the nodes in multihop wireless networks. Then we model each node as an M/G/1 queue and apply the probability generating functions (PGF) to describe the distribution of the service time of a data packet. The average packet delay can be obtained by the Pollaczek-Khinchin mean value formula for the M/G/1 queues. In the following analysis, we assume that N nodes with the packet transmission range r are uniformly distributed in a circular area with radius R . Therefore, the average number of nodes within one hop is
PPT Slide
Lager Image
. We assume that the data packets of each node are generated according to Poisson distribution with the arrival rate λ and transmitted to one of its neighboring nodes with the same probability. Therefore, the probability that each node sends its data packets approximately equals to the probability that it receives the RTS packets and replies with the CTS packets.
- 4.1 Node Behavior Model
According to the ETE-MAC protocol, each node randomly chooses a backoff window k from [0, N CMS -1] to reserve the channel. The associated counter begins to count at the beginning of RS and decreases from k to zero. It takes T CMS interval for the counter to decrease by one. Each node keeps sensing the CCH during counting. Once sensing RTS packet transmissions from other nodes, its channel reservation is failure, and it will retry in the next RS if their data packet transmissions cannot interfere with each other. Once the counter value reaches zero, the node starts to send its RTS packet to reserve channel.
We use a stochastic process b (t) to represent the backoff time counter for a given node. It can be modeled with the discrete-time Markov chain shown in Fig. 6 . For k = 1, 2, ..., N CMS -1 and i =0, 1, ··· , N CMS -1, the transition probabilities are
PPT Slide
Lager Image
PPT Slide
Lager Image
PPT Slide
Lager Image
where p is the probability that a node fails to reserve channel due to sensing the RTS transmissions of other nodes.
PPT Slide
Lager Image
Node behavior model
Let b k be the stationary distribution of this Markov chain. Owing to the Markov chain regularities, we have
PPT Slide
Lager Image
Making use of the fact that
PPT Slide
Lager Image
the probability that a node sends its RTS packet successfully can be obtained as follows
PPT Slide
Lager Image
p can be expressed as
PPT Slide
Lager Image
where p 0 represents the probability that a node has no data packets to send, p HST is the probability that a node (i.e., a hidden sending terminal) cannot transmit data packets in order to avoid packet collisions with the data packets that is being received by its neighboring nodes, (1- p 0 )(1- pHST ) τ represents the probability that a node with a data packet to send transmits its RTS packet successfully to reserve the channel without subsequent data packet collisions, and (1-(1- p 0 )(1- pHST ) τ ) n-1 indicates the probability that all the neighboring nodes of a node do not send RTS packets successfully.
p HST also represents the probability that at least one neighboring node of a node is receiving data packets during the last N RS -1 RSs, and can be expressed as
PPT Slide
Lager Image
where p ERT is the probability that a node cannot receive data packets correctly because its neighboring nodes is transmitting their data packets, and can be expressed as
PPT Slide
Lager Image
From Eq. (8) and (9), it is obvious that PHST = PERT .
- 4.2 Packet Service Time and Average Packet Delay
Each node has a transmission queue for its data packets. Packet service time is defined as the interval from the time that a data packet arrives at the head of the queue to the time that an ACK packet for this data packet is received.
When a data packet arrives at the queue head of a node, the node may be limited to send its related RTS packet because its neighboring nodes are receiving data packets. The PGF of the backoff time because the node is limited to send the related RTS packet can be described as follows
PPT Slide
Lager Image
where pHST ( NRS -1) TRS /2 represents the average backoff time for its attempt to reserve the channel due to the ongoing data packet reception of its neighboring nodes.
The probability that a node fails to reserve the channel is
PPT Slide
Lager Image
It means that the node either fails to send its RTS packet or sends its RTS packet successfully but its recipient cannot reply with a related CTS packet due to the ongoing data packet transmissions of its neighboring nodes.
The number of access collisions N f has the following probability mass function (PMF)
PPT Slide
Lager Image
The backoff time that the node reserves the channel for m times is
PPT Slide
Lager Image
Let G B be the PGF of the total backoff time. From Eq. (12) and (13), we have
PPT Slide
Lager Image
The PGF of the transmission time of a data packet is
PPT Slide
Lager Image
Aggregating the G F , G B and G T , the distribution of packet service time can be expressed by the following PGF
PPT Slide
Lager Image
Therefore, the mean and mean square value of the packet service time is given as follows
PPT Slide
Lager Image
PPT Slide
Lager Image
According to the queuing theory, the service rate μ and service strength ρ can be obtained by the definition
PPT Slide
Lager Image
PPT Slide
Lager Image
Based on the M/G/1/∞ queue, we can calculate p 0 through
PPT Slide
Lager Image
By the Pollaczek-Khinchin mean value formula for M/G/1/∞ queue, the average packet delay including average packet service time and queuing delay can be calculated as
PPT Slide
Lager Image
- 4.3 Throughput Analysis
In multihop wireless networks, the total network throughput is affected by the network size and the average number of hops. Therefore, we take the one-hop throughput as the performance metrics, considering the impacts of hidden terminals and exposed terminals around the nodes within one-hop transmission range. The one-hop throughput is defined as the ratio of the time on the channel to be used to successfully transmit data packets for all the nodes within one-hop transmission range to the total time by considering the impacts of their hidden terminals and exposed terminals within two-hop transmission range.
Let p t be the probability that there is at least one node to make channel reservation in the considered RS, which can be expressed as
PPT Slide
Lager Image
On the condition that at least one node sends its RTS packet, the probability of successful channel reservation is
PPT Slide
Lager Image
Let T p be the average time between two consecutive transmissions, which is obtained considering that, with probability 1- p t there is no transmission, with probability p t p s there is a successful transmission, and with probability p t (1- p s ) there is a collision, i.e.,
PPT Slide
Lager Image
Thus, the one-hop throughput is
PPT Slide
Lager Image
where E [ P ] represents the average transmission time of data packets. In the ETE-MAC protocol, we assume that all data packets have the same fixed size, i.e.
PPT Slide
Lager Image
With the increase of λ , each node reaches saturation and always has packets to send, i.e. p 0 =0. At this time, the corresponding throughput is defined as one-hop saturation throughput and can be expressed as
PPT Slide
Lager Image
where p t-sat , p s-sat and T p-sat represent p t , p s and T p under the saturation situation respectively, which can be obtained by substituting p 0 =0 into Eq. (6), (7), (8), (9), (23), (24) and (25).
- 4.4 Model Validation
In this section, we use MATLAB to obtain the numerical results of the above analysis and validate them by C++ simulation results. Table 1 gives the default parameter settings used in both the numerical analysis and the simulation.
Parameter settings
PPT Slide
Lager Image
Parameter settings
Fig. 7 shows the one-hop saturation throughput of the ETE-MAC protocol with the variation of L DATA . It is obvious that the analytical results nearly coincide with the simulation results. With the same N , the larger data packet is, the higher one-hop saturation throughput is. This is because the increase of data packet length actually improves the data rate of data packet transmissions under the same network overheads, which means that nodes can transmit more data bits using the same channel resources.
PPT Slide
Lager Image
One-hop saturation throughput under different LDATA
Fig. 8 and Fig. 9 show the average packet delay of the ETE-MAC protocol under unsaturated network environment with the variation of N and N RS , respectively. In Fig. 8 , the average packet delay obvious increases with N increasing. This is because the probability of collisions between the nodes becomes larger with the increase of the number of neighboring nodes, which makes the packet service time longer and then leads to the increase of average packet delay. In Fig. 9 , with the increase of N RS , average packet delay increases dramatically. Two reasons lead to this phenomenon. One is that the increase of N RS results in the increase of the transmission time of a data packet and then the larger probability of transmission interference among the neighboring nodes. Another reason is that with the same arrival rate, longer L DATA means higher network load and longer packet service time of a data packet.
PPT Slide
Lager Image
Average packet delay under different N
PPT Slide
Lager Image
Average packet delay under different NRS
Fig. 7 , Fig. 8 and Fig. 9 show that the simulation results are generally in reasonably good agreement with the analytical results, which validates the accuracy of the proposed analytical model. The reason for their differences is that in the analytical results, failure access nodes can have unlimited times to retry the channel reservation, whereas in the simulation, a data packet is dropped when its packet delay exceeds a predefined threshold (i.e., 500 s in this paper).
5. Performance Comparison
In this section, we compared the ETE-MAC protocol with the WiFlex [5] and the DCP protocol [16] through C++ simulation. The default network parameters are shown in Table 1 . As mentioned in Section 4, we assume that N nodes with the packet transmission range r are uniformly distributed in a circular area with radius R and the data packets of each node are generated according to Poisson distribution with the arrival rate λ . For a fair comparison, we assume that all the protocols use the same R b and L DATA , and R b =11 Mb/s. In WiFlex, the durations of the observation, review and access phases are the same and are equal to ( L DATA + L ACK )/ R DCH +2SIFS. It includes one common CCH and three DCHs in the simulation. To fully reflect the MAC performance of the protocols, we only take into consideration the transmission failures caused by packet collisions from the viewpoint of MAC layer, rather than by channel errors from the viewpoint of the PHY layer. And we assume that, if two nodes are within the packet transmission range, they can correctly receive the packet from each other. It is noted that the same node density that is determined by N, R and r results in the same simulation results.
Fig. 10 and Fig. 11 show the network throughputs and average packet delays of the ETE-MAC, WiFlex and DCP protocols under different L DATA , respectively. Herein, the network throughput is defined as the ratio of the time on the channel to be used to successfully transmit data packets for all the nodes in the network to the total time, and the average packet delay is defined as the mean time interval for a data packet from the time of its generation to the time of its successful reception by its recipient. The figures show that the ETE-MAC protocol can generally achieve higher network throughput and lower average packet delay than the WiFlex and DCP protocols with the same L DATA . This can be explained as follows: In WiFlex, long observation and review phases on the CCH lead to more severe CCH bottleneck problems and more wastage of DCH, and the exposed-terminal type problem is not solved due to the adoption of carrier sense multiple access (CSMA) without explicit backoff on the CCH and the transmissions of data and ACK packets on the same DCH. In the DCP protocol, control packets are exchanged on two channels for different communication node pairs, which may incur the problem that a recipient with a half-duplex transceiver misses the RTS packet from its sender, and the useless RTS transmissions can further limit the channel reservation and data packet transmissions of their neighboring nodes. The ETE-MAC protocol solved these problems by exchanging the control packets on the CCH and letting nodes backoff based on the instantaneous reception/sensing results of CTS/data packets from their neighboring nodes. In addition, it does not take the reception of RTS packets as the backoff basis of its packet transmissions, and only takes the reception of CTS and data packets as the backoff basis, which greatly reduces the impact of ineffective RTS transmissions on restricting the neighboring nodes from channel reservation and data packet transmissions, and improves the channel utilization. Under the same packet arrival rate, their network throughput and average packet delay increase with the increase of L DATA . This is because with larger L DATA each node can send more data information bits in the presence of each successful channel reservation, and meanwhile the larger L DATA means higher network traffic load and longer service time for each data packet, which leads to higher average packet delay.
PPT Slide
Lager Image
Network throughput under different LDATA
PPT Slide
Lager Image
Average packet delay under different LDATA
Fig. 12 and Fig. 13 show the network throughputs and average packet delays of the ETE-MAC, WiFlex and DCP protocols under different VCSRange. Here, N RS =2, N CMS =16, and VCSRange=20, 30, 40 and 60 m means that VCSRange is equal to r , 1.5 r , 2 r and 3 r , respectively.
PPT Slide
Lager Image
Network throughput under different VCSRange
PPT Slide
Lager Image
Average packet delay under different VCSRange
From Fig. 12 we can see that with the increase of VCSRange, network throughput decreases and when VCSRange=20 m, it achieves the maximum value. This is because the increase of VCSRange enhances the mutual transmission interference among nodes in the network and causes more packet backoff. In the ETE-MAC protocol, the impact of VCSRange is limited within the same RS, i.e., after sensing more reservation transmissions within an RS, each sender backoffs to the next RS to decide whether to initiate its channel reservation. For the corresponding transmissions within the VCSRange but out of packet transmission range, the proposed protocol can still make a decision to reserve the channel in the current RS or backoff to the next RS. That is to say, its solutions to the hidden-terminal type and exposed-terminal type problems are still applicable to the case that the VCSRange is lager than r . Whereas, besides the reason mentioned before, the carrier-sensing mechanism adopted by WiFlex and DCP cannot efficiently resolve these problems. Therefore, when VCSRange is 20, 30, 40 and 60 m, the proposed protocol achieves throughput gains of 186.3%, 111.7%, 114.6% and 101.1% than the DCP protocol, and 26.72%, 34.23%, 34.16% and 30.49% than WiFlex, respectively. Fig. 13 shows that the average packet delay increases with the increase in VCSRange. This is because that the probability that each node senses the channel idle becomes smaller, and thus the backoff time for each data packet transmission increase dramatically, resulting in longer packet service time and queuing delay.
6. Conclusion
In this paper, we propose the slotted dual-channel ETE-MAC protocol to exploit the maximum multichannel multi-access performance in multihop wireless networks. In the protocol, each node takes full advantages of one half-duplex transceiver to exchange the RTS/CTS packets on the CCH based on the RS and CMS backoff mechanisms, and complete the corresponding data packet transmissions on the DCH without collisions. Meanwhile, by the appropriate slot scheduling, it allows the hidden receiving terminals and the exposed sending terminals to complete simultaneous conflict-free data packet transmissions with their corresponding sender. It also increases the probability of concurrent data packet transmissions, which greatly improves channel access and utilization efficiency. It is compatible with the legacy IEEE 802.11 DCF protocol without the need of a channel state table or a modified RTS and CTS frame format. Even so, it avoids setting up and updating the network allocation vector (NAV) for transmission backoffs, or employing extra channels and hardware devices, which greatly reduces the overheads, implementation cost and complexity. Simulation results show that compared with the WiFlex and DCP protocols, the proposed protocol can achieve better network performance. In the future, we plan to consider the impact of channel model on the MAC performance from the system level aspect and investigate improved multichannel MAC protocols based on the channel model. Furthermore, we will investigate and analyze the optimal parameters, such as N RS and N CMS , for different network applications, and embed an efficient contention resolution scheme into the proposed protocol in order to further improve its network performance.
BIO
Kai Liu received his B.S., M.S. and Ph.D. degree at Xidian University, Xi’an, China in 1994, 1997 and 2001, respectively. From Mar. 2000 to Feb. 2001, he was a visiting researcher at Shizuoka University, Hamamatsu, Japan. From Jan. 2002 to Feb. 2004, he was a senior research associate at Illinois Institute of Technology, Chicago, USA. He is currently an associate professor at School of Electronics and Information Engineering, Beihang University, Beijing, China. He is also a member of IEEE and senior member of CIE. His research interests include mobile ad hoc networks, wireless sensor networks, cognitive networks, cooperative networks and Internet of Things.
Yupeng Zhang received his B.S. degree of Electronic and Information Engineering in June 2010 at Xidian University, Xi’an, China. He is currently a graduate student at School of Electronics and Information Engineering, Beihang University, Beijing, China. His research interests include medium access control (MAC) in wireless networks.
Feng Liu received M.S. and Ph.D. degree in Control Science and Engineering from Xi’an Jiaotong University, Xi’an, China in 1997 and 2000, respectively. Now he is a professor in School of Electronics and Information Engineering, Beihang University, Beijing, China. His research interests include network and communication theory, wireless sensor network and complex network.
References
Booysen M. J. , Zeadally S. , van Rooyen G.-J. 2011 “Survey of media access control protocols for vehicular ad hoc networks” IET Communications Article (CrossRef Link). 5 (11) 1619 - 1631    DOI : 10.1049/iet-com.2011.0085
Wu S.-L. , Lin C.-Y. , Tseng Y.-C. , Sheu J.-L. 2000 “A new multi-channel MAC protocol with on-demand channel assignment for multi-hop mobile ad hoc networks” in Proc. of IEEE ISPAN 2000 Dallas, USA Article (CrossRef Link). 232 - 237
So J. , Vaidya N. 2004 “Multichannel MAC for ad hoc networks: handling multichannel hidden terminals using a single transceiver” in Proc. of ACM Mobihoc 2004 Tokyo, Japan Article (CrossRef Link). 222 - 233
Nguyen D. , Garcia-Luna-Aceves J. J. , Obraczka K. 2009 “Collision-free asynchronous multi-channel access in ad hoc networks” in Proc. of IEEE GLOBECOM 2009 Honolulu, USA Article (CrossRef Link). 1 - 6
Lee J. , Mo J. , Trung T. M. , Walrand J. , So H.-S. W. 2010 “Design and analysis of a cooperative multichannel MAC protocol for heterogeneous networks” IEEE Transactions on Vehicular Technology Article (CrossRef Link). 59 (7) 3536 - 3548    DOI : 10.1109/TVT.2010.2051691
Shih K.-P. , Chen Y.-D. , Liu S.-S. 2010 “A collision avoidance multi-channel MAC protocol with physical carrier sensing for mobile ad hoc networks” in Proc. of IEEE AINA 2010 Perth, Australia Article (CrossRef Link). 656 - 661
Liu K. , Xing X. 2009 “A new exposed-terminal-free MAC protocol for multi-hop wireless networks” Chinese Journal of Aeronautics Article (CrossRef Link). 22 (3) 285 - 292    DOI : 10.1016/S1000-9361(08)60101-6
Bahl P. , Chandra R. , Dunagan J. 2004 “SSCH: Slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks” in Proc. of ACM MobiCom 2004 Philadelphia, USA Article (CrossRef Link). 216 - 230
Zhai H. , Wang J. , Fang Y. 2006 “DUCHA: A new dual-channel MAC protocol for multihop ad hoc networks” IEEE Transactions on Wireless Communications Article (CrossRef Link). 5 (11) 3224 - 3233    DOI : 10.1109/TWC.2006.04869
Bianchi Giuseppe 2000 “Performance analysis of the IEEE 802.11 distributed coordination function” IEEE Journal on Selected Areas in Communications Article (CrossRef Link). 18 (3) 535 - 547    DOI : 10.1109/49.840210
Ziouva E. , Antonakopoulos T. 2002 “CSMA/CA performance under high traffic conditions: throughput and delay analysis” Computer Communications Article (CrossRef Link). 25 (3) 313 - 321    DOI : 10.1016/S0140-3664(01)00369-3
Kalfas G. , Pleros N. , Tsagkaris K. , Alonso L. , Verikoukis C. 2011 “Saturation throughput performance analysis of a medium transparent MAC protocol for 60 GHz radio-over-fiber networks” IEEE Journal of Lightwave Technology Article (CrossRef Link). 29 (24) 3777 - 3785    DOI : 10.1109/JLT.2011.2172392
Cheng S.-T. , Wu M. 2005 “Performance evaluation of ad-hoc WLAN by M/G/1 queueing model” in Proc. of IEEE International Conference on Information Technology: Coding and Computing (ITCC’05) Las Vegas, NV, USA vol. 2, Article (CrossRef Link). 681 - 686
Zhang Y. , He C. , Jiang L. 2008 “Performance analysis of S-MAC protocol under unsaturated conditions” IEEE Communications Letters Article (CrossRef Link). 12 (3) 210 - 212    DOI : 10.1109/LCOMM.2008.071705
Karamad E. , Ashtiani F. 2009 “Performance analysis of IEEE 802.11 DCF and 802.11e EDCA based on queueing networks” IET Communications Article (CrossRef Link). 3 (5) 871 - 881    DOI : 10.1049/iet-com.2008.0676
Ng P. C. , Edwards D. J. , Liew S. C. 2009 “Assigning channels by link directionality in a medium access control protocol for IEEE 802.11 ad hoc networks” IET Communications Article (CrossRef Link). 3 (11) 1736 - 1746    DOI : 10.1049/iet-com.2008.0522
Yang Xinyu , Huang Yuefeng , Yang Wenjing , Yang Shuseng 2009 “A dual channel MAC protocol for providing high spatial reuse and channel efficiency” in Proc. of IEEE International Conference on Information Science and Engineering (ICISE2009) Nanjing, China Article (CrossRef Link). 3930 - 3935
Haas Z. J. , Deng J. 2002 “Dual busy tone multiple access (DBTMA): a multiple access control scheme for ad hoc networks” IEEE Transactions on Communications Article (CrossRef Link). 50 (6) 975 - 985    DOI : 10.1109/TCOMM.2002.1010617
Wu S.-L. , Tseng Y.-C. , Sheu J.-P. 2000 “Intelligent medium access for mobile ad hoc networks with busy tones and power control” IEEE Journal on Selected Areas in Communications Article (CrossRef Link). 18 (9) 1647 - 1657    DOI : 10.1109/49.872953
Liu Ke , Leng Supeng , Fu Huirong , Li Longjiang 2009 “A novel dual busy tone aided MAC protocol for multi-hop wireless networks” in Proc. of Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing (DASC 2009) Chengdu, China Article (CrossRef Link). 373 - 378
Huang Rongsheng , Zhai Hongqiang , Zhang Chi , Fang Yuguang 2008 “SAM-MAC: An efficient channel assignment scheme for multi-channel ad hoc networks” Computer Networks Article (CrossRef Link). 52 (8) 1634 - 1646    DOI : 10.1016/j.comnet.2008.02.004
Chen J. 2010 “AMNP: ad hoc multichannel negotiation protocol with broadcast solutions for multi-hop mobile wireless networks” IET Communications Article (CrossRef Link). 4 (5) 521 - 531    DOI : 10.1049/iet-com.2009.0318
Tzamaloukas A. , Garcia-Luna-Aceves J. J. 2000 “Channel-hopping multiple access” in Proc. IEEE Int’l Conf. Comm. (ICC ’00) New Orleans, LA, USA Article (CrossRef Link). 415 - 419
So H. S. W. , Walrand J. , Mo J. 2007 “McMAC: A parallel rendezvous multi-channel MAC protocol” in Proc. of IEEE Wireless Communications and Networking Conference (WCNC’07) Hong Kong, China Article (CrossRef Link). 334 - 339
Chao1 Chih-Min , Tsai Hsien-Chen , Huang Kuan-Ju 2009 “A new channel hopping MAC protocol for mobile ad hoc networks” in Proc. IEEE International Conference on Wireless Communications & Signal Processing (WCSP 2009) Nanjing, China Article (CrossRef Link). 1 - 5
Hou Fen , Cai Lin X. , Shen Xuemin , Huang Jianwei 2011 “Asynchronous multichannel MAC design with difference-set-based hopping sequences” IEEE Transactions on Vehicular Technology Article (CrossRef Link). 60 (4) 1728 - 1739    DOI : 10.1109/TVT.2011.2119384
Ng P. C. , Edwards D. J. , Liew S. C. 2010 “Scaling capacity by two channels in IEEE 802.11 ad hoc networks with an SIR comparison algorithm” IEEE Transactions on Vehicular Technology Article (CrossRef Link). 59 (4) 2071 - 2079    DOI : 10.1109/TVT.2010.2040847
Ben-El-Kezadri R. , Pau G. 2010 “TimeRemap: stable and accurate time in vehicular networks” IEEE Communications Magazine Article (CrossRef Link). 48 (12) 52 - 57    DOI : 10.1109/MCOM.2010.5673072