0 引言

    由于無(wú)線傳感網(wǎng)將大量傳感器分布于目標(biāo)區(qū)域用來(lái)監(jiān)控目標(biāo)區(qū)域中的可感知狀態(tài)(溫度、高度等)^[1]，因此被廣泛應(yīng)用于工業(yè)控制^[2]、農(nóng)產(chǎn)品生產(chǎn)^[3]及戰(zhàn)爭(zhēng)^[4]等領(lǐng)域。傳感節(jié)點(diǎn)一般體積較小、成本低廉，傳感節(jié)點(diǎn)的能量是一個(gè)重要資源。

    文獻(xiàn)[5]針對(duì)周期性采集數(shù)據(jù)的傳感器網(wǎng)絡(luò)提出了一種基于分布式的跨層能效優(yōu)化協(xié)議EEDS。EEDS的核心思想是建立一個(gè)能量效率樹(shù)狀結(jié)構(gòu)，樹(shù)的節(jié)點(diǎn)為傳感器節(jié)點(diǎn)，并建立了相應(yīng)的TDMA調(diào)度器^[6]。

    本文基于EEDS協(xié)議的能量效率樹(shù)與調(diào)度器建立了跨層優(yōu)化模型。本算法通過(guò)設(shè)置目標(biāo)成本函數(shù)，并求解其最優(yōu)解來(lái)獲得全局最優(yōu)生命周期，從而提高了原協(xié)議的網(wǎng)絡(luò)生命期，降低了數(shù)據(jù)傳輸?shù)难舆t。

1 EEDS協(xié)議及其模型簡(jiǎn)介

    EEDS的核心思想是建立一個(gè)聯(lián)合路由樹(shù)狀結(jié)構(gòu)及TDMA調(diào)度器。EEDS協(xié)議將每個(gè)時(shí)間幀分為若干輪，每輪分為3個(gè)階段：建立樹(shù)狀結(jié)構(gòu)(BT)、建立調(diào)度器(BS)、數(shù)據(jù)傳輸(DT)。BT階段：建立以sink節(jié)點(diǎn)為根的樹(shù)狀結(jié)構(gòu)；BS階段：建立一個(gè)分布式TDMA調(diào)度器；DT階段：將數(shù)據(jù)從源節(jié)點(diǎn)傳輸至sink節(jié)點(diǎn)。每輪中的3個(gè)階段重復(fù)多次，如圖1所示。

1.1 建立能量效率樹(shù)狀結(jié)構(gòu)

    采用文獻(xiàn)[7]的算法建立能效樹(shù)狀結(jié)構(gòu)。首先，初始化sink節(jié)點(diǎn)并廣播控制信息，控制信息由4部分組成：狀態(tài)、深度、父節(jié)點(diǎn)、剩余能量值。

1.2 建立TDMA調(diào)度階段

    基于第一階段建立的能量效率樹(shù)，建立TDMA調(diào)度器。設(shè)TRR、TRT為2個(gè)關(guān)于節(jié)點(diǎn)的時(shí)間常量：對(duì)于一個(gè)節(jié)點(diǎn)v，TRR_v表示該節(jié)點(diǎn)準(zhǔn)備好接收其子節(jié)點(diǎn)信息的時(shí)間間隙長(zhǎng)度，TRT_v表示該節(jié)點(diǎn)準(zhǔn)備好向其子節(jié)點(diǎn)發(fā)送信息的時(shí)間間隙。因此節(jié)點(diǎn)在時(shí)間段[TRR_v，TRR_v+1]內(nèi)必須處于喚醒狀態(tài)。設(shè)t′表示時(shí)間間隙，在該時(shí)間間隙內(nèi)節(jié)點(diǎn)采集數(shù)據(jù)并向父節(jié)點(diǎn)傳輸數(shù)據(jù)。然后，因葉節(jié)點(diǎn)無(wú)子節(jié)點(diǎn)，所以葉節(jié)點(diǎn)的TRRv無(wú)效；對(duì)于非葉節(jié)點(diǎn)v，可表示為：

