Priority scheduling in wireless ad hoc networks.
Ad hoc networks formed without the aid of any established infrastructure are typically multi-hop networks. Location dependent contention and "hidden terminal" problem make priority scheduling in multi-hop networks significantly different from that in wireless LANs. Most of the prior work related to priority scheduling addresses issues in wireless LANs. In this paper, priority scheduling in multi-hop networks is discussed. We propose a scheme using two narrow-band busy tone signals to ensure medium access for high priority source stations. The simulation results demonstrate the effectiveness of the proposed scheme.
INTRODUCTION
With advances in wireless communications and the growth
of real-time applications, wireless networks that support quality
of service (QoS) have recently drawn a lot of attention.
In order to provide di#erentiated service to real-time and
non-real-time packets, the medium access control protocol
must provide certain mechanisms to incorporate di#erenti-
ated priority scheduling, such that higher priority tra#c can
be transmitted in preference to lower priority tra#c.
# This research is supported in part by National Science
Foundation grant ANI-9973152.
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, to
republish, to post on servers or to redistribute to lists, requires prior specific
permission and/or a fee.
MOBIHOC'02, June 9-11, 2002, EPFL Lausanne, Switzerland.
There are two standards for wireless networks that cover
MAC sub-layer: the European Telecommunications Standards
Institute (ETSI) High Performance European Radio
LAN (HIPERLAN) [4] and the IEEE 802.11 WLAN [6].
HIPERLAN explicitly supports QoS for packet delivery in
wireless LANs. IEEE 802.11 may carry tra#c with time-bounded
requirements using PCF (Point Coordination Func-
tion), which needs the coordination of an "Access Point".
Neither of them can provide e#ective priority scheduling in
ad hoc networks.
By wireless LAN, we mean a network in which all stations
1 are within each other's transmission range. On the
other hand, in multi-hop networks, two stations that cannot
hear each other may still compete with each other for
the channel due to the "hidden terminal" problem. In such
environments, in addition to local channel information, the
channel status near the neighboring nodes also has to be
considered to ensure priority scheduling.
Another di#erence between Wireless LANs and multi-hop
networks with respect to priority scheduling is that di#erent
flows in multi-hop networks have di#erent degree of con-
tention. Here, we define the contention degree for a flow
as the number of flows with which it is competing for the
channel. While each flow competes for the channel with all
other flows in wireless LANs, in multi-hop networks, di#er-
ent flows may experience di#erent situations depending on
the network topology and flow pattern. For example, in a
multi-hop network, it is possible that flow A has contention
degree of 10 while flow B just competes with flow A. Under
such a circumstance, it might be easier for flow B to access
the channel.
While there is some research related to priority scheduling
in wireless networks [1] [9] [10] [2] [3] [7] [11] [14], most of
these schemes can only work well in a wireless LAN. In this
paper, we propose a scheme using two narrow-band busy
tone signals to achieve e#ective priority scheduling in ad
hoc networks.
The rest of this paper is organized as follows. Section 2
presents the related work. The problem of priority scheduling
in multi-hop networks is discussed in section 3. Section
4 describes the proposed busy tone priority scheduling
(BTPS) protocol. Performance evaluation is presented in
section 5. Finally, we present our conclusions in section 6.
2. RELATED WORK
Medium Access Control (MAC) protocols that aim to provide
di#erentiated services should be able to meet require-
We use the terms station and node interchangeably
ments of tra#c with di#erent priority classes. If a high priority
flow's tra#c pattern satisfies the behavior described
in the service agreement, its packets should be delivered in
preference to other packets with lower priorities. On the
other hand, flows with lower priorities should use as much
bandwidth as possible after the transmission requirements
of higher priority flows have been satisfied.
In general, there are two directions in wireless MAC protocols
to facilitate channel access privilege of high priority
tra#c: reservation based schemes and contention based
schemes.
Reservation based schemes usually make some assumptions
about high priority tra#c. For example, high priority
tra#c is assumed to be periodic with fixed arrival rate. For
reservation based schemes, when resources are reserved but
unused, they are often wasted. A typical example of a reservation
based MAC protocol is GAMA/PS [1]. GAMA-PS
divides time into a sequence of cycles; each cycle begins with
a contention period and ends with a "group-transmission"
period. The group-transmission period is divided into a set
of zero or more individual transmission periods, each for a
station in the "transmission group". A station with data to
send competes for membership in the "transmission group"
during the contention period; also, by listening to the chan-
nel, a group member becomes aware of how many stations
are in the group and of its own position within the group.
In this case, members of the transmission group take turn
transmitting data, and collision is avoided. However, a basic
requirement for this protocol is that each station can hear
the transmissions of other stations, which limits the use of
the protocol to wireless LANs.
The MACA/PR protocol [2] extends the reservation based
scheme to multi-hop networks. The first data packet of
a high priority flow makes reservations along the route to
the destination. Each station maintains a reservation table
(RT) which keeps track of the transmitting and receiving
"reserved windows" for neighbors within a two-hop neigh-
borhood. Low priority sources are only allowed to fill in
empty windows. In order for the reservation scheme to work,
the size of high priority packets must be pre-specified for
each connection, and the size of low priority packets must
be bounded so as not to interfere with the reservation constraints

Unlike the reservation based schemes, contention based
schemes are probabilistic. Flow scheduling decision is made
locally, and contention is resolved probabilistically. As an
example, reference [9] uses "black burst" to help high priority
flows contend for the channel. After channel becomes
idle, a high priority flow has shorter waiting time before it
transmits the "black burst", other low priority flows which
have longer waiting time will drop out of contention once
they hear the "black burst" during their waiting time. This
scheme thus provides a way for the high priority source stations
in a wireless LAN to reserve the channel by occupying
the channel with "black burst". Reference [10] further generalizes
this scheme to "ad hoc carrier sense multiple access
wireless network", which is defined as a wireless network
without hidden nodes. That is, each source station in such
a network can always sense the possible interfering transmis-
sions. However, this is not the case in most ad hoc networks.
More often, "hidden terminals" do exist in ad hoc networks,
and nodes cannot always sense each other's transmissions.
Thus, the scheme in [10] cannot be applied to general ad
hoc networks.
Several researchers propose some simple modifications to
the IEEE 802.11 Distributed Coordination Function (DCF)
to incorporate di#erentiated service. IEEE 802.11 DCF defines
a collision avoidance mechanism to resolve contention
among di#erent stations willing to access the medium. Each
station chooses a random number between zero and a given
"Contention Window" as the backo# duration. After sensing
the channel to be idle for a suitable "interframe space"
duration, each station waits until the backo# timer has been
counted down to zero before accessing the channel. A station
freezes its backo# timer if it senses a busy channel, and
then continues to count down the backo# timer when the
channel becomes idle for "interframe space" duration again.
If collisions occur, the colliding stations will exponentially
increase their "Contention Window" by a factor of 2. The
value of "Contention Window" is constrained to be between
CWmin and CWmax . A source station sends a "RTS" (re-
quest to send) first. If it gets a "CTS" (clear to send) back
from the receiver, the data packet will be sent, followed by
an "ACK" from the receiver. In the case that a "RTS" is
not followed by a "CTS", or "Data" is not followed by an
"ACK", collision is assumed to have occurred.
Summarizing, there are two "waiting stages" in IEEE
802.11 before the station accesses the channel.
. The "interframe space"(IFS) stage.
. The backo# stage, whose duration is a random value
between zero and the "Contention Window".
In [3], [7], [11] and [14], various schemes have been proposed
to modify the backo# stage so that di#erent priority
source stations use di#erent "Contention Window" generation
functions. For example, [3] proposes that high priority
source stations randomly choose the backo# interval from
- 1] and low priority source stations choose from
[2
is the number of consecutive times
a station attempts to send a packet. [11] proposes to set
di#erent values of CWmin and CWmax for di#erent priority
classes. [7] proposes that instead of using the exponential
factor of 2 after a collision, di#erent priority classes use
di#erent exponential increase factor. Stations with lower
priority increase their "Contention Window" much faster
than the stations with higher priority. One drawback faced
by [3], [11] and [7] is that high priority flows may possibly
experience more collisions compared to their low priority
counterparts in multi-hop networks. As a result, "high pri-
flows cannot be ensured to have smaller "Contention
hence, the priority of channel access cannot be
ensured either. In order to adapt better to multi-hop net-
works, in [14], a packet's priority information is piggybacked
in the RTS/CTS/Data/ACK frames. Based on overheard
packets, each station maintains a scheduling table, which
records priority information of flows that are within two-hop
neighborhood. The backo# duration is generated based
on the scheduling table. However, this scheme su#ers from
incomplete scheduling table which is caused by collisions,
location dependent errors, node mobility and partially overlapping
transmission regions.
All of the above schemes, which propose to modify the
backo# interval of IEEE 802.11 to incorporate di#erentiated
service, su#er from one major drawback as described below:
As the backo# timer for a low priority packet is frozen only
when the channel becomes busy, it will continue to count
down each time when the channel becomes idle again. Thus,
eventually a low priority packet that arrived earlier might
have the shortest backo# interval. In such cases, "priority
occurs in that the low priority packet has a shorter
backo# interval than backlogged high priority packets, and
grabs the channel. An example is illustrated in Figure 1.
bc-backoff counter
Packet transmission
Packet transmission

Figure

1: Priority reversal
Suppose that two ranges of backo# interval [0, 15] and
[16, 31] are now used respectively by high priority and low
priority packets. Nodes 1 and 4 have high priority packets
(flows 1, 2) to node 2 while nodes 3 and 5 have low priority
packets for node 2 (flows 3, 4). At time t1, nodes 1, 3 and 5
had packets backlogged with backo# intervals 10, 17 and
respectively. Node 1 began its transmission at time t2, so
nodes 3 and 5 froze their backo# counters with the remaining
values of 7 and 8. During node 1's transmission, at time
t3, a high priority packet arrived at node 4. Node 4 chose 9
slots as the backo# interval. When node 1 finished its transmission
at time t4, nodes 4, 3 and 5 began to count down
backo# interval after "interframe space" duration. Hence,
node 4, the high priority source node, had the largest back-
o# counter. Consequently, node 4 lost the channel access to
nodes 3 and 5.
As we mentioned earlier, IEEE 802.11 requires each station
to wait for the channel to be idle for "interframe space
duration before counting down the backo# interval.
IEEE 802.11 defines 4 types of IFS, which are used to provide
di#erent priorities for di#erent transmissions. Packets
with shorter IFS have higher priority. SIFS is the minimum
interframe space, which is used to separate transmissions belonging
to a single dialog, i.e., CTS, DATA and ACK trans-
missions, thus giving them highest priority. PIFS is used
by the PCF (Point Coordination Function) to give the Access
Point higher priority over other stations. DIFS is used
by a station willing to start a new transmission. EIFS is
the longest IFS used by a station that has received a packet
that it could not understand; this is needed to prevent the
station from colliding with a future packet belonging to an
on-going dialog.
Unlike IEEE 802.11 Distributed Coordination Function
(DCF) in which all new transmissions use DIFS as the "in-
terframe space(IFS)", [3] and [7] propose that di#erent priority
source stations can apply di#erent IFS. Specifically,
one of the schemes proposed in [7] works in the following
way. Assume that there are two priority classes: one is high
priority and the other is low priority. Then, the IFS of a
low priority flow is defined as the sum of IFS and maximum
contention window of high priority flows. The high priority
packets are constrained to increase their contention window
no larger than the above maximum value. That is, let LIFS
represent the IFS for low priority flows, HIFS represent the
IFS for high priority flows, and Cwh represent the maximum
contention window of high priority flows. Then we have:
This scheme sacrifices available network capacity to ensure
the transmissions of high priority flows. Since the entire
IFS duration is enforced before each station can continue to
count down the backo# interval, this scheme avoids the "pri-
ority reversal" problem mentioned earlier. However, there
is a critical trade-o# between making full use of bandwidth
and ensuring priority. If the maximum contention window
of high priority flows is constrained to be too small, they will
experience high degree of contention. On the other hand, if
this parameter is chosen to be too large, significant band-width
will be wasted by making low priority flows wait very
long unnecessarily when high priority flows are not backlogged

Among several choices of modifying IEEE 802.11 DCF,
shows that the scheme using di#erent IFS for di#erent
priority classes, as described above, works best. For this
reason, this scheme is chosen to be the one that we compare
our scheme's performance with. Considering only two priority
classes, this scheme is implemented in the following way:
high priority flows use DIFS as the IFS. The sum of DIFS
and Cwh (as defined above) is used as the IFS of low priority
flows. Throughout the rest of this paper, this scheme is
called "PMAC"(Priority MAC) for convenience.
3. PRIORITY SCHEDULING IN
MULTI-HOP NETWORKS
We consider two priority classes: high priority and low
priority.20
High priority flow low priority flow

Figure

2: Impact of "hidden terminals" on priority
scheduling
3.1 Impact of "Hidden Terminals" on Priority
Scheduling
Consider a very simple three-hop scenario in Figure 2.
Node 0 has high priority packets for node 1 (flow 1) and node
2 has low priority packets for node 3 (flow 2). Flow 1 and
flow 2 conflict with each other since node 2's transmission
will interfere with node 1's reception of any other packets.
When both flows are backlogged, how to ensure the channel
access priority of flow 1?
The scheme proposed in [7], which we refer to as "PMAC"
in section 2, tries to solve this problem by forcing node 2 to
wait for a longer IFS after the channel becomes idle. How-
ever, as we mentioned earlier, there is a critical trade-o#
between making full use of bandwidth and ensuring priority

The key point here is that, when node 0 has a high priority
packet backlogged, node 2 should be aware of that and
defer its transmission; on the other hand, if node 0 is not
backlogged, node 2 should maximize its own throughput.
This objective can be achieved by using two narrow-band
busy tone signals (BT1 and BT2) as proposed in this paper.
The basic idea (as elaborated later) is that whenever a high
priority packet is backlogged at node 0, it will send a BT1
every M slots before it acquires the channel, where M is a
parameter of the proposed scheme. In Figure 2, when node
1 hears this BT1, it will send a BT2. All nodes with low
priority packets that hear either BT1 or BT2 will defer their
transmissions for some duration. In this way, channel access
priority of node 0 can be ensured. Certainly, if there is no
high priority packet backlogged at node 0, node 2 will not
hear any busy tone signal, hence, its channel access will not
be a#ected at all. The details of this protocol are described
in Section 4.
3.2 Impact of Collisions on Priority
Scheduling
14low priority flow
High priority
flows

Figure

3: Impact of collisions on priority scheduling
In

Figure

nodes 0 and 2 have high priority packets for
node 1 while there is a low priority flow from node 3 to node
4. When node 3 transmits to node 4, node 1 cannot receive
any packet from node 0 or 2 during that transmission. Now
suppose the transmissions of nodes 0 and 2 collide at node
1 (this can occur with non-negligible frequency). The time
period in which nodes 0 and 2 detect the collision and resolve
the channel contention could be long. Unless node 3 defers
its transmission during this entire period, nodes 0 and 2 are
likely to lose the channel access to node 3. However, how can
node 3 know that collision occurred between high priority
nodes 0 and 2? Similarly, how can node 3 know that the
contention between nodes 0 and 2 has been resolved and
both of them have finished the transmissions of backlogged
high priority packets?
In multi-hop networks, under severe contention amongst
high priority flows it is a challenge to ensure their priority
over low priority flows. The major di#culty is that every
node can only sense its local channel status. In the example
above, even if nodes 0 and 2 are experiencing continuous
collisions, node 3 still may sense its channel as free and start
its transmission.
The scheme proposed in this paper solves this problem as
follows. During the procedure of channel access of nodes
0 and 2, they will send BT1 signal every M slots until the
packet is sent on the data channel, where M is a parameter
to be set as mentioned earlier. Node 1 will send BT2 after
sensing BT1. If the transmissions of nodes 0 and 2 collide
at node 1, they will detect the collision after some duration,
which is called "CTS-Timeout" in the case of IEEE 802.11
DCF using RTS/CTS handshake. After the collision is de-
tected, the channel access procedure will start once again,
during which BT1 and BT2 will again be sent periodically.
We require low priority source nodes that sense BT1 or BT2
signal to defer their transmissions for the "CTS-Timeout"
duration. This ensures channel access of high priority packets
as elaborated in Section 4.
4. PROPOSED BUSY TONE PRIORITY
The scheme proposed in this paper is a contention based
protocol. The proposed scheme makes use of two busy tone
signals, and borrows some mechanisms from IEEE 802.11
DCF. The proposed protocol is called "Busy Tone Priority
Scheduling(BTPS)". We now describe the protocol, followed
by an example in Figure 5.
4.1 Channel Requirement
In the proposed BTPS scheme, two narrow-band busy
tone signals named BT1 and BT2 are used. Reference [8]
previously proposed the use of two busy tone signals to provide
higher network utilization. The work in [8] has a different
objective and di#erent mechanism compared to the
priority scheduling protocol proposed in this paper.
Low priority source stations determine the presence of
high priority packets by sensing the carrier on the busy-tone
channel. According to [5], the time period of 5-s is su#cient
for the busy tone signal to be detected if 1% of total channel
frequency spectrum 2 is assigned to each busy tone channel
(including guard band). To ensure adequate spectral separation
between two busy tone channels, they can be put
at the two ends of the channel spectrum as Figure 4 shows.
Now, the total available channel bandwidth is divided into
three parts: BT1 channel, Data channel and BT2 channel,
with respective bandwidth percentage of 1%, 98%, and 1%.
The resulting data channel has a bit rate of 1.96 Mbps.
Channel BT2 Channel
Data Channel (98% bandwidth)

Figure

4: Channel Spectrum Division
2 The channel frequency spectrum is 22 MHz with IEEE
In general, it is hard to require a node to have the capability
of receiving while it is transmitting, or transmitting
to more than one channel at the same time. The proposed
BTPS protocol only requires that stations be able to monitor
the carrier status of the data channel as well as two
busy tone channels while the station is idle and lock onto
the signal on the data channel as desired. Here, a station is
defined to be idle when it is not transmitting to any channel,
and it is not receiving a packet from the data channel. Since
we only need to detect the existence of busy tone without
it should not be di#cult for a station to have such
capabilities. Once stations begin to receive from or transmit
to the data channel, the status of busy tone channel can be
ignored. The busy tone channel's sensing threshold is set
the same as data channel's sensing threshold.
4.2 Channel Access Procedure with the use of
dual busy tone
In BTPS, busy tone serves as the indication of backlogged
high priority packets. All packets are transmitted on the
data channel. Each dialog begins with RTS/CTS hand-
shake, followed by the transmissions of Data/ACK packets.
As in IEEE 802.11, each station, before accessing the
channel, needs to wait for the channel to be idle for the
period of "interframe space (IFS)", then enter the backo#
stage. The length of backo# interval is randomly chosen between
zero and the value of "Contention Window". When
collision occurs, the "Contention Window" will be exponentially
increased by the factor of 2. Stations will freeze their
backo# timers once they sense data channel is busy. At
the end of backo# stage, stations are allowed to acquire the
channel. Time is slotted and each unit is called one Slot-
Time.
The di#erence between IEEE 802.11 Distributed Coordination
Function (DCF) and BTPS is that high priority and
low priority source stations behave di#erently during "IFS"
and "backo# " stages in BTPS.
. High Priority Source Stations: The DIFS is used as the
interframe space for high priority source stations. During
DIFS and backo# stages, the high priority source
stations send a BT1 pulse (5-s duration) every M slots.
Between two consecutive busy tone pulse transmis-
sions, there should be at least one Slot-Time interval
so that these stations have a chance to listen to data
Therefore, M could be any value that is larger
than 2, depending on the choice of IFS for low priority
source stations. The principle is that the IFS of low
priority stations should be larger than M slots, so that
they can always sense the busy tones before they attempt
to acquire the channel. In our implementation,
M is set to 3.
. Stations that sense BT1: High priority source stations
will disregard BT1. Any other station that senses a
will send a BT2 pulse (5-s duration) if it is not
receiving a packet from the data channel. It will also
defer its transmission of a low priority packet. Specif-
ically, RTS for a low priority packet is deferred for
"CTS-Timeout" duration after receipt of a BT1. Special
attention also needs to be paid to the transmission
interval of BT2. Between two consecutive BT2 pulses,
there should be at least one Slot-Time interval to make
sure that the stations, which transmit BT2 after sensing
BT1, have a chance to receive packet from data
channel. That is, a station will send BT2 pulse at
most once every two slots.
. Stations that sense BT2: High priority source stations
will disregard BT2. Any other station that senses a
will defer its RTS for a low priority packet for
"CTS-Timeout" duration.
. Low priority source stations: DIFS plus one Slot-Time
is used as the "interframe space" for low priority source
stations. In the case of IEEE 802.11 DSSS [6], DIFS
lasts for two and half Slot-Time. Since busy tone will
be initiated every three slots by high priority stations,
low priority source nodes that wait for at least three
and half Slot-Time will sense the busy tone and defer
their transmissions.
4.3 Occupancy of Data Channel using black
burst
During the channel access procedure described above, a
station may transmit BT1 or BT2. However, the same station
could be the receiver of a high priority packet for which
an RTS may be transmitted while it is sending BT1 or BT2.
Since a station cannot receive while it is transmitting, the
high priority packet intended for this station will be missed
during its busy tone transmission. The scenario in Figure 3
can be used to illustrate the situation. After sensing BT1
from node 0, node 1 will send BT2 correspondingly. But
when node 1 is transmitting BT2, node 2, another high priority
source node, could possibly be sending RTS to node
1 on the data channel. Without taking care of such a situ-
ation, node 1 will miss the high priority packet from node
2.
Taking into account several factors including data channel
carrier detection time, turnaround time of stations from
receiving mode to transmitting mode as well as the transmission
time of BT2, BTPS requires that each high priority
source station send a two slot duration of "black burst" before
the transmission of RTS packet on data channel. The
"black burst" is used to occupy the channel. With "black
burst" ahead of useful data, the receivers will either detect
that data channel is busy before turning to transmit busy
tone, or be able to correctly receive packet from data channel
after the transmission of a busy tone.
Now, back to our example. After the transmission of BT2,
node 1 will sense the carrier on data channel and begin to
receive the signal. Because of the two slot duration of "black
burst" ahead of RTS packet, node 1 can still receive the RTS
packet correctly from node 2.
There is no need to add "black burst" before CTS, Data
or ACK packets.
4.4 Summary of BTPS protocol
The behavior of the BTPS protocol is summarized in Figure
5. The high priority source station in Figure 5(a) will
send BT1 every 3 slots during DIFS and backo# stage. Once
the backo# counter is counted down to zero and the channel
is idle, a "black burst" which lasts two Slot-Time long will
be sent first, followed by a RTS packet. After getting a CTS
reply, the data packet will be sent, followed by the reception
of an ACK. From the point of sending "black burst" to
the time of receiving the ACK, no busy tone signal will be
transmitted. Any other station that senses BT1, as shown
Station that sense BT1:
DIFS Backoff Stage black
burst
(a) .
Data
Note: RTS, CTS, Data and ACK are not represented
in their actual lengths due to space limitation.
s
Turnaround time from receiving to transmitting
(b)
The arrows indicate sensed BT1. After BT1 is sensed, transmission
High priority source station:
(c)
The arrows indicate sensed BT2. After BT2 is sensed, transmission
Busy Medium
Station that sense BT2:
of a low piroirty packet is deferred for CTS-Timeout duration (355
of a low piroirty packet is deferred for CTS-Timeout duration (355

Figure

5: Behavior of BTPS protocol. One Slot-time is 20-s. The duration between consecutive ticks,
shown as short bars in the figure, is 10-s. Black boxes represent received signal, and white boxes represent
transmitted signal. Figure (a) shows the behavior of a high priority source station which has a packet
backlogged. Figure (b) shows behavior of stations that sense BT1, while figure (c) shows behavior of stations
that sense BT2.
in

Figure

5(b), will transmit BT2 provided that it is not
receiving from data channel. Each time when stations sense
busy tone (BT1 or BT2), the transmissions of low priority
packets will be deferred for "CTS-Timeout" duration, which
is shown in Figure 5(b) and Figure 5(c).
5. PERFORMANCE EVALUATION
In this section, simulation results are presented to demonstrate
the e#ectiveness of the proposed BTPS protocol. The
simulation results for PMAC [7] are also shown for com-
parison. Recall that PMAC is a modified version of IEEE
802.11 DCF, which chooses IFS for low and high priority
flows di#erently to attempt to achieve priority scheduling.
As we mentioned earlier, Cwh is a critical parameter for
PMAC, and it is di#cult to adapt this parameter to dynamic
network situations. However, in the simulation, being
aware of the number of high priority flows and tra#c load,
we try to choose a suitable value to demonstrate a reason-able
performance for PMAC. In some scenarios, results of
IEEE 802.11 DCF are also presented to show the baseline.
The performance metrics we use include "Delivery Ratio of
High Priority Packets", which is the ratio of high priority
flows' throughput over their sending rate; and "Aggregate
Throughput", which is the aggregate throughput of all high
and low priority flows. For PMAC [7], a higher value of Cwh
improves the first metric; but degrades aggregate through-
put, and vice versa. Our scheme can improve on PMAC
with respect to both metrics.
5.1 Simulation Model
All the simulation results are based on a modified version
of ns-2 network simulator from USC/ISI/LBNL [13],
with wireless extensions from the CMU Monarch project
[12]. The extensions provide a wireless protocol stack including
IEEE 802.11. The radio interface model approximates
the first generation WaveLan radio interface with 2
Mbps bit rate and 250 meter transmission range using omnidirectional
antenna. The tra#c sources are chosen to be
constant bit rate (CBR) sources using packet size of 512
bytes. Cwh for PMAC is set to 32 slots. The simulation
results are averages over runs, and each simulation run
is for 6 second duration.
Since our objective is to demonstrate MAC protocol's performance
to deliver high priority packets, mobile situations
are not simulated here. However, the behavior of BTPS
protocol itself will not be impacted by mobility.
5.2 Scenario 1
In this scenario, 24 nodes are arranged in a 4-6 grid with
a grid spacing of 200 meters. The flow pattern is as shown
in

Figure

6. Figure 7 plots the flows' conflict graph. The
conflict graph is defined as G=(V, E), in which V is the set
of all flows, and an edge (f i , f j ) belongs to E if and only if
Number of high
priority flows High priority flow ID1 flow 4
3 flow 4, 5, 6
4 flow 4, 5, 6, 8
5 flow 4, 5, 6, 7, 8
6 flow 4, 5, 6, 7, 8, 9

Table

1: The high priority flows in scenario 1
flows f i and f j conflict with each other (i.e., they cannot
simultaneously). Among all flows, flows 5 and 8
have the highest contention degree, while flows 1, 3, 10, 12
have the lowest contention degree.
flow4 flow5 flow6
200m
200m

Figure

Network topology of scenario 1
flow 1
flow 4
flow 7
flow
flow 3
flow 2
flow 5
flow 8
flow 11
flow 6
flow 9
flow 12

Figure

7: Conflict graph for flows in scenario 1
The number of high priority flows is increased from 0 to
6 in our simulations. The corresponding high priority flows
for each case are given in Table 1. The tra#c sending rate
for each high priority flow in each case is 180 Kbps, while
all remaining low priority flows have aggressive sending rate
of 1500 Kbps.

Figure

8 plots the delivery ratio of high priority packets
versus the number of high priority flows. The proposed
BTPS protocol can deliver most of the high priority packets
in each case, while the delivery ratio of PMAC [7] begins
to drop when the number of high priority flows is 3. When
there are six high priority flows, the performance gap between
BTPS and PMAC in terms of high priority packets'
delivery ratio is 12.6%. Because IEEE 802.11 DCF does not
provide di#erentiated service and the high priority flows simulated
have higher contention degree, IEEE 802.11 delivers
very few high priority packets.0.10.30.50.70.90 1
Delivery
of
High
Priority
Flows
Number of high priority flows
BTPS

Figure

8: Delivery ratio of high priority pack-
ets, comparison between BTPS, PMAC and IEEE
Figure

9 presents the aggregate throughput for BTPS,
PMAC and IEEE 802.11. When all flows are low priority
(i.e., number of high priority flows is 0), the aggregate
throughput achieved by PMAC is only 83.4% of that
achieved by IEEE 802.11. In PMAC, for each packet's trans-
mission, the waiting time of low priority source nodes in
"interframe space" stage is slots more than the
corresponding waiting time in IEEE 802.11. This causes
the 16.6% loss of aggregate throughput. Furthermore, the
larger the value of Cwh, the more is the loss in aggregate
throughput. If we reduce the value of Cwh, the throughput
loss can be smaller, but the deliver ratio for high priority
packets would be worse. On the other hand, the aggregate
throughput achieved by BTPS is 97.4% of that achieved by
802.11. The loss of throughput is mainly caused by the 2%
bandwidth given to busy tone channels in BTPS.
When there are high priority flows, IEEE 802.11 schedules
a di#erent set of flows compared to priority scheduling
protocols BTPS and PMAC, hence achieves much more
throughput at the cost of starving high priority flows. The
situation is elaborated below.
For the scenario with six high priority flows, we plot each
individual flow's throughput for BTPS, PMAC and IEEE
802.11 DCF in

Figure

10. The highest throughput in this
situation can be achieved by scheduling flows 1, 3, 10, and
12 at all times since they have the lowest contention degree
and most aggressive sending rate. However, this maximum
throughput is achieved at the cost of starving other flows,
particularly, the high priority flows 4, 5, 6, 7, 8 and 9. From
the results shown in Figure 10, IEEE 802.11 DCF performs
in this way and achieves the highest aggregate throughput
of 4820 Kbps 3 . On the other hand, BTPS and PMAC give
channel access preference to high priority flows, but at the
cost of decreased aggregate throughput. BTPS achieves aggregate
throughput of 2645 Kbps and PMAC achieves 2311
3 Recall that our proposed scheme can achieve the aggregate
throughput comparable to IEEE 802.11 when there are no
high priority flows.
Aggregate
Throughput
(Kbps)
Number of high priority flows
BTPS

Figure

9: Aggregate throughput comparison between
BTPS, PMAC and IEEE 802.11
Kbps. The reason why both BTPS and PMAC lose through-put
in comparison with IEEE 802.11 is because high priority
flows have higher contention degree in the simulated sce-
nario. As shown in Figure 7, for example, when flow 4 is
transmitting on the data channel, flows 1, 5, 7 cannot be
scheduled. Similarly, when flow 5 is transmitting, flows 2,
4, 6, 8 cannot use the channel either.
Note the two high priority flows (flows 5 and 8) with the
highest contention degree. PMAC just delivers 61% of packets
for flow 5, and 57.3% for flow 8 compared to proposed
BTPS. PMAC is unable to deliver many high priority packets
due to contention among the high priority flows. With
PMAC, the problem illustrated in section 3.2 occurs often,
resulting in low priority tra#c gaining channel access instead
of high priority tra#c. Thus, PMAC [7] delivers more
low priority packets from flows 2 and 11 but fewer high priority
packets from flows 5 and 8 than the proposed BTPS
protocol.20060010001400
Flow ID
Throughput
of
each
flow
(Kbps)
BTPS
high priority flows

Figure

10: Throughput of each flow in scenario 1
with six high priority flows
5.3 Scenario 2: Random Topology
We generate eight random topologies in a 1000m-1000m
area. The total number of nodes in this area is increased
Num. of nodes Total num. of flows Num. of high
priority flows
50 43 22

Table

2: The number of high priority flows in random
topologies
from 10 to 80 with a step size of 10, and flows are randomly
chosen between two nodes which are one hop away. Among
all flows, half are high priority flows with sending rate of
120 Kbps, the remaining low priority flows have aggressive
sending rate of 1500 Kbps. Table 2 shows the number of
high priority flows for each simulated topology.
The delivery ratio of high priority packets is shown in

Figure

11, from which we can see that BTPS delivers more
high priority packets than PMAC in most cases. Only when
there are only 10 or 20 nodes and the corresponding numbers
of high priority flows are 4 or 7 respectively, does PMAC
deliver as many high priority packets as BTPS. In the case
of 80 nodes, the delivery ratio di#erence between BTPS and
PMAC reaches 20.5%. The simulation results demonstrate
that severe contention among high priority flows will cause
significant performance degradation with PMAC.0.40.60.81
Delivery
of
High
Priority
Flows
Number of nodes
BTPS

Figure

Delivery ratio of high priority packets in
random scenarios, comparison between BTPS and

Figure

12 presents the aggregate throughput comparison
between BTPS and PMAC for the generated random sce-
narios. With an increase in the number of flows in the
1000m-1000m area, the contention degree for each flow
tends to become higher. BTPS ensures high priority pack-
ets' delivery first, then low priority packets use as much
bandwidth as possible after satisfying requirements of the
high priority flows. On the other hand, PMAC lacks the
capability to resolve contention among high priority flows
e#ciently under situations with high degree of contention;
also the low priority packets cannot make full use of available
bandwidth due to larger "interframe space" duration. For
these reasons, it is not surprising that the proposed BTPS
protocol provides higher aggregate throughput than PMAC
[7]. In the case of 80 nodes, BTPS gains 51.5% aggregate
throughput over PMAC.12001600200024002800
Aggregate
Throughput
(Kbps)
Number of nodes
BTPS

Figure

12: Aggregate throughput comparison between
BTPS and PMAC in random scenarios
6. CONCLUSION
We present a priority scheduling MAC protocol (BTPS)
for ad hoc networks. With the use of two narrow-band busy
tone signals, BTPS ensures channel access of high priority
packets. Furthermore, in the absence of high priority
packets, low priority flows can make full use of available
bandwidth in BTPS. Simulation results demonstrate the effectiveness
of BTPS protocol with respect to "delivery ratio
of high priority packets" and "aggregate throughput".
7.



--R



A Priority Scheme for IEEE 802.11 DCF Access Method.
Radio Equipment and Systems(RES)
Packet Switching in Radio Channels: Part II- The Hidden Terminal Problem in Carrier Sense Multiple-Access and the Busy-Tone Solution


Dual busy tone multiple access(DBTMA): A new medium access control for packet radio networks.


Distributed Control Algorithms for Service Di
The CMU Monarch Project.
VINT Group.

--TR
An efficient packet sensing MAC protocol for wireless networks
Real-time support in multihop wireless networks
Distributed multi-hop scheduling and medium access with delay and throughput constraints

--CTR
Xue Yang , Nitin Vaidya, Priority scheduling in wireless ad hoc networks, Wireless Networks, v.12 n.3, p.273-286, May 2006
Yang Xiao , Yi Pan, Differentiation, QoS Guarantee, and Optimization for Real-Time Traffic over One-Hop Ad Hoc Networks, IEEE Transactions on Parallel and Distributed Systems, v.16 n.6, p.538-549, June 2005
Marco Caccamo , Lynn Y. Zhang, The capacity of an implicit prioritized access protocol in wireless sensor networks, Journal of Embedded Computing, v.1 n.2, p.195-207, April 2005
Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA
Luciano Bononi , Luca Budriesi , Danilo Blasi , Vincenzo Cacace , Luca Casone , Salvatore Rotolo, A differentiated distributed coordination function MAC protocol for cluster-based wireless ad hoc networks, Proceedings of the 1st ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 04-04, 2004, Venezia, Italy
Ming Li , B. Prabhakaran, MAC Layer admission control and priority re-allocation for handling QoS guarantees in non-cooperative wireless LANs, Mobile Networks and Applications, v.10 n.6, p.947-959, December 2005
Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Wireless Networks, v.11 n.4, p.471-487, July 2005
J. Jobin , Michalis Faloutsos , Satish K. Tripathi, The case for a systematic approach to wireless mobile network simulation, Journal of High Speed Networks, v.14 n.3, p.243-262, July 2005
Thomas Kunz, Multicasting in mobile ad-hoc networks: achieving high packet delivery ratios, Proceedings of the conference of the Centre for Advanced Studies on Collaborative research, p.156-170, October 06-09, 2003, Toronto, Ontario, Canada
Luciano Bononi , Marco Di Felice , Lorenzo Donatiello , Danilo Blasi , Vincenzo Cacace , Luca Casone , Salvatore Rotolo, Design and performance evaluation of cross layered MAC and clustering solutions for wireless ad hoc networks, Performance Evaluation, v.63 n.11, p.1051-1073, November 2006
ad hoc network;busy tone;medium access control;priority scheduling