Wireless Sensor Networks Phd Thesis 2010 Ford

Thesis 25.10.2019

Inthehierarchicaltopologyconstructionapproach,acommunicationhierarchyiscreatedinwhichareducedsubsetofthenodesisselectedandgivenmoreresponsibilities onbehalfofasimpliedandreducedfunctionalityforthemajorityofthenodes.

Theprocessworks fromthesetofnodesthatarepartofthetreeattime t. Thenodesmaybetransmittingatfullpower,whichisnotnecessarytoreachthe nextnodeintheirpathtowardsthesink. Finally,wirelesssensordevicescanbeequippedwithactuators toperformactionsuponcertainconditions. Inthetimeyouspentreadingthisdissertation,billionsofbitswillbe generatedwiththeonlypurposeofgatheringdataaboutvirtuallyeverything:howmany carsarecrossingtheSkywaybridgeinSt. Providingthatcommunicationisnotalwaysbidirectional,linksaremodeled asunidirectionaledges. Theprotocolsinthesecondbrancharemoreorientedinprovidingcoverageinthe area,evenif,insomecases,connectivityisnotguaranteed.

Department of E. Inbothphases ofthealgorithm,competitionisusedtodeterminethebestcandidatestobeincludedin theindependentsetsandthenaltree. Multihop broadcast is complex in duty-cycled WSNs due to non simultaneous wakeup in neighborhoods. Also,iftheoriginal graph G isconnected,thenthereducedgraph G 0 isalsoconnected.

Bilal loukan thesis biyak

Chapter3describesthe methodologyusedfortheperformanceevaluationofthedifferenttopologyconstruction andmaintenanceprotocolsintroducedinthisdissertation,includingboththeanalytical andsimulation-basedapproaches.

DT hasamessagecomplexityof Phd n andcomputationalcomplexityof O nlogn. TheRNGcanbeeasilydeterminedusingalocalalgorithm withmessagecomplexity O n andcomputationalcomplexity O n 2. Thesetofedges E aretheunionofallpairscreatedbyeachvertexandalltheadjacentverticescontainedin itsopenball. The 15 PAGE 33 evaluationoftheseprotocolsisbasedonthecomparisonofaveragebehaviorin randomtopologiesagainstotheralgorithmsintheliterature,andagainsttheoretical optimaldeployments.

InthecaseofapproximatesolutionstotheMCDSproblem,manyalgorithmshavebeen provedtobeapproximationalgorithmsoftheoptimalsolution. Then,oneof theGraynodesisalsocoloredBlack,whichmakesitsneighborsGray. However,assumingthatthenodesaredeployedintheEuclideanspace,better approximationratioscanbeachieved. Thisisthesecondapproachonthecentralizedparadigm:thewellknownRangeAssignmentRAproblem,whichisdenedasthefunctionthatndsa stronglyconnectedgraphandminimizesthetotalcostofthenetwork,whichisgivenby thesummationofthetransmissionpowerusedbyall n sensors.

Ifduringthistime, itdoesnotreceiveanyBlackmessageinresponse,andithasthehighestweight,itbecomesaBlacknode,andtheprocessstartsagain. Thegrowingatree techniquehascharacteristicsthataredesirableforroutingprotocols,likeanorganized structurethatallowsimplementingroutingbasedonthesimpliedlogicalstructure,hierarchicaladdressing,queryingbasedontreesearches,etc. Then,basedonthereplymessages,theinitiatorchecksif allitsneighborsarecoveredbyatleastoneactivenodedifferentfromitself.

College admission essay editing services

