偏好感知的邊云協同群智感知參與者選擇策略

王汝言，劉 佳，何 鵬，崔亞平

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶高校市級光通信與網絡重點實驗室，重慶 400065；3.泛在感知與互聯重慶市重點實驗室，重慶 400065)

近年來，隨著移動智能設備的普及和嵌入式傳感器的發展，移動群智感知(Mobile Crowd Sensing，MCS)[1-3]已經成為一種有效的物聯網數據收集范式。另外，無線通信技術的快速發展[4-5](比如未來B5G和6G移動通信網絡等)使得網絡容量和傳輸速率進一步突破，這將顯著地提高群智感知數據收集的效率。傳統的移動群智感知系統依賴集中式服務器處理來自大量參與者提供的感知數據，在大規模移動群智感知部署情況下，這種體系結構消耗大量計算資源。若集中式服務器遠離感知區域，用戶和服務器間通信則會增加數據和信息傳輸的延遲，這會阻礙移動群智感知下實時數據收集[6]。近年來，隨著移動邊緣計算(Mobile Edge Computing，MEC)技術的發展，結合邊緣計算的移動群智感知架構已經被提出[7]。在移動群智感知中，邊緣節點用于處理移動設備和云服務器之間的數據，用戶實時狀態更新發生在移動設備附近，用戶收集的感知數據由最近的邊緣節點處理，因此可以減少信息傳播和通信時延，有效支持實時的移動群智感知場景[8]。

在大量的用戶群體中，如何選擇最有效的用戶子集作為參與者執行感知任務是移動群智感知面臨的關鍵問題[9-11]。現有工作[12-13]通常從平臺的角度出發選擇參與者完成任務，滿足其不同的優化目標，包括最小化感知成本和用戶移動距離、最大化任務覆蓋等。這種策略沒有考慮用戶感知能力差異。還有部分文獻[14-15]考慮了用戶的社會屬性去選擇參與者，但忽視了用戶對不同任務的偏好這一關鍵因素。在現實中，由于任務的位置、時間、類型等差異，用戶更想要執行自己偏好的任務。不恰當的任務分配使用戶和平臺雙方都不滿意，這在很大程度上影響用戶執行任務的態度和積極性，降低了群智感知系統的性能。這些問題在結合移動邊緣計算的移動群智感知架構下變得更為復雜，參與者選擇過程應該由云平臺和邊緣節點共同執行以發揮各自的優勢。

關于群智感知中的參與者選擇問題，國內外的學者和研究機構已經做了大量研究。文獻[16]考慮多個參與者方面的因素和任務的多維異構性而選擇參與者最大化系統效用，又考慮了任務覆蓋質量和參與者任務完成可能性，但并沒有關注任務預算和感知成本。文獻[17]提出一種多任務分配框架，考慮參與者意向移動和非意向移動，分別為時間敏感型任務和延遲容忍型任務而選擇合適的參與者，最小化移動距離和參與者的數量。文獻[18]提出一種數據質量指導下的激勵機制設計，采用擴展期望最大化算法、最大似然估計和貝葉斯推理評估數據質量，并進一步應用信息論衡量有效數據貢獻，基于數據貢獻獎勵參與者。文獻[19]提出一種服務效益感知的多任務分配策略，首先根據任務困難度、任務歷史、感知能力和感知積極性計算參與者的服務效益，然后通過改進的模糊聚類方法聚類用戶，最后設計了一種梯度下降算法為任務匹配用戶。現有參與者選擇策略往往只能滿足其單一優化目標，而忽視用戶偏好和任務偏好等因素，這些因素對群智感知系統的發展至關重要。

針對上述研究問題，筆者首先在傳統群智感知系統架構下引入移動邊緣計算，提出一種邊云協同的群智感知系統架構，整個感知過程由云平臺和邊緣節點協作執行。然后在此基礎上，針對群智感知過程中的參與者選擇階段提出偏好感知的參與者選擇策略，為任務選擇合適的參與者。云平臺根據任務位置向邊緣節點分發任務，邊緣節點在區域內進行參與者選擇，并將收集的數據上傳到云平臺。考慮用戶和任務雙方的不同偏好，根據任務的時間、位置、類型和獎勵評估用戶對任務的偏好；根據用戶的聲譽和感知成本，評估任務對用戶的偏好。把群智感知中的參與者選擇問題建模為用戶與任務間的穩定匹配問題，通過求解穩定匹配最大化用戶偏好。

1 系統模型

