F 16 Location Services

Views:
 
Category: Entertainment
     
 

Presentation Description

No description available.

Comments

Presentation Transcript

Location Services for Ad-Hoc Networks: 

Location Services for Ad-Hoc Networks Rich Goyette 11 Nov 05 rgoyette@forces.gc.ca

Outline: 

Outline Introduction Problem Characteristics of Location Services Solution Space Review Overview of Selected Approaches Summary Questions

Introduction: 

Introduction Position-Based routing protocols: use physical location of destination node to turn global routing into a local decision. Examples of progress based algorithms: Greedy, DIR, MFR [S2] scale with increasing network size [LCN][C]; have reduced overhead in comparison to position-less protocols [C][SPHL]; can operate without memory;

Problem: 

Problem In order to route, the source node S needs accurate position of destination node D. This requires a location service beneath the routing layer that provides the following service primitives [SQ][SP]: Node position registration; Node position update; Node position location;

Location Service Characteristics: 

Location Service Characteristics An effective location service: must be scalable (hinges on position discovery and maintenance overhead [SPHL] [DPH][SP]); must be robust to changes in network topology [DPH]; should itself operate using position based routing [DPH];

Solution Domain: 

Solution Domain * This taxonomy is taken from [C] with additional works mapped into it from [DPH], [MWH], and [S1].

Solution Domain: 

Solution Domain * This taxonomy is taken from [C] with additional works mapped into it from [DPH], [MWH], and [S1].

SLURP [WS]: 

SLURP [WS] SLURP: Scalable Location Update-Based Routing Protocol [WS]. Simplest “home region” implementation [YLZ]; Home Region (HR) for each node is derived by hashing Node IDs to (x,y) coordinates. One HR for the entire network.

SLURP [WS]: 

SLURP [WS]

SLURP [WS]: 

SLURP [WS] Position Update:

SLURP [WS]: 

SLURP [WS] Position Location:

SLURP [WS]: 

SLURP [WS] Observations: SLURP has low implementation complexity. Slurp does not appear to be scalable [SPHL][YLZ]. Location requests may traverse long paths even if nodes are close. Robustness could be problematic for non-uniformly distributed networks (empty HR, restricted zones). SLALoM seeks to improve scalability of SLURP by localizing updates.

SLALoM [CLPBZ]: 

SLALoM [CLPBZ] SLALoM: Scalable Ad-hoc Location Management [CLPBZ]. Grid-based – physical location of network divided into “grid squares.” Home Regions (HR) for each node are derived by hashing Node IDs to (x,y) coordinates. SLALoM maintains multiple home regions – can be viewed as a hybrid between quorum and home zone approach.

SLALoM [CLPBZ]: 

SLALoM [CLPBZ] Home Region Assignment for each node ni: HR(ni)=F(ni,Order2) next

SLALoM [CLPBZ]: 

SLALoM [CLPBZ]

SLALoM [CLPBZ]: 

SLALoM [CLPBZ]

SLALoM [CLPBZ]: 

SLALoM [CLPBZ] Location Discovery (u wishes to find v):

SLALoM [CLPBZ]: 

SLALoM [CLPBZ] Observations (from [CLPBZ]): Compared to SLURP: Average signalling delay of SLALoM remains relatively constant as network size grows (while SLURP increases). Location updates and queries are localized in Order2 squares For small to moderate sized networks, both have comparable signalling traffic. SLALoM signalling can be reduced by increasing Order2 dimension at expense of signalling delay. SLALoM is more robust to loss of nodes in HR. ELF seeks to improve SLURP by introducing location forwarding concept from packet radio.

ELF [SQ]: 

ELF [SQ] ELF: Efficient Location Forwarding Aim: to improve SLALoM by introducing location forwarding. Replace “near” and “far” home regions with forwarding and terminal home regions.

ELF [SQ]: 

ELF [SQ] Location Update Case 1:

ELF [SQ]: 

ELF [SQ] Location Update Case 2:

ELF [SQ]: 

ELF [SQ] Location Update Case 3: u inquires into Order1 square about nodes for which it must maintain location information.

ELF [SQ]: 

ELF [SQ] Location Discovery (u wishes to find v): u v

ELF [SQ]: 

