Optimal QoM in Multichannel Wireless Networks Based on MQICA

Abstract

In wireless networks, wireless sniffers are distributed in a region to monitor the activities of users. It can be applied for fault diagnosis, resource management, and critical path analysis. Due to hardware limitations, wireless sniffers typically can only collect information on one channel at a time. Therefore, it is a key topic to optimize the channel selection for sniffers to maximize the information collected, so as to maximize the Quality of Monitoring (QoM) for wireless networks. In this paper, a Multiple-Quantum-Immune-Clone-Algorithm- (MQICA-) based solution was proposed to achieve the optimal channel allocation. The extensive simulations demonstrate that MQICA outperforms the related algorithms evidently with higher monitoring quality, lower computation complexity, and faster convergence. The practical experiment also shows the feasibility of this algorithm.

1. Introduction

With the growing application of wireless networks (e.g., WiFi, WiMax, Mesh, and WLAN), high quality management of wireless device and networks is becoming more and more important [1–3]. It has been a key point to monitor network status and performance accurately and in real time, so as to implement effective management.

Wireless monitoring is usually realized using Simple Network Management Protocol (SNMP) and base-station logs. Since they reveal detailed PHY (e.g., signal strength and spectrum density) and MAC behaviors (e.g., collision and retransmission), as well as timing information, they are essential for network diagnosis and management [4–9]. But wireless monitoring equipments are usually single-radio multichannel device [10–12]. That is to say, it has multioptional channels (In IEEE 802.11.b/g WLAN, there are 3 orthogonal channels, and in IEEE 802.11.a WLAN, there are 12 orthogonal channels). So, it is a key topic to allocate channels and other resources for these monitoring equipments to optimize the monitoring quality of entire network [13–17]. In the literature [16], it has turned out to be a NP-hard problem in user-center mode, and an effective solution for the problem will be with great significance to the performance improvement of all kinds of wireless application networks.

In this paper, we carry out the full investigation on the current wireless monitoring networks and establish a system monitoring model based on the undirected bipartite graph. Then, compared with existing algorithms, we propose an optimization solution “Multiple Quantum Immune Clone Algorithm (MQICA)” to solve the problem. Finally, the algorithm has been proved to be with good performance both in theory and experiments.

The rest of the paper is organized as follows. In Section 2, we provide a brief review of existing work on wireless monitoring. The problem formulation is presented in Section 3. The Multiple Quantum Immune Clone channel allocation algorithm (MQICA) is detailed in Section 4. Then we prove the validity of the proposed algorithm in Section 5 followed by extensive simulation experiments in Section 6. Finally, we conclude this paper with some future work in Section 7.

2. Related Work

In recent years, wireless monitoring networks have become a hot topic. The research mainly contains monitoring device, system design, fault diagnosis and so forth [4–9]. In 2004, “passive monitoring” utilizing multi-wireless sniffers was first introduced by Yeo et al. [4, 5]. He analyzed the advantages and challenges of wireless passive monitoring and preliminarily set up an application system, which fulfilled the network fault diagnosis based on time synchronization and data fusion of multisniffers. In 2005, Rodrig et al. [6] used sniffers to capture wireless communication data and analyze the performance characteristics of 802.11 WiFi network. In 2006, Cheng et al. [7] investigated a large-scale monitoring network composed of 150 sniffers and discussed the time synchronization method for distributed sniffers. In 2007, Yang and Guo et al. [8] studied the lifetime model of wireless monitoring networks and proposed to adjust the sensing and communication radius of sniffers in real time to maximize the lifetime of networks. In 2010, Liu and Cao [9] researched the relationship between the number of monitoring sniffers and false alarm rate and put forward an algorithm based on poller-poller structure, which can limit the false alarm rate and minimize sniffers.

It has become an important subject to optimize the channel selection of monitoring sniffers so as to improve the network monitoring quality. In 2009, Shin and Bagchi [13] researched the channel selection of sniffers in Wireless Mesh network to maximize the coverage of users. He described it as a maximum coverage problem based on group budget constraints [14, 15] and solved it using Greedy and Linear Programming (LP) algorithms, which achieved good performance. Based on the previous research, Chhetri et el. [16] formulated the problem of channel allocation of sniffers and proved it to be NP-hard to maximize the Quality of Monitoring (QoM) of wireless network under universal network model. Greedy and LP algorithms were employed to solve the problem. Greedy algorithm always seeks the solution with maximal current benefit during the process of resolution and misses the global optimal solution or approximate of it. Although LP algorithm can achieve better solution than others, its complexity is too high to meet the real-time optimization in dynamic wireless networks. In 2011, we applied Gibbs Sampler theory to address the problem and proposed a distributed channel selection algorithm for sniffers to maximize QoM of network [17]. This method utilizes the local information to select the channel with low energy but cannot achieve the global optima in most of the cases.

In [15–20], we can get an overview of much excellent work in multichannel selection of wireless network itself. In 2006, Wormsbecker and Williamson [18] studied the impact of channel selection technique on the communication performance of system and applied soft channel reservation technique to select channels, so as to reduce link layer data frame losses and provide higher TCP throughput. In 2007, Kanthi and Jain [19] proposed a channel selection algorithm for multiradio and multichannel mesh networks. It is based on Spanner conception and combined with network topology. The experiment results showed that it can improve data throughput in communication link layer. In 2009, You et al. [20] investigated the end-to-end data transmission and the optimal allocation of channel resource in wireless cellular networks and figured it out with stochastic quasi-gradient method. In 2010, Hou and Huang [21] researched the channel selection problem in Cognitive Ratio networks, described it as a binary integer nonlinear optimization problem, and proposed an algorithm based on priority order to maximize the total channel utilization for all secondary nodes. In 2011, an interface-clustered channel assignment (ICCA) scheme was presented by Du et al. [22]. It can eliminate the collision and interference to some extent, enhance the network throughput, and reduce the transmission delay.

From what has been discussed previously, there exist great shortcomings in solution of wireless monitoring network channel allocation problems. All of these studies most focused on the wireless network itself, rather than the wireless monitoring sniffers. Existing algorithms will have high algorithm complexity, slow convergence speed, and, in most cases, it is difficult to get global optimal solution in the cases of large-scale networks or having more optional channels. Therefore, in this paper, a so-called Multiple-QICA (MQICA) algorithm, taking full advantage of the parallel characteristics of Quantum Computing (QC), is proposed. Compared with traditional Quantum Immune Clone Algorithm (QICA), MQICA possesses lots of characteristics inherited from both immune and evolution algorithms. Meanwhile, allele and Gaussian mutations are introduced in MQICA to further improve the performance of the algorithm. Extensive simulations and practical experiments demonstrate that the proposed algorithm outperforms other algorithms not only in quality of solution, but also in time efficiency.

3. Problem Description

3.1. Network Model

Consider a wireless network of m monitoring sniffers, n users, and k optional channels. $S=\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_m\}$ is the set of sniffers, $U=\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\}$ is the set of users, and $C=\{c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_k\}$ is the set of channels. In homogeneous networks, sniffers have the same transmission characteristics. They have the ability to read frame information and can analyze the information from users or other sniffers. But at any point in time, a sniffer can only observe transmissions over a single channel. Let $p_{u_j}$ denote the transmission probability of a user $u_j\hspace{0.17em}\hspace{0.17em}(j=\mathrm{1,2},\dots ,n)$ that works on channel $c(u_j)\in C$ . These users can be a wireless router, access point or mobile phone user, and so forth. If a user sends data through a channel at time t, it will be called active user in time t.

In wireless networks, the relationship between sniffers and users can be described by an undirected bipartite graph $G=(S,U,E)$ shown in Figure 1. If $u_j$ is in the monitoring area of $s_i$ , there will be a connection between them, indicated by $e=(s_i,u_j)$ . When $s_i$ and $u_j$ work on the same channel, $s_i$ can capture the data from $u_j$ , and then we say that $u_j$ is covered by $s_i$ . E represents the set of all connecting edges. If a user is outside all sniffers' monitoring area, it is excluded from G. The vertex v in G is sniffer or user, namely, $v\in S\cup U$ . $N(v)$ denotes the neighbors of vertex v. If the vertex is a user $u_j$ , $N(u_j)$ means its neighbor sniffers; if the vertex is a sniffer $s_i$ , $N(s_i)$ is the set of neighbor users of $s_i$ . If a sniffer is inside the communication range of another sniffer, they are called adjacent sniffers. $V(s_i)$ denotes the set of adjacent sniffers of $s_i$ , and $B_{s_i}$ is the set of subscript of sniffers in $V(s_i)$ . In this paper, we assume that the communication radius of sniffer is twice as its monitoring radius.

Figure 1

undirected bipartite graph G.

3.2. Problem Formulation

$\mathbf{a}:S\to C$ represents a channel selection scheme for wireless monitoring networks, and O is the set of all possible schemes. a can be expressed in the form of vector as follows: $\mathbf{a}=(a(s_{\mathrm{1}}),a(s_{\mathrm{2}}),\dots ,a(s_m))$ , where $a(s_i)\in C$ is the channel selected by $s_i$ . When $s_i$ selects the channel $a(s_i)$ , it can communicate with the neighbor users, who also work on channel $a(s_i)$ . Given a channel selection scheme a, then $S={\cup }_{q=\mathrm{1}}^k{S}_{c_q}$ , $U={\cup }_{q=\mathrm{1}}^k{U}_{c_q}$ , where $S_{c_q}$ denotes the set of sniffers assigned to channel $c_q$ , and $U_{c_q}$ denotes the set of users working on channel $c_q$ . Now it is able to show the relationship between all the sniffers and users working on channel $c_q$ in the form of undirected bipartite graph     $G_{c_q}=(S_{c_q},U_{c_q},E_{c_q})$ .

Definition 1.

Monitoring quality of node (MQN): when wireless monitoring network works on channel $\mathbf{a}\in \text{O}$ , the monitoring quality of node $s_i$ can be defined as follows:

$$\begin{array}{cc}& Q_{s_i}\left(\mathbf{a}\right)=\sum _{u\in N\left(s_i\right)}{p}_u·\frac{\mathbf{1}\left(c\left(u\right)=a\left(s_i\right)\right)}{\mathrm{1}+{\sum }_{t\in B_{s_i}}\mathbf{1}\left(c\left(u\right)=a\left(s_t\right),s_t\in N\left(u\right)\right)},\end{array}$$

(1)

where $\mathbf{1}(·)$ is an indicator function. It equals 1 when the condition is true and 0 otherwise. It is clear that the more neighbor users work on the same channel as $s_i$ , the higher transmission probability these users have, and meanwhile, the less other sniffers cover these users, the higher monitoring quality $s_i$ has. MQN reflects the number of active users available to $s_i$ under the channel selection scheme a. Active users are in the state of sending data.

Given a channel selection scheme a, the Quality of Monitoring (QoM) of wireless network can be defined as follows:

$$\begin{array}{cc}& Q\left(\mathbf{a}\right)=\sum _{s_i\in S}{Q}_{s_i}\left(\mathbf{a}\right).\end{array}$$

(2)

So, the higher QoM is, the more active users can be monitored in the network and the higher quality of service the wireless monitoring network provides.

The problem of maximizing of QoM (MQM) can be described as follows: finding an optimal channel allocation scheme for sniffers to collect the largest amount of information transmitted by users, that is, to maximize the QoM of the network.

The channel allocation scheme will be changed according to probability during different time slot. So the maximal information collected by monitoring network in a certain period can be expressed as

$$\begin{array}{l}\max \hspace{1em}{\sum }_{\mathbf{a}\in \text{O}}Q\left(\mathbf{a}\right)\times \pi \left(\mathbf{a}\right),\hfill \\ \text{s}.\text{t}.\hspace{1em}\pi \left(\mathbf{a}\right)\in \left[\mathrm{0,1}\right]\hfill \\ \hspace{1em}\hspace{1em}\hspace{1em}{\sum }_{\mathbf{a}\in \text{O}}\pi \left(\mathbf{a}\right)=\mathrm{1},\hfill \end{array}$$

(3)

where $\pi (\mathbf{a})$ is the probability for wireless monitoring network to work on the channel allocation scheme a.

From (3), the optimal channel allocation scheme will be got as follows:

$$\begin{array}{cc}& {\mathbf{a}}^{*}=\text{argmax}Q\left(\mathbf{a}\right).\end{array}$$

(4)

For this complicated combination optimization problem, an effective heuristic algorithm is needed. In 2005 Jiao and Li proposed a brand new Quantum-Inspired Immune Clone Algorithm (QICA) [23]. QICA constructs antibodies in view of the superposition characteristics of quantum coding and enlarges the original population via clone operation, thus expanding the searching space and improving the performance of the algorithm when doing local search. It is very suitable for this complicated combination optimization problem because of the attributes of parallelism and provable rapid convergence. But the results in QICA are expressed in a binary form [24], which are more appropriate for solving problems in a binary encoding. Thus we need to extend it to k-resolution coding before applying the algorithm to this MQM problem in wireless monitoring network. Then, Multiple-QICA channel selection algorithm is proposed and described in detail as follows.

4. Multiple Quantum Immune Clone Channel Allocation Algorithm (MQICA)

4.1. Fundamental Definitions

To accurately describe the evolutionary process of the MQICA algorithm, the following fundamental definitions are proposed.

Definition 2 (Channel Quantum Antibody (CQA)).

We define the Channel Quantum Antibody as the following triploid chromosome:

$$\begin{array}{cc}& \text{CQA}\stackrel{\mathrm{def}}{=}\left[\begin{array}{c}{x}_{\mathrm{0}}\cdots x_i\cdots x_{m-\mathrm{1}}\\ {\alpha }_{\mathrm{0}}\cdots {\alpha }_i\cdots {\alpha }_{m-\mathrm{1}}\\ {\beta }_{\mathrm{0}}\cdots {\beta }_i\cdots {\beta }_{m-\mathrm{1}}\end{array}\right],\end{array}$$

(5)

where m is called the length of the chromosome, that is, the number of the monitoring sensors. $x_i\in [\mathrm{0,1})$ represents channel selection scheme of the ith monitoring sensor. ${\alpha }_i$ and ${\beta }_i$ should meet the normalization condition: ${|{\alpha }_i|}^{\mathrm{2}}+{|{\beta }_i|}^{\mathrm{2}}=\mathrm{1}$ , where ${|{\alpha }_i|}^{\mathrm{2}}$ and ${|{\beta }_i|}^{\mathrm{2}}$ indicate, respectively, the nonoptimal and optimal probability of the channel selection scheme of the ith monitoring sensor. ${\left[\begin{array}{ccc}{x}_i& {\alpha }_i& {\beta }_i\end{array}\right]}^T$ is named as an allele of the CQA.

Definition 3 (mapping between antibody to channel).

Note that in the CQA,

$$\begin{array}{cc}& X=\left[x_{\mathrm{0}},x_{\mathrm{1}},\dots ,x_i,\dots ,x_{m-\mathrm{1}}\right]\in R^m,\end{array}$$

(6)

where $x_i\in [\mathrm{0,1})$ is a continuous real number. If it is discrete, X can be mapped into integer space that

$$\begin{array}{cc}& \mathbf{C}=\left[c_{s_{\mathrm{0}}},c_{s_{\mathrm{1}}},\dots ,c_{s_i},\dots ,c_{s_{m-\mathrm{1}}}\right]\in Z^m,\end{array}$$

(7)

where $c_{s_i}\in \{\mathrm{0,1},\dots ,k-\mathrm{1}\}$ and indicates the monitoring sensor $s_i$ to select channel $c_{s_i}$ . k is the total number of selectable channels in the network. The process described previously is called mapping of the CQA to channel selection scheme, briefly as antibody to channel. The mapping relationship is defined as follows:

$$\begin{array}{cc}& c_{s_i}\stackrel{\text{mapping}}{=}\lfloor k{x}_i\rfloor ,\hspace{1em}i=\mathrm{0,1},\dots ,m-\mathrm{1}.\end{array}$$

(8)

Definition 4 (channel affinity).

Channel affinity refers to the affinity degree between the CQA and the channel antigen, which is the approximate level between feasible solution and optimal solution. With the affinity value increased, the feasible solution will be much closer to the optimal one. On the contrary, the feasible solution will gradually deviate from the optimal one. Channel affinity is the foundation of immune selection operation.

Definition 5 (evolutionary entropy of the CQA).

To measure the extent of the evolution, we introduce evolutionary entropy to the CQA:

$$\begin{array}{l}H\left(X\right)=H\left(x_{\mathrm{0}},x_{\mathrm{1}},\dots x_{m-\mathrm{1}}\right)\hfill \\ =H\left(x_{\mathrm{0}}\right)+H\left(x_{\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{x}_{\mathrm{0}}\right)\hfill \\ \hspace{1em}+\cdots +H\left(x_{m-\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{x}_{\mathrm{0}},x_{\mathrm{1}},\dots ,x_{m-\mathrm{2}}\right)\hfill \\ =\sum _{i=\mathrm{0}}^{m-\mathrm{1}}\left({\left|{\alpha }_i\right|}^{\mathrm{2}}\log \frac{\mathrm{1}}{{\left|{\alpha }_i\right|}^{\mathrm{2}}}+{\left|{\beta }_i\right|}^{\mathrm{2}}\log \frac{\mathrm{1}}{{\left|{\beta }_i\right|}^{\mathrm{2}}}\right)\hfill \\ =-\sum _{i=\mathrm{0}}^{m-\mathrm{1}}\left({\left|{\alpha }_i\right|}^{\mathrm{2}}\log {\left|{\alpha }_i\right|}^{\mathrm{2}}+{\left|{\beta }_i\right|}^{\mathrm{2}}\log {\left|{\beta }_i\right|}^{\mathrm{2}}\right)\hfill \\ =-\mathrm{2}\sum _{i=\mathrm{0}}^{m-\mathrm{1}}\left({\left|{\alpha }_i\right|}^{\mathrm{2}}\log \left|{\alpha }_i\right|+{\left|{\beta }_i\right|}^{\mathrm{2}}\log \left|{\beta }_i\right|\right).\hfill \end{array}$$

(9)

As the evolution process continues, ${\alpha }_i\to \mathrm{0}$ , ${\beta }_i\to \mathrm{0}$ , thus $H(X)\to \mathrm{0}$ . So the evolutionary entropy can be used to describe the extent of the evolution. When the algorithm finally comes to a convergent result, the value of evolutionary entropy is indefinitely close to zero.

4.2. Process Design

The population is denoted as $A=\{r_{\mathrm{1}},r_{\mathrm{2}},\dots ,r_N\}$ , where N indicates the scale of the population and $r_i$ represents a CQA in it. An evolution process of the algorithm in this paper consists of three basic operations, including clone, immune genetic variation, and immune selection. Clone operation ( $T_c$ ) clones each antibody and the clone scale is decided by the channel affinity value of the antibody. Immune genetic variation ( $T_m$ ) will increase the diversity of population information. The immune selection operation ( $T_I$ ) chooses from all antibodies generated by the former two operations according to their channel affinity and get the optimal CQA. Then compare them with the original N elite antibody $r_{i\mathrm{0}}^{\mathrm{\prime \prime }}$ [25], $i=\mathrm{1,2},\dots ,N$ in immune memory set $S_m$ [26]. Meanwhile, it forms the new population of next generation. Thus an evolution process can be described as

$$\begin{array}{l}A\left(t\right)\stackrel{\text{Clone}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\text{Operation}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\left(T_c\right)}{\to }{A}^{\prime }\left(t\right)\stackrel{\text{Immune}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\text{Genetic}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\text{Variation}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\left(T_m\right)}{\to }\\ A^{\mathrm{\prime \prime }}\left(t\right)\stackrel{\text{Immune}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\text{Selection}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\left(T_I\right)}{\to }A\left(t+\mathrm{1}\right).\hfill \end{array}$$

(10)

After this operation, we need to do full interference cross to the new operation $A(t+\mathrm{1})$ and continue returning to the next, in case that the evolution still did not meet the termination conditions.

4.2.1. Cloning Operation

A self-adaptive clone operation is proposed in [23]:

$$\begin{array}{cc}& T_c\left(A\left(t\right)\right)=\left\{T_c\left(r_{\mathrm{1}}\right),T_c\left(r_{\mathrm{2}}\right),\dots ,T_c\left(r_N\right)\right\},\end{array}$$

(11)

where $T_c(r_i)=E_i\times r_i$ , $i=\mathrm{1,2},\dots ,N$ and $E_i$ is a unit row vector with $q_i$ columns, while $q_i$ indicates the clone scale of the CQA and is decided by the equation as follows:

$$\begin{array}{cc}& q_i=\lceil N_c\times \frac{Q\left({\mathit{C}}_i\right)}{{\sum }_{j=\mathrm{1}}^{N}Q\left({\mathit{C}}_j\right)}\rceil ,\end{array}$$

(12)

where $N_c>N$ . It can be concluded from (12) that if the channel affinity of a specific CQA is greater than that of the others in the population, then corresponding clone scale will be larger. Thus this clone strategy guarantees that the more excellent an antibody is, the more resource it will get, and this will obviously drive the algorithm to evolve towards the optimal solution much more quickly. Once the clone operation is completed, the population $A(t)$ is expanded to have the following form:

$$\begin{array}{cc}& A^{\prime }\left(t\right)=\left\{A\left(t\right),A_1^{\prime }\left(t\right),\dots ,A_N^{\prime }\left(t\right)\right\},\end{array}$$

(13)

where,

$$\begin{array}{cc}& A_i^{\prime }\left(t\right)=\left\{r_{i\mathrm{1}}\left(t\right),r_{i\mathrm{2}}\left(t\right),\dots ,r_{i{q}_i-\mathrm{1}}\left(t\right)\right\},\\ r_{ij}\left(t\right)=r_i\left(t\right),\hspace{1em}j=\mathrm{1,2},\dots ,q_{i-1}.\end{array}$$

(14)

4.2.2. Immune Genetic Variation

MQICA algorithm implements a single-gene mutation on every triploid chromosome during the evolution. Compared with full-gene mutation, it has been proved in the literature [27] that single-gene mutation can dramatically improve the search efficiency of the algorithm. Denote $r_z^t$ as a CQA in $A_i^{\prime }(t)=\{r_{i1}(t),r_{i2}(t),\dots ,r_{i{q}_i-1}(t)\}$ which is generated by clone operation on the ith CQA of population $A(t)$ . Choose the jth allele ${\left[\begin{array}{ccc}{x}_{zj}^t& {\alpha }_{zj}^t& {\beta }_{zj}^t\end{array}\right]}^T$ randomly from $r_z^t$ and perform two kinds of Gaussian mutation on it:

$$\begin{array}{l}{x}_{zj}^{t+1,\varpi }=N\left({\mu }_{zj}^{t,\varpi },{\left({\delta }_{zj}^{t,\varpi }\right)}^2\right)\hfill \\ =\{\begin{array}{ll}{x}_{zj}^t+N\left(0,{\left|{\alpha }_{zj}^t\right|}^2\right),\hfill & \varpi =\alpha ,\hfill \\ \frac{x_{\max }-x_{\min }}{2}+N\left(0,\frac{{\left|{\beta }_{zj}^t\right|}^2}{\chi }\right),\hfill & \varpi =\beta .\hfill \end{array}\hfill \end{array}$$

(15)

χ is a variable. After the Gaussian mutation, $x_{zj}^{t+1,\varpi }$ might exceed the interval $[\mathrm{0,1})$ . To avoid it, redefine $x_{zj}^{t+1,\varpi }$ as follows:

$$\begin{array}{cc}& x_{zj}^{t+1,\varpi }=\{\begin{array}{cc}\frac{k-1}{k},\hfill & x_{zj}^{t+1,\varpi }>1,\hfill \\ 0,\hfill & x_{zj}^{t+1,\varpi }<0,\hfill \\ N\left({\mu }_{zj}^{t,\varpi },{\left({\delta }_{zj}^{t,\varpi }\right)}^2\right),\hfill & \text{others}.\hfill \end{array}\end{array}$$

(16)

Gaussian mutation consists of two operations: one performs a local search around the current solution with a variance of ${|{\alpha }_{zj}^t|}^2$ , another performs a wide-range search around the mean value with a variance of ${|{\beta }_{zj}^t|}^2/\chi$ lest the algorithm converges to a local optimal solution.

After the Gaussian mutation indicated by (15) and (16), the algorithm will calculate the channel affinity of the new antibody and compare it with the original one, that is, to decide which one is better between the two feasible solutions $(x_{z0}^{t+1},\dots ,x_{zj}^{t+1,\varpi },\dots ,x_{z,m-1}^{t+1})$ and $(x_{z0}^t,\dots ,x_{zj}^t,\dots ,x_{z,q_i-1}^t)$ . If the Gaussian mutation does improve the quality of the antibody, replace $x_{zj}^{t,\varpi }$ with $x_{zj}^{t+1,\varpi }$ , and keep the probability of $x_{zj}^{t,\varpi }$ unchanged, that is, ${\alpha }_{zj}^{t+1}={\alpha }_{zj}^t$ , ${\beta }_{zj}^{t+1}={\beta }_{zj}^t$ . Otherwise, the Gaussian mutation has no effect and the probability indicating that the current solution is optimal should be increased. Quantum Rotation Door (QRD) is adopted to update ${|{\alpha }_{zj}^t|}^2$ and ${|{\beta }_{zj}^t|}^2$ : the former will be decreased and the latter will be correspondingly increased after the rotation operation. Assume that the step size of the rotation is $\mathrm{\Delta }{\theta }_{zj}^t$ , the newly generated ${\alpha }_{zj}^{t+1}$ and ${\beta }_{zj}^{t+1}$ are decided by (17)

$$\begin{array}{cc}& \left[\begin{array}{c}{\alpha }_{zj}^{t+1}\\ {\beta }_{zj}^{t+1}\end{array}\right]=\left[\begin{array}{cc}\cos \left(\mathrm{\Delta }{\theta }_{zj}^t\right)& -\sin \left(\mathrm{\Delta }{\theta }_{zj}^t\right)\\ \sin \left(\mathrm{\Delta }{\theta }_{zj}^t\right)& \cos \left(\mathrm{\Delta }{\theta }_{zj}^t\right)\end{array}\right]\left[\begin{array}{c}{\alpha }_{zj}^t\\ {\beta }_{zj}^t\end{array}\right].\end{array}$$

(17)

During the evolution, the probability of composite vector $({\alpha }_{zj}^t,{\beta }_{zj}^t)$ will approach gradually towards y-axis, shown as in Figure 2:

• (1)

If $({\alpha }_{zj}^t,{\beta }_{zj}^t)$ lies in the first or the third quadrant, an anticlockwise rotation is needed and $\mathrm{\Delta }{\theta }_{zj}^t$ is positive.

(2)

If $({\alpha }_{zj}^t,{\beta }_{zj}^t)$ lies in the second or the fourth quadrant, a clockwise rotation is needed and $\mathrm{\Delta }{\theta }_{zj}^t$ is negative.

(3)

If $({\alpha }_{zj}^t,{\beta }_{zj}^t)$ lies exactly on y-axis, the algorithm has converged and the current feasible solution is the optimal one.

Figure 2

Sketch map of QRD operation.

To sum up, $\mathrm{\Delta }{\theta }_{zj}^t$ is realized as follows:

$$\begin{array}{cc}& \mathrm{\Delta }{\theta }_{zj}^t=\mathrm{sgn}\left({\alpha }_{zj}^t{\beta }_{zj}^t\right)\mathrm{\Delta }\theta \exp \left(-\frac{{\left|{\beta }_{zj}^t\right|}^2}{{\left|{\alpha }_{zj}^t\right|}^2+N_q/N_s}\right),\end{array}$$

(18)

where $\mathrm{sgn}(·)$ is a sign function used to control the direction of the rotation, thus to make sure that the algorithm will finally converge to an optimal solution. $\mathrm{\Delta }\theta$ means the maximum rotation angle in a single rotation operation. Current probability ${|{\alpha }_{zj}^t|}^2$ , ${|{\beta }_{zj}^t|}^2$ as well as $N_q/N_s$ is employed to control the rotation dimension, or that is to say, to adjust the evolutionary speed in case of precocity of an antibody: $N_q$ represents the total number of CQAs in $A^{\prime }(t)$ , that is, $N_q={\sum }_{i=1}^N{q}_i$ and $N_s$ indicates how stable the current population $A(t)$ is. After every operation, including Gaussian mutation and crossover, which may update $x_{ij}^t$ , $N_s$ should be recalculate as follows:

$$\begin{array}{cc}& N_s=\{\begin{array}{cc}{N}_s+1,\hfill & x_{ij}^{t+1}=x_{ij}^t,\hspace{0.17em}i=\mathrm{1,2},\dots ,N,\hfill \\ \hfill & j=\mathrm{0,1},\dots ,m-1,\hfill \\ 1,\hfill & x_{ij}^{t+1}\ne x_{ij}^t,\hspace{0.17em}i=\mathrm{1,2},\dots ,N,\hfill \\ \hfill & j=\mathrm{0,1},\dots ,m-1.\hfill \end{array}\end{array}$$

(19)

4.2.3. Immune Selecting Operation

There shall form a new population:

$$\begin{array}{cc}& A^{\prime \prime }\left(t\right)=\left\{A\left(t\right),A_1^{\prime \prime }\left(t\right),\dots ,A_N^{\prime \prime }\left(t\right)\right\}\end{array}$$

(20)

after the immune genetic variation wherein

$$\begin{array}{cc}& A_i^{\prime \prime }\left(t\right)=\left\{r_{i1}^{\prime \prime }\left(t\right),r_{i2}^{\prime \prime }\left(t\right),\dots ,r_{i{q}_i-1}^{\prime \prime }\left(t\right)\right\},\hspace{1em}i=\mathrm{1,2},\dots ,N.\end{array}$$

(21)

For each CQA in population $A^{\prime \prime }(t)$ derived from immune manipulation operation, we firstly map $X=[x_0,x_1,\dots ,x_{m-1}]\in R^m$ to channel selection scheme $\mathit{C}=[c_{s_0},c_{s_1},\dots ,c_{s_{m-1}}]\in Z^m$ . Then compare them with original $r_{i0}^{\prime \prime }$ in $S_m$ on the basis of channel affinity. For all $i=\mathrm{1,2},\dots ,N$ , if exists

$$\begin{array}{cc}& {\mathit{C}}_{b_i}\left(t\right)=\left\{{\mathit{C}}_{r_{ij}^{\prime \prime }}\left(t\right)\hspace{0.17em}|\hspace{0.17em}\max Q\left({\mathit{C}}_{r_{ij}^{\prime \prime }}\right),j=\mathrm{0,1},2,\dots ,q_i-1\right\}\end{array}$$

(22)

making $Q({\mathit{C}}_{r_i})<Q({\mathit{C}}_{b_i}),\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2},\dots ,N$ , then $r_{i0}^{\prime \prime }(t+1)=b_i(t)$ , otherwise $r_{i0}^{\prime \prime }(t+1)$ remains unchanged as $r_{i0}^{\prime \prime }(t)$ . Immune selection operation selects the optimal CQA from all the antibodies generated by clone operation and immune manipulation operation as well as the immune memory set $S_m$ to form a brand new population. After the operation is down, we can get not only new immune memory set $S_m$ but also the new generation of CQA population $A(t+1)$ .

4.2.4. Full Interference Crossover

To make full use of the information of all CQAs in the population, thus to guarantee that new antibodies will be generated in case of antibody precocity, which may cause the algorithm converge to a local optimal solution, a full interference crossover strategy [28] is adopted in this paper. Denote the jth allele in the ith antibody before and after the crossover operation to be $A_{ij}$ and $B_{ij}$ respectively; the relationship between $A_{ij}$ and $B_{ij}$ can then be revealed as $B_{ij}=A_{[(i+j)\%N][j]}$ . A simple example is shown in Tables 1(a) and 1(b) to help understand when the population scale is set to $N=5$ , and the number of the monitoring sensors and current available channels is set to $m=8$ and $k=5$ , respectively.

Table 1

(a) Group information before the crossing. (b) Group information after the crossing.

(a)
NO.0:	$A_{\mathit{00}}$	$A_{\mathit{01}}$	$A_{\mathit{02}}$	$A_{\mathit{03}}$	$A_{\mathit{04}}$	$A_{\mathit{05}}$	$A_{\mathit{06}}$	$A_{\mathit{07}}$
NO.1:	$A_{\mathit{10}}$	$A_{\mathit{11}}$	$A_{\mathit{12}}$	$A_{\mathit{13}}$	$A_{\mathit{14}}$	$A_{\mathit{15}}$	$A_{\mathit{16}}$	$A_{\mathit{17}}$
NO.2:	$A_{\mathit{20}}$	$A_{\mathit{21}}$	$A_{\mathit{22}}$	$A_{\mathit{23}}$	$A_{\mathit{24}}$	$A_{\mathit{25}}$	$A_{\mathit{26}}$	$A_{\mathit{27}}$
NO.3:	$A_{\mathit{30}}$	$A_{\mathit{31}}$	$A_{\mathit{32}}$	$A_{\mathit{33}}$	$A_{\mathit{34}}$	$A_{\mathit{35}}$	$A_{\mathit{36}}$	$A_{\mathit{37}}$
NO.4:	$A_{\mathit{40}}$	$A_{\mathit{41}}$	$A_{\mathit{42}}$	$A_{\mathit{43}}$	$A_{\mathit{44}}$	$A_{\mathit{45}}$	$A_{\mathit{46}}$	$A_{\mathit{47}}$
(b)
NO.0:	$A_{\mathit{00}}$	$A_{\mathit{11}}$	$A_{\mathit{22}}$	$A_{\mathit{33}}$	$A_{\mathit{44}}$	$A_{\mathit{05}}$	$A_{\mathit{16}}$	$A_{\mathit{27}}$
NO.1:	$A_{\mathit{10}}$	$A_{\mathit{21}}$	$A_{\mathit{32}}$	$A_{\mathit{43}}$	$A_{\mathit{04}}$	$A_{\mathit{15}}$	$A_{\mathit{26}}$	$A_{\mathit{37}}$
NO.2:	$A_{\mathit{20}}$	$A_{\mathit{31}}$	$A_{\mathit{42}}$	$A_{\mathit{03}}$	$A_{\mathit{14}}$	$A_{\mathit{25}}$	$A_{\mathit{36}}$	$A_{\mathit{47}}$
NO.3:	$A_{\mathit{30}}$	$A_{\mathit{41}}$	$A_{\mathit{02}}$	$A_{\mathit{13}}$	$A_{\mathit{24}}$	$A_{\mathit{35}}$	$A_{\mathit{46}}$	$A_{\mathit{07}}$
NO.4:	$A_{\mathit{40}}$	$A_{\mathit{01}}$	$A_{\mathit{12}}$	$A_{\mathit{23}}$	$A_{\mathit{34}}$	$A_{\mathit{45}}$	$A_{\mathit{06}}$	$A_{\mathit{17}}$

4.3. Algorithm Description

Based on the discussion, the process of MQICA is described as follows.

Step 1.

Set algorithm parameters and initialize population $A(\mathrm{0})$ . Calculate the initial channel affinity of each CQA in the population, that is, the Quality of Monitoring (QoM).

Step 2.

Calculate the clone scale of each CQA according to (12) and then execute clone operation. After this step, $A^{\prime }(t)$ is obtained.

Step 3.

Do mutation operation on $A^{\prime }(t)$ , and get $A^{\prime \prime }(t)$ .

Step 4.

Do immune selection, and those selected antibodies constitute the new population $A(t+1)$ .

Step 5.

Calculate the channel affinity of each CQA in the new population as well as the evolutionary entropy of the population: if the former does not change any more and the latter tends to be close to zero infinitely or $t>t_{\max }$ , the algorithm has already approximately converged, otherwise, crossover operation is applied to $A(t+1)$ and jump to Step 2.

The pseudo code of the algorithm is also given in Pseudocode 1.

Pseudocode 1  

  Input: the sniffer set  $S=\{s_{\mathrm{1}},s_{\mathrm{2}},\dots ,s_m\}$ , channel set

   $C=\{c_{\mathrm{1}},c_{\mathrm{2}},\dots ,c_k\}$ , user set

   $U=\{u_{\mathrm{1}},u_{\mathrm{2}},\dots ,u_n\}$ , $c\left(u_j\right)$ and $p_{u_j}\left(j=\mathrm{1,2},\dots ,n\right)$ ,

  the iterative terminal entropy ε and the maximum iterations $t_{\max }$ .

  Output: the channel allocation vector C.

(1)  $r_i(t)\leftarrow$ Generate initial population, $\mathrm{1}\le i\le N$ , $t=\mathrm{0}$ ;

(2) Do mappings between antibody to channel, calculate the

  evolutionary entropy of each CQA and get $H(X_{r_i})$ ;

(3)  $Q_i(t)\leftarrow$ function( ${\mathbf{C}}_{r_i}$ );  /*compute the channel

  affinity of each antibody according to (2)*/

(4)  $r_{i\mathrm{0}}^{\prime \prime }(t)\leftarrow r_i(t)$  /*copy the original message to $S_m$ */

(5) do  {

(6)    $A^{\prime }(t)\leftarrow A(t)$ ;  /* clone operation*/

(7)    $A^{\prime \prime }(t)\leftarrow A^{\prime }(t)$ ;  /*immune genetic variation*/

(8)    Update immune memory set $S_m$ ;

(9)          /*immune selection operation*/

(10)    $A(t+\mathrm{1})\leftarrow S_m$ ;

(11)    $Q^{\mathrm{*}}=\max (Q_i(t)$ ); /*choose the max value*/

(12)    Calculate the evolutionary entropy update $H(X_{r_i})$ ;

(13)    if   $\left(\left(t<t_{\max }\right)\hspace{0.17em}|\hspace{0.17em}\left({{\displaystyle \sum }}_{i=\mathrm{1}}^{N}H\left(X_{r_i}\right)>\epsilon \right)\right)$  then

(14)     $t=t+\mathrm{1}$ ;

(15)     Do full interference cross and update $A(t)$ ;

(16)    end;}

(17) while   $\left(\left(t<t_{\max }\right)\hspace{0.17em}|\hspace{0.17em}\left({{\displaystyle \sum }}_{i=\mathrm{1}}^{N}H\left(X_{r_i}\right)>\epsilon \right)\right)$ ;

5. Performance Analysis of MQICA

We will firstly prove that MQICA, just like traditional QICA, has a dramatic ability on global optimization searching. And in next chapter, lots of experiments are given to further identify the outstanding performance of MQICA, especially on MQoM problems.

Lemma 6.

The population sequence $\{A_t,t\ge 0\}$ , generated by the evolutionary process of MQICA, is a stochastic process with discrete parameters and constitutes a time homogeneous Markov chain.

Proof.

Suppose that the state space of a single CQA is Ω, $A=\{r_1,r_2,\dots ,r_N\}$ represents the population where $r_i$ responds to the ith antibody in A and N is the population scale. $r_i\in \Omega$ , $A\in {\Omega }^N$ . During the evolution process, all CQAs are discrete. $X=\lfloor \mathit{C}/k\rfloor \in \{\mathrm{0,1}/k,\dots ,(k-1)/k\}$ describes the channel selection scheme. If the quantity of the CQA in population A is m, $\Omega ={\{\mathrm{0,1}/k,\dots ,(k-1)/k\}}^m\notin \varphi$ . So the population state space should be $|{\Omega }^N|=k^{Nm}$ , that is, the state space during the evolution is finite. According to literature [29], denote δ to be the minimum σ -algebra generated by all cylinder set of Ω and P to be a real-value measure function defined in $(\Omega ,\delta )$ , and thus the probability space of an CQA can be expressed as $(\Omega ,\delta ,P)$ and the probability space of MQICA should be defined as $({\Omega }^N,\delta ,P)$ . As a result, $\{A(t),t\ge 0\}$ , defined in state space $(\Omega ,\delta ,P)$ , is a stochastic sequence with discrete parameter and will change with t, the evolutionary times of our algorithm. Obviously, when the state space is replaced by $({\Omega }^N,\delta ,P)$ , the conclusion previously mentioned still holds.

Furthermore, the operations adopted in MQICA, including clone ( $T_c$ ), immune gene manipulation ( $T_m$ & $T_e$ ), and immune selection ( $T_I$ ), guarantee that $A(t+1)$ is only related to $A(t)$ . So $\{A(t),t\ge 0\}$ is time homogeneous Markov chain in state space $({\Omega }^N,\delta ,P)$ .

Definition 7.

Denote ${\mathbf{a}}^{\mathbf{*}}={\mathbf{C}}^{\mathbf{*}}$ as the optimal channel selection scheme, namely, ${\mathbf{C}}^{*}=\arg \hspace{0.17em}\max Q(\mathbf{a})=\arg {\hspace{0.17em}Q}^{*}$ , where $Q^{*}$ is the QoM value corresponding to optimal channel selection scheme. MQICA will converge to global optimal solution when and only when ${\lim }_{t\to \infty }P(Q_t=Q^{*})=\mathrm{1}$ .

Lemma 8.

The transition probability matrix $M(T_m)$ , which indicates that the probability for a CQA in clone group $A^{\prime }(t)$ changes its state from ${\mathrm{\Lambda }}^{\mu }$ to ${\mathrm{\Lambda }}^{\lambda }$ after the MQICA mutation operation $T_m$ , is strictly positive.

Proof.

For Gaussian mutation operation G, shown in (15), assume that after the mutation $x_{zj}^{t+1}=\{\begin{array}{c}{x}_{zj}^{t+1,\alpha }\\ x_{zj}^{t+1,\beta }\end{array},$ the probability for $x_{zj}^t$ to mutate to $x_{zj}^{t+1,\alpha }$ should be

$$\begin{array}{l}G\left(x_{z,j}^t,x_{z,j}^{t+1,\alpha }\right)\hfill \\ \hspace{1em}\hspace{1em}={\int }_{x_{z,j}^t}^{x_{z,j}^{t+1,\alpha }}\left(\frac{1}{\sqrt{2\pi }\left|{\alpha }_{z,j}^t\right|}·\exp \left(-\frac{{\left(x-x_{z,j}^{t+1,\alpha }\right)}^2}{\pi {\left|{\alpha }_{z,j}^t\right|}^2}\right)\right)·dx\hfill \\ \hspace{1em}\hspace{1em}>0.\hfill \end{array}$$

(23)

By the same token, the probability for $x_{zj}^t$ to mutate to $x_{zj}^{t+1,\beta }$ should be

$$\begin{array}{l}G\left(x_{z,j}^t,x_{z,j}^{t+1,\beta }\right)\hfill \\ \hspace{1em}\hspace{1em}={\int }_{x_{z,j}^t}^{x_{z,j}^{t+1,\beta }}\left(\frac{1}{\sqrt{2\pi }\left|{\beta }_{z,j}^t\right|}·\exp \left(-\frac{{\left(x-x_{z,j}^{t+1,\beta }\right)}^2}{\pi {\left|{\beta }_{z,j}^t\right|}^2}\right)\right)·dx\hfill \\ \hspace{1em}\hspace{1em}>0.\hfill \end{array}$$

(24)

Because these two Gaussian mutations are independent, so the probability of state transition from ${\mathbf{x}}_{\mu }$ to ${\mathbf{x}}_{\lambda }$ after this operation would be

$$\begin{array}{l}G\left({\mathbf{x}}_{\mu },{\mathbf{x}}_{\lambda }\right)=G\left(x_{z,j}^t,x_{z,j}^{t+1}\right)\hfill \\ =G\left(x_{z,j}^t,x_{z,j}^{t+1,\alpha }\right)·G\left(x_{z,j}^t,x_{z,j}^{t+1,\beta }\right)>\mathrm{0}.\hfill \end{array}$$

(25)

When the state of α in a specific allele of an antibody is changed from $a_{\lambda }$ to $a_{\mu }$ by QRD operation, the state transition probability $U(a_{\mu },a_{\lambda })>0$ . Thus,

$$\begin{array}{l}{m}_{\mu \lambda }\left(T_m\right)=G\left({\mathbf{x}}_{\mu },{\mathbf{x}}_{\lambda }\right)\times \left(1-U\left(a_{\mu },a_{\lambda }\right)\right)\hfill \\ \hspace{1em}+\left(1-G\left({\mathbf{x}}_{\mu },{\mathbf{x}}_{\lambda }\right)\right)\times U\left(a_{\mu },a_{\lambda }\right)>0,\hfill \end{array}$$

(26)

and obviously the transition probability matrix $M(T_m)$ is strictly positive.

Lemma 9.

The state transition matrix P for MQICA is a regular one.

Proof.

The state transition process of the population in ${\Omega }^N$ is described by the following four operations: $T_c$ , $T_m$ , $T_I$ , and $T_e$ . Denote T to be $T=T_c·T_m·T_I·T_e$ , and as a result, $r_i(t+1)=T[r_i(t)]=T_c·T_m·T_I·T_e[r_i(t)]$ . Assume that the state of the population was transferred from ${\mathrm{\Lambda }}^{\mu }$ to ${\mathrm{\Lambda }}^{\lambda }$ after the tth iteration, where ${\mathrm{\Lambda }}^{\mu },{\mathrm{\Lambda }}^{\lambda }\subseteq {\Omega }^N$ . So the state transition probability of MQICA is

$$\begin{array}{l}{p}_{\mu \lambda }\left(t\right)=p\left\{A(t+1)=Y\hspace{0.17em}|\hspace{0.17em}A\left(t\right)=W\right\}=p\left(Y\hspace{0.17em}|\hspace{0.17em}W\right)\hfill \\ =\prod _{i=1}^N\{p\left\{T_c\left(r_i\left(t\right)\right)\right\}\times \prod _{j=1}^{q_i-1}p\left\{T_m\left(r_{ij}\left(t\right)\right)\right\}·p_m\hfill \\ \times \prod _{\eta =1}^{t}p\left\{T_I\left(r_{\lambda i}(t+1)=r_{\mu i}\left(t\right)\right)\right\}\hfill \\ \times p\left\{T_e\left(r_{\mu i}\left(t+1\right)\right)\right\}·p_c\phantom{\left\{T_c\left(r_i\left(t\right)\right)\right\}\times \prod _{j=1}^{q_i-1}p\left\{T_m\left(r_{ij}\left(t\right)\right)\right\}·p_{m}p\left\{T_m\left(r_{ij}\left(t\right)\right)\right\}·p_m}\},\hfill \end{array}$$

(27)

where,  

$$\begin{array}{cc}& p\left\{T_c\left(r_i\left(t\right)\right)\right\}=\frac{Q\left({\mathbf{C}}_i\right)}{{\sum }_{j=1}^{N}Q\left({\mathbf{C}}_j\right)}>0,\\ p\left\{T_m\left(r_{ij}\left(t\right)\right)\right\}=m_{\mu \lambda }\left(T_m\right)\ge 0.\end{array}$$

(28)

Because the full interference cross has fixed relationships, that is, $p\{T_e(r_{\mu i}(t+1))\}=1$ , the lemma can be proved with the following three conditions.

Condition 1.

When $Q({\mathbf{C}}_{\mu i})<Q({\mathbf{C}}_{\lambda i})$ ,

$$\begin{array}{cc}& p\left\{T_I\left(r_{\lambda i}(t+1)=r_{\mu i}\left(t\right)\right)\right\}=1.\end{array}$$

(29)

Condition 2.

When $Q({\mathbf{C}}_{\mu i})>Q({\mathbf{C}}_{\lambda i})$ ,

$$\begin{array}{cc}& p\left\{T_I\left(r_{\lambda i}(t+1)=r_{\mu i}\left(t\right)\right)\right\}=0.\end{array}$$

(30)

Condition 3.

When $Q({\mathit{C}}_{\mu i})=Q({\mathit{C}}_{\lambda i})$ , the evolutionary entropy of the CQA satisfies $H(X)\to 0$ ; in other words, the algorithm should be converged and $p_{\mu \lambda }(t)=p_{\mu \mu }(t)=1$ , and the state transition probability of MQICA can be summarized as

$$\begin{array}{cc}& p_{\mu \lambda }\left(t\right)>0,\hspace{1em}\text{s}.\text{t}.\hspace{0.17em}\hspace{0.17em}Q\left({\mathbf{C}}_{\mu i}\right)\le Q\left({\mathbf{C}}_{\lambda i}\right),\\ p_{\mu \lambda }\left(t\right)=0,\hspace{1em}\text{s}.\text{t}.\hspace{0.17em}\hspace{0.17em}Q\left({\mathbf{C}}_{\mu i}\right)>Q\left({\mathbf{C}}_{\lambda i}\right).\end{array}$$

(31)

Obviously, $P\ge 0$ and $\exists t$ that makes $P^t>0$ . Thus P is a is regular matrix.

Lemma 10.

The Markov chain derived from MQICA is ergodic.

Proof.

Lemma 9 indicates that the state transition matrix P for MQICA is regular, and because the Markov cycle is 1, based on the basic Markov limit theorem, a unique limit ${\lim }_{t\to \infty }{P}^t=P^{*}$ must exist. Because $P^{*}>0$ , so the homogeneous Markov chain is nonzero and recurrent, thus any state in this chain would have an only limit distribution with a probability that is greater than zero regardless of how the population is initialized. As a result, MQICA can start from state i to state j within limited time; that is, when $t\to \infty$ , this Markov chain could traverse the whole state space.

Lemma 11.

MQICA converges to the global optimal solution on a probability of 1.

Proof.

MQICA adopts a so-called survival of the fittest strategy, which means that the channel affinities of this Markov sequence, generated by the evolution, are monotone and will not decrease. ${\mathrm{\Lambda }}^{*}\subseteq {\Omega }^N$ represents the population containing the global optimal antibody ${\mathit{r}}^{*}$ . ${\mathit{C}}^{*}$ denotes the global optimal channel selection scheme, while $Q^{*}$ denotes the global optimal channel affinity. Since the evolution process would not degenerate, ${\mathrm{\Lambda }}^{*}$ is a closed set and will be always in an attractive state, which means that for all $i\in {\mathrm{\Lambda }}^{*}$ , ${\sum }_{j\in {\mathrm{\Lambda }}^{*}}^{}{p}_{ij}=1$ always holds. So once the state of the population $A_t$ is changed to ${\mathrm{\Lambda }}^{*}$ , there would be no chance for the population to enter other state.

Based on the basic Markov limit theorem, MQICA will definitely reach state ${\mathrm{\Lambda }}^{*}$ after limited steps $t_c$ if only the state transition matrix P is regular and the corresponding Markov chain is ergodic, which have been proved by Lemmas 9 and 10. Thus, the following equation is satisfied:

$$\begin{array}{cc}& \underset{t\to \infty }{\lim }P\left(Q\left(t\right)=Q_{t_c}=Q^{*}\right)=\mathrm{1}.\end{array}$$

(32)

This indicates that MQICA converges to the global optimal solution on a probability of 1.

6. Experiment Results

6.1. Simulations

In this paper, we conduct extensive experiments to validate the effectiveness of the algorithm. The program is run on a PC with Intel(R) Core(TM)2 CPU @2.40 GHz, 2 GB memory. The software platform is Windows XP. Table 2 lists the parameters of MQICA.

Table 2

Parameters setting.

N	$p_m$	$p_c$	$N_c$	χ	ε	$t_{\max }$
10	0.5	0.88	15	3	10−5	1000

N is the population scales. Large N can promote the searching ability of the algorithm, meanwhile extend the running time of program. The other parameters are all set as the experiential value for MQICA applications, and the experiments result also shows the validity in this case.

From Section 5 we have known the validity of the proposed algorithm, MQICA, in solving multichannel allocation problems. Now a mass of experiment results also elaborate the effectiveness in another way. Firstly, we tentatively do three different experiments 5 times, respectively, according to the size. For small scale, $m=3$ , $k=2$ , $n=25$ ; for medium scale, $m=12$ , $k=6$ , $n=200$ ; for large scale, $m=12$ , $k=9$ , $n=1000$ . The experiment results are shown in Figures 3(a), 3(b), and 3(c). As can be seen from the graph, no matter how initialization is, MQICA will eventually well converge to the same optimal solution.

Figure 3

(a) The convergence of small scale. (b) The convergence of medium scale. (c) The convergence of large scale.

Secondly, in order to validate the correctness of the algorithm and eliminate the possibility of local optimal solution, we take traversal method for the small scale monitoring network. Ergodic results are shown as follows: 1.1, 1.1, 0.8, 0.767, 1.15, 1.15, 0.767, and 0.75. Obviously, MQICA can quickly find the optimal solution in small time. For medium and large scale, we both do the test fifty times. The results are expressed in Tables 3 and 4.

Table 3

Result for medium scale.

ID	$Q_{\mathit{0}}$	$Q^{*}$	Times
1	2.439	9.345	473
2	2.536	9.345	431
3	6.304	9.345	487
4	9.003	9.345	375
5	8.604	9.345	510
6	6.966	9.345	457
7	7.444	9.171	218
8	8.046	9.345	324
9	8.667	9.345	321
10	8.856	9.345	78
11	8.871	9.345	310
12	2.122	9.345	454
13	7.164	9.345	356
14	2.439	9.345	409
15	6.304	9.345	326
16	2.536	9.345	245
17	8.667	9.345	265
18	4.350	9.345	351
19	9.345	9.345	0
20	2.122	9.345	456
21	7.164	9.345	328
22	8.604	9.345	91
23	9.003	9.345	103
24	5.438	9.345	501
25	2.536	9.171	365
26	5.473	9.345	141
27	3.180	9.345	265
28	2.439	9.345	454
29	8.992	9.345	263
30	8.646	9.003	453
31	3.857	9.345	261
32	2.122	9.345	356
33	7.444	9.345	452
34	2.597	9.345	365
35	2.122	9.345	532
36	8.367	9.345	269
37	6.304	9.345	462
38	7.146	9.345	254
39	8.171	9.345	56
40	3.200	9.345	495
41	9.003	9.345	321
42	5.251	9.345	256
43	3.062	9.345	518
44	6.304	9.345	265
45	6.996	9.345	348
46	8.046	9.345	206
47	2.536	9.345	527
48	9.345	9.345	0
49	7.164	9.345	215
50	8.171	9.345	256

Table 4

Results for large scale.

ID	$Q_{\mathit{0}}$	$Q^{*}$	Times
1	24.150	28.900	684
2	26.367	28.900	596
3	27.200	28.850	352
4	28.900	28.900	0
5	28.250	28.900	152
6	25.850	29.050	715
7	27.417	28.900	254
8	24.533	28.900	561
9	28.450	28.900	215
10	27.250	28.900	325
11	27.200	28.900	387
12	28.467	28.900	152
13	24.533	28.900	356
14	27.050	28.900	261
15	28.700	28.900	164
16	28.150	28.850	92
17	26.900	28.900	364
18	24.533	28.900	259
19	24.750	28.900	381
20	25.850	28.900	681
21	28.267	28.900	154
22	24.750	29.050	296
23	27.200	28.900	614
24	25.700	28.900	265
25	24.150	28.900	562
26	28.567	28.900	244
27	27.800	29.050	264
28	25.700	28.900	157
29	24.533	28.900	246
30	27.800	28.900	106
31	27.417	28.900	315
32	28.850	28.900	26
33	27.800	29.050	268
34	24.533	28.900	654
35	27.200	28.900	341
36	25.700	28.900	465
37	26.750	28.900	287
38	28.467	28.900	384
39	27.900	29.050	468
40	27.200	28.900	215
41	24.750	28.900	216
42	24.150	28.900	656
43	23.587	28.900	146
44	25.700	28.900	356
45	28.267	28.850	21
46	27.200	28.900	265
47	24.533	28.900	378
48	27.800	28.900	198
49	28.700	28.850	254
50	26.750	28.900	394

From Table 3, During 50-times experiment, we can see that initial channel scheme is random so the initial QoM value is not optimal. But after a certain number of iterations, the network monitoring quality has been converged to or close to the optimal value of 9.345. Similarly, Table 4 shows that the algorithm can still do a better performance for the distribution of channel options under lager networks.

Now we can easily conclude that MQICA will generate a good performance in channel allocation problems. It can be quickly uniform convergence to the optimal solution when the size of monitoring networks is small or moderate. If the scale is large; MQICA can also be better converged to the optimal or near optimal solution in most cases. These experimental results have proved the effectiveness of the proposed algorithm from various scales.

We also evaluate the performance of MQICA comparing three baseline algorithms.

Greedy. Select channel for each sniffer to maximize the sum of transmission probability of its neighbor users.

Linear Programming (LP). Solve the integer programming problem from formula (4).

Gibbs Sampler. Sniffer computes the local energy of optional channels and their selection probability, then chooses one channel according to the probability.

We conducted four sets of experiments, and the number of optional channels is 2, 6, and 9, respectively. In each experiment, the four algorithms are compared in different aspects of performance. The algorithm program runs 30 times to get the average result for evaluation.

In the first set of experiment, 1000 users are distributed in $500\times 500$  m² square field as shown in Figure 4; transmission probability $p_u\in [\mathrm{0},\mathrm{0.06}]$ . The field is partitioned in several regular hexagon units to construct cellular framework. Each unit center is equipped with a base station (BS) working on a certain channel and users in the unit work on the same channel as BS. Every two adjacent units are on different channels. For easy to control, 25 sniffers are deployed uniformly in the field to form a network to monitor the communication activities of users in the field. Monitoring radius of sniffer is 120 meters and 3 optional channels (in IEEE 802.11.b/g WLAN, there are 3 orthogonal channels, the 1st, 6th, and 11th, with center frequency 2412 MHz, 2437 MHz, and 2462 MHz). MQICA, LP, Greedy, and Gibbs Sampler are applied separately to solve the optimal channel selection scheme for sniffers. The quality of solution (QoM) of the four algorithms is shown in Figure 5.

Figure 4

Wireless network topology Hexagonal layout with users (purple “+”), sniffers (solid dots), and base stations (isosceles triangles) of each cell (different color representing working on different channels).

Figure 5

Performance comparison of the four algorithms in the first set of experiments (3 optional channels).

As depicted in Figure 5, after 700 iterations, the proposed MQICA algorithm converges to the extremely optimal solution $(\text{QoM}=\mathrm{28.975})$ . LP algorithm takes the second place with QoM up to 28.105, while Gibbs Sampler and Greedy algorithm achieve the QoM of 27.048 and 23.893, respectively. It is shown that the Multiple Quantum Immune Clone Algorithm improves the convergence rate of other algorithm effectively and produces a better global searching ability.

Table 5 demonstrates the statistical results of the three sets of experiments. Among the four algorithms, MQICA and Gibbs Sampler both run 20 times in each set of experiments to get the average optimal solution and its QoM value. As deterministic methods, LP and Greedy just run once. From Table 5, we can see that MQICA outperforms LP in three sets of experiments and evidently better than Gibbs Sampler and Greedy. Furthermore, MQICA converges fast, with shorter running time than Gibbs Sample.

Table 5

Statistical results of three sets of experiments.

Experiment no.	MQICA		Gibbs sampler		LP		Greedy
	Average optimal QoM	Running time/s(1000 iter.)	Average optimal QoM	Running time/s(1000 iter.)	QoM	Running time/s(1 iter.)	QoM	Running time/s(1 iter.)
1 (2 channels)	27.338	10.616	26.052	28.938	27.105	0.562	22.872	0.093
2 (6 channels)	26.760	11.695	26.261	30.953	26.484	0.812	23.363	0.109
3 (9 channels)	26.263	11.759	26.140	35.031	26.088	0.934	23.481	0.119

6.2. Practical Network Experiment

In this section, we evaluate the proposed MQICA algorithm by practical network experiment based on campus wireless network (IEEE 802.11.b WLAN). 21 WiFi sniffers were deployed in a building to collect the user information from 1 pm to 6 pm (over 5 hours). Each sniffer captured approximately 320,000 MAC frames. Totally 622 users were monitored working on 3 orthogonal channels. The number of users in 1st, 2nd, and 3rd channels is 349, 118, and 155, respectively. The activity probabilities (active probability of a user is computed as the percentage of the user's active time in a unit time.) of these users were recorded in Table 6. It is shown that the activity probabilities of most users are less than 1%. The average activity probability is 0.0026.

Table 6

Parameters setting.

Active probability	0~0.01	0.01~0.02	0.02~0.04
Number of users	578	15	29

Figure 6 depicted the QoM of network with different number of sniffers. It is clear that the QoM (the number of monitored active users) is growing up with the increment of sniffers (from 5 to 21). Except the experiment with 21 sniffers, the other sets of experiments were conducted repeatedly with different sniffers selected randomly from the 21 sniffers, and the statistical average value of QoM was recorded and shown in Figure 6. Since the average activity probability is 0.0026, the largest number of active users is less than 1.7 during every time slot. By comparing with LP, Gibbs Sampler, and Greedy, the proposed MQICA exhibits its superiority and feasibility in the practical network environment.

Figure 6

QoM of campus wireless network with different number of sniffers.

7. Conclusion

In this paper, we investigate the channel allocation for sniffers to maximize the Quality of Monitoring (QoM) for wireless monitoring networks, which is proved to be NP-hard. A Multiple-Quantum-Immune-Clone-based channel selection algorithm (MQICA) is put forward to solve the problem. By theoretical proof and extensive experiments, we demonstrate that MQICA can solve the channel allocation problem effectively, and outperform related algorithms evidently with fast convergence. As an ongoing work, we are reducing the computation complexity and proving the convergence performance of algorithm in theory.