Η μερική αντικατάσταση των παραδοσιακών ενσύρματων επικοινωνιών από ασύρματες οδήγησε στην ανάγκη για κατάλληλη σχεδίαση των ασύρματων δικτύων, ώστε να υποστηρίζουν τα απαιτούμενα επίπεδα ποιότητας. Η προσφερόμενη ποιότητα περιορίζεται σίγουρα από φυσικά εμπόδια όπως τα όρια που έθεσε ο Shannon, αλλά και από την περιορισμένη γνώση μας στην εκπομπή και διάδοση κυμάτων. Η διαρκής βελτίωση της ικανότητας των ασύρματων δικτύων να προσφέρουν υψηλής ποιότητας υπηρεσίες είναι όμως γεγονός και οφείλεται σε δύο βασικούς ερευνητικούς άξονες, αυτόν που εφευρίσκει νέες μεθόδους επικοινωνίας (διαμόρφωση, κωδικοποίηση, πολυπλεξία, κεραίες κ.α.) και αυτόν που προσπαθεί να βελτιώσει τη διαχείριση των ήδη υπαρχόντων πόρων. Η παρούσα διατριβή προσφέρει επιστημονικές ιδέες και μοντέλα, που έχουν σαν σκοπό την καλύτερη διαχείριση των πόρων. Τα παραδοσιακά αλλά και τα μοντέρνα δίκτυα κινητής τηλεφωνίας έχουν κατακλύσει την αγορά. Η λειτουργία τους όμως, παραμένει να κινείται στα πλαίσια συμβιβασμών, προσφέροντας χαμηλή ποιότητα υπηρεσίας. Η είσοδος των ασύρματων δικτύων υπολογιστών στην αγορά, ως ανταγωνιστές παροχής κλασικών υπηρεσιών (υπηρεσία φωνής και υπηρεσία δεδομένων), δίνει μια ώθηση αναπροσαρμογής των στόχων των δικτύων κινητής τηλεφωνίας. Οι προτεινόμενοι αλγόριθμοι διαχείρισης των δικτύων αυτών προσφέρουν καλύτερη ποιότητα υπηρεσιών με αλλαγή μεμονωμένων μόνο τμημάτων του δικτύου, χωρίς την ασύμφορη ολική επανασχεδίασή του. Αποτελούν δηλαδή πρακτικές λύσεις για την αποδοτικότερη λειτουργία των ήδη εγκατεστημένων δικτύων. Από την άλλη πλευρά, η ανερχόμενη τεχνολογία των ασύρματων δικτύων υπολογιστών βρίσκεται περισσότερο σε ανταγωνισμό με τα κλασικά ενσύρματα δίκτυα υπολογιστών. Το πλεονέκτημα της ελεύθερης κίνησης μετατρέπεται σε δυσβάσταχτο περιορισμό όταν η σύγκριση ποιότητας των δύο δικτύων είναι αναπόφευκτη. Για το λόγο αυτό, υπάρχει η μεγάλη ανάγκη τα ασύρματα δίκτυα να γίνουν ανταγωνιστικά των ενσύρματων και κυρίως να παρέχουν ποιότητα ικανού επιπέδου, ώστε οι διάφορες υπηρεσίες να μπορούν να λειτουργήσουν ανεπηρέαστες από την χρήση του ασύρματου καναλιού. Οι προτεινόμενοι αλγόριθμοι σε αυτόν τον τομέα αποσκοπούν στην βελτίωση της λειτουργίας των ασύρματων δικτύων με τελικό σκοπό την εξασφάλιση επιπέδων ποιότητας. Για την μελέτη των ασύρματων δικτύων κινητής τηλεφωνίας και υπολογιστών και την εξαγωγή συμπερασμάτων απαιτούνται αναλυτικές μέθοδοι περιγραφής και εξομοιώσεις των δικτύων αυτών ώστε να γίνουν και οι κατάλληλες συγκρίσεις της προσφερόμενης ποιότητας. Ο τομέας αυτός της επιστήμης είναι διαρκώς ενεργός καθώς νέες τεχνικές και αναλύσεις προτείνονται συνεχώς. Με στόχο την ανάλυση και την εξομοίωση των προηγούμενα αναφερθέντων αλγορίθμων αναπτύχθηκε ένας αριθμός τεχνικών, που αποτελούν αναπόσπαστο τμήμα της διατριβής αυτής. Στα πλαίσια της διατριβής αυτής και συγκεκριμένα στο τμήμα μελέτης της επίδοσης των δικτύων, προτείνεται η μετατροπή μη γραμμικών αλυσίδων Markov σε γραμμικές, για χρήση σε προβλήματα κίνησης ταυτόχρονων πολλαπλών υπηρεσιών. Η προτεινόμενη μεθοδολογία οδηγεί σε ταχύτατο υπολογισμό της αλυσίδας με τη χρήση μιας προσέγγισης. Παράλληλα, αναλύεται ο χρόνος διαμονής και ο εναπομένων χρόνος διαμονής σε μια κυψέλη. Η ανάλυση γίνεται εκ του μηδενός και με χρήση βασικών στοχαστικών μοντέλων, ενώ το αποτέλεσμα καταλήγει σε κατανομή gamma, κάτι που είχε ήδη παρατηρηθεί από πειράματα στην βιβλιογραφία. Στη συνέχεια κατασκευάζεται ένα ντετερμινιστικό μοντέλο εξομοίωσης που μπορεί να εφαρμοστεί εύκολα μέσω ενός χάρτη σε κάθε πόλη με ορθογώνια δόμηση. Στο τμήμα των δικτύων κινητής τηλεφωνίας προτείνεται ένας αλγόριθμος διαχείρισης και αποδοχής κλήσεων που προκαλεί μεταπομπές συστήματος (system initiated handover). Η χρήση των μεταπομπών αυτών επιφέρει μεταβλητή χωρητικότητα (soft capacity) σε μια ομάδα κυψελών με αποτέλεσμα την αποδοτικότερη διαχείριση πόρων σε περιπτώσεις άνισης κατανομής κίνησης. Ένας άλλος αλγόριθμος προτείνεται για διαρκή διαπραγμάτευση (real-time negotiation) ποιότητας μεταξύ του δικτύου και του χρήστη με αποτέλεσμα την καλύτερη οργάνωση και διαχείριση των πόρων. Αποδεικνύονται η δυνατότητα χρήσης του αλγορίθμου σε πραγματικό χρόνο και τα οφέλη που αποκομίζονται από αυτήν. Στο τμήμα ασύρματων δικτύων υπολογιστών προτείνεται ένα νέο πρωτόκολλο πρόσβασης μέσου, για χρήση στα ασύρματα τοπικά δίκτυα. Το πρωτόκολλο αυτό είναι πλήρως κατανεμημένο (μπορεί να χρησιμοποιηθεί και σε αυτοοργανονούμενα δίκτυα - ad hoc), ενώ προσφέρει τη δυνατότητα παροχής διαφορετικών επιπέδων ποιότητας, από άριστη ποιότητα για κλήσεις πραγματικού χρόνου μέχρι ποιότητα καλύτερης δυνατής προσπάθειας (best effort). Επίσης προτείνονται αλγόριθμοι βελτίωσης των ασύρματων δικτύων αισθητήρων. Αναλύεται συγκεκριμένα ο αυτόματος εντοπισμός κόμβων με χρήση τριγωνισμού και μεταβλητής ισχύος σημάτων-φάρων και η εξοικονόμηση ενέργειας με χρήση συστημάτων πολλαπλών κεραιών (MIMO). / The trend of replacing the traditional wired communications with their wireless counterparts led to the need for better design and organization of wireless networks so as to provide the necessary Quality of Service (QoS) levels. The offered QoS is bounded by Shannon’s limit and from the limitation of human knowledge on the wireless channel matters. However, the constant improvement of network performance is a fact based on two parallel scientific axes, the one that provides new communication techniques (modulation, coding, multiple access, antennas, etc) and the one that handles the already invented methods in an optimized manner. This thesis offers new scientific ideas and models for better resource management of wireless networks. Traditional and modern mobile telephone networks have occupied the market. Nevertheless, their functionality is still based on compromising of offered quality with the needs of a two-way voice application. Wireless computer networks appear in the market as contenders of voice service, acting like a threat to telephone networks. The proposed models for the mobile telephone networks provide solutions for improving overall QoS by altering only minor parts of these already-installed networks. On the other hand, the advancement of the wireless technology gives rise to visions of the so called Broadband Wireless Access. Computer Networks are expected to offer global roaming and provide traditional services over the IP protocol. In this context, QoS is necessary for guaranteeing service levels of quality. The proposed models in this part are focused in offering acceptable quality levels over the wireless channel for these services. The performance analysis of wireless networks requires the use of analytical approaches and simulation of these networks in order to assess the final offered quality. This section of science is constantly developing since new methods and techniques are applied to different parts of research. Through the procedure of analyzing the wireless networks in this thesis, a number of new techniques have been invented which constitute an important part of it. In terms of network traffic description, a new transformation of nonlinear markov chain to linear is proposed. By means of this transformation, the calculation of unbalanced nonuniform traffic can be accelerated. In the section of performance analysis, the sojourn time and the remaining sojourn time are analytically calculated. These cell parameters are found to follow a gamma distribution, a result that is backed from simulations in bibliography. Moreover, a deterministic simulation model is derived to enable easy calculation of these parameters from a map. As regards the mobile telephone networks, a new call admission control scheme is proposed in order to simulate soft capacity functionality in 2G networks. This feature, organizes better the resources in a cluster in cases of inhomogeneous network traffic. Moreover, a QoS negotiation algorithm is proposed for use in 3G networks (e.g. UMTS). Real-time negotiation is proposed for better resource organization and management. The gain from these schemes is calculated and presented. A new Medium Access Control (MAC) protocol is proposed for use in 802.11 Wireless Local Area Networks. This protocol is backward compatible with the protocol 802.11e and offers better quality infrastructure for VoIP services. The proposed protocol is analyzed and simulated and the results are compared to the previously used protocols to showcase the improvements. A new analytical approach with better accuracy is proposed for this reason. Finally, two techniques are proposed for improving the quality of wireless sensor networks. Firstly, a technique for low cost real-time localization with a small number of GPS or other beacons is proposed and tested. Secondly, a means of energy conservatiοn by use of Multiple Input Multiple Output (MIMO) systems is proposed, and then the gain from a QoS scheme is derived.

