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

Authors: Hong-hua Xu; Xinping Guan
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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∗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 Section2, 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 andN FNs as shown in Figure 1. Without loss of generality, let {FNi}i=1N denote theN FNs. Assume the FNi consists of a master and Nif slaves. As in most IWSNs, the network topology is based on centralized master/slave architecture. Let n0fi denote the master in the FNi, and {njfi}j=1Nif present the Nif slaves with update rate in increasing order. A set of masters {n0fi}i=0N 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ω1,ω2,…,ω15. We part the available channels into three groups, presented as Ω1={ω3j-2}, Ω2={ω3j-1}, and Ω3={ω3j}, where j={1,2,…,5}. Let γ=mod⁡(i,3); the γth group is for communication link (nib,ni-1b). Successive three forwarding links employ different channel groups at the same slot. The master n0fi selects a channel from the γth group to polling slaves in the FNi.


### 2.2.  Scheduling Cycles

In WH, the supported update rates should be defined2i 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 βi different update rates are presented in the FNi, and {Tjfi}j=1βi present the update rate sequence in increasing order. Obviously, Tjfi/T(j-1)fi≥2.As shown in Figure2, a convergecast cycle is divided into Tβifi/T1fi 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 βi-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 n0fi will carry out predefined polling scheduling in the FNi. Following that, the polled data will be forwarded to GW over the BN consisting of {n0fj}j=0i 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. LetMkfi denote the number of slaves to be polled in the polling cycle of the kth primary convergecast cycle. Denote Akfi={akjfi}j=1Mkfi as the polling slots allocating sequence for Mkfi slaves, where akjfi presents the number of slots for slave njfi. Denote {akjbi}j=1i as corresponding forwarding slots allocating sequence, where akjbi presents the number of slots for master n0fj in the forwarding cycle of the kth primary convergecast.In the polling cycle ofkth primary convergecast cycle, for all slave njfi in the FNi, there are up to akjfi transactions (including retransmission trials) to be scheduled. Let Dkfi=∑j=1Mkfiakjfi denote the total number of transactions for the Mkfi slaves, and Dkbi=∑j=1iakjbi presents the ones for forwarding the polled packets to GW. For all FNi, there are up to ∑k=1Tβifi/T1fi(Dkfi+Dkbi) 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 minimizeMkfi constrained with deadlines of slaves.(ii)
For givenDkfi slots in the kth polling cycle of FNi, find a fair slots allocating sequence {akjfi}j=1Mkfi.(iii)
For givenDkbi slots in the kth forwarding cycle, find an optimal {akjbi}j=1i 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.


## 2.1.  Network Model and Available Channels

Consider a star-linear IWSN consisting of a BN andN FNs as shown in Figure 1. Without loss of generality, let {FNi}i=1N denote theN FNs. Assume the FNi consists of a master and Nif slaves. As in most IWSNs, the network topology is based on centralized master/slave architecture. Let n0fi denote the master in the FNi, and {njfi}j=1Nif present the Nif slaves with update rate in increasing order. A set of masters {n0fi}i=0N 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ω1,ω2,…,ω15. We part the available channels into three groups, presented as Ω1={ω3j-2}, Ω2={ω3j-1}, and Ω3={ω3j}, where j={1,2,…,5}. Let γ=mod⁡(i,3); the γth group is for communication link (nib,ni-1b). Successive three forwarding links employ different channel groups at the same slot. The master n0fi selects a channel from the γth group to polling slaves in the FNi.


## 2.2.  Scheduling Cycles

