Field Division Routing

Multi-hop communication objectives and constraints impose a set of challenging requirements that create difficult conditions for simultaneous optimization of features such as scalability and performance. We have developed field division routing (FDR), a distributed and non-hierarchical routing protocol that aims to coordinated addressing of scalability, topology alternations, latency, throughput, energy efficiency, and local storage requirements. FDR is based upon two optimization mechanisms: a reactive and focused diffusion that collects only network topology information directly required for making localized routing decisions, and a protocol for sharing routing information among neighboring nodes. Routing table initialization and maintenance are scalable in terms of both storage and overhead traffic. FDR provides guaranteed connectivity while providing near-optimal all-node-pairs message delivery. The protocol is also power-efficient to a wide spectrum of topology changes that induce relatively few messages to update routing tables network-wide. We analyzed FDR both theoretically and using simulation.