Τα Δίκτυα Αισθητήρων αποτελούνται από ένα μεγάλο αριθμό μικρών αυτόνομων συσκευών, που αλληλεπιδρούν με το άμεσο περιβάλλον τους μέσω αισθητήρων, επικοινωνούν μεταξύ τους ασύρματα και συνεργάζονται φέροντας εις πέρας εργασίες που δε θα μπορούσε να ολοκληρώσει μία μόνο συσκευή. Κάθε συσκευή του δικτύου διαθέτει περιορισμένη υπολογιστική δύναμη και ενεργειακούς πόρους, επομένως η όσο το δυνατόν λιγότερη κατανάλωση ενέργειας είναι βασικό πρόβλημα των δικτύων αισθητήρων για τη μεγιστοποίηση του χρόνου ζωής τους. Συνήθως τα δίκτυα αισθητήρων αναπτύσσονται σε μεγάλες περιοχές ενδιαφέροντος για την υποστήριξη σημαντικών εφαρμογών του πραγματικού κόσμου. Η πληροφορία που ανιχνεύεται από τους κόμβους αισθητήρων προωθείται προς ένας σταθερό, συνήθως, κέντρο ελέγχου, με αναμεταδόσεις των δεδομένων στους ενδιάμεσους κόμβους. Η διαδικασία αυτή έχει ως αποτέλεσμα τη μεγάλη κατανάλωση ενέργειας στις συσκευές, ιδιαίτερα σε αυτές που βρίσκονται κοντά στο κέντρο ελέγχου, αφού πρέπει να αναμεταδίδουν και τα δεδομένα που φτάνουν από το υπόλοιπο δίκτυο προς το κέντρο ελέγχου. Για την επίτευξη μιας πιο ισορροπημένης και αποδοτικής διαδικασίας συλλογής δεδομένων, τα τελευταία χρόνια έχει υιοθετηθεί μια νέα προσέγγιση, όπου το κέντρο ελέγχου είναι κινητό. Η βασική ιδέα είναι ότι το κέντρο ελέγχου διαθέτει σημαντικά και εύκολα ανανεώσιμα αποθέματα ενέργειας, επομένως μπορεί να κινείται στην περιοχή όπου έχει αναπτυχθεί το δίκτυο αισθητήρων, αναλαμβάνοντας να συλλέξει τα δεδομένα από τους κόμβους με πολύ μικρό κόστος. Ωστόσο, η μετάδοση των δεδομένων μπορεί να παρουσιάζει σημαντικές καθυστερήσεις. Στην παρούσα εργασία αναπτύχθηκαν πρωτόκολλα ελέγχου της κίνησης ενός κέντρου ελέγχου σε δίκτυο αισθητήρων με ανομοιογενή ανάπτυξη των κόμβων αισθητήρων, με στόχο την αποδοτική, ως προς την ενέργεια και τον χρόνο παράδοσης, συλλογή των δεδομένων. Συγκεκριμένα, το κέντρο ελέγχου διαιρεί νοητά το δίκτυο σε περιοχές τις οποίες και επισκέπτεται διαδοχικά, σταματώντας σε κάθε περιοχή για ένα συγκεκριμένο χρονικό διάστημα, ώστε να συλλέξει τα δεδομένα. Προτείνουμε δύο τρόπους κίνησης του κέντρου ελέγχου, ντετερμινιστικό και τυχαίο. Στην τυχαία κίνηση, η επιλογή της επόμενης περιοχής την οποία θα επισκεφτεί το κέντρο ελέγχου γίνεται με τυχαίο τρόπο, εισάγοντας όμως ένα όρο μεροληψίας, έτσι ώστε να προτιμούνται περιοχές που έχουν δεχτεί λιγότερες επισκέψεις. Επιπλέον η μέθοδός μας αποφασίζει το χρόνο παύσης σε κάθε περιοχή λαμβάνοντας υπόψιν κάποιες βασικές παραμέτρους του δικτύου, όπως τα αρχικά αποθέματα ενέργειας των κόμβων αισθητήρων και την πυκνότητα της κάθε περιοχής, έτσι ώστε να παραμένει περισσότερο χρόνο σε περιοχές με μεγαλύτερη πυκνότητα, άρα και μεγαλύτερη ποσότητα πληροφορίας. Με τον τρόπο αυτό επιτυγχάνεται η γρήγορη κάλυψη όλου του δικτύου, καθώς επίσης και η δίκαιη εξυπηρέτηση των επιμέρους περιοχών του δικτύου. Τα προτεινόμενα πρωτόκολλα αξιολογήθηκαν πειραματικά μέσω προσομοίωσης, χρησιμοποιώντας ποικίλες τιμές για βασικές παραμέτρους του δικτύου και σύγκρινοντάς τα με σχετικές υπάρχουσες ευρέως αποδεκτές μεθόδους. Τα αποτελέσματα που πήραμε δείχνουν ότι τόσο ο χρόνος παράδοσης των μηνυμάτων, όσο και η ενέργεια που καταλώθηκε διατηρούνται σε χαμηλά επίπεδα, βελτιώνοντας σημαντικά την προηγούμενη σχετική έρευνα. / Wireless Sensor Networks consist of a large number of small, autonomous devices, that are able to interact with their inveronment by sensing and collaborate to fulfill their tasks, as, usually, a single node is incapable of doing so; and they use wireless communication to enable this collaboration. Each device has limited computational and energy resources, thus a basic issue in the applicastions of wireless sensor networks is the low energy consumption and hence, the maximization of the network lifetime. The collected data is disseminated to a static control point – data sink in the network, using node to node - multi-hop data propagation. However, sensor devices consume significant amounts of energy in addition to increased implementation complexity, since a routing protocol is executed. Also, a point of failure emerges in the area near the control center where nodes relay the data from nodes that are farther away. Recently, a new approach has been developed that shifts the burden from the sensor nodes to the sink. The main idea is that the sink has significant and easily replenishable energy reserves and can move inside the area the sensor network is deployed, in order to acquire the data collected by the sensor nodes at very low energy cost. However, the need to visit all the regions of the network may result in large delivery delays. In this work we have developed protocols that control the movement of the sink in wireless sensor networks with non-uniform deployment of the sensor nodes, in order to succeed an efficient (with respect to both energy and latency) data collection. More specifically, a graph formation phase is executed by the sink during the initialization: the network area is partitioned in equal square regions, where the sink, pauses for a certain amount of time, during the network traversal, in order to collect data. We propose two network traversal methods, a deterministic and a random one. When the sink moves in a random manner, the selection of the next area to visit is done in a biased random manner depending on the frequency of visits of its neighbor areas. Thus, less frequently visited areas are favored. Moreover, our method locally determines the stop time needed to serve each region with respect to some global network resources, such as the initial energy reserves of the nodes and the density of the region, stopping for a greater time interval at regions with higher density, and hence more traffic load. In this way, we achieve accelerated coverage of the network as well as fairness in the service time of each region.Besides randomized mobility, we also propose an optimized deterministic trajectory without visit overlaps, including direct (one-hop) sensor-to-sink data transmissions only. We evaluate our methods via simulation, in diverse network settings and comparatively to related state of the art solutions. Our findings demonstrate significant latency and energy consumption improvements, compared to previous research.

