一種面向智能電網數據采集的傳感器聚合布局構造算法

邱雪松 藺艷斐 邵蘇杰 郭少勇 于 軍

?

一種面向智能電網數據采集的傳感器聚合布局構造算法

邱雪松 藺艷斐*邵蘇杰 郭少勇 于 軍

(北京郵電大學網絡與交換技術國家重點實驗室 北京 100876)

智能電網中分布著大量的無線傳感器用于監測智能電網設備和用戶的運營狀態信息，原始監測數據都采集到數據處理中心會給數據采集通信網絡帶來極大的數據流量壓力。采用在數據采集過程中進行數據聚合的策略，將極大地縮減數據流量，降低通信網絡的開銷。因此聚合節點的選擇以及聚合拓撲的構造成為智能電網數據采集的關鍵問題。該文提出一種基于層次聚類的異步分布式聚合布局構造算法。該算法首先按照層次聚類把所有節點按照距離的遠近聚合構造出一棵采集樹。隨后計算出最佳分組數，按照該分組數進行分組。然后按照異步分布式策略進行最佳聚合節點的選擇以及最佳傳輸拓撲的構造。仿真實驗表明，該算法可以快速找到具有最小開銷的數據聚合方式，提高智能電網數據采集網絡的效率。

智能電網；數據采集；聚合布局；層次聚類；最佳聚合節點

1 引言

智能電網中分布著大量的無線傳感器用于監測一定范圍內的用戶狀態，數據處理中心需要采集這些數據進行分析處理，并作相應的供電調度。隨著電網的建設和發展，智能電網的規模逐漸增大，通信設備種類數量繁多、網絡結構越來越復雜，使得反映智能電網各層節點資源和設備運行狀態以及相關業務的信息數據隨之大幅度增加。原始監測數據都轉發到數據處理中心，會給數據采集通信網絡帶來極大的數據流量壓力。采用在數據采集過程中進行數據聚合的策略，將極大地縮減數據流量，降低通信網絡的開銷。因此聚合節點的選擇以及聚合拓撲的構造成為智能電網數據采集的關鍵問題。

由于智能電網數據采集網絡中的傳感器設備分布密集，距離近的節點采集到的數據存在相關性[10,11]。文獻[12]提出了一種基于最小生成樹的數據聚合思想，在數據采集過程中可以進行數據聚合，從而降低鏈路開銷。但是聚合節點的不同選擇以及不同拓撲構造會帶來不同的開銷結果。因此，如何快速地進行聚合節點的選擇以及如何進行聚合拓撲的構造是智能電網數據采集的關鍵問題。該問題包含3個關鍵部分，首先是分組數目的確定，其次是聚合節點的確定，最后是聚合拓撲的構造。

文獻[13]提出了一種基于蟻群優化算法的傳感器網絡聚合思想，通過稱為“螞蟻”的人工代理探尋數據自源節點至匯聚節點的最優路徑。該聚合策略在路徑構造過程中需要大量鏈路開銷。文獻[14]提到的算法給每一個節點設置一個時間參數，節點時間參數變為零時，該節點發送鏈路信息給時間參數不為零的節點。該方法可以用最小開銷尋找最佳聚合拓撲，但是在整個網絡中只存在一個聚合節點，不適用于大規模的網絡。文獻[12]的算法，首先構造一棵最小生成樹，然后刪除最小生成樹中超過一定閾值的邊，這樣最小生成樹變成森林，在森林中一棵樹就是一個分組。該算法可以完成網絡中節點的分組，但是算法在構造最小生成樹時的效率很低，且不能保證所選鏈路是最小開銷的鏈路。文獻[15]中的算法首先計算出組內節點之間距離的平均值和組間節點之間距離的平均值，然后把這兩個平均值之和作為評測指標，選出最佳分組數。但是所有節點之間距離的平均值可能因為某個特殊的點造成較大的偏差，因此這樣選出的最佳分組數并不是最優的。

基于上述分析，本文在文獻[14]提出的異步分布式思想的基礎上，引入層次劃分的概念，對智能電網數據采集中節點分組，聚合節點選擇，拓撲構造問題進行深入研究。首先進行采集樹的構造，求出兩組中任意兩個點之間距離的平均值，選擇該值最小的兩個組合并，直到所有的節點合并為一個組，完成一棵二叉樹的構造。之后按照最佳分組數評測指標，確定出最佳分組數，根據之前構造出的采集樹和該最佳分組數進行分組。最后針對組內節點，考慮分別以各節點作為聚合節點，給其它每個節點設置一個時間參數，該參數與鏈路開銷成比例，隨著時間的推移，該時間參數逐漸減小，當某節點的時間參數減小到零時，該節點發送信息包到時間參數不為零的節點。按照這種方法可以用盡可能少的算法開銷找到具有最小鏈路開銷的聚合節點。

為此，本文提出一種基于層次聚類的異步分布式聚合布局構造算法。該算法首先利用層次聚類完成采集樹的構造，隨后根據最佳分組數評測指標，計算出最佳分組數進行分組，最后在每個組內用異步分布式采集策略進行聚合節點的選擇、數據聚合服務布局的構造以及鏈路總開銷的計算。仿真實驗驗證了該算法可以快速找到具有最小開銷的數據聚合方式，提高智能電網數據采集網絡的效率。

本文第2節是問題模型，把智能電網數據采集網絡抽象化，介紹算法要解決的主要問題。第3節詳細介紹基于層次聚類的異步分布式聚合布局構造算法。第4節實驗仿真，驗證算法的有效性。第5節給出結論。

2 問題描述

智能電網數據采集無線傳感器網絡如圖1所示，該網絡主要由若干個傳感器和數據處理中心組成。所有傳感器的數據都需要匯聚到數據處理中心，用于分析智能電網設備和用戶的狀態信息。但是隨著智能電網規模的逐漸增大，把原始監測數據都轉發到數據處理中心，會給數據采集網絡帶來較大的數據傳輸壓力，因此需要在數據采集過程中進行數據聚合處理。本文數據采集聚合的思路是：傳感器首先按照層次聚類分為多個組，在每個組中選取一個傳感器作為數據聚合節點；此時若聚合節點數目較大，不能滿足最佳分組數評測指標，則對聚合節點繼續進行分組，直到聚合節點數目滿足該評測指標；最后按照該分組聚合過程將網絡中所有傳感器的數據聚合到數據處理中心。在數據聚合過程中存在兩個主要問題需要解決。

第1個問題是如何對數據采集系統中的傳感器進行分組。首先是智能電網數據采集樹的構造，根據層次聚類構造出一棵二叉采集樹。然后根據該采集樹確定最佳分組數進行分組。精確的分組數關系到網絡鏈路開銷的大小，分組內的節點數目較多，則組內鏈路開銷較大，組間鏈路開銷較少。反之，則組內鏈路開銷較小，組間鏈路開銷較大。因此，最佳的分組方式為分組后組間和組內開銷之和最小。本文采用最佳分組數評測指標對分組性能進行評價，該評測指標在組內分離度和組間分離度兩個因素之間取得平衡點，即可解決最佳分組數目確定問題。

圖1 智能電網數據采集無線傳感器網絡

第2個問題是組內聚合節點的選擇和數據傳輸拓撲的構造。所選擇的聚合節點和構造的數據傳輸拓撲需要滿足組內其它節點沿著該拓撲向聚合節點發送數據時，所需要的鏈路開銷之和最小。本文采用異步分布式聚合策略進行聚合節點的選擇和最佳聚合拓撲的構造，該策略分別把組內每一個節點作為聚合節點，計算出數據聚合時所需要的最小開銷，選擇這些最小開銷中數值最小的節點作為聚合節點，并以該節點最小開銷的計算過程產生的組內數據轉發鏈路作為最佳聚合拓撲。為了以盡可能少的算法開銷找到具有最小鏈路開銷的聚合節點，在組內拓撲確定過程中，優先確定鏈路開銷最小的節點的轉發拓撲，降低聚合節點最小開銷的計算復雜度。

為了解決以上兩個問題，本文提出了智能電網數據采集無線傳感器網絡中基于層次聚類的異步分布式算法，具體見第3節。

圖2 采集樹的構造流程圖

3 基于層次聚類的異步分布式算法

3.1 節點分組

3.1.1采集樹構造 本節采用層次聚類的方法構造智能電網數據采集樹，構造方法如圖2所示。將網絡中的每一個傳感器看作一類，針對這個類，依據距離最近的原則，逐一進行分層聚合。

在構造二叉樹時，新產生的類號是在原類號的基礎上遞增的。假設初始有7個類，距離最近的兩個類是，則把合并后新產生的類是8，如圖3(a)所示。之后新產生類9。按照這種方式最終構造出的采集樹如圖3(c)所示。

圖3 采集樹構造過程

