<<

. 68
( 87 .)



>>

26. IEEE 802.11b-1999 Supplement to 802.11-1999,Wireless LAN MAC and PHY specifications:
Higher speed Physical Layer (PHY) extension in the 2.4 GHz band.
27. “Specification of the Bluetooth System,” Bluetooth Special Interest Group, Version 1.1, Febru-
ary 22, 2001, http://www.bluetooth.com/pdf/Bluetooth_11_Specifications_Book.pdf.
28. B. Schneier, Applied Cryptography, Wiley, 1996.
29. Stubblefield, Loannidis, and Rubin, “Using the Fluhrer, Mantin, and Shamir Attack to Break
WEP,” AT&T Labs Technical Report, 2001.
CHAPTER 13




SELF-ORGANIZED AND COOPERATIVE
AD HOC NETWORKING

SILVIA GIORDANO and ALESSANDRO URPI




13.1 INTRODUCTION

Traditional approaches to ad hoc networks do not exploit certain characteristic of these
networks (e.g., cooperation and relationships among nodes). A different approach to the
network layer is based on the social behavior of people in real life.
A community is the structure that derives from individuals™ interactions in a shared en-
vironment. The resulting set of interrelated community members is generally called the
social network of a community. A fundamental characteristic of communities of individu-
als is that, regardless of the number of individuals, a single individual needs only little in-
formation about other individuals to still be able to potentially interact with a large num-
ber (or all) of the community members. An interesting model for social relationships is
represented by the small-world graph [33]. The six degrees of separation property illus-
trates this in the case of human communities. Moreover, communities are often character-
ized by a highly self-organizing behavior. Insect collectives such as ants or bees and also
physical and chemical systems composed of large numbers of individuals or particles in-
teract locally and thereby contribute to global organization, optimization, and adaptation
to the environment. Computer networks or distributed systems in general may be regarded
as communities similar to the above examples [32].
In particular, a mobile ad hoc network is a community of users and, very similarly to
human communities, can be modeled as a small-world graph. Nodes maintain routes not
only to nodes discovered by means of the routing protocol (short connections), but also to
some other nodes (long connections) that are considered interesting to them. The main re-
sult is a self-organizing network that is more naturally suitable and effective for construct-

355
Mobile Ad Hoc Networking. Edited by Basagni, Conti, Giordano, and Stojmenovic.
ISBN 0-471-37313-3 © 2004 Institute of Electrical and Electronics Engineers, Inc.
356 SELF-ORGANIZED AND COOPERATIVE AD HOC NETWORKING


ing a citizens™ network, which can reduce communication costs and complexity and im-
prove people™s ability to share information anywhere and anytime. The self-organization
characteristic is one of the fundamental and more innovative aspects of mobile ad hoc net-
works. Learning from biology, self-organization can be defined as a property of certain
dynamical mechanisms whereby structures, patterns, and decisions appear at the global
level of a system based on interaction among low-level components. The rules specifying
interactions among the systems™ components are executed on the basis of purely local in-
formation, without reference to the global pattern. A large amount of research in ad hoc
routing deals with the networking aspects of these networks. However, traditional
schemes for ad hoc networks do not exploit the characteristics more related to self-organi-
zation (e.g. cooperation and relationship among nodes).
The Internet Engineering Task Force (IETF) working group on Mobile Ad-hoc NET-
works (MANETs) is standardizing routing in ad-hoc networks. The group studies routing
specifications, with the goal of supporting networks scaling up to hundreds of routers [1]
The work done in the MANET working group relies on other existing IETF standards
such as mobile-IP and IP addressing.
A mobile ad-hoc network that explicitly supports the Internet still presents the major
salient characteristics we described above, as described in [10]:

Dynamic topologies
1.
Bandwidth-constrained and variable-capacity links
2.
Energy-constrained operation
3.
Limited physical security
4.

As presented in [11] and [20], the approach followed by the protocols produced by the
MANET working group, and by similar protocols worked on outside of MANET working
group is based on the traditional two-level hierarchy routing architecture.
With this view, these routing protocols fall into the class of interior gateway protocols,
that is, protocols used to route within a (mobile wireless) network or a set of interconnect-
ed (mobile wireless) networks under the same administration authority. However, the
managing of IP addresses of the nodes in a mobile ad hoc network is not straightforward.
This approach does not fully exploit the cooperation and self-organization peculiarities of
ad hoc networks. Therefore, there is a need for another approach, as we explain later.
As discussed in Chapter [10], most of the research on ad hoc networking, in the past
and in the recent years, has focussed on this approach. The current chapter illustrates how
ad hoc networks can be based on the social model of human communities in order to
achieve collaboration and communication, as happens in the real life. The communication
task is identified with the capability of delivering some information to a destination. In
this case, the critical aspect is the selection of a path from the source to the destination. In
Section 13.2, we discuss how this routing task can be performed in a way that reproduces
human behavior in a human community. Node collaboration involves several aspects, and,
even in this case, it will be addressed with a model that tries to emulate the real behavior
of people. Game theory, as we discuss in Section 13.3, considers the cooperation aspects
in dynamical system such as ad hoc networks. Games rules model the freedom of every
node to choose cooperation or isolation, and, given that players (i.e., nodes) choose rules
that maximize their personal benefits, it is possible to address situations of heterogeneity.
Finally, as rules and strategies lead to the creation of new network topologies, game theo-
357
13.2 COMMUNICATION IN A SELF-ORGANIZED NETWORK


ry is the natural tool for studying how the different ways of cooperating affect the evolu-
tion of the system.


13.2 COMMUNICATION IN A SELF-ORGANIZED NETWORK

Stanley Milgram introduced the small-world phenomenon with experimental study in so-
cial science in the 1960™s [25]. These experiments showed that the acquaintanceship graph
connecting the entire human population has a diameter of six or less, hence the “six-de-
grees of separation.” The small-world phenomenon formalizes this anecdotal notion by in-
troducing a class of graphs”small-world graphs (SWGs)”that appear to embody the
defining characteristics of the small-world phenomenon: very large graphs that tend to be
sparse, clustered, and have a small diameter. The behavior of small-world systems is very
far from the typical behavior of physical systems. In particular, the notion of being
“close,” which in physical systems obeys the triangle inequality, it is very different. The
fact that node A is well acquainted with B and C, could easily be associated with the situ-
ation in which B and C are not even remotely familiar with each other. The main conse-
quence is that, in SWGs, local actions can have global consequences.
The applications of small-world research both encompass and stretch well beyond so-
ciological problems [25] and can include the mobile ad hoc networks. With this view,
nodes are in relationships. They need not be physically close, but if they know how to de-
liver packets to each other, they may violate the transitivity of distances rule of physical
systems. That is, while connectivity is achieved through local wireless links (see a well-
known model in [27]), the communication is based on a relationship that does not respect
the local connectivity. In this way, the communication network can be modeled as a small-
world graph. In line with this approach, self-organized routing distinguishes itself from
traditional mobile ad hoc routing protocols based, as previously stated, on the traditional
Internet two-level hierarchy routing architecture, by emphasizing the self-organizing pe-
culiarities [3]:

1. Self-organized networks are nonauthority-based networks; that is, they can act in
independently of any provider or common denominator, such as the Internet. There-
fore, whereas authorities or special role nodes do not belong to this architecture, it
is mandatory to regulate the way the nodes cooperate, as explained in the next sec-
tions.
2. Self-organized networks are not regularly distributed, neither in terms of node (net-
work density), nor in terms of topology. Potentially, they can be very large.
3. Self-organized networks are based on the cooperation between nodes. Thus, net-
working functions must be based on the support of other nodes (aided routing; see
[16]).

13.2.1 Terminode Routing
One way to achieve self-organization is terminode routing [4]. Terminode routing is a
self-organized routing scheme where by internode communication, even in a large net-
work, relies solely on local information and interaction with other nodes. The routing task
is accomplished by two interacting protocols: Terminode Local Routing (TLR) and Ter-
358 SELF-ORGANIZED AND COOPERATIVE AD HOC NETWORKING


minode Remote Routing (TRR). The TLR mechanism is used to reach destinations in the
vicinity of a node and uses local routing tables that every node proactively maintains for
its close neighbor nodes. It is very similar to the traditional mobile ad hoc routing proto-
cols presented in Chapter 10 and, therefore, not a main point of interest for our analysis.
More interesting is the approach taken whenever a source has to send data to a remote
destination. The TRR protocol works with geographic information, that is, node coordi-
nates in two- or three-dimensional space. Geographic (or position-based) routing [15] al-
lows nodes in the network to be nearly stateless; the routing based is on information main-
tained locally. For that reason, it is more scalable than traditional routing; the information
that nodes in the network have to maintain is not much more than that of their neighbor-
hood.
However, greedy geographic routing could fail in some scenarios, so the TRR protocol
introduces two novel elements: the friend nodes and the anchor paths. These two elements
allow for a more valid use of geographical routing by structuring the communication net-
work as a SWG.

