Ph.D Thesis

Ph.D StudentKliot Gabriel
SubjectProbabilistic Middleware Services in Wireless Mobile
Ad-Hoc Networks
DepartmentDepartment of Computer Science
Supervisor PROF. Roy Friedman
Full Thesis textFull thesis text - English Version


Mobile Ad-Hoc Networks (MANETs) are a special type of wireless networks in which a collection of mobile devices with wireless network interfaces 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 packets for other nodes.

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 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.

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.

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.

We next 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.

We later focus on a content location service, which allows nodes to share the data, as well as to find and fetch it. Our location service is built on top of an asymmetric probabilistic bi-quorum system.

In the end we concentrate on dissemination services, which allow delivering a piece of information to all nodes. We focus on reducing the number of collisions of simultaneous broadcast transmissions, usually used by dissemination services and present jitter - the technique for randomly delaying (jittering) the transmission time of broadcast messages.