Página 1 dos resultados de 122 itens digitais encontrados em 0.002 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
Publicado em 13/02/2012 Português
Relevância na Pesquisa
415.65562%
O problema de roteamento em arcos capacitado e aberto (open capacitated arc routing problem, OCARP) é um problema de otimização combinatorial NP-difícil em que, dado um grafo não-direcionado, o objetivo consiste em encontrar um conjunto de rotas de custo mínimo para veículos com capacidade restrita que atendam a demanda de um subconjunto de arestas. O OCARP está relacionado com o problema de roteamento em arcos capacitado (capacitated arc routing problem, CARP), mas difere deste pois o OCARP não possui um nó depósito e as rotas não estão restritas a ciclos. Aplicações da literatura para o OCARP são discutidas. Uma formula ção de programação linear inteira é fornecida junto com propriedades do problema. Uma metaheurística GRASP (greedy randomized adaptive search procedure) com reconexão por caminhos (path-relinking) é proposta e comparada com outras metaheurísticas bem-sucedidas da literatura. Algumas características do GRASP são: (i) ajuste reativo de parâmetros, cujos valores são estocasticamente selecionados com viés `aqueles valores que produziram, em média, as melhores soluções; (ii) um filtro estatístico que descarta soluções iniciais caso estas tenham baixa probabilidade de superar a melhor solução incumbente; (iii) uma busca local infactível que gera soluções de baixo custo utilizadas para explorar fronteiras factíveis/infactíveis do espaço de soluções; (iv) a reconexão por caminhos evolutiva aprimora progressivamente um conjunto de soluções de elevada qualidade (soluções elites). Testes computacionais foram conduzidos com instâncias CARP e OCARP e os resultados mostram que o GRASP é bastante competitivo...

Scale-free networks and scalable interdomain routing

Rodrigues, Pedro Miguel Fonseca
Fonte: Faculdade de Ciências e Tecnologia Publicador: Faculdade de Ciências e Tecnologia
Tipo: Dissertação de Mestrado
Publicado em //2010 Português
Relevância na Pesquisa
628.09812%
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
Publicado em 27/05/2009 Português
Relevância na Pesquisa
419.52848%
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
514.1357%
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
Publicado em //2010 Português
Relevância na Pesquisa
405.1107%
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
Fonte: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires Publicador: Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Tipo: info:eu-repo/semantics/doctoralThesis; tesis doctoral; info:eu-repo/semantics/publishedVersion Formato: application/pdf
Publicado em //2011 Português
Relevância na Pesquisa
409.34223%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 13/07/2005 Português
Relevância na Pesquisa
524.0841%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 24/02/2009 Português
Relevância na Pesquisa
426.0943%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 28/04/2015 Português
Relevância na Pesquisa
542.18043%
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.
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 30/03/2009 Português
Relevância na Pesquisa
531.88973%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 06/05/2013 Português
Relevância na Pesquisa
517.1921%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/10/2011 Português
Relevância na Pesquisa
409.34223%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/12/2011 Português
Relevância na Pesquisa
521.3008%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
401.52277%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 20/05/2006 Português
Relevância na Pesquisa
527.61414%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/05/2013 Português
Relevância na Pesquisa
400.0029%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 23/08/2011 Português
Relevância na Pesquisa
409.34223%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 08/07/2013 Português
Relevância na Pesquisa
415.65562%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Português
Relevância na Pesquisa
498.55688%
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
Fonte: Universidade Cornell Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 15/02/2015 Português
Relevância na Pesquisa
419.2435%
The greedy strategy of geographical routing may cause the local minimum problem when there is a hole in the routing area. It depends on other strategies such as perimeter routing to find a detour path, which can be long and result in inefficiency of the routing protocol. In this paper, we propose a new approach called Intermediate Target based Geographic Routing (ITGR) to solve the long detour path problem. The basic idea is to use previous experience to determine the destination areas that are shaded by the holes. The novelty of the approach is that a single forwarding path can be used to determine a shaded area that may cover many destination nodes. We design an efficient method for the source to find out whether a destination node belongs to a shaded area. The source then selects an intermediate node as the tentative target and greedily forwards packets to it, which in turn forwards the packet to the final destination by greedy routing. ITGR can combine multiple shaded areas to improve the efficiency of representation and routing. We perform simulations and demonstrate that ITGR significantly reduces the routing path length, compared with existing geographic routing protocols.