<p>Today, information and communication technology is not only for professional use, but also for private tasks. In this thesis, the use of such technology for managing family information flow is investigated. Busy family life today, with school, work and leisure activites, makes coordination and synchronisation a burden. In what way cell-phones and Internet provides a support for those tasks is investigated, together with proposals for future technology.</p><p>The problem with coordination and synchronisation were found to be managed by a bulletin board placed at a central point at home. Besides the bulletin board, we found that calendars, shopping lists, and to-do lists are important. The families we investigated in field studies were all intensive users of both Internet and cell-phones.</p><p>Since the bulletin board played such an important role in the family life, we equipped families with cameras to be able to track what happened at those places with help of photo diaries. The field studies revealed that each family had their own unconscious procedure to manage the flow of notes on the bulletin board.</p><p>With technology, new problem will emerge. We investigated how notes on typical family bulletin boards may be visualised on a computer screen, and compared click-expand, zoom-pan and bifocal interfaces. The click-expand interface was substantially faster for browsing, and also easier to use.</p><p>An advantage of information and communication technology is that it may provide possibilities for multiple interfaces to information, and not only different terminals but also from different places. At home, a digital refrigerator door or a mobile web tablet; at work or at school, a conventional computer; when on the move, a cell-phone or a PDA. System architecture for these possibilities is presented.</p> / Report code: LiU-TEK-LIC-2004:39.

Une des problématiques majeure de sécurité pour les opérateur est de permettre à ses utilisateurs de maintenir la sécurité d’une communication même au travers d’un réseau qui ne soit pas de confiance. Pour l’utilisateur, une communication est établie entre deux identifiants, et ceci indépendamment des mouvements et changements de réseau de l’utilisateur. Autrement dit, l’opérateur doit permettre cette communication entre identifiants possible grâce au système DNS, et fournir les mécanismes réseaux nécessaires afin que la communication puisse être maintenue quand le client bouge et change d’adresse. Dans cette thèse nous nous somme concentrés sur les aspects sécurités et plus exactement: - DNSSEC: DNSSEC définit comme sécuriser la résolution d’un nom de domaine. La sécurité a un coût que nous commençons par évaluer avant de proposer des architectures permettant aux ISPs de migrer des plateformes de Service de Résolution de DNS vers DNSSEC. - IPsec: IPsec définit comment sécuriser une communication IP. Dans cette thèse nous définissons une extension qui permet à un utilisateur de maintenir une communication sécurisée par IPsec pour un terminal mobile, Multihomé, et avec de Multiples Interfaces / ISPs are concerned about providing and maintaining the level of security of its End User’s communications. A communication is initiated by the End User with a name, and goes on by exchanging packets between two IP addresses. In this thesis, we focused our attention on two main points: (1) providing a secure Naming service, and (2) making IPsec communication resilient to IP address modification, addition or lost of an interface. We designed MOBIKE-X for that purpose and propose it as a standard at the IETF

Inom modern informationsteknologi har självloggning fått en allt större roll. Dessa tjänster består vanligtvis av flera delar som behöver samverka för att ge en bra användarupplevelse. Eftersom fysiska enheter kompletteras med appar och webbtjänster behövs det en samspelad gränssnittsdesign för att användarna skall känna ett samband mellan tjänsterna och för att användarna skall använda flera delar. Detta kan göras på flera olika sätt, men genom olika designmål kan utvecklarna bland annat forma de olika delarna av tjänsterna mot samma mål eller spetsa dem för att uppfylla olika delar av tjänsten. Studien undersöker användarnas relation till olika gränssnitt och även olika tjänster. Denna uppsats xxnner att engagemang, personlighet och motivation påverkar valet av tjänst men även hur aktiva användarna är i ett flergränssnittsanvändande och vad de tycker om att behöva hantera flera gränssnitt. Denna uppsats belyser även hur användarna i sin jakt på större självin- sikt samlar och reflekterar över insamlad data över flera gränssnitt och enheter. Genom en kvalitativ intervjustudie med aktiva användare undersöks det närmare hur användarna upplever sitt samlande och hur tjänsterna fungerar och används över flera gränssnitt. Resultaten visar att användare ofta har problem med insamlingen av data och dessutom sällan använder sig av mer än ett eller kanske två gränssnitt. / In modern information technology Personal Informatics(PI) has gained an increasingly important role. Usually PI consists of several parts that need to work together to provide a great user experience. Since physical devices supplemented with apps and web services, to allow users to feel the connection between the services it is very important with a unified interface design. This can be done in several different ways, but through different design objectives you can shape services towards the same goal, or focus them to meet goals in other parts of the service. The study examines users' relationship with various interfaces and also various services. This paper finds that dedication, personality and motivation influences the choice of service but also, how active users are in a multi-use interface and what they think about having to manage multiple interfaces. This paper also highlights how the users in their quest for greater self-awareness collect and reflect on collected data over multiple interfaces and devices. Through qualitative interviews with active users we look closely at how users perceive their collecting and how the services works and are used across multiple interfaces. The results show that users often have problems with the collection of data and that they also rarely use more than one or maybe two interfaces.

