Achieving spectrum conservation for the minimum-span and minimum-order frequency assignment problems

Content Provider	Semantic Scholar
Author	Heyward, Ann O.
Copyright Year	1992
Abstract	Effective and efficient solution of frequency assignment problems assumes increasing importance as the radiofrequency spectrum experiences ever-increasing utilization by diverse communications services, requiring that the most efficient use of this resource be achieved. The research presented explores a engg_n.g_l approach to the frequency assignment problem, in which such problems are categorized by the appropriate spectrumconserving objective function, and are each treated as an N-job, M-machine scheduling problem appropriate for the objective. Results obtained and presented illustrate that such an approach presents an effective means of achieving spectrum-conservlng frequency assignments for communications systems in a variety of environments. 1.0 Introduction The general frequency assignment problem may be stated as follows: given a number of nodes in a set of communications networks, and constraints imposed by the need to eliminate unacceptable levels of a variety of types of interference between communications links, determine the assignment of frequencies (channels) to each node that achieves acceptable performance relative to one or more selected criteria. This general problem statement encompasses a range of problems of interest to the communications planner. One such problem is the need to assign sets of frequencies or channels to the transponders of a collection of communications satellites serving a variety of geographical areas on the Earth, so that allowable levels of co-channel and adjacent-channel interference are not exceeded, all requirements for channels are met, and the minimum number of channels is utilized. Alternatively, in frequency division multiple access (FDMA) satellite networks, dynamic channel assignment to network nodes accessing a single satellite may be required, while preserving as much continuous spectrum as possible to respond to fluctuating demands. There are a number of insights to be gained from previous research that may be applied to the development of an approach to the frequency assignment problem. The frequency assignment problem is NP-hard; it is unlikely that a computational procedure can be devised which will find a truly optimum assignment within reasonable computation time for large, complex problems 15,16. Certain classes of frequency assignment problems are equivalent to graph-coloring problems 18'39. Graph-colorlng approaches therefore provide some strategies which may be extrapolated to specific frequency assignment problems, particularly with regard to ordering of frequency, assignment requirements to be 5,6,7,8,9,21,26,27,31,34,36,37,39 satisfied . A number of heuristic approaches to the frequency assignment problem have also been developed. Such approaches often exploit specific assignment _ in order to minimize spectrum use or, alternative_, maximize spectrum conservation. 1,2,4,10,11,12,13,20,2_,25,.28,29,30,32,3:_,38. An approach particularly relevant to the research presented in this paper is that of lgnizio 19,which uses a generalized goal-programming approach to the minimal interference, multicriterion, N-job, 1-machine scheduling problem. Examination of this approach implies that a more general, N-job, M-machine scheduling approach displays significant promise as a frequency assignment technique. High demands are placed on virtually all portions of the frequency spectrum that are currently in use for communications applications. Thus, frequency/channel assignment procedures should seek spectrum conservation. As previous researchers have noted, alternative definitions of spectrum conserving frequency assignment are possible 18. A minimom-grder frequency assignment (utilizing the minimum number of discrete frequencies) may be sought; this objective is desired in circumstances dictating conservation of the maximum number of _ frequency slots for future assignment. Alternatively, a minimum-span assignment (with minimum difference between highest-valued and lowest-valued assigned frequencies) is desired when the mafimum length continuous portion of the spectrum should be conserved for future assignment. These objectives are conflicting: use of a greater frequency span may be required to achieve a minimum-order assignment, and, conversely, use of a higher number of frequencies may be required to achieve a minimum-span assignment. These conflicting objectives require different modelling and solution approaches, but both objectives are accommodated within the theoretical framework of N-job, M-machine scheduling problems. Two N-job, M-machine scheduling models of the frequency/channel assignment problem were developed, corresponding to minimum-span and minimum-order frequency assignment objectives, and were applied to problems of varied size and complexity. Results indicate circumstances under which use of each model is suitable. For the model corresponding to minimum-span frequency assignment, results also indicate circumstances under which each of two requirements-ordering techniques are most effective. Finally, both models and associated requirements-ordering techniques are demonstrated to result in spectrum-conserving frequency assignments, thus presenting an effective ng.e.._l approach for solution of minimum-order and minimumspan frequency assignment problems via N-job, Mmachine scheduling. 2.0 Scheduling Models of the Frequency Assi__ament Problem Two N-job, M-machine scheduling models of the frequency/channel assignment problem are presented below, corresponding to the conflicting objectives of minimum-span and minimum-order frequency assignment, respectively. The first model is a scheduling analog of the minimum span frequency assignment problem the Minim_lm M k_ Model. The second model is a scheduling analog of the minimum order frequency assignment problem -the_ Resource Model. The first model is applicable to frequency assignment in portions of the spectrum allocated to more than one service, whose frequency assignments cannot be interleaved or cannot overlap, since the maximum-length continuous portion of the spectrum is conserved for future assignment. The second model is applicable to frequency assignment in portions of the spectrum allocated to only one service, where conservation of the maximum number of frequency slots for future assignment is desired. 2,1 The Minimum Makesp.an Model Minimization of the makespan, or total time, required to complete a given series of jobs or operations within a schedule is directly analogous to minimizing frequency span, if available frequency bandwidth is mapped into a finite time interval. The minimum time needed to complete all jobs in the schedule will be equivalent to use of the minimum frequency span to complete the assignment. A schedule will determine specific start and stop times for particular jobs, which consist of a series of distinct operations to be performed on different machines. Machines represent distinct nodes in a communications system where operating frequencies are required; each node may require a different number of operating frequencies. An operation within a job represents assignment of one operating frequency to one node; each jg.._, therefore, will consist of the assignment of an operating frequency to each of a series of nodes. Interference protection requirements between operating frequencies at different nodes are represented as time separations between operations within the same job, or different jobs, under the assumption that all interference protection requirements between nodes may be expressed as frequency separation requirements. To recover a frequency assignment from solution of a scheduling problem, the resulting schedule must translate directly to a frequency assignment. To construct a one-to-one mapping of frequency to time, let time interval (0,...,T) represent the interval (0, BW) where BW, the total frequency bandwidth available, is the difference between the lowest frequency available and the highest frequency available, e.g. Fmax-Fmi n. The interval (0, BW) is discretized by selecting a small portion of the available bandwidth, Fnorm, so that the total interval (0, BW) contains a reasonable number of discrete units that each approximate a unit of frequency separation required between assignments. In order to construct channel assignments, Fnorm must be art integer divisor of the channel bandwidth. The interval (0, BW) may then be discretized as (0, l*Fnorm, 2*Fnorm..... BW); discrete times in the interval (0, T) are then: f/ -Fn_ ÷ 1 (1) xt" F,M. where fi is in (Fmin,Fmax), the range of frequencies available for assignment. Assigned frequency values may be recovered from the scheduling problem solution by inverting (1): --(xiI)F,_,+ F.._. (2) where xi = (0,...,T). The transformation from the frequency interval (Fmin,Fmax) to the discretlzed time interval (0,T) is illustrated in Figure 1. CONSTRUCTION OF DISCRETE TIMES (t,, ,,,"r} FROM Ful N , F MAX' AND F NOP, M
File Format	PDF HTM / HTML
DOI	10.2514/6.1992-1960
Alternate Webpage(s)	https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/19920013944.pdf
Alternate Webpage(s)	https://doi.org/10.2514/6.1992-1960
Language	English
Access Restriction	Open
Content Type	Text
Resource Type	Article