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

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

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

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

本文在構(gòu)建智能建筑室內(nèi)環(huán)境下分布式可計算WSN模型的基礎(chǔ)上，主要針對負(fù)責(zé)任務(wù)調(diào)度的WSN網(wǎng)絡(luò)進(jìn)行了建模，采用分布式技術(shù)的思想，將任務(wù)調(diào)度分為任務(wù)分配和資源調(diào)度兩個方面，在任務(wù)分配的的過程中按照執(zhí)行時間、資源利用率等方面進(jìn)行任務(wù)的調(diào)度，找尋任務(wù)被合理調(diào)度的過程，實現(xiàn)了更高的任務(wù)調(diào)度成功率，有效降低了任務(wù)總體完成時間。

1 WSN系統(tǒng)設(shè)計

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

圖1 建筑智能環(huán)境分布式可計算WSN系統(tǒng)結(jié)構(gòu)圖

2 WSN分布式的任務(wù)調(diào)度架構(gòu)設(shè)計

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

圖2 分布式任務(wù)調(diào)度結(jié)構(gòu)圖

2.1 基于可計算復(fù)雜性的任務(wù)分配設(shè)計

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

圖3 多帶圖靈機(jī)

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

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

圖4 任務(wù)分配有向無環(huán)拓?fù)鋱D

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

2.2 基于動態(tài)調(diào)度算法的任務(wù)調(diào)度設(shè)計

在滿足一定的性能指標(biāo)和依賴關(guān)系的前提下，將任務(wù)(子任務(wù))調(diào)度到滿足其條件的計算節(jié)點中，同時安排計算節(jié)點可并行執(zhí)行的任務(wù)的執(zhí)行次序，滿足執(zhí)行時間最短。本設(shè)計中，針對WSN系統(tǒng)結(jié)構(gòu)圖中網(wǎng)路部分的任務(wù)調(diào)度過程，采用動態(tài)調(diào)度算法進(jìn)行任務(wù)調(diào)度設(shè)計，程序流程圖如圖5所示。

圖5 動態(tài)調(diào)度算法程序流程圖

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

輸出:最優(yōu)調(diào)度列表f。

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

第1步:檢查就緒列表是否為空，如果不為空，繼續(xù);否則結(jié)束任務(wù)調(diào)度;

第2步:查詢?nèi)蝿?wù)，獲取輸入任務(wù)的有向無環(huán)圖DGA參數(shù)。

第3步:隨機(jī)生成的調(diào)度列表f，求解過程中用于記錄最新的調(diào)度列表。

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

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

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

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

定義:調(diào)度成功率為規(guī)定時間條件之下正確處理任務(wù)數(shù)與需處理的總?cè)蝿?wù)數(shù)之比。

在任務(wù)調(diào)度的過程中采用動態(tài)調(diào)度算法，以運(yùn)行時間最短為目標(biāo)，在滿足帶寬約束的條件下，經(jīng)過根據(jù)優(yōu)先級制定的調(diào)度列表進(jìn)行任務(wù)的調(diào)度，在以可計算復(fù)雜度的準(zhǔn)確任務(wù)分配的基礎(chǔ)上，縮短任務(wù)的執(zhí)行之間。

3 實驗與分析

在智能建筑室內(nèi)環(huán)境的分布式WSN網(wǎng)絡(luò)中，根據(jù)可計算復(fù)雜性的思想進(jìn)行任務(wù)分配，再采用動態(tài)調(diào)度算法進(jìn)行任務(wù)調(diào)度，并通過MATLAB仿真實驗驗證其優(yōu)越性。

結(jié)合本文的分布式任務(wù)管理模型，利用MATLAB進(jìn)行仿真實驗。針對智能建筑室內(nèi)環(huán)境資源任務(wù)的特點，設(shè)置20種傳感器普通節(jié)點，其中有10個計算節(jié)點，隨機(jī)產(chǎn)生30、50、60、100和150個任務(wù)，實驗仿真統(tǒng)計次數(shù)均為1 000。資源的參數(shù)設(shè)置如表1所示。

表1 資源參數(shù)

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

圖6 算法運(yùn)行時間比較圖

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

在任務(wù)調(diào)度成功率方面，本文算法較MCT算法、遺傳算法和Min-min算法體現(xiàn)了優(yōu)越性，如圖8所示。

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

圖8 任務(wù)調(diào)度成功率比較圖

從圖8中可以看出，與MCT算法、遺傳算法和Min-min算法3種算法相比，本文算法以任務(wù)優(yōu)先級為標(biāo)準(zhǔn)進(jìn)行調(diào)度，任務(wù)均可以在其有效期間內(nèi)完成，成功率可達(dá)到90%以上，而MCT算法、遺傳算法和Min-min算法3種算法都比較注重任務(wù)完成時間短的任務(wù)調(diào)度，當(dāng)計算節(jié)點空閑時才開始執(zhí)行完成時間長但重要率高的任務(wù)，導(dǎo)致其最終計算結(jié)果失效，成功率低。在網(wǎng)絡(luò)環(huán)境復(fù)雜繁多的WSN中，本文算法具有非常好的應(yīng)用前景。

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

4 結(jié)語

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

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

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

［3］孔玉靜，侯鑫，華爾天，等.基于BP神經(jīng)網(wǎng)絡(luò)的無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究［J］.傳感技術(shù)學(xué)報，2013，26(2):246 -251.

［4］王中杰，謝璐璐.信息物理融合系統(tǒng)研究綜述［J］.自動化學(xué)報，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］熊聰聰，馮龍.云計算中基于遺傳算法的任務(wù)調(diào)度算法研究［J］.華中科技大學(xué)學(xué)報，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ìn)免疫克隆選擇的對等網(wǎng)絡(luò)任務(wù)調(diào)度機(jī)制［J］.計算機(jī)集成制造系統(tǒng)，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］王金良，蘇志強(qiáng).網(wǎng)絡(luò)使用研究進(jìn)展——影響因素、后果變量及影響機(jī)制［J］.西南大學(xué)學(xué)報，2012，38(3):82-90.

［13］譚朋柳，舒堅.一種信息-物理融合系統(tǒng)體系結(jié)構(gòu)［J］.計算機(jī)研究與發(fā)展，2010，47:312-316.

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

［15］王寧，屈國棟.一種基于Eclipse RCP的任務(wù)管理系統(tǒng)設(shè)計與實現(xiàn)［J］.微計算機(jī)信息，2011，27(4):119-121.

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

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

智能建筑室內(nèi)環(huán)境分布式可計算WSN任務(wù)調(diào)度研究*

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

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

WSN;任務(wù)調(diào)度;圖靈機(jī);有向無環(huán)圖;智能建筑

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

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