考慮協(xié)作方雙重身份的數(shù)據(jù)協(xié)作下載激勵機制①

陳 曉 劉 敏 周雅琴 李忠誠

(*中國科學院計算技術研究所 北京 100190) (**中國科學院大學 北京 100049) (***Singapore University of Technology and Design, ISTD, Singapore 487372)

?

考慮協(xié)作方雙重身份的數(shù)據(jù)協(xié)作下載激勵機制①

陳 曉②***劉 敏③*周雅琴***李忠誠*

(*中國科學院計算技術研究所 北京 100190) (**中國科學院大學 北京 100049) (***Singapore University of Technology and Design, ISTD, Singapore 487372)

研究了移動無線網(wǎng)絡數(shù)據(jù)的協(xié)作下載。為了鼓勵資源有限的移動用戶參與協(xié)作下載，針對多任務數(shù)據(jù)下載場景，利用協(xié)作用戶既可作數(shù)據(jù)出售者也可作數(shù)據(jù)請求用戶的合作者的雙重身份，同時考慮協(xié)作用戶差異化的服務質量，基于拍賣理論設計了一種新穎的數(shù)據(jù)協(xié)作下載激勵機制，該機制能夠激勵并選擇合適的協(xié)作用戶完成數(shù)據(jù)下載任務。仿真實驗表明，這種激勵機制的性能優(yōu)于忽略協(xié)作用戶雙重身份的激勵機制，有效提高了協(xié)作用戶的服務質量、請求用戶獲得的效用和社會福利。

激勵機制， 協(xié)作下載， 拍賣理論， 任務分配， 用戶選擇

0 引 言

數(shù)據(jù)協(xié)作下載應用是希望獲得互聯(lián)網(wǎng)數(shù)據(jù)的移動用戶，通過其他移動用戶的數(shù)據(jù)轉發(fā)，間接地獲得網(wǎng)絡數(shù)據(jù)的應用。這類應用不僅可以使無法上網(wǎng)的移動用戶獲得數(shù)據(jù)，而且能夠彌補移動網(wǎng)絡運營商提供移動數(shù)據(jù)服務的缺陷，實現(xiàn)移動用戶和移動運營商之間的“雙贏”。然而，由于移動用戶的移動設備的存儲空間、計算資源以及電池電量等資源都非常有限，很少有用戶自愿無償?shù)貛椭渌脩粝螺d并轉發(fā)數(shù)據(jù)。解決這一難題的一種有效方法是設計激勵機制來鼓勵用戶參與數(shù)據(jù)協(xié)作下載。拍賣理論被廣泛用于激勵機制中，比如發(fā)布任務的移動用戶通過支付一些獎金的方式，激勵其他用戶成為任務的協(xié)作用戶完成其請求的任務[1-6]。在以往的研究中，協(xié)作用戶只被作為服務出售方。然而在數(shù)據(jù)協(xié)作下載應用中，協(xié)作用戶會對發(fā)布的任務產(chǎn)生一定的興趣，也就是說，需要下載的數(shù)據(jù)對協(xié)作用戶具有一定的價值。因此，在數(shù)據(jù)協(xié)作下載的應用中，協(xié)作用戶除了具有數(shù)據(jù)出售方這一個身份外，又多了一個新的身份，即請求用戶的合作伙伴。在數(shù)據(jù)協(xié)作下載應用中，考慮協(xié)作用戶的雙重身份，會給協(xié)作用戶和請求用戶帶來很多好處。首先，由于協(xié)作用戶對需要完成的任務有一定的興趣，協(xié)作用戶會自發(fā)地努力完成任務，提高完成任務的質量。其次，由于需要完成的數(shù)據(jù)任務對協(xié)作用戶有一定的價值，協(xié)作用戶可以作為請求用戶的合作伙伴一起共同分攤完成任務的費用，從而一定程度上降低了請求用戶的費用支出。