Comparison of clustering algorithms and protocols for wireless sensor networks. Ottawa, ON, Canada; A centralized energy-efficient routing protocol for wireless sensor networks. Heinzelma WB. Application-specific protocol architectures for wireless networks [PhD thesis]. Massachusetts Institute of Technology; Res J Inform Tech. Comput Electr Eng. Kwon TJ, Gerla M. Efficient flooding with Passive Clustering PC in ad hoc networks. A density and distance based cluster head selection algorithm in sensor networks. LCM: a link-aware clustering mechanism for energy-efficient routing. IEEE Sensors. We also study asymmetric quorum-based wakeup scheduling for two-tiered network topologies for further improving energy efficiency. Heterogenous duty-cycling causes transmission latencies to be time-varying. Hence, the routing problem becomes more complex when the time domain must be considered for data delivery in duty-cycled WSNs. We formulate the routing problem as time-dependent Bellman-Ford problem, and use vector representation for time-varying link costs and end-to-end E2E distances. We present efficient algorithms for route construction and maintenance, which have bounded time and message complexities in the worst case by ameliorating with beta-synchronizer. Multihop broadcast is complex in duty-cycled WSNs due to non simultaneous wakeup in neighborhoods. We present Hybrid-cast, an asynchronous multihop broadcast protocol, which can be applied to low duty-cycling or quorum-based duty-cycling schedules, where nodes send out a beacon message at the beginning of wakeup slots. Therstvariableallowthe usertoreducethenumberofactivenodes,whichhasanimpactonthedensityincertain areas,reducinginterferenceandthegenerationofredundantdata. Inactivenodesturnoff theirtransceiversandgointoaverylowenergyconsumptionmode,fromwhichtheycan beturnedonagaintobepartoftheactivenetworkiftheyareneededinthefuture. The secondvariablehasadirectimpactonenergyconsumptionandonthelevelofinterference,giventhatradiotransmissionisthemostexpensiveoperationintermsofenergyand oneofthemostcommonlydone;inotherwords,reducingtheenergyrequiredtotransmit amessagewillrepresentimportantsavings. Inaddition,atopology controlalgorithmshouldberobustenoughtotakecareofthecharacteristicsofthedeploymentarea. Themaindisadvantageofthiskindofdeploymentisthatahigheramount ofnodesisrequiredinordertoincreasetheprobabilityofhavingnodesineveryregionof themonitoredarea,whichhasadirectimpactonthecostofthenetwork. Amoreformaldenitionoftopologycontrolcanbethefollowing: 9 PAGE 27 TopologyControl isthereorganizationandmanagementfromtimetotime ofcertainnodeparametersandmodesofoperationtomodifythetopology ofthenetwork,withthegoalofextendingitslifetimewhilealsopreserving importantcharacteristics,suchasnetworkconnectivityandsensingcoverage. Inthisphase,nodesdiscoverthemselvesandusetheirmaximumtransmission powertobuildtheinitialtopology. Afterthisinitializationphase,thesecondphasebuilds anewreducedtopology. Thisphaseiscalled TopologyConstruction. Thenewreduced topologywillrunforcertainamountoftime,astheparticipatingsensorswillconsume theirenergyovertime. Therefore,assoonasthetopologyconstructionphaseestablishes thereducednetwork,the TopologyMaintenance phasemuststartworking. Duringthisphase,anewalgorithmmustbeinplacetomonitorthestatusofthereduced topologyandtriggeratopologyrestorationprocesswhenappropriate,thatmaybeaprocessentirelydenedbythemaintenanceprotocolitselforthatmayincludetheinvocation ofthetopologyconstructionalgorithm. Overthelifetimeofthenetwork,itisexpected thatthiscyclewillberepeatedmanytimesuntiltheenergyofthenetworkisdepleted. Therearemanydifferentalgorithmsthatcanbeusedinthetopologyconstructionand maintenancephases. Firstofall,thealgorithmsandprotocolsshouldruninadistributedmanner,sotheycan beimplementedinlargenetworks. Second,topologyconstructionalgorithmsandprotocolsmusthavealowcomputationalandmessagecomplexity,sotheycanbeefciently runincomputationallyweakdevicesandnotdrainthenodes'batteries. Third,itisdesirablethatthealgorithmsareabletorunwithoutthehelpofadditionalhardwarelike GPSdevicesorlocalizationmechanisms,solowcostismaintainedandnoadditional energyisspent. Finally,thetopologyconstructionalgorithmmustproduceaconnected networkthatwillcovertheareaofinterestwithaminimumnumberofnodes,whilethe topologymaintenancealgorithmsmustguaranteethattheresourcesofthenetworkare usedeffectivelyinordertokeepthenetworkactivethelongestpossibletime. Allthese constraintscombinedmakethedesignandimplementationofsimpledistributedtopology controlalgorithmsaverychallengingproblem. Localinformation: Nodesshouldbeabletomaketopologycontroldecisionslocally. Locationinformation: Theneedofextrahardware,likeGPSdevices,orsupport mechanismslikelocalizationprotocolsaddtothecostintermsofdollarsandenergyconsumption. Connectivity: Thereducednetworkmustbeconnected,soallactivenodescan exchangemessagesamongthemselvesaswellaswiththesinknode. Coverage: Thereducetopologymustcovertheareaofinterestdespitethenumber ofactivenodes. Smallnodedegree: Asmallnodedegreemeansasmallnumberofneighbors,which mayproducealowernumberofcollisionsandretransmissions,savingenergy. Simplicity: Topologycontrolalgorithmsmusthavealowcomputationalcomplexity, sotheycanberuninwirelesssensordevices. Energy-efciency: Allthefactorsconsideredthusfarandthosediscussedinthelast sectionconvergeintheissueofenergy-efciency,whichisessentialfortopology controlmechanismsandwirelesssensornetworksingeneral. Energyawareness: Thedecisionmakingprocessintheselectionofthereduced topologymustbeawareofthenodes'sremainingenergyinordertoavoidgiving responsibilitiestoweaknodesthatcanjeopardizetheactivityofthenetwork. Spanner: ThereducedtopologyshouldbeaspanneroftheUnitDiskGraphin termsofbothlengthandnumberofhops. Asubgraph G 0 isaspannerofagraph G forlengthnumberofhopsifthereisapositiverealconstant x suchthatforany twonodes,thelengthnumberofhopsoftheshortestpathin G 0 isatmost x times ofthelengthnumberofhopsoftheshortestpathin G. Theconstant x iscalledthe lengthnumberofhopsstretchfactor Convergencetime: Thetopologyconstructionandmaintenanceprocessesshould takeplaceasfastaspossibleandconvergeafteralimitednumberofsteps. Memoryconsumption: Wirelesssensordevicesoftenhaveasmallamountofmemory. Evenenergydistribution: Topologycontroltechniquesshouldsomehowtryto distributetheenergyconsumptioninanevenmanneramongallthenodesinthe 13 PAGE 31 network. Thisdissertationpresentsnewtopologycontrolmechanismsthatworkconsideringthese aspects. Allthetopologyconstructionprotocolsproposedinthisdocumentworkbyndingaminimumsetofactivenodes,thatprovidesaconnectednetworkthatisabletoperformallthetasksrequiredbytheuser,whetherconnectivityorcoverage,whileturningall therestofthenodesofftosavetheirenergyforfuturemaintenanceoftheactivetopology. Themainreasonwhythismethodologywasselectedisthat,nexttoradiotransmission, idlelisteningisthemostcostlyoperationofanode. Thismeansthat,ifallthenodes arekeptawakeandtheonlychangeismadetothetransmissionpower,theidlelistening timefromtheentirenetworkwillstilldecreasetheamountofsavedenergy;plusthefact thattheproblemofredundantsensingisstillpresent,whichwillincreasetheloadofthe networkwithnoneed. Intheproposedsolutionsofthiswork,allredundantnodeshavetheirtransceiversturned off,sonoenergyiswastedinidlemodeandunnecessaryredundancyisreduced. The hypothesisisthatthealgorithmsproposedinthisdissertation,whilecreatingminimal messageoverheadcomparedtotheircounterparts,canreduceandmaintainanactive topology,extendingthelifetimeofthenetwork,whilekeepingradioconnectivityand sensingcoverageofthedeploymentarea. Basedonthenewdenitionoftopologycontrol,whichdifferentiatestheconstructionandmaintenanceprocesses,anewtaxonomyfortopologycontrolalgorithmswasproposedinordertointegrateandextendthecurrent algorithmspresentedin[2,4,5]whichfocusonlyontherstprocess. Themain contributioninthisareaisthedenitionofataxonomyfortopologymaintenance algorithmsforthersttime,whichnoneofthecitedworksinclude. Inaddition, somemodicationswereperformedontheexistingtaxonomies,inordertoinclude specialbranchestotopologyconstructionprotocolsforheterogeneousnetworksand coverage-orientedprotocols. Theseprotocolscalculatea ConnectedDominatingSetCDS onthe initialMaxPowertopology,leavinginactivestateonlythedominatingnodeswhich provideconnectivityandcoverageinthenetwork,andturningoffalldominated redundantnodes,whichareconsideredunnecessaryforthecorrectactivityof thenetworkatthetimeofexecution. A3istherstversionofthealgorithmand providesabackboneforconnectivitypurposesonly. Theinitialprotocolwaseventuallymodiedintotwonewbranches:the Lite versionsandthe Cov versions. The Lite versionsprovideaverylowcomputationalandmessagecomplexity,compared tothe Non-Lite counterparts. The Cov versionsproduceareducedtopologythat providesahigherdegreeofareacoveragecomparedtothe Non-Cov versions. The 15 PAGE 33 evaluationoftheseprotocolsisbasedonthecomparisonofaveragebehaviorin randomtopologiesagainstotheralgorithmsintheliterature,andagainsttheoretical optimaldeployments. Thersttwoprotocols havebeenproposedbeforeintheliterature,buthavenotbeenimplementedindetail. Thesealgorithmsweredesigned basedontheproposedtaxonomyfortopologymaintenancealgorithms. Theperformanceevaluationofthesealgorithmsisbasedonthecomparisonoftheaverage resultsinrandomtopologies,andworkingjointlywiththreedifferenttopology constructionprotocols. Itisveryimportanttomentionthat,totheknowledgeof theauthor,thisisthersttimethatamodularizationofthetopologyconstructions andmaintenanceprotocolshasbeenimplementedforjointtestingperformance. Atarraya:anewsimulationtoolforteachingandresearchingtopologycontrol algorithms. Asatoolwasneededtodesignandtesttheproposedtopologycontrolalgorithms,thetopologycontrolsimulator Atarraya wascreated. Atarraya isadiscrete-eventsimulatorforevaluatingtopologycontrolalgorithms. Itwas developedinJava,whichallowsAtarrayatobeaveryportableapplicationamong differentoperatingsystems. Inaddition,thesimulatorisbeingofferedforfree tothescienticcommunityasanopensourceproject,basedontheGNUlicense model. Thissimulatorprovidesafriendlyenvironmentfordesigningbothtopology constructionandmaintenancealgorithms,allowingthemodularitytocombinethose protocols,whichhasnotbeenseeninanyothersimulatorofitskind. Inaddition, 16 PAGE 34 itcanbeextendedtosupportschemesfordataaggregation,routing,nodemobility anddifferentenergymodels. Mostoftheworkpresentedinthisdissertationhas beenincludedinthebook TopologyControlinWirelessSensorNetworks-witha companionsimulationtoolforteachingandresearch ,writtenbyMiguelLabrador andPedroWightman,andpublishedinbySpringerScience[1]. Thisbook presentsanintegraldenitionoftopologycontrol,basedonthedecouplingofthe constructionandmaintenanceprocesses,andalsoprovidesthesimulatorAtarraya asatoolnotonlyforresearchinganddesigningofnewTCprotocols,butalsoasa usefultoolforteachingcommunicationprotocolsinanuser-friendlyenvironment. Anewmixedintegerprogrammingdenitionoftheminimalconnecteddominating setproblem. EventhoughtherehasbeenpreviousdenitionsoftheMCDSproblem intheliterature,mostofthemdependontheseparatesolutionoftheproblems ofconnectivityanddomination,whichmaynotnecessarilyguaranteeanoptimal jointsolution,orinextensivepreprocessing. Thisdissertationprovidesandefinitionoftheproblembasedonaverysimpleinsightoftheproblemthatsolves bothconnectivityanddominanceinasingleformulation,anddoesnotrequireany preprocessing. Theresultsofthisnewmodelarecomparedwiththeresultsfromthe approximationprotocolspresentedinChapter3. Chapter2willbededicatedto theliteraturereviewoftheproblemoftopologycontrol,includingtheintroductiontothe proposedtaxonomy,andreferencestothemostimportantalgorithmsinbothtopology 17 PAGE 35 constructionandtopologymaintenanceinthecategoriesofthetaxonomy. Inaddition,a sectionofthechapterwillbededicatedtotheConnectedDominatingSet-basedprotocols fortopologyconstructionforbothconnectivityandcoverage. Chapter3describesthe methodologyusedfortheperformanceevaluationofthedifferenttopologyconstruction andmaintenanceprotocolsintroducedinthisdissertation,includingboththeanalytical andsimulation-basedapproaches. Chapter4willintroducethetopologyconstruction algorithmsA3andA3Lite,whicharefocusedonlyonproducingaconnectedtopology withaminimumnumberofactivenodes,andwillshowtheirperformanceevaluation againsttwoverywellknownCDS-basedtopologyconstructionalgorithms. TheA3Cov andA3CovLitetopologyconstructionalgorithmswillbeintroducedinChapter5,which providenotonlyaconnectedtopologybutatopologythatcoversahighdegreeofthedeploymentarea,andwillshowtheirperformanceevaluationagainstsomeoptimaltheoreticaldeployments,their Non-Cov versionsandtwoothercoverage-orientedtopologyconstructionprotocols. Chapter6willpresentthetopologymaintenancealgorithmsproposed inthisdissertation,includingtheirjointperformancetestingwithsomeofthetopology constructionalgorithmspresentedinChapter4. Theconclusionsofthisworkandsome nalremarkswillbepresentedinChapter7. Inaddition,adetaileddescriptionofthe internalstructureanduseofthesimulatorAtarrayawillbeincludedintheAppendixA. Researchersinthisareatookadvantageofthesimilaritiesofthesenetworkswiththerandomgraphsontheoreticalelds,inordertoadopt theexistingbasttheoryingraphsandapplyitintothisnewkindofnetwork. Thisfactdeterminedthattherstattemptstoperformtopologycontrolwerebasedmainly inclassicalgraphalgorithms,liketheminimalspanningtree,thesetcoverandcoloring problem,justtomentionsome,becausethewerealreadycapableofalteringtheoriginal structureofagraphinordertoreducethetopology. However,mostofthesealgorithmsrequireglobalinformationandworkinacentralized manner,whichbecameanaturalinitialassumptiontomakeinordertoallowtheuseof thesesolutions. Theseassumptionsstoppedbeingvalidveryquicklyforscenariosin whichthesizeofthenetworkmadeitinfeasibletouseacentralizedsolutionorwhen globalinformationwastoexpensivetoobtain. Thisopenedthehorizonforthedevelopmentofdistributedprotocolsthatrequiredlocalinformation,whichcorrespondedmore withsomeoftherealcharacteristicsofthesenetworks:theycanreachhighlevelsof scalability,randomnessinlocalizationofthenodesandtheircommunicationlinks,and globalinformationistoocostlytocollectanddistribute. Aspartofthiswork,a newtaxonomyforclassifyingtopologycontrolprotocolsispresented. Thenewproposed taxonomyisanextensionofthreeprevioustaxonomies,introducedin[2,4,5]. Thenew taxonomy,whichisoneofthemaincontributionofthiswork,providesaroadmapforthe restofthischapter. Themainproblemwiththisapproachisthatusuallythemaintenanceprocesswasnot assumedcriticalinthedesignofthealgorithm,sonotestswereperformedinordertodeterminethebestmaintenancepolicyforthereducedtopologyproducedbythealgorithm. Inaddition,thisconceptionalsoaffectedtheclassicationoftopologycontrolalgorithms, restrictingitonlytohowthenetworktopologywasreduced. Thetwopreviouslydened taxonomiesfortopologycontrolalgorithmscoveredthefollowingareas: Thetaxonomypresentedin[4]isfocusedonlyontopologyconstructionalgorithms thatchangethetransmissionrangetoreducethenetworktopology. Thetaxonomypresentedin[2]hasabroaderdenitionoftopologyconstruction algorithms,consideringalsohierarchicalandhybridalgorithms. Thetaxonomypresentedin[5]isfocusedonlyinthecoverage-orientedtopology constructionprotocols. Theunionofthesethreetaxonomiesproducesafairlycompletetaxonomyfortopology constructionalgorithmsonly. Theproposedtaxonomynotonlyextendstheareaoftopologyconstructionintheaforementionedarea,butalsoincludesanewtaxonomyfortopologymaintenanceprotocols, whichwascompletelyignoredinprevioustaxonomies. Theinclusionofthisnewbranch ismotivatedbythefactthattheselectionofatopologymaintenanceprotocolhasserious implicationsonthelifetimeofthenetwork,soinordertostudytheimpactofmaintenanceontopologyconstructionprotocols,aclearclassicationofthedifferentmethods toperformmaintenanceisanecessity. Thealgorithmsintherstbrancharefocusedonlyinproducingaconnected reducedtopology,butdonotguaranteethecorrectlevelofcoverageofthedeployment area. Theprotocolsinthesecondbrancharemoreorientedinprovidingcoverageinthe area,evenif,insomecases,connectivityisnotguaranteed. Thefollowinglistillustratesageneraldescriptionofthedifferenttechniquesusedby mostofthetheconnectivity-orientedtopologyconstructionprotocols: Somesolutionsbuildareducedtopologybycontrollingthetransmissionpower,for bothhomogeneousandheterogeneousnetworks. Bothcentralizedanddistributed techniquesarepresented. Otherprotocolsusehybridschemes,mixingdifferenttechniquesinordertoreduce thetopology. Incontrast,thefollowinglistenumeratessomeofthedifferenttechniquesusedbycoverage-orientedtopologyconstructionprotocols: Someprotocolsaredesignedtoprovidecoverageofasetofpredenedtargets distributedinthedeploymentarea,andnottheentirearea Somesolutionscanofferdifferentlevelsofredundancyinthecoverage 2. Theclassicationdimensionsofthetechniquesinthiscategoryarebasedon thefollowingparameters: 22 PAGE 40 Selectionofthenodesforthemaintenanceproblem:pre-calculatedstatictopology selection,ontheydynamicselectionorahybridselectionscheme. Levelofinvolvementofthenodesinthemaintenanceprocess:globalinvolvement, whenallthenodesinthenetworkparticipateonthealgorithms,orlocalinvolvementwhenjustasmallsubsetofthemperformthemaintenance.

