Η Ορθογώνια Πολυπλεξία Διαίρεσης Συχνότητας (OFDM) έχει προταθεί ως τεχνική διαμόρφωσης σε οπτικά δίκτυα, λόγω της καλής φασματικής απόδοσής της, της ευελιξίας και της ανοχής της σε βλάβες. Η διαμόρφωση OFDM επιτρέπει την ελαστική ανάθεση φάσματος, χρησιμοποιώντας μεταβλητό πλήθος υποφερουσών, καθώς και την επιλογή του κατάλληλου επιπέδου διαμόρφωσης με βάση την απόσταση της μετάδοσης. Το «Πρόβλημα Δρομολόγης και Ανάθεσης Φάσματος» (RSA) έχει αποδειχθεί ότι είναι ένα NP-πλήρες πρόβλημα, γεγονός που υποδηλώνει τη χρήση γραμμικού προγραμματισμού για τη λύση του. Στόχος της διπλωματικής εργασίας είναι η βελτίωση της απόδοσης του υπάρχοντος αλγορίθμου ακέραιου γραμμικού προγραμματισμού, με χρήση μεταευριστικών, έτσι ώστε στο ίδιο χρονικό διάστημα να υπολογίζεται αποδοτικότερη χρησιμοποίηση του συνολικού απαιτούμενου φάσματος, για το σύνολο των μεταδόσεων στο δίκτυο. / Orthogonal Frequency Division Multiplexing (OFDM) has been proposed as a modulation technique for optical networks, because of its good spectral efficiency, flexibility, and tolerance to impairments. OFDM modulation allows elastic spectrum allocation, using a variable number of subcarriers and choosing an appropriate modulation level, taking into account the transmission distance. The “Routing and Spectrum Allocation” (RSA) problem has been proved to be a NP-complete problem, which suggests the usage of linear programming in order to be solved. This diploma thesis aims to improve the efficiency of the existing integer linear programming algorithm, by using metaheuristics, so that at the same time period a more efficient utilization of the required spectrum is computed, for all network transmissions.

