Scalable routing for networked sensors and actuators
Thomas T. Fuhrmann · 2005
Abstract — The design of efficient routing protocols for ad hoc and sensor networks is challenging for several reasons: Physical network topology is random. Nodes have limited computation and memory capabilities. Energy and bisection bandwidth are scarce. Furthermore, in most settings, the lack of centralized components leaves all network control tasks to the nodes acting as decentralized peers. In this paper, we present a novel routing algorithm, scalable source routing (SSR), which is capable of memory and message efficient routing in large random networks. A guiding example is a community of ’digital homes ’ where smart sensors and actuators are installed by laypersons. Such networks combine wireless ad-hoc and infrastructure networks, and lack a well-crafted network topology. Typically, the nodes do not have sufficient processing and memory resources to perform sophisticated routing algorithms. Flooding on the other hand is too bandwidthconsuming in the envisaged large-scale networks. SSR is a fully self-organizing routing protocol for such scenarios. It creates a virtual ring that links all nodes via predecessor/successor source routes. Additionally, each node possesses O(log N) short-cut source routes to nodes in exponentially increasing virtual ring distance. Like with the Chord overlay network, this ensures full connectivity within the network. Moreover, it provides a routing semantic which can efficiently support indirection schemes like i3. Memory and message efficiency are achieved by the introduction of a route cache together with a set of path manipulation rules that allow to produce near-to-optimal paths.