We develop two algorithms for important problems in mobile ad hoc networks (MANETs). A MANET is a collection of mobile processors (“nodes”) which communicate via message passing over wireless links. Each node can communicate directly with other nodes within a specified transmission radius; other communication is accomplished via message relay. Communication links may go up and down in a MANET (as nodes move toward or away from each other); thus, the MANET can consist of multiple connected components, and connected components can split and merge over time. We first present a deterministic leader election algorithm for asynchronous MANETs along with a correctness proof for it. Our work involves substantial modifications of an existing algorithm and its proof, and we adapt the existing algorithm to the asynchronous environment. Our algorithm’s running time and message complexity compare favorably with existing algorithms for leader election in MANETs. Second, many algorithms for MANETs require or can benefit from knowledge about the size of the network in terms of the number of processors. As such, we present an algorithm to approximately determine the size of a MANET. While the algorithm’s approximations of network size are only rough ones, the algorithm has the important qualities of requiring little communication overhead and being tolerant of link failures.

This thesis presents an intelligent early packet discard (I-EPD) for real-time video streaming over a multi-hop ad hoc network. In a multi-hop ad hoc network, the quality of transferring real-time video streams could be seriously degraded, since every intermediate node (IN) functionally like forwarding device does not possess large buffer and sufficient bandwidth. Even worse, a selected forwarding node could leave or power off unexpectedly which breaks the route to destination. Thus, a video packet temporarily buffered in intermediate nodes may exceed its time constraint when either a congested or failed link occurs; a stale video packet is useless even if it can reach destination after network traffic becomes smooth or failed route is reconfigured. In the proposed I-EPD, an IN can intelligently determine whether a buffered video packet should be discarded based on an estimated time constraint which is calculated from the RTP timestamps and the round trip time (RTT) measured by RTCP. For the purpose of validation, we implement the I-EPD scheme on a Linux-based embedded system. We compare the quality of video streams under different bit rates and different route repair time. In addition, we use PSNR to validate the quality of pictures from the aspect of application layer. The experimental results demonstrate that with I-EPD buffer utilization on IN can be more effectively used and unnecessary bandwidth wastage can be avoided.

This paper studies the integrated mobile ad-hoc networks (MANETs) and Internet network which the Mobile IP and AODV routing protocols are integrated to offer MANET nodes to set up multi-hop routes to the Internet. Gateways act as bridges for forwarding data packets between integrated MANETs and the Internet. Mobile nodes in MANETs must discover available gateways to gain access to the Internet. This study presents an adaptive gateway discovery scheme that balances efficiency and overhead by limiting the flooding scope of gateway advertisement messages. The proposed scheme dynamically adjusts the ADV_TTL according to the average delay time of network. The simulation results showed that the proposed scheme obtains the shortest average delay time while keeping the network a relatively lower overhead.

Mobile ad hoc networks create communication links without the aid of any infrastructure, forwarding packets among mobile nodes. The MANET research community has identified several fundamental challenges, among which the most prominent is discovering an optimal route between two nodes. Existing work has proposed a plethora of routing protocols. Since each protocol implements its own philosophy and algorithm to target a specific purpose, routing protocols in MANETs show very different characteristics. Selecting a particular protocol for an application or deployment environment involves evaluating many complex inter-dependent tradeoffs and can be an overwhelming task for an application designer. However, this decision can have a significant impact on the success of a system in terms of performance, cost, and responsiveness. Emerging distributed applications deployed in MANETs inherently experience highly dynamic situations, which necessitate real-time routing protocol selection in response to varying scenarios. Most of the relevant research in this area relies on simulation studies or empirical analysis to select a routing protocol, requiring an infeasible amount of time and resources for the approaches to be used in real-time decision making. In my dissertation work, I designed the Chameleon framework to facilitate real-time routing protocol decisions based on given application and environmental characteristics. My approach develops analytical models for important network layer performance measures capturing various inter-dependent factors that affect routing protocol behavior. I provide an analytical framework that expresses protocol performance metrics in terms of environment-, protocol-, and application-dependent parameters. This effort has resulted in detailed models for two important metrics: end-to-end delay and throughput. I specify detailed models for the parameters embedded in the models with respect to the ability of network deployers, protocol designers, and application developers to reasonably provide the information. Finally, in a systematic manner, I outline the Chameleon software framework to integrate the analytical models with parameters specified by these three groups of stakeholders. / text