Today, information and communication technology is not only for professional use, but also for private tasks. In this thesis, the use of such technology for managing family information flow is investigated. Busy family life today, with school, work and leisure activites, makes coordination and synchronisation a burden. In what way cell-phones and Internet provides a support for those tasks is investigated, together with proposals for future technology. The problem with coordination and synchronisation were found to be managed by a bulletin board placed at a central point at home. Besides the bulletin board, we found that calendars, shopping lists, and to-do lists are important. The families we investigated in field studies were all intensive users of both Internet and cell-phones. Since the bulletin board played such an important role in the family life, we equipped families with cameras to be able to track what happened at those places with help of photo diaries. The field studies revealed that each family had their own unconscious procedure to manage the flow of notes on the bulletin board. With technology, new problem will emerge. We investigated how notes on typical family bulletin boards may be visualised on a computer screen, and compared click-expand, zoom-pan and bifocal interfaces. The click-expand interface was substantially faster for browsing, and also easier to use. An advantage of information and communication technology is that it may provide possibilities for multiple interfaces to information, and not only different terminals but also from different places. At home, a digital refrigerator door or a mobile web tablet; at work or at school, a conventional computer; when on the move, a cell-phone or a PDA. System architecture for these possibilities is presented. / <p>Report code: LiU-TEK-LIC-2004:39.</p>

Aujourd'hui les réseaux de capteurs sont devenus des systèmes pouvant atteindre un très grand nombre de noeuds, avec une zone de couverture déterminée et déployés d'une manière plus ou moins dense dans un environnement hétérogène dont on mesure ainsi son état global. La problématique de cette thèse consiste à concevoir une architecture pour les objets communicants à faible consommation en utilisant des antennes « intelligentes » pour l'instrumentation et la mesure. Intégrant une approche pluridisciplinaire, cette architecture couvre les services offerts depuis les couches MAC jusqu'à celles de plus haut niveau. Basés sur une partie matérielle complètement reconfigurable (amplificateur de puissance et antennes à base de MEMS RF), les services des couches supérieures sont définis en partie sur circuits numériques pour la couche physique (bande de base) et la couche MAC, et de manière logicielle pour les protocoles de routages adaptés et les services innovants. En résumé, le travail consiste à concevoir un système autonome multi capteurs, d'acquisition et de traitement avec mémorisation, communicant à travers un réseau sans fil. Les principaux problèmes à résoudre seront : le contrôle de la topologie, la précision de la synchronisation, la consommation d'énergie. / Researches in the field of sensor networks show the variety and vastness of applications in which these types of systems are used. One of their main features is the large number (up to hundreds of elements) of sensors that must be distributed in different environments. Another concern consists in making routing decisions in order to reduce the energy consumption. Depending on the application requirements, ensuring synchronous network functionality is currently a challenge. The issue addressed in this thesis is to develop an architecture for smart objects using low-power antennas for structural heald monitoring. Integrating a multidisciplinary approach, this architecture includes services from the MAC layer to those of the highest level. In summary, we will develop an autonomous system ofi sensors, for acquisition and information processing, which communicate via a wireless network. The main problems are: the control of topology, the timing accuracy and the energy consumption.

