Skip to content

Vertex Cover Link Monitoring for IoT-Enabled Wireless Sensor Networks

View on GitHub Experiment in the IDE

This tutorial is partly based on work published in May 2022 [1].

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.

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]. 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.

Screenshot 2025-04-27 at 13.17.02.png

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 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.

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:

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")

png

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:

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.

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 the WSN sink node, force it into the vertex cover solution as follows:

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:

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]—are defined:

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:

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:

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!!
Write the model to file, then view all quantum configurations and execution logic.

from classiq import write_qmod

write_qmod(qmod, "link_monitoring")

You can load the above file to the Classiq web IDE for further analysis and ease of execution.

2. Generating a Parameterized Quantum Circuit

Simply synthesize the model and view the QAOA circuit (ansatz) used to solve the optimization problem:

from classiq import show, synthesize

qprog = synthesize(qmod)
show(qprog)

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:

from classiq import execute

result = execute(qprog).result_value()

4. Analyzing the Energy Convergence Execution Results

Check the energy convergence through the iterations:

from classiq.execution import VQESolverResult

vqe_result = VQESolverResult.parse_obj(result)
vqe_result.convergence_graph

png

Examine the optimization results 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
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:

optimization_result.hist("cost", weights=optimization_result["probability"])

array([[<Axes: title={'center': 'cost'}>]], dtype=object)

png

Plot the optimal solution:

best_solution = optimization_result.solution[optimization_result.cost.idxmin()]

best_solution

[1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 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)

png

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.

[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.