王 忱

（南京郵電大學，南京 210003）

1 研究背景

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當ib≠P時

當ib=P時，

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

當ib=P時，對于其他i≠P的項有：

當ib=P時，對于其他i = P的項有：

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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