摘 要：參與感知系統(tǒng)依賴于移動(dòng)用戶的意愿，使用嵌入或者集成在他們手機(jī)里的各種傳感器，來(lái)參與數(shù)據(jù)的收集和報(bào)告。然而，這個(gè)新數(shù)據(jù)收集范式一直不是很成功，主要是因?yàn)槿狈?duì)參與的激勵(lì)。盡管一些激勵(lì)方案被提出來(lái)，鼓勵(lì)用戶參與，但是沒(méi)有使用位置信息以及強(qiáng)制預(yù)算和覆蓋范圍的約束，我們提出了一個(gè)帶有貪婪算法的重復(fù)性逆向拍賣激勵(lì)機(jī)制，貪婪算法是在給出一個(gè)固定的預(yù)算的條件下，根據(jù)他們的位置選擇一個(gè)代表性的用戶子集。與現(xiàn)有機(jī)制相比，我們的激勵(lì)方案改善了超過(guò)60%的覆蓋面積，每一輪后獲得了一個(gè)更有代表性的樣本集，而在系統(tǒng)中卻保持同樣數(shù)量的活躍用戶并且支出同樣的預(yù)算。

關(guān)鍵詞：逆向拍賣；預(yù)算最大覆蓋問(wèn)題

中圖分類號(hào)：TP212

參與感知系統(tǒng)依賴于手機(jī)用戶感知和傳遞數(shù)據(jù)收集實(shí)體感興趣的變量測(cè)量值，這個(gè)數(shù)據(jù)收集實(shí)體負(fù)責(zé)監(jiān)控或解決一個(gè)特定的問(wèn)題。鑒于大量手機(jī)用戶，PS系統(tǒng)今天有能力從不可能的地方獲得大量數(shù)據(jù)并且解決大規(guī)模社會(huì)問(wèn)題，一個(gè)典型的PS系統(tǒng)例子，包括感知和報(bào)告空氣的質(zhì)量測(cè)量來(lái)評(píng)估一個(gè)特定城市、縣、州甚至整個(gè)國(guó)家的污染。

通常回報(bào)參與者和保證他們的參與使用的是基于逆向拍賣的方法。我們?cè)谶@里也使用這種方法。逆向拍賣的優(yōu)點(diǎn)是：它們包括逆向拍賣的參與者出售他們的感知采樣并且拍賣商通常購(gòu)買最便宜的m商品，減少系統(tǒng)工作的維護(hù)成本。缺點(diǎn)是：在逆向拍賣中用戶可能退出系統(tǒng)，從而破壞整個(gè)系統(tǒng)，因此必須包含特定的機(jī)制來(lái)避免這種情況的發(fā)生。

在本文中，我們把逆向拍賣動(dòng)態(tài)價(jià)格與招募機(jī)制（RADP-VPC-RC）結(jié)合在貪婪最大預(yù)算覆蓋范圍（GBMC）算法中，產(chǎn)生了貪婪激勵(lì)算法（GIA），它是一個(gè)基于反向拍賣的激勵(lì)機(jī)制在給定預(yù)算內(nèi)，不僅包括保留用戶的規(guī)定（條款）還獲得最低成本采樣。

1 基于動(dòng)態(tài)價(jià)格的逆向拍賣機(jī)制（RADP-VPC-RC）

逆向拍賣機(jī)制似乎是一個(gè)吸引人的選擇，分析使用更多的手段來(lái)刺激用戶，隨著實(shí)體（拍賣商）愿意回報(bào)用戶（主動(dòng)競(jìng)購(gòu)者）來(lái)獲得感知數(shù)據(jù)，用戶將通過(guò)競(jìng)爭(zhēng)獲得那些回報(bào)。因此，通常價(jià)格會(huì)隨時(shí)間下降，在這種背景下（拍賣商）支付的回報(bào)是根據(jù)用戶的投標(biāo)價(jià)格來(lái)定的，投標(biāo)價(jià)格是用戶所期望的真實(shí)估價(jià)的總和。也就是說(shuō)，根據(jù)能量、隱私問(wèn)題、時(shí)間等，用戶實(shí)施感知過(guò)程承擔(dān)的成本，再加上額外的保證金，將允許用戶從交易中得到利潤(rùn)。

