Sage Journals: Discover world-class research

Abstract

The industrial wireless network (IWN) is an important part of industrial CPS, which must address the key issue of reliable and real-time communication as well as the desired network lifetime. The nodes of IWN are usually fixed on the devices for better monitoring of the state information of the equipment and environment, while the relay node placement plays a significant role on network performance guarantee. This paper proposes an Integer Linear Program (ILP) placement strategy to meet the fault tolerance and survivability requirement. In addition, an edge coloring algorithm is proposed to solve the conflict of TDMA communication, which improves paralleled and real-time communication performance. Simulation results show that this placement strategy not only meets the requirements of robust communication and survivability, but also enhances real-time communication of IWN.

1. Introduction

1.1. Introduction of CPS

A cyber-physical system (CPS) is a system of collaborating computational elements controlling physical entities. Today, a precursor generation of cyber-physical systems can be found in areas as diverse as aerospace, automotive, chemical processes, civil infrastructure, energy, healthcare, manufacturing, transportation, entertainment, and consumer appliances. CPS will play a great role, especially in the industrial world. This generation is often referred to as embedded systems. In embedded systems, the emphasis tends to be more on the computational elements and less on an intense link between the computational and physical elements. The CPS has been studied by many foreign research institutions. The US National Science Foundation (NSF) has identified cyber-physical systems as a key area of research [1]. Starting in late 2006, the NSF and other United States federal agencies sponsored several workshops on cyber-physical systems [2–4]. Some scholars have studied CPS in China, and the representative papers can be seen in [5–7]. As the special WSN in the industry, IWN can be used as an important technology of CPS components. It has attracted more and more attention.

1.2. Industrial Wireless Network

IWN is specially designed for harsh industrial environment application, which has better network performance with respect to anti-interference, robustness, real-time, and security through the use of mesh network, spread spectrum, frequency hopping, and the multihop technique. The concept of IWN was firstly proposed by the U.S. Department of Energy (DOE), and it transformed other research which focuses of industrial automatic measurement and control field after the industrial field bus [8–10]. ISA SP100 [11], WirelessHART [12–15], and WIA-PA [16] are three IWN specifications which have some common features such as short-range multihop wireless communication, being battery-powered, and a TDMA scheme [17]. Although there are some distinctions on node definition for these three specifications, all the nodes can be divided into sensor node and relay node logically. Relay node must be scheduled in specified time slots to fulfill correspondent communication task.

In comparison to the random placement of a WSN senor node, the positioning of an IWN node is relatively fixed. As usual, the IWN node can be divided into sink node, relay node, and sensor node. There is little research on the sink node placement because it is usually fixed; sensor node placement primarily considers the probability-of-detection, data fusion, and accuracy [18, 19]. Tremendous attention has been paid to address the issue of relay node placement on the grounds that a relay node can be deployed flexibly; the relay node acts as a bridge between the sensor node and sink nodes; relay node placement strategy is distinct for different application requirements. Although we can use the AGV mobile robot or person with handheld devices to collect data, there is usually a limited number of mobile robots. People cannot use handheld mobile acquisition equipment to collect information in the harsh environment. The AGV mobile robot is not able to work in the limited space environment. In addition, the above two ways have a higher cost. So we hope that WSN can bear the bulk of the work, only allowing man or AGV to carry out regular inspections and verifications. A better node deployment strategy for the relay node can also provide fine-grained navigation for the AGV or mobile robot. By combining the two ways using IWN and AGV, it can be easier to complete the construction of an industrial intelligent environment. Therefore, we say that the deployment of the relay node is essential and important for research.

1.3. Related Work on Relay Node Placement

Hou et al. [20] extended the network lifetime by designing an heuristic algorithm (SPINDS) to solve optimized RN placement problem; experiments validated the effectiveness of this algorithm. Chen et al. [21] demonstrated that redundant fault-tolerant techniques improved query reliability and network lifetime, and it could be referred in RN placement. While Hou et al. [20] aimed to extend the network lifetime, but this work does not consider the reliable communication issue in hash industrial environments.

Wang et al. [22] tended to solve the issue of the minimum network cost relay node placement under the constraint of network lifetime and connectivity. This work firstly solved the minimum set cover problem without considering energy consumption. They also proposed three heuristic algorithms to solve the energy consumption constraint. Liu et al. [23] aimed at network coverage and connectivity based on transportation industry, and this work proposed a heuristic and network flow algorithm to deal with the relay node placement problem. Wang et al. [22] and Liu et al. [23] were typical relayed node placement research under constraint of network coverage, connectivity, and lifetime, but they did not consider fault tolerant issue in hash industry environment.

Bredin et al. [24] established k-connectivity network to improve fault tolerance by ${RN}_{s}$ placement; the greedy and distributed algorithms were proposed and their performance had been proven by simulations. Han et al. [25] focused on adding additional ${RN}_{s}$ to improve fault tolerance, and a heuristic algorithm was proposed and validated by experiments. Liu et al. [26] and Liu et al. [27] addressed the issue of the ${RN}_{s}$ placement for a two-tier sensor network under a simply connected situation or a two-connected situation. Approximation algorithms had been proposed for these two situations. The time complexity was $6 + ε$ , $24 + ε$ , or $6 / T + 12 + ε$ . Hao et al. [28] proposed a fault tolerant placement solution under the minimum ${RN}_{s}$ constraints, which could insure that every sensor node can be connected with at least two ${RN}_{s}$ and two-connected among all the ${RN}_{s}$ , and its time complexity is $O (D \log_{n})$ , where n was the number of sensor nodes and D was the number of potential RN positions. Kashyap et al. [29] proposed an ${RN}_{s}$ placement algorithm targeting two edges and the vertex connectivity in d-dimensional Euclidean space, and this work also considered the geometric disorder. The minimum spanning tree was deployed. Tang et al. [30] also proposed approximation algorithms for a simply connected network and a two-connected network. Simulations of Tang et al. [30] showed similar results with Liu et al. [26] and Liu et al. [27]. Zhang et al. [31] concluded the existing ${RN}_{s}$ placement algorithms, and this work proposed a fault tolerant placement algorithm based on the steiner graph. This algorithm had a $O (1)$ time complexity. Zhang et al. [32] addressed the nuclear power plant problem, and it proposed a three-step application oriented solution: the constructing redundant connected graph, the optimization through genetic algorithm, and the generating position of relay nodes. Experimental results showed that this solution had a 3D obstacles avoidance with better network fault tolerance and the optimized placement position feature. Reference [24–31] aimed to establish fault tolerant sensor network, and they proposed profound theories and algorithms based on Steiner and other graphic theories. But these researches did not consider the industrial environment in practice; for example, the influence of sink node position, network delay, and overall energy consumption was not considered.

