对星间链路数量非常有限、需要同时满足星间测距和星间通信需求的导航卫星网络的链路分配问题进行了研究。首先,分析了导航卫星网络的特点,并设计了一种基于有限状态自动机(FSA)的拓扑处理机制。然后,将星间测距需求作为一个约束,以星间通信的延时性能为优化目标,将导航卫星网络的链路分配问题建模为一个多目标优化问题。最后,针对建立的多目标优化问题,分别提出一种基于首次改善(FI)的本地搜索算法和基于模拟退火(SA)的启发式优化算法以对链路分配问题进行求解,并提出一种基于分支交换策略的新链路分配生成方法。仿真结果表明,通过FI算法和SA算法获得的优化链路分配的网络延时性能均得到了改进,且SA算法的性能要优于FI算法;同时,FSA的状态持续时间的减小有利于获得网络延时性能好的链路分配。