基于SEP協(xié)議和無線傳感網(wǎng)節(jié)點剩余能量的多跳傳輸節(jié)能算法的實現(xiàn)

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

摘 要：針對基于SEP協(xié)議實現(xiàn)的傳感器網(wǎng)絡(luò)存在簇頭節(jié)點過早死亡的現(xiàn)象和遠(yuǎn)距離通信網(wǎng)絡(luò)傳輸能耗大的弊端。文中設(shè)計了一種基于節(jié)點剩余能量的多跳傳輸節(jié)能算法。該算法把剩余能量高的節(jié)點作為簇頭的候選節(jié)點，采用多跳樹簇拓?fù)渫ㄐ艡C制，建立簇頭與匯聚節(jié)點間的通信鏈路。使用Matlab對算法進行仿真實驗分析，結(jié)果表明，該算法減小了用于網(wǎng)絡(luò)傳輸?shù)哪芰块_銷，有效延長了網(wǎng)絡(luò)的生命周期。

關(guān)鍵詞：SEP協(xié)議；節(jié)能算法；節(jié)點剩余能量；多跳樹簇拓?fù)浣Y(jié)構(gòu)；多跳傳輸

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

0 引 言

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

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

因此，本文基于SEP協(xié)議設(shè)計了一種基于節(jié)點剩余能量的多跳傳輸節(jié)能算法。該算法在每輪選擇簇頭時考慮網(wǎng)絡(luò)中所有節(jié)點的剩余能量，選擇能量高的節(jié)點當(dāng)選為簇頭，以及采用多跳樹簇拓?fù)浣Y(jié)構(gòu)路由通信機制實現(xiàn)簇頭與匯聚節(jié)點的通信，減少了距離匯聚節(jié)點較遠(yuǎn)的簇頭節(jié)點的能量開銷，從而均衡了傳感器網(wǎng)絡(luò)中簇頭節(jié)點的能耗，延長了網(wǎng)絡(luò)的生命周期。

實驗表明，基于改進后的SEP協(xié)議設(shè)計實現(xiàn)的算法比普通SEP協(xié)議算法有更長的生存周期。

1 基于SEP協(xié)議動態(tài)隨機選擇簇頭和簇頭直接通信的解決方案

在無線傳感器網(wǎng)絡(luò)中，由傳感器節(jié)點感知區(qū)域數(shù)據(jù)，并將數(shù)據(jù)傳輸?shù)絽R聚節(jié)點（Sink），匯聚節(jié)點把接收的數(shù)據(jù)進行處理，從中得到有價值的信息。而傳感器節(jié)點與匯聚節(jié)點如何通信，本文采用分簇路由通信協(xié)議。這種分簇協(xié)議在節(jié)約能量上更有優(yōu)勢[5]。分簇的思想是：網(wǎng)絡(luò)被劃分為若干個簇（Cluster），每個簇按照一定的選舉機制選舉一個節(jié)點作為簇頭（Cluster Head）。每個簇內(nèi)除了簇頭，其他節(jié)點均為成員節(jié)點（Cluster Member）。成員節(jié)點負(fù)責(zé)感知區(qū)域數(shù)據(jù)，并將數(shù)據(jù)傳輸?shù)较嘟拇仡^，簇頭將數(shù)據(jù)以自組織的方式傳送到匯聚節(jié)點（Sink）。分簇協(xié)議以輪為單位，每輪分為簇頭的建立和穩(wěn)定通信階段。

SEP協(xié)議是一種異構(gòu)無線傳感器網(wǎng)絡(luò)的穩(wěn)定分簇選舉協(xié)議。它在節(jié)點能量分布不均的情況下，解決了簇頭節(jié)點耗能高的問題，但存在以下不足：

（1）在每輪動態(tài)成簇的過程中，會隨機產(chǎn)生簇頭，若能量低的節(jié)點當(dāng)選為簇頭，會使某些節(jié)點過早死亡，加速第一個死亡節(jié)點出現(xiàn)的時間，進而縮短網(wǎng)絡(luò)的穩(wěn)定期；

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

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

（1）針對簇頭節(jié)點過早死亡的現(xiàn)象，在建立簇頭時，把節(jié)點剩余能量列為選擇簇頭的標(biāo)準(zhǔn)，剩余能量高的節(jié)點優(yōu)先被選為簇頭，以避免能量低的節(jié)點當(dāng)選簇頭，使其能量過早耗盡。

（2）針對直接通信的弊端，提出多跳的樹簇拓?fù)浣Y(jié)構(gòu)通信機制（如圖1所示的實線線路），使傳感器網(wǎng)絡(luò)中的簇頭和匯聚節(jié)點通信時，盡可能采用多跳方式以節(jié)省能量，均衡簇頭節(jié)點的能量消耗。

