基于用戶關注度以及時間監(jiān)督的任務分發(fā)

張 力 張書奎 劉 海 張 洋 陶 冶 龍 浩 于淳清 祝啟鼎

1(蘇州大學計算機科學與技術學院 江蘇蘇州 215006)

2(淮北師范大學計算機科學與技術學院 安徽淮北 235099)

(greenwuhu@126.com)

自2006年，Howe[1]定義了“用電話方式通知不確定的一群人(通常稱為工人)來完成通常個人難以完成的感知任務行為”以來，人們用“群智”來解決困難問題取得了非常好的效果.當前，智能設備中嵌入各種傳感器是常見的事情，這些傳感器可以幫助人們獲取想要的信息.Wang等人[2]研究了群智感知中最常見的問題——任務分配.傳統(tǒng)無線傳感器網絡中感知節(jié)點通常是功能專業(yè)的傳感器，部署復雜，安裝費用高.而群智感知中的感知節(jié)點利用工人高度自治的嵌入式智能設備.伴隨無線技術應用不斷提升，尤其是功能強大的5G技術普遍應用，可以充分利用“閑散”的功能強大的智能設備幫助人們解決復雜問題.

群智感知利用感知功能，相互之間協(xié)調合作，不僅可以完成短期的收集城市交通流量信息[3]、停車位檢測[4]，而且可以感知長期感知任務、危險山區(qū)地形檢測[5]、空氣質量監(jiān)測[6]等，都能夠非常好地完成感知任務.

Fig. 1 Location sensing task圖1 位置感知任務

圖1顯示，這些應用中的感知任務通常依據任務所在的位置進行分發(fā)，網絡中的“悠閑”用戶利用智能設備完成感知任務.該方式的核心是通過眾包進行，任務的分發(fā)會考慮用戶狀態(tài)、環(huán)境信息、社會屬性等.感知任務分發(fā)位置[7-9]和完成感知任務時間[10-11]是任務的最基本屬性，挖掘感知任務位置的自身特征，更能體現(xiàn)對任務的本質揭示.一般來說用戶間的穩(wěn)定關系以及相互之間的依賴性，能更好地協(xié)作完成感知任務.感知用戶間頻繁接觸，可使用戶間形成良好的偏好關系.挖掘用戶之間友好關系對任務分發(fā)的影響，可以提升任務分發(fā)的準確度.對感知任務完成時間已有部分研究，多數(shù)研究主要關注的是完成感知任務最小時間，如平均最小完成時間和完成感知任務的總時間最小.對任務執(zhí)行過程，沒有很好地監(jiān)控，對于任務的完成情況影響很大.因此，本文從任務參與者之間的關系，以及任務完成感知過程中的時間監(jiān)督，研究對感知任務的影響.

本文主要貢獻包括3個方面：

1) 通過分析執(zhí)行感知任務用戶之間的關系，提出用戶之間的單關注度、互關注度以及多關注度概念.

2) 根據完成感知任務的時間要求，提出感知任務完成過程時間監(jiān)督定義，通過分析用戶之間的關系以及時間監(jiān)督對移動群智感知中感知任務分發(fā)的影響，將用戶之間關系強弱和時間監(jiān)督作為感知任務影響因素，提出用戶關注度與時間監(jiān)督的感知任務分發(fā)(task distribution with user attention and time supervision, TDUATS)算法.

3) 在真實數(shù)據集上進行了感知任務分發(fā)實驗.結果表明，所提出的算法(TDUATS)從關注度和時間監(jiān)督對感知任務分發(fā)的影響，以及隨著感知任務數(shù)目增加任務分發(fā)成功率都有不同程度的提升.

1 相關工作

移動用戶攜帶嵌入豐富智能的傳感設備，將移動技術和群智感知結合起來，出現(xiàn)了許多創(chuàng)新的商業(yè)模式，使學術和工業(yè)界都備受關注.這些應用中需要考慮不同感知位置、完成感知任務的時間約束、移動成本和信譽等用戶任務的選擇問題.感知任務分配是NP難問題.怎樣高效分發(fā)感知任務是群智感知中的研究熱點問題,常見任務分發(fā)如圖2所示.

Fig. 2 Sensing task distribution圖2 感知任務分發(fā)方式

