A Time-Efficient Convergecast Scheduling on Star-Linear IWSN for Narrow Process Industries

Abstract

The wireless technology is regarded as a paradigm shifter in the process industry. A star-linear industry wireless sensor network (IWSN) for narrow process industries is proposed in this paper. Based on the proposed IWSN, we focus on time-efficient convergecast solutions. We present algorithms to achieve optimal convergecast performance in terms of time slots use. In the proposed IWSN, the field devices (FDs) constitute a set of TDMA (time division multiple access) based star topology clusters, and the cluster heads present a multihop linear backbone. Time slots are scarce communication resource for convergecast in a narrow IWSN. Aiming to use slots efficiently, we design optimal algorithms to improve the polling scheduling in the cluster and the packets forwarding over the backbone. In a cluster, we design a multicycle scheduling algorithm and a fair polling algorithm to improve slots utility of the communication reliability and integrity. Over the backbone, an optimal slots allocating algorithm is designed to maximize the slots performance in terms of the end-to-end communication reliability, based on which a slot-efficient multisuperframe scheduling algorithm is presented. Performance analysis and simulations show that our solution outperforms traditional ones in terms of communication reliability and real-time.

1. Introduction

A growing trend in the process automation is to use wireless technology to reduce cable cost, deployment time, and unlocking of stranded information in previously deployed devices. Based on huge research efforts on IWSN, some professional products and business solutions have been presented for the process automation [1]. Wireless technologies have been regarded as a paradigm shifter in the process industry. Most commercial products tend to present general solutions. However, different scenarios may require different IWSN to match their process characteristics. We consider IWSN for narrow process automation systems in this paper. Some research works have been done for the IWSN with long and linear structure. Aiming at increasing network life time, a routing algorithm has been proposed to realize energy balance in the IWSN for structural health monitoring of long narrow tunnels in [2]. Energy-efficient wireless MAC Protocols for railway monitoring have been designed in [3]. Comparing with above systems, delay and packet loss are main metrics in IWSN for the process industry. Process automation systems have more stringent requirements on reliability, real-time performance. We focus on improving time utility in terms of communication reliability performance in IWSN for narrow process automation systems. In this paper, we present a star-linear IWSN based on the process characteristics. Based on the proposed IWSN, we design a time-efficient convergecast scheduling solution.

There exists a lot of research work done with IWSNs for industrial large-scale production. It is commonly assumed that the IWSN consists of thousands or tens of thousands FDs. This assumption may not be true in process industries. Production availability is of significant importance in the continuous process. Even though there are tens of thousands of FDs that need to communicate, they do not belong to the same network. The FDs are usually distributed over a set of process controllers, divided in several process sections, in order to avoid a complete production stop in case of a non-fail-silent situation in one FD [4]. Furthermore, to cover the process sections efficiently, FDs should be installed manually in groups other than random deploying assumed in most research works. In a narrow process automation system, a long assembly line consists of sensor groups. To capture the aspects of this kind of target process, we propose a star-linear IWSN as shown in Figure 1. The FDs are divided into clusters (field networks, FNs) following process sections [5, 6]. Each cluster is a star topology network. The cluster head (named master) polls the other FDs (named slaves) periodically. A set of masters present a linear-topology backbone network (BN) over which the polled packets are forwarded to the GW hop by hop. Two distinct time-windows, polling cycles and forwarding cycles, are provided in the proposed IWSN. To provide collision free and deterministic communications, TDMA strategy is adopted in both time-windows.

Figure 1

Architecture of the star-linear IWSN.

Over the years, some wireless technology standards for process automation have been put forward. The most remarkable example of this strategy is wireless HART (WH). Another well-known solution, ISA100.11, includes similar technical features to WH. These solutions are based on mesh network topologies, which may not be efficient for narrow process industries [7]. We have studied a two-tier IWSN for narrow process automation [7]. In this paper, different from employing monocycle polling strategy in [7], we consider the multicycle polling method in FN to save slots. Furthermore, we will present optimal slots allocation method over the BN to improve the slot utility in terms of end-to-end communication reliability. Aiming to use slots efficiently, we conduct the actual work in four aspects.

First is arranging slaves into polling cycles following their update rates. The update rates of slaves might be different. Much work is based on monocycle convergecast scheduling, in which all slaves are updated with the same update rate [8, 9]. In this way, some slaves may be updated more than once before their deadline and slots are wasted. For wired field bus systems, [10] presents an earliest deadline first multicycle (EDFM) polling algorithm to arrange minimal number of slaves in a polling cycle. EDFM is based on priority calculating with computational complexity $O(n\mathrm{\ast }\log n)$ , where n is the number of slaves to be polled in a polling cycle. Modifying EDFM to suit the special characteristics of our system, we design an algorithm with low computational complexity to arrange the minimal number of slaves into a polling cycles to save bandwidth.

Second is allocating slots fairly in a polling cycle. Generally, retransmission slots are available in a polling cycle. Slots are allocated to slaves averagely in most wired automation systems (e.g., PROFIBUS-DP and WorldFIP) [11]. Average allocating transmission trials may not be efficient. Time slots may be used luxuriously over high quality links, while low quality links suffer from data delivering failure for using up attempt trials. Slots should be allocated fairly. To exploit the multiuser diversity gain, we adopt proportional fair scheduling (PFS) to address this problem. In PFS, the ratio of the feasible rate to the average throughput for each user is calculated, which is defined as preference metric. For the next slot, the scheduler selects the user with the maximum preference metric to schedule [12]. IWSNs are very different from opportunistic system. Only when the allocated slots sequences are distributed to slaves can the communication schedule be generated. To meet the deterministic requirement of our IWSN, an algorithm is designed to allocate all slots fairly to slaves for the polling cycle.

