Capacity of Hybrid Wireless Mesh Networks with Random APs

Capacity of Hybrid Wireless Mesh
Networks with Random APs
Weihuang Fu, Member, IEEE, and Dharma P. Agrawal, Fellow, IEEE
Abstract—In conventional Wireless Mesh Networks (WMNs), multihop relays are performed in the backbone comprising of
interconnected Mesh Routers (MRs) and this causes capacity degradation. This paper proposes a hybrid WMN architecture that the
backbone is able to utilize random connections to Access Points (APs) of Wireless Local Area Network (WLAN). In such a proposed
hierarchal architecture, capacity enhancement can be achieved by letting the traffic take advantage of the wired connections through
APs. Theoretical analysis has been conducted for the asymptotic capacity of three-tier hybrid WMN, where per-MR capacity in the
backbone is first derived and per-MC capacity is then obtained. Besides related to the number of MR cells as a conventional WMN, the
analytical results reveal that the asymptotic capacity of a hybrid WMN is also strongly affected by the number of cells having AP
connections, the ratio of access link bandwidth to backbone link bandwidth, etc. Appropriate configuration of the network can drastically
improve the network capacity in our proposed network architecture. It also shows that the traffic balance among the MRs with AP
access is very important to have a tighter asymptotic capacity bound. The results and conclusions justify the perspective of having such
a hybrid WMN utilizing widely deployed WLANs.
Index Terms—Access points, asymptotic capacity, WLAN, wireless mesh networks, mesh routers
Ç
1 INTRODUCTION
WIRELESS Mesh Network (WMN) [1] is emerging as a
promising technology in providing ubiquitous highspeed
service for Mobile Clients (MCs), also called mesh
clients. Mesh routers (MRs) play an essential role in a
WMN, which provides service for MCs on one hand;
forward data packets via wireless link to neighboring MRs
on the other hand. Interconnected MRs form the backbone
of a WMN, where several special MRs connecting to the
Internet with wired cables are called Internet Gateways
(IGWs). By taking advantage of wireless multihop forwarding
[2], deployment of MRs poses much less constraints as
they can be deployed on electric poles or house rooftop.
Such deployment feasibility enables a WMN to provide low
cost metro-scale coverage for MCs’ access.
The major challenge in aWMNis the capacity degradation
problem caused by the interference on a single or multiple
routing paths during multihop transmission. Although the
network architecture of anyWMNis different from an ad hoc
network, the asymptotic capacity bound derived by the
analytical work in [3] is still valid for aWMNbackbone. Per-
MR capacity of a randomly deployed backbone with ad hoc
routing can be given by

W ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
NR logNR
p
 