3.1.2分組數確定 由于本文的目的是找到一個數據聚合的最佳布局，使得數據沿著該布局聚合傳輸時，所用的開銷最小。當分組數目較多時，組內的開銷減小，而組間的開銷會增多；分組數目較少時，組內開銷增加，組間開銷減少。如何確定一個最佳分組數，使得組內和組間的開銷之和最小，是本節要解決的主要問題。

為解決該問題，本節提出影響分組效果的兩個因素，組內分離度和組間分離度。具體地，假設網絡中共有個傳感器節點，分成組，第組的組內節點數目用表示，則組傳感器可以表示為集合，其中表示第個傳感器組。表示同一組中任意兩個節點之間的距離開銷。

組內兩兩節點之間開銷的方差為

3.1.3分組方式 在前兩節中已經完成了采集樹的構造和分組數的確定。圖3(c)是構造出的采集樹，分組過程是采集樹構造過程的逆過程，本節以圖3(c)構造出的采集樹為例，介紹分組的具體方式。

由圖3可知，距離越近的類越優先合并，合并時產生的類號越小，因此分組時節點號越大，越優先去掉。如圖4(a)所示，去掉節點13，采集樹變為有兩棵樹的森林，一棵樹中的葉結點是一組，傳感器分為2組；如圖4(b)所示，進一步去掉節點12，傳感器分為3組；如圖4(c)所示，進一步去掉節點11，傳感器分為4組。按照這種分組方式，假設采集樹中有個傳感器(即采集樹中葉結點的數目)，要分為組，則去掉采集樹中節點號最大的個節點即可得到最佳分組方式。

圖4 分組過程

3.2聚合策略

3.2.1聚合流程 本節主要是針對組內的所有節點，進行聚合節點的選擇和聚合拓撲的構造。算法分別把組內每一個節點作為聚合節點，計算出數據聚合時所需要的最小開銷，選擇這些最小開銷中數值最小的節點作為聚合節點，并以該節點最小開銷的計算過程產生的組內數據轉發鏈路作為最佳聚合拓撲。在計算每一個節點作為聚合節點時的最小開銷時，由于給每一個非聚合節點設置一個時間參數，可以優先確定鏈路開銷最小的節點的轉發拓撲，且一旦該節點的拓撲確定即時間參數變為零以后，不再有關于鏈路信息的數據包發送到該節點，因此可以降低算法的鏈路開銷。算法流程如圖5所示。

圖5 異步分布式聚合策略流程圖

3.2.2聚合實例 選擇某一節點作為聚合節點以后，其它節點轉發數據到聚合節點的鏈路開銷計算過程如圖6所示。圖中字母表示節點號，以作為聚合節點，邊上的數字表示鏈路開銷，中表示鏈路開銷，表示時間參數，表示下一跳轉發節點。

如圖6(b)所示，在=0時，初始化各節點的時間參數和鏈路開銷均為直接發送數據到節點所需開銷。圖6(c)顯示在=1時刻，節點的時間參數變為0，其鏈路開銷確定。發送自己的開銷到節點，節點計算從節點轉發的開銷都比原來的小，所以轉發鏈路都要經過節點。如圖6(d)所示，在=3時刻，節點的時間參數變為0，其鏈路開銷確定。發送數據到唯一時間參數不為0的節點,計算從轉發的開銷與原開銷相同，不操作。如圖6(e)所示，在=5時刻，所有節點的時間參數均變為0，此時各節點發送數據到節點的最佳拓撲以及最小開銷確定。節點直接發送數據到節點，節點和的數據經過節點轉發后到達節點，此時的最小鏈路開銷為6。

圖6 異步分布式聚合實例

4 仿真結果分析

4.1 仿真結果

4.1.1采集點分組 本文以隨機分布的傳感器節點和一個數據處理中心構成智能電網數據采集仿真網絡，數據中心位于網絡的中心位置。分別以50, 100, 150個傳感器節點為例，引入和后，其隨分組數目的變化情況分別如圖7和圖8所示。

圖7顯示，對隨機分布的傳感器節點進行分組時，組內分離度隨著分組數目的增多而減少，然而無限增加分組數，即增加用于聚合的傳感器節點是不合理的。因為頻繁的數據聚合會降低數據轉發的效率，同時具有聚合功能的傳感器節點需要更高的開銷。圖8顯示，傳感器節點分別為50,100,150時，組間分離度最大的分組數分別為7,12,15。圖7顯示在分組數目分別大于7,12,15以后，組內分離度的變化已經很小，因此分別選擇7,12,15作為節點數目為50,100,150時的最佳分組數。

