孫 偉，吳海青，高 萍

(南京林業(yè)大學 信息科學技術學院，江蘇 南京 210037)

0 引言

在傳統(tǒng)無線傳感器網絡(WSN)中，傳感器節(jié)點通常由電池供電，但電池容量有限，且更換成本高。因此，能源供應不足嚴重限制了WSN的工作時間，是無線傳感器網絡中的一個重要問題[1]。為解決這個問題，在WSN中引入了無線充電技術，采用無線充電技術的傳感器構成了無線可充電傳感器網絡(WRSN)[2]。相比較于利用環(huán)境能量供電，無線充電技術可以持續(xù)有效地提供能量，具有更大的潛能[3]。在WRSN中，移動充電小車可以移動，利用無線充電方式為大量傳感器節(jié)點充電。當移動充電小車以隨機方式運動時，當其運動至不需要充電傳感器節(jié)點旁邊時，此時若繼續(xù)向該傳感器節(jié)點供應能量，會導致傳感器節(jié)點的能量冗余。與此同時，有一些傳感器節(jié)點由于從移動充電車輛獲得的能量較低或無移動充電小車對其供能，不能正常工作。因此，充電小車不合適的運動方式將導致能量浪費和能量的不足同時存在，即能效低下[4]。

由于傳感器節(jié)點分布不均勻，節(jié)點傳輸功耗不是恒定的。此外，移動充電小車隨機且冗長的行駛路徑會導致充電效率降低[5]。這2個問題嚴重降低傳感器網絡的能量效率，從而降低了網絡的生存期。為了提高WRSN的能量效率，許多工作采用了優(yōu)化移動充電小車的充電路徑或將傳感器節(jié)點分簇的方法。

文獻[6]中提出了移動充電小車的充電停留選擇算法。在該算法中，將節(jié)點的平均接收功率定義為適應度函數，通過使用遺傳算法最大化平均接收功率，找到優(yōu)化的充電停留點集合。雖然該算法可以提高充電節(jié)點的利用率，但忽略了節(jié)點能量分布不均勻引起的問題。文獻[7]中提出了基于低功耗自適應集簇分層協議(LEACH)來改進簇頭節(jié)點選擇。但是，該協議忽略了所選簇頭的分布狀態(tài)以及節(jié)點之間的不同通信距離，從而導致了節(jié)點能耗的不均衡。這種能耗不均衡的現象造成能量浪費，使得整個網絡的壽命降低。文獻[8]提出了Revised Earliest Deadline First(REDF)無線充電調度優(yōu)化算法。該算法綜合考慮充電期限和節(jié)點距離2個制約因素，從而延長無線傳感器網絡生命周期，建立一個穩(wěn)定供應能量的無線傳感器網絡，但是該算法不適合大規(guī)模傳感器網絡。

為了克服當前算法的不足，在LEACH算計的基礎上，提出了一種改進的分簇算法。在選擇簇首期間，考慮節(jié)點的剩余能量和相鄰簇首之間的距離，從而可以避免選擇具有較少剩余能量的節(jié)點作為簇首，并且簇頭可以均勻分布。該算法可以延長節(jié)點的生存時間，提高網絡的能量效率。

1 LEACH協議

LEACH協議是無線傳感器網絡一個重要的分簇路由協議[9]，該協議采用LEACH算法，以循環(huán)方式隨機選擇簇頭節(jié)點，并將整個網絡的能量負載均勻分配到每個傳感器節(jié)點，從而提高網絡整體生存時間。與一般的平面多跳路由協議和靜態(tài)分層算法相比，現有結果表明LEACH算法可以有效地延長網絡生命周期。

運行LEACH協議的過程實際上是連續(xù)循環(huán)分簇的過程，每個集群重建可以稱為一輪循環(huán)。一輪循環(huán)分為2個階段：集群建立階段和傳輸數據的穩(wěn)定階段。集群的建立又分為4個階段：簇首節(jié)點的選擇，簇首節(jié)點的廣播，簇首節(jié)點的建立以及調度機制的生成。簇首節(jié)點選擇的選擇策略如下：傳感器節(jié)點隨機生成0到1之間的隨機數，并將其與閾值T(n)進行比較。如果它小于閾值，則選擇節(jié)點作為簇首。T(n)計算為:

(1)

式中，P代表成為簇首節(jié)點的概率，r為當前循環(huán)的輪數，G為在接近1/P輪中未當選簇首的節(jié)點的集合。

2 系統(tǒng)模型

