康晶晶，王 龍，魏麗娟

(山西農(nóng)業(yè)大學(xué)信息學(xué)院，山西 晉中 030800)

1 引言

多終端引擎作為完成移動(dòng)互聯(lián)網(wǎng)終端用戶數(shù)據(jù)融合的框架和個(gè)性化平臺(tái)，從感知到服務(wù)，可以在挖掘大數(shù)據(jù)中的社會(huì)性網(wǎng)絡(luò)，為第三方構(gòu)建動(dòng)態(tài)的終端服務(wù)組，按照用戶歷史數(shù)據(jù)和動(dòng)態(tài)環(huán)境采取個(gè)性化推薦[1]?？梢詫⒍嘟K端引擎當(dāng)作平臺(tái)，容納不同種類的服務(wù)，并將其使用在智慧生活、移動(dòng)社交等領(lǐng)域。例如把多終端和廣場電子屏幕做信息互通，完成智能廣告的搭建。

新興的群智感知技術(shù)逐步變成實(shí)時(shí)感知及采集周邊環(huán)境數(shù)據(jù)的有效方法，與傳統(tǒng)方法不同，群智感知技術(shù)把用戶隨身佩戴的移動(dòng)終端當(dāng)作基礎(chǔ)感知單元[2]，使用終端的感知、計(jì)算、儲(chǔ)存和通信功能，及時(shí)得到需要的數(shù)據(jù)，并利用無線網(wǎng)絡(luò)進(jìn)行協(xié)作收發(fā)，完成感知任務(wù)的分發(fā)和收集，同時(shí)實(shí)現(xiàn)低成本的大范圍、復(fù)雜化數(shù)據(jù)的感知任務(wù)[3]。

由此，本文提出一種基于群智感知計(jì)算的多終端引擎任務(wù)分配方法。按照歷史信息預(yù)判未來不同類別任務(wù)的數(shù)量轉(zhuǎn)換情況，并使用預(yù)判結(jié)果建立整數(shù)線性規(guī)劃模型，采用累減算法還原相對(duì)變量的原始序列預(yù)測值，通過相對(duì)偏差衡量模型結(jié)果準(zhǔn)確度；利用云端平臺(tái)和參與結(jié)點(diǎn)建立群智感知計(jì)算系統(tǒng)，根據(jù)壓縮感知準(zhǔn)則設(shè)計(jì)壓縮感知任務(wù)模型，提高多終端引擎任務(wù)分配效率；采用基于遺傳算法的多終端引擎任務(wù)分配方法，通過二維分配矩陣獲取遺傳代碼，讓個(gè)體完成交叉操作，引入自學(xué)習(xí)流程計(jì)算新生成個(gè)體的適應(yīng)函數(shù)值，實(shí)現(xiàn)多終端引擎任務(wù)的合理分配。與傳統(tǒng)方法相比，本文方法實(shí)用性高，可適用于多種復(fù)雜環(huán)境下的任務(wù)分配運(yùn)作，為用戶提供精準(zhǔn)有效的個(gè)性化推薦服務(wù)。

2 多終端引擎任務(wù)分配模型

多終端引擎是終端管理系統(tǒng)的重要部件，而多終端引擎的主要工作就是利用其內(nèi)部任務(wù)管理器，對(duì)系統(tǒng)任務(wù)進(jìn)行分配。多終端引擎任務(wù)分配模型的建立不但能夠預(yù)測引擎任務(wù)數(shù)量，還能在確保流程順利運(yùn)轉(zhuǎn)的情況下提高任務(wù)處理正確率[4]。

如果任務(wù)請(qǐng)求總數(shù)是N，變遷節(jié)點(diǎn)T具備有關(guān)權(quán)限的任務(wù)處理模塊集合是P，各個(gè)模塊處理多種類別任務(wù)所耗費(fèi)的時(shí)間也不相同，任務(wù)類別集合為W。為了讓模型更加直觀，對(duì)其進(jìn)行適當(dāng)簡化，若不同類別產(chǎn)生任務(wù)的時(shí)間為隨機(jī)的，按照任務(wù)處理的歷史信息，可得到模塊pi處理wj類任務(wù)的時(shí)間均值ti，j。

