EFFICIENT COMMUNICATION PROTOCOLS FOR UNDERWATER ACOUSTIC SENSOR NETWORKS AThesis Presentedto TheAcademicFaculty by DarioPompili InPartialFulfillment oftheRequirementsfortheDegree DoctorofPhilosophyinthe SchoolofElectricalandComputerEngineering GeorgiaInstituteofTechnology August2007 EFFICIENT COMMUNICATION PROTOCOLS FOR UNDERWATER ACOUSTIC SENSOR NETWORKS Approvedby: ProfessorIanF.Akyildiz,Advisor ProfessorWilliamD.Hunt SchoolofElectricalandComputer SchoolofElectricalandComputer Engineering Engineering GeorgiaInstituteofTechnology GeorgiaInstituteofTechnology ProfessorFaramarzFekri ProfessorMostafaH.Ammar SchoolofElectricalandComputer CollegeofComputing Engineering GeorgiaInstituteofTechnology GeorgiaInstituteofTechnology ProfessorRaghupathySivakumar DateApproved: June5th,2007 SchoolofElectricalandComputer Engineering GeorgiaInstituteofTechnology Ad Alessandra iii ACKNOWLEDGEMENTS The author wishes to thank most sincerely Prof. Ian F. Akyildiz for his continuing guid- ance in the completion of this work, as well as for his valuable support as advisor during the entire Ph.D. program. His mentorship was paramount in providing a well rounded ex- perience,whichIwilltreasureinmycareer. To all the academic members of the Electrical and Computer Engineering Department attheGeorgiaInstituteofTechnology,Iwishtoexpressmydeepestgratitudeforexcellent advice,constructivecriticism,helpfulandcriticalreviewsthroughoutthePh.D.program. A special thank goes to Drs. Fekri, Sivakumar, Hunt, and Ammar, who kindly agreed toserveinmyPh.D.DefenseCommittee. The author is indebt to his friend and colleague Tommaso Melodia for all the valuable workdonetogetherduringthecompletionofthePh.D.program. Aswell,theauthorwould like to thank all former and current members of the Broadband and Wireless Networking Laboratoryforsharingthislearningexperience. Last but not least, the author is grateful to the many anonymous reviewers that with theirunselfishcommentsgreatlyimprovedthecontentofthepapersfromwhichthisthesis hasbeenpartlyextracted. iv TABLE OF CONTENTS DEDICATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii ACKNOWLEDGEMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv LISTOFTABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii LISTOFFIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix SUMMARY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii I INTRODUCTION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 OrganizationoftheThesis . . . . . . . . . . . . . . . . . . . . . . . . . 5 II RESEARCHCHALLENGESFORUNDERWATERACOUSTICSENSORNET- WORKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 CommunicationArchitectures . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 DesignChallenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.4 BasicsofUnderwaterAcousticPropagation . . . . . . . . . . . . . . . . 21 2.5 PhysicalLayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 DataLinkLayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.7 NetworkLayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.8 TransportLayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.9 ApplicationLayer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.10 ExperimentalImplementationsofUnderwaterSensorNetworks . . . . . 40 III DEPLOYMENTANALYSISFORUNDERWATERACOUSTICSENSORNET- WORKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.3 CommunicationArchitectures . . . . . . . . . . . . . . . . . . . . . . . 43 3.4 Deploymentina2DEnvironment . . . . . . . . . . . . . . . . . . . . . 45 v 3.5 Deploymentina3DEnvironment . . . . . . . . . . . . . . . . . . . . . 62 IV DISTRIBUTEDROUTINGALGORITHMSFORUNDERWATERACOUSTIC SENSORNETWORKS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.3 NetworkModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.4 PacketTrainandOptimalPacketSize . . . . . . . . . . . . . . . . . . . 73 4.5 Delay-insensitiveRoutingAlgorithm . . . . . . . . . . . . . . . . . . . 85 4.6 Delay-sensitiveRoutingAlgorithm . . . . . . . . . . . . . . . . . . . . 89 4.7 PerformanceEvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 94 V ARESILIENTROUTINGALGORITHMFORLONG-TERMUNDERWATER MONITORINGMISSIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 5.2 BasicsoftheResilientRoutingAlgorithm . . . . . . . . . . . . . . . . . 108 5.3 PerformanceEvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 114 VI A CDMA MEDIUM ACCESS CONTROL PROTOCOL FOR UNDERWATER ACOUSTICSENSORNETWORKS . . . . . . . . . . . . . . . . . . . . . . 122 6.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 6.2 RelatedWork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.3 UW-MAC:ADistributedCDMAMACforUW-ASNs . . . . . . . . . . 126 6.4 PowerandCodeSelf-assignmentProblem . . . . . . . . . . . . . . . . . 130 6.5 PerformanceEvaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 136 VII CROSS-LAYER COMMUNICATION FOR MULTIMEDIA APPLICATIONS INUNDERWATERACOUSTICSENSORNETWORKS . . . . . . . . . . . 150 7.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 7.2 Cross-layerResourceAllocationFramework . . . . . . . . . . . . . . . 153 7.3 Cross-layerRouting/MAC/PHYSolutionforDelay-tolerantApplications 161 7.4 Cross-layerRouting/MAC/PHYSolutionforDelay-sensitiveApplications168 7.5 ProtocolOperationoftheCross-layerSolution . . . . . . . . . . . . . . 171 vi VIII CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 LISTOFACRONYMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 VITA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 vii LIST OF TABLES 1 AvailablebandwidthfordifferentrangesinUW-Achannels . . . . . . . . . 21 2 Evolutionofmodulationtechnique . . . . . . . . . . . . . . . . . . . . . . 26 3 Redundantsensors ∆N∗ tocompensateforfailures . . . . . . . . . . . . . 62 4 Simulationperformanceparameters . . . . . . . . . . . . . . . . . . . . . 94 5 Scenarios2and3: SurfaceStationandAverageEnergyperBit . . . . . . . 101 6 SourceBlockProbability(SBP)vs. ObservationTime . . . . . . . . . . . . 114 viii LIST OF FIGURES 1 Architecturefor2Dunderwatersensornetworks . . . . . . . . . . . . . . . 10 2 Architecturefor3Dunderwatersensornetworks . . . . . . . . . . . . . . . 12 3 Architecturefor3DunderwatersensornetworkswithAUVs . . . . . . . . 13 4 Internalorganizationofanunderwatersensornode . . . . . . . . . . . . . 17 5 PathlossofshortrangeshallowUW-Achannelsvs. distanceandfrequency inband 1−50kHz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6 Triangular-griddeployment. Gridstructureandsidemargins . . . . . . . . 47 7 Triangular-griddeployment. Uncoveredarea . . . . . . . . . . . . . . . . 47 8 Triangular-griddeployment. Sensingcoverage . . . . . . . . . . . . . . . 49 9 Minimum number of sensors in triangular-grid deployment vs. sensor dis- tanceoversensingrange. A = 100x100m2 . . . . . . . . . . . . . . . . . 51 1 10 Minimum number of sensors in triangular-grid deployment vs. sensor dis- tanceoversensingrange. A = 300x200m2 . . . . . . . . . . . . . . . . . 51 2 11 Minimum number of sensors in triangular-grid deployment vs. sensor dis- tanceoversensingrange. A = 1000x1000m2 . . . . . . . . . . . . . . . 52 3 12 Trajectoryofasinkingobject . . . . . . . . . . . . . . . . . . . . . . . . . 53 13 Average horizontal displacement of sensors and uw-gateways vs. current velocity(forthreedifferentdepths) . . . . . . . . . . . . . . . . . . . . . . 58 14 Maximum and average sensor-gateway distance vs. number of deployed gateways(inthreedifferentvolumes,andwith vmax = 1m/s) . . . . . . . 59 c 15 Normalized average and standard deviation of number of sensors per uw- gateway vs. number of deployed gateways (for grid and random deploy- mentstrategies,inthreedifferentvolumes,andwith vmax = 1m/s) . . . . 59 c 16 Deployment surface area for unknown (a) and known (b) current direction β,givenabottomtargetarea lxh . . . . . . . . . . . . . . . . . . . . . . . 61 17 Three-dimensionalscenario. 3Dcoveragewitha3Drandomdeployment . 65 18 Three-dimensional scenario. Optimized 3D coverage with a 2D bottom- randomdeployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 19 Three-dimensional scenario. Optimized 3D coverage with a 2D bottom- griddeployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 20 Theoreticalandexperimentalsensingrange . . . . . . . . . . . . . . . . . 66 ix 21 Theoretical, Fisher&Simon’s, and Thorp’s medium absorption coefficient α(f)vs. frequencyf ∈ [10−1,102]kHz . . . . . . . . . . . . . . . . . . . 74 22 Single-packettransmissionscheme . . . . . . . . . . . . . . . . . . . . . . 75 23 Underwater and terrestrial channel utilization efficiency for different dis- tances(100m−500m). Underwaterchannelefficiencyvs. packetpayload sizewithoutFEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 24 Underwater and terrestrial channel utilization efficiency for different dis- tances(100m−500m). Underwaterchannelefficiencyvs. packetpayload sizewith (255,239)Reed-SolomonFEC . . . . . . . . . . . . . . . . . . . 78 25 Underwater and terrestrial channel utilization efficiency for different dis- tances (100m−500m). Terrestrial channel efficiency vs. packet payload sizewithoutFEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 26 Packet-trainperformance. Packet-traintransmissionscheme . . . . . . . . 80 27 Packet-train performance. Underwater packet efficiency vs. packet pay- loadsizefordifferentdistances(100mand500m) . . . . . . . . . . . . . 84 28 Packet-train performance. Packet-train efficiency vs. packet-train payload lengthfordifferentdistances(100m-500m) . . . . . . . . . . . . . . . . . 85 29 Scenario 1: Delay-insensitive routing. Average node residual energy vs. time,fordifferentlinkmetrics . . . . . . . . . . . . . . . . . . . . . . . . 96 30 Scenario 1: Delay-insensitive routing. Average and standard deviation of numberofhopsvs. time,fordifferentlinkmetrics . . . . . . . . . . . . . . 97 31 Scenario 1: Delay-insensitive routing. Average packet delay vs. time, for differentlinkmetrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 32 Scenario 1: Delay-insensitive routing. Distribution of data delivery delays fortheFullMetric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 33 Scenario 1: Delay-insensitive routing. Average and standard deviation nodequeueingdelays,fordifferentlinkmetrics . . . . . . . . . . . . . . . 99 34 Scenario 1: Delay-insensitive routing. Average and standard deviation of numberofpackettransmissions,fordifferentlinkmetrics . . . . . . . . . . 99 35 Scenario 2: Delay-insensitive routing. Packet delay and average delay vs. timeforsourcerateequalto 150bps . . . . . . . . . . . . . . . . . . . . . 101 36 Scenario 2: Delay-insensitive routing. Packet delay and average delay vs. timeforsourcerateequalto 300bps . . . . . . . . . . . . . . . . . . . . . 102 37 Scenario 2: Delay-insensitive routing. Packet delay and average delay vs. timeforsourcerateequalto 600bps . . . . . . . . . . . . . . . . . . . . . 102 x