基于多因素加權的電力線通信組網算法

謝志遠，王夢雨，曹旺斌,2

(1.華北電力大學 電子與通信工程系，河北 保定 071003；2.華北電力大學 河北省電力物聯(lián)網技術重點實驗室，河北 保定 071003；3.河北省互感器技術創(chuàng)新中心，河北 保定 071003)

0 引言

近年來，隨著經濟的快速發(fā)展，傳統(tǒng)電網逐漸不能滿足人們日益增長的需求，建立統(tǒng)一堅強的智能電網成為未來電力系統(tǒng)和能源互聯(lián)網的發(fā)展方向[1-2]。可靠的通信方式是建設智能電網的關鍵技術,其中低壓電力線通信技術利用隨處可見的電力傳輸線作為傳輸數據的通信介質，無需費時費力地重新布線，在廣泛性、靈活性和經濟性上具有不可比擬的優(yōu)勢，因而被廣泛應用在智能配電網用電信息采集、智能路燈控制、智能樓宇自動化、智能家居和光伏能源接入以及環(huán)保用電監(jiān)測等眾多領域[3-4]。然而,電力線與光纖、同軸電纜等專門的通信介質不同，其線路上的噪聲干擾、關聯(lián)電氣設備的通斷以及線路阻抗的變化等因素，導致信道具有明顯的時變特征，從而對電力線通信的通信效果產生了不良影響。

為了更好地利用低壓電力線的天然優(yōu)勢，研究人員一直致力于改善該通信方式的不足之處。從針對物理層的信道建模[5]、信道估計[6]和信道編碼[7]，到網絡層各種優(yōu)化組網方法[8]的提出，都是為了提高其通信可靠性。物理層與硬件結構有關，相對來說不易實現(xiàn)，因此研究網絡層更具有實際意義。網絡層主要利用中繼思想，通過某種算法選取中繼節(jié)點來實現(xiàn)組網路由。組網路由算法主要分為3類:以分簇算法及其改進算法為代表的分級分層式算法[9-11]、以蟻群算法為代表的智能仿生類算法[12-14]以及一些其他算法，如文獻[15]提出一種以鄰節(jié)點覆蓋為核心的改進分簇算法，算法過程中加入動態(tài)延時轉發(fā)機制，經過仿真驗證了算法的有效性；文獻[16]結合萊維飛行機制和蟻群算法，提出基于迭代激勵機制的電力線通信組網算法；文獻[17]提出了基于圖論生成樹的路由算法等。

由上述分析可知，目前對網絡層的研究已經取得了顯著的效果。分簇算法因思想簡單和擴展性強等優(yōu)點，在低壓電力線通信中的應用最為廣泛，但還是存在一些問題。比如在選擇簇頭節(jié)點時，現(xiàn)有算法往往采用單一的選擇標準，導致某些節(jié)點很容易被選為簇頭，無法保障節(jié)點公平性和負載平衡。因此，本文在選擇簇頭時考慮多種因素，包括節(jié)點連通度、負載以及節(jié)點的有效通信距離和，并在組網過程中借鑒人工蛛網的思想，為通信節(jié)點選擇同層鄰居節(jié)點，增加可選路徑。仿真結果表明，改進后的算法形成的簇結構更加均勻，有利于保障網絡的穩(wěn)定和負載平衡，簇頭個數相比傳統(tǒng)算法有所減少，一定程度上改善了網絡性能，同時，備份路徑的引入避免了頻繁的網絡重構，提高了通信可靠性。

1 低壓電力線通信組網算法基礎分析

1.1 低壓電力線通信網絡模型

了解網絡的拓撲結構是分析整個系統(tǒng)的基礎。圖1給出了一種常見的低壓電力線通信網絡樹型物理拓撲結構。圖中變壓器的二次側為A,B,C三相配電網，每一相的網關節(jié)點負責管理和收集該相位管轄下的普通子節(jié)點的信息。一般，在不考慮相間耦合器的情況下，三相之間不能相互通信，因此研究低壓電力線通信網絡的單相物理拓撲結構即具有代表性[18]。為便于表述，下文統(tǒng)稱網關節(jié)點為中心節(jié)點，普通子節(jié)點為通信節(jié)點或節(jié)點。

圖1 低壓電力線通信物理拓撲Fig.1 Physical topology of low-voltage power line communication

低壓電力線通信通過電力線進行數據傳輸，信道時變性強，電力線上的信號衰減和噪聲干擾等問題雖然不會改變節(jié)點之間的電氣連接關系，但會降低某些鏈路的通信質量，從而導致部分節(jié)點失去和中心節(jié)點直接通信的能力。因此，即使2個節(jié)點在物理上是連接的，在邏輯上也可能是斷開的。圖2給出了低壓電力線通信邏輯拓撲結構。

如圖2所示，網絡中包含1個中心節(jié)點和b個通信節(jié)點，由于低壓電力線通信網絡中的節(jié)點傳輸范圍有限，只有位于中心節(jié)點可直接通信范圍內的a個通信節(jié)點能夠與中心節(jié)點直接進行數據收發(fā)，除此之外的(b-a)個通信節(jié)點，由于處在中心節(jié)點的可直接通信范圍之外，距離中心節(jié)點太遠，只能借助可直接通信范圍內的a個通信節(jié)點作為與中心節(jié)點進行溝通的“橋梁”，最終全部節(jié)點都能實現(xiàn)與中心節(jié)點的數據通信。這a個通信節(jié)點被稱為“中繼節(jié)點”，具有數據轉發(fā)的功能。對于低壓電力線通信網絡，選擇合適的中繼節(jié)點至關重要。

圖2 低壓電力線通信邏輯拓撲Fig.2 Logic topology of low-voltage power line communication

1.2 傳統(tǒng)分簇算法

分簇算法啟蒙于無線傳感器網絡(Wireless Senor Network,WSN)，后來也被廣泛應用在移動自組網(Ad-Hoc Network)中。低壓電力線通信網絡與WSN和移動自組網具有相似的網絡特征，如邏輯拓撲都動態(tài)變化和節(jié)點傳輸距離都有限等，因此在組網時可以借鑒分簇的思想。

分簇算法具有很強的擴展性和延伸性，能夠滿足日益擴大的網絡規(guī)模的需求，實現(xiàn)數據從源節(jié)點到目的節(jié)點的快速、有效、可靠的通信。分簇算法的核心思想是用特定的算法在網絡中選擇合適的節(jié)點充當“領導者”的角色，即簇頭；簇頭再根據需要選擇自己的成員，即簇員。一個簇頭節(jié)點和至少一個簇員節(jié)點組成一個完整的簇結構，分簇算法就是將網絡劃分為多個簇結構。一個簇員是否可以同屬于不同的簇，決定了該簇結構是非交疊[9]的還是交疊[19]的。

以往的文獻對非交疊分簇算法和交疊分簇算法已經介紹的非常清楚，圖3和圖4給出了這2類算法的結構?？偟膩碚f，非交疊分簇算法形成的是網絡結構簡單的樹形拓撲，網絡連通性和可靠性較差，從中心節(jié)點到每個目的通信節(jié)點只有單一的通信鏈路。交疊分簇算法形成的是網狀結構，節(jié)點之間存在多條通信路徑，與非交疊相比，可靠性雖得到了提高，但增加了路由開銷?？紤]到實際因素，目前應用較多的還是非交疊分簇算法。

圖3 非交疊分簇算法結構Fig.3 Non-overlapping clustering algorithm structure

圖4 交疊分簇算法結構Fig.4 Overlapping clustering algorithm structure

1.3 人工蛛網思想

蛛網組網算法是研究人員受到蜘蛛捕食行為和自然蛛網結構啟發(fā)后提出的一種組網方法，屬于智能仿生類算法。文獻[20]提出了基于人工蛛網的網絡模型，將蛛網組網算法應用到低壓電力線通信組網上，通過仿真實驗證明了該方法的可行性，同時結果表明，基于蛛網的組網算法具有很強的可靠性和抗毀性。

圖5給出了人工蛛網邏輯拓撲。從圖中可以看出，對于每一個通信節(jié)點，都存在2個可以直接通信的鄰居節(jié)點，當中心節(jié)點不能與目的通信節(jié)點直接通信時，可以將其鄰居節(jié)點作為中繼，進而與目的節(jié)點通信。鄰居鏈路的存在，等同于為通信節(jié)點增加備份路徑，能夠保障通信的可靠性。

圖5 人工蛛網邏輯拓撲Fig.5 Logical topology of artificial cobweb

1.4 組網特點及要求

① 通信節(jié)點應具有中繼轉發(fā)功能。電力線信道干擾大，噪聲環(huán)境惡劣，節(jié)點的傳輸距離受到影響，因此節(jié)點需要具有轉發(fā)數據的功能。

② 算法自適應能力強，擴展性好。電力線上的負載類型多種多樣，拓撲結構復雜多變，并且信道的衰減特性、噪聲特性等會導致電力線通信網絡的隨機性和時變性，所以組網算法需要具有一定的愈合能力和自適應能力，能夠適應網絡拓撲的動態(tài)改變。

③ 算法簡潔，路由開銷小。電力線通信網絡系統(tǒng)中節(jié)點的處理能力和計算能力較弱，所以設計的算法不宜復雜，應追求路由和通信開銷小的目標。

④ 考慮節(jié)點負載平衡問題。由于某些通信節(jié)點性能較好，可能會承載過多的傳輸任務，如果節(jié)點之間的通信負載差異太大，反而會降低整個網絡的通信效率和可靠性。因此，在設計算法時要考慮節(jié)點的負載平衡問題。

2 改進的組網算法

2.1 組網前提

① 網絡中的每個節(jié)點在物理鏈路上是連通的，且都具有唯一的物理地址(ID)。假設算法中網絡節(jié)點總數為n，則中心節(jié)點物理ID為1，其余節(jié)點物理ID依次為2，3，…，n。

② 不考慮網絡中的孤島效應，網絡經過分簇后可以實現(xiàn)對所有節(jié)點的遍歷，即不存在孤立節(jié)點。

③ 為了仿真的便利性，在實驗中認為網絡通信鏈路是對稱的。

④ 網絡初始化時，每個通信節(jié)點可以經交互控制消息得到鄰居節(jié)點的物理ID和權值等信息[21]。

2.2 算法概述

目前，應用在電力線通信組網中的分簇算法大多是以節(jié)點的某一度量作為選擇簇頭的規(guī)則，如最高節(jié)點度分簇算法選擇簇頭時只考慮通信節(jié)點的連通度，連通度大的節(jié)點能夠優(yōu)先被選為簇頭；最小ID分簇算法在選舉簇頭時只考慮通信節(jié)點的邏輯ID值等。這種只考慮某一方面的選擇標準會使某些節(jié)點頻繁地被選為簇頭，無法保證節(jié)點的公平性，一旦這些節(jié)點出現(xiàn)問題，會影響整個網絡的性能。

針對上述問題，在對傳統(tǒng)非交疊分簇算法進行研究和分析的基礎上，提出了一種基于多因素加權的電力線通信組網算法，選擇簇頭節(jié)點時綜合考慮3方面因素：節(jié)點連通度、節(jié)點的負載情況以及有效通信距離和，為這3種因素分配相應的權重并給出相應公式計算節(jié)點權值，權值越大，說明該節(jié)點越適合當簇頭。組網時優(yōu)先選擇權值最大的通信節(jié)點成為簇頭，若權值最大的節(jié)點不止一個，則選擇其中邏輯ID值最小的節(jié)點，同時為了提高網絡的可靠性。該算法借鑒人工蛛網的思想，在組網階段，為通信節(jié)點尋找2個(至多)同層鄰居節(jié)點作為備份路徑，一旦原本的通信鏈路失效，則可以選擇備份路徑進行網絡維護，作為中繼實現(xiàn)與目的節(jié)點的通信。這樣可以減少頻繁的網絡重構，以免造成網絡資源的浪費。組網算法的主要實現(xiàn)過程如圖6所示，主要包括組網初始化和網絡維護2個階段。

圖6 組網算法的主要實現(xiàn)過程Fig.6 Main implementation process of networking algorithm

2.3 組網初始化算法

2.3.1 算法描述

在實際的低壓電力線通信網絡中，為了最大程度發(fā)揮分簇算法的優(yōu)勢，提升整個網絡的性能，需要在選擇簇頭時考慮多種因素，使產生的簇頭更符合實際組網情況。本算法中定義每個節(jié)點充當簇頭的適合程度為一個組合權值，用weight表示該權值。weight值越大，說明該通信節(jié)點與周圍節(jié)點的聯(lián)系越緊密，節(jié)點的穩(wěn)定性和可靠性越強，越適合當簇頭。在給出權值的計算公式之前，介紹所用到的變量的定義：

定義1 節(jié)點連通度：用來衡量一個通信節(jié)點與其他節(jié)點建立通信連接的能力，定義為該通信節(jié)點在可直接通信范圍內能連接的下一層的節(jié)點個數，用f(ni)表示。f(ni)越大，說明該節(jié)點的連通性越好。

定義2 節(jié)點負載：將某個通信節(jié)點的節(jié)點連通度與同一邏輯層中的所有通信節(jié)點的平均節(jié)點連通度之差定義為節(jié)點負載，用N(ni)表示。若s表示同層節(jié)點個數，則：

(1)

定義3 節(jié)點有效通信距離和：節(jié)點有效通信距離和是通信節(jié)點到其一跳范圍內的可通信節(jié)點的通信距離之和，該值越大，在一定程度上表示節(jié)點的通信范圍越廣，用D(ni)表示。

