See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/221148716

BF-SD-ZRP: A Smart Integrated Scheme for Service and Route Discovery in Mobile
Ad Hoc Network

Conference Paper · September 2010

DOI: 10.1109/HPCC.2010.13 · Source: DBLP

CITATIONS READS

11 852

4 authors, including:

Véronique Vèque Ridha Bouallegue

École Supérieure d'Electricité École Supérieure des Communications de Tunis
96 PUBLICATIONS 308 CITATIONS 348 PUBLICATIONS 877 CITATIONS

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Vehicular communication View project

Smart Grid View project

All content following this page was uploaded by Ridha Bouallegue on 22 May 2014.

The user has requested enhancement of the downloaded file.

BF-SD-ZRP: A smart integrated scheme for service
and route discovery in Mobile ad hoc network
Fatma Outay∗† , Florent Kaisser∗ , Veronique Veque∗ , Ridha Bouallegue†
∗ Institute
of Fundamental Electronics,
University of Paris-Sud 11
Bat 220, Orsay 91405
[email protected]
† SUP’COM, 6’Tel Laboratory

[email protected]

Abstract—Mobile ad hoc networks are characterized by their rely primarily on their assumption of the use of a centralized
highly dynamic, multi-hop, and infrastructure-less nature. Due to repository, and it is not suitable for ad hoc network scenarios.
limited computing power, scarce bandwidth, high mobility and In recent years, several protocols have been presented
the lack of a central coordinating entity, service discovery in
these network is a challenging task. The great majority of service to support the service discovery specifically designed for
discovery protocols developed for MANETs deal with the above MANET environments [1], [3]–[5]. These service discovery
issues at the application layer. protocols for ad hoc can be divided into two categories:
In this paper, we discuss the fact of implementing service centralized directory-based protocols and distributed directory-
discovery at the routing layer instead of the application layer, less protocols. In the first category, some agents of the direc-
in order to reduce Service Discovery (SD) overhead and to
limit resources consumption. We develop an integrated service
tory (or service brokers) are involved as a logical entity in
discovery protocol, called BF-SD-ZRP, utilizing a combination of a process of service discovery for a communication between
different optimization techniques: piggibacking of SD informa- client and service providers [4], [7]. However, in [1], [3],
tion on the routing messages, compact description of SD using [5], [6], the distributed directory-less approach without central
Bloom filter (BF) and service caching. Our simulation results repository has been proposed where each node is required to
allows to validate our scheme and demonstrate its efficiency in
terms of overhead reduction and service discoverability.
provide some form of directory services and locate resources
Index Terms—MANETs, Service discovery, Routing protocols, in a Peer to Peer way. The distributed directory-less protocols
Service description, Bloom filter, ZRP, OLSR. are deployed with two different models of operation: “push
model” and “pull model”. With the push model, service
I. I NTRODUCTION announcements are flooded periodically in an active manner by
service providers, so clients learn passively services available
Recent research in mobile ad hoc networks (MANETs) has by simply receiving these advertisements. While in the pull
focused on providing a basic network support such as medium model, clients are more active, requesting explicitely services,
access control, routing protocols and TCP. There is no doubt by broadcasting service requests to all the servers which will
that these issues are critical and must be resolved to meet sev- respond eventually.
eral requirements of ad hoc network environments (ie shared Although the algorithms proposed for MANET applications
wireless medium, multihop routes and their dynamic changes, differ in the approach used to search for and provide the
processing capabilities and limited resources, etc.). However, desired services, they are all oriented middleware solutions
other important researches are still in their initial stages. and are based on the common assumption that some routing
These include among others the power management, network protocols may exist below (separately from the middleware
security, and middleware services. Especially, research on mid- layer) to support the delivery of client service requests to
dleware for ad hoc networks is important to make easier the service providers or vice versa. This may make their use
development and deployment of MANET applications. Among inefficient in the ad hoc wireless networks, due to the problem
a variety of services middleware, service discovery played of redundant control packets flooding, which in part can cause
a significant role in MANETs. With the auto-configurable an extremely high network overhead.
and autonomous characteristic of ad hoc networks, mobile It is important to note that both service and route discovery
nodes should be able to automatically and efficiently discover protocols are based on the mechanism of broadcasting with
available network services, e.g., DNS, Webserver, mail server, different goals of discovery. Motivated by this interesting
print server and TFTP. Several protocols have been proposed observation, in this paper, we focus on the combination of
for service discovery in wired connection, but unfortunately these two different problems of discovery (but quite similar
these protocols can not adapt to the ad hoc environment in some sense) such that service discovery can be combined
due to its dynamic nature and very limited resources. These with the discovery of a route to those services. As the SD
service discovery protocols like Jini, UPnP and SLP, etc., takes place at the application layer and routing is a network
issue, we develop a cross-layer approach. network. This approach exploits the ability to acquire infor-
In this paper, we focus on integrated approaches of service mation service with routing information (the same message) by
and route discovery. In our previous work [2], we have superimposing the information service with routing messages.
introduced our scheme of combining service and route dis- In this way, redundant transmissions of service discovery
covery, using a smart compression scheme “Bloom filter” for packets at the application layer are avoided and more resources
service description , and theoretically proved that by exploiting will be saved.
service discovery information provided by the routing layer, The idea of providing a routing layer support for service
the resulting communication overhead is significantly reduced discovery was first introduced by Koodli and Perkins [6]. They
and the service discovery efficiency is proved. In this paper, we add extensions to the ad hoc routing protocols to provide sup-
develop our integrated approach on a simulator by modifying port for service discovery and route to these services together.
the ZRP protocol. Our simulation results allows to evaluate However, no experimental evaluation of their proposal has
our scheme and demonstrate its efficiency in terms of overhead been published so far.
reduction and service discoverability. Another integrated approach was proposed by Jodra in [8],
Our approach was to implement service discovery in the in which, he presents a solution to integrate service discovery
routing layer by piggybacking the service information into the with routing protocol OLSR. The various messages in OLSR
routing protocol control messages, thus enabling the devices to share a common message header. Using this header, a new
acquire both service and routing information simultaneously. message called Service Discovery Message (SDM) was intro-
This way a node looking for a service, in addition to discover- duced. The SDM packet may contain either an announcement
ing the service, it is also informed of the route to the service or request for service. However, OLSR is a proactive routing
provider at the same time. We extended the hybrid routing protocol, to maintain updated routing tables, it introduces a
protrocol ZRP [15] considerable overhead. In addition, it should be noted that no
Differing from existing work on cross-layer service discov- comparison with other protocols or integrated application layer
ery, this paper focuses to support low bandwidth environments has been presented.
and investigates an efficient way to describe services using Another scheme proposed in [9], is to implement service
Bloom Filter combining with service caching. The analysis and discovery at the routing layer by piggybacking service in-
simulation results show that our optimised approach named formation, using UUID descriptor, into ZRP routing protocol
(Bloom Filter based Service Discovery combined with ZRP control messages, thus enabling the terminals to acquire the
BF-SD-ZRP induces very low overhead compared to other service and routing information simultaneously.
integrated protocols and satisfy several network issues, where As direct comparisons of integrated approaches are diffi-
each node should discover the maximum number of services. cult due to lack of certain performance data compatible for
The reminder of this paper is organised as follows: In sec- different protocols, a rough categorization regarding the type
tion II we briefly present some existing integrated approachs of of routing protocol (reactive, proactive or hybrid), the most
routing layer supported service discovery and their limitations. efficient (in terms of Overhead) when including a service
Section III presents BF-SD-ZRP protocol in details. Section discovery protocol is desired.
IV describes our implementation and discusses the simulation ZRP seems to be the most appropriate protocol for this type
results. Finally, in section V we provide our conclusion and of network using the following criteria:
introduce our future research directions. • It is ideal for environments where local information,
either routing or service information, is of particular
II. E XISTING I NTEGRATED SCHEME
interest because it can discover (through the concept of
In an ad hoc network, each message transmission consumes zones) in a fast and efficient way in terms of resources
a considerable amount of network bandwidth as well as some consumption.
processing power and battery at each crossing by a node along • It is scalable as it propagates in an intelligent way the
its path. The discovery service itself requires the exchange of information to remote nodes by avoiding floods.
many messages. The subsequent discovery of a route to the The approach described in [9] seems to be ideal in terms of
service provider via the underlying routing protocol requires choice of routing protocol because the cross layer solution
a further exchange of messages. However, when integrating used is based on ZRP protocol, however, in terms of service
service and route discovery, we are able to discover a service description, using the universal identifiers UUID is not the
provider and a route to it using the same set of messages. optimal solution.
Therefore, a combined approach will significantly reduce
the consumption of bandwidth and the total latency in the A. Limitations of existing service discovery approaches in
discovery process of a service and a route to its provider. term of service description
Traditionally, service discovery is considered as a function There are different approaches to describe service informa-
of the application layer. However, in this paper, we examine tion in requests and advertisements (ads). Many service dis-
the execution of service discovery at the network layer in covery protocols use XML to describe the service information.
order to reduce the communication and processing overhead. Such a method is adopted in [1]. Another approach is to create
Such a modification is reasonable in the case of an ad hoc service descriptors from ontologies designed for semantic
web services using the Web Ontology Language (OWL) as
proposed in [10]. Using this approach, the ontology must be
shared between nodes before communication. However, XML
and OWL descriptions require considerable bandwidth, which
is sparse in ad hoc networks. A kind of compression can be
used to fill this gap if rich and flexible service descriptors
are necessary. Some proposals aim to reduce the consumption
of bandwidth, and do not see the benefits of using XML or
OWL as necessary. By mapping a set of service descriptors
to a predefined set of integers as in [8] or unique identifiers
Universal (UUID) as in [11] and [9], the description can be
reduced by a few bytes.
These solutions can save bandwidth compared to the trans-
Fig. 1: SvcCache and IARP table update and interaction upon
mission of XML files. However, these solutions are neither
receiving of NDP “hello” messages announcing video (1000)
flexible enough nor scalable, when the maintenance on each
service provided by node I and printer (1100) service provided
network node is required when adding new categories of
by node G. Node D looks for a printer service, which is
services. From these studies, we found Bloom filters [12].
converted into a BF (1100), it checks first its SvcCache,
Using Bloom filters, any textual description of services can
retrieves the printer’s provider which is G and looks for a
be hashed into an array of defined size without requiring a
route to G in its IARP Table.
predefined set of stationary keywords.
III. BF-SD-ZRP DESIGN
A. Overview service informations are stored: provider, service name (as a
BF vector) and its lifetime. When a node wants to use a service
In this paper, we propose the piggybacking of service
(Figure 1), checks its cache, if it is found, retrieves its provider
information into routing messages to reduce communication
address and check for a route to it in the routing table.
overhead and latency and prove the effeciency of service
The protocol uses local services caching advertised by
discovery. We demonstrate the advantages of our approach
neighbour nodes to save network bandwidth and reduce la-
(i.e., routing layer supporting service discovery) by extending
tency of discovery. The process of service discovery and
the routing protocol (ZRP), which is an hybrid routing protocol
location of provider is described in the algorithm1:
(i.e., proactive in a number of hops around a node called the
node zone, and reactive for applications outside this zone), so it
is able to encapsulate service information in its messages. We Algorithm 1 Return P x provider of service X
have changed the behaviour of ZRP protocol to support service Require: SvcCache not empty
information. We have added an extra field in NDP packets. 1: if ∃LookupSvcCache(X) then
Our intention is to evaluate the performance of a combined 2: P x ← LookupSvcCache(X).@
approach in several scenarios. Our proposal also introduces a 3: if ∃RoutingT able(P x) then
cache of discovered services for each node in the network. 4: Return P x
Bloom Filters are used to describe service information 5: end if
encapsulated in routing messages. Our service discovery ap- 6: end if
proach is used to distribute the filters using a protocol format
that extends the routing protocol ZRP.
In order to add mechanisms for service discovery to the ZRP B. Service description using Bloom Filter
protocol, we incorporated an additional field in the “hello” In our context, the intention of Bloom Filter is to represent a
messages to store the service identifier. We used the concept set S = (x1, x2, ..., xn) of service descriptors n in an efficient
of Bloom Filter instead of service descriptions to keep small manner. We begin by defining a V Bloom Filter implemented
size of packets for routing messages and minimize the impact as an array of m bits. All bits (1, ..., m) are initially set to
on the network (the bigger the messages, the larger the delays 0. The filter uses k independent hash functions h1, h2, ..., hk
and the possibility of transmission errors ). Such an approach With the range (1, ..., m) for hashing each service descriptor
requires that all nodes use the same number of hash functions x in the filter V . For each service descriptor x ∈ S, the output
and the same MD5 [17] cryptographic algorithm to convert a hash hi(x) represents a position in Table V , V [hi(x)] is set
service description into a Bloom Filter. to 1 for all hash functions i = 1, 2, ..., k. One position in
ZRP has been extended to include service information in V can be set to 1 several times, but it is clear that only the
each entry of IARP routing messages. Each node of the ad first change has an effect. Figures 2(a) and 2(b) illustrate two
hoc network uses a cache SvcCache where every provided different services hashed with three hash functions, and then
service will be stored through service announcements gathered added to the same filter. To check whether a service z is in
from the incoming NDP packets . In this cache the following the Bloom Filter, we must determine whether all hi(z) are set
 Algorithm 2 Calculate the Bloom Filter V for a service X
1 1 Require: : x 6= 0
0 1
h1 Gateway h1 1: a ⇐ M D5(x)
0 0
hash("Gateway",k) = {0,3,5} h2 hash("Printer",k) = {1,3,5} h2 128
h3 1 h3 1 2: r ⇐
0 0 k
K hash functions K hash functions 3: for i = 0 TO k do
1 1
4: f ← subbits(r ∗ i, (r ∗ (i + 1)) − 1, a)
5: V [f mod m] = 1
0 0
6: end for
M-bit vector M-bit vector

(a) The first service added to the (b) The second service added to
0 1 2 3
Bloom Filter the Bloom Filter
0123456789012345678901234567890 1
Fig. 2: Construct a Bloom Filter Link Source Address
Link State Seq Num Zone radius TTL
RESERVED RESERVED Link Dest Cnt
<Node Address 1>...<Node Address n> \
1 1
Service Filter \
h1
1 h1
1
hash("Fax",k) = {2,3,5} h2 0 hash("Vidéo",k) = {1,3,5} h2 0
h3 1 h3 1 Fig. 4: IARP packet Format
0 0
K hash functions K hash functions
1 1

C. Our Protocol format

0 0
M-bit vector M-bit vector
The ZRP protocol [15] is an hybrid model between proactive
and reactive scheme. ZRP combines several sub protocols,
(a) The service is not in the Filter (b) This request give a false posi- namely, IARP (inside the zone), IERP (outside the zone),
tive
and others (NDP, ICMP and BRP... Etc..). The detection of
Fig. 3: Check a Bloom Filter neighbors is done by consulting the lower layers. ZRP simply
retrieves neighbors table provided by another neighborhood
search mechanism. This table will be used by IARP to
construct the network map. Each modification of the neighbors
to 1. If so, we assume that the service z is available. If all the table will lead to an updating of the zone by IARP and
hi(z) are not set to 1, the service is not part of the filter, as updating routing tables by IERP.
in the Figure 3(a). However, the Bloom Filter can give a false Neighbor Discovery Protocol (NDP) is implemented at the
positive if the filter indicates that the service descriptor z ∈ S, link layer. Using NDP, each node periodically broadcasts a
even if it is not (Figure 3(b)). The chances of obtaining a false “hello” message to indicate its presence. NDP updates IARP
positive can be estimated using the calculation of probabilities table, IERP uses IARP table, IERP then relays the requests
[12]. to border nodes via BRP. BRP uses IARP table to guide
The heart of Bloom Filter is a hash function. Any hash func- requests. In our implementation, we have built an extra field in
tion can be used as it is able to map an element (for example the “hello” messages to store the service identifiers. We used
service descriptor) to a uniform pseudo-random number over the concept of Bloom Filter instead of an ordinary service
the range 1...m.The results of various k hash functions must description to keep the NDP packet length small. The Bloom
be independent. One way to implement a hashing function is Filter length used in our implementation is 128 bits.
to use a serie of modulo functions [18]. Another approach Our proposed solution is therefore to distribute a summary
is to use a cryptographic hash function MD5 [17]. MD5 is of offered services in a vector described as a Bloom filter. A
deterministic and uniform, and has excellent collision resis- Bloom filter is a data structure that allows the representation
tance for our purpose. MD5 also exists as an open source of a data in a simple and unobtrusive way. The IARP packet(
code for many programming languages, and implementations figure 4) carries all the information about neighbors and their
are relatively fast. services in a Bloom filter to all zone nodes.
Our Service Discovery design uses MD5 in the following Each node has a cache in which it stores all the provided
manner: the k hash functions, which constitute the Bloom services (local and those of neighbors). In this cache, the sotred
Filter, are constructed from k groups of each r bits out of informations (provider address, service name (Bloom filter)
the 128 bit hash from the MD5 operation. Any set of sub-bits and the lifetime) are retained from received NDP packets.
from an MD5 output can be used as an input to an independent Upon receiving NDP packet, a node updates its neighbor table.
function. Each of these k functions sets one bit in the filter v. IARP listens to informations gathered from NDP messages,
In BF-SD-ZRP, the hash functions are implemented as updates its IARP table, and periodically broadcasts its table
shown in the algorithm 2: to its neighbors in IARP packets. A node distributing these
IARP update packets sets the TTL field to the radius value of 0 1 2 3
the routing zone, hence packets are dropped when arriving at 01234567890123456789012345678901
border nodes. Upon receiving of IARP packets, a node updates Message \
its service cache and its routing table. Thus, each node knows Message Type Vtime Message size
the routes to all nodes in its zone as well as services offered Originator Address
by these nodes. In the next section, we demonstrate the perfor- TTL Hop count Message Sequence Number
mance of BF-SD-ZRP in terms of overhead optimization and Service Descriptor (URL:String) \
service discovery efficiency in different network conditions.
Fig. 5: OLSR message Format
IV. P ERFORMANCE E VALUATION OF BF-SD-ZRP
A. Simulation setup
TABLE I: Default simulation parameters for ZRP and OLSR
The choice of the simulator is an essential step to test and
evaluate the performance of any new protocol. In this paper, Parameters Default Values
and in order to evaluate our approach, we will proceed to Simulation area 1000X1000m2
the simulation using the JIST/SWANS [14] toul (Java in Sim- Simulation time 130s
ulation Time/Scalable Wireless Ad-hoc Network Simulator). Data rate 10kbit/s
This will allow us to conduct a serie of tests to measure transmission range 250m
the performance of our approach and study the impact of Mac Layer 802.11b
some parameters of MANET namely the mobility degree , Default Wifi radio bandwidth 11M bit/s
the density of nodes and the choice of routing protocol. Zone radius 2 hops
In Jist/Swans, the routing entity has only three routing NDP message broadcast intervall
protocols, namely AODV, DSR and ZRP and no proactive in ZRP and BF-SD-ZRP 10s
routing protocol has been implemented. To study the perfor- IARP message broadcast intervall
mance of our integrated discovery approach, we implemented in ZRP and BF-SD-ZRP 2s
the OLSR ( Optimized Link State Routing Protocol)routing SDM message broadcast intervall
protocol [16] at the routing layer of the Jist/Swans protocol in OLSR and SD-OLSR 10s
stack. The BF-SD-ZRP protocol is compared with OLSR hello message broadcast intervall
integrated protocol and with standard ZRP routing protcol in OLSR and SD-OLSR 2s
without service information. Offered services 1 service per node
Integrating service discovery protocol with proactive OLSR
(Optimized Link State Routing) has been proposed by [8].
A new type of message, called Service Discovery Message
OLSR combined with the service discovery, and compared its
(SDM) was added. This message announces (servers) and
behaviour with our extented ZRP approach. Simulation results
requests (clients) services. Local services available will be
and performance discussions on performance are presented in
advertised only once, with a specific life time, to avoid
the next sections.
increasing the network overhead.
These services will be stored in a service cache which is B. Simulation metrics and scenarios
maintained in each node. When a node requests a service, it
will look in the local cache. If the requested service is not We have implemented our extension of ZRP on Jist/Swans
yet stored, it will send a query message. In their results, they simulator. In this section, we evaluate the performance of our
showed that the introduced packet overhead is insignificant approach. The performance is measured in terms of overhead
compared to the standard OLSR. For such a mechanism, to of control packets after the extension (after adding a service
be efficient, it is necessary that each node must know the information of size 128 bits in the NDP packet), the packet
maximum number of services without increasing the overhead delivery rate of data packets (PDR) and the impact of mobility,
of the network. density and zone radius on the efficiency of service discovery.
Our implementation of OLSR combined with service dis- Therefore, the simulations are performed by varying several
covery was based on the idea gathered from the approach factors and observing the specific performance metrics. In the
described in [8]. The SDM message format added to OLSR simulations, many different scenarios were conducted based
control messages is shown in Figure 5. Its size is 8 bytes, on metrics that we wish to assess.
including the description of the service information as an 1) Simulation Parameters: The default settings of the
URL String of size 2 bytes. In our implementation of SD- wireless network shown in Table I are used in all
OLSR, we proceeded like in BF-SD-ZRP, each node maintains scenarios of OLSR and ZRP. We have almost kept the
a service cache to store services announced in the network. same values to observe the behavior of each approach
Hence a node in our case does not need to send a service in almost the same wireless environment.
request if the requested service is not in the service cache, it 2) Metrics used in performance evaluation of BF-SD-
considers that it is not available. We studied the performance of ZRP: In all experiments we have conducted, our hybrid
 routing protocol ZRP combined with service discovery

