基于能量自采集的無線傳感器網(wǎng)絡(luò)網(wǎng)關(guān)切換機(jī)制研究①

杜文振陳海明 李 棟 崔 莉

(中國科學(xué)院計算技術(shù)研究所 北京 100190)

?

基于能量自采集的無線傳感器網(wǎng)絡(luò)網(wǎng)關(guān)切換機(jī)制研究①

杜文振②陳海明 李 棟 崔 莉③

(中國科學(xué)院計算技術(shù)研究所 北京 100190)

針對野外傳感網(wǎng)系統(tǒng)中采用太陽能供電的網(wǎng)關(guān)因天氣變化而產(chǎn)生能量供給失效的問題，研究了基于歷史能量采集信息和實時氣象信息的多網(wǎng)關(guān)切換方法。首先基于氣象信息決定需要切換的網(wǎng)關(guān)和網(wǎng)關(guān)切換的時機(jī)；其次提出了一種網(wǎng)關(guān)選擇算法(EasiGS)，根據(jù)候選網(wǎng)關(guān)剩余工作時間讓節(jié)點先驗式選擇網(wǎng)關(guān)接入，以避免網(wǎng)關(guān)失效帶來的數(shù)據(jù)丟失問題，并通過最優(yōu)網(wǎng)關(guān)接入方法降低系統(tǒng)中采集節(jié)點的整體能耗；最后根據(jù)實際應(yīng)用關(guān)注的數(shù)據(jù)發(fā)送頻率、網(wǎng)關(guān)恢復(fù)時間、節(jié)點與候選網(wǎng)關(guān)之間的傳輸距離等信息，通過概率統(tǒng)計的方法對EasiGS的計算開銷進(jìn)行了進(jìn)一步優(yōu)化。仿真實驗表明，EasiGS能使系統(tǒng)整體能耗達(dá)到最優(yōu)，并且優(yōu)化后的EasiGS能夠有效降低節(jié)點上的計算量。

環(huán)境監(jiān)測， 太陽能供電網(wǎng)關(guān)， 網(wǎng)關(guān)切換方法， 網(wǎng)關(guān)選擇算法， 能量恢復(fù)時間， 概率統(tǒng)計

0 引 言

野外環(huán)境監(jiān)測傳感網(wǎng)系統(tǒng)[1,2]在水體監(jiān)測、森林監(jiān)測等領(lǐng)域得到廣泛的長期使用。該類系統(tǒng)具有如下特點：(1)傳感網(wǎng)絡(luò)本身由許多具有數(shù)據(jù)采集及傳輸通信能力的傳感節(jié)點和接入網(wǎng)關(guān)構(gòu)成；(2)網(wǎng)關(guān)使用能量自采集技術(shù)(如太陽能)進(jìn)行供電。此類系統(tǒng)中的網(wǎng)關(guān)除了執(zhí)行自身的能量采集、任務(wù)處理等功能之外，還擔(dān)負(fù)著把數(shù)據(jù)傳輸?shù)胶蠖朔?wù)器的任務(wù)。因此，如果網(wǎng)關(guān)因供電不足失效，就會造成數(shù)據(jù)的丟失，從而影響整個系統(tǒng)的數(shù)據(jù)傳輸可靠性和數(shù)據(jù)完整性。

目前的傳感網(wǎng)系統(tǒng)大多采用多網(wǎng)關(guān)備份的方法[3-8]，并通過網(wǎng)關(guān)切換機(jī)制來保證系統(tǒng)的數(shù)據(jù)傳輸可靠性。但現(xiàn)有方法多采用判斷當(dāng)前工作網(wǎng)關(guān)失效之后切換到備用網(wǎng)關(guān)的技術(shù)思路。這種方法存在以下局限性：首先，切換方法不能完全避免數(shù)據(jù)丟失，因為無論怎么提高網(wǎng)關(guān)掃描速度，路由也只會在網(wǎng)關(guān)失效之后進(jìn)行切換，很難實現(xiàn)網(wǎng)關(guān)之間的無縫切換；其次，未重視失效網(wǎng)關(guān)能夠恢復(fù)工作的可能性，切換算法會嚴(yán)重影響傳感網(wǎng)系統(tǒng)的整體能量均衡；極端情況下會導(dǎo)致系統(tǒng)網(wǎng)關(guān)頻繁切換，帶來過多的整體能量消耗。

目前在網(wǎng)關(guān)切換方面的研究大多是針對802.11網(wǎng)絡(luò)和Mesh網(wǎng)絡(luò)提出的，如文獻(xiàn)[8-15]。網(wǎng)關(guān)切換解決的問題包括：(1)如何快速掃描需要切換的網(wǎng)關(guān)；(2)確定需要切換網(wǎng)關(guān)后如何進(jìn)行快速的切換。在進(jìn)行網(wǎng)關(guān)切換之前，節(jié)點需要在候選網(wǎng)關(guān)中選擇最優(yōu)的網(wǎng)關(guān)。現(xiàn)有的網(wǎng)關(guān)選擇方法[3-9]大多綜合權(quán)衡多種參數(shù)進(jìn)行最優(yōu)網(wǎng)關(guān)選擇。然而，與無線Mesh網(wǎng)絡(luò)和移動網(wǎng)絡(luò)不同的是，本文考慮的網(wǎng)關(guān)設(shè)備采用能量自采集技術(shù)，網(wǎng)關(guān)的切換不僅需要考慮其剩余能量還需要考慮失效網(wǎng)關(guān)能量恢復(fù)等因素。如何結(jié)合網(wǎng)關(guān)自供電這一特點，研究合適的網(wǎng)關(guān)切換策略與方法，在保證數(shù)據(jù)傳輸可靠性的同時，選擇最優(yōu)網(wǎng)關(guān)以保證傳感網(wǎng)系統(tǒng)整體能耗最優(yōu)是一個具有實際意義的問題。本文從保證數(shù)據(jù)可靠性和降低系統(tǒng)整體能耗出發(fā)，研究了采用自供電技術(shù)的多網(wǎng)關(guān)傳感網(wǎng)系統(tǒng)中網(wǎng)關(guān)無縫切換機(jī)制和最優(yōu)網(wǎng)關(guān)選擇算法及其優(yōu)化，研究結(jié)果得到了仿真實驗驗證。