ELF [SQ] Observations: ELF outperforms SLALoM in average case scenarios and is no worse in worse case scenarios ([SQ]). Use of forwarding chain enhances scalability by reducing the average signalling cost in comparison to SLALoM ([SQ]).

Solution Domain: 

Solution Domain * This taxonomy is taken from [C] with additional works mapped into it from [DPH], [MWH], and [S1].

XYLS [DPH]: 

XYLS [DPH] A node updates position by storing to a “write” quorum. A node queries a location by making destination request from “read” quorum. Challenge is to ensure that read/write quorums intersect sufficiently to maximize P(query success) ([C]) XYLS – a row/column quorum method based on [SP1]

XYLS [DPH]: 

XYLS [DPH] Location Registration/Update u

XYLS [DPH]: 

u v XYLS [DPH] Location Query Loc request includes time- stamped last known position of u. Reply packets are sent with more recent loc only.

XYLS [DPH]: 

XYLS [DPH] Observations: Authors of [MWH] conclude: Algorithm for selecting row/column nodes can impact overhead. Robustness of Quorum-Based location services can be affected by node failure. Authors of [DPH] conclude XYLS is scalable in comparison to other protocols (GLS, GHLS).

XYLS [DPH]: 

XYLS [DPH] Observations: Read/Write quorums can be a challenge to define and manage in mobile networks. Position based Virtual backbone Commonly identified issue: Locally northernmost problem.

Solution Domain: 

Solution Domain * This taxonomy is taken from [C] with additional works mapped into it from [DPH], [MWH], and [S1].

DREAM [BCS]: 

DREAM [BCS] DREAM: Distance Routing Effect Algorithm for Mobility. Dream represents class of proactive, flooding based protocols. Based on two observations: Distance Effect: “the greater the distance separating two nodes, the slower they appear to be moving with respect to each other.”[BCS] Node updates are related to node mobility rate.

DREAM []: 

DREAM [] Distance Effect Nodes transmit update packets with fixed lifetime: Most are “short lived” and don’t travel far. Some are “long lived” and reach outer edges. Frequency of update packets related to speed. Figure 2 from [Mauve]

DREAM [BCS]: 

DREAM [BCS] Location Registration * DLS [] also maintains speed as provided by node

DREAM []: 

DREAM [] Location Update Case 1:

DREAM [BCS]: 

DREAM [BCS] Location Query

DREAM [BCS]: 

DREAM [BCS] Location Query Anew C Aold One-hop neighbours re- transmit to their one-hop neighbours using their LT info for A.

DREAM [BCS]: 

DREAM [BCS] Observations: Authors of DREAM contend loop free but [S2] indicates that this is not the case; Authors of [MWH] conclude: DREAM is very robust (messages can take multiple, independent routes and all nodes contain info on all other nodes). Implementation complexity is low; BUT not scalable (for large networks) due to update communication complexity (flooding).

DREAM [BCS]: 

DREAM [BCS] Observations: In event that node has no LT entry or entry is stale, a recovery mechanism (flooding) is needed. Authors of [BCS] found that messages are delivered 80% of time with moderate mobility rate. Authors of [CBW] found: Location requests are almost always answered; Location information accuracy is affected by speed;

Summary: 

Summary Use of position information for routing has generated need for location services. Location services need to provide position registration, update, and query in efficient, robust, scalable manner. Some examples – SLURP, SLALoM, DREAM.

Questions for Exam: 

Questions for Exam During the course, a number of position-based routing protocols (eg SLURP, SLALOM ) were examined. What difficult problem must be solved in order for these algorithms to be effective? A. Each node must be able to obtain and share position information in a scalable, robust, and bandwidth efficient manner. Position-based routing depends on a location service to provide three basic tasks in relation to position information. What are these? A. Position registration, position update, and position query. The Distance Routing Effect Algorithm for Mobility (DREAM) is a location service for position-based routing. Explain the “Distance Effect” that it is based on. A. The Distance Effect makes nodes that are further away appear to move less. This is used by DREAM to limit location updates to the local area.

Questions: 

Questions

References: 

