On the Minimization of Communication in Networked Systems with a Central Station

The problem of minimizing communication in a distributed networked system is considered in a discrete-event formalism where the system is modeled as a finite-state automaton. The system consists of a central station and a set of N local agents, each observing a set of local events. The central station needs to know exactly the state of the system, whereas local agents need to disambiguate certain pre-specified pairs of states for purposes of control or diagnosis. This requirement is achieved by communication, which occurs only between the central station and the local agents but not among the local agents. A communication policy is defined as a set of event occurrences to be communicated between the central station and the local agents. A communication policy is said to be minimal if any removal of communication of event occurrences will affect the correctness of the solution. Under an assumption on the absence of cycles (other than self-loops) in the system model, this paper presents an algorithm that computes a minimal communication policy in polynomial time in all parameters of the system. These results improve upon previous algorithms for solving minimum communication problems.

Feng LinEmail:

---

Weilin Wang   received M.S. and Ph.D. degrees in Electrical Engineering: Systems from the University of Michigan, Ann Arbor, in 2003 and 2007, respectively. He received a M.S.E. in Industrial Engineering, also from the University of Michigan, Ann Arbor, in 2006. He is currently a postdoctoral research fellow in the Department of Electrical Engineering and Computer Science at the University of Michigan, Ann Arbor. Prior to enrolling at the University of Michigan, Ann Arbor, he worked for the Zhejiang Department of Transportation, Hangzhou, China. His research interests are in optimization algorithms, discrete event systems, networked control systems, coverage and mobility for wireless sensor networks, and energy efficient wireless networking. Stéphane Lafortune   received the B. Eng degree from Ecole Polytechnique de Montréal in 1980, the M. Eng. degree from McGill University in 1982, and the Ph.D. degree from the University of California at Berkeley in 1986, all in electrical engineering. Since September 1986, he has been with the University of Michigan, Ann Arbor, where he is a Professor of Electrical Engineering and Computer Science. Dr. Lafortune is a Fellow of the IEEE (1999). He received the Presidential Young Investigator Award from the National Science Foundation in 1990 and the George S. Axelby Outstanding Paper Award from the Control Systems Society of the IEEE in 1994 (for a paper co-authored with S. L. Chung and F. Lin) and in 2001 (for a paper co-authored with G. Barrett). At the University of Michigan, he received the EECS Department Research Excellence Award in 1994–1995, the EECS Department Teaching Excellence Award in 1997–1998, and the EECS Outstanding Achievement Award in 2003–2004. Dr. Lafortune is a member of the editorial boards of the Journal of Discrete Event Dynamic Systems: Theory and Applications and of the International Journal of Control. His research interests are in discrete event systems modeling, diagnosis, control, and optimization. He is co-developer of the software packages DESUMA and UMDES. He co-authored, with C. Cassandras, the textbook Introduction to Discrete Event Systems—Second Edition (Springer, 2007). Recent publications and software tools are available at the Web site . Feng Lin   received his B.Eng. degree in electrical engineering from Shanghai Jiao-Tong University, Shanghai, China, in 1982, and his M.A.Sc. and Ph.D. degrees in electrical engineering from the University of Toronto, Toronto, Canada, in 1984 and 1988, respectively. From 1987 to 1988, he was a postdoctoral fellow at Harvard University, Cambridge, MA. Since 1988, he has been with the Department of Electrical and Computer Engineering, Wayne State University, Detroit, Michigan, where he is currently a professor. His research interests include discrete-event systems, hybrid systems, robust control, and image processing. He was a consultant for GM, Ford, Hitachi and other auto companies. Dr. Lin co-authored a paper with S. L. Chung and S. Lafortune that received a George Axelby outstanding paper award from IEEE Control Systems Society. He is also a recipient of a research initiation award from the National Science Foundation, an outstanding teaching award from Wayne State University, a faculty research award from ANR Pipeline Company, and a research award from Ford. He was an associate editor of IEEE Transactions on Automatic Control.