首先提出群智感知系統的工作流程。如圖1所示，移動群智感知系統模型由4部分組成：數據請求者、MCS云平臺、邊緣節點和移動用戶(用戶區域)。數據請求者向MCS云平臺請求數據，MCS云平臺根據請求信息生成一組任務集，根據任務的位置將任務子集發送至區域對應的邊緣節點。邊緣節點向當前區域用戶發布任務消息，區域內想要參與任務的用戶會向邊緣節點發送任務請求。邊緣節點在區域內進行參與者選擇過程，完成用戶與任務間的匹配。最后，邊緣節點接收用戶提交的數據并最終上傳到云平臺。其中，任意兩個節點之間進行的通信和數據流的傳輸需要移動通信技術[20]的支持，保障群智感知系統各個階段的效率。主要研究群智感知中的參與者選擇階段，假設任意節點間可以正常通信，提出合適的參與者選擇策略。

圖1 移動群智感知系統模型

考慮用戶和平臺不同的偏好，如何設計一種參與者選擇策略在保證數據質量的同時使用戶方的偏好最大化，是研究的主要問題。群智感知中的參與者選擇可以看作用戶與任務間的匹配問題，穩定匹配理論在具有雙方偏好的匹配問題中應用廣泛，適用于學生擇校、婚姻匹配等各種場景[21]。在移動群智感知中應用穩定匹配可以充分整合影響用戶和任務偏好的各種因素，并且實現匹配后雙方都能達到穩定狀態。考慮到用戶感知能力受限，假定每個用戶只能完成一個任務；而每個任務需要多個用戶共同完成以確保感知質量。因此，筆者把用戶和任務之間的參與者選擇建模為多對一匹配模型，為每個任務選擇合適的參與者，以用戶偏好最大化為目標求解雙方完全匹配下的穩定匹配。

首先給出用戶ui偏好任務集，記為ι(ui)：

ι(ui)={wj|?j∈[1，2，…，n]} ，

(1)

該集合為一個有序集，集合中的任務按照用戶對任務的偏好γi，j降序排列，集合中的任務數量為n。使用wj?uiwj′表示ui相對于wj′更喜歡wj。

相似地，得到任務wj偏好用戶集，記為ι(wj)：

ι(wj)={ui|?i∈[1，2，…，m]} ，

(2)

該集合為一個有序集，集合中的用戶按照任務對用戶的偏好εj，i降序排列，集合中的用戶數量為m。使用ui?wjui′表示wj相對于ui′更喜歡ui。

下面給出多對一穩定匹配相關定義。

定義1(匹配S)匹配S是用戶-任務對(ui，wj)的集合，S(ui)表示用戶ui在S中的匹配對象，S(wj)表示任務wj在S中的匹配對象。

定義3(不穩定對)給定一個匹配S，在雙方完全匹配中一個用戶ui和一個任務wj組成一個不穩定對(ui，wj)，滿足wj?uiS(ui)并且存在一個子集U′?S(wj)，{ui}?wjU′。

定義4(穩定匹配)如果匹配S中不包含任何不穩定對，那么匹配S為穩定匹配。

所提參與者選擇問題可以描述為：對于邊緣節點管理的區域，首先評估任務所需用戶總數k，然后從用戶集U中選擇k個用戶作為候選用戶Uk，與n個任務構造穩定匹配S，使得穩定匹配S中每個用戶分配任務的用戶偏好最大化。

(3)

其中，S*為所有穩定匹配構成的集合。

2 用戶和任務偏好評估

主要評估用戶偏好和任務偏好的影響因素，邊緣節點根據這些因素量化用戶和任務的偏好。

2.1 用戶偏好

2.1.1 時間因素

時間因素對用戶偏好具有重要影響。群智感知中的任務是有時間約束的，用戶在任務規定的持續時間內任意時刻到達任務地點才能執行任務。如果用戶到達時間超過了任務結束時間，則用戶無法完成感知任務。不同用戶空余時間是不同的，用戶更偏好那些在空余時間內能夠完成的任務。根據任務的持續時間和用戶空余時間，邊緣節點首先計算用戶的有效時間，然后通過用戶執行任務的有效時間與任務持續時間的比例評估用戶ui與任務wj的時間匹配度。分3種情況進行討論：第1種是用戶結束時間為任務持續時間內的某個時刻，此時用戶有效時間為用戶的空余時間；第2種是用戶結束時間小于任務開始時間或用戶開始時間大于任務結束時間，此時用戶有效時間為0；第3種是用戶開始時間小于任務結束時間，但用戶結束時間大于任務結束時間，此時用戶有效時間為任務結束時間與用戶開始時間的差值。用戶ui與任務wj的時間匹配度，記為Ξi，j：

