In many emerging wireless networks (such as ad hoc networks, 
cognitive radios, etc.), no central frequency allocation authority 
is naturally available. This makes Distributed frequency allocation 
an important but mostly unchartered territory in wireless networking.

We will first discuss existing proposed solutions to this problem,
including methods based on graph colouring, iterative waterfilling, 
etc. These approaches either excessively simplify the interference 
models, or are not fully decentralized, or require too much information 
exchange between autonomous nodes/clusters, or suffer from all these 
shortcomings.  Additionally, they are all too complex to implement.

Subsequently, we disclose a simple, fully distributed, dynamic freqeuncy
allocation algorithm that requires neither any information exchange
between autonomous devices, nor even any knowledge of the existence of
other autonomous entities. Additionally, the proposed algorithm can be 
use in conjunction with any realistic wireless radio channel model such 
as those commonly employed in wireless standards.

We prove convergence of this algorithm to a sub-optimal solution, and
develop performance bounds showing that this sub-optimal solution is
near-optimal under various practical node activity models.

This is a joint work with Behtash Babadi.

[slides]