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

Abstract

This doctoral thesis deals with the problem of Scheduling and Dynamic Resource Allocation in modern wireless networks that can provide advanced and differentiated Quality of Service (QoS), emphasizing on networks based on the IEEE 802.16 standard. The complexity of this multidimensional problem is enlarged together with the degree of flexibility that the system aims to provide. Especially for the most recent versions of the standard, which take advantage of advanced transmission techniques such as OFDMA (Orthogonal Frequency Division Multiple Access), adaptive modulation and coding, and adaptive power allocation, the problem becomes a real challenge. Although many research efforts has focused on this area during the last decade, only a small number of proposals take advantage of the full set of capabilities in terms of flexibility and adaptation, to provide a joint solution for both scheduling and resource allocation. In contrast to the most known solutions that adjust existing approaches for other systems, or rely on extensive theoretical models, this doctoral thesis follows a novel approach. The novelty of our approach lies on the use of advanced and sophisticated tree data structures, which operate in parallel to the traditional traffic queues, storing metadata for data packets (for the downlink) and requests/grants (for the uplink). A family of algorithms are proposed that cover different versions of ΙΕΕΕ 802.16, are applied to PMP (Point-to-Multipoint) and mesh topologies, and support multicast transmissions, while the last member of the proposed family is a joint solution for scheduling and resource allocation for mobile WiMAX (IEEE 802.16e). The main advantage of the proposed approach is the counterbalance between computational complexity and a finite amount of memory. Moreover, the required computational complexity is spread throughout the entire life of a packet, in contrast to most existing approaches that concentrate complex computations just before the transmission of each time frame. The main challenge of our research is to guarantee most of the QoS parameters and improve overall system throughput. As shown by simulation results for each algorithm, the proposed approach guarantees the agreed QoS parameters, resulting in much lower packet loss rate for the same amount of traffic and much better throughput compared to existing solutions.

Η παρούσα Διδακτορική Διατριβή πραγματεύεται το πρόβλημα του χρονοπρογραμματισμού και δυναμικής ανάθεσης πόρων σε σύγχρονα δίκτυα ασύρματων επικοινωνιών που έχουν την δυνατότητα παροχής προηγμένης και διαβαθμισμένης ποιότητας υπηρεσίας (Quality of Service - QoS), με έμφαση στο πρότυπο ΙΕΕΕ 802.16 γνωστό και ως WiMAX. Πρόκειται για ένα σύνθετο και πολυδιάστατο πρόβλημα, ο βαθμός δυσκολίας του οποίου αυξάνεται με την αύξηση της πολυπλοκότητας των δικτυακών συστημάτων και τα επίπεδα ποιότητας υπηρεσίας που αυτά παρέχουν. Ιδιαίτερα στις πιο πρόσφατες εκδόσεις του προτύπου, οι οποίες ενσωματώνουν την τεχνική OFDMA (Orthogonal Frequency Division Multiple Access), καθώς και τις λειτουργίες της προσαρμοστικής διαμόρφωσης και κωδικοποίησης και της ρύθμισης ισχύος, το πρόβλημα γίνεται ακόμη πιο πολύπλοκο. Παρότι την τελευταία δεκαετία, που η έρευνα στη συγκεκριμένη περιοχή βρίσκεται σε εξέλιξη, έχουν προταθεί διάφορες προσεγγίσεις για το πρόβλημα του χρονοπρογραμματισμού και της ανάθεσης πόρων, λίγες είναι αυτές που εκμεταλλεύονται το σύνολο των δυνατοτήτων παραμετροποίησης και προσαρμοστικότητας, για να προτείνουν μία ενιαία λύση χρονοπρογραμματισμού και ανάθεσης πόρων. Η παρούσα Διατριβή ακολουθεί μία διαφορετική προσέγγιση από τις μέχρι σήμερα γνωστές λύσεις, οι οποίες βασίζονται στην μετεξέλιξη και προσαρμογή παλαιότερων προτάσεων στα χαρακτηριστικά του ΙΕΕΕ 802.16/ WiMAX. Η καινοτομία της προσέγγισής μας έγκειται στην χρήση έξυπνων και προηγμένων δενδρικών δομών δεδομένων, οι οποίες δεν αντικαθιστούν τις ουρές δεδομένων των χρηστών και των συνδέσεών τους, αλλά λειτουργούν παράλληλα, διατηρώντας μεταδεδομένα για τα πακέτα (για την κατωφερή-ζεύξη ή τις αιτήσεις και εκχωρήσεις μετάδοσης για την ανωφερή-ζεύξη) των χρηστών-συνδέσεων. Προτείνεται λοιπόν μία οικογένεια αλγορίθμων που καλύπτει όλες τις εκδόσεις του ΙΕΕΕ 802.16, τις τοπολογίες PMP (από σημείο σε πολλαπλά σημεία) και πλέγματος (κεντρικοποιημένης διαχείρισης), αλλά και την δυνατότητα πολυμετάδοσης (multicast), ενώ το τελευταίο μέλος της προτεινόμενης οικογένειας αποτελεί μία ολοκληρωμένη λύση χρονοπρογραμματισμού και ανάθεσης πόρων για προσαρμοστικά συστήματα OFDMA.