. In particular, we show an $\Omega \left(n^2/k^2\tau\log n\right)$ lower bound for the global broadcast in $T$-interval $k$-connected radio networks against a $\tau$-oblivious adversary for $\tau \geq 1$.      

\begin{theorem}\label{thm:lowerbound-k-connect}
There exists a $T$ interval $k$ connected radio network such that any randomized algorithm requires at least $\Omega \left(\frac{n^2}{k^2\tau\log n}\right)$ time to solve global broadcast against a $\tau$-oblivious adversary, where $1 \leq T \leq \left(\frac{n}{k}\right)^{1-\varepsilon}$ for some constant $\varepsilon$. 
\end{theorem}
\begin{proof}[Proof sketch]
Given a $n$-node graph $G$, we can always construct a new graph of $nk$ nodes replacing each node of $G$ by a clique of size $k$. Assume the above $\tau$-dual $T$-interval $1$-connected radio network of $n/k$ nodes. Then replace every node in this graph by a clique of size $k$ and for each edge, add complete bipartite connection between two cliques. See the Figure~\ref{fig:fragment-graph}. Clearly this new graph has $n$ nodes in total and it is $k$ connected. Hence the $\tau$-dual $T$-interval $1$-connected graph of size $n$ is equivalent (i.e., has similar structure) to a $\tau$-dual $T$-interval $k$-connected graph of size $n/k$. Therefore, we can apply the same reduction from the $(\alpha,\beta,l,\varphi)$-periodic hitting game to get a lower bound  $\Omega \left(\frac{n^2}{k^2\tau\log n}\right)$ of the global broadcast problem in $\tau$-dual $T$-interval $k$-connected radio networks.  
\end{proof}

The impossibility result is also valid even with the collision detection. The strongly adaptive adversary knows the random choices of the algorithm in the current round and  
}



\section{Introduction}
\label{sec:intro}

By now, a rich theory on algorithms for large-scale wireless networks
exists and we have a rather precise understanding of the complexity of
many basic computation and communication tasks for a variety of
wireless network models. While many wireless communication models and
modeling assumptions have been studied, to a large part, the
considered models all share one basic property. Most of the existing
work is based on static networks and on communication models where
wireless signal reception is modeled in a completely deterministic
way. For example, in the classic radio network model, a wireless
network is modeled as a graph and a node in the graph can receive a
message transmitted by some neighbor if and only if no other neighbor
transmits at the same time, e.g., \cite{bgi1,moscibroda05}. In the
SINR (or physical) model, nodes have fixed coordinates in some
geometric space and a transmitted signal can be successfully received
if and only if the signal-to-noise-and-interference ratio at the
receiver is above a certain fixed threshold, e.g.,
\cite{gupta:2000,moscibroda06}.

The situation in actual networks however is quite different and
wireless signal reception might behave in a rather unpredictable
way. There can be multiple sources for interference which cannot be
controlled by a distributed algorithm and signal propagation depends
on various properties of the environment. As a result, we often obtain
wireless communication links with unreliable behavior
\cite{kim06,newport:2007,ramachandran07,srinivasan08,yarvis02}. In
addition, wireless devices might be mobile leading to a potentially
completely dynamic network topology.

As a consequence, in recent years, researchers in the wireless
algorithms community have also started to consider radio network
models which exhibit nondeterministic behavior and sometimes general
dynamic topologies, e.g.,
\cite{structuringDG,clementi09,clementi12,fernandezanta12,dualgraph,obliviousDG}.
In the present paper, we continue this line of research and study the
global broadcast problem in dynamic radio networks for a range of
modeling assumptions. Note that in ordinary, static radio networks,
albeit appearingly simple, global broadcast is one of the best studied
problems in the area, (see, e.g.,
\cite{bgi2,bgi1,chlamtac:1985,jurdzinski14,newport-hitting} and many
others). We model a dynamic network by applying the dynamic network
model introduced in \cite{kuhn_stoc10}. Time is divided into
synchronous rounds and a wireless network is modeled as a dynamic
graph with a fixed set of $n$ nodes and a set of edges which can
change from round to round. For two parameters $T\geq 1$ and
$k\geq 1$, a dynamic graph is called \emph{$T$-interval $k$-connected}
if for any interval of $T$ consecutive rounds, the set of edges which
are present throughout these $T$ rounds induces a graph with vertex
connectivity at least $k$ (in \cite{kuhn_stoc10}, the model was only
introduced for $k=1$). We refer to \cite{kuhn:2011:survey} for a more
thorough discussion of the model of \cite{kuhn_stoc10} and of several
earlier related dynamic network models (e.g.,
\cite{avin08,baumann09,clementi09,odell05}).

Communication is modeled by using the standard
radio network model. In each round, each node can either transmit a message or
listen. A listening node successfully receives a message transmitted
by a neighbor in the current graph if and only if no other neighbor
transmits in the same round. We assume that nodes cannot detect
collisions, i.e., whether $0$ or more than $1$ neighbors transmit is
indistinguishable for a listening node. Note that the described
dynamic network model does not only allow to model topology changes
due to arbitrary node mobility. It also allows to model unreliable
links where the presence/availability can change for various reasons.

We assume that the dynamic graph is provided by a worst-case
adversary. As we study randomized distributed protocols, we need to
specify to what extent the adversary can adapt to the random decisions
of the nodes when determining the sequence of network topologies. For
the adaptiveness of the adversary, we use a more fine-grained
classification than what is usually done. For an integer parameter
$\tau\geq 0$, we say that the adversary is $\tau$-oblivious if for
determining the graph in round $r$, the adversary knows the randomness
of all nodes of all the rounds up to round $r-\tau$. Typically, only
the extreme cases are studied. An adversary which does not have access
to the random decisions of the algorithm (i.e., $\tau=\infty$) is
called an \emph{oblivious} adversary, whereas an adversary which has
access to the randomness of the algorithm is called an \emph{adaptive}
adversary. If the adversary even has access to the randomness of the
current round ($\tau=0$), it is called \emph{strongly adaptive},
otherwise ($\tau=1$), it is called \emph{weakly adaptive}. For more
precise formal definitions of the modeling assumptions, we refer to
\cref{sec:model}.

In our paper, we consider the problem of broadcasting a single message
from a source node to all the nodes of a dynamic network. The most
relevant previous work in the context of the present work appeared in
\cite{clementi09,obliviousDG,dualgraph}. In \cite{clementi09}, it is
shown that in $1$-interval $1$-connected networks (i.e., the graph is
connected in every round)\footnote{In \cite{clementi09}, the
  connectivity condition on the dynamic network is phrased differently
  and slightly more general.}, the complexity of global broadcast for
a $1$-oblivious adversary is $\Theta(n^2/\log n)$. In \cite{dualgraph}
and \cite{obliviousDG}, $\infty$-interval $1$-connected graphs are
considered (i.e., there is a stable connected subgraph which is
present throughout the whole execution). In \cite{dualgraph}, it is
shown that even for a $0$-oblivious adversary, it is possible to solve
broadcast in $O(n\log^2 n)$ rounds and it is shown that $\Omega(n)$
rounds are necessary even if the stable connected subgraph has
diameter $2$. In \cite{obliviousDG}, it is shown that when only
assuming an $\infty$-oblivious adversary, the running time can be
improved to $O((D+\log n)\log n)$, where $D$ is the diameter of the
stable connected subgraph. Note that in this case,