# Ant Colony Optimization for Social Utility Maximization in  a Multiuser Communication System

Authors: Ming-Hua Lin; Jung-Fa Tsai; Lu-Yao Lee
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

In a multiuser communication system such as cognitive radio or digital subscriber lines, the transmission rate of each user is affected by the channel background noise and the crosstalk interference from other users. This paper presents an efficient ant colony optimization algorithm to allocate each user’s limited power on different channels for maximizing social utility (i.e., the sum of all individual utilities). The proposed algorithm adopts an initial solution that allocates more power on the channel with a lower background noise level. Besides, the cooling concept of simulated annealing is integrated into the proposed method to improve the convergence rate during the local search of the ant colony optimization algorithm. A number of experiments are conducted to validate the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

In a modern communication system such as cognitive radio or digital subscriber lines (DSL), multiple users share the same frequency band and how to mitigate interference is a major design and management concern. The frequency division multiple access (FDMA) mechanism is a standard approach to eliminate interference by dividing the spectrum into multiple tones and preassigning them to the users on a nonoverlapping basis. However, this approach may lead to high system overhead and low bandwidth utilization. Therefore, how to allocate spectrum dynamically to enhance overall system utility in a multiuser communication system has become a topic of intensive research in the signal processing and digital communication community.From the optimization perspective, the study of the dynamic spectrum management problem can be divided into three kinds of categories [1, 2]: noncooperative Nash equilibrium, cooperative social utility maximization, and competitive economy equilibrium. Several approaches were proposed to compute a Nash equilibrium solution such as iterative waterfilling algorithm (IWFA) [3, 4] and linear complementarity problem (LCP) [5]. Some algorithms [6–9] were developed to compute a globally optimal power allocation for the cooperative game. Walras [10] proposed the competitive equilibrium concept which dynamically balances by the supply and demand to model the market operation. Ye [2] proposed a competitive economy equilibrium solution that may achieve both social economic efficiency and individual optimality in dynamic spectrum management. Lin et al. [11] further observed that adjusting budget can meet each user’s physical power demand or balance all individual utilities in a competitive spectrum market. Xie et al. [13] proposed a decentralized tâtonnement process for adjusting the prices to achieve a competitive equilibrium. They showed that competitive equilibrium is the solution of a linear complementarity problem and can be computed efficiently.It is difficult to optimize the overall system utility if only each user’s individual utility is improved. Yu et al. [14] proposed a method which refined the optimal spectrum management with less complexity and generalized the multiuser power management for orthogonal frequency division multiplex systems maximized the overall utility. Due to the nonconvexity of this problem, the CPU time required to solve this problem by the conventional mathematical programming techniques increases greatly as the number of users and channels increases. Luo and Zhang [1] presented a systematic study of the dynamic spectrum management problem, covering two key theoretical aspects: complexity and duality. They have determined the complexity status of the spectrum management problem under various practical settings as well as different choices of system utility functions and have identified subclasses which are polynomial time solvable. They proved that the sum-rate maximization problem is NP-hard even when there are only two users in the system. Ma et al. [15] proposed an efficient scheduling algorithm for concurrent transmissions with power control to maximize the spectrum utilization and thus the network throughput in broadband wireless networks. The original nonconvex problem is converted into a series of convex problems using a two-step approximation. Then a power and channel allocation with fairness algorithm is proposed to solve these problems. Simulation results showed that both network throughput and fairness are improved by their method compared to the previously developed scheduling algorithms.Although the heuristic algorithms cannot guarantee global optimality, they have the advantages of robustness and easy implementation for complex problems. In this paper, we propose an efficient ant colony optimization algorithm to allocate each user’s limited power on different channels for maximizing social utility (i.e., the sum of all individual utilities). In order to improve the solution efficiency, the proposed algorithm adopts an initial solution that allocates more power on the channel with a lower background noise level. Besides, the cooling concept of simulated annealing is integrated into the proposed method to improve the convergence rate during the local search of the ant colony optimization algorithm. A number of experiments are conducted to validate the effectiveness and contribution of the proposed algorithm. Comparing with the simulated annealing approach, computational results indicate that the proposed algorithm spends less CPU time but finds a solution with a higher social utility. Comparing with mathematical programming solver LINGO, the differences in social utility obtained between the proposed algorithm and LINGO are within 0.5% for all cases, and the proposed algorithm obviously decreases CPU time for solving large-scale problems.The rest of this paper is organized as follows. Section2 gives an overview of the problem formulation of the social utility maximization problem as well as ant colony optimization techniques. Section 3 describes the proposed ant colony optimization algorithm. Section 4 presents the extensive experimental results and analysis of the proposed algorithm. Finally, concluding remarks are made in Section 5.