2 基于SEP協(xié)議的無線傳感器網(wǎng)絡(luò)節(jié)點剩余能量多跳傳輸節(jié)能算法及其實現(xiàn)過程

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

2.1 算法的能量模型

在對算法進行實現(xiàn)時，采用第一順序能量模型來模擬傳感器網(wǎng)絡(luò)中各個節(jié)點的能量消耗[6，7]。該模型把節(jié)點能量的消耗分為數(shù)據(jù)發(fā)送耗能、數(shù)據(jù)融合耗能、數(shù)據(jù)接收耗能三個部分，以對網(wǎng)絡(luò)傳輸中的能耗進行模擬。

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

每個簇頭節(jié)點融合1 b數(shù)據(jù)所消耗的能量為EDA。

2.2 基于SEP協(xié)議的無線傳感器網(wǎng)絡(luò)節(jié)點剩余能量多跳傳輸節(jié)能算法

由于基于SEP協(xié)議實現(xiàn)的傳感器網(wǎng)絡(luò)存在節(jié)點過早死亡的現(xiàn)象和遠(yuǎn)距離通信能耗大的弊端，本文設(shè)計的基于節(jié)點剩余能量多跳傳輸?shù)墓?jié)能算法基于SEP協(xié)議做了以下兩處改進：

（1）把節(jié)點剩余能量列為簇頭選擇的標(biāo)準(zhǔn)；

（2）簇頭和匯聚節(jié)點通信時采用多跳樹簇拓?fù)渫ㄐ艡C制。

2.2.1 剩余能量列為選舉簇頭標(biāo)準(zhǔn)

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

SEP協(xié)議的自適應(yīng)成簇技術(shù)是在簇頭建立階段，傳感器節(jié)點生成0～1之間的隨機數(shù)rand。如果隨機數(shù)小于閾值T（n），則該節(jié)點被選為簇頭。在該技術(shù)中隨機數(shù)rand的生成以及閾值T（n）的計算均與節(jié)點剩余能量無關(guān)，這樣不利于高能量節(jié)點被選為簇頭?？赏ㄟ^減小隨機數(shù)rand的值來增大剩余能量高的節(jié)點當(dāng)選為簇頭的概率。

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

由于（1）式為指數(shù)函數(shù)，在該函數(shù)中節(jié)點剩余能量越大，指數(shù)越小，進而對應(yīng)的指數(shù)函數(shù)的值越小。用該權(quán)值對rand做處理，會減小rand的值。因此，用該權(quán)值對隨機數(shù)rand做處理，會增大剩余能量高的節(jié)點當(dāng)選為簇頭的概率。

2.2.2 采用多跳樹簇拓?fù)浣Y(jié)構(gòu)路由通信機制建立網(wǎng)絡(luò)

對于簇頭與匯聚節(jié)點的通信方式本文算法采用多跳樹簇拓?fù)浣Y(jié)構(gòu)路由通信機制[10]，以該方式建立的通信網(wǎng)絡(luò)降低了基于SEP協(xié)議中簇頭與匯聚節(jié)點直接通信對于遠(yuǎn)距離簇頭節(jié)點的能量消耗，均衡了傳感器網(wǎng)絡(luò)中的能耗。

簇頭和匯聚節(jié)點的通信方式采用直接通信方式和多跳通信方式所形成的網(wǎng)絡(luò)結(jié)構(gòu)，簇頭與匯聚節(jié)點通信圖如圖2所示。該圖在一個100×100區(qū)域內(nèi)的傳感器網(wǎng)絡(luò)中，網(wǎng)絡(luò)被劃分為若干個簇，簇頭和匯聚節(jié)點通信。

多跳樹簇拓?fù)渫ㄐ艡C制是由一系列簇頭節(jié)點通過單跳或多跳的形式形成的一種樹狀拓?fù)渫ㄐ欧绞健４仡^會選擇距離匯聚節(jié)點較近的簇頭作為上級節(jié)點進行多跳通信。但不是網(wǎng)絡(luò)中所有的簇頭都會進行多跳通信，需要把單個簇頭與上級節(jié)點的通信耗能同匯聚節(jié)點的直接通信耗能進行比較，若傳輸?shù)缴霞壒?jié)點的耗能低則進行多跳通信，反之進行直接通信。所謂的上級節(jié)點是距離該簇頭最近且已加入通信鏈路的簇節(jié)點。在確定好單個簇頭的通信方式后，網(wǎng)絡(luò)中就形成了一條由簇頭到匯聚節(jié)點的多跳樹狀拓?fù)渫ㄐ沛溌贰?/p>

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

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

