^{1}Institute of Space technology, Pakistan
^{2}University of Nottingham, UK
Received date: August 13, 2015; Accepted date: September 05, 2015; Published date: September 10, 2015
Citation: Ullah S, Wahid M (2015) Topology Control of Wireless Sensor Network Using Quantum Inspired Genetic Algorithm. Int J Swarm Intel Evol Comput 4:121. doi:10.4172/2090-4908.1000121
Copyright: © 2015 Ullah S, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at International Journal of Swarm Intelligence and Evolutionary Computation
In this work, an evolving Linked Quantum Register has been introduced, which are group vector of binary pair of genes, uses local topological space to represent those nodes. The optimal points of node for topology control have high connectivity and have low energy consumption, and have interference at low. The register works in higher dimension. In this modeling order-2 Quantum Inspired Genetic Algorithm has been used and higher order can be used to achieve greater versatility in topology control of nodes. Numerical result has been obtained, analysis is done as how the result has previously been obtained with Quantum Genetic Algorithm and results are compared too. For future work, metrics for LQR are hinted which would exploit the algorithm to work in more computational intensive problem.
Relative quantum order; Topology Control; Linked quantum register
The two algorithms, evolutionary and quantum computation has made a remarkable success by solving some problem with relatively less computational time and memory. From it a new meta heuristics field has been made which combined the power of two. Genetic programming has been used in number of application. [1,2]. The work, Quantum inspired genetic algorithm (QIGA) was put forward by Narayan in 1996 [3]. Although evolutionary techniques combined with quantum computing has been for years but the first work on practical problem to work out was used for combinatory optimization [4]. Quantum inspired genetic algorithm used probability based optimizations which include algorithms from evolutionary and quantum computing with the likes of parallel computing, superposition and genetic variation [3]. QIGA does not require quantum computer for its implementation, but there are metrics when reached certain level, then can quantum computer be required. Those computing techniques combine with probabilities achieve such great result which converge for global optimum.
QIGA has been used for combinatory optimization problem, and solved several computational intensive problems. QIGA has been used in Power system optimization and localization of mobile robots [5], Image processing [6], flow shop Scheduling [7], Optimization of Hot Extrusion Process [8]. Several algorithms are used for topology control in wireless network (WSN). LEACH [9], SPAN [10], ASCENT [11], and STEM [12]. The first use of evolutionary and Quantum computing used for topology control was in the work [13], which show better result than simple genetic algorithm. The topology control was achieved in fewer generation in Quantum genetic algorithm (QGA). QGA proves superior to simple genetic algorithm. Higher order QIGA was presented in work [14]. Order-2 QIGA does need a functional quantum computer for its implementation as it uses random features from quantum mechanical system such as qubits, superposition, and parallel computing. Quantum factor defines when algorithm have to be implemented on quantum computer, and is elaborated in [14].
The optimal point of topology control is standardized on the connectivity of nodes, number of nodes exceeding the threshold, energy of nodes, and interference between the nodes. The interference is one of key issue in wireless sensor network (WSN). An optimal point is selected which minimize the interference in the register and the intra node between the registers. Interference has not been accounted in topology control here. Higher order QIGA have terminology which does not exist in QGA. Quantum and relative quantum order, and quantum factor are defined here and for detailed work, the reader should understand the full algorithm in [14].
This paper is structured as: section 1 will describe the various design metrics, that influence the topology of nodes. Section 2 discussed the order -2 QIGA, various definitions of the algorithm are introduced. In section 3 Linked quantum register has been introduced. In section 4 algorithm has been implemented for topology control. In Last section, Numerical result has been obtained for topological control of nodes (Figures 1-4).
The sensor network is initialized with n number of sensor node at t=0, all the nodes have equal resources.
So at the start of the process the nodes have identical probability amplitudes which implies from the above statement, initially the nodes are randomly selected in topological space in which they are sensing, surveillance or other data acquisition. The second necessary step in topological control is its construction for which we present a novel higher, dimensional register LQR, which varies itself across (Table 1).
Algorithms | Earliest generation findingthe solution | Solution found in the generation | Total power theradius threshold | Rf |
QGA | 90 | 47 | 156 | 7 |
QIGA-2 | 79 | 42 | 140 | 6 |
Table 1: Result of algorithm: QGA and QIGA-2.
The QIGA uses individual independent qubits to represent binary genes, so they are effectively in order 1. Higher order QIGA was presented in [14]. We here present introductory definition from their work. For full understanding of their work reader should study [14]. QIGA-2 symbolizes classical and quantum individual population by P and Q. Order r is defined as the largest register used in the algorithms.1≤ r ≤N.
• Quantum order r is the size of biggest quantum register used in the algorithm.
• Relative quantum order w shows the ratio of quantum order to problem size, N. For QIGA-2, the 100 individual qubits would have a Relative Quantum range of 2/100=0.02, this is representation, based on 2-qubit registers.
• Quantum factor (λ ϵ [0 1]) which define the ratio of the ratio of the dimension of space of a current Algorithm to the dimension of space of the full quantum register of all individuals.
In our topological control problem, there can be a scenario in a high dimensional space in which there will be a need to deploy different registers size for nodes in local proximity of topological space. In QIGA- 2, register have a pair of nodes.
In this work we propose a model which takes the adjacent 2-qubit quantum register into account to form a binary paired register. The pair of binary genes in a register represents a node; while in register have a pair of nodes. The information between nodes in a register is transferred which achieve the topology optimal point in space. As a result, the LQR has four points in probability in distribution. |α_{0}|^{2}, |α_{1}|^{2}, |α_{2}|^{2} and |α_{3}|^{2}
These are a few key points about LQR.
• There can be an arbitrary number of Quantum binary genes in the register. It can vary across different register depending upon the computational complexity a classical machine can cope with. The network can have different number of chromosomes in a register, and still can achieve the work of having the same number of chromosomes (nodes) with turning off those nodes for the iterative procedure, but survival of the fittest results from evolutionary computing will keep the nodes ahead in the run.
• The protocol used is application specific in a register. The control decision information on the elements of a register is specific to the individuals only.
• LQR has memory because in each update step, which is the distance of nodes in each register, is to be stored.
Algorithm for topology control
The QIGA-2 starts by searching the adjacent nodes for which the register identifies (RI) is identical. After selecting the nodes of same RI. The algorithm checks for the node connectivity in adjacency matrix which is updated by algorithm presented in [14]. The connectivity of nodes is range of space between the nodes or discrete set of point in space. A prior optimal point is set for WSN which is application dependent. A loop is run over the node and the distance is incremented or decremented between the node is achieved which assign node to the same RI. The algorithms then compute the distance between the nodes and set it to be connected. The position of each node is varied by choosing the number of steps in each iterative process, which results in step size of the increment or decrement of topology control. The algorithm converges when the given node in WSN is in the connectivity range set prior in the algorithm. The update of 2x2 dimension of LQR depends by choosing one or both of the nodes. The algorithm has select () method that chooses one of the nodes in QLR.
Algorithm 1: Topology Control in QIGA2
1: for i=0,1,2,...,N
2: for j=0,1,2,...,N-1/2
3: distconn(i,i+1)=1
4: select( i,i+1) for j=j+1
5: dist(i,i+1)
6: if dist(i,i+1)=distconn(i,i+1)
7: then Mat [i,i+1]=1
8: else if dist(i,i+1)≤distconn (i.i+1)=1
9: while dist(I,i+1)≠ distconn(i,i+1)
10: do dist(i,i+1)←dist(i,i+1)+Δi
11: else if dist(i,i+1)≥distconn(i,i+1)
12: while dist(I,i+1)≠distconn(i,i+1)
13: do dist(i,i+1)←dist(i,i+1)-Δi
14: end for
15: end for
Several algorithms have been implemented for topology control [9-13].
The algorithm starts with an arbitrary number of wireless sensor network (1 ≤ i ≤ n). The initial population will start with equal resources in term of energy, processing Capability and Transceiver power.
In order-2 QIGA the population is represented by a vector of chromosome (register). All amplitudes are initialized with a magnitude of
Solution of individual Q-bits in register
In this step, binary string is produced from qubits string; this is called observation of states. Q (t) with n bits represents a superposition of 2^{n} binary states of gene. The states of individual in the register are observed
For any Register, R_{id}
Where P_{t}^{j} represent observational result of j^{th} individual, Rid will have N/r number of P (t) in each iterative step
In evaluation step, LQR has the individual nodes, and they are evaluated on the basis of how strongly they are connected. The individual use minimum energy and minimum number of nodes that exceeds the power transmission threshold radius, R_{f}. The Binary solution is stored.
Then the observation of state of Q (t-1) produces a binary solution in P (t). The variation operator is model specific, and the user can pick any of the operators that suit the algorithm the best. In order-2, genetic operators are taken 4x4 quantum gates. The observation function from step 2 of algorithm returns strings of binary genes 00, 01, 10 and 11 with a probability of |α0|, | α1|, | α2 |, and |α3| respectively.
Topology was obtained by
The modelling of LQR makes the difference in how topology is obtained unlike QGA. The pair of nodes in LQR works in coordination checking the node in its LQR and nodes in adjacent LQR for the topological condition the algorithm applies.
The algorithm has been implemented for 16 nodes. The WSN took 79 generations to accomplish the condition specified in algorithm to converge. Roulette wheel was used for the evaluation function of fitness. The QIGA-2 has been compared with Simple Quantum Genetic (SGA) algorithm. Solution found in QIGA-2 earlier, which was obtained because there were two pair of LQR which were in transmission range of one another. So as a result, it takes fewer generations for finding the optimal topology control.
LQR modeling in QIGA-2 results in less generation for topology control than QGA. The solution obtained earlier because the two pair of LQR which have transmission region exceeded than standardized earlier. The power consumption due to less generation of WSN was beneficial in QIGA-2, and results in less net power than QGA.
In this work, a novel register is introduced based on QIGA-2 which uses evolutionary computing in addition to quantum computing to find the optimal solution for topology control. The attributes inherited from quantum computing in LQR are the way of representation of solution of nodes. The order 2 register use the nodes in register to cooperate in the information necessary to increase the connectivity to an optimal level. At the start of algorithm nodes are paired to make LQR, which transfer the information in each iteration of the algorithm for the topology control. Future perspective of the QIGA lies in using more than two number of node in LQR which seem to obtain better result. Modeling of LQR for more than two nodes and its implementation on Quantum computer would be challenging.
We would like to thank our colleagues from institute of space technology and university of Nottingham for their valuable discussion about the problem and insights that greatly assists in our research work.