Link packing in mmWave networks

In this paper we formulate a general link packing problem for mmWave networks. Each link is a 4-tuple determined by the choice of receiving user, transmitting access point, transmit beamforming vector and receive beamforming vector. The problem seeks to optimize the weighted sum over active links, where each link is allowed to have any arbitrarily chosen weight or priority and an active link must satisfy a minimum link quality threshold. Our formulation models a practical scenario in which blockages due to arbitrarily placed obstacles in the propagation environment are allowed to occur, where we note that mmWave transmissions are extremely susceptible to blockages. This is a key departure from the classical link packing problem where only the signal attenuation based on propagation distance is modeled. We exploit the sparsity induced by the directional nature of propagation due to beamforming, limited diffraction and the significant signal attenuation due to high path, penetration losses. We propose a novel technique that exploits this sparsity and considers an alternate formulation which is a column-sparse binary packing problem. This alternate formulation is in general conservative and we derive sufficient conditions under which it is equivalent to the original problem. We construct an efficient iterative algorithm and show that it outperforms other heuristics and guarantees a constant factor approximation for input instances that are likely to occur in mmWave networks.