Time Varying Communication Networks: Modelling, Reliability Evaluation and Optimization

In recent times, there has been a tremendous research interests and growth in the direction of time varying communication networks (TVCNs) due to their widespread applications. The examples of such networks include, but not limited to, the networks like mobile ad hoc networks (MANETs), delay tolerant networks (DTNs), vehicular ad hoc networks (VANETs) and opportunistic mobile networks (OMNs). Some formidable challenges posed by such networks are long propagation delay, frequent disruption of communication between any two nodes, high error rates, asymmetric link rates, lack of end-to-end connectivity, routing, etc. Thus, it is vital for TVCN design, modelling and performance evaluation and/or comparison to assess their performance through some quantifiable metrics like packet delivery ratio (PDR), average number of link failures during the routing process, routing requests ratio, average end-to-end (E2E) delay, route lifetime and network reliability. Although a plethora of tools and techniques are available that deal with the design, modelling, analysis and assessment of reliability and other performance metrics of static networks yet the same is not true for the present days’ TVCNs. This Chapter describes extension of the reliability assessment techniques and performance metrics used for static networks to the TVCNs. More specifically, the aspects dealt in this chapter are: (i) TVCN models for representing features like mobility, links and topology, (ii) description of the notion of time-stamped-minimal path sets (TS-MPS) and time-stamped-minimal cut sets (TS-MCS) for TVCNs as an extension of MPS and MCS, respectively that are widely used in static networks, (iii) techniques for enumerating TS-MPS and TS-MCS, and evaluating reliability measure(s)-particularly two-terminal reliability, expected hop and slot counts along with some other related metrics, and (iv) discussion on several recent optimization problems in TVCNs.