;
where W denotes the maximum backbone link data
transmission rate between a pair of neighboring MRs and
NR denotes the number of MRs. It is obvious that the size of
the network is largely constrained by requirements of per-
MR capacity. By optimizing the locations of MRs, per-MR
capacity can be improved by a factor ofð
ffiffiffiffiffiffiffiffiffiffiffiffiffiffi
logNR
p
Þ. Actually,
MRs need not have access to A/C power as energy can be
supplied from self-equipped solar panels. MRs can even be
“dropped” anywhere required. Then, per-MR asymptotic
capacity can be said to approach ð Wffiffiffiffiffi
NR
p Þ.
By deploying IGWs in the network, the whole WMN
forms multiple clusters where each cluster is led by an IGW
and constraints MRs closer to the IGW. Readers interested in
various cluster construction methods are suggested to refer
to [4]. After IGW clusters are formed, the traffic between the
MRs in different clusters, i.e., intercluster traffic, are directed
to their associated IGWs and utilize the wired connections
between the IGWs. A similar network architecture is the
hybrid ad hoc networks, where infrastructures are interconnected
with wired cables and deliver data packets for ad
hoc clients in a single or multiple hops, as shown in Fig. 1a.
The capacity of such an ad hoc network with infrastructure
has been investigated in [5], [6], and [7]. Due to random
deployment, connectivity has a major impact on the
performance. Two geometrically closeby MCs may have a
very long routing path due to weak network connectivity.
Recent results [6] indicate that per-MC capacity under
strong connectivity can achieve ð W0
logNC
Þ, where NC denotes
the number of MCs and W0 denotes the total bandwidth.
BandwidthW0 is shared by all MCs for ad hoc connection or
the connection to infrastructure with time division multiple
access (TDMA) scheduling.
Different from an ad hoc network, a WMN is possible to
reduce the random effect and improve the network capacity
by appropriately deploying MRs. The effect of the number
of IGWs in a WMN is discussed in [8], where MCs are
connected to MRs in a single hop. When the number of
arbitrary deployed IGWs is !ð
ffiffiffiffiffiffiffi
NR
p
Þ, the asymptotic
136 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
. The authors are with the Department of Computer Science, University of
Cincinnati, Cincinnati, OH 45221. E-mail: {fuwg, dpa}@cs.uc.edu.
Manuscript received 23 July 2009; revised 6 May 2010; accepted 4 Nov. 2011;
published online 15 Nov. 2011.
For information on obtaining reprints of this article, please send e-mail to:
tmc@computer.org, and reference IEEECS Log Number TMC-2009-07-0299.
Digital Object Identifier no. 10.1109/TMC.2011.244.
1536-1233/13/$31.00  2013 IEEE Published by the IEEE CS, CASS, ComSoc, IES, & SPS
capacity increases with the number of IGWs, as long as data
is denominated by the intercluster traffic through the IGWs.
If the network capacity needs to fully explore IGWs,
adequate number of IGWs need to be deployed, which
poses restrictions on the deployment of MRs. When
the number of IGWs is Oð
ffiffiffiffiffiffiffi
NR
p
Þ, MRs in a cluster with a
single IGW have to be designed to have information about
the complete network topology so as to perform routing
functions without involving the IGW. Otherwise, the
capacity is constrained by the IGWs and the capacity may
be worse than that of ad hoc routing in the backbone.
Having the whole network information at the MRs may lead
to excessive overhead and may not facilitate easy management
of the clustering approach.
It is noted that MRs, MCs, and IGWs in [8] share the same
spectrum with TDMA scheduling, which are different from
a common two-tier WMN. The role played by MR in [8] is
more like a relay that has additional forwarding function to
MC. It has been pointed out in [9] that current IEEE 802.11
MAC protocol cannot achieve a reasonable throughput as
the number of hops increases to four or higher. A two-tier
WMN illustrated in Fig. 1b employs dedicated spectrum for
the backbone and different spectrum for access link between
MR and MC. MCs can use IEEE 802.11, which has been
widely adopted for Wireless Local Area Network (WLAN)
connection. As different notations used in Fig. 1b for
backbone links and access links, MRs can have two types
of wireless interfaces and use multichannel multiradio [10],
[11] for backbone connections.
The analysis in the paper will show that the asymptotic
capacity can be further enhanced with our proposed hybrid
WMN architecture, wherein WMN is augmented by the
presence of wired Access Points (APs). WLAN technology is
popular to provide network access for clients. However,
limited coverage can only support relatively small region,
like area within a house or an office. Extending the coverage
by multiple co-deployed APs requires availability of wired
cables at the AP locations. Second, deploying multiple APs
in a large coverage area leads to serious inter-WLAN
interference and throughput degradation [2], [12]. In
addition, the Medium Access Control (MAC) layer of APs
cannot support handover for MCs. Although many APs can
be deployed, it is still not feasible to provide seamless
coverage in a city by APs without huge investment on cables
and it is not efficient for APs to provide service directly to
MCs. The use of APs in WMN needs to be explored.
In this paper, we propose to have a higher capacity
bound for a WMN with three-tier hybrid network architecture
by exploring random AP connections, where MR is
allowed to connect to the APs in its coverage. The proposed
network architecture is illustrated in Fig. 2. Backbone links
use a dedicated spectrum with bandwidth W bps. MRs and
IGWs employ multiple orthogonal channels to isolate
interference regions. Each MR is equipped with multiple
radios that are able to operate on different channels
simultaneously. While two neighboring MRs employ the
same channel, a link is formed between them and such a
link is called a backbone link. MRs also provide access to
the MCs around its neighborhood. The total data rate
available for the network access is B bps, with a dedicated
wireless interface for the access link. APs operate on access
link spectrum, which shares bandwidth B with MCs. The
impact on capacity from APs is related to the deployment.
MRs and IGWs are predeployed by Internet Service
Provider (ISP) at planned locations for constructing a
WMN backbone. In contrast, APs are randomly deployed
by users and the connection between AP and MR is
random. APs could be turned off by the users and new
APs could appear to be active. The number of APs could be
changing over time. We take the random deployment of
APs into account. As we can see from Fig. 1b, two-tier
WMN connects to the Internet through a backbone link to
IGWs. On the other hand, Fig. 2 shows three-tier WMN to
have a random connection to the Internet through access
links via APs. In a later analysis, we show that the ratio of B
to W has a very important effect on the network capacity,
besides the number of APs.
Random deployment, random connection, and using
access link spectrum are the special attributes of employing
unsystematic APs as an additional third tier for a WMN.
There are significant advantages of having such connections.
The number of hops that traffic transfers in the
backbone is reduced by utilizing the wired connection of
APs. As a result, end-to-end delay is also decreased. The
network coverage can also be enhanced as MRs have good
outdoor coverage while APs have better indoor coverage.
Knowing that WLANs and WMNs are different networks,
our scheme provides cooperation between WMN and
WLANs by utilizing the residual capacity of WLANs.
The focus of different environment enables two types of
FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 137
Fig. 2. Proposed three-tier hybrid WMN with random AP connections.
Fig. 1. Network architecture.
networks to work together. This three-tier WMN achieves
capacity enhancement at near no additional cost as
WLANs are already deployed. It is compatible with
current wireless network technology and facilitates current
MCs to explore that.
Our main contributions are:
. Proposing a novel network architecture—a hybrid
WMN, which will have a higher capacity than a
conventional WMN. Presence of APs in the deployment
area of conventional WMNs is assumed and
access links for the connections to MRs are used.
Thus, from the network architecture view, existing
WMN is extended with new elements—APs and a
new link type—AP-MR link, and translates a two-tier
network into a three-tier network;
. Applying analytical model to the proposed network
architecture;
. Deriving an asymptotic capacity value for MRs and
MCs under various conditions; and
. Analyzing the impact of the number of MR with
randomly located AP access, ratio of backbone link
bandwidth to access link bandwidth, etc.
The rest of this paper is organized as follows: The system
model is presented in Section 2. Section 3 performs the per-
MR capacity with various traffics, and Section 4 analyzes
the per-MC capacity under grid deployed MRs and random
AP access. The effects of network elements and comparison
with other networks are discussed in Section 5. Finally, the
paper is concluded in Section 6.
2 NETWORK MODEL AND ANALYSIS
The backbone of a WMN consists of MRs and IGWs,
where the MRs and the IGWs are wireless interconnected
to each other and provide service to the MCs. Multiple
IGWs divide a WMN into several clusters such that each
one is led by an IGW. We investigate such an IGW cluster
shown in Fig. 2. MRs in the cluster is homogeneous that
have the same backbone and access link transmission
region. Due to interference among neighboring MRs, they
have to share wireless resources in the frequency domain
and/or time domain.
If an AP is present in the transmission range of anMRcell,
MR can access the AP, as shown in Fig. 2. The connection
between the MR and the AP is also an access link, which
shares bandwidth with the MCs it is serving. We call the MR
with AP connection as AP-MR and the MR without AP
connection as non-AP-MR. While we use term “MR”
without specifying this, and it means both kinds of MRs.
The number of AP-MRs is denoted by NA. The locations of
NA AP-MRs in NR MRs are assumed to be uniformly
distributed. APs and IGWs have wired connection to the
Internet as shown in Fig. 2. The bandwidth of wired
connection to APs and IGWs is assumed to be large enough
so as not to pose any constraint on the network capacity.
Fig. 3 shows two examples for random AP connections,
which is a portion of the network shown in Fig. 2. There are
two types of routings that can benefit from the random AP
connections. While the traffic is between two MRs, the
routing in a conventional WMN is relayed by MRs in the
backbone, denoted by the dotted line in Fig. 3a. With
the inclusion of APs, it can also select the routing path going
through the wired Internet, denoted by the dashed line in
Fig. 3a. By such an alternative routing path, the traffic at MRs
in backbone can be reduced. It also diminishes the interference
in the backbone. As a result, the capacity can be
enhanced. Similarly, when the traffic is between MR and
IGW, the alternative path can go through the AP and the
wired connection to the IGW, denoted by the dashed line in
Fig. 3b. The conventional routing path, denoted by the dotted
line in the figure, could easily cause congestion at the IGW.
2.1 Hybrid WMN Architecture
The network is modeled as shown in Fig. 4, where grid
deployed MRs are indicated by blue circles, the IGW is
indicated by red rectangles, randomly distributed MCs are
indicated by green dots, and APs are indicated by dark
triangles. The three tiers of a hybrid WMN are: MCs in the
first tier (the first column in Fig. 4a) connect to the MRs in the
second tier. Each MR provides network access service for
multiple MCs. MRs in the second tier also interconnect to
each other. So, the traffic from MCs can exchange via the
connections among MRs in the second tier. There is one IGW
in the second layer to provide Internet access to MRs. The
third tier includes APs which are connected to each other by
wired connections. The connections from the MRs in the
second tier to the APs in the third tier are random, which are
denoted by dotted lines in the figure. While wireless
connections between the second tier and the third tier
available, the traffic between two MRs in the second tier
can be exchanged via the third tier. It may be noted that the
138 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
Fig. 3. Alternate routing with random APs connections.
Fig. 4. Hierarchy and deployment.
link bandwidth between two nodes in different tiers are
distinct, where the capacity enhancement of hybrid WMN
benefits from the additional tier of alternate Internet access.
Fig. 4b shows the geographic model of our proposed
hybrid WMN. MRs are deployed in a unit square denoted
by D. The deployment of MRs follows the grid deployment
method, which divides the unit square into NR smaller
squares and each square is served by MR located at the
center of the square. The reason behind a grid deployment
is that the locations of MRs are preplanned and most of the
cities such as Manhattan, New York, has grid-based streets,
which naturally support the grid deployment. Without loss
of generality, NR is the value such that
ffiffiffiffiffiffiffi
NR
p
is an odd
number. An IGW is deployed at the center square.
The coverage of MR i is a circle Cðsi; rsÞ centered at
point si with radius rs. Given a region D, MRs should satisfy
D 
S
i Cðsi; rsÞ to seamlessly cover D. To simplify the
analysis, we assume MRs only provide network access
service for MCs within the coverage closer to MRs. In other
words, MR’s coverage can be approximated by a small
square illustrated in Fig. 4. The size of the small square is
1ffiffiffiffiffi
NR
p  1ffiffiffiffiffi
NR
p . MR is able to connect with APs in its coverage
through the access link. The total number of APs in D is NA.
MR backbone transmission distance rT should be able to
reach closeby MR, which is slightly larger than 1ffiffiffiffiffi
NR
p . It is
trivial to prove that such an MR deployment is connected
with transmission distance larger than 1ffiffiffiffiffi
NR
p . To provide full
coverage to each unit square, MR u needs to provide an
access service for the small square center at si with at
least side length 1ffiffiffiffiffi
NR
p . Since a circle is generally used to
denote the coverage of a cell, we use a circle Cðsi; rsÞ
containing the square to denote the coverage of MR i, where
rs ¼ ffi1ffiffiffiffiffiffi
2NR
p . So, the whole unit square area can be seamlessly
served by such a backbone network.
With the protocol model given in [3], any transmission
from MR i to MR j needs to be within the transmission
distance rT , jsi  sjj  rT . To avoid the interference, other
transmitting MR k needs to satisfy jsk  sjj  rT , where 
is a positive constant to ensure a safe geographic gap
between two simultaneous transmissions. While WMN
backbone employs multichannel multiradio technology for
interference avoidance, the protocol does affect the transmission
using the same channel.
2.2 Traffic Model
First, traffic generated or terminated at MCs can be divided
into intercluster and intracluster traffic. The intercluster
traffic is from the MCs to the destination outside the cluster
or from the source outside the cluster to the MC in the
cluster. The traffic goes to the IGW and the IGW is in-charge
of aggregating intercluster traffic, routing in the wired
network, protocol conversation, etc. Without loss of
generality, we assume inter-cluster traffic is from the MCs
to the IGW. This condition also applies in the reverse
direction. While random AP access is available in a cluster,
the intercluster traffic can be relayed by the APs to the IGW
through wired connection or vice versa. We assume that the
management function is located at the IGW and the
intercluster traffic can be exchanged between the AP and
the IGW via the wired connection between them (which
may go through several routers in the wired Internet).
The other type of traffic is the intracluster traffic, which
is between two MCs in the same cluster. In a WMN, each
MR has the routing ability that can divert the intracluster
traffic. The routing list of the MRs in a cluster can be created
by the same way as in a mobile ad hoc network (MANET)
or be periodically configured by the IGW. For intracluster
traffic, there are two ways to route. The traffic can be routed
toward the cluster head (IGW) and then reroute to the
destination MR. This method is simple to implement as
each MR only needs to know the route to the IGW, and the
information of the MC’s cell locations can be simply stored
at the IGW. However, since all the traffic goes to or comes
from the IGW, the capacity is seriously constrained at the
IGW. Intracluster traffic with such a routing method shows
the same traffic pattern as that of intercluster traffic. The
cluster forms a tree-like topology that is rooted at the IGW.
Network capacity with such a routing method can be easily
derived from the case of the intercluster traffic. Another
way is to route the intracluster traffic like MANET routing
in the form of a mesh topology. Each MR either has the
location information of the MCs in the cluster or is able to
inquire the information from the IGW. The data traffic does
not have to go through the IGW, so the congestion at the
IGW can be mitigated and the capacity of the cluster can
be improved. With MANET type routing among MRs, the
capacity can be improved further by balancing the traffic
among multiple routing paths between the source and the
destination MRs. We assume the MANET routing method is
used for intracluster traffic so as to have an enhanced
network capacity. The asymptotic capacity of the method
that forwards all traffic to the IGW can be also derived from
our results, which is a special case of the asymptotic
capacity with only intercluster traffic.
2.3 Capacity Definition
In the literature such as [5], [13], the network capacity
analysis is based on the per-node asymptotic capacity of
the traffic in a single-tier network. We extend this
definition to three-tier hybrid WMNs with multiple traffics
described above.
Definition 1 (Asymptotic Capacity). The asymptotic capacity
of a node, denoted by ðNCÞ, is of order ðgðNCÞÞ bps if
deterministic constants c > 0 and c0 < þ1 are such that lim NC!þ1 P½ðNCÞ ¼ cgðNCÞis feasible ¼ 1; lim NC!þ1 inf P½ðNCÞ ¼ c0gðNCÞis feasible < 1: Definition 2 (Per-MR Capacity R). The maximum asymptotic capacity per MR can be achieved with different combinations of possible traffic. Definition 3 (Per-MC Capacity C). The maximum asymptotic capacity per MC can be achieved with various combinations of possible traffic. 3 PER-MR CAPACITY In this section, we consider an asymptotic capacity of the backbone. Traffic in the backbone network can be divided FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 139 into four categories according to the types of devices involved. The first type is the ad hoc MANET-type traffic which exists in the backbone only among MRs. The second one is the random intracluster AP traffic. With wireless connection between MR and AP, intracluster traffic can utilize the wired connection between two APs. The third is the intercluster traffic relayed by MRs through the IGW. And the fourth one is the random intercluster AP traffic, which uses the wired connection between the AP and the IGW. The main results of per-MR capacity are summarized here. We show per-MR capacity for four different types of traffic. Then, we determine the per-MR capacity with the combination of the traffic patterns. Per-MR capacity with ad hoc intracluster traffic which does not involve AP can be expressed by Rr ¼  Wffiffiffiffiffiffiffi NR p   : ð1Þ Per-MR capacity with intracluster AP traffic is expressed by Rp ¼  NAB NR   ; B¼ OðWÞ;  NAW NR   ; B¼ !ðWÞ: 8>>>< >>>:
ð2Þ
From (1) and (2), the combination of two types of traffic
that maximizes the asymptotic capacity is expressed by
RI ¼