Bari et al. [33] focused on $k_{s}$ coverage and $k_{r}$ connectivity of the ${RN}_{s}$ placement problem. It presented the integer linear programming method and it also showed the effectiveness of the algorithm. Sitanayah et al. [34] gave a GRASTP-ARP centralized placement algorithm, which ensured $k - 1$ disjoint paths. Bhuiyan et al. [35] aimed at building monitoring sensor network and analyzed its special issues such as communication unstability, unreachability, and ambient noise. Then an ${RN}_{s}$ placement repairing algorithm called FTSHM was proposed, and it improved fault tolerance while considering network lifetime and connectivity. Reference [33–35] sought to construct a fault tolerant sensor network, and all of them focused on the practical testing experiments and techniques which were very useful.

Bari et al. [36] presented the formal description of ILP, and this work had improved the network fault tolerance by ${RN}_{s}$ placement. This work also enhances the network lifetime by routing load balance. Z. Wang and Q. Wang [37] added constraints of irreversible communication path and communication capacity into the existing ${RN}_{s}$ placement model, and this work proposed a new evaluation criterion-minimum network distance factor. Experimental results showed its advantage on the network energy consumption. Wang et al. [38] proposed an ${RN}_{s}$ placement algorithm to insure fault tolerance under multiconstraints; similar to Z. Wang and Q. Wang [37], this work also presented a new evaluation criterion and its algorithm to improve the network energy consumption. Al-Turjman et al. [39] constructed a simple 3D cube model, and this work proposed an integer linear programming under the constraints of fault tolerance and energy consumption, and it also proved that this algorithm can improve the network lifetime effectively. Yang et al. [40] and Chaudhry et al. [41] proposed a network base station placement and a fault tolerant routing strategy. This solution mainly sought to improve the network robustness and lifetime. Comparing with the solution which only considered connectivity, the experimental results of Yang et al. [40] and Chaudhry et al. [41] showed that the lifetime of this solution did not be reduced significantly. Michael and Pinciu [42] concluded the techniques of sensor node coverage based on the artist gallery problem and the voronoi graphic, and this work proposed an placement strategy which could ensure network coverage of several positions; this result guaranteed network fault tolerance, and this work reduced overall network energy consumption. Reference [36–42] considered network fault tolerance, routing load balance, communication capacity, and network coverage; these integrated research methods were more practical. Such fault tolerant and energy consumption research methods were also applicable to IWN research; however, there was no placement research of real time performance on IWN.

Sun et al. [43] addressed an ${RN}_{s}$ placement issue of IWN. This work firstly analyzed the reason of industrial environment communication failure and explained that fault tolerance was a key issue in IWN applications. In this work, they proposed an integrated optimum strategy based on genetic algorithm and simulated annealing algorithm to realize the goal of two-coverage of sensor nodes and two-connected among ${RN}_{s}$ . There could be a lot of future work based on this paper as it did not consider many other practical constraints.

1.4. Research Feature and Paper Arrangement

Although spread spectrum, frequency hopping, and the TDMA technique improves IWN reliability to some degree, this network still has some deficiencies such as being battery powered and short distance communication. Moreover, there are electromagnetic interference, multipath effects, and other wireless signal interference, all of which make it easier for communication to fail. Therefore, this paper focuses on improving the fault tolerance ability and network lifetime of IWN. In addition, IWN also needs to focus on real time communication because monitoring information should be delivered within the required time [44, 45]. However, when network scale increases, the communication resource utilization of TDMA technique decreases greatly, which will affect real-time communication. This paper also seeks to enhance real-time communication through paralleled communication.

The main contribution of this paper is (i) presenting a comprehensive constraint and formulation about fault tolerance, energy consumption, and real-time issues, (ii) proposing a heuristic algorithm to calculate paralleled communication resources according to objective function, (iii) simulation experiments to show the influence of other parameters on real-time performance and validate that the proposed relay node placement strategy can improve real time performance while guaranteeing fault tolerance and energy limitation, which is firstly proposed in related research.

2. Network Model and Formulation

2.1. Network Model

This paper considers two-tiered IWN model, in which lower-tiered is sensor nodes distributed in sensing area or above sensing object to gather required data [18]. It assumes the sensor nodes have been deployed in predetermined position, and the potential position of relay node has also been determined using grid met $1 \leq i \leq x$ . Let S be the set of sensor nodes, and let R be the set of potential ${RN}_{s}$ positions, $| S | = x$ , and $| R | = y$ . For each sensor node i, $1 \leq i \leq x$ ; for each potential ${RN}_{s}$ position j, $x + 1 \leq j \leq x + y$ ; the label of base station is $x + y + 1$ . $p_{c}$ -coverage means that every senor node can transmit with at less $p_{c} {RN}_{s}$ . $q_{c}$ -connectivity means that every RN is connected with at least $q_{c} {RN}_{s}$ .