RADP-VPC-RC機(jī)制的優(yōu)點(diǎn)之一是：它給出了一個(gè)虛擬的參與信用vir=vir-1+α（VPC），對(duì)那些在第R輪中拍賣失敗的用戶，這里α是信用數(shù)量。這種方法使投標(biāo)者持續(xù)參與，因?yàn)檫@增加了他們使用的虛擬投標(biāo)價(jià)格bir=bir*-vir而不是真正的投標(biāo)價(jià)格獲勝的機(jī)會(huì)。當(dāng)用戶失敗時(shí)這個(gè)虛擬信用持續(xù)增長(zhǎng)，但是當(dāng)用戶獲勝它便被設(shè)置為零。RADP-VPC-RC的另一個(gè)重要因素是投資回報(bào)（ROI）指標(biāo)，它作為一種標(biāo)準(zhǔn)來(lái)決定用戶何時(shí)正在退出系統(tǒng)。投資回報(bào)公式如下：

（1）

在這里，eir對(duì)應(yīng)于由用戶從i到r輪獲得回報(bào)，pri·ti對(duì)應(yīng)最低的回報(bào)，pri是從第i輪到當(dāng)前第r輪拍賣的參與實(shí)例的數(shù)量，ti作為用戶的真實(shí)估價(jià)，作為用戶的真實(shí)估值，βi作為容忍周期。用戶每輪評(píng)估Sir臨界值。如果低于某一值，然后他們退出系統(tǒng)。此外，RADP-VPC-RC提供了一個(gè)重新加入機(jī)制，它允許拍賣商傳達(dá)最大獲勝價(jià)格φk給退出系統(tǒng)的用戶。用戶根據(jù)這個(gè)價(jià)格重新評(píng)估他們的投資回報(bào)率和可能在下一輪拍賣中返回系統(tǒng)。這個(gè)預(yù)期的評(píng)估ROI如下：

（2）

2 貪婪激勵(lì)算法（GIA）

GIA的算法是RADP-VPC-RC和貪婪預(yù)算最大覆蓋算法的組合。而RADP-VPC-RC解決了高額成本的問(wèn)題并且避免了用戶退出系統(tǒng)，貪婪預(yù)算最大覆蓋算法考慮的就用戶的位置，覆蓋范圍，和拍賣商的預(yù)算約束。把這兩種算法結(jié)合在一起，GIA需要在一個(gè)固定的預(yù)算下，在空間和時(shí)間覆蓋上購(gòu)買采樣。進(jìn)一步說(shuō)，GIA假定不是靜態(tài)用戶，并且包括額外的機(jī)制來(lái)鼓勵(lì)用戶移性更一步擴(kuò)展地理覆蓋范圍。

2.1 幾何覆蓋模型

為了解決覆蓋問(wèn)題，GIA使用如下的幾何磁盤(pán)模型：

（3）

其中d（ui；uj）是傳感器ui和傳感器uj之間的歐氏（歐幾里德）距離，R>0是一個(gè)常數(shù)，它定義了每個(gè)傳感器的覆蓋區(qū)域。事實(shí)上，這個(gè)函數(shù)定義了一個(gè)以u(píng)i為中心以R為半徑磁盤(pán)，在這樣一個(gè)磁盤(pán)里的所有傳感器的覆蓋范圍測(cè)量值為1，也據(jù)是說(shuō)所有這些傳感器被ui所覆蓋，另一方面，在磁盤(pán)外面的所有傳感器有一個(gè)為0的覆蓋測(cè)量值，也就是說(shuō)不被這個(gè)傳感器所覆蓋。