Discovery Overhead (ZRPBytes sent/(ZRPBytes+DataBytes)sent)

(BF-SD-ZRP) was compared to a basic routing proto- 1.2
col without the integration of service information, and Overhead ZRP Static
Overhead ZRP-Modified Static
also to another integrated proactive protocol SD-OLSR.
1
Metrics maintained in the simulations are as follows:
• Overhead: is the rate of control packets sent in 0.8

the network. The overhead represents the ratio of

the size of control packets by the size of data and 0.6
control packets.
• PDR (Packet Delivery Rate): is the rate of received 0.4
data packets in the network.
• Efficiency of service discovery: is the percentage of 0.2
services discovered among all the provided services
in the network. 0
0 20 40 60 80 100 120 140
3) Scenarios and simulation results of BF-SD-ZRP As Node population
(a) Overhead generated in Static Network
we modified the NDP control packet to add a new

Discovery Overhead (ZRPBytes sent/(ZRPBytes+DataBytes)sent)

service information in the form of a Bloom Filter
of size 16 bytes, the NDP packet size has increased. 1.2
Overhead ZRP Mobile
Our objective in evaluating the Overhead metric, is to Overhead ZRP-Modified Mobile

prove that we obtain an efficient mechanism for service 1

discovery without introducing a significant overhead in