首先要根據(jù)歷史信息預(yù)判未來不同類別任務(wù)的個(gè)數(shù)轉(zhuǎn)換狀態(tài)，同時(shí)利用預(yù)判結(jié)果構(gòu)建整數(shù)線性規(guī)劃模型了解預(yù)判窗口中能否完成多類別任務(wù)的合理分配。

設(shè)定第wj類任務(wù)在第q天的個(gè)數(shù)是hi，q，則第q天需要處理的整體任務(wù)數(shù)量為

(1)

式中，i=1，2，…，k，q是不小于1的整數(shù)。

按照歷史信息能夠推導(dǎo)出第i類任務(wù)中各個(gè)任務(wù)的處理時(shí)間均值ti，j，則結(jié)束未來第k天的任務(wù)總耗時(shí)為

(2)

任務(wù)管理器在分配第k天任務(wù)的過程中，不但要保障不同模塊的任務(wù)負(fù)載均衡，還要確保模塊可以有足夠時(shí)間處理各個(gè)類別的任務(wù)[5]。將此約束條件作為前提，從而實(shí)現(xiàn)全局時(shí)間最短目標(biāo)。將di，j當(dāng)作模塊pi所分配的任務(wù)類別wj的個(gè)數(shù)，O為模塊每天的工作時(shí)長，將構(gòu)建的整數(shù)線性規(guī)劃模型表示成

(3)

(4)

如果可以對(duì)式(3)進(jìn)行求解，那么就會(huì)獲得各個(gè)模塊需要處理的類別任務(wù)個(gè)數(shù)，反之證明β值設(shè)定較小或任務(wù)總數(shù)超出模塊的最高負(fù)載性能。當(dāng)β=1時(shí)，式(3)依舊無解，這時(shí)就要增強(qiáng)模塊個(gè)數(shù)。繼而提升引擎的任務(wù)吞吐量。

為了實(shí)現(xiàn)多終端引擎的低成本目標(biāo)，需要在確保完成所有任務(wù)的基礎(chǔ)上，降低模塊的運(yùn)用數(shù)量[6]，因此可將式(3)與式(4)轉(zhuǎn)換成下面兩個(gè)解析式

(5)

(6)

在灰色預(yù)測模型中，假設(shè)模型的輸入信息序列為：

X0=(X0(1)，X0(2)，…，X0(n))

(7)

則一次疊加生成與依次平均值生成分別描述為

X1=(X1(1)，X1(2)，…，X1(n))

(8)

Z1=(Z1(1)，Z1(2)，…，Z1(n))

(9)

其中

(10)

由此可以把任務(wù)數(shù)量預(yù)測模型記作式(11)，a、b是模型的參變量。

X0(k)+a×Z1(k)=b

(11)

將式(9)的方程解定義為

(12)

然后利用累減方法還原相對(duì)變量的初始序列預(yù)測數(shù)值

(13)

獲得任務(wù)量預(yù)測結(jié)果后，通過研究預(yù)測結(jié)果與實(shí)際值的相對(duì)偏差，對(duì)模型精度進(jìn)行深入分析，相對(duì)偏差表達(dá)式為

(14)

3 群智感知計(jì)算系統(tǒng)分析

群智感知計(jì)算系統(tǒng)由兩部分構(gòu)成：云端平臺(tái)和參與結(jié)點(diǎn)。任意參與結(jié)點(diǎn)都是具備智能終端的自然人。平臺(tái)具有很多不同的感知任務(wù)，各個(gè)感知任務(wù)主要是持續(xù)不間斷地采集一種特殊的感知數(shù)據(jù)，如交通狀態(tài)、空氣質(zhì)量及噪聲水準(zhǔn)等[7]。參與結(jié)點(diǎn)會(huì)周期性地采集相對(duì)的感知數(shù)據(jù)并輸送至平臺(tái)，平臺(tái)負(fù)責(zé)整理感知數(shù)據(jù)，同時(shí)交付給需要感知的機(jī)構(gòu)。

