Η οπτική μεταγωγή καταιγισμών (Optical Burst Switching) είναι ένα ελπιδοφόρο παράδειγμα μεταγωγής για την επόμενη γενεά του Διαδικτύου. Ένα βασικό πρόβλημα στα δίκτυα OBS είναι η δρομολόγηση και ο χρονοπρογραμματισμός των καταιγισμών στους συνδέσμους του δικτύου, ώστε να μειωθεί η απώλεια και η καθυστέρηση τους. Εδώ παρουσιάζουμε έναν βασισμένο στην πηγή αλγόριθμο δρομολόγησης και χρονοπρογραμματισμού πολλαπλών κριτηρίων για την επιλογή μονοπατιών (διαδρομών) που ακολουθούνται από τους καταιγισμούς. Ο αλγόριθμος επιπλέον υπολογίζει και το χρόνο στον οποίο πρέπει να αρχίσει η μετάδοση των καταιγισμών ώστε να φθάσουν στον προορισμό με την ελάχιστη καθυστέρηση. Τα διαγράμματα χρησιμοποίησης (utilization profiles) των συνδέσμων του δικτύου, η καθυστέρηση διάδοσης των συνδέσμων και οι παράμετροι των καταιγισμών (μέγεθος, offset time κ.α.) διαμορφώνουν τα δεδομένα εισόδου του αλγορίθμου. Το προτεινόμενο σχήμα εκμεταλλεύεται τα κενά (void filling) που προκύπτουν από τη χρήση του bandwidth σε κάθε σύνδεσμο ώστε να βρεθεί η καλύτερη διαθέσιμη διαδρομή. Όταν δεν υπάρχει καμία κατάλληλη διαδρομή τη χρονική στιγμή που ζητείται από τον καταιγισμό, ο αλγόριθμος καθορίζει επίσης το χρονικό διάστημα (Time Offset) που πρέπει να καθυστερήσουμε τον καταιγισμό στην πηγή έως ότου γίνει διαθέσιμη η καλύτερη δυνατή διαδρομή. / Optical burst switching (OBS) is considered a promising switching paradigm for the next generation Internet. A key problem in OBS networks is the routing and scheduling of the bursts on the network links, so as to reduce burst loss and delay. In this paper we present a source-based multicost routing and scheduling algorithm to select the paths to be followed by the bursts and the times when the bursts should start transmission from their source so as to arrive at their destination with minimum delay. The utilization profiles of the network links, the link propagation delays, and the parameters of the bursts that have to be scheduled form the inputs to the algorithm. The proposed scheme exploits gaps in capacity utilization so as to find the best available path. When there is no suitable path at the time it is requested, the algorithm also determines the amount of time the burst must be delayed at the source for the best path to become available.

