Προσδιορισμός του ελάχιστου μιας μη γραμμικής συνάρτησης υπό τους όρους μη γραμμικών περιορισμών κατά μήκος καμπυλόγραμμων μονοπατιών αναζήτησης. / Definition of the minimum of a non linear function by using non linear constraines.

Στην παρούσα διδακτορική διατριβή ασχολούμαστε με ζητήματα ελαχιστοποίησης της κατανάλωσης ενέργειας που ανακύπτουν σε ασύρματα δίκτυα. Εξετάζουμε τόσο την περίπτωση ασυρμάτων δικτύων τύπου ad hoc όσο και την περίπτωση όπου υπάρχει ένα σταθερό ενσύρματο δίκτυο το οποίο συνδέει τους σταθμούς εκπομπής, οι οποίοι χρησιμοποιούν ασύρματα μέσα προκειμένου να μεταδώσουν μηνύματα στους χρήστες. Στην πρώτη κατηγορία, μελετούμε τόσο περιπτώσεις όπου η συνάρτηση κόστους στις ακμές είναι συμμετρική, όσο και περιπτώσεις όπου δεν ισχύει αυτή η υπόθεση. Εξετάζουμε επιπλέον προβλήματα που προκύπτουν όταν θεωρούμε ότι οι σταθμοί βρίσκονται σε κάποιον Ευκλείδειο χώρο και η απόσταση εξαρτάται από την Ευκλείδεια απόσταση. Παρουσιάζουμε αποτελέσματα υπολογιστικής δυσκολίας για την εύρεση τόσο της βέλτιστης λύσης όσο και μιας καλής προσεγγιστικής λύσης. Από την άλλη πλευρά, αποδεικνύουμε άνω φράγματα στον λόγο προσέγγισης διάφορων πολυωνυμικών αλγορίθμων. Στην περίπτωση που θεωρούμε πως οι σταθμοί μετάδοσης είναι συνδεδεμένοι με ένα ενσύρματο δίκτυο, έχουμε το πρόβλημα της συσταδοποίησης. Παρουσιάζουμε έναν βέλτιστο πολυωνυμικό αλγόριθμο για την περίπτωση όπου τα σημεία είναι συνευθειακά, ενώ αποδεικνύουμε αποτελέσματα υπολογιστικής δυσκολίας για την περίπτωση των δύο ή περισσοτέρων διαστάσεων. Τέλος, παρουσιάζουμε έναν προσεγγιστικό αλγόριθμο του οποίου ο λόγος προσέγγισης μπορεί να πλησιάσει αυθαίρετα κόντα το 1, με άλλα λόγια παρουσιάζουμε ένα προσεγγιστικό σχήμα πολυωνυμικού χρόνου. / In this dissertation we focus on issues related to energy consumption in wireless networks. We examine both ad hoc wireless networks, where we assume that there is no wired infrastructure, and networks where antennas are wired through a traditional, wired backbone network but they transmit messages to the users using wireless means. In the first case, we consider networks where the distance function can be symmetric or asymmetric; asymmetric edge cost functions can be used to model medium abnormalities or batteries with different energy levels. We prove results concerning the NP-hardness of computing the optimal solution or in some cases even an approximate solution, and also present upper bounds on the approximation ratio of several polynomial time algorithms. In the case where the antennas are connected through a wired backbone network, we consider a clustering problem. We present an optimal polynomial time algorithm for the special case when points are located on a line. We also present NP-hardness results concerning special cases of the problem in the case of 2 or more dimensions. Finally, we conclude with a polynomial time approximation scheme (PTAS).

Η αλματώδης ανάπτυξη που παρατηρείται τα τελευταία χρόνια στον τομέα των οπτικών δικτύων τηλεπικοινωνιών, έχει ως συνέπεια την αύξηση της κατανάλωσης ενέργειας. Σήμερα υπολογίζεται ότι η ενέργεια που οφείλεται σε IT τεχνολογίες αποτελεί το 1%-2% της παγκόσμιας κατανάλωσης. Ωστόσο, τα ποσοστά αυτά αναμένεται να αυξηθούν δραματικά μιας και όλο και περισσότερες εφαρμογές, που απαιτούν μεγάλο εύρος ζώνης (π.χ. video streaming, HDTV), αναπτύσσονται ταχύτατα. Μέχρι πρόσφατα ο κύριος περιορισμός στην ανάπτυξη των δικτύων ήταν το κόστος εξοπλισμού και μετάδοσης. Σήμερα το μεγαλύτερο πρόβλημα είναι η όλο και αυξανόμενη κατανάλωση ενέργειας. Έτσι λοιπόν πιο energy-aware προσεγγίσεις για το σχεδιασμό, την υλοποίηση και τη λειτουργία των οπτικών δικτύων κρίνονται πλέον απαραίτητες. Για την αντιμετώπιση του προβλήματος της κατανάλωσης ενέργειας σε οπτικά δίκτυα υπάρχουν δυο προσεγγίσεις: η ανάπτυξη ενεργο-αποδοτικών συσκευών δικτύου ή η ανάπτυξη αλγορίθμων δρομολόγησης και ανάθεσης μήκους κύματος (RWA) που να λαμβάνουν υπόψη τους και την ενέργεια που καταναλώνει το δίκτυο. Στην παρούσα διπλωματική εργασία επιλέχθηκε η δεύτερη προσέγγιση όπου και αναπτύχθηκαν Energy Aware RWA αλγόριθμοι για τον σχεδιασμό WDM οπτικών δικτύων με στόχο την ελαχιστοποίηση της ενέργειας που καταναλώνεται. Αυτό επιτυγχάνεται μειώνοντας τον αριθμό των συσκευών του δικτύου, όπως αναγεννητές, ενισχυτές, add/drop τερματικά κ.τ.λ. που είναι γνωστό ότι καταναλώνουν αρκετή ενέργεια κατά τη λειτουργία τους. Αρχικά αναπτύχθηκε ένας αλγόριθμος σε Ακέραιο Γραμμικό Ακέραιο Προγραμματισμό (Integer Linear Programming - ILP) που ελαχιστοποιεί από κοινού όλες εκείνες τις συσκευές του δικτύου που καταναλώνουν ενέργεια. Έπειτα το πρόβλημα χωρίζεται σε δυο υπο-προβλήματα: την κατανομή αναγεννητών σε κόμβους του δικτύου όπου η αναγέννηση είναι απαραίτητη και στο Energy Aware RWA. Σε αυτή τη περίπτωση εκτός από ILP προγραμματισμό εφαρμόζεται επίσης και χαλάρωση των περιορισμών ακεραιότητας (LP προγραμματισμός) ώστε να μπορούν να προκύψουν λύσεις και για μεγαλύτερες τοπολογίες. Για τον υπολογισμό της απόδοσης των προτεινόμενων αλγορίθμων διεξάγονται μια σειρά από πειράματα εξομοιώσεων σε Matlab, με τη βοήθεια του LINDO API για την επίλυση των (I)LP προβλημάτων σε ένα μικρό δίκτυο αλλά και στο ευρωπαϊκό δίκτυο Geant-2. Oι προτεινόμενοι αλγόριθμοι συγκρίνονται με τυπικούς RWA αλγορίθμους που δεν λαμβάνουν υπόψη την ενέργεια ή ελαχιστοποιούν κάποιες από τις συνιστώσες του δικτύου. Οι υπολογισμοί δείχνουν ότι η κατανάλωση της ενέργειας του δικτύου μπορεί να μειωθεί μέχρι και 45% σε δίκτυο με συνδέσμους μονής ίνας και μέχρι και 65% σε συνδέσμους διπλής ίνας. / The continuing deployment and upgrade of optical telecommunication networks drive up power and energy consumption, in a way that makes operators worry that future energy consumption levels may pose constraints on communications growth that are more significant than those posed by bandwidth considerations. As community concerns about global energy consumption grow, the power consumption of the optical networks is becoming an issue of increasing importance. Even though energy consumption of IT-related infrastructure currently represents between 1% and 2% of global energy consumption, such values are destined to rise, as more bandwidth-hungry applications (such as video streaming, and HDTV in particular) continue to be developed. Thus, it seems that an energy-aware approach is increasingly needed during the design, implementation and operation of optical networks. Two different approaches can be explored to reduce energy consumption in optical networks: the improvement of the energy efficiency of the equipment and the energy awareness of the Routing and Wavelengths Assignment (RWA) algorithms. In this work the energy minimization problem in optical networks is considered from an algorithmic perspective. The objective of the proposed algorithms is to plan optical WDM networks so as to minimize the energy consumed, by minimizing the number of the most energy-consuming components. Such components can be amplifiers, regenerators, add/drop terminals, optical fibers, etc. Firstly an Integer Linear Programming (ILP) formulation is given that aims at jointly minimizing the energy consuming modules present in an optical network, such as the regenerators, amplifiers, wavelength selective switches, etc. Then the problem for a general (translucent network) is decomposed into a regeneration placement problem, and an energy-aware RWA for transparent networks problem, where again ILP formulations are given to minimize energy consumption. The ILP of the decomposed problem is solved as an LP problem, by relaxing the integer constraints, in order to obtain solutions for larger network topologies. In order to evaluate the performance of the proposed Energy Aware (EA)-RWA algorithms a number of simulation experiments is carried out. All the RWA algorithms are implemented in Matlab and LINDO API is used to solve the corresponding (I)LP problems. The proposed algorithms are compared with RWA algorithms that do not consider energy minimization techniques or RWA algorithms that partially take into account energy consuming components. The simulation results showed that the energy consumption in the optical layer can be reduced by up to 45% in single fiber networks and by up to 65% in multi-fiber networks.

