Kai H , He H , Jun L . Quality-Aware Pricing for Mobile Crowdsensing[J]. IEEE/ACM Transactions on Networking, 2018:1-14.

簡介

移動群智感知被認為是大規模城市數據收集的一種有前景的方法，但也帶來了新的挑戰性問題，如激勵和質量控制。如何在群智感知系統中設置“正確”的價格的基本問題仍然存在。在本文中，我們研究了移動群體感知的質量感知定價問題，我們的目標是選擇合適的發佈價格來招募具有合適感知質量的一組參與者，以實現穩健的群體感知，同時最小化總預期支付。我們的問題是NP-hard的，並且與泊松二項分佈（PBD）密切相關。為了解決我們的問題，我們首先發現PBD的一些新的子模塊屬性，然後提出一種新的“熨燙方法”，通過影響新發現的PBD屬性將我們的問題從非子模塊優化問題轉化為子模塊優化問題。最後，通過熨燙方法，提供了幾種具有可證明的性能比的近似算法，並且還進行了廣泛的數值實驗以證明我們的方法的有效性。

介紹

隨著手持設備（如智能手機）和嵌入其中的各種移動傳感器的激增，人們越來越關注移動群智感知（MC）。我們最近目睹了MC系統在各個領域的蓬勃發展，例如醫療保健，環境監測，運輸和人類活動檢測。雖然MC被認為是一種有前途的感知數據收集方法，但移動群智感知也帶來了一些獨特的研究挑戰。由於MC任務的參與者（或用戶）必須付出大量人力物力用於感知活動，因此在激發參與者的行為的同時需要適當的經濟補償（即確保真實性）。此外，由於MC參與者在他們的傳感設備和他們的感知行為通常是不專業的（導致低感知質量），從單個參與者獲得的感知數據可能是嘈雜的甚至是無用的。這使得明智的MC任務所有者有必要選擇具有合適感知質量的適當參與者以及引入感知冗餘（即形成“人群”）以實現感知穩健性，這最終將使所有者從收集的數據中獲得更高的利益。實際上，在數據採集和分佈式計算的許多眾包應用中強烈要求提高對傳感魯棒性的要求。

基於上述觀察，感知任務所有者需要設計適當的激勵機制以進行穩健的群體感知。實際上，即使沒有考慮到感知質量問題，設計真實群眾激勵機制也是非常重要的。大多數先前的研究都是基於拍賣來解決這個問題，即所有者向用戶徵求密封投標，然後決定向每個用戶付款。但是，由於用戶可能不信任所有者並理解其真實成本的機制，因此實施此方法可能會很複雜。此外，密封投標可能導致對用戶的異種支付（也就是“價格歧視”），這可能引起人們的不滿。因此，一種更適用的方式可能是發佈定價，即感知所有者向參與者宣佈一個價格以進行眾包活動，然後參與者根據自己的意願選擇加入活動或不加入。許多當前的商業眾包系統採用了公佈定價方法來激勵參與。

儘管公佈定價是當前的主流方法，但如何設定“正確”價格以招募具有合適質量（和成本）的人群的基本問題仍然存在。直觀地說，如果公佈的價格設定得太低，可能會有太少的參與者願意加入這項任務，從而損害最終感知的穩健性。如果盲目地提高定價，那麼所有者可能招募大量用戶以實現感知穩健性，但是它會浪費資金在質量非常差的參與者上。 據我們所知，文獻中從未研究過招聘成本與移動人群感知中的感知穩健性之間的這種權衡。

A.貢獻

在本文中，我們提出了一種新的事前發佈定價機制，以實現移動人群中的感知穩健性。我們的目標是選擇適當的定價和一組候選參與者，以便最小化支付給參與者的總預期成本，同時招募的具有合適感知質量的參與者的數量大於預定的下限（ 在概率意義上）以保持所需的感知魯棒性水平。我們將這個問題稱為Posted Pricing for Robust Crowdsensing（PPRC） ，並提出了幾種算法來解決它具有可證明的性能界限。

