Chapter 2 Previous Work
Providing efficient service discovery in a mobile ad hoc network is a complex task. Various solutions have been proposed for service discovery in MANETs. These solutions can be categorized by the level of integration between the service discovery techniques and the underlying routing protocol. Previous research suggests that integrating service discovery with a MANET routing protocol can increase the efficiency and improve the performance of the service discovery process. This chapter presents a brief overview of routing protocols for mobile ad hoc networks. Service discovery techniques are then reviewed with respect to how they are integrated with MANET routing protocols. In Section 2.1, a general overview of mobile ad hoc network routing is presented. Section 2.2 reviews the most popular service discovery solutions. These solutions are analyzed based on their level of integration with the underlying routing protocols in Sections 2.3 and 2.4.
Mobile Ad Hoc Network Routing
Different approaches have been taken to address the problem of routing in a self-organizing and dynamic mobile ad-hoc network. In reactive routing approaches a routing protocol does not take the initiative for finding a route to a destination until it is required. These protocols only attempt to discover routes on demand and by flooding queries in the network. Reactive routing protocols can often reduce control messaging overhead at the cost of increased latency in finding routes to the destination. The Ad-hoc On-demand Distance Vector (AODV) , Dynamic Source Routing (DSR) , and Temporally-Ordered Routing Algorithm (TORA)  routing protocols lie in this category of reactive routing protocols. Proactive routing protocols are based on periodic exchange of control messages. The route to the destination is provided immediately when needed, but often at the cost of higher control overhead. Optimized Link State Routing (OLSR)  is a proactive routing protocol that reduces control overhead through its optimized flooding techniques and compact control messages. Zone Routing Protocol (ZRP)  is an example of a hybrid routing protocol for mobile ad hoc networks. ZRP divides the network into overlapping routing zones. The intra-zone protocol (IARP) proactively generates a zone topology. Hence, nodes within a zone hold a topology of the neighbors in that zone. The reactive inter-zone protocol (IERP) determines inter-zone routes for packets by sending route request (RREQ) messages to all border nodes in a reactive manner.
OLSR is an example of an optimized link-state routing protocol. It is discussed in more detail here since it is the basis of the system developed in this research. Due to its proactive nature, it has the advantage of having the routes immediately available when needed. It also inherits the stability of a link-state routing algorithm. In a pure link-state protocol, all the links with neighbors are declared and flooded to the entire network. To improve performance in an ad-hoc mobile environment, OLSR reduces the size of control packets. Instead of all links, it declares only a subset of links with its neighbors for which it serves as a multipoint relay selector (MPRS). The protocol is particularly suitable for large and dense networks, as it minimizes the flooding of its control traffic by using only the selected nodes, called multipoint relays (MPR) to diffuse its messages through the network. Only the multipoint relays of a node retransmit its broadcast messages. Apart from normal periodic control messages, the protocol does not generate extra control traffic in response to link failures and additions. Participating nodes in the topology keep an updated topology table with information regarding links between nodes in the network.
Overview of Service Discovery Protocols
Protocols designed for discovery of services in fixed infrastructure networks mostly rely on centralized approaches that assume reliable communication in the network. Previous solutions for service discovery include the following.
- JINI 
- Salutation 
- Universal Plug and Play (UPnP) 
- Universal Description, Discovery and Integration (UDDI) 
- Service Discovery Protocol (SDP) 
- Service Location Protocol (SLP) 
These protocols utilize special nodes acting as central service repositories, where service providers can register their service offerings. The clients then broadcast service discovery messages to locate service coordinators in the network. Direct messages are then sent to the service coordinators for service binding and registrations. In typical mobile ad hoc network environments, the topology is not stable and wireless link conditions are continuously changing. Hence, service discovery protocols that are intended for fixed wired networks are not efficient and practical for wireless MANET applications. This has motivated recent research targeting service discovery in MANETs, including the following.
- Alliance-based Service Discovery for Ad-Hoc Environments (Allia) 
- Grid Service Discovery (GSD) 
- DEAPspace 
- Konark 
- Service Awareness and Discovery in Mobile Ad Hoc Network (SANDMAN) 
These protocols facilitate discovery of various network services independent of the underlying routing protocol. Hence, these protocols rely on a MANET routing protocol for providing end-to-end routing of service discovery messages creating additional overhead to support service discovery functions in addition to routing functions.
Service Discovery Independent of Routing
All service discovery protocols implemented independent of the routing layer require the support of a routing protocol. This creates additional control message overhead. These protocols can be further categorized based on the service discovery architecture, which can be centralized, direct, or hybrid in nature.
Centralized Approach to Service Discovery
In the centralized approach dedicated service coordinator nodes are responsible for providing information regarding the available services in the network. Using such a centralized method is not suitable for a mobile ad hoc environment. Link conditions and interference in the wireless network can cause topology partitioning and make the central specialized service directory nodes unreachable. This can further limit service discovery and lookup, hence preventing nodes from locating available services in the network. The Universal Description, Discovery and Integration (UDDI) service discovery scheme  is an example of a centralized approach.
Direct Approach to Service Discovery
As an alternative to the centralized methods, direct approaches define a decentralized architecture without relying on particular designated nodes. A client floods the network with service discovery messages. Each service provider then responds with a service reply message if it finds a match to the service request. This direct approach can be expensive in ad hoc networks that have limited wireless communications resources since it may cause a large number of broadcast messages to be transmitted throughout the network whenever a client attempts to locate a particular service. This creates significant overhead in the case of on-demand routing protocols. In proactive routing protocols, the service discovery messages do not affect the number of routing messages. Additionally, the direct approach has the potential drawback of limiting the service availability in presence of topology partitioning. The service discovery schemes that follow a direct approach include. Universal Plug and Play (UPnP) , Service location Protocol (SLP)  and DEAPspace .
Hybrid Approach to Service Discovery
The hybrid approach combines aspects of both direct and centralized solutions. Using the hybrid approach can further limit periodic exchanges of service discovery message broadcasts to a node’s neighborhood. These schemes may rely on hierarchies where particular nodes proactively broadcast service discovery messages in the network to announce availability of new resources. Protocols that utilize a hybrid service discovery architecture are Salutation, Konark, Jini.
Service Discovery Integrated with Routing
The proposed protocols for MANET service discovery that are independent of the routing protocol can lead to a high level of messaging overhead. It is important to realize that both the service discovery and the underlying routing protocol utilize flooding techniques to discover other nodes and resources in the network. Hence, integrating service discovery with the routing protocol can significantly reduce additional control overhead and significantly increase service availability in mobile ad hoc environments.
Additionally, good service selection based on a routing protocol’s route and topology information can group clients with nearby servers, resulting in localized communication that can reduce interference and allow for multiple concurrent transmissions in different parts of the network. The cross-layer service discovery approach, which integrates service discovery and routing, leverages existing routing control messages for service discovery and allows clients to switch to closer servers as the network topology changes. As a result, the number of control messages needed for service discovery can be reduced by coupling service discovery with the underlying MANET routing protocol. In Section 2.4.1 and 2.4.2 the integration strategies are further categorized based on the underlying routing protocol used for disseminating service discovery messages throughout the network.
Service Discovery using Reactive Routing Protocols
Koodli and Perkins  propose integration of service discovery with an underlying reactive routing protocol. In their approach Service Discovery Requests (SREQs) are piggybacked on Routing Request (RREQ) packets and Service Discovery Replies (SREP) are added on Routing Reply (RREP) messages. This solution mainly relies on a reactive routing protocol, such as AODV, DSR, or TORA, and, therefore, suffers from increased latency of service discovery as network size and node mobility increase. Broadcast service discovery traffic triggers additional control messaging in the underlying reactive routing protocol and significantly increases the routing message overhead in the network.
Service Discovery using Proactive Routing
In proactive link state routing protocols, every node maintains a topology table with regularly updated information on the links between the participating nodes. Integrating service discovery and binding with network topology can result in immediate service discovery after information convergence in the network. Using an integrated service and topology table, nodes can choose closer service providers and effectively enhance service selection in the network. Effective service selection can improve network throughput by up to 400 percent . The availability of explicit routing information such as route breaks or updates allows clients to efficiently detect changes in the network topology and switch to closer servers without additional delays.
Service Discovery using OLSR
Jodra and Vara  propose adding a new message type, called a Service Discovery Message (SDM), to the OLSR routing protocol. SDM messages are eight bytes long and are used by service providers to announce new services available in the network. New services are advertised once, with a specific lifetime, and cached at each node. Client nodes send broadcast query messages when unable to locate a service in the local cache. These SDM messages are then forwarded by MPR nodes through the network.
A similar approach is taken by Li and Lemont  by coupling support for the Session Initiation Protocol (SIP) for real-time session service location and discovery with the OLSR routing protocol. In both the proxy-based and proxy-less SIP networking architectures, a key issue for providing support for SIP in a MANET is service location and discovery, i.e., determining the location of the SIP server node where SIP signaling messages can be sent. In their approach, a new Service Location Extension (SLE) message type is added to OLSR to provide service location support for SIP service discovery. In the SLE message, a service is advertised with a service-type field and one or more Uniform Resource Locator (URL) fields denoting SIP server location(s). MPR nodes forward the SLE messages through the network. SIP servers periodically advertise their location using the SLE messages. The SLE messages can also be used by clients as a query message to request the location of a SIP server.
2. Previous Work
2.1 Mobile Ad Hoc Network Routing
2.2 Overview of Service Discovery Protocols
2.3 Service Discovery Independent of Routing
2.4 Service Discovery Integrated with Routing
3. Problem Statement and Methodology
3.1 Problem Statement
3.2 Goals and System Definition
3.3 Performance Metrics
3.4 Validation and Tradeoffs
4. MANET Information Dissemination: Design and Integration with NRL OLSR
4.2 Client Registration Scheme
4.3 Receiving and Processing Updates From Local Users
4.4 Topology Server Event Processing Scheme
4.5 Routing Process Separation
4.6 Bucket Data Unit Message Format
4.7 Information Dissemination Using Buckets
4.8 TC Bucket Fragmentation
4.9 User Priorities and Service IDs
4.10 Information Dissemination Radius
4.11 MPR Nodes and Bucket Aggregation
5. Information Dissemination: Experimentation, Testing, and Results
5.2 Test Configuration
5.3 Test Performance Metrics
5.4 Test Platform.
5.5 Test Clients
5.6 Test Variables
5.7 Test Runs
5.8 Results and Analysis
6.4 Potential Future Work.
GET THE COMPLETE PROJECT
An Extensible Information Dissemination Scheme over the Optimized Link State Routing Protocol for Mobile Ad Hoc Networks