Communications and Network, 2013, 5, 355-360
http://dx.doi.org/10.4236/cn.2013.53B2065 Published Online September 2013 (http://www.scirp.org/journal/cn)
Collision Detection and the Design of Fair and Stable MAC
Scheme for Wireless Ad Hoc Networks
Yongkang Xiao, Rong Xiao, Bo Sun
School of Information Science and Technology, Beijing Normal University, Beijing, China
Email: xiaoyk@bnu.edu.cn
Received July, 2013
ABSTRACT
Fairness and stability guarantee among TCP flows is very stubborn in wireless ad hoc networks. There is not a MAC
protocol that can fulfill this acq uirement until no w. In th is paper, we firstly reveal the in-depth causes of the severe TCP
unfairness and instability problems in IEEE 802.11-based multihop networks. Then we utilize the collision detection
mechanism of th e IEEE 802.1 1 protocol which is often ignored b y most of the people to design a novel co llision detec-
tion mechanism-based MAC (CDMB-MAC) scheme to solve the short-term and long-term fairness and stability issues
while providing a good aggregate throug hput in many topologies.
Keywords: Ad hoc Networks; IEEE 802.11 MAC Protocol; TCP; Fair; Stable; Collision Detection Mechanism
1. Introduction
Currently, the IEEE 802.11 distributed coordination
function (DCF) [1] has been the de facto access standard
for wireless ad hoc networks. However, Reference [2,3]
have shown TCP flows over IEEE 802.11 MAC obtain
extreme unfairness, instability and incompatibility prob-
lems in multihop ad hoc networks. And they have also
shown that all these issues are rooted in the MAC layer.
Therefore, researches of how to improve the performance
of IEEE 802.11 (e.g., the fairness issue) have been re-
ceiving an increasing attention [4-6]. Unfortunately, all
of these solutions only aim at the improvement of
long-term fairness property, i.e., the average throughput
share among TCP flows during the whole simulation
interval. They do not cons ider th e fairness property in the
short time scale, e.g. second-level. More importantly,
there are few papers dealing with the stability of TCP
traffic currently.
In this article, we try to find a MAC scheme that can
provide a fair and stable communication for TCP flows
while achieving high aggregate throughput. Note that if
we can acquire short-term fairness and stability per-
formance, we naturally resolve the incompatibility prob-
lem among TCP flows. In order to achieve this aim, we
firstly introduce the collision detection mechanism of
IEEE 802.11 in detail. Then by analyzing throughput
results of TCP flows in a classic topology, we provide a
novel collision detection mechanism-based MAC (CDMB-
MAC) scheme to resolve TCP fairness and stability per-
formance while maintaining a good aggregate throughpu t.
The main advantage of CDMB-MAC is that it is easier to
implement than other methods since it only requires
minimal modifications to the IEEE 802.11 protocol. To
the best of our knowledge, this is the first attempt to ad-
dress the fairness and stability problem of TCP simulta-
neously in the design of MAC protocol for wireless ad
hoc networks.
2. Collision Detection Mechanism of 802.11
Before proceeding further we point out that the analysis
and simulation results reported in this article are b ased on
the NS2 network simulator (version 2.32) [7]. With a few
exceptions, we keep most of simulation parameters as the
default setting of NS2. And we only research th e Request
To Send/Clear To Send (RTS/CTS) scheme of IEEE
802.11 DCF and indiscriminately use the term “IEEE
802.11” and the term “RTS/CTS scheme”.
As a contention-based MAC scheme, the contention
detection mechanism plays an important role for IEEE
802.11. When a node receives a packet, the power level
at which the packet was received is compared with two
different values: the carrier sense threshold and the re-
ceive threshold. If the power level falls below the carrier
sense threshold, the packet is discarded as noise. If the
received power level is above the carrier sense threshold
but below the receive threshold, the packet is marked as a
packet in error before being passed to the MAC layer.
Otherwise, the packet is simply handed up to the MAC
layer.
Once the MAC layer receives a packet, it checks to
C
opyright © 2013 SciRes. CN
Y. K. XIAO ET AL.
356
insure that its receive state is presently idle. If the re-
ceiver is not idle, one of two things can happen. If the
power rate of the packet already being received (carrier)
and the received power level of the new packet (interfer-
ence), , is greater than (the default
value is 10.0 dB in NS2), we assume capture, discard the
new packet, and allow th e receiving interface to con tinue
with its current receive operation. Otherwise, a collision
occurs and both packets are dropped. In other words,
whether a collision occurs at the receiver of the MAC
layer depends on the val ue of [7,10].
CINR CPThresh
NRCI
3. Performance Problem of IEEE 802.11
Consider a classic topology with four nodes (0 through 3)
as shown in Figure 1. All nodes communicate with a
bandwidth of 2 Mbps, and the transmission range is
equal to 250 m. According to the IEEE 802.11 protocol
implementation in the NS2 simulation software, the in-
terfering range (sensing range) is 2.2 times the size of the
communication range, i.e. 550 m. The distance between
any two neighboring nodes is equal to 200 m. We set up
two TCP-Reno sessions as shown in Figure 1. The first
session is from node 0 to 1 and the second from 3 to 2.
Each TCP flow is an FTP session transf er r in g a lar g e s i ze
file and runs for 300 s. The TCP packet size is equal to
1460 bytes and the TCP maximum window size window
is 1. The routing protocol is the dynamic source routing
(DSR) proto col [8].
Figure 2 shows the throughput results of the two flows.
The plotted values of the throughput are measured over
each 1.0 second interval. We count the successively re-
ceived TCP packets in each 1.0 interval and transfer it
into the throughput in that interval. We can observe that
two TCP sessions suffer from the serious unfairness
problem. In most of simulation lifetime, the throughput
of the second session is zero. The aggregate throughput
of these two TCP connections belongs completely to the
first session aroun d 746.362 Kbps.
Note that node 2 is in the transmission range of node 1,
it can receive and decode the CTS frame correctly, and
the virtual carrier sensing mechanism of IEEE 802.11
makes node 2 know when the current transmission be-
tween 0 and 1 will end. However, the hidden node 3 can
only sense the CTS frame, but it can not decode the
frame, because the distance between 1 and 3 is equal to
400 m which is greater than the transmission radius (250
m). Now if node 3 has data to send to 2, it will defer a
distributed interframe space (DIFS) interval and then
generate a random backoff period before transmitting.
When the backoff timer reaches zero, node 1 is silent
while receiving the TCP-Data from 0, however node 3
cannot sense the Data. Therefore, node 3 believes the
medium is idle and transmits an RTS to 2. Unfortunately,
a collision occurs at od e 2 and it cannot rep ly a CTS to 3,
so that the latter times out waiting for a CTS frame and
adopts the binary exponential backoff (BEB) algorithm
to compute a new random backoff time to retransmit the
RTS frame. Since the BEB algorithm assigns a larger
backoff counter to the failed node, node 3 cannot com-
pete the channel immediately even when the transmission
between 0 and 1 finishes. After failing seven times to
receive CTS from node 2, node 3 quits and reports a link
breakage to its upper layer. Then a route failure event
occurs. Then the TCP session has to wait before a route
becomes available again. On the other hand, node 0 does
not know that node 3 wants to communicate with 2 and
starts a new transmission immediately after a successful
one.
Here, it is very interesting why node 3’s RTS frames
do not collide with TCP-Data transmitted by node 0 at
node 1. Although the reason is often ignored by most of
the people, it is very important to the improvement of
TCP performance. According to the two-ray ground re-
flection model [7], the received power at distance d is
predicte d by
22
4
() ttrtr
r
PGG hh
Pd dL
(1)
Figure 1. A classic topology with two TCP connections.
0100 200 300
0
200
400
600
800
Throughput(Kbps)
Time ( s )
From 0 to 1
0100 200 300
0
200
400
600
800
Throughput(Kbps)
Time(s)
From 3 to 2
Figure 2. TCP throughput in the IEEE 802.11-based net-
work, d1 =d2 =d3= 200m, window= 1.
Copyright © 2013 SciRes. CN
Y. K. XIAO ET AL. 357
where t is the transmitted signal power. and
are the antenna gains of the transmitter and the receiver
respectively. L() is the system loss. t and r are
the heights of the transmit and receive antennas respec-
tively. We assume that each node is equipped with the
same wireless radio, therefore is only dependant
on the distance of the receiver to two senders. For exam-
ple, the at node 1 in Figure 1 is
P
CI
tGtG
1Lh h
CINR
NR
4
01
131
23 16 10
1
Pdd
CINR CPThresh
Pd

 

 (2)
