[發(fā)明專利]多樣性約束的群智感知任務(wù)分配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202010149178.8
• 申請(qǐng)日: 2020-03-06
• 公開（公告）號(hào): CN111475266B
• 公開（公告）日: 2021-11-30
• 發(fā)明（設(shè)計(jì)）人: 張立臣;丁宇;宋星辰;李黎;郭龍江
• 申請(qǐng)（專利權(quán)）人: 陜西師范大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48;G06F9/50
• 代理公司: 西安永生專利代理有限責(zé)任公司 61201
• 代理人: 申忠才

1.一種多樣性約束的群智感知任務(wù)分配方法，其特征在于是由下述步驟組成：

(1)收集用戶和感知任務(wù)

感知任務(wù)集合Γ＝{τ₁，τ₂，...，τ_n}由n個(gè)任務(wù)組成，其中，每個(gè)任務(wù)τ_i為(N_i,s_i,e_i)，對(duì)應(yīng)一個(gè)執(zhí)行時(shí)間區(qū)間(s_i,e_i)和一個(gè)所需用戶人數(shù)N_i，s_i是任務(wù)τ_i的開始時(shí)間，e_i是任務(wù)τ_i的結(jié)束時(shí)間，滿足e_is_i，i∈{1,2,...,n}，n為有限的正整數(shù)，k為有限用戶類型集合C＝{c₁,c₂,…,c_k}所含用戶類型個(gè)數(shù)；

用戶集合U＝{u₁,u₂,…,u_m}由m個(gè)用戶組成，其中，每個(gè)用戶u_j對(duì)應(yīng)一個(gè)用戶類型c_j∈C、一個(gè)空閑時(shí)間區(qū)間(s_j,e_j)和一組執(zhí)行任務(wù)τ_i的收益v_ij，其中，j∈{1,2,...,m}，e_js_j，v_ij≥0；

每個(gè)任務(wù)τ_i對(duì)每個(gè)用戶類型c_t∈C具有多樣性約束參數(shù)和其中，t∈{1,2,...,k}，

(2)確定任務(wù)的可用用戶

確定每個(gè)任務(wù)τ_i∈Γ的可用用戶集合A_i如下：

A_i＝{u_j|u_j∈U,s_j≤s_i,e_j≥e_i}

(3)選擇任務(wù)分配用戶

1)對(duì)每個(gè)任務(wù)τ_i∈Γ，每一個(gè)用戶類型c_t∈C，按用戶u_j執(zhí)行任務(wù)的收益v_ij，從大到小分別對(duì)可用用戶集合A_i中用戶類型為c_t的用戶集合中的用戶進(jìn)行排序，其中：

2)對(duì)每個(gè)任務(wù)τ_i∈Γ，每一個(gè)用戶類型c_t∈C，按如下公式分別從可用用戶集合A_i中用戶類型為c_t的用戶集合中選擇前個(gè)用戶組成任務(wù)τ_i的可分配用戶集合U_i

其中是可用用戶集合A_i中用戶類型為c_t的用戶集合中的用戶個(gè)數(shù)，是可分配用戶集合U_i中用戶類型為c_t的用戶集合；

3)按如下公式選擇一個(gè)待分配任務(wù)τ_p，將待分配任務(wù)τ_p移入已分配用戶的任務(wù)集合Γ’

|U_i|是可分配用戶集合U_i中的用戶個(gè)數(shù)，是可分配用戶集合U_i中用戶類型為c_t的用戶集合中的用戶個(gè)數(shù)，若不存在滿足條件的待分配任務(wù)τ_p，則分配結(jié)束；

4)對(duì)每一個(gè)用戶類型c_t∈C按用戶u_j執(zhí)行待分配任務(wù)τ_p的收益v_pj，從大到小分別對(duì)待分配任務(wù)τ_p的可分配用戶集合U_p中用戶類型為c_t的用戶集合中的用戶進(jìn)行排序，其中

5)對(duì)每個(gè)用戶類型c_t∈C，按如下公式分別從待分配任務(wù)τ_p的可分配用戶集合U_p中用戶類型為c_t的用戶集合中，選擇前個(gè)用戶加入待分配任務(wù)τ_p的被選用戶集合U_p’

其中，N_p是待分配任務(wù)τ_p的所需人數(shù)，是待分配任務(wù)τ_p的被選用戶集合U_p’中用戶類型為c_t的用戶集合；

6)按用戶u_j執(zhí)行待分配任務(wù)τ_p的收益v_pj，從大到小對(duì)集合U_p-U_p’中的用戶進(jìn)行排序，選擇前N_p-|U_p’|個(gè)用戶加入被選用戶集合U_p’，其中|U_p’|是被選用戶集合U_p’中的用戶個(gè)數(shù)；

(4)調(diào)整被選任務(wù)所分配的用戶

1)找出被選用戶集中收益最小的用戶u_min∈U_p’和未被選用戶集中收益最大的用戶u_max∈U_p-U_p’，若不存在收益最小的用戶u_min和收益最大的用戶u_max滿足下式，轉(zhuǎn)至步驟(4)的步驟5)

v_p,min＜v_p,max

其中，v_p,min和v_p,max分別是收益最小的用戶u_min和收益最大的用戶u_max執(zhí)行任務(wù)τ_p的收益；

2)選擇收益最小的可去用戶u’_min

其中，v_pj是用戶u_j執(zhí)行待分配任務(wù)τ_p的收益，是待分配任務(wù)τ_p對(duì)用戶u_j的用戶類型c_j的反向多樣性約束參數(shù)，是被選用戶集合U_p’中用戶類型為c_j的用戶集合中的用戶個(gè)數(shù)；若不存在收益最小的可去用戶u’_min，轉(zhuǎn)至步驟(4)的步驟5)；

3)選擇收益最大的可加用戶u’_max

其中，是待分配任務(wù)τ_p對(duì)用戶u_j的用戶類型c_j的正向多樣性約束參數(shù)；若不存在收益最大的可加用戶u’_max，轉(zhuǎn)至步驟(4)的步驟5)；

4)將收益最大的可加用戶u’_max移入U(xiǎn)_p’，將收益最小的可去用戶u’_min移出U_p’

U_p'＝U_p'∪{u'_max}-{u'_min}

轉(zhuǎn)至步驟(4)的步驟1)；

5)按下式更新與待分配任務(wù)τ_p有時(shí)間沖突的任務(wù)τ_conf∈Γ_conf所對(duì)應(yīng)的可用用戶集A_conf

A_conf＝A_conf-U_p'

其中

其中，(s_conf,e_conf)是與待分配任務(wù)τ_p有時(shí)間沖突的任務(wù)τ_conf的執(zhí)行時(shí)間區(qū)間，轉(zhuǎn)至步驟(3)，直到不存在滿足條件的待分配任務(wù)。