本文主要貢獻(xiàn)包括以下幾點：

(1)針對野外環(huán)境太陽能供電傳感網(wǎng)系統(tǒng)網(wǎng)關(guān)能量供給失效問題，利用歷史能量采集信息和實時天氣信息，提出了一種無縫切換的網(wǎng)關(guān)切換方法，保證了數(shù)據(jù)傳輸?shù)倪B續(xù)性和可靠性。

(2)基于網(wǎng)關(guān)剩余工作時間、恢復(fù)工作時間、傳感節(jié)點距離網(wǎng)關(guān)的跳數(shù)、數(shù)據(jù)發(fā)送速率等因素，設(shè)計了最優(yōu)網(wǎng)關(guān)選擇算法EasiGS。

(3)考慮到傳感網(wǎng)系統(tǒng)中傳感節(jié)點的大規(guī)模性以及切換的頻繁性，基于EasiGS，結(jié)合具體的實際應(yīng)用，給出不同參數(shù)(數(shù)據(jù)發(fā)送頻率、網(wǎng)關(guān)恢復(fù)時間、節(jié)點與候選網(wǎng)關(guān)之間的傳輸距離)下的近似最優(yōu)算法，減少了計算開銷。

(4)實驗驗證了近似最優(yōu)網(wǎng)關(guān)選擇方法的正確性，并結(jié)合具體的參數(shù)給出了近似算法優(yōu)化性能分析。

1 相關(guān)研究工作

1.1 網(wǎng)關(guān)切換時機(jī)選擇

對于網(wǎng)關(guān)切換時機(jī)的選擇，現(xiàn)有的研究主要集中在對網(wǎng)關(guān)的快速掃描和提高路由性能兩個方面。網(wǎng)關(guān)的快速掃描主要是為了及時發(fā)現(xiàn)可用的網(wǎng)關(guān)。文獻(xiàn)[9]利用快速同步方法來降低掃描延遲。文獻(xiàn)[10，11]在鏈路層進(jìn)行快速的可用信道掃描來降低掃描延遲。文獻(xiàn)[12，13]提出了一種新的網(wǎng)絡(luò)架構(gòu)來降低切換延遲。文獻(xiàn)[14]通過提高多跳路由協(xié)議的性能來降低路由發(fā)現(xiàn)延遲。但以上工作的基本思路都要求網(wǎng)關(guān)切換請求由節(jié)點發(fā)起，并由節(jié)點主動查詢候選網(wǎng)關(guān)。在本文的應(yīng)用場景中，雖然節(jié)點也具備主動查詢候選網(wǎng)關(guān)信息的功能，但是切換時機(jī)由主網(wǎng)關(guān)確定，并發(fā)起切換通知。這也就意味著可以在主網(wǎng)關(guān)失效之前通知節(jié)點進(jìn)行切換，并在主

網(wǎng)關(guān)失效之前選定最優(yōu)的候選網(wǎng)關(guān)。文獻(xiàn)[12，13]雖然提出了新的網(wǎng)絡(luò)架構(gòu)，但是這種網(wǎng)絡(luò)架構(gòu)不適用于本文的應(yīng)用場景。

1.2 網(wǎng)關(guān)選擇

在網(wǎng)關(guān)的選擇方面，文獻(xiàn)[16]提出的方法由網(wǎng)關(guān)發(fā)送廣播信息，每個節(jié)點統(tǒng)計距離網(wǎng)關(guān)的跳數(shù)，選擇跳數(shù)最少的網(wǎng)關(guān)作為最優(yōu)切換網(wǎng)關(guān)。此方法在最初網(wǎng)絡(luò)建立的時候可用，但是在網(wǎng)絡(luò)運行時網(wǎng)關(guān)需要頻繁切換的情況下，這種由網(wǎng)關(guān)發(fā)起機(jī)制會導(dǎo)致大量廣播數(shù)據(jù)包，影響網(wǎng)絡(luò)傳輸?shù)挠行лd荷和系統(tǒng)整體能耗。

文獻(xiàn)[3]考慮延遲、跳數(shù)、比特誤碼率等參數(shù)綜合計算節(jié)點到網(wǎng)關(guān)的最小代價，選擇代價最小的網(wǎng)關(guān)作為候選網(wǎng)關(guān)。文獻(xiàn)[4]通過代價函數(shù)計算路由之間的數(shù)據(jù)流量，選擇的候選網(wǎng)關(guān)使得網(wǎng)絡(luò)總體的數(shù)據(jù)流量最小。文獻(xiàn)[5]基于節(jié)點與網(wǎng)關(guān)之間的歐式距離和候選網(wǎng)關(guān)負(fù)載量兩個參數(shù)，并分別賦予它們適合的權(quán)重，從而選擇最優(yōu)網(wǎng)關(guān)。文獻(xiàn)[6]在選擇最優(yōu)網(wǎng)關(guān)時考慮了網(wǎng)絡(luò)服務(wù)質(zhì)量。以上工作都基于多參數(shù)賦權(quán)形式設(shè)計最優(yōu)網(wǎng)關(guān)選擇算法，但其在實際應(yīng)用場景中存在如下問題：首先，計算參數(shù)實時數(shù)值需要在節(jié)點端發(fā)起多次查詢，會引起一定的通信和能量開銷；其次，網(wǎng)關(guān)選擇算法計算復(fù)雜度相對較高，例如文獻(xiàn)[6]，其在節(jié)點上完全實現(xiàn)的難度很大，另一方面，如果采用由網(wǎng)關(guān)實現(xiàn)該算法，則需要發(fā)送大量查詢數(shù)據(jù)包。另外，文獻(xiàn)[7]將網(wǎng)關(guān)剩余工作時間作為網(wǎng)關(guān)選擇的一個因素，但是未考慮網(wǎng)關(guān)可恢復(fù)工作的可能。

綜合以上網(wǎng)關(guān)選擇算法，結(jié)合實際應(yīng)用場景，現(xiàn)有的工作則存在以下局限性：首先，現(xiàn)有的工作較少考慮網(wǎng)關(guān)失效后恢復(fù)的場景，而本文根據(jù)實際情況將恢復(fù)供電時間作為影響網(wǎng)關(guān)選擇的一個重要因素，根據(jù)網(wǎng)關(guān)剩余工作時間、恢復(fù)工作時間、節(jié)點距離網(wǎng)關(guān)的跳數(shù)、數(shù)據(jù)發(fā)送速率等參數(shù)選擇最優(yōu)網(wǎng)關(guān)；其次，在資源受限的節(jié)點上通過復(fù)雜算法選擇最優(yōu)網(wǎng)關(guān)會帶來很大的計算開銷，不適用于頻繁切換網(wǎng)關(guān)的場景，本文通過優(yōu)化方法降低計算開銷，從而降低網(wǎng)關(guān)的切換開銷。

2 采用能量自采集網(wǎng)關(guān)的野外環(huán)境監(jiān)測傳感網(wǎng)系統(tǒng)概述

2.1 系統(tǒng)架構(gòu)

系統(tǒng)整體架構(gòu)和網(wǎng)關(guān)結(jié)構(gòu)如圖1所示，系統(tǒng)中由傳感節(jié)點(包含路由節(jié)點，以下無特殊說明均用節(jié)點代表)、網(wǎng)關(guān)和服務(wù)器端組成。其中，網(wǎng)關(guān)具有能量自采集功能，其主要組成單元如圖1中所示，包括：太陽能供電單元、處理單元、氣象數(shù)據(jù)采集單元、任務(wù)單元和通信單元。

其中處理單元處理網(wǎng)關(guān)計算操作；任務(wù)單元管理網(wǎng)關(guān)需要完成的任務(wù)，并且根據(jù)供電單元信息得出剩余工作時間；通信單元負(fù)責(zé)網(wǎng)關(guān)與服務(wù)器和節(jié)點的通信；太陽能供電單元給網(wǎng)關(guān)供電，即在光照充足的情況下，太陽能電池板在供給網(wǎng)關(guān)工作電源的同時，為蓄電池充電，在光照不足的情況下，網(wǎng)關(guān)由蓄電池供電。正常情況下，蓄電池滿電量時一般可供應(yīng)網(wǎng)關(guān)工作3到7天。在實際的系統(tǒng)中，由于各個網(wǎng)關(guān)所承擔(dān)的數(shù)據(jù)采集的轉(zhuǎn)發(fā)任務(wù)量不同，使得每個網(wǎng)關(guān)的剩余工作時間不同。氣象和天氣信息獲取單元負(fù)責(zé)從服務(wù)器獲取參考的氣象信息。

圖1 基于能量自采集網(wǎng)關(guān)的傳感網(wǎng)系統(tǒng)架構(gòu)及網(wǎng)關(guān)結(jié)構(gòu)圖

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

在環(huán)境監(jiān)測系統(tǒng)中，每個節(jié)點通過分層路由算法建立起以各個網(wǎng)關(guān)為頂點的層次網(wǎng)絡(luò)，如圖2所示。在本文中用到的主要參數(shù)如表1所示。其中，hop(Nij,k)既可事先通過在網(wǎng)絡(luò)建立時將該信息存儲在節(jié)點本地，也可在進(jìn)行網(wǎng)關(guān)切換時向從屬其他網(wǎng)關(guān)的節(jié)點取得；本文采用兩者相結(jié)合的方法。Lday(i)由網(wǎng)關(guān)根據(jù)自身剩余電壓和工作消耗能量情況計算求得；Rday由網(wǎng)關(guān)根據(jù)接收到的氣象信息計算而得。利用向服務(wù)器端獲取到的7天內(nèi)的天氣信息，得出網(wǎng)關(guān)恢復(fù)時間。如果獲取到7天的氣象信息都不能使太陽能板充電，則把網(wǎng)關(guān)恢復(fù)時間置為最大值7天。

在環(huán)境監(jiān)測系統(tǒng)中，每個節(jié)點通過建路方案，建立起以各個網(wǎng)關(guān)為頂點的層次網(wǎng)絡(luò)。每個節(jié)點選擇距離自己最近的網(wǎng)關(guān)，在每個節(jié)點中存儲自己的距離網(wǎng)關(guān)的跳數(shù)信息hop(Nij, i)。如圖2所示，每個節(jié)點記錄自身距離網(wǎng)關(guān)的跳數(shù)信息。

圖2 系統(tǒng)節(jié)點層次結(jié)構(gòu)圖

符號 含義G(g1，g2，…，gi…)傳感網(wǎng)網(wǎng)關(guān)集合Nij從屬于網(wǎng)關(guān)gi標(biāo)號為j的節(jié)點hop(Nij，k)從屬于網(wǎng)關(guān)gi的節(jié)點到網(wǎng)關(guān)gk的跳數(shù)Lday(i)網(wǎng)關(guān)gi的剩余工作時間Rday網(wǎng)關(guān)能夠恢復(fù)工作的時間R節(jié)點數(shù)據(jù)發(fā)送速率

3 網(wǎng)關(guān)切換方法的設(shè)計與實現(xiàn)

本節(jié)詳細(xì)介紹網(wǎng)關(guān)切換算法的設(shè)計和實現(xiàn)。3.1節(jié)介紹根據(jù)天氣和氣象信息網(wǎng)關(guān)切換機(jī)制。3.2節(jié)介紹了網(wǎng)關(guān)選擇算法EasiGS的詳細(xì)設(shè)計實現(xiàn)和優(yōu)化。

3.1 網(wǎng)關(guān)無縫切換機(jī)制

基于2.1節(jié)的介紹，網(wǎng)關(guān)可從服務(wù)器獲得當(dāng)前天氣信息，并可以從端獲取未來的氣象情況。根據(jù)這兩種信息，提前做出是否需要進(jìn)行網(wǎng)關(guān)切換的判斷。

定義1：太陽能的充電速度為Rcharge，網(wǎng)關(guān)的電量消耗速度為Egate，在T天中網(wǎng)關(guān)能夠恢復(fù)充電的時間為Rday。

網(wǎng)關(guān)切換需同時滿足以下兩個條件：

Rcharge

(1)

Lday

(2)

式(1)通過網(wǎng)關(guān)的電壓值變化來判斷充電速度是否小于消耗速度(周期性采樣網(wǎng)關(guān)的電池電壓，采樣頻率根據(jù)實際需求在具體應(yīng)用中設(shè)定)，如果兩次采樣所得到的電壓值的差為負(fù)數(shù)則表明充電速度小于消耗速度，反之表明電壓值充電速度大于消耗速度。

式(2)通過歷史統(tǒng)計的網(wǎng)關(guān)的電壓與壽命之間的關(guān)系來判定。圖3所示為某個網(wǎng)關(guān)的從1月4號到1月7號的電壓變化曲線，發(fā)現(xiàn)當(dāng)網(wǎng)關(guān)電壓低于2.4V時它已不能正常工作。讀取當(dāng)前網(wǎng)關(guān)電壓值，然后對照下圖得出距離電壓2.4V剩余工作時間，即Lday(由于網(wǎng)關(guān)存在充電因素，所以實際網(wǎng)關(guān)的剩余工作時間要大于Lday，所以需要周期性地更新Lday)。

圖3 網(wǎng)關(guān)電壓變化示意圖

考慮到在實際應(yīng)用場景中，根據(jù)歷史氣象數(shù)據(jù)[17]統(tǒng)計，持續(xù)陰雨天的時間很少超過7天，因此Rday<7。根據(jù)圖1中所示的氣象和天氣信息獲取單元得到的數(shù)據(jù)預(yù)計出Rday。由于一年不同時期電池的一次充電工作時間會出現(xiàn)差別，所以網(wǎng)關(guān)根據(jù)所工作的時期動態(tài)調(diào)整。例如未來T=7天的氣象信息如表2所示，當(dāng)天分時段氣象信息如表3所示。

表2 未來7天氣象信息數(shù)據(jù)來源：http://www.weather.com.cn/weather/101010100.shtml

表3 當(dāng)天分時段天氣信息①

根據(jù)表2和表3，分別把描述天氣的情況進(jìn)行形式化定義，具體如表4所示。表3中根據(jù)不同季節(jié)白天日照時間來調(diào)整采集的分時段天氣信息。

表4 氣象形式化定義

定義2：T1，T2，T3，分別為Level=1,2,3時，即晴、陰和多云，天氣的持續(xù)天數(shù)。T21為多云天氣時(Level=2)，晴天(Level=1)的小時數(shù)。

Rday=T1+T21

網(wǎng)關(guān)切換流程如圖4所示。當(dāng)需要切換算法的時候，網(wǎng)關(guān)用廣播包向所在網(wǎng)絡(luò)節(jié)點發(fā)送切換網(wǎng)關(guān)消息，切換消息通過層次網(wǎng)絡(luò)直到傳送到葉子節(jié)點，節(jié)點收到切換消息后會向上層節(jié)點發(fā)送確認(rèn)消息。

3.2 網(wǎng)關(guān)選擇算法EasiGS

在傳感網(wǎng)網(wǎng)關(guān)發(fā)出切換網(wǎng)關(guān)命令之后，從屬于該網(wǎng)關(guān)的節(jié)點需要選擇切換的網(wǎng)關(guān)，選擇網(wǎng)關(guān)的目標(biāo)是使網(wǎng)絡(luò)整體消耗的能量最少。

3.2.1 輸入?yún)?shù)

節(jié)點收到切換網(wǎng)關(guān)命令之后，首先建立一個候選網(wǎng)關(guān)信息列表，列表信息包括hop(Nij,k)， Lday(k)，以及Rday；然后根據(jù)hop(Nij,k)、Lday(k)和Rday計算最優(yōu)候選網(wǎng)關(guān)。需要指出的是，按照設(shè)計目標(biāo)應(yīng)該選用傳輸數(shù)據(jù)所經(jīng)過的各節(jié)點的能量之和為指標(biāo)之一來選擇網(wǎng)關(guān)?？紤]在實際場景中，每個節(jié)點的發(fā)送功率一致，該能量指標(biāo)可近似視為與跳數(shù)參數(shù)具有一致的分布，即傳輸數(shù)據(jù)能耗最低的路徑就是跳數(shù)最少的路徑。因此，本文采用hop(Nij,k)來作為一個指標(biāo)。

圖4 網(wǎng)關(guān)切換流程圖

3.2.2 算法設(shè)計

EasiGS算法是為每個節(jié)點能夠快速選擇最優(yōu)網(wǎng)關(guān)而設(shè)計的，優(yōu)化目標(biāo)是總跳數(shù)最少?？偺鴶?shù)包括正常數(shù)據(jù)傳輸?shù)奶鴶?shù)和進(jìn)行最優(yōu)網(wǎng)關(guān)選擇時查詢數(shù)據(jù)包所經(jīng)過的跳數(shù)。網(wǎng)關(guān)選擇的過程如算法1所示。

算法1 網(wǎng)關(guān)選擇算法．EasiGSInput：Nij[k]，Rday，CalGW，Ld=0；k=1，2，…，N，k≠i；Output：gt；1 FORk=1，2，…，Nk≠i2 IFRday≤Nij[k]．Lday(k)3 Nij[k]放入集合AHop中4 對集合AHop中按Nij[k]．hop(Nij，k)從小到大排序5 ELSE6 Nij[k]放入集合IHop中7 對集合IHop中按Nij[k]．hop(Nij，k)從小到大排序8 ENDIF9 ENDFOR10 IFAHop=?11 IFNij[k]∈IHop12 t←argmaxk(Nij[k]．Lday(k))13 returngt14 ENDIF15 ELSEIFIHop=?16 IFNij[k]∈AHop17 t←argmink(Nij[k]．hop(Nij，k))18 returngt19 ENDIF20 ELSE21 IFmin(AHop．Hop)≤min(IHop．Hop)22 IFNij[k]∈AHop23 t←argmink(Nij[k]．hop(Nij，k))24 returngt25 ENDIF26 ELSE27 FOR Nij[k]．hop(Nij，k)∈Ihop．Hop≥Min(Ahop．Hop)28 IHop←IHop?Nij[k]29 ENDFOR30 FOR Nij[k]∈Ihop31 IFLd≥Nij[k]．Lday(k)32 IHop←IHop?Nij[k]33 ENDIF34 Ld←Nij[k]．Lday(k)35 ENDFOR36 FORNij[k]∈(IHop∪{Nij[m]} whereNij[m]∈AHopandNij[m]． hop(Nij，m)=min(AHop．Hop)37 Nij[k]放入集合CalGW

38 ENDFOR39 對集合CalGW執(zhí)行算法240 ENDIF41 ENDIF

算法1中輸入變量Nij[k]是一個結(jié)構(gòu)體，包含3個成員變量hop(Nij,k)、Lday(k)和EHop。EHop是算法2中計算出來代表總的跳數(shù)代價；在算法1中Ld是用來臨時存儲跳數(shù)信息的一個變量。考慮到節(jié)點的資源受限，為了減少每個節(jié)點的計算量，在進(jìn)行最優(yōu)網(wǎng)關(guān)選擇之前，先對候選網(wǎng)關(guān)進(jìn)行篩選，僅對篩選出來的網(wǎng)關(guān)進(jìn)行總的跳數(shù)計算。篩選的基本原則是在保證總的跳數(shù)少的前提下，盡可能選擇剩余工作時間長的網(wǎng)關(guān)。算法1的第1行到第9行把網(wǎng)關(guān)分為兩類，一類是網(wǎng)關(guān)剩余工作時間大于網(wǎng)關(guān)恢復(fù)時間的(AHop)；另一類是網(wǎng)關(guān)剩余工作時間小于網(wǎng)關(guān)恢復(fù)時間的(IHop)。本文優(yōu)先選擇剩余工作時間長且距離網(wǎng)關(guān)跳數(shù)少的節(jié)點，所以對這兩類網(wǎng)關(guān)進(jìn)行篩選，篩選的方法是把剩余工作時間相對較短并且距離節(jié)點跳數(shù)較多的網(wǎng)關(guān)從集合中去掉(第10行到第19行)。篩選之后的候選網(wǎng)關(guān)滿足以下性質(zhì)：剩余工作時間越長的候選網(wǎng)關(guān)，節(jié)點距離該網(wǎng)關(guān)的跳數(shù)越多。

最終把節(jié)點可選的候選網(wǎng)關(guān)剩余工作時間情況分為以下三類：

(1)候選網(wǎng)關(guān)的剩余工作時間大于網(wǎng)關(guān)恢復(fù)工作時間(第15行到第19行)，節(jié)點直接選擇距離跳數(shù)最少網(wǎng)關(guān)即可(第15到第19行)，因為在此種情況下每一個候選網(wǎng)關(guān)的壽命都能滿足任務(wù)的能量需求，選擇跳數(shù)最少的候選網(wǎng)關(guān)就是最優(yōu)的網(wǎng)關(guān)。

(2)候選網(wǎng)關(guān)的剩余工作時間都小于網(wǎng)關(guān)恢復(fù)工作時間(第10行到第14行)。如果多網(wǎng)關(guān)比較后再切換，會在原本很短的剩余工作時間內(nèi)進(jìn)行冗余的查詢操作。為此，在以下兩種方案中選擇一個作為網(wǎng)關(guān)切換方案：一種是直接選擇剩余工作時間最長的候選網(wǎng)關(guān)(第10行到第14行)；另一種是先選擇剩余工作時間較短的網(wǎng)關(guān)然后再切換到剩余工作時間最長的候選網(wǎng)關(guān)(性能參見實驗部分的分析)。具體采用哪種方案與節(jié)點的數(shù)據(jù)發(fā)送頻率、候選網(wǎng)關(guān)最少跳數(shù)等參數(shù)相關(guān)，本文在實驗部分進(jìn)行了詳細(xì)的討論。

(3)候選網(wǎng)關(guān)的剩余工作時間既有大于網(wǎng)關(guān)恢復(fù)工作時間又有小于網(wǎng)關(guān)恢復(fù)時間的(第20行到第40行)。此時，在大于網(wǎng)關(guān)恢復(fù)時間的候選網(wǎng)關(guān)中選擇跳數(shù)最少的一個網(wǎng)關(guān)，再和小于網(wǎng)關(guān)恢復(fù)時間的網(wǎng)關(guān)組合起來，計算在網(wǎng)關(guān)恢復(fù)工作時間內(nèi)各種方案的跳數(shù)代價，最終，通過比較選擇最優(yōu)的方案。

3.2.3 網(wǎng)關(guān)選擇算法的優(yōu)化

在上一小節(jié)中，對于篩選后的候選網(wǎng)關(guān)分為三類，其中，情況(1)無需進(jìn)行計算，直接選擇距離跳數(shù)最少的候選網(wǎng)關(guān)即為最優(yōu)的方案；情況(2)和情況(3)則需要對不同方案進(jìn)行總跳數(shù)計算，然后從中選擇總跳數(shù)最少的方案。在本節(jié)中，針對情況(2)和情況(3)，結(jié)合實際應(yīng)用的系統(tǒng)，提出了一種近似最優(yōu)的低時間復(fù)雜度候選網(wǎng)關(guān)選擇算法。

為了便于計算，在算法1中假設(shè)d1,d2,…,dn分別代表已經(jīng)進(jìn)行篩選過的候選網(wǎng)關(guān)剩余工作時間，且是從小到大排列；h1,h2,…,hn分別代表相應(yīng)的節(jié)點到該網(wǎng)關(guān)的跳數(shù)；節(jié)點產(chǎn)生數(shù)據(jù)的速率用R表示；網(wǎng)關(guān)恢復(fù)工作時間用tr表示；則對于di(1≤i≤n)和h2(1≤i≤n)存在以下性質(zhì)：

性質(zhì)1：對于i>j，1≤i≤n，1≤j≤n；

則di>dj，且hi>hj。

下面針對情況(2)和情況(3)分別進(jìn)行分析，提出近似最優(yōu)的候選網(wǎng)關(guān)選擇方案。

在候選網(wǎng)關(guān)剩余工作時間低于網(wǎng)關(guān)恢復(fù)時間的情況下,則對于篩選后的候選網(wǎng)關(guān)除了滿足性質(zhì)1還滿足性質(zhì)2。

性質(zhì)2：對于1≤i≤n；

則di

此種情況下，由算法1可得，對于直接選擇最大剩余時間和先選擇跳數(shù)相對較少然后再切換剩余時間最長方案，在dn時間內(nèi)節(jié)點傳送的總跳數(shù)分別為：

當(dāng)1≤i

(3)

當(dāng)i=n時；

hopi=Cinitial+dihiR+αi

(4)

其中αi為冗余跳數(shù)，即查詢候選網(wǎng)關(guān)或者切換網(wǎng)關(guān)的時候傳輸失敗或者數(shù)據(jù)丟失重傳等因素造成的額外跳數(shù);Cinitial為初始化情況下對所有符合條件的候選網(wǎng)關(guān)進(jìn)行查找和查詢候選網(wǎng)關(guān)信息的總跳數(shù);Ci為查詢候選網(wǎng)關(guān)Gi的總跳數(shù)，在本文中Ci取為4hi。 如上所示，式(3)減去式(4)可得：

1≤i

在式(5)中αi-αn在實際計算中可以忽略不計。所以式(5)可以簡化為：

hopi-hopn=diR(hi-hn)+4hn

1≤i

結(jié)合實際情況，在本文網(wǎng)關(guān)選擇算法中假設(shè)hi取值范圍是4到15；di不低于10h；當(dāng)hi在4到15之間隨機(jī)分布的情況下，可得出以下推論：

推論1：當(dāng)R>2的情況下，hopi(1≤i

證明：

(1)取di等于10，R等于2，則式(6)可以轉(zhuǎn)化為：

f(hi, hn)=hopi-hopn=20(hi-hn)+4hn=4(5hi-4hn)

因此該問題可轉(zhuǎn)化為：在4≤hi<15，4

(2)式(6)中hi-hn<0，所以隨著di和R的增加，式(6)是遞減的，也就是hopi(1≤i

綜合(1)和(2)結(jié)果可知，推論1得證。

根據(jù)推論1應(yīng)用概率統(tǒng)計原理，計算不同方案的概率，可得出如下結(jié)論：在候選網(wǎng)關(guān)剩余工作時間都不是很長的情況下，為了避免頻繁的切換，可以選擇一個剩余工作時間最長的網(wǎng)關(guān)；或先選擇跳數(shù)最少的網(wǎng)關(guān)再切換到剩余工作時間最長的網(wǎng)關(guān)。

在候選網(wǎng)關(guān)剩余工作時間同時存在低于恢復(fù)時間和高于恢復(fù)時間的情況下，則對于篩選后的候選網(wǎng)關(guān)除了滿足性質(zhì)1外還滿足性質(zhì)3。

性質(zhì)3：對于1≤i

則dn>tr，且di

此時節(jié)點選擇直接切換到剩余工作時間大于恢復(fù)時間的網(wǎng)關(guān)，也可在剩余工作時間小于網(wǎng)關(guān)恢復(fù)時間的網(wǎng)關(guān)中選擇一個后再切換到剩余工作時間大于恢復(fù)時長的網(wǎng)關(guān)。

下面的式(7)是節(jié)點在選擇剩余工作時間低于恢復(fù)時間的網(wǎng)關(guān)Gk，然后再切換剩余工作時間大于恢復(fù)時間的網(wǎng)關(guān)Gm的總跳數(shù)代價。由于不同選擇方案初始查詢跳數(shù)代價都相同，所以為了計算方便，這部分的跳數(shù)代價沒有計入到初始跳數(shù)代價中。

(7)

根據(jù)算法2可得，對于先選擇剩余工作時間為di(1≤i

(8)

選擇剩余工作時間為dn的網(wǎng)關(guān)總跳數(shù)為

hopn=Cinitial+trhiR+αi

(9)

由式(8)減去式(9)可得

(10)

推論2：當(dāng)R>3，di>15且候選網(wǎng)關(guān)個數(shù)不超過5個的情況下，hopi(1≤i

證明：

(1)取di等于15，R等于3，則

因此該問題可轉(zhuǎn)化為：在4≤hi<15，4

(2)式(10)中hi-hn<0，所以隨著di和R的增加，式(10)是遞減的，也就是hopi(1≤i

綜合(1)和(2)結(jié)果可知，推論2得證。

在本文的第4部分，將針對具體的參數(shù)取值區(qū)間，基于統(tǒng)計的結(jié)果給出參考性的方案選擇。

4 系統(tǒng)實驗與性能分析

本節(jié)通過仿真實驗分析本文提出的網(wǎng)關(guān)選擇算法EasiGS的性能。一方面驗證本文提出的網(wǎng)關(guān)選擇算法能夠使得節(jié)點選擇最優(yōu)的網(wǎng)關(guān)；另一方面分析不同最少跳數(shù)、網(wǎng)關(guān)數(shù)量和發(fā)送頻率場景下的網(wǎng)絡(luò)性能，并根據(jù)這些統(tǒng)計結(jié)果給出如何選擇相應(yīng)的最優(yōu)網(wǎng)關(guān)選擇方案的參考性結(jié)論。

本文采用Matlab做為仿真實驗工具，設(shè)定的候選網(wǎng)關(guān)最多跳數(shù)不超過15跳，剩余工作時長不低于10h。本實驗根據(jù)上節(jié)中網(wǎng)關(guān)選擇算法優(yōu)化部分進(jìn)行驗證，根據(jù)上節(jié)中的推論，本文分別針對以下兩種情況進(jìn)行驗證：一是候選網(wǎng)關(guān)剩余工作時間低于恢復(fù)時間，二是候選網(wǎng)關(guān)剩余工作時間同時存在低于恢復(fù)時間和高于恢復(fù)時間。

4.1 候選網(wǎng)關(guān)剩余工作時間低于恢復(fù)時間

在本節(jié)中把直接切換到剩余時間最長網(wǎng)關(guān)的方案定義為方案一；把先切換到跳數(shù)最少的網(wǎng)關(guān)再切換到剩余時間最長的網(wǎng)關(guān)定義為方案二。

在本實驗中，N表示候選網(wǎng)關(guān)個數(shù)，H表示節(jié)點距離候選網(wǎng)關(guān)最少跳數(shù)，R表示數(shù)據(jù)產(chǎn)生頻率，D表示一天時間內(nèi)節(jié)點產(chǎn)生的總跳數(shù)。Thop1表示節(jié)點選擇方案一的總跳數(shù)，Thop2表示節(jié)點選擇方案二的總跳數(shù)。

在實際應(yīng)用場景下，綜合考慮成本等因素，系統(tǒng)中會部署盡可能少的網(wǎng)關(guān)，節(jié)點可選的候選網(wǎng)關(guān)十分有限。本文的實驗場景選取的候選網(wǎng)關(guān)上限為5個，已經(jīng)足夠覆蓋實際應(yīng)用場景。實驗場景將Rday設(shè)定為120h，通過不同的R，分別統(tǒng)計N分別為2、3、4、5和H為4到9的情況下，比較方案一和方案二產(chǎn)生的最少跳數(shù)的次數(shù)。如果方案一比方案二產(chǎn)生的最少跳數(shù)少，則方案一優(yōu)于方案二。實驗進(jìn)行10000次，R分別設(shè)定為0.5、1、2次/h，實驗結(jié)果分別如圖5～圖7所示。

圖5 方案一最優(yōu)的次數(shù)與H和N的關(guān)系(R=0.5)

如圖5可得，在R為0.5、N為5的情況下，進(jìn)行的10000次實驗中，即使在方案二優(yōu)于方案一的情況下，在本實驗中統(tǒng)計Thop1-Thop2>D的次數(shù)如下表5所示。

在Thop1-Thop2≤D的情況下，方案一和方案二的差別不大，所以根據(jù)圖5和表5可得出結(jié)論：在R為0.5且N為5的情況下，方案一不落后于方案二的概率超過80%，在此種情況下，直接選擇方案一。

表5 方案一比方案二產(chǎn)生的總跳數(shù)相差大于D統(tǒng)計(在

如圖6可得，在R為1的情況下，進(jìn)行的10000次實驗中，方案一和方案二兩種方案產(chǎn)生最少跳數(shù)的次數(shù)不相上下，所以在此種情況下需要分別進(jìn)行計算來選擇最優(yōu)的方案。

圖6 方案一最優(yōu)的次數(shù)與H和N的關(guān)系(R=1)

如圖7所示，在R為2的情況下，進(jìn)行的10000次實驗中，方案一優(yōu)于方案二的次數(shù)不超過3000次，即R為2的情況下，有超過70%的概率方案二優(yōu)于方案一；即使在方案一優(yōu)于方案二的情況下，根據(jù)結(jié)果統(tǒng)計，Thop2-Thop1>D 的次數(shù)分別如表6所示：

圖7 方案一最優(yōu)的次數(shù)與H和N的關(guān)系(R=2)

NH23454017203750183569601551140703389275805116856090802861336

根據(jù)圖7和表6可得出結(jié)論：在R為2的情況下，方案一不落后于方案二的概率超過85%，在此種參數(shù)情況下，可以無需計算直接選擇方案一。

除了上述實驗，還進(jìn)行了實驗驗證在候選網(wǎng)關(guān)個數(shù)一定的情況下，隨著數(shù)據(jù)發(fā)送速率的提高，兩種方案產(chǎn)出的最少跳數(shù)次數(shù)的變化趨勢，如圖8所示。

圖8 方案一和方案二的優(yōu)的次數(shù)隨著R的變化趨勢(Rday=120)

圖9的實驗是在候選網(wǎng)關(guān)個數(shù)一定的情況下，隨著候選網(wǎng)關(guān)Rday的增加，兩種方案產(chǎn)出的最少跳數(shù)次數(shù)的變化趨勢。

從圖8和圖9可得，隨著R和Rday的增大，方案二優(yōu)于方案一的次數(shù)會增加。如果不采用此方法，首先要對所有候選方案分別進(jìn)行計算，然后對計算結(jié)果進(jìn)行排序，選擇跳數(shù)最少的方案。如果從單個節(jié)點進(jìn)行一次計算考慮，不采用優(yōu)化方法的計算量非常小，但是實際應(yīng)用場景中存在著大量的節(jié)點，并且需要比較頻繁的切換，這種情況下產(chǎn)生的計算代價就變成一個值得考慮的因素。再者，在R大于2，且在一定的恢復(fù)時間內(nèi)的情況下，即可采用優(yōu)化方案進(jìn)行選擇。大多數(shù)應(yīng)用場景中，R不會低于2次，所以在多數(shù)情況下，優(yōu)化方案都適用。

圖9 方案一和方案二的優(yōu)的次數(shù)隨著Rday的

4.2 候選網(wǎng)關(guān)剩余工作時間同時存在低于恢復(fù)時間和高于恢復(fù)時間

在本節(jié)中把候選網(wǎng)關(guān)按照跳數(shù)從小到大排序，假設(shè)有N個網(wǎng)關(guān)，則候選網(wǎng)關(guān)的編號依次為1到N；方案M代表節(jié)點先選擇網(wǎng)關(guān)M(1≤M

圖10 方案二或方案三的最優(yōu)的概率與R和Rday的關(guān)系(N=3)

圖11 方案二或方案三的最優(yōu)的概率與R和Rday的關(guān)系(N=4)

如圖10所示，在N為3且R大于2的時候，方案二或者方案三基本上都能以100%的比率產(chǎn)生最小跳數(shù)，所以在此種情況下，只需在方案二和方案三中進(jìn)行計算選擇最優(yōu)網(wǎng)關(guān)，而無需計算和比較方案一。

如圖11所示，在N為2且R大于4的時候，方案二或者方案三以高于75%的概率產(chǎn)生最小距離，所以在此種情況下，只需在方案二和方案三中進(jìn)行計算選擇最優(yōu)網(wǎng)關(guān)，而無需計算和比較方案一和方案四。

類似的結(jié)論可以在具有更多候選網(wǎng)關(guān)的情況下得到，在這里不再贅述?；谝陨蠈嶒灲Y(jié)論，既可以保證節(jié)點總體發(fā)送跳數(shù)最少，又可以保證節(jié)點較高的概率選擇最優(yōu)的網(wǎng)關(guān)進(jìn)行切換。從整個網(wǎng)絡(luò)來看，尤其是節(jié)點數(shù)量較多和切換較頻繁的場景中，本文算法可以有效地降低系統(tǒng)的整體能量開銷。

5 結(jié) 論

采用野外環(huán)境太陽能供電傳感網(wǎng)系統(tǒng)受到越來越廣泛的應(yīng)用。本文從保證數(shù)據(jù)可靠性和降低系統(tǒng)整體能耗的角度出發(fā)，研究了在采用自供電技術(shù)的多網(wǎng)關(guān)傳感網(wǎng)系統(tǒng)中，網(wǎng)關(guān)無縫切換機(jī)制和最優(yōu)網(wǎng)關(guān)選擇算法及其優(yōu)化方法。本文提出并證明了計算復(fù)雜度的近似最優(yōu)方案，實驗結(jié)果表明，EasiGS算法能使系統(tǒng)獲得最優(yōu)的整體能耗性能。

未來的研究工作將進(jìn)一步考慮結(jié)合路由協(xié)議實現(xiàn)，在整體能耗最低的條件下如何提高整個網(wǎng)絡(luò)接入網(wǎng)關(guān)的公平性，并在實際系統(tǒng)中[1]驗證近似最優(yōu)網(wǎng)關(guān)選擇算法的性能。

[ 1] Zhang L, Zhao Z, Li D, et al. Wildlife monitoring using heterogeneous wireless sensor networks .Adhoc&SensorWirelessNetworks, 2013, 18(3-4): 159-179

[ 2] Li D, Zhao Z, Cui L, et al. A cyber physical networking system for monitoring and cleaning up blue-green algae blooms with agile sensor and actuator control mechanism on Lake Tai. In: Proceedings of the 1st International Workshop on Cyber-Physical Networking Systems in Conjunction with INFOCOM 2011, Shanghai, China, 2011

[ 3] Ghassemian M, Hofmann P, Friderikos V, et al. An optimised gateway selection mechanism for wireless ad hoc networks connected to the Internet. In: Proceedings of the IEEE 63rd Vehicular Technology Conference, Melbourne, Australia, 2006, 2. 782-787

[ 4] Tajima S, Higashinoz T, Funabikiy N, et al. An Internet gateway access-point selection problem for wireless infrastructure mesh networks. In: Proceedings of the 7th International Conference on Mobile Data Management, Nara, Japan, 2006. 112-112

[ 5] Ammari H, El-Rewini H. Using hybrid selection schemes to support QoS when providing multihop wireless Internet access to mobile ad hoc networks. In: Proceedings of the 1st International Conference on Quality of Service in Heterogeneous Wired/Wireless Networks(QSHINE), Dallas, USA, 2004. 148-155

[ 6] Park B N, Lee W, Lee C, et al. QoS-aware adaptive Internet gateway selection in ad hoc wireless Internet access networks. In: Proceedings of the 3rd International Conference on.Broadband Communications, Networks and Systems, San José, USA, 2006. 1-10

[ 7] Setiawan F P, Bouk S H, Sasase I. An optimum multiple metrics gateway selection mechanism in MANET and infrastructured networks integration. In: Proceedings of the IEEE Wireless Communications and Networking Conference, Las Vegas, USA, 2008. 2229-2234

[ 8] Narayan D G, Sugnani K, Raichur A, et al. A cross layer routing metric for gateway aware routing in wireless mesh network. In: Proceedings of the 2013 4th International Conference on Computing, Communications and Networking Technologies, Tiruchengode, India, 2013. 1-6

[ 9] Ramani I, Savage S. SyncScan: practical fast handoff for 802.11 infrastructure networks. In: Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, USA, 2005, 1. 675-684

[10] Wu H, Tan K, Zhang Y, et al. Proactive scan: Fast handoff with smart triggers for 802.11 wireless LAN. In: Proceedings of the 26th IEEE International Conference on Computer Communications, Anchorage, USA, 2007. 749-757

[11] Shin M, Mishra A, Arbaugh W A. Improving the latency of 802.11 hand-offs using neighbor graphs. In: Proceedings of the 2nd International Conference on Mobile Systems, Applications, and Services, Boston, USA, 2004. 70-83

[12] Amir Y, Danilov C, Hilsdale M, et al. Fast handoff for seamless wireless mesh networks. In: Proceedings of the 4th International Conference on Mobile Systems, Applications and Services (MobiSys), Uppsala, Sweden, 2006. 83-95

[13] Zhao W, Xie J. IMeX: Intergateway cross-layer handoffs in Internet-based infrastructure wireless mesh networks.IEEETransactionsonMobileComputing, 2012, 11(10): 1585-1600

[14] Speicher S. OLSR-FastSync: fast post-handoff route discovery in wireless mesh networks. In: Proceedings of the 64th Vehicular Technology Conference, Melbourne, Australia, 2006. 1-5

[15] Liu J, Chung S H. An efficient load balancing scheme for multi-gateways in wireless mesh networks.JournalofInformationProcessingSystems, 2013, 9(3): 365-378

[16] Domingo M C. Integration of ad hoc networks with fixed networks using an adaptive gateway discovery protocol. In: Proceedings of the 2nd IET International Conference on Intelligent Environments, 2006. 371-379

[17] 氣象信息查詢. http://www.cma.gov.cn/2011qxfw/2011qsjcx: 中國氣象局, 2011

doi：10.3772/j.issn.1002-0470.2016.07.004

Research on a gateway switching mechanism based on gateway’s energy-harvesting for wireless sensor networks

Du Wenzhen, Chen Haiming, Li Dong, Cui Li

(Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190)

To address the problem of insufficient energy supply of the solar-powered gateway in field wireless sensor network system due to weather variations, a multi-gateway switching method based on historically collected energy information and real-time weather information was studied. Firstly, which gateways need to switch and when to switch were determined based on the weather information. Secondly, a gateway selection algorithm, called EasiGS, was presented to make nodes proactively choose the appropriate gateway as the accessing gateway based on the remaining work time of the gateway, so as to avoid data loss and to achieve reduced overall energy consumption of the system. Finally, the computational overhead of the gateway selection algorithm was further optimized according to the rate of data transmission, the time for the gateway to recover to work, the hops of shortest path between the candidate gateway and the node. The simulation results show that the EasiGS can achieve optimal overall power consumption of the system. The optimized EasiGS can effectively reduce the amount of computation required by the nodes.

environment monitoring, solar powered gateway, gateway switch method, gateway selection algorithm, time to restore energy, probability statistics

10.3772/j.issn.1002-0470.2016.07.003

①國家自然科學(xué)基金(61303246)和863計劃(2014AA093402)資助項目。

②男，1989年生，博士生；研究方向：物聯(lián)網(wǎng)，無線傳感器，傳感網(wǎng)系統(tǒng)路由協(xié)議等；E-mail: duwenzhen@ict.ac.cn

③通訊作者，E-mail: lcui@ict.ac.cn

2016-01-21)