买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜合肥工业大学申请的专利一种基于变邻域搜索启发式的中继卫星任务调度方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN115441936B 。

龙图腾网通过国家知识产权局官网在2023-09-26发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202211074908.8，技术领域涉及：H04B7/185；该发明授权一种基于变邻域搜索启发式的中继卫星任务调度方法是由龙建成;王世民;袁凯;开彩红;郭嘉琪;徐小明;丁建勋设计研发完成，并于2022-09-02向国家知识产权局提交的专利申请。

本一种基于变邻域搜索启发式的中继卫星任务调度方法在说明书摘要公布了：本发明公开了一种基于变邻域搜索启发式的中继卫星任务调度方法，包括：1、构建卫星调度的数学模型，2、为卫星中的发送设备和接收设备安排初始调度方案，3、采用邻域搜索算子对当前解进行扰动，4、对步骤3扰动后的解进行局部搜索，5、采用模拟退火方式来更新当前解，6、更新迭代次数和最优解。本发明能够在较短的时间内为中继卫星系统提供合理调度方案，从而能提高中继卫星资源的利用率。

本发明授权一种基于变邻域搜索启发式的中继卫星任务调度方法在权利要求书中公布了：1.一种基于变邻域搜索启发式的中继卫星任务调度方法，其特征是应用于由一个中继卫星与若干个近地卫星进行信息交互的场景中，所述中继卫星内设置有接收设备集合和发送设备集合将中继卫星向近地卫星传输信息的事件记为发任务，且所述发任务由所述发送设备服务；将近地卫星向中继卫星传输信息的事件记为收任务，且所述收任务由所述接收设备服务；将中继卫星和近地卫星同时向对方传输信息的事件记为双向任务，且所述双向任务由所述接收设备和发送设备同时服务；其中，Hp表示第p个发送设备，Rq表示第q个接收设备；m1表示发送设备的数量，m2表示接收设备的数量，令由n1个发任务构成的集合记为令由n2个收任务构成的集合记为令由n3个双向任务构成的集合记为其中，表示第i个发任务，表示第j个收任务，表示第k个双向任务；令第i个发任务的个时间窗构成的集合为其中，表示第i个发任务的第w个时间窗；令第j个收任务的个时间窗构成的集合为其中，表示第j个收任务的第w个时间窗；令第k个双向任务的个时间窗构成的集合为其中，表示第k个双向任务的第w个时间窗；所述中继卫星任务调度方法包括以下步骤：步骤1、将集合J3中的每个双向任务均拆分一个发任务和一个收任务，由双向任务拆分后的发任务构成的集合记为由双向任务拆分后的收任务构成的集合记为其中，表示被双向任务拆分出的第k1个发任务，表示表示被双向任务拆分出的第k2个收任务；利用式1构建以优先级最高和开始服务时刻最早为目标的卫星任务调度模型： 式1中，表示第i个发任务的优先级，表示第j个收任务的优先级，表示第k个双向任务的拆分的发任务的优先级，大小等于的优先级；表示第i个发任务的开始服务时刻，表示第j个收任务的开始服务时刻，表示第k个双向任务的拆分成的发任务开始服务时刻，α是归一化系数，是双向任务拆分出的发任务的第k个时间窗；xipw表示发送设备Rp是否在第i个发任务的第w个时间窗内服务发任务若xipw＝1表示发送设备Rp服务在第i个发任务的第w个时间窗内服务发任务若xipw＝0表示发送设备Rp不在第i个发任务的第w个时间窗内服务发任务xjqw表示接收设备Hq是否在第j个收任务的第w个时间窗内服务收任务若xjqw＝1表示接收设备Hq服务在第j个收任务的第w个时间窗内服务收任务若xjqw＝0表示接收设备Hq不在第j个收任务的第w个时间窗内服务收任务表示发送设备Rp是否在拆分后的发任务的第w时间窗内服务发任务若表示发送设备Rp服务在在拆分后的发任务的第w个时间窗内服务发任务若表示发送设备Rp不在拆分后的发任务的第w个时间窗内服务发任务 式2表示每个发任务最多只能由一个发送设备选择一个时间窗服务；式3表示每个收任务最多只能由一个接收设备选择一个时间窗服务； 式4表示双向任务拆分出的发任务只能由一个发送设备选择一个时间窗服务；式5表示双向任务拆分出的收任务只能由一个接收设备选择一个时间窗服务；其中，是双向任务拆分出的收任务的第k个时间窗； 式6表示第i个发任务的时间窗约束，表示第i个发任务的第w个时间窗的左端，表示第i个发任务的第w个时间窗的右端，表示第i个发任务的结束服务时刻；式7中Si表示第i个发任务的服务时长；式8表示第j个收任务的时间窗约束，其中，表示第j个收任务的第w个时间窗的左端，表示第j个收任务的第w个时间窗的右端，表示第j个收任务的结束服务时刻；式9中Sj表示第j个收任务的服务时长； 式10表示第k个双向任务的分解出的发任务的时间窗约束；其中，表示第k个双向任务拆分出的发任务第w个时间窗的左端，表示第w个时间窗的右端，表示的开始服务时刻，表示的结束服务时刻；式11中Sk表示第k个双向任务的服务时长；式12表示第k个双向任务的分解出的收任务的时间窗约束；其中，表示分解出的收任务的开始服务时刻，表示的结束服务时刻； 式15和式16表示发送设备所服务的任务服务时间不冲突约束；式17和式18表示接收设备所服务的任务服务时间不冲突约束；步骤2、给每个设备构建可行的服务任务序列以得到初始调度方案Xinitiate：定义调度方案为所有的发送设备和接收设备所服务的任务序列；其中，令第p个发送设备Hp所服务的任务序列记为Lp；第q个接收设备Rq所服务的任务序列记为Aq；初始化所有的发送设备所服务的任务序列和所有接收设备所服务的任务序列为空集；步骤2.1、给所有发送设备安排所服务的发任务序列：步骤2.1.1、对集合J1中所有发任务按照第一个时间窗的左端进行升序排序，得到排序后的集合J′1；步骤2.1.2、初始化p＝1；令未被服务的发任务集合记为U1；并初始化U1＝J1；步骤2.1.3、对排序后的集合J′1依次遍历，并陆续将排序后的每个发送任务插入第p个发送设备Hp的任务序列末尾，直到插入的发送任务不满足式6为止，从而得到第p个发送设备Hp的任务序列Lp；步骤2.1.4、从U1中剔除第p个发送设备Hp的任务序列Lp中的发任务，得到更新后的发任务集合并赋值给U1；步骤2.1.5、令p+1赋值给p，返回步骤2.1.3顺序执行，直到p＞m1为止，从而得到所有发送设备的任务序列以及未被服务的发任务集合U1；步骤2.2、给所有接收设备安排所服务的收任务序列：步骤2.2.1、对集合J2中所有收任务按照第一个时间窗的左端进行升序排序，得到排序后的集合J′2；步骤2.2.2、初始化q＝1；令未被服务的收任务集合记为U2，并初始化U2＝J2；步骤2.2.3、对排序后的集合J′2依次遍历，并陆续将排序后的每个收任务插入第q个接收设备Rq的任务序列末尾，直到插入的收任务不满足式8为止，从而得到第q个接收设备Rq的任务序列Aq；步骤2.2.4、从U2中剔除第q个接收设备Rq的任务序列Aq中的收任务，得到更新后的收任务集合并赋值给U2；步骤2.2.5、令q+1赋值给q，返回步骤2.2.3顺序执行，直到q＞m2为止，从而得到所有接收设备的任务序列以及未服务的收任务集合U2；步骤2.3、将双向任务插入所述发送设备的任务序列和接收设备的任务序列中：步骤2.3.1、令未服务的双向任务记为U3，并初始化U3＝J3；步骤2.3.2、将每个发送设备的任务序列分别和接收设备的任务序列进行两两组合，从而得到m1×m2个组合任务序列；步骤2.3.3、依次遍历集合U3，将双向任务拆分成一个发任务和一个收任务依次遍历m1×m2个组合任务序列，再依次遍历组合任务序列中相邻任务之间的位置，找到能满足式10～式14的位置，并将插入组合任务序列中发送设备的任务序列的相应位置，将插入组合任务序列中接收设备的任务序列的相应位置，从而更新相应的组合任务序列；步骤2.3.4、从U3中剔除双向任务并将所得到的更新后的双向任务任务集合赋值给U3；步骤2.3.5、返回步骤2.3.3直到所有的双向任务都被插入组合任务序列中，或者没有双向任务能够插入为止，从而得到未被服务的双向任务集合U3；步骤2.3.6、由m1个发送设备的任务序列和m2个接收设备的任务序列所构成的调度方案记为Xinitiate；步骤3、构建邻域算子用于对当前调度方案X进行扰动，以扩大搜索空间：定义最大迭代次数为Imax；定义当前迭代次数为icur；并初始化icur＝1；第icur次迭代的调度方案记为初始化为Xinitiate；步骤3.1、构建邻域算子：定义邻域算子N1为：随机选择中一个发送设备的任务序列或者一个接收设备的任务序列，随机选择任务序列中的一个任务，先将其从相应任务序列中剔除，再随机重新插入相应任务序列中能满足式6或式8的一个位置；定义邻域算子N2为：随机选择中一个发送设备的任务序列或者一个接收设备的任务序列，随机选择同一任务序列中的两个任务，如果交换两任务的位置后设备的任务序列仍然满足式6或式8，则交换两个任务的位置；定义邻域算子N3为：随机选择中同为发送设备的两个任务序列或者同为接收设备的两个任务序列，并从两个任务序列中分别随机选择一个任务，如果交换两个任务后设备的任务序列仍然满足式6或式8，则交换两个任务的位置；定义邻域算子N4为：随机选择中一个发送设备的任务序列或者一个接收设备的任务序列，随机删除任务序列中的一个任务，并加入到相应未被服务的任务集合U1或U2或U3中；定义邻域算子N5为：随机选择中一个发送设备的任务序列或者一个接收设备的任务序列，随机删除任务序列中的一段连续任务，将连续任务插入其他相应的设备且能满足式6或式8的任务序列的位置中；定义邻域算子N6为：随机选择中一个被服务的双向任务，先将其从现在所在的设备序列中剔除，然后通过步骤2.3.1～步骤2.3.3找一对可行的位置并插入；步骤3.2、选择邻域算子的序列：定义邻域算子序列为其中，Nu表示第u个邻域算子，u∈[1，6]；初始化u＝1；步骤3.3、选择第u个邻域算子Nu，对进行扰动操作得到扰动后的调度方案步骤4、构建局部搜索算子对进行局部搜索：步骤4.1、构建局部搜索算子：局部搜索算子M1为：针对中每一个发送设备的任务序列和每一个接收设备的任务序列，依次遍历设备的任务序列中每一个任务，先将其从相应任务序列中剔除，再重新插入原任务序列中最优位置，所述最优位置为使得式1增量最大的位置，如果不能使式1增加，则恢复任务在原任务序列中的位置；局部搜索算子M2为：针对中每个发送设备的任务序列中所服务的任务进行两两组合，如果交换两个任务的位置，能使得式1增加，则交换两个任务，否则不进行交换，选择下一个组合进行操作；局部搜索算子M3为：针对中每个接收设备的任务序列中所服务的任务进行两两组合，如果交换两个任务的位置，能使得式1增加，则交换两个任务，否则不进行交换，选择下一个组合进行操作；局部搜索算子M4为：针对中两个发送设备的任务序列，或者两个接收设备的任务序列，将两个设备之间的任务进行两两组合，如果交换两个任务的位置，若能使得式1增加，则进行交换，否则不进行交换，选择下一个组合进行操作；局部搜索算子M5为：依次遍历未被服务的任务集合如果是发任务就插入发送设备序列中，如果是收任务就插入接收设备序列中，如果是双向任务就将其分解成一个发任务和一个收任务，并通过步骤2.3.1～步骤2.3.2找一对能使得式1增量最大的位置将双向任务插入，如不能使得式1增加，就选择下一个任务进行操作；局部搜索算子M6为：依次遍历中所有被服务的双向任务，先将其从现在所在的设备中剔除，然后通过步骤2.3.1～步骤2.3.3找一对能使得式1增量最大的位置并插入，如果不能使得式1增加，则恢复任务在原任务序列中的位置，选择下一个双向任务进行操作；步骤4.2、定义局部搜索算子的序列为其中，Mv表示第v个局部搜索算子；步骤4.3、依次采用Mset中的局部搜索算子对进行操作，得到的邻域调度方案步骤5、采用模拟退火的方式判断是否将赋值给最优调度方案Xbest；步骤6、如果icur＝Imax则停止迭代，输出Xbest作为最优调度方案，并输出最优调度方案对应的式1的目标函数值，否则将icur+1赋值给icur后，返回步骤3.3。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人合肥工业大学，其通讯地址为：230009 安徽省合肥市包河区屯溪路193号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。