基于SEP協議和無線傳感網節點剩余能量的多跳傳輸節能算法的實現

姚萌萌　邵秀麗　任智娟　郭海波

摘 要：針對基于SEP協議實現的傳感器網絡存在簇頭節點過早死亡的現象和遠距離通信網絡傳輸能耗大的弊端。文中設計了一種基于節點剩余能量的多跳傳輸節能算法。該算法把剩余能量高的節點作為簇頭的候選節點，采用多跳樹簇拓撲通信機制，建立簇頭與匯聚節點間的通信鏈路。使用Matlab對算法進行仿真實驗分析，結果表明，該算法減小了用于網絡傳輸的能量開銷，有效延長了網絡的生命周期。

關鍵詞：SEP協議；節能算法；節點剩余能量；多跳樹簇拓撲結構；多跳傳輸

中圖分類號：TP393 文獻標識碼：A 文章編號：2095-1302（2016）08-00-04

0 引 言

一個成熟傳感器網絡有許多傳感器節點，這些傳感器節點進行數據的采集、壓縮、識別、融合等多種處理以滿足用戶的多樣化需求。但傳感器節點體積小、能量有限，大都采用電池供電，需要與匯聚節點通信來上傳采集的數據，且通信耗能比較大。因此，如何降低傳感器網絡中的通信耗能以延長網絡的生命周期是本文的重點。

SEP協議是一種二重異構網絡分簇路由協議[1，2]，它是在LEACH協議的基礎上提出的適應異構網絡的協議[3，4]。異構網絡中節點有兩種，一種是普通節點，另一種是高能量節點。但由于SEP協議在每輪成簇過程中，隨機選擇的簇頭會使能量低的節點當選為簇頭，使節點過早死亡，因此選擇簇頭時，應選擇能量高的節點作為簇頭。簇頭選擇好后，SEP協議建立了簇頭與匯聚節點間的直接通信鏈路，致使遠距離的簇頭節點與匯聚節點的通信能量消耗非常大。如何均衡距離匯聚節點遠近簇頭節點的能量消耗，也決定了傳感器網絡生命周期的長短。

因此，本文基于SEP協議設計了一種基于節點剩余能量的多跳傳輸節能算法。該算法在每輪選擇簇頭時考慮網絡中所有節點的剩余能量，選擇能量高的節點當選為簇頭，以及采用多跳樹簇拓撲結構路由通信機制實現簇頭與匯聚節點的通信，減少了距離匯聚節點較遠的簇頭節點的能量開銷，從而均衡了傳感器網絡中簇頭節點的能耗，延長了網絡的生命周期。

實驗表明，基于改進后的SEP協議設計實現的算法比普通SEP協議算法有更長的生存周期。

1 基于SEP協議動態隨機選擇簇頭和簇頭直接通信的解決方案

在無線傳感器網絡中，由傳感器節點感知區域數據，并將數據傳輸到匯聚節點（Sink），匯聚節點把接收的數據進行處理，從中得到有價值的信息。而傳感器節點與匯聚節點如何通信，本文采用分簇路由通信協議。這種分簇協議在節約能量上更有優勢[5]。分簇的思想是：網絡被劃分為若干個簇（Cluster），每個簇按照一定的選舉機制選舉一個節點作為簇頭（Cluster Head）。每個簇內除了簇頭，其他節點均為成員節點（Cluster Member）。成員節點負責感知區域數據，并將數據傳輸到相近的簇頭，簇頭將數據以自組織的方式傳送到匯聚節點（Sink）。分簇協議以輪為單位，每輪分為簇頭的建立和穩定通信階段。

SEP協議是一種異構無線傳感器網絡的穩定分簇選舉協議。它在節點能量分布不均的情況下，解決了簇頭節點耗能高的問題，但存在以下不足：

（1）在每輪動態成簇的過程中，會隨機產生簇頭，若能量低的節點當選為簇頭，會使某些節點過早死亡，加速第一個死亡節點出現的時間，進而縮短網絡的穩定期；