針對多任務數(shù)據(jù)下載場景，本文基于協(xié)作用戶的雙重身份——數(shù)據(jù)的出售方和請求用戶的合作者，同時考慮協(xié)作用戶差異化的服務質量，設計了一個基于組合拍賣的成本分攤激勵機制 (Cost AppointMent Incentive based Combinatorial Auctions)，簡稱CAMCA，以鼓勵并選擇合適的用戶參與數(shù)據(jù)協(xié)作下載。據(jù)我們所知，這是第一個針對多任務數(shù)據(jù)下載場景，基于拍賣理論考慮協(xié)作用戶的雙重身份的激勵機制。本文理論分析了CAMCA機制的保護隱私、保證協(xié)作用戶報價真實和計算高效等優(yōu)越特性，并通過仿真實驗驗證了CAMCA機制在服務質量、任務完成比例、請求用戶的效用以及社會福利等方面都優(yōu)于不考慮協(xié)作用戶雙重身份的激勵機制。

1 相關工作

1.1 協(xié)作下載應用

目前，在移動無線網(wǎng)絡中協(xié)作下載的應用有很多。在文獻[7-10]中，在同一時間多個希望觀看同一視頻的用戶，先分別從互聯(lián)網(wǎng)中下載一部分數(shù)據(jù)，然后在本地數(shù)據(jù)共享，從而使每個人獲得完整的數(shù)據(jù)。文獻[7-10]認為用戶之間是合作式的協(xié)作，不需要虛擬貨幣的支付進行激勵，同時協(xié)作用戶需要與請求用戶同時對某個數(shù)據(jù)完全感興趣才會進行協(xié)作，這個約束條件非常嚴格。而在本文的機制中，協(xié)作用戶不要求對數(shù)據(jù)完全感興趣，所以本文的機制適用的范圍更廣。在文獻[11]中，能夠接入網(wǎng)絡的用戶通過向不能上網(wǎng)的用戶分享帶寬，使其能夠連接網(wǎng)絡，并采用非競爭的方式對可用帶寬進行定價與分配。而在本文中，協(xié)作用戶是采用競爭的方式制定服務質量方案。

1.2 協(xié)作應用的激勵機制

激勵機制的設計通常分為基于聲譽的激勵機制和基于虛擬貨幣機制的激勵機制，目前多數(shù)研究集中在基于虛擬貨幣的激勵機制中。拍賣理論作為博弈論的一個分支，是一種定量分析的方法，常在基于虛擬貨幣的機制中使用。

在基于虛擬貨幣的激勵機制中，有在P2P場景中采用虛擬貨幣形式設計的激勵機制[12，13]。由于在P2P系統(tǒng)中，協(xié)作用戶提供的是本地已存儲的文件資源的上傳服務，也就是說協(xié)作用戶已經(jīng)獲得了請求用戶需要的數(shù)據(jù)，所以協(xié)作用戶對內(nèi)容任務不會再有興趣和需求，因此就不會與請求用戶共同分攤成本，所以協(xié)作用戶和請求用戶的策略都與本文有很大不同。在眾包應用中，文獻[14]對實時到達的任務，選擇最優(yōu)的完成任務用戶集合，使用虛擬貨幣作為協(xié)作用戶的完成任務的獎勵。在移動無線網(wǎng)絡協(xié)作下載應用中，文獻[15]設計了一個幫助他人下載數(shù)據(jù)的服務系統(tǒng)，使用虛擬貨幣和聲譽相結合的方式激勵用戶參與協(xié)作下載。文獻[14，15]都沒有使用拍賣的方式設計激勵機制，而且沒有考慮到協(xié)作用戶對任務有興趣而具有雙重身份的特點設計激勵機制。

拍賣理論作為博弈論的分支在很多領域的激勵機制的設計中被采用。文獻[1]采用在線采購拍賣的方式，根據(jù)用戶的邊際價格選擇合適的用戶緩解云存儲數(shù)據(jù)壓力。文獻[2]采用在線拍賣的方式，在預算有限的約束下，設計貪心算法，貪心地選擇邊際價值大于閾值的動態(tài)到達的用戶參與協(xié)作。文獻[3]首次根據(jù)貝葉斯博弈采用全支付拍賣(all-pay auction)的方式選擇用戶實現(xiàn)請求平臺的收益最大化。文獻[4]將用戶的參與程度作為其服務質量，根據(jù)貝葉斯博弈采用逆向拍賣的方式選擇用戶集合以達到一定服務質量要求。在文獻[5]的以用戶為中心的模型中，未考慮協(xié)作用戶的服務質量，采用了組合拍賣方式設計貪心近似算法選擇最優(yōu)協(xié)作用戶集合完成任務。