Στο κεφάλαιο 1 της εργασίας αυτής γίνεται μια εισαγωγή στα ασύρματα δίκτυα με την περιγραφή της δομής του ασύρματου καναλιού. Στο κεφάλαιο 2 δίνονται τα χαρακτηριστικά, η δομή και η λειτουργία του συστήματος UMTS. Επίσης στο συγκεκριμένο κεφάλαιο θα παρουσιαστεί αναλυτικά η αρχιτεκτονική και οι λειτουργικότητες του συγκεκριμένου συστήματος. Στο 3ο κεφάλαιο γίνεται μια παρουσίαση του προτύπου WIMAX που δημιουργήθηκε για να ικανοποιήσει τις απαιτήσεις για ασύρματη πρόσβαση ευρείας ζώνης. Στο κεφάλαιο 4 γίνεται μια εκτενής ανάλυση του HSDPA (High Speed Downlink Packet Access) που βασικός του στόχος είναι η αύξηση των πακέτων δεδομένων στην έξοδο. Στο 5ο κεφάλαιο παρουσιάζονται διεξοδικά οι παρεμβολές και ο θόρυβος που μπορούν να εμφανιστούν κατά τη μετάδοση δεδομένων στα ασύρματα δίκτυα. Τέλος, στο 6ο κεφάλαιο γίνεται μια θεωρητική ανάλυση της παρεμβολής ενδοδιαμόρφωσης, ακολουθεί η πειραματική μελέτη της και καταλήγουμε με συμπεράσματα και σχόλια. / -

