The Vehicular Ad Hoc Network (VANET) is a promising approach for future Intelligent Transportation Systems (ITS) implementation. The data transmission is wireless primarily in the VANET system. The secure data transmission in VANET attracts research attention without any doubt. The Ciphertext-Policy Attribute-Based Encryption (CP-ABE) provides an encrypted access control mechanism for broadcasting messages in VANET. The user’s attributes stand for its current property. However, if we apply vehicle location as the attribute, this attribute has to keep up-to-date with the vehicle’s movement. It is not easy for current CP-ABE algorithms because whenever one attribute changes, the entire private key, which is based on all the attributes, must be changed. In this thesis, we apply fading function to realize the “dynamic attribute” feature in CP-ABE. The dynamic attribute allows the user to update each attribute separately, and fading function gives each attribute a valid period. We introduce the dynamic attribute feature to three different CP-ABE algorithms. Then we design a VANET system that applies the CP-ABE with dynamic attribute feature. We evaluate the processing time of three different CP-ABE algorithms. We apply two different pairing curves for different security requirements. Our results show that the introduction of fading function does not cause significant extra time cost to current CP-ABE algorithms. The fading function causes extra 0.2ms on average for each attribute that participates in encryption and decryption. The sum-up time for encryption and decryption is between 100ms to 200ms when there are ten attributes participating in encryption and decryption. / VANET är ett lovande tillvägagångssätt för framtida genomförande av ITS. Dataöverföringen är i första hand trådlös i VANET-systemet. Den säkra dataöverföringen i VANET är utan tvekan föremål för forskningens uppmärksamhet. CP-ABE ger en krypterad åtkomstkontrollmekanism för sändning av meddelanden i VANET. Användarens attribut står för dennes aktuella egenskaper. Men om vi använder fordonets position som attribut måste detta attribut hålla sig uppdaterat med fordonets rörelse. Det är inte lätt för de nuvarande CP-ABE-algoritmerna eftersom hela den privata nyckeln, som är baserad på alla attribut, måste ändras när ett attribut ändras. I den här avhandlingen tillämpar vi fading-funktionen för att realisera funktionen ”dynamiskt attribut” i CP-ABE. Det dynamiska attributet gör det möjligt för användaren att uppdatera varje attribut separat, och fading-funktionen ger varje attribut en giltighetstid. Vi inför den dynamiska attributfunktionen i tre olika CP-ABE-algoritmer. Därefter utformar vi ett VANET-system som tillämpar CP-ABE med dynamisk attributfunktion. Vi utvärderar tidsåtgången för tre olika CP-ABE-algoritmer. Vi tillämpar två olika parningskurvor för olika säkerhetskrav. Våra resultat visar att införandet av fading-funktionen inte orsakar någon betydande tidsåtgång för de nuvarande CP-ABE-algoritmerna. Fading-funktionen orsakar i genomsnitt 0,2 ms extra för varje attribut som deltar i kryptering och dekryptering. Den sammanlagda tiden för kryptering och dekryptering är mellan 100 och 200 ms när tio attribut deltar i kryptering och dekryptering.

Vehicle-to-infrastructure (V2I) and vehicle-to-vehicle (V2V) communication enable the sharing, in real time, of vehicular locations and speeds with other vehicles, traffic signals, and traffic control centers. This shared information can help traffic to better traverse intersections, road segments, and congested neighborhoods, thereby reducing travel times, increasing driver safety, generating data for traffic planning, and reducing vehicular pollution. This study, which focuses on vehicular pollution, used an analysis of data from NREL, BTS, and the EPA to determine that the widespread use of V2V-based truck platooning—the convoying of trucks in close proximity to one another so as to reduce air drag across the convoy—could eliminate 37.9 million metric tons of CO2 emissions between 2022 and 2026.

