Get Latest CSE Projects in your Email


Maximizing Network Lifetime of Wireless Sensor Actuator Networks Under Graph Routing

ABSTRACT

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 first 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 benefits of graph routing.

RELATED WORK

Fig. 1: Source and Graph Routing

Fig. 1: Source and Graph Routing

Energy-aware routing for wireless sensor and adhoc networks has received significant 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 traffic 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 benefits 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.

NETWORK MODELS

Fig. 2: Transaction timing in one time slot

Fig. 2: Transaction timing in one time slot

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

Fig. 3: Reduction

Fig. 3: Reduction

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 efficient solutions based on linear programming relaxation and greedy heuristic. The efficiency 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.

EVALUATION

Fig. 4: Topology of the WSAN Testbed

Fig. 4: Topology of the WSAN Testbed

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 field 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.

CONCLUSION

As IoT starts gaining adoption in industrial applications, industrial WSANs provide critical communication infrastructure for industrial automation. Industrial WSANs face significant 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 efficient 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 significantly 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

Download Project

>> Latest IoT based Automation Projects for Engineering Students

>> 50+ IoT based Wireless/GSM Projects for Engineering Students

For Free CSE Project Downloads:

Enter your email address:
( Its Free 100% )


Leave a Comment

Your email address will not be published. Required fields are marked *