# Millimetre-Wave Backhaul for 5G Networks: Challenges and Solutions
## 5 Framework Design for 5G Mm-Wave Backhaul
### Scheduling
#### 5.3.2 Algorithm and Solution  
Since the complexity may become prohibitively high when the numbers of new flows and phases are very large, the optimization model of scheduling is time-consuming in dense small cells with explosive data demands. Simple, but effective heuristic algorithms become necessary to solve the problem. As an example, we provide a brief introduction of a scheduling scheme, which borrows the idea from the greedy colouring method given in [25]. The algorithm is conducted in chronological order, _i.e._, we select and allocate the links that could be transmitted together in the first phase and then in the second phase, and so on. We define the unscheduled set as \(\mathcal{U}\), containing all unscheduled hops in every new flow based on the result of transmission path selection. For example, the original requested Flow 2 in Figure 4a is divided into three new flows, and corresponding elements in \(\mathcal{U}\) for these new flows could be depicted as \(\{b_{1},b_{3}\}\), \(\{\{b_{1},b_{2}\},\{b_{2},b_{3}\}\}\) and \(\{\{b_{1},b_{5}\},\{b_{5},b_{3}\}\}\), respectively, with a time length of 7 \(\upmu\)s for each hop. The ultimate goal of the algorithm is to allocate all hops in \(\mathcal{U}\) within the minimum total transmission time. We renumber all new flows from one, and define the visited matrix by \(\mathbf{V}\), with binary element \(v_{i,j}\) representing that the \(j\)-th hop of the \(i\)-th new flow is visited when it is one, and zero otherwise. \(v_{i,j}\) is initialized as zero if the corresponding hop exists, and one otherwise. For example, we assume that the indices of the above three new flows corresponding to the original requested Flow 2 in Figure 4a are 2, 3 and 4, respectively. Since there is only one hop in new Flow 2, \(v_{2,1}\) and \(v_{2,2}\) are initialized as zero and one, respectively.  
In the scheduling of each phase, higher priority is given to the hop that occupies the most transmission time slots. The hops in \(\mathcal{U}\) are rearranged in non-increasing order according to their required transmission time, and we search and select the hop from the beginning element of \(\mathcal{U}\). If the hop is available to be allocated in the current phase, its corresponding element in \(\mathbf{V}\) is set as one. If the hop is not qualified to be transmitted together with hops that have been already allocated in the current phase, e.g., due to the constraints of the numbers of RF chains or the interference limitations, the corresponding elements of this hop and its following hops in the same new flow in \(\mathbf{V}\) are all set as one. This is because if a hop has not been transmitted, the following hops of the same new flow should not be assigned ahead of it. Scheduling for each phase continues until \(\mathbf{V}\) becomes an all-one matrix, which means no available hop is left unvisited. Set \(\mathcal{U}\) is renewed at the end of each phase by removing the allocated hops. Meanwhile, corresponding elements of these allocated hops in \(\mathbf{V}\) are set as one permanently. The algorithm terminates when \(\mathcal{U}\) becomes empty, _i.e._, all requested flows have been scheduled. The scheduling result by this heuristic method for the above example contains two phases; all hops except \(b_{5}\to b_{4}\) are allocated into the first phase, and \(b_{5}\to b_{4}\) is transmitted in the second phase due to the interference restriction. The total transmission time of the heuristic algorithm result turns out to be the same as that in (b4) in Figure 4b, _i.e._, the optimal result for this particular example.