Στα ασύρματα αδόμητα δίκτυα, οι κόμβοι μπορούν να συνεργαστούν για τη μετάδοση δεδομένων σε απομακρυσμένουσ κόμβους. Συνήθως, η συνεργασία αυτή επιτυγχάνεται χρησιμοποιώντας βοηθητικούς ενδιάμεσους κόμβους για τη μετάδοση δεδομένων από ένα κόμβο πηγή σε ένα κόμβο προορισμό, μέσω point-to-point ή point-to-multipoint συνδέσμους. Πρόσφατα, μεγάλο ενδιαφέρον έχει αποκτήσει η τεχνική της συνεργατικής μετάδοσης, όπου περισσότεροι του ενός κόμβοι συμμετέχουν για τη μετάδοση του ίδιου σήματος σε έναν απομακρυσμένο κόμβο. Ο παραλήπτης ανακατασκευάζει το αρχικό σήμα συνδυάζωντας τα διαφορετικά σήματα που έφτασαν σε αυτόν. Εδώ, αναπτύσσεται και εκτιμάται ένας πολυ-κριτηριακός αλγόριθμος συνεργατικής δρομολόγησης που λαμβάνει υπόψην την εναπομένουσα ενέργεια και την απαιτούμενη ισχύ μετάδοσης των κόμβων. Ο αλγόριθμος για ένα ζευγάρι κόμβων πηγής – προορισμού ανακαλύπτει όλα τα δυνατά υποψήφια μονοπάτια λαμβάνοντας υπόψη και συνδέσμους με την δυνατότητα συνεργασίας των κόμβων για την αποστολή των δεδομένων. Τελικά επιλέγεται το μονοπάτι που βελτιστοποιεί μια συνάρτηση κόστους. Τα κριτήρια είναι η εναπομένουσα ενέργεια και η συνολική ισχύς μετάδοσης στους κόμβους του μονοπατιού. Εκτελούμε πειράματα προσομοίωσης σε δίκτυα με κόμβους που έχουν σταθερή ισχύ μετάδοσης και με κόμβους που μπορούν να προσαρμόσουν την ισχύ μετάδοσής τους. Τα αποτελέσματα δείχνουν ότι ο αλγόριθμός μας πετυχαίνει σημαντική εξοικονόμηση ενέργειας και μεγαλύτερο αριθμό επιτυχημένων αποστολών πακέτων σε σχέση με την περίπτωση που δεν χρησιμοποιείται συνεργασία. / In wireless ad-hoc networks, nodes cooperate to make possible the communication between otherwise distant nodes. Usually, this cooperation is in the form of nodes acting as intermediate relays that forward data from a source to a destination node using point-to-point or point-to-multipoint links. A technique that has gained considerable recent attention is cooperative diversity, where nodes are organized for transmitting the same signal to a given, often otherwise unreachable, node. The receiver combines the multiple receptions to reconstruct the original signal. In this work, we present and evaluate a multi-criteria cooperative routing algorithm that uses as parameters the nodes’ residual energy and their transmission power. This algorithm selects for each source-destination pair a path, in the form of a sequence of groups of cooperative nodes, and the nodes’ transmission powers. We perform a number of simulation experiments, assuming nodes with variable or fixed transmission power, evaluating the benefits of the proposed multi-criteria cooperative routing algorithm. The results show that our algorithm achieves significant energy savings and larger number of successfully delivered packets than the case where cooperation is not applied.

Adaptive beamforming is a. powerful approach to receive or transmit signals of interest in a spatially selective way in the presence of interference and noise. Recently, there has been renewed interest in adaptive beamforming driven by applications in wireless communications, where multiple-input multiple-output (MEMO) techniques have emerged as one of the key technologies to accommodate the high number of users as well as the increasing demand for new high data rate services. Beamforming techniques promise to increase the spectral efficiency of next generation wireless systems and are currently being incorporated in future industry standards. Although a significant amount of research has focused on theoretical capacity analysis, little is known about the performance of such systems in practice. In thesis, I experimentally and analytically evaluate the performance of adaptive beamforming techniques on the downlink channel of a wireless LAN. To this end. I present the design and implementation of the first multi-user beam-forming system and experimental framework for wireless LANs. Next, I evaluate the benefits of such system in two applications. First, I investigate the potential of beamforming to increase the unicast throughput through spatial multiplexing. Using extensive measurements in an indoor environment, I evaluate the impact of user separation distance, user selection, and user population size on the multiplexing gains of multi-user beamforming. I also evaluate the impact of outdated channel information due to mobility and environmental variation on the multiplexing gains of multi-user beamforming. Further, I investigate the potential of beamforming to eliminate interference at unwanted locations and thus increase spatial reuse. Second, I investigate the potential of adaptive beamforming for efficient wireless multicasting. I address the joint problem of adaptive beamformer design at the PHY layer and client scheduling at the MAC layer by proposing efficient algorithms that are amenable to practical implementation. Next, I present the implementation of the beamforming based multicast system on the WARP platform and compare its performance against that of omni-directional and switched beamforming based multicast. Finally, I evaluate the performance of multicast beamforming under client mobility and infrequent channel feedback, and propose solutions that increase its robustness to channel dynamics.

