Topology transparency in mobile ad-hoc networks
by Charles Colbourn
Arizona State University
ABSTRACT
Suppose that n mobile agents wish to communicate via radio transmission
over limited range, and there is no supporting installed infrastructure.
Indeed the "network" formed by these agents is defined implicitly by one
agent being within transmission range of another, not by any physical
connection; this network is dynamic, depending on the mobility of the
agents. Assuming only that the agents are synchronized, how can they
communicate? We first contrast contention-based approaches and
standard time-division multiple access. We then examine the situation in which the
topology is not known ("topology transparency") but the number of agents
within range of a given transmitter is limited. We develop transmission
schedules in such an environment by exploiting a connection with a
remarkable family of set systems, the cover-free families. Specifically, we
demonstrate the use of two classical families of combinatorial designs,
orthogonal arrays and Steiner systems, in designing transmission schedules;
and we show the improvement in performance over other scheduled schemes.
We emphasize the connections between the application and the combinatorial mathematics.
Back to the
Discrete Mathematics and its Applications home page.