Many mobile applications in wireless networks such as military battlefield, emergency response, and mobile commerce are based on the notion of secure group communications. Unlike traditional security protocols which concern security properties only, in this dissertation research we design and analyze a class of QoS-aware protocols for secure group communications in wireless networks with the goal to satisfy not only security requirements in terms of secrecy, confidentiality, authentication, availability and data integrity, but also performance requirements in terms of latency, network traffic, response time, scalability and reconfigurability. We consider two elements in the dissertation research: design and analysis. The dissertation research has three major contributions. First, we develop three "threshold-based" periodic batch rekeying protocols to reduce the network communication cost caused by rekeying operations to deal with outsider attacks. Instead of individual rekeying, i.e., performing a rekeying operation right after each group membership change event, these protocols perform batch rekeying periodically. We demonstrate that an optimal rekey interval exists that would satisfy an imposed security requirement while minimizing the network communication cost. Second, we propose and analyze QoS-aware intrusion detection protocols for secure group communications in mobile ad hoc networks to deal with insider attacks. We consider a class of intrusion detection protocols including host-based and voting-based protocols for detecting and evicting compromised nodes and examine their effect on the mean time to security failure metric versus the response time metric. Our analysis reveals that there exists an optimal intrusion detection interval under which the system lifetime metric can be best traded off for the response time performance metric, or vice versa. Furthermore, the intrusion detection interval can be dynamically adjusted based on the attacker behaviors to maximize the system lifetime while satisfying a system-imposed response time or network traffic requirement. Third, we propose and analyze a scalable and efficient region-based group key management protocol for managing mobile groups in mobile ad hoc networks. We take a region-based approach by which group members are broken into region-based subgroups, and leaders in subgroups securely communicate with each other to agree on a group key in response to membership change and member mobility events. We identify the optimal regional area size that minimizes the network communication cost while satisfying the application security requirements, allowing mobile groups to react to network partition/merge events for dynamic reconfigurability and survivability. We further investigate the effect of integrating QoS-aware intrusion detection with region-based group key management and identify combined optimal settings in terms of the optimal regional size and the optimal intrusion detection interval under which the security and performance properties of the system can be best optimized. We evaluate the merits of our proposed QoS-aware security protocols for mobile group communications through model-based mathematical analyses with extensive simulation validation. We perform thorough comparative analyses against baseline secure group communication protocols which do not consider security versus performance tradeoffs, including those based on individual rekeying, no intrusion detection, and/or no-region designs. The results obtained show that our proposed QoS-aware security protocols outperform these baseline algorithms. â / Ph. D.

