Report

A Unified View to Greedy Routing Algorithms in Ad-Hoc Networks ○Truong Minh Tien Joint work with Jinhee Chun, Akiyoshi Shioura, and Takeshi Tokuyama Tohoku University Japan Our Problem and Results Problem: Geometric routing in ad-hoc network. Main Results: ○ Give unified view to known greedy-type routing algorithms. ○ Propose new routing algorithms that works on Delaunay graphs. ○ Compare previous/new algorithms from the viewpoint of guaranteed delivery, fast transmission & power consumption. Contents 1. Ad-hoc network and geometric routing 2. Previous geometric routing algorithms 3. Desirable properties of routing algorithms – Comparison of algorithms 4. Generalized greedy routing algorithm – New greedy-type algorithms 5. Sufficient condition for guaranteed packet delivery Ad-hoc Network Self-organizing network without fixed pre-existing infrastructure Communication between nodes are achieved by multi-hop links Decentralized, mobility-adaptive operation Network topology can be represented by undirected graph G=(V, E) Geometric Routing on Ad-hoc Network Geometric Routing on Ad-hoc network G=(V,E) Send packet from source node S to destination node T (position of T is known in advance) . Packet is repeatedly sent from a node to its neighboring node. No information of entire network; only local information around current node. T S V Greedy Approach for Routing Algorithms Geometric Routing on Ad-hoc network G=(V,E) Greedy approach is often useful: Choose “closer” neighbor to destination in each iteration Which neighbor to choose? Greedy Routing, Compass Routing, Midpoint Routing, etc. T S V Contents 1. Ad-hoc network and geometric routing 2. Previous geometric routing algorithms 3. Desirable properties of routing algorithms – Comparison of algorithms 4. Generalized greedy routing algorithm – New greedy-type algorithms 5. Sufficient condition for guaranteed packet delivery Greedy Routing w2 w1 v t w3 Finn, 1987 • The next neighbor w is the node nearest to t w4 smallest (, ) Compass Routing smallest ∠ w2 w1 v t w3 Kranakis, Singh, Urrutia, 1999 • Packet will be sent to w if the line vw forms with vt the smallest angle. w4 Midpoint Routing w2 v w1 smallest (, ) m t w3 Si, Zomaya, 2010 • Choose next neighbor w that is closest to midpoint m between v an t w4 Modified Midpoint Routing w2 v w1 m p w3 Si, Zomaya, 2010 • The next node w closest to p o p = t : Greedy routing o p = m : Midpoint routing t smallest (, ) w4 Contents 1. Ad-hoc network and geometric routing 2. Previous geometric routing algorithms 3. Desirable properties of routing algorithms – Comparison of algorithms 4. Generalized greedy routing algorithm – New greedy-type algorithms 5. Sufficient condition for guaranteed packet delivery Desirable Properties of Routing Algorithms Guaranteed Delivery: It is guaranteed that a packet is delivered from source to destination. Fast Transmission: Each packet should be sent with a small number of hops. S T Desirable Properties of Routing Algorithms Power Consumption: Long edges should not be used as much as possible. Comparison of Routing Algorithms Guaranteed delivery Number of hops Power Consumption Greedy very small very large Midpoint small large small large average average Modified Midpoint Compass guaranteed on Delaunay graph Need appropriate routing algorithm satisfying desirable properties in response to the request of applications. Contents 1. Ad-hoc network and geometric routing 2. Previous geometric routing algorithms 3. Desirable properties of routing algorithms – Comparison of algorithms 4. Generalized greedy routing algorithm – New greedy-type algorithms 5. Sufficient condition for guaranteed packet delivery Generalized Greedy Routing Unify greedy-type routing algorithms using general objective function. – Obtain better understanding of previous algorithms. – Propose new algorithms. • T = {(w ,v ,t) | w ,v ,t: distinct nodes} (w: next node, v: current node, t: terminal node) • General objective function f : T R {} • Generalized greedy routing: Choose a neighbor w of v that minimizes f (w, v, t) in each iteration Generalized Greedy Routing: Example Choose next node w that minimize f (w, v, t) Example: v 7 3 w2 w1 t 2 w3 +∞ w4 Congruence-Invariant Function w t’ t v f ( w, v, t ) f ( w' , v ' , t ' ) w’ v’ • f is congruence-invariant if function value f (w ,v ,t) depends only on shape and size of wvt . Congruence-Invariant Function f is congruence-invariant function if there exists a function h such that: f ( w, v, t ) h( d vt , d wt , d vw , at , aw , av ) w aw d vw v d wt at av d vt t Greedy Routing: Min d(w, t) function hG d wt w Compass Routing: Min function hc av t w v t v Midpoint Routing: Min d(w, m) function hMP ( d wt sin at ) 2 ( d wt cos at w t d vt 2 ) 2 M. Midpoint Routing: Min d(w, p) function hMMP (dwt sin at )2 (dwt cosat dvt )2 w 1 ( ) 2 t p v wvt m v New routing algorithms w New Greedy I max vwt function h1 aw t v New Greedy II w t w t min d (v, w) / cos(tvw) (tvw / 2) function d vw h2 / 2 (av ) cosav v New Greedy III min d (t, w) / cos(wtv) (wtv / 2) function d wt h3 / 2 (at ) cosat v Contour Map GREEDY - concentric circles about t MIDPOINT - concentric circles about m COMPASS – rays with same endpoint v MODIFIED MIDPOINT concentric circles about p Contour Map of New Routings New Greedy I – curves with same chord vt New Greedy II – circles tangent at v New Greedy III – circles tangent at t Comparison of Routing Algorithms Guaranteed Delivery Number of hops Power Consumption Greedy Very small Very large Midpoint Small Large Small Large Average Average New Greedy II Large Small New Greedy III Small Large Modified Midpoint Compass New Greedy I guaranteed on Delaunay graph Properties of New Greedy II, III If graph G contains Delaunay graph. New Greedy II : always selects Delaunay edge without calculating which edge is Delaunay edge. New Greedy III : always selects Delaunay neighbor of t if there is a two-hop path from v to t . Desired by many occasions. New Greedy II – circles tangent at v New Greedy III – circles tangent at t Comparison of Routing Algorithms Guaranteed Delivery Number of hops Power Consumption Greedy Very small Very large Midpoint Small Large Small Large Average Average New Greedy II Large Small New Greedy III Small Large Modified Midpoint Compass New Greedy I guaranteed on Delaunay graph Contents 1. Ad-hoc network and geometric routing 2. Previous geometric routing algorithms 3. Desirable properties of routing algorithms – Comparison of algorithms 4. Generalized greedy routing algorithm – New greedy-type algorithms 5. Sufficient condition for guaranteed packet delivery Delivery on Delaunay graph • Known results: Each of greedy, compass, midpoint and modified midpoint routing guarantee delivery of packet on Delaunay graph. • Our result: Sufficient condition for guaranteed delivery of generalized greedy routing on Delaunay graph. Delaunay Delivery Guarantee Condition (DDG) ∀distinct nodes w, v, t ∈ P, if f(w ,v ,t) ≤ max{ f(u ,v ,t) | u ∈D(v ,t)}, then d(w ,t) < d(v ,t) holds d(a ,b) : distance between a and b D(v ,t): open disk of diameter d(v,t) DDG Condition D w C : open disk with diameter vt D : open disk with radius tv about t A = max{f(u, v, t) | u ∈ C} C v t u • DDG Condition : For all w with f(w, v, t) ≤ A ; w∈D Strong DDG Condition w C : open disk with diameter vt C v t • Strong DDG Condition : For all u C and w C f (u , v, t ) f ( w, v, t ) u • Strong DDG implies DDG Delivery Guarantee on Delaunay triangulations w v t u Theorem. f is a function satisfying (strong) DDG condition. The algorithm with function f guarantees packet delivery on Delaunay triangulations. Routing Algorithms and DDG Condition Theorem. Greedy Routing, Midpoint Routing and Modified Midpoint Routing satisfy DDG condition Theorem. New Greedy Routing I, II, III satisfy Strong DDG condition Guarantee delivery of packet on Delaunay graphs Example: New Greedy I on Delaunay triangulation S T Hybrid of algorithms Theorem. If f and g satisfy (strong) DDG condition, af+bg (a,b>0) also satisfies (strong) DDG condition. Corresponding algorithm guarantees delivery on Delaunay triangulation • Possible to design appropriate hybrid of algorithms based on requirement of application. Conclusion Our Problem: Geometric routing in Ad-hoc network Our Results: ○ We gave unified view to known greedy-type routing algorithms. ○ We proposed new routing algorithms that works on Delaunay graphs. ○ We compared previous/new algorithms from the viewpoint of guaranteed delivery, fast transmission, & power consumption. Future Work o Consider a metric space with the existence of obstacles and other natural/social conditions in real ad hoc network design. w u t v f (v, w, t ) f (v, u , t ) Thank You