郭穩(wěn)濤，郝麗波，余 波

（湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙 410151）

基于動態(tài)流能量高效的無線傳感網(wǎng)路由算法*

郭穩(wěn)濤，郝麗波，余 波

（湖南機(jī)電職業(yè)技術(shù)學(xué)院，長沙 410151）

針對無線傳感網(wǎng)中結(jié)點(diǎn)能量受限，提出了一種基于動態(tài)流能量高效的路由算法DFEERA（Dynamic Flow-based Energy-Efficient Routing Algorithm）。該算法通過在無線傳感網(wǎng)內(nèi)設(shè)置多個基站收集區(qū)域內(nèi)傳感器結(jié)點(diǎn)的數(shù)據(jù)流拓?fù)浣Y(jié)構(gòu)建立數(shù)據(jù)傳輸能量消耗模型，將該模型轉(zhuǎn)換為最大流問題求解最優(yōu)傳輸路徑，作為某時(shí)期內(nèi)結(jié)點(diǎn)數(shù)據(jù)傳輸路徑。隨著結(jié)點(diǎn)能量的消耗，動態(tài)調(diào)整該能量消耗模型重新規(guī)劃路徑，作為新的傳輸路徑，從而平衡結(jié)點(diǎn)間的能量消耗，提高網(wǎng)絡(luò)結(jié)點(diǎn)的存活率。仿真結(jié)果表明，與其他典型的路由算法相比，DFEERA能夠更好地平衡結(jié)點(diǎn)的能耗，獲得更高的能量消耗率和更長的網(wǎng)絡(luò)生存期。

無線傳感網(wǎng)絡(luò)，動態(tài)流，路由算法，能量高效

0 引言

無線傳感網(wǎng)（WSN，wireless sensor network）是由分布在監(jiān)測區(qū)域內(nèi)的能夠采集環(huán)境數(shù)據(jù)、簡單數(shù)據(jù)處理和無線通信的大量傳感器結(jié)點(diǎn)通過無線通信協(xié)議構(gòu)成的無線多跳ad hoc網(wǎng)絡(luò)［1］。WSN是由多個攜帶能夠簡單計(jì)算和存儲能力并具有無線發(fā)送接收設(shè)備的感知設(shè)備組成，這些感知設(shè)備部署后可以在線操作和重新配置［2］，能夠在寬闊惡劣的條件下，實(shí)時(shí)收集大量詳實(shí)可靠的一手?jǐn)?shù)據(jù)，被廣泛應(yīng)用于工業(yè)控制、環(huán)境監(jiān)測、交通管理、國防軍事等領(lǐng)域。與傳統(tǒng)網(wǎng)絡(luò)相比，WSN中的結(jié)點(diǎn)能夠協(xié)作地感知、采集、匯總和處理監(jiān)測區(qū)域的各種信息，WSN通常分布密集，結(jié)點(diǎn)數(shù)量能達(dá)到幾百至上千，傳感器結(jié)點(diǎn)體積小，采用容量有限的電池供電，限制了結(jié)點(diǎn)的處理和通信能力，一旦某個結(jié)點(diǎn)能量消耗完，該結(jié)點(diǎn)意味著死亡。因此，如何高效平衡地使用結(jié)點(diǎn)的能量來最大化網(wǎng)絡(luò)生命期是無線傳感網(wǎng)面臨的主要挑戰(zhàn)，如何設(shè)計(jì)合理的無線傳感網(wǎng)數(shù)據(jù)傳輸路由算法綜合平衡結(jié)點(diǎn)的能耗，是衡量無線傳感網(wǎng)性能的重要因素。

