## 2 Related Work
### Node Activity Scheduling
#### 2.2.2 Solutions Dependent on the Medium Access
FLAMA is simplified both in terms of message exchange and processing complexity. * _Hybrid_: Z-MAC [37] is based on DRAND [38] which assigns slots to nodes in such a way that any node has a slot different from those assigned to its one-hop and two-hop neighbors. The goal of Z-MAC is to optimize the bandwidth utilization the MAC protocol, selecting CSMA/CA under low contention and TDMA under heavy contention. We can notice that Z-MAC does not allow an immediate acknowledgement of unicast messages, while this acknowledgement is important in wireless communication to confirm the correct reception of the packet. From the energy point of view, Z-MAC reduces the activity period in the polling cycle enforced by the application. It does not allow nodes to sleep during the activity period, unlike SERENA (see Section 4) that aims at maximizing network lifetime by scheduling node activity. The advantage of Z-MAC is that it does not depend on the number of network nodes but on the cost of an asymptotic convergence. More generally, slot assignment can be based on a coloring algorithm, as in Z-MAC and TDMA-ASAP. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels, traditionally called colors, to elements of a graph subject to certain constraints. Before presenting the two categories of graph coloring (edge or vertex coloring), we define the criteria used to evaluate a distributed coloring algorithm, [45, 46]:  
* the number of colors needed to color a graph \(G\): closer this number to the chromatic number of \(G\), more efficient the algorithm. * its time complexity, expressed in the case of a distributed algorithm, by the maximum number of rounds needed to color each node and the total number of messages exchanged to color \(G\). The concept of round, used to evaluate the time complexity of a graph coloring algorithm, can be defined as follows. In a round, any node can:  
* send a message to all its one-hop neighbors,
* receive the messages sent by them,
* perform some local computation based on the information contained in the received messages. The two classes of graph coloring are vertex coloring and edge coloring. _Vertex coloring_ has received a lot of attention from researchers. One-hop vertex coloring consists in coloring each vertex of the graph such that two adjacent vertices have not the same color and the number of colors used is minimum. This problem has been shown NP-complete in [39] for the general case, whereas graphs with maximum vertex degree less than four, and bipartite graphs can be colored in polynomial time. The first researches on one-hop graph coloring proposed centralized algorithms (see [40, 41]). In [40], Dsatur, a greedy algorithm (_i.e._, no color backtracking), colors first the vertex with the highest number of already colored neighbor vertices. This algorithm exhibits very good performances, even if it is not optimal. It is then followed by Largest First, where the node with the highest degree is colored first. Distributed one-hop graph coloring algorithms also exist. Some of them resort to randomization to select the color as for instance [42, 43, 44]. The color selected by a node can be used only if it does not conflict with the colors chosen by its neighbors. Let \(n\) be the number of vertices and \(\Delta\) the largest vertex degree. For one-hop graph coloring, the algorithm proposed in [45] runs in _O_(_log n_) rounds, and uses a number of colors close to \(\Delta\), whereas Distributed Largest First runs in \(O(\Delta^{2}\ log\ n)\) rounds [46]. _Edge coloring_ is an assignment of colors to the edges of the graph such that edges incident on the same vertex receive different colors. Note that an edge coloring of a graph is just a vertex coloring of its link graph. Many solutions focus on this type of graph coloring to apply it to the wireless networks. These solutions are named link scheduling algorithm. The idea is to assign to each link between two neighbors a color (which corresponds to a time slot) in which these two neighbors can communicate.