MOBILE AD HOC NETWORKS Mobile Ad Hoc Networks Energy-Efficient Real-Time Data Communications by BULENTTAVLI University of Rochester, NY, U.S.A. and WENDI HEINZELMAN University of Rochester, NY, U.S.A. AC.I.P. Catalogue record for this book is available from the Library of Congress. ISBN-10 1-4020-4632-4 (HB) ISBN-13 978-1-4020-4632-2 (HB) ISBN-10 1-4020-4633-2 ( e-book) ISBN-13 978-1-4020-4633-9 (e-book) Published by Springer, P.O. Box 17, 3300 AADordrecht, The Netherlands. www.springer.com Printed on acid-free paper All Rights Reserved © 2006 Springer No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written permission from the Publisher, with the exception of any material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Printed in the Netherlands. Toourfamilies Contents Dedication v ListofFigures xi ListofTables xix Preface xxiii 1. INTRODUCTION 1 1.1 CharacteristicsofMANETs 2 1.2 ImportanceofQoSandEnergyEfficiencyinMANETs 4 1.3 ScopeandNoveltyoftheBook 5 1.4 HighLevelOverviewoftheBook 7 2. MANETFUNDAMENTALS 9 2.1 PerformanceMetrics 9 2.2 TheLayeredCommunicationNetwork 11 2.3 Cross-layerDesign 23 2.4 Mobility 26 3. MEDIUMACCESSCONTROL 31 3.1 FixedAssignmentMACProtocols 31 3.2 RandomAccessMACProtocols 37 4. ROUTING 47 4.1 UnicastRouting 47 4.2 MulticastRouting 48 4.3 BroadcastingRouting 50 4.4 HierarchicallyOrganizedNetworks 51 viii Contents 5. ENERGYEFFICIENCYANDQOS 59 5.1 EnergyEfficiency 59 5.2 QualityofService 67 6. SH-TRACEPROTOCOLARCHITECTURE 71 6.1 Introduction 71 6.2 ProtocolArchitecture 73 6.3 SimulationsandAnalysis 77 6.4 Discussion 96 6.5 Summary 98 7. MH-TRACEPROTOCOLARCHITECTURE 99 7.1 Introduction 99 7.2 ProtocolArchitecture 100 7.3 SimulationsandAnalysis 108 7.4 Discussion 123 7.5 Summary 124 8. EFFECTSOFCHANNELERRORS 125 8.1 Introduction 125 8.2 RelatedWork 128 8.3 AnalyticalModel 129 8.4 SimulationsandAnalysis 138 8.5 Summary 146 9. REAL-TIMEDATABROADCASTING 147 9.1 Introduction 147 9.2 BroadcastArchitectures 148 9.3 SimulationEnvironment 152 9.4 LowTrafficRegime 156 9.5 HighTrafficRegime 167 9.6 Summary 172 10.NB-TRACEPROTOCOLARCHITECTURE 175 10.1 Introduction 175 10.2 ProtocolArchitecture 175 10.3 SimulationsandAnalysis 185 10.4 Summary 198 Contents ix 11.MC-TRACEPROTOCOLARCHITECTURE 199 11.1 Introduction 199 11.2 ProtocolArchitecture 200 11.3 SimulationsandAnalysis 208 11.4 Summary 210 12.CONCLUSIONSANDFUTURERESEARCHDIRECTIONS 211 12.1 Conclusions 211 12.2 FutureResearchDirections 218 Bibliography 221 Appendices 235 A Multi-StageContentionwithFeedback 235 A.1 GenericDR-TDMAFrameStructure 236 A.2 Single-StageS-ALOHAContention 236 A.3 Multi-StageContention 237 A.4 OptimalMulti-StageContention 238 A.5 Discussion 239 A.6 Summary 241 B EffectsofClusterheadSeparationonMH-TRACE 243 B.1 ModifiedClusterCreationandMaintenanceAlgorithms 243 B.2 SimulationResultsandDiscussion 244 B.3 Summary 251 C BroadcastCapacityofWirelessAdHocNetworks 253 C.1 Background 253 C.2 UpperBoundonBroadcastCapacity 255 C.3 Summary 256 D GlossaryofTerms 257 Index 261 AboutTheAuthors 265 List of Figures 1.1 TRACEfamilyofprotocolarchitectures. 8 2.1 MANETprotocolperformancemetrics. 10 2.2 TCP/IPreferencemodel. 12 2.3 FreeSpaceandTwo-RayGroundpropagationmodels. 14 2.4 IllustrationofASK,BFSK,andBPSK. 16 2.5 Successiveencapsulation. 18 2.6 Blockdiagramofadatatransmissionsystem. 18 2.7 Illustrationofunicast,multicast,andbroadcastrouting. S and D represent the source and destination nodes, respectively. 21 2.8 UDPandTCPpacketformats. 22 2.9 Audiocommunicationsthroughthenetworkstack. 24 2.10 Theleftcolumnshowsaconventionallayeredprotocol stack. The middle column shows a cross-layer design, where layers share information while keeping the layers intact. Therightcolumnshowsanothercross-layer designwhereapplicationandtransportlayersare combinedintoasingleentityandnetworkandMAClayers aremerged. 25 2.11 Average node speed for a simulation scenario created bytherandomwaypointmobilitymodelwith80nodes over 1 km by 1 km area. The node speeds are chosen randomlyfrom[0,5m/s]withzeropausetime. 27 2.12 Node distribution produced at 1000 s of the mobility scenario by the random waypoint mobility model with 80nodesover1kmby1kmarea. Thenodespeedsare chosenrandomlyfrom[0,5m/s]withzeropausetime. 28 xii ListofFigures 2.13 Combined snapshots of node positions in time plotted over a 500 m by 500 m grid. The lower-left corner of the figure is the snapshot at time 0.0 s. The upper-left cornershowsthenodesinbunchingmodeat50.0s. The finalpositionofthenodesat100.0sisintheupper-right cornerofthefigure. 29 3.1 NodeBisclosertonodeCthannodeA.Simultaneous transmissionsbynodeAandnodeBdonotresultin collisions because the signal strength of the transmission by node B at node C’s receiver (P ) is much higher B,C thanthatofnodeA(P ). Thiseffectisknownas“capture”. 32 A,C 3.2 Fixedassignmentmediumaccesscontrolprotocols: (a) TimeDivisionMultipleAccess(TDMA),(b)Frequency Division Multiple Access (FDMA), (c) Code Division MultipleAccess(CDMA). 32 3.3 Digital European Cordless Telephone (DECT) uses TDMA as the MAC layer. The frame length is 10 ms consisting of 24 time slots of duration 417 s, of which 12 are used for downlink (i.e., from the base station to themobilenodes)and12areusedforuplink(i.e.,from themobilenodestothebasestation). 33 3.4 GlobalSystemforMobilecommunication(GSM)uses FDMA as the MAC layer. The frequency band is divided into 256 channels (128 channels for uplink and 128 channels for downlink), and the carriers are separatedby200kHz. 34 3.5 IllustrationofFrequencyHoppingSpreadSpectrum(FHSS). 36 3.6 ALOHAmediumaccess. 37 3.7 ALOHA and Slotted ALOHA throughput versus offeredload. 38 3.8 SlottedALOHAmediumaccess. 38 3.9 Comparisonofthethroughputefficiencyversusoffered loadfortheALOHAandCSMAschemes. The propagationdelayissmallwhencomparedtothepacket length. 39 3.10 Startopologynetwork—thebasestationisinthecenter. 40 3.11 Fullyconnectedsingle-hopwirelessnetwork. 41 3.12 Illustrationoftransmitandcarriersenseregions. 42 ListofFigures xiii 3.13 The hidden terminal problem: Node A is cannot hear nodeC,andviceversa. Therefore,simultaneous transmissionsdestinedtonodeBbynodeAandnodeC will resultincollisions. 43 3.14 Theexposedterminalproblem. NodeCistransmitting todestinationD.Sincethechannelisbusyduetonode C’s transmission, node B cannot transmit. However, nodeB’stransmissionfornodeAwillnotinterferewith node C’s transmission to node D. Thus, by preventing node B’s transmission, bandwidth is wasted due to the underutilizationofthechannel. 43 3.15 IllustrationofIEEE802.11DCFfour-wayhandshaking. 44 4.1 Illustration of the lowest-ID clustering algorithm. Squares, triangles, and disks represent clusterheads, gateways,andordinarynodes,respectively. 54 4.2 Illustrationofthehighestdegree(connectivity)clustering algorithm. Squares, triangles, and disks represent clusterheads,gateways,andordinarynodes,respectively. 56 5.1 Aironet PC4800 PCMCIA Network Interface Card power consumption in transmit (2500 mW), receive (900mW),idle(110mW),andsleep(20mW)modes. 61 5.2 SchematicofAironetPC4800PCMCIANetwork interfaceCard. 61 5.3 Energydissipatedontransmit,receive,idle,andcarrier sense modes for ooding with IEEE 802.11 in an 800 m by800mnetworkwith40nodes. 63 5.4 Delay-PacketDeliveryRatio(PDR)utilityfunction. 68 5.5 IllustrationofR-ALOHAmediumaccesscontrol. “ ” “ Notation X|Y standsfor ReservationforX, ” Transmission byY . 69 5.6 IEEE802.15.3superframe. 70 6.1 OverviewofSH-TRACEoperation. 72 6.2 SH-TRACEframeformat. 74 6.3 Average number of voice packets per frame vs. total numberofnodeswithactivevoicesources. 80 6.4 Average number of voice packets delivered per frame pernodevs. numberofnodes. 82