無線傳感網(wǎng)路由算法從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)上可以分為分簇路由算法和全局規(guī)劃路由算法。在分簇路由算法中，網(wǎng)絡(luò)中的結(jié)點(diǎn)通常根據(jù)某種規(guī)則被劃歸為簇首結(jié)點(diǎn)和成員結(jié)點(diǎn)。簇首結(jié)點(diǎn)管理簇內(nèi)部成員結(jié)點(diǎn)，負(fù)責(zé)簇內(nèi)成員結(jié)點(diǎn)的數(shù)據(jù)收集融合處理以及簇間數(shù)據(jù)轉(zhuǎn)發(fā)。簇首結(jié)點(diǎn)承擔(dān)著主要的無線傳感網(wǎng)的任務(wù)，其失效往往影響整個簇的失效，雖然設(shè)計(jì)時(shí)可以賦予簇首結(jié)點(diǎn)高能量，但隨著時(shí)間的推移，簇首結(jié)點(diǎn)由于故障或能量急劇消耗從而導(dǎo)致整個簇失效。近年來，國內(nèi)外研究學(xué)者和機(jī)構(gòu)相繼提出了多種分簇路由算法，比較典型的有：LEACH算法［3］、PEGASID［4］、PEDAP 協(xié)議［5］和多層回溯協(xié)議 MTP［6］。LEACH算法隨機(jī)選取簇首，成員結(jié)點(diǎn)的數(shù)據(jù)匯聚到簇首結(jié)點(diǎn)后發(fā)送給基站，減少了與基站直接通信結(jié)點(diǎn)數(shù)據(jù)，協(xié)議在每輪隨機(jī)重新選擇簇首，理論上能夠?qū)⒛芰肯木鶆虻胤植荚谒薪Y(jié)點(diǎn)上，但是，算法很難保證簇首結(jié)點(diǎn)在網(wǎng)絡(luò)中均勻分布。PEGASID協(xié)議根據(jù)結(jié)點(diǎn)的地理位置形成一條相鄰結(jié)點(diǎn)間距離最短的鏈，結(jié)點(diǎn)間的通信僅限于相鄰結(jié)點(diǎn)，可以有效地減少通信距離所消耗的能量，PEDAP協(xié)議在PEGASID協(xié)議進(jìn)一步優(yōu)化，將結(jié)點(diǎn)構(gòu)造一棵最小匯集樹，但是需要維護(hù)網(wǎng)絡(luò)全局信息，尤其是結(jié)點(diǎn)意外失效時(shí)，需要重新廣播全局信息。多層回溯協(xié)議MTP通過檢測基站信號強(qiáng)弱來確定結(jié)點(diǎn)和基站的距離，根據(jù)基站信號的距離來確定結(jié)點(diǎn)和基站的距離，通過頂層結(jié)點(diǎn)遷移機(jī)制，能夠?qū)⒛芰繐p耗較均勻地分布在所有結(jié)點(diǎn)上。這些分簇協(xié)議能夠在一定程度上緩解由于簇首能量消耗過多導(dǎo)致無線網(wǎng)生命周期終結(jié)，但是簇首畢竟能量和計(jì)算存儲能力有限，無論如何優(yōu)化，也是一定程度上緩解。

全局規(guī)劃路由算法是將所有結(jié)點(diǎn)的地位平等，網(wǎng)絡(luò)中沒有管理結(jié)點(diǎn)，優(yōu)點(diǎn)是簡單、易擴(kuò)展，但不利結(jié)點(diǎn)的數(shù)據(jù)融合，離源結(jié)點(diǎn)近的結(jié)點(diǎn)由于頻繁中轉(zhuǎn)，數(shù)據(jù)傳輸能量消耗快，典型的路由算法如：基于整數(shù)線性規(guī)劃的路由算法［7］和基于流的路由算法［8］，通過計(jì)算各結(jié)點(diǎn)的剩余能量、發(fā)送數(shù)據(jù)所需要的能量，為數(shù)據(jù)流使用圖論中流量優(yōu)化方法計(jì)算選擇最佳發(fā)送路線，以延長壽命。全局規(guī)范路由算法可以將規(guī)劃路由算法轉(zhuǎn)移到基站（base station）處理，基站是無線傳感網(wǎng)中能夠收集某個區(qū)域內(nèi)傳感器感知的數(shù)據(jù)并能夠進(jìn)行處理和存儲，能量不受限制的特殊結(jié)點(diǎn)。全局規(guī)劃可以避免局部最優(yōu)而一定是全局最優(yōu)，可以更加合理地規(guī)劃和分配區(qū)域內(nèi)結(jié)點(diǎn)能量消耗，當(dāng)前方法研究將路由問題轉(zhuǎn)換為最小代價(jià)流問題，進(jìn)行約束求解，但是沒有考慮結(jié)點(diǎn)剩余能量進(jìn)行動態(tài)調(diào)整，以便更加合理均衡能量的消耗。

