Research on Distributed Computing WSN Task Scheduling in Intelligent Building Indoor Environment*

GAO Zhijun，WANG Hongyu，WANG Xin，HAN Zhonghua

(1.School of Information and Communication Engineering，Dalian University of Technology，Dalian Liaoning 116024，China; 2.School of Information and Control Engineering，Shenyang Jianzhu University，Shenyang 110168，China)

Research on Distributed Computing WSN Task Scheduling in Intelligent Building Indoor Environment*

GAO Zhijun1，2，WANG Hongyu1*，WANG Xin2，HAN Zhonghua2

(1.School of Information and Communication Engineering，Dalian University of Technology，Dalian Liaoning 116024，China; 2.School of Information and Control Engineering，Shenyang Jianzhu University，Shenyang 110168，China)

To solve the dynamic task scheduling problems of distribution parallel computing in intelligent building，a structure model of WSN based on distributed CPS conception is proposed.The task allocation strategy based on the computability complexity and dynamic scheduling algorithm based on the task scheduling strategy are designed.Firstly，the task is decomposed to a number of sub-tasks，Multi-band Turing machine is applied to the input of the task.The directed acyclic graph is formed though the calculation of the appropriate selected nodes.Second，task scheduling sequence tables are formed and tasks are processed in sequence through scheduling priority.The experimental results show that this strategy reduces the communication time and waiting time of running tasks in WSN.Meanwhile，the success rate of the task scheduler is improved and the efficiency of the system is optimized effectively.

WSN;task scheduling;turing machines;the directed acyclic graph;intelligent building

隨著信息技術的飛速發展和人們對智能建筑室內環境綜合需求的不斷提升，智能建筑室內環境中環境舒適度監測、火災信號檢測和能耗檢測與節能等多任務調度及大規模計算問題已成為制約智能建筑發展的瓶頸，基于信息物理融合系統CPS(Cyber-Physical System)［1-2］分布式可計算WSN的出現，為人們解決這一問題提供了全新的方法，因而受到學術界的廣泛關注。

信息物理融合系統(CPS)是重要而且全新的研究領域，隨著相關研討會的相繼召開和專家的不斷深入研究，CPS得到了越來越多的青睞。2007年7月，美國總統科學技術顧問委員會(PCAST)在題為《挑戰下的領先——競爭世界中的信息技術研發》的報告中將CPS列為八大關鍵信息技術的首位［1］。CPS在智能交通系統、醫療設備系統、能源保護、環境監控、航空航天軟件、關鍵基礎設施(電力、水)、普適自適應通信、節能建筑、生物系統等領域具有廣闊的應用前景。而高性能的計算能力是CPS實時性、準確性應用的保證，分布式技術的發展為高性能的CPS系統提供了可能，保證了系統的可靠性。所謂分布式，主要指數據分布和計算分布，數據分布是指數據分散的存儲在不同計算機中;計算分布則是將計算任務分配給不同的計算節點進行分布處理，實現快速準確的分布式管理，保證系統的可靠性，任務優化調度方法尤為重要。

一直以來多任務調度是調度理論中的經典問題，主要分為靜態任務調度和動態任務調度的算法［3-6］。現如今基于CPS的WSN是分布、異構且復雜的系統，靜態調度算法以不太適用，對動態調度算法的研究趨于主流，例如最小完成時間算法MCT［7］(Minimum Completion Time)、遺傳算法［8］，最小最早完成時間算法(Min-min算法)［9］，Mehdi.N.A等人提出了MCT算法［10］，該方法簡單實用，易實現，但由于其以將每個任務分配給任務完成時間最早的資源為目的，會造成一些任務未被分配到最佳資源的問題，分配成功率較低;熊聰聰等人將遺傳算法用于任務調度中，但容易出現早熟收斂、搜索效率低、收斂性能差以及搜索時間過長等現象，缺乏靈活性; Panda Sanjaya Kumar等人提出了Min-min算法，在任務調度次序的選擇上僅僅以完成時間為標準，負載過度集中在某些節點上，造成高性能節點超負荷運轉，而其余性能較低的節點的處理能力卻沒有得到很好的利用的缺點。

本文在構建智能建筑室內環境下分布式可計算WSN模型的基礎上，主要針對負責任務調度的WSN網絡進行了建模，采用分布式技術的思想，將任務調度分為任務分配和資源調度兩個方面，在任務分配的的過程中按照執行時間、資源利用率等方面進行任務的調度，找尋任務被合理調度的過程，實現了更高的任務調度成功率，有效降低了任務總體完成時間。

1 WSN系統設計

通常，建筑室內環境下WSN處理任務包括濾波、計算、分析、處理、融合等，因此本文WSN系統的任務處理部分采用分布式技術，它將傳感器節點中參與計算的計算節點連成整體，其計算節點的處理能力遠大于傳統無線網絡，實現安全資源管理、合理任務分配以及快速結果輸出，并提供各種資源環境接口。本文所設計的WSN系統結構圖如圖1所示。傳感器網絡感知建筑的物理環境數據信息以及用戶終端的任務請求命令均發送到信息中心，再由WSN網路進行數據分析以及任務的處理，通過執行器網絡控制建筑物理環境。其中本文的任務調度設計主要由傳感器計算節點來完成。

圖1 建筑智能環境分布式可計算WSN系統結構圖

2 WSN分布式的任務調度架構設計

針對WSN系統結構圖中的傳感器計算節點部分，本文主要采用分布式的任務調度策略，任務調度結構圖如圖2所示。任務調度主要分為兩個部分:任務分配和資源調度。一個任務會根據不同的數據約束關系和可計算復雜性等要求分解成若干個子任務，任務分配的目的是解決任務的分解問題以及將分解后的若干子任務分配到合適的計算節點上的過程，選擇任務或子任務在哪些計算節點上執行，任務調度則涉及到在某一個計算節點上，任務將按怎樣的順序被合理的調度執行的過程。任務分配決策必須在任務調度執行之前作出決策。

圖2 分布式任務調度結構圖

2.1 基于可計算復雜性的任務分配設計

WSN系統是智能建筑的發展方向，是實現智慧生活的保證［11-13］。本文針對WSN系統結構圖中的WSN網路部分的任務分配過程，主要對任務分配器進行了設計。1936年圖靈(Turing)提出著名的圖靈機判據:“如果一個函數能用圖靈機來計算，則這個函數是可計算的。”［14-15］。采用圖靈機輸入任務，并根據圖靈可計算復雜性的思想對任務進行合理化的分配，實現智能建筑環境WSN系統任務的快速、準確的處理能力。由于任務的多樣性，采用多帶圖靈機模型(如圖3)進行。

圖3 多帶圖靈機

多帶圖靈機M:關系系統為M=(Q，Σ，Γ，δ，B，F)，有限狀態集Q;輸入符號的有窮集Σ;帶符號集Γ，滿足Σ?Γ;轉移函數δ:Q×Γk→Q×Γk×{L，R，S}k，則δ(q，X1，…，Xk)=(p，Y1，…，Yk，D1，…Dk)，表示機器當前狀態為q，當前讀寫頭讀出的符號為X，當轉移狀態到p時，用Y代替X，讀寫頭向Di(i=1…k)方向移動，若Di=S，表示停留在原地不動;空白符號B∈Γ-Σ，開始時空白出現在除輸入的所有單元中;終結狀態的集合F?Q，當控制達到此集合中任意狀態時，計算過程結束。

多帶圖靈機M的初始狀態為q0(q0∈Q)，設輸入任務為w，M接受w的計算時間被記為tM(w)，WSN系統中的每個參與的計算節點中，都存在一個上述的多帶圖靈機服務器，多帶圖靈機服務器根據時間復雜性TM(n)=max{tM(w):|w|=n，w∈L(M)}將任務分解成若干個子任務，分解的同時，其他計算節點根據本身的計算能力和計算資源與子任務進行匹配，任務分配有向無環圖DGA(Direct A-cyclic Graph)如圖4所示，如此反復的任務、子任務的分解和變換，從而完成任務。

