Novel optimized link state routing protocol based on quantum genetic strategy for mobile learning

https://doi.org/10.1016/j.jnca.2018.07.018Get rights and content

Abstract

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). Due to the mobility, self-organization and distributed control of MANET, the routing protocol of MANET has to adapt to the rapid changes of the network structure, and have to make sure the network resources being saved at most. The OLSR (Optimized Link State Routing) is a representative table-driven routing in MANET, and the main technology of OLSR is MPR. In this paper, we improved the quantum genetic strategy, and proposed a new routing protocol named QG-OLSR by combining the characteristics of OLSR. The quick changes of topology of MANET make it a huge challenge to find and maintain an end-to-end optimal path, while heuristic Q-Learning strategy is able to dynamically adjust the routing path through interaction with the surrounding environment. New Q-Learning strategy has been embedded in our improved quantum genetic strategy. The QG-OLSR of this paper optimized the selection of MPR, overcomes the shortage of the traditional protocol, and proves the property of convergence and global optimization. The new routing protocol improved the performance of transmission. The simulation results show that the new protocol is feasible and applicable, and perform a better experimental result.

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)

  • Wenbin Li

    Novel ID-based anti-collision approach for RFID

    Enterprise Inf. Syst.

    (2016)
  • Yanping Liang

    A kind of novel method of service-aware computing for uncertain mobile applications

    Math. Comput. Model.

    (2013)
  • Zhen Ma

    New AODV routing method for mobile wireless mesh network (MWMN)

    Intell. Autom. Soft Comput.

    (2016)
  • Zhen Ma

    A novel compressive sensing method based on SVD sparse random measurement matrix in wireless sensor network

    Eng. Comput.

    (2016)
  • Zhen Ma

    Shadow detection of moving objects based on multisource information in internet of things

    J. Exp. Theor. Artif. Intell.

    (2017)
  • A. Malossini et al.

    Quantum genetic optimization

    IEEE Trans. Evol. Comput.

    (2007)
  • B. Mohamed

    Performance evaluation of a cartography enhanced OLSR for mobile multi-hop ad hoc networks

    Proc. Wireless Adv. Netw.

    (2011)
  • S. Muhammad

    Comparative study of routing protocols in mobile ad hoc networks

    Int. J. Comput. Sci. Trends Technol.

    (2016)
  • Hongli Niu

    Novel PEECR-based clustering routing approach

    Soft Comput.

    (2017)
  • Hongli Niu

    Novel positioning service computing method for WSN

    Wireless Pers. Commun.

    (2017)
  • Di Niu et al.

    An asynchronous fixed-point algorithm for resource sharing with coupled objectives

    IEEE/ACM Trans. Netw.

    (2016)
  • Cited by (149)

    • Mitigation of coverage and connectivity issues in wireless sensor network by multi-objective randomized grasshopper optimization based selective activation scheme

      2022, Sustainable Computing: Informatics and Systems
      Citation 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].

    View all citing articles on Scopus

    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.

    View full text