Ο ανερχόμενος κλάδος των ασύρματων δικτύων αισθητήρων (Wireless Sensor Networks - WSNs) συνδυάζει δυνατότητα αίσθησης, υπολογισμού και επικοινωνίας σε μια μικρή συσκευή. Ενώ οι δυνατότητες ενός και μόνο κόμβου – αισθητήρα (mote) είναι ελάχιστες, η συνύπαρξη πολλών τέτοιων συσκευών δικτυακά συνδεδεμένων μπορεί να οδηγήσουν σε νέες τεχνολογικές δυνατότητες. Κύριος στόχος αυτών των μικρών συσκευών – κόμβων είναι η δειγματοληψία διάφορων φυσικών μεγεθών, η επεξεργασία αυτών των μεγεθών – μετρήσεων και τέλος, η επικοινωνία του κάθε κόμβου με άλλους με στόχο την μετάδοση αυτών των μετρήσεων – πληροφορίας ασφαλώς και αξιόπιστα. Τα κύρια χαρακτηριστικά αυτών των κόμβων όπως, μικρό μέγεθος, χαμηλό κόστος, αυτονομία και δυνατότητα επικοινωνίας είναι που τα κάνουν τόσο ευέλικτα προσδίδοντας έτσι τη δυνατότητα για ανάπτυξη και υλοποίηση χιλιάδων εφαρμογών. Τα ασύρματα δίκτυα αισθητήρων μπορούν να συμβάλουν σε κρίσιμες εφαρμογές που δεν περιορίζονται αποκλειστικά στον ερευνητικό και επιστημονικό χώρο αλλά επεκτείνονται και στον χώρο της υγείας και της ασφάλειας, όπως παρακολούθηση και επίβλεψη ασθενών, πρόβλεψη και αντιμετώπιση φυσικών καταστροφών, οικιακές εφαρμογές, και στοχεύουν στην βελτίωση της ποιότητας ζωής του ατόμου και της κοινωνίας ως σύνολο. Στο πλαίσιο της παρούσας διπλωματικής εργασίας έγινε προσπάθεια προσέγγισης μιας ανεξερεύνητης έως τώρα σε βάθος εφαρμογής Ασυρμάτων Δικτύων Αισθητήρων, των λεγόμενων «έξυπνων» πόλεων, ως προς τις επικοινωνιακές απαιτήσεις και τους περιορισμούς που θέτει και μια προσπάθεια καταγραφής και αξιολόγησης της απόδοσης και της συμπεριφοράς WSN τεχνολογιών υλικού και επικοινωνιακών τεχνικών σε σχέση με τις απαιτήσεις και τους περιορισμούς αυτούς. Παρουσιάζονται πειραματικά δεδομένα από μετρήσεις που διεξήχθησαν σε εξωτερικό περιβάλλον και εξάγονται χρήσιμα συμπεράσματα σχετικά με μελλοντικές κατευθύνσεις. / The increasingly interesting research field of Wireless Sensor Networks combines the possibility of sensing, computing and networking in a small device. While the capabilities of a single sensor node are limited, the combination of multiple such devices communicating over a network may lead to new technological possibilities and challenges. The main goal of these device nodes is the sampling of several physical values, their processing and the communication of the results to other nodes in a safe and reliable way. The main characteristics of wireless sensor nodes such as the small size, the low cost, autonomy and communication capacity render them flexible and suitable for the development of thousands of applications. Wireless sensor networks are most popular for critical applications that go beyond the research and scientific domain expanding to health, environment and security application classes, like surveillance, patient monitoring, natural disaster prediction and home applications, targeted to improve the quality of life of a single person and of society in general. In the context of this master thesis, the state of the art of a WSN application has been investigated, namely smart cities application field, with respect to the imposed networking requirements and communicational restrictions as well as the analysis and evaluation of the behavioral performance of WSN hardware and communication technologies as far as these requirements and limits are concerned. Finally, experimental results are presented based on measurements conducted outdoors and useful conclusions are extracted forming a future roadmap.

