简介：

简介：Delaytolerantnetworks(DTNs)experiencefrequentandlonglastingnetworkdisconnectionduetovariousreasonssuchasmobility,powermanagement,andscheduling.OneprimaryconcerninDTNsistoroutemessagestokeeptheend-to-enddeliverydelayaslowaspossible.Inthispaper,westudythesingle-copymessageroutingproblemandproposeanoptimalopportunisticroutingstrategy—LeapfrogRouting—forprobabilisticallycontactedDTNswherenodesencounterorcontactinsomefixedprobabilities.Wededucetheiterativecomputationformulateofminimumexpectedopportunisticdeliverydelayfromeachnodetothedestination,anddiscoverthatundertheoptimalopportunisticroutingstrategy,messageswouldbedeliveredfromhigh-delaynodetolow-delaynodeintheleapfrogmanner.Rigoroustheoreticalanalysisshowsthatsucharoutingstrategyisexactlytheoptimalamongallpossibleones.Moreover,weapplytheideaofReverseDijkstraalgorithmtodesignanalgorithm.Whenadestinationisgiven,thisalgorithmcandetermineforeachnodetheroutingselectionfunctionundertheLeapfrogRoutingstrategy.ThecomputationoverheadofthisalgorithmisonlyO(n~2)wherenisthenumberofnodesinthenetwork.Inaddition,throughextensivesimulationsbasedonrealDTNtraces,wedemonstratethatouralgorithmcansignificantlyoutperformthepreviousones.