Third is optimal slots allocating in the forwarding cycle. In the forwarding cycle, the communication reliability will refer to end-to-end reliability other than single-hop link reliability, and slots should be allocated carefully to avoid communication bottleneck. WH adopts an average retransmission schedule. In WH, the furthest end device allocates one slot for each en route network device to the GW, allocating a 2nd dedicated slot on the same path to handle a retry. Another retry is handled by allocating a 3rd slot on a separate path. To improve the end-to-end communication reliability, WH takes channel hopping technique to combat external interference [13]. Reference [14] presents a method to allocate slots optimally to improve communication performance of a multihop link for single channel scene. In this case, all trials may be exhausted and result in communication failure with cochannel interference being presented. Along exploring time and frequency diversity, we design an optimal joint channel-slot selecting method to improve slots gain in terms of end-to-end communication reliability.

Finally, fourth is designing an algorithm to schedule more transactions in each slot in the forwarding cycle. A set of polled packets are to be delivered to GW hop by hop. Communication transactions, including transmissions and retry ones, will be scheduled over BN in forwarding cycles. The general time-constrained scheduling problem is NP-complete even in linear networks. We try to schedule maximal number of transactions at each slot to improve system performance in terms of slots reuse. Some work has been done on designing efficient forwarding schemes in a linear network [15]. To the best of our knowledge, scheduling on forwarding with optimal retransmission has not been described so far in the context of industrial communications. In this paper, a subsection parallel delivering strategy is presented for optimal retransmission scheduling over a linear network.

The rest of this paper is organized as follows. In Section 2, system model and motivation are given. Section 3 presents a low computational complexity multicycle scheduling strategy. Section 4 presents fair slots allocating schemes in the FN. In Section 5, an optimal joint channel-slot selecting method is given over the BN. In Section 6, a subsection parallel delivering strategy is presented for forwarding scheduling. Section 7 gives the numerical results. Finally, we conclude the paper.

2. System Model and Motivation

2.1. Network Model and Available Channels

Consider a star-linear IWSN consisting of a BN and N FNs as shown in Figure 1. Without loss of generality, let $\{\text{F}{\text{N}}_i{\}}_{i=\mathrm{1}}^N$ denote the N FNs. Assume the $\text{F}{\text{N}}_i$ consists of a master and $N_i^f$ slaves. As in most IWSNs, the network topology is based on centralized master/slave architecture. Let $n_{\mathrm{0}}^{fi}$ denote the master in the $\text{F}{\text{N}}_i$ , and $\{n_j^{fi}{\}}_{j=\mathrm{1}}^{N_i^f}$ present the $N_i^f$ slaves with update rate in increasing order. A set of masters $\{n_{\mathrm{0}}^{fi}{\}}_{i=\mathrm{0}}^N$ and GW present the N-hop BN.

Generally, the FN is a heuristic network in the process automation system. Assume masters are powerful FDs (e.g., actors). Masters can deliver packets with adapt channel hopping technology. The other FDs, for example, sensors, can only communicate over a fixed channel. In general, just as in WH, the system can use up to 15 parallel channels, denoted as ${\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},\dots ,{\omega }_{\mathrm{15}}$ . We part the available channels into three groups, presented as ${\Omega }_{\mathrm{1}}=\{{\omega }_{\mathrm{3}j-\mathrm{2}}\}$ , ${\Omega }_{\mathrm{2}}=\{{\omega }_{\mathrm{3}j-\mathrm{1}}\}$ , and ${\Omega }_{\mathrm{3}}=\{{\omega }_{\mathrm{3}j}\}$ , where $j=\{\mathrm{1,2},\dots ,\mathrm{5}\}$ . Let $\gamma =\mathrm{mod}\hspace{0.17em}(i,\mathrm{3})$ ; the γth group is for communication link $(n_i^b,n_{i-\mathrm{1}}^b)$ . Successive three forwarding links employ different channel groups at the same slot. The master $n_{\mathrm{0}}^{fi}$ selects a channel from the γth group to polling slaves in the $\text{F}{\text{N}}_i$ .

2.2. Scheduling Cycles

In WH, the supported update rates should be defined ${\mathrm{2}}^i$ seconds, where i is positive or negative integer values, for example, update rate selections of 250 msec, 500 msec, 1 sec, 2 sec, 4 sec, 8 sec, 16 sec, and 32 sec (or more) [13]. We assume that the slaves in our system follow above update rates. Consider ${\beta }_i$ different update rates are presented in the $\text{F}{\text{N}}_i$ , and $\{T_j^{fi}{\}}_{j=\mathrm{1}}^{{\beta }_i}$ present the update rate sequence in increasing order. Obviously, $T_j^{fi}/T_{(j-\mathrm{1})}^{fi}\ge \mathrm{2}$ .

As shown in Figure 2, a convergecast cycle is divided into $T_{{\beta }_i}^{fi}/T_{\mathrm{1}}^{fi}$ primary convergecast cycles. The primary convergecast cycle coincides with the shortest period of slaves. A second convergecast cycle consists of two or more primary convergecast cycles. There are ${\beta }_i-\mathrm{1}$ second convergecast cycles. A primary convergecast cycle consists of a polling cycle, a forwarding cycle, and an idle cycle. In a primary convergecast cycle, masters run polling scheduling transactions as well as forwarding ones. In a polling cycle, the $n_{\mathrm{0}}^{fi}$ will carry out predefined polling scheduling in the $\text{F}{\text{N}}_i$ . Following that, the polled data will be forwarded to GW over the BN consisting of $\{n_{\mathrm{0}}^{fj}{\}}_{j=\mathrm{0}}^i$ in the forwarding cycle.

Figure 2

Operation cycle of the master.

2.3. Available Time Slots and Periodic Communication Transactions

As in most IWSNs, we assume that time is synchronized and slotted based on TDMA strategy. Each time slot allows the transmission of a single packet and the associated link level acknowledgement. We assume a number of retransmission trials are available for the slaves, and extra time slots will be allocated in the periodic window. Let $M_k^{fi}$ denote the number of slaves to be polled in the polling cycle of the kth primary convergecast cycle. Denote $A_k^{fi}=\{a_{kj}^{fi}{\}}_{j=\mathrm{1}}^{M_k^{fi}}$ as the polling slots allocating sequence for $M_k^{fi}$ slaves, where $a_{kj}^{fi}$ presents the number of slots for slave $n_j^{fi}$ . Denote $\{a_{kj}^{bi}{\}}_{j=\mathrm{1}}^i$ as corresponding forwarding slots allocating sequence, where $a_{kj}^{bi}$ presents the number of slots for master $n_{\mathrm{0}}^{fj}$ in the forwarding cycle of the kth primary convergecast.