由於PBD經常出現在各種研究主題中，包括眾包，多傳感器融合，模式識別和計量經濟學，我們對PBD子模塊屬性的發現可能有助於解決其中的相關優化問題。其次，我們對“熨燙方法”的想法可以為子模塊優化提供新的視角，並且有可能將應用於非子模塊優化問題轉換為子模塊優化問題的其他場景。

問題設置

在本節中，我們正式介紹了我們問題的假設和定義。為清楚起見，我們列出了經常使用的符號含義。假設我們有一個群眾感知任務和一組有資格完成任務的n個參與者。每個參與者具有私人類型（q_i，c_i），其表示如果參與者將參與群體感覺任務，則將以成本c_i產生質量q_i的輸出。在進行了大量關於眾包的工作之後，我們考慮一個標準的貝葉斯環境，其中關於用戶質量和成本的“貝葉斯”知識是可用的，即：每個用戶類型（q_i，c_i）的聯合概率分佈對於眾包任務所有者是已知的，但q_i和c_i的確切值是未知的。為了接近現實情況，考慮到用戶的異構行為和感知能力可能遵循不同的分佈函數，假設不同用戶的類型是獨立分佈的。

由於用戶通常在參與群智感知時將其感知成本貨幣化，我們假設有一組有限的候選價格，任務所有者可以從中選擇發佈給參與者的價格。如果用戶的質量太低，他輸出的數據可能只是噪音而對任務所有者來說是無用的（或者由於誤導甚至是有害的）。我們將這樣的用戶稱為“臨時用戶”，否則稱為“普通用戶”。基於這種觀察，所有者將設置下限為任何用戶的最低質量需求。為了保證傳感數據的整體質量，有必要要求多個用戶參與任務，以便通過融合多組數據來減少測量誤差。因此，我們通過要求至少k個普通用戶必須加入群智感知任務，群眾感知任務被作為任務所有者的預定義需求來感測魯棒性。

基於上述考慮，任務所有者可能盲目地向所有用戶發佈非常高的價格，招募大量參與者以實現穩健性，但這屬於“過度支付”。 因此，一個更精明的任務所有者會仔細選擇一組目標用戶併為他們提供“足夠”的發佈價格，這樣至少k個普通用戶最終會加入任務（在概率意義上），而總數（預期）支付所選用戶的費用最小化。

定義1：給定一組用戶users{1,2，...，n}，一組公佈的價格W = {w1，...，wσ}，閾值（k，θ）∈[n]×（0，1），集合P={(u_i，l, p_i，l)|i ∈ [n], l ∈ [σ]} 。魯棒群體發佈的定價（PPRC）問題是找到以下數學優化問題的最優解：

備註：PPRC問題的表述意味著我們只向一組目標用戶（即X中的用戶）發佈價格，以便在質量約束下可以最小化總預期支付。

A.仔細研究問題

根據我們的問題公式，可以看出PPRC問題中出現的隨機變量S_l（X）遵循泊松二項分佈。 泊松二項分佈是眾所周知的獨立伯努利試驗之和的離散概率分佈，其不一定是相同分佈的，並且存在其p.m.f的精確表達式。更具體地說，如果我們使用Fⁱ_X來表示可以從X⊆[n]中選擇的i個整數的所有子集的集合，我們得到以下等式：

如果我們將上述等式輸入到定義1中的PPRC問題中，我們將得到非線性0-1整數規劃問題，這通常很難解決。實際上，我們發現PPRC問題是NP-hard的。

定理一：PPRC問題是NP-hard的。

解決我們問題的另一個想法是看看ρl（·，k）是否是子模塊，所以我們可以應用一些子模塊優化技術。

熨燙方法

定理2：給定兩組X，Y和兩個整數a，b滿足X⊆Y⊆[n]和0≤a≤b≤n且a≤| X |，我們得到

根據上述定理，我們現在更接近於解決我們的問題，因為我們已經證明lnρ_l（·，k）=lnΓ_l（·，k，n）是域{X|X ⊆ [n] ∧ |X| ≥ k}的子模塊。 但是，我們仍然不能使用現有的子模塊優化算法來解決我們的問題，因為：

