劉豐年

(三門峽職業(yè)技術(shù)學(xué)院 信息傳媒學(xué)院，河南 三門峽 472000)

目前，無(wú)線傳感器網(wǎng)絡(luò)已被廣泛應(yīng)用于狀態(tài)監(jiān)測(cè)、動(dòng)態(tài)路徑查找等醫(yī)療保健[1-2]和智能家居[3]等領(lǐng)域，它涉及網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)，通過(guò)預(yù)先定義的網(wǎng)絡(luò)拓?fù)湎蚪邮掌鞴?jié)點(diǎn)報(bào)告?zhèn)鞲衅鲾?shù)據(jù)，然后向中央服務(wù)器報(bào)告。由于多數(shù)無(wú)線傳感器網(wǎng)絡(luò)采用電池工作，故在數(shù)據(jù)通信過(guò)程中通常有兩個(gè)主要目標(biāo)：高能效、低延遲。一種有效的能夠?qū)崿F(xiàn)高能效的方案是采用聚合傳輸，每個(gè)節(jié)點(diǎn)負(fù)責(zé)從其子節(jié)點(diǎn)接收聚合數(shù)據(jù)，然后盡快將聚合數(shù)據(jù)發(fā)送到其父節(jié)點(diǎn)。該方法中的每個(gè)節(jié)點(diǎn)均處于活動(dòng)模式并消耗能量，直到完成所有數(shù)據(jù)的接收和聚合。因此，降低傳輸延遲成為實(shí)現(xiàn)高能效的一個(gè)重要因素。正交信道的出現(xiàn)使得無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間的同步通信成為可能，可以減少網(wǎng)絡(luò)中用于數(shù)據(jù)收集的時(shí)隙數(shù)量，從而實(shí)現(xiàn)低延遲。

國(guó)內(nèi)外許多學(xué)者針對(duì)能效調(diào)度展開(kāi)了深入的研究。文獻(xiàn)[4]提出了一種以時(shí)分復(fù)用(time division multiple access,TDMA)方式向多個(gè)節(jié)點(diǎn)同時(shí)發(fā)送數(shù)據(jù)的方法，大大減少了總發(fā)送時(shí)間；文獻(xiàn)[5]提出了一種獨(dú)立通用多相(dependent general multiframe,DGMF)方法，用于捕獲調(diào)度分析系統(tǒng)中的主要特征；文獻(xiàn)[6]提出了一種新的Zigbee無(wú)線網(wǎng)絡(luò)路由協(xié)議，降低了網(wǎng)絡(luò)能耗；文獻(xiàn)[7]討論了通信能量約束下無(wú)線傳感器網(wǎng)絡(luò)的傳輸功率調(diào)度與控制協(xié)同設(shè)計(jì)問(wèn)題，詳細(xì)描述了不同傳輸功率水平對(duì)數(shù)據(jù)傳輸?shù)挠绊?；文獻(xiàn)[8]提出了一種新的無(wú)干擾TDMA睡眠調(diào)度方案，該方案可以為傳感器分配連續(xù)時(shí)隙以減少狀態(tài)轉(zhuǎn)換頻率；文獻(xiàn)[9]分析了具有移動(dòng)接收器的時(shí)延容忍無(wú)線傳感器網(wǎng)絡(luò)中的數(shù)據(jù)采集問(wèn)題，并基于壓縮感知和聚類技術(shù)提出了新的高效的數(shù)據(jù)采集算法；文獻(xiàn)[10]提出了一種基于權(quán)值的優(yōu)先級(jí)方案，該方案利用二部圖服從依賴和干擾約束。

在此背景下，針對(duì)無(wú)線計(jì)量網(wǎng)絡(luò)，本研究提出了一種新的調(diào)度方法用于解決多信道多跳傳輸?shù)膬?yōu)化調(diào)度問(wèn)題。在智能電網(wǎng)、水表、煤氣表等無(wú)線計(jì)量網(wǎng)絡(luò)中，所有的傳感器節(jié)點(diǎn)都會(huì)被周期性地喚醒以測(cè)量計(jì)量數(shù)據(jù)，并在傳輸完成后切換到休眠模式。

