EAGER: Exploratory Frameworks for Distributed Algorithms for Optimization Problems on Networks of Heterogeneous Sensors

许多新兴的关键应用程序，例如用于目标监测和跟踪、数据收集、查询和集成的应用程序，将越来越多地基于由不同种类的传感器和手持设备组成的联网计算平台。这将依赖于分布式算法，这些算法可以产生准确、省电、省时的解决方案，为美国在监视(BOLO)和对手的重心相关信息领域提供压倒性的技术优势。然而，这些应用中的许多都具有潜在的难以处理的NP-Hard优化问题，实际上将它们限制在近似解的范围内。不利的结果是，使用远离问题结构的自组织贪婪启发式算法的算法不是最先进的，因此对于上述应用程序呈现出严重的漏洞。这就需要对这些NP-Hard优化问题进行根本性的探索，从而在理论上和实践上都能在这一领域产生明显优越的分布式算法。在过去的几年里，PI一直在研究传感器目标覆盖问题，从第一原理出发最大化网络寿命。与各个小组的常规做法不同的是，PI成功地正面解决了问题，因为从每个传感器的角度来看，PI利用了几乎可处理的局部解空间的可能性。这种新的方法已经产生了(I)对问题结构及其解空间的基本见解；(Ii)用于相关类型的覆盖问题的分布式算法的通用算法框架，其特征是局部子解共同产生可行的全局解；以及(Iii)一组分布式算法将最新技术的水平移动到网络生命周期上限以下的25%。所提出的算法框架和总体方法有望适用于其他无关的网络上的NP-Hard优化问题。这一创新的探索性项目首先提出了研究所提出的算法框架是否能够有效地解决与目标覆盖无关的问题，例如蜂窝网络中的信道分配、顶点覆盖和三角形填充。接下来，PI建议探索整体方法是否可以应用于其他基本但关键的问题，如目标跟踪、数据聚合和用于实时流量的自组织移动网络的信道化。虽然前者有一些路线图，但对后者知之甚少。缺乏行业的权威工具，以及该项目的早期、未经测试、探索性、高风险和高回报的性质，是这一急切提议的主要原因。

Many emerging critical applications such as those for target monitoring and tracking, data gathering, querying and integration would increasingly be based on networked computing platforms comprising heterogeneous sensor and hand held devices. These will be dependent on distributed algorithms which can yield accurate, power- and time-efficient solutions, providing the United States commanding technical superiority in be-on-the-look-out-for (BOLO) and opponent's center of gravity-related information arena. However, many of these applications have underlying intractable NP-hard optimization problems, practically restricting them to approximate solutions. The adverse result has been sub-par state-of-art with algorithms employing ad-hoc greedy heuristics far removed from problem structures, and therefore presenting critical vulnerability for aforementioned applications. This calls for a fundamental exploration of these NP-hard optimization problems leading to distinctly superior class of distributed algorithms in this arena, both theoretically and practically. For past several years, the PI has been studying the sensor target coverage problem to maximize network lifetime from the first principles. As opposed to incrementally improving the greedy heuristics as has been routine practice by various groups, the PI has succeeded in attacking the problem head-on by exploiting the possibility of practically tractable local solution space as seen from the perspective of each sensor. This novel approach has resulted in (i) fundamental insights into the problem structure and its solution space; (ii) a general algorithmic framework for distributed algorithms for related class of coverage problems characterized by those wherein local sub-solutions collectively yield feasible global solution; and (iii) a set of distributed algorithms moving the state-of-art to 25% below an upper-bound on network lifetime. The proposed algorithmic framework as well as the overall approach are expected be applicable to other unrelated NP-hard optimization problems over networks. This innovative exploratory project first proposes to investigate whether the proposed algorithmic framework can be effective for non-target-coverage related problems such as channel assignment in cellular networks, vertex cover, and triangle packing. Next, the PI proposes to explore whether the overall approach can be applied to other fundamental yet critical problems such as for target tracking, data aggregation, and channelization of ad-hoc mobile networks for real-time traffic. While there is some road map for the former, very little is known for the latter. This lack of definitive tools of the trade and early, untested, exploratory, high-risk high-reward nature of the project are the primary reasons for this EAGER proposal.