> ## Documentation Index
> Fetch the complete documentation index at: https://prod-mint.classiq.io/llms.txt
> Use this file to discover all available pages before exploring further.
# Vertex Cover Link Monitoring for IoT-Enabled Wireless Sensor Networks
Open this notebook in GitHub to run it yourself
***This tutorial is partly based on work published in May 2022 \[[1](#wsn)].***
Wireless sensor networks (WSNs) for environmental sensing are fundamental communication layer technologies in the Internet of Things (IoT).
WSNs are 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.
This tutorial delves into a technique for tackling the challenge of solving WSN link monitoring through the lens of the Minimum Vertex Cover (MVC) problem using Classiq.
## The Link Monitoring Problem
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 IoT.
Most of the time, WSNs are deployed for various applications in forests, mines, and land borders, where they must 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 use. As the network scales, manually selecting these links becomes increasingly complex and time-consuming.
This is where the concept of graph theory and the MVC problem step in.
#
## Graph Modeling
To effectively address the link monitoring challenge, this tutorial leverages 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$ where each $e \in E$ is incident to at least one vertex of $S$.
#
## MVC Concept
At the heart of the approach lies the concept of the Minimum Vertex Cover \[[2](#mvc)].
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 MVC represent the critical sensors that ensure seamless communication throughout the network.
Vertex cover is a useful structure for WSN applications such as routing, clustering, backbone formation, link monitoring, replica management, and network attack protection.
Considering the link monitoring application, the number of monitor nodes should be minimized since they are equipped with extra software/hardware solutions to monitor the network traffic. On the other side, the optimization version of the MVC 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 of 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)*. *Figure 1(c)* shows the link monitoring application for this topology. 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 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.**
Figure
1. An example of a link monitoring application for the vertex cover problem: (a) Deployment of a sample WSN; (b) Graph representation of the topology; (c) Link monitoring application on the topology.
#
## MVC Mathematical Formulation
The MVC 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 MVC with Classiq and QAOA
Follow the steps for solving the MVC problem with Classiq using the Quantum Approximate Optimization Algorithm (QAOA) \[[2](#qaoa)].
QAOA is a quantum algorithm designed to solve combinatorial optimization problems, making it an ideal candidate for tackling the MVC problem in large-scale WSNs.
Apply QAOA to the modeled graph, iteratively adjusting the parameters to navigate the solution space and identify the MVC.
Quantum computing's unique ability to explore multiple solution candidates simultaneously accelerates the optimization process, significantly outperforming classical algorithms for complex problems.
To solve the link monitoring problem with Classiq:
1. Build a Classiq model.
2. Generate a parameterized quantum circuit.
3. Execute the circuit and optimize parameters to get the optimal solution.
```python theme={null}
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
from classiq import *
```
#
## Building the Working Example Graph
Build and view a modeled graph to fit the working example above:
```python theme={null}
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 Graph Input
To build the optimization model, use Pyomo, a Python-based, open-source optimization modeling language with a diverse set of optimization capabilities.
Formalize the QUBO model into a Pyomo model object. **Classiq seamlessly incorporates the Pyomo object into its model.**
Define the Pyomo model that is used to build a Classiq model using the mathematical formulation defined above:
```python theme={null}
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
* a binary variable declaration for each node (model.x), indicating whether the variable is chosen for the set.
* a constraint rule ensuring that all edges are covered.
* an objective rule that minimizes the number of selected nodes.
```python theme={null}
mvc_model = mvc(WSN_network_graph)
```
```python theme={null}
mvc_model.pprint()
```
**Output:**
```
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 the WSN sink node, force it into the vertex cover solution as follows:
```python theme={null}
mvc_model.x[1].fixed = True
mvc_model.x[1].value = 1
```
**You are set to go!**
#
##
1. Building a Classiq Model
Utilize the `construct_combinatorial_optimization_model` function to create the model object.
As input for this function, define the quantum configuration of the QAOA algorithm though the `QAOAConfig` object where the number of repetitions (`num_layers`) is defined:
```python theme={null}
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, 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](#cvar)]—are defined:
```python theme={null}
optimizer_config = OptimizerConfig(max_iteration=60, alpha_cvar=0.9)
```
Load the Classiq model, based on the problem and algorithm parameters, which you can than use to solve the problem:
```python theme={null}
qmod = construct_combinatorial_optimization_model(
pyo_model=mvc_model,
qaoa_config=qaoa_config,
optimizer_config=optimizer_config,
)
```
The Classiq model (`qmod`) already incorporates the QAOA execution logic. However, you can set the quantum backend on which to execute so the Classiq synthesis engine takes it into consideration when generating an optimized quantum circuit:
```python theme={null}
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)
```
That's it! The Classiq model is set!!
#
##
2. Generating a Parameterized Quantum Circuit
Simply `synthesize` the model and view the QAOA circuit (ansatz) used to solve the optimization problem:
```python theme={null}
from classiq import show, synthesize
qprog = synthesize(qmod)
show(qprog)
```
**Output:**
```
Quantum program link: https://platform.classiq.io/circuit/2wJCSZm2PCV7kHiFldLj3o8HNjx?login=True&version=0.76.0
```
#
##
3. Executing the Circuit: Optimizing Parameters to Get the Optimal Solution
To solve the problem using the generated quantum program, use the `execute` method:
```python theme={null}
from classiq import execute
result = execute(qprog).result_value()
```
#
##
4. Analyzing the Energy Convergence Execution Results
Check the energy convergence through the iterations:
```python theme={null}
from classiq.execution import VQESolverResult
vqe_result = VQESolverResult.parse_obj(result)
vqe_result.convergence_graph
```
Examine the optimization results statistics of the algorithm:
```python theme={null}
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 |
| --- | ----------- | ---- | ------------------------------------- | ----- |
| 37 | 0.002930 | 5.0 | \[1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0] | 6 |
| 2 | 0.004395 | 5.0 | \[1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0] | 9 |
| 10 | 0.003906 | 5.0 | \[0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0] | 8 |
| 104 | 0.002441 | 6.0 | \[1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1] | 5 |
| 96 | 0.002441 | 6.0 | \[1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0] | 5 |
View the histogram:
```python theme={null}
optimization_result.hist("cost", weights=optimization_result["probability"])
```
**Output:**
```
array([[]], dtype=object)
```
Plot the optimal solution:
```python theme={null}
best_solution = optimization_result.solution[optimization_result.cost.idxmin()]
```
```python theme={null}
best_solution
```
**Output:**
```
[1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0]
```
```python theme={null}
WSN_network_graph.nodes
```
**Output:**
```
NodeView((1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12))
```
```python theme={null}
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)
```
You obtained a set of vertices that form the MVC! These vertices correspond to the critical sensors that need to be monitored and maintained for optimal link connectivity.
The outcome is a comprehensive link monitoring strategy that ensures efficient data transmission while conserving energy.
#
## Larger Scale Models
TBD
Solving the WSN link monitoring challenge through the MVC problem and QAOA highlights the transformative potential of quantum computing in addressing real-world optimization problems. By combining graph theory, quantum algorithms, and practical applications, we open the door to enhanced connectivity, energy efficiency, and the seamless functioning of wireless sensor networks. As technology continues to evolve, the synergy between these methodologies will shape the future of network optimization.
## References
\[1] [Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks.](https://www.researchgate.net/publication/360630980_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.](https://vmonaco.com/papers/Solving%20Vertex%20Cover%20via%20Ising%20Model%20on%20a%20Neuromorphic%20Processor.pdf)
\[3] [Barkoutsos, Panagiotis Kl, et al. "Improving variational quantum optimization using CVaR." Quantum 4 (2020): 256.](https://arxiv.org/abs/1907.04769)