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.