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 solutions in a bottom-up approach, 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 neighbors within DTN transmission range, which is the building block for all applications relying on short range wireless communication. We firstly give an analytical review on 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 WiFi access points. It is scalable with node density 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 essential part of DTN communication. Our solution Plankton was motivated by an observation that most existing DTN connection prediction algorithms are 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 saving. 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 example 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? update by collecting information from 15% to 25% nodes only.

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