《农业网络信息》PPT课件

OverviewofGraphTheory,AdHocNetworkingInstructor:CarlosPomalaza-RezFall2003UniversityofOulu,Finland,SomeapplicationsofGraphTheory,ModelsforcommunicationsandelectricalnetworksModelsforcomputerarchitecturesNetworkoptimizationmodelsforoperationsanalysis,includingschedulingandjobassignmentAnalysisofFiniteStateMachinesParsingandcodeoptimizationincompilers,ApplicationtoAdHocNetworking,NetworkscanberepresentedbygraphsThemobilenodesareverticesThecommunicationlinksareedges,RoutingprotocolsoftenuseshortestpathalgorithmsThislectureisbackgroundmaterialtotheroutingalgorithms,Vertices,Edges,ElementaryConcepts,AgraphG(V,E)istwosetsofobjectVertices(ornodes),setVEdges,setEAgraphisrepresentedwithdotsorcircles(vertices)joinedbylines(edges)ThemagnitudeofgraphGischaracterizedbynumberofvertices|V|(calledtheorderofG)andnumberofedges|E|(sizeofG)Therunningtimeofalgorithmsaremeasuredintermsoftheorderandsize,GraphsNetworks,DirectedGraph,AnedgeeEofadirectedgraphisrepresentedasanorderedpair(u,v),whereu,vV.Hereuistheinitialvertexandvistheterminalvertex.Alsoassumeherethatuv,2,4,3,1,V=1,2,3,4,|V|=4E=(1,2),(2,3),(2,4),(4,1),(4,2),|E|=5,UndirectedGraph,2,4,3,1,V=1,2,3,4,|V|=4E=(1,2),(2,3),(2,4),(4,1),|E|=4,AnedgeeEofanundirectedgraphisrepresentedasanunorderedpair(u,v)=(v,u),whereu,vV.Alsoassumethatuv,DegreeofaVertex,Degreeofavertexinanundirectedgraphisthenumberofedgesincidentonit.Inadirectedgraph,theoutdegreeofavertexisthenumberofedgesleavingitandtheindegreeisthenumberofedgesenteringit,2,4,3,1,2,4,3,1,Thedegreeofvertex2is3,Theindegreeofvertex2is2andtheindegreeofvertex4is1,WeightedGraph,Aweightedgraphisagraphforwhicheachedgehasanassociatedweight,usuallygivenbyaweightfunctionw:ER,2,4,3,1,2,4,3,1,1.2,2.1,0.2,0.5,4,8,6,2,9,WalksandPaths,3,2,3,4,1,1,V5,V4,V3,V2,V1,V6,4,1,Awalkisansequenceofnodes(v1,v2,.,vL)suchthat(v1,v2),(v1,v2),.,(v1,v2)E,e.g.(V2,V3,V6,V5,V3),Acycleisanwalk(v1,v2,.,vL)wherev1=vLwithnoothernodesrepeatedandL3,e.g.(V1,V2,V5,V4,V1),Asimplepathisawalkwithnorepeatednodes,e.g.(V1,V4,V5,V2,V3),Agraphiscalledcyclicifitcontainsacycle;otherwiseitiscalledacyclic,CompleteGraphs,A,D,C,B,4nodesand(4*3)/2edgesVnodesandV*(V-1)/2edges,C,A,B,3nodesand3*2edgesVnodesandV*(V-1)edges,Acompletegraphisanundirected/directedgraphinwhicheverypairofverticesisadjacent.If(u,v)isanedgeinagraphG,wesaythatvertexvisadjacenttovertexu.,ConnectedGraphs,A,D,E,F,B,C,A,B,C,D,AnundirectedgraphisconnectedifyoucangetfromanynodetoanyotherbyfollowingasequenceofedgesORanytwonodesareconnectedbyapath,Adirectedgraphisstronglyconnectedifthereisadirectedpathfromanynodetoanyothernode,Agraphissparseif|E|V|Agraphisdenseif|E|V|2,BipartiteGraph,AbipartitegraphisanundirectedgraphG=(V,E)inwhichVcanbepartitionedinto2setsV1andV2suchthat(u,v)EimplieseitheruV1andvV2ORvV1anduV2.,u1,u2,u3,u4,v1,v2,v3,V1,V2,Anexampleofbipartitegraphapplicationtotelecommunicationproblemscanbefoundin,C.A.Pomalaza-Rez,“ANoteonEfficientSS/TDMAAssignmentAlgorithms,”IEEETransactionsonCommunications,September1988,pp.1078-1082.ForanotherexampleofbipartitegraphapplicationsseetheslidesintheAddendumsection,Trees,A,B,D,F,C,E,LetG=(V,E)beanundirectedgraph.Thefollowingstatementsareequivalent,GisatreeAnytwoverticesinGareconnectedbyuniquesimplepathGisconnected,butifanyedgeisremovedfromE,theresultinggraphisdisconnectedGisconnected,and|E|=|V|-1Gisacyclic,and|E|=|V|-1Gisacyclic,butifanyedgeisaddedtoE,theresultinggraphcontainsacycle,SpanningTree,Atree(T)issaidtospanG=(V,E)ifT=(V,E)andEE,V5,V4,V3,V2,V1,V6,V5,V4,V3,V2,V1,V6,V5,V4,V3,V2,V1,V6,Forthegraphshownontherighttwopossiblespanningtreesareshownbelow,Foragivengraphthereareusuallyseveralpossiblespanningtrees,MinimumSpanningTree,1,3,8,2,6,7,4,5,5,23,10,21,14,16,6,18,9,7,11,8,1,3,8,2,6,7,4,5,5,6,4,9,7,11,8,G=(V,E),T=(V,F),w(T)=50,24,4,GivenconnectedgraphGwithreal-valuededgeweightsce,aMinimumSpanningTree(MST)isaspanningtreeofGwhosesumofedgeweightsisminimized,CayleysTheorem(1889)Therearenn-2spanningtreesofacompletegraphKnn=|V|,m=|E|CantsolveMSTbybruteforce(becauseofnn-2),ApplicationsofMST,Designingphysicalnetworkstelephone,electrical,hydraulic,TVcable,computer,roadClusteranalysisdeletelongedgesleavesconnectedcomponentsfindingclustersofquasarsandSeyfertgalaxiesanalyzingfungalsporespatialpatternsApproximatesolutionstoNP-hardproblemsmetricTSP(TravelingSalesmanProblem),SteinertreeIndirectapplications.describingarrangementsofnucleiinskincellsforcancerresearchlearningsalientfeaturesforreal-timefaceverificationmodelinglocalityofparticleinteractionsinturbulentfluidflowreducingdatastorageinsequencingaminoacidsinaprotein,MSTiscentralcombinatorialproblemwithdiverseapplications,MSTComputation,Selectanarbitrarynodeastheinitialtree(T)AugmentTinaniterativefashionbyaddingtheoutgoingedge(u,v),(i.e.,uTandvG-T)withminimumcost(i.e.,weight)Thealgorithmstopsafter|V|-1iterationsComputationalcomplexity=O(|V|2),SelecttheedgeeEofminimumweightE=eContinuetoaddtheedgeeEEofminimumweightthatwhenaddedtoE,doesnotformacycleComputationalcomplexity=O(|E|xlog|E|),PrimsAlgorithm,KruskalsAlgorithm,PrimsAlgorithm(example),3,2,3,4,1,1,V5,V4,V3,V2,V1,V6,4,1,V1,V2,V1,1,3,3,V2,V1,1,V3,3,3,1,V5,V2,V1,1,V3,3,1,1,V5,V4,V3,V2,V1,1,3,2,1,1,V5,V4,V3,V2,V1,V6,1,Algorithmstarts,Afterthe1stiteration,Afterthe2nditeration,Afterthe3rditeration,Afterthe4thiteration,Afterthe5thiteration,KruskalsAlgorithm(example),3,2,1,1,V5,V4,V3,V2,V1,V6,1,V2,V1,1,1,V5,V3,V2,V1,1,1,1,V5,V4,V3,V2,V1,1,2,1,1,V5,V4,V3,V2,V1,V6,1,Afterthe1stiteration,Afterthe2nditeration,Afterthe3rditeration,Afterthe4thiteration,Afterthe5thiteration,3,2,3,4,1,1,V5,V4,V3,V2,V1,V6,4,1,DistributedAlgorithms,EachnodedoesnotneedcompleteknowledgeofthetopologyTheMSTiscreatedinadistributedmannerExampleofthistypeofalgorithmsistheoneproposedbyGallager,Humblet,andSpira(“DistributedAlgorithmforMinimum-WeightSpanningTrees,”ACMTransactionsonProgrammingLanguagesandSystems,January1983,pp.66-67).StartswithoneormorefragmentsconsistingofsinglenodesEachfragmentselectsitsminimumweightoutgoingedgeandusingcontrolmessagingfragmentscoordinatetomergewithaneighboringfragmentoveritsminimumweightoutgoingedgeThealgorithmcanproduceaMSTinO(|V|x|V|)timeprovidedthattheedgeweightsareuniqueIftheseweightsarenotuniquethealgorithmstillworksbyusingthenodesIDstobreaktiesbetweenedgeswithequalweightThealgorithmrequiresO(|V|xlog|V|)+|E|)messageoverhead,DistributedAlgorithm-Example,1,4,3,3,6,5,V5,V4,V3,V2,V1,V6,4,1,V7,2,5,2,1,4,3,3,6,5,V5,V4,V3,V2,V1,V6,4,1,V7,2,5,2,1,4,3,3,6,5,V5,V4,V3,V2,V1,V6,4,1,V7,2,5,2,1,4,3,3,6,5,V5,V4,V3,V2,V1,V6,4,1,V7,2,5,2,1,4,3,3,6,5,V5,V4,V3,V2,V1,V6,4,1,V7,2,5,2,Zerolevelfragments,1stlevelfragments1,2and5,6areformed,Nodes3,4,and7joinfragment1,2,Fragments1,2,3,4,7and5,6jointoform2ndlevelfragmentthatistheMST,ShortestPathSpanningTree,Ashortestpathspanningtree(SPTS),T,isaspanningtreerootedataparticularnodesuchthatthe|V|-1minimumweightpathsfromthatnodetoeachoftheothernetworknodesiscontainedinT,2,4,3,1,6,2,5,2,2,4,3,1,2,5,2,2,4,3,1,6,2,2,Graph,MinimumSpanningTree,ShortestPathSpanningTreerootedatvertex1,NotethattheSPSTisnotthesameastheMST,ApplicationsofTrees,Unicastrouting(onetoone)SPSTMulticastrouting(onetoseveral)MaximumprobabilityofreliableonetoallcommunicationsmaximumweightspanningtreeLoadbalancingDegreeconstrainedspanningtree,ShortestPathAlgorithms,Assumenon-negativeedgeweightsGivenaweightedgraph(G,W)andanodes,ashortestpathtreerootedatsisatreeTsuchthat,foranyothernodevG,thepathbetweensandvinTisashortestpathbetweenthenodesExamplesofthealgorithmsthatcomputetheseshortestpathtreesareDijkstraandBellman-Fordalgorithmsaswellasalgorithmsthatfindtheshortestpathbetweenallpairsofnodes,e.g.Floyd-Marshall,DijkstraAlgorithm,Procedure(assumestobetherootnode)V=s;U=V-s;E=;ForvUdoDv=w(s,v);Pv=s;EndForWhileUdoFindvUsuchthatDvisminimal;V=Vv;U=Uv;E=E(Pv,v);ForxUdoIfDv+w(v,x)DxthenDx=Dv+w(v,x);Px=v;EndIfEndForEndWhile,Example-Dijkstra,V1,1,4,3,3,6,4,4,1,2,5,2,AssumeV1issandDvisthedistancefromnodestonodev.Ifthereisnoedgeconnectingtwonodesxandyw(x,y)=,V2,V3,V7,V6,V5,V4,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,D2=1,D4=3,D3=2,D7=,D5=,D6=,D3=,D2=1,D4=3,D7=3,D6=,D5=,V=1,V=1,2,Example-Dijkstra,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,D3=2,D2=1,D4=3,D7=3,D6=6,D5=,V=1,2,3,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,D3=2,D2=1,D4=3,D7=3,D6=6,D5=9,V=1,2,3,4,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,D3=2,D2=1,D4=3,D7=3,D6=6,D5=7,V=1,2,3,4,7,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,D3=2,D2=1,D4=3,D7=3,D6=6,D5=7,V=1,2,3,4,7,6,Example-Dijkstra,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,D3=2,D2=1,D4=3,D7=3,D6=6,D5=7,V=1,2,3,4,7,6,5,Thealgorithmterminateswhenallthenodeshavebeenprocessedandtheirshortestdistancetonode1hasbeencomputed,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,Notethatthetreecomputedisnotaminimumweightspanningtree.AMSTforthegivengraphis,Bellman-FordAlgorithm,FindtheshortestwalkfromasourcenodestoanarbitrarydestinationnodevsubjecttotheconstraintsthatthewalkconsistofatmosthhopsandgoesthroughnodevonlyonceProcedureDv-1=vV;Ds0=0andDv0=vs,vV;h=0;Until(Dvh=Dvh-1vV)or(h=|V|)doh=h+1;ForvVdoDvh+1=minDuh+w(u,v)uV;EndForEndUntil,Bellman-FordAlgorithm(Example),V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,Until(Dvh=Dvh-1vV)or(h=|V|)doh=h+1;ForvVdoDvh+1=minDuh+w(u,v)uV;EndForEndUntil,V1,1,4,3,3,6,4,4,1,2,5,2,V2,V3,V7,V6,V5,V4,Floyd-WarshallAlgorithm,Findtheshortestpathbetweenallorderedpairsofnodes(s,v),s,vvV.Eachiterationyieldsthepathwiththeshortestweightbetweenallpairofnodesundertheconstraintthatonlynodes1,2,n,n|V|,canbeusedasintermediarynodesonthecomputedpaths.ProcedureD=W;(Wisthematrixrepresentationoftheedgeweights)Foru=1to|V|doFors=1to|V|doForv=1to|V|doDs,v=minDs,v,Ds,u+Wu,vEndForEndForEndForNotethatthisalgorithmcompletesinO(|V|3)time,Floyd-WarshallAlgorithm(Example),V1,2,3,4,1,5,V2,V3,V5,V4,4,1,1,8,3,2,2,6,D=WForu=1to|V|doFors=1to|V|doForv=1to|V|doDs,v=minDs,v,Ds,u+Wu,vEndForEndForEndFor,V1,V2,V3,V4,V5,V1,V2,V3,V4,V5,Floyd-WarshallAlgorithm(Example,DistributedAsynchronousShortestPathAlgorithms,EachnodecomputesthepathwiththeshortestweighttoeverynetworknodeThereisnocentralizedcomputationAsforthedistributedMSTalgorithmdescribedinGallager,Humblet,andSpiral,controlmessagingisrequiredtodistributedcomputationAsynchronousmeansherethatthereisnorequirementofinter-nodesynchronizationforthecomputationperformedateachnodeoffortheexchangeofmessagesbetweennodes,DistributedDijkstraAlgorithm,ThereisnoneedtochangethealgorithmEachnodefloodsperiodicallyacontrolmessagethroughoutthenetworkcontaininglinkstateinformationtransmissionoverheadisO(|V|x|E|)EntiretopologyknowledgemustbemaintainedateachnodeFloodingofthelinkstateinformationallowsfortimelydisseminationofthetopologyasperceivedbyeachnode.Eachnodehastypicallyaccurateinformationtobeabletocomputetheshortestpaths,AssumeGcontainsonlycyclesofnon-negativeweightIf(u,v)Ethensois(v,u)TheupdateequationisN(s)=NeighborsofsEachnodeonlyneedstoknowtheweightsoftheedgesthatareincidenttoit,theidentityofallthenetworknodesandestimates(receivedfromitsneighbors)ofthedistancestoallnetworknodes,DistributedBellman-FordAlgorithm,EachnodestransmitstoitsneighborsitscurrentdistancevectorDs,VLikewiseeachneighbornodeuN(s)transmitstositsdistancevectorDu,VNodesupdatesDs,v,vVsinaccordancewith:IfanyupdatechangesadistancevaluethenssendsthecurrentversionofDs,vtoitsneighborsNodesupdatesDs,veverytimethatitreceivesadistancevectorinformationfromanyofitsneighborsAperiodictimerpromptsnodestorecomputeDs,VortotransmitacopyofDs,Vtoeachofitsneighbors,DistributedBellman-FordAlgorithm,DistributedBellman-FordAlgorithmExample,A,B,E,C,D,7,1,2,8,1,2,A,B,E,C,D,7,1,2,8,1,2,EreceivesDsroutesandupdatesitsDs,V,DistributedBellman-FordAlgorithmExample,A,B,E,C,D,7,1,2,8,1,2,AreceivesBsroutesandupdatesitsDs,V,A,B,E,C,D,7,1,2,8,1,2,AreceivesEsroutesandupdatesitsDs,V,DistributedBellman-FordAlgorithmExample,A,B,E,C,D,7,1,2,8,1,2,A,B,E,C,D,7,1,2,8,1,2,DistanceVectorProtocols,EachnodemaintainsaroutingtablewithentriesDestination,NextHop,Distance(cost)NodesexchangeroutingtableinformationwithneighborsWhenevertablechangesPeriodicallyUponreceptionofaroutingtablefromaneighboranodeupdatesitsroutingtableiffindsa“better”routeEntriesintheroutingtablearedeletediftheyaretooold,i.e.theyarenot“refreshed”withincertaintimeintervalbythereceptionofaroutingtable,LinkFailure,A,B,E,C,D,G,F,Simplereroutingcase,FdetectsthatlinktoGhasfailedFsetsadistanceoftoGandsendsupdatetoAAsetsadistanceoftoGsinceitusesFtoreachGAreceivesperiodicupdatefromCwith2-hoppathtoG(viaD)AsetsdistancetoGto3andsendsupdatetoFFdecidesitcanreachGin4hopsviaA,LinkfromAtoEfailsAadvertisesdistanceoftoEBandChadadvertisedadistanceof2toE(priortothelinkfailure)UponreceptionofAsroutingupdateBdecidesitcanreachEin3hops;andadvertisesthistoAAdecidesitcanreadEin4hops;advertisesthistoCCdecidesthatitcanreachEin5hops,LinkFailure,A,B,E,C,D,G,F,Routingloopcase,Thisbehavioriscalledcount-to-infinity,Count-to-InfinityProblem,A,B,C,D,E,(A,1),(A,2),(A,3),(A,3),(A,2),(A,1),(A,4),Example:routersworkinginstablestate,RoutingupdateswithdistancestoAareshown,Count-to-InfinityProblem,A,B,C,D,