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

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

0 引言

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

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

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

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

1 軟件眾包任務發(fā)布者權重模型

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

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

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

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

(1)

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

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

圖1 半正弦曲線

1.2 軟件眾包任務發(fā)布者權重模型

軟件眾包任務發(fā)布優(yōu)先級模型設計的主要目標之一就是對任務發(fā)布者的權重進行計算，以確定該發(fā)布者對平臺的重要程度。為此，本文定義發(fā)布者活躍度Pw和任務累計成交額Vw對發(fā)布者權重進行度量。

定義1 發(fā)布者活躍度。描述當前任務發(fā)布者活躍程度所占比重，以任務發(fā)布者在某一周期T內發(fā)布任務的次數(shù)S度量任務發(fā)布者的活躍度，用Pw表示：

(2)

其中：S是周期T內該發(fā)布者發(fā)布任務總次數(shù)，ti表示距離周期起始時刻的時間，ti越大表示該任務距離當前時間越近，說明該發(fā)布者對平臺重要程度越高，所以其權重越大。

定義2 任務累計成交額。描述該發(fā)布者發(fā)布眾包任務累積成交金額，以任務發(fā)布者在某一周期T內累積發(fā)布任務的總額來衡量該發(fā)布者對平臺的重要程度，用Vw表示：

(3)

其中：S是周期T內該發(fā)布者發(fā)布任務總次數(shù)，mi是該發(fā)布者發(fā)布的第i個眾包任務的成交金額，ti表示距離周期起始時刻的時間，ti越大表示該任務距離當前時間越近，說明該發(fā)布者對平臺重要程度越高，所以其權重越大。

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

Wpro=ωPw+(1-ω)Vw

(4)

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

2 基于復雜度的軟件眾包任務權重

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

2.1 軟件眾包任務復雜度計算

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

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

(5)

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

設計復雜度Cdes則以系統(tǒng)級模塊之間的相互調用關系來度量，其值為程序中所有模塊設計復雜度之和，公式如下：

(6)

(7)

其中：Ci, j表示模塊i是否調用模塊j，若調用，則Ci, j=1；反之Ci, j=0，n是模塊總數(shù)。

數(shù)據(jù)復雜度Cstr是使用數(shù)據(jù)流圖中路徑個數(shù)和每條路徑的長度來進行度量，其值為所有路徑復雜程度之和。所謂路徑，是指從某個特定的輸入，經(jīng)過一系列處理，最終得到某個輸出的全流程。數(shù)據(jù)復雜度計算如下：

(8)

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

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

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

α+β+γ=1

(9)

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

2.2 基于復雜度的軟件眾包任務權重

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

2.2.1 任務效益

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

B=e-Ctas/Q

(10)

其中：Q表示任務的總報價，Ctas表示任務復雜度。

2.2.2 任務緊急程度

為使平臺中所有發(fā)布者的任務盡可能多地被分配出去，當任務復雜度相同時，任務期限越短，任務緊急程度越高，因此，任務緊急程度因子U是將任務期限除以任務復雜度，并將所得結果歸一化得來，公式如下：

U=e-AT/Ctas

(11)

其中：AT表示任務期限，Ctas表示任務復雜度。

2.2.3 任務權重

如上所述，本文定義任務權重Wtas，并采用對數(shù)Logistic模式，計算如下：

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

(12)

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

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

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

任務發(fā)布優(yōu)先級模型通過計算任務發(fā)布者權重Wpro和任務權重Wtas，得到任務優(yōu)先數(shù)δ，根據(jù)任務優(yōu)先數(shù)確定任務發(fā)布的優(yōu)先級。任務優(yōu)先數(shù)δ如式(13)所示：

δ=φWpro+(1-φ)Wtas

(13)

其中φ是任務優(yōu)先數(shù)因子，φ∈[0,1]，實際應用表明，當φ=0.6時效果最佳。

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

算法1 TRP算法。

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

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

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

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

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

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

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

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

7)基于B和U計算任務權重Wtas;

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

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

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

3.2 算法復雜度分析

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

4 實驗結果與分析

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

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

為了驗證TRP算法的有效性，本文抓取了程序員客棧上12 739個任務發(fā)布者及其成功發(fā)布的4 721條任務信息進行實驗，由于主要驗證不同數(shù)據(jù)量對算法性能的影響，所以取式(4)中ω=0.4，式(9)中α=0.5，β=0.3，γ=0.2，式(12)中λ=0.8，μ=0.2，式(13)中φ=0.6，任務數(shù)量的取值范圍是[400,3 600]，任務發(fā)布者數(shù)量的取值范圍是[1 000,9 000]。

4.2 實驗結果與分析

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

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

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

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

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

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

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

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

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

表2 部分任務信息表

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

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

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

4.2.3 參數(shù)設定

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

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

本文對任務發(fā)布前和任務實際接收后的數(shù)據(jù)進行對比，以任務成功分配的概率作為度量條件，其結果如圖6～8所示。

圖6 任務發(fā)布者權重因子與任務成功分配率之間的關系

圖7 任務效益權重因子與任務成功分配率之間的關系

圖8 任務優(yōu)先數(shù)因子與任務成功分配率之間的關系

由圖6可知，當任務發(fā)布者權重因子ω=0.4時，任務成功分配率最高，為97%；由圖7可知，當任務效益權重因子λ=0.8時，任務成功分配率高達97.6%，由式(12)的約束公式可知，此時μ=0.2；由圖8可知，當任務優(yōu)先數(shù)因子φ=0.6時，任務成功分配率最高，為98.1%。

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

本文對任務發(fā)布前和任務實際接收后的數(shù)據(jù)進行對比，提出預期復雜可信度，即以任務預期復雜度與軟件開發(fā)實際復雜度之間的吻合度的高低作為其度量條件，由式(9)可知，α∈[0.4,0.8]，γ∈[0.1,0.3]，其結果如圖9所示。

圖9 參數(shù)α、γ與預期復雜可信度之間的關系

由圖9可知，當參數(shù)α=0.5，γ=0.2時，吻合度最高，為98%，此時β=0.3。

5 結語

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