Αλγόριθμοι χρονοδρομολόγησης για ασύρματα συστήματα εκπομπής δεδομένων

Abstract

Data broadcasting has emerged as an efficient means for the dissemination of information over asymmetric wireless networks. Examples of data broadcasting applications are traffic information, weather information, news distribution systems, sightseeing applications. In such applications, client needs for data items are usually overlapping. Consequently, broadcasting seems to be an efficient solution, as the broadcast of a single information item will likely satisfy a (possibly large) number of client requests. In this thesis, four scheduling algorithms for wireless data broadcasting systems, and more specifically for wireless push systems, that are able to adapt their broadcast schedule to the characteristics of the environments where they operate, are proposed. The proposed algorithms achieve high performance and are able to adapt efficiently to the demands of the operational environment. Firstly, a wireless push system for environments with unequal client group sizes and different service priority levels is proposed. Taking into account the population and the priority level of each group, the broadcast server forms the broadcast schedule of the system so that fair service for all clients along with efficient service of the different priority levels of the system are achieved. In another system, the use of smart antennas at the broadcast server, instead of directional antennas with fixed beamwidth is proposed. The ability of smart antennas to change their beamwidth is exploited so that the coverage area of each antenna is changed according to the current placement of clients within the system. The simulation results reveal that the use of smart antennas instead of the fixed-beadmwidth antennas has led to a significant improvement of the system’s performance. Furthermore, a distributed adaptive push system is proposed. The novelty of the introduced system has to do with the replacement of the single centralized learning automaton of the broadcast server with a number of distributed learning automata that are equal to the number of clients’ groups. The proposed scheme seems to be more sensitive concerning the various client demands compared to the centralized one. The simulation results show that the proposed distributed scheme is more efficient and more fair compared to the centralized one. Finally, in this thesis, the use of Hidden Markov Models has been introduced for the first time as a prediction module of the client demands in a wireless push system. The proposed system uses a predictive module based on the Hidden Markov Model aided by a set of history vectors. The outcome of the Hidden Markov Models is used to conduct a schedule of the forthcoming server’s broadcasts. The simulation results reveal that the proposed scheme succeeds accurate predictions of the clients’ demands, resulting in an efficient operation of the system.

Η εκπομπή δεδομένων αποτελεί μία αποτελεσματική μέθοδο διανομής πληροφοριών σε ασύμμετρα ασύρματα δίκτυα. Χαρακτηριστικά παραδείγματα εφαρμογών εκπομπής δεδομένων αποτελούν οι εφαρμογές ενημέρωσης της κίνησης των δρόμων, πρόγνωσης καιρού, διανομής ειδήσεων, ξενάγησης. Σε τέτοιου είδους εφαρμογές, οι απαιτήσεις των πελατών αναφορικά με τις μεταδιδόμενες πληροφορίες είναι συνήθως αλληλεπικαλυπτόμενες. Συνεπώς, η εκπομπή δεδομένων φαίνεται να είναι η πιο αποδοτική λύση καθώς η εκπομπή ενός πακέτου πληροφορίας είναι πιθανό να ικανοποιήσει ένα (πιθανώς μεγάλο) αριθμό πελατών. Στην παρούσα διατριβή προτείνονται τέσσερις αλγόριθμοι χρονοδρομολόγησης για ασύρματα συστήματα εκπομπής δεδομένων και ειδικότερα για ασύρματα συστήματα ώθησης δεδομένων με δυνατότητα προσαρμογής των προγραμμάτων εκπομπής τους στα χαρακτηριστικά του περιβάλλοντος στο οποίο λειτουργούν. Οι προτεινόμενοι αλγόριθμοι εξασφαλίζουν υψηλή απόδοση και δυνατότητα αποτελεσματικής προσαρμογής στις απαιτήσεις του περιβάλλοντος λειτουργίας τους. Αρχικά, προτάθηκε ένα ασύρματο σύστημα ώθησης για περιβάλλοντα με άνισα μεγέθη ομάδων πελατών και διαφορετικά επίπεδα προτεραιότητας εξυπηρέτησης της κάθε ομάδας. Λαμβάνοντας υπόψη το μέγεθος και το επίπεδο προτεραιότητας της κάθε ομάδας, ο εξυπηρετητής εκπομπής διαμορφώνει το πρόγραμμα εκπομπής του συστήματος με τέτοιο τρόπο ώστε να εξασφαλίζεται η δίκαιη εξυπηρέτηση όλων των ομάδων και να εξυπηρετούνται αποτελεσματικά τα διαφορετικά επίπεδα προτεραιότητας. Στην συνέχεια, προτάθηκε η χρήση έξυπνων κεραιών, αντί κεραιών σταθερού εύρους δέσμης στον εξυπηρετητή εκπομπής ενός προσαρμοστικού συστήματος ώθησης. Αξιοποιώντας την ιδιότητα των έξυπνων κεραιών να τροποποιούν το εύρος δέσμης τους, η περιοχή κάλυψης της κάθε κεραίας τροποποιείται ανάλογα με την τρέχουσα κατανομή των ομάδων των πελατών. Τα αποτελέσματα των προσομοιώσεων έδειξαν ότι, η αντικατάσταση των κεραιών σταθερού εύρους δέσμης με έξυπνες κεραίες, οδήγησε σε σημαντική βελτίωση της απόδοσης του συστήματος. Ακόμα, προτάθηκε ένα κατανεμημένο προσαρμοστικό σύστημα ώθησης. Η καινοτομία του συστήματος αυτού έγκειται στην αντικατάσταση του μοναδικού μανθάνοντος αυτομάτου του σταθμού βάσης από ένα σύνολο κατανεμημένων μανθάνοντων αυτομάτων, τόσα σε αριθμό όσες και οι ομάδες των πελατών που εξυπηρετεί ο εξυπηρετητής εκπομπής. Η χρήση κατανεμημένων αυτομάτων καθιστά το σύστημα πιο ευαίσθητο στις μεταβολές των απαιτήσεων της κάθε ομάδας σε σχέση με το συγκεντρωτικό. Τα αποτελέσματα της προσομοίωσης έδειξαν ότι η κατανεμημένη μορφή του προτεινόμενου σχήματος, επιφέρει καλύτερη απόδοση και το καθιστά πιο δίκαιο στην εξυπηρέτηση σε σχέση με το συγκεντρωτικό προσαρμοστικό σύστημα. Τέλος, η διατριβή αυτή, εισήγαγε για πρώτη φορά την χρήση Κρυμμένων Μαρκοβιανών Μοντέλων ως μηχανή πρόβλεψης της ζήτησης των πελατών σε ένα σύστημα ώθησης δεδομένων. Το προτεινόμενο σύστημα χρησιμοποιεί μια μηχανή πρόβλεψης της ζήτησης βασισμένη στο Κρυμμένο Μαρκοβιανό Μοντέλο, υποβοηθούμενη από ένα σύνολο διανυσμάτων καταγραφής ιστορικού. Βάσει των αποτελεσμάτων (έξοδος) του μηχανισμού πρόβλεψης γίνεται και ο χρονοπρογραμματισμός των επικείμενων εκπομπών. Το προτεινόμενο σύστημα οδηγεί σε επιτυχείς προβλέψεις της ζήτησης των χρηστών και συνεπώς και στην αποτελεσματική εξυπηρέτηση τους.