當前，無線技術無處不在，基于移動通信的群智感知已經被廣泛應用，用戶在感知任務的位置時，移動軌跡信息容易暴露，使得用戶感到非常不安全.Pournajaf等人[12]通過任務管理使參與感知用戶間的敏感信息避免收到威脅，并應用于相關的群智感知中.Sherchan等人[13]為了減少發(fā)送數(shù)據量以及手機能量消耗，采用挖掘數(shù)據實現(xiàn)可擴展的數(shù)據收集.根據感知用戶實時移動的位置信息，提供了一種有效的移動群智感知策略.Ma等人[14]為了提升推薦的成功率，通過研究用戶之間的相關性，為沒有標記和較少標記的用戶添加標記，構建用戶之間的標簽矩陣，獲取用戶的標簽權重，設計了用戶之間的迭代興趣機制.該機制是對沒有標記或很少標記添加標簽，這些用戶是否可靠信任，難以保證推薦的滿意度.Wang等人[15]通過對用戶的感知區(qū)域和感知時間進行分割，劃分為更小的區(qū)域和時間段.由感知用戶覆蓋區(qū)域，感知區(qū)域以及感知時間構建感知用戶間的任務效用評價，結合感知用戶移動模型，分析用戶效用質量的模型理論，使感知用戶任務效用質量最大化.對感知區(qū)域和感知時間進行了分割，增加了搜索的規(guī)模，卻沒有對劃分的更小時間段進行更細致的監(jiān)督.于瑞云等人[16]通過用戶之間的接觸時間和接觸次數(shù)來衡量用戶之間的關系強弱，如果用戶之間接觸時間越長，接觸次數(shù)越多，則說明用戶之間的關系越強，反之則反.通過用戶之間的相關性構建用戶位置預測模型.該模型采用2階Markov模型，可能會導致搜索狀態(tài)空間過大，搜索時間過長.楊金勞等人[17]根據用戶之間的共有群信息，計算用戶之間的相關性，以獲取其他用戶的偏好，為了減少用戶的搜索過程和檢索時間,提升推薦成功率，采用均值與最小痛苦策略融合修正滿意平衡策略.而滿意度修正采用最小痛苦策略,也就是最小評分策略，難以保證群組中的用戶的滿意度.文獻[18]為了減少僵尸網絡對移動互聯(lián)網的入侵，研究了用戶活動之間的相關性和人工免疫監(jiān)測系統(tǒng).創(chuàng)建tweet的簽名和bot行為簽名庫，在Twitter，F(xiàn)acebook，YouTube等社交媒體上進行監(jiān)測，獲得不錯的效果.該模型僅僅考慮用戶的活動時間相關性，2個活動時間相同并不能保證其完成任務的質量.

有很多學者從不同角度研究感知過程消耗的時間對感知任務的影響.Xiao等人[19]根據用戶在社會網絡中的歷史數(shù)據，預測用戶的移動軌跡.任務的處理時間分為：用戶與任務發(fā)起者的相遇時間、移動用戶完成任務的執(zhí)行時間和任務結果返回給任務發(fā)布者的時間.設計了完成所有任務的最小化最長完成時間任務分配算法.該算法中加入用戶等待時間，等待時間可能很長，這樣增大了任務的平均時間，也沒能體現(xiàn)具體不同時間段對感知任務的影響.Lu等人[20]在傳感器感應半徑和相同的傳輸半徑前提下，為了找到目標覆蓋和數(shù)據收集的最大化，在目標區(qū)域覆蓋密度有界的條件下，提出多項式時間常數(shù)因子近似算法.實現(xiàn)實時預測出租車目的地及乘客下車地點服務推薦的估算.Chen等人[21]利用2階段法，由GPS軌跡數(shù)據降點聚類與城市空間候選活動區(qū)域匹配，提取行為細粒度時空模式，獲取估算目的地和下一目的地推薦服務.Ma等人[22]以時間、容量和報酬為限制，匹配最佳出租車乘車共享接機.平衡乘車人付費和出租車行駛最小化距離來滿足請求人的出租出行需求，為乘客和出租車設計了快速搜索算法.該算法僅討論了距離最小化，卻沒有體現(xiàn)任務執(zhí)行過程中乘客對任務執(zhí)行過程的滿意度.

對于有時間約束，與感知任務位置息息相關的分發(fā)任務，為了找到最佳任務參與者，He等人[23]設計了局部比率算法，使分配者的總獎勵與局部比率逼近某個常數(shù)，基于議價理論設計定價機制，可以找到任務的最佳分配.To等人[24]為了實現(xiàn)降低眾包數(shù)據收集成本和周轉時間，在預算固定時間戳限制下，設計了超局部空間眾包，可以提供細粒度感知數(shù)據，激勵感知任務時空附近的工人積極參與感知活動.然而在時間戳內，任務執(zhí)行的怎么樣，能否滿足發(fā)送者的請求，如果任務執(zhí)行過程不滿意，怎么調整等，這些都沒有進行分析.為了提高出租車共享系統(tǒng)的性能，Li等人[25]采用自適應鄰域搜索方法，進行固定樣本、近似平均樣本和順序采樣策略.結果顯示采用固定樣本可以提高出租車共享系統(tǒng)性能.可固定樣本策略不夠靈活，不能滿足實時需求.Xiao等人[26]在移動群智感知協(xié)助活動中，利用截止日期敏感的概率協(xié)助，為移動群智感知任務招募用戶，采用非線性編程約束和非平凡覆蓋的形式化表示，在預期時間內持續(xù)招募更多用戶算法，協(xié)作完成困難任務.

