A wireless ad hoc network consists of a number of mobile nodes that temporarily form a dynamic infrastructure-less network. New routing protocols that can adapt to the frequent topology changes induced by node mobility and varying link qualities are needed. During the last decade dozens of different ad hoc routing protocols have been proposed, optimized and partially compared, mainly through simulation studies. This thesis takes an experimental approach to the evaluation of ad hoc routing protocols. We argue that real world experiments are needed in order to complement simulation studies, and to gain practical experience and insights that can provide feedback to routing protocol design and existing simulation models. For example, we discovered a performance discrepancy for the AODV protocol between real world experiments and corresponding simulation studies. This so called ``communication gray zone'' problem was explored and countermeasures were implemented. As a result we could eliminate this performance problem to a large extent. We have implemented a software-based testbed called APE to carry out efficient and systematic experimental evaluation of ad hoc routing protocols. Experiments with up to 37 participating ad hoc nodes have demonstrated APE's ability to scale efficiently and assess repeatability between test runs. APE is part of our methodology for test repeatability in a real world ad hoc routing protocol testbed. It addresses the repeatability issue induced by stochastic factors like the radio environment and node mobility. Using APE, we have performed a systematic experimental evaluation of three ad hoc routing protocols (AODV, OLSR and LUNAR). Our results show that TCP does not work satisfactorily even in very small networks with limited mobility.

在耐延遲網路環境下節點的相遇情況不是很頻繁，這可能導致節點間的連線斷斷續續，使得有效地將訊息傳遞成為一件困難的事情。藉由社群感知轉送機制的中間度指標特性，可以來提升傳送成功率。雖然大多數研究幾乎都是將訊息轉送到單一目的地或是多個且已知的目的地。然而，一些應用像是廣告的散佈，要將訊息送給對訊息有興趣的人，但卻不知道是誰。因此，關鍵的問題為如何建立社群網路關係的親密度機制，來選擇作為轉送訊息的節點，並利用群體廣播的方式盡可能有效地傳播至最多可能目標目的地，進而提升效能。 本論文以群播機制和社群感知當作基礎概念，來設計新的轉送訊息的方法和公式化選擇中繼節點的機制。最後，我們使用政治大學實際軌跡來模擬，將模擬結果與其它路由演算法比較，其結果證明我們所提出的方法能提高訊息傳送成功率和正確率，降低傳送延遲時間和傳送訊息的成本。 / In delay tolerant networks (DTNs), nodes infrequently encounter with each others. This results in intermittent connectivity of the nodes, and makes it difficult to deliver the message effectively. A social-aware forwarding scheme can help for successful delivery ratio by utilizing the characteristic of their centrality metric. Most of the previous studies focus on message delivery to single destination or some priori known destinations. However, some applications like advertisement dissemination may not know who will be the interested persons to be delivered. Therefore, the key challenge is how to establish the social relationship strategy to select appropriate nodes as relays, and furthermore to use multicasting to disseminate effectively as many “target” destinations as possible to improve the performance. This thesis developed a new strategy which has a new forwarding message scheme and formulates the selection of the relay nodes based on the concept of the multicasting and the social network. Finally, we used the reality trace data of National Chengchi University to simulate. The simulation results are compared to others DTNs routing protocols as well as other social-aware forwarding schemes. The results showed that our proposed approach can enhance the successful delivery ratio and delivery accuracy, decrease the delivery delay and reduce the delivery overhead.

In multi-hop wireless network (MWN), the mobile nodes relay others’ packets for enabling new applications and enhancing the network deployment and performance. However, the selfish nodes drop the packets because packet relay consumes their resources without benefits, and the malicious nodes drop the packets to launch Denial-of-Service attacks. Packet drop attacks adversely degrade the network fairness and performance in terms of throughput, delay, and packet delivery ratio. Moreover, due to the nature of wireless transmission and multi-hop packet relay, the attackers can analyze the network traffic in undetectable way to learn the users’ locations in number of hops and their communication activities causing a serious threat to the users’ privacy. In this thesis, we propose efficient security protocols for thwarting packet drop attacks and preserving users’ privacy in multi-hop wireless networks. First, we design a fair and efficient cooperation incentive protocol to stimulate the selfish nodes to relay others’ packets. The source and the destination nodes pay credits (or micropayment) to the intermediate nodes for relaying their packets. In addition to cooperation stimulation, the incentive protocol enforces fairness by rewarding credits to compensate the nodes for the consumed resources in relaying others’ packets. The protocol also discourages launching Resource-Exhaustion attacks by sending bogus packets to exhaust the intermediate nodes’ resources because the nodes pay for relaying their packets. For fair charging policy, both the source and the destination nodes are charged when the two nodes benefit from the communication. Since micropayment protocols have been originally proposed for web-based applications, we propose a practical payment model specifically designed for MWNs to consider the significant differences between web-based applications and cooperation stimulation. Although the non-repudiation property of the public-key cryptography is essential for securing the incentive protocol, the public-key cryptography requires too complicated computations and has a long signature tag. For efficient implementation, we use the public-key cryptography only for the first packet in a series and use the efficient hashing operations for the next packets, so that the overhead of the packet series converges to that of the hashing operations. Since a trusted party is not involved in the communication sessions, the nodes usually submit undeniable digital receipts (proofs of packet relay) to a centralized trusted party for updating their credit accounts. Instead of submitting large-size payment receipts, the nodes submit brief reports containing the alleged charges and rewards and store undeniable security evidences. The payment of the fair reports can be cleared with almost no processing overhead. For the cheating reports, the evidences are requested to identify and evict the cheating nodes. Since the cheating actions are exceptional, the proposed protocol can significantly reduce the required bandwidth and energy for submitting the payment data and clear the payment with almost no processing overhead while achieving the same security strength as the receipt-based protocols. Second, the payment reports are processed to extract financial information to reward the cooperative nodes, and contextual information such as the broken links to build up a trust system to measure the nodes’ packet-relay success ratios in terms of trust values. A node’s trust value is degraded whenever it does not relay a packet and improved whenever it does. A node is identified as malicious and excluded from the network once its trust value reaches to a threshold. Using trust system is necessary to keep track of the nodes’ long-term behaviors because the network packets may be dropped normally, e.g., due to mobility, or temporarily, e.g., due to network congestion, but the high frequency of packet drop is an obvious misbehavior. Then, we propose a trust-based and energy-aware routing protocol to route traffics through the highly trusted nodes having sufficient residual energy in order to establish stable routes and thus minimize the probability of route breakage. A node’s trust value is a real and live measurement to the node’s failure probability and mobility level, i.e., the low-mobility nodes having large hardware resources can perform packet relay more efficiently. In this way, the proposed protocol stimulates the nodes not only to cooperate but also to improve their packet-relay success ratio and tell the truth about their residual energy to improve their trust values and thus raise their chances to participate in future routes. Finally, we propose a privacy-preserving routing and incentive protocol for hybrid ad hoc wireless network. Micropayment is used to stimulate the nodes’ cooperation without submitting payment receipts. We only use the lightweight hashing and symmetric-key-cryptography operations to preserve the users’ privacy. The nodes’ pseudonyms are efficiently computed using hashing operations. Only trusted parties can link these pseudonyms to the real identities for charging and rewarding operations. Moreover, our protocol protects the location privacy of the anonymous source and destination nodes. Extensive analysis and simulations demonstrate that our protocols can secure the payment and trust calculation, preserve the users’ privacy with acceptable overhead, and precisely identify the malicious and the cheating nodes. Moreover, the simulation and measurement results demonstrate that our routing protocols can significantly improve route stability and thus the packet delivery ratio due to stimulating the selfish nodes’ cooperation, evicting the malicious nodes, and making informed decisions regarding route selection. In addition, the processing and submitting overheads of the payment-reports are incomparable with those of the receipts in the receipt-based incentive protocols. Our protocol also requires incomparable overhead to the signature-based protocols because the lightweight hashing operations dominate the nodes’ operations.

Wireless Mesh Network (WMN) is an emerging technology that is gaining importance among traditional wireless communication systems. However, WMNs are particularly vulnerable to external and insider attacks due to their inherent attributes such as open communication medium and decentralized architecture. In this research, we propose a complete distributed and cooperative intrusion detection system for efficient and effective detection of WMN attacks in real-time. Our intrusion detection mechanism is based on reliable exchange of network events and active cooperation between the participating nodes. In our distributed approach, Intrusion Detection Systems (IDSs) are independently placed at each mesh node to passively monitor the node routing behavior and concurrently monitor the neighborhood behavior. Based on that, we first implement a Routing Protocol Analyzer (RPA) that accuracy generates Routing Events from the observed traffic, which are then processed by the own node and exchanged between neighboring nodes. Second, we propose a practical Distributed Intrusion Detection Engine (DIDE) component, which periodically calculates accurate Misbehaving Metrics by making use of the generated Routing Events and pre-defined Routing Constraints that are extracted from the protocol behavior. Third, we propose a Cooperative Consensus Mechanism (CCM), which is triggered among the neighboring nodes if any malicious behavior is detected. The CCM module analyzes the Misbehaving Metrics and shares Intrusion Detection Results among the neighbors to track down the source of intrusion. To validate our research, we implemented the distributed intrusion detection solution using a virtualized mesh network platform composed of virtual machines (VMs) interconnected. We also implemented several routing attacks to evaluate the performance of the intrusion detection mechanisms

In multi-hop wireless network (MWN), the mobile nodes relay others’ packets for enabling new applications and enhancing the network deployment and performance. However, the selfish nodes drop the packets because packet relay consumes their resources without benefits, and the malicious nodes drop the packets to launch Denial-of-Service attacks. Packet drop attacks adversely degrade the network fairness and performance in terms of throughput, delay, and packet delivery ratio. Moreover, due to the nature of wireless transmission and multi-hop packet relay, the attackers can analyze the network traffic in undetectable way to learn the users’ locations in number of hops and their communication activities causing a serious threat to the users’ privacy. In this thesis, we propose efficient security protocols for thwarting packet drop attacks and preserving users’ privacy in multi-hop wireless networks. First, we design a fair and efficient cooperation incentive protocol to stimulate the selfish nodes to relay others’ packets. The source and the destination nodes pay credits (or micropayment) to the intermediate nodes for relaying their packets. In addition to cooperation stimulation, the incentive protocol enforces fairness by rewarding credits to compensate the nodes for the consumed resources in relaying others’ packets. The protocol also discourages launching Resource-Exhaustion attacks by sending bogus packets to exhaust the intermediate nodes’ resources because the nodes pay for relaying their packets. For fair charging policy, both the source and the destination nodes are charged when the two nodes benefit from the communication. Since micropayment protocols have been originally proposed for web-based applications, we propose a practical payment model specifically designed for MWNs to consider the significant differences between web-based applications and cooperation stimulation. Although the non-repudiation property of the public-key cryptography is essential for securing the incentive protocol, the public-key cryptography requires too complicated computations and has a long signature tag. For efficient implementation, we use the public-key cryptography only for the first packet in a series and use the efficient hashing operations for the next packets, so that the overhead of the packet series converges to that of the hashing operations. Since a trusted party is not involved in the communication sessions, the nodes usually submit undeniable digital receipts (proofs of packet relay) to a centralized trusted party for updating their credit accounts. Instead of submitting large-size payment receipts, the nodes submit brief reports containing the alleged charges and rewards and store undeniable security evidences. The payment of the fair reports can be cleared with almost no processing overhead. For the cheating reports, the evidences are requested to identify and evict the cheating nodes. Since the cheating actions are exceptional, the proposed protocol can significantly reduce the required bandwidth and energy for submitting the payment data and clear the payment with almost no processing overhead while achieving the same security strength as the receipt-based protocols. Second, the payment reports are processed to extract financial information to reward the cooperative nodes, and contextual information such as the broken links to build up a trust system to measure the nodes’ packet-relay success ratios in terms of trust values. A node’s trust value is degraded whenever it does not relay a packet and improved whenever it does. A node is identified as malicious and excluded from the network once its trust value reaches to a threshold. Using trust system is necessary to keep track of the nodes’ long-term behaviors because the network packets may be dropped normally, e.g., due to mobility, or temporarily, e.g., due to network congestion, but the high frequency of packet drop is an obvious misbehavior. Then, we propose a trust-based and energy-aware routing protocol to route traffics through the highly trusted nodes having sufficient residual energy in order to establish stable routes and thus minimize the probability of route breakage. A node’s trust value is a real and live measurement to the node’s failure probability and mobility level, i.e., the low-mobility nodes having large hardware resources can perform packet relay more efficiently. In this way, the proposed protocol stimulates the nodes not only to cooperate but also to improve their packet-relay success ratio and tell the truth about their residual energy to improve their trust values and thus raise their chances to participate in future routes. Finally, we propose a privacy-preserving routing and incentive protocol for hybrid ad hoc wireless network. Micropayment is used to stimulate the nodes’ cooperation without submitting payment receipts. We only use the lightweight hashing and symmetric-key-cryptography operations to preserve the users’ privacy. The nodes’ pseudonyms are efficiently computed using hashing operations. Only trusted parties can link these pseudonyms to the real identities for charging and rewarding operations. Moreover, our protocol protects the location privacy of the anonymous source and destination nodes. Extensive analysis and simulations demonstrate that our protocols can secure the payment and trust calculation, preserve the users’ privacy with acceptable overhead, and precisely identify the malicious and the cheating nodes. Moreover, the simulation and measurement results demonstrate that our routing protocols can significantly improve route stability and thus the packet delivery ratio due to stimulating the selfish nodes’ cooperation, evicting the malicious nodes, and making informed decisions regarding route selection. In addition, the processing and submitting overheads of the payment-reports are incomparable with those of the receipts in the receipt-based incentive protocols. Our protocol also requires incomparable overhead to the signature-based protocols because the lightweight hashing operations dominate the nodes’ operations.

在耐延遲網路上，離線的使用者，可以透過節點的相遇，以點對點之特定訊息繞送方法，將資訊傳遞至目的地。如此解決了使用者暫時無法上網時欲傳遞資訊之困難。因此，在本研究中，當使用者在某一地區，欲查詢該地區相關之資訊，但又一時無法連上網際網路時，則可透過耐延遲網路之特性，尋求其它同樣使用本服務之使用者幫忙以達到查詢之目的。 本論文提出一適地性服務之資料搜尋方法，以三層式區域概念，及混合式節點型態，並透過資料訊息複製、查詢訊息複製、資料回覆及資料同步等四項策略來達成使用者查詢之目的。特別在訊息傳遞方面，提出一訊息佇列選擇演算法，賦予優先權概念於每一訊息中，使得較為重要之訊息得以優先傳送，藉此提高查詢之成功率及減少查詢之延遲時間。最後，我們將本論文方法與其它查詢方法比較評估效能，其模擬結果顯示我們提出的方法有較優的查詢效率與延遲。 / In Delay Tolerant Networks (DTNs), the offline users can, through the encountering nodes, use the specific peer-to-peer message routing approach to deliver messages to the destination. Thus, it solves the problem that users have the demands to deliver messages while they are temporarily not able to connect to Internet. Therefore, by the characteristics of DTNs, people who are not online can still query some location based information, with the help of users using the same service in the nearby area. In this thesis, we proposed a Location-based content search approach. Based on the concept of three-tier area and hybrid node types, we presented four strategies to solve the query problem. They are Data Replication, Query Replication, Data Reply and Data synchronization strategies. Especially in message transferring, we proposed a Message Queue Selection algorithm. We set the priority concept to every message such that the most important one could be sent first. In this way, it can increase the query success ratio and reduce the query delay time. Finally, we evaluated our approach, and compared with other routing schemes. The simulation results showed that our proposed approach had better query efficiency and shorter delay.

Η αλματώδης πρόοδος στις ασύρματες επικοινωνίες έχει φέρει ως αποτέλεσμα την δυνατότητα δημιουργίας μικρών σε μέγεθος μικροϋπολογιστικών συστημάτων που έχουν την δυνατότητα ασύρματης διασύνδεσης. Λόγω του μικρού μεγέθους αυτών είναι δυνατή η μεταφορά τους ακόμα και από φυσικά πρόσωπα και άρα προσφέρουν με τον τρόπο αυτό το πλεονέκτημα φορητότητας. Παράλληλα η επιθυμία για δημιουργία δικτύων μεγάλης κλίμακας με χρήση τέτοιων συσκευών χωρίς την δυνατότητα σταθερής παροχής ενέργειας δημιούργησε την ανάγκη μικρής εμβέλειας μετάδοσης και άρα πολλαπλών επαναμεταδόσεων ανά πακέτο δεδομένων μέχρι να φτάσει στον τελικό προορισμό του. Το ερευνητικό αντικείμενο αυτής της διδακτορικής διατριβής είναι η πρόταση μίας ολοκληρωμένης ασύρματης δομής που θα παρέχει δυνατότητες ασύρματης διασύνδεσης σε δίκτυα μεγάλης κλίμακας χωρίς ύπαρξη κεντρικής διαχείρισης. Το πρόβλημα της εύρεσης διαδρομών σε ένα ασύρματο δίκτυο κινούμενων αισθητήρων αποτελεί ένα πολύ δύσκολο εγχείρημα, ακόμα δε περισσότερο αν λάβουμε υπόψη μας και το ασύρματο μέσο που είναι ένα μη-ντετερμινιστικό φυσικό μέσο δικτύου. Η ύπαρξη απαιτήσεων πραγματικού χρόνου παρ’ όλες τις δυσκολίες υπάρχει σε εφαρμογές δικτύων κινούμενων αισθητήρων και δυσκολεύει περαιτέρω την σχεδίαση μιας δομής που θα διατηρεί διασυνδεσιμότητα μεταξύ των αισθητήρων του δικτύου ενώ παράλληλα θα ικανοποιεί τις απαιτήσεις πραγματικού χρόνου. Πρόσθετα οι δυναμικές συνθήκες που παρατηρούνται σε ένα ασύρματο δίκτυο κινούμενων αισθητήρων όσον αφορά σημαντικές παραμέτρους λειτουργίας όπως μεταβλητό φορτίο εφαρμογής, ταχύτητα φυσικής κίνησης του κινούμενου αισθητήρα και αριθμός συγκέντρωσης τους στην ίδια ασύρματη περιοχή καθώς και η μη ύπαρξη σταθερής παροχής ενέργειας, δημιουργούν την ανάγκη σχεδίασης μιας ασύρματης δομής που θα έχει την δυνατότητα να προσαρμόζεται στις εκάστοτε συνθήκες του δικτύου. Υποστηρίζοντας δυνατότητα προσαρμογής στις εκάστοτε συνθήκες του δικτύου ενώ παράλληλα εξυπηρετούνται οι απαιτήσεις πραγματικού χρόνου, δημιουργείται η δυνατότητα μείωσης του προσθετόμενου πρωτοκολλικού δικτυακού φόρτου άρα και μείωση της ενεργειακής κατανάλωσης του κινούμενου αισθητήρα. Προχωρώντας περαιτέρω, η λειτουργία του πρωτοκόλλου δρομολόγησης μπορεί επίσης να βελτιστοποιηθεί ώστε να εξυπηρετεί τα δρομολογούμενα πακέτα με μεγαλύτερη επιτυχία. Η παρούσα διδακτορική διατριβή έρχεται να καλύψει την ανάγκη για τεχνικές προσαρμοστικότητας σε ασύρματα δίκτυα στις εκάστοτε συνθήκες του δικτύου και να παρουσιάσει μια πρόταση πρότυπης υλοποίησης που να βελτιστοποιεί την λειτουργία του ασύρματου δικτύου, παρακολουθώντας σε πραγματικό χρόνο κρίσιμες μεταβλητές της λειτουργίας. Τα κυριότερα αποτελέσματα της παρούσας διδακτορικής διατριβής παρουσιάζονται παρακάτω: • Μελέτη και ανάλυση της εν γένη συμπεριφοράς υπαρχόντων προτεινόμενων δομών για την δρομολόγηση σε ασύρματα κινούμενα δίκτυα αισθητήρων. • Σχεδίαση και ανάλυση πρότυπης υβριδικής δομής στηριζόμενη σε γνωστούς αποδεκτούς αλγορίθμους δρομολόγησης. • Μελέτη και ανάλυση των μεταβλητών λειτουργίας και εξαγωγή των κρίσιμων μεταβλητών μέσω των οποίων μπορεί να γίνει η αναγνώριση κατάστασης του ασύρματου δικτύου. • Σχεδίαση, ανάλυση και υλοποίηση πρότυπου αλγορίθμου ελέγχου και προσαρμογής λειτουργίας της ασύρματης δομής στις εκάστοτε συνθήκες λειτουργίας του δικτύου. • Πλήρης υλοποίηση πρότυπης δικτυακής ασύρματης αρχιτεκτονικής με δυνατότητες αναπροσαρμογής σε μεταβλητές συνθήκες δικτύου. • Λήψη και δημοσίευση πλήρους συνόλου μετρήσεων μέσω προσομοίωσης της προτεινόμενης δομής με χρήση παγκοσμίου φήμης λογισμικού προσομοίωσης δικτύων και απόδειξη της επιτυγχανόμενης βελτίωσης λειτουργίας του δικτύου. / The progress in wireless telecommunications has resulted in the creation of small sized microprocessor systems that are wireless enabled. Due to the small size of these systems, they are considered portable since they can even be carried by a person. Furthermore, the need to create large scale wireless networks using such systems, without a fixed power supply, has created the constraint of small communication range for such devices. This leads to multiple retransmissions of data packets in order to reach their final destination within the wireless network. This communication is often referred to as multihop communication. The research objective of this thesis is to propose a new wireless architecture that will provide wireless connectivity for large scale wireless ad-hoc networks without the need of central management. The problem of finding a route, or even worse, the optimal route in a wireless ad-hoc network is very difficult and gets even worse if we consider the nature of the wireless medium that is un-deterministic and probably the less predictable medium used in networks. The need of real time constraints in wireless ad-hoc networks exists however, making even more difficult the design of a wireless architecture that will provide connectivity in the domain of a wireless network while managing to succeed in satisfying the real time constraints. Furthermore the dynamic nature of a wireless mobile network as far as important functional variables are concerned, like application load, speed of node movement, rate of connectivity in the same wireless domain, as well as the lack of a fixed power supply, create the need of adaptivity support, based on network status, in any wireless module designed to address the above problems. Supporting an adaptivity functionality based on the wireless network status, while managing to meet the real time constrains imposed from the application, we manage to lower the overhead of the network protocol, hence reducing the energy consumption of the wireless node. Moving forward, the functionality of the routing protocol itself is enhanced so as to route the data packets to the destination node with higher rates of success. This dissertation manages to fulfill the need for techniques of adaptivity in wireless ad-hoc networks by presenting a new wireless architecture, that is enhancing the general behavior of a wireless network by monitoring in real time various critical network variables and change the protocols behavior to adapt to changing network condition. The more important results of this dissertation are presented below: • Study and analysis of general behavior of already existing routing protocols for ad-hoc wireless networks. • Design and analysis of a prototype hybrid module, based on existing routing algorithms. • Study and analysis of functional variables, extraction of critical functional variables that can be used to identify the status of the wireless network within a certain domain. • Design, analysis and implementation of a prototype algorithm that controls and adapts the general functionality of the wireless module based on the network status. • Implementation prototype of a wireless architecture supporting automatic real time adaptability to network status based on real time monitoring of network variables. • Collection and publication of a full set of tests by using a world wide known software tool to simulate data networks, and proof of the resulted functionality enhancement of the wireless network’s behaviour.

Thesis (MScEng (Electrical and Electronic Engineering))--University of Stellenbosch, 2011. / ENGLISH ABSTRACT: An investigation is made to find a suitable routing protocol for a millimeter wave ad hoc wireless network. It is discovered that a hierarchical routing protocol is ideal for a high node density. Due to the high bandwidth that is possibly available, with millimeter wave transmission, packets are used to keep links between nodes active and to control data packet congestion. Cluster leaders are elected and use token packets to provide nodes with more queued messages with more transmission chances, assisting the network in congestion control. Hello messages are sent frequently to keep routing information at nodes fresh and to detect broken links quickly. If a broken link is found a new route is readily available, within a second. A simulation is created to test the protocol. Changes are made to the original proactive cluster routing protocol to reduce the route length and lessen routing overhead. A theoretical model is developed to estimate the mean waiting time for a packet. Although insight is gained by modelling the latency with queueing theory it is suggested, due to the protocol’s complexity, to use other mathematical modelling techniques such as a Markov state model or a Petri net. / AFRIKAANSE OPSOMMING: Ondersoek word ingestel na ’n geskikte roete protokol vir ’n millimeter golflengte ad hoc radio pakkie netwerk. Daar word gevind dat ’n hi¨erargiese kluster roete protokol ideaal is vir ’n ho¨e digtheid van nodusse. As gevolg van die ho¨e bandwydte, wat moontlik beskikbaar is met millimeter golflengte transmissie, word pakkies gebruik om kommunikasie skakels tussen nodes in stand te hou en data pakkie verkeersopeenhoping te beheer. Kluster leiers word verkies en gebruik teken-pakkies om nodes met ’n groter data pakkie las meer transmissie kanse te gee. Sodoende word die verkeersopeenhoping van data pakkies verminder. Hallo pakkies word gereeld gestuur om die roete inligting vars te hou en gebroke kommunikasie skakels vinnig op te spoor. As ’n gebroke skakel gevind word, word ’n alternatiewe roete vinnig opgestel, binne ’n sekonde. ’n Simulasie word opgestel om die protokol te toets. Veranderinge aan die oorspronklike proaktiewe kluster protokol word aangebring om roete lengte te verklein en oorhoofse roete inligting kommunikasie te verminder. ’n Teoretiese model gebasseer op tou-staan teorie word ontwikkel om die wagtyd van ’n pakkie te bepaal. Alhoewel, insig verkry is deur die protokol te analiseer deur middel van tou-staan teorie, word daar voorgestel, as gevolg van die protokol se kompleksiteit, om eerder ander wiskundige modelleeringstegnieke te gebruik soos ’n Markov toestands model of ’n Petri net.

