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

随着无线计算设备尺寸的缩小和能力的日益多样性，无处不在的计算的价值正迅速成为真实的。随着这些设备的数量激增，它们的配置，管理和组织作为ad-hoc网络环境被证明是一个具有挑战性的研究领域。在大多数情况下，这些设备的交互能够实现广泛的应用。一组这样的设备可以彼此通信以实现特定于应用的目标，即，它们通过智能地相互通信来执行更高级别的任务或服务。这个建议是调查和开发一个分布式的框架来执行复杂的任务，而不是通过使用预先配置的设备，而是通过选择合适的计算元素的任务要求和设备特性的基础上。这项工作的一个先决条件和使能组件是创建一组自组织协议，用于在任务的生命周期内以最小的应用程序干预连接和管理这些计算元素。这样的协议被称为“智能”协议。 现有的组织设备的协议受到限制，他们对可用的基础设施的依赖，主要是因为使用基于目录的服务发现，因此是一个真正的ad-hoc计算环境的价值较低。这个提议的一个关键前提是，任务的性质可以被利用来组织无处不在的计算设备到基于逻辑任务的组。然后，任务由描述设备如何相互交互的依赖关系或任务图表示。提出了一种分布式机制，用于在计算元素网络上构建和嵌入任务图，以实现”智能”任务执行。此外，任务感知路由协议，以减少路由延迟的建议。这种方法的一个预期结果是，更大、更复杂的服务可以很容易地由更小的服务组成。因此，这些协议可以快速部署在ad-hoc环境中，使新的应用在不同的领域，如智能家居和办公室，分布式机器人，传感器网络，大规模分布式计算，智能战场，危机管理等。 本研究的具体任务是：（1）开发有效的分布式算法，用于从大量的有系链或无系链设备中发现能够一起执行分布式任务的合适设备，以及执行这些分布式任务的协议;（2）开发使用关键链路状态信息的任务感知路由协议;（3）规范使用状态增强技术来尽可能无缝地处理用户和设备的游牧性：（4）使用公共域网络模拟器来模拟上述协议;以及（5）使用商品硬件和软件实现概念验证原型。

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 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. This proposal is to investigate and develop a distributed framework for executing complex tasks not by using pre-configured devices but by selecting suitable computing elements 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. Such protocols are referred to as "smart" protocols. Existing protocols for organizing devices are constrained by their dependence on available infrastructureprimarily because of the use of directory-based service discovery and are therefore less valuable for a truly ad-hoc computing environment. A key premise of this proposal is that the nature of the task can be exploitedto organize ubiquitous computing devices into logical task based groups. Tasks are then represented bydependency or task graphs that describe how devices interact with each other. A distributed mechanism isproposed for constructing and embedding a task graph on a network of computing elements for"\smart" taskexecution. Additionally, a task-aware routing protocol for reducing routing delays is proposed. An expectedoutcome of this approach is the ease with which larger, more complex services can be composed from smallerservices. These protocols can thus be rapidly deployed in ad-hoc environments enabling new applications indiverse areas such as smart homes and offices, distributed robotics, sensor networks, large scale distributedcomputing, smart battlefields, crisis management, etc. Specific tasks of this research are: (1) the development of efficient distributed algorithms for discoveryof suitable devices that can together perform a distributed task from within a sea of tethered or tetherlessdevices, and protocols for execution of those distributed tasks; (2) the development of task aware routingprotocols using key link-state information; (3) specification for the use of state augmentation techniques forhandling nomadicity of users and devices as seamlessly as possible; (4) the simulation of the above protocolsusing public domain network simulators; and (5) the implementation of a proof-of-concept prototype usingcommodity hardware and software.