Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks

不可靠移动自组织网络中可靠计算的理论基础

• 批准号: 0726514
• 负责人: Nancy Lynch
• 金额: $ 27.5万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0726514&HistoricalAwards=false
• 关键词: Theoretical; Foundations; Reliable; Computing; Unreliable

"Theoretical Foundations for Reliable Computing in Unreliable Mobile ad hoc Networks"Nancy Lynch, MIT CSAILThis project is developing theoretical foundations---formal models, complexity measures, abstract problem definitions, algorithms, and impossibility results---to explain what can and what cannot be computed reliably in realistic, unreliable mobile ad hoc networks (MANETs). The long-range goal of this work is to provide guidance for building high quality, reliable, high performance applications for such networks. Motivating applications include data management, communication, and coordination (e.g., of people, robots, or vehicles).The assumed MANET model consists of a collection of mobile nodes, moving according to specified constraints. A special ``real world'' component provides the mobile nodes with approximate information about the current time and their own locations. Nodes communicate using local wireless radio broadcast, subject to realistic message delivery constraints. A ``contention manager'' component encapsulates strategies such as exponential backoff, advising nodes about when they are likely to be able to transmit successfully. A ``collision detector'' component provides (possibly unreliable) information to each node about messages that it might not have received.Some problems being studied arise directly from MANET applications. Others describe abstractions that are intended to simplify the task of writing applications, such as leader and cluster management services, group membership services, location services, and virtual networks. The need for reliability arises from reliability requirements of the applications and from the need for abstractions with clear guarantees.Results being sought are:(1) Definitions of realistic MANET models.(2) Definitions of application and abstraction problems with strong reliability requirements.(3) Efficient algorithms and corresponding impossibility results for these problems.(4) Integration of individual algorithmic results to yield end-to-end guarantees for high-level problems in terms of the basic MANET model.

“在不可靠的移动临时网络中可靠计算的理论基础” Nancy Lynch，MIT CSailthis项目正在开发理论基础 - 正式模型，复杂性测量，抽象问题定义，算法和不可能的结果 - - 以在现实的，不可靠的移动移动广告网络（Manets）中可靠地计算出什么和无法可靠地计算出来。这项工作的远程目标是为建立高质量，可靠，高性能应用程序的高质量应用程序提供指导。 激励应用程序包括数据管理，通信和协调（例如，人，机器人或车辆）。假定的MANET模型由根据指定约束移动的移动节点集合。 一个特殊的``现实世界''组件为移动节点提供了有关当前时间和自己位置的近似信息。 节点使用本地无线无线电广播进行通信，但要受到现实消息传递约束。 ``竞争经理''组件封装了诸如指数向退缩之类的策略，向节点提供了有关何时能够成功传输的策略。 ``碰撞检测器''组件向每个节点提供了有关其可能未收到的消息的（可能是不可靠的）信息。研究的某些问题直接来自MANET应用程序。 其他人描述了旨在简化编写应用程序任务的抽象，例如领导者和集群管理服务，组成员服务，位置服务和虚拟网络。 对可靠性的需求是由应用程序的可靠性要求以及对具有明确保证的抽象需求引起的。寻求的重点是：（1）定义现实的Manet模型的定义。（2）具有强大可靠性要求的应用和抽象问题的定义。（3）有效的算法和对这些问题的有效算法的结果。 MANET模型。