Abstract: Some auto rate protocols at the MAC layer have been proposed to improve the throughput of Ad Hoc networks with multiple rates support at physical layer. However, all of them neglect the influence of network congestion. The network performance will deteriorate as a result of transmitting data to a congested node. In this study, an auto rate protocol based on congestion detection called auto rate based on congestion detection (ARCD) is proposed. In the ARCD protocol, congestion level is detected at the receiving nodes and fed back to the sending nodes along with the rate selection information and then the sending nodes transmit a limited number of back-to-back packets at appropriate rates. The simulation results show that the ARCD protocol can not only improve the throughput and packet delivery ratio of Ad Hoc networks by taking full advantage of channel condition, but also achieve hop-by-hop congestion control.
INTRODUCTION
A wireless Ad Hoc network is usually defined as a set of wireless mobile nodes that dynamically self-organize a temporary network without any central administration or existing network infrastructure (Frodigh et al., 2000). Since, the nodes in wireless Ad Hoc networks can serve as routers and hosts, they can forward packets for other nodes if they are on the path from the source to the destination. Wireless Ad Hoc networks make it easily to achieve ubiquitous communication.
The channel condition is time-variant in Ad Hoc network. The channel efficiency is low if all the data packets are transmitted at a single rate. The IEEE802.11a (IEEE Computer Society, 1999a), 802.11b (IEEE Computer Society, 1999b) and 802.11 g (IEEE Computer Society, 2003) provide physical layer capability to support multi-rate. Some auto rate MAC protocols are presented to improve the throughput of Ad Hoc network. The basic thought of auto rate MAC protocols is that the sending nodes transmit data packets at appropriate rates, which are selected according to the channel condition estimation, to achieve significant throughput gain. By far, the auto rate MAC protocols are divided into two kinds. One kind of them, such as ARF (Auto Rate Fallback) (Kamerman and Monteban, 1997) protocol, estimates the channel quality at the sender based on the information of previous data packet transmissions and increases or decreases the data rate after a number of consecutive success or losses, respectively. RBAR (Receiver-Based Auto Rate) (Holland et al., 2001), OAR (Opportunistic Auto Rate) (Sadeghi et al., 2002) and AAR (Adaptive Auto Rate) (Lin and Chang, 2003) are the instances of the other kind. In these protocols, the channel condition is estimated by the receiver after receiving the RTS frames. The transmission rate of the next data packet is selected by the receiver based on the channel condition and sent back to the sender in the CTS or ACK frames. Then, the sender transmits the data packet at the selected rate. The estimation of channel condition at the receiver is more accurate than estimation at the sender (Sadeghi et al., 2002). Thus, the rate adaptive mechanisms at the receiver can obtain better throughput than that at the sender.
Although, the mentioned auto rate MAC protocols can make good use of the channel condition and increase the throughput of the network, they all neglect the influence of the network congestion. Congestion is one of the most important restrictions of wireless Ad Hoc networks. It may deteriorate the performance of the whole network. In Ad Hoc networks, many nodes serve as routers and they forward packets for others, so some of them may become the junctions of several flows and these nodes are very likely congested. Many packets may be accumulated at congested nodes and discarded finally. Congestion may lead to long delay, high overhead and low throughput in wireless Ad Hoc networks (Chen et al., 2007). If a node is congested while its access channel quality is high, the sending node will still transmit data packets at a high rate according to the auto rate protocols above. As a result, the congestion condition of the network will be worse. Therefore, the network congestion condition should be taken into account while designing the auto rate MAC protocols.
An auto rate MAC protocol based on congestion detection, called ARCD, is proposed in this study. In the ARCD protocol, the congestion level is measured and fed back to the upstream node along with the rate selected based on the estimation of the channel quality. The upstream node determines the number of the back-to-back packets and transmits the back-to-back data packets at the selected rate. The throughput is optimized and the hop-by-hop congestion control is achieved.
CONGESTION DETECTION
A number of congestion detection methods have been proposed in literatures. These methods can be divided into two types: single-metric and multi-metric. In single-metric methods, buffer occupancy, packet drop rate, channel loading and transmission time etc., are always employed to measure the congestion level. Chen et al. (2007) used WCD (Weighted Congestion Delay) as congestion metric, WCD was the weighted sum of queue time, transmission time and the time spent at MAC layer. If WCD was above the threshold, the node was considered to be congested. He et al. (2008) utilized buffer occupancy to measure the congestion level. Congestion was divided into 3 levels according to the buffer occupancy (Tran and Raghavendra, 2006). A node was said to be green, yellow or red, if the buffer occupancy was below 1/2, between 1/2 and 3/4, or above 3/4. The higher the buffer occupancy is, the more likely the node is congested. Wang et al. (2007) proposed Intelligent Congestion Detection (ICD) to measure local congestion level at each intermediate node. The ICD represents the ratio of the input packet rate to the outgoing packet rate. In multi-metric methods, several metrics are cooperatively taken to measure the congestion level. Hu and Johnson (2004) proposed to quantify the congestion level by queue length and average MAC layer utilization. Fu et al. (2002) pointed out that packet loss in Ad Hoc networks is resulted from congestion, channel error, route change, disconnection. They differentiated the causes by 4 different metric to provide accurate congestion information to the improved TCP protocol; Wan et al. (2003) combined queue length and channel loading to differentiate congestion and contention. Wang et al. (2007) proposed a congestion control mechanism based on bandwidth estimation. In order to get the metric of congestion degree, the available bandwidth was estimated through the work status of wireless link that monitored by the node continuously.
Wan et al. (2003) pointed out that queue length could not accurately and timely reflect the node congestion degree. Otherwise, in multi-metric methods, it is needed to judge once for each metric. Monitoring multiple metrics cost much more energy, but energy is the most constrained resource for a wireless device. All the methods above can reflect the current or past congestion level, but they cannot predict the congestion change tendency. Therefore, we propose a novel quantitative congestion detection method for Ad Hoc network.
It is assumed that the node’s total buffer size is Q and the current number of packets in the buffer is q. When the buffer is full, i.e., Q = q, the node is congested completely, the packets arrived at this node will be discarded. Conversely, when the buffer is not full, the input packet rate Rin and output packet rate Rout are monitored.
Rin is the reciprocal of ΔTin, i.e. Rin = 1/ΔTin, where, ΔTin represents the packet arrival interval. Packet arrival interval is defined as the time interval of two consecutive packets received at the node MAC layer. Rout is the reciprocal of ΔTout, i.e., Rout = 1/ΔTin, where, ΔTout represents the packet service time. Packet service time is referred as the time interval between the time that a packet arrives at MAC layer and the time that it is transmitted successfully, ΔTout is the sum of the time for queue, collision, backoff and transmission (Wang et al., 2007). In out method, ΔTin and ΔTout are measured by using Exponential Weighted Moving Average (EWMA) algorithm as follow:
| (1) |
| (2) |
where,
There are special cases that when congestion detection information is updated,
there is no packet arrived or sent out at the node for a long time. So, the
input packet rate or the output packet rate should be close to 0. In other words,
| (3) |
| (4) |
where, γ is the ratio of the interval between congestion detection time tD and arrival time of the last packet tla and the last packet arrival interval tla-tsla; λ is the ratio of the interval between congestion detection time tD and the time that the last packet is transmitted successfully tlo and the service time of the last outgoing packet Ts. γ and λ are represented as follow:
| (5) |
| (6) |
If γ≤5, the value of
When Rin > Rout, the node buffer is getting smaller and the node is getting congested. When Rin≤Rout, the node buffer is getting bigger or keeps invariant, the node keeps away from congestion. Therefore, the maximum number of packets that the node can accept in T sec represented by N, is:
| (7) |
where, ([Q-q+(Rout-Rin)T] represents rounding the value of Q-q+(Rout-Rin)T down. And the value of N should be between 0 and Q, i.e., N∈[0,Q]. In T sec, the bigger the value of N is, the less congested the node is. Conversely, the smaller the value of N is, the closer to overflow the buffer is, the more congested the node is.
THE AUTO RATE MAC PROTOCOL BASED ON CONGESTION DETECTION
The basic thought of ARCD is that the receiver measures its congestion condition and sends the congestion information back to the sender along with the transmission rate selected based on the channel condition and the sender transmits a limited number of back-to-back data packets at the selected rate according to the feedback information. If the receiver is less congested, the sender transmits as many back-to-back packets as possible at a higher rate while the channel quality is high. If the receiver is badly congested, the sender decreases the number of back-to-back packets and transmits them at an appropriate rate to alleviate the congestion.
First, the frame formats of RTS, CTS, ACK and DATA should be modified. Instead of carrying the duration of the reservation, the control frames and data frames carry the data rate and size of data packet. Referring to Fig. 1-4 the 16 bit duration field in standard IEEE 802.11 (IEEE Computer Society, 1997) frame is replaced by a 4 bit rate subfield and a 12 bit length subfield. The duration of the reservation can be calculated by the data rate and packet size. The overhearing nodes can update their NAV value according to the data rate and packet size.
| Fig. 1: | The modified frame format of RTS |
| Fig. 2: | The modified frame format of CTS |
| Fig. 3: | The modified frame format of ACK |
| Fig. 4: | The modified frame format of DATA |
A congestion detection information field called CD is appended to the CTS and ACK frames, it is utilized to notify the sending nodes the maximum number N of packets to transmit which is calculated by the Eq. 7.
When the sender attempts to transmit data packets to the receiver, a RTS frame is transmitted to the receiver at basic rate so that the receiver in the transmission region can accept it without error. By estimating the channel condition at the physical layer according to received power information, the highest feasible rate for the next DATA packet is chosen and set to the rate subfield of the CTS frame which is used to reply the RTS frame. The value of packet length subfield in CTS frame can get from that of RTS frame. At the same time, the congestion level is detected and the value of N is calculated by Eq. 7. Here, the value of T in Eq. 7 is the sum of the time required to transmit one CTS frame and two SIFS (Short Inter Frame Space) intervals, i.e., T = TCTS+2TSIFS, where, TCTS is the time required to transmit one CTS frame and TSIFS is a SIFS interval. The congestion detection field CD is set to the value of N. Then, the CTS frame is sent back to the sender.
The reason that the CTS frames send back the value of N rather than the parameters like Rin, Rout and q in the Eq. 7 is that feeding back the value of N can shorten the length and the transmission time of the CTS frames. However, each node needs higher computational capability.
The channel coherence times (durations for which mobile stations have better-than-average channels) are typically at least multiple packet transmission times. As a result, when the sending node accesses the channel and the channel quality is high, multiple data packets can be transmit at a high rate in a channel access time. The sender can transmit [transmission rate/base rate] back-to-back packets in a channel access time. For instance, if the transmission rate chosen according to the channel quality is 11 Mbps and the base rate is 2 Mbps, the sender is granted a channel access time to send [11/2] = 5 packets (Sadeghi et al., 2002). This mechanism reduces the random backoff time to contend for the channel for each packet and times of sending RTS/CTS and makes effective use of channel condition. This conclusion is adopted and modified in our mechanism.
On receiving the CTS frame, the sending node calculates the number of the back-to-back packets transmitted in a channel access time. According to the conclusion of the study Sadeghi et al., (2002) presented, the number should be calculated as [transmission rate/base rate]. However, Sadeghi et al., (2002) neglected the congestion condition. Thus, the number of the back-to-back packets transmitted in a channel access time which will not make the receiver’s queue overflow should be set by comparing the value of [transmission rate/base rate] and N which is got from the CD field of the CTS frame. When [transmission rate/base rate]<N, the receiver’s queue will not overflow if the sender transmits [transmission rate/base rate] back-to-back packets in a channel access time. Conversely, when [transmission rate/base rate]≥N, the receiver’s queue will be full or overflow and the receiver will be congested, if sender transmits [transmission rate/base rate] back-to-back packets in a channel access time. In order to keep the receiver’s from being full or overflow, the maximum number of packets transmitted in a channel access time, represented by M , should be set as:
M = min{[transmission
rate/base rate], N-1} | (8) |
Then the sending node begins to transmit a DATA packet at the rate which is got from the rate subfield of the CTS frame. After transmitting a DATA packet successfully, the value of M is reduced by 1.
Due to the mobility of Ad Hoc networks and the uncertainty of wireless media, the channel quality is time-variant. In the process of transmitting back-to-back packets, the channel condition will be not utilized effectively if the packets are transmitted at a lower rate when the channel quality becomes higher. Conversely, the BER will increase and data packets cannot be received correctly if the packets are transmitted at a higher rate with lower channel quality. Therefore, the transmission rate of each DATA packet should be adapted dynamically. In our ARCD protocol, the transmission rate for the next DATA packet and the maximum number of packets that the node can accept are also fed back to the sender by the ACK frame. DATA/ACK packets serve as virtual RTS/CTS packets. Here, the value of T in Eq. 7 is the sum of the time required to transmit one ACK frame and 2 SIFS intervals, i.e., T = TACK+2TSIFS, where, TACK is the time required to transmit one ACK frame.
After receiving the ACK frame, the sender should compare the current value of [transmission rate/base rate], N and M whose value has been reduced by 1. The new value of M is set as the minimum of these three parameters. Then the next DATA frame is transmitted and the value of M is reduced by 1. The channel is released and all the sending nodes begin to contend for the channel until the value of M counts down to 0.
The brief processes of our ARCD protocol on senders and receivers are shown in Fig. 5.
The ARCD protocol reduces the overhead of contention by transmitting multiple back-to-back packets according to the channel quality.
| Fig. 5: | The brief processes of ARCD on senders and receivers |
Furthermore, the influence of congestion in Ad Hoc networks is well considered in ARCD protocol. The ARCD protocol adopts hop-by-hop congestion control mechanism, reduces the input packets of the congested nodes or areas to relieve the congestion level.
RESULTS
Here, we used the NS2(Network Simulator) to evaluate the performance of the ARCD protocol and compared it with OAR protocol and IEEE802.11 protocol with single rate. The available rates were set to 2, 5.5 and 11 Mbps based on IEEE802.11b. For the rate adaptation algorithm, we used a threshold based technique. Here, the rate was chosen by comparing the channel quality estimated against a series of thresholds based on the setting of Cisco Aironet 350 series client adapter (Cisco System Inc., 2003). The thresholds used in the simulation are listed in Table 1.
The topology of simulation is shown in the Fig. 6. Node A and Node B transmitted CBR traffic to the Node D respectively and the packets were forward by the Node C. All the nodes moved in a region with a 5 m radius. The buffer size was 50 packets and the data packet size was 1000 bytes. The AODV (Ad Hoc on-Demand Distance Vector routing) protocol (Perkins et al., 2003) was employed as the routing protocol in the simulation.
We varied the offered traffic load to compare the performance of ARCD, OAR and IEEE802.11 with fixed rates. Figure 7 shows the end-to-end throughput of ARCD, OAR and IEEE802.11 with fixed rates for variant offered traffic load. Figure 8 shows the packet delivery ratio of ARCD, OAR and IEEE802.11 with fixed rates for variant offered traffic load.
| Table 1: | The received power threshold in simulation |
| Fig. 6: | The simulation topology |
| Fig. 7: | Throughput comparison for various offered traffic load |
| Fig. 8: | The comparison of packet delivery ratio for various offered traffic load |
In Fig. 7, it could be found that the throughput of all the protocols increased linearly with the growth of the offered traffic load before the congestion happened. Because of congestion and the limit of rate, the throughput of IEEE 802.11 with fixed rates stopped increasing when the offered traffic load was up to a certain value. While the OAR protocol and our protocol could adapt the rate to transmit packets, they got better throughput than the IEEE802.11 with fixed rates when the congestion happened. Figure 7 shows that the OAR achieved about 8% throughput gain over the IEEE802.11 with fixed rate at 11Mbps and our ARCD protocol achieved about 3% throughput gain over the OAR protocol and about 12% throughput gain over the IEEE802.11 with fixed rate at 11Mbps when the congestion happened.
In Fig. 8, we could find that the packet delivery ratio decreased sharply when the offered traffic load was up to a certain value. The packet delivery ratio of our ARCD protocol was better than the others. The packet delivery ratio of our ARCD protocol was approximately 4% higher than that of the OAR protocol and 9% than that of the IEEE802.11 with fixed rate at 11Mbps when the congestion happened.
DISCUSSION
Congestion control is more complicated in Ad Hoc networks than that in the traditional networks because of the characteristic of Ad Hoc network, such as the uncertainty of the wireless channel and the distributed resource management. Present ARCD protocol is a kind of hop-by-hop congestion control. The differences between the ARCD protocol and the other study are the distinctive congestion detection method and rate adaption algorithm which corresponds to our congestion detection method nicely. Our congestion detection method reflects the change tendency of congestion level instead of the obsolete congestion information in the earlier study. This method can be employed by other congestion control mechanisms as congestion detection, too.
The simulation results show that our ARCD protocol performs better than the OAR protocol and IEEE802.11 with fixed rates in term of end-to-end throughput and packet delivery ratio, particularly when the offered traffic load is high and the network is likely congested. This is because:
Our congestion detection method can not only measure the congestion level accurately and timely, but also predict the congestion variation tendency.
Our ARCD protocol transmits appropriate number of packets to the congested nodes at appropriate rate according to the congestion condition and the channel quality. Unlike OAR protocol, our mechanism can avoid that too many packets is accumulated at congested nodes and dropped finally. Thereby, our ARCD protocol can increase the packet delivery ratio and throughput and mitigate the congestion problem.
When the offered traffic load is low, the network is far from congested. The number of packets transmitted in a channel access time in ARCD protocol is the same with that in OAR protocol. Thus, the performance of ARCD protocol is almost the same with that of OAR protocol when the offered traffic load is low.
The ARCD protocol adopts the OAR’s conclusion that multiple data packets can be transmit at a high rate in a channel access time when the sending node accesses the channel and the channel quality is high and modifies its mechanism based on this conclusion. From the simulation results, it can be found that OAR protocol achieves better performance than the IEEE802.11 with fixed rate. However, the performance of OAR is inferior to ARCD’s.
The results prove that our ARCD protocol achieves our aim to improve the packet delivery ratio and throughput and mitigate the congestion problem of wireless Ad Hoc networks.
CONCLUSION
In this study, we proposed an auto rate MAC protocol based on congestion detection for wireless Ad Hoc networks, called ARCD. In the ARCD protocol, the sending nodes transmit a limited number of back-to-back packets at appropriate rates according to the information which is detected at receiving nodes and fed back to the senders, so that the congestion is alleviated and the performances like throughput and packet delivery ratio are improved. By comparing the OAR and IEEE 802.11 with fixed rate, the outstanding performance of the ARCD protocol is verified with simulation.
ACKNOWLEDGMENTS
This study is supported by the National Basic Research Program of China under Grant No. 2007CB310601.