In the polling cycle of kth primary convergecast cycle, for all slave $n_j^{fi}$ in the $\text{F}{\text{N}}_i$ , there are up to $a_{kj}^{fi}$ transactions (including retransmission trials) to be scheduled. Let $D_k^{fi}={\sum }_{j=\mathrm{1}}^{M_k^{fi}}{a}_{kj}^{fi}$ denote the total number of transactions for the $M_k^{fi}$ slaves, and $D_k^{bi}={\sum }_{j=\mathrm{1}}^i{a}_{kj}^{bi}$ presents the ones for forwarding the polled packets to GW. For all $\text{F}{\text{N}}_i$ , there are up to ${\sum }_{k=\mathrm{1}}^{T_{{\beta }_i}^{fi}/T_{\mathrm{1}}^{fi}}(D_k^{fi}+D_k^{bi})$ communication transactions to be scheduled in a convergecast cycle.

2.4. Motivation

A set of periodic communication transactions must be supported in the system, which are interrelated and compete for the shared communication resources. In IWSNs based on TDMA strategy, especially in a narrow process, time slots are scarce communication resource. To improve communication efficiency in terms of slots using, we try to address the following problem.

• (i)

Design a multicycle scheduling algorithm with lower computational complexity to minimize $M_k^{fi}$ constrained with deadlines of slaves.

(ii)

For given $D_k^{fi}$ slots in the kth polling cycle of $\text{F}{\text{N}}_i$ , find a fair slots allocating sequence $\{a_{kj}^{fi}{\}}_{j=\mathrm{1}}^{M_k^{fi}}$ .

(iii)

For given $D_k^{bi}$ slots in the kth forwarding cycle, find an optimal $\{a_{kj}^{bi}{\}}_{j=\mathrm{1}}^i$ to maximize end-to-end communication reliability.

(iv)

Find a parallel delivering strategy to maximize the number of transactions to be scheduled for forwarding in every slot.

3. Arranging Slaves into Polling Cycles

In this section, we design a multicycle scheduling scheme with low computational complexity to minimize $M_k^{fi}$ constrained with deadlines of slaves in the $\text{F}{\text{N}}_i$ . Let $\{M_k^{fi}{\}}_{k=\mathrm{1}}^{T_{{\beta }_i}^{fi}/T_{\mathrm{1}}^{fi}}$ present the number sequence of slaves to be polled in $T_{{\beta }_i}^{fi}/T_{\mathrm{1}}^{fi}$ primary convergecast cycles. $M_{\max }^{fi}$ presents the upbound of $M_k^{fi}$ . Let $g_j$ denote the number of slaves with update rate $T_j^{fi}$ in the $\text{F}{\text{N}}_i\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le j\le {\beta }_i)$ .

Theorem 1.

The lower bound of $M_{\max }^{fi}$ is $⌈{\sum }_{j=\mathrm{1}}^{{\beta }_i}(g_j/(T_j^{fi}/T_{\mathrm{1}}^{fi}))⌉$ .

Proof.

In the polling cycle of $\text{F}{\text{N}}_i$ , a slave with update rate $T_j^{fi}\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le j\le {\beta }_i)$ should be polled at least once every $T_j^{fi}/T_{\mathrm{1}}^{fi}$ polling cycles, and the minimal number of time slots for the master to update the slaves is $T_{{\beta }_j}^{fi}/T_j^{fi}$ in the polling cycle. The minimal number of total time slots by which the master updates all slaves should be ${\sum }_{j=\mathrm{1}}^{{\beta }_j}(T_j^{fi}/T_{\mathrm{1}}^{fi})g_j$ . The number of polling cycles in a convergecast cycle is $T_{{\beta }_j}^{fi}/T_{\mathrm{1}}^{fi}$ , and there are at least average ${\sum }_{j=\mathrm{1}}^{{\beta }_i}(T_{{\beta }_i}^{fi}/T_j^{fi})g_j$ slaves to be polled in a polling cycle. There is one or more primary cycles in which at least $⌈{\sum }_{j=\mathrm{1}}^{{\beta }_i}(g_j/(T_j^{fi}/T_{\mathrm{1}}^{fi}))⌉$ slaves should be polled.

Proof is finished.

Theorem 2.

If $M_{\max }^{fi}=⌈{\sum }_{j=\mathrm{1}}^{{\beta }_i}(g_j/(T_j^{fi}/T_{\mathrm{1}}^{fi}))⌉$ , all slaves in $F{N}_i$ can be scheduled in a convergecast cycle.

Proof.

Consider

$$\begin{array}{cc}& M_{\max }^{fi}=⌈{\displaystyle \sum }_{j=\mathrm{1}}^{{\beta }_i}‍\frac{g_j}{T_j^{fi}/T_{\mathrm{1}}^{fi}}⌉\ge {\displaystyle \sum }_{j=\mathrm{1}}^{{\beta }_i}‍\frac{T_{\mathrm{1}}^{fi}}{T_j^{fi}}{g}_j,\\ M_{\max }^{fi}\frac{T_{{\beta }_i}^{fi}}{T_{\mathrm{1}}^{fi}}\ge {\displaystyle \sum }_{j=\mathrm{1}}^{{\beta }_i}‍\frac{T_{{\beta }_i}^{fi}}{T_j^{fi}}{g}_j=\frac{T_{{\beta }_i}}{T_{{\beta }_i-\mathrm{1}}}{\displaystyle \sum }_{j=\mathrm{1}}^{{\beta }_i-\mathrm{1}}‍\frac{T_{{\beta }_i-\mathrm{1}}}{T_j}{g}_j+g_{{\beta }_i},\end{array}$$