References [BCC] N. Bauer, M. Colagrosso, T. Camp, An agile approach to distributed information dissemination in mobile ad hoc networks, Proc. 6th IEEE Int. Symposium on a World of Wireless Mobile and Multimedia Networks 2005 (WoWMoM’05), pp. 131-141.   [BCS] S. Basagni, I. Chlamtac, V. Syrotiuk, A distance routing effect algorithm for mobility, Proc. 4th Annual ACM/IEEE Int. Conf. On Mobile Computing and Networking MOBICOM’98, pp. 76-84, 1998.   [C] T. Camp, Location information services in mobile ad hoc networks, Technical Report MCS-03-15, The Colorado School of Mines, October 2003.   [CBW] T. Camp, J. Boleng, L. Wilcox, Location information services in mobile ad hoc networks, IEEE International Conference on Communications, 2002 (ICC 2002), vol. 5, pp. 3318 – 3324.   [SCS] Y. Sasson, D. Cavin, A. Schiper, A location service mechanism for position-based multicasting in wireless mobile ad hoc networks, Proc. 38th IEEE Annual Hawaii International Conference on System Sciences, 2005 (HICSS '05) pp. 321b - 321b   [CLPBZ] C. Cheng, H. Lemberg, S. Philip, E. van den Berg, T. Zhang, SLALoM: a scalable location management scheme for large mobile ad-hoc networks, Proc. IEEE Wireless Communications and Networking Conference, 2002 (WCNC2002), vol. 2, pp. 574 – 578.

References: 

References [DPH] S. Das, H. Pucha, Y.C. Hu, Performance comparison of scalable location services for geographic ad hoc routing, Proc. IEEE INFOCOM 2005, Miami, FL, March 13-17, pp. 1228-1239, 2005.   [KV] Y.B. Ko, N. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proc. 4th Annual ACM/IEEE Int. Conf. On Mobile Computing and Networking MOBICOM’98, pp. 66-75, 1998.   [LCN] X. Luo, T. Camp, W. Navidi, Predictive methods for location services in mobile ad hoc networks, Proc. 19th IEEE Int. Parallel and Distributed Processing Symposium 2005 (IPDPS’05), pp. 246b-246b.   [MK] Z. Mir, S. Khan, A zone based location service for mobile ad hoc networks, International Conference on Networking and Communication 2004 (INCC204), pp. 1 – 5.   [MWH] M. Mauve, J. Widmer, H. Hartenstein, A survey on position-based routing in mobile ad-hoc networks, IEEE Network Magazine, 15(6):30 - 39, November 2001. [S1] I. Stojmenovic, Location updates for efficient routing in ad hoc networks, in: Handbook on Wireless Networks and Mobile Computing, John Wiley & Sons, 2002, to appear. [S2] I. Stojmenovic, Position based routing in ad hoc networks, IEEE Communications Magazine, Vol. 40, No. 7, July 2002, pp. 128-134. [SP1] I. Stojmenovic, P. Pena, A scalable quorum based location update scheme for routing in ad hoc wireless networks.

References: 

References [SP2] S. Sivavakeesar, G. Pavlou, Scalable location services for hierarchically organized mobile ad hoc networks, Proc. MobiHoc’05, Urbana-Champaign, Illinois, May 25-27, pp. 217-228. [SPHL] B.C. Seet, Y. Pan, W.J Hsu, C.T. Lau, Multi-home region location service for wireless ad hoc networks: an adaptive demand-driven approach, Proc. 2nd Annual Conf. On Wireless On-Demand Network Systems and Services (WONS’05), pp. 258-263.   [SQ] S. Philip, C. Qiao, ELF: efficient location forwarding in ad hoc networks, Proc. GLOBECOM '03 IEEE, vol. 2,  1-5 Dec. 2003, pp. 913 – 918.   [SSHMH] C. Shete, S. Sawhney, S. Herwadkar, V. Mehandru, A. Helmy, Analysis of the effects of mobility on the grid location service in ad hoc networks, IEEE International Conference on Communications 2004, vol. 7, pp. 4341-4345.   [WS] S.C.M. Woo, S. Singh, Scalable routing protocol for ad hoc networks, Wireless Networks 7, pp. 513-529, Kluwer Academic Publishers, 2001.   [YLZ] Y. Yu, G.H. Lu, Z.L. Zhang, Enhancing location service scalability with HIGH-GRADE, Proc. of the 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS 2004), Fort Lauderdale, Florida, October 2004, pp. 164-173.

authorStream Live Help