綜合考慮以上3方面因素，改進算法中簇頭的選擇標準用這3個變量的一個加權組合值weight表示，具體計算公式如下：

weight(ni)=ω1×D(ni)+ω2×f(ni)×exp(-|N(ni)|)，

(2)

式中，w1，w2為加權系數因子，且滿足w1+w2=1。w1，w2取值不固定，可以根據具體的要求和應用環(huán)境設定不同的值，從而適應網絡的變化。

2.3.2 算法流程

組網初始化的過程即簇生成的過程，共分為以下4個步驟：

① 網絡初始化。上電后中心節(jié)點向周圍發(fā)送廣播信息，啟動組網過程，其余節(jié)點分別計算自己的weight值，中心節(jié)點依據可通信范圍建立節(jié)點之間的鄰居關系。

② 第1層組網。中心節(jié)點默認為是第1個簇頭，發(fā)出分簇廣播信息，假設有m(0

③ 第2層組網。layer1的m個通信節(jié)點按照weight值由高到低的次序依次獲得組網權限，若出現(xiàn)節(jié)點weight值相同的情況，則優(yōu)先選擇其中邏輯ID值最小的節(jié)點。權值最高的節(jié)點首先向未入網的節(jié)點發(fā)送廣播信息，接收節(jié)點發(fā)送應答信號入網，加入該簇。然后借鑒蛛網思想，向同層通信節(jié)點發(fā)送廣播信息，選擇至多2個通信質量最好的節(jié)點作為其鄰居節(jié)點，充當備份鏈路。

④ 更高層的組網。重復步驟③，直到低壓電力線網絡中的節(jié)點全部成功接入網絡，即都建立了相應的通信鏈路，則組網過程結束。初始化算法的流程如圖7所示。

圖7 組網初始化算法流程Fig.7 Flow chart of networking initialization algorithm

2.4 網絡維護

低壓電力線通信網絡在運行過程中，傳輸質量易受到信道時變性的影響，因此會出現(xiàn)通信鏈路失效的問題。在傳統(tǒng)非交疊算法中，中心節(jié)點到每個目的通信節(jié)點只有單一的通信路徑，很大程度上不能保障網絡的可靠性。如果頻繁地進行組網，會降低網絡運行效率。因此，有必要為節(jié)點引入備份路徑。

本文算法中蛛網思想的引入為節(jié)點增加了備份鏈路，在組網過程中為通信節(jié)點尋找至多2個同層鄰居節(jié)點，一旦原本的通信鏈路出現(xiàn)了故障，則選擇鄰居節(jié)點作為中繼，實現(xiàn)與目的節(jié)點的數據收發(fā)。如果節(jié)點沒有找到同層鄰居節(jié)點，或者網絡情況差到備用鏈路也無法通信，此時將重新啟動組網算法，進行網絡重構。

3 實驗仿真與分析

3.1 組網初始化仿真

為了充分證明所提組網算法的有效性和優(yōu)越性，本文在Matlab R2018b的環(huán)境下進行了仿真研究。設定在一個100 m×100 m的方形區(qū)域內，分布著多個通信節(jié)點，其中中心節(jié)點的坐標是(50，50)，位于區(qū)域的正中心，編號為1，其余通信節(jié)點隨機分布，編號依次為2～40。為了體現(xiàn)出電力線通信信道的時變性，實驗中設定各個節(jié)點的有效通信距離在20～25 m隨機變化，實驗中加權系數因子設定為w1=w2=0.5。

依次對傳統(tǒng)分簇算法(本實驗采用最小ID分簇算法)、未引入蛛網思想的改進分簇算法以及引入蛛網思想的改進分簇算法進行仿真，圖8～圖10給出了實驗結果。

圖8 傳統(tǒng)最小ID分簇算法仿真結果Fig.8 Simulation results of traditional minimum ID clustering algorithm

圖9 未引入蛛網思想的改進分簇算法仿真結果Fig.9 Simulation results of improved clustering algorithm without cobweb idea

圖10 引入蛛網思想的改進分簇算法仿真結果Fig.10 Simulation results of improved clustering algorithm with cobweb idea

由圖8可以看出，傳統(tǒng)的最小ID分簇算法選舉簇頭時僅根據單一因素，選擇出的簇頭較為分散和不均勻。與圖8相比，圖9中本文提出的考慮多因素加權的簇頭選舉方法，使得分簇效果更加均勻，整個網絡中各個簇的簇成員個數基本相等，簇的結構更加穩(wěn)定。

為了更直觀地比較圖8和圖9的分簇效果，定義η為網絡的負載平衡因子，用來衡量整個網絡的負載均衡性。η的計算公式如下：

(3)

(4)

式中，nc為整個網絡簇的總數；xi為每個簇的簇員個數；μ為網絡的平均簇員數；η為每個簇簇員個數與平均簇員數方差之和的倒數。η越大，說明網絡的結構越均勻，負載均衡性越好。經計算，傳統(tǒng)最小ID算法的負載平衡因子η1=0.021 5，改進后算法的負載平衡因子η2=0.025。由此可見，本文提出的算法在負載平衡方面具有優(yōu)越性。

圖10為引入蛛網思想的改進分簇算法組網結果圖，在圖9的基礎上，增加了同層鄰居節(jié)點作為備份鏈路(圖中虛線)。以中心節(jié)點1與節(jié)點40進行通信為例，對3種仿真結果進行分析。由于距離較遠，中心節(jié)點無法直接與節(jié)點40通信，因此需要尋找合適的中繼節(jié)點。在傳統(tǒng)分簇算法和未引入蛛網思想的改進分簇算法中均只有一條路徑：1-25-30-40，而在引入蛛網思想的改進分簇算法中，可以明顯看到，除通信鏈路1-25-30-40外，還有多條備份路徑能夠完成中心節(jié)點與節(jié)點40的通信。

由上述分析可知，傳統(tǒng)分簇算法和未引入蛛網思想的改進分簇算法路徑單一，網絡連通性和抗干擾性能差；而本文提出的引入蛛網思想的改進分簇算法，一方面能夠更加合理地選擇簇頭，保障節(jié)點公平和負載均衡性，另一方面增加了鄰居節(jié)點作為備份路徑，為節(jié)點之間的通信提供了更多選擇，當通信鏈路出現(xiàn)故障時，備份路徑的存在能夠及時保障通信可靠性。

3.2 網絡維護仿真

在網絡維護的仿真研究中，本實驗研究了通信鏈路失效時的情況。假設節(jié)點32與37之間的通信鏈路失效，那么節(jié)點32將無法與節(jié)點37直接通信，此時啟動網絡維護策略。對于節(jié)點37，存在2個同層鄰居節(jié)點：節(jié)點29和節(jié)點38，這2個鄰居節(jié)點都可以作為節(jié)點37的備份路徑。此時節(jié)點32將自動選擇節(jié)點29或節(jié)點38作為中繼進而與節(jié)點37進行通信，于是維護后的通信鏈路變成1-28-32-29-37或1-28-32-38-37。具體仿真結果如圖11所示。

(a) 1-28-32-29-37

3.3 簇頭數目的變化

網絡中的簇頭數目在一定程度上能夠用來衡量分簇算法的性能，簇頭數目過多會帶來一系列問題，如網絡延時、開銷過大等，因此有必要對簇頭數目的變化情況進行分析。

由于算法中是否引入蛛網思想并不改變簇頭的個數，所以下文將未引入蛛網思想的改進分簇算法和引入蛛網思想的改進分簇算法統(tǒng)稱為改進分簇算法。圖12給出了傳統(tǒng)分簇算法和改進分簇算法的簇頭數目隨節(jié)點有效通信距離的變化曲線。結果表明，2種算法的簇頭個數都會隨著節(jié)點有效通信距離的增加而減少，相比之下,改進后的分簇算法簇頭個數更少，性能更優(yōu)。

圖12 簇頭數目隨節(jié)點有效通信距離的變化Fig.12 Number of cluster heads varing with the effective communication distance of nodes

4 結束語

本文首先分析了低壓電力線通信網絡結構，介紹了傳統(tǒng)分簇算法的分類、特點以及電力線通信組網的特點和要求，針對目前組網算法存在的問題，提出了一種基于多因素加權的改進組網算法。不同于以往的算法在選擇簇頭節(jié)點時只考慮單一因素，改進的算法在選取簇頭時考慮了節(jié)點連通度、節(jié)點的負載情況以及有效通信距離和3種因素。另一方面，為提高通信可靠性，該算法借鑒蛛網的思想，為通信節(jié)點引入鄰居節(jié)點作為備份路徑，避免頻繁的網絡重構。最后，通過仿真驗證了該算法的可行性和優(yōu)越性。仿真結果表明，該算法的提出使簇頭的選擇更加合理，有利于保障節(jié)點公平性和負載平衡，改進后的算法減少了簇頭個數，并且能夠在通信鏈路出現(xiàn)故障時利用備份路徑實現(xiàn)網絡維護，有效地提高了低壓電力線通信的可靠性。未來的研究方向將考慮分析算法的QoS參數，使得算法更具有實際工程上的指導意義。