In WH, the supported update rates should be defined2i 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 βi different update rates are presented in the FNi, and {Tjfi}j=1βi present the update rate sequence in increasing order. Obviously, Tjfi/T(j-1)fi≥2.As shown in Figure2, a convergecast cycle is divided into Tβifi/T1fi 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 βi-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 n0fi will carry out predefined polling scheduling in the FNi. Following that, the polled data will be forwarded to GW over the BN consisting of {n0fj}j=0i 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. LetMkfi denote the number of slaves to be polled in the polling cycle of the kth primary convergecast cycle. Denote Akfi={akjfi}j=1Mkfi as the polling slots allocating sequence for Mkfi slaves, where akjfi presents the number of slots for slave njfi. Denote {akjbi}j=1i as corresponding forwarding slots allocating sequence, where akjbi presents the number of slots for master n0fj in the forwarding cycle of the kth primary convergecast.In the polling cycle ofkth primary convergecast cycle, for all slave njfi in the FNi, there are up to akjfi transactions (including retransmission trials) to be scheduled. Let Dkfi=∑j=1Mkfiakjfi denote the total number of transactions for the Mkfi slaves, and Dkbi=∑j=1iakjbi presents the ones for forwarding the polled packets to GW. For all FNi, there are up to ∑k=1Tβifi/T1fi(Dkfi+Dkbi) 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 minimizeMkfi constrained with deadlines of slaves.(ii)
For givenDkfi slots in the kth polling cycle of FNi, find a fair slots allocating sequence {akjfi}j=1Mkfi.(iii)
For givenDkbi slots in the kth forwarding cycle, find an optimal {akjbi}j=1i 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 minimizeMkfi constrained with deadlines of slaves in the FNi. Let {Mkfi}k=1Tβifi/T1fi present the number sequence of slaves to be polled in Tβifi/T1fi primary convergecast cycles. Mmax⁡fi presents the upbound of Mkfi. Let gj denote the number of slaves with update rate Tjfi in the FNi(1≤j≤βi).Theorem 1.
The lower bound ofMmax⁡fi is ∑j=1βi(gj/(Tjfi/T1fi)).Proof.
In the polling cycle ofFNi, a slave with update rate Tjfi(1≤j≤βi) should be polled at least once every Tjfi/T1fi polling cycles, and the minimal number of time slots for the master to update the slaves is Tβjfi/Tjfi in the polling cycle. The minimal number of total time slots by which the master updates all slaves should be ∑j=1βj(Tjfi/T1fi)gj. The number of polling cycles in a convergecast cycle is Tβjfi/T1fi, and there are at least average ∑j=1βi(Tβifi/Tjfi)gj slaves to be polled in a polling cycle. There is one or more primary cycles in which at least ∑j=1βi(gj/(Tjfi/T1fi)) slaves should be polled.
Proof is finished.Theorem 2.
IfMmax⁡fi=∑j=1βi(gj/(Tjfi/T1fi)), all slaves in FNi can be scheduled in a convergecast cycle.Proof.
Consider(1)Mmax⁡fi=∑j=1βi‍gjTjfi/T1fi≥∑j=1βi‍T1fiTjfigj,Mmax⁡fiTβifiT1fi≥∑j=1βi‍TβifiTjfigj=TβiTβi-1∑j=1βi-1‍Tβi-1Tjgj+gβi,and we have(2)TβiTβi-1Tβi-1T1Mmax⁡fi-∑j=1βi-1‍Tβi-1Tjgj≥gβi.
ConsiderTj+1fi/Tjfi≥2; formula (2) means the slaves in βith group can be scheduled if the other βi-1 ones can be done. Similarly, we can conclude that βith group can be scheduled if the 1th ones can be done. That is true.
Proof is finished.Based on Theorems1 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: arrangeg1 slaves in each polling cycle to be polled.Step 2: get the slaves of groupk with the smallest update rate Tkfi to be arranged.Step 3: arrangegk slaves into Tβifi/Tkfi second convergecast cycles.Step 4: ifk<βi, go to Step 2; else output allocated sequence.


## 4. Fair Slots Allocating in the Polling Cycle

AssumingMkfi slaves are allocated in a polling cycle to be scheduled in the FNi, we get Mkfi links Lif={ljfi}j=1Mkfi over which the n0fi can poll slaves in the FNi. We assume that link ljfi is unreliable with independent erasure events following a Bernoulli model with communication reliability probability pkjfi. Multipolling architecture of FNi is shown in Figure 1.Considerakjfi slots are available for the link ljfi; we can denote link ljfi reliability as follows:(3)Rkjfiakjfi=1-∏j=0akjfi‍1-pkjfi.The reliability over linkljfi is an increasing function of akjfi, and more slots allocated for link ljfi can improve the polling reliability over link ljfi. Taking into account Dkfi slots are available, we must allocate all the slots in the FNi fairly to improve the system efficiency. We adapt proportional fair scheduling to address the problem. A scheduling policy R is proportionally fair, if and only if the sum of the logarithmic average user throughput is maximized after the scheduling decision [9]:(4)R=argmax⁡S∑j=1Mkfi‍log⁡qjS,where qj(S) is the average throughput of all slaves under scheduling policy S. In the FNi, a polling command and the ACK form a transaction in a time slot, for all Akfi={akfi1,akfi2,…,akMkfifi} as a slots allocating sequence, where ∑j=1Mkfiakjfi=Dkfi, and the average throughput of njfi in Dkfi slots can be represented with Rkjfi. We have(5)R=argmax⁡Akfi∑j=1Mkfi‍log⁡Rkjfiakjfi.The fair scheduling can be rewritten as follows:(6)max⁡⁡RkfiAkfi=∏j=0Mkfi‍Rkjfiakjfi,Subjectto∑j=1Mkjfi‍akjfi=Dkfi.Obviously, we can present many slots allocation policies for polling the slaves in theFNi. We try to maximize the slots gain utility. We define the slots gain utility for lifi as follows.Definition 4.
K
k
j
f
i
(
a
k
j
f
i
)
=
R
k
j
f
i
(
a
k
j
f
i
+
1
)
/
R
k
j
f
i
(
a
k
j
f
i
) define the slots gain function, which describe the increase rate when one retransmission slot is added to link ljfi.Lemma 5.
K
k
j
f
i
(
a
k
j
f
i
) is a monotone decreasing function.Proof.
Consider(7)Kkjfiakjfi=Rkjfi+1-RkjfipkjfiRkjfi=1-pkjfi+pkjfiRkjfi.
Similarly,(8)Kkjfiakjfi+1=1-pkjfi+pkjfiRkjfi+1-Rkjfipkjfi.
Obviously,(9)1-Rkjfipkjfi>0,Kkjfiakjfi+1<Kkjfiakjfi.
Proof is finished.Theorem 6.
When the retranslation slots are allocated one by one for linkLiF={ljfi}j=1Mkfi, the Rkjfi get the maximal increase in rate if the added slot is allocated to the link with maximal Kkjfi(akjfi).Proof.
Consider the polling scheduling inFNi with Dkfi slots. Obviously, Dkfi>Mkfi. Let m=Dkfi-Mkfi denote the retransmission slots. According to formula (3) and Definition 4, we have(10)RkjfiAkfi=∏j=0Mkfi‍Rkjfi1∏j=0Mkfi‍Rkjfi1Kkjfiakjfi.
There are up tom∗Mkfi different Kkjfi(akjfi) following different slots allocating policy, which presents according Rkjfi(Akfi). For all dth slot to be allocated (m+1≤d≤Dkfi), we can get ((Dkfi-d)∗Mkfi) possible Kkjfi(k)(j(1,2,…,Mkfi)),k∈(Dkfi-d+1,…,Mkfi), assuming the added slot is allocated to the link lkfi, where k∗=argmax⁡Kj(d), (j∈(1,2,…,Mi)). According to Lemma 5, Ki′′fi(d)>Kjft(k)(∀j≠i∗). 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∗M gain utility.
Proof is finished.Following Theorem6, we can get the fair slots allocating strategy for FNi.Algorithm 7.
Fair slots allocating algorithm is as follows.Step 1.
Let{a1fi,a2fi,…,aMkfifi}={1,1,…,1}, allocate each link a slot, and let d=Mkfi.Step 2.
Get the(d+1)th retransmission slot to be allocated; calculate Kjf(d),(j∈(1,2,…,Mkfi)).Step 3.
Leti∗=arg⁡max⁡Kjf(d), (j∈(1,2,…,M)), ai∗fi=ai∗fi+1,d=d+1.Step 4.
Ifd=Dkfi, output Akfi; else go to Step 2.


## 5. Optimal Slots Allocating for the Forwarding Cycle

