趙 敏

(貴州民族大學(xué)數(shù)據(jù)科學(xué)與信息工程學(xué)院，貴州 貴陽 550025)

1 引言

車載感知設(shè)備、智能手機(jī)、可穿戴設(shè)備和平板電腦等終端設(shè)備在近年來得到了普及和發(fā)展，上述智能設(shè)備中存在了大量的傳感器，具有通信、計算、存儲和感知的能力，促進(jìn)了群智感知技術(shù)的發(fā)展[1]。群智感知技術(shù)是移動感知和眾包思想結(jié)合生成的，其感知單元是用戶身上存在的移動設(shè)備，構(gòu)成移動網(wǎng)絡(luò)，通過網(wǎng)絡(luò)進(jìn)行無意識或有意識的協(xié)作，實現(xiàn)數(shù)據(jù)收集、任務(wù)分發(fā)，可以完成復(fù)雜、大規(guī)模的感知任務(wù)[2]。群智感知技術(shù)被廣泛的應(yīng)用在城市環(huán)境感知、環(huán)境檢測、公共安全和智能交通等領(lǐng)域中[3]。時間變化的同時移動節(jié)點在網(wǎng)絡(luò)中的位置也會發(fā)生變化，使節(jié)點在網(wǎng)絡(luò)中相遇的時間出現(xiàn)較大的波動，所以節(jié)點在傳輸數(shù)據(jù)的過程中所用的時間較長，提高了實現(xiàn)任務(wù)的時間成本，因此需要研究網(wǎng)絡(luò)群智感知任務(wù)的分配方法[4]。

基于混合任務(wù)網(wǎng)絡(luò)的任務(wù)分配方法考慮服務(wù)群體的協(xié)同水平和勝任度構(gòu)建群智感知任務(wù)分配模型，通過粒子群算法求解任務(wù)分配模型，引入加權(quán)TOPSIS評估方法結(jié)合網(wǎng)絡(luò)實際情況和用戶偏好得到群智感知任務(wù)的分配方案，該方法分配任務(wù)所用的時間較長，任務(wù)分配效率低[5]?；赒學(xué)習(xí)的網(wǎng)絡(luò)任務(wù)分配方法通過Q學(xué)習(xí)方法確定多目標(biāo)在網(wǎng)絡(luò)中相遇的最好時機(jī)，利用回報函數(shù)和Q學(xué)習(xí)函數(shù)得到最優(yōu)簇首在目標(biāo)并行階段中的切換方案，采用動態(tài)最小簇成員總數(shù)和信息效用函數(shù)保證網(wǎng)絡(luò)剩余能量的同時，選擇不同階段中的簇成員和最優(yōu)簇首，實現(xiàn)網(wǎng)絡(luò)任務(wù)的分配，該方法將任務(wù)分配給用戶后，只有少數(shù)的用戶能夠完成任務(wù)，存在任務(wù)完成率低的問題[6]?；陔p邊匹配的任務(wù)分配方法分析網(wǎng)絡(luò)用戶的屬性指標(biāo)信息，采用聚類方法根據(jù)用戶的相關(guān)信息對用戶做聚類處理，采用優(yōu)勢數(shù)分析和用戶偏好信息的任務(wù)評價排序方法，評價每個聚類的任務(wù)集，在雙邊匹配理論的基礎(chǔ)上實現(xiàn)用戶和任務(wù)的匹配，完成網(wǎng)絡(luò)任務(wù)的分配，該方法中的算法較為復(fù)雜，存在計算所用的時間較長、分配效率低的問題[7]。

針對當(dāng)前任務(wù)分配方法中存在的分配效率低和任務(wù)完成率低的問題，提出數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法。

2 群智感知環(huán)境和約束條件

1)群智感知環(huán)境

