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

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

0 引 言

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

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

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

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

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

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

能量采集型無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)結(jié)構(gòu)如圖1 所示。其中，能量采集裝置將外界能量轉(zhuǎn)換為電能，并將采集到的能量存儲在節(jié)點(diǎn)中的存儲器中。能量采集過程中節(jié)點(diǎn)處于閑置狀態(tài)。節(jié)點(diǎn)中的微型控制器和無線收發(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ù)所需能量。獲取信息(或者接收信息)和處理信息所需的能量是固定的，傳輸信息過程所消耗的能量與2 個節(jié)點(diǎn)之間的距離有關(guān)?？梢杂靡粋€二次方公式來表示處理一個數(shù)據(jù)包的能量消耗

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

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

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

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

可以用一個有向網(wǎng)絡(luò)圖G =(V，E)表示能量采集型無線傳感器網(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ò)有一個始點(diǎn)Vs和一個終點(diǎn)Vt，流過網(wǎng)絡(luò)的流量具有一定的方向，其弧的方向就是流量流動的方向。對每一弧(Vi，Vj)∈E，都賦予一個容量 C(Vi，Vj)=Cij≥0，為允許通過該弧的最大流量。流過一個網(wǎng)絡(luò)的某種流在各邊上的流量的集合稱為網(wǎng)絡(luò)流。在有向連通網(wǎng)絡(luò)G=(V，E)中，設(shè) fij=f(Vi，Vj)為通過弧(Vi，Vj)∈E 的實(shí)際流量，則集合f={fij|(Vi，Vj)∈E}就稱為該網(wǎng)絡(luò)的一個流。網(wǎng)絡(luò)中所有的流加起來為該網(wǎng)絡(luò)的最大流。

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

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

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

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

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

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

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

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

2.2 改進(jìn)方法

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

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

圖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)定性。

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

引入容差的概念:

容差:對于有向網(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ù)娜萘俊?/p>

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

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

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

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

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

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

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

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

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

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

對于連續(xù)的均勻采集數(shù)據(jù)的網(wǎng)絡(luò)，最大流的結(jié)果受數(shù)據(jù)采集速率的影響，因此，在每個源節(jié)點(diǎn)處引入一個虛擬的輸入節(jié)點(diǎn)，每個虛擬節(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的可增廣路徑，選擇增廣路徑的過程中要優(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)的可增路時算法終止，將求得的所有的增廣路徑流量和相加可得網(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即是要求的最大流。

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

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

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

3.1 算例分析

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

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

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

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

3.2 仿真分析

網(wǎng)絡(luò)仿真模型大小為100 m×100 m，仿真時間為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 所示。

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

圖4 最大吞吐量對比Fig 4 Comparison of maximum throughput

4 結(jié) 論

傳統(tǒng)的無線傳感器網(wǎng)絡(luò)協(xié)議不能適用于能量采集型無線傳感器網(wǎng)絡(luò)。本文對FF 算法進(jìn)行了改進(jìn)，并將改進(jìn)后的算法引入到能量采集型無線傳感器網(wǎng)絡(luò)中，提出了一種新的基于最大流的能量采集型無線傳感器網(wǎng)絡(luò)路由算法。此算法解決了能量采集型無線傳感器網(wǎng)絡(luò)中最大網(wǎng)絡(luò)工作量的問題。通過仿真可以看出:本文算法不僅可以很好地適用于能量采集型無線傳感器網(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］ 張華良，王 軍，于海斌，等.一個能量收集無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32(7):1277 －1280.

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

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

［11］ 趙禮峰，陳 華，宋常城，等.基于一個網(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.