基于最大流的能量采集型無(wú)線傳感器網(wǎng)絡(luò)路由算法*

馬 寧，李開宇，吳 寅，陳智軍

(南京航空航天大學(xué) 自動(dòng)化學(xué)院，江蘇 南京210016)

0 引 言

傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)由電池供電，由于電池能量有限，最大化網(wǎng)絡(luò)壽命就成為無(wú)線傳感器網(wǎng)絡(luò)中需要解決的重要問(wèn)題［1］。為了克服電池能量的限制，人們研究出一種新型的能量采集型無(wú)線傳感器網(wǎng)絡(luò)(EH－WSNs)。能量采集型無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)可以從外界吸收能量并存儲(chǔ)到蓄電池中供節(jié)點(diǎn)使用。如果節(jié)點(diǎn)從外界吸收能量的速率高于節(jié)點(diǎn)消耗能量的速率，理論上講，此網(wǎng)絡(luò)中節(jié)點(diǎn)的壽命是無(wú)限長(zhǎng)的。那么，能量采集型無(wú)線傳感器網(wǎng)絡(luò)中需要重點(diǎn)解決的問(wèn)題不再是能量的可持續(xù)性而是在特定環(huán)境下最大化網(wǎng)絡(luò)的吞吐量。

由于能量采集型無(wú)線傳感器網(wǎng)絡(luò)引入了能量采集，那么協(xié)議中應(yīng)當(dāng)能夠考慮采集速率問(wèn)題［2～8］，此時(shí)傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)協(xié)議不再適用于此網(wǎng)絡(luò)。為最大化網(wǎng)絡(luò)的吞吐量，參考文獻(xiàn)［2，3］將解決最大流問(wèn)題的 FF(Ford－Fulkerson)［9，10］算法引入能量采集型無(wú)線傳感器網(wǎng)絡(luò)中。因?yàn)镕F 算法在尋找最大流路徑時(shí)考慮了容量問(wèn)題，通過(guò)建立容量與能量采集速率的聯(lián)系，使得該算法能夠很好地用于能量采集型無(wú)線傳感器網(wǎng)絡(luò)。但是FF 由于本身增廣鏈選擇的任意性，提高了計(jì)算的復(fù)雜性，并且不能保證收斂到流的最大值。

本文對(duì)參考文獻(xiàn)［2］進(jìn)行了改進(jìn)，在搜索增廣鏈時(shí)加入對(duì)定點(diǎn)容差［11］的判定，優(yōu)先選取容差最大的點(diǎn)加入到增廣鏈［9，12］中，既提高了路徑的尋找效率，又能夠保證得到流的最大值。實(shí)驗(yàn)表明:該算法既適用于能量采集型無(wú)線傳感器網(wǎng)絡(luò)，還在獲取最大吞吐量的穩(wěn)定性上優(yōu)于文獻(xiàn)［2］中的算法。

1 能量采集型無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)模型

能量采集型無(wú)線傳感器網(wǎng)絡(luò)是一種基于多跳的，由傳輸節(jié)點(diǎn)、源節(jié)點(diǎn)以及基站組成的網(wǎng)絡(luò)。源節(jié)點(diǎn)可以從外界感知所需信息并進(jìn)行傳輸，傳輸節(jié)點(diǎn)只能傳輸已有的信息，有時(shí)源節(jié)點(diǎn)可充當(dāng)傳輸節(jié)點(diǎn)使用。源節(jié)點(diǎn)和傳輸節(jié)點(diǎn)可以從外界獲取所需的能量，并通過(guò)無(wú)線電波傳輸數(shù)據(jù)。基站即匯聚節(jié)點(diǎn)，將網(wǎng)絡(luò)中采集到的所需要的信息傳到此節(jié)點(diǎn)，它具有無(wú)限的能量。

1.1 節(jié)點(diǎn)的組成

能量采集型無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)結(jié)構(gòu)如圖1 所示。其中，能量采集裝置將外界能量轉(zhuǎn)換為電能，并將采集到的能量存儲(chǔ)在節(jié)點(diǎn)中的存儲(chǔ)器中。能量采集過(guò)程中節(jié)點(diǎn)處于閑置狀態(tài)。節(jié)點(diǎn)中的微型控制器和無(wú)線收發(fā)器可使用由德克薩斯公司生產(chǎn)的MSP430 芯片和CC2500 芯片。

圖1 節(jié)點(diǎn)結(jié)構(gòu)圖Fig 1 Structure diagram of node

1.2 能量模型

路由協(xié)議中需要模擬處理數(shù)據(jù)包所需的能量和節(jié)點(diǎn)可供使用的能量。處理數(shù)據(jù)包所需能量包括從外界獲取信息(或者接收數(shù)據(jù))、處理數(shù)據(jù)和傳輸數(shù)據(jù)所需能量。獲取信息(或者接收信息)和處理信息所需的能量是固定的，傳輸信息過(guò)程所消耗的能量與2 個(gè)節(jié)點(diǎn)之間的距離有關(guān)。可以用一個(gè)二次方公式來(lái)表示處理一個(gè)數(shù)據(jù)包的能量消耗

式中 E 為數(shù)據(jù)包傳輸所需的能量，E0為獲取信息所需的固定能量，Eunit為單位距離內(nèi)傳輸信息所需的能量。此能量模型并不包含數(shù)據(jù)包傳輸過(guò)程中所有的能量消耗，因?yàn)樵垂?jié)點(diǎn)和傳播節(jié)點(diǎn)在等待所需信息到來(lái)時(shí)需要消耗，但此處消耗的能量與獲取信息和傳輸信息所消耗的能量相比可以忽略不計(jì)。

可充電電池或者超級(jí)電容器可作為節(jié)點(diǎn)中的能量存儲(chǔ)器，能量存儲(chǔ)器為節(jié)點(diǎn)提供所需能量。由于各節(jié)點(diǎn)的能量采集速率不同，能量存儲(chǔ)器充滿電所需的時(shí)間也是不同的。能量采集型傳感網(wǎng)中節(jié)點(diǎn)的能量模型為

式中 Pn(τ)為節(jié)點(diǎn) τ 時(shí)刻的能量值;Pn(τ －1)為節(jié)點(diǎn) τ之前的剩余能量值;Rn(τ －1)為節(jié)點(diǎn)τ 時(shí)刻之前從外界吸收的能量;un為節(jié)點(diǎn)的充電電池的容量;I(an(j))表示事件j 是否發(fā)生，當(dāng)事件發(fā)生時(shí)其值為1，不發(fā)生時(shí)其值為－1;E為節(jié)點(diǎn)處理數(shù)據(jù)包所消耗的能量。

1.3 網(wǎng)絡(luò)模型

可以用一個(gè)有向網(wǎng)絡(luò)圖G =(V，E)表示能量采集型無(wú)線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)模型，V 為所有節(jié)點(diǎn)，E 為網(wǎng)絡(luò)中的所有弧。如果節(jié)點(diǎn)Vi與節(jié)點(diǎn)Vj可直接傳輸數(shù)據(jù)，則兩節(jié)點(diǎn)之間存在一條弧。

此網(wǎng)絡(luò)有一個(gè)始點(diǎn)Vs和一個(gè)終點(diǎn)Vt，流過(guò)網(wǎng)絡(luò)的流量具有一定的方向，其弧的方向就是流量流動(dòng)的方向。對(duì)每一弧(Vi，Vj)∈E，都賦予一個(gè)容量 C(Vi，Vj)=Cij≥0，為允許通過(guò)該弧的最大流量。流過(guò)一個(gè)網(wǎng)絡(luò)的某種流在各邊上的流量的集合稱為網(wǎng)絡(luò)流。在有向連通網(wǎng)絡(luò)G=(V，E)中，設(shè) fij=f(Vi，Vj)為通過(guò)弧(Vi，Vj)∈E 的實(shí)際流量，則集合f={fij|(Vi，Vj)∈E}就稱為該網(wǎng)絡(luò)的一個(gè)流。網(wǎng)絡(luò)中所有的流加起來(lái)為該網(wǎng)絡(luò)的最大流。

