CAREER: Self-organizing Algorithm and Protocol Design for Infrastructureless Wireless Networks

职业：无基础设施无线网络的自组织算法和协议设计

• 批准号: 0093484
• 负责人: Songwu Lu
• 金额: $ 29.99万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-15 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0093484&HistoricalAwards=false
• 关键词: CAREER; Self; organizing; Algorithm; Protocol

Emerging infrastratureless wireless networking technologies such as MANET [1], sensor networks [31],and bluetooth [2] will seek to support advanced applications such as smart environment, "zero conf"teleconferencing setups, collaborative learning, wireless access to Web services, and emergency rescureoperations. This class of applications is mission critical, and the network has to address a number of criticalissues in order to cope with the anticipated design requirements of such applications. In aninfrastructureless wireless network, no underlying infrastructure, such as cellular layout and central control units e.g. base stations, is available for networking support. A large number of networking devices are allowed to communicate with one another over the shared wireless medium in an ad hoc manner. Someunique design challenges posed by such networks include fully distributed and localized design, sustainedquality of service (QoS), efficient network resource utilization, unconstrained scalability and robust systemperformance. State-of-the-art solutions are inadequate to address these issues and meet the applications'requirements. A fundamental problem is that an infrastructureless wireless network is a large-scaledistributed system that may consist of a very large number of wireless networking components (e.g.thousands, even millions in a sensor network), which have limited power and computing resources and areprone to channel errors and failures. Therefore, any feasible system solution must be fully distributed andlocalized, scalable, and robust. In some sense, the microscopic behavior of each individual node may not bevery critical, but network nodes must collectively achieve the desired global macroscopic property. In this project, we propose a novel self-organizing protocol and algorithm design approach for suchnetworks, in order to meet the challenges posed by applications as well as the network itself. In a self-organizing design approach, local decision makers self-organize themselves and coordinate among oneanother, in order to collectively achieve the desired global property. We apply our proposed designmethodology in two largely unaddressed problem domains: fair packet scheduling in multihop wirelessnetworks, and robust report forwarding in sensor networks. Toward this end, we present four self-organizing packet-scheduling algorithms and a novel report forwarding protocol that we have developedrecently [22, 24, 35, 36, 46, 47]. The key innovations of this work are: A model-referenced self-organizing algorithm and protocol design approach. A suite of self-organizing packet scheduling algorithms for infrastructureless wireless networks thatprovide QoS performance bounds in terms of fairness, throughput and delay, maximize channel spatialreuse, and arbitrate the conflict between achieving fairness and maximizing channel utilization. A novel self-organizing data forwarding protocol that allows for unconstrained scalability, supportsrobust message delivery along the optimal forwarding band, and ensures efficient power consumptionin the context of sensor networks. The expected research results from this project include a formal investigation of self-organizing designapproach, and a detailed design, analysis, and evaluation of the self-organizing algorithms and protocols forpacket scheduling and report forwarding. The resulting software will be freely available to the researchcommunity. The education plan in this proposal includes offering a new graduate course, reinventing anundergraduate networking course, recruiting more students into undergraduate research programs, andsetting up an undergraduate networking laboratory.

新兴的无基础设施无线网络技术，如 MANET [1]、传感器网络 [31] 和蓝牙 [2]，将寻求支持先进的应用，如智能环境、“零配置”电话会议设置、协作学习、无线访问 Web 服务和紧急救援操作。此类应用程序是关键任务，网络必须解决许多关键问题，才能满足此类应用程序的预期设计要求。在无基础设施的无线网络中，没有底层基础设施，例如蜂窝布局和中央控制单元，例如基站，可用于网络支持。允许大量网络设备以一种自组织方式通过共享无线介质相互通信。此类网络带来的一些独特的设计挑战包括完全分布式和本地化设计、持续的服务质量（QoS）、高效的网络资源利用、不受限制的可扩展性和强大的系统性能。最先进的解决方案不足以解决这些问题并满足应用程序的要求。一个基本问题是，无基础设施的无线网络是一个大规模的分布式系统，可能由大量的无线网络组件（例如传感器网络中的数千甚至数百万）组成，这些组件的功率和计算资源有限，并且容易出现信道错误和故障。因此，任何可行的系统解决方案都必须是完全分布式和本地化的、可扩展的和健壮的。从某种意义上说，每个单独节点的微观行为可能不是很关键，但网络节点必须共同实现所需的全局宏观属性。 在这个项目中，我们为此类网络提出了一种新颖的自组织协议和算法设计方法，以应对应用程序以及网络本身带来的挑战。在自组织设计方法中，当地决策者自我组织并相互协调，以共同实现所需的全球财产。我们将我们提出的设计方法应用于两个很大程度上未解决的问题领域：多跳无线网络中的公平数据包调度，以及传感器网络中的稳健报告转发。为此，我们提出了四种自组织数据包调度算法和我们最近开发的一种新颖的报告转发协议[22,24,35,36,46,47]。这项工作的主要创新点是： 模型参考的自组织算法和协议设计方法。 一套适用于无基础设施无线网络的自组织数据包调度算法，可在公平性、吞吐量和延迟方面提供 QoS 性能界限，最大化信道空间重用，并仲裁实现公平性与最大化信道利用率之间的冲突。 一种新颖的自组织数据转发协议，允许不受限制的可扩展性，支持沿最佳转发频带的鲁棒消息传递，并确保传感器网络环境中的高效功耗。 该项目的预期研究成果包括对自组织设计方法的正式研究，以及对用于数据包调度和报告转发的自组织算法和协议的详细设计、分析和评估。由此产生的软件将免费提供给研究界。该提案中的教育计划包括提供新的研究生课程、重新设计本科网络课程、招募更多学生参加本科研究项目以及建立本科网络实验室。