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

信息物理融合系統(tǒng)(CPS)是重要而且全新的研究領(lǐng)域，隨著相關(guān)研討會(huì)的相繼召開和專家的不斷深入研究，CPS得到了越來(lái)越多的青睞。2007年7月，美國(guó)總統(tǒng)科學(xué)技術(shù)顧問(wèn)委員會(huì)(PCAST)在題為《挑戰(zhàn)下的領(lǐng)先——競(jìng)爭(zhēng)世界中的信息技術(shù)研發(fā)》的報(bào)告中將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)用前景。而高性能的計(jì)算能力是CPS實(shí)時(shí)性、準(zhǔn)確性應(yīng)用的保證，分布式技術(shù)的發(fā)展為高性能的CPS系統(tǒng)提供了可能，保證了系統(tǒng)的可靠性。所謂分布式，主要指數(shù)據(jù)分布和計(jì)算分布，數(shù)據(jù)分布是指數(shù)據(jù)分散的存儲(chǔ)在不同計(jì)算機(jī)中;計(jì)算分布則是將計(jì)算任務(wù)分配給不同的計(jì)算節(jié)點(diǎn)進(jìn)行分布處理，實(shí)現(xiàn)快速準(zhǔn)確的分布式管理，保證系統(tǒng)的可靠性，任務(wù)優(yōu)化調(diào)度方法尤為重要。

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

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

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

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

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

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

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

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

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

WSN系統(tǒng)是智能建筑的發(fā)展方向，是實(shí)現(xiàn)智慧生活的保證［11-13］。本文針對(duì)WSN系統(tǒng)結(jié)構(gòu)圖中的WSN網(wǎng)路部分的任務(wù)分配過(guò)程，主要對(duì)任務(wù)分配器進(jìn)行了設(shè)計(jì)。1936年圖靈(Turing)提出著名的圖靈機(jī)判據(jù):“如果一個(gè)函數(shù)能用圖靈機(jī)來(lái)計(jì)算，則這個(gè)函數(shù)是可計(jì)算的?！保?4-15］。采用圖靈機(jī)輸入任務(wù)，并根據(jù)圖靈可計(jì)算復(fù)雜性的思想對(duì)任務(wù)進(jìn)行合理化的分配，實(shí)現(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;輸入符號(hào)的有窮集Σ;帶符號(hào)集Γ，滿足Σ?Γ;轉(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)前讀寫頭讀出的符號(hào)為X，當(dāng)轉(zhuǎn)移狀態(tài)到p時(shí)，用Y代替X，讀寫頭向Di(i=1…k)方向移動(dòng)，若Di=S，表示停留在原地不動(dòng);空白符號(hào)B∈Γ-Σ，開始時(shí)空白出現(xiàn)在除輸入的所有單元中;終結(jié)狀態(tài)的集合F?Q，當(dāng)控制達(dá)到此集合中任意狀態(tài)時(shí)，計(jì)算過(guò)程結(jié)束。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)與分析

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

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

表1 資源參數(shù)

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

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

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

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

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

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

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

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

4 結(jié)語(yǔ)

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

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

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

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

［4］王中杰，謝璐璐.信息物理融合系統(tǒng)研究綜述［J］.自動(dòng)化學(xué)報(bào)，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ì)算中基于遺傳算法的任務(wù)調(diào)度算法研究［J］.華中科技大學(xué)學(xué)報(bào)，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)免疫克隆選擇的對(duì)等網(wǎng)絡(luò)任務(wù)調(diào)度機(jī)制［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é)報(bào)，2012，38(3):82-90.

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

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

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

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

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

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

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

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

WSN;任務(wù)調(diào)度;圖靈機(jī);有向無(wú)環(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

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