王 忱

（南京郵電大學(xué)，南京 210003）

1 研究背景

利用移動設(shè)備進(jìn)行信息感知，即移動群智感知，可以融合人的主動感知能力和設(shè)備豐富的傳感器資源，因而具有信息種類豐富、感知水平高和部署成本極低的優(yōu)勢，將成為5G的重要業(yè)務(wù)之一。群智感知是智慧城市的一個重要的解決方案。例如，群智感知會方便政府部門監(jiān)測河流污染狀況。監(jiān)測任務(wù)會通過基站定期向河流覆蓋區(qū)域進(jìn)行發(fā)布，用戶隨后可以上傳反映河水水質(zhì)和周圍工業(yè)情況的照片，服務(wù)器在收集到所有用戶的感知信息后，通過一定的檢測算法確定污染情況和污染源。

由于用戶參與群智感知需要花費一定的網(wǎng)絡(luò)流量、設(shè)備電量、交通成本甚至機(jī)會成本，因此需要設(shè)計一定的群智感知激勵機(jī)制，主要包括拍賣、信譽(yù)和定價三種方式。由于定價機(jī)制具有客觀性和直接性，近來越來越多的學(xué)者聚焦在定價激勵機(jī)制的研究上。例如，文獻(xiàn)[1]將定價機(jī)制用于指紋定位系統(tǒng)。文獻(xiàn)[2]將基于用戶參與感知概率的定價機(jī)制用于車輛系統(tǒng)中。文獻(xiàn)[3]和[4]在服務(wù)器有限預(yù)算背景下，基于到任務(wù)現(xiàn)場的距離成本，設(shè)計了激勵用戶參與感知的定價。文獻(xiàn)[5]和[6]也假設(shè)服務(wù)器的預(yù)算是有限的，并基于Stackelberg博弈設(shè)計了Q學(xué)習(xí)定價機(jī)制，文獻(xiàn)[3]研究了智慧城市背景下的群智感知應(yīng)用，但采用了社會關(guān)系這樣一種單一的激勵方式。本文中，我們基于對智慧城市應(yīng)用的認(rèn)識，假設(shè)服務(wù)器的預(yù)算是一個固定的預(yù)期值，基于Stackelberg博弈研究了多精度群智感知的最優(yōu)定價的存在條件，并設(shè)計了基于Q學(xué)習(xí)的優(yōu)化定價方法，能有效提升算法的用戶適應(yīng)性、成本節(jié)約性和感知安全性。

2 基于Stackelberg博弈的定價收益模型

下面在Stackelberg博弈模型的基礎(chǔ)上，給出本文的定價博弈模型。假設(shè)感知精度i分為P級且表示為i=1，2，...，P，另有i=0表示用戶參與虛假感知，i=-2表示用戶參與未參與感知。首先，服務(wù)器作為帶頭人發(fā)布定價策略，為保證定價的公平性，本文假設(shè)在同一時刻，服務(wù)器付給不同用戶在同一感知精度i上的價格是相同的，均為y（i）。然后，用戶作為跟隨者選擇一定的感知精度i，并付出感知成本，第j個用戶的成本記為

下面分別建立建立用戶端和服務(wù)器端的定價收益模型。在用戶端，考慮用戶進(jìn)行虛假感知時可能給自身帶來收益，則有可能使未參與感知的成本用戶j選擇參與精度為i的感知所期望獲得的收益記為，令和將用戶期望得到的定價記為ey（i），則有：

在服務(wù)器端，由于服務(wù)器存在評估錯誤概率e，服務(wù)器只能認(rèn)為評估后的感知精度才是服務(wù)器的收益，且評估后的虛假感知會被服務(wù)器自動舍棄，因而帶給服務(wù)器的收益為0。因此，如果用戶j選擇的感知精度為i，服務(wù)器經(jīng)評估后得到的收益為：

服務(wù)器在所有M個用戶可能參與的群智感知任務(wù)中獲得的總收益記為us，可表示如下：

3 多精度群智感知的最優(yōu)定價存在條件

首先討論單個用戶參與的情況，從用戶收益最大化出發(fā)，若要使該用戶選擇感知精度i，則用戶收益應(yīng)大于用戶選擇其他精度、不參與感知和參與虛假感知等情況。據(jù)此可以不加證明地得到如下的引理。

引理1：對于參與多精度群智感知的某一個特定用戶j，激勵他選擇精度為的感知的充分必要條件是：

根據(jù)上述引理得到 ey（i）后，可以根據(jù) ey（i）與 y（i）的關(guān)系得到 y（i）。

對于某一特定用戶，最優(yōu)定價應(yīng)是使用戶參與某種非虛假的感知、且服務(wù)器收益最大的定價。為使最大化，應(yīng)使 ey（i）大于且盡可能地接近，這樣能得到最大值的如下表達(dá)式：

因此，應(yīng)激勵用戶選擇的精度i應(yīng)使得最大。結(jié)合引理1，可以不加證明地得到如下的引理：

引理2：對于參與多精度群智感知的某一個特定用戶j，最優(yōu)定價應(yīng)激勵用戶選擇使最大的精度i0，且定價應(yīng)滿足如下的充分必要條件：

這里假設(shè)定價是離散的，且最小單位是0.01。

接下來討論所有M個用戶參與多精度群智感知的情況。若要使用戶選擇精度不小于i的感知，且服務(wù)器期望得到的總感知精度為U，從用戶收益最大化出發(fā)，若要激勵不少于個用戶選擇精度不小于i的感知，則這些用戶的收益應(yīng)大于選擇其他精度、不參與感知和參與虛假感知等情況。據(jù)此可以不加證明地得到如下的定理。

定理1：對于參與多精度群智感知的所有M個用戶，假設(shè)可以將用戶按他們在感知精度i上的成本從小到大排序為，若要激勵不少于個用戶選擇精度不小于i的感知，則定價應(yīng)滿足如下的充分必要條件：

若服務(wù)器期望從所有M個用戶得到的總感知精度為U，最優(yōu)定價應(yīng)是使用戶參與某種非虛假的感知、且服務(wù)器收益最大的定價。根據(jù)引理2，最優(yōu)定價過程即尋找所有M個用戶中感知精度與成本差最大的感知精度及其對應(yīng)用戶，與此同時，應(yīng)使ey（i）大于且盡可能地接近。據(jù)此可以證明得到如下的定理。

定理2：對于參與多精度群智感知的所有M個用戶和P個感知精度，假設(shè)可以將從大到小排序，并取出最大的n項為，對應(yīng)的感知精度和i1+i2+...+in等于U，而這n項中最小的一項對應(yīng)的感知精度和用戶成本分別為ib和Cb。則最優(yōu)定價可有下面的線性定價形式：

當(dāng)ib≠P時

當(dāng)ib=P時，

證明：根據(jù)假設(shè)條件，不論ib是否等于P，上面的期望價格ey都可以補(bǔ)償選出的n個凈收益最大項所對應(yīng)的成本。對于其他項，我們有。然后，當(dāng)ib≠P時，對于其他ib≠P的項有：

當(dāng)ib=P時，對于其他i≠P的項有：

當(dāng)ib=P時，對于其他i = P的項有：

因此，除了選出的n項，這些用戶將不會選擇其他感知精度，而且其他用戶也不會選擇任何感知精度或參與虛假感知。

4 不完全信息條件下的動態(tài)定價算法

在大多數(shù)智慧城市的應(yīng)用場景中，潛在的感知用戶數(shù)量及其感知成本都會隨時間變化，可記為M（t）和。因此不能簡單根據(jù)上面的最優(yōu)定價方法來確定群智感知的定價。此時定價過程應(yīng)該服從如下的動態(tài)定價過程：（1）在系統(tǒng)測試階段，發(fā)布一個隨機(jī)的定價，測試用戶的選擇；（2）服務(wù)器根據(jù)用戶的選擇，決定定價的滑動方向和滑動步長，該步驟會被迭代重復(fù)，直到定價趨于穩(wěn)定；（3）在系統(tǒng)運行階段，根據(jù)現(xiàn)場用戶的響應(yīng)再次動態(tài)調(diào)整定價。

根據(jù)上述討論，該動態(tài)定價過程可以用Q學(xué)習(xí)算法來完成。Q學(xué)習(xí)是強(qiáng)化學(xué)習(xí)的一種，它有狀態(tài)（state）、動作（action）、獎賞（reward）這三個要素。Q為動作效用函數(shù)，每個狀態(tài)所對應(yīng)的動作都有一個效用值。Q學(xué)習(xí)的訓(xùn)練公式如下：

