User Scheduling and Beam Alignment in mmWave Networks With a Large Number of Mobile Users.

In this paper, we study an optimal user scheduling with minimum beam alignment overhead in millimeter wave networks. The problem is posed as constrained Markov decision process (CMDP) with the goal of minimizing the average beam alignment overhead subject to the average rate constraint on each user. Under a certain assumption on the rate function of the users, by using a structural result derived from the Lagrangian formulation of the CMDP, we show that the optimal policy should keep scheduling the users that are scheduled in the previous time slot unless an abrupt change in the beam direction occurs. Using this result, the complexity of the problem decreases to polynomial in the number of users. In addition, we provide a heuristic deterministic algorithm that achieves $({1}+\epsilon)$ approximation of the optimal solution, with smaller $\epsilon $ at the cost of longer transmission interval of each user. Lastly, to deal with the case where the assumption on the rate function does not hold due to beam conflicts between the users, we consider a system model that accounts for an angular channel information. A new CMDP is formulated for the problem and a heuristic algorithm based on the age information is proposed. [ABSTRACT FROM AUTHOR]