## 4 Node Activity Scheduling
### Cross Layering Optimization
#### 4.4.3 End-to-end Delays and Reliability  
Let us now evaluate the end-to-end delays in a data gathering application, assuming a MAC cycle given in Figure 12. Figure 15 depicts the network delays, assuming a slot duration of 128 ms. The network delay represents the time elapsed from the time where the farthest node from the sink starts to transmit to the time where this message is received by the sink. We then have: \(network\ delay=number\ of\ colors\cdot slot\ duration\). For the evaluation illustrated in Figure 15, each node has 30 bytes to transmit. Packet size is 128 bytes. For configurations with 200 nodes, we assume that any node other than the sink has at most 100 descendants in the tree. Assuming a slot duration of 128 ms, we get an active period of 5.376 s for 200 nodes and 42 colors with SERENA + immediate acknowledgement + broadcast. Notice that the slot duration can be adapted to the maximum number of descendants of the children of the sink. For 100 nodes and assuming a slot duration of 64 ms and any node other than the sink having at most 50  
Figure 14: Average number of messages sent per node in a tree. descendants in the tree, a slot duration of 64 ms, we get an active period of 2.176 s and 34 colors with SERENA + immediate acknowledgement + broadcast. We observe that the network delay curves are very similar to the number of colors curves. This is expected because of the formula giving the network delay from the number of colors. We can also compute the maximum end-to-end delays, considering that the farthest node from the sink wants to transmit just at the end of its color slot. It must then wait until the next cycle. Hence, the maximum end-to-end delay is equal to the network delay increased by the cycle duration. Notice that without tree coloring, a message from the farthest node can take a number of cycles equal to 1+ its distance in hop number to the sink. Hence, tree coloring brings a huge benefit with regard to end-to-end delays. If now we focus on reliability, we observe that the inherent versatility of the wireless environment makes the transmissions unreliable: message losses are possible. To cope with them, two solutions are possible. Either sampling at a frequency higher than required in order to tolerate message losses. Or detecting losses by using acknowledgements: immediate or delayed. As already said, immediate acknowledgements are easier to implement in the MAC layer and lead to shorter transmission delays. That is why they are frequently used. If we use TDMA-ASAP that has not been designed to support this immediate acknowledgement, potential color conflicts can occur. They correspond to situations where two nodes having the same color transmit simultaneously, causing a collision between a data frame and an acknowledgement frame and making impossible for the destination to receive its intended frame. Such conflicts cannot be avoided by the capture effect. The number of such situations depend on the tree and the network topology. To illustrate our purpose, we take a very simple example with 9 nodes. The topology is depicted in Figure 16, where circled letters denote nodes. A plain line denotes a link in the tree whereas a dotted line denotes a neighbor link unused in the tree. The number besides the circled letter denotes the color granted to this node. We apply two tree colorings to this topology: TDMA-ASAP and SERENA with immediate acknowledgement. Figure 16(a) shows that with TDMA-ASAP, 6 colors  
Figure 15: Network delays in a tree. are needed. All the leaves have the same color. Notice also that this coloring does not support broadcast: nodes H and I broadcast simultaneously, each of them will be unable to receive the message of the other. With SERENA, as shown in Figure 16, 7 colors are needed, broadcast being required or not. This additional color is needed to avoid any color conflict due to the immediate acknowledgement. With TDMA-ASAP coloring, we count two potential color conflicts.