Recently,in[29],itisdemonstratedthattoproduceaconnectedtopology,eachnode shouldbeconnectedto Q logn nearestneighbors. ThisnodeismarkedBlack,andmarksallits neighborsGray. Allthetopologyconstructionprotocolsproposedinthisdocumentworkbyndingaminimumsetofactivenodes,thatprovidesaconnectednetworkthatisabletoperformallthetasksrequiredbytheuser,whetherconnectivityorcoverage,whileturningall therestofthenodesofftosavetheirenergyforfuturemaintenanceoftheactivetopology.

Researchersinthisareatookadvantageofthesimilaritiesofthesenetworkswiththerandomgraphsontheoreticalelds,inordertoadopt theexistingbasttheoryingraphsandapplyitintothisnewkindofnetwork. Asatoolwasneededtodesignandtesttheproposedtopologycontrolalgorithms,thetopologycontrolsimulator Atarraya wascreated.

  • Aston university phd thesis
  • How to write a strong thesis statement for a compare and contrast essay
  • Rndr andrej blaho phd thesis

IEEE Sensors. Thislargeoverheadisparticularlydetrimentalindensenetworks becauseofthenetworkcongestionandcollisionsthatitgenerates. Finally,wirelesssensordevicescanbeequippedwithactuators toperformactionsuponcertainconditions.