The objective is to obtain the position of relay node to achieve minimum edge coloring under the following requirement: (i) the relay node has fault tolerance coverage to sensor node, and the communication among relay nodes is still fault tolerant; (ii) meet the requirement of network lifetime and energy consumption; (iii) the degree of node is balanced to improve paralleled communication performance.

Since there is data collection period of IWN (in one period all the data collected from sensor node must be transmitted to base station), another two objectives of this paper are to shorten the period time and to reduce the communication resource usage in one period.

This RN's placement strategy is specially designed for the IWN of industrial application, where the location of node does not change frequently and the network control information is distributed by the network manager through message advertisement; thus this strategy is not suitable for such application whose network topology changes frequently.

2.2. Parameter Definition

(1)

The following notation is the input constant in ILP formulation:

(a)

x: the number of sensor nodes, and every sensor node has an index $i (1 \leq i \leq x)$ ;

(b)

y: the number of potential RN positions with a unique index for each position j, $x + 1 \leq j \leq x + y$ ;

(c)

$x + y + 1$ : the index of base station;

(d)

$r_{\max}$ : the communication distance of sensor node;

(e)

$d_{\max}$ : the communication distance of ${RN}_{s}$ ;

(f)

$d_{i, j}$ : the Euclidean distance between node i and node j;

(g)

$p_{c}$ : the minimum number of ${RN}_{s}$ covering every single sensor node;

(h)

$q_{c}$ : the minimum number of ${RN}_{s}$ which can be reached by node j ( $d_{j, n + m + 1} > d_{\max}$ ) to forward data to base station;

(i)

$α_{1} (α_{2})$ : energy coefficient for transmission (reception);

(j)

β: energy coefficient for amplifiers;

(k)

s: path loss rate;

(l)

$b_{i}$ : the number of bits that need to sending by node i;

(m)

D: a large constant, $D \geq \sum_{i = 1}^{x} b_{i}$ ;

(n)

the maximum allowable energy consumption of each RN in one period.

(2)

The following notation is the input variables:

(o)

$A_{i, j}$ : binary variable. If node i chooses ${RN}_{j}$ as back-up next hop, $A_{i, j} = 1$ ; else $A_{i, j} = 0$ ;

(p)

$B_{i, j}$ : binary variable. If node i chooses ${RN}_{j}$ as primary next hop, $B_{i, j} = 1$ ; else $B_{i, j} = 0$ ;

(q)

$Y_{j}$ : binary variable. $Y_{j} = 1$ means that if RN is placed in position j, it can be reached by sensor node or other RN;

(r)

$C_{j}$ : the number of ${RN}_{s}$ which can be used by ${RN}_{j}$ to forward data to base station;

(s)

the number of bits forwarded by ${RN}_{j}$ in one period.

2.3. ILP Formulation

In this section, ILP formulation is proposed, which should guarantee that the ${RN}_{s}$ is $p_{c}$ -coverage to sensor nodes and $q_{c}$ -connectivity among each other. In addition, the level of conflict edge coloring in the network topology should be as little as possible to improve the real-time performance under the constraints of fault tolerance, energy consumption, and node degree.

The objective function is as follows:

\begin{matrix} Minimize C_{t}, \end{matrix}

(1)

subject to

(1)

transmission range constraints

\begin{matrix} d_{j, k} > d_{\max} ⟹ e_{j, k} = 0, \forall j, k, j \neq x + y + 1, \end{matrix}

(2)

\begin{matrix} B_{i, j} \cup A_{i, j} = 1 ⟹ d_{i, j} \leq r_{\max}, \forall i : i \in S, \forall j : j \in R; \end{matrix}

(3)

(2)

fault tolerance constraints

\begin{matrix} \exists! B_{i, j} = 1 (j \in R), \forall i : i \in S, \end{matrix}

(4)

\begin{matrix} \sum_{j = x + 1}^{x + y} ‍ A_{i, j} + 1 \geq p_{c}, \forall i : i \in S, \end{matrix}

(5)

\begin{matrix} C_{j} = \sum_{w : (w \in R) \cap (d_{j, w} \leq d_{\max}) \cap (d_{w, x + y + 1} < d_{j, x + y + 1})} ‍ Y_{w}, \end{matrix}

(6)

\begin{matrix} Y_{j} = 1 ⟹ C_{j} \geq q_{c} \forall j : j \in R \cap (d_{j, x + y + 1} \geq d_{\max}); \end{matrix}

(7)

(3)

energy consumption constraints

\begin{array}{l} w_{j} = \sum_{i} ‍ b_{i} B_{i, j} \forall i, j : i \in R, j \in S, \end{array}

(8)

\begin{array}{l} \sum_{k = x + 1}^{x + y + 1} ‍ e_{j, k} - \sum_{k = x + 1}^{x + y} ‍ e_{k, j} = w_{j}, \forall j : j \in S, \end{array}

(9)

\begin{array}{l} T_{j} = \sum_{k = x + 1}^{x + y + 1} ‍ e_{j, k}, \forall j : j \in S, \end{array}

(10)

\begin{array}{l} G_{j} = β \sum_{k = x + 1}^{x + y + 1} ‍ e_{j, k} {(d_{j, k})}^{s}, \forall j : j \in S, \end{array}

(11)

\begin{array}{l} R_{j} = \sum_{k = x + 1}^{x + y} e_{k, j}, \forall j, j \in S \cup j = x + y + 1, \end{array}

(12)

\begin{array}{l} E_{j} = α_{1} R_{j} + α_{2} T_{j} + α_{1} w_{j} + G_{j} \\ \leq E_{\max}, \forall j, j \in S \cup j = x + y + 1; \end{array}

(13)

(4)

real-time constraints

\begin{matrix} a \leq d_{j} \leq b, \end{matrix}

(14)

\begin{matrix} σ = \sqrt{\frac{1}{N} \sum_{j = 1}^{N} ‍ {(d_{j} - u)}^{2}} \leq T . \end{matrix}