the network. 0.8

In this scenario, the overhead, which represents the

percentage (size) of control packets sent over total 0.6

(data and control) is plotted as a function of network

density, the result is shown in Figures 6(a) and 6(b) in 0.4
both mobile and static topologies. The routing overhead
introduced by the BF-SD-ZRP protocol is represented 0.2
by the dotted line. It is clearly observed that the service
information add an insignificant overhead in the network 0
0 20 40 60 80 100 120 140
in both static and mobile case. Looking at the results Node population
below, it is clear that our approach is efficient in terms (b) Overhead generated in Mobile Network
of overhead. We note that the overhead generated by our
integrated protocol is always insignificant compared to Fig. 6: Overhead generated by piggybacking service informa-
the standard protocol. It has increased only by around tion in NDP Packets
(0.09%(static) to 0.12%(mobile)) compared to the initial
overhead generated by the basic ZRP protocol.
Another set of experiment has been run to measure the 1.2
PDR ZRPmodified Mobile
PDR. We want to acheive a rate of PDR up to 100% PDR ZRPmodified Static
. Our goal is to prove that the routing protocol is still 1
efficient and works well even by adding new information
to control packets such as service information. The result
Packet Delivery Rate %

0.8
is shown in Figure 7. In this scenario, we have simulated
a network consisting of 10 to 150 nodes, we have varied
the network density, the mobility model is the Random 0.6

