Distributed Algorithms for Voronoi Diagrams and Applications in Ad-hoc Networks

Hadjicostis, Christoforos N.; Cao, Min

Permalink

https://hdl.handle.net/2142/99588 Copy

Description

Title

Distributed Algorithms for Voronoi Diagrams and Applications in Ad-hoc Networks

Author(s)

• Hadjicostis, Christoforos N.
• Cao, Min

Issue Date

2003-10

Keyword(s)

• Voronoi diagram
• Distributed algorithms
• Ad-hoc networks
• Ad hoc networks
• Topology control

Abstract

The Voronoi diagram is a fundamental structure in computational geometry and arises naturally in many applications including wireless networking. In this paper, we propose a distributed algorithm by which each node u can compute its Voronoi region in O(d(u)) time, where d(u) is the number of the Voronoi neighbors of node u. Then we show how the algorithm can be applied in topology control of wireless ad-hoc networks, and also propose a revised version of the algorithm to minimize transmission energy consumption. Further applications of the algorithm in different areas are expected.

Publisher

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

Series/Report Name or Number

Coordinated Science Laboratory Report no. UILU-ENG-03-2222, DC-210

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/99588

Sponsor(s)/Grant Number(s)

National Science Foundation

Owning Collections