Wireless Network Design_ Optimization Models and Solution Procedures.pdf下载

1 IntroductiontoOptimizationinWirelessNetworks............... 1 JeffKennington,EliOlinick,andDineshRajan PartIBackground 2 IntroductiontoWirelessCommunications....................... 9 DineshRajan 2.1 Introduction.............................................. 9 2.1.1 LayeredArchitecture..............................10 2.1.2 DigitalCommunicationSystem......................11 2.2 DigitalModulationinSingleUserPoint-to-pointCommunication.14 2.3 InformationTheoreticCapacityandCoding...................18 2.4 ChannelCoding..........................................23 2.4.1 BlockCodes......................................24 2.4.2 ConvolutionalCodes...............................26 2.5 MultiuserCommunication.................................27 2.5.1 DataLinkLayerRandomAccessMethods............28 2.5.2 PhysicallayerMultiuserSignalingSchemes...........32 2.5.3 PowerControl....................................39 2.6 AdvancedTransceiverMethods.............................42 2.6.1 MultipleAntennaSystems..........................43 2.6.2 Scheduling,Rate,andPowerControl.................44 2.7 Conclusions..............................................44 References.....................................................44 3 ChannelModelsforWirelessCommunicationSystems............ 47 K.V.S.Hari 3.1 Introduction..............................................47 3.2 WirelessChannel.........................................47 3.3 PropagationModelforWirelessChannel......................48 3.4 MathematicalModelingofWirelessChannels.................49 vii viii Contents 3.4.1 ExperimentstoCharacterizeWirelessChannels........50 3.4.2 RayleighandRiceanFlatFadingChannels............52 3.4.3 DopplerSpreadDuetoRelativeMotionBetween TransmitterandReceiverandCoherenceTime.........53 3.4.4 FiniteImpulseResponseChannelModelforFrequency SelectiveFadingChannels..........................55 3.4.5 DelaySpreadParameters...........................55 3.4.6 DecorrelationDistanceoftheChannel................56 3.5 ChannelModelsforSystemsusingMultipleAntennas..........57 3.5.1 SpatialWirelessChannelModelsusingGeometry......57 3.5.2 GeometricallyBasedSingle-BounceStatisticalModels..58 3.6 Conclusion...............................................61 References.....................................................61 4 AnIntroductiontoIntegerandLarge-ScaleLinearOptimization... 65 J.ColeSmithandSibelB.Sonuc 4.1 Introduction..............................................65 4.2 BasicsofModelingandOptimization........................66 4.2.1 FoundationsofOptimizationModels.................66 4.2.2 LinearProgrammingProblems......................68 4.2.3 Duality..........................................71 4.2.4 ModelingwithNonlinearandDiscreteVariables.......74 4.2.5 IntegerProgrammingMethods......................75 4.3 LargeScaleOptimization...................................81 4.3.1 BendersDecomposition............................82 4.3.2 Dantzig-WolfeDecomposition......................87 4.3.3 LagrangianOptimization...........................92 4.3.4 OtherMethods....................................94 References.....................................................96 PartIIOptimizationProblemsforNetworkswithInfrastructure 5 MathematicalProgrammingModelsforThirdGenerationWireless NetworkDesign.............................................101 EliOlinick 5.1 Introduction..............................................101 5.2 TowerLocationandSubscriberAssignmentinCDMANetworks.104 5.2.1 TheCoreModel...................................104 5.2.2 ChallengesinSolvingtheCoreModel................107 5.3 ExtensionstotheCoreModel...............................107 5.3.1 SIR-BasedPowerControl..........................108 5.3.2 ProfitMaximizationwithMinimum-ServiceRestrictions109 5.3.3 Infrastructure.....................................110 5.3.4 ThePower-RevenueTrade-Off......................113 5.3.5 AdditionalDesignConsiderations....................114 5.4 SolvingtheModels........................................116 Contents ix 5.4.1 TheNearestAvailableTowerPrinciple................116 5.4.2 RandomizedGreedySearch.........................117 5.4.3 ImprovingBranch-and-BoundPerformance...........118 5.4.4 DealingwithNumericalInstability...................120 5.4.5 ReducingProblemSize.............................121 References.....................................................122 6 OptimizationBasedWLANModelingandDesign................127 JeffKennington,JasonKratz,andGheorgheSpiride 6.1 Introduction..............................................128 6.2 LiteratureSurvey.........................................129 6.2.1 SiteSurveys......................................129 6.2.2 CoverageModels..................................130 6.2.3 ChannelAssignment...............................131 6.2.4 AccessPointPlacement............................134 6.2.5 ProprietaryDesignTools...........................134 6.2.6 CurrentState-of-the-Art............................136 6.3 AMaximimumCapacity-OrientedModel.....................136 6.3.1 SolutionTechniquesfortheCapacity-OrientedModel...140 6.3.2 EmpiricalAnalysis................................141 6.4 SummaryandConclusions.................................143 References.....................................................145 7 SpectrumAuctions..........................................147 KarlaHoffman 7.1 Introduction..............................................147 7.2 SomeAuctionTermsandMechanisms.......................148 7.3 TheFirstSpectrumAuction:TheNewZealandExperiment......152 7.4 EvolutionoftheUSSimultaneousAscendingAuction(SAA) Design..................................................153 7.5 CombinatorialAuctionDesignsandtheirUseforSpectrum Allocation...............................................160 7.5.1 Sealed-bidCombinatorialDesigns...................161 7.5.2 TwoCombinatorialAscendingAuctionDesigns........165 7.6 TheNeedforBidder-aideTools.............................172 7.7 Conclusions..............................................173 References.....................................................174 8 TheDesignofPartiallySurvivableNetworks....................177 SyamMenon 8.1 Introduction..............................................177 8.2 TheSinglePeriodProblem.................................179 8.2.1 ProblemFormulation..............................179 8.2.2 ReductiontoaBinaryKnapsackProblem.............180 8.3 TheMulti-periodProblem..................................182 8.3.1 ProblemDescriptionandFormulations................182 x Contents 8.3.2 TheSolutionProcedure............................184 8.3.3 ComputationalExperiments.........................188 8.4 TheSinglePeriodProblemwithCapacityRestrictions..........189 8.4.1 APartitioningFormulation..........................191 8.4.2 ComputationalExperiments.........................194 8.5 Conclusions..............................................194 References.....................................................196 PartIIIOptimizationProblemsinAdHocNetworks 9 RoutinginMobileAdHocNetworks...........................199 KhaldounAlAghaandStevenMartin 9.1 AdHocNetworks.........................................199 9.2 WhatisRouting?.........................................200 9.3 AdHocintheLinkLayer..................................202 9.3.1 AdHocModeinWi-Fi.............................203 9.3.2 BluetoothLinkLayer..............................205 9.4 AdHocRoutingProtocols..................................207 9.4.1 IntroductiontoAdHocRoutingProtocols.............207 9.4.2 ReactiveProtocols.................................208 9.4.3 ProactiveProtocols................................210 9.5 QualityofServiceinAdHocNetworks.......................211 9.5.1 FQMM(FlexibleQoSModelforMANETs)...........212 9.5.2 CEDAR(Core-ExtractionDistributedAdhocRouting)..213 9.5.3 TBP(Ticket-basedProbing).........................213 9.5.4 INSIGNIA.......................................214 9.5.5 SWAN(StatelessWirelessAdhocNetwork)...........214 9.5.6 QOLSR(QualityofServiceforOLSR)...............215 9.6 Conclusion...............................................216 References.....................................................216 10 CompactIntegerProgrammingModelsforPower-optimalTreesin AdHocWirelessNetworks...................................219 DagHauglandandDiYuan 10.1 Introduction..............................................219 10.1.1 ProblemOverview.................................221 10.1.2 OutlineoftheChapter..............................222 10.2 ProblemDefinitions.......................................222 10.2.1 NotationandAssumptions..........................222 10.2.2 MinimumEnergyBroadcastandMulticast............224 10.2.3 RangeAssignment................................225 10.2.4 OptimalTreesandArborescence:IllustrativeExample..226 10.3 NetworkFlowModelsforMET.............................228 10.3.1 ModelsandAnalysis...............................229 10.3.2 ModelsBasedonIncrementalPower.................232 10.4 NetworkFlowModelsforRAP.............................233 Contents xi 10.5 AStrongMulti-treeModelforRAP.........................234 10.5.1 TheModel.......................................234 10.5.2 LPStrength......................................236 10.6 ExperimentalResults......................................237 10.6.1 ResultsforMET..................................238 10.6.2 ResultsforRAP..................................239 10.7 ConcludingRemarks......................................243 References.....................................................244 11 ImprovingNetworkConnectivityinAdHocNetworksUsing ParticleSwarmOptimizationandAgents.......................247 AbdullahKonak,OrhanDengiz,andAliceE.Smith 11.1 Introduction..............................................247 11.2 Background..............................................248 11.3 ProposedMANETManagementSystemandProblemDescription250 11.3.1 ObjectivesandEvaluatingNetworkConnectivity.......250 11.3.2 FutureUserLocationPrediction.....................251 11.3.3 OptimizationProblemandDeploymentDecision.......252 11.4 ParticleSwarmOptimizationandImplementation..............253 11.4.1 ParticleSwarmOptimization(PSO)..................253 11.4.2 TheOptimizationProcedure........................255 11.4.3 Semi-IntelligentAgentNodeBehavior................257 11.5 ComputationalExperiments................................258 11.5.1 MobilitySimulationEnvironment....................259 11.5.2 TheEffectofNumberofAgents,FutureLocation Prediction,andClustering..........................260 11.5.3 ComparativePerformanceofthePSOAlgorithm.......262 11.6 Conclusions..............................................264 References.....................................................265 PartIVOptimizationProblemsintheOperationofWirelessNetworks 12 Simulation-BasedMethodsforNetworkDesign..................271 MarinaAguado,JasoneAstorga,NereaToledoandJonMatias 12.1 Introduction..............................................272 12.2 SimulationMethodologies:aTaxonomy......................274 12.3 ValidatingDiscreteEventSimulations:theRandomNumber SeedandtheConfidenceInterval............................276 12.4 SurveyofSimulationforWirelessNetworkDesign.............280 12.5 CaseStudies.............................................281 12.5.1 TrafficModelingApplication........................282 12.5.2 NetworkabilityandImpactAssessmentApplication.....284 12.5.3 NetworkOperationsandCapacityPlanning............285 12.5.4 NetworkResearchandDevelopment.................286 12.5.5 NetworkEmulationwithClick......................290 12.6 Conclusions..............................................292 xii Contents References.....................................................292 13 OptimizationofWirelessBroadband(WiMAX)Systems...........295 HangJinandLiGuo 13.1 Introduction..............................................295 13.2 BriefDescriptionofWiMAX...............................297 13.2.1 WiMAXPhysicalLayer............................297 13.2.2 WiMAXMACLayer..............................300 13.3 RadioResourceAllocationOptimization......................302 13.3.1 ModulationCodingSchemeSelection................303 13.3.2 MIMOModeSelection.............................305 13.3.3 PowerControl....................................307 13.3.4 LinkAdaptation...................................309 13.4 SchedulingOptimization...................................310 13.4.1 RoundRobin.....................................310 13.4.2 ProportionalFair..................................311 13.4.3 MaxSystemThroughput...........................312 13.4.4 WiMAXQoSPolicy...............................313 13.5 SystemSimulations.......................................315 13.6 Conclusion...............................................318 References.....................................................319 14 CrossLayerSchedulinginWirelessNetworks...................321 NitinSalodkarandAbhayKarandikar 14.1 Introduction..............................................321 14.2 WirelessChannelCapacity.................................322 14.2.1 Point-to-PointCapacitywithPerfectTransmitterCSI...324 14.2.2 MultiuserCapacitywithPerfectTransmitterCSIonthe Uplink...........................................326 14.3 AFrameworkforCrossLayerScheduling.....................329 14.3.1 OpportunisticScheduling...........................329 14.3.2 EnergyEfficientScheduling.........................330 14.3.3 SystemModelforCentralizedScheduling.............330 14.4 FairScheduling...........................................333 14.4.1 NotionsofFairness................................334 14.4.2 FairSchedulingAlgorithms.........................334 14.5 PowerOptimalScheduling.................................335 14.5.1 SingleUserScheduling.............................336 14.5.2 MultiuserUplinkScheduling........................342 14.6 SchedulingSchemesthatMaximizeThroughput...............345 14.6.1 ThroughputOptimalScheduling.....................346 14.6.2 DelayOptimalScheduling..........................347 References.....................................................350