The immediate objective of this work is to organize the communications between many mobile nodes that must exchange urgent messages, voice, video, and data. Addressing this objective requires new scalable adaptive QoS routing algorithms with protection switching.
Our strategy is a hierarchical link state approach. The nodes organize themselves into clusters based on their connectivity. They then select radio channels to maximize the cluster capacity. The clusters implement an intra-cluster link state algorithm and an inter-cluster link state algorithm.
The dynamic clustering algorithm is a random search designed to discover quickly a good clustering. Roughly, a good clustering is one whose boundaries do not cut too many links. The intuition is that by creating clusters, one forces the communications to go through gateways instead of directly between arbitrary nodes of distinct clusters. This structure reduces the capacity of the network if the cluster boundaries cut many links.
Our radios can operate on different channels and the network selects the channels to increase the capacity of the network. The idea is for nodes to select channels based on the traffic patterns. We use a distributed simulated annealing algorithms were the nodes attempt to reduce a "potential function" that measure the degree of channel sharing.
The routing algorithms are also novel because of structure of the capacity constraints. These constraints are very different from those in a wired network. For instance, if a node relays a packet on a radio channel, then the rate of these packets is counted twice in the capacity constraint. Accordingly, the constraint that a channel imposes depends on the subsequent route of the traffic. This new structure necessitates new algorithms.
We have presented a few versions of these algorithms at Darpa meetings. The web site discusses the results. This work is done in collaboration with Pravin Varaiya, Antonios Dimakis, Linhai He, Bill Hodge, John Musacchio, Teresa Tung, and Wilson So. See also the paper presented at MWCN 2003.