Το βασικό χαρακτηριστικό των ασύρματων δικτύων αυθαίρετης τοπολογίας (wireless ad hoc networks) είναι πως δεν απαιτούν την ύπαρξη σταθερής υποδομής (σε αντίθεση π.χ. με τα κυψελωτά δίκτυα). Ένα ιδιαίτερα σημαντικό παράδειγμα τέτοιων δικτύων αποτελούν τα λεγόμενα δίκτυα αισθητήρων (sensor networks), τα οποία μπορούν να χρησιμοποιηθούν σε τομείς όπως η παρακολούθηση και καταγραφή φυσικών φαινομένων, ή η προσωρινή δημιουργία δικτύου επικοινωνίας σε περιοχές που έχουν πληγεί από κάποια καταστροφή, κλπ., και επομένως αποτελούν μια ερευνητική περιοχή μεγάλου ενδιαφέροντος. Στα δίκτυα αυτά, όταν ένας κόμβος πρέπει να στείλει ένα πακέτο σε κόμβο που βρίσκεται εκτός της ακτίνας μετάδοσης του, τότε η μετάδοση γίνεται μέσω κόμβων που βρίσκονται πάνω σε μια διαδρομή μεταξύ αυτών των δύο κόμβων. Επειδή, όμως, οι κόμβοι αυτοί συνήθως έχουν περιορισμένη ενέργεια, ο τρόπος δρομολόγησης είναι καθοριστικός για τη λειτουργία του δικτύου. Τα πρωτόκολλα δρομολόγησης βασίζονται σε διάφορες μεθόδους όπως: κάθε κόμβος να επικοινωνεί μόνο με ορισμένους από τους γείτονες του, ή κάθε κόμβος να επιλέγει κόμβους στους οποίους θα μεταδώσει πακέτα με βάση τη γεωμετρική θέση τους. Μια άλλη μέθοδος δρομολόγησης είναι η κατασκευή ενός εικονικού δικτύου υποδομής, οι κόμβοι του οποίου είναι κόμβοι του ασύρματου δικτύου και οι ακμές του οποίου χρησιμοποιούνται για τη μεταφορά των πακέτων. Η κατασκευή του δικτύου υποδομής πρέπει να πραγματοποιηθεί με κατανεμημένο τρόπο και το μέγεθος και η δομή του πρέπει να είναι τέτοια ώστε η δρομολόγηση να απαιτεί όσο το δυνατόν λιγότερη κατανάλωση ενέργειας από τους κόμβους. Στα πλαίσια της διπλωματικής αυτής εργασίας: 1) Αναπτύχθηκαν δύο νέες μέθοδοι δρομολόγησης σε ασύρματα δίκτυα αυθαίρετης τοπολογίας μέσω κατασκευής εικονικών δικτύων υποδομής. Οι μέθοδοι αυτοί βασίζονται σε αντίστοιχους αλγόριθμους κατασκευής επικαλυπτόντων υπογραφημάτων και έχουν την ιδιότητα ότι τα εικονικά δίκτυα που παράγονται έχουν σχετικά μικρό αριθμό ακμών, ενώ παράλληλα η απόσταση μεταξύ δύο κόμβων στο εικονικό δίκτυο είναι το πολύ t φορές μεγαλύτερη από την ελάχιστη απόσταση τους στο αρχικό δίκτυο (όπου t είναι παράμετρος που εξαρτάται από τον αλγόριθμο). 2) Υλοποιήθηκαν οι δύο αυτές νέες μέθοδοι δρομολόγησης σε κατάλληλο περιβάλλον εξομοίωσης και έγινε εκτενής πειραματική αξιολόγηση τους. / The characteristic feature of wireless ad hoc networks is that there is no fixed infastructure (in constrast with cellular networks). One considerabe example of such networks is sensor networks, which can be used to monitor a natural phenomenon, or to construct a temporary communication network in areas where a disaster has occurred, etc, therefore wireless ad hoc networks is a research area of great interest. In wireless ad hoc networks when a node needs to send a message to a node which relies outside of its transmission range, then the transmission takes place through the nodes which rely on a path which connects these two nodes. The wireless nodes, however, have limited energy, therefore routing method is crusial for the operation of the network. Routing protocols are based on several methods, such as: each node is allowed to communicate with only a selected subset of its neighbors, or each node chooses to transmits a message to one of its neighbors based on its geometrical position. Another routing method is to construct a virtual backbone network. The virtual network has the same nodes as the ad hoc network, but only its links are used for the routing of messages. The construction of the virtual network must be executed in a distributed way and its size and structure must be suitable to allow the nodes to consume as less energy as possible in order to support the routing protocol. In this work 1) we have developed two new routing methods for wireless ad hoc networks by constructing virtual networks. These two methods are based on corresponding algorithms for maintaining spanners. The virtual networks constructed have relatively small number of links, while having the ability that for every pair of nodes their distance in the virtual network is at most t times their distance in the ad hoc network (parameter t depends on the algorithm). 2) we have implemented these two algorithms in a simulation environment, and we have conducted an extensive study on them.