2.2.2.2 采用多跳樹簇拓?fù)浣Y(jié)構(gòu)的具體算法

采用多跳樹簇拓?fù)浣Y(jié)構(gòu)的具體算法步驟如下所示：

（1）將匯聚節(jié)點標(biāo)記為已加入通信鏈路，并標(biāo)記為父節(jié)點；

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

（3）對于每個非父簇頭節(jié)點執(zhí)行如下操作：

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

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

③標(biāo)記該節(jié)點為已加入通信鏈路，同時標(biāo)記為父節(jié)點；

④重復(fù)直到所有簇頭節(jié)點都加入通信鏈路。

2.3 算法的流程描述

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

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

2.3.1 簇頭的產(chǎn)生與各個節(jié)點的耗能

簇頭的產(chǎn)生與各個節(jié)點的耗能如圖3中的Part1所示。首先設(shè)置初始化參數(shù)，根據(jù)參數(shù)和相應(yīng)公式計算出閾值T（n），并為每個節(jié)點生成隨機數(shù)rand，然后按照上述規(guī)則用剩余能量對rand加權(quán)（剩余能量高的權(quán)值?。Ｈ艏訖?quán)后的rand小于T（n），則該節(jié)點當(dāng)選為簇頭。其次，成員節(jié)點選擇距離最近的簇頭加入。最后按能耗模型模擬網(wǎng)絡(luò)中成員節(jié)點向簇頭節(jié)點傳輸數(shù)據(jù)的耗能，其中成員節(jié)點耗能只考慮發(fā)送數(shù)據(jù)耗能，簇頭節(jié)點考慮融合耗能和接收耗能。

2.3.2 簇頭向匯聚節(jié)點通信部分

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

3 算法實驗

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

3.1 算法的執(zhí)行過程分析

該實驗設(shè)置的仿真參數(shù)為：在100 m×100 m的正方形區(qū)域內(nèi)，隨機部署100個節(jié)點，匯聚節(jié)點位于（50， 50）處，在整個網(wǎng)絡(luò)運行期間，節(jié)點和匯聚節(jié)點的位置固定；能量消耗參數(shù)：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；數(shù)據(jù)包的平均長度為4 000 b；在該異構(gòu)網(wǎng)絡(luò)中高能量節(jié)點高于普通節(jié)點的能量倍數(shù)a=0.5。

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

根據(jù)節(jié)點坐標(biāo)來計算節(jié)點之間的距離。運用該結(jié)構(gòu)化方式對節(jié)點信息進行存儲，以此作為模擬本文算法的基礎(chǔ)。然后采用第一順序能耗模型對網(wǎng)絡(luò)在數(shù)據(jù)傳輸過程中的成員節(jié)點向簇頭節(jié)點通信、簇頭節(jié)點向匯聚節(jié)點通信的能量消耗進行模擬。

算法第一輪執(zhí)行過后，部分節(jié)點產(chǎn)生的中間結(jié)果如圖4所示。

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

中間結(jié)果表明本文算法很好地實現(xiàn)了分簇路由通信協(xié)議的思想，并且用第一順序能耗模型能很好地模擬網(wǎng)絡(luò)中的能量消耗。

3.2 算法的運行結(jié)果分析

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

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

4 結(jié) 語

本文通過對穩(wěn)定異構(gòu)網(wǎng)絡(luò)協(xié)議SEP進行分析，發(fā)現(xiàn)在大規(guī)模傳感器網(wǎng)絡(luò)中存在節(jié)點過早死亡的現(xiàn)象，以及遠(yuǎn)距離數(shù)據(jù)傳輸能耗大的不足，設(shè)計了一種基于節(jié)點剩余能量的多跳節(jié)能算法。該算法在選取簇頭時，增大了剩余能量高的節(jié)點當(dāng)選為簇頭的概率，并采用多跳樹簇拓?fù)渫ㄐ沤Y(jié)構(gòu)的方式，在簇頭和匯聚節(jié)點建立了一條多跳樹狀數(shù)據(jù)傳輸鏈路，有效降低了用于網(wǎng)絡(luò)傳輸?shù)哪芰肯?，延長了網(wǎng)絡(luò)的生命周期。

參考文獻

[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通信協(xié)議研究[J].中國新通信，2014（12）：80.

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

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

[5]沈波，張世永，鐘亦平.無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議[J].軟件學(xué)報，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]張志東，孫雨耕，劉洋，等.無線傳感器網(wǎng)絡(luò)能量模型[J]. 天津大學(xué)學(xué)報，2007，40（9）：1029-1034.

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

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

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