[發(fā)明專利]一種基于移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)的群智計(jì)算在線任務(wù)分配方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201810083243.4
• 申請(qǐng)日: 2018-01-29
• 公開(kāi)（公告）號(hào): CN108415760B
• 公開(kāi)（公告）日: 2021-11-30
• 發(fā)明（設(shè)計(jì)）人: 徐琴珍;李卓青;楊堤;楊綠溪
• 申請(qǐng)（專利權(quán)）人: 東南大學(xué)
• 主分類號(hào): G06F9/48
• 分類號(hào): G06F9/48
• 代理公司: 南京經(jīng)緯專利商標(biāo)代理有限公司 32200
• 代理人: 姜慧勤

1.一種基于移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)的群智計(jì)算在線任務(wù)分配方法，其特征在于，包括以下步驟：

步驟1，初始化任務(wù)請(qǐng)求者發(fā)布的待分配任務(wù)J＝{j₁,j₂,...,j_m,...,j_M}，其中，m＝1,…,M，j_m代表第m個(gè)待分配任務(wù)，M為待分配任務(wù)的總數(shù)；根據(jù)待分配任務(wù)類型和優(yōu)化目標(biāo)，將待分配任務(wù)按平均執(zhí)行時(shí)間進(jìn)行排序，得到有序任務(wù)列表；

步驟2，初始化候選用戶U＝{u₁,u₂,...,u_n,...,u_N}，其中，n＝1,…,N，u_n代表第n個(gè)愿意參與群智計(jì)算任務(wù)的候選用戶，N為候選用戶的總數(shù)；根據(jù)歷史交易記錄，計(jì)算每個(gè)候選用戶與任務(wù)請(qǐng)求者的相遇參數(shù){λ₁,λ₂,...,λ_n,...,λ_N}和各個(gè)候選用戶的歷史任務(wù)執(zhí)行時(shí)間比{p₁,p₂,...,p_n,...,p_N}，其中，λ_n和p_n分別代表第n個(gè)候選用戶與任務(wù)請(qǐng)求者的相遇參數(shù)和歷史任務(wù)執(zhí)行時(shí)間比；

步驟3，當(dāng)任務(wù)請(qǐng)求者與移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中某個(gè)候選用戶u_n相遇時(shí)，對(duì)該用戶進(jìn)行在線任務(wù)分配，具體為：

3-1，執(zhí)行離線全局虛擬分配方法，從步驟1得到的有序任務(wù)列表中的第一個(gè)任務(wù)開(kāi)始，計(jì)算所有候選用戶對(duì)該任務(wù)的預(yù)估反饋時(shí)間，并按從小到大的順序排序，將第一個(gè)任務(wù)分配給當(dāng)前預(yù)估反饋時(shí)間最小的用戶，同時(shí)更新該用戶的執(zhí)行等待時(shí)間，重新計(jì)算所有候選用戶對(duì)第二個(gè)任務(wù)的預(yù)估反饋時(shí)間并從小到大排序，將第二個(gè)任務(wù)分配給當(dāng)前預(yù)估反饋時(shí)間最小的用戶，以此類推，直到所有任務(wù)虛擬分配完成；

3-2，將步驟3-1的分配結(jié)果中屬于候選用戶u_n的任務(wù)真實(shí)分配給候選用戶u_n執(zhí)行，其他任務(wù)不分配；對(duì)已經(jīng)真實(shí)分配的任務(wù)和用戶進(jìn)行標(biāo)記，并從有序任務(wù)列表和候選用戶中刪除；

所述預(yù)估反饋時(shí)間，具體包括：

(1)任務(wù)請(qǐng)求者等待與某個(gè)候選用戶u_n初次相遇，期望相遇時(shí)間δ_n，當(dāng)二者已經(jīng)相遇時(shí)，δ_n＝0；二者還未相遇時(shí)，δ_n＝1/λ_n，λ_n為候選用戶u_n與任務(wù)請(qǐng)求者的相遇參數(shù)；

(2)候選用戶u_n對(duì)任務(wù)j_m的預(yù)估完成時(shí)間為T_nm，根據(jù)歷史任務(wù)平均執(zhí)行時(shí)間τ_m和歷史任務(wù)執(zhí)行時(shí)間比p_n，候選用戶u_n對(duì)任務(wù)j_m的預(yù)估執(zhí)行時(shí)間為：

若候選用戶u_n在執(zhí)行任務(wù)j_m之前還有前序未完成的任務(wù)，則預(yù)估完成時(shí)間T_nm還包括執(zhí)行前序任務(wù)的時(shí)間，即任務(wù)j_m的執(zhí)行等待時(shí)間，求和得到候選用戶u_n對(duì)任務(wù)j_m的預(yù)估完成時(shí)間為：

其中，∑t_nm代表候選用戶u_n過(guò)去參與執(zhí)行的所有任務(wù)消耗的總時(shí)間，∑τ_m代表所有人執(zhí)行候選用戶過(guò)去參與執(zhí)行的所有任務(wù)平均消耗的總時(shí)間，為任務(wù)j_m的執(zhí)行等待時(shí)間；

(3)任務(wù)請(qǐng)求者等待候選用戶回傳結(jié)果的時(shí)間δ_n'，等待候選用戶回傳結(jié)果需在任務(wù)完成后二者再次相遇時(shí)進(jìn)行，該時(shí)間為等待最后一次相遇的期望時(shí)間減去等待最后一次相遇的期望時(shí)間內(nèi)執(zhí)行任務(wù)占用的時(shí)間，即：

δ_n'＝1/λ_n-T_nm％(1/λ_n)

故候選用戶對(duì)待分配任務(wù)j_m的預(yù)估反饋時(shí)間為：FT_n(m)＝δ_n+T_nm+δ_n'；

步驟4，當(dāng)任務(wù)請(qǐng)求者與其他候選用戶相遇時(shí)，重復(fù)步驟3的過(guò)程，直到所有待分配任務(wù)真實(shí)分配完成。