Overlay systems for remote impromptu systems

0
0
1773 days ago, 566 views
PowerPoint PPT Presentation
Inspiration. Remote specially appointed systems have numerous critical applications: pursuit and salvage missions crisis circumstances military applications Signal handling and MAC: OK Scheduling: to some degree OK Routing: HARD!!. Layout. In this discussion: Basic model and objectives Basic methodology (diagram spanners) Basic results about spanners Examples Extensions and issues Realistic remote models and conventions Reference

Presentation Transcript

Slide 1

Overlay systems for remote specially appointed systems Christian Scheideler Dept. of Computer Science Johns Hopkins University

Slide 2

Motivation Wireless specially appointed systems have numerous vital applications: pursuit and safeguard missions crisis circumstances military applications Signal handling and MAC: OK Scheduling: to some degree OK Routing: HARD!!

Slide 3

Outline In this discussion: Basic model and objectives Basic approach (diagram spanners) Basic outcomes about spanners Examples Extensions and issues Realistic remote models and conventions References

Slide 4

Wireless impromptu system

Slide 5

Overlay arrange

Slide 6

Unit circle chart 1

Slide 7

Unit plate diagram Basic objectives: low vitality utilization, high throughput Some connections: high vitality/low achievement prob No specific structure Contention can be issue in thick charts! Methodology: find organized sparsification

Slide 8

Sparsification is not trifling! Each hub associates with two closest neighbors. < 0.074 log n closest neighbors: disengaged w.h.p. > 5.1774 log n closest neighbors: associated w.h.p. on the off chance that hubs disseminated consistently at irregular in curved reg.

Slide 9

Goals of Sparsification Guarantee network Guarantee vitality proficient ways resp. ways with high achievement likelihood Maintain self-directing system (no preprocessing for way choice) General technique: chart spanners

Slide 10

Assumptions Node set V appropriated in 2-diminish Euclidean space e u v Euclidean separation: ||u v|| or ||e|| Power utilization: ||u v|| d for some  > 2  - cost of way p=(e 1 ,… ,e k ): ||p||  =  i=1 k ||e i || 

Slide 11

Distance G=(V,E) u v d G  (u,v) : min ||p||  over all ways p from u to v in G Unit circle diagram UDG(V): just d  (u,v)

Slide 12

UDG Spanners Basic thought : S is spanner of diagram G for some  : subgraph of G with d S  (u,v) ¼ d G  (u,v) for all u,v 2 V c>1 steady, G: UDG(V) Geometric spanner : d S (u,v) < c ¢ d(u,v) Power spanner : d S  (u,v) < c ¢ d  (u,v),  >2 Weak spanner : way p from u to v inside plate of measurement c ¢ d(u,v) Topological spanner : d S 0 (u,v) < c ¢ d 0 (u,v) S G

Slide 13

UDG Spanners Geometric spanner: Weak spanner: Power spanner:

Slide 14

Spanners Geometric spanner: Weak spanner: Power spanner:

Slide 15

UDG Spanners Easier: c>1 consistent. Geometric spanner : d S (u,v) < c ¢ ||u v|| Power spanner : d S  (u,v) < c ¢ ||u v||  ,  >2 Weak spanner : way p from u to v inside circle of breadth c ¢ ||u v|| Constrained spanner : there is a way p fulfilling imperative above and ||e|| <= ||u v|| for all e 2 p E(constrained spanner) Å UDG(V): spanner of UDG(V) We need: c>1 steady Geometric spanner : d S (u,v) < c ¢ d(u,v) Power spanner : d S  (u,v) < c ¢ d  (u,v),  >2 Weak spanner : way p from u to v inside plate of distance across c ¢ d(u,v)

Slide 16

Spanner Properties Geometric spanner ) control spanner Geometric spanner ) frail spanner Weak spanner ) geometric spanner Power spanner ) feeble spanner Weak spanner ) control spanner geometric ) powerless ) control spanner geometric ) control ) frail spanner/

Slide 17

Spanners Geometric spanner: Weak spanner: Power spanner:

Slide 18

Proximity diagrams G=(V,E) is vicinity chart of V if 8 u,w 2 V: either (u,w) 2 E or (u,v) 2 E for some v: ||v w|| < ||u w|| v w u w

Slide 19

Example v

Slide 20

Proximity charts Every closeness chart of V is a feeble 2-spanner . Confirmation: by acceptance on separation min remove: v enlistment w u

Slide 21

Relative neighborhood charts G=(V,E) is a RNG of V if for all u,w 2 V: either (u,w) 2 E or (u,v) 2 E for some v: ||u v|| <= ||u w|| and ||v w|| < ||u w|| v RNG: compelled closeness diagram u w

Slide 22

Relative neighborhood charts Local control govern: v Gives powerless 2-spanner of UDG(V).

Slide 23

Relative neighborhood diagrams Problem: Minimal RNGs have outdegree at most 6 however indegree can be huge.

Slide 24

Routing in RNGs ??? v u What if hubs have GPS? Better: build up/keep up ways Naïve approach: flooding

Slide 25

Sector-based spanners Yao diagram or  - chart (exceptional RNG): Rule: Connect to closest hub in every part

Slide 26

Sector based spanners  - diagrams with >6 segments are geometric spanners Routing: goal Go to hub in area of goal. Requires thick hub dissemination, GPS!

Slide 27

Sector based diagrams Distribution not thick: v s t ???

Slide 28

Delaunay-based spanners Idea: utilize variations of Delaunay diagram Delaunay chart Del(V) of V: contains all {u,v}: 9 w 2 V where O(u,v,w) does not contain any hub of V

Slide 29

Delaunay-based spanners Gabriel chart GG(V) of V: contains all {u,w} with no v 2 V s.t. ||u v|| 2 + ||v w|| 2 < ||u w|| 2 u w GG(V) ½ Del(V)

Slide 30

Relative neighborhood chart G=(V,E) is a RNG of V if for all u,w 2 V: either (u,w) 2 E or (u,v) 2 E for some v: ||u v|| <= ||u w|| and ||v w|| < ||u w|| v RNG: compelled nearness diagram u w

Slide 31

RNG for way misfortune The GG fulfills for all u,w 2 V: either (u,w) 2 E or (u,v) 2 E for some v: c(u,v) <= c(u,w) and c(v,w) < c(u,w) v GG: obliged closeness chart for way misfortune with  =2 u w

Slide 32

Delaunay-based spanners GG(V) is an ideal influence spanner . Evidence: Let p be vitality ideal way for {u,v}. Consider any edge {x,y} in p. {x,y} 2 GG(V): {x,y} 2 GG(V):/Contradiction!

Slide 33

Delaunay-based spanners Problem with Gabriel charts: can have high degree, can be poor geometric spanner Alternative: k-confined Delaunay diagrams LDel (k) (V) v No hub in k-neighborhood of u,v,w in UDG(V) u w

Slide 34

Delaunay-based spanners LDel (1) (V): not planar LDel (2) (V): planar and geometric spanner Planarity vital for steering!

Slide 35

Routing in planar charts Face directing: s t

Slide 36

That's pleasant, however do these methodologies work practically speaking???

Slide 37

Problem: Unit Disk Model in actuality, difficult to keep up planar overlay organize.

Slide 38

Reality u Cost work c and steady  >0 s.t. for any two focuses v and w c(v,w) 2 [(1- ) ¢ ||v w||, (1+  ) ¢ ||v w||] c(v,w) = c(w,v)

Slide 39

Realistic remote model When utilizing cost work c: Proximity diagrams: OK Relative neighborhood charts: OK  - charts:  < arccos (  2 +1/2)/(1- 2 ),  < 1/2 Gabriel charts, confined Delaunay charts: not planar but rather other spanner comes about OK Face steering extendable to more sensible model? Is GPS essential?

Slide 40

Problem: GPS a bit much for topology control, but rather would we be able to stay away from GPS for steering? Conceivable arrangement: utilize compel approach

Slide 41

Problem: Cost Model Power spanner inclines toward over Energy utilization:

Slide 42

Solution Only permit long edges (aside from last).

Slide 43

Problem: Contention Still an excessive amount of dispute on the grounds that each hub takes part in steering. Better to have thruway framework (i.e., just couple of hubs go about as transfer hubs).

Slide 44

Solution Construct overwhelming set : each has inside its transmission extend

Slide 45

Problem: Mobility Solution: see portability as another measurement

Slide 46

Problem: Protocol Design u Cost work c and steady  >0 s.t. for any two focuses v and w c(v,w) 2 [(1- ) ¢ ||v w||, (1+  ) ¢ ||v w||] c(v,w) = c(w,v)

Slide 47

Realistic remote model v u w transmission run impedance extend

Slide 48

Realistic remote model Design of calculations considerably more confused! s v t Estimate of thickness troublesome without physical bearer detecting

Slide 49

Physical transporter detecting v u w coordinate impact no impact

Slide 50

Future issues Overlay systems are interesting issue! Issues: Local self-adjustment Robustness against antagonistic conduct Distributed enhancement Unified system display (???)

Slide 51

References Surveys: R. Rajaraman. Topology control and directing in specially appointed systems: an overview. SIGACT News 33(2):60-73, 2002. C. Scheideler. Overlay systems for remote frameworks. To show up in Performance Analysis of Mobile Ad Hoc Networks. Nova Science Publishers. Stochastic dissemination of hubs: F. Xue and P.R. Kumar. The quantity of neighbors required for availability in remote systems. Remote Networks 10(2):169-181, 2004. Spanners: D. Eppstein. Spreading over Trees and Spanners. In Handbook of Computational Geometry. Elsevier, 2000. D. Peleg and A. Schaffer. Chart Spanners. Diary of Graph Theory 13:99-116, 1989. A. C.- C. Yao. On developing least traversing trees in k-dimensional space and related issues. SIAM Journal on Computing 11:721-736, 1982.

Slide 52

References Properties of geometric spanners: C. Schindelhauer, K. Volbert and M. Ziegler. Spanners, feeble spanners, and power spanners for remote systems. In Proc. of 15 th Int. Symp. On Algorithms and Computation (ISAAC), pages 805-821, 2004. Segment based spanners: K. L. Clarkson. Estimation calculations for briefest way movement arranging. In Proc. 19 th SIGACT Symposium, 1987. X.- Y. Li, P.- J. Wan and Y. Wang. Control proficient and inadequate spanner for remote specially appointed systems. In Proc. of IEEE Int. Conf. on Computer Communications and Networks (ICCCN), 2001. F. Meyer auf der Heide, C. Schindelhauer, K. Volbert and M. Grunewald. Vitality, clog and expansion in radio systems. In Proc. of 14 th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 230-237, 2002. J. Ruppert and R. Seidel. Approximating the d-dimensional finish Euclidean diagram. In 3 rd Canadian Conf. on Computational Geometry (CCCG), pages 207-210, 1991. A. C.- C. Yao. On developing least spreading over trees in k-dimensional space and related issues. SIAM Journal on Computing 11:721-736,

SPONSORS