Wffiffiffiffiffiffiffi
NR
p
 
; NA ¼ O
W
ffiffiffiffiffiffiffi
NR
p
B
 
;

NAB
NR
 
; NA ¼ !
W
ffiffiffiffiffiffiffi
NR
p
B
 
^ B ¼ OðWÞ;

NAW
NR
 
; NA ¼ !ð
ffiffiffiffiffiffiffi
NR
p
Þ ^ B ¼ !ðWÞ:
8>>>>>>>>< >>>>>>>>:
ð3Þ
Per-MR capacity with intercluster traffic without APs is
expressed by
Rg ¼ 
W
NR
 
: ð4Þ
Per-MR capacity with intercluster AP traffic is expressed
by
Re ¼

NAB
NR
 
; B¼ OðWÞ;

NAW
NR
 
; B¼ !ðWÞ:
8>>>< >>>:
ð5Þ
From (4) and (5), Per-MR capacity with intercluster
traffic can be expressed by
RE ¼

NAB þW
NR
 
; B¼ OðWÞ;

ðNA þ 1ÞW
NR
 
; B¼ !ðWÞ:
8>>>< >>>:
ð6Þ
Per-MR capacity with the composition of all traffic
patterns is expressed by
R ¼

Wffiffiffiffiffiffiffi
NR
p
 
; NA ¼ O
W
ffiffiffiffiffiffiffi
NR
p
B
 
;

NAB
NR
 
; NA ¼ !
W
ffiffiffiffiffiffiffi
NR
p
B
 
^ B ¼ OðWÞ;

ðNA þ 1ÞW
NR
 
; NA ¼ !ð
ffiffiffiffiffiffiffi
NR
p
Þ ^ B ¼ !ðWÞ:
8>>>>>>>>< >>>>>>>>:
ð7Þ
3.1 Routing and Traffic Balance
To illustrate the routing and traffic balance scheme used in
analyzing a WMN backbone, we use a 2D grid-based WMN
of Fig. 5. Figure also shows the connectivity graph of the
MRs, which are denoted by dots at the intersections. The
edges between intersection points denote the communication
links. Packets can transmit from one MR to the
neighboring MR in the grid, which counts as one-hop
transmission. The location of MRs in the grid can be
expressed by two integers: an integer for the x-axis and the
other one for the y-axis. For example, we have the traffic
from source MR1 to destination MR2. The locations of MR1
and MR2 are denoted by ði; jÞ and ðm; nÞ, respectively. The
minimum number of hops for the transmission is given by
h ¼ jm  ij þ jn  jj. A feasible routing path with the
minimum number of hops is illustrated by the blue color
arrows P1 along the grids in Fig. 5.
There are a number of paths that satisfy the shortest path
routing, which are within the rectangles formed by MR1
and MR2 points and are shown in Fig. 5, by the broken
rectangle A1 formed by MR1 and MR2. The traffic can be
distributed and balanced on those paths and is routed by
the set of MRs at the locations within in the rectangular
area (x 2 ½i;m, y 2 ½j; n).
Random access to AP enables the traffic to take the
shortcut of the wired connection. There may be another
alternate routing path. For example, if MR3 and MR4 are
two MRs with AP access. MR1 can transmit the packets to
MR3 and MR3 sends the packets to its AP(s) with the access
link. The packets then go through the wired connection(s)
between the APs, to the AP(s) at the cell of MR4. It is
noticeable that the number of APs at a cell may be more
than one and the traffic might be distributed to multiple
APs. After MR4 receives the packets, it relays the packets to
destination MR2 via the backbone. The routing path is
denoted by P2 and is illustrated by the red arrows, and the
wired connection is denoted by the red dashed line in Fig. 5.
Routing between non-AP-MR and AP-MR can do the
balancing between normal backbone traffic. For example,
140 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
Fig. 5. Routing and traffic balance in a WMN backbone.
the routing paths can take the set of paths within the broken
rectangular area A2 formed by MR1 and MR3, which is
illustrated by the broken rectangle between MR1 and MR3
in the figure. It is also applicable to MR4 and MR2, as
shown by the broken rectangle A3 in Fig. 5. The traffic
balance in the wired connection depends on the configuration
of the wired network, assuming that the wired
connections among APs has enough bandwidth and are
able to deliver packets with relatively low latency.
Here, some useful lemmas used later are listed. Proofs of
Lemmas 1 and 2 are given in [14] and a proof of Lemma 3 is
given in [15].
Lemma 1 (Chernoff Upper Tail Bound). If  is the sum of
independent indicator random variables, then
P½  ð1 þ ÞE½  e2E½
2þ; >0: ð8Þ
Lemma 2 (Chernoff Lower Tail Bound). If  is the sum of
independent indicator random variables, then
P½  ð1  ÞE½  e2E½
2 ; 2 ð0; 1: ð9Þ
Lemma 3. For NC MCs uniformly and independently distributed
in a unit square, the critical transmission distance is
c0
ffiffiffiffiffiffiffiffiffiffiffiffiffiffi
logNC
NC
s
; ð10Þ
where c0 is a positive constant greater than one.
3.2 Backbone Ad Hoc Routing
The backbone capacity of intracluster traffic with ad hoc
routing, i.e., MR to MR traffic, has higher asymptotic
capacity with a regular grid deployment. Proposition 1
provides the asymptotic capacity of MRs with grid deployment
which follows the arbitrary network asymptotic
capacity of [3].
Proposition 1. Given a connected backbone network consisting
of NR grid deployed MRs, per-MR capacity with ad hoc
traffic is Rr ¼ ð Wffiffiffiffiffi
NR
p Þ.
Proof. Traffic with ad hoc routing is between a pair of MRs
in the same cluster. With a relative large NR, each MR
has the same probability to be a source or a destination.
Two MRs on grid ðm; nÞ and ði; jÞ can be randomly
picked as the source MR and the destination MR,
respectively. The number of hops for the routes on the
grids is at least h ¼ jm  ij þ jj  nj. Considering all
such possible pairs, the lower bound of the average
number of hops hL is computed as follows:
E½hL ¼ E½jm  ij þ E½jj  nj ¼ 2E½E½jm  iki: ð11Þ
E½jm  iki is obtained as
E½jm  iki ¼
1ffiffiffiffiffiffiffi
NR
p
Xi1
m¼1
ði  mÞ þ
X
ffiffiffiffiffi
NR
p
m¼i
ðm  iÞ
!
¼
i2
ffiffiffiffiffiffiffi
NR
p 
1ffiffiffiffiffiffiffi
NR
p þ 1
 
i þ
ffiffiffiffiffiffiffi
NR
p
þ 1
2
:
ð12Þ
E½i2 is computed by following equation:
E½i2 ¼
ð
ffiffiffiffiffiffiffi
NR
p
þ 1Þð2
ffiffiffiffiffiffiffi
NR
p
þ 1Þ
6
: ð13Þ
Substituting E½i2 from (13) into (12), and then
substituting (12) into (11), we obtain the lower bound
of average number of hops
hL ¼ E½hL ¼
2
3
ffiffiffiffiffiffiffi
NR
p

1ffiffiffiffiffiffiffi
NR
p
 
: ð14Þ
Denote the upper bound for the average number of
hops by hU. In any feasible routing scheme illustrated
earlier, traffic can be distributed and balanced on the
routes available within the minimum rectangular area
constructed by the source and the destination MRs. One
of the attributes of such a routing scheme is that the
number of hops for different routes is the same and is
equal to the number of hops of the shortest path. So, the
upper bound of the average number of hops can be
obtained by
hU ¼ O
 ffiffiffiffiffiffiffi
NR
p 
: ð15Þ
As the maximum data rate is no more than W, the
maximum throughput in the backbone is
RrhNR  NRW: ð16Þ
Due to interference among multiple transmissions, not
all MRs could send data at the same time over the whole
frequency band. For MRs in the interference region, they
have to share the bandwidth by operating at different
frequencies and/or time slots. Given the grid topology of
a WMN backbone, the transmission is set to reach the
closest MRs that does not interfere with another second
closest MRs. We use the channel assignment for the links
between neighboring MRs in the grids so that links in the
same interference region can operate on different orthogonal
channels, without interfering with each other. An
interference region is formed by a circle r2I
centered at
the transmitting MR. Let us take rT ¼ 1ffiffiffiffiffi
NR
p , then rI ¼ ð1þffiffiffiffiffiÞ
NR
p .
Each MR occupies a region of 1ffiffiffiffiffi
NR
p  1ffiffiffiffiffi
NR
p in the unit
square. So, there are at most r2I
NR MRs in the interference
region, expressed by nIM  r2I
NR ¼ ð1þÞ2. The number
of links within the interference region is no more than
4nIM  4ð1 þ Þ2. So, the number of channels required
is no more than c1 ¼ 4ð1 þ Þ2 for a feasible channel
assignment like [16]. With this channel assignment and
scheduling, we can have
RrhNR 
NRW
2c1
: ð17Þ
Thus, we obtain the MR ad hoc asymptotic capacity
from (16) and (17), which is expressed by
Rr ¼ 
Wffiffiffiffiffiffiffi
NR
p
 
