摘要：針對異構(gòu)監(jiān)測傳感器網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)計了一個容錯拓?fù)淇刂?/strong>方案，在可以減少網(wǎng)絡(luò)冗余的同時，兼顧了網(wǎng)絡(luò)的穩(wěn)定性，并且保證生成拓?fù)渚哂凶钚〉哪芰肯?。該方案首先將異?gòu)監(jiān)測傳感器網(wǎng)絡(luò)簡化為同構(gòu)傳感器網(wǎng)絡(luò)以簡化計算，然后根據(jù)節(jié)點的位置信息，建立各監(jiān)測節(jié)點到簇節(jié)點的能量消耗最小，并且可以保證K容錯的K連通子圖。該方案在保證傳感器網(wǎng)絡(luò)K連通的前提下，可以最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑，且可以較好地均衡無線傳感器網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生命周期。
關(guān)鍵詞：異構(gòu)無線傳感器網(wǎng)絡(luò)；客錯拓?fù)淇刂疲荒芰烤?；多簇點簡化

0 引言
    在無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǖ难芯恐?，利用簡化冗余路徑可以降低通信干擾，減少能量消耗，并且延長網(wǎng)絡(luò)生存期。但是，以路徑簡化為主要方法的拓?fù)淇刂票囟◣砭W(wǎng)絡(luò)的健壯性下降。因此，在無線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯恐校枰紤]具有容錯特性的拓?fù)淇刂茊栴}。如何建立能夠在當(dāng)K-1個節(jié)點失效時，仍然具有連通性的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，是近年來研究的一個熱點問題。
    近年來，很多學(xué)者開展了關(guān)于容錯拓?fù)浣扑惴ǖ难芯俊Ｈ缇S持網(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é)點的發(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ò)模型上，提出了一種基于多簇點簡化的K容錯能量均衡拓?fù)?strong>控制方案。該方案在保證傳感器網(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é)點集合，E表示節(jié)點之間的通信路徑集合。傳感器網(wǎng)絡(luò)中包括三類節(jié)點：監(jiān)測節(jié)點、接力節(jié)點和簇節(jié)點。設(shè)該傳感器網(wǎng)絡(luò)中，有N個用于信息監(jiān)測的傳感器節(jié)點Vs，該類節(jié)點用于采集監(jiān)測區(qū)域內(nèi)的信息，并將信息發(fā)送到鄰居節(jié)點，且承擔(dān)轉(zhuǎn)發(fā)其他節(jié)點數(shù)據(jù)的任務(wù)；為了使監(jiān)測區(qū)域內(nèi)保持網(wǎng)絡(luò)連通，布署了R個用于數(shù)據(jù)接力節(jié)點Vr，接力節(jié)點負(fù)責(zé)信息的轉(zhuǎn)發(fā)。監(jiān)測節(jié)點采集到的數(shù)據(jù)經(jīng)多跳轉(zhuǎn)發(fā)最終傳送到簇節(jié)點Vc，簇節(jié)點一方面接收簇內(nèi)的信息，同時參與簇之間的信息轉(zhuǎn)發(fā)，設(shè)簇節(jié)點個數(shù)為M。在該無線傳感器網(wǎng)絡(luò)模型中，有V=Vs∪Vr∪Vc。

2 基于多簇點簡化的K容錯能量均衡拓?fù)淇刂品桨?br />     本文提出了一個K容錯能量均衡拓?fù)淇刂品桨?。首先，為了簡化運(yùn)算，該方案將多簇點異構(gòu)傳感器網(wǎng)絡(luò)簡化為單簇點網(wǎng)絡(luò)，簡化后的網(wǎng)絡(luò)連通性與簡化前相同，且路徑保持能量最小；然后，在簡化后的網(wǎng)絡(luò)結(jié)構(gòu)上，提出了一個K-MST算法，根據(jù)節(jié)點的位置信息，建立各監(jiān)測節(jié)點到簇節(jié)點的最小能耗的K連通網(wǎng)絡(luò)。
2．1 異構(gòu)傳感器網(wǎng)絡(luò)多簇點簡化
    首先對異構(gòu)傳感器網(wǎng)絡(luò)模型進(jìn)行化簡。已知一個多簇點網(wǎng)絡(luò)，包括N個監(jiān)測節(jié)點和M個簇節(jié)點，V={n1，n2，…，nN，nN+1，nN+2，…，nN+M}。如果1≤i≤N，則節(jié)點ni為監(jiān)測節(jié)點；當(dāng)N<i≤N+M時，ni為簇節(jié)點。
   
    式中：表示在節(jié)點，ni的最大發(fā)射范圍Rmax(ni)內(nèi)，該節(jié)點到鄰居節(jié)點的路徑；dist(ni，nj)是節(jié)點，ni和nj之間的歐氏距離。由節(jié)點能量消耗模型可以算出路徑上數(shù)據(jù)傳輸需消耗節(jié)點能量值cost(ni，nj)。異構(gòu)傳感器網(wǎng)絡(luò)多簇點簡化到單簇點的步驟描述如下：
    步驟1：簡化節(jié)點V→Vr，使Vr={n1，n2，…，nN，nN+1}，即將M個簇節(jié)點簡化為1個節(jié)點nN+1，記為簇節(jié)點nroot，監(jiān)測節(jié)點不變。
    步驟2：簡化路徑，減化過程分為兩個步驟。
    (1)保留N個監(jiān)測節(jié)點之間的所有路徑；
    (2)當(dāng)監(jiān)測節(jié)點ni和簇節(jié)點nj間只存在一條路徑ni→nj(N+1≤j≤N+M)，令nroot<=nj且；當(dāng)監(jiān)測節(jié)點ni和多個簇節(jié)點間存在路徑時，為了保證網(wǎng)絡(luò)能量消耗最小，則保留該節(jié)點到簇節(jié)點的最小路徑min(cost(ni，nj))，且使該簇節(jié)點變?yōu)閚root。
    在簡化監(jiān)測節(jié)點與簇節(jié)點路徑時，若監(jiān)測節(jié)點和多個簇節(jié)點間存在路徑時，則保留監(jiān)測節(jié)點到簇節(jié)點的最小路徑。由此可見，如果網(wǎng)絡(luò)原拓?fù)涫荎連通的，則簡化后的拓?fù)淙詾镵連通且是能量消耗最小的單簇點拓?fù)浣Y(jié)構(gòu)。
