Routing, Anycast, and Multicast for Mesh and Sensor Networks

Abstract

This paper studies routing schemes and their distributed construction in limited wireless networks, such as sensor or mesh networks. We argue that the connectivity of such networks is well captured by a constant doubling metric and present a constant stretch multicast algorithm through which any network node <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">u</i> can send messages to an arbitrary receiver set <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> . In other words, we describe a distributed approximation algorithm which is only a constant factor off the NP-hard minimum Steiner tree on <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">u</i> cup <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">U</i> . As a building block for the multicasting, we construct a 1 + epsiv stretch labeled routing scheme with label size O(log ominus) and storage overhead O(1/epsiv) <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</sup> (log ominus)(O( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> ) + log Delta), where ominus is the diameter of the network, Delta the maximum degree of any network node, and <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">alpha</i> a constant representing the doubling dimension of the network. In addition to unicast and multicast, we present a constant approximation for anycasting on the basis of radic(6)-approximate distance queries. We provide a distributed algorithm to construct the required labeling and routing tables.