: ð18Þ
tu
FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 141
Different from the capacity analysis in a random network,
some factors can be identified and capacity can be
improved in a regular topology. The average number of
hops in a grid topology is tightly bounded by the optimal
routing scheme and the feasible routing scheme. The
number of MRs affected by the interference can also be
computed correctly. As a result, the backbone capacity can
be accurately evaluated taking these factors into account.
The asymptotic capacity in other regular deployment such
as hexagonal topology, triangle topology, and so on, can be
estimated with the same method used in Proposition 1.
3.3 Intracluster AP Traffic
For the intracluster traffic between two MCs in the same
cluster, it can also utilize random connections between MRs
and APs. Decreasing the number of hops for the traffic
going to the Internet reduces the load in the backbone. The
enhancement is mainly affected by the number of accessible
APs and the bandwidth of such random connections. As
described later, Propositions 2 and 3 provide per-MR
capacity under different conditions.
Lemma 4. Given a connected backbone network consisting of NR
grid deployed MRs, per-MR capacity with intracluster AP
traffic is ðNAB
NR
Þ, if B ¼ OðWÞ.
Proof. When the access link data rate is B ¼ OðWÞ, the
capacity is constrained by the access links. The throughput
is no more than the total throughput of all APs and
the IGW. While each AP-MR fully utilizes access link
bandwidth, the per-MR capacity is
Rp 
BNA þW
NR
: ð19Þ
While the capacity is constrained by the access link,
the backbone link bandwidth is sufficient for traffic
balance among the MRs having AP access. Without loss
of generality, we assume that the traffic are toward the
APs. For an AP-MR cell, the feasible solution can redirect
the traffic in the cell with AP access to the AP in the same
cell. The rest of the cells without AP access, routes the
traffic to the cells with AP access by considering traffic
balance among different AP-MR cells.
In the cell having AP access, the AP access link shares
the bandwidth with MCs. The aggregated traffic between
the MR and the MCs takes Rp bandwidth, and the
redirection of this traffic to the AP costs additional Rp
bandwidth. The residual bandwidth is available for other
MRs. As we can evenly associate non-AP-MRs to each
AP-MR or the IGW, the backbone bandwidth is not a
constraint. The number of associated non-AP-MRs for
every AP-MR is no more than NRNA1
NAþ1 þ 1. The asymptotic
capacity is
Rp
NR
NA þ 1
 B  2Rp ;
Rp 
BðNA þ 1Þ
NR þ 2NA þ 2
:
ð20Þ
From (19) and (20), the asymptotic capacity of
ðBNA
NR
Þ holds for B ¼ OðWÞ. tu
Lemma 5. Given a connected backbone network having NR
grid deployed MRs, per-MR capacity with intracluster AP
traffic is ðNAW
NR
Þ, if B ¼ omegaðWÞ and NA ¼ Oð
ffiffiffiffiffiffiffi
NR
p
Þ.
Proof. While B ¼ !ðWÞ, the intracluster AP throughput is
constrained by backbone links rather than access links.
The aggregated traffic at the AP-MR cell would not be
forwarded into backbone network but redirected to the
AP by the MR via the access link. The upper bound of
the capacity is
Rp 
ðNA þ 1ÞW
NR  NA  1
: ð21Þ
The interference at neighboring AP-MRs could degrade
the throughout. With grid topology, each MR will
have four neighboring MRs that could interfere with it. If
AP-MR has four neighboring MRs that all have AP
accesses, the equal bandwidth shared among five MRs
will be less than W
5 . It degrades throughput if the traffic is
relayed from peripheral AP-MRs to the middle AP-MR.
So, we do not allocate the traffic from the non-AP-MRs to
the AP-MRs that are surrounded by AP-MRs. The traffic
is only allocated and balanced among the AP-MRs
having non-AP-MRs available as neighbors. The probability
that a backbone link is adjacent to two AP-MRs,
is approximated by
N2
A
N2R
. According to the Chernoff upper
tail bound, the number of links adjacent to two AP-MRs,
denoted by nA, is bounded by
P nA  ð1 þ c2Þ
N2A
NR
 
 e
c22
N2
A
ð2þc2ÞNR ; ð22Þ
where c2 is a positive constant.
If NA ¼ Oð
ffiffiffiffiffiffiffi
NR
p
Þ, nA is bounded by ð1 þ c2Þ N2
A
NR
with
high probability (w.h.p.). The number of AP-MRs
surrounded with AP-MRs is less than nA. We use the
same feasible traffic distribution and balance them as
illustrated by Lemma 4 for the intracluster AP traffic. The
feasible throughput per MR is
Rp 
W
c1

NA  ð1þc2ÞN2
A
NR

NR  NA  1
: ð23Þ
To summarize, per-MR capacity with intracluster AP
traffic is Rp ¼ ðWNA
NR
Þ, if B ¼ !ðWÞ and NA ¼ Oð
ffiffiffiffiffiffiffi
NR
p
Þ. tu
Lemma 6. Given a connected backbone network having NR grid
deployed MRs, per-MR capacity with intracluster AP traffic
is ðNAW
NR
Þ, if B ¼ !ðWÞ and NA ¼ !ð
ffiffiffiffiffiffiffi
NR
p
Þ.
Proof. The upper bound for per-MR capacity is
Rp 
ðNA þ 1ÞW
NR  NA  1
: ð24Þ
The probability that a backbone link is adjacent to a
non-AP-MR and an AP-MR is 2NA
NR
ð1  NA
NR
Þ.
According to the Chernoff bound, the number of such
links in the network has a lower bound of
P nM  ð1  c3Þ2 NA 
N2A
NR
  
 ec23
ðNA
N2
A
NR
Þ; ð25Þ
where c3 is a positive constant less than 1.
Since NA ¼ !ð
ffiffiffiffiffiffiffi
NR
p
Þ, nM is no less than c4ðNA  N2
A
NR
Þ
w.h.p., where c4 ¼ 2ð1  c3Þ. Several links may have the
142 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
same adjacent AP-MR, but the maximum number of
links being adjacent to the same AP-MR is no more than
four. So, the number of AP-MRs has non-AP-MR in one
hop is more than c4
4 ðNA  N2
A
NR
Þ w.h.p. In the worst case,
we can schedule the traffic to these AP-MRs having
neighboring non-AP-MR. An AP-MR can provide at least
throughput of W
c1
bps. With the feasible scheduling, the
per-MR capacity is
Rp 
c4

NA 
N2
A
NR

W
4c1ðNR  NA  1Þ
: ð26Þ
In summary, Rp ¼ ðNAW
NR
Þ, if B ¼ !ðWÞ and NA ¼
!ð
ffiffiffiffiffiffiffi
NR
p
Þ. tu
Proposition 2 is obtained from Lemmas 4, 5, and 6.
Proposition 2. Given a connected backbone network consisting of
NR grid deployed MRs, per-MR capacity with intracluster AP
traffic is
Rp ¼

NAB
NR
 
; B¼ OðWÞ;

NAW
NR
 
; B¼ !ðWÞ:
8>>< >>:
ð27Þ
3.4 Intercluster Traffic through IGW
Assuming that intercluster traffic only transmits in the
backbone toward or from the IGW, the per-MR capacity is
bounded by the bandwidth of the IGW and given by the
following proposition:
Proposition 3. Per-MR capacity of intercluster traffic without
AP connections is
Rg ¼ 
W
NR
 
: ð28Þ
Proof. When the intertraffic goes through the IGW, the
capacity is constrained by the bandwidth at the IGW and
the wired connection of the IGW is assumed to have
unconstrained bandwidth. The bandwidth can be fairly
shared by all the MRs in the cluster and the per-MR
throughput is
Rg 
W
NR  1
: ð29Þ
IGW shares the bandwidth with the neighboring MRs.
With the channel assignment, the maximum number of
required channels is no more than c1. The feasible IGW
throughput is no less than 4W
c1
bps. The assigned traffic at
each MR is Rg  4W
c1ðNR1Þ . MR can have throughput that
is more than 4W
c1
. Considering the relay and aggregated
traffic, the traffic at MR u follows:
Rg þWiðuÞ þWoðuÞ 
4W
c1
;
Rg þWiðuÞ ¼ WoðuÞ;
8< : ð30Þ where WiðuÞ denotes the incoming traffic of MR u, and WoðuÞ denotes the outgoing traffic of MR u. Since the maximum throughput of IGW is no more than W, per-MR capacity Rg  W NR1 . From (30), we have WiðuÞ  2W c1  W NR  1  W c1ðNR  1Þ ; ð31Þ while NR  c1þ3 2 . According to the asymmetric structure of the grid network, the incoming traffic at the one hop away MR is no more than W c1ðNR1Þ . So, the MR one hop away from the IGW can afford the assigned traffic load. Similarly, the MRs at the two and more hops away can support the assigned traffic loads. We have a feasible scheduling that the per-MR capacity can achieve as Rg  4W c1ðNR  1Þ : ð32Þ To sum up, Rg ¼ ðW NR Þ. tu As shown by the per-MR ad hoc capacity ð Wffiffiffiffiffi NR p Þ, the MR will not be the bottleneck for intercluster traffic. The traffic is only constrained by the IGW. This result is also confirmed by the experimental result in [17]. 3.5 Intercluster AP Traffic With random access to APs, the capacity is increased by leveraging the AP’s wired connections. For some gateway functions such as authentication and authorization located in the cluster head (IGW), AP still can forward the traffic to the IGW by the wired connections for management purpose. Such mechanism can effectively reduce the number of hops and the volume of the traffic in WMN backbone. Proposition 4. Given a connected backbone network consisting of NR grid deployed MRs and NA of them have AP access, per- MR capacity with intercluster AP traffic is Re ¼  NAB NR   ; B¼ OðWÞ;  NAW NR   ; B¼ !ðWÞ: 8>>>< >>>:
ð33Þ
Proof. While the capacity is constrained by the access links
of the AP-MRs, we have
Re ðNR  NA  1Þ  NAðB  Re Þ;
Re 
BNA
NR  1
:
ð34Þ
Otherwise, it is constrained by the backbone. The feasible
routing and scheduling can use a similar method
indicated in the proof of intracluster traffic going
through APs to reach the capacity bound. With such a
traffic balance, the traffic from or to backbone is given by
Re
NRNA1
NA
. A feasible scheduling is
Re
NR  NA  1
NA
þ 2Re  B;
Re 
BNA
NR þ NA  1
:
ð35Þ
When the capacity is constrained by the backbone,
there are two situations: NA ¼ Oð
ffiffiffiffiffiffiffi
NR
p
Þ and NA ¼
!ð
ffiffiffiffiffiffiffi
NR
p
Þ. When NA ¼ Oð
ffiffiffiffiffiffiffi
NR
p
Þ, the APs are far apart
FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 143
and do not interfere with one another w.h.p., as given by
Lemma 5. Then, the asymptotic capacity is Re ¼ !ðNAW
NR
Þ.
When NA ¼ !ð
ffiffiffiffiffiffiffi
NR
p
Þ, some MRs having APs are
surrounded by other AP-MRs and cannot effectively
provide the traffic shortcut. However, the rest of AP-MRs
can be accessed by non-AP-MRs and the capacity can
reach ðNAW
NR
Þ as proved in Lemma 6. tu
4 PER-MC CAPACITY
The per-MC capacity is not only constrained by the
backbone per-MR capacity but also the access link of each
cell. The asymptotic capacity can be identified by a
combination of traffic under various cases.
The main results of per-MC capacity are summarized
here. Per-MC capacity with MR ad hoc routing is given by
Cr ¼