用戶的移動設(shè)備在群智感知環(huán)境中可以作為無線傳感器，通過設(shè)備的通信、感知、存儲和計算功能協(xié)同完成任務(wù)。群智感知技術(shù)可以以較小的代價實現(xiàn)城市Wifi描述、交通信息映射等復(fù)雜且規(guī)模較大的感知任務(wù)。一般情況下通過視頻、文本、音頻和圖像等媒介存儲群智感知的數(shù)據(jù)和任務(wù)。群智感知問題可以描述為在未知環(huán)境中請求者利用環(huán)境感知學(xué)習(xí)實現(xiàn)任務(wù)的調(diào)度。

(1)

(2)

式中，TL代表的是最晚完成時間；EPT代表的是移動用戶uj執(zhí)行任務(wù)ti需要的時間；TM代表的是理論最小完成時間，其計算公式如下

(3)

式中，CPj代表的是第j個設(shè)備在交互網(wǎng)絡(luò)中的處理能力；TAT代表的是為移動用戶uj分配任務(wù)ti所用的時間。

設(shè)Ti，j代表的是在第j個設(shè)備中運行第i個任務(wù)實際花費的時間，其計算公式如下

(4)

交互網(wǎng)絡(luò)群智感知環(huán)境中處理任務(wù)的過程主要為：通過交互網(wǎng)絡(luò)為用戶設(shè)備中傳送任務(wù)；用戶通過設(shè)備執(zhí)行任務(wù)；在利用交互網(wǎng)絡(luò)將任務(wù)處理結(jié)果傳送到設(shè)備中。

2)約束條件

在分配任務(wù)時，所用的時間越少方法的性能越好，分配任務(wù)過程中消耗的能量也是需要任務(wù)分配方法考慮的因素[8]。

設(shè)E代表的是分配任務(wù)消耗的能量，其計算公式如下

(5)

式中，TMEM(ti，uj)代表的是在用戶uj的內(nèi)核中運行任務(wù)ti消耗的最大能量。

如果在交互網(wǎng)絡(luò)群智感知環(huán)境中將任務(wù)分配給其他用戶時，則從移動設(shè)備中接收任務(wù)和將任務(wù)發(fā)送給移動用戶是任務(wù)在設(shè)備中的主要能量消耗，其中接收任務(wù)消耗的能量較小，所以用戶采用移動終端執(zhí)行任務(wù)消耗的能量可以只考慮發(fā)送任務(wù)消耗的能量。

任務(wù)請求者通過交互網(wǎng)絡(luò)將任務(wù)傳送給用戶，設(shè)Trans(ti)代表的是傳送任務(wù)所用的時間，其計算公式如下

Trans(ti)=WS(ti)/B

(6)

式中，WS(ti)代表的是任務(wù)ti中存在的工作量；B代表的是任務(wù)傳輸帶寬。

用戶會考慮本身在網(wǎng)絡(luò)中空閑的資源總數(shù)對接收到的任務(wù)進(jìn)行處理，接收到任務(wù)后用戶判斷自身資源是否能夠處理任務(wù)，設(shè)EPT(ti，uj)代表的是處理任務(wù)花費的時間，其計算公式如下

EPT(ti，uj)=WS(ti)/[Trans(ti)·CPj]

(7)

利用交互網(wǎng)絡(luò)將任務(wù)處理結(jié)果傳送給請求者。

為用戶分配任務(wù)是任務(wù)分配方法的最終目標(biāo)，在滿足分配約束的條件下，盡可能的縮短分配任務(wù)所用的時間[9]。任務(wù)分配時間主要包括任務(wù)傳輸時間和任務(wù)處理時間。

在滿足服務(wù)約束和資源約束的基礎(chǔ)上，最小化用戶處理任務(wù)需要的時間

(8)

3 群智感知任務(wù)分配方法

數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法通過信譽(yù)模型實現(xiàn)群智感知任務(wù)的分配，首先在交互網(wǎng)絡(luò)中為不同的用戶設(shè)置對應(yīng)的信譽(yù)值，用戶在交互網(wǎng)絡(luò)中競爭感知任務(wù)時，交互網(wǎng)絡(luò)優(yōu)先將任務(wù)分配給信譽(yù)值高的用戶，采用因子對用戶處理任務(wù)的代價花費進(jìn)行調(diào)節(jié)，在數(shù)據(jù)驅(qū)動下實現(xiàn)交互網(wǎng)絡(luò)中群智感知任務(wù)的分配，具體步驟如下：

