## 2 State of the Art
### TDMA-based Protocols  
In wireless networks, it has been shown in [9] that scheduling packet transmissions taking into account the conflict graph modeling the interferences optimizes the network throughput. However, this omniscient scheduling is unrealistic. In radio networks where medium access is scheduled by TDMA, energy is saved because of the absence of collisions and a deterministic access is guaranteed. However, in order to maximize the efficiency of the MAC protocol, to save energy, bandwidth and delay, the active period during which each node can transmit must be kept small to improve application reactivity. Hence, the schedule should allow several nodes to transmit in the same slot. However, to be valid, this schedule must ensure that all nodes allowed to transmit in the same slot do so without interfering. We can distinguish two types of slot assignment:  
* _slots are assigned per link_. In this case, only the transmitter and the receiver, the two extremities of the link are awake, all other nodes are sleeping. However, if the traffic on this link is light, the slot is not used at 100%. Broadcast transmissions are expensive: they require to copy the same information \(n\) times where \(n\) is the number of neighbors. Such solutions are also called link scheduling in [10, 11]. A genetic solution is proposed in [12]. Two examples of deterministic slot assignment per link are given by TRAMA for general communications and FLAMA for tree-based communications like in data gathering applications. TRAMA [13], consists of 1) a neighborhood discovery protocol, 2) a schedule exchange protocol and 3) an adaptive election algorithm that selects the transmitter and the receiver(s) for each time slot. The node having the highest priority among its one-hop and two-hop neighbors wins the right to transmit in the considered slot. Each node declares in advance the list of its slots and for each slot its receiver(s). TRAMA is adaptive but also complex. To mitigate this complexity, a solution named FLAMA [14] is introduced for data gathering applications. FLAMA is simplified both in terms of message exchange and processing complexity. * _slots are assigned per node_. In such a case, the transmitting node can use its slots as it wants: it can broadcast, send a unicast transmission to one of its neighbors then to another one. The advantage is that it can optimize the utilization of its slot. The drawback is that any neighbor of the transmitter must be awake during this slot, because it can be the destination of a message. Such solutions are also called broadcast scheduling as in [15] for instance. [PERSON] _et al_. have defined the problem called channel assignment in radio networks and have established complexity results for different types of network configurations [16]. They propose a 2-approximation algorithm for the minimum two-hop coloring on bounded degree planar graphs. With two-hop coloring, two nodes that are one-hop or two-hop neighbors must not have the same color. More generally, medium access scheduling can also be done according to graph coloring in order to improve bandwidth and energy efficiency. In graph theory, graph coloring is a special case of graph labeling. It is an assignment of colors to either edges or vertices of the graph subject to certain constraints. Edge coloring [17] is an assignment of colors to the graph edges, such that two edges incident on the same vertex receive different colors. Whereas vertex coloring [19, 20] is an assignment of colors to nodes such that two adjacent vertices have not the same color. In both cases, the number of colors used to color the graph should be minimized. Both use one-hop coloring. Extensions have been brought to two-hop or three-hop coloring. Vertex or node coloring enables broadcast communications, unlike edge coloring. Broadcast is needed to discover the neighborhood of a node and to advertise topology information to name a few. That is why we choose vertex coloring in SERENA. The one-hop node coloring problem has been proved NP-complete in [18].