基于數(shù)據(jù)冗余控制的移動(dòng)群智感知任務(wù)分配方法

摘要：移動(dòng)群智感知系統(tǒng)中任務(wù)之間存在時(shí)空覆蓋重疊性，這可能導(dǎo)致重復(fù)數(shù)據(jù)收集從而引發(fā)數(shù)據(jù)冗余問(wèn)題，為此，提出了一種可同時(shí)控制任務(wù)內(nèi)以及任務(wù)間數(shù)據(jù)冗余的任務(wù)分配方法。該方法首先提出基于長(zhǎng)短期記憶（LSTM）神經(jīng)網(wǎng)絡(luò)的軌跡序列預(yù)測(cè)模型，對(duì)任務(wù)參與者進(jìn)行細(xì)分時(shí)空單元的軌跡序列預(yù)測(cè)，然后根據(jù)軌跡預(yù)測(cè)結(jié)果提出最小化數(shù)據(jù)冗余的優(yōu)化模型。通過(guò)最小化時(shí)空單元的數(shù)據(jù)冗余度來(lái)控制單個(gè)任務(wù)內(nèi)的數(shù)據(jù)冗余問(wèn)題，并通過(guò)讓單個(gè)任務(wù)參與者在時(shí)空單元中的感知數(shù)據(jù)被最大化重復(fù)利用來(lái)控制多個(gè)任務(wù)之間時(shí)空覆蓋重疊性帶來(lái)的數(shù)據(jù)冗余。實(shí)驗(yàn)結(jié)果表明，提出的任務(wù)分配方法可以有效地減少任務(wù)內(nèi)及任務(wù)間的數(shù)據(jù)冗余。

關(guān)鍵詞：移動(dòng)群智感知； 數(shù)據(jù)冗余； 軌跡序列預(yù)測(cè)； 優(yōu)化模型

中圖分類號(hào)：TP393文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695（2022）08-024-2381-07

doi：10.19734/j.issn.1001-3695.2021.12.0700

Task allocation method based on data redundant control in mobile crowd sensing

He Xingyua，b， Zhao Dana， Yang Guisonga， Jin Zirib， Qin Yangkailongb， Wang Qipeib

（a.School of Optical-Electrical amp; Computer Engineering， b.College of Communication amp; Art Design， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract：Due to the overlap of time and space coverage between tasks in mobile crowd sensing， repeated data collection may happen and cause data redundancy problem. In view of this， this paper proposed a task allocation method to reduce data redundancy within and between tasks. Firstly， this method designed a trajectory sequence prediction model based on the long short-term memory （LSTM） neural network， to predict trajectory sequences of task participants within subdivided spatial-temporal units. Then based on the trajectory prediction results， the method proposed an optimization model to minimize data redundancy. Specifically， the optimization model constrained the data redundancy within a single task by minimizing the data redundancy metric in each spatial-temporal unit， and limited the data redundancy between multiple tasks by maximizing the reuse of the sensing data of each task participant in a spatial-temporal unit. Experimental results verify that the proposed task allocation method can effectively reduce the data redundancy within and between tasks.

Key words：mobile crowd sensing; data redundancy; trajectory sequence prediction; optimization model

0引言

移動(dòng)群智感知（mobile crowd sensing， MCS）作為一種利用移動(dòng)設(shè)備感知能力的新興物聯(lián)網(wǎng)感知模式，已受到學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注［1］。與傳統(tǒng)的靜態(tài)傳感器網(wǎng)絡(luò)相比，MCS利用嵌入在移動(dòng)設(shè)備中的傳感器和參與者的移動(dòng)性來(lái)感知周圍環(huán)境，在不花費(fèi)大量成本和時(shí)間的情況下實(shí)現(xiàn)了更廣泛的時(shí)空范圍覆蓋，它在環(huán)境監(jiān)測(cè)［2］、城市管理［3］等場(chǎng)景中已有廣泛應(yīng)用。

感知質(zhì)量和成本是移動(dòng)群智感知中的重要性能指標(biāo)［4］。感知質(zhì)量主要由時(shí)空覆蓋率衡量，成本控制一般體現(xiàn)在控制參與者的報(bào)酬。為了兼顧感知質(zhì)量和成本，一些研究在預(yù)算限制下實(shí)現(xiàn)任務(wù)的全覆蓋［5］或是覆蓋范圍的最大化［6］，另有一些研究在滿足覆蓋率的約束下實(shí)現(xiàn)感知成本的最小化［7，8］。為了進(jìn)一步控制感知成本，一些研究開(kāi)始關(guān)注任務(wù)分配中的數(shù)據(jù)冗余問(wèn)題。文獻(xiàn)［9］指出，當(dāng)任務(wù)達(dá)到一定的覆蓋率后，再增加參與者不會(huì)過(guò)多改善感知結(jié)果，反而會(huì)增加成本。

現(xiàn)有的任務(wù)分配策略主要關(guān)注單個(gè)任務(wù)中的數(shù)據(jù)冗余問(wèn)題。一些研究通過(guò)分析數(shù)據(jù)間的時(shí)空相關(guān)性［10，11］來(lái)實(shí)現(xiàn)高精度的數(shù)據(jù)推斷，從而避免數(shù)據(jù)冗余，以降低感知成本。另有一些研究考慮參與者的不確定性和不可控性，通過(guò)分析參與者的移動(dòng)特征來(lái)制定合理的任務(wù)分配方法。文獻(xiàn)［12，13］盡可能地減少為同一任務(wù)服務(wù)的多個(gè)參與者之間重復(fù)的數(shù)據(jù)收集工作，以減少數(shù)據(jù)冗余。為了保證數(shù)據(jù)收集的數(shù)量并且避免每個(gè)任務(wù)收集過(guò)多的冗余數(shù)據(jù)，文獻(xiàn)［14］定義冗余數(shù)據(jù)因子計(jì)算數(shù)據(jù)質(zhì)量。文獻(xiàn)［15］為每個(gè)任務(wù)收集的樣本數(shù)量定義最大上限閾值，從而避免了任務(wù)內(nèi)的數(shù)據(jù)冗余，但是忽略了任務(wù)之間的數(shù)據(jù)冗余。文獻(xiàn)［16］為了解決參與者之間上傳圖片的冗余問(wèn)題，提出了圖相似度模型以進(jìn)行細(xì)粒度的圖片選擇。文獻(xiàn)［17］在參與者與任務(wù)的匹配函數(shù)中引入任務(wù)冗余因子，以懲罰多余的任務(wù)分配，從而避免了單個(gè)任務(wù)內(nèi)的數(shù)據(jù)冗余并節(jié)省了預(yù)算，進(jìn)而有利于完成更多的任務(wù)。在壓縮感知范疇中，文獻(xiàn)［18］利用感知數(shù)據(jù)之間的隱式相關(guān)性來(lái)減少數(shù)據(jù)冗余，并選擇合適的用戶組以保證感知網(wǎng)格的時(shí)空覆蓋。文獻(xiàn)［19］研究了完全不存在數(shù)據(jù)冗余情況下的參與者選擇問(wèn)題，該方法假設(shè)參與者的感知區(qū)域是固定的。然而在移動(dòng)群智感知場(chǎng)景中，參與者是移動(dòng)的且參與者的移動(dòng)性會(huì)對(duì)感知質(zhì)量產(chǎn)生較大影響。