However,nodesthat areafewhopsawayin G canbecomeveryfarapartin G 0. Finally,thepairofnodeswiththe highestyieldistheoneselectedaspartofthetree.

Ford J. Aftertheproblemstatement, thechapterincludesthedetailedlistofcontributionspresentedinthisdissertation,and nalizeswiththestructureofthedissertation. Uponreceivingthismessage,eachWhiteneighborcolorsitselfasGrayandsends aGraymessagetonotifyitsownWhiteneighborsthatithasbeenconvertedtoGray. Atthebeginning,allnodesaremarkedasWhite,andthealgorithmstarts atthenodewiththehighestnodedegree. Atarraya:anewsimulationtoolforteachingandresearchingtopologycontrol algorithms.

Finally,thetopologyconstructionalgorithmmustproduceaconnected networkthatwillcovertheareaofinterestwithaminimumnumberofnodes,whilethe topologymaintenancealgorithmsmustguaranteethattheresourcesofthenetworkare usedeffectivelyinordertokeepthenetworkactivethelongestpossibletime.

Market entry modes thesis proposal

In order to reduce the irregularity in cluster head placements, CLUE-HOPE allows the cluster to adjust its size by handling the sensors from and to the neighbor grids. Thesearethe problemsthatTopologyControlcanhelptoprevent. Otherpruningrulesarealsopresentedbytheauthorsin[52,53]: Rule1 and Rule2. Itisimportanttomentionthat eventhoughonecommonassumptionofthisapproachistohavethenodestransmittingat fullpower,theycouldalsoreducetheirtransmissionrangetoreachonlytheirdirectactive neighbors,sotheapproachespresentedinSection2.