為了在一組騎乘車輛中找到最大持續(xù)時間和最大用戶乘車的最低成本路線.Gschwind等人[27]在攤銷固定時間算法中通過請求插入的可行性，使所提算法在路由選擇方面優(yōu)于對比算法.龍浩等人[28]研究了社區(qū)中移動節(jié)點之間的行為模式，計算節(jié)點之間的最小距離和社區(qū)融合度.該模型將用戶合理地分配到不同的社區(qū)，通過計算感知任務和社區(qū)行為之間的匹配度，然后根據社區(qū)間匹配度分發(fā)感知任務.仿真實驗顯示，社區(qū)任務分發(fā)算法降低了任務完成時間.

目前感知任務研究主要集中于用戶位置之間距離或感知任務時間花費等.基于位置的任務分發(fā)，常以感知任務為中心，選擇感知任務位置空間關聯(lián)較近的參與者，僅僅考慮位置遠近，不能反映用戶是否能夠勝任要求完成的感知任務.對于感知任務時間問題，?？紤]任務完成順序以及完成任務所需時間最優(yōu)化問題.而任務完成時間長短只是任務完成的時間限制，不能代表任務完成的好壞.

因此，感知任務的分發(fā)考慮感知用戶之間的關聯(lián)關系對任務分發(fā)成功的影響，以及在感知任務執(zhí)行過程中用戶之間的交互.為了深入考慮感知用戶和感知任務時間對感知任務的影響，本文提出基于感知用戶之間的關注度及感知任務時間監(jiān)督等級，并分析其對感知任務分發(fā)的影響.

2 任務關注度分析

感知器網絡中感知用戶和接受者之間看上去沒有聯(lián)系，沒有規(guī)律.如果能挖掘出參與者之間的內在聯(lián)系，有利于感知任務的完成.任務的發(fā)布與接收，常常與參與者之間的關系緊密聯(lián)系，找到最佳完成任務要求的接受者，則可以提升感知任務的完成效率.

2.1 用戶之間的相關性

感知器網絡中的用戶有2種典型的行為：接收其他用戶的任務請求和發(fā)布任務.

圖3表示用戶及任務之間相互關注，相互關注是用戶和任務之間關聯(lián)關系.感知器網絡中用戶與地理位置、用戶行為、用戶移動軌跡和專業(yè)知識等因素有關，因此用戶所關注的感知任務就有所不同.共同關心某一類任務，說明這些用戶之間對此類任務熟悉或可勝任類似的任務.如果能夠勝任類似任務，說明他們具有完成這些任務的能力，感知用戶之間相似程度會非常高.因此，我們從感知用戶對任務的關注程度出發(fā)，探討感知任務分發(fā).

Fig. 3 Mutual attention among user tasks圖3 用戶任務間的互關注聯(lián)系

同一用戶勝任多種任務關注度(one user to multi-tasks, OMT)記為O.某一用戶能夠完成多種類型的任務.圖4中用戶u1可以勝任2種任務.

Oi=Ntaski/Nui.

(1)

Oi表示第i個用戶的OMT，Ntaski是完成第i個任務的次數(shù)，Nui為用戶i完成所有任務的次數(shù).

Fig. 4 Competent for multiple tasks of the same user圖4 同一用戶勝任多種任務

多個用戶完成同一任務關注度(multi-user to the same task, MUST)記為M.圖5中用戶u1和用戶u2都可以勝任任務task1.說明用戶u1和用戶u2對任務task1的要求度有非常高的相似性.Mi表示第i個MUST.

Fig. 5 Multi-user sensing of the same task圖5 多用戶感知同一任務

(2)

Ntaskii∩taskij是用戶i和用戶j完成第i個任務的次數(shù)，Nui+uj表示用戶i和用戶j完成所有任務的次數(shù).

用戶與任務之間相互關注(user and tasks focus on each other, USTF)記為U.圖6表示用戶u1接受感知任務task1,同時感知任務task1的發(fā)送者也能勝任用戶u1發(fā)布的任務.兩者之間能夠互相幫助完成彼此的任務，說明他們之間有共同的“話題”，兩者趣味相投，一定會盡力完成彼此要完成的任務.

