面向電能質量數據采集的蟻群優化算法?

王嘉怡 房 俊 高 鵬

（1.北方工業大學大規模流數據集成與分析技術北京市重點實驗室 北京 100144）（2.北方工業大學數據工程研究院 北京 100144）

1 引言

電網電能質量的優劣是電網正常運行的重要標志。電能質量數據涉及的指標數據種類多，且采集這些指標數據頻率不一［1］；現有電能質量數據采集系統以省作為單位進行數據收集，但各省數據互相隔絕，造成“信息孤島”，使得數據不能得到很好的利用。為了能更好地評估電能質量問題，增強用電效率，改善電能質量，進一步匯集各省電能質量數據很有必要。

在電網環境里，采集的各種歷史電能質量指標數據以數據包的形式存儲、發送，然而由于各指標數據采集頻率的差異，所以在一段時間內，省網成批采集到數據量不等的數據包。在面臨多批次任務時，大量數據發送到服務器時，可能會造成處理延遲，單點故障等等。如果對其進行合理的調度，既可以縮短任務整體處理的時間，也能減輕服務器處理負擔。

電能數據的調度問題與TSP問題類似，批量任務在服務器集群中的調度可以理解為在集群中找到適合各任務的最好服務節點，達到處理時間最優的效果。該問題屬于NP問題，作為一種啟發式算法，貪心算法容易陷入局部最優解，整體性能無法保障；而蟻群算法在解決該類組合優化問題中取得較好的效果。蟻群算法是根據螞蟻覓食路徑的行為，總結歸納的一種最優路徑搜索算法，在解決任務調度的問題中取得了較好的結果。本文對電網數據的任務調度問題進行建模，在蟻群算法的基礎上進行改進，得到最優的任務-服務器的映射關系，以求改善任務時間，并將服務器負載情況記錄在信息素中進行反饋，可以在降低任務時間的同時，達到負載均衡的效果。

2 相關工作

2.1 相關調度算法

2.1.1 輪詢調度算法

假設所有服務器的處理性能都相同，不關心每臺服務器的當前連接數和響應速度。其優點是：簡潔，無需記錄當前所有連接的狀態，屬于無狀態調度。但當請求服務間隔時間變化較大時，該調度容易導致服務器間的負載不平衡。

2.1.2 蟻群算法

蟻群算法來源于螞蟻尋找食物過程中發現路徑的行為。該方法經常被用于解決NP問題的優化求解，如旅行商問題，生產調度，路徑規劃等組合優化問題。在文獻［2］中，考慮到虛擬機處理能力和其異構性，大量任務集中分配到性能較好的同一虛擬機上執行，有可能導致任務等待時間過長，同時出現其他虛擬機資源空閑的狀態，針對該問題提出了信息素調整因子，將負載情況記錄到信息素中，在迭代過程中，提高空閑資源的分配概率，在降低任務執行時間的同時，改善負載不均的情況，合理分配資源，提高資源利用率。該算法的主要參數，對蟻群尋找最優解的影響比較大，在文獻［3］中，對蟻群算法的收斂性進行分析，可知重要參數影響收斂速度，合理設置參數取值可以有效地增強算法的全局搜索能力，提高算法收斂速度，減少算法計算時間，得到穩定全局最優解。

2.2 數據存儲

數據包中的電能質量數據的任一實例可以表示為四元組，每分鐘采集大約由2000個指標構成，單個量測大約80字節，每分鐘采集數據包約160KB。如果有1000個監測點采集分鐘數據，當天采集數量可達220GB。面對海量數據［4］，用常規存儲方式很難實現對其有效的管理。文獻［8］中提出了電能質量大數據存儲分析原型系統，是基于Hadoop和HBase的高效存儲和分析數據的云平臺。它結合監測數據特點，設計列存儲模式，將有相關性的數據集中存儲，以提高查詢效率。但該系統雖然實現了數據存儲，但易造成寫入熱點，且忽略了傳輸過程中數據的完整性和規范性，造成存儲空間的浪費和數據冗余。文獻［7］中的系統架構，在數據存儲前，加入數據預處理層和數據寫入層，結合數據多源、海量、高速的特點，對流數據進行數據預處理操作，并結合多線程技術，并行存儲數據。同時對HBase行健進行優化設計，結合hash散列方法，將數據均衡存儲到集群，既提高了存儲效率，又提高了某種特定類型數據的查詢效率。

在電能質量數據收集平臺的數據存儲系統結構的基礎上，改進任務調度方法，采用多個數據接收服務器作為任務接收服務器，提出基于蟻群算法的電能質量數據多任務調度。

