  We consider a dynamical linear network where nearest neighbours communicate
via links whose states form binary (open/closed) valued independent and
identically distributed Markov processes. Our main result is the tight
information-theoretic lower bound on the network traffic required by the
connection state overhead, or the information required for all nodes to know
their connected neighbourhood. These results, and especially their possible
generalisations to more realistic network models, could give us valuable
understanding of the unavoidable protocol overheads in rapidly changing Ad hoc
and sensor networks.
