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

许多新兴的关键应用，例如用于目标监视和跟踪、数据收集、查询和集成的应用，将越来越多地基于包括异构传感器和手持设备的联网计算平台。这些将依赖于分布式算法，这些算法可以产生准确的，功率和时间效率的解决方案，为美国提供在被关注（博洛）和对手的重力中心相关信息竞技场的技术优势。 然而，这些应用程序中有许多潜在的棘手的NP-难优化问题，实际上限制了他们的近似解决方案。 不利的结果是低于标准的最先进的算法，采用自组织贪婪算法远离问题结构，因此提出了上述应用程序的严重漏洞。 这就要求从根本上探索这些NP难优化问题，从而在这个竞技场中，从理论上和实践上找到明显上级的分布式算法。在过去的几年里，PI一直在研究传感器目标覆盖问题，以最大限度地提高网络的生命周期从第一原则。相反，逐步提高贪婪的算法，已经被各种团体的常规做法，PI已经成功地攻击的问题，通过利用实际上易于处理的局部解决方案空间的可能性，从每个传感器的角度来看，正面。 这种新的方法导致了（i）基本的见解的问题结构和它的解决方案空间;（ii）一个通用的算法框架的分布式算法的相关类的覆盖问题，其特征在于其中的局部子解决方案共同产生可行的全局解决方案;和（iii）一组分布式算法移动的最先进的网络寿命的上限以下25%。 所提出的算法框架以及整体的方法，预计适用于其他无关的NP-难优化问题的网络。这个创新的探索性项目首先提出研究所提出的算法框架是否对非目标覆盖相关问题有效，例如蜂窝网络中的信道分配、顶点覆盖和三角形填充。 接下来，PI建议探索整体方法是否可以应用于其他基本但关键的问题，如目标跟踪，数据聚合，和信道化的ad-hoc移动的网络的实时流量。 虽然前者有一些路线图，但后者知之甚少。 缺乏确定的交易工具，以及项目的早期、未经测试、探索性、高风险高回报的性质，是EAGER提议的主要原因。

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.