基于多級分簇的拓撲重構算法的研究

石文玉

(安徽新華學院信息工程學院，安徽合肥 230087)

?

基于多級分簇的拓撲重構算法的研究

石文玉

(安徽新華學院信息工程學院，安徽合肥 230087)

針對大規模分布式的無線傳感器網絡的特殊應用場景，由于復雜電磁環境等因素導致傳感器節點拓撲結構易受到破壞，本文在滿足網絡的連通性和魯棒性的基礎上，提出了一種多級分簇的拓撲結構，當拓撲結構遭到破壞后立刻恢復拓撲實現拓撲重構。仿真實驗表明，該算法相在保持原算法特性的基礎上可以有效延長網絡的生命周期。

無線傳感器網絡；分簇；拓撲重構

無線傳感器網絡WSNs(Wireless Sensor Networks)[1]目前已被廣泛應用于各個領域，而其相關技術問題也因應用場景的不同而被提出。無線傳感器網絡被應用于森林環境監測中，森林環境復雜多變，包括山體環境的差異、森林氣候的變化、復雜的電磁環境及各種自然災害都會對節點的無線通信信道造成干擾或者破壞。

網絡拓撲(Network Topology)是指網絡中各節點之間的特定的物理關系，即真實的或邏輯的排列方式[2]。對于無線傳感器網絡的節點構造的特點來說，節點一旦被撒布很難再回收，節點一般是依靠電池進行供電的，在早期拓撲設計時，算法讓每個節點與基站直接通信是非常耗電的、不現實的，因此構建一個良好的網絡拓撲結構對無線傳感器網絡節能來說非常重要。

1 問題描述

在復雜的電磁環境中，無線傳感器網絡拓撲極易受到破壞，其被破壞后如何快速恢復拓撲顯得尤為重要。石文玉[3]提出了一種基于非均勻虛擬網格劃分的拓撲重構算法(TCUVG算法)，根據傳感器節點所在地理位置區域電磁環境的復雜度不同劃分為若干個全覆蓋且不重疊的正方形區域。通過數據分析表明，在電磁環境越復雜的區域，節點的無線通信就越容易受到干擾，因此電磁環境復雜度越高的地方矩形區域面積越小，簇頭節點數量越多，相對“死亡”概率越小。在拓撲重構算法中根據快速性原則提出了備用節點的選舉公式，將主參數在其簇的上下跳簇頭節點所在通信范圍內的普通節點優先選為備用簇頭節點。該算法簡單，在計算備用簇頭節點時對網絡資源消耗較小。但該算法存在以下問題：(1)簇樹狀型初始拓撲搭建時使用非均勻虛擬網格劃分的方法來進行簇的劃分，矩形區域較大的簇頭節點的壓力過大；(2)在備用簇頭選舉時，為了滿足快速恢復拓撲，要求備用簇頭節點盡可能在上下跳節點的通信范圍之內，選舉概率較低。

本文在TCUVG算法的基礎上，針對上述問題提出了一種多級分簇拓撲重構算法TCUVG-MH。該算法在快速恢復拓撲的基礎上，在電磁環境復雜度較高的地方，采用多級分簇的方式來完成粗頭節點的分級，通過多個簇頭節點之間生成最小剛性圖。

2 圖論基礎知識描述

剛性圖，即在保證各邊長度不變的情況下，一個圖不會發生形變，否則稱為可變形圖。若剛性圖的任意一條邊被刪除都會導致圖形可變，則此圖稱為最小剛性圖，如圖1所示。

圖1 可變形圖、剛性圖、最小剛性圖圖示

圖2 三級分簇式拓撲

如圖1所示，最小剛性圖中每個頂點至少有兩條相鄰邊[4]，因此最小剛性圖用于網絡拓撲中具有較小的通行復雜度和較強的魯棒性。通過最小剛性圖建立網絡拓撲可以有效地均衡負載，形成有效的最優路徑，從而減少鏈路能量消耗，延長網絡的生存時間。

Tay and whitely[5]證明了下面兩個引理。

(1)

則子矩陣對應的邊和N個頂點構成了最小剛性圖。

引理2 若G′(v′,ε′)是剛性圖G(v,ε)的一個子圖，由其它剛性圖的子圖G″(v″,ε″)替代得到的圖仍是剛性的。

3 TCUVG-MH算法

本文在TCUVG設計的網絡應用場景的基礎上，提出了一種三級分簇式的拓撲重構算法，該算法中拓撲結構包含簇頭節點(CH)、二級簇頭節點(SCH)、普通成員節點(Node)，如圖2所示。

如2圖所示，根據三級分簇拓撲結構，在電磁環境復雜度較低的區域進行分級，其中普通節點收集其檢測區域的信息，子簇頭節點SCH匯聚其子簇所有節點信息并傳輸給簇頭節點CH，最后簇頭節點按照最小剛性圖原則生成鏈路進行通信。

在復雜電磁環境中，在滿足拓撲快速重建的基礎上節約能耗，算法的核心內容如下：

第一，根據節點所處環境的電磁環境的復雜度的不同將網絡用非均勻虛擬網格劃分為若干個矩形區域。這樣保證了電磁環境復雜的區域簇頭節點數量相對多，從而減少簇頭通信被破壞的幾率。

