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

摘要：針對異構監測傳感器網絡結構，設計了一個容錯拓撲控制方案，在可以減少網絡冗余的同時，兼顧了網絡的穩定性，并且保證生成拓撲具有最小的能量消耗。該方案首先將異構監測傳感器網絡簡化為同構傳感器網絡以簡化計算，然后根據節點的位置信息，建立各監測節點到簇節點的能量消耗最小，并且可以保證K容錯的K連通子圖。該方案在保證傳感器網絡K連通的前提下，可以最大限度減少傳感器網絡中的冗余路徑，且可以較好地均衡無線傳感器網絡能耗，延長網絡生命周期。
關鍵詞：異構無線傳感器網絡；客錯拓撲控制；能量均衡；多簇點簡化

0 引言
在無線傳感器網絡拓撲控制算法的研究中，利用簡化冗余路徑可以降低通信干擾，減少能量消耗，并且延長網絡生存期。但是，以路徑簡化為主要方法的拓撲控制必定帶來網絡的健壯性下降。因此，在無線傳感器網絡拓撲控制研究中，需要考慮具有容錯特性的拓撲控制問題。如何建立能夠在當K-1個節點失效時，仍然具有連通性的無線傳感器網絡拓撲結構，是近年來研究的一個熱點問題。
近年來，很多學者開展了關于容錯拓撲近似算法的研究。如維持網絡K連通的全局近似算法FGSS和局部近似算法FLSS。但是由于這兩種算法不停地對比網絡路徑和判斷網絡是否達到K連通，開銷較大。文獻以同構網絡為對象，提出了CBTC(a)算法。該算法中當a=2π／3K條件滿足時，可使原網絡的生成子圖保持K連通性。文獻對隨機分布無線傳感器網絡節點的發射半徑與形成K連通圖的概率關系進行了分析，并提出Yp,K結構能夠使生成K連通子圖保持原拓撲的K連通性。文獻提出了集中式和分布式算法K-UPVCS，但是該算法產生的拓撲結構極易產生回路而造成網絡不能夠連通。
本文在異構無線傳感器網絡模型上，提出了一種基于多簇點簡化的K容錯能量均衡拓撲控制方案。該方案在保證傳感器網絡K連通的前提下；可最大限度減少傳感器網絡中的冗余路徑，且可以較好地均衡無線傳感器的網絡能耗。

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

2 基于多簇點簡化的K容錯能量均衡拓撲控制方案
本文提出了一個K容錯能量均衡拓撲控制方案。首先，為了簡化運算，該方案將多簇點異構傳感器網絡簡化為單簇點網絡，簡化后的網絡連通性與簡化前相同，且路徑保持能量最??；然后，在簡化后的網絡結構上，提出了一個K-MST算法，根據節點的位置信息，建立各監測節點到簇節點的最小能耗的K連通網絡。
2．1 異構傳感器網絡多簇點簡化
首先對異構傳感器網絡模型進行化簡。已知一個多簇點網絡，包括N個監測節點和M個簇節點，V={n1，n2，…，nN，nN+1，nN+2，…，nN+M}。如果1≤i≤N，則節點ni為監測節點；當Ni≤N+M時，ni為簇節點。

式中：表示在節點，ni的最大發射范圍Rmax(ni)內，該節點到鄰居節點的路徑；dist(ni，nj)是節點，ni和nj之間的歐氏距離。由節點能量消耗模型可以算出路徑上數據傳輸需消耗節點能量值cost(ni，nj)。異構傳感器網絡多簇點簡化到單簇點的步驟描述如下：
步驟1：簡化節點V→Vr，使Vr={n1，n2，…，nN，nN+1}，即將M個簇節點簡化為1個節點nN+1，記為簇節點nroot，監測節點不變。