TSBS: A Two-Stage Backpressure Scheduling scheme over multihop wireless networks

The backpressure algorithm has been considered a promising routing and scheduling scheme in multihop wireless networks. However, path detours or loop problems and the last packet problem have always troubled the performance improvement of the backpressure algorithm. Existing backpressure algorithms cannot simultaneously prevent both path detours or loop and the last packet problems and thus fail to improve network performance further. To this end, this paper proposes a Two-Stage Backpressure Scheduling (TSBS) scheme that presents a new link weight design and develops a two-stage execution algorithm to resolve the above two problems. In the first stage, we use the shortest path and queue backlog metrics to build link weight to prevent path detours or loop problems and obtain the scheduling link set with the maximum queue backlog. In the second stage, considering the delay differential of the Head-of-Line (HOL) packets in link weight design, an optimal scheduling link is selected from the scheduling link set to inhibit the last packet problem. By Lyapunov drift theory, our analysis proves that TSBS achieves network stability and optimal throughput within the network's capacity region. Simulation results show that TSBS improves average end-to-end delay by up to 26.78%, the percentage of packet forwarding by up to 18.92%, average queue length by up to 27.91%, and network throughput by up to 283.86%, compared with the baseline D-BP algorithm, respectively.