Keywords

1 Introduction

In 1980, Hale introduced the relationship between frequency assignment problems (FAPs) and graph coloring [1]. Since then, many authors have noted that frequency assignment is a graph coloring problem if only the co-channel constraint is involved [2–4].

Graph-coloring is defined as a way of coloring the vertices of a graph such that no two adjacent vertices share the same color. The most common type of graph coloring seeks to minimize the number of colors for a given graph. Minimal coloring can be achieved using a brute-force search or exhaustive search that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem’s statement when the problem size is limited [5]. Brelaz’s heuristic algorithm can also be used to produce a satisfactory, but not necessarily minimum coloring of a graph [6]. To find an optimal solution, Giortzis tried the branch-and-bound method of integer linear programming [2].

On the other hand, many frequency assignment problems can be expressed as constraint satisfaction problems (CSPs) [3, 4]. A CSP consists of a set of variables. Each variable is associated with a finite set of possible values and a set of constraints restricts the values that can be simultaneously assigned to the variables. Most of these techniques produce approximate, near-optimal solutions. In order to assess the quality of these approximate solutions, some lower bounds are needed. The lower bound of the chromatic number of graph coloring has been studied for a few decades [7].

In this paper, we describe a formal definition of the channel assignment problems in Sect. 2. Furthermore, graph coloring algorithms are described in Sect. 3, and simulation results are presented in Sect. 4, and a conclusion is provided in Sect. 5.

2 The Channel Assignment Problems

We build CSP models for two different but similar channel assignment problems. One is frequency assignment for low power FM broadcasting and the other is reader collision problem in RFID systems. The CSP model gives us a drastic reduction of search space of the problems.

2.1 Frequency Assignment for Low Power FM Broadcasting

FM radio signals are transmitted on VHF frequencies in the range of 88–108 MHz and this band is usually partitioned into a set of channels, all with the same bandwidth: 200 kHz of frequencies. For this reason, the channels are usually numbered from 1 to 100. Due to the vastly increasing number of radio stations and the very limited availability of frequencies, it is difficult to find vacant frequencies that can be assigned to the low power FM radio [8] operators. Consequently, a major challenge to improve the frequency utilization efficiency is needed.

Our research objective is to find a frequency assignment that satisfies all the constraints using a minimum number of frequencies while maximizing the number of radio stations served in a given area. A given area is partitioned into cells, which are served by FM radio transmitters. In the problem, each radio transmitter can be viewed as a variable. The set of possible frequencies makes the domain for each transmitter variable can take. Several types of frequency separation constraints exist and these make the problem more complex than the simple graph coloring as shown below.

  • Co-channel constraint (CCC): Any two transmitters located at different cells cannot use the same channel within interfering distance. If f i and f j are the frequencies assigned to transmitter i and j, d(i, j) is the distance between transmitter i and j, k is a sufficiently separated distance, then these give rise to constraints of the form:

    $$ f_{i} \ne f_{j,} \;{\text{if}}\;d\left( {i, \, j} \right) \le k $$

  • Adjacent channel constraint (ACC): Any two transmitters located at different cells within interfering distance cannot use adjacent channels, unless they are separated by sufficient frequencies because there is still the potential for interference normally within one to three channel-distance. The ACC can be represented as an n by n symmetric compatibility matrix corresponding to a constraint graph with n vertices. Therefore a number of constraints arise in the following form:

    $$ \left| {f_{i} - f_{j} } \right| \ge c_{ij} $$

    where i ≠ j and c ij is the required number of channel separation.

  • IF constraint (IFC): An intermediate frequency (IF) a beat frequency between the signal and the local oscillator in a superheterodyne radio receiver. The transmitters should not be apart between any two channels assigned to the same cell or adjacent cells for better reception of signals.

  • Pre-assigned frequency constraint (PFC): Some frequencies are already occupied by local FM stations within the service area. Thus, these channels cannot be assigned.

2.2 The Reader Collision Problem