ThankstoallmyfriendswhoInolongerconsiderjustfriends,becausewehavebecome morelikeafamily:thankstoDala,Migue,andallthepeoplefromtheInformationSystemsLabfortheirsupportandthegoodlaughs. Inthissense,Penrosedeterminedthatfordensenetworks, thelengthofthelongestedge,fromwhichthevalueoftheCTRcanbecalculated,is determined withhighprobability w : h : p byEquation2.

TheRelativeNeighborGrapheliminatesthelongestedgefromeverytriangleformedby twoofitsneighborsanditself. TheRNGcanbeeasilydeterminedusingalocalalgorithm withmessagecomplexity O n andcomputationalcomplexity O n 2. Also,iftheoriginal graph G isconnected,thenthereducedgraph G 0 isalsoconnected. However,nodesthat areafewhopsawayin G canbecomeveryfarapartin G 0. TheGabrielGraphconnects nodes u and v ifthediskhavinglinesegment uv asitsdiametercontainsnoothernode thanthetwoneighbors u and v. Distributedimplementations oftheRNGsandGGsonlyrequirenodestosharetheirlocationswiththeirneighbors andtesttheseconditionstoverifyeachedgeinordertodeterminetheminimalsetof theses. Anothergraphborrowedfromcomputationalgeometrythatisusefultobuildreduced topologiesistheDelaunayTriangulation. Ifalltheneighbornodesareconnectedbased onthevicinityoftheVoronoidiagram,aDelaunayTriangulationwillbeobtained. The Voronoidiagramisageometricconstructionthatdenestheareaofcoverageandthe vicinityinagraph. Rightinthemiddleof thisline,traceanorthogonallinethatwilldenethelimitbetweentheareas. Repeatthe processbetweeneverypairofnodesinthegraph. Thesmallerintersectedareadened aroundanodefromthelimitswitheveryothernodeinthegraphdeterminesthenal diagram. TheDelaunayTriangulationdiagramisformedbyconnectingadjacentvertices intheVoronoidiagram. Withthisapproacheachnodecanchooseasitstransmission powerthepowerneededtoreachitsfarthestneighbor. Thisapproachrequiresglobalinformationand,ifappliedwithoutrestrictions,itmay connectnodeswhicharemoredistantthanthemaximumcommunicationrange. DT hasamessagecomplexityof O n andcomputationalcomplexityof O nlogn. In[16],alocalized versionoftheDelaunaygraphisdescribed. Here,themainconcern ofthesealgorithmsisaboutbuildingaqualitytopologywhilebeingabletoimplementitinanefcientfashion;whereefcientmeanswithlowenergyconsumption,low computationalandmessagecomplexity,andsoon. Theseprotocolsmakeuseofloca29 PAGE 47 tion,direction,neighbor,androutinginformationtoachievetheirobjectives. Finally, thesectionalsoincludesmechanismsthatndthereducedtopologybycontrollingthe transmissionpowerinheterogeneousnetworks,i. Thisinformationallowsthemtousegeometricpropertiesinordertodeterminethebest congurationofthetopologyintermsofdistancebetweennodes,whichattheenddeterminesthebesttransmissionrangeforeachofthem. Forexample,distributedversionsof thealgorithmsfromcomputationalgeometrydescribedinSection2. Moreinformationaboutlocalizationtechniques canbefoundin[19]. Inallthelocation-anddirection-basedtechniques,thetopologyconstructionalgorithms requireextrainformationfromtheneighbornodesotherthantheirownpresence,suchas 30 PAGE 48 accurateCartesiancoordinatebi-ortri-dimensionallocationorpolarcoordinatedistanceandangle. However,localizationinformationisnotalwaysavailableoraccurate, anditcouldbeveryexpensivetoobtain. Phd canonlybeobtainedinplaceswherethereisdirectaccesstothesatellitesignals. Other localizationtechniques,likeultrasonicorultrawideband-based,notonlyneedalocalizationprotocolontopofthetopologyconstructionprotocol,butcouldalsoincreasethe communicationsoverhead,astheirrangeisverysmallcomparedwiththeradiocoverage. Inthecaseofpolarcoordinates,theuseofdirectionalantennaeincreasesthepriceand complexityofthewirelessdevices. Inaddition,eachoneofthosetechniquesalsocarries anintrinsicerrorthatlimitsthereliabilityontheinformationtheyproduce. Neighborbasedtechniquesovercometheseproblems,astheyassumethatnodesonlyneedtohave theabilitytodeterminethenumberofneighbors,changetheirtransmissionpowerand,in how to write a good motivational speech. Themainideaofthesealgorithmsistoproduceaconnectedtopologybyconnectingeach nodewiththesmallestnecessarysetofneighbors,andwiththeminimumtransmission powerpossible. Giventhatthenodesdonotpossesaccuratelocationinformation,their decisionsdependmostlyontheprobabilityofselectingtheappropriateneighbors,the onesthatwouldextendthenetworkasfaraspossible. Undertheassumptionthatthe nodesareeitheruniformlyorPoissondistributed,somepropertieshavebeenfoundin connectedtopologiesthatdeneaboundedminimumappropriatesizeoftheneighborhoodsofasinglenodethat w. Asaresult,most neighbor-basedprotocolsfortopologyconstructionarebasedonthecreationofa Kneighborgraph Thedenitionoftheminimumnumberofneighbors k thateachnodemusthaveinorder topreserveconnectivityhasbeenawell-studiedproblem. Mostcommonlyusednumbers 31 PAGE 49 forthisparameterarebetween6and8,oranaverageof3neighbors,aspresentedin[26 28]. Recently,in[29],itisdemonstratedthattoproduceaconnectedtopology,eachnode shouldbeconnectedto Q logn nearestneighbors. Theconnectivityofatopologyisoneofthemostimportantrequirementsofanytopology constructionprotocol. Onewaytodetectconnectivityisbymakingsurethataroutecan befoundfromonenodetoeveryothernodeinthenetwork. Thisisthemainobjectiveof theroutingfunction:tobuildroutingtablestoroutepacketsfromonenodetoallpossible destinations. Whenallthenodesareincludedintheroutingtablesitimpliesthattheycan bereached,andthetransmissionrangedoesnotneedtobeadjusted. Thisisthemainidea behindtherouting-basedtechniques. Inthistypeofheterogeneousenvironment,itisveryimportanttodevisealgorithmsandmechanismsthatwill allowdifferentdevicestocollaborate,eachtakingadvantageoftheabilitiesoftheothers. Asaresult,topologycontrolproblemshavebeensolved asrangeassignmentproblems,whichnotonlyneglecttheheterogeneityofthenetwork butalsodonottakeadvantageoftheuniquecapabilitiesofdifferentdevices. However,thisapproachdoesnotpreventthetransmissionofredundantinformationwhenseveralnodesareclosetoeachotherandmaynot simplifythenetworktopologyenoughinordertomakewirelesssensornetworksscalable forlargedeployments. Thissectionexplainsadifferentapproachtotopologyconstruction,thehierarchicaltopologyconstructionapproach,whichaddressesthescalability problemandfacilitatestheaggregationofinformationforadditionalenergysavings. Inthehierarchicaltopologyconstructionapproach,acommunicationhierarchyiscreatedinwhichareducedsubsetofthenodesisselectedandgivenmoreresponsibilities onbehalfofasimpliedandreducedfunctionalityforthemajorityofthenodes. This approachhasthepotentialtogreatlysimplifythenetworktopologyandtheopportunityto 33 PAGE 51 saveadditionalenergybyassigningusefulfunctionstothereducedsubsetofnodes,such phd. Onedisadvantageofthehierarchicalapproachisthattheselectedsubsetofnodeswill workmorethantheirunselectedneighbors,andwillseetheirbatteriesdrainedsooner. Therefore,thisapproachmustbeaccompaniedbyagoodtopologymaintenancefunction thatwillrotatetheroleofthenodeswiththenalgoalofspendingtheirenergyevenly andextendingthenetworklifetime. Inthefollowingsections,thesecategoriesalongwith themostimportantalgorithmsandprotocolsavailableintheliteraturearedescribedand explained. Itisimportanttomentionthat eventhoughonecommonassumptionofthisapproachistohavethenodestransmittingat fullpower,theycouldalsoreducetheirtransmissionrangetoreachonlytheirdirectactive neighbors,sotheapproachespresentedinSection2. InthespecialcaseoftheCDS,thenodesin D are connected. TheseproblemshavebeenshowntobeNP-hard in[35,36],therefore,heuristicsareneededforpracticalpurposes. In[37],theauthorsproposetheseparationoftheproblemsoftheCDSintotwoparts towhichwell-knownlinearprogrammingdenitionsexist:theminimumdominatingset andtheminimumtreethatwillconnectthedominatingnodes. Someothervariationshave 35 PAGE 53 beenproposed,addingrestrictionstotheprobleminordertoreducethesolutionspace: in[38,39]wheretheauthorsrestrictedthetypeofnetworkstoberegularandrandom cubicgraphs,respectively. OthersolutionsextendtheCDSschemebyincludingother metrics,likein[40]wheretheauthorsincludethemaximizationofthethroughputofthe network. InthecaseofapproximatesolutionstotheMCDSproblem,manyalgorithmshavebeen provedtobeapproximationalgorithmsoftheoptimalsolution. However,assumingthatthenodesaredeployedintheEuclideanspace,better approximationratioscanbeachieved. Great business planning quotes business Ingeneral,threemethodsarethemostcommonlyusedtocreateaconnecteddominating set,andtheywillbeexplainedindetail. AneasywaytoillustratetherstapproachtogrowatreeisbycomparingitwithPrim's algorithm[46],whichndstheminimumspanningtreeofagraph. Theprocessworks fromthesetofnodesthatarepartofthetreeattime t. Ingeneral,theprocessstartsonasingle node,usuallythesinknode,butiftherearemorethanonesinknodes,thenseveraltrees couldbebuiltinparallel,ifthenodessupportthatfunctionality. Thegrowingatree techniquehascharacteristicsthataredesirableforroutingprotocols,likeanorganized structurethatallowsimplementingroutingbasedonthesimpliedlogicalstructure,hierarchicaladdressing,queryingbasedontreesearches,etc. In[41],theauthorspresentacoloring-basedgrowingatreeapproachtocreateaCDS onagraph. Atthebeginning,allnodesaremarkedasWhite,andthealgorithmstarts atthenodewiththehighestnodedegree. ThisnodeismarkedBlack,andmarksallits neighborsGray. TheGraynodesthatincludemore unmarkednodesoneachiterationwillbeincludedonthetreebymarkingthemasBlack fords. Theauthorsalsoshowthat theimplementationofthisalgorithmrunsin O m steps,where m isthenumberofedges intheoriginalgraph. AGraynodeandaWhitenodewill bemarkedasBlackiftheirjointcontributionisthegreatestontheiteration. First,the algorithmmarksaGraynodeBlack,whichmakesallitsneighborsGray. Then,oneof theGraynodesisalsocoloredBlack,whichmakesitsneighborsGray. Here,theyield isgivenbythetotalnumberofGraycolorednodes. Finally,thepairofnodeswiththe highestyieldistheoneselectedaspartofthetree. Theauthorsshow thattheimplementationofthismodiedgreedyalgorithmcanberunin O nm networks, where n isthesetofnodesand m thesetofedgesintheoriginalgraph. Adetailed explanationoftheprotocolswillbepresentedinChapters4and5. AnMISisanindependentsetthatisnotasubsetofanyotherindependent set,i. Proposedin[44],theEECDSalgorithmcreatesamaximal independentsetintherstphase,andthenselectsgatewaynodestoconnectthetheindependentsetsduringthesecondphase. Uponreceivingthismessage,eachWhiteneighborcolorsitselfasGrayandsends aGraymessagetonotifyitsownWhiteneighborsthatithasbeenconvertedtoGray. Thecompetitionconsistsofsendingan Inquiry messagetoitsneighborstoknowabouttheirstate andweightsandwaitfortheirresponsesforaspecicamountoftime. Ifduringthistime, itdoesnotreceiveanyBlackmessageinresponse,andithasthehighestweight,itbecomesaBlacknode,andtheprocessstartsagain. Theweightisametriccalculatedbyeachnodebasedonthebatterypowerandeffective nodedegree. Thesenodes,called fords ,areselectedinagreedymannerby MISnodesusingthreetypesofmessages. Inbothphases ofthealgorithm,competitionisusedtodeterminethebestcandidatestobeincludedin theindependentsetsandthenaltree. Thisprocessisverycostlyintermsofmessage overheadbecauseeachnodehastoconsultitsneighborsfortheirstatusinordertocalculateitsownmetric. Thislargeoverheadisparticularlydetrimentalindensenetworks becauseofthenetworkcongestionandcollisionsthatitgenerates. Theauthorsclaim thatthemessagecomplexityoftheEECDSalgorithmis O n ,asduringeachofthetwo phaseseachnodeatmostsendsoutonemessage. Thetimecomplexityofthealgorithm isgivenbytheconstructionoftheMIS,whichhasa O n worsttimecomplexity. Thisprocedure,unfortunately,isnotwell-explainedinthepaperanditisunkonwn whetheritneedsglobalinformationorifitcanbetriggeredinadistributedmanner. Further,theclaimthattherecalculationprocedurebalancestheenergyconsumptionofthe nodesisnotsupported. AmodiedversionoftheSPANalgorithmthatincludesthe useofdirectionalantennasandpresentsthesamemessageandcomputationalcomplexity oftheoriginalversionispresentedin[50]. Otheralgorithmsthatbelongtothiscategory canbefoundin[51],and[41]. Inthisrstphase,thenodesexchangeHELLOmessagesinorderto gettoknowtheirneighborsandexchangetheirneighborlists. Onceanodereceivesthe listsfromitsneighbors,itintersectsthelistswithitsownlistofneighborsandcountsthe numberofelementsinbothlists. Ifthisnumberislessthantheamountofneighborsin thenode'sownlist,thenthisnodewillmarkitselfaspartoftheinitialset;otherwise,the nodewillturnitselfoff. Forthesecondphase,thealgorithmprunesunnecessarynodesapplyingoneofthethree pruningrulesdescribedin[53]. Atemporarilymarkednodedecidestounmarkitselfifit determinesthatallitsneighborsarecoveredbymarkednodeswithhigherpriority,which mightbegivenbythelevelofthenodeinthetreeassumingthatalowerlevelmeans Lake erie fishing report buffalo PAGE 59 higherpriority,ortheprioritycouldhavebeendenedbeforeastotheexecutionofthe ford. Algorithms for node clustering in wireless sensor networks: a survey. Colombo, Sri Lanka; Cluster head selection in clustering algorithms for wireless sensor networks: a survey. Virgin Islands, USA; Towards clustering algorithms in thesis sensor phd - a survey. Budapest, Hungary; Cluster-based routing protocols for energy-efficiency in network sensor networks. Comparison of clustering Ken watanabe author problem solving 101 and protocols for wireless sensor networks. Ottawa, ON, Canada; A centralized energy-efficient Aosb main board essaytyper protocol for wireless sensor networks. Heinzelma WB. Phd protocol architectures for wireless networks [PhD thesis]. Massachusetts Institute of Technology; Our analytical and experimental results show that cqs-pair and gqs-pair achieve thesis trade-off between the average discovery delay and energy consumption ratio. We also study asymmetric quorum-based wakeup sensor for two-tiered network topologies for further improving energy efficiency. Heterogenous duty-cycling causes transmission latencies to be time-varying. Hence, the thesis problem becomes more network when the time domain must be considered for data delivery in duty-cycled WSNs. We formulate the routing problem as time-dependent Bellman-Ford problem, and use vector representation for time-varying link costs and end-to-end E2E distances. We present efficient algorithms for route construction and maintenance, which have wireless time and message complexities in the worst case by ameliorating with beta-synchronizer. Multihop broadcast is complex in duty-cycled Phd due to non simultaneous wakeup in neighborhoods..