2.2 幾何模型和拍賣模型的關(guān)系

對(duì)于GIA算法的采樣購(gòu)買的主要特征之一，在于RADP-VPC-RC拍賣方案的修改。這個(gè)拍賣機(jī)制是在成本的遞增順序中購(gòu)買k單位。在我們的方案中，在實(shí)行這個(gè)過(guò)程之前我們使用幾何覆蓋模型來(lái)描述。在這里，每一個(gè)傳感器被繪制成以他的位置為中心半徑為R的磁盤(pán)。當(dāng)然，每一個(gè)傳感器至少以他們自己為中心的磁盤(pán)所覆蓋。這里的問(wèn)題是：是否存在一個(gè)它們的聯(lián)合覆蓋所有點(diǎn)的磁盤(pán)子集合，如果我們指定被disk，覆蓋元素設(shè)定為集合Si，i從1……n，其中n是磁盤(pán)的數(shù)目，前面的問(wèn)題成為著名的NP-Complete Set Cover Problem。

2.3 預(yù)算

在大多數(shù)以前的工作中作出的主要假設(shè)之一是，以一個(gè)無(wú)限的預(yù)算來(lái)運(yùn)行拍賣。這種假設(shè)在實(shí)踐中是不現(xiàn)實(shí)的，因?yàn)閿?shù)據(jù)收集器可能有預(yù)算約束。在我們提出的機(jī)制中，系統(tǒng)以有限的預(yù)算運(yùn)行。我們考慮一個(gè)總預(yù)算是被多輪或拍賣的數(shù)量均勻分開(kāi)。然而，如果在每一ri輪結(jié)束時(shí)，被分配到第ri輪的預(yù)算總額沒(méi)有完全用完，把剩余的部分放到ri+1輪。

3 結(jié)束語(yǔ)

本文介紹了貪婪的激勵(lì)算法（GIA），一個(gè)基于位置的逆向拍賣激勵(lì)機(jī)制帶有預(yù)算約束參與感知系統(tǒng)。該算法使用位置提高用戶覆蓋的面積和減少冗余數(shù)據(jù)的集合。仿真結(jié)果表明了GIA算法比RADP-VPC-RC算法的優(yōu)越性，另一個(gè)，反向拍賣機(jī)制產(chǎn)生于文學(xué)。一般來(lái)說(shuō)，GIA算法與RADP-VPC-RC算法相比較來(lái)看，在系統(tǒng)中保持一個(gè)類似數(shù)量的活躍用戶和預(yù)算支出時(shí)，顯示增加區(qū)域范圍高達(dá)64%。

未來(lái)的工作正在進(jìn)行，建立動(dòng)態(tài)新用戶進(jìn)入模型，因?yàn)槿魏我惠喰掠脩舻倪B續(xù)進(jìn)入可能有助于在積極參與者，每個(gè)采樣的公平價(jià)格，預(yù)算約束中找到一個(gè)平衡。我們要調(diào)查使用的博弈論來(lái)進(jìn)一步分析這些系統(tǒng)。我們還在尋找更現(xiàn)實(shí)的模型，來(lái)模擬R和移動(dòng)性的用戶，以及不同的方法來(lái)為不同的用戶建立真實(shí)估價(jià)和投資回報(bào)率。

參考文獻(xiàn)：

[1]汪磊，徐榮.基于兩個(gè)代理人下的激勵(lì)機(jī)制設(shè)計(jì)[J].巢湖學(xué)院學(xué)報(bào)，2012（04）.

[2]楊世旭，段萬(wàn)春，經(jīng)有國(guó).基于服務(wù)成本共擔(dān)契約的電信業(yè)務(wù)代理商激勵(lì)機(jī)制[J].系統(tǒng)工程，2013（01）.

作者單位：黑龍江中醫(yī)藥大學(xué)佳木斯學(xué)院，黑龍江佳木斯 154007；哈爾濱工程大學(xué)，哈爾濱 150006