131 1300 0010
引言
在無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǖ难芯恐校煤?jiǎn)化冗余路徑可以降低通信干擾，減少能量消耗，并且延長(zhǎng)網(wǎng)絡(luò)生存期。但是，以路徑簡(jiǎn)化為主要方法的拓?fù)淇刂票囟◣?lái)網(wǎng)絡(luò)的健壯性下降。因此，在無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯恐校枰紤]具有容錯(cuò)特性的拓?fù)淇刂茊?wèn)題。如何建立能夠在當(dāng)K-1個(gè)節(jié)點(diǎn)失效時(shí)，仍然具有連通性的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，是近年來(lái)研究的一個(gè)熱點(diǎn)問(wèn)題。
近年來(lái)，很多學(xué)者開(kāi)展了關(guān)于容錯(cuò)拓?fù)浣扑惴ǖ难芯俊Ｈ缇S持網(wǎng)絡(luò)K連通的全局近似算法FGSS和局部近似算法FLSS。但是由于這兩種算法不停地對(duì)比網(wǎng)絡(luò)路徑和判斷網(wǎng)絡(luò)是否達(dá)到K連通，開(kāi)銷較大。文獻(xiàn)以同構(gòu)網(wǎng)絡(luò)為對(duì)象，提出了CBTC（a）算法。該算法中當(dāng)a=2π／3K條件滿足時(shí)，可使原網(wǎng)絡(luò)的生成子圖保持K連通性。文獻(xiàn)對(duì)隨機(jī)分布無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的發(fā)射半徑與形成K連通圖的概率關(guān)系進(jìn)行了分析，并提出Yp，K結(jié)構(gòu)能夠使生成K連通子圖保持原拓?fù)涞腒連通性。文獻(xiàn)提出了集中式和分布式算法K-UPVCS，但是該算法產(chǎn)生的拓?fù)浣Y(jié)構(gòu)極易產(chǎn)生回路而造成網(wǎng)絡(luò)不能夠連通。
本文在異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)模型上，提出了一種基于多簇點(diǎn)簡(jiǎn)化的K容錯(cuò)能量均衡拓?fù)淇刂品桨浮Ｔ摲桨冈诒ＷC傳感器網(wǎng)絡(luò)K連通的前提下；可最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑，且可以較好地均衡無(wú)線傳感器的網(wǎng)絡(luò)能耗。
1、 異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)模型
定義異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)，V表示傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E表示節(jié)點(diǎn)之間的通信路徑集合。傳感器網(wǎng)絡(luò)中包括三類節(jié)點(diǎn)：監(jiān)測(cè)節(jié)點(diǎn)、接力節(jié)點(diǎn)和簇節(jié)點(diǎn)。設(shè)該傳感器網(wǎng)絡(luò)中，有N個(gè)用于信息監(jiān)測(cè)的傳感器節(jié)點(diǎn)Vs，該類節(jié)點(diǎn)用于采集監(jiān)測(cè)區(qū)域內(nèi)的信息，并將信息發(fā)送到鄰居節(jié)點(diǎn)，且承擔(dān)轉(zhuǎn)發(fā)其他節(jié)點(diǎn)數(shù)據(jù)的任務(wù)；為了使監(jiān)測(cè)區(qū)域內(nèi)保持網(wǎng)絡(luò)連通，布署了R個(gè)用于數(shù)據(jù)接力節(jié)點(diǎn)Vr，接力節(jié)點(diǎn)負(fù)責(zé)信息的轉(zhuǎn)發(fā)。監(jiān)測(cè)節(jié)點(diǎn)采集到的數(shù)據(jù)經(jīng)多跳轉(zhuǎn)發(fā)最終傳送到簇節(jié)點(diǎn)Vc，簇節(jié)點(diǎn)一方面接收簇內(nèi)的信息，同時(shí)參與簇之間的信息轉(zhuǎn)發(fā)，設(shè)簇節(jié)點(diǎn)個(gè)數(shù)為M。在該無(wú)線傳感器網(wǎng)絡(luò)模型中，有V=Vs∪Vr∪Vc。
2、 基于多簇點(diǎn)簡(jiǎn)化的K容錯(cuò)能量均衡拓?fù)淇刂品桨?/p>
本文提出了一個(gè)K容錯(cuò)能量均衡拓?fù)淇刂品桨浮Ｊ紫龋瑸榱撕?jiǎn)化運(yùn)算，該方案將多簇點(diǎn)異構(gòu)傳感器網(wǎng)絡(luò)簡(jiǎn)化為單簇點(diǎn)網(wǎng)絡(luò)，簡(jiǎn)化后的網(wǎng)絡(luò)連通性與簡(jiǎn)化前相同，且路徑保持能量最小；然后，在簡(jiǎn)化后的網(wǎng)絡(luò)結(jié)構(gòu)上，提出了一個(gè)K-MST算法，根據(jù)節(jié)點(diǎn)的位置信息，建立各監(jiān)測(cè)節(jié)點(diǎn)到簇節(jié)點(diǎn)的最小能耗的K連通網(wǎng)絡(luò)。
2．1 異構(gòu)傳感器網(wǎng)絡(luò)多簇點(diǎn)簡(jiǎn)化
在簡(jiǎn)化監(jiān)測(cè)節(jié)點(diǎn)與簇節(jié)點(diǎn)路徑時(shí)，若監(jiān)測(cè)節(jié)點(diǎn)和多個(gè)簇節(jié)點(diǎn)間存在路徑時(shí)，則保留監(jiān)測(cè)節(jié)點(diǎn)到簇節(jié)點(diǎn)的最小路徑。由此可見(jiàn)，如果網(wǎng)絡(luò)原拓?fù)涫荎連通的，則簡(jiǎn)化后的拓?fù)淙詾镵連通且是能量消耗最小的單簇點(diǎn)拓?fù)浣Y(jié)構(gòu)。
2．2 K-MST拓?fù)淇刂扑惴?/p>
3、 實(shí)驗(yàn)結(jié)果和性能分析
構(gòu)建1 000 m×1 000 m無(wú)線傳感器網(wǎng)絡(luò)仿真區(qū)域，網(wǎng)絡(luò)中隨機(jī)布置監(jiān)測(cè)節(jié)點(diǎn)70～140個(gè)不等，令網(wǎng)絡(luò)中監(jiān)測(cè)節(jié)點(diǎn)最大發(fā)射半徑為400 m，取簇節(jié)點(diǎn)個(gè)數(shù)N=3，首先對(duì)該網(wǎng)絡(luò)進(jìn)行多簇點(diǎn)簡(jiǎn)化，然后分別采用YG6，3算法、FLSS3算法以及本文提出的K-MST算法（K=3）進(jìn)行保證每個(gè)節(jié)點(diǎn)至簇節(jié)點(diǎn)有3條不相關(guān)路徑的拓?fù)淇刂疲瑢?duì)每種算法分別進(jìn)行50次仿真，將所得的節(jié)點(diǎn)平均度數(shù)和未進(jìn)行拓?fù)淇刂乒?jié)點(diǎn)平均度數(shù)進(jìn)行比較，如圖1所示。
從圖1可以看出，隨著網(wǎng)絡(luò)規(guī)模增大，未進(jìn)行拓?fù)淇刂频木W(wǎng)絡(luò)節(jié)點(diǎn)平均度數(shù)由11．4增加到23．37，且增長(zhǎng)速度很快。采用三種拓?fù)淇刂扑惴ň鶎⒐?jié)點(diǎn)的度數(shù)進(jìn)行了有效的控制，將平均度數(shù)減小到了16以下，這三種算法中，本文提出的K-MST算法將節(jié)點(diǎn)平均度數(shù)保證在2．8～2．94之間，比其他兩種算法更多地減少了路徑的冗余，較小的網(wǎng)絡(luò)冗余減少了數(shù)據(jù)傳輸過(guò)程中的數(shù)據(jù)沖突耗，可延長(zhǎng)能量有限的無(wú)線傳感器網(wǎng)絡(luò)工作壽命，又可較好地保證網(wǎng)絡(luò)的連通性。
采用YG6，3算法、FLSS3算法以及3-MST算法分別進(jìn)行50次仿真，將生成拓?fù)浣Y(jié)構(gòu)中平均鏈路長(zhǎng)度和未進(jìn)行拓?fù)淇刂频钠骄溌烽L(zhǎng)度進(jìn)行比較，如圖2所示。
從圖2可以看出，由于網(wǎng)絡(luò)規(guī)模增大，采用三種拓?fù)淇刂扑惴ㄋ玫木W(wǎng)絡(luò)平均鏈路長(zhǎng)度均呈下降趨勢(shì)，采用3-MST算法得到的平均鏈路長(zhǎng)度最小。這意味著在采用3-MST算法生成拓?fù)涞穆窂缴线M(jìn)行數(shù)據(jù)傳輸，比另外兩種算法可以消耗更少的能量，從而延長(zhǎng)網(wǎng)絡(luò)壽命。
4 、結(jié)論
針對(duì)異構(gòu)監(jiān)測(cè)傳感器網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)計(jì)了一個(gè)優(yōu)化的拓?fù)淇刂品桨福跍p少網(wǎng)絡(luò)冗余的同時(shí)兼顧了網(wǎng)絡(luò)的容錯(cuò)性，并且保證生成拓?fù)淇梢杂行а娱L(zhǎng)網(wǎng)絡(luò)生存周期。該拓?fù)淇刂品桨冈诒ＷC傳感器網(wǎng)絡(luò)K連通的前提下，可以最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑，可以較好地均衡無(wú)線傳感器網(wǎng)絡(luò)能耗，延長(zhǎng)網(wǎng)絡(luò)生命周期。
