袁 姝，周朝榮,2+，楊正清，王婧柔

(1.四川師范大學 物理與電子工程學院，四川 成都 610101；2.成都信息工程大學 氣象信息與信號處理四川省高校重點實驗室，四川 成都 610225)

0 引 言

群智感知(crowdsensing，CS)[1,2]利用智能設備收集數(shù)據(jù)，提供了靜態(tài)傳感器網(wǎng)絡難以支持的大規(guī)模應用服務，比如ParkSense[3]等。為了更好地支持各類應用服務，群智感知系統(tǒng)要求在某些約束條件下將任務分配給合適的工人，工人移動到對應位置執(zhí)行任務，這樣的任務分配問題是當前群智感知相關研究領域中的熱點。

目前，已有學者針對群智感知系統(tǒng)中的任務分配問題展開研究。文獻[4,5]考慮到任務的執(zhí)行時長分配任務，但忽略了工人的在線時間限制。因此，針對工人在線時間存在限制的情況，文獻[6,7]利用感知設備的可用時間代表工人的在線時間，從而分配任務。然而，工人的在線時間并非簡單等同于感知設備的可用時間。為了避免此局限，文獻[8,9]分別用工人活躍時間與最晚工作時間來表示工人的在線時間，但忽略了工人在線時間的不確定性。此外，考慮到工人的在線時間，則不能忽視工人的時間成本。雖然文獻[10]考慮了預算對任務分配的影響，但預算中忽略了工人的延時成本與空閑成本。

為此，考慮工人在線時間為彈性時間的情況，采用模糊機會約束規(guī)劃方法[11]對工人的在線時間進行建模，并引入延時成本與空閑成本。對應的任務分配問題為組合優(yōu)化問題，屬于NP-hard問題范疇，不存在時間有效的最優(yōu)算法，只能考慮次優(yōu)算法。鑒于鯨魚優(yōu)化算法(whale optimization algorithm，WOA)[12]具有全局搜索能力強等優(yōu)點，利用WOA設計了兩階段算法求解該任務分配問題。仿真結果表明，所提出的算法與其它算法相比具有更好的搜索性能；同時，較之于固定在線時間，考慮彈性在線時間工人效率更高且工人成本更低。

1 問題描述與系統(tǒng)模型

考慮一個存在t個感知任務以及w個注冊工人的群智感知系統(tǒng)。其中，T={T1,…,Tt} 以及W={W1,…,Ww} 分別表示任務集合與工人集合。對于任務i來說，TTi為該任務執(zhí)行所需時間；對于工人j來說，WTj為該工人在注冊時設定的預計在線時間。為便于問題的描述，給出以下定義。

定義1 任務執(zhí)行時間MissionTime： 任務執(zhí)行時間為工人執(zhí)行系統(tǒng)所分配任務的總時間花費，其定義如式(1)所示

(1)

其中，Vj表示分配給工人j的任務集合。

定義2 空閑時間IdleTime： 工人在預計在線時間內(nèi)未執(zhí)行任務的時間稱作空閑時間，其定義如式(2)所示

ITj=WTj-MTj

(2)

此時，WTj≥MTj。

定義3 延時時間DelayTime： 工人任務執(zhí)行時間超過工人預計在線時間的情況下，工人實際在線時間即為工人任務執(zhí)行時間，而工人超出預計在線時間的部分則為延時時間，其定義如式(3)所示

DTj=MTj-WTj

(3)

根據(jù)工人存在空閑時間定義工人空閑代價如式(4)所示

ICj=α*ITj

(4)

其中，α為單位空閑時間代價。

此外，根據(jù)工人存在延時時間定義工人延時代價如式(5)所示

DCj=β*DTj

(5)

其中，β為工人單位延時代價。

在任務分配之前，由于工人還沒有開始執(zhí)行任務，工人不能確定自己是否會在執(zhí)行任務之后選擇延長在線時間，此時，系統(tǒng)考慮工人均不延長在線時間，從而為工人初次分配任務。V′={V0′,V1′,V2′,V3′,…,Vw′} 表示此時感知任務的分配結果。其中，V0′為感知系統(tǒng)中未被分配的任務集合；V1′～Vw′分別表示感知系統(tǒng)為工人分配的任務集合。在這個階段，由于系統(tǒng)考慮工人均不延長在線時間，工人的任務執(zhí)行時間均不超過工人預計在線時間。此時，若工人存在空閑時間，則會產(chǎn)生空閑代價ICj′， 確定此時工人總代價(TotalCost)為

(6)

在初次任務分配之后，工人能夠根據(jù)自身空閑情況以及后續(xù)安排決定是否考慮延長在線時間。此時，利用工人時間約束可能性(即工人不選擇延長時間的可能性)及置信水平大小來表示工人最終是否選擇延時。根據(jù)模糊機會約束規(guī)劃方法，當工人時間約束可能性大于置信水平時，工人必須保證任務執(zhí)行時間不超過預計在線時間，此時工人不選擇延長在線時間來執(zhí)行額外任務；而當工人時間約束可能性小于置信水平時，工人選擇延長在線時間來執(zhí)行額外任務，此時給工人分配額外任務?；诖?，對初次任務分配的結果進行調(diào)整。集合V={V0,V1,V2,V3,…,Vw} 表示最終任務分配結果。同理，V0為最終任務分配后未被分配的任務集合；V1～Vw表示工人最終的任務分配集合。分配完成后，根據(jù)工人是否選擇延時確定工人代價為延時代價或空閑代價

(7)

對應的工人效率也分為兩種情況

(8)

基于上述定義，考慮工人彈性在線時間的任務分配模型給出如下

(9)

約束條件

(10)

V0∪V1∪…∪Vw=T

(11)

V0∩Vj=?,Wj∈W

(12)

Vk∩Vj=?,j≠k

(13)

|Vj|≥1,Wj∈W

(14)

Cr(WTj-MTj≥0)>τ,Wj∈W

(15)

TC≤TC′

(16)

?WTj,WTj-TTi≥0,Ti∈T,Wj∈W

(17)

其中，式(9)為優(yōu)化目標即最大化工人總效率；式(10)與式(11)表示分配的任務為系統(tǒng)中發(fā)布的任務；式(12)與式(13)表示一個任務不能同時出現(xiàn)在工人任務集合以及未分配任務集合中；式(14)表示每個工人至少需要完成一個任務；式(15)為工人在線時間的模糊機會約束，其中τ為置信水平，采用模糊機會約束規(guī)劃模型建模，在一定程度上允許工人實際在線時間超過工人預計在線時間；式(16)表示引入彈性時間之后工人總代價不能超過未引入彈性時間的工人總代價；式(17)表明至少存在一個工人的預計在線時間超過所需執(zhí)行時間最長的任務，保證執(zhí)行時間最長的任務在初次分配時能夠有機會被執(zhí)行。由于考慮工人在線時間為彈性的任務分配問題是組合優(yōu)化問題，屬于NP-hard問題的范疇，不存在時間有效的最優(yōu)算法，只能考慮次優(yōu)算法，所以在求解時考慮使用智能算法。相較于其它智能算法，鯨魚優(yōu)化算法能夠更好地平衡全局尋優(yōu)和局部尋優(yōu)階段且收斂速度更快，因此，在求解式(9)～式(17)所確定的任務分配問題時考慮采用鯨魚優(yōu)化算法。

2 求解算法

鯨魚優(yōu)化算法[12]是由Mirjalili等提出，其思想源自座頭鯨的捕食行為。根據(jù)座頭鯨的捕食行為將算法分為3個階段：包圍獵物，氣泡網(wǎng)攻擊，搜索獵物。由于鯨魚優(yōu)化算法最初提出是為了求解連續(xù)問題，而上述任務分配問題為組合優(yōu)化問題，因此，需要對鯨魚優(yōu)化算法進行改進，使之更加適合求解該任務分配問題。