本文提出的基于動態(tài)流能量高效的無線傳感網(wǎng)路由算法是對全局規(guī)劃路由算法的改進(jìn)，將數(shù)據(jù)傳輸時(shí)間分配為更為合理的時(shí)間片，在時(shí)間片輪詢初各基站收集區(qū)域內(nèi)結(jié)點(diǎn)的剩余能量和路由拓?fù)浣Y(jié)構(gòu)，傳輸路徑重新規(guī)劃，將剩余能量多的結(jié)點(diǎn)承擔(dān)更多的中轉(zhuǎn)任務(wù)，以此來平衡簇內(nèi)結(jié)點(diǎn)能量的消耗。

1 系統(tǒng)模型

DFEERA路由算法假設(shè)無線傳感網(wǎng)中的結(jié)點(diǎn)隨機(jī)分布在一個方形區(qū)域內(nèi)，并且具有以下性質(zhì)：

1）每個感知結(jié)點(diǎn)具有唯一的標(biāo)識ID，具有相同的傳輸范圍和初始能量；

2）傳感網(wǎng)能夠主動感知環(huán)境，且每個結(jié)點(diǎn)在每個時(shí)間單元生成相同的數(shù)據(jù)量，每個數(shù)據(jù)包具有相同的長度；

3）數(shù)據(jù)收發(fā)器采用與文獻(xiàn)［9］相同的能耗模型，能量衰減模型隨發(fā)送距離的遠(yuǎn)近分為自由空間模型和多路衰減模型：當(dāng)發(fā)送距離在一定閾值d0（d0為常量）內(nèi)，發(fā)送數(shù)據(jù)的功耗和距離的平方成正比；當(dāng)發(fā)送距離大于d0時(shí)，功耗和距離的四次方成正比，當(dāng)節(jié)點(diǎn)向距離d以外的另一個節(jié)點(diǎn)發(fā)送k個字節(jié)的數(shù)據(jù)時(shí)，其所消耗的能量由式（1）計(jì)算：

其中，Eelec表示收發(fā)電路所消耗的能量，Eamp表示信號放大器消耗的能量，∈fr和∈mp分別表示自由空間模型和多路衰減模型的放大器能耗。

4）路由算法是基于多跳路由協(xié)議；

5）網(wǎng)絡(luò)中具有一個或多個基站，負(fù)責(zé)某區(qū)域的數(shù)據(jù)收集；

6）傳感器節(jié)點(diǎn)部署后不再移動；

7）將多個時(shí)間周期劃分為時(shí)間片，在每個時(shí)間片的開始時(shí)，路由信息將被重新計(jì)算。

2 基于動態(tài)流的WSN路由算法

2.1 問題形式化描述

可以使用圖論模型形式化定義該路由問題，使用一個二元組圖G=〈V，E〉表示，其中：

1）V=Vs∪Vb，Vs是感知結(jié)點(diǎn)集，Vb是基站集；

2）E?V×V，表示無線鏈接集，可以直接通信的結(jié)點(diǎn)組成的集合。

使用時(shí)間輪片R表示T個時(shí)間幀，傳感器結(jié)點(diǎn)在每個時(shí)間幀生成一個數(shù)據(jù)包。在時(shí)間片R的開始，傳感器結(jié)點(diǎn)i有剩余能量REi，在時(shí)間片R內(nèi)，結(jié)點(diǎn)i總消耗的最大能量可以用α×REi表示，其中：α為參數(shù)，0＜α≤1，最優(yōu)路由算法應(yīng)該具有以下兩個約束條件：