（1）lnρ_l（X，k）是負的;

（2）lnρ_l（X，k）在| X |< k（ρ_l（X，k）=0）時沒有定義。

因此，我們進一步設計了兩個替代子模函數Ψ_l和φ_l，它們在2 ^[n]上定義，並且對於任何l∈[σ]與函數ρl對齊。 直觀地，這些替代函數在不損害PPRC問題的最優解的最優性的情況下產生將非子模函數ρl“鐵”化為子模函數的效果，因此使我們能夠將PPRC問題轉換為子模塊優化問題。 我們稱這種方法為“熨燙方法”，並將在下面詳細描述。

A. PBD的一般代理函數

我們首先提出一個子模函數Ψ_l（如定理4所示），它作為任意PBD的一般代理函數，因此它也可以應用於其他相關的優化問題。函數Ψ_l不僅在2 ^[n]上是非負的和子模塊的，而且還具有Ψ_l在{X：| X | 1}上達到其最小值的良好屬性。當Γ_l（X，μ₁，μ₂）= 0，對於具有| X | 1的任意X，Ψ_l與Γ_l對齊。

定理4：給定任何l∈[σ]和任意兩個整數μ₁，μ_2，滿足0 1≤μ₂≤n，令δ_l= min {Γ_l（X，μ1，μ2）|X⊆[n]∧| X|≥μ₁}定義

如果α_l≥-2lnδ_l，那麼我們就有了

1）Ψ_l（·，μ1，μ2）是非負和子模塊函數在2 ^[n]上定義。

2）對於任何X₁，X₂⊆[n]，使得| X₁ | 1和| X₂ |≥μ₁，我們有Ψ_l（X₁，μ₁，μ₂）≤Ψ_l（X₂，μ₁，μ₂）

設（S1，S2,....,Sn）是滿足p_s1,l ≤ p

由於定理4已經證明Ψ₁是在2 [n]上的子模塊，可以看出[PPRC0]問題對於任何給定的l基本上都是“子模塊覆蓋”問題。

B. PPRC問題的進一步轉變

雖然我們已經證明原始的[PPRC]問題可以轉化為子模塊覆蓋問題[PPRC0]，但我們仍然無法用可證明的界限來解決它，因為解決子模塊覆蓋問題的現有技術通常需要額外的條件。據我們所知，Wan等人提出瞭解決非整數子模塊覆蓋問題的最佳性能（如我們的例子），但僅適用於某些特殊的子模塊功能。我們引用其結果：

定理5：設F是在2^G上定義的非負單調子模塊函數。如果F（∅）= 0，那麼這樣的F稱為多面體函數。假設Yopt是子模塊的最優解，覆蓋問題和cst（Yopt）是Yopt的成本。假設Yopt是子模塊覆蓋問題的最優解決方案，而cst（Yopt）是Yopt的成本。如果F（Yopt）= F（G）≥cst（Yopt）並且貪婪算法總是選擇x∈G\ X，使得當F（X）

注意，我們有G = [n]，並且[PPRC0]中的成本函數是模塊化的。 然而，定理5要求F（Yopt）= F（G）≥opt和F（x | X）≥cst（x）以獲得對數比。 為了應用定理5，我們基於Ψl為任何l∈[σ]設計新的代理函數φl，並證明函數φl滿足定理5中所需的所有條件。之後我們得到定理6：

使用代理函數φl，我們可以進一步將[PPRC0]問題轉換為以下[PPRC1]問題：

由於定理6證明函數φ_l滿足定理5中所需的條件，我們可以基於定理5設計[PPRC1]的算法以實現可證明的近似比。但是，[PPRC1]需要知道opt_l（也是[PPRC0]的最佳解決方案），這是不易得知的。

近似算法

首先我們需要證明[PPRC1]是否等同於[PPRC]，我們找到以下定理：