以上這些研究工作都沒有考慮協(xié)作用戶雙重身份的特點，而且多數(shù)研究工作沒有考慮由協(xié)作用戶完成任務服務質量的不同而帶來任務價值差異性的特點。而本文設計的激勵機制考慮了協(xié)作用戶的服務質量和雙重身份的特點。

針對數(shù)據(jù)協(xié)作下載應用中請求用戶發(fā)布單任務的場景，我們的已有工作[6]基于次級密封得分拍賣機制[16]設計了一個基于協(xié)作用戶雙重身份的激勵機制。本文針對請求用戶發(fā)布多任務場景，基于傳統(tǒng)的組合拍賣機制提出了一個基于協(xié)作用戶雙重身份的激勵機制。

2 系統(tǒng)模型

在本文設計的激勵機制模型中，有一個數(shù)據(jù)下載任務的請求用戶和多個可提供數(shù)據(jù)下載服務的候選協(xié)作用戶A={a1,a2,…,an}，其中|A|≥2。請求用戶有一個數(shù)據(jù)下載任務集合T={τ1,τ2,…,τ}，其中|T|≥1，任務之間是相互獨立的。請求用戶把T所需求的數(shù)據(jù)當作任務向周圍的移動用戶發(fā)布，希望通過購買其他移動用戶的數(shù)據(jù)轉發(fā)服務的方式獲得數(shù)據(jù)。候選協(xié)作用戶ai是在請求用戶周圍，且有能力完成一些數(shù)據(jù)下載任務Ti?T的移動用戶。候選協(xié)作用戶希望以向請求用戶提供所需數(shù)據(jù)的方式獲得報酬。當候選協(xié)作用戶被請求用戶選擇后，成為完成數(shù)據(jù)協(xié)作下載任務的協(xié)作用戶。

假設互聯(lián)網(wǎng)絡中的數(shù)據(jù)內(nèi)容可以按照不同的主題進行分類，如經(jīng)濟類、體育類和娛樂類等，數(shù)據(jù)的表現(xiàn)形式上可以是一首歌、一篇文章或是一段視頻等。假設任意一個數(shù)據(jù)τk有所屬的唯一主題Iτk。

候選協(xié)作用戶對數(shù)據(jù)內(nèi)容的模糊興趣和進行協(xié)作服務的成本參數(shù)是其私有信息。模糊興趣是指用戶對任意一個主題的數(shù)據(jù)可以是完全感興趣或有一些興趣或完全不感興趣。本文使用δiτk(0≤δiτk≤1)表示候選協(xié)作用戶ai對數(shù)據(jù)τk的模糊興趣。δiτk=1(或δiτk=0)表示ai對數(shù)據(jù)τk完全(或不)感興趣，0<δiτk<1表示ai對數(shù)據(jù)τk有一定興趣。ai根據(jù)自身對任務集合的興趣Δi={δiτ1,δiτ2,…,δiτ}確定自己意愿完成的任務集合Ti?T。成本參數(shù)是表示協(xié)作用戶完成任務所需要消耗的成本[16]。候選協(xié)作用戶ai的成本參數(shù)βi(βmin≤βi≤βmax)越大，表示ai完成任務的成本越高，完成任務的能力越低。本文假設ai的βi是隨時間變化的。

本文認為任務的價值受協(xié)作用戶完成服務質量的影響。由于數(shù)據(jù)下載的服務質量可從多個維度綜合衡量，如下載速度和丟包率，為不失一般性，本文假設衡量協(xié)作用戶服務質量的向量是由m個獨立的收益型[17]服務屬性i構成。iτk=(qi1τk,qi2τk,…,qimτk)表示ai對任務τk提供的服務質量向量。假設1表示平均速度，且1是請求用戶必須考慮的服務質量屬性，qi1τk表示ai對任務τk提供的平均速度。服務質量屬性的類型可分兩種，收益型和成本型。收益型屬性的效用隨屬性數(shù)值的增加而增加，而成本型屬性的效用隨屬性數(shù)值的增加而減少。雖然收益型屬性和成本型屬性是兩個性質相反的屬性，但兩個屬性之間可簡單地進行轉換，如平均速度就是數(shù)據(jù)大小除以完成時間。因此，為了方便計算和分析，請求用戶考慮在乎的服務屬性需要先統(tǒng)一為收益型屬性，然后再進行相關計算。

