一種面向智能電網(wǎng)數(shù)據(jù)采集的傳感器聚合布局構(gòu)造算法

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

?

一種面向智能電網(wǎng)數(shù)據(jù)采集的傳感器聚合布局構(gòu)造算法

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

(北京郵電大學(xué)網(wǎng)絡(luò)與交換技術(shù)國家重點(diǎn)實(shí)驗(yàn)室 北京 100876)

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

智能電網(wǎng)；數(shù)據(jù)采集；聚合布局；層次聚類；最佳聚合節(jié)點(diǎn)

1 引言

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

由于智能電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)中的傳感器設(shè)備分布密集，距離近的節(jié)點(diǎn)采集到的數(shù)據(jù)存在相關(guān)性[10,11]。文獻(xiàn)[12]提出了一種基于最小生成樹的數(shù)據(jù)聚合思想，在數(shù)據(jù)采集過程中可以進(jìn)行數(shù)據(jù)聚合，從而降低鏈路開銷。但是聚合節(jié)點(diǎn)的不同選擇以及不同拓?fù)錁?gòu)造會帶來不同的開銷結(jié)果。因此，如何快速地進(jìn)行聚合節(jié)點(diǎn)的選擇以及如何進(jìn)行聚合拓?fù)涞臉?gòu)造是智能電網(wǎng)數(shù)據(jù)采集的關(guān)鍵問題。該問題包含3個(gè)關(guān)鍵部分，首先是分組數(shù)目的確定，其次是聚合節(jié)點(diǎn)的確定，最后是聚合拓?fù)涞臉?gòu)造。

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

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

為此，本文提出一種基于層次聚類的異步分布式聚合布局構(gòu)造算法。該算法首先利用層次聚類完成采集樹的構(gòu)造，隨后根據(jù)最佳分組數(shù)評測指標(biāo)，計(jì)算出最佳分組數(shù)進(jìn)行分組，最后在每個(gè)組內(nèi)用異步分布式采集策略進(jìn)行聚合節(jié)點(diǎn)的選擇、數(shù)據(jù)聚合服務(wù)布局的構(gòu)造以及鏈路總開銷的計(jì)算。仿真實(shí)驗(yàn)驗(yàn)證了該算法可以快速找到具有最小開銷的數(shù)據(jù)聚合方式，提高智能電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)的效率。

本文第2節(jié)是問題模型，把智能電網(wǎng)數(shù)據(jù)采集網(wǎng)絡(luò)抽象化，介紹算法要解決的主要問題。第3節(jié)詳細(xì)介紹基于層次聚類的異步分布式聚合布局構(gòu)造算法。第4節(jié)實(shí)驗(yàn)仿真，驗(yàn)證算法的有效性。第5節(jié)給出結(jié)論。

2 問題描述

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

第1個(gè)問題是如何對數(shù)據(jù)采集系統(tǒng)中的傳感器進(jìn)行分組。首先是智能電網(wǎng)數(shù)據(jù)采集樹的構(gòu)造，根據(jù)層次聚類構(gòu)造出一棵二叉采集樹。然后根據(jù)該采集樹確定最佳分組數(shù)進(jìn)行分組。精確的分組數(shù)關(guān)系到網(wǎng)絡(luò)鏈路開銷的大小，分組內(nèi)的節(jié)點(diǎn)數(shù)目較多，則組內(nèi)鏈路開銷較大，組間鏈路開銷較少。反之，則組內(nèi)鏈路開銷較小，組間鏈路開銷較大。因此，最佳的分組方式為分組后組間和組內(nèi)開銷之和最小。本文采用最佳分組數(shù)評測指標(biāo)對分組性能進(jìn)行評價(jià)，該評測指標(biāo)在組內(nèi)分離度和組間分離度兩個(gè)因素之間取得平衡點(diǎn)，即可解決最佳分組數(shù)目確定問題。

圖1 智能電網(wǎng)數(shù)據(jù)采集無線傳感器網(wǎng)絡(luò)

