Xueying Guo
Abstract
In networked cyber-physical systems, the inter-delivery time of data packets becomes an important quantity of interest. However, providing a guarantee that the inter-delivery times of the packets are “small enough” becomes a difficult task in such systems due to the unreliable communication medium and limited network resources. We design scheduling policies that meet the inter-delivery time requirements of multiple clients connected over wireless channels. We formulate the problem as an infinite-state risk-sensitive Markov decision process, where large exceedances of inter-delivery times for different clients over their design thresholds are severely penalized. We reduce the infinite-state problem to an equivalent finite-state problem and establish the existence of a stationary optimal policy and an algorithm for computing it in a finite number of steps. However, its computational complexity makes it intractable when the number of clients is of the order of 100 or so that is found in applications such as in-vehicle networks. To design computationally efficient optimal policies, we, therefore, develop a theory based on the high reliability asymptotic scenario, in which the channel reliability probabilities are close to one. We thereby obtain an algorithm of relatively low computational complexity for determining an asymptotically optimal policy. To address the remaining case when the channels are not relatively reliable, we design index-based policies for the risk sensitive case, which extends key ideas for index policies in risk-neutral multi-armed bandit problems. Simulation results are provided to show the effectiveness of our policies.
- X. Guo, R. Singh, P. R. Kumar, and Z. Niu, "A high reliability asymptotic approach for packet inter-delivery time optimization in cyber-physical systems," in Proc. 16th ACM Int. Symp. Mobile Ad Hoc Netw. Comput. (MobiHoc), 2015, pp. 197-206. Google Scholar
- E. A. Lee, "Cyber physical systems: Design challenges," in Proc. 11th IEEE Int. Symp. Object Compon.-Oriented Real-Time Distrib. Comput. (ISORC), May 2008, pp. 363-369. Google Scholar
- H. Xiong, R. Li, A. Eryilmaz, and E. Ekici, "Delay-aware cross-layer design for network utility maximization in multi-hop networks," IEEE J. Sel. Areas Commun., vol. 29, no. 5, pp. 951-959, May 2011.Google Scholar
- M. J. Neely, E. Modiano, and C.-P. Li, "Fairness and optimal stochastic control for heterogeneous networks," in Proc. IEEE INFOCOM, Mar. 2005, pp. 1723-1734.Google Scholar
- R. Li, A. Eryilmaz, and B. Li, "Throughput-optimal wireless scheduling with regulated inter-service times," in Proc. IEEE INFOCOM, Apr. 2013, pp. 2616-2624.Google Scholar
- 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 Proc. INFOCOM, Apr./May 2015, pp. 505-512.Google Scholar
- R. Singh, I.-H. Hou, and P. R. Kumar, "Fluctuation analysis of debt based policies for wireless networks with hard delay constraints," in Proc. IEEE INFOCOM, Apr./May 2014, pp. 2400-2408.Google Scholar
- R. Singh, I.-H. Hou, and P. R. Kumar, "Pathwise performance of debt based policies for wireless networks with hard delay constraints," in Proc. IEEE 52nd Annu. Conf. Decis. Control (CDC), Dec. 2013, pp. 7838-7843.Google Scholar
- X. Guo, R. Singh, P. R. Kumar, and Z. Niu, "Optimal energy-efficient regular delivery of packets in cyber-physical systems," in Proc. IEEE ICC, Jun. 2015, pp. 3186-3191.Google Scholar
- R. A. Howard and J. E. Matheson, "Risk-sensitive Markov decision processes," Manage. Sci., vol. 18, no. 7, pp. 356-369, 1972.Google Scholar
- K.-J. Chung and M. J. Sobel, "Discounted MDP's: Distribution functions and exponential utility maximization," SIAM J. Control Optim., vol. 25, no. 1, pp. 49-62, 1987. Google Scholar
- W. H. Fleming and D. Hernández-Hernández, "Risk sensitive control of finite state machines on an infinite horizon. I," in Proc. IEEE Conf. Decis. Control, Dec. 1997, pp. 3407-3412.Google Scholar
- S. I. Marcus, E. Fernández-Gaucherand, D. Hernández-Hernández, S. Coraluppi, and P. Fard, "Risk sensitive Markov decision processes," in Systems and Control in the Twenty-First Century. Boston, MA, USA: Birkhäuser, 1997.Google Scholar
- R. Cavazos-Cadena and E. Fernández-Gaucherand, "Controlled Markov chains with risk-sensitive criteria: Average cost, optimality equations, and optimal solutions," Math. Methods Oper. Res., vol. 49, no. 2, pp. 299-324, 1999.Google Scholar
- S. C. Jaquette, "A utility criterion for Markov decision processes," Manage. Sci., vol. 23, no. 1, pp. 43-49, 1976. Google Scholar
- A. S. Avestimehr, S. N. Diggavi, and D. N. C. Tse, "Wireless network information flow: A deterministic approach," IEEE Trans. Inf. Theory, vol. 57, no. 4, pp. 1872-1905, Apr. 2011. Google Scholar
- P. Whittle, "Restless bandits: Activity allocation in a changing world," J. Appl. Probab., vol. 25, pp. 287-298, Jan. 1988.Google Scholar
- B. Li, R. Li, and A. Eryilmaz, "Heavy-traffic-optimal scheduling with regular service guarantees in wireless networks," in Proc. MobiHoc, 2013, pp. 79-88. Google Scholar
- Y. Sadi and S. C. Ergen, "Optimal power control, rate adaptation, and scheduling for UWB-based intravehicular wireless sensor networks," IEEE Trans. Veh. Technol., vol. 62, no. 1, pp. 219-234, Jan. 2013.Google Scholar
- R. Singh and A. Stolyar, "Maxweight scheduling: Asymptotic behavior of unscaled queue-differentials in heavy traffic," in Proc. ACM SIGMETRICS, Jun. 2015, pp. 431-432. Google Scholar
- R. Singh, X. Guo, and E. Modiano, "Risk-sensitive optimal control of queues," in Proc. 56th IEEE Conf. Decis. Control, Dec. 2017, pp. 3563-3568.Google Scholar
- E. Altman, V. Kavitha, F. De Pellegrini, V. Kamble, and V. Borkar, "Risk sensitive optimal control framework applied to delay tolerant networks," in Proc. IEEE INFOCOM, Apr. 2011, pp. 3146-3154.Google Scholar
- S. Kittipiyakul, P. Elia, and T. Javidi, "High-SNR analysis of outage-limited communications with bursty and delay-limited information," IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 746-763, Feb. 2009. Google Scholar
- Y. Zhang and C. Tepedelenlioglu, "Applications of Tauberian theorem for high-SNR analysis of performance over fading channels," IEEE Trans. Wireless Commun., vol. 11, no. 1, pp. 296-304, Jan. 2012.Google Scholar
- A. Bar-Noy, R. Bhatia, J. S. Naor, and B. Schieber, "Minimizing service and operation costs of periodic scheduling," in Proc. ACM Symp. Discrete Algorithms, 2002, pp. 11-20. Google Scholar
- D. Zhu, D. Mosse, and R. Melhem, "Multiple-resource periodic scheduling problem: How much fairness is necessary?" in Proc. IEEE Real-Time Syst. Symp., Dec. 2003, pp. 142-151. Google Scholar
- M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1st ed. Hoboken, NJ, USA: Wiley, 1994. Google Scholar
- S. M. Ross, Applied Probability Models with Optimization Applications. New York, NY, USA: Dover, 1992.Google Scholar
- D. E. Knuth, "Big omicron and big omega and big theta," ACM SIGACT News, vol. 8, no. 2, pp. 18-24, 1976. Google Scholar
- R. R. Weber and G. Weiss, "On an index policy for restless bandits," J. Appl. Probab., vol. 27, no. 3, pp. 637-648, Sep. 1990.Google Scholar
- K. E. Atkinson, An Introduction to Numerical Analysis. Hoboken, NJ, USA: Wiley, 2008.Google Scholar
- V. S. Borkar, Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge, U.K.: Cambridge Univ. Press, 2008.Google Scholar
- V. S. Borkar and S. P. Meyn, "The O.D.E. Method for convergence of stochastic approximation and reinforcement learning," SIAM J. Control Optim., vol. 38, no. 2, pp. 447-469, 2000. Google Scholar
- I.-H. Hou, V. Borkar, and P. R. Kumar, "A theory of QoS for wireless," in Proc. IEEE INFOCOM, Apr. 2009, pp. 486-494.Google Scholar
Recommendations
A High Reliability Asymptotic Approach for Packet Inter-Delivery Time Optimization in Cyber-Physical Systems
MobiHoc '15: Proceedings of the 16th ACM International Symposium on Mobile Ad Hoc Networking and ComputingIn 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 ...
Ultimately Stationary Policies to Approximate Risk-Sensitive Discounted MDPs
VALUETOOLS 2019: Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and ToolsRisk-sensitive Markov Decision Process (RSMDP) models are less studied than linear Markov decision models. Linear models optimize only expected cost whereas RSMDP models optimize a combination of expected cost and higher moments of the cost. On the ...
Brief Risk-sensitive and minimax control of discrete-time, finite-state Markov decision processes
This paper analyzes a connection between risk-sensitive and minimax criteria for discrete-time, finite-state Markov decision processes (MDPs). We synthesize optimal policies with respect to both criteria, both for the finite horizon and the discounted ...
Comments