A unified framework and algorithm for (T/F/C)DMA channel assignment in wireless networks

Channel assignment problems in the time, frequency and code domains have thus far been studied separately. Exploiting the similarity of “constraints” that characterize assignments within and across these domains, we introduce the first unified framework for the study of assignment problems. Our framework identifies eleven atomic constraints underlying most current and potential assignment problems, and characterizes a problem as a combination of these constraints. Based on this framework, we present a unified algorithm for efficient (T/F/C)DMA channel assignments to nodes or to inter-nodal links in a (multihop) wireless network. The algorithm is parametrized to allow for tradeoff-selectable use as three different variants called random (RAND) ordering, minimum neighbors first (MNF), and progressive minimum neighbors first (PMNF). Using theoretical analysis, we show that the worst-case performance guarantee of PMNF is an order of magnitude better than that of the traditional RAND and MNF for most networks. We also experimentally study the relative performance for one node and one link assignment problem. We observe that PMNF performs the best, and that a larger fraction of unidirectional links degrades the performance in general