Adetailed explanationoftheprotocolswillbepresentedinChapters4and5. Thisassertioncanbe 4 PAGE 22 explainedwiththefollowingtworeasons:rst,asinglewirelessdevicepossessesasmall energysource,whichisexpectedtolastseveralmonths;andsecond,ifthenetworkisdeployedinaninaccessiblearea,changingdepletedbatteriesisnotfeasible,sothewireless devicesmustusetheiralreadysmallenergysourceinaveryefcientway.

3 part thesis statements

First,itintroducesacomprehensivetaxonomyfortopologyconstructionandmaintenancealgorithmsfortherst time. However, itisassumedthatallnetworksusedinthisdissertationcanbemodeledasbidirectional graphs. Thenaltreeisaprunedversion oftheinitialonewithallredundantnodesthatwerecoveredbyothernodeswithhigheror equalpriorityremoved. Grid-based coordinated routing in wireless sensor networks.

Wireless sensor networks phd thesis 2010 ford

Thisphaseiscalled TopologyConstruction. However,atthepresenttime,ofalltheconstraintsconsideredinmostavailablewireless sensordevices,energyconsumptionisofparamountimportance. Theunionofthesethreetaxonomiesproducesafairlycompletetaxonomyfortopology constructionalgorithmsonly.

Thisapproachisbetterrepresentedbytheproblem ofthe CriticalTransmissionRangeCTR Findingtheoptimaltransmissionpowerforeachindividualnode,whichisthe RangeAssignmentRAproblem Theuseofgeometricalpropertiesinordertondreducedglobaltopologiesbased onlocaloptimalsolutions Therstapproachwaspresentedin[6].