1）在一個時(shí)間片使所有結(jié)點(diǎn)消耗的總能量最小化，將這個問題規(guī)約為最小代價(jià)路由問題（Minimum Cost Routing，MCR）；

2）在保證條件1）使某個結(jié)點(diǎn)消耗最大能量最小化，這可以規(guī)約為最小最大問題（Min-MINMAX）。

由于某個結(jié)點(diǎn)消耗的能量與通過該結(jié)點(diǎn)轉(zhuǎn)發(fā)的數(shù)據(jù)流成正比，因此，最小化結(jié)點(diǎn)消耗的最大能量問題等同于最小化該結(jié)點(diǎn)最大的數(shù)據(jù)流?？梢詫⒃撀酚伤惴ㄞD(zhuǎn)換為該拓?fù)鋱D上的數(shù)據(jù)流最小最大問題。

2.2 路由算法規(guī)約為流問題

在最小代價(jià)流問題中，給定的有向圖G=〈V，E〉，假定：結(jié)點(diǎn) i自身的供 /需量使用 b（i）表示，對每條邊（i，j）∈E，使用 cij表示邊代價(jià)，uij表示容量。路由問題可以規(guī)約圖上每條邊（i，j）∈E的流xij，滿足每個結(jié)點(diǎn)上的供/需要求和每條邊的容量約束。

最優(yōu)路由算法規(guī)約為流上的總代價(jià)∑（i，j）∈Ecijxij最小，可以按照以下步驟將最小代價(jià)問題MCR抽象為最小代價(jià)流問題：

1）使用兩個有向邊（i，j）和（j，i）替換每個無向邊（i，j）∈E，這些邊使用代價(jià) Ct標(biāo)識（如圖 1所示），Ct為發(fā)送一個數(shù)據(jù)包消耗的能量。

2）將每個傳感器結(jié)點(diǎn)i∈Vs拆分成兩個結(jié)點(diǎn)i0和i1。在結(jié)點(diǎn)i0和i1增加一條有向邊，所有結(jié)點(diǎn)i的入邊轉(zhuǎn)換為結(jié)點(diǎn)i0的入邊上，所有結(jié)點(diǎn)i的出邊轉(zhuǎn)換為結(jié)點(diǎn)i1的出邊上。對每個結(jié)點(diǎn)i1，增加一個b（i）=T（一個時(shí)間片的時(shí)間幀數(shù)目）的源結(jié)點(diǎn)，且使用額外邊指向該結(jié)點(diǎn)。

3） 結(jié) 點(diǎn) i 每 條 邊 （i0，i1） 的 容 量 max（0，這里：Cr和Ct分別表示為接受和發(fā)送一個數(shù)據(jù)包的代價(jià)，對每個?i∈Vs，邊（i0，i1）的代價(jià)為Cr。

4）對所有j∈Vb，增加一個目的結(jié)點(diǎn)Sd和結(jié)束邊（j，Sd），在結(jié)點(diǎn) Sd增加流，b（Sd）=|V|×T。

圖1 MCR轉(zhuǎn)換過程

對結(jié)點(diǎn)i∈Vs，轉(zhuǎn)換1）表示結(jié)點(diǎn)傳遞一個數(shù)據(jù)包消耗的能量，轉(zhuǎn)換3）表示結(jié)點(diǎn)i接受一個數(shù)據(jù)包消耗的能量，轉(zhuǎn)換1）和轉(zhuǎn)換2）的正確性可以參考文獻(xiàn)［10］。轉(zhuǎn)換3）描述的是將結(jié)點(diǎn)在一個時(shí)間片消耗的能量（α×REi）等值轉(zhuǎn)換為在該時(shí)間片需要轉(zhuǎn)發(fā)的數(shù)據(jù)包的數(shù)目，Ct×T表示在一個時(shí)間片內(nèi)結(jié)點(diǎn)i需要發(fā)送自身感知環(huán)境的數(shù)據(jù)包需要消耗的能量。（α×REi-Ct×T）表示在一個時(shí)間片內(nèi)轉(zhuǎn)發(fā)來自其他結(jié)點(diǎn)的數(shù)據(jù)包消耗的能量表示結(jié)點(diǎn)i在一個時(shí)間片內(nèi)能夠轉(zhuǎn)發(fā)其他結(jié)點(diǎn)數(shù)據(jù)包的數(shù)目。求解最小代價(jià)流問題最快的算法時(shí)間復(fù)雜度為：O（（|E|log|V|）（|E|+|V|log|V|））［10］。

