喬 蕊，李 靖

（周口師范學(xué)院計算機科學(xué)與技術(shù)學(xué)院，河南周口466001）

報告匯聚節(jié)點子任務(wù)Wi的最小測量時間為：

基于負載分割理論的無線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度算法

喬 蕊，李 靖

（周口師范學(xué)院計算機科學(xué)與技術(shù)學(xué)院，河南周口466001）

利用分簇思想和負載分割理論，提出基于一種集群結(jié)構(gòu)的無線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度算法。將整個無線傳感器網(wǎng)絡(luò)劃分為多個簇進行負載分割，采用簇間和簇內(nèi)任務(wù)調(diào)度建立任務(wù)執(zhí)行過程的時序圖，通過最小化總?cè)蝿?wù)時間，實現(xiàn)任務(wù)所需數(shù)據(jù)測量、融合和傳輸時間的合理分配，達到任務(wù)的最優(yōu)調(diào)度。仿真實驗結(jié)果表明，該算法能縮短任務(wù)執(zhí)行時間，并減少節(jié)點在任務(wù)執(zhí)行過程中的能量消耗。

無線傳感器網(wǎng)絡(luò)；任務(wù)調(diào)度；網(wǎng)絡(luò)分簇；負載分割理論；節(jié)點能耗

1 概述

在最短時間內(nèi)傳感器之間的傳感任務(wù)只有被及時分配和處理才能保證用戶快速獲取傳感數(shù)據(jù)，且快速分配和執(zhí)行任務(wù)有助于減少系統(tǒng)能量消耗。有向無環(huán)圖和獨立任務(wù)集通常作為傳感器任務(wù)調(diào)度的建模工具，但這2種模型的調(diào)度問題是一個NP難問題［1-2］。為有效解決無線傳感器網(wǎng)絡(luò)（Wireless Sensor Netw ork，WSN）的任務(wù)調(diào)度問題，本文基于啟發(fā)式方法，采用負載分割理論得到任務(wù)調(diào)度的最優(yōu)解決方案。負載分割理論可以使給定的任務(wù)在最短時間內(nèi)獲得最佳分割和調(diào)度策略。在采用負載分割理論對傳感器網(wǎng)絡(luò)進行處理時，所采用的網(wǎng)絡(luò)拓撲結(jié)構(gòu)為單級樹狀結(jié)構(gòu)或集群結(jié)構(gòu)（均質(zhì)多級樹形結(jié)構(gòu)）。雖然在無線傳感器網(wǎng)絡(luò)中［3-4］，單級樹狀結(jié)構(gòu)簡單、容易實現(xiàn)，但并不適合于采用負載分割理論的無線傳感器網(wǎng)絡(luò)［5-6］。因此，本文提出的基于負載分割理論的傳感器網(wǎng)絡(luò)采用集群結(jié)構(gòu)進行分析，通過最小化總?cè)蝿?wù)時間，使得集群算法可以對網(wǎng)絡(luò)進行有效分簇，實現(xiàn)多個子任務(wù)劃分，同時充分利用網(wǎng)絡(luò)資源，達到任務(wù)的最優(yōu)調(diào)度。

2 相關(guān)工作

文獻［7］提出一種WSN中基于多目標(biāo)優(yōu)化的協(xié)同任務(wù)分配算法，建立基于動態(tài)聯(lián)盟的、具有跟蹤精度、系統(tǒng)能耗、負載均衡等多個目標(biāo)參數(shù)的優(yōu)化模型，并基于折中度的決策精選策略，從最優(yōu)解集中選出最終的任務(wù)分配方案，該算法可以獲得較好的任務(wù)調(diào)度結(jié)果。文獻［8］提出一種無線傳感器網(wǎng)絡(luò)可分負載調(diào)度算法，該算法在群內(nèi)調(diào)度階段，采用群內(nèi)節(jié)點共享同一信道，相繼向群首發(fā)送數(shù)據(jù)的方式，而在群間調(diào)度階段，采用群首節(jié)點和Sink節(jié)點之間獨立的信道使得群首將群內(nèi)節(jié)點報告的數(shù)據(jù)融合，可以減少總?cè)蝿?wù)完成時間，提高資源利用率。文獻［9］提出一種無線傳感器網(wǎng)絡(luò)中帶復(fù)雜聯(lián)盟的自適應(yīng)任務(wù)分配算法，以節(jié)點能耗和網(wǎng)絡(luò)能量分布平衡為優(yōu)化目標(biāo)，并且采用矩陣的二進制編碼形式，通過設(shè)計一種離散粒子群優(yōu)化算法以并行生成聯(lián)盟，并執(zhí)行基于負載和能量平衡的子任務(wù)分配算法，能夠在較短時間內(nèi)得到較好的任務(wù)調(diào)度解。文獻［10］提出無線傳感器網(wǎng)絡(luò)分布式數(shù)據(jù)鏈路（Data Link，DL）推理任務(wù)的上下文感知任務(wù)調(diào)度算法，該算法結(jié)合無線傳感器網(wǎng)絡(luò)和分布式本體進行一致推理，基于本體的方法和DL推理來優(yōu)化帶寬利用率和功率消耗。文獻［11］提出一種多功能無線傳感器網(wǎng)絡(luò)系統(tǒng)并發(fā)應(yīng)用的節(jié)能任務(wù)分配算法，采用一種新的資源分配啟發(fā)式的多功能無線傳感器網(wǎng)絡(luò)系統(tǒng)，以最大限度地提高系統(tǒng)壽命，通過有效的啟發(fā)式與服務(wù)參數(shù)進行任務(wù)調(diào)度，最大化地利用網(wǎng)絡(luò)資源，減少能量損耗。

3 面向任務(wù)調(diào)度的WSN系統(tǒng)場景分析

假設(shè)無線傳感器網(wǎng)絡(luò)在其生命周期構(gòu)建多個集群，每個集群有一個建立階段和穩(wěn)態(tài)階段，假設(shè)在穩(wěn)態(tài)階段有K個簇網(wǎng)絡(luò)［16-18］，每個簇頭表示為Ci，在每一個簇Gi內(nèi)，有j個節(jié)點表示為，簇頭和匯聚節(jié)點Si之間的通信鏈路表示為li（i≤K）。在簇內(nèi)節(jié)點和簇頭之間的通信鏈路表示為（

系統(tǒng)場景需要用到的符號表示如下：Wi表示通過匯聚節(jié)點分配到簇頭Ci的負載總數(shù)；表示在簇Gi內(nèi)分配給群集內(nèi)節(jié)點的負載數(shù)，其中，Wi和分別滿足：表示一個簇頭Ci的處理（數(shù)據(jù)融合）速度成反比的常量。表示一個與簇內(nèi)節(jié)點nij的感測速度成反比的常量。表示一個與簇頭Ci和簇內(nèi)節(jié)點之間的鏈路速度成反比的常量。TD表示當(dāng)λi=1時在一個簇頭融合所有負載所需的時間。λiTDbi表示在簇頭Ci融合負載所需的時間。TE表示當(dāng)λi=1時采用簇內(nèi)節(jié)點感測整個負載時間，在簇內(nèi)的節(jié)點上所有被分配的負載被感測出所用的時間為表示通信強度不變時，當(dāng)時它需要發(fā)送的所有處理負荷。整個負載可以通過第i條鏈路傳輸，所用時間為ψ表示簇頭C的效用信息。T表示一個給iiK定任務(wù)的完成時間。本文將大規(guī)模傳感器網(wǎng)絡(luò)中的任務(wù)調(diào)度問題進行優(yōu)化，通過盡可能地減少TK提高任務(wù)完成速度。

4 簇內(nèi)任務(wù)調(diào)度模型

圖1給出了一組簇內(nèi)任務(wù)處理時序圖。從圖1可以看出，每2個連續(xù)的節(jié)點之間沒有時間差，因為可分配的工作量能夠在簇中進行轉(zhuǎn)移。所有節(jié)點在同一時間開始測量數(shù)據(jù)。一旦一個節(jié)點完成傳輸數(shù)據(jù)的任務(wù)，另外一個節(jié)點完成測量任務(wù)并開始報告其數(shù)據(jù)。最后所提出的時序圖通過安排每個節(jié)點的測量時間和報告時間來最小化任務(wù)完成時間。

圖1 簇內(nèi)任務(wù)處理時序圖

對于簇頭Ci，基于圖1所示的時序圖，在簇Gi內(nèi)任務(wù)分配給簇內(nèi)節(jié)點可以表示如下：

其中：

簇頭Ci使用獲取j-1個剩余的傳感器所測量到的數(shù)據(jù)量，表示為：

報告匯聚節(jié)點子任務(wù)Wi的最小測量時間為：

5 簇間任務(wù)調(diào)度模型

在簇頭融合了簇內(nèi)節(jié)點的數(shù)據(jù)后，簇頭可以通過一個單獨的信道發(fā)送融合數(shù)據(jù)給匯聚節(jié)點。為提高任務(wù)工作效率，減少節(jié)點閑置所帶來的性能下降問題，如圖2的任務(wù)調(diào)度時序圖所示，可以得到：

圖2 簇間任務(wù)調(diào)度時序圖

將式（6）簡化為：

將σi引入到式（7）中，可以得到：

得到簇頭Ci從匯聚節(jié)點接收到的負載量Wi和簇內(nèi)節(jié)點從匯聚節(jié)點接收到的負載量所得到的總?cè)蝿?wù)執(zhí)行時間如下：

無線傳感器網(wǎng)絡(luò)每個簇內(nèi)的傳感器網(wǎng)絡(luò)參數(shù)，具體如下：測量速度λ，通信速度η，數(shù)據(jù)融合速度θ和信息效用Ψ，且都具有m個節(jié)點，匯聚節(jié)點能夠均勻地給每個簇分配負載，因此假設(shè)負載量為1，則任一簇Gi分配的負載量為：

任一簇Gi完成總?cè)蝿?wù)最小花費時間是：

6 任務(wù)調(diào)度能耗模型

在無線傳感器網(wǎng)絡(luò)中有3種類型的能源消耗，包括數(shù)據(jù)測量、數(shù)據(jù)融合及通信。由于每一個簇內(nèi)的節(jié)點通過數(shù)據(jù)傳輸來協(xié)作執(zhí)行任務(wù)，因此在簇內(nèi)節(jié)點、簇頭都存在能耗，而簇頭不需要花費能量在數(shù)據(jù)測量上，但需要花費能量在數(shù)據(jù)融合上，而通信所產(chǎn)生的能耗是兩者都具有的。在本文中測量、融合以及發(fā)送和接收一個單元的感知數(shù)據(jù)分別用ES，EF，ET，ER來表示。假設(shè)發(fā)送端節(jié)點i和接收端節(jié)點j的距離為d（i，j），則在執(zhí)行任務(wù)負載為Wi的簇內(nèi)節(jié)點i所消耗的能量表示為：

在執(zhí)行任務(wù)負載為Wi的簇頭節(jié)點i所消耗的能量表示為：

匯聚節(jié)點i所需要消耗的能量表示為：

7 實驗仿真與結(jié)果分析

本文研究不同參數(shù)λ，η，θ，ψ對每個簇內(nèi)的節(jié)點的最小任務(wù)完成時間的影響。仿真軟件采用Matlab7.1，算法模擬仿真環(huán)境設(shè)置為：節(jié)點感知每單元數(shù)據(jù)的能耗為ES=200 nJ，發(fā)送每單元數(shù)據(jù)的能耗為ET=200 nJ，接收每單元數(shù)據(jù)的能量消耗為ER= 100 nJ，融合每單元數(shù)據(jù)的能量消耗為EF=30 nJ。接收端和發(fā)送端之間相距d（i，j）=100 m，每個簇內(nèi)設(shè)定為50個節(jié)點。假設(shè)時間參數(shù)TD=TE=TF=1。

本文選擇參數(shù)λ的變化范圍為（0，1）之間，并分別取在這個范圍內(nèi)的4個λ值進行仿真，其他參數(shù)不變，都設(shè)置為1，從圖3可以看出，簇的數(shù)量越小時，參數(shù)λ的值越大，任務(wù)完成時間越小，當(dāng)參數(shù)λ保持不變，簇數(shù)量增大時，則完工時間會隨之變小?？梢钥闯?，在參數(shù)λ在［0.2，0.4］的范圍內(nèi)，完工時間隨著簇數(shù)量和參數(shù)λ的增大而減少。

本文選擇參數(shù)λ，η，θ和ψ的變化范圍都在（0.5，1.5）之間，并分別取在這個范圍內(nèi)的4個η，θ和ψ值進行仿真，在此實驗中其他參數(shù)都保持不變，設(shè)置為1。從圖4可以看出，參數(shù)η在范圍［0.6，1.2］內(nèi)變化時，任務(wù)完成時間隨著簇數(shù)量和參數(shù)η的增大而減小。從圖5可以看出，隨著簇數(shù)量的變化任務(wù)完成時間逐漸減小，而當(dāng)參數(shù)θ發(fā)生變化時，任務(wù)完成時間的變化幅度很小，因此參數(shù)θ在（0.5，1.5）之間變化時對任務(wù)完成時間的影響基本可以忽略。

圖4 參數(shù)η對任務(wù)完成時間的影響

圖5 參數(shù)θ對任務(wù)完成時間的影響

從圖6可以看出，參數(shù)ψ的值越大會造成算法在執(zhí)行任務(wù)時的完工時間越長，因此參數(shù)ψ在（0.5，1.5）之間取值越小越有利。

圖6 參數(shù)ψ對任務(wù)完成時間的影響

在上述實驗中，通過仿真實驗可知，參數(shù)λ，η，θ和ψ的取值變化對任務(wù)完成時間的影響，因此在接下來的實驗中盡量選取有利的參數(shù)，并在實驗對比中進行體現(xiàn)。

本文選取的參數(shù)值如下：λ=0.4，η=1.2，θ= 0.8，ψ=0.6。對比算法為基于分布式DL推理的任務(wù)調(diào)度算法［10］與基于系統(tǒng)并發(fā)應(yīng)用的節(jié)能任務(wù)調(diào)度算法［11］。圖7為不同簇數(shù)量下算法的任務(wù)完成時間對比，其中本文提出的基于負載分割理論的任務(wù)調(diào)度算法在完成相同任務(wù)上需要的時間更少。由于本文算法采用將無線傳感器網(wǎng)絡(luò)分成多個簇，再通過簇間和簇內(nèi)的節(jié)點任務(wù)調(diào)度來最小化完工時間，相比另外2個算法采用一個匯聚節(jié)點為傳感器內(nèi)所有節(jié)點進行任務(wù)分配的方法更加有效。

圖7 算法任務(wù)完成時間比較

圖8 為在執(zhí)行完任務(wù)后傳感器網(wǎng)絡(luò)節(jié)點的平均能量消耗情況，在實驗中逐漸增大簇的數(shù)量，可以看出，簇的數(shù)量越多，節(jié)點的平均能量消耗量越少，這是因為有更多的簇來分擔(dān)任務(wù)量，從而使每個簇內(nèi)的節(jié)點負擔(dān)變得更小。基于系統(tǒng)并發(fā)應(yīng)用的節(jié)能任務(wù)調(diào)度算法基于節(jié)能目的進行設(shè)計，因此在節(jié)能方面表現(xiàn)較好，但隨著簇數(shù)量的逐漸增多，本文的節(jié)能效果更加明顯，能量消耗量相比基于系統(tǒng)并發(fā)應(yīng)用的節(jié)能任務(wù)調(diào)度算法要更少。

圖8 節(jié)點平均能量消耗比較

8 結(jié)束語

為縮短無線傳感器網(wǎng)絡(luò)在執(zhí)行數(shù)據(jù)采集任務(wù)時所消耗的時間，從而提高任務(wù)執(zhí)行效率，并且通過減少任務(wù)執(zhí)行時間來降低網(wǎng)絡(luò)能耗，本文提出一種基于負載分割理論的集群傳感器任務(wù)調(diào)度算法，通過將整個無線傳感器網(wǎng)絡(luò)劃分為多個簇進行負載分割，利用匯聚節(jié)點將任務(wù)分配給簇頭，再由簇頭進行簇內(nèi)任務(wù)調(diào)度，以最小化任務(wù)完成時間為目標(biāo)來合理分配執(zhí)行任務(wù)所需的數(shù)據(jù)測量、融合和傳輸時間。實驗仿真及對比分析結(jié)果表明，本文算法可以有效縮短執(zhí)行任務(wù)所需時間，并降低網(wǎng)絡(luò)節(jié)點能量消耗。今后將對不可靠環(huán)境下的無線傳感器網(wǎng)絡(luò)節(jié)點定位、數(shù)據(jù)通信及能耗問題作進一步研究。

［1］ Shrivastava P，Pokle S B.Energy Efficient Scheduling Strategy for Data Collection in Wireless Sensor Networks［C］//Proceedings of 2014 International Conference on Electronic System s，Signal Processing and Computing Technologies.Washington D.C.，USA：IEEE Press，2014：170-173.

［2］ Mezei I，Lukic M，Malbasa V，et al.Auctions and iMesh Based Task Assignment in Wireless Sensor and Actuator Networks［J］.Computer Communications，2013，36（9）：979-987.

［3］ Jin Y，Vural S，Gluhak A，et al.dynamic Task Allocation in Multi-hop Multimedia Wireless Sensor Networks with Low Mobility［J］.Sensors，2013，13（10）：13998-14028.

［4］ Chen J，Guo W.A PSO-optim ized Nash Equilibrium based Task Scheduling Algorithm for Wireless Sensor Network［M］.Berlin，Germany：Springer，2013：62-73.

［5］ Shao Yuanhai，Chen Weijie，Zhang Jingjing，et al.An Efficient Weighted Lagrangian Twin Support Vector Machine for Imbalanced Data Classification［J］.Pattern Recognition，2014，47（9）：3158-3167.

［6］ Peng X，Xu D.Structural Regularized Projection Tw in Support Vector Machine for Data Classification［J］. IEEE Transactions on Neural Networks，2014，22（4）：416-432.

［7］ 杜慶偉，顧漢杰，陶 軍.WSN中基于多目標(biāo)優(yōu)化的協(xié)同任務(wù)分配算法［J］.東南大學(xué)學(xué)報：自然科學(xué)版，2014，44（4）：11-15.

［8］ 代 亮，許宏科，陳 婷.無線傳感器網(wǎng)絡(luò)可分負載調(diào)度算法［J］.西安交通大學(xué)學(xué)報，2012，46（6）：23-28.

［9］ 郭文忠，蘇金樹，陳澄宇，等.無線傳感器網(wǎng)絡(luò)中帶復(fù)雜聯(lián)盟的自適應(yīng)任務(wù)分配算法［J］.通信學(xué)報，2014，35（3）：1-10.

［10］ Verstichel S，Volckaert B，Dhoedt B，et al.Contextaware Scheduling of Distributed DL-reasoning Tasks in Wireless Sensor Networks［J］.International Journal of Distributed Sensor Networks，2011，3：1-24.

［11］ LiWei，Delicato F C，Pires P F.Energy-efficient Task Allocation with Quality of Service Provisioning for Concurrent Applications in Multi-functional Wireless Sensor Network System s［J］.Concurrency and Computation：Practice&Experience，2014，26（11）：1869-1888.

［12］ Guo W，Xiong N，Chao H C，et al.Design and Analysis of Self-adapted Task Scheduling Strategies in Wireless Sensor Networks［J］.Sensors，2011，11（7）：6533-6554.

［13］ Xiong Shuguang，Li Jianzhong，Li M o，et al.Multiple Task Scheduling for Low-duty-cycled Wireless Sensor Networks［C］//Proceedings of IEEE INFOCOM'11. Washington D.C.，USA：IEEE Press，2011：1323-1331.

［14］ Ergen S C，Varaiya P.TDMA Scheduling Algorithm s for Wireless Sensor Networks［J］.Wireless Networks，2010，16（4）：985-997.

［15］ Abdelhak S，Gurram C S，Tessier J，et al.ETSSI：Energy-based Task Scheduling Sim ulator for Wireless Sensor Networks［C］//Proceedings of IEEE International Symposium on Circuits and System s. Washington D.C.，USA：IEEE Press，2011：2821-2824.

［16］ Dai Liang，Chang Yilin，Shen Zhong.An Optimal Task Scheduling Algorithm in Wireless Sensor Networks［J］. International Journal of Computers Communications& Control，2011，6（1）：101-112.

［17］ Toscano E，Bello L.Multichannel Superframe Scheduling for IEEE 802.15.4 Industrial Wireless Sensor Networks［J］.IEEE Transactions on Industrial Informatics，2012，8（2）：337-350.

［18］ DaiLiang，Chang Y ilin，Shen Zhong.Non-cooperative Game Algorithm for Task Scheduling in Wireless Sensor Networks［J］.International Journal of Computers Communication&Control，2011，6（3）：592-602.

編輯 陸燕菲

Task Schedu ling Algorithm in Wireless Senser Network Based on Load Segm entation Theory

QIAO Rui，LI Jing
（School of Computer Science and Technology，Zhoukou Normal University，Zhoukou 466001，China）

In order to more effectively solve the task scheduling problem in Wireless Sensor Network（WSN），a cluster sensor task scheduling algorithm based on the idea of clustering and the theory of load segmentation is proposed.The whole WSN is divided into several clusters，and the timing diagram of task execution process is established by using the process of task scheduling between inter-cluster and intra-cluster.Reasonable distribution is performed between measurements of tasks performing，fusion，and transmission time by minimizing the total task time.It makes full use of network resources.Experimental results show that the algorithm shortens the task execution time of WSN，and further reduces the average energy consumption of nodes in the process of executing the task.

Wireless Sensor Network（WSN）；task scheduling；network clustering；load segmentation theory；energy consumption of node

喬 蕊，李 靖.基于負載分割理論的無線傳感器網(wǎng)絡(luò)任務(wù)調(diào)度算法［J］.計算機工程，2015，41（9）：140-144.

英文引用格式：Qiao Rui，Li Jing.Task Scheduling Algorithm in Wireless Senser Network Based on Load Segmentation Theory［J］.Computer Engineering，2015，41（9）：140-144.

1000-3428（2015）09-0140-05

A

TP393

10.3969/j.issn.1000-3428.2015.09.025

河南省軟科學(xué)研究計劃基金資助項目（132400411253）；河南省高等學(xué)校重點科研基金資助項目（15A520115）。

喬 蕊（1983-），女，講師、碩士，主研方向：無線傳感器網(wǎng)絡(luò)，圖像處理；李 靖，講師、碩士。

2014-12-03

2015-01-24 E-m ail：18033023@qq.com