圖4 任務分配有向無環拓撲圖

任務提交到WSN網絡的同時，計算節點中的多帶圖靈機服務器通過可計算時間復雜性的判斷，將一個需要分布式技術解決的任務劃分為若干個子任務，其他網絡中參與計算的計算節點中的多帶圖靈機服務器會與子任務進行匹配，并通過任務調度算法將子任務調度到適合其快速計算的計算節點中進行計算，如若本計算節點無法完成計算，則將任務繼續向下一級分解和匹配，但每個計算節點的計算過程可能需要其不定的上N級有效結果，形成有向無環圖，得其最終結果。

2.2 基于動態調度算法的任務調度設計

在滿足一定的性能指標和依賴關系的前提下，將任務(子任務)調度到滿足其條件的計算節點中，同時安排計算節點可并行執行的任務的執行次序，滿足執行時間最短。本設計中，針對WSN系統結構圖中網路部分的任務調度過程，采用動態調度算法進行任務調度設計，程序流程圖如圖5所示。

圖5 動態調度算法程序流程圖

輸入:一個物理環境發出的任務信息或用戶提出的任務信息(G，t)，其中:任務模型G，時間限制t;

輸出:最優調度列表f。

假設有向無環拓撲圖模型為G=(V，E，p，W，s，D，R)，節點集V={1，2，…，n};弧集E={(i1，j1)，…，(im，jm)};非負向量p為計算節點權重向量，元素pi代表計算節點i的時間開銷;非負矩陣W為弧權重矩陣，元素wk，j表示弧(k，j)的時間開銷;si表示計算節點Vi的運算速度;Di，j表示需要從任務(子任務)ti傳送到tj的數據量、di表示任務(子任務)ti的計算量; Ri，j表示計算節點Vi到Vj的數據信息傳輸速率。

第1步:檢查就緒列表是否為空，如果不為空，繼續;否則結束任務調度;

第2步:查詢任務，獲取輸入任務的有向無環圖DGA參數。

第3步:隨機生成的調度列表f，求解過程中用于記錄最新的調度列表。

第4步:通過式(1)計算任務的優先級程度，如果任務ti的優先級最高，則更新調度列表;如果無最高優先級，按照原調度列表運行。

其中:Mp為處理單元計算能力中值，Mc為鏈路傳輸能力中值。

第5步:判斷是否滿足|f|最小，如果滿足則結束;否則返回步驟4。

pi，j為執行代價，表示任務ti在處理器節點Vj上的執行時間，pi，j=di/sj+pj;Wi，j為通信代價，假定任務ti運行在處理器節點Vf上，tj運行在處理器Vt上，處理器Vf和Vt之間的通信時間，Wi，j=pf+Di，j/Rf，t。

定義:調度成功率為規定時間條件之下正確處理任務數與需處理的總任務數之比。

在任務調度的過程中采用動態調度算法，以運行時間最短為目標，在滿足帶寬約束的條件下，經過根據優先級制定的調度列表進行任務的調度，在以可計算復雜度的準確任務分配的基礎上，縮短任務的執行之間。

3 實驗與分析

在智能建筑室內環境的分布式WSN網絡中，根據可計算復雜性的思想進行任務分配，再采用動態調度算法進行任務調度，并通過MATLAB仿真實驗驗證其優越性。

結合本文的分布式任務管理模型，利用MATLAB進行仿真實驗。針對智能建筑室內環境資源任務的特點，設置20種傳感器普通節點，其中有10個計算節點，隨機產生30、50、60、100和150個任務，實驗仿真統計次數均為1 000。資源的參數設置如表1所示。

