A spanning tree construction algorithm for industrial wireless sensor networks based on quantum artificial bee colony

WSN (wireless sensor networks) [1, 2] is an autonomous measurement and control network system that consist of a large number of ubiquitous, small sensor nodes with communication and computing capabilities that are densely deployed in unattended monitoring areas [3]. WSN is a new information acquisition and processing technology [4]. Due to its advantages of low communication cost, flexible networking, and ease of use, it has a wide application prospect in the industry, military, environment, medical, and other fields [5]. IWSN (industrial wireless sensor networks) [6‐8] is used to control and monitor various industrial tasks and is an emerging application of WSN.

Due to its high flexibility, low node cost, no wiring, and relatively easy maintenance, IWSN has been favored by more and more companies [9]. A large number of wireless sensors are deployed in industrial parks [10]. These sensor nodes form a multi-hop network in the form of ad hoc networks, which are very sensitive to the equipment, production lines, and environmental information of the industrial site and transmitted to the control center in real time [11]. Through the calculation and analysis of data, the control center can monitor the operating conditions of the equipment, find problems in a timely manner, issue control commands, and reduce safety problems in the production process.

IWSN faces more challenges than ordinary wireless sensor networks [12], which have the following features: (l) The sensor node deployment of the IWSN is related to the industrial environment. It needs to be manually installed on the plant equipment that needs to be monitored [13], emphasizing reliable monitoring of designated points [14]. The nodes of the WSN are generally deployed in a random and dense manner, focusing on the overall coverage of the monitoring area. (2) In IWSN, once the sensor node is installed, it is generally no longer moving, unless the node failure needs to be replaced or the plant equipment is moved [15]; in contrast, the WSN node mobility is strong. (3) In addition to sensor nodes in IWSN, there are routers, handheld devices, and other nodes [16]. Different types of nodes perform different functions, forming a heterogeneous network. The WSN generally refers to homogeneous networks, and the status of nodes is equal. (4) The factory environment is complex, and the interference is severe [17]. Therefore, the IWSN wireless network protocol design aims at high reliability and real-time performance. WSNs generally work in unattended areas. Node energy is limited, so the protocol design focuses on energy saving.

Field equipment production process data and network status data are collected periodically [18]. IWSN analyzes and processes this data to monitor factory equipment and networks. In the production process, it is often necessary to obtain some statistical information, such as the total number of network nodes and the temperature of the production site [19]. At present, the data collection of industrial wireless networks is basically centralized. That is, the original data is uniformly collected and processed by the central node. This is generally called the data collection protocol [20, 21]. The control information such as commands for monitoring the industrial field devices is performed through another protocol. This is generally referred to as data distribution protocol [22]. The data distribution process is one-to-many communication, and the data collection process is many-to-one communication. The above two processes are preferably implemented using trees to save network resources, especially the minimum spanning tree. Therefore, in industrial wireless sensor networks, how to construct an effective minimum spanning tree (MST) is a critical issue [23]. Classical algorithms in graph theory, such as Kruskal algorithm and Prim algorithm, utilize greedy strategies to generate only one MST. In IWSN, a series of spanning trees are required to improve reliability and deal with network changes [24]. Even if the found spanning tree is not optimal, but suboptimal, the found suboptimal spanning tree has important practical significance for responding to the dynamic changes of the network.

In the evolutionary process of swarm intelligence algorithm [25‐27], a series of solutions are generated, which is very suitable for the solution of the spanning tree problem in Industrial Wireless Sensor Networks environment. At the same time, the swarm intelligence optimization algorithm can search without prior knowledge to find a solution to the optimization problem [28, 29]. Artificial bee colony algorithm is a kind of swarm intelligence algorithm, which was put forward by Karabogay in order to solve the problem of multivariable function optimization. Artificial bee colony algorithm is an optimization method proposed to imitate bee behavior. It is a specific application of swarm intelligence thought. Its main characteristic is that it does not need to know the special information about the problem, but only needs to compare the pros and cons of the problem. Through the local optimization behavior of individual artificial bees, the global optimal value is finally emerging in the group, and it has a faster convergence speed. Quantum computation is a new computational model that follows quantum mechanics regulation to regulate quantum information units. From the point of view of computational efficiency, due to the existence of the superposition of quantum mechanics, some known quantum algorithms are faster than conventional general-purpose computers when dealing with certain problems. In this paper, quantum computation and artificial bee colony algorithm are combined and a quantum artificial bee colony algorithm is proposed to solve multicast tree construction problem in industrial wireless sensor networks.

This paper is organized as follows: In Section 2, we first describe IWSN architecture and the minimum spanning tree problem in IWSN. We then present the proposed algorithm in Section 3. Sections 4 and 5 report the simulation results and discussion. Finally, Section 6 concludes the paper.

