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

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

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

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

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

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

1 系統抗毀性模型

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

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

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

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

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

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

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

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

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

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

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

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

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

2 改進多簇頭K連通網絡抗毀算法

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

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

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

輸入：網絡相關參數

do k-means；

do選取臨時簇頭；

do選舉簇頭；

if簇頭失效

then臨時簇頭升級為簇頭；

end if

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

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

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

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

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

其中：NC（Ci）是簇C（i）的成員節點個數。

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

由于節點與分簇質心距離越近，節點通信總代價越小，并在WSNs中節點的連通度為6～8時，網絡的性能最優。因此權值公式：

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

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

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

圖1 多簇頭網絡拓撲模型示意圖

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

2.2 K連通節點檢測

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

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

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

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

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

表1 路由信息

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

圖2 簇拓撲圖和簇信息表結構框圖

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

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

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

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

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

圖3 K連通拓撲結構示意圖

采用K-Means聚類算法的分布式策略后，經過關鍵節點的檢測和關鍵節點的功率控制相結合的分布式算法，使網絡中的所有的關鍵節點轉變為非關鍵節點，構建出了一個K連通的網絡拓撲結構，從而增強了整個系統的拓撲結構的抗毀性和可靠性。

3 算法性能分析

模型中的傳感器節點隨機部署在網絡區域中，普通傳感器節點能量受限，但是其功率可調節，AP節點能量無限，其他具體參數如表2所示。

表2 WSNs系統網絡參數

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

圖4 WSNs系統平均收發包數量曲線

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

圖5 WSNs系統端到端時延曲線

4 結論

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

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