定理7：給定任何l∈[σ]，如果[PPRC]和[PPRC1]不相等，那麼我們可以在多項式時間內找到[PPRC]的最優解。

在定理5-7中，直接的方法是在貪婪算法中直接使用φ_l來求解[PPRC1]，如算法1所示。

對於每個l∈[σ]，算法1首先根據定理7嘗試找到[PPRC1]的最優解 ，如果找不到最優解，它使用貪婪策略找到近似解（第7-11行）。 算法1輸出的最終解決方案是尋找所有l∈[σ]的最小成本（第12-13行）。不幸的是，由於opt

因此，我們可以放棄φ_l並獲得算法1所示的算法1等效算法2。

可以看出，算法2與第7-13行中的算法1不同，它首先將具有最小預期成本的k-1個用戶添加到結果集中（第7行）。之後，該算法逐個添加用戶，每次選擇“增量貢獻”與其成本的比率最大的用戶（第9和12行）。有趣的是，當選擇第k個用戶時，該算法使用lnmin {ρl（X∪{x}，k），θ} +αl來計算增量貢獻（第9行），其中αl可以被理解為k-1個的用戶的估計貢獻。使用定理5-7，我們可以很容易地得到：

定理8：算法2對PPRC問題的近似比最多為

接下來，我們分析算法2的時間複雜度。算法2的第3行中的排序過程在最壞的情況下花費O（n²）運行時間。在第7-13行的執行過程中，我們為每個i∈[k]維持ρ（X，i）的值。 當X在第7行初始化時，我們可以使用Eqn在O（n²）時間內計算所有i∈[k]的ρ（X，i）。第7-13行的總時間複雜度最多為O（n² + n（n + k））= O（n²）。 第3-15行的時間複雜度由第3行和第7-13行的時間複雜度決定，而第3-15行最多執行σ次。 因此，算法2的總時間複雜度最多為O（n²σ）。

雙標準近似算法

在本節中，我們考慮質量約束（即等式（1））與PPRC中的總預期支付之間的權衡，並提出雙標準近似算法來解決我們的問題。 我們在定義3中闡明瞭“雙標準近似”的概念：

基於定義3，我們提出了PPRC的雙標準近似算法，如算法3所示。

在算法3中，我們使用Ψ_l作為ρl（∀l∈[σ]）的替代函數，並使用貪婪搜索處代替算法1中的處理。然而，我們將貪婪搜索過程的停止規則從φ₁（X）l（X，k，n）1（在算法3的第9行中示出）。這種修正是因為PPRC的雙標準近似解決方案中的寬鬆質量要求，並且參數η和ε1根據定義3和定理4中的Ψ

我們可以證明算法3的近似比，它由定理9表示。

定理9：對於任何ε∈（0，θ），算法3向PPRC問題輸出

雙標準近似解。

處理未知分佈情況和多個任務

在本節中，我們概括了我們處理用戶未知分佈情況和多個同質群智感知任務的方法。 更具體地說，我們假設存在以在線方式獲得的T個同質群智感知任務，並且從獲得了針對不同任務的任何用戶i∈[n]的感知質量和成本。 在這種情況下，我們的問題變成了“學習動態定價（LDP）”問題，其中任務所有者必須找到針對任何任務t∈[T]的PPRC問題的近似解（Xt，lt）， 觀察和學習用戶對過去處理的任務的行為（即任務1，...，t-1）。

當用戶的分佈未知時，任務所有者為任何任務t選擇的元組（Xt，lt）可能違反PPRC問題中的質量約束（即，等式（1））。因此，我們引入懲罰函數Q（·）來模擬由於違反等式（1）而導致的任務所有者的損失，其中Q（·）可以是滿足

的任何非遞減函數.基於此懲罰函數，我們進一步定義PPRC問題的任何解（X，l）的總損失如下：

我們定義了定義4：

根據定義4，我們設計了算法4：

效用評估