where and is the received power of signal and
interference at node 1 transmitted by node 0 and 3 re-
spectively. According to the collision detection mecha-
nism, if node 1 is receiving a Data from 0, a new arriving
RTS frame from node 3 can only defer the channel ac-
cess of 1, but does not collide with the TCP-Data from 0.
However, the default value of RTS retry count (RRC) is
so small that node 3 reports a link breakage to its upper
layer too early which causes a serial of problems men-
tioned above. Therefore, the deference occurring at node
1 does not have an effect on node 0, and the latter starts a
new transmission as soon as it receives the ACK frame.
An intuition here is that a large value of RRC should be
able to effectively suppress the channel access of node 0
and 1 and at the same time give a high opportunity to
node 3 to acquire the channel successfully after a MAC
layer transmission of the first session finishes.
01P31P
4. Collision Detection Mechanism-Based
Scheme
The CDMB-MAC scheme can be summarized as follows:
When the CINR value is greater than the CPTh resh value,
a node transmits with a probability p if the channe l is idle
for a period of time equal to a DIFS. With a probability q
= 1-p, it backoffs with a fixed time interval T. When the
backoff timer timeouts, and if the channel is also idle, it
either transmits or defers again with the same probabili-
ties and . This process is repeated until either the
frame has been transmitted or the maximum RTS retry
count RRC is reached. In the latter case, the MAC layer
of the unluck y node will drop its transmitti ng packet and
report a link breakage to its upper layer. If the node ini-
tially senses the channel busy, it waits until the medium
becomes idle without interruption for a DIFS, then ap-
plies the above algorithm. Note that when a node re-
transmits an RTS frame, the backoff window size is still
equal to T. For CDMB-MAC, three important parameters
need be designed carefully, i.e., maximum RTS retry
count RRC, backoff window size T and transmission
probability . According to the simulation results, we
set as 200, T as the minimum contention window
of IEEE 802.11 MAC protocol, that is (31
slot time) [7], and as 0.4.
p
RR
q
p
C
min
TCW
p
d2
For CDMB-MAC, each node determines its RTS
transmission or waits only according to its own channel
state. This is a main advantage over the traditional p-
persistent CSMA algorithm in wireline networks, be-
cause CDMB-MAC does not require to divide time into
discrete intervals and thus does not need a synchroniza-
tion scheme to make nodes agree on slot boundaries.
5. Performance Evaluation
The goal of the following simulation is to evaluate the
performance of the CDMB-MAC scheme in various
scenarios. The maximum window size of TCP, window,
is equal to 8 in the next simulations.
5.1. Classic Topology
1) Case 1: mdd 20031
: In this scenario, the
distance between node 0 and 3 is 600 m and is greater
than the carrier sense range, therefore the two nodes are
fully independent. The main problem with IEEE 802.11
is the serious long-term unfairness and incompatibility
problems as shown in Figure 2.
Figure 3 is TCP throughput of the two flows in the
CDMB-MAC-based network. In the 300 s lifetime of the
two flows, there is not one time when the throughput
reaches zero. The aggregate throughput in Figure 2
(752.522 Kbp s) is greater than that in Figure 3 (680.042
Kbps), however the stability and short-term fairness per-
formance of the latter is far better than that of the former.
And two simultaneous TCP traffics can coexist in the
0100 200 300
0
100
200
300
400
500
Throughput (Kbps)
Time ( s )
From 0 to 1
0100 200300
0
100
200
300
400
500
Throughput(Kbps)
Time( s)
From 3 to 2
Figure 3. Throughput of two TCP flow s in the CDMB-MAC
network, d1 =d2 =d3= 200m.
Copyright © 2013 SciRes. CN
Y. K. XIAO ET AL.
358
network at the same time. It is well-known that there is a
fundamental conflict between achieving flow fairness
and maximizing overall throughput. We must have a
trade-off between aggregate throughput and fairness.
Therefore, this result is really what we need.
From the simulation trace file of NS2 which is not
presented here, we can find that node 0 has transmitted
8493 different RTS frames successfully. About 52%
frames are transmitted without any retransmission; about
40% frames are transmitted with a retry count less than
10; and about 2% frames need be retransmitted above 15
times. A similar case also occurs at node 3. The biggest
RTS retry count for nodes 0 and 3 are 29 and 34 respec-
tively. Obviously if we set RRC = 7(the default setting of
IEEE 802.11), CDMB-MAC will also results in a serious
fairness and incompatibility issue. A large RTS retry
attempts will give two flows a big opportunity to access
the channel, so that they can simultaneously share the
channel stably and fairly.
2) Case 2:d1 =d3= 200 m, d2= 155 m: In this scenario,
the distance between node 1 and 2, d2, is reduced to 155
m. Figure 4 shows TCP throughput of the two flows in
the CDMB-MAC network. From the long-term fairness
point of view, the two flows can fairly share the channel.
This result is better than that in the IEEE 802.11-base
network where one flow monopolizes the channel and
the other is starved. However, in the 300 s lifetime of two
connections, they cannot share the channel simultane-
ously and there are 66 times when the aggregate
throughput reaches zero. Therefore, from the short-term
fairness and stability points of view, this result is not
really what we need.
0100 200 300
0
200
400
600
800
Throughput(Kbps)
Time( s )
From 0 to 1
0100200 300
0
200
400
600
800
Throughput(Kbps)
Time (s )
From 3 to 2
Figure 4. Throughput of two TCP flow s in the CDMB-MAC
network, d1 = d3= 200 m, d2 =155 m.
The reason can be explained as follows. In this sce-
nario, the distance between node 0 and 3 is 555 m which
is greater than the carrier sense range, therefore node 3
cannot sense the frame transmitted by 0, either. From
Equation (2), the CINR at both node 1 and 2 are equal to
9.926 (<10). When node 1 is receiving the TCP-Data
from 0, the new or retransmitted RTS frame from node 3
would collide with the TCP-Data frame, therefore node 1
must drop two frames. This case also occurs at node 2.
These collisions and drops degrade seriously TCP per-
formance.
Fortunately, we can utilize the node mobility to im-
prove the TCP performance. As we all known, node mo-
bility is an important characteristic of ad hoc networks.
However, arbitrary movement does not benefit our
CDMB-MAC scheme. Since the transmitters need to
communicate with the receiver, they should move coop-
eratively so that CINR of the receiver can be greater than
. Here if the receivers can move only one me-
ter towards the transmitters, we can also achieve an ideal
result similar to that shown in Figure 3.
CPThresh
3) Case 3:d1 =199 m, d2= 155 m, d3= 200 m: From
Equation (2), the CINR at node 1 is equal to 10.1275
(>10), and that in node 2 is equal to 9.8151 (<10) in this
scenario. Figure 5 shows TCP throughput of the two
flows in the CDMB-MAC network. In the 300 s lifetime
of the two flows, there is not one time when the
throughput reaches zero. The stability and short-term
fairness performance is also satisfying.
Because there is some collision at node 2, the aggre-
gate throughput is 496.682 Kbps which is less than that
0100 200 300
0
100
200
300
400
500
Throughput(Kbps)
Time (s )
From 0 to 1
0100 200 300
0
100
200
300
400
500
Throughput(Kbps)
Time(s)
From 3 to 2
Figure 5. Throughput of two TCP flow s in the CDMB-MAC
network, d1 =199 m, d2 =155 m, d3= 200 m.
Copyright © 2013 SciRes. CN
Y. K. XIAO ET AL. 359
in that in Figure 3. And since there is not collision at
node 1, throughpu t of session 1 is about two ti mes that of
session 2. As mentioned above, the node mobility can
also improve the network performance. Here if the node
3 move only one meter towards node 2, we can also
achieve an ideal result similar to that shown in Figure 3.
4) Case 4:d1 =d2 =d3= 150m: Different from the sce-
narios above, all nodes are within the carrier sense range
of one another in this scenario. Figure 8 shows the
throughput of the two flows in the CDMB-MAC-based
network. Here, the average throughput of the two flows
is 354.881 and 359.201 Kbps, respectively. In the 300 s
lifetime of the two flows, there is not one time when the
throughput reaches zero. More important, we are satis-
fied with the stability and short-term fairness perform-
ance.
Note that node 3 can decode the CTS frame from 1 in
this scenario. Therefore, if node 1 is receiving the
TCP-Data from 0, node 3 does not transmit an RTS
frame. This is also true for node 0. In other words, if one
flow has finished the RTS/CTS handshake successfully,
it can communication withou t collision. However, a large
value of RRC an d fixed size of b ackoff window will giv e
a high opportunity to two flows to access the channel.
5.2. Adaptivity Analysis of CDMB-MAC
According to simulation results above, we can find if
CINR of the receiver is greater than CPThresh or correla-
tive channel contenders are within the carrier sense range
of one another, that is
0100 200 300
0
100
200
300
400
500
Throughput(Kbps)
Time( s)
From 0 to 1
0100 200 300
0
100
200
300
400
500
Throughput(Kbps)
Time( s)
From 3 to 2
Figure 6. Throughput of two TCP flow s in the CDMB-MAC
network, d1 =d2 =d3= 150 m.
121.77828 3
231.77828 1
dd d
dd d


