Novel optimized link state routing protocol based on quantum genetic strategy for mobile learning
Introduction
As we know, in order to support mobile learning, we often use mobile video devices (such as mobile laptop, ipad, mobile phone, mobile TV terminal), mobile audio devices (such as mobile mp3, mobile learning machine), mobile human -computer interaction devices (such as mobile interaction whiteboard, mobile smart space) and so on. The communication of these devices are mainly based on the MANET (Mobile Ad hoc Network). MANET is a wireless network to connect mobile devices, which is composed of a group of logically equivalent nodes with wireless transceiver device, it does not rely on any basis set (Zhang and Li, 2014; Yi, 2011; Niu, 2017a). Due to the flexibility and extensibility of MANET, it's widely used in various fields such as environmental monitoring, battlefield monitoring and disaster relief (Moussaoui, 2014; Ma, 2017; Sondi, 2013; Hiroshi, 2011). In disaster-relief applications, traditional emergency networks with central topology, such as cellular mobile systems, are easily destroyed, and a temporary emergency system can be established by using MANET (Wang and Song, 2015). Due to the high dynamic property of the topology, the traditional routing protocol is not applicable. So the routing problem of MANET is especially important (Zhang, 2012a; Stefano, 2016; Cervera, 2013; Ma, 2016a). At present, for the characteristics of MANET, the proposed routing protocol is divided into two categories: table-driven routing and on-demand routing. Table-driven routing is more suitable for the dynamic characteristics of MANET topology and the requirements of QoS routing. A typical table-driven routing protocol is OLSR (Optimized Link State Routing).
OLSR is different from the traditional LSR (Link State Routing), its core function is the MPR (Multipoint Relay) mechanism. In OLSR, each node selects a part of its own hop node as its own MPR node set. Only the node selected as MPR will forward the TC (Topology Control) packet. MPR node is responsible for notification of link state in the network. (Niu and Li, 2016; Ma, 2016b; Mohamed, 2011). Link state information is generated by the nodes selected as MPR, which can reduce the flooding of information in the network. The MPR node set periodical floods the TC message to the whole network, and the message contains the link information (Song and Wang, 2015) with the MS (Multi-point Relay Selector) node of the node. And the MPR node receives and forwards the TC message from the other MPR node. When the MPR node sends its own TC message, the MPR node also needs to add the information of being selected as MPR by the neighbor node in the TC packet.
OLSR is a table-driven routing protocol based on link state. It is suitable for the characteristics of node mobility in MANET that makes the network topology change constantly. It needs to update the routing information timely. However, the characteristics of wireless network determine the limited bandwidth of available links. The existing research mainly focuses on improving the protocol and resolving the problem of the timeliness of information updating and the limited bandwidth of available links. In (Muhammad, 2016; Zhu, 2012), the problem of flooding is considered for a specific physical layer. In (Zhu, 2012; Zheng and Zhang, 2015; Zhang et al., 2017), the flooding problem of heterogeneous MANET is studied. In (Niu, 2017b; Saha, 2015), MPR is applied to multicast protocols. In (Zhang, 2012b; Malossini and Blanzieri, 2007; Nowotniak and Kucharski, 2012), it is proved that the MPR selection is an NP-complete problem. The MPR mechanism is very important when the node density is bigger in the network, so OLSR is very suitable for the network with high node density.
In the early 1980s, Benioff and Feynman put forward the concept of quantum computation (Wang, 2017; Muhammad, 2016; Zhu, 2012; Zheng and Zhang, 2015). After Grover proposed a quantum algorithm for random database search and Shor proposed a quantum algorithm for decomposing a large number of factors, quantum computation has attracted much attention due to its unique computational performance, and has rapidly become a research hotspot. As early as the 1990s, there have been many quantum computing methods (Zhang et al., 2017; Niu, 2017b; Saha, 2015; Zhang, 2012b; Malossini and Blanzieri, 2007). Quantum computing can be seen as a computer without an operating system, much more efficient than traditional computing methods. NSGA (Nondominated Sorting Genetic Algorithm) can be used as multi-objective function optimization (Nowotniak and Kucharski, 2012; Patvardhan, 2015; Kang, 2012; Liang, 2013). It is known to all that NSGA-II (Liang, 2013) is one of the fast & elitist successful multi-objective genetic algorithms in optimization of current generation mobile WSN and MANET as well.
Some researchers proposed Quantum Genetic Algorithm (QGA), which is based on vector expression of quantum states (Zhou, 2017a; Wu, 2010; Zhang et al., 2014; Jamal, 2012; Zhao, 2012). Quantum bit representations are applied to chromosome coding, so that each chromosome can represent the superposition of multiple states at the same time, and realize the update operation of chromosome by using quantum revolving door, and overcome the phenomenon of local optimal solution of population by quantum crossing and quantum variation.
The current research focuses on two types of models: Quantum Inspired Genetic Algorithm based on quantum multi-cosmic features, Quantum Genetic Algorithm based on Quantum Genetic and Quantum Genetic Superposition (QGA) (Wang, 2015; Zheng, 2016; Song, 2015; Li, 2016). The problem of solving 0–1 knapsack problem in QGA is that each gene has only “0” or “1” state. But in other problem solving, each gene may exist multiple states, so the proposed algorithms are not universal. The solution is to design a unitary transformation that can operate on multiple states at the same time. This method has the advantages of simple encoding, high computational efficiency, but computational complexity is large, and the design of high latitude unitary transformation is troublesome. Another solution is the use of binary coding in genetic algorithms to quantify the presence of polymorphic bits, such as two states encoded with a single qubit and four states encoded with two bits, and the characteristics of the method is better versatility, and easier to achieve. Quantum bit coding makes it possible for a chromosome to express multiple states at the same time, which makes Quantum Genetic Algorithm have better diversity characteristics than classical algorithm.
As a self-learning algorithm, Q-Learning strategy (Zhou, 2017b; Chen and Mao, 2018; Israel, 2017; Palvinder, 2017) can find a shortest path from source node to destination node through constant interaction with outside of MANET. Based on this idea, in this paper, our improved quantum genetic strategy is designed by new Q-Learning strategy. It can adaptively adjust Q-Table with ensuring the reliability of each hop link to adapt such dynamic network topology of MANET. New Q-Learning strategy has been embedded in our improved routing protocol QG-OLSR by quantum genetic strategy.
Our designed approach adopts the multi-state factor bit coding method to encode the nodes in the network. The quantum cross-operation and the quantum not-gate are used to realize the genetic mutation. The quantum rotation gate strategy and the dynamic adjustment of the rotation angle mechanism are adopted to consider the nodal energy information, which avoid premature and local convergence. For the NP- completeness of the MPR problem, an improved global genetic algorithm is used to obtain the global optimal solution.
Section snippets
Design of our QL-OLSR protocol
The purpose of this method is to propose one novel optimized link state routing protocol (QG-OLSR) based on our improved quantum genetic algorithm (QGA), to reduce the redundant information in the network. The global convergence of the MPR set selection is guaranteed by quantum crossing and quantum not - gate variation, and the quantum rotation gate is used to update the data to improve the data transmission efficiency in the network topology. Definition 1 Optimal link state routing protocol: Based on the
Simulation & analysis
This experiment uses the MATLAB platform, carries on the simulation analysis to this QG-OLSR. This paper compares this protocol with the classical OLSR protocol, the proposed OLSR-NSSUA (Neighborhood State Self-Adaptive Update) protocol and the CE-OLSR (Cartography Enhanced - OLSR) protocol (Niu and Li, 2016; Ma, 2016b; Mohamed, 2011; Song and Wang, 2015; Wang, 2017; Muhammad, 2016). The packet-to-packet delivery rate, the average end-to-end delay between the nodes and the network lifetime are
Discussions
In order to make our proposed new routing protocol named QG-OLSR to understand easily and highlight its innovative advantage for mobile learning, we discuss the following several points in this section: what we improve in term of the algorithm, the convergence of the algorithm and the suitability of applying QGA in the application of mobile learning under the banner of MANET.
On the topic of what we improve in term of the algorithm, the new routing algorithm named QG-OLSR by combining the
Conclusions & future works
In order to support mobile learning, we studied the communication problem of mobile video devices, mobile audio devices, mobile human -computer interaction devices under the banner of the MANET (Mobile Ad hoc Network). We proposed an improved quantum genetic strategy for OLSR routing protocol named QG-OLSR routing protocol in this paper. Firstly, the traditional QGA strategy needs to be improved. New Q-Learning strategy has been embedded in our improved quantum genetic strategy. The nodes in
Acknowledgement
This research work is supported by National Natural Science Foundation of China (Grant No. 61571328), Tianjin Key Natural Science Foundation (No. 13JCZDJC34600), CSC Foundation (No. 201308120010), Major projects of science and technology in Tianjin (No. 15ZXDSGX 00050), Training plan of Tianjin University Innovation Team (No. TD12-5016, No. TD13-5025), Major projects of science and technology for their services in Tianjin (No. 16ZXFWGX00010, No. 17YFZC GX00360), the Key Subject Foundation of
De-gan Zhang (M'01) Born in 1970, Ph.D. Graduated from Northeastern University, China. Now he is a visiting professor of School of Electronic and Information Engineering, University of Sydney, Sydney, NSW 2006, Australia; professor of Tianjin Key Lab of Intelligent Computing and Novel software Technology, Key Lab of Computer Vision and System, Ministry of Education, Tianjin University of Technology, Tianjin, 300384, China. His research interest includes service computing, etc.
References (42)
Multipath routing strategy to prevent flooding disruption attacks in link state routing protocol for MANET
J. Netw. Comput. Appl.
(2013)A link-state QoS routing protocol based on link stability for Mobile Ad hoc Networks
J. Netw. Comput. Appl.
(2014)Design guidelines for quality of service support in Optimized Link State Routing-based mobile ad hoc networks
Ad Hoc Netw.
(2013)A kind of novel VPF-based energy-balanced routing strategy for wireless mesh network
Int. J. Commun. Syst.
(2017)- et al.
Novel unequal clustering routing protocol considering energy balancing based on network partition & distance for mobile education
J. Netw. Comput. Appl.
(2017) - et al.
Capacity of cooperative vehicular networks with infrastructure support: multi-user case
IEEE Trans. Veh. Technol.
(2018) Integrated protocol for optimized link state routing and localization: OLSR-L
Simulat. Model. Pract. Theor.
(2011)A hybrid method for the QoS analysis and parameter optimization in time-critical random access wireless sensor networks
J. Netw. Comput. Appl.
(2017)Intelligent OLSR routing protocol optimization for VANETs
IEEE Trans. Veh. Technol.
(2012)A novel image de-noising method based on spherical coordinates system
EURASIP J. Appl. Signal Process.
(2012)
Novel ID-based anti-collision approach for RFID
Enterprise Inf. Syst.
A kind of novel method of service-aware computing for uncertain mobile applications
Math. Comput. Model.
New AODV routing method for mobile wireless mesh network (MWMN)
Intell. Autom. Soft Comput.
A novel compressive sensing method based on SVD sparse random measurement matrix in wireless sensor network
Eng. Comput.
Shadow detection of moving objects based on multisource information in internet of things
J. Exp. Theor. Artif. Intell.
Quantum genetic optimization
IEEE Trans. Evol. Comput.
Performance evaluation of a cartography enhanced OLSR for mobile multi-hop ad hoc networks
Proc. Wireless Adv. Netw.
Comparative study of routing protocols in mobile ad hoc networks
Int. J. Comput. Sci. Trends Technol.
Novel PEECR-based clustering routing approach
Soft Comput.
Novel positioning service computing method for WSN
Wireless Pers. Commun.
An asynchronous fixed-point algorithm for resource sharing with coupled objectives
IEEE/ACM Trans. Netw.
Cited by (149)
The study of DDPG based spatiotemporal dynamic deployment optimization of Air-Ground ad hoc network for disaster emergency response
2024, International Journal of Applied Earth Observation and GeoinformationDynamic optimization based on quantum computation-A comprehensive review
2024, Computers and StructuresNESEPRIN: A new scheme for energy-efficient permutation routing in IoT networks
2022, Computer NetworksMitigation of coverage and connectivity issues in wireless sensor network by multi-objective randomized grasshopper optimization based selective activation scheme
2022, Sustainable Computing: Informatics and SystemsCitation Excerpt :Therefore, overlapping can be avoided by deactivating certain unwanted nodes [13]. Several existing techniques based on Genetic Algorithms (GA), harmonic search algorithm, Artificial Bee Colony (ABC), and Particle Swarm Optimization (PSO) have been proposed to mitigate these issues by considering connectivity, cost, and coverage [14–18]. Moreover, techniques based on k-coverage and energy-aware clustering schemes have been used to limit energy consumption [19,20].
New Method of Edge Computing-Based Data Adaptive Return in Internet of Vehicles
2024, IEEE Transactions on Industrial InformaticsLinear-layer-enhanced quantum long short-term memory for carbon price forecasting
2023, Quantum Machine Intelligence
De-gan Zhang (M'01) Born in 1970, Ph.D. Graduated from Northeastern University, China. Now he is a visiting professor of School of Electronic and Information Engineering, University of Sydney, Sydney, NSW 2006, Australia; professor of Tianjin Key Lab of Intelligent Computing and Novel software Technology, Key Lab of Computer Vision and System, Ministry of Education, Tianjin University of Technology, Tianjin, 300384, China. His research interest includes service computing, etc.
Ting Zhang (M'03) Born in 1973, Ph.D., a Member (M) of IEEE in 2003. Now he is a researcher of Tianjin University of Technology, Tianjin, 300384, China. Her research interest includes WSN, etc.
Yue Dong (M'13) Born in 1994, Ph.D. candidate, a Member (M) of IEEE in 2013. Now she is a researcher of Tianjin University of Technology, Tianjin, 300384, China. Her research interest includes WSN, mobile computing, etc.
Xiao-huan Liu (M'12) Born in 1989, Ph.D. candidate, a Member (M) of IEEE in 2012. Now she is a researcher of Tianjin University of Technology, Tianjin, 300384, China. Her research interest includes WSN, mobile computing, etc.
Yu-ya Cui (M'12) 1992. Ph.D, candidate, He is a researcher of Tianjin Key Lab of Intelligent Computing and Novel software Technology, Key Lab of Computer Vision and System, Ministry of Education, Tianjin University of Technology, Tianjin, 300384, China. Her research interest includes WSN, industrial application, etc.
De-xin Zhao (M'01) 1972. Ph.D, She is a professor of Tianjin Key Lab of Intelligent Computing and Novel software Technology, Key Lab of Computer Vision and System, Ministry of Education, Tianjin University of Technology, Tianjin, 300384, China. Her research interest includes WSN, industrial application, etc.