1)當(dāng)交互網(wǎng)絡(luò)群智感知環(huán)境中存在需要處理的任務(wù)時，對任務(wù)集T進(jìn)行劃分，得到多個子任務(wù)k?{1，2，…，K}。設(shè)U代表的是用戶集，存在于任務(wù)發(fā)布區(qū)域中，劃分任務(wù)集，得到Ui，其中i?{1，2，…，N}。

為用戶i在交互網(wǎng)絡(luò)群智感知環(huán)境中設(shè)置閾值Thresi，交互網(wǎng)絡(luò)群智感知環(huán)境中的其他用戶不知道該閾值，設(shè)Qi代表的是信譽(yù)值，由用戶單個閾值和全部用戶閾值得到，其計算公式如下

(9)

設(shè)uk=f(ξ，ξk)代表的是不同子任務(wù)對應(yīng)的效用值，其計算公式如下

(10)

式中，ξk代表的是第k個子任務(wù)在交互網(wǎng)絡(luò)中的大?。沪未淼氖撬腥蝿?wù)在交互網(wǎng)絡(luò)中的大小。

2)交互網(wǎng)絡(luò)會選用信譽(yù)值大的用戶處理子任務(wù)，參與在群智感知環(huán)境中處理任務(wù)的過程，用戶在交互網(wǎng)絡(luò)中處理任務(wù)k時，會生成花費代價。設(shè)ci=f(ξk，uk，Qi)代表的是子任務(wù)在交互網(wǎng)絡(luò)中對應(yīng)的代價函數(shù)，用戶信譽(yù)值和子任務(wù)的大小都會影響用戶的代價，用戶代價分別與信譽(yù)值和子任務(wù)大小成反比和正比，其計算公式如下

(11)

式中，因子α和因子β符合下式：

α+β=10

(12)

3)為了促進(jìn)用戶在交互網(wǎng)絡(luò)群智感知環(huán)境中處理任務(wù)，不同的子任務(wù)在交互網(wǎng)絡(luò)中都對應(yīng)著相應(yīng)的報酬。設(shè)Pk=f(uk，N(t)，B(t))代表的是報酬函數(shù)，其中，N(t)代表的是用戶在時間t時在交互網(wǎng)絡(luò)中參與任務(wù)處理的比例；B(t)代表的是在時間t時交互網(wǎng)絡(luò)中剩余的預(yù)算，其計算公式如下

(13)

式中，c代表的是常數(shù)。在上述方式中，初始段中交互網(wǎng)絡(luò)提供的報酬較高，用來激勵用戶參與處理群智感知任務(wù)。用戶參與交互網(wǎng)絡(luò)中群智感知任務(wù)處理的比例逐漸升高，最后趨近于穩(wěn)定，交互網(wǎng)絡(luò)提供的報酬最終也會在某個值附近保持平穩(wěn)[10]。

4)用戶根據(jù)交互網(wǎng)絡(luò)處理任務(wù)k需要支付的報酬P(guān)k以及處理任務(wù)k付出的代價ci，決定是否接受交互網(wǎng)絡(luò)中的群智感知任務(wù)，通過函數(shù)Ji=f(ci，Pk，Thresi)表示上述結(jié)果，函數(shù)的表達(dá)式如下

(14)

對比用戶閾值Thresi和交互網(wǎng)絡(luò)處理任務(wù)付出的代價ci與處理任務(wù)k需要支付的報酬P(guān)k比例的大小，如果用戶閾值小于比例，用戶接受交互網(wǎng)絡(luò)中存在的群智感知任務(wù)；如果用戶閾值小于比例，用戶不接受交互網(wǎng)絡(luò)中存在的群智感知任務(wù)。

5)采用用戶處理交互網(wǎng)絡(luò)中群智感知任務(wù)對應(yīng)的效用值對用戶信譽(yù)值進(jìn)行更行，利用更新后的信譽(yù)值進(jìn)行交互網(wǎng)絡(luò)中下一個群智感知任務(wù)的處理，直到將交互網(wǎng)絡(luò)中存在的任務(wù)全部分配完為止，結(jié)束。

