王小雪，張志勇，史培寧

(河南科技大學 信息工程學院，河南 洛陽 471023)

0 引 言

群體計算[1]旨在整合互聯網上大量未知用戶(人群)和計算資源(機群)來處理現有計算技術難以完成的復雜任務。在群體計算的研究中，任務分配問題是核心問題之一，該問題研究如何將實時出現的群體任務分配給適宜的用戶?，F有工作[2]通常基于靜態(tài)場景，即全部群體任務與用戶的信息在任務分配前已經完整獲知，較少融合用戶多維環(huán)境信息[3]，且很少考慮到用戶的屬性信息與歷史記錄，但群體任務在實際應用中動態(tài)出現，且需實時地對其進行任務分配。上下文感知[4-6]在1994年被提出，并將情景定義為位置，周邊的人和對象的集合和這類對象的變化。Carl K.Chang[7]提出了情境分析理論，并基于此理論提出Situ架構，該架構能夠通過分析用戶歷史行為數據獲取用戶的實時意圖，從而為用戶提供實時并且個性化的服務。張等[8]在上述理論的基礎上建立了SocialSitu理論，提出了一種面向在線社交網絡用戶的行為模式發(fā)現方法，通過分析用戶的歷史行為數據，預測用戶下一時刻意圖。因此，在此研究的基礎上，通過分析移動社交用戶的SocialSitu(t)序列和歷史信息提出了面向移動在線社交網絡的任務分配架構，進一步提出基于SocialSitu的用戶適合度任務分配算法并通過實驗驗證算法的適用性。

1 任務分配架構

本文所提出的面向在線社交網絡的群體計算系統(tǒng)架構的目的在于為社交網絡中的用戶分配合適的任務，因此需滿足3個基本需求：①在社交網絡中找到最適合某項任務的移動用戶群體；②服務端可以自主設計、發(fā)布、評價任務；③提供用戶執(zhí)行任務的接口，因此本文設計了一個層次架構以滿足這些要求，群體計算系統(tǒng)架構如圖1所示。具體的分層架構設計如下：

(1)社交平臺設施層

第一層是社交平臺設施層，其中社交媒體平臺服務器設計并發(fā)布群體計算任務。該層的主要功能是待用戶完成任務并回傳數據至本層時，平臺設施層對用戶返回的數據進行處理，處理結果將作為下次該用戶分配任務的參考，同時更新群體的信息。

(2)數據處理中間層

第二層是數據處理中間層，數據傳輸鏈將社交平臺設施層的群體用戶數據傳遞至數據處理中間層，本層分析用戶的訪問行為(如：登錄)與歷史信息(如：成功率)，根據基于SocialSitu的用戶適合度任務分配算法尋找合適的用戶。同時，本層還整理、分析、存儲來自群體用戶應用層的結果數據。

(3)群體用戶應用層

第三層是群體用戶應用層，本層包括不同種類的群體應用，并提供群體用戶接口。用戶加入群體任務后，可以轉發(fā)任務興趣相投的好友，待執(zhí)行任務之后，用戶將結果數據返回至數據處理中間層處理。

圖1 任務分配架構

2 基于SocialSitu的用戶適合度任務分配算法

移動社交用戶具有移動性、隨機性和復雜性等特征，因此面向移動社交網絡用戶群體的任務分配不單單要著重考慮用戶的可信度和服務能力，而且更要關注用戶的訪問行為的變化及歷史服務信息等因素?？紤]到影響任務分配的因素，本文通過分析移動社交用戶的歷史信息定義了影響任務分配的屬性，由這些屬性計算得出的用戶任務適合度即用戶適合某項任務的程度。

2.1 相關定義

定義1 SocialSitu (t)：定義請參見文獻[8]。

定義2 成功率Ssucc為移動用戶成功完成歷史任務的比例，如式(1)所示，其中Nsucc為歷史服務成功次數，Ntotal為歷史服務總次數

(1)

定義3 平均服務應答時間Sdel為平臺分配任務到移動用戶接受任務的時間間隔，如式(2)所示，其中d(hj)為歷史任務hj的應答時間(hj∈H)，sdel(Ui)為平臺分配任務的時間，e(Ui)為用戶Ui接受任務的時間，H為用戶歷史信息