NRB
NC
 
; NR¼O
NC
logNC
 
^ B¼o
Wffiffiffiffiffiffiffi
NR
p
 
;

ffiffiffiffiffiffiffi
NR
p
W
NC
 
; NR¼O
NC
logNC
 
^ B¼
Wffiffiffiffiffiffiffi
NR
p
 
;

B
logNC
 
; NR¼!
NC
logNC
 
^ B¼o
Wffiffiffiffiffiffiffi
NR
p
 
;

W ffiffiffiffiffiffiffi
NR
p
logNC
 
; NR¼!
NC
logNC
 
^ B¼
Wffiffiffiffiffiffiffi
NR
p
 
:
8>>>>>>>>>>>>< >>>>>>>>>>>>:
ð36Þ
Per-MC capacity with intracluster AP traffic is obtained as
Cp ¼

NAB
NC
 
; B¼ OðWÞ;

NAWÞ
NC
 
; NA ¼ O
NC
logNC
 
^ B ¼ !ðWÞ;

W
logNC
 
; NA ¼ !
NC
logNC
 
^ B ¼ !ðWÞ:
8>>>>>>>>< >>>>>>>>:
ð37Þ
The intracluster traffic is the combination of ad hoc MR
traffic and intracluster AP traffic. Considering reasonable
access link bandwidth B ¼ ð Wffiffiffiffiffi
NR
p Þ ^ B ¼ OðWÞ, per-MC
capacity with intracluster traffic can be expressed by
CI ¼

ffiffiffiffiffiffiffi
NR
p
W
NC
 
; NR ¼ O
NC
logNC
 
^ NA ¼ O W
ffiffiffiffiffi
NR
p
B

;

NAB
NC
 
; NR ¼ O
NC
logNC
 
^ NA ¼ ! W
ffiffiffiffiffi
NR
p
B

;

W ffiffiffiffiffiffiffi
NR
p
logNC
 
; NR ¼ !
NC
logNC
 
^ NA ¼ O WNC
B
ffiffiffiffiffi
NR
p
logNC

;

NAB
NC
 
; NR ¼ !
NC
logNC
 
^ NA ¼ ! WNC
B
ffiffiffiffiffi
NR
p
logNC

:
8>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>:
ð38Þ
Per-MC capacity with IGW traffic is Cg ¼ ðW
NC
Þ. Per-MC
capacity with intercluster AP traffic is given by
Ce ¼

NAB
NC
 
; B¼ OðWÞ;

NAW
NC
 
; NA ¼ O
NC
logNC
 
^ B ¼ !ðWÞ;

W
logNC
 
; NA ¼ !
NC
logNC
 
^ B ¼ !ðWÞ:
8>>>>>>< >>>>>>:
ð39Þ
Per-MC capacity with intercluster AP traffic, if B ¼
OðWÞ, is expressed by
CE ¼ 
NAB
NC
 
: ð40Þ
Besides dominating factor of the number of NR and/or
NA, the ratio of B to W also has a strong impact on the
selection of capacity region. As there are two spectrums in a
WMN, the network bottleneck could be either the backbone
link bandwidth or the access link bandwidth. For appropriate
capacity region, the ratio of B to W shall be
B
W
¼ 
1ffiffiffiffiffiffiffi
NR
p
 
^ Oð1Þ: ð41Þ
Per-MC capacity within the region of (41) is expressed by
C ¼

ffiffiffiffiffiffiffi
NR
p
W
NC
 
; NR ¼ O
NC
logNC
 
^ NA ¼ O W
ffiffiffiffiffi
NR
p
B

;

NAB
NC
 
; NR ¼ O
NC
logNC
 
^NA ¼ ! W
ffiffiffiffiffi
NR
p
B

;

W ffiffiffiffiffiffiffi
NR
p
logNC
 
; NR ¼ !
NC
logNC
 
^NA ¼ O WNC
B
ffiffiffiffiffi
NR
p
logNC

;

NAB
NC
 
; NR ¼ ! NC
logNC

^NA ¼ ! WNC
B
ffiffiffiffiffi
NR
p
logNC

:
8>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>:
ð42Þ
The access link bandwidth B needs to be higher or equal
order of Wffiffiffiffiffi
NR
p ; otherwise, the access link is the bottleneck and
strongly constraints the capacity. While B is the higher
order of W, W becomes the capacity constraint. When
B ¼ ð Wffiffiffiffiffi
NR
p Þ ^ B ¼ OðWÞ, the question about which link
serves as the capacity constraint will also depend on the
number of random APs. Equation (42) shows the capacity
region for B
W between ð 1ffiffiffiffiffi
NR
p Þ and Oð1Þ. While NR ¼
Oð NC
logNC
Þ, the capacity can be enlarged with NA ¼ !ðW
ffiffiffiffiffi
NR
p
B Þ
and capacity is constrained by access link bandwidth B.
While NR ¼ !ð NC
logNC
Þ, the capacity can be significantly
increased with NA ¼ !ð WNC
B
ffiffiffiffiffi
NR
p
logNC
Þ.
4.1 Per-MC Capacity with MR Ad Hoc Routing
Lemmas 7, 8, and 9 give the bounds for the number of MCs
in a cell with different orders of the number of MRs, which
lead to different per-MC asymptotic capacity in later
propositions. Lemma 10 is the critical transmission distance
for MCs in a unit square. It serves as the bound for the
distance between any two MCs in the region.
144 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
Lemma 7. Given NC MCs are uniformly and independently
distributed in NR identical cells, we have
sup

ni
C


NC
NR
; ð43Þ
where ni
C denotes the number of MCs at cell i.
Proof. If the number of MCs in each cell is less than NC
NR
, the
total number of MCs will be less than NC, which contradicts
P
i ni
C ¼ NC. tu
Lemma 8. Given NC MCs are uniformly and independently
distributed in NR identical cells, the following equation holds
w.h.p., if NR ¼ Oð NC
logNC
Þ:
sup

ni
C

 c5
NC
NR
; ð44Þ
where c5 is a positive constant.
Proof. According to the Chernoff upper tail bound, the
number of MCs in any cell i is upper bounded by
P ni
C  c5
NC
NR
 
 e
ðc51Þ2NC
ð1þc5ÞNR ; ð45Þ
where c5 is a positive number. IfNR ¼ Oð NC
logNC
Þ, the RHS of
the equation approaches zero and ni
C  c5
NC
NR
w.h.p. tu
Lemma 9. Given NC MCs are uniformly and independently
distributed in NR identical cells, the following equation holds
w.h.p., if NR ¼ !ð NC
logNC
Þ:
supfni
Cg  c6 logNC; ð46Þ
where c6 is a positive constant.
Proof. According to the Chernoff upper tail bound, the
number of MCs in any cell i is upper bounded by
P½ni
C  c6 logNC  e


c6NR logNC
NC
1
2
1þ
c6NR logNC
NC
NC
NR
: ð47Þ
The RHS of equation approaches zero while NC goes
infinity. So, the number of MCs in a cell is no more than
c6 logNC w.h.p. tu
Lemma 10. There exists an MC that is selected by more than
c7 logNC MCs as the destination w.h.p., where c7 is a positive
constant.
Proof. For the MCs in the unit square, performing Voronoi
tessellation based on the location of MCs such that the
point in a cell Vi of MC i is closer to point MC i than any
other MCs. The set of Voronoi cells is denoted by V.
According to the critical transmission distance for random
deployment of APs, there exists such a cell Vi 2 V such
that the size of Vi area, denoted by SðViÞ, is ðlogNC
NC
Þ.
The method to find the destination for MC j is to drop
a randomly point and select MC that is closer to the point
than any other MCs. So, MC will take all the MCs that
drop random destination points in its Voronoi cell as its
source MCs. For cell Vi that has size ðlogNC
NC
Þ, the number
of points falls in the cell follows:
P½nS  c7 logNC  e
ð
c7
c8
þ1Þ2 logNC
2 ; ð48Þ
where c7 and c8 are positive constants. The RHS
approaches zero while NC approches infinity. So, there
exist more than c7 logNC MCs that will drop their
destination points in its Voronoi cell w.h.p. tu
Different orders of NR lead to distinct asymptotic
capacity. As indicated in the Lemmas above, NR mainly
divides into NR ¼ Oð NC
logNC
Þ and NR ¼ !ð NC
logNC
Þ. The per-MR
capacity with ad hoc routing in the backbone network only
involves the MRs. So, the capacity is mainly affected by NR.
Since the traffic is from one cell to another, the traffic of
different cells are constrained to each other. The per-MR
capacity is also considered for both uplink and downlink of
MCs in cells. Propositions 5 and 6 derive the per-MR
asymptotic capacity from the view of uplink in a cell, while
Propositions 7 and 8 analyze the per-MR asymptotic
capacity from the view of downlink in a cell.
Proposition 5. With ad hoc routing in the backbone, per-MC
capacity for uplink traffic from MCs in a cell is Cr ¼
ðNR
NC
minfR;BgÞ, if NR ¼ Oð NC
logNC
Þ.
Proof. The uplink throughput is either constrained by the
backbone per-MR capacity or the access link bandwidth,
which is expressed by
Crni
C  minfRr;Bg: ð49Þ
From Lemma 7, we obtain
Cr 
NR
NC
minfRr;Bg: ð50Þ
It is easy to schedule Crni
C traffic for one hop access
link from MCs to the MR, which is
Crni
C  minfR;Bg: ð51Þ
FromLemma8, the traffic can be scheduled and achieve
Cr 
NR
c5NC
minfR;Bg: ð52Þ
Thus, Cr ¼ ðNR
NC
minfR;BgÞ holds, where NR ¼
Oð NC
logNC
Þ. tu
Proposition 6. With ad hoc routing in the backbone, per-MC
capacity for uplink traffic from MCs in a cell is Cr ¼
ðminfR;Bg
logNC
Þ, where NR ¼ !ð NC
logNC
Þ.
Proof. There exists an MC that is selected by more than
c7 logNC according to Lemma 10. So, we have
Cr 
minfR;Bg
c7 logNC
: ð53Þ
According to Lemma 9, the number of MCs in a cell is
upper bounded by c6 logNC. With the TDMA scheduling,
we have
Cr 
minfR;Bg
c6 logNC


