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

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

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.