（2）簇頭向匯聚節點傳輸數據時，采用直接通信方式（如圖1所示的虛線線路），耗能單一，但隨著距離的增大，簇頭節點能耗急劇增加，導致傳感器網絡中節點能耗不均，影響傳感器網絡的穩定性，進而縮短傳感器網絡的生命周期。

針對上述不足，本文提出了如下解決方案：

（1）針對簇頭節點過早死亡的現象，在建立簇頭時，把節點剩余能量列為選擇簇頭的標準，剩余能量高的節點優先被選為簇頭，以避免能量低的節點當選簇頭，使其能量過早耗盡。

（2）針對直接通信的弊端，提出多跳的樹簇拓撲結構通信機制（如圖1所示的實線線路），使傳感器網絡中的簇頭和匯聚節點通信時，盡可能采用多跳方式以節省能量，均衡簇頭節點的能量消耗。

2 基于SEP協議的無線傳感器網絡節點剩余能量多跳傳輸節能算法及其實現過程

本文算法在實現前，需要一個合適的能量模型對算法在傳感器網絡中的能量消耗進行模擬，以驗證算法在延長網絡生命周期中的作用。

2.1 算法的能量模型

在對算法進行實現時，采用第一順序能量模型來模擬傳感器網絡中各個節點的能量消耗[6，7]。該模型把節點能量的消耗分為數據發送耗能、數據融合耗能、數據接收耗能三個部分，以對網絡傳輸中的能耗進行模擬。

本文采用的耗能模型假設：節點A向距離為d的另一節點B傳輸L比特的信息，則A節點發送耗能的計算公式為：

每個簇頭節點融合1 b數據所消耗的能量為EDA。

2.2 基于SEP協議的無線傳感器網絡節點剩余能量多跳傳輸節能算法

由于基于SEP協議實現的傳感器網絡存在節點過早死亡的現象和遠距離通信能耗大的弊端，本文設計的基于節點剩余能量多跳傳輸的節能算法基于SEP協議做了以下兩處改進：

（1）把節點剩余能量列為簇頭選擇的標準；

（2）簇頭和匯聚節點通信時采用多跳樹簇拓撲通信機制。

2.2.1 剩余能量列為選舉簇頭標準

選擇簇頭時要考慮節點的剩余能量[8]，這就需對SEP協議中隨機選擇簇頭的方法做改進，以增加能量高的節點被選為簇頭的概率，避免能量低的節點當選簇頭而出現節點過早死亡的現象[9]。

SEP協議的自適應成簇技術是在簇頭建立階段，傳感器節點生成0～1之間的隨機數rand。如果隨機數小于閾值T（n），則該節點被選為簇頭。在該技術中隨機數rand的生成以及閾值T（n）的計算均與節點剩余能量無關，這樣不利于高能量節點被選為簇頭。可通過減小隨機數rand的值來增大剩余能量高的節點當選為簇頭的概率。

因此，本文考慮將節點剩余能量按照某種函數組織起來，以此對rand加權。該函數要使節點剩余能量更大，rand的權值更小，進而經過權值處理的rand值越小，最終增大剩余能量高的節點當選為簇頭的概率。

由于（1）式為指數函數，在該函數中節點剩余能量越大，指數越小，進而對應的指數函數的值越小。用該權值對rand做處理，會減小rand的值。因此，用該權值對隨機數rand做處理，會增大剩余能量高的節點當選為簇頭的概率。

2.2.2 采用多跳樹簇拓撲結構路由通信機制建立網絡

對于簇頭與匯聚節點的通信方式本文算法采用多跳樹簇拓撲結構路由通信機制[10]，以該方式建立的通信網絡降低了基于SEP協議中簇頭與匯聚節點直接通信對于遠距離簇頭節點的能量消耗，均衡了傳感器網絡中的能耗。

簇頭和匯聚節點的通信方式采用直接通信方式和多跳通信方式所形成的網絡結構，簇頭與匯聚節點通信圖如圖2所示。該圖在一個100×100區域內的傳感器網絡中，網絡被劃分為若干個簇，簇頭和匯聚節點通信。

多跳樹簇拓撲通信機制是由一系列簇頭節點通過單跳或多跳的形式形成的一種樹狀拓撲通信方式。簇頭會選擇距離匯聚節點較近的簇頭作為上級節點進行多跳通信。但不是網絡中所有的簇頭都會進行多跳通信，需要把單個簇頭與上級節點的通信耗能同匯聚節點的直接通信耗能進行比較，若傳輸到上級節點的耗能低則進行多跳通信，反之進行直接通信。所謂的上級節點是距離該簇頭最近且已加入通信鏈路的簇節點。在確定好單個簇頭的通信方式后，網絡中就形成了一條由簇頭到匯聚節點的多跳樹狀拓撲通信鏈路。

2.2.2.1 判斷簇頭節點是否需要進行多跳通信

假設簇頭與匯聚節點的距離為d1，與上級節點的距離為d2，且都大于d0。那么根據傳感器網絡能耗模型，簇頭與匯聚節點（Sink）直接通信對整個網絡消耗的能量為（不需計較匯聚節點接收耗能，只需計算發送耗能+融合耗能）：

2.2.2.2 采用多跳樹簇拓撲結構的具體算法

采用多跳樹簇拓撲結構的具體算法步驟如下所示：

（1）將匯聚節點標記為已加入通信鏈路，并標記為父節點；

（2）選擇距離匯聚節點最近的簇頭節點，加入通信鏈路，同時標記為父節點；

（3）對于每個非父簇頭節點執行如下操作：

①找出距離該簇頭最近的已加入通信鏈路的節點；

②比較該簇頭節點直接與匯聚節點通信所需要消耗的能量和與上級節點通信全網所消耗的能量，即Ec與Eb+Ep做比較，如果Ec>Eb+Ep，則采用多跳通信，在通信時按該節點耗能為Eb、父節點耗能為Ep計算；

③標記該節點為已加入通信鏈路，同時標記為父節點；

④重復直到所有簇頭節點都加入通信鏈路。

2.3 算法的流程描述

本文基于剩余能量多跳傳輸節能算法的程序運行流程圖如圖3所示。

該算法分多次進行迭代，迭代與算法的時間輪對應，每次迭代分兩部分模擬本文算法在傳感器網絡中的耗能過程。

2.3.1 簇頭的產生與各個節點的耗能

簇頭的產生與各個節點的耗能如圖3中的Part1所示。首先設置初始化參數，根據參數和相應公式計算出閾值T（n），并為每個節點生成隨機數rand，然后按照上述規則用剩余能量對rand加權（剩余能量高的權值小）。若加權后的rand小于T（n），則該節點當選為簇頭。其次，成員節點選擇距離最近的簇頭加入。最后按能耗模型模擬網絡中成員節點向簇頭節點傳輸數據的耗能，其中成員節點耗能只考慮發送數據耗能，簇頭節點考慮融合耗能和接收耗能。

2.3.2 簇頭向匯聚節點通信部分

簇頭向匯聚節點通信的部分如圖3中的Part2所示。首先找到距離匯聚節點最近的簇頭節點，加入通信鏈路，然后逐一對每個未加入通信鏈路的簇頭進行處理，找到該簇頭的上級節點（上級節點是距離該點最近的且已加入通信鏈路的簇節點），然后根據能耗模型計算該簇頭和上級節點的通信耗能（Eb+Ep）和直接與匯聚節點的通信耗能（Ec）。若Eb+Ep>Ec，選擇與上級節點通信；若Eb+Ep

3 算法實驗

本次實驗基于Windows系統、Matlab語言進行算法仿真分析。模擬從簇節點的生成，到簇頭通過多跳形式和匯聚節點通信的過程，根據第一順序能耗模型，對各節點按輪進行能量消減，對采用SEP協議算法和本文算法的結果進行對比分析。在執行過程中，每輪簇的劃分、簇頭的產生均動態可視化?？汕逦目吹酱?、簇頭的交替動態變化。

3.1 算法的執行過程分析

