On Verifying and Maintaining Connectivity of Interval Temporal Networks

Akrida, Eleni C.; Spirakis, Paul G.

Abstract

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 [x, y], if it is connected for all time instances t∈[x,y] (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 [x, y]; the algorithm also considers the components of the network that start as large at time t=x but dis-connect into small components within the time interval [x, y], and answers how long after time t=x these 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 randomised 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.

Citation

Akrida, E. C., & Spirakis, P. G. (2015, December). On Verifying and Maintaining Connectivity of Interval Temporal Networks. Presented at Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), Patras, Greece

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS)
• Acceptance Date: Jul 20, 2015
• Online Publication Date: Jan 1, 2016
• Publication Date: 2015
• Deposit Date: Oct 25, 2021
• Publicly Available Date: Oct 26, 2021
• Print ISSN: 0302-9743
• Volume: 9536
• Pages: 142-154
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithms for Sensor Systems
• ISBN: 9783319284712
• DOI: https://doi.org/10.1007/978-3-319-28472-9_11
• Public URL: https://durham-repository.worktribe.com/output/1139648