## 3 Framework
### Overhead Reduction and Properties of SERENA
#### 3.5.1 Overhead Reduction  
During the coloring algorithm, each node \(N\) periodically broadcasts a \(Color\) message to its 1-hop neighbors. In a naive implementation, this message would include the priority and color of (a) the node \(N\) itself, (b) its 1-hop neighbors in \(\mathcal{N}(N)\), as well as (c) its 2-hop neighbors in \(\mathcal{N}(N)\). Such messages lead to a high overhead, that can be unacceptable in dense networks with a short MAC frame size. That is why we propose in this paper, an optimized \(Color\) message. The content of the \(Color\) message is reduced: it is no longer required to transmit each one-hop and two-hop neighbor with its priority and its color. More precisely, in a general application with broadcast and immediate acknowledgement of unicast communications, any node \(N\) after having built its two-hop neighborhood by means of the \(Hello\) messages sends a \(Neighbor2\) message containing all its two-hop neighbors. Notice that this \(Neighbor2\) message can be fragmented if requested by the MAC layer. New fields are added such as a fragment number and a flag indicating the last fragment. This message is sent once, at the beginning of the coloring in general applications. This message should also be transmitted whenever the one or two-hop neighborhood changes. Hence, any receiving node \(M\) can build its set \(\mathcal{N}(M)\) and determine its priority. The priority of node \(N\) is equal to its number of neighbors up to three-hop. The optimized \(Color\) message sent by node \(N\) to its one-hop neighbors contains:  
* For node \(N\): its address, priority and color. * The address and priority, denoted \(Maxprio1(N)\), of the uncolored one-hop neighbor having the highest priority. Let \(1 hop(N)\) denote the set of one-hop neighbors of \(N\). We have: \(Maxprio1(N)=max_{M\in 1 hop(N)}(Prio(M)\ with\ M\ uncolored)\),
* The bitmap of colors already selected by its one-hop neighbors. * The address and priority, denoted \(Maxprio2\), of the uncolored node \(P\) providing the highest \(Maxprio1(M)\) among all nodes \(M\in 1 hop(N)\). By definition, \(Maxprio2(N)=max_{M\in 1 hop(N)}(Maxprio1(M))\),
* The bitmap of colors already selected by its two-hop neighbors. In a data gathering application with broadcast and immediate acknowledgement of unicast communications, each node first computes its priority. For this, it sends its number of descendants to its parent. This parent computes its priority by summing the number of descendants of each child and sends it to its own parent. In its \(Hello\) message, any node uses two specific flags to indicate its parent and children among its one-hop neighbors. Node \(N\) sends to its one-hop neighbors its \(Color\) message containing:  
* For node \(N\): its address, priority and color. * The address and priority, denoted \(Maxprio1(N)\), of the uncolored one-hop neighbor having the highest priority. We have \(Maxprio1(N)=max_{M\in 1 hop(N)}(Prio(M)\ with\ M\ uncolored)\),
* The bitmap of colors already selected by its one-hop neighbors. * The bitmap of colors already selected by its parent and children. * The address and priority, denoted \(MaxprioSend2(N)\), of the uncolored parent or child of one-hop neighbors having the highest priority. By definition, \(MaxprioSend2(N)=max_{M\in 1 hop(N)}(Maxprio1(M)=Prio(P)\) where \(P\) is a parent or child of \(M\)). This is because only a subset of the three-hop neighbors is needed by the receivers. * The bitmap of colors already selected by the parents or children of one-hop neighbors. Notice that it is sufficient to know that a node is parent or child of one-hop neighbors of the parent or children node. It does not matter to know which exact role it plays among the two. In general applications as well as in data gathering ones, node \(N\) processes the received messages and applies the principles previously given to color itself. This optimization considerably reduces the overhead induced by the coloring algorithm, making possible its use in dense networks with small MAC frame size.