Είναι γεγονός ότι, τα τελευταία χρόνια, η χρήση των κινητών δικτύων τρίτης γενιάς έχει αρχίσει να επεκτείνεται. Οι υπηρεσίες που απευθύνονται σε ομάδες χρηστών θα αποτελέσουν μία νέα κατηγορία προηγμένων υπηρεσιών προς στους κινητούς χρήστες. Στα συμβατικά ενσύρματα δίκτυα, η χρήση multicast μηχανισμών είναι αυτή που συνήθως ενδείκνυται για αυτή την κατηγορία υπηρεσιών. Ένας multicast μηχανισμός μεταδίδει τα δεδομένα μόνο μία φορά πάνω από κάθε σύνδεσμο που αποτελεί τμήμα των μονοπατιών προς τους προορισμούς. Είναι προφανής η αύξηση της απόδοσης που προσφέρει το multicasting καθώς ελαχιστοποιεί τη χρήση των πόρων του δικτύου. Επομένως, η εφαρμογή του multicasting σε ένα κινητό δίκτυο έχει αρκετά διαφορετικά χαρακτηριστικά σε σχέση με την εφαρμογή του στο Internet. Κατά συνέπεια, δημιουργείται η ανάγκη για νέους μηχανισμούς οι οποίοι θα καλύψουν τις ιδιαιτερότητες των κινητών δικτύων. Στην παρούσα διπλωματική εργασία προτείνεται ένας μηχανισμός που εκτελεί multicast μετάδοση δεδομένων στο σύστημα UMTS. Ο συγκεκριμένος μηχανισμός εκμεταλλεύεται τη δενδρική τοπολογία των κινητών δικτύων και εισάγει τη χρήση των Routing Lists (RLs) στους κόμβους του UMTS. Η χρήση και η ενημέρωση των RLs γίνεται από τον προτεινόμενο μηχανισμό με τρόπο που παρουσιάζεται αναλυτικά. Επίσης, εξετάζονται διεξοδικά τα πιθανά σενάρια τα οποία περιλαμβάνουν όλες τις περιπτώσεις κινητικότητας των χρηστών. Ειδικότερα, εξετάζονται οι διάφοροι τύποι handover καθώς και η διαδικασία SRNS relocation. Τέλος, ο συγκεκριμένος μηχανισμός εξομοιώνεται στον network simulator ns-2. Μέσω της εξομοίωσης διερευνάται η ορθότητα του μηχανισμού καθώς και η αποδοτικότητά του. / It is a matter of fact that the third generation cellular networks are being deployed all over the world. A set of new services which will be provided by these networks, are those who address to user groups. Wireline networks use multicast mechanisms for the provision of similar services. A multicast mechanism transmits the same data once over each link of the path from the source to the destinations. Obviously, multicasting leads to the efficient use of the network resources. Nevertheless, the adoption of this kind of mechanisms by a mobile network is quite complicated and new schemes are required. In this master thesis, I present a mechanism for the multicast transmission of data in UMTS. This mechanism takes advantage of the tree topology of the examined networks and introduces the use of Routing Lists (RLs) in the nodes of UMTS. The use and the update of RLs are performed by the proposed mechanism and each step of these procedures is described in detail. Furthermore, I analyze the handling of special cases such as user mobility scenarios. Especially, the various handover types are examined along with the SRNS relocation procedure. Finally, I implement this approach in the ns-2 simulator. Through this simulation, I investigate the correctness and the efficiency of the proposed mechanism.

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