除了單個(gè)任務(wù)內(nèi)部存在數(shù)據(jù)冗余外，任務(wù)之間也存在數(shù)據(jù)冗余問(wèn)題。具體來(lái)說(shuō)，當(dāng)兩個(gè)任務(wù)需要來(lái)自同一時(shí)空單元的數(shù)據(jù)時(shí)，而這個(gè)時(shí)空單元的數(shù)據(jù)收集任務(wù)被兩個(gè)不同的參與者重復(fù)執(zhí)行將會(huì)帶來(lái)任務(wù)間的數(shù)據(jù)冗余。雖然現(xiàn)有的移動(dòng)群智感知任務(wù)分配方法有分析任務(wù)間的相關(guān)性［20，21］，其目標(biāo)通常是最小化成本。文獻(xiàn)［20］考慮任務(wù)間的時(shí)空包含關(guān)系，旨在最小化激勵(lì)成本。文獻(xiàn)［21］定義兩個(gè)任務(wù)之間的相關(guān)性指標(biāo)，目的也在于降低參與者的參與成本。這些研究都忽略了任務(wù)之間的相關(guān)性對(duì)于冗余控制的影響，尤其是忽略了多個(gè)任務(wù)之間時(shí)空覆蓋重疊性帶來(lái)的數(shù)據(jù)冗余問(wèn)題。另外，降低多個(gè)任務(wù)之間的數(shù)據(jù)冗余問(wèn)題極具挑戰(zhàn)性，因?yàn)橐紤]不同任務(wù)的時(shí)空粒度，同時(shí)還要兼顧數(shù)據(jù)質(zhì)量和計(jì)算激勵(lì)報(bào)酬等方面的差異性。

為了實(shí)現(xiàn)任務(wù)分配過(guò)程中的數(shù)據(jù)冗余控制以及解決上述挑戰(zhàn)，本文需要預(yù)測(cè)參與者未來(lái)一段時(shí)間內(nèi)較長(zhǎng)的移動(dòng)軌跡序列?，F(xiàn)有研究通常使用深度學(xué)習(xí)方法［22］、馬爾可夫模型［23］及基于參與者歷史信息的概率模型或統(tǒng)計(jì)結(jié)果［20，24］對(duì)參與者軌跡進(jìn)行預(yù)測(cè)分析。然而，實(shí)現(xiàn)較長(zhǎng)軌跡序列預(yù)測(cè)時(shí)，普通循環(huán)神經(jīng)網(wǎng)絡(luò)（RNN）在解決長(zhǎng)期依賴和上下文泛化方面存在局限性，馬爾可夫模型隨著序列長(zhǎng)度的增加，復(fù)雜度也快速增加，而基于概率模型或統(tǒng)計(jì)分析的方法準(zhǔn)確度較低。相比之下，長(zhǎng)短期記憶（LSTM）神經(jīng)網(wǎng)絡(luò)更適合有效處理長(zhǎng)序列訓(xùn)練過(guò)程中的梯度消失和梯度爆炸問(wèn)題，所以本文利用LSTM神經(jīng)網(wǎng)絡(luò)實(shí)現(xiàn)參與者長(zhǎng)軌跡序列的預(yù)測(cè)。通常使用LSTM神經(jīng)網(wǎng)絡(luò)的軌跡預(yù)測(cè)模型將短期內(nèi)的歷史信息序列作為輸入得到未來(lái)移動(dòng)軌跡序列［25］，本文為了提高預(yù)測(cè)準(zhǔn)確度，分析了參與者的長(zhǎng)期軌跡信息，構(gòu)建長(zhǎng)期訪問(wèn)概率矩陣并作為模型的輸入，使用LSTM神經(jīng)網(wǎng)絡(luò)并借助編碼器—解碼器框架實(shí)現(xiàn)對(duì)參與者一段時(shí)間內(nèi)的連續(xù)軌跡序列預(yù)測(cè)。

綜上所述，本文通過(guò)利用LSTM神經(jīng)網(wǎng)絡(luò)分析參與者的未來(lái)移動(dòng)軌跡序列，并進(jìn)一步提出一種在滿足感知質(zhì)量約束的同時(shí)控制任務(wù)內(nèi)以及任務(wù)間數(shù)據(jù)冗余的任務(wù)分配方法。

為了對(duì)參與者未來(lái)移動(dòng)軌跡進(jìn)行更精確的預(yù)測(cè)，本文分析了參與者的長(zhǎng)期訪問(wèn)概率，定義了與參與者軌跡時(shí)空相關(guān)的訪問(wèn)概率矩陣，提出了基于長(zhǎng)短期記憶神經(jīng)網(wǎng)絡(luò)的參與者移動(dòng)軌跡序列預(yù)測(cè)模型，以提高軌跡預(yù)測(cè)的準(zhǔn)確度。

為了控制成本，基于參與者的移動(dòng)軌跡，本文提出了一種最小化數(shù)據(jù)冗余度的優(yōu)化模型，一方面通過(guò)細(xì)粒度時(shí)隙劃分的方法最小化時(shí)空單元的數(shù)據(jù)冗余度，從而控制單個(gè)任務(wù)內(nèi)的數(shù)據(jù)冗余問(wèn)題；另一方面，分析多個(gè)感知任務(wù)之間的時(shí)空覆蓋重疊性，使參與者在時(shí)空單元中的感知數(shù)據(jù)被多個(gè)任務(wù)最大化重復(fù)利用，從而減少任務(wù)間的數(shù)據(jù)冗余，降低平臺(tái)的成本。

1系統(tǒng)模型和問(wèn)題定義

在本系統(tǒng)中，一天被劃分成K個(gè)等長(zhǎng)的時(shí)段，所有時(shí)段的集合為T={T1，T2，…，TK}，其中第k個(gè)時(shí)段表示為Tk，1≤k≤K。將MCS活動(dòng)區(qū)域劃分成G個(gè)網(wǎng)格，所有區(qū)域的集合為R={R1，R2，…，RG}，其中第g個(gè)分區(qū)表示為Rg，1≤g≤G，網(wǎng)格分區(qū)易于實(shí)現(xiàn)且高度可擴(kuò)展，可以通過(guò)調(diào)整網(wǎng)格的寬度和長(zhǎng)度實(shí)現(xiàn)不同的粒度控制。

系統(tǒng)中發(fā)布一系列的群智感知任務(wù)，M個(gè)任務(wù)構(gòu)成任務(wù)集S={s1，s2，…，si，…，sM}，對(duì)于任意一個(gè)任務(wù)si∈S，其都存在要求的時(shí)間范圍Tsi={Tsi1，…，Tsip，…}及空間范圍Rsi={Rsi1，…，Rsiq，…}，其中Tsip表示任務(wù)需要感知的時(shí)段，為系統(tǒng)劃分的T中的任意一個(gè)指定的時(shí)段，即Tsip∈T，其中1≤p≤|Tsip|，|Tsip|表示任務(wù)si要求感知的時(shí)段個(gè)數(shù)。Rsiq表示任務(wù)需要感知的分區(qū)，為系統(tǒng)劃分的R中的任意一個(gè)指定的區(qū)域，即Rsiq∈R，其中1≤q≤|Rsi|，|Rsi|為任務(wù)si要求感知的分區(qū)個(gè)數(shù)。假設(shè)系統(tǒng)中存在N個(gè)參與者W={w1，w2，…，wj，…，wN}，對(duì)于任意一個(gè)參與者wj∈W都熟知系統(tǒng)中的任務(wù)詳情，隨時(shí)可以參與任務(wù)。

對(duì)于每個(gè)任務(wù)si，它具有任務(wù)分配的報(bào)酬支付預(yù)算Bsi，并且要求參與者必須處于感知時(shí)間范圍Tsi及空間范圍Rsi內(nèi)才能夠?yàn)槿蝿?wù)提供有效的感知數(shù)據(jù)。為了便于表示任務(wù)的完成情況，將任務(wù)si中的任意一個(gè)時(shí)段Tsip與任意一個(gè)分區(qū)Rsiq形成的二元組定義為時(shí)段—分區(qū)對(duì)，任務(wù)si包含的時(shí)段—分區(qū)對(duì)構(gòu)成的集合表示為TSsi={（Tsip，Rsiq）|Tsip∈Tsi，Rsiq∈Rsi}。為了確保返回的感知結(jié)果的質(zhì)量，需要在每個(gè)時(shí)段—分區(qū)對(duì)中實(shí)現(xiàn)收集至少L個(gè)感知數(shù)據(jù)報(bào)告。

