Open Collections

Link scheduling directed graphs using undirected edge colours

University of British Columbia

Communication in a wireless network is typically modeled as either a directed or an undirected communication graph. Link scheduling is the problem of assigning time slots to each edge so that communication on every edge at its assigned time may occur without interference. Interference is also modeled as a graph, typically the same as the communication graph. However, interference may occur even without the desire or possibility of communication and warrants its own graph. When link scheduling directed graphs, Packet Radio Network (PRN)-colouring is used to create a link schedule. When modeled as an undirected graph, strong edge colouring is typically used to create a link schedule. Both PRN and strong edge colouring have been shown to be NP-complete. In this thesis, two new types of undirected edge colourings are analyzed: Acyclic Colour Induced (ACI) and Even Cycle Parity Colour Induced (ECPCI) edge colouring. Both ACI and ECPCI edge colouring are less restrictive than strong edge colouring in the sense that a strong edge colouring provides both an ACI and an ECPCI edge colouring; in fact, it is possible to use significantly fewer colours. Further, there is a translation that will take an ACI or an ECPCI edge colouring of an undirected graph and transform it into a directed PRN-colouring of the corresponding symmetric directed graph.These two new types of edge colourings are shown to be NP-complete. Lower bounds for ACI and ECPCI edge colouring planar graphs are analyzed. It is shown that there exists planar graphs with maximum degree Δ that require 33Δ/16 (respectively 2Δ+1) colours in an ACI (respectively ECPCI) edge colouring. Also, algorithms are given for strong, ACI, and ECPCI edge colouring that take into account a communication graph that is a subgraph of the interference graph. Using these algorithms, a link schedule using PRN-colouring on directed communication and interference graphs can be created that is an Ο(1) and Ο(\sqrt{\gamma}) approximation for planar and general graphs with genus γ≥1 respectively. The approximation algorithm given improves the best known upper bound for link scheduling planar graphs.

Text

2012-05-16

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/42329

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/