## 3 Framework
### Principles of SERENA Coloring Algorithm  
The SERENA coloring algorithm is distributed and localized. Any node \(N\) proceeds as follows:  
1. \(N\) _builds its set_ \(\mathcal{N}(N)\), denoting the set of nodes that cannot have the same color as \(N\). This set is built from the requirements previously expressed. A collision table is built as we will see later, to identify all possible collisions between the frames transmitted in the network. Such collisions should be avoided. In a general application with broadcast and immediate acknowledgement support, SERENA will use a three-hop node coloring. Indeed, from \(Req1\) and \(Req3\), no one 1-hop or 2-hop neighbor can have the same color as \(N\), otherwise a collision would occur between the data frames sent by \(N\) and the other node. From \(Req1\) and \(Req2\), no 3-hop neighbor should have the same color as \(N\), otherwise a collision would occur between an acknowledgement and a data frame as illustrated in Figure 2. Nodes \(N\) and \(Q\) having the same color, transmit simultaneously to \(O\) and \(P\) respectively. The acknowledgement of \(P\) to \(Q\) causes a collision on node \(O\) that fails to receive the data framesent by \(N\). Hence, for a general application, 3-hop coloring is needed: two nodes \(N\) and \(M\) can share the same color if and only if they are neither 1-hop, nor 2-hop, nor 3-hop neighbors. In a data gathering application with broadcast and immediate acknowledgement support, two-hop coloring is required by \(Req3\): no one-hop or two-hop neighbor of \(N\) can have the same color as \(N\). Moreover, \(Req2\) adds the following constraints: nodes \(M\) and \(N\) cannot have the same color, otherwise the conflicts illustrated in Figure 3 would occur. We adopt the following convention: the link between a node and its parent is represented by a vertical plain line, the parent node being represented over its child node. A dotted line represents a one-hop neighbor link that is not a parent link: it is either horizontal or diagonal. A single arrow represents the transmission of a data frame, whereas a double arrow represents the transmission of an acknowledgement. Cases 1 and 2 correspond to a conflict between a unicast transmission by \(N\) and the acknowledgement of another unicast transmission originated from \(M\). Cases 3 and 4 correspond to a conflict caused by the acknowledgement of a unicast transmission and a broadcast transmission, originated from \(M\) in case 3 and from \(N\) in case 4. For data gathering applications, to color itself, \(N\) should know:  
Figure 3: Collision between nodes N and M having the same color with two-hop coloring and immediate acknowledgement in a tree. Figure 2: Collision with two-hop coloring and immediate acknowledgement. * its one-hop and two-hop neighbors;
* the children of the one-hop neighbors of its parent: case 1 of Figure 3;
* the parents of the one-hop neighbors of its children: case 2 of Figure 3;
* the children of the one-hop neighbors of its children: case 3 of Figure 3;
* the parents of the one-hop neighbors of its parent: case 4 of Figure 3.  
Each case allows node \(N\) to add conflicting nodes in its set \(\mathcal{N}(N)\). 2. \(N\)_computes its priority_, denoted \(prio(N)\). To minimize the number of colors needed to color all network nodes, the priority is chosen as the cardinal of: * \(\mathcal{N}(N)\) in case of general communications;
* \(Descendants(N)\) in case of tree communications. This choice tends to alleviate the color constraints imposed to the descendants of the node and thus to reduce the number of colors used. Ties are broken by the smallest node identifier. The priority choice is done according to the simulation results published in [19, 20, 21]. 3. \(N\)_colors itself according to its priority order in \(\mathcal{N}(N)\)_. This leads to the two following rules: * _Rule R1:_ any node \(N\) colors itself if and only if all nodes in \(\mathcal{N}(N)\) having a higher priority than \(N\) are already colored.