Redefining Routing and Channel Access in Ad Hoc Networks

There has been considerable work on the architecture and protocols of wireless networks since the inception of the ALOHA system and the DARPA packet radio network approximately 40 years ago. However, the design choices that have been made for wireless networks are derivatives of protocols designed for wireline networks and are such that: (a) channel access is either very inefficient and unable to support multimedia traffic across multiple hops, or requires complex clock synchronization to support scheduling schemes based on time division of the channel and dynamic channel reuse; (b) the routes established in wireless networks have no correlation to the transmission schedules used over the wireless links forming those routes, which reduces the efficiency with which flows can be forwarded; and (c) the mechanisms used for information dissemination in wireless ad hoc networks do not scale with the size or dynamics of the network.

In this talk, I argue that the way in which naming, addressing, routing and channel access are done in wireless networks must be redefined from the ground up in order for these networks to scale and perform much more efficiently than they currently do. This redesign must take into account the facts that: (a) nodes do not attach to the network at static points and need not be grouped in stable sets; (b) wireless links do not operate in isolation from one another; (c) establishing transmission schedules and routes are intimately related to one another; (d) SScoding must be eliminated in the signaling of routing protocols; and (e) routing and channel access protocols do not have to use static identifiers that have no relationship to their operation.

I summarize recent results on automatic incremental routing (AIR) and harmonic channel access, which follow the above design guidelines. AIR attains efficient routing in large networks without the use of traditional routing tables or flooding, and supports unicast and multicast routing using the same signaling. Harmonic channel access attains distributed transmission schedules based on circular permutations of identifiers of those entities competing for the shared channel, which need not be node identifiers.