# Minimal-Overlap Centrality for Multi-Gateway Designation in Real-Time TSCH Networks

Gaitán Miguel Gutiérrez, Almeida Luís, D'Orey Pedro M., Santos Pedro M., Thomas Watteyne

► To cite this version:

Gaitán Miguel Gutiérrez, Almeida Luís, D'Orey Pedro M., Santos Pedro M., Thomas Watteyne. Minimal-Overlap Centrality for Multi-Gateway Designation in Real-Time TSCH Networks. ACM Transactions on Embedded Computing Systems (TECS), 2023. hal-04170029

HAL Id: hal-04170029

https://inria.hal.science/hal-04170029

Submitted on 25 Jul 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Minimal-Overlap Centrality for Multi-Gateway Designation in Real-Time TSCH Networks

MIGUEL GUTIÉRREZ GAITÁN*, Universidad Andres Bello, Chile and CISTER, Portugal

LUÍS ALMEIDA, CISTER, Portugal and Faculdade de Engenharia, Universidade do Porto, Portugal

PEDRO M. D'OREY, CISTER, ISEP/IPP, Portugal and Faculdade de Ciências, Universidade do Porto, Portugal

PEDRO M. SANTOS, CISTER, ISEP/IPP, Portugal

THOMAS WATTEYNE, Inria, France

This article presents a novel centrality-driven gateway designation framework for the improved real-time performance of low-power wireless sensor networks (WSNs) at system design time. We target time-synchronized channel hopping (TSCH) WSNs with centralized network management and multiple gateways with the objective of enhancing traffic schedulability by *design*. To this aim, we propose a novel network centrality metric termed *minimal-overlap centrality* that characterizes the overall number of path overlaps between all the active flows in the network when a given node is selected as gateway. The metric is used as a gateway designation criterion to elect a as a gateway the node leading to the minimal number of overlaps. The method is then extended to multiple gateways with the aid of the unsupervised learning method of *spectral clustering*. Concretely, after a given number of clusters are identified, we use the new metric at each cluster to designate as cluster gateway the node with the least overall number of overlaps. Extensive simulations with random topologies under centralized *earliest-deadline-first* (EDF) scheduling and *shortest-path* routing suggest our approach is dominant over traditional centrality metrics from social network analysis, namely, *eigenvector*, *closeness*, *betweenness*, and *degree*. Notably, our approach reduces by up to 40% the worst-case end-to-end deadline misses achieved by classical centrality-driven gateway designation methods.

CCS Concepts: • **Computer systems organization** → **Embedded systems**; *Redundancy*; Robotics; • **Networks** → Network reliability.

Additional Key Words and Phrases: Earliest-deadline-first (EDF), Gateway selection, Time-synchronized channel hopping (TSCH)

## 1 INTRODUCTION

Industrial wireless networks allow the development of a number of innovative applications, services, and systems (e.g. real-time monitoring) as one of the key enablers of the Industrial Internet of Things (IIoT). IIoT-driven systems supported by wireless technologies [20, 33] have been deployed ubiquitously due to many advantages,

Authors' addresses: Miguel Gutiérrez Gaitán, Universidad Andres Bello, Santiago, Chile, miguel.gutierrez@unab.cl and CISTER, Porto, Portugal, mjggt@isep.ipp.pt; Luís Almeida, CISTER, Porto, Portugal and Faculdade de Engenharia, Universidade do Porto, Porto, Portugal, lda@fe.up.pt; Pedro M. d'Orey, CISTER, ISEP/IPP, Porto, Portugal and Faculdade de Ciências, Universidade do Porto, Porto, Portugal, ore@isep.ipp.pt; Pedro M. Santos, CISTER, ISEP/IPP, Porto, Portugal, pss@isep.ipp.pt; Thomas Watteyne, Inria, Paris, France, thomas.watteyne@inria.fr.
Field View: Wastewater Treatment Plant

<figure><img src="image_2.png" /><figcaption>Fig. 1. A graphical representation for an RT-WSN at a wastewater treatment plant using several sensor nodes and two gateways, namely, GW₁ and GW₂. The orange lines represent data flow paths from the sensors toward the gateways.</figcaption></figure>

but mostly due to their superior flexibility and low infrastructure cost when compared to their wired counterpart. Particularly, real-time wireless sensor networks (RT-WSNs), i.e. WSNs with explicit requirements on the timely delivery of data, have appeared more recently, enabling a number of time-sensitive IIoT applications in automation and data management, most commonly for the purposes of system-wide monitoring and process control [25]. Notably, their industrial scope has been broad, spanning from traditional oil and gas facilities [42] to the emerging additive manufacturing [41], automotive [36], health-care [11], and (even) smart marinas [2].

Typically, the primary RT-WSNs infrastructure is simple, consisting of a fixed set of field nodes (i.e., sensors and/or actuators) transmitting periodic and deadline-constrained sensory data flows toward one or multiple gateways (see Fig. 1). Gateways or managers are special nodes able to schedule the traffic and serve as bridges between field devices and the Internet or an intranet. In typical industrial settings, managers handle small wireless networks ranging from 10 to 100 nodes, while requiring wire-like reliability, i.e., 99.9% or better [44]. However, achieving high-performing RT-WSN is challenging due to the distinctive harsh (wireless) industrial conditions (e.g. due to external interference or fading) and dynamic multi-hop mesh topologies [37].

Proper physical, data-link, and network layer considerations are required to facilitate real-time communication, especially providing guarantees in terms of end-to-end (E2E) delays and reliability. Despite its limited bandwidth, Medium Access Control (MAC) layers such as Time-Synchronized Channel Hopping (TSCH) [10] offer salient features in this direction, both to achieve predictable and highly-reliable operation. TSCH is, in fact, one of the most popular standards for RT-WSNs, with plenty of literature dedicated to addressing major factors influencing real-time network performance [16, 25]. While research has been mostly devoted to scheduling and routing problems, other dimensions such as the proper selection or placement of the gateway node have recently emerged as important due to their not negligible impact on traffic schedulability, i.e. the network's ability to schedule packet transmissions within specific deadline constraints.

In this article, we target judicious RT-WSN gateway designation for improved real-time performance in terms of traffic schedulability. We claim that this proposition further stresses the relevance of this dimension in the design of RT-WSNs, complementing the more common approaches based on real-time scheduling [32] or routing [45]. While gateways in RT-WSNs are generally deployed in arbitrary positions (see e.g., [43]), gateways can also be designated among the existing nodes [47], i.e. elected without adding new ones, but being constrained by the actual nodes positions. In both situations, an arbitrary (random) or non-optimized gateway position can greatly
influence the real-time network performance, e.g., in terms of E2E communication delays or schedulability, thus justifying the need for proper mechanisms to designate gateways<fnref n="1" />.

This research is a follow-up of our recent study in [13] in which we first introduce the concept of *network centrality*<fnref n="2" /> as an effective heuristic for gateway designation in RT-WSNs. Our prior work has shown that social network analysis (SNA) metrics are an appropriate criterion for gateway designation for remarkably increasing traffic schedulability by design. Despite the promising results, none of the *network centrality* metrics evaluated (eigenvector, closeness, betweenness, and degree) dominated over the other, nor achieved optimal *real-time* performance. A challenge we attempt to address herein.