Στην παρούσα εργασία εξετάζουμε το πρόβλημα της δρομολόγησης σε δίκτυα ad-hoc, όπου οι κόμβοι είναι ακίνητοι και έχουν πεπερασμένα αλλά επαναφορτιζόμενα ενεργειακά αποθέματα. Αρχικά μελετάμε σε θεωρητική βάση τους ενεργειακούς και χωρητικούς περιορισμούς. Ενεργειακοί είναι οι περιορισμοί που οφείλονται στην μικρή ενεργειακή αυτοτέλεια των κόμβων, ενώ οι χωρητικοί περιορισμοί οφείλονται στην περιορισμένη χωρητικότητα του ασύρματου μέσου και στην παρεμβολή. Συγκεκριμένα εξετάζουμε πώς ορισμένα δικτυακά χαρακτηριστικά επηρεάζουν την απόδοση του δικτύου. Τέτοια δικτυακά χαρακτηριστικά είναι η πυκνότητα των κόμβων του δικτύου, η φυσική απόσταση τους, η ακτίνα μετάδοσης τους κ.α. Εξετάζουμε διαφόρων ειδών δίκτυα και σε γενικές γραμμές αποδεικνύουμε ότι η ενέργεια είναι ο κρίσιμος πόρος σε δίκτυα τα οποία είναι αραιά ή οι κόμβοι τους έχουν μικρό ρυθμό επαναφόρτισης της ενέργειας ή μεγάλη ακτίνα μετάδοσης. Στην αντίθετη περίπτωση η απόδοση των δικτύων περιορίζεται από την χωρητικότητα και την παρεμβολή. Επιπλέον προτείνουμε και υλοποιούμε έναν ενεργειακά-αποδοτικό αλγόριθμο δρομολόγησης με πολλαπλά κόστη, όπου ένα διάνυσμα από παραμέτρους, εν’αντιθέσει με μία μόνο παράμετρο, ανατίθεται σε κάθε σύνδεσμο του δικτύου. Σε κάθε ανακαλυπτόμενη διαδρομή ανατίθεται ομοίως ένα διάνυσμα παραμέτρων, που προκύπτει από τα αντίστοιχα διανύσματα των συνδέσμων της διαδρομής. Οι παράμετροι που χρησιμοποιούμε είναι ο αριθμός των συνδέσμων της διαδρομής, η υπολειπόμενη ενέργεια και η ισχύς μετάδοσης. Ο αλγόριθμος αυτός συγκρίνεται με τον αλγόριθμο ελάχιστου-μήκους διαδρομής, για την επίλυση του προβλήματος του άπειρου χρονικού ορίζοντα. Στο πρόβλημα του άπειρου χρονικά ορίζοντα, ενέργεια και νέα πακέτα δεδομένων δημιουργούνται συνεχώς σε κάθε κόμβο του δικτύου. Στα πειράματα που εκτελέσαμε μας ενδιαφέρει να υπολογίσουμε την μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax στους κόμβους, η οποία επιτρέπει στο δίκτυο μας να παραμένει ευσταθές. Ένα δίκτυο χαρακτηρίζεται ευσταθές όταν η εισερχόμενη κίνηση εξυπηρετείται από το δίκτυο με μικρή μέση καθυστέρηση παράδοσης αλλά και μεγάλο ποσοστό επιτυχούς παράδοσης των πακέτων δεδομένων στους προορισμούς τους. Όταν μία από αυτές τις συνθήκες δεν ισχύει τότε θεωρούμε ότι το δίκτυο είναι ασταθές και δεν μας ενδιαφέρει περαιτέρω η μελέτη του. Ουσιαστικά η μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax είναι η μέγιστη απόδοση του δικτύου μας. Η μέση καθυστέρηση παράδοσης των πακέτων δεδομένων ορίζεται ως ο μέσος χρόνος μεταξύ της δημιουργίας ενός πακέτου στον κόμβο-πηγή και της λήψης του πακέτου στον κόμβο-προορισμού. Το ποσοστό της επιτυχούς παράδοσης των πακέτων δεδομένων ορίζεται σαν τον λόγο του αριθμού των πακέτων που παρελήφθησαν επιτυχώς από τους κόμβους-προορισμού προς τον αριθμό των πακέτων που δημιουργήθηκαν στους κόμβους-πηγής. Κατά την διάρκεια των πειραμάτων μας δοκιμάζουμε διάφορες πιθανότητες δημιουργίας πακέτων δεδομένων p και διάφορους ρυθμούς επαναφόρτισης των κόμβων X. Από τα αποτελέσματα των πειραμάτων μας παρατηρούμε ότι ο ενεργειακά-αποδοτικός αλγόριθμος δρομολόγησης με πολλαπλά κόστη υπερτερεί του αλγορίθμου ελάχιστου-μήκους διαδρομής, πετυχαίνοντας όταν το δίκτυο είναι ενεργειακά περιορισμένο, μέγιστη πιθανότητα δημιουργίας πακέτων δεδομένων pmax σχεδόν διπλάσια από αυτή που πετυχαίνει ο ελάχιστου-μήκους διαδρομής αλγόριθμος. Ακόμα παρατηρούμε ότι η μέση καθυστέρηση καθώς και το ποσοστό επιτυχούς παράδοσης των πακέτων δεδομένων παρουσιάζουν καλύτερα αποτελέσματα με την χρήση του ενεργειακά-αποδοτικού αλγορίθμου. Επιπλέον παρατηρούμε ότι η μέση καθυστέρηση αυξάνει πολύ απότομα σε σχέση με την πιθανότητα δημιουργίας πακέτων δεδομένων p, όταν το δίκτυο γίνεται ασταθές λόγο των ενεργειακών περιορισμών. Αντίθετα η αύξηση αυτή είναι πολύ πιο ομαλή, όταν το δίκτυο γίνεται ασταθές λόγο των χωρητικών περιορισμών. / In our thesis we examine the problem of routing in ad-hoc networks, where the nodes are stationary and have limited but rechargeable energy reserves. Initially we study theoretically, the energy and the capacity constraints. The energy constraints are the result of the limited energy reserves of the nodes, while the capacity constraints are the result of the limited capacity and of the interference in the wireless medium. In our theoretically study we examine how the various network characteristics, influence the network performance. Such network characteristics are the nodes density, their distance, the transmission radius etc. We examine various network topologies and in every case we prove that energy is a vital resource in networks which are sparsely or where the nodes have small recharge rate or big transmission radius. In every other case the performance of a network is constrained by the capacity and the interference. Furthermore we propose and implement an energy-aware multicost routing algorithm, where a vector of parameters, instead of just one parameter, is assigned to each link of the network. In the same way in every discovered path, a vector of parameters is assigned. This vector is calculated using the vectors of the links from which the path consists of. The parameters used are the hops number, the residual energy and the transmission power. The proposed algorithm is compared with the minimum-hop algorithm, under the infinite time horizon problem. In this problem energy and data packets are constantly created in every node of the network. In our experiments we are interested in finding the maximum packet generation probability pmax in the nodes, under which the network remains stable. A network is characterized as stable when the incoming traffic is served by the network with small average delivery delay and big successful delivery ratio, of the packets in their destinations. When one of these conditions doesn’t hold, then we assume that the network is unstable and we do not study it anymore. The maximum packet generation probability pmax is in fact the maximum throughput of the network. The average delivery delay is defined as the average time between the creation of a data packet in the source-node and the reception of the packet in the destination-node. The successful delivery ratio is defined as the ratio of the number of packets successfully received by their destinations by the number of packets created in the source-nodes. During our experiments we tried various packet generation probabilities p and recharge rates at the nodes X. From the results of ours experiments we observe that the energy-aware multicost routing algorithm outperforms the minimum-hop algorithm. Specifically when the network is energy constrained, the maximum packet generation probability pmax is almost double as the one achieved by the minimum-hop algorithm. Furthermore the average delivery delay and the successful delivery ratio present better results using the energy-aware algorithm. Also we generally observe that the average delivery delay increases suddenly as the packet generation probability p increases, when the network becomes unstable because of the energy constraints. On the other hand the increase in the average delivery delay is much more normal, when the network becomes unstable because of the capacity constraints.

