On Verifying and Maintaining Connectivity of Interval Temporal Networks
On Verifying and Maintaining Connectivity of Interval Temporal Networks
复制标题
DOI：
10.1007/978-3-319-28472-9_11
复制
发表时间：
2015-09
期刊：
影响因子：
--
通讯作者：
Eleni C. Akrida;P. Spirakis
中科院分区：
文献类型：
--
作者：
Eleni C. Akrida;P. Spirakis
区间时间网络，通俗地说，是一个网络，其链接随时间变化。术语间隔意味着链接可能存在一个或多个时间间隔，称为链接的可用性间隔，在此之后它将不存在（可能直到它再次开始可用的另一个时刻）。在该模型中，我们考虑了连续时间和高速（瞬时）信息传播。如果所有时间实例（瞬时连接）都连接，则间隔时间网络在一段时间内连接。在这项工作中，我们研究了区间时间网络的瞬时连通性问题。我们提供了一个多项式时间算法来回答给定的间隔时间网络是否在一个时间段内连接。如果网络在给定的时间段内没有连接，那么我们也给出了一个多项式时间算法，该算法返回网络中保持连接并在此期间保持较大的大型组件；该算法还考虑了网络中那些开始时很大，但在时间间隔内断开为小组件的组件，并回答了这些组件在一段时间后保持连接和大的时间。最后，我们研究了树形图上的间隔时间网络的一个例子，其中链路的寿命和网络连接的故障不受我们的控制；然而，我们可以为网络“提供”额外的边，当故障发生时，这些边可以将其重新连接到树中，以便在一段时间内保持其连通性。我们表明，通过使用随机方法使这些额外的边可用于重新连接，我们可以在很长一段时间内以高概率保持网络的连通性。我们的方法在边缘可用性的设计上也节省了一些成本；在这里，成本是所有额外边的可用性到重新连接间隔长度的总和。
An interval temporal network is, informally speaking, a network whose links change with time. The term interval means that a link may exist for one or more time intervals, called availability intervals of the link, after which it does not exist (until, maybe, a further moment in time when it starts being available again). In this model, we consider continuous time and high-speed (instantaneous) information dissemination. An interval temporal network is connected during a period of time, if it is connected for all time instances(instantaneous connectivity). In this work, we study instantaneous connectivity issues of interval temporal networks. We provide a polynomial-time algorithm that answers if a given interval temporal network is connected during a time period. If the network is not connected throughout the given time period, then we also give a polynomial-time algorithm that returns large components of the network that remain connected and remain large during; the algorithm also considers the components of the network that start as large at timebut dis-connect into small components within the time interval, and answers how long after timethese components stay connected and large. Finally, we examine a case of interval temporal networks on tree graphs where the lifetimes of links and, thus, the failures in the connectivity of the network are not controlled by us; however, we can “feed” the network with extra edges that may re-connect it into a tree when a failure happens, so that its connectivity is maintained during a time period. We show that we can with high probability maintain the connectivity of the network for a long time period by making these extra edges available for re-connection using a randomized approach. Our approach also saves some cost in the design of availabilities of the edges; here, the cost is the sum, over all extra edges, of the length of their availability-to-reconnect interval.