: ð54Þ
The following result is obtained from (53) and (54). tu
Proposition 7. Downlink traffic of MCs at a cell is Cr ¼
ðNR
NC
minfR;BgÞ, if NR ¼ Oð NC
logNC
Þ.
Proof. The critical connection distance of MCs is aðnÞ ¼
c0
ffiffiffiffiffiffiffiffiffiffi
logNC
NC
q
(Lemma 3). It means that MC can be found
FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 145
within a circle with radius aðnÞ w.h.p. For the intracluster
traffic, it is generated by randomly picking up two points
in the unit square and the nodes closest to the points are
selected as the source and the destination, respectively.
So, the MCs in the cell will be selected as the destination
nodes while random destination points fall in the
combined area of the cell and the surround region with
aðnÞ width. The size of such area can be computed by
Pd 
1ffiffiffiffiffi
N
p
R
þ 2aðnÞ
 2

1
NR
þ 4a2ðnÞ þ
4aðnÞ ffiffiffiffiffiffiffi
NR
p :
ð55Þ
Downlink traffic satisfies CrPdðNCni
CÞminfR;Bg.
We have
Cr 
minfR;Bg
PdðNC  ni
CÞ

minfR;Bg

1
NR
þ 4a2ðnÞ þ 4affiðffinffiffiÞffi
NR
p

NCð1  oð1ÞÞ

minfR;Bg
 NC
NR
þ 4c20
logNC
 þ 4c0
ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
NC logNC
NR
q 
ð1  oð1ÞÞ
:
ð56Þ
If NR ¼ Oð NC
logNC
Þ, we obtain
Cr  c9
NR
NC
minfR;Bg: ð57Þ
Let nD denote the number of MCs selecting the MCs
in a cell as the destination. With the Chernoff upper
bound, we have
P nD 
c10NC
NR
 
 e

ð
c10
NRPd
1Þ2
1þ
c10
NRPd
NCPd
; ð58Þ
where c10 > 1.
If NR ¼ Oð NC
logNC
Þ, the RHS of the equation approaches
zero, so nD is upper bounded by c10NC
NR
w.h.p. With feasible
TDMA scheduling, we have
Cr 
minfR;Bg
nD



NRminfR;Bg
c10NC


: ð59Þ
Thus, Cr ¼ ðNR
NC
minfR;BgÞ holds, ifNR ¼ Oð NC
logNC
Þ.tu
Proposition 8. Downlink traffic of MCs at a cell is Cr ¼
ðminfR;Bg
logNC
Þ, if NR ¼ !ð NC
logNC
Þ.
Proof. According to Lemma 10, the maximum per-MC
capacity is upper bounded by
Cr 
minfR;Bg
c7 logNC
; ð60Þ
if NR ¼ !ð NC
logNC
Þ.
Also, from the Chernoff upper bound, the number of
MCs having traffic to a cell is upper bounded by
P½nD  c11 logNC  e


c11NC
logNCPd
1
2
NCPd
1þ
c11NC
logNCPd ; ð61Þ
where c11 > 1.
The RHS of the equation approaches zero if
NR ¼ !ð NC
logNC
Þ. So, nD is upper bounded by c11 logNC
w.h.p. With the feasible TDMA scheduling, we have
Cr ¼
minfR;Bg
nD



minfR;Bg
c11 logNC


: ð62Þ
Thus, Cr ¼ ðminfR;Bg
logNC
Þ holds, if NR ¼ !ð NC
logNC
Þ. tu
Substituting ad hoc per-MR capacity by the expression
obtained from previous section, the per-MC intracluster
traffic with ad hoc backbone routing is
Cr ¼

NRB
NC
 
; NR ¼ O
NC
logNC
 
^ B ¼ o
Wffiffiffiffiffiffiffi
NR
p
 
;

ffiffiffiffiffiffiffi
NR
p
W
NC
 
; NR ¼ O
NC
logNC
 
^ B ¼ 
Wffiffiffiffiffiffiffi
NR
p
 
;

B
logNC
 
; NR ¼ !
NC
logNC
 
^ B ¼ o
Wffiffiffiffiffiffiffi
NR
p
 
;

W ffiffiffiffiffiffiffi
NR
p
logNC
 
; NR ¼ !
NC
logNC
 
^ B ¼ 
Wffiffiffiffiffiffiffi
NR
p
 
:
8>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>< >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>:
ð63Þ
4.2 Per-MC Capacity with Intracluster AP Traffic
While utilizing a random AP connection, the ratio of the
backbone link bandwidth to the access link bandwidth is
very critical. The traffic via the APs employs the access link.
While it is not sufficient, the benefits from using the random
connections will be limited. An increase in the number of
AP-MRs can help increase the traffic through the APs. The
efficiency of implementing a large number of APs depends
very much on the strategies of traffic load balancing. Our
traffic balance is based on MCs rather than MR cells. The
traffic from the same MR cell may go to different AP-MRs
by considering the traffic load on the AP-MRs.
Proposition 9 is for B ¼ OðWÞ case, where the backbone
link bandwidth is assumed sufficient for the traffic balance
among different AP-MRs. The per-MC capacity with B ¼
!ðWÞ is considered in Propositions 10 and 11 for NA ¼
Oð NC
logNC
Þ and NA ¼ !ð NC
logNC
Þ, respectively.
Proposition 9. If B ¼ OðWÞ, per-MC capacity with intracluster
traffic having random AP access is
Cp ¼ 
NAB
NC
 
: ð64Þ
Proof. Because the traffic can be evenly distributed in the
backbone for intracluster AP traffic, we analyze the
traffic from MCs to APs without any loss of generality.
The traffic of an AP from the MR includes the aggregated
traffic from MCs in the cell and the traffic from other
non-AP-MRs. Non-AP-MR’s intracluster AP traffic can
146 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
go through the backbone and arrive at the AP-MR cells.
With evenly distributed traffic, some of the number of
MCs associate their traffic to the AP-MR and the number
of the MCs associated to an AP-MR is no less than b NC
NAþ1c.
While B ¼ OðWÞ, the capacity is constrained by the
access link. The per-MC traffic in an AP-MR cell is
constrained by
Cp
NC
NA þ 1


 B;
Cp 
NA þ 1
NC
 
B:
ð65Þ
The feasible scheduling will have different situations
for NA and NR.
1. NR ¼ Oð NC
logNC
Þ. According to Lemma 8, the number
of MCs in a cell is upper bounded by c5
NC
NR
w.h.p.
NC
NAþ1 ’s order is no less than c5
NC
NR
, which means the
MCs in an AP-MR is Oð NC
NAþ1Þ and the traffic can
be evenly distributed to the AP-MRs. Since
B ¼ OðWÞ, the traffic is constrained by access link.
For the traffic from the AP-MR cell to the AP(s)
costs twice of the access link bandwidth. We have
Cp
NC
NA þ 1
 
þ supfni
Ag
 
¼ B: ð66Þ
If NR ¼ Oð NC
logNC
Þ, supfni
Ag  c5
NC
NR
according to
Lemma 8. The per-MC traffic follows the following
bound:
Cp 
ðNA þ 1ÞB
NC

1 þ c5
NAþ1
NR

$ %
: ð67Þ
Since NA is no more than NR, we have Cp¼
ðNAB
NC
Þ.
2. NR ¼ !ð NC
logNC
Þ and NA ¼ oð NC
logNC
Þ. Where ni
A is
upper bounded by c6 logNC according to Lemma
9. The order of NC
NAþ1 is ðlogNCÞ, which is
higher than the upper bound of ni
A. So, the
number of cells associated to an AP-MR is more
than one w.h.p. and the traffic can be distributed
and balanced among the AP-MRs. We have the
feasible scheduling derived from (66), which is
Cp 
ðNA þ 1ÞB
NC

1 þ c6
ðNAþ1Þ logNC
NC

$ %
: ð68Þ
Since NA ¼ oð NC
logNC
Þ, we obtain Cp ¼ ðNAB
NC
Þ.
3. NR ¼ !ð NC
logNC
Þ and NA ¼ ð NC
logNC
Þ. ni
A is upper
bounded by c6 logNC according to Lemma 9. The
order of NC
NAþ1 is oðlogNCÞ, which is lower than ni
A.
It means that the number of MCs in a cell may be
more than the average number of MCs for an APMRs.
To perform the traffic balance, some of the
traffic in the AP-MRs that is over NC
NAþ1 needs to be
scheduled to other AP-MR. For the cell having
more than NC
NAþ1 MCs, ni
A  NC
NAþ1 go to the backbone
and rest of the traffic is served by local AP. The
per-MR capacity served by local AP is
Cp 
ðNA þ 1ÞB
2NC


: ð69Þ
The traffic through the backbone follows:
Cp 
W
supfni
Ag  NC
NAþ1
$ %
¼
W
c6 logNC  NC
NAþ1
$ %
: ð70Þ
Since NA ¼ ð NC
logNC
Þ, (70) is not the constraint
and we obtain Cp ¼ ðNAB
NC
Þ.
With the traffic balance algorithm, we can have
Cp ¼ ðNAB
NC
Þ for different situations.
In summary, the proposition holds. tu
In Proposition 9, we implement the proposed traffic
balance algorithm, so it is tighter feasible scheduling bound
than previously given in the literature.
Proposition 10. If B ¼ !ðWÞ and NA ¼ Oð NC
logNC
Þ, per-MC
capacity under intracluster traffic with random AP access is
Cp ¼ 
NAB
NC
 
: ð71Þ
Proof. While B ¼ !ðWÞ, the capacity is constrained by the
backbone bandwidth at the AP-MR. With evenly
distributed MC traffic, the number of MCs associated
to an AP-MR is no less than b NC
NAþ1c. According to Lemma
8, supfni
Ag  c5
NC
NR
. The per-MC traffic has the following
upper bound:
Cp 
W
NC
NAþ1  supfni
Ag

