The broadcast scheduling problem asks how an arbitrary network of broadcast transceivers operating on a shared medium may share the medium in such a way that communication over the entire network is possible. In the case where transmissions are explicitly scheduled, as opposed to be determined by contention, the problem is naturally modeled as a graph coloring problem. The canonical model is the L(1, 1)-labeling, also known as the distance-2 coloring, coloring of the graph square, or strict schedule. This coloring is, however, difficult to obtain even sub-optimally and typically uses many colors, which corresponds to an undesirable over-division of the medium.
This work introduces a relaxation of L(1, 1)-labeling called L˜(1, 1)-labeling or the pseudo-schedule. Whereas strict schedules guarantee that every path in the graph is a communication path, pseudo-schedules only require the existence of a communication path between any two vertices. The study shows that pseudo-schedules have many superior characteristics to the canonical model, provided the relaxation is acceptable. In particular, the worst case number of colors used is linear in the degree of the graph, as opposed to quadratic for strict schedules.
The formal properties of the L˜(1, 1)-labeling are comprehensively treated, including investigations of its “chromatic number,” rigorous analysis of several algorithms, and proofs of hardness of optimization and approximation. Basic results on a generalization of the coloring are obtained, and nine open problems are posed for future research.
|Commitee:||Eaton, Nancy, Henry, Timothy, Lamagna, Edmund, Sun, Yan|
|School:||University of Rhode Island|
|Department:||Applied Mathematical Sciences|
|School Location:||United States -- Rhode Island|
|Source:||DAI-B 72/06, Dissertation Abstracts International|
|Subjects:||Applied Mathematics, Computer science|
|Keywords:||Broadcast scheduling, Graph coloring, Graph theory, Medium access control, Time division multiple access, Wireless sensor networks|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be