Οι κατανεμημένοι αλγόριθμοι δρομολόγησης για switches βασισμένα σε κελιά (=πακέτα σταθερού μεγέθους - π.χ. ΑΤΜ) που χρησιμοποιούν την αρχιτεκτονική Virtual Output Queueing έχουν οδηγήσει στη κατασκευή δρομολογητών υψηλών επιδόσεων. Στην παρούσα διπλωματική παρουσιάζουμε μια νέα ιδέα για την κατασκευή τέτοιων αλγορίθμων που λέγεται "αμοιβαία προτεραιότητα". Οι αλγόριθμοι της οικογένειας αυτής, που λέγεται οικογένεια "MPE", πετυχαίνουν βέλτιστη εγγύηση εξυπηρέτησης για κάθε ουρά εισόδου (καθυστέρηση το πολύ N κύκλων για switch ΝχΝ). Επίσης όσον αφορά τη μέση καθυστέρηση των πακέτων , ξεπερνούν σε απόδοση όλους τους γνωστούς αλγορίθμους. Οι βελτιώσεις που επιτυγχάνονται είναι αρκετά σημαντικές (π.χ. μέχρι και 78% μικρότερη καθυστέρηση πακέτων σε σύγκριση με τον καλύτερο υπάρχοντα αλγόριθμο, για μια επανάληψη). / Distributed scheduling algorithms for cell-based (e.g. ATM) Virtual Output Queuing (VOQ) switches have led to high performance schedulers. In this thesis we introduce a new concept in making such algorithms called "mutual priority" . Algorithms of this family , called "MPE" , achieve optimal service guarantee (N in a NxN switch) and lead to packet delays that outperform all existing algorithms. The improvements achieved are quite significant (i.e. up to 78% less packet delay compared to the best existing algorithm for a single iteration).

Σκοπός αυτής της εργασίας είναι η μελέτη τεχνικών κατανεμημένου προσανατολισμού σε πραγματικές συνθήκες. Πιο συγκεκριμένα σε αυτά στα συστήματα θεωρείται ότι ο κόμβος-πομπός δεν έχει καλή σύνδεση με το δέκτη και κατά συνέπεια δεν μπορεί να επικοινωνήσει απευθείας με τον κόμβο-δέκτη χωρίς δραματική αύξηση της ενέργειας μετάδοσης. Παρόλα αυτά η χρήση κατανεμημένου προσανατολισμού δίνει τη δυνατότητα να βελτιωθεί σημαντικά η κατανάλωση ενέργειας. Το σχήμα που θα χρησιμοποιηθεί είναι ενίσχυση και προώθηση (AF) 2 βημάτων, με το οποίο οι συνεργατικοί κόμβοι απλώς ενισχύουν και στην συνέχεια επαναμεταδίδουν το μήνυμα. Συνεπώς, ζητούμενο είναι η εύρεση των μιγαδικών βαρών με τα οποία πρέπει ο κάθε συνεργαζόμενος κόμβος χωριστά να ενισχύσει το σήμα. Οι τεχνικές που θα χρησιμοποιηθούν έχουν ως κριτήρια την ελαχιστοποίηση της ενέργειας μετάδοσης με ταυτόχρονη ικανοποίηση του SNR, μεγιστοποίηση του SNR με περιορισμένη ολική ενέργεια μετάδοσης και μεγιστοποίηση του SNR με περιορισμένη ενέργεια μετάδοσης ανά συνεργαζόμενο κόμβο. Το πρώτο κριτήριο θα εξεταστεί, επίσης, και σε συστήματα με πολλαπλούς πομπούς και δέκτες. Λόγω της φύσης του προβλήματος, ο κατανεμημένος προσανατολισμός αναμένεται να έχει μεγάλη απήχηση σε συστήματα με πολλούς διασκορπιστές και εμπόδια, όπως σε ένα αστικό περιβάλλον, και, επομένως, είναι λογικό να θεωρηθεί ότι τα κανάλια του συστήματος είναι Rayleigh, δηλαδή ασυσχέτιστα χωρίς οπτική επαφή (LOS). Για να προσομοιωθεί το σύστημα σε πραγματικές συνθήκες οι μέθοδοι που θα υλοποιήσουμε στην εργασία χρησιμοποιούν τα στατιστικά του καναλιού. Επιπλέον, η εκτίμηση καναλιού εφόσον θεωρούμε ότι έχουμε Gaussian λευκό θόρυβο θα γίνει με την χρήση του βέλτιστου γραμμικού εκτιμητή (BLUE). Η επίδραση της εκτίμησης του καναλιού θα μελετηθεί για δύο περιπτώσεις: με αμοιβαία και χωρίς αμοιβαία κανάλια. / The purpose of this thesis is the study of methods of distributed beamforming under real circumstances. More specifically, these systems are considered that the transmitter must increase tremendously the required transmit energy to communicate with the receiver. However the use of the distributed beamforming allows the system to improve the energy consumption. The scheme that is used from relays is amplify and forward of two steps, where the relays only amplify and then forward the message to the destination. That is, the purpose is to find the complex weights to be used by the corresponding relay so as to amplify the message of the transmitter. The methods that are implemented have as criterions the minimization of transmit energy while satisfying the SNR, maximization of SNR while limiting the system's transmit energy and maximization of SNR while limiting transmit energy of each relay individually. The first criterion is also studied at systems with more than one pair transmitter-receiver. Due to the nature of the problem, distributed beamforming is expected to be used at environments with many obstacles and scatterers, like urban environment, and so it is rationale to suppose that the channels should be Rayleigh, meaning uncorrelated without line of sight. To simulate the system under real circumstances the methods that we will implement shall use the second order statistics of the channels. Moreover, due to Gaussian white noise, channels are estimated using the Best Linear Unbiased Estimator. The impact of channel estimation is studied in two cases: "reciprocal" and "not reciprocal".