**Contributions.** We present a novel *centrality-driven* single- and multi-gateway designation framework for RT-WSNs with improved real-time performance. We deal with alike foundational questions of the work in [13], but solve the gateway designation problem by proposing a new flow-informed metric termed *minimal-overlap centrality* based on the reduction of path node-overlaps in shortest path routing. This metric requires knowing the routing approach beforehand to compute the overall overlapping degree resulting from the encountering of all active flows in the network elements. The metric is inspired by the minimal-overlap routing protocol [14], which reduces path overlaps among flows using a greedy heuristic that weights links based on the flows’ node-overlaps. By contrast, this work reduces the network global overlapping degree by judiciously choosing as gateway the node that *minimizes* the overall number of overlaps. While a schedulability-optimal choice could be made using enough computational power, we explore a less demanding approach that does not require fully assessing network schedulability to achieve optimal or near-optimal real-time performance.

We also extend the idea to multiple gateways with the aid of the unsupervised learning method of *spectral clustering* [29], as in [15]. Concretely, at each cluster, we use the *minimal-overlap centrality* to designate as gateway the node which produces the least overall number of overlaps. Note clustering is used here for gateway designation only, being orthogonal to traffic scheduling and routing that operate globally across the network.

To the best of our knowledge, this work represents the first extensive study of a centrality-driven single- and multi-gateway designation framework specifically designed to reduce end-to-end deadline misses in RT-WSNs. Without loss of generality, we consider RT-WSNs operating under the TSCH (time-synchronized channel hopping) mode of the IEEE802.15.4e standard, a popular medium access control (MAC) layer common to several WSN standards (e.g. WirelessHART, ISA100.11a, 6TiSCH, etc.) offering salient real-time features.

**Organization.** The remainder of this article is organized as follows. Section 2 discusses related work. Section 3 summarizes the system model, including the network, flow and performance models. Section 4 describes the proposed framework. Section 5 reports and discusses extensive empirical results and validation of the proposed framework. Finally, Section 6 gives concluding remarks and future work directions.

## 2 RELATED WORK

Table 1 shows a non-exhaustive review of gateway designation methods based on their goal and underlying principle of operation. It highlights in bold those terms which are closely related to the approach proposed here, namely, *network centrality*, *clustering*, and *schedulability*. In the following, we discuss in more detail how these ideas appear in prior work for both the single and multiple gateway designation categories.

**Single-gateway designation.** Prior work has already addressed the problem of how to properly designate a node for the role of gateway, i.e. among the existing nodes in the infrastructure, to choose the one which is more

<footnote n="1">¹Although we consistently use the term *gateway* to refer to nodes enabling seamless communication with external entities (e.g. a host application), the problem addressed here assumes the gateways also play the role of *sinks* (or even edge-computing nodes), thus used to centrally (and *timely*) gather data transmissions from sensors, e.g., for further processing or storage.</footnote>

<footnote n="2">² a relative measure of the importance of the node according to its position in the network.</footnote>
<table><caption>Table 1. Gateway Designation Methods for RT-WSNs</caption><thead><tr><th>Category</th><th>Goal</th><th>Concept</th><th>Reference</th></tr></thead><tbody><tr><td rowspan="3">Single Gateway Designation</td><td>Timeliness</td><td><strong>Network Centrality</strong></td><td>[47]</td></tr><tr><td>Energy Efficiency</td><td>Load Balancing</td><td>[34]</td></tr><tr><td>System Throughput</td><td>Flowchart</td><td>[24]</td></tr><tr><td rowspan="3">Multi-Gateway Designation</td><td>Latency</td><td>Optimization</td><td>[8]</td></tr><tr><td><strong>Schedulability</strong></td><td><strong>Clustering</strong></td><td>[9]</td></tr><tr><td>Reliability</td><td>Routing</td><td>[48]</td></tr></tbody></table>

suitable according to a given key performance indicator. These works have often targeted specific metrics such as energy efficiency [34], timeliness [47], etc., or composite trade-offs [24], e.g. with the goal of reducing load and interference [4]. Moreover, a great part of related work has considered optimization-based problems [35], yet often relying on positions or distance-based inputs to find a suitable solution. This, however, is typically deemed as a different problem called gateway placement. Recently, we have proposed a (position-agnostic) network centrality-driven gateway designation method for real-time WSNs [13] with improved performance in terms of schedulability. The concept of network centrality has been applied in previous research on wireless networks to solve several problems, namely, for information dissemination in Delay-Tolerant Networks (DTN) [27] or for reducing traffic congestion in Information-Centric Networking (ICN) [7] to improve, for instance, caching and content delivery. Centrality has also been applied in wireless networks for network modeling or protocol design, namely for routing [30], topology control [40], security [26], among others. Nevertheless, the notion of centrality for gateway designation has been considered in few works only (e.g. [47]). Specifically, Xing et al. [47] proposed a method for gateway designation for improving information timeliness, however, without specifically targeting real-time performance guarantees, e.g. schedulability.

Moreover, although prior centrality-based gateway designation methods have been shown to improve the real-time performance of WSNs, optimal performance was far from being reached. In short, knowledge of the routing approach allows computing the overall overlapping degree resulting from the encountering of all active flows in the network elements and the node that minimizes the overall number of overlaps is selected as gateway.

**Multi-gateway designation.** Previous works in the literature demonstrated that using multiple sinks or gateways increases parallelization of flows and improves traffic timeliness in WSNs (e.g. [21, 38]). Similarly, several studies (e.g. [8][9][48]) in the field have focused on the problem of selecting a subset of nodes as gateways for a WSN. Chen et al. [8], for example, have shown that the minimum gateway designation problem with latency and reliability guarantees in a TSCH network is NP-hard. The authors proposed a method to address this problem that jointly considers RPL routing and DeTAS [1] scheduling, but they didn't target schedulability. Dobslaw et al. [9] explicitly addressed schedulability as a QoS constraint by proposing a complete cross-layer configuration for industrial WSN that considers, among others, the possibility of adding multiple sinks. This work - as many others in related literature - relied on actual node positions for finding an appropriate gateway or sink designation/placement, in this case, based on the popular k-means clustering. This approach, however, is not applicable when physical positions are unknown, and when the only information available is the logical network topology; as in our case. Other studies have addressed alike problems (e.g. [22, 28]), either from the perspective of clustering and/or from the viewpoint of multi-sink placement, targeting common delay or reliability issues; yet, often ignoring the cornerstone aspect of real-time performance, i.e. schedulability, and/or assuming a match among physical and logical topologies. To tackle these downsides, our recent work in [15] provided a novel combination of network
centrality and spectral clustering [29] - which rely only on topology in the form of an adjacency matrix - to designate multiple gateways in WSNs, yet offering an improvement over a random benchmark.

**Novelty.** To the best of our knowledge, this is the first position-agnostic framework for single- and multi-gateway designation specifically designed to enhance real-time performance in WSNs. We contribute with a new metric termed minimal-overlap centrality able to reduce the overall number of path overlaps in the network, which in turn impact positively on traffic schedulability. We then built upon the work in [15] to extend the minimal-overlap insight to multiple gateways by combining our new metric with spectral clustering [29]. We show by extensive simulations that with this combined approach our metric is able to outperform classic centrality metrics showing up to ~ 40% better traffic schedulability under particular configurations, and up to about ~ 200% more schedulable network flows than when considering a worst-case node selection.

# 3 SYSTEM MODEL

## 3.1 Network Model

