Large Scale Energy Efficient Sensor Network Routing Using a Quantum Processor Unit

Summary

This study provides a method to use a quantum processor unit to compute the routes for various traffic dynamics that work to outperform classical methods in literature to maximize network lifetime.

Abstract

The sensor network energy conservation method, which is a usage hybrid of a classical computer and quantum processor, has proved to perform better than the heuristic algorithm using a classical computer. In this manuscript, the technical context for the significance of the method is presented and justified. Then the experimental steps are demonstrated in an operational sequence with illustrations if ever needed. The method has been validated by positive results across a randomly generated sample set of network topologies. The successful experimental results of this method have provided a better approach for sensor network lifetime maximization problems and demonstrated that the current state of art quantum processor has been able to solve large practical engineering problems with merits that override current methods in the literature. In other words, quantum advantage can be exploited to best efforts. It has gone beyond the stage of proof of concept to proof of feasibility.

Introduction

Energy conservation in sensor networks has been a very critical issue in design¹. Classical methods normally tackle the problem using an ad hoc approach^2,3,4,5,6. That said, these methods emulate the sensor nodes as individually managed intelligent assets that could also cooperate to serve both the interests of the individual and the community. Due to the volatile environment where sensors work, in some works, random algorithms are introduced in order to capture the environmental uncertainties, while in others, bio-intelligence is borrowed to devise heuristic algorithms that could achieve common sense acceptable results⁷. To illustrate further, for those random algorithms, for one hand, environmental uncertainties might not be as random as the random sequence generated by a classical CPU, for the other hand, even if the environmental uncertainties are absolutely random, they could not be captured by the random process simulator generated by classical CPU; for those bio-intelligence algorithms, first of all, no rigorous mathematical analysis has been derived to make a conceptual proof work, secondly, the convergence to truth or the error tolerance boundary can only be configured given an informed ground truth - though a significant amount of works in literature have demonstrated to some extent these heuristic algorithms work, for one thing, these algorithms are analyzed (not simulated) against well-defined use case scenarios, they stops at certain criteria that are still worth pondering in further research, for another, as said before, a majority of the algorithms have not been validated against software simulation that can be more readily deployed in the microprocessors that make a sensor into its being⁸.

We do not consider machine learning (ML) here because it needs to employ data analytics which requires a relatively large volume of computational power that is not portable in sensor devices⁹.

To address the above-mentioned concerns, we provide a hybrid quantum algorithm. The algorithm is hybrid in that the cluster head selection mechanism is implemented using a classical random algorithm during the routing computations conducted using a quantum processor once the network topology is set up. The method is justified as follows: (1) As discussed in the first paragraph regarding the environmental uncertainties, we do not want to endeavor further to apply a quantum sequence generator to capture the environmental dynamic because it might be historically traceable. The environmental dynamic that can be historically traceable has been justified by various machine learning research works in network science. For the current stage, we stay with the classical approach. (2) The exact method that relies on abstract mathematical analysis guarantees to arrive at ground truth. Quantum experimental physics has so far been sophisticatedly supported by physical mathematics. Moreover, algorithm applications like the Shor algorithm¹⁰ have existed to prove this rounded theory.

An adequate amount of literature survey is provided below for comparison. The HEESR protocol proposed¹¹ has demonstrable merits in results, but the authors have specified the simulation configuration parameters well, for example, the exact random distribution function of the node position, the proper justification of the cluster head percentage p (0.2%), and the scaling parameter for distribution of energy level (1-2 joules) among nodes a_i. It prohibited the author from proceeding further to duplicate the experiments and conduct the comparison. The Power routing mechanism¹² employs the curve fitting method to approximate converged continuous functions from discrete data sets obtained from unspecified sample space for determinants that impact the decision process of the optimal network routing. The curve fitting method¹³ requires prior information on the network topology. Real circumstances might not have prior information readily available. Even when prior information exists, network topology might not be regular enough to be able to be mapped onto fitting curves that are able to facilitate derivable computation. Following the same logic, DORAF protocol¹⁴ has not justified how and why to borrow the Boltzmann function and Logistic Function to approximate the network determinants. Ismail et al.¹⁵ have provided a sound reference for future research endeavors into energy-efficient routing protocol design in the underwater network.

