New Model For Scheduling Radio Networks

摘要

This dissertation explores the problem of radio network scheduling using graphmodels. It is well known that network scheduling problems map into the set of graph coloring problems. These problems are known to be NP-complete for arbitrary graphs, but can be optimally solved for some restricted classes of graphs. The graph models previously used for radio networks are shown to be inaccurate in their representation of the problem domain characteristics that affect network scheduling. Therefore, a new restricted class of graphs, called Point Graphs, is defined that accurately models radio networks. This model suggests new approaches to solving the scheduling problem. The graph coloring problems are then analyzed with respect to the problem domain. Two types of network schedule are common, broadcast and link schedules. These scheduling problems are solved using distance-2 vertex coloring and a variant of edge coloring called pm-scheduling. Traditional vertex coloring is defined only for undirected graphs. However, for network scheduling the arc direction is important. Therefore, a new problem, directed distance-2 vertex coloring, is defined, and shown to produce schedules which are superior to those produced using undirected coloring. Within the context of broadcast scheduling it is proven that, despite being a restricted class of graph, both the traditional coloring and the new directed coloring problems are NP-complete for point graphs. An exception is a subset of point graphs called linear point graphs that can be colored in polynomial time. These complexity results provide the impetus for developing new approximation algorithms for graph coloring using features unique to point graphs. The performance of these algorithms is compared to the performance of existing algorithms.