(4)
or
123550dd dm
 (5)
CDMB-MAC can provide perfect long-term and short-
term fairness and stability performance while maintain-
ing a good aggregate. Especially, from Equation (4) and
(5), we can deduce a following important fact. In spite of
the value of , if
2d1198dm
and , we
can acquire ideal TCP performance. In addition, if the
value of CINR is greater than CPThresh at a MAC re-
ceiver, and its contending nodes do not meet this re-
quirement, we can also acquire good TCP performance
as the result presented in Case 3. And th e TCP parameter,
known as maximum window size (window), only has a
small effect on the performance. We argue that these
conditions are not the defect of our CDMB-MAC scheme.
On the contrary, they actually provide a deployment
guide for ad hoc networks. If the network topology does
not satisfy the requirement of Equation (4) or (5), we can
utilize node mobility or power control technology to im-
prove network performance, which need further investi-
gation.
3198md
6. Conclusions
In this article we focus on the following question: How
to acquire fair and stable TCP communication in multi-
hop ad hoc networks? Based on the collision detection
mechanism of IEEE 802.11, this article has proposed a
new CDMB-MAC scheme based on IEEE 802.11.
CDMB- MAC replaces the BEB algorithm with a p-per-
sistent transmission strategy and adopts a lot of retry at-
tempts when a node cannot transmit an RTS frame suc-
cessfully. We have analyzed CDMB-MAC performance
from fairness, stability and efficiency points of view in
some classic scenarios that are known to lead to fairness
issues. Simulation results show if at the MAC layer
CINR of the receiver is greater than CPThresh or correla-
tive channel contenders are within the carrier sense range
of one another, CDMB-MAC can provide perfect long-
term and short-term fairness and stability performance
while maintaining a good aggreg ate.
More importantly, we provide a guide of node move-
ment and deployment. Since the ad hoc network is a
self-organizing network, nodes especially the MAC
layer’s receiver should not move completely blindly and
arbitrarily. In the future, we will design a movement al-
gorithm according to this guide and an adaptive algo-
rithm to adjust the transmission probability to acquire
optical performance in different topol ogi es.
Copyright © 2013 SciRes. CN
Y. K. XIAO ET AL.
Copyright © 2013 SciRes. CN
360
REFERENCES
[1] IEEE STD. 802.11, “Wireless LAN Medium Access
Control (MAC) and Physical Layer (PHY) Specifica-
tions,” 1999.
[2] S. G. Xu and T. Saadawi, “Does the IEEE 802.11 MAC
Protocol Work Well in Multi-hop Wireless ad Hoc Net-
works?” IEEE Communica-tions Magazine, Vol. 39,
No. 6, 2001, pp. 130-137. doi:10.1109/35.925681
[3] S. G. Xu and T. Saadawi, “Revealing the Problems with
802.11 Medium Access Control Protocol in Multi-hop
Wireless ad Hoc Networks, Computer Networks, Vol. 38,
2002, pp. 531-548. doi:10.1016/S1389-1286(01)00273-0
[4] J. He and H. K. Pung, “Fairness of Medium Access Con-
trol Protocols for Multi-hop Ad Hoc Wireless Networks,”
Computer Networks, No. 48, 2005, pp. 867-890.
doi:10.1016/j.comnet.2004.11.020
[5] C. Chaudet, G. Chelius, H. Meunier and D. Simplot-Ryl,
“Adaptive Prob-abilistic NAV to Increase Fairness in Ad
Hoc 802.11 MAC layer,” Proc. of the MedHoc NET,
2005.
[6] T. Razafindralambo and I. Gu´erin-Lassous, “Increasing
Fair-ness and Efficiency Using the MadMac Protocol in
Ad Hoc Networks,” Ad Hoc Networks, No. 6, 2008, pp.
408-423. doi:10.1016/j.adhoc.2007.03.003
[7] Network Simulator 2 (ns2), http://www.isi.edu/nsnam/ns.
[8] D. B. Johnson, “Routing in Ad Hoc Networks of Mobile
Hosts,” In Proc. of the IEEE Workshop on Mobile Com-
puting Systems and Applications, 1994, pp. 158-163.
[9] R. Jain, A. Durresi and G. Babic, “Throughput Fairness
Index: An Explanation,” ATM Forum/99-0045, Feb. 1999,
http://www.netlab.ohio-state.edu/˜jain/atmforum.htm.
[10] J. Broch, D. A. Maltz, D. B. Johnson, Y.-C. Hu and J.
Jetcheva, “A Performance Comparison of Multi-hop
Wireless Ad Hoc Network Routing Protocols,” In Proc.
of Mobile Computing and Networking, 1998, pp. 85-97.