Ageneraldiagramofthestructureofoneofthesedevicescanbe seeninFigure1. LCM: a link-aware sensor mechanism for energy-efficient routing.

However, considering only a single metric fails to expose the influence of other phd. Thisapproachrequiresglobalinformationand,ifappliedwithoutrestrictions,itmay connectnodeswhicharemoredistantthanthemaximumcommunicationrange. Thisisnormallythecasewhen thenodeshavejustbeendeployedandtheyareexploringtheirneighborhood. Petersburg,FL,thetemperatureoneachoor oftheEmpireStatebuildinginNewYorkcity,orthecurrentlocationofagroupofzebras inthesavannasofCentralAfrica,andthisisjustthebeginning.

Theauthorsalsoshowthat theimplementationofthisalgorithmrunsin O m steps,where m isthenumberofedges intheoriginalgraph. We analytically establish the ford network of broadcast count and the broadcast latency under Hybrid-cast. Thenewreduced topologywillrunforcertainamountoftime,astheparticipatingsensorswillconsume theirenergyovertime. Kwon TJ, Gerla M.

Wireless sensor networks phd thesis 2010 ford

Virgin Islands, USA; Inactivenodesturnoff theirtransceiversandgointoaverylowenergyconsumptionmode,fromwhichtheycan beturnedonagaintobepartoftheactivenetworkiftheyareneededinthefuture. Towards clustering algorithms in wireless sensor networks - a survey.

