引言

在無線傳感器網(wǎng)絡拓撲控制算法的研究中，利用簡化冗余路徑可以降低通信干擾，減少能量消耗，并且延長網(wǎng)絡生存期。但是，以路徑簡化為主要方法的拓撲控制必定帶來網(wǎng)絡的健壯性下降。因此，在無線傳感器網(wǎng)絡拓撲控制研究中，需要考慮具有容錯特性的拓撲控制問題。如何建立能夠在當K-1個節(jié)點失效時，仍然具有連通性的無線傳感器網(wǎng)絡拓撲結構，是近年來研究的一個熱點問題。

近年來，很多學者開展了關于容錯拓撲近似算法的研究。如維持網(wǎng)絡K連通的全局近似算法FGSS和局部近似算法FLSS。但是由于這兩種算法不停地對比網(wǎng)絡路徑和判斷網(wǎng)絡是否達到K連通，開銷較大。文獻以同構網(wǎng)絡為對象，提出了CBTC（a）算法。該算法中當a=2π／3K條件滿足時，可使原網(wǎng)絡的生成子圖保持K連通性。文獻對隨機分布無線傳感器網(wǎng)絡節(jié)點的發(fā)射半徑與形成K連通圖的概率關系進行了分析，并提出Yp，K結構能夠使生成K連通子圖保持原拓撲的K連通性。文獻提出了集中式和分布式算法K-UPVCS，但是該算法產(chǎn)生的拓撲結構極易產(chǎn)生回路而造成網(wǎng)絡不能夠連通。

本文在異構無線傳感器網(wǎng)絡模型上，提出了一種基于多簇點簡化的K容錯能量均衡拓撲控制方案。該方案在保證傳感器網(wǎng)絡K連通的前提下；可最大限度減少傳感器網(wǎng)絡中的冗余路徑，且可以較好地均衡無線傳感器的網(wǎng)絡能耗。

1、 異構無線傳感器網(wǎng)絡模型

定義異構無線傳感器網(wǎng)絡，V表示傳感器網(wǎng)絡中的節(jié)點集合，E表示節(jié)點之間的通信路徑集合。傳感器網(wǎng)絡中包括三類節(jié)點：監(jiān)測節(jié)點、接力節(jié)點和簇節(jié)點。設該傳感器網(wǎng)絡中，有N個用于信息監(jiān)測的傳感器節(jié)點Vs，該類節(jié)點用于采集監(jiān)測區(qū)域內(nèi)的信息，并將信息發(fā)送到鄰居節(jié)點，且承擔轉發(fā)其他節(jié)點數(shù)據(jù)的任務；為了使監(jiān)測區(qū)域內(nèi)保持網(wǎng)絡連通，布署了R個用于數(shù)據(jù)接力節(jié)點Vr，接力節(jié)點負責信息的轉發(fā)。監(jiān)測節(jié)點采集到的數(shù)據(jù)經(jīng)多跳轉發(fā)最終傳送到簇節(jié)點Vc，簇節(jié)點一方面接收簇內(nèi)的信息，同時參與簇之間的信息轉發(fā)，設簇節(jié)點個數(shù)為M。在該無線傳感器網(wǎng)絡模型中，有V=Vs∪Vr∪Vc。

2、 基于多簇點簡化的K容錯能量均衡拓撲控制方案

本文提出了一個K容錯能量均衡拓撲控制方案。首先，為了簡化運算，該方案將多簇點異構傳感器網(wǎng)絡簡化為單簇點網(wǎng)絡，簡化后的網(wǎng)絡連通性與簡化前相同，且路徑保持能量最?。蝗缓?，在簡化后的網(wǎng)絡結構上，提出了一個K-MST算法，根據(jù)節(jié)點的位置信息，建立各監(jiān)測節(jié)點到簇節(jié)點的最小能耗的K連通網(wǎng)絡。

2．1 異構傳感器網(wǎng)絡多簇點簡化

在簡化監(jiān)測節(jié)點與簇節(jié)點路徑時，若監(jiān)測節(jié)點和多個簇節(jié)點間存在路徑時，則保留監(jiān)測節(jié)點到簇節(jié)點的最小路徑。由此可見，如果網(wǎng)絡原拓撲是K連通的，則簡化后的拓撲仍為K連通且是能量消耗最小的單簇點拓撲結構。

2．2 K-MST拓撲控制算法

3、 實驗結果和性能分析

構建1 000 m×1 000 m無線傳感器網(wǎng)絡仿真區(qū)域，網(wǎng)絡中隨機布置監(jiān)測節(jié)點70～140個不等，令網(wǎng)絡中監(jiān)測節(jié)點最大發(fā)射半徑為400 m，取簇節(jié)點個數(shù)N=3，首先對該網(wǎng)絡進行多簇點簡化，然后分別采用YG6，3算法、FLSS3算法以及本文提出的K-MST算法（K=3）進行保證每個節(jié)點至簇節(jié)點有3條不相關路徑的拓撲控制，對每種算法分別進行50次仿真，將所得的節(jié)點平均度數(shù)和未進行拓撲控制節(jié)點平均度數(shù)進行比較，如圖1所示。

從圖1可以看出，隨著網(wǎng)絡規(guī)模增大，未進行拓撲控制的網(wǎng)絡節(jié)點平均度數(shù)由11．4增加到23．37，且增長速度很快。采用三種拓撲控制算法均將節(jié)點的度數(shù)進行了有效的控制，將平均度數(shù)減小到了16以下，這三種算法中，本文提出的K-MST算法將節(jié)點平均度數(shù)保證在2．8～2．94之間，比其他兩種算法更多地減少了路徑的冗余，較小的網(wǎng)絡冗余減少了數(shù)據(jù)傳輸過程中的數(shù)據(jù)沖突耗，可延長能量有限的無線傳感器網(wǎng)絡工作壽命，又可較好地保證網(wǎng)絡的連通性。

采用YG6，3算法、FLSS3算法以及3-MST算法分別進行50次仿真，將生成拓撲結構中平均鏈路長度和未進行拓撲控制的平均鏈路長度進行比較，如圖2所示。

從圖2可以看出，由于網(wǎng)絡規(guī)模增大，采用三種拓撲控制算法所得的網(wǎng)絡平均鏈路長度均呈下降趨勢，采用3-MST算法得到的平均鏈路長度最小。這意味著在采用3-MST算法生成拓撲的路徑上進行數(shù)據(jù)傳輸，比另外兩種算法可以消耗更少的能量，從而延長網(wǎng)絡壽命。

4 、結論

針對異構監(jiān)測傳感器網(wǎng)絡結構，設計了一個優(yōu)化的拓撲控制方案，在減少網(wǎng)絡冗余的同時兼顧了網(wǎng)絡的容錯性，并且保證生成拓撲可以有效延長網(wǎng)絡生存周期。該拓撲控制方案在保證傳感器網(wǎng)絡K連通的前提下，可以最大限度減少傳感器網(wǎng)絡中的冗余路徑，可以較好地均衡無線傳感器網(wǎng)絡能耗，延長網(wǎng)絡生命周期。