University of Illinois Urbana-Champaign

Ss/tdma Time Slot Assignment With Generalized Switching Modes

Lewandowski, James Louis

This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.

Permalink

https://hdl.handle.net/2142/69516

Description

Title
Ss/tdma Time Slot Assignment With Generalized Switching Modes
Author(s)
Lewandowski, James Louis
Issue Date
1983
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
  • A number of problems which arise from the time slot assignment problem for satellite communications using the satellite-switched 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 non-negative 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
  • 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 Birkhoff-Von 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.
Graduation Semester
1983
Type of Resource
text
Permalink
http://hdl.handle.net/2142/69516

Owning Collections

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