Cellular-connected unmanned aerial vehicles (UAVs) are expected to play an increasingly important role in future wireless networks. To facilitate the reliable navigation for cellular-connected UAVs, channel knowledge map (CKM) is considered a promising approach capable of tackling the non-negligible co-channel interference resulting from the high line-of-sight (LoS) probability of air-ground (AG) channels. Nevertheless, due to measurement constraints and the aging of information, CKM is usually incomplete and needs to be regularly updated to capture the dynamic nature of complex environments. In this paper, we propose a novel trajectory design strategy in which UAV navigation and CKM completion are incorporated into a common framework, enabling mutual benefits for both tasks. Specifically, a cellular-connected UAV deployed in an urban environment measures the radio information during its flight and completes the CKM with Kriging interpolation. Based on the method of grid discretization and spherical approximation, a mixed-integer multi-objective optimization problem is formulated. The problem falls into the category of combinatorial mathematics and is essentially equivalent to determining an optimum sequence of grid points to traverse. Through proper mathematical manipulation, the problem is reformulated as variants of two classic models in graph theory, namely the shortest-path problem (SPP) and the traveling salesman problem (TSP). Two navigation strategies based on the two different models are proposed and thoroughly compared based on numerical results to provide implementable methods for engineering practice and reveal the trade-offs between UAV navigation and CKM completion. Simulation results reveal that the proposed navigation strategies can quickly expand the Pareto boundary of the problem and approach the performance of fully-known CKM.

翻译：蜂窝连接无人机（UAV）预计将在未来无线网络中发挥日益重要的作用。为保障蜂窝连接无人机的可靠导航，信道知识图（CKM）被视为一种有前景的方法，能够应对空对地（AG）信道高视距（LoS）概率带来的不可忽视的同信道干扰。然而，由于测量限制与信息时效性，CKM通常不完整，需定期更新以捕捉复杂环境的动态特性。本文提出一种新颖的轨迹设计策略，将无人机导航与CKM补全纳入统一框架，实现两项任务的协同增益。具体而言，部署于城市环境的蜂窝连接无人机在飞行过程中测量无线电信信息，并利用克里金插值法补全CKM。基于网格离散化与球面近似方法，构建了一个混合整数多目标优化问题。该问题属于组合数学范畴，本质上等价于确定最优的网格点遍历序列。通过适当的数学变换，问题被重构为图论中两个经典模型——最短路径问题（SPP）和旅行商问题（TSP）的变体。本文提出了基于这两种不同模型的导航策略，并依据数值结果进行全面比较，为工程实践提供可实施方案，同时揭示无人机导航与CKM补全之间的权衡关系。仿真结果表明，所提出的导航策略能快速扩展问题的帕累托边界，并逼近完全已知CKM的性能水平。