TheN-hop BN consists of {n0fi}i=1N and GW. Let γi=mod⁡(i,3). As mentioned in Section 3, the channel group Ωγi is available for communication link i-hops away from GW. There are up to |Ωγi| sublinks between nib and ni-1b for forwarding and up to ∏j=1i|Ωγj| potential path for convergecast from nib to GW. Let lib={ljbi}j=1|Ωγi| denote all the sublinks between nib and ni-1b, and pib={pjbi}j=1|Ωγi| denote the corresponding primary communication reliability probability. A multihop multichannel BN is shown in Figure 1.For allnib,(i≠N), given Dkbi slots for forwarding to GW, obviously, we can present up to (∏j=1i|Ωγj|) slots allocation strategies for forwarding from nib to GW. In the BN, we are interested in maximizing the probability that the packet is delivered from source to destination with given slots Dib. We explore time and frequency diversity to attach optimal forwarding scheduling strategy in this section.Letcib={cjbi}j=1|Ωγi|, where cjbi is defined as a 0-1 binary variable as follows:(11)cjbi=0ifljbiattatchaslot1ifljbiisnotselected.The reliability over linklib can be written as follows:(12)Rjbiajbi,cjbi=1-∏l=1Ωγj‍1-clbjplbj.LetAib={ajbi}j=1i present a slots allocating sequence, and Cib={cjb}j=1i presents a sublinks selection. We get the optimization problem as follows:(13)max⁡RibAib,Cib=∏j=1i‍Rjbiajbi,cjbiSubjectto∑j=1i‍∑l=1Ωγj‍clbi≤Dib.The optimization problem (6) is a nonlinear 0-1 integer programming problem. We introduce an ordering {k1,k2,…,k|Ωγi|} of the sublink in terms of decreasing reliability. Obviously, the first ajbi=∑k=1|Ωγj|ckbi sublink should be selected during slots allocating; then we have(14)Rjbiajbi=1-∏l=1ajbi‍1-plbj.Definition 8.
Define the slots utility functionKjbi(ajbi)=Rjbi(akjfi+1)/Rjbi(ajbi), which is the increase in rate when one retransmission slot is added to link Ljbi.Lemma 9.
K
j
b
i
(
a
j
b
i
) is a monotone decreasing function.Proof.
For alll∈{1,2,…,ajbi-1}(15)Kjbil=Rjbi+1-Rjbipkl+1bjRjbi=1-pkl+1bj+pkl+1bjRjbi.
Similarly,(16)Kjbil+1=1-pkl+2bj+pkl+2bjRjbi+1-Rjbipkl+1,and we have(17)Kjbil-Kjbil-1=pkl+1bjRjbi+pkl+1bjRjbi+1-Rjbipkl+1bi+pkl+2bj-pkl+1bj≥pkl+2bjRjbi-pkl+2bjRjbi+1-Rjbipkl+1bjKjbil>Kjbil+1.Similar to Theorem6, we can get Theorem 10 as follows.Theorem 10.
When the retransmission slots are allocated one by one forLib={Ljbi}j=1i, the Rib(Aib,Cib) get the maximal increase rate if the added one is allocated to the link with maximal kjbi(ajbi).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 Section4. 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 allnib, there are ∑j=iNajbi transactions to be scheduled, and the low bound slots to forward the corresponding packets are ∑j=i+1Najb(i+1)+∑j=iNajbi.Proof.
For allnjb,(j≥i),ajbi attempt slots for τjb are allocated in nib, and there are ∑j=iNajbi transactions to be scheduled in nib.
Similar, there are∑j=i+1Najb(i+1) transactions to be scheduled in ni+1b, which need the corresponding slots for receiving in nib.
LinksLib and Li+1b 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 ∑j=i+1Najb(i+1)+∑j=iNajbi.
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/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 ai+1bj≠aibj, 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 scheduleS, n0bi(1≤i≤N) is called an empty node if all packets in its buffers of n0bi are delivered.Definition 13.
At any slot in scheduleS, n0bi(1≤i≤N) is called a left bounding node if n0bi is an empty node and n0b(i+1) is not an empty one. Similarly, n0bi(1≤i≤N) is called a right bounding node if n0bi is not an empty node and n0b(i+1) is an empty one.The GW is always an empty node, andn0bN is always a right bounding node before it finishes aNbi communication transactions.Corollary 14.
For alln0bi(1≤i≤N), when ∑j=iNajbi transactions are scheduled, all packets in n0bj(i≤j≤N) are delivered. Specifically, the forwarding schedule over the BN is finished when ∑j=1Najbi transactions are scheduled in n1bj.Based on Theorem11 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.
Searchn0bj in which all packets are delivered according to Corollary  14.Step 2.
Search bounding nodes from GW ton0bj. 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 Step3.Step 5.
If the convergecast schedule over the BN is finished, scheduling sequence is generated; else go to Step1.


## 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 theFNi

We simulate theFNi 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 2/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 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. Figure4 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. Figure5 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 onBN

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 n0bi and GW is 3i. 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. Figure7 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 inFNi are at depth i+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 inFNi 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 depthi+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 theFNi 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.


## 7.1. Performance Evaluation on theFNi

We simulate theFNi 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 2/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 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. Figure4 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. Figure5 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 onBN

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 n0bi and GW is 3i. 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. Figure7 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 inFNi are at depth i+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 inFNi 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 depthi+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 theFNi 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.



---

*Source: 123062-2015-05-13.xml*