Latency Improvement Strategies for Reliability-Aware Scheduling in Industrial Wireless Sensor Networks

Abstract

We propose novel strategies for end-to-end reliability-aware scheduling in Industrial Wireless Sensor Networks (IWSNs). Because of stringent reliability requirements in industrial applications where missed packets may have disastrous or lethal consequences, all IWSN communication standards are based on Time Division Multiple Access (TDMA), allowing for deterministic channel access on the MAC layer. We therefore extend an existing generic and scalable reliability-aware scheduling approach by the name of SchedEx. SchedEx has proven to quickly produce TDMA schedules that guarantee a user-defined end-to-end reliability level $\underset{\_}{\rho }$ for all multihop communication in a WSN. Moreover, SchedEx executes orders of magnitude faster than recent algorithms in the literature while producing schedules with competitive latencies. We generalize the original problem formulation from single-channel to multichannel scheduling and propose a scalable integration into the existing SchedEx approach. We further introduce a novel optimal bound that produces TDMA schedules with latencies around 20% shorter than the original SchedEx algorithm. Combining the novel strategies with multiple sinks, multiple channels, and the introduced optimal bound, we could through simulations verify latency improvements by almost an order of magnitude, reducing the TDMA superframe execution times from tens of seconds to seconds only, which allows for a utilization of SchedEx for many time-critical control applications.

1. Introduction

The advantages of wireless technologies with respect to flexibility and cost compared to wired solutions together with the introduction of industrial wireless communication standards have led to a growing deployment of Industrial Wireless Sensor Networks (IWSNs) [1]. For an adaptation of WSN for control applications in industrial automation, though, the communication protocol stack must in a scalable way offer end-to-end quality of service (QoS) guarantees which is an acknowledged research challenge lacking a general enough solution [2, 3]. Further, actuator support in the problem formulation, as well as coexistence of interfering networks, is among the open issues that require attention from the research community [3].

IWSN provides an opportunity for flexible and cost-effective sensor networks but introduces difficult challenges. In scenarios with stringent end-to-end QoS requirements, wireless is not trivially implemented, mostly because WSNs suffer from a shared and open communication medium. QoS features, such as end-to-end latency or reliability, can be addressed on different communication layers. For instance, an improvement in terms of end-to-end reliability can be achieved by a change of route on the network layer, or a rescheduling on the MAC layer. One prominent approach to achieve end-to-end QoS guarantees is to apply contention-free medium access protocols, such as time-division medium access (TDMA) [4]. TDMA assigns dedicated transmission rights to the sensors in a repeating schedule. Energy-efficiency due to duty-cycling and a guaranteed access to the communication medium are avdantages of TDMA, as opposed to the best-effort strategies based on carrier sensing [5, 6]. This feature is especially relevant in densely populated sensor networks, with stringent QoS demands, such as for automation control in factories.

WirelessHART [7], the most widespread standard for IWSN, supports an IEEE 802.15.4e amendment for the MAC layer using a variant of TDMA on top of IEEE 802.15.4 2006/2012 PHY. WirelessHART does not dictate the choice of scheduling algorithm: it is the vendor who decides the implementation. Finding minimal size TDMA schedules is an NP-hard problem to solve, both in the single-channel case where concurrent noninterfering transmissions are allowed (slot-reuse [8]) and in the case of multichannel use (e.g., WirelessHART), where concurrent transmissions in dedicated slots may only be scheduled on different channels [9]. Combining multichannel use and slot-reuse is desired in order to further reduce the achievable schedule sizes but brings along a large complexity increase in the formal problem formulation. In order to address end-to-end QoS requirements, the common assumption for IWSN is that all network link quality information is collected at the network manager which stands responsible for scheduling, routing, and the distribution of control messages on the downlink to the sensors for both topology deployment and adjustment. The centralized collection of global control information allows for network wide optimal choices and QoS optimization with respect to, for example, fairness or jitter, which would otherwise not be possible in a decentralized setting.

The focus of this paper is on scalable reliability-aware scheduling. A scheduling algorithm is here defined as reliability-aware, if it guarantees a user-defined statistic within-network end-to-end reliability $\underset{\_}{\rho }\in [\mathrm{0,1}]$ that all packets created within a superframe arrive at their destination at the end of a predefined time interval. As opposed to existing work concerning reliable packet delivery [10, 11], a maximum latency can be guaranteed due to the integration with TDMA and controlled redundancy in terms of repeated transmissions. The proposed metrics for assessment are therefore the minimization of the schedule frame to minimize the maximum guaranteed latency under the guarantee of end-to-end reliability $\underset{\_}{\rho }$ . We significantly extend the work in [12] with the following contributions.

• (i)

The performance of the recent reliability-aware scheduling algorithm SchedEx from [12] is here improved by introducing an optimal bound that reduces latencies for the investigated convergecast topologies by on average 20%, while guaranteeing the same end-to-end reliability levels as in the original paper. A proof of correctness with respect to end-to-end reliability is given too.

(ii)

The results of the scalable extension show that the schedules are calculated about 20% faster than those in the original paper and that the performance in terms of latency outperforms those created by a recent but poorly scaling approach from [13] in all tested topologies.

(iii)

To the best of our knowledge, this is the first paper addressing scalable TDMA scheduling combining slot-reuse, multiple channels, and reliability-aware scheduling in combination. We provide numerous simulation results that verify how even for stringent end-to-end reliabilities of 99.999% all sensor readings can be collected within seconds using schedules that are calculated within microseconds, assuming a variant of WirelessHART that supports slot-reuse.

(iv)

The paper makes a case for the simple extendability of SchedEx for other features such as multichannel use and multisink deployment.

