Due to the paramount importance of (wireless) communication systems and computer networks, in the last decade both resource allocation (RA) and anomaly detection (AD) problems addressed herein have been intensively studied and numerous solutions have been proposed in the specialized literature [1]. The RA specially in wireless multiple access networks and the AD in computer networks are problems of complex nature and an engineering compromise solution has much appeal in terms of practical and effective deployment.

Resource allocation problems in wireless communication networks include power consumption minimization, information rate and network capacity maximization, battery lifetime maximization, energy-efficient and bandwidth-efficient optimal design among others. In computer networks, anomaly detection system (ADS) consists of a set of techniques aiming to detect anomalies in network operation, helping the administrator to decide which action need to be performed in each situation. Anomaly detection is not an easy task and brings together a range of techniques in several areas, such as machine learning, signal processing techniques based on specification techniques, and data mining among others. Generally, for most scenarios of practical interest, these optimization formulations result in non-convex problems, which is hard to solve or even impossible using conventional convex optimization techniques, even after imposing relaxations to deal with RA problems.

In this sense, heuristics have been widely used to solve problems that deterministic optimization methods result in high computational complexity and therefore have no application in real systems. In this context, the ant colony optimization (ACO) algorithm [2] developed in recent years has attracted a lot of interest from so many professionals due

Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. © 2013 Sampaio et al.; licensee InTech. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. © 2013 Sampaio et al., licensee InTech. This is a paper distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

©2012 Marques et al., licensee InTech. This is an open access chapter distributed under the terms of the

to its robustness and great performance in deal with discrete (combinatorial) and continuous optimization problems.

**2. Resource Allocation in Wireless Multiple Access Networks**

resources in a simple1 and optimized manner is pretty important.

recently done we enumerate some notorious in the next section.

**2.1. Related Work**

networks.

as a weighted SNIR's productory.

1 Here, simple is used as a synonym for low computational complexity.

The optimized resource allocation in wireless multiple access networks, specially the power rate allocation, is a problem of great interest for telecommunications enterprises and users. It is well known that spectrum and power are valuable resources due to their scarcity, the first one is a natural non renewable resource and the second one is limited by the battery and device size. Therefore, proposing new techniques and algorithms that can allocate this

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

http://dx.doi.org/10.5772/53338

111

In the last few decades many researchers have been working on this subject aiming to find a simple yet sturdy algorithm for resource allocation in wireless systems. Among many works

Among numerous solutions proposed to resource allocation in wireless multiple access networks we enumerate herein some of great importance works: Foschini and Miljanic [4] distributed power control algorithm (DPCA) stands as the main one. When it comes to metaheuristics, in [5] and [6] a genetic algorithm approach was used to propose the genetic algorithm for mobiles equilibrium, providing the joint power-rate control in CDMA multiple access networks. In [7], the particle swarm optimization (PSO) metaheuristic was used in order to establish a low-complexity power control algorithm. Finally, in [8] a power allocation approach was proposed to solve the parallel interference cancelation in multi-user detectors. Beyond the metaheuristic approaches, the work developed in [9] exploits an algorithm based on the dynamic cost assignment for downlink power allocation in CDMA networks. Besides, [10] addressed the uplink fairness maximization in a CDMA system with multiple processing gains. In [11], the Verhulst population model, firstly developed to describe the biological species growth with restrictions of space and food, was adapted to the distributed power control problem in a DS/CDMA network. It is noteworthy that this work was the first one to propose a Verhulst model adaptation to resource allocation problems in multiple access

Furthermore, in [12] an analytical approach was proposed for the weighted throughput maximization (WTM) problem, namely MAPEL. The algorithm performs the power control in the interference limited wireless networks, i.e., CDMA and MC/CDMA networks, through a monotonically increasing objective function that is not necessarily convex. This function was formulated as a multiplicative linear fractional programming (MLFP) problem, which is a special case of generalized linear fractional programming (GLFP). So, the GLFP problem presented in [12] was used in [13] in order to formulate a non-decreasing objective function

Finally, this section presents a heuristic approach through ant colony optimization in the continuous domains (ACO**R**) applicable to the power and rate allocation problems [13], and is organized as follows: subsection 2.2 describes aspects of the DS/CDMA networks and the power control problem on subsection 2.3 the power control problem and the cost function used with the ACO algorithm are presented; subsection 2.4 deals with the throughput maximization problem and how the ACO algorithm can be applied to solve this optimization

An important challenge for the future wireless communication systems has been how to acquire higher throughput with lower power consumption. Hence, in order to transfer the exponentially rising amount of available data to the user in an acceptable time, following the "Moore's Law", according to which both the processing power of CPUs and the capacity of mass storage devices doubles approximately every 18 months, the transmission rate in cellular network has been risen at the speed of nearly 10 times every 5 years. Meanwhile, the price paid for this enormous growth in data rates and market penetration is a rising power requirement of information and communication technologies (ICT) – although at a substantially lower speed than "Moore's Law" – the energy consumption doubles every 4-5 years [3].

In order to avoid the collapsing of communication systems and networks resources, an increasing interest and intensive researches in both energy and bandwidth efficient designs have mobilized enormous efforts of research's groups around the globe in the last decade. Against this background, the conventional efficient design of wireless networks mainly focuses on system capacity and spectral efficiency (SE). However, energy-efficient design in wireless networks is of paramount importance and is becoming an inevitable trend, since the deployment of multimedia wireless services and requirement of ubiquitous access have increased rapidly, and as a consequence, energy consumption at both the base station and mobile terminals side have experienced enormous increasing.

In order to achieve high throughput with low total transmit power, system resources such as spectrum (subcarriers, bandwidth), transmit power (energy, battery lifetime) and information rate (QoS requirements) in different multiple access wireless communication systems should be efficiently and appropriately allocated to the different active users. The first part of this chapter is dedicated to deal with the energy-efficient and spectral-efficient designs in DS/CDMA wireless communication systems through the appropriate heuristic optimization of energy and information rate resources.

The Internet has brought to our daily life easy and new ways to execute tasks as searching and gathering information, to communicate and spread ideas and others small gestures that are changing our lives. In order to prevent possible failures and loss of performance, the infrastructure providing theses services must be monitored, which unavoidably increases the responsibility and charge of the network administrator. The administrator is assisted by tools such as firewall, proxy, among others, including the anomaly detection system to help prevent abnormal network operation. Usually the anomaly behavior is a sudden increase or decrease into the network traffic. It can be caused by a simple programming error in some software to hardware failure, among many other causes that affect directly the network operation.

In the next sections of this Chapter the ACO methodology will be applied and analyzed regarding two distinct application of communication scenarios: the resource allocation in a direct sequence code division multiple access (DS/CDMA) systems, which is developed in Section 2 and the anomaly detection in computer networks is discussed in the Section 3. The conclusion remarks for both ACO-communication application problems are offered in Section 4.

## **2. Resource Allocation in Wireless Multiple Access Networks**

The optimized resource allocation in wireless multiple access networks, specially the power rate allocation, is a problem of great interest for telecommunications enterprises and users. It is well known that spectrum and power are valuable resources due to their scarcity, the first one is a natural non renewable resource and the second one is limited by the battery and device size. Therefore, proposing new techniques and algorithms that can allocate this resources in a simple1 and optimized manner is pretty important.

In the last few decades many researchers have been working on this subject aiming to find a simple yet sturdy algorithm for resource allocation in wireless systems. Among many works recently done we enumerate some notorious in the next section.

## **2.1. Related Work**

2 Search Algorithms

years [3].

operation.

Section 4.

optimization problems.

to its robustness and great performance in deal with discrete (combinatorial) and continuous

An important challenge for the future wireless communication systems has been how to acquire higher throughput with lower power consumption. Hence, in order to transfer the exponentially rising amount of available data to the user in an acceptable time, following the "Moore's Law", according to which both the processing power of CPUs and the capacity of mass storage devices doubles approximately every 18 months, the transmission rate in cellular network has been risen at the speed of nearly 10 times every 5 years. Meanwhile, the price paid for this enormous growth in data rates and market penetration is a rising power requirement of information and communication technologies (ICT) – although at a substantially lower speed than "Moore's Law" – the energy consumption doubles every 4-5

In order to avoid the collapsing of communication systems and networks resources, an increasing interest and intensive researches in both energy and bandwidth efficient designs have mobilized enormous efforts of research's groups around the globe in the last decade. Against this background, the conventional efficient design of wireless networks mainly focuses on system capacity and spectral efficiency (SE). However, energy-efficient design in wireless networks is of paramount importance and is becoming an inevitable trend, since the deployment of multimedia wireless services and requirement of ubiquitous access have increased rapidly, and as a consequence, energy consumption at both the base station and

In order to achieve high throughput with low total transmit power, system resources such as spectrum (subcarriers, bandwidth), transmit power (energy, battery lifetime) and information rate (QoS requirements) in different multiple access wireless communication systems should be efficiently and appropriately allocated to the different active users. The first part of this chapter is dedicated to deal with the energy-efficient and spectral-efficient designs in DS/CDMA wireless communication systems through the appropriate heuristic optimization

The Internet has brought to our daily life easy and new ways to execute tasks as searching and gathering information, to communicate and spread ideas and others small gestures that are changing our lives. In order to prevent possible failures and loss of performance, the infrastructure providing theses services must be monitored, which unavoidably increases the responsibility and charge of the network administrator. The administrator is assisted by tools such as firewall, proxy, among others, including the anomaly detection system to help prevent abnormal network operation. Usually the anomaly behavior is a sudden increase or decrease into the network traffic. It can be caused by a simple programming error in some software to hardware failure, among many other causes that affect directly the network

In the next sections of this Chapter the ACO methodology will be applied and analyzed regarding two distinct application of communication scenarios: the resource allocation in a direct sequence code division multiple access (DS/CDMA) systems, which is developed in Section 2 and the anomaly detection in computer networks is discussed in the Section 3. The conclusion remarks for both ACO-communication application problems are offered in

mobile terminals side have experienced enormous increasing.

of energy and information rate resources.

Among numerous solutions proposed to resource allocation in wireless multiple access networks we enumerate herein some of great importance works: Foschini and Miljanic [4] distributed power control algorithm (DPCA) stands as the main one. When it comes to metaheuristics, in [5] and [6] a genetic algorithm approach was used to propose the genetic algorithm for mobiles equilibrium, providing the joint power-rate control in CDMA multiple access networks. In [7], the particle swarm optimization (PSO) metaheuristic was used in order to establish a low-complexity power control algorithm. Finally, in [8] a power allocation approach was proposed to solve the parallel interference cancelation in multi-user detectors.

Beyond the metaheuristic approaches, the work developed in [9] exploits an algorithm based on the dynamic cost assignment for downlink power allocation in CDMA networks. Besides, [10] addressed the uplink fairness maximization in a CDMA system with multiple processing gains. In [11], the Verhulst population model, firstly developed to describe the biological species growth with restrictions of space and food, was adapted to the distributed power control problem in a DS/CDMA network. It is noteworthy that this work was the first one to propose a Verhulst model adaptation to resource allocation problems in multiple access networks.

Furthermore, in [12] an analytical approach was proposed for the weighted throughput maximization (WTM) problem, namely MAPEL. The algorithm performs the power control in the interference limited wireless networks, i.e., CDMA and MC/CDMA networks, through a monotonically increasing objective function that is not necessarily convex. This function was formulated as a multiplicative linear fractional programming (MLFP) problem, which is a special case of generalized linear fractional programming (GLFP). So, the GLFP problem presented in [12] was used in [13] in order to formulate a non-decreasing objective function as a weighted SNIR's productory.

Finally, this section presents a heuristic approach through ant colony optimization in the continuous domains (ACO**R**) applicable to the power and rate allocation problems [13], and is organized as follows: subsection 2.2 describes aspects of the DS/CDMA networks and the power control problem on subsection 2.3 the power control problem and the cost function used with the ACO algorithm are presented; subsection 2.4 deals with the throughput maximization problem and how the ACO algorithm can be applied to solve this optimization

1 Here, simple is used as a synonym for low computational complexity.

problem, while in subsection 2.5 the ACO algorithm itself is described. Finally, subsection 2.6 introduces the simulations scenarios, the numerical results and conclusions for the first part of this chapter.

#### **2.2. Resource Allocation in DS/CDMA Networks**

In DS/CDMA multirate networks, the Bit Error Rate (BER) is usually used as a QoS metric, since it is directly related to the Signal to Noise plus Interference Ratio (SNIR). Thus, the SNIR is associated to the Carrier to Interference Ratio as follows:

$$
\gamma\_{\dot{i}} = \frac{r\_c}{r\_{\dot{i}}} \times \Gamma\_{\dot{i}\prime} \qquad \qquad \dot{\imath} = 1, \ldots, \dot{\jmath}L \tag{1}
$$

Additionally, the theoretical Shannon channel capacity is defined as [15]:

[1]:

level.

can be defined as [1]:

where *BER* is the desired bit error rate (BER).

**2.3. Power Allocation Problem**

relation must be calculated as [16]:

QoS) that is acceptable to each user.

capacity model using the gap introduced in Eq (8):

respectively, and *γ*∗

be mathematically stated as:

where *C* is the channel capacity in *bits*/*s* and *γ* is the SNIR. It is worthy to note that since this is a theoretical bound a gap can be included, thus, the Shannon equation can be rewritten as

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

where *θ* is the gap between the theoretical bound and the real information rate. Usually, *θ*

The power control objective is to find the minimal transmission power for each user that satisfy its QoS requirement, usually a minimum transmission rate. Since user rate is related to the user SNIR one may use it as a QoS measure. Thus, the power allocation problem may

min **p** = [*p*1, *p*2,..., *pU*]

0 ≤ *pi* ≤ *p*max

In order to enable the users to have minimum QoS warranty, the minimum CIR to SNIR

*i rc*

where Γ*i*,min and *Ri*,min are the minimum CIR and minimum information rate of each user,

This way, the minimum information rate can be mapped in the SNIR through the Shannon's

*i* is the minimum SNIR needed in order to obtain a minimum BER (or

s.t. *γi* ≥ *γ*∗

where *pi* and *γi* is the *i*th user power and SNIR, respectively, and *γ*∗

Γ*i*,min = *ri*,min*γ*∗

*θ* = − 1.5

*C* = *W* log(1 + *γ*) (6)

http://dx.doi.org/10.5772/53338

113

*C* = *W* log(1 + *θγ*) (7)

log(5*BER*) (8)

*i* (9)

, *i* = 1, ..., *U* (10)

*i* is the desired SNIR

where *γi* is the *i*-th user's SNIR, *rc* is the chip rate, *ri* is the *i*-th user's information rate, *U* is the system load and Γ*i* is the *i*-th user's CIR defined as [11], [14]:

$$\Gamma\_{i} = \frac{p\_{i}|g\_{ii}|^{2}}{\sum\_{j=1, i \neq j}^{II} p\_{j}|g\_{ij}|^{2} + \sigma^{2}}, i = 1, \dots, II \tag{2}$$

where *pi* is the *i*-th user's power bounded by *pmax*, *U* the number of active users on the system, |*gii*| the channel gain of the *i*-th user, |*gij*| is the interfering signals gain and *σ*2 the Additive White Gaussian Noise (AWGN) at the *i*-th receiver's input.

$$\mathbf{G}\_{\text{upl}} = \begin{bmatrix} \\$11 & \\$12 & \cdots & \\$1u \\ \\$21 & \\$22 & \cdots & \\$2u \\ \vdots & \vdots & \ddots & \vdots \\ \\$u & \\$u 2 & \cdots & \\$uu \end{bmatrix} \tag{3}$$

where the main diagonal (*gii*) shows the *i*-th user's channel attenuation, while the other values shows the interfering signals gain.

The path loss is inversely proportional to the distance between the mobile unit and the base station; the shadowing is obtained by a log-normal probability distribution random variable, and the multipath fading obtained assuming a Rayleigh probability distribution for cases without line of sight (LOS), and Rice distribution for cases with LOS.

In the DS/CDMA networks with multiple processing gains (MPG), where each user has a different processing gain *Fi* > 1, it is defined as a function of the chip rate:

$$F\_{\bar{l}} = \frac{r\_c}{r\_{\bar{l}}}, \qquad \bar{l} = 1, 2, \dots, \mathcal{U} \tag{4}$$

Therefore, from Eq. (1) and (4) follows:

$$
\gamma\_{\bar{\imath}} = F\_{\bar{\imath}} \times \Gamma\_{\bar{\imath}} \tag{5}
$$

Additionally, the theoretical Shannon channel capacity is defined as [15]:

$$\mathbb{C} = W \log(1 + \gamma) \tag{6}$$

where *C* is the channel capacity in *bits*/*s* and *γ* is the SNIR. It is worthy to note that since this is a theoretical bound a gap can be included, thus, the Shannon equation can be rewritten as [1]:

$$C = W \log(1 + \theta \gamma) \tag{7}$$

where *θ* is the gap between the theoretical bound and the real information rate. Usually, *θ* can be defined as [1]:

$$\theta = -\frac{1.5}{\log(5BER)}\tag{8}$$

where *BER* is the desired bit error rate (BER).

#### **2.3. Power Allocation Problem**

4 Search Algorithms

part of this chapter.

**2.2. Resource Allocation in DS/CDMA Networks**

SNIR is associated to the Carrier to Interference Ratio as follows:

*γi* = *rc ri*

the system load and Γ*i* is the *i*-th user's CIR defined as [11], [14]:

Γ*i* = *pi*|*gii*|

∑*U*

Additive White Gaussian Noise (AWGN) at the *i*-th receiver's input.

**G**upl =

without line of sight (LOS), and Rice distribution for cases with LOS.

*Fi* = *rc ri*

different processing gain *Fi* > 1, it is defined as a function of the chip rate:

values shows the interfering signals gain.

Therefore, from Eq. (1) and (4) follows:

. . . . . . ... . . .

where the main diagonal (*gii*) shows the *i*-th user's channel attenuation, while the other

The path loss is inversely proportional to the distance between the mobile unit and the base station; the shadowing is obtained by a log-normal probability distribution random variable, and the multipath fading obtained assuming a Rayleigh probability distribution for cases

In the DS/CDMA networks with multiple processing gains (MPG), where each user has a

problem, while in subsection 2.5 the ACO algorithm itself is described. Finally, subsection 2.6 introduces the simulations scenarios, the numerical results and conclusions for the first

In DS/CDMA multirate networks, the Bit Error Rate (BER) is usually used as a QoS metric, since it is directly related to the Signal to Noise plus Interference Ratio (SNIR). Thus, the

where *γi* is the *i*-th user's SNIR, *rc* is the chip rate, *ri* is the *i*-th user's information rate, *U* is

2

where *pi* is the *i*-th user's power bounded by *pmax*, *U* the number of active users on the system, |*gii*| the channel gain of the *i*-th user, |*gij*| is the interfering signals gain and *σ*2 the

> *g*11 *g*12 ... *g*1*U g*21 *g*22 ... *g*2*U*

*gU*1 *gU*2 ... *gUU*

× Γ*i*, *i* = 1, . . . , *U* (1)

*j*=1,*i*�=*j pj*|*gij*|2 + *σ*2 , *i* = 1, ..., *U* (2)

, *i* = 1, 2, . . . , *U* (4)

*γi* = *Fi* × Γ*i* (5)

(3)

  The power control objective is to find the minimal transmission power for each user that satisfy its QoS requirement, usually a minimum transmission rate. Since user rate is related to the user SNIR one may use it as a QoS measure. Thus, the power allocation problem may be mathematically stated as:

$$\begin{aligned} \text{minim} \quad & \mathbf{p} = [p\_1, p\_2, \dots, p\_U] \\ \text{s.t.} \quad & \gamma\_i \ge \gamma\_i^\* \\ & 0 \le p\_i \le p\_{\text{max}} \end{aligned} \tag{9}$$

where *pi* and *γi* is the *i*th user power and SNIR, respectively, and *γ*∗ *i* is the desired SNIR level.

In order to enable the users to have minimum QoS warranty, the minimum CIR to SNIR relation must be calculated as [16]:

$$\Gamma\_{i,\min} = \frac{r\_{i,\min} \gamma\_i^\*}{r\_c}, \quad i = 1, \ldots, U \tag{10}$$

where Γ*i*,min and *Ri*,min are the minimum CIR and minimum information rate of each user, respectively, and *γ*∗ *i* is the minimum SNIR needed in order to obtain a minimum BER (or QoS) that is acceptable to each user.

This way, the minimum information rate can be mapped in the SNIR through the Shannon's capacity model using the gap introduced in Eq (8):

$$\mathcal{D}^{\frac{\gamma}{\gamma\_i}} = \max \left[ 1 + \theta\_i \gamma\_i \right] \\ = \max \left[ 1 + \frac{\theta\_i F\_{\bar{l}} \cdot p\_{\bar{i}} |g\_{\bar{i}\bar{l}}|^2}{\sum\_{i \neq j}^{\mathcal{U}} p\_j |g\_{\bar{i}j}|^2 + \sigma^2} \right] \tag{11}$$

where 2 *ri rc* is the normalized information rate for the *i*-th user, *θi* is the inverse of the gap between the channel's theoretical capacity and the real information rate. Note that for the minimum SNIR *γ*∗ *i* , Eq. 11 uses the minimum information rate established by the system, in order to guarantee QoS. Such that one obtain the condition needed for the minimum SNIR to be satisfied, given a minimum information rate:

$$\gamma\_i^\* = \frac{\mathfrak{D}^{r\_{i,\text{min}}} - 1}{\theta\_i} \tag{12}$$

function for power control problem in CDMA systems using genetic algorithms has been proposed. This function was later modified and used with swarm intelligence in [1] to solve the power control problem. Due to the good results obtained in [1] that cost function was

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

*i* =

The increasing information traffic demand due to multimedia services on third generation networks (3G) and beyond, along with the need of telecommunications companies to improve their profits have motivated development on weighted throughput maximization (WTM)

0 ≤ *pi* ≤ *p*max

where *f*(**p**) is a cost function that describes the behaviour of information rate of each user regarding the allocated transmit power vector **p**; *ri* is the *i*-th user's information rate, *ri*,min the minimum rate needed to ensure QoS for user *i*, **p** is the power vector such that **p** = [*p*1, *p*2,..., *pU*], and *p*max is the maximum transmission power allowed in the system.

Therefore, we must incorporate the multirate criterion to the WTM problem subject to maximum power allowed per user. From this, the optimization problem is formulated as a special case of *generalized linear fractional programming* (GLFP) [18]. This way, the second RA

*vi*

where 2*ri*,min is the minimum information rate normalized by the bandwidth of the system (*rc*) of the *i*-th link, including null rate restrictions; *vi* > 0 is the priority of the *i*-th user to

*hi*(**p**) ≥ 2*ri*,min , ∀*i* = 1, . . . , *U*

problem, which aims to maximize the system throughput, been formulated as:

max*r f*(**p**) s.t. *ri* ≥ *ri*,min , ∀*i* = 1, 2, . . . , *U*

http://dx.doi.org/10.5772/53338

115

(18)

(19)

0 ≤ *pi* ≤ *p*max (17)

*i* 0, otherwise

1, *γi* ≥ *γ*∗

used with the ACO algorithm and reproduced hereafter for convenience:

**F**th *i* · 1 − *pi p*max

*U* ∑ *i*=1

1 *U*

*i*

**2.4. Weighted Throughput Maximization (WTM) Problem**

*ri* = *ri*,min

*J*1(**p**) = max

where the threshold function is defined as **F**th

problem can be described as follows:

*J*2(**p**) = max

*U* ∏ *i*=1  *fi*(**p**) *hi*(**p**)

s.t. 0 < *pi* ≤ *pi*,max, *fi*(**p**)

s.t. *γi* ≥ *γ*∗

Consider the QoS normalized interference matrix **B** [1]:

$$B\_{ij} = \begin{cases} 0, & i = j; \\ \frac{\Gamma\_{l, \text{min} \mathcal{G} \mid l}}{\mathcal{G}^{\mu}}, & \text{otherwise.} \end{cases} \tag{13}$$

which Γ*i*,min can be obtained as follows:

$$
\Gamma\_{i, \text{min}} = \frac{r\_{i, \text{min}} \gamma\_i^\*}{r\_c}, \quad i = 1, \dots, U \tag{14}
$$

Now consider the information rate requirements for each user and the QoS normalized noise vector *u* = [*u*1, *u*2,..., *uk*] *T*, with elements:

$$
\mu\_i = \frac{\Gamma\_{i,\text{min}} \sigma\_i^2}{\mathcal{g}\_{ii}} \tag{15}
$$

The solution to the power control problem may be analytically obtained solving the following linear system:

$$\mathbf{p}^\* = (\mathbf{I} - \mathbf{B})^{-1}\mathbf{u} \tag{16}$$

