## 2 Related Work
### Node Activity Scheduling
#### 2.2.2 Solutions Dependent on the Medium Access  
With this second type of solutions, any node is allowed to sleep whenever it is neither transmitting nor receiving. These solutions can be organized in three classes depending on the medium access. * _CSMA/CA_: This medium access provides spatial reuse of the bandwidth, is highly adaptive and has a low overhead in case of light load. All the solutions relying on CSMA/CA are based on the RTS/CTS exchanges preceding unicast transmissions. Any two nodes exchanging RTS/CTS packets need to keep active to start the actual data transmission, whereas their neighbors can enter the sleeping mode to avoid overhearing and idle listening. S-MAC [25] is a famous example. Many other variations of S-MAC have arisen such as T-MAC [26] with an adaptive duration of the active period, D-MAC [27] that reduces network latency, O-MAC [28] that improves the throughput. We can notice that RTS/CTS packets increase the overhead and reduce protocol efficiency. Hence, they are not adequate in case of short messages, the usual case in wireless sensor networks. * _TDMA_: Since the transmissions are scheduled in slots, TDMA ensures that no collision will occur and hence saves energy. It provides a deterministic guarantee for the transmission delays. In order to save energy, bandwidth and delay, the active period during which each node can transmit must be kept as small as possible. Hence, several nodes will transmit in the same slot. To be valid, the 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 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 [30] 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 [29]. 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. TDMA-ASAP [36] is designed for data gathering applications. Based on node coloring, it aims at providing spatial reuse, saving energy and decreasing the end-to-end delays. Moreover, this protocol considers slot stealing to adapt to various traffic conditions. However, it does not support the immediate acknowledgement of unicast transmissions between a parent and its child. * _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 [32] and [33]. A genetic solution is proposed
in [31]. Two examples of deterministic slot assignment per link are given by TRAMA for general communications, FLAMA for tree-based communications like in data gathering applications. TRAMA [34], consists of 1) a neighborhood discovery protocol, 2) a schedule exchange protocol and 3) an adaptive election algorithm that selects the transmitter and 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 [35] is introduced for data gathering applications.