Where convergecast with a single sink does not suffice, SchedEx is here evaluated with different sink deployment plans. Our simulations reveal the latency gain that can be expected for the given topologies using reliability-aware scheduling, highly relevant for mission-critical applications.

The structure of this paper is as follows. Section 2 presents the relevant research in the area. In Section 3 the network model is described, and Section 4 defines the formal problem formulation. The SchedEx algorithm is explained in Section 5. Section 6 introduces the improvements and extensions. The simulations are explained in Section 7, and the results are presented in Section 8. A discussion and concluding remarks follow in Sections 9 and 10, respectively.

2. Related Work

A lack of a generic framework that addresses the end-to-end QoS concerns for mission-critical applications over WSN has been reported in [2] with regards to the MAC layer, and more generally in [3]. Many noteworthy contributions to QoS-aware scheduling have been made [14–20], but since the requirements in industrial automation differ heavily from traditional applications for WSN, alternative approaches are required.

The work in [17] investigates multichannel transmissions with dynamic channel assignment to reduce interference. Network lifetime maximization has been investigated under the consideration of energy harvesting [20], applying cross-layer optimization [19], and the use of redundant actors that support the network in regions where sensor availability drops with time [18]. However, contention-based approaches, such as [17–20], are not suitable to guarantee end-to-end reliability, because of their best-effort nature.

TDMA-based MAC protocols are the most common means to ensure reliability and latency bounds for WSNs (e.g., [8, 12, 21, 22]). TDMA scheduling is an NP-hard combinatorial problem in its most basic static version without the consideration of time synchronization or reliability guarantees [8]. Finding optimal or even initial branch-and-cut solutions using traditional Integer Programming can take weeks or months for moderately large topologies of sizes around 50 nodes without even considering stringent QoS constraints.

In [8], the authors prove the schedule minimization problem with guaranteed packet delivery to be NP-hard and propose two scalable scheduling algorithms to solve it. In [22], the authors show how their SAS-TDMA outperforms the algorithms from [8] under the consideration of a harsh dynamic industrial environment. However, SAS-TDMA does not come with any guarantees in terms of reliability. The TDMA-based multichannel scheduling approaches introduced in [23, 24] address the scheduling problem assuming static network topologies without the consideration of slot-reuse or reliability guarantees. Offline dimensioning approaches, such as GinMAC [25] and Burst [26], address the problem for industrial networks by maximizing end-to-end reliability under latency constraints. However, they cannot be considered for large or dynamic networks because of their time-consuming execution. The authors in [13] introduce a two-phase scheduling strategy that extends existing scheduling algorithms and maximizes end-to-end reliability under a fixed latency constraint, outperforming the algorithms introduced in [8]. They further investigate redundancy in form of multipath routing in both theory and simulations, and their results show the superiority of single-path routing, not even considering communication overhead in their comparison. The SchedEx scheduling approach is introduced in [12]. SchedEx produces schedules that guarantee a given end-to-end reliability while cooptimizing latency. Simulations show that SchedEx is an order of magnitude faster than the strategy from [13]. So far, SchedEx has only been investigated on single sink topologies and a single communication channel. In this paper the SchedEx approach is further improved with respect to execution time and end-to-end latency performance. Simulations verify its suitability even for multichannel and multisink scenarios, compared to existing work.

3. Model Assumptions

We base our network model, optimization problem formulation, and simulation setup on the work in [12], extending it for multiple channel use in order to allow for an easy comparison between the approaches. Multiple sinks are already supported but have not yet been evaluated. A WSN is defined as a digraph $G=\{V,E\}$ with the set of sensors $V=\mathcal{T}\cup \mathcal{S}$ , where $\mathcal{T}$ are the transceivers, $\mathcal{S}$ sinks, and $\mathcal{T}\cap \mathcal{S}=\varnothing$ . The successful arrival of a packet is modeled as the node-to-node packet arrival rate that includes the successful reception of an acknowledgement (ACK) on the sender side before the end of the time-slot has been reached. $E=\{(t,p)\hspace{0.17em}|\hspace{0.17em}{q}_{tp}>\mathrm{0}\}$ is the set of directed links from any transceiver $t\in \mathcal{T}$ to any sensor $p\in V$ . Q is the link quality matrix of size $|\mathcal{T}|\times |V|$ . Node-to-node packet reception rates are expressed as $q_{tp}$ . The state of the network is represented by a buffer $b=(b_{\mathrm{1}},\dots ,b_{|\mathcal{T}|})$ , where $b_t$ is the amount of packets waiting for transmission at sensor t. $b=\overrightarrow{x}$ signifies that each sensor has equally x packets in the local buffer. All sensors operate in half-duplex mode and time synchronization between the sensors is assumed to be guaranteed by the lower layers of the protocol stack. Multihop routing is allowed. Packets are produced at the beginning of a schedule frame F and the common deadline to be held is the final slot in the schedule, after which all sensors have to have succeeded to transmit all their packets. Packets that could not be transmitted in F are removed from the buffer in order to preclude contention problems. Assuming stochastic independence among transmissions, any two transmissions from t to p and $t^{\prime }$ to $p^{\prime }$ succeed with a probability

$$\begin{array}{cc}& P_{\mathrm{s}\mathrm{u}\mathrm{c}\mathrm{c}\mathrm{e}\mathrm{s}\mathrm{s}}\left(tp,t^{\prime }{p}^{\prime }\right)=q_{tp}{q}_{t^{\prime }{p}^{\prime }}.\end{array}$$

(1)

For reasons of simplicity, topology changes are not considered and all channels of a link have the same link quality $q_{tp}$ .

4. Problem Formulation

Let $o:\mathcal{I}\to \mathbb{R}$ be an objective function that assigns each configuration of the network $x\in \mathcal{I}$ a quality index.

