胡 栗

（昆明理工大學信息工程與自動化學院 云南省人工智能重點實驗室 云南省計算機技術應用重點實驗室）

無線傳感器網(wǎng)絡 （Wireless Sensor Network，WSN）是由多個傳感器節(jié)點無規(guī)律散落在某個空間內(nèi)，實現(xiàn)信息交互功能的網(wǎng)絡體系。 節(jié)點之間在一定的條件下實現(xiàn)數(shù)據(jù)轉(zhuǎn)發(fā)，最終將數(shù)據(jù)傳送到基站，完成整個網(wǎng)絡的通信工作。 在各個傳感器節(jié)點通信［1］過程中，節(jié)點能耗問題必須關注，節(jié)點電池能量是有限的，而且往往被安放在一些復雜空間中，導致電池不易更換［2］，一旦電池能量耗盡，就不能繼續(xù)執(zhí)行傳遞數(shù)據(jù)信息的任務，相當于該節(jié)點“死亡”，若多個節(jié)點“死亡”，網(wǎng)絡不再連通，最終致使整個無線傳感器網(wǎng)絡“癱瘓”。 因此，節(jié)點的能耗問題是無線傳感器網(wǎng)絡生命周期的關鍵限制條件， 在保證網(wǎng)絡連通的前提下，減少節(jié)點能耗、延長整個網(wǎng)絡的生命周期成為無線傳感器網(wǎng)絡研究的熱點。

節(jié)點之間采用分簇路由的方式優(yōu)化節(jié)點能耗是目前最有效的途徑之一。 經(jīng)典分簇算法低能耗自適應聚類層次協(xié)議 （Low Energy Adaptive Clustering Hierarchy，LEACH）雖然能起到一定的效果，但也存在不足：每個節(jié)點都有某種可能成為或者不成為簇頭，但每輪重復選舉的過程會導致能量浪費；簇頭節(jié)點到基站的距離不同，距離較遠的簇頭節(jié)點由于經(jīng)過的路徑相對較長，因此會過多使用能量而導致自身“死亡”，致使整個網(wǎng)絡處于分區(qū)不連通狀態(tài)； 在選舉簇頭節(jié)點過程中，約束條件少之又少，因此很難選出符合條件的簇頭節(jié)點完成網(wǎng)絡間的信息交互過程。

針對上述問題， 胡源等提出非均勻分簇算法，把整個空間劃分成不同區(qū)域，在簇頭節(jié)點的選擇上提出采用與距離相關的通信代價評估函數(shù)選擇最優(yōu)簇頭［3］；劉衛(wèi)等提出LEACH-C算法，該算法修正了LEACH原先的閾值計算方法，使用兩種控制因子作為簇頭選擇約束條件，同時節(jié)點間的距離可以隨情況改變［4］；戴劍勇等提出基于改進螢火蟲優(yōu)化神經(jīng)網(wǎng)絡的WSNs分簇路由協(xié)議，使用螢火蟲智能優(yōu)化算法和權(quán)重因子平衡簇內(nèi)、簇間的通信距離，采用BP神經(jīng)網(wǎng)絡優(yōu)化簇頭選舉和數(shù)據(jù)傳輸路徑［5］；甄巖等提出分布式能量均衡的WSN動態(tài)數(shù)據(jù)轉(zhuǎn)發(fā)策略， 根據(jù)節(jié)點自身的能量、位置和相關因素構(gòu)建層次結(jié)構(gòu)，并根據(jù)節(jié)點的通信開銷等選擇中繼節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)［6］。

針對以上提出的分簇路由算法、簇頭節(jié)點選舉與數(shù)據(jù)傳輸階段，考慮因素都不夠全面、不能很好地優(yōu)化節(jié)點能耗的問題，筆者提出基于多因子與雙簇頭的LEACH優(yōu)化算法，完成網(wǎng)絡節(jié)點間的通信。

1 網(wǎng)絡和能耗模型

1.1 WSN數(shù)學網(wǎng)絡模型

WSN數(shù)學網(wǎng)絡模型類似于圖論中圖的數(shù)據(jù)結(jié)構(gòu)，無線傳感器網(wǎng)絡是多個傳感器節(jié)點隨機散落在監(jiān)控區(qū)域，節(jié)點與節(jié)點之間構(gòu)成相互連通的鏈路，因此可以用無向賦權(quán)圖Gw表示：

