05-04-2012, 04:32 PM
RESOURCE MANAGEMENT IN MULTI-HOP CELLULAR
NETWORKS
RESOURCE MANAGEMENT IN MULTI-HOP CELLULAR NETWORKS.pdf (Size: 674.21 KB / Downloads: 28)
Abstract
In recent years, mobile communications have become affordable and popular. High
cellular capacity in terms of number of users and data-rates is in need. As the available
frequency spectrums for mobile communications are limited, the utilization of the radio
resources to achieve high capacity without imposing high equipment cost is of utmost
importance. Recently, multi-hop cellular networks (MCNs) were introduced. These
networks have the potential of enhancing the cell capacity and extending the cell
coverage at low extra cost. However, in a cellular network, the cell or system capacity is
inversely related to the cell size. In MCNs, the cell size, the network density and topology
affect the coverage of source nodes and the total demands that can be served and, thus,
the system throughput. Although the cell size is an important factor, it has not been
exploited for maximizing throughput. Another major issue in MCNs is the increase in
packet delay because multi-hopping is involved. High packet delay affects quality of
service provisioning in these networks.
In this thesis, we propose the Optimal Cell Size (OCS) and the Optimal Channel
Assignment (OCA) schemes to address the cell size and packet delay issues for a time
division duplex (TDD) wideband code division multiple access (W-CDMA) MCN. OCS
finds the optimal cell sizes to provide an optimal balance of cell capacity and coverage to
maximize the system throughput, whereas OCA assigns channels optimally in order to
minimize packet relaying delay. Like many optimized schemes, OCS and OCA are
computationally expensive and may not be suitable for large real-time problems. Hence,
we also propose heuristics for solving the problems. For the cell size problem, we
propose two heuristics: Smallest Cell Size First (SCSF) and Highest Throughput Cell
ii
Size First (HTCSF). For the channel assignment problem, we propose the Minimum Slot
Waiting First (MSWF) heuristic. Simulation results show that OCS achieves high
throughput compared to that of conventional (single-hop) cellular networks and OCA
achieves low packet delay in MCNs. Results also show that the heuristics, SCSF, HTCSF
and MSWF, provide good results compared to the optimal ones provided by OCS and
OCA, respectively.
iii
Acknowledgements
First, I would like to thank God for guiding me in this wonderful journey that I have
never thought of.
To my two supervisors, Dr. Selim Akl and Dr. Hossam Hassanein, I would like to
express my deepest gratitude. Dr. Akl is an excellent and exceptional supervisor. He is a
humble, gentle, knowledgeable, vigorous, and efficient researcher. He inspires me by
showing me what an excellent researcher should be like. His expertise in algorithm
design and problem solving techniques broadens my intellectual horizon. He always
gives me valuable advice for my research work. Dr. Hassanein is also an excellent
supervisor. He not only provided excellent guidance and support on my research work,
but also gave valuable advice, support, and encouragement for my professional and
personal development. He is a very considerate supervisor with a wonderful sense of
humor. His expert knowledge in the networking field helped me tackle a number of
obstacles during this work. I am very lucky to have them as my supervisors. I would also
like to thank Dr. Robert Benkoczi, who is my collaborator, friend, and mentor, for his
great help and patience. What an excellent researcher and an exceptional mentor he is.
Not only has he broadened my knowledge of linear programming techniques, but also
helped me to excel in my research work. I would like to thank Dr. Juergen Dingel for his
advice, help, support and encouragement.
To my parents, Mom and Dad, thank you so much for your deepest and unconditional
love for me so that I could carry on my journey. This journey has never been easy for me.
iv
But I finally made it. I am proud of being your son. I miss you so much. Grandma and
Grandpa, thank you for your unconditional and genuine love which was important to me
when my parents left. Auntie King Ming So, thank you so much for your love and care
and treating me like your son. Brian Cheuk Hung Siu, you are the best of my best friends.
Without your unconditional support financially and spiritually, my life would be much
more difficult and this accomplishment may not be possible. Winnie Man, thank you for
being part of my life. Your unconditional love and care makes me feel rich. Chun-ho
Chan and Angela Lau, thank you for caring, listening, and standing by me all the time
especially in Canada where I do not have many friends. Auntie Pauline So, thank you for
your love and care which makes me feel home in Canada. Benjamin Chan, you are such a
wonderful person. You are always helpful and considerate. Ben Kam, thank you for being
my buddy in this study journey. Without you, this would be a long and lonely journey.
Dr. Wenying Feng, thank you so much for your tremendous help and guidance in my
undergraduate studies. Thank you also for your care and support all the time. I would also
like to thank Mrs. Ruth Kennedy, Carolina Cuthbert, Rosie, Emily Jansons and Mrs. Ruth
Pester, who volunteers to help me improve my English. You are such wonderful persons.
To my relatives and friends including the members of So family, Priscilla Chan, Elaine
So, Edmond Lo, Kevin Lai, SKC friends, Chi-Shun Chan, Ven Lee, FAS friends, PIE
friends, Jenny Li, Ronnie Kwan, Ivy Lam, Connie Chan, Benny Ng, Agatha Wong, Aunt
Lam Yuen Tai, Simon Yu, Chi-hung Ho, UI colleagues, Adrianne Wai, Mandy Lee,
Simon Yam, Sharen Li, Marianne Lo, IN25 buddies, Patrick Lam, John Lau, Sebastian
Hung, Ian, and Debby, thank you for your love, care and support all the time – I love you
all.
v
I would like to thank the students, the staff, especially Debby Robertson, the faculty
members of the School of Computing, and my colleagues, especially Dr. Abd-Elhamid
Taha, in the Telecommunications Research (TR) Lab for their help, care, valuable advice,
and fun times we spent together.
Finally, I would like to thank the financial support provided by Queen’s University, the
Natural Sciences and Engineering Research Council of Canada (NSERC), the Ontario
Graduate Scholarship program, and the Communication Information Technology of
Ontario (CITO) and Bell University Labs (BUL).
List of Acronyms
1G 1st Generation Wireless Communication Systems
2G 2nd Generation Wireless Communication Systems
3G 3rd Generation Wireless Communication Systems
3GPP 3rd Generation Partnership Project
4G 4th Generation Wireless Communication Systems
ACAR A-Cell Adaptive Routing
A-Cell Ad hoc-Cellular
A-GSM Ad hoc Global System for Mobile
ALBA A-Cell Load BAlancing
AMC Adaptive Multi-hop Cellular
AODV Ad hoc On-Demand Distance Vector
AP Access Point
ARS Ad hoc Relaying Station
BCR Base-Centric Routing
BER Bit error rate
BS Base Station
CAMA Cellular Aided Mobile Ad hoc Network
CAHAN Cellular Ad hoc Augmented Network
CBM Cellular Based Multi-hop
CBR Call Blocking Ratio
CDMA Code Division Multiple Access
cMCN Clustered Multihop Cellular Network
DCF Distributed Coordination Function
DSR Dynamic Source Routing
DSSA Delay-Sensitive Slot Assignment
FDD Frequency Division Duplex
FDMA Frequency Division Multiple Access
GPS Global Positioning System
GSM Global System for Mobile
xii
HTCSF Highest Throughput Cell Size First
HMCN Hierarchical Multi-hop Cellular Network
HWN Hybrid Wireless Network
iCAR integrated Cellular and Ad hoc Relay
IP Internet Protocol
ISM Industrial, Scientific, and Medical
LDPR Location-Dependent Packet Relay
LCS Large Cell Size
MAC Medium Access Control
MADF Mobile Assisted Data Forwarding
MANET Mobile Ad Hoc NETwork
MCN Multi-hop Cellular Network
MCN-p Multi-hop Cellular Network – power reduction
MCN-b Multi-hop Cellular Network – base station reduction
MRAC Multi-hop Radio Access Cellular
MSWF Minimum Slot Waiting First
MSC Mobile Switching Centre
MT Mobile Terminal
OCA Optimal Channel Assignment
OCS Optimal Cell Size
ODMA Opportunity-Driven Multiple Access
OFDMA Orthogonal Frequency Division Multiple Access
P2P Peer to Peer
PSTN Public Switching Telephone Networks
QoS Quality of Service
PARCelS Pervasive Ad hoc Relaying for Cellular System
RNC Radio Network Controller
SCS Small Cell Size
SCSF Small Cell Size First
SOPRANO Self-Organizing Packet Radio Ad hoc Networks with Overlay
TDD Time Division Duplex
xiii
TDMA Time Division Multiple Access
UCAN Unified Cellular and Ad hoc Network
UMTS Universal Mobile Telecommunication System
VCN Virtual Cellular Network
W-CDMA Wideband Code Division Multiple Access
WiMAX Worldwide Interoperability for Microwave Access
WLAN Wireless Local Area Network
1
Chapter 1
Introduction
1. Introduction
Wireless communication technology has made great gains in popularity over the past
decade and will be playing a more important role in access networks, as evidenced by the
widespread adoption of cellular networks, Wireless Local Area Networks (WLANs) and
Worldwide Interoperability for Microwave Access (WiMAX) [Tane04]. A common
feature of these wireless technologies is the presence of a base station (BS) and central
control. Users of these wireless access networks expect high quality, reliability, and easy
access to high-speed services anytime, anywhere, and in any form.
1.1. Cellular and Multi-hop Cellular Networks
Mobile communications are facilitated by cellular networks. These networks basically
consist of mobile terminals, BSs, the radio network controller (RNC) and the core
network. A region that is being served is divided into sub-regions, called cells. Each cell
is covered by a BS and is allocated a number of channels for mobile terminals to
communicate with the BS. A mobile terminal communicates with another mobile
terminal, a landline phone of the Public Switched Telephone Network (PSTN), or the
Internet through the BS and the RNC. RNC and the core network are developed for third
generation (3G) cellular systems to facilitate both voice and data services and to provide
better radio resource management, handoff, and security. In first generation (1G) and
2
second generation (2G) cellular systems, the mobile switching centre (MSC) is used
instead of the RNC. Figure 1.1 illustrates the system architecture of a 3G cellular system.
In 3G networks, the wideband code division multiple access (W-CDMA) technology is
used. The technology allows higher frequency reuse and higher data-rates than that of 1G
frequency division multiple access (FDMA) and 2G time division multiple access
(TDMA) technologies. In 3G networks, frequency division duplex (FDD) and time
division duplex (TDD) modes are available. More discussion on the multiple access
technologies and the duplex schemes are in Chapter 3.
Figure 1.1: System architecture of a 3G cellular system
Limitations and problems of cellular networks
Cellular networks have inherent limitations on cell capacity and coverage. They also
suffer from the dead spot problem. Limited capacity also raises the hot spot problem and
BS
PSTN
BS
The Internet
Mobile terminal
Core
Network
RNC
BS
3
the issue of radio resource utilization. We discuss these limitations, problems, and issues
as follows.
Limited capacity – In a cellular network, the capacity of a cell is limited by the number of
channels allocated to the cell. The larger the number of channels, the greater the number
of users that can be served. The number of channels is limited by the available frequency
spectrums and by the frequency reuse factor [Rapp02]. A smaller cell size allows higher
frequency reuse and, thus, a higher capacity can be achieved. In a 3G system, the cell
capacity is not only limited by the available frequency spectrums, but also by the
interference among mobile nodes and the BSs. The higher the interference, the lower the
cell capacity is.
The hot spot problem - Due to the limited capacity, in dense areas known as hot spots,
such as downtown areas and amusement parks, mobile users tend to experience higher
call blocking, i.e., call requests are denied. This is because, in hot spots, there are more
mobile users than the number of available channels.
Radio resource utilization - The hot spot problem in turn raises the issue of radio
resource utilization. While there are not enough channels or capacity in a hot spot for
serving mobile users, the cells neighbouring the hot spot may still have available
channels. In other words, the radio resources of neighbouring cells are under-utilized.
Limited coverage – the coverage of cells is limited by the communication range or
transmission power of the BS. Mobile users, which are outside the coverage of the BSs,
are not able to access the networks.
4
The dead spot problem - Even though mobile users are within the communication range
of the BS, there are still some areas where coverage is not available. These areas are often
referred to as dead spots such as indoor environments and underground areas.
A possible solution to extend cell coverage and alleviate the hot spot and dead spot
problems is to install extra BSs or repeaters in the out-of-coverage region, congested
areas and dead spots. However, such a solution is expensive and may not be flexible to
adapt the dynamic traffic load conditions in the networks. A multi-hop cellular network
(MCN) [Chan03, De02, Kwon02, Lin00, Safw03, Zhou02] can be an alternative
complementary solution in cellular systems.
Benefits of multi-hop cellular networks
The idea of MCNs is based on multi-hop relaying. The source node signals are relayed
through other intermediate nodes to the BS. The intermediate nodes can be fixed, mobile
or ad hoc relays. In this way, the capacity can be enhanced, the coverage can be extended,
the hot spot and dead spot problems can be alleviated and the radio resource can be better
utilized. Figure 1.2 illustrates a general network architecture of a MCN which consists of
source nodes, relaying nodes and the BSs. The use of MCNs
enhances capacity - By using the concept of MCN or multi-hop relaying, the cell size can
be smaller, which allows higher system capacity in terms of higher frequency reuse
[Rapp02]. A higher transmission rate (cell capacity) due to a shorter transmission range
can also be achieved. This is further explained in Chapter 2.
alleviates the hot spot problem - With multi-hop relaying, congestions in hot spots can be
alleviated by relaying the traffic from the hot spots to their neighbouring less-congested
5
or non-congested cell through other mobile terminals or relaying devices. The radio
resource or available channels in the neighbouring cells can also be utilized.
extends cell coverage – Mobile users, in areas where BS coverage cannot be attained, can
relay their messages via one or more mobile terminals and/or special stationary devices
that have a direct or indirect link to the BS.
alleviates the dead spot problem – By using multi-hop relaying, mobile users in dead
spots are still able to reach the BS through other intermediate nodes.
is economically desirable – In MCNs, the number or the transmission power of the BSs
can be reduced (see Figure 1.3). In other words, a simpler infrastructure or cheaper
devices can be used. Therefore, MCNs can be more economically desirable. A study of
the economic issues of MCNs can be found in [Li08].