Sage Journals: Discover world-class research

Abstract

WirelessHART is considered to be one of the most promising wireless network protocols for its high robustness comparing to other similar wireless networks. Convergecast is an efficient approach for industrial control. But in WirelessHART specifications, no scheduling algorithms are defined for convergecast. In this paper, an efficient link arrangement strategy for packet delivering named WBLSS (Weight-Based Link Scheduling Strategy) is proposed. In order to improve the communication reliability and assign time slots to nodes in the network evenly, WBLSS considers network topology for time slot assignment. Nodes with more children in the communication tree have more time slots for communication, which improves the global throughput dramatically. As compared to the existing link arrangement strategy in WirelessHART, both the throughput of the network and the real-time performance are improved in WBLSS.

1. Introduction

Industrial wireless sensor networks are efficient means of industrial control, but considering the special demands of industry, the wireless network transport protocol must have high real-time capability. The traditional protocols like ZigBee, UWB, ISA, and Bluetooth promote the application of wireless technologies in industrial automation control. However, there are many challenges when they are used in practical application because of lack of real-time characteristics [1, 2]. To address the real-time of wireless networks, WirelessHART, extended from HART protocol, becomes the first publicly available standard.

WirelessHART employs IEEE 802.15.4-2006 as its physical layer and uses 16 frequency channels. In MAC layer, it defines some unique features, including 10 ms time slot of TDMA technology, global network time synchronous, frequency hopping, and channel blacklist. Communication between the devices is arranged in one time slot composed of superframe. When one superframe is an end and it will come back to ASN0 (Absolute Slot Number) till this superframe is abandoned, the time synchronization can be finished in one slot. Devices will record the time when the packet arrives, compare with the anticipant arrival time, and get the time deviation delta-T ( $Δ T$ ). If the packet is from its time synchronization neighbor, the device will alter its clock according to $Δ T$ . The frequency hopping technique realizes the diversity of channels. Communication between different devices uses distinct channels, and distinct channels are used when one device connects to other devices in different slots, which improves the reliability of communication.

In the network layer, WirelessHART supports the self-organized mesh network topology; each device in the network acts as a router [3, 4]. Being a centralized network, WirelessHART has exactly one active network manager to be responsible for everything like constituting network, allocating resource, and configuring routers. The network manager collects the field information to get the topology of the network and schedule the communication according to the need of actual transmission. By our scheduling algorithm, network manager creates the superframe which consists of time slots and links between the devices and sends it to each device. The device will establish communication time based on the superframe. Although WirelessHART protocol specifies the structure of the superframe, the scheduling algorithm is not presented.

Several universities and research institutes began to study the scheduling algorithm for WirelessHART after the agreement was announced and have achieved some research results [5, 6]. In this paper, we put forward a scheduling strategy based on the network weights—WBLSS which combines the periodical sensor data with the actual load of the network link. WBLSS can realize the convergecast in a short period of time and improve the network throughput.

2. Related Work

The current study for the wireless network scheduling algorithm has achieved fruitful results, but those algorithms cannot be applied to WirelessHART directly. By now, the researches about the scheduling algorithm of WirelessHART are so few.

Zhang et al. and Soldati et al. started to research this topic, and in literature [7, 8] they analyzed the convergecast of WirelessHART network with line routing topology, multiple line routing topology, and general tree routing topology. Their algorithm takes at least $2 N - 1$ slots and $N / 2$ channels to finish data aggregation in line or multiple line routing topology and takes at least $m a x {2 n - 1, N}$ time slots in tree routing topology, where N is the nodes in the network and n is the number of nodes that belong to the maximum subtree of root node. Though their scheduling algorithm can optimize slot and channel usage, the algorithm does not support the mesh topology and the redundant path.