Η οπτική μεταγωγή καταιγισμών (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.

Στην εργασία αυτή ασχολούμαστε με το πρόβλημα της δρομολόγησης ενός συνόλου αιτήσεων επικοινωνίας σε WDM (Wavelength Division Multiplexing) πλήρως οπτικά δίκτυα από την άποψη της θεωρίας παιγνίων. Αν θεωρήσουμε κάθε αίτηση δρομολόγησης (ζεύγος κόμβων αφετηρία-προορισμός) ως παίκτη, τότε μία στρατηγική περιλαμβάνει ένα μονοπάτι από τον κόμβο-αφετηρία στον κόμβο-προορισμό και μία συχνότητα (χρώμα). Λαμβάνοντας υπόψη τον περιορισμό ότι δύο παίκτες δεν μπορούν να χρησιμοποιήσουν την ίδια συχνότητα στην ίδια ακμή, θεωρούμε ότι το κόστος δύο αλληλοσυγκρουόμενων στρατηγικών είναι απαγορευτικά μεγάλο. Στο παραπάνω πλαίσιο, μελετάμε διάφορες φυσικές συναρτήσεις κόστους επικεντρώνοντας στην ύπαρξη αμιγών σημείων ισορροπίας Nash και στην υπολογιστική πολυπλοκότητα αναγνώρισης και υπολογισμού τους. / We consider the problem of routing a number of communication requests in WDM (wavelength division multiplexing) all-optical networks from the standpoint of game theory. If we view each routing request (pair of source-target nodes) as a player, then a strategy consists of a path from the source to the target and a frequency (color). To reflect the restriction that two requests must not use the same frequency on the same edge, conflicting strategies are assigned a prohibitively high cost. Under this formulation, we consider several natural cost functions focusing on the existence of Nash equilibria and on the complexity of recognizing and computing them.

During an emergency evacuation, most people will use their vehicles to evacuate. However, there is a group of people who do not have access to reliable transportation or for some reason cannot drive, even if they have their own automobiles - the carless. There are different groups of carless (disabled, medically homebound, poor or immigrant populations, etc.) who require different forms of transportation assistance during an emergency evacuation. In this study we focus on those carless who are physically intact and able to walk to a set of designated locations for transportation during an emergency, and we propose using public transit and school buses to evacuate this carless group. A model has been developed to accommodate the use of public transit and school buses to efficiently and effectively evacuate the carless. The model has two parts. Part 1 is a location problem which aims at congregating the carless at some specific locations called evacuation sites inside the affected area. To achieve this goal, the affected area is partitioned into zones and this congregating of the carless has been formulated as a Single Source Capacitated Facility Location Problem. Changes in the demand of the carless in zones over different periods of a day and over different days of the week have been considered and included in the model. A walking time constraint is explicitly considered in the model. A heuristic developed by Klincewicz and Luss (1986) has been used to solve this location model.Part 2 is a routing problem which aims at obtaining itineraries of buses to pick up the carless at evacuation sites and transport them to safe locations outside the affected area, such that the total number of carless evacuated with the given time limit is maximized. A Tabu search heuristic has been developed for solving the routing problem. Computational results show that the Tabu search heuristic efficiently and effectively solves the routing problem; in particular, the initial heuristic produces a high quality initial solution in very short time. This study has also made slight contribution to the development of the Tabu search technique.

School bus routing and scheduling are among the major problems because school bus transportation needs to be safe, reliable and efficient. Hence, the research question for this thesis is to answer how to transport students in the safest, most economical and convenient manner. The objective of this thesis is to create a GIS based school transport management system which helps in bus-stop allocation, design fastest and safest bus routes with AVL facility. This thesis also aims to investigate how a school transportation management system may improve the transportation security. The result from this study has helped to develop a school bus routing and scheduling prototype model for Sujatha High School, Hyderabad. This prototype model will help the school transportation management to design shortest and fastest school bus routes and they can also allocate bus stops, which will help them in selecting the pick-up stops for the students and staff, according to their concentration in the areas. This thesis has also, through literature study, investigated how a school transport management system can improve the transportation security. For the time being, there is a general belief that ICT contributes to improving the security, although a quantification of such improvements are lacking. The user interface application has been developed by using VBA and ArcGIS 9.1 Network Analyst provided by Environmental Science Research Institute and it has been evaluated by GIS users.

The efficient designs of Wireless Sensor Network protocols and intelligent Machine Learning algorithms, together have led to the advancements of various systems and applications for Smart Environments. By definition, Smart Environments are the typical physical worlds used in human daily life, those are seamlessly embedded with smart tiny devices equipped with sensors, actuators and computational elements. Since human user is a key component in Smart Environments, human motion activity patterns have key importance in building sensor network systems and applications for Smart Environments. Motivated by this, in this thesis my work is focused on human motion activity-aware sensor networks for Smart Environments. The main contributions of this thesis are in two important aspects: (i) Designing event activity context-aware sensor networks for efficient performance optimization as well as resource usage; and (ii) Using binary motion sensing sensor networks' collective data for device-free real-time tracking of multiple users. Firstly, I describe the design of our proposed event activity context-aware sensor network protocols and system design for Smart Environments. The main motivation behind this work is as follows. A sensor network, unlike a traditional communication network, provides high degree of visibility into the environmental physical processes. Therefore its operation is driven by the activities in the environment. In long-term operations, these activities usually show certain patterns which can be learned and effectively utilized to optimize network design. In this thesis I have designed several novel protocols: (i) ActSee for activity-aware radio duty-cycling, (ii) EAR for activity-aware and energy balanced routing, and (iii) ActiSen complete working system with protocol suites for activity-aware sensing/ duty-cycling/ routing. Secondly, I have proposed and designed FindingHuMo (Finding Human Motion), a Machine Learning based real-time user tracking algorithm for Smart Environments using Sensor Networks. This work has been motivated by increasing adoption of sensor network enabled Ubiquitous Computing in key Smart Environment applications, like Smart Healthcare. Our proposed FindingHuMo protocol and system can perform device-free tracking of multiple (unknown and variable number of) users in the hallway environments, just from non-invasive and anonymous binary motion sensor data.

Mobile Delay Tolerant Networks (MDTNs) are wireless mobile networks in which a complete routing path between two nodes that wish to communicate cannot be guaranteed. A number of networking scenarios have been categorized as MDTNs, such as vehicular ad hoc networks, pocket switched networks, etc. The network asynchrony, coupled with the limited resources of mobile devices make message dissemination (also called routing) one of the fundamental challenges in MDTNs. In the literature, a large body of work has been done to deal with routing in MDTNs. However, most of the existing routing protocols are based on at least one of the following three assumptions: (1) all messages can be routed by relying on a single mobility property; (2) all messages can be routed using a single message allocation strategy; (3) users are willing to disclose their mobility information and relationships to others in order to improve the quality of the routing. We argue that the above three assumptions are not realistic because: (1) users can exhibit various social behaviors and consequently various mobility properties (e.g., they can have regular movements during week-days and exhibit non-predictable movements during week-ends); (2) some messages might need more or less copies to be delivered according to the localization of the source and the destination and to the urgency of the message; and (3) users mobility data can disclose sensitive information about the users. In this thesis, we relieve MDTN routing from the above three restrictive assumptions. Firstly, we propose an adaptive routing protocol for mobile delay tolerant networks. The proposed protocol can dynamically learn the social properties of nodes based on their mobility patterns, and exploit the most appropriate routing strategy each time an intermediate node is encountered. Simulations performed on real mobility traces show that our protocol achieves a better delivery ratio than existing state-of-the-art routing protocols that rely on a single mobility property. Secondly, we present a delay and cost balancing protocol for efficient routing in mobile delay tolerant networks. The presented protocol reasons on the remaining time-to-live of a message to dynamically allocate the minimum number of copies that are necessary to achieve a given delivery probability. Evaluation results show that the protocol can achieve a good balance between message delivery delay and delivery cost, compared with most of the existing routing protocols in the literature. Lastly, we propose an efficient privacy preserving prediction-based routing protocol for mobile delay tolerant networks. This protocol preserves the mobility patterns of a node from being disclosed by exploiting the mobility pattern of communities that node belongs to. Evaluation results demonstrate that this protocol can obtain comparable routing performance to prediction-based protocols while preserving the mobility pattern of nodes.

Reducing the energy consumption of available resources is still a problem to be solved in Wireless Sensor Networks (WSNs). Many types of existing routing protocols are developed to save power consumption. In these protocols, cluster-based routing protocols are found to be more energy efficient. A cluster head is selected to aggregate the data received from root nodes and forwards these data to the base station in cluster-based routing. The selection of cluster heads should be efficient to save energy. In our proposed protocol, we use static clustering for the efficient selection of cluster heads. The proposed routing protocol works efficiently in large as well as small areas. For an optimal number of cluster head selection we divide a large sensor field into rectangular clusters. Then these rectangular clusters are further grouped into zones for efficient communication between cluster heads and a base station. We perform MATLAB simulations to observe the network stability, throughput, energy consumption, network lifetime and the number of cluster heads. Our proposed routing protocol outperforms in large areas in comparison with the LEACH, MH-LEACH, and SEP routing protocols.