本文考慮的是一個由n個傳感器節(jié)點組成的無線傳感器網絡，如圖1所示，網絡由3部分組成：大量傳感器節(jié)點、移動充電小車和基站?；竞鸵苿映潆娦≤囄挥跈z測區(qū)域外。檢測區(qū)域內有大量的傳感器節(jié)點，主要負責向基站收集、轉發(fā)、存儲和處理數據，傳感器節(jié)點以單跳或多跳的方式將信息發(fā)送到基站。假設每個傳感器節(jié)點具有有限且相同的初始能量，由于每個節(jié)點的業(yè)務負載和能量消耗速率不相同。基站和移動充電小車形成充電系統(tǒng)，主要負責傳感器網絡的能量供應。

圖1 分簇式無線充電技術的系統(tǒng)模型

假設傳感器節(jié)點服從高斯分布[10]，則每個簇里節(jié)點的分布可以用獨立的高斯分布來描述，即簇首節(jié)點的概率密度函數為:

(2)

式中，m為該密度函數的特征矩陣，u為高斯分布的期望值，d為確定節(jié)點分布幅度的參數。期望u的計算公式為:

(3)

式中，Si為簇的區(qū)域面積，N為簇的數量。

3 傳感器節(jié)點分簇算法

為了解決能量冗余，減少節(jié)點能量的不合理損失，提高網絡服務質量，本文在LEACH算法的基礎上，提出了一種適用于無線可充電傳感器網絡的改進分簇算法。該分簇算法選擇簇首的基本原則是：考慮簇首選舉中節(jié)點的剩余能量，盡量選擇具有最大剩余能量的節(jié)點作為簇首節(jié)點；考慮簇首選舉中相鄰簇首之間的距離。算法的簡單介紹如下。

首先，根據節(jié)點的剩余能量，利用LEACH算法選擇剩余能量較多的節(jié)點作為簇首。其次，考慮相鄰簇首之間的距離，如果簇首之間的距離小于由所提出的算法得到的距離閾值D，則簇首節(jié)點分布太密集，進而取消較低能量節(jié)點當選簇首的資格；否則，應適當增加簇首節(jié)點的數量，以確保簇首節(jié)點均勻分布在整個區(qū)域中。最后，簇首節(jié)點將在整個無線通信區(qū)域中廣播，然后其他節(jié)點將通過就近原則加入簇首節(jié)點以形成簇，并通知相應的簇首完成簇建立過程。

簇形成之后，移動充電小車按順序對各簇首進行充電。完成一輪充電后，充電小車返回基站，對自身進行充電。此時，簇內傳感器節(jié)點將收集的數據發(fā)送給簇首節(jié)點。簇首節(jié)點對收集的數據進行數據融合，然后將信息發(fā)送到基站，基站進行數據處理，最后將處理后的數據發(fā)送給用戶。工作一段時間或充電小車完成充電后，網絡開始進行新一輪的分簇。

從上述描述中，可以發(fā)現所設計算法中的2個關鍵是：簇首的選擇和距離閾值D的計算。

3.1 簇首選擇算法

在LEACH算法中，閾值T(n)沒有考慮節(jié)點的剩余能量，因此剩余能量較小的一些節(jié)點也會被選為簇頭，由于簇頭的能量消耗較快，從而會出現簇頭因耗盡導致死亡，進而導致需要開始新一輪簇頭選擇，或由于節(jié)點死亡，網絡無法正常工作。因此，在本文中，簇首的選擇考慮節(jié)點的剩余能量。本文通過閾值的設置來直接濾除剩余能量過低的節(jié)點，閾值定義為:

(4)

式中，Enc為節(jié)點的當前能量，E為初始能量，rs為沒有連續(xù)當選簇首的節(jié)點數量。一旦節(jié)點被選為簇首，則rs被設置為0，并且G是正常節(jié)點，不充當第一輪1/P中的簇首節(jié)點的集合。從式(4)可以看出，在其他參數不變的情況下，在r個循環(huán)后，當節(jié)點的剩余能量較大時，T(n)的值較大，節(jié)點被選為簇首節(jié)點的概率也更大；當節(jié)點的剩余能量越小時，T(n)的值越小，該節(jié)點被選為簇頭首點的概率越小。

3.2 計算簇首之間的距離閾值D

