Resource Efficient Urban Delay/disruptive Tolerant Networks

Abstract

This thesis presents systematic research on Delay/disruptive Tolerant Network (DTN), especially for urban DTNs, e.g., opportunistic networks consisted of smart phones, and Vehicular Ad hoc NETworks (VANET) of vehicles. These DTNs are the emerging class of new communication paradigms for mobile nodes. With an emphasis on resource efficiency, we present three systematic solutions, from `how to discover communication chances?, to `how to route messages from a source node to a destination node?, to `how to aggregate data via DTN communication?. The three questions share the common features with layers in the Internet stacks, namely, link layer, network and transport layer, and application layer.

First, we discuss the solution for discovering nearby communicable neighbors within DTN transmission range, which is an essential building block for all applications relying on short range wireless communication. We firstly analytically review existing solutions and investigate the requirements on energy consumption and neighbor discovery latency. Then, we discuss our solution R2, a synchronous neighbor discovery algorithm based on Wi-Fi access points. It is energy efficient and has short discovery latency. Evaluations show that R2 can discover 90% of neighbors within 50 seconds at 1% duty cycle, with the number of neighbors from 10 to 60.

Next, we discuss message routing algorithms, which is an indispensable part of DTN communication. Our solution Plankton was motivated by an observation that most existing DTN connection prediction algorithms were not reliable. We propose a connection prediction algorithm based on short-term bursty contacts association and long-term contacts association. This significantly improves the reliance of connection prediction. By Plankton, a node controls message replica quota by the connection predictions, which serves well the goal of the resource efficiency. Evaluations show we can save 14% to 88% of message replicas compared to existing DTN routing solutions.

Finally, we present a solution for data aggregation over DTN communication, with the application of ubiquitous sensor data aggregation. We propose a novel concept on how propagated information may have changed, namely change awareness. Based on the concept of change awareness, we propose an algorithm for computing a minimum set of nodes, via which a server can collect a snapshot of the all nodes information. Extensive evaluations show that a server can obtain a global snapshot on nodes? updates by collecting information from only 15% to 25% nodes.

In a summary, we systematically investigate DTNs with the focus on resource efficiency. With the growing penetration of smart mobile commutative devices, the solutions in this thesis can contribute to the growing DTN applications.