Sage Journals: Discover world-class research

Abstract

Research studies on smart cities have been conducted, which will enable a better management of the available resources. Industrial wireless sensor networks (IWSNs) are important part of smart city. IWSNs are used for process measurement and control applications in harsh and noisy industrial environments. As substitutes for traditional wired industrial networks, IWSNs are more flexible, scalable, and efficient. However, resource limitation of the sensor nodes and unreliability of low-power wireless links, in combination with stringent quality of the service (QoS) requirements of industrial applications, imposes many challenges in designing efficient routing for IWSNs. Existing standards propose a simple and reliable routing mechanism named graph routing. In this paper, we propose novel routing algorithms to discover reliable paths and construct reliable routing graphs. In our approaches, the centralized manager selects parent nodes for each node in the network to satisfy reliability requirements of the intended application. We try to maximize the number of reliable nodes and change the parent nodes selection strategy along with the link quality and the link correlation. Our design is evaluated using simulation where we show that our algorithm could achieve a balance between routing reliability and overhead.

1. Introduction

The ubiquitous computing research studies and the deployment of urban wireless infrastructures make smart cities take shape [1–5]. The concept of smart cities is a natural evolution of research studies about smaller-scale smart spaces [6, 7]. Research studies on smart cities have been conducted by not only some organizations but also several governments. Smart cities form advanced collaborations to optimize resource allocation by monitoring the urban environment, collecting and conveying information, and establishing automated control. Wireless sensor networks (WSNs) can be used to integrate with the surrounding environment and interact with the management system. In smart cities, IWSNs as a smaller smart space can intercommunicate and interoperate with other networks of smart cities providing a unified and personalized interface for their managers.

IWSNs are new industrial networks appearing after field bus in industrial control field [8–13]. IWSNs should be designed specifically due to the extreme industrial environments and the stringent industrial application requirements. WirelessHART [14] approved by IEC is the first global industrial wireless communication standard. It is the extension of wired HART for wireless process monitoring and control. On September 6, 2011, ISA-100.11a [15] is recognized by IEC as a new standard for process automation (PA) and factory automation (FA). Nowadays, more and more research studies about IWSNs have emerged.

In industrial systems, the existing standards advocate centralized control. Unlike the distributed control adopted by the traditional WSNs, IWSNs push the complexity of ensuring reliable and accurate data transfers to the centralized manager. The construction of the global reliable routing is performed by the centralized manager to meet stringent requirements [16–18]. The centralized control could achieve relatively complicated algorithms and makes control decisions based on the whole network's information. Therefore, the centralized control could improve network performance by global information and globally optimal control laws.

In typical IWSNs, each field device collects data and publishes its data to the manager, and then the manager dispatches the control messages to field devices periodically. The broadcast messages are propagated through the network to configure the node information. Uplink has a sample rate of each device to transmit its process message to the centralized manager. The broadcast and uplink traffic in industrial applications is mainly a cyclical communication with a predicable interval. In some situations, the manager needs to generate downlink path for each device to forward specific control messages. For industrial control communication, lost packets may lead to industrial application malfunction. But there are many challenges for industrial field devices to achieve reliable transmission. On the one hand, too many wireless devices in the 2.4 GHz frequency band likely cause mutual interference. On the other hand, the industrial environment is extremely severe which may lead to signal reflection and scattering. How to satisfy the reliability requirements is a challenging problem in routing algorithm.

A simple and reliable routing mechanism named graph routing is presented by ISA 100.11a [15] and WirelessHART [14]. However, these current standards do not specify a routing algorithm. How to construct a reliable graph has not received enough attention and how to satisfy the strict reliability requirements in the graph routing is still a challenge. Now several research works have been devoted on the reliable graph routing [19–21]. But existing approaches educe the routing graphs based on the fixed routing strategy, which may decrease flexibility to balance communication performances. We hope that the routing strategy could decrease overhead while the reliability can be guaranteed. Therefore, we present flexible route selection algorithms which consider the reliability requirement together with network overhead. The route selection of each node depends on the link quality with neighbor node. In a word, we propose the efficient algorithms to construct reliable graphs: determining the routing that (1) achieves the maximum proportion of nodes which successfully transmit packets to the destination node (2) and a tradeoff between the reliable routing and the network overhead.

In this paper, our algorithms choose reliable parent nodes to construct reliable graphs. We maintain maximum number of reliable nodes and present an evaluation method of node reliability. The remainder of this paper is organized as follows. Section 2 presents related works of reliable routing. Section 3 introduces the architecture of IWSNs. Section 4 describes the proposed centralized reliable graph routing. This section details how to construct reliable graphs. Section 5 presents the performance of our approach compared with other graphs. Finally, we conclude our approach and summarize the future work in Section 6.

2. Related Works

In this section, we first present previous works about reliable routing in wireless sensor networks (WSNs). Then two routing approaches defined by existing industrial standards are described.

2.1. Reliable Routing in Wireless Sensor Networks

IWSNs are meant for industrial measure and control with high reliable requirements. Link error is usually due to network congestion, node failure, signal interference, and so on. How to select a reliable path is an important research for routing protocols. We also focus on how to repair path if route entries become invalid.

Some routing protocols regard link error rate as a routing metric for reliability [22, 23]. In [22], energy-aware routing taking into account the retransmission can choose a reliable path by energy cost. Because link error rate can cause the potential energy cost. In [23], the source node sends a redundant packet via alternate path to achieve reliability sometimes. If the reliability of the selected path does not meet the requirements, the source node will randomly select one additional successor.

Some routing protocols achieve fault tolerance by providing multiple path [24–29]. Multipath can improve communication reliability, realize load-balancing, and relieve congestion. Ad hoc on-demand multipath distance vector (AOMDV) [26] is the multipath extension of a single path routing protocol known as ad hoc on-demand distance vector (AODV). AODMV maintains disjoint multipath which fails independently. The disjoint paths include link-disjoint path and node-disjoint path. Link-disjoint is effective in keeping links available while node-disjoint is appropriate for relieving congestion.

Most of these works focus on identifying reliable path and constructing multiple path. IWSNs should adapt to harsh environment and meet stringent requirements. ISA100.11a [15] and WirelessHART [14] as main industrial standardization groups present graph routing which also supports multipath.