## 2. Background Information

### 2.1. Social Utility Maximization Problem

Consider a communication system consisting ofm users and n channels indicated in Figure 1. Multiple users may use the same channel at the same time and cause interference to each other. Suppose the power allocated by user i at channel j is xij>0, the total power allocated by user i is bounded by the power budget Pi, ∑j=1nxij≤Pi. To evaluate each user’s utility, a commonly recognized utility for user i in communication is the Shannon utility [2, 16]:
(1)ui(xi,x-i)=∑j=1nlog(1+xijσij+∑k≠iakjixkj),
where variable xi=(xi1,xi2,…,xin) is the power allocation of user i on each channel, variables in x-i=(x1,…,xi-1,xi+1,…,xm) are the power units allocated by all other users on each channel, parameter σij denotes the normalized background noise power for user i at channel j, and parameter akji is the normalized crosstalk ratio from user k to user i at channel j. Due to multiuser interference, user i’s utility evaluated by Shannon utility depends on not only its own power allocation on each channel but also those of others. This study aims to maximize the overall system throughput, which is the sum of individual rates in each frequency carrier. Since each user has a fixed transmit power budget Pi, the social utility maximization problem (sum-rate maximization problem) can be formulated as follows:Figure 1
The power allocation problem in a multiuser communication system.Model 1:(2)maximize∑i=1m∑j=1nlog(1+xijσij+∑k≠iakjixkj)subjectto∑j=1nxij≤Pi,i=1,…,m,xij≥0,i=1,…,m,j=1,…,n,
where xij are variables and the other are parameters.Consider a communication system with two channels (f1 and f2) and two users, each of them has a physical power constraint P1=P2=1. Let the Shannon utility function for user 1 be
(3)log(1+x111+x21)+log(1+x124+x22)
and one for user 2 be
(4)log(1+x212+x11)+log(1+x224+x12),
and let the aggregate social utility be the sum of the two individual user utilities. The social utility maximization problem for the above system can be formulated as follows.Model 2:(5)maximizelog(1+x111+x21)+log(1+x124+x22)+log(1+x212+x11)+log(1+x224+x12)subjecttox11+x12≤1,x21+x22≤1,x11,x12,x21,x22≥0.The Nash equilibrium of Model 2 is(x11,x12)=(1,0) and (x21,x22)=(1,0), where the social utility has value 0.3010. However, the solution for maximizing social utility is (x11,x12)=(1,0) and (x21,x22)=(0,1), where the social utility has value 0.3979. This paper aims to find the power allocation for each user to achieve the maximal social utility, that is, the highest system throughput. The above sum-rate maximization problem (Model 1) has been proven to be NP-hard even when only two users are available in the system. In this paper, we propose an efficient ant colony optimization algorithm to allocate each user’s limited power on different channels for maximizing social utility.


### 2.2. Ant Colony Optimization Techniques

