Abstract: Age of Information (AoI) characterizes the temporal properties of data collected by a system. To address the issue that traditional linear AoI fails to accurately characterize the nonlinear attenuation of sensor information value, a nonlinear growth AoI model was established, and two age metrics — Nonlinear Average Peak AoI (NAPAoI) and Nonlinear Average AoI (NAAoI) — were defined for this model. Two optimization problems were formulated based on these two age metrics; Unmanned Aerial Vehicle (UAV) trajectories were constrained using a mobility graph, and both problems were solved by planning the UAV's flight trajectory. Among them, the NAPAoI optimization problem was difficult to solve directly due to irreducibility constraints. First, the optimal stationary distribution was obtained using the Karush-Kuhn-Tucker (KKT) conditions. Then, original problem was transformed into finding the transition probability matrix of an irreducible Markov chain with the known optimal stationary distribution, and a random trajectory was subsequently derived via the Monte Carlo method. Experimental results show that this random trajectory is optimal in terms of NAPAoI. On the other hand, the NAAoI optimization problem is proven to be Non-deterministic Polynomial-hard (NP-hard). A Markov chain was used to model the random trajectory, and the NAAoI was optimized by minimizing the convergence time of the Markov chain to the stationary distribution, thus obtaining a random trajectory. The gap between its corresponding average age and the optimal average age does not exceed 8 times the mixing time. Meanwhile, analysis shows that the random trajectory optimal for NAPAoI exhibits superior NAAoI performance.

Key words: Wireless Sensor Network (WSN), Unmanned Aerial Vehicle (UAV), nonlinear Age of Information (AoI), Markov chain, trajectory planning

摘要： 信息年龄（AoI）能够刻画系统采集数据的时间特性。针对传统线性AoI无法准确描述传感器信息价值的非线性衰减问题，建立一种非线性增长的AoI模型，并定义该模型的非线性平均峰值信息年龄（NAPAoI）和非线性平均信息年龄（NAAoI）两个年龄指标。以两个年龄指标建立两个优化问题，使用移动图约束无人机（UAV）轨迹，通过规划UAV飞行轨迹，求解两个优化问题。其中，NAPAoI优化问题因存在不可约性约束而难以直接求解，先使用KKT(Karush-Kuhn-Tucker)条件求得最优平稳分布，将原问题转化为已知最优平稳分布寻找不可约马尔可夫链的的转移概率矩阵，继而使用蒙特卡洛算法求解得到随机轨迹,实验结果表明该随机轨迹是NAPAoI最优的。另一方面，证明NAAoI优化问题属于NP（Non-deterministic Polynomial）难问题，采用马尔可夫链建模随机轨迹，通过最小化马尔可夫链收敛到平稳分布的时间以优化NAAoI并得到随机轨迹，它对应平均年龄与最优平均年龄的差距不会超过混合时间的8倍，同时结果分析表明NAPAoI最优的随机轨迹的NAAoI性能较优。

关键词: 无线传感器网络, 无人机, 非线性信息年龄, 马尔可夫链, 轨迹规划