2.1 改進鯨魚優(yōu)化算法

2.1.1 鯨魚優(yōu)化算法過程

包圍獵物階段：座頭鯨根據(jù)獵物的位置更新自身位置，從而接近獵物，稱作包圍獵物階段。相關定義如式(18)所示

(18)

(19)

(20)

氣泡網(wǎng)攻擊階段：氣泡網(wǎng)攻擊階段座頭鯨螺旋移動并吐出氣泡以包圍獵物。此時，座頭鯨的螺旋運動軌跡定義如式(21)所示

(21)

綜合上述兩個階段，此時座頭鯨處于已經(jīng)發(fā)現(xiàn)獵物并且向獵物移動的過程，因此，這兩個階段也稱作局部搜索階段。通過觀察發(fā)現(xiàn)，座頭鯨在獵物周圍游動行為同時包括了包圍獵物以及氣泡網(wǎng)攻擊兩種行為。因此，為了描述此時座頭鯨的行為，假設座頭鯨包圍獵物以及氣泡網(wǎng)攻擊的概率各為50%，此時，座頭鯨行為總結如下

(22)

其中，p為[0,1]之間的隨機數(shù)。

搜索獵物階段：在這個階段，座頭鯨還處于尋找獵物階段，它們根據(jù)彼此位置在空間內(nèi)進行隨機搜索。因此，這部分也稱作全局搜索階段，其定義如下

(23)

(24)

2.1.2 編碼及改進

由于鯨魚優(yōu)化算法最初提出是為了求解連續(xù)優(yōu)化問題，而工人彈性在線時間的任務分配為組合優(yōu)化問題，其中涉及到任務和工人的配對問題，因此需要對任務與工人序列進行編碼并且對鯨魚優(yōu)化算法進行改進，使之能夠求解該任務分配問題。

分別將任務和工人編碼成兩個序列。 [N1,N2,N3,…,Nt] 表示t個任務的排列，其中Ni∈{1,2,3,…,t}； [m1,m2,m3,…,mt] 表示任務對應的執(zhí)行工人排列，其中mi∈{0,1,2,…,w}。 當mj=0時，表明任務序列中Nj任務未被分配；而當mj≠0時，表示對應位置的任務分配給對應位置的工人，從而確定任務分配結果。對應的任務序列和工人序列相結合為一個鯨魚，此時，工人總效率即為鯨魚優(yōu)化算法的適應度值。在利用鯨魚優(yōu)化算法進行組合優(yōu)化問題求解時，額外設計反轉模塊與局部搜索模塊以保證算法的搜索性能。為更好描述反轉模塊與局部搜索模塊，假設系統(tǒng)中存在9個任務和3個工人。初始化任務序列為[1 2 3 4 5 6 7 8 9]，隨機生成工人序列為[1 2 3 1 2 3 1 2 1]，相同位置的任務和工人構成任務-工人對，表示該任務由該工人執(zhí)行。

反轉模塊：如圖1所示，選擇反轉起始點為4，反轉長度為4，則需要反轉的任務序列為4 5 6 7；反轉之后該任務序列變?yōu)閇1 2 3 7 6 5 4 8 9]。根據(jù)優(yōu)化后的任務及工人序列可以發(fā)現(xiàn)任務分配發(fā)生了變化。

圖1 反轉模塊

圖2 局部搜索模塊

局部搜索：如圖2所示，選擇任務序列中的第5個元素進行局部搜索優(yōu)化，因此，將第5個元素即任務6剔除，選擇第2個位置將該任務重新插入，則該任務序列變?yōu)閇1 6 2 3 7 5 4 8 9]。結合隨機生成的工人序列可知，任務分配發(fā)生了變化，使得任務分配的優(yōu)化結果跳出局部最優(yōu)。