2 基于FF 算法的網(wǎng)絡(luò)模型

2.1 引入FF 至能量采集型網(wǎng)絡(luò)

對(duì)于能量采集型無(wú)線傳感器網(wǎng)絡(luò)，需要解決的重點(diǎn)問(wèn)題是最大化網(wǎng)絡(luò)傳輸量，而不再是能量問(wèn)題。為解決此問(wèn)題引入了FF 算法，將最大化傳輸量問(wèn)題轉(zhuǎn)為采集速率約束下的最大流問(wèn)題。

FF 算法中每條傳輸邊上都有一個(gè)對(duì)數(shù)據(jù)的傳輸容量的限制C，各節(jié)點(diǎn)上的傳輸容量決定了該網(wǎng)絡(luò)可達(dá)到的最大傳輸量。

用E 表示能量采集型無(wú)線傳感器網(wǎng)絡(luò)中某節(jié)點(diǎn)傳輸單個(gè)數(shù)據(jù)包消耗的能量，Pu表示此節(jié)點(diǎn)從外界采集能量的速率。那么Te= E/Pu稱為恢復(fù)時(shí)間，即節(jié)點(diǎn)采集傳輸數(shù)據(jù)所需能量而耗費(fèi)的時(shí)間。為使得節(jié)點(diǎn)可用，從源節(jié)點(diǎn)傳輸?shù)? 個(gè)相鄰數(shù)據(jù)包的間隔時(shí)間至少為Te，所以，有

Pu和E 是可測(cè)量的，至此，將FF 中容量和無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)能量采集速率建立的聯(lián)系。如果一個(gè)節(jié)點(diǎn)有多條傳輸路徑，則有

通過(guò)上面的公式計(jì)算，可以根據(jù)節(jié)點(diǎn)的能量采集速率和各節(jié)點(diǎn)傳輸單個(gè)數(shù)據(jù)包消耗的能量計(jì)算出每條路徑的容量。然而，節(jié)點(diǎn)實(shí)際可以傳輸?shù)娜萘砍伺c每條弧的容量有關(guān)外還與節(jié)點(diǎn)剩余能量以及節(jié)點(diǎn)傳輸單個(gè)數(shù)據(jù)包消耗的能量有關(guān)，即

其中，Ca為節(jié)點(diǎn)能量能夠傳輸?shù)娜萘浚琍r為節(jié)點(diǎn)的剩余能量。節(jié)點(diǎn)在實(shí)際傳輸數(shù)據(jù)時(shí)可以傳輸?shù)娜萘?/p>

2.2 改進(jìn)方法

盡管引入FF 算法在理論上可以最大化網(wǎng)絡(luò)傳輸量，但FF 算法本身有著一些缺陷，如增廣路徑選擇的隨機(jī)性，雙向傳輸造成能量的浪費(fèi)。因此，本節(jié)對(duì)其進(jìn)行了改進(jìn)，使其更好地應(yīng)用于能量采集型無(wú)線傳感器網(wǎng)絡(luò)。

1)FF 算法需要多次進(jìn)行標(biāo)號(hào)，計(jì)算量較大。而且增廣路徑的選取存在隨意性，如果選擇不好，算法甚至可能不會(huì)終止:流的值隨著求和運(yùn)算將不斷增加，但它甚至不會(huì)收斂到流的最大值。

圖2 展示了FF 算法由于增廣路徑選擇的隨機(jī)性得出的不同最大流。

圖2 網(wǎng)絡(luò)圖例Fig 2 Graph example of network

如果先選擇路徑 S-V1-V2-T，那么，所有的增廣鏈依次為 S-V1-V2-T，S-V2-T，S-V3-T，流量為 9 +2 +5 =16。

由此可以看出:FF 算法最后得出的流量受增廣路徑選擇的影響，而增廣路徑選擇的隨機(jī)性，導(dǎo)致了算法的不穩(wěn)定性。

