## 3 Framework
### Overhead Reduction and Properties of SERENA
#### 3.5.2 Properties  
More generally, we can now give the properties met by SERENA algorithm. _Property P1: With assumptions A0, A1 and A2, \(\forall\) node \(N\) if \(\exists\) node \(M\in\mathcal{N}(N)\) then \(N\in\mathcal{N}(M)\)._  
_Proof:_ This property is deduced from assumptions \(A0\), \(A1\) and \(A2\). _Property P2: In an ideal environment, the only types of collision that can occur in a general application with broadcast and immediate acknowledgement are between one-hop, two-hop or three-hop neighbors._  
_Proof:_ In a general application with broadcast and immediate acknowledgement, the only collisions that can occur are caused by a unicast data frame, a broadcast data frame or an acknowledgement frame. Table 1 summarizes all possible cases. In case of a collision involving a unicast or broadcast data frame, the color of the data frame sender is conflicting, whereas in the case of a collision involving an acknowledgement frame, the destination of the acknowledgement has a conflicting color. That is why this table is symmetric and lines corresponding to unicast and broadcast data are identical. As a consequence, all possible collisions are taken into account by three-hop coloring. \(\blacksquare\)  
_Property P3: SERENA three-hop coloring provides a valid coloring for general applications, assuming an ideal environment._  
_Proof:_ For three-hop coloring, the set \(\mathcal{N}(N)\) contains by construction all nodes up to 3-hop from \(N\), assuming an ideal environment. SERENA ensures by construction that no node in \(\mathcal{N}(N)\) will color simultaneously with \(N\). Moreover, when \(N\) colors itself, it knows all the colors taken by nodes in \(\mathcal{N}(N)\) with a higher priority. Hence, it takes a color that is not already used in \(\mathcal{N}(N)\). Furthermore, assuming an ideal environment, nodes that do not belong to \(\mathcal{N}(N)\) cannot create a collision with data sent by \(N\) or acknowledgement sent to \(N\), as shown by Property P2. Hence, SERENA does not create collision. \(\blacksquare\)  
_Property P4: In an ideal environment, the only types of collision that can occur in a data gathering application with broadcast and immediate acknowledgement are between one-hop, two-hop nodes or correspond to cases 1 to 4 in Figure 2._  
_Proof:_ In a data gathering application with broadcast and immediate acknowledgement, the only collisions that can occur are caused by a unicast data frame sent to its parent or child, a broadcast data frame sent to its neighbors or an acknowledgement frame sent to its parent or child. Table 2 summarizes all possible cases. This table is symmetric. In case of tree communications where all unicast data transmissions of a cycle are either upstream or downstream, unicast and broadcast data frames do not cause the same collisions, unlike in the general communications case (see for instance the acknowledgement column). As a consequence, all possible collisions are taken into account by tree coloring. \(\blacksquare\) \begin{table}
\begin{tabular}{c c c c} \hline  & Unicast Data & Acknowledgement & Broadcast Data \\ \hline Unicast Data & 1 or 2-hop nodes & 1 or 3-hop nodes & 1 or 2-hop nodes \\ Acknowledgement & 1 or 3 hop nodes & 2-hop nodes & 1 or 3-hop nodes \\ Broadcast Data & 1 or 2-hop nodes & 1 or 3-hop nodes & 1 or 2-hop nodes \\ \hline \end{tabular}
\end{table} 
Table 1: Possible collisions in case of general application, broadcast and immediate acknowledgement. \begin{table}
\begin{tabular}{c c c c} \hline  & Unicast Data & Acknowledgement & Broadcast Data \\ \hline Unicast Data & same parent & cases 1 to 4 & 1 or 2-hop nodes \\ Acknowledgement & cases 1 to 4 & a child of a 1-hop node of the other & 2-hop node of parent or child \\ Broadcast Data & same parent & 2-hop node of parent or child & 1 or 2-hop nodes \\ \hline \end{tabular}
\end{table} 
Table 2: Possible collisions in case of data gathering application, broadcast and immediate acknowledgement.