Protocol

1. Setting up Dwave Ocean Environment

1. Download and install the ocean tools from the link: https://docs.ocean.dwavesys.com/en/stable/overview/install.html
   1. At the terminal, type python -m venv ocean.
   2. At the terminal, type . ocean/bin/activate, as shown in Figure 1.
   3. At the terminal, type git clone https://github.com/dwavesystems/dwave-ocean-sdk.git
      Next, type cd dwave-ocean-sdk, as shown in Figure 2.
      Then, type python setup.py install

Figure 1: Ocean virtual environment activation. Ocean package, as D-wave API integrated, provides a cloudy user experience over the user's own computer to the D-wave machine premise. Please click here to view a larger version of this figure.

Figure 2: Ocean SDK installation. Ocean package provides necessary tool kits for developers, including a handy Cplex installation. Please click here to view a larger version of this figure.

2. Installation of Cplex Python API interface

1. Download and install Cplex: https://pypi.org/project/cplex/
   1. At the terminal, type pip install cplex.

3. Experiment configuration parameters

1. Set up the experiment configuration parameters mentioned in Table 1 using Python programming notation in the script, as shown in Supplementary Figure 1. Once the script is run and executed, the underlying language will process to store the variables in RAM. A screenshot of the Python codes where the parameters are assigned values respectively is attached (Supplementary Figure 1).

d0	87.7085 m
E	50 * 1 x 10-09 joules
epson_fs	1 * 10-12* 10 joules
epson_mp	0.0013 * 1 * 10-12 joules
packet size	4000 bits

Table 1: Energy model parameter and packet size settings.

Supplementary Figure 1: Script1. Script to set up the experiment parameters. Please click here to download this File.

4. Python scripts

1. Prepare the Python scripts to generate 198 sensor node 2D positions that are equally scattered into six sectors that divide the circular area with a radius of 50 m.
   NOTE: The circular graph is segmented into 6 sectors. In each sector, the position of each node is treated with two corresponding variables. One is the angle, and the other is the radius. Assign values to both angle and radius using a uniform random distribution generator. The detailed procedure is shown in Supplementary Figure 2 and Supplementary Figure 3.
2. Within each sector, ensure that the 33 sensor nodes are scattered randomly by a normal distribution. Save the 2D positions into text files by each sector under the name spelling rule as 'posdata'+sector_no+'.txt' (Figure 3 and Figure 4).
   1. Segment the circular area with a radius of 50 m into six sectors. The starting angular values for these six sectors make the vector A= [60,120,180,240,300,360].
      1. Suppose the sector index is i, set the pole length for j^th sensor node as l_{i,j}=50*random.random()
      2. Suppose the sector index is i, set the angular value for j^th sensor node as ang_{i,j}=(60*random.random() + A_i - 60) * 2 * pi / 360
      3. Set the Cartesian coordinates of the j^th sensor node in i^th sector as
         x_{i,j}=l_{i,j}*cos(ang_{i,j})
         y_{i,j}=l_{i,j}*sin(ang_{i,j})

Supplementary Figure 2: Script2. Script to configure the two dimension position locations for each node by sector. Please click here to download this File.

Supplementary Figure 3: Script3. Script to configure each node position values within 1 sector. Please click here to download this File.

Figure 3: Node positions generated and stored separated into 6 files each corresponding to one sector. Two-dimension position locations are saved in 6 posdata+'idx' files. Each presents a sector. Please click here to view a larger version of this figure.

Figure 4: Node positions stored in sector 0. The positions are in two dimensions and generated using a uniform random generator. The first column is the horizontal locations, and the second column is the vertical locations. Please click here to view a larger version of this figure.