3 問題描述

現有的電能質量數據采集系統的調度結構如圖1，采用多省輪詢發送數據包。其采集特點是：調度器獲取當前數據服務器上的數據包，將數據包按序依次發給指定數據接收節點。由于接收節點單一，導致入庫效率較低。

在圖1的基礎上，以電能質量數據為研究對象，設計面向電能質量數據采集的蟻群優化算法。調整調度結構如圖2，實現單省數據包動態分配到不同節點，結合多線程技術存儲數據庫。

蟻群算法的模型優化：改變信息素更新方式，添加信息素負載調整因子。為保證系統的運行效率和服務器的資源利用率最優，建立任務調度模型。

圖1 現有數據采集調度結構

圖2 基于蟻群優化算法的數據采集調度結構

定義1待處理的任務集合Task。設Task={Taski|i∈N+}表示當前有n個相互獨立的任務待接收，其中Taski表示第i個任務只在一個服務器上接收。

定義2可用的服務器集合M。設M=表示有m個可用接收服務器的集合，其中Mj表示第j個服務器。

定義3與TSP問題不同，電網調度由待處理任務和服務器兩個因素決定，因此將Task與M做笛卡爾積運算，得到調度集合K，定義K={Kij|1≤i≤m，1≤j≤n}，根據 K估算出任務的執行時間，用T表示，Tij表示Taski在Mj上的運行時間。為方便求解問題，將K任意兩列構成連通圖，如圖3所示。

圖3 連通圖

定義4對蟻群算法中的啟發函數和信息素函數進行初始化。其中εij（t）為啟發函數，定義：

τij（t）為信息素函數，定義：

該函數表示Taski分配給Mj的信息素濃度，其中Δτij代表信息素增量，初始時為0，1-ρ表示信息素濃度殘留程度。當螞蟻k完成一次遍歷后，對本次遍歷選擇節點進行局部信息素更新時的增量：

對全局信息素更新時選取最優路徑解更新增量：

式中C，C'為常量。Tij表示Taski在Mj的完成時間；T'

ij表示本次最優分配中Taski在Mj的完成時間。

螞蟻k從當前節點i訪問下一相鄰節點j的概率為

其中α，β反映螞蟻在任務調度中路徑上的殘留信息素和啟發式信息對任務調度的影響。

定義5添加信息素負載調整因子，記錄每臺服務器的當前接收任務的時間t，t=1-調整后式（2）中變為

tj表示在Mj上的運行時間，tavg表示所有服務器的平均運行時間，tsum表示所有服務器運行的總時間；當分配給服務器的任務變多，tj變大，此時t變小；當下次任務分配時，該服務器的信息素降低，被分配任務的概率降低。

4 算法描述

算法的基本思想：將待處理任務與可用服務器進行組合形成任務調度集合作為任務搜索集合，隨機設置螞蟻的初始節點，將包含初始節點的任務-接收服務器的映射關系從任務搜索集中刪除，然后計算下次允許訪問的各個節點概率，依照概率隨機訪問下一節點，并從搜索集中刪除包含下一節點的所有任務-接收服務器的映射關系，重復搜索過程。當螞蟻沒有任何節點可以訪問時（即任務搜索集為空），結束這只螞蟻本次搜索，得到一條搜索路徑。比較所有螞蟻本次迭代中的路徑選擇最優路徑，調整信息素，記錄該選擇為當前最優解。根據調整后的信息素和啟發式信息進行下一次搜索，直到迭代完成。從中選出全局最優解作為最優路徑輸出。算法實現步驟和實現流程如圖4和表1所示。

圖4 算法流程圖

表1 算法的具體實現步驟

5 實驗與分析

5.1 實驗目的

為了驗證面向電能質量數據采集的蟻群優化算法的可行性和有效性，設置3組實驗。實驗1為蟻群優化算法的參數對照實驗，找到參數組合的最佳范圍；實驗2對不同負載的服務器，設置基于蟻群算法和蟻群優化算法的任務分配對照實驗；實驗3比較現有數據采集調度方法和面向電能質量數據采集的蟻群優化算法的數據存儲寫入性能。通過分析相關實驗結果，期望驗證面向電能質量數據采集的蟻群優化算法在存儲性能和負載均衡方面更優。

5.2 實驗環境與數據

