軟件眾包任務(wù)發(fā)布優(yōu)先級計算方法

趙焜松，余敦輝,2，張萬山,2

(1.湖北大學(xué) 計算機與信息工程學(xué)院，武漢 430062； 2.湖北省教育信息化工程技術(shù)中心，武漢 430062)(*通信作者電子郵箱yumhy@163.com)

0 引言

隨著互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展，眾包(crowdsourcing)[1]受到了更多工業(yè)和學(xué)術(shù)界人士的極大關(guān)注。眾包平臺，尤其是軟件眾包(software crowdsourcing)平臺，成為當(dāng)前軟件開發(fā)的流行方式之一。軟件眾包的相關(guān)研究已成為當(dāng)前的研究熱點之一，眾多研究人員就軟件眾包任務(wù)設(shè)計、任務(wù)標(biāo)價、欺詐者分析、任務(wù)分配、眾包工人選擇等問題展開了大量的研究。

文獻[2-3]中概括了任務(wù)分配中相關(guān)研究，為以后的研究提供了參考。文獻[4]中提出了質(zhì)量控制策略和眾包結(jié)果質(zhì)量評估方法，有效地控制了任務(wù)完成質(zhì)量；但對任務(wù)復(fù)雜度和效益等考慮不足。文獻[5]中對軟件任務(wù)參與度的影響因素進行了分析，但忽略了發(fā)布者對任務(wù)的影響。文獻[6-7]中對眾包質(zhì)量進行評估，但欠缺對任務(wù)發(fā)布者的考慮。文獻[8]中提出了一種基于用戶信譽值的激勵機制，并通過仿真實驗驗證了激勵機制的有效性，但涉及實際用戶參與度對眾包質(zhì)量的影響。文獻[9]中針對眾包系統(tǒng)中的激勵和信譽機制進行研究，設(shè)計了激勵機制和信譽機制來確保用戶盡最大努力高質(zhì)量地完成任務(wù)，但實際上發(fā)布者、眾包工作者和眾包任務(wù)的特征均會對任務(wù)發(fā)布之后的結(jié)果產(chǎn)生一定影響。文獻[10]中提出了基于用戶可靠性的眾包系統(tǒng)任務(wù)分配機制，通過仿真實驗證明了所設(shè)計任務(wù)分配機制的高效性；但是活躍度也會對用戶有實際影響。文獻[11]中提出基于活躍度的眾包工作者信譽模型，綜合考慮了眾包活躍度與信譽值；但并未考慮眾包任務(wù)本身的特性。文獻[12]中針對任務(wù)本身的特性，分析了眾包任務(wù)設(shè)計對眾包參與者行為的影響；但忽略了任務(wù)發(fā)布者所產(chǎn)生的影響。然而上述研究并未將任務(wù)發(fā)布者與任務(wù)綜合考慮，且都建立在眾包任務(wù)被分配的基礎(chǔ)上。

對于軟件眾包平臺而言，不同的發(fā)布者在平臺發(fā)布軟件眾包任務(wù)的踴躍程度不一樣，歷史發(fā)布任務(wù)的總金額不同，因此，不同任務(wù)發(fā)布者對于平臺的重要性是不同的；同時，某個被發(fā)布的軟件眾包任務(wù)的效益權(quán)重和緊迫程度也存在差異。所以，相對于平臺而言，對于不同發(fā)布者發(fā)布的任務(wù)，如何進行優(yōu)先級排序，從而提高平臺收益，是其關(guān)注的重點。