where *IU*×*U* is the identity matrix. Note that that (**I** − **B**) is invertible only, and only if the maximum eigenvalue of *B* is smaller than one [17]. Only in this case, the power control problem will present a feasible solution. Nevertheless, due to the limited resources of mobile terminals, the use of this method is not feasible since its computational cost grows prohibitively when the number of users goes beyond some dozens due to a matrix inversion operation. Besides a totally distributed allocation scheme cannot be deployed using this analytical solution. To overcome this issues, this work proposes a metaheuristic approach for the optimum power-rate allocation problems.

In order to use the ACO algorithm to solve the power allocation problem one must map the problem objective into a mathematical function so-called cost function. In [5, 6] a new cost function for power control problem in CDMA systems using genetic algorithms has been proposed. This function was later modified and used with swarm intelligence in [1] to solve the power control problem. Due to the good results obtained in [1] that cost function was used with the ACO algorithm and reproduced hereafter for convenience:

$$J\_1(\mathbf{p}) = \max \, \frac{1}{U} \sum\_{i=1}^{U} \mathbb{F}\_i^{\mathbf{th}} \cdot \left(1 - \frac{p\_i}{p\_{\max}}\right), \qquad \forall i = 1, 2, \dots, U$$

$$\begin{array}{ll} \text{s.t.} & \gamma\_i \ge \gamma\_i^\* \\ & 0 \le p\_i \le p\_{\max} \\ & r\_i = r\_{i,\min} \end{array} \tag{17}$$

where the threshold function is defined as **F**th *i* = 1, *γi* ≥ *γ*∗ *i* 0, otherwise

6 Search Algorithms

where 2 *ri*

minimum SNIR *γ*∗

2 *ri*

which Γ*i*,min can be obtained as follows:

the optimum power-rate allocation problems.

vector *u* = [*u*1, *u*2,..., *uk*]

linear system:

to be satisfied, given a minimum information rate:

Consider the QoS normalized interference matrix **B** [1]:

*rc* = max [1 + *θiγi*] = max

*γ*∗

Γ*i*,min = *ri*,min*γ*∗

*Bij* =

*T*, with elements:

 1 +

*rc* is the normalized information rate for the *i*-th user, *θi* is the inverse of the gap

between the channel's theoretical capacity and the real information rate. Note that for the

order to guarantee QoS. Such that one obtain the condition needed for the minimum SNIR

*i* = 2*ri*,min − 1 *θi*

 0, *i* = *j*; Γ*i*,min *gji*

> *i rc*

Now consider the information rate requirements for each user and the QoS normalized noise

*ui* = Γ*i*,min*σ*2

The solution to the power control problem may be analytically obtained solving the following

where *IU*×*U* is the identity matrix. Note that that (**I** − **B**) is invertible only, and only if the maximum eigenvalue of *B* is smaller than one [17]. Only in this case, the power control problem will present a feasible solution. Nevertheless, due to the limited resources of mobile terminals, the use of this method is not feasible since its computational cost grows prohibitively when the number of users goes beyond some dozens due to a matrix inversion operation. Besides a totally distributed allocation scheme cannot be deployed using this analytical solution. To overcome this issues, this work proposes a metaheuristic approach for

In order to use the ACO algorithm to solve the power allocation problem one must map the problem objective into a mathematical function so-called cost function. In [5, 6] a new cost

*i gii*

*θiFi* · *pi*|*gii*|

*i*�=*j pj*|*gij*|2 + *σ*2

∑*U*

*i* , Eq. 11 uses the minimum information rate established by the system, in

2

*gii* , otherwise. (13)

, *i* = 1, ..., *U* (14)

**p**∗ = (**I** − **B**)−1**u** (16)

(11)

(12)

(15)

## **2.4. Weighted Throughput Maximization (WTM) Problem**

The increasing information traffic demand due to multimedia services on third generation networks (3G) and beyond, along with the need of telecommunications companies to improve their profits have motivated development on weighted throughput maximization (WTM) problem, which aims to maximize the system throughput, been formulated as:

$$\begin{aligned} \max\_{r} & \quad f(\mathbf{p})\\ \text{s.t.} & \quad r\_{i} \ge r\_{i,\min} \\ & \quad 0 \le p\_{i} \le p\_{\max} \end{aligned} \tag{18}$$

where *f*(**p**) is a cost function that describes the behaviour of information rate of each user regarding the allocated transmit power vector **p**; *ri* is the *i*-th user's information rate, *ri*,min the minimum rate needed to ensure QoS for user *i*, **p** is the power vector such that **p** = [*p*1, *p*2,..., *pU*], and *p*max is the maximum transmission power allowed in the system.

Therefore, we must incorporate the multirate criterion to the WTM problem subject to maximum power allowed per user. From this, the optimization problem is formulated as a special case of *generalized linear fractional programming* (GLFP) [18]. This way, the second RA problem can be described as follows:

$$\begin{aligned} \underline{f\_2}(\mathbf{p}) = \max \quad & \prod\_{i=1}^{U} \left[ \frac{f\_i(\mathbf{p})}{h\_i(\mathbf{p})} \right]^{v\_i} \\ \text{s.t.} \quad & 0
 0 is the priority of the *i*-th user to transmit with satisfied QoS requirements, assumed normalized, such that ∑*U i*=1 *vi* = 1. It is noteworthy that the second restriction in Eq. (19) is easily obtained from Eqs. (11) and (12), where the minimum information rate given can be transformed in the minimum SNIR through the Shannon capacity equation, considering a maximum tolerable BER for each user or service class. Hence, functions *fi*(**p**) and *hi*(**p**) can be readily defined as:

*Gi* (*x*) =

1, *µi*

Gaussian PDFs (*gi*

*l*

2,..., *µi*

input parameters is sketched in Fig. 1.

layer (in depth) shows the solution file in each iteration from *n* = 1 to *N*.

(*x*)) in the *i*-th kernel (*Gi*

µ*i* = [*µi*

set, |ω| = |µ*i*

*Fs* ∑ *l*=1 *ωlgi l* (*x*) =

*Fs* ∑ *l*=1 *ωl*

1 *σi l* √2*π*

*Fs*] is the vector of means and σ*i* = [*σi*

exp

where *i* is the Gaussian kernel indexer, with *U* being the number of dimensions of the problem; ω = [*ω*1, *ω*2,..., *ωFs*] is the weight vector associated to each Gaussian in the kernel;

deviations. Hence, the cardinality of both vectors is equal to the number of Gaussians in the

For discrete combinatorial optimization problems, the pheromone informations are kept in a table. This is not possible when we need to deal with continuous problems, since there are an infinite number of points to keep, and as a consequence, an infinite ways to evolve. Thus, a solution file is deployed, where the *l*th solution *sl*, ∀*l* = 1, 2, . . . , *Fs*, in the *i*th dimension, ∀*i* = 1, . . . , *U*, is kept on the memory file at the *n*th iteration, as well as the respective cost function values *f*(*sl*). A schematic grid to understand the file format and the associate ACO

**Figure 1.** File structure for the ACO algorithm's solutions. Each line of the *Fs* × *U* matrix represents one solution for the problem of dimension *U*; each column represents one dimension, which, in turn, is sampled by each Gaussian kernel. Cost function vector **J** = [*J*(*s*1),..., *J*(*sl*),..., *J*(*sFs*)], dimension *Fs* × 1, represents the solution for the *n*-th iteration. Finally, each

The found solutions are used to generate PDFs dynamically, through a method based on the stored solutions. The vectors µ*i* and σ*i* at *i*th dimension and ω common for all dimensions are calculated through the solutions of the file at each algorithm iteration; so, the Gaussian

The solutions file must store *Fs* solutions. Note that this number is equal to the number of

kernel will have one Gaussian PDF sampling each *i*-th variable of each solution. Herein, the

). Thus, one can conclude that the *i*-th Gaussian

kernel can be built, and guide the ants throughout the dimensions of the problem.

−(*x* − *µi l* )2

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

2*σi*2 *l*

1, *σi*

2,..., *σi*

, *i* = 1, . . . , *U* (22)

http://dx.doi.org/10.5772/53338

117

*Fs*] is the vector of standard

$$h\_{l}(\mathbf{p}) = \sum\_{j \neq i}^{\mathcal{U}} p\_{j} |g\_{ij}|^{2} + \sigma^{2} \qquad \text{and} \qquad f\_{l}(\mathbf{p}) = \theta F\_{l} \cdot p\_{l} |g\_{il}|^{2} + h\_{l}(\mathbf{p}), \qquad \forall i = 1, \ldots, \mathcal{U}. \tag{20}$$

