低壓電力通信系統(tǒng)中的人工蛛網(wǎng)及可靠性和性能計(jì)算與分析

張培培，邵方明，張震霄

（華東理工大學(xué) 數(shù)學(xué)系，上海 200237）

0 引 言

網(wǎng)絡(luò)是關(guān)聯(lián)系統(tǒng)的一種特殊情形，網(wǎng)絡(luò)可靠性是度量網(wǎng)絡(luò)性能好壞的指標(biāo)。在以前的研究中，研究者通常用概率圖建立具有不可靠點(diǎn)或邊的網(wǎng)絡(luò)模型。因此，網(wǎng)絡(luò)可靠性指在給定的每條邊或每個(gè)點(diǎn)的可靠性條件下，所有的終端節(jié)點(diǎn)可以相互連通的概率[1]，通常記為R(G)。本文的可靠性模型建立在邊不可靠，點(diǎn)可靠的條件下。

智能電網(wǎng)是以物理電網(wǎng)為基礎(chǔ)，將現(xiàn)代先進(jìn)的傳感測(cè)量技術(shù)、通信技術(shù)、信息技術(shù)、計(jì)算機(jī)技術(shù)和控制技術(shù)與物理電網(wǎng)高度集成而形成的新型電網(wǎng)。它以充分滿足用戶對(duì)電力的需求和優(yōu)化資源配置、確保電力供應(yīng)的安全性、可靠性和經(jīng)濟(jì)性、滿足環(huán)保約束、保證電能質(zhì)量、適應(yīng)電力市場(chǎng)化發(fā)展等為目的，實(shí)現(xiàn)對(duì)用戶可靠、經(jīng)濟(jì)、清潔、互動(dòng)的電力供應(yīng)和增值服務(wù)。隨著智能電網(wǎng)在全球范圍內(nèi)的快速發(fā)展，中國(guó)國(guó)家電網(wǎng)公司決定以智能電網(wǎng)技術(shù)為基礎(chǔ)，在全國(guó)范圍內(nèi)建設(shè)新型電網(wǎng)。低壓電力線通信技術(shù)（LVPLC）作為終端用戶與電力公司交換信息的直接手段，是智能電網(wǎng)的通信網(wǎng)絡(luò)建設(shè)中可供選擇的極具競(jìng)爭(zhēng)力的技術(shù)手段。

由于低壓配電網(wǎng)物理拓?fù)涞奈粗?、?fù)雜性與易變性，物理介質(zhì)的共享性和多樣性以及信道的強(qiáng)噪聲干擾等特點(diǎn)，使得電力線通信可靠性較低，直接影響了其在智能電網(wǎng)建設(shè)中的大規(guī)模應(yīng)用。近年來(lái)的研究主要有，提高PLC網(wǎng)絡(luò)內(nèi)點(diǎn)對(duì)點(diǎn)的通信成功率，包括：信道建模與快速估計(jì)[2]，傳輸特性與信號(hào)衰減特性研究[3]，跳頻調(diào)制/解調(diào)技術(shù)研究等[4]；通過(guò)組網(wǎng)，建立網(wǎng)絡(luò)中繼，提高電力線通信網(wǎng)絡(luò)的可靠性[5]。文獻(xiàn)[6]針對(duì)電力線載波通信網(wǎng)絡(luò)可靠性低的問(wèn)題，研究了人工蛛網(wǎng)路由在低壓電力線通信領(lǐng)域應(yīng)用的可靠性。采用基于馬爾科夫概率論模型改進(jìn)的因子分解方法，對(duì)應(yīng)用于低壓電力線通信的人工蛛網(wǎng)結(jié)構(gòu)的全端可靠性和抗毀度進(jìn)行分析與計(jì)算，與傳統(tǒng)的樹(shù)形、星形、環(huán)狀網(wǎng)絡(luò)進(jìn)行對(duì)比，證明了單層人工蛛網(wǎng)的高全終端可靠性。

然而，在實(shí)際中，往往不僅需要點(diǎn)對(duì)之間有連通的路，也需要這條路的長(zhǎng)度有所限制[7]。例如，網(wǎng)絡(luò)中每個(gè)點(diǎn)在傳輸數(shù)據(jù)時(shí)需要傳輸時(shí)間t，若總傳輸時(shí)間限制在T內(nèi)，那么參與傳輸?shù)狞c(diǎn)數(shù)不能超過(guò)T t，這就意味著傳輸?shù)穆窂介L(zhǎng)度受到限制。在無(wú)線傳感器網(wǎng)絡(luò)中，傳輸數(shù)據(jù)時(shí)則有跳數(shù)限制。因此，在研究人工蛛網(wǎng)可靠性問(wèn)題時(shí)加入直徑限制是十分必要的。文獻(xiàn)[8]中介紹了直徑限制，指的是網(wǎng)絡(luò)中所有路的長(zhǎng)度均不能超過(guò)一個(gè)給定的正整數(shù)D。直徑限制下的網(wǎng)絡(luò)可靠性（DCNR）指所有的終端節(jié)點(diǎn)可以通過(guò)一條長(zhǎng)度不大于D的路徑相互連通的概率[9]，記為R(G,D)。