2.2. Source Routing and Graph Routing

These industrial standards define two primary routing approaches: source routing and graph routing. Source routing is a general routing supported by simple protocol and a single direct route from a source to a destination. The next hop of a packet will be directed to a specific neighbor. The ordered list of routing is included in the network layer header. Source routing only establishes a single path between the source and the destination.

In graph routing, the packet is disseminated to its destination according to routing graph. The routing graph is a set of directed links and identified by unique graph ID. All nodes will be preconfigured with relevant graph information about which neighbor the packets can be forwarded. The network layer header of packets just need to include the graph ID. In a graph, the neighbors which can be forwarded are not single. So graph routing makes it possible to provide redundant communication path. The source routing and graph routing information defined in separate network header fields could coexist in industrial standards.

Reference [19] presents efficient algorithms to construct three types of reliable routing graphs for different communication purposes. This paper ensures reliability by redundant parent nodes. To construct reliable graph, this paper choose two different parent nodes so that there are two communication paths at least. The experiment results show that the algorithms can achieve highly reliable routing at the cost of modest configuration overhead compared with other baseline methods.

3. Industrial Wireless Sensor Networks Architecture

The architecture of IWSNs mainly consists of centralized manager, backbone routers (BBRs), and field devices (see Figure 1). The centralized manager not only takes charge of the management of the entire network but also represents infrastructure device to communicate with external networks. In IWSNs, each field device, sensor or actuator, has a designed sample rate to publish its data to manager and receive control commands. These field devices attached to the plant devices collect data, in this paper, and also route message [16].

Figure 1

The architecture of IWSNs.

The BBRs unite multiple wireless subnets and make industrial wireless systems interoperate with control networks. Multiple BBRs make the system robust with redundancy and optimize the communication path. Multiple BBRs provide multiple access points in IWSNs in order to facilitate node arrangement [30]. So the ISA100.11a architecture employs multiple BBRs and they are all connected by wire [15].

Both ISA100.11a and WirelessHART adopt IEEE 802.15.4-2006 [31] as the bottom of their communication stack. These standards define TDMA, channel hopping, and industry-standard AES-128 ciphers, and keys. In network layer, the backbone network conforms to Internet Protocol (IP), IPv4 and newer IPv6. In IWSNs, these standards present two primary routing approaches: graph routing and source routing. The centralized manager is responsible for maintaining up-to-date routing and guaranteeing the communication reliability.

4. Centralized Reliable Graph Routing

In this section, we present the content concerning how to achieve the centralized reliable graph routing. The mechanism of graph routing is described in detail by industrial standards. We proposed the algorithms to construct reliable routing graph. We describe three reliable routing graphs for different communication purposes. For three communication types, the reliable routing graph should meet different requirements.

4.1. Communication Types

There are three communication types for industrial process monitoring and control (see Figure 2). The BBRs link up the field network and the control system. The types of communication are broadcast, uplink, and downlink.

Figure 2

The Types of Communication.

4.1.1. Broadcast

Broadcast refers to the direction from the BBRs towards entire network. The centralized manager propagates the common configuration and control data to field devices periodically.

4.1.2. Uplink

Uplink refers to the direction from field devices towards the BBRs, in the reverse direction of broadcast. Every field device has a specific sample rate to propagate its process data to the manager.

4.1.3. Downlink

Downlink refers to the direction from the BBRs towards any field device. The centralized manager propagates a specific control message to an individual device by the BBRs.

The routing graphs have different characteristics for different communication types. The entire network can share the same broadcast graph and uplink graph. However, the centralized manager should generate the corresponding downlink graph for each field device. The reliability requirements are also different when applied to different communication types.

4.2. Notations

This section presents the notations used in this paper. In wireless network $G = (V, E)$ , $V_{BBR}$ denotes the set of BBRs, and $V_{N}$ denotes the set of field devices, and M denotes the centralized manager. In this paper, we assume that centralized manager and $V_{BBR}$ are connected by wire, and the BBRs are wireless access points. The edge $e_{i, j} \in E$ represents $v_{i}$ and $v_{j}$ can communicate directly for all $v_{i}, v_{j} \in V$ . Then uplink graph and broadcast graph are represented by $G_{U} (V_{U}, E_{U})$ and $G_{B} (V_{B}, E_{B})$ , respectively. $G_{N} (V_{N}, E_{N})$ represents the downlink graph of the node $v_{N}$ .