(1)

and we have

$$\begin{array}{cc}& \frac{T_{{\beta }_i}}{T_{{\beta }_i-\mathrm{1}}}\left(\frac{T_{{\beta }_i-\mathrm{1}}}{T_{\mathrm{1}}}{M}_{\max }^{fi}-{\displaystyle \sum }_{j=\mathrm{1}}^{{\beta }_i-\mathrm{1}}‍\frac{T_{{\beta }_i-\mathrm{1}}}{T_j}{g}_j\right)\ge g_{{\beta }_i}.\end{array}$$

(2)

Consider $T_{j+\mathrm{1}}^{fi}/T_j^{fi}\ge \mathrm{2}$ ; formula (2) means the slaves in ${\beta }_i$ th group can be scheduled if the other ${\beta }_i-\mathrm{1}$ ones can be done. Similarly, we can conclude that ${\beta }_i$ th group can be scheduled if the 1th ones can be done. That is true.

Proof is finished.

Based on Theorems 1 and 2, we can arrange slaves into polling cycles as Algorithm 3, in which the maximum number of slaves to be polled in the polling cycles is minimized.

Algorithm 3.

Multicycle scheduling algorithm is as follows.

•  

Step 1: arrange $g_{\mathrm{1}}$ slaves in each polling cycle to be polled.

 

Step 2: get the slaves of group k with the smallest update rate $T_k^{fi}$ to be arranged.

 

Step 3: arrange $g_k$ slaves into $T_{{\beta }_i}^{fi}/T_k^{fi}$ second convergecast cycles.

 

Step 4: if $k<{\beta }_i$ , go to Step 2; else output allocated sequence.

4. Fair Slots Allocating in the Polling Cycle

Assuming $M_k^{fi}$ slaves are allocated in a polling cycle to be scheduled in the $\text{F}{\text{N}}_i$ , we get $M_k^{fi}$ links $L_i^f=\{l_j^{fi}{\}}_{j=\mathrm{1}}^{M_k^{fi}}$ over which the $n_{\mathrm{0}}^{fi}$ can poll slaves in the $\text{F}{\text{N}}_i$ . We assume that link $l_j^{fi}$ is unreliable with independent erasure events following a Bernoulli model with communication reliability probability $p_{kj}^{fi}$ . Multipolling architecture of $\text{F}{\text{N}}_i$ is shown in Figure 1.

Consider $a_{kj}^{fi}$ slots are available for the link $l_j^{fi}$ ; we can denote link $l_j^{fi}$ reliability as follows:

$$\begin{array}{cc}& R_{kj}^{fi}\left(a_{kj}^{fi}\right)=\mathrm{1}-{\displaystyle \prod }_{j=\mathrm{0}}^{a_{kj}^{fi}}‍\left(\mathrm{1}-p_{kj}^{fi}\right).\end{array}$$

(3)

The reliability over link $l_j^{fi}$ is an increasing function of $a_{kj}^{fi}$ , and more slots allocated for link $l_j^{fi}$ can improve the polling reliability over link $l_j^{fi}$ . Taking into account $D_k^{fi}$ slots are available, we must allocate all the slots in the $\text{F}{\text{N}}_i$ fairly to improve the system efficiency. We adapt proportional fair scheduling to address the problem. A scheduling policy $\mathfrak{R}$ is proportionally fair, if and only if the sum of the logarithmic average user throughput is maximized after the scheduling decision [9]:

$$\begin{array}{cc}& \mathfrak{R}=\arg \underset{S}{\max }{\displaystyle \sum }_{j=\mathrm{1}}^{M_k^{fi}}‍\log q_j^{\left(S\right)},\end{array}$$

(4)

where $q_j^{(S)}$ is the average throughput of all slaves under scheduling policy S. In the $\text{F}{\text{N}}_i$ , a polling command and the ACK form a transaction in a time slot, for all $A_k^{fi}=\{a_k^{fi}\mathrm{1},a_k^{fi}\mathrm{2},\dots ,a_{k{M}_k^{fi}}^{fi}\}$ as a slots allocating sequence, where ${\sum }_{j=\mathrm{1}}^{M_k^{fi}}{a}_{kj}^{fi}=D_k^{fi}$ , and the average throughput of $n_j^{fi}$ in $D_k^{fi}$ slots can be represented with $R_{kj}^{fi}$ . We have

$$\begin{array}{cc}& \mathfrak{R}=\arg \underset{A_k^{fi}}{\max }{\displaystyle \sum }_{j=\mathrm{1}}^{M_k^{fi}}‍\log R_{kj}^{fi}\left(a_{kj}^{fi}\right).\end{array}$$

(5)

The fair scheduling can be rewritten as follows:

$$\begin{array}{l}\max R_k^{fi}\left(A_k^{fi}\right)={\displaystyle \prod }_{j=\mathrm{0}}^{M_k^{fi}}‍R_{kj}^{fi}\left(a_{kj}^{fi}\right),\\ \text{Subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\displaystyle \sum }_{j=\mathrm{1}}^{M_{kj}^{fi}}‍a_{kj}^{fi}=D_k^{fi}.\end{array}$$

(6)

Obviously, we can present many slots allocation policies for polling the slaves in the $\text{F}{\text{N}}_i$ . We try to maximize the slots gain utility. We define the slots gain utility for $l_i^{fi}$ as follows.

Definition 4.

$K_{kj}^{fi}(a_{kj}^{fi})=R_{kj}^{fi}(a_{kj}^{fi}+\mathrm{1})/R_{kj}^{fi}(a_{kj}^{fi})$ define the slots gain function, which describe the increase rate when one retransmission slot is added to link $l_j^{fi}$ .

Lemma 5.

$K_{kj}^{fi}(a_{kj}^{fi})$ is a monotone decreasing function.

Proof.

Consider