The wireless sensor network is abstracted as an undirected graph $G = (V, E)$ where $V$ is the set of vertices or nodes and $E$ is the set of edges or links between those nodes. The order of the graph $G$ is denoted as $N = |V|$, of which a set of $N-k$ nodes act as field nodes (e.g. sensors) while the rest of $k$ nodes are designated as gateways. All nodes can perform the sensing, relaying or gateway functions, are provided with adequate power sources, and are connected wirelessly forming a wireless mesh network (see Fig. 1). We then assume full knowledge of the network topology (i.e. the graph $G$) in the form of an adjacency matrix representing binary connectivity with lossless links. Topology tracking can be assumed as a native in-built centralized service that can be further implemented, e.g., as in [3].

Multiple access is governed using TSCH protocol which uses fixed-size TDMA slots combined with multi-channel hopping. TSCH allows concurrent transmissions over up to $m = 16$ different radio-frequency channels with global synchronization. A time slot interval, here $t_s = 10$ ms, allows the transmission of a single packet and receiving the corresponding acknowledgment. All packet transmissions are considered centrally managed using a global earliest-deadline-first (EDF) scheduling<fnref n="3" /> policy and a (hop-count) shortest-path routing algorithm.

## 3.2 Real-Time Flow Model

We consider a subset of $n \le N-k$ field nodes as sensor nodes, thus required to transmit periodically their sensing data toward any of the $k$ designated gateways (destinations). These messages need to reach their corresponding gateways before specific timing constraints, i.e. deadlines. We denote as $F = \{f_1, f_2, ..., f_n\}$ the set $n$ of real-time flows potentially transmitting an infinite number of deadline-constrained messages, periodically. Each of the $n$ flows is characterized by a 4-parameter tuple $(C_i, D_i, T_i, \phi_i)$, where $C_i$ represents the transmission time between the source node $s_i$ and any of the $k$ gateway destinations. $T_i$ is the transmission period, $D_i$ is the (relative) deadline, and $\phi_i$ is the multi-hop routing path. The $\gamma^{th}$ transmission of each periodic flow $f_i$ is released at time $r_{i,y}$ such that $T_i = r_{i,y+1} - r_{i,y}$. Then, according to the EDF scheduling policy, each of these flow instances $f_{i,y}$ is constrained to reach the gateway before its absolute deadline [$d_{i,y} = r_{i,y} + D_i$].

## 3.3 Performance Model

We consider the schedulability assessment framework in [17] to evaluate the real-time performance of our TSCH-based network under global EDF. The method is a state-of-the-art supply/demand-based schedulability test leveraging the concept of *forced-forward demand-bound function (FF-DBF)* [5] from multiprocessor scheduling theory. Essentially, this method evaluates if the *supply-bound function (SBF)*, here the minimal transmission

<footnote n="3">³We assume both routing and scheduling are always computed offline, thus do not generate further network traffic during normal operation.</footnote>
capacity offered by an RT-WSN with *m* channels, is equal or larger than the upper-bound of the FF-DBF network demand when adapted to WSNs (FF-DBF-WSN) [18].

Formally, (1) presents the traffic schedulability test for RT-WSNs, where sbf (*l*) is such that satisfies the conditions in (2), and the FF-DBF-WSN is defined in (3).

$$ \text{FF-DBF-WSN}(l) \leq \text{sbf}(l), \forall l \geq 0. \qquad (1) $$

$$ \text{sbf}(0) = 0 \wedge \text{sbf}(l+h) - \text{sbf}(l) \leq m \times h, \forall l, h \geq 0. \qquad (2) $$

$$ \text{FF-DBF-WSN}(l) = \underbrace{\frac{1}{m} \sum_{i=1}^{n} \text{FF-DBF}(f_i, l)}_{\text{CHANNEL CONTENTION}} + \underbrace{\sum_{i,j=1}^{n} \left( \Delta_{i,j} \cdot \max\left\{\left\lfloor \frac{l}{T_i} \right\rfloor, \left\lfloor \frac{l}{T_j} \right\rfloor\right\} \right)}_{\text{TRANSMISSION CONFLICTS}} \qquad (3) $$

Note that the expression for FF-DBF-WSN is composed by two terms, namely, i) **channel contention** and ii) **transmission conflicts**. The former – in the left parcel of (3) – represents the mutual exclusive condition for allocating concurrent transmissions on multiple channels, equivalent to the FF-DBF expression for multiprocessors scheduling [5]. The latter – in the right parcel of (3) – models the delay contribution due to multiple flows encountering at a common half-duplex node. Eq. (4) defines $\Delta_{i,j}$ as a delay factor representing the node-path overlapping between any pair of flows $f_i$ and $f_j \in F$ (with $i \neq j$), as in [46].

$$ \Delta_{i,j} = \sum_{\alpha=1}^{\delta(ij)} \text{Len}_{\alpha}(ij) - \sum_{\beta=1}^{\delta'(ij)} (\text{Len}_{\beta}(ij) - 3) \qquad (4) $$

where $\delta(ij)^4$ indicates the total number of overlaps between the flows $f_i$ and $f_j$ of which $\delta'(ij)$ are the ones larger than 3. The length of the $\alpha^{th}$ and $\beta^{th}$ path overlaps between $f_i$ and $f_j$ are termed $\text{Len}_\alpha(ij)$ and $\text{Len}_\beta(ij)$, respectively, with $\alpha \in [1, \delta(ij)]$ and $\beta \in [1, \delta'(ij)]$. Note that this expression considers the fact that after 3 hops slots can be reused, not causing further transmission conflicts.

Table 2 summarizes the main symbols of the performance model.

<table><caption>Table 2. Table of Performance Model Symbols</caption><thead><tr><th>Symbol</th><th>Definition</th></tr></thead><tbody><tr><td>FF-DBF-WSN</td><td>Forced-forward demand-bound function for WSNs</td></tr><tr><td>SBF</td><td>Supply bound function</td></tr><tr><td>l</td><td>Length of the interval of evaluation</td></tr><tr><td>Δ<sub>ij</sub></td><td>Delay factor between f<sub>i</sub> and f<sub>j</sub></td></tr><tr><td>δ<sub>(ij)</sub></td><td>No. of overlaps between f<sub>i</sub> and f<sub>j</sub></td></tr><tr><td>δ'(ij)</td><td>No. of δ(ij) larger than 3</td></tr><tr><td>m</td><td>No. of channels</td></tr><tr><td>h</td><td>A scalar</td></tr></tbody></table>

<footnote n="4">⁴Note that $\delta(ij)$ is trivially calculated by counting the number of nodes that belong to the path of $f_i$ and to the path of $f_j$ at the same time.</footnote>
Minimal-Overlap Centrality-Driven GW Designation

<figure><img src="image_3.png" /><figcaption>Fig. 2. A graphical representation of the minimal-overlap centrality-driven single-gateway designation strategy.</figcaption></figure>

## 4 MINIMAL-OVERLAP NETWORK CENTRALITY FOR GATEWAY DESIGNATION IN RT-WSNS

Given the network, flow and performance models presented in Section 3, we consider the problem of how to judiciously designate one or multiple nodes as gateways for improved WSN traffic schedulability. In this direction, and resorting to the notion of network centrality, we propose a new metric that characterizes the relationship between gateway designation and node-path overlaps. We recall that our framework is intended to be used at system design time, assuming full knowledge of the network topology (graph) in the form of an adjacency matrix. The proposed metric is then used to designate as gateway the node with the highest centrality score. Similarly to [15], we also extend the framework to multiple gateways with the aid of the unsupervised learning method of spectral clustering. Classical network centrality metrics are considered for benchmarking purposes.