Made available in DSpace on 2015-05-14T12:36:57Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2319492 bytes, checksum: 7322dcd074c1c36c3d7750aad585ca51 (MD5) Previous issue date: 2010-03-26 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The increasing popularity and demand of wireless networks, over the past few years, has led to new challenges that stimulate the development of technology to build better standards and protocols. In such a context arises the Wireless Mesh Networks (WMN) which are low cost, self-organized and self-configurable networks that are easy to deploy and are fault tolerant. The WMN are aiming to achieve better performance, greater reliability and flexibility when compared to other wireless networks. These networks can provide an infrastructure consisting of dedicated devices for routing, strategically placed to achieve adequate coverage, providing connectivity within the coverage area for mobile clients. Therefore, these networks need to adapt to topology changes that can occur at any time. To allow this adjustment a routing protocol is required. An important component of a proactive routing protocol is a network topology discovery protocol, which disseminates link-state updates messages over the network. The proactive protocols usually have a high message overhead. However, a high message overhead has a major impact on the performance of a routing protocol and can lead to scalability problems. In such a context, the main contribution of this work is to build a reliable link-state dissemination protocol, called MLSD specially designed for RMSF whose goals are to reduce the messages overhead and reduce the total messages sent to advertise topology changes. / O aumento da popularidade e da demanda das redes sem fio ao longo dos últimos anos tem levado a novos desafios que estimulam o desenvolvimento da tecnologia na busca de melhores padrões e protocolos. Neste contexto, surgem as Redes em Malha Sem Fio - RMSF (Wireless Mesh Networks WMN), que são redes de baixo custo, que tem a capacidade de se organizar e se configurar automaticamente, de fácil implantação e com capacidade de tolerância a falhas. As RMSFs buscam alcançar melhor desempenho, maior confiabilidade e flexibilidade quando comparadas a outras redes sem fio. Estas redes podem fornecer uma infraestrutura formada por dispositivos dedicados à tarefa de roteamento, com seu posicionamento planejado para obter cobertura satisfatória, proporcionando conectividade dentro da área de cobertura para os clientes móveis. Por isto, estas redes precisam se adaptar a alterações de topologia, que podem ocorrer a todo o momento. Para permitir esta adaptação é necessário um protocolo de roteamento. Um componente importante de um protocolo de roteamento proativo é um protocolo de descoberta de topologia da rede, no qual as modificações na topologia da rede são divulgadas através de mensagens de atualização. Entretanto, protocolos proativos possuem uma alta carga de mensagens. Uma carga elevada de mensagens tem grande impacto no desempenho do protocolo de roteamento e podem levar a problemas de escalabilidade. Neste contexto, a principal contribuição deste trabalho é a construção de um protocolo de divulgação dos estados dos enlaces com garantia de entrega, chamado Mesh Network Link State Dissemination Protocol - MLSD, projetado para RMSFs, cujos objetivos são reduzir a carga de mensagens de atualização na rede e reduzir o total de mensagens enviadas para divulgar as atualizações.

Les travaux réalisés dans cette thèse se situent dans le domaine des réseaux de capteurs sans fil (Wireless Sensor Networks), déployés en environnement urbain et se focalisent sur la sécurité des protocoles de routage multi-sauts. Les capteurs sont souvent déployés dans des environnements ouverts et accessibles permettant aux éventuels attaquants de les détruire ou de les capturer afin d'en extraire les données sensibles (clés de chiffrement, identité, adresse, etc.). Les méthodes traditionnelles, basées sur la cryptographie, permettent d'obtenir une sécurité de base (authentification, confidentialité, intégrité, non répudiation etc.), mais ne permettent pas toujours de se prémunir contre les attaques dues à la compromission des nœuds (réplication des nœuds, Sybil, Selective forwarding, Blackhole, Sinkhole, Wormhole etc.). Dans le but d'apporter des solutions algorithmiques complémentaires aux solutions cryptographiques, nous étudions la résilience des protocoles de communication en présence d'adversaires internes visant à perturber l'acheminement de l'information à travers le réseau. Dans un premier temps, nous introduisons la notion de résilience et une métrique quantitative doublée d'une représentation qualitative pour mieux l'appréhender. Nous étudions les principaux protocoles de routage de la littérature selon notre métrique pour montrer leur capacité d'être résilients. Cette étude nous permet de proposer trois mécanismes visant à développer la résilience: (i) l'introduction de comportements aléatoires, (ii) la limitation de la longueur des routes et (iii) la réplication de paquets. Nous appliquons ces mécanismes aux protocoles classiques et nous les étudions selon notre métrique. Pour confirmer les résultats de simulations, nous proposons enfin un travail théorique pour mesurer analytiquement la résilience en nous basant sur le modèle des marches aléatoires biaisées. / This thesis focuses on the security issues of multi-hop routing protocols for Wireless Sensor Networks (WSNs). The rapid deployment capabilities, due to the lack of infrastructure, as well as the self organized and potentially fault-tolerant nature of WSNs make them attractive for multiple applications spanning from environmental monitoring (temperature, pollution, etc.) to building industrial automation (electricity/gas/water metering, event detection, home automation etc). Security is particularly challenging in WSNs. Because of their open and unattended deployment, in possibly hostile environments, powerful adversaries can easily launch Denial-of-Service (Dos) attacks, cause physical damage to sensors, or even capture them to extract sensitive information (encryption keys, identities, addresses etc.). After node compromise, an adversary can seek to disrupt the functionality of network layer by launching attacks such as node replication, Sybil, Selective forwarding, Sinkhole, Wormhole etc. To cope with these "insider" attacks, stemming from node compromise, "beyond cryptography" algorithmic solutions must be envisaged to complement the traditional cryptographic solutions. Firstly, we propose the resiliency concept including our definition and a new metric to compare routing protocols. This method allows to aggregate meaningfully several parameters (quantitative information) and makes it easier to visually discern various tradeoffs (qualitative information), thus greatly simplifying the process of protocol comparison. Secondly, we propose the protocol behaviors enhancing resiliency. Our proposition consists in three strategies: (i) introduce random behaviors (ii) limit route length (iii) introduce data replication. These mechanisms are applied to several well known routing protocols to study their resiliency. Finally, a theoretical study of resiliency is introduced. We present an analytical study of biased random walks under attacks to confirm the results obtained through simulations.