事實(shí)上，對(duì)有些網(wǎng)絡(luò)僅僅需要了解部分端點(diǎn)間通信能力的大小，但不必知道具體是哪些點(diǎn)。例如，移動(dòng)通信需要實(shí)現(xiàn)至少90%用戶的接入能力，卻不需要知道這些用戶是誰(shuí)；又如野戰(zhàn)通信網(wǎng)的故障判斷為網(wǎng)絡(luò)內(nèi)15%的端點(diǎn)傳輸中斷[10]，該判據(jù)也僅需要知道傳輸中斷節(jié)點(diǎn)的數(shù)量。文獻(xiàn)[11]在此基礎(chǔ)上提出了連通比的概念及基于連通比的有源網(wǎng)絡(luò)可靠性模型，并進(jìn)一步研究了它的上界問(wèn)題。連通比是能夠相互通信的端點(diǎn)數(shù)k與總端點(diǎn)數(shù)n的比值。它體現(xiàn)了網(wǎng)絡(luò)對(duì)保障有效服務(wù)的用戶接入比例的最低要求。本文在以上的基礎(chǔ)上考慮直徑限制下保證一定連通比的低壓電力線通信人工蛛網(wǎng)可靠性問(wèn)題。不同于傳統(tǒng)的可靠性模型，本文中的網(wǎng)絡(luò)要實(shí)現(xiàn)直徑限定下至少一定比例的節(jié)點(diǎn)能夠相互通信而不是指定的K個(gè)節(jié)點(diǎn)。

網(wǎng)絡(luò)可靠性算法包括精確算法和近似算法。文獻(xiàn)[12]介紹了利用生成樹(shù)計(jì)算網(wǎng)絡(luò)可靠性的精確算法。R(G)可以通過(guò)評(píng)估表示生成樹(shù)的操作狀態(tài)事件的并集的概率來(lái)獲得。將這些相互獨(dú)立的事件分別記為E1,E2,…,En，那么至少一個(gè)時(shí)間發(fā)生的概率用文獻(xiàn)[13]中的不交和定理計(jì)算即為：

綜上，本文主要研究低壓電力下單層人工蛛網(wǎng)在直徑限制及連通比限制下的可靠性分析與計(jì)算問(wèn)題。通過(guò)找到實(shí)現(xiàn)直徑限制下至少一定比例的節(jié)點(diǎn)能夠相互通信的子圖及生成樹(shù)來(lái)計(jì)算其可靠性。仿真結(jié)果表明人工蛛網(wǎng)拓?fù)浣Y(jié)構(gòu)在連通比及直徑限制下具有較高的通信可靠性。

1 可靠性數(shù)學(xué)模型與人工蛛網(wǎng)

用無(wú)向圖G(V,E)表示人工蛛網(wǎng)網(wǎng)絡(luò)拓?fù)?，其中V={v1,v2,…,vn}是網(wǎng)絡(luò)中的節(jié)點(diǎn)集，E={e1,e2,…,em}是邊集，n為點(diǎn)的個(gè)數(shù)，m為邊的個(gè)數(shù)。假設(shè)點(diǎn)是始終運(yùn)行的，邊有失效和運(yùn)行兩種狀態(tài)，各邊連通的概率相互獨(dú)立，邊e運(yùn)行的概率為p，失效的概率為q=1-p。

為行文方便，引用文獻(xiàn)[11]中的定義：

定義1：設(shè)k為在網(wǎng)絡(luò)節(jié)點(diǎn)集V中能夠相互通信的端點(diǎn)數(shù)，把k與n的比值κ=k n稱為連通比，κ∈[0,1]。

顯然，在網(wǎng)絡(luò)G中，要保證連通比κ，則能夠成功通信的端點(diǎn)數(shù)至少為（表示對(duì)*上取整）。

定義2：在網(wǎng)絡(luò)G(V,E)中，在D限制下且在端點(diǎn)集V中至少k個(gè)端點(diǎn)間能夠相互通信的概率稱為直徑限制下保證連通比的網(wǎng)絡(luò)可靠性，記為Rk(G,D)。

由定義2可知，只要G的任何一個(gè)端點(diǎn)數(shù)大于或等于k的子圖連通就能保證G的連通比不低于給定的κ。那么，只要計(jì)算G的端點(diǎn)數(shù)大于或等于k的所有子圖在D限制下的可靠性，即可得Rk(G,D)。易知，這些子圖的個(gè)數(shù)為：

2 可靠性Rk(G,D)的計(jì)算

為了更清楚地說(shuō)明直徑限制下保證連通比的網(wǎng)絡(luò)可靠性的定義，在例1中選定節(jié)點(diǎn)數(shù)為4的單層人工蛛網(wǎng)解釋說(shuō)明上述Rk(G,D)的計(jì)算。

例1：如圖1所示，給定直徑限制D=2，連通比κ=0.6，每條邊通信的概率均為p=0.9，不通信的概率為q=0.1。

由于給定的連通比κ=0.6，因此只要保證至少個(gè)點(diǎn)連通。問(wèn)題轉(zhuǎn)化為求個(gè)子圖在直徑限制下的全終端可靠性問(wèn)題。本文將采用先找出子圖的所有生成樹(shù)，再根據(jù)D=2，找出所有冗余樹(shù)，最后用式（1）計(jì)算R0.6(G,2)。

圖1是單層蛛網(wǎng)包含3個(gè)點(diǎn)和4個(gè)點(diǎn)的子圖及它們的所有生成樹(shù)。由于生成樹(shù)T17～T28的直徑均為3大于D，因此T17～T28是冗余樹(shù)，在計(jì)算時(shí)可以刪去。結(jié)合式（1），有：

圖1 點(diǎn)數(shù)為4的單層人工蛛網(wǎng)Fig.1 Single-layer artificial cobweb network with 4 nodes

3 單層蛛網(wǎng)高可靠性的仿真例子

低壓配電網(wǎng)是一種樹(shù)形網(wǎng)絡(luò)，因此分析這種網(wǎng)絡(luò)的直徑限制下基于連通比的可靠性具有實(shí)際的意義。本文采用能代表各自網(wǎng)絡(luò)特性的樹(shù)形網(wǎng)絡(luò)、星形網(wǎng)絡(luò)、單層環(huán)網(wǎng)及單層蛛網(wǎng)進(jìn)行分析與比較。為保證直徑限制下基于連通比的可靠性的公平性，選定節(jié)點(diǎn)數(shù)均為6的上述網(wǎng)絡(luò)，直徑限定D=3，連通比κ=0.8，每條邊通信的概率均為p。

由于給定的連通比κ=0.8，因此只要保證至少k=個(gè)點(diǎn)連通。問(wèn)題轉(zhuǎn)化為求個(gè)子圖在直徑限制下的全終端可靠性問(wèn)題。先找出子圖的所有生成樹(shù)，再根據(jù)D=3，找出所有冗余樹(shù)，最后用式（1）計(jì)算R0.8(G,3)。

圖2a）是樹(shù)形網(wǎng)絡(luò)包含5個(gè)點(diǎn)和6個(gè)點(diǎn)的子圖。其中Ga2，Ga3，Ga4是不連通子圖，所以沒(méi)有生成樹(shù)。又因?yàn)镈=3，因 此Ta2～Ta4是 冗 余 樹(shù) ，在 計(jì) 算 時(shí) 可 以 刪去R0.8(Ga,3)=Pr(E1)=p4。

圖2b）是星形網(wǎng)絡(luò)包含5個(gè)點(diǎn)和6個(gè)點(diǎn)的子圖，其中Gb2是不連通子圖。由星形圖的對(duì)稱性知，子圖Gb1有5個(gè)。因此，Ga保證至少5個(gè)點(diǎn)連通的生成樹(shù)有Tb2和5個(gè)Tb1。D=3，Tb2和Tb1不是冗余樹(shù)。所以，R0.8(Gb,3)=Pr(E1∪E2)=p4+4p4q。

圖2 樹(shù)形、星形、單層環(huán)網(wǎng)及單層蛛網(wǎng)拓?fù)鋱DFig.2 Topology diagrams of the tree，star，single-layer ring and single-layer cobweb networks

圖2c）是單層環(huán)網(wǎng)包含5個(gè)點(diǎn)和6個(gè)點(diǎn)的子圖。由環(huán)網(wǎng)的對(duì)稱性知，Gb保證至少5個(gè)點(diǎn)連通的子圖Gc1有5個(gè)，生成樹(shù)Tc2有6個(gè)。在直徑限制下，其所有生成樹(shù)均為冗余樹(shù)，因此，R0.8(Gc,3)=0。