1.2 WSN節(jié)點能耗模型

WSN節(jié)點間數(shù)據(jù)處理與傳輸過程的能耗遠多于其他應用能耗，因此筆者根據(jù)文獻［6］中的一階無線電能耗模型進行說明，分為發(fā)送數(shù)據(jù)和接收數(shù)據(jù)兩個階段。

發(fā)送節(jié)點能耗ETX（k，d）的計算式為：

為了簡化問題，只考慮同一簇群內(nèi)的數(shù)據(jù)融合問題，其中節(jié)點數(shù)據(jù)融合的能耗Ec的計算式為：

其中，ni是簇群內(nèi)所有節(jié)點的數(shù)量；EDA是每比特數(shù)據(jù)融合的能耗。

由式（1）～（3）可以看出，在數(shù)據(jù)長度相同的情況下，傳感器節(jié)點的能耗主要是由節(jié)點間的傳輸距離、鄰居節(jié)點的數(shù)量等因素決定的。

2 基于多因子與雙簇頭的LEACH優(yōu)化算法

上述提出的各種分簇算法都沒有較好地優(yōu)化節(jié)點能耗，單個簇頭節(jié)點承擔數(shù)據(jù)轉(zhuǎn)發(fā)的壓力過大， 數(shù)據(jù)傳輸過程中缺乏良好的數(shù)據(jù)轉(zhuǎn)發(fā)路徑， 不能很好地解決節(jié)點能量消耗問題。 而且LEACH算法僅有較少的約束條件，在延長網(wǎng)絡生命周期的過程中存在一定缺陷。

為此， 筆者提出基于多因子與雙簇頭的LEACH優(yōu)化算法，其基本原理是：首先提出一種新的簇頭評估閾值函數(shù)，通過加入距離控制因子和輪次能耗因子判斷節(jié)點能否成為簇頭節(jié)點；其次設置成簇評估函數(shù)判斷簇頭所在簇群能否成簇，同時設置副簇頭節(jié)點均衡簇頭節(jié)點數(shù)據(jù)轉(zhuǎn)發(fā)的能耗壓力，降低簇頭節(jié)點能耗；最后在數(shù)據(jù)傳輸過程中通過加入權(quán)重因子綜合選擇中繼節(jié)點，采用多跳方式轉(zhuǎn)發(fā)數(shù)據(jù)到基站。

2.1 簇頭選舉

經(jīng)典LEACH算法中，任一節(jié)點都有相同的可能性成為簇頭節(jié)點， 節(jié)點會產(chǎn)生一個0～1范圍內(nèi)的隨機值，若該值小于閾值函數(shù)T，就采用洪泛方式使其余節(jié)點都知道“我”已經(jīng)是簇頭，該輪應該放棄當選。 每次都以同樣的方式選舉簇頭，使得能量消耗的代價隨之增加，又因為約束條件少之又少， 導致很難選出符合條件的簇頭， 因此LEACH算法存在一定的缺陷。

筆者提出的簇頭評估閾值函數(shù)T的表達式為：

其中，p是節(jié)點成為簇頭的概率；r為選舉次數(shù)；QSCH（i）為簇頭評估函數(shù)，該函數(shù)與節(jié)點間的距離、節(jié)點運行多輪之后使用的能量情況以及通信半徑范圍內(nèi)節(jié)點的個數(shù)有關。 將節(jié)點此刻的值與閾值T進行比較，若大于閾值T，即為簇頭。

由于簇頭節(jié)點要轉(zhuǎn)發(fā)大量數(shù)據(jù)，節(jié)點自身能量使用程度要大于普通成員節(jié)點，節(jié)點的剩余能量固然重要，但是究其根源，節(jié)點運行多輪后消耗的能量也是不容忽視的直接因素，通常選舉簇頭都會考慮節(jié)點的剩余能量，但是之前消耗的能量不只是數(shù)據(jù)傳輸?shù)哪芰?，還包括每輪節(jié)點向鄰居節(jié)點廣播自身信息所消耗的能量，以及換簇過程中控制信息消耗的能量等。 因此，筆者提出輪次能耗因子， 用以衡量節(jié)點運行多輪消耗的能量， 同時考慮到節(jié)點在與鄰居節(jié)點通信過程中，節(jié)點間的距離也會影響節(jié)點能量的消耗量，因此提出將距離控制因子作為評估函數(shù)的一部分，由于簇頭是針對整個網(wǎng)絡的，考慮到全局性，簇頭的評估標準還依賴網(wǎng)絡中未失效的節(jié)點個數(shù)。

