Efficient Flooding in Ad Hoc Networks: a Comparative Performance StudyYJung and Mario GerlaUniversity of California, Los AngelesIntroductionn Flooding¨ The basic mechanism to propagate control messages¨ Ex. route query flooding of reactive routing schemen Blind flooding¨ All nodes in the network (re)-broadcast the packet¨ Inefficiencyn Redundant and superfluous packetsn High probability of collision and contentionn Heavy congestion of wireless mediumIntroduction (2)n Efficient flooding¨ A subset of dominant neighbors re-broadcast the flood packet to guarantee complete floodingn 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 Protocoln 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 awayn 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 Protocoln Builds a sh-path source-tree rooted at the flood initiatorn Rebroadcast if a node is on shortest path and non-leaf n “Reverse Path Forwarding”S123 45Blue nodes (non-leafs) rebroadcastCluster-based Protocoln Clustering: grouping nodes into clustersn Cluster head: a representative node of each groupn Gateway: a node connecting more than two clustersn Ordinary nodes: Othersn Efficient Flooding: only cluster heads and gateways rebroadcastn Two clustering mechanisms¨ Active clustering: builds the cluster structure proactively¨ Passive clustering: builds the clusters passively, using on-going data trafficSClusterHeadGatewayOrdinary NodeSimulation Studyn Environment¨ GloMoSim 2.0¨ Target protocols:n MPR (F-MPR)n Active clustering with Lowest ID algorithm (F-AC)n Passive clustering (F-PC)n Reverse path forwarding (source-tree based protocol) (F-RPF)n Blind flooding (F-BF)¨ Protocolsn UDP/802.11 DCF/two-ray propagation modeln BW: 2MBits/secn Power Range: 250meters¨ Single source initiates flooding 4 times per secondPerformance Test v.s. Densityn Delivery Ratio rank:¨ F-BF >> F-PC >> F-RPF >> F-AC >> F-MPRn Flooding efficiency rank¨ F-RPF >> F-MPR >> F-AC >> F-PC >> F-BFn MPR suffers due to inaccurate neighbor information -> insufficient # of dominating nodes are chosenn RPF works the best. But RPF needs a complex extension to be applied to multiple floodings (multiple source trees)n PC works overall okayDelivery Ratio Forwarding OHPerformance v.s. Mobilityn Rank does not change from the previous resultsn Passive clustering outperforms all (but BF): keep stable with increase of mobilityDelivery Ratio Forwarding 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 rtngConclusionn A comparative study of efficient flooding mechanismsn Results:¨ Passive clustering performs well for a broad range of node mobility and network density valuesn Passive clustering is the most robust¨ Accurate neighbor information collection is very challenging dueto unreliable pkt deliveryn MPR, active clustering shows bad performance in high mobility¨ Each scheme has a different set of suitable applicationsn F-PC for reactive routing protocolsn F-MPR, F-AC and F-RPF for proactive
View Full Document
Unlocking...