本文假設候選協(xié)作用戶是信息對稱、相互獨立以及風險中性的。也就是說每個用戶除了自身的私有信息外，其他公共信息是相同的；候選協(xié)作用戶獨立地計算自己的收益，不會和其他用戶共謀；候選協(xié)作用戶計算自己的收益時不用考慮風險，也就是確定性收益就是其期望收益。

針對多任務場景，本文以請求用戶自身效用最大化為目標，考慮協(xié)作用戶雙重身份的特點以及服務質量，鼓勵和選擇用戶參與數(shù)據(jù)協(xié)作下載。

3 多任務場景的激勵機制設計

在請求用戶同時發(fā)布多個任務的場景中，即T={τ1,τ2,…,τ}, |T|≥2，請求用戶希望從候選協(xié)作用戶集合A中選擇一個子集作為執(zhí)行數(shù)據(jù)下載任務的協(xié)作用戶集合W?A。本文假設候選協(xié)作用戶ai的投標任務集合Ti不能拆分，即如果ai被選擇成為協(xié)作用戶，Ti就是其分配的任務集合。

3.1 請求用戶確定協(xié)作用戶選擇準則

s.t. xi={0,1}, ?i∈A

(1)

所示。其中，viτk是候選協(xié)作用戶ai完成任務τk的服務價值； xi=1(或0)表示候選協(xié)作用戶ai是(或否)成為協(xié)作用戶，即ai∈W(或ai?W)。由于可能存在多個協(xié)作用戶完成同一個任務的情況，本文使用協(xié)作用戶集合W中完成該任務的最高服務價值表示請求用戶獲得的服務價值。

由于服務屬性是相互獨立的，候選協(xié)作用戶ai的服務價值viτk定義如公式

(2)

所示。其中dτk表示下載任務τk的數(shù)據(jù)大小，qijτk(0≤qijτk≤qijmax)表示協(xié)作用戶ai的第j個服務質量屬性的數(shù)值，qijmax表示ai能提供的服務屬性j的最大數(shù)值。參數(shù)00。

3.2 候選協(xié)作用戶確定投標方案

(3)

所示。其中，由于候選協(xié)作用戶ai具有雙重身份，ai的完成任務τk的收入來自兩部分，一部分來自從ai期望從請求用戶獲得的服務報酬biτk，另一部分來自由自身對數(shù)據(jù)的模糊興趣而從獲得的滿足感?iτk；ciτk是ai完成任務τk的成本。由于任務是相互獨立的，ai完成任務集合Ti的總收入和總成本可分別由每個任務的收入和成本相加得到。

(4)

為衡量候選協(xié)作用戶ai從數(shù)據(jù)τk中獲得的滿足感，即所要下載的數(shù)據(jù)對協(xié)作用戶ai的價值，本文使用biτk作為衡量數(shù)據(jù)價值的標準。這是因為biτk是ai認為數(shù)據(jù)τk對于完全感興趣的用戶(如請求用戶)的價值。由于ai對數(shù)據(jù)τk有著模糊興趣δiτk(0<δiτk<1)，所以ai從該數(shù)據(jù)獲得的滿足感?iτk的定義如下式所示：

?iτk=δiτkbiτk

(5)

由于服務質量屬性是相互獨立的，候選協(xié)作用戶ai完成任務的成本ciτk可由每個服務屬性的成本相加得到[16]，如公式

(6)

所示。其中kj體現(xiàn)邊際成本效應：kj>1[11]體現(xiàn)邊際成本遞增效應，即隨著服務屬性數(shù)值的提高，服務成本的增量逐漸增加；kj=1體現(xiàn)邊際成本恒定不變，即每單位服務屬性提高的成本不變；hj表示服務屬性的成本系數(shù)。

為確定投標方案，ai需確定對每個任務提供的服務質量屬性數(shù)值。由于服務質量屬性之間是獨立的，因此每個服務質量最優(yōu)值可獨立確定。本文假設除平均速度服務屬性1外，其他服務質量屬性的計算數(shù)值不受任務執(zhí)行順序的影響，因此計算方法如公式[6]

j=1,2,…,m (7)