最小最大問題（Min-MINMAX）抽象為流問題的過程如下：

1）執(zhí)行MCR轉(zhuǎn)換過程，將所有邊上代價(jià)設(shè)置為0，忽略結(jié)點(diǎn)增加的額外邊和結(jié)束邊。

2）為所有的結(jié)點(diǎn)i∈Vs增加一個新的結(jié)點(diǎn)Ss（源結(jié)點(diǎn)）和邊（Ss，i1），邊上的容量賦值為：T。

3）求解最大流問題，對每個傳感器結(jié)點(diǎn)i，在所有邊（i0，i1）中，求解最大流的邊，設(shè)置參數(shù) Xmax為邊的流。

4）MINMAX最優(yōu)解將小于Xmax，使用二叉搜索獲得Xmax的最小值，過程如下：

11 GOTO 3；}

12else{mincap=currentcap

13 GOTO 3；}

Min-MINMAX問題可以在MINMAX求解基礎(chǔ)上按照以下方法得到：

1）執(zhí)行MCR轉(zhuǎn)換過程。

2）對結(jié)點(diǎn) i的邊（i0，i1），容量賦值為：ui0i1=∑j∈Nixij-T，這里 xij為 MINMAX 求解過程中的邊（i，j）的流，Ni表示結(jié)點(diǎn)i的鄰居集合。

3）求解最小代價(jià)流問題獲得Min-MINMAX求解方案。

2.3 基于動態(tài)流的路由算法

通過以上MCR和Min-MINMAX求解過程，可以得到路由拓?fù)鋱D上的流信息，數(shù)據(jù)包傳遞過程如下：

1）對每個傳感器結(jié)點(diǎn)的出邊（i，j），設(shè)置一個計(jì)數(shù)器，計(jì)算器的值為出邊的xij值。

2）當(dāng)一個結(jié)點(diǎn)需要傳遞數(shù)據(jù)包時(shí)，從所有的出邊選擇一個出邊。

3）當(dāng)選擇邊的計(jì)算器值大于需要傳遞數(shù)據(jù)包的數(shù)目時(shí)，那么，所有的數(shù)據(jù)包從經(jīng)過該邊的路由路徑傳遞出去，該邊的計(jì)算器值相應(yīng)地減少了數(shù)據(jù)包的數(shù)目；否則，數(shù)據(jù)包只能通過該傳遞與計(jì)算器等值的數(shù)據(jù)包量，該邊的計(jì)算器相應(yīng)設(shè)置為0，剩余的數(shù)據(jù)包需要重新選擇其他出邊進(jìn)行傳遞。

基于動態(tài)流的路由算法主要包括以下過程：收集路由拓?fù)湫畔?、跟蹤結(jié)點(diǎn)的剩余能量、調(diào)用MCR和Min-MINMAX過程進(jìn)行求解流信息、根據(jù)流信息進(jìn)行數(shù)據(jù)傳遞并更新路由信息，該算法的偽代碼如下：

①收集所有傳感器結(jié)點(diǎn)間的相鄰連接信息，并構(gòu)建傳感器的拓?fù)鋱D；

②設(shè)置α參數(shù)，α=1；

③按照2.2描述的方法形式化MCR和Min-MIN MAX問題并求解，得到拓?fù)鋱D上流信息；

④If問題可以求解，跳轉(zhuǎn)到7）；

⑤Else if（α==1）表明傳感網(wǎng)已經(jīng)死亡；

⑥Else α=α+0.01，并調(diào)轉(zhuǎn)到 3）；

⑦傳遞數(shù)據(jù)包，更新路由信息；

