THE VERTEX COVER PROBLEM WITH APPLICATION IN CYBER SECURITY
Link Monitoring for Internet-of-Things-Enabled Wireless Sensor Networks
Demonstration is partly based on work published May 2022 [1]
Intorduction
Wireless sensor networks (WSNs) achieving environmental sensing are fundamental communication layer technologies in the Internet of Things.
Wireless Sensor Networks (WSNs) have become a cornerstone of modern technology, enabling real-time data collection and communication across a myriad of applications, from environmental monitoring to industrial automation.
However, ensuring seamless connectivity while optimizing energy consumption remains a critical challenge.
The Link Monitoring Problem:
Wireless sensor networks (WSNs) do not have a predefined structure to maintain fundamental data-transfer operations. They are crucial communication layer technologies for providing environmental sensing operations in the Internet of Things (IoT). Most of the time, WSNs are deployed for various applications in forests, mines and land borders, where they should bear harsh circumstances.
Link monitoring in WSNs involves identifying the optimal set of communication links between sensors to guarantee reliable data transmission while minimizing energy usage. As the network scales, manually selecting these links becomes increasingly complex and time-consuming. This is where the concept of graph theory and the Minimum Vertex Cover problem step in.
Graph Modeling
To effectively address the link monitoring challenge, we leverage graph theory to model the WSN. Each sensor is represented as a node, and communication links between sensors are depicted as edges. This graphical representation captures the essence of connectivity in the network, providing a foundation for optimizing link monitoring.
A WSN can be modeled as a graph \(G(V,E)\), where \(V\) and \(E\) represent the set of vertices (nodes) and edges (communication links), respectively. A vertex cover of a given undirected graph \(G(V,E)\) is a set \(S ⊆ V\) such that each \(e \in E\) is incident to at least one vertex of \(S\).
Minimum Vertex Cover Concept:
At the heart of our approach lies the concept of Minimum Vertex Cover [2]. This optimization problem aims to find the smallest subset of nodes (vertices) in a graph such that every edge in the graph is incident to at least one of these nodes. In the context of WSNs, the vertices selected for the minimum vertex cover represent the critical sensors that ensure seamless communication throughout the network.
Considering the link monitoring application, the number of monitor nodes should be minimized since they should be equipped with extra software/hardware solutions to monitor the network traffic. On the other side, the optimization version of the minimum vertex cover problem, which aims to solve the problem by selecting the minimum number of nodes to cover the whole graph, is in the NP-Hard complexity class
For example, limiting the link count monitored by a node directly provides energy efficiency for link monitoring applications.
Working example
An example sensor network deployment for a habitat monitoring application is depicted in Figure 1(a), where there are \(12\) nodes in the sensing area and node \(1\) is the sink node.
The graph representation of this network is given in Figure 1(b). In Figure 1(c), link monitoring application for this topology is shown. In this application, each link must be sniffed by one secure point (monitor node) to detect attacks such as packet injection and data manipulation. The red nodes (nodes \(1, 3, 4, 5, 6\) and \(8\)) are secure points that are assigned to control message traffic in Figure 1(c). Red arrows show the assigned links to the monitor nodes in the same figure. For example, the links \((8,9)\) and \((8,10)\) are monitored by node \(8\)
This architecture can also be used in other common operations such as backbone formation, clustering and routing. Red nodes can be cluster heads, and ordinary nodes can send their data to the cluster heads to achieve data aggregation.
The network induced by red nodes is a virtual backbone that can carry messages to the sink node. By accomplishing the clustering and backbone formation operations, the data packets can be routed from ordinary nodes to the sink node.
Minimum Vertex Cover Mathematical Formulation
The Min Vertex Cover problem can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO):
Minimize: \(\sum_{i \in V} x_i\)
Subject to: \((1 - x_i)(1 - x_j)=0 \quad \forall (i,j) \in E_0\) and \(x_i \in \{0, 1\} \quad \forall i \in V\)
Where:
-
\(x_i\) is a binary variable that equals 1 if node \(i\) is in the cover and 0 otherwise
-
\(E_0\) is the set of all edges (connected and not connected)
-
\(V\) is the set of vertices in the graph
Solving with Classiq
We go through the steps of solving the problem with Classiq, using QAOA algorithm [2].
Quantum Approximate Optimization Algorithm (QAOA)
QAOA is a quantum algorithm designed to solve combinatorial optimization problems, making it an ideal candidate for tackling the Minimum Vertex Cover problem in large-scale WSNs.
Applying QAOA to the modeled graph, we iteratively adjust parameters to navigate the solution space and identify the minimum vertex cover. Quantum computing's unique ability to explore multiple solution candidates simultaneously accelerates the optimization process, significantly outperforming classical algorithms for complex problems.
import classiq
from typing import cast
import networkx as nx
import numpy as np
import pyomo.core as pyo
from IPython.display import Markdown, display
from matplotlib import pyplot as plt
Building the working example graph
We can start by building and viewing a modeled graph to fit the working example above:
import networkx as nx
edge_dict = {
1: [2, 3, 4, 5],
2: [1, 3, 4],
3: [1, 2, 7, 12],
4: [1, 2, 6],
5: [1, 11],
6: [4, 8],
7: [3],
8: [6, 9, 10],
9: [8],
10: [8],
11: [5],
12: [3],
}
WSN_network_graph = nx.Graph()
WSN_network_graph.add_nodes_from([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])
for u in range(1, 12):
for v in edge_dict[u]:
WSN_network_graph.add_edge(u, v)
nx.draw(WSN_network_graph, with_labels=True, font_color="whitesmoke")
Building the optimization model from a graph input
To build the optimization model we will utilize Pyomo. Pyomo is a Python-based, open-source optimization modeling language with a diverse set of optimization capabilities. We will formalize our QUBO model into a pyomo model object.
Classiq seamlessly incorporates the pyomo object into its Model
We proceed by defining the pyomo model that will be used to build a Classiq Model. Using the mathematical formulation defined above:
import networkx as nx
import pyomo.core as pyo
def mvc(graph: nx.Graph) -> pyo.ConcreteModel:
model = pyo.ConcreteModel()
model.x = pyo.Var(graph.nodes, domain=pyo.Binary)
nodes = list(graph.nodes())
@model.Constraint(graph.edges)
def full_cover(model, i, j):
# all sets are covered
return ((1 - model.x[i]) * (1 - model.x[j])) == 0
def obj_expression(model):
# number of nodes selected
return sum(model.x.values())
model.cost = pyo.Objective(rule=obj_expression, sense=pyo.minimize)
return model
The model contains:
-
Binary variable declaration for each node (model.x) indicating whether the variable is chosen for the set.
-
Constraint rule – ensures that all edges are covered.
-
Objective rule – minimize the number of nodes selected.
mvc_model = mvc(WSN_network_graph)
mvc_model.pprint()
2 Set Declarations
full_cover_index : Size=1, Index=None, Ordered=False
Key : Dimen : Domain : Size : Members
None : 2 : Any : 13 : {(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (3, 7), (3, 12), (4, 6), (5, 11), (6, 8), (8, 9), (8, 10)}
x_index : Size=1, Index=None, Ordered=False
Key : Dimen : Domain : Size : Members
None : 1 : Any : 12 : {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
1 Var Declarations
x : Size=12, Index=x_index
Key : Lower : Value : Upper : Fixed : Stale : Domain
1 : 0 : None : 1 : False : True : Binary
2 : 0 : None : 1 : False : True : Binary
3 : 0 : None : 1 : False : True : Binary
4 : 0 : None : 1 : False : True : Binary
5 : 0 : None : 1 : False : True : Binary
6 : 0 : None : 1 : False : True : Binary
7 : 0 : None : 1 : False : True : Binary
8 : 0 : None : 1 : False : True : Binary
9 : 0 : None : 1 : False : True : Binary
10 : 0 : None : 1 : False : True : Binary
11 : 0 : None : 1 : False : True : Binary
12 : 0 : None : 1 : False : True : Binary
1 Objective Declarations
cost : Size=1, Index=None, Active=True
Key : Active : Sense : Expression
None : True : minimize : x[1] + x[2] + x[3] + x[4] + x[5] + x[6] + x[7] + x[8] + x[9] + x[10] + x[11] + x[12]
1 Constraint Declarations
full_cover : Size=13, Index=full_cover_index, Active=True
Key : Lower : Body : Upper : Active
(1, 2) : 0.0 : (1 - x[1])*(1 - x[2]) : 0.0 : True
(1, 3) : 0.0 : (1 - x[1])*(1 - x[3]) : 0.0 : True
(1, 4) : 0.0 : (1 - x[1])*(1 - x[4]) : 0.0 : True
(1, 5) : 0.0 : (1 - x[1])*(1 - x[5]) : 0.0 : True
(2, 3) : 0.0 : (1 - x[2])*(1 - x[3]) : 0.0 : True
(2, 4) : 0.0 : (1 - x[2])*(1 - x[4]) : 0.0 : True
(3, 7) : 0.0 : (1 - x[3])*(1 - x[7]) : 0.0 : True
(3, 12) : 0.0 : (1 - x[3])*(1 - x[12]) : 0.0 : True
(4, 6) : 0.0 : (1 - x[4])*(1 - x[6]) : 0.0 : True
(5, 11) : 0.0 : (1 - x[5])*(1 - x[11]) : 0.0 : True
(6, 8) : 0.0 : (1 - x[6])*(1 - x[8]) : 0.0 : True
(8, 9) : 0.0 : (1 - x[8])*(1 - x[9]) : 0.0 : True
(8, 10) : 0.0 : (1 - x[8])*(1 - x[10]) : 0.0 : True
5 Declarations: x_index x full_cover_index full_cover cost
Since node \(1\) is our WSN sink node we will force it into the Vertex Cover solution as follows:
mvc_model.x[1].fixed = True
mvc_model.x[1].value = 1
We are set to go!
1. Build a Classiq Model
We will utilize construct_combinatorial_optimization_model function to create our Model object.
As input for this function we will define the quantum configuration of the QAOA algorithm though the QAOAConfig object where the number of repetitions (num_layers) is defined:
from classiq import construct_combinatorial_optimization_model
from classiq.applications.combinatorial_optimization import OptimizerConfig, QAOAConfig
qaoa_config = QAOAConfig(num_layers=1)
For the classical optimization part of the QAOA algorithm we define the classical optimization configuration through the OptimizerConfig object where the maximum number of classical iterations (max_iteration) and the \(\alpha\)-parameter (alpha_cvar) for running CVaR-QAOA, an improved variation of the QAOA algorithm [3], are defined:
optimizer_config = OptimizerConfig(max_iteration=60, alpha_cvar=0.9)
Lastly, we load the Classiq model, based on the problem and algorithm parameters, which we can than use to solve the problem:
qmod = construct_combinatorial_optimization_model(
pyo_model=mvc_model,
qaoa_config=qaoa_config,
optimizer_config=optimizer_config,
)
Our Classiq Model (qmod) already incorporates the QAOA execution logic. However, we can set the quantum backend we wish to execute on so the Classiq synthesis engine will take it into consideration when generating an optimized Quantum Circuit:
from classiq import set_execution_preferences
from classiq.execution import ClassiqBackendPreferences, ExecutionPreferences
backend_preferences = ExecutionPreferences(
backend_preferences=ClassiqBackendPreferences(backend_name="simulator")
)
qmod = set_execution_preferences(qmod, backend_preferences)
from classiq import write_qmod
write_qmod(qmod, "link_monitoring")
The above file can also be loaded to our web IDE for further analysis and ease of execution.
2. Generate a parameterized Quantum Circuit
synthesize our Model and view the QAOA circuit (ansatz) used to solve the optimization problem:
from classiq import show, synthesize
qprog = synthesize(qmod)
show(qprog)
Opening: https://platform.classiq.io/circuit/8e647b73-8bbd-4cb4-8239-4c56d92fe7ef?version=0.41.0.dev39%2B79c8fd0855
3. Execute the circuit: optimize parameters to get the optimal solution
execute method:
from classiq import execute
res = execute(qprog).result()
Analyzing the execution results
Energy convergence
First, let's check the Energy convergence through the iterations:
from classiq.execution import VQESolverResult
vqe_result = VQESolverResult.parse_obj(res[0].value)
vqe_result.convergence_graph
Optimization Results
We can also examine the statistics of the algorithm:
import pandas as pd
from classiq.applications.combinatorial_optimization import (
get_optimization_solution_from_pyo,
)
solution = get_optimization_solution_from_pyo(
mvc_model, vqe_result=vqe_result, penalty_energy=qaoa_config.penalty_energy
)
optimization_result = pd.DataFrame.from_records(solution)
optimization_result.sort_values(by="cost", ascending=True).head(5)
| probability | cost | solution | count | |
|---|---|---|---|---|
| 58 | 0.003 | 5.0 | [0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0] | 3 |
| 14 | 0.006 | 5.0 | [1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0] | 6 |
| 23 | 0.005 | 5.0 | [1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0] | 5 |
| 125 | 0.002 | 6.0 | [0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0] | 2 |
| 134 | 0.002 | 6.0 | [1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0] | 2 |
And the histogram:
optimization_result.hist("cost", weights=optimization_result["probability"])
array([[<Axes: title={'center': 'cost'}>]], dtype=object)
Plot the optimal solution!
best_solution = optimization_result.solution[optimization_result.cost.idxmin()]
best_solution
[1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0]
WSN_network_graph.nodes
NodeView((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12))
def draw_solution(graph: nx.Graph, solution: list):
solution_nodes = [v for v in graph.nodes if solution[v - 1]]
solution_edges = [
(u, v) for u, v in graph.edges if u in solution_nodes or v in solution_nodes
]
nx.draw_kamada_kawai(graph, with_labels=True)
nx.draw_kamada_kawai(
graph,
nodelist=solution_nodes,
edgelist=solution_edges,
node_color="r",
edge_color="y",
)
draw_solution(WSN_network_graph, best_solution)
Larger scale models
TBD
References
[1]: Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks
[2]: Solving Vertex Cover via Ising Model on a Neuromorphic Processor
[3]: Barkoutsos, Panagiotis Kl, et al. "Improving variational quantum optimization using CVaR." Quantum 4 (2020): 256.