Fig. 6 Inter user sensing task圖6 用戶間感知任務

Ui表示第i個USTF,計算為

Ui=Ntaski∪taskj/2Nui+uj.

(3)

Ntaski∪taskj是完成彼此任務的次數(shù)，Nui+uj為用戶i和用戶j完成所有任務的次數(shù).

感知用戶之間的關聯(lián)性體現(xiàn)為：感知用戶間能夠互相完成相同或類似的任務.對于將要發(fā)布的任務，有利于找到合適的用戶.因此，我們挖掘出用戶與感知任務之間的3種關系，建立用戶之間的關聯(lián)關系.

根據用戶的軌跡數(shù)據，由軌跡數(shù)據尋找用戶之間的關聯(lián)關系，利用軌跡數(shù)據的關系，推測出用戶完成感知任務的相似程度.我們用Xijk表示根據軌跡數(shù)據獲取的用戶關注度，Yijk表示預測值，那么用戶之間的Xijk和Yijk的相似度越高則說明用戶間的相似行為越高，表示為

Xijk≈Yijk.

(4)

為了使Xijk-Yijk趨向于0，又因Xijk-Yijk有正負，同時為了計算方便，即使(Xijk-Yijk)2最小.

Zmin=(Xijk-Yijk)2+α(Oi+Mi+Ui)2.

(5)

式(5)中Zmin為(Xijk-Yijk)2的最小值，為了調節(jié)Zmin的最小值，需要加上(Oi+Mi+Ui)2，Oi,Mi,Ui分別為用戶第i個任務的OMT,MUST,USTF，α為調節(jié)因子(推導公式只考慮正值).

Zmin=(Xijk-Yijk)2+α(Oi+Mi+Ui)2,
0=2(Xijk-(Oi+Mi+Ui))Oi+
2α(Oi+Mi+Ui)Oi，
0=Xijk-(Oi+Mi+Ui)+α(Oi+Mi+Ui)，
Xijk-Mi-Ui+α(Mi+Ui)=Oi-αOi.

可以得到：

(6)

同理得到：

(7)

(8)

式(6)表示第i個任務的OMT關注度，是感知任務用戶獲取的軌跡數(shù)據關注度、同一任務關注度和用戶任務間的互關注三者之間的度量關系，α是調節(jié)因子，本文中的α=0.6.式(7)、式(8)分別表示軌跡數(shù)據關注度OMT和USTF之間的度量關系、軌跡數(shù)據關注度OMT和MUST之間的度量關系.

2.2 時間監(jiān)督

感知任務時間通常被用來衡量感知任務是否執(zhí)行完成、完成所有感知任務時間最短、平均完成時間最小等問題，對感知過程沒有具體化.

在某一段時間內，當感知任務剛被接受者接受時，希望發(fā)送任務的用戶能把任務的具體要求說清楚，發(fā)送者與接受者之間就需要進行交互，是為了更好地完成發(fā)送者的任務.在感知任務執(zhí)行的過程中，要對正在進行的任務完成情況向發(fā)送者匯報，溝通任務執(zhí)行情況是否符合發(fā)送者的要求.如果任務完成情況與發(fā)送者有差距，則可以及時進行調整.在任務基本完成時，雙方應及時進行交流，使發(fā)送者了解任務完成的近似結果，是否符合發(fā)送任務時的要求.這樣可以對任務過程進行全程監(jiān)督.

起始監(jiān)督是接受者能否在要求的時間內接受感知任務.設任務開始執(zhí)行時間為Ts,任務接受提前或推遲時間為Tad.如果參與者在任務有效時間內接受任務，即Ts-Tad≤Ts≤Ts+Tad,那么起始監(jiān)督就認為可以提高感知任務質量.如果不能在有效時間內執(zhí)行任務，即Ts-Tad>Ts或Ts>Ts+Tad，就會造成接受者對完成任務的不利影響.參與者接受任務的時間與發(fā)送者要求的時間差就形成不同程度的任務起始監(jiān)督影響.

執(zhí)行過程監(jiān)督是在任務執(zhí)行過程中，參與者與發(fā)布者進行相互監(jiān)督，溝通任務完成情況以及任務的完成是否符合發(fā)送者的要求.根據任務的難易程度和計劃時間長短，設定執(zhí)行過程監(jiān)督評價，如表1所示:

Table 1 Effect of Difficulty and Length of Execution on Sensing Tasks

Te為任務的實際執(zhí)行時間，Tad為完成任務推遲或提前時間.

任務完成監(jiān)督是對任務完成時間的約束，可以提前或推遲時間為Tad，但有限制范圍.任務完成時間為Tf,如果參與者在任務有效時間內完成任務，即Tf-Tad≤Tf≤Tf+Tad,那么任務完成監(jiān)督認為接受者提供高質量感知任務,與起始監(jiān)督相似.

知識庫是模糊集合和模糊規(guī)則構成推理的一系列過程.任務的起始監(jiān)督、執(zhí)行過程監(jiān)督和任務完成監(jiān)督設置為參與者完成任務的模糊集合，由“優(yōu)”“良”“合格”構成，分別用字母E,G,Q表示，發(fā)送者提供的數(shù)據質量模糊集合為“非常優(yōu)”“優(yōu)”“良”“合格”“不夠好”構成，分別用字母VE,E,G,Q,NQ表示.因此，發(fā)送者與接受者的模糊集合分別表示為：

Z1表示起始監(jiān)督；Z2表示執(zhí)行過程監(jiān)督；Z3表示完成監(jiān)督；Z4表示任務提交數(shù)據質量.

Z1={E,G,Q},
Z2={E,G,Q},
Z3={E,G,Q},
Z4={VE,E,G,Q,NQ}.

根據模糊規(guī)則和模糊集描述任務完成情況，模糊規(guī)則基于專家知識系統(tǒng)或經驗.模糊規(guī)則我們采用IF-AND-THEN形式，模糊規(guī)則的定義如表2所示:

Table 2 Fuzzy Rule Set for Sensing Task Quality Determination

續(xù)表2

注：VE，E，G，Q，NQ分別表示“非常優(yōu)”“優(yōu)”“良”“合格”“不夠好”.

時間監(jiān)督通過起始監(jiān)督、執(zhí)行過程監(jiān)督、任務完成監(jiān)督3方面判斷接受者提交的任務完成情況，再由知識庫判斷接受者提交的完成任務情況.

3 感知任務模型

相關研究表明，影響感知任務分發(fā)原因很多，諸如感知任務平臺利潤、用戶之間位置關系、參與感知任務用戶數(shù)目等因素，但研究用戶之間關系和時間監(jiān)督對任務分發(fā)的影響不多.本文提出用戶間互關注度和任務時間監(jiān)督對感知任務進行分發(fā)研究.首先對感知任務與用戶之間的關系建立模型；接著挖掘出用戶之間相關性進行建模，用戶之間相關性弱，則在感知過程中一般表現(xiàn)為完成感知任務不能令發(fā)布者滿意或不愿意接受任務.由于感知任務時間是影響任務完成的主要因素之一，對任務完成過程怎樣進行監(jiān)督，提出時間監(jiān)督衡量感知任務執(zhí)行過程.感知任務是通過用戶之間互關注度，再結合時間監(jiān)督參與感知任務執(zhí)行過程，讓發(fā)布者選擇適合自己要求的接受者.

3.1 感知任務分發(fā)

從圖7中可以看出，在感知器網絡中，感知用戶利用攜帶的智能感知設備，既可以發(fā)布任務，也可以接受任務.感知中心分發(fā)感知任務，用戶也可以積極參與感知任務.如果感知任務非常復雜，感知中心和發(fā)布任務者共同把任務分解，小任務分發(fā)給感知用戶合作解決復雜任務.感知任務分發(fā)先比較關注度大小，選擇關注度差值最小，因此感知任務分發(fā)總關注度之和最小.時間監(jiān)督是先判斷接受者是否能在允許的時間范圍內完成感知任務，再考慮起始、執(zhí)行過程和完成監(jiān)督的模糊規(guī)則集，盡量選擇是良好及以上的用戶接受感知任務.從這個角度看，用戶之間在感知任務過程中存在競爭.如果選中的感知用戶的模糊集都是優(yōu)等級，則說明時間監(jiān)督非常切合發(fā)布用戶的要求，感知任務時間也是最短的，但我們不是求具體時間之和最短.

Fig. 7 Task distribution process圖7 任務分發(fā)過程

3.2 TDUATS算法

在移動感知器網絡中，任務的分發(fā)或參與者接受任務是隨機的，從歷史軌跡中發(fā)現(xiàn)參與者之間的某種關聯(lián)關系，有助于感知任務的完成.在互聯(lián)網中，彼此之間不信任是正常且合情合理.發(fā)布者和接受者之間如果存在聯(lián)系或者彼此之間有過合作，那么再一次合作的意向就會增強.在合作過程中有互動，能夠及時交流任務的執(zhí)行情況，是否滿足發(fā)布者的要求，有利于提升雙方的合作，也能夠提升任務分發(fā)的合理性以及準確性.