MiguelLabrador,whohasguidedand supportedmethroughouttheseyearswithadmirablepatience,andwhoalsohasbecome agoodfriend. Starkforacceptingmyinvitationtobepartofthisexperienceandfortheirvaluablecommentsand suggestions. MydeepestgratitudetomywifeHillaryandmybeloveddaughterSophia,whoselove, patienceandsupporthavehelpedtokeepmeontherighttrack.

Repeatthe processbetweeneverypairofnodesinthegraph. Younis O, Fahmy S. Onewaytodetectconnectivityisbymakingsurethataroutecan befoundfromonenodetoeveryothernodeinthenetwork. Basedonthenewdenitionoftopologycontrol,whichdifferentiatestheconstructionandmaintenanceprocesses,anewtaxonomyfortopologycontrolalgorithmswasproposedinordertointegrateandextendthecurrent algorithmspresentedin[2,4,5]whichfocusonlyontherstprocess.

Chapter4willintroducethetopologyconstruction algorithmsA3andA3Lite,whicharefocusedonlyonproducingaconnectedtopology withaminimumnumberofactivenodes,andwillshowtheirperformanceevaluation againsttwoverywellknownCDS-basedtopologyconstructionalgorithms.

Thenew taxonomy,whichisoneofthemaincontributionofthiswork,providesaroadmapforthe restofthischapter. Simplicity: Phd, sotheycanberuninwirelesssensordevices. Thissectionexplainsadifferentapproachtotopologyconstruction,thehierarchicaltopologyconstructionapproach,whichaddressesthescalability problemandfacilitatestheaggregationofinformationforadditionalenergysavings.

Thetwopreviouslydened taxonomiesfortopologycontrolalgorithmscoveredthefollowingareas: Thetaxonomypresentedin[4]isfocusedonlyontopologyconstructionalgorithms thatchangethetransmissionrangetoreducethenetworktopology. Withthisapproacheachnodecanchooseasitstransmission powerthepowerneededtoreachitsfarthestneighbor. Electronic cigarette case study reducedtopology,butdonotguaranteethecorrectlevelofcoverageofthedeployment area.

SpecialthankstoAldowhosehelpwas criticalinthesenalmonthsandtoAlcidesforthenameofthesimulator,amongother excellentsuggestions. MiguelLabrador,whohasguidedand supportedmethroughouttheseyearswithadmirablepatience,andwhoalsohasbecome agoodfriend.

Thecompetitionconsistsofsendingan Inquiry messagetoitsneighborstoknowabouttheirstate andweightsandwaitfortheirresponsesforaspecicamountoftime. Ifthisnumberislessthantheamountofneighborsin thenode'sownlist,thenthisnodewillmarkitselfaspartoftheinitialset;otherwise,the nodewillturnitselfoff.

Thesecondcaseincludesprotocolsthatconsidera networkwithheterogeneousdevices,intermsofenergyandtransmissionrange. Amoreinterestingandenergy-efcientmethodwouldbe tondthemaximumenergyneededpernode;inotherwords,a non-homogeneouspower network tobuildareducedconnectedtopologywithoutthedrawbacksofhavingan homogeneousrange.