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

1(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇蘇州 215006)

2(淮北師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽淮北 235099)

(greenwuhu@126.com)

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

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

Fig. 1 Location sensing task圖1 位置感知任務(wù)

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

本文主要貢獻(xiàn)包括3個(gè)方面：

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

2 任務(wù)關(guān)注度分析

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

2.1 用戶之間的相關(guān)性

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

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

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

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

Oi=Ntaski/Nui.

(1)

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

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

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

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

(2)

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

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

Fig. 6 Inter user sensing task圖6 用戶間感知任務(wù)

Ui表示第i個(gè)USTF,計(jì)算為

Ui=Ntaski∪taskj/2Nui+uj.

(3)

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

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

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

Xijk≈Yijk.

(4)

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

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

(5)

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

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個(gè)任務(wù)的OMT關(guān)注度，是感知任務(wù)用戶獲取的軌跡數(shù)據(jù)關(guān)注度、同一任務(wù)關(guān)注度和用戶任務(wù)間的互關(guān)注三者之間的度量關(guān)系，α是調(diào)節(jié)因子，本文中的α=0.6.式(7)、式(8)分別表示軌跡數(shù)據(jù)關(guān)注度OMT和USTF之間的度量關(guān)系、軌跡數(shù)據(jù)關(guān)注度OMT和MUST之間的度量關(guān)系.

2.2 時(shí)間監(jiān)督

感知任務(wù)時(shí)間通常被用來(lái)衡量感知任務(wù)是否執(zhí)行完成、完成所有感知任務(wù)時(shí)間最短、平均完成時(shí)間最小等問(wèn)題，對(duì)感知過(guò)程沒(méi)有具體化.

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

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

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

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

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

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

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

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

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

根據(jù)模糊規(guī)則和模糊集描述任務(wù)完成情況，模糊規(guī)則基于專家知識(shí)系統(tǒng)或經(jīng)驗(yàn).模糊規(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)”“良”“合格”“不夠好”.

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

3 感知任務(wù)模型

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

3.1 感知任務(wù)分發(fā)

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

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

3.2 TDUATS算法

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

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

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

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

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

① procedureTDUATS(URS,TS)

② 初始化URS,TS←0;

③ for (i=1;i

④ for (j=1;j

⑤ 計(jì)算用戶之間關(guān)注度強(qiáng)度URS[i];

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

⑦ end for

⑧ end for

⑨ for (i=1;i

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

3.3 算法性能分析

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

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

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

4 實(shí)驗(yàn)分析

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

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

4.2 對(duì)比方法

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

4.3 感知用戶之間互關(guān)注影響比較

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

Fig. 8 OMT attention comparison圖8 OMT關(guān)注度比較

Fig. 9 MUST attention comparison圖9 MUST關(guān)注度比較

Fig.10 USTF attention comparison圖10 USTF關(guān)注度比較

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

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

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

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

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

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

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

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

Fig. 11 Influence of OMT attention on sensing task圖11 OMT關(guān)注度對(duì)感知任務(wù)影響

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

Fig. 12 Influence of MUST attention on sensing task圖12 MUST關(guān)注度對(duì)感知任務(wù)影響

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

Fig. 13 Influence of USTF attention on sensing task圖13 USTF關(guān)注度對(duì)感知任務(wù)影響

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

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

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

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

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

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

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

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

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

5 總結(jié)及未來(lái)研究

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

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

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

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