Το πρόβλημα εύρεσης συντομότερων διαδρομών είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε αυτό το πρόβλημα αναζητείται η συντομότερη διαδρομή μεταξύ δύο δεδομένων σημείων ελαχιστοποιώντας ένα κριτήριο κόστους. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην εύρεση διαδρομών σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει εκτός από την διανυμένη απόσταση και η ελαχιστοποίηση του χρόνου και του κόστους. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές τις περιπτώσεις η καλύτερη λύση δεν μπορεί να οριστεί με μονοσήμαντο τρόπο, και συνεπώς καταφεύγουμε σε αντισταθμίσεις μεταξύ των παραγόντων, που είναι γνωστές ως σύνολο λύσεων κατά Pareto. Παρόλο που για το πρόβλημα μονοκριτηριακής εύρεσης συντομότερων διαδρομών υπάρχουν πολλοί αποδοτικοί αλγόριθμοι για την επίλυση του προβλήματος, το αντίστοιχο πολυκριτηριακό πρόβλημα είναι πολύ πιο σύνθετο. Μέχρι τώρα, αυτό το πρόβλημα έχει αποδειχθεί ότι είναι NP-πλήρες. Επιπλέον, έχει αποδειχθεί ότι το πλήθος των λύσεων σε αυτό το πρόβλημα αυξάνεται εκθετικά σε σχέση με το μέγεθος της εισόδου. Υπάρχουν δύο βασικές προσεγγίσεις επίλυσης τέτοιων προβλημάτων, όπου εξετάζονται πολλαπλά κριτήρια. α) Η πρώτη μέθοδος βρίσκει προσεγγιστικές λύσης κατά έναν ορισμένο παράγοντα. Οι προσεγγιστικές μέθοδοι δεν βρίσκουν απαραίτητα ακριβείς λύσεις, αλλά είναι σχετικά γρήγορες και προσφέρουν εγγύηση για το ποσοστό απόκλισης από την βέλτιστη λύση. β) Η δεύτερη μέθοδος χρησιμοποιεί ευρετικές βελτιώσεις για να επιταχύνει τους ήδη υπάρχοντες αλγορίθμους. Τέτοιες τεχνικές βρίσκουν ακριβείς λύσεις, και το ζητούμενο είναι να επιτευχθεί μια πολύ καλή χρονική απόδοση. Στην παρούσα διπλωματική εργασία επικεντρωνόμαστε στην δεύτερη μέθοδο, υποκινούμενοι από την μεγάλη ζήτηση πρακτικών εφαρμογών για εύρεση αποτελεσματικής και ακριβούς λύσης του προβλήματος συντομότερων διαδρομών υπό πολλαπλά κριτήρια. Πιο συγκεκριμένα, στην εργασία αυτή παρουσιάζουμε ένα ενοποιημένο πλαίσιο για την αποδοτική επίλυση αυτών των προβλημάτων. Προτείνουμε νέες μεθόδους ή βελτιώσεις των υπαρχόντων. Υλοποιήσαμε τις μεθόδους που παρουσιάζουμε συνοδεύοντάς τις με μια εκτενή πειραματική μελέτη πάνω σε δίκτυα ευρείας κλίμακας. / We present new implementations of heuristic algorithms for the solution of the multiobjective shortest path problem, using a new graph structure specifically suited for large scale road networks. We enhance the heuristics with further optimizations and experimentally evaluate the performance of our enhanced implementation on real world road networks achieving 10 times better performance with respect to the best previous study.