為了使任務(wù)在其時(shí)段—分區(qū)對(duì)中收集的數(shù)據(jù)均衡分布以及降低數(shù)據(jù)冗余，現(xiàn)對(duì)時(shí)段進(jìn)行進(jìn)一步的細(xì)粒度劃分，將每個(gè)時(shí)段劃分成L個(gè)等長(zhǎng)的時(shí)隙，例如將時(shí)段Tk劃分成L個(gè)時(shí)隙tk（1），…，tk（τ），…，tk（L），其中tk（τ）表示時(shí)段Tk中的第τ個(gè)時(shí)隙。將細(xì)分后的時(shí)隙與分區(qū)二元組命名為時(shí)空單元，因此一個(gè)時(shí)段—分區(qū)對(duì)包含L個(gè)時(shí)空單元。例如任務(wù)si的某個(gè)時(shí)段—分區(qū)對(duì)（Tsip，Rsiq）經(jīng)過(guò)細(xì)粒度劃分后的時(shí)空單元可以表示為（Tsip（1），Rsiq），（Tsip（2），Rsiq），…，（Tsip（τ），Rsiq），…，（Tsip（L），Rsiq），其中Tsip（τ）表示時(shí)段Tsip劃分出的第τ個(gè)時(shí)隙。因此，在每個(gè)任務(wù)內(nèi)，為了使收集的數(shù)據(jù)分布更加均衡，希望每個(gè)時(shí)段分區(qū)對(duì)所收集的數(shù)據(jù)都均衡地分布在其劃分的每個(gè)時(shí)空單元中。另外，對(duì)于每個(gè)參與者wj，由于受到設(shè)備等其他因素的限制，每個(gè)參與者在系統(tǒng)中最多可參與ω個(gè)時(shí)空單元的數(shù)據(jù)收集工作。

如圖1所示，假設(shè)任務(wù)s1時(shí)間范圍Ts1={T2，T3}，空間范圍Rs1={R1，R2，R3}，任務(wù)s2時(shí)間范圍Ts2={T3，T4}，空間范圍Rs2={R3，R4}，則有時(shí)段—分區(qū)對(duì)構(gòu)成的集合TSs1={（T2，R1），（T2，R2），（T2，R3），（T3，R1），（T3，R2），（T3，R3）}，如圖中綠色框和藍(lán)色框所示（見(jiàn)電子版），TSs2={（T3，R3），（T3，R4），（T4，R3），（T4，R4）}，如圖中橙色框和藍(lán)色框所示。以時(shí)段T3為例，為了使數(shù)據(jù)在T3內(nèi)分布均衡，將T3進(jìn)一步劃分成三個(gè)時(shí)隙t3（1）、t3（2）和t3（3），那么本文將在任務(wù)分配方法中針對(duì)每個(gè)時(shí)段—分區(qū)對(duì)包含的時(shí)空單元進(jìn)行任務(wù)分配，使得收集的數(shù)據(jù)均衡分布在每個(gè)細(xì)分的時(shí)空單元內(nèi)，而不是都集中于同一個(gè)時(shí)空單元，以控制每個(gè)時(shí)空單元的數(shù)據(jù)冗余。另外，任務(wù)s1和s2存在相同的時(shí)段—分區(qū)對(duì)（T3，R3） ，如圖中藍(lán)色框所示，此時(shí)時(shí)空單元（t3（1），R3） 、（t3（2），R3） 、（t3（3），R3）均僅需要一份數(shù)據(jù)報(bào)告即可滿足兩個(gè)任務(wù)的數(shù)據(jù)收集需求。如果忽略任務(wù)s1和s2之間的時(shí)空重疊性，將這三個(gè)時(shí)空單元的數(shù)據(jù)收集任務(wù)獨(dú)立地分配給不同的參與者，不僅會(huì)產(chǎn)生重復(fù)收集數(shù)據(jù)而且會(huì)導(dǎo)致重復(fù)開(kāi)銷。本文將通過(guò)在任務(wù)分配方法中最大化每個(gè)時(shí)空單元收集數(shù)據(jù)在多個(gè)任務(wù)之間的重復(fù)利用率來(lái)降低任務(wù)之間的數(shù)據(jù)冗余。

2任務(wù)參與者軌跡預(yù)測(cè)模型

為了向任務(wù)分配合適的參與者，需要預(yù)測(cè)參與者在不同時(shí)空單元的移動(dòng)軌跡，于是本文設(shè)計(jì)了一個(gè)基于長(zhǎng)短期記憶（LSTM）神經(jīng)網(wǎng)絡(luò)的參與者移動(dòng)軌跡序列預(yù)測(cè)模型。相比于根據(jù)歷史記錄直接采用基于統(tǒng)計(jì)的模型來(lái)推導(dǎo)參與者訪問(wèn)時(shí)空單元的狀態(tài)，本文使用LSTM可以實(shí)現(xiàn)更精確的參與者軌跡預(yù)測(cè)。預(yù)測(cè)模型如圖2所示，包含編碼器和解碼器兩個(gè)部分，其中編碼器用來(lái)處理數(shù)據(jù)的輸入，解碼器用來(lái)處理數(shù)據(jù)的輸出，每個(gè)部分均含有L個(gè)LSTM單元。

由于任務(wù)參與者在歷史中經(jīng)常訪問(wèn)的地方，在未來(lái)還有很大可能再次訪問(wèn)。為了分析影響預(yù)測(cè)軌跡序列訪問(wèn)概率的特征，定義了與參與者軌跡時(shí)空相關(guān)的訪問(wèn)概率矩陣，因?yàn)闅v史記錄中經(jīng)常訪問(wèn)的地方，在未來(lái)還有很大可能再次訪問(wèn)。在此基礎(chǔ)上形成預(yù)測(cè)模型的輸入，對(duì)應(yīng)圖2中編碼器部分的P1～PL。

訪問(wèn)概率矩陣表示參與者wj在歷史統(tǒng)計(jì)周期中在時(shí)段Tk的各個(gè)時(shí)隙中訪問(wèn)的各個(gè)分區(qū)的概率，用概率矩陣P表示。

P=p（tk（1），R1）p（tk（1），R2）…p（tk（1），Rg）…p（tk（1），RG）

p（tk（2），R1）p（tk（2），R2）…p（tk（2），Rg）…p（tk（2），RG）

p（tk（τ），R1）p（tk（τ），R2）…p（tk（τ），Rg）…p（tk（τ），RG）

p（tk（L），R1）p（tk（L），R2）…p（tk（L），Rg）…p（tk（L），RG）

（1）

其中：元素p（tk（τ），Rg）表示在歷史記錄中參與者wj在Tk的時(shí)隙tk（τ）訪問(wèn)分區(qū)Rg的概率。例如，在過(guò)去的七天歷史記錄中，參與者在時(shí)隙tk（1）有兩次訪問(wèn)分區(qū)R1，有一次訪問(wèn)分區(qū)R2，有四次訪問(wèn)分區(qū)R3，則有p（tk（1），R1）=2/7，p（tk（1），R2）=1/7，p（tk（1），R3）=4/7。

如果將矩陣P的第一行記為P1，第τ行記為Pτ，第L行記為PL，則L個(gè)時(shí)間步的輸入可以記為IN={P1，P2，…，Pτ，…，PL}，IN中L個(gè)元素分別對(duì)應(yīng)編碼器中L個(gè)單元的輸入。為了便于表示，將第τ個(gè)單元的輸入Pτ記為時(shí)間步τ的輸入，1≤τ≤L。同時(shí)為了在不明顯降低性能的情況下加快收斂過(guò)程，首先將每一個(gè)輸入通過(guò)嵌入層嵌入到θ維的嵌入向量，時(shí)間步τ的輸入Pτ的嵌入向量為eτ，如式（2）所示。然后將嵌入向量作為該時(shí)間步單元的輸入，獲得時(shí)間步τ的隱藏狀態(tài)hτ，如式（3）所示。

eτ=φ（WePτ）（2）

hτ=LSTM（Wenc［hτ-1，eτ］）（3）