這里將對(duì)FF 算法進(jìn)行改進(jìn)，以解決這個(gè)問(wèn)題。

引入容差的概念:

容差:對(duì)于有向網(wǎng)絡(luò)G=(V，E)，所謂頂點(diǎn)A 的容差ΦA(chǔ)是指:所有以A 為始點(diǎn)的有向弧的容量總和與所有以A 為終點(diǎn)的有向弧的容量和之差，即

式中 vi(a)為弧a 的始點(diǎn)，vj(a)為弧a 的終點(diǎn)，為所有以節(jié)點(diǎn) A 為始點(diǎn)的弧，為所有以節(jié)點(diǎn)A 為終點(diǎn)的弧。根據(jù)公式(5)計(jì)算出的實(shí)際傳輸數(shù)據(jù)時(shí)可以傳輸?shù)娜萘俊?/p>

容差的定點(diǎn)稱為結(jié)構(gòu)阻塞點(diǎn)。簡(jiǎn)單地說(shuō)，某點(diǎn)的容差就是該點(diǎn)所有出弧容量之和與該點(diǎn)所有入弧容量之和的差值。

將FF 算法隨機(jī)選取路徑的方法改為選擇容差較大的節(jié)點(diǎn)進(jìn)行傳輸，選擇容差大的節(jié)點(diǎn)進(jìn)行傳輸可盡力使信息以最大流傳輸，減少中間的損耗。這種做法的合理性如下:

整個(gè)界面布局極接地氣，一經(jīng)推出，深受新生讀者的喜愛(ài)，“小布”卡通形象深入人心，武漢大學(xué)圖書館也借此創(chuàng)立了自己的閱讀推廣品牌，他們的《基于卡通形象“小布”的高校圖書館閱讀推廣》獲得了2014年度中國(guó)圖書館學(xué)會(huì)“高校閱讀推廣活動(dòng)優(yōu)秀案例”一等獎(jiǎng)。

如果網(wǎng)絡(luò)流先推進(jìn)到負(fù)容差的網(wǎng)絡(luò)堵塞點(diǎn)，可能會(huì)由于出現(xiàn)出弧容量小于入弧流量而需要減小前面增廣流量的情況，甚至可能由于所有出弧都已飽和而終止增廣過(guò)程。而當(dāng)網(wǎng)絡(luò)流經(jīng)過(guò)非結(jié)構(gòu)堵塞點(diǎn)時(shí)，由于在該點(diǎn)容差為正，即出弧容量和大于入弧容量和，那么無(wú)論已經(jīng)是第幾條增廣鏈的流量流入，只要該點(diǎn)的入弧未飽和，就完全沒(méi)有網(wǎng)絡(luò)流流不入該點(diǎn)的出弧的可能性。

基于以上思想，在選擇增廣鏈時(shí)加入容差判定，優(yōu)先選擇容差較大的點(diǎn)加入到路徑中。

2)傳統(tǒng)的FF 算法中可能存在弧的雙向傳輸，這樣會(huì)導(dǎo)致數(shù)據(jù)包來(lái)回傳送浪費(fèi)能量。因此，此算法中要求數(shù)據(jù)包只能單向正向傳輸，反向路徑不允許傳送數(shù)據(jù)包。

2.3 改進(jìn)后的算法步驟

由于網(wǎng)絡(luò)中可能存在多個(gè)源節(jié)點(diǎn)和基站，為了使FF 算法可以適用于網(wǎng)絡(luò)，給網(wǎng)絡(luò)添加2 個(gè)虛擬節(jié)點(diǎn):

1)虛擬的S 節(jié)點(diǎn)連接各源節(jié)點(diǎn)，無(wú)容量限制;

2)虛擬的T 節(jié)點(diǎn)連接各基站，無(wú)容量限制。