Figure 1 shows the common IWSN architecture [30]. In IWSNs, sensor nodes are used as field devices to form industrial wireless networks. Nodes have the dual functions of data collection and routing. Sensor nodes distributed in the factory transmit the collected field data to servers through multi-hop routing. The access router is responsible for connecting the wireless network and the wired network and forwarding the field data from the wireless network to the wired network. There can be one or more access routers in the IWSNs. The gateway is responsible for the protocol conversion between the IWSNs and the existing factory network, so that both networks can send packets to each other. The management server is responsible for managing all network devices and in charge of storing topology information, node information, and neighbor relationships, as well as the link status of the entire network. In addition, the management server is also responsible for processing network information, managing network communication processes, and interacting with industrial applications. The security server [31] is responsible for the security management of the network and supports data integrity verification, data encryption, identity authentication, and replay protection. The data server stores field device configuration data, process flow data parameters, and data generated during the production process [32]. Gateways, management servers, security servers, and file servers are logically differentiated and can actually be deployed on the same network device as IWSNs controllers [33]. Finally, IWSN may need to connect to the Internet, depending on the specific conditions and needs of the factory.

A very important area of IWSN is data distribution and data collection. The effective implementation of data distribution and data collection is to use a minimal spanning tree. The minimum spanning tree problem is a basic problem in the areas of graph theory, optimization, and network optimization. Let graph G = (N,E,W) be a connected undirected weighted graph, where N is the set of nodes, E is the set of edges, and W is the weight defined on the edge. \( W=\sum \limits_{e\in E}{w}_e \) is the weight function. In graph theory, a tree is defined as an acyclic connected graph. If a subgraph of a connected graph G is a tree and contains all vertices of G, the subgraph T is called a spanning tree of G. If G has n vertices, its spanning tree has n vertices and n − 1 edges. \( {W}_T=\sum \limits_{e\in {E}_T}{w}_e \) is the weight function of the tree T. The spanning tree of a graph G is not unique. A graph can have many different spanning trees. Among these trees, the spanning tree with the least sum of edge weight is the minimum spanning tree (MST).

Because the minimum spanning tree problem is very important in network optimization, researchers have conducted a detailed study of this problem. At present, there are already some classical algorithms for solving the minimum spanning tree in graph theory, such as Kruskal algorithm or Prim algorithm. These algorithms can only get one solution at a time. The characteristic of industrial wireless sensor networks determines that multiple solutions are also necessary and meaningful. These different solutions are mutually complementary and backup. Swarm intelligence algorithm to obtain multiple solutions at a time just can effectively solve this requirement of industrial wireless sensor networks. This paper will use the artificial bee colony algorithm and use the idea of quantum computing to solve this problem.

In this section, simulation experiments are conducted on the newly proposed algorithm to verify the validity of our proposed algorithm.

The industrial wireless sensor network shown in Fig. 6 is used as an example to simulate. The industrial wireless sensor network, represented as G, has 16 nodes and 32 edges. These nodes are deployed in a 500 × 400 rectangular area. Table 1 shows the coordinates of the nodes.The weight function on each edge is the Euclidean distance between two nodes. Table 2 lists the correspondence between edges and nodes, as well as the weight of the edges.

Our new proposed algorithm will be compared with Kruskal algorithm and BABC [40] algorithm. BABC uses the basic artificial bee colony algorithm to solve the minimum spanning tree. It can also obtain multiple spanning tree construction schemes in one calculation. The population size is 20, and the algorithm loops 3000 times. All the algorithms have been coded using C++ in VS 2010. We run all the configurations on an Intel (R) Core (TM) i7-2600 CPU @ 3.40 GHz with 8.00 GB RAM in the Windows 10 Operation System.

Each of the three algorithms runs one time, and the experimental results are compared. First, the Kruskal algorithm is used to handle this example. The Kruskal algorithm can only obtain one solution. The obtained ST (spanning tree) is shown in Table 3. The resulting spanning tree has a weight of 1326.409668. The resulting minimum spanning tree is shown in Fig. 7. The Kruskal algorithm’s calculation time is about 0.05 s.

Tables 4 and 5 are the results obtained after the BABC and QABCST algorithms are run once. As can be seen from Tables 4 and 5, the QABCST algorithm has got more solutions. This is due to the diversity of our replacement strategies. The reason for this result is the persistence of diversity in QABCST’s replacement strategy. Figure 8 is an illustration of the other one (10th in Table 5) of the solutions obtained by the QABCST algorithm.

The following is a comparison of the average performance of the QABCST and BABC algorithms running multiple times. The algorithm is performed 10 times independently to obtain its average performance. Table 6 shows the average of the 10 minimum spanning tree weights. The result of Table 6 about Kruskal is the result of running once. As can be seen from the table, the QABCST algorithm has better performance than BABC.

With the rapid development of wireless sensor networks, wireless devices are increasingly deployed in industrial environments. Compared with common wireless sensor networks, industrial wireless sensor networks have higher requirements for the determinism and reliability of data communications. Therefore, it is particularly important to design reasonable mechanisms for the data aggregation/distribution of IWSNs to ensure the certainty and reliability of the data transmission process. Data collection and distribution in industrial wireless sensor networks can be described using the spanning tree problem in graph theory. Existing classical algorithms such as Kruskal and Prim algorithm can only get one solution at a time. In order to improve reliability, industrial application scenarios need to provide multiple solutions for mutual backup. This paper improves the artificial bee colony algorithm based on the idea of quantum computing and proposes a spanning tree construction algorithm for industrial wireless sensor networks based on quantum artificial bee colony. Finally, our algorithm was verified by experiments. The experimental results show that the algorithm can achieve better performance and can obtain more solutions at the same time. Future work includes increasing a priori knowledge of the network structure to improve search efficiency.