我們進行了廣泛的數值實驗來評估算法的性能。我們的實驗目的是證實我們的算法在不同參數設置（如θ，n和k）下的有效性。為了模擬用戶在移動眾包中的類型，我們生成各種二元分佈，包括二進制正態分佈，指數分佈和均勻分佈，作為用戶質量和成本的先驗知識，任何兩個不同的用戶的類型遵循不同的分佈。將所有生成的分佈截斷為具有支持[0,1]×[0,1]，並且從（0,1）中隨機採樣生成每個雙變量分佈的相關係數，以模擬參與者質量之間的正相關性。在不失一般性的情況下，我們將γ= 0.1設置為任何用戶的最低質量需求，並將W = {0.1,0.2，...，0.9}設置為候選價格的集合。

在我們的實驗中，我們實現算法2，算法3和算法4用於比較，並且它們分別由我們的圖中的“PRC”，“CAA”和“DP”表示。 BCAA中的輸入參數ε設置為ε=θ/ 3。 我們還實現了EXACT算法作為基準，通過枚舉[n]的所有子集找到PPRC問題的最優解。 由於BCAA和LDP都可以輸出僅近似滿足等式（1）的解，因此當違反PPRC問題中的等式（1）時，我們使用線性罰函數Q（x）= x來測量任務所有者的損失。 除非另有說明，否則我們在實驗中將懲罰因子設置為50。 利用該懲罰函數，在我們的比較中使用等式（6）中定義的總損失L（X，l）作為度量。

由於EXACT具有指數時間複雜度，我們首先將PPRC，BCAA和LDP與圖中大量人群的情況在圖1-3進行比較，其中報告的數據是超過1000個數據集（1000個任務）的測試算法的平均總損失（ATL）。

在圖1中，我們研究了實現的算法的性能如何受到用於控制所選用戶質量的閾值的影響。最終我們得到結論，需要選擇更多用戶以滿足更大θ的等式（1）。

在圖2中，我們將人群的大小從1500縮放到3500，每個子圖中增加200，並且k和θ的值也變化，可以看出PPRC優於其他算法。 此外，當n增加時，PPRC和BCAA輸出的ATL都減少，這可以解釋為當人群規模增加時用於選擇用戶的搜索空間擴大，因此可以發現具有較小成本的組滿足質量需求。最後，可以看出LDP的ATL隨著n增加，因為在LDP的“探索階段”中發生的總損失隨著人群規模而增加。

在圖3中，我們通過在n，k和θ的不同設置下將懲罰因子從10縮放到100來研究所實現的算法的性能。 可以看出，所實現的算法的相對性能類似於圖1中的相對性能，而與懲罰因子的變化無關。此外，圖3顯示，PPRC的ATL不受影響，而LDP和BCAA的ATL增加。這是因為LDP和BCAA都有可能輸出違反約束條件（1）的解決方案，而PPRC則不會。

在圖4中，我們將任務數量從100擴展到1000並測試PPRC和LDP的ATL，並且n，k，θ的值分別設置為500,100和0.2。可以看出，當T增加時，LDP的性能逐漸接近PPRC。

需要注意的是，EXACT或PPRC的總損失等於PPRC問題的優化函數的值（即，總預期成本），因為這兩個算法的輸出總是滿足等式（1）。因此，我們比較EXACT和PPRC，以瞭解PPRC的解決方案輸出的最優性。由於EXACT具有指數時間複雜度，我們必須在人群規模較小的情況下比較PPRC和EXACT，結果如圖5所示。

在圖5中，我們在k和θ的不同設置下縮放n的值。每個數據點是50多個數據集的模擬結果的平均值。從圖5中可以看出，當n增加時，EXACT和PPRC的總成本降低。這可以通過類似於圖2的原因來解釋，即，具有較小成本的用戶組可以在具有更多用戶的更大搜索空間中找到。更重要的是，圖5顯示PPRC的性能非常接近於EXACT，而與n，k和θ的變化無關。這證實了我們的算法的有效性。

致謝

本文由南京大學軟件學院2019級碩士吉品翻譯轉述。

閱讀更多 慕測科技 的文章

關鍵字: 分佈式計算 設計 算法