Weight-based Link Scheduling For Convergecast In ... - Hindawi

Copy and paste this link to your website, so they can see this document directly without any plugins.



Keywords

node, link, network, WirelessHART, time, algorithm, send, scheduling, will, packet, topology, slot, with, which, between, WBLSS, weight, slots, Zhang,, communication, number, Industrial, figure, tree, each, strategy, receive, from, mesh, this

Transcript

Weight-based Link Scheduling for Convergecast in
WirelessHART Network
Kewang Zhang
School of Electronic and Information,
Xi'an Jiaotong University,
Xi'an 710072, China
E-mail: zhangkw@mail.xjtu.edu.cn
Zhou Feng
School of Electronic and Information,
Xi'an Jiaotong University,
Xi'an 710072, China
E-mail: irfengz@163.com
Xin Li
School of Electronic and Information,
Xi'an Jiaotong University,
Xi'an 710072, China
E-mail: z295638718@stu.xjtu.edu.cn
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.
Keywords: Industrial wireless sensor network; WirelessHART, Link Scheduling, Real-time
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 lacking of real-time
characteristics (Gungor & Hancke, 2009) (Petersen &
Carlsen, 2011). To address the real-time of wireless
networks, WirelessHART, extended from HART protocol,
become the first publicly available standard.
WirelessHART employs IEEE 802.15.4-2006 as its
physical layer, and use 16 frequency channels. In MAC
layer, it defines some unique features, including 10ms time
slot of TDMA technology, global network time synchronous,
frequency hopping and channel blacklist. Communication
between the devices is arranged in one time slot composing
of super-frame. When one super-frame is end and it will
comes 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 use 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 selforganized mesh network topology, each device in the
network acts as a router (Song et al., 2008) (Saifullah, Xu,
Lu, & Chen, 2015). 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 super-frame which
consist of time slots and links between the devices and
sends it to each device. The device will establish
communication time based on the super-frame. Although
WirelessHART protocol specifies the structure of the superframe, the scheduling algorithm is not presented.
Several universities and research institutes begin to study
the scheduling algorithm for WirelessHART after the
agreement was announced and have achieved some research
results (Shen, Zhang, Barac, & Gidlund, 2014) (Ikram,
Petersen, Orten, & Thornhill, 2014). 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.
Haibo Zhang and Pablo Soldati started to research this
topic, and in literature (Soldati, Zhang, & Johansson, 2009)
(H. Zhang, Soldati, & Johansson, 2009) 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 2N-1 slots
and N/2 channels to finish data aggregation in line or
multiple line routing topology, and takes at least MAX{2n-1,
N} time slots in tree routing topology, where N is the nodes
in the network and n is the number of nodes 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 (Saifullah, Xu, Lu, & Chen, 2010), Abusayeed
Saifullah 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 realtime data flow and reduces the delay of data flow. However
the complicated calculations makes it difficult to implement
in production.
In (Fang, Li, Quan, Zhang, & Lin, 2012), Mingjie Fang
delaminated the node in network and allocate 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, Kui
Dang put forward a scheduling algorithm in (Dang, Shen,
Dong, & Xia, 2012). 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. The
(S. Zhang, Zhang, Yan, Xiang, & Ma, 2013) improves the
retransmission mechanism of 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 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 although have yielded the
certain results, but 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, BWLSS
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 Fig. 1. The filed 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 have more than one virtual gateway to improves 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 control the communication between the
devices by broadcasting super-frame.
Fig.1 An 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 depth value the device is, the less
hops 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 date flows to gateway and diametrically when the
network manager broadcasts super-frame.
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 show in figure 2. Link l=
(u,v)∈E shows node u can communicate with node v
directly.
Fig.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 packet 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 send link (the link between the node
and its father node) should be larger than the receive link
(the link between the node and its child node). We use the
weight of the receive link and the packets' number of the
node to calculate the value of the send link. When the node
has more than one send links, the result will be given to
each send 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 send links for every node and
stipulate the weight of receive link of leaf node is 0. The
proposed weight is calculated as:
𝑊𝑢𝑠 = �(�𝑊𝑢𝑑 + 𝑎)/𝑛�
Where 𝑊𝑢𝑠 is the weight of send link of node u, and
∑𝑊𝑢𝑑 is the weighted sum of receiving links of node u, and
a is the number of packets that wait to be sent in node u, and
n is the number of the send link of node u. The result is
rounded up to increase the redundant path. We assume the a
equals 1 for simplicity in research. An example on topology
in figure 2 demonstrates the calculating procedure. The leaf
node J has two send link (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 send link, (j,h) and (j,i), is 1. As
to node H, a=1, n=3 and ∑𝑊ℎ𝑑=1, so the weight of send
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.
Fig.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 free
from conflicts. There are two kinds of conflicts. Due to the
half-duplex of the device, conflicts is introduced when the
node is both the send node and the receive 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 node send
packets to in one slot will lose packets, as shown in figure
4(b). The communication is conflict free, if the scheduling
algorithm avoid both cases.
Fig.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 send link should be arranged after the receive
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 receive links.
The rules of assign link. In WirelessHART, node can
communicate with each other in one slot using different
channels. If all the receive nodes on the equal layer are
arranged in a 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 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
Here is our scheduling algorithm to allocate time slots for
the link according to the weighted network and the
constraint condition.
Table.1 WBLSS Link Scheduling Strategy
Algorithm1:WirelessHART link scheduling strategy
Output:Weighted Graph G
Input:Superframe SF
1.begin
2. while(W!=0) do
3. for d←D to 1 do
4. for Every link l=(u,v) in Ld do
5. if(wl>0) then
6. if(SASNu!=∅) then
// Take the elements asn from SASNu in turn
7. for n←asn to N do
//The constraint condition in the above section
8. if l meet SF[n] then
9. SF[n]←l; W←W-1; wl←wl -1;
//Allocate ASN n for l and add the node v to the SASNv
11. SASNv ←n;
12. SASNu = SASNu -{asn}
10. end
11. end
12. else
13. for n←0 to N
14. if l meet SF[n] then
15. SF[n]←l; W←W-1; wl←wl -1;
11. SASNv ←n;
17. end
18. end
19. end
20. else
21. Li=Li-{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 weighted sum of the network 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 allocate suitable slot for 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 send link Ld, 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 Ld, where u is the send node
and v is the receive node. Based on the constraint condition,
the link l should be arranged after the receive link of the
node u. The algorithm starts at the bottom, and the slots,
allocated to the receive links of node u, is stored in an
ordered set ASNu, therefore the algorithm will search the
right slot for the link l according to the set ASNu. We
calculate the schedule of figure 2, as shown in figure 5:
Fig.5 The schedule of superframe calculated by WBLSS
From the superframe, we can get every node appear 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,gw) 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,gw) and (b,gw). If the packet arrives at the 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 (H. Zhang et al., 2009) and the
graph route-based link scheduling scheme, GRBLSS, in (S.
Zhang et al., 2013) 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 the figure 2 by BFS, as shown
in figure 6. The compare of performance between Z. Haibo's
strategy and our method is in the tree topology. The figure 7
shows the result of compare, and it shows that WBLSS has
the same performance with 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
is fully played the role. Compare to tree topology, WBLSS
has better performance in mesh topology. As can be seen
from the figure 7, there is a big difference of performance
between MBLSS and GRBLSS, because GRBLSS builds
separate superframe for each node and these superframe is
linked end-to-end to realize convergecast, which increase
the period of convergecast.
Fig. 6 Tree topology generated by BFS
Fig.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:
𝑁𝑇 =
𝑛
𝑁
The table 2 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 with the Z. Haibo's in the tree topology and has
a 46 percent increase over graph route-based link scheduling
scheme.
Table.2 Throughput comparison result of algorithms
Scheduling Algorithm Throughput(%)
GRBLSS
Z. Haibo's
WBLSS in tree topology
WBLSS in mesh topology
37
91
91
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 3. GRBLSS imports the retransmission
mechanism for the optimal path between the source node
and the gateway, so it needs 2D slots to transmit the packet
to the gateway whatever the conflict is occurred or not.
However, when the conflict appeared in the Z. Haibo's
strategy, the packet will be sent to gateway in the next
superframe, so the maximum delay with conflict is 2D and
D without conflict. In our method, the retransmission link is
mixed with the effective way and if there occurs an conflict,
the packet will be resent within C slots which is the number
of child nodes of the send node and less than 3 generally.
Table.3 Delay comparison result for different algorithms
Scheduling Algorithm maximum delay
without conflict
maximum delay
with conflict
0
20
40
60
80
100
120
140
160
180
200
220
240
260
1 2 3 4 5 6 7 8 9 10 11 12
Sl ot s f
in is h th e co nv er ge ca st Packets of the node to send
Z. Haibo's
GRBLSS
WBLSS in tree topology
GRBLSS
Z. Haibo's
WBLSS in tree topology
WBLSS in mesh
topology
2D TS
D TS
D TS
(D+C) TS
2D TS
2D TS
2D 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.
References
Dang, K., Shen, J.-Z., Dong, L.-D., & Xia, Y.-X. (2012). A
Graph Route-Based Superframe Scheduling
Scheme in WirelessHART Mesh Networks for
High Robustness. Wireless Personal
Communications, 71(4), 2431-2444. doi:
10.1007/s11277-012-0946-2
Fang, M., Li, D., Quan, J., Zhang, S., & Lin, X. (2012). An
Innovative Routing and Resource Optimization
Strategy for WirelessHART. In H. Kim (Ed.),
Advances in Technology and Management (pp.
353-360): Springer Berlin Heidelberg.
Gungor, V. C., & Hancke, G. P. (2009). Industrial Wireless
Sensor Networks: Challenges, Design Principles,
and Technical Approaches. IEEE Transactions on
Industrial Electronics, 56(10), 4258-4265. doi:
10.1109/TIE.2009.2015754
Ikram, W., Petersen, S., Orten, P., & Thornhill, N. F. (2014).
Adaptive Multi-Channel Transmission Power
Control for Industrial Wireless Instrumentation.
IEEE Transactions on Industrial Informatics, 10(2),
978-990. doi: 10.1109/TII.2014.2310594
Petersen, S., & Carlsen, S. (2011). WirelessHART Versus
ISA100.11a: The Format War Hits the Factory
Floor. IEEE Industrial Electronics Magazine, 5(4),
23-34. doi: 10.1109/MIE.2011.943023
Saifullah, A., Xu, Y., Lu, C., & Chen, Y. (2010, 2010).
Real-Time Scheduling for WirelessHART Networks.
Paper presented at the IEEE Real-Time Systems
Symposium.
Saifullah, A., Xu, Y., Lu, C., & Chen, Y. (2015). End-toEnd Communication Delay Analysis in Industrial
Wireless Networks. IEEE Transactions on
Computers, 64(5), 1361-1374. doi:
10.1109/TC.2014.2322609
Shen, W., Zhang, T., Barac, F., & Gidlund, M. (2014).
PriorityMAC: A Priority-Enhanced MAC Protocol
for Critical Traffic in Industrial Wireless Sensor
and Actuator Networks. IEEE Transactions on
Industrial Informatics, 10(1), 824-835. doi:
10.1109/TII.2013.2280081
Soldati, P., Zhang, H., & Johansson, M. (2009, 2009).
Deadline-constrained transmission scheduling and
data evacuation in WirelessHART networks. Paper
presented at the Control Conference (ECC), 2009
European.
Song, J., Han, S., Mok, A., Chen, D., Lucas, M., Nixon, M.,
& Pratt, W. (2008, 2008/04//). WirelessHART:
Applying Wireless Technology in Real-Time
Industrial Process Control. Paper presented at the
IEEE Real-Time and Embedded Technology and
Applications Symposium.
Zhang, H., Soldati, P., & Johansson, M. (2009, 2009/06/).
Optimal link scheduling and channel assignment
for convergecast in linear WirelessHART networks.
Paper presented at the 7th International
Symposium on Modeling and Optimization in
Mobile, Ad Hoc, and Wireless Networks.
Zhang, S., Zhang, G., Yan, A., Xiang, Z., & Ma, T. (2013,
2013). A highly reliable link scheduling strategy
for WirelessHART networks. Paper presented at the
2013 International Conference on Advanced
Technologies for Communications.

PDF Document reader online

This website is focused on providing document in readable format, online without need to install any type of software on your computer. If you are using thin client, or are not allowed to install document reader of particular type, this application may come in hand for you. Simply upload your document, and Docureader.top will transform it into readable format in a few seconds. Why choose Docureader.top?

  1. Unlimited sharing - you can upload document of any size. If we are able to convert it into readable format, you have it here - saved for later or immediate reading
  2. Cross-platform - no compromised when reading your document. We support most of modern browers without the need of installing any of external plugins. If your device can oper a browser - then you can read any document on it
  3. Simple uploading - no need to register. Just enter your email, title of document and select the file, we do the rest. Once the document is ready for you, you will receive automatic email from us.

Previous 10

Next 10