In RFID systems, interference refers to the collision of different radio signals with the same frequency, which leads to distorted signals being received. Occasionally, if tags or readers broadcast radio signals of the same frequency, collisions occur [9, 10]. There are two primary types of reader interferences experienced in RFID systems: reader-to-reader interference and reader-to-tag interference [11]. Reader-to-reader interference occurs when a reader transmits a signal that interferes with the operation of another reader, thus preventing the second reader from communicating with tags in its interrogation zone [10, 12]. Reader-to-tag interference occurs when a tag is located in the interrogation zone of two or more readers and more than one reader tries to read the same tag simultaneously [10]. We consider reader-to-reader interference only in this paper.

For example, in Fig. 1, the signal strength of a reader is superior to that of a tag and therefore if a frequency channel occupied by R2 is the same as that of T1 and R1, R1 is no longer able to listen to T1′s response. This problem can be solved when the channel occupied by R1 and T1 is different from the channel of R2. In the case of an identical channel being used, it should be assumed that R1 and R2 keep their distance long enough for T1’s responding signal strength to become more powerful than R2’s interference signal [13].

Fig. 1
figure 1

RFID reader interference

Full size image

Some researchers indicate that the reader collision problem of RFID systems is equivalent to the channel assignment problem, which, in turn, is equivalent to the simple graph-coloring problem [12]. In the reader collision problem, the following types of frequency separation constraints exist.

  • Co-site constraints (CSC) : Any pair of channels in the same cell must have the specified frequency separation, typically 3 channels in RFID reader collision problem. r i means reader i, therefore f(r i ) is the channel assigned to the reader i.

    $$ \left| {{\text{f}}(r_{i} ) - {\text{f}}(r_{j} )} \right| \ge k $$

  • Adjacent channel constraints (ACC): Any two transmitters located at different cells within interfering distance cannot use adjacent channels, unless they are separated by sufficient frequencies because there is still the potential for interference normally within one to two channel-distance. Therefore a number of constraints arise in the following form:

    $$ \left| {{\text{f}}_{i} - {\text{f}}_{j} } \right| \ge {\text{c}}_{ij} $$

where i ≠ j and c ij is the required number of channel separation. The ACC can be represented as an n by n symmetric compatibility matrix corresponding to a constraint graph with n vertices.

This problem is very similar to the frequency assignment of LPFM broadcasting because we assign different channels to avoid interference between each transmitter. In this case, an RFID reader can be thought of as a transmitter and a tag as a radio receiver.

3 The Graph Coloring Algorithms

A graph G(V,E) is a pair of finite sets where the set V contains the vertices of the graph and the set E contains distinct unordered pairs of vertices called edges. The set of vertices V may represent the transmitters in the FM radio stations or readers in the RFIS systems, i.e. V = {v 1 , v 2 ,,…, v n } is the set of readers in a RFID system or the set of FM radio transmitters. The set of edges E represent potential reader collision between readers in a RFID system or interferences between FM radio transmitters. The set of possible frequencies makes the domain for each variable. Therefore, D i is the domain of frequencies that a variable i can take.

In RFID system, if two readers have overlapping regions between their interrogation zones, we connect these two readers by an undirected edge. This way, the reader collision in a dense reader environment is constructed as a multigraph G = (V,E) [14].

The traditional approach to minimizing the number of assigned frequencies is to perform graph coloring on the channel graph. Because each color can be identified with one channel, the minimal number of colors, which is called the chromatic number in graph theory, equals the minimal number of channels needed.

Channel assignment problems are modeled as constraint satisfaction problems in Sect. 2. A solution to a CSP is the assignment of every variable to a value in its domain in such a way that all the constraints are satisfied. The total number of frequencies assigned to the transmitters can be considered an objective. The problem is solved by a systematic search through the set of all possible assignments to the decision variables.

Experiments show that good variable ordering moves a CSP solution to the left of the search tree, so the solution can be found quickly using a heuristic backtracking algorithm. The backtracking method essentially performs a depth-first search of the search space and it can be enhanced using variable ordering heuristics.

One of the best-known dynamic variable-ordering heuristics is dom, which chooses the next variable with the smallest remaining domain. Therefore, it is also called the smallest-domain-first principle. This ordering heuristic was introduced by Golomb and Baumert [15] and Haralick and Elliott [16], who show analytically that dom minimizes the depth of search trees.

Static heuristics order the variables from the highest to the lowest degree by repeatedly selecting a variable in the constraint graph. The typical algorithm is deg, presented by Freuder [17]. Sohn applied the deg algorithm to the frequency assignment of LPFM problem to generate a satisfactory, but not minimal result [8]. We can also think of the <deg,dom> heuristic in addition to simple deg. In this case, dom acts like a tiebreaker when the degree of the variables is the same.

Bessiere and Regin [18] show that static variable ordering, which considers variables in descending order of degree, gives good results in comparison with dom when the constraints are sparse. However it performs very badly on complete constraint graphs. They propose a combined heuristic dom/deg that does not give priority to the domain size or to the degree of variables, but uses them equally in the criteria. This chooses the next variable, minimizing the ratio of domain size to degree. Boussemart et al. [19] propose dom/ωdeg to divide domain size by weighted degree. As another efficient combined heuristic of dom and deg, we propose αdom - deg to select the first variable in the smallest value of domain size and the biggest value of degree, where α is a weighting factor in the domain size. The algorithm αdom - deg chooses the first transmitter in the center of the service area because the center is most constrained. Once a transmitter has been selected, the algorithm generates a frequency for it in a nondeterministic manner. Once again, the model specifies a heuristic for the value ordering in which the frequencies must be tried. To reduce the number of frequencies, the model says to try the values that were used most often in previous assignments first. This is called the most-used value-ordering heuristic.

4 Simulation Results

4.1 Frequency Assignment for LPFM Broadcasting

For simplicity, we have chosen a grid of square cells for the topology of the region. We consider a 5,000 by 5,000 m square service area for each instance. The each cell is 500 × 500 m in size and we have a total of 100 cells in the service area. As is clear from the problem statement, transmitters are contained within cells, and each cell may have one radio transmitter at the most. Some cells may not have a transmitter due to a geographic reason. Some frequencies cannot be assigned to the transmitters because commercial broadcasting operators already use the frequencies.

Widely used intermediate frequencies (IF) are 10.7 MHz in the FM superheterodyne radio receiver. This makes IF constraints, so 10,700/200 kHz = 53.5 channels (53 and 54 for real channels) should not be apart between adjacent transmitters within the service area. We assume all LPFM transmitters are at 25 m height above average terrain (HAAT) with 1 watt effective radiated power (ERP). The radio service area is within about 2 km radius for each transmitter. Table 1 clearly shows the minimum channels when each variable ordering heuristic is applied to the problem.

Table 1 Performance comparison of variable ordering heuristics for frequency assignment of LPFM broadcast radio stations
Full size table

4.2 The Reader Collision Problem

We consider a 100 m by 100 m square service area for each instance. Each cell is 10 m by 10 m in size, and we have a total of 100 cells in the service area. As is clear from the problem statement, RFID readers are contained within cells, and each cell may have zero to two readers where we use 67 readers on average in the service area. Some cells may not have readers due to geographic reasons. The bandwidth is 200 kHz, and we use a total of 32 channels in RFID frequency ranges from 917 to 923.5 MHz. Each reader’s output power is 10 mW effective radiated power (ERP).

Table 2 shows the minimum number of channels when each variable ordering heuristic is applied to the problem. We carry out our simulation experiments using an ILOG OPL 3.7 optimization tool to verify the effectiveness of the proposed αdom - deg variable ordering algorithm over our simulation environment.

Table 2 Performance comparison of variable ordering heuristics for the reader collision problem
Full size table

5 Conclusions

Solving a frequency assignment problem is a graph coloring and many researchers have attempted to find approximate solutions using heuristic searches. We presented the CSP models for the two different problems to reduce the search space: one is the frequency assignment for low power FM broadcasting and the other is the reader collision problem of RFID systems. We also applied the proposed variable ordering heuristic, αdom - deg, to traverse the search tree efficiently and reduce search time greatly. The simulation results show that the proposed algorithm, αdom - deg, is far better than the conventional algorithms in terms of three comparison parameters, taken as a whole.