TY - GEN
T1 - Cyclic network automata and cohomological waves
AU - Cai, Yiqing
AU - Ghrist, Robert
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 2014
Y1 - 2014
N2 - Following Baryshnikov-Coffman-Kwak [2], we use cyclic network automata (CNA) to generate a decentralized protocol for dynamic coverage problems in a sensor network, with only a small fraction of sensors awake at every moment. This paper gives a rigorous analysis of CNA and shows that waves of awake-state nodes automatically solve pusuit/evasion-type problems without centralized coordination. As a corollary of this work, we unearth some interesting topological interpretations of features previously observed in cyclic cellular automata (CCA). By considering CCA over networks and completing to simplicial complexes, we induce dynamics on the higher-dimensional complex. In this setting, waves are seen to be generated by topological defects with a nontrivial degree (or winding number). The simplicial complex has the topological type of the underlying map of the workspace (a subset of the plane), and the resulting waves can be classified cohomologically. This allows one to 'program' pulses in the sensor network according to cohomology class. We give a realization theorem for such pulse waves.
AB - Following Baryshnikov-Coffman-Kwak [2], we use cyclic network automata (CNA) to generate a decentralized protocol for dynamic coverage problems in a sensor network, with only a small fraction of sensors awake at every moment. This paper gives a rigorous analysis of CNA and shows that waves of awake-state nodes automatically solve pusuit/evasion-type problems without centralized coordination. As a corollary of this work, we unearth some interesting topological interpretations of features previously observed in cyclic cellular automata (CCA). By considering CCA over networks and completing to simplicial complexes, we induce dynamics on the higher-dimensional complex. In this setting, waves are seen to be generated by topological defects with a nontrivial degree (or winding number). The simplicial complex has the topological type of the underlying map of the workspace (a subset of the plane), and the resulting waves can be classified cohomologically. This allows one to 'program' pulses in the sensor network according to cohomology class. We give a realization theorem for such pulse waves.
UR - http://www.scopus.com/inward/record.url?scp=84904628854&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84904628854&partnerID=8YFLogxK
U2 - 10.1109/IPSN.2014.6846754
DO - 10.1109/IPSN.2014.6846754
M3 - Conference contribution
AN - SCOPUS:84904628854
SN - 9781479931460
T3 - IPSN 2014 - Proceedings of the 13th International Symposium on Information Processing in Sensor Networks (Part of CPS Week)
SP - 215
EP - 224
BT - IPSN 2014 - Proceedings of the 13th International Symposium on Information Processing in Sensor Networks (Part of CPS Week)
PB - IEEE Computer Society
T2 - 13th IEEE/ACM International Conference on Information Processing in Sensor Networks, IPSN 2014
Y2 - 15 April 2014 through 17 April 2014
ER -