陳 曉 劉 敏 周雅琴 李忠誠

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

?

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

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

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

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

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

0 引 言

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

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

1 相關(guān)工作

1.1 協(xié)作下載應(yīng)用

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

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

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

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

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

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

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

2 系統(tǒng)模型

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

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

候選協(xié)作用戶對數(shù)據(jù)內(nèi)容的模糊興趣和進行協(xié)作服務(wù)的成本參數(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ù)自身對任務(wù)集合的興趣Δi={δiτ1,δiτ2,…,δiτ}確定自己意愿完成的任務(wù)集合Ti?T。成本參數(shù)是表示協(xié)作用戶完成任務(wù)所需要消耗的成本[16]。候選協(xié)作用戶ai的成本參數(shù)βi(βmin≤βi≤βmax)越大，表示ai完成任務(wù)的成本越高，完成任務(wù)的能力越低。本文假設(shè)ai的βi是隨時間變化的。

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

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

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

3 多任務(wù)場景的激勵機制設(shè)計

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

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

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

(1)

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

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

(2)

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

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

(3)

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

(4)

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

?iτk=δiτkbiτk

(5)

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

(6)

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

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

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

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

(8)

(9)

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

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

4.2 保證投標(biāo)價格真實

定理1.[19]當(dāng)拍賣機制滿足以下兩個性質(zhì)后，該拍賣機制能保證投標(biāo)價格真實性：

(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機制能保證投標(biāo)價格真實。

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

4.3 計算高效

5 實驗和性能分析

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

5.1 對比算法及評價指標(biāo)

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

(12)

(13)

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

5.2 實驗設(shè)計

候選協(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)分布的標(biāo)準(zhǔn)差σ設(shè)為0.15。本文假設(shè)協(xié)作用戶對數(shù)據(jù)τk的興趣等于對數(shù)據(jù)所屬主題Iτk的興趣，即δiτk=δiIτk。

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

(15)

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

(16)

表1 參數(shù)設(shè)置

5.3 多任務(wù)場景的實驗結(jié)果分析

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

圖1 請求用戶獲得平均服務(wù)質(zhì)量Q1的比較

圖2 請求用戶獲得平均服務(wù)質(zhì)量Q2的比較

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

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

圖4 平均任務(wù)集合完成比例的比較

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

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

圖6 平均社會福利的比較

6 結(jié) 論

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

雖然本文的激勵機制是針對移動設(shè)備的數(shù)據(jù)協(xié)作下載應(yīng)用而設(shè)計的，但該激勵機制也可以應(yīng)用到其他領(lǐng)域中，如延時容忍網(wǎng)絡(luò)(delay tolerant networks，DTN)和眾包應(yīng)用中。只要滿足請求用戶發(fā)布的任務(wù)對協(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] 劉樹林, 邱菀華. 多屬性決策基礎(chǔ)理論研究. 系統(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

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

2015-09-21)

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

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