Walk model with a pause time of 0 seconds. We observe

from the figure that the PDR is beyond 92%, which 0.4
proves the efficiency of our combined approach.
The third metric evaluated in our set of scenarios is 0.2
the Efficiency of service discovery. To demonstrate the
efficeincy of our integrated approach in terms of service 0
discovery, we have conducted two sets of experiments. 0 20 40 60 80 100 120 140 160
In the first set of experiments, we vary the density Node density

of the network (between 10 and 150). The mobility Fig. 7: The resulting PDR after the modification of ZRP
model used in the case of mobile network is the random
 1.2 1.2

Discovery Overhead (ZrpM Bytes/(ZrpM+Data)Bytes)

Avg of discovered services in Static Network Overhead ZRP-Modified Mobile(Var R)
Avg of discovered services in Mobile Network Overhead ZRP-Modified Static(Var R)
Average of Discovered Services per Node

1 1

0.8 0.8

0.6 0.6

0.4 0.4

0.2 0.2

0 0
0 20 40 60 80 100 120 140 160 1 1.5 2 2.5 3 3.5 4
Node population Zone Radius
(a) Overhead is inscreasing with the zone radius
Fig. 8: Service discovery process efficeincy 1.2
Avg of discovered services Static Network(Var R)
Avg of discovered services Mobile Network(Var R)

