Coloring spatial point processes with applications to peer discovery in large wireless networks

Jian Ni, R. Srikant, Xinzhou Wu

Research output: Contribution to journalArticle

Abstract

In this paper, we study distributed channel assignment in wireless networks with applications to peer discovery in ad hoc wireless networks. We model channel assignment as a coloring problem for spatial point processes in which n nodes are located in a unit cube uniformly at random and each node is assigned one of K colors, where each color represents a channel. The objective is to maximize the spatial separation between nodes of the same color. In general, it is hard to derive the optimal coloring algorithm, and we therefore consider a natural online greedy coloring algorithm first proposed by Ko and Rubenstein in 2005. We prove two key results: 1) with just log n/log log n colors, the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algorithm which is allowed to optimally place the nodes but is allowed to use only one color; and 2) when K=Ω (log n), the greedy coloring algorithm asymptotically achieves the best distance separation that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algorithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobility.

Original languageEnglish (US)
Article number5640697
Pages (from-to)575-588
Number of pages14
JournalIEEE/ACM Transactions on Networking
Volume19
Issue number2
DOIs
StatePublished - Apr 1 2011

Keywords

  • Channel assignment
  • coloring algorithms
  • peer discovery
  • spatial point processes
  • wireless networks

ASJC Scopus subject areas

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Coloring spatial point processes with applications to peer discovery in large wireless networks'. Together they form a unique fingerprint.

  • Cite this