其中：φ（·）是由非線性激活函數(shù)ReLU表示的嵌入層函數(shù)；We是嵌入權(quán)重；eτ是時(shí)間步τ的輸入，為輸入信息的嵌入向量；hτ-1是上個(gè)時(shí)間步得到的隱藏狀態(tài)；Wenc是LSTM中的可學(xué)習(xí)參數(shù)，在每個(gè)輸入時(shí)間步權(quán)重參數(shù)Wenc是共享的。具體來(lái)說(shuō)，當(dāng)前時(shí)間步τ的隱藏狀態(tài)由上一時(shí)間步的隱藏狀態(tài)和當(dāng)前時(shí)間步的輸入得出。

將輸入時(shí)間步1～L形成的上下文向量表示為

H=f（h1，h2，…，hL）（4）

其含義是所有輸入時(shí)間步的隱含特征，由所有輸入時(shí)間步的隱藏狀態(tài)組成。

在預(yù)測(cè)輸出階段，第τ個(gè)輸出單元的隱藏狀態(tài)h′τ的計(jì)算如下：

h′τ=LSTM（Wdec［h′τ－1，yτ－1，H］）（5）

其中：h′τ－1表示上一輸出時(shí)間步的隱藏狀態(tài)；yτ－1表示上一個(gè)時(shí)間步的輸出；H是所有輸入時(shí)間步形成的上下文向量；Wdec表示解碼器中的學(xué)習(xí)權(quán)重參數(shù)。

第τ個(gè)時(shí)間步的輸出為

yτ=Rwj，tk（τ）=softmax（hτ－1）（6）

由此可以得出，參與者wj在時(shí)段Tk的預(yù)測(cè)軌跡序列Trapre（wj，Tk）={Rwj，tk（1），Rwj，tk（2），…，Rwj，tk（τ），…，Rwj，tk（L）}。

3冗余控制的任務(wù)分配方法

3.1任務(wù)分配優(yōu)化模型

本文定義參與者wj關(guān)于時(shí)空單元（tk（τ），Rg）的訪問(wèn)指針Ywjtk（τ），Rg，如果預(yù)測(cè)出參與者wj在時(shí)段Tk中時(shí)隙tk（τ）將訪問(wèn)分區(qū)Rg，則令Ywjtk（τ），Rg=1，否則為0，即

Ywjtk（τ），Rg=1如果Rwj，tk（τ）=Rg0否則 （7）

類似地，對(duì)于每個(gè)任務(wù)，用YwjTsip（τ），Rsiq=1表示參與者wj將在任務(wù)si的Tsip（τ）時(shí)隙訪問(wèn)分區(qū)Rsiq。

若用0-1決策變量Xij=1表示將任務(wù)si分配給參與者wj，那么任務(wù)si的時(shí)空單元（Tsip（τ），Rsiq）預(yù)計(jì)收集數(shù)據(jù)樣本數(shù)量如式（8）所示，任務(wù)si在時(shí)段—分區(qū)對(duì)（Tsip，Rsiq）預(yù)計(jì)收集數(shù)據(jù)樣本數(shù)量如式（9）所示，其中C（·）表示計(jì)數(shù)函數(shù)。

C（Tsip（τ），Rsiq）=∑Nj=1YwjTsip（τ），RsiqXij（8）

C（Tsip，Rsiq）=∑Lτ=1C（Tsip（τ），Rsiq）（9）

對(duì)于單個(gè)任務(wù)，將任務(wù)的一個(gè)時(shí)段—分區(qū)對(duì)的數(shù)據(jù)冗余度定義為時(shí)段分區(qū)對(duì)中收集的數(shù)據(jù)數(shù)量與覆蓋的時(shí)空單元數(shù)量的比值，計(jì)算如下：

dr（Tsip，Rsiq）=C（Tsip，Rsiq）∑Lτ=1cov（Tsip（τ），Rsiq）（10）

該公式的計(jì)算前提是該時(shí)段分區(qū)滿足任務(wù)的最低感知要求。其中式（10）中的cov（Tsip（τ），Rsiq）用來(lái)表示時(shí)空單元是否被覆蓋，計(jì)算如下：

cov（Tsip（τ），Rsiq）=1如果C（Tsip（τ），Rsiq）≥10否則 （11）

系統(tǒng)中多個(gè)任務(wù)之間可能存在時(shí)空覆蓋重疊性，也就是說(shuō)，多個(gè)任務(wù)之間包含相同的時(shí)段—分區(qū)對(duì)。為了降低任務(wù)間因時(shí)空覆蓋重疊性帶來(lái)的數(shù)據(jù)冗余，本文將讓參與者wj在同一時(shí)空單元感知的數(shù)據(jù)盡可能被多個(gè)任務(wù)重復(fù)利用，其重復(fù)利用度定義為參與者在這一時(shí)空單元所參與的任務(wù)數(shù)量，計(jì)算如下：

overlap（tk（τ），Rg）（wj）=∑Mi=1Ywjtk（τ），RgXij（12）

參與者wj在單個(gè)時(shí)空單元（tk（τ），Rg）中可獲得的報(bào)酬定義為單個(gè)任務(wù)支付的固定單位報(bào)酬和重疊任務(wù)經(jīng)過(guò)折扣系數(shù)加權(quán)后的報(bào)酬之和，參與者在一個(gè)時(shí)空單元可獲得的報(bào)酬總和由數(shù)據(jù)的重復(fù)利用度決定，計(jì)算如下：

pay（tk（τ），Rg）（wj）=u+γu［overlap（tk（τ），Rg）（wj）－1］（13）

其中：u為單位報(bào)酬；γ為折扣因子參數(shù)，0≤γ≤1。如果參與者提供的數(shù)據(jù)被更多的任務(wù)利用，其將獲得更高的報(bào)酬。

參與者wj獲得的報(bào)酬由重疊的任務(wù)平均支付。任務(wù)si在單個(gè)時(shí)空單元（Tsip（τ），Rsiq）對(duì)參與者wj支付的報(bào)酬計(jì)算如下：

pay（Tsip（τ），Rsiq）（wj，si）=pay（tk（τ），Rg）（wj）overlap（tk（τ），Rg）（wj）（14）

其中：Tsip=Tk。

因此任務(wù)si關(guān)于所有時(shí)段分區(qū)的報(bào)酬支出總和為

pay（si）=∑|Rsi|q=1 ∑|Tsi|p=1 ∑Lτ=1 ∑Nj=1pay（Tsip（τ），Rsiq）（wj，si）（15）

本文的第一個(gè)優(yōu)化目標(biāo)為降低任務(wù)內(nèi)的數(shù)據(jù)冗余，使每個(gè)時(shí)段分區(qū)對(duì)收集到的數(shù)據(jù)盡可能均衡地分布在各個(gè)時(shí)空單元中；第二個(gè)優(yōu)化目標(biāo)為最大化每個(gè)參與者在同一時(shí)空單元感知數(shù)據(jù)的重復(fù)利用度，即降低任務(wù)間的數(shù)據(jù)冗余。優(yōu)化目標(biāo)如下：

mindr（Tsip，Rsiq）maxoverlap（tk（τ），Rg）（wj） （16）

約束為

pay（si）≤Bsi（17-1）

C（Tsip，Rsiq）≥L（17-2）

∑Gg=1 ∑Kk=1 ∑Lτ=1overlap（tk（τ），Rg）（wj）≤ω（17-3）

其中：約束式（17-1）表示對(duì)于每個(gè)任務(wù)si，其報(bào)酬支付應(yīng)不超過(guò)預(yù)算限制Bsi；約束式（17-2）表示對(duì)于每個(gè)任務(wù)，其各個(gè)時(shí)段—分區(qū)對(duì)的收集樣本數(shù)量不少于閾值L；約束式（17-3）表示每個(gè)參與者可參與的時(shí)空單元數(shù)量不超過(guò)ω個(gè)。

3.2任務(wù)分配優(yōu)化模型求解

