Design Considerations for Multihop Relay Broadband Wireless Mesh Networks

Navin Kumar, Member IEEE, IET, IETE, IE

Defence Engineering College, Department of Communication & Instrumentation Technology, Debrezeit, Ethiopia,
navin_kum3@yahoo.com

Abstract functionality usually provided by the network

Wireless relay has been proposed as the infrastructure (e.g., routers, switches, or servers).
solution to extend the coverage of a single base
station. The usage of multihop transmission method Currently deployed cellular communication
is one of the cost effective method that provides more architectures rely upon wireless links between
coverage of a base station (BS) especially in low user
wired infrastructure devices (base stations and
density environment. The basic idea is to perform
data transmission via intermediate relay stations and access points) and end user devices (mobile
thus range extension and higher throughput can be stations) for voice and data transmission. Although
achieved. In this paper the merits of multihop research and development in the fields of multiple
relaying in broadband cellular mesh networks have antenna techniques and advanced coding and signal
been presented. Under the guidance of these results, processing techniques (such as low-density parity-
the design perspectives on relay deployment, check codes, interference cancellation algorithms,
spectrum allocation and end-to-end optimization of and so forth) have enabled ground breaking
certain QoS measures such as throughput, coverage, enhancements in system performance in terms of
reliability and robustness are explained. Towards the
capacity, coverage and reliability and have become
end, the problem of efficiently designing a multihop
wireless backhaul to connect multiple wireless access part of the latest wireless standards such as 3G,
points to a wired gateway is also discussed. 802.16 and 802.11, these technologies on their own
Keywords: (Multihop, Relay Network, Wireless cannot satisfy future demands of wireless systems
Mesh, Cellular) without further deployment of infrastructure
devices, especially in reasonably large or densely
I. Introduction: populated areas [3]. In the meantime, cost-effective
In an environment, mobile devices self deployment of infrastructure-based solutions is
organize to create a network by exploiting their desired in order to meet economic feasibility
wireless network interfaces, without a requirement criteria; in this respect, it could be appealing for the
for a pre-deployed infrastructure. The simplest ad additional infrastructure devices to not require any
hoc network is a peer-to-peer network formed by a physical wired connection (e.g., electrical or fiber
set of stations within range of each other that optic connection) to the core network, such as the
dynamically configure themselves to set up a telephone network or an Internet protocol (IP)
temporary single-hop ad hoc network. This type of network, but rather to transmit and receive in a
network provides an effective solution to home and completely wireless fashion. The demands and
office automation by dynamically interconnecting constraints on future wireless networks outlined
devices in a short range. A Bluetooth piconet is above lead to a multihop cellular or mesh
probably the most widespread example of a single- architecture, an example of which is depicted in
hop ad hoc network. However, these networks are Fig. 1 and Fig. 2.
limited to devices that are within the same
transmission range. This limitation can be
overcome by exploiting the Multihop AdHoc
Paradigm.

In a multihop network, the packets are forwarded

in adhoc fashion by the network nodes from the
source to the destination. Nearby nodes can
communicate directly by exploiting a single hop
wireless technology (e.g., Zigbee, Bluetooth,
802.11, etc.). Devices that are not directly Fig 1. (a)
connected can communicate by forwarding their
traffic via a sequence of intermediate devices [1,
2]. Thus, the network nodes (i.e., the users’ mobile
devices) must cooperatively provide the
 multihop relay network is designed in reality [5];
we need to address and follow these issues.

II. Related Work