4.1.2組內數據聚合 為了模擬具有300個傳感器節點的網絡，在100 m100 m的范圍內，隨機取300個點，根據異步分布式聚合策略產生的網絡轉發拓撲圖如圖9所示，完成數據聚合所需要的最小開銷為10788。

4.2評測指標

為了比較異步分布式聚合策略(Async)，基于最小生成樹的聚合策略(MST)，基于蟻群優化算法的聚合策略(ACAR)的性能，下面從最小開銷和算法執行時間兩個方面加以分析。

圖10顯示，與基于最小生成樹的聚合策略和基于蟻群優化算法的聚合策略相比，異步分布式聚合策略所找到的最小開銷值分別減小了10%~40%和0%~10%。這是因為異步分布式聚合策略尋找的數據轉發拓撲可以保證每一個節點到聚合節點的鏈路開銷最小，因此總開銷是最小的。圖11顯示，異步分布式聚合策略所用時間隨節點數目的變化很緩慢，而基于蟻群優化算法的聚合策略和基于最小生成樹的聚合策略所用時間隨著節點數目的增加，以接近于指數的速度增長。異步分布式聚合策略的高效性是因為該聚合策略優先確定距離近的節點的轉發拓撲，且轉發拓撲已確定的節點不再參與后續轉發拓撲構造過程。因此異步分布式聚合策略可以明顯提高智能電網數據聚合的效率，網絡規模增大時，其效率提高更加明顯，更適用于大規模網絡。

??????????? 圖7 CI隨分組數目的變化 ???? ? ???? 圖8 CE隨分組數目的變化 ????? ????? 圖9 異步分布式聚合策略產生的樹

圖10 兩種策略計算的最小開銷隨節點數目的變化 ?????????? 圖11 兩種策略所用時間隨節點數目的變化

5 結束語

智能電網中分布著大量的無線傳感器用于監測一定范圍內的用戶狀態，數據處理中心需要采集這些數據進行分析處理。為了提高數據采集的效率，需要在數據傳輸過程中進行聚合，因此需要設計一個高效的算法尋找數據聚合的最佳布局。為此，本文提出了基于層次聚類的異步分布式算法，該算法可以按照最佳分組數和傳感器節點的位置對傳感器節點進行分組，在組內利用異步分布式聚合策略進行最佳聚合節點的選擇以及最佳聚合拓撲的構造。仿真實驗表明，與基于蟻群優化算法的聚合策略和基于最小生成樹的聚合策略相比，該算法可以以更高的速率找到具有最小鏈路開銷的數據傳輸方式，適用于大規模智能電網聚合網絡。

[1] Chang Chih-yung, Lin Chih-yu, and Kuo Chin-hwa. EBDC: an energy-balanced data collection mechanism using a mobile data collector in WSNs[J]., 2012, 12(5): 5850-5871.

[2] 錢志鴻, 王義君. 面向物聯網的無線傳感器網絡綜述[J]. 電子與信息學報, 2013, 35(1): 215-227.

Qian Zhi-hong and Wang Yi-jun. Internet of things-oriented wireless sensor networks review[J].&, 2013, 35(1): 215-227.

[3] 付喬. 移動無線傳感器網絡數據采集算法設計[D]. [碩士論文], 清華大學, 2013.

[4] 葉寧, 王汝傳. 傳感器網絡中一種基于估計代價的數據聚合樹生成算法[J]. 電子學報, 2007, 35(5): 806-810.

Ye Ning and Wang Ru-chuan.A tree formation algorithm for data aggregation based on estimate cost in sensor networks[J]., 2007, 35(5): 806-810.

[5] 李宏, 于宏毅, 李林海, 等. 對無線傳感器網絡區域數據聚合有效性的研究[J]. 計算機應用, 2007, 27(9): 2218-2226.

Li Hong, Yu Hong-yi, Li Lin-hai,..Efficiency of area- based data aggregation in wireless sensor networks[J]., 2007, 27(9): 2218-2226.

[6] 張強, 盧瀟, 崔曉臣. 基于分簇的無線傳感器網絡數據聚合方案研究[J]. 傳感器技術學報, 2010, 23(12): 1778-1782.

Zhang Qiang, Lu Xiao, and Cui Xiao-chen. Research on the scheme of data aggregation based on clustering for wireless sensor network[J]., 2010, 23(12): 1778-1782.