2.2 兩階段任務分配算法

針對式(9)～式(17)所確定的任務分配模型，設計任務分配過程為兩個階段：初次分配與彈性調(diào)整。初次分配階段中群智感知系統(tǒng)首先將系統(tǒng)中所有任務初步分配給注冊工人，系統(tǒng)預評估感知系統(tǒng)所分配任務需花費的總時間，當發(fā)現(xiàn)某工人執(zhí)行完某個任務之后，執(zhí)行接下來的任務會使工人任務執(zhí)行時間超過工人預計在線時間，此時，系統(tǒng)確定分配給工人的任務為不超過預計在線時間的部分任務。沒有被執(zhí)行的任務聚集在一起為未分配任務，此時，工人的總代價中都只存在空閑代價，初次分配階段完成。其過程如算法1所示。

算法1： 初次分配

輸入： 工人信息W及任務信息T, 初始化工人任務執(zhí)行時間MTj’=0(j=1,2,…,w),工人空閑時間ITj’=0 (j=1,2,…,w)， 工人總代價TC’=0,單位空閑代價c。

系統(tǒng)將任務隨機分配給工人， 生成任務分配集Vj(j=1,2,…,w)

forj=1 towdo

forTvinVjdo

ifMTj’+TTv=

MTj’=MTj’+TTv

else

將該任務從該工人任務集中轉移到未分配任務中

endif

endfor

ITj’=WTj-MTj’

TC’=TC’+c*ITj’

endfor

輸出：工人最終任務集Vj’，未分配任務集V0’，總代價TC。

完成初次分配后，系統(tǒng)開始彈性調(diào)整階段。在彈性調(diào)整階段中，根據(jù)每個工人的時間約束可能性以及預設的置信水平，確定工人是否選擇延時，從而確定是否為工人分配額外任務。當工人的時間約束可能性大于置信水平時，說明工人任務執(zhí)行時間不能超過工人預計在線時間，此時工人不選擇延長時間；當工人時間約束可能性小于置信水平時，此時工人選擇延長時間，執(zhí)行額外任務，因此將未分配任務集中的某一個任務從未分配任務集中剔除，分配給該工人，在分配該任務時保證任務分配成功后的工人代價不能夠超過初次分配時的工人代價。其過程如算法2所示。

算法2： 彈性調(diào)整

輸入： 任務分配集合Vj’(j=0,1,…,w), 工人時間約束可能性Pbj(j=1,…,w)， 預設置信水平z, 初次分配分配階段工人總代價TC’, 初始化最終工人總代價TC=TC’。

forj=1towdo

ifPbj

未分配任務集中選擇一個任務預分配分配給工人j

計算TC

ifTC’

將該任務分配給工人j

endif

endif

更新工人任務集、 未分配任務集

endfor

輸出： 最終工人任務集合Vj(j=0,1,…,w)， 工人總代價TC。

綜合以上兩個階段，在基于鯨魚優(yōu)化算法設計的兩階段任務分配算法中,首先執(zhí)行初次分配，即根據(jù)工人、任務的相關信息隨機分配任務，然后利用改進鯨魚優(yōu)化算法對隨機分配結果進行優(yōu)化；接著執(zhí)行彈性調(diào)整，即根據(jù)初次分配結果以及工人時間約束可能性判斷工人是否選擇延長時間，從而確定是否選擇額外任務分配給該工人，經(jīng)過多次迭代之后得到一個較優(yōu)的結果。完整的任務分配過程如算法3所示。

算法3： 離散鯨魚算法

輸入： 置信水平z， 工人集W， 任務集T， 工人時間約束可能性Pbj(j=1,2,…,w), 迭代次數(shù)maxIter

初始化種群Xi(i=1,2,…,n)

計算工人總效率

X*=工人總效率最高的任務分配方案

