A High Reliability Asymptotic Approach for Packet Inter-Delivery Time Optimization in Cyber-Physical Systems

ABSTRACT

In cyber-physical systems such as automobiles, measurement data from sensor nodes should be delivered to other consumer nodes such as actuators in a regular fashion. But, in practical systems over unreliable media such as wireless, it is a significant challenge to guarantee small enough inter-delivery times for different clients with heterogeneous channel conditions and inter-delivery requirements. In this paper, we design scheduling policies aiming at satisfying the inter-delivery requirements of such clients. We formulate the problem as a risk-sensitive Markov Decision Process (MDP). Although the resulting problem involves an infinite state space, we first prove that there is an equivalent MDP involving only a finite number of states. Then we prove the existence of a stationary optimal policy and establish an algorithm to compute it in a finite number of steps.

However, the bane of this and many similar problems is the resulting complexity, and, in an attempt to make fundamental progress, we further propose a new high reliability asymptotic approach. In essence, this approach considers the scenario when the channel failure probabilities for different clients are of the same order, and asymptotically approach zero. We thus proceed to determine the asymptotically optimal policy: in a two-client scenario, we show that the asymptotically optimal policy is a "modified least time-to-go" policy, which is intuitively appealing and easily implementable; in the general multi-client scenario, we are led to an SN policy, and we develop an algorithm of low computational complexity to obtain it. Simulation results show that the resulting policies perform well even in the pre-asymptotic regime with moderate failure probabilities.

References

1. E. Altman, V. Kavitha, F. De Pellegrini, V. Kamble, and V. Borkar. Risk sensitive optimal control framework applied to delay tolerant networks. In IEEE INFOCOM, April 2011.
2. A. S. Avestimehr, S. N. Diggavi, and D. N. Tse. Wireless network information flow: A deterministic approach. IEEE Trans. on Info. Theory, 2011.
3. A. Bar-Noy, R. Bhatia, J. S. Naor, and B. Schieber. Minimizing service and operation costs of periodic scheduling. In ACM Symposium on Discrete Algorithms, 2002.
4. R. Cavazos-Cadena and E. Fernandez-Gaucherand. Controlled Markov chains with risk-sensitive criteria: Average cost, optimality equations, and optimal solutions. Mathematical Methods of Operations Research, 49(2), 1999.
5. K.-J. Chung and M. J. Sobel. Discounted MDP';s: Distribution functions and exponential utility maximization. SIAM J. Control Optim., 25(1), 1987.
6. T. ElBatt, C. Saraydar, M. Ames, and T. Talty. Potential for intra-vehicle wireless automotive sensor networks. In IEEE Sarnoff Symposium, March 2006.
7. W. Fleming and D. Hernandez-Hernandez. Risk sensitive control of finite state machines on an infinite horizon. I. In Decision and Control, IEEE Conference on, Dec 1997.
8. X. Guo, R. Singh, P. Kumar, and Z. Niu. Optimal energy-efficient regular delivery of packets in cyber-physical systems. In IEEE ICC, 2015.
9. X. Guo, S. Zhou, Z. Niu, and P. Kumar. Optimal wake-up mechanism for single base station with sleep mode. In IEEE International Teletraffic Congress, Sept 2013.
10. I.-H. Hou, V. Borkar, and P. Kumar. A theory of QoS for wireless. In IEEE INFOCOM, April 2009.
11. R. A. Howard and J. E. Matheson. Risk-sensitive Markov decision processes. Manage. Science, 1972.
12. S. C. Jaquette. A utility criterion for Markov decision processes. Management Science, 23(1), 1976.
13. S. Kittipiyakul, P. Elia, and T. Javidi. High-snr analysis of outage-limited communications with bursty and delay-limited information. Information Theory, IEEE Transactions on, Feb 2009.
14. B. Li, R. Li, and A. Eryilmaz. Heavy-traffic-optimal scheduling with regular service guarantees in wireless networks. In MobiHoc, 2013.
15. R. Li, A. Eryilmaz, and B. Li. Throughput-optimal wireless scheduling with regulated inter-service times. In IEEE INFOCOM, April 2013.
16. S. I. Marcus, E. Fernandez-Gaucherand, D. Hernandez-Hernandez, S. Coraluppi, and P. Fard. Risk sensitive Markov decision processes. In Systems and control in the 21st century, 1997.
17. M. Neely, E. Modiano, and C. ping Li. Fairness and optimal stochastic control for heterogeneous networks. In IEEE INFOCOM, 2005.
18. M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., 1st edition, 1994.
19. Rahul Singh, I-Hong Hou and P.R. Kumar. Pathwise performance of debt based policies for wireless networks with hard delay constraints. In IEEE 52nd Annual Conference on Decision and Control (CDC), 2013, pages 7838--7843, Dec 2013.
20. Rahul Singh, I-Hong Hou and P.R. Kumar. Fluctuation analysis of debt based policies for wireless networks with hard delay constraints. In Proceedings of IEEE INFOCOM, 2014, pages 2400--2408, April 2014.
21. Y. Sadi and S. Ergen. Optimal power control, rate adaptation, and scheduling for uwb-based intravehicular wireless sensor networks. IEEE Transactions on Vehicular Technology, Jan 2013.
22. R. Singh, X. Guo, and P. R. Kumar. Index policies for optimal mean-variance trade-off of inter-delivery times in real-time sensor networks. In INFOCOM, 2015.
23. R. Singh and A. Stolyar. Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic. In Proceedings of ACM SIGMETRICS, June 2015.
24. H.-M. Tsai, O. Tonguz, C. Saraydar, T. Talty, M. Ames, and A. MacDonald. Zigbee-based intra-car wireless sensor networks: a case study. IEEE Wireless Communications, December 2007.
25. H. Xiong, R. Li, A. Eryilmaz, and E. Ekici. Delay-aware cross-layer design for network utility maximization in multi-hop networks. Selected Areas in Communications, IEEE Journal on, May 2011.
26. Y. Zhang and C. Tepedelenlioglu. Applications of tauberian theorem for high-snr analysis of performance over fading channels. Wireless Communications, IEEE Transactions on, January 2012.

Index Terms

• Networks

  • Network types

    • Mobile networks

    • Wireless access networks