(15)

2.4. ILP Formal Specification

Formula (1) is the objective function, which must achieve minimum conflict edge coloring under certain constraints as follows. The transmission and coverage constraints are in formulae (2) and (3). Formula (2) means that the transmission range is longer than Euclidean distance among ${RN}_{s}$ , which is the necessary condition of connectivity. There will be no data flow if the distance between the two ${RN}_{s}$ is longer than $d_{\max}$ . Formula (3) means that if the sensor node chooses an RN as primary next hop or backup next hop, the distance between them is shorter than their Euclidean distance.

Network coverage, connectivity, and fault tolerance between ${RN}_{s}$ are in formulae (4), (5), (6), and (7). Formula (4) means there is one, and only one, RN to be primary next hop for each sensor node. Formula (5) means the number of ${RN}_{s}$ for each sensor node to connect must be at least $p_{c} - 1$ . Formulae (6) and (7) mean the ${RN}_{s}$ used by node j to forward data to the base station must meet transmission range, direction, and $q_{c}$ connectivity requirements.

Energy consumption constraints are in formulae (8), (9), (10), (11), (12), and (13), which focus on limiting energy use in one period. Formula (8) means the total number of bits generated by sensors' nodes within the transmission range of ${RN}_{j}$ . Formula (9) shows the relation among data flow from j to k, data flow from k to j, and the data bits generated by related sensor nodes. Formula (10) is the total number of bits forwarded by ${RN}_{j}$ . Formula (11) means the amplifier energy dissipated by ${RN}_{j}$ . Formula (12) means the total number of bits that ${RN}_{j}$ received from other ${RN}_{s}$ . Formula (13) means the total energy consumption of ${RN}_{j}$ and its maximum energy consumption.

Node degree constraints are in formulae (14) and (15), which seek to limit the number of neighbors to balanced level. Parameter a, b, and T can be adjusted according to the practical situation.

3. Solution

3.1. Solution Explanation

The solution is divided into two parts. The first part is to calculate all the topologies that meet fault-tolerance and energy consumption requirements; the second part is to find a placement topology with the lowest level of conflict edge coloring from the result in the first phase.

The algorithm running time depends on the number of binary variables, including $A_{i, j}$ , $B_{i, j}$ , and $Y_{j}$ , whose value does not relay to the number of sensor nodes but relates to the potential number of ${RN}_{s}$ . It can be inferred from the formula that the potential number of ${RN}_{s}$ is large, which will make the running time of the algorithm long; while in practical situations, most of the binary variables of ${RN}_{s}$ are zero due to the limitation of transmission range. Thus the calculation is simplified in the first phase. In the second phase, the core idea is to conduct vertex coloring for several network topologies. To improve running efficiency, a heuristic algorithm is used to avoid high time complexity in overall optimization.

3.2. Calculating the Fewest Number of Conflict Edge Coloring

There are two sorts of communication conflicts in IWN, which are direct conflict and indirect conflict. For direct conflict there are three kinds; the first is that a node cannot receive and send data simultaneously; the second is that a node cannot receive data from two neighbors simultaneously; the third is that a node cannot send data to two neighbors simultaneously. To avoid direct conflict, the algorithm must allocate different communication resources for such conflict links. For indirect conflict due to channel sharing, the solution must meet some interference constraint model; the node will interfere with all its neighbors when it is sending data and this situation must be considered in the communication resource scheduling.

In IWN, the valid communication resources are restricted; thus if using a traditional communication resources scheduling technique, the above conflicts will make network channel utilization low, which will reduce the network throughput, increase transmission delay (real-time performance), and have a negative impact on large network scale applications. Therefore, if taking advantage of short distance wireless communication, paralleled communication can be used to schedule same communication resources to such links that do not conflict with each other. Then the network throughput and real time performance can be improved.

We transform the original graph into a link conflict graph according to the communication conflict principle. The conflict edges in the original graph become vertexes in the link conflict graph, and then vertex coloring is conducted in the link conflict graph to obtain the lowest coloring level. There are many vertex coloring algorithms: the backtrack, branch bounding method is accurate but high in time complexity; the greedy algorithm is low in running time but the results are normal; the intelligent algorithms like neural network and genetic and ant-colony optimization; the DNA algorithm can obtain preferable results, but the algorithm itself is very complex, the running process is randomly, and the running time is long. In this paper, a maximum degree first heuristic algorithm is proposed on the basis of the Welsh Powell algorithm. The following are some explanations and algorithm steps.

For a graph ( $G = (V, E)$ ), mapping ( $π : V \to \{1,2, \dots, k\}$ ) is a k-vertex coloring and $\{1,2, \dots, k\}$ is the set of colors; for any two neighbor nodes μ and υ, if $π (μ) \neq π (υ)$ , the coloring is normal. The minimum value of normal k-vertex coloring is called color number $(χ (G)), Δ (G)$ , which means the maximum degree of nodes. χ and Δ are simple notation.

Vertex coloring corresponds to vertex set partition. If π is $G k$ -vertex coloring of $G (π (V (G)) = \{1,2, \dots, k\})$ , then $\{π^{- 1} (1), π^{- 1} (2), \dots, π^{- 1} (k)\}$ is a partition of $V (G)$ . If π has normal coloring, then every $π^{- 1} (i)$ is vertex independent set of G. And if $\{V_{1}, V_{2}, \dots, V_{k}\}$ is a partition of $V (G)$ , the partition can derive a k-coloring $π (V_{i} = π^{- 1} (i))$ , and we called $π^{- 1} (i)$ to be an color group of π. If $\{V_{1}, V_{2}, \dots, V_{k}\}$ is a partition of $V (G)$ and $V_{i}$ are all independent set, then this partition is called color partition.

Theorem 1.

For any G, $χ \leq Δ + 1$ is right.

