基于負載分割理論的無線傳感器網絡任務調度算法

喬 蕊，李 靖

（周口師范學院計算機科學與技術學院，河南周口466001）

報告匯聚節點子任務Wi的最小測量時間為：

基于負載分割理論的無線傳感器網絡任務調度算法

喬 蕊，李 靖

（周口師范學院計算機科學與技術學院，河南周口466001）

利用分簇思想和負載分割理論，提出基于一種集群結構的無線傳感器網絡任務調度算法。將整個無線傳感器網絡劃分為多個簇進行負載分割，采用簇間和簇內任務調度建立任務執行過程的時序圖，通過最小化總任務時間，實現任務所需數據測量、融合和傳輸時間的合理分配，達到任務的最優調度。仿真實驗結果表明，該算法能縮短任務執行時間，并減少節點在任務執行過程中的能量消耗。

無線傳感器網絡；任務調度；網絡分簇；負載分割理論；節點能耗

1 概述

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

2 相關工作

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

3 面向任務調度的WSN系統場景分析

假設無線傳感器網絡在其生命周期構建多個集群，每個集群有一個建立階段和穩態階段，假設在穩態階段有K個簇網絡［16-18］，每個簇頭表示為Ci，在每一個簇Gi內，有j個節點表示為，簇頭和匯聚節點Si之間的通信鏈路表示為li（i≤K）。在簇內節點和簇頭之間的通信鏈路表示為（

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

4 簇內任務調度模型

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

圖1 簇內任務處理時序圖

對于簇頭Ci，基于圖1所示的時序圖，在簇Gi內任務分配給簇內節點可以表示如下：

其中：

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

報告匯聚節點子任務Wi的最小測量時間為：

5 簇間任務調度模型

在簇頭融合了簇內節點的數據后，簇頭可以通過一個單獨的信道發送融合數據給匯聚節點。為提高任務工作效率，減少節點閑置所帶來的性能下降問題，如圖2的任務調度時序圖所示，可以得到：

圖2 簇間任務調度時序圖

將式（6）簡化為：

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

得到簇頭Ci從匯聚節點接收到的負載量Wi和簇內節點從匯聚節點接收到的負載量所得到的總任務執行時間如下：

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

任一簇Gi完成總任務最小花費時間是：

6 任務調度能耗模型

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

在執行任務負載為Wi的簇頭節點i所消耗的能量表示為：

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

7 實驗仿真與結果分析

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

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

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

圖4 參數η對任務完成時間的影響

圖5 參數θ對任務完成時間的影響

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

圖6 參數ψ對任務完成時間的影響

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

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

圖7 算法任務完成時間比較

圖8 為在執行完任務后傳感器網絡節點的平均能量消耗情況，在實驗中逐漸增大簇的數量，可以看出，簇的數量越多，節點的平均能量消耗量越少，這是因為有更多的簇來分擔任務量，從而使每個簇內的節點負擔變得更小。基于系統并發應用的節能任務調度算法基于節能目的進行設計，因此在節能方面表現較好，但隨著簇數量的逐漸增多，本文的節能效果更加明顯，能量消耗量相比基于系統并發應用的節能任務調度算法要更少。

圖8 節點平均能量消耗比較

8 結束語

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

［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中基于多目標優化的協同任務分配算法［J］.東南大學學報：自然科學版，2014，44（4）：11-15.

［8］ 代 亮，許宏科，陳 婷.無線傳感器網絡可分負載調度算法［J］.西安交通大學學報，2012，46（6）：23-28.

［9］ 郭文忠，蘇金樹，陳澄宇，等.無線傳感器網絡中帶復雜聯盟的自適應任務分配算法［J］.通信學報，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

喬 蕊，李 靖.基于負載分割理論的無線傳感器網絡任務調度算法［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

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

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

2014-12-03

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