25-01-2013, 02:27 PM
Routing in Multi-hop Wireless Mesh Networks with Bandwidth Guarantees
[attachment=48467]
Abstract
Wireless Mesh Networks (WMNs) has become an important
edge network to provide Internet access to remote
areas and wireless connections in a metropolitan scale. In
this paper, we describe our hop-by-hop bandwidth guaranteed
routing protocol in IEEE 802.11-based wireless
mesh networks. Due to interference among links, bandwidth,
a well-known bottleneck metric in wired networks,
is neither concave nor additive in wireless networks. To
facilitate hop-by-hop routing, we develop a mechanism
for computing the available bandwidth of a path in a
distributed manner. Unfortunately, available bandwidth
is not isotonic, the necessary and sufficient property for
consistent hop-by-hop routing. To solve the problem, we
introduce an isotonic parameter that captures the available
bandwidth metric so that packets can traverse the
maximum bandwidth path consistently according to the
routing tables constructed in the nodes along the path. To
the best of our knowledge, our protocol is the first WMN
hop-by-hop routing scheme that can identify bandwidth
guaranteed paths.
INTRODUCTION
A wireless mesh network (WMN) consists a large
number of wireless nodes. The nodes form a wireless
overlay to cover the service area while a few nodes sitting
on the edge are wired to the Internet. As part of the
Internet, WMN has to support diversified multimedia applications
for its users. Quality-of-Service (QoS) routing,
which focus on finding a path satisfying the application
requirements, is one of the building blocks for supporting
QoS. In this paper, we study how to find a path satisfying
the bandwidth requirement of an incoming connection request.
We adopt the proactive approach, which computes
the maximum bandwidth supported by the paths from a
source to a destination prior to the requests arrive. By precomputing
the supported QoS, we can determine whether
a request is feasible upon its arrival. If this request is feasible,
a resource reservation will be initiated; otherwise,
this request is blocked.
RELATEDWORKS
To find a path with higher bandwidth, many researchers
develop new link metrics to quantify the interference
level of a link and these new link metrics are
additive. The weight of a path becomes the sum of individual
link weights of the links along the path and any
routing protocol that works for an additive metric can be
applied. Simulation studies show that paths found based
on this kind of metrics are better than the least hop count
paths [1, 2].
In [3], the expected transmission count (ETX) metric
is proposed, which computes the average number
of transmission attempts required to send successfully a
packet over the link. It is the earliest link metric developed
and many other metrics are extended from it, such
as mETX, ETN [4], and ETT [9]. The link metric ETT is
used for designing the path metrics WCETT (weighted
cumulative expected transmission time), iAWARE [5],
and MIC [6]. Instead of developing an additive metric,
the Bottleneck Link Capacity (BLC) is based on the
expected busy time of a link for transmitting a packet
successfully [7]. The path BLC is the minimum link
BLC along the path. The link metric CATT proposed
in [8] is similar to BLC. The work in [11] proposes the
interference-aware routing metric, which determines the
percentage of time each transmission wastes due to interference
from other nodes. The routing algorithm based
on the proposed metric selects the path with the minimum
interference.
Table construction
The isotonicity property of the proposed QoS metric
of a path allows us to develop a routing protocol that can
identify the maximum bandwidth path from each node
to each destination. In our routing protocol, if a node
finds a new non-dominated path, it will advertise this
path information to its neighbors. We call the packet carrying
the path information the route packet. For each
non-dominated path p from s to d, s advertises the tuple
(s;d;NF(p);NS(p);~w(p)) to its neighbors in a route
packet. NF(p) and NS(p) are the next hop and the second
next hop on p from s. Based on the information contained
in a route packet, each node knows the first three hops of
a path identified. This information is necessary for consistent
routing, as discussed in the following subsection
CONCLUSIONS
In this paper, we have studied the problem of designing
a hop-by-hop routing protocol with bandwidth requirement
in wireless mesh networks. We presented the
mechanism for path selection and packet forwarding. We
have formally proved that our routing protocol satisfies
the optimality and consistency guarantees, so as to ensure
the proper operation of our protocol. By doing simulations,
we investigated the performance of our routing
protocol. The simulation results showed that our routing
protocol works better than the existing hop-by-hop routing
protocols for finding the maximum bandwidth path.
[attachment=48467]
Abstract
Wireless Mesh Networks (WMNs) has become an important
edge network to provide Internet access to remote
areas and wireless connections in a metropolitan scale. In
this paper, we describe our hop-by-hop bandwidth guaranteed
routing protocol in IEEE 802.11-based wireless
mesh networks. Due to interference among links, bandwidth,
a well-known bottleneck metric in wired networks,
is neither concave nor additive in wireless networks. To
facilitate hop-by-hop routing, we develop a mechanism
for computing the available bandwidth of a path in a
distributed manner. Unfortunately, available bandwidth
is not isotonic, the necessary and sufficient property for
consistent hop-by-hop routing. To solve the problem, we
introduce an isotonic parameter that captures the available
bandwidth metric so that packets can traverse the
maximum bandwidth path consistently according to the
routing tables constructed in the nodes along the path. To
the best of our knowledge, our protocol is the first WMN
hop-by-hop routing scheme that can identify bandwidth
guaranteed paths.
INTRODUCTION
A wireless mesh network (WMN) consists a large
number of wireless nodes. The nodes form a wireless
overlay to cover the service area while a few nodes sitting
on the edge are wired to the Internet. As part of the
Internet, WMN has to support diversified multimedia applications
for its users. Quality-of-Service (QoS) routing,
which focus on finding a path satisfying the application
requirements, is one of the building blocks for supporting
QoS. In this paper, we study how to find a path satisfying
the bandwidth requirement of an incoming connection request.
We adopt the proactive approach, which computes
the maximum bandwidth supported by the paths from a
source to a destination prior to the requests arrive. By precomputing
the supported QoS, we can determine whether
a request is feasible upon its arrival. If this request is feasible,
a resource reservation will be initiated; otherwise,
this request is blocked.
RELATEDWORKS
To find a path with higher bandwidth, many researchers
develop new link metrics to quantify the interference
level of a link and these new link metrics are
additive. The weight of a path becomes the sum of individual
link weights of the links along the path and any
routing protocol that works for an additive metric can be
applied. Simulation studies show that paths found based
on this kind of metrics are better than the least hop count
paths [1, 2].
In [3], the expected transmission count (ETX) metric
is proposed, which computes the average number
of transmission attempts required to send successfully a
packet over the link. It is the earliest link metric developed
and many other metrics are extended from it, such
as mETX, ETN [4], and ETT [9]. The link metric ETT is
used for designing the path metrics WCETT (weighted
cumulative expected transmission time), iAWARE [5],
and MIC [6]. Instead of developing an additive metric,
the Bottleneck Link Capacity (BLC) is based on the
expected busy time of a link for transmitting a packet
successfully [7]. The path BLC is the minimum link
BLC along the path. The link metric CATT proposed
in [8] is similar to BLC. The work in [11] proposes the
interference-aware routing metric, which determines the
percentage of time each transmission wastes due to interference
from other nodes. The routing algorithm based
on the proposed metric selects the path with the minimum
interference.
Table construction
The isotonicity property of the proposed QoS metric
of a path allows us to develop a routing protocol that can
identify the maximum bandwidth path from each node
to each destination. In our routing protocol, if a node
finds a new non-dominated path, it will advertise this
path information to its neighbors. We call the packet carrying
the path information the route packet. For each
non-dominated path p from s to d, s advertises the tuple
(s;d;NF(p);NS(p);~w(p)) to its neighbors in a route
packet. NF(p) and NS(p) are the next hop and the second
next hop on p from s. Based on the information contained
in a route packet, each node knows the first three hops of
a path identified. This information is necessary for consistent
routing, as discussed in the following subsection
CONCLUSIONS
In this paper, we have studied the problem of designing
a hop-by-hop routing protocol with bandwidth requirement
in wireless mesh networks. We presented the
mechanism for path selection and packet forwarding. We
have formally proved that our routing protocol satisfies
the optimality and consistency guarantees, so as to ensure
the proper operation of our protocol. By doing simulations,
we investigated the performance of our routing
protocol. The simulation results showed that our routing
protocol works better than the existing hop-by-hop routing
protocols for finding the maximum bandwidth path.