Τα ασύρματα κινητά Ad Hoc δίκτυα γίνονται ολοένα και πιο δημοφιλή λόγω της αυξανόμενης χρήσης κινητών συσκευών. Οι κόμβοι αυτών των δικτύων μπορούν να κινούνται ελεύθερα στον χώρο, έχοντας ταυτόχρονα πολλαπλούς ρόλους αφού μπορούν να λάβουν και να στείλουν πληροφορία προερχόμενη από οποιοδήποτε πόρο του δικτύου. Αυτό σημαίνει ότι ένας κόμβος μπορεί να έχει το ρόλο του αποστολέα, του παραλήπτη και του αναμεταδότη. Η ικανότητα αυτών των δικτύων να αυτοπροσαρμόζονται και να δημιουργούν ένα συνεκτικό δίκτυο μέσω ασύρματων συνδέσεων, τα κάνει κατάλληλα για μια σειρά από εφαρμογές στις οποίες τα άλλα δίκτυα αποτυγχάνουν. Τέτοιες εφαρμογές περιλαμβάνουν τοπολογίες που στήνονται σε συνθήκες έκτακτης ανάγκης, δίκτυα αισθητήρων και γενικά τοπολογίες στις οποίες δεν υπάρχει προκαθορισμένη υποδομή ή η υποδομή που υπήρχε έχει καταστραφεί. Τα ασύρματα κινητά δίκτυα παρέχουν την ελευθερία στους κόμβους να κινηθούν ακόμα και μακρυά από σταθμούς βάσης ή και να αποσυνδεθούν προσωρινά από το υπόλοιπο δίκτυο, με αποτέλεσμα να καθιστούν δύσκολο το πρόβλημα της δρομολόγησης. Τα πρωτόκολλα δρομολόγησης που έχουν αναπτυχθεί για τέτοιου τύπου δίκτυα επηρεάζουν άμεσα τα χαρακτηριστικά της μετάδοσης δεδομένων και την απόδοση των σχετικών εφαρμογών. Κάθε πρωτόκολλο έχει τη δική του στρατηγική δρομολόγησης έτσι ώστε να καταφέρει να συνδέσει δυο κινητούς κόμβους του δικτύου. Η απόδοση μεταβάλλεται ανάλογα με την κατάσταση του δικτύου και τις επικρατούσες συνθήκες όπως η πυκνότητα των κόμβων σε μια συγκεκριμένη περιοχή, η ταχύτητα και η κατεύθυνση τους. Είναι προφανές ότι η επιλογή του κατάλληλου πρωτοκόλλου δρομολόγησης ανάλογα με τα χαρακτηριστικά και τις παραμέτρους του δικτύου παίζει πολύ σημαντικό ρόλο. Η ενσωμάτωση των κινητών συσκευών σε κινούμενα οχήματα έχει οδηγήσει σε έναν νέο τύπο δικτύων, τα ονομαζόμενα Ad Hoc δίκτυα οχημάτων ή Vehicular Ad hoc Networks (VANETs). Αυτά τα δίκτυα απαιτούν εξειδικευμένα πρωτόκολλα δρομολόγησης εξαιτίας της φύσης των κινητών Ad Hoc δικτύων. Η απόδοση αυτών των πρωτοκόλλων έχει αξιολογηθεί για την περίπτωση της γενικευμένης κίνησης αλλά όχι υπό το πρίσμα της μετάδοσης πολυμέσων και ειδικότερα της μετάδοσης βίντεο. Αρχικός στόχος αυτής της εργασίας είναι η πραγματοποίηση ενός συνόλου από εξομοιώσεις με στόχο την αξιολόγηση της απόδοσης των τριών από τα πιο δημοφιλή πρωτόκολλα δρομολόγησης για τα κινητά Ad Hoc δίκτυα MANETs και VANETs: AODV, DSR, και OLSR. Ο σκοπός της αξιολόγησης είναι η μελέτη της συμπεριφοράς των πρωτοκόλλων όταν μεταβάλλεται το πλήθος των ταυτόχρονων μεταδόσεων βίντεο. Οι μετρικές που προτείνονται είναι • το ποσοστό απώλειας πακέτων • η καθυστέρηση από άκρο σε άκρο • η διακύμανση της καθυστέρησης (jitter) • η επιβάρυνση του δικτύου με πακέτα δρομολόγησης Η μετάδοση πολυμέσων μέσα από τα ασύρματα κινητά Ad Hoc δίκτυα δεν είναι πάντοτε αποδοτική εξαιτίας των υψηλών απαιτήσεων που υπάρχουν, όπως το υψηλό εύρος ζώνης και οι χαμηλοί χρόνοι καθυστέρησης. Δηλαδή, αυτά τα δίκτυα δεν δείχνουν ικανά να υποστηρίξουν μεταδόσεις πολυμέσων υψηλής ποιότητας και ειδικότερα μεταδόσεις βίντεο. Στα πλαίσια της εργασίας αναπτύσσεται και παρουσιάζεται ένας διαστρωματικός μηχανισμός για αποδοτική μετάδοση βίντεο πάνω σε ασύρματα Ad Hoc δίκτυα οχημάτων (VANETs). Ο μηχανισμός αυτός αποτελείται από έναν αλγόριθμο χρονοπρογραμματισμού και ανάθεσης προτεραιότητας στο επίπεδο δικτύου. Ακόμα προτείνεται και αξιολογείται η χρήση του προτύπου IEEE 802.11e στο επίπεδο ζεύξης δεδομένων. Ο αλγόριθμος χρονοπρογραμματισμού και ανάθεσης προτεραιότητας στοχεύει στο να αξιοποιεί την πληροφορία που αφορά στον τύπο των πλαισίων των MPEG-4 βίντεο, με στόχο να παρέχει διαφορετικές προτεραιότητες ανάλογα με τη σημαντικότητα του κάθε πλαισίου. Στο επίπεδο ζεύξης δεδομένων το πρωτόκολλο IEEE 802.11e προτείνεται να αναθέτει τη μέγιστη προτεραιότητα στα πακέτα βίντεο με στόχο την καλύτερη εξυπηρέτηση των εφαρμογών μετάδοσης πολυμέσων. Αυτή η επιλογή γίνεται για τη μείωση της καθυστέρησης και της απώλειας πακέτων εξαιτίας της κίνησης ανταγωνιστικών δεδομένων. Ο σχεδιασμός που παρουσιάζεται είναι εύκολα ενσωματώσιμος σε κάθε ασύρματο Ad Hoc δίκτυο, σαν επέκταση του δημοφιλούς πρωτοκόλλου δρομολόγησης AODV. Οι εφαρμογές μετάδοσης πολυμέσων συνήθως χρησιμοποιούν το UDP ως πρωτόκολλο μεταφοράς. Με αυτή την επιλογή αποφεύγονται οι καθυστερήσεις που προκαλούνται από αναμεταδόσεις πακέτων και από τους μηχανισμούς ελέγχου συμφόρησης του TCP, αλλά δημιουργούνται δυο σημαντικά προβλήματα. Το πρώτο πρόβλημα έχει να κάνει με τους πιθανούς περιορισμούς εύρους ζώνης με αποτέλεσμα τα πακέτα πολυμέσων να μην ελέγχονται από μηχανισμούς ελέγχου ροής και συμφόρησης, οδηγώντας σε αυξημένη απώλεια πακέτων. Το δεύτερο πρόβλημα είναι σχετικό με τη φιλικότητα προς το TCP πρωτόκολλο. Κάτω υπό ορισμένες συνθήκες, η μετάδοση πακέτων χωρίς κάποιον ελεγκτικό μηχανισμό μπορεί να οδηγήσει σε μια κατάσταση στην οποία οι εφαρμογές του δικτύου που χρησιμοποιούν το TCP να μην εξυπηρετούνται. Στα πλαίσια της εργασίας προτείνονται διαστρωματικές τεχνικές και μηχανισμοί που στοχεύουν στη βελτίωση της μετάδοσης βίντεο, μέσω του πρωτοκόλλου TFRC το οποίο είναι φιλικό ως προς την συνυπάρχουσα TCP κίνηση. Ο σχεδιασμός περιλαμβάνει μηχανισμούς που δίνουν προτεραιότητα στα πακέτα βίντεο, ενώ παράλληλα αξιοποιούνται πληροφορίες από τα κατώτερα επίπεδα του μοντέλου OSI. Συγκεκριμένα, αξιοποιούνται πληροφορίες που συλλέγονται από το στρώμα ζεύξης δεδομένων οι οποίες αφορούν την ποιότητα του λαμβανόμενου σήματος. Ο προτεινόμενος μηχανισμός χρησιμοποιεί τις μετρήσεις της ενέργειας σήματος ως προς τον θόρυβο του καναλιού (SNR) σε όλο το μήκος ενός μονοπατιού, προκειμένου να βελτιώσει την αποδοτικότητα του πρωτοκόλλου δρομολόγησης AODV και συγκεκριμένα τη διαδικασία ανακατασκευής μονοπατιών. Η αξιολόγηση που προτείνεται είναι με εξομοιώσεις στον εξομοιωτή δικτύων ns-2. Συμπερασματικά, στόχος αυτής της διπλωματικής εργασίας είναι η μελέτη μετάδοσης πολυμεσικών δεδομένων μέσω διαφόρων πρωτοκόλλων δρομολόγησης σε συνθήκες αστικού περιβάλλοντος. Επίσης, στόχος είναι η μελέτη και η ανάπτυξη διαστρωματικών μηχανισμών προσαρμοστικής μετάδοσης και η πιθανή βελτίωση ή παραμετροποίηση υπαρχόντων μηχανισμών για την αποδοτικότερη μετάδοση πάνω από τα ασύρματα κινητά Ad Hoc δίκτυα. Ο κεντρικός άξονας στην ανάπτυξη αυτών των μηχανισμών στηρίζεται στην παροχή προτεραιότητας στα πακέτα που περιέχουν δεδομένα πολυμέσων, στην ενίσχυση των μηχανισμών ελέγχου ροής και συμφόρησης και στη βελτίωση των πρωτοκόλλων δρομολόγησης αξιοποιώντας στοιχεία του φυσικού δικτύου, με απώτερο στόχο τη βελτίωση της απόδοσης της μετάδοσης πολυμεσικών δεδομένων. / Mobile ad hoc networks (MANETs) are becoming more essential to wireless commu- nications due to growing popularity of mobile devices. The integration of mobile ad hoc devices inside vehicles has led to another type of networks, called Vehicular Ad hoc Networks (VANETs) which are also becoming important. These networks require specialized routing protocols due to their ad hoc nature. The performance of these pro- tocols has been tested for the case of general traffic but not in respect with to multimedia traffic and especially video transmission. In this work we conduct a number of simulations in order to evaluate the performance of three of the most popular routing protocols for MANETs and VANETs, namely AODV, DSR and OLSR, for different number of simultaneous video transmissions. We use the packet delivery ratio, the end-to-end delay, the packet delay variation (jit- ter) and the routing overhead as evaluation metrics. The results indicate that the DSR protocol outperforms AODV and OLSR in terms of end-to-end delay and packet delay variation and seems to be the most efficient routing protocol when multimedia traffic and especially video traffic is considered. Moreover, we present a cross-layer mechanism for efficient video transmission over this type of networks. The proposed mechanism consists of a priority-scheduling algorithm, at the network layer, and the use of the IEEE 802.11e standard at the MAC layer. The priority-scheduling algorithm takes into account the frame type of the MPEG-4 video file in order to provide different priorities to the most important video packets. At the MAC layer, the IEEE 802.11e protocol assigns the highest priority to video applications to reduce delay and packets losses due to other competing traffic. This design is easily implemented in any ad hoc wireless network as an extension on the AODV MANET routing protocol. Simulation results conducted with the network simulator ns-2 show the advantages of the proposed design. Finally, we propose a cross-layer design that aims to improve the performance of video transmission using TCP Friendly Rate Control (TFRC). Our design provides priority to video packets and exploits information from the MAC layer in order to improve TFRC’s performance. The proposed cross-layer mechanism utilizes Signal to Noise Ratio (SNR) measurements along the routing path, in order to make the route recon- struction procedure more efficient. Simulation results show that both the use of traffic categorization and the SNR utilization lead to important improvements of video trans- mission over the mobile Ad hoc network. More specifically, simulations indicate in- creased average Peak Signal to Noise Ratio (PSNR) for the received video, increased throughput and packet delivery ration, as well as reduced average end-to-end delay.