第二，對電磁環境復雜度最低的區域，即矩形區域劃分最大的區域按照三級分簇拓撲算法進行分級。(a)將簇內節點當前剩余能量進行排序；(b)選擇其中能量最高的節點作為CH，再選擇次能量較高的M個節點作為SCH。此方法可以在一個網格內通過子簇頭分擔簇頭節點的任務，有效避免了簇頭節點的大能耗問題，保證了網絡負載的均衡，達到延長網絡生存時間的目的。

第三，備用簇頭節點的選舉，在TCUVG-MH算法中設置三個參數：節點的通信范圍、剩余能量、子簇頭通信范圍。

判斷節點是否能稱為備用簇頭節點的判決式為

(2)

其中，ei,j為節點剩余能量，α的數值由(3)(4)判定。

首先，根據主參數判斷節點是否在其所在簇的上下跳簇頭節點的通信范圍內。

(3)

(4)

當(3)(4)同時成立時，α=1，否則α=0。

當α=0時，根據上述思想判斷節點是否在子簇簇頭節點的通信范圍內。

(5)

(6)

當(5)(6)同時成立時，有β=1，否則β=0。節點的drr最大時，該節點擔任備用簇頭節點。

在數據包中增加一個信息位SBCL(standby cluster head)，信息位的數值為0或1。SBCL=1時表明該節點的drr數值最大為備用簇頭節點，其它節點的SBCL=0。

根據最小剛性圖的方法，簇頭節點CH之間進行拓撲優化，該拓撲保證簇頭節點都是2-連通的。根據引理2，當簇頭節點需要更換時不需要重新生成拓撲，只需在簇內找到一個新的簇頭節點代替原簇頭節點，這樣可以保證新的拓撲能是最小剛性圖。

在數據傳輸階段，簇頭節點在固定的時隙向基站發送數據包，若基站在某一時隙未收到其所在網格的數據包，則立刻通知備用簇頭節點擔任簇頭。

4 仿真實驗及分析

本文使用Matlab軟件根據文獻[3]中的參數對TCUVG-MH算法進行大規模網絡的仿真實驗，在1000×1000 m2的范圍內隨即撒布n個節點(n=1500,2000,2500,3000)，節點傳輸最大半徑為200m，傳輸的初始能量為0.5J，Eelec為50nJ，εfs為10pj/(bit·m2)，εmp為0.0013pj/(bit·m4)。

通過表1可以看出，網絡中備用簇頭的選舉概率隨著網絡規模的增大而增大，且由于在網格中添加了多級的簇頭節點，使得TCUVG-MH算法比原算法的選舉概率要大。

表1 網格中備用簇頭選舉概率

本文提出的TCUVG-MH算法在TCUVG算法滿足快速拓撲重構的基礎上，提出了多級分簇的初始拓撲構建，子簇簇頭節點的出現使得網格中備用簇頭節點的選舉概率大大增加，基于最小剛性圖構建簇頭節點之間的通信鏈路，簇頭節點之間至少是2-連通，當網絡通信中斷時，上述兩個舉措大大降低了網絡的拓撲重構時間，如圖3所示。在多級分簇思想中，提出了子簇簇頭的選舉，其大大降低了簇頭節點的能量損耗，均衡了網絡負載，延長了網絡生存時間，如圖4所示。

圖3 網絡死亡時網絡拓撲重構時間

圖4 網絡生存時間

5 結語

本文中算法設計目標為快速拓撲重構，針對TCUVG算法的不足提出了一種基于最小剛性圖的多級分簇的拓撲重構算法，分級中選舉的子簇簇頭節點可以增大備用簇頭節點的選舉概率，縮短拓撲重構的時間。同時為了避免在非均勻虛擬網格劃分時，矩形區域大的簇中簇頭節點因能耗過大而過早死亡從而導致整個網絡的生存時間短，子簇簇頭分擔簇頭節點的負載延長了網絡的生存時間。仿真結果表明，TCUVG-MH算法適用于大規模網絡且具有較好的優化效果。

[1]Tubaishat M,Madria S.Sensor Networks:AnOverview[J].IEEE Potentials,2003,22(2):20-23.

[2]Wikipedia.Network topology[EB/OL].(2016-01-01)[2016-02-03]. http://en.wikipedia.org/wiki/Network_topology.

[3]石文玉,鹿建銀.基于非均勻虛擬網格的無線傳感器網絡拓撲重構算法[J].赤峰學院學報:自然科學版,2014，189(30):20-22.

[4]Luo X Y,Li S B,Guan X P.Automatic generation of min-weighted persistent formations[J].Chinese Physics B, 2009, 18(8):3104-3114.

[5]Tay T S,Whiteley W.Generating isostaticframeworks[J].Structure Topology,1985(11):21-69.

Research on Multi-layer Hierarchical Clustering Topology Construction Algorithm

SHI Wen-yu

(School of Information Engineering, Anhui Xinhua University, Hefei Anhui 230087, China)

A multi-layer hierarchical clustering topology for large-scale distributed wireless sensor networks is presented. This algorithm is proposed based on keeping good connectivity and robustness because that topology is easily damaged in complex environment. The results show that this algorithm can increase the lifetime of network based on keeping the original features.

wireless sensor networks; clustering; topology reconstruction

2016-05-07

安徽新華學院校級科研項目“復雜電磁環境中無線傳感器網絡拓撲控制研究”(2014zr023)；安徽省自然科學研究項目“面向隱私保護的傳感器網絡查詢技術研究”(KJ2016A303)。

石文玉(1987- )，女，講師，碩士，從事無線傳感器網絡研究。

TP212；TN929

A

2095-7602(2016)08-0030-04