24-11-2012, 06:25 PM
On the Design of Self-Organized Cellular Wireless Networks
[attachment=41105]
ABSTRACT
It has been observed that complex networks
such as the Internet, World Wide Web, social
networks, and biological systems are self-organizing
in nature and exhibit some common properties
such as the power law degree distribution.
Recently, two models (i.e., small world and
scale-free network models) have been proposed
and successfully used to describe the nature of
such networks. In this article we investigate
whether these concepts can also be applied to
cellular wireless networks, which typically do not
exhibit self-organizing or scalability properties
due to the limited range of the wireless nodes.
Our ultimate goal is to design robust, reliable,
scalable, and efficiently utilized wireless networks
via self-organizing mechanisms.
INTRODUCTION
The size and scope of wireless networks continue
to grow with more users, and introduction
of a myriad of devices and sensors at homes
and businesses. All this, in conjunction with
short and dynamic flows of information, is
adding to the spatiotemporal complexity of the
network topology and dynamics requiring selforganization.
For over a century (until the late 1950s),
physical systems were modeled assuming that
interactions among the nodes in a system can
be represented by a regular and perhaps universal
structure of Euclidean lattices. In the
1950s Erdös and Rényi (ER) represented complex
network topologies by random graphs [1],
laying the foundation of random network theory.
Until the late 1990s, random graph or network
theory remained the only rigorous
approach to studying complex networks. However,
it has been observed that both of these
approaches have some shortcomings and fail to
represent some important properties of complex
networks such as the Internet, which are
not completely regular or random. Recently,
with the availability and analyses of volumes of
traces and statistics on the behavior of nodes,
two major approaches to describe complex networks
have been proposed.
THE SMALL WORLD CONCEPT
Basically, in a small world the average path
length is small (i.e., most nodes are a few hops
away from each other) and the clustering coefficient
is high. To form the small world model,
Watts and Strogatz interpolated between a regular
lattice and a random graph [2]. It is shown
that randomly rewiring a few edges (i.e., removing
a few edges and adding new edges to randomly
selected nodes) reduces the average
distance between nodes, but has little effect on
the clustering coefficient. For both the random
and small world models, the degree distribution
(i.e., the number of neighbors of the nodes in
the network) is exponential (i.e., probability of
having k neighbors decreases exponentially with
k). Hence, nodes with high connectivity are practically
absent, and the power-law property is not
observed.
As an illustration, the random rewiring procedure
for interpolating between a regular ring
and a random network is shown in Fig. 1. We
assume that the number of nodes in the network
is 20, and each node has an initial degree of 4.
Here p is defined as the rewiring probability,
where p = 0 and p = 1 represent the cases for
regular and random graphs, respectively. Note
that the average degree of the nodes after random
rewiring is still 4.
APPLICATION OF SMALL WORLD AND
SCALE-FREE MODELS TO
CELLULAR WIRELESS NETWORKS
Although much work has been done in ad hoc
wireless networking on the topics of self-configuration
and multihop routing [10], the scalability
of a hybrid network, which combines the cellular
network and ad hoc wireless networks (i.e.,
relay-based networks) has not been studied
before. Most previous work has studied ad hoc
wireless networks that consist of mobile nodes
placed randomly in the network, trying to
achieve scalable routing protocols for such networks
(e.g., hierarchical state routing [HSR] [11]
and zone routing protocol [ZRP] [12]). In addition,
a recent approach that applies small world
model ideas to ad hoc wireless networks is proposed
by Helmy [13, 14]. It is shown that by
removing/adding (i.e., “rewiring”) some wireless
links randomly, small world effects can be
obtained in wireless ad hoc and sensor networks.
The removal/addition of links is implemented
using physical wires between sensor nodes. However,
we believe that introducing new links using
physical wires is not realistic in wireless networks.
Therefore, in our work we do not make
this assumption, but attempt to make the network
small-world-like.
THE SYSTEM MODEL
Traditional cellular wireless networks consist of
BSs (or access points) controlled by a mobile
switching center (MSC) that communicate over
single-hop wireless links. We envision that in the
future, in addition to the wireless infrastructure
(i.e., the BSs), overlay fixed relay networks with
no infrastructure can be deployed in the geographical
coverage area to provide service to
mobile users, enhance network performance,
and use system resources (i.e., frequency channels)
efficiently. Therefore, in this article we
study a joint cellular and FRN network such as
the integrated cellular and ad hoc relay (iCAR)
system proposed in [8, 9]. We assume that an
FRN is a wireless communication device that
can communicate directly with a mobile user
(MU), a BS, or another FRN via different air
interfaces.
THE APPROACH
In this section we investigate if and how the
small world and scale-free network concepts can
be created in cellular wireless networks so that
they become scalable (e.g., average number of
hops between node pairs is minimized). Here,
node pairs consist of a BS and an FRN. We
assume that the FRNs basically receive the signal
of various mobile users and other FRNs
(within their range), and transmit the received
data to the next FRN or BS in the route. The
FRNs do not have any (wired) infrastructure.
Since connectivity between a mobile device and
an FRN is single hop and an FRN functions as
an aggregator and a traffic forwarder/router, we
do not call the mobile terminal a node from the
standpoint of the graph formulation.
[attachment=41105]
ABSTRACT
It has been observed that complex networks
such as the Internet, World Wide Web, social
networks, and biological systems are self-organizing
in nature and exhibit some common properties
such as the power law degree distribution.
Recently, two models (i.e., small world and
scale-free network models) have been proposed
and successfully used to describe the nature of
such networks. In this article we investigate
whether these concepts can also be applied to
cellular wireless networks, which typically do not
exhibit self-organizing or scalability properties
due to the limited range of the wireless nodes.
Our ultimate goal is to design robust, reliable,
scalable, and efficiently utilized wireless networks
via self-organizing mechanisms.
INTRODUCTION
The size and scope of wireless networks continue
to grow with more users, and introduction
of a myriad of devices and sensors at homes
and businesses. All this, in conjunction with
short and dynamic flows of information, is
adding to the spatiotemporal complexity of the
network topology and dynamics requiring selforganization.
For over a century (until the late 1950s),
physical systems were modeled assuming that
interactions among the nodes in a system can
be represented by a regular and perhaps universal
structure of Euclidean lattices. In the
1950s Erdös and Rényi (ER) represented complex
network topologies by random graphs [1],
laying the foundation of random network theory.
Until the late 1990s, random graph or network
theory remained the only rigorous
approach to studying complex networks. However,
it has been observed that both of these
approaches have some shortcomings and fail to
represent some important properties of complex
networks such as the Internet, which are
not completely regular or random. Recently,
with the availability and analyses of volumes of
traces and statistics on the behavior of nodes,
two major approaches to describe complex networks
have been proposed.
THE SMALL WORLD CONCEPT
Basically, in a small world the average path
length is small (i.e., most nodes are a few hops
away from each other) and the clustering coefficient
is high. To form the small world model,
Watts and Strogatz interpolated between a regular
lattice and a random graph [2]. It is shown
that randomly rewiring a few edges (i.e., removing
a few edges and adding new edges to randomly
selected nodes) reduces the average
distance between nodes, but has little effect on
the clustering coefficient. For both the random
and small world models, the degree distribution
(i.e., the number of neighbors of the nodes in
the network) is exponential (i.e., probability of
having k neighbors decreases exponentially with
k). Hence, nodes with high connectivity are practically
absent, and the power-law property is not
observed.
As an illustration, the random rewiring procedure
for interpolating between a regular ring
and a random network is shown in Fig. 1. We
assume that the number of nodes in the network
is 20, and each node has an initial degree of 4.
Here p is defined as the rewiring probability,
where p = 0 and p = 1 represent the cases for
regular and random graphs, respectively. Note
that the average degree of the nodes after random
rewiring is still 4.
APPLICATION OF SMALL WORLD AND
SCALE-FREE MODELS TO
CELLULAR WIRELESS NETWORKS
Although much work has been done in ad hoc
wireless networking on the topics of self-configuration
and multihop routing [10], the scalability
of a hybrid network, which combines the cellular
network and ad hoc wireless networks (i.e.,
relay-based networks) has not been studied
before. Most previous work has studied ad hoc
wireless networks that consist of mobile nodes
placed randomly in the network, trying to
achieve scalable routing protocols for such networks
(e.g., hierarchical state routing [HSR] [11]
and zone routing protocol [ZRP] [12]). In addition,
a recent approach that applies small world
model ideas to ad hoc wireless networks is proposed
by Helmy [13, 14]. It is shown that by
removing/adding (i.e., “rewiring”) some wireless
links randomly, small world effects can be
obtained in wireless ad hoc and sensor networks.
The removal/addition of links is implemented
using physical wires between sensor nodes. However,
we believe that introducing new links using
physical wires is not realistic in wireless networks.
Therefore, in our work we do not make
this assumption, but attempt to make the network
small-world-like.
THE SYSTEM MODEL
Traditional cellular wireless networks consist of
BSs (or access points) controlled by a mobile
switching center (MSC) that communicate over
single-hop wireless links. We envision that in the
future, in addition to the wireless infrastructure
(i.e., the BSs), overlay fixed relay networks with
no infrastructure can be deployed in the geographical
coverage area to provide service to
mobile users, enhance network performance,
and use system resources (i.e., frequency channels)
efficiently. Therefore, in this article we
study a joint cellular and FRN network such as
the integrated cellular and ad hoc relay (iCAR)
system proposed in [8, 9]. We assume that an
FRN is a wireless communication device that
can communicate directly with a mobile user
(MU), a BS, or another FRN via different air
interfaces.
THE APPROACH
In this section we investigate if and how the
small world and scale-free network concepts can
be created in cellular wireless networks so that
they become scalable (e.g., average number of
hops between node pairs is minimized). Here,
node pairs consist of a BS and an FRN. We
assume that the FRNs basically receive the signal
of various mobile users and other FRNs
(within their range), and transmit the received
data to the next FRN or BS in the route. The
FRNs do not have any (wired) infrastructure.
Since connectivity between a mobile device and
an FRN is single hop and an FRN functions as
an aggregator and a traffic forwarder/router, we
do not call the mobile terminal a node from the
standpoint of the graph formulation.