其中，學(xué)習(xí)速率α越大，保留之前訓(xùn)練的效果就越小；折扣因子λ越大，記憶中的利益所占比重就越大。在定價學(xué)習(xí)過程中，從每個定價狀態(tài)出發(fā)，只可能有增或減兩種動作，分別表示為αr和αι，動作的獎勵應(yīng)為i（t+1）/（t+1）。我們現(xiàn)在令α=1，提出基于Q學(xué)習(xí)的滑動定價算法SPA，其過程如下：

（1）初始化及滑動區(qū)間的設(shè)定：固定虛假感知的期望價格為-1，而完全精度感知的期望價格ey（p）從最低定價0開始滑動，滑動范圍從最低定價0到最高定價p-0.5e，單步滑動步長固定為最小值0.01，當(dāng)ey（p）滑動至1-0.5e之后，ey（p-1）從0開始與ey（p）同時滑動，且總與ey（p-1）保持1-0.5e的差距。以此類推，當(dāng)ey（2）滑動至1之后，ey（1）從0開始與ey（2）...ey（p）同時滑動，且總與ey（2）保持1的差距。

（2）滑動定價過程：將當(dāng)前期望價格向用戶群體中的某隨機(jī)抽取的用戶進(jìn)行發(fā)布，如果該用戶選擇精度為的感知，則當(dāng)前期望價格向量ey的獎勵值增加i。如果當(dāng)前所有價格的平均獎勵值（即獎勵值與被測試次數(shù)的比）大于或等于NU/M（N為當(dāng)前測試過的總?cè)藬?shù)），則當(dāng)前所有不為0的價格向低滑動一次，反之則向高滑動一次。如果該用戶參與虛假感知，則進(jìn)一步降低虛假感知的定價。對該步驟迭代進(jìn)行M次。

（3）定價選?。簭漠?dāng)前穩(wěn)定價格的下方選擇平均激勵值大于或等于U的最低用戶期望價格組合。然后可以根據(jù)ey與y的關(guān)系得到y(tǒng)。

下面對該算法的性能進(jìn)行仿真。首先驗證算法的收斂性。我們假設(shè)用戶的感知成本服從均勻分布，圖1展示了在服務(wù)器評估錯誤概率為0.1、N/M=0.1的條件下，定價誤差絕對值和服務(wù)器平均收益隨學(xué)習(xí)次數(shù)增加的性能變化情況：由于平均獎勵值利用了歷史標(biāo)簽數(shù)據(jù)，之前在當(dāng)前價格上每次測試得到的用戶感知精度都會反饋影響到當(dāng)前價格的滑動方向，該算法收斂速度較快。由圖1可以看到，達(dá)到穩(wěn)定價格的學(xué)習(xí)次數(shù)與定價間隔數(shù)接近，而服務(wù)器的平均收益隨著學(xué)習(xí)次數(shù)增加而增加，最終穩(wěn)定在期望平均收益附近。

圖1 感知成本服從均勻分布時SPA算法的性能

此外，我們還試驗了用戶的感知成本服從高斯分布的情況，算法的性能與均勻分布的情況十分類似，仿真結(jié)果如下圖所示：

圖2 感知成本服從高斯分布時SPA算法的性能

綜合圖1和圖2可以看出，我們提出的滑動定價算法具有用戶適應(yīng)性、成本節(jié)約性和感知安全性。

5 結(jié)束語

本文提出了面向智慧城市應(yīng)用的群智感知模式，即固定價值的多精度群智感知，并基于Stackelberg模型建立了定價收益模型。隨后在完全博弈信息條件下，在考慮了服務(wù)器評估錯誤概率的基礎(chǔ)上，得到激勵用戶選擇某種精度感知的定價存在區(qū)間，并得到了使虛假感知最少和服務(wù)器收益最大化的最優(yōu)定價。然后在感知成本位置的不完全信息條件下，基于Q學(xué)習(xí)設(shè)計了滑動定價算法SPA。隨后通過仿真驗證了算法的用戶適應(yīng)性、成本節(jié)約性和感知安全性。