Rapid Task-based Self-Organization in Distributed Ad-hoc Spaces

National Science Foundation Grant No. ANI-0073843
Principal Investigator: Thomas D.C. Little

Project Summary

With the shrinking size of tetherless computing devices and increasing diversity in capabilities, the value of ubiquitous computing is rapidly becoming real. As these devices proliferate in number, their configuration, management, and organization as ad-hoc networking environments proves to be a challenging research domain. In most scenarios the interaction of these devices enables a broad range of distributed applications. A group of such devices can communicate with each other to achieve a goal specific to the application, i.e., they perform a higher-level task or service by communicating intelligently with each other. In this project, we attempt to investigate and develop a distributed framework for executing complex tasks not by using pre-configured devices but by selecting suitable computing elements on-the-fly based on task requirements and device characteristics. A prerequisite and enabling component for this work is the creation of a set of self-organization protocols for connecting and managing these computing elements with minimal application intervention during the lifetime of the task. We refer to such protocols as smart protocols.

A key premise of this research is that the nature of a given distributed application or task can be exploited to organize ubiquitous computing devices into logical task based groups. Tasks/Applications are then represented by resource dependency graphs or task graphs which are logical representations of how different classes of devices interact with each other in the application. We have developed mechanisms for constructing and embedding a task graph on a network of computing elements for smart task execution. Specifically, we have developed simple and efficient algorithms for dynamic discovery and selection of suitable devices in a mobile network from among a multitude of them providing the same functionality. This is carried out with respect to a proposed task graph representation of a distributed application.

An expected outcome of this approach is the ease with which larger, more complex services can be composed from smaller services. These protocols can thus be rapidly deployed in ubiquitous computing or ad-hoc environments enabling new applications in diverse areas such as smart homes and offices, distributed robotics, sensor networks, large scale distributed computing, smart battlefields, disaster relief, etc.

Specific objectives of this research are the following:

The project is supported by a mobile ad hoc networking testbed comprised of several laptop, handheld, as well as desktop computers connected wirelessly by an IEEE 802.11b network operating in DCF (ad hoc) mode.

This material is based upon work supported by the National Science Foundation under Grant No. ANI-0073843. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Participants

Graduate students: Prithwish Basu; Wang Ke, Salma Abu Ayyash.

Publications Demonstrations Technical Reports

Evaluation

Task Execution Simulator

To study the performance of our distributed task graph embedding algorithms we augmented the public domain ns-2 network simulator from ISI/UC Berkeley. A public domain graph data types and algorithms package, LEDA (from Algorithmic Solutions Software GmbH, Saarbrucken, Germany) was also integrated with ns-2 to build tasksim (we refer to the augmented version of ns-2 by this name). All algorithms that were developed during the research have been implemented and tested using tasksim. The wireless extensions to ns-2 by the CMU Monarch Project were used as a building block for simulating basic MANET MAC/routing protocols. The TCP implementation in ns-2 (inclusive of the initial 3-way handshake mechanism) was also used as a building block for our task embedding protocols. Currently we have implemented the embedding protocols above the routing/transport layer. In future, we have plans of integrating embedding with routing for gaining better performance.

Static TG-Instantiation Simulator

For fast simulation of instantiation in static scenarios in order to study the effect of probability of instantiation on the density of network topology, we developed a simple tool that generates random parameterized TGs and MANET topologies and attempts to embed the former onto the latter. This tool was built in C++ using LEDA. It is extremely effective in studying the feasibility of instantiation in a time-efficient manner since no network level transmissions are simulated.

Proof-of-Concept Prototype

We have created a modest multi-hop ad-hoc network testbed in our laboratory. This tesbed is intended to support a proof-of-concept implementation and evaluation of our task-aware discovery and routing techniques; and for the support of enabled application scenarios. The testbed is comprised of 3 desktop PCs, 7 laptop computers, and 5 PDAs (Compaq iPAQs), each equipped with wireless connectivity. The wireless cards are operated in a peer-to-peer mode (IEEE 802.11b DCF) to constitute an ad-hoc network. All Task Graph instantiation protocols are implemented in Linux for both the laptops and iPAQs. The implementation relies on public domain implementations of MANET routing protocols such as AODV and OLSR. We have successfully demonstrated the prototype using an audience polling application. Demonstrations were performed at ACM MOBICOM 2003 [pdf], Poster 1 [ppt], Poster 2 [ppt], in San Diego, and MOBISYS 2004 [ppt], [ppt]. in Boston. The demonstration is also recorded as a video.

Software Distribution

Each of the aforementioned components represents software developed in support of this project and is available for download: