## 4 WirelessHART Scheduling Schemes
### Conflict-Aware Least Laxity First Algorithm  
The work in [81] presents a proof for the NP-hardness of the scheduling problem in WirelessHART technology, and two scheduling algorithms to solve this problem. The first is an optimal branch and bound-based scheduling algorithm, that uses a search tree, so as to guarantee that a schedule will be found whenever a feasible one exists. The algorithm metric is the laxity of a packet, which consists of the remaining time slots minus its remaining number of transmissions in the transmission route.  
Although the algorithm is optimal, the execution time needed limits the application of the algorithm in a WirelessHART network due to the dynamic nature of such an environment. In order to attend to this requirement, the authors proposed a second algorithm based on the idea that the algorithm must be cognizant of conflicts between transmissions, the conflict-aware least laxity first (C-LLF) heuristic algorithm based on the least laxity first, which has been used successfully on wired networks. The conflict-aware laxity metric consist of considering the length of the time windows in which the transmissions can be scheduled and the potential concurrent transmission windows that would cause conflicts.  
The windows are determined by the values of the release time (\(r\)) of a transmission \(\tau_{k}\), which is the first slot in the superframe in which the transmission can be scheduled, and the deadline (\(d\)) of that packet to reach its destination. The release time and the deadline are respectively affected by the number of hops to the transmission link (\(pre_{k}\)) and the number of hops left from the link to the destination (\(post_{k}\)). For example: if a transmission \(\tau_{k}\) is three hops away from the destination, the deadline for this transmission to happen is the deadline of the packet to be delivered minus three slots.  
The scheduling algorithm starts from a pool of all transmissions \(\Gamma\) to be scheduled and begins allocating from the first slot time to the last (the variable \(s\) goes from zero to the size of the superframe). The algorithm runs until it schedules all transmissions (\(\tau_{k}\)) by selecting a group (Released(s)) of transmissions that have a release time equal to \(s\) (the current slot time being allocated). From this group Released(s), the algorithm gives priority to those transmissions with the closest deadline and the bigger number of conflicts in their lifetimes. When a transmission is scheduled, all conflicting transmissions are removed from the Released(s) group to be scheduled in another slot. The algorithm tries to allocate all transmissions from Released(s) in the available channels of the slot time before proceeding to the next slot. The algorithm ends in success if it manages to schedule all transmissions from \(\Gamma\), but ends in failure if a transmission misses a deadline and is unschedulable.  
To validate the algorithm, the paper describes both simulation and testbeds comparing the proposal to a set of baseline real-time scheduling policies. The three metrics used were:  
* Schedulable ratio: the percentage of test cases for which an algorithm is able to find a feasible schedule.
* Buffer size maximum of packets buffered at a node when transmissions are scheduled.
* Execution time: average execution time to generate the schedule for the packets generated in a superframe.  
The proposal outperforms the other policies in most parts of the tests, except for the execution time, which grew more than the others with an increasing number of nodes in the network. Nevertheless, the calculation time obtained was around 2.5 s, which is a reasonable computation time for a WirelessHART network. For more detailed results, see [81].