A busca de soluções para a mobilidade urbana que minimizem a agressão do setor de tráfego e transportes ao meio ambiente está cada vez maior. Os veículos elétricos se posicionam como uma alternativa interessante, pois reduzem a emissão de gases poluentes na atmosfera, a poluição sonora e o consumo de petróleo. No entanto, sua limitada autonomia e a escassez de postos de recarga intimidam sua adoção. Por conta disso, políticas governamentais de incentivo têm sido desenvolvidas para a oferta de benefícios a quem optar por um veículo elétrico. Estima-se que dentro de poucas décadas toda a frota urbana será substituída por veículos dessa natureza. Por isso, é importante entender as mudanças no tempo de viagem e no consumo de energia oriundos da inclusão de veículos elétricos em cenários de tráfego. Trabalhos anteriores estudaram as diferenças entre os mecanismos internos de veículos convencionais e elétricos na determinação destas mudanças. Porém, dadas as características destes últimos, motoristas de veículos elétricos se preocupam com a economia de energia e podem optar por rotas diferentes. Logo, uma análise completa destes impactos deve considerar uma nova distribuição de tráfego. Este trabalho propõe um método biobjetivo de alocação de tráfego que considera o tempo de viagem e o consumo de energia para determinar a distribuição de veículos elétricos em cenários de tráfego urbano. Duas estratégias de distribuição de fluxo são propostas como mecanismos de escolha de rotas. Como parte da alocação de tráfego, é proposto um algoritmo biobjetivo de caminhos mínimos para veículos elétricos. A abordagem apresentada foi aplicada a três cenários distintos, onde percebeu-se uma diminuição de até 80% no consumo total de energia. Em cenários com congestionamento, observou-se um aumento de 10% no tempo de viagem. Já em cenários sem congestionamento o tempo de viagem diminuiu cerca de 2%. A recuperação de energia representa quase 6% da economia total dos veículos elétricos. Além disso, experimentos mostraram que investimentos na eficiência dos veículos elétricos podem resultar em uma economia de até 15% de energia. / The search for urban mobility solutions that minimize the aggression to the environment is increasing. Electric vehicles are an attractive alternative because they reduce greenhouse gas emissions, noise pollution, and oil consumption. However, their limited autonomy and the lack of charging stations restrict their popularization. Therefore, government incentive policies have been developed in order to offer benefits to those who choose an electric vehicle. It is estimated that the entire urban fleet will be replaced by these vehicles in a few decades. Therefore, it is important to understand the changes in travel time and energy consumption from the inclusion of electric vehicles in traffic scenarios. Previous works determined these changes by studying the differences between the internal engine of conventional and electric vehicles. However, given the characteristics of the latter, drivers of electric vehicles care about saving energy and may want to choose different routes. Thus, a complete analysis of these impacts should consider a redistribution of traffic. This work proposes a bi-objective traffic assignment method that considers the travel time and the energy consumption to determine the distribution of electric vehicles in urban traffic scenarios. We introduce two strategies for flow distribution as models of route choice. As a procedure of the traffic assignment method, we propose a bi-objective shortest path algorithm for electric vehicles. Our approach was applied to three different scenarios, which resulted in a decrease of up to 80% in total energy consumption. In congested scenarios, we observe an increase of about 10% in average travel time. In uncongested scenarios, travel time decreases about 2%. Energy recovery is almost 6% of the total savings of electric vehicles. Moreover, experiments have shown that investments in the efficiency of electric vehicles can result in up to 15% of energy savings.

XML documents and related technologies represent one of the most widespread ways how data on the Web are maintained and interchanged. Unfortunately, many of the real-world documents contain various types of consistency issues that prevent their successful automated processing. In this thesis we focus on the problem of the structural invalidity and its correction. In particular, having one potentially invalid XML document modeled as a tree, and a schema in DTD or XML Schema languages modeled as a regular tree grammar, our goal is to find all the minimal corrections of this tree. The model we proposed builds on top of the recursively nested structures of correction multigraphs, where the shortest paths are being found. For this purpose we formally introduce three correction strategies with different pruning optimizations applied. According to the experiments we performed, the refinement correction strategy not only significantly outperforms all the other existing approaches, but also guarantees important characteristics the others cannot. Powered by TCPDF (www.tcpdf.org)

ARARUMA Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T19:26:26Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T13:35:18Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-07-13T13:35:18Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.

A busca de soluções para a mobilidade urbana que minimizem a agressão do setor de tráfego e transportes ao meio ambiente está cada vez maior. Os veículos elétricos se posicionam como uma alternativa interessante, pois reduzem a emissão de gases poluentes na atmosfera, a poluição sonora e o consumo de petróleo. No entanto, sua limitada autonomia e a escassez de postos de recarga intimidam sua adoção. Por conta disso, políticas governamentais de incentivo têm sido desenvolvidas para a oferta de benefícios a quem optar por um veículo elétrico. Estima-se que dentro de poucas décadas toda a frota urbana será substituída por veículos dessa natureza. Por isso, é importante entender as mudanças no tempo de viagem e no consumo de energia oriundos da inclusão de veículos elétricos em cenários de tráfego. Trabalhos anteriores estudaram as diferenças entre os mecanismos internos de veículos convencionais e elétricos na determinação destas mudanças. Porém, dadas as características destes últimos, motoristas de veículos elétricos se preocupam com a economia de energia e podem optar por rotas diferentes. Logo, uma análise completa destes impactos deve considerar uma nova distribuição de tráfego. Este trabalho propõe um método biobjetivo de alocação de tráfego que considera o tempo de viagem e o consumo de energia para determinar a distribuição de veículos elétricos em cenários de tráfego urbano. Duas estratégias de distribuição de fluxo são propostas como mecanismos de escolha de rotas. Como parte da alocação de tráfego, é proposto um algoritmo biobjetivo de caminhos mínimos para veículos elétricos. A abordagem apresentada foi aplicada a três cenários distintos, onde percebeu-se uma diminuição de até 80% no consumo total de energia. Em cenários com congestionamento, observou-se um aumento de 10% no tempo de viagem. Já em cenários sem congestionamento o tempo de viagem diminuiu cerca de 2%. A recuperação de energia representa quase 6% da economia total dos veículos elétricos. Além disso, experimentos mostraram que investimentos na eficiência dos veículos elétricos podem resultar em uma economia de até 15% de energia. / The search for urban mobility solutions that minimize the aggression to the environment is increasing. Electric vehicles are an attractive alternative because they reduce greenhouse gas emissions, noise pollution, and oil consumption. However, their limited autonomy and the lack of charging stations restrict their popularization. Therefore, government incentive policies have been developed in order to offer benefits to those who choose an electric vehicle. It is estimated that the entire urban fleet will be replaced by these vehicles in a few decades. Therefore, it is important to understand the changes in travel time and energy consumption from the inclusion of electric vehicles in traffic scenarios. Previous works determined these changes by studying the differences between the internal engine of conventional and electric vehicles. However, given the characteristics of the latter, drivers of electric vehicles care about saving energy and may want to choose different routes. Thus, a complete analysis of these impacts should consider a redistribution of traffic. This work proposes a bi-objective traffic assignment method that considers the travel time and the energy consumption to determine the distribution of electric vehicles in urban traffic scenarios. We introduce two strategies for flow distribution as models of route choice. As a procedure of the traffic assignment method, we propose a bi-objective shortest path algorithm for electric vehicles. Our approach was applied to three different scenarios, which resulted in a decrease of up to 80% in total energy consumption. In congested scenarios, we observe an increase of about 10% in average travel time. In uncongested scenarios, travel time decreases about 2%. Energy recovery is almost 6% of the total savings of electric vehicles. Moreover, experiments have shown that investments in the efficiency of electric vehicles can result in up to 15% of energy savings.

ARARUNA, Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 88 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-01T19:53:59Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-01T19:54:22Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-06-01T19:54:22Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.

Les travaux effectués dans cette thèse industrielle concernent l'amélioration du calculateur d'itinéraire de Cityway, société spécialisée dans les technologies de l’information appliquées à la mobilité.Nous avons d'abord établi un état de l'art exhaustif, accompagné d'une mise en perspective de l'existant Cityway avec celui-ci. Cela nous a permis d'aider l'entreprise à prendre du recul sur son produit et de justifier les axes de recherche choisis pour nos travaux.Nous nous sommes ensuite intéressés à l'aspect multicritère du problème. En effet, le calculateur, basé sur l'algorithme de Dijkstra, permet de trouver des trajets minimisant une somme pondérée de critères. Nous avons développé un algorithme multilabel permettant de conserver et étendre plusieurs labels au même nœud. Malgré une légère augmentation des temps de calculs, des résultats satisfaisants ont été obtenus dans une application bicritère de ce nouvel algorithme.Nous avons également travaillé sur la génération et la sélection de trajets alternatifs. La génération s'appuie sur les algorithmes monolabel ou multilabel. La sélection s'appuie quant à elle sur la définition d'une distance entre les solutions et des méthodes de regroupement.Enfin, nous nous sommes intéressés à l'optimisation du calcul du critère lexicographique de durée minimale dans le cas bicritère. Pour qu'un trajet soit intéressant, il faut qu'il soit optimal sur les critères usuels, mais aussi qu'il dure le moins longtemps possible. L'utilisation de certaines propriétés sur ce critère permet de réduire des temps de calcul initialement trop longs. / The work carried out in this industrial PhD aims at improving the route planner of Cityway, a company specialized in information technologies applied to mobility. We first established an exhaustive state of the art, and compared it to the existing Cityway product. This allowed us to help the company take a step back from its urgent needs, and justify the research guidelines chosen for our work.We then looked at the multi-criteria aspect of the problem. Indeed, the trip planner, based on the Dijkstra algorithm, makes it possible to find paths minimizing a weighted sum of criteria. We have developed a multilabel algorithm to maintain and extend multiple labels at the same node. Despite a slight increase in computation time, satisfactory results were obtained in a bicriteria application of this new algorithm.We also worked on the generation and selection of alternative routes. The generation algorithm relies on the existing monolabel or newly developed multilabel algorithms. The selection algorithm is based on the definition of a distance between trips and adaptations of existing clustering algorithms to this specific case.Finally, we were interested in what we called the lexicographic criterion. For a trip to be interesting, it must be optimal on the usual criterion of earliest arrival, and, for trips arriving at the same time, on the latest departure criterion. The use of certain properties on this criterion makes it possible to reduce computation times on the bicriteria case.

abstract: The shortest path between two locations is important for spatial analysis, location modeling, and wayfinding tasks. Depending on permissible movement and availability of data, the shortest path is either derived from a pre-defined transportation network or constructed in continuous space. However, continuous space movement adds substantial complexity to identifying the shortest path as the influence of obstacles has to be considered to avoid errors and biases in a derived path. This obstacle-avoiding shortest path in continuous space has been referred to as Euclidean shortest path (ESP), and attracted the attention of many researchers. It has been proven that constructing a graph is an effective approach to limit infinite search options associated with continuous space, reducing the problem to a finite set of potential paths. To date, various methods have been developed for ESP derivation. However, their computational efficiency is limited due to fundamental limitations in graph construction. In this research, a novel algorithm is developed for efficient identification of a graph guaranteed to contain the ESP. This new approach is referred to as the convexpath algorithm, and exploits spatial knowledge and GIS functionality to efficiently construct a graph. The convexpath algorithm utilizes the notion of a convex hull to simultaneously identify relevant obstacles and construct the graph. Additionally, a spatial filtering technique based on intermediate shortest path is enhances intelligent identification of relevant obstacles. Empirical applications show that the convexpath algorithm is able to construct a graph and derive the ESP with significantly improved efficiency compared to visibility and local visibility graph approaches. Furthermore, to boost the performance of convexpath in big data environments, a parallelization approach is proposed and applied to exploit computationally intensive spatial operations of convexpath. Multicore CPU parallelization demonstrates noticeable efficiency gain over the sequential convexpath. Finally, spatial representation and approximation issues associated with raster-based approximation of the ESP are assessed. This dissertation provides a comprehensive treatment of the ESP, and details an important approach for deriving an optimal ESP in real time. / Dissertation/Thesis / Doctoral Dissertation Geography 2015

abstract: Social media has become popular in the past decade. Facebook for example has 1.59 billion active users monthly. With such massive social networks generating lot of data, everyone is constantly looking for ways of leveraging the knowledge from social networks to make their systems more personalized to their end users. And with rapid increase in the usage of mobile phones and wearables, social media data is being tied to spatial networks. This research document proposes an efficient technique that answers socially k-Nearest Neighbors with Spatial Range Filter. The proposed approach performs a joint search on both the social and spatial domains which radically improves the performance compared to straight forward solutions. The research document proposes a novel index that combines social and spatial indexes. In other words, graph data is stored in an organized manner to filter it based on spatial (region of interest) and social constraints (top-k closest vertices) at query time. That leads to pruning necessary paths during the social graph traversal procedure, and only returns the top-K social close venues. The research document then experimentally proves how the proposed approach outperforms existing baseline approaches by at least three times and also compare how each of our algorithms perform under various conditions on a real geo-social dataset extracted from Yelp. / Dissertation/Thesis / Masters Thesis Computer Science 2016

A wireless sensor network (WSN) is made of tiny sensor nodes usually deployed in high density within a targeted area to monitor a phenomenon of interest such as temperature, vibration or humidity. The WSNs can be employed in various applications (e.g., Structural monitoring, agriculture, environment monitoring, machine health monitoring, military, and health). For each application area there are different technical issues and remedies. Various challenges need to be considered while setting up a WSN, including limited computing, memory and energy resources, wireless channel errors and network scalability. One way of addressing these problems is by implementing a routing protocol that efficiently uses these limited resources and hence reduces errors, improves scalability and increases the network lifetime. The topology of any network is important and wireless sensor networks (WSNs) are no exception. In order to effectively model an energy-efficient routing algorithm, the topology of the WSN must be factored in. However, little work has been done on routing for WSNs with regular patterned topologies, except for the shortest path first (SPF) routing algorithms. The issue with the SPF algorithm is that it requires global location information of the nodes from the sensor network, which proves to be a drain on the network resources. In this thesis a novel algorithm namely, BRALB (Biased Random Algorithm for Load Balancing) is proposed to overcome the issues faced in routing data within WSNs with regular topologies such as square-base topology and triangle-based topology. It is based on random walk and probability. The proposed algorithm uses probability theory to build a repository of information containing the estimate of energy resources in each node, in order to route packets based on the energy resources in each node and thus does not require any global information from the network. It is shown in this thesis by statistical analysis and simulations that BRALB uses the same energy as the shortest path first routing as long as the data packets are comparable in size to the inquiry packets used between neighbours. It is also shown to balance the load (i.e. the packets to be sent) efficiently among the nodes in the network. In most of the WSN applications the messages sent to the base station are very small in size. Therefore BRALB is viable and can be used in sensor networks employed in such applications. However, one of the constraints of BRALB is that it is not very scalable; this is a genuine concern as most WSNs deployment is large scale. In order to remedy this problem, C-BRALB (Clustered Biased Random Algorithm for Load Balancing) has been proposed as an extension of BRALB with clustering mechanism. The same clustering technique used in Improved Directed Diffusion (IDD) has been adopted for C-BRALB. The routing mechanism in C-BRALB is based on energy biased random walk. This algorithm also does not require any global information apart from the initial flooding initiated by the sink to create the clusters. It uses probability theory to acquire all the information it needs to route packets based on energy resources in each cluster head node. It is shown in this thesis by using both simulations and statistical analysis that C-BRALB is an efficient routing algorithm in applications where the message to be sent is comparable to the inquiry message among the neighbours. It is also shown to balance the load (i.e. the packets to be sent) among the neighbouring cluster head nodes.