Keywords

1 Introduction

Interest in the channel assignment problem (CAP) has been growing rapidly with both the spread of wireless data networks and the increasing scarcity of electromagnetic (EM) spectrum [1, 13, 35]. Efficient channel allocation schemes leverage channel reuse, where a channel is a contiguous block of EM spectrum. The ability to reuse a channel is dependent on (among other things) co-channel interference, i.e., interference occurring between two radios assigned the same channel but that do not wish to communicate. The vast majority of research on the CAP considers only pairwise interference constraints [1] due to the computational challenges of explicitly representing cumulative interference, and the ease with which the problem can be represented as a graph-coloring problem [4, 9, 25, 27, 38]. This seemingly simple problem is NP-complete [6], and yet the realistic cumulative interference constraints we model are much more difficult [26,27,28].

We consider the challenge of a spectrum manager who must determine an efficient channel allocation scheme to support radio communications over a certain period of time for mobile units operating on rough terrain. We specifically consider the use of wideband mobile ad-hoc network (MANET) radios fielded by the United States Marine Corps (USMC), but our approach generalizes to other military services and any EM transceiver system requiring a discrete channel assignment. The spectrum manager knows the capabilities of each radio and their starting locations, and has a rough understanding of their future locations within the operating area. Using this information and terrain elevation data, the spectrum manager must determine the minimum number of channels required to support communications with an acceptable level of co-channel interference. Further, since each radio requires manual assignment, the spectrum manager is responsible for the reallocation of channels whenever the situation changes, and therefore desires to minimize the number of channel changes over time.

Due to the computational difficulties of exactly solving the CAP, heuristics are often used to solve the problem [1, 23]. While heuristics may provide usable solutions in reasonable amounts of time, we feel that optimality bounds are important for understanding the goodness of a particular solution, especially since spectrum is increasingly crowded and scarce, and communications may be critical to the success of a military operation.

Dunkin et al. [9] describe the challenge of using cumulative interference constraints, and instead use simple binary and tertiary constraints (i.e., groups of three interfering radios) using a constraint satisfaction approach. Daniels et al. [7] formulate an integer CAP that considers cumulative interference and establish the NP-hardness of the problem. Fischetti et al. [11] use pre-processing and branch-and-cut to solve their cumulative interference CAP, but their problem sizes are much smaller than those studied here and they consider relatively few sources of interference, i.e., they have a relatively small number of constraints.

We use integer and constraint programming methods to develop more efficient methods of channel allocation. Our first problem minimizes the number of required channels (i.e., minimum order), subject to cumulative co-channel interference constraints for any given instance in time, and the second problem minimizes the number of channel assignment changes over time (i.e., minimum cost). We use realistic radio performance data from large-scale, high-fidelity simulations of U.S. Marine Corps operational scenarios (the data are available to the research community at [12]). To our knowledge, we are the first to solve to global- or near-global optimality the minimum-order and minimum-cost channel assignment problems for large, realistic datasets while also considering the effects of cumulative co-channel interference and the costs of manual channel changes. We believe that the tools created for this application are likely to be appropriate for other complex graph-coloring problems, as well.

This paper is organized as follows. Section 2 provides an overview of our model of MANET operations. Section 3 describes our formulation and computational results in solving the minimum-order channel assignment problem, and Sect. 4 does the same for the minimum-cost CAP. Section 5 provides conclusions and suggestions for future research.

2 Model of MANET Communications

We create a network model to simulate the key aspects of a MANET formed by tactical wideband radios at a given moment in time (i.e., time step). Let \(r\in R\) (alias s) represent each MANET radio. Each radio is permanently assigned to a MANET unit \(u \in U\), indicated by the set of logical arcs \((r,u) \in L\). In a military scenario, a unit may represent a tactical military organization, such as an infantry company or battalion headquarters. Let the set of nodes N (indexed by n) consist of both radios R and units U, i.e., \(n \in N = R \cup U\). Let a channel \(c\in C\) be a contiguous range of EM frequencies, where C is the set of available orthogonal (i.e., non-interfering) channels. Each unit u and the radios assigned to it require a channel assignment.

