王義勇, 汪 毅

(1.浙江經(jīng)濟職業(yè)技術學院 數(shù)字信息技術學院，浙江 杭州 310018； 2.華中農(nóng)業(yè)大學 信息學院，湖北 武漢 430070)

0 引 言

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

1 本文聚類協(xié)議

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

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

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

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

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

(5)簇成員節(jié)點可以直接將數(shù)據(jù)包轉發(fā)給簇頭節(jié)點；

(6)簇頭節(jié)點可以通過其它簇頭節(jié)點將數(shù)據(jù)轉發(fā)到基站。

1.1 節(jié)點簇劃分

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

表1 節(jié)點簇構建偽代碼

1.2 簇頭節(jié)點選擇

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

(1)

在每一輪選擇時，各個節(jié)點隨機產(chǎn)生一個隨機數(shù)，與門限函數(shù)進行比較，如果小于門限函數(shù)，則被選為簇頭節(jié)點。

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

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

(2)

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

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

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

(3)

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

(4)

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

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

(5)

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

表2 簇頭節(jié)點選擇偽代碼

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

1.3 簇頭節(jié)點回收

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

表3 簇頭節(jié)點回收偽代碼

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

2 仿真實驗與分析

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

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

表4 仿真實驗相關參數(shù)

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

2.1 負載均衡度分析

圖1給出了3種聚類協(xié)議得到的節(jié)點簇中的節(jié)點數(shù)量分布，可見，本文構建的5個節(jié)點簇的規(guī)?；疽恢拢畲蠊?jié)點數(shù)量為22，最小節(jié)點數(shù)量為19。文獻[12]構建的5個節(jié)點簇的規(guī)模差異最大，最大節(jié)點數(shù)量為64，最小節(jié)點數(shù)量為4。文獻[13]構建的5個節(jié)點簇的最大節(jié)點數(shù)量為26，最小節(jié)點數(shù)量為16。因此，本文聚類協(xié)議選擇的簇頭的負載分布最均衡。

圖1 負載均衡度對比

2.2 節(jié)點生存時間分析

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

圖2 節(jié)點生存時間對比

2.3 網(wǎng)絡能量分析

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

圖3 網(wǎng)絡能耗對比

3 結束語

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