Στην παρούσα διπλωματική εργασία εξετάζεται η εκμετάλλευση της διαφορετικότητας πολλών χρηστών και της προσαρμοστικής διαμόρφωσης στα OFDMA συστήματα. Οι αλγόριθμοι που εκμεταλλεύονται αυτά τα κέρδη δεν προσδιορίζονται από το πρότυπο WiMAX, και έτσι όλοι οι κατασκευαστές WiMAX να είναι ελεύθεροι να αναπτύξουν τις δικές τους καινοτόμες διαδικασίες. Η ιδέα είναι η ανάπτυξη αλγορίθμων για την κατανομή των υποφορέων στους χρήστες, για τον προσδιορισμό των ποσοτήτων ισχύος σε αυτούς. Η μελέτη εστιάζεται στην κάτω ζεύξη (downlink) του συστήματος OFDMA, δηλαδή στη μετάδοση δεδομένων από το σταθμό βάσης της κυψέλης στους χρήστες – δέκτες. Οι διαθέσιμοι πόροι του συστήματος είναι οι ορθογώνιοι υποφορείς και η συνολική διαθέσιμη ισχύς στο σταθμό βάσης. Οι χρήστες κάνουν εκτίμηση και ανατροφοδότηση της πληροφορίας κατάστασης του καναλιού (CSI-channel state information) σε έναν κεντρικό σταθμό βάσης, όπου υποφορείς και κατανομή ισχύος προσδιορίζονται σύμφωνα με CSI των χρηστών και τη διαδικασία κατανομής των διαθέσιμων πόρων. Μόλις οι υποφορείς για κάθε χρήστη καθοριστούν, ο σταθμός βάσης πρέπει να ενημερώνει τον κάθε χρήστη για το ποιοι υποφορείς έχουν ανατεθεί στον καθένα. Συνήθως, η κατανομή των πόρων πρέπει να γίνεται σε χρονικά διαστήματα της τάξης του χρόνου συνοχής, αν και μπορεί να γίνει πιο συχνά, αν υπάρχουν πολλοί χρήστες που ανταγωνίζονται για τους πόρους που είναι διαθέσιμοι. Στην παρούσα διπλωματική εργασία εξετάζονται διαφορετικά σενάρια κατανομής των πόρων που περιλαμβάνουν αλγορίθμους για την ανάθεση των υποφορέων και το διαμοιρασμό των κατάλληλων ποσοτήτων ισχύος στους υποφορείς. Ανάλογα με το στόχο και τις ανάγκες των χρηστών του συστήματος, καθώς και με το ποσό της διαθέσιμης πληροφορίας καναλιού στο σταθμό βάσης, χρησιμοποιούνται διαφορετικοί αλγόριθμοι. Η κατανομή των διαθέσιμων πόρων συνήθως διατυπώνεται ως πρόβλημα βελτιστοποίησης με περιορισμούς, είτε (1) ελαχιστοποίηση της συνολικής εκπεμπόμενης ισχύoς με περιορισμό στο ρυθμό μετάδοσης δεδομένων στο χρήστη είτε (2) μεγιστοποίηση του συνολικού ρυθμού μετάδοσης δεδομένων με περιορισμό στην συνολική εκπεμπόμενη ισχύ. Ο αλγόριθμος με περιορισμό αναλογίας των ρυθμών μετάδοσης (Proportional Rate Constraints algorithm - PRC) έχει ως στόχο τη μεγιστοποίηση της συνολικής διεκπεραίωσης με τον περιορισμό ότι ο ρυθμός μετάδοσης δεδομένων σε κάθε χρήστη είναι ανάλογος με ένα σύνολο από προκαθορισμένες παραμέτρους του συστήματος. Ενώ ο στόχος του αλγόριθμου μέγιστου ολικού ρυθμού μετάδοσης (MSR- maximum sum rate algorithm), είναι η μεγιστοποίηση του συνόλου των ρυθμών μετάδοσης όλων των χρηστών, λαμβάνοντας υπόψη έναν περιορισμό της συνολικής εκπεμπόμενης ισχύoς. / In this diploma thesis, multiuser diversity and adaptive modulation in OFDMA systems is considered. Algorithms that take advantage of these gains are not specified by the WiMAX standard, and all WiMAX developer are free to develop their own innovative procedures. The idea is to develop algorithms for determining which users to schedule, how to allocate subcarriers to them, and how to determine the appropriate power levels for each user on each subcarrier. The downlink of a single-cell system is considered in the downlink transmission. The available resources to be distributed among the users of the OFDMA system comprise the subcarriers over which the signals of the users are transmitted and the available power that is allocated among subcarriers. Users estimate and feedback the channel state information (CSI) to a centralized base station, where subcarrier and power allocation are determined according to users’ CSI and the resource-allocation procedure. Once the subcarriers for each user have been determined, the base station must inform each user which subcarriers have been allocated to it. Typically, the resource allocation must be performed on the order of the channel coherence time, although it may be performed more frequently if a lot of users are competing for resources. In this diploma thesis, different resource allocation strategies for the downlink of an OFDMA system are compared. Each algorithm has a different objective. The resource allocation is usually formulated as a constrained optimization problem, to either (1) minimize the total transmit power with a constraint on the user data rate or (2) maximize the total data rate with a constraint on total transmit power. The proportional rate constraints (PRC) algorithm is to maximize the sum throughput, with the additional constraint that each user’s data rate is proportional to a set of predetermined system parameters. While the objective of the maximum sum rate (MSR) algorithm, is to maximize the sum rate of all users, given a total transmit power constraint.

Η παρούσα διπλωματική εργασία έγινε στα πλαίσια του Προγράμματος Μεταπτυχιακών Σπουδών Ηλεκτρονικής και Υπολογιστών, στο Τμήμα Φυσικής του Πανεπιστημίου Πατρών. Αντικείμενό της αποτελεί η μελέτη του φυσικού επιπέδου συστημάτων κινητής τηλεφωνίας τρίτης γενιάς και η εξομοίωση χαρακτηριστικού καναλιού του φυσικού επιπέδου σύμφωνα με την παγκόσμια προτυποποίηση 3GPP. Στο πρώτο κεφάλαιο γίνεται ιστορική ανασκόπηση των συστημάτων προηγούμενων γενεών. Αναφέρονται βασικά προβλήματα που πρέπει να αντιμετωπίσει ένα τηλεπικοινωνιακό σύστημα καθώς και η βασική δομή των κυψελοειδών συστημάτων. Γίνεται εισαγωγή στα συστήματα τρίτης γενιάς ως προς τις απαιτήσεις, τις υπηρεσίες που προσφέρουν, την προτυποποίηση και την αρχιτεκτονική τους. Στο δεύτερο κεφάλαιο μελετώνται οι τρόποι πολλαπλής πρόσβασης με ιδιαίτερη έμφαση στην προσπέλαση με διαίρεση κωδικών. Αναλύονται τα συστήματα διάχυσης φάσματος. Γίνεται εκτενής αναφορά και υλοποίηση προγραμμάτων για τις ψευδοτυχαίες ακολουθίες και τις ακολουθίες Gold. Στο τρίτο κεφάλαιο μελετάται η δομή δικτύων επικοινωνίας κατά το μοντέλο OSI. Αναφέρονται τα επίπεδα των τηλεπικοινωνιακών συστημάτων με διεξοδική μελέτη του φυσικού επιπέδου και στις διεπαφές που χρησιμοποιεί για επικοινωνία καθώς και στις υπηρεσίες που προσφέρει. Αναλύεται η δομή όλων των φυσικών καναλιών και εξομοιώνεται η διαδικασία ενθυλάκωσης του καναλιού PRACH. Στο τέταρτο κεφάλαιο αναλύονται οι κώδικες διάχυσης των φυσικών καναλιών ανερχόμενης ζεύξης καθώς και η διαδικασία διάχυσης τους. Δημιουργούνται προγράμματα που παράγουν αυτούς τους κώδικες και γίνεται εξομοίωση της διάχυσης και της αποδιάχυσης του PRACH καναλιού. Στο πέμπτο κεφάλαιο αναφέρεται η διαδικασία κωδικοποίησης πηγής και μελετάται η PSK διαμόρφωση και αποδιαμόρφωση που χρησιμοποιούν τα συστήματα τρίτης γενιάς. Υλοποιούνται προγράμματα που εξομοιώνουν τη συνολική διαδικασία σε ενθόρυβο κανάλι AWGN μελετώντας την επίδραση του θορύβου σε μεταδιδόμενο σήμα. Όλες οι εξομοιώσεις υλοποιήθηκαν με το πρόγραμμα Matlab 7.1. / This master thesis is a part of the post-graduate course of the Physics department of the University of Patras, on Electronics and Computers. Its main objective is the study of the physical layer of 3rd generation telecommunication systems and the simulation of a particular channel, in accordance to 3GPP specifications. In the first chapter we review telecommunication systems of previous generations. We also refer to major problems that need to be dealt with and also the basic structure of cellular networks. 3rd generation telecommunication systems, their requirements, offered services, standardisation and architecture are all introduced. In the second chapter we study multiple access methods, emphasising CDMA methods. Moreover, spread spectrum systems are analysed. Finally we refer to pseudorandom and Gold sequences. Programs are created which generate these sequences. In the third chapter we look into the structure of communication networks according to the OSI model. The layers of telecommunication systems are mentioned, laying emphasis on the physical layer, the interfaces used for communication as well as the offered services. We report all physical channels and we simulate the encapsulation of the PRACH channel. In the fourth chapter we analyse the spreading and scrambling codes referring to the uplink channels. Next we point out the code allocation process. Programs are created which generate these spreading and scrambling codes and we finally simulate the spreading and de-spreading process of the PRACH channel. In the fifth chapter we outline the source coding process using PCM, and we study PSK modulation and demodulation which are used by 3rd generation telecommunication systems. We create programs that simulate the whole procedure in a noisy channel, and we study the effect of AWGN. The programs were created and the simulations were run using Matlab version 7.1.