$$\begin{array}{cc}& K_{kj}^{fi}\left(a_{kj}^{fi}\right)=\frac{R_{kj}^{fi}+\left(\mathrm{1}-R_{kj}^{fi}\right)p_{kj}^{fi}}{R_{kj}^{fi}}=\mathrm{1}-p_{kj}^{fi}+\frac{p_{kj}^{fi}}{R_{kj}^{fi}}.\end{array}$$

(7)

Similarly,

$$\begin{array}{cc}& K_{kj}^{fi}\left(a_{kj}^{fi}+\mathrm{1}\right)=\mathrm{1}-p_{kj}^{fi}+\frac{p_{kj}^{fi}}{R_{kj}^{fi}+\left(\mathrm{1}-R_{kj}^{fi}\right)p_{kj}^{fi}}.\end{array}$$

(8)

Obviously,

$$\begin{array}{cc}& \left(\mathrm{1}-R_{kj}^{fi}\right)p_{kj}^{fi}>\mathrm{0},\\ K_{kj}^{fi}\left(a_{kj}^{fi}+\mathrm{1}\right)<K_{kj}^{fi}\left(a_{kj}^{fi}\right).\end{array}$$

(9)

Proof is finished.

Theorem 6.

When the retranslation slots are allocated one by one for link $L_i^F=\{l_j^{fi}{\}}_{j=\mathrm{1}}^{M_k^{fi}}$ , the $R_{kj}^{fi}$ get the maximal increase in rate if the added slot is allocated to the link with maximal $K_{kj}^{fi}(a_{kj}^{fi})$ .

Proof.

Consider the polling scheduling in $\text{F}{\text{N}}_i$ with $D_k^{fi}$ slots. Obviously, $D_k^{fi}>M_k^{fi}$ . Let $m=D_k^{fi}-M_k^{fi}$ denote the retransmission slots. According to formula (3) and Definition 4, we have

$$\begin{array}{cc}& R_{kj}^{fi}\left(A_k^{fi}\right)={\displaystyle \prod }_{j=\mathrm{0}}^{M_k^{fi}}‍R_{kj}^{fi}\left(\mathrm{1}\right){\displaystyle \prod }_{j=\mathrm{0}}^{M_k^{fi}}‍R_{kj}^{fi}\left(\mathrm{1}\right)K_{kj}^{fi}\left(a_{kj}^{fi}\right).\end{array}$$

(10)

There are up to $m\mathrm{\ast }{M}_k^{fi}$ different $K_{kj}^{fi}(a_{kj}^{fi})$ following different slots allocating policy, which presents according $R_{kj}^{fi}(A_k^{fi})$ . For all dth slot to be allocated $(m+\mathrm{1}\le d\le D_k^{fi})$ , we can get $((D_k^{fi}-d)\mathrm{\ast }{M}_k^{fi})$ possible $K_{kj}^{fi}(k)\hspace{0.17em}\hspace{0.17em}(j(\mathrm{1,2},\dots ,M_k^{fi})),\hspace{0.17em}\hspace{0.17em}k\in (D_k^{fi}-d+\mathrm{1},\dots ,M_k^{fi})$ , assuming the added slot is allocated to the link $l_k^{fi}$ , where $k^{\mathrm{\ast }}=\arg \hspace{0.17em}\max K_j(d)$ , $(j\in (\mathrm{1,2},\dots ,M_i))$ . According to Lemma 5, $K_{i^{\mathrm{\prime \prime }}}^{fi}(d)>K_j^{ft}(k)\hspace{0.17em}\hspace{0.17em}(\forall j\ne i^{\mathrm{\ast }})$ . So we can allocate all the m retranslation slots one by one; each one is added to the link with maximal slots gain utility, and we get the m maximal result of $m\mathrm{\ast }M$ gain utility.

Proof is finished.

Following Theorem 6, we can get the fair slots allocating strategy for $\text{F}{\text{N}}_i$ .

Algorithm 7.

Fair slots allocating algorithm is as follows.

Step 1.

Let $\{a_{\mathrm{1}}^{fi},a_{\mathrm{2}}^{fi},\dots ,a_{M_k^{fi}}^{fi}\}=\{\mathrm{1,1},\dots ,\mathrm{1}\}$ , allocate each link a slot, and let $d=M_k^{fi}$ .

Step 2.

Get the $(d+\mathrm{1}$ )th retransmission slot to be allocated; calculate $K_j^f(d),\hspace{0.17em}\hspace{0.17em}(j\in (\mathrm{1,2},\dots ,M_k^{fi}))$ .

Step 3.

Let $i^{\mathrm{\ast }}=\arg \max K_j^f(d)$ , $(j\in (\mathrm{1,2},\dots ,M))$ , $a_{i^{\mathrm{\ast }}}^{fi}=a_{i^{\mathrm{\ast }}}^{fi}+\mathrm{1},d=d+\mathrm{1}$ .

Step 4.

If $d=D_k^{fi}$ , output $A_k^{fi}$ ; else go to Step 2.

5. Optimal Slots Allocating for the Forwarding Cycle

The N-hop BN consists of $\{n_{\mathrm{0}}^{fi}{\}}_{i=\mathrm{1}}^N$ and GW. Let ${\gamma }_i=\mathrm{mod}(i,\mathrm{3})$ . As mentioned in Section 3, the channel group ${\Omega }_{\gamma i}$ is available for communication link i-hops away from GW. There are up to $\left|{\Omega }_{\gamma i}\right|$ sublinks between $n_i^b$ and $n_{i-\mathrm{1}}^b$ for forwarding and up to ${\prod }_{j=\mathrm{1}}^i\left|{\Omega }_{{\gamma }_j}\right|$ potential path for convergecast from $n_i^b$ to GW. Let $l_i^b=\{l_j^{bi}{\}}_{j=\mathrm{1}}^{\left|{\Omega }_{{\gamma }_i}\right|}$ denote all the sublinks between $n_i^b$ and $n_{i-\mathrm{1}}^b$ , and $p_i^b=\{p_j^{bi}{\}}_{j=\mathrm{1}}^{\left|{\Omega }_{{\gamma }_i}\right|}$ denote the corresponding primary communication reliability probability. A multihop multichannel BN is shown in Figure 1.

