*This work was sponsored by the Department of the Air Force under Contract FA8721-05-C-0002. Opinions, interpretations,
conclusions, and recommendations are those of the author and are not necessarily endorsed by the United States Government.
978-1-4244-2677-5/08/$25.00 ©2008 IEEE
1 of 8
MULTI-FREQUENCY TIME-DIVISION MULTIPLE-ACCESS (MF-TDMA)
RESOURCE PACKING
Navid Yazdani
MIT Lincoln Laboratory*
Lexington, MA
ABSTRACT
Multi-Frequency Time-Division (MF-TDMA) techniques
allow a large community of users to share bandwidth
efficiently. Resources can be allocated based on user
demands and user capabilities. The resources allocated to
each individual user must be packed together in the
spectrum available to the system while maintaining certain
constraints based on user capabilities. Increasing the
resource packing efficiency directly increases system
bandwidth efficiency. This paper describes the MF-TDMA
packing problem, defines a packing algorithm, and
evaluates the packing performance under various
scenarios.
INTRODUCTION
In any communication system, there are limited resources.
When a large number of users attempt to use a
communication system there is a need to arbitrate these
limited resources among the users. A system that can
efficiently arbitrate these resources can maximize the
capacity of the system.
One limited resource in a communication system is
bandwidth. Frequency-division multiple-access (FDMA)
systems divide the total available bandwidth into smaller
bandwidths, each dedicated to an individual user of the
system. In this way the limited bandwidth resource is
arbitrated by frequency sharing. In contrast, time-division
multiple-access (TDMA) systems divide the time each
user can access the total bandwidth. In this way the
limited bandwidth resource is arbitrated by time sharing.
Multi-frequency time-division multiple-access (MF-
TDMA) systems allow both frequency and time division.
Each user is allocated a particular set of sub-bandwidths at
a particular set of times (Figure 1). In the general case,
different users can be assigned different sub-bandwidth
sizes for different time durations. Then the various user
allocations must be packed into the limited bandwidth
available to the system. This paper is primarily concerned
with this packing problem and its efficiency.
In this paper, the MF-TDMA packing problem is first
defined. Then a packing solution is offered. And finally
the performance of the packing algorithm is evaluated.
MF-TDMA PACKING PROBLEM
Consider a basic MF-TDMA resource allocation algorithm
where three steps are taken. In step 1, the bandwidth for
each user is determined. In step 2, the number of time-
slots allocated to each user is determined. At this point the
‘value’ of each user’s allocation is calculated based on a
variety of factors. In step 3, the allocated timeslots of
various bandwidths are packed into the total system
bandwidth. Finding the solution that maximizes the total
value requires several iterations of the steps. For example,
the highest value solution to step 1 and step 2 may be very
poorly packed in step 3 (Figure 2). On the other hand a
lower value solution to step 1 and step 2 may be very
efficiently packed in step 3, yielding a higher overall
solution. The MF-TDMA resource allocation problem is a
form of the knapsack problem [1] which is NP-Hard. In
the general case to find the highest value solution may
require a large number of iterations of steps 1, 2, and 3. In
practice it may not be computationally feasible for a
frequency
User 4
User 7
Figure 1: MF-TDMA Example