This paper concentrates on designing an autonomous navigation scheme for Mars exploration. In this scheme, formation flying spacecraft are used to realise absolute orbit determination when orbiting around Mars. Inertial Line-Of-Sight (LOS) vectors from “deputy” spacecraft to the “chief” are measured using radio cross-link, optical devices and attitude sensors. Since the system's observability is closely related to the navigation performance, an analytical approach is proposed to optimise the observability. In this method, the gravity gradient tensor difference is chosen as the performance index to optimise two navigation scenarios. When there is one deputy flying around the chief, optimal parameters are obtained by solving the constrained optimisation problem. When a second deputy is added into the formation, the optimal configuration is also obtained. These results reveal that the observability is mainly determined by the magnitude of the in-track and cross-track distances in the configuration. An Extended Kalman Filter (EKF) is used to estimate the position and velocity of the chief. The results of a navigation simulation confirms that adding more deputies can significantly improve the navigational performance.