Demonstration. Mathematical induction is used for vertex number n of G, when $n = 1$ , $χ = 1, Δ \geq 0$ , and $χ \leq Δ + 1$ is right. For $n \geq 2$ , $u \in V (G)$ , suppose $G^{'} = G - u$ ; according to induction hypothesis $χ (G^{'}) \leq Δ (G^{'}) + 1$ , then there exists $Δ (G^{'}) + 1$ color π of $G^{'}$ . Because of $Δ (G^{'}) \leq Δ (G)$ , π is also $Δ (G^{'}) + 1$ coloring of $G^{'}$ . Assuming $d_{G} (u) = k$ , the neighbor vertex of u is $V_{1}, V_{2}, \dots, V_{k}$ , due to $| \{π (v_{1}), \dots, π (v_{k})\} | \leq k < Δ (G) + 1$ ; there exit $j \in \{1,2, \dots, Δ (G) + 1\}$ , $j \notin \{π (v_{1}), \dots, π (v_{k})\}$ ; let $π (u) = j$ , and then π is a $Δ (G) + 1$ coloring of G; thus the theorem is proved right and an upper bound is found, which can be used as initial color set of our algorithm.

Since the solution seeks to obtain the lowest level of vertex colors, firstly the heuristic algorithm uses one color for as many vertexes as possible; obviously these vertexes must not be mutual neighbors. It is the same with the following process. The algorithms first find the maximal independent set, and the entire vertex in this set is given the same color. Then the second maximal independent set till the entire vertex is given a color. Since there is no unique result for this method, we must try to find a better result, which is an NP complete problem. However, we can infer that the degree of one vertex is larger, its influence to other vertexes is greater. Thus this algorithm gives higher priority for such a vertex with a large degree, which can reduce the influence. This is the idea of Welsh Powell algorithm. Figure 1 outlines our algorithm steps.

Figure 1

Coloring algorithm flow chart.

4. Simulation Experiment and Result

In simulation, $r_{\max} = 40 m$ and $d_{\max} = 80 m$ . Assume that the network communication is a cosmic model, and energy model is in Bari et al. [36]. $α_{1}$ = $α_{2}$ = 50 nJ/bit, β = 100 pJ/bit/ $m^{2}$ , $s = 2$ , and initial energy of every RN is 5 J.

In order to focus on the key point the distribution of relay nodes, we do not conduct practical sensor placement like in Zhang et al. [18], but we use random placement strategy. The whole network area includes 3 different sizes, $80 * 80 m^{2}$ , $90 * 90 m^{2}$ , and $100 * 100 m^{2}$ , and the grid method is used to obtain the potential positions of ${RN}_{s}$ .

The simulation programs run on a desktop with Intel Core i3 3.30 GHz CPU and 4 G RAM, and the experiment environment is Matlab R2010B. The main goal is to find the lowest level of edge coloring ${RN}_{s}$ placement topology; in a normal case, execution time of the simulation is less than 20 minutes, when the value of main inputs reach maximum; the whole program will take over 35 minutes to finish.

4.1. Network Performance without Real-Time Constraints or Energy Constraints

( 1) Single-Connected Topology ( $p_{c} = q_{c} = 1$ ) Only. When considering connection only, the network real-time performances are shown in Figures 2 and 3. Figure 2 illustrates the relationship between real-time performance and network area size, under the same problem size (number of sensors). According to the experiment results, the real-time performance enhances with the gradual expansion of the network area. Figure 3 shows the effects of different numbers of sensors on the network real-time performance in the same area. As Figure 3 has shown, the more the sensors exist in a unit area, the worse the real-time performance of the network topology is.

Figure 2

Comparison of chromatic number of 40-sensor topology under different relay node schemes, when $p_{c} = q_{c} = 1$ .

Figure 3

Comparison of chromatic number of different topologies under 81-Grid relay node scheme, when $p_{c} = q_{c} = 1$ .

( 2) Multiple-Connected Topology ( $p_{c} = q_{c} = 2$ ) Only. Fault-tolerance constraints find a redundant backup path which has no intersections with the main path for both sensor nodes and relay nodes. Thus the self-organizing topology gains multiple connections and the network robustness improves. In Figure 4, the network real-time performance improves while the area size expands. Figure 5 shows that real-time performance gets worse when more sensors are distributed in the same size area.

Figure 4

Comparison of chromatic number of 40-sensor topology under different relay node schemes, when $p_{c} = q_{c} = 2$ .

Figure 5

Comparison of chromatic number of different topologies under 81-Grid relay node scheme, when $p_{c} = q_{c} = 2$ .

Comparing Figure 2 with Figures 4, 3, and 5, respectively, the following conclusions are made: (i) no matter if the topology is single-connected or multiple-connected, the network real-time performances have almost similar trends of change under same effects (different number of sensors or different size of network area); (ii) the real-time performance of a multiple-connected topology is much worse than the performance of a single-connected topology, since there are no constraints to control the multitude of additional redundant backup paths; therefore the probability of collisions in the network raises.

4.2. Network Performance without Real-Time Constraints but Energy Constraints

The strategy of energy constraints is to limit the maximum energy cost per round of nodes to prevent the early appearance of dead nodes. In this experiment, set-up three, different levels of energy constraints are used, RE-Level 1 (Restricted Energy, Level 1) is the most relaxed with $E_{\max} = 2.6 * 1 0^{- 4} nJ$ , and Level 3 is the most constrained with $E_{\max} = 2.0 * 1 0^{- 4} nJ$ .

Figures 6 and 7 show the network real-time performances of single-connected topology and multiple-connected topology, respectively, when energy constraints are included. Contrast the chromatic numbers of topologies which have the same number of sensors and the same size of network area but different RE-Levels; the real-time performances show almost no change. This means that energy constraints alone cannot improve the real-time performance of a network.

Figure 6

Comparison of chromatic number of different topologies with energy constraints under 81-Grid relay node scheme, when $p_{c} = q_{c} = 1$ .

Figure 7

Comparison of chromatic number of different topologies with energy constraints under 81-Grid relay node scheme, when $p_{c} = q_{c} = 2$ .

4.3. Network Performance with Both Real-Time Constraints and Energy Constraints

Real-time constraints will limit the degree of each node and the standard deviation of the degrees of all the nodes in a network. Network topology can distribute all the data flows as equally as possible with real-time constraints, so both lifetime and real-time performance of the network will improve. Here, besides some real-time constraints, fault-tolerance ( $p_{c} = q_{c} = 1$ ) and energy constraints ( $E_{\max} = 2.0 * 1 0^{- 4} nJ$ ) are included as well in the topology.

According to formulae (14) and (15), node degree $d_{j}$ will be constrained by both a and b, and standard deviation of node degrees will be constrained by T. Three different levels of real-time constraints are used in this experiment. For $d_{j}$ , the point is to control the upper limit value b, RD-Level 1 (Restricted Degree-Level 1) is the most relaxed with $b = 6$ , and RD-Level 3 is the most constrained with $b = 4$ , the variale a, which has a default value of 2 represents lower limit of $D_{j}$ ; for real-time altering in self-organizing proved difficult and ineffient, when default a cannot satisfy the requirement, the proposed algorithm will automatically alter the value of a to adjust dynamic self-organizing topology. The reference value of T is given in formula (15), and the actual T value may have a slight deviation based on a given network.

The effects of $d_{j}$ on network real-time performance are shown in Figures 8 and 9. From these two figures, the results indicate that the real-time performances obviously improve through $d_{j}$ , and the improvements increase with higher RD-Level. Figures 10 and 11 show that, using the proposed approach, the network lifetimes can be significantly improved, especially when T (restricted T, indicated by “RT-Level” in Figures 10 and 11) is more constrained.

Figure 8

Comparison of chromatic number of different topologies with energy constraints and real-time constraints under 81-Grid relay node scheme, when $p_{c} = q_{c} = 2$ .

Figure 9

Comparison of chromatic number of 40-sensor topology with energy constraints and real-time constraints under different relay node schemes, when $p_{c} = q_{c} = 2$ .

Figure 10

Comparison of lifetime of different topologies with energy constraints and real-time constraints under 81-Grid relay node scheme, when $p_{c} = q_{c} = 2$ .

Figure 11

Comparison of lifetime of 40-sensor topology with energy constraints and real-time constraints under different relay node schemes, when $p_{c} = q_{c} = 2$ .

Figures 12 and 13 compare the number of relay nodes required by the proposed approach under different real-time constraint levels. It can be seen from these two figures that, on the whole, the number of relay nodes required is stead, and increases very slightly when the real-time constraint level raises. Comparing Figures 8 to 13 comprehensively, the results indicate that the proposed approach improves the network performances significantly with very slight costs (number of relay nodes required).

Figure 12

Comparison of number of relay nodes required of different topologies with energy constraints and real-time constraints under 81-Grid relay node schemes, when $p_{c} = q_{c} = 2$ .

Figure 13

Comparison of number of relay nodes required of 40-sensor topology with energy constraints and real-time constraints under different relay node schemes, when $p_{c} = q_{c} = 2$ .

Figures 14 and 15 show the performance comparisons for the following cases: (i) ILP with no constraints (the left-most bar in each group, indicated by “ILP-ALL” [36]), (ii) ILP with fault-tolerance (the second bar from the left in each group, indicated by “ILP-RED” [36]), (iii) ILP based approach with fault-tolerance and some energy constraints (the third bar in each group, indicated by “ILP-Bari” [36]), and (iv) an approach with some real-time constraints based on (iii) (the right-most bar, indicated by “ILP-ZH”). Figure 14 compares the number of relay nodes required for different approaches and shows the results of real-time performance comparison.

Figure 14

Comparison of number of relay nodes required by different approaches.

Figure 15

Comparison of chromatic number under different approaches.

As shown in Figure 14, ILP-ALL requires the least number of relay nodes for all networks. This is expected, because ILP-ALL always generates a solution with the greedy algorithm. ILP-RED requires the most relay nodes, since fault-tolerance is considered but without other constraints, and the number of paths will simply be double in the network. As energy constraints are included, the ILP-Bari requires more relay nodes than ILP-ALL and less nodes than ILP-RED.

The main idea of the real-time constraint is to balance the data flows and energy costs in the whole topology; thereupon collisions and the lifetime of the network will be improved. In such cases, the number of required relay nodes obtained by the proposed approach may be higher than some other approaches (this is shown in Figure 14). However, when incorporating Figure 15 with Figure 14, the results illustrate that the number of required relay nodes is an inevitable cost to improve the whole performance of the network. The chromatic number of the proposed approaches is obviously less than other approaches (sometimes the ILP-ALL could also obtain the least chromatic number but the whole performance cannot reach the proposed approach, e.g., lifetime), which means collisions in the network are definitely controlled. This proves that industrial WSN could achieve a link fault-tolerance, node energy constraints, and preferable real-time performance within the proposed approach.

5. Conclusion

In IWN, except for fault tolerance and energy consumption constraints, real time performance is also important but is easily ignored. Since the position of IWN nodes is usually fixed in reality, the network real time performance is also determined after topology placement. Thus this paper considers fault tolerance, energy consumption, and real time performance of IWN and presents a formal description of the problem of ${RN}_{s}$ placement. For fault tolerance, we consider $p_{c}$ -coverage and $q_{c}$ -connectivity of ${RN}_{s}$ ; for energy consumption, we consider maximum energy constraints in one period for every node, and then a network conflict edge coloring algorithm based on the Welsh-Power algorithm is proposed. Experiment results show that this placement strategy can obtain better paralleled utilization of communication, and it also meets fault tolerance and energy consumption constraints. Thus the network real time performance is improved. Since our current research needs to consider the application compatibility of network topology, we mainly seek to improve real time performance. In the future, there are two aspects to study further. One is the realization of relay node optimal deployment of the combination of the AGV and IWN with limited numbers. The other is the fine-grained navigation for AGV supported by the IWN monitoring the status of the equipment and environment.

Footnotes

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant no. 61202042), China-Canada Joint Research Project (Grant no. 2009DFA12100), the Fundamental Research Funds for the Central Universities (Grant nos. SWU113066, XDJK2015C023, and XDJK2012C019), and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry of China.