In this paper, we define $R_{N}$ as the expected reliability of publishing a packet from the $V_{BBR}$ to $v_{N}$ while $R_{N}^{'}$ as the expected reliability of sending a packet from $v_{N}$ to the $V_{BBR}$ . $R_{i, j}$ denotes the expected reliability of communication from $V_{BBR}$ to $v_{i}$ via $v_{j}$ and $R_{i, j}^{'}$ denotes the expected reliability of communication from $v_{i}$ to $V_{BBR}$ via $v_{j}$ . The expected reliability means the probability of sending a packet from source device to destination device successfully. For an edge $e_{i, j}$ , we use $L_{i, j}$ to denote link reliability of single hop communication between $v_{i}$ and $v_{j}$ . Therefore, $R_{i, j}$ and $R_{i, j}^{'}$ are given by

\begin{matrix} R_{i, j} = R_{j} L_{i, j}, \\ R_{i, j}^{'} = R_{j}^{'} L_{i, j} . \end{matrix}

(1)

In order to construct reliable graph, individual node should be positioned relative to the BBRs. So we use rank

r_{N}

to denote relative position between the BBRs and a field device.

r_{BBR} = 0

at the BBRs and the rank of field devices connected with the BBRs directly is 1. The rank of a node is equal to the rank of its parent nodes plus one. If a node has more than one parent node, we choose the first selected parent node for rank calculation. The rank of a node is a scalar representation of location; therefore, the rank monotonically decreases towards the BBRs, increasing in the down direction and decreasing in the up direction.

We choose reliability rather than hop count as criteria to choose parent node to improve reliability and reduce energy consumption. Equation (1) shows that the path with fewer hops has higher reliability in general, but more hops may be better when additional forwarding nodes are inserted according to certain principles to shorten the length of individual hops [32, 33]. In our approach, we define a reliability parameter $R_{d}$ to measure the reliability of the industrial application. The nodes with low rank are more critical and need to be more reliable because more data are transited by these nodes. Therefore, our approaches set up a threshold $R_{d}^{r_{i}}$ to measure the reliability of $v_{i}$ . If the reliability of a node $R_{i}$ is greater than $R_{d}^{r_{i}}$ , the node is a reliable node in the graph and included in $V_{i n}$ which is the reliable node set. Otherwise it will be included in the unreliable node set $V_{e n}$ .

4.3. Link Correlation

A feature of wireless communication is that link errors are dependent between neighbor nodes. Recent works [34–36] have shown that correlated interference might lead to correlated packet errors because the interference signal can corrupt neighbor links simultaneously. Link correlation has significant effects on reliability attributes for our route selection.

To illustrate the link correlation, we give an example to demonstrate the reliability attributes with correlation, as Figure 3. Link independence means that $L (i, j_{2} | \bar{i, j_{1}})$ equals $L_{i, j_{2}}$ , where $L (i, j_{2} | \bar{i, j_{1}})$ is the link success probability between $v_{i}$ and $v_{j_{2}}$ when the link between $v_{i}$ and $v_{j_{1}}$ fails. When node $v_{i}$ forwards a packet, if $v_{i}$ forwards the packet to $v_{j_{1}}$ , the packet delivery probability is $L_{i, j_{1}}$ . If $v_{j_{1}}$ does not receive the packet and the packet is forwarded to $v_{j_{2}}$ , the packet delivery probability is $L (i, j_{2} | \bar{i, j_{1}})$ . Therefore, when the packet is forwarded to $v_{j_{3}}$ , the packet delivery probability is $L (i, j_{3} | \bar{i, j_{1}}, \bar{i, j_{2}})$ . The node $v_{i}$ receives the broadcast packet successfully as long as one of its parent nodes transfers successfully. Therefore, the packet transmission probability is $1 - P (\bar{L_{i, j_{1}}}, \bar{L_{i, j_{2}}}, \bar{L_{i, j_{3}}})$ , where $P (\bar{L_{i, j_{1}}}, \bar{L_{i, j_{2}}}, \bar{L_{i, j_{3}}})$ is the probability that none of packets are received from $v_{j_{1}}$ , $v_{j_{2}}$ , $v_{j_{3}}$ , which equals $(1 - L_{i, j_{1}}) (1 - L_{i, j_{2}}) (1 - L_{i, j_{3}})$ if link independence.

Figure 3

The link correlation.

4.4. Fault Tolerant and Reliability Attributes

The errors that occur on the communication links can be classified into two categories: transient errors and permanent errors. For permanent errors, the routing should be recovered by the centralized manager. But recovering from transient errors, hop-to-hop (data link layer) and end-to-end (transport layer) retransmission can be performed. The link layer retransmission cannot work sometimes in case of signal interference. And end-to-end retransmission has significant latency that would be unacceptable to some real-time industrial applications. The fault tolerant of our routing can be categorized into replication and retransmission mechanism for different communication types [37].

In $G_{B}$ and $G_{N}$ , the replication of packet is a mechanism used to provide fault tolerant routing. The nodes in the network broadcast it to all their next hop when they receive a new broadcast packet. Therefore, a node could receive the packet from all of its parent nodes. When a node receives multiple copies of a packet, it only rebroadcasts the packet once. Anyone of parent nodes transmits the packet to the node successfully, and then the node receives the packet successfully, as (2). In $G_{U}$ , every node tries to forward packets to the manager and every node has its paths to the manager. The hop-to-hop transmission is successful, as long as the packet is forwarded to any next hop successfully. When a node has a packet to transmit, it firstly forwards the packet to one of its parent nodes. If the packet is lost, the node will forward the packet to an alternate parent node. This retransmission process continues until either the packet is forwarded successfully or all parent nodes have been tried, as follows:

\begin{array}{l} R_{i} = 1 - P (\bar{R_{i, j_{1}}}, \bar{R_{i, j_{2}}}, \dots, \bar{R_{i, j_{n}}}), \end{array}

(2)

\begin{array}{l} R_{i}^{'} = L_{i, j_{1}} R_{j_{1}}^{'} + L (i, j_{2}, \bar{i, j_{1}}) R_{j_{2}}^{'} \\ + \dots + L (i, j_{n}, \bar{i, j_{1}}, \bar{i, j_{2}}, \dots, \bar{i, j_{n - 1}}) R_{j_{n}}^{'}, \end{array}

(3)

where

v_{j_{1}}, v_{j_{2}}, \dots, v_{j_{n}}

are selected as parent nodes.

R_{i}

and

R_{i}^{'}

are the expected reliability of the communication between the

V_{BBR}

and a field device

v_{i}

L_{i, j}

is link reliability for single hop communication between

v_{i}

and

v_{j}

P (\bar{R_{i, j_{1}}}, \bar{R_{i, j_{2}}}, \dots, \bar{R_{i, j_{n}}})

is the probability that that none of packets are received by

v_{i}

from the centralized manager via

v_{j_{1}}, v_{j_{2}}, \dots, v_{j_{n}}

In IWSNs, the centralized manager will determine the importance of the industrial massage for the desired reliability $R_{d}$ . In our approach, field devices have two attributes of reliability, $R_{N}$ and $R_{N}^{'}$ . These reliability attributes are used for constructing reliable graphs. When a new device $v_{i}$ joins network, the centralized manager chooses parent nodes for the device based on reliability attributes.

In this paper, there are redundant BBRs as access points for reliability and load balancing. They are connected by wire and the reliability attributes, $R_{BBR}$ and $R_{BBR}^{'}$ , are 1. The new node can calculate the reliability attributes by its parent nodes' reliability attributes, link reliability, and link correlation. Link reliability can be estimated by observing packet success and loss events as follows:

\begin{matrix} L_{i, j} = \frac{1}{Pac} \sum_{pac \in Pac} ‍ {ACK}_{pac} . \end{matrix}

(4)

Pac

is a set of packets forwarded from

v_{i}

v_{j}

, and

pac

is one packet of

Pac

. When packet

pac

is forwarded successfully,

v_{i}

can receive ACK_pac. Every node measures the reliability of links and the centralized manager maintains link reliability and calculates reliability attributes for routing. The link correlation also can be estimated by correlated packet reception [35].

4.5. Process to Construct Graph

In our approaches, we divide nodes into two categories: in the graph and out of the graph. The nodes out of the graph are incrementally selected to construct graph. The new node has neighbor nodes which can communicate with each other and only neighbor nodes in the graph can be selected as parent nodes; then Figure 4 illustrates an example. The communication area may not be a circle because each node may have a different communication range. We choose eligible nodes as parent nodes, and then the node becomes one of the sets in the graph. When all nodes in the network are in the graph, the process of constructing graph is over.

Figure 4

Process of constructing graph.

4.6. Reliable Broadcast Graph

Reliable broadcast graph needs $R_{i}$ of the node $v_{i}$ to meet desired reliability for the broadcast message being propagated to the entire network. Initially, all nodes are out of the graph and not included in $V_{B}$ except for $V_{BBR}$ . The manager chooses parent nodes in the graph for the new node joining graph. In the broadcast graph $G_{B}$ , for all $v_{i}$ , $v_{i}$ is a new node joining the $G_{B}$ . If the selected parent node $v_{j}$ is $V_{BBR}$ , the broadcast path is $V_{BBR} \to v_{i}$ . If not, $v_{j}$ is a field device, and $v_{j}$ can also act as a children node and find its parent node. This process terminates until it finds that its parent node is $V_{BBR}$ . Then the broadcast path is $V_{BBR} \to \dots \to v_{j} \to v_{i}$ . Therefore, when $v_{i}$ find its parent nodes from the set of nodes in the graph, the new node also has its broadcast paths.

The number of selected parent nodes depends on the reliability attribute and the link correlation. We maintain $V_{B}$ , a set of nodes which have joined $G_{B}$ and $V_{B}$ is initialized as $V_{BBR}$ . The edges $E_{B}$ are also initialized to include all wired links among $V_{BBR}$ . The reliability attribute of $V_{BBR}$ is 1 because of wired connection. Then a node $v_{i}$ is incrementally selected from $V - V_{B}$ . The node $v_{i}$ has one or more neighbor nodes included in $V_{B}$ . For a neighbor node $v_{j}$ as parent node, the reliability attribute is $R_{i, j}$ , where $R_{i, j}$ means the expected reliability that $v_{i}$ receives the broadcast message from $v_{j}$ . Sort its neighbor nodes from $V_{B}$ according to their reliability attributes $R_{i, j}$ and select $v_{j_{1}}$ with maximum reliability attribute. The rank $r_{i}$ is also determined by $v_{j_{1}}$ . If $R_{i, j_{1}}$ is greater than $R_{d}^{r_{i}}$ , we only choose one parent node and $R_{i}$ equals $R_{i, j_{1}}$ (Line 17). If not, we will find the node $v_{j_{2}}$ with maximum $R_{i}$ among its neighbor nodes correlated with $v_{j_{1}}$ , where $R_{i}$ equals $1 - P (\bar{R_{i, j_{1}}}, \bar{R_{i, j_{2}}})$ . If $R_{i}$ is greater than $R_{d}^{r_{i}}$ , we choose $v_{j_{1}}$ and $v_{j_{2}}$ as parent nodes of $v_{i}$ . If not, this process continues until $R_{i}$ is greater than $R_{d}^{r_{i}}$ . Otherwise all its neighbor nodes become its parent nodes (Line 16–22). At the end of this process, $v_{i}$ is a reliable node if $R_{i}$ is greater than $R_{d}^{r_{i}}$ ; otherwise it is a unreliable node.

For each node from the reliable node set $V_{i n}$ , we sort their rank and choose the node with minimum rank and add it to $V_{B}$ (Line 26–28). If for all $v_{i}, v_{i} \in V - V_{B}$ and $v_{i} \notin V_{i n}$ , there is no reliable node available, and we sort their reliability attribute, choose the node with maximum $R_{i}$ , and add it to $V_{B}$ (Line 29–32). This process can be repeated and terminates when all nodes in V are contained in $V_{B}$ or an error is reported, shown in Algorithm 1. The worst-case complexity of the algorithm is

\begin{matrix} \sum_{k = | V_{BBR} |}^{| V |} (| E | + (| V | - k) * k) = O ({| V |}^{3}) . \end{matrix}

(5)

Algorithm 1: Constructing reliable broadcast graph.

(1) Initially $V_{B} = V_{BBR}$ and $E_{B}$ contains all wired links

among $V_{BBR}$ .

(2) $G (V, E)$ is the original graph, construct $G_{B} (V_{B}, E_{B})$

(3) while $V_{B} \neq V$ do

(4) Find S, $S \subseteq V_{B}$ , $\forall v_{j} \in S$ , $v_{j}$ is a neighbor node of $v_{i}$ ,

and Pt is the parent set of $v_{i}$

(5) if $S = ϕ$ , the neighbor set S of $v_{i}$ , $\forall v_{i} \in V - V_{B}$ then

(6) The network topology is disconnected

(7) return FAIL;

(8) else

(9) for all node $v_{i} \in V - V_{B}$ do

(10) for all node $v_{j} \in S$ do

(11) Sort the reliability $R_{i} = 1 - P (\bar{R_{i, j}}, \bar{Pt})$

(12) if $Pt = ϕ$ then

(13) $r_{i} = r_{j} + 1$

(14) end if

(15) Choose the node $v_{j}$ with max $R_{i}$ as a parent

node, $v_{j} \in Pt$

(16) if $R_{i} \geq R_{d}^{r_{i}}$ then

(17) $v_{i} \in V_{i n}$ break;

(18) else if $S - v_{j} = ϕ$ then

(19) $v_{i} \in V_{e n}$ break;

(20) else

(21) $S = S - v_{j}$

(22) end if

(23) end for

(24) end for

(25) end if

(26) if $V_{i n} \neq ϕ$ then

(27) Choose the node $v_{i}$ , $v_{i} \in V_{i n}$ , with min $r_{i}$

(28) Add $v_{i}$ to $V_{B}$ , add $e_{j, i}$ to $E_{B}$

(29) else

(30) Choose the node $v_{i}$ , $v_{i} \in V_{e n}$ , with max $R_{i}$

(31) Add $v_{i}$ to $V_{B}$ , add $e_{j, i}$ to $E_{B}$

(32) end if

(33) end while

(34) return SUCCESS;

4.7. Reliable Uplink Graph

The algorithm to construct reliable uplink graph $G_{U} (V_{U}, E_{U})$ is similar to $G_{B} (V_{B}, E_{B})$ , and all nodes in IWSNs share the same uplink graph. $R_{i}^{'}$ is different from $R_{i}$ because the fault tolerant mechanism of $G_{U}$ is different from $G_{B}$ . Therefore, the parent nodes of a node in $G_{U}$ may not be the same as $G_{B}$ . The construction of $G_{U} (V_{U}, E_{U})$ is summarized by Algorithm 2.

Algorithm 2: Constructing reliable uplink graph.

Initially $V_{U} = V_{BBR}$ and $E_{U}$ contains all wired links

among $V_{BBR}$ .

(2) $G (V, E)$ is the original graph

Construct $G_{U} (V_{U}, E_{U})$ by applying Algorithm 1, where ${R^{}}_{i}^{'} =$

$R_{i}$ .

(4) while $V_{B} \neq V$ do

Find S, $S \subseteq V_{U}$ , $\forall v_{j} \in S$ , $v_{j}$ is a neighbor node of $v_{i}$ ,

and Pt is the parent set of $v_{i}$

(6) if $S = ϕ$ , the parent set S of $v_{i}$ , $\forall v_{i} \in V - V_{U}$ then

The network topology is disconnected

(8) return FAIL;

else

(10) for all node $v_{i} \in V - V_{U}$ do

for all node $v_{j} \in S$ do

(12) Sort the reliability ${R^{}}_{i}^{'}$

Choose the node $v_{j}$ with max ${R^{}}_{i}^{'}$ as a parent

node, $v_{j} \in Pt$

(14) if ${R^{}}_{i}^{'} \geq R_{d}^{r_{i}}$ then

$v_{i} \in V_{i n}$ break;

(16) else if $S - v_{j} = ϕ$ then

$v_{i} \in v_{e n}$ break

(18) else

$S = P - v_{j}$

(20) end if

end for

(22) end for

end if

(24) If $V_{i n} \neq ϕ$ then

Choose the node $v_{i}$ , $v_{i} \in V_{i n}$ , with min $r_{i}$

(26) Add $v_{i}$ to $V_{U}$ , add $e_{i, j}$ to $E_{U}$

else

(28) Choose the node $v_{i}$ , $v_{i} \in V_{e n}$ , with max ${R^{}}_{i}^{'}$

Add $v_{i}$ to $V_{U}$ , add $e_{i, j}$ to $E_{U}$

(30) end if

end while

(32) return SUCCESS;

4.8. Reliable Downlink Graph

The downlink graph $G_{N} (V_{N}, E_{N})$ is different from $G_{B} (V_{B}, E_{B})$ and $G_{U} (V_{U}, E_{U})$ because nodes in IWSNs have their own downlink graph and these graphs do not involve all nodes of $G (V, E)$ . We should gradually construct reliable downlink graph $G_{i} (V_{i}, E_{i})$ for each node $v_{i}$ . If $R_{i}$ satisfies the reliability criterion in $G_{i} (V_{i}, E_{i})$ , the node $v_{i}$ is a reliable node for downlink.

We maintain D, a set of nodes which have their reliable downlink graphs. Initially, D only contains $V_{BBR}$ . To construct $G_{i}$ , $v_{i}$ should find reliable parent nodes from D. The manager prefers to add the reliable nodes to D. If the reliable nodes exist, this algorithm will construct downlink graph for the node with minimum $r_{i}$ . If not, the node with maximum $R_{i}$ will be selected. If the parent node $v_{j}$ is $V_{BBR}$ , the downlink path is $V_{BBR} \to v_{i}$ . If not, the downlink path can be $V_{BBR} \to \dots \to v_{j}$ in $G_{j}$ firstly, and then $v_{j} \to v_{i}$ . Therefore, $G_{i}$ should contain the downlink graph of its parent nodes. As shown in Algorithm 3, a node $v_{i}$ is incrementally selected from $V - D$ . We select parent nodes by calculating the reliability $R_{i}$ and add the optimal node to D. Then $G_{i}$ contains $G_{j_{1}}, G_{j_{2}}, \dots, e_{j_{1}, i}, e_{j_{2}, i}, \dots$ , and $v_{i}$ .

Algorithm 3: Constructing reliable downlink graph.

Initially $D = {V_{BBR}}$ , D is a set of nodes with $G_{N}$ .

while $D \neq V$ do

(3) Find S, $S \subseteq D$ , $\forall v_{j} \in S$ , $v_{j}$ is a neighbor node of $v_{i}$ ,

and Pt is the parent set of $v_{i}$

if $S = ϕ$ , the neighbor set S of $v_{i}$ , $\forall v_{i} \in V - D$ then

The network topology is disconnected

(6) return FAIL;

else

for all node $v_{i} \in V - D$ do

(9) Choose $v_{j}$ and find $V_{i n}$ by Lines (10–25) of Algorithm 1

end for

end if

(12) if $V_{i n} \neq ϕ$ then

Choose the node $v_{i}$ , $v_{i} \in V_{i n}$ , with min $r_{i}$

Add $v_{i}$ to S, $G_{i} = v_{i} \cup e_{j_{1}, i} \cup G_{j_{1}} \cup e_{j_{2}, i} \cup G_{j_{2}} \cup \dots$

( $15$ ) else

Choose the node $v_{i}$ , $v_{i} \in V_{e n}$ , with max $R_{i}$

Add $v_{i}$ to S, $G_{i} = v_{i} \cup e_{j_{1}, i} \cup G_{j_{1}} \cup e_{j_{2}, i} \cup G_{j_{2}} \cup \dots$

(18) end if

end while

return SUCCESS;

4.9. The Percentage of Reliable Nodes and the Link Quality

In harsh and noisy industrial environment, the link quality is the major barrier to maintain reliable nodes. The bad link quality will make the network unreliable. We evaluate the relationship between the percentage of reliable nodes and the link quality.

We conducted some experiments to evaluate the percentage of reliable nodes by changing the link success probability. In Figure 5, we observe that with 50, 100, and 150 nodes in the experiments, when the link success probability is above 0.7, most nodes are reliable nodes by multiparent nodes. The percentage of reliable nodes drops quickly along with the decreasing link quality below 0.7. Figure 5(a) shows that there are few reliable nodes in the network when the link success probability drops to 0.4 but the value is nearly 0.6 in Figure 5(b) because the fault tolerant mechanism of $G_{U}$ is different from $G_{B}$ . The performance of fault tolerant mechanism is compared in Section 5. Based on these results, we conclude that it is difficult to achieve reliable nodes with bad link quality.

Figure 5

Percentage of reliable nodes and link quality.

4.10. Loop Avoidance

In IWSNs, the node mobility and failure would incur topology change and routing failure. The graph routing with our algorithm would generate routing failure, take time to converge, and introduce much overhead. However, our approaches will not cause the loop problem. The nodes in the network are added to the graph in order. We can sort these nodes based on the time when they join the graph. In $G_{B}$ and $G_{N}$ , a packet is always transmitted from an older node to a newer node while in $G_{U}$ it is from a newer node to an older node. The packets move following the order of the nodes to avoid a loop.

5. Performance Evaluation

This section shows some simulation results illustrating features of reliable graph routing. The reliable performance of graph routing is largely independent of MAC layer protocols. The simulation topology consists of 100 nodes. The link success probability of all links is the mean percentage of successful links assuming link independence. The link success probability is varied from 0.0 to 0.9. In our simulations, there are three BBRs interconnecting with the centralized manager and the topology is shown in Figure 6.

Figure 6

The topology of simulation.

5.1. Simulation Parameters

Our simulation for graph routing performance is based on 100 nodes. We evaluate the impact for graph routing performance when the size of the network varies. Figure 7 shows the number of links along with the size of the network. In Figure 7(a), the number of links decreases when the link success probability is 0.5, while it is 0.65 in Figure 7(b). The curves for three kinds of the network have similar trends.

Figure 7

Number of links with node number.

The other important parameter is $R_{d}$ . $R_{d}$ as a reliability criterion depends on the reliability requirement of industrial application. The graph routing performance is affected by $R_{d}$ , as shown in Figures 8 and 9. We vary $R_{d}$ from 0.86 to 0.98 for high reliability requirements. When the link success probability is low, there is no difference in the performance with different $R_{d}$ because our approaches select all parent nodes in routing graph. The difference appears when $R_{d}$ is greater than 0.4 in Figure 8 and 0.55 in Figure 9. The result shows that higher $R_{d}$ introduces more links and gets more successful communication. The curves with different $R_{d}$ have similar trends, so we choose 0.9 as our simulation parameter.

Figure 8

Performance of Broadcast Graph with Different $R_{d}$ .

Figure 9

Performance of Uplink Graph with Different $R_{d}$ .

5.2. Performance of Graph Routing

In the experiment, we conducted a series of experiments to evaluate the performance of routing reliability, number of links, and expected number of transmissions in different routing graphs. Then the link success probability in the network is gradually increasing from 0% to 90%. The fault tolerant mechanism of $G_{B}$ and $G_{N}$ is the same so that some experiment results of $G_{N}$ are similar to $G_{B}$ in Figures 10 and 12.

Figure 10

Performance of broadcast graph.

We compare our approaches for the reliable graphs with three other approaches. The first approach constructs a single tree using breadth-first search, the second approach chooses two parents to construct graphs [19], and the third approach contains all parents in graphs for max reliable. When a node is added to the graph in these approaches, one, two, or all parent nodes from the current graph are chosen by the average hop between the new node and BBRs. In our approach, reliability attributes are used to support a balance between the reliability and overhead. In our experiment, the number of links is measured by the number of links that the periodic messages used to maintain these links available. More parents need to exchange more information to maintain these links. The expected number of transmissions is defined as the expected number of links for the communication between every nodes and BBRs. In $G_{B}$ , the communication means the centralized manager broadcasts a message to the entire network. In $G_{U}$ and $G_{N}$ , the communication means each node sends a packet to the manager and receives a specific packet from the manager.

The first experiment evaluates the performance of reliable broadcast graph. Figure 10 summarizes all results of $G_{B}$ . Figure 10(a) shows that the percentage of successful communication varies along with the increasing link success probability. When the link success probability is less than 0.5, our approach performs best as max parent graph. Because the link reliability is low, our approach also includes all parents in graph to improve transmission success rate. But more than 0.5, the performance of our approach is different from max parent graph. In spite of the increasing link success probability, the reachable nodes also drop after 0.7 because of the less links. Figure 10(b) shows that the number of links of our approach decreases along with the increasing link success probability when the link success probability is more than 0.5. The number of links of other three approaches is constant, and the max parent graph is much higher than the other three approaches. When the link reliability can satisfy the needs of communication reliability, our approach need not maintain many links for communication. The decline of overhead also leads to the decline of reliability. Figure 10(c) shows the expected number of transmission when the manager broadcasts a message to the entire network. The higher percentage of reliable links makes more nodes reachable from the manager, and then these nodes also broadcast the message by introducing expected number of transmissions. If the percentage of reliable links is 0, any node cannot receive the broadcast message and introduce the expected number of transmissions. And the graph maintaining more links also introduces the expected number of transmissions because every node has more neighbor nodes to communicate with. We observe that the expected number of transmissions increases along with the increasing link success probability in other three approaches due to their constant links. In our approach, the expected number of transmissions increases when the link success probability is less than 0.5. However, when the link success probability is more than 0.5, the expected number of transmissions did not vary like max parent graph because of the decreased links. The few links need to be included in our graph along with the increasing link reliability. Therefore, the result is affected by the two factors jointly as Figure 10(a). So the curve of the expected number of transmissions increases slowly around 0.5 to 0.7, and then drops quickly after 0.7.

In the second experiment, the performance of $G_{U}$ is similar to $G_{B}$ , as shown in Figure 11. In other three approaches, the successful communication and the expected number of transmissions all increase along with the increasing link success probability and the number of links is constant. In Figure 11(a), the successful communication of our approach does vary as max parent graph when link success probability is more than 0.7. That is because the fault tolerant mechanism of $G_{U}$ is different from $G_{B}$ so that the reliability attributes are different. When the node $v_{i}$ has the same parent nodes in different graphs, $R_{i}^{'}$ is lower than $R_{i}$ with the same number of links. Therefore, the nodes in $G_{U}$ which meet the reliability requirement need to maintain more links than $G_{B}$ , as shown in Figure 11(b). Figure 11(c) shows the expected number of transmissions when every node in the network forwards a packet to the manager. So the expected number of transmissions is greater than $G_{B}$ .

Figure 11

Performance of uplink graph.

Figure 12

Performance of downlink graph.

The third experiment shows the performance of reliable downlink graph. As $G_{N}$ and $G_{B}$ have the same reliability attributes and fault tolerant mechanism, the performance of reliability and the number of links are the same, as shown in Figures 12(a) and 12(b). Figure 12(c) shows the expected number of transmissions when the manager sends a special packet to every node in network. Every packet should be broadcast in the $G_{N}$ of its destination, so 100 packets propagated in the network will introduce a large sum of transmission. The communication of $G_{N}$ and $G_{U}$ is between the manager and every node in the network, but the fault tolerant mechanism of $G_{U}$ introduces less expected number of transmissions.

6. Conclusion

In this paper, we present the mechanism to support reliable graph routing in IWSNs. We summarize three communication types for industrial application and construct reliable graphs for different communication purposes. Our approach constructs the routing graph based on the link reliability and link correlation. When the link success probability is low, our approaches provide reliable communication with compromising network overhead. When the communication links are reliable, we pursue not the optimal reliability but less overhead. Indeed, the performance and overhead also rely on the network topology and the node density. Therefore, we should further improve and detect our approach.

In future work, our system will be deployed in real large-scale manufacturing factory and will face more challenges and problems in industrial environments. We will do the experiment about the packet reception correlation among neighbor nodes. Then we should look for more efficient algorithms to construct reliable graph and improve other network performances. As a future extension of this work we will focus on the data link layer communication schedule based on routing graphs for multihop transmission. We want to have a cross-layer approach where the network and MAC layer will work together to achieve end-to-end reliable and real-time communication.

Footnotes

Acknowledgments

This work was supported by the National Natural Science Foundation of China (Grant nos. 61201204 and 61271201), the Fundamental Research Funds for the Central Universities (Grant no. 2013YJS014), and the National Major Projects of China (Grant no. 2012ZX03005003).

References

Karnouskos

De Holanda

T. N.

Simulation of a smart grid city with software agents

Proceedings of the UKSim 3rd European Modelling Symposium on Computer Modelling and Simulation (EMS '09)

November 2009

IEEE

424 429

2-s2.0-77950986417

10.1109/EMS.2009.53

Gil-Castineira

Costa-Montenegro

Gonzalez-Castano

Lpez-Bravo

Ojala

Bose

Experiences inside the ubiquitous Oulu smart city

Computer 2011 44 6 48 55

2-s2.0-79959346147

10.1109/MC.2011.132

5765905

H. N.

Song

G. B.

Kim

J. T.

T. H.

Sensing methodologies and sensor networks for health monitoring of civil infrastructures

International Journal of Distributed Sensor Networks 2012 2012 2

358286

10.1155/2012/358286

Al-Hader

Rodzi

Sharif

A. R.

Ahmad

SOA of smart city geospatial management

Proceedings of the UKSim 3rd European Modelling Symposium on Computer Modelling and Simulation (EMS '09)

November 2009

IEEE

6 10

2-s2.0-77951007857

10.1109/EMS.2009.112

Yang

Honary

Smart sensor networks: theory and practice

International Journal of Distributed Sensor Networks 2012 2012 2

602893

10.1155/2012/602893

Commuri

Watfa

M. K.

Coverage strategies in wireless sensor networks

International Journal of Distributed Sensor Networks 2006 2 4 333 353

2-s2.0-35348872125

10.1080/15501320600719151

Kim

T. H.

Fang

W. C.

Ramos

Mohammed

Gervasi

Stoica

Ubiquitous sensor networks and its application

International Journal of Distributed Sensor Networks 2012 2012 3

310271

10.1155/2012/310271

Willig

Recent and emerging topics in wireless industrial communications: a selection

IEEE Transactions on Industrial Informatics 2008 4 2 102 124

2-s2.0-44249108577

Chen

Nixon

Mok

Wirelesshart: Real-Time Mesh Network for Industrial Automation 2010

New York, NY, USA

Springer

10.

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

2-s2.0-70349619163

10.1109/TIE.2009.2015754

11.

Koumpis

Hanna

Andersson

Johansson

A review and roadmap of wireless industrial control

The Industrial Wireless Book Email Newsletter 2006 4

GGH Marketing Communications

2009 Available lastactualization

12.

Song

Han

Mok

A. K.

Chen

Lucas

Nixon

Pratt

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

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

April 2008

IEEE

377 386

2-s2.0-51249117686

10.1109/RTAS.2008.15

13.

Willig

Matheus

Wolisz

Wireless technology in industrial networks

Proceedings of the IEEE 2005 93 6 1130 1151

2-s2.0-21644466923

10.1109/JPROC.2005.849717

14.

Wirelesshart

http://www.hartcomm.org

15.

Isa-100. 11a-2009 wireless systems for industrial automation: process control and related applications

http://www.isa.org/ISA100-11a

16.

Zhao

Yang

Qin

Zheng

Duan

Gidlund

Issues of routing protocol for wireless industrial sensor networks

Proceedings of the 38th Annual Conference on IEEE Industrial Electronics Society (IECON '12)

2012

IEEE

3225 3230

17.

Yang

Gidlund

Shen

Zhang

CCA-embedded tdma enabling acyclic traffic in industrial wireless sensor networks

Ad Hoc Networks 2013 11 3 1105 1121

18.

Lennvall

Svensson

Hekland

A comparison of wirelesshart and zigbee for industrial applications

Proceedings of the 7th IEEE International Workshop on Factory Communication Systems (WFCS '08)

May 2008

IEEE

85 88

2-s2.0-56349109631

10.1109/WFCS.2008.4638746

19.

Han

Zhu

Mok

A. K.

Chen

Nixon

Reliable and real-time communication in industrial wireless mesh networks

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

April 2011

IEEE

3 12

2-s2.0-79957611513

10.1109/RTAS.2011.9

20.

Zhao

Liang

Zhao

ELHFR: a graph routing in industrial wireless mesh network

Proceedings of the IEEE International Conference on Information and Automation (ICIA '09)

June 2009

IEEE

106 110

2-s2.0-70449686134

10.1109/ICINFA.2009.5204902

21.

Gao

Zhang

A reliable multipath routing strategy for wirelesshart mesh networks using subgraph routing?

Journal of Computational Information Systems 2013 9 5 2001 2008

22.

Banerjee

Misra

Minimum energy paths for reliable communication in multi-hop wireless networks

Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing

June 2002

ACM

146 156

2-s2.0-0242612035

23.

Heo

Hong

Cho

EARQ: energy aware routing for real-time and reliable communication in wireless industrial sensor networks

IEEE Transactions on Industrial Informatics 2009 5 1 3 11

2-s2.0-62449084821

10.1109/TII.2008.2011052

24.

Radi

Dezfouli

Bakar

K. A.

Lee

Multipath routing in wireless sensor networks: survey and research challenges

Sensors 2012 12 1 650 685

2-s2.0-84856296169

10.3390/s120100650

25.

Lee

S.-J.

Gerla

Split multipath routing with maximally disjoint paths in Ad hoc networks

Proceedings of the IEEE International Conference on Communications (ICC '01)

June 2000

IEEE

3201 3205

2-s2.0-0034844688

26.

Marina

M. K.

Das

S. R.

On-demand multipath distance vector routing in ad hoc networks

Proceedings of the International Conference on Network Protocols (ICNP '01)

November 2001

IEEE

14 23

2-s2.0-0035703920

27.

Ganesan

Govindan

Shenker

Estrin

Highly-resilient, energy-efficient multipath routing in wireless sensor networks

ACM SIGMOBILE Mobile Computing and Communications Review 2001 5 4 11 25

28.

Nasipuri

Das

S. R.

On-demand multipath routing for mobile ad hoc networks

Proceedings of the IEEE 8th International Conference on Computer Communications and Networks

1999

IEEE

64 70

29.

Nasipuri

Castañeda

Das

S. R.

Performance of multipath routing for on-demand protocols in mobile Ad Hoc networks

Mobile Networks and Applications 2001 6 4 339 349

2-s2.0-0035425905

10.1023/A:1011426611520

30.

Ishii

Exploiting backbone routing redundancy in industrial wireless systems

IEEE Transactions on Industrial Electronics 2009 56 10 4288 4295

2-s2.0-70349622743

10.1109/TIE.2009.2021176

31.

Ieee 802. 15. 4 wpan task group, http://www.ieee802.org/15/pub/TG4.html

32.

Gomez

Campbell

A. T.

Naghshineh

Bisdikian

PARO: supporting dynamic power controlled routing in wireless ad hoc networks

Wireless Networks 2003 9 5 443 460

2-s2.0-0042976448

10.1023/A:1024636132348

33.

Doshi

Bhandare

Brown

T. X.

An on-demand minimum energy routing protocol for a wireless ad hoc network

ACM SIGMOBILE Mobile Computing and Communications Review 2002 6 3 50 66

34.

Basalamah

Kim

S. M.

Guo

Tobe

Link correlation aware opportunistic routing

Proceedings of the 31st Annual IEEE International Conference on Computer Communications (INFOCOM '12)

2012

IEEE

3036 3040

35.

Zhu

Zhong

Zhang

Z. L.

Exploring link correlation for efficient flooding in wireless sensor networks

Proceedings of the 7th USENIX Symposium on Networked Systems Design and Implementation (NSDI '10)

49 64

36.

Srinivasan

Jain

Choi

Azim

Kim

E. S.

Levis

Krishnamachari

The κ factor: inferring protocol performance using inter-link reception correlation

Proceedings of the 16th Annual Conference on Mobile Computing and Networking (MobiCom '10)

September 2010

ACM

317 328

2-s2.0-78649300366

10.1145/1859995.1860032

37.

Alwan

Agarwal

A survey on fault tolerant routing techniques in wireless sensor networks

Proceedings of the 3rd International Conference on Sensor Technologies and Applications (SENSORCOMM '09)

June 2009

IEEE

366 371

2-s2.0-70449500739

10.1109/SENSORCOMM.2009.62

Reliable Graph Routing in Industrial Wireless Sensor Networks

Abstract

1. Introduction

2. Related Works

2.1. Reliable Routing in Wireless Sensor Networks

2.2. Source Routing and Graph Routing

3. Industrial Wireless Sensor Networks Architecture

4. Centralized Reliable Graph Routing

4.1. Communication Types

4.1.1. Broadcast

4.1.2. Uplink

4.1.3. Downlink

4.2. Notations

4.3. Link Correlation

4.4. Fault Tolerant and Reliability Attributes

4.5. Process to Construct Graph

4.6. Reliable Broadcast Graph

Algorithm 1: Constructing reliable broadcast graph.

4.7. Reliable Uplink Graph

Algorithm 2: Constructing reliable uplink graph.

4.8. Reliable Downlink Graph

Algorithm 3: Constructing reliable downlink graph.

4.9. The Percentage of Reliable Nodes and the Link Quality

4.10. Loop Avoidance

5. Performance Evaluation

5.1. Simulation Parameters

5.2. Performance of Graph Routing

6. Conclusion

Footnotes

Acknowledgments

References