In this paper, the end-to-end delay in terms of schedule frame size for a given end-to-end reliability demand $\underset{\_}{\rho }$ shall be minimized as in

$$\begin{array}{cc}& \underset{x}{\min }\hspace{1em}o\left(x\right)=\left|F\right|,\forall x=\left(R,F\right)\in \mathcal{I}\end{array}$$

(2)

$\begin{array}{cc}& \text{subject\hspace{0.17em}\hspace{0.17em}to}\hspace{1em}{c}_{\mathrm{0}}\text{:}\hspace{0.17em}\hspace{0.17em}\underset{\_}{\rho }\le \rho \end{array}$

(3)

$\begin{array}{cc}& \hspace{1em}{c}_{\mathrm{1}}\text{:}\hspace{0.17em}\hspace{0.17em}{r}_{tt}=\mathrm{0}\end{array}$

(4)

$\begin{array}{cc}& \hspace{1em}{c}_{\mathrm{2}}\text{:}\hspace{0.17em}\hspace{0.17em}{\displaystyle \sum }_{p\in V}{r}_{tp}\le \mathrm{1}\end{array}$

(5)

$\begin{array}{cc}& \hspace{1em}{c}_{\mathrm{3}}\text{:}\hspace{0.17em}\hspace{0.17em}{r}_{tp}=\mathrm{1}⟹\left(t,p\right)\in E\end{array}$

(6)

$\begin{array}{cc}& \hspace{1em}{c}_{\mathrm{4}}\text{:}\hspace{0.17em}\hspace{0.17em}{f}_{st}=\mathrm{1}⟹f_{sp}{q}_{pt}=\mathrm{0}\end{array}$

(7)

$\begin{array}{cc}& \hspace{1em}{c}_{\mathrm{5}}\text{:}\hspace{0.17em}\hspace{0.17em}{f}_{st}{f}_{s{t}^{\prime }}=\mathrm{1}⟹q_{tp}{q}_{t^{\prime }p}=\mathrm{0}\hspace{0.17em}\hspace{0.17em}\vee \end{array}$

(8)

$\begin{array}{cc}& \hspace{1em}{\displaystyle \sum }_{t\in \mathcal{T}}{f}_{st}{r}_{tp}=\mathrm{0}\hspace{0.17em}\hspace{0.17em}\vee \end{array}$

(9)

$\begin{array}{cc}& \hspace{1em}{\mathrm{c}\mathrm{h}}_{ts}\ne {\mathrm{c}\mathrm{h}}_{t^{\prime }s}\wedge r_{tp}+r_{t^{\prime }p}\le \mathrm{1}.\end{array}$

(10)

End-to-end reliability $\rho \in [\mathrm{0,1}]$ , schedule frame F with its transmission rights $f_{st}\in \{\mathrm{0,1}\}$ , and channel assignment $\mathrm{c}{\mathrm{h}}_{ts}\in \{\mathrm{1},\dots ,\mathrm{C}{\mathrm{H}}_{\mathrm{M}\mathrm{A}\mathrm{X}}\}$ are the variables to be identified. All constraints $c_i$ must hold true for x in order to be considered a feasible solution $x\in \mathcal{I}$ . It follows an explanation of the equations.

A schedule frame F is a binary matrix of size $m\times |\mathcal{T}|$ that with $f_{st}=\mathrm{1}$ assigns transmitter $t\in \mathcal{T}$ transmission allowance at discretized time k in time-slot $s=k\mathrm{mod}m$ . F is continuously repeated in order to ensure that the scheduled transceivers can transmit periodically. In (2), $\left|·\right|$ signifies the size of the frame, m. $\mathrm{S}\mathrm{A}(R)=F$ describes the deterministic scheduling algorithm $\mathrm{S}\mathrm{A}$ that creates a schedule frame F given a single-path routing table R. $\underset{\_}{\rho }$ in (3) is the required user-defined end-to-end reliability and ρ the actual end-to-end reliability of the network.

The formal routing constraints (4)–(6) are expressed over a binary routing table R of size $\left|\mathcal{T}\right|\times \left|V\right|$ that by $r_{tp}=\mathrm{1}$ assigns each transceiver in row t one recipient, its so called parent, p. A successful routing table that fulfills all constraints is here expected to be supplied by the network layer.

A schedule F is called valid or collision-free if no receiving sensor is disturbed by a second concurrent transmission (7)-(8) (either no sensor exists that hears two concurrent transmissions or that sensor is not interested in either transmission, or both send via different channels while not sharing the same parent). According to the constraints, spatial-reuse within a slot is allowed if no conflicts arise and transceivers may be scheduled in multiple slots of the same superframe. Constraint (10) for channel assignment has been added in this paper. Channel assignment is realized by ${\mathrm{c}\mathrm{h}}_{ts}\in \{\mathrm{1},\dots ,{\mathrm{C}\mathrm{H}}_{\mathrm{M}\mathrm{A}\mathrm{X}}\}$ , the channel over which transceiver t transmits in time-slot s of frame F.

5. SchedEx

In [12], the authors compare the two-phase schedule reliability enhancer from [13] and a novel scheduling algorithm extension for reliability-awareness by name SchedEx, with respect to performance and runtime. They show that the schedule enhancer does not scale in the size of the network by both complexity analysis and simulations. For WSNs in industrial applications, the deployed sensors are not capable of running long processes to identify better schedules, because of battery drainage and restricted computational power. SchedEx shows to scale well in the size of the network and guarantees a reliability lower bound $\underset{\_}{\rho }$ instead of calculating the exact reliability as done in [13]. Link quality varies over time, and calculating an exact reliability is only of theoretical interest, whereas a swiftly produced schedule that guarantees a lower bound is of practical importance.