Η διπλωματική αυτή σκοπό έχει να μελετήσει στρατηγικές οι οποίες έχουν ως στόχο την αύξηση της αποδοτικότητας με κριτήριο την ενέργεια σε ad hoc δίκτυα. Σε αυτού του είδους τα δίκτυα η ενέργεια είναι κρίσιμος πόρος και η εξοικονόμησή της είναι κρίσιμος παράγοντας. Θα ακολουθήσουμε τον αλγόριθμο δρομολόγησης multi-cost με cost vectors πολλών παραμέτρων. Με βάση αυτά τα cost vectors ένα σύνολο από candidate paths θα υπολογιστούν για κάθε ζευγάρι κόμβων source-destination και μια συνάρτηση βελτιστοποίησης χρησιμοποιείται για να επιλεχθεί το βέλτιστο από αυτά. Οι παράμετροι που μας ενδιαφέρουν είναι ο αριθμός των hops σε ένα μονοπάτι, η υπολειπόμενη ενέργεια και η ισχύς μετάδοσης των κόμβων σε ένα μονοπάτι καθώς και η παρεμβολή που δημιουργείται από την μετάδοση ενός κόμβου. Αυτές οι παράμετροι συνδυάζονται σε ποικίλες συναρτήσεις βελτιστοποίησης οι οποίες αντιστοιχούν σε διαφορετικούς αλγόριθμους δρομολόγησης και οι οποίοι εξετάζονται για την επιλογή του βέλτιστου μονοπατιού. Λαμβάνοντας υπόψη όλες αυτές τις συναρτήσεις εξετάζουμε την συμπεριφορά του δικτύου προσέχοντας την κατανάλωση ενέργειας, το throughput κα. Από τα πειράματα καταλήγουμε στις βέλτιστες από τις συναρτήσεις βελτιστοποίησης. / In this work we study the combination of multi-cost routing and variable transmission power in wireless ad hoc networks. We assume that the nodes have power control capabilities and can adjust their transmission power to their desired level. We propose algorithms for selecting the routes to be followed by the packets and the transmission power to be used by the nodes at each hop in order to reduce interference and energy consumption, and improve network performance. The cost parameters used by the proposed interference/energy-aware routing algorithms are the number of hops of the paths, the interference caused to other nodes, the node residual energies, and the node transmission powers. In the experiments conducted we examine the resulting network performance with respect to energy consumption, packet delay, frequency of collisions, and other parameters of interest. Our results show that the proposed routing algorithms significantly improve network performance and lifetime.

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