對(duì)于連續(xù)的均勻采集數(shù)據(jù)的網(wǎng)絡(luò)，最大流的結(jié)果受數(shù)據(jù)采集速率的影響，因此，在每個(gè)源節(jié)點(diǎn)處引入一個(gè)虛擬的輸入節(jié)點(diǎn)，每個(gè)虛擬節(jié)點(diǎn)處的數(shù)據(jù)采集速率用Srate表示。

最大流求法具體步驟如下:

1)初始化有向網(wǎng)絡(luò)，置初始可行流為0，并讓Srate←∞。

2)根據(jù)式(3)計(jì)算出有向網(wǎng)絡(luò)G =(V，E)中各條弧的容量C，根據(jù)式(5)和式(6)計(jì)算出各節(jié)點(diǎn)的容差值，并標(biāo)記在節(jié)點(diǎn)處。

3)從源點(diǎn)Vs出發(fā)，判斷是否存在一條到匯點(diǎn)Vt的可增廣鏈，若存在，轉(zhuǎn)步驟(4);若不存在，轉(zhuǎn)步驟(5)。

4)尋找一條從Vs到Vt的可增廣路徑，選擇增廣路徑的過(guò)程中要優(yōu)先選擇容差較大的節(jié)點(diǎn)進(jìn)行傳輸。確保每次的增流至少使一條弧飽和，并在后面的路徑尋找中不再加入該飽和弧，計(jì)算出此路徑的增量，轉(zhuǎn)到步驟(3)。每尋找出一條可增路徑后計(jì)算并標(biāo)記各節(jié)點(diǎn)的剩余能量，并根據(jù)剩余節(jié)點(diǎn)能量重新計(jì)算容差。

5)當(dāng)不存在(Vs，Vt)的可增路時(shí)算法終止，將求得的所有的增廣路徑流量和相加可得網(wǎng)絡(luò)最大流Fmax。

6)計(jì)算出最大流后比較Fmax與Srate×N(N 為網(wǎng)絡(luò)中源節(jié)點(diǎn)的數(shù)目)是否接近相等，若不接近相等，則選擇小點(diǎn)的Srate的值從步驟(2)重新循環(huán)，直到運(yùn)行出Fmax=Srate×N，則Fmax即是要求的最大流。

此算法只要將每個(gè)節(jié)點(diǎn)標(biāo)上容差值即可，減少了傳統(tǒng)的FF 算法中的標(biāo)記過(guò)程，降低了復(fù)雜度，而且對(duì)路徑的選取具有了針對(duì)性。

3 實(shí)驗(yàn)分析

為了說(shuō)明本文算法在能量采集型無(wú)線傳感器網(wǎng)絡(luò)中的適用性，并能將該算法和參考文獻(xiàn)［2］中的算法進(jìn)行比較，本文在OMNET+ +4.1 環(huán)境中分別對(duì)2 種算法進(jìn)行了仿真和分析。

3.1 算例分析

將本文算法應(yīng)用于圖3 所示的網(wǎng)絡(luò)中。分別對(duì)各節(jié)點(diǎn)的采集速率相同和部分節(jié)點(diǎn)采集速率有變化的情況進(jìn)行了分析。根據(jù)不同節(jié)點(diǎn)的傳輸消耗和能量采集速率得到各路徑上的傳輸容量，并選擇路徑如表1 所示。

圖3 能量采集型無(wú)線傳感器網(wǎng)絡(luò)Fig 3 EH-WSNs

表1 路徑選擇情況Tab 1 Condition of path selection

通過(guò)表1 可以看出:改進(jìn)后的算法在節(jié)點(diǎn)采集速率相同和有變化的情況下都可以選擇出合適的路徑傳輸信息。

3.2 仿真分析

網(wǎng)絡(luò)仿真模型大小為100 m×100 m，仿真時(shí)間為120 s，節(jié)點(diǎn)數(shù)分別為 8，12，16，20，24，28 六種情況，節(jié)點(diǎn)初始能量為1 J，節(jié)點(diǎn)隨即分布，數(shù)據(jù)包為80 byte，各節(jié)點(diǎn)的采集速率隨機(jī)分布。仿真結(jié)果如圖4 所示。

