基于多簇點(diǎn)簡(jiǎn)化的K容錯能量均衡拓撲控制方案

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

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

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

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

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