References

Wolf

News briefs

IEEE Computer 2007 40 11 104 105

10.1109/MC.2007.404

New Research Directions for Future Cyber-Physical Energy Systems

2009

Bridging the Cyber, Physical, and Social Worlds

2011

NIST Foundations for Innovation in Cyber-Physical Systems Workshop, 2012

Wan

Yan

Suo

Advances in cyber-physical systems research

KSII Transactions on Internet and Information Systems 2011 5 11 1891 1908

2-s2.0-82755186159

10.3837/tiis.2011.11.001

Wan

Yan

Liu

Zhou

Enabling cyber-physical systems with machine-to-machine technologies

International Journal of Ad Hoc and Ubiquitous Computing 2013 13 3-4 187 196

10.1504/IJAHUC.2013.055454

2-s2.0-84881160058

Wan

Chen

Xia

Zhou

From machine-to-machine communications towards cyber-physical systems

Computer Science and Information Systems 2013 10 3 1105 1128

10.2298/CSIS120326018W

2-s2.0-84880050834

Alcaraz

Lopez

A security analysis for wireless sensor mesh networks in highly critical systems

IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews 2010 40 4 419 428

10.1109/TSMCC.2010.2045373

2-s2.0-77953688880

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

10.

Egea-Lopez

Martinez-Sala

