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

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

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.