The thesis investigates the process of modeling and simulation of the mobile ad-hoc networks. It provides a overview of the actual state of art together with a literature survey. Basic ideas of both security issues in mobile ad-hoc networks as well as intrusion detection systems are presented. Additionally some new ideas for improvements - like the AGM mobility model - are proposed, and tested during the simulation proces. As an addition a set of applications designer for automating the simulation processes were created.

With the proliferation of mobile devices and wireless connectivity technologies, mobile social communities offer novel opportunities for targeted marketing by service or product providers. Unfortunately, marketers are still unable to realize the full potential of these markets due to their inability to effectively target right audiences. This thesis presents a novel middleware for identifying spontaneous social communities (SSCs) of mobile users in ad hoc networks in order to facilitate marketers' advertisements. The contributions of the presented work are two fold; the first is a novel model for SSCs that captures their unique dynamic nature, in terms of community structure and interest in different \textit{hot-topics} over time. These time-varying interests are represented through an inferred \textit{community profile prototype} that reflects dominant characteristics of community members. This prototype is then employed to facilitate the identification of new potential members. The selected community prototypes are also used by marketers to identify the right communities for their services or products promotions. The second contribution of this paper is novel distributed techniques for efficient calculation of the community prototypes and identification of potential community links. In contrast to traditional models of detecting fixed and mobile social networks that rely on pre-existing friendships among its members to predict new ones, the proposed model focuses on measuring the degree of similarity between the new user's profile and the profiles of members of each community in order to predict new users' relationships in the community. The adopted model of SSCs can foster many existing and new socially-aware applications such as recommender systems for social events and tools for collaborative work. It is also an ideal target for business-oriented applications such as short-message-service (SMS) advertisement messages, podcasting news feeds in addition to location/context-aware services. The performance of the proposed work was evaluated using the NetLogo platform where obtained experimental results demonstrate the achieved high degree of stability in the resulting communities in addition to the effectiveness of the proposed middleware in terms of the reduction in the number of routing messages required for advertisements.