Είναι γνωστό από τη Θεωρία της Πληροφορίας, πως η δειγματοληψία σημάτων ακολουθεί το Θεώρημα των Shannon-Nyquist. Σύμφωνα με το θεώρημα αυτό, για την εκτέλεση της δειγματοληψίας ενός σήματος χωρίς απώλεια πληροφορίας, ο ρυθμός δειγματοληψίας αυτού θα πρέπει να είναι τουλάχιστον δύο φορές μεγαλύτερος από τη μεγαλύτερη συχνότητα που εμφανίζεται στο φάσμα του σήματος. Αυτή τη θεωρία κατάφερε – κατά κάποιο τρόπο - να ανατρέψει το 2006 μια νέα, αυτή της Συμπιεσμένης Καταγραφής που ξεκίνησε από δύο επιστημονικές εργασίες των Donoho, Candes, Romberg και Tao και η οποία έρχεται να αλλάξει τα έως σήμερα δεδομένα. Σήμερα, λίγα έτη αργότερα, μια αφθονία θεωρητικών πτυχών της συμπιεσμένης καταγραφής εξερευνάται ήδη σε περισσότερες από 1000 δημοσιεύσεις. Οι εφαρμογές αυτής της τεχνικής εκτείνονται και σε άλλα πεδία όπως η επεξεργασία εικόνας, η μαγνητική τομογραφία, η ανάλυση γεωφυσικών δεδομένων, η επεξεργασία εικόνας radar, η αστρονομία κ.α. Η μέθοδος της συμπιεσμένης καταγραφής ή αλλιώς Compressed Sensing ή Compressed Sampling, όπως αυτή είναι γνωστή στη βιβλιογραφία, στηρίζεται στη δυνατότητα ανακατασκευής αραιών σημάτων από πλήθος δειγμάτων αισθητά κατώτερο από αυτό που προβλέπει το θεωρητικό όριο του Nyquist. Έχει αποδειχθεί ότι, η ανακατασκευή αυτή είναι δυνατή όταν το σήμα ή έστω κάποιος μετασχηματισμός του περιέχει λίγα μη μηδενικά στοιχεία σε σχέση με το μήκος του. Στα πλαίσια αυτής της εργασίας παρουσιάζονται οι βασικές αρχές που διέπουν την ανακατασκευή αραιών σημάτων μέσω της επίλυσης υπο-ορισμένων συστημάτων γραμμικών εξισώσεων. Στη συγκεκριμένη εργασία, γίνεται μία προσπάθεια εφαρμογής της εν λόγω μεθόδου στα ανερχόμενα Cognitive Radio δίκτυα (Cognitive Radio Networks - CRN) τα οποία εμφανίζουν την ιδιότητα Spectrum Sharing. Σύμφωνα με αυτή την ιδιότητα, δηλαδή, το διαμοιρασμό του διαθέσιμου φάσματος, ο πρωταρχικός στόχος, είναι η ανίχνευση και η αναγνώριση των λεγόμενων spectrum holes σε ασύρματο περιβάλλον. Πιο συγκεκριμένα, παρουσιάζεται μια Distributed (κατανεμημένη) προσέγγιση συμπιεσμένης καταγραφής φάσματος για (τα ultra-) Wideband Cognitive Radio δίκτυα. Η τεχνική Compressed Sensing εφαρμόζεται σε τοπικά CRs του δικτύου, προκειμένου να ανιχνεύσει το υπερ-ευρύ φάσμα (ultra-wideband) με ρεαλιστική πολυπλοκότητα ανάκτησης του αρχικού σήματος. Οι φασματικές εκτιμήσεις από πολλαπλούς τοπικούς CRs του δικτύου «συνενώνονται» για να αποκομίσουν το χωρικό κέρδος ποικιλομορφίας (spatial diversity gain), το οποίο όσο αυξάνεται, βελτιώνει την ποιότητα ανίχνευσης, ειδικά στην περίπτωση των υπό εξασθένιση καναλιών (channel fading effect). Αρχικά, μελετάται ένας κατανεμημένος αλγόριθμος πλειοψηφίας (Distributed Consensus Algorithm) για να επιτευχθεί η συνεργασία κατά το στάδιο της ανίχνευσης της πληροφορίας που μεταφέρεται στο δίκτυο και έπειτα η αποστολή αυτής σε ένα fusion center. Αυτού του είδους ο distributed αλγόριθμος που χρησιμοποιεί μόνο one-hop επικοινωνία, συγκλίνει γρήγορα σε συνολικά βέλτιστες λύσεις που λειτουργούν με χαμηλό φόρτο επικοινωνίας και υπολογισμού που είναι ανάλογο του μεγέθους του δικτύου. Ένα σενάριο που εξετάζεται στο πλαίσιο αυτής της εργασίας, είναι η συγκεντρωτική ανίχνευση φάσματος ευρείας ζώνης με επικαλυπτόμενες συχνότητες ή αλλιώς κανάλια που είναι κοινά (frequency overlapping) σε Cognitive Radio δίκτυα και τα οποία, χρησιμοποιούν την τεχνική Compressed Sensing καθώς επίσης και την από κοινού ανακατασκευή (Joint Reconstruction) του αρχικού σήματος. Τέλος, προτείνεται ένα σενάριο, μιας κατανεμημένης αυτή τη φορά, τεχνικής ανίχνευσης φάσματος, που βασίζεται σε κανόνες πλειοψηφίας. Τα αποτελέσματα της προσομοίωσης, σε περιβάλλον Matlab, επιβεβαιώνουν την αποτελεσματικότητα αυτής της προτεινόμενης προσέγγισης, δηλαδή την ανίχνευση φάσματος, από συνδυασμό Cognitive Radio δικτύων με αραιά επικαλυπτόμενες συχνότητες. / It is well known from Information Theory, that the sampling of signals should be performed as dictated by the celebrated Shannon – Nyquist theorem. According to this theorem, in order to fully recover a signal from its samples, it must be sampled at a sampling rate that should be at least twice the bandwidth of the signal. This theory has been significantly extended over the past few years by the advent of the so-called Compressed Sensing theory, which first appeared in seminal scientific articles of Donoho, Candes, Romberg and Tao in 2006. Nowadays, an abundance of theoretical aspects of compressed sensing is already explored in more than 1000 articles. Τhis technique has been applied in various fields such as image processing, magnetic tomography, analysis of geophysical data, radar image processing, astronomy etc. The method of Compressed Sensing, also known as Compressed Sampling, is related to the reconstruction of sparse signals from far fewer samples or measurements than what the theoretical limit of Nyquist suggests. It has been proved that, this reconstruction is possible when the signal or a transformation of it, contains just a few non-zero elements with respect to its length. In this work, we firstly summarize the basic principles that condition the reconstruction of sparse signals via the solution of underdetermined systems of linear equations. Next, in this Master Thesis we aim at implementing Compressed Sensing method in emerging Cognitive Radio (CR) networks with spectrum sharing. The first cognitive task preceding any dynamic spectrum access is the sensing and identification of spectral holes in wireless environments. In more detail, this work is mainly concerned with a distributed compressed spectrum sensing approach for (ultra-)wideband CR networks. Compressed sensing is performed at local CRs to scan the very wide spectrum at practical signal-acquisition complexity. Meanwhile, spectral estimates from multiple local CR detectors are fused to collect spatial diversity gain, which improves the sensing quality especially under fading channels. Initially, a distributed consensus algorithm is analyzed for collaborative sensing and fusion in a scenario where all nodes are estimating the same spectral bands. Using only one-hop local communications, this distributed algorithm converges fast to the globally optimal solutions, at low communication and computation load scalable to the network size. Another scenario that has been investigated in this thesis is the joint wideband spectrum sensing in frequency overlapping cognitive radio networks, using centralized compressive sensing techniques. Finally, for the latter scenario, a distributed compressive sensing technique, based on consensus, has been proposed. Simulation results in Matlab environment verify the effectiveness of proposed joint spectrum sensing approach in jointly sparse frequency overlapping cognitive radio networks.