in Proceedings of
61
st
IEEE Vehicular Technology Conference (VTC 2005 Spring),
Stockholm, Sweden, May 29-June 1, 2005
Interference-Aware IEEE 802.16 WiMax Mesh
Networks
Hung-Yu Wei, Samrat Ganguly, Rauf Izmailov
Broadband & Mobile Networking Department
NEC Laboratories America
Princeton, New Jersey, USA
{hungyu, samrat, rauf}@nec-labs.com
Zygmunt J. Haas
School of Electrical and Computer Engineering
Cornell University
Ithaca, New York, USA
haas@ece.cornell.edu
Abstract—
The IEEE 802.16 WiMax standard provides a
mechanism for creating multi-hop mesh, which can be deployed
as a high speed wide-area wireless network. To realize the full
potential of such high-speed IEEE 802.16 mesh networks, two
efficient wireless radio resource allocation extensions were
developed. The objective of this paper is to propose an efficient
approach for increasing the utilization of WiMax mesh through
appropriate design of multi-hop routing and scheduling. As
multiple-access interference is a major limiting factor for wireless
communication systems, we adopt here an interference-aware
cross-layer design to increase the throughput of the wireless mesh
network. In particular, our scheme creates a tree-based routing
framework, which along with scheduling is interference aware
and results in a much higher spectral efficiency. Performance
evaluation results show that the proposed interference-aware
scheme achieves significant throughput enhancement over the
basic IEEE 802.16 mesh network.
Keywords-IEEE 802.16, Mesh Network, WiMax, Cross-layer
Design and Optimization, Multi-hop Routing, Mesh Mode
flexibility to attain Quality of Service in terms of data
throughput, achieving the same in multi-hop WiMax mesh is
challenging. One of the major problem is dealing with the
interference from transmission of the neighboring WiMax
nodes.
Cross-layer design and optimization is known to improve
the performance of wireless communication and mobile
networks [3,4]. In order to design a spectrally efficient IEEE
802.16 mesh network, we opt for joint design and optimization
that relies on Application Layer load demand information,
Physical Layer interference information, as well as scheduling
and route selection mechanism in Data Link Layer. We believe
that interference in wireless systems is one of the most
significant factors that limit the network capacity and
scalability of wireless mesh networks. Consideration of
interference conditions during radio resource allocation and
route formation processes impacts the design of concurrent
transmission schemes with better spectral utilization while
limiting the mutual interference.
We developed an interference-aware IEEE 802.16
framework with a design goal of achieving overall high
utilization of the WiMax Mesh network. Our proposed scheme
includes a novel interference-aware route construction
algorithm and an enhanced centralized mesh scheduling
scheme, which consider both traffic load demand and
interference conditions. This interference-aware design
approach will lead to better spatial reuse and thus higher
spectral efficiency.
The rest of the paper is organized as follows: in Section II,
we briefly overview the IEEE 802.16 Mesh mode operation. In
Section III, we present the interference-aware framework that
includes route construction and scheduling algorithm. In
Section IV, the IEEE 802.16 mesh network performance is
evaluated via simulations and compared to theoretical upper
bound, which we found using linear programming. Finally, we
summarize our results and provide some concluding remarks in
Section V.
I.
I
NTRODUCTION
The IEEE 802.16 Working Group created a new standard,
commonly known as WiMax, for broadband wireless access at
high speed, at low cost, which is easy to deploy, and which
provides a scalable solution for extension of a fiber-optic
backbone. WiMax base stations can offer greater wireless
coverage of about 5 miles, with LOS (line of sight)
transmission within bandwidth of up to 70 Mbps.
Beyond just providing a single last hop access to a
broadband ISP, WiMax technology can be used for creating
wide-area wireless
backhaul
network. When a backhaul-based
WiMax is deployed in
Mesh
mode, it does not only increase the
wireless coverage, but it also provides features such as lower
backhaul deployment cost, rapid deployment, and re-
configurability. Various deployment scenarios include citywide
wireless coverage, backhaul for connecting 3G RNC with base
stations, and others.
In addition to the single-hop IEEE 802.16 PMP (point-to-
multipoint) operation, IEEE 802.16a standard [1] defined the
basic signaling flows and message formats to establish a mesh
network connection. Subsequently, the Mesh mode
specifications were integrated into the IEEE 802.16-2004
revision [2]. Although single hop WiMax provides high
II.
O
VERVIEW OF
W
I
M
AX
M
ESH
A. Motivation and Problem Overview
In comparison to IEEE 802.11a/b/g based mesh network,
the 802.16-based WiMax mesh provides various advantages
apart from increased range and higher bandwidth. The TDMA
based scheduling of channel access in WiMax-based multi-hop
relay system provides fine granularity radio resource control, as
compared to RTS/CTS-based 802.11a/b/g systems. This
TDMA based scheduling mechanism allows centralized slot
allocation, which provides overall efficient resource utilization
suitable for fixed wireless backhaul network. (The WiMax-
based mesh backhaul application differs from the 802.11a/b/g-
based mesh, which targets mobile ad hoc networks.) However,
the interference remains a major issue in multi-hop WiMax
mesh networks. To provide high spectral usage, an efficient
algorithm for slot allocation is needed, so as to maximize the
concurrent transmissions of data in the mesh. The level of
interference depends upon how the data is routed in the WiMax
network.
In this paper, we consider the following scenario of
WiMax-based mesh deployment. A mesh network is managed
by a single node, which we refer to as Mesh BS. Mesh BS
serves as the interface for WiMax-based mesh to the external
network. We provide an algorithm for interference-aware
multi-hop route selection for a given capacity-request matrix,
which leads to efficient scheduling.
TABLE I.
BS
SS
MSH
SN
CN
MSH-NCFG
MSH-NENT
MSH-CSCH
MSH-CSCF
IEEE 802.16 M
ESH
M
ODE
A
CRONYMS
Base Station
Subscriber Station
Mesh
Sponsoring Node
Candidate Node
Mesh network Configuration Message
Mesh Network Entry Message
Mesh Centralized Scheduling Message
Mesh Centralized Scheduling Configuration Message
messages are used for advertisement of the mesh network and
for helping new nodes to synchronize and to joining the mesh
network. Active nodes within the mesh periodically advertise
MSH-NCFG messages with Network Descriptor, which
outlines the basic network configuration information such as
BS ID number and the base channel currently used. A new
node that plans to join an active mesh network scans for active
networks and listens to MSH-NCFG message. The new node
establishes coarse synchronization and starts the network entry
process based on the information given by MSH-NCFG.
Among all possible neighbors that advertise MSH-NCFG, the
joining node (which is called
Candidate Node
in the 802.16
Mesh mode terminology) selects a potential
Sponsoring Node
to connect to. A Mesh Network Entry message (MSH-NENT)
with NetEntryRequest information is then sent by the
Candidate Node to join the mesh.
The IEEE 802.16 Mesh mode MAC supports both
centralized scheduling and distributed scheduling. Here, we
focus on the centralized mesh scheme to establish high-speed
broadband mesh connections, where the Mesh BS coordinates
the radio resource allocation within the mesh network. In the
centralized scheme, every Mesh SS estimates and sends its
resource request to the Mesh BS, and the Mesh BS determined
the amount of granted resources for each link and
communicates. The request and grant process uses the
Mesh
Centralized Scheduling (MSH-CSCH)
message type. A
Subscriber Stations capacity requests are sent using the
MSH-
CSCH:Request
message to the Subscriber Station’s parent
node. After the Mesh BS determines the resource allocation
results, the
MSH-CSCH:Grant
is propagated along the route
from Mesh BS. To disseminate the link, node, and scheduling
tree configuration information to all participants within the
mesh network, the
Mesh Centralized Scheduling Configuration
(MSH-CSCF)
message is broadcasted by the Mesh BS and then
re-broadcasted by intermediate nodes.
III.
I
NTERFERNCE
-A
WARE DESIGN
W
ITH
802.16 M
ESH
B. IEEE 802.16 Mesh Mode Operations
In IEEE 802.16 Mesh mode, a Mesh
base station (BS)
provides backhaul connectivity of the mesh network and
controls one or more
subscriber stations (SS).
When
centralized scheduling scheme is used, the Mesh BS is
responsible for collecting bandwidth request from subscriber
stations and for managing resource allocation. We will first
introduce the 802.16 Mesh network entry process (i.e., a
process by which a new node joins the mesh), and then we
describe the network resource allocation request/granting
procedure.
In IEEE 802.16 Mesh mode, Mesh Network Configuration
(MSH-NCFG) and Mesh Network Entry (MSH-NENT)
A. Interference-Aware Route Construction
To achieve efficient spectral utilization and high throughput
in 802.16 mesh networks, the route construction within the
mesh network is crucial. To this end, we propose an
interference-aware route construction algorithm that considers
interference condition in the mesh network. The concept of
blocking metric B(k)
of a given route from the Mesh BS toward
an SS node
k
is introduced to model the interference level of
routes in the mesh.
The
blocking metric B(k) of a multihop route
indicates the
number of blocked (interfered with) nodes by all the
intermediate nodes along the route from the root node toward
the destination node
k.
We also define the
blocking value
b(
η
)
of a node
η
,
as the number of blocked (interfered with) nodes
when node
η
is transmitting. Therefore, the blocking metric of
a route will be the summation of the blocking values of nodes
that transmit or forward packets along the route. A simple
example of blocking metric computation is shown in Figure 1.
In this example, a node is blocked when it is within the
transmission range of the transmitting node. Thus, node
η
i
’s
blocking value
b(
η
i
) equals the number of neighboring nodes of
η
i
.
The blocking metric along a route toward
k, B(k)
is equal to
the summation of all the blocking value b(
η
i
) for every node
η
i
(including the source node and all the forwarding nodes) on the
route
k.
In the example in Figure 1,
B(k)
is computed by adding
b(s), b(n1), b(n2), and b(n3).
As shown in Figure 1, nodes are blocked if their
transmissions would interfere with the currently receiving
node. Similarly, Figure 2 shows an example of blocking metric
computation of a route with larger interference than the
example in Figure 1. Our design approach in the proposed
interference-aware scheme is to select the routes with less
interference. For the clarity of illustration in Figure 1 and 2, the
blocking metric computation presented here shows a simplified
case, where only nodes within the transmission range of a
transmitting node are blocked. In various scenarios, a
transmitting node could interfere with nodes that are in a larger
distance away. Other types of blocking metrics (such as
detailed propagation model or measurement with receiver
sensitivity) could be defined based on the information
availability and system design tradeoffs.
¦
¥
¥
¤
¦
£
¢
¢
§
¡
S
←
{0}
//node 0 is the root node; Initialize the set of selected nodes
N
S
←
{1,2,...,
n
} //Initialize the set of unselected nodes
p
(
i
)
← ∅
,
i
∈
{1,2,...,
n
}
Do if N
S
≠ ∅
//Initialize parent node for node 1,2,…,n
η
←
arg max
σ
(
i
) //Node
η
with high
σ
(
η
) value joins first
i
∈
N
S
Neighbor
(
S
)
C(
η
)
←
Neighbor
(
η
) //All nodes within transmission distance of
η
W
(
η
)
←
C
(
η
)
S
i
∈
W
(
η
)
©
p
(
η
)
←
arg min
B
(
i
) //Select the node with minimum blocking
Add
η
to S
Remove
η
from N
S
END
Figure 3. Interference-Aware Route Construction Algorithm
s
s
n1
s
s
b(2)=4
n2
b(1)=2
b(3)=3
n3
b(4)=4
d
d
d
d
Figure 1. An exmple of blocking metric
B(k)=2+4+3+4=13
s
s
s
s
b’(2)=4
b’(1)=2
b’(3)=5
b’(4)=4
d
d
d
d
B. Interference-Aware Scheduling
The design goal of the proposed interference-aware
scheduling is to exploit concurrent transmission opportunity to
achieve high spectral utilization and hence high system
throughput. The interference-aware scheduling seeks to
maximize the number of concurrent transmissions, without
creating exceeding interference for other simultaneous
transmission. This is achieved by taking into the consideration
the traffic capacity request of each SS. We denote the capacity
request of an SS node
k
from the Mesh BS as
D(k).
The Mesh
BS grants radio resource according to the Application Layer
capacity requests,
D(k)-s,
of all SS nodes and the route
information of the mesh network.
We show the interference-aware scheduling algorithm in
Figure 4. With the obtained route information from network
entry and the initialization process, the node capacity request
D(k)
can also be equivalently represented in terms of link
demands
Y(j)
for every link j. The scheduling algorithm
iteratively determines
ActiveLink(t),
which is the set of active
links at the time
t.
In each allocation iteration
t,
a link with the
highest unallocated traffic demand is selected for next
allocation of a unit traffic. The scheduling algorithm is
designed to find the maximum number of concurrent
transmissions. To satisfy the SINR constraints of concurrent
transmissions, the
Blocked_Neighbor(k)
function is used to
exclude interfering links that are located in the neighborhood of
k.
The iterative allocation continues until there is no
unallocated capacity request.
Figure 2. Blocking metric of an alternative route
B(k)=2+4+5+4=15
We show the interference-aware route construction
algorithm in Figure 3. Beginning with a single Mesh BS node,
we add one SS into the mesh at a time. The time sequence of
node
η
joining the mesh is represented by
σ(
η
). When the SS
node
η
joins the mesh, it will select the Sponsoring Node with
the minimum blocking.
In the interference-aware route construction scheme, the
blocking metric information is incorporated into the Network
Descriptor of a MSH-NCFG message. When a new node is
scanning for active network during the network entry process,
the new node chooses the potential Sponsoring Node based on
the blocking metric information to reduce the interference of
the multihop route and hence to improve the throughput.
¨
//Candidate parent nodes of node
η
t
←
1
While exist any
Y(j)>0
for any link j
k
←
arg max Y(j)
//select link k
∀
j
B
←∅
// set of blocked links in this iteration
A
←∅
// set of selected active links in this iteration
k
≠∅
While
Add k to A
Add
Blocked_Neighbor(k)
to B
k
←
arg max Y(j)
j
∉
A
∪
B
;
Y
(
j
)
>
0
The optimal solutions of the linear programming algorithm,
is used as a performance comparison benchmark for the
proposed interference-aware 802.16 mesh network scheme.
Since the optimal linear programming algorithm is computed
based on arbitrarily slicing of time fractions of all feasible
transmission combinations, the performance of the discrete-
time event driven design of proposed schemes is capped by the
performance of the linear programming algorithm. Thus the
performance of the linear programming algorithm serves as an
upper bound.
End while
Figure 4. Interference-Aware Scheduling Algorithm
L
(
α
) /
x
(
j
)
S
(
α
,
j
)
=
L
(
β
) /
∀
j
x
(
j
)
≤
1,
j
∈
{1, 2,...,
M
}
∀
j
IV. P
ERFRORMANCE
E
VALUATION
We have evaluated the system throughput of IEEE 802.16
mesh in two scenarios: a linear chain topology and a random
mesh topology. The proposed schemes are compared to the “no
spatial reuse MSH-CSCH” scheduling example given in IEEE
802.16a standard [1], which we refer to in this paper as the
basic scheme. To see how the 802.16 mesh schemes perform,
we also investigate a theoretical upper-bound based on linear
programming. The network throughput of the basic 802.16
scheme and the proposed interference-aware scheme are
simulated on the Matlab platform.
A. Optimal Solution From Linear Program
A linear programming algorithm is formulated to model the
network throughput upper bound of IEEE 802.16 mesh
networks. Similar to the modeling technique demonstrated in
[5], the network activity is modeled in terms of the normalized
time fraction as a real number between 0 and 1. The set
S
represents all the possible transmission schemes in terms of
link bandwidth
R
(bits/second). In a given transmission scheme
j with active transmitting node
t
and receiving nodes
r, S(t,j)
is
set to -R(t,r)
,
the link bandwidth between the node pair (t,r), if
node
t
is transmitting to node
r,
and
S(r,j)
is set to
+R(t,r).
All
other
S(x, j)
are set to 0 if node
x
is neither transmitting nor
receiving in the
j-th
transmission scheme. In a transmission
scheme, multiple concurrent transmissions are allowed, if all
receiving conditions are satisfied. The variable
x(j)
represents
the normalized time fraction that the
j-th
transmission scheme
is active in unit time. At all receivers, it is required that
SINR(j)>γ, which is the minimum reception SINR threshold.
The objective function of this linear programming
algorithm is to maximize the overall network throughput. A
resource allocation constraint is imposed to ensure fair
throughput allocation among users. End-to-end throughput is
proportionally allocated based on the parameter
L; i.e.,
user
α
will be allocated the end-to-end throughput proportional to
L(
α
).
In addition, the summation of all transmission time
fractions
x(j)
should be less than unit time.
0
≤
x
(
j
)
≤
1
Figure 5. The Linear Programming Algorithm
B. Throughput Performance in Chain Topology
The first scenario considers only the scheduling problem in
a chain topology IEEE 802.16 multihop network. In this chain
topology, route construction is straightforward; i.e., data
packets are always forwarded along the chain. Here, we
investigate the effectiveness of interference-aware scheduling.
The throughput of the basic 802.16 mesh network without
interference-aware scheduling is compared to that of the
proposed scheme and to the upper bound obtained from the
linear programming algorithm. As shown in Figure 6, the
proposed interference-aware scheduling scheme performance
approaches the upper bound, while outperforms the basic
802.16 mesh mode significantly.
Also as shown in the figure, the number of nodes in this
multihop 802.16 network affects the possibility of concurrent
transmissions and hence adversely affects the network
throughput. In the basic 802.16 mesh scheme, the network
throughput drops significantly as the number of nodes
increases, because of the limited spatial reuse. On the other
hand, with the interference-aware concurrent transmission, the
normalized overall throughput degrades significantly less as the
number of nodes increases.
The proposed interference-aware scheduling scheme is
more scalable than the basic scheme. As the length of relay
route increases with the number of nodes in the network, the
overall network throughput decreases due to the fact that a
packet needs to be forwarded several times. If the increase in
the degree of spatial reuse is less than the increase of number of
hops, the network throughput will decrease. Depending on the
number of relay hops and the network topology, there are
limitations on the degree of spatial reuse that could be
achieved. By comparing the results of the optimal linear
programming algorithm, we concluded that our proposed
¢
¢
End while
ActiveLinks(t)
←
A
t
←
(
t
+
1)
Y(j)
←
Y(j)-1
∀
j
∈
A
Maximize
Such that
¡
x
(
j
)
S
(
i
,
j
)
i
>
1
∀
j
x
(
j
)
S
(
β
,
j
) ,
∀
α
,
β
∈
{1, 2,...,
N
}
∀
j
£
scheme could achieve a near-optimal network throughput and
spatial utilization.
randomly selects a Sponsoring Node in the random routing
scheme. This type of route construction is denoted as random
routing in Figure 7. Both, the proposed interference-aware
scheduling and the basic 802.16 mesh scheduling were
simulated. Similar to the chain topology scenario, we discuss
the overall network throughput decreases as the number of
nodes increases. As shown in Figure 7, the scheme with both,
the interference-aware routing and the scheduling achieves the
highest network throughput. The “interference-aware routing
only” scheme has the second best performance. The
“interference-aware scheduling only” scheme also outperforms
the basic 802.16 mesh scheme. As a result, we conclude that
the proposed interference-aware framework could effectively
enhance the basic IEEE 802.16 Mesh mode operation. In the
design process of scheduling and route construction in mesh
network, one should adopt the interference-aware design
concept and hence exploit the benefit of concurrent
transmissions with less interference. Consequently, the spectral
utilization in mesh networks is enhanced with less interference
and more spatial reuse.
Figure 6. Overall throuhgput of a chain topology 802.16 network
C. Throughput Performance in Random Topology
In the second scenario, we considered both scheduling and
routing in a random-topology 802.16 mesh network. Locations
of a set of mesh nodes are randomly generated. The order of
nodes joining the mesh is not correlated with the nodes’
locations, but is randomly determined. The mesh formation
begins with the Mesh BS node. Then the SS nodes join one-by-
one. Any node that has already joined the mesh network could
become a Sponsoring Node. When a new node joins the
existing mesh network, depending on the number of candidate
SNs within the new node’s transmission range, it may hear
multiple MSH-NCFG advertisement messages.
V. C
ONCLUSIONS
Allowing concurrent transmissions to achieve high spatial
reuse is essential for scalable wireless mesh network design.
We proposed an interference-aware research framework for the
emerging IEEE 802.16 Mesh mode to improve spectral
utilization. Using this framework, we introduced an
interference-aware route construction algorithm for 802.16
mesh network initialization process to improve the network
throughput by selecting routes with minimal interference to
existing nodes. In addition, a load-aware and interference-
aware scheduling algorithm for centralized scheduling in IEEE
802.16 Mesh mode is also discussed. Simulation results show
that the proposed schemes effectively improve the network
throughput performance in IEEE 802.16 mesh networks and
achieve high spectral utilization.
R
EFERENCES
[1]
IEEE Std 802.16a-2003, "IEEE Standard for Local and metropolitan
area networks--Part 16: Air Interface for Fixed Broadband Wireless
Access Systems--Amendment 2: Medium Access Control Modifications
and Additional Physical Layer Specifications for 2-11 GHz," 2003
IEEE Std 802.16-2004 (Revision of IEEE Std 802.16-2001), "IEEE
Standard for Local and Metropolitan Area Networks Part 16: Air
Interface for Fixed Broadband Wireless Access Systems," 2004
M. Conti, G. Maselli, G. Turi, and S. Giordano, "Cross-layering in
mobile ad hoc network design," IEEE Computer, vol. 37, pp. 48-51,
2004.
S. Shakkottai, T. S. Rappaport, and P. C. Karlsson, "Cross-layer design
for wireless networks," IEEE Communications Magazine, vol. 41, pp.
74-80, 2003
S. Toumpis and A.J. Goldsmith, “Capacity Regions For Wireless Ad hoc
Networks,” IEEE International Conference on Communications (ICC),
2002
[2]
[3]
[4]
Figure 7. Throuhgput performance of a random topology 802.16 mesh
[5]
In the interference-aware routing scheme, the new node
selects the Sponsoring Node as the candidate SN with the
minimum blocking metric. For comparison, the new node
京公网安备 11010802033920号
Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved
评论