Average of Discovered Services per Node

1

Random WayPoint model (RWP) at a constant speed of

3.5m/s and a pause time of 0 second. In this scenario, 0.8
we want to analyze the efficeincy of service discovery
mechanism. As shown in Figure 8, the average number 0.6
of discovered services per node was more than 98% for
mobile network and almost the same in static network 0.4
since a density of 40 nodes. For a density of 20 and
30 nodes, as nodes are placed in an area of 1000m2,
0.2
and not moving, so they are not within each other
range, therefore they can not discover all services in
the network for reasons of connectivity. We observe that 0
1 1.5 2 2.5 3 3.5 4
the protocol gives a better result when nodes are mobile Zone Radius
(b) Service discovery rate is almost constant
(meaning that each moving node meets several nodes
throughout its lifetime). Fig. 9: Compromise between overhead and service discovery
In the second set of experiements, we correlate the over- depending on the zone radius of ZRP
head generated by our integrated protocol by varying
the radius of the area (see Figure 9(a)) with the rate
of service discovery (see Figure 9(b)). We note that in
our simulation results shown in Figure 9, the overhead an hybrid routing protocol in terms of overhead opti-
increases with the zone radius. This is logical because, mization. We also want to demonstrate the importance of
when increasing the radius of the zone, the IARP packets modifying the control packets structure in order to carry
dominate the network, therefore, the protocol behave the service information, as presented in our approach,
almost like a proactive protocol, thus increasing the instead of adding another type of message circulating in
overhead in the network because of periodic sending of the network carrying service information.
control packets. Contrary to service discovery, we notice In this set of experiments, we vary the network density
that increasing the zone radius had no impact on the (between 10 and 80). To allow a fair comparison with
efficiency of service discovery. Service discovery rate our approach, in the case of a mobile network, we
in the network is always beyond 90%. kept the same mobility model to measure the overhead,
4) Scenarios and simulation results of SD-OLSR and which is the Random Walk model, with a pause time of
comparison with BF-SD-ZRP In this stage of evalu- 0, and the Random Wayoint model with a pause time
ation, we want to compare our approach BF-SD-ZRP of 0 for the service discovery efficeincy. From figures
with the integrated protocol SD-OLSR in the same ad 10(a) and 10(b), we note that the overhead generated
hoc environment with the same simulation parameters. by SDM messages is raised to 0.59% in the mobile
The purpose of this comparison is to prove that our case and 0.56% in the static case. We remark that,
proposal outperforms SD-OLSR and is more scalable. the overhead added by SDM message is almost 50%
Our intention is to demonstrate the efficeincy of using more than that for basic OLSR routing protocol. From
OLSR Versus OLSR-SDM Service Discovery Overhead

