Minimum-Length Scheduling With Rate Control in Wireless Networks: A Shortest Path Approach
In this paper, the minimum-length scheduling problem in wireless networks is studied, where each source of traffic has a finite amount of data to deliver to its corresponding destination. The authors' objective is to obtain a joint scheduling and rate control policy to minimize the total time required to deliver this finite amount of data from all sources. First, networks with time-invariant channels are considered. An optimal solution is provided by formulating the minimum-length scheduling problem as finding a shortest path on a single-source directed acyclic graph. However, finding the shortest paths is computationally hard since the number of vertices and edges of the graph increases exponentially in the number of network nodes, as well as in the initial traffic demand values.