4 實驗結(jié)果與分析

為了驗證數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法的整體有效性，需要進(jìn)行測試，在本次測試過程中用到的數(shù)據(jù)來源為Andrews_sassy數(shù)據(jù)集和St Andrews大學(xué)，本次測試的平臺為Visual C++開發(fā)的TTE平臺。分別采用數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法、基于混合任務(wù)網(wǎng)絡(luò)的任務(wù)分配方法和基于Q學(xué)習(xí)的網(wǎng)絡(luò)任務(wù)分配方法進(jìn)行測試，對比三種不同方法分配任務(wù)花費的時間，測試結(jié)果如圖1所示。

圖1 三種不同方法的任務(wù)分配時間

分析圖1(a)可知，采用數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法分配任務(wù)時，花費的分配時間均在3s以內(nèi)；分析圖1(b)可知，采用基于混合任務(wù)網(wǎng)絡(luò)的任務(wù)分配方法分配網(wǎng)絡(luò)任務(wù)時，在第6次迭代中花費的分配時間高達(dá)13s，其余迭代中花費的分配時間均高于11s；分析圖1(c)可知，采用基于Q學(xué)習(xí)的網(wǎng)絡(luò)任務(wù)分配方法分配群智感知任務(wù)時，花費的時間均在7s以上，最高為10s。對比三種不同方法的測試結(jié)果可知，數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法分配任務(wù)花費的時間均少于基于混合任務(wù)網(wǎng)絡(luò)的任務(wù)分配方法和基于Q學(xué)習(xí)的網(wǎng)絡(luò)任務(wù)分配方法分配任務(wù)花費的時間，因為所提方法在分配任務(wù)之前，基于服務(wù)約束和資源約束，在群智感知環(huán)境中最小化用戶處理任務(wù)需要的時間，縮短了分配任務(wù)花費的時間，提高了數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法的分配效率。

將任務(wù)完成率作為衡量指標(biāo)進(jìn)一步測試數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法、基于混合任務(wù)網(wǎng)絡(luò)的任務(wù)分配方法和基于Q學(xué)習(xí)的網(wǎng)絡(luò)任務(wù)分配方法的有效性，測試結(jié)果如圖2所示。

圖2 三種不同方法的任務(wù)完成率

分析圖2可知，數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法的任務(wù)完成率在多次迭代中均在80%以上，基于混合任務(wù)網(wǎng)絡(luò)的任務(wù)分配方法和基于Q學(xué)習(xí)的網(wǎng)絡(luò)任務(wù)分配方法的任務(wù)完成率均在50%和20%附近波動。對比三種不同方法的任務(wù)完成率可知，數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法的任務(wù)完成率最高，因為該方法利用信譽(yù)模型分配群智感知任務(wù)，優(yōu)先將任務(wù)分配給信譽(yù)值高的用戶，提高了群智感知任務(wù)的完成率，驗證數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法的任務(wù)完成率高。

5 結(jié)束語

移動智能終端具有高性能的內(nèi)置，被廣泛的應(yīng)用到各個領(lǐng)域中，目前獲取環(huán)境信息、感知數(shù)據(jù)的主要方法是群智感知技術(shù)，為激勵并協(xié)調(diào)用戶參與交互網(wǎng)絡(luò)中任務(wù)的處理，保證數(shù)據(jù)在網(wǎng)絡(luò)中的可靠性和有效性，需要研究群智感知任務(wù)分配方法，當(dāng)前群智感知任務(wù)分配方法存在分配效率低和任務(wù)完成率低的問題，提出數(shù)據(jù)驅(qū)動下交互網(wǎng)絡(luò)群智感知任務(wù)分配方法，可在短時間內(nèi)完成群智感知任務(wù)的分配，并且用戶完成任務(wù)的概率較高，解決了當(dāng)前任務(wù)分配方法中存在的問題，為群智感知技術(shù)的發(fā)展奠定了基礎(chǔ)。