[發明專利]一種基于連接特征的多任務集合劃分方法

有效

• 申請號: 201310692186.7
• 申請日: 2013-12-17
• 公開（公告）號: CN103631751A
• 公開（公告）日: 2014-03-12
• 發明（設計）人: 胡威;鄒代坤;黎文飛;張凱;郭宏;李偉強;張若凡;徐景;譚練;江若成
• 申請（專利權）人: 武漢科技大學
• 主分類號: G06F15/163
• 分類號: G06F15/163;G06F9/50
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙) 42222
• 代理人: 張火春

1.一種基于連接特征的多任務集合劃分方法，其特征在于該實現方法的步驟如下：

步驟1、建立多任務模型

對于多任務，建立多任務模型G(T,P,Q)，其中：

T為任務的集合，T={t₀,t₁,…,t_m}；

P為pi_j的集合，pi_j=1表示任務t_i與任務t_j之間存在著通信關系，pi_j=0表示任務t_i與任務t_j之間不存在通信關系；

Q為q_ij的集合，q_ij=1表示任務t_i與任務t_j之間不存在通信關系，但通過任務t_i與其他任務之間的通信關系和通過任務t_j與其他任務之間的通信關系，任務t_i與任務t_j能被連通；

多任務模型G(T,P,Q)所具有的屬性為：

D(q_ij)為連通關系q_ij的屬性，表示任務t_i與任務t_j之間的連通所需要經過的任務數量；

w_ij是任務t_i的屬性，w_ij表示任務t_i與任務t_j之間的通信量，W為w_ij的集合；

L_i是任務t_i的屬性，表示與任務t_i存在通信關系的任務的數量；

H_i是任務t_i的屬性，表示任務t_i所有通信量之和；

步驟2、計算每個任務的連接特征因子θ_i

任務t_i的連接特征因子θ_i為：

θ_i=L_i×lg(H_i)?????(1)

然后對所有任務按照連接特征因子θ_i的大小進行降序排序，形成多任務集合T’；在排序過程中，如果多個任務具有相同大小的連接特征因子，則按照多個任務的序號大小進行降序排序；

步驟3、建立任務t_i的關聯任務集合

對于多任務集合T中的任務t_i，任務t_i的關聯任務集合S_i為與任務t_i具有通信關系或連通關系的所有任務的集合；對于關聯任務集合S_i中與任務t_i具有通信關系的任務t_j，S_i(t_j)=0；對于關聯任務集合S_i中與任務t_i具有連通關系的任務t_j，S_i(t_j)=D(q_ij)；

其中，Si(t_j)是任務t_i與任務t_j之間的關聯所需要經過的任務數量；若S_i(t_j)=0，表示任務t_i與任務t_j之間的關聯所需要經過的任務數量為0；若S_i(t_j)=D(q_ij)，表示任務t_i與任務t_j之間的關聯所需要經過的任務數量為D(q_ij)。

步驟4、按任務關聯集合Si對多任務集合T進行劃分

按照任務t_i的關聯性，對多任務集合T根據任務t_i之間的關聯進行劃分，劃分為g個相互之間沒有任何關聯的集合V₁,V₂,…,V_g，具體步驟是：

步驟4.1、對于任務t₀，將任務t₀和集合S₀中的所有任務加入到集合V₁當中；

步驟4.2、對于不在集合V₁中的任務t_i，將任務t_i和集合S_i中的所有任務加入到集合V₂當中；

步驟4.3、對于不在集合V₁和集合V₂中的任務t_j，將任務t_j和集合S_j中的所有任務加入到集合V₃當中；

步驟4.4、按照步驟4.1、步驟4.2和步驟4.3進行到第k步時，對于不在集合V₁,V₂,…V_k-1中的任務t_c，將任務t_c和集合S_c中的所有任務加入到集合V_k當中；直到完成第g個步驟，多任務集合T劃分為集合V₁,V₂,…,V_g；

步驟5、按照連接特征因子θ_i進行多任務集合劃分

對于步驟4中生成的集合V₁,V₂,…,V_g進行進一步的劃分，具體步驟是：

步驟5.1、設置收斂因子I，I為0或自然數；

步驟5.2、對于集合V₁,V₂,…,V_g中的一個集合V_i，對于在集合V_i中且多任務集合T’排序第一的任務t_x，按照多任務集合T’中的排序，檢查任務t_x與多任務集合T’中任務t_y之間的連通關系；如果S_x(t_y)<I，則將任務t_y從集合V_i中去除，建立集合V_g+1，并將任務t_y加入集合V_i’；

步驟5.3、對所有集合V_i’，均按照步驟5.1和步驟5.2進行操作，直到不再有新的集合生成；其中每次按照步驟5.1操作時，需重新設置收斂因子I；

步驟5.4、對于只有一個任務ti的集合，通過p_ij找到對應的任務編號最小的任務t_j所在的集合，將任務t_i所在的集合與任務t_j所在的集合合并，劃分完成。