The two-phase schedule enhancer from [13] produced schedules that are on average between 5 and 20% shorter than those for SchedEx, with a cost between 4000 and 12000% runtime for networks with node-to-node reliability levels produced by the Rayleigh Fading model with a signal to noise ratio of 60 dB. For 50 dB, the results for SchedEx are reported to be on average better than those for the two-phase enhancer. SchedEx produces the schedules in runtimes 2-3 orders of magnitude faster than the two-phase approach. The simulations in [12] are conducted for topologies of sizes between 50 and 200 uniformly at random distributed sensors, for single-path routing over a single channel, given a single sink in the center of a circular area.

As explained in [12], slotted scheduling algorithms operate as follows.

• (i)

While not all packet buffers are empty,

• (1)

apply scheduling algorithm to decide the next slot(s),

(2)

append the slot(s) to the schedule frame,

(3)

update packet buffers according to the transitions,

(4)

update meta-data (if required).

SchedEx substitutes step 3 for packet update to ensure reliability by a controlled packet move delay. The authors in [12] therefore propose Algorithm 1 which maintains a vector of down-counters for all transceivers in the network, based on $\overrightarrow{\tau }$ . Given $\overrightarrow{\tau }$ , an initial attempt vector is created where each transmitter contains the amount of attempts per packet to ensure a link reliability which is calculated given the user-defined end-to-end reliability demand $\underset{\_}{\rho }$ . Each time a transmission attempt for a sensor has been registered in a slot, its counter is decremented. SchedEx only registers a packet move from a transmitter to a receiver, once its down-counter reaches 0, which even triggers a reinitialization of the counter thereafter to the required amount of attempts per transmission. The algorithm terminates once all packets have arrived at their destinations, identical to the none reliability-aware scheduling version.

Algorithm 1: Update Packet Buffers $$(t,\mathcal{S},b,c,\mathrm{\tau })$$ .

Input: Scheduled Transmitter $$t\in \mathcal{T}$$ , Sinks $$\mathcal{S}$$ , Buffer State b,

  Counter Vector c, Repetition Vector τ

(1) if   $$b_t>\mathrm{0}$$   then

(2)   $$c_{t^{--}}$$ // count down attempts for transmitter t

(3)  if   $$c_t=\mathrm{0}$$   then

(4)    $$b_{t^{--}}$$ // remove packet from transmitter buffer

(5)   if   $$R_t\notin \mathcal{S}$$   then

(6)     $$b_{R_t}\text{}+\text{}+$$ // add packet to receiver buffer

(7)    $$c_t\leftarrow {\mathrm{\tau }}_t$$ // update counter

SchedEx, the slot-based scheduling algorithm extension improved in

this paper by a tighter bound introduced further below.

The lower-bound formulation of minimal repetitions $n_t$ per transceiver from [12] to ensure the end-to-end reliability $\underset{\_}{\rho }$ is here repeated for convenience. It applies to networks utilizing a single-path routing table R and assesses a total amount of $k_{\mathrm{1}},\dots ,k_{|\mathcal{T}|}$ packets passing each transceiver t, $\mathrm{1}\le t\le \mathcal{T}$ on their way towards any of the sinks via multihop. An end-to-end reliability of $\underset{\_}{\rho }$ is guaranteed if $n_t$ repetitions are executed for each route from t to parent $R_t$ for each packet over the whole network, according to

$$\begin{array}{cc}& n_t=⌈\frac{\log \left(\mathrm{1}-{\underset{\_}{\rho }}^{\mathrm{1}/\left(\left|\mathcal{T}\right|·k_t\right)}\right)}{\log \left(\mathrm{1}-q_{t{R}_t}\right)}⌉,\forall t\in \mathcal{T}.\end{array}$$

(11)

Given the lower bound $n_t$ for a single packet, a repetition vector $\overrightarrow{\tau }$ can be created with ${\tau }_t=n_t$ . If each packet transmission through t ensures at least ${\tau }_t$ attempts, the end-to-end reliability of the network, ρ, will be larger or equal to the demand $\underset{\_}{\rho }$ .

6. Method

SchedEx calculates the minimal amount $n_t$ (11) of repetition of attempts to ensure a minimum end-to-end reliability $\underset{\_}{\rho }$ over the entire WSN, given the node-to-node packet reception rates between all sensors. $n_t$ is then integrated algorithmically into the scheduling algorithm to ensure $\underset{\_}{\rho }$ for superframes produced by arbitrary scheduling algorithms. The improvements made in this paper are outlined below.

6.1. Multichannel Assignment

Each centralized slot-based scheduling algorithm, in Step 1 of the loop, sequentially adds transceivers to the slot until a conflict, according to constraints $c_{\mathrm{4}}$ or $c_{\mathrm{5}}$ , emerges. We extend the routine that checks the conflicts for single channel networks by a loop that iterates all channels for a new candidate transmitter and only report a conflict if the transmitter conflicts for all available channels in $\{\mathrm{1},\dots ,{\mathrm{C}\mathrm{H}}_{\mathrm{M}\mathrm{A}\mathrm{X}}\}$ . Otherwise, the transceiver is scheduled for the first nonconflicting channel, in numeric order.

6.2. SchedEx Improvement

In this section, we introduce a new formula that substitutes (11), prove its correctness, and show that the adjusted formula requires the proven lowest amount of repetitions per scheduled link for SchedEx and any given initial buffer b.

Proposition 1.

Given a network with a single-path routing table R, sinks $\mathcal{S}$ , transceivers $\mathcal{T}$ , a link quality matrix Q, and a total amount of $k_{\mathrm{1}},\dots ,k_{|\mathcal{T}|}$ packets passing each transceiver $t,\mathrm{1}\le t\le \mathcal{T}$ on their way towards any of the sinks via multihop. An end-to-end reliability of $\underset{\_}{\rho }$ can be guaranteed if $n_t$ repetitions are executed for each route from t to $R_t$ for each packet over the whole network, according to