1 網(wǎng)絡(luò)架構(gòu)與問(wèn)題描述

1.1 網(wǎng)絡(luò)架構(gòu)

針對(duì)無(wú)線計(jì)量網(wǎng)絡(luò)，考慮構(gòu)建一種多跳無(wú)線傳感器網(wǎng)絡(luò)，該網(wǎng)絡(luò)由具有一組可用信道的單無(wú)線電傳感器節(jié)點(diǎn)構(gòu)成，在完成傳感器數(shù)據(jù)的最新測(cè)量后，每個(gè)節(jié)點(diǎn)均可開(kāi)始傳輸數(shù)據(jù)，節(jié)點(diǎn)可以選擇一個(gè)可用的正交通道。

無(wú)線傳感器網(wǎng)絡(luò)可以表示為一個(gè)圖G=(V,E)，其中V為傳感器節(jié)點(diǎn)ni的集合，E表示集合V中兩個(gè)節(jié)點(diǎn)間通信鏈路ej的集合，其中ej為有向邊，表示向匯聚節(jié)點(diǎn)的下一跳節(jié)點(diǎn)傳輸數(shù)據(jù)，集合E可以通過(guò)多跳路由算法生成，產(chǎn)生一個(gè)路由路徑生成樹(shù)。本研究提出了一種基于利用率的多信道多跳路由方法來(lái)解決低功耗問(wèn)題。大多數(shù)程序公司要求在盡可能短的時(shí)限內(nèi)對(duì)所有儀表加以測(cè)量，從而確保能夠捕捉能源的即時(shí)快照以準(zhǔn)確地平衡能源負(fù)荷分配。因此，在該項(xiàng)工作中，假設(shè)集合V里所有節(jié)點(diǎn)一起被喚醒以測(cè)量數(shù)據(jù)，而每個(gè)節(jié)點(diǎn)在完成發(fā)送到它的下一個(gè)躍點(diǎn)后立即進(jìn)入睡眠狀態(tài)。假設(shè)網(wǎng)絡(luò)共可使用N個(gè)正交信道，每個(gè)節(jié)點(diǎn)都將測(cè)量的計(jì)量數(shù)據(jù)發(fā)送到其下一個(gè)躍點(diǎn)，當(dāng)每個(gè)節(jié)點(diǎn)從其所有子節(jié)點(diǎn)中接收數(shù)據(jù)時(shí)，它將從子節(jié)點(diǎn)接收到的數(shù)據(jù)加以聚合并附上自己的測(cè)量數(shù)據(jù)，然后將聚合數(shù)據(jù)包發(fā)送到下一個(gè)躍點(diǎn)，一旦所有節(jié)點(diǎn)完成向接收節(jié)點(diǎn)發(fā)送全部數(shù)據(jù)包，整個(gè)網(wǎng)絡(luò)就進(jìn)入休眠模式。根據(jù)智能電網(wǎng)中使用低功耗射頻收發(fā)器模塊的實(shí)驗(yàn)，切換射頻通道的時(shí)間可以忽略不計(jì)，而且切換開(kāi)銷不會(huì)產(chǎn)生額外的功耗。

1.2 問(wèn)題描述

在一個(gè)具有有限正交信道生成樹(shù)的多跳無(wú)線傳感器網(wǎng)絡(luò)中，兩個(gè)不同信道的節(jié)點(diǎn)可共享一個(gè)時(shí)隙，而傳輸調(diào)度的目標(biāo)正是為所有節(jié)點(diǎn)分配時(shí)隙，使所有節(jié)點(diǎn)使用有限的正交通道并以非常低的延遲進(jìn)行數(shù)據(jù)傳輸，且確保消耗最少的能量。

