Real Time Flow Handoff in Ad Hoc Wireless Networks using Mobility PredictionChallenges in Ad Hoc Wireless NetworkOn Demand RoutingSlide 4Mobility Prediction EnhancementsSlide 6Prediction of link connectivityOther Schemes that use GPSOn Demand Mobility Prediction (OD-MP) ProtocolSlide 10Predictive Route ReconstructionSlide 12Slide 13Slide 14Slide 15Slide 16Slide 17Future DirectionsPrediction of connectivitySlide 20IntroductionApproach 2Slide 23Real Time Flow Handoff in Ad Hoc Wireless Networks using Mobility PredictionWilliam SuMario GerlaComp Science Dept, UCLAChallenges in Ad Hoc Wireless Network•Topology is constantly changing•Key requirements–dynamic route reconfiguration–minimize impact on multimedia connections (voice/video/data)–minimize control overhead (bandwidth is very limited)sourcedestinationdata routeOn Demand Routing 051243query(0)query(0)query(0)query(0)query(0)query(0)query(0)Destinationreply(0)reply(0)051243reply(0)Source SourceDestinationOn Demand Approach•PROS:–No periodic routing table broadcast (routing table maintained only when a node has data to send) •CONS:–Initial route acquisition delay and route rebuild delay–Overhead goes up as number of active connections in the network increases (broadcast storm!)–Requires mechanisms to detect route break and perform route reconstruction•beacons, passive acknowledgementsMobility Prediction Enhancements•The motivation:–Mobility patterns often exhibit predictable behavior (i.e., cars traveling on freeway)–Reacting to topology changes only after they occur can seriously degrade real-time (voice, video) performanceMobility Prediction Enhancements•The goal:–Minimize disruptions due to topology changes by performing re-route ahead of time–Reduce the transmission of unnecessary control overhead by using more stable routes (bandwidth efficient)Prediction of link connectivitymobileBATXBTXATX Transmission Range•For mobiles A and B, we compute the link expiration time (LET) of the radio link–Approach 1: use GPS position information exchange –Approach 2: use Transmission power informationOther Schemes that use GPS•Location Aided Routing (LAR) by Ko-Vaidya at Texas A&M University–an On Demand scheme that uses location information obtained from GPS to limit the propagation region of Route Requests packets•Distance Routing Effect Algorithm for Mobility (DREAM) by Basagni-Chlamtac at UT Dallas–Performs routing (location) table updates periodically, however data is flooded in the general direction of the destinationOn Demand Mobility Prediction (OD-MP) Protocol•Initial route discovery–as the ROUTE-REQ message is flooded, intermediate nodes also append their ID and LET for last hop of the ROUTE-REQ–destination receives ROUTE-REQ with different paths and the link expiration times•Destination computes the Route Expiration Time (RET) for each route and selects the most stable one (maximum RET) for data delivery–ROUTE-SETUP message is sent back to the source to setup the routeInitial Route ConstructionRoute DiscoverysourceA BCDEdestinationRouteSetupA BCDEmobileROUTE-SETUPROUTE-REQ4.15.03.04.04.5LETRET for route A-B-C-E= 4.1RET for route A-B-D-E= 3.0Predictive Route Reconstruction•Data packets carry current RET in their header; thus, RET is refreshed at the destination•When RET is approaching, destination floods ROUTE-REQ messages in similar fashion as initial route construction•source receives ROUTE-REQ messages and chooses the best route for the data deliveryConnection reroute examplebeforererouteA BCDE Fafterreroutemobiledata routesourceA BCDE Fdestinationcurrent time= 4.96.35.06.05.07.0RET = 5.06.5RET = 6.06.37.05.05.06.56.0Simulation Experiment environmentmultihop network environment100 mobile nodes, radio bandwidth = 2Mbps, roaming square = 500x500m, transmission range = 120mrouting protocols evaluatedOD-MP DSDV (Destination Sequence Distance Vector)LMR (Lightweight Mobile Routing)UDP traffic, single source/destination pair; constant bit rate = 40 packets/sec; packet size = 10kbitsMobility varying between 18 km/hr to 180 km/hr; mobility pattern = straight trajectoryPerformance Parameters•Packet Delivery Ratio : Fraction of original packets delivered to destination•End to End Delay•Control Traffic Overhead (Kbits/s)00.10.20.30.40.50.60.70.80.9115 30 45 60 75 90 105 120 135 150 165 180Mobility Speed (km/hr)Packet Delivery RatioOD-MPLMRDSDVPacket Delivery Ratio vs. Mobility Speed02040608010012014016015 30 45 60 75 90 105 120 135 150 165 180Mobility Speed (km/hr)Avg. Packet Delay (ms)OD-MPLMRDSDVAvg. Packet Delay vs. Mobility Speed0500010000150002000025000300003500015 30 45 60 75 90 105 120 135 150 165 180Mobility Speed (km/hr)Control Overhead (Kbits/s)OD-MPLMRDSDVControl Overhead vs. Mobility Speed020040060080010001200140016001800200015 30 45 60 75 90 105 120 135 150 165 180Mobility Speed (km/hr)OD-MPLMRFuture Directions•Impacts of prediction errors on performance–Location and speed errors–Mobility pattern randomness•Hybrid distance vector and on demand routing using mobility prediction•Performance improvements with prediction for non-realtime applications (TCP)Prediction of connectivity•Approach 1: GPS –Assuming a free space propagation model–let the mobility info for mobile i be (xi,yi,vi,i,TXi,), where (xi,yi) = position, vi = speed,  i = heading, and TXi = transmission power for mobile i–assume we have mobiles 1 and 2 and TX1 = TX2 = TX, then Dt, the amount of time mobiles 1 and 2 will stay connected is given by)(2))((4)(4)(222222222caTXdbcacdabcdabDtwhere212211212211sinsincoscosyydvvcxxbvva–We can obtain mobility information using Differential GPSPrediction of connectivity•Approach 2: Transmission Power Measurements–Transmission power samples are measured from a mobile’s neighbor–From the samples we can obtain the rate of change for the neighbor’s transmission power level–the time that the neighbor’s power level drops below the accepted level for a connection (e.g. hysterisis region) can be computedIntroductionWireless Mobile NetworksSingle hop (cellular) : fixed base stationsMultihop (ad hoc) : no fixed base stations, mobile stations act as routersIPv6 FlowSupports real time flows (i.e., voice, video)Designed to replace existing IPv4 protocolApproach 2Example: Transmission power level measured by mobile 1 for