趙焜松,余敦輝,2,張萬山,2
(1.湖北大學(xué) 計(jì)算機(jī)與信息工程學(xué)院,武漢 430062; 2.湖北省教育信息化工程技術(shù)中心,武漢 430062)(*通信作者電子郵箱yumhy@163.com)
隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展,眾包(crowdsourcing)[1]受到了更多工業(yè)和學(xué)術(shù)界人士的極大關(guān)注。眾包平臺,尤其是軟件眾包(software crowdsourcing)平臺,成為當(dāng)前軟件開發(fā)的流行方式之一。軟件眾包的相關(guān)研究已成為當(dāng)前的研究熱點(diǎn)之一,眾多研究人員就軟件眾包任務(wù)設(shè)計(jì)、任務(wù)標(biāo)價(jià)、欺詐者分析、任務(wù)分配、眾包工人選擇等問題展開了大量的研究。
文獻(xiàn)[2-3]中概括了任務(wù)分配中相關(guān)研究,為以后的研究提供了參考。文獻(xiàn)[4]中提出了質(zhì)量控制策略和眾包結(jié)果質(zhì)量評估方法,有效地控制了任務(wù)完成質(zhì)量;但對任務(wù)復(fù)雜度和效益等考慮不足。文獻(xiàn)[5]中對軟件任務(wù)參與度的影響因素進(jìn)行了分析,但忽略了發(fā)布者對任務(wù)的影響。文獻(xiàn)[6-7]中對眾包質(zhì)量進(jìn)行評估,但欠缺對任務(wù)發(fā)布者的考慮。文獻(xiàn)[8]中提出了一種基于用戶信譽(yù)值的激勵(lì)機(jī)制,并通過仿真實(shí)驗(yàn)驗(yàn)證了激勵(lì)機(jī)制的有效性,但涉及實(shí)際用戶參與度對眾包質(zhì)量的影響。文獻(xiàn)[9]中針對眾包系統(tǒng)中的激勵(lì)和信譽(yù)機(jī)制進(jìn)行研究,設(shè)計(jì)了激勵(lì)機(jī)制和信譽(yù)機(jī)制來確保用戶盡最大努力高質(zhì)量地完成任務(wù),但實(shí)際上發(fā)布者、眾包工作者和眾包任務(wù)的特征均會對任務(wù)發(fā)布之后的結(jié)果產(chǎn)生一定影響。文獻(xiàn)[10]中提出了基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機(jī)制,通過仿真實(shí)驗(yàn)證明了所設(shè)計(jì)任務(wù)分配機(jī)制的高效性;但是活躍度也會對用戶有實(shí)際影響。文獻(xiàn)[11]中提出基于活躍度的眾包工作者信譽(yù)模型,綜合考慮了眾包活躍度與信譽(yù)值;但并未考慮眾包任務(wù)本身的特性。文獻(xiàn)[12]中針對任務(wù)本身的特性,分析了眾包任務(wù)設(shè)計(jì)對眾包參與者行為的影響;但忽略了任務(wù)發(fā)布者所產(chǎn)生的影響。然而上述研究并未將任務(wù)發(fā)布者與任務(wù)綜合考慮,且都建立在眾包任務(wù)被分配的基礎(chǔ)上。
對于軟件眾包平臺而言,不同的發(fā)布者在平臺發(fā)布軟件眾包任務(wù)的踴躍程度不一樣,歷史發(fā)布任務(wù)的總金額不同,因此,不同任務(wù)發(fā)布者對于平臺的重要性是不同的;同時(shí),某個(gè)被發(fā)布的軟件眾包任務(wù)的效益權(quán)重和緊迫程度也存在差異。所以,相對于平臺而言,對于不同發(fā)布者發(fā)布的任務(wù),如何進(jìn)行優(yōu)先級排序,從而提高平臺收益,是其關(guān)注的重點(diǎn)。
本文工作主要研究如何根據(jù)發(fā)布者和任務(wù)的特征,衡量任務(wù)發(fā)布的優(yōu)先級。為了解決上述問題,本文假設(shè)某時(shí)間段內(nèi)有平臺收到若干軟件眾包任務(wù)申請,以優(yōu)化任務(wù)發(fā)布次序?yàn)槟繕?biāo),提出了一種基于發(fā)布者活躍度與任務(wù)權(quán)重的軟件眾包任務(wù)發(fā)布優(yōu)先級(Task Release Priority, TRP)計(jì)算算法:首先,基于任務(wù)發(fā)布者的活躍度及其任務(wù)累積成交額,利用半正弦曲線的時(shí)間權(quán)重函數(shù)度量任務(wù)發(fā)布者權(quán)重;然后,對任務(wù)本身的特性進(jìn)行分析,以模塊復(fù)雜度、設(shè)計(jì)復(fù)雜度和數(shù)據(jù)復(fù)雜度三個(gè)方面度量任務(wù)復(fù)雜度,衡量任務(wù)效益和任務(wù)緊急程度,計(jì)算得到任務(wù)權(quán)重;最后,綜合考慮發(fā)布者權(quán)重與任務(wù)權(quán)重計(jì)算得到任務(wù)優(yōu)先數(shù)。使用該模型可以使平臺以最優(yōu)的方式確定任務(wù)分配優(yōu)先級,以便合理安排將要發(fā)布的任務(wù),最終提高平臺收益。
軟件眾包任務(wù)發(fā)布者本身的屬性會影響平臺收益。為了反映在某一周期內(nèi)任務(wù)發(fā)布者對平臺的重要程度,本文采用了一種半正弦的時(shí)間權(quán)重函數(shù)作為擬合曲線,通過給不同的任務(wù)發(fā)布者屬性賦予權(quán)值來反映其所占比重。
本文約定半正弦曲線函數(shù)的時(shí)間權(quán)重函數(shù)為:
weight(t)=[sin (πt/T)+1]/2
(1)
如圖1所示,t是距離周期起始時(shí)刻的時(shí)間,t越小說明距離周期起始時(shí)刻越近,即距離當(dāng)前時(shí)刻越遠(yuǎn),平臺無需對其過分關(guān)注,因此所占權(quán)重趨向于0;t越大則說明距離當(dāng)前時(shí)刻越近,該發(fā)布者對平臺的重要程度越高,因此,平臺加大其權(quán)重。
式(1)中T表示一個(gè)具有調(diào)節(jié)作用的函數(shù)周期,不同的t會產(chǎn)生不同權(quán)重值結(jié)果,t的取值范圍為[0,T/2],weight(t)的取值范圍在[0,1],適用于反映任務(wù)發(fā)布者對平臺的重要程度。
圖1 半正弦曲線
軟件眾包任務(wù)發(fā)布優(yōu)先級模型設(shè)計(jì)的主要目標(biāo)之一就是對任務(wù)發(fā)布者的權(quán)重進(jìn)行計(jì)算,以確定該發(fā)布者對平臺的重要程度。為此,本文定義發(fā)布者活躍度Pw和任務(wù)累計(jì)成交額Vw對發(fā)布者權(quán)重進(jìn)行度量。
定義1 發(fā)布者活躍度。描述當(dāng)前任務(wù)發(fā)布者活躍程度所占比重,以任務(wù)發(fā)布者在某一周期T內(nèi)發(fā)布任務(wù)的次數(shù)S度量任務(wù)發(fā)布者的活躍度,用Pw表示:
(2)
其中:S是周期T內(nèi)該發(fā)布者發(fā)布任務(wù)總次數(shù),ti表示距離周期起始時(shí)刻的時(shí)間,ti越大表示該任務(wù)距離當(dāng)前時(shí)間越近,說明該發(fā)布者對平臺重要程度越高,所以其權(quán)重越大。
定義2 任務(wù)累計(jì)成交額。描述該發(fā)布者發(fā)布眾包任務(wù)累積成交金額,以任務(wù)發(fā)布者在某一周期T內(nèi)累積發(fā)布任務(wù)的總額來衡量該發(fā)布者對平臺的重要程度,用Vw表示:
(3)
其中:S是周期T內(nèi)該發(fā)布者發(fā)布任務(wù)總次數(shù),mi是該發(fā)布者發(fā)布的第i個(gè)眾包任務(wù)的成交金額,ti表示距離周期起始時(shí)刻的時(shí)間,ti越大表示該任務(wù)距離當(dāng)前時(shí)間越近,說明該發(fā)布者對平臺重要程度越高,所以其權(quán)重越大。
綜上,任務(wù)發(fā)布者權(quán)重Wpro計(jì)算如式(4)所示:
Wpro=ωPw+(1-ω)Vw
(4)
其中ω為任務(wù)發(fā)布者權(quán)重因子,ω∈[0,1]。實(shí)驗(yàn)表明,當(dāng)ω=0.4時(shí)效果最佳。
軟件眾包任務(wù)發(fā)布優(yōu)先級計(jì)算中的任務(wù)權(quán)重模型,是從模塊復(fù)雜度、設(shè)計(jì)復(fù)雜度和任務(wù)復(fù)雜度等方面度量任務(wù)復(fù)雜度,并基于任務(wù)復(fù)雜度,從任務(wù)效益和任務(wù)緊急程度兩方面計(jì)算得到任務(wù)權(quán)重。對于平臺在某時(shí)間段接收的任務(wù),用集合T={t1,t2,…,tn}表示,對于每個(gè)任務(wù)ti∈T,由于任務(wù)復(fù)雜度、報(bào)價(jià)、任務(wù)期限都存在差異,因此所占權(quán)重也不同。
任務(wù)權(quán)重模型中的任務(wù)復(fù)雜度,是基于軟件工程中的軟件架構(gòu)及數(shù)據(jù)流圖模型,并參照文獻(xiàn)[13]所述復(fù)雜度計(jì)算方法計(jì)算而來,包括模塊復(fù)雜度、設(shè)計(jì)復(fù)雜度及數(shù)據(jù)復(fù)雜度三個(gè)方面。
模塊復(fù)雜度Cmod是通過計(jì)算系統(tǒng)中各個(gè)子模塊的復(fù)雜度得出,計(jì)算如下:
(5)
其中:n表示模塊的總數(shù),ev(Gi)表示第i個(gè)子模塊的復(fù)雜度。
設(shè)計(jì)復(fù)雜度Cdes則以系統(tǒng)級模塊之間的相互調(diào)用關(guān)系來度量,其值為程序中所有模塊設(shè)計(jì)復(fù)雜度之和,公式如下:
(6)
(7)
其中:Ci, j表示模塊i是否調(diào)用模塊j,若調(diào)用,則Ci, j=1;反之Ci, j=0,n是模塊總數(shù)。
數(shù)據(jù)復(fù)雜度Cstr是使用數(shù)據(jù)流圖中路徑個(gè)數(shù)和每條路徑的長度來進(jìn)行度量,其值為所有路徑復(fù)雜程度之和。所謂路徑,是指從某個(gè)特定的輸入,經(jīng)過一系列處理,最終得到某個(gè)輸出的全流程。數(shù)據(jù)復(fù)雜度計(jì)算如下:
(8)
其中:m是數(shù)據(jù)流圖中的路徑個(gè)數(shù),Lk是第k條路徑的長度。
綜上,可得任務(wù)復(fù)雜度Ctas如式(9):
Ctas=αCmod+βCdes+γCstr;1>α>β>γ>0,
α+β+γ=1
(9)
式(9)表明,在眾包平臺中,模塊復(fù)雜度是衡量任務(wù)復(fù)雜度最重要的指標(biāo),其次是模塊間的耦合程度,而數(shù)據(jù)復(fù)雜性則較為次要。實(shí)驗(yàn)表明,當(dāng)α=0.5,β=0.3,γ=0.2時(shí)效果最佳。
考慮到報(bào)價(jià)與完成周期對任務(wù)的影響,根據(jù)任務(wù)復(fù)雜度,以單位報(bào)價(jià)與任務(wù)期限度量任務(wù)權(quán)重。為此,本文定義任務(wù)效益和任務(wù)緊急程度兩個(gè)因子來進(jìn)行任務(wù)權(quán)重的計(jì)算。
2.2.1 任務(wù)效益
相對于眾包平臺,任務(wù)報(bào)價(jià)是其較為優(yōu)先考慮的因素,本文以任務(wù)復(fù)雜度與任務(wù)報(bào)價(jià)度量任務(wù)效益。當(dāng)任務(wù)復(fù)雜度相同時(shí),任務(wù)報(bào)價(jià)越高,任務(wù)效益越高。任務(wù)效益因子B是將任務(wù)復(fù)雜度除以任務(wù)報(bào)價(jià),并將所得結(jié)果歸一化得來,公式如下:
B=e-Ctas/Q
(10)
其中:Q表示任務(wù)的總報(bào)價(jià),Ctas表示任務(wù)復(fù)雜度。
2.2.2 任務(wù)緊急程度
為使平臺中所有發(fā)布者的任務(wù)盡可能多地被分配出去,當(dāng)任務(wù)復(fù)雜度相同時(shí),任務(wù)期限越短,任務(wù)緊急程度越高,因此,任務(wù)緊急程度因子U是將任務(wù)期限除以任務(wù)復(fù)雜度,并將所得結(jié)果歸一化得來,公式如下:
U=e-AT/Ctas
(11)
其中:AT表示任務(wù)期限,Ctas表示任務(wù)復(fù)雜度。
2.2.3 任務(wù)權(quán)重
如上所述,本文定義任務(wù)權(quán)重Wtas,并采用對數(shù)Logistic模式,計(jì)算如下:
Wtas=1/(1+e-λB-μU);1>λ>μ>0,λ+μ=1
(12)
其中λ是任務(wù)效益權(quán)重因子,約束條件1>λ>μ>0表明報(bào)價(jià)始終是平臺優(yōu)先考慮的因素,因此其所占比重最大,而對任務(wù)期限考慮則相對較小,這符合實(shí)際中平臺的考慮方式。實(shí)驗(yàn)表明,當(dāng)λ=0.8,μ=0.2時(shí)效果最佳。
任務(wù)發(fā)布優(yōu)先級模型通過計(jì)算任務(wù)發(fā)布者權(quán)重Wpro和任務(wù)權(quán)重Wtas,得到任務(wù)優(yōu)先數(shù)δ,根據(jù)任務(wù)優(yōu)先數(shù)確定任務(wù)發(fā)布的優(yōu)先級。任務(wù)優(yōu)先數(shù)δ如式(13)所示:
δ=φWpro+(1-φ)Wtas
(13)
其中φ是任務(wù)優(yōu)先數(shù)因子,φ∈[0,1],實(shí)際應(yīng)用表明,當(dāng)φ=0.6時(shí)效果最佳。
任務(wù)發(fā)布優(yōu)先級TRP算法描述如算法1所示。
算法1 TRP算法。
輸入:任務(wù)發(fā)布次數(shù)S,歷史任務(wù)總額M,任務(wù)報(bào)價(jià)Q,任務(wù)期限AT。
輸出:任務(wù)優(yōu)先數(shù)δ。
1)基于權(quán)重時(shí)間函數(shù)計(jì)算發(fā)布者活躍度Pw和任務(wù)累計(jì)成交額Vw;
2)基于Pw和Vw計(jì)算任務(wù)發(fā)布者權(quán)重Wpro;
3)基于系統(tǒng)架構(gòu)圖、數(shù)據(jù)流圖計(jì)算模塊復(fù)雜度Cmod、設(shè)計(jì)復(fù)雜度Cdes和數(shù)據(jù)復(fù)雜度Cstr;
4)基于Cmod、Cdes和Cstr計(jì)算任務(wù)復(fù)雜度Ctas;
5)基于任務(wù)復(fù)雜度Ctas和任務(wù)報(bào)價(jià)Q計(jì)算任務(wù)效益因子B;
6)基于任務(wù)復(fù)雜度Ctas和任務(wù)期限AT計(jì)算任務(wù)緊急程度因子U;
7)基于B和U計(jì)算任務(wù)權(quán)重Wtas;
8)基于任務(wù)發(fā)布者權(quán)重Wpro和任務(wù)權(quán)重Wtas計(jì)算任務(wù)優(yōu)先數(shù)δ;
9)返回任務(wù)優(yōu)先數(shù)δ,算法結(jié)束。
根據(jù)以上算法,可以計(jì)算出任務(wù)優(yōu)先數(shù),平臺根據(jù)任務(wù)優(yōu)先數(shù)合理安排任務(wù)。
TRP算法主要由三大部分構(gòu)成,其中,眾包任務(wù)發(fā)布者權(quán)重模型中,計(jì)算發(fā)布者活躍度與任務(wù)累計(jì)成交額的復(fù)雜度均為Ο(n1),所以計(jì)算發(fā)布者權(quán)重的時(shí)間復(fù)雜度為Ο(n1);在任務(wù)權(quán)重模型中,計(jì)算模塊復(fù)雜度和數(shù)據(jù)復(fù)雜度的時(shí)間復(fù)雜度均為Ο(n2),而設(shè)計(jì)復(fù)雜度僅與模塊間的相互調(diào)用有關(guān),因?yàn)橛衝個(gè)模塊,所以其時(shí)間復(fù)雜度為Ο(n22),因此計(jì)算任務(wù)權(quán)重的復(fù)雜度為Ο(n22)。綜上可知,TRP算法的復(fù)雜度為Ο(n1)+Ο(n22)。
本文提出的軟件眾包任務(wù)發(fā)布優(yōu)先級模型,綜合考慮了任務(wù)發(fā)布者與任務(wù)本身的權(quán)重,實(shí)現(xiàn)了任務(wù)發(fā)布優(yōu)先級的排序,其合理性和有效性通過實(shí)驗(yàn)予以驗(yàn)證。
為了驗(yàn)證TRP算法的有效性,本文抓取了程序員客棧上12 739個(gè)任務(wù)發(fā)布者及其成功發(fā)布的4 721條任務(wù)信息進(jìn)行實(shí)驗(yàn),由于主要驗(yàn)證不同數(shù)據(jù)量對算法性能的影響,所以取式(4)中ω=0.4,式(9)中α=0.5,β=0.3,γ=0.2,式(12)中λ=0.8,μ=0.2,式(13)中φ=0.6,任務(wù)數(shù)量的取值范圍是[400,3 600],任務(wù)發(fā)布者數(shù)量的取值范圍是[1 000,9 000]。
4.2.1 發(fā)布者數(shù)量變化對算法的影響
當(dāng)任務(wù)發(fā)布者數(shù)量為{1 000,2 000,…,9 000}時(shí),分別分析算法準(zhǔn)確度和算法運(yùn)行時(shí)間,部分任務(wù)發(fā)布者信息如表1所示。
表1 任務(wù)發(fā)布者信息表
當(dāng)任務(wù)數(shù)量恒定時(shí),任務(wù)發(fā)布者數(shù)量對算法的影響如圖2~3所示。
由圖2~3可以看出,當(dāng)任務(wù)數(shù)量恒定時(shí),隨著任務(wù)發(fā)布者數(shù)量的增加,算法準(zhǔn)確度逐漸提升。當(dāng)任務(wù)發(fā)布者數(shù)量超過7 000之后,算法準(zhǔn)確度慢慢趨向于穩(wěn)定,并基本穩(wěn)定在0.92。算法運(yùn)行時(shí)間也隨著任務(wù)發(fā)布者數(shù)量的增加而緩慢增加,當(dāng)任務(wù)發(fā)布者數(shù)量超過5 000之后,算法運(yùn)行時(shí)間增大的幅度越來越小,說明數(shù)據(jù)量太大時(shí),不會對算法的性能造成很大影響,驗(yàn)證了算法的穩(wěn)定性。
圖2 任務(wù)發(fā)布者數(shù)量與準(zhǔn)確度之間的關(guān)系
圖3 任務(wù)發(fā)布者數(shù)量與運(yùn)行時(shí)間之間的關(guān)系
4.2.2 任務(wù)數(shù)量變化對算法的影響
當(dāng)任務(wù)數(shù)量為{400,800,1 200,…,3 600}時(shí),分別分析算法準(zhǔn)確度和算法運(yùn)行時(shí)間,部分任務(wù)信息如表2所示。
表2 部分任務(wù)信息表
當(dāng)任務(wù)發(fā)布者數(shù)量恒定時(shí),任務(wù)數(shù)量對算法的影響如圖4~5所示。
圖5 任務(wù)數(shù)與運(yùn)行時(shí)間之間的關(guān)系
由圖4~5可以看出,當(dāng)任務(wù)發(fā)布者數(shù)量恒定時(shí):隨著任務(wù)數(shù)量的增加,算法準(zhǔn)確度逐漸提升,當(dāng)任務(wù)數(shù)量超過2 000之后,算法準(zhǔn)確度基本穩(wěn)定在0.93;當(dāng)任務(wù)數(shù)量較少時(shí),算法運(yùn)行時(shí)間變化較大,隨著任務(wù)數(shù)量的增加,算法運(yùn)行時(shí)間也緩慢增加;當(dāng)任務(wù)數(shù)量超過2 000之后,算法運(yùn)行時(shí)間變化越來越小,基本趨向于水平。由此,驗(yàn)證了算法的有效性。
4.2.3 參數(shù)設(shè)定
本文利用爬取的數(shù)據(jù),在自己的平臺上做模擬實(shí)驗(yàn),以確定最適合的參數(shù)。每次都選擇發(fā)布序列中的前100個(gè)任務(wù)進(jìn)行實(shí)驗(yàn)。
1)任務(wù)發(fā)布者權(quán)重因子ω,任務(wù)權(quán)重計(jì)算中任務(wù)效益權(quán)重因子λ及任務(wù)優(yōu)先數(shù)因子φ的確定。
本文對任務(wù)發(fā)布前和任務(wù)實(shí)際接收后的數(shù)據(jù)進(jìn)行對比,以任務(wù)成功分配的概率作為度量條件,其結(jié)果如圖6~8所示。
圖6 任務(wù)發(fā)布者權(quán)重因子與任務(wù)成功分配率之間的關(guān)系
圖7 任務(wù)效益權(quán)重因子與任務(wù)成功分配率之間的關(guān)系
圖8 任務(wù)優(yōu)先數(shù)因子與任務(wù)成功分配率之間的關(guān)系
由圖6可知,當(dāng)任務(wù)發(fā)布者權(quán)重因子ω=0.4時(shí),任務(wù)成功分配率最高,為97%;由圖7可知,當(dāng)任務(wù)效益權(quán)重因子λ=0.8時(shí),任務(wù)成功分配率高達(dá)97.6%,由式(12)的約束公式可知,此時(shí)μ=0.2;由圖8可知,當(dāng)任務(wù)優(yōu)先數(shù)因子φ=0.6時(shí),任務(wù)成功分配率最高,為98.1%。
2)任務(wù)復(fù)雜度計(jì)算中相關(guān)參數(shù)的確定。
本文對任務(wù)發(fā)布前和任務(wù)實(shí)際接收后的數(shù)據(jù)進(jìn)行對比,提出預(yù)期復(fù)雜可信度,即以任務(wù)預(yù)期復(fù)雜度與軟件開發(fā)實(shí)際復(fù)雜度之間的吻合度的高低作為其度量條件,由式(9)可知,α∈[0.4,0.8],γ∈[0.1,0.3],其結(jié)果如圖9所示。
圖9 參數(shù)α、γ與預(yù)期復(fù)雜可信度之間的關(guān)系
由圖9可知,當(dāng)參數(shù)α=0.5,γ=0.2時(shí),吻合度最高,為98%,此時(shí)β=0.3。
軟件眾包任務(wù)發(fā)布優(yōu)先級是眾包研究中一個(gè)重要的環(huán)節(jié),本文針對軟件眾包任務(wù)發(fā)布過程中發(fā)布者和眾包任務(wù)兩大類因素對眾包任務(wù)優(yōu)先級的影響,提出了種基于發(fā)布者權(quán)重與任務(wù)權(quán)重的軟件眾包任務(wù)發(fā)布優(yōu)先級計(jì)算方法。實(shí)驗(yàn)表明,該算法具有一定的有效性和合理性,同時(shí)也具有較高的穩(wěn)定性。