杜文振陳海明 李 棟 崔 莉

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

?

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

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

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

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

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

0 引 言

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

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

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

本文主要貢獻包括以下幾點：

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

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

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

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

1 相關研究工作

1.1 網(wǎng)關切換時機選擇

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

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

1.2 網(wǎng)關選擇

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

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

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

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

2.1 系統(tǒng)架構

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

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

圖1 基于能量自采集網(wǎng)關的傳感網(wǎng)系統(tǒng)架構及網(wǎng)關結構圖

2.2 網(wǎng)絡模型

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

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

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

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

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

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

3.1 網(wǎng)關無縫切換機制

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

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

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

Rcharge

(1)

Lday

(2)

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

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

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

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

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

表3 當天分時段天氣信息①

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

表4 氣象形式化定義

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

Rday=T1+T21

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

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

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

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

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

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

3.2.2 算法設計

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

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

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

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

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

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

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

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

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

性質1：對于i>j，1≤i≤n，1≤j≤n；

則di>dj，且hi>hj。

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

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

性質2：對于1≤i≤n；

則di

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

當1≤i

(3)

當i=n時；

hopi=Cinitial+dihiR+αi

(4)

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

1≤i

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

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

1≤i

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

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

證明：

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

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

因此該問題可轉化為：在4≤hi<15，4

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

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

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

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

性質3：對于1≤i

則dn>tr，且di

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

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

(7)

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

(8)

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

hopn=Cinitial+trhiR+αi

(9)

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

(10)

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

證明：

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

因此該問題可轉化為：在4≤hi<15，4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

NH23454017203750183569601551140703389275805116856090802861336

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結 論

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

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

[ 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

①國家自然科學基金(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)