針對(duì)區(qū)域覆蓋感知任務(wù)而言，考慮傳感器覆蓋范圍與使用者對(duì)感知區(qū)域覆蓋準(zhǔn)確度要求，設(shè)定一個(gè)不變的面積作為基礎(chǔ)感知單元，對(duì)基礎(chǔ)感知單元內(nèi)信息的一次有效收集與傳輸當(dāng)作對(duì)此區(qū)域的一次感知操作[8]。這里對(duì)感知節(jié)點(diǎn)軌跡長度及任務(wù)數(shù)量都采用基礎(chǔ)感知單元數(shù)量進(jìn)行表達(dá)。

把全局任務(wù)收集區(qū)域分割成n個(gè)基礎(chǔ)感知單元，將全部基礎(chǔ)感知單元集合描述成

S={s1，s2，…，sn}

(15)

全部基礎(chǔ)收集單元感知數(shù)據(jù)是

X=[x1，x2，…xn]T

(16)

式中，sj是第j個(gè)基礎(chǔ)感知單元，xj是第j個(gè)基礎(chǔ)感知單元的感知信息。

關(guān)于整體感知節(jié)點(diǎn)L*，節(jié)點(diǎn)pl的軌跡定義為

(17)

(18)

(19)

按照壓縮感知原則，構(gòu)建一個(gè)壓縮感知任務(wù)模型，模型中的先驗(yàn)稀疏感知信息為

XC=[x1，x2，…，xn]T

(20)

具備特定的過完備稀疏字典

Ψ=[Ψ1，Ψ2，…，Ψn]

(21)

XC可利用Ψ進(jìn)行稀疏表達(dá)，且Ψ是一個(gè)n×n矩陣

(22)

式中，α是XC在基于Ψ的對(duì)照稀疏系數(shù)矢量，并保證k稀疏，也就是α內(nèi)僅有k個(gè)大于0的值。將一維稀疏列矢量α采取降維

Y=Φ*α

(23)

其中，Φ*是m×n的降維矩陣，Y是m維度的檢測值列矢量，且k

針對(duì)參與感知任務(wù)的節(jié)點(diǎn)增設(shè)固定成本，全局任務(wù)成本會(huì)受到感知節(jié)點(diǎn)個(gè)數(shù)影響，參與感知的節(jié)點(diǎn)數(shù)量越少，全局成本越少[9]。感知節(jié)點(diǎn)參與一個(gè)基礎(chǔ)感知單元任務(wù)會(huì)生成附加成本，也就是感知節(jié)點(diǎn)成本會(huì)伴隨任務(wù)數(shù)量的增長而變多，同時(shí)系統(tǒng)還要兼顧感知節(jié)點(diǎn)內(nèi)部成本。將系統(tǒng)中的感知成本劃分為檢測成本、運(yùn)算儲(chǔ)存成本及上傳成本，則感知任務(wù)的總成本是

E=λ(Ccnl+Ctml+Csmlnl)+I0L

(24)

式中，L表示參與感知任務(wù)的感知節(jié)點(diǎn)集合，nl、ml依次為節(jié)點(diǎn)Pl的感知任務(wù)數(shù)量及檢測值數(shù)量，λ用來調(diào)節(jié)感知節(jié)點(diǎn)內(nèi)部成本及不同類別感知任務(wù)成本間的比率。

通過構(gòu)建群智感知計(jì)算系統(tǒng)，可以判斷終端是否存在任務(wù)超載現(xiàn)象，增強(qiáng)多終端引擎任務(wù)的分配效率。

4 基于遺傳算法的多終端引擎任務(wù)分配

設(shè)計(jì)一種基于遺傳算法的多終端引擎任務(wù)分配方法，可以有效提高多終端處理復(fù)雜問題性能，保證引擎任務(wù)的均衡分配，以下為方法的詳細(xì)過程。