本文所要解決的問(wèn)題為式（16）的優(yōu)化問(wèn)題，采用運(yùn)行速度快且應(yīng)用性較強(qiáng)的遺傳算法來(lái)求解?？紤]到細(xì)分的時(shí)空單元，本文問(wèn)題求解空間較大，初始種群中的個(gè)體難以接近最優(yōu)解，為了以較低的成本取得較好的結(jié)果，本文結(jié)合貪婪算法和遺傳算法，提出基于混合遺傳算法的任務(wù)分配方法。下面將詳細(xì)地介紹本文算法。

a）分配矩陣表示。本文要解決的問(wèn)題是減少數(shù)據(jù)冗余的任務(wù)分配，采用0-1決策變量構(gòu)成的矩陣結(jié)構(gòu)來(lái)表示任務(wù)分配的解，矩陣的行和列分別對(duì)應(yīng)M個(gè)任務(wù)和N個(gè)參與者，M行N列的分配矩陣X表示為{Xij（i=1，2，…，M;j=1，2，…，N）}，Xij為0或1。當(dāng)?shù)趇行的第j個(gè)元素為1時(shí)，則表示任務(wù)si被分配給編號(hào)為j的參與者wj，否則不被分配。分配矩陣示例如下所示。

w1w2…wj…wN

s1s2sM-2sM-1sM00…0…0

10…1…1

11…0…001…1…101…1…1

例如，假設(shè)共有3個(gè)任務(wù)5個(gè)參與者，參與者w1分配給任務(wù)s1、s2，w2分配給任務(wù)s1，w3分配給任務(wù)s3，w4分配給任務(wù)s2，w5分配給任務(wù)s1、s2和s3，則分配矩陣X可以表示為

X=11001

10011

00101（18）

b）初始化種群。初始群體是搜索開(kāi)始時(shí)的一組染色體，其影響著算法結(jié)果的好壞，隨機(jī)生成的染色體可能不能每次都滿足本文問(wèn)題的約束條件。為了保證種群的多樣性，本文引入貪心算子，對(duì)不滿足問(wèn)題約束條件的個(gè)體進(jìn)行改進(jìn)，如算法1所示。

算法1種群初始化

輸入： 任務(wù)集S，參與者集W，種群規(guī)模PopSize。

輸出： 初始種群，即個(gè)體X1～XPopSize。

（a）令k=1。

（b）如果kgt;PopSize，輸出X1～XPopSize；否則令W′=W。

（c）對(duì)于Xk中每個(gè)元素隨機(jī)以0或1賦值，令i=1，j=1。

（d）如果igt;M，跳轉(zhuǎn)到步驟h）；否則對(duì)于Xk的第i行執(zhí)行步驟（e）（f）。

（e）計(jì)算每個(gè)參與者的已分配時(shí)空單元數(shù)量，如果wj已分配的時(shí)空單元大于ω，即不滿足式（17-3），則令Xij［i］［j］=0并將wj從W′中移除；

（f）計(jì)算si的各個(gè)時(shí)段—分區(qū)對(duì)的收集數(shù)據(jù)量，如果存在時(shí)段—分區(qū)對(duì)數(shù)據(jù)量小于L，即不滿足式（17-2），貪婪地從W′中選擇產(chǎn)生數(shù)據(jù)冗余度最小的參與者，直至不存在不滿足數(shù)據(jù)量的時(shí)段分區(qū)對(duì)或W′=。

（g）令i=i+1，跳轉(zhuǎn)到步驟（d）；

（h）令k=k+1，跳轉(zhuǎn)到步驟（b）。

c）適應(yīng)度函數(shù)。本文為了降低任務(wù)分配的數(shù)據(jù)冗余量，冗余量越小，適應(yīng)性越好。因此個(gè)體Xk的適應(yīng)度函數(shù)與數(shù)據(jù)冗余量相關(guān)，計(jì)算為

1fitness（Xk）=DR（Xk）∑PopSizek=1DR（Xk）（19）

其中：DR（Xk）表示分配方案Xk產(chǎn)生的數(shù)據(jù)冗余量。

DR（Xk）=DR1（Xk）+DR2（Xk）（20）

其中：DR1（Xk）和DR2（Xk）分別表示該分配方案在任務(wù)內(nèi)及任務(wù)間產(chǎn)生的數(shù)據(jù)冗余量，計(jì)算公式分別如下：

DR1（Xk）=∑Mi=1 ∑|Rsi|q=1 ∑|Tsi|p=1dr（Tsip，Rsiq）（21）

DR2（Xk）=∑Gg=1 ∑Kk=1 ∑Lτ=1max（overlap（tk（τ），Rg））num（tk（τ），Rg）（22）

其中：max（overlap（tk（τ），Rg））表示時(shí)空單元（tk（τ），Rg）分配的所有參與者中最大的數(shù)據(jù)利用量；num（tk（τ），Rg）表示該時(shí)空單元實(shí)際存在的重疊任務(wù)數(shù)量。

d）選擇。選擇算子是將適應(yīng)度更高的個(gè)體傳遞給下一代，將適應(yīng)度低的個(gè)體淘汰。因?yàn)檫m應(yīng)度低的個(gè)體也可能含有好的基因，所有本文使用輪盤賭輪盤方法來(lái)選擇要保留的個(gè)體。

e）交叉。本文以矩陣的行為單位進(jìn)行部分匹配交叉操作。隨機(jī)選擇兩個(gè)個(gè)體作為父節(jié)點(diǎn)并設(shè)置交叉點(diǎn)，然后交換兩個(gè)父節(jié)點(diǎn)所設(shè)定交叉點(diǎn)所在的行生成兩個(gè)新個(gè)體。如果新個(gè)體超過(guò)參與者的執(zhí)行能力，則重新設(shè)置交叉點(diǎn)，直至滿足式（17-3）。

f）變異。為了避免算法結(jié)果陷入局部最優(yōu)并加快算法收斂速度，本文隨機(jī)地在矩陣中選擇變異元素，將元素1變?yōu)?，元素0變?yōu)?，同時(shí)要驗(yàn)證變異后的個(gè)體是否滿足任務(wù)的最低需求，即式（17- 2）。

g）終止。當(dāng)?shù)螖?shù)達(dá)到最大進(jìn)化代數(shù)時(shí)終止運(yùn)行。

算法2為提出的任務(wù)分配方法的執(zhí)行過(guò)程。

算法2任務(wù)分配算法

輸入： 任務(wù)集S，參與者集W。

輸出： 分配矩陣Xbest。

a）根據(jù)算法1初始化種群，即產(chǎn)生個(gè)體X1～XPopSize。

b）初始化迭代次數(shù)，令I(lǐng)ter=0。

c）根據(jù)式（19）計(jì)算種群中個(gè)體適應(yīng)度。

d）更新當(dāng)前最佳個(gè)體Xbest。

e）通過(guò)輪盤賭選擇適應(yīng)度高的個(gè)體。

f）對(duì)選擇的個(gè)體進(jìn)行按行交叉操作。

g）選擇個(gè)體以預(yù)定義概率進(jìn)行突變，將元素1變?yōu)?，元素0變?yōu)?。

h）令I(lǐng)ter=Iter+1，達(dá)到迭代閾值則停止迭代；否則跳轉(zhuǎn)到步驟c）。

i）輸出最佳個(gè)體Xbest。

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

針對(duì)MCS中的任務(wù)分配問(wèn)題，本文綜合考慮了任務(wù)的時(shí)空屬性及感知質(zhì)量要求、參與者的未來(lái)可能軌跡序列等因素，以最小化任務(wù)內(nèi)的數(shù)據(jù)冗余度及最大化任務(wù)間的感知數(shù)據(jù)利用率為目標(biāo)，基于遺傳算法設(shè)計(jì)了一種減少感知成本的任務(wù)分配算法。為了評(píng)估本文方法的性能，在Python中首先對(duì)本文的預(yù)測(cè)方法準(zhǔn)確度進(jìn)行了實(shí)驗(yàn)對(duì)比，然后對(duì)任務(wù)分配算法的效率進(jìn)行了實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)的主要參數(shù)設(shè)置如表1所示。