Τα ασύρματα δίκτυα που βασίζονται στο πρότυπο ΙΕΕΕ 802.11 είναι σήμερα από τα πλέον δημοφιλή παγκοσμίως. Παρόλη την ευρεία διάδοσή τους υπάρχει σημαντικό πρόβλημα όσον αφορά την ασφάλεια των δεδομένων που διακινούνται εντός του δικτύου. Αρχικά, στο πρότυπο οριζόταν μία μόνο μέθοδος για την ασφάλεια των πληροφοριών, που ονομάζεται WEP (Wired Equivalent Privacy) και βασίζεται στον αλγόριθμο κρυπτογράφησης RC4. Ήδη από το 2000 το WEP έχει αποδειχθεί ανεπαρκές και οι προσπάθειες για την αύξηση του επιπέδου της ασφάλειας οδήγησαν πρόσφατα στο πρότυπο ΙΕΕΕ 802.11i. Το πρότυπο ορίζει μία νέα μέθοδο, που εγγυάται την ασφάλεια των δεδομένων στο MAC επίπεδο. Ονoμάζεται CCMP και βασίζεται στον αλγόριθμο κρυπτογράφησης AES (Advanced Encryption Standard). Το CCMP παρέχει εμπιστευτικότητα (confidentiality), επικύρωση (authentication), ακεραιότητα (integrity) και προστασία από την επανάληψη πακέτων (replay protection). Βασίζεται στη χρήση του αλγόριθμου κρυπτογράφησης AES σε κατάσταση λειτουργίας CCM. Το CCM συνδυάζει την κατάσταση λειτουργίας CTR (Counter mode) για εμπιστευτικότητα και την CBC (Cipher Block Chaining mode) για επικύρωση και ακεραιότητα. Το CCM προστατεύει την ακεραιότητα τόσο των δεδομένων του πακέτου, όσο και συγκεκριμένων τμημάτων της επικεφαλίδας του πακέτου. Η επεξεργασία που γίνεται στο CCMP από τον αλγόριθμο AES χρησιμοποιεί μέγεθος κλειδιού 128-bit και μέγεθος μπλοκ 128-bit. Μετά την επεξεργασία από το CCMP το μέγεθος του πακέτου έχει επεκταθεί κατά 16 bytes, 8 bytes για την επικεφαλίδα του CCMP και 8 bytes για την ψηφιακή υπογραφή MIC (Message Integrity Code). Τα δεδομένα του πακέτου και το MIC μεταδίδονται κρυπτογραφημένα, αφού προστεθεί η αρχική επικεφαλίδα του πακέτου και η επικεφαλίδα του CCMP. Στα πλαίσια της διπλωματικής μελετήθηκαν διάφορες αρχιτεκτονικές για την υλοποίηση του συστήματος κρυπτογράφησης/αποκρυπτογράφησης σύμφωνα με το CCMP. Οι αρχιτεκτονικές αυτές παρουσιάζουν διαφορετικά χαρακτηριστικά όσον αφορά την επιφάνεια, την ταχύτητα λειτουργίας και το συνολικό throughput. Η υλοποίηση και ο έλεγχος ορθής λειτουργίας των σχεδιασμών έγινε σε τεχνολογία FPGA Spartan-3 της εταιρίας Xilinx. / Today, wireless networks IEEE 802.11 are very popular. Despite their worldwide deployment there is significant problem, as far as the security of the data exchanged through the network, is concerned. Initially, there was only one method defined for the security of information, called WEP (Wired Equivalent Privacy). WEP is based on the RC4 encryption algorithm. It is proven, since 2000, that WEP provides insufficient security and recent research efforts in the direction of a more secure solution have led to IEEE 802.11i standard. A new method, applied in the MAC layer, which provides a higher level of security, is defined in this standard. This method is called CCMP and is based on the AES encryption algorithm (Advanced Encryption Standard). CCMP provides confidentiality, authentication, integrity check and replay protection. It uses AES in the CCM mode of operation. CCM combines the CTR (Counter) and CBC (Cipher Block Chaining) modes of operation, for confidentiality and authentication/integrity, respectively. CCM protects the integrity of plaintext data, as well as selected portions of the IEEE MAC header. CCMP processing uses AES with 128-bit encryption key and 128-bit block size. CCMP extends the original packet size by 16 bytes; 8 bytes for the CCMP header and 8 bytes for the digital signature called MIC (Message Integrity Code). Plaintext data and MIC are encrypted and the original MAC header, as well as the CCMP header is included in the packet before transmission. Various architectures for the implementation of an encryption/decryption system based on CCMP were studied. These architectures have different characteristics concerning area overhead, minimum clock period and overall throughput. Circuits were implemented and verified using Xilinx’s Spartan-3 FPGA technology.

