Vertex Cover Link Monitoring for IoT-Enabled Wireless Sensor Networks

View on GitHub

Open this notebook in GitHub to run it yourself

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.

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

Figure

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:

Build a Classiq model.
Generate a parameterized quantum circuit.
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")

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

Output:

1 Var Declarations
      x : Size=12, Index={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}
          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={(2, 4), (1, 2), (5, 11), (1, 5), (3, 7), (6, 8), (4, 6), (8, 10), (1, 4), (2, 3), (8, 9), (3, 12), (1, 3)}, 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

  3 Declarations: x 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!

Building a Classiq Model

Use the CombinatorialProblem class to set up the problem. Pass the Pyomo model together with the quantum configuration of the QAOA algorithm — the number of repetitions (num_layers):

from classiq.applications.combinatorial_optimization import CombinatorialProblem

combi = CombinatorialProblem(pyo_model=mvc_model, num_layers=1)

The classical optimization settings — the maximum number of iterations (maxiter) and the quantile for running CVaR-QAOA, an improved variation of the QAOA algorithm [3] — are provided later, when you call combi.optimize. Load the Classiq model, based on the problem and algorithm parameters, which you can than use to solve the problem:

qmod = combi.get_model()

The Classiq model (qmod) already incorporates the QAOA execution logic.

That’s it! The Classiq model is set!!

Generating a Parameterized Quantum Circuit

Generate the quantum program with combi.get_qprog() and view the QAOA circuit (ansatz) used to solve the optimization problem:

qprog = combi.get_qprog()
show(qprog)

Output:

Quantum program link: https://platform.classiq.io/circuit/3IoRtQvcITTCCGwkfYBUrmt3fFY
  

Output:

https://platform.classiq.io/circuit/3IoRtQvcITTCCGwkfYBUrmt3fFY?login=True&version=22
  

Executing the Circuit: Optimizing Parameters to Get the Optimal Solution

To solve the problem, run the hybrid optimization loop with combi.optimize:

optimized_params = combi.optimize(maxiter=60, quantile=0.9)

Output:

/home/dor/Sources/Classiq/library-13/lib/python3.13/site-packages/classiq/applications/combinatorial_optimization/combinatorial_problem.py:258: ClassiqDeprecationWarning: ExecutionSession.minimize is deprecated; use variational_minimize instead.
    result = _es.minimize(
  

Analyzing the Energy Convergence Execution Results

Check the energy convergence through the iterations:

plt.plot(combi.cost_trace)
plt.xlabel("Iterations")
plt.ylabel("Cost")
plt.title("Cost convergence")

Output:


Text(0.5, 1.0, 'Cost convergence')

Examine the optimization results statistics of the algorithm:

optimization_result = combi.sample(optimized_params)
optimization_result.sort_values(by="cost", ascending=True).head(5)

	solution	probability	cost
575	{‘x’: [0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0]}	0.000488	5
732	{‘x’: [0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0]}	0.000488	5
0	{‘x’: [0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0]}	0.002930	6
1294	{‘x’: [0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0]}	0.000488	6
1075	{‘x’: [0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0]}	0.000488	6

View the histogram:

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

Output:

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

Plot the optimal solution:

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


best_solution

Output:

[0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0]

WSN_network_graph.nodes

Output:


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)

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.

Algorithms

Applications

Tutorials

Vertex Cover Link Monitoring for IoT-Enabled Wireless Sensor Networks

View on GitHub

The Link Monitoring Problem

Graph Modeling

MVC Concept

Working Example

MVC Mathematical Formulation

Solving MVC with Classiq and QAOA

Building the Working Example Graph

Building the Optimization Model from Graph Input

Larger Scale Models

References

View on GitHub

​The Link Monitoring Problem

​Graph Modeling

​MVC Concept

​Working Example

​MVC Mathematical Formulation

​Solving MVC with Classiq and QAOA

​Building the Working Example Graph

​Building the Optimization Model from Graph Input

​Larger Scale Models

​References

The Link Monitoring Problem

Graph Modeling

MVC Concept

Working Example

MVC Mathematical Formulation

Solving MVC with Classiq and QAOA

Building the Working Example Graph

Building the Optimization Model from Graph Input

Larger Scale Models

References