由于候選協(xié)作用戶ai對請求用戶的每個任務都有模糊興趣，而ai的服務時間li有限，所以ai需要確定投標任務集合Ti?T，使自己最有可能被選擇為協(xié)作用戶。由選擇協(xié)作用戶的規(guī)則可知，當ai的投標任務集合具有越高的服務價值和越低投標價格時，該協(xié)作用戶越有可能獲得投標勝利。由于協(xié)作用戶對任務的興趣越高，其提供的服務價值越高，相對報價也越低[6]。因此，CAMCA機制中，ai根據(jù)自身對任務的模糊興趣和服務時間確定投標任務集合Ti的算法如算法1所示。在算法1中，ai先將任務按照模糊興趣的降序排列；然后確定候選任務的完成時間，在有限的服務時間li約束下，確定投標任務集合Ti。

算法1 TaskDetermination(Δi,li)1. l←li,Ti←?,Qi1←?2. Forjfrom1toNN3. τk←argmaxτj∈TTiδiτk;4. q*i1τk←(t1w1(1+δiτk)k1h1βi)1k1-t1;5. Ifq*i1τk≥qi1max6. q*i1τk←qi1max;7. Endif8. υ*←υmax-(υmax-υmin)(qi1max-q*i1τk)qi1max-qi1min;9. l←l-dτk/υ;10. Ifl≥011. υ←dτk/(li-l);12. qi1τk←qi1max-(qi1max-qi1min)(υmax-υ)υmax-υmin;13. Ti←Ti∪{τk};14. Qi1←Qi1∪{qi1τk};15. Else16. break;17. Endif18. Endfor19. ReturnTi,Qi1;

3.3 請求用戶確定協(xié)作用戶及報酬

由請求用戶選擇協(xié)作用戶規(guī)則可知，如式(1)所示，協(xié)作用戶選擇問題是0-1整數(shù)規(guī)劃問題。由于0-1整數(shù)規(guī)劃問題是NP難的，請求用戶確定協(xié)作用戶的問題也是NP難的。因此，本文使用貪心算法設計近似算法確定協(xié)作用戶集合以及協(xié)作用戶的報酬。

(8)

(9)

所示。然后，更新已選用戶集合W的服務價值向量、已選協(xié)作用戶集合W以及未選的候選協(xié)作用戶集合A′。最后，重復上述兩個步驟，當在未選候選協(xié)作用戶集合中，用戶邊際服務得分最大值為負數(shù)時，選擇結束。