⑧在當(dāng)前輪結(jié)束時(shí)，預(yù)測結(jié)點(diǎn)的剩余能量；

⑨跳轉(zhuǎn)到3）。

3 仿真實(shí)驗(yàn)及結(jié)果分析

本文采用基于Java的DTN仿真工具ONE（Opportunistic Network Environment）［11］進(jìn)行仿真實(shí)驗(yàn)。仿真環(huán)境區(qū)域面積為：100 m×100 m，傳感器結(jié)點(diǎn)分布選取100和200個，基站數(shù)目為3個，均勻分布在網(wǎng)絡(luò)中，時(shí)間片為200個時(shí)間單元，在每個時(shí)間片初始時(shí)刻每個傳感器結(jié)點(diǎn)采集周圍環(huán)境結(jié)點(diǎn)，數(shù)據(jù)包大小為200 B，根據(jù)文獻(xiàn)［9］設(shè)置結(jié)點(diǎn)能量參數(shù)，初始能量為 15 J，d0=10 m，Eamp=0.001 2 pJ/B/m4，Efr=12 pJ/B/m2，收發(fā)電路功耗為50 nJ/B。

為了驗(yàn)證本文算法的有效性，分別對典型全局規(guī)劃路由算法 MCF［12］、ILP-based［7］和 DFEERA 3種算法分別在結(jié)點(diǎn)數(shù)目為100和200情況下網(wǎng)絡(luò)生存周期（定義為第一個結(jié)點(diǎn)能量耗盡的時(shí)間）進(jìn)行對比。

圖2 不同結(jié)點(diǎn)網(wǎng)絡(luò)生命對比

3種算法的網(wǎng)絡(luò)生命周期分別在結(jié)點(diǎn)數(shù)目為100和200情況下對比如圖2所示。可以看出，DFEERA路由算法由于每次時(shí)間輪片之初，根據(jù)最小最大流算法Min-MINMAX找到剩余能量最少的結(jié)點(diǎn)并進(jìn)行動態(tài)調(diào)節(jié)不承擔(dān)消息轉(zhuǎn)發(fā)任務(wù)，因此，比MCF和ILP-based具有明顯的網(wǎng)絡(luò)生命周期優(yōu)勢。

圖3 結(jié)點(diǎn)剩余能量對比

結(jié)點(diǎn)消耗能量對比是在傳感器網(wǎng)絡(luò)中結(jié)點(diǎn)數(shù)目死亡一半時(shí)刻統(tǒng)計(jì)結(jié)點(diǎn)剩余能量總和，對比結(jié)果如圖3所示?？梢钥闯觯?dāng)網(wǎng)絡(luò)中只有一半結(jié)點(diǎn)存活時(shí)，DFEERA路由算法中結(jié)點(diǎn)剩余能量要比MCF和ILP-based多，因?yàn)镈FEERA路由算法能夠根據(jù)全局規(guī)劃約束求解算法找到全局最優(yōu)數(shù)據(jù)傳輸路徑，有效地降低數(shù)據(jù)傳輸能量消耗。

4 結(jié)論

針對無線傳感網(wǎng)數(shù)據(jù)傳輸結(jié)點(diǎn)消耗能量不均衡和結(jié)點(diǎn)能量受限等問題，本文提出了一種基于動態(tài)能量高效的無線傳感網(wǎng)絡(luò)路由算法DFEERA。該算法通過基站收集區(qū)域內(nèi)結(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)和能量消耗情況，并轉(zhuǎn)換為流問題，并使用約束求解得到全局能量消耗代價(jià)最小最優(yōu)路由路徑，作為一個時(shí)間輪片的結(jié)點(diǎn)數(shù)據(jù)傳輸路徑。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了該路由算法能夠在網(wǎng)絡(luò)生命周期和能量消耗方面取得比較好的均衡效果。針對無線傳感網(wǎng)的規(guī)模大小設(shè)置合理基站的數(shù)目和分布，能夠影響該路由算法的效能，針對特定使用情況的無線傳感網(wǎng)結(jié)點(diǎn)規(guī)模設(shè)置合理的基站數(shù)量是下一步研究的方向。