### 4.1 Minimal-Overlap Network Centrality

In the following, we address the single-gateway designation problem illustrated in Fig. 2 by proposing a new metric termed minimal-overlap (MO) network centrality. This metric is built upon the computation of the overall path overlapping resulting from the superposition of all flow routes in the network when directed to a given node $v_q \in V$. The metric represents the relative importance (centrality) of the node $v_q$ w.r.t. the other nodes in the network in terms of node-path overlaps. A higher score indicates a higher overlapping degree at that node. Formally, the MO centrality metric is presented in (5).

$$ MO(v_q) = \frac{1}{\sum_{i,j=1 \land i \neq j}^{n} \Delta_{i,j}^{q}} \quad (5) $$

where the factor $\Delta_{i,j}^q$ is the node-path overlap contribution from flows $f_i$ and $f_j$ when their routes $\phi_i$ and $\phi_j$ are directed toward node $v_q$, and $n$ is the number of flows in the set $F$. Note that we consider a subset of $n < N$ nodes are message sources (i.e. sensor nodes) transmitting periodic data toward a single gateway. The rest of $N - n - 1$ act as relays only. Without loss of generality, we also assume all the routes are computed using a hop-count-based shortest-path algorithm (e.g. Dijkstra, as in [19]).

### 4.2 Classical Network Centrality Metrics

For comparison, we assess four of the most common network centrality metrics in network science, namely, i) eigenvector, ii) closeness, iii) betweenness and iv) degree. These metrics are deemed as near optimally correlated for the purposes of benchmarking [39]. For completeness, we revisit their formal definitions as follows:
**4.2.1 Eigenvector Centrality (EC).** This metric quantifies how influential a specific node is w.r.t. others in a given network, a concept also known as transitive influence. This means a node with an EC score that is higher than another is connected to many other nodes which themselves also are highly scoring nodes. The score can be determined from the analysis of the principal eigenvector extracted from the adjacency matrix representing the network topology. Formally, the EC for a given node $v_q \in V$ can be expressed by (6):

$$EC(v_q) = \frac{1}{\lambda_{max}(A)} \cdot \sum_{j=1}^{N} a_{j,q} \cdot x_j \quad (6)$$

where $\lambda_{max}(A)$ is the largest eigenvalue of the adjacency matrix $A = [a_{j,q}]_N$, $a_{j,q}$ is the matrix element at row j and column q, $x_j$ is the jth value of the eigenvector x of graph G, and N is number of nodes in the network.

**4.2.2 Closeness Centrality (CC).** This metric quantifies the level of proximity (or closeness) a specific node has w.r.t. the rest of nodes in the network. For a given node $v_q \in V$, CC is defined as the inverse of the sum of the geodesic distances from $v_q$ to all the other nodes. Formally, the CC metric is presented in (7) as follows:

$$CC(v_q) = \frac{1}{\sum_{p \neq q} \text{distance}(v_p, v_q)} \quad (7)$$

where distance($v_p, v_q$) is the shortest path distance between the nodes $v_p$ and $v_q$, with $p \neq q$, $\forall v_p \in V$. Note that, for simplicity, we consider in this work only hop-count-based shortest paths.

**4.2.3 Betweenness Centrality (BC).** This metric quantifies how many shortest-path routes pass through a specific node in the network. For a given node $v_q \in V$, the metric can be computed as the fraction between the number of shortest paths of any pair $v_r$ and $v_s$ ($\forall v_r, v_s \in V \land r \neq s \neq q$) passing through node $v_q$, and the total number of shortest paths in the network. Eq. (8) formally presents the BC metric:

$$BC(v_q) = \sum_{q \neq r} \frac{sp_{r,s}(v_q)}{sp_{r,s}} \quad (8)$$

where $sp_{r,s}$ is the number of shortest paths between any pair of nodes $v_r$ and $v_s$, and $sp_{r,s}(v_q)$ is the number of those paths passing through node $v_q$.

**4.2.4 Degree Centrality (DC).** This metric quantifies the number of links, edges or one-hop neighbours a specific node has. For a given node $v_q \in V$, DC can be formally presented as in (9):

$$DC(v_q) = \frac{\text{degree}(v_q)}{N-1} \quad (9)$$

where degree($v_q$) denotes the number of links or edges of $v_q$ directly connected to other nodes and $N = |V|$.

## 4.3 Clustering-Aided Multi-Gateway Designation

We built upon the work in [15] to extend our minimal-overlap centrality-driven framework to multiple gateways. This prior work consists on first clustering the network with spectral clustering (SC)[29], which does not require knowledge of nodes positions, just adjacency, and then applying a classical centrality metric (EC, CC, BC or DC) to designate a gateway inside each cluster. This novel combination of spectral clustering and network centrality is applied to our framework in its original fashion, but using MO as the centrality instead. The end goal is to demonstrate MO outperforms classical centrality metrics also for the multi-gateway designation case.
### 4.3.1 Spectral Clustering.
Several clustering algorithms (e.g. survey in [49]) have been proposed in the literature. In this work, we resort to Spectral Clustering (SC) due to its superior performance as demonstrated in comparative studies (e.g. [31]) and since this algorithm family does not rely on the node’s position but rather the graph structure. The relatively high time complexity<fnref n="5" /> and the need to preset the number of clusters are two of the main drawbacks of this class of clustering methods. In short, SC resorts to the eigendecomposition of the graph Laplacian matrix (L) to find solutions based on the relaxation of graph cut problems. Specifically, we use the direct k-way SC algorithm proposed by Ng, Jordan and Weiss [29] to identify groups of widely separated nodes represented by k connected subgraphs (or clusters). The Ng-Jordan-Weiss (NJW) algorithm uses eigenvectors of the normalized Laplacian (Lnorm) which can formally be obtained as follows:

$$L_{norm} = D^{-1/2} \cdot L \cdot D^{-1/2} \qquad (10)$$

where D is the degree matrix, and L = D - A is the Laplacian, with A being the adjacency matrix of the graph. Algorithm 1 presents a high-level pseudo-code for the NJW SC method.

#### Algorithm 1 NJW Spectral Clustering [29]

**Input:** a graph G and the target number of clusters k
**Output:** a partition of k clusters $\Pi = \{G_1, G_2, ..., G_k\}$

1. Find the first k eigenvectors $u_1, u_2, ..., u_k$ of Lnorm and sort them in the columns of U'

2. Build matrix $U = [u_{ij}]_{n \times k}$ based on U' by normalizing each row of U' using $u_{ij} = u'_{ij} / \sqrt{\sum_k u'^2_{ik}}$

3. Let the $i^{th}$ row of the matrix U represent node $v_i$ from graph G

4. Apply k-means algorithm (or an equivalent method) to U and find a k-way partitioning $\Pi' = \{G'_1, ..., G'_n\}$

5. Form the final partition $\Pi$ assigning every node $v_i$ to the cluster $G_i$, if the $i^{th}$ row of U belongs to $G'_i$ in $\Pi'$