2．2 K-MST拓?fù)淇刂扑惴?br />     K-MST拓?fù)淇刂扑惴ㄖ?，有如下定義：
    定義1：定義節(jié)點ni的鄰居節(jié)點為{nj|nj∈V，j≠i)；
    定義2：規(guī)定網(wǎng)絡(luò)中的邊有惟一權(quán)值。給定兩條邊(u1，v1)∈E和(u2，v2)∈E，dist(·，·)表示兩個節(jié)點間的歐氏距離，則邊的權(quán)值函數(shù)w：E→R滿足：
   
    id(u1)表示節(jié)點u的序號，可以取其ID號或者M(jìn)AC地址。這樣可以保證在圖Gr中的權(quán)值惟一，即使是權(quán)值相同的邊(u，v)和(v，u)。
在異構(gòu)監(jiān)測無線傳感器網(wǎng)絡(luò)圖中，任意監(jiān)測節(jié)點與簇節(jié)點間生成K條不相交路徑的算法分四步進(jìn)行。
    步驟1：將多簇點網(wǎng)絡(luò)簡化為單簇點網(wǎng)絡(luò)，即。
    步驟2：求網(wǎng)絡(luò)的最小生成樹，生成各監(jiān)測節(jié)點至簇節(jié)點的能量消耗最小路徑，將這些路徑作為網(wǎng)絡(luò)信息采集和傳輸?shù)闹髀窂?，整個網(wǎng)絡(luò)能量消耗最小。
    步驟3：將主路徑斷開，在條路徑中求最小生成樹可保證節(jié)點有兩條路徑和簇點連通。
    步驟4：重復(fù)步驟3，生成直至網(wǎng)絡(luò)K連通，則保證網(wǎng)絡(luò)的K連通子圖為。

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

    從圖1可以看出，隨著網(wǎng)絡(luò)規(guī)模增大，未進(jìn)行拓?fù)淇刂频木W(wǎng)絡(luò)節(jié)點平均度數(shù)由11．4增加到23．37，且增長速度很快。采用三種拓?fù)淇刂扑惴ň鶎⒐?jié)點的度數(shù)進(jìn)行了有效的控制，將平均度數(shù)減小到了16以下，這三種算法中，本文提出的K-MST算法將節(jié)點平均度數(shù)保證在2．8～2．94之間，比其他兩種算法更多地減少了路徑的冗余，較小的網(wǎng)絡(luò)冗余減少了數(shù)據(jù)傳輸過程中的數(shù)據(jù)沖突耗，可延長能量有限的無線傳感器網(wǎng)絡(luò)工作壽命，又可較好地保證網(wǎng)絡(luò)的連通性。
    采用YG6,3算法、FLSS3算法以及3-MST算法分別進(jìn)行50次仿真，將生成拓?fù)浣Y(jié)構(gòu)中平均鏈路長度和未進(jìn)行拓?fù)淇刂频钠骄溌烽L度進(jìn)行比較，如圖2所示。

    從圖2可以看出，由于網(wǎng)絡(luò)規(guī)模增大，采用三種拓?fù)淇刂扑惴ㄋ玫木W(wǎng)絡(luò)平均鏈路長度均呈下降趨勢，采用3-MST算法得到的平均鏈路長度最小。這意味著在采用3-MST算法生成拓?fù)涞穆窂缴线M(jìn)行數(shù)據(jù)傳輸，比另外兩種算法可以消耗更少的能量，從而延長網(wǎng)絡(luò)壽命。

4 結(jié)論
    針對異構(gòu)監(jiān)測傳感器網(wǎng)絡(luò)結(jié)構(gòu)，設(shè)計了一個優(yōu)化的拓?fù)?strong>控制方案，在減少網(wǎng)絡(luò)冗余的同時兼顧了網(wǎng)絡(luò)的容錯性，并且保證生成拓?fù)淇梢杂行а娱L網(wǎng)絡(luò)生存周期。該拓?fù)淇刂?/strong>方案在保證傳感器網(wǎng)絡(luò)K連通的前提下，可以最大限度減少傳感器網(wǎng)絡(luò)中的冗余路徑，可以較好地均衡無線傳感器網(wǎng)絡(luò)能耗，延長網(wǎng)絡(luò)生命周期。