In [9], Saifullah et al. presented an algorithm named C-LLF which set a critical time for each data flow. The flow cannot arrive at the destination address when the flow is not sent before critical time. The difference between the critical time and the current time makes up the laxity of the flow. Setting the flow which has the least laxity in the active flows to the current slot, until the active data stream is scheduled or the available channel is assigned, the algorithm takes the next time slot. C-LLF realizes the effective arrangement for real-time data flow and reduces the delay of data flow. However the complicated calculations make it difficult to implement in production.

In [10], Fang et al. delaminated the node in network and allocated time slots for the communication link between layers. Link in different layer uses distinct channel. This approach avoids conflict, but the actual communication is not considered; therefore it leads to high latency and low throughput.

Based on graph routing in WirelessHART protocol, Dang et al. put forward a scheduling algorithm in [11]. The algorithm arranges slot for each link in subgraph, and the superframe can send packets from the source node to the destination node. To increase the robustness of the network, every link is assigned twice. Reference [12] improves the retransmission mechanism of the above algorithm. The new algorithm finds an optimal path according to the reliability of the link between the source and destination, and only the link in the optimal path is assigned twice. Both of them are based on graph routing and need to schedule time slot for every graph, which leads to more transmission latency and resource consumption.

In general, the researches regarding the scheduling strategy for WirelessHART despite having yielded the certain results cannot solve the convergecast problem in mesh network perfectly. In this paper, owing to the actual traffic of network link, taking the load balancing of each link into full account and weighting value for links, WBLSS assigns slot according to its weighted value. The algorithm can converge the traffic rapidly in mesh network of WirelessHART.

3. Scheduling Strategy

This chapter describes the scheduling strategy of WBLSS including building network model, the method of the link weight, and the slot management method.

3.1. Network Model

WirelessHART network is a mesh network consisting of the field devices, the gateway server, and the network manager as shown in Figure 1. The field device can sense and control process equipment, moreover acting as a router, which can forward flow for neighbor device. Gateway is the bridge linking the wireless network and the network manager. As a cache for the WirelessHART data and the source point of time synchronization, only one active gateway can be used in WirelessHART network, but there could be more than one virtual gateway to improve the robustness of the network. The responsibility of the network manager is to configure the network and schedule communication. Network manager supervises the whole network's flow and controls the communication between the devices by broadcasting superframe.

Figure 1

A WirelessHART network.

Gateway is the sink node of the WirelessHART, so all the data will converge to the gateway. We layer the device and use “depth” to define the hops between source device and the gateway. The smaller the depth value the device has is, the less hops there are to reach the gateway. Therefore we assume that the devices with the same depth do not send packets to each other, and the packet will only be sent to lower ground when the data flows to the gateway and diametrically when the network manager broadcasts superframe.

Based on the assumptions, the WirelessHART networks could be modeled as a directed graph $G = (V, E)$ , where V is the set of field devices including gateway and E is the set of links connecting devices in V, as shown in Figure 2. Link $l = (u, v) \in E$ shows node u can communicate with node v directly.

Figure 2

An example of network topology.

3.2. Link Weight

The nodes in the network can receive, send, and store packet. When the number of receiving packets is greater than the number of sending, the packets will be accumulated in the nodes which will result in packet loss. To avoid packet loss, the weight of the sending link (the link between the node and its father node) should be larger than the receiving link (the link between the node and its child node). We use the weight of the receiving link and the packets' number of the node to calculate the value of the sending link. When the node has more than one sending link, the result will be given to each sending link on average to load balancing. A layer-to-layer method is used from bottom to top of the topology to compute the weight of the sending links for every node and stipulate that the weight of the receiving link of leaf node is 0. The proposed weight is calculated as

\begin{matrix} W_{u s} = ⌈\frac{(\sum W_{u d} + a)}{n}⌉, \end{matrix}

(1)

where

W_{u s}

is the weight of sending link of node u,

\sum W_{u d}

is the weighted sum of receiving links of node u, a is the number of packets that wait to be sent in node u, and n is the number of the sending link of node u. The result is rounded up to increase the redundant path. We assume a equals 1 for simplicity in research. An example of topology in Figure 2 demonstrates the calculating procedure. The leaf node J has two sending links (

n = 2

) and one packet to send (

a = 1

) and the weighted sum of receiving links of node u is 0. Therefore the weight of the sending link,