本研究的目標(biāo)是在有限可用信道的前提下，最小化分配所有節(jié)點(diǎn)傳輸所需要的時(shí)隙總數(shù)。給定的圖G=(V,E)有n個(gè)節(jié)點(diǎn)，V1[n],V2[n],…,Vn[n]為每個(gè)節(jié)點(diǎn)ni的n個(gè)二進(jìn)制變量的位置數(shù)組。Vi[k]表示時(shí)隙k中節(jié)點(diǎn)ni的狀態(tài)，當(dāng)ni在時(shí)隙k處于活躍模式并等待傳輸時(shí)，Vi[k]的數(shù)值為1；當(dāng)ni完成傳輸并在時(shí)隙k處于休眠模式時(shí)，Vi[k]的數(shù)值設(shè)置為0。換言之，若Vi[k]=1，則Vi[k+1]=0。

為了獲得盡可能低的功耗，所有節(jié)點(diǎn)都應(yīng)盡早發(fā)送并切換到休眠模式。這個(gè)目標(biāo)可以被表述為最小化所有二進(jìn)制數(shù)組變量的總和，即盡早為節(jié)點(diǎn)分配時(shí)間槽以進(jìn)行傳輸。基于此，將此優(yōu)化問(wèn)題作為二元線性規(guī)劃(binary linear programming, BLP)問(wèn)題加以提出，BLP的目標(biāo)函數(shù)為

(1)

BLP的約束條件可以通過(guò)以下方式加以定義。

(1)時(shí)隙狀態(tài)約束。每個(gè)節(jié)點(diǎn)只傳輸一次數(shù)據(jù)，傳輸后的數(shù)據(jù)節(jié)點(diǎn)不能返回前一狀態(tài)，即下一狀態(tài)始終較小或相等：

對(duì)?i?k，有Vi[k]≥Vi[k+1]。

(2)

(2)路由約束。節(jié)點(diǎn)按照?qǐng)DG=(V,E)中指定集合E中的有向邊傳輸數(shù)據(jù)，針對(duì)集合E中所有的有向邊Ei：Vi→Vj，Vi必須在下一跳節(jié)點(diǎn)傳輸前進(jìn)行傳輸，且子節(jié)點(diǎn)應(yīng)在節(jié)點(diǎn)傳輸之前進(jìn)行傳輸：

(3)

(3)單個(gè)無(wú)線約束。每個(gè)節(jié)點(diǎn)都有單個(gè)無(wú)線，故只能在一個(gè)時(shí)間段內(nèi)使用一個(gè)節(jié)點(diǎn)進(jìn)行接收或發(fā)送，且每個(gè)節(jié)點(diǎn)的邊緣都必須在不同的槽中傳輸數(shù)據(jù)。在給定圖G=(V,E)中，若Ei：Vi→Vj和Ej：Vl→Vj為節(jié)點(diǎn)Vj的兩條有向邊，則

對(duì)?k，有(Vi[k]-Vi[k+1])+(Vl[k]-Vl[k+1])≤1。

(4)

(4)信道限制約束。根據(jù)網(wǎng)絡(luò)體系結(jié)構(gòu)中的定義，網(wǎng)絡(luò)系統(tǒng)只有n個(gè)正交信道可供使用，意味著在給定的時(shí)間段內(nèi)最多可以發(fā)生n次傳輸：

(5)

式中：Vi[k]是一個(gè)二值變量，取值范圍為{0, 1}。

2 本方法

2.1 二元線性方程的實(shí)現(xiàn)

采用C語(yǔ)言實(shí)現(xiàn)了路由算法生成樹(shù)圖G=(V,E)，使用生成的預(yù)定義路由路徑作為BLP中式(1)～(5)的輸入。為了驗(yàn)證BLP中式(1)～(5)的有效性，模擬了兩個(gè)分別具有21個(gè)節(jié)點(diǎn)和26個(gè)節(jié)點(diǎn)的傳感器網(wǎng)絡(luò)。需要指出的是，本研究采用CPLEX[11]進(jìn)行二元線性規(guī)劃問(wèn)題的求解。

