logo

SCIENTIA SINICA Informationis, Volume 46, Issue 11: 1633-1647(2016) https://doi.org/10.1360/N112016-00139

Timing optimal control and reliability of uncertain data transmission systems with interval parameters

More info
  • ReceivedAug 12, 2016
  • AcceptedOct 14, 2016
  • PublishedNov 10, 2016

Abstract

This paper presents an investigation of the timing optimal control and timing reliability of data transmission systems of which the launch time, transmission time, and reception time are uncertain. The time series model of uncertain data transmission systems is established by using max-plus algebra. We introduce the parametric vector-valued function of uncertain data transmission systems and the non-negative solution of max-plus linear equations. We determine, on the one hand, the minimum value of the reception time (the earliest reception time) of the data and the corresponding optimal solutions under the constraints for which the transmission time is valued in given intervals and the launch time is non-negative. On the other hand, we establish the maximum value of the launch time (the latest launch time) of the data and the corresponding optimal solutions under the constraints for which the reception time is limited in some intervals. We define reliable intervals of uncertain data transmission systems such that the data can be received within the required time and the influence of transport delays can be avoided as long as they are launched at any time during such intervals. The tolerance solution intervals of interval systems of max-plus linear equations is introduced to establish the existing criterion of reliable intervals, and an effective algorithm for finding the largest reliable interval is developed.


Funded by

国家自然科学基金(60774007)

国家自然科学基金(61305101)


References

[1] Roddy D. {Satellite Communications}. New Jersey: Prentice Hall, 1989. Google Scholar

[2] Collinson R P G. {Introduction to Avionics Systems}. New York: Springer Science+Business Media, 2011. Google Scholar

[3] Dumas M B. {Principles of Computer Networks and Communications}. New Jersey: Prentice Hall, 2008. Google Scholar

[4] Cohen G, Dunois D, Quadrat J P, et al. A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing. newblock IEEE Trans Autom Contr, 1985, 30: 210-220 CrossRef Google Scholar

[5] Olsder G J. Applications of the theory of stochastic discrete-event systems to array processors and scheduling in public transportation. In: {Proceedings of the 28th IEEE Conference on Decision and Control}, Tampa, 1989. 2012-2017. Google Scholar

[6] Li Q, Zhang X, Xiong H. An optimization for packet delivery in integrated avionics systems. In: {Proceedings of the 23rd Digital Avionics Systems Conference}, Salt Lake City, 2004. Google Scholar

[7] Goverde R M P. Railway timetable stability analysis using max-plus system theory. {Transport Res B-Meth}, 2007, {41}: 179-201. Google Scholar

[8] Olsder G J, Roos C. Cramer and {C}ayley-{H}amilton in the max algebra. {Linear Algebra Appl}, 1988, 101: 87-108. Google Scholar

[9] D$\text{e\ }$Schutter B, De Moor B. A note on the characteristic equation in the max-plus algebra. newblock Linear Algebra Appl, 1997, 261: 237-250 CrossRef Google Scholar

[10] Chen W, Qi X, Deng S. The eigen-problem and period analysis of the discrete event system. {Syst Sci Math Sci}, 1990, 3: 243-260. Google Scholar

[11] Gaubert S. {Th$\acute{\text{e}}$orie des Syst$\grave{\text{e}}$mes Lin$\acute{\text{e}}$aires dans les Dioides}. Dissertation for Ph.D. Degree. Paris: L'Ecole Nationale Sup$\acute{\text{e}}$rieure des Mines de Paris, 1992. Google Scholar