本文工作主要研究如何根據(jù)發(fā)布者和任務(wù)的特征，衡量任務(wù)發(fā)布的優(yōu)先級。為了解決上述問題，本文假設(shè)某時間段內(nèi)有平臺收到若干軟件眾包任務(wù)申請，以優(yōu)化任務(wù)發(fā)布次序為目標(biāo)，提出了一種基于發(fā)布者活躍度與任務(wù)權(quán)重的軟件眾包任務(wù)發(fā)布優(yōu)先級(Task Release Priority, TRP)計算算法：首先，基于任務(wù)發(fā)布者的活躍度及其任務(wù)累積成交額，利用半正弦曲線的時間權(quán)重函數(shù)度量任務(wù)發(fā)布者權(quán)重；然后，對任務(wù)本身的特性進行分析，以模塊復(fù)雜度、設(shè)計復(fù)雜度和數(shù)據(jù)復(fù)雜度三個方面度量任務(wù)復(fù)雜度，衡量任務(wù)效益和任務(wù)緊急程度，計算得到任務(wù)權(quán)重；最后，綜合考慮發(fā)布者權(quán)重與任務(wù)權(quán)重計算得到任務(wù)優(yōu)先數(shù)。使用該模型可以使平臺以最優(yōu)的方式確定任務(wù)分配優(yōu)先級，以便合理安排將要發(fā)布的任務(wù)，最終提高平臺收益。

1 軟件眾包任務(wù)發(fā)布者權(quán)重模型

軟件眾包任務(wù)發(fā)布者本身的屬性會影響平臺收益。為了反映在某一周期內(nèi)任務(wù)發(fā)布者對平臺的重要程度，本文采用了一種半正弦的時間權(quán)重函數(shù)作為擬合曲線，通過給不同的任務(wù)發(fā)布者屬性賦予權(quán)值來反映其所占比重。

1.1 基于半正弦曲線的時間權(quán)重函數(shù)

本文約定半正弦曲線函數(shù)的時間權(quán)重函數(shù)為：

weight(t)=[sin (πt/T)+1]/2

(1)

如圖1所示，t是距離周期起始時刻的時間，t越小說明距離周期起始時刻越近，即距離當(dāng)前時刻越遠，平臺無需對其過分關(guān)注，因此所占權(quán)重趨向于0；t越大則說明距離當(dāng)前時刻越近，該發(fā)布者對平臺的重要程度越高，因此，平臺加大其權(quán)重。

式(1)中T表示一個具有調(diào)節(jié)作用的函數(shù)周期，不同的t會產(chǎn)生不同權(quán)重值結(jié)果，t的取值范圍為[0,T/2]，weight(t)的取值范圍在[0,1]，適用于反映任務(wù)發(fā)布者對平臺的重要程度。

圖1 半正弦曲線

1.2 軟件眾包任務(wù)發(fā)布者權(quán)重模型