(2)

定義4 滿意度Ssat為用戶對于系統(tǒng)為其分配的任務的滿意程度，如式(3)所示，其中s(hj)為用戶對平臺分配歷史任務hj的滿意度(hj∈H)，ρ(式(4))為衰減因子，它是一種隨時間變化而動態(tài)衰減的量，即所隔時間越久，用戶滿意度對服務決策的影響越小

(3)

(4)

定義5 用戶適合度是評價用戶適合執(zhí)行某項任務的程度。由以上成功率、平均服務應答時間、滿意度計算得出，由式(5)所示，適合度越大表示用戶越適合此項任務。其中wij表示用戶i的第j個屬性，αit表示對于任務t，用戶Ui的第j個屬性duj所占的權重，p為屬性的個數

(5)

2.2 分配算法

為實時準確地為移動社交用戶分配任務，采用的基于SocialSitu(t)的用戶意圖序列化算法可根據用戶的歷史行為的SocialSitu序列實時地預測用戶在下一時刻的意圖，在了解用戶的意圖(用戶會選擇何種任務)的情況下，再計算出移動用戶的任務適合度，依據任務適合度大小分配任務。算法流程如圖2所示，具體的算法過程如下所示：

(1)獲取待完成任務的相關信息。待完成任務列表R={r1,r2,…rn}，遍歷i(1≤i≤n)個任務ri的ID，需要完成該項任務的人數K，待完成任務的類別庫C，以及任務完成的截止時間T。

(2)在用戶列表中獲取用戶的歷史信息，計算出包括用戶的完成度Ssucc，平均服務應答時間Sdel，滿意度Ssat。

(3)如果用戶u當前在線，則跳到步驟(4)，如果用戶u為離線用戶，則跳到步驟(8)。

(4)對在線用戶u的歷史SocialSitu(t)信息進行分析處理，并通過用戶行為模式發(fā)現算法SituBehaviorAnalytics(DS, Min_Support, G)獲得用戶u的行為序列模式。

(5)將用戶u對應特定意圖的行為序列模式存儲，Compare(Social(0)u,Social(1)u,…,SocialSitu(t-1)u),uBehaviorpattern[intention]函數將用戶u當前行為與行為模式序列進行對比，并預測用戶u下一刻意圖。

(6)如果用戶u的意圖與待完成任務ri的類別C相關，則將用戶u的ID存入待分配任務的用戶集合U。

(7)計算用戶u對于待完成任務ri的適合度Sui。

(8)計算出所有對于待分配任務ri的用戶的適合度，按照適合度從高到低進行排序，選出被分配的用戶集合L，將任務ri分配給L中的所有用戶。

(9)重復步驟(1)～(7)直到不再有新的未分配的任務。

圖2 算法流程

算法1：任務分配算法

Input: 用戶集合：U， 用戶歷史信息：H， 用戶的情境信息： SocialSitu(t)， 待完成任務集合：T， 待分配任務用戶集合：UT， 所需人數：K

Output: 待分配任務的用戶的UserID

TaskAssign(UT, T)

(1)Begin

(2)foreachri∈Randi←1ton

(3)foreachu∈UandSsucc、Sdel、Ssat

(4)ifu is online

(5)u.Behaviorpattern[intentionm]=SituBehaviorAnlytics(DS,Min_Support,G);

(6)foreach intentionm∈Intention

(7)Compare(Social(0)u,Social(1)u,…SocialSitu(t+1)u),uBehaviorpattern[intention]

(8)ifintentionut=intentionm

(9)ifintentionut∈C

(10)u∈UT

(11)endif

(12)endif

(13)foreachu∈UT

(15)endfor

(16)endif

(17)else

(18)foru∈UT

(20)endfor

(21)Rank(Sui);

(22)endfor

(23) Assign(UT, T)

(24)endfor

(25)End

其中SituBehaviorAnlytics(DS, Min_Support, G)函數指分析用戶特定意圖下的行為模式，DS為用戶行為數據集，Min_Support,為最小支持度，G為用戶的意圖。Compare(Social(0)u,Social(1)u,…,SocialSitu(t-1)u),uBehaviorpattern[intention]函數指將用戶當前行為與行為模式進行對比[8]。

