无线网络·10无线MESH网络

Wireless Mesh NetworksChallenges and OpportunitiesYi PingSchool of Information Security Engineering,Shanghai Jiao Tong University 2005,20061OutlineOverview of the technologyOpportunities(Research)ChallengesCurrent state of the artConclusion2 Wireless routers Gateways Printers,servers Mobile clients Stationary clientsIntra-mesh wireless links Stationary client accessMobile client accessInternet access links Node TypesLink TypesOverview3GatewaysMultiple interfaces(wired&wireless)MobilityStationary(e.g.rooftop)most common caseMobile(e.g.,airplane,busses/subway)Serve as(multi-hop)“access points”to user nodesRelatively few are needed,(can be expensive)GW4Wireless RoutersAt least one wireless interface.MobilityStationary(e.g.rooftop)Mobile(e.g.,airplane,busses/subway).Provide coverage(acts as a mini-cell-tower).Do not originate/terminate data flowsMany needed for wide areas,hence,cost can be an issue.5UsersTypically one interface.MobilityStationaryMobileConnected to the mesh network through wireless routers(or directly to gateways)The only sources/destinations for data traffic flows in the network.6User Wireless Router LinksWiredBus(PCI,PCMCIA,USB)Ethernet,Firewire,etc.Wireless802.11xBluetoothProprietaryPoint-to-Point or Point-to-MultipointIf properly designed is not a bottleneck.If different from router-to-router links well call them access links7Router to Router LinksWireless802.11xProprietaryUsually multipoint to multipointSometimes a collection of point to pointOften the bottleneckIf different from router-to-user links well call them backbone links8Gateway to Internet LinksWiredEthernet,TV Cable,Power LinesWireless802.16ProprietaryPoint to Point or Point-to-MultipointWell call them backhaul linksIf properly designed,not the bottleneck9How it WorksUser-Internet Data FlowsIn most applications the main data flows User-User Data FlowsIn most applications a small percentage of data flows10TaxonomyWirelessNetworkingMulti-hopInfrastructure-less(ad-hoc)Infrastructure-based(Hybrid)Infrastructure-less(MANET)SingleHopCellularNetworksWireless Sensor NetworksWireless MeshNetworksCar-to-car Networks(VANETs)Infrastructure-based(hub&spoke)802.11802.16Bluetooth802.1111Mesh vs.Ad-Hoc NetworksMultihopNodes are wireless,possibly mobileMay rely on infrastructureMost traffic is user-to-userAd-Hoc NetworksWireless Mesh NetworksMultihopNodes are wireless,some mobile,some fixedIt relies on infrastructureMost traffic is user-to-gateway12Mesh vs.Sensor NetworksBandwidth is limited(tens of kbps)In most applications,fixed nodesEnergy efficiency is an issueResource constrainedMost traffic is user-to-gatewayWireless Sensor NetworksWireless Mesh NetworksBandwidth is generous(1Mbps)Some nodes mobile,some fixedNormally not energy limitedResources are not an issueMost traffic is user-to-gateway13OutlineOverview of the technologyOpportunitiesApplicationsComparison with existing technologies(Research)ChallengesCurrent state of the artConclusion14Broadband Internet Access15Extend WLAN CoverageSource: Source: 16Mobile Internet AccessLaw enforcementIntelligent transportationDirect competition with G2.5 and G3 cellular systems.Source: (now ).17Emergency ResponseSource: 18Layer 2 ConnectivityThe entire wireless mesh cloud becomes one(giant)Ethernet switchSimple,fast installationShort-term events(e.g.,conferences,conventions,shows)Where wires are not desired(e.g.,hotels,airports)Where wires are impossible(e.g.,historic buildings)Internet19Military Communications Source: 20Community Networks Source: broadband Internet AccessSeveral neighbors may share their broadband connections with many other neighborsNot run by ISPsPossibly in the disadvantage of the ISPs21Many Other ApplicationsRemote monitoring and controlPublic transportation Internet accessMultimedia home networkingSource:(now ).22OutlineOverview of the technologyOpportunitiesApplicationsComparison with existing technologies(Research)ChallengesCurrent state of the artConclusion23Broadband Internet AccessCableDSLWMAN(802.16)Cellular(2.5-3G)WMNBandwidthVeryGoodVeryGoodLimitedGoodUpfront InvestmentsVeryHighHighHighLowTotal InvestmentsVeryHighHighHighModerateMarket CoverageGoodGoodGoodModest24WLAN CoverageSource:802.11WMNWiringCostsLowHighNumber of APsAs neededTwice as manyCost of APsHighLowBandwidthGoodVeryGood25Mobile Internet AccessCellular2.5 3GWMNUpfrontInvestmentsLowHighGeolocationLimitedGoodBandwidthGoodLimitedUpgradeCostLowHighSource:(now ).26Emergency ResponseCellular2.5 3GWMNSource: WalkieTalkieAvailabilityReasonableGoodGoodBandwidthGoodLimitedPoorGeolocationPoorLimitedPoor27Layer 2 ConnectivityEthernetWMNTotal CostLowModerateMobile Users802.11 needed GoodBandwidthGoodVeryGoodSpeed/Ease of DeploymentFast/EasySlow/Difficult28Military CommunicationsWMNsSource: ExistingSystem(s)CoverageVeryGoodGoodGoodPoorBandwidthVoice SupportGoodVeryGoodCovertnessPoorBetterPower efficiencyGoodReasonable29OutlineOverview of the technologyOpportunitiesApplicationsComparison with existing technologies(Research)ChallengesCurrent state of the artConclusion30AbstractionUsers+routers=nodesNodes have two functions:Generate/terminate trafficRoute traffic for other nodesInternet+=Internet31Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location32Physical Layer(PHY)Wish listPerformanceBandwidthRobust modulationSensitivityShort preamble Fast switch between channelsFast switch from Tx/Rx and backExtrasMobility(potentially high-speed)Link adaptationVariable transmission power(details shortly)Multiple channels Link quality feedback33PHY-ModulationExisting modulations work well(OFDM,DSSS,FSK,etc.).UWB may be an interesting alternative for short distancesSpread spectrum solutions are preferred as they tend to have better reliability in the face ofFading(very important for mobile applications)Interference(more of a factor than in any other wireless system)34LicensedSpectrumUnlicensedSpectrumCostExpensiveFreeControllable medium(i.e.,no interference)YesNoPHY-Licensed vs.Unlicensed SpectrumLimits on Transmitted PowerSomeLots35PHY Smart AntennasBackgroundImplemented as an array of omnidirectional antennasBy changing the phase,beamforming can be achievedThe result is a software steered directional antennaOmnidirectionalantennaVariabledelaySignal totransmitRadiation PatternDirectionchanged bythe delays36PHY-Smart AntennasAdvantagesLow power transmissionsBattery not a big concern in many applicationsEnables better spatial reuse and,hence,increased network capacity37PHY-Smart AntennasAdvantages(cont)Punch-through linksBetter delays(?)Less packet loss(?)Better data rates(?)Less power(?)38PHY-Smart Antennas Advantages(cont)Better SNRBetter data ratesBetter delaysBetter error rates39PHY-Smart Antennas DisadvantagesSpecialized hardwareSpecialized MAC(difficult to design)Difficult to track mobile data users40PHY Transmission Power ControlToo lowToo highJust rightGWGWGW41PHY Transmission Power Control(cont)Optimization CriteriaNetwork capacityDelayError ratesPower consumptionThe ideal solution will depend onNetwork topologyTraffic load 42Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location43Medium Access Control(MAC)ScheduledFix scheduled TDMAPollingImpractical due to lack of:Central coordination pointReasonable time synchronization Random AccessCSMA simple and popularRTS/CTS protects the receiver44Proprietary MAC802.11CompatibleEase of upgradeHardEasyForce clients to buy custom cardsYes/YesNo/No802.11 CompatibilityFlexible PHY/MACYesNo45MAC MultichannelWhat?Channels can be implemented by:TDMA(difficult due to lack of synchronization)FDMACDMA(code assignment is an issue)SDMA(with directional antennas)Combinations of the above46Increases network capacityMAC MultichannelWhy?B=bandwidth of a channelUser bandwidth=B/2Ch-1Ch-11234User bandwidth=BCh-1Ch-21234Chain bandwidth=BCh-1Ch-212347MAC MultichannelHow?Standard MAC(e.g.,802.11)Custom MACSingle RadioMultiple RadiosXXXX48MAC MultichannelStandard MAC Single RadioCan it be done at all?Perhaps,if a new Multi-Channel Coordination Layer(MCCL)is introduced between MAC and NetworkMust work within the constraints of 802.11May increase the capacity of the networkPHY802.11MCCLIPCh-1Ch-21234Ch-1Ch-212349MAC MultichannelStandard MAC Single Radio(cont)Channel assignmentGateway Loads=2:2:2Gateway Loads=4:1:1GWGWGWGWGWGW50MAC MultichannelCustom MAC Single RadioEasier problem than beforeCommon advantages and disadvantages associated with custom MACsMay further increase the capacity of the networkThe problem of optimal channel assignment remainsPHYCustomIPGWGWGW51MAC MultichannelStandard MAC Multiple RadiosA node now can receive while transmittingPractical problems with antennas separation(carrier sense from nearby channel)Optimal assignment NP complete problemSolutionsCentralizedDistributedGWGWGW52MAC MultichannelCustom MAC Multiple RadiosNodes can use a control channel to coordinate and the rest to exchange data.In some conditions can be very efficient.However the control channel can be:an unacceptable overhead;a bottleneck;GWGWGW53Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location54RoutingFinds and maintains routes for data flowsThe entire performance of the WMN depends on the routing protocolMay be the main product of a mesh companyMay be missing55Routing Wish ListScalabilityOverhead is an issue in mobile WMNs.Fast route discovery and rediscoveryEssential for reliability.Mobile user supportSeamless and efficient handoverFlexibilityWork with/without gateways,different topologiesQoS SupportConsider routes satisfying specified criteriaMulticastImportant for some applications(e.g.,emergency response)56Existing Routing ProtocolsInternet routing protocols(e.g.,OSPF,BGP,RIPv2)Well known and trustedDesigned on the assumption of seldom link changesWithout significant modifications are unsuitable for WMNs in particular or for ad hoc networks in general.Ad-hoc routing protocols(e.g.,DSR,AODV,OLSR,TBRPF)Newcomers by comparison with the Internet protocolsDesigned for high rates of link changes;hence perform well on WMNsMay be further optimized to account for WMNs particularitiesAd HocNetworksWireless MeshNetworks57Routing-Optimization CriteriaMinimum HopsMinimum DelaysMaximum Data RatesMinimum Error RatesMaximum Route StabilityMinimum ETAPower ConsumptionCombinations of the aboveUse of multiple routes to the same gatewayUse of multiple gateways58Routing Cross-Layer DesignRouting PhysicalLink quality feedback is shown often to help in selecting stable,high bandwidth,low error rate routes.Fading signal strength can signal a link about to fail preemptive route requests.Cross-layer design essential for systems with smart antennas.Routing MACFeedback on link loads can avoid congested links enables load balancing.Channel assignment and routing depend on each other.MAC detection of new neighbors and failed routes may significantly improve performance at routing layer.59Routing Cross-Layer Design(cont)Routing TransportChoosing routes with low error rates may improve TCPs throughput.Especially important when multiple routes are usedFreezing TCP when a route fails.Routing ApplicationEspecially with respect of satisfying QoS constraints60Network Layer-FairnessFairnessEqual share of resources to all participants.Special case of priority based QoS.Horizontal nodes 1,2The MAC layers fairness ensures horizontal fairness.Vertical nodes 3,4MAC layer is no longer sufficientGW12GW3461FairnessProblemIdealRealUnfairInefficientGWGGS1S21262Network FairnessProblem SourceConflict between locally generated traffic and forwarded traffic.At high loads the network layer queue fills up with local traffic and traffic to be forwarded arrives to a full queue.Consequence:no fairnesspoor efficiencySolutions:Compute the fair share for each user and enforce itLocal information based solution presented nextforwardedgeneratedOffered loadThroughputNetwork layerMAC layerGW63 Capacity of the network:G=B/8 Assume unidirectional traffic for the clarity of explanation.f1f2,f3 and f4FairnessConsidered Topology and Node ModelGWGG2G4G123464Single Queuef1f2,-f4Separate Queueforwarded(f2-f4)generated(f1)Offered loadTheoretically evaluated throughputsf1:f2:f3:f4=4:1:2:1 FairnessSeparate Queue for Local TrafficUnfairInefficientUnfairInefficient65Separate Queuef1:f2:f3:f4=4:1:2:1 FairnessWeighted Queue for Local TrafficUnfairInefficientf1:f2:f3:f4=4:6:3:3 Weighted QueueUnfairInefficient66f1:f2:f3:f4=4:6:3:3 f1:f2:f3:f4=1:1:1:1 Per-flow QueuingWeighted QueueFairnessPer-flow QueueingFairInefficientUnfairInefficient67Per-flow QueuingFairnessPer-flow Queues+MAC Layer QoSFairInefficientf1:f2:f3:f4=1:1:1:1 n1:n2:n3:n4=4:2:1:1 f1:f2:f3:f4=1:1:1:1 Per-flow Queues+MAC Layer QoSFairEfficient68QoSSupport required at every layerPhysical LayerRobust modulationLink adaptationMAC LayerOffer prioritiesOffer guarantees(bandwidth,delay)Network LayerSelect“good”routesOffer prioritiesReserve resources(for guarantees)TransportAttempt end-to-end recovery when possibleApplicationNegotiate end-to-end and with lower layersAdapt to changes in QoS69QoSFlavorsSimilar to RSVP in the InternetHas to implement connection admission controlDifficult in WMNs due to:Shared medium(see provisioning section)Fading and noiseSimilar to diffserv in the InternetOffers classes of servicesGeneralization of fairnessA possible implementation on next slideGuaranteesPriorities70n1:n2:n3:n4=4:2:1:1 f1:f2:f3:f4=1:1:1:1 f1:f2:f3:f4=1:2:3:4 n1:n2:n3:n4=4:2:1:1 Per-flow Weighted Queues+MAC Layer QoSPer-flow Queues+MAC Layer QoSNetwork Layer QoS(Priorities)71Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location72TCPProblemsEfficiency TCP assumes that a missing(or late)ACK is due to network congestion and slows down:to half if the missing ACK shows up fast enoughto zero if it times outCauses for missing ACKs in WMNs:Wireless transmission errorBroken routes due to mobility(both users and wireless routers)Delays due to MAC contentionInterplay between MAC and TCP back-off mechanisms73TCPEfficiency SolutionsFocus on eliminating the confusion between congestion loss and all other reasonsMany approaches developed for single-hop wireless systemsSnoopI-TCPM-TCPEnd to endSACKExplicit error notificationExplicit congestion notification(e.g.RED)Several solutions for multi-hopA-TCPFreeze-TCPApplicabilityClean LayeringImprovement inEfficiencyLayer ViolationsTrade-off74TCPProblems(cont)UnfairnessDue to network layer unfairnessDue to variation in round trip delaysLikely both will be fixed if network layer fairness is ensuredPHYDLLIPTCP75Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location76Two related questions:How much bandwidth for each user?Where to place the next gateway?Essential for QoS guaranteesComplicated by the shared medium and multi-hop routingProvisioning77ACKDATATimeDATASIFS ACKDIFSBODATADIFSBORepeatedProvisioning802.11 Timing diagram for CSMA/CAGW78Bit Stream(PMD-SDU)PLCP-PDUPreambP-HDRPLCP-SDUMAC-PDUM-HDRMAC-SDUFCSIFSBO LLCTime 802.11(b)MAC PLCP PMDProvisioning802.11 Overhead79ProvisioningTMT of 802.11 and 802.11b(CSMA/CA)80ProvisioningTMT of 802.11b and 802.11a(CSMA/CA)81ProvisioningTopology ModelingGWGWGWGWGWGW82Inter-and intra-flow interferenceInterference and topological modelsProvisioningIntra-flow Interference&Chain UtilizationGWGWGWGW83ProvisioningChain Utilization=1/3TimeFlowGW=1/4TimeFlowGW84ProvisioningCollision DomainsGWSymmetric MACGWAsymmetric MACGWCollision Domain(Symmetric MAC)85ProvisioningChain Topology GWGGGGGGGGG2G3G4G5G6G7G8G4G+5G+6G+7G+8G=30 GTherefore,G B/3086ProvisioningArbitrary TopologyGWGGGGGGGG2GGGGGGGGGGG2G2GGGGG3G2G3G3GG87ProvisioningConclusionNon-trivial procedureCapacity depends on:Network topologyTraffic loadAny practical algorithm will trade-off:ResponsivenessEfficiencyGWGGGGGGGG2GGGGGGGGGGG2G2GGGGG3G2G3G3GG88Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location89SecurityAuthenticationPrevent theft of servicePrevent intrusion by malicious usersPrivacy-user data is at risk while on transit in the WMN due to:Wireless mediumMulti-hopReliability protect:Routing dataManagement dataMonitoring dataPrevent denials of service(very difficult at the physical layer)90Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location91Network ManagementMonitor the“health”of the networkDetermine when is time to upgradeEither hardwareNew gatewayDetect problemsEquipment failures(often hidden by the self-repair feature of the network)IntrudersManage the systemSource: 92Overview of Research TopicsPhysical LayerSmart AntennasTransmission Power ControlMAC LayerMultiple ChannelsNetwork LayerRoutingFairness and QoSTransport LayerProvisioningSecurityNetwork ManagementGeo-location93GeolocationWhat?WirelessRoutersUsersMonitoringStation94GeolocationHow?Measure ranges between mobile users and some known fixed points(wireless routers).Triangulate(same as cellular systems).Since the“cells”are much smaller,much better precisions is possible.Many improvements possible as users can talk to each other.95OutlineOverview of the technologyOpportunities(Research)ChallengesCurrent state of the artCompaniesUniversitiesStandardsConclusion96CompaniesAerial BroadbandBelAir NetworksFiretideIntelKiyonLamTech(ex.Radiant)Locust WorldMesh DynamicsMicrosoftMotorola(ex.Mesh Networks)Nokia RooftopNortel NetworksPacket HopRicochet NetworksSkyPilot NetworksStrix SystemsTelabriaTropos Networks97Tiny start-up in RTP,NC,USA in 2002Closed its doors shortly after its startApplication:broadband Internet access to apartment complexesFeatures802.11b-compatible productZero configurationLayer 2“routing”Source: Aerial Broadband98BelAir NetworksBased in Ontario,CanadaApplication:802.11b coverage of large zonesFeatures:Three radios on each wireless router;dynamically mapped on:8 fixed directional antennasDynamic Tx power and data rate controlRouting based on PHY feedback,congestion,latencyLoad balancing features Source: 99FiretideBased in Hawaii and Silicon Valley,USAApplication:Layer 2 connectivity(indoor and outdoor)Features:Proprietary routing protocol2.4GHz and 5GHz productsAES,WEP securityVariable Tx PowerManagement softwareSource: 100IntelExpressed interest in WMNs(since 2002).Research in:Low power related with their wireless sensor networks activities at Intel Research Berkeley Lab.Traffic balancingTogether with Cisco active in 802.11s standardization processSource: 101KiyonBased in La Jolla,CA,USAApplications:extended 802.11 indoor coverageFeatures:Products based on 802.11a/b/gCustom routing(WARP)Management softwareSource: 102LamTech(ex.Radiant Networks)UK-based companyPurchased by LamTech in 2004Applications:broadband Internet accessMESHWORKTM ATM switch in wireless router90 MbpsDirectional links4 mobile directional antennasQoS-CBR&VBR-NRSource: 103Locust WorldBased in UKApplication:community networksFeatures:Free,open source softwareOff-the-shelf hardware+open source softwareMonitoring softwareSeveral deployments around the worldSource: 104Mesh DynamicsBased on Santa Clara,CA,USAApplication:802.11