算法2 WinnerSetSelection(A)1.W←?,A'←A,s←-∞;2. Forτk∈T3. vWk←0;4. Endfor5. aj←SelectOneWinner(A',W,&s)6. Whiles>07. A'←A'{aj};8. W←W∪{aj};9. Forτk∈Tjdo10. Ifvjk>vWk11. vWk←vjk;12. Endif13. Endfor14. s←-∞15. aj←SelectOneWinner(A',W,&s);16. Endwhile17. ReturnW;

算法3 SelectOneWinner(A',W,&s)1.aImax←0,smax←s;2. Forai∈A'do3. si←-bi;4. Forτk∈Tido5. Ifvik>vWk6. si←si+vik-vWk;7. Endif8. Endfor9. Ifsi>smax10. aImax←ai;11. smax←smax+si;12. Endif13. Endfor14. Returnalmax

算法4 PaymentDetermination(aj)1.pj←0,A'←A{aj},W'←?2. Forτk∈T3. vWk←0;4. Endfor5. Repeat6. s←-∞,vj=0;7. aji←SelectOneWinner(A',W',&s);8. Forτk∈Tdo9. Ifvjk>vWk10. vj←vj+vjk;11. Endif12. Ifvjik>vWk13. vWk←vjk;14. Endif15. Endfor16. pj←maxpj,min{vj-s,vj}}17. W'←W'∪{aji}18. A'←A'{aji}19. Untils<020. Returpj;

4 CAMCA激勵機制理論分析

4.1 保護私有信息

在候選協(xié)作用戶的投標方案中，服務價值向量和投標價格都是由候選協(xié)作用戶的私有興趣和私有成本共同決定的，因此，候選協(xié)作用戶的私有信息得以保護，從而用戶參與協(xié)作的積極性不會受到隱私泄露問題的影響。

4.2 保證投標價格真實

定理1.[19]當拍賣機制滿足以下兩個性質后，該拍賣機制能保證投標價格真實性：

(2)獲勝用戶的報酬是臨界值：如果用戶的報價高于其報酬，則該用戶不會被選擇成為獲勝用戶。

定義：子模函數(shù) 令Z為一個有限集合，對任意的子集X?Y?Z和任意的元素i∈ZY，如果函數(shù)f: 2Z|→滿足f(X∪{i})-f(X)≥f(Y∪{i})-f(Y)，稱函數(shù)f為子模函數(shù)。其中2Z為集合Z的冪集，為實數(shù)集。

(10)

(11)

定理2. CAMCA機制能保證投標價格真實。

證明：首先，協(xié)作用戶選擇算法具有單調性。由協(xié)作用戶選擇算法(如算法3)可知，候選協(xié)作用戶的報價越低，其邊際效用評分函數(shù)越高，越容易成為被選擇成為協(xié)作用戶。

4.3 計算高效

5 實驗和性能分析

本節(jié)使用MATLAB平臺，采用仿真實驗的方法評價CAMCA的性能評價。首先，介紹對比未考慮候選協(xié)作用戶雙重身份的激勵機制MCA以及性能評價指標。接著，闡述仿真實驗的設計。最后，將CAMCA和MCA進行實驗對比分析。

5.1 對比算法及評價指標

在多任務場景中，進行CAMCA與MCA的對比實驗，評價指標分別為獲勝方提供的服務質量、任務集合完成比例、請求用戶獲得的效用(式(12))和社會效用(式(13))。在MCA中，除了協(xié)作用戶在確定投標方案時不考慮自己的雙重身份外，MCA機制的其他步驟都與CAMCA相同。

(12)

(13)

在實驗中，請求用戶發(fā)布的任務種類數(shù)目、候選協(xié)作用戶的成本參數(shù)、模糊興趣參數(shù)和服務時間都是隨機取得，評價指標的結果是重復實驗1000次后的平均數(shù)值。

5.2 實驗設計

候選協(xié)作用戶的成本參數(shù)服從在[βmin, βmax]范圍內(nèi)的均勻分布，成本參數(shù)取值的跨度比例為βmax/βmin=6。由于βmax/βmin值越大，候選協(xié)作用戶的差異性越大，本文提出的激勵機制相對于與對比機制的性能效果更加優(yōu)越。本文選擇適中的[1,6]作為候選協(xié)作用戶成本參數(shù)的取值范圍。

候選協(xié)作用戶ai對屬于主題Ij的數(shù)據(jù)內(nèi)容的興趣δij服從以流行程度Pj為均值的正態(tài)分布[20]，如下式所示：

(14)

為了使δij的取值范圍為[0,1]，正態(tài)分布的標準差σ設為0.15。本文假設協(xié)作用戶對數(shù)據(jù)τk的興趣等于對數(shù)據(jù)所屬主題Iτk的興趣，即δiτk=δiIτk。

本文假設主題數(shù)目為10，數(shù)據(jù)主題的流行程度Pj服從s=2[20]的zipf分布，如下式所示：

(15)

在多任務場景中，請求用戶發(fā)布的任務數(shù)目為20個，每個任務的大小為1M，任務的所屬主題服從請求用戶對數(shù)據(jù)興趣的概率分布。由于手機的搜索范圍和本地網(wǎng)絡連接數(shù)目有限，實驗中參與競標的候選協(xié)作用戶的數(shù)目設定為10～20。候選協(xié)作用戶的服務時間服從[30s,150s]的均勻分布，候選協(xié)作用戶的最大下載速度為200kb/s。協(xié)作用戶根據(jù)任務選擇方法確定投標任務集合。請求用戶考慮的服務質量屬性是平均速度1和丟包率L。由于丟包率是成本型屬性，按照公式

(16)

表1 參數(shù)設置

5.3 多任務場景的實驗結果分析

圖1和圖2分別描述了CAMCA與MCA在服務質量Q1和Q2指標方面隨候選協(xié)作用戶數(shù)目變化的實驗結果。采用CAMCA的請求用戶與采用MCA請求用戶相比，獲得的服務質量屬性Q1平均提高了27.57%，服務質量屬性Q2平均提高了157.17%。這說明在多任務場景中，考慮協(xié)作用戶的雙重身份特點，能夠激勵協(xié)作用戶提高服務質量，從而使請求用戶高質量的服務。在多任務場景下Q1和Q2的平均數(shù)值公式不同，且服務屬性的權重不同w1≠w2， 所以CAMCA的服務屬性數(shù)值Q1和Q2與MCA相比的提高幅度不同。在圖3中，盡管 CAMCA選擇用戶數(shù)目少于MCA選擇用戶數(shù)目， CAMCA的獲勝用戶集合提供的服務質量仍然高于MCA的獲勝用戶提供的服務質量。這進一步驗證了CAMCA機制能夠選擇高質量的協(xié)作用戶集合，并有效地激勵協(xié)作用戶提供高質量的服務。

圖1 請求用戶獲得平均服務質量Q1的比較

圖2 請求用戶獲得平均服務質量Q2的比較

圖3 平均選擇用戶個數(shù)的比較

圖4顯示了CAMCA與MCA在完成任務集合比例指標方面隨候選協(xié)作用戶數(shù)目變化的情況。請求用戶采用CAMCA獲得的任務完成比例比采用MCA獲得的效用平均提高了11.50%。結合圖3所示的CAMCA選擇用戶數(shù)目少于MCA選擇的獲勝用戶數(shù)目的對比結果，可以說明CAMCA能夠有效地激勵有能力的協(xié)作用戶完成更多的任務。

圖4 平均任務集合完成比例的比較

圖5和圖6分別顯示了CAMCA與MCA在請求用戶獲得的效用和社會福利指標方面隨候選協(xié)作用戶數(shù)目變化的實驗結果。請求用戶使用CAMCA機制獲得的效用比使用MCA機制獲得的效用平均提高了69.32%，社會福利平均提高了41.39%。這主要是因為CAMCA中考慮了協(xié)作用戶的雙重身份，協(xié)作用戶對數(shù)據(jù)的興趣提高了協(xié)作用戶提供的服務質量，從而提高了協(xié)作用戶的服務價值以及完成任務的數(shù)量，并且通過與請求用戶一起分攤成本開銷的方式降低了請求用戶的支付費用，實現(xiàn)了請求用戶獲得的效用以及社會福利的提高。

圖5 請求用戶獲得平均效用的比較

圖6 平均社會福利的比較

6 結 論

在移動設備的數(shù)據(jù)協(xié)作下載應用中，針對請求用戶發(fā)布多個數(shù)據(jù)下載任務的場景，考慮協(xié)作用戶在數(shù)據(jù)下載中的雙重身份以及差異化服務質量，提出了一種數(shù)據(jù)協(xié)作下載激勵機制CAMCA，該機制具有保護隱私、保證投標價格真實和計算高效等優(yōu)越特性。本研究通過實驗驗證，與忽略協(xié)作用戶雙重身份的激勵機制相比，CAMCA能充分激勵協(xié)作用戶提供高質量的服務，提高請求用戶的效用以及社會福利。

雖然本文的激勵機制是針對移動設備的數(shù)據(jù)協(xié)作下載應用而設計的，但該激勵機制也可以應用到其他領域中，如延時容忍網(wǎng)絡(delay tolerant networks，DTN)和眾包應用中。只要滿足請求用戶發(fā)布的任務對協(xié)作用戶來說是從未做過且有價值的這一特點，就可以采用本文的機制。

[1] Zhao J, Chu X, Liu H, et al. Online procurement auctions for resource pooling in client assisted cloud storage systems. In: Proceedings of the 34th Annual IEEE International Conference on Computer Communications, Hong Kong, China, 2015. 576 - 584

[2] Zhao D, Li X, Ma H. Budget-feasible online incentive mechanisms for crowdsourcing tasks truthfully.IEEE/ACMTransactionsonNetworking, 2014, 24(2): 647-661

[3] Luo T, Tan H P, Xia L. Profit-maximizing incentive for participatory sensing. In: Proceedings of the 33th Annual IEEE International Conference on Computer Communications, Toronto, Canada, 2014. 127-135

[4] Koutsopoulos I. Optimal incentive-driven design of participatory sensing systems. In: Proceedings of the 32th Annual IEEE International Conference on Computer Communications, Turin, Italy, 2013. 1402-1410

[5] Yang D, Xue G, Fang X, et al. Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing. In: Proceedings of the 18th International Conference on Mobile Computing and Networking, Istanbul, Turkey, 2012. 173-184

[6] Chen X, Wang S, Liu M, et al. Partner-recruitment: Incentive mechanism for content offloading. In: Proceedings of the IEEE International Conference on Communications, Sydney, Australia, 2014. 2538-2543

[7] Chen X, Proulx B, Gong X, et al. Social trust and social reciprocity based cooperative D2D communications. In: Proceedings of the 14th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Bangalore, India, 2013. 187-196

[8] Keller L, Le A, Cici B, et al. MicroCast: cooperative video streaming on smartphones. In: Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services, Ambleside, UK, 2012. 57-70

[9] Seferoglu H, Keller L, Cici B, et al. Cooperative video streaming on smartphones. In: Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing, Monticello, USA, 2011. 220-227

[10] Huang C, Zhou A, Liu M, et al. FEDCVS: A fair and efficient scheduling scheme for dynamic cooperative video streaming on smartphones. In: Proceedings of the IEEE Global Communications Conference, Atlanta, USA, 2013. 1699-1704

[11] Cui Y, Ma T, Cheng X. Multi-hop access pricing in public area WLANs. In: Proceedings of the 30th Annual IEEE International Conference on Computer Communications, Shanghai, China, 2011. 2678-2686

[12] Vishnumurthy V, Chandrakumar S, Sirer E G. Karma: A secure economic framework for peer-to-peer resource sharing. In: Workshop on Economics of Peer-to-Peer Systems, Berkeley, USA, 2003. 35

[13] Zhang Z, Chen S, Yoon M. A distributed incentive scheme for peer-to-peer networks. In: Proceedings of the 26th Annual IEEE International Conference on Computer Communications, Anchorage, USA, 2007. 1091-1099

[14] Boutsis I, Kalogeraki V. On task assignment for real-time reliable crowdsourcing. In: Proceeding of the 2014 IEEE 34th International Conference on Distributed Computing Systems, Madrid, Spain, 2014. 1-10

[15] Yu T, Zhou Z, Zhang D, et al. INDAPSON: An incentive data plan sharing system based on self-organizing network. In: Proceedings of the 33rd Annual IEEE International Conference on Computer Communications, Toronto, Canada, 2014. 1545-1553

[16] David E, Azoulay-schwartz R, Kraus S. Bidding in sealed-bid and english multi-attribute auctions.DecisionSupportSystems, 2006, 42(2): 527-556

[17] 劉樹林, 邱菀華. 多屬性決策基礎理論研究. 系統(tǒng)工程理論與實踐, 1998, 18(1): 38-43

[18] Saaty T L. Decision making with the analytic hierarchy process.InternationalJournalofServicesSciences, 2008, 1(1): 83-98

[19] Singer Y. Budget feasible mechanisms. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, Las Vegas, USA , 2010. 765-774

[20] Gao W, Cao G. User-centric data dissemination in disruption tolerant networks. In: Proceedings of the 30th Annual IEEE International Conference on Computer Communications, Shanghai, China, 2011. 3119-312

An incentive mechanism for cooperative data downloading considering cooperators’ dual identity

Chen Xiao***, Liu Min*, Zhou Yaqin***, Li Zhongcheng*

(*Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190) (**Graduate University of Chinese Academy of Sciences, Beijing 100049) (***Singapore University of Technology and Design, ISTD, Singapore 487372)

The problem of cooperative downloading of mobile wireless data was studied. To spur the mobile users with limited resources in mobile devices to participate in cooperative downloading, a novel incentive mechanism for cooperative data downloading based on auction theories was designed with the considerations of cooperative users’ differential service qualities and their dual identity (they can be treated as data sellers as well as partners of requestors). The incentive mechanism can spur and select appropriate users to complete data downloading tasks under multi-task situation. The simulation experiment shows that compared with the incentive mechanisms ignoring dual identity of cooperative users, this new incentive mechanism can improve the quality of cooperative service, utility of requestors and social welfare.

incentive mechanism, cooperative downloading, auction theory, task allocation, user selection

10.3772/j.issn.1002-0470.2016.02.004

①國家自然科學基金重點項目(61132001)，國家自然科學基金面上項目(61572476)和青年科學基金(61502457)資助項目。

2015-09-21)

②女，1988年生，博士生；研究方向：無線協(xié)作通信技術，激勵機制；E-mail: chenxiao3310@ict.ac.cn

③通訊作者，E-mail: liumin@ict.ac.cn