綜上，簇頭評估函數(shù)QSCH（i）的表達式如下：

2.2 成簇及副簇頭選舉

在簇頭節(jié)點選舉完成之后，各簇頭節(jié)點周圍的節(jié)點根據(jù)自己與簇頭節(jié)點的距離進入相應的簇群內(nèi)。 因為簇頭的選舉是針對整個網(wǎng)絡而言的，考慮到全局性，根據(jù)節(jié)點自身的剩余能量和節(jié)點與基站的距離， 構(gòu)造的成簇評估函數(shù)QSBC如下：

將簇頭節(jié)點的剩余能量與整個網(wǎng)絡中節(jié)點間的距離的比值作為評估值， 選擇QSBC值較大的簇頭節(jié)點成簇。

由于簇頭節(jié)點既要接收簇內(nèi)普通節(jié)點成員發(fā)來的數(shù)據(jù)， 又要進行簇間數(shù)據(jù)傳輸與基站通信，因此在數(shù)據(jù)接收與轉(zhuǎn)發(fā)的過程中，能量消耗顯著增加。 針對這個問題，提出用副簇頭節(jié)點均衡簇頭節(jié)點的能耗， 當簇群中選出副簇頭后，由于默認副簇頭與基站的距離比簇頭節(jié)點近，因此簇頭節(jié)點先將數(shù)據(jù)傳遞給副簇頭節(jié)點，再一步步傳遞給基站，進而降低傳輸能耗。 副簇頭節(jié)點只針對單個簇群而言，僅考慮節(jié)點的局部性，依賴于節(jié)點的鄰居節(jié)點的能量和節(jié)點間的距離。 設α與β都是屬于［0，1］的均衡調(diào)節(jié)因子，則構(gòu)造的副簇頭評估函數(shù)Pach如下：

在簇頭選舉與成簇的過程中，綜合考慮節(jié)點與其通信半徑內(nèi)所有節(jié)點的平均距離和最大距離，同時考慮節(jié)點的輪次消耗能量和節(jié)點的剩余能量，既考慮節(jié)點的局部性又考慮整個簇群。 針對簇頭存在過大數(shù)據(jù)轉(zhuǎn)發(fā)壓力的情況，設置副簇頭節(jié)點來均衡簇頭的能耗，達到了有效優(yōu)化網(wǎng)絡節(jié)點能耗的目的。

2.3 數(shù)據(jù)傳輸

數(shù)據(jù)傳輸分為簇內(nèi)傳輸和簇間傳輸。 簇內(nèi)傳輸是指單個簇群內(nèi)，普通節(jié)點成員與簇頭節(jié)點之間的信息交互。 簇間傳輸是指在簇頭節(jié)點完成簇內(nèi)傳輸后，通過多跳將數(shù)據(jù)傳遞給基站。 但是由于網(wǎng)絡節(jié)點的分布是隨機的，所以簇頭與基站的距離不一，距離基站的遠近程度可以衡量數(shù)據(jù)轉(zhuǎn)發(fā)路徑的長短，若到基站距離較短則選擇一跳傳遞數(shù)據(jù)，反之則選擇過渡點作為數(shù)據(jù)的承上啟下節(jié)點（即中繼節(jié)點），使得路徑滿足多跳的條件，將數(shù)據(jù)傳遞給基站。

要構(gòu)建最優(yōu)傳輸路徑，中繼節(jié)點的選擇受多種條件的約束，同時考慮到簇群規(guī)模越小，簇內(nèi)數(shù)據(jù)傳遞越少，簇頭在數(shù)據(jù)處理過程中消耗的能量就越小。 筆者考慮多種限制條件：簇頭節(jié)點與基站間的距離、簇群規(guī)模和簇頭節(jié)點自身剩余能量，進而構(gòu)造路徑權(quán)重因子，作為判斷中繼節(jié)點構(gòu)造最優(yōu)傳輸路徑的標準。 路徑權(quán)重因子ω的表達式如下：

