Backbones for military multilayer wireless ad hoc networks based on networks science concepts

Abstract

In the context of the present thesis we focus on Military multilayer wireless networks and invest on the ad hoc network paradigm to improve their performance. We envision these Tactical wireless networks as having layers of Mobile Ad hoc Networks (MANETS) which will be all connected together as part of a seamless overarching network, allowing information, from multiple sources, to flow faster among its participants. Towards the implementation of this vision first we build on the (minimum) Connected node Dominating Sets theory and propose novel distributed algorithms to efficiently connect multilayer ad hoc networks so as to reduce their latency, improve their scalability and increase their lifetime.Then, we investigate the problem of distributed computation of a resilient network overlay for communication link monitoring in multilayer ad hoc networks. A hard to address problem, especially using distributed algorithms, because of coordination failures related to the multilayer environment which can lead to loss of communication between the network layers or over-dependence on a specific layer. In order to solve this problem we build on the (minimum) Edge Dominating Sets theory and propose novel distributed algorithms which calculate, for purposes of either network management/monitoring, an overlay with high numbers of inter-layer links, so as to the communication among different layers not to break easily (accidentally or due to malicious attacks).The main contributions of the present dissertation are: It is introduced the problem of calculating (minimum) connected node dominating sets (MCDS) in multilayer networks which has not been considered in the literature so far. In this context, we prove that decomposition-based and aggregation-based approaches for dominating set calculation in multilayer networks will not work and highlight the significance of assessing and exploiting each node’s intra- and inter-layer links in order to be considered as candidate members of DS. Thus, we propose a family of centrality measures able to rank a multilayer node, with respect to its “strategic” position in the multilayer network. We also develop distributed algorithms for calculating the connected dominating set which exhibit superior performance compared to other widely used algorithms.It is introduced the novel problem of finding (minimum) connected edge dominating sets(MCEDS) in multilayer networks. We prove that the problem of finding the MCEDS in a multilayer network is NP-hard and we propose a centrality measure-based technique that provides to multilayer network nodes awareness about the significance of the edges that are adjacent to them. We develop also distributed algorithms that heuristically calculate the MCEDS. Moreover, it is proposed a new trajectory prediction scheme for use in the Vehicle Ad hoc Network environment, which builds in a purely distributed fashion a rich summary of a vehicles’ roaming history that subsequently is used to provide online accurate predictions. We compare the proposed method against several, model independent and highly accurate prediction algorithms and the results affirm its superior performance.