第2個(gè)問題是組內(nèi)聚合節(jié)點(diǎn)的選擇和數(shù)據(jù)傳輸拓?fù)涞臉?gòu)造。所選擇的聚合節(jié)點(diǎn)和構(gòu)造的數(shù)據(jù)傳輸拓?fù)湫枰獫M足組內(nèi)其它節(jié)點(diǎn)沿著該拓?fù)湎蚓酆瞎?jié)點(diǎn)發(fā)送數(shù)據(jù)時(shí)，所需要的鏈路開銷之和最小。本文采用異步分布式聚合策略進(jìn)行聚合節(jié)點(diǎn)的選擇和最佳聚合拓?fù)涞臉?gòu)造，該策略分別把組內(nèi)每一個(gè)節(jié)點(diǎn)作為聚合節(jié)點(diǎn)，計(jì)算出數(shù)據(jù)聚合時(shí)所需要的最小開銷，選擇這些最小開銷中數(shù)值最小的節(jié)點(diǎn)作為聚合節(jié)點(diǎn)，并以該節(jié)點(diǎn)最小開銷的計(jì)算過程產(chǎn)生的組內(nèi)數(shù)據(jù)轉(zhuǎn)發(fā)鏈路作為最佳聚合拓?fù)?。為了以盡可能少的算法開銷找到具有最小鏈路開銷的聚合節(jié)點(diǎn)，在組內(nèi)拓?fù)浯_定過程中，優(yōu)先確定鏈路開銷最小的節(jié)點(diǎn)的轉(zhuǎn)發(fā)拓?fù)?，降低聚合?jié)點(diǎn)最小開銷的計(jì)算復(fù)雜度。

為了解決以上兩個(gè)問題，本文提出了智能電網(wǎng)數(shù)據(jù)采集無線傳感器網(wǎng)絡(luò)中基于層次聚類的異步分布式算法，具體見第3節(jié)。

圖2 采集樹的構(gòu)造流程圖

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

3.1 節(jié)點(diǎn)分組

3.1.1采集樹構(gòu)造 本節(jié)采用層次聚類的方法構(gòu)造智能電網(wǎng)數(shù)據(jù)采集樹，構(gòu)造方法如圖2所示。將網(wǎng)絡(luò)中的每一個(gè)傳感器看作一類，針對這個(gè)類，依據(jù)距離最近的原則，逐一進(jìn)行分層聚合。

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

圖3 采集樹構(gòu)造過程

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

為解決該問題，本節(jié)提出影響分組效果的兩個(gè)因素，組內(nèi)分離度和組間分離度。具體地，假設(shè)網(wǎng)絡(luò)中共有個(gè)傳感器節(jié)點(diǎn)，分成組，第組的組內(nèi)節(jié)點(diǎn)數(shù)目用表示，則組傳感器可以表示為集合，其中表示第個(gè)傳感器組。表示同一組中任意兩個(gè)節(jié)點(diǎn)之間的距離開銷。

組內(nèi)兩兩節(jié)點(diǎn)之間開銷的方差為

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

由圖3可知，距離越近的類越優(yōu)先合并，合并時(shí)產(chǎn)生的類號越小，因此分組時(shí)節(jié)點(diǎn)號越大，越優(yōu)先去掉。如圖4(a)所示，去掉節(jié)點(diǎn)13，采集樹變?yōu)橛袃煽脴涞纳?，一棵樹中的葉結(jié)點(diǎn)是一組，傳感器分為2組；如圖4(b)所示，進(jìn)一步去掉節(jié)點(diǎn)12，傳感器分為3組；如圖4(c)所示，進(jìn)一步去掉節(jié)點(diǎn)11，傳感器分為4組。按照這種分組方式，假設(shè)采集樹中有個(gè)傳感器(即采集樹中葉結(jié)點(diǎn)的數(shù)目)，要分為組，則去掉采集樹中節(jié)點(diǎn)號最大的個(gè)節(jié)點(diǎn)即可得到最佳分組方式。

圖4 分組過程

3.2聚合策略