Η παρούσα μεταπτυχιακή εργασία καταπιάνεται με την περιοχή των Aσύρματων Δικτύων Αισθητήρων και τα προβλήματα που αυτά αντιμετωπίζουν στην αποδοτική δρομολόγηση της πληροφορίας. Τα ασύρματα δίκτυα αισθητήρων είναι πολύπλοκα συστήματα που αποτελούνται από έναν αριθμό από σχετικά απλές και αυτόνομες συσκευές αίσθησης, οι οποίες αναπτύσσονται σε μια γεωγραφική περιοχή. Η ιδιομορφία των συσκευών αυτών έγκειται στο ότι αντιμετωπίζουν περιορισμούς όσων αφορά τόσο το ενεργειακό τους απόθεμα και συνεπώς την επιχειρησιακή ζωή τους, όσο και στις ικανότητές τους να επεξεργάζονται, αποθηκεύουν και zεκπέμπουν πληροφορία. Η χρησιμότητα των Ασύρματων Δικτύων Αισθητήρων (ΑΔΑ) στηρίζεται στην ικανότητά τους να αναπτύσσονται εύκολα και σχετικά φθηνά, σε μια περιοχή ενδιαφέροντος στην οποία και παρακολουθούν κάποιο συγκεκριμένο φαινόμενο. Επιπλέον φροντίζουν να ενημερώνουν τους σταθμούς βάσης για την κατάσταση και την εξέλιξη του φαινομένου. Στο πλαίσιο αυτό έχουν αναπτυχθεί μια σειρά από αρχιτεκτονικές ασύρματων αισθητήριων κόμβων αλλά και ποικίλα πρωτόκολλα επικοινωνίας αυτών, τα οποία τα δομούν σε δίκτυα. Η συνεισφορά μας έγκειται στην πρόταση τριών νέων πρωτοκόλλων επικοινωνίας για τα ΑΔΑ τα οποία προσπαθούν να εφαρμόσουν την ιδέα της Δικαιοσύνης επιδιώκοντας να βελτιώσουν τόσο την απόδοση των ΑΔΑ όσο και να επιμηκύνουν την επιχειρησιακή τους ζωή. Τα πρωτόκολλα που παρουσιάζουμε άντλησαν την έμπνευσή τους από το πρωτόκολλο PFR (Πρωτόκολλο Πιθανοτικής Προώθησης των Χατζηγιαννάκη, Δημητρίου, Νικολετσέα και Σπυράκη). Όλα τα προτεινόμενα πρωτόκολλα κατηγοριοποιούνται στο επίπεδο Δικτύου του μοντέλου OSI. / This MSc thesis is about Wireless Sensor Networks and focuses on the problems these networks face in order to route information efficiently Wireless Sensor Networks (WSNs) are complex systems which consist of a number of relative simple autonomous sensing devices. These devices are deployed on a geographical area. The particularity of them lies on the fact that they face serious limitations concerning their energy reserves and consequently their operational life as well as regarding their computational, storage and communication capabilities. WSN's usefulness is mainly about its ability of easy and cheap deployment on an area of concern, where it monitors a particular phenomenon. Moreover the WSN's nodes take the initiative to inform certain base stations regarding the status and evolution of this phenomenon. In this context there is a great volume of work in relation to sensor node architectures and communication protocols which turn these numbers of devices to working networks. Our contribution sums up to the proposal of three novel communication protocols for WSNs, which attempt to enforce the idea of Fairness in order to better WSN�s performance and elongate their life. These protocols are highly influenced by PFR protocol introduced by Chatzigiannakis, Demetriou, Nikoletseas and Spirakis. All the proposed protocols belong to the network layer of the OSI standard.

Στις ημέρες μας, εμφανίζεται ολοένα και σε περισσότερα πλαίσια η ανάγκη για την ανάπτυξη αξιόπιστων ασύρματων αυτοοργανούμενων δικτύων (Mobile Ad hoc Networks). Τα δίκτυα αυτά δεν απαιτούν την ύπαρξη μίας σταθερής υποδομής ή διαδικασίας προετοιμασίας και εγκατάστασης, ενώ παράλληλα επιτρέπουν τη δημιουργία δυναμικών και συχνά μεταβαλλόμενων τοπολογιών με υπολογιστικούς κόμβους που κινούνται με τυχαίο τρόπο και συχνά χαρακτηρίζονται από αυστηρούς ενεργειακούς περιορισμούς. Το πρόβλημα της αποτελεσματικής σχεδίασης και ανάπτυξης αυτοοργανούμενων δικτύων αποτελεί μία πρόκληση που έχει προσελκύσει αρκετές ερευνητικές προσπάθειες. Στο πλαίσιο της παρούσας εργασίας, το ενδιαφέρον επικεντρώνεται στη μελέτη αλγορίθμων δρομολόγησης δεδομένων μεταξύ των κόμβων ενός αυτοοργανούμενου ασύρματου δικτύου. Αρχικά, παρατίθεται μία κριτική επισκόπηση των αλγορίθμων δρομολόγησης που υπάρχουν στη βιβλιογραφία. Στη συνέχεια, λαμβάνει χώρα η υλοποίηση του πρωτοκόλλου ZRP (Zone Routing Protocol), το οποίο όπως προκύπτει από την προαναφερθείσα κριτική επισκόπηση παρουσιάζει σημαντικά πλεονεκτήματα για αυτήν την κατηγορία δικτύων. Ακολουθεί η παρουσίαση τριών σειρών προσομοιώσεων που πραγματοποιήθηκαν για την ποσοτική αξιολόγηση του ZRP πρωτοκόλλου σε διάφορα σενάρια φορτίου και κινητικότητας των υπολογιστικών κόμβων. Παράλληλα, πραγματοποιήθηκε και μία εκτεταμένη ποσοτική σύγκριση του DSR πρωτοκόλλου με το ZRP. Τέλος, στο πλαίσιο της εργασίας προτείνεται μία βελτιωμένη παραλλαγή του πρωτοκόλλου ZRP, το επονομαζόμενο AZRP (Adaptive Zone Routing Protocol). Το AZRP πρωτόκολλο προσπαθεί να βελτιώσει και να επεκτείνει τους μηχανισμούς του ZRP εισάγοντας μία τεχνική αυτόματης προσαρμογής του μεγέθους της ζώνης δρομολόγησης κάθε κόμβου. Με αυτόν τον τρόπο το AZRP μπορεί να προσαρμόζεται πιο αποτελεσματικά σε οποιαδήποτε κατάσταση του δικτύου ανά πάσα χρονική στιγμή. Η ιδέα αυτή οδήγησε και σε μία σχετική επιστημονική δημοσίευση στο πλαίσιο της διπλωματικής αυτής. / Nowadays, there is a growing need to deploy reliable mobile ad hoc networks (MANETs). These networks enable the development of dynamic and frequently changing topologies of computational nodes that move randomly, and typically have energy consumption limitations, without relying on a centralized, pre-configured infrastructure. The abundance of challenges in the design and deployment of such networks has attracted the interest of many research efforts. The focus of this thesis is on the study of routing algorithms for MANETs. Initially, the thesis presents a critical survey of such routing algorithms mentioned in the bibliography. Next, an implementation of the ZRP protocol (Zone Routing Algorithm) is presented, which according to the aforementioned survey was found to have significant advantages for MANETs. Subsequently, three sets of simulations that evaluated the performance of the ZRP protocol in different scenarios of node mobility and network traffic are presented. In addition, an extended quantitative comparison of the DSR and ZRP protocol performance is also presented. Finally, in the context of this thesis a new, improved version of the ZRP protocol is proposed, named AZRP (Adaptive Zone Routing Protocol). The AZRP protocol tries to improve the performance of ZRP by introducing a mechanism that automatically adjusts the size of the routing zone of each node based on the overall network traffic and node mobility. The latter idea led to a related publication in the context of this thesis.

