Regionalizing global optimization algorithms to improve the operation of large ad hoc networks

When optimizing the operations of large wireless ad hoc networks, neither global nor local information-based approaches fits well: they require either information about the entire network structure, which is in most cases impossible to get, or are not capable of optimizing beyond a very narrow horizon. We propose a novel optimization scheme based on regional information to compute the network-wide optimizations, taking the peculiarities of large ad hoc networks into account, and obtain an "emergent algorithm" out of a global optimization algorithm. Our solution uses a clustering algorithm to define regions but needs neither cluster maintenance nor inter-cluster communication protocols, thus is expected to be very robust. The problem of distributed frequency assignment is used as a case study to demonstrate the performance of our method as compared to algorithms based on local- or global information.