在感知任務分發(fā)過程中，提出的TDUATS算法挖掘用戶之間的關注度，為感知任務找到適合自己需求的接受者，提升了感知用戶接受感知任務的可能性，確保感知任務完成質量；引入時間監(jiān)督，監(jiān)督任務執(zhí)行過程，用戶之間可以及時溝通任務執(zhí)行情況，及時調整策略達到分發(fā)任務用戶的要求.具體算法描述見算法1.

算法1.基于用戶關注度和時間監(jiān)督的感知任務分發(fā)算法.

輸入：初始化用戶與任務之間的互關注、時間監(jiān)督；

輸出：URS[n]，TS[n]，表示經過循環(huán)處理后，每個用戶之間的互關注度和選中的感知任務時間監(jiān)督.

① procedureTDUATS(URS,TS)

② 初始化URS,TS←0;

③ for (i=1;i

④ for (j=1;j

⑤ 計算用戶之間關注度強度URS[i];

⑥ 比較接受者和發(fā)送者的關注度最小;

⑦ end for

⑧ end for

⑨ for (i=1;i

⑩ if (根據模糊規(guī)則判斷用戶時間監(jiān)督)

3.3 算法性能分析

TDUATS算法的時間復雜度為O(n2)，空間復雜度為O(n)，其中n,m分別代表發(fā)布任務的數(shù)目n和接受感知任務的用戶數(shù)目m.

算法1中行③～⑧為循環(huán)的時間復雜度，由發(fā)送感知任務的數(shù)目和接受任務的參與者數(shù)目共同決定.行⑨～循環(huán)判斷任務時間監(jiān)督的時間復雜度為O(n).TDUATS算法中當發(fā)送者和接受者的數(shù)目都趨向n時，算法循環(huán)的次數(shù)為n2，TDUATS算法的時間復雜度為O(n2).

當發(fā)送任務數(shù)目和參與感知任務的用戶數(shù)目都為n時,算法1中需要輔助存儲的變量為用戶的關注度，需要存儲的輔助空間是URS[n]和TS[n].故算法的空間復雜度為O(n+n+O(URS[m])+O(TS[n]))，所以總的空間復雜度為O(n).

4 實驗分析

本實驗主要是驗證在移動感知器網絡中，具有互關注的用戶之間和任務時間監(jiān)督對感知任務的分發(fā)影響.為了充分體現(xiàn)所提算法的優(yōu)越性，在真實數(shù)據集中進行了實驗仿真.

4.1 實驗設計

首先采用麻省理工學院Reality Mining[29]提供的真實數(shù)據集對算法關注度進行驗證.該數(shù)據集記錄麻省理工學院教職工和學生攜帶的97個智能設備，包含約9個月的移動時間、接觸聯(lián)系、通話時長和移動地點等信息，約有100萬條記錄，實驗選取了約50萬條軌跡數(shù)據，因其部分設備有很多智能設備與其相連，而有的設備相連智能設備數(shù)量較少，兩者數(shù)目差距較大，因此刪減了部分數(shù)據.為了收集相同任務的數(shù)據，最終選取50個智能設備，驗證實驗結果.

實驗采用Eclipse平臺，開發(fā)語言為Java語言,在戴爾(DELL)臺式機(i5-7400 8 GB 128GSSD+1T)上進行實驗.實驗結果集中刪除了非常小或非常大的數(shù)據，如用戶之間的關注度小于0.005或大于10的數(shù)據，將感知用戶和任務編號，便于數(shù)據整理.

4.2 對比方法

在驗證對比方法中，首先我們選取文獻[19]的WF(water filing)算法，WF算法是移動感知網絡中的典型任務分配算法，該算法思想是根據最早空閑用戶優(yōu)先的原則，也就是說感知任務是最先分配給已經完成任務空閑下來的用戶.同時該算法是按照任務到達的順序進行分配，不管任務的緊急程度及對任務完成時間的要求.另一個對比算法是文獻[15]中的RU-AG算法，該算法是首先選擇最大效用值的任務工人，然后為了任務工人都能夠被選中，不以最小覆蓋為條件選擇最大效用值增加的任務工人，即被選擇的最大效用值增大的任務工人的覆蓋可能是最小也有可能不是最小.TDUATS算法是選擇感知任務的互關注度和時間監(jiān)督最相似的參與用戶作為任務分發(fā)對象.

4.3 感知用戶之間互關注影響比較

圖8～10中的縱軸表示接受者與發(fā)送者關注度差值，橫軸表示感知任務編號.

Fig. 8 OMT attention comparison圖8 OMT關注度比較

Fig. 9 MUST attention comparison圖9 MUST關注度比較

Fig.10 USTF attention comparison圖10 USTF關注度比較

圖8可以觀察出，TDUATS算法獲得的接受者與發(fā)送者之間相似性很強，因為TDUATS算法的感知任務發(fā)布者和接受者之間的OMT差值最小.而WF，RU-AG算法的OMT值較大，WF選擇最早空閑的參與者，不管其OMT值的大小，RU-AG選擇最大OMT值的參與者.

圖9顯示，TDUATS算法的MUST關注度好于WF和RU-AG算法.說明感知任務發(fā)布者和接受者之間MUST相似度高于WF和RU-AG算法的MUST關注度.

圖10可以看出算法的USTF關注度值都較小，WF和RU-AG算法的USTF值出現(xiàn)了較多負數(shù)，說明任務接受者和發(fā)送者之間關注度較弱，所以值較小.根據式(8),USTF值出現(xiàn)負數(shù)，是由于MUST和OMT值較大，因此發(fā)送者與接受者之間的關聯(lián)關系較弱.

4.4 任務時間監(jiān)督對執(zhí)行任務的影響

為了驗證感知任務數(shù)目對關注度和時間監(jiān)督的影響，我們使用了ParticipAct數(shù)據集[30]，該數(shù)據集是劍橋大學老師和學生攜帶移動設備在辦公、會議和城市環(huán)境中的移動軌跡數(shù)據.我們使用了數(shù)據集中用戶之間接觸次數(shù)、接觸時間、開始結束時間等相關信息.

圖11～13顯示的是感知任務數(shù)目增加對關注度影響,縱軸表示各個算法的關注度的和,橫軸表示感知任務數(shù)目.時間監(jiān)督中的推遲或提前時間Tad=120 s.

1) 關注度隨感知任務數(shù)目變化的影響

圖11中，每個感知任務的OMT關注度值是接受者與發(fā)送者的差.TDUATS算法是選擇接受者和發(fā)送者之間關注度差值最小,因此得到的總和最小.RU-AG選擇OMT值最大的參與者，因此總和最大.圖11也顯示隨感知任務數(shù)目的遞增，發(fā)送者和接受者之間的OMT差之和仍然最小.

Fig. 11 Influence of OMT attention on sensing task圖11 OMT關注度對感知任務影響

圖12中，每個感知任務的MUST關注度值是接受者與發(fā)送者的差.WF算法是選擇最早空閑的接受者接受感知任務，接受者和發(fā)送者之間的差值沒辦法保證總是最小，雖表現(xiàn)不錯，但比TDUATS還要大一些.

Fig. 12 Influence of MUST attention on sensing task圖12 MUST關注度對感知任務影響

圖13中，每個感知任務的USTF關注度值是接受者與發(fā)送者的差值.RU-AG算法的每個感知任務的USTF關注度值多數(shù)都是負值，一方面說明接受者和發(fā)布者直接關系不強，另一方面從式(8)可以看出發(fā)布者和接受者之間的OMT和MUST值較大.從實驗獲的數(shù)據也顯示OMT值比MUST和USTF大，也就是說OMT關注度較強，說明了發(fā)送者和接受者之間關聯(lián)性強.

Fig. 13 Influence of USTF attention on sensing task圖13 USTF關注度對感知任務影響

2) 起始監(jiān)督隨感知任務數(shù)目變化的影響

從圖14可以看出，TDUATS算法在每個組中獲得的起始監(jiān)督的數(shù)據質量非常優(yōu)和優(yōu)的數(shù)目比WF，RU-AG算法要多.WF算法顯示也不錯，是因為WF算法是利用最早空閑工人來感知任務；RU-AG算法是選擇最大的關注度，影響了感知任務的起始監(jiān)督.TDUATS算法的良好和合格數(shù)目較少，是因為選取每組感知任務數(shù)目都是50，如果優(yōu)及以上的數(shù)目多，良好和合格數(shù)目就可能不會比其他數(shù)目多，因為總數(shù)目是固定的.這也反過來說明TDUATS算法獲得的優(yōu)及以上等級數(shù)目較多.

Fig. 14 Influence of initial supervision on the number of sensing tasks圖14起始監(jiān)督隨感知任務數(shù)目變化影響

3) 執(zhí)行過程監(jiān)督隨感知任務數(shù)目變化的影響

