負載均衡的異構傳感器網絡分簇路由算法研究

樊思煒

摘 要：有限的能量資源是無線傳感器網絡（WSNs）廣泛應用的主要限制之一。為了最大化整個網絡的生存時間，需要優化無線傳感器網絡中節點的能量消耗。協議使用的無線傳感器網絡模型包含兩種節點：普通節點和能量較高的高級節點。算法中綜合考慮了節點當前剩余能量、網絡中平均能量、簇頭到基站的距離和節點類型等因素，設計了一種適合于異構無線傳感器網絡路由協議（HCEEC）。在該協議中，基站在對應的區域中選擇能量更大、更加靠近基站的節點作為簇頭來搜集本區域內的信息，簇頭節點對本簇內的信息進行融合之后發送至基站節點。實驗表明，該算法能夠更好地綜合網絡中能量的負載、提高網絡吞吐量和延長網絡生存時間。

關鍵詞：異構網絡；無線傳感器網絡；分簇路由算法

DOIDOI：10.11907/rjdk.171308

中圖分類號：TP312

文獻標識碼：A 文章編號文章編號：1672-7800（2017）008-0063-04

0 引言

無線傳感器網絡（WSNs）是由大量傳感器節點和一個或者很少的基站（BS）通過自組網方式構成的無線網絡[1]。這些傳感器節點不僅具備傳感能力、計算能力，同時還能夠實現數據傳輸功能。然而傳感器節點通常由干電池供電，其能源具有應用局限性。研究表明，太陽能和風能等可再生能源可以被應用在WSN中，為傳感器節點提供能源[2-3 ] 。然而，這些可再生能源自身的間歇性會引起網絡中節點能源供應的不持續性，進而影響WSNs的性能[4] 。因此，WSN 的研究與部署中，傳感器節點的能耗問題仍值得重點關注。

WSNs根據初始節點的狀態是否相同分為同構網和異構網，能量異構是最普遍的網絡異構現象，即節點的初始能量不同。早期研究傳感器網絡主要是針對同構傳感器網絡，即假定網絡中所有節點初始化能量相同且均為同一類型，研究的節點類型比較單一[5]。這種簡化忽略了節點間差異可能給網絡及其協議帶來的影響。而在實際應用中，經常會在傳感器群中混合異構節點，比如部分節點沒有使用自身攜帶的電源而是直接使用建筑環境內或者是周圍環境中的交流電源或者是其它種類的電源[6]，在野外環境還有可能使用太陽能作為傳感器節點的電源。因此，在WSNs中異構性也是路由算法研究中需要考慮的一個重要因素[7]。

1 研究現狀

相比于同構傳感器網絡，異構傳感器網絡更貼近現實應用場景，尤其是能量異構的傳感器網絡路由協議是目前研究的重點課題之一[8]。本文主要介紹幾種能量異構的傳感器網絡分簇路由算法。

SEP[9]由LEACH[10]算法發展而來，是針對二級能量異構傳感器網絡提出的路由算法。網絡中有兩種類型的節點：高級節點和普通節點。SEP基于節點的能量初始值為高級節點和普通節點設置了不同的加權概率，使得高級節點成為簇頭（CH）的概率更大，這樣確保了兩種節點的生存時間一致，既保證了負載均衡，又延長了網絡的穩定期。但SEP的簇首選擇過程依賴隨機數，簇首數目波動較大卻可以保證均勻。簇首選擇未考慮當前剩余能量水平，這些都會影響分簇的效果和網絡的性能及生命周期。簇頭直接傳送數據到基站，這樣當簇頭遠離基站時會消耗大量的能量。DEEC[11] 是一種基于LEACH的適用于多級能量異構網絡的分布式高能效分簇式路由算法。DEEC的簇首選舉概率值綜合考慮節點當前的剩余能量和網絡當前平均剩余能量，使得簇首的選舉能夠自適應節點剩余能量的變化，以最大化延長網絡的穩定期。每個節點按照其剩余能量的不同將第r 輪的簇首選舉閾值設置為pi=（Ei（r）/E（r）×popt，這樣保證網絡在每個選舉周期內的平均簇首個數為N×popt。DEEC使用一個求近似解的估計方案估計了整個網絡的全局能量水平，計算出在第r輪中網絡節點的平均能量，這在一定程度上削弱了DEEC的實用性。TDEEC[12]算法是對DEEC算法的改進，其對閾值進行調整：在閾值中加入節點剩余能量和網絡平均剩余能量的比值，盡量讓當前剩余能量多的節點優先成為簇首，且加入了一個最優簇首。針對于異構的WSNs，人們提出了SEP、DEEC和TDEEC等路由算法。但是這些路由算法并沒有提出相應的網絡分布方案。這種情況下，具有較高能量的節點（高級節點）在網絡中的分布不均勻。另外，在之前的方案中，每個節點都需要計算自己成為簇頭的概率，這無疑增加了簇中節點的計算開銷。另外，上述文獻中沒有討論網絡中最佳節點個數。