Note that the Eq. (19) is the productory of linear fractional exponentiated functions, and the function ∏*U i*=1(*zi*)*vi* is an increasing function in a nonnegative real domain [12]. Based on these properties, problem (19) can be properly rewritten as:

$$\begin{aligned} f\_2(\mathbf{p}) &= \max \sum\_{i=1}^{U} v\_i [\log\_2 f\_i(\mathbf{p}) - \log\_2 h\_i(\mathbf{p})] \ &= \max \sum\_{i=1}^{U} v\_i [\bar{f}\_i(\mathbf{p}) - \bar{h}\_i(\mathbf{p})] \\ \text{s.t.} \quad &0 < p\_i \le p\_{i,\text{max}} \\ &\bar{f}\_i(\mathbf{p}) - \bar{h}\_i(\mathbf{p}) \ge r\_{i,\text{min}} \quad \forall i = 1, \dots, U \end{aligned} \tag{21}$$

This way, the cost function turns into a sum of logarithms, which results in a monotonic nondecreasing function. With no loss of generality, in this work *vi* = *U*−1, ∀*i*, has been adopted.

## **2.5. The ACOR Metaheuristic**

The ACO**R** is a continuous-valued metaheuristic based on the ants behavior when looking for food. Note that it was first proposed for combinatorial optimization problems. In its discrete version, each ant walks through the points of the input set and deposits pheromone on its edges. The next point selection is done probabilistically, considering the amount of pheromone on each edge, jointly with the heuristic information available in the current algorithm iteration.

Given a set of points next to an ant, the probability of each of this points to be chosen forms a probability mass function (PMF). The main idea of the continuous version ACO**R** is the adaptation of this PMF to a Probability Density Function (PDF), allowing each ant to sample a continuous PDF instead of dealing with discrete sampling points. This is due to the fact that the continuous domain has infinite points to be chosen.

The PDF used in this work is Gaussian given its soft capacity in generating random numbers, and due to the fact that it has only one maximum point located at the mean of the process. Nevertheless, this last feature is not useful when the search space has more than one feasible region. To overcome this problem, the ACO**R** uses a Gaussian kernel pdf (a weighted sum of Gaussians) to sample each dimension of the problem. Each Gaussian kernel is defined as follows [19]:

$$\mathcal{G}^{i}(\mathbf{x}) = \sum\_{l=1}^{\text{Fs}} \omega\_{l} \eta\_{l}^{i}(\mathbf{x}) = \sum\_{l=1}^{\text{Fs}} \omega\_{l} \frac{1}{\sigma\_{l}^{i} \sqrt{2\pi}} \exp\left[-\frac{(\mathbf{x} - \mu\_{l}^{i})^{2}}{2\sigma\_{l}^{i}}\right], \qquad i = 1, \dots, \mathsf{U} \tag{22}$$

where *i* is the Gaussian kernel indexer, with *U* being the number of dimensions of the problem; ω = [*ω*1, *ω*2,..., *ωFs*] is the weight vector associated to each Gaussian in the kernel; µ*i* = [*µi* 1, *µi* 2,..., *µi Fs*] is the vector of means and σ*i* = [*σi* 1, *σi* 2,..., *σi Fs*] is the vector of standard deviations. Hence, the cardinality of both vectors is equal to the number of Gaussians in the set, |ω| = |µ*i* | = |σ*i* | = *Fs*.

8 Search Algorithms

*hi*(**p**) =

function ∏*U*

adopted.

algorithm iteration.

follows [19]:

*U* ∑ *j*�=*i*

*pj*|*gij*|

*J*2(**p**) = max

− *f i*

**2.5. The ACOR Metaheuristic**

transmit with satisfied QoS requirements, assumed normalized, such that ∑*U*

or service class. Hence, functions *fi*(**p**) and *hi*(**p**) can be readily defined as:

2 + *σ*2 and *fi*(**p**) = *θFi* · *pi*|*gii*|

these properties, problem (19) can be properly rewritten as:

that the continuous domain has infinite points to be chosen.

*U* ∑ *i*=1

(**p**) − −

is noteworthy that the second restriction in Eq. (19) is easily obtained from Eqs. (11) and (12), where the minimum information rate given can be transformed in the minimum SNIR through the Shannon capacity equation, considering a maximum tolerable BER for each user

Note that the Eq. (19) is the productory of linear fractional exponentiated functions, and the

*vi*[log2 *fi*(**p**) − log2 *hi*(**p**)] = max

This way, the cost function turns into a sum of logarithms, which results in a monotonic nondecreasing function. With no loss of generality, in this work *vi* = *U*−1, ∀*i*, has been

The ACO**R** is a continuous-valued metaheuristic based on the ants behavior when looking for food. Note that it was first proposed for combinatorial optimization problems. In its discrete version, each ant walks through the points of the input set and deposits pheromone on its edges. The next point selection is done probabilistically, considering the amount of pheromone on each edge, jointly with the heuristic information available in the current

Given a set of points next to an ant, the probability of each of this points to be chosen forms a probability mass function (PMF). The main idea of the continuous version ACO**R** is the adaptation of this PMF to a Probability Density Function (PDF), allowing each ant to sample a continuous PDF instead of dealing with discrete sampling points. This is due to the fact

The PDF used in this work is Gaussian given its soft capacity in generating random numbers, and due to the fact that it has only one maximum point located at the mean of the process. Nevertheless, this last feature is not useful when the search space has more than one feasible region. To overcome this problem, the ACO**R** uses a Gaussian kernel pdf (a weighted sum of Gaussians) to sample each dimension of the problem. Each Gaussian kernel is defined as

*hi*(**p**) ≥ *ri*,min, ∀*i* = 1, . . . , *U*

*i*=1(*zi*)*vi* is an increasing function in a nonnegative real domain [12]. Based on

s.t. 0 < *pi* ≤ *pi*,max, (21)

*U* ∑ *i*=1 *vi*[ − *f i* *i*=1 *vi* = 1. It

2 + *hi*(**p**), ∀*i* = 1, . . . , *U*. (20)

(**p**) − −

*hi*(**p**)]

For discrete combinatorial optimization problems, the pheromone informations are kept in a table. This is not possible when we need to deal with continuous problems, since there are an infinite number of points to keep, and as a consequence, an infinite ways to evolve. Thus, a solution file is deployed, where the *l*th solution *sl*, ∀*l* = 1, 2, . . . , *Fs*, in the *i*th dimension, ∀*i* = 1, . . . , *U*, is kept on the memory file at the *n*th iteration, as well as the respective cost function values *f*(*sl*). A schematic grid to understand the file format and the associate ACO input parameters is sketched in Fig. 1.

**Figure 1.** File structure for the ACO algorithm's solutions. Each line of the *Fs* × *U* matrix represents one solution for the problem of dimension *U*; each column represents one dimension, which, in turn, is sampled by each Gaussian kernel. Cost function vector **J** = [*J*(*s*1),..., *J*(*sl*),..., *J*(*sFs*)], dimension *Fs* × 1, represents the solution for the *n*-th iteration. Finally, each layer (in depth) shows the solution file in each iteration from *n* = 1 to *N*.

The found solutions are used to generate PDFs dynamically, through a method based on the stored solutions. The vectors µ*i* and σ*i* at *i*th dimension and ω common for all dimensions are calculated through the solutions of the file at each algorithm iteration; so, the Gaussian kernel can be built, and guide the ants throughout the dimensions of the problem.

The solutions file must store *Fs* solutions. Note that this number is equal to the number of Gaussian PDFs (*gi l* (*x*)) in the *i*-th kernel (*Gi* ). Thus, one can conclude that the *i*-th Gaussian kernel will have one Gaussian PDF sampling each *i*-th variable of each solution. Herein, the greater the value of *Fs*, the greater will be the number of Gaussian PDFs on the algorithm. Therefore, the parameter *Fs* leads to the complexity of the set.

(more diversity), at the cost of lower convergence speed. Thus, the ACO**R**'s *q* parameter corresponds to the best-so-far solution and iteration-best solution concepts. So, Eq. (23) gives rise to an important equilibrium between *q* and *Fs* parameters, making their individual calibration sensitive to each one, in order to achieve a good tradeoff among robustness and

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

