吳 昊，陳雯柏，2，王文凱，郝 翠

（1.北京信息科技大學(xué) 自動化學(xué)院，北京 100192；2.北京市通信與信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，北京 100044）

當(dāng)前，無線傳感器網(wǎng)絡(luò)（wireless sensor networks，WSNs）廣泛應(yīng)用于社會各領(lǐng)域［1－2］。當(dāng)處于復(fù)雜、對抗和惡劣的網(wǎng)絡(luò)環(huán)境中時(shí)，系統(tǒng)拓?fù)浣Y(jié)構(gòu)的抗毀性和可靠性是無線傳感器節(jié)點(diǎn)成功完成任務(wù)的關(guān)鍵［3－4］。人為打擊、能量耗盡以及惡劣的感知環(huán)境等因素，將直接或間接導(dǎo)致無線傳感器節(jié)點(diǎn)的失效，進(jìn)而致使WSNs系統(tǒng)拓?fù)浣Y(jié)構(gòu)分割，降低WSNs系統(tǒng)的性能，進(jìn)而導(dǎo)致感知任務(wù)失?。?］。

為增強(qiáng)WSNs系統(tǒng)拓?fù)浣Y(jié)構(gòu)抗毀性，Yin等［6］基于WSNs無標(biāo)度拓?fù)湔归_研究，得到度分布指數(shù)和冪律系數(shù)與WSNs容錯性能正相關(guān)這一結(jié)論。李雅倩等［7］利用概率母函數(shù)法求解WSNs無標(biāo)度拓?fù)浼壜?lián)失效的臨界負(fù)載值。但這種平面型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)缺乏靈活性，在網(wǎng)絡(luò)中會存在大量冗余鏈接，加大整個WSNs系統(tǒng)的通信負(fù)載量，使得WSNs的能量消耗加劇，從而縮短網(wǎng)絡(luò)的整體生存周期。相對而言，層次型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可有效對節(jié)點(diǎn)進(jìn)行分層管理，減少節(jié)點(diǎn)通信能耗，并且網(wǎng)絡(luò)可擴(kuò)展性較好。近年來，基于分簇機(jī)制的層次型拓?fù)淇刂瞥蔀檠芯繜狳c(diǎn)。Dasgupta等［8］提出一種基于分簇的啟發(fā)式算法使網(wǎng)絡(luò)存活時(shí)間最大化。常鐵原等［9］通過平衡簇內(nèi)節(jié)點(diǎn)通信與簇間節(jié)點(diǎn)通信的能耗，使用副簇頭進(jìn)行中繼轉(zhuǎn)發(fā)延長網(wǎng)絡(luò)壽命。周遠(yuǎn)林等［10］提出一種基于演化博弈論的無線傳感器網(wǎng)絡(luò)節(jié)能分簇路由算法，均衡節(jié)點(diǎn)間能耗，有效延長網(wǎng)絡(luò)生命周期。但這些算法大多只是針對網(wǎng)絡(luò)能量消耗進(jìn)行優(yōu)化以延長網(wǎng)絡(luò)壽命，并未考慮節(jié)點(diǎn)失效的情況。

在WSNs系統(tǒng)中，傳感器節(jié)點(diǎn)的失效會導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷改變，網(wǎng)絡(luò)中容易出現(xiàn)連通性較差的節(jié)點(diǎn)。該節(jié)點(diǎn)的存在會造成感知信息傳遞的擁塞，一旦能量耗盡或者遭受到惡意攻擊，很可能使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)斷裂，甚至網(wǎng)絡(luò)崩潰［11－13］。本文針對于無線傳感器網(wǎng)絡(luò)復(fù)雜應(yīng)用環(huán)境中簇頭節(jié)點(diǎn)失效問題，提出一種改進(jìn)的多簇頭K連通抗毀拓?fù)浣Y(jié)構(gòu)的構(gòu)建方法，并基于OPNET仿真，驗(yàn)證分析了算法的有效性。

1 系統(tǒng)抗毀性模型

