S4: Small State and Small Stretch Routing Protocol
Routing protocols for wireless sensor networks must address the
challenges of reliable packet delivery at increasingly large scale and
highly constrained node resources. Attempts to limit node state can
result in undesirable worst-case routing performance, as measured by
stretch, which is the ratio of the hop count of the selected path to that of
the optimal path.
We develop a new routing protocol, Small State and Small Stretch
(S4), which jointly minimizes the state and stretch. S4 uses a
combination of beacon distance-vector based global routing state and
scoped distance-vector based local routing state to achieve a
worst-case stretch of 3 using $O(\sqrt{N})$ routing state per node in
an N-node network. Its average routing stretch is close to 1. S4
further incorporates local failure recovery to achieve resilience to
dynamic topology changes. We use multiple
simulation environments to assess performance claims at scale, and use
experiments in a 42-node wireless sensor network testbed to evaluate
performance under realistic RF and failure dynamics. The results show
that S4 achieves scalability, efficiency, and resilience in a wide range of
scenarios.
Papers
Source code