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

Jian Ni, R. Srikant, Xinzhou Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 therefore, we consider a natural greedy coloring algorithm, first proposed in [5]. We prove two key results: (i) with just a small number of colors when K is roughly of the order of log n= log log n, 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 select the locations of the nodes but is allowed to use only one color, and (ii) 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 mobilities.

Original languageEnglish (US)
Title of host publicationSIGMETRICS'10 - Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems
Pages167-178
Number of pages12
Edition1 SPEC. ISSUE
DOIs
StatePublished - 2010
Event2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'10 - New York, NY, United States
Duration: Jun 14 2010Jun 18 2010

Publication series

NamePerformance Evaluation Review
Number1 SPEC. ISSUE
Volume38
ISSN (Print)0163-5999

Other

Other2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'10
Country/TerritoryUnited States
CityNew York, NY
Period6/14/106/18/10

Keywords

  • Channel assignment
  • Coloring algorithms
  • Spatial point processes
  • Wireless networks

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

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