For all $n_i^b,\hspace{0.17em}\hspace{0.17em}(i\ne N)$ , given $D_k^{bi}$ slots for forwarding to GW, obviously, we can present up to $({\prod }_{j=\mathrm{1}}^i\left|{\Omega }_{\gamma j}\right|)$ slots allocation strategies for forwarding from $n_i^b$ to GW. In the BN, we are interested in maximizing the probability that the packet is delivered from source to destination with given slots $D_i^b$ . We explore time and frequency diversity to attach optimal forwarding scheduling strategy in this section.

Let $c_i^b=\{c_j^{bi}{\}}_{j=\mathrm{1}}^{\left|{\Omega }_{\gamma i}\right|}$ , where $c_j^{bi}$ is defined as a 0-1 binary variable as follows:

$$\begin{array}{cc}& c_j^{bi}=\left\{\begin{array}{cc}\mathrm{0}\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{l}_j^{bi}\hspace{0.17em}\text{attatch}\hspace{0.17em}\text{a}\hspace{0.17em}\text{slot}\hfill \\ \mathrm{1}\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{l}_j^{bi}\hspace{0.17em}\text{is}\hspace{0.17em}\text{not}\hspace{0.17em}\text{selected}.\hfill \end{array}\right.\end{array}$$

(11)

The reliability over link $l_i^b$ can be written as follows:

$$\begin{array}{cc}& R_j^{bi}\left(a_j^{bi},c_j^{bi}\right)=\mathrm{1}-{\displaystyle \prod }_{\mathcal{l}=\mathrm{1}}^{\left|{\Omega }_{{\gamma }_j}\right|}‍\left(\mathrm{1}-c_{\mathcal{l}}^{bj}{p}_{\mathcal{l}}^{bj}\right).\mathrm{\hspace{0.17em}\hspace{0.17em}}\end{array}$$

(12)

Let $A_i^b=\{a_j^{bi}{\}}_{j=\mathrm{1}}^i$ present a slots allocating sequence, and $C_i^b=\{c_j^b{\}}_{j=\mathrm{1}}^i$ presents a sublinks selection. We get the optimization problem as follows:

$$\begin{array}{l}\max \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}{R}_i^b\left(A_i^b,C_i^b\right)={\displaystyle \prod }_{j=\mathrm{1}}^i‍R_j^{bi}\left(a_j^{bi},c_j^{bi}\right)\\ \text{Subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\displaystyle \sum }_{j=\mathrm{1}}^i‍\hspace{0.17em}{\displaystyle \sum }_{\mathcal{l}=\mathrm{1}}^{\left|{\Omega }_{\gamma j}\right|}‍c_{\mathcal{l}}^{bi}\le D_i^b.\end{array}$$

(13)

The optimization problem (6) is a nonlinear 0-1 integer programming problem. We introduce an ordering $\{k_{\mathrm{1}},k_{\mathrm{2}},\dots ,k_{\left|{\Omega }_{\gamma }i\right|}\}$ of the sublink in terms of decreasing reliability. Obviously, the first $a_j^{bi}={\sum }_{k=\mathrm{1}}^{\left|{\Omega }_{\gamma j}\right|}{c}_k^{bi}$ sublink should be selected during slots allocating; then we have

$$\begin{array}{cc}& R_j^{bi}\left(a_j^{bi}\right)=\mathrm{1}-{\displaystyle \prod }_{\mathcal{l}=\mathrm{1}}^{a_j^{bi}}‍\left(\mathrm{1}-p_{\mathcal{l}}^{bj}\right).\end{array}$$

(14)

Definition 8.

Define the slots utility function $K_j^{bi}(a_j^{bi})=R_j^{bi}(a_{kj}^{fi}+\mathrm{1})/R_j^{bi}(a_j^{bi})$ , which is the increase in rate when one retransmission slot is added to link $L_j^{bi}$ .

Lemma 9.

$K_j^{bi}(a_j^{bi})$ is a monotone decreasing function.

Proof.

For all $l\in \{\mathrm{1,2},\dots ,a_j^{bi}-\mathrm{1}\}$

$$\begin{array}{l}{K}_j^{bi}\left(l\right)=\frac{R_j^{bi}+\left(\mathrm{1}-R_j^{bi}\right)p_{k_{l+\mathrm{1}}}^{bj}}{R_j^{bi}}\\ =\mathrm{1}-p_{k_{l+\mathrm{1}}}^{bj}+\frac{p_{k_{l+\mathrm{1}}}^{bj}}{R_j^{bi}}.\end{array}$$

(15)

Similarly,

$$\begin{array}{c}{K}_j^{bi}\left(l+\mathrm{1}\right)=\mathrm{1}-p_{k_{l+\mathrm{2}}}^{bj}+\frac{p_{k_{l+\mathrm{2}}}^{bj}}{R_j^{bi}+\left(\mathrm{1}-R_j^{bi}\right)p_{k_{l+\mathrm{1}}}},\end{array}$$

(16)

and we have

$$\begin{array}{l}{K}_j^{bi}\left(l\right)-K_j^{bi}\left(l-\mathrm{1}\right)\\ \hspace{1em}=\frac{p_{k_{l+\mathrm{1}}}^{bj}}{R_j^{bi}}+\frac{p_{k_{l+\mathrm{1}}}^{bj}}{R_j^{bi}+\left(\mathrm{1}-R_j^{bi}\right)p_{k_{l+\mathrm{1}}}^{bi}}+p_{k_{l+\mathrm{2}}}^{bj}-p_{k_{l+\mathrm{1}}}^{bj}\\ \hspace{1em}\ge \frac{p_{k_{l+\mathrm{2}}}^{bj}}{R_j^{bi}}-\frac{p_{k_{l+\mathrm{2}}}^{bj}}{R_j^{bi}}+\left(\mathrm{1}-R_j^{bi}\right)p_{k_{l+\mathrm{1}}}^{bj}\hspace{1em}{K}_j^{bi}\left(l\right)>K_j^{bi}\left(l+\mathrm{1}\right).\end{array}$$