Στο πλαίσιο της παρούσας διδακτορικής διατριβής εστιάζουμε στα στρατιωτικά πολυεπίπεδα ασύρματα δίκτυα και επενδύουμε στην τεχνολογία των ad hoc δικτύων προκειμένου να βελτιώσουμε την απόδοση τους. Οραματιζόμαστε τα Τακτικά ασύρματα δίκτυα να απαρτίζονται από στρώματα ad hoc δικτύων με κινούμενους κόμβους, τα οποία είναι αδιαφανώς συνδεδεμένα μεταξύ τους ως μέρος ενός απρόσκοπτου υπερδικτύου το οποίο επιτρέπει την άμεση ροή πληροφοριών μεταξύ των κόμβων του.Για την υλοποίηση αυτού του οράματος αρχικά βασιζόμαστε στη θεωρία των Connected node Dominating Sets (CDS) και προτείνουμε καινοτόμους αλγόριθμους οι οποίοι επιτυγχάνουν κατανεμημένα αποτελεσματική σύνδεση των ανωτέρω πολυεπίπεδων ad hoc δικτύων ώστε να μειωθεί η καθυστέρηση τους (latency), να βελτιωθεί η επεκτασιμότητά τους (scalability) και να αυξηθεί η διάρκεια της ζωής τους. Στη συνέχεια εξετάζουμε το πρόβλημα της αποτελεσματικής και ταυτόχρονα κατανεμημένης παρακολούθησης της διακίνησης δεδομένων εντός του πολυεπίπεδου ad hoc δικτύου. Ένα δύσκολο πρόβλημα, ιδιαίτερα αν αυτό πρόκειται να επιλυθεί μέσω της χρήσης κατανεμημένων αλγορίθμων, λόγω των προβλημάτων συντονισμού που έχουν να κάνουν με το πολυεπίπεδο περιβάλλον καθώς δύνανται να οδηγήσουν είτε σε απώλεια επικοινωνίας μεταξύ των επιπέδων του δικτύου είτε σε υπερβολική εξάρτηση αυτού από ένα συγκεκριμένο επίπεδό του. Για την επίλυση του συγκεκριμένου προβλήματος επενδύουμε στη θεωρία των Connected edge Dominating Sets (CEDS) και προτείνουμε νέους κατανεμημένους αλγορίθμους οι οποίοι υπολογίζουν για σκοπούς διαχείρισης ή/και παρακολούθησης του πολυεπίπεδου δικτύου μία επικάλυψη (overlay) αυτού η οποία εμπεριέχει μεγάλο αριθμό από διασυνδέσεις μεταξύ των επιπέδων του δικτύου έτσι ώστε η επικοινωνία μεταξύ αυτών να μη διακόπτεται εύκολα (είτε κατά λάθος είτε λόγω κακόβουλων επιθέσεων).Οι κύριες συνεισφορές της παρούσας διατριβής είναι: Παρουσιάζεται το πρόβλημα του υπολογισμού του (Minimum) Connected node Dominating Set (MCDS) σε πολυεπίπεδα δίκτυα το οποίο δεν έχει εξεταστεί μέχρι στιγμής στη βιβλιογραφία. Αποδεικνύουμε ότι, οι προσεγγίσεις είτε για επίλυση του συγκεκριμένου προβλήματος με βάση την αποσύνθεση του πολυεπίπεδου δικτύου στα επιμέρους επίπεδά του είτε για συσσωμάτωση των επιπέδων του ώστε αυτά επί της ουσίας να μην υφίστανται δε θα φέρουν το επιθυμητό αποτέλεσμα και τονίζουμε την ανάγκη για αξιολόγηση αλλά και περαιτέρω εκμετάλλευση των διασυνδέσεων που διαθέτουν οι κόμβοι του δικτύου ώστε αυτοί να θεωρηθούν ως υποψήφια μέλη του DS. Στο πλαίσιο αυτό, προτείνουμε μία ομάδα από μέτρα για τη μέτρηση της σημαντικότητας του κάθε κόμβου εντός του πολυεπίπεδου δικτύου ώστε να προσδιοριστεί η στρατηγική θέση καθενός από αυτούς. Επίσης, προτείνουμε αλγόριθμους οι οποίοι υπολογίζουν κατανεμημένα το επιζητούμενο MCDS και παρουσιάζουν ανώτερη απόδοση σε σύγκριση με άλλους ευρέως χρησιμοποιούμενους αλγόριθμους.Παρουσιάζεται επίσης, το πρόβλημα της εύρεσης (Minimum) Connected Edge Dominating Set (MCEDS) σε πολυεπίπεδα δίκτυα. Αποδεικνύουμε ότι, το συγκεκριμένο πρόβλημα είναι NP-hard και προτείνουμε μία τεχνική η οποία προσδίδει στους κόμβους του πολυεπίπεδου δικτύου αντίληψη αναφορικά με τη σπουδαιότητα των ακμών που ακουμπούν σε πάνω σε αυτούς. Επιπρόσθετα, προτείνουμε νέους ευριστικούς αλγόριθμους οι οποίοι υπολογίζουν κατανεμημένα το MCEDS. Προτείνεται επίσης, ένας καινοτόμος αλγόριθμος πρόβλεψης για χρήση στο περιβάλλον των Vehicle Ad hoc Networks (VANETs) ο οποίος με καθαρά κατανεμημένο τρόπο και λαμβάνοντας υπόψη του την ιστορία κίνησης ενός οχήματος πραγματοποιεί online ακριβείς προβλέψεις αναφορικά με τη μελλοντική τροχιά του. Η προτεινόμενη μέθοδος συγκρίνεται με αντίστοιχους, υψηλής ακρίβειας, αλγόριθμους πρόβλεψης και τα αποτελέσματα επιβεβαιώνουν την ανωτερότητα της.