Vales-Alonso

Garcia-Haro

Malgosa-Sanahuja

Wireless communications deployment in industry: a review of issues, options and technologies

Computers in Industry 2005 56 1 29 53

10.1016/j.compind.2004.10.001

2-s2.0-11144316051

11.

ISA

An ISA Standard Wireless Systems for Industrial Automation: Process Control and Related Applications

ISA-100.11a-2009, ISA, 2009

12.

IEC

Industrial communication networks—fieldbus specifications—WirelessHART communication network and communication profile

IEC/PAS 2009 62591, edition 1.0

IEC

13.

Chen

D. J.

Mark

Aloysius

WirelessHART: Real-Time Mesh Network for Industrial Automation 2010

Springer

14.

Song

Han

Mok

A. K.

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

2-s2.0-51249117686

15.

Ferrari

Flammini

Marioli

Rinaldi

Sisinni

On the implementation and performance assessment of a wirelessHART distributed packet analyzer

IEEE Transactions on Instrumentation and Measurement 2010 59 5 1342 1352

10.1109/TIM.2010.2040907

2-s2.0-77950917003

16.

Industrial Communication Networks

CFieldbus specifications

2009 IEC.IEC/PAS 62601

CWIA-PA Communication Network and Communication Profile

17.

Lee

W. L.

Datta

Cardell-Oliver

FlexiTP: a flexible-schedule-based TDMA protocol for fault-tolerant and energy-efficient wireless sensor networks

IEEE Transactions on Parallel and Distributed Systems 2008 19 6 851 864

10.1109/TPDS.2007.70774

2-s2.0-44049089919

18.

Zhang

Chen

D. Y.

Liu

A WSN vibration sensor nodes optimization placement strategy in nuclear power plant equipment monitoring application

Journal of Convergence Information Technology 2013 8 2 348 355

19.

Chang

Tan

Xing

Sensor placement algorithms for fusion-based surveillance networks

IEEE Transactions on Parallel and Distributed Systems 2011 22 8 1407 1414

10.1109/TPDS.2011.115

2-s2.0-79959750842

20.

Hou

Y. T.

Shi

Sherali

H. D.

Midkiff

S. F.

On energy provisioning and relay node placement for wireless sensor networks

IEEE Transactions on Wireless Communications 2005 4 5 2579 2590

10.1109/TWC.2005.853969

2-s2.0-28444472453

21.

Chen

I.-R.

Speer

A. P.

Eltoweissy

Adaptive fault-tolerant QoS control algorithms for maximizing system lifetime of query-based wireless sensor networks

IEEE Transactions on Dependable and Secure Computing 2011 8 2 161 176

10.1109/TDSC.2009.54

2-s2.0-78751676469

22.

Wang

Takahara

Hassanein

Device placement for heterogeneous wireless sensor networks: minimum cost with lifetime constraints

IEEE Transactions on Wireless Communications 2007 6 7 2444 2453

10.1109/TWC.2007.05357

2-s2.0-34547461043

23.

Liu

Energy conservation algorithms for maintaining coverage and connectivity in wireless sensor networks

IET Communications 2010 4 7 786 800

10.1049/iet-com.2009.0129

MR2778368

2-s2.0-77956940213

24.

Bredin

J. L.

Demaine

E. D.

Hajiaghayi

M. T.

Rus

Deploying sensor networks with guaranteed fault tolerance

IEEE/ACM Transactions on Networking 2010 18 1 216 228

10.1109/TNET.2009.2024941

2-s2.0-77249088133

25.

Han

Cao

Lloyd

E. L.

Shen

C.-C.

Fault-tolerant relay node placement in heterogeneous wireless sensor networks

IEEE Transactions on Mobile Computing 2010 9 5 643 656

10.1109/TMC.2009.161

2-s2.0-77949875456

26.

Liu

Wan

Jia

On optimal placement of relay nodes for reliable connectivity in wireless sensor networks

Journal of Combinatorial Optimization 2006 11 2 249 260

