Analysis of probabilistic information dissemination in wireless networks employing algebraic graph theory elements

Abstract

Information dissemination constitutes a large field of study in the scientific community. In the past, the networks consisted mainly of a relatively small number of nodes with a preconstructed structure and hierarchy. Over the years, both their form and their size have been changed radically resulting in unstructured large-scale networks with high node mobility. Therefore, information dissemination in modern networks is a bigger challenge comparing to the past, because of the large scale and the high complexity of this process. Approaches like traditional flooding, are not suitable in modern networks due to the large number of transmitted information messages that waste valuable resources. In order to increase network’s lifetime, it is necessary to disseminate information in a way that minimizes unnecessary transmissions and at the same time maximizes the number of nodes that receives it. The purpose of this dissertation is to find optimized algorithms for disseminating information in modern networks that saves valuable resources and increases network’s lifetime.

Η διάχυση πληροφοριών στα δίκτυα, αποτελούσε και αποτελεί ένα από τα μεγαλύτερα πεδία μελέτης της επιστημονικής κοινότητας. Κατά το παρελθόν, τα δίκτυα απαρτίζονταν κυρίως από ένα σχετικά μικρό αριθμό κόμβων με προκαθορισμένη δομή και ιεραρχία. Με το πέρασμα των χρόνων, τόσο η μορφή τους όσο και το μέγεθός τους άλλαξαν ριζικά. Έτσι σήμερα έχουμε δίκτυα πολύ μεγάλου μεγέθους τα οποία χαρακτηρίζονται από υψηλή κινητικότητα των κόμβων τους, από την ανυπαρξία προκαθορισμένης δομής αλλά και από το γεγονός ότι στις περισσότερες των περιπτώσεων υπάρχει ισοτιμία μεταξύ των κόμβων. Η διάχυση επομένως μιας πληροφορίας σε ένα σύγχρονο δίκτυο, αποτελεί μεγαλύτερη πρόκληση συγκριτικά με το παρελθόν, αφού υπεισέρχονται νέοι παράγοντες που αυξάνουν την πολυπλοκότητα της διαδικασίας. Μέθοδοι όπως το κλασσικό flooding δεν μπορούν να εφαρμοστούν στα σημερινά δίκτυα, αφού οι άσκοπες μεταδόσεις μηνυμάτων σπαταλούν πολύτιμους πόρους. Είναι επομένως αναγκαίο, η διάχυση της πληροφορίας να γίνεται με τέτοιο τρόπο ώστε να ελαχιστοποιούνται οι άσκοπες μεταδόσεις και ταυτόχρονα να μεγιστοποιείται ο αριθμός των κόμβων που τελικά την έχουν λάβει. Σκοπός της συγκεκριμένης διατριβής θα είναι η εύρεση βελτιστοποιημένων αλγόριθμων για την διάχυση των πληροφοριών στα σύγχρονα δίκτυα, με τρόπους οι οποίοι θα εξοικονομούν πολύτιμους πόρους, αυξάνοντας έτσι την διαθεσιμότητα των κόμβων και την διάρκεια ζωής του δικτύου.