Let \((r,s) \in W\) indicate the set of arcs representing wireless transmissions between all radios \(r,s \in R\). A unit \(u \in U\) forms a separate MANET among its assigned radios using the available wireless arcs \((r,s) \in W : (r,u) \in L, (s,u) \in L\). Figure 1 shows two separate units (indicated in blue and green) and their assigned radios. The solid lines indicate bidirectional wireless arcs \((r,s) \in W\) between radios. Any radio (e.g., radio r in Fig. 1) communicates with its network control radio (e.g., radio s) via these arcs (a radio may route through other radios in the same unit to reach the network control radio). All radios are subject to co-channel interference from any other radios assigned to different units but operating on the same channel and geographically close enough to cause interference; this is indicated by dashed gray arrows directed to r (other lines withheld for clarity).

Fig. 1.
figure 1

Simple example of two units (indicated in blue and green) with network control radios (solid circles) and other radios (open circles). Wireless arcs are indicated by arrows. The radios within each unit must be capable of bi-directional communication with their unit’s network control radio via direct communication or routing through other radios in the same network. All radios are subject to co-channel interference (dashed arrows) from other radios assigned to different units but operating on the same channel. (Color figure online)

Full size image

To calculate both co-channel interference and the strength of desired wireless transmissions between intra-unit radios, we calculate the received signal strength (RSS) along all wireless arcs \((r,s) \in W\) in dBm (power ratio in decibels relative to milliwatts). We instantiate our scenarios in Systems Toolkit (STK) [3] and then use Python and the Terrain Integrated Rough Earth Model (TIREM) of Alion Science & Technology Corporation [2] to calculate path loss considering the technical specifications of each radio and the effects of terrain, atmospheric absorption, etc.

For each radio \(s \in R\), we follow [1] and pre-calculate the maximum allowable interference in watts \(\textit{max}\_\textit{interference}_s^c\). This calculation is based on the RSS between radios and each particular radio’s required signal-to-interference ratio (SIR), a measure of signal quality [33]. Any co-channel interference above this level severs the shortest path and thus disconnects the radio from its assigned network control radio. Among radios not assigned to the same unit but operating on the same channel, the RSS represents co-channel interference. The magnitude of co-channel interference along all arcs \((r,s) \in W\) for each available channel \(c \in C\) is pre-calculated in watts, and is indicated by \(\textit{interference}_{rs}^c\).

We use realistic datasets generated from high-fidelity simulations of U.S. Marine Corps operations. We find the largest scenario, depicting a Marine Expeditionary Force (MEF) of 60,000 Marines conducting a large amphibious operation and based on Integrated Security Construct B [8], to be the most computationally interesting. We generate separate datasets at 20 different time steps (i.e., discrete moments) within the scenario (each containing the locations of 118 units comprising 1887 total radios). See [26] for full details of our scenarios.

3 Minimum-Order Channel Assignment Problem (MO-CAP)

3.1 Problem Formulation

The MO-CAP aims to minimize the total number of channels required to support MANET operations at a given moment in time.

Variables:

$$\begin{aligned} X_n^c&= \left\{ {\begin{array}{clcr} 1,&{}\text {if node }n \text { uses channel }c\\ 0,&{}\text {otherwise} \end{array}}\right.&\forall n \in N, c \in C \end{aligned}$$
(1)
$$\begin{aligned} Y^c&= \left\{ {\begin{array}{clcr} 1,&{}\text {if channel }c\text { is used} \\ 0,&{}\text {otherwise} \end{array}}\right.&\forall c \in C \quad \quad \quad \end{aligned}$$
(2)

Constraints:

We enforce the definition of \(Y^c\) via:

$$\begin{aligned} X_u^c \le Y^c \quad \forall u \in U, c \in C. \end{aligned}$$
(3)

Each radio is assigned the same channel as its associated unit:

$$\begin{aligned} X_r^c = X_u^c \quad \forall c \in C, (r,u) \in L. \end{aligned}$$
(4)

To ensure each unit u is assigned one and only one channel, we add the constraints:

$$\begin{aligned} \sum _{c \in C} X_u^c = 1 \quad \forall u \in U. \end{aligned}$$
(5)

Two radios from different units are subject to interference if they are both assigned to the same channel. This assignment will only be allowed if the received \(\textit{interference}_{rs}^c\) between these two radios is less than the precalculated allowable total interference, \({max\_interference}_s^c\). One way of representing this pairwise interference is:

$$\begin{aligned} \textit{interference}_{rs}^c X_r^c X_s^c \le {max}\_{interference}_s^c \quad \forall \left( r,s \right) \in W, c \in C. \end{aligned}$$
(6)

To model the total aggregate interference that a radio receives, we follow the lead of [19], and assume the cumulative effects of jamming sources on the same channel are additive (in watts). That is, a radio \(s \in R\) may be unable to use a channel \(c \in C\) because the total sum of interference exceeds the threshold \({max\_interference}_s^c\), even if the interference received from any single radio is less than the threshold. Summing along all arcs yields:

$$\begin{aligned} \sum _{r:(r,s) \in W} \textit{interference}_{rs}^c X_r^c X_s^c \le {max\_interference}_s^c \quad \forall s \in R, c \in C. \end{aligned}$$
(7)

To linearize these constraints, we introduce the binary variable \(Z_{rs}^c\) where:

$$\begin{aligned} Z_{rs}^c = \left\{ {\begin{array}{clcr} 1,&{}\text {if } X_r^c = X_s^c = 1 \\ 0,&{}\text {otherwise} \\ \end{array}}\right. \quad \quad \quad \forall r,s \in R, c \in C \end{aligned}$$
(8)

which is enforced via:

$$\begin{aligned} Z_{rs}^c&\ge X_r^c + X_s^c - 1 \quad&\forall r,s \in R, c \in C \end{aligned}$$
(9)
$$\begin{aligned} Z_{rs}^c&\le X_r^c \quad&\forall r,s \in R, c \in C \end{aligned}$$
(10)
$$\begin{aligned} Z_{rs}^c&\le X_s^c \quad&\forall r,s \in R, c \in C. \end{aligned}$$
(11)

Our cumulative co-channel interference constraints are thus represented:

$$\begin{aligned} \sum _{r:(r,s) \in W} \textit{interference}_{rs}^c Z_{rs}^c \le {max\_interference}_s^c \quad \forall s \in R, c \in C. \end{aligned}$$
(12)

Given the results of radio propagation simulation in a military scenario, we pre-calculate the \({max\_interference}_s^c\) values (using the method described above), and fix the assignment of radios to their respective units (indicated by arcs \(\left( r,u \right) \in L\)).

Since the goal is to minimize the total number of channels required, our objective function is:

$$\begin{aligned} \min \sum _{c \in C} Y^c. \end{aligned}$$
(13)

3.2 Computational Challenges

The MO-CAP is relatively easy to understand and describe. However, it suffers from several serious computational difficulties when the full problem is simply provided to a commercial solver (e.g., CPLEX or Gurobi) with our realistic datasets. First, commercial solvers may be sensitive to vast differences in input parameters. In our simulated datasets, our interference values vary by 24 orders of magnitude, and are generally quite small. Also, non-integral input data may result in highly fractionalized LP solutions, as the solver will attempt to pack the most units (including fractions of units) onto the same channel.

Another computational problem (also observed by [32]) is that of symmetry, which occurs when channel assignments may be changed among units with no corresponding change in the objective function value [24]. The very near symmetry that is characteristic of our datasets (as opposed to exact symmetry) results from some units being located near each other, and is especially difficult for solvers to detect and mitigate [31].

Some of these computational problems could be avoided if we considered only pairwise interference constraints, as IP and constraint satisfaction solvers reformulate these pairwise constraints into clique constraints and then handle these structures very efficiently. Unfortunately, these constraints alone do not adequately represent our real-world problem, and will cause at least a few radios to be disconnected from their respective MANETs.

A simple “brute force” IP method (i.e., using CPLEX to solve the full problem as-is, without providing any initial solution or conducting preprocessing) fails to obtain useful answers to the Marine Corps scenario, even after two weeks of computation on a cluster of 14 high-performance desktop computers. In an attempt to improve the solution process, we create a simple greedy heuristic that iteratively “packs” units onto channels until the channel is “full,” and then starts with the next channel. We provide the heuristic solution as an initial feasible solution to CPLEX and attempt to solve the problem for a single time step. We find that after 60 h of runtime, CPLEX improves upon the initial feasible solution, but the obtained solution has an optimality gap of 77%. This indicates that our heuristic may not be finding very good solutions and/or the lower bounding technique is not very effective, and that we require more sophisticated methods if we are going to solve realistic instances of this problem with certifiably-good solutions.

3.3 Integer Programming Solution Method and Results

Rather than simply “throw” the computationally-challenging cumulative interference constraints (12) at a solver, we preprocess the constraints to create simplified and more computationally tractable packing constraints. For example, suppose two specific nodes r and s (not assigned to the same unit) are not both allowed to be assigned to channel c because to do so would violate the associated interference constraint. This may be represented as:

$$\begin{aligned} X_r^c + X_s^c \le 1. \end{aligned}$$
(14)

We use Python and the mpmath library [18], which allows the use of arbitrary-precision floating point mathematics, to identify unacceptable pairs of radios and handle the extremely small interference values present in our realistic data sets.

To generalize for larger n-tuples of units above pairs (triplets, quadruplets, etc.), let \(S \subset U\) be a subset of units that cannot all be assigned to the same channel c. We can represent such a restriction of assignments as:

$$\begin{aligned} \sum _{r \in S} X_r^c \le \vert S \vert - 1. \end{aligned}$$
(15)

Preprocessing all such unacceptable combinations and adding them as constraints would effectively replace the cumulative co-channel interference constraints (12). However, identifying all combinations would be computationally prohibitive (as they grow exponentially with both the number of units and available channels) and unnecessary, as many combinations will be redundant and/or represent negligible levels of co-channel interference.

Instead, we dynamically add these higher-order constraints to the formulation only as needed via lazy constraints, which are constraints that are checked for violation whenever an integer solution to the current formulation is found. They are added on an as-needed basis [17]. This approach avoids the problem of very small numbers in CPLEX, as we can process the constraints outside of the solver (e.g., in Python), and then add the much-simplified packing constraints (15) dynamically. Also, since the solver is no longer required to calculate cumulative interference at each radio, the formulation no longer requires the index \(r \in R\). That is, we are now concerned only with the cumulative interference received at each unit. By removing the index \(r \in R\), we reduce the number of decision variables in the problem by an order of magnitude.

After building an initial problem instance with pairwise constraints using Python and Pyomo [15], we send the problem to CPLEX via the Python API and indicate to the solver that we wish to initiate lazy constraint callbacks. Upon finding an integer solution that is feasible with the current constraints, the solver runs our lazy constraint callback code. The code checks the feasibility of the current solution in the full problem, i.e., it checks if the solution satisfies each of the constraints (12). This can be calculated in polynomial time, specifically \(\mathcal {O} \left( |R|^2|C| \right) \). If infeasibility exists, we add the lowest-order constraint (15) to the constraint set to prevent the same units from being assigned the same channel again. CPLEX then continues the search process with these new constraints added into the formulation. The process repeats until optimality is achieved or a time limit is reached.

Table 1. MO-CAP results by time step using pairwise and lazy constraints. “Time” indicates the time at which the displayed solution and optimality gap is obtained, during a total runtime of 9,000 s.
Full size table

Table 1 displays results for each time step in the Marine Corps scenario, including the number of lazy constraints (and the order of the highest-order lazy constraint), and solution results. Each time step is run for 9,000 s, or until optimality is obtained. The times in Table 1 indicate the time when the displayed solution value and optimality gap is obtained; those time steps with a non-zero optimality gap fail to converge within 9,000 s. Our results are obtained using a Dell Mobile Precision 6800 laptop with 32 GB of RAM and an Intel Core i7-4940MX processor running at 3.1 GHz. We use IBM ILOG CPLEX version 12.6.2 and Python 2.7.

The lazy constraint approach to solving the MO-CAP yields results far superior to our previous methods. The solutions are on average 24% lower than the heuristic, and each solution has an associated optimality gap. On seven time steps, optimality is achieved. Even for those for which optimality is not proven, the method finds solutions within one or two channels of optimality.

We next improve on our lazy constraint method by adding the constraints specifying the maximum clique, which is the largest complete sub-graph formed from among the pairwise interference constraints. We use the NetworkX Python library [14] to find the maximum clique, which relies on the algorithm of [5] as adapted by [36]. Let \(M \subset U\) be the subset of units in the maximum clique. The maximum clique constraint takes the form:

$$\begin{aligned} \sum _{u \in M} X_u^c \le 1 \quad \forall c \in C. \end{aligned}$$
(16)

That is, only one unit in the clique may be assigned any given channel. Adding this constraint forces the lower bound up significantly and allows the optimization engine to search in a much smaller feasible region. After we add the maximum clique, we then add all remaining pairwise constraints that are not included in this clique constraint. The lazy constraint method is used again to generate any higher-order interference constraints.

The results of this method are displayed in Table 2, where bolded values indicate an improvement over the previously-described technique. Again, each time step is run for 9,000 s, or until optimality is obtained, and “Time” indicates solver time when the displayed solution value and optimality gap is obtained. Overall, inclusion of the maximum clique reduces average runtime to obtain solutions within one channel of optimality. For the problem associated with time step 3, this method obtains a solution that requires one less channel than that identified without use of the maximum clique. On eight time steps, this method reduces the known optimality gap, and on 12 time steps, the method obtains the provably-optimal solution (five more time steps than the previous method). It is interesting to note that the size of the maximum clique (which itself provides a lower bound on the number of required channels) is within one of the best-known solution for each time step. This is indicative of the power of the maximum clique constraint. We note that there is a clique constraint generator within CPLEX, but this procedure does not find this very strong clique; the overall solution times obtained when the maximum clique constraint is removed and CPLEX clique generator is turned on to aggressive yields results no better than those obtained with default parameters for CPLEX.

We also note that we do not obtain shorter solutions times or better bounds when we provide CPLEX with our feasible solution obtained using our greedy heuristic. This indicates that the solutions found with the heuristic are of little use to CPLEX.

3.4 Constraint Programming Solution Method and Results

We reformulate MO-CAP as a constraint programming (CP) problem in an attempt to quickly find lower bounds to the problem. We use the Optimization Programming Language (OPL) to formulate the problem using integer variables, where each variable \(w_u \in C\) indicates the channel number that unit \(u \in U\) is assigned, and the domain of each variable is equal to the number of available channels |C|. (We originally formulate this problem using binary variables, but find that the CP solver is much less efficient in determining feasibility using binary variables for this particular problem.)

Table 2. MO-CAP results by time step using pairwise and lazy constraints, and a maximum clique constraint. Bold values indicate an improvement over the previous method. “Time” indicates the time at which the displayed solution and optimality gap is obtained, during a total runtime of 9,000 s.
Full size table

We add all pairwise constraints to the problem by indicating that two given units u and v are not allowed to be assigned the same channel, for all pairs \(\left( u,v \right) \in P\). We solve the problem using IBM ILOG CPLEX CP Optimizer [17]. We begin with a small (infeasible) number of available channels |C| (i.e., the domain of each \(w_u \in C\)), and iteratively increase |C| until the solver either determines that the problem is feasible, or it cannot resolve the problem within 12 h. At each |C|, we have a relaxation of the original MO-CAP. If a problem is infeasible with the given number of channels, then we have established that the original MO-CAP (with all constraints) is also infeasible. This indicates that at least \(|C|+1\) channels are required, establishing a MO-CAP lower bound. If the lower bound equals the upper bound (obtained using CPLEX), we have obtained an optimal solution.

Table 3. MO-CAP results by time step using constraint programming. “Optimal solution?” indicates whether the obtained value proves the optimality of a solution, and bolded values indicate new lower bounds (i.e., not found in the previous analyses.
Full size table

The results are displayed in Table 3, where “Infeasible” indicates the largest value at which the solver detects infeasibility, i.e., at least one more channel is required for the problem to be feasible. “Optimal solution?” indicates whether the obtained value proves the optimality of a solution, where bolded values indicate new lower bounds (i.e., not found in the previous analyses). While the solver does not find the exact lower bound at each time step, it does establish two new exact lower bounds (for the problems associated with time steps 13 and 17). When infeasibility is detected by the solver, it is detected extremely quickly (less than a tenth of a second in each case).

On the other hand, the constraint programming procedure was not capable of proving optimality. In general, one can quickly determine that one needs at least k channels (because one can establish that \(k-1\) channels are not feasible). If the CP solver cannot establish whether k channels are infeasible within a few seconds, one is likely to find that the solver will not establish the satisfiability of these constraints within 12 h. In order to improve the solver’s capabilities to prove optimality, we try adding symmetry-breaking constraints (following [34]) but that does not alter the performance result. Next, we try adding all triplet constraints and the known maximum clique constraint (via CP allDifferent constraints), as well as adding constraints iteratively, to no avail.

Thus, we conclude that the CP approach is very efficient at finding infeasibilities (and thus establishing lower bounds), but is incapable of finding feasible solutions close to or at the actual lower bound. We conclude that a very good approach to obtaining optimal or near-optimal solutions to the problem is to integrate CP and IP in a complementary fashion ([16]), where IP is used to search for good solutions and establish upper bounds, and CP is used to quickly tighten lower bounds. Similar techniques have been used for large-scale spectrum auctions [20] and scheduling [30, 37].

4 Minimum-Cost Channel Assignment Problem over Time (MC-CAP-T)

4.1 Problem Formulation

Given the number of channels needed at a moment in time (established using MO-CAP), a spectrum manager may now wish to reduce the total number of times a radio must change channels. Excessive channel changes waste the time of radio operators and require coordination and synchronization among potentially many dispersed units, which may be difficult to achieve in battlefield conditions.

The minimum-cost channel assignment problem over time (MC-CAP-T) aims to minimize the cost incurred by channel changes over time, given the number of channels required at each time step. Let the index \(t\in T\) represent each time step, and let \(g\in G\) (alias h) be a group of units that must be assigned the same channel at a given time step. Groups are obtained at each time step from the MO-CAP. A naïve approach would simply assign channel numbers to the groups as they appear in order. In practice, this produces surprisingly bad solutions as group membership (i.e., the units assigned to each group) may change significantly from time step to time step, and thus an excessively large cost is incurred if one simply dictates that group 1 is always assigned channel 1, etc. We instead use a decomposition approach that takes the solutions from each MO-CAP time step and minimizes the “distance” (i.e., number of channel changes) from one time step to the next. We obtain globally-optimal solutions to this problem in polynomial time using our decomposition approach.

Fig. 2.
figure 2

Example of the association of groups (blue boxes) at each time step. Virtual groups (comprising no units) are represented by dashed boxes. (Color figure online)

Full size image

We wish to associate each group g at time t to a group h at time \(t+1\) at least cost. Let the binary variable \(Y_{gh}^t\) indicate if group g at t is associated with group h at \(t+1\), and let \(\left( g,h,t \right) \in A\) be the arcs representing the set of possible associations between g and h. One could simplify this formulation further by dropping the \(t \in T\) index, but we retain the notation to aid in describing our solution approach. At each time step, each group g at t must be assigned a group h at \(t+1\), and vice versa, which is enforced via the assignment constraints:

$$\begin{aligned} \sum _{h \in G} Y_{gh}^t = 1 \quad&\forall \left( g,\cdot ,t \right) \in A \end{aligned}$$
(17)
$$\begin{aligned} \sum _{g \in G} Y_{gh}^t = 1 \quad&\forall \left( \cdot ,h,t \right) \in A. \end{aligned}$$
(18)

The cost of associating a group g at time t to a group h at time \(t+1\), \(\textit{cost}_{gh}^t\), is a function of the difference in unit membership between g and h. Specifically, if \(\textit{radios}_u\) is the number of radios assigned to unit u,

$$\begin{aligned} \textit{cost}_{gh}^t = \sum _{u\in h \texttt {\textbackslash } g} \textit{radios}_u \quad \forall \left( g,h,t \right) \in A. \end{aligned}$$
(19)

That is, the cost from g to h is the number of radios from units that are in group h but not in group g. This method of calculating costs prevents double-counting when a unit moves from an existing channel to a new channel. Our objective function minimizes the sum total costs of associating each group g at t with group h at \(t+1\):

$$\begin{aligned} \min _Y \sum _{\left( g,h,t \right) \in A} \textit{cost}_{gh}^t Y_{gh}^t. \end{aligned}$$
(20)

Note this cost function assumes all units and radios have the same importance, but that need not be the case: one could associate scalar weights with each radio or to an entire unit to model its relative importance.

4.2 Decomposition Solution Method and Results

To solve the MC-CAP-T, we use a decomposition approach based on the key insight that the actual channel number (or color, or any other label) is arbitrary. We also observe that the cost of changing assignment of a group from t to \(t+1\) depends only on the unit membership of each group at t and \(t+1\); i.e., the costs can be decomposed by time step. These properties allow us to decompose the problem by time step while maintaining global convergence.

Figure 2 provides a visual representation of the process of associating groups at each time step, where for each time step the column of squares on the left represents groups g and on the right groups h. The number of groups (and their unit membership) is determined by the solutions from the MO-CAP, so some time steps may have more or fewer groups than others. For those time steps with fewer groups than the maximum, we create virtual groups (indicated in Fig. 2 by dashed boxes), representing a placeholder group with no assigned units. In this sense, a group represents both a collection of units to be assigned the same channel, and a placeholder for the channel itself, i.e., |G| is equal to the maximum number of available channels across all time steps in the scenario.

At each time step, each group g must be associated with a group h, indicated by gray lines between groups in Fig. 2. When a real group g (i.e., comprising units) is associated with a virtual group h, no cost is incurred because the units in g are assigned to other groups (not in h) at \(t+1\). When a virtual group g is associated with a real group at h, the cost equals the number of radios in h, since, according to (18), each unit in h was previously assigned a different group.

We implement our solution in Python. We first calculate all of the \(\textit{cost}_{gh}^t\) values for each possible \(\left( g,h,t \right) \in A\), and then solve a classic integer assignment problem at each time step using a variation of the Hungarian (or Munkres) algorithm [21], which solves to optimality in \(\mathcal {O} \left( n^3 \right) \) time. Global convergence is maintained because at each time step, the cost of channel changes depends only on the assignments at t and \(t+1\). The actual assigned channel (i.e., its number) is arbitrary, since all channels provide the same performance and each group must have a channel. Thus this formulation exhibits optimal substructure that allows us to efficiently solve each time step to optimality and then combine our results to solve the entire problem to optimality.

Note that in this approach, there is no variable or index representing a particular channel; the association \(Y_{gh}^t\) implies one. After solving the problem, the paths created by associating each g with an h at the next time step represent discrete channels. By assigning a channel number to each of these paths (i.e., the gray lines in Fig. 2), we effectively solve the MC-CAP-T. The following pseudo-code describes our algorithm for solving the problem:

figure a
Fig. 3.
figure 3

Results of MC-CAP-T, where each row represents a unit, and each column represents a time step. White indicates that the channel assignment remains the same (i.e., no cost), and color indicates that a different channel is assigned at the next time step. Red indicates larger units (more radios); green indicates smaller units. (Color figure online)

Full size image

We solve for each time step in the Marine Corps scenario. The naïve method requires a total of 33, 340 channel changes, whereas our decomposition method (which solves to optimality in less than 53 s) requires 21, 915 channel changes, a reduction of 34%. Figure 3 is a method of visualizing the results of this comparison. For both the naïve and decomposition methods, a row represents a unit, where reddish units are larger (comprising up to 25 radios each) and greenish units are smaller, each column represents a time step, and a blank entry indicates that no channel change is required for that unit at that time step. This visualization provides a qualitative sense of how much better the decomposition method (which provides an exact solution) is at reducing channel changes, especially for larger (and thus more penalizing) units.

5 Conclusions and Future Research

We present new integer optimization and constraint programming methodologies that solve large, realistic instances of the minimum-order and minimum-cost channel assignment problems to global or near-global optimality in reasonable amounts of time. Our approach can be used to support military spectrum managers who must quickly make spectrum allocation decisions in congested EM environments. Our ongoing and future research explores robustness and resiliency in the presence of an adversary determined to jam portions of the EM spectrum (see, e.g., [10, 22, 29, 39]).