［1］VIDYASAGAR P，ATIF S，ELIZABETH C.Wireless sensor networks：a survey ［C］//International Conference on Advanced Information Networking and Applications Workshops.Bradford，United Kingdom，2009：636-641.

［2］OKINO C M，CORR M G.Statistically accurate sensor networking［C］//Wireless Communications and Networking Conference，2002.

［3］HEINZELMAN W R，KULIK J，BALAKRISHNAN H.Adaptive protocols for information dissemination in wireless sensor networks［C］//Proc of the 5th Annual International Conference on Mobile Computing and Networking.New York：ACM Press，2001：174-185.

［4］LINDSEY S，RAGHAVENDRA C S.Pegasis：Power-efficient gathering in sensor information systems［C］//Proc of IEEE Aerospace Conference 2002.Los Alamitos，CA：IEEE Computer Society Press，2002：1-6.

［5］TAN H O.Power efficient data gathering and aggregation in wireless sensor networks［J］.SIGMOD Record，2003，32（4）：66-71.

［6］劉昕，王全玉，金旭亮.基于能量感知的素具匯聚和路由協(xié)議［J］.計(jì)算機(jī)研究與發(fā)展，2008，45（1）：83-88.

［7］SHASHIDHAR R G，DAWANDE M，PRAKASH R ，et al.Energy effcient schemes for wireless sensor networks with multiple mobile stations［C］//Proc of IEEE Globecom 2003：377-381.

［8］GANDHAM S，DAWANDE M，PRAKASH R.An integral flow-based energy-efficient routing algorithm for wireless sensor networks［C］//IEEE Wireless Communications and Networking Conference，Atlanta，Georgia，USA，2004.

［9］HEINZELMAN W B，CHANDRAKASAN A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks ［J］.IEEE Transactions on Wireless Communications，2002（1）：660-670.

［10］AHUJA R K，MAGNANTI T L，ORLIN J B.Network Flows［M］.New Jersey：Prentice Hall，1993.

［11］KERANEN A，OTT J，KARKKAINEN T.The ONE simulator for DTN protocol evaluation［C］//SIMUTools’09：Proceedings of the 2nd International Conference on Simulation Tools and Techniques，New York，USA，2009.

［12］YE F，CHEN A，LIU S，et al.A scalable solution to minimum cost forwarding in large sensor networks［C］//Proc.of Tenth Intl.Conference on Computer Communications and Networks，2001：304-309.

A Dynamic Flow-Based Energy-Efficient Routing Algorithm for Wireless Sensor Networks

GUO Wen-tao，HAO Li-bo，YU Bo
（Hunan Mechanical and Electrical Polytechnic，Changsha 410151，China）

As sensor nodes in the wireless sensor network are energy-constrained，an energyefficient routing algorithm based on dynamic flow is presented，called DFEERA.The DFEERA distributes several base stations uniformly in the network，which collect the topology of data flow of sensors in their area and construct the data transfer and energy consumption model.This model can be converted to the maximum flow to get optimal transmission path，as the transmission path period of sensor nodes in a period.With the node energy consumption，the energy consumption model is adjusted dynamically and the transmission path is re-planned.So，it can balance the energy consumption of nodes，thus protecting the survival of network nodes effectively.Simulation results show that DFEERA can balance the energy consumption of nodes better，and thus get higher energy consumption rate and prolong the lifetime of WSN，compared with other typical routing algorithms.

wireless sensor network，dynamic flow，routing algorithm，energy efficient

TP316.4

：A

10.3969/j.issn.1002-0640.2017.06.036

2016-05-21

：2016-06-27

湖南省教育廳高等學(xué)?？茖W(xué)研究基金資助項(xiàng)目（15C0491）

郭穩(wěn)濤（1980- ），男，湖北天門人，碩士，副教授。研究方向：嵌入式系統(tǒng)的研究與開發(fā)、人工智能理論研究和通信技術(shù)等。

1002-0640（2017）06-0158-05