3.2.1聚合流程 本節(jié)主要是針對組內(nèi)的所有節(jié)點(diǎn)，進(jìn)行聚合節(jié)點(diǎn)的選擇和聚合拓?fù)涞臉?gòu)造。算法分別把組內(nèi)每一個(gè)節(jié)點(diǎn)作為聚合節(jié)點(diǎn)，計(jì)算出數(shù)據(jù)聚合時(shí)所需要的最小開銷，選擇這些最小開銷中數(shù)值最小的節(jié)點(diǎn)作為聚合節(jié)點(diǎn)，并以該節(jié)點(diǎn)最小開銷的計(jì)算過程產(chǎn)生的組內(nèi)數(shù)據(jù)轉(zhuǎn)發(fā)鏈路作為最佳聚合拓?fù)?。在?jì)算每一個(gè)節(jié)點(diǎn)作為聚合節(jié)點(diǎn)時(shí)的最小開銷時(shí)，由于給每一個(gè)非聚合節(jié)點(diǎn)設(shè)置一個(gè)時(shí)間參數(shù)，可以優(yōu)先確定鏈路開銷最小的節(jié)點(diǎn)的轉(zhuǎn)發(fā)拓?fù)?，且一旦該?jié)點(diǎn)的拓?fù)浯_定即時(shí)間參數(shù)變?yōu)榱阋院?，不再有關(guān)于鏈路信息的數(shù)據(jù)包發(fā)送到該節(jié)點(diǎn)，因此可以降低算法的鏈路開銷。算法流程如圖5所示。

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

3.2.2聚合實(shí)例 選擇某一節(jié)點(diǎn)作為聚合節(jié)點(diǎn)以后，其它節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)到聚合節(jié)點(diǎn)的鏈路開銷計(jì)算過程如圖6所示。圖中字母表示節(jié)點(diǎn)號，以作為聚合節(jié)點(diǎn)，邊上的數(shù)字表示鏈路開銷，中表示鏈路開銷，表示時(shí)間參數(shù)，表示下一跳轉(zhuǎn)發(fā)節(jié)點(diǎn)。

如圖6(b)所示，在=0時(shí)，初始化各節(jié)點(diǎn)的時(shí)間參數(shù)和鏈路開銷均為直接發(fā)送數(shù)據(jù)到節(jié)點(diǎn)所需開銷。圖6(c)顯示在=1時(shí)刻，節(jié)點(diǎn)的時(shí)間參數(shù)變?yōu)?，其鏈路開銷確定。發(fā)送自己的開銷到節(jié)點(diǎn)，節(jié)點(diǎn)計(jì)算從節(jié)點(diǎn)轉(zhuǎn)發(fā)的開銷都比原來的小，所以轉(zhuǎn)發(fā)鏈路都要經(jīng)過節(jié)點(diǎn)。如圖6(d)所示，在=3時(shí)刻，節(jié)點(diǎn)的時(shí)間參數(shù)變?yōu)?，其鏈路開銷確定。發(fā)送數(shù)據(jù)到唯一時(shí)間參數(shù)不為0的節(jié)點(diǎn),計(jì)算從轉(zhuǎn)發(fā)的開銷與原開銷相同，不操作。如圖6(e)所示，在=5時(shí)刻，所有節(jié)點(diǎn)的時(shí)間參數(shù)均變?yōu)?，此時(shí)各節(jié)點(diǎn)發(fā)送數(shù)據(jù)到節(jié)點(diǎn)的最佳拓?fù)湟约白钚￠_銷確定。節(jié)點(diǎn)直接發(fā)送數(shù)據(jù)到節(jié)點(diǎn)，節(jié)點(diǎn)和的數(shù)據(jù)經(jīng)過節(jié)點(diǎn)轉(zhuǎn)發(fā)后到達(dá)節(jié)點(diǎn)，此時(shí)的最小鏈路開銷為6。

圖6 異步分布式聚合實(shí)例

4 仿真結(jié)果分析

4.1 仿真結(jié)果

4.1.1采集點(diǎn)分組 本文以隨機(jī)分布的傳感器節(jié)點(diǎn)和一個(gè)數(shù)據(jù)處理中心構(gòu)成智能電網(wǎng)數(shù)據(jù)采集仿真網(wǎng)絡(luò)，數(shù)據(jù)中心位于網(wǎng)絡(luò)的中心位置。分別以50, 100, 150個(gè)傳感器節(jié)點(diǎn)為例，引入和后，其隨分組數(shù)目的變化情況分別如圖7和圖8所示。

