Routing in Wireless Networks and Local Solutions for Global Problems

  • Jorge Urrutia
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3738)


Let P n be a set of points. The unit distance graph of P n is the graph with vertex set P n , in which two points are connected if their distance is at most one. Unit distance graphs of point sets can be used to model wireless networks in which the elements of P n represent the location the broadcast stations of our wireless networks. The stations are assumed to broadcast with the same power.

In recent years, it has been proved that many global problems for this type of networks can be solved by means of local algorithms, that is algorithms in which a node needs to communicate only with its neighbours. The first example of this, was the extraction of a planar connected subgraph of a unit distance wireless network, which was then used for a local type routing algorithm. In this talk we will survey several results in this area of research, and present recent results related to approximations of minimum weight spanning trees, snapshots of networks, etc.


Wireless Network Research Community Software Engineer Local Type Local Solution 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Jorge Urrutia
    • 1
  1. 1.Instituto de MatematicasUniversidad Nac. Aut. de MexicoMexico

Personalised recommendations