  Coloring is used in wireless networks to improve communication efficiency,
mainly in terms of bandwidth, energy and possibly end-to-end delays. In this
paper, we define the h-hop node coloring problem, with h any positive integer,
adapted to two types of applications in wireless networks. We specify both
general mode for general applications and strategic mode for data gathering
applications.We prove that the associated decision problem is NP-complete. We
then focus on grid topologies that constitute regular topologies for large or
dense wireless networks. We consider various transmission ranges and identify a
color pattern that can be reproduced to color the whole grid with the optimal
number of colors. We obtain an optimal periodic coloring of the grid for the
considered transmission range. We then present a 3-hop distributed coloring
algorithm, called SERENA. Through simulation results, we highlight the impact
of node priority assignment on the number of colors obtained for any network
and grids in particular. We then compare these optimal results on grids with
those obtained by SERENA and identify directions to improve SERENA.