2.2 仿真結(jié)果

前面提出的BLP公式確定了目標(biāo)無(wú)線傳感器網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)向接收節(jié)點(diǎn)傳輸數(shù)據(jù)所需要的最小時(shí)隙分配。下面給出兩個(gè)傳感器網(wǎng)絡(luò)實(shí)驗(yàn)，假設(shè)可用信道數(shù)為4，則網(wǎng)絡(luò)消耗的總能量計(jì)算如下：

EC=NNodes×ETX+ActiveNodes×Eactive，

(6)

式中：EC表示能量消耗值；傳輸能量ETX是傳輸聚合數(shù)據(jù)包時(shí)每個(gè)節(jié)點(diǎn)的無(wú)線電消耗能量；活動(dòng)能量Eactive是每個(gè)活動(dòng)節(jié)點(diǎn)在一個(gè)時(shí)段內(nèi)消耗的能量。簡(jiǎn)單起見(jiàn)，在該實(shí)驗(yàn)中假定ETX和Eactive均為1 MJ。

在具有21個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中共有20個(gè)傳感器節(jié)點(diǎn)和一個(gè)接收器節(jié)點(diǎn)，接收節(jié)點(diǎn)用節(jié)點(diǎn)N0加以表示，如圖1所示。圖2給出了本方法的仿真結(jié)果。圖3給出了基于文獻(xiàn)[11]的多信道調(diào)度方法的仿真結(jié)果。該方法結(jié)合跨層設(shè)計(jì)理論，提出了一種基于MAC層和路由層間信道信息交換機(jī)制的跨層多信道分配CMA-AODV協(xié)議，可以在一定程度上改善網(wǎng)絡(luò)吞吐量等性能。其中，圖2的能量消耗為92 MJ，圖3的能量消耗為106 MJ。

在具有26個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中共有25個(gè)傳感器節(jié)點(diǎn)和1個(gè)接收器節(jié)點(diǎn)，如圖4所示。圖5給出了本方法的仿真結(jié)果，圖6給出了基于文獻(xiàn)[12]的多信道調(diào)度方法的仿真結(jié)果。其中，圖5的能量消耗為126 MJ，圖6的能量消耗為177 MJ。

圖1 具有21個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)Fig.1 Twenty-first nodes network

圖2 21個(gè)節(jié)點(diǎn)的BLP時(shí)隙分配Fig.2 BLP slot allocation of twenty-first nodes

圖3 21個(gè)節(jié)點(diǎn)的多信道時(shí)隙分配Fig.3 Multi-channel slot allocation of twenty-first nodes

圖4 具有26個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)Fig.4 Twenty-six nodes network

圖5 26個(gè)節(jié)點(diǎn)的BLP時(shí)隙分配Fig.5 BLP slot allocation of twenty-six nodes

圖6 26個(gè)節(jié)點(diǎn)的多信道時(shí)隙分配Fig.6 Multi-channel slot allocation of twenty-six nodes

綜上所述，本方法在運(yùn)行過(guò)程中需要的時(shí)間間隙較少，消耗的能量值也較低，具有顯著的優(yōu)勢(shì)。

3 結(jié)語(yǔ)

本研究提出了一種低功耗的多信道無(wú)線傳感器網(wǎng)絡(luò)調(diào)度方法，通過(guò)求解二元線性規(guī)劃問(wèn)題，以最大限度降低各節(jié)點(diǎn)的能量消耗為目標(biāo)，得出了各節(jié)點(diǎn)的最優(yōu)時(shí)隙分配，并用仿真實(shí)驗(yàn)驗(yàn)證了本方法的優(yōu)越性。