### 4.3.2 Multi-Gateway Designation.
As shown in Fig. 3, we leverage a centrality-driven multi-gateway designation framework resorting to the SC algorithm to partitioning the network. The approach requires computing a centrality metric per cluster after a number of k clusters has been identified. This means selecting as gateways of each cluster the node with the highest centrality score. Differently from the work in [15] – that uses classical centrality metrics –, here we use the MO centrality instead. MO centrality is used with the interpretation of being a cluster centrality metric. This requires considering each cluster $G_i$ as a subgraph of G which can be characterized by its cluster adjacency matrix $A_i$ and the number of nodes in the cluster $N_i$, with $\sum_{l=1}^k N_i = N$. As in [15], we can trivially adapt the centrality expressions in Equations (5), (6), (7), (8) and (9) to reflect these formalities. We summarize these adaptations in Table 3⁶ for completeness.

Particularly, for the MO centrality, we reformulate the expression in (5) for clusters as follows:

$$MO^{l}(v_{q}) = \frac{1}{\sum_{i,j=1 \land i \neq j}^{n_{l}} \Delta_{i,j}^{q} + 1} \qquad (11)$$

<footnote n="5">⁵While solutions to further reduce the time complexity of SC exist in the literature (see e.g., [23]), the time complexity will be a potential issue only in the case of large datasets, e.g., with millions of samples or nodes. In contrast, we target here a typical industrial network setting with no more than 100 field devices per each controller or gateway [44]; thus resulting in a marginal increase of the processing time⁶.</footnote>

<footnote n="6">⁶Notation: degree($v_q$) denotes the number of edges of node $v_q$ that are directly connected to any of the rest $N_l - 1$ nodes in $G_l$; sp<sub>r,s</sub> is the number of shortest paths between any pair of cluster nodes $v_r$ and $v_s$, and sp<sub>r,s</sub>($v_q$) is the number of those paths passing through node $v_q$; distance($v_p, v_q$) is the (hop-count) shortest path distance between nodes $v_p$ and $v_q$, with $p \neq q$, $\forall v_p \in V_l$, where $V_l$ is the set of vertices or nodes of cluster $G_l$; $x_j$ is the j-th value of the eigenvector x of the subgraph $G_l$, and $\lambda_{max}(A_l)$ is the largest eigenvalue of the cluster's adjacency matrix $A_l = [a_{j,q}]_{N_l \times N_l}$, with $a_{j,q}$ being the matrix element at the row j and column q.</footnote>
Example: 3 clusters/gateways

<figure><img src="image_4.png" /></figure>

Inputs:

- Network topology (Adjacency)

- Number of gateways (k)

<figure><img src="image_5.png" /><figcaption>① Spectral clustering, k=3
agnostic to node positions</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>② GW designation w/centrality
e.g., degree centrality</figcaption></figure>

<caption>Fig. 3. A toy example of the centrality-driven multi-gateway designation framework in [15] for k = 3 clusters/gateways.</caption>

where $n_{\ell} < n$ is the number of sources which flows are directed to node $v_q \in G_{\ell}$. Note that $v_q$ as well as all the $n_{\ell}$ sources belongs to the same cluster $G_{\ell}$. $MO^{\ell}(v_q)$ denotes the MO cluster centrality for a given node $v_q \in G_{\ell}$.

<table><caption>Table 3. Cluster Centrality Metrics.</caption><thead><tr><td>Metric</td><td>Definition</td></tr></thead><tbody><tr><td>Degree</td><td>DC(v<sub>q</sub>) = <sup>degree(v<sub>q</sub>)</sup>/<sub>N<sub>ℓ</sub>−1</sub></td></tr><tr><td>Betweenness</td><td>BC(v<sub>q</sub>) = Σ<sub>q≠r</sub> <sup>sp<sub>r,s</sub>(v<sub>q</sub>)</sup>/<sub>sp<sub>r,s</sub></sub></td></tr><tr><td>Closeness</td><td>CC(v<sub>q</sub>) = <sup>1</sup>/<sub>Σ<sub>p≠q</sub> distance(v<sub>p</sub>,v<sub>q</sub>)</sub></td></tr><tr><td>Eigenvector</td><td>EC(v<sub>q</sub>) = <sup>1</sup>/<sub>λ<sub>max</sub>(A<sub>k</sub>)</sub> ⋅ Σ<sub>j=1</sub><sup>N<sub>k</sub></sup> a<sub>j,q</sub> ⋅ x<sub>j</sub></td></tr></tbody></table>

# 5 PERFORMANCE EVALUATION

We resort to the joint system model described in Section 3 to assess the performance of the single and multi-gateway designation methods presented in Section 4. We perform UUniFast-like [6][12] simulation with random task sets of random flows and random topologies, and then sample the output process for performance assessment. In the following subsection, we present the simulation setup for each of the components of the system model (i.e. wireless network, real-time flow and performance models). The main results are given and discussed in Section 5.2.

## 5.1 Simulation Setup

### 5.1.1 Wireless network.
We consider 1000 network topologies built upon the synthetic generation of random graphs. Each graph is generated using a sparse uniformly distributed random matrix with a target (average) node density of $d = \{0.1, 0.5, 1.0\}$. The dimension of the random matrix is $N \times N$, where $N = 75$ is the total number of
<figure><img src="image_7.png" /><figcaption>Fig. 4. **Top:** Schedulability ratio of 1000 random topologies for varying number of flows with target density 0.1 (a), 0.5 (b) and 1.0 (c) resorting to gateway designation methods based on i) classical network centrality metrics (e.g. eigenvector centrality) and ii) the proposed minimal-overlap network centrality. **Bottom:** the deviation in terms of schedulability from the best and worst possible gateway assignments. A random selection is included as a benchmark.</figcaption></figure>

nodes in the network including $k = \{1, 2, 3\}$ gateways. All graphs represent TSCH-based WSNs in multi-channel operation with up to $m = 16$ channels and time slots of $t_s = 10$ ms.

### 5.1.2 Real-time flows.
We consider a subset of $n \in [1, 30]$ nodes acting as source nodes while the rest are relays and/or gateways. Source nodes are selected randomly from the set of field nodes, i.e. excluding the $k$ gateway(s). All flows are consistently generated according to the real-time model in Section 3, following a 4-tuple parameter $(C_i, D_i, T_i, \phi_i)$. Each of these flows is directed to only one gateway through its (hop-count-based) shortest path $\phi_i$. $C_i$ is computed by multiplying the time slot duration $t_s$ with the length of the routing path (i.e. the number of hops). $T_i$ is randomly generated in the form $2^{\eta}$, with $\eta \in \mathbb{N}$ in the range $[4, 7]$ as done in similar works with stricter (industrial) application requirements (e.g. [45]), thus leading to harmonic periods. This implies a super-frame duration (or hyper-period) of $H = 2^7$ slots, i.e. $H = 1280$ ms. All deadlines ($D_i$) are assumed to be equal to the respective flow periods, i.e. $D_i = T_i$, thus forming an implicit-deadline model.

### 5.1.3 Performance assessment.
We resort to the schedulability test in (1) to assess the real-time performance of the network, which assumes a global EDF scheduling policy. In all the cases, we consider an interval equal to the hyper-period ($\ell = H$) for the assessment. Concerning $\Delta_{i,j}$, network topologies are used to directly compute node-path overlaps. Recall clustering is used here only to assist the gateway designation process, being orthogonal to traffic scheduling and routing that operate globally across the network. This implies all experiments are performed allowing routing paths to use any link on the network, accounting for the eventual path overlaps in the computation of the schedulability.
## 5.2 Simulation Results