[12] Gaubert S, Gunawardena J. The duality theorem for min-max functions. {Comptes Rendus de l'Acad$\acute{\text{e}}$mie des Sciences, Series I: Mathematics}, 1998, 326: 43-48. Google Scholar

[13] Zhao Q. A remark on inseparability of min-max systems. newblock IEEE Trans Autom Contr, 2004, 49: 967-970 CrossRef Google Scholar

[14] Butkovi$\check{c}$ P, MacCaig M. On integer eigenvectors and subeigenvectors in the max-plus algebra. newblock Linear Algebra Appl, 2013, 438: 3408-3424 CrossRef Google Scholar

[15] D$\text{e\ }$Schutter B, De Moor B. The {QR} decomposition and the singular value decomposition in the symmetrized max-plus algebra. newblock SIAM J Matrix Anal Appl, 1998, 19: 378-406 CrossRef Google Scholar

[16] Chen W, Qi X. Period assignment of discrete event dynamic systems. {Sci China Ser A}, 1993, 13: 1-7. Google Scholar

[17] Cohen G, Dubois D, Quadrat J P, et al. Linear system theory for discrete event systems. In: {Proceedings of the 23rd IEEE Conference on Decision and Control}, Las Vegas, 1984. 539-544. Google Scholar

[18] Wang L, Zheng D. On the reachability of linear discrete event dynamic systems. {Appl Math A J Chinese Univ}, 1990, 5: 292-301. Google Scholar

[19] Tao Y, Liu G-P, Mu X. Max-plus matrix method and cycle time assignability and feedback stabilizability for min-max-plus systems. {Math Contr Signals Syst}, 2013, {25}: 197-229. Google Scholar

[20] Adzkiya D, De Schutter B, Abate A. Computational techniques for reachability analysis of max-plus-linear systems. {Automatica}, 2015, {53}: 293-302. Google Scholar

[21] D$\text{e\ }$Schutter B, van den Boom T J J. Model predictive control for max-plus-linear discrete event systems. {Automatica}, 2001, {37}: 1049-1056. Google Scholar

[22] van den Boom T J J, De Schutter B. Properties of {MPC} for max-plus-linear systems. {Eur J Contr}, 2002, {8}: 453-462. Google Scholar

[23] Moore R E. {Methods and Applications of Interval Analysis}. Philadelphia: Society for Industrial and Applied Mathematics, 1979. Google Scholar

[24] Lhommeau M, Hardouin L, Cottenceau B, et al. Interval analysis and dioid: application to robust controller design for timed event graphs. {Automatica}, 2004, {40}: 1923-1930. Google Scholar

[25] Aubry C, Desmare R, Jaulin L. Loop detection of mobile robots using interval analysis. {Automatica}, 2013, {49}: 463-470. Google Scholar

[26] Zhang H, Tao Y, Zhang Z. Strong solvalibility of interval max-plus systems and applications to optimal control. {Syst Contr Lett}, 2016, {96}: 88-94. Google Scholar

[27] Cechl$\acute{\text{a}}$rov$\acute{\text{a}}$ K, Cuninghame-Green R A. Interval systems of max-separable linear equations. {Linear Algebra Appl}, 2002, {340}: 215-224. Google Scholar

[28] My$\check{\text{s}}$kov$\acute{\text{a}}$ H. Interval systems of max-separable linear equations. {Linear Algebra Appl}, 2005, {423}: 263-272. Google Scholar

[29] My$\check{\text{s}}$kov$\acute{\text{a}}$ H. Interval max-plus systems of linear equations. {Linear Algebra Appl}, 2012, {437}: 1992-2000. Google Scholar

[30] {Chakraborty S, Yun K Y, Dill D L. Timing analysis of asynchronous systems using time separation of events. {IEEE Trans Comput Aided Design Integr Circ Syst}, 1999, {18}: 1061-1076}. Google Scholar

[31] {Zhao Q, Mao J, Tao Y. Time separations of cyclic event rule systems with min-max timing constraints. {Theor Comput Sci}, 2008, {407}: 496-510}. Google Scholar

[32] Cuninghame-Green R A. {Minimax Algebra}. Berlin: Springer-Verlag, 1979. Google Scholar

[33] Baccelli F, Cohen G, Olsder G J, et al. {Synchronization and Linearity}. New York: John Wiley and Sons, 1992. Google Scholar

[34] Heidergott B, Olsder G J, van der Woude J. {Max-Plus at Work: Modeling and Analysis of Synchronized Systems}. New Jersey: Princeton University Press, 2006. Google Scholar

[35] Zimmermann K. {Extrem$\acute{\text{a}}$lni Algebra}. Praha: Ekonomicko-matematick$\acute{\text{a}}$ laborato$\check{\text{r}}$ Ekonomick$\acute{\text{e}}$ho $\acute{\text{u}}$stavu $\check{\text{C}}$SAV, 1976. Google Scholar

[36] Butkovi$\check{\rm c}$ P. {Max-Linear Systems: Theory and Algorithms}. Berlin: Springer-Verlag, 2010. Google Scholar

[37] Alefeld G, Herzberger J. {Introduction to Interval Computations}. New York: Academic Press, 1983. Google Scholar

[38] Alefeld G, Mayer G. Interval analysis: theory and applications. {J Comput Appl Math}, 2000, {121}: 421-464. Google Scholar

[39] Litvinov G L, Sobolevski$\breve{{\i}}$ A N. Idempotent interval analysis and optimization problems. {Reliable Comput}, 2001, {7}: 353-377. Google Scholar

[40] Cechl$\acute{\text{a}}$rov$\acute{\text{a}}$ K. Solutions of interval linear systems in max-plus algebra. In: Proceedings of the Symposium on Operations Research, Preddvor, 2001. 321-326. Google Scholar

Copyright 2019 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1