ðNA þ 1ÞW
NCð1  c5
NAþ1
NR
Þ
; ð72Þ
where c5
NAþ1
NR
approaches zero while NC approaches to
infinity.
Now, we consider the feasible scheduling. With
evenly distributed traffic in the backbone, the number
of MCs associated to an AP-MR is no more than d NC
NAþ1e.
By the feasible scheduling, we have
Cp 
ðNA þ 1ÞW
c1NC


: ð73Þ
Equations (72) and (73) yield the result. tu
Proposition 11. If B ¼ !ðWÞ and NA ¼ !ð NC
logNC
Þ, per-MC
capacity under intracluster traffic with random AP access is
Cp ¼ 
W
logNC
 
: ð74Þ
Proof. With traffic balance function, AP-MR traffic should
be NC
NAþ1 . When NA ¼ !ð NC
logNC
Þ, we have
NC
NA þ 1
¼ OðlogNCÞ: ð75Þ
According to Lemma 9, the number of MCs in a cell is
upper bounded by c6 logNC. As compared with (75), we
find that the traffic balance in the backbone cannot
be performed for some cells w.h.p. From (69) and (70), we
find that the per-MC capacity is now constrained by the
backbone bandwidth.
FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 147
From Lemma 10, there exists an MC that is selected by
c7 logNC MCs w.h.p. So, we have the upper bound of the
capacity as
Cp 
B
c7 logNC
: ð76Þ
When the upper bound of the number of MCs in a cell
is c6 logNC, it does not collect the traffic from other non-
AP-MR cells because its traffic is above the average. So,
the feasible uplink per-MC capacity is
Cp 
B
2c6 logNC


: ð77Þ
For the downlink traffic, the analysis is similar to the
proof of Proposition 8 and we also use the upper bound
of nD. The difference is that the traffic is from the AP
then to the MR and does not pass through the backbone
while nD approaches its upper bound. We obtain
Cp 
B
2nD



B
2c11 logNC


: ð78Þ
Thus, the proposition is satisfied. tu
In general, access link bandwidth B¼ð Wffiffiffiffiffi
NR
p Þ. So, the
access link would not be a bottleneck for the per-MC capacity
in ad hoc routing. In this region, the per-MC capacity is
Cr ¼

ffiffiffiffiffiffiffi
NR
p
W
NC
 
; NR ¼ O
NC
logNC
 
^ B ¼ 
Wffiffiffiffiffiffiffi
NR
p
 
;

W ffiffiffiffiffiffiffi
NR
p
logNC
 
; NR ¼ !
NC
logNC
 
^ B ¼ 
Wffiffiffiffiffiffiffi
NR
p
 
:
8>>>>>>>>>>>< >>>>>>>>>>>:
ð79Þ
Since access to APs are random, access link bandwidth is
designed according to the analysis and requirements of a
WMN, which is B ¼ OðWÞ. In this region, the per-MC
capacity with AP routing is
Cp ¼ 
NA
NC
B
 
; B¼ OðWÞ: ð80Þ
4.3 Per-MC Capacity with Intercluster Traffic
Following a similar process of MR intercluster capacity, the
MC intercluster capacity can be derived as follows:
Proposition 12. Per-MC capacity with intercluster traffic
through the IGW is Cg ¼ ðW
NC
Þ.
Proof. The proof is similar to Proposition 4. tu
Proposition 13. Per-MC capacity with intercluster AP traffic is
expressed by
Ce ¼

NAB
NC
 
; B¼ OðWÞ;

NAW
NC
 
; NA ¼ O
NC
logNC
 
^ B ¼ !ðWÞ;

W
logNC
 
; NA ¼ !
NC
logNC
 
^ B ¼ !ðWÞ:
8>>>>>>>< >>>>>>>:
ð81Þ
Proof. Due to the traffic balance and the AP routing scheme,
per-MC capacity computed for intracluster AP traffic is
applicable to intercluster AP traffic. The difference is that
intercluster AP traffic needs to consider both the capacity
constraints as the source and the destination are in the
same cluster. So, we use (70) under case B ¼ !ðWÞ to
derive Ce ¼ ð W
logNC
Þ. The rest procedures are similar to
Proposition 11. tu
5 DISCUSSION AND IMPLICATIONS
MRs can be deployed on electric poles or on the top of house
roofs and can cover hole and/or network area extension.
The power supply for MR operations can come from the
electric poles or the solar panels. With the wireless relay and
routing function, MRs do not need wired cables except for
the IGWs. The feasibility of deployment enables WMNs to
cover any such desired area to take care of decay in the
signal strength and environmental complexity in an urban
area. Throughput of MCs can be improved by accessing
deployed MRs. MCs can have much better Signal to
Interference Noise Ratio (SINR) and higher data transmission
rate by accessing nearby MRs. With preplanned and
optimized deployment, connections among MRs should
have a required data transmission rate. By controlling the
coverage of MRs, the maximum transmission between MC
and its serving MR is also determined, which affects the
quality of the signals and the service. Overall, the system
performance can be improved with specific benefits
discussed above. It is also one of the reasons that IEEE
802.16j [18], IEEE 802.16m [19], and LTE Advanced [20] have
adopted relay stations in their systems to fill the cell
coverage holes and/or enhance the cell capacity.
Grid topology provides a better coverage and an
enhanced capacity than that of a random topology. Grid
deployment discussed in [21] argues for a better coverage
than a hexagonal deployment. While MRs are deployed in
grids, it also naturally matches grid street topology like
Manhattan model. Backbone link between two neighboring
MRs can be within the line of sight and have better channel
condition. On the other hand, grid deployed MRs can
provide better access for MCs along the streets.
In our analytical work, backbone links employ different
frequency bands from that of the access links. Backbone
links among MRs may use licensed band so as to reduce any
unexpected interference and guarantee the backbone
performance. The stability and quality of backbone links
are essential for the quality of service provided to the MCs.
Most of the traffic is delivered via the backbone links. A
poor backbone link may drop traffic flows and lead to chaos
in the network. So, MRs are mostly deployed by the
network operators. They use licensed band that is protected
and seldom interfered by unlicensed band used by wireless
home phone, various monitoring system, WLANs, and so
on. Some present public places may have tens of different
systems using the same unlicensed band. If unlicensed band
is used for a backbone link, signals will largely interfere
with the transmission of a WMN backbone. In contrast, to
facilitate the access of MCs, it is very likely to use unlicensed
band and protocols for access link of MR cells. To be
compatible with many current mobile devices, contention
based protocols like IEEE802.11 are most likely to be used
for access links between MRs and MCs. Roaming MCs can
148 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013
recognize MR cells and connect to them for access. When
MC moves from a cell to a neighboring cell, the backbone
performs the handover to maintain service continuity for
the MC.
WMN is a cost efficient way to provide network access
service for a wide region. However, the capacity constraint
due to multiple hop transmission is still the drawback to
overcome before having a wider acceptance. As discussed
early, the per-MR capacity is

W ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi
NR logNR
p
 
