基于多級分簇的拓撲重構(gòu)算法的研究

石文玉

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

?

基于多級分簇的拓撲重構(gòu)算法的研究

石文玉

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

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

無線傳感器網(wǎng)絡；分簇；拓撲重構(gòu)

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

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

1 問題描述

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

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

2 圖論基礎知識描述

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

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

圖2 三級分簇式拓撲

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

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

(1)

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

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

3 TCUVG-MH算法

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

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

在復雜電磁環(huán)境中，在滿足拓撲快速重建的基礎上節(jié)約能耗，算法的核心內(nèi)容如下：

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

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

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

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

(2)

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

首先，根據(jù)主參數(shù)判斷節(jié)點是否在其所在簇的上下跳簇頭節(jié)點的通信范圍內(nèi)。

(3)

(4)

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

當α=0時，根據(jù)上述思想判斷節(jié)點是否在子簇簇頭節(jié)點的通信范圍內(nèi)。

(5)

(6)

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

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

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

在數(shù)據(jù)傳輸階段，簇頭節(jié)點在固定的時隙向基站發(fā)送數(shù)據(jù)包，若基站在某一時隙未收到其所在網(wǎng)格的數(shù)據(jù)包，則立刻通知備用簇頭節(jié)點擔任簇頭。

4 仿真實驗及分析

本文使用Matlab軟件根據(jù)文獻[3]中的參數(shù)對TCUVG-MH算法進行大規(guī)模網(wǎng)絡的仿真實驗，在1000×1000 m2的范圍內(nèi)隨即撒布n個節(jié)點(n=1500,2000,2500,3000)，節(jié)點傳輸最大半徑為200m，傳輸?shù)某跏寄芰繛?.5J，Eelec為50nJ，εfs為10pj/(bit·m2)，εmp為0.0013pj/(bit·m4)。

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

表1 網(wǎng)格中備用簇頭選舉概率

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

圖3 網(wǎng)絡死亡時網(wǎng)絡拓撲重構(gòu)時間

圖4 網(wǎng)絡生存時間

5 結(jié)語

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

[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]石文玉,鹿建銀.基于非均勻虛擬網(wǎng)格的無線傳感器網(wǎng)絡拓撲重構(gòu)算法[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

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

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

TP212；TN929

A

2095-7602(2016)08-0030-04