Στην παρούσα εργασία έγινε μια πρώτη προσπάθεια ενασχόλησης με τα Ασύρματα Δίκτυα Αισθητήρων, πιο γνωστά στον επιστημονικό κόσμο ως Wireless Sensor Networks ή WSNs. Μελετήσαμε τα βασικά χαρακτηριστικά των δικτύων αυτών, όπως οι τοπολογίες τους και η αρχιτεκτονική τους. Επίσης, μελετήσαμε την αρχιτεκτονική των ασύρματων κόμβων που απαρτίζουν το δίκτυο, που είναι γνωστά σαν motes. Τα motes έχουν την ικανότητα τοπικής επεξεργασίας των δεδομένων που συλλέγουν και την ασύρματη μετάδοσή τους σε έναν κεντρικό σταθμό για περαιτέρω επεξεργασία. Τη λειτουργία αυτή διεκπαιρεώνει μια μονάδα μικροεπεξεργαστή με τη χρήση ενός ολοκληρωμένου chip για την ασύρματη μετάδοση. Για τη συλλογή των μετρήσεων μπορούν να φιλοξενήσουν διάφορες πλατφόρμες ψηφιακών αισθητήρων. Στην παρούσα εργασία έγινε χρήση της υπολογιστικής μονάδας micaz και της πλατφόρμας αισθητήρων MTS400/420. Οι πλατφόρμες αυτές φιλοξενούν αισθητήρες υγρασίας/θερμοκρασίας, βαρομετρικής πίεσης/θερμοκρασίας, φωτεινότητας, μέτρησης δονήσεων και ειδικά η 420 πλατφόρμα έχει υποδοχή και για μονάδα GPS. Σκοπός μας ήταν η ανάπτυξη ενός γραφικού περιβάλλοντος μέσω του οποίου θα απεικονίζαμε τις μετρήσεις που έστελναν στον υπολογιστή τα motes. Η ανάπτυξη του γραφικού περιβάλλοντος έγινε στο Matlab. Για το σκοπό αυτό, ήταν απαραίτητη η σύνδεση ενός mote στον υπολογιστή που θα λειτουργούσε σαν ενδιάμεσος αποδέκτης των δεδομένων και θα τα προωθούσε στον υπολογιστή μέσω της σειριακής θύρας. Για την προβολή και αποθήκευση των δεδομένων στον υπολογιστή, έγινε χρήση του interface Χlisten. / At this thesis there was a first attempt of occupation with Wireless Sensor Networks, most kown to the scientific world as WSNs. We studied the basic characteristics of these networks such as topologies and architecture. We also studied the architecture of the wireless nodes which form the network, also known as motes.The motes have the ability of local data computation and the wireless transmition of them to a base station, where they can further processed. This ability is performed by a microprocessor unit with the use of a single integrated chip responsible for the radio transmition. The data collection can be performed by many digital sensor platforms. At this paper, it has been used the micaz computional unit and the MTS400/420 sensor platform of Crossbow company. These platforms are integrated with sensors that measure relative humidity/temperature, barometric pressure/temperature, illumination, acceleration on axis x and y and especially the 420 platform can integrate a GPS module. Our goal is the development of a Graphical User Interface (GUI) through which we can plot the data that the sensors would send. The development of GUI made with Matlab. For this purpose, it was necessary the connection of a mote to the computer, that would behave like an intermediate receiver and would forward the data packets to the computer through the serial port. The MIB520 board was used for this purpose. For the data projection and saving to the computer, the xlisten interface was used.