ω越小，表示簇頭節(jié)點間的距離越小，簇群規(guī)模較小，且簇頭節(jié)點剩余能量越高，更適合作為中繼節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)。

3 算法步驟

基于多因子與雙簇頭的LEACH優(yōu)化算法的步驟如下：

a. 計算節(jié)點的輪次能耗因子、集中度和距離控制因子，構(gòu)造新的簇頭評估閾值函數(shù)；

b. 根據(jù)新的簇頭評估閾值函數(shù)判斷是否可以成為簇頭；

c. 選舉簇頭完成后， 構(gòu)造成簇評估函數(shù)，普通節(jié)點自行進入到某個簇中， 成為簇內(nèi)成員節(jié)點；

d. 在簇群內(nèi)設置副簇頭節(jié)點均衡簇頭的數(shù)據(jù)轉(zhuǎn)發(fā)能耗；

e. 在數(shù)據(jù)轉(zhuǎn)發(fā)階段根據(jù)多種因子綜合選擇中繼節(jié)點，形成最優(yōu)傳輸路徑，將數(shù)據(jù)傳遞給基站。

4 仿真模擬

仿真模擬在Matlab 2019a平臺進行， 本試驗模擬100個傳感器節(jié)點安置于200 m×200 m的區(qū)域中，基站默認在空間最右邊。 通過加入多種控制因子， 優(yōu)化簇頭選舉成簇和數(shù)據(jù)傳輸， 對節(jié)點的剩余能量以及運行的輪數(shù)通過多種算法進行仿真。 該試驗將LEACH 算法、LEACH-C算法和筆者算法在節(jié)點存活數(shù)和剩余能量比值兩個方面進行分析對比， 以證明筆者算法的優(yōu)越性。

WSN參數(shù)設置如下：

節(jié)點分布區(qū)域 200 m×200 m

數(shù)據(jù)融合能耗Ec50 nJ/bit

節(jié)點初始能量Emax1 J

節(jié)點的通信半徑R 30 m

WSN中節(jié)點的簇內(nèi)傳輸是指單個簇群內(nèi)，普通節(jié)點成員與簇頭節(jié)點間的信息交互。 簇間傳輸是指簇頭節(jié)點完成簇內(nèi)傳輸后，通過多跳最后將數(shù)據(jù)傳遞給基站。 由于與基站的距離不同，導致能耗不同，因此為了分擔簇頭進行數(shù)據(jù)轉(zhuǎn)發(fā)的能耗壓力，設置副簇頭節(jié)點，默認副簇頭節(jié)點的位置更靠近基站， 距離相對較近。 通過在200 m×200 m的空間內(nèi)隨機布設100個傳感器節(jié)點，節(jié)點仿真分簇，每個簇群的簇頭節(jié)點和副簇頭節(jié)點分布情況如圖1所示。

圖1 簇頭成簇示意圖

在無線傳感器網(wǎng)絡中，節(jié)點能耗均衡度是判斷該網(wǎng)絡保持網(wǎng)絡數(shù)據(jù)通信時長的一個重要標準，通常情況下，運行一定輪數(shù)后，節(jié)點的剩余能量和網(wǎng)絡中存活的節(jié)點數(shù)可以作為網(wǎng)絡連通持久的參考依據(jù)。 現(xiàn)通過比較LEACH算法、LEACHC算法和筆者算法在輪數(shù)一定的情況下， 節(jié)點的最小剩余能量和平均剩余能量的比值以及存活節(jié)點數(shù)進行分析。

