Hypergraph-based Modelling for Coexistence-Aware Channel Allocation

In this paper a novel technique for modelling a radio frequency (RF) environment based on hypergraph theory is investigated for solving coexistence management of heterogeneous networks and efficient channel allocation for spectrum sharing. Conventionally, traditional graph theory is used to model interference relationships and exclusive channel allocation. The demand for wireless services is increasing, hence the need for efficient spectrum management techniques, such as spectrum sharing among coexistent networks. However, coexistence-aware channel allocation would require representation of both interference and spectral coexistence relationships in the RF environment model. A graph cannot be used to represent multiple and multifaceted relationships without violating consistency with graph theory. This paper therefore proposes representing the RF environment using a hypergraph. The network coexistence method used is an implementation of the IEEE 802.19.1 method for co-sharing via network geometry classification. The simulation results show that the hypergraph-based model allocated channels, on average, up to 8% more networks than the graph-based model. The results also show that, for the same RF environment, the hypergraph model requires up to 36% fewer channels than the graph model to achieve an average of 100% operational networks. The rate of growth of the running time of the hypergraph-based algorithm with respect to the input size is quadratic, like the graph-based algorithm.