3 實驗與結果

本文所采用的實驗平臺是在線社交網絡平臺CyVOD[9](www.cyvod.net)和CyVOD客戶端應用。該平臺架構如圖3所示。CyVOD平臺作為設計、發(fā)布、分配任務的服務端，如圖4所示?？蛻舳藙t作為用戶申請、執(zhí)行、反饋、轉發(fā)任務的應用端，如圖5所示。

圖3 CyVOD體系架構

圖4 服務端任務分配界面

圖5 客戶端執(zhí)行任務界面

3.1 實驗設計

移動社交網絡作為人類傳播信息、進行社會交流活動的平臺，引發(fā)了廣泛的應用和關注。當今社交網絡平臺上的安全隱私問題的凸顯，亟需社交網絡用戶對平臺功能、安全防范、隱私保護等功能進行評估[10-12]。根據當前社交網絡中普遍存在的安全問題，本文設計了7項社交平臺群體評估任務，分別對社交網絡平臺的安全信任等方面進行評估，評估內容見表1。群體評估的流程如圖6所示。

3.2 實驗結果

為驗證所提算法的正確性，因此與隨機分配和基于用戶屬性兩種任務分配算法進行對比。隨機任務分配算法即不考慮用戶的多維屬性與影響因子，只是簡單隨機地選取用戶后分配任務。操作簡單但無針對性，因此用戶完成度，反饋率均較低?；谟脩魧傩苑峙渌惴ǔ浞挚紤]用戶的多維屬性與影響因子，但是不考慮用戶的行為與意圖，因此提出的基于SocialSitu算法綜合二者優(yōu)點，取長補短。既充分分析了用戶的行為與意圖，還綜合考量了多維屬性與影響因子。

表1 群體評估任務

圖6 群體評估流程

3.2.1 正確性分析

表2是通過基于SocialSitu(t)的用戶意圖序列化算法根據用戶的歷史行為的SocialSitu序列得出用戶的行為模式，并實時地預測出的下一時刻的意圖。

表2 基于SocialSitu的用戶行為模式與意圖

表3是采用隨機分配算法所得出的實驗數據，表4是采用基于用戶屬性的任務分配算法所得出的實驗數據，表5是采用基于SocialSitu的用戶適合度分配算法所得出的實驗數據，很顯然，隨機算法以及基于用戶屬性分配算法所選取的用戶并沒有及時反饋信息，從而導致用戶完成率低下，用戶對平臺的所分配任務的滿意程度也較低，相對而言，基于SocialSitu的用戶適合度分配算法大大提高了用戶的完成率與用戶滿意度。

表3 隨機算法任務分配及回收情況

表4 基于用戶屬性的任務分配及回收情況

表5 基于SocialSitu的用戶適合度任務分配及回收情況

3.2.2 有效性分析

為驗證所提算法有效性，比較同一任務下用戶的適合度，如圖7所示，用戶ID為9，8，5更適合此項任務。在總體任務數相同的基礎上分別比較采用3種算法整體用戶的任務平均完成度和滿意度，實驗結果如圖8和圖9所示。通過3種分配算法的對比結果可以得出基于SocialSitu的用戶適合度分配算法在提高用戶任務完成度與用戶滿意度方面效果顯著，用戶整體平均完成度較隨機和基于屬性的分配算法提高平均0.4和0.2左右，平均滿意度提高平均0.1和0.2左右，因此可說明基于SocialSitu的用戶適合度任務分配算法優(yōu)勢明顯。

圖7 用戶適合度對比情況

圖8 3種算法的整體用戶完成度比較

圖9 3種算法的整體用戶滿意度比較

4 結束語

在線社交網絡的迅速發(fā)展，移動設備的普及使得在線社交網絡中含有豐富的計算資源，為了充分地利用這些資源，本文提出了一種面向移動社交網絡群體的任務分配架構，同時提出了基于SocialSitu的用戶適合度任務分配算法，通過分析用戶的訪問行為、歷史信息為用戶分配適合的任務，并通過群體評估實驗驗證了算法的有效性。該算法的分配準確率和用戶完成度較高，運算速度還較慢。在后續(xù)研究中，考慮利用機器學習中的關聯規(guī)則解決此問題。