La convergencia de las telecomunicaciones, la informática, la tecnología inalámbrica y los sistemas de transporte, va a facilitar que nuestras carreteras y autopistas nos sirvan tanto como plataforma de transporte, como de comunicaciones. Estos cambios van a revolucionar completamente cómo y cuándo vamos a acceder a determinados servicios, comunicarnos, viajar, entretenernos, y navegar, en un futuro muy cercano. Las redes vehiculares ad hoc (vehicular ad hoc networks VANETs) son redes de comunicación inalámbricas que no requieren de ningún tipo de infraestructura, y que permiten la comunicación y conducción cooperativa entre los vehículos en la carretera. Los vehículos actúan como nodos de comunicación y transmisores, formando redes dinámicas junto a otros vehículos cercanos en entornos urbanos y autopistas. Las características especiales de las redes vehiculares favorecen el desarrollo de servicios y aplicaciones atractivas y desafiantes. En esta tesis nos centramos en las aplicaciones relacionadas con la seguridad. Específicamente, desarrollamos y evaluamos un novedoso protocol que mejora la seguridad en las carreteras. Nuestra propuesta combina el uso de información de la localización de los vehículos y las características del mapa del escenario, para mejorar la diseminación de los mensajes de alerta. En las aplicaciones de seguridad para redes vehiculares, nuestra propuesta permite reducir el problema de las tormentas de difusión, mientras que se mantiene una alta efectividad en la diseminación de los mensajes hacia los vehículos cercanos. Debido a que desplegar y evaluar redes VANET supone un gran coste y una tarea dura, la metodología basada en la simulación se muestra como una metodología alternativa a la implementación real. A diferencia de otros trabajos previos, con el fin de evaluar nuestra propuesta en un entorno realista, en nuestras simulaciones tenemos muy en cuenta tanto la movilidad de los vehículos, como la transmisión de radio en entornos urbanos, especialmente cuando los edificios interfieren en la propagación de la señal de radio. Con este propósito, desarrollamos herramientas para la simulación de VANETs más precisas y realistas, mejorando tanto la modelización de la propagación de radio, como la movilidad de los vehículos, obteniendo una solución que permite integrar mapas reales en el entorno de simulación. Finalmente, evaluamos las prestaciones de nuestro protocolo propuesto haciendo uso de nuestra plataforma de simulación mejorada, evidenciando la importancia del uso de un entorno de simulación adecuado para conseguir resultados más realistas y poder obtener conclusiones más significativas. / Martínez Domínguez, FJ. (2010). Improving Vehicular ad hoc Network Protocols to Support Safety Applications in Realistic Scenarios [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/9195

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Benefiting from the constant and significant advancement of wireless communication technologies and networking protocols, Wireless Ad hoc NETwork (WANET) has played a more and more important role in modern communication networks without relying much on existing infrastructures. The past decades have seen numerous applications adopting ad hoc networks for service provisioning. For example, Wireless Sensor Network (WSN) can be widely deployed for environment monitoring and object tracking by utilizing low-cost, low-power and multi-function sensor nodes. To realize such applications, the design and evaluation of communication protocols are of significant importance. Meanwhile, the network performance analysis based on mathematical models is also in great need of development and improvement. This dissertation investigates the above topics from three important and fundamental aspects, including data collection protocol design, protocol modeling and analysis, and physical interference modeling and analysis. The contributions of this dissertation are four-fold. First, this dissertation investigates the synchronization issue in the duty-cycled, pipelined-scheduling data collection of a WSN, based on which a pipelined data collection protocol, called PDC, is proposed. PDC takes into account both the pipelined data collection and the underlying schedule synchronization over duty-cycled radios practically and comprehensively. It integrates all its components in a natural and seamless way to simplify the protocol implementation and to achieve a high energy efficiency and low packet delivery latency. Based on PDC, an Adaptive Data Collection (ADC) protocol is further proposed to achieve dynamic duty-cycling and free addressing, which can improve network heterogeneity, load adaptivity, and energy efficiency. Both PDC and ADC have been implemented in a pioneer open-source operating system for the Internet of Things, and evaluated through a testbed built based on two hardware platforms, as well as through emulations. Second, Linear Sensor Network (LSN) has attracted increasing attention due to the vast requirements on the monitoring and surveillance of a structure or area with a linear topology. Being aware that, for LSN, there is few work on the network modeling and analysis based on a duty-cycled MAC protocol, this dissertation proposes a framework for modeling and analyzing a class of duty-cycled, multi-hop data collection protocols for LSNs. With the model, the dissertation thoroughly investigates the PDC performance in an LSN, considering both saturated and unsaturated scenarios, with and without retransmission. Extensive OPNET simulations have been carried out to validate the accuracy of the model. Third, in the design and modeling of PDC above, the transmission and interference ranges are defined for successful communications between a pair of nodes. It does not consider the cumulative interference from the transmitters which are out of the contention range of a receiver. Since most performance metrics in wireless networks, such as outage probability, link capacity, etc., are nonlinear functions of the distances among communicating, relaying, and interfering nodes, a physical interference model based on distance is definitely needed in quantifying these metrics. Such quantifications eventually involve the Nodal Distance Distribution (NDD) intrinsically depending on network coverage and nodal spatial distribution. By extending a tool in integral geometry and using decomposition and recursion, this dissertation proposes a systematic and algorithmic approach to obtaining the NDD between two nodes which are uniformly distributed at random in an arbitrarily-shaped network. Fourth, with the proposed approach to NDDs, the dissertation presents a physical interference model framework to analyze the cumulative interference and link outage probability for an LSN running the PDC protocol. The framework is further applied to analyze 2D networks, i.e., ad hoc Device-to-Device (D2D) communications underlaying cellular networks, where the cumulative interference and link outage probabilities for both cellular and D2D communications are thoroughly investigated. / Graduate / 0984 / 0544 / tong1987fei@163.com

Pendant les deux dernières décennies, les technologies de réseaux ad-hoc de véhicules (VANETs : Vehicular Ad-Hoc Networks) ont été développées sous l’impulsion du monde de la recherche comme de l’industrie, étant donnés les liens des VANETs avec la sécurité routière, l’internet des objets (IoT/WoT : Internet of Things/Web of Things) pour les systèmes de transport intelligents (ITS : Intelligent Transportation Systems), les villes intelligentes et les villes vertes. Composant essentiel des VANETs, les protocoles de communication inter-véhicules (IVC : Inter-Vehicle Communication) font face à des défis techniques, en particulier à cause de la diversité des applications dans lesquelles ils sont impliqués. Dans cette thèse, après une présentation des VANETs et de l’état de l’art des IVC, nous proposons un protocole de dissémination de données, TrAD, conçu pour diffuser de manière efficiente des messages d’une source vers les véhicules présents dans la zone d’intérêt (ROI : Range of Interest). TrAD se base sur les états du trafic routier et du trafic réseau pour adapter localement la stratégie et les paramètres de transmission des données afin d’optimiser les performances des applications qui l’utilisent. De plus, un algorithme de classification des clusters locaux de véhicules est conçu pour permettre l’usage de TrAD sur autoroute aussi bien qu’en ville. Pour éviter l’encombrement des canaux de communication, un mécanisme illustratif de contrôle de la congestion reposant sur une approche distribuée est utilisé. Trois protocoles IVC de l’état de l’art ont été comparés à TrAD dans des scénarios réalistes de simulation, basés sur différentes villes réelles, différents trajets et densités véhiculaires. Les performances de TrAD surpassent celles des protocoles de référence en termes de taux de délivrance des paquets (PDR : Packet Delivery Ratio), nombre de transmissions et latence. De plus, nous montrons que TrAD est tolérant, dans une certaine mesure, aux erreurs sur les données GPS. Pour s’assurer de la qualité des simulations, nous avons étudié le modèle de déplacement employé dans le simulateur de trafic, puis couplé ce dernier au simulateur de réseau, afin que les deux s’échangent des informations en temps-réel. Grâce à la compréhension acquise lors de l’analyse du modèle de déplacement, nous avons pu développer un simulateur de conduite de tramway pour la T2C (Transports en Commun de l’agglomération Clermontoise). Des tests menés sur le matériel roulant nous ont permis d’élaborer des modèles de déplacement fidèles correspondants aux diverses situations rencontrées par le tramway. L’affichage de la simulation est assuré par un flux vidéo ajusté plutôt que des images de synthèse, ce qui permet de limiter le coût de développement tout en garantissant un certain réalisme dans l’affichage. Ce projet est soutenu par la T2C pour une durée de deux ans. / In the last two decades, Vehicular Ad hoc Network (VANETs) were developed significantly by both academic institute and industries association, since VANETs originate from traffic safety and are also an important application of Internet of Things / Web of Things (IoT/WoT) for Intelligent Transportation System (ITS), Intelligent Vehicles and Smart Cities. As an essential component of VANETs, Inter-Vehicle Communication (IVC) protocols face many critical challenges, in particular, because they relate to various specific applications. In this thesis, after elaborating on related knowledge of VANETs and state-of-the-art of IVC protocols, we propose a data dissemination protocol for vehicular networking, named TrAD, to disseminate efficiently warning messages from a source to vehicles in a range of interest (ROI). TrAD considers the status of road traffic and network traffic to adapt locally the strategy and the parameters of transmissions in order to optimize the global performance of IVC application. Moreover, a local vehicular cluster classification algorithm is designed to support TrAD to be performed in both highway and urban scenarios. In addition, an illustrative congestion control mechanism is used to avoid channel congestion using a distributed approach. Three state-of-the-art IVC protocols have been compared with TrAD by means of realistic simulations. The performance of all those protocols is evaluated quantitatively in various scenarios by taking into account different real road maps, trafic routes and vehicular densities. Compared with the reference protocols, TrAD gains an outstanding overall performance in terms of packet delivery ratio, number of transmissions and delay. Furthermore, TrAD also can tolerate a reasonable degree of GPS drift while achieving efficient data dissemination. In order to ensure the quality of simulations, we deeply investigated the mobility model of road traffic simulator, and then performed the bidirectionally coupled simulation in which the network simulator and the road trafic simulator can exchange information in real-time. Upon understanding of the mobility model, we obtained a chance to develop a low-cost tram simulator for the local public transportation provider, the T2C (Transports en Commun de l’agglomération Clermontoise). We attempt to design accurate mobility models from different scenarios for the specific type of tram used by T2C. Real world trials are carried out to explore the key parameters required by theoretical deduction for our mobility model. Moreover, the display GUI relies on a video stream, rather than 3D graphics, which can reduce the cost while guaranteeing the quality of service. This project was supported for two years by T2C.

Vehicular ad hoc networks (VANETs) are a hot topic in the intelligent transport system (ITS) area. The introduction of wireless communications between vehicles will enable many useful applications to enhance road traffic safety as well to increase efficiency. The standardization of IEEE 802.11p, being an amendment to IEEE 802.11 intended for VANETS, faces many challenges. In Europe a 30 MHz spectrum at 5.9 GHz have been dedicated for ITS and this spectrum has to be used to its full potential. For this reason this thesis compares a 20 MHz wide frequency channel with a 10 MHz wide through measurements using 802.11p hardware. The measurements were conducted on a highway with relative speeds of up to 240 km/h. The results from these initial measurements show that a 20 MHz channel does not perform worse than a 10 MHz channel despite the high relative speeds and large metal signs scattering the signals. What enabled this thesis to do the measurements was Halmstad University‟s participation in the Grand Cooperative Driving Challenge (GCDC) 2011. In GCDC nine teams mostly from Europe competed in having the vehicle that had the best behaviour in a platoon of vehicles using cooperative adaptive cruise control (CACC), the CACC algorithm controlled the vehicles‟ acceleration and breaking autonomously based on in-vehicle sensors and communicated messages between the vehicles in the platoon using 802.11p. This thesis implemented the communication part of Halmstad University‟s vehicle. The challenge was held in Helmond, Holland, May 14-15, 2011. Halmstad University‟s team finished in second place. / CoAct

Στην παρούσα διδακτορική διατριβή, ασχολούµαστε µε ζητήµατα που ανακύπτουν σε ασύρµατα δίκτυα επικοινωνίας, δηλ. δίκτυα που βασίζονται σε τηλεπικοινωνιακή υποδοµή όπως τα κυψελικά δίκτυα κινητής τηλεφωνίας, δίκτυα αυτόνοµων ασύρµατων εκποµπών όπως τα ασύρµατα δίκτυα τύπου ad hoc, κτλ. Τα ασύρµατα δίκτυα επικοινωνίας διαφόρων τύπων έχουν εξελιχθεί σηµαντικά τα τελευταία χρόνια. Ειδικότερα, τα ασύρµατα αδόµητα δίκτυα (ή αλλιώς ασύρµατα δίκτυα τύπου ad hoc) έχουν προσελκύσει το έντονο εν­διαφέρον της επιστηµονικής κοινότητας λόγω των πολλών εφαρµογών που έχουν κυρίως σε περιπτώσεις όπου δεν είναι δυνατή ή επιθυµητή η ολική ή µερική κάλυψη µέσω υποδοµής µε βάση την ενσύρµατη δικτύωση (π.χ., επι­κοινωνία σε δυσπρόσιτες ή αποµακρυσµένες περιοχές, φυσικές καταστροφές, στρατιωτικές εφαρµογές, κλπ.). ΄Οπως και στα παραδοσιακά ενσύρµατα δίκτυα, σηµαντικό πρόβληµα αποτελεί η εγκαθίδρυση σχηµάτων επικοινωνίας όπως διάδοση (broadcasting, multicasting), επικοινωνία όλων µε όλους (gossiping, all-to-all communica­tion), και επικοινωνία σε οµάδες (group communication). Για την επικοινω­νία απαιτείται η κατανάλωση ενέργειας στους κόµβους του δικτύου και, λαµβ.άνοντας υπόψη ότι τα αδόµητα ασύρµατα δίκτυα χρησιµοποιούν κόµβους µε περιορισµένα αποθέµατα ενέργειας, είναι απαραίτητη η ορθολογιστική χρήση αυτής της ενέργειας κατά την επικοινωνία. Αυτό µπορεί να σηµαίνει ότι είναι επιθυµητή είτε η ελαχιστοποίηση της συνολικής ενέργειας που κα­ταναλώνεται στους κόµβους του δικτύου για επικοινωνία ή η ελαχιστοποίηση της µέγιστης ενέργειας ώστε να επιτυγχάνεται όσο το δυνατό µεγαλύτερος χρόνος ζωής όλων των κόµβων του δικτύου. Στη διατριβή εξετάζουµε αλγόριθ­µους για την εγκαθίδρυση διαφορετικών σχηµάτων επικοινωνίας σε αδόµητα ασύρµατα δίκτυα όπου βασικό κριτήριο για την εκτίµηση της απόδοσής τους θα είναι η κατανάλωση ενέργειας που επιφέρουν στο δίκτυο. Μοντελοποιούµε τα δίκτυα µε ειδικά γραφήµατα και τα αντίστοιχα προβλήµατα επικοινωνίας σαν προβλήµατα συνδυαστικής βελτιστοποίησης στα γραφήµατα αυτά. Τα αποτελέσµατά µας περιλαµβάνουν νέους αλγόριθµους που βελτιώνουν προηγούµενα γνωστά σχετικά αποτελέσµατα και νέα κάτω φράγµατα. Με κεντρικό στόχο την αποδοτική κατανοµή ενέργειας σε ασύρµατα δίκτυα, η µελέτη µας έχει διττό χαρακτήρα: από τη µια πλευρά, ασχολούµαστε µε µε­λέτη και ανάλυση θεµελιωδών προβληµάτων της Θεωρητικής Επιστήµης των Υπολογιστών (όπως, π.χ., το πρόβληµα Κάλυψης µε Σύνολα). Τέτοια προβλήµατα, και ειδικές περιπτώσεις τους, παρουσιάζουν εξαιρετικό ενδιαφέρον αφού χρησιµοποιούνται (µεταξύ άλλων) συχνά για τη µοντελοποίηση προβλη­µάτων ενεργειακά αποδοτικής επικοινωνίας σε ασύρµατα δίκτυα. Επιπλέον, προτείνουµε και αναλύουµε νέους αλγόριθµους για συγκεκριµένα σενάρια επικοινωνίας σε σύγχρονα ασύρµατα δίκτυα. Από την άλλη πλευρά, µελετάµε και εκτιµούµε πειραµατικά την απόδοση αρκετών αλγορίθµων και τεχνικών (από τη βιβλιογραφία αλλά και νέων) για ενεργειακά αποδοτική επικοινωνία σε ασύρµατα δίκτυα. Ειδικότερα: Μελετάµε το πρόβληµα κάλυψης µε σύνολα και ενδιαφέρουσες παραλ­λαγές του. Παρουσιάζουµε νέους συνδυαστικούς προσεγγιστικούς αλγόριθµους για το πρόβληµα k-κάλυψης συνόλων. Προηγούµενες προσεγγίσεις έχουν βασισθεί σε επεκτάσεις του άπληστου αλγόριθµου µέσω αποδοτικού χειρισµού µικρών συνόλων. Οι νέοι αλγόριθµοι επεκτείνουν περαιτέρω τις προηγούµενες προσεγγίσεις χρησιµοποιώντας την ιδέα του υπολογισµού µεγάλων οµάδων στοιχείων και στη συνέχεια της οµαδοποίησής τους σε σύνολα µεγάλου µεγέθους. Τα αποτελέσµατά µας βελτιώνουν τα καλύτερα γνωστά φράγµατα προσέγγισης για το πρόβληµα k-κάλυψης συνόλων για κάθε τιµή του k >= 6. Η τεχνική που χρησιµοποιούµε για την ανάλυση παρουσιάζει επιπλέον ανεξάρτητα ενδιαφέρον: το πάνω φράγµα για τον παράγοντα προ­σέγγισης επιτυγχάνεται φράσσοντας την αντικειµενική τιµή ενός γραµµικού προγράµµατος η οποία ‘αποκαλύπτει’ το λόγο προσέγγισης του υπό εξέταση αλγορίθµου (factor-revealing). Παρουσιάζουµε έναν απλό αλγόριθµο για το πρόβληµα εύρεσης µέγιστου δάσους γεννητικού αστέρα. Λαµβάνουµε υπόψη το γεγονός ότι το πρόβληµα αποτελεί ειδική περίπτωση του συµπληρωµατικού προβλήµατος κάλυψης συ­νόλου και προσαρµόζουµε έναν αλγόριθµο των Duh και Furer για την επίλυ­σή του. Αποδεικνύουµε ότι ο αλγόριθµος αυτός υπολογίζει 193/240 που είναι περίπου ίσο με 0.804 ­προσεγγιστικά δάση γεννητικών αστέρων. Το αποτέλεσµα αυτό βελτιώνει ένα προηγούµενο άνω φράγµα µε τιµή 0.71 των Chen και άλλων. Αν και ο αλ­γόριθµος είναι καθαρά συνδυαστικός, η ανάλυσή µας ορίζει ένα γραµµικό πρόγραµµα που χρησιµοποιεί µια παράµετρο f το οποίο είναι επιλύσιµο για τιµές της παραµέτρου f που δεν είναι µικρότερες από το λόγο προσέγγισης του αλγορίθµου. Η ανάλυση είναι αυστηρή και, το ενδιαφέρον είναι ότι, µπορεί να εφαρµοστεί και σε συµπληρωµατικές εκδοχές του προβλήµατος κάλυψης συνόλου όπως η εξοικονόµηση χρωµάτων. Δίνει την ίδια εγγύηση προσέγγισης µε τιµή 193/240 που οριακά βελτιώνει το προηγούµενο γνω­στό κάτω φράγµα των Duh και Furer. Αποδεικνύουµε επίσης ότι, γενικά, µια φυσική κλάση αλγορίθµων τοπικής αναζήτησης δε δίνουν καλύτερα από 1/2-προσεγγιστικά δάση γεννητικών αστέρων. Μελετάµε προβλήµατα επικοινωνίας σε ασύρµατα δίκτυα που υποστηρί­ζουν πολλαπλά µέσα ασύρµατης διασύνδεσης. Σε τέτοια δίκτυα, δύο κόµβοι µπορούν να επικοινωνήσουν αν είναι αρκετά κοντά και διαθέτουν κάποιο κοινό µέσο ασύρµατης διασύνδεσης. Η ενεργοποίηση ενός µέσου ασύρµατης διασύνδεσης επιφέρει ένα κόστος που αντανακλά την ενέργεια που καταναλώ­νεται όταν κάποιος κόµβος χρησιµοποιεί το µέσο αυτό. Διακρίνουµε µεταξύ της συµµετρικής και της µη συµµετρικής περίπτωσης, µε βάση το κόστος ενεργοποίησης για κάθε ασύρµατο µέσο διασύνδεσης είναι το ίδιο για όλους τους κόµβους ή όχι. Για τη συµµετρική περίπτωση, παρουσιάζουµε έναν (3/2+ε)–προσεγγιστικό αλγόριθµο για το πρόβληµα πλήρους διασύνδεσης µε ελάχιστο κόστος ενεργοποίησης, βελτιώνοντας ένα προηγούµενο φράγµα µε τιµή 2. Για τη µη συµµετρική περίπτωση, αποδεικνύουµε ότι το πρόβληµα διασύνδεσης δεν είναι προσεγγίσιµο στα πλαίσια ενός παράγοντα υπολογα­ριθµικού ως προς το πλήθος των κόµβων και παρουσιάζουµε ένα λογαριθµι­κό προσεγγιστικό αλγόριθµο για µια γενικότερη περίπτωση που µοντελοποιεί την οµαδική επικοινωνία. Επίσης, µελετάµε αλγόριθµους για τον υπολογισµό αποδοτικών ως προς την ενέργεια δένδρων µετάδοσης (multicasting) σε ασύρµατα αδόµητα δί­κτυα. Τέτοιοι αλγόριθµοι είτε ξεκινούν από µια κενή λύση η οποία σταδιακά επαυξάνεται για να δώσει ένα δένδρο µετάδοσης (επαυξητικοί αλγόριθµοι ­augmentation algorithms) είτε λαµβάνουν σαν είσοδο ένα αρχικό δένδρο µε­τάδοσης και εκτελούν ‘περιπάτους ’ σε διαφορετικά δένδρα µετάδοσης για πεπερασµένο αριθµό βηµάτων µέχρι να επιτευχθεί κάποια αποδεκτή µείωση στην κατανάλωση της ενέργειας (αλγόριθµοι τοπικής αναζήτησης -local search algorithms). Εστιάζουµε τόσο σε επαυξητικούς αλγόριθµους όσο και σε αλγό­ριθµους τοπικής αναζήτησης και συγκεκριµένα έχουµε υλοποιήσει αρκετούς υπάρχοντες αλγόριθµους από τη βιβλιογραφία αλλά και νέους. Συγκρίνου­µε πειραµατικά τους αλγόριθµους αυτούς σε τυχαία γεωµετρικά στιγµιότυπα του προβλήµατος και επιτυγχάνουµε αποτελέσµατα όσον αφορά στην αποδο­τικότητα ως προς την ενέργεια των λύσεων που λαµβάνουµε. Παρουσιάζουµε επίσης αποτελέσµατα σχετικά µε το χρόνο εκτέλεσης των υλοποιήσεών µας. Επίσης διερευνούµε το κατά πόσον οι λύσεις που λαµβάνουµε από επαυ­ξητικούς αλγόριθµους µπορούν να βελτιωθούν µέσω αλγορίθµων τοπικής αναζήτησης. Τα αποτελέσµατά µας αποδεικνύουν ότι ένας από τους νέους αλγόριθµους που προτείνουµε και οι εκδοχές του επιτυγχάνουν τις πιο απο­δοτικές ενεργειακά λύσεις και µάλιστα πολύ γρήγορα και, επιπλέον, υποδεικ­νύουν ιδιότητες γεωµετρικών στιγµιοτύπων του προβλήµατος που συντελούν στη βελτιωµένη απόδοση των επαυξητικών αλγορίθµων. / In this dissertation, we study issues arising in wireless communication networks, i.e., networks based on telecommunication infrastructure like cellular wireless networks, networks of autonomous wireless transmitters like ad hoc wireless networks, and so on. Wireless networks have received significant attention during the recent years. Especially, ad hoc wireless networks for which unlike traditional wired networks or cellular wireless networks, no wired backbone infrastructure is installed emerged due to their potential applications in emergency disaster relief, battlefield, etc. Like in traditional wired networks, an important problem concerns the establishment of communication patterns like broadcasting, multicasting, gossiping, all-to-all communication, and group communication. Communication then requires energy consumption at network nodes, and given that in ad hoc wireless networks energy is a scarce resource, it is of paramount importance to use it efficiently when establishing communication patterns. In such a setting, it is usually pursued that either the total energy consumed at networks nodes or the maximum energy consumed at any network node is minimized so that the network lifetime is prolonged as long as possible. Herein, we present and analyze theoretically and experimentally algorithms for guaranteeing the establishment of various communication patterns in ad hoc wireless networks and evaluate their performance in terms of their energy-efficiency. We represent these networks using graphs and model the corresponding communication problems as combinatorial optimization problems in such graphs. Our results include new algorithms which improve previously known relevant results as well as new lower bounds. Our main objective being the efficient energy allocation in wireless networks, our study is of dual character: on the one hand, we study and analyze fundamental problems of Theoretical Computer Science (like, e.g., Set Cover); such problems, as well as special cases of them, are highly interesting since they usually model energy-efficient communication problems in wireless networks. Furthermore, we propose and analyse new algorithms for particular communication scenaria in modern wireless networks. On the other hand, we experimentally study and evaluate several algorithms and techniques (both from the literature and new ones) for energy-efficient communication in wireless networks.

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal