簇規模約束與簇頭最優化選擇的WSN聚類協議

王義勇, 汪 毅

(1.浙江經濟職業技術學院 數字信息技術學院，浙江 杭州 310018； 2.華中農業大學 信息學院，湖北 武漢 430070)

0 引 言

在無線傳感器網絡(wireless sensor network，WSN)[1-3]中，傳感器節點通常采用自身攜帶的電池供電，且電池不易更換或者充電，因此傳感器節點的能量是有限的。如果傳感器的能量耗盡，則該傳感器節點將會失效，導致傳感器網絡的拓撲結構變化。傳感器節點失效越多，傳感器網絡癱瘓越快。因此，需要研究傳感器節能技術，延長無線傳感器網絡生存時間[4-6]。對于無線傳感器網絡而言，其能耗主要來源于傳感器節點的無線通信模塊。為了降低傳感器節點的通信能耗，通常采用的技術手段是設計分簇路由協議，將網絡中的節點聚類成若干個節點簇，每一個簇選擇一個簇頭，由簇頭節點收集簇中其它節點的信息，與基站進行通信交互，這樣簇中其它節點大部分時間可以關閉無線通信模塊，從而降低了這些節點的能耗，總體上降低了網絡的能耗，延長了網絡的生存時間[7-14]。學者們[12]針對這些問題提出了許多有意義的改進聚類協議，如文獻[13]提出了一種聚類區域自適應調整的聚類協議，主要改進在于引入了節點的剩余能量參量，選擇剩余能量大的節點作為簇頭節點，避免簇頭節點過早失效。文獻[14]類似，也是通過引入能量參量來均衡節點能耗。然而，這類聚類協議仍然采用隨機方式建立節點簇，存在節點簇規模差異大的問題，而且選擇簇頭時沒有考慮節點是否可信，容易因為數據轉發失敗率高而過多消耗能量。針對這些問題，本文在文獻[13]所述聚類協議的基礎上，提出一種簇規模約束與簇頭最優化選擇的聚類協議，主要思想是在節點簇建立階段引入規模約束，通過固定閾值法創建規模基本一致的節點簇。同時在簇頭選擇時引入節點的信任度參量，并依據最優化理論設計簇頭節點選擇的目標函數，選擇最優的節點作為簇頭節點。另外還增加簇頭節點回收步驟，對剩余能量和信任度低于設定閾值的簇頭節點進行回收，避免節點過早失效，目標是解決現有聚類協議存在的簇頭分布不均勻、負載不均衡、網絡生存時間短的問題。

1 本文聚類協議

本文為了解決現有聚類協議在無線傳感器網絡(WSN)應用中存在的簇頭分布不均勻、負載不均衡、網絡生存時間短的問題，提出一種簇規模約束與簇頭最優化選擇的聚類協議。本文所述聚類協議主要包括3個階段，分別是節點簇劃分、簇頭節點選擇和簇頭節點回收。由基站監測簇頭節點能量和信任度，當簇頭節點能量下降到能量閾值之下，或者簇頭節點的信任度下降到信任度閾值之下時，回收該簇頭節點。在介紹本文協議之前，首先給出無線傳感器網絡的通用假設條件：

(1)無線傳感器網絡中存在一個基站，且基站的能量是無限的；

(2)無線傳感器網絡中傳感器節點是固定的且初始能量相同；

(3)無線傳感器網絡中每個節點都知道其位置信息；

(4)無線傳感器網絡中每個節點都可以作為簇頭或簇成員；

(5)簇成員節點可以直接將數據包轉發給簇頭節點；

(6)簇頭節點可以通過其它簇頭節點將數據轉發到基站。

1.1 節點簇劃分

對于無線傳感器網絡的節點聚類而言，如果聚類簇過小，會導致簇數量過大，引起網絡擁堵，進而增加通信開銷。如果聚類簇過大，會導致簇頭節點的通信任務過大，從而增加網絡的能量消耗。文獻[12,13]所述的聚類協議采用隨機聚類的方式劃分節點簇，容易導致節點簇的規模差異大，引發節點簇之間負載不均衡、能量消耗大的問題。因此，本文在建立簇時對簇的規模進行約束，按照空間分布構建規模近似的節點簇。具體思路是：引入一個固定閾值N，在建立節點簇時，任選一個節點，以半徑R畫一個圓，如果圓內節點的數量不小于N，則將該圓內的節點作為一個節點簇。否則，增加圓的半徑，直至圓內節點的數量不小于N。節點簇構建的偽代碼見表1。其中，閾值N、初始半徑R0和半徑步長△R是事先設置的參數，具體在實驗部分討論。按照表1的節點簇創建流程，依次對網絡中的節點進行劃分，每一次劃分都得到一個節點簇，然后對剩余的節點集合繼續進行劃分，直到網絡中的所有節點都分配到節點簇中。也可以規定節點簇數量，如果劃分的節點簇數量與規定的節點簇數量不一致，則重新開始節點簇劃分過程，利用初始節點選擇的隨機性更新節點簇，直至節點簇數量達到規定數量。本文在隨機劃分節點簇的基礎上引入規模約束，對于均衡網絡負載很有意義。

表1 節點簇構建偽代碼

1.2 簇頭節點選擇

簇頭的選擇是一個最優化過程，需要從節點簇的所有節點中選擇一個最適合的節點來擔任簇頭，選擇的依據需根據網絡的任務而定。考慮到簇頭需要擔負簇成員節點與基站之間的通信橋梁任務，簇頭節點的通信遠比簇成員節點頻繁。文獻[12]采用輪轉法選擇簇頭，節點擔任簇頭的頻率越低，越有機會被選為簇頭，這樣節點可以輪流擔任簇頭，維護通信過程中的能量均衡。該方法定義了一個門限函數，為

(1)

在每一輪選擇時，各個節點隨機產生一個隨機數，與門限函數進行比較，如果小于門限函數，則被選為簇頭節點。

該聚類協議采用隨機方式選擇簇頭，容易出現簇頭分布不均勻的現象，導致節點簇規模差異大，進而導致不同節點簇之間負載不均勻的現象。而且該聚類協議沒有考慮節點的剩余能量，可能出現簇頭節點剩余能量不足的現象，導致節點存活時間短，進而導致網絡拓撲結構變化，引起網絡能耗不均衡現象和降低網絡的生存時間。

為了解決文獻[12]所述聚類協議的不足，文獻[12,13]的基礎上，引入了能量參量，在選擇簇頭時除了要考慮節點擔任簇頭的頻率之外，還需要考慮節點的剩余能量，因為簇頭所需要消耗的能量遠大于簇成員節點。因此文獻[13]選擇剩余能量最多的節點作為簇頭。文獻[12,13]中的門限函數進行改進，為

(2)

然而，文獻[13]所述聚類協議選擇的簇頭仍然具有隨機性，導致節點簇的規模差異大，引發負載不均勻現象。而且文獻[12,13]在選擇簇頭時都沒有考慮節點是否可信。然而，簇頭節點需要管理簇成員節點的所有通信活動，因此簇頭節點必須是值得信任的節點，這樣可以提高數據轉發的成功率，降低簇頭節點的能耗。基于這一思想，本文在文獻[13]所述聚類協議的基礎上，引入節點的信任度參量，作為簇頭選擇的依據，目標是選擇最值得信賴的節點作為簇頭。另外，本文在上一小節提出了規模約束的節點簇劃分方法，可以解決節點簇規模差異大的問題。由于本文在選擇簇頭時節點簇是已經劃分好的，因此不需要像文獻[12,13]那樣，設計一個門限函數，將每輪選擇中小于門限函數的所有節點都作為簇頭。本文將簇頭的選擇看作一個最優化過程，融合前述的簇頭選擇策略和節點信任度度量，構建一個簇頭選擇目標函數，在每一個節點簇中，選擇一個使得目標函數達到最大值的節點作為簇頭節點。下面首先介紹信任度的計算方法，然后給出目標函數的表達方式。

信任度通常是基于節點轉發數據包的行為計算的。在無線傳感器網絡中，節點在接收數據包之后會將數據包轉發給其它節點，由于網絡中可能存在惡意節點或者失效節點，此類節點在轉發數據包時經常會出現丟包現象。丟包現象越頻繁，節點的信任度越低。因此可以基于數據包轉發頻率來計算節點的信任度參量。

對于節點簇中任意節點p，其鄰居節點集合記為pii=1,2,…,Np，Np為鄰居節點集合中的元素數量，也即節點p的鄰居節點數量。在時間段Δt(本文Δt=60 s)內，監聽節點p是否轉發來自鄰居節點pi的數據包。假設，Mp,pi表示的是，在時間段Δt內，該鄰居節點pi發送給節點p的數據包的數量，Np,pi是在時間段Δt內節點p成功轉發的來自鄰居節點pi的數據包數量，于是節點p對鄰居節點pi的數據包轉發頻率可以表示為

(3)

數據包轉發頻率fp,pi越大，說明鄰居節點pi選擇節點p為其轉發數據的可靠性越強。因此，本文采用數據包轉發頻率構建節點的信任度參量。對于節點簇而言，節點p的信任度由其對所有鄰居節點的數據包轉發頻率的平均值來表示，為

(4)

信任度vp越大，說明節點p對節點簇中所有鄰居節點的數據包轉發頻率越高，這樣該節點作為簇頭節點可以更可靠地管理簇成員節點的通信活動。

為了兼顧節點的信任度、剩余能量以及節點作為簇頭的比例，本文設計的簇頭選擇的目標函數為

(5)

簇頭節點選擇算法的偽代碼見表2。

表2 簇頭節點選擇偽代碼

按照表2的簇頭節點選擇流程，選出每一個簇的簇頭節點，由基站進行聲明。

1.3 簇頭節點回收

由于簇頭節點需要管理簇成員節點的所有通信活動，因此簇頭節點的能量消耗非常大。簇頭節點必須有足夠的能量才能有效地執行其所有任務。為了避免簇頭節點因能量消耗過大而失效，本文制定簇頭節點回收策略，對剩余能量過小的簇頭節點進行回收。同時，考慮到數據傳輸的可靠性，對信任度過小的簇頭節點也需要進行回收。簇頭節點回收的偽代碼見表3。其中，Emin和vmin分別表示能量閾值和信任度閾值。在本文中，這兩個閾值取經驗值，分別為Emin=0.3Einit、vmin=0.3。

表3 簇頭節點回收偽代碼

本文通過對簇頭節點進行回收，可以避免單個節點過載而提前失效，均衡網絡中節點的能量消耗。同時防止惡意節點攻擊，提高數據轉發成功率，降低節點能耗。

2 仿真實驗與分析

為了便于對比，本文參考文獻[13]的實驗環境設計仿真實驗，仿真參數見表4。其中，仿真計算機平臺性能為Intel I7 CPU、DDR3 16 G RAM，軟件平臺為Matlab 2012。

對于文獻[12,13]所述聚類協議，簇頭數目比例設置為5%，與文獻[13]設置一樣。對于本文而言，節點簇的劃分方式采用規模約束方式，相應的參數有閾值N、初始半徑R0和半徑步長△R，為了偏于對比，盡可能使得本文構建的節點簇數量與文獻[12,13]得到的節點簇數量一致，因此本文設置參數N=18、R0=30、△R=1。按照該組參數劃分節點簇，得到的節點簇數量為5，與文獻[12,13]得到的節點簇數量相同。

表4 仿真實驗相關參數

與文獻[13]一樣，本文從負載均衡度、節點生存時間和網絡能量3個分析進行分析，對比文獻[12,13]和本文所述聚類協議的性能差異，詳細描述如下。

2.1 負載均衡度分析

圖1給出了3種聚類協議得到的節點簇中的節點數量分布，可見，本文構建的5個節點簇的規模基本一致，最大節點數量為22，最小節點數量為19。文獻[12]構建的5個節點簇的規模差異最大，最大節點數量為64，最小節點數量為4。文獻[13]構建的5個節點簇的最大節點數量為26，最小節點數量為16。因此，本文聚類協議選擇的簇頭的負載分布最均衡。

圖1 負載均衡度對比

2.2 節點生存時間分析

圖2展示了3種聚類協議下網絡中節點的生成時間對比情況，文獻[12]聚類協議在第220 s開始出現節點失效現象，文獻[13]聚類協議在第310 s開始出現節點失效現象，本文聚類協議在第340 s開始出現節點失效現象，與文獻[12,13]所述聚類協議相比，本文聚類協議的節點失效時間分別推遲了55%和10%，這說明本文聚類協議可以有效延長節點的生存時間。另外，從圖中可以看出，文獻[12,13]和本文聚類協議的節點全部失效時間分別是580 s、690 s和760 s，很明顯本文聚類協議驗證了網絡的生存時間。究其原因，主要是因為本文聚類協議劃分的節點簇的規模基本一致，能耗更均衡。本文聚類協議通過簇頭節點回收，避免簇頭節點過早失效，進而也延長了網絡的生存時間。

圖2 節點生存時間對比

2.3 網絡能量分析

圖3展示了3種聚類協議的網絡能耗對比情況。其中，網絡中100個節點的初始能量共計150 J。隨著時間的增長，網絡能耗不斷增大，文獻[12]聚類協議在580 s時耗盡全部能量，文獻[13]聚類協議在690 s時耗盡全部能量，而本文聚類協議在760 s時耗盡網絡能量。可見，本文聚類協議的能耗最低，而且，本文聚類協議的能耗曲線相對而言更加平緩，說明本文聚類協議的能耗更均衡，可以更高效利用網絡能量，延長網絡生存時間。

圖3 網絡能耗對比

3 結束語

本文對文獻[12,13]的聚類協議進行改進，主要改進包括：①在節點簇建立階段，在隨機選擇的基礎上采用固定閾值法對節點簇規模進行約束，保證建立的簇規模基本一致，均衡簇頭節點的負載；②在簇頭節點選擇階段，除了考慮節點的剩余能量和節點作為簇頭的比例之外，還兼顧節點的信任度，減少數據轉發失敗造成的能量消耗，同時采用最優化理論，設計簇頭節點選擇目標函數來代替門限函數，選擇最優的簇頭；③在簇頭節點回收階段，對剩余能量和信任度低于閾值的簇頭節點進行回收，避免簇頭節點過早失效，延長網絡生存時間。仿真實驗結果表明，與文獻[12,13]的聚類協議相比，改進的聚類協議的簇頭分布更均勻，負載更均衡，網絡生存時間更長，而且網絡能量消耗也更慢。