5. Preparing the initial energy levels

1. Prepare the initial energy levels for all 198 sensor nodes. Assign half of them with initial energy at 0.5 J and the other half with initial energy at 1 J. Create an array to store each node's energy level, and use a loop to assign cells sequenced in even numbers the value 1 and those sequenced in odd numbers the value of 0.5. Supplementary Figure 4 shows the Python codes, and the result is shown in Figure 5.

Supplementary Figure 4: Script4. Script to assign half of the node's energy of 1 joule and the other 0.5 joules. Please click here to download this File.

Figure 5: Energy_buffer initial assignment. Half of the nodes are assigned with energy 1 joule, while the other halves are assigned with 0.5 joules. Please click here to view a larger version of this figure.

6. Preparing Advanced_Leach algorithm script (Figure 6 and Figure 7)

1. Prepare a functional script where the cluster head is selected and the cluster is formed.
   NOTE: The cluster is selected using a loop on the condition that the number of cluster heads selected is less than the overall number of nodes divided by 6. The condition is to ensure that within each cluster, the source node amount is equal to or less than 6. Within the loop, each node is assigned a random number between [0,1]. Those smaller than a given criteria number become the cluster head, while others become the source nodes. The detailed procedure is shown in Supplementary Figure 5. Then given a fixed pool of cluster heads, the rest of the source nodes select their cluster heads within the shortest distance, given that the cluster head has not hosted more than 6 source nodes yet. The detailed procedure is shown in Supplementary Figure 6.
   1. Set T_n=P/(1-P*(count%(1/P))), where P = 0.2 (the proportional rate of the number of cluster heads to the overall network size) and the count is the amount of transmission round up to date.
   2. For each sensor node, attain a random number between[0,1] threshold_rm = random.random()
      1. If threshold_rm is less than T_n, select this sensor node as the cluster head.
   3. For each of the non-cluster_head nodes, select the closest cluster head sensor node to it as its cluster head. Given a fixed pool of cluster heads, the rest of the source nodes select their cluster heads within the shortest distance, given that the cluster head has not hosted more than 6 source nodes yet. The detailed procedure is shown in Supplementary Figure 6.
2. Prepare the command lines to calculate the energy depletion process across the whole network for this round. For each run of the algorithm that completes one batch of deliveries of the packets from source nodes to the sink, the energy storage array as prepared will be updated to have reduced cell by cell in values. The energy consumption along the path will be the summation of energy consumption per node-to-node route, which is calculated according to an energy model¹. The detailed procedure is shown in Supplementary Figure 7.
3. Calculate the required transmission round metrics.
   NOTE: Per each run of the algorithm to complete one batch of packet delivery, the energy array is updated, the run amount and the number of drained-out nodes are counted. If the value is larger or equal to 1, then FND (first node die) is equal to current run amount. If the value is larger or equal to half of the node amount, then HND(half node die) is equal to current run amount. If the value is equal to the overall node amount, then AND(all node die) is equal to current run amount. The detailed procedure is shown in Supplementary Figure 8.

Figure 6: Cluster head array. The sequence numbers of the nodes that have been selected to be the cluster heads. Please click here to view a larger version of this figure.

Figure 7: Cluster head index array. As there are six sectors, each with 33 sensor nodes, in the cluster head index array, the number indicates the sequence number of the cluster head the corresponding sensor node belongs to. The position index of the array corresponds to the sequence number of each sensor node. For the sensor node that is selected as the cluster head, the number assigned to its slot in the array is the sequence number of itself. Please click here to view a larger version of this figure.

Supplementary Figure 5: Script5. Script to select the cluster head. Please click here to download this File.

Supplementary Figure 6: Script6. Script to assign source nodes to clusters. Please click here to download this File.

Supplementary Figure 7: Script7. Script to update the energy buffer for all source nodes via reduction of the amount of energy consumed through transmission. Please click here to download this File.