Over a period of time, it has been studied that a mobile “edge-cloud” formed by hand-held devices could be a productive resource entity for providing a service in the mobile cloud landscape. The ease of access to a pool of devices is much more arbitrary and based purely on the needs of the user. This pool can act as a provider of an infrastructure for various services that can be processed with volunteer node participation, where the node in the vicinity is itself a service provider. This representation of cloud formation to engender a constellation of devices in turn providing a service is the basis for the concept of Mobile Ad-hoc Cloud Computing. In this thesis, an architecture is designed for providing an Infrastructure as a service in Mobile Ad-hoc Cloud Computing. The performance evaluation reveals the gain in execution time while offloading to the mobile ad-hoc cloud. Further, this novel architecture enables discovering a dedicated pool of volunteer devices for computation. An optimized task scheduling algorithm is proposed that provides a coordinated resource allocation. However, failure to maintain the service between heterogeneous networks shows the inability of the present day networks to adapt to frequent changes in a network. Thus, owing to the heavy dependence on the centralized mobile network, the service related issues in a mobile ad-hoc cloud needs to be addressed. As a result, using the principles of Software Defined Networking (SDN), a disruption tolerant Mobile Ad-hoc Cloud framework is proposed. To evaluate this framework a comprehensive case study is provided in this work that shows a round trip time improvement using an SDN controller.