1.2 1.2
Overhead OLSR Static Avg of discovred services in Static Network
Overhead OLSR-SDM Static Avg of discovred services in Mobile Network

OLSR Average of discoverd services per node

1 1

0.8 0.8

0.6 0.6

0.4 0.4

0.2 0.2

0 0
0 10 20 30 40 50 60 70 80 10 20 30 40 50 60 70 80 90
Node population Node population
(a) Overhead of SD-OLSR in static network
Fig. 11: Service discovery rate using SD-OLSR protocol
OLSR Versus OLSR-SDM Service Discovery Overhead

1.2
Overhead OLSR Mobile
Overhead OLSR-SDM Mobile

1
1.2
Overhead Zrp Static

OLSR Versus ZRP Service Discovery Overhead

Overhead Zrp-Modified Static
0.8 Overhead OLSR Static
1 Overhead OLSR-SDM Static

0.6
0.8

0.4
0.6

0.2
0.4

0
0 10 20 30 40 50 60 70 80 0.2
Node population
(b) Overhead of SD-OLSR in mobile network
0
Fig. 10: Overhead generated by adding SDM message to 0 10 20 30 40 50 60 70 80
Node population
OLSR protocol
Fig. 12: Overhead Comparaison (BF-SD-ZRP et SD-
OLSR) in static network
figure 11, we note that the service discovery using the
SD-OLSR approach described in IV-A is also efficeint.
We observe that the discovery rate is beyond 85%. As
OLSR is a proactive protcol, the latency in the exchange SD-OLSR. To do this, we simulate the two approaches in
of control packets is too high, depending on network the same wireless environment with the same simulation
density, which is the reason for which we simulate a parameters. The result of this set of simulations is shown
network of 80 nodes maximum. in Figures 12 and 13 in a static and a mobile network.
Using the previous simulations, we found that the ser- According to the results shown in Figures 12 and 13,
vice discovery is always efficient regardless of the nature we observe the performance of our approach over the
of the routing protocol used. Therefore, in terms of per- approach SD-OLSR described in IV-A. We note that for
formance regarding the efficiency of service discovery, a network of 50 nodes, the rate of overhead generated
BF-SD-ZRP and SD-OLSR, have almost the same level by our approach is much smaller than that generated by
of performance. SD-OLSR. For a network consisting of over 50 nodes,
Thus, we would prove, by measuring the amount of we note that the dotted curve, which represents the over-
overhead generated by piggybacking the service infor- head generated by SD-OLSR protocol, is always above
mation to both routing protocols, that our approach all other curves and generates an important overhead.
performs better than SD-OLSR, i.e. that the overhead Therefore, we conclude that our approach is always
generated by our approach is negligible as compared to optimal for a large-scale network.
 1.2
