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 networksIssue of ScalabilityGeographic 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 diameterRouting cost lessAny reasonable scheme might work!To test scalability, area (playground size) must increase with nodesAverage node degree constantWill present a mobility model that consolidates the above relationshipTraditional ProtocolsTable driven incur large overheads due to routing table maintenanceDelayed control as good as no controlOn-demand flood the entire network with discovery packetslong latency for discoveryPath 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 forwardingPacket header contains the destination’s locationMost 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 RegistrationPeriodicTriggeredLocation MaintenanceOperations for database consistencyLocation DiscoveryQuery/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[NArt2Location update Overheadregion of area region of side 2rangeion transmiss node of velocity hops ofnumber costbroadcast crossingregion of rate aRrvubtRvdRCosv4 22 21 trabsec/)( )(cost pdateLocation U ubcuLocation update OverheaddzzzfzeezrzftzrzAntz)(12)(0222regions ofNumber G region ain nodes Average region excluded of Area distance node-intermean degree node average progress forwardmost NAnzz)( )( )( )(2NvONRRRvzdbubcNRGRduHome 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 NOzduclCost of LocatingSend a Location query to Home regionTotal Overhead = Sum of all overheads for all nodessec/)( NvNONNNvNNvcccclmuScaLAble 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(1vObcmMaintenance OverheadLocation UpdateCost of Locating)()(zKOzKOclTotal Overhead)( at minimized );(343122vNONKKNvvKNOcGrid 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 MGMTMotivationsCurrent solutions do not scale well or not robust with node mobilityDo not consider
View Full Document