軟件眾包任務(wù)發(fā)布優(yōu)先級模型設(shè)計的主要目標(biāo)之一就是對任務(wù)發(fā)布者的權(quán)重進行計算，以確定該發(fā)布者對平臺的重要程度。為此，本文定義發(fā)布者活躍度Pw和任務(wù)累計成交額Vw對發(fā)布者權(quá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表示距離周期起始時刻的時間，ti越大表示該任務(wù)距離當(dāng)前時間越近，說明該發(fā)布者對平臺重要程度越高，所以其權(quán)重越大。

定義2 任務(wù)累計成交額。描述該發(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個眾包任務(wù)的成交金額，ti表示距離周期起始時刻的時間，ti越大表示該任務(wù)距離當(dāng)前時間越近，說明該發(fā)布者對平臺重要程度越高，所以其權(quán)重越大。

綜上，任務(wù)發(fā)布者權(quán)重Wpro計算如式(4)所示：

Wpro=ωPw+(1-ω)Vw

(4)

其中ω為任務(wù)發(fā)布者權(quán)重因子，ω∈[0,1]。實驗表明，當(dāng)ω=0.4時效果最佳。

2 基于復(fù)雜度的軟件眾包任務(wù)權(quán)重

軟件眾包任務(wù)發(fā)布優(yōu)先級計算中的任務(wù)權(quán)重模型，是從模塊復(fù)雜度、設(shè)計復(fù)雜度和任務(wù)復(fù)雜度等方面度量任務(wù)復(fù)雜度，并基于任務(wù)復(fù)雜度，從任務(wù)效益和任務(wù)緊急程度兩方面計算得到任務(wù)權(quán)重。對于平臺在某時間段接收的任務(wù)，用集合T={t1,t2,…,tn}表示，對于每個任務(wù)ti∈T，由于任務(wù)復(fù)雜度、報價、任務(wù)期限都存在差異，因此所占權(quán)重也不同。

2.1 軟件眾包任務(wù)復(fù)雜度計算

任務(wù)權(quán)重模型中的任務(wù)復(fù)雜度，是基于軟件工程中的軟件架構(gòu)及數(shù)據(jù)流圖模型，并參照文獻[13]所述復(fù)雜度計算方法計算而來，包括模塊復(fù)雜度、設(shè)計復(fù)雜度及數(shù)據(jù)復(fù)雜度三個方面。

模塊復(fù)雜度Cmod是通過計算系統(tǒng)中各個子模塊的復(fù)雜度得出，計算如下：

(5)

其中：n表示模塊的總數(shù)，ev(Gi)表示第i個子模塊的復(fù)雜度。

設(shè)計復(fù)雜度Cdes則以系統(tǒng)級模塊之間的相互調(diào)用關(guān)系來度量，其值為程序中所有模塊設(shè)計復(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ù)流圖中路徑個數(shù)和每條路徑的長度來進行度量，其值為所有路徑復(fù)雜程度之和。所謂路徑，是指從某個特定的輸入，經(jīng)過一系列處理，最終得到某個輸出的全流程。數(shù)據(jù)復(fù)雜度計算如下：

(8)

其中：m是數(shù)據(jù)流圖中的路徑個數(shù)，Lk是第k條路徑的長度。

綜上，可得任務(wù)復(fù)雜度Ctas如式(9)：

Ctas=αCmod+βCdes+γCstr;1>α>β>γ>0,

α+β+γ=1

(9)

式(9)表明，在眾包平臺中，模塊復(fù)雜度是衡量任務(wù)復(fù)雜度最重要的指標(biāo)，其次是模塊間的耦合程度，而數(shù)據(jù)復(fù)雜性則較為次要。實驗表明，當(dāng)α=0.5，β=0.3，γ=0.2時效果最佳。

2.2 基于復(fù)雜度的軟件眾包任務(wù)權(quán)重

考慮到報價與完成周期對任務(wù)的影響，根據(jù)任務(wù)復(fù)雜度，以單位報價與任務(wù)期限度量任務(wù)權(quán)重。為此，本文定義任務(wù)效益和任務(wù)緊急程度兩個因子來進行任務(wù)權(quán)重的計算。

2.2.1 任務(wù)效益

相對于眾包平臺，任務(wù)報價是其較為優(yōu)先考慮的因素，本文以任務(wù)復(fù)雜度與任務(wù)報價度量任務(wù)效益。當(dāng)任務(wù)復(fù)雜度相同時，任務(wù)報價越高，任務(wù)效益越高。任務(wù)效益因子B是將任務(wù)復(fù)雜度除以任務(wù)報價，并將所得結(jié)果歸一化得來，公式如下：

B=e-Ctas/Q

(10)

其中：Q表示任務(wù)的總報價，Ctas表示任務(wù)復(fù)雜度。

2.2.2 任務(wù)緊急程度

為使平臺中所有發(fā)布者的任務(wù)盡可能多地被分配出去，當(dāng)任務(wù)復(fù)雜度相同時，任務(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模式，計算如下：

Wtas=1/(1+e-λB-μU);1>λ>μ>0,λ+μ=1

(12)

其中λ是任務(wù)效益權(quán)重因子，約束條件1>λ>μ>0表明報價始終是平臺優(yōu)先考慮的因素，因此其所占比重最大，而對任務(wù)期限考慮則相對較小，這符合實際中平臺的考慮方式。實驗表明，當(dāng)λ=0.8，μ=0.2時效果最佳。

3 軟件眾包任務(wù)發(fā)布優(yōu)先級計算

3.1 軟件眾包任務(wù)發(fā)布優(yōu)先級計算

任務(wù)發(fā)布優(yōu)先級模型通過計算任務(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]，實際應(yīng)用表明，當(dāng)φ=0.6時效果最佳。

任務(wù)發(fā)布優(yōu)先級TRP算法描述如算法1所示。

算法1 TRP算法。

輸入:任務(wù)發(fā)布次數(shù)S，歷史任務(wù)總額M，任務(wù)報價Q，任務(wù)期限AT。

輸出:任務(wù)優(yōu)先數(shù)δ。

1)基于權(quán)重時間函數(shù)計算發(fā)布者活躍度Pw和任務(wù)累計成交額Vw；

2)基于Pw和Vw計算任務(wù)發(fā)布者權(quán)重Wpro;

3)基于系統(tǒng)架構(gòu)圖、數(shù)據(jù)流圖計算模塊復(fù)雜度Cmod、設(shè)計復(fù)雜度Cdes和數(shù)據(jù)復(fù)雜度Cstr;