Furthermore, the suitable choice for the population size *m* plays an important role in order to improve the robustness-speed tradeoff in conjunction with the best attainable *q* · *Fs* calibration. Note that *m* might be overloaded in order to increase the algorithm capacities, at the undesirable cost of greater computational complexity. Finally, the algorithm robustness R can be thought as the ratio between the number of convergence success S to the total

T · 100 [%] @*N* iterations

and the speed as the average number of iterations needed to the algorithm achieves

Next, important steps of the ACO algorithm are briefly discussed, such as general ACO algorithm structure, the σ*i* vector computation, as well as the sampling process; the last one will be presented directly on the algorithm structure. The algorithm organization common to various implemented versions of continuous ACO is described in Algorithm 1, in which

• *AntBasedSolutionConstruction()*: Through the decision variables of each solution *si*

1, . . . , *U*, each ant builds the solution by *U* steps. Since ACO**R** uses a Gaussian mixture in each problem dimension (Eq. (22)), and that the number of Gaussians on the mixture is equal to the size *Fs* of the solutions file, we conclude that at each step *i* we will have a

this work, the vector ω will not be used, and the explanation for that is given in the next

In practice, the sample process is made on three stages: First, the elements of ω vector must be calculated, where should be noted that the solutions ranking parameter *l* will never change, independently of the change of the solutions order on the file. On the second stage, each ant must choose a solution of the file aiming to sample it, and the probability of this choose must be relative to the normalization of each solution weight

*l* , *i* =

, σ*i* and ω must be updated. In

http://dx.doi.org/10.5772/53338

119

convergence velocity for each specific optimization problem.

R = S

the functions performed inside are briefly described in following.

number of process realizations T :

**Algorithm 1** Overview of ACO

*PheromoneUpdate() DaemonActions()*

different sample of *Gi*

for the sum of all weights:

**end while**

paragraph.

**while** *The end conditions aren't met* **do** *AntBasedSolutionConstruction()*

.

In order to sample the Gaussian kernel, the vectors µ*i*

convergence in T trials for a given problem.

A detailed description for the evolution of the ACO solution structure is given in the following. From Fig. 1, note that for an *U*-dimensional problem, the file solution stores *Fs* different solutions, the values of its *U* variables and the results of each solution applied to the cost function. So, *si l* is the value of the *i*-th variable of the *l*-th solution of the file, and *J*(*sl*) is the result of the *l*-th solution applied to the cost function. For each dimension *i* = 1, . . . , *U* of the problem (in this case, each column of the table), there is a different Gaussian Kernel PDF (*Gi* ) defined. So, for each *Gi* , the values of the *i*-th variable of all solutions becomes the elements of the mean vector, µ*i* = [*µi* 1,..., *µi Fs*]=[*si* 1,...,*si Fs*], i.e., the *l*-th value of dimension *i* is the mean of the *l*-th gaussian of *Gi* .

Furthermore, the number of ants (or particles) *m* is another important input parameter of the ACO algorithm to be adjusted. The ants are responsible for the sampling of *Gi* , and thus, for the algorithm evolution as well. In that way, on each iteration, each ant chooses one solution of the file probabilistically, through a method based on the weight vector ω. Since the ant has chosen one solution of the file, the next step consists of sampling through the Gaussian kernel. After that, a new solution is generated and attached to the end of the file. As the last ant finishes its sampling, the solution file is sorted based on the value entries in the cost function matrix **J** = [*J*(*s*1),..., *J*(*sl*),..., *J*(*sFs*)]. Hence, for both problems treated in Eq. (17) and (21), the matrix **J** must be sorted decreasingly, i.e., *J*(*s*1) ≥ *J*(*s*2) ≥ ... ≥ *J*(*sFs*).

When the sorting process is completed, a number of worst solutions ordered at the end of the file is discarded, in which is done equal to the number of solutions added on the sampling process. Note that since each ant samples only one solution on each iteration, the number of solutions to be discarded is equal to the number of ants.

At this point, a Gaussian kernel (*Gi* ) is defined for each dimension of the problem, which the *l*-th variable becomes an element of the µ*i* vector. Thus, considering the *Gi* defined on the *i*-th dimension, The weight *wl* of each solution is calculated as follows:

$$\omega\_{l} = \frac{1}{q \text{F} s \sqrt{2\pi}} \exp\left[-\frac{(l-1)^{2}}{2q^{2} \text{F} s^{2}}\right], \qquad l = 1, \ldots, \text{F}s \tag{23}$$

The weight of the *l*-th solution can be seen as the probability of a solution to be chosen and sampled by an ant. Hence, the *l*-th solution's rank in the file, also is the input parameter in Eq. (23), which is a Gaussian PDF with mean 1 and standard deviation *q* · *Fs*, where *q* is an input parameter of the ACO algorithm. The *q* parameter can be interpreted as a diversification parameter, where low values of *q* enhances the convergence speed of the algorithm; on the other hand, high values entries for *q* enhances the process robustness. This is due to the fact that, on the normal function for the *l*-th solution's weight calculation in Eq. (23), the higher the standard deviation values are, more chances to select solutions that are not so near to the mean of the process, which, in turn, is the first solution of the file. So, when the standard deviation *q* · *Fs* assumes small values, only the best and a few solutions of the file will be sampled, enabling the algorithm to converge faster. On the other hand, when high-valued standard deviations are admitted, the probability of the file solutions to be chosen becomes more uniform, which makes the algorithm search in a larger space (more diversity), at the cost of lower convergence speed. Thus, the ACO**R**'s *q* parameter corresponds to the best-so-far solution and iteration-best solution concepts. So, Eq. (23) gives rise to an important equilibrium between *q* and *Fs* parameters, making their individual calibration sensitive to each one, in order to achieve a good tradeoff among robustness and convergence velocity for each specific optimization problem.

10 Search Algorithms

PDF (*Gi*

the cost function. So, *si*

) defined. So, for each *Gi*

elements of the mean vector, µ*i* = [*µi*

At this point, a Gaussian kernel (*Gi*

*i* is the mean of the *l*-th gaussian of *Gi*

greater the value of *Fs*, the greater will be the number of Gaussian PDFs on the algorithm.

A detailed description for the evolution of the ACO solution structure is given in the following. From Fig. 1, note that for an *U*-dimensional problem, the file solution stores *Fs* different solutions, the values of its *U* variables and the results of each solution applied to

is the result of the *l*-th solution applied to the cost function. For each dimension *i* = 1, . . . , *U* of the problem (in this case, each column of the table), there is a different Gaussian Kernel

*Fs*]=[*si*

Furthermore, the number of ants (or particles) *m* is another important input parameter of the

the algorithm evolution as well. In that way, on each iteration, each ant chooses one solution of the file probabilistically, through a method based on the weight vector ω. Since the ant has chosen one solution of the file, the next step consists of sampling through the Gaussian kernel. After that, a new solution is generated and attached to the end of the file. As the last ant finishes its sampling, the solution file is sorted based on the value entries in the cost function matrix **J** = [*J*(*s*1),..., *J*(*sl*),..., *J*(*sFs*)]. Hence, for both problems treated in Eq. (17)

When the sorting process is completed, a number of worst solutions ordered at the end of the file is discarded, in which is done equal to the number of solutions added on the sampling process. Note that since each ant samples only one solution on each iteration, the number of

*l*-th variable becomes an element of the µ*i* vector. Thus, considering the *Gi* defined on the

−(*l* − 1)2 2*q*2*Fs*2

The weight of the *l*-th solution can be seen as the probability of a solution to be chosen and sampled by an ant. Hence, the *l*-th solution's rank in the file, also is the input parameter in Eq. (23), which is a Gaussian PDF with mean 1 and standard deviation *q* · *Fs*, where *q* is an input parameter of the ACO algorithm. The *q* parameter can be interpreted as a diversification parameter, where low values of *q* enhances the convergence speed of the algorithm; on the other hand, high values entries for *q* enhances the process robustness. This is due to the fact that, on the normal function for the *l*-th solution's weight calculation in Eq. (23), the higher the standard deviation values are, more chances to select solutions that are not so near to the mean of the process, which, in turn, is the first solution of the file. So, when the standard deviation *q* · *Fs* assumes small values, only the best and a few solutions of the file will be sampled, enabling the algorithm to converge faster. On the other hand, when high-valued standard deviations are admitted, the probability of the file solutions to be chosen becomes more uniform, which makes the algorithm search in a larger space

1,..., *µi*

.

ACO algorithm to be adjusted. The ants are responsible for the sampling of *Gi*

and (21), the matrix **J** must be sorted decreasingly, i.e., *J*(*s*1) ≥ *J*(*s*2) ≥ ... ≥ *J*(*sFs*).

solutions to be discarded is equal to the number of ants.

*ωl* = 1

*qFs*√2*π*

*i*-th dimension, The weight *wl* of each solution is calculated as follows:

exp

*l* is the value of the *i*-th variable of the *l*-th solution of the file, and *J*(*sl*)

1,...,*si*

, the values of the *i*-th variable of all solutions becomes the

) is defined for each dimension of the problem, which the

, *l* = 1, . . . , *Fs* (23)

*Fs*], i.e., the *l*-th value of dimension

, and thus, for

Therefore, the parameter *Fs* leads to the complexity of the set.

Furthermore, the suitable choice for the population size *m* plays an important role in order to improve the robustness-speed tradeoff in conjunction with the best attainable *q* · *Fs* calibration. Note that *m* might be overloaded in order to increase the algorithm capacities, at the undesirable cost of greater computational complexity. Finally, the algorithm robustness R can be thought as the ratio between the number of convergence success S to the total number of process realizations T :

> R = S T · 100 [%] @*N* iterations

and the speed as the average number of iterations needed to the algorithm achieves convergence in T trials for a given problem.

Next, important steps of the ACO algorithm are briefly discussed, such as general ACO algorithm structure, the σ*i* vector computation, as well as the sampling process; the last one will be presented directly on the algorithm structure. The algorithm organization common to various implemented versions of continuous ACO is described in Algorithm 1, in which the functions performed inside are briefly described in following.

• *AntBasedSolutionConstruction()*: Through the decision variables of each solution *si l* , *i* = 1, . . . , *U*, each ant builds the solution by *U* steps. Since ACO**R** uses a Gaussian mixture in each problem dimension (Eq. (22)), and that the number of Gaussians on the mixture is equal to the size *Fs* of the solutions file, we conclude that at each step *i* we will have a different sample of *Gi* .

In order to sample the Gaussian kernel, the vectors µ*i* , σ*i* and ω must be updated. In this work, the vector ω will not be used, and the explanation for that is given in the next paragraph.

In practice, the sample process is made on three stages: First, the elements of ω vector must be calculated, where should be noted that the solutions ranking parameter *l* will never change, independently of the change of the solutions order on the file. On the second stage, each ant must choose a solution of the file aiming to sample it, and the probability of this choose must be relative to the normalization of each solution weight for the sum of all weights:

$$p\_l = \omega\_l \cdot \left(\sum\_{r=1}^{k} \omega\_r\right)^{-1} \tag{24}$$

• *DaemonActions()*: This is the optional component of ACO**R** that can be used to implement centralized actions of the algorithm that aren't accessible for the ants. In this stage, the found solution must be updated and returned as the final solution. Besides, it is possible to implement local search methods here, but this aspect is not exploited in this current

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

This subsection is divided in two parts. The first one deals with ACO typical performance and its input parameters optimization; the second part numerical simulations results for both power and rate allocation problems are presented and the NMSE is compared with the

The simulations were carried out in the MatLab 7.0 platform and the scenario parameters are presented on Table 1. We assumed a rectangular cell with one base station in the center and users uniformly spread across all the cell extension. We considered that all mobile terminals

rate, and (∆*t*)*c* is the coherence time of the channel2. This is part of the SNIR estimation process, which means that the channel is constant in each optimization window, assumed herein equal to 667*µs*. Thus, the ACO algorithm must converge to the solution within each

Simulation experiments were carried out in order to determine the suitable values for the ACO input parameters for each problem, such as file size (*Fs*), pheromone evaporation coefficient (*ξ*), population (*m*) and the diversity parameter (*q*). The best parameters combination was chosen considering the solutions quality measured by the normalized mean

where **p** is the solution found through the ACO algorithm, **p**∗ the analytical (optimal) solution and **E** the mathematical expectation operator. In order to find the best parameters

A typical convergence behavior for the RA-ACO under equal-rate power control problem is shown in Fig. 2. At a first glance, power allocation for *U* = 5 users (lightly loading system) is performed by a) RA-ACO algorithm, b) RA-PSO algorithm from [1]. One can

2 Corresponds to the time interval in which the channel characteristics do not suffer expressive variations.

NMSE = **E**

slot is the time slot duration, *R*slot is the transmitted power vector update

*T*slot < (∆*t*)*c* (26)

http://dx.doi.org/10.5772/53338

121

(27)

experience slow fading channels, i.e. the following relation is always satisfied:

work, since we look firstly for low computational complexity.

**2.6. Numerical Results**

RA-PSO algorithm.

where *T*slot = *R*−1

667*µs* interval.

*2.6.1. RA-ACO Input Parameters Optimization*

for both problems non-exhaustive tests were conducted.

squared error (NMSE), defined as:

that is, the probability of each solution being chosen can be thought as a random number generator of normal distribution, with mean 1 and standard deviation *q* × *Fs*, since the choose probability of each rank will never change. Adopting this strategy, the *ω* vector as well as the first stage of the sampling process will no longer be needed.

Thus, since the ant chosen its solution, it must be sampled stepwise using a normal random number generator. The chosen solution must be sampled dimensionally (*gi l* , *i* = 1, . . . , *U*), causing each Gaussian mixture's parameters to be seen only in one dimension a time, smoothing the calculation of the pattern deviation and allowing linear transformations on the problem without result changes.

Therefore, let *sl* (Fig. 1) to be the solution chosen by an ant during the ACO's evolution process. It is known that the ant will sample *sl* dimensionally, as well as that the sampling is done through a Gaussian function parametrized by the *µi l* and *σi l* values. Thus, the *σi l* is calculated for dimension *i* as follows:

$$
\sigma\_l^i = \xi \sum\_{\varepsilon=1}^k \frac{|s\_\varepsilon^i - s\_l^i|}{k-1} \tag{25}
$$

Herein, the *σi l* value for *si l* is the mean distance from *si l* to the other values of dimension *i* in the other solutions of the file. The process is repeated until the last dimension of the file is reached. This way, the higher the variability of the different solutions, higher will be the standard deviation value *σi l* . Note that the *ξ* ∈ [0, 1] parameter aims to reduce the standard deviation, working as a learning factor. Since the *σi l* value is calculated, the ant will sample the Gaussian PDF *gi l* (*µi l* , *σi l*).

The parameter *ξ* is the same for all dimensions of all solutions, and corresponds to the pheromone evaporation rate, or to the inverse of the learning rate. This way, when *ξ* is low valued the algorithm speed is enhanced, and when it is high-valued, its robustness is enhanced. It is noteworthy that the algorithm converges when *σ* → 0 throughout all dimensions of the file.

• *PheromoneUpdate()*: The ACO**R** algorithm updates its pheromone informations as follows: At the beginning of the algorithm, the file is initialized with *Fs* solutions uniformly random distributed. From this, the pheromone updating is done adding the new solutions generated by the ants, as well as removing the same number of worst solutions.

Finally, the size of the solutions file is a parameter of the algorithm, and must not be smaller than the number of dimensions of the problem if it is enabled to handle variable correlation, and to support linear transformations on the problem being optimized. Nevertheless, these techniques are not used in this work. Furthermore, the size of the file leads to the algorithm diversity, since a big file will cover a greater region of the search space than the small one, enabling the algorithm to overcome local optima, but on the other hand, a small file will make the algorithm to be faster than the big one.

• *DaemonActions()*: This is the optional component of ACO**R** that can be used to implement centralized actions of the algorithm that aren't accessible for the ants. In this stage, the found solution must be updated and returned as the final solution. Besides, it is possible to implement local search methods here, but this aspect is not exploited in this current work, since we look firstly for low computational complexity.

## **2.6. Numerical Results**

12 Search Algorithms

(*gi l*

Herein, the *σi*

*pl* = *ωl* ·

well as the first stage of the sampling process will no longer be needed.

*σi l* = *ξ*

*l*

standard deviation, working as a learning factor. Since the *σi*

*l* (*µi l* , *σi l*).

transformations on the problem without result changes.

is calculated for dimension *i* as follows:

*l* value for *si*

be the standard deviation value *σi*

will sample the Gaussian PDF *gi*

dimensions of the file.

is done through a Gaussian function parametrized by the *µi*

 *k* ∑ *r*=1 *ωr*

that is, the probability of each solution being chosen can be thought as a random number generator of normal distribution, with mean 1 and standard deviation *q* × *Fs*, since the choose probability of each rank will never change. Adopting this strategy, the *ω* vector as

Thus, since the ant chosen its solution, it must be sampled stepwise using a normal random number generator. The chosen solution must be sampled dimensionally

Therefore, let *sl* (Fig. 1) to be the solution chosen by an ant during the ACO's evolution process. It is known that the ant will sample *sl* dimensionally, as well as that the sampling

> *k* ∑ *e*=1

*l* is the mean distance from *si*

*i* in the other solutions of the file. The process is repeated until the last dimension of the file is reached. This way, the higher the variability of the different solutions, higher will

The parameter *ξ* is the same for all dimensions of all solutions, and corresponds to the pheromone evaporation rate, or to the inverse of the learning rate. This way, when *ξ* is low valued the algorithm speed is enhanced, and when it is high-valued, its robustness is enhanced. It is noteworthy that the algorithm converges when *σ* → 0 throughout all

• *PheromoneUpdate()*: The ACO**R** algorithm updates its pheromone informations as follows: At the beginning of the algorithm, the file is initialized with *Fs* solutions uniformly random distributed. From this, the pheromone updating is done adding the new solutions

Finally, the size of the solutions file is a parameter of the algorithm, and must not be smaller than the number of dimensions of the problem if it is enabled to handle variable correlation, and to support linear transformations on the problem being optimized. Nevertheless, these techniques are not used in this work. Furthermore, the size of the file leads to the algorithm diversity, since a big file will cover a greater region of the search space than the small one, enabling the algorithm to overcome local optima, but on

generated by the ants, as well as removing the same number of worst solutions.

the other hand, a small file will make the algorithm to be faster than the big one.

*l* and *σi*

. Note that the *ξ* ∈ [0, 1] parameter aims to reduce the

*k* − 1 (25)

*l* to the other values of dimension

*l* value is calculated, the ant

*l* values. Thus, the *σi*

, *i* = 1, . . . , *U*), causing each Gaussian mixture's parameters to be seen only in one dimension a time, smoothing the calculation of the pattern deviation and allowing linear

−1

(24)

*l*

This subsection is divided in two parts. The first one deals with ACO typical performance and its input parameters optimization; the second part numerical simulations results for both power and rate allocation problems are presented and the NMSE is compared with the RA-PSO algorithm.

The simulations were carried out in the MatLab 7.0 platform and the scenario parameters are presented on Table 1. We assumed a rectangular cell with one base station in the center and users uniformly spread across all the cell extension. We considered that all mobile terminals experience slow fading channels, i.e. the following relation is always satisfied:

$$T\_{\rm slot} < (\Delta t)\_{\rm c} \tag{26}$$

where *T*slot = *R*−1 slot is the time slot duration, *R*slot is the transmitted power vector update rate, and (∆*t*)*c* is the coherence time of the channel2. This is part of the SNIR estimation process, which means that the channel is constant in each optimization window, assumed herein equal to 667*µs*. Thus, the ACO algorithm must converge to the solution within each 667*µs* interval.

## *2.6.1. RA-ACO Input Parameters Optimization*

Simulation experiments were carried out in order to determine the suitable values for the ACO input parameters for each problem, such as file size (*Fs*), pheromone evaporation coefficient (*ξ*), population (*m*) and the diversity parameter (*q*). The best parameters combination was chosen considering the solutions quality measured by the normalized mean squared error (NMSE), defined as:

$$\text{NMSE} = \mathbb{E}\left[\frac{||\mathbf{p} - \mathbf{p}^\*||^2}{||\mathbf{p}^\*||}\right] \tag{27}$$

where **p** is the solution found through the ACO algorithm, **p**∗ the analytical (optimal) solution and **E** the mathematical expectation operator. In order to find the best parameters for both problems non-exhaustive tests were conducted.

A typical convergence behavior for the RA-ACO under equal-rate power control problem is shown in Fig. 2. At a first glance, power allocation for *U* = 5 users (lightly loading system) is performed by a) RA-ACO algorithm, b) RA-PSO algorithm from [1]. One can

2 Corresponds to the time interval in which the channel characteristics do not suffer expressive variations.

**Power Allocation (PA) Problem.** Under the first resource allocation problem posed by Eq. (9) or (17), Fig. 3 depicts the associated NMSE under different ACO input parameter values combination taking into account different loading system, i.e., *U* = 5, 10 and 20, respectively. Note that the population size *m* and file size *Fs* parameters (*m*, *Fs* ∈ **N**), both with entry values common for all the different {*q*, *ξ*} input parameters configurations, where chosen based on the problem dimensionality. Numerical experiments have shown that different entries around the ones chosen do not affect substantially the NMSE results as the different entries for *q* and *ξ* parameters do. It is worth noting that the PA problem in (9) presents a non-convex characteristic; hence, the value entries for the population size *m* and file size *Fs* parameters assume relative high values regarding the dimensions of the problem, meaning that both parameters are of the order of problem dimension, {*m*, *Fs*}≈O[*U*]. It means that RA-ACO can solve the non-convex PA problem in DS/CDMA systems but with input

Ant Colony Optimization for Resource Allocation and Anomaly Detection in Communication Networks

http://dx.doi.org/10.5772/53338

123

Herein, a parameter calibration strategy was adopted in order to find the best tradeoff for the {*q*; *Fs*} set, given in Eq. (23). Since the parameters *Fs* and *m* are directly related to the computational complexity of the algorithm, finding a suitable parameter set with *Fs* entries

On the other hand, the population size *m* parameter has a small or even no influence on the any other ACO input parameter (as *q* and *Fs* interfere each other). Although the *m* entries values directly increases the algorithm computational complexity. Therefore, the parameters *m* and *Fs* were fixed at low values and then the best *q* and *ξ* combination for it was sought. Hence, based on the NMSE *versus* convergence speed results obtained in Fig. 3, the optimized RA-ACO input *q* and *ξ* parameters for the power control problem in DS/CDMA networks

> *U* (users) 5 10 20 *q* 0.61 0.40 0.40 *ξ* 1.00 0.82 0.75 *m* 7 15 35 *Fs* 8 4 25 Robustness, R 100 % 100 % 30 %

Also, the robustness achieved by the RA-ACO for the power allocation problem is added to the Table 2. Herein, the success of convergence is reached when the NMSE of the algorithm's solution goes less than 10−2. Due to the non-convexity of the PA problem in (17), when the number of users grows from 10 to 20, the needed robustnes grows exponentially, thus, the

**Weighted Throughput Maximization (WTM) Problem.** For the weighted throughput maximization (WTM) problem posed in Eq. (21), Figure 4 shows different cost function evolutions when parameters *q* and *ξ* are combined under three distinct system loading, *U* = 20, 100 and 250 users. The average cost function evolution values where taken over

From Fig. 4-a it is clear that for *U* = 20 users, the *q* = 0.10 and *ξ* = 1.00 choice results in an average cost function value higher than the other ones. Besides, even in a

T = 1000 trials. Also, the correspondent sum rate difference (∆ ∑rate) is zoomed in.

under different level of interference could be found, as summarized in Table 2.

**Table 2.** Optimized RA-ACO input parameters and respective robustness for the Problem of Eq. (17).

algorithm's performance have a critical decay of 70%.

parameter loads relatively high.

as low as possible is of great interest.

**Table 1.** Multirate DS/CDMA system, channel and ACO input parameters

see the smooth-monotonic convergence of the RA-ACO algorithm toward the optimal power solution, in this case given by (16), in contrast to the non-monotonic oscillated convergence behavior presented by the RA-PSO algorithm. Besides, for *U* = 5 users power allocation problem, the ACO was able to achieve convergence after ≈ 250 iterations in contrast to the ≈ 450 iterations necessary for the RA-PSO convergence.

**Figure 2.** Power allocation for *U* = 5 users. Equally information rate among users is adopted. a) RA-ACO; b) RA-PSO algorithm from [1].

**Power Allocation (PA) Problem.** Under the first resource allocation problem posed by Eq. (9) or (17), Fig. 3 depicts the associated NMSE under different ACO input parameter values combination taking into account different loading system, i.e., *U* = 5, 10 and 20, respectively.

14 Search Algorithms

**Parameters Adopted Values**

Noise Power *Pn* = −63 [dBm] Chip rate *rc* = 3.84 × 106 Min. Signal-noise ratio *SNR*min = 4 dB Max. power per user *P*max = 1 [W] Min. Power per user *P*min = 0 [W]