(17)

Similar to Theorem 6, we can get Theorem 10 as follows.

Theorem 10.

When the retransmission slots are allocated one by one for $L_i^b=\{L_j^{bi}{\}}_{j=\mathrm{1}}^i$ , the $R_i^b(A_i^b,C_i^b)$ get the maximal increase rate if the added one is allocated to the link with maximal $k_j^{bi}(a_j^{bi})$ .

Now, the optimization problem (6) is converted into a conventional resource allocation problem. Similarly, the problem can be solved by employing Algorithm 7 described in Section 4. Different from Algorithm 7, channels will be switched following slots allocating.

6. A Subsection Parallel Delivering Strategy over the BN

Let us consider the forwarding of packets over the BN. An optimal slots allocation sequence has been presented in Section 4. In common hop-by-hop IWSN, bandwidth is especially challenging for delivering packets over long narrow path. In the proposed system, we attempt to schedule more transactions synchronously in each slot to improve throughput over the BN.

Theorem 11.

For all $n_i^b$ , there are ${\sum }_{j=i}^N{a}_j^{bi}$ transactions to be scheduled, and the low bound slots to forward the corresponding packets are ${\sum }_{j=i+\mathrm{1}}^N{a}_j^{b(i+\mathrm{1})}+{\sum }_{j=i}^N{a}_j^{bi}$ .

Proof.

For all $n_j^b,\hspace{0.17em}\hspace{0.17em}(j\ge i),\hspace{0.17em}\hspace{0.17em}{a}_j^{bi}$ attempt slots for ${\tau }_j^b$ are allocated in $n_i^b$ , and there are ${\sum }_{j=i}^N{a}_j^{bi}$ transactions to be scheduled in $n_i^b$ .

Similar, there are ${\sum }_{j=i+\mathrm{1}}^N{a}_j^{b(i+\mathrm{1})}$ transactions to be scheduled in $n_{i+\mathrm{1}}^b$ , which need the corresponding slots for receiving in $n_i^b$ .

Links $L_i^b$ and $L_{i+\mathrm{1}}^b$ cannot be scheduled simultaneously since each node has only one half-duplex radio transceiver. Therefore, the low bound slots to forward the corresponding packets are ${\sum }_{j=i+\mathrm{1}}^N{a}_j^{b(i+\mathrm{1})}+{\sum }_{j=i}^N{a}_j^{bi}$ .

Proof is finished.

In most exiting works [15, 16], the two-slice scheduling scheme based on temporal separation between the adjacent nodes is adopted for a linear network. A cycle is split into two time slices, named odd slots and even slots. All odd slots construct the odd slice and even ones construct another slice. Nodes located at odd hops away from GW send data in one time slice (e.g., odd time slice) and receive data in another time slice (e.g., even ones). The even nodes run at opposite case. If transactions are always available in all nodes, there are average $N/\mathrm{2}$ transactions to be scheduled synchronously over the N-hop BN, which is an ideal case to maximize the throughput. From Theorem 11, we find that the number of slots for a node to transmit and receive packets may be different when $a_{i+\mathrm{1}}^{bj}\ne a_i^{bj}$ , which may result in the absence of transactions and throw the above strategy into lower efficiency. We try to improve the two-slice scheduling scheme for forwarding operation over the multihop BN. Before that, two definitions and a corollary are presented.

Definition 12.

At any slot in schedule S, $n_{\mathrm{0}}^{bi}\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i\le N)$ is called an empty node if all packets in its buffers of $n_{\mathrm{0}}^{bi}$ are delivered.

Definition 13.

At any slot in schedule S, $n_{\mathrm{0}}^{bi}\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i\le N)$ is called a left bounding node if $n_{\mathrm{0}}^{bi}$ is an empty node and $n_{\mathrm{0}}^{b(i+\mathrm{1})}$ is not an empty one. Similarly, $n_{\mathrm{0}}^{bi}\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i\le N)$ is called a right bounding node if $n_{\mathrm{0}}^{bi}$ is not an empty node and $n_{\mathrm{0}}^{b(i+\mathrm{1})}$ is an empty one.

The GW is always an empty node, and $n_{\mathrm{0}}^{bN}$ is always a right bounding node before it finishes $a_N^{bi}$ communication transactions.

Corollary 14.

For all $n_{\mathrm{0}}^{bi}\hspace{0.17em}\hspace{0.17em}(\mathrm{1}\le i\le N)$ , when ${\sum }_{j=i}^N{a}_j^{bi}$ transactions are scheduled, all packets in $n_{\mathrm{0}}^{bj}\hspace{0.17em}\hspace{0.17em}(i\le j\le N)$ are delivered. Specifically, the forwarding schedule over the BN is finished when ${\sum }_{j=\mathrm{1}}^N{a}_j^{bi}$ transactions are scheduled in $n_{\mathrm{1}}^{bj}$ .

Based on Theorem 11 and Corollary 14, we design a subsection parallel delivering strategy over the BN. The basic idea of the algorithm is to divide the BN into subbackbone (SBN) with all bounding nodes. A SBN consists of a left bounding node, the nearest right bounding node lying apart from GW, and all nodes between the two bounding nodes. At any slot in the forwarding cycle, nodes located at odd hops away from the left bounding node are scheduled in every SBN until new bounding node(s) appear or current ones disappear.

Algorithm 15.

Subsection parallel packets delivering algorithm is as follows.

Step 1.

Search $n_{\mathrm{0}}^{bj}$ in which all packets are delivered according to Corollary  14.

Step 2.

Search bounding nodes from GW to $n_{\mathrm{0}}^{bj}$ . Construct SBNs based on each bounding nodes pair sequence.

Step 3.

Schedule nodes locating odd hops away from the left bounding node in all SBNs.

Step 4.

If no new bounding node(s) appear or current ones disappear, go to Step 3.

Step 5.

If the convergecast schedule over the BN is finished, scheduling sequence is generated; else go to Step 1.

7. Performance Evaluation