Wireless mobile ad-hoc networks consist of a collection of peer mobile nodes that form a network and are capable of communicating with each other without help from stationary infrastructure such as access points. The availability of low-cost, com-modity network interface cards (NICs) has made the IEEE 802.11 medium access control (MAC) protocol the de facto MAC protocol for wireless mobile ad-hoc net-works, even though it is not optimal. The IEEE 802.11 MAC protocol is designed to have stations share a single channel in a given network. However, many of the IEEE 802.11 physical (PHY) layer specifications define multiple channels and allow the simultaneous, non-interfering use of some of these channels. Therefore, multiple communications can occur at the same time, offering the opportunity to increase the effective network capacity. We present an innovative routing protocol that utilizes multiple channels to im-prove the performance of wireless ad-hoc networks. The basic idea of the protocol is to use multiple channels so that multiple useful transmissions can occur simultane-ously, thus increasing network capacity. The proposed scheme requires minor changes to existing proactive ad-hoc routing protocols and no modifications to the current IEEE 802.11 MAC protocol. To reduce inefficiencies due to periodic updates in the proactive routing protocols, the proposed scheme divides the network layer into control and data planes. Nodes send routing updates using the control channel and user packets using the data channel. To demonstrate the multi-channel routing scheme, we extend the Destination-Sequenced Distance-Vector (DSDV), Open Shortest Path First-Minimal Connected Dominating Set (OSPF-MCDS), and Optimized Link State Routing (OLSR) protocol to multiple channel (MC) versions, denoted as DSDV-MC, OSPF-MCDS-MC, and OLSR-MC, respectively. Simulation results for DSDV-MC, OSPF-MCDS-MC, and OLSR-MC are presented and experimental results for OLSR-MC are presented. Simulation results indicate that DSDV-MC and OSPF-MCDS-MC effectively exploit multiple channels to improve network capacity. Goodput, the throughput consider-ing only useful error-free packets, increases with an increased number of available channels as the number of nodes and network load increase in both single-hop and multiple-hop networks. Experimental results with OLSR-MC also support that the proposed scheme increases network capacity without modification to the MAC proto-col in a real implementation. Although simulation and experimental results show that proposed scheme im-proves network capacity by exploiting multiple channels, problems exist with channel distribution. We introduce a new metric, the Channel Distribution Index (CDI) to in-vestigate these issues. The CDI indicates the fairness of the channel distribution. We identify the channel convergence problem, where a particular channel is over-utilized, and propose a channel reallocation scheme to mitigate the impact of the channel convergence problem using the CDI. / Ph. D.

ISPs are concerned about providing and maintaining the level of security of its End User's communications. A communication is initiated by the End User with a name, and goes on by exchanging packets between two IP addresses. In this thesis, we focused our attention on two main points: (1) providing a secure Naming service, and (2) making IPsec communication resilient to IP address modification, addition or lost of an interface. We designed MOBIKE-X for that purpose and propose it as a standard at the IETF

