NeTS: Small: Pareto-Optimized Heat Diffusion Protocol on Ollivier-Ricci Curvature Controlled Wireless Networks

NetS：小型：Ollivier-Ricci 曲率控制无线网络上的帕累托优化热扩散协议

• 批准号: 1423624
• 负责人: Edmond Jonckheere
• 金额: $ 50万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423624&HistoricalAwards=false
• 关键词: NeTS; Small; Pareto; Optimized; Heat

While there are a variety of throughput-optimal wireless network protocols, more challenging is the problem of making the protocol optimal relative to such conflicting objectives as queue occupancy (related to latency) and routing cost (related to power management), while holding throughput-optimality. The first step in that direction is the design of a protocol mimicking heat diffusion, as the celebrated Dirichlet principle of heat calculus already endows the routing with minimum routing cost property. The next step requires a significant departure from heat diffusion in order to make the protocol Pareto-optimal relative to routing cost and queue occupancy, while enforcing interference restrictions, link directionality and capacity. From this point onwards, the research effort will be conducted along two different lines of investigation. First, since the classical heat calculus had to be modified in a nontrivial way to make it an implementable wireless network protocol, there is a need to understand the ?heat equation? in the context of directed graphs, subject to interference restrictions and capacity constraints. Classical heat calculus involves the classical Laplacian, which is a linear operator, while here the central mathematical object of concern of this new "heat calculus" is a nonlinear Laplacian in the fluid limit, which describes the rate-level, rather than packet-level, behavior of the stochastic wireless network. The second line of investigation is dedicated to finding the network invariant that could anticipate the potential for large queue occupancy and/or large routing cost. We will develop the Ollivier-Ricci curvature as a computationally implementable network parameter inversely proportional to queue occupancy and routing cost, even under directionality and other network constraints. Also, the Ollivier-Ricci curvature will be investigated as a predictor of the size of the capacity region. Finally, the research will culminate with some Ricci flow technique to optimize the network for maximum Ollivier-Ricci curvature, hence attaining the largest capacity region. The framework of this proposal is applicable to a wide family of stochastic problems with interdependent resources, where the resources are a collection of interdependent servers that can only be accessed under certain constraints, and the consumers are of random service time with asynchronous completion. This general model describes a wide variety of problems including queuing networks, product assembly systems, memory or processor managements, call centers, agent allocations, data switches, healthcare systems, and transmission planning or storage allocation in power systems just to name a few. Specifically, the research will strive to achieve cross-fertilization among this broad set of problems with classical thermodynamics and Ohm?s law in circuit theory that open a new way to analyze and optimize these complicated problems.

虽然存在各种吞吐量最优的无线网络协议，但更具有挑战性的是使协议相对于诸如队列占用（与延迟相关）和路由成本（与功率管理相关）等冲突目标最优，同时保持吞吐量最优的问题。在这个方向上的第一步是模仿热扩散的协议的设计，著名的Dirichlet原理热演算已经赋予路由与最小路由成本属性。下一步需要显着偏离热扩散，以便使协议相对于路由成本和队列占用率达到帕累托最优，同时实施干扰限制、链路方向性和容量。从这一点开始，研究工作将沿着沿着两条不同的调查路线进行。首先，由于经典的热演算必须修改一个非平凡的方式，使其成为一个可实现的无线网络协议，有必要了解？热方程？在有向图的上下文中，受到干扰限制和容量限制。经典的热演算涉及经典的拉普拉斯算子，这是一个线性算子，而在这里，这个新的“热演算”关注的中心数学对象是一个非线性拉普拉斯算子的流体限制，它描述了速率级别，而不是数据包级别，随机无线网络的行为。调查的第二条线是专门寻找网络不变，可以预期的潜在大队列占用和/或大路由成本。我们将开发的奥利维尔-里奇曲率作为一个计算可实现的网络参数成反比的队列占用率和路由成本，即使在方向性和其他网络约束。此外，奥利维尔-里奇曲率将作为预测的容量区域的大小进行研究。最后，研究将达到高潮，一些里奇流技术优化网络最大的奥利维尔里奇曲率，从而获得最大的容量区域。 这个建议的框架是适用于一个广泛的家庭的随机问题与相互依赖的资源，资源是一个集合的相互依赖的服务器，只能在一定的约束条件下访问，和消费者的随机服务时间与异步完成。这个通用模型描述了各种各样的问题，包括排队网络，产品装配系统，存储器或处理器管理，呼叫中心，代理分配，数据交换，医疗保健系统，以及电力系统中的传输规划或存储分配，仅举几例。 具体而言，研究将努力实现这一广泛的问题与经典热力学和欧姆？为分析和优化这些复杂问题开辟了一条新的途径。