該實驗設置的仿真參數為：在100 m×100 m的正方形區域內，隨機部署100個節點，匯聚節點位于（50， 50）處，在整個網絡運行期間，節點和匯聚節點的位置固定；能量消耗參數：Eelec=50×0.000 000 001 J，εfs=10×0.000 000 000 001 J/b/m2，εmp=0.001 5×0.000 000 000 001 J/b/m4；EDA=6×0.000 000 001 J/b/signal；數據包的平均長度為4 000 b；在該異構網絡中高能量節點高于普通節點的能量倍數a=0.5。

對于能量異構無線傳感器網絡，節點的能量初始化分布為兩種類型，普通節點Eo=0.5 J，高能量節點Eo×（1+a）；節點信息以結構化方式存儲，如表1所列。

根據節點坐標來計算節點之間的距離。運用該結構化方式對節點信息進行存儲，以此作為模擬本文算法的基礎。然后采用第一順序能耗模型對網絡在數據傳輸過程中的成員節點向簇頭節點通信、簇頭節點向匯聚節點通信的能量消耗進行模擬。

算法第一輪執行過后，部分節點產生的中間結果如圖4所示。

第二輪結束后，節點19到24均未被選為簇頭，和第一輪結果對比可知未被選為簇頭的節點能量E消耗緩慢。且節點在選擇簇頭時各節點因為坐標不一，所要加入的簇（min_dis_cluster）也不一樣。

中間結果表明本文算法很好地實現了分簇路由通信協議的思想，并且用第一順序能耗模型能很好地模擬網絡中的能量消耗。

3.2 算法的運行結果分析

某一輪的簇劃分與簇頭的選擇過程如圖6所示。

將本文算法與基于SEP協議路由算法進行對比，可明顯看出本文算法的有效性。將剩余能量加入選擇簇頭的標準，讓剩余能量高的節點被選為簇頭的幾率增大，避免了因為能量不足造成節點過早死亡的現象；通過加入多跳樹簇拓撲結構通信機制，使得簇頭到匯聚節點間的通信更具有靈活性，減少了網絡傳輸中的能量開銷，對比結果表明本文算法達到了延長網絡生存周期的目的。

4 結 語

本文通過對穩定異構網絡協議SEP進行分析，發現在大規模傳感器網絡中存在節點過早死亡的現象，以及遠距離數據傳輸能耗大的不足，設計了一種基于節點剩余能量的多跳節能算法。該算法在選取簇頭時，增大了剩余能量高的節點當選為簇頭的概率，并采用多跳樹簇拓撲通信結構的方式，在簇頭和匯聚節點建立了一條多跳樹狀數據傳輸鏈路，有效降低了用于網絡傳輸的能量消耗，延長了網絡的生命周期。

參考文獻

[1] Georgios Smaragdakis，Ibrahim Mata，Azer Bestavros. SEP： A Stable Election Protocol for clustered heterogeneous wireless sensor networks[Z].Computer Science Department Boston University.

[2]楊莉莉.SEP2.0通信協議研究[J].中國新通信，2014（12）：80.

[3]楊永健，賈冰，王杰.無線傳感器網絡中LEACH協議的改進[J].北京郵電大學學報，2013（1）：105-109.

[4]李巖，張曦煌，李彥中.基于LEACH協議的簇頭多跳（LEACH-M）算法[J].計算機工程與設計，2007，28（17）：4158-4160.

[5]沈波，張世永，鐘亦平.無線傳感器網絡分簇路由協議[J].軟件學報，2006，17（7）：1588-1600.

[6]Heinzelman W B，Chandrakasan A P，Balakrishnan H.An Application-specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans. on Wireless Commun.，2002，1（4）：660-667.

[7]張志東，孫雨耕，劉洋，等.無線傳感器網絡能量模型[J]. 天津大學學報，2007，40（9）：1029-1034.

[8]丁男，譚國真，由笛，等.一種基于WSN時變性與節點剩余能量均衡的機會路由算法[J].電子與信息學報，2013，35（3）：715-720.

[9]郭文強，周強，侯勇嚴，等.一種基于無線傳感器網絡分簇路由的改進算法[J].陜西科技大學學報，2013，31（2）：132-135，141.

[10]李小亞，黃道平，吳洪艷.無線傳感器網絡單跳與多跳路由的選擇性[J].計算機工程，2009，35（3）：13-14，53.