Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho propõe uma nova métrica denominada AP (Alternative Path), a ser utilizada para o cálculo de rotas em protocolos de roteamento em redes em malha sem fio. Esta métrica leva em consideração a interferência causada por nós vizinhos na escolha de uma rota para um destino. O desempenho da métrica AP é avaliado e comparado com o da métrica ETX (Expected Transmission Count) e com o da métrica número de saltos (Hop Count). As simulações realizadas mostram que a métrica AP pode propiciar desempenho superior à rede quando comparada com as outras duas métricas. A métrica AP apresenta melhor desempenho em cenários com maior diversidade de caminhos alternativos. / This work proposes a new metric, AP (Alternative Path), to be used in the calculation of routes in wireless mesh network routing protocols. This new metric takes into account the interference caused by neighbor nodes when choosing a route for a destination. The performance of the AP metric is evaluated and compared to the ETX (Expected Transmission Count) and Hop count metrics. Simulations show that AP can provide superior performance to the network when compared with the other two metrics. The AP metric shows a better performance in networks with a wider variety of alternative paths.

Mobile Ad-hoc Network (MANET) is a group of mobile devices that can form a network, interconnect and share resources without the use of any fixed network infrastructure or centralised management. MANET is exposed to security attacks because of its fundamental characteristics such as open medium, dynamic topology and lack of central monitoring. The black hole attack is one example of the attacks MANET is exposed to. In black hole attack, a malicious node misleadingly claims to have an updated route to the destination node, absorbs and drops the packets that are supposed to be forwarded to the destination node. The common MANET reactive routing protocols are Ad-hoc on-demand Distance Vector (AODV) and Dynamic Source Routing (DSR). These protocols are easily attacked by the black hole during the route discovery process. This research therefore studies black hole attack in detail and assesses the performance of AODV and DSR under black hole attack. The work is achieved by simulating the two protocols under regular operation and under black hole attack using Network Simulator 2 (NS-2). The protocols are analysed using packet delivery ratio, throughput and end-to-end delay as performance metrics. The research further compares the black hole attack solutions that have been previously proposed and determines the solution that performs better than others. The simulation results show that MANET under normal operating environment out performs MANET attacked by black hole, and that AODV is more vulnerable to black hole attack than DSR. The comparison study of the existing black hole attack solutions show that SAODV is the best effective black hole attack removal technique. But when considering the solution that brings no negative impact to the normal operation of the network, IDSAODV is the best solution. / Computing / M. Sc. (Computer Science)

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho propõe uma nova métrica denominada AP (Alternative Path), a ser utilizada para o cálculo de rotas em protocolos de roteamento em redes em malha sem fio. Esta métrica leva em consideração a interferência causada por nós vizinhos na escolha de uma rota para um destino. O desempenho da métrica AP é avaliado e comparado com o da métrica ETX (Expected Transmission Count) e com o da métrica número de saltos (Hop Count). As simulações realizadas mostram que a métrica AP pode propiciar desempenho superior à rede quando comparada com as outras duas métricas. A métrica AP apresenta melhor desempenho em cenários com maior diversidade de caminhos alternativos. / This work proposes a new metric, AP (Alternative Path), to be used in the calculation of routes in wireless mesh network routing protocols. This new metric takes into account the interference caused by neighbor nodes when choosing a route for a destination. The performance of the AP metric is evaluated and compared to the ETX (Expected Transmission Count) and Hop count metrics. Simulations show that AP can provide superior performance to the network when compared with the other two metrics. The AP metric shows a better performance in networks with a wider variety of alternative paths.

La multiplication de l'usage des équipements connectables à un réseau sans fil tels que les smartphones ou les objets connectés peut être mise à profit pour construire des réseaux reposant sur des communications de proximité : les appareils communiquent directement entre eux, sans le support d'une infrastructure centrale. On parle de réseau ad hoc. Ce type de réseau sans infrastructure est exploité dans de nombreux domaines comme le militaire ou la gestion de catastrophes naturelles. Pour certains cas d'utilisation, le passage à l'échelle, c'est-à-dire la capacité à fonctionner avec la croissance de la taille du réseau, est une propriété indispensable. Dans cette thèse, nous nous intéressons à la problématique du routage sous l'aspect du passage à l'échelle. Le routage est la fonction responsable de l'acheminement des données au sein du réseau. Pour cela, des informations de contrôle sont échangées entre les nœuds du réseau. Mais le trafic associé à ces échanges peut être un frein pour passer à l'échelle. Afin de le réduire, nous proposons d'agréger les informations concernant des nœuds géographiquement proches. Dans un premier temps, nous mettons en place une structuration de la zone de déploiement du réseau en régions hiérarchiques. Ces régions servent d'agrégateur de nœuds à travers un adressage de ces derniers selon les régions auxquelles ils appartiennent. Par la suite, nous proposons un protocole de routage combinant les approches topologique et géographique. Il s'agit, pour un nœud donné, de maintenir des routes menant, d’une part, vers d'autres nœuds dans un voisinage proche et, d'autre part, vers des zones géographiques de plus en plus étendues au fur et à mesure de l'éloignement. Cette dernière propriété est obtenue en profitant de la structuration hiérarchique précédente des zones d'agrégation. Les résultats montrent la faculté de notre proposition à monter à grande échelle par rapport aux protocoles de routage ad hoc classique et aussi sa capacité à adresser les problèmes propres aux protocoles de routage purement géographique. / The widespread use of wireless devices such as smartphones and connected objects leads to an increasing emergence of infrastructure-less networks relying on device-to-device communication: ad hoc networks. Applications of this type of network vary widely from military operations to emergency situations. Scalability is a key property for some use cases involving a large number of devices, also called nodes. We mean by scalability, the ability of the network to increase in size without drastic loss of performance and with a cost-effective network maintenance. In this thesis, we focus on the scalability from a routing perspective. Routing handles the delivery of data packets from a source to a destination across the network. This is achieved by the exchange of information between nodes. The corresponding traffic may represent a break for scalability in presence of numerous nodes. In this work, we propose an aggregation of routing information. First, we partition the deployment area into smaller hierachical regions based on geographical coordinates. Nodes are assigned hierachical address depending on the regions they are located in. Then, we propose a mixed topological and geographical-based routing protocol. A node maintains precise routing information to other nodes in close proximity and geographically aggregate information for nodes at greater distances. Regions are the units of nodes aggregation. The further the nodes are, the larger the regions referring to them are. The results show that our proposition outperforms regular ad hoc routing in terms of scalability and addresses more efficiently geographical routing-related issues compared to classical geographical routing.

Nous nous intéressons dans ce travail au guidage optimal des usagers dans un réseau routier. Plus précisément, nous nous focalisons sur les stratégies adaptatives de guidage avec des garanties en termes de fiabilité des temps de parcours, et en termes de robustesse de ces stratégies. Nous nous basons sur une approche stochastique où des distributions de probabilités sont associées aux temps de parcours sur les liens du réseau. Le guidage est adaptatif et individuel. L'objectif de ce travail de recherche est le développement de stratégies « robustes » de guidage des usagers dans un réseau de transport routier. Une stratégie de guidage d’un nœud origine vers un nœud destination est dite robuste, ici, si elle minimise la détérioration de sa valeur maximale calculée au départ de l’origine, contre d’éventuelles reconfigurations du réseau dues à des coupures de liens (accidents, travaux, etc.) La valeur de la stratégie de guidage est maximisée par rapport à la moyenne et à la fiabilité des temps de parcours associées à la stratégie. Deux principales parties sont distinguées dans ce travail. Nous commençons par l’aspect statique du guidage, où la dynamique du trafic n’est pas prise en compte. Nous proposons une extension d’une approche existante de guidage, pour tenir compte de la robustesse des itinéraires calculés. Dans une deuxième étape, nous combinons notre nouvel algorithme avec un modèle microscopique du trafic pour avoir l’effet de la dynamique du trafic sur le calcul d’itinéraires robustes / In this work, we are interested in the optimal guidance of users on road networks. More precisely, we are focused on the adaptive strategies of guidance with guarantees in terms of the travel time reliability and in terms of the robustness of the strategies. We base here on a stochastic approach, where probability distributions are associated to travel times on the links of the network. The guidance is adaptive and user-based. The objective of this work is the development of "robust" strategies for user guidance in a road network. A guidance strategy is said to be robust, here, if it minimizes the deterioration of its maximum value calculated at the origin, against eventual reconfigurations of the network due to link failures (accidents, works, etc.) The value of a guidance strategy is maximized with respect to the mean travel time and its reliability. Two main parts are distinguished in this work. We start with the static aspect of the guidance, where the traffic dynamics are not taken into account. We propose an extension of an existing guidance approach, to take into account the robustness of the calculated itineraries. In a second step, we combine our new guidance algorithm with a microscopic traffic model in order to have the effect of the traffic dynamics on the robust route calculation

In this study, three different algorithms are implemented to solve thecapacitated vehicle routing problem with and without time windows:ant colony optimization, a genetic algorithm and a genetic algorithmwith self-organizing map. For the capacitated vehicle routing problemthe Augerat et al’s benchmark problems were used and for the capaci-tated vehicle routing problem with time windows the Solomon’sbenchmark problems. All three algorithms were tuned over thirtyinstances per problem with the tuners SPOT and ParamILS. The tuningresults from all instances were combined to the final parameter valuesand tested on a larger set of instances. The test results were used tocompare the algorithms and tuners against each other. The ant colonyoptimization algorithm outperformed the other algorithms on bothproblems when considering all instances. The genetic algorithm withself-organizing map found more best known solutions than any otheralgorithm when using parameters, on the capacitated vehicle routingproblem. The algorithms performed well and several new best knownresults were discovered for the capacitated vehicle routing problem andnew best solutions found by heuristics were discovered for the 100customer Solomon problems. When comparing the tuners they bothworked well and no clear winner emerged.

Battery powered wireless sensors are widely used in industrial and regulatory monitoring applications. This is primarily due to the ease of installation and the ability to monitor areas that are difficult to access. Additionally, they can be left unattended for long periods of time. However, there are many challenges to successful deployments of wireless sensor networks (WSNs). In this thesis we draw attention to two major challenges. Firstly, with a view to extending network range, modern WSNs use mesh network topologies, where data is sent either directly or by relaying data from node-to-node en route to the central base station. The additional load of relaying other nodes’ data is expensive in terms of energy consumption, and depending on the routes taken some nodes may be heavily loaded. Hence, it is crucial to locate routes that achieve energy efficiency in the network and extend the time before the first node exhausts its battery, thus improving the network lifetime. Secondly, WSNs operate in a dynamic radio environment. With changing conditions, such as modified buildings or the passage of people, links may fail and data will be lost as a consequence. Therefore in addition to finding energy efficient routes, it is important to locate combinations of routes that are robust to the failure of radio links. Dealing with these challenges presents a routing optimisation problem with multiple objectives: find good routes to ensure energy efficiency, extend network lifetime and improve robustness. This is however an NP-hard problem, and thus polynomial time algorithms to solve this problem are unavailable. Therefore we propose hybrid evolutionary approaches to approximate the optimal trade-offs between these objectives. In our approach, we use novel search space pruning methods for network graphs, based on k-shortest paths, partially and edge disjoint paths, and graph reduction to combat the combinatorial explosion in search space size and consequently conduct rapid optimisation. The proposed methods can successfully approximate optimal Pareto fronts. The estimated fronts contain a wide range of robust and energy efficient routes. The fronts typically also include solutions with a network lifetime close to the optimal lifetime if the number of routes per nodes were unconstrained. These methods are demonstrated in a real network deployed at the Victoria & Albert Museum, London, UK.

The number of potential applications for wireless sensor networks is immense. These networks may consist of large numbers of low cost, low power, disposable sensor nodes that can be deployed inside or close to phenomena to be monitored. The nature of these networks necessitates specific design requirements, of which energy efficiency is paramount. The limited available energy of sensor nodes is mainly drained during communication and computational processing. An energy efficient routing protocol can limit the number of message transmissions and the computational complexity of finding routing paths. Many routing protocols have been proposed for wireless sensor networks. Most of them are computationally complex, require a large number of messages to be transmitted or require that sensor nodes possess certain hardware capabilities in order to function. The objective of this dissertation was to develop a Simple Energy Efficient Routing (SEER) protocol for wireless sensor networks that is computationally simple, reduces the number of transmitted messages and does not impose any hardware prerequisites. The new routing protocol, which was developed during this research, uses a flat network structure for scalability and source initiated communication along with event-driven reporting to reduce the number of message transmissions. Computational simplicity is achieved by using a simple method for routing path selection. The SEER protocol selects the next hop for a message by choosing a neighbour that has a smaller or equal hop count to the current node. If multiple neighbours satisfy this requirement, the neighbour with the highest remaining energy is chosen as the next hop. Each node in the network has a table containing the hop count and remaining energy of each of its neighbours. Periodic messages sent through the network update these neighbour tables. SEER uses a novel approach to select the next hop of a message during routing. The protocol increases the lifetime of the network dramatically, compared to other similar routing protocols. This improvement is directly related to the reduction in the number of transmissions made by each node. The simplicity of the protocol reduces the required computational processing compared to other protocols, and at the same time makes this one of the few available protocols that does not impose hardware requirements on nodes in order to function. / Dissertation (MEng (Computer Engineering))--University of Pretoria, 2007. / Electrical, Electronic and Computer Engineering / unrestricted

No description available.

Syfte: Att undersöka de potentiella fördelarna vid implementering av Lean-baserade metoder för att möta prestanda, tillgänglighet och effektivitet i transportsystemet samt användningen av en varuflödesplan för att identifiera slöseri. Vidare, att observera hur fördelarna med en ruttoptimering kan minimera slöseri och reducera kostnader relaterade till transport samt minskningen av miljöutsläpp, stadsbuller och säkerhet. Metod och genomförande: För att uppnå syftet med denna studie och att besvara forskningsfrågorna har en fallstudie och en litteraturstudie kombinerats och genomförts. Fallstudien innehåller observationer och intervjuer som har genomförts för att samla in information om hur fallföretaget arbetar med transport dagligen, användningen av standardisering och effektivisering samt hantering av ruttplanering. Vidare har en implementering utförts av de föreslagna ruttoptimeringsmetoderna för att få större förståelse för de föreslagna metoderna och litteraturen. Slutligen har en analys och diskussion genomförts där de empiriska resultaten studerats och jämförts med litteraturstudien. Resultat: Genomförandet av Lean-baserade metoder för att identifiera och minska slöseri baserat på prestationsmätningsverktyg, såsom värdeflödekartläggning och användningen av ruttoptimering, har visat flera fördelar. De identifierade fördelarna var kortare körtider för chaufförerna, en minskad total kilometersträcka, en mer optimerad fyllnadsgrad i lastbilarna samt mer effektiv tid vid lastning och lossning av gods. Den sistnämna fördelen påverkar främst tillgängligheten och prestandan av den totala fordon- och chaufförseffektiviteten. En del av fördelarna var tolkbara i monetära termer för att ge insikt om hur de eventuella kostnadsbesparingarna. Rekommendationer: För att få bättre och mer djupgående resultat i framtida studier, föreslås att: fallföretaget kartlägger alla transporter som utförs för att bedöma lönsamheten i vissa körrutter samt för att undersöka hur all transport kan uppdelas geografiskt med hjälp av presenterat material i denna studie; noggrannare observationer av förare under andra veckodagar för att identifiera ytterligare problemområden och förbättringsmöjligheter; standardisera och implementera Lean metoder i närliggande processer i verksamheten för fortsatt strävan efter en lönsam verksamhet, till exempel genom att granska mottagandet av varor från leverantörer och utvärdera möjligheten med att ha lokala leverantörer; slutligen, all personal ska utbilda sig inom Lean och standardiserat arbete för att ytterligare eliminera och minska interna NIT-aktiviteter, såsom väntetid. / Purpose: To explore the possible benefits with the implementation of Lean methods to measure performance, availability and efficiency in transportation, including the use of a value stream map to identify waste. Furthermore, to observe how the benefits with a route optimization eventually can minimize waste and reduce costs related to transportation as well as the reduction of environmental emissions, urban noise and security. Methodology: To achieve the purpose of this study and to solve the research questions, a case study and a literature study has been combined and carried out. The case study contains observations and interviews which has been executed in order to gather information related to how the case-company work with transportation on a daily basis, the usage of standardization and the management of route planning. Moreover, an implementation of the proposed route optimizations has been executed with the purpose of gaining knowledge related to the outcome. Finally, an analysis and discussion has been performed where the empirical results are studied and compared with the literature findings. Findings: The implementation of Lean methods to identify and reduce waste based on performance measuring tools, such as value stream mapping and the use of route optimization, showed several advantages. The identified advantages were shorter driving schedules for the chauffeurs, a reduced overall mile distance, a more optimal degree of filling in the driver trucks and more efficient time spent while loading and unloading the trucks. The last advantage mainly affecting the availability and performance of the overall vehicle efficiency. Some of the advantages were interpretable into monetary terms in order to provide an insight into any cost savings. Recommendations: To gain better and more profound results in any further studies, it is suggested that: the case company map out all transports carried out in order to assess the profitability of certain driving routes, as well as to examine how all transport can be geographically divided using the presented material in this study; more thorough observations of drivers during other weekdays to further identify problem areas and improvement opportunities ought to be done; standardization and implementation of Lean methods in related processes in the company for continued pursuit of profitable operations. For example, by reviewing the receipt of goods from suppliers and reviewing the option of having local suppliers; lastly, all staff gets training and education of Lean methods and standardized work for additional elimination and reduction of internal NIT activities, such as waiting time.