25-08-2017, 09:32 PM
Uisce: Characteristic-based Routing in Mobile Ad Hoc Networks
Uisce Characteristic based Routing.pdf (Size: 577.29 KB / Downloads: 185)
Abstract
The goal of communication in computer networks is
the delivery of information to endpoints with certain properties.
In wired networks, identities such as IP addresses are used
to guide information through a network and the properties of
network nodes are mapped to these identities by service discovery
mechanisms. In mobile ad hoc networks (MANETs), identities
lose their guiding ability because of the dynamism of the topology.
Instead of identities, we introduce a concept called a characteristic,
which describes the properties of nodes. Characteristics
are disseminated throughout a network, simulating the flow of
water streams. Messages are forwarded to their destinations
- nodes with given properties - following these characteristics
like following a water stream to its source. Characteristic-based
routing differs from existing content-based routing in that a
characteristic describes features of MANET nodes rather than
contents of data messages. A trace characteristic is left by
data messages along their forwarding path. Subsequent data
messages can be forwarded to the same destination node and
reply messages can be delivered back to the sender of data
messages following the trace characteristic.
We demonstrate that a characteristic-based approach increases
the rate of successful delivery in comparison to existing identitybased
approaches in MANETs. Then we analyze the ability
of trace characteristics to maintain routes for subsequent data
messages in different mobility settings.
I. INTRODUCTION
In current communication architectures, the Internet Protocol
(IP) suite provides identity-based addressing and routing
at network layer. Service discovery is achieved at application
layer by maintaining a mapping between the identity of a node
and the services that the node provides. In wired networks,
IP address describes the location of a network node, i.e. the
subnet that the node is attached to[2]. However, the location
of nodes changes frequently in MANETs. IP addresses lose
the meaning that they have in wired networks. Rather, they
are used as identities to differentiate nodes.
We argue that identity-based end-to-end communication
does not suit MANETs. First, identity-based routing is misdirected:
it is the properties rather than the identities of nodes
that are of primary interest. Second, the topology of a MANET
consisting of individual nodes is more dynamic and prone to
communication failure than the topology of services in such a
network. Shown in Fig.I, S1 and S2 provide the same service
that the requestor C is interested in. From the perspective
of individual nodes (Fig.1(a)), the failure of an intermediate
link disrupts the provision of a service; In contrast, from the
C
S1
S2
1
3
2
S1, S2: Service providers
C: Service requestor
(a) Identity-based
1 C
3
2
S
S: Service provided by S1 and S2
C: Service requestor
(b) Service-based
Fig. 1. Topologies of a MANET
perspective of service (Fig.1(b)), the failure of an intermediate
link has less effect on the provision of the service.
Content-based routing (CBR) has been proposed to address
the aforementioned issues of identity-based approaches. Instead
of identities, in CBR data messages are routed based on
their content and the subscriptions of nodes. Therefore senders
and receivers are loosely coupled and communication is less
affected by the frequent network changes. A limitation of CBR
is that by itself CBR only provides one-way data delivery from
content publishers to subscribers. Because the two ends of a
communication are loosely coupled, it does not address the
issue of delivering data from subscribers back to publishers,
i.e. two-way communication is not supported by CBR.
In our protocol Uisce, we introduce a concept called a characteristic.
A characteristic describes information of general
interest about a MANET node. It can be service description,
as used in service discovery, or features of a node such as
type of CPU, battery power, etc. We propose a potential-based
approach for dissemination of characteristic information. To
establish a two-way communication, a characteristic is left
by data messages along the path. Further communication will
follow the characteristic towards specific nodes.
II. SERVICE DISCOVERY
Service information includes service name, service description,
service type, etc. It is advertised periodically with the IP
address of its provider. A database of this information, called a
directory, can be used to facilitate communication between service
providers and requesters. A service provider registers its
information with a directory and a service requester contacts
a directory for the IP addresses of providers. The requester
then contacts a provider for a service invocation. Based
on the existence of directories, service discovery protocols
can be classified into three categories: centralized directorybased
solution [3], distributed directory-based solution [4], and
directory-less solution [1]. Compared to centralized solution,
directory-less solution suits more in a dynamic MANET while
2011 The 10th IFIP Annual Mediterranean Ad Hoc Networking Workshop
978-14577-0900-5/11/$26.00 ©2011 IEEE 119
distributed solution achieve a better scalability. [5]. However,
regardless of the structure, the service discovery is strongly
coupled with IP as a service is associated with an IP address.
III. CHARACTERISTIC-BASED COMMUNICATION
Majority of identity-based routing protocols use the distance
of a path, such as hop count and delay experienced, as
routing metric. Resource discovery such as service discovery,
on the other hand, uses the capacity of resources as metric
when selecting providers. Characteristic-based routing uses a
potential-based method to combine the two metrics into one
to integrate route discovery with resource discovery.
Each characteristic at its source node is assigned a potential
value called weight to represent its capacity. The dissemination
of characteristic information simulates a water stream: water
propagation is driven by potential value, from high to low.
And during the propagation, water flows lose their potential
value. Multiple streams merge into one at intersection point,
form a new stream and propagate further. The higher capacity a
characteristic contains, the further it may propagate; the closer
to a character source, the higher capacity could be sensed.
Different characteristics may have different form of weight
changes during propagation, depending on the nature of the
characteristics and the network environment they run through.
For example, internet connection is preferable to nodes in
the vicinity, while a printing service may function in a much
larger area. We introduce three "knob" functions to tune the
form of weight changes as a characteristic propagates. Data
forwarding is driven by weight gradient. In this way, route
selection balances between the distance to a source node and
the capacity of a characteristic.
A. Characteristic Flow
Periodically, every node broadcasts its characteristic information.
Its neighbours inherit these characteristics and spread
them out further during their broadcasts. A node has only the
knowledge about the characteristics of its one-hop neighbours.
During the one-hop based propagation of characteristic
flows, a weight cost function is applied to simulate the weight
lost over a link. The capacity of a characteristic perceived
by a remote node decreases as the distance to the source
node increases. This reduction arises from error-prone wireless
links as well as the potential consumption of the resource
along the path. Consider the example of internet access, a
route that consists of multiple hops will not achieve the
same throughput as a single hop communication. The weight
decrease at each hop forms a weight gradient to the anonymous
sources of a characteristic. Characteristic propagation is driven
by weight gradient: the characteristic information can only
flow from nodes with higher weight to nodes with lower
weight. A predefined constant wdif is given to control this
aspect of propagation: a node which contains a characteristic
with weight w accepts an incoming characteristic of the same
type only if it has a weight no lower than w−wdif , see Fig.2.
Multiple sources of a characteristic may coexist in a
MANET. Information about various source of the same characteristic
will merge when they meet at an intermediate node.
The resulting weight of the merged characteristic is computed
by weight fusion function.