4.1對(duì)比算法

為了評(píng)估本文算法，將以下兩種算法（細(xì)粒度的多任務(wù)分配算法（MTPS）［15］、啟發(fā)式參與者招募機(jī)制（CAPR）［21］）作為基線，針對(duì)在不同任務(wù)數(shù)量上的情況進(jìn)行性能比較。

1）細(xì)粒度的多任務(wù)分配算法（MTPS）該算法采用集中式方法在總預(yù)算限制下，根據(jù)效用函數(shù)使用迭代貪婪的過(guò)程優(yōu)化分配，以實(shí)現(xiàn)感知質(zhì)量最大化。MTPS中設(shè)計(jì)了合理的激勵(lì)函數(shù)并對(duì)任務(wù)進(jìn)行了細(xì)粒度的周期劃分，是較典型的控制任務(wù)內(nèi)數(shù)據(jù)冗余的方法。

2）啟發(fā)式參與者招募機(jī)制（CAPR）該方法考慮任務(wù)間及參與者間的相關(guān)性（包括正相關(guān)和負(fù)相關(guān)）進(jìn)行參與者招募，提出三階段的啟發(fā)式參與者招募機(jī)制，以降低參與者成本并實(shí)現(xiàn)平臺(tái)效用最大化。雖然CAPR沒(méi)有直接實(shí)現(xiàn)任務(wù)間數(shù)據(jù)冗余控制，但該機(jī)制定義任務(wù)間的相關(guān)函數(shù)并在分配過(guò)程中考慮任務(wù)之間的相關(guān)性，可以在一定程度上降低任務(wù)間的數(shù)據(jù)冗余。

關(guān)于CAPR中定義的任意兩個(gè)任務(wù)si和si′間的相關(guān)函數(shù)S（si，si′）在本文中用時(shí)空覆蓋重疊率衡量，具體計(jì)算如式（23）所示。另外，由于本文忽略參與者的信譽(yù)因素，所以在CAPR中將參與者信譽(yù)值設(shè)置為常數(shù)1。

S（si，si′）=0TSsi∩TSsi′=

1TSsiTSsi′或TSsi′TSsi

|TSsi∩TSsi′||TSsi∪TSsi′|其他 （23）

其含義：當(dāng)任務(wù)si和si′不存在時(shí)空重疊時(shí)，兩者的相關(guān)系數(shù)為0；當(dāng)一個(gè)任務(wù)含于另一個(gè)任務(wù)時(shí)，兩者的相關(guān)系數(shù)為1；否則，兩者的相關(guān)系數(shù)為任務(wù)的時(shí)段—分區(qū)對(duì)的交集數(shù)與并集數(shù)的比值，此時(shí)S（si，si′）∈（0，1）。

4.2評(píng)估指標(biāo)

為了驗(yàn)證本文方法的有效性，首先對(duì)預(yù)測(cè)方法的準(zhǔn)確性進(jìn)行了實(shí)驗(yàn)分析；然后根據(jù)任務(wù)執(zhí)行率、數(shù)據(jù)冗余率和感知成本三項(xiàng)指標(biāo)對(duì)任務(wù)分配算法進(jìn)行評(píng)估，分析任務(wù)數(shù)量的變化對(duì)三項(xiàng)指標(biāo)的影響。

1）任務(wù)執(zhí)行率

本文將任務(wù)執(zhí)行率定義為分配成功的任務(wù)數(shù)量（即滿足最低感知質(zhì)量的任務(wù)）與系統(tǒng)總?cè)蝿?wù)數(shù)量的比值，任務(wù)執(zhí)行率為［0， 1］。

任務(wù)執(zhí)行率=分配成功的任務(wù)數(shù)量總?cè)蝿?wù)數(shù)量

2）數(shù)據(jù)冗余率

本文將數(shù)據(jù)冗余率定義為整體與有效數(shù)據(jù)所占比例的差，其中有效數(shù)據(jù)指所收集數(shù)據(jù)覆蓋的時(shí)空單元數(shù)量，因此數(shù)據(jù)冗余率的取值為［0， 1］。

數(shù)據(jù)冗余率=1－有效數(shù)據(jù)樣本收集的總數(shù)據(jù)樣本=收集的總數(shù)據(jù)樣本－有效數(shù)據(jù)樣本收集的總數(shù)據(jù)樣本

3）平均感知成本

本文將平均感知成本定義為平臺(tái)的報(bào)酬支付總和與已分配的任務(wù)數(shù)量的比值，表示平均每個(gè)任務(wù)的成本。

平均感知成本=平臺(tái)總支付/已分配任務(wù)數(shù)量

4.3實(shí)驗(yàn)結(jié)果分析

4.3.1預(yù)測(cè)方法評(píng)估

為評(píng)估本文提出的參與者軌跡序列預(yù)測(cè)方法，對(duì)本文預(yù)測(cè)方法與基于統(tǒng)計(jì)分析的預(yù)測(cè)方法［20］、基于馬爾可夫模型的方法［23］和考慮短期歷史信息的LSTM方法［25］進(jìn)行了對(duì)比實(shí)驗(yàn)。其中文獻(xiàn)［20］根據(jù)歷史軌跡記錄采用統(tǒng)計(jì)模型推導(dǎo)參與者在特定時(shí)間通過(guò)特定分區(qū)的概率，文獻(xiàn)［23］利用半馬爾可夫過(guò)程計(jì)算參與者的訪問(wèn)概率，文獻(xiàn)［25］將預(yù)測(cè)時(shí)間點(diǎn)之前的一段歷史軌跡序列作為預(yù)測(cè)模型的輸入。在實(shí)驗(yàn)中，本文將一天劃分成T=12個(gè)時(shí)段，對(duì)時(shí)段的不同劃分個(gè)數(shù)，即L=2、4、6、12分別進(jìn)行了準(zhǔn)確度分析。

圖3顯示時(shí)段劃分個(gè)數(shù)L不同取值下的預(yù)測(cè)方法準(zhǔn)確度。從圖中可以看出，本文預(yù)測(cè)方法的準(zhǔn)確度高于其他三種方法?？梢钥闯鲴R爾可夫方法和統(tǒng)計(jì)分析方法準(zhǔn)確度較低，表明LSTM神經(jīng)網(wǎng)絡(luò)自學(xué)習(xí)功能可以有效提高預(yù)測(cè)的準(zhǔn)確性?？紤]短期信息的LSTM方法準(zhǔn)確度略低于本文預(yù)測(cè)方法，其原因是本文方法考慮了參與者的長(zhǎng)期移動(dòng)軌跡的概率信息，更具有普遍性。另外，本文的預(yù)測(cè)方法在L取值為4時(shí)，準(zhǔn)確度最高，約為86.4%，隨著L的增大，四種方法的準(zhǔn)確度均在降低，其原因是L增大會(huì)使預(yù)測(cè)時(shí)間間隔變小，參與者的軌跡多變，規(guī)律不明顯，因此準(zhǔn)確性降低。

4.3.2任務(wù)分配方法評(píng)估

為說(shuō)明任務(wù)數(shù)量變化對(duì)實(shí)驗(yàn)結(jié)果的影響，本文固定參與者數(shù)量為15，參與者可參與的時(shí)空單元數(shù)量最大限制為30。首先比較了本文算法的收斂情況，然后通過(guò)改變?nèi)蝿?wù)的數(shù)量對(duì)本文算法、CAPR機(jī)制和WTPS算法進(jìn)行了在任務(wù)執(zhí)行率、數(shù)據(jù)冗余率和平均感知成本三個(gè)方面的指標(biāo)對(duì)比，并且每項(xiàng)指標(biāo)均重復(fù)進(jìn)行了10次實(shí)驗(yàn)取平均值作為實(shí)驗(yàn)結(jié)果。