Although a wide variety of deterministic optimization techniques are proposed to solve optimization problems, many of these methods have inherent disadvantages because they require continuous evaluation of derivatives and become prohibitively ill conditioned for large-scale problems [17]. Several heuristic methods inspired from physics, biology, and social science have been developed in recent years such as genetic algorithm, simulated annealing, particle swarm optimization, tabu search, neural nets, and ant colony systems. Ant colony optimization (ACO) which simulates the action of ants was first introduced by Dorigo [18]. ACO aims at mimicking the way almost blind ants establish the shortest route from their nests to the food source and back. It was observed that a moving ant deposits some pheromone on the paths they traverse. New ants joining the search, attracted by the pheromone, further reinforce the path. With time, a series of feasible routes are traversed by teams of ants. As the pheromone evaporates, solutions with no substantial travelers will have difficulty in maintaining their pheromone trails and infeasible routes are gradually eliminated [19]. The complete surveys of applications, models, and algorithmic advances for ACO through 2006 are provided by Blum [20], Cordon et al. [21], Dorigo et al. [22], Dorigo and Stützle [23], and Lim et al. [19].The ant colony algorithm was originally used for solving combinatorial optimization problems including the traveling salesman problem. Then it has been applied to other optimization problems such as quadratic assignment, vehicle routing, sequential orderings, job shop scheduling, power system optimization, telecommunication network routing, and logic circuit design [17, 19]. Although ACO has been proven to be one of the best metaheuristics in some combinatorial optimization problems, the application to the real-parameter optimizations appears more challenging, since the pheromone laying method is not straightforward. The algorithms for continuous function optimization were first developed by Bilchev and Parmee [24]. Attention in these works was devoted only on local search processes. Wodrich and Bilchev [25] extended and modified the earlier algorithm to make it an effective global optimization procedure for continuous problem spaces. Later, several approaches [26–31] have been proposed for continuous optimization in recent years. The complete surveys and comparisons of using ACO for continuous cost function optimization can be found in de França et al. [26] and Korošec and Šilc [28].


## 2.1. Social Utility Maximization Problem

Consider a communication system consisting ofm users and n channels indicated in Figure 1. Multiple users may use the same channel at the same time and cause interference to each other. Suppose the power allocated by user i at channel j is xij>0, the total power allocated by user i is bounded by the power budget Pi, ∑j=1nxij≤Pi. To evaluate each user’s utility, a commonly recognized utility for user i in communication is the Shannon utility [2, 16]:
(1)ui(xi,x-i)=∑j=1nlog(1+xijσij+∑k≠iakjixkj),
where variable xi=(xi1,xi2,…,xin) is the power allocation of user i on each channel, variables in x-i=(x1,…,xi-1,xi+1,…,xm) are the power units allocated by all other users on each channel, parameter σij denotes the normalized background noise power for user i at channel j, and parameter akji is the normalized crosstalk ratio from user k to user i at channel j. Due to multiuser interference, user i’s utility evaluated by Shannon utility depends on not only its own power allocation on each channel but also those of others. This study aims to maximize the overall system throughput, which is the sum of individual rates in each frequency carrier. Since each user has a fixed transmit power budget Pi, the social utility maximization problem (sum-rate maximization problem) can be formulated as follows:Figure 1
The power allocation problem in a multiuser communication system.Model 1:(2)maximize∑i=1m∑j=1nlog(1+xijσij+∑k≠iakjixkj)subjectto∑j=1nxij≤Pi,i=1,…,m,xij≥0,i=1,…,m,j=1,…,n,
where xij are variables and the other are parameters.Consider a communication system with two channels (f1 and f2) and two users, each of them has a physical power constraint P1=P2=1. Let the Shannon utility function for user 1 be
(3)log(1+x111+x21)+log(1+x124+x22)
and one for user 2 be
(4)log(1+x212+x11)+log(1+x224+x12),
and let the aggregate social utility be the sum of the two individual user utilities. The social utility maximization problem for the above system can be formulated as follows.Model 2:(5)maximizelog(1+x111+x21)+log(1+x124+x22)+log(1+x212+x11)+log(1+x224+x12)subjecttox11+x12≤1,x21+x22≤1,x11,x12,x21,x22≥0.The Nash equilibrium of Model 2 is(x11,x12)=(1,0) and (x21,x22)=(1,0), where the social utility has value 0.3010. However, the solution for maximizing social utility is (x11,x12)=(1,0) and (x21,x22)=(0,1), where the social utility has value 0.3979. This paper aims to find the power allocation for each user to achieve the maximal social utility, that is, the highest system throughput. The above sum-rate maximization problem (Model 1) has been proven to be NP-hard even when only two users are available in the system. In this paper, we propose an efficient ant colony optimization algorithm to allocate each user’s limited power on different channels for maximizing social utility.


