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

Abstract—In this paper, we study distributed channel assign-ment 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 nodes are located in a unit cube uniformly at random and each node is assigned one of 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 re-sults: 1) with just colors, the distance separation achieved by the greedy coloring algorithm asymptotically matches the optimal distance separation that can be achieved by an algo-rithm which is allowed to optimally place the nodes but is allowed to use only one color; and 2) when the greedy coloring algorithm asymptotically achieves the best distance sep-aration that can be achieved by an algorithm which is allowed to both optimally color and place nodes. The greedy coloring algo-rithm is also shown to dramatically outperform a simple random coloring algorithm. Moreover, the results continue to hold under node mobility. Index Terms—Channel assignment, coloring algorithms, peer discovery, spatial point processes, wireless networks. I