基于多簇點(diǎn)簡化的K容錯能量均衡拓?fù)淇刂品桨?/h1>
摘要:針對異構(gòu)監(jiān)測傳感器網(wǎng)絡(luò)結(jié)構(gòu),設(shè)計(jì)了一個容錯控制方案,在可以減少網(wǎng)絡(luò)冗余的同時,兼顧了網(wǎng)絡(luò)的穩(wěn)定性,并且保證生成能量消耗。該方案首先將異構(gòu)監(jiān)測傳感器網(wǎng)絡(luò)簡化為同構(gòu)傳感器網(wǎng)絡(luò)以簡化計(jì)算,然后根據(jù)節(jié)點(diǎn)的位置信息,建立各監(jiān)測節(jié)點(diǎn)到簇節(jié)點(diǎn)的能量消耗最小,并且可以保證K容錯的K連通子圖。該方案在保證傳感器網(wǎng)絡(luò)K連通的前提下,可以最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑,且可以較好地均衡無線傳感器網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生命周期。
關(guān)鍵詞:異構(gòu)無線傳感器網(wǎng)絡(luò);客錯控制;能量均衡;多簇點(diǎn)簡化
0 引言
在無線傳感器網(wǎng)絡(luò)拓?fù)?a class="contentlabel" href="http://www.ex-cimer.com/news/listbylabel/label/控制">控制算法的研究中,利用簡化冗余路徑可以降低通信干擾,減少能量消耗,并且延長網(wǎng)絡(luò)生存期。但是,以路徑簡化為主要方法的拓?fù)淇刂票囟◣砭W(wǎng)絡(luò)的健壯性下降。因此,在無線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯恐?,需要考慮具有容錯特性的拓?fù)淇刂茊栴}。如何建立能夠在當(dāng)K-1個節(jié)點(diǎn)失效時,仍然具有連通性的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),是近年來研究的一個熱點(diǎn)問題。
近年來,很多學(xué)者開展了關(guān)于容錯拓?fù)浣扑惴ǖ难芯?。如維持網(wǎng)絡(luò)K連通的全局近似算法FGSS和局部近似算法FLSS。但是由于這兩種算法不停地對比網(wǎng)絡(luò)路徑和判斷網(wǎng)絡(luò)是否達(dá)到K連通,開銷較大。文獻(xiàn)以同構(gòu)網(wǎng)絡(luò)為對象,提出了CBTC(a)算法。該算法中當(dāng)a=2π/3K條件滿足時,可使原網(wǎng)絡(luò)的生成子圖保持K連通性。文獻(xiàn)對隨機(jī)分布無線傳感器網(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ǎng)絡(luò)模型上,提出了一種基于多簇點(diǎn)簡化的K容錯能量均衡拓?fù)淇刂品桨?。該方案在保證傳感器網(wǎng)絡(luò)K連通的前提下;可最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑,且可以較好地均衡無線傳感器的網(wǎng)絡(luò)能耗。
1 異構(gòu)無線傳感器網(wǎng)絡(luò)模型
定義異構(gòu)無線傳感器網(wǎng)絡(luò),V表示傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)集合,E表示節(jié)點(diǎn)之間的通信路徑集合。傳感器網(wǎng)絡(luò)中包括三類節(jié)點(diǎn):監(jiān)測節(jié)點(diǎn)、接力節(jié)點(diǎn)和簇節(jié)點(diǎn)。設(shè)該傳感器網(wǎng)絡(luò)中,有N個用于信息監(jiān)測的傳感器節(jié)點(diǎn)Vs,該類節(jié)點(diǎn)用于采集監(jiān)測區(qū)域內(nèi)的信息,并將信息發(fā)送到鄰居節(jié)點(diǎn),且承擔(dān)轉(zhuǎn)發(fā)其他節(jié)點(diǎn)數(shù)據(jù)的任務(wù);為了使監(jiān)測區(qū)域內(nèi)保持網(wǎng)絡(luò)連通,布署了R個用于數(shù)據(jù)接力節(jié)點(diǎn)Vr,接力節(jié)點(diǎn)負(fù)責(zé)信息的轉(zhuǎn)發(fā)。監(jiān)測節(jié)點(diǎn)采集到的數(shù)據(jù)經(jīng)多跳轉(zhuǎn)發(fā)最終傳送到簇節(jié)點(diǎn)Vc,簇節(jié)點(diǎn)一方面接收簇內(nèi)的信息,同時參與簇之間的信息轉(zhuǎn)發(fā),設(shè)簇節(jié)點(diǎn)個數(shù)為M。在該無線傳感器網(wǎng)絡(luò)模型中,有V=Vs∪Vr∪Vc。
2 基于多簇點(diǎn)簡化的K容錯能量均衡拓?fù)淇刂品桨?br /> 本文提出了一個K容錯能量均衡拓?fù)淇刂品桨浮J紫?,為了簡化運(yùn)算,該方案將多簇點(diǎn)異構(gòu)傳感器網(wǎng)絡(luò)簡化為單簇點(diǎn)網(wǎng)絡(luò),簡化后的網(wǎng)絡(luò)連通性與簡化前相同,且路徑保持能量最?。蝗缓?,在簡化后的網(wǎng)絡(luò)結(jié)構(gòu)上,提出了一個K-MST算法,根據(jù)節(jié)點(diǎn)的位置信息,建立各監(jiān)測節(jié)點(diǎn)到簇節(jié)點(diǎn)的最小能耗的K連通網(wǎng)絡(luò)。
2.1 異構(gòu)傳感器網(wǎng)絡(luò)多簇點(diǎn)簡化
首先對異構(gòu)傳感器網(wǎng)絡(luò)模型進(jìn)行化簡。已知一個多簇點(diǎn)網(wǎng)絡(luò),包括N個監(jiān)測節(jié)點(diǎn)和M個簇節(jié)點(diǎn),V={n1,n2,…,nN,nN+1,nN+2,…,nN+M}。如果1≤i≤N,則節(jié)點(diǎn)ni為監(jiān)測節(jié)點(diǎn);當(dāng)Ni≤N+M時,ni為簇節(jié)點(diǎn)。
式中:表示在節(jié)點(diǎn),ni的最大發(fā)射范圍Rmax(ni)內(nèi),該節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的路徑;dist(ni,nj)是節(jié)點(diǎn),ni和nj之間的歐氏距離。由節(jié)點(diǎn)能量消耗模型可以算出路徑上數(shù)據(jù)傳輸需消耗節(jié)點(diǎn)能量值cost(ni,nj)。異構(gòu)傳感器網(wǎng)絡(luò)多簇點(diǎn)簡化到單簇點(diǎn)的步驟描述如下:
步驟1:簡化節(jié)點(diǎn)V→Vr,使Vr={n1,n2,…,nN,nN+1},即將M個簇節(jié)點(diǎn)簡化為1個節(jié)點(diǎn)nN+1,記為簇節(jié)點(diǎn)nroot,監(jiān)測節(jié)點(diǎn)不變。
摘要:針對異構(gòu)監(jiān)測傳感器網(wǎng)絡(luò)結(jié)構(gòu),設(shè)計(jì)了一個容錯控制方案,在可以減少網(wǎng)絡(luò)冗余的同時,兼顧了網(wǎng)絡(luò)的穩(wěn)定性,并且保證生成能量消耗。該方案首先將異構(gòu)監(jiān)測傳感器網(wǎng)絡(luò)簡化為同構(gòu)傳感器網(wǎng)絡(luò)以簡化計(jì)算,然后根據(jù)節(jié)點(diǎn)的位置信息,建立各監(jiān)測節(jié)點(diǎn)到簇節(jié)點(diǎn)的能量消耗最小,并且可以保證K容錯的K連通子圖。該方案在保證傳感器網(wǎng)絡(luò)K連通的前提下,可以最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑,且可以較好地均衡無線傳感器網(wǎng)絡(luò)能耗,延長網(wǎng)絡(luò)生命周期。
關(guān)鍵詞:異構(gòu)無線傳感器網(wǎng)絡(luò);客錯控制;能量均衡;多簇點(diǎn)簡化
0 引言
在無線傳感器網(wǎng)絡(luò)拓?fù)?a class="contentlabel" href="http://www.ex-cimer.com/news/listbylabel/label/控制">控制算法的研究中,利用簡化冗余路徑可以降低通信干擾,減少能量消耗,并且延長網(wǎng)絡(luò)生存期。但是,以路徑簡化為主要方法的拓?fù)淇刂票囟◣砭W(wǎng)絡(luò)的健壯性下降。因此,在無線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯恐?,需要考慮具有容錯特性的拓?fù)淇刂茊栴}。如何建立能夠在當(dāng)K-1個節(jié)點(diǎn)失效時,仍然具有連通性的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),是近年來研究的一個熱點(diǎn)問題。
近年來,很多學(xué)者開展了關(guān)于容錯拓?fù)浣扑惴ǖ难芯?。如維持網(wǎng)絡(luò)K連通的全局近似算法FGSS和局部近似算法FLSS。但是由于這兩種算法不停地對比網(wǎng)絡(luò)路徑和判斷網(wǎng)絡(luò)是否達(dá)到K連通,開銷較大。文獻(xiàn)以同構(gòu)網(wǎng)絡(luò)為對象,提出了CBTC(a)算法。該算法中當(dāng)a=2π/3K條件滿足時,可使原網(wǎng)絡(luò)的生成子圖保持K連通性。文獻(xiàn)對隨機(jī)分布無線傳感器網(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ǎng)絡(luò)模型上,提出了一種基于多簇點(diǎn)簡化的K容錯能量均衡拓?fù)淇刂品桨?。該方案在保證傳感器網(wǎng)絡(luò)K連通的前提下;可最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑,且可以較好地均衡無線傳感器的網(wǎng)絡(luò)能耗。
1 異構(gòu)無線傳感器網(wǎng)絡(luò)模型
定義異構(gòu)無線傳感器網(wǎng)絡(luò),V表示傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)集合,E表示節(jié)點(diǎn)之間的通信路徑集合。傳感器網(wǎng)絡(luò)中包括三類節(jié)點(diǎn):監(jiān)測節(jié)點(diǎn)、接力節(jié)點(diǎn)和簇節(jié)點(diǎn)。設(shè)該傳感器網(wǎng)絡(luò)中,有N個用于信息監(jiān)測的傳感器節(jié)點(diǎn)Vs,該類節(jié)點(diǎn)用于采集監(jiān)測區(qū)域內(nèi)的信息,并將信息發(fā)送到鄰居節(jié)點(diǎn),且承擔(dān)轉(zhuǎn)發(fā)其他節(jié)點(diǎn)數(shù)據(jù)的任務(wù);為了使監(jiān)測區(qū)域內(nèi)保持網(wǎng)絡(luò)連通,布署了R個用于數(shù)據(jù)接力節(jié)點(diǎn)Vr,接力節(jié)點(diǎn)負(fù)責(zé)信息的轉(zhuǎn)發(fā)。監(jiān)測節(jié)點(diǎn)采集到的數(shù)據(jù)經(jīng)多跳轉(zhuǎn)發(fā)最終傳送到簇節(jié)點(diǎn)Vc,簇節(jié)點(diǎn)一方面接收簇內(nèi)的信息,同時參與簇之間的信息轉(zhuǎn)發(fā),設(shè)簇節(jié)點(diǎn)個數(shù)為M。在該無線傳感器網(wǎng)絡(luò)模型中,有V=Vs∪Vr∪Vc。
2 基于多簇點(diǎn)簡化的K容錯能量均衡拓?fù)淇刂品桨?br /> 本文提出了一個K容錯能量均衡拓?fù)淇刂品桨浮J紫?,為了簡化運(yùn)算,該方案將多簇點(diǎn)異構(gòu)傳感器網(wǎng)絡(luò)簡化為單簇點(diǎn)網(wǎng)絡(luò),簡化后的網(wǎng)絡(luò)連通性與簡化前相同,且路徑保持能量最?。蝗缓?,在簡化后的網(wǎng)絡(luò)結(jié)構(gòu)上,提出了一個K-MST算法,根據(jù)節(jié)點(diǎn)的位置信息,建立各監(jiān)測節(jié)點(diǎn)到簇節(jié)點(diǎn)的最小能耗的K連通網(wǎng)絡(luò)。
2.1 異構(gòu)傳感器網(wǎng)絡(luò)多簇點(diǎn)簡化
首先對異構(gòu)傳感器網(wǎng)絡(luò)模型進(jìn)行化簡。已知一個多簇點(diǎn)網(wǎng)絡(luò),包括N個監(jiān)測節(jié)點(diǎn)和M個簇節(jié)點(diǎn),V={n1,n2,…,nN,nN+1,nN+2,…,nN+M}。如果1≤i≤N,則節(jié)點(diǎn)ni為監(jiān)測節(jié)點(diǎn);當(dāng)Ni≤N+M時,ni為簇節(jié)點(diǎn)。
式中:表示在節(jié)點(diǎn),ni的最大發(fā)射范圍Rmax(ni)內(nèi),該節(jié)點(diǎn)到鄰居節(jié)點(diǎn)的路徑;dist(ni,nj)是節(jié)點(diǎn),ni和nj之間的歐氏距離。由節(jié)點(diǎn)能量消耗模型可以算出路徑上數(shù)據(jù)傳輸需消耗節(jié)點(diǎn)能量值cost(ni,nj)。異構(gòu)傳感器網(wǎng)絡(luò)多簇點(diǎn)簡化到單簇點(diǎn)的步驟描述如下:
步驟1:簡化節(jié)點(diǎn)V→Vr,使Vr={n1,n2,…,nN,nN+1},即將M個簇節(jié)點(diǎn)簡化為1個節(jié)點(diǎn)nN+1,記為簇節(jié)點(diǎn)nroot,監(jiān)測節(jié)點(diǎn)不變。
評論