Industrial Wireless Sensor-Actuator Networks (WSANs) enable Internet of Things (IoT) to be incorporated in industrial plants. The dynamics of industrial environments and stringent reliability requirements necessitate high degrees of fault tolerance. WirelessHART is an important industrial standard for WSANs that have seen world-wide deployments. WirelessHART employs graph routing to enhance network reliability through multiple paths. Since many industrial devices operate on batteries in harsh environments where changing batteries is prohibitively labor-intensive, WirelessHART networks need to achieve a long network lifetime.
To meet industrial demand for long-term reliable communication, this paper studies the problem of maximizing network lifetime for WirelessHART networks under graph routing. We ﬁrst formulate the network lifetime maximization problem and prove it is NP-hard. Then, we propose an optimal algorithm based on integer programming, a linear programming relaxation algorithm and a greedy heuristic algorithm to prolong the network lifetime of WirelessHART networks. Experiments in a physical testbed and simulations show our algorithms can improve the network lifetime by up to 60% while preserving the reliability beneﬁts of graph routing.
Energy-aware routing for wireless sensor and adhoc networks has received signiﬁcant attention. Stojmenovic and Lin proposed a protocol to minimize total power consumption and extend network lifetime. Chang and Tassiulas maximized network lifetime by balancing network trafﬁc among the nodes in proportion to their residual energy. Wu etal proposed a routing algorithm to improve the lifetime and reliability of the network based on local topology information. Li et al proposed a routing protocol that combines the beneﬁts of selecting the path with minimum power consumption and the path that maximizes residual power in the nodes. Doshi et at implemented a minimum energy routing version of the DSR protocol in a network simulator.
Figure 2 shows the timing of a transmission in a time slot. The top of the timing diagram shows the operation of the sender and the bottom shows that of the receiver. When a shared slot is assigned, the sender will perform Clear Channel Assessment (CCA) before transmitting the packet. We use TsMax Packet to denote the maximum time to transmit a packet. When scheduled as the transmission’s receiver, the receiver must enter receive mode. The receiver must keep the radio on to listen to potential packet transmission.
GRAPH ROUTE LIFETIME MAXIMIZATION PROBLEM
We reduce the decision problem of MEDP to the decision problem of SRLM. The reduction algorithm takes an instance of the decision problem of MEDP problem as input. Given a graph G, we construct an auxiliary graph G0 in the following diagram.
LIFETIME MAXIMIZATION GRAPH ROUTING ALGORITHMS
In this section, we propose an optimal solution based on integer programming, followed by more efﬁcient solutions based on linear programming relaxation and greedy heuristic. The efﬁciency of the routing algorithms are important because the network manager needs to recompute routes as network topology and channel condition change in real-world environments.
Figure 4 shows the topology of our testbed. We select motes 129 and 155 (green circles) as the access points, which are physically connected to a root server (gateway). The other motes act as ﬁeld devices (red circles). The network manager is a software running on the root server. For each link in the testbed, we measured its packet reception ratio (PRR) by counting the number of received packets among 250 packets transmitted over the link.
As IoT starts gaining adoption in industrial applications, industrial WSANs provide critical communication infrastructure for industrial automation. Industrial WSANs face signiﬁcant challenges in achieving long-term reliable communication in harsh environments. While the WirelessHART standard adopts graph routing to enhance network reliability, the problem of maximizing network lifetime for graph routing becomes a critical open problem. This paper introduces and formulates the network lifetime maximization problem for graph routing. We present an optimal graph routing algorithm based on integer programming, and two efﬁcient algorithms based on linear programming relaxation and greedy heuristic, respectively.
We have implemented our graph routing algorithms on a physical WSAN network testbed. Experimental results on the testbed and in simulations show the linear relaxation and greedy heuristic can improve the network lifetime by up to 60% when compared to an existing graph routing algorithm. Moreover, the greedy heuristic requires signiﬁcantly lower computation time, making it particularly suitable for WirelessHART networks that may compute graph routes frequently when facing network changes in open environments.
Source: Washington University
Authors: Chengjie Wu | Dolvara Gunatilaka | Abusayeed Saifullah | Mo Sha | Paras Tiwari | Chenyang Lu | Yixin Chen