Supplementary Figure 8: Script8. Script to calculate the amount of rounds up to which the first node dies, and half of the nodes die. Please click here to download this File.

7. Preparing hybrid quantum algorithm script

1. Prepare a functioning script where the cluster head is selected and the cluster head is formed.
   1. As the maximum cluster size is 6 in this experiment¹, ensure that the amount of cluster heads is no less than current_valid_node_amount/6, the selection procedure will be run in a loop until this criterion is met.
      NOTE: If current_valid_node_amount is no larger than 6, then these valid nodes form one and only cluster themselves.
   2. For each of the non-cluster_head_valid nodes, calculate the distance of it to each of the selected cluster heads, and assign to it the cluster head whose cluster size has not exceeded 6 where the distance value is the smallest.
      NOTE: In Figure 8, all the non-cluster_head_valid nodes' distances to the selected cluster head 24 are calculated, and all the selected cluster head is displayed in Figure 9. Figure 10 displays all the nodes are assigned to their corresponding cluster head, and Figure 11 shows grouping each cluster's member nodes in a vector array.
2. Prepare the sub-function script, where the routing optimization problem per cluster is formed and submitted to the D-wave API (Figure 12). The routing paths are computed cluster by cluster.
3. Using Python script, calculate the energy depletion process across the whole network to quantitatively evaluate the algorithm by network lifetime in terms of the number of transmission rounds.
   NOTE: For each run of the algorithm that completes one batch of deliveries of the packets from source nodes to the sink, the energy storage array as prepared will be updated to have reduced cell by cell in values. The energy consumption along the path will be the summation of energy consumption per node-to-node route, calculated according to an energy model¹. The detailed procedure is shown in Supplementary Figure 7.
4. Using Python script, record the moment when the first node is drained out and when half the nodes are drained out. The detailed procedure is shown in Supplementary Figure 8.

Figure 8: toClusterHeadDistance Array for non-cluster_head node with index 24. The first column is the distance and the second column is the cluster head index number Please click here to view a larger version of this figure.

Figure 9: CHID_buff array. Sequence numbers of the sensor nodes that are selected as the cluster heads. Please click here to view a larger version of this figure.

Figure 10 CHIdx_buff array. Assigned cluster head sensor nodes' sequence number to each corresponding sensor node. Please click here to view a larger version of this figure.

Figure 11: CH_BUFF array. Cluster group per cluster head sensor nodes corresponding to the array CHID_buff. Each cluster group consists of 0 or more than 0 sensor nodes. Each cluster group array displays the sequence numbers of sensor nodes that are in it. Please click here to view a larger version of this figure.

Figure 12: Routing path computation per sector. For each sector, the routing paths for all source nodes are computed. Please click here to view a larger version of this figure.

Representative Results

Results from one run sample are shown in Table 2, Table 3, and Table 4. The detailed datasets for the three batches of data are available in the Supplementary Data 1 folder.

Dataset 1
198 nodes in a circular area with a radius of 50m	Hybrid Quantum Algorithm	Advanced_Leach Algorithm
FND	1442	727
HND	2499	1921

Table 2: Batch 1 of results from the experiment.

Dataset 2
198 nodes in a circular area with a radius of 50m	Hybrid Quantum Algorithm	Advanced_Leach Algorithm
FND	757	1463
HND	1925	2500

Table 3: Batch 2 of results from the experiment.

Dataset 3
198 nodes in a circular area with a radius of 50m	Hybrid Quantum Algorithm	Advanced_Leach Algorithm
FND	790	1461
HND	1888	2500

Table 4: Batch 3 of results from the experiment.

Three metrics are selected with definitions⁴ as below:
FND - first node die. The number of transmissions round up to which the first sensor node energy is drained out;
HND - half node die. The number of transmissions rounds up to which half amount of the sensor nodes' energy is drained out;
LND - last node die. The number of transmissions rounds up to which the whole sensor network is dead.