圖7顯示，對隨機(jī)分布的傳感器節(jié)點(diǎn)進(jìn)行分組時(shí)，組內(nèi)分離度隨著分組數(shù)目的增多而減少，然而無限增加分組數(shù)，即增加用于聚合的傳感器節(jié)點(diǎn)是不合理的。因?yàn)轭l繁的數(shù)據(jù)聚合會降低數(shù)據(jù)轉(zhuǎn)發(fā)的效率，同時(shí)具有聚合功能的傳感器節(jié)點(diǎn)需要更高的開銷。圖8顯示，傳感器節(jié)點(diǎn)分別為50,100,150時(shí)，組間分離度最大的分組數(shù)分別為7,12,15。圖7顯示在分組數(shù)目分別大于7,12,15以后，組內(nèi)分離度的變化已經(jīng)很小，因此分別選擇7,12,15作為節(jié)點(diǎn)數(shù)目為50,100,150時(shí)的最佳分組數(shù)。

4.1.2組內(nèi)數(shù)據(jù)聚合 為了模擬具有300個(gè)傳感器節(jié)點(diǎn)的網(wǎng)絡(luò)，在100 m100 m的范圍內(nèi)，隨機(jī)取300個(gè)點(diǎn)，根據(jù)異步分布式聚合策略產(chǎn)生的網(wǎng)絡(luò)轉(zhuǎn)發(fā)拓?fù)鋱D如圖9所示，完成數(shù)據(jù)聚合所需要的最小開銷為10788。

4.2評測指標(biāo)

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

圖10顯示，與基于最小生成樹的聚合策略和基于蟻群優(yōu)化算法的聚合策略相比，異步分布式聚合策略所找到的最小開銷值分別減小了10%~40%和0%~10%。這是因?yàn)楫惒椒植际骄酆喜呗詫ふ业臄?shù)據(jù)轉(zhuǎn)發(fā)拓?fù)淇梢员ＷC每一個(gè)節(jié)點(diǎn)到聚合節(jié)點(diǎn)的鏈路開銷最小，因此總開銷是最小的。圖11顯示，異步分布式聚合策略所用時(shí)間隨節(jié)點(diǎn)數(shù)目的變化很緩慢，而基于蟻群優(yōu)化算法的聚合策略和基于最小生成樹的聚合策略所用時(shí)間隨著節(jié)點(diǎn)數(shù)目的增加，以接近于指數(shù)的速度增長。異步分布式聚合策略的高效性是因?yàn)樵摼酆喜呗詢?yōu)先確定距離近的節(jié)點(diǎn)的轉(zhuǎn)發(fā)拓?fù)?，且轉(zhuǎn)發(fā)拓?fù)湟汛_定的節(jié)點(diǎn)不再參與后續(xù)轉(zhuǎn)發(fā)拓?fù)錁?gòu)造過程。因此異步分布式聚合策略可以明顯提高智能電網(wǎng)數(shù)據(jù)聚合的效率，網(wǎng)絡(luò)規(guī)模增大時(shí)，其效率提高更加明顯，更適用于大規(guī)模網(wǎng)絡(luò)。

??????????? 圖7 CI隨分組數(shù)目的變化 ???? ? ???? 圖8 CE隨分組數(shù)目的變化 ????? ????? 圖9 異步分布式聚合策略產(chǎn)生的樹

圖10 兩種策略計(jì)算的最小開銷隨節(jié)點(diǎn)數(shù)目的變化 ?????????? 圖11 兩種策略所用時(shí)間隨節(jié)點(diǎn)數(shù)目的變化

5 結(jié)束語