表2展示了算法的迭代次數(shù)。為直觀表示本文算法的收斂性能，將本文算法與未使用算法1（種群初始化算法）初始化的算法進(jìn)行關(guān)于算法收斂時(shí)的迭代次數(shù)比較?？梢钥闯?，隨著任務(wù)數(shù)量的增加，本文算法和未初始化算法的迭代次數(shù)均在增加，未初始化算法的迭代次數(shù)大于本文算法?？梢员砻?，本文提出的算法1有利于加快任務(wù)分配求解速度。

圖4顯示任務(wù)數(shù)量變化對(duì)任務(wù)執(zhí)行率的影響?？梢钥闯?，本文算法具有更高的任務(wù)執(zhí)行率，WTPS算法效果較差。其原因是，WTPS雖然考慮按照周期分配的方式降低任務(wù)內(nèi)的數(shù)據(jù)冗余，卻忽略了任務(wù)間的時(shí)空覆蓋重疊性，在任務(wù)之間存在過(guò)多的重復(fù)分配，產(chǎn)生較高的支付成本，不利于選擇更多的參與者滿足任務(wù)最低閾值要求。隨著任務(wù)數(shù)量的增加，三種方法實(shí)現(xiàn)的任務(wù)執(zhí)行率整體趨勢(shì)均在下降。 因?yàn)閰⑴c者受到最多可參與時(shí)空單元數(shù)量的限制，隨著任務(wù)數(shù)量的增加，任務(wù)分配逐漸達(dá)到參與者的可參與時(shí)空單元數(shù)量閾值，沒(méi)有足夠的參與者進(jìn)行任務(wù)分配。其中，本文算法與CAPR機(jī)制效果差距較小，因?yàn)槿蝿?wù)內(nèi)的數(shù)據(jù)冗余對(duì)任務(wù)分配成功數(shù)量影響小于任務(wù)間的影響，CAPR即使忽略了任務(wù)內(nèi)的數(shù)據(jù)冗余，但由于其可以根據(jù)任務(wù)間的相關(guān)性節(jié)約成本，所以可以有較高的任務(wù)執(zhí)行率。另外，當(dāng)任務(wù)數(shù)量低于50時(shí)，本文算法和CAPR的任務(wù)執(zhí)行率均在0.84左右，當(dāng)任務(wù)數(shù)量高于50時(shí)，本文算法的效果優(yōu)于CAPR機(jī)制。其原因是，當(dāng)任務(wù)數(shù)量較少時(shí)，任務(wù)間的時(shí)空覆蓋重疊度較低，本文算法的最大化時(shí)空覆蓋重疊區(qū)域中參與者數(shù)據(jù)的重復(fù)利用度效果不明顯，與CAPR實(shí)現(xiàn)結(jié)果接近；而當(dāng)任務(wù)數(shù)量較多時(shí)，任務(wù)間的時(shí)空覆蓋重疊度增加，本文算法中的最大化參與者數(shù)據(jù)的重復(fù)利用度可以盡最大可能地提高時(shí)空覆蓋重疊區(qū)域內(nèi)任務(wù)分配的數(shù)量，因此任務(wù)執(zhí)行率優(yōu)于CAPR。另外，CAPR在任務(wù)開(kāi)始時(shí)間作出的預(yù)分配可能不適合后續(xù)的分配，因?yàn)楹罄m(xù)出現(xiàn)的任務(wù)負(fù)相關(guān)或者參與者不可用情況可能導(dǎo)致任務(wù)分配失敗。

圖5顯示任務(wù)數(shù)量變化對(duì)數(shù)據(jù)冗余率的影響。從圖中可以看出，本文算法實(shí)現(xiàn)的數(shù)據(jù)冗余率低于CAPR機(jī)制和WTPS算法。其原因是WTPS僅是降低任務(wù)內(nèi)的數(shù)據(jù)冗余，CAPR機(jī)制考慮任務(wù)的時(shí)空相關(guān)性，可以在一定程度上減少任務(wù)間的數(shù)據(jù)冗余，而本文算法一方面通過(guò)細(xì)粒度時(shí)隙劃分的方法減少任務(wù)內(nèi)的數(shù)據(jù)冗余問(wèn)題，另一方面使參與者在時(shí)空單元中的感知數(shù)據(jù)最大化重復(fù)利用，同時(shí)實(shí)現(xiàn)任務(wù)內(nèi)和任務(wù)間的數(shù)據(jù)冗余控制。當(dāng)任務(wù)數(shù)量增多時(shí)，本文算法和CAPR的數(shù)據(jù)冗余率緩慢增加，而WTPS數(shù)據(jù)冗余率增加較快，本文算法的數(shù)據(jù)冗余率增加至22%左右，WTPS的數(shù)據(jù)冗余率已達(dá)到30%，差距逐漸增大。其原因是，任務(wù)數(shù)量增加可能會(huì)產(chǎn)生更多具有時(shí)空覆蓋重疊的任務(wù)，WTPS忽略了任務(wù)間的時(shí)空覆蓋重疊性，進(jìn)行了過(guò)多的重復(fù)任務(wù)分配，產(chǎn)生了較多任務(wù)間的冗余數(shù)據(jù)，且隨著系統(tǒng)任務(wù)數(shù)量的增多，重復(fù)分配的任務(wù)增加。本文算法的數(shù)據(jù)冗余率緩慢增加，因?yàn)槿蝿?wù)間的時(shí)空覆蓋重疊度增加，時(shí)空覆蓋重疊區(qū)域中參與者的數(shù)據(jù)利用率增加，所以產(chǎn)生的數(shù)據(jù)冗余率變化趨勢(shì)緩慢。從圖中可以看出，相較于本文算法，CAPR的數(shù)據(jù)冗余率增加更加緩慢，其原因可能是在任務(wù)數(shù)量較少時(shí)，CAPR在任務(wù)內(nèi)部已經(jīng)產(chǎn)生較多的冗余數(shù)據(jù)；而當(dāng)任務(wù)數(shù)量增加時(shí)，由于時(shí)空覆蓋重疊的任務(wù)較多，CAPR可以在一定程度上降低任務(wù)間的數(shù)據(jù)冗余，產(chǎn)生較少的冗余數(shù)據(jù)。因此CAPR的數(shù)據(jù)冗余變化不明顯。

圖6顯示任務(wù)數(shù)量變化對(duì)平均感知成本的影響。在任務(wù)數(shù)量低于40時(shí)，三種方法的平均感知成本相近，但隨著任務(wù)數(shù)量的增加，本文算法和CAPR的感知成本逐漸降低。其原因是，隨著任務(wù)數(shù)量的增加，任務(wù)間的時(shí)空覆蓋重疊性增加，本文算法可以提高時(shí)空覆蓋重疊區(qū)域參與者數(shù)據(jù)的重復(fù)利用度，有效降低任務(wù)的報(bào)酬支付，因此隨著任務(wù)數(shù)量的增加，本文算法的平均感知成本逐漸降低。同理，CAPR為任務(wù)選擇參與者的過(guò)程中考慮任務(wù)相關(guān)性，在一定程度上可以降低感知成本，并且當(dāng)任務(wù)數(shù)量較少時(shí)，CAPR有較高的任務(wù)執(zhí)行率，因此平均感知成本相較于本文算法更低。另外可以看出，WTPS算法的平均感知成本變化比較平穩(wěn)，由于WTPS沒(méi)有考慮任務(wù)間的數(shù)據(jù)冗余，隨著任務(wù)數(shù)量增加受到預(yù)算的限制，WTPS并沒(méi)有完成更多的任務(wù)分配。

5結(jié)束語(yǔ)

