《论文解读

admin管理员组

文章数量:1516870

《论文解读

论文

[1]毕晓伟,李斌,王育强,陈实华,彭平,雷涛.基于有向图模型的多星星上处理下传数据冲突优化决策方法[J].电子信息对抗技术,2020,35(06):46-49+77.

知网链接

有向图模型

即图论中的经典模型，对于图G(V,E) 其基本构成为图的顶点以及顶点之间的边，边存在权重和方向，每个顶点可能包含其它属性信息。

图论中最经典的求解问题是寻路问题，即给定开始节点、结束节点，寻找对于目标函数最优的路径，以最短路为目标函数，即退化为寻找开始顶点到结束顶点之间的最短路

卫星多星数传问题

地面接收终端在接收卫星星上数传数据时，只能在与卫星可见的时间窗口内，当地面接收终端在给定的时间段内同时接收到超过自身接收设备数量上限的卫星数传下传请求时，发生多星下传数据冲突。

求解模型

论文给定了一个简单容易理解的求解模型，即在给定规划的时间段内，按照到达顺序的前后，将卫星与地面接收设备可见时间窗口排序。

图的每一个顶点对应于一个可执行的卫星下传数据任务。

若两个下传任务之间没有时间段上的重合，认为两个任务不冲突，即可以由任务A完全执行完，同时可以在设备调整稳定时间之后，继而执行任务B，那么任务A到任务B存在一条有向边，边的权重对应于任务切换的开销信息。

对于未发生冲突的前后两个任务，认为其存在一条有向边，那么最终的问题转变为寻找从起点到终点的一条最优路径。

同时寻优的目标函数不同可能引发最终的任务执行序列不同

多星下传任务的优化目标

最终的每条边的权重是按照以上两个准则进行综合计算，每个影响因子的权重由领域先验知识给出，若1权重更大，则注重最终的规划收益，若2权重更大，则注重最终的规划任务数量。

寻找收益最大的路径

论文采取最短路的Dijkstra算法求解最大收益路径，但没有给出详细的求解思路

本文提供一种求解思路，最短路算法是结合边的权重寻找最短路径，但本问题权重是每个顶点的收益值，那么问题转化为寻找最大权重路径，思路如下：

首先添加两个辅助顶点V_start、V_end 然后求解单源最大收益路径。

伪代码如下：

int num_of_point = 100;
int m_min = -1;
int test_length = 1000;int max_path(vector<vector<int>> m_map)   //map[i][j]存放从i到j的收益  初始化时当且仅当 i -> j直接相连时  以j任务的观测收益初始化 否则初始化为0
{vector<int> dis(num_of_point, m_min);//初始化顶点到所有其他顶点的权益累积值为-1vector<bool> visit(num_of_point, false);//初始化所有节点未方位，即未加入到已计算集合visit[0] = true;//搜索起点为V[0]//初始化dis数组 若存在边 则dis为对应顶点的权重值 否则为-1for (int i = 1; i < num_of_point; i++){if (m_map[0][i] >0)  //存在有向边{dis[i] = m_map[0][i];}elsedis[i] = m_min;//不存在有向边 那么到对应顶点的收益为-1}//依次将后序 收益最大的顶点加入  同时更新原有路径（如果可能）for (int i = 0; i < num_of_point; i++){int index = -1;int m_max = -1;for (int j = 1; j < num_of_point; j++){if (visit[j] == false && dis[j] > m_max){m_max = dis[j];index = j;}}visit[index] = true;//标记位已访问for (int j = 1; j < num_of_point; j++)  //更新可能的更大权益{if (m_map[index][j] > 0 && dis[j] < dis[index] + m_map[index][j])  //当index的引入使得从起点到Index+  index-> j  （即index和j需要直接相连）{dis[j] = dis[index] + m_map[index][j];}}//结束以后  遍历dis中的最大值}int res = -1;for (int i = 1; i < num_of_point; i++){res = max(res, dis[i]);}return res;}

本文标签： 《论文解读