text: Managing interference in a network of macrocells underlaid with femtocells presents an important, yet challenging problem. A majority of spatial (frequency time) reuse based approaches partition the users based on coloring the interference graph, which is shown to be suboptimal. Some spatial time reuse based approaches schedule the maximal independent sets (MISs) in a cyclic, (weighted) round-robin fashion, which is inefficient for delay-sensitive applications. Our proposed policies schedule the MISs in a non-cyclic fashion, which aim to optimize any given network performance criterion for delay-sensitive applications while fulfilling minimum throughput requirements of the users. Importantly, we do not take the interference graph as given as in existing works; we propose an optimal construction of the interference graph. We prove that under certain conditions, the proposed policy achieves the optimal network performance. For large networks, we propose a low-complexity algorithm for computing the proposed policy. We show that the policy computed achieves a constant competitive ratio (with respect to the optimal network performance), which is independent of the network size, under wide range of deployment scenarios. The policy can be implemented in a decentralized manner by the users. Compared to the existing policies, our proposed policies can achieve improvement of up to 130 in large-scale deployments.
  @cite_30: Algorithms for transmission scheduling in multihop broadcast radio networks are presented. Both link scheduling and broadcast scheduling are considered. In each instance, scheduling algorithms are given that improve upon existing algorithms both theoretically and experimentally. It is shown that tree networks can be scheduled optimally and that arbitrary networks can be scheduled so that the schedule is bounded by a length that is proportional to a function of the network thickness times the optimum. Previous algorithms could guarantee only that the schedules were bounded by a length no worse than the maximum node degree times optimum. Since the thickness is typically several orders of magnitude less than the maximum node degree, the algorithms presented represent a considerable theoretical improvement. Experimentally, a realistic model of a radio network is given and the performance of the new algorithms is studied. These results show that, for both types of scheduling, the new algorithms (experimentally) perform consistently better than earlier methods. >
  @cite_41: This paper proposes a dynamic semi-centralized resource partitioning algorithm to mitigate the problem of co-tier interference in dense femtocell deployments. This algorithm incorporates graph-colouring and network utility concepts to address inter-cell interference in femtocell networks. The aforementioned scheme acts as a multi-cell coordination mechanism on top of intra-cell scheduling by applying a low complexity graph-based algorithm. The objective of the coordination mechanism is the efficient management of resource conflicts due to interference in a multi-cell environment consisting of femtocells. This coordination mechanism defines a novel category of graph-based ICIC algorithms that uses bipartite graph colouring to avoid resource conflicts by randomizing them in time domain.
  @cite_29: We investigate scheduling problems associated with radio networks using models based on graphs. Scheduling in networks is typically solved using graph coloring algorithms. In many cases the coloring algorithms are based on simplifying assumptions about the network structure. We show the limitations of the current models and propose modifications. The current models do not address the nonuniform transceiver transmitter networks and they over-restrict transceiver interconnections. We develop algorithms which are more specific to the domain of radio network scheduling. We compare the performance of the earlier algorithms to our algorithms. The results are analyzed with respect to both execution time and quality of solution for networks of various sizes and densities.
  @cite_0: 
  @cite_40: New distributed dynamic channel assignment algorithms for a multihop packet radio network are introduced. The algorithms ensure conflict-free transmissions by the nodes of the network. The basic idea of the algorithms is to split the shared channel into a control segment and a transmission segment. The control segment is used to avoid conflicts among nodes and to increase the utilization of the transmission segment. It is shown how these algorithms can be used in order to determine time-division multiple access (TDMA) cycles with spatial reuse of the channel. >
summary: Some policies based on spatial time reuse, partition the UEs based on the coloring of the interference graph h @cite_30 @cite_29 @cite_0 @cite_40 @cite_41 , which is not efficient. In general, a set of UEs with the same color (i.e. the UEs who can transmit simultaneously) may not be maximal (See Fig. 1 a), in the sense that there may be UEs who do not interfere but have different colors (we will also show this in the motivating example in Subsection ). In this case, it is more efficient to also let those non-interfering UEs to transmit simultaneously, although they have different colors. Hence, the partitioning based on coloring the interference graph is not efficient, because the average number of active UEs (i.e. the average cardinality of the subsets of UEs with the same color) is low.