4)基于Cmod、Cdes和Cstr計算任務(wù)復(fù)雜度Ctas;

5)基于任務(wù)復(fù)雜度Ctas和任務(wù)報價Q計算任務(wù)效益因子B;

6)基于任務(wù)復(fù)雜度Ctas和任務(wù)期限AT計算任務(wù)緊急程度因子U;

7)基于B和U計算任務(wù)權(quán)重Wtas;

8)基于任務(wù)發(fā)布者權(quán)重Wpro和任務(wù)權(quán)重Wtas計算任務(wù)優(yōu)先數(shù)δ;

9)返回任務(wù)優(yōu)先數(shù)δ,算法結(jié)束。

根據(jù)以上算法，可以計算出任務(wù)優(yōu)先數(shù)，平臺根據(jù)任務(wù)優(yōu)先數(shù)合理安排任務(wù)。

3.2 算法復(fù)雜度分析

TRP算法主要由三大部分構(gòu)成，其中，眾包任務(wù)發(fā)布者權(quán)重模型中，計算發(fā)布者活躍度與任務(wù)累計成交額的復(fù)雜度均為Ο(n1)，所以計算發(fā)布者權(quán)重的時間復(fù)雜度為Ο(n1)；在任務(wù)權(quán)重模型中，計算模塊復(fù)雜度和數(shù)據(jù)復(fù)雜度的時間復(fù)雜度均為Ο(n2)，而設(shè)計復(fù)雜度僅與模塊間的相互調(diào)用有關(guān)，因為有n個模塊，所以其時間復(fù)雜度為Ο(n22)，因此計算任務(wù)權(quán)重的復(fù)雜度為Ο(n22)。綜上可知，TRP算法的復(fù)雜度為Ο(n1)+Ο(n22)。

4 實驗結(jié)果與分析

本文提出的軟件眾包任務(wù)發(fā)布優(yōu)先級模型，綜合考慮了任務(wù)發(fā)布者與任務(wù)本身的權(quán)重，實現(xiàn)了任務(wù)發(fā)布優(yōu)先級的排序，其合理性和有效性通過實驗予以驗證。

4.1 實驗數(shù)據(jù)集