2 分布式異構網絡模型

本文使用的WSNs模型中，假設N個節點隨機均勻地分布在M×M監控區域，其中包含普通節點和高級節點。高級節點的個數是普通節點的m倍，普通節點的初始能量設定為E0 ，高級節點的能量比普通節點多出倍，基站節點設定在網絡的頂層。整個網絡中節點的分布如圖1所示。

網絡中節點的總個數N=Nn+mNn，其中，Nn 代表普通節點的數目。在無線傳感器異構網之中，普通節點和高級節點的總能量分別為：

En=Nn×E0（1）

Ea=mNn×（E0×（1+））（2）

網絡中節點的總能量為：

Et=Nn×E0+mNn×（E0×（1+））（3）

假設網絡中的節點具有以下特征：所有節點部署之后不再移動；節點均勻分布在區域中；每一個普通節點的一跳范圍內有一個或多個高級節點；所有節點實現通信；整個網絡中能量異構，節點能夠調整發射頻率；節點能夠獲取自己的位置信息；基站知道節點初始能量。

3 HCEEC算法

HCEEC算法主要包括兩個過程：簇的建立過程和通信過程。HCEEC算法使用初始能量、節點剩余能量、節點類型和節點與基站的距離4個因素判斷最佳簇頭的選擇。在網絡中節點通信階段，分析網絡中簇頭節點和每一輪中能量的消耗情況。

3.1 網絡形成階段endprint

WSNs中高效的簇結構在提高網絡的生存時間方面有著至關重要的作用。在HCEEC的網絡形成階段，基站使用集中控制算法（Central Control Algorithm）選擇簇頭。最初，基站通過網絡中節點的初始能量計算區域中的平均能量。在此之后，網絡中節點在每輪結束之前，向基站報告當前的剩余能量信息。

設ni表示si 個普通節點所對應的簇頭節點個數。在同構網絡中，ni的值為ni=poptN。popt為優化簇首比例，即簇頭節點在網絡的節點總數中所占比例，即：

popt=koptN（4）

其中，kopt是網絡中最優簇頭個數，其可以通過計算得出[13]。

kopt=N2πεfsεmpMd2toBS（5）

在LEACH協議中，網絡中的每一個節點si（i=1，2，3…N）輪流成為簇頭，ni=1/popt。但是，由于網絡中節點通信的過程中節點之間距離不同，因而消耗的能量不同，網絡中節點的剩余能量也不相同。如果在異構網絡中為所有節點設置相同的成簇概率值，則網絡中能源的消耗不能進行很好的均衡，能量較低的節點會比能量較高的節點更快死亡。在HCEEC算法中，根據節點si在第r 輪的剩余能量Ei（r） 選擇不同的popt值。

令pi=1/ni ，可以將pi看作是在ni中成為簇頭的平均概率。在某一輪中，如果網絡中節點的能量相同，pi的值可以選擇為popt，這種情況下，可以保證每一輪中簇頭節點的個數為popt×N，并且所有節點在同一時間死亡。如果節點擁有的能量不同，則能量較高節點的pi值應該大于能量較小節點的pi值。定義E（r） 表示在第r輪時網絡中節點的平均能量。

E（r）=1N∑Ni=1Ei（r）（6）

基站節點將每個節點的當前能量和平均能量作比較，能量高于平均能量的節點被選作預選簇頭（Excepted Clutering Heads ECHs）。基站繼續對ECHs進行檢查，因為基站在每一輪中只選擇pi×N個簇頭。ECHs中剩余能量最高同時距離基站節點最短的節點會有更大的機會成為最終簇頭節點。節點到簇頭的距離可以通過式（7）進行計算：