Multihop Relay Network is comparatively
new concept of increasing capacity, data rate and
enhancement in performance [6, 7, 8, 9]. A number
of papers [10, 11, 12] describe the merits of this
network. However, based on these results, the
Fig 1 (a), (b): Multihop Cellular Network Architecture paper explains the design criteria for future
broadband wireless networks. As illustrated and
explained in [5] the pure general purpose MANET
(Multihop AdHoc Network) does not exist. But
researchers are visualizing to see the future or next
generation broadband wireless multihop network.
Therefore, some of the considerations as listed out
and discussed need to be dealt with. In the above
papers, the advantages and characteristics are
discussed and performance improvements are also
Fig 2. (a) Relaying (b) Network with High benefit shown, however, some additional issues are
Transmission of relaying
The relay terminals serve the purpose of routing addressed here based on the results.
the data between the wired infrastructure devices
(labeled as BS, i.e. base station) and end users III A. Performance Parameters
(labeled as MS, i.e. mobile station) and thereby to Capacity Determination:
enhance the quality of end-to-end communication. Consider the linear multihop network
The size of their coverage area referred to as shown in Fig. 3 as a simple model to evaluate
“micro” or “pico” base stations (e.g., nodes 102- merits of relay-assisted multihop communication
110 in Fig. 1 each cover their respective shaded over cellular mesh networks. It is assume that the
hexagonal micro cells) and are generally smaller in multihop wireless network consists of N + 1
size and less expensive than the wired terminals, with a single active source-destination
infrastructure devices. These relay deployments pair separated by a distance D and N − 1
provide: enhancing data rate coverage and intermediate relay terminals located on the line
enabling range extension over cellular networks. between them; thus, N is the number of “hops”
Therefore, a growing interest is found recently in along the route.
the concept of relaying in infrastructure-based
wireless networks such as next generation cellular
networks (B3G, 4G), and broadband fixed wireless
networks (802.16, WiMax).

Although the literature contains significant

