have been applied for power control and rate control prob-
lem in wireless networks, which assume the parameters
are varying in a predetermined uncertainty set. However,
the varying range of channel gain and external interference
is generally unknown or unbounded in real environment.
In [12,13], the concept of interference margin is adopted
to characterize the network robustness. It was demon-
strated that the network robustness can be improved by
optimizing the interference margin. However, [12,13] are
focused on the link-level resource provisioning. In this
work, we consider the multi-hop wireless mesh networks
with end-to-end traffic requirements. We incorporate the
concept of interference margin and outage probability,
which can better characterize the robustness of network
under homogeneous and heterogeneous wireless channel
conditions. Our previous work [26] shows that this prob-
lem is more challenging since it involves the jointly opti-
mization of routing, radio-channel assignment, and link
rate selection.
In MR–MC mesh networks, each radio can operate in
multiple orthogonal channels. This property has been
exploited in some research work. In [10,3,5,6], each radio
is tuned to a particular channel for a relatively long period
of time even if the radio is utilized by multiple links. In
[27,28,12], each radio is allowed to switch among available
channels on a per-packet basis, so that different links asso-
ciated with the same radio can be assigned to different
channels. However, such dynamic channel assignment
schemes require additional coordination mechanisms to
ensure that both the transmitting and receiving radios
are operating on the same channel to start the transmis-
sions. In [15], Kyasanur et al. propose a hybrid radio
switching scheme which requires no additional coordina-
tion while keeping the flexibility of dynamic channel
assignment. We adopt the hybrid scheme in this work.
3. System models
We consider a MR–MC mesh network that can be mod-
eled by a directed multigraph
1
G¼ðN; LÞ, where G is re-
ferred to as the connected graph of the network. A node
n 2N is a wireless mesh node with multiple radios, and
l ¼ðSNðlÞ; SRðlÞ; DNðlÞ; DRðlÞÞ 2 L represents a directed physi-
cal link from node SN(l)toDN(l), where SR(l) and DR(l) rep-
resent the transmitting and receiving radios at two ends of
the link respectively. We further define h ¼ðSNðlÞ; DNðlÞÞ 2
H as a logical link between nodes SN(l) and DN(l) if they
are within the communication range of each other. Clearly,
each logical link is consisted of multiple physical links if
both ends have more than one radio. Some notations used
in the rest of this paper are listed in Table 1.
3.1. Interference margin and link capacity
The SINR of a link l =(s,sr,d,dr) is defined as
SINR
l
¼
P
s
G
sd
N
0
þ I
e
þ I
c
;
where P
s
is the transmit power of s, G
sd
denotes the channel
gain from node s to node d, and N
0
denotes the noise floor.
I
e
represents the external interference from co-existing
wireless devices operating in overlapping spectrum, e.g.,
WLANs, WPANs and other EMI sources. I
c
is the interfer-
ence from the concurrent transmission links. In the worst
case, all the nodes outside the contention domain of link
l may transmit simultaneously with l. Therefore, I
c
¼
P
s
0
RCDðlÞ
P
s
0
G
s
0
d
, where CD(l) is the set of contending nodes
that are not allowed to transmit simultaneously with link l.
We adopt the concept of interference margin to charac-
terize the robustness of a physical link as in [12]. Specifi-
cally, each physical link is associated with an interference
margin
r
l
, which represents the maximum value of chan-
nel variability and external interference that can be sus-
tained by link l for achieving a certain level of SINR.In
this way, the SINR of link l can be expressed as a function
of the interference margin
r
l
as follows:
SINR
l
¼
P
s
G
sd
N
0
þ
r
l
þ
P
s
0
RCDðlÞ
P
s
0
G
s
0
d
; ð1Þ
where G
sd
is the average channel gain from s to d. In other
words, the interference margin
r
l
represents the maximum
sustainable external interference and channel variations
given the channel gain of the link is at the average level.
We consider the IEEE 802.11 a/g systems and assume
that the link capacity C
l
of link l is a function of SINR
l
,or
C
l
= f(SINR
l
). In IEEE 802.11 a/g systems, due to the limita-
tion of modulation-coding schemes, only a set of finite
and discrete transmission rates are supported, so the trans-
mission rate can be expressed as a step function of the SINR
(see Table 2). Let H
r
denote the rth transmission rate, SINR
r
denote the required SINR (0 6 r 6 7), and w
r
l
denote the
indicator variable for link l, where w
r
l
equals 1 if link l
transmits with rate H
r
, and 0 otherwise. The following con-
straints should be satisfied for link l,
1
A multigraph is a graph which is permitted to have multiple edges
between the same end nodes.
Table 1
Notations.
Variable Description
r Link transmit rate level
u
l
Link activity indicator variable
w
r
l
Rate selection indicator variable of link l
z
q
n;j
Channel assignment indicator variable for radio j on
node n
A
m
Traffic demand of unicast session m
A
p
m
Traffic of session m routed on path p
B
h
Traffic load on logical link h
C
l
Link capacity of physical link l
D
l
Traffic load on physical link l
G
sd
Channel gain between nodes s and d
H
r
rth transmission rate
I
e
External interference
I
c
Concurrent transmission interference
N
0
Noise floor
O
l
Outage probability of link l
O
r
l
Outage probability of link l at rate level r
P
s
Transmit power of node s
T
l
Aggregate transmission time of link l
n
l
OPIM of link l
r
l
Interference margin of link l
r
r
l
Interference margin of link l at rate level r
X. Shao et al. / Ad Hoc Networks 13 (2014) 123–133
125