搭建1臺數據服務器用于采集數據包（任務），作為數據發送端；Hbase集群由3臺裝載CentOS7系統，Hbase1.2.1及Hadoop-2.6.0的接收服務器構成，將調度器部署在一臺服務器上，用于周期性地訪問數據服務器和檢測接收服務器的負載情況，實現任務與接收服務器的關系映射；將數據采集系統部署到3臺接收服務器中，用于接收任務并存儲數據。實驗中采用電網某省2016年12月9日下午4點到晚上12點的真實數據，真實數據采集時間1～3分鐘不等。

實驗1設置蟻群優化算法的參數對照試驗，尋找參數的最佳組合數值范圍，保證算法求得最優解的穩定性，即平均耗時。設置如下：實驗單省數據包的任務分配，數據包大小約52000KB～55000KB；接收服務器的可用資源的差異比約為1：1.8：2.6。設置參數初始值為：α=2，β=3，ρ=0.7。①β，ρ不變，α從1開始以0.5的步長遞增。②α，ρ不變，β從1開始以1.0的步長遞增。③α，β不變，ρ從0.5開始以0.1的步長遞增。①②③取值重復5次并記錄最優解的平均耗時。④總結各參數的最佳取值范圍及參數之間的組合優化設置。實驗結果如表2所示。

實驗結果分析：β，ρ不變，α∈［2，3］時，平均耗時較少，穩定性較高；α，ρ不變，隨著β的遞增，最優解的平均耗時呈遞減趨勢，在β∈［3，5］時，平均耗時較少，算法的穩定性較高；α，β不變時，隨ρ的遞增，平均耗時先降后升，在ρ∈［0.6，0.8］時，平均耗時較少，算法穩定性較好。由此得出參數的最佳取值范圍：α∈［2，3］，β∈［3，5］，ρ∈［0.6，0.8］。并在實驗2、3中設置α=2，β=3，ρ=0.7。

表2 蟻群優化算法參數對照實驗

實驗2設置蟻群算法和蟻群優化算法的任務分配實驗：單省數據包的分配，數據包大小約52000KB～55000KB，接收服務器A，B，C負載存在差異，其可用資源比約為：①1∶1.2∶1.4②1∶1.5∶2③1∶1.8∶2.6④1∶1∶1。實驗結果如表3所示。

表3 負載均衡實驗

實驗結果表明：當服務器的負載相近（④）時，蟻群算法分配任務的隨機性較高，而蟻群優化算法的任務分配比例接近1∶1∶1，負載較均衡；當服務器的負載差異較小（①）時，蟻群算法與蟻群優化算法的分配比例差異較小；當服務器負載差異較大造成處理性能差異較大（②，③）時，蟻群優化算法對均衡負載有一定改善。由此得出：服務器負載較均衡時，蟻群優化算法的任務分配比較平均；隨著負載差異變大，負載較重的服務器接收任務較少或不接收任務，負載輕的接收較多任務，從而在下次的任務調度時，達到服務器負載均衡的效果。

實驗3蟻群優化算法與現有數據采集調度方法的對照實驗。設置如下：現有數據采集調度方法的數據處理節點為1個。蟻群優化算法中擴展節點到3個，接收并存儲大小約9200KB的n個壓縮包；分別記錄服務器數據寫入總量，寫入時間和各服務器的數據分配比例。實驗結果如圖5、6所示。

圖5 兩種調度算法的寫入性能比較

圖6 蟻群優化算法的任務分配比例

實驗結果表明：蟻群優化算法的寫入速率平均達到63692條/s，比現有數據采集調度方法的速率（23473.7條/s）快2.71倍；隨著寫入時間增加，蟻群優化算法和現有數據采集調度方法的寫入速率的比例穩定在2.65倍。同時，每臺服務器都能被分配任務，各服務器的數據接收分配比例基本維持在0.3～0.4之間。由此可見，蟻群優化算法在一定程度上提高了數據寫入速度，降低任務執行時間，執行時間越長，其優勢越明顯，且對資源的分配較為平均。因此，蟻群優化算法的任務調度既可以提高寫入效率，同時可以達到負載均衡的效果。

6 結語

本文針對電能質量數據的采集調度問題，提出蟻群優化算法的多任務調度方法，用于降低整體任務執行時間，實現任務并行處理，且實現接收服務器的負載均衡。作為一種啟發式算法，蟻群算法對解決服務器集群的多任務調度較為有效。基于上述的實驗結果及推理論證，表明合理的參數設置對算法有直接影響；同時，該算法不僅能降低任務執行的總時間，而且對數據接收層的負載起到一定的調節作用。

在下一步工作中，對服務器負載做進一步研究。本文對服務器負載考慮并不全面，后續應結合多個性能指標確定服務器負載狀況。