New version page

UCLA COMSCI 218 - clustering-icc03

Documents in this Course
GSM

GSM

59 pages

Chord

Chord

30 pages

10_2

10_2

9 pages

13_4

13_4

10 pages

RAP

RAP

17 pages

46_4

46_4

9 pages

32_4

32_4

10 pages

umts

umts

39 pages

AdHoc-MAC

AdHoc-MAC

29 pages

rma

rma

8 pages

Lecture

Lecture

29 pages

Load more

This preview shows page 1-2-3-4 out of 12 pages.

View Full Document
View Full Document

End of preview. Want to read all 12 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

Efficient Flooding in Ad Hoc Networks: a Comparative Performance StudyIntroductionIntroduction (2)Overview of Efficient FloodingNeighbor Topology based ProtocolSource-Tree Based ProtocolCluster-based ProtocolSimulation StudyPerformance Test v.s. DensityPerformance v.s. MobilityApplications : AODVConclusionEfficient Flooding in Ad Hoc Networks: a Comparative Performance StudyYJung and Mario GerlaUniversity of California, Los AngelesIntroductionFloodingThe basic mechanism to propagate control messagesEx. route query flooding of reactive routing schemeBlind floodingAll nodes in the network (re)-broadcast the packetInefficiencyRedundant and superfluous packetsHigh probability of collision and contentionHeavy congestion of wireless mediumIntroduction (2)Efficient floodingA subset of dominant neighbors re-broadcast the flood packet to guarantee complete floodingContributionsWe classify and evaluate existing efficient flooding schemesOverview of Efficient FloodingNeighboring topology based protocolSource-tree based protocolCluster-based protocolNeighbor Topology based ProtocolMulti-Point Relay (MPR)Use neighbors’ information within two hopsSelects a minimal subset of forwarding neighbors (MPRNs) that covers all the nodes two-hop awayGAFUse location information to choose minimal set of dominating nodesExcluded from our study due to the assumption of (extra) position information32,31241,3,41,2,3,41,3,42,3MPR: Node 1 chooses node 2 as MPRNStop forwardingSource-Tree Based ProtocolBuilds a sh-path source-tree rooted at the flood initiatorRebroadcast if a node is on shortest path and non-leaf “Reverse Path Forwarding”S123 45Blue nodes (non-leafs) rebroadcastCluster-based ProtocolClustering: grouping nodes into clustersCluster head: a representative node of each groupGateway: a node connecting more than two clustersOrdinary nodes: OthersEfficient Flooding: only cluster heads and gateways rebroadcastTwo clustering mechanismsActive clustering: builds the cluster structure proactivelyPassive clustering: builds the clusters passively, using on-going data trafficSClusterHeadGatewayOrdinary NodeSimulation StudyEnvironmentGloMoSim 2.0Target protocols:MPR (F-MPR)Active clustering with Lowest ID algorithm (F-AC)Passive clustering (F-PC)Reverse path forwarding (source-tree based protocol) (F-RPF)Blind flooding (F-BF)ProtocolsUDP/802.11 DCF/two-ray propagation modelBW: 2MBits/secPower Range: 250metersSingle source initiates flooding 4 times per secondPerformance Test v.s. DensityDelivery Ratio rank:F-BF >> F-PC >> F-RPF >> F-AC >> F-MPRFlooding efficiency rankF-RPF >> F-MPR >> F-AC >> F-PC >> F-BFMPR suffers due to inaccurate neighbor information -> insufficient # of dominating nodes are chosenRPF works the best. But RPF needs a complex extension to be applied to multiple floodings (multiple source trees)PC works overall okayDelivery Ratio Forwarding OHPerformance v.s. MobilityRank does not change from the previous resultsPassive clustering outperforms all (but BF): keep stable with increase of mobilityDelivery RatioForwarding OHApplications : AODVDelivery Ratio Control OHEfficient flooding improves AODV performance at heavy loadMPR works better than Pass Clustering at heavy load; but, MPR requires periodic table exchange – unfit for on-demand rtngConclusionA comparative study of efficient flooding mechanismsResults:Passive clustering performs well for a broad range of node mobility and network density valuesPassive clustering is the most robustAccurate neighbor information collection is very challenging due to unreliable pkt deliveryMPR, active clustering shows bad performance in high mobilityEach scheme has a different set of suitable applicationsF-PC for reactive routing protocolsF-MPR, F-AC and F-RPF for proactive


View Full Document
Loading Unlocking...
Login

Join to view clustering-icc03 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 clustering-icc03 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?