In this section, we evaluate the performance of the star-linear IWSN system through numerical simulations. Firstly, we demonstrate the reliability and integrity of the FN and discuss their performance benefits in real-time. Secondly, we evaluate the end-to-end reliability of a multihop BN constrained with given number of retransmission transactions. Thirdly, the performance of the subsection parallel delivering method is compared with the two-slice ones. We also discuss the way to extend our scheme to the more complex topologies.

7.1. Performance Evaluation on the $\text{F}{\text{N}}_{\mathit{i}}$

We simulate the $\text{F}{\text{N}}_i$ consisting of nine slaves and one master in single channel mode. We consider average three slots are available for each slave. Slaves failed successively for three slots will be removed from the polling sequence and communication loss probability is less than $\mathrm{2}/\mathrm{3}$ . Let communication loss probability be uniformly distributed in (1%~67%). We compare the polling schedule employing optimal slots allocating method to the ones using average allocating slots strategy. We also simulate the case in which interference takes place in some links randomly. We calculate the the communication reliability and integrity for four cases: average allocating slots, optimal allocating slots, average allocating slots with interference being absent, and optimal allocating slots with interference being absent. The number of time slots consumed is the same $\mathrm{27}$ . Figure 3 shows the communication reliability curves. The FN is scheduled to be more reliable and integrated when the optimal slots allocating is employed.

Figure 3

Comparison of average, optimal, average with interference, and optimal with interference utility in terms of reliability and integrity.

Polling fair improves slots gain utility, which will bring performance benefits in reliability and real-time. Figure 4 shows the mean reliability curves of each link for 1000 primary convergecast cycles. It is found that the proposed approach attaches more reliability.

Figure 4

Comparison of average, optimal, average with interference, and optimal with interference utility in terms of link reliability.

Improvement of slots gain utility can act as another aspect. When real-time is more important than reliability in the system, less slots can be expended to catch the same reliability. Figure 5 shows the case where slots are saved by employing optimal slots allocation.

Figure 5

Slots saved curves according to variational resource available.

Obviously, more resources available will result in more slots to be saved. Let communication loss probabilities of masters follow a uniform distribution (1%~67%); the numbers of FNs are set from 2 to 19. We calculate the polling reliability employing optimal slots allocation and compare the result to the conventional average allocation case. The number of time slots consumed is the same $3(N-1)$ . Simulation in Figure 5 shows that up to 1/3 slots are saved.

7.2. Performance Evaluation on $\text{BN}$

Consider a linear-topology BN consisting of 19 masters. Let primary communication loss probabilities of available channels between adjacent masters uniformly distribute in (1%~67%). We evaluate the forwarding performance in terms of the end-to-end communication reliability through numerical simulations. The number of available time slots for the i-hop link between $n_{\mathrm{0}}^{bi}$ and GW is $\mathrm{3}i$ . We calculate the end-to-end reliability of each i-hop link for four cases: average allocating slots, optimal allocating slots, average allocating slots with interference being absent, and optimal allocating slots with interference being absent. Figure 6 shows the reliability curves for the four cases. The simulations show that the optimal solution outperforms traditional average ones in terms of end-to-end communication reliability. The end-to-end reliability of optimal scheduling is not sensitive on interference for employing adapted hopping scheme.

Figure 6

The end-to-end reliability comparison of average, optimal, average with interference, and optimal with interference utility.

We simulate the forwarding scheduling based on optimal scheduling without interference being present for 1000 forwarding cycles to evaluate the subsection parallel delivering strategy. Figure 7 shows the slots consumed curve for our solution and the two-slice ones. For the 19th link, up to 30 slots are saved when our solution is adopted.

Figure 7

Comparison of slots consumed for subsection parallel packets delivering scheme and two-slice ones.

7.3. Extension to More Complex Topologies

Define the depth of a FD as the number of logical hops from the FD to GW. The GW is at depth zero. All slaves in $\text{F}{\text{N}}_i$ are at depth $i+\mathrm{1}$ in the IWSN proposed in Figure 2, which acts as a limited network coverage and rigid network topologies. Several cases as follows can be presented after extending our system. There are up to five upper star networks can be scheduled synchronously.

• (i)

All FDs in $\text{F}{\text{N}}_i$ form topologies similar to the ones in Figure 8. In this case, the polling cycle will be divided into two subcycles: subpolling cycle and subforwarding cycle. We can apply fair scheduling strategy and reliability forwarding ones in the two subcycle directly.

(ii)

Some slaves are connected to multiple nodes at upper depth, called child nodes. The child nodes are at depth $i+\mathrm{2}$ . The FN acts as two-tier star topologies as shown in Figure 9, which presents one lower star network and one or more upper ones. In this case, polling cycle will be divided into two subpolling cycle, one for lower network and another for upper ones. The fair scheduling strategy can be applied directly.

(iii)

Slaves in the $\text{F}{\text{N}}_i$ act as multitree topologies similar to the ones in Figure 10. As in case 1, the polling cycle will be divided into two subcycles. In the forwarding cycle, all subtrees are scheduled following the depth first principle.

Figure 8

Extension to more complex topologies: FNs act as star-linear topologies.

Figure 9

Extension to more complex topologies: FNs act as two-level star topologies.

Figure 10

Extension to more complex topologies: FNs act as multitree topologies.

8. Conclusions

We have studied the IWNs for the process automation in this paper. To meet the requirement in narrow process industries, we present a star-linear IWSNs based on FNs and BN. Considering that slots are scarce communication resource in this kind of IWSN, we focus on using slots efficiently to carry out convergecast over the proposed IWSN. We designed a multicycle scheduling scheme with low computational complexity to allocate slaves into primary cycles and presented a fair slots allocating method for the FN. Over the BN, we designed an optimal slot-channel selecting scheme to improve the system performance in terms of the end-to-end communication reliability. Based on the optimal slot-channel selecting scheme, the subsection parallel delivering strategy was designed to save slots for forwarding scheduling over the BN. Further discussions on extending our solution to more complex topologies are presented.