(j, h)

and

(j, i)

, is 1. As to node H,

a = 1

n = 3

, and

\sum W_{h d} = 1

, so the weight of sending link,

(h, c)

(h, d)

, and

(h, e)

, is 1 too. Computing the other node in turn will get weighted network as shown in Figure 3.

Figure 3

Weighted network.

3.3. Scheduling Algorithm

In order to improve performance of data convergecast, there are some restrictions that need to be considered.

Collision Avoidance. The TDMA isolates the communication in time and the frequency hopping isolates the communication in channel which reduce the likelihood of conflict greatly. However, they cannot completely become free from conflicts. There are two kinds of conflicts. Due to the half duplex of the device, conflicts are introduced when the node is both the sending node and the receiving node in one slot, as shown in Figure 4(a). Each node can only listen to one channel in one slot; therefore the node which two nodes send packets to in one slot will lose packets, as shown in Figure 4(b). The communication is conflict-free, if the scheduling algorithm avoids both cases.

Figure 4

Two kinds of conflicts.

The Order of Communication. In order to reduce the need of the storage of the node and decrease the delay of the packet, the node should send the packet as soon as possible. Therefore the sending link should be arranged after the receiving link. This condition is unsatisfactory for the packet from the node itself, so the link for sending this packet can be arranged more front than its receiving links.

The Rules of Assigning Link. In WirelessHART, nodes can communicate with each other in one slot using different channels. If all the receiving nodes on the equal layer are arranged in the same slot, packets will not be flowed to lower layer because of the half duplex of the node, which could increase the network delays. To solve this problem, we stipulate that the number of the destination node on the equal layer must not exceed half of the total number of nodes on the layer. The communication is conflict-free if there is only one node on the layer.

Algorithm Description. Algorithm 1 is our scheduling algorithm to allocate time slots for the link according to the weighted network and the constraint condition.

Algorithm 1: WBLSS link scheduling strategy.

Output: Weighted Graph G

Input: Superframe SF

( $1$ ) begin

( $2$ ) while (W != 0) do

( $3$ ) for $d \leftarrow D$ to 1 do

( $4$ ) for Every link $l = (u, v)$ in $L_{d}$ do

( $5$ ) if ( $w_{l} > 0$ ) then

( $6$ ) if ( ${N S A S}_{u}$ != ⌀) then

//Take the elements ASN from ${S A S N}_{u}$ in turn

( $7$ ) for $n \leftarrow A S N$ to N do

//The constraint condition in the above section

( $8$ ) if l meet SF[n] then

( $9$ ) SF $[n] \leftarrow l$ ; $W \leftarrow W - 1$ ; $w_{l} \leftarrow w_{l} - 1$ ;

//Allocate ASN n for l and add the node v to the ${S A S N}_{v}$

( $11$ ) ${S A S N}_{v} \leftarrow n$ ;

( $12$ ) ${S A S N}_{u} = {S A S N}_{u} - \{A S N \}$

( $10$ ) end

( $11$ ) end

( $12$ ) else

( $13$ ) for $n \leftarrow 0$ to N

( $14$ ) if l meet $S F [n]$ then

( $15$ ) $S F [n] \leftarrow l$ ; $W \leftarrow W - 1$ ; $w_{l} \leftarrow w_{l} - 1$ ;

( $11$ ) ${S A S N}_{v} \leftarrow n$ ;

( $17$ ) end

( $18$ ) end

( $19$ ) end

( $20$ ) else

( $21$ ) $L_{i} = L_{i} - \{l \}$ ;

( $22$ ) end

( $23$ ) end

( $24$ ) end

( $25$ ) end