Τα οπτικά δίκτυα αποτελούν την αποδοτικότερη επιλογή όσον αφορά την εγκατάσταση ευρυζωνικών δικτύων κορμού, καθώς παρουσιάζουν μοναδικά χαρακτηριστικά μετάδοσης. Διαθέτουν τεράστιο εύρος ζώνης, υψηλή αξιοπιστία, ενώ επίσης έχουν μειωμένο κόστος μετάδοσης ανά bit πληροφορίας σε σχέση με τα υπόλοιπα ενσύρματα δίκτυα. Τις τελευταίες δεκαετίες διατυπώθηκαν οι αρχές μίας τεχνολογίας μετάδοσης πολλαπλών φερουσών, γνωστής ως Ορθογώνια Πολυπλεξία Διαίρεσης Συχνότητας (Orthogonal Frequency Division Multiplexing - OFDM), η οποία στηρίζεται στην πολυπλεξία διαίρεσης συχνότητας, αλλά πετυχαίνει πολύ καλύτερη χρησιμοποίηση του διαθέσιμου εύρους ζώνης. Πρόσφατα και στις οπτικές επικοινωνίες άρχισε να μετατοπίζεται το ενδιαφέρον στην Οπτική Ορθογώνια Πολυπλεξία Διαίρεσης Συχνότητας (O-OFDM), λόγω της προόδου στην κωδικοποίηση και στην ηλεκτρονική ψηφιακή επεξεργασία σήματος (DSP). Οι εξελίξεις αυτές μπορούν να αλλάξουν ριζικά τα οπτικά δίκτυα. Μέσω της πολυπλεξίας υποφερουσών και της δέσμευση μεταβλητού φάσματος, που είναι χαρακτηριστικά της O-OFDM τεχνολογίας, ένα οπτικό μονοπάτι μπορεί να χρησιμοποιεί το απολύτως απαραίτητο φάσμα (αριθμό υποφερουσών) ανάλογα με το μεταδιδόμενο ρυθμό δεδομένων. Με τον τρόπο αυτό επιτυγχάνεται καλύτερη χρησιμοποίηση φάσματος αναιρόντας τον περιορισμό σταθερού πλέγματος των δικτύων πολυπλεξίας μήκους κύματος (WDM). Παράλληλα η αρχιτεκτονική αυτή υποστηρίζει τη δέσμευση χωρητικότητας μικρότερης ή μεγαλύτερης από αυτή ενός μήκους κύματος μέσω της δέσμευσης κατάλληλου αριθμού υποφερουσών από κατάλληλους transponders και μεταγωγείς WXCs. Στην παρούσα διπλωματική εργασία αντιμετωπίζεται το πρόβλημα της σχεδίασης ευέλικτων OFDM οπτικών δικτύων, όπου οι αιτήσεις εξυπηρετούνται από κατάλληλους transponders όσον αφορά την επιλογή του χρησιμοποιούμενου φάσματος και του επίπεδου διαμόρφωσης. Με δεδομένη την τοπολογίας του δικτύου, τον πίνακα αιτήσεων και των χαρακτηριστικών των transponders, παρουσιάζονται οι μοντελοποιήσεις γραμμικού ακέραιου προγραμματισμού (Integer Linear Programming) για την επίλυση του προβλήματος σχεδίασης διαφανών (transparent) και ημι-διαφανών (translucent) οπτικών OFDM δικτύων λαμβάμνοντας υπόψη τους υπαρκτούς περιορισμούς φυσικού επιπέδου. Σχεδιάζεται λοιπόν, ένα πρόβλημα βελτιστοποίησης που λαμβάνει υπόψη του τόσο το εύρος ζώνης που χρησιμοποιείται όσο και τον αριθμό των transponders. Από τη στιγμή που το πρόβλημα της δρομολόγησης και δέσμευσης φάσματος (Routing and Spectrum Allocation RSA) είναι ΝP πλήρες (NP-complete), η λύση του προβλήματος γραμμικού ακέραιου προγραμματισμού (ILP) δεν είναι αποδοτική για μεγάλα στιγμιότυπα του προβλήματος. Για το λόγο αυτό, παρουσιάζονται ευριστικοί αλγόριθμοι (heuristic algorithms) για την επίλυση του προβλήματος σχεδίασης διαφανών και ημι-διαφανών οπτικών δικτύων. / We consider the planning problem of a spectrum flexible optical network where traffic is served by flexible transponders that can be tuned in both the spectrum and the modulation format that they utilize. We assume that physical layer impairments are incorporated in the definition of the feasible transmission configurations for the transponders, described by capacity-reach-spectrum-guardband tuples. Given the feasible configurations (tuples) of the transponders and the traffic matrix, we formulate the planning problem of a spectrum flexible optical network considering both the use or not of regenerators in the network. Demands are served for their requested rates by choosing the route, breaking the transmission in more than one connection if needed, placing regenerators if needed, and allocating spectrum to the connections. The connections are separated by appropriate spectrum guardbands so that physical layer interference is kept at acceptable levels. The objective is to serve the traffic and find a solution that is Pareto optimal with respect to the total amount of spectrum utilized and the number of transponders used. We start by presenting algorithms that are based on integer linear programming (ILP) formulations for planning both transparent (without regenerators) and translucent (with regenerators) networks and then we continue by presenting heuristic algorithms. Our heuristic algorithms utilize simulated annealing to tradeoff performance with running time. We use transmission tuples based on studies on OFDM-based networks in our simulation experiments. We initially examine the optimality performance of the heuristic algorithms in small scale experiments. Then we use the heuristic algorithms to study realistic network planning problems and evaluate the spectrum and transponder cost savings that can be obtained by an OFDM-based network as compared to a mixed line rate (MLR) fixed-grid WDM optical network.