A Cross-layer MAC Mechanism to Solve Performance Anomaly in MANET - SEMINAR
1. Introduction
Mobile
networking is one of the most important technologies supporting pervasive
computing. During the last decade, advances in both hardware and software
techniques have resulted in mobile hosts and wireless networking common and
miscellaneous. Generally there are two distinct approaches for enabling
wireless mobile units to communicate with each other:
1)
Infrastructured:
Wireless mobile networks have traditionally been based on the cellular concept
and relied on good infrastructure support, in which mobile devices communicate
with access points like base stations connected to the fixed network
infrastructure. Typical examples of this kind of wireless networks are GSM,
UMTS, WLL, WLAN, etc.
2) Infrastructureless: As to infrastructureless
approach, the mobile wireless network is commonly known as a mobile ad hoc
network (MANET). A MANET is a collection of wireless nodes that can dynamically
form a network to exchange information without using any pre-existing fixed
network infrastructure. This is a very important part of communication
technology that supports truly pervasive computing, because in many contexts
information exchange between mobile units cannot rely on any fixed network
infrastructure, but on rapid configuration of a wireless connections
on-the-fly. Wireless ad hoc networks themselves are an independent, wide area
of research and applications.
1.1 MANET Concept
A
mobile ad hoc network is a collection of wireless nodes that can dynamically be
set up anywhere and anytime without using any pre-existing network
infrastructure. It is an autonomous system in which mobile hosts connected by
wireless links are free to move randomly and often act as routers at the same
time. The traffic types in ad hoc networks are quite different from those in an
infrastructured wireless network , including:
1)
Peer-to-Peer: Communication between two nodes
which are within one hop. Network traffic (Bps) is usually consistent.
2)
Remote-to-Remote: Communication between two nodes beyond a single hop but which maintain a
stable route between them. This may be the result of several nodes staying
within communication range of each other in a single area or possibly moving as
a group. The traffic is similar to standard network traffic.
3)
Dynamic Traffic. This occurs when nodes are
dynamic and moving around. Routes must be reconstructed. This results in a poor
connectivity and network activity in short bursts.
1.2 MANET Features:
1)
Autonomous terminal: In
MANET, each mobile terminal is an autonomous node, which may function as both a
host and a router. In other words, besides the basic processing ability as a
host, the mobile nodes can also perform switching functions as a router. So
usually endpoints and switches are indistinguishable in MANET.
2)
Distributed operation: Since
there is no background network for the central control of the network
operations, the control and management of the network is distributed among the
terminals. The nodes involved in a MANET should collaborate amongst themselves
and each node acts as a relay as needed, to implement functions e.g. security
and routing.
3)
Multihop routing: Basic types of ad hoc routing
algorithms can be single-hop and multihop, based on different link layer
attributes and routing protocols. Single-hop MANET is simpler than multihop in
terms of structure and implementation, with the cost of lesser functionality
and applicability. When delivering data packets from a source to its
destination out of the direct wireless transmission range, the packets should
be forwarded via one or more intermediate nodes.
4)
Dynamic network topology: Since the
nodes are mobile, the network topology may change rapidly and unpredictably and
the connectivity among the terminals may vary with time. MANET should adapt to
the traffic and propagation conditions as well as the mobility patterns of the
mobile network nodes. The mobile nodes in the network dynamically establish
routing among themselves as they move about, forming their own network on the
fly. Moreover,a user in the MANET may not only operate within the ad hoc
network, but may require access to a public fixed network.
1.3.
MANET Challenges
1)
Routing. Since the topology of the
network is constantly changing, the issue of routing packets between any pair
of nodes becomes a challenging task. Multicast routing is another challenge
because the multicast tree is no longer static due to the random movement of
nodes within the network. Routes between nodes may potentially contain multiple
hops, which is more complex than the single hop communication.
2)
Security and Reliability: wireless
connection, an ad hoc network has its particular security problems due to the
feature of distributed operation requires different schemes of authentication
and key management. Further, wireless link characteristics introduce also
reliability problems, because of the limited wireless transmission range, the
broadcast nature of the wireless medium mobility-induced packet losses and data
transmission errors.
3)
Quality of Service (QoS): Providing different quality of service levels in a
constantly changing environment will be a challenge. The inherent stochastic
feature of communications quality in a MANET makes it difficult to offer fixed
guarantees on the services offered to a device. An adaptive QoS must be
implemented over the traditional resource reservation to support the multimedia
services.
4)
Internetworking. In addition to the communication
within an ad hoc network, internetworking between MANET and fixed networks
(mainly IP based) is often expected in many cases. The coexistence of routing
protocols in such a mobile device is a challenge for the harmonious mobility
management.
1.4 MANET
Applications
1)
Military battlefield: Military
equipment now routinely contains some sort of computer equipment. Ad hoc
networking would allow the military to take advantage of commonplace network
technology to maintain an information network between the soldiers, vehicles,
and military information head quarters. The basic techniques of ad hoc network
came from this field.
2)
Commercial sector. Ad hoc can be used in
emergency/rescue operations for disaster relief efforts, e.g. in fire, flood,
or earthquake. Emergency rescue operations must take place where non-existing
or damaged communications infrastructure and rapid deployment of a
communication network is needed. Information is relayed from one rescue team
member to another over a small handheld. Other commercial scenarios include
e.g. ship-to-ship ad hoc mobile communication, law enforcement.
3)
Local level. Ad hoc networks can autonomously
link an instant and temporary multimedia network using notebook computers or
palmtop computers to spread and share information among participants at a e.g.
conference or classroom. Another appropriate local level application might be
in home networks where devices can communicate directly to exchange information.
Similarly in other civilian environments like taxicab, sports stadium, boat and
small aircraft, mobile ad hoc communications will have many applications.
4)
Personal Area Network (PAN). Short-range MANET can simplify the
intercommunication between various mobile devices (such as a PDA, a laptop, and
a cellular phone). Such an ad hoc network can also extend the access to the
Internet or other networks by mechanisms e.g. Wireless LAN (WLAN), GPRS, and
UMTS. The PAN is potentially a promising application field of MANET.
2. Literature survey
“A Rate
Adaptive MAC Protocol for Multi hop Wireless Networks”
G.Holland ,
N.Vaidya
RBAR
(Receiver Based Auto Rate), as one of the most popular multi-rate MAC
protocols, was proposed by Gaven. The novelty of RBAR is that its rate
adaptation mechanism is in the receiver instead of the sender. Compared with
its poor channel quality estimation and the dependence on RTS/CTS packet, more
problems of RBAR came from performance anomaly.
Distributed Coordination Function (DCF)
The Distributed Coordination
Function (DCF) in 802.11 is an implementation of the RTS/CTS protocol, and is
Since node A is in range of Src, it
overhears the RTS and summarily defers its own transmissions for the duration
of the reservation in the RTS (DRTS), starting from the mo- ment that it
received the RTS (T1). If Dst is capable of receiving the data packet, it
responds by transmitting a CTS packet back to Src containing the time remaining
in the reservation (DCTS), which it calculates by subtracting the transmission
time of the CTS from DRTS. Node B, overhearing the RTS, learns of the requested
reservation and, like A, defers for length DCTS.
At this point, transmission of the
data packet and subsequent ACK can now proceed without interference from A or
B. However, in the off-chance that A did not receive the RTS, due to, for
example, an RTS collision caused by another node, the data packet also carries
the time remaining in the reservation Ddata to ensure that A defers during the
transmission of the ACK.
Figure 4: Timeline showing the RTS/CTS protocol in the IEEE 802.11
Distributed Coordination Function (DCF) for transmitting a data packet.
Network Allocation Vector (NAV)
Since a node may overhear many
different, potentially overlapping, reservation requests, it needs a means by
which it can efficiently manage them. This is the purpose for the maintenance
of a structure called the Network Allocation Vector (NAV). The NAV is a data
structure that stores the aggregate duration of time that the medium is
presumed to be “busy" based on the reservation requests that have been
received. Maintenance of the NAV is straightforward, since reservations are not
allowed to change. Thus, nodes that overhear a reservation request are free to
update their NAVs without regard to any further communication, such as if the
reservation was actually granted by the receiver.
THE RECEIVER-BASED AUTO RATE (RBAR) PROTOCOL
The core idea of RBAR is to allow
the receiver to select the appropriate rate for the data packet during the
RTS/CTS packet exchange. Advantages to this approach include:
- Both channel quality estimation
and rate selection mechanisms are now on the receiver. This allows the
channel quality estimation mechanism to directly access all of the
information made available to it by the receiving hardware (such as the
number of multipath components, the symbol error rate, the received signal
strength, etc.), for more accurate rate selection.
- Since the rate selection is
done during the RTS/CTS exchange, the channel quality estimates are nearer
to the actual transmission time of the data packet than in existing
sender-based approaches, such as the protocol in which attempts to predict
channel conditions based on conditions experienced during previous data packet
transmissions.
- It can be implemented into
IEEE 802.11 with minor changes, as we will show in a later section.
In the remainder of this section, we
present the RBAR protocol in more detail. Note that although our discussion is in
the context of the RTS/CTS protocol in the DCF of the 802.11 standard, the
concepts are equally applicable to other RTS/CTS based protocols such as SRMA,
MACA, MACAW, and FAMA.
In RBAR, instead of carrying the
duration of the reservation, the packets carry the modulation rate and size of
the data packet. This modification serves the dual purpose of providing a
mechanism by which the receiver can communicate the chosen rate to the sender,
while still providing neighboring nodes with enough information to calculate
the duration of the requested reservation. The protocol is as follows
The sender Src chooses a data rate
based on some heuristic (such as the most recent rate that was successful for
transmission to the destination Dst), and then stores the rate and the size of
the data packet into the RTS. Node A, overhearing the RTS, calculates the
duration of the requested reservation DRTS using the rate and packet size
carried in the RTS.
“Performance Anomaly of 802.11b”
M.Heusse,Franck
Rousseau,Gilles Berger-Sabbatel and A.Duda
The IEEE 802.11b standard defines
two access methods: the Distributed Coordination Function (DCF) that uses
CSMA/CA to allow for contended access to the wireless media and the Point
Coordination Function (PCF) providing uncontended access via arbitration by a
Point Coordinator, which resides in the Access Point. The DCF method provides a
best effort type of service whereas the PCF guarantees a time-bounded service. The
DCF access method is based on the CSMA/CA principle, in which a host wishing to
transmit senses the channel, waits for a period of time (DIFS – Distributed
Inter Frame Space) and then transmits if the medium is still free. If the
packet is correctly received, the receiving host sends an ACK frame after
another fixed period of time (SIFS – Short Inter Frame Space). If this ACK
frame is not received by the sending host, a collision is assumed to have
occurred. The sending host attempts to send the packet again when the channel
is free for a DIFS period augmented of a random amount of time.
Let first consider that a single
host in a 802.11b cell transmits a single data frame. If we neglect propagation
times, the overall transmission time is composed of the transmission time and a
constant overhead:
T
= ttr + tov (1)
Where the
constant overhead
tov = DIFS + tpr + SIFS + tpr + tack
Is composed of the PLCP (Physical
Layer Convergence Protocol) preamble and header transmission time tpr, SIFS = 10 μs, tack is the MAC acknowledgment
transmission time (10 μs if the
selected rate is 11 Mb/s, as the ACK length is 112 bits), and DIFS = 50 μs. ttr is the
frame transmission time . tpr
varies according to the bit rate used by the host. When it transmits at 1 Mb/s,
the long PLCP header is used and tpr
= 192 μs. If it uses 2, 5.5 or
11 Mb/s, then tpr = 96 μs (short PLCP header). For bit rates
greater than 1Mb/s and the frame size of 1500 bytes of data (MPDU of total 1534
bytes), proportion p of the
useful throughput measured above the MAC layer will be:
So, a single host sending long frames over an
11 Mb/s radio channel will have a maximum useful throughput of 7.74 Mb/s. If
there are multiple hosts attempting to transmit, the channel may be sensed busy
and hosts enter a collision avoidance phase: a host executes the exponential
backoff algorithm it waits for a random interval distributed uniformly between [0, CW] × SLOT. The congestion window CW varies between CWmin
= 31 and CWmax = 1023, the
value of SLOT is 20 μs (these parameters are for
802.11b). The host that chooses the smallest interval starts transmitting and
the others hold counting down until the transmission is over. Each time a host
happens to collide, it doubles CW up
to CWmax. In the case of a
single host that tries to transmit a sustained traffic (the host has always a
packet to send), the carrier sense applies also to the host’s own
transmissions, so that it inserts a random interval between each transmission.
“Performance
analysis of IEEE 802.11 Multi rate WLANs: Time Based Fairness Vs Throughput
Based Fairness”
A.V.Babu and
Lillykutty Jacob
In
time-based fairness, each node receives an equal share of the wireless channel
occupancy time. It is demonstrated in that the time-based fairness can achieve
higher aggregate throughput. Several solutions are proposed to solve
performance
Performance Analysis under Multi-rate Scenario
To
overcome unfairness of conventional CSMAICA in a multi rate scenario, we use
priority control according to the data rate of the stations. By selecting
appropriate priority depending on the data rate and giving more transmission
opportunity for high data rate station, the system capacity can be improved.
Consider a heterogeneous WLAN of nodes with two different rates, lower rate
corresponding to slow station and higher rate corresponding to fast station,
and assume that each station is in saturation, i.e., has always a frame ready
for transmission. Let there be ns slow stations and nf fast stations and let n=
n, + nf.
The
maximum back off stage, m, and the retry limit m, are assumed to be equal for
the two priority classes. Let Wij represents the contention window (CW) size in
the j-th retry/retransmission for rate-i station, je {O,l,...m}. For rate-i
station, contention window size in the j-th
retry/retransmission, Wij, and the retry limit, m, are related as
follows:
Let
si(t) and bi(t) be the stochastic processes representing the back off stage and
the back off time counter value, respectively, for rate-i traffic flow. We
assume that the frame collision process is Bernoulli which allows us to describe
the state of each station, slow or fast, with two dimensional DTMC {s1(t),
bj(t)} . The state transition occurs at the beginning of the next slot time, where
a transition can happen after a transmission or an empty slot time. Let pc,i
and pr,i , respectively, represent the frame collision probability and frame
transmission probability for rate-i station. From the DTMC the frame transmission
probability can be derived as follows. Let qi(j,k) = lim {P(si(t) = j,bi(t) =
k)}, j E (O,m), k E (O,Wi j -1) be the stationary distribution for the chain.
In steady state the following relations can be obtained:
Solutions for Performance Anomaly
It has been proven that
if there are two bit rates under the same channel conditions, the saturation
throughput of any station will be equal to the saturation throughput of station
with the lower data rate. To solve the throughput degradation occurring in a
multi rate environment, we propose two mechanisms: In the first method CW, n of
slow host is increased to decrease its transmission opportunity. In the second
method the frame size of slow station traffic is reduced to decrease its
transmission time for each transmission opportunity. Our objective is to make
the long term channel occupancy time of slow and fast stations equal.
As mentioned above,
this is done in one of the two ways: (i) by increasing the CWmin of the slow
stations, which causes the mean contention delay (E[Ds ] ) of slow station to
increase; (ii) by reducing the frame size of slow stations, which causes
successful transmission time (Ts,s) at each transmission opportunity to
decrease. Therefore, According to Little's law, for any queueing system, the
average number of customers in the system is equal to the average experienced
delay multiplied by the average customer departure rate. Because each of the n,
stations is contending with an HOL frame and Z,/E[L,] represents throughput in frames/seconds.
“Resolving
802.11 performance anomalies through Qos differentiation”
H.Kim, S.Yun, I.Kang, and S.Bahk
The idea of our
differentiation scheme is to set CWmin for each bit-rate inversely
proportional to the bit-rate. (Let l denote a bit-rate in the hierarchy,
which we call class. In this letter, we will use the example of 802.11b,
so there are 4 classes: 1 Mb/s, 2 Mb/s, 5.5 Mb/s, and 11 Mb/s. First, the
highest bit rate terminals in the bit-rate hierarchy (i.e., 11 Mb/s)
retain the current default value, i.e., CW(11) min = 32
(slots). Then CWmin of other bit-rate terminals is set to CW(x)
min = CW(11) min · 11/x , where x = 1, 2, or
5.5. We will prove that through this simple configuration we can precisely
create the throughput ratio corresponding to the bit-rate ratio. As a matter of
fact, the readers should now notice, any throughput ratio can be created
this way. For the ensuing analysis we make some simplifying assumptions as
follows.
- The
number of terminals in the system, N, is large.
- The
maximum contention window size, CWmax, can be set high.
- All nodes
are within the receive range of each other. This assumption excludes the
hidden terminal problem.
Although these
assumptions significantly simplify our analysis, they are not essential. In
fact, the simulation results that corroborate the analysis are obtained in
small N network.
The second assumption
is needed to ensure correct throughput ratio upon high contention, or
equivalently, large number of back off. Since the payload size is independent
of the nominal bit rate, the throughput ratio between different class terminals
becomes the inverse ratio of the transmission times T(l). (The
transmission time is what it takes until a class-l node to successfully
transmit a packet).
Where Rij is the throughput ratio and K is the packet size
in bits. so the packets are always transmitted in full size. To determine Rij
, we just need to compute T(l) for each class l. T(l)
is composed of several components:
1)
E[T(l)s ] : Packet transmission time of a class l
terminal. With maximal packet size assumption, E[T(l)s
] = T(l)s =K/l.
2)
E[T(l)c ]: Average time wasted on a mangled packet
transmission due to collision. It is a packet time, and does not contain the
backoff times due to the collision.
3)
E[T(l)i ] : Average idle time between transmission
attempts for a class l terminal. Since we assume that terminals are
backlogged, this idle time is due to the backoffs for collision avoidance.
4)
E[T(l)o ]: Time of channel occupation by the
terminals in classes other than l. In 802.11, when the terminal is
detected busy, the backoff timer for the terminal in backoff is suspended.
Therefore, this time is added to the total cost for the other terminals. Since
“channel busy” could mean either successful transmission or collision, the
possible collision time of other terminals is also accounted.
“Ad hoc on demand distance vector
(AODV) routing”
Perking C, Royer E B, and Das S
The Ad-hoc On-Demand Distance Vector Algorithm
The basic proposal can
be called a pure on-demand route acquisition system; nodes that do not lie on
active paths neither maintain any
routing information nor participate in any periodic routing table exchanges.
Further, a node does not have to discover and maintain a route to another node
until the two needs to communicate, unless the former node is offering its
services as an intermediate forwarding station to maintain connectivity between
two other nodes.
The algorithm's primary objectives are:
·
To broadcast discovery packets only when necessary
·
To
distinguish between local connectivity management (neighborhood detection) and
general topology maintenance
·
To disseminate information about changes in local
connectivity to those neighboring mobile nodes that are likely to need the
information.
AODV uses a broadcast route discovery mechanism.
Path Discovery
The Path Discovery
process is initiated whenever a source node needs to communicate with another
node for which it has no routing information in its table. Every node maintains
two separate counters: a node sequence number and a broadcast id. The source
node initiates path discovery by broadcasting a route request (RREQ) packet to
its neighbors. The RREQ contains the following fields:
< source addr; source sequence #; broadcast id;
dest addr; dest sequence #; hop cnt >
The pair < source
addr; broadcast id > uniquely identifies a RREQ. Broadcast id is incremented
whenever the source issues a new RREQ. Each neighbor either satisfies the RREQ
by sending a route reply (RREP) back to the source or rebroadcasts the RREQ to
its own neighbors after increasing the hop_cnt .
Reverse Path Setup
There are two sequence
numbers (in addition to the broadcast id) included in a RREQ: the source
sequence number and the last destination sequence number known to the source.
The source sequence number is used to maintain freshness information about the
reverse route to the source, and the destination sequence number specifies how
fresh a route to the destination must be before it can be accepted by the
source. To set up a reverse path, a node records the address of the neighbor
from which it received the first copy of the RREQ. These reverse path route
entries are maintained for at least enough time for the RREQ to traverse the
network and produce a reply to the sender.
Forward Path Setup
Eventually, a RREQ will
arrive at a node (possibly the destination itself) that possesses a current
route to the destination. If the RREQ's sequence number for the destination is
greater than that recorded by the intermediate node, the intermediate node must
not use its recorded route to respond to the RREQ. The intermediate node can
reply only when it has a route with a sequence number that is greater than or
equal to that contained in the RREQ. If it does have a current route to the
destination, and if the RREQ has not been processed previously, the node then
unicast a route reply packet (RREP) back to its neighbor from which it received
the RREQ. A RREP contains the following information:
< source addr; dest addr; dest sequence #;
hop cnt; lifetime >
By the time a broadcast
packet arrives at a node that can supply a route to the destination, a reverse
path has been established to the source of the RREQ. As the RREP travels back to
the source, each node along the path sets up a forward pointer to the node from
which the RREP came, updates its timeout information for route entries to the
source and destination, and records the latest destination sequence number for
the requested destination. A node receiving an RREP propagates the first RREP
for a given source node towards that source.
If it receives further
RREPs, it updates its routing information and propagates the RREP only if the
RREP contains either a greater destination sequence number than the previous
RREP or the same destination sequence number with a smaller hop count .
Route Table Management
In addition to the
source and destination sequence numbers, other useful information is also
stored in the route table entries, and is called the soft-state associated with
the entry. Associated with reverse path routing entries is a timer, called the
route request expiration timer. A mobile node maintains a route table entry for
each destination of interest. Each route table entry contains the following
information:
·
Destination
·
Next Hop
·
Number of hops (metric)
·
Sequence number for the destination
·
Active neighbors for this route
·
Expiration time for the route table entry
3. Problem definition
Traditional solutions
have some limitations when solving performance anomaly especially when dealing
with multi-hop networks because in MANETs data rates of competitive nodes can
not reflect the whole path’s rate information. We are now trying to apply the
mechanism in unsaturated conditions and investigate the impact of mobility.
4. Proposed Methodology
A)
Motivation
By introducing tiny
modification to the IEEE 802.11 standard, nodes with higher bit-rate could have
a more time share of channel than nodes with lower bit-rate.
Two issues have been ignored.
i) Competition in MANETs usually occurs between multi-hop paths. At the
intersection, the competition between different paths turns into a competition
between nodes.
Fig. 1 Competition between two paths
As shown in Fig.1,
Node0 sends data to Node2 (denoted by Path1) and Node3 sends data to Node4
(denoted by Path2). Node 1 is needed for both paths as a route node. Traditional
solutions make sure Node3 has absolute advantage to access the channel because
Node3 select a much higher data rate than its competitive node. However, data
rates can not reflect the whole information of two competitive paths. Although Node3
can take full advantage of the channel, congestion will occur on Path2 because
the next hop (Node1 to Node4) is a low-rate link. Meanwhile, the multi-rate
capability of Path1 has not been effectively utilized. In a multi-hop and
multi-rate path, the overall throughput of a multi-hop path depends on the hop
with the lowest throughput. In order to avoid unnecessary back-off, nodes on the
same path should be taken as a whole.
ii) Initial contention window adaptation, as one of the solutions to
solve performance anomaly, has some limitations, which come from the
inefficient back-off mechanism. The main idea of initial contention window adaptation
is adjusting CWmin according to equation (1):
(1)
IEEE 802.11 standards
support 1, 2, 5.5 and 11Mbps at the physical layer. As shown in Table , if two
competitive nodes in an 802.11b network have chosen 11Mbps and 1Mbps separately
as their data rate, as soon as collision happens, the high-rate node will
initialize its CWmin with 32 and the low-rate node will initialize its CWmin
with 352. This adjustment is necessary. On the other hand, when signal to noise
ratio of channel is low, both nodes will choose 1Mbps as their data rate and initialize
their CWmin with 352. Unnecessary back-off leads to a degradation of
performance in both aggregate throughput and end-to-end delay.
B. Rate selection scheme of RBAR
The rate selection of
proposed mechanism is based on RBAR and can be incorporated into IEEE 802.11b. RBAR
modifies the Duration field in RTS, CTS, DATA and ACK packets into Rate & Length
(R&L). The R&L field defines 4 bits for Rate and 12 bits for Length.
These changes will not conflict with the original definition in IEEE 802.11
standard. Moreover, the new R&L field can provide enough information for
overhearing nodes to find out their own correct NAV value.
The destination node
selects the appropriate data rate based on the received power of RTS packet and
stores the chosen rate and the size of the data packet into the CTS packet.
After receiving the CTS packet, the source node responds to the receipt of the
CTS by transmitting the data packet at the rate chosen by destination node. The
new R&L field can also provide enough information for the overhearing nodes
to update their NAV tables.
C. Proposed Protocol
In the proposed
mechanism, some other modifications are made based on RBAR.
Fig.2 Storage Structures
We use “link” to refer
to the point-to-point connections between two nodes through a wireless MAC,
whereas we use “path” to refer to the end-to-end connections between two nodes
through a routing protocol. As shown in Fig.2 (a), two new substructures are
introduced to store its neighbor nodes’ MAC address and data rate. As shown in
Fig.2 (b), a new structure, denoted by Path List, is introduced to store paths’
information. The first two substructures of Path List are used to store path’s
source node and destination node’s IP addresses. The Path Rate substructure is
used to record the reciprocal of the time that spent transmitting unit data
packet from path’s source node to the destination node. Path Rate, which can be
recognizes as the average data rate of the whole path, represents the whole
path’s data transmission capacity so nodes on the same path have the same Path
Rate. Competitive node’s competitive level (denoted by Path Level), which is
the ratio of its own Path Rate to the competitive node’s Path Rate, is stored
in Path Level substructure.
Format of RTS and CTS
remains unchanged because RTS and CTS packet play an important role such as
helping overhearing nodes to update their NAV tables or estimating channel’s
quality in RBAR. We use ACK packet and DATA packet for piggybacking messages
between the nodes.
Fig.3 Modified MAC layer frame format
As shown in Fig.3 (c),
we modify the Rate&Length field in DATA packet into Rate&Pathrate in
which the Path Rate subfield is used to piggyback the information stored in
node’s Path Rate substructure. As shown in Fig3 (d), we modify the
Rate&Length field in ACK packet into Rate&Pathlevel in which the Path
Level subfield is used to piggyback the information stored in nodes’ Path Level
substructure. In the following four sections, we give details of the proposed mechanism
that is backward compatible with the legacy 802.11 DCF and RBAR scheme.
(1)
Estimation of Path Rate
In order to acquire the
whole Path’s rate information, the proposed mechanism always keeps tracks of
two-hop neighbor’s state information. Similarly to most existing work node
listens to all ongoing RTS and CTS packets. Node measures the channel quality
between the sender or the receiver and itself by sensing the signal strength of
RTS or CTS, respectively. Therefore, node estimates the transmission rate used
to send data packet from itself to its neighbor node and stores them in its
Neighbor List. Source node of a path needs to get the rate information of the
whole path. The interactions between MAC and Routing layers are needed to
achieve this approach.
Fig.4 A illustrative Example of Estimating Path
Rate
Take AODV a widely used
ad-hoc routing protocol, as an example. We introduce a new subfield with the
name of LD in the RREP packet of AODV. LD, with the default value of 0, is used
to piggyback the information of Path Rate between nodes of the same path. After
a successful routing, destination node sends RREP to source node via route
nodes. After receiving RREP packet, node calculates the time spent transmitting
unit data packet from itself to destination node based on the information
stored in its Neighbor List and update the LD field of RREP. Only a source node
of the path can update its Path List based on the information piggyback by RREP
because only when receiving RREP, source node has acquired the whole path’s
rate information. Source node stores the path’s information in its Path List
which includes source node’s IP address, destination node’s IP address and the
reciprocal of LD.
Take a two-hop
transmission as an example. As shown in Fig.4, Node3 sends data to Node1 using
Node2 as a route node. After a successful routing, Node1 sends RREP to Node3
via Node2. After receiving RREP, Node2 updates RREP’s LD subfield from 0 to
0.091, which is the reciprocal of the data rate Node1 is using. After receiving
RREP, Node3, as the source node of the path, stores the corresponding value of
Path Rate, which is the reciprocal of LD, in its Path List.
(2)
Transmission of Path Rate
Path Rate is
piggybacked by the DATA packet of MAC layer to make sure all the nodes on this
path can get it. Before transmitting DATA packet, node searches its Path List
by source node and destination node’s addresses. If the path has been recorded,
the DATA packet’s Path Rate subfield will be set to the corresponding value
stored in Path Rate substructure. After receiving DATA packet, node searches
its Path List by source node and destination node’s addresses. If the path has
been recorded, node updates its Path List. Otherwise, add a new record in the
Path List.
(3)
Calculation of Path Level
When a node records
more than one path in its Path List, it means collision occurs here and the
node should calculate each path’s Path Level based on the Path Rate. Let N
denote the number of paths that a node has recorded and PR_i represent the Path
Rate of path_i. The Path level of path_ican be calculated by Equation (2).
Path Level, which is
the ratio of its own transmission rate to the average of its competitive paths’
transmission rates, represents a path’s competitive level. Path with higher
Path Level can provide higher data transmission capability.
(4)
Adjustment of CWmin
Before sending ACK
packet, node searches its Path List by addresses and sets Path Level subfield
of ACK packet to the value of corresponding Path Level. After receiving ACK
packet, node updates its Path List and adjusts its CWmin. By adjusting CWmin,
nodes on the path with higher Path Level have more opportunity to access the
channel. Adjusted CWmin can be calculated by Equation (3).
When there are no
competitions in the network, all the paths’ Path Level is set to be 1 based on
Equation (2), so we don’t adjust any nodes’ CWmin to make sure the proposed
mechanism can be compatible with 802.11 DCF and RBAR scheme.
Fig.5 Illustrative Example of Adjusting CWmin
Take the topology in
Fig.5 as an example. Node3 sends data to Node1 using Node2 as a route node
(denoted by Path2) while Node0 sends data to Node1 directly (denoted by Path1).
Suppose that both of the source nodes, Node3 and Node0, have acquired all the
information by the mechanism presented in Fig. 4 and have recorded the
information in their Path Lists. Path Rate (denoted by PR in Fig.5) is
piggybacked by DATA packet to make sure PR1 and PR2 can be acquired by Node1
and Node2. Collision happens between Path1 and Paht2 because Node1 records two
paths’ information. Node1 calculates Path1 and Path2’s Path Levels (denoted by
PL in Fig.5) based on Equation (2) and update its Path List. After receiving
ACK packet, Node0, Node2 and Node3 update their Path List according to PL which
is piggybacked by ACK packet and adjust their CWmin based on Equation (3). As
shown in Fig.5, Node0 adjusts its CWmin from 32 to 55 while the other nodes
keep their CWmin unchanged. This adjustment reflects the superiority and novelty
of the proposed mechanism. We compare the proposed mechanism with some other
approaches. RBAR [1] keeps all the nodes’ CWmin unchanged to make sure all the
nodes have the same opportunity to access the channel leading to performance
anomaly. Initial contention window adaption [5], which tries to solve
performance anomaly by adjusting CWmin according to Equation (1), adjusts
Node0’s CWmin from 32 to 352 and adjusts Node3’s CWmin from 32 to 176. This
adjustment will lead to unreasonable allocation of channel because of
unnecessary back-off. The proposed mechanism takes nodes on the same path as a
whole and adjusts CWmin according to paths’ competitive levels to make sure
nodes with a relatively higher competitive level have a higher opportunity to
access the channel.
5. CONCLUSION
Traditional solutions
have some limitations when solving performance anomaly especially when dealing
with multi-hop networks because in MANETs data rates of competitive nodes can
not reflect the whole path’s rate information. The interactions between MAC and
Routing layers are fully exploited to achieve higher performance. Source node
of a path uses RREP packet to acquire the whole paths’ rate information and
estimate the path’s data transmission capacity. When competition happens
between paths, the proposed mechanism can reallocate the channel by adjusting
competitive node’s CWmin based on each path’s Path Level. Simulation results
show that comparing with RBAR, the proposed mechanism can not only solve the
performance anomaly in multi-hop networks but also improve the overall
performance by avoiding unnecessary back-off. Some problems remain unsolved in
the proposed mechanism. We are now trying to apply the mechanism in unsaturated
conditions and investigate the impact of mobility.
REFERENCE
[1] G.Holland, N.Vaidya, “A
Rate-Adaptive MAC Protocol for Multi-Hop Wireless Networks,” Proceedings of
ACMMOBICOM '01,
[2] M.Heusse, F.Rousseau,
G.Berger-Sabbateland A.Duda,“Performance anomaly of 802.11b,” Proc.IEEE Int. Conf.
Comput. Commun. (INFOCOM), pp.836–843, Apr.2003.
[3] Tan, G., and GuRag, J.,
“Time-based Fairness Improves Performance in Multi-rate Wireless LANS,”
Proceedings of USENIX’04 ,
[4] A. V. Babu, and
Lillykutty Jacob, “Performance Analysis of IEEE 802.11 Multirate WLANs:Time
Based Fairness Vs Throughput Based Fairness,” Internaional Conference on
Wireless Networks, Communications and
[5] H.Kim, S.Yun, I.Kang,
and S.Bahk, “Resolving 802.11 performance anomalies through QoS
differentiation,” IEEE Commun. Lett., vol.9, no.7, pp.655–657, Jul.2005.
[6] Yoo, S., Choi, J., and
Hwan, J., “Eliminating the performance anomaly of 802.11b,” LNCS, 1055-1062,
2005.
[7] Sadeghi,B., Kanodia,V.,
Sabharwal,A., and Knightly,E., “Opportunistic Media Access for Multi-rate
Ad-Hoc Networks,” MOBICOM,2002:
[8] Yongho S., Jaewoo P, and
Yanghee C., “Multirate Aware Routing Protocol for Mobile Ad Hoc Networks,”
Proc.IEEE Vehicular Technology Conf., pp.22-25, Apr.2003.
[9] Hao Zhu, and Guohong
Cao, “rDCF: A Relay-Enabled Medium AccessControl Protocol for Wireless Ad Hoc
Networks ” IEEE Transations on Mobile Computing, Vol.5, NO.9, Sep.2006,
pp.1201-1214.
[10] Zeng W, Tan H, and Suda
T, “A Relay Based MAC Protocol to Support Multi-rate Feature in
Comments
Post a Comment