$$\begin{array}{cc}& n_t=⌈\frac{\log \left(\mathrm{1}-{\underset{\_}{\rho }}_t\right)}{\log \left(\mathrm{1}-q_{t{R}_t}\right)}⌉,\forall t\in \mathcal{T}\end{array}$$

(12)

with

$$\begin{array}{cc}& {\underset{\_}{\rho }}_t={\underset{\_}{\rho }}^{\mathrm{1}/\widehat{k}},\end{array}$$

(13)

$\begin{array}{cc}& \widehat{k}={\displaystyle \sum }_{t\in \mathcal{T}}{k}_t.\end{array}$

(14)

Proof.

For the case of one link and k packets, this is trivially true because of Proposition  2 in [12]. For $|\mathcal{T}|$ links, and $k_t$ transmissions for each $t\in \mathcal{T}$ , we get, according to (14), a total of $\widehat{k}$ stochastically independent transmissions in the network. We therefore need to guarantee

$$\begin{array}{cc}& \underset{\_}{\rho }\le {\displaystyle \prod }_{i=\mathrm{1}}^{\widehat{k}}{\underset{\_}{\rho }}_i,\end{array}$$

(15)

to make (12) fulfilled (3) for each transmission. However, this is fulfilled because of

$$\begin{array}{cc}& {\displaystyle \prod }_{t\in \mathcal{T}}{\underset{\_}{\rho }}_t={\displaystyle \prod }_{i=\mathrm{1}}^{\widehat{k}}{\underset{\_}{\rho }}_i={\underset{\_}{\rho }}_i^{\widehat{k}}={\left({\underset{\_}{\rho }}^{\mathrm{1}/\widehat{k}}\right)}^{\widehat{k}}=\underset{\_}{\rho }.\end{array}$$

(16)

Due to the equality of ${\prod }_{t\in \mathcal{T}}‍{\underset{\_}{\rho }}_t$ and $\underset{\_}{\rho }$ , we get that (13) is tightest bound for SchedEx producing a minimal demand of repetitions $n_t$ per transceiver $t\in \mathcal{T}$ , guaranteeing end-to-end reliability constraint $\underset{\_}{\rho }$ .

7. Simulations

We apply single-path routing in this paper. Routing tables are determined by the Dijkstra shortest path algorithm using the expected transmission count (ETX) metric [27]. Table 1 contains the network model parameters.

Table 1

Simulation setup parameters.

Parameter	Value
Routing	Single-path
Routing algorithm	Shortest path (ETX)
Network size	$$\{\mathrm{50,100,200,400,800}\}$$
Channel model	Rayleigh Fading
$$a_n$$	67.7328
$$g_n$$	0.9819
$${\mathrm{\gamma }}_{pn}$$	4.2935
α	3.3
λ	0.5
SNR ( $${\mathrm{\gamma }}_n$$ )	60 dB
Transmission range $$r_t$$	30 units
Interference range $$r_i$$	60 units

7.1. Topologies

A simulation model with n randomly distributed nodes in a circular area of radius 100 units around a center point at $(\mathrm{100,100})$ is applied. The first $n\lambda /(\lambda +\mathrm{1})$ nodes are distributed uniformly at random within the inner circle of radius $\mathrm{100}/\sqrt{\mathrm{2}}$ , with $\lambda \in [\mathrm{0,1}]$ . The remaining nodes are randomly distributed in the outer partition of the circle. All sensors in $\mathcal{T}$ have a packet waiting for transmission; thus, $b=\overrightarrow{\mathrm{1}}$ .

We analyze 50 topologies, each ten of sizes 50, 100, 200, 400, and 800. SchedEx supports WSNs with multiple sinks, while the simulations only use a single sink. We extend the work by assessing each topology in three variations, with

• (1)

a single sink in the center at $(\mathrm{100,100})$ ,

(2)

two sinks, one at $(\mathrm{50,50})$ and one at $(\mathrm{150,150})$ ,

(3)

four sinks at $\{(\mathrm{50,50}),(\mathrm{50,150}),(\mathrm{150,50}),(\mathrm{150,150})\}$ .

