We consider the problem of placing the minimum
number of monitors in a dynamic network to identify additive
link metrics from path metrics measured along cycle-free pa
ths
between monitors. Our goal is robust monitor placement, i.e
.,
the same set of monitors can maintain network identifiabilit
y
under topology changes. Our main contribution is a set of mon
i-
tor placement algorithms with different performance-comp
lexity
tradeoffs that can simultaneously identify multiple topol
ogies
occurring during the network lifetime. In particular, we sh
ow that
the optimal monitor placement is the solution to a generaliz
ed
hitting set problem, for which we provide a polynomial-time
algo-
rithm to construct the input and a greedy algorithm to select
the
monitors with logarithmic approximation. Although the opt
imal
placement is NP-hard in general, we identify non-trivial sp
ecial
cases that can be solved efficiently. Our secondary contribu
tion
is a dynamic triconnected decomposition algorithm to compu
te
the input needed by the monitor placement algorithms, which
is the first such algorithm that can handle edge deletions. Ou
r
evaluations on mobility-induced dynamic topologies verif
y the
efficiency and the robustness of the proposed algorithms.