10.1007/s10878-006-7140-y

MR2212920

2-s2.0-33646532423

27.

Liu

Wan

P. J.

Jia

X. H.

Fault-tolerant relay node placement in wireless sensor networks

3595

Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM ′07)

2005

230 239

28.

Hao

Tang

Xue

Fault-tolerant relay node placement in wireless sensor networks: formulation and approximation

Proceedings of the Workshop on High Perfomance Switching and Routing (HPSR ′04)

April 2004

246 250

2-s2.0-2942525470

29.

Kashyap

Khuller

Shayman

Relay placement for fault tolerance in wireless networks in higher dimensions

Computational Geometry: Theory and Applications 2011 44 4 206 215

10.1016/j.comgeo.2010.11.002

MR2763792

2-s2.0-78751641738

30.

Tang

Hao

Sen

Relay node placement in large scale wireless sensor networks

Computer Communications 2006 29 4 490 501

10.1016/j.comcom.2004.12.032

2-s2.0-32644439091

31.

Zhang

W. Y.

Xue

Misra

Fault-tolerant relay node placement in wireless sensor networks: problems and algorithms

Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM ′07)

May 2007

1649 1657

10.1109/INFCOM.2007.193

2-s2.0-34548357224

32.

Zhang

Chen

Ling

A novel wsn relay nodes placement strategy in NPP equipment monitoring application

Proceedings of the 8th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM ′12)

September 2012

Shanghai, China

10.1109/WiCOM.2012.6478357

2-s2.0-84876062784

33.

Bari

Jaekel

Bandyopadhyay

Optimal placement of relay nodes in two-tiered, fault tolerant sensor networks

Proceedings of the 12th IEEE International Symposium on Computers and Communications (ISCC ′07)

July 2007

159 164

10.1109/ISCC.2007.4381590

2-s2.0-48049113662

34.

Sitanayah

Brown

K. N.

Sreenan

C. J.

Fault-tolerant relay deployment for k node-disjoint paths in wireless sensor networks

Proceedings of the IFIP Wireless Days (WD ′11)

October 2011

Niagara Falls, Canada

1 6

10.1109/WD.2011.6098176

2-s2.0-84856317491

35.

Bhuiyan

M. Z. A.

Cao

Wang

Deploying wireless sensor networks with fault tolerance for structural health monitoring

Proceedings of the 8th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS ′12)

May 2012

194 202

10.1109/DCOSS.2012.38

2-s2.0-84864248428

36.

Bari

Jaekel

Jiang

Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements

Computer Communications 2012 35 3 320 333

10.1016/j.comcom.2011.10.006

2-s2.0-84856513954

37.

Wang

Research on multi-restricted fault-tolerant relay node placement algorithm in wireless sensor networks

Acta Electronica Sinica 2011 39 3A 115 120

2-s2.0-79959600294

38.

Wang

Wei

D.-B.

Wang

Relay node placement and addition algorithms in wireless sensor networks

Acta Physica Sinica 2012 61 12 1 10

120505

2-s2.0-84863855942

39.

Al-Turjman

F. M.

Al-Fagih

A. E.

Hassanein

H. S.

Ibnkahla

M. A.

Deploying fault-tolerant grid-based wireless sensor networks for environmental applications

Proceedings of the IEEE 35th Conference on Local Computer Networks (LCN ′10)

October 2010

Denver, Colo, USA

715 722

10.1109/LCN.2010.5735798

40.

Yang

Misra

Xue

Joint base station placement and fault-tolerant routing in wireless sensor networks

Proceedings of the IEEE Global Telecommunications Conference

December 2009

1 6

10.1109/GLOCOM.2009.5425292

2-s2.0-77951526165

41.

Chaudhry

Hung

Guha

Optimal placement of wireless sensor nodes with fault tolerance and minimal energy consumption

Proceedings of the IEEE International Conference on Mobile Ad Hoc and Sensor Sysetems

October 2006

610 615

10.1109/MOBHOC.2006.278621

2-s2.0-39049132143

42.

Michael

T. S.

Pinciu

Art gallery theorems for guarded guards

Computational Geometry 2003 26 3 247 258

10.1016/S0925-7721(03)00039-7

2-s2.0-84867945100

MR2005302

43.

Sun

Kai

N. A.

A genetic simulated annealing hybrid algorithm for relay nodes deployment optimization in industrial wireless sensor networks

Proceedings of the IEEE International Conference on Computational Intelligence for Measurement Systems and Applications (CIMSA ′12)

2012

24 28

44.

Saifullah

Chen

Real-time scheduling for WirelessHART networks

Proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS ′10)

December 2010

150 159

10.1109/RTSS.2010.41

2-s2.0-79951808118

45.

Yoo

S.-E.

Chong

P. K.

Kim

Doh

Pham

M.-L.

Choi

Huh

Guaranteeing real-time services for industrial wireless sensor networks with IEEE 802.15.4

IEEE Transactions on Industrial Electronics 2010 57 11 3868 3876

10.1109/TIE.2010.2040630

2-s2.0-77955710846

Optimized Design of Relay Node Placement for Industrial Wireless Network

Abstract

1. Introduction

1.1. Introduction of CPS

1.2. Industrial Wireless Network

1.3. Related Work on Relay Node Placement

1.4. Research Feature and Paper Arrangement

2. Network Model and Formulation

2.1. Network Model

2.2. Parameter Definition

2.3. ILP Formulation

2.4. ILP Formal Specification

3. Solution

3.1. Solution Explanation

3.2. Calculating the Fewest Number of Conflict Edge Coloring

Theorem 1.

4. Simulation Experiment and Result

4.1. Network Performance without Real-Time Constraints or Energy Constraints

4.2. Network Performance without Real-Time Constraints but Energy Constraints

4.3. Network Performance with Both Real-Time Constraints and Energy Constraints

5. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References