:
By optimizing the placement, it approachesð Wffiffiffiffiffi
NR
p Þ. Utilizing
random connection to APs can improve the capacity
significantly, especially when the number of AP-MRs is
increased. With a large number of MRs and WLAN APs that
have been deployed, the average number of such AP
connections is large. Per-MR capacity can be increased up
to NABþW
NR
. Because random connection is utilized only for a
single hop between MR and AP, it is still highly reliable as
compared to a pure multihop random network.
As an Internet gateway, the backbone link bandwidth W
of the IGW is constrained by the maximum throughput of
the intercluster traffic if without random AP access. It
serves as the lower bound of intercluster traffic performance
if there is no constraint on the access link bandwidth.
By adjusting the number of IGWs deployed in a region, it
controls the coverage area of every cluster led by an IGW.
While the density of MCs is given, smaller cluster coverage
area means smaller number of MCs in a cluster and more
intercluster traffic per MC can be supported. An extreme
case of increasing the number of IGWs is to form a multicell
single hop network architecture like GSM base stations.
This is not as cost-efficient because the cost to deploy such a
network is ðNIGWÞ.
Given a cluster with fixed coverage, increasing the density
of MRs could improve the per-MC capacity with intracluster
traffic. Assume that the access link bandwidth is not the
bottleneck, i.e., B ¼ ð Wffiffiffiffiffi
NR
p Þ. The increase in the MR density
have two different effects: when the number of MRs in a
unit square is less than a threshold of Oð NC
logNC
Þ, the per-MC
capacity increases with
ffiffiffiffiffiffiffi
NR
p
. When the number of MRs
reaches or runs over the threshold, the per-MC capacity with
intracluster traffic starts to degrade. Thus, it is important to
consider the upper bound and choose an appropriate
number of MRs for an optimal performance.
Random access to APs has positive impact on both
intercluster traffic and intracluster traffic. With access to
APs, intracluster traffic has the routing shortcut through the
wired connection between APs. Intracluster traffic path like
MC-(-MR)k-MC can be changed like MC-(-MR)i-AP-AP-(-
MR)j-MC, where i, j, and k denote the number of intermediator
MRs and i þ j < k. In that case, not only the capacity can be improved but also the delay can be decreased. The wired connection is assumed to have enough throughput and the transmission delay between two APs is less than k  ði þ jÞ hops. Per-MC capacity with intercluster traffic is also improved with AP access. Intercluster traffic would not be constrained by the IGW, as the traffic can go through the APs and the wired connection of APs to other clusters or the Internet. It is noticeable that the wireless access between MRs and APs use the same type of air interfaces as that between MRs and MCs. So, it is easy for MRs to utilize the APs that are widely deployed, without drastic changes in the network functions. MR can take the APs as special MCs. The difference is that the MR needs to be aware of wired connection of APs to the Internet and redirect the traffic to the APs or in the reverse direction. The reasons that MCs in an AP-MR cell connect to the MRs rather than to the APs in the cell directly, differ on the following aspects. APs usually assume the access clients are static while MRs assume the MCs having mobility and provide better channel estimate for optimizing the link performance. MCs can have better response if connected to the MR. MRs can perform access control for QoS and security purposes. It is unconventional to have such functions for the random access APs. In addition, the handover for MCs can be supported by MRs. With the information exchange in the backbone, MCs are able to handover from the serving MR to a neighboring MR. These functions are naturally supported by the MRs. APs are only able to serve as tunnels for the traffic. The number of AP-MRs has a different level of impact on the capacity. For intracluster traffic, the capacity of intracluster traffic increases with ffiffiffiffiffiffiffi NR p if NR ¼ Oð NC logNC Þ. With the random access to APs, the capacity is improved by the number of AP-MRs. If NA ¼ OðW B ffiffiffiffiffiffiffi NR p Þ, the capacity is still predominated by the traffic with ad hoc routing in the backbone. However, if NA ¼ !ðW B ffiffiffiffiffiffiffi NR p Þ, the capacity is then dominated by random access to the APs and the asymptotic capacity becomes ðNAB NR Þ. On the other hand, if there is a large number of MRs in the cluster that NR ¼ !ð NC logNC Þ, NA would have similar effect. If NA¼!ð WNC B ffiffiffiffiffi NR p logNC Þ, the asymptotic capacity is ðNAB NC Þ. For the intercluster traffic, the increase of MRs accessing to APs almost linearly increase the asymptotic capacity while access link is not the bottleneck. Under these situations, increasing cell access link bandwidth will almost linearly increase the per-MC capacity. This is a significant enhancement to the capacity. In this three-tier network, backbone link bandwidth W, and access link bandwidth B, not only their absolute value but also their ratio, determine the bottleneck of the network. For the intracluster traffic, the capacity will be bounded by the access link if B ¼ oð Wffiffiffiffiffi NR p Þ. Then, the per-MC capacity is determined by the number of MCs in a cell, which leads to the asymptotic capacity ðNRB NC Þ. Under this situation, the access to APs does not have much effect on the capacity. When B ¼ ð Wffiffiffiffiffi NR p Þ and NA ¼ OðW ffiffiffiffiffi NR p B Þ, access link is no longer the bottleneck. When NA ¼ !ðW ffiffiffiffiffi NR p B Þ, the role is changed again and the increase for the bandwidth of access link will increase the capacity. Thus, the access link bandwidth should be large enough so that it would not be the bottleneck of the network. According to the derivation in previous sections, B ¼ ð Wffiffiffiffiffi NR p Þ^B ¼ OðWÞ. If B ¼ oð Wffiffiffiffiffi NR p Þ, the network capacity will be seriously constrained by the access link bandwidth. If B ¼ !ðWÞ, access link bandwidth will be wasted if there are no enough random APs connections. While taking B ¼ ð Wffiffiffiffiffi NR p Þ ^ B ¼ OðWÞ, the values ofNR,NA,W, and B mutually affect each other for the asymptotic per-MC capacity. FU AND AGRAWAL: CAPACITY OF HYBRID WIRELESS MESH NETWORKS WITH RANDOM APS 149 6 CONCLUSION In this paper, we have derived asymptotic capacity of a hybrid WMN architecture with random connections to APs. With this, the access link bandwidth greatly affects the capacity, which is different from a conventional WMN. To some extent, the ratio of access link bandwidth to backbone link bandwidth is critical. It dominates the capacity bottleneck and magnifies the influence of AP-MRs. Theoretical results show that the capacity enhancement by accessing APs within the coverage of MRs is significant with an increase in the number of AP-MRs and the bandwidth ratio. The improvement is at the very low cost by utilizing currently available networks and it is also possible for those networks to take advantage of a WMN. It should be noted that the access to the APs are random, it may have negative impact on WLANs’ performance when the WLANs’ traffics are heavy. In the future work, we plan to consider the traffic between MRs and WLANs so as to have a control mechanism that takes the traffic load at the APs into account. REFERENCES [1] N. Nandiraju, D. Nandiraju, L. Santhanam, B. He, J. Wang, and D.P. Agrawal, “Wireless Mesh Networks: Current Challenges and Future Directions of Web-in-the-Sky,” IEEE Wireless Comm., vol. 14, no. 4, pp. 79-89, Aug. 2007. [2] C. Cordeiro and D.P. Agrawal, Ad Hoc & Sensor Networks: Theory and Applications. World Scientific, 2006. [3] P. Gupta and P. Kumar, “The Capacity of Wireless Networks,” IEEE Trans. Information Theory, vol. 46, no. 2, pp. 388-404, Mar. 2000. [4] B. He, B. Xie, and D.P. Agrawal, “Optimizing the Internet Gateway Deployment in a Wireless Mesh Network,” Proc. IEEE Int’l Conf. Mobile Adhoc and Sensor Systems (MASS), 2007. [5] B. Liu, Z. Liu, and D. Towsley, “On the Capacity of Hybrid Wireless Networks,” Proc. IEEE INFOCOM, 2003. [6] U.C. Kozat and L. Tassulas, “Throughput Capacity of Random Ad Hoc Networks with Infrastructure Support,” Proc. ACM MobiCom, 2003. [7] A. Zemlianov and G. Veciana, “Capacity of Ad Hoc Wireless Networks with Infrastructure Support,” IEEE J. Selected Area in Comm., vol. 23, no. 3, pp. 657-667, Mar. 2005. [8] P. Zhou, X. Wang, and R. Rao, “Asymptotic Capacity of Infrastructure Wireless Mesh Networks,” IEEE Trans. Mobile Computing, vol. 7, no. 8, pp. 1011-1024, Aug. 2008. [9] I.F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks:A Survey,” Computer Networks, vol. 47, no. 4, pp. 445-487, Mar. 2005. [10] P. Kyasanur and N.H. Vaidya, “Capacity of Multi-Channel Wireless Networks: Impact of Number of Channels and Interfaces,” Proc. ACM MobiCom, 2005. [11] M. Kodialam and T. Nandagopal, “Characterising the Capacity Region in Multi-Radio Multi-Channel Wireless Mesh Networks,” Proc. ACM MobiCom, 2005. [12] D.P. Agrawal and Q. Zeng, Introduction to Wireless and Mobile Systems. Thomson Brooks/Cole, 2003. [13] P. Gupta and P. Kumar, “Internets in the Sky: The Capacity of Three Dimensional Wireless Networks,” Comm. in Information and Systems, vol. 1, pp. 33-50, 2001. [14] M. Mitzenmacher and E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge Univ., 2005. [15] P. Santi, Topology Control in Wireless Ad Hoc and Sensor Networks. Wiley, 2005. [16] W. Fu, B. Xie, X. Wang, and D. Agrawal, “Flow-Based Channel Assignment in Channel Constrained Wireless Mesh Networks,” Proc. 17th Int’l Conf. Computer Comm. and Networks (ICCCN), 2008. [17] J. Jun and M.L. Sichitiu, “The Nominal Capacity of Wireless Mesh Networks,” Wireless Comm., vol. 10, no. 5, pp. 8-14, Oct. 2003. [18] IEEE 802.16 Broadband Wireless Access Working Group, Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems - Multihop Relay Specification, IEEE, 2004. [19] IEEE 802.16 Broadband Wireless Access Working Group, The Draft IEEE 802.16m System Description Document, IEEE, 2008. [20] E. Dahlman, H. Ekstrom, A. Furuskar, Y. Jading, J. Karlsson, M. Lundevall, and S. Parkvall, “The 3G Long-Term Evolution-Radio Interface Concepts and Performance Evaluation,” Proc. IEEE Vehicular Technology Conf., 2006. [21] J. Robinson and E. Knightly, “A Performance Study of Deployment Factors in Wireless Mesh Networks,” Proc. IEEE INFOCOM, 2007. Weihuang Fu received the BS degree in communications engineering and the MS degree in communication and information systems from the Zhejiang University of Technology, China, in 2002 and 2005, respectively, and the PhD degree in computer science and engineering from the University of Cincinnati, Ohio, in 2010. He joined Cisco Systems, Inc., in 2010. He has been a technical program committee member of many international conferences and a technical reviewer of numerous international journals and conference proceedings. His research interests include network modeling and analysis, MAC/ routing protocol for wireless multihop networks, and mobility management. He is a member of the IEEE and the IEEE Computer Society. Dharma P. Agrawal is the Ohio Board of Regents distinguished professor in the School of Computing Sciences and Informatics and the founding director for the Center for Distributed and Mobile Computing at the University of Cincinnati, Ohio. He was a visiting professor of electrical and computer engineering at the Carnegie Mellon University on sabbatical leave during the autumn 2006 and winter 2007 quarters. He was a faculty member at North Carolina State University, Raleigh from 1982-1998 and at Wayne State University, Detroit from 1977-1982. His current research interests include energy-efficient routing and information retrieval in sensor and mesh networks, QoS in integrated wireless networks, use of smart multibeam directional antennas for enhanced QoS, various aspects of sensor networks including environmental monitoring, and secured communication in ad hoc and sensor networks. His coauthored textbook, Introduction to Wireless and Mobile Systems, third edition published by Cengage Corp., has been adopted throughout the world and revolutionized the way the course is taught. His second coauthored textbook, Ad Hoc and Sensor Networks, second edition, was published by World Scientific. He has served as an editor of the IEEE Computer, the IEEE Transactions on Computers, and the International Journal of High Speed Computing. He is an editor for the Journal of Parallel and Distributed Systems, International Journal on Distributed Sensor Networks, International Journal of Ad Hoc and Ubiquitous Computing (IJAHUC), International Journal of Ad Hoc and Sensor Wireless Networks, and Journal of Information Assurance and Security. He has been the program chair and general chair for numerous international conferences and meetings. He has received numerous certificates and awards from the IEEE Computer Society. He was awarded a “Third Millennium Medal” by the IEEE for his outstanding contributions. He has also delivered keynote speeches for five international conferences. He has five patents and 23 patent disclosures in the area of wireless networking. He served as a fulbright senior specialist for five years and was the founding editor-in-chief of the Central European Journal of Computer Science, Versita. He has graduated 62 PhD and 51 MS students and was also named as an ISI Highly Cited Researcher in computer science. He won the 2008 Harry Goode Memorial award from the IEEE Computer Society and the 2011 Award for Excellence in Mentoring of Doctoral Students, University of Cincinnati. He is a fellow of the IEEE, IEEE Computer Society, ACM, AAAS, and WIF. 150 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 12, NO. 1, JANUARY 2013

Comments are closed.