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

Georgia State University Research Foundation, Inc., Atlanta GA

Investigators

Abstract

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.