Resource Virtualization with End-to-End Timing Guarantees for Multi-Hop Multi-Channel Real-Time Wireless Networks

Resource virtualization is a promising technique that has been increasingly deployed in industrial automation systems to support multiple time-critical applications sharing the same physical resources. Extensive studies have been reported on how to perform real-time virtualization on computing resources. However, when applying virtualization techniques on network resources (especially for real-time wireless networks), node dependency among applications, wireless channel contention and stringent end-to-end timing requirements of the real-time flows in the network pose severe challenges. To address this problem, this paper formulates the network virtualization problem for multi-hop multi-channel real-time wireless networks (RTWNs). We first present a Satisfiability Modulo Theory (SMT)-based exact solution to capture the constraints posted by each application's resource interfaces and node dependency graphs. A novel supply graph (SG)-based partitioning framework, SGP, is then proposed to determine the resource partitions for individual applications. SGP uses supply graph to maintain compliance with the regularity constraints while efficiently allocating resources. Experimental results from both a real-world testbed and extensive simulations show that SGP can achieve comparable success ratio with the SMT-based exact solution but reduce the computational overhead significantly.