Overhead Zrp Mobile with limited bandwidth. Nevertheless, the energy in this type
OLSR Versus ZRP Service Discovery Overhead

Overhead Zrp-Modified Mobile

Overhead OLSR Mobile of network, is a scarce resource. We believe that our integrated
1 Overhead OLSR-SDM Mobile
approach with other optimization techniques must target en-
ergy consumption optimization in ad hoc network.
0.8 In our next study, and with the same objective of opti-
mizing scarce and critical resources of ad hoc network, we
0.6 will introduce other optimization techniques to reduce energy
consumption.
0.4
R EFERENCES
[1] Varun Verma, Sumi Helal, Nitin Desai and Choonhwa Lee. Konark
0.2 : A service discovery and delivery protocol for ad-hoc networks. In
WCNC : In Proceedings of the Third IEEE Conference on Wireless
Communication Networks , New Orleans, March 2003.
0 [2] Outay, F. and Veque, V. and Bouallegue, R. Bloom-Filter Based
0 10 20 30 40 50 60 70 80
Combined Service and Route Discovery for Mobile Ad Hoc Networks.
Nodes population
Proceedings of the The 2007 International Conference on Intelligent
Pervasive Computing, pages 188–193, 2007.
Fig. 13: Overhead Comparaison (BF-SD-ZRP et SD- [3] Ratsimor, O. and Chakraborty, D. and Joshi, A. and Finin, T. Allia:
OLSR) in mobile network Alliance-based service discovery for ad-hoc environments. Proceedings
of the 2nd international workshop on Mobile commerce, pages 9, 2002.
[4] G. Blair M. Storey and A. Friday. Mare . Resource discovery and
configuration in ad hoc networks. in Mobile Networks and Applications
V. C ONCLUSION Journal, page 377387, 2002.
[5] Liu, J. and Sohraby, K. and Zhang, Q. and Li, B. and Zhu, W. Resource
Existing Architectures for service discovery at the applica- discovery in mobile ad hoc networks. The Handbook of Ad Hoc Wireless
tion layer suffer from redundant control messages transmission Networks, CRC Press, New York, 2003.
[6] Rajeev Koodli and Charles E. Perkins. Service discovery in on-demand
of both route and service discovery (in the sense that control ad hoc networks. Internet Engineering Task Force (IETF) Internet-Draft,
messages for information discovery are necessary at the net- October, 2002.
work layer and the application layer). In the literature, it was [7] Kozat, U.C. and Tassiulas, L. Network layer support for service discovery
in mobile ad hoc networks. IEEE INFOCOM,volume 3, pages 1965–
suggested that the service discovery can be integrated with 1975, 2003
routing, enabling nodes to find available services and routes [8] Jodra, JL and Vara, M. and Cabero, JM and Bagazgoitia, J. Service
at the same time. Therefore, fewer messages are broadcasted discovery mechanism over OLSR for mobile ad-hoc networks. Advanced
Information Networking and Applications, 2006. AINA 2006. 20th Inter-
in the network. However, no evaluation comparing cross-layer national Conference on, volume 2, 2006.
approaches of routing combined with the service discovery [9] Ververidis, CN and Polyzos, GC. Extended ZRP: a routing layer based
has been presented so far. In this paper, we presented a new service discovery protocol for mobile ad hoc networks. Mobile and
Ubiquitous Systems: Networking and Services, 2005. MobiQuitous 2005.
architecture of routing layer that integrates service discovery The Second Annual International Conference on, pages 65–72, 2005.
functionality with existing routing protocol. Our main objec- [10] Kopena, J. and Sultanik, E. and Naik, G. and Howley, I. and Peysakhov,
tive was to demonstrate the impact of such an approach on M. and Cicirello, VA and Kam, M. and Regli, W. Service-based comput-
ing on MANETs: enabling dynamic interoperability of first responders.
the efficeincy of service discovery in ad hoc environment. IEEE Intelligent Systems, pages 17–25, 20, 2005.
We have presented a method for discovering services using [11] Obaid, A. and Khir, A. and Mili, H. and Laforest, L. A Routing Based
a combination of Bloom filters and the extensibility feature of Service Discovery Protocol for Ad hoc Networks. ICNS07: Proceedings
of the Third International Conference on Networking and Services, 2007.
ZRP. Our protocol uses Bloom filters as an efficeint way to [12] Bloom, B.H. Space/time trade-offs in hash coding with allowable errors,
describe the information of an arbitrary service. The protocol Communications of the ACM, 13, pages 422–426, 1970
uses the efficient dissemination of service descriptor using [13] Sailhan, F. and Issarny, V. Scalable service discovery for MANET. Third
IEEE International Conference on Pervasive Computing and Communi-
the bordercasting ZRP protocol. In addition, the protocol uses cations, 2005. PerCom 2005, pages 235–244, 2005.
local caching to reduce discovery latency. [14] Barr, R. and Haas, ZJ JiST/SWANS, Wireless Networks Laboratory,
We have shown that service descriptor compression obtained Cornell University. http://jist. ece. cornell. edu, March 2005.
[15] M. R. Pearlman Z. J. Haas and P. Samar. The Zone Routing Protocol
from the Bloom Filter scheme (compared to transmission of (zrp) for ad hoc networks. Internet draft 4, 2002. Cornell University New
service descriptors in a text format [8]), and the subsequent York, USA, 2002.
piggybacking of service information in ZRP routing packet, [16] Clausen, T. and Jacquet, P. RFC3626: Optimized Link State Routing
Protocol (OLSR). RFC Editor United States, 2003.
does not much increase network overhead. With these opti- [17] Rivest, R. RFC1321: The MD5 message-digest algorithm, RFC Editor
mizations, it is expected that BF-SD-ZRP is better than other United States, 1992.
cross-layer proposals [8], [9]. The service cache is used to [18] Flathagen, J. and Øvsthus, K. Service Discovery using OLSR and Bloom
Filters. 4th OLSR Interop & Workshop, Ottawa, Canada, 2008.
conserve network bandwidth.
We have shown through simulations that our approach
outperforms other integrated approaches, for both fixed and
mobile environments. We find that a combination of optimiza-
tion techniques as presented by BF-SD-ZRP is inevitable in
order to support efficeint service discovery in environments

View publication stats