Abstract: Fornavigationconstellationequippedwithdirectionalantennaswhichperformsdeterministiclinkscheduling,inter-satelliteroutingprobleminnotfully-connectedconstellationwasstudied.Firstly,thedynamictopologyofnavigationconstellationwasmodeledbasedontheevolvinggraphtheory,andthecorrespondingdatastructurewasgivenlater.Secondly,aroutingalgorithmtocomputetheearliestjourneywasproposed,thenthestepsandthecomplexityofthealgorithmwerediscussed.Finally,theaveragetimecostandaveragehopsofearliestjourneywereshownbysimulationundergivenparameters.Theimpactof startingtimeonearliestjourneywasalsodiscussed.

Key words: Inter-satellitelink, Topologicalconnectivity, Evolvinggraph, Routingalgorithm, Navigationconstellation