Accession Number:

ADA439537

Title:

Rate of Degradation of Centralized Optimization Solutions and Its Application to High Performance Domain Formation in Ad Hoc Networks

Descriptive Note:

Technical research rept.

Corporate Author:

MARYLAND UNIV COLLEGE PARK DEPT OF ELECTRICAL AND COMPUTER ENGINEERING

Report Date:

2004-01-01

Pagination or Media Count:

9.0

Abstract:

Future military systems such a FCS require a robust and flexible network that supports thousands of ad hoc nodes therefore, we must ensure the scalability of networking protocols e.g., routing, security and QoS. The use of hierarchy is a powerful solution to the scaling problem, since it allows networking protocols to operate on a limited number of nodes, as opposed to the entire network. We have proposed an automated solution to dynamically create and maintain such hierarchy based on a combination of global optimization algorithms 1 and local distributed maintenance protocols 2. Global optimization clearly improves performance in a static network but, it is unclear how effective it is in a dynamic ad hoc environment. As network and node characteristics change, the optimization algorithm may use incomplete, stale, or even inaccurate metrics. In this paper, were analyze how the hierarchy created deteriorates from the optimal as network conditions change. We show that the fragility of the optimization depends on the particular cost function and the number of metrics that change. More important, we show, for the first time, that global optimization can remain effective for long periods with good cost functions, even in large dynamic ad hoc networks where metrics may change rapidly due to node mobility and links making and breaking. This result shows that, with fast optimization algorithms such as modified Simulated Annealing 1, future military systems can use global optimization to autoconfigure domains to significantly improve performance. We also show that local maintenance protocols support the global optimization mechanisms by extending the time the hierarchy remains feasible.

Subject Categories:

  • Computer Systems
  • Computer Programming and Software
  • Command, Control and Communications Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE