Reach Us
+1-470-347-1923

Medical, Pharma, Engineering, Science, Technology and Business

^{1}Institute of Space technology, Pakistan

^{2}University of Nottingham, UK

- Corresponding Author:
- Sajid Ullah

Institute of Space technology, Pakistan

**Tel:**92.51.9075502

**E-mail:**[email protected]

**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.

- Programming, Australian journal of Basic& Applied Sciences( 2012) 6: 132
- Sensitive Analysis of Optimized Infiltration Parameters in SWDC model (2012) Advances in Environmental Biology. 6:2574
- Narayanan M. Moore A (1996) Quantum-inspired genetic algorithms, Proc. IEEE Evolutionary computation 61-66
- Han KH and Kim JH (2000) Genetic quantum algorithm and its application to combinatorial optimization problem, Proc. Congress on Evolutionary Computation 1354-1360
- S. Jezewski, Laski M, Nowotniak R (2010) Comparison of Algorithms for simulation Localization and Mapping Problem for Mobile Robot, Scientific Bulletin of Academy of Science and Technology, Automatics 14:439-452.
- Talbi H, Batouche M, Draa A (2004). A Quantum- Inspired genetic algorithm for multi-source affine image registration, Image Analysis and Recognition, Springer,147-154.
- Wang L, Wu H, Tang F, Zheng DZ (2005) A hybrid quantum-inspired genetic algorithm for flow shop scheduling, Advances in Intelligent Computing, Springer, 636-644
- RajatSetia, Hans Raj K (2012) Quantum Inspired Evolutionary Algorithm for Optimization of Hot Extrusion Process, International journal of Soft Computing and Engineering (IJSCE).
- Optimize of all Effective Infiltration Parameters in Furrow Irrigation Using Visual Basic and Genetic Algorithm
- Chen, Jamieson, Balkrishnan, Morris (2002) “Span, an energy efficient coordination algorithms for topology maintenance in ad hoc wireless network”, Wireless Network Journal 481-494
- Cerpa A, Estrin D .ASCENT: adaptive self- configuring sensor network topologies” Transaction on Mobile Computing, IEEE 3(3), P. 272-285.Scrugers et al. STEM: Topology management for energy efficient sensor network. Aerospace Conference Proceedings 1099-1108
- SUN Lijuan, GUO Jian, LU Kai, WANG Ruchuan (2006) Topology Control based on quantum genetic algorithm in sensor network”. Journal on Communication 27: 1-5
- Robert Nowotniak, JacekKucharski (2014) Higher- Order Quantum-Inspired Genetic Algorithms”, Computer Science and Information Systems (FedCSIS),Federated Conference on, 465-470
- Wendi R. Heninzelman, Chanderakasan A, BalakrishanH(2000) Energy-Efficient Communication Protocol for Wireless Microsensor Network”, Proceedings of the 33rd Hawaii International Conference on System Sciences.

Select your language of interest to view the total content in your interested language

- ACS Nano
- AI Algorithm
- Advanced Materials
- Algorithm
- Android Technology
- Artificial Intelligence
- Artificial Intelligence Studies
- Artificial Intelligence and Philosophy
- Artificial neural networks
- Automated Mining
- Automated Reasoning and Inference
- Automation
- Behavior-based systems
- Big data
- Bioinformatics Modeling
- Biomechanics
- Biomechanics and Robotics
- Biosensor
- Biostatistics: Current Trends
- Case-based reasoning
- Cloud
- Cloud Computation
- Cognitive Aspects of AI
- Commonsense Reasoning
- Computational Neuroscience
- Computational Sciences
- Computer Artificial Intelligence
- Computer Hardware
- Computer Science
- Computer-aided design (CAD)
- Constraint Processing
- Cryptography
- Data Communication
- Data Mining Current Research
- Data Mining and Analysis
- Data Security
- Data Storage
- Development Process
- Digital Image Processing
- Distributed Sensor Networks
- Electronic Engineering
- Evolution of social network
- Evolutionary Optimisation
- Evolutionary algorithm
- Evolutionary algorithm in datamining
- Evolutionary computation
- Evolutionary science
- Findings on Machine Learning
- Fuzzy Logic
- Handover
- Hardware Networking
- Heuristic Search
- High-Level Computer Vision
- Human Centered
- Human-Robot Interaction
- Hybrid soft computing
- IT Management
- Industrial Robotics
- Information Systems
- Information Technology
- Intelligent Interfaces
- Intelligent Robotics
- Internet Communication Technology
- Knowledge modelling
- Lovotics
- Machine Learninng
- Mathematical Modeling
- Medical Device
- Medical Robotics
- Mobile Communication
- Mobile Device
- Mobile Repots
- Mobile Robot System
- Motion Sensors
- Multi Objective Programming
- Nano/Micro Robotics
- Network Algorthims
- Network Security
- Networks Systems Technology
- Neural Network
- Neural Networks
- Neurorobotics
- Ontology Engineering
- Optical Communication
- Project development
- Real Time
- Robotic Rehabilitation
- Robotics
- Robotics In Medical
- Robotics Research
- Robotics for Application
- Robotics for Mechanism
- Routing Protocol
- Sensing and Perception
- Sensor Network Technology
- Sensor Technology
- Sensors and Actuators
- Simulation
- Social Robots
- Soft Computing
- Software Architecture
- Software Component
- Software Quality
- Studies on Computational Biology
- Swarm Robotics
- Swarm intelligence
- Systems Biology
- Telerobotics
- Web Service
- Wireless Sensor Networks
- Wireless Technology
- ZIPBEE Protocol
- swarm intelligence and robotics

- Total views:
**12128** - [From(publication date):

October-2015 - Oct 17, 2018] - Breakdown by view type
- HTML page views :
**8180** - PDF downloads :
**3948**

Peer Reviewed Journals

International Conferences 2018-19