UB CSE 620 - Scalable Location Management for Large Mobile Ad hoc Networks

Unformatted text preview:

Scalable Location Management for Large Mobile Ad hoc NetworksContentsWireless Ad hoc networksIssue of ScalabilityTraditional ProtocolsAny contenders ?Geographic ForwardingDesirable Properties of Location ManagementScalable Location based Routing Protocol (SLURP)ExampleCost of Location ManagementMobility ModelLocation update OverheadSlide 14Home Region MaintenanceTotal OverheadScaLAble Location Management (SLALoM)Protocol OperationControl OverheadGrid Location Service (GLS)PowerPoint PresentationGLS QueryHIEARCHICAL GRID LOCATION MGMTLOCATION REGISTRATIONLOCATION MAINTENANCELOCATION DISCOVERY & DATA TRANSFERPERFORMANCE ANALYSIS: Location Management OverheadLOCATION REGISTRATION COSTLOCATION MAINTENANCE COSTLOCATION DISCOVERY COSTPERFORMANCE ANALYSIS: Simulations (GloMoSim)RESULTSCONCLUSIONSReferencesScalable Location Management for Large Mobile Ad hoc NetworksSumesh J. PhilipContentsWireless Ad hoc networksIssue of ScalabilityGeographic RoutingScalable Location Update based RoutingSLALoM - Scalable Location ManagementGrid Location ServiceHierarchical Grid Location ManagementSimulations and ResultsConclusionWireless Ad hoc networksInfrastructure-less networks that can be easily deployedEach wireless host acts as an independent router for relaying packetsNetwork topology changes frequently and unpredictablyHow to route packets?Quite a lot of protocols proposed in literature (table driven/reactive/hybrid)Dynamic source Routing (DSR) works well for small networksIssue of ScalabilityIncreasing density increases average node degree, decreases network diameterRouting cost lessAny reasonable scheme might work!To test scalability, area (playground size) must increase with nodesAverage node degree constantWill present a mobility model that consolidates the above relationshipTraditional ProtocolsTable driven incur large overheads due to routing table maintenanceDelayed control as good as no controlOn-demand flood the entire network with discovery packetslong latency for discoveryPath maintenance means additional stateNo separation between data and controlUltimately, data suffers!!Any contenders ?Not many invariants to play with (IP address, local connectivity)Nodes physically located closer likely to be connected by a small number of radio hopsPossible to obtain node location via a GPS receiverGeographic forwardingPacket header contains the destination’s locationMost forward with fixed radiusGeographic ForwardingABCDFC’s radio rangeEGA addresses a packet to G’s latitude, longitudeC only needs to know its immediate neighbors to forward packets towards G.Geographic forwarding needs location management!Desirable Properties ofLocation ManagementSpread load evenly over all nodesDegrade gracefully as nodes failQueries for nearby nodes stay localPer-node storage and communication costs grow slowly as the network size growsScalable Location based Routing Protocol (SLURP)Hybrid Protocol that has a deterministic manner of discovering the destinationTopography divided into square gridsEach node (ID) selects a home region using f(ID), and periodically registers with the HRNodes that wish to communicate with a node query its HR using f--1(ID)Use geographic forwarding to send data, once location is known (e.g. MFR)Example[12][10]- Home region- Update/Query- Location Database- Dataf(ID)- ID Mod(RT)ID = 22; RT= 12;HR=22%12 = 10;DST = 22; RT= 12;HR=22%12 = 10;Cost of Location ManagementLocation RegistrationPeriodicTriggeredLocation MaintenanceOperations for database consistencyLocation DiscoveryQuery/responseData TransferMobility ModelEach node moves independently and randomlyDirection , Velocity [v-c, v+c] at tNew direction and velocity at destinationNode degree = To keep degree constant, A must grow linearly with N]20[NArt2Location update Overheadregion of area region of side 2rangeion transmiss node of velocity hops ofnumber costbroadcast crossingregion of rate aRrvubtRvdRCosv4 22 21 trabsec/)( )(cost pdateLocation U ubcuLocation update OverheaddzzzfzeezrzftzrzAntz)(12)(0222regions ofNumber G region ain nodes Average region excluded of Area distance node-intermean degree node average progress forwardmost NAnzz)( )( )( )(2NvONRRRvzdbubcNRGRduHome Region Maintenance)( Overhead eMaintenanc))1(2(4 1 );2(2vOraRvbctm On region crossingInform previous region of departureInform new region of arrivalUpdate from any node in new regionregionper nodes ofnumber Average nodes ofnumber Total NTotal Overhead)(2 2 NOzduclCost of LocatingSend a Location query to Home regionTotal Overhead = Sum of all overheads for all nodessec/)( NvNONNNvNNvcccclmuScaLAble Location Management (SLALoM)Define a hierarchy of regions : Order(3), Order(2), Order(1)Each Order(2) region consists of K2 Order(1) regionsEach node assigned a HR in an Order(2) regionTo reduce location update overhead, define far and near HRs; near regions updated frequentlyNodes that wish to communicate with another node query its HR in current Order(2) gridQueries from far HRs find way to near ones for exact location of destinationProtocol Operation- Order 3- Update/Query- Location Database- DataK = 3- Order 2- Home regionControl Overhead)( ))()9((22221KvNvKOuKAbubOcfnu)( 1 );2(1vObcmMaintenance OverheadLocation UpdateCost of Locating)()(zKOzKOclTotal Overhead)( at minimized );(343122vNONKKNvvKNOcGrid Location Service (GLS)nsssssssss• s is n’s successor in that square. (Successor is the node with “least ID greater than” n )sibling level-0squaressibling level-1squaressibling level-2squares...1.........GLS Updates923, 211, 269111623617426215192573292...........................181 location table contentlocation update2Invariant (for all levels):For node n in a square, n’s successor in each sibling square “knows” about n.1.........923, 211, 2691121623617426215192573292...........................18... 1 location table contentquery from 23 for 1GLS QueryHIEARCHICAL GRID LOCATION MGMTMotivationsCurrent solutions do not scale well or not robust with node mobilityDo not consider


View Full Document

UB CSE 620 - Scalable Location Management for Large Mobile Ad hoc Networks

Download Scalable Location Management for Large Mobile Ad hoc Networks
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Scalable Location Management for Large Mobile Ad hoc Networks and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Scalable Location Management for Large Mobile Ad hoc Networks 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?