## 2.2. Ant Colony Optimization Techniques

Although a wide variety of deterministic optimization techniques are proposed to solve optimization problems, many of these methods have inherent disadvantages because they require continuous evaluation of derivatives and become prohibitively ill conditioned for large-scale problems [17]. Several heuristic methods inspired from physics, biology, and social science have been developed in recent years such as genetic algorithm, simulated annealing, particle swarm optimization, tabu search, neural nets, and ant colony systems. Ant colony optimization (ACO) which simulates the action of ants was first introduced by Dorigo [18]. ACO aims at mimicking the way almost blind ants establish the shortest route from their nests to the food source and back. It was observed that a moving ant deposits some pheromone on the paths they traverse. New ants joining the search, attracted by the pheromone, further reinforce the path. With time, a series of feasible routes are traversed by teams of ants. As the pheromone evaporates, solutions with no substantial travelers will have difficulty in maintaining their pheromone trails and infeasible routes are gradually eliminated [19]. The complete surveys of applications, models, and algorithmic advances for ACO through 2006 are provided by Blum [20], Cordon et al. [21], Dorigo et al. [22], Dorigo and Stützle [23], and Lim et al. [19].The ant colony algorithm was originally used for solving combinatorial optimization problems including the traveling salesman problem. Then it has been applied to other optimization problems such as quadratic assignment, vehicle routing, sequential orderings, job shop scheduling, power system optimization, telecommunication network routing, and logic circuit design [17, 19]. Although ACO has been proven to be one of the best metaheuristics in some combinatorial optimization problems, the application to the real-parameter optimizations appears more challenging, since the pheromone laying method is not straightforward. The algorithms for continuous function optimization were first developed by Bilchev and Parmee [24]. Attention in these works was devoted only on local search processes. Wodrich and Bilchev [25] extended and modified the earlier algorithm to make it an effective global optimization procedure for continuous problem spaces. Later, several approaches [26–31] have been proposed for continuous optimization in recent years. The complete surveys and comparisons of using ACO for continuous cost function optimization can be found in de França et al. [26] and Korošec and Šilc [28].


## 3. The Proposed Algorithm