Μέχρι σήμερα στη δρομολόγηση στα ασύρματα αδόμητα δίκτυα λαμβάνεται ως κριτήριο ένα μοναδιαίο μέγεθος για κάθε σύνδεσμο του δικτύου, το οποίο αναπαριστά το κόστος της μετάδοσης πάνω στον συγκεκριμένο σύνδεσμο. Στη δρομολόγηση με βάση πολλαπλά κριτήρια η βασική ιδέα είναι ότι σε κάθε σύνδεσμο ανατίθεται ένα διάνυσμα από παραμέτρους-κόστη με βάση το οποίο προκύπτει και ένα αντίστοιχο διάνυσμα για κάθε μονοπάτι. Για κάθε ζευγάρι κόμβων αποστολέα-παραλήπτη γίνεται καταρχήν η εύρεση όλων των υποψήφιων για χρήση μονοπατιών. Τα υποψήφια μονοπάτια, που λαμβάνονται υπόψη κατά τη διαδικασία επιλογής, έχουν την ιδιότητα να είναι μη-κυριαρχημένα μεταξύ τους. Στη συνέχεια εφαρμόζεται στο σύνολο των μη-κυριαρχημένων μονοπατιών μια συνάρτηση που συνδυάζοντας τις συνιστώσες του κάθε διανύσματος παράγει το κόστος χρήσης κάθε μονοπατιού και έτσι το μονοπάτι με το ελάχιστο κόστος επιλέγεται για χρήση. Στα πλαίσια της εργασίας, καταρχήν μελετήθηκε ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη χρησιμοποιώντας παραμέτρους-κόστη σχετικές με την ενέργεια, όπως η τρέχουσα διαθέσιμη ενέργεια στους κόμβους και η ισχύς μετάδοσής τους. Στη συνέχεια στις παραμέτρους προστέθηκε και η παρεμβολή που δημιουργείται από τη μετάδοση πάνω σε ένα σύνδεσμο. Τα αποτελέσματα των προσομοιώσεων έδειξαν ότι ο αλγόριθμος δρομολόγησης με πολλαπλά κόστη, σε σχέση με τον ελάχιστου μήκους διαδρομής, κατανέμει πιο ομοιόμορφα την κίνηση στο δίκτυο, επιμηκύνει τον χρόνο ζωής του δικτύου και αυξάνει το ποσοστό των παραδιδόμενων πακέτων. Στο επόμενο στάδιο της εργασίας έγινε μια κατανεμημένη υλοποίηση του αλγορίθμου δρομολόγησης με πολλαπλά κόστη, που επιπλέον λαμβάνει υπόψη την κινητικότητα των κόμβων του δικτύου, η οποία και πάλι φάνηκε να υπερέχει έναντι πιο παραδοσιακών πρακτικών. Τέλος η ιδέα της δρομολόγησης με πολλαπλά κόστη εφαρμόστηκε για τη λύση του προβλήματος ενεργο-αποδοτικής πολλαπλής ή ολικής εκπομπής (multicasting ή broadcasting, αντίστοιχα). Στόχος ήταν να βρεθεί η βέλτιστη ενεργο-αποδοτικά ακολουθία συνδέσμων πάνω στους οποίους πρέπει να γίνει μετάδοση ενός πακέτου προκειμένου να υλοποιηθεί η επιθυμητή εκπομπή. Σαν παράμετροι-κόστη χρησιμοποιήθηκαν η τρέχουσα διαθέσιμη ενέργεια και η ισχύς μετάδοσης των κόμβων. Τα αποτελέσματα δείχνουν σαφή υπεροχή του αλγορίθμου με πολλαπλά κόστη έναντι παραδοσιακών λύσεων τόσο για πολλαπλή εκπομπή όσο και για ολική εκπομπή. / Until now, routing in wireless ad hoc networks has been studied by taking into account a single scalar metric for every network link, representing the cost of transmitting through this link. In multicost routing a vector of cost parameters is assigned to each link, based on which a respective cost vector is produced for every path in the network. For every source-destination pair all the candidate paths are initially calculated that are non-dominated to each other. At the cost vectors of the candidate paths, an optimization function is applied in order to produce a cost for each path based on which the selection of the optimal one is made. In the present thesis multicost routing in wireless ad hoc networks was studied initially using as cost parameters the node residual energy and transmission power. As a next step the interference cause by the transmission of each link was added to the cost vectors assigned to each network link. The simulation results showed that multicost routing in comparison to traditional routing practices achieves more uniform traffic distribution and energy consumption in the network, prolongs the network lifetime and increases the percentage of the packets that are successfully delivered to their destinations. Expanding these ideas, the multicost routing algorithm was next implemented in a fully distributed fashion in which additionally the node mobility was taken into account. The results again proved that a significant improvement was accomplished compared to minimum-hop routing. Finally, multicost routing was applied in the field of multicasting and broadcasting in wireless ad hoc networks. The emphasis was again on energy-efficiency by incorporating energy-related cost parameters like node residual energy and transmission power. The multicost algorithm calculates the optimal energy-efficient sequence of nodes that by transmitting implement the desired communication task (multicasting or broadcasting). Simulation results illustrate a clear advantage of our algorithm over established solutions for energy-efficient multicasting and broadcasting.