DtoBS（i）=（XBS-xi）2+（YBS-yi）2（7）

其中，DtoBS是第j 個ECHs到基站的距離，X 和Y 分別表示基站節點的橫坐標和縱坐標。xj 和yj 是相應第j個ECHs的坐標值。由于同一種類型節點具有相同的初始能量，節點的當前能量能夠通過節點的能量消耗率表示出來，當前輪之前節點能量的消耗率為：

Ri=E0/（E0-Ei（r））（8）

其中，E0 代表節點的初始能量，Ei（r） 為節點剩余能量。基站計算出每個ECHs節點成為簇頭的概率為：

pi=Ei（r）Ri×DtoBS（i）=Ei（r）（E0-Ei（r））E0×DtoBS（i）（9）

由于高級節點具有更多的能量，因此，在選擇簇頭時，應該將節點類型同時考慮進去，不同的節點在選擇簇頭時擁有不同的權重。

pnrm=pi1+m，padv=pi（1+）1+m。（10）

將式（9）分別帶入式（10）可得高級節點和普通節點相應成為最終簇頭的概率為：

pi=Ei（r）（E0-Ei（r））E0×DtoBS（i）（1+m） if Si is the normal nodeEi（r）（E0-Ei（r））（1+）E0×DtoBS（i）（1+m） if Si is the advanced node（11）

因此，節點成為簇頭的可能性直接取決于節點剩余能量、節點能量消耗速率、節點類型以及節點到基站的距離。如果ECHs的個數和網絡區域中所需節點個數相等，那么所有的備選節點都將被選作最終簇頭節點（Finally Selected Cluster-Heads FSCHs）。因此，網絡中節點的能量得到了均衡，網絡的生存時間得到了延長。

基站向網絡中廣播FSCHs信息。FSCHs接收到自己成為最終簇頭的消息之后向周邊節點廣播自己成為簇頭的消息。周邊節點接收到一個或者多個簇頭節點的成為簇頭的消息，非簇頭節點選擇一個相應區域且信號強度最高的簇頭作為數據轉發的下一跳節點。對應的簇頭為簇內節點分配TDMA時間間隙，非簇頭節點在相應的時間間隙向簇頭節點性地發送消息。如果有非簇頭節點沒有收到FSCHs節點發送的成為簇頭的消息 ，則他自己選擇自己作為簇頭。在HCEEC算法中，網絡建立階段的時間遠遠小于網絡的通信時間。

3.2 網絡通信階段

在HCEEC協議算法的通信階段。網絡中的非簇頭節點在實際環境中通過感知獲取周圍環境數據，然后傳遞給相應的簇頭節點。簇頭節點接收到數據后對數據進行壓縮，去掉無用信息之后，將數據傳遞給基站。簇頭節點對數據進行壓縮，減少了數據的長度，降低了節點能量的消耗，延長了網絡生存周期。節點在傳輸數據的過程中，會消耗大量的能量。采用文獻[11]所使用的能量模型，節點l 個bit的數據發送到d 的過程中，整個能量的消耗模型如下：

ETx（l，d）=lEelec+lεfsd2 d

其中，Eelec是接收器或者發射器處理一個比特數據所消耗的能量。lεfsd2和lεmpd4是根據發送器的放大器的信號放大所消耗的能量。簇頭向基站傳遞數據的方式分為兩種：直接交付或者多跳傳遞。由式（12）可知，當數據的傳輸距離大于某一閾值d0 時，傳輸所需要的能量會大大增加，因此規定，在CH上傳數據的過程中，如果基站和簇頭的距離在d0之內，則通過直接交付的方式將數據傳輸給基站，否則，簇頭選擇通信范圍內距離基站較近、能量較高的備選簇頭作為下一跳數據傳輸的節點，通過多跳的方式將數據傳送到基站。

如果每一個非簇頭節點在每一輪中向簇頭節點發送L 個字節的數據，則每一輪網絡中消耗的所有能量為：

Eround=L（2NEelec+NEDA+kεmpd4toBS+Nεfsd2toCH）（13）