This study proposes an efficient ant colony optimization algorithm to allocate each user’s limited power on different channels for maximizing social utility. To improve the solution efficiency, the proposed algorithm uses an initial solution that allocates more power on the channel with a lower background noise. Moreover, the cooling concept of simulated annealing is incorporated into the proposed method to improve the convergence rate during the local search of the ant colony optimization algorithm. The flowchart of the proposed simulated annealing-based ant colony optimization (SAACO) algorithm is shown in Figure2.Figure 2
Flowchart of the proposed SAACO algorithm.Letv be the number of ants in the colony; the location of ant k, k=1,…,v at time t represents a solution Xkt={xk,1t,…,xk,mt} of the social utility maximization problem, where xk,it=(xi1t,xi2t,…,xint) and xijt is the power units allocated by user i at channel j at time t. More detail of the proposed SAACO algorithm in this study is summarized as follows.(1) Initialization. v ants are placed in solution space. According to the Shannon utility function, allocating power on the channel with a lower background noise level contributes more to the user utility. The proposed algorithm considers an initial solution based on the background noise level. One half of ants adopt an initial solution considering background noise level, another half generate the initial solution randomly.(2) Pheromone Updating Rule. Since this study aims to find a solution with maximal social utility (i.e., ∑i=1m∑j=1nlog(1+xij/(σij+∑k≠iakjixkj))), the pheromone laid on each location is set in proportion to the value of social utility. That is, the pheromone level of visited location by ant k at time t, phkt, is updated as follows:
(6)phkt=(1-p)phkt-1+gU(Xkt),
where p is the pheromone evaporation rate, g is a proportional ratio, and U(Xkt) is the social utility of solution Xkt. The ant deposits more pheromone on a location with a higher social utility value. The pheromone level is updated only when a better solution is found.(3) State Transition Rule. After objective function (social utility) evaluation, the best solution (i.e., the highest pheromone) location uncovered by the ants is used to guide the search in subsequent generations. Assume that the ant with the highest social utility deposits the most pheromone at time t, BestPht=maxk{phkt}, on its location, then each ant k on the location with its pheromone level Phkt uses the following state transition rule to determine the next move:
(7)Xkt+1={Xkt+min_step*d,ifw≤G0,(exploitation)Xkt+max_step*d,ifw>G0,(exploration),
where w=(Best Pht-Phkt)/Best Pht, d is a random variable between 0 and 0.5, and min_step, max_step, and G0 are prespecified constants. To facilitate both exploitation and exploration in the proposed method, an ant searches locally when w is found to be lower than or equal to the user-specific threshold G0 and searches globally when w is greater than G0.(4) Solution Adjustment. After an ant uses the transition rule to move next, the solution on next location is verified so that it meets the problem constraint (∑j=1nxij≤Pi). If the problem constraint is violated, the proposed method performs solution adjustment to make the next solution a feasible solution.(i)
Ifxij is not in the domain (x_ij,x-ij), where x_ij and x-ij are lower bound and upper bound of xij, then adjust xij in its range by the following rule:
(8)xij={x-ij,ifxij>x-ij,x_ij,ifxij<x_ij,xij,otherwise.(ii)
If∑j=1nxij>Pi, then randomly select one of the following three conditions for adjusting xij.
(a)
xij are adjusted proportionally such that the total power allocation does not exceed its limitation Pi, that is, xij=(xij/∑j=1nxij)Pi.(b)
Remain the power allocation for the channel with maximal power allocation, and allocatePi-maxj{xij} on a randomly selected channel.(c)
Allocate all power on the channel with the lowest background noise level.(iii)
If∑j=1nxij<Pi, then allocate unused power Pi-∑j=1nxij to the channel that gets the lowest power allocated.(5) Local Search Range Reduction. If there is no improvement in solution quality after a user-defined number of iterations in the searching process, the searching process is stable and the proposed method incorporates the concept of simulated annealing to reduce the local search range from min_step to min_step*Rstep, where Rstep is between 0.8 and 0.99.(6) Stopping Criteria. After min_step is below the user-specific threshold Sq, terminate the searching process.


## 4. Experimental Results and Discussions

In this section, the effectiveness of the proposed SAACO method is validated using experimental data. All experiments are implemented using C++ language under the circumstance of Windows XP on an Intel CPU P4 1.7 G computer with 1 GB memory. In all simulated cases, each user’s power constraintPi=1, the channel background noise level σij are chosen randomly from the interval [1,9], and the normalized crosstalk ratio akji are chosen randomly from the interval [0.1,0.9].


### 4.1. Parameters Settings

Since different parameter settings significantly affect the performance of the proposed SAACO algorithm, a number of experiments are run to determine suitable parameter settings for the algorithm listed in Table1.Table 1
Parameter setting for the proposed SAACO algorithm.
Parameter
Descriptions
Settings
v
Number of ants
10
R
step
Rate to reduce the local search range
0.9
S
q
Threshold of the local search range for stopping criteria
0.01
min_step
Local search range
0.5
max_step
Global search range
1.0
p
The pheromone evaporation rate
0.9
g
Proportional ratio
0.1
G
0
Probability of global search
0.7


### 4.2. Comparison between SAACO and SA

We compare the proposed SAACO approach with the simulated annealing (SA) approach proposed by Lin et al. [12] in the case of m users (m=10,20,30,40) and n channels (n=10,20,30,40,50). Figures 3 and 4 compare social utility and CPU time, respectively, by SAACO and SA. We find that the proposed SAACO algorithm spends less CPU time but obtains better solutions with higher social utilities than the SA approach Lin et al. [12].Figure 3
Comparison of social utility by SAACO and SA Lin et al. [12].Figure 4
Comparison of CPU time by SAACO and SA Lin et al. [12].


### 4.3. Comparison between SAACO and LINGO

In this section, some experiments are conducted to compare the proposed SAACO approach with the optimization software LINGO [32]. First we consider small-scale problems of m users (m=10,20) and n channels (n=10,20,30,40,50). Ten problems are randomly generated for each group. Table 2 compares average performance of the proposed SAACO approach and LINGO. To compare SAACO and LINGO more clearly, we normalize the data and plot it in Figures 5 and 6. In Figure 5, we observe that the difference between social utility by LINGO and by SAACO is between +0.5% and −0.2%. Besides, the proposed SAACO approach uses less CPU time than LINGO in obtaining an optimal solution when 20 users and over 20 channels exist in the communication system.Table 2
Comparisons of CPU time and social utility between the proposed SAACO approach and LINGO.
Test case (m,n)*
LINGO
SAACO
Difference
Social utility
CPU time (seconds)
Social utility
CPU time (seconds)
Difference_s+
Difference_t++
(
10,10
)
2.422536
1.0
2.418003
1.214600
-
0.001871
0.214600
(
10,20
)
3.027710
4.0
3.029383
4.901600
0.000553
0.225400
(
10,30
)
3.454207
10.5
3.448223
15.805900
-
0.001732
0.505324
(
10,40
)
3.665038
21.2
3.660824
22.857000
-
0.001150
0.078160
(
10,50
)
3.737554
31.3
3.7343727
36.64825
-
0.000851
0.171994
(
20,10
)
3.981162
5.6
3.998787
7.241300
0.004427
0.293089
(
20,20
)
5.575991
30.9
5.60343
26.974900
0.004921
-
0.127026
(
20,30
)
6.447189
88.9
6.440597
79.355200
-
0.001023
-
0.107366
(
20,40
)
6.942952
215.7
6.943312
190.842300
0.000052
-
0.115242
(
20,50
)
7.265195
375.3
7.250848
347.890200
-
0.001975
-
0.073034
*(m,n) = (number of users, number of channels).
+Difference_s = (social utility by SAACO-social utility by LINGO)/social utility by LINGO.
++Difference_t = (CPU time by SAACO-CPU time by LINGO)/CPU time by LINGO.Figure 5
Comparison of social utility by SAACO and LINGO.Figure 6
Comparison of CPU time by SAACO and LINGO.To demonstrate effectiveness of the proposed method in large-scale problems, we compare the proposed SAACO approach with LINGO in the cases ofm users (m=10,20) and n channels (n=100,128,256). Three problems are randomly generated for each group. Table 3 compares average performance of SAACO and LINGO measured by the resulting social utility and the required CPU time. To compare SAACO and LINGO more clearly, we normalize the data and plot it in Figures 7 and 8. Figure 8 indicates that the proposed SAACO algorithm performs better than LINGO in CPU time as the number of users and channels increases. Compared with LINGO, the proposed SAACO approach uses roughly 50% of CPU time to obtain the solution in the case of 20 users and 256 channels. Although the required CPU time by the proposed SAACO approach is much less than LINGO, the proposed SAACO approach can get a better social utility or an approximate social utility not less than 1 percent from the solution reported by LINGO as indicated in Figure 7.Table 3
Comparisons of CPU time and social utility between the proposed SAACO approach and LINGO in large scale problem.
Test case (m,n)*
LINGO
SAACO
Differrence
Sociall utility
CPU time (seconds)
Sociall utility
CPU time (seconds)
Difference_s+
Difference_t++
(
10,100
)
4.064655
238.333
4.054523
238.439
-
0.00249
0.00044
(
10,128
)
4.122419
563.667
4.107250
362.911
-
0.00368
-
0.55318
(
10,256
)
4.162954
3906.667
4.217743
2835.007
0.01316
-
0.37801
(
20,100
)
7.911308
3224.000
7.888093
1608.873
-
0.00293
-
1.00389
(
20,128
)
8.061679
4807.000
8.031333
3144.747
-
0.00376
-
0.52858
(
20,256
)
8.372676
45587.000
8.354917
21984.100
-
0.00212
-
1.07364
*(m,n) = (number of users, number of channels).
+Difference_s = (social utility by SAACO-social utility by LINGO)/social utility by LINGO.
++Difference_t = (CPU time by SAACO-CPU time by LINGO)/CPU time by LINGO.Figure 7
Comparison of social utility by SAACO and LINGO in large-scale problems.Figure 8
Comparison of CPU time by SAACO and LINGO in large-scale problems.


## 4.1. Parameters Settings

Since different parameter settings significantly affect the performance of the proposed SAACO algorithm, a number of experiments are run to determine suitable parameter settings for the algorithm listed in Table1.Table 1
Parameter setting for the proposed SAACO algorithm.
Parameter
Descriptions
Settings
v
Number of ants
10
R
step
Rate to reduce the local search range
0.9
S
q
Threshold of the local search range for stopping criteria
0.01
min_step
Local search range
0.5
max_step
Global search range
1.0
p
The pheromone evaporation rate
0.9
g
Proportional ratio
0.1
G
0
Probability of global search
0.7


## 4.2. Comparison between SAACO and SA

We compare the proposed SAACO approach with the simulated annealing (SA) approach proposed by Lin et al. [12] in the case of m users (m=10,20,30,40) and n channels (n=10,20,30,40,50). Figures 3 and 4 compare social utility and CPU time, respectively, by SAACO and SA. We find that the proposed SAACO algorithm spends less CPU time but obtains better solutions with higher social utilities than the SA approach Lin et al. [12].Figure 3
Comparison of social utility by SAACO and SA Lin et al. [12].Figure 4
Comparison of CPU time by SAACO and SA Lin et al. [12].


## 4.3. Comparison between SAACO and LINGO

In this section, some experiments are conducted to compare the proposed SAACO approach with the optimization software LINGO [32]. First we consider small-scale problems of m users (m=10,20) and n channels (n=10,20,30,40,50). Ten problems are randomly generated for each group. Table 2 compares average performance of the proposed SAACO approach and LINGO. To compare SAACO and LINGO more clearly, we normalize the data and plot it in Figures 5 and 6. In Figure 5, we observe that the difference between social utility by LINGO and by SAACO is between +0.5% and −0.2%. Besides, the proposed SAACO approach uses less CPU time than LINGO in obtaining an optimal solution when 20 users and over 20 channels exist in the communication system.Table 2
Comparisons of CPU time and social utility between the proposed SAACO approach and LINGO.
Test case (m,n)*
LINGO
SAACO
Difference
Social utility
CPU time (seconds)
Social utility
CPU time (seconds)
Difference_s+
Difference_t++
(
10,10
)
2.422536
1.0
2.418003
1.214600
-
0.001871
0.214600
(
10,20
)
3.027710
4.0
3.029383
4.901600
0.000553
0.225400
(
10,30
)
3.454207
10.5
3.448223
15.805900
-
0.001732
0.505324
(
10,40
)
3.665038
21.2
3.660824
22.857000
-
0.001150
0.078160
(
10,50
)
3.737554
31.3
3.7343727
36.64825
-
0.000851
0.171994
(
20,10
)
3.981162
5.6
3.998787
7.241300
0.004427
0.293089
(
20,20
)
5.575991
30.9
5.60343
26.974900
0.004921
-
0.127026
(
20,30
)
6.447189
88.9
6.440597
79.355200
-
0.001023
-
0.107366
(
20,40
)
6.942952
215.7
6.943312
190.842300
0.000052
-
0.115242
(
20,50
)
7.265195
375.3
7.250848
347.890200
-
0.001975
-
0.073034
*(m,n) = (number of users, number of channels).
+Difference_s = (social utility by SAACO-social utility by LINGO)/social utility by LINGO.
++Difference_t = (CPU time by SAACO-CPU time by LINGO)/CPU time by LINGO.Figure 5
Comparison of social utility by SAACO and LINGO.Figure 6
Comparison of CPU time by SAACO and LINGO.To demonstrate effectiveness of the proposed method in large-scale problems, we compare the proposed SAACO approach with LINGO in the cases ofm users (m=10,20) and n channels (n=100,128,256). Three problems are randomly generated for each group. Table 3 compares average performance of SAACO and LINGO measured by the resulting social utility and the required CPU time. To compare SAACO and LINGO more clearly, we normalize the data and plot it in Figures 7 and 8. Figure 8 indicates that the proposed SAACO algorithm performs better than LINGO in CPU time as the number of users and channels increases. Compared with LINGO, the proposed SAACO approach uses roughly 50% of CPU time to obtain the solution in the case of 20 users and 256 channels. Although the required CPU time by the proposed SAACO approach is much less than LINGO, the proposed SAACO approach can get a better social utility or an approximate social utility not less than 1 percent from the solution reported by LINGO as indicated in Figure 7.Table 3
Comparisons of CPU time and social utility between the proposed SAACO approach and LINGO in large scale problem.
Test case (m,n)*
LINGO
SAACO
Differrence
Sociall utility
CPU time (seconds)
Sociall utility
CPU time (seconds)
Difference_s+
Difference_t++
(
10,100
)
4.064655
238.333
4.054523
238.439
-
0.00249
0.00044
(
10,128
)
4.122419
563.667
4.107250
362.911
-
0.00368
-
0.55318
(
10,256
)
4.162954
3906.667
4.217743
2835.007
0.01316
-
0.37801
(
20,100
)
7.911308
3224.000
7.888093
1608.873
-
0.00293
-
1.00389
(
20,128
)
8.061679
4807.000
8.031333
3144.747
-
0.00376
-
0.52858
(
20,256
)
8.372676
45587.000
8.354917
21984.100
-
0.00212
-
1.07364
*(m,n) = (number of users, number of channels).
+Difference_s = (social utility by SAACO-social utility by LINGO)/social utility by LINGO.
++Difference_t = (CPU time by SAACO-CPU time by LINGO)/CPU time by LINGO.Figure 7
Comparison of social utility by SAACO and LINGO in large-scale problems.Figure 8
Comparison of CPU time by SAACO and LINGO in large-scale problems.


## 5. Conclusions

With the rapid development of wireless networks and devices, the demand for spectrum resource is increasingly growing. Therefore, how to allocate spectrum dynamically to enhance total system throughput in a multiuser communication system has become an important issue in recent years. Due to the nonconvexity of this problem, the CPU time required to solve this problem by the conventional mathematical programming techniques increases greatly as the number of channel and user increases. This paper proposes an efficient ant colony algorithm for allocating spectrum to maximize social utility. Computational results show that the proposed algorithm significantly outperforms the simulated annealing approach in solution efficiency and solution quality in most cases. Comparing with the mathematical programming solver LINGO in solving large-scale problems, the proposed SAACO algorithm spends much less CPU time obtaining an approximate social utility close to the social utility reported from LINGO.



---

*Source: 798631-2013-07-24.xml*