為了驗證TRP算法的有效性，本文抓取了程序員客棧上12 739個任務(wù)發(fā)布者及其成功發(fā)布的4 721條任務(wù)信息進行實驗，由于主要驗證不同數(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 實驗結(jié)果與分析

4.2.1 發(fā)布者數(shù)量變化對算法的影響

當(dāng)任務(wù)發(fā)布者數(shù)量為{1 000，2 000,…，9 000}時，分別分析算法準(zhǔn)確度和算法運行時間，部分任務(wù)發(fā)布者信息如表1所示。

表1 任務(wù)發(fā)布者信息表

當(dāng)任務(wù)數(shù)量恒定時，任務(wù)發(fā)布者數(shù)量對算法的影響如圖2～3所示。

由圖2～3可以看出，當(dāng)任務(wù)數(shù)量恒定時，隨著任務(wù)發(fā)布者數(shù)量的增加，算法準(zhǔn)確度逐漸提升。當(dāng)任務(wù)發(fā)布者數(shù)量超過7 000之后，算法準(zhǔn)確度慢慢趨向于穩(wěn)定，并基本穩(wěn)定在0.92。算法運行時間也隨著任務(wù)發(fā)布者數(shù)量的增加而緩慢增加，當(dāng)任務(wù)發(fā)布者數(shù)量超過5 000之后，算法運行時間增大的幅度越來越小，說明數(shù)據(jù)量太大時，不會對算法的性能造成很大影響，驗證了算法的穩(wěn)定性。

圖2 任務(wù)發(fā)布者數(shù)量與準(zhǔn)確度之間的關(guān)系

圖3 任務(wù)發(fā)布者數(shù)量與運行時間之間的關(guān)系

4.2.2 任務(wù)數(shù)量變化對算法的影響

當(dāng)任務(wù)數(shù)量為{400,800,1 200，…，3 600}時，分別分析算法準(zhǔn)確度和算法運行時間，部分任務(wù)信息如表2所示。

表2 部分任務(wù)信息表

當(dāng)任務(wù)發(fā)布者數(shù)量恒定時，任務(wù)數(shù)量對算法的影響如圖4～5所示。

圖5 任務(wù)數(shù)與運行時間之間的關(guān)系

由圖4～5可以看出，當(dāng)任務(wù)發(fā)布者數(shù)量恒定時：隨著任務(wù)數(shù)量的增加，算法準(zhǔn)確度逐漸提升，當(dāng)任務(wù)數(shù)量超過2 000之后，算法準(zhǔn)確度基本穩(wěn)定在0.93；當(dāng)任務(wù)數(shù)量較少時，算法運行時間變化較大，隨著任務(wù)數(shù)量的增加，算法運行時間也緩慢增加；當(dāng)任務(wù)數(shù)量超過2 000之后，算法運行時間變化越來越小，基本趨向于水平。由此，驗證了算法的有效性。

4.2.3 參數(shù)設(shè)定

本文利用爬取的數(shù)據(jù)，在自己的平臺上做模擬實驗，以確定最適合的參數(shù)。每次都選擇發(fā)布序列中的前100個任務(wù)進行實驗。

1)任務(wù)發(fā)布者權(quán)重因子ω，任務(wù)權(quán)重計算中任務(wù)效益權(quán)重因子λ及任務(wù)優(yōu)先數(shù)因子φ的確定。

本文對任務(wù)發(fā)布前和任務(wù)實際接收后的數(shù)據(jù)進行對比，以任務(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時，任務(wù)成功分配率最高，為97%；由圖7可知，當(dāng)任務(wù)效益權(quán)重因子λ=0.8時，任務(wù)成功分配率高達97.6%，由式(12)的約束公式可知，此時μ=0.2；由圖8可知，當(dāng)任務(wù)優(yōu)先數(shù)因子φ=0.6時，任務(wù)成功分配率最高，為98.1%。

2)任務(wù)復(fù)雜度計算中相關(guān)參數(shù)的確定。

本文對任務(wù)發(fā)布前和任務(wù)實際接收后的數(shù)據(jù)進行對比，提出預(yù)期復(fù)雜可信度，即以任務(wù)預(yù)期復(fù)雜度與軟件開發(fā)實際復(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時，吻合度最高，為98%，此時β=0.3。

5 結(jié)語

軟件眾包任務(wù)發(fā)布優(yōu)先級是眾包研究中一個重要的環(huán)節(jié)，本文針對軟件眾包任務(wù)發(fā)布過程中發(fā)布者和眾包任務(wù)兩大類因素對眾包任務(wù)優(yōu)先級的影響，提出了種基于發(fā)布者權(quán)重與任務(wù)權(quán)重的軟件眾包任務(wù)發(fā)布優(yōu)先級計算方法。實驗表明，該算法具有一定的有效性和合理性，同時也具有較高的穩(wěn)定性。