圖15是感知任務的執(zhí)行過程監(jiān)督，劍橋大學[30]數(shù)據集中是沒有感知任務過程時間，我們采用接觸時間的比值來衡量.參與者的接觸時間是參與者完成某個感知任務的時間與該參與者完成所有任務的比值.這個比值如果大于0.67，就認為該參與者的執(zhí)行過程監(jiān)督為優(yōu)或非常優(yōu).從圖15可以看出隨感知任務數(shù)目增加，TDUATS算法根據關注度的相似程度，再選擇時間監(jiān)督相似，故表現(xiàn)得較好.WF算法根據其算法思想，在剛開始接受任務時，可以根據任務要求從空閑的參與者中快速選中接受者，所以在開始時表現(xiàn)得也還不錯.良好和合格數(shù)目的變化情況同圖14中的原因分析.

Fig. 15 Influence of execution process supervision on the number of sensing tasks圖15 執(zhí)行過程監(jiān)督隨感知任務數(shù)目變化影響

4) 任務完成監(jiān)督隨感知任務數(shù)目變化的影響

圖16是感知任務的完成監(jiān)督，TDUATS算法是先通過選擇關注度差最小的參與者，關注度越相似，越能說明它們可以很好地完成同一任務，完成任務的結束時間能夠達到發(fā)送者的要求.在感知任務數(shù)目不多的情況下，TDUATS算法優(yōu)勢不明顯，但隨著感知任務數(shù)目的增加，表現(xiàn)為優(yōu)和非常優(yōu)的數(shù)目增加較明顯.RU-AG算法選擇的感知任務時間變化較大，所以在發(fā)布的感知任務數(shù)目較多時，能夠選擇適合的接受者會不夠好.隨著感知任務數(shù)目的增加，TDUATS算法完成監(jiān)督的優(yōu)及以上數(shù)目還是有優(yōu)勢的.WF算法變化不大，RU-AG算法變化較大，都是由算法思想決定的.對于良好和合格數(shù)目的變化趨勢同圖14中的分析.

