Files in this item
Files  Description  Format 

application/pdf 8324594.pdf (3MB)  (no description provided) 
Description
Title:  Ss/tdma Time Slot Assignment With Generalized Switching Modes 
Author(s):  Lewandowski, James Louis 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
Abstract:  A number of problems which arise from the time slot assignment problem for satellite communications using the satelliteswitched time division multiple access (SS/TDMA) method are studied. Given an m x n real matrix T, and a set of (0, 1)matrices {Z(,1), Z(,2), (.)(.)(.) , Z(,(nu))}, the optimization problem we wish to solve is to find nonnegative real constants (gamma)(,1), (gamma)(,2), ... , (gamma)(,(nu)) so that (DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI) is minimized, and where the inequality is implied for each corresponding entry. Although this problem can be posed as a linear program, more efficient algorithms are presented here for several special cases. We first consider the case where each Z(,i) has a specified number of ones in each row and column. For two vectors (rho) = {(rho)(,1), (rho)(,2), (.)(.)(.) , (rho)(,m)} and (lamda) = {(lamda)(,1), (lamda)(,2), (.)(.)(.) , (lamda)(,n)} of positive integers where (DIAGRAM, TABLE OR GRAPHIC OMITTED...PLEASE SEE DAI) we define the set U((rho), (lamda)) to be the set of all (0, 1)matrices which have exactly (rho)(,i) ones in the i('th) row for all i, and exactly (lamda)(,j) ones in the j('th) column for all j. A complete characterization of the class of real matrices which can be written as a positive sum of matrices in U((rho), (lamda)) is given. This result provides a generalization of the BirkhoffVon Neumann Theorem. Also for a given T, an algorithm is presented which will solve, if possible, the above optimization problem for this set of (0, 1)matrices. The optimization problem does not always have a feasible solution, and a complete characterization of the conditions needed for the existence of one is given. In the above expression, using these (0, 1)matrices, (nu) can be as large as O(n('2)). In SS/TDMA applications, it is desirable to have a small value for (nu). As a second problem we consider a fixed set Z = {Z(,1), Z(,2), (.)(.)(.) , Z(,l)} for (0, 1)matrices, where l is proportional to O(n). Given such a set of matrices, which satisfy certain constraints, we have an efficient algorithm which solves the above optimization problem for these matrices. 
Issue Date:  1983 
Type:  Text 
Description:  120 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1983. 
URI:  http://hdl.handle.net/2142/69516 
Other Identifier(s):  (UMI)AAI8324594 
Date Available in IDEALS:  20141215 
Date Deposited:  1983 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois