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

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

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!!

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

Wireless impromptu system

Overlay arrange

Unit circle chart 1

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

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.

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

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 ||

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)

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

UDG Spanners Geometric spanner: Weak spanner: Power spanner:

Spanners Geometric spanner: Weak spanner: Power spanner:

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)

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/

Spanners Geometric spanner: Weak spanner: Power spanner:

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

Example v

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

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

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

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

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

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

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

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

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

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)

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

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

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!

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

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

Routing in planar charts Face directing: s t

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

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

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)

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?

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

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

Solution Only permit long edges (aside from last).

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).

Solution Construct overwhelming set : each has inside its transmission extend

Problem: Mobility Solution: see portability as another measurement

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)

Realistic remote model v u w transmission run impedance extend

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

Physical transporter detecting v u w coordinate impact no impact

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

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.

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

No comments found.

SPONSORS

SPONSORS