Fig. 16 Influence of task completion supervision on the number of sensing tasks圖16 任務完成監(jiān)督隨感知任務數(shù)目變化影響

5 總結及未來研究

本文首先分析了感知器網絡中的用戶和任務之間的關聯(lián)關系，構建任務和用戶之間的模型，形成用戶和感知任務之間的3種關注度：同一用戶勝任多種任務、多個用戶完成同一任務和用戶間互關注.其次，討論感知任務時間對感知任務的影響，對任務執(zhí)行過程分為起始監(jiān)督、執(zhí)行過程監(jiān)督和完成監(jiān)督，實現(xiàn)感知任務時間對任務執(zhí)行過程進行監(jiān)督.最后利用所提用戶關注度與時間監(jiān)督算法對感知任務進行分發(fā).

實驗表明：對于感知用戶動態(tài)分發(fā)感知任務，本文所提的TDUATS算法對比感知任務中典型的WF算法和RU-AG算法，雖出現(xiàn)部分感知任務不能被分發(fā)出去，但分發(fā)效率和精準度都有所提高.在OMT,MUST,USTF方面，TDUATS算法比WF算法分別提升約2.4%,4%,19%，比RU-AG算法分別提升約14.5%,9.3%,28.5%.從起始監(jiān)督、執(zhí)行過程監(jiān)督以及任務完成監(jiān)督方面分析，TDUATS算法在優(yōu)和非常優(yōu)方面比WF算法分別提升約6.5%,8.1%,7%，比RU-AG算法分別提升約21.9%,20.9%,10.3%.在將來的工作中，我們將對感知用戶協(xié)作關系、感知用戶和任務的關系、感知任務時間建模及更深入對任務執(zhí)行過程的影響進行研究，以形式化的方法刻畫它們之間的關系，以獲得更好的性能.

如何提升感知任務完成情況、防止感知用戶提交虛假數(shù)據、提高感知用戶的積極性等情況在感知任務分發(fā)中受很多因素影響.參與感知任務的用戶為了獲得高的報酬，用戶之間就會互相競爭獲取更多感知任務的機會；另一方面，感知任務在更復雜的分布式環(huán)境中如何進行任務管理和分發(fā)，參與用戶如何調度都將是我們繼續(xù)研究的方向.

作者貢獻聲明：張力負責本論文思路的提出、算法實驗和論文的撰寫等事宜；張書奎負責論文算法討論和整體質量把控；劉海、張洋在算法實驗中提出優(yōu)化；陶冶討論算法思路，使算法不斷完善；龍浩針對論文撰寫提出一些建議，使論文不斷完善；于淳清和祝啟鼎在論文字句修改中提出建議.以上各位都積極參與論文構想、撰寫、投稿、修改以及不斷完善.