Adaptive, Traffic-based Channel Allocation for Wireless Ad-hoc NetworksOutlineWireless BackboneAnalogyRadio Architecture: OFDMOFDM (contd.)Problem StatementExampleFirst level of clusteringSecond level of clusteringPollingPolling (contd.)AlgorithmSimulationsScalabilityComparisonConclusionsGautam Kulkarni & Vijay Raghunathan UCLA Networked and Embedded Systems Lab (NESL)http://nesl.ee.ucla.edu/Adaptive, Traffic-based Channel Allocation for Wireless Ad-hoc Networkshttp://nesl.ee.ucla.edu/ 2OutlineOutline•Introduction•Radio architecture: overview of OFDM•Distributed Channel Allocation Algorithm•Validation and Simulation Resultshttp://nesl.ee.ucla.edu/ 3Wireless BackboneWireless BackboneWirelessIP routerOFDMRadio•Rapidly deployable ad hoc backbone•Need high capacity links between the wireless routers•Limited available spectrum – need spatial reuseWireless IP backboneGigabit Wireless Router project with RSC – part of NGI programhttp://nesl.ee.ucla.edu/ 4AnalogyAnalogy•Links  “Pipes” carrying information•Thickness  Bandwidth available•Due to limited spectrum, increase in the thickness of one pipe comes at the cost of a decrease in the thickness of some other.•Modulation schemes like OFDM allow us to modify the thickness of a pipe.http://nesl.ee.ucla.edu/ 5Radio Architecture: OFDMRadio Architecture: OFDMN-IFFTFront-endFrequencyfN tonesTimeN samplesN.f1•OFDM: Orthogonal Frequency Division Multiplexing•N tightly spaced subcarriers•Each tone is modulated individually •Digital multiplexing using an IFFThttp://nesl.ee.ucla.edu/ 6OFDM (contd.)OFDM (contd.)ModulateDemodulateSub channels•The wireless channel is heavily frequency selective.•OFDM is composed of multiple narrow contiguous subcarriers.•Each subcarrier experiences only a part of the channel (subchannel).•OFDM effectively deals with multi-path effects.•Becoming increasingly popular: Cisco, Rockwell Science Center, Iospan Wireless (formerly Gigabit Wireless), Malibu Networks etc.http://nesl.ee.ucla.edu/ 7Problem StatementProblem Statement•Two orthogonal issues•What channels to assign?•How to assign?•Constraints:•Limited spectrum•Spatial reuse of spectrum permitted•Subchannels have to be contiguousWe present a distributed algorithm to perform channel allocation under these constraints.http://nesl.ee.ucla.edu/ 8ExampleExample•Spatial reuse is NOT permitted in any three link chain.•Each link has a pre-specified bandwidth requirement.0123 45678206181128731712http://nesl.ee.ucla.edu/ 9First level of clusteringFirst level of clusteringLowest ID clustering algorithm [Lin & Gerla]0123 45678Ordinary node Clusterheadhttp://nesl.ee.ucla.edu/ 10Second level of clusteringSecond level of clustering0123 45678Masterhttp://nesl.ee.ucla.edu/ 11PollingPolling•Each Master polls its clusterheads, granting them permission to allocate frequencies.0123 45678http://nesl.ee.ucla.edu/ 12Polling (contd.)Polling (contd.)•Each clusterhead assigns frequencies to its links.0123 45678Link Requirement Assigned0-1 20 0-190-2 6 20-253-2 18 26-433-4 11 44-545-2 28 55-825-6 7 83-895-7 12 90-1018-7 17 0-166-7 3 102-104http://nesl.ee.ucla.edu/ 13AlgorithmAlgorithm•Combines the features of clustering and polling1. Organize into clusters based on lowest ID2. Organize the clusters into super-clusters (Each super-cluster can allocate frequencies in parallel)3. Master assigns channels to its ordinary neighbors4. Master polls each clusterhead, asking it to allocate channels within its cluster, given the allocation restrictions.5. The clusterhead allocates contiguous sub-channels to its links and when done, returns an acknowledgement to the master along with the allotted sub-channels.http://nesl.ee.ucla.edu/ 14SimulationsSimulations•Simulated using PARSEC•Measures of performance•Scalability in terms of protocol messages•Comparison with optimal assignment (graph-theoretic approach)•Simulation parameters•Number of nodes•Connectivity of networkhttp://nesl.ee.ucla.edu/ 15ScalabilityScalabilityNo. of protocol messages vs. No. of nodes01002003004005006007000 20 40 60 80 100 120No. of nodesNo. of messagesNo. of messages vs. Connectivity0501001502002503003504004500 2 4 6 8 10 12ConnectivityNo. of messageshttp://nesl.ee.ucla.edu/ 16ComparisonComparisonNo of subchannels vs. Connectivity020040060080010001200140016000 2 4 6 8 10 12ConnectivityNo. of subchannelsNo of subchannels vs. No of nodes0204060801001201401601800 20 40 60 80 100 120No of nodesNo. of subchannelshttp://nesl.ee.ucla.edu/ 17ConclusionsConclusions•Presented a distributed algorithm for contiguous channel allocation in wireless ad hoc networks•Validated through PARSEC simulations•Future work•Incorporate traffic-based adaptation into the scheme•Possible application•As a wireless ad hoc backbone in the MINUTEMAN