Local solutions for global problems in wireless networks

In this paper, we review a recently developed class of algorithms that solve global problems in unit distance wireless networks by means of local algorithms. A local algorithm is one in which any node of a network only has information on nodes at distance at most k from itself, for a constant k  . For example, given a unit distance wireless network NN, we want to obtain a planar subnetwork of NN by means of an algorithm in which all nodes can communicate only with their neighbors in NN, perform some operations, and then halt. We review algorithms for obtaining planar subnetworks, approximations to minimum weight spanning trees, Delaunay triangulations, and relative neighbor graphs. Given a unit distance wireless network NN, we present new local algorithms to solve the following problems:1.Calculate small dominating sets (not necessarily connected) of NN.2.Extract a bounded degree planar subgraph HH of NN and obtain a proper edge coloring of HH with at most 12 colors. The second of these algorithms can be used in the channel assignment problem.