基于群智感知計算的多終端引擎任務(wù)分配仿真

康晶晶，王 龍，魏麗娟

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

1 引言

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

(4)

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

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

(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)

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

(13)

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

(14)

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

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

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

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

S={s1，s2，…，sn}

(15)

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

X=[x1，x2，…xn]T

(16)

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

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

(17)

(18)

(19)

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

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

(20)

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

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

(21)

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

(22)

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

Y=Φ*α

(23)

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

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

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

(24)

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

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

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

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

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

A={aij}

(25)

其中

(26)

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

圖1 分配矩陣示意圖

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

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

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

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

(27)

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

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

(28)

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

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

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

5 仿真研究

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

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

圖2 能耗性能對比

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

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

圖3 任務(wù)分配時間對比

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

6 結(jié)論

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