Συνδυασμένη σχεδίαση αλγόριθμων δρομολόγησης, χρονοδρομολόγησης και ελέγχου ισχύος για ασύρματα αδόμητα δίκτυα

Abstract

Η ανάπτυξη των ασύρματων αδόμητων δικτύων (ad-hoc networks) τα τελευταία ήταν ραγδαία. Ο αριθμός των εφαρμογών στις οποίες μπορούμε να εφαρμόσουμε την τεχνολογία των αδόμητων δικτύων είναι αρκετά μεγάλος. Το πρώτο πράγμα που πρέπει να εξεταστεί πάνω στην συγκεκριμένη κατηγορία δικτύων είναι τα προβλήματα που αντιμετωπίζουμε εδώ και ο τρόπος επίλυσής τους. Φυσικά πολλά από αυτά τα προβλήματα δεν έχουν ακόμα επιλυθεί. Το κύριο πρόβλημα που έχουμε να αντιμετωπίσουμε σε ένα αδόμητο δίκτυο είναι η διάρκεια ζωής του ίδιου του δικτύου. Οι κινητοί χρήστες του δικτύου λειτουργούν με την χρήση συσσωρευτών (μπαταρίες) πεπερασμένης διάρκειας ζωής. Από την στιγμή που κάποιος συσσωρευτής εξαντληθεί παύει να υπάρχει και ο χρήστης στον οποίο ανήκει. Όλες οι διαδικασίες που γίνονται σε κάποιο κόμβο χρειάζονται ενέργεια για να περατωθούν. Έτσι κύριος στόχος μας θα πρέπει να είναι η όσον το δυνατόν μικρότερη κατανάλωση ισχύος στους διάφορους κόμβους του δικτύου. Η έλλειψη κάποιου κεντρικού κόμβου που να συντονίζει όλους τους άλλους κόμβους του δικτύου και συνάμα να αποφασίζει για λειτουργίες όπως η δρομολόγηση, η χρονοδρομολόγηση και ο έλεγχος ισχύος χαρακτηρίζει όλα τα αδόμητα δίκτυα. Επίσης η συνεχής αλλαγή στην τοπολογία του δικτύου κάνει ακόμα mo δύσκολη την επιλογή των διαδρομών που θα χρησιμοποιήσουμε για επικοινωνία. Στην διπλωματική εργασία που ακολουθεί προσπαθούμε να βρούμε αλγορίθμους που συνδυάζουν τις διαδικασίες της δρομολόγησης, χρονοδρομολόγησης και ελέγχου ισχύος, με απώτερο στόχο την όσο το δυνατόν μεγαλύτερη εξοικονόμηση ισχύος. Μεγάλο ποσοστό της ισχύς των κινητών κόμβων του δικτύου καταναλώνεται κατά την διαδικασία της δρομολόγησης των δεδομένων. Θα πρέπει να εξετάσουμε διάφορους συνδυασμούς των παραπάνω παραμέτρων (καθώς και τον συνδυασμό και των τριών παραμέτρων) για να ήμαστε στη συνέχεια σε θέση να επιλέξουμε την διαδικασία που μας αποφέρει την μικρότερη κατανάλωση ισχύς. Αρχικά θα εξετάσουμε τα ασύρματα αδόμητα δίκτυα, τα χαρακτηριστικά τους και τον τρόπο με τον οποίο αυτά λειτουργούν (κεφάλαιο 1). Στη συνέχεια έχουμε την μελέτη των διαδικασιών ελέγχου ισχύος, δρομολόγησης και χρονοδρομολόγησης (κεφάλαιο 2). Προσπαθούμε να βρούμε τον τρόπο λειτουργίας αυτών των παραμέτρων και το πώς επηρεάζει καθεμία από αυτές ξεχωριστά την συνολική κατανάλωση ενέργειας του δικτύου. Στο κεφάλαιο 3, έχουμε τους ανά δύο συνδυασμούς αυτών παραμέτρων, όπως επίσης και τον συνδυασμό και των τριών παραμέτρων. Επικεντρωνόμαστε σε κάποιες τεχνικές που ήδη υπάρχουν και τις οποίες στη συνέχεια προσπαθούμε να τις εφαρμόσουμε και στις δικές μας μελέτες (π.χ. τους αλγορίθμους χρονοδρομολόγησης της μελέτης [4]). Στα κεφάλαια 4 και 5 έχουμε το πρακτικό κομμάτι της εργασίας μας. Αρχικά στο 4 κεφάλαιο έχουμε την περιγραφή τριών εναλλακτικών αλγορίθμων που προσπαθούν μέσα από έλεγχο ισχύος, δρομολόγηση και χρονοδρομολόγηση να εξοικονομήσουν όσο το δυνατόν μεγαλύτερα ποσά ενέργειας κατά την εκπομπή των δεδομένων. Στη συνέχεια έχουμε την μελέτη δύο επιπλέον αλγορίθμων, οι οποίες δεν συνδυάζουν και τις τρεις παραπάνω παραμέτρους. Στην τέταρτο αλγόριθμο εκτελούμε έλεγχο ισχύος και χρονοδρομολόγηση ενώ στον πέμπτο αλγόριθμο κάνουμε μόνο έλεγχο ισχύος. Τους δύο αυτούς αλγορίθμους τους παραθέτουμε για να έχουμε ένα μέτρο σύγκρισης των αποτελεσμάτων τους, με τα αποτελέσματα των προηγούμενων τριών αλγορίθμων που κατασκευάσαμε. Στο κεφάλαιο 5 έχουμε τα αποτελέσματα από την εκτέλεση των προηγούμενων αλγορίθμων- προσεγγίσεων καθώς και τα γραφήματα της συνολικής καταναλισκόμενης ισχύς που έχουμε σε κάθε μία από αυτές τις περιπτώσεις. Τέλος στο κεφάλαιο 6 ακολουθούν κάποια συμπεράσματα από την όλη μελέτη που έγινε, όπως επίσης και άξονες για μελλοντική μελέτη και βελτιώσεις πάνω στους πέντε αλγορίθμους μας.