Página 1 dos resultados de 122 itens digitais encontrados em 0.001 segundos

## Métodos heurísticos e exatos para o problemas de roteamento em arcos capacitado e aberto = : Heuristic and exact approaches for the open capacitated arc routing problem; Heuristic and exact approaches for the open capacitated arc routing problem

Fábio Luiz Usberti
Fonte: Biblioteca Digital da Unicamp Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado Formato: application/pdf
Relevância na Pesquisa
38.633562%

## Scale-free networks and scalable interdomain routing

Rodrigues, Pedro Miguel Fonseca
Relevância na Pesquisa
59.024473%
Trabalho apresentado no âmbito do Mestrado em Engenharia Informática, como requisito parcial para obtenção do grau de Mestre em Engenharia Informática; The exponential growth of the Internet, due to its tremendous success, has brought to light some limitations of the current design at the routing and arquitectural level, such as scalability and convergence as well as the lack of support for traffic engineering, mobility, route differentiation and security. Some of these issues arise from the design of the current architecture, while others are caused by the interdomain routing scheme - BGP. Since it would be quite difficult to add support for the aforementioned issues, both in the interdomain architecture and in the in the routing scheme, various researchers believe that a solution can only achieved via a new architecture and (possibly) a new routing scheme. A new routing strategy has emerged from the studies regarding large-scale networks, which is suitable for a special type of large-scale networks which characteristics are independent of network size: scale-free networks. Using the greedy routing strategy a node routes a message to a given destination using only the information regarding the destination and its neighbours...

## A Distributed Geo-Routing Algorithm for Wireless Sensor Networks

Joshi, Gyanendra Prasad; Kim, Sung Won
Fonte: Molecular Diversity Preservation International (MDPI) Publicador: Molecular Diversity Preservation International (MDPI)
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.755237%
Geographic wireless sensor networks use position information for greedy routing. Greedy routing works well in dense networks, whereas in sparse networks it may fail and require a recovery algorithm. Recovery algorithms help the packet to get out of the communication void. However, these algorithms are generally costly for resource constrained position-based wireless sensor networks (WSNs). In this paper, we propose a void avoidance algorithm (VAA), a novel idea based on upgrading virtual distance. VAA allows wireless sensor nodes to remove all stuck nodes by transforming the routing graph and forwarding packets using only greedy routing. In VAA, the stuck node upgrades distance unless it finds a next hop node that is closer to the destination than it is. VAA guarantees packet delivery if there is a topologically valid path. Further, it is completely distributed, immediately responds to node failure or topology changes and does not require planarization of the network. NS-2 is used to evaluate the performance and correctness of VAA and we compare its performance to other protocols. Simulations show our proposed algorithm consumes less energy, has an efficient path and substantially less control overheads.

## Relaxing Routing Table to Alleviate Dynamism in P2P Systems

Fang, Hui; Hsu, Wen Jing; Rudolph, Larry
Fonte: MIT - Massachusetts Institute of Technology Publicador: MIT - Massachusetts Institute of Technology
Tipo: Artigo de Revista Científica Formato: 85408 bytes; application/pdf
Português
Relevância na Pesquisa
48.58581%
In dynamic P2P networks, nodes join and depart from the system frequently, which partially damages the predefined P2P structure, and impairs the system performance such as basic lookup functionality. Therefore stabilization process has to be done to restore the logical topology. This paper presents an approach to relax the requirement on routing tables to provide provably better stability than fixed structured P2P systems. We propose a relaxed Chord that keeps the O(logN) number of hops for greedy lookup, but it requires less stabilization overhead. It allows a tradeoff between lookup efficiency and structure flexibility without adding any overhead to the system. In the relaxed routing structure, each routing entry ("finger") of the node is allowed to vary within a set of values. Each node only needs to keep a certain number of fingers that point to nodes in its anchor set. This relaxation reduces the burden of state management of the node. The relaxed routing scheme provides an alternative structure other than randomized P2P and deterministic P2P, by relaxing on finger selection. It provides good flexibility and therefore extends the system functioning time.; Singapore-MIT Alliance (SMA)

## Energy-efficient beaconless geographic routing in wireless sensor networks

Zhang, H.; Shen, H.
Fonte: IEEE Computer Soc Publicador: IEEE Computer Soc
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.30227%
Geographic routing is an attractive localized routing scheme for wireless sensor networks (WSNs) due to its desirable scalability and efficiency. Maintaining neighborhood information for packet forwarding can achieve a high efficiency in geographic routing, but may not be appropriate for WSNs in highly dynamic scenarios where network topology changes frequently due to nodes mobility and availability. We propose a novel online routing scheme, called Energy-efficient Beaconless Geographic Routing (EBGR), which can provide loop-free, fully stateless, energy-efficient sensor-to-sink routing at a low communication overhead without the help of prior neighborhood knowledge. In EBGR, each node first calculates its ideal next-hop relay position on the straight line toward the sink based on the energy-optimal forwarding distance, and each forwarder selects the neighbor closest to its ideal next-hop relay position as the next-hop relay using the Request-To-Send/Clear-To-Send (RTS/CTS) handshaking mechanism. We establish the lower and upper bounds on hop count and the upper bound on energy consumption under EBGR for sensor-to-sink routing, assuming no packet loss and no failures in greedy forwarding. Moreover, we demonstrate that the expected total energy consumption along a route toward the sink under EBGR approaches to the lower bound with the increase of node deployment density. We also extend EBGR to lossy sensor networks to provide energy-efficient routing in the presence of unreliable communication links. Simulation results show that our scheme significantly outperforms existing protocols in wireless sensor networks with highly dynamic network topologies.; Haibo Zhang and Hong Shen

## Metaheurísticas híbridas aplicadas al problema de ruteo de arcos capacitados; Hybrid metaheuristics for the capacitated arc routing problem

Martínez, Cristian Alejandro
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Relevância na Pesquisa
38.435215%
El Problema de Ruteo de Arcos Capacitados (CARP) es un problema de optimización combinatoria que consiste en satisfacer demandas de servicios/productos sobre determi- nadas calles de una red vial mediante una flota homogénea de vehículos, minimizando el costo total de recorrido involucrado. Ha sido aplicado a casos reales como recolección de residuos, mantenimiento de calles, lectura de medidores eléctricos, entre otros. CARP es un problema de optimización combinatoria de tipo NP-Hard. A tal efecto, en la literatura se han propuesto algoritmos exactos y heurísticas. Los primeros, basados en su mayoría en las técnicas Branch and Bound y Cutting Plane, obtienen soluciones óptimas sobre instancias de datos de tamaño reducido. Los segundos, en general, alcanzan soluciones cercanas a las óptimas y a bajo costo computacional. El objetivo de esta tesis es el desarrollo de algoritmos heurísticos que contengan ca- racterísticas salientes de metaheurísticas tales como Honey Bee Mating Optimization (HBMO), Biased Random Key Genetic Algorithm (BRKGA), Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search (VNS), entre otras. Los resultados computacionales obtenidos por los algoritmos propuestos usando diferentes instancias de la literatura...

## Papillon: Greedy Routing in Rings

Abraham, Ittai; Malkhi, Dahlia; Manku, Gurmeet Singh
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.89836%
We study {\sc greedy} routing over $n$ nodes placed in a ring, with the \emph{distance} between two nodes defined to be the clockwise or the absolute distance between them along the ring. Such graphs arise in the context of modeling social networks and in routing networks for peer-to-peer systems. We construct the first network over $n$ nodes in which {\sc greedy} routing takes $O(\log n / \log d)$ hops in the worst-case, with $d$ out-going links per node. Our result has the first asymptotically optimal greedy routing complexity. Previous constructions required $O(\frac{\log^2 n}{d})$ hops.

## Efficient Greedy Geographical Non-Planar Routing with Reactive Deflection

Theoleyre, Fabrice; Schiller, Eryk; Duda, Andrzej
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.961514%
We present a novel geographical routing scheme for spontaneous wireless mesh networks. Greedy geographical routing has many advantages, but suffers from packet losses occurring at the border of voids. In this paper, we propose a flexible greedy routing scheme that can be adapted to any variant of geographical routing and works for any connectivity graph, not necessarily Unit Disk Graphs. The idea is to reactively detect voids, backtrack packets, and propagate information on blocked sectors to reduce packet loss. We also propose an extrapolating algorithm to reduce the latency of void discovery and to limit route stretch. Performance evaluation via simulation shows that our modified greedy routing avoids most of packet losses.

## Succint greedy routing without metric on planar triangulations

Leone, Pierre; Samarasinghe, Kasun
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
49.466895%
Geographic routing is an appealing routing strategy that uses the location information of the nodes to route the data. This technique uses only local information of the communication graph topology and does not require computational effort to build routing table or equivalent data structures. A particularly effi?cient implementation of this paradigm is greedy routing, where along the data path the nodes forward the data to a neighboring node that is closer to the destination. The decreasing distance to the destination implies the success of the routing scheme. A related problem is to consider an abstract graph and decide whether there exists an embedding of the graph in a metric space, called a greedy embedding, such that greedy routing guarantees the delivery of the data. In the present paper, we use a metric-free de?nition of greedy path and we show that greedy routing is successful on planar triangulations without considering the existence of greedy embedding. Our algorithm rely entirely on the combinatorial description of the graph structure and the coordinate system requires O(log(n)) bits where n is the number of nodes in the graph. Previous works on greedy routing make use of the embedding to route the data. In particular, in our framework...

## On the Necessary and Sufficient Condition of Greedy Routing Supporting Geographical Data Networks

Ghaffari, M.; Hariri, B.; Shirmohammadi, S.
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
49.14359%
Large scale decentralized communication systems have introduced the new trend towards online routing where routing decisions are performed based on a limited and localized knowledge of the network. Geometrical greedy routing has been among the simplest and most common online routing schemes. A perfect geometrical routing scheme is expected to deliver each packet to the point in the network that is closest to the packet destination. However greedy routing fails to guarantee such delivery as the greedy forwarding decision sometimes leads the packets to localized minimums. This article investigates the necessary and sufficient properties of the greedy supporting graphs that provide the guaranteed delivery of packets when acting as a routing substrate.

## Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids

Dietzfelbinger, Martin; Woelfel, Philipp
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.681836%
We consider Kleinberg's celebrated small world graph model (Kleinberg, 2000), in which a D-dimensional grid {0,...,n-1}^D is augmented with a constant number of additional unidirectional edges leaving each node. These long range edges are determined at random according to a probability distribution (the augmenting distribution), which is the same for each node. Kleinberg suggested using the inverse D-th power distribution, in which node v is the long range contact of node u with a probability proportional to ||u-v||^(-D). He showed that such an augmenting distribution allows to route a message efficiently in the resulting random graph: The greedy algorithm, where in each intermediate node the message travels over a link that brings the message closest to the target w.r.t. the Manhattan distance, finds a path of expected length O(log^2 n) between any two nodes. In this paper we prove that greedy routing does not perform asymptotically better for any uniform and isotropic augmenting distribution, i.e., the probability that node u has a particular long range contact v is independent of the labels of u and v and only a function of ||u-v||. In order to obtain the result, we introduce a novel proof technique: We define a budget game, in which a token travels over a game board...

## Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Full)

Eppstein, David; Goodrich, Michael T.; Löffler, Maarten; Strash, Darren; Trott, Lowell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.435215%
A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.; Comment: 12 pages

## Greedy routing on networks of mobile agents

Yang, Han-Xin; Wang, Wen-Xu; Lai, Ying-Cheng; Wang, Bing-Hong
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
48.81092%
In this paper, we design a greedy routing on networks of mobile agents. In the greedy routing algorithm, every time step a packet in agent $i$ is delivered to the agent $j$ whose distance from the destination is shortest among searched neighbors of agent $i$. Based on the greedy routing, we study the traffic dynamics and traffic-driven epidemic spreading on networks of mobile agents. We find that the transportation capacity of networks and the epidemic threshold increase as the communication radius increases. For moderate moving speed, the transportation capacity of networks is the highest and the epidemic threshold maintains a large value. These results can help controlling the traffic congestion and epidemic spreading on mobile networks.

## Near Optimal Routing for Small-World Networks with Augmented Local Awareness

Zeng, Jianyang; Hsu, Wen-Jing; Wang, Jiangdian
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
38.18955%
In order to investigate the routing aspects of small-world networks, Kleinberg proposes a network model based on a $d$-dimensional lattice with long-range links chosen at random according to the $d$-harmonic distribution. Kleinberg shows that the greedy routing algorithm by using only local information performs in $O(\log^2 n)$ expected number of hops, where $n$ denotes the number of nodes in the network. Martel and Nguyen have found that the expected diameter of Kleinberg's small-world networks is $\Theta(\log n)$. Thus a question arises naturally: Can we improve the routing algorithms to match the diameter of the networks while keeping the amount of information stored on each node as small as possible? We extend Kleinberg's model and add three augmented local links for each node: two of which are connected to nodes chosen randomly and uniformly within $\log^2 n$ Mahattan distance, and the third one is connected to a node chosen randomly and uniformly within $\log n$ Mahattan distance. We show that if each node is aware of $O(\log n)$ number of neighbors via the augmented local links, there exist both non-oblivious and oblivious algorithms that can route messages between any pair of nodes in $O(\log n \log \log n)$ expected number of hops...

## Aligned Virtual Coordinates for Greedy Routing in WSNs

Liu, Ke; Abu-Ghazaleh, Nael
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
49.00927%
Geographic routing provides relatively good performance at a much lower overhead than conventional routing protocols such as AODV. However, the performance of these protocols is impacted by physical voids, and localization errors. Accordingly, virtual coordinate systems (VCS) were proposed as an alternative approach that is resilient to localization errors and that naturally routes around physical voids. However, we show that VCS is vulnerable to different forms of the void problem and the performance of greedy routing on VCS is worse than that of geographic forwarding. We show that these anomalies are due to the integral nature of VCS, which causes quantization noise in the estimate of connectivity and node location. We propose an aligned virtual coordinate system (AVCS) on which the greedy routing success can be significantly improved. With our approach, and for the first time, we show that greedy routing on VCS out-performs that on physical coordinate systems even in the absence of localization errors. We compare AVCS against some of the most popular geographical routing protocols both on physical coordinate system and the virtual coordinate systems and show that AVCS significantly improves performance over the best known solutions.

## Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol (Technical Report)

Herzen, Julien; Westphal, Cedric; Thiran, Patrick
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.1418%
We present PIE, a scalable routing scheme that achieves 100% packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a space of concise dimensionality, which enables greedy routing based only on local knowledge. PIE is a general routing scheme, meaning that it works on any graph. We focus however on the Internet, where routing scalability is an urgent concern. We show analytically and by using simulation that the scheme scales extremely well on Internet-like graphs. In addition, its geometric nature allows it to react efficiently to topological changes or failures by finding new paths in the network at no cost, yielding better delivery ratios than standard algorithms. The proposed routing scheme needs an amount of memory polylogarithmic in the size of the network and requires only local communication between the nodes. Although each node constructs its coordinates and routes packets locally, the path stretch remains extremely low, even lower than for centralized or less scalable state-of-the-art algorithms: PIE always finds short paths and often enough finds the shortest paths.; Comment: This work has been previously published in IEEE ICNP'11. The present document contains an additional optional mechanism...

## Category-Based Routing in Social Networks: Membership Dimension and the Small-World Phenomenon (Short)

Eppstein, David; Goodrich, Michael T.; Löffler, Maarten; Strash, Darren; Trott, Lowell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.435215%
A classic experiment by Milgram shows that individuals can route messages along short paths in social networks, given only simple categorical information about recipients (such as "he is a prominent lawyer in Boston" or "she is a Freshman sociology major at Harvard"). That is, these networks have very short paths between pairs of nodes (the so-called small-world phenomenon); moreover, participants are able to route messages along these paths even though each person is only aware of a small part of the network topology. Some sociologists conjecture that participants in such scenarios use a greedy routing strategy in which they forward messages to acquaintances that have more categories in common with the recipient than they do, and similar strategies have recently been proposed for routing messages in dynamic ad-hoc networks of mobile devices. In this paper, we introduce a network property called membership dimension, which characterizes the cognitive load required to maintain relationships between participants and categories in a social network. We show that any connected network has a system of categories that will support greedy routing, but that these categories can be made to have small membership dimension if and only if the underlying network exhibits the small-world phenomenon.

## Hierarchical Bipartition Routing for delivery guarantee in sparse wireless ad hoc sensor networks with obstacles

Gaußmann, Daniel; Hoffmann, Stefan; Wanke, Egon
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
38.633562%
We introduce and evaluate a very simple landmark-based network partition technique called Hierarchical Bipartition Routing (HBR) to support routing with delivery guarantee in wireless ad hoc sensor networks. It is a simple routing protocol that can easily be combined with any other greedy routing algorithm to obtain delivery guarantee. The efficiency of HBR increases if the network is sparse and contains obstacles. The space necessary to store the additional routing information at a node u is on average not larger than the size necessary to store the IDs of the neighbors of u. The amount of work to setup the complete data structure is on average proportional to flooding the entire network log(n) times, where n is the total number of sensor nodes. We evaluate the performance of HBR in combination with two simple energy-aware geographic greedy routing algorithms based on physical coordinates and virtual coordinates, respectively. Our simulations show that the difference between using HBR and a weighted shortest path to escape a dead-end is only a few percent in typical cases.; Comment: Presented on the ICWN 2012, Las Vegas

## A stochastic analysis of greedy routing in a spatially dependent sensor network

Keeler, H. Paul
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
48.09637%
For a sensor network, a tractable spatially-dependent node deployment model is presented with the property that the density is inversely proportional to the sink distance. A stochastic model is formulated to examine message advancements under greedy routing in such a sensor network. The aim of this work is to demonstrate that an inhomogeneous Poisson process can be used to model a sensor network with spatially-dependent node density. Elliptic integrals and asymptotic approximations are used to describe the random behaviour of hops. Types of dependence that affect hop advancements are examined. We observe that the dependence between successive jumps in a multihop path is captured by including only the previous forwarding node location. We include a simple uncoordinated sleep scheme, and observe that the complexity of the model is reduced when enough nodes are asleep. All expressions involving multidimensional integrals are derived and evaluated with quasi-Monte Carlo integration methods based on Halton sequences and recently-developed lattice rules. An importance sampling function is derived to speed up the quasi-Monte Carlo methods. The ensuing results agree extremely well with simulations.

## Improving Routing Efficiency through Intermediate Target Based Geographic Routing

Fei, Zongming; Yang, Jianjun; Lu, Hui
Tipo: Artigo de Revista Científica