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

康晶晶，王 龍，魏麗娟

(山西農業大學信息學院，山西 晉中 030800)

1 引言

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

新興的群智感知技術逐步變成實時感知及采集周邊環境數據的有效方法，與傳統方法不同，群智感知技術把用戶隨身佩戴的移動終端當作基礎感知單元[2]，使用終端的感知、計算、儲存和通信功能，及時得到需要的數據，并利用無線網絡進行協作收發，完成感知任務的分發和收集，同時實現低成本的大范圍、復雜化數據的感知任務[3]。

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

2 多終端引擎任務分配模型

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

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

首先要根據歷史信息預判未來不同類別任務的個數轉換狀態，同時利用預判結果構建整數線性規劃模型了解預判窗口中能否完成多類別任務的合理分配。

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

(1)

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

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

(2)

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

(3)

(4)

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

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

(5)

(6)

在灰色預測模型中，假設模型的輸入信息序列為：

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)

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

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

(11)

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

(12)

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

(13)

獲得任務量預測結果后，通過研究預測結果與實際值的相對偏差，對模型精度進行深入分析，相對偏差表達式為

(14)

3 群智感知計算系統分析

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

針對區域覆蓋感知任務而言，考慮傳感器覆蓋范圍與使用者對感知區域覆蓋準確度要求，設定一個不變的面積作為基礎感知單元，對基礎感知單元內信息的一次有效收集與傳輸當作對此區域的一次感知操作[8]。這里對感知節點軌跡長度及任務數量都采用基礎感知單元數量進行表達。

把全局任務收集區域分割成n個基礎感知單元，將全部基礎感知單元集合描述成

S={s1，s2，…，sn}

(15)

全部基礎收集單元感知數據是

X=[x1，x2，…xn]T

(16)

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

關于整體感知節點L*，節點pl的軌跡定義為

(17)

(18)

(19)

按照壓縮感知原則，構建一個壓縮感知任務模型，模型中的先驗稀疏感知信息為

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

(20)

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

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

(21)

XC可利用Ψ進行稀疏表達，且Ψ是一個n×n矩陣

(22)

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

Y=Φ*α

(23)

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

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

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

(24)

式中，L表示參與感知任務的感知節點集合，nl、ml依次為節點Pl的感知任務數量及檢測值數量，λ用來調節感知節點內部成本及不同類別感知任務成本間的比率。

通過構建群智感知計算系統，可以判斷終端是否存在任務超載現象，增強多終端引擎任務的分配效率。

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

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

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

A={aij}

(25)

其中

(26)

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

圖1 分配矩陣示意圖

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

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

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

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

(27)

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

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

(28)

式中，fi表示第i個個體的適應度。

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

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

5 仿真研究

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

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

圖2 能耗性能對比

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

為進一步研究不同方法的任務分配耗時，獲得結果如圖3所示。

圖3 任務分配時間對比

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

6 結論

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