Technical Report PHD-2009-05

Title: Probabilistic Middleware Services in Wireless Mobile Ad-Hoc Networks
Authors: Gabriel Kliot
Supervisors: Roy Friedman
Abstract: Mobile Ad-Hoc Networks (MANETs) are a special type of wireless networks in which a collection of mobile devices with wireless network interfaces may form a temporary network, without the aid of any established infrastructure or centralized administration. In order to maintain network connectivity, each host may act as a router, forwarding data packets for other nodes. Such mobile networks are especially useful when considering collaborative applications among mobile participants. For example, the nodes of the network may be deployed in a search-and-rescue mission, where all participants wish to share information about their immediate surroundings with their peers.

However, despite a decade of extensive research and abundance of potential applications, large scale multi-hop ad-hoc networks are still rarely adopted for civilian real-life usage. We believe this to be due to the lack of adequate scalable distributed middleware services specially designed for this environment. Such services can hide the complexities of an underlying dynamic network from application developers and allow a more efficient use of network resources (such as bandwidth and battery life). This can facilitate development of new applications for ad hoc networks and significantly improve the quality of existing ones.

Specifically, in our research we focus on three middleware services, which are essential for an efficient implementation of a lot of distributed applications: membership, content location and data dissemination. Our approach is to provide probabilistic guarantees, while focusing on scalability and proven correctness. We do it by applying two complimentary approaches. First, by devising protocols with mathematically proven guarantees and well understood trade-offs in a theoretical framework that is commonly used to model ad hoc networks. Second, by validating them through simulations, which provide a more realistic and flexible environment. We believe that probabilistic constructions are more adaptable to the dynamics and unpredictability of ad hoc networks and allow greater flexibility of the design trade-offs (guarantees vs. cost).

We start by presenting a number of Random Walk (RW) based techniques, which we use later in our protocols as basic building blocks for search and sampling. RWs do not require a priori knowledge of all network nodes and do not use multi-hop routing, which makes them very attractive for ad hoc networks.

In Chapter 4 we present RaWMS, a novel lightweight membership service for ad hoc networks. The service provides each node with a partial uniformly chosen view of network nodes. The design of RaWMS is based on a novel reverse random walk sampling technique. A random membership service is useful, e.g., for data dissemination, lookup and discovery services, peer sampling services, and complete membership construction. We also utilize this membership service in our content location service, presented next.

In Chapter 5 we focus on a content location service, which allows every node to share the data with other network nodes, as well as to find and fetch this data. Such a service increases the collaboration between users of an ad hoc network, by enabling a variety of applications, such as providing web browsing capabilities to mobile devices that have no (direct or multiple hop) connectivity to a wireless access point. Our location service is built on top of a probabilistic quorum system. We explore several access strategies for implementing probabilistic quorums in ad hoc networks and present the first detailed study of asymmetric probabilistic bi-quorum systems. In particular, we show that one of the strategies that uses random walks exhibits the smallest communication overhead, thus being very attractive for ad hoc networks.

In Chapter 6 we concentrate on dissemination services, which allow delivering a piece of information to all network nodes. We tackle the problem of reducing the number of collisions of simultaneous broadcast transmissions, which are inherent to a lot of dissemination services. First, we present jitter - the technique for randomly delaying (jittering) the transmission time of broadcast messages. Next we examine, both formally and by simulations, several approaches for implementing transmission jittering in MANETs. In particular, the interplay between the maximal jitter duration, transmission success probability and throughput of the network is investigated. Finally we show how jittering can be used to reduce broadcast collisions and subsequently increase throughput, with negligible latency cost.

In Chapter 7 we briefly describe a real-life application for ad-hoc networks that we have developed. WiPeer (Wireless Peer) is a suit of Serverless P2P collaborative applications for wireless networks. WiPeer simplifies the way people create and use ad-hoc networks, by integrating a set of P2P collaborative applications into a single unified suite. The wide adoption and the publicity of WiPeer is a clear evidence of the great potential and applicability of ad hoc networks.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2009
To the main CS technical reports page

Computer science department, Technion