3種算法節(jié)點最小剩余能量和平均剩余能量的比值趨勢如圖2所示， 當節(jié)點運行600輪時，LEACH算法節(jié)點剩余能量比值為0.75，LEACH-C算法為0.83，筆者算法為0.86；當節(jié)點運行1 100輪時，LEACH算法節(jié)點剩余能量比值為0.0，LEACHC算法為0.5，筆者算法為0.7；當節(jié)點運行1 400輪時，LEACH算法和LEACH-C算法節(jié)點剩余能量比值均為0.00，而筆者算法為0.55。 由此可以看出，當LEACH 算法失效時， 節(jié)點能量耗盡，而LEACH-C算法和筆者算法的節(jié)點最小剩余能量和平均剩余能量比值較大， 能耗相對更為均衡；當LEACH-C算法失效時，節(jié)點能量耗盡，而筆者算法節(jié)點的最小剩余能量和平均剩余能量比值較大， 能耗相對更為均衡。 仿真試驗結(jié)果表明， 當運行輪數(shù)一定時， 節(jié)點的剩余能量比值可以有效地衡量網(wǎng)絡能耗情況， 隨著輪數(shù)的增加， 節(jié)點最小剩余能量和平均剩余能量的比值在減小， 從各個算法比值的坡度趨勢來看，在相同輪數(shù)情況下， 該比值越大， 各節(jié)點能量差距越小，能耗越均衡。 因此，從3種算法的節(jié)點剩余能量比值差距程度來看， 筆者算法在加入雙簇頭和多重控制因子后， 有效地均衡了節(jié)點能耗， 延續(xù)了節(jié)點運行的輪數(shù)， 延長了網(wǎng)絡節(jié)點的生命周期。

圖2 3種算法節(jié)點最小剩余能量和平均剩余能量比值趨勢

3種算法存活節(jié)點個數(shù)的趨勢如圖3所示，節(jié)點運行到1 100輪時，LEACH算法存活節(jié)點的個數(shù)開始減少；當節(jié)點運行到1 400輪時，LEACH-C算法存活節(jié)點的個數(shù)開始減少，而筆者算法存活節(jié)點的個數(shù)還未減少，說明筆者算法能夠有效延長網(wǎng)絡生命周期； 當節(jié)點運行到2 500 輪時，LEACH算法存活節(jié)點的個數(shù)為0個，LEACH-C算法的也為0個， 而筆者算法存活節(jié)點的個數(shù)雖然減少，但仍然有大量存活節(jié)點，說明筆者算法相對而言能夠運行更多輪數(shù)；當節(jié)點運行到3 100輪時，3種算法存活節(jié)點的個數(shù)均為0。 試驗表明，在輪數(shù)一定的情況下，存活節(jié)點的個數(shù)越多，即表明網(wǎng)絡中剩余可用節(jié)點的數(shù)量越多，可以繼續(xù)進行網(wǎng)絡信息交互，在能量有限的情況下節(jié)點能運行更多輪數(shù)。 隨著運行輪數(shù)的不斷增加，節(jié)點能量隨之減少， 監(jiān)測區(qū)中的節(jié)點剩余數(shù)會隨之減少。 當運行輪數(shù)一定時，網(wǎng)絡中節(jié)點的存活個數(shù)作為決定該網(wǎng)絡是否可以繼續(xù)使用的條件，即判斷網(wǎng)絡生命周期的另一個重要標準。 說明筆者算法相比于LEACH算法和LEACH-C算法，對網(wǎng)絡生命周期的延長效果有明顯提升。

圖3 3種算法存活節(jié)點個數(shù)趨勢

5 結(jié)束語

在無線傳感器網(wǎng)絡節(jié)點通信時，均衡節(jié)點能耗和延長網(wǎng)絡生命周期是當前研究領域的重點。筆者提出的基于多因子與雙簇頭的LEACH優(yōu)化算法， 通過設置雙簇頭節(jié)點均衡簇頭節(jié)點的能耗， 在考慮剩余能量的同時考慮輪次消耗能量，設置距離控制因子和輪次能耗因子，數(shù)據(jù)傳輸過程加入路徑權(quán)重因子選擇中繼節(jié)點構(gòu)造最優(yōu)傳輸路徑。 仿真試驗證明了筆者方法的優(yōu)越性。 但是在輪次能耗因子的計算上增加了復雜度，而且在網(wǎng)絡分簇過程中會存在某些節(jié)點不屬于任意簇的情況，造成了節(jié)點資源的浪費，優(yōu)化解決這些問題是下一步的研究方向。