(4)

2.1.2 距離因素

群智感知中的任務是基于位置的。不同任務需要在不同的地點執行，并且不同用戶所處位置也具有很大差異。用戶位置與任務位置間距離越大，用戶需要花費越多的時間到達任務位置執行任務。平臺發布任務時，對每個任務都有一個有效覆蓋半徑Rj，處于任務有效覆蓋半徑的用戶更有可能完成任務。當用戶與任務的位置距離超過有效覆蓋半徑，用戶與任務的距離匹配度隨兩者距離的增大而減小。假設任務存在最大距離Rmax，當兩者間的距離超過最大距離時，認為用戶無法完成任務。邊緣節點根據用戶提交的位置信息以及任務位置計算用戶ui和任務wj的距離匹配度，記為Ψi，j：

(5)

其中，Di，j為用戶位置與任務所處位置間的歐式距離。

2.1.3 任務類型因素

在群智感知系統中，平臺發布任務具有不同的類型。任務大致可以劃分為3大類：環境現象類、基礎設施現象類、社交應用類[1]。不同用戶對不同類型任務具有不同的偏好，用戶往往更想要或者有能力完成其中某一類任務。根據用戶一段時間內完成任務的列表Lui計算用戶對任務wj的類別偏好，其中，Lui中任務wj所屬類型的任務個數越多，用戶ui對該任務wj的偏好越大，記為Ζi，j：

(6)

當wi與wj類型相同時，M(wi，wj)為1，否則為0。

2.1.4 獎勵因素

平臺發布任務時，往往會給出任務的預算。該預算用來彌補用戶感知過程的成本消耗，并激勵用戶積極參與感知任務。在用戶選擇自己偏好任務時，任務獎勵是需要考慮的。不同任務的預算不同，往往任務價值越大，執行感知任務越困難，任務所需用戶數越多，任務預算越大。同時用戶感知成本也會影響用戶的獎勵偏好，在相同的任務獎勵下，感知成本越低，用戶需要付出的代價越小，用戶的獎勵偏好越大。因此，首先通過任務的預算和所需用戶數計算參與者平均獎勵，結合感知成本計算用戶ui對任務wj的獎勵偏好，記為Ωi，j：

(7)

其中，ci，j為用戶感知成本，在節2.2.2介紹。

綜上所述，用戶與任務間的時間匹配度、距離匹配度、任務類型以及任務獎勵都會影響用戶對任務的偏好，且用戶偏好與上述因素成正相關關系。用戶與任務的時間、距離越匹配以及用戶對任務的類型和獎勵偏好越高，用戶對任務的偏好越大。參考文獻[10，22]中對用戶相關屬性的量化方式，計算用戶ui對任務wj的偏好，記為γi，j：

γi，j=Ξi，jΨi，jΖi，jΩi，j。

(8)

2.2 任務偏好

2.2.1 用戶聲譽

參與者提交數據質量對群智感知服務性能具有重要影響。高質量的數據不僅可以提高數據請求者的滿意度，也能維持平臺高效運行；反之，低質量的數據降低了群智感知服務的可用性。聲譽指標可以很好地反映用戶執行感知任務的能力，通過考慮用戶歷史任務記錄來評估用戶的聲譽。在用戶歷史任務記錄中，用戶提交數據的準確性是主要因素。

假設用戶ui在執行歷史任務wj時提交了一組數據{d1，d2，…，dn}，感知平臺計算的數據真值為d*，則通過均方根誤差來衡量一組感知數據的觀測值同真值之間的偏差αui(wj)，對其進行歸一化，得到參與者感知數據的準確度，記為βui(wj)：

(9)

(10)

其中，αmin(wj)和αmax(wj)分別為執行感知任務wj的所有用戶感知數據的最小偏差和最大偏差。

(11)

2.2.2 用戶感知成本

邊緣節點通過考慮移動成本、資源消耗成本和流量消耗成本實時評估用戶感知成本ci，j。其中，移動成本表明用戶從當前位置走到任務位置所產生的距離開銷，與用戶和任務間的距離有關。距離越大，移動成本越大并且用戶每移動單位距離會產生一個固定的開銷，ρdis為單位距離成本，與系統類型有關。資源消耗成本和流量消耗成本表明用戶執行感知任務過程消耗的設備內存、電量和流量。用戶執行感知任務所需時間越長，資源消耗越多，ρres為單位時間資源消耗系數，根據用戶自身設備可知；用戶感知數據量越大，上傳數據花費的流量越多，其中ρdata為單位數據流量消耗系數，由用戶提交的配置文件可得。因此，邊緣節點評估用戶ui完成任務wj的感知成本，記為ci，j：