5.2.1 **Schedulability Ratio, k=1.** Figs. 4a, 4b, 4c present schedulability ratio results for the case of single-gateway designation (i.e., *k* = 1) for varying number of network flows *n* ∈ [1, 30] and different network densities *d* = {0.1, 0.5, 1.0}, respectively. Different centrality metrics were used as criterion to designate a single gateway. In specific, our minimal-overlap metric is compared against the classical eigenvector, closeness, betweenness and degree, as well as versus a random assignment. As expected, the schedulability ratio decreases for larger numbers of flows in all configurations due to the larger channel contention and transmission conflicts. Conversely, higher network density increases the number of potential paths between any given pair of nodes, thus favoring schedulability.

The results also show that the minimal-overlap gateway designation method achieves higher schedulability for all numbers of flows and densities when compared with a method based on classical centrality metrics. We argue this is caused by the minimal-overlap method ability's of decreasing, by design, the number of overlapping paths. This, in turn, allows for reducing transmission conflicts, thus improving the timely delivery of data messages. As expected, the proposed *minimal-overlap* method is also clearly superior to random selection, further demonstrating the significance of judicious gateway designation.

We also analyze how the proposed method deviates from the system's optimal gateway election in Figs. 4d, 4e, 4f. The metric *relative ratio* is defined as the ratio between the schedulability ratio of a given method to the schedulability ratio of the best and worst performing nodes in the network, with a value of 1 denoting best and 0 the worst performance. The results show the performance of the proposed method is only slightly below the best method, having the maximum degradation of ~24% for a density of 0.1 and 20 simultaneous flows. We highlight this degradation is lower for larger densities (e.g. *d* = 0.5) - becoming negligible for highly connected networks (e.g. *d* = 1.0) - since the overall overlapping degree decreases for increasing density, which was also confirmed by previous studies [14]. Additionally, these results reveal the performance improvements of the proposed method are, in general, able to increase for higher density and higher number of flows when compared with other centrality-based gateway designation methods or random gateway selection.

5.2.2 **Schedulability Ratio, k>1.** Fig. 5 presents different schedulability ratio results for the *minimal-overlap* multi-gateway designation framework when compared to classical centrality-driven methods. Also, both the best and worst possible gateway selections at each cluster are presented (in dotted lines) for comparison. Overall, these results show that our minimal-overlap framework is always dominant over all the classical metrics assessed while achieving optimal (best) or near-optimal real-time performance, especially when the node density is increased. As expected, it is also shown to be clearly superior to the worst-performing gateway selection at each cluster.

Fig. 5a show the results for *k* = 2 gateways, Fig. 5b the case for *k* = 3 and Fig. 5c for *k* = 5. In general, these results confirm the expectation that an increase in the number of gateways (and clusters) also favors schedulability. These results can also be compared with those in Fig. 4, equivalent to the case with *k* = 1. As shown in a prior study [15], increasing the number of gateways reduces significantly worst-case network demand (i.e. contention and conflicts), impacting positively the overall network schedulability. On one hand, having a larger number of gateways allows reducing the mean path length between source and gateway as flows are directed towards a closer sink, which reduces channel contention. On the other hand, dividing the network into a number of clusters, ensures higher flow isolation, which reduces transmission conflicts. These benefits can be observed, for example, when comparing the case of using classical metrics in Fig. 5a with the case of using MO in Fig. 5b for *d* = 0.5, which allows passing from about 10 to 30 schedulable flows with 99.9% of schedulability, representing an improvement of ~ 200% w.r.t. the same framework, same configuration, but with only one more cluster/gateway. A similar effect can be observed in Fig. 5b for *d* = 0.1 but with much lower gains, due to the reduced node density. The case of *d* = 1.0 is included Fig. 5b and Fig. 5a for comparison, confirming the validity of the approach for higher densities. Note these density-related effects are consistent with the plots for the
<figure><img src="image_8.png" /><figcaption>Fig. 5. Average schedulability ratio of 1000 random topologies for a varying number of flows when using (a) $k = 2$, (b) $k = 3$ and (c) $k = 5$ gateways. The solid blue line curves show the results for our minimal-overlap centrality used as a cluster centrality metric and when compared against classical centrality metrics. Best and worst performing nodes are also shown as benchmarks.</figcaption></figure>

single-gateway designation case, which can be explained because by offering more diversity paths (due to higher node density) we favor schedulability, which is especially convenient for our *minimal-overlap* approach (see Fig. 6 for additional insights in terms of densities and number of overlaps). Despite these positive results, the benefits in schedulability of increasing the number of clusters are also limited by the network load and size. In
<figure><img src="image_9.png" /><figcaption>Fig. 6. Average number of overlaps of 100 random topologies when varying network flows for two gateway designation methods (minimal-overlap and degree) and two extreme densities, namely 0.1 (solid line) and 1.0 (dotted line).</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Fig. 7. Execution time for different gateway designation methods, namely, minimal-overlap, degree and best, considering up to 50 network flows and two extreme target densities, namely 0.1 (solid line) and 1.0 (dotted line).</figcaption></figure>

Fig. 5c we see that schedulability suffers a sudden drop at about 25 flows, after which the results with 5 clusters can even be worse than using less clusters, thus holding a trade off for high network loads.

### 5.2.3 Computational Cost.
Fig. 7 depicts the average execution time for the different single-gateway designation methods and the optimal gateway designation. Regarding the classical centrality-based designation method, we solely present the result for degree centrality for visual clarity and because this has the lowest execution time among all metrics. We also present results for two extreme density values of 0.1 (solid line) and 1 (dashed lines). The setup for this experiment used MATLAB R2020b on Ubuntu 18.04 LTS on a laptop with an Intel Core i7-6500U CPU at 2.5GHz and 4GB of DD3 RAM.

The results confirm the low execution time of the degree-centrality gateway designation. On the other hand, minimal overlaps designation considerably decreases the execution time when compared to optimal gateway designation, particularly for higher number of flows. Note that the optimal method uses extensive search with full schedulability analysis for each case, while the MO metric just requires computing the number of overlaps in the network given a set of flows. The results also show that the density has a minimal impact on the average execution time. Overall, the proposed method provides a good trade-off between achievable schedulability ratio (near optimal) and computational cost (up to one-quarter of the value of the optimal method). Note these results are higher than if obtained by cluster, considering the reduced number of nodes and flows in each cluster.

### 5.2.4 Limitations.
Despite the promising results of the MO framework performance under varying network conditions, the overall approach may benefit from future studies that further evaluate the validity and applicability of the proposed approach in real-world settings. Not only in terms of time complexity and real-time performance but also in terms of energy consumption, throughput, latency, scalability, etc. Particularly, in terms of scalability, simulations have shown that increasing the number of gateways while keeping greater network loads holds a trade-off, thus requiring proper design. This, however, enables the possibility to compute how many gateways will satisfy a given schedulability requirement under a given load, which translates into an opportunity. Likewise, although the proposed framework may require considering some additional capabilities on normal nodes to become gateway-enabled (e.g., hardware components), the benefits of an improved real-time performance may justify the costs and complexity of deployment. Overall, while these limitations exist, they do not diminish the potential value and contributions of the proposed minimal-overlap multi-gateway designation framework.
# 6 CONCLUSIONS