遺傳算法是一種模擬生命進(jìn)化機(jī)制的搜索優(yōu)化方法，任務(wù)分配問題的終極解為某個(gè)分配方案，可以將其用分配矩陣進(jìn)行描述[10]。針對(duì)單流狀態(tài)，分配矩陣是二維矩陣

A={aij}

(25)

其中

(26)

值得注意的是，不是全部二值二維矩陣都是可用的，分配矩陣應(yīng)該符合以下收斂條件：必須維持任務(wù)之間的先后次序，也就是1的排列呈現(xiàn)右下方向階梯；一個(gè)任務(wù)只可以分配給1個(gè)PE，也就是矩陣中每列僅有1個(gè)1。通過分析可知，最佳引擎任務(wù)分配方法都是首先將第一個(gè)任務(wù)分配至第一個(gè)處理器。具體如圖1所示。

圖1 分配矩陣示意圖

考慮矩陣內(nèi)1的階梯狀態(tài)分布，可以探尋一種合理的遺傳代碼。從圖1可知，一個(gè)合適的分配方式應(yīng)該對(duì)照一個(gè)階梯，所以可以將階梯當(dāng)作初始問題解。因?yàn)樵撾A梯具有單調(diào)向下及向右特征，假設(shè)有n列分配矩陣，那么一個(gè)階梯就是n-1步的兩個(gè)隨機(jī)游走。把兩個(gè)隨機(jī)游走編碼成n-1位的二進(jìn)制代碼為遺傳代碼，該代碼向右移動(dòng)是1，向下移動(dòng)是0，此方法簡便可靠，能夠很好地呈現(xiàn)待求解問題。

在真實(shí)場景中，PE數(shù)量通常不大于任務(wù)數(shù)量，所以階梯向右下方游走是有限制的，游走數(shù)值要小于PE數(shù)量，在染色體中就表示0個(gè)數(shù)目要小于PE個(gè)數(shù)[11]，將該約束點(diǎn)當(dāng)作擇取染色體的收斂條件，可以降低擇取時(shí)間。

若系統(tǒng)中包含的處理流水線有L級(jí)，各個(gè)級(jí)的PE是相同的，流內(nèi)擁有M個(gè)單獨(dú)任務(wù)。使用隨機(jī)游走可以獲得遺傳原始種群，原始種群的個(gè)體值是一個(gè)關(guān)鍵參變量，個(gè)體數(shù)量越多，算法尋找到最優(yōu)解的概率就越高，將其引入本文方法中就表示集合越大，原始種群個(gè)體數(shù)量越大，否則較小。

因此，可將流在每級(jí)流水內(nèi)處理的最長時(shí)段描述為

(27)

所以，對(duì)任務(wù)合理分配就是探尋解aij，讓P為最小值，并把P的倒數(shù)當(dāng)作適應(yīng)函數(shù)，如果任意個(gè)體通過適應(yīng)函數(shù)推算獲得的適應(yīng)值較大，則此個(gè)體就是一個(gè)較優(yōu)解。

可以參與遺傳過程的個(gè)體，其父代的適應(yīng)度也相對(duì)較高，本文使用輪盤賭式正比挑選方法權(quán)衡適應(yīng)度。首先算出目前種群全部個(gè)體適應(yīng)度總和sumfit，產(chǎn)生一個(gè)取值范圍在0至sumfit之間的勻稱分布的偽隨機(jī)數(shù)r，則應(yīng)該符合的條件為

(28)

式中，fi表示第i個(gè)個(gè)體的適應(yīng)度。

將被挑選的兩個(gè)個(gè)體采取交叉操作，過程為：首先生成一個(gè)任意數(shù)，明確交叉點(diǎn)處在個(gè)體的第幾位基因上，其次實(shí)現(xiàn)部分基因轉(zhuǎn)換。交叉可以使用單點(diǎn)交叉、多點(diǎn)交叉、勻稱交叉等。單點(diǎn)交叉方法計(jì)算簡單，但收斂速率較慢。通常按照個(gè)體內(nèi)部染色體長度進(jìn)行方式擇取，染色體長使用多點(diǎn)交叉，反之使用單點(diǎn)交叉。