距離閾值用于確定簇首的密度。如果D太小，則大量節(jié)點被選為簇首，這些簇首都需要充電小車來進行充電，可能會導致充電小車的能量不足，一些簇首可能無法及時被充電，從而沒有足夠的能量來為相應簇中的其他節(jié)點進行充電。相反，如果D具有較大的值，則表明相鄰簇首之間的距離較大，即簇首的數量較少。這意味著每個簇內都有較多的傳感器節(jié)點。由于傳感器節(jié)點容量有限，在對每個簇首充電之后，移動充電小車可能仍然有一些能量，這些能量沒有被充分使用。同時，由于簇內傳感器節(jié)點太多，簇首沒有足夠的能量來為這些傳感器節(jié)點充電。為了避免浪費和短缺，分2步來設置閾值D。

首先，通過考慮節(jié)點分布和感應區(qū)域，將簇首間的最優(yōu)距離D定義為:

(5)

式中，Si和Sj為被測節(jié)點的簇區(qū)域，g(xj)和g(xi)為被測節(jié)點的概率密度函數。

利用式(5)計算出的D值，可以獲得簇首的數量，由N1表示。根據移動充電小車的容量和傳感器的電池尺寸，可以計算簇首數量N2：

(6)

式中，Cc為移動充電車的容量，Cs為傳感器的電池尺寸，β為冗余因子，0.5<β<0.9。

如果N1

4 仿真結果

首先，比較了LEACH算法和本文所提出的分簇算法得到的簇首分布情況，如圖2所示，其中黑色圓圈表示簇首節(jié)點，其他表示普通的傳感器節(jié)點。比較圖2(a)和圖2(b)可以發(fā)現，與LEACH算法相比，本文設計的算法使簇首節(jié)點的分布更均勻。原因是所設計的分簇算法考慮了節(jié)點分布的密度和簇首之間的距離，可以避免由于簇首節(jié)點的損壞導致區(qū)域無法正常通信的問題，提高了網絡的穩(wěn)定性。

圖2 節(jié)點分布

其次，比較了3種不同充電算法的網絡剩余能量，結果如圖3所示。在圖3中，“ZC”是指移動充電小車直接對每個節(jié)點充電而沒有運用任何分簇算法，“FCSF”是指使用LEACH算法來選擇簇首節(jié)點，“N-FCSF”代表了本文提出的算法。結果表明，使用ZC充電技術的網絡剩余能量和使用FCSF算法的網絡剩余能量都比使用N-FCSF算法的剩余能量衰減得快。其中，ZC充電技術是網絡剩余能量衰減時間最早的。因為ZC充電技術直接隨機對整個網絡中的每個節(jié)點充電，忽略了節(jié)點的剩余能量，并且由于無法及時充電，可能導致需要充電的節(jié)點過早死亡。另外，由于FCSF算法不對簇首節(jié)點進行篩選，剩余能量較少的節(jié)點當選簇首以后會加速死亡，大大降低了網絡的能量效率。N-FCSF算法通過篩選簇首節(jié)點解決了網絡節(jié)點分布不均勻的現象，有效降低了節(jié)點的能耗，延長了節(jié)點的生存時間，提高了網絡的通信效率。

圖3 剩余能量比較

圖4比較了3種不同充電方法的節(jié)點存活數量。采用ZC充電方式的網絡，節(jié)點從150 s開始死亡，所有節(jié)點在500 s后死亡。這是由于節(jié)點數量大，分布范圍廣，移動充電小車的自身耗能增加，可充電能量降低，充電周期延長，節(jié)點死亡次數增加。FCSF算法的節(jié)點從250 s死亡，所有節(jié)點在600 s后死亡。N-FCSF算法中，節(jié)點從500 s開始死亡，所有節(jié)點在650 s后死亡。這種結果表明N-FCSF算法延長了節(jié)點的生存時間，延長了網絡的生命周期。原因是N-FCSF算法使簇首節(jié)點均勻分布，避免了每個節(jié)點與簇首之間距離引起的大量能量損失，并考慮了簇首節(jié)點選舉時節(jié)點的剩余能量，避免了低剩余能量的節(jié)點作為簇首，提高了能量的效率。

圖4 節(jié)點存活數量的比較

5 結束語

節(jié)點能量有限以及節(jié)點能耗的不平衡會導致“節(jié)點能量冗余”和“節(jié)點因能量耗盡而死亡”在網絡中共存，為解決該問題，本文提出了一種適用于可充電傳感器網絡的分簇算法，該算法考慮了節(jié)點剩余能量和簇首之間的距離，充分地利用了移動充電小車的能量，改善了網絡中能量的分布不平衡問題，提高了整個網絡的能效，有效地延長了節(jié)點的生存時間和網絡的生存期。