假設(shè)WSNs系統(tǒng)中各節(jié)點(diǎn)功率可調(diào)，t時(shí)刻節(jié)點(diǎn)vi的發(fā)射功率為0≤pi（t）≤pmax，其中pmax表示所有成員節(jié)點(diǎn)vi的最大發(fā)射功率。根據(jù)傳輸媒介中的噪音類型，各個節(jié)點(diǎn)需要的傳輸能耗由無線傳輸模型進(jìn)行計(jì)算［14］。

采用的無線傳輸模型不僅考慮了接收器的接收功耗，還考慮到了發(fā)射器的傳輸功耗。t時(shí)刻發(fā)射器傳輸功耗與節(jié)點(diǎn)vi和節(jié)點(diǎn)vj間的距離dij（t）成正比。pij（t）表示t時(shí)刻節(jié)點(diǎn)vi和節(jié)點(diǎn)vj之間能實(shí)現(xiàn)信息交互需要的傳輸功率。所以，經(jīng)過dij（t）的距離傳輸b bits信息，各個節(jié)點(diǎn)需要的傳輸功耗如下：

式中：pelec和λamp分別為發(fā)射器和接收器的驅(qū)動電路以及放大器需要的無線傳輸損耗。

每個節(jié)點(diǎn)的初始傳輸功率一致，節(jié)點(diǎn)隨機(jī)部署后，可得到一個動態(tài)的網(wǎng)絡(luò)拓?fù)鋱DG（t）＝（V，E（t）），其中節(jié)點(diǎn)集V＝（v1，v2，…，vn）表示W(wǎng)SNs系統(tǒng)中的傳感器節(jié)點(diǎn)，若t時(shí)刻兩傳感器節(jié)點(diǎn)間進(jìn)行了通信，則邊集E（t）表示隨時(shí)間變化的各傳感器節(jié)點(diǎn)間的無向信息交互邊，如式（4）所示：

式中：傳感器節(jié)點(diǎn)vi和vj間的信息交互邊用（vi，vj）來表示。

引入以下相關(guān)定義與假設(shè)：

定義1 在分簇算法中用無向圖來表示節(jié)點(diǎn)之間的雙向鏈路連接，不考慮隱藏終端和暴露終端等問題。

定義2 在t時(shí)刻，圖G（t）＝（V，E（t））是K連通的，圖G（t）中任意K－1個節(jié)點(diǎn)失效，圖G（t）會分割為2個或多個連通子圖。

定義3 AP節(jié)點(diǎn)使用全向天線進(jìn)行廣播通信，AP節(jié)點(diǎn)能量無限且全網(wǎng)一跳可達(dá)。

定義4 節(jié)點(diǎn)vi和vj之間的距離dij＜R，說明vi和vj可直接通信，則vi和vj之間的跳數(shù)DH（vi，vj）；若vi和vj之間不能通信，則DH（vi，vj）＝0。

定義5 各節(jié)點(diǎn)有唯一標(biāo)識id（vi）＝i。節(jié)點(diǎn)的一跳鄰居數(shù)為Nbn，即節(jié)點(diǎn)的度。

定義6 簇頭是簇的管理者和信息收集中心。簇頭集合用CH表示。

定義7 簇集合用C表示，C＝（C1，C2，…，CK），CH（i）為簇Ci的簇頭，其id為id（CHi），簇大小即簇內(nèi)成員節(jié)點(diǎn)數(shù)用NC（Ci）表示。

2 改進(jìn)多簇頭K連通網(wǎng)絡(luò)抗毀算法

