楊桂松,張楊林,何杏宇
1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院,上海 200093) 2(上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院,上海 200093)
隨著移動(dòng)設(shè)備的傳感,計(jì)算和通信的快速發(fā)展,由大量攜帶有移動(dòng)設(shè)備的參與者組成的移動(dòng)群智感知成為一種新穎的感知范式[1],并且得到極大的關(guān)注.與傳統(tǒng)的固定部署感知模式相比,移動(dòng)群智感知有部署成本低、網(wǎng)絡(luò)維護(hù)更容易、系統(tǒng)更有可擴(kuò)展性等優(yōu)點(diǎn)[2],因此更適合完成大量的感知任務(wù),例如,智能交通[3],醫(yī)療保健應(yīng)用[4],噪聲檢測(cè)[5]等.近年來,也已經(jīng)建立一些移動(dòng)群智感知平臺(tái),如WAZE[6],Millionagents[7],Medusa[8],PRISM[9].
在移動(dòng)群智感知中,參與者攜帶的移動(dòng)設(shè)備被用作基本感知單元.首先,系統(tǒng)平臺(tái)應(yīng)將任務(wù)分配給合適的參與者,然后參與者執(zhí)行任務(wù),并將感知數(shù)據(jù)上傳到系統(tǒng)平臺(tái).最后,系統(tǒng)平臺(tái)分析和處理感知數(shù)據(jù)以完成這些任務(wù).其中,任務(wù)分配是一個(gè)根本而核心的問題.任務(wù)分配的研究經(jīng)歷了幾個(gè)發(fā)展階段.在早期的任務(wù)分配研究中,大多數(shù)研究工作集中在單任務(wù)分配[10-12].隨著越來越多的應(yīng)用利用移動(dòng)群智感知,考慮到有限的資源(即,移動(dòng)設(shè)備的數(shù)量,傳感器的類型和能量等),并且任務(wù)的數(shù)量逐漸增加,因此在有限資源下的多任務(wù)分配成為研究熱點(diǎn)[13-15].另外,在移動(dòng)群智感知中,由于參與者的感知活動(dòng)受到時(shí)間和空間的影響,因此研究多任務(wù)分配的時(shí)空特性[14,16,17]具有重要意義.
在特定的時(shí)空中,參與者密度,即活動(dòng)的參與者數(shù)量占所有參與者的比重,是移動(dòng)群智感知的重要因素,并且對(duì)任務(wù)完成的質(zhì)量和效率具有重要影響.例如,一些工作研究了參與者密度對(duì)任務(wù)分配的影響[15]和位置隱私保護(hù)[18,19].目前,獲取參與者密度的一種直接方法是要求他們不停地報(bào)告實(shí)時(shí)位置,以便系統(tǒng)平臺(tái)可以準(zhǔn)確地查看不同區(qū)域的密度.但是,這種方法通常是不切實(shí)際的,因?yàn)樗粌H昂貴,而且還會(huì)在位置隱私方面帶來潛在的風(fēng)險(xiǎn).另一種方法是與城市管理部門合作,以便系統(tǒng)平臺(tái)可以獲取參與者出行的數(shù)據(jù).但是這種方法的靈活性較差,通常情況下,這些部門不愿意合作.因此,對(duì)于移動(dòng)群智感知的應(yīng)用和系統(tǒng),需要另一種密度估計(jì)方法.在本文中,我們旨在解決兩個(gè)挑戰(zhàn).1)如何準(zhǔn)確,靈活地估算參與者密度.2)如何在參與者密度的限制條件下實(shí)現(xiàn)任務(wù)分配策略.
為了解決第一個(gè)挑戰(zhàn),我們提出了用于參與者密度分析的模糊邏輯控制方法.考慮到時(shí)空下的參與者密度是非線性且復(fù)雜的,因此難以在高參與者密度和低參與者密度之間校準(zhǔn)清晰的邊界.為了解決這個(gè)問題,在本文中,采用模糊邏輯控制方法來獲取不同時(shí)間和空間下的參與者密度.作為基于規(guī)則的方法,模糊邏輯控制方法可以模擬人的思維并將專家知識(shí)轉(zhuǎn)換為啟發(fā)式控制算法[20].模糊邏輯控制的最重要特征是反映人們的經(jīng)驗(yàn)和以自然語(yǔ)言表達(dá)的推理規(guī)則.在本文中,根據(jù)參與者的出行時(shí)間和空間來反映經(jīng)驗(yàn)和規(guī)則,從而可以獲得不同時(shí)空下的參與者密度.
另外,為了應(yīng)對(duì)第二個(gè)挑戰(zhàn),我們提出了任務(wù)分配策略.首先,基本思想是根據(jù)參與者的密度確定任務(wù)所需的有效樣本數(shù)量.例如,在低參與者密度的特定時(shí)空中,由于參與者數(shù)量不足,任務(wù)分配的效率和感知質(zhì)量將降低.在這種情況下,傳統(tǒng)的任務(wù)分配策略可能會(huì)導(dǎo)致較長(zhǎng)的完成周期,甚至某些任務(wù)無法在有效時(shí)間內(nèi)完成.因此,對(duì)于每個(gè)任務(wù),根據(jù)參與者密度,如何確定其有效樣本數(shù)量(合理范圍內(nèi)的較低值)以確保每個(gè)任務(wù)在有效時(shí)間內(nèi)完成很重要.相反,在參與者密度較高的特定時(shí)空中,由于參與者數(shù)量充足,因此對(duì)于每個(gè)任務(wù),確定其有效樣本數(shù)量(合理范圍內(nèi)的較高值)也很重要,以便系統(tǒng)平臺(tái)可以在有效時(shí)間內(nèi)收集足夠的高質(zhì)量樣本.另外,本文還考慮任務(wù)的屬性和參與者方的因素來計(jì)算所有任務(wù)的效用.進(jìn)一步地,為了最大化所有任務(wù)的效用,在參與者承載的最大工作負(fù)載和任務(wù)所需要的樣本數(shù)量的限制條件下,本文提出了一種全局貪婪算法將任務(wù)分配給參與者.
總之,本文通過基于模糊邏輯的參與者密度分析,研究了多任務(wù)分配問題.本文的主要貢獻(xiàn)如下:
1)由于不同時(shí)空下的參與者密度是非線性的、復(fù)雜的,因此采用模糊邏輯控制方法對(duì)參與者密度進(jìn)行分析.
2)為了最大化所有任務(wù)的效用,提出了一種全局貪婪算法進(jìn)行任務(wù)分配.
一些工作研究不同情況下的多任務(wù)分配問題.Guo等人在[13]中考慮了時(shí)間敏感任務(wù)和延遲容忍任務(wù)的參與者選擇問題.Song和Hu研究了如何在任務(wù)分配質(zhì)量受限的情況下將多個(gè)任務(wù)分配給參與者[21,22].與這些研究工作不同,本文考慮不同時(shí)空下參與者密度的問題以進(jìn)行任務(wù)分配.
在移動(dòng)群智感知中,時(shí)空模型是一個(gè)熱門的研究問題,近年來引起了很多關(guān)注.與典型的眾包不同,基于時(shí)空模型的任務(wù)分配需要考慮任務(wù)和參與者的時(shí)空特征,例如時(shí)間,空間,時(shí)空覆蓋等.例如,在文獻(xiàn)[10]中,一種名為CrowdRecruiter的新型參與者選擇框架,以通過選擇少量參與者并滿足時(shí)空覆蓋概率約束來最小化獎(jiǎng)勵(lì)支出.Xiong等人定義了一種新穎的時(shí)空覆蓋率度量,即k深度覆蓋率,并在不同激勵(lì)和k深度覆蓋的約束下優(yōu)化任務(wù)分配[16].就時(shí)間和地點(diǎn)而言,Cheng等人考慮每個(gè)空間任務(wù)都受時(shí)間限制,并提出了一種最優(yōu)的參與者和任務(wù)分配策略,該策略可以在預(yù)算約束下最大化參與者的利益[23].
上述工作僅考慮了任務(wù)和參與者的某些時(shí)空特性,并且缺乏對(duì)參與者的時(shí)空密度進(jìn)行全面分析和建模的能力.因此,就參與者密度對(duì)任務(wù)分配的影響而言,本文充分考慮了參與者密度,并采用模糊邏輯控制方法進(jìn)行了分析.
作為近似推理模式的邏輯[24],模糊邏輯已在導(dǎo)航系統(tǒng),醫(yī)療,食品等許多領(lǐng)域中得到應(yīng)用.在文獻(xiàn)[25]中,開發(fā)了一種用于移動(dòng)機(jī)器人的導(dǎo)航系統(tǒng),其中,將移動(dòng)機(jī)器人的傳感數(shù)據(jù)用作模糊邏輯的輸入,以獲得不同的機(jī)器人行為.在文獻(xiàn)[26]中,提出了一種基于模糊邏輯的專家系統(tǒng),該系統(tǒng)可以為患者診斷可能的心臟病.文獻(xiàn)[27]等人設(shè)計(jì)了基于模糊邏輯控制的面團(tuán)發(fā)酵系統(tǒng),該系統(tǒng)不需要數(shù)學(xué)模型,并且具有更好的抗干擾性能.
Liu等人考慮了參與者密度對(duì)任務(wù)分配的影響,他們提出了一個(gè)名為TaskMe的參與者選擇框架,用于兩種典型的多任務(wù)分配情況,即參與者少,任務(wù)多和參與者多,任務(wù)少,并根據(jù)這兩種情況提出了不同的優(yōu)化目標(biāo)和算法[15].據(jù)我們所知,目前還沒有其他工作將模糊邏輯控制應(yīng)用于移動(dòng)群智感知中的任務(wù)分配領(lǐng)域.因此,基于該技術(shù),如何獲得不同時(shí)空的參與者密度具有重要的研究?jī)r(jià)值.
本文設(shè)計(jì)的系統(tǒng)模型考慮了一個(gè)實(shí)際場(chǎng)景,即所有任務(wù)和參與者都是雙方選擇.具體過程如圖1所示.
圖1 系統(tǒng)模型Fig.1 System model
首先,任務(wù)請(qǐng)求者將任務(wù)提交給系統(tǒng)平臺(tái),系統(tǒng)平臺(tái)基于時(shí)空下的參與者密度,可以生成每個(gè)任務(wù)所需的有效樣本數(shù)的樣本表.然后,系統(tǒng)平臺(tái)將任務(wù)信息(例如任務(wù)的位置,任務(wù)的感知內(nèi)容以及任務(wù)的感知時(shí)間)提供給所有參與者.之后,每個(gè)參與者可以根據(jù)任務(wù)信息和自己的意愿選擇任務(wù),然后向系統(tǒng)平臺(tái)提交意愿表.另外,系統(tǒng)平臺(tái)通過考慮任務(wù)的感知質(zhì)量,感知時(shí)間,以及參與者的感知質(zhì)量,參與者的意愿性,生成所有參與者去感知每個(gè)任務(wù)的系統(tǒng)效用表.進(jìn)一步地,系統(tǒng)平臺(tái)基于樣本表和系統(tǒng)效用表,通過混合貪婪算法將這些任務(wù)分配給參與者.最后,當(dāng)參與者完成感知任務(wù)之后,參與者應(yīng)將感知數(shù)據(jù)上傳到系統(tǒng)平臺(tái),然后系統(tǒng)平臺(tái)處理該數(shù)據(jù)并將結(jié)果反饋給任務(wù)請(qǐng)求者.
為了更清楚地表示上述過程,系統(tǒng)中使用的詳細(xì)參數(shù)描述如下.
在這項(xiàng)工作中,對(duì)于某一個(gè)感知區(qū)域的時(shí)空劃分,系統(tǒng)平臺(tái)將一天劃分為等長(zhǎng)的z個(gè)時(shí)間周期TZ={T1,…,Tg,…,Tz},并將感知區(qū)域按基站劃分為l個(gè)獨(dú)立的子區(qū)域SL= {S1,…,Sk,…,Sl}.在特定的時(shí)間周期和子區(qū)域中,n個(gè)任務(wù)的集合表示為tN={t1,…,ti,…,tn},m個(gè)參與者的集合表示為pM={p1,…,pj,…,pm}.每個(gè)參與者對(duì)每個(gè)任務(wù)的意愿性用Wi,j表示,其中Wi,j= 1表示參與者pj愿意感知任務(wù)ti,否則Wi,j= 0.另外,任務(wù)ti和參與者pj的分配狀態(tài)用表示,表示任務(wù)ti已分配給參與者pj,否則.應(yīng)注意的是,意愿性Wi,j和分配狀態(tài)φi,j均為二進(jìn)制值.
在本文中,考慮到特定感知區(qū)域的時(shí)空劃分,系統(tǒng)平臺(tái)將一天劃分為24個(gè)時(shí)間周期T={T1,T2,…,T24},并將感知區(qū)域按基站劃分為10個(gè)獨(dú)立的子區(qū)域S={S1,S2,…,S10},不同的子區(qū)域有不同的參與者密度.
通常,決策受到多方面不確定性的影響,決策中的信息可能是不完整,不精確,零散,不完全可靠,模糊,自相矛盾或以其他方式缺乏[27].由于模糊邏輯控制可以用計(jì)算機(jī)來執(zhí)行人們的控制策略,并且避免在實(shí)際應(yīng)用中建立復(fù)雜的模型,因此很多不確定性可以使用模糊邏輯來處理.由于不同時(shí)間周期和子區(qū)域中的參與者密度是非線性且復(fù)雜的,因此模糊邏輯控制方法對(duì)于參與者密度分析變得非常有益.
圖2 隸屬度函數(shù)Fig.2 Membership functions
傳統(tǒng)的模糊邏輯控制系統(tǒng)以三個(gè)步驟運(yùn)行,如圖2所示.首先,通過隸屬函數(shù)將精確的輸入轉(zhuǎn)換為輸入變量的模糊集,即模糊化.其次,根據(jù)輸出變量的隸屬函數(shù)和模糊邏輯規(guī)則,系統(tǒng)推導(dǎo)輸出模糊集,即模糊推理.最后,對(duì)輸出模糊集進(jìn)行去模糊化,將模糊值轉(zhuǎn)換為系統(tǒng)輸出的精確值,即去模糊處理.在運(yùn)行模糊邏輯控制系統(tǒng)時(shí),應(yīng)先確定輸入和輸出變量.參與者密度受參與者出行的時(shí)間周期和子區(qū)域的影響.例如,在低峰期和稀疏子區(qū)域中,參與者較少,這導(dǎo)致參與者密度較低.相反,在高峰期和密集子區(qū)域中有較高的參與者密度.因此,在本文中,將參與者的出行時(shí)間周期Tg和參與者的出行子區(qū)域Sk作為輸入變量,參與者密度P作為輸出變量.
在這項(xiàng)工作中,詳細(xì)的模糊邏輯控制系統(tǒng)設(shè)計(jì)如下.
模糊集和隸屬度函數(shù).使用MATLAB對(duì)模糊邏輯控制系統(tǒng)進(jìn)行編程.在這項(xiàng)工作中,根據(jù)參與者的出行時(shí)間周期和子區(qū)域的經(jīng)驗(yàn),通過建立隸屬度函數(shù)來描述輸入和輸出變量的模糊集.
模糊邏輯規(guī)則.模糊邏輯控制系統(tǒng)主要基于規(guī)則的方法來運(yùn)行,該方法使用IF(條件)和THEN(結(jié)論)的可變公式化來定義規(guī)則.因此,在設(shè)置輸入和輸出變量之后,下一步是將它們與IF-THEN規(guī)則進(jìn)行匹配,即模糊推理.在這項(xiàng)工作中,使用Mamdani的模糊推理方法[26],15條規(guī)則均如下所示.另外,我們提供一個(gè)示例來說明如何評(píng)估規(guī)則.
1. IF(Tg=ELP)and(Sk=SP),THEN(P=L).
2. IF(Tg=ELP)and(Sk=BS),THEN(P=RL).
3. IF(Tg=ELP)and(Sk=DE),THEN(P=NO).
4. IF(Tg=EP)and(Sk=SP),THEN(P=NO).
5. IF(Tg=EP)and(Sk=BS),THEN(P=RH).
6. IF(Tg=EP)and(Sk=DE),THEN(P=H).
7. IF(Tg=BT)and(Sk=SP),THEN(P=RL).
8. IF(Tg=BT)and(Sk=BS),THEN(P=NO).
頂層由Sphere包圍盒作為外部處理,內(nèi)部加以O(shè)BB包圍盒結(jié)合設(shè)計(jì)。這種設(shè)計(jì)方法主要是考慮到Sphere包圍盒的構(gòu)造簡(jiǎn)單性以及檢測(cè)易操作兩方面,如果外圍的Sphere包圍盒已經(jīng)發(fā)生相交或者碰撞情況,則需進(jìn)一步地檢測(cè),內(nèi)部的OBB包圍盒開始運(yùn)作;如果外部Sphere包圍盒還未碰撞,不進(jìn)行下一步檢測(cè)操作。而以O(shè)BB包圍盒為內(nèi)部的根節(jié)點(diǎn),其中心即為Sphere包圍盒的球心,進(jìn)一步方便構(gòu)造,而且Sphere包圍盒結(jié)構(gòu)方面的優(yōu)勢(shì),無論被測(cè)物體進(jìn)行平移還是旋轉(zhuǎn)操作,其形狀不發(fā)生改變,有利于更新。
9. IF(Tg=BT)and(Sk=DE),THEN(P=RH).
10. IF(Tg=LP)and(Sk=SP),THEN(P=NO).
11. IF(Tg=LP)and(Sk=BS),THEN(P=RH).
12. IF(Tg=LP)and(Sk=DE),THEN(P=H).
13. IF(Tg=LLP)and(Sk=SP),THEN(P=L).
14. IF(Tg=LLP)and(Sk=BS),THEN(P=RL).
15. IF(Tg=LLP)and(Sk=DE),THEN(P=NO).
如果參與者的出行時(shí)間周期處于早期高峰,并且出行的子區(qū)域很密集,那么參與者的密度就高.可以給出表示形式,IF(Tg=EP)and(Sk=DE),THEN(P=H).
模糊化.模糊化通過使用重心法(COG)將模糊值轉(zhuǎn)換為精確值.模糊推理的最終輸出值是根據(jù)隸屬度函數(shù)曲線的重心和交叉坐標(biāo)區(qū)域確定的[20].因此,參與者密度的精確輸出值表示為.
(1)
其中Pi和Pj表示積分的第i界和第j界,而μ(P)表示隸屬度函數(shù)P的值.
另外,在時(shí)間周期Tg和子區(qū)域Sk中,參與者密度的精確值是通過計(jì)算多個(gè)精確值的平均值來表示的.
為了節(jié)省系統(tǒng)資源以及確保任務(wù)的感知質(zhì)量,系統(tǒng)平臺(tái)根據(jù)任務(wù)類型預(yù)先設(shè)置樣本量的區(qū)間[vil,vir].實(shí)際上,一方面,如果任務(wù)ti的樣本數(shù)量超過vir,則將浪費(fèi)系統(tǒng)資源.另一方面,如果任務(wù)ti的樣本數(shù)量少于vil,則無法確保ti的質(zhì)量.另外,為了確保樣本質(zhì)量,假定每個(gè)參與者為其分配的任務(wù)提供一個(gè)有效樣本.
在特定的時(shí)間周期Tg和子區(qū)域Sk中,ti所需的有效樣本數(shù)量與任務(wù)ti的預(yù)區(qū)間以及參與者密度有關(guān).任務(wù)ti所需的有效樣本量和任務(wù)ti的感知質(zhì)量定義如下.
定義1.假設(shè)在時(shí)間周期Tg和子區(qū)域Sk中,任務(wù)ti需要的有效樣本數(shù)量定義如下:
(2)
其中,POk,g表示在時(shí)間周期Tg和子區(qū)域Sk中參與者密度的精確值.
定義2.設(shè)在時(shí)間周期Tg和子區(qū)域Sk中,任務(wù)ti的感知質(zhì)量計(jì)算如下:
(3)
基于以上定義,所有任務(wù)的效用具體計(jì)算如下.
在特定的時(shí)間周期和子區(qū)域中,參與者感知任務(wù)的效用受任務(wù)的屬性和參與者方因素的影響.一方面,任務(wù)的屬性包括感知時(shí)間,感知質(zhì)量,其中感知時(shí)間與任務(wù)的類型和復(fù)雜性有關(guān).另一方面,參與者方的因素包括參與者的感知質(zhì)量和意愿性,其中參與者的感知質(zhì)量受其移動(dòng)設(shè)備的性能影響.因此,對(duì)于系統(tǒng)平臺(tái),在時(shí)間周期Tg和子區(qū)域Sk中,參與者pj感知任務(wù)ti的效用可以計(jì)算為:
(4)
另外,在時(shí)間周期Tg和子區(qū)域Sk中,m個(gè)參與者感知任務(wù)ti的效用表示為:
(5)
因此,在時(shí)間周期Tg和子區(qū)域Sk中,所有n個(gè)任務(wù)的效用計(jì)算為:
(6)
對(duì)于系統(tǒng)平臺(tái),在時(shí)間周期Tg和子區(qū)域Sk中,目標(biāo)是最大化所有n個(gè)任務(wù)的效用.考慮到移動(dòng)設(shè)備的性能差異,一方面,每個(gè)參與者具有承載的最大工作負(fù)載fj,即可以完成的最大任務(wù)數(shù).例如,當(dāng)fj=2時(shí),它表示參與者pj在一次任務(wù)分配中最多可以完成2個(gè)任務(wù).另一方面,任務(wù)ti所需的有效樣本數(shù)量應(yīng)由不同的參與者提供.因此,以下目標(biāo)函數(shù)和約束可以表示為:
(7)
約束條件:
(8)
(9)
此外,在上述問題中,我們還考慮了在時(shí)間周期和子區(qū)域中分配任務(wù)以實(shí)現(xiàn)最大化任務(wù)效用.
在時(shí)間周期Tg和子區(qū)域Sk中,對(duì)于所有任務(wù),將每個(gè)參與者去感知每個(gè)任務(wù)的效用建模為系統(tǒng)效用表,用公式(10)表示.其中,ti∈tN以及pj∈pM.
(10)
在這項(xiàng)工作中,使用GGA將任務(wù)分配給參與者,同時(shí)最大化所有任務(wù)的效用.此外,為了確保樣本質(zhì)量,參與者為每個(gè)任務(wù)只提供一個(gè)有效樣本.詳細(xì)的算法過程如下描述.
算法1說明GGA的執(zhí)行過程.
算法1.全局貪婪算法(GGA)進(jìn)行任務(wù)分配過程
2.輸出: M
3.Repeat
4.forΩ≠?do
6.ifpj_r≠0 andti_r≠0then
7. 任務(wù)ti分配給參與者pj
8.pj_r=pj_r-1,ti_r=ti_r-1
9.elseifti_r=0then
10. Ω=Ω-ti
11.else
12. continue
13.endif
14.endfor
15.UntilΩ≠? or ?pj_r≠0
16.ReturnM
圖3展示了任務(wù)分配實(shí)例.在這個(gè)例子中,我們假設(shè)任務(wù)集tN={t1,t2,t3},參與者集pM={p1,p2,p3,p4}.在任務(wù)分配之前,我們使用二分圖來表示參與者去感知任務(wù)的效用,其中每條連接線代表的是參與者pj愿意去感知任務(wù)ti的效用.圖3(a)展示了參與者感知任務(wù)的效用,參與者可用的工作負(fù)載以及任務(wù)需要的有效樣本數(shù)的初始設(shè)置值.算法搜索系統(tǒng)效用表,找到滿足約束條件的最大效用42,如圖3(b)所示,用黑色虛線橢圓框標(biāo)記42,并將t1分配給p1,同時(shí)更新t1_r=2以及p1_r=1.目前,除42外,最大的效用是38,如圖3(c)所示,用黑色虛線橢圓框標(biāo)記38并將t2分配給p4,同時(shí)更新t2_r=0以及p4_r=1.該算法繼續(xù)搜索系統(tǒng)效用表,找到除已經(jīng)標(biāo)記過的最大效用26,此時(shí)t2_r=0,表明任務(wù)t2已經(jīng)被分配完,則任務(wù)t2不會(huì)分配給參與者p3.以相同的方式進(jìn)行貪婪選擇過程,分別如圖3(d),圖3(e)以及圖3(f)所示,t1,t3,t1依次分配給p2,p4,p3.
圖3 任務(wù)分配實(shí)例Fig.3 Task allocation instance
為了進(jìn)一步說明所提出的模型和算法的優(yōu)勢(shì),我們?cè)贛ATLAB和Python中對(duì)任務(wù)分配的性能進(jìn)行了實(shí)驗(yàn).仿真實(shí)驗(yàn)的主要參數(shù)在表1中給出.
表1 仿真參數(shù)Table 1 Simulation parameters
為了與提出的GGA進(jìn)行比較,將其他兩種算法(隨機(jī)分配算法(RAA)和局部貪婪算法(LGA))作為基線,并針對(duì)在不同時(shí)間周期和子區(qū)域上的情況進(jìn)行比較.
隨機(jī)分配算法(RAA)-在RAA中,所有的任務(wù)都是基于隨機(jī)性分配給參與者,同時(shí)要滿足兩個(gè)約束條件,即每個(gè)參與者承載的最大工作負(fù)載以及任務(wù)所需的有效樣本數(shù)量由不同的參與者提供.
局部貪婪算法(LGA)-在LGA中,基于GGA的約束條件,所有任務(wù)將依次分配給參與者,同時(shí)通過最大化每個(gè)任務(wù)的效用來最大化所有任務(wù)的效用.
雖然本文提出的GGA在時(shí)間復(fù)雜度上面高于LGA以及RAA,但是在獲得最大化所有任務(wù)的效用方面遠(yuǎn)遠(yuǎn)優(yōu)于其他兩個(gè).
由于參與者密度受參與者出行的時(shí)間周期和子區(qū)域的影響,我們研究了所有任務(wù)的效用隨不同時(shí)間周期和子區(qū)域下的任務(wù)數(shù)量、參與者數(shù)量以及參與者承載的最大工作負(fù)載的變化而變化.以上三種算法產(chǎn)生的最終仿真結(jié)果平均計(jì)算50次.
如第3.1節(jié)所述,參與者密度至關(guān)重要,因?yàn)樗鼪Q定了系統(tǒng)是否可以成功分配任務(wù).
圖4顯示了在不同時(shí)間周期和子區(qū)域下的參與者密度變化.在圖6中,對(duì)于10個(gè)子區(qū)域S1-S10,參與者的出行時(shí)間周期設(shè)置為Tg=T20,Tg=T15,Tg=T5,即{19:00-20:00,14:00-15:00,4:00-5:00}分別隸屬于模糊集LP,EQ和ELP.根據(jù)第3節(jié)中的模糊邏輯控制系統(tǒng)的設(shè)計(jì),我們可以得到如圖4所示的參與者密度變化,其中在時(shí)間周期T20,T15,T5時(shí)的參與者密度分別約為69%,50%和32%.顯然,在時(shí)間周期T20的參與者密度高于在時(shí)間周期T15和T5的參與者密度,其原因是,在時(shí)間周期T20,有更多的參與者.總的來說,這種現(xiàn)象表明數(shù)值結(jié)果在實(shí)際應(yīng)用中是合理的,符合模糊邏輯規(guī)則的設(shè)計(jì)精度.
圖4 參與者密度Fig.4 Participant density
根據(jù)理論分析,所有任務(wù)的效用與不同時(shí)間周期和子區(qū)域中任務(wù)的數(shù)量、參與者的數(shù)量以及參與者承載的最大工作負(fù)載有關(guān).因此,本文分別通過使用GGA,LGA和RAA計(jì)算在不同時(shí)間周期和子區(qū)域下,不同任務(wù)數(shù)量、參與者數(shù)量以及參與者承載的最大工作負(fù)載的所有任務(wù)的效用.在仿真中,不同時(shí)間周期和子區(qū)域被設(shè)計(jì)為(a)Sk=S2,Tg=T5;(b)Sk=S8,Tg=T20.
在這一部分中,參與者的數(shù)量固定為50,參與者承載的最大工作負(fù)載固定為2.
如圖5所示,實(shí)驗(yàn)結(jié)果表明,隨著任務(wù)數(shù)量從5增加到25,在三種算法中,所有任務(wù)的效用均增加.另外,當(dāng)最大化所有任務(wù)的效用時(shí),GGA的性能要優(yōu)于LGA和RAA.此外,當(dāng)任務(wù)數(shù)量增加到一定值時(shí),GGA,LGA和RAA生成的所有任務(wù)的效用之間的差異變得越來越明顯.原因是,如第4節(jié)中所述,在每次任務(wù)分配時(shí),GGA全局地從系統(tǒng)效用表里搜索最大效用以最大化所有任務(wù)的效用,而LGA是依次分配任務(wù)并且每次都是局部搜索.進(jìn)一步地,隨著任務(wù)數(shù)量的增加,需要將更多的任務(wù)分配給參與者,因此,GGA和LGA之間的性能差異變得更加明顯.在RAA中,所有任務(wù)都是基于隨機(jī)性將任務(wù)分配給參與者,因此,RAA的性能比GGA和LGA差.
值得注意的是,當(dāng)任務(wù)數(shù)量增加到一定值時(shí),所有任務(wù)的效用增加地速度變慢.這是由于,在早期過程中,參與者的數(shù)量大于任務(wù)需要的有效樣本數(shù)量.進(jìn)一步地,根據(jù)公式(6),任務(wù)數(shù)量的增加將導(dǎo)致所有任務(wù)效用的增加.但是,隨著任務(wù)數(shù)量的增加,由于可用的參與者的工作負(fù)載越來越少,算法會(huì)將過多的任務(wù)分配給有限的參與者,這將導(dǎo)致所有任務(wù)的效用增長(zhǎng)速度比早期的慢.
圖5 不同時(shí)空下任務(wù)數(shù)量對(duì)所有任務(wù)效用的影響Fig.5 Utility of all tasks for the quantity of task in different time and space
此外,如圖5(a)和圖5(b)所示,在時(shí)間周期T20和子區(qū)域S8中所有任務(wù)的效用比在時(shí)間周期T5和子區(qū)域S2中所有任務(wù)的效用大.這是由于,根據(jù)第3.1節(jié)中說明的模糊邏輯規(guī)則,時(shí)間周期T20和子區(qū)域S8分別隸屬于模糊集LP和模糊集DE,因此參與者密度P隸屬于模糊集H.時(shí)間周期T5和子區(qū)域S2分別隸屬于模糊集ELP和模糊集SP,因此參與者密度P隸屬于模糊集L.因此,在時(shí)間周期T20和子區(qū)域S8,參與者密度是最大的.進(jìn)一步地,根據(jù)公式(2),任務(wù)需要的有效樣本數(shù)量越大,所以需要更多地參與者去提供樣本.再根據(jù)公式(5),所有參與者去感知每個(gè)任務(wù)的效用越大,所有任務(wù)的效用越大.
在仿真中,任務(wù)的數(shù)量固定為20,參與者承載的最大工作負(fù)載固定為2.
如圖6所示,隨著參與者數(shù)量從10增加到50,在GGA,LGA以及RAA中,所有任務(wù)的效用都增加,并且GGA的性能是遠(yuǎn)優(yōu)于LGA和RAA.原因與第5.2節(jié)一樣.
圖6 參與者數(shù)量對(duì)所有任務(wù)效用的影響Fig.6 Utility of all tasks for the quantity of participant
此外,從圖6還可以看出,隨著參與者數(shù)量的增多,GGA的優(yōu)勢(shì)越來越好.這是由于,在早期分配過程中,任務(wù)的數(shù)量是大于參與者的數(shù)量,即任務(wù)需要的有效樣本數(shù)是多的,因此在早期階段,所有的任務(wù)的效用增長(zhǎng)速度較慢.但是,隨著參與者數(shù)量的增多,參與者可用的工作負(fù)載將增加,算法在資源充足的條件下,將一定的任務(wù)分配給過多的參與者,因此增長(zhǎng)速度比早期的快.
在仿真中,任務(wù)數(shù)量固定為10,參與者數(shù)量固定為20.
如圖7所示,隨著參與者承載的最大工作負(fù)載從1增加到4時(shí),在三種算法中,所有任務(wù)的效用都是處于增加趨勢(shì),另外,可以看出GGA在最大化所有任務(wù)的效用性能上要優(yōu)于LGA和RAA.原因是,GGA是通過全局的搜索最大的效用以實(shí)現(xiàn)所有任務(wù)的效用最大化,而LGA是局部的實(shí)現(xiàn)任務(wù)的效用最大化,RAA則是基于隨機(jī)性進(jìn)行分配任務(wù)以達(dá)到效用最大化.
圖7 參與者承載的最大工作負(fù)載對(duì)所有任務(wù)效用的影響Fig.7 Utility of all tasks for participant maximum workload
由圖7所示,隨著參與者承載的最大工作負(fù)載越來越多時(shí),在GGA中,所有任務(wù)的效用越來越大.這是因?yàn)?,任?wù)的數(shù)量一定時(shí),表明任務(wù)需要的有效樣本數(shù)量一定.在早期階段,由于參與者承載的工作負(fù)載少,因此可以被分配的任務(wù)比較少.進(jìn)一步地,算法在有限的可用的工作負(fù)載條件下,將任務(wù)分配給一定的參與者,導(dǎo)致所有任務(wù)的效用比較低.但是隨著參與者承載的工作負(fù)載越來越大時(shí),表明參與者可以完成的任務(wù)的數(shù)量也越來越多,根據(jù)公式(5),所有任務(wù)的效用隨著可以任務(wù)數(shù)量的增加而增加.
在本文中,考慮到參與者密度在實(shí)際應(yīng)用中的影響,我們的工作集中在通過基于模糊邏輯的時(shí)空參與者密度分析中的任務(wù)分配問題.為了解決該問題,采用了模糊邏輯控制方法來獲得不同時(shí)間周期和子區(qū)域中的參與者密度.然后,基于參與者的密度和所有任務(wù)的效用,提出了一種GGA,以確保最大化所有任務(wù)的效用.仿真結(jié)果表明,該算法是有效的,并且在最大化效用方面表現(xiàn)良好.至于將來的工作,應(yīng)更多考慮任務(wù)的復(fù)雜性、緊急性以及參與者的專業(yè)知識(shí)、時(shí)間可用性等屬性對(duì)多任務(wù)分配的影響.同時(shí),還將探索更多的優(yōu)化方法.