La presencia de topologías multi-salto en comunicaciones inalámbricas de todo tipo es cada vez más apreciable, esperándose además que esta tendencia se mantenga en un futuro cercano. A pesar de que inicialmente fueran concebidos para solventar la falta de infraestructura subyacente en ciertos escenarios concretos, estos despliegues han acaparado el interés de diferentes actores del ámbito de las comunicaciones (incluyendo los operadores), con lo que es razonable pensar que su relevancia irá creciendo paulatinamente. De hecho, existen diversas iniciativas en algunos foros de estandarización que de alguna manera corroboran este hecho. Hay que tener en cuenta, por otro lado, otros factores adicionales (como la eclosión que se ha producido en el campo de las redes de sensores inalámbricos) que seguramente fomentarán el uso de estas topologías.A pesar de la creciente actividad en el ámbito de los despliegues multi-salto, sigue siendo necesario establecer, de manera cuantitativa, cuáles son sus posibles beneficios, tanto para los usuarios finales de los sistemas de comunicación, como para los operadores, especialmente teniendo en cuenta el elevado grado de heterogeneidad que también caracterizará las redes inalámbricas.Por otro lado, en lo que se refiere a los algoritmos y protocolos a ser empleados sobre este tipo de topologías, y a pesar de la intensa labor de investigación que sobre ellos se ha realizado recientemente, queda aún un número relevante de aspectos a analizar. En primer lugar, el mero hecho de que sus requerimientos y retos iniciales hayan variado de manera sustancial puede, y debe, influenciar sus principios básicos. Además, es necesario acometer verificaciones de los mismos sobre plataformas reales y, así mismo, asegurar que las evaluaciones que se realicen con técnicas de simulación utilicen modelos reales que permitan reflejar de manera fidedigna las condiciones que se dan en la realidad.Esta Tesis afronta, en primer lugar, la evaluación cuantitativa de la mejora que es posible alcanzar al utilizar topologías inalámbricas multi-salto para extender despliegues de red más tradicionales. Un primer aspecto que es razonable considerar es la ampliación de la cobertura que se consigue; en este caso se ha realizado un análisis que sigue un doble enfoque, analítico y mediante técnicas de simulación, para determinar es la ganancia que se logra. Se ha partido de dos modelos de red complementarios entre sí, asumiendo en el primero de ellos una falta total de planificación previa, mientras que en el segundo se utiliza un emplazamiento óptimo de los elementos de conexión a la red. Se ha comprobado que, a pesar de sus características claramente antagónicas, los resultados obtenidos con ambos escenarios son similares entre sí. Además, se concluye que, a pesar de que la ampliación de la cobertura que se alcanza es muy relevante, es posible establecer un límite razonable para el número máximo de saltos a emplear, ya que la mejoría adicional al incrementar la longitud de la ruta deja de ser apreciable a partir del mismo. Este aspecto se podría aprovechar para influir en el diseño de las técnicas de encaminamiento a emplear sobre este tipo de topologías.Se analizan también otras mejoras adicionales, utilizando un escenario en el que predomina sobremanera la heterogeneidad de los elementos de conexión a la red, e integrando las extensiones multi-salto con un algoritmo de selección de acceso genérico, que permite modular el peso que tienen las diferentes entidades (tanto el terminal de usuario como la propia red), así como diversos parámetros y restricciones a considerar, a la hora de determinar la alternativa de conexión óptima. Se comprueba que, tanto para los usuarios, gracias a la mejora de la calidad del servicio que perciben, como para la red, que incrementa el tráfico que es capaz de cursar, el uso de comunicaciones multi-salto puede resultar altamente atractivo.En segundo lugar, también se afronta la mejora de las técnicas de encaminamiento que tradicionalmente se emplean sobre las redes multi-salto, basadas en minimizar el número de saltos entre los dos extremos de la comunicación. Para ello, y utilizando el paradigma de Cross-Layer Optimisation, se propone una versión mejorada del protocolo DSR, denominada SADSR, que emplea la información relativa a la calidad de los enlaces subyacentes para modular el algoritmo de selección de ruta. Destacar que se acomete una verificación experimental de dicha propuesta, contestando, de este modo, a una de las reivindicaciones más importantes en este campo. Los resultados obtenidos permiten inferir que las prestaciones de la propuesta realizada en el marco de esta Tesis son superiores a los de la versión original del DSR.A pesar del evidente valor que las validaciones empíricas aportan, tienen la limitación de que es complicado establecer topologías con un número elevado de nodos, o acometer experimentos con una pauta repetitiva para determinar un comportamiento promedio. Es por ello que también se acomete un análisis mediante técnicas de simulación, en el que se compara SADSR con la versión original del DSR, así como con otras propuestas que han acaparado el interés por parte de la comunidad científica. Los resultados que se derivan a raíz de la evaluación llevada a cabo no hacen sino corroborar lo que ya adelanta la verificación experimental, ya que las prestaciones del SADSR son muy superiores a las del resto de alternativas analizadas.Para llevar a cabo el análisis anterior es fundamental el uso de un modelo de canal que refleje, con el mayor grado de exactitud posible, un comportamiento realista. Para ello, en la Tesis se afronta el diseño, implementación y posterior integración en la plataforma Network Simulator de BEAR, un modelo de canal basado en filtrado auto-regresivo, que se caracteriza principalmente por emular la aparición de errores a ráfagas que se observa en entornos reales. En ese sentido, se parte de un extenso conjunto de medidas que permite corroborar el correcto funcionamiento de la propuesta. / The presence of multi-hop topologies within all types of wireless communications is becoming more and more common, and this tendency is expected to be maintained in the near future. Although they were originally conceived to compensate the lack of subjacent infrastructure in certain scenarios, these deployments have attracted the interest of different actors in the wireless communications value chain (including network operators) and thus it is logical to think that their relevance will gradually increase. In fact, there already exist some standardization initiatives which corroborate this point to some extent. Furthermore, other additional factors, such as the rapid growth which has been seen in wireless sensor technologies, also strengthen the use of these topologies..In spite of the growing activity in the multi-hop deployment field, it is still necessary to establish, in a quantitative way, their potential benefits, both for the end-users of the communication systems, as well as for the operators, considering, in addition, the high degree of heterogeneity which will characterize wireless networks in the future.On the other hand, as far as algorithms and protocols to be used over this type of topology are concerned, and despite the intense research which has been conducted into them, there is still a large number of issues to be tackled. First, the simple fact that their initial requirements and challenges have been modified can, and must, influence their basic principles. In addition, it becomes necessary to address their validation on real platforms and, on the other hand, to ensure that simulation-based evaluations of their performance make use of realistic models which accurately reflect the conditions which are observed in real scenarios.This dissertation tackles, on the one hand, the quantitative evaluation of the improvements which are achievable when using multi-hop topologies to extend legacy network deployments. One first aspect which is logical to consider is the increase in the coverage which is brought about. In this sense, a two-fold approach has been followed, employing both an analytical as well as a simulation-based analysis, to establish what the gain is. Two network models have been used, being complementary to each other; the first one assumes a complete lack of network planning for the deployment of the access elements, while the second one assumes an optimum distribution of them. Although their characteristics are completely different, the results are somehow similar for both cases. Furthermore, it can be concluded that, despite the coverage extension which can be obtained, it is indeed possible to establish a reasonable limit on the maximum number of hops to be used, since the improvement becomes less relevant for higher values. This aspect could influence the design of routing techniques to be used over this type of topology.Furthermore, other additional benefits have been also analyzed, using a network deployment in which the presence of heterogeneity (multi-access) is evident. The multi-hop extensions have been integrated within a generic access selection algorithm which enables the modification of the weights which are assigned to the different entities (both the end-user terminals and the network) as well as to the set of parameters and constraints to be considered when selecting the most appropriate access alternative. It is concluded that for both the end-users, who improve their perception of the quality of service, and the network, which is able to increase the overall amount of traffic possible to be handled, multi-hop extensions are certainly beneficial.In addition, the dissertation also tackles the improvement of the routing techniques which are traditionally employed over multi-hop networks, which are based on minimizing the number of hops between the two sides of the communication. To accomplish this, and using the Cross-Layer Optimisation paradigm, an improved version of the DSR protocol is proposed, namely SADSR. It uses information about the subjacent link qualities to modulate the route selection algorithm. It is worth highlighting that a fully empirical (on a real platform) validation has been conducted, addressing one of the most pressing demands within this field. The results obtained allow us to infer that the proposal made in the framework of this dissertation is clearly outperforming the original DSR version.Although the added value provided by empirical validations is unquestionable, they also have some limitations. First, they normally do not favour the establishment of large topologies, or to undertake repetitive experiments aimed at finding an average behaviour. In this sense, a simulation-based analysis is also used so as to compare the SADSR with the original DSR version as well as with other proposals which have recently attracted interest from the scientific community. The results obtained by the validation carried out on a real platform are confirmed, since the performance brought about by the SADSR is somewhat higher than that of the other strategies.In order to perform the previous analysis the use of a realistic channel model, able to capture with a high degree of accuracy the behaviour exhibited on real platforms, is mandatory. To fulfil this requirement, the dissertation also tackles the design, implementation, and integration within the Network Simulator platform of BEAR, a channel model based on auto-regressive filtering. It is mainly characterized by being able to emulate the bursty presence of errors which is observed over real channels. The design is based on an extensive set of measurements which is used to assess the validity of the proposal.

Στην παρούσα διδακτορική διατριβή, ασχολούµαστε µε ζητήµατα που ανακύπτουν σε ασύρµατα δίκτυα επικοινωνίας, δηλ. δίκτυα που βασίζονται σε τηλεπικοινωνιακή υποδοµή όπως τα κυψελικά δίκτυα κινητής τηλεφωνίας, δίκτυα αυτόνοµων ασύρµατων εκποµπών όπως τα ασύρµατα δίκτυα τύπου 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.