無線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度雙層規(guī)劃方法

代亮，沈中，常義林，張穎，閆中江

(西安電子科技大學(xué) 綜合業(yè)務(wù)網(wǎng)理論與關(guān)鍵技術(shù)國家重點實驗室，陜西 西安710071)

0 引言

由于無線傳感器網(wǎng)絡(luò)中節(jié)點帶有有限的能量，任務(wù)調(diào)度的關(guān)鍵問題是如何恰當(dāng)?shù)胤峙淇側(cè)蝿?wù)到相應(yīng)的節(jié)點上，以使得從SINK 節(jié)點下發(fā)任務(wù)到收到融合后的結(jié)果這段時間最短。

用于無線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度應(yīng)用建模的工具通常是有向無環(huán)圖(DAG)和獨立任務(wù)集。在一般情況下，基于這2 類模型的調(diào)度問題都是NP 完全的。與此形成鮮明對比的是可分負(fù)載理論(Divisible load theory)［1］。在一定條件下，可分負(fù)載理論可以得到最優(yōu)解的解析解。

文獻(xiàn)［2］首次將可分負(fù)載理論應(yīng)用于無線傳感器網(wǎng)絡(luò)上來進(jìn)行任務(wù)調(diào)度分析。其應(yīng)用環(huán)境是，對于一個具體的數(shù)據(jù)采樣空間來說，互不重疊地給每一個傳感器節(jié)點分配一個采集子空間來采集數(shù)據(jù)。例如，采樣空間覆蓋一個很大的頻率范圍，可按照一定比例劃分采集子空間，分配給不同的傳感器來采集數(shù)據(jù)，以節(jié)省總?cè)蝿?wù)完成時間及能耗。但是該文只是應(yīng)用到了單層樹型結(jié)構(gòu)。而在無線傳感器網(wǎng)絡(luò)中，與單層樹型結(jié)構(gòu)相比分群結(jié)構(gòu)(即多層樹形結(jié)構(gòu))具有很大優(yōu)勢［3］。文獻(xiàn)［4］在文獻(xiàn)［2］的基礎(chǔ)上，增加了對數(shù)據(jù)采集和網(wǎng)絡(luò)通信中存在的延時的分析，但其網(wǎng)絡(luò)拓?fù)溥€是單層樹型結(jié)構(gòu)。文獻(xiàn)［5］將可分負(fù)載理論應(yīng)用于無線傳感器網(wǎng)狀網(wǎng)(Wireless sensor mesh networks)中來分析任務(wù)調(diào)度，其任務(wù)下發(fā)到結(jié)果上報也是基于單層樹型結(jié)構(gòu)的。文獻(xiàn)［6］將可分負(fù)載理論用于只有單個群的無線傳感器網(wǎng)絡(luò)中，分析了可行的指令下發(fā)時間和最短的總體完工時間。但由于分群結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)都具有多個群，具有單個群的無線傳感器網(wǎng)絡(luò)沒有太大的實用性，在這種網(wǎng)絡(luò)結(jié)構(gòu)下分析具有片面性。

本文基于可分負(fù)載理論，建立了雙層規(guī)劃［7］模型對分群結(jié)構(gòu)無線傳感器網(wǎng)絡(luò)的任務(wù)調(diào)度進(jìn)行優(yōu)化，同時考慮了群間和群內(nèi)任務(wù)分配的合理性，目標(biāo)是得到在網(wǎng)絡(luò)中SINK 節(jié)點給群首節(jié)點，群首節(jié)點給群內(nèi)節(jié)點分配任務(wù)比例的最優(yōu)解，以使SINK 節(jié)點從分配任務(wù)到完全得到任務(wù)執(zhí)行結(jié)果的時間最短。

由于在無線傳感器網(wǎng)絡(luò)分群結(jié)構(gòu)下，群首節(jié)點負(fù)責(zé)SINK 節(jié)點和群內(nèi)節(jié)點的數(shù)據(jù)交互。為了減少冗余數(shù)據(jù)的傳輸耗能，降低延遲，延長網(wǎng)絡(luò)的生存期，在群首節(jié)點需要進(jìn)行數(shù)據(jù)融合［8］。本文基于文獻(xiàn)［9］采用了信息效用常量方法。信息效用常量基于信息正確性估計技術(shù)，通過信息正確性估計，群首節(jié)點可以知道近似的數(shù)據(jù)融合比例。

1 問題描述

本文所討論的無線傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖1所示，網(wǎng)絡(luò)中一共有k 個群，分別表示為Clusteri，i=1，…，k，每個群內(nèi)群首節(jié)點分別表示為Ci，i=1，…，k，群內(nèi)分別有ni，i =1，…，k 個節(jié)點，群首和SINK節(jié)點的通信鏈路分別表示為li，i =1，…，k.群內(nèi)的普通節(jié)點分別表示為nij(i =1，…，k;j =1，…，ni);群內(nèi)節(jié)點和群首的通信鏈路分別用lij(i =1，…，k;j=1，…，ni)來表示。

yij是節(jié)點nij相對于標(biāo)準(zhǔn)處理器的數(shù)據(jù)采集速度;zij是第lij條鏈路相對于標(biāo)準(zhǔn)鏈路的傳輸速度;wi是群首Ci相對于標(biāo)準(zhǔn)處理器的計算(數(shù)據(jù)融合)速度;zi是第li條鏈路相對于標(biāo)準(zhǔn)鏈路的傳輸速度;φi是群首Ci的信息效用常量。

所謂的標(biāo)準(zhǔn)處理器和鏈路是作為參照的任何一個處理器和鏈路，可以是網(wǎng)絡(luò)中的任何一個處理器和鏈路，甚至為了方便可以是假想的處理器和鏈路。

SINK 節(jié)點首先將負(fù)載劃分為k 個部分，將這些子負(fù)載發(fā)送給k 個群首。第i 個群首Ci再將其負(fù)責(zé)的負(fù)載劃分為ni個部分并將其發(fā)送給群內(nèi)的ni個節(jié)點。定義αi是SINK 節(jié)點分配給群首Ci的負(fù)載百分比;αij是群首節(jié)點Ci分配給群內(nèi)普通節(jié)點nij的負(fù)載百分比。由定義可知:

圖1 網(wǎng)絡(luò)拓?fù)鋱DFig.1 Network topology

定義Tms是整個采集業(yè)務(wù)在標(biāo)準(zhǔn)處理器上完成的時間，Tcm是在標(biāo)準(zhǔn)鏈路上傳輸這個應(yīng)用的全部輸入數(shù)據(jù)的時間，Tcp是整個應(yīng)用在標(biāo)準(zhǔn)處理器上數(shù)據(jù)融合的時間［2］。因此αijyijTms是節(jié)點nij采集相應(yīng)負(fù)載的時間，αijzijTcm是節(jié)點nij通過第lij條鏈路向群首Ci發(fā)送相應(yīng)采集數(shù)據(jù)的時間，αiwiTcp是群首Ci融合群內(nèi)節(jié)點報告的數(shù)據(jù)的時間，φiαiziTcm是群首Ci將融合后的數(shù)據(jù)報告SINK 節(jié)點所需的時間。

ti是第i 個群的群內(nèi)處理時間(數(shù)據(jù)采集，報告群首)，Ti是網(wǎng)絡(luò)中第i，i=1，…，k，個群完成相應(yīng)的負(fù)載并報告SINK 節(jié)點所需的時間，Tf是整個系統(tǒng)響應(yīng)的時間。調(diào)度的目標(biāo)是整個負(fù)載的處理時間Tf最小，即各個群完成相應(yīng)任務(wù)，數(shù)據(jù)融合后并報告SINK 節(jié)點所需時間Ti的最大值，即Tf=max{T1，T2，…，Tk}.

由于和其他執(zhí)行過程的耗時相比較，SINK 節(jié)點和群首節(jié)點下發(fā)任務(wù)給相應(yīng)節(jié)點的耗時是微不足道的。故在本文中，忽略SINK 節(jié)點，群首節(jié)點下發(fā)任務(wù)的耗時。

2 調(diào)度模型

本文考慮的任務(wù)調(diào)度模型基于可分負(fù)載理論，如圖2所示:群內(nèi)節(jié)點同時開始采集數(shù)據(jù)，假設(shè)群內(nèi)節(jié)點共享同一信道，為了去除通信的干擾和空閑導(dǎo)致的性能下降，群內(nèi)節(jié)點采集完相應(yīng)的數(shù)據(jù)后相繼向群首報告采集結(jié)果。群首節(jié)點收集群內(nèi)節(jié)點采集的數(shù)據(jù)并作數(shù)據(jù)融合后，假設(shè)各群首間也共享同一信道，故也只能相繼向SINK 節(jié)點報告數(shù)據(jù)。

圖2 本文調(diào)度策略的時序圖Fig.2 Timing diagram of this scheduling strategy

將SINK 節(jié)點給群首節(jié)點，群首節(jié)點給群內(nèi)節(jié)點任務(wù)分配的優(yōu)化視作一個領(lǐng)導(dǎo)者(Leader)-跟從者(Follower)問題。

上層規(guī)劃可以描述為SINK 節(jié)點在滿足可分負(fù)載條件下確定給群首節(jié)點分配任務(wù)的比例，使得總?cè)蝿?wù)完成時間最小;下層規(guī)劃描述了群首節(jié)點確定給群內(nèi)節(jié)點分配任務(wù)的比例，使得該群所獲子任務(wù)的完成時間最小。

由圖2可知，對于上層規(guī)劃來說，其數(shù)學(xué)模型為:

當(dāng)上層模型達(dá)到最優(yōu)時，即確定了各群首獲得SINK 下發(fā)的子任務(wù)比例αi，則下層規(guī)劃便根據(jù)上層規(guī)劃確定的各群首的任務(wù)比例αi，尋求最優(yōu)的群內(nèi)分配方案，以確定群內(nèi)節(jié)點應(yīng)該獲得的任務(wù)比例αi，j.約束條件式(3)表明了，由于各群首與SINK 間共享信道，各個群首相繼將群內(nèi)處理的結(jié)果融合后發(fā)送至SINK.約束條件(4)表明了總?cè)蝿?wù)執(zhí)行完畢。

對于下層規(guī)劃來說其數(shù)學(xué)模型為

我們把上述雙層規(guī)劃歸結(jié)成一個值型雙層規(guī)劃。上層規(guī)劃確定了各個群應(yīng)該獲得的最合理的任務(wù)比例αi，下層規(guī)劃確定各個群內(nèi)節(jié)點所獲得的最合理的任務(wù)比例αi，j，以求得最小的總?cè)蝿?wù)完成時間。其中:αi和Tf分別為上層問題的決策變量和目標(biāo)函數(shù);αi，j和ti分別為下層問題的決策變量和目標(biāo)函數(shù)。約束(5)表明了由于群內(nèi)各節(jié)點共享信道，群內(nèi)節(jié)點相繼將采集的結(jié)果發(fā)送至群首。約束條件(6)說明每個群內(nèi)的所有節(jié)點共同執(zhí)行完該群的子任務(wù)。

雙層規(guī)劃模型的數(shù)學(xué)求解方法主要有K 次極點搜索法，分支定界法和罰函數(shù)法3 種［7］。本文利用罰函數(shù)原理，將線性雙層規(guī)劃轉(zhuǎn)化為目標(biāo)函數(shù)帶懲罰項的單層問題，來進(jìn)行本文的雙線性規(guī)劃模型的求解。

3 能量消耗模型

在本節(jié)，提出了分群結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)能量消耗模型。在本文中，有4 種不同的能量消耗方式，分別是:數(shù)據(jù)采集，數(shù)據(jù)報告，數(shù)據(jù)接收和數(shù)據(jù)融合。在網(wǎng)絡(luò)中，普通群內(nèi)節(jié)點執(zhí)行數(shù)據(jù)采集和數(shù)據(jù)報告;群首節(jié)點執(zhí)行數(shù)據(jù)報告，數(shù)據(jù)接收和數(shù)據(jù)融合;SINK 節(jié)點執(zhí)行數(shù)據(jù)接收。

在本文中，采用基于LEACH 協(xié)議［10］的一階無線電模型來構(gòu)造能量消耗公式。LEACH 協(xié)議的一階無線電模型基于以下假設(shè):1)網(wǎng)絡(luò)中所有節(jié)點完全相同;2)無線電信號在各個方向上能量消耗相同;3)SINK 節(jié)點是固定的，并且離整個網(wǎng)絡(luò)較遠(yuǎn)。

定義網(wǎng)路內(nèi)節(jié)點采集，融合，報告，接收一單位數(shù)據(jù)所消耗的能量為分別為:es，ep，etx，erx;報告和發(fā)送節(jié)點間的距離均為d.

根據(jù)一階無線電模型，可得第i 個群中第j 個節(jié)點的能量消耗為:

群首Ci的能量消耗為

SINK 節(jié)點的能量消耗為

4 仿真分析

在以上章節(jié)，我們得到了給定任務(wù)完成時間的封閉表達(dá)式和各個節(jié)點的能量消耗公式。在本章，我們對采集速度，通信速度，數(shù)據(jù)融合速度和信息效用常量這4 個系統(tǒng)參數(shù)在同構(gòu)網(wǎng)絡(luò)環(huán)境下，對任務(wù)完成時間和群內(nèi)節(jié)點能量消耗的影響進(jìn)行了仿真分析。

在仿真中，能量消耗參數(shù)如下所示:在一單位距離上，報告一單位數(shù)據(jù)所消耗的能量為etx=200 nJ;采集一單位數(shù)據(jù)所消耗的能量為es=100 nJ;報告、接收節(jié)點間的距離均為d =100 m，每個群里有30個節(jié)點。在仿真中令Tms=Tcm=Tcp=1.

因為在無線傳感器網(wǎng)絡(luò)中，SINK 節(jié)點一般沒有能量限制，而且在現(xiàn)有的無線傳感器網(wǎng)絡(luò)分群協(xié)議中，當(dāng)群穩(wěn)定后，群首節(jié)點相對來說也是能量有保障的，所以在本文中，只考察群內(nèi)節(jié)點的能耗情況。不失一般性，本文以第一個群中的節(jié)點來考察群內(nèi)各個節(jié)點的能耗情況。

因為群數(shù)目增加，整個網(wǎng)絡(luò)中節(jié)點的數(shù)目就會增加。網(wǎng)絡(luò)中協(xié)作完成任務(wù)的機會也就會更多，但用于報告的開銷又會增大。分別考察參數(shù)y，z，w，φ隨著群的數(shù)目的增加，對系統(tǒng)總?cè)蝿?wù)完成時間的影響，和隨著負(fù)載分配的次序?qū)θ簝?nèi)節(jié)點能耗的影響。總體上來說，隨著群數(shù)目的增加，總?cè)蝿?wù)完成時間遞減;隨著群內(nèi)各節(jié)點所承載的負(fù)載遞減，各節(jié)點的能量消耗遞減。

1)y，z，w 固定，令w=y=z =1.0，φ 分別取0.2，0.4，0.6，0.8，1.0.如圖3(a)所示，隨著群數(shù)目的增大，系統(tǒng)完成時間逐漸減小。信息效用常量越大，其系統(tǒng)完成時間減小的趨勢越緩。如圖4(a)所示，φ 的選取對于群內(nèi)各節(jié)點的能耗情況幾乎沒有影響。隨著群內(nèi)負(fù)載的分配次序，各節(jié)點能耗遞減。

2)φ，z，y 固定，令y=z=1.0，φ=0.5，w 分別取0.8，1.0，1.2，1.4，1.6.如圖3(b)所示，隨著網(wǎng)絡(luò)中群數(shù)目的增加，系統(tǒng)總?cè)蝿?wù)完成時間會減少。如圖4(b)所示，隨著群內(nèi)負(fù)載分配的次序，群內(nèi)節(jié)點的能耗遞減。

3)φ，z，w 固定，令w =z =1.0，φ =0.5，y 分別取0.8，1.0，1.2，1.4，1.6.如圖3(c)所示，由于數(shù)據(jù)采集只占據(jù)了總?cè)蝿?wù)完成時間的很小一部分，所以傳感器節(jié)點的數(shù)據(jù)采集速度的增大，對系統(tǒng)完成時間幾乎沒有影響。如圖4(c)所示，群內(nèi)節(jié)點采集數(shù)據(jù)的速度越大，群首可將負(fù)載更加均衡地分配給各個節(jié)點，所以各個節(jié)點的能耗越小。

4)φ，w，y 固定，令y =w =1.0，φ =0.5，z 分別取0.8，1.0，1.2，1.4，1.6.如圖3(d)所示，隨著群數(shù)目的增大，系統(tǒng)的完成時間會減少。節(jié)點間的通信速度越大，其系統(tǒng)完成時間減小的趨勢越緩。如圖4(d)所示，節(jié)點間的通信速度越大，群內(nèi)節(jié)點的能耗越小。

圖3 各參數(shù)對本文任務(wù)調(diào)度模型完成任務(wù)耗時的影響Fig.3 Impact of these four parameters on finish time

5 結(jié)論

由于無線傳感器網(wǎng)絡(luò)中的節(jié)點帶有有限的能量，所以網(wǎng)絡(luò)應(yīng)該盡可能快的完成系統(tǒng)任務(wù)?？煞重?fù)載理論在無線傳感器網(wǎng)絡(luò)上的應(yīng)用為其任務(wù)調(diào)度提供了一個有效的解決方案。本文建立雙層規(guī)劃模型對分群結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)的任務(wù)調(diào)度進(jìn)行優(yōu)化，同時考慮了群間和群內(nèi)任務(wù)分配的合理性，得到了在網(wǎng)絡(luò)中SINK 節(jié)點給群首節(jié)點、群首節(jié)點給群內(nèi)節(jié)點分配任務(wù)比例的最優(yōu)解，以使SINK 節(jié)點從分配任務(wù)到完全得到任務(wù)執(zhí)行結(jié)果的時間最短。

隨著無線傳感器網(wǎng)絡(luò)技術(shù)和泛在網(wǎng)絡(luò)的逐步發(fā)展，可分負(fù)載理論對這種復(fù)雜網(wǎng)絡(luò)的建模與擴展也需要進(jìn)一步研究及驗證。此外，目前對可分負(fù)載理論在無線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度的驗證仍停留在仿真試驗階段，缺乏大型的，實際的應(yīng)用來證明它的真正潛力，因此可分負(fù)載理論在實際無線傳感器網(wǎng)絡(luò)的應(yīng)用將是下一步研究的重要方向。

圖4 各參數(shù)對本文任務(wù)調(diào)度模型群內(nèi)各節(jié)點能耗的影響Fig.4 Impact of these four parameters on energy consumption of each in-cluster nodes

References)

［1］Bharadwaj V，Ghose D，Robertazzi T G.Divisible load theory:a new paradigm for load scheduling in distributed systems ［J］.Cluster Computing，2003，6(1):7 -18.

［2］Moges M，Robertazzi T G.Wireless sensor networks:scheduling for measurement and data reporting［J］.IEEE Transactions on Aerospace and Electronic Systems，2006，42(1):327 -340.

［3］劉麗萍，王智，孫優(yōu)賢.無線傳感器網(wǎng)絡(luò)連接問題研究［J］.兵工學(xué)報，2007，28(9):1096 -1102.LIU Li-ping，WAN Zhi，SUN You-xian.Connectivity in wireless sensor networks［J］.Acta Armamentarii，2007，28(9):1096 -1102.(in Chinese)

［4］LIU Hao-ying，YUAN Xiao-jing，MOGES M.An efficient task scheduling method for improved network delay in distributed sensor networks［C］∥Proceedings of the International Conference on Testbeds and Research Infra-structure for the Development of Networks and Communities.Los Alamitos:IEEE Computer Society，2007:1 -8.

［5］LIU Hao-ying，SHEN Jian，YUAN Xiao-jing，Moges M.Performance analysis of data aggregation in wireless sensor mesh networks［C］∥Proceedings of the International Conference on Engineering，Science，Construction and Operations in Challenging Environments.Los Alamitos:IEEE Computer Society，2008:1 -8.

［6］Kijeung Choi，Robertazzi T G.Divisible load scheduling in wireless sensor networks with information utility performance［C］∥Proceedings of the International Performance Computing and Communications Conference.Piscataway:IEEE，2008:9 -17.

［7］王先甲，馮尚友.二層系統(tǒng)最優(yōu)化理論［M］.北京:科學(xué)出版社，1995:12 -120.WANG Xian-jia，F(xiàn)ENG Shang-you.Optimality theory of bi-level systems［M］.Beijing:Science Press，1995:12 -120.

［8］鄧克波，劉中.基于無線傳感器網(wǎng)絡(luò)動態(tài)簇的目標(biāo)跟蹤［J］.兵工學(xué)報，2008，29(10):1197 -1202.DENG Ke-bo，LIU Zhong.Target tracking with dynamic clusters in wireless sensor network［J］.Acta Aramamentarii，2008，29(10):1197 -1202.(in Chinese)

［9］Lin Jianyong，Xiao Wendong，Lewis F L，et al.Energy-efficient distributed adaptive multisensor scheduling for target tracking in wireless sensor networks［J］.IEEE Transactions on Instrumentation and Measurement，2009，58(6):1886 -1896.

［10］Heinzelman W，Chandrakasan A.An application-specifid protocol architecture for wireless microsensor networks［J］.IEEE Transaction on Wireless Communications，2002，1(4):660 -670.