2 基于線性規(guī)劃問(wèn)題EEDS協(xié)議優(yōu)化模型(LPP)

    本文基于EEDS協(xié)議建立了新的跨層優(yōu)化LPP模型，因此，LPP的限制條件與成本函數(shù)必須滿足EEDS協(xié)議。EEDS協(xié)議中建立了一個(gè)能效樹(shù)，本模型的首要目標(biāo)是最大化網(wǎng)絡(luò)的生命期，另一個(gè)重要目標(biāo)是最小化延遲。

    假設(shè)網(wǎng)絡(luò)中共n個(gè)節(jié)點(diǎn)(包括sink節(jié)點(diǎn))，sink的序號(hào)設(shè)為1，設(shè)d_ij表示節(jié)點(diǎn)i和節(jié)點(diǎn)j之間的距離，1≤i，j≤n，設(shè)R表示節(jié)點(diǎn)的單跳傳輸范圍，E_i表示節(jié)點(diǎn)i(1≤i)的剩余能量。

2.1 成本函數(shù)

    EEDS協(xié)議的主要目標(biāo)是最大化網(wǎng)絡(luò)生命期，首先建立一個(gè)能效樹(shù)，樹(shù)中的每個(gè)節(jié)點(diǎn)選擇能量最多的父節(jié)點(diǎn)來(lái)進(jìn)行數(shù)據(jù)傳輸，從而實(shí)現(xiàn)了整體網(wǎng)絡(luò)生命期的優(yōu)化。設(shè)EC_i為節(jié)點(diǎn)i從子節(jié)點(diǎn)接收數(shù)據(jù)包所消耗的能量，E_i表示節(jié)點(diǎn)i的剩余能量。

    應(yīng)考慮如下因素：

    (1)對(duì)于剩余能量較高的節(jié)點(diǎn)，應(yīng)最大化其EC_i；反之，對(duì)于能量低的節(jié)點(diǎn)，則最小化其EC_i。

    (2)E_i高的節(jié)點(diǎn)，其子節(jié)點(diǎn)應(yīng)該更多。

    綜上，應(yīng)最大化每個(gè)節(jié)點(diǎn)的EC_i×E_i。因此，成本函數(shù)則是最大化所有節(jié)點(diǎn)EC_i×E_i的總和：

    LPP模型另一個(gè)目標(biāo)為最小化延遲，延遲定義為一個(gè)數(shù)據(jù)包到達(dá)sink節(jié)點(diǎn)所需的總時(shí)間。根據(jù)EEDS協(xié)議，每個(gè)中間節(jié)點(diǎn)需將其本輪接收的所有數(shù)據(jù)均傳至其父節(jié)點(diǎn)，最終所有數(shù)據(jù)傳至sink節(jié)點(diǎn)。將sink節(jié)點(diǎn)表示為node-1，為了最小化延遲，node-1的傳輸時(shí)間(t1)必須最小化。因此，第二個(gè)目標(biāo)表示為：

    LPP模型可通過(guò)式(4)求解，或者將延遲作為一個(gè)限制條件來(lái)求解網(wǎng)絡(luò)生命期的最大值。

2.2 能效樹(shù)的限制條件

    為了表示節(jié)點(diǎn)i與節(jié)點(diǎn)j之間的父子鏈接關(guān)系，定義二值變量x_ij為：

    對(duì)于兩個(gè)節(jié)點(diǎn)組成的節(jié)點(diǎn)對(duì)，僅有一個(gè)父節(jié)點(diǎn)與一個(gè)子節(jié)點(diǎn)，或者兩節(jié)點(diǎn)間無(wú)關(guān)系，因此：

式(6)表示兩個(gè)節(jié)點(diǎn)為父子關(guān)系時(shí)，x_ij與x_ji中至少有一個(gè)為1；兩者無(wú)關(guān)系時(shí)為0。

    每個(gè)節(jié)點(diǎn)i(包括sink節(jié)點(diǎn))僅有一個(gè)父節(jié)點(diǎn)：

    設(shè)節(jié)點(diǎn)通信范圍為R，節(jié)點(diǎn)僅可與其通信范圍內(nèi)的節(jié)點(diǎn)通信。對(duì)于一對(duì)節(jié)點(diǎn)(i與j)，如果距離大于R，則無(wú)法建立鏈接，表示為：

    設(shè)距離為d的兩個(gè)節(jié)點(diǎn)間發(fā)送k比特?cái)?shù)據(jù)的能耗為E_Tx，而接收k比特?cái)?shù)據(jù)所需能量為E_Rx：

2.3 TDMA調(diào)度器限制條件

    引入一個(gè)二值變量：在一個(gè)時(shí)間間隙中，一對(duì)節(jié)點(diǎn)間是否有數(shù)據(jù)傳輸，表示為：

其中k是i的子節(jié)點(diǎn)。

    將式(23)代入式(24)：

    因此LPP的成本函數(shù)為式(2)～(4)，限制函數(shù)為式(5)~(11)、式(15)、式(18)~(22)、式(25)。

3 仿真試驗(yàn)與結(jié)果

3.1 試驗(yàn)環(huán)境與試驗(yàn)平臺(tái)

    使用LINGO求解器來(lái)求解LPP模型。本實(shí)驗(yàn)中，設(shè)置LINGO自動(dòng)選擇合適的方案。利用Visual Basic將本算法編程實(shí)現(xiàn)并產(chǎn)生可執(zhí)行程序(驅(qū)動(dòng)程序)，驅(qū)動(dòng)調(diào)用LINGO求解器來(lái)求解。

3.2 參數(shù)設(shè)置

    試驗(yàn)中，設(shè)網(wǎng)絡(luò)進(jìn)行1 000個(gè)周期活動(dòng)。如果1 000個(gè)周期小于TP，則使用能效樹(shù)；否則，使用TP。每輪結(jié)束，驅(qū)動(dòng)計(jì)算每個(gè)節(jié)點(diǎn)的剩余能量，將剩余能量為0的節(jié)點(diǎn)刪除。若該輪數(shù)據(jù)傳輸成功，則使用更新的輸入?yún)?shù)調(diào)用LINGO求解器。

    采用不同的網(wǎng)絡(luò)參數(shù)建立多組試驗(yàn)：每組配置中，傳感節(jié)點(diǎn)在不同維度上隨機(jī)分布，但所有網(wǎng)絡(luò)配置中，sink均處于幾何中心位置；每組試驗(yàn)測(cè)試30個(gè)不同的網(wǎng)絡(luò)結(jié)構(gòu)，每組試驗(yàn)的結(jié)果為30次試驗(yàn)的平均值，其置信水平為0.95。采用文獻(xiàn)[8]的能量模型，參數(shù)設(shè)置如下：節(jié)點(diǎn)通信范圍(R)：15 m；電氣能耗(eelec)：50(nJ/bit)；sink的起始能量：100 J；各節(jié)點(diǎn)初始化能量：2 J；控制數(shù)據(jù)包大?。?0 B；數(shù)據(jù)包大?。?00 B；放大器能耗：100(pJ/bit/m²)。

    試驗(yàn)中比較參數(shù)包括：網(wǎng)絡(luò)生命期、總吞吐量與延遲。生命期設(shè)為：從開(kāi)始直至目標(biāo)區(qū)域的網(wǎng)絡(luò)覆蓋率降至75%的時(shí)間。

3.3 試驗(yàn)結(jié)果與分析

    將EEDS協(xié)議的仿真結(jié)果與本文模型優(yōu)化的結(jié)果(僅考慮第一個(gè)成本函數(shù))進(jìn)行比較。

    第一組試驗(yàn)設(shè)為：將10個(gè)節(jié)點(diǎn)隨機(jī)分布于大小為50 m×50 m的方形區(qū)域，試驗(yàn)結(jié)果如圖2所示。從圖2可看出兩個(gè)解的變化趨勢(shì)相仿，但LPP的解優(yōu)于EEDS仿真的解。在250 s后，LPP的節(jié)點(diǎn)存活數(shù)量為5，而EEDS仿真的結(jié)果僅為150 s，即降至5個(gè)節(jié)點(diǎn)。LPP解比EEDS仿真的解性能提高了66%。

    圖3所示為L(zhǎng)PP解與EEDS仿真的覆蓋率的比較，可看出LPP的覆蓋率較優(yōu)：250 s之后LPP解的覆蓋率降至60%，而仿真在190 s即降至60%。LPP解比EEDS仿真的性能提高了31.5%。

    圖4所示為網(wǎng)絡(luò)生命期隨網(wǎng)絡(luò)密度變化的試驗(yàn)結(jié)果?？煽闯鰞蓚€(gè)解的性能接近，生命期均隨著網(wǎng)絡(luò)密度的提高而提高。原因在于：當(dāng)網(wǎng)絡(luò)密度較高時(shí)，節(jié)點(diǎn)間距離較近，從而傳輸數(shù)據(jù)消耗的能量也較少。此外，高密度下節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量也較多，因此，每輪中節(jié)點(diǎn)可選擇不同的鄰居節(jié)點(diǎn)進(jìn)行傳輸。反之，如果密度較低，每個(gè)節(jié)點(diǎn)僅有一個(gè)鄰居節(jié)點(diǎn)，因此該節(jié)點(diǎn)消耗較多的能量，導(dǎo)致其能量可能較早耗盡。

    從圖4中可看出，LPP解的生命期優(yōu)于EEDS仿真解，當(dāng)網(wǎng)絡(luò)密度為0.025 node/m²時(shí)，LPP解的網(wǎng)絡(luò)生命期為395 s，而EEDS的生命期僅為308 s。LPP解的性能比EEDS仿真提高了28.3%。其原因在于：LPP模型建立的能效樹(shù)假設(shè)網(wǎng)絡(luò)的全局信息是已知的，在此基礎(chǔ)上建立了一個(gè)最優(yōu)樹(shù)，而EEDS仿真基于局部信息建立，無(wú)法獲得全局最優(yōu)解。

4 小結(jié)

    現(xiàn)有的EEDS協(xié)議通過(guò)建立跨層優(yōu)化模型提高了網(wǎng)絡(luò)生命期，本文基于EEDS協(xié)議建立了優(yōu)化模型與目標(biāo)成本函數(shù)，并設(shè)計(jì)一些合理的限制條件來(lái)提高求解速度。試驗(yàn)結(jié)果證明，本優(yōu)化模型進(jìn)一步提高了EEDS協(xié)議的網(wǎng)絡(luò)生命期性能，并降低了數(shù)據(jù)傳輸?shù)难舆t。

參考文獻(xiàn)

[1] 錢志鴻，王義君.面向物聯(lián)網(wǎng)的無(wú)線傳感器網(wǎng)絡(luò)綜述[J].電子與信息學(xué)報(bào)，2013，35(1)：215-227.

[2] 呂西午，劉開(kāi)華，趙巖.基于Zigbee的無(wú)線監(jiān)測(cè)系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)工程，2010，36(5)：243-244.

[3] 崔偉，馮媛，甘勇，等.基于WSN的農(nóng)產(chǎn)品物流跟蹤監(jiān)控系統(tǒng)[J].通信技術(shù)，2009，41(9)：140-141.

[4] 王翔宇，沈冬遠(yuǎn).傳感器網(wǎng)絡(luò)技術(shù)在未來(lái)戰(zhàn)爭(zhēng)中的發(fā)展及應(yīng)用[J].通信技術(shù)，2008(11)：227-229.

[5] AL-KHDOUR T A，BAROUDI U.An energy-efficient distributed schedule-based communication protocol for periodic wireless sensor networks[J].Arabian Journal for Science and Engineering，2010(35)：155-168.

[6] 王陸江，張偉，張敬忠.基于TDMA的無(wú)線傳感器網(wǎng)絡(luò)時(shí)隙分配算法[J].計(jì)算機(jī)工程與設(shè)計(jì)，2008，29(7)：1706-1708.

[7] BOUKERCHE A，CHENG X，LINUS J.A performance evaluation of a novel energy-aware data-centric routing algorithm in wireless sensor networks[J].Wireless Networks，2005，11(5)：619-635.

[8] HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J].Wireless Communications，IEEE Transactions on，2002，1(4)：660-670.