其中，k 表示網絡中簇的個數，EDA表示在簇頭中數據融合所消耗的能量，dtoBS 代表簇頭節點到基站節點的平均距離，dtoCH表示簇頭節點和簇內節點之間的平均距離。

4 仿真實驗

將本文提出的HCEEC在ns2環境下進行仿真實驗。100個節點均勻分布在100m×100M的無線傳感網絡中，假設基站的位置處在監控區域中心位置（50×50）。實驗中使用表1中的參數，使用本路由協議和LEACH、SEP、E-SEP和DEEC算法進行了實驗比較。圖2（a）顯示了隨著時間的推移，網絡中存活節點的情況，實驗結果表明，HCEEC算法較其它路由協議在均衡網絡中節點能量方面有突出表現，網絡的生存時間最長。HCEEC中網絡穩定期的時間，比LEACH，SEP、E-SEP、和DEEC分別高出了120%、70%、55%和48%。算法穩定期的增加，得益于算法中使用基站對分區中的分布進行計算，減少了節點中的計算和相互通信，節省了大量能量。圖2（b）是網絡中死亡節點數目情況。同樣，HCEEC在最小化死亡節點方面同樣優于其余的路由算法。

5 結語

本文提出了基于異構無線傳感網絡的能量高效的路由協議。在網絡中，有兩種包含不同初始能量的節點：普通節點和高級節點。兩類節點均勻分布在監控區域中。基站節點位于監控區域中央，負責網絡中簇結構的構建和網絡中數據的收集。在網絡構建過程中，綜合考慮了節點剩余能量、節點類型、節點到基站距離以及網絡中平均剩余能量等因素，選擇最佳簇頭。通信過程中，設置距離閾值d0 ，處在基站d0之內的簇頭節點通過直接交付的方式將數據傳遞給基站，否則，簇頭節點選擇能量最高且距離基站最近的節點作為中繼節點，通過多跳的方式將數據傳輸到基站。實驗表明，本文提出的HCEEC算法，相比于LEACH、SEP、E-SEP等算法都有很大的優越性。

參考文獻：

[1] YADAV S，YADAV RS.A review on energy efficient protocols in wireless sensor networks[J].Wireless Networks，2016，22（1）：335-350.

[2] LI Y，SHI R.An intelligent solar energy-harvesting system for wireless sensor networks[J].Wireless Communications and Networking on EURASIP Journal，2015（1）：1-12.

[3] ZHANG B，SIMON R，AYDIN H.Harvesting-aware energy management for time-critical wireless sensor networks with joint voltage and modulation scaling[C].IEEE Trans.on Industrial Informatics，2013，9（1）：514-526.

[4] MEKKI K，ZOUINKHI A，DERIGENT W，et al.USEE：a uniform data dissemination and energy efficient protocol for communicating materials[J].Future Generation Computer Systems，2016，56（3）：651-663.

[5] MOORE M R，SMITH S F，LEE K.The next step：wireless IEEE 1451 smart sensor networks[J].Sensors Mag，2001，18（9）：35-43.

[6] MUNIR E U，ASLAM M，SHAH T，et al.An advanced heterogeneity-aware centralized energy efficient clustering routing protocol for wireless sensor networks[C].IEEE 2014 International Green Computing Conference （IGCC），2014：1-10.

[7] JAVAID N，RASHEED M B，IMRAN M，et al.An energy-efficient distributed clustering algorithm for heterogeneous WSNs[J].EURASIP Journal on Wireless Communications and Networking，2015，2015（1）：1-11.

[8] YADAV S，YADAV RS.A review on energy efficient protocols in wireless sensor networks[J].Wireless Networks，2016，22（1）：335-350.

[9] G SMARAGDAKIS，I MATTA，A BESTAVROS.SEP：a stable election protocol for clustered heterogeneous wireless sensor networks[C].Proc.SANPA，2004.

[10] HEINZELMAN W R， CHANDRAKASAN A， BALAKRISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C].Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000.

[11] QING L，ZHU Q，WANG M.Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks[J].Computer communications，2006，29（12）：2230-2237.

[12] SAINI P，SHARMA A K.Energy efficient scheme for clustering protocol prolonging the lifetime of heterogeneous wireless sensor networks[J].International Journal of Computer Applications，2010，6（2）：1-5.endprint