research in the field of multihop wireless
networking in the context of ad hoc networks and
peer-to-peer networks [4], multihop in
infrastructure based networks has been less
extensively studied. There are many challenges to Fig. 3: Linear Multihop Network Model
be tackled, both on the theoretical and practical
sides, for understanding performance limits and The full decoding also known as “regeneration or
devising design principles for infrastructure-based decode-and-forward” of the entire codeword at the
multihop mesh networks, for both narrowband and intermediate terminals is also considered.
wideband applications. In this paper, a step is taken Under quasi-static fading, the achievable rates over
forward to point out the design limits on overall different hops become random and vary as the
multihop relay broadband wireless network as well channel changes. Let us denote by Cn the
as the backhaul. After intensive simulation with maximum achievable rate (assuming the use of
respect to various key parameters, some capacity-approaching point-to-point codes) over
suggestions are outlined to emphasize that when hop n, where n = 1, ...,N, and by C the maximum
achievable rate over the multihop route. The and link adaptation mechanisms are designed to
performance in terms of the well-known spectral optimize performance under such reliability and
efficiency (in bits/second/Hertz or b/s/Hz) is delay constraints.
examined, the power efficiency tradeoff given in
simplest form in [10] To implement the rate-adaptive relaying solution
over random time-varying channels (e.g., fading
Eb 2C - 1 wireless channels), where the maximum achievable
----- = ------------ (i)
N0 C
where Eb is the energy per bit, and N0 is the one- rates
sided noise power spectral density. All receiving become random variables, the transmit terminal
terminals are assumed to accurately estimate and over hop n only needs to know the value of Cn and
track their channels and therefore possess full the value of an end-to-end link quality parameter
channel state information (CSI). There are two M, which is defined as
different strategies for the transmissions over
multiple hops:
The knowledge of global CSI (i.e. CSI for all links
(i) Fixed-Rate Relaying: In this approach, a fixed-
in the multihop network) is not required at every
rate coding strategy is adopted over all hops; the
terminal [14], which implies significantly reduced
rate over hop n equals Rn = R, ∀n for some fixed messaging overhead.. On the other hand, the
value of R. Thus, in order to ensure reliable parameter M depends on the channel conditions
communication (i.e., codeword error probability over all links, which may be computed in a
approaching zero) under the time division half- distributed fashion using a routing algorithm (e.g.,
duplex multihop protocol, the condition R ≤ Cn destination-sequenced distance-vector (DSDV)
must be satisfied over all hops. If R > Cn for any n [15]) in which the cost of the link over hop n is
∀n. {1, ...,N}, the reliable transmission of the represented by the metric 1/Cn, which is also
known as the expected transmission time
codeword over hop n is not possible even under
(ETT.)[16] Such a distributed approach involves
large coding block lengths and the multihop link is
the end-to-end propagation of a single parameter,
considered to be in outage [13]. In this setting, the
only requiring neighbor-to-neighbor message
maximum end-to-end data rate C can be achieved
passing of the accumulated multihop link cost
by choosing R as R = minn Cn, which leads to
metric which is updated by each terminal with the
1
addition of the cost of the last hop. Once the total
C = ----- minn Cn (ii)
N route cost has been determined by one
(ii) Rate-Adaptive Relaying: More generally, of the end terminals, the value of M can be
each terminal can to some extent obtain transmit broadcasted to all the terminals in the linear
CSI on the link to the neighbor terminal along the multihop network.
multihop route, and thus can perform rate-adaptive
relaying. In case of perfect transmit CSI at all B. Analysis
terminals, this implies that rate adaptation can be These relay stations enable multihop routing of the
performed such that Rn = Cn, ∀n. In this setting, packets from a (wired) base station to a (low
provided the use of capacity-approaching codes, mobility user, and vice versa. The model of Fig 3.
reliable communication can be guaranteed and the and results can be readily extended to more general
maximum end-to-end data rate is given by [11] scenarios. The following examples discuss various
N -1 performance gains from multihop communication
C= ∑ 1/Cn (iii) such as enhancements in capacity, power efficiency
n=1 and reliability. In cellular communications, such
However, in practice, the expected end-to-end benefits are critical, especially for users suffering
capacity performance under rate-adaptive relaying from poor signal-to-interferenceand- noise-ratio
to lie between (ii) and (iii). Furthermore, due to the (SINR) conditions, which may arise from reasons
usage of finite coding block lengths under delay such as high path loss due to distant positioning of
constraints and sub-optimal coding and decoding the end user from the base station or coverage
algorithms, Rn < Cn for practical systems even holes caused by high shadowing losses.
under perfect CSI assumptions, where Rn is the (a) Path Loss Mitigation: Considering frequency-
maximum achievable rate that guarantees a certain flat link models with additive white Gaussian noise
level of reliability (e.g., packet error rate (PER)) (AWGN) and path-loss of the form d − α, where d
is the distance between two radios and 2 < α < 5 is K, the slope with which we approach the minimum
the path-loss exponent [17]. The end-to-end increases. This wideband slope is a figure of merit
capacity can then be studied as a special case of (ii) introduced in [10] to measure spectral efficiency in
and (iii), which are identical in the case of equally- the power-limited regime.
spaced terminals. Details can be found in [11],
[12]. Fig. 3 illustrates capacity performance, in
terms of the spectral efficiency, power efficiency
tradeoff (1), for multihop transmission with path-
loss exponent α = 4 for varying number of hops N
= 1, 2, . . . , 6. In Fig. 3, transmissions employ
fixed-rate relaying, and the number of nodes
between simultaneously transmitting radios is K =
N, i.e., there is no interference caused by Fig. 5. Spectral efficiency C b/s/Hz vs. Eb/N0 over frequency-
simultaneous transmissions. For low Eb/N0, or the flat AWGN multihop channels with path-loss of exponent α = 4.
power-limited regime, multihop with large N offers Varying number of hops N = 1, 2, 3, 4, 6 and spatial reuse
parameter K ≤ N are considered. Again, the results are
improved performance, because transmission over normalized so that single hop achieves the usual −1.59 dB
shorter distances corresponds to increased effective corresponding to Shannon’s limit on the minimal Eb/N0.
signal-to-noise ratios. For high Eb/N0, or the (c) Outage Capacity and Reliability
bandwidth-limited regime, transmission with small Enhancement against Fading: For mitigating
N is preferable, at least for the timesharing fading. Each multipath fading link has two
schedule without interference discussed so far, independent taps with an exponential power delay
because increasing the number of hops corresponds profile (PDP) and complex Gaussian (Rician)
to reducing the effective bandwidth in which distribution with mean 1/√2 and variance 1/2, i.e., κ
transmissions occur on a given hop. For each = 1. The path loss exponent is assumed to be α = 4,
Eb/N0, or correspondingly for each target spectral and the average received signal-to-noise ratio
efficiency, there is an optimal number of hops, (SNR) between the mobile user and the base
which can be determined from Fig. 4 or using station is normalized to 0dB. The plot in Fig. 6 is
analytical solutions [18], [19]. cumulative distribution function (c.d.f.) of the end-
to-end capacity for both fixed-rate and rate-
adaptive multihop relaying schemes with varying
number of hops N = 1, 2, 10. It is observe that with
increasing number of hops, the c.d.f. of capacity
sharpens around the mean (i.e. the probability
distribution function (p.d.f.) concentrates), yielding
significant enhancements at low outage
probabilities over single-hop communication. This
Fig. 4. Spectral efficiency C b/s/Hz vs. Eb/N0 over frequency- can be interpreted as multihop diversity, which
flat AWGN multihop channels with path-loss of exponent α = 4. serves to ensure higher reliability in diversity-
Varying number of hops N = 1, 2, . . . , 6 are considered. The
results are normalized so that single hop achieves the usual
limited fading environments as well as for QoS-
−1.59 dB corresponding to Shannon’s limit on the minimal constrained and delay-limited applications. Similar
Eb/N0. to (a), it is shown in [11] that, for any given desired
(b) Enhancements from Reuse: Here, improved level of end-to -end data rate R, there exists an
performance in the power-limited regime through optimal number of hops that minimizes end-to-end
frequency or spatial reuse is illustrated. From outage probability and this optimal number
above K = N allows multiple nodes to transmit and increases with decreasing R.
so more efficient use of bandwidth, but introduces
intra-route interference. Now assuming every K ≤
N nodes to transmit simultaneously. Fig. 5
illustrates the capacity performance, again in terms
of the spectral efficiency, power efficiency tradeoff
(i), for multihop transmission over AWGN
channels with path-loss of exponent α = 4 and
varying number of hops N = 1, 2, 3, 4, 6. As N
increases, the case of K < N can offer better
Fig. 6. Cumulative distribution function of end-to-end capacity
multihop performance for low Eb/N0. Specifically, for fixed-rate and rate-adaptive multihop relaying schemes for N
although the minimum Eb/N0 does not change with = 1, 2, 10.
(d) Sensitivity of Gains to Channel Parameters: above the multihop relaying offers certain
Here, the impact of varying path loss, which performance advantages; however, a number of
depends closely on range, antenna heights, terrain specific challenges related to PHY/MAC-layer
characteristics and carrier frequency is design of multihop systems remain. These
investigated. End-to-end capacity varies as the path challenges include:
loss characteristics of the network changes with (i) Resource allocation: The allocation of
respect to the choice of these system design resources in relay-assisted cellular mesh networks
parameters and consequently the sensitivity of the requires design of novel scheduling and routing
optimal solution on the design parameters. policies, under certain QoS constraints such as
Considering realistic broadband wireless channel reliability, fairness and latency. Broadly, resource
models [20]. The simulation results shows (see allocation over multihop cellular mesh networks
[14] for further results) are sufficient to show the can be categorized as follows:
high sensitivity of gains from multihop (a) Centralized: The base station is the sole
communication to various channel parameters. In decision-maker for allocating the time and
Fig. 7, we analyze the expected value of the frequency resources across users and the actions of
optimal number of hops, denoted as Nopt, as a the relay terminals are fully coordinated by the
function of the path loss exponent α assuming rate- base station. It requires efficient design of joint
adaptive relaying, an end-to-end average received centralized scheduling and routing algorithms and
SNR of 0 dB between the base station and end has substantial overhead for feedback which may
user, log normal shadowing of standard deviation become intractable if there is fast fading. Under
values σ = 0, 4,8 dB and a frequency-selective moderately slow fading channel conditions, a novel
channel model with 2 independent exponential resource allocation policy, orthogonal frequency
PDP taps and complex Gaussian (Rician) fading division multihop multiple access (OFDM2A), was
distribution with mean 1/√2 and variance 1/2, i.e., κ proposed recently in [21] as a low-complexity
= 1, over each tap and each link. These results suboptimal solution for resource allocation over
show the high sensitivity of Nopt with changing α cellular mesh systems requiring reduced messaging
and σ, necessitating the use of accurate channel overhead. This policy is based on centralized
models in order to extract the highest gains from scheduling using end-to-end link quality metrics,
multihop cellular system designs. The only regime under the principle of separation of subcarrier
in which Nopt appears to be robust with respect to allocation and multihop route selection, and was
α and σ is for high path loss exponent range, e.g., α shown to simultaneously realize gains from both
> 4. multiuser diversity and multihop relaying to
enhance capacity and coverage, provided the
availability of closed-loop transmission
mechanisms.
(b) Distributed: This form of resource allocation
requires more intelligence at the relay terminals to
allow them to contribute to scheduling, resource
allocation and interference management. The relay
stations perform resource allocation across users in
their locality, with no influence from the base
Fig. 7. The expected value of the optimal number of hops Nopt station. A fixed cellular reuse pattern may be
as a function of the path loss exponent α for different values of enforced across micro cells. Alternatively,
shadowing standard deviation, σ = 0, 4,8 dB. depending upon the quality of service (QoS)
conditions (user load, fairness, throughput demands
These observations suggest that the system or changing channel conditions), the relay
designer should carefully account for application terminals can dynamically allocate resources (i.e.,
requirements, hardware specifications, and terrain via distributed scheduling algorithms) to the users
characteristics in choosing the optimal multihop in their locality, in which case no static frequency
network architecture. reuse pattern is enforced across the micro cells.
This approach requires close coordination among
IV. Design Challenges neighboring relay stations, where they may
The key technical goal to be accomplished compete or cooperatively bargain for spectrum in
in the design of multihop cellular mesh networks is order to optimize their respective radio access
end-to-end QoS optimization with the assistance of networks.
cost-effective relay architectures. As outlined
(c) Hybrid or hierarchical: In this form of resource association with a base station. Furthermore,
allocation, the base station and relay stations work besides the usual difficulties in reliable channel
together such that the base station makes certain estimation and feedback experienced in
partial decisions on resource allocation across users conventional cellular networks, high mobility
(such as assigning a cluster of frequency bands or makes it impossible to realize the advantages of
time slots to a relay station for user assignments) dynamic resource allocation, such as gains from
and each relay station makes the final decisions on bandwidth allocation, scheduling, and routing, due
the specific resource allocation among the users in to increase in the required frequency of route
its locality. updates and the fact that channel state feedback has
(ii) Sectorization, reuse and interference higher overhead. Under stringent end-to-end delay
management: Spatial reuse through resource (time constraints, one can expect multihop systems to be
and frequency) sharing among relay terminals impacted more severely from mobility than
could be an important factor in enhancing conventional cellular systems.
throughput over multihop cellular networks. A
static spatial reuse pattern can be enforced among V. Wireless Backhaul
the micro cells, or resource assignments can be The Wireless backhaul is fast becoming a
performed dynamically. Especially under the cost effective alternative to wired technologies.
centralized control of the base station, resource Wireless backhaul networks will be useful to
allocation allowing for controlled levels of intra- provide high speed Internet access to residential,
cell interference (i.e., interference within the small and medium business customers, as well as
coverage area of the base station due to spatial Internet access for WiFi hot spots and cellular base
reuse by multiple active relay transmissions) may stations. Public safety services and private
result in higher network capacity. On the other networks could also be built using wireless
hand, under distributed resource allocation backhaul links. However, there are several
schemes, aggressive spatial reuse may cause problems of efficiently designing a multihop,
undesired levels of intra-cell interference between wireless backhaul to connect multiple wireless
the base station, relay stations and users due to lack access points to a wired gateway.
of coordination, lowering capacity and reliability. (i) The Interference: There are two types of
However, with the development of advanced interference in our backhaul network: (a) self-
spectrum sensing mechanisms, distributed resource interference that prevents a single access point
allocation and opportunistic spectrum usage may from simultaneously transmitting and receiving, or
become attractive options for future relay from simultaneously receiving from multiple
deployments. neighbors on the same subchannel; and (b) cross-
(iii) Precise channel models: The presence of the link interference, caused by transmissions using the
relay terminals in cellular multihop mesh networks same subchannel over two separate links with
results in four different channel types: (a) channels distinct receivers that are located close to each
between the base station and users (as in other.
conventional cellular architectures), (b) channels (ii) Efficient Backhaul Routes: This is another
between relay stations and users (c) channels design problem of constructing efficient backhaul
between relay stations, and (d) channels between routes.
relay stations and the base station. Although the Here, a link activation framework called Even-Odd
first channel type is specified by widely accepted scheduling framework for scheduling packets are
channel models in several standards [20], summarized to highlight improvements in both the
specifications and precise models for the channels interference as well as routing.
involving relay terminals are necessary because the The Even-Odd scheduling framework uses a
gains from multihop communication and end-to- simple link activation scheme: each directed link is
end optimization criteria are found to be very active every alternate timeslot. All even links are
sensitive to different model assumptions and active in the even timeslots, while all odd links are
channel parameters such as path loss exponent, active in the odd timeslots. It also applies sub
carrier frequency, antenna heights, and terrain channelization to adjust link bandwidths and to
characteristics. allow access points to receive simultaneously over
(iv) Mobility and handoff: The issue of mobility multiple links. Figure 8(b,c) illustrates this link
becomes more critical in multihop cellular mesh activation scheme for a sample backhaul topology.
networks. One immediate difficulty arises with Consider the even node u in Figure 8(a). Every
handoff, as each user may need to be associated even timeslot, u is transmitting to its neighbors,
with a relay terminal in addition to the usual since links from u to its neighbors are all labelled
odd; we say u is now in the transmitting mode. VI. Results
Every odd timeslot u, is receiving data from its Figure 9 shows the average and maximum delays
neighbors; we say u is now in the receiving mode. incurred by packets for each backhaul topology T1
Similarly, odd nodes are in the transmitting mode – T7. As it can be seen from the figure, the
in every odd timeslot, and in the receiving mode subchannelization and alternate link activation of
every even timeslot. Thus when an access point the Even-Odd framework provides a significant
joins the backhaul network, the centralized routing improvement in end-to- end delays. Further, within
phase must assign it a label along with uplink and either framework, the bounded delay schedulers
downlink routes connecting it to the gateway. (WFQ and CEDF) result in lower maximum delays
Combined with interference-aware routing and a (up to 45% lower compared to, say, FIFO).
TDMA MAC layer, the Even-Odd framework
eliminates interference and maps a wireless
backhaul into an equivalent, half-idle wireline
network. As a result, any existing wireline
scheduling policy can be implemented locally at
each access point in the wireless backhaul. A
careful analysis shows that when a multihop
wireline scheduler with worst case delay bounds (a)
(such as WFQ [22] or Coordinated EDF [23], [24])
is implemented over a wireless backhaul, the
framework guarantees approximately twice the
delay compared to the corresponding wireline
topology.

(b)
Fig. 9. (a) Maximum and (b) average packet delays over all
uplink and downlink connections using different link activation
schemes and scheduling policies. The striped bars represent
delays in the Even-Odd framework.

The effect of the number of nodes in a backhaul

network on the network’s capacity and the end-to-
Fig. 8. (a) Possible valid uplink (in dash-dotted blue) and end delays are examined. From 5 nodes to 25
downlink (in dashed purple) routes for a node : only links
connecting odd nodes and even nodes are permitted in routes; nodes in a 5km x 5km space are added in step. At
(b) links that are activated in even timeslots in the Even-Odd each step, the best heuristic-based backhaul tree
framework; (c) links that are activated in odd timeslots. topology is constructed from the given set of
nodes. Note that when a node is added, the capacity
Self-interference, that is, interference between link of the resulting backhaul network may rise or fall
pairs that share a node, is eliminated in this depending on the location of the node. Figure 10
framework with a combination of Even-Odd link shows the capacity and the average end-to-end
activation and subchannelization. The Even-Odd delay at each step as they are added. It is found that
scheme prevents a node from simultaneously the Even-Odd activation framework remains
transmitting and receiving, while subchannelization significantly more stable in its delays as the
ensures that simultaneous receptions to (or number of nodes increases.
transmissions from) a single node do not interfere
with each other. Therefore the routing component Figure 11 shows the effect of increasing load on
only needs to consider interfering link pairs that do end-to-end delays. Here the link activation
not have a node in common. Such cross-link schedule is determined according to the maximum
interference is eliminated by the routing admissible rates, so at low rates far fewer packets
component by ensuring that no two links that are sent over each link compared to its maximum
interfere will be assigned the same label; thus links capacity. Therefore, at very low loads, the
with cross interference will not be active difference between the schedulers is less
simultaneously. pronounced, although the Even-Odd framework
consistently yields lower delays.
 Zirwas, M. Dohler, H. Aghvami, D. Falconer, and G. Fettweis,
“Relay-based deployment concepts for wireless and mobile
broadband radio,” IEEE Comm. Mag., vol. 42, no. 9, pp. 80–89,
Sept. 2004.
[4] M. Haenggi and D. Puccinelli, “Routing in ad hoc networks:
A case for long hops,” IEEE Comm. Mag., vol. 43, no. 10, pp.
93–101, Oct. 2005.
[5] Marco Conti, (CNR), Silvia Giordano, (SUPSI), “Multihop
Ad Hoc Networking: The Reality”, IEEE Comm. Mag. Vol. 6,
Fig. 10. Total backhaul network capacity (as a histogram) and no. 5, pp. 88 – 95, Apr. 2007
the average packet delays as more nodes are added to a 5km x [6] Marks, R.B.: IEEE 802 Tutorial: 802.16 Mobile Multihop
5km space. The backhaul tree is reconstructed at each stage. Relay, March 2006
[7] Jain, R.: Wireless Mesh and Multi-Hop relay networks, 2006
[8] IEEE 802.16 Mobile Multihop Relay Study Group:
Recommendations for the Scope and Purpose of the Mobile
Multihop Relay Task Group, November 2005
[9] Nosratinia, A. – Hunter, T. E. – Hedayat, A.: Cooperative
Communication in Wireless Networks, October 2003
[10] S. Verd´u, “Spectral efficiency in the wideband regime,”
IEEE Trans. Inf. Theory, vol. 48, no. 6, pp. 1319–1343, Jun.
2002.
[11] O¨ . Oyman and S. Sandhu, “Non-ergodic power-
Fig. 11. Maximum and average end-to-end packet delays as the
bandwidth tradeoff in linear multi-hop networks,” in Proc.
data rates of all the connections is increased, shown here as a
IEEE International Symposium on Information Theory
percentage of the maximum admissible connection rate.
(ISIT’06), Seattle, WA, July 2006.
[12] O¨ . Oyman and S. Sandhu, “Throughput improvements in
VII. Conclusion micro-cellular multi-hop networks,” in IEEE 802.16 MMR
Multihopping through the use of relays was Contributions, Vancouver, Canada, Nov. 2005
found to increase throughput in cellular networks. In this [13] L. H. Ozarow, S. Shamai, and A. D. Wyner, “Information
paper, the merits of multihop relaying in broadband theoretic considerations for cellular mobile radio,” IEEE Trans.
cellular mesh networks have been discussed. Under the Veh. Technol., vol. 43, no. 2, pp. 359–378, May 1994.
[14] O¨ . Oyman, “Reliability bounds for delay-constrained
guidance of these results, some of the design multi-hop networks,” in Proc. Allerton Conference on
perspectives on relay deployment, spectrum allocation Communication,Control and Computing, Monticello, IL, Sep.
and end-to-end optimization of certain QoS measures 2006.
such as throughput, coverage, reliability and robustness [15] C. Perkins and P. Bhagwat, “Highly dynamic destination-
are summarized. In addition to this, design parameters of sequenced distance-vector routing (DSDV) for mobile
wireless backhaul are also outlined with the Even-Odd computers,” in Proc. ACM-SIGCOMM, London, UK, 1994.
link activation framework, which provides a simple [16] R. Draves, J. Padhye, and B. Zill, “Routing in multi-radio
mechanism for implementing wireline scheduling multi-hop wireless mesh networks,” in Proc. ACM
MobiCom’04, Philadelphia, PA, Sep. 2004.
policies locally at each access point in a wireless [17] G. St¨uber, Principles of Mobile Communication, Kluwer,
backhaul network. This framework is applicable to any Norwell, MA, 3rd edition, 1996.
backhaul topology, provided that all routes consist of [18] M. Sikora, J. N. Laneman, M. Haenggi, D. J. Costello, and
alternately labelled nodes. The Even-Odd framework T. E. Fuja, “On the Optimum Number of Hops in Linear Ad
allows bounded-delay schedulers such as WFQ and Hoc Networks,” in Proc. IEEE Inform. Theory Workshop
CEDF to be efficiently mapped to our multihop wireless (ITW), San Antonio, TX, Oct. 2004.
network. Several researchers have worked on designing [19] M. Sikora, J. N. Laneman, M. Haenggi, D. J. Costello, and
interference-free schedules for multihop wireless T. E. Fuja, “Bandwidth and power efficient routing in linear
wireless networks,” IEEE Trans. Inf. Theory, vol. 52, no. 6, pp.
networks. The main goal is to increase the throughput of 2624–2633, June 2006.
the network by optimizing the length of the computed [20] Channel Models for Fixed Wireless Applications, IEEE
periodic schedule. The scheduling framework allows for 802.16.3c-01/29r5, 2003.
better delays in practice compared to the approach of [21] O¨ . Oyman, “OFDM2A: A centralized resource allocation
building periodic schedules. policy for cellular multi-hop networks,” in Proc. IEEE Asilomar
In this paper, the detailed studies are not taken and Conference on Signals, Systems and Computers, Monterey, CA,
neither all the design parameters. Therefore, the Oct. 2006.
investigation continues to bring more improvement [22] A. K. Parekh and R. G. Gallager. A generalized processor
sharing approach to flow control in integrated services
before actually designing multihop wireless broadband networks: The multiplenode case. IEEE/ACM Transactions on
system. Networking, 2(2):137 – 150, 1994.
[23 M. Andrews and L. Zhang. Minimizing end-to-end delay in
References high-speed networks with a simple coordinated schedule. In
[1] I. Chlamtac, M. Conti, and J. Liu, “Mobile Ad Hoc Proceedings of IEEEINFOCOM, pages 380 – 388, New York,
Networking: Imperatives and Challenges,” Ad Hoc Networks J., NY, March 1999.
vol. 1, no. 1, Jan.–Mar., 2003. [24] C. Li and E. Knightly. Coordinated network scheduling: A
[2] S. Basagni et al., Eds., Mobile Ad Hoc Networking, IEEE framework for end-to-end services. In Proceedings of IEEE
Press and Wiley, 2004. ICNP, Osaka, Japan, November 2000.
[3] R. Pabst, B. Walke, D. Schultz, P. Herhold, H.
Yanikomeroglu, S. Mukherjee, H. Viswanathan, M. Lott, W.