This paper has presented a novel single- and multi-gateway designation method for enhanced real-time performance in RT-WSNs. The single-gateway designation approach based on minimizing the number of path node-overlaps has shown to be substantially effective in terms of improved traffic schedulability while offering lower execution times w.r.t. the optimal case. The multi-gateway extension also showed considerable improvements in terms of real-time network operation, while generalizing the single case in a straightforward fashion. Notably, both methods outperform classical centrality-driven single- and multi-gateway designation methods in up to 50% and 40% better traffic schedulability, respectively. In the future, we are interested in further benefiting from the use of this framework at run-time, for example, as a potential solution for fast leader node selection in dynamic networks of mobile robots (i.e. robot swarms). Furthermore, we will investigate the performance impact of having only a subset of nodes as gateway candidates due to computational or energy constraints. Other aspects to consider in the future are the impact of time-varying channel conditions and retransmissions.

# ACKNOWLEDGMENTS

This work was partially supported by National Funds through FCT/MCTES (Portuguese Foundation for Science and Technology), within the CISTER Research Unit (UIDB/04234/2020); by the Operational Competitiveness Programme and Internationalization (COMPETE 2020) under the PT2020 Agreement, through the European Regional Development Fund (ERDF); also by FCT and the ESF (European Social Fund) through the Regional Operational Programme (ROP) Norte 2020, under PhD grant 2020.06685.BD.

# REFERENCES

[1] Nicola Accettura, Elvis Vogli, Maria Rita Palattella, Luigi Alfredo Grieco, Gennaro Boggia, and Mischa Dohler. 2015. Decentralized traffic aware scheduling in 6TiSCH networks: Design and experimental evaluation. *IEEE Internet of Things Journal* 2, 6 (2015), 455–470.

[2] Orestis Akrivopoulos, Dimitrios Amaxilatis, Nikolaos Tsironis, Dimitrios Karadimas, Nektarios Konstantopoulos, and Ioannis Panaretou. 2022. Modernizing Marinas in the Mediterranean Sea using SMartY: Methodologies and Lessons learned. In *2022 IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops)*. IEEE, 472–477.

[3] Diogo Almeida, Miguel Gutiérrez Gaitán, Pedro d'Orey, Pedro Miguel Santos, Luis Pinto, and Luís Almeida. 2021. Demonstrating RA-TDMAs+ for robust communication in WiFi mesh networks. In *42nd IEEE Real-Time Systems Symposium (RTSS), Demo Session*.

[4] Usman Ashraf, Slim Abdellatif, and Guy Juanole. 2009. Gateway selection in backbone wireless mesh networks. In *2009 IEEE Wireless Communications and Networking Conference. IEEE, 1–6*.

[5] Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, and Sebastian Stiller. 2010. Improved multiprocessor global schedulability analysis. *Real-Time Systems* 46, 1 (2010), 3–24.

[6] Enrico Bini and Giorgio C Buttazzo. 2005. Measuring the performance of schedulability tests. *Real-Time Systems* 30, 1-2 (2005), 129–154.

[7] Wei Koong Chai, Diliang He, Ioannis Psaras, and George Pavlou. 2013. Cache “less for more” in information-centric networks (extended version). *Computer Communications* 36, 7 (2013), 758–770.

[8] Yu-Shu Chen, Shih-Ying Chang, Tzu-Wen Chang, and Ming-Jer Tsai. 2018. Multiple sink placement with latency and reliability guarantee in lossy wireless sensor networks. In *IEEE Global Communications Conference (GLOBECOM)*. IEEE, 1–7.

[9] Felix Dobslaw, Tingting Zhang, and Mikael Gidlund. 2016. QoS-aware cross-layer configuration for industrial wireless sensor networks. *IEEE Trans. on Industrial Informatics* 12, 5 (2016), 1679–1691.

[10] Diego Dujovne, Thomas Watteyne, Xavier Vilajosana, and Pascal Thubert. 2014. 6TiSCH: deterministic IP-enabled industrial internet (of things). *IEEE Communications Magazine* 52, 12 (2014), 36–41.

[11] Atis Elsts, Xenofon Fafoutis, George Oikonomou, Robert Piechocki, and Ian Craddock. 2020. TSCH networks for health IoT: Design, evaluation, and trials in the wild. *ACM Transactions on Internet of Things* 1, 2 (2020), 1–27.

[12] Paul Emberson, Roger Stafford, and Robert I Davis. 2010. Techniques for the synthesis of multiprocessor tasksets. In *proceedings 1st International Workshop on Analysis Tools and Methodologies for Embedded and Real-time Systems (WATERS 2010)*. 6–11.

[13] Miguel G. Gaitan, Luis Almeida, Alejandro Figueroa, and Diego Dujovne. 2021. Impact of Network Centrality on the Gateway Designation of Real-Time TSCH Networks. In *Proceedings of the 17th IEEE International Conference on Factory Communication Systems (WFCS)*. IEEE.

[14] Miguel G. Gaitan, Luis Almeida, Pedro M. Santos, and Patrick M. Yomsi. 2021. EDF scheduling and minimal-overlap shortest-path routing for real-time TSCH networks. In *Workshop on Next Generation Real-Time Embedded Systems (NG-RES)*, Vol. 87. Virtual, 2–1.
[15] Miguel G. Gaitán, Diego Dujovne, Julián Zuñiga, Alejandro Figueroa, and Luís Almeida. 2022. Multi-Gateway Designation for Real-Time TSCH Networks using Spectral Clustering and Centrality. *IEEE Embedded Systems Letters* (2022).

[16] Miguel Gutierrez Gaitan and Patrick Meumeu Yomsi. 2019. Multiprocessor Scheduling meets the Industrial Wireless: A brief review. *U. Porto Journal of Engineering* 5, 1 (2019), 59-76.

[17] Miguel G. Gaitan, Patrick M Yomsi, Pedro M Santos, and Luís Almeida. 2020. Work-in-Progress: Assessing supply/demand-bound based schedulability tests for wireless sensor-actuator networks. In *IEEE Int. Conference on Factory Communication Systems (WFCS)*. IEEE, 1-4.

[18] Miguel G. Gaitán and Patrick Meumeu Yomsi. 2018. FF-DBF-WIN: On the Forced-Forward Demand-Bound Function Analysis for Wireless Industrial Networks. In *Work-in-Progress Session of the 30th Euromicro Conference on Real-Time System (ECRTS)*. 13-15.

[19] Oliver Harms and Olaf Landsiedel. 2020. MASTER: Long-term stable routing and scheduling in low-power wireless networks. In *2020 16th International Conference on Distributed Computing in Sensor Systems (DCOSS)*. IEEE, 86-94.

[20] Wazir Zada Khan, MH Rehman, Hussein Mohammed Zangoti, Muhammad Khalil Afzal, Nasrullah Armi, and Khaled Salah. 2020. Industrial internet of things: Recent advances, enabling technologies and open challenges. *Computers & Electrical Engineering* 81 (2020), 106522.

[21] Arvind Kumar, Rakesh Matam, and Mithun Mukherjee. 2021. Time Optimal Concurrent Data collection Trees for IoT Applications. In *2021 IEEE International Systems Conference (SysCon)*. IEEE, 1-7.

[22] Adrian Lang, Yi Wang, Cheng Feng, Eleni Stai, and Gabriela Hug. 2021. Data Aggregation Point Placement for Smart Meters in the Smart Grid. *IEEE Trans. on Smart Grid* 13, 1 (2021), 541-554.