Η παρούσα διπλωματική εργασία πραγματεύεται τη διερεύνηση μεθόδου εξοικονόμησης ενέργειας σε ηλεκτροκίνητο όχημα, μέσω ελέγχου του κινηητήρα για την ελαχιστοποίηση των απωλειών του ηλεκτροκινητήριου συστήματος. Στη συγκεκριμένη περίπτωση, το ηλεκτροκινητήριο σύστημα αποτελείται από ασύγχρονο τριφασικό κινητήρα οδηγούμενο. από αντιστροφέα τάσης, ο οποίος τροφοδοτείται από συσσωρευτές. Η εργασία αυτή εκπονήθηκε στο Εργαστήριο Ηλεκτρομηχανικής Μετατροπής Ενέργειας του Τμήματος Ηλεκτρολόγων Μηχανικών της Πολυτεχνικής Σχολής του Πανεπιστημίου Πατρών. Σκοπός της διπλωματικής αυτής εργασίας είναι η ανάπτυξη της μεθόδου εξοικονόμησης ενέργειας σε ηλεκτροκίνητο όχημα, μέσω ελαχιστοποίησης των απωλειών του συστήματος. Η ελαχιστοποίηση των απωλειών υλοποιείται μεταβάλλοντας τη μαγνητική ροή διακένου του ασύγχρονου κινητήρα και το λόγο μετάδοσης του κιβωτίου ταχυτήτων. Απώτερος στόχος είναι η επέκταση της μεθόδου ελαχιστοποίησης των απωλειών του ηλεκτροκινητήριου συστήματος που αναπτύχθηκε στη διδακτορική διατριβή του Ε.Ρίκου, "Μέθοδοι Εξοικονόμησης Ενέργειας σε Ηλεκτροκίνητα Οχήματα". Πανεπιστήμιο Πατρών, Τμήμα Ηλεκτρολόγων Μηχανικών και Τεχνολογίας Υπολογιστών, Πάτρα 2005, στην περίπτωση κινητήριου συστήματος με ασύγχρονο τριφασικό κινητήρα και αντιστροφέα και επιβεβαίωση της αποτελεσματικότητάς της σε θεωρητικό επίπεδο, επίπεδο προσομοίωσης και πειραματικό. Αρχικά, εξετάζονται οι σχέσεις που περιγράφουν τις απώλειες ισχύος που παράγονται κατά τη λειτουργία του ηλεκτροκίνητου οχήματος, καθώς και η εξάρτησή τους από τη μαγνητική ροή διακένου και το λόγο μετάδοσης του κιβωτίου ταχυτήτων. Στη συνέχεια, δείχνεται με γραφικό τρόπο η δυνατότητα ελαχιστοποίησης των απωλειών του συστήματος με τη μεταβολή της μαγνητικής ροής διακένου και του λόγου μετάδοσης για δεδομένες μόνιμες καταστάσης λειτουργίας (ταχύτητα και δύναμη στους τροχούς του οχήματος). Το επόμενο βήμα είναι η επιβεβαίωση της θεωρητικής μελέτης μέσω προσομοίωσης η οποία γίνεται σε περιβάλλον Matlab/ Simulink. Τέλος, κατασκευάζονται στο εργαστήριο πειραματική διάταξη με χρήση της οποίας διεξάγονται μετρήσεις για την επιβεβαίωση και αξιολόγηση της θεωρητικής μελέτης. / This diploma thesis discourses the analysis of an energy saving method in an electrically powered vehicle by control of the electric motor for the loss minimization of the electromotion system. In this case, the electromotion system consists of an induction motor, driven by a voltage inverter which is fed by batteries. This project was based in the Laboratory of Electromechanincal Energy Conversion of School of Engineering of University of Patras. The objective of this project is the development of the method for energy saving in an electrically powered vehicle, through system losses minimization. The loss minimization is carried out by controlling motor air-gap magnetic flux and gear ratio. The aim of the project is the extension of the electromotion system loss minimization method which was developed in the doctoral thesis of Evangelos Rikos, "Methods of energy saving in electric vehicles", University of Patras, department of Electrical and Computer Engineering, Patras 2005 for the case of a three phase induction motor and inverter electric drive, as well as the confirmation of its effectiveness in theoretical level, simulation and experimental level. At first, an analysis of the equations that describe the losses of the electric vehicle is performed as well as their dependence from the air-gap flux and gear ratio. Following, is graphically demonstrated the ability to minimize the losses of the electromotion system by controlling the air-gap flux and the gear ratio for certain steady states (values of force and velocity at the vehicle's wheels). The next step is the confirmation of the theoretical analysis by simulation which is carried out in Matlab/Simulink environment. Finally, a three phase inverter is constructed with the use of which, the experiment is carried out on order to confirm the efficiency and evaluate the accuracy of the theoretical analysis

Σκοπός αυτής της εργασίας είναι η μελέτη τεχνικών κατανεμημένου προσανατολισμού σε πραγματικές συνθήκες. Πιο συγκεκριμένα σε αυτά στα συστήματα θεωρείται ότι ο κόμβος-πομπός δεν έχει καλή σύνδεση με το δέκτη και κατά συνέπεια δεν μπορεί να επικοινωνήσει απευθείας με τον κόμβο-δέκτη χωρίς δραματική αύξηση της ενέργειας μετάδοσης. Παρόλα αυτά η χρήση κατανεμημένου προσανατολισμού δίνει τη δυνατότητα να βελτιωθεί σημαντικά η κατανάλωση ενέργειας. Το σχήμα που θα χρησιμοποιηθεί είναι ενίσχυση και προώθηση (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".

Το αντικείμενο της διατριβής αυτής είναι η μελέτη της διαστρωματικής (cross-layer) προσέγγισης ανάπτυξης ασύρματων δικτύων κατανεμημένης λειτουργίας με απαιτήσεις επικοινωνίας πραγματικού χρόνου και περιορισμένους διαθέσιμους πόρους. Επιπλέον βασικό στόχο αποτελεί και η σχεδίαση, πρόταση αντίστοιχης αρχιτεκτονικής η οποία στοχεύει στη βέλτιστη διαχείριση διαθεσίμων δικτυακών πόρων σε καταστάσεις συμφόρησης του δικτύου και κατά συνέπεια στην βελτίωση της απόδοσης αυτού. Μέσα από μελέτες στα πλαίσια της διατριβής αναδεικνύεται η σημασία του φαινομένου συμφόρησης ως κύριου παράγοντα σπατάλης δικτυακών πόρων καθώς και οδήγησης του δικτύου σε κατάσταση κορεσμού με αρνητική επίπτωση σε όλες τις παραμέτρους απόδοσης του δικτύου. Στόχος, λοιπόν, της προτεινόμενης επικοινωνιακής αρχιτεκτονικής είναι η αποφυγή του φαινομένου συμφόρησης έτσι ώστε το δίκτυο να οδηγείται δυναμικά σε ένα σταθερό σημείο απόδοσης (όσο αυτό είναι δυνατό) το οποίο θα επιτρέπει στο δίκτυο να αποδίδει όσο το δυνατόν καλύτερα αποφεύγοντας τη ίδια στιγμή άσκοπη σπατάλη πόρων. Βασική παράμετρος στη σχεδίαση αποτελεί η συμβατότητα τόσο ως προς σημαντικό εύρος διαθέσιμων πρωτοκόλλων σε διάφορα επίπεδα, όσο και ως προς τη δυνατότητα συνύπαρξης κόμβων που ενσωματώνουν την προτεινόμενη αρχιτεκτονική με κόμβους χωρίς αυτήν. Η προτεινόμενη αρχιτεκτονική υλοποιήθηκε στα πλαίσια γνωστού και αξιόπιστου δικτυακού εξομοίωση. Αξιολόγηση της υλοποίησης αυτής μέσα από μεγάλο αριθμό πειραμάτων έδειξε επίτευξη του στόχου καθώς το φαινόμενο της συμφόρησης αντιμετωπίστηκε σε όλες τις περιπτώσεις με σημαντικά οφέλη στην απόδοση του δικτύου και διαχείριση των πόρων. Επιπλέον, λόγω του μεγάλου βαθμού παραμετροποίησης αποτελεί ιδανική βάση για μελλοντικές προεκτάσεις. / This objective of this dissertation is the study of cross-layer approach applied on the development of distributed wireless networks with real-time response demands and scarce available resources. Furthermore, another main goal is the design and proposal of a respective network architecture aiming at optimum resource management under congestion scenarios and therefore maximization of network performance. Through various studies undertaken in the context of this dissertation the importance of the congestion problem is presented as a main factor leading the network to resource waste and saturation conditions negatively affecting all network performance metrics. Consequently, this dissertation aims in proposing a cross-layer architecture able to detect and tackle congestion phenomenon by dynamically retaining network performance at a steady state (as than is possible) where network performs optimally and resource waste in minimized. Among others, a main parameter is retaining compatibility with a wide range of widely used protocols of various layers as well compatibility concerning the coexistence in the same network of stations supporting with stations not supporting the proposed architecture. The proposed architecture is implemented in the context of widely known and used network simulator. Evaluation of this implementation through numerous simulations showed that the objectives are met since congestion phenomenon is tackled in most cases with significant benefits concerning network performance and resource management. Furthermore, due to the high parametrization degree it constitutes a very good base for future expansions.