圖2d）是單層蛛網(wǎng)包含5個(gè)點(diǎn)和6個(gè)點(diǎn)的子圖。由蛛網(wǎng)的對(duì)稱性，生成樹(shù)Td1～Td10的個(gè)數(shù)分別為5個(gè)、1個(gè)、20個(gè)、4個(gè)、12個(gè)、1個(gè)、10個(gè)、10個(gè)、15個(gè)、5個(gè)。考慮直徑限制，有：

同理，當(dāng)D=2，κ=0.8時(shí)，R0.8(Ga,2)=0，R0.8(Gb,2)=p4+4p4q，R0.8(Gc,2)=0，R0.8(Gd,2)=p4+4p4q；當(dāng)D=4，κ=0.8時(shí)，R0.8(Ga,4)=p4+2p4q，R0.8(Gb,4)=p4+4p4q，R0.8(Gc,4)=p4+4p4q+3p4q2，R0.8(Gd,4)=p4+4p4q+10p4q2+0p4q3+34p4q4+12p4q5。

圖3a）～圖3c）分別是樹(shù)形網(wǎng)絡(luò)、星形網(wǎng)絡(luò)、單層環(huán)網(wǎng)與單層蛛網(wǎng)在κ=0.8時(shí)，D=2，D=3和D=4限制下的可靠性計(jì)算結(jié)果對(duì)比圖。從圖3a）可以看出，在相同的連通比限制下，當(dāng)直徑限制為2時(shí)，單層蛛網(wǎng)在連通比及直徑限制下的可靠性與星形網(wǎng)絡(luò)相同，遠(yuǎn)高于樹(shù)形網(wǎng)絡(luò)及單層環(huán)網(wǎng)；而當(dāng)直徑限制為3或4時(shí)，單層蛛網(wǎng)在連通比及直徑限制下的可靠性均遠(yuǎn)高于其他網(wǎng)絡(luò)。當(dāng)κ=0.8，D=1時(shí)，由于Ga，Gb，Gc，Gd在連通比限制下的子圖生成樹(shù)的直徑均大于1，所以R0.8(Ga,1)=R0.8(Gb,1)=R0.8(Gc,1)=R0.8(Gd,1)=0；當(dāng)κ=0.8，D≥ 5時(shí)，由于Ga，Gb，Gd在連通比限制下的子圖生成樹(shù)的直徑均小于等于4，所以R0.8(Ga,D)=R0.8(Ga,4)，R0.8(Gb,D)=R0.8(Gb,4)，R0.8(Gd,D)=R0.8(Gd,4)，而 經(jīng) 計(jì) 算 得R0.8(Gc,D)=R0.8(Gc,4)，與圖3b）情況相同。因此，在相同的連通比限制下，人工蛛網(wǎng)拓?fù)浣Y(jié)構(gòu)在連通比及直徑限制下具有較高的通信可靠性。

為了驗(yàn)證在相同直徑限制下，人工蛛網(wǎng)拓?fù)浣Y(jié)構(gòu)在連通比及直徑限制下也具有較高的通信可靠性，在給定D=3，分析k取不同數(shù)值時(shí)Ga，Gb，Gc，Gd的可靠性。計(jì)算結(jié)果見(jiàn)表1。

顯然，在取相同的p(p≠0)值時(shí)，單層人工蛛網(wǎng)的Rκ(Gd,3)恒大于其他三個(gè)網(wǎng)絡(luò)。綜上，在低壓電力通信系統(tǒng)中，與傳統(tǒng)的樹(shù)形網(wǎng)絡(luò)、星形網(wǎng)絡(luò)及單層環(huán)網(wǎng)相比，無(wú)論D，κ值如何變化，單層人工蛛網(wǎng)拓?fù)浣Y(jié)構(gòu)在連通比及直徑限制下都具有較高的通信可靠性。

圖3 κ=0.8限制下的可靠性Fig.3 Reliability asκ=0.8

表1 D=3，k取不同數(shù)值限制下的可靠性對(duì)比Table 1 Comparison of reliability atD=3and different values ofk

4 結(jié) 論

本文考慮直徑限制下保證一定連通比的低壓電力下人工蛛網(wǎng)可靠性問(wèn)題。對(duì)樹(shù)形網(wǎng)絡(luò)、星形網(wǎng)絡(luò)、單層環(huán)網(wǎng)及單層蛛網(wǎng)在連通比及直徑限制下的可靠性進(jìn)行分析與比較，得出人工蛛網(wǎng)拓?fù)浣Y(jié)構(gòu)在連通比及直徑限制下具有較高的通信可靠性。仿真實(shí)例說(shuō)明人工蛛網(wǎng)的通信可靠性比較好。

注：本文通訊作者為邵方明。