面向模糊邏輯控制的移動(dòng)群智感知多任務(wù)分配

楊桂松，張楊林，何杏宇

1(上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093) 2(上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計(jì)學(xué)院，上海 200093)

1 引 言

隨著移動(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ù)分配.

2 相關(guān)工作

一些工作研究不同情況下的多任務(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à)值.

3 效用分析

本文設(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ū)域有不同的參與者密度.

3.1 參與者密度設(shè)計(jì)

通常，決策受到多方面不確定性的影響，決策中的信息可能是不完整，不精確，零散，不完全可靠，模糊，自相矛盾或以其他方式缺乏[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è)精確值的平均值來表示的.

3.2 效用設(shè)計(jì)

為了節(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ù)效用.

4 任務(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

5 實(shí)驗(yàn)分析

為了進(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次.

5.1 參與者密度

如第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.

5.2 任務(wù)的數(shù)量

在這一部分中，參與者的數(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ù)的效用越大.

5.3 參與者的數(shù)量

在仿真中，任務(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)速度比早期的快.

5.4 參與者承載的最大工作負(fù)載

在仿真中，任務(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ù)量的增加而增加.

6 總 結(jié)

在本文中，考慮到參與者密度在實(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)化方法.