Whilet

fori=1tondo

更新鯨魚優(yōu)化算法中參數(shù)a,A,C,l和p

改進鯨魚優(yōu)化算法優(yōu)化初次分配

彈性調(diào)整

endfor

計算每個個體適應度值

更新X*

t=t+1

endwhile

2.3 算法的計算復雜性

假設算法的最大迭代次數(shù)為T，種群大小為P，工人數(shù)量為W。由算法3可知，完整算法中包含初次分配以及彈性調(diào)整兩個階段。在初次分配以及彈性調(diào)整中，算法的時間復雜度均只與工人數(shù)量有關，表示為O(W)。 由于兩部分都處于種群迭代優(yōu)化的內(nèi)層，因此，算法3的時間復雜度為O(TPW)。 可以看出，算法的時間復雜度是隨種群大小、迭代次數(shù)以及工人數(shù)量線性增長的，這樣的復雜度是可以接受的。

3 仿真結果與分析

通過仿真實驗驗證所設計任務分配算法的性能，系統(tǒng)參數(shù)見表1。由于工人選擇延時會執(zhí)行額外任務，從而得到額外收益，使得工人延時成本降低；而工人空閑時，由于不執(zhí)行任務而沒有額外收益，不能降低空閑成本，因此，設置工人單位延時成本小于單位工人空閑成本?；诒?中的參數(shù)設置，我們首先分析置信水平對各算法中選擇彈性時間的工人數(shù)量的影響。然后，對比分析工人數(shù)量變化、置信水平變化以及彈性工人數(shù)量變化時，所提任務分配算法與基于遺傳算法(genetic algorithm，GA)[13]、貪婪算法(greedy algorithm，Greedy)以及隨機分配(random allocation，RA)的任務分配算法的性能比較。其中，基于遺傳算法的任務分配算法中，遺傳算法被用于優(yōu)化初步分配結果；基于貪婪算法的任務分配算法中，依次為工人分配使得當前工人總效率達到最大的任務；基于隨機的任務分配算法中，根據(jù)工人是否選擇彈性時間將任務隨機分配給工人。最后，驗證考慮工人彈性時間相較于不考慮工人彈性時間的優(yōu)勢。本文算法均以MATLAB R2014a為仿真平臺，所用機器配置為Intel?CoreTMi7-4710MQ 2.50GHz 8GB RAM，操作系統(tǒng)為Windows。

利用模糊機會約束方法對工人在線時間建模，工人能夠根據(jù)自身情況選擇是否延時以執(zhí)行額外任務，因此，每次仿真選擇彈性時間的工人數(shù)可能不同，從而影響優(yōu)化的結果。在仿真中預設置信水平，隨機生成工人的時間約束可能性，當某個工人的該時間約束可能性大于置信水平時，判定該工人不選擇彈性時間，當該工人的可能性小于置信水平時，則該工人選擇彈性時間，可以看出置信水平的大小會影響到選擇彈性時間的工人數(shù)，將選擇彈性時間的工人稱作彈性工人。表2給出了經(jīng)過重復多次實驗后在不同的置信水平下基于鯨魚優(yōu)化算法、遺傳算法、隨機分配以及貪婪算法的任務分配算法中彈性工人數(shù)量的平均值。從表2可以看出，隨著置信水平的增加，算法中的彈性工人數(shù)量也在增加，彈性工人數(shù)量在總工人數(shù)中所占比例大約等于置信水平。這說明選擇彈性時間的工人數(shù)量會受到置信水平的影響，當置信水平越大時，能夠滿足延時要求的工人數(shù)量就越多，此時，就有越多的工人選擇彈性時間。

表1 參數(shù)設置

表2 彈性工人數(shù)量隨置信水平變化的變化

為了驗證置信水平對工人效率的影響，分別取置信水平為 [0.3,0.4,0.5,0.6,0.7] 時進行多次仿真，從而得到圖3結果?？梢园l(fā)現(xiàn)在不同的置信水平下，相較于遺傳算法、隨機分配算法以及貪婪算法，鯨魚優(yōu)化算法得到的工人效率最高。此外，在不同算法中工人效率均會隨置信水平的增加而增加。

圖3 工人效率隨置信水平變化而變化

圖4給出了工人效率隨工人數(shù)變化而變化的趨勢?？梢钥闯鲭S著工人數(shù)量的增加，工人總效率也相應增加，而基于鯨魚優(yōu)化算法制定的任務分配算法始終比其它算法所得工人效率好。

圖4 工人效率隨工人數(shù)變化而變化

由于選擇彈性時間的工人效率會得到提高，在相同單位代價、工人數(shù)量、任務數(shù)量以及置信條件下，不同的彈性工人數(shù)也會影響到工人總效率，記錄在工人、任務數(shù)量以及置信水平不變的情況下彈性工人數(shù)量分別為3、4、5、6、7時工人總效率的變化。如圖5所示，隨著彈性工人數(shù)的增加，不同算法中的工人的總效率均增加了。鯨魚優(yōu)化算法中工人總效率接近最高值，此后，工人總效率增長變緩。此外，隨著彈性工人數(shù)量增長，基于鯨魚優(yōu)化算法制定的任務分配算法的工人效率始終高于其它算法。

圖5 工人效率隨彈性工人數(shù)變化而變化

為了討論引入工人彈性時間的重要性，圖6展示了鯨魚優(yōu)化算法的最優(yōu)任務分配結果中各工人效率?？梢钥闯鲇幸话牍と诉_到了最高效率1；圖7展示了工人任務執(zhí)行時間與預計在線時間的對比，可以看出工人2、4、6、9、10選擇了延長時間執(zhí)行額外任務，所以他們達到了最高效率。因此，考慮工人彈性時間能夠提升工人效率。

圖6 工人效率

圖7 工人執(zhí)行任務時間與預計在線時間對比

為了進一步展示彈性時間的效果，將考慮彈性時間與未考慮彈性時間的任務分配結果進行對比。從圖8中可以看出未考慮彈性時間的工人總效率較低，相比來說，考慮彈性時間的工人效率比不考慮彈性時間的工人效率高，其中工人2、4、6、9、10在考慮彈性時間之后均提高了工人效率。圖9展示了工人未考慮彈性時間以及考慮彈性時間之后工人任務執(zhí)行時間與工人預計在線時間的對比?？梢钥闯?，在未考慮彈性時間時，每個工人的任務執(zhí)行時間都不會超過工人預計在線時間，工人2、6、10即使空閑時間很多，也不會再執(zhí)行任務；而在考慮彈性時間之后，一部分工人選擇延長在線時間執(zhí)行額外任務以達到更高的效率。圖10給出了未考慮彈性時間與考慮彈性時間后工人代價對比?？梢钥闯觯紤]彈性時間時工人代價均不會超過未考慮彈性時間時的工人代價，且總代價大幅度降低。因此，考慮工人彈性在線時間不但增加了工人效率，同時也降低了工人總代價，使得資源利用更為合理。

圖8 工人效率對比

圖9 任務執(zhí)行時間與預計在線時間對比

圖10 工人代價對比

4 結束語

任務分配問題是群智感知相關研究中的重點。針對該任務分配問題，本文考慮工人在線時間為彈性在線時間，采用模糊機會約束規(guī)劃方法進行建模。由于該任務分配問題為組合優(yōu)化問題，不存在時間有效的最優(yōu)解，因此，基于鯨魚優(yōu)化算法設計了兩階段的任務分配算法進行求解。仿真結果表明，所設計的任務分配算法相較于其它算法具有更高的工人效率；此外，相較于工人固定在線時間，在進行任務分配時考慮工人彈性在線時間能夠提高工人效率同時降低工人成本。