[7] 陳杰. 無線傳感器網絡中基于數據聚合路由協議研究[D]. [碩士論文], 西安電子科技大學, 2013.

[8] 張軍, 楊子晨. 多傳感器數據采集系統中的數據融合研究[J]. 傳感器與微系統, 2014, 33(3): 52-57.

Zhang Jun, and Yang Zi-chen. Study on data fusion of multi-sensor data acquisition system[J]., 2014, 33(3): 52-57.

[9] 吉佳, 溫巧燕, 張華. 無線傳感器網絡中基于分簇的數據聚合機制[J]. 傳感器與微系統, 2015, 34(1): 17-20.

Ji Jia, Wen Qiao-yan, and Zhang Hua. Cluster-based data aggregation scheme in wireless sensor networks[J]., 2015, 34(1): 17-20.

[10] 陳鳳超. 無線傳感器網絡路由及匯聚節點選址算法研究[D]. [博士論文], 華南理工大學, 2011.

[11] 吳堅, 張偉. 基于無線傳感器網絡的數據采集實驗設計[J]. 實驗室研究與探索, 2013, 32(6): 271-286.

Wu Jian and Zhang Wei. Design of an experiment for data acquisition based on wireless sensor network[J]., 2013, 32(6): 271-286.

[12] 徐晨凱, 高茂庭. 改進的最小生成樹自適應分層聚類算法[J]. 計算機工程與應用, 2014, 50(22): 149-153.

Xu Chen-kai and Gao Mao-ting. Improved adaptive hierarchical clustering algorithm based on minimum spanning tree[J]., 2014, 50(22): 149-153.

[13] 葉寧, 王汝傳. 基于蟻群算法的無線傳感器網絡數據聚合路由算法[J]. 南京郵電大學學報(自然科學版), 2008, 28(2): 63-68.

Ye Ning, and Wang Ru-chuan.A routing algorithm for data aggregation based on ACA in wireless sensor networks[J].(), 2008, 28(2): 63-68.

[14] Lu Zong-qing and Wen Yong-gang. Distributed algorithm for tree-structured data aggregation service placement in smart grid[J]., 2014, 8(2): 553-561.

[15] 陳黎飛, 姜青山, 王聲瑞. 基于層次劃分的最佳聚類數確定方法[J]. 軟件學報, 2008, 19(1): 62-72.

Chen Li-fei, Jiang Qing-shan, and Wang Sheng-rui. A hierarchical method for determining the number of clusters[J]., 2008, 19(1): 62-72.

Sensor Aggregation Distribution Construction Algorithm for Smart Grid Data Collection System

Qiu Xue-song Lin Yan-fei Shao Su-jie Guo Shao-yong Yu Jun

(,,100876,)

Large-scale of wireless sensors are distributed to monitor smart grid equipment and user,s operating status information in smart grid. The original monitoring data are all collected to data processing center. And it brings huge data traffic pressure for communication network. Thus it is necessary to use data aggregation strategy in the process of data collection to reduce data traffic greatly, and reduce the overhead of communication network. This paper proposes asynchronous distributed aggregation layout construction algorithm based on hierarchical clustering. Firstly, a collection tree is constructed with the distance of all the nodes based on hierarchical clustering. Then the optimal numbers of clusters and group are calculated. And then, this paper selects the optimal aggregation nodes and constructs the best transmit topology with asynchronous distributed strategy. Finally, the simulation experiment shows that the algorithm could find the data aggregation mode of minimum cost quickly, and improve the efficiency for data collection in smart grid.

Smart grid; Data collection; Aggregation distribution; Hierarchical clustering; Optimal aggregation node

TP393

A

1009-5896(2015)10-2411-07

10.11999/JEIT150231

2015-02-09；改回日期：2015-05-14；

2015-06-29

藺艷斐 907389726@qq.com

國家支撐計劃(2015BAG10B01)和國家自然科學基金(61372108)

The National Key Technology Support Program (2015BAG10B01); The National Natural Science Foundation of China (61372108)

邱雪松： 男，1973 年生，博士生導師，教授，研究方向為網絡與業務管理.

藺艷斐： 女，1992年生，碩士生，研究方向為智能電網、網絡與業務管理.

邵蘇杰： 男，1985 年生，博士生，研究方向為網絡管理與智能電網.

郭少勇： 男，1985 年生，博士后，研究方向為網絡管理、終端管理與智能電網.

于 軍： 男，1964年生，高級工程師，研究方向為通信網絡管理.