改進(jìn)多簇頭K連通網(wǎng)絡(luò)抗毀策略分為3個階段：第1階段為簇頭選舉；第2階段為簇內(nèi)關(guān)鍵節(jié)點(diǎn)檢測；第3階段是構(gòu)建簇內(nèi)K連通網(wǎng)絡(luò)。簇頭選舉前，需要對網(wǎng)絡(luò)進(jìn)行分簇，網(wǎng)絡(luò)分簇采用KMeans聚類算法把WSNs系統(tǒng)劃分為K個互不相交疊的簇；網(wǎng)絡(luò)分簇后，基于節(jié)點(diǎn)連通可靠度來進(jìn)行簇頭選舉，然后簇頭節(jié)點(diǎn)為建立簇內(nèi)成員節(jié)點(diǎn)與簇頭節(jié)點(diǎn)之間的通信路徑，加載地理位置路由算法在簇內(nèi)進(jìn)行泛洪，產(chǎn)生節(jié)點(diǎn)路由信息表，檢測關(guān)鍵節(jié)點(diǎn)，若節(jié)點(diǎn)維護(hù)的鄰居節(jié)點(diǎn)的路由表中沒有K個鄰居，則簇頭節(jié)點(diǎn)給成員節(jié)點(diǎn)發(fā)送hello消息包，成員節(jié)點(diǎn)收到消息包后，調(diào)節(jié)節(jié)點(diǎn)發(fā)射功率，使其可以與其他節(jié)點(diǎn)進(jìn)行通信。

2.1 基于連通可靠度的多簇頭選舉算法

基于連通可靠度的多簇頭選舉算法需要計(jì)算節(jié)點(diǎn)連通性，采用連通可靠度約束確定臨時(shí)簇頭集合，根據(jù)臨時(shí)簇頭節(jié)點(diǎn)的權(quán)值大小確定工作簇頭。多簇頭選舉算法描述如算法1所示。

輸入：網(wǎng)絡(luò)相關(guān)參數(shù)

do k-means；

do選取臨時(shí)簇頭；

do選舉簇頭；

if簇頭失效

then臨時(shí)簇頭升級為簇頭；

end if

在水泥混凝土路面切縫方面，應(yīng)該實(shí)施橫向施工縫配合鋸縫方法，保證縫深度在6cm左右，縫寬度在5mm左右。切縫過程中要始終保證充足注水，且允許在切縫過程中直接切斷，但需要時(shí)刻關(guān)注刀片的注水情況。另外在接縫位置要采用灌縫料加工方法，鋸縫位置澆灌水泥混合瀝青，且在灌縫之前需要清除縫隙內(nèi)存在的臨時(shí)密堵材料，保證縫頂面高度施工與路面位置平齊，全面提高水泥混凝土路面的施工質(zhì)量[4]。

節(jié)點(diǎn)初始化之后，利用K-Means算法對節(jié)點(diǎn)集合進(jìn)行分簇。分簇完成后，每個節(jié)點(diǎn)開始檢測1跳鄰居節(jié)點(diǎn)，并記錄1跳鄰居節(jié)點(diǎn)身份、位置等信息，統(tǒng)計(jì)直接鄰居數(shù)。各節(jié)點(diǎn)根據(jù)自身1跳鄰居數(shù)與1跳鄰居節(jié)點(diǎn)的直接鄰居的數(shù)目進(jìn)行比較，選取1跳鄰居節(jié)點(diǎn)中直接鄰居數(shù)最多的1跳鄰居作為自己的臨時(shí)簇頭，把所有簇頭節(jié)點(diǎn)加入臨時(shí)簇頭集合TH中。

Sensor為非簇頭節(jié)點(diǎn)，按式（5）計(jì)算其連通可靠度，TCH為臨時(shí)簇頭節(jié)點(diǎn)，按式（6）計(jì)算自身的連通可靠度。

式中：CH（i）表示節(jié)點(diǎn)i的簇頭；deg（i，CH（i））表示節(jié)點(diǎn)i連通可靠度，當(dāng)成員節(jié)點(diǎn)與其簇頭在一起時(shí)，deg（i，CH（i））＝0，CPS（vi）＝1。

對于節(jié)點(diǎn)i的分簇C（i），假設(shè)其簇頭為CH（i），臨時(shí)簇頭節(jié)點(diǎn)的連通可靠度為：

其中：NC（Ci）是簇C（i）的成員節(jié)點(diǎn)個數(shù)。

由式（6）可知，如果一個臨時(shí)簇頭節(jié)點(diǎn)的成員節(jié)點(diǎn)數(shù)量少，則連通簇頭的可靠度就低。

由于節(jié)點(diǎn)與分簇質(zhì)心距離越近，節(jié)點(diǎn)通信總代價(jià)越小，并在WSNs中節(jié)點(diǎn)的連通度為6～8時(shí)，網(wǎng)絡(luò)的性能最優(yōu)。因此權(quán)值公式：

式中：w1及w2為權(quán)重因子；dist為臨時(shí)簇頭到聚類質(zhì)心的歐氏距離；deg為簇頭節(jié)點(diǎn)的連通度。從臨時(shí)簇頭集合中選取權(quán)值W最大的節(jié)點(diǎn)作為簇頭。

簇頭節(jié)點(diǎn)不僅可以收集、處理簇內(nèi)成員節(jié)點(diǎn)的感知消息［15］，而且還可以調(diào)節(jié)成員節(jié)點(diǎn)的發(fā)射功率，因此簇頭節(jié)點(diǎn)的負(fù)載和通信量遠(yuǎn)遠(yuǎn)大于簇內(nèi)普通的成員節(jié)點(diǎn)，更容易成為選擇性攻擊破壞的目標(biāo)，故簇頭節(jié)點(diǎn)的故障失效率遠(yuǎn)大于成員節(jié)點(diǎn)。簇頭節(jié)點(diǎn)一旦失效，則感知數(shù)據(jù)也會隨之丟失，會嚴(yán)重影響系統(tǒng)的穩(wěn)定性、可靠性以及抗毀性。為提高WSNs系統(tǒng)抗毀性，提升網(wǎng)絡(luò)性能，在K-Means分簇算法構(gòu)建的分簇網(wǎng)絡(luò)的基礎(chǔ)上，提出了多簇頭機(jī)制，即在每個簇內(nèi)選擇多個簇頭，當(dāng)正在工作的簇頭遭受攻擊或者電池能量不足時(shí)，臨時(shí)簇頭集合中權(quán)值最大的節(jié)點(diǎn)自動升級成為簇頭。

在每個簇內(nèi)維護(hù)一個由K個備份簇頭組成的簇頭集合，系統(tǒng)中的每一個簇當(dāng)前僅有一個簇頭節(jié)點(diǎn)正在工作，當(dāng)前工作的簇頭節(jié)點(diǎn)故障時(shí)，簇內(nèi)成員節(jié)點(diǎn)可以快速地與簇頭集合中的備份簇頭節(jié)點(diǎn)之間建立連接，保證數(shù)據(jù)能夠及時(shí)、準(zhǔn)確地發(fā)送到控制節(jié)點(diǎn)AP，多簇頭機(jī)制模型如圖1所示。

圖1 多簇頭網(wǎng)絡(luò)拓?fù)淠Ｐ褪疽鈭D

多簇頭機(jī)制模型容錯性與抗毀性的提升是通過當(dāng)前工作的每個簇頭節(jié)點(diǎn)維護(hù)著一份簇頭節(jié)點(diǎn)集合路由表實(shí)現(xiàn)的，通過簇頭節(jié)點(diǎn)的冗余增大了各個成員節(jié)點(diǎn)將數(shù)據(jù)通過多跳形式轉(zhuǎn)發(fā)到簇頭節(jié)點(diǎn)的概率。這一方法實(shí)現(xiàn)較為簡單，每個備份簇頭集合根據(jù)簇頭選舉算法的權(quán)值公式重新計(jì)算臨時(shí)簇頭的權(quán)值大小，不過將臨時(shí)簇頭與質(zhì)心節(jié)點(diǎn)之間的距離變?yōu)榕c簇頭之間的距離，選出權(quán)值最大的臨時(shí)簇頭作為備份簇頭，不斷循環(huán)，形成備份簇頭集合。當(dāng)前簇頭由于故障失效時(shí)，備份簇頭則自動轉(zhuǎn)化成簇頭，并在簇內(nèi)進(jìn)行泛洪，這樣就減少了由于簇頭失效進(jìn)行簇頭選舉所使用的時(shí)間，提高了網(wǎng)絡(luò)容錯性能的水平。

2.2 K連通節(jié)點(diǎn)檢測

WSNs系統(tǒng)拓?fù)浣Y(jié)構(gòu)用無向圖G＝（V，E）表示。V為節(jié)點(diǎn)集合，E為傳感器節(jié)點(diǎn)間的通信路徑組成的邊集。若兩傳感器節(jié)點(diǎn)間只有一條通信路徑，則稱該無向圖G是單連通的；若任意兩傳感器節(jié)點(diǎn)間的通信路徑不止一條，則稱該無向圖G是雙連通或多連通，刪除該雙連通或多連通圖中任意一條信息交互邊，該圖的連通性也基本不會發(fā)生改變。

基于簇的層次型網(wǎng)絡(luò)的初始拓?fù)浣Y(jié)構(gòu)并非全是雙連通或者多連通的，提出一種K連通檢測算法，用來查找網(wǎng)絡(luò)中的單連通節(jié)點(diǎn)，即關(guān)鍵節(jié)點(diǎn)，然后通過網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)來調(diào)節(jié)該關(guān)鍵節(jié)點(diǎn)的發(fā)射功率，使其可以與周圍的其他傳感器節(jié)點(diǎn)之間建立通信路徑，不用移動WSNs系統(tǒng)中的任何節(jié)點(diǎn)，即可實(shí)現(xiàn)WSNs系統(tǒng)轉(zhuǎn)化為K連通網(wǎng)絡(luò)，從而保證網(wǎng)絡(luò)不會由于某一傳感器節(jié)點(diǎn)的失效而致使整個WSNs系統(tǒng)拓?fù)浣Y(jié)構(gòu)的割裂，提高系統(tǒng)在不同環(huán)境下的可靠性和抗毀性。

WSNs系統(tǒng)節(jié)點(diǎn)的通信半徑和節(jié)點(diǎn)的部署位置決定了網(wǎng)絡(luò)的初始拓?fù)浣Y(jié)構(gòu)［16］。調(diào)節(jié)節(jié)點(diǎn)的發(fā)射功率，使最終形成的系統(tǒng)拓?fù)浣Y(jié)構(gòu)是K連通的，并在該基礎(chǔ)上，最大化降低WSNs系統(tǒng)中傳感器節(jié)點(diǎn)的通信傳輸損耗，延長WSNs系統(tǒng)的生存周期。

K連通描述的是系統(tǒng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的全局特征，單個傳感器節(jié)點(diǎn)僅擁有其自身及1跳鄰居節(jié)點(diǎn)的拓?fù)湫畔?，因此無法直接確定當(dāng)前系統(tǒng)是否是K連通的。本文中采用了分布式策略，首先采用WSNs系統(tǒng)的經(jīng)典分簇算法［17－18］，將整個網(wǎng)絡(luò)劃分為多個互相不交疊的簇，然后檢測各個簇是否均為K連通。若某些簇不是K連通的，則在系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)改變之前，采取相應(yīng)的措施來將其構(gòu)建成為K連通的簇。

在網(wǎng)絡(luò)分簇及簇頭選舉之后，簇頭節(jié)點(diǎn)通過周期性的泛洪狀態(tài)信息，簇內(nèi)成員節(jié)點(diǎn)收到消息后，通過地理位置路由算法不斷維護(hù)其自身的路由信息表，表1所示為節(jié)點(diǎn)所維護(hù)的路由信息表，其中包含了源節(jié)點(diǎn)、目的節(jié)點(diǎn)、傳輸功率、最大傳輸功率及節(jié)點(diǎn)的刪除指數(shù)。路由信息表包含了節(jié)點(diǎn)通信過程中所需的必要信息，網(wǎng)絡(luò)中所有節(jié)點(diǎn)的路由信息表構(gòu)成了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。節(jié)點(diǎn)的刪除指數(shù)表明了當(dāng)前節(jié)點(diǎn)的連通度以及信息的可靠性，節(jié)點(diǎn)的刪除指數(shù)越大，則意味著節(jié)點(diǎn)所收到的信息越可靠。

表1 路由信息

每個簇頭節(jié)點(diǎn)獲取其所在簇中所有成員節(jié)點(diǎn)的狀態(tài)信息，通過表中的相關(guān)路由信息，判斷當(dāng)前簇是否為K連通。如圖2所示，根據(jù)節(jié)點(diǎn)1的路由狀態(tài)信息表，可知在節(jié)點(diǎn)1所在的簇中，節(jié)點(diǎn)1與簇內(nèi)其他節(jié)點(diǎn)之間至少存在2條信息交互邊，即節(jié)點(diǎn)2和節(jié)點(diǎn)3。但是通過檢測簇內(nèi)所有節(jié)點(diǎn)的狀態(tài)信息表可以發(fā)現(xiàn)，節(jié)點(diǎn)6只有1條與節(jié)點(diǎn)2的信息交互邊，因此可知該簇是單連通的，需要將其構(gòu)建成為K連通網(wǎng)絡(luò)。

圖2 簇拓?fù)鋱D和簇信息表結(jié)構(gòu)框圖

2.3 改進(jìn)多簇頭K連通抗毀拓?fù)錁?gòu)建

考慮到WSNs系統(tǒng)中節(jié)點(diǎn)的移動性差等特點(diǎn)，同時(shí)為了不影響網(wǎng)絡(luò)的初始部署與分配，網(wǎng)絡(luò)經(jīng)過K連通檢測之后，簇頭節(jié)點(diǎn)將需要構(gòu)建K連通的節(jié)點(diǎn)存入消息包內(nèi)，稱這些節(jié)點(diǎn)為關(guān)鍵節(jié)點(diǎn)。然后簇頭發(fā)送泛洪消息，調(diào)節(jié)關(guān)鍵節(jié)點(diǎn)發(fā)射功率，使其與網(wǎng)絡(luò)中其他節(jié)點(diǎn)產(chǎn)生新的信息交互邊，使系統(tǒng)中所有關(guān)鍵節(jié)點(diǎn)逐步成為非關(guān)鍵節(jié)點(diǎn)，從而實(shí)現(xiàn)WSNs系統(tǒng)K連通拓?fù)浣Y(jié)構(gòu)的構(gòu)建。

在系統(tǒng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)已經(jīng)分簇的基礎(chǔ)上，根據(jù)K連通檢測算法，判斷當(dāng)前簇是K連通的，且K＜Kth，采用Harary圖思想［18］，構(gòu)建需要的連通簇。Kth連通簇的構(gòu)建首先需要對網(wǎng)絡(luò)進(jìn)行初始化，進(jìn)行網(wǎng)絡(luò)分簇與多簇頭選舉。簇頭節(jié)點(diǎn)處理成員節(jié)點(diǎn)轉(zhuǎn)發(fā)的消息數(shù)據(jù)包，找出網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)。如果需要構(gòu)建K連通的簇的連通性Kth是偶數(shù)，則將簇中關(guān)鍵節(jié)點(diǎn)與各個方向上與該節(jié)點(diǎn)相鄰的（Kth－1）／2個節(jié)點(diǎn)進(jìn)行相連，得到最終的拓?fù)鋱DGKCth－1，n（GC（K））。若需要構(gòu)建K連通的簇的連通性Kth是奇數(shù)，則將簇中關(guān)鍵成員節(jié)點(diǎn)與各個方向上與該點(diǎn)相鄰的（Kth－1）／2個節(jié)點(diǎn)進(jìn)行相連，得到最終的拓?fù)鋱DGKCth－1，n（GC（K））。Kth連通簇構(gòu)建算法偽代碼如算法2所示。

根據(jù)以上算法，簇頭計(jì)算出簇中每個關(guān)鍵節(jié)點(diǎn)所需的發(fā)射功率，進(jìn)而計(jì)算出節(jié)點(diǎn)所需添加的信息交互邊。若簇頭發(fā)現(xiàn)某些關(guān)鍵節(jié)點(diǎn)的最大發(fā)射功率小于需要的發(fā)射功率，那么簇頭節(jié)點(diǎn)應(yīng)相應(yīng)地增大關(guān)鍵節(jié)點(diǎn)需要連接的節(jié)點(diǎn)的接收功率來建立連接，若還是無法通信，則放棄該節(jié)點(diǎn)。

圖3（a）是基于K-Means聚類算法與簇頭選舉算法后得到的單連通拓?fù)浣Y(jié)構(gòu)。網(wǎng)絡(luò)拓?fù)渲?，通過關(guān)鍵節(jié)點(diǎn)檢測算法可以得到節(jié)點(diǎn)5與節(jié)點(diǎn)7為關(guān)鍵節(jié)點(diǎn)。首先，簇頭節(jié)點(diǎn)收集各簇內(nèi)節(jié)點(diǎn)經(jīng)過地理位置路由泛洪發(fā)送過來的數(shù)據(jù)包，然后檢測出是否有節(jié)點(diǎn)為單連通。若存在，則計(jì)算與其最近的非連通節(jié)點(diǎn)與關(guān)鍵節(jié)點(diǎn)之間的距離，計(jì)算出與非連通節(jié)點(diǎn)進(jìn)行通信所需要的功率。之后在簇內(nèi)發(fā)送泛洪消息，簇內(nèi)節(jié)點(diǎn)接收到數(shù)據(jù)包后，判斷自己是否為目的節(jié)點(diǎn)。若是，則開始增大發(fā)射功率至其可與其他節(jié)點(diǎn)進(jìn)行通信；否則丟棄該數(shù)據(jù)包。以節(jié)點(diǎn)7為例，增大其發(fā)射功率后，其與節(jié)點(diǎn)6與簇頭1之間均建立了信息交互邊。節(jié)點(diǎn)5同理與節(jié)點(diǎn)2之間也建立了信息交互邊。如圖3（b）所示，節(jié)點(diǎn)5和節(jié)點(diǎn)7也不再是關(guān)鍵節(jié)點(diǎn)，從而構(gòu)建出一個K連通拓?fù)浣Y(jié)構(gòu)。

圖3 K連通拓?fù)浣Y(jié)構(gòu)示意圖

采用K-Means聚類算法的分布式策略后，經(jīng)過關(guān)鍵節(jié)點(diǎn)的檢測和關(guān)鍵節(jié)點(diǎn)的功率控制相結(jié)合的分布式算法，使網(wǎng)絡(luò)中的所有的關(guān)鍵節(jié)點(diǎn)轉(zhuǎn)變?yōu)榉顷P(guān)鍵節(jié)點(diǎn)，構(gòu)建出了一個K連通的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從而增強(qiáng)了整個系統(tǒng)的拓?fù)浣Y(jié)構(gòu)的抗毀性和可靠性。

3 算法性能分析

模型中的傳感器節(jié)點(diǎn)隨機(jī)部署在網(wǎng)絡(luò)區(qū)域中，普通傳感器節(jié)點(diǎn)能量受限，但是其功率可調(diào)節(jié)，AP節(jié)點(diǎn)能量無限，其他具體參數(shù)如表2所示。

表2 WSNs系統(tǒng)網(wǎng)絡(luò)參數(shù)

如圖4所示為基于改進(jìn)多簇頭K連通抗毀策略的WSNs系統(tǒng)在仿真后產(chǎn)生的網(wǎng)絡(luò)收發(fā)包的大小曲線。從圖中可以看出：隨著仿真時(shí)間的推進(jìn)，網(wǎng)絡(luò)的收發(fā)包數(shù)量大小已經(jīng)趨于穩(wěn)定，因而可以使用穩(wěn)定階段的網(wǎng)絡(luò)收發(fā)包的數(shù)量大小來計(jì)算網(wǎng)絡(luò)的丟包率。由圖可知，在網(wǎng)絡(luò)仿真運(yùn)行300 s時(shí)，基于改進(jìn)多簇頭K連通WSNs系統(tǒng)抗毀策略構(gòu)建的網(wǎng)絡(luò)發(fā)送數(shù)據(jù)包大小為410 824 bits，接收包大小為374 294 bits，因此可計(jì)算出網(wǎng)絡(luò)的丟包率為8.89%，比基于K-Means算法的普通分簇網(wǎng)絡(luò)的丟包率降低了15.63%?？梢?，就網(wǎng)絡(luò)丟包率來看，改進(jìn)多簇頭K連通WSNs系統(tǒng)具有很好的抗毀性。算法通過節(jié)點(diǎn)連通可靠度選舉多個簇頭，利用K連通檢測算法檢測出關(guān)鍵節(jié)點(diǎn)并調(diào)整其發(fā)射功率，節(jié)約了簇頭節(jié)點(diǎn)失效后網(wǎng)絡(luò)重新進(jìn)行簇頭選舉所耗費(fèi)的時(shí)間，因此網(wǎng)絡(luò)丟包率明顯降低。

圖4 WSNs系統(tǒng)平均收發(fā)包數(shù)量曲線

圖5給出了基于改進(jìn)多簇頭K連通抗毀策略的效果對比。從圖中可以看出：隨著仿真時(shí)間的推進(jìn)，網(wǎng)絡(luò)的端到端時(shí)延已經(jīng)趨于穩(wěn)定，因而可以使用穩(wěn)定階段的網(wǎng)絡(luò)端到端時(shí)延大小來研究網(wǎng)絡(luò)的抗毀性能。由圖可知：在網(wǎng)絡(luò)仿真運(yùn)行300 s時(shí)，基于改進(jìn)多簇頭K連通WSNs系統(tǒng)抗毀策略構(gòu)建的網(wǎng)絡(luò)端到端時(shí)延為9.95 ms，比基于KMeans算法的普通分簇網(wǎng)絡(luò)的端到端時(shí)延降低了20.1%。從網(wǎng)絡(luò)時(shí)延方面來看，改進(jìn)多簇頭K連通WSNs系統(tǒng)也具有較好的抗毀性。算法通過選舉多個簇頭并檢測出關(guān)鍵節(jié)點(diǎn)，調(diào)整其發(fā)射功率，選取最優(yōu)備份簇頭節(jié)點(diǎn)，在簇頭失效后，備份簇頭成為簇頭節(jié)點(diǎn)，簇內(nèi)節(jié)點(diǎn)與新簇頭節(jié)點(diǎn)距離減小，端到端時(shí)延得到降低。

圖5 WSNs系統(tǒng)端到端時(shí)延曲線

4 結(jié)論

針對簇頭節(jié)點(diǎn)隨機(jī)性失效，提出一種改進(jìn)的多簇頭K連通抗毀拓?fù)浣Y(jié)構(gòu)的構(gòu)建方法，通過節(jié)點(diǎn)連通可靠度選舉多個簇頭。當(dāng)簇頭節(jié)點(diǎn)失效時(shí)，臨時(shí)簇頭集合中權(quán)值最大的節(jié)點(diǎn)自動升級成為簇頭，同時(shí)利用K連通檢測算法檢測出關(guān)鍵節(jié)點(diǎn)并調(diào)整其發(fā)射功率實(shí)現(xiàn)K連通拓?fù)錁?gòu)建。

提出的改進(jìn)方法節(jié)約了簇頭節(jié)點(diǎn)失效后網(wǎng)絡(luò)重新進(jìn)行簇頭選舉所耗費(fèi)的時(shí)間以及能量，并且增加了關(guān)鍵節(jié)點(diǎn)與周圍節(jié)點(diǎn)之間的信息交互邊。為節(jié)點(diǎn)失效后網(wǎng)絡(luò)拓?fù)錁?gòu)建提供了一種合理有效的新方法，在提高網(wǎng)絡(luò)抗毀性方面具有實(shí)際應(yīng)用價(jià)值。