alexa Topology Control of Wireless Sensor Network Using Quantum Inspired Genetic Algorithm | Open Access Journals
ISSN: 2090-4908
International Journal of Swarm Intelligence and Evolutionary Computation
Make the best use of Scientific Research and information from our 700+ peer reviewed, Open Access Journals that operates with the help of 50,000+ Editorial Board Members and esteemed reviewers and 1000+ Scientific associations in Medical, Clinical, Pharmaceutical, Engineering, Technology and Management Fields.
Meet Inspiring Speakers and Experts at our 3000+ Global Conferenceseries Events with over 600+ Conferences, 1200+ Symposiums and 1200+ Workshops on
Medical, Pharma, Engineering, Science, Technology and Business

Topology Control of Wireless Sensor Network Using Quantum Inspired Genetic Algorithm

Sajid Ullah1* and Mussarat Wahid2

1Institute of Space technology, Pakistan

2University of Nottingham, UK

Corresponding Author:
Sajid Ullah
Institute of Space technology, Pakistan
Tel: 92.51.9075502
E-mail: sajidullah.ist@gmail.com

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

Abstract

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.

Keywords

Relative quantum order; Topology Control; Linked quantum register

Introduction

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

Figure

Figure 1: (a) In order one each individual chromosome is spanned in two dimensional spaces. (b): In Order-2 the register has two chromosomes, and dimension of space for the order-2 QIGA is 4

Figure

Figure 2: The 1st depiction shows two nodes in an unlocked manner while the second show nodes in a Quantum locked register.

Figure

Figure 3: Updating Quantum gene state space.

Figure

Figure 4: Topology attained by QIGA-2.

Topological Initialization, Construction and Maintenance

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.

Order-2 Quantum Inspired Genetic Algorithm

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.

image

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.

Linked Quantum Register (LQR)

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

Algorithm Implementation for Topology Control

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 image

image

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 2n binary states of gene. The states of individual in the register are observed

For any Register, Rid

image

Where Ptj represent observational result of jth 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, Rf. The Binary solution is stored.

image

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.

Numerical Results

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.

Conclusion

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.

Acknowledgment

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.

References

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

Share This Article

Relevant Topics

Recommended Conferences

Article Usage

  • Total views: 11898
  • [From(publication date):
    October-2015 - Nov 23, 2017]
  • Breakdown by view type
  • HTML page views : 7978
  • PDF downloads : 3920
 

Post your comment

captcha   Reload  Can't read the image? click here to refresh

Peer Reviewed Journals
 
Make the best use of Scientific Research and information from our 700 + peer reviewed, Open Access Journals
International Conferences 2017-18
 
Meet Inspiring Speakers and Experts at our 3000+ Global Annual Meetings

Contact Us

Agri & Aquaculture Journals

Dr. Krish

agriaquaculture@omicsonline.com

1-702-714-7001Extn: 9040

Biochemistry Journals

Datta A

biochemjournals@omicsonline.com

1-702-714-7001Extn: 9037

Business & Management Journals

Ronald

business@omicsonline.com

1-702-714-7001Extn: 9042

Chemistry Journals

Gabriel Shaw

chemistryjournals@omicsonline.com

1-702-714-7001Extn: 9040

Clinical Journals

Datta A

clinicaljournals@omicsonline.com

1-702-714-7001Extn: 9037

Engineering Journals

James Franklin

engineeringjournals@omicsonline.com

1-702-714-7001Extn: 9042

Food & Nutrition Journals

Katie Wilson

nutritionjournals@omicsonline.com

1-702-714-7001Extn: 9042

General Science

Andrea Jason

generalscience@omicsonline.com

1-702-714-7001Extn: 9043

Genetics & Molecular Biology Journals

Anna Melissa

geneticsmolbio@omicsonline.com

1-702-714-7001Extn: 9006

Immunology & Microbiology Journals

David Gorantl

immunomicrobiol@omicsonline.com

1-702-714-7001Extn: 9014

Materials Science Journals

Rachle Green

materialsci@omicsonline.com

1-702-714-7001Extn: 9039

Nursing & Health Care Journals

Stephanie Skinner

nursinghealthcare@omicsonline.com

1-702-714-7001Extn: 9039

Medical Journals

Nimmi Anna

medicaljournals@omicsonline.com

1-702-714-7001Extn: 9038

Neuroscience & Psychology Journals

Nathan T

neuropsychology@omicsonline.com

1-702-714-7001Extn: 9041

Pharmaceutical Sciences Journals

Ann Jose

pharmajournals@omicsonline.com

1-702-714-7001Extn: 9007

Social & Political Science Journals

Steve Harry

social_politicalsci@omicsonline.com

1-702-714-7001Extn: 9042

 
© 2008- 2017 OMICS International - Open Access Publisher. Best viewed in Mozilla Firefox | Google Chrome | Above IE 7.0 version
adwords