Low Complexity Outage Optimal Distributed Channel Allocation for Vehicle-to-Vehicle Communications

Due to the potential of enhancing traffic safety, protecting environment, and enabling new applications, vehicular communications, especially vehicle-to-vehicle (V2V) communications, has recently been receiving much attention. Because of both safety and non-safety real-time applications, V2V communications has QoS requirements on rate, latency, and reliability. How to appropriately design channel allocation is therefore a key MAC/PHY layer issue in vehicular communications. The QoS requirements of real-time V2V communications can be met by achieving a low outage probability and high outage capacity. In this paper, we first formulate the subchannel allocation in V2V communications into a maximum matching problem on random bipartite graphs. A distributed shuffling based Hopcroft-Karp (DSHK) algorithm will then be proposed to solve this problem with a sub-linear complexity of O(N^{2/3}), where N is the number of subchannels. By studying the maximum matching generated by the DSHK algorithm on random bipartite graphs, the outage probabilities are derived in the high (two near vehicles) and low (two far away vehicles) SNR regimes, respectively. It is then demonstrated that the proposed method has a similar outage performance as the scenario of two communicating vehicles occupying N subchannels. By solving high degree algebraic equations, the outage capacity can be obtained to determine the maximum traffic rate given an outage probability constraint. It is also shown that the proposed scheme can take an advantage of small signaling overhead with only one-bit channel state information broadcasting for each subchannel.