### 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 language | English (US) |
---|---|

Title of host publication | SIGMETRICS'10 - Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems |

Pages | 167-178 |

Number of pages | 12 |

Edition | 1 SPEC. ISSUE |

DOIs | |

State | Published - Jul 30 2010 |

Event | 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'10 - New York, NY, United States Duration: Jun 14 2010 → Jun 18 2010 |

### Publication series

Name | Performance Evaluation Review |
---|---|

Number | 1 SPEC. ISSUE |

Volume | 38 |

ISSN (Print) | 0163-5999 |

### Other

Other | 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS'10 |
---|---|

Country | United States |

City | New York, NY |

Period | 6/14/10 → 6/18/10 |

### Fingerprint

### Keywords

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

### ASJC Scopus subject areas

- Software
- Hardware and Architecture
- Computer Networks and Communications

### Cite this

*SIGMETRICS'10 - Proceedings of the 2010 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems*(1 SPEC. ISSUE ed., pp. 167-178). (Performance Evaluation Review; Vol. 38, No. 1 SPEC. ISSUE). https://doi.org/10.1145/1811099.1811059