智能電網(wǎng)中分布著大量的無線傳感器用于監(jiān)測一定范圍內(nèi)的用戶狀態(tài)，數(shù)據(jù)處理中心需要采集這些數(shù)據(jù)進(jìn)行分析處理。為了提高數(shù)據(jù)采集的效率，需要在數(shù)據(jù)傳輸過程中進(jìn)行聚合，因此需要設(shè)計(jì)一個(gè)高效的算法尋找數(shù)據(jù)聚合的最佳布局。為此，本文提出了基于層次聚類的異步分布式算法，該算法可以按照最佳分組數(shù)和傳感器節(jié)點(diǎn)的位置對傳感器節(jié)點(diǎn)進(jìn)行分組，在組內(nèi)利用異步分布式聚合策略進(jìn)行最佳聚合節(jié)點(diǎn)的選擇以及最佳聚合拓?fù)涞臉?gòu)造。仿真實(shí)驗(yàn)表明，與基于蟻群優(yōu)化算法的聚合策略和基于最小生成樹的聚合策略相比，該算法可以以更高的速率找到具有最小鏈路開銷的數(shù)據(jù)傳輸方式，適用于大規(guī)模智能電網(wǎng)聚合網(wǎng)絡(luò)。

[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] 錢志鴻, 王義君. 面向物聯(lián)網(wǎng)的無線傳感器網(wǎng)絡(luò)綜述[J]. 電子與信息學(xué)報(bào), 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] 付喬. 移動無線傳感器網(wǎng)絡(luò)數(shù)據(jù)采集算法設(shè)計(jì)[D]. [碩士論文], 清華大學(xué), 2013.

[4] 葉寧, 王汝傳. 傳感器網(wǎng)絡(luò)中一種基于估計(jì)代價(jià)的數(shù)據(jù)聚合樹生成算法[J]. 電子學(xué)報(bào), 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] 李宏, 于宏毅, 李林海, 等. 對無線傳感器網(wǎng)絡(luò)區(qū)域數(shù)據(jù)聚合有效性的研究[J]. 計(jì)算機(jī)應(yīng)用, 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] 張強(qiáng), 盧瀟, 崔曉臣. 基于分簇的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合方案研究[J]. 傳感器技術(shù)學(xué)報(bào), 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] 陳杰. 無線傳感器網(wǎng)絡(luò)中基于數(shù)據(jù)聚合路由協(xié)議研究[D]. [碩士論文], 西安電子科技大學(xué), 2013.

[8] 張軍, 楊子晨. 多傳感器數(shù)據(jù)采集系統(tǒng)中的數(shù)據(jù)融合研究[J]. 傳感器與微系統(tǒng), 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] 吉佳, 溫巧燕, 張華. 無線傳感器網(wǎng)絡(luò)中基于分簇的數(shù)據(jù)聚合機(jī)制[J]. 傳感器與微系統(tǒng), 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] 陳鳳超. 無線傳感器網(wǎng)絡(luò)路由及匯聚節(jié)點(diǎn)選址算法研究[D]. [博士論文], 華南理工大學(xué), 2011.

[11] 吳堅(jiān), 張偉. 基于無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)采集實(shí)驗(yàn)設(shè)計(jì)[J]. 實(shí)驗(yàn)室研究與探索, 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ìn)的最小生成樹自適應(yīng)分層聚類算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 葉寧, 王汝傳. 基于蟻群算法的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)聚合路由算法[J]. 南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 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] 陳黎飛, 姜青山, 王聲瑞. 基于層次劃分的最佳聚類數(shù)確定方法[J]. 軟件學(xué)報(bào), 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

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

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

邱雪松： 男，1973 年生，博士生導(dǎo)師，教授，研究方向?yàn)榫W(wǎng)絡(luò)與業(yè)務(wù)管理.

藺艷斐： 女，1992年生，碩士生，研究方向?yàn)橹悄茈娋W(wǎng)、網(wǎng)絡(luò)與業(yè)務(wù)管理.

邵蘇杰： 男，1985 年生，博士生，研究方向?yàn)榫W(wǎng)絡(luò)管理與智能電網(wǎng).

郭少勇： 男，1985 年生，博士后，研究方向?yàn)榫W(wǎng)絡(luò)管理、終端管理與智能電網(wǎng).

于 軍： 男，1964年生，高級工程師，研究方向?yàn)橥ㄐ啪W(wǎng)絡(luò)管理.