通過(guò)仿真結(jié)果可以看出:在節(jié)點(diǎn)數(shù)相同的情況下通過(guò)本文算法獲得的吞吐量在多數(shù)情況下要大于參考文獻(xiàn)［2］中算法獲得的吞吐量，而且隨著節(jié)點(diǎn)數(shù)的增加2 種算法獲得值的差逐步增大。因此，本文算法在獲取最大吞吐量上具有更好的穩(wěn)定性。

圖4 最大吞吐量對(duì)比Fig 4 Comparison of maximum throughput

4 結(jié) 論

傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)協(xié)議不能適用于能量采集型無(wú)線傳感器網(wǎng)絡(luò)。本文對(duì)FF 算法進(jìn)行了改進(jìn)，并將改進(jìn)后的算法引入到能量采集型無(wú)線傳感器網(wǎng)絡(luò)中，提出了一種新的基于最大流的能量采集型無(wú)線傳感器網(wǎng)絡(luò)路由算法。此算法解決了能量采集型無(wú)線傳感器網(wǎng)絡(luò)中最大網(wǎng)絡(luò)工作量的問(wèn)題。通過(guò)仿真可以看出:本文算法不僅可以很好地適用于能量采集型無(wú)線傳感器網(wǎng)絡(luò)，而且在最大吞吐量的獲取上具有很好的穩(wěn)定性。

［1］ Eu Zhi Ang，Tan Hwee－pink，Seah Winston K G.Opportunistic routing in wireless sensor networks powered by ambient energy harvesting［J］.Computer Networks，2010，54:2943 － 2966.

［2］ Bogliolo Alessandro，Lattanzi Emanuele，Acquaviva Andrea.Energetic sustainability of environmentally powered wireless sensor networks［C］∥Proceedings of the Third ACM International Workshop on Performance Evaluation of Wireless Ad Hoc，Senser and Ubiquitous Networks，Torremolinos，Spain，2006:149 －152.

［3］ Lattanzi Emanuele，Regini Edoardo，Alessandro Andrea.Energetic sustainability of routing algorithms forenergy－h(huán)arvesting wireless sensor networks［J］.Computer Networks，2007，30:2976 － 2986.

［4］ Hasenfratz D.Simulative analysis of routing algorithms for energy harvesting sensor networks［D］.Swiss:Swiss Federal Institute of Technology，Zurich，2009.

［5］ Ye Peijun，Chen Cheng，Zhu Fenghua.Dynamic route guidanceusing maximum flow theory andits map reduce implementation［C］∥IEEE International Conference on Intelligent Transportation Systems，Washington DC，USA，2011:180 －185.

［6］ Eu Zhi Ang，Tan Hwee－Pink，Seah Winston K G.Wireless sensor networks powered by ambient energy harvesting:An empirical characterization［C］∥IEEE International Conference on Communications (ICC)，Singapore，2010:37 －41.

［7］ Noh Donggeon，Kim Junu，Lee Joonho.Priority based routing for solar－powered wireless sensor networks［C］∥The 2nd International Symposium on Wireless Pervasive Computing，Seoul，Korea，2007:53 －58.

［8］ 張華良，王 軍，于海斌，等.一個(gè)能量收集無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32(7):1277 －1280.

［9］ 陳 華.網(wǎng)絡(luò)流算法的若干研究和分析［D］.南京:南京郵電大學(xué)，2011.

［10］ 張憲超，陳國(guó)良，萬(wàn)穎瑜.網(wǎng)絡(luò)最大流問(wèn)題研究進(jìn)展［J］.計(jì)算機(jī)研究與發(fā)展，2003，40(9):1281 －1292.

［11］ 趙禮峰，陳 華，宋常城，等.基于一個(gè)網(wǎng)絡(luò)圖最大流算法的改進(jìn)［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20(12):162 －166.

［12］ Jakobsen Mikkel Koefoed.Energy harvesting aware routing and scheduling in wireless sensor networks［D］.Denmark:Technical University of Denmark(DTU)，2008.