[23] Mu Li, Xiao-Chen Lian, James T Kwok, and Bao-Liang Lu. 2011. Time and space efficient spectral clustering via column sampling. In *CVPR 2011*. IEEE, 2297-2304.

[24] Wei Liu, Hiroki Nishiyama, Nei Kato, Yoshitaka Shimizu, and Tomoaki Kumagai. 2012. A novel gateway selection method to maximize the system throughput of wireless mesh network deployed in disaster areas. In *2012 IEEE 23rd International Symposium on Personal, Indoor and Mobile Radio Communications-(PIMRC)*. IEEE, 771-776.

[25] Chenyang Lu, Abusayeed Saifullah, Bo Li, Mo Sha, Humberto Gonzalez, Dolvara Gunatilaka, Chengjie Wu, Lanshun Nie, and Yixin Chen. 2015. Real-time wireless sensor-actuator networks for industrial cyber-physical systems. *Proc. IEEE* 104, 5 (2015), 1013-1024.

[26] Leonardo Maccari, Quynh Nguyen, and Renato Lo Cigno. 2016. On the computation of centrality metrics for network security in mesh networks. In *2016 IEEE Global Communications Conference (GLOBECOM)*. IEEE, 1-6.

[27] Naércio Magaia, Alexandre P Francisco, Paulo Pereira, and Miguel Correia. 2015. Betweenness centrality in delay tolerant networks: A survey. *Ad Hoc Networks* 33 (2015), 284-305.

[28] Luca Mottola and Gian Pietro Picco. 2010. MUSTER: Adaptive energy-aware multisink routing in wireless sensor networks. *IEEE Trans. on Mobile Computing* 10, 12 (2010), 1694-1709.

[29] Andrew Ng, Michael Jordan, and Yair Weiss. 2001. On spectral clustering: Analysis and an algorithm. *Advances in neural information processing systems* 14 (2001).

[30] Eduardo MR Oliveira, Heitor S Ramos, and Antonio AF Loureiro. 2010. Centrality-based routing for wireless sensor networks. In *2010 IFIP Wireless Days*. IEEE, 1-5.

[31] Mayra Z. Rodriguez, Cesar H. Comin, Dalcimar Casanova, Odemir M. Bruno, Diego R. Amancio, Luciano da F. Costa, and Francisco A. Rodrigues. 2019. Clustering algorithms: A comparative approach. *PLOS ONE* 14, 1 (01 2019), 1-34. https://doi.org/10.1371/journal.pone.0210236

[32] Abusayeed Saifullah, You Xu, Chenyang Lu, and Yixin Chen. 2010. Real-time scheduling for WirelessHART networks. In *2010 31st IEEE Real-Time Systems Symposium*. IEEE, 150-159.

[33] Emiliano Sisinni, Abusayeed Saifullah, Song Han, Ulf Jennehag, and Mikael Gidlund. 2018. Industrial Internet of Things: Challenges, opportunities, and directions. *IEEE Trans. on Industrial Informatics* 14, 11 (2018), 4724-4734.

[34] Rebiha Souadih and Fouzi Semchedine. 2022. Energy-efficient coverage and connectivity of wireless sensor network in the framework of hybrid sensor and vehicular network. *International Journal of Computers and Applications* 44, 5 (2022), 444-454.

[35] Sylia Mekhmoukh Taleb, Yassine Meraihi, Asma Benmessaoud Gabis, Seyedali Mirjalili, and Amar Ramdane-Cherif. 2022. Nodes placement in wireless mesh networks using optimization approaches: a survey. *Neural Computing and Applications* (2022), 1-37.

[36] Rasool Tavakoli, Majid Nabi, Twan Basten, and Kees Goossens. 2018. Topology management and TSCH scheduling for low-latency convergecast in in-vehicle WSNs. *IEEE Transactions on Industrial Informatics* 15, 2 (2018), 1082-1093.

[37] Federico Terraneo, Paolo Polidori, Alberto Leva, and William Fornaciari. 2018. TDMH-MAC: Real-time and multi-hop in the same wireless MAC. In *2018 IEEE Real-Time Systems Symposium (RTSS)*. IEEE, 277-287.

[38] Maryam Vahabi, Hamid Reza Faragardi, and Hossein Fotouhi. 2018. An analytical model for deploying mobile sinks in industrial Internet of Things. In *IEEE Wireless Communications and Networking Conference Workshops*. IEEE, 155-160.

[39] Thomas W Valente, Kathryn Coronges, Cynthia Lakon, and Elizabeth Costenbader. 2008. How correlated are network centrality measures? *Connections* 28, 1 (2008), 16.

[40] Andrés Vázquez-Rodas and J Luis. 2015. A centrality-based topology control protocol for wireless mesh networks. *Ad Hoc Networks* 24 (2015), 34-54.
[41] Stefano Vitturi, Luca Trevisan, Alberto Morato, Guglielmo Frigo, and Federico Tramarin. 2020. Evaluation of LoRaWAN for Sensor Data Collection in an IIoT-based Additive Manufacturing Project. In *2020 IEEE International Instrumentation and Measurement Technology Conference (I2MTC)*. IEEE, 1-6.

[42] Thumeera R Wanasinghe, Raymond G Gosine, Lesley Anne James, George KI Mann, Oscar De Silva, and Peter J Warrian. 2020. The internet of things in the oil and gas industry: a systematic review. *IEEE Internet of Things Journal* 7, 9 (2020), 8654-8673.

[43] Jiachen Wang, Tianyu Zhang, Dawei Shen, Xiaobo Sharon Hu, and Song Han. 2021. APaS: An adaptive partition-based scheduling framework for 6TiSCH networks. In *2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS)*. IEEE, 320-332.

[44] Thomas Watteyne, Joy Weiss, Lance Doherty, and Jonathan Simon. 2015. Industrial IEEE802. 15.4 e networks: Performance and trade-offs. In *2015 IEEE International Conference on Communications (ICC)*. IEEE, 604-609.

[45] Chengjie Wu, Dolvara Gunatilaka, Mo Sha, and Chenyang Lu. 2018. Real-time wireless routing for industrial internet of things. In *2018 IEEE/ACM Third International Conference on Internet-of-Things Design and Implementation (IoTDI)*. IEEE, 261-266.

[46] Changqing Xia, Xi Jin, and Peng Zeng. 2016. Resource analysis for wireless industrial networks. In *Int. Conference on Mobile Ad-Hoc and Sensor Networks (MSN)*. IEEE, 424-428.

[47] Bo Xing, Mayur Deshpande, Sharad Mehrotra, and Nalini Venkatasubramanian. 2010. Gateway designation for timely communications in instant mesh networks. In *2010 8th IEEE Int. Conf. on Pervasive Computing and Communications Workshops (PERCOM Workshops)*. IEEE, 564-569.

[48] Dan Xu, Wenli Jiao, Zhuang Yin, Bin Wu, Yao Peng, Xiaojiang Chen, Feng Chen, and Dingyi Fang. 2018. Enabling robust and reliable transmission in Internet of Things with multiple gateways. *Computer Networks* 146 (2018), 183-199.

[49] Dongkuan Xu and Yingjie Tian. 2015. A comprehensive survey of clustering algorithms. *Annals of Data Science* 2, 2 (2015), 165-193.