為了讓所提方法快讀獲取最優(yōu)解，實(shí)現(xiàn)多終端引擎任務(wù)的均衡分配，需要改進(jìn)遺傳算法的收斂性[12]。在采取變異操作的過程中，增添個(gè)體尋優(yōu)的自學(xué)習(xí)流程。即在某個(gè)基因產(chǎn)生變異后，算出新生成個(gè)體的適應(yīng)函數(shù)值。若個(gè)體適應(yīng)度較大，證明此種分配方法的最長任務(wù)處理時(shí)間較短，保留該方法，反之維持初始解不變。

5 仿真研究

為了評(píng)估方法的可靠性，將本文方法與傳統(tǒng)離散布谷鳥搜索算法進(jìn)行仿真對(duì)比，實(shí)驗(yàn)平臺(tái)為Matlab仿真軟件。

為了進(jìn)一步驗(yàn)證本文方法的性能，采用文獻(xiàn)[5]方法、文獻(xiàn)[6]方法以及本文方法對(duì)能耗性能進(jìn)行檢測，實(shí)驗(yàn)結(jié)果如圖2所示。

圖2 能耗性能對(duì)比

分析圖2可知，當(dāng)任務(wù)數(shù)量為100個(gè)時(shí)，文獻(xiàn)[5]方法任務(wù)分配耗能為81 J，文獻(xiàn)[6]方法任務(wù)分配耗能為79 J，本文方法任務(wù)分配耗能為僅為21 J。當(dāng)任務(wù)數(shù)量為1000個(gè)時(shí)，文獻(xiàn)[5]方法任務(wù)分配耗能為168 J，文獻(xiàn)[6]方法任務(wù)分配耗能為132 J，本文方法任務(wù)分配耗能為僅為42 J。本文方法分配任務(wù)耗能一直較低，這是因?yàn)樵谌蝿?wù)數(shù)增加時(shí)，本文利用遺傳算法對(duì)局部進(jìn)行優(yōu)化，保證了方法的實(shí)用性。

為進(jìn)一步研究不同方法的任務(wù)分配耗時(shí)，獲得結(jié)果如圖3所示。

圖3 任務(wù)分配時(shí)間對(duì)比

根據(jù)圖3可知，當(dāng)任務(wù)數(shù)量為100個(gè)時(shí)，文獻(xiàn)[5]方法任務(wù)分配時(shí)間為30s，文獻(xiàn)[6]方法任務(wù)分配時(shí)間為28s，本文方法任務(wù)分配時(shí)間僅為5s。當(dāng)任務(wù)數(shù)量為500個(gè)時(shí)，文獻(xiàn)[5]方法任務(wù)分配時(shí)間為48s，文獻(xiàn)[6]方法任務(wù)分配時(shí)間為52s，本文方法任務(wù)分配時(shí)間僅為8s。本文方法任務(wù)分配用時(shí)較少，且伴隨任務(wù)數(shù)量的增加，總體消耗時(shí)間基本處于固定值，證明所提方法的穩(wěn)定性好，且分配效率極高。而其它兩種傳統(tǒng)方法隨著任務(wù)數(shù)量增多，傳統(tǒng)算法整體性能有所下滑，關(guān)鍵在于沒有考慮到感知區(qū)域覆蓋準(zhǔn)確度，繼而降低了算法的運(yùn)行效率。

6 結(jié)論

為了增強(qiáng)多終端引擎獲取用戶感知數(shù)據(jù)能力，保證用戶個(gè)性化推薦的精準(zhǔn)性，提出一種基于群智感知計(jì)算的多終端引擎任務(wù)分配方法。通過建立多終端引擎任務(wù)分配模型，提升任務(wù)分配正確率，并設(shè)計(jì)群智感知計(jì)算系統(tǒng)，完善任務(wù)分配效率；運(yùn)用基于遺傳算法的多終端引擎任務(wù)分配方法，完成任務(wù)均衡分配目標(biāo)。