Υλοποιηση, Μελετη Και Αναλυση Επιδοσης Αλγοριθμων Κατανομης Φασματος Για Dvb-t Allotments

Abstract

Εδώ και δύο περίπου χρόνια έχει ξεκινήσει μια προσπάθεια για το σχεδιασμό του πλάνου συχνοτήτων επίγειας ψηφιακής τηλεόρασης (DVB-T) για την Ευρώπη, την Αφρική και μεγάλο μέρος της Ασίας. Η διαδικασία του σχεδιασμού περιλαμβάνει δύο στάδια: Το πρώτο είναι το στάδιο της ανάλυσης, με το οποίο γίνεται η οριοθέτηση κάποιων περιοχών (allotments) και ο έλεγχος συμβατότητας μεταξύ τους. Το αποτέλεσμα αυτής της ανάλυσης είναι ένας γράφος ασυμβατοτήτων, ο οποίος περιγράφει ποιες περιοχές μπορούν να χρησιμοποιούν ταυτόχρονα το ίδιο κανάλι συχνοτήτων και ποιες όχι. Το δεύτερο στάδιο είναι το στάδιο της σύνθεσης και αφορά στην εύρεση μιας κατανομής συχνοτήτων η οποία θα εξασφαλίζει ότι οι περιορισμοί που περιγράφονται με το γράφο ασυμβατοτήτων δε θα παραβιάζονται και παράλληλα θα γίνεται αποδοτική χρήση του φάσματος. Σκοπός αυτής της διπλωματικής είναι η υλοποίηση, μελέτη και ανάλυση επίδοσης αλγορίθμων για τη βέλτιστη κατανομή των 49 καναλιών που χρησιμοποιούνται για DVB-T στη ζώνη συχνοτήτων UHF, από τα 470 μέχρι τα 862 MHz. Οι αλγόριθμοι που υλοποιήθηκαν γι’ αυτό το σκοπό είναι η Προσομοιωμένη Ανόπτηση, η Αναζήτηση με Απαγορευμένες Καταστάσεις, μια περίπτωση Γενετικού Αλγόριθμου, καθώς και μια σειρά Ακολουθιακών Αλγορίθμων.Το πρόβλημα που εξετάζουμε εδώ είναι μια ειδική περίπτωση αυτού που είναι γνωστό ως FAP (Frequency Assignment Problem). Μια σύντομη περιγραφή του FAP μπορεί να βρεθεί στο κεφάλαιο 2, ενώ η αναγκαιότητα για εκχώρηση συχνοτήτων για το DVB-T αναλύεται στο κεφάλαιο 1. Το κεφάλαιο 3 είναι αφιερωμένο στην περιγραφή των τεσσάρων αλγορίθμων που υλοποιήθηκαν. Στο επόμενο κεφάλαιο αναλύεται αρχικά η εφαρμογή των αλγορίθμων για την εύρεση του ελάχιστου αριθμού καναλιών που απαιτείται για την κάλυψη μιας περιοχής (Minimum Span), ενώ στη συνέχεια περιγράφεται μια πρωτότυπη μέθοδος που υλοποιήθηκε στα πλαίσια αυτής της εργασίας για την ανάθεση καναλιών σε allotments χρησιμοποιώντας τους αλγόριθμους αυτούς. Στο πέμπτο κεφάλαιο, αφού πρώτα παρουσιάσουμε τα αποτελέσματα, αναλύουμε την επίδοση των αλγορίθμων και επιχειρούμε μια σύγκριση μεταξύ τους. Στο τελευταίο κεφάλαιο συζητούνται τα βασικά συμπεράσματα που προκύπτουν από την παρούσα εργασία καθώς και πιθανές μελλοντικές βελτιώσεις στις χρησιμοποιούμενες μεθόδους.