ci，j=ρdisDi，j+ρresΔt(wj)+ρdataowj，

(12)

其中，Di，j為用戶所需移動距離，Δt(wj)為任務所需感知時間，owj為任務所需數據量。

在評估任務對用戶的偏好時，平臺更喜歡為任務選擇完成質量較大的用戶。高質量的用戶往往能夠提供高質量的感知數據，用戶聲譽代表用戶完成任務的質量。另外，對于不同的任務，用戶完成任務的感知成本不同，在用戶提供數據質量相同的情況下，平臺更想要那些感知成本低的用戶。因此，通過用戶聲譽和感知成本來量化平臺中任務wj對用戶ui的偏好，記為εj，i：

(13)

3 參與者選擇策略

筆者基于延遲接受機制[21]的思想實現多對一匹配條件下的穩定匹配。算法從候選用戶集Uk中的每個用戶ui出發，向用戶偏好列表l(ui)中的第一個任務wj發出匹配。任務集中的每個任務wj根據收到的用戶請求和所需用戶數rj限制最優地選擇用戶子集。未被選擇的用戶開始下一輪的匹配，向偏好列表中的下一個未被選擇的任務發出匹配，然后相應的任務根據當前用戶集和新到達用戶最優地更新當前用戶集合，直到所有用戶找到自己匹配的任務。

所提的參與者選擇算法如下。

算法1基于穩定匹配的參與者選擇算法(PSSM)。

輸入：任務集W，用戶集U，l(ui)，l(wj)。

輸出：匹配S。

初始化：S(ui)←φ，S(wj)←φ。

① 對用戶集U按照聲譽值降序排序

② 候選用戶集Uk←聲譽前k個用戶

③ whileUk不為φ

④ for?ui∈Uk

⑤ 選擇l(ui)中還未被選過的第一個任務

⑥ if (|S(wj)|

⑦S(ui)←wj

⑧S(wj)←S(wj)∪ui

⑨Uk←Ukui

結論1PSSM算法是有窮的。

證明 while循環中每個用戶最多向n個任務發出請求，所以最多在nk個請求后算法停止。

結論2PSSM算法可以得到穩定匹配。

證明 假設匹配S中不包含匹配對(ui，wj)。第1種情況：ui從未向wj發出請求，得到ui比起wj更喜歡當前匹配對象，因此(ui，wj)是穩定對；第2種情況：ui向wj發出了請求，但是wj拒絕或拋棄了ui，得到wj比起ui更喜歡當前的匹配對象，(ui，wj)是穩定對。因此，匹配S中不包含的對一定是穩定對，匹配S不包含不穩定對，所以，PSSM算法是穩定的。

結論3PSSM算法可以產生雙方完全匹配。

證明 假設存在用戶ui在算法結束后未匹配到任務。由此可知，一定有一個任務wj的匹配對象沒有達到任務所需用戶數rj。根據算法，這種情況下任務wj一定會接收用戶ui發出的請求，所以用戶ui沒有向任務wj發出請求。根據算法，用戶ui向所有任務發出請求后才會終止，因此用戶ui向任務wj發出了請求。前后矛盾，假設不成立。所有用戶完全匹配，因此產生雙方完全匹配。

結論4PSSM算法產生用戶最優分配。

證明 對于用戶ui，如果最后該用戶的匹配任務是在其偏好列表的第i位，那么在i位之前的那些任務，他是匹配不到的。假設ui匹配到前面的任務wj(即wj一時糊涂答應)，那么任務wj必然會有比用戶ui更加偏好的對象uj(在當時情況下，uj已經向wj發出匹配)。uj在當時向wj發出匹配，表明在偏好列表中wj之前的任務都拒絕了uj，如果wj也拒絕了uj，那么uj最后匹配到的任務必定排在wj后面。所以，uj和wj必然會構成不穩定對。假設不成立，因此PSSM算法產生用戶最佳分配。

4 數值結果分析

為了更好地體現參與者選擇策略PSSM的性能，與文獻[14]提出的TRIM機制和文獻[23]提出的IMRAL機制進行對比。TRIM機制首先根據任務向量和用戶向量計算兩者的相似度并獲得候選用戶集，然后根據報酬和相似度比值確定最終用戶集。IMRAL機制針對每個任務選擇投標與任務價值之比最小的用戶作為獲勝者，并根據臨界價格給出報酬。仿真性能指標包括偏好程度、用戶滿意度、數據質量和任務平均完成時間。具體仿真參數如表1所示。

表1 仿真參數設置

4.1 用戶偏好分析

圖2 用戶和任務偏好程度分析

圖2展示的是在單任務需求數為2時，100個用戶與50個任務進行穩定匹配，得到的每個匹配對中用戶和任務各自的偏好程度。其中偏好程度表示每個匹配對中用戶匹配到的任務或任務匹配到的用戶在各自偏好列表中的排名，偏好程度越小，用戶或任務對匹配對象的偏好越高。從圖2中可以看到，在100個任務用戶匹配對中，大多數的小點處在小圓的下方，表明在得到的穩定匹配中，用戶對各自匹配任務的偏好明顯優于任務對用戶的偏好。這是因為筆者提出的PSSM算法中對于每個用戶來說，匹配到的任務都是穩定匹配條件下能夠匹配到的偏好最大的任務，因此該算法可以實現用戶偏好最優分配。

圖3研究了在任務數量為10和單任務所需用戶數為3時，任務總預算對用戶滿意度的影響。其中用戶滿意度表示為穩定匹配對中用戶對任務的平均偏好值。隨著任務預算的增加，三種算法的用戶滿意度都會增加。其中，IMRAL算法的主要目的是提高用戶效用和任務覆蓋，任務預算的增加使所選用戶的效用提高，但由于沒有考慮用戶的偏好，用戶的滿意度比較低。相比于TRIM算法，PSSM算法以用戶偏好最大化為目標，因此PSSM算法中用戶滿意度最大。

4.2 平臺效用分析

圖4展示了在單任務需求用戶數為3時任務數量對整體數據質量的影響。整體數據質量定義為所有用戶提交數據質量的均值，在這里用聲譽代表用戶提交數據的質量。隨著任務數量的增加，整體數據質量有所降低。這是由于在用戶資源有限的情況下，任務數量越多，任務所需的用戶數越多，提交低質量數據的用戶會增多，導致數據質量降低。其中，IMRAL算法的目的是提高用戶效用和任務覆蓋，但是沒有考慮用戶具體感知數據質量，因此整體數據質量較低。相比于TRIM算法，PSSM算法量化了用戶的聲譽，并且從用戶集中優選聲譽值高的用戶構造候選用戶集，保證感知數據的質量。

圖3 任務總預算對用戶滿意度的影響

圖4 任務數量對整體數據質量的影響

圖5展示了在任務數量為20和單任務需求用戶數為3時，不同用戶數量對整體數據質量的影響。隨著用戶數量的增加，整體數據質量有所提高。由于在任務數量固定的情況下，任務所需的用戶數是固定的，隨著用戶數量的提高，用戶資源變得充足，平臺可以選擇更優的用戶去執行任務，數據質量有所提高。IMRAL機制主要優化用戶效用，假定所有用戶提交數據質量是一樣的，因此整體數據質量較低。TRIM機制考慮用戶和任務間的相似度，并根據閾值優化候選用戶集，數據質量有所提高。而筆者提出的PSSM機制量化了用戶的聲譽，并根據聲譽對匹配用戶進行優化，數據質量較高。

圖6展示了在任務數量為10和單任務需求用戶數為3時，用戶數量對任務平均完成時間的影響。任務平均完成時間定義為用戶執行感知任務所需的時間均值。隨著用戶數量的增多，任務平均完成時間有所下降。這是由于用戶數量的增多，導致用戶方的資源充足，有效降低任務完成時間。IMRAL機制主要優化用戶效用，沒有考慮用戶的具體位置，任務完成時間最高。相比于TRIM，筆者提出的PSSM考慮了用戶可用時間和所處位置，并量化用戶的偏好，為用戶分配最優偏好任務，因此任務完成時間最低。

圖5 用戶數量對整體數據質量的影響

圖6 用戶數量對任務平均完成時間的影響

5 結束語

筆者在結合移動邊緣計算的移動群智感知架構下提出了一個偏好感知的參與者選擇策略，參與者選擇過程由云平臺和邊緣節點協作執行。考慮用戶和任務不同的偏好，邊緣節點從任務時間、位置、類型和獎勵方面對用戶偏好進行量化，從用戶聲譽和感知成本方面對任務偏好進行量化。基于雙方的偏好，在用戶與任務間構造一個多對一穩定匹配，使匹配后的每個用戶得到最優分配任務。在未來的工作中，打算研究在用戶或任務動態到達的情況下如何立即做出選擇，如何更好地實現邊云協同發揮移動群智感知的優勢等。