The input in the algorithm is weighted graph G, the depth of the graph is D, and the network's weighted sum is W. The output of the algorithm is the superframe which can be recognized by the nodes. The algorithm is running until the value of W is equal to zero and allocates a suitable slot to the nodes in every layer, starting at the lowest available level of the topology and moving upward. In the layer d, for example, traversing the set of sending link $L_{d}$ , if the weight of the link $l = (u, v)$ is not zero, the link l will be allocated a slot and then removed from the set $L_{d}$ , where u is the sending node and v is the receiving node. Based on the constraint condition, the link l should be arranged after the receiving link of the node u. The algorithm starts at the bottom, and the slots, allocated to the receiving links of node u, are stored in an ordered set $A S N_{u}$ ; therefore the algorithm will search the right slot for the link l according to the set $A S N_{u}$ . We calculate the schedule of Figure 2, as shown in Figure 5.

Figure 5

The schedule of superframe calculated by WBLSS.

From the superframe, we can get that every node appears only once in the same slot, and every link in the same slot is arranged in different channels, so the communication is conflict-free. The weight of the link determines the link's assigned slots. Taking the link $l = (a, g w)$ whose weight is five, for instance, we arrange five slots for it after node a receives packets. The superframe calculated by WBLSS arranges the link to gateway in every slot. In this case, they are $(a, g w)$ and $(b, g w) .$ If the packet arrives at node a or node b, the packet will be sent to gateway in the next slot. Therefore the algorithm reduces the waiting time of the packet in the node and increases the throughput.

4. Analysis and Evaluation

In this section, we compare our method with Z. Haibo's convergecast schedule in [8] and the graph route-based link scheduling scheme, GRBLSS, in [12] to evaluate the performance of our algorithm in three aspects: the total slots to finish convergecast, the network throughput, and the maximum delay of the packet.

Z. Haibo's strategy cannot be applied in mesh network, so we get a tree topology from Figure 2 by BFS, as shown in Figure 6. The comparison of performances between Z. Haibo's strategy and our method is in the tree topology. Figure 7 shows the result of comparison, and it shows that WBLSS has the same performance as Z. Haibo's. This is because the node has only one parent node and there is no redundant link in tree topology; in the process of scheduling, each link has fully played the role. Compared to tree topology, WBLSS has better performance in mesh topology. As can be seen from Figure 7, there is a big difference of performance between MBLSS and GRBLSS, because GRBLSS builds a separate superframe for each node and these superframes are linked end to end to realize convergecast, which increases the period of convergecast.

Figure 6

Tree topology generated by BFS.

Figure 7

The simulation result of slot number to finish convergecast.

The network throughput can be expressed by the ratio between the total number of the packets in the network and the total slots required to finish the convergecast as follows:

\begin{matrix} N T = \frac{n}{N} . \end{matrix}

(2)

Table 1 is the computation result of the throughput of two other algorithms and our strategy in two topologies. As shown in the table we notice that our algorithm has the same throughput as Z. Haibo's in the tree topology and has a 46 percent increase over graph route-based link scheduling scheme.

Table 1

Throughput comparison result of algorithms.

Scheduling algorithm	Throughput (%)
GRBLSS	37
Z. Haibo's	91
WBLSS in tree topology	91
WBLSS in mesh topology	83

The redundant path in the mesh network will increase the maximum delay of the packet. In a D depth network, for example, the result of maximum transmission delay is displayed in Table 2. GRBLSS imports the retransmission mechanism for the optimal path between the source node and the gateway, so it needs $2 D$ slots to transmit the packet to the gateway no matter whether the conflict occurs or not. However, when the conflict appeared in Z. Haibo's strategy, the packet will be sent to gateway in the next superframe, so the maximum delay with conflict is $2 D$ and D without conflict. In our method, the retransmission link is mixed with the effective way and if there occurs a conflict, the packet will be resent within C slots which is the number of child nodes of the sending node and less than 3 generally.

Table 2

Delay comparison result for different algorithms.

Scheduling algorithm	Maximum delay without conflict	Maximum delay with conflict
GRBLSS	2D TS	2D TS
Z. Haibo's	D TS	2D TS
WBLSS in tree topology	D TS	2D TS
WBLSS in mesh topology	(D + C) TS	(D + C) TS