For the multisink topologies, all sinks are connected via a backbone-network, which is why the choice of sink for transmission does not matter for the sensors. We investigate all scenarios first without reliability constraint and then for reliability demand $\underset{\_}{\rho }\in \{\mathrm{0.9,0.999,0.99999}\}$ . All topologies with their calculated link quality levels are publicly available (https://github.com/feldob/wsnScenarios/tree/master/SchedEx%2B). We utilize four scheduling algorithms, namely, node-based scheduling [8], level-based scheduling [8], dedicated scheduling [13], and shared scheduling [13], following the same setup. The interference range is modeled by directed packet reception rates of $\mathrm{0.00001}$ , assuring the avoidance of transmissions for interfering sensors.

8. Results

8.1. Multiple Channels, Reliability-Unaware

Figure 1 illustrates the impact of the amount of utilized channels on latency and runtime. In terms of schedule size the performance is similar for all algorithms. Node-based scheduling provides the majority of shortest schedules for the given topologies, with a runtime that is between 50 and 220% faster than for the competitors. For one and two channels, node-based scheduling is clearly better, whereas the variance in the amount of utilized channels. For 8 and 15 channels the expected performance is very similar, also because the results converge towards the theoretical optimum $⌈|\mathcal{T}|/|\mathcal{S}|⌉$ . The dedicated scheduling algorithm scales worst in the amount of channels with respect to runtime.

Figure 1

The average impact of the amount of available channels on the scheduling performance (a) and runtime (b) of the benchmarked scheduling algorithms. The more channels are utilized, the less impact has the choice of scheduling algorithm on the latency performance.

8.2. Multiple Channels, Reliability-Aware

We define the simulations using $n_t$ from (11) as SchedEx(1) and $n_t$ from (12) as SchedEx(2). Table 2 presents the reliability-aware scheduling results for the two SchedEx variants and the two-phase approach proposed in [13]. Figure 2 presents the scheduling and runtime performance for the competitors in comparison. With few exceptions, SchedEx(2) is best in terms of minimizing latency, while guaranteeing reliability, inspite of the amount of channels. SchedEx(1) performance slightly decreases in the amount of channels utilized, with schedules that are about 20% longer than the best ones identified (almost exceptionally by SchedEx(2)). The schedules from the two-phase approach are throughout about 10–16% longer than the best ones found. SchedEx(1) has longer execution times compared to SchedEx(2) by in average ca. 20%. The schedules are in average 20% longer which explains the increase in runtime, since both are based on the same algorithm. The two-phase approach is on average 35–55 times slower than SchedEx(2).

Table 2

Results for node-based scheduling given the networks of 5 different sizes, 1–15 utilized channels, and a stringent reliability requirement of $$\underset{\_}{\mathrm{\rho }}=\mathrm{0.99999}$$ .

Reliability algorithm		SchedEx(1)		SchedEx(2)		Two-phase approach
Size	Channels	ms	$$|\mathcal{F}|$$	ms	$$|\mathcal{F}|$$	ms	$$|\mathcal{F}|$$
1 sink topology
50	1	$$\mathrm{7}\pm \mathrm{1}$$	$$\mathrm{1423}\pm \mathrm{469}$$	$$\mathbf{7}\pm \mathrm{1}$$	$$\mathbf{1223}\pm \mathrm{368}$$	$$\mathrm{863}\pm \mathrm{512}$$	$$\mathrm{1364}\pm \mathrm{416}$$
	2	$$\mathrm{5}\pm \mathrm{1}$$	$$\mathrm{869}\pm \mathrm{267}$$	$$\mathbf{5}\pm \mathrm{1}$$	$$\mathbf{745}\pm \mathrm{215}$$	$$\mathrm{472}\pm \mathrm{244}$$	$$\mathrm{877}\pm \mathrm{257}$$
	4	$$\mathrm{4}\pm \mathrm{1}$$	$$\mathrm{761}\pm \mathrm{229}$$	$$\mathbf{4}\pm \mathrm{1}$$	$$\mathbf{648}\pm \mathrm{181}$$	$$\mathrm{393}\pm \mathrm{191}$$	$$\mathrm{755}\pm \mathrm{208}$$
	8	$$\mathrm{5}\pm \mathrm{1}$$	$$\mathrm{759}\pm \mathrm{225}$$	$$\mathbf{4}\pm \mathrm{1}$$	$$\mathbf{646}\pm \mathrm{181}$$	$$\mathrm{389}\pm \mathrm{192}$$	$$\mathrm{755}\pm \mathrm{208}$$
	15	$$\mathrm{6}\pm \mathrm{1}$$	$$\mathrm{759}\pm \mathrm{225}$$	$$\mathbf{5}\pm \mathrm{1}$$	$$\mathbf{646}\pm \mathrm{181}$$	$$\mathrm{390}\pm \mathrm{191}$$	$$\mathrm{755}\pm \mathrm{208}$$
200	1	$$\mathrm{85}\pm \mathrm{4}$$	$$\mathrm{3648}\pm \mathrm{112}$$	$$\mathbf{79}\pm \mathrm{2}$$	$$\mathbf{3232}\pm \mathrm{98}$$	$$\mathrm{6779}\pm \mathrm{501}$$	$$\mathrm{3512}\pm \mathrm{95}$$
	2	$$\mathrm{62}\pm \mathrm{6}$$	$$\mathrm{2565}\pm \mathrm{140}$$	$$\mathbf{59}\pm \mathrm{10}$$	$$\mathbf{2241}\pm \mathrm{119}$$	$$\mathrm{3760}\pm \mathrm{239}$$	$$\mathrm{2440}\pm \mathrm{102}$$
	4	$$\mathrm{44}\pm \mathrm{4}$$	$$\mathrm{2307}\pm \mathrm{182}$$	$$\mathbf{39}\pm \mathrm{1}$$	$$\mathbf{2003}\pm \mathrm{155}$$	$$\mathrm{3164}\pm \mathrm{282}$$	$$\mathrm{2148}\pm \mathrm{147}$$
	8	$$\mathrm{38}\pm \mathrm{3}$$	$$\mathrm{2286}\pm \mathrm{186}$$	$$\mathbf{34}\pm \mathrm{1}$$	$$\mathbf{1985}\pm \mathrm{159}$$	$$\mathrm{3054}\pm \mathrm{266}$$	$$\mathrm{2115}\pm \mathrm{147}$$
	15	$$\mathrm{40}\pm \mathrm{3}$$	$$\mathrm{2286}\pm \mathrm{186}$$	$$\mathbf{36}\pm \mathrm{1}$$	$$\mathbf{1985}\pm \mathrm{159}$$	$$\mathrm{3063}\pm \mathrm{258}$$	$$\mathrm{2115}\pm \mathrm{147}$$
800	1	$$\mathrm{1644}\pm \mathrm{36}$$	$$\mathrm{14925}\pm \mathrm{204}$$	$$\mathbf{1605}\pm \mathrm{68}$$	$$\mathbf{13228}\pm \mathrm{176}$$	$$\mathrm{353375}\pm \mathrm{36084}$$	$$\mathrm{14226}\pm \mathrm{147}$$
	2	$$\mathrm{1102}\pm \mathrm{17}$$	$$\mathrm{10653}\pm \mathrm{238}$$	$$\mathbf{1052}\pm \mathrm{9}$$	$$\mathbf{9309}\pm \mathrm{197}$$	$$\mathrm{135011}\pm \mathrm{8600}$$	$$\mathrm{10051}\pm \mathrm{181}$$
	4	$$\mathrm{704}\pm \mathrm{12}$$	$$\mathrm{9879}\pm \mathrm{200}$$	$$\mathbf{670}\pm \mathrm{12}$$	$$\mathbf{8569}\pm \mathrm{172}$$	$$\mathrm{105797}\pm \mathrm{7189}$$	$$\mathrm{9008}\pm \mathrm{141}$$
	8	$$\mathrm{505}\pm \mathrm{8}$$	$$\mathrm{9856}\pm \mathrm{199}$$	$$\mathbf{477}\pm \mathrm{5}$$	$$\mathbf{8546}\pm \mathrm{176}$$	$$\mathrm{106114}\pm \mathrm{9437}$$	$$\mathrm{8888}\pm \mathrm{148}$$
	15	$$\mathrm{514}\pm \mathrm{8}$$	$$\mathrm{9856}\pm \mathrm{199}$$	$$\mathbf{483}\pm \mathrm{7}$$	$$\mathbf{8546}\pm \mathrm{176}$$	$$\mathrm{105777}\pm \mathrm{8073}$$	$$\mathrm{8886}\pm \mathrm{147}$$
4 sink topologies
50	1	$$\mathbf{4}\pm \mathrm{1}$$	$$\mathrm{366}\pm \mathrm{85}$$	$$\mathbf{4}\pm \mathrm{1}$$	$$\mathbf{343}\pm \mathrm{78}$$	$$\mathrm{83}\pm \mathrm{24}$$	$$\mathrm{392}\pm \mathrm{71}$$
	2	$$\mathbf{3}\pm \mathrm{0}$$	$$\mathrm{229}\pm \mathrm{74}$$	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathbf{214}\pm \mathrm{67}$$	$$\mathrm{52}\pm \mathrm{16}$$	$$\mathrm{257}\pm \mathrm{58}$$
	4	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathrm{198}\pm \mathrm{63}$$	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathbf{183}\pm \mathrm{57}$$	$$\mathrm{45}\pm \mathrm{16}$$	$$\mathrm{211}\pm \mathrm{52}$$
	8	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathrm{198}\pm \mathrm{63}$$	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathbf{182}\pm \mathrm{56}$$	$$\mathrm{42}\pm \mathrm{13}$$	$$\mathrm{209}\pm \mathrm{50}$$
	15	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathrm{198}\pm \mathrm{63}$$	$$\mathbf{2}\pm \mathrm{0}$$	$$\mathbf{182}\pm \mathrm{56}$$	$$\mathrm{43}\pm \mathrm{13}$$	$$\mathrm{209}\pm \mathrm{50}$$
200	1	$$\mathrm{49}\pm \mathrm{1}$$	$$\mathrm{1037}\pm \mathrm{74}$$	$$\mathbf{48}\pm \mathrm{2}$$	$$\mathbf{978}\pm \mathrm{63}$$	$$\mathrm{926}\pm \mathrm{89}$$	$$\mathrm{1153}\pm \mathrm{72}$$
	2	$$\mathrm{34}\pm \mathrm{2}$$	$$\mathrm{604}\pm \mathrm{41}$$	$$\mathbf{33}\pm \mathrm{2}$$	$$\mathbf{563}\pm \mathrm{35}$$	$$\mathrm{533}\pm \mathrm{51}$$	$$\mathrm{706}\pm \mathrm{42}$$
	4	$$\mathrm{24}\pm \mathrm{4}$$	$$\mathrm{536}\pm \mathrm{30}$$	$$\mathbf{21}\pm \mathrm{1}$$	$$\mathbf{500}\pm \mathrm{25}$$	$$\mathrm{453}\pm \mathrm{29}$$	$$\mathrm{604}\pm \mathrm{21}$$
	8	$$\mathrm{20}\pm \mathrm{2}$$	$$\mathrm{534}\pm \mathrm{29}$$	$$\mathbf{19}\pm \mathrm{1}$$	$$\mathbf{498}\pm \mathrm{25}$$	$$\mathrm{445}\pm \mathrm{23}$$	$$\mathrm{596}\pm \mathrm{18}$$
	15	$$\mathrm{22}\pm \mathrm{3}$$	$$\mathrm{534}\pm \mathrm{29}$$	$$\mathbf{20}\pm \mathrm{1}$$	$$\mathbf{498}\pm \mathrm{25}$$	$$\mathrm{447}\pm \mathrm{29}$$	$$\mathrm{596}\pm \mathrm{18}$$
800	1	$$\mathrm{999}\pm \mathrm{25}$$	$$\mathrm{4147}\pm \mathrm{141}$$	$$\mathbf{984}\pm \mathrm{21}$$	$$\mathbf{3921}\pm \mathrm{120}$$	$$\mathrm{19189}\pm \mathrm{1211}$$	$$\mathrm{4519}\pm \mathrm{130}$$
	2	$$\mathrm{651}\pm \mathrm{20}$$	$$\mathrm{2409}\pm \mathrm{102}$$	$$\mathbf{632}\pm \mathrm{18}$$	$$\mathbf{2256}\pm \mathrm{78}$$	$$\mathrm{9434}\pm \mathrm{453}$$	$$\mathrm{2761}\pm \mathrm{92}$$
	4	$$\mathrm{367}\pm \mathrm{9}$$	$$\mathrm{2184}\pm \mathrm{94}$$	$$\mathbf{359}\pm \mathrm{11}$$	$$\mathbf{2027}\pm \mathrm{82}$$	$$\mathrm{8079}\pm \mathrm{309}$$	$$\mathrm{2436}\pm \mathrm{65}$$
	8	$$\mathrm{281}\pm \mathrm{5}$$	$$\mathrm{2181}\pm \mathrm{93}$$	$$\mathbf{271}\pm \mathrm{7}$$	$$\mathbf{2023}\pm \mathrm{83}$$	$$\mathrm{8014}\pm \mathrm{323}$$	$$\mathrm{2413}\pm \mathrm{67}$$
	15	$$\mathrm{283}\pm \mathrm{7}$$	$$\mathrm{2181}\pm \mathrm{93}$$	$$\mathbf{277}\pm \mathrm{10}$$	$$\mathbf{2023}\pm \mathrm{83}$$	$$\mathrm{8022}\pm \mathrm{297}$$	$$\mathrm{2414}\pm \mathrm{66}$$

Figure 2

The average impact of the amount of available channels on the scheduling performance (a) and runtime (b) for the three reliability-aware approaches. SchedEx(1) produces the shortest schedules throughout the investigation.

8.3. Multiple Sinks

The impact for the one, two, and four sink scenarios is presented in Figure 3(a) for basic scheduling and Figure 3(b) for reliability-aware scheduling. The results show that all algorithms react similar to the introduction of multiple sinks. For two sinks, schedule size can on average be reduced by ca. $\mathrm{40}\%$ and for four sinks by ca. $\mathrm{67}\%$ . For SchedEx(1), schedule size reduces relatively better in the amount of sinks, compared to the competitors. SchedEx(2) reduces latency by 47% for two instead of one sink and by 67% using four sinks. SchedEx(2) produces on average the shortest schedules for all scenario types, even though the competitors are catching up the higher the number of utilized sinks.

Figure 3

The average impact of the amount of available sinks on latency for the four scheduling algorithms (a) and the three reliability-aware scheduling approaches (b). Reliability-aware scheduling performance is equally positively correlated with the amount of deployed sinks in the network compared to basic scheduling.

8.4. Runtime Impact

Figures 4(a) and 4(b) illustrate the impact of multiple sinks and multiple channels, respectively, on the runtime of the scheduling. Where the amount of sinks has a large impact on the scheduling performance, the runtime is less strongly affected. The amount of applied channels, however, has a much larger impact on the algorithm runtime than the amount of sinks. The runtime increases substantially until a certain point. Thereafter, a performance decline can be observed.

Figure 4

The average execution time impact of the amount of available sinks (a) and channels (b), respectively, on the scheduling algorithms. The choice of utilized scheduling algorithm becomes less important with respect to latency performance the more channels are available. Node-based scheduling however performs best in both execution time and latency.

9. Discussion

We are interested in how the introduced formula (12) compares to the original one and how the scheduling algorithms scale in the amount of sinks and utilized channels. From the nonreliability-aware simulations, we derive that single-channel simulations, as conducted in previous studies, are not sufficient to evaluate the scheduling efficiency of an algorithm for real-life scenarios where multiple channels are available. The performance for the four algorithms is very different for one to four channels, and node-based scheduling seems to offer a good trade-off between frame-size and execution time. The overall general schedule size in Figure 3(a) suggests that the choice of a best scheduling algorithm with respect to schedule frame size is hard, because the summarized statistics reveal that all competitors perform on average very similar. For the reliability-aware simulations, the new formula (12) significantly outperforms the one from [12]. It is substantially faster in execution time and obtains better schedules than both SchedEx(1) and the two-phase approach from [13], with narrow variances. For the one-channel one-sink utilization on topologies of size 50 and reliability constraint $\underset{\_}{\rho }=\mathrm{0.99999}$ SchedEx(1) in [12] requires an expected runtime of 14.3 seconds, assuming WirelessHART with slot-sizes of 10 ms. SchedEx(2) utilizing four sinks and four channels in the same setup produces a 20% shorter schedule within 2 ms and reduces the expected runtime to 1.83 seconds, which implies a substantial improvement of nearly one order of magnitude. Assuming the same setup as for [12], applying formula (11), SchedEx performs on average 14% better in terms of schedule frame-size, with a standard deviation which is about 21% more narrow.

10. Conclusions

The simulations presented in this paper reveal that the introduced SchedEx enhancements and problem formulation extensions lead to a substantial performance improvement. Significant improvements in terms of performance and runtime can be achieved using multiple sinks and utilizing multiple channels for reliable packet delivery in WSN. Still, there is space for improvement, and a need for future work. Adaptive algorithms that for a given topology are able to recommend a setup that includes the amount of channels to be used and also the number of sinks and their positioning for a simplified deployment are required. Our simulations suggest that the utilization of four channels is a good heuristic value for IWSN, in order to reach a close-to-optimal scheduling performance and as fast a runtime as possible. In real scenarios, the distribution of sensors is usually not uniform, and positioning of sinks might be difficult due to application specific constraints. Where objective functions for network design can be formulated, heuristic algorithms can identify near-optimal solutions that fulfill the given constraints.

The identification of the routing table R could become part of the problem formulation in order to better address the network dynamics. Weighted shortest path routing may be far from being the most appropriate routing table for a topology given specific transmission patterns and interference landscapes.

Further, a WSN specific risk analysis for reliable packet delivery is required which for the given deployment calculates the risk of failure over a time period. Then, for real networks, flows are usually arbitrary and maximum acceptable latencies are on a sensor, if not packet, level. SchedEx in its extended version significantly improves on the applicability of reliability-aware scheduling for IWSN, where link qualities in the network can vary in time, and new schedules have to quickly be computed and deployed.