Friends Nodes. In order to achieve the SWG properties, the authors introduce nodes
with a special role: the friends. Similarly to social networks, the mobile ad hoc network is
seen as a large graph, with edges representing the “friend relationship.” As explained in
[4], B is a friend of A if (1) A thinks that it has a good path to B and (2) A decides to keep
B in its list of friends. A may have a good path to B because A can reach B by applying
TLR, or by geodesic packet forwarding, or because A managed to maintain one or several
anchor paths to B that work well [4]. The value of a path is given in terms of congestion
feedback information such as packet loss and delay. The way a node gets in touch with its
potential friends is thought to be similar to the human behavior, such that the friend rela-
tionship works similarly to a relationship in a human community and the networks pre-
sents SWG properties. More precisely, a node, being used by some person and running
certain applications, has a given number of contacts with other nodes, which potentially
are remote. Additionally, by its nature the friend relationship is present within the node™s
neighborhood, as neighbor nodes are known and reachable.
With this approach, a node is assumed to select its friends from a list that includes
some remote nodes in addition to the close nodes of the neighborhood. Therefore, this set
is suitable for constructing the short- and long-range connections of a SWG. And each
couple of nodes are likely to be connected through a short sequence of intermediate ver-
tices. This means that any two nodes are likely to be connected to a small number of inter-
mediate friends. The key element of the terminode routing scheme for achieving the SWG
characteristic is the way the friends are selected (and maintained). The characteristic that
is reproduced in the scheme is the presence of a small fraction of long-range edges, which
connect otherwise distant parts of the graph, while most edges remain local, thus con-
tributing to the high clustering property of the graph.

Anchor Paths. In order to exploit the potential of this approach, in conjunction with
the geographical routing, TRR introduce an additional novel element: the anchor path. In
contrast to traditional routing paths, an anchor path does not consist of a list of nodes that
a packet has to visit before reaching the destination. An anchor path is a list of fixed geo-
graphic points called anchors. If we make a comparison with traditional paths, the advan-
tage of using geographic points is given by the fact that they do not move. So, whereas tra-
ditional paths can become invalid when the nodes move, the anchor paths, once
established, can always be used, even in a mobile environment.
359
13.2 COMMUNICATION IN A SELF-ORGANIZED NETWORK


The friends are used to discover the anchor paths. When a source S wants to discover a
path to destination D, it requests assistance from some friend. If this friend is in condition
to collaborate, it tries to provide S with some path to D (it can have it already or try to find
it, perhaps with the collaboration of its own friends) [4]. Therefore, an anchor path results
in a list of positions of friends. Now, given that the friend relationship can represent, with
some probability, a long-range connection, the anchor path is likely to be much shorter
than the number of hops necessary between the source and the destination.

Example. Suppose that a source S wants to communicate with a destination D. Tradition-
al routing methods try to discover a path from S to D. In Figure 13.1, we use as an exam-
ple the shortest path (in terms of number of hops) from S to D, and we represent it with
dotted lines. It consists of six hops.
With the SWG approach of terminode routing, S contacts its friend F1 to get a path to
D, and F1 contacts F2, which knows a path to D (see [4] for technical details). In this case,
the resulting anchor path (S, AP1, AP2, D), illustrated by thick lines, consists of just three
hops and shows that this communication network has a smaller characteristic path length
compared to the traditional routing approaches.

13.2.2 Grid Location Service (GLS)
Another example based on the small-world phenomenon is presented in GRID [19]. In
this work, the authors build a structure that can be seen as a small-world graph for the
location aspects. At the routing level, GRID uses geographical forwarding to take ad-
vantage of the similarity between physical and network proximity. In order to support
geographical forwarding, the GRID scheme introduces the Grid Location Server (GLS).
GLS is based on the idea that a node maintains its current location in a number of lo-
cation servers distributed throughout the network. These location servers are not spe-
cially designated; each node acts as a location server on behalf of some other nodes. The
location servers for a node are relatively dense near the node but sparse farther from
node; this ensures that any node near a destination can use a nearby location server to
find the destination, and also limits the number of location servers for each node.
Therefore, the graph representing the connection between each node and its location




F2

F1 AP2
AP1
D
S




Figure 13.1. The communication network when traditional routing (dotted lines) and anchor paths
(thick lines) are used.
360 SELF-ORGANIZED AND COOPERATIVE AD HOC NETWORKING


servers has the sparse, clustered, and small-diameter characteristics of a small-world
graph.


13.3 COOPERATION MODELING

In all the communities, a certain degree of cooperation is needed to carry on all the com-
mon tasks. Cooperation can be the result of a strong hierarchy induced in the group (e.g.,
in ant or bee colonies, where each member has a clear role and there is a set of critical
tasks is assigned to each role), or of a more or less spontaneous altruism (like the mutual
grooming of birds). In both cases, cooperation leads to undoubted benefits: group equilib-
rium, probably reached after a long time, is maintained, and every community member
achieves some personal advantage by helping others.

<<

. 68
( 87 .)



>>