With the proliferation of fairly powerful mobile devices and ubiquitous wireless technology, traditional mobile ad hoc networks (MANETs) now migrate into a new era of service-oriented MANETs wherein a node can provide and receive service from other nodes it encounters and interacts with. This dissertation research concerns trust management and its applications for service-oriented MANETs to answer the challenges of MANET environments, including no centralized authority, dynamically changing topology, limited bandwidth and battery power, limited observations, unreliable communication, and the presence of malicious nodes who act to break the system functionality as well as selfish nodes who act to maximize their own gain. We propose a context-aware trust management model called CATrust for service-oriented ad hoc networks. The novelty of our design lies in the use of logit regression to dynamically estimate trustworthiness of a service provider based on its service behavior patterns in a context environment, treating channel conditions, node status, service payoff, and social disposition as 'context' information. We develop a recommendation filtering mechanism to effectively screen out false recommendations even in extremely hostile environments in which the majority recommenders are malicious. We demonstrate desirable convergence, accuracy, and resiliency properties of CATrust. We also demonstrate that CATrust outperforms contemporary peer-to-peer and Internet of Things trust models in terms of service trust prediction accuracy against collusion recommendation attacks. We validate the design of trust-based service management based on CATrust with a node-to-service composition and binding MANET application and a node-to-task assignment MANET application with multi-objective optimization (MOO) requirements. For either application, we propose a trust-based algorithm to effectively filter out malicious nodes exhibiting various attack behaviors by penalizing them with trust loss, which ultimately leads to high user satisfaction. Our trust-based algorithm is efficient with polynomial runtime complexity while achieving a close-to-optimal solution. We demonstrate that our trust-based algorithm built on CATrust outperforms a non-trust-based counterpart using blacklisting techniques and trust-based counterparts built on contemporary peer-to-peer trust protocols. We also develop a dynamic table-lookup method to apply the best trust model parameter settings upon detection of rapid MANET environment changes to maximize MOO performance. / Ph. D.

Policy based network management is a promising approach for provisioning and management of quality of service in mobile ad hoc networks. In this thesis, we focus on performance evaluation of this approach in context of the amount of service received by certain nodes called policy execution points (PEPs) or policy clients from certain specialized nodes called the policy decision points (PDPs) or policy servers. We develop analytical models for the study of the system behavior under two scenarios; a simple Markovian scenario where we assume that the random variables associated with system processes follow an exponential distribution and a more complex non-Markovian scenario where we model the system processes according to general distribution functions as observed through simulation. We illustrate that the simplified Markovian model provides a reasonable indication of the trend of the service availability seen by policy clients and highlight the need for an exact analysis of the system without relying on Poisson assumptions for system processes. In the case of the more exact non-Markovian analysis, we show that our model gives a close approximation to the values obtained via empirical methods. Stochastic Petri Nets are used as performance evaluation tools in development and analysis of these system models. / Master of Science