From the results, we can see that the hybrid quantum algorithm has more efficiency than the advanced_leach algorithm.

Further results of the time complexity of the proposed method and the compliance plot are shown in Figure 13 and Figure 14, respectively.

Figure 13: Time complexity of the Hybrid Quantum algorithm. Time in the unit of second spent in running one cycle of HQA across various network sizes. Please click here to view a larger version of this figure.

Figure 14: Results of the Hybrid Quantum algorithm that complies with the Advanced Leach algorithm. FND and HND or HQA and ALA share a similar plot shape pattern. Please click here to view a larger version of this figure.

Supplementary Data 1: Dataset of the three batches of experiments performed in this study. Please click here to download this File.

Discussion

The current state-of-the-art commercial quantum processor can be used in computational problems of any network topology¹. Quantum processor application is not constrained by the number of physical qbits any of the quantum processors has been able to implement.

In sensor network lifetime prolongation design, the results show an advancement in method to achieve even longer network life by using a quantum processor. The results imply that quantum advantage is ready to be exploited commercially in both public and private sectors.

For managerial implications, Quantum Advantage is able to be the next milestone to pave a promising way for near-future Hi-Tech sustainable prosperity. Current Hi-Tech, in terms of Learning-strategy and/or Artificial Intelligence (AI), requires in any method the power drive to process/hold the data. From a high-level perspective of Green Globe, it does not stand out as a good candidate¹⁶. ML/AI though it makes computation more economically efficient, does not provide a root cause analytical solution because efficient computing is traded off by high-power computational facilities. Therefore, they are fundamentally bounded by the high-performance computer (HPC). Quantum computing which revolutionizes the computing paradigm, has proved effective in computing faster than legacy computers across multiple practical trial applications^17,18. Quantum-assisted ML, as far as the author is concerned, is PML (probabilistic machine learning). ML algorithm (script/high-low level programming language) runs on a computing device that can be either a classical computer or quantum computing. Given the same ML algorithm of executable command lines n, let f_cc(n) indicate the consumption in computation for classical computers and f_qc(n) indicate the consumption in computation for quantum computers. f_cc(n) is a weighted summation of computational consumption of classical computer executable alpha_i for the n command lines. f_qc(n) is an equally weighted summation of computational consumption of quantum computer executable alpha_j for the equally same n command lines. The weights stay unchanged as the upper-level ML command lines are equally the same. Simply put, this work and previous work¹ have shown that alpha_j is always less than alpha_i so f_qc(n) is always less than f_cc(n).

Regarding academic Implications, previously established processors/computing facilities are conventionally used to help researchers think/generate/develop their ideas and plans. Quantum computing indicates researchers' methodological approach awaits an epic evolution. It could be disruptive but optimistically. From now on, researchers not used to theoretical algorithm design/analysis need to work hand in hand to devise/generate quantum algorithms to solve their research topic. Most quantum algorithms for practical research are not handily available. In one sentence, researchers' computing devices changed. Virtual environment setup and QPU API completely rely on a satisfactory internet connection.

Limitations of the study include (i) Link capacity has not been considered¹. The packet loss rate is ignored. Future works will consider the underlying sensor networking protocol to appropriately formulate the problem considering both energy consumption and loss control (either with a re-transmission scheme or not). (ii) Network topology is assumed to be known beforehand. Node positions are fixed. (iii) Time required to run the hybrid quantum algorithm per round is longer than the Advanced Leach algorithm but with higher accuracy. (iv) The algorithm could not work offline.

Materials

Name	Company	Catalog Number	Comments
Dell Laptop	Dell	N/A
Ubuntu 18.04.6 LTS	Canonical Ltd	18.04.6 LTS
Python3.8	Python Software Foundation	3.8.0
Dwave QPU	Dwave	https://docs.ocean.dwavesys.com/en/stable/overview/install.html