Network coding based adaptive CSMA for network utility maximization

It is well known that network coding can improve the capacity of wireless networks efficiently while adaptive CSMA-based link scheduling can efficiently allocate channel resources in a fully distributed manner in such networks. By combining the advantages of these two mechanisms, in this paper, we are aimed at achieving network utility maximization in a fully distributed manner when network coding is applied. For this purpose, we first model the network under study by considering transmission conflict relationship in the network. Then, by treating coding combinations as scheduling units for transmissions at the MAC layer, we deduce the weighted network capacity based on the network-coding-based adaptive CSMA link scheduling and further analyze its features. This way of link scheduling also eases the queue load estimation when network coding opportunity is present, which is a prerequisite for CSMA based link scheduling. We accordingly propose a distributed network-coding-based adaptive CSMA algorithm, which assigns the mean backoff time of a coded packet transmission for medium access based on its coding gain. We prove the convergence property of the proposed algorithm and its optimality in network utility maximization when coding combinations/patterns applicable at nodes in the network are known. Simulation results validate our analytical results.