5. Conclusion

In this paper, we present an effective convergecast scheduling algorithm, WBLSS, for WirelessHART network with low delay and high throughput. Compared with other link scheduling algorithms, our method has a higher performance and wider range of application. The following work is to add the link reliability when computing the link weight and evaluate our schemes on real WirelessHART environments.

Footnotes

Competing Interests

The authors declare that they have no competing interests.

References

Gungor

V. C.

Hancke

G. P.

Industrial wireless sensor networks: challenges, design principles, and technical approaches

IEEE Transactions on Industrial Electronics 2009 56 10 4258 4265

10.1109/tie.2009.2015754

2-s2.0-70349619163

Petersen

Carlsen

WirelessHART versus ISA100.11a: the format war hits the factory floor

IEEE Industrial Electronics Magazine 2011 5 4 23 34

10.1109/mie.2011.943023

2-s2.0-84555217935

Song

Han

Mok

Chen

Lucas

Nixon

Pratt

WirelessHART: applying wireless technology in real-time industrial process control

Proceedings of the IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS '08)

April 2008

St. Louis, Mo, USA

377 386

10.1109/RTAS.2008.15

Saifullah

Chen

End-to-end communication delay analysis in industrial wireless networks

IEEE Transactions on Computers 2015 64 5 1361 1374

10.1109/tc.2014.2322609

2-s2.0-84926658201

Shen

Zhang

Barac

Gidlund

PriorityMAC: a priority-enhanced MAC protocol for critical traffic in industrial wireless sensor and actuator networks

IEEE Transactions on Industrial Informatics 2014 10 1 824 835

10.1109/tii.2013.2280081

2-s2.0-84891065883

Ikram

Petersen

Orten

Thornhill

N. F.

Adaptive multi-channel transmission power control for industrial wireless instrumentation

IEEE Transactions on Industrial Informatics 2014 10 2 978 990

10.1109/tii.2014.2310594

2-s2.0-84900863804

Soldati

Zhang

Johansson

Deadline-constrained transmission scheduling and data evacuation in WirelessHART networks

Proceedings of the 10th European Control Conference (ECC '09)

August 2009

Budapest, Hungary

4320 4325

2-s2.0-84928182799

Zhang

Soldati

Johansson

Optimal link scheduling and channel assignment for convergecast in linear WirelessHART networks

Proceedings of the 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt '09)

June 2009

10.4108/icst.wiopt2009.6312

2-s2.0-74349131150

Saifullah

Chen

Real-time scheduling for wirelessHART networks

Proceedings of the IEEE Real-Time Systems Symposium

2010

10.

Fang

Quan

Zhang

Lin

An innovative routing and resource optimization strategy for wirelessHART

Advances in Intelligent and Soft Computing 2012 165 353 360

10.1007/978-3-642-29637-6_45

2-s2.0-84861858564

11.

Dang

Shen

J.-Z.

Dong

L.-D.

Xia

Y.-X.

A graph route-based superframe scheduling scheme in WirelessHART mesh networks for high robustness

Wireless Personal Communications 2013 71 4 2431 2444

10.1007/s11277-012-0946-2

2-s2.0-84880841205

12.

Zhang

Yan

Xiang

A highly reliable link scheduling strategy for WirelessHART networks

Proceedings of the International Conference on Advanced Technologies for Communications (ATC '13)

October 2013

Ho Chi Minh, Vietnam

39 43

10.1109/atc.2013.6698073

2-s2.0-84893392759

Weight-Based Link Scheduling for Convergecast in WirelessHART Network

Abstract

1. Introduction

2. Related Work

3. Scheduling Strategy

3.1. Network Model

3.2. Link Weight

3.3. Scheduling Algorithm

Algorithm 1: WBLSS link scheduling strategy.

4. Analysis and Evaluation

5. Conclusion

Footnotes

Competing Interests

References