表1 資源參數

本文對算法運行時間和任務的完成時間進行了MATLAB仿真實驗。圖6所示為算法運行時間與任務數關系，由圖6可以更直觀的看出，隨著任務數量的增加，各算法運行時間均所增加，當任務數為60時，MCT、遺傳算法和Min-min 3種算法運行時間分別為270 ms、255 ms和240 ms，而本文算法運行時間為230 ms;當任務數增至100時，本文算法運行時間為270 ms，仍明顯低于其他3種算法運行時間，這主要是因為MCT算法易于出現部分任務未被分配到最佳資源;Min-min算法則產生負載過度集中在某些節點上，造成高性能節點超負荷運轉問題;遺傳算法容易出現早熟收斂、搜索效率低;而本文算法中采用在任務分配的的過程中按照執行時間、資源利用率等方面進行任務的調度，有效克服了以上算法所存在的缺陷，大大縮短了算法運行時間，進而顯現出本文算法在運行時間上的優勢。

圖6 算法運行時間比較圖

通過與MCT算法、遺傳算法和Min-min算法3種較為經典的任務調度算法的比較，仿真得出圖7的任務完成時間比較圖。采用本文算法，任務完成時間明顯小于其他3種任務調度算法，這主要是本文在調度算法中分成任務分配和資源調度兩個部分，再將復雜任務分解為若干個子任務，使其復雜度簡化，并利用優先級調度機制。隨著任務數量的增加，在縮短任務完成時間方面優勢越來越明顯。

在任務調度成功率方面，本文算法較MCT算法、遺傳算法和Min-min算法體現了優越性，如圖8所示。

圖7 任務完成時間比較圖

圖8 任務調度成功率比較圖

從圖8中可以看出，與MCT算法、遺傳算法和Min-min算法3種算法相比，本文算法以任務優先級為標準進行調度，任務均可以在其有效期間內完成，成功率可達到90%以上，而MCT算法、遺傳算法和Min-min算法3種算法都比較注重任務完成時間短的任務調度，當計算節點空閑時才開始執行完成時間長但重要率高的任務，導致其最終計算結果失效，成功率低。在網絡環境復雜繁多的WSN中，本文算法具有非常好的應用前景。

由以上仿真實驗可以看出，相對于MCT算法、遺傳算法和Min-min算法3種比較經典的任務調度算法，在智能建筑室內環境分布式WSN網絡中，采用任務分配和任務調度獨立工作但結果又相互融合的方式進行任務調度的方案是可行的，既可以加快任務處理的速度，而且還可以增加任務調度成功率，同時在任務分配和處理的同時，系統的資源庫不斷更新，不僅加快了未來數據訪問速度和任務的處理速度，而且通過圖靈機服務器的記憶功能，還實現了系統的自主學習能力。

4 結語

本文在智能建筑室內環境分布式可計算WSN系統中，采用分布式技術的思想，利用可計算復雜性和動態調度算法進行任務的分配、調度和處理工作，可以將各種高性能服務器和計算節點等有機的結合起來，實現分布式的資源高度共享。實驗結果表明本文所提出的調度機制可有效的提高整個任務調度的總體完成時間和任務調度的成功率，與MCT、遺傳算法和Min-min 3種算法相比，本文算法具有較低的算法運行時間，可有效解決智能建筑室內環境下多任務調度的復雜性及大規模計算問題。

［1］王小樂，黃宏斌，鄧蘇.處理順序約束的信息物理融合系統靜態任務表調度算法［J］.自動化學報，2012，38(11):1870 -1879.

［2］陳曉娟，王卓，吳潔.一種基于LEACH的改進WSN路由算法［J］.傳感技術學報，2013，26(1):116-121.

［3］孔玉靜，侯鑫，華爾天，等.基于BP神經網絡的無線傳感器網絡路由協議的研究［J］.傳感技術學報，2013，26(2):246 -251.

