Including context in a routing algorithm for the internet of things

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para obtenção do grau de Mestre em Engenharia Informática

Question Waves: A multicast query routing algorithm for social search

This paper describes Question Waves, an algorithm that can be applied to social search protocols, such as Asknext or Sixearch. In this model, the queries are propagated through the social network, with faster propagation through more trustable acquaintances. Question Waves uses local information to make decisions and obtain an answer ranking. With Question Waves, the answers that arrive first are the most likely to be relevant, and we computed the correlation of answer relevance with the order of arrival to demonstrate this result. We obtained correlations equivalent to the heuristics that use global knowledge, such as profile similarity among users or the expertise value of an agent. Because Question Waves is compatible with the social search protocol Asknext, it is possible to stop a search when enough relevant answers have been found; additionally, stopping the search early only introduces a minimal risk of not obtaining the best possible answer. Furthermore, Question Waves does not require a re-ranking algorithm because the results arrive sorted

An oblivious shortest-path routing algorithm for fully connected cubic networks

Fully connected cubic networks (FCCNs) are a class of newly proposed hierarchical interconnection networks for multicomputer systems, which enjoy the strengths of constant node degree and good expandability. The shortest path routing in FCCNs is an open problem. In this paper, we present an oblivious routing algorithm for n-level FCCN with N = 8(n) nodes, and prove that this algorithm creates a shortest path from the source to the destination. At the costs of both an O(N)-parallel-step off-line preprocessing phase and a list of size N stored at each node, the proposed algorithm is carried out at each related node in O(n) time. In some cases the proposed algorithm is superior to the one proposed by Chang and Wang in terms of the length of the routing path. This justifies the utility of our routing strategy. (C) 2006 Elsevier Inc. All rights reserved.

A low power routing algorithm for localization in IEEE 802.15.4 networks

Many context-aware applications rely on the knowledge of the position of the user and the surrounding objects to provide advanced, personalized and real-time services. In wide-area deployments, a routing protocol is needed to collect the location information from distant nodes. In this paper, we propose a new source-initiated (on demand) routing protocol for location-aware applications in IEEE 802.15.4 wireless sensor networks. This protocol uses a low power MAC layer to maximize the lifetime of the network while maintaining the communication delay to a low value. Its performance is assessed through experimental tests that show a good trade-off between power consumption and time delay in the localization of a mobile device.

Self-organizing Routing Algorithm fo Wireless Sensors Networks (WSN) using Ant Colony Optimization (ACO) with Tinyos.

This paper describes the basic tools to work with wireless sensors. TinyOShas a componentbased architecture which enables rapid innovation and implementation while minimizing code size as required by the severe memory constraints inherent in sensor networks. TinyOS's component library includes network protocols, distributed services, sensor drivers, and data acquisition tools ? all of which can be used asia or be further refined for a custom application. TinyOS was originally developed as a research project at the University of California Berkeley, but has since grown to have an international community of developers and users. Some algorithms concerning packet routing are shown. Incar entertainment systems can be based on wireless sensors in order to obtain information from Internet, but routing protocols must be implemented in order to avoid bottleneck problems. Ant Colony algorithms are really useful in such cases, therefore they can be embedded into the sensors to perform such routing task.

The Balanced Cross-Layer Design Routing Algorithm in Wireless Sensor Networks Using Fuzzy Logic

Recently, the cross-layer design for the wireless sensor network communication protocol has become more and more important and popular. Considering the disadvantages of the traditional cross-layer routing algorithms, in this paper we propose a new fuzzy logic-based routing algorithm, named the Balanced Cross-layer Fuzzy Logic (BCFL) routing algorithm. In BCFL, we use the cross-layer parameters’ dispersion as the fuzzy logic inference system inputs. Moreover, we give each cross-layer parameter a dynamic weight according the value of the dispersion. For getting a balanced solution, the parameter whose dispersion is large will have small weight, and vice versa. In order to compare it with the traditional cross-layer routing algorithms, BCFL is evaluated through extensive simulations. The simulation results show that the new routing algorithm can handle the multiple constraints without increasing the complexity of the algorithm and can achieve the most balanced performance on selecting the next hop relay node. Moreover, the Balanced Cross-layer Fuzzy Logic routing algorithm can adapt to the dynamic changing of the network conditions and topology effectively.

Multi-region routing

Dissertação apresentada na Faculdade de Ciências e Tecnologia da Universidade Nova de Lisboa para a obtenção do grau de Mestre em Engenharia Electrotécnica e de Computadores

Intrusion tolerant routing with data consensus in wireless sensor networks

Dissertação para obtenção do Grau de Mestre em Engenharia Informática

An adaptive cluster based routing scheme for mobile wireless sensor networks

Clustering schemes improve energy efficiency of wireless sensor networks. The inclusion of mobility as a new criterion for the cluster creation and maintenance adds new challenges for these clustering schemes. Cluster formation and cluster head selection is done on a stochastic basis for most of the algorithms. In this paper we introduce a cluster formation and routing algorithm based on a mobility factor. The proposed algorithm is compared with LEACH-M protocol based on metrics viz. number of cluster head transitions, average residual energy, number of alive nodes and number of messages lost

Impact of Node Mobility on Routing Protocols for Wireless Sensor Networks

Wireless sensor networks monitor their surrounding environment for the occurrence of some anticipated phenomenon. Most of the research related to sensor networks considers the static deployment of sensor nodes. Mobility of sensor node can be considered as an extra dimension of complexity, which poses interesting and challenging problems. Node mobility is a very important aspect in the design of effective routing algorithm for mobile wireless networks. In this work we intent to present the impact of different mobility models on the performance of the wireless sensor networks. Routing characteristics of various routing protocols for ad-hoc network were studied considering different mobility models. Performance metrics such as end-to-end delay, throughput and routing load were considered and their variations in the case of mobility models like Freeway, RPGM were studied. This work will be useful to figure out the characteristics of routing protocols depending on the mobility patterns of sensors

Artificial ants for active routing

Ant colonies in nature provide a good model for a distributed, robust and adaptive routing algorithm. This paper proposes the adoption of the same strategy for the routing of packets in an Active Network. Traditional store-and-forward routers are replaced by active intermediate systems, which are able to perform computations on transient packets, in a way that results very helpful for developing and dynamically deploying new protocols. The adoption of the Active Networks paradigm associated with a cooperative learning environment produces a robust, decentralized routing algorithm capable of adapting to network traffic conditions.

Adaptive routing in active networks

New conceptual ideas on network architectures have been proposed in the recent past. Current store-andforward routers are replaced by active intermediate systems, which are able to perform computations on transient packets, in a way that results very helpful for developing and deploying new protocols in a short time. This paper introduces a new routing algorithm, based on a congestion metric, and inspired by the behavior of ants in nature. The use of the Active Networks paradigm associated with a cooperative learning environment produces a robust, decentralized algorithm capable of adapting quickly to changing conditions.

Dynamic Routing in Translucent WDM Optical Networks: The Intradomain Case

Translucent wavelength-division multiplexing optical networks use sparse placement of regenerators to overcome physical impairments and wavelength contention introduced by fully transparent networks, and achieve a performance close to fully opaque networks at a much less cost. In previous studies, we addressed the placement of regenerators based on static schemes, allowing for only a limited number of regenerators at fixed locations. This paper furthers those studies by proposing a dynamic resource allocation and dynamic routing scheme to operate translucent networks. This scheme is realized through dynamically sharing regeneration resources, including transmitters, receivers, and electronic interfaces, between regeneration and access functions under a multidomain hierarchical translucent network model. An intradomain routing algorithm, which takes into consideration optical-layer constraints as well as dynamic allocation of regeneration resources, is developed to address the problem of translucent dynamic routing in a single routing domain. Network performance in terms of blocking probability, resource utilization, and running times under different resource allocation and routing schemes is measured through simulation experiments.

Vehicle routing and crew scheduling for metropolitan mail distribution at Australia Post

This paper presents a new multi-depot combined vehicle and crew scheduling algorithm, and uses it, in conjunction with a heuristic vehicle routing algorithm, to solve the intra-city mail distribution problem faced by Australia Post. First we describe the Australia Post mail distribution problem and outline the heuristic vehicle routing algorithm used to find vehicle routes. We present a new multi-depot combined vehicle and crew scheduling algorithm based on set covering with column generation. The paper concludes with a computational investigation examining the affect of different types of vehicle routing solutions on the vehicle and crew scheduling solution, comparing the different levels of integration possible with the new vehicle and crew scheduling algorithm and comparing the results of sequential versus simultaneous vehicle and crew scheduling, using real life data for Australia Post distribution networks.