移動(dòng)群智感知系統(tǒng)中多個(gè)任務(wù)之間存在時(shí)空覆蓋重疊性可能導(dǎo)致重復(fù)數(shù)據(jù)收集從而引發(fā)數(shù)據(jù)冗余問(wèn)題，本文提出了一種可降低任務(wù)內(nèi)及任務(wù)間數(shù)據(jù)冗余的任務(wù)分配方法。首先設(shè)計(jì)了參與者移動(dòng)軌跡序列的預(yù)測(cè)方法，然后在預(yù)測(cè)結(jié)果的基礎(chǔ)上考慮到任務(wù)間的時(shí)間及空間范圍的重疊性，提出了基于遺傳算法的任務(wù)分配方法。仿真結(jié)果表明，本文方法在降低任務(wù)內(nèi)及任務(wù)間的數(shù)據(jù)冗余方面有良好的效果。在未來(lái)的工作中，應(yīng)考慮更多可能會(huì)影響參與者行為的因素以及參與者自身的時(shí)間可用性等因素對(duì)任務(wù)分配的影響，并探索新的優(yōu)化方法和理論基礎(chǔ)。

參考文獻(xiàn)：

［1］Hettiachchi D， Kostakos V， Goncalves J. A survey on task assignment in crowdsourcing ［J］. ACM Computing Surveys， 2022， 55（3）： 1-35.

［2］Seid S， Zennaro M， Libse M， et al. Mobile crowd sensing based road surface monitoring using smartphone vibration sensor and LoRaWAN ［C］// Proc of the 1st Workshop on Experiences with the Design and Implementation of Frugal Smart Objects. New York： ACM Press， 2020： 36-41.

［3］Bock F， Martino S D， Origlia A. Smart parking： using a crowd of taxis to sense on-street parking space availability ［J］. IEEE Trans on Intelligent Transportation Systems， 2020， 21（2）： 496-508.

［4］方文鳳， 周朝榮， 孫三山. 移動(dòng)群智感知中任務(wù)分配的研究 ［J］. 計(jì)算機(jī)應(yīng)用研究， 2018， 35（11）： 3206-3212. （Fang Wenfeng， Zhou Zhaorong， Sun Sanshan. Research on task assignment for mobile crowd sensing ［J］. Application Research of Computers， 2018， 35（11）： 3206-3212.）

［5］Ko H， Pack S， Leung V. Coverage-guaranteed and energy-efficient participant selection strategy in mobile crowdsensing ［J］. IEEE Internet of Things Journal， 2019， 6（2）： 3202-3211.

［6］Yang Jing， Fu Lei， Yang Boran， et al. Participant service quality aware data collecting mechanism with high coverage for mobile crowdsensing ［J］. IEEE Access， 2020，8： 10628-10639.

［7］Xiao Mingjun， Gao Guoju， Wu Jie， et al. Privacy-preserving user recruitment protocol for mobile crowdsensing ［J］. IEEE/ACM Trans on Networking， 2020， 28（2）： 519-532.

［8］Hu Qin， Wang Shengling， Cheng Xiuzhen， et al. Cost-efficient mobile crowdsensing with spatial-temporal awareness ［J］. IEEE Trans on Mobile Computing， 2021， 20（3）： 928-938.

［9］Song Shiwei， Liu Zhidan， Li Zhenjiang， et al. Coverage-oriented task assignment for mobile crowdsensing ［J］. IEEE Internet of Things Journal， 2020， 7（8）： 7407-7418.

［10］Zhou Siwang， He Yan， Xiang Shuzhen， et al. Region-based compressive networked storage with lazy encodings ［J］. IEEE Trans on Parallel and Distributed Systems， 2019， 30（6）： 1390-1402.

［11］Liu Wenbin， Wang Leye， Wang En， et al. Reinforcement learning-based cell selection in sparse mobile crowdsensing ［J］. Computer Networks， 2019， 161（9）： 102-114.

［12］Liu Wenbin， Yang Yongjian， Wang En， et al. User recruitment for enhancing data inference accuracy in sparse mobile crowdsensing ［J］. IEEE Internet of Things Journal， 2020， 7（3）： 1802-1814.

［13］Liu Wenbin， Yang Yongjian， Wang En， et al. Prediction based user selection in time-sensitive mobile crowdsensing ［C］// Proc of the 14th Annual IEEE International Conference on Sensing， Communication， and Networking. Piscataway， NJ： IEEE Press， 2017： 1-9.

［14］Tao Xi， Song Wei. Location-dependent task allocation for mobile crowdsensing with clustering effect ［J］. IEEE Internet of Things Journal， 2019， 6（1）： 1029-1045.

［15］Wang Jiangtao， Wang Yasha， Zhang Daqing， et al. Fine-grained multitask allocation for participatory sensing with a shared budget ［J］. IEEE Internet of Things Journal， 2016， 3（6）： 1395-1405.

［16］Zhou Tongqing， Xiao Bin， Cai Zhiping， et al. A utility model for photo selection in mobile crowdsensing ［J］. IEEE Trans on Mobile Computing， 2021， 20（1）： 48-62.

［17］Gendy M， Al-Kabbany A， Badran E. Maximizing clearance rate of budget-constrained auctions in participatory mobile crowdsensing ［J］. IEEE Access， 2020，8： 113585-113600.

［18］Xia Xingyou， Zhou Yan， Li Jie， et al. Quality-aware sparse data collection in MEC-enhanced mobile crowdsensing systems ［J］. IEEE Trans on Computational Social Systems， 2019， 6（5）： 1051-1062.

［19］Nguyen T N， Zeadally S. Mobile crowd-sensing applications： data redundancies， challenges， and solutions ［J］. ACM Trans on Internet Technology， 2022， 22（2）： 1-15.

［20］Wang Liang， Yu Zhiwen， Zhang Daqing， et al. Heterogeneous multi-task assignment in mobile crowdsensing using spatiotemporal correlation ［J］. IEEE Trans on Mobile Computing， 2019， 18（1）： 84-97.

［21］Zhang Lichen， Ding Yu， Wang Xiaoming， et al. Conflict-aware participant recruitment for mobile crowdsensing ［J］. IEEE Trans on Computational Social Systems， 2020， 7（1）： 192-204.

［22］Yang Wenjie， Sun Guodong， Ding Xingjian， et al. Budget-feasible user recruitment in mobile crowdsensing with user mobility prediction ［C］// Proc of the 37th International Performance Computing and Communications Conference. Piscataway， NJ： IEEE Press， 2018： 1-10.

［23］Yang Yongjian， Liu Wenbin， Wang En， et al. A prediction-based user selection framework for heterogeneous mobile crowdsensing ［J］. IEEE Trans on Mobile Computing， 2019， 18（11）： 2460-2473.

［24］Wang Jiangtao， Wang Feng， Wang Yasha， et al. HyTasker： hybrid task allocation in mobile crowd sensing ［J］. IEEE Trans on Mobile Computing， 2020， 19（3）： 598-611.

［25］Zhu Xiaoyu， Luo Yueyi， Liu Anfeng， et al. A deep learning-based mobile crowdsensing scheme by predicting vehicle mobility ［J］. IEEE Trans on Intelligent Transportation Systems， 2021， 22（7）： 4648-4659.

收稿日期：2021-12-28；修回日期：2022-02-16基金項(xiàng)目：國(guó)家自然科學(xué)基金資助項(xiàng)目（61802257）

作者簡(jiǎn)介：何杏宇（1984-），女，湖南岳陽(yáng)人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)槲锫?lián)網(wǎng)、群智計(jì)算和大數(shù)據(jù)分析；趙丹（1996-），女，山東棗莊人，碩士研究生，主要研究方向?yàn)橐苿?dòng)群智感知；楊桂松（1982-），男（通信作者），河南漯河人，副教授，碩導(dǎo)，博士，主要研究方向?yàn)槲锫?lián)網(wǎng)與普適計(jì)算等（gsyang@usst.edu.cn）；金子日（2001-），男，北京人，本科生，主要研究方向?yàn)橐苿?dòng)群智感知；覃洋愷龍（2000-），男，廣西柳州人，本科生，主要研究方向?yàn)橐苿?dòng)群智感知；汪琦沛（2001-），男，四川峨眉山人，本科生，主要研究方向?yàn)橐苿?dòng)群智感知.