［4］王中杰，謝璐璐.信息物理融合系統研究綜述［J］.自動化學報，2011，37(10):1157-1166.

［5］Mehdi N A，Mamat Ali，Amer Ali.Minimum Completion Time for Power-Aware Scheduling in Cloud Computing［C］//Proceedings of the 4th International Conference on Developments in Systems Engineering，2011:484-489.

［6］熊聰聰，馮龍.云計算中基于遺傳算法的任務調度算法研究［J］.華中科技大學學報，2012(40):1-4.

［7］Panda Sanjaya Kumar，Bhoi Sourav Kumar，Khilar Pabitra Mohan. A Semi-Interquartile min-min max-min(SIM2)Approach for Grid Task Scheduling［J］.Advances in Intelligent Systems and Computing，2013:415-421.

［8］Yang J D，Xu H，Pan L，et al.Task Scheduling Using Bayesian Optimization Algorithm for Heterogeneous Computing Environments［J］.Applied Soft Computing，2011，11(4):3297-3310.

［9］Lee Y C，Zomaya A Y.A Novel State Transition Method for Metaheuristic-Based Scheduling in Heterogeneous Computing Systems［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(9):1215-1223.

［10］孟憲福，王敏.基于改進免疫克隆選擇的對等網絡任務調度機制［J］.計算機集成制造系統，2009，15(9):1795-1802.

［11］Tang Xiaoyong，Li Kenli.A Stochastic Scheduling Algorithm for Precedence Constrained Tasks on Grid［J］.Future Generation Computer Systems，2011，27(8):1083-1091.

［12］王金良，蘇志強.網絡使用研究進展——影響因素、后果變量及影響機制［J］.西南大學學報，2012，38(3):82-90.

［13］譚朋柳，舒堅.一種信息-物理融合系統體系結構［J］.計算機研究與發展，2010，47:312-316.

［14］宋文，牟行軍.計算的模型:圖靈機與Petri網［J］.西華大學學報，2013(3):1-6.

［15］王寧，屈國棟.一種基于Eclipse RCP的任務管理系統設計與實現［J］.微計算機信息，2011，27(4):119-121.

高治軍(1978-)，男，大連理工大學博士研究生生，主要從事無線傳感器網絡技術與應用、無線網絡技術、智能建筑等方面的研究，gzj1267@sjzu.edu.cn;

王洪玉(1968-)，男，大連理工大學教授、博士生導師，IEEE會員，中國電子學會高級會員，主要從事無線定位技術、移動自組織網絡技術、移動通信先進物理層技術等方向的研究，whyu@ dlut.edu.cn。

智能建筑室內環境分布式可計算WSN任務調度研究*

高治軍1，2，王洪玉1*，王鑫2，韓忠華2
(1.大連理工大學信息與通信工程學院，遼寧大連116024;2.沈陽建筑大學信息與控制工程學院，沈陽110168)

針對智能建筑室內環境下并行計算的動態任務調度問題，構建了基于分布式CPS思想的無線傳感器網絡(WSN)模型，并分別設計了基于可計算復雜性的任務分配策略和基于動態調度算法的任務調度策略。通過先將任務分配成若干個子任務，采用多帶圖靈機輸入任務，由合適的計算節點進行計算，形成有向無環圖，再按調度優先級排列任務，形成任務調度序列表，依序處理任務，從而達到了將任務分配、調度和執行相結合的目的。實驗結果表明該策略可有效減少智能建筑室內環境分布式可計算WSN分布運行時任務之間的通訊時間和等待時間，同時提高了任務調度的成功率，最終優化系統的運行效率。

WSN;任務調度;圖靈機;有向無環圖;智能建筑

TP393

A

1004－1699(2014)03－0378－05

2013-10-10修改日期:2014-03-02

C:6150P

10.3969/j.issn.1004－1699.2014.03.020

項目來源:國家自然科學基金項目(61172058);住房與城鄉建設部研究開發項目(2009-K9-25)