Routing plays a fundamental role in network applications, but it is especially challenging in Delay Tolerant Networks (DTNs). These are a kind of mobile ad hoc networks made of, e.g., (possibly, unmanned) vehicles and humans where, despite a lack of continuous connectivity, data must be transmitted while the network conditions change due to the nodes’ mobility. In these contexts, routing is NP-hard and is usually solved by heuristic “store and forward” replication-based approaches, where multiple copies of the same message are moved and stored across nodes in the hope that at least one will reach its destination. Still, the existing routing protocols produce relatively low delivery probabilities. Here, we genetically improve two routing protocols widely adopted in DTNs, namely, Epidemic and PRoPHET, in the attempt to optimize their delivery probability. First, we dissect them into their fundamental components, i.e., functionalities such as checking if a node can transfer data, or sending messages to all connections. Then, we apply Genetic Improvement (GI) to manipulate these components as terminal nodes of evolving trees. We apply this methodology, in silico, to six test cases of urban networks made of hundreds of nodes and find that GI produces consistent gains in delivery probability in four cases. We then verify if this improvement entails a worsening of other relevant network metrics, such as latency and buffer time. Finally, we compare the logics of the best evolved protocols with those of the baseline protocols, and we discuss the generalizability of the results across test cases.

Genetic Improvement of Routing Protocols for Delay Tolerant Networks / Lorandi, Michela; Custode, Leonardo Lucio; Iacca, Giovanni. - In: ACM TRANSACTIONS ON EVOLUTIONARY LEARNING. - ISSN 2688-299X. - 1:1(2021), pp. 401-437. [10.1145/3453683]

Genetic Improvement of Routing Protocols for Delay Tolerant Networks

Custode, Leonardo Lucio;Iacca, Giovanni
2021-01-01

Abstract

Routing plays a fundamental role in network applications, but it is especially challenging in Delay Tolerant Networks (DTNs). These are a kind of mobile ad hoc networks made of, e.g., (possibly, unmanned) vehicles and humans where, despite a lack of continuous connectivity, data must be transmitted while the network conditions change due to the nodes’ mobility. In these contexts, routing is NP-hard and is usually solved by heuristic “store and forward” replication-based approaches, where multiple copies of the same message are moved and stored across nodes in the hope that at least one will reach its destination. Still, the existing routing protocols produce relatively low delivery probabilities. Here, we genetically improve two routing protocols widely adopted in DTNs, namely, Epidemic and PRoPHET, in the attempt to optimize their delivery probability. First, we dissect them into their fundamental components, i.e., functionalities such as checking if a node can transfer data, or sending messages to all connections. Then, we apply Genetic Improvement (GI) to manipulate these components as terminal nodes of evolving trees. We apply this methodology, in silico, to six test cases of urban networks made of hundreds of nodes and find that GI produces consistent gains in delivery probability in four cases. We then verify if this improvement entails a worsening of other relevant network metrics, such as latency and buffer time. Finally, we compare the logics of the best evolved protocols with those of the baseline protocols, and we discuss the generalizability of the results across test cases.
2021
1
Lorandi, Michela; Custode, Leonardo Lucio; Iacca, Giovanni
Genetic Improvement of Routing Protocols for Delay Tolerant Networks / Lorandi, Michela; Custode, Leonardo Lucio; Iacca, Giovanni. - In: ACM TRANSACTIONS ON EVOLUTIONARY LEARNING. - ISSN 2688-299X. - 1:1(2021), pp. 401-437. [10.1145/3453683]
File in questo prodotto:
File Dimensione Formato  
3453683.pdf

Solo gestori archivio

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 3.52 MB
Formato Adobe PDF
3.52 MB Adobe PDF   Visualizza/Apri
2103.07428.pdf

accesso aperto

Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.59 MB
Formato Adobe PDF
1.59 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/316147
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact