基于多簇頭K連通的抗毀拓撲構建方法

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

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

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

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

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

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

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

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

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

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

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

引入以下相關定義與假設：

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

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

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

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

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

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

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

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

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

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

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

輸入：網(wǎng)絡相關參數(shù)

do k-means；

do選取臨時簇頭；

do選舉簇頭；

if簇頭失效

then臨時簇頭升級為簇頭；

end if

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

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

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

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

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

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

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

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

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

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

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

圖1 多簇頭網(wǎng)絡拓撲模型示意圖

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

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

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

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

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

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

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

表1 路由信息

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

圖2 簇拓撲圖和簇信息表結(jié)構框圖

2.3 改進多簇頭K連通抗毀拓撲構建

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

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

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

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

圖3 K連通拓撲結(jié)構示意圖

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

3 算法性能分析

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

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

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

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

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

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

4 結(jié)論

針對簇頭節(jié)點隨機性失效，提出一種改進的多簇頭K連通抗毀拓撲結(jié)構的構建方法，通過節(jié)點連通可靠度選舉多個簇頭。當簇頭節(jié)點失效時，臨時簇頭集合中權值最大的節(jié)點自動升級成為簇頭，同時利用K連通檢測算法檢測出關鍵節(jié)點并調(diào)整其發(fā)射功率實現(xiàn)K連通拓撲構建。

提出的改進方法節(jié)約了簇頭節(jié)點失效后網(wǎng)絡重新進行簇頭選舉所耗費的時間以及能量，并且增加了關鍵節(jié)點與周圍節(jié)點之間的信息交互邊。為節(jié)點失效后網(wǎng)絡拓撲構建提供了一種合理有效的新方法，在提高網(wǎng)絡抗毀性方面具有實際應用價值。