石文玉

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

?

基于多級分簇的拓?fù)渲貥?gòu)算法的研究

石文玉

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

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

無線傳感器網(wǎng)絡(luò)；分簇；拓?fù)渲貥?gòu)

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

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

1 問題描述

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

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

2 圖論基礎(chǔ)知識描述

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

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

圖2 三級分簇式拓?fù)?/p>

如圖1所示，最小剛性圖中每個頂點至少有兩條相鄰邊[4]，因此最小剛性圖用于網(wǎng)絡(luò)拓?fù)渲芯哂休^小的通行復(fù)雜度和較強(qiáng)的魯棒性。通過最小剛性圖建立網(wǎng)絡(luò)拓?fù)淇梢杂行У鼐庳?fù)載，形成有效的最優(yōu)路徑，從而減少鏈路能量消耗，延長網(wǎng)絡(luò)的生存時間。

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

(1)

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

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

3 TCUVG-MH算法

本文在TCUVG設(shè)計的網(wǎng)絡(luò)應(yīng)用場景的基礎(chǔ)上，提出了一種三級分簇式的拓?fù)渲貥?gòu)算法，該算法中拓?fù)浣Y(jié)構(gòu)包含簇頭節(jié)點(CH)、二級簇頭節(jié)點(SCH)、普通成員節(jié)點(Node)，如圖2所示。

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

在復(fù)雜電磁環(huán)境中，在滿足拓?fù)淇焖僦亟ǖ幕A(chǔ)上節(jié)約能耗，算法的核心內(nèi)容如下：

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

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

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

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

(2)

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

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

(3)

(4)

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

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

(5)

(6)

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

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

根據(jù)最小剛性圖的方法，簇頭節(jié)點CH之間進(jìn)行拓?fù)鋬?yōu)化，該拓?fù)浔ＷC簇頭節(jié)點都是2-連通的。根據(jù)引理2，當(dāng)簇頭節(jié)點需要更換時不需要重新生成拓?fù)?，只需在簇?nèi)找到一個新的簇頭節(jié)點代替原簇頭節(jié)點，這樣可以保證新的拓?fù)淠苁亲钚傂詧D。

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

4 仿真實驗及分析

本文使用Matlab軟件根據(jù)文獻(xiàn)[3]中的參數(shù)對TCUVG-MH算法進(jìn)行大規(guī)模網(wǎng)絡(luò)的仿真實驗，在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)絡(luò)中備用簇頭的選舉概率隨著網(wǎng)絡(luò)規(guī)模的增大而增大，且由于在網(wǎng)格中添加了多級的簇頭節(jié)點，使得TCUVG-MH算法比原算法的選舉概率要大。

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

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

圖3 網(wǎng)絡(luò)死亡時網(wǎng)絡(luò)拓?fù)渲貥?gòu)時間

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

5 結(jié)語

本文中算法設(shè)計目標(biāo)為快速拓?fù)渲貥?gòu)，針對TCUVG算法的不足提出了一種基于最小剛性圖的多級分簇的拓?fù)渲貥?gòu)算法，分級中選舉的子簇簇頭節(jié)點可以增大備用簇頭節(jié)點的選舉概率，縮短拓?fù)渲貥?gòu)的時間。同時為了避免在非均勻虛擬網(wǎng)格劃分時，矩形區(qū)域大的簇中簇頭節(jié)點因能耗過大而過早死亡從而導(dǎo)致整個網(wǎng)絡(luò)的生存時間短，子簇簇頭分擔(dān)簇頭節(jié)點的負(fù)載延長了網(wǎng)絡(luò)的生存時間。仿真結(jié)果表明，TCUVG-MH算法適用于大規(guī)模網(wǎng)絡(luò)且具有較好的優(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)絡(luò)拓?fù)渲貥?gòu)算法[J].赤峰學(xué)院學(xué)報:自然科學(xué)版,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

安徽新華學(xué)院校級科研項目“復(fù)雜電磁環(huán)境中無線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯俊?2014zr023)；安徽省自然科學(xué)研究項目“面向隱私保護(hù)的傳感器網(wǎng)絡(luò)查詢技術(shù)研究”(KJ2016A303)。

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

TP212；TN929

A

2095-7602(2016)08-0030-04