徐　濤　呼和木其日

(1.中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院　天津　300300)(2.中國民航信息技術(shù)科研基地　天津　300300)

?

一種機場噪聲等值線三維動態(tài)繪制的任務(wù)分配方法

徐濤1,2呼和木其日1

(1.中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院天津300300)(2.中國民航信息技術(shù)科研基地天津300300)

任務(wù)分配方法是影響集群系統(tǒng)性能的關(guān)鍵所在,影響著集群系統(tǒng)的負載均衡和系統(tǒng)資源利用率。在機場噪聲等值線三維動態(tài)繪制過程中,網(wǎng)格間距大小決定繪制精度和噪聲計算量,如何將機場周圍區(qū)域中的噪聲計算任務(wù)分配到集群中不同服務(wù)器節(jié)點并動態(tài)控制網(wǎng)格間距是提高集群系統(tǒng)資源利用率、縮短平均響應(yīng)時間和提高噪聲等值線繪制精度的重要環(huán)節(jié)。針對上述目標,分析了機場周圍環(huán)境結(jié)構(gòu)因素和機場噪聲分布特性,建立了噪聲計算量與服務(wù)器負載之間的關(guān)系,從而構(gòu)建面向機場噪聲等值線三維動態(tài)繪制的任務(wù)分配模型,并采用遺傳算法對模型進行求解。仿真結(jié)果表明,該方法能夠均衡地分配任務(wù),充分利用系統(tǒng)資源,縮短系統(tǒng)響應(yīng)時間,達到機場噪聲等值線三維動態(tài)繪制的實時計算要求。

機場噪聲等值線繪制; 集群系統(tǒng); 任務(wù)分配; 遺傳算法

Class NumberTP391

1　引言

機場噪聲等值線繪制在機場環(huán)境評估工作中起著重要的作用,可直觀形象地表現(xiàn)目標區(qū)域噪聲分布,呈現(xiàn)目標區(qū)域受噪聲影響情況,支持機場周圍噪聲控制與城市規(guī)劃協(xié)同推進。在機場噪聲等值線繪制工作中,對機場周圍目標區(qū)域進行網(wǎng)格化是基礎(chǔ),通常目標區(qū)域被劃分為等間距網(wǎng)格,通過網(wǎng)格點處的噪聲值進行機場噪聲等值線追蹤和繪制[1～3]。機場噪聲等值線的精準度和質(zhì)量依賴于輸入數(shù)據(jù)的規(guī)模和詳細信息,而網(wǎng)格密度影響機場噪聲等值線繪制的精度,雖然可以通過減小網(wǎng)格間距來提高準確性,但冗余計算量會使計算時間成倍增長,使得噪聲等值線繪制速度降低。因此,滿足有效噪聲繪制精度和計算實時性是機場噪聲動態(tài)繪制的關(guān)鍵問題。

機場噪聲等值線一般用來表征機場周圍區(qū)域地表受噪聲影響情況,目前針對三維空間機場噪聲等值線繪制的影響分析研究較少。文獻[4～6]對城市噪聲三維可視化做出了突破性的工作,從等值線繪制算法的角度將噪聲可視化工作擴展到空間垂直方向,并對算法時間效率進行了分析,取得了一定的研究成果。但是這些工作都是針對月、季或年度平均噪聲的評估上,未涉及到噪聲等值線動態(tài)繪制。文獻[3]提出的單航班噪聲動態(tài)等值線繪制算法雖滿足繪制的實時性要求,但未考慮機場周圍區(qū)域土地利用情況,僅滿足傳統(tǒng)的機場噪聲等值線動態(tài)繪制需求。一般來說,不管是噪聲等值線繪制還是其它領(lǐng)域中,三維可視化中的計算量往往超過普通單機的計算能力,更不能滿足實時仿真。

由于機場周圍目標區(qū)域土地利用情況不同,各子區(qū)域?qū)υ肼暤拿舾谐潭纫膊煌?。而傳統(tǒng)機場噪聲等值線繪制中,通常在所選計算區(qū)域二維平面上按等距網(wǎng)格劃分方法生成網(wǎng)格點。因此,若按此方法在三維場景中生成網(wǎng)格點并保持有效噪聲繪制精度,噪聲計算量將進一步提高,單機無法滿足實時計算要求。采用集群系統(tǒng)處理大量計算任務(wù)是處理場景或環(huán)境仿真的常用方法。在群體仿真、醫(yī)學(xué)和經(jīng)濟學(xué)領(lǐng)域中對具有廣泛的應(yīng)用。文獻[7]采用分布式系統(tǒng)對室內(nèi)群體仿真,考慮室內(nèi)環(huán)境因素和群體動向用較低代價劃分任務(wù)縮短仿真響應(yīng)時間,但該方法是基于集群系統(tǒng)中各計算節(jié)點性能相等的理想情況而設(shè)計,在實際應(yīng)用中系統(tǒng)中各計算節(jié)點的負載不一定處于理想狀態(tài)。

使用集群系統(tǒng)處理并行計算任務(wù)過程中負載均衡是關(guān)鍵問題[8～12]。在利用集群系統(tǒng)實現(xiàn)機場噪聲等值線三維動態(tài)繪制過程中,通過有效的任務(wù)劃分和任務(wù)調(diào)度解決集群系統(tǒng)的負載均衡是縮短任務(wù)響應(yīng)時間的重要環(huán)節(jié)。本文結(jié)合機場周圍目標區(qū)域土地利用情況和環(huán)境結(jié)構(gòu)特征,分析機場噪聲分布特性,建立面向機場噪聲等值線三維動態(tài)繪制的任務(wù)分配模型,并用遺傳算法對模型求解,得到一種能夠保證機場噪聲等值線繪制精度并滿足實時繪制要求的任務(wù)分配方法。

2　問題分析

2.1機場噪聲時空特性分析

1) 機場噪聲范圍特性

噪聲源的指向性對環(huán)境的影響很大。機場噪聲影響范圍主要在航空器噪聲輻射方向集中的航空器下面、前方和后方(如圖1所示)。航空器起飛或著陸時,受噪聲影響的范圍主要在飛行下方沿跑道延伸擴展的區(qū)域。

圖1　機場噪聲影響范圍示意圖

2) 機場噪聲空間特性

機場噪聲主要源自進離場的航空器,與其他城市噪聲不同,航空器產(chǎn)生的噪聲是從空中傳向地面,因此地面的地形、遮擋物等不能對它產(chǎn)生明顯衰減,其影響范圍較大。某一時刻航空器噪聲的空間影響范圍如圖2所示,它是以航空器下方的網(wǎng)格點為中心向四周擴散的一個區(qū)域,中心點的噪聲值最大,越往外噪聲值越小。

圖2　機場噪聲空間特性示意圖

3) 機場噪聲時間特性

受航空噪聲影響區(qū)域的噪聲一般持10s～20s左右,人們感受到的航空器噪聲有明顯的由小到大再變小的變化特征,其噪聲影響區(qū)域也會隨著航空器飛行而變化,呈現(xiàn)如圖3所示的時間特征。

由機場噪聲的時空特性可以看出,機場周圍區(qū)域在航空器飛行過程中受噪聲影響的區(qū)域隨航空器位置變化主要由飛行航跡決定。而傳統(tǒng)機場噪聲等值線動態(tài)繪制對所有區(qū)域的網(wǎng)格點進行噪聲計算,其中包含大量不必要的計算工作,影響實時性。本文采用網(wǎng)格索引方式對受噪聲影響區(qū)域進行索引,過濾掉不必要的空間位置和實體,有利于提高機場噪聲等值線三維動態(tài)繪制的實時性能。

圖3　機場噪聲時間特性示意圖

2.2機場周圍區(qū)域環(huán)境結(jié)構(gòu)對任務(wù)分配的影響

由于機場周圍區(qū)域的土地類型利用情況不同,各區(qū)域?qū)υ肼暤拿舾谐潭纫膊煌?。居民區(qū)、教育區(qū)、醫(yī)療社區(qū)等人口密集區(qū)域?qū)υ肼暶舾谐潭容^大。而工廠或田地等區(qū)域?qū)υ肼暶舾谐潭容^小或幾乎不敏感。在機場噪聲等值線三維動態(tài)繪制問題中,可充分考慮這些噪聲敏感程度不同區(qū)域的分布并分別進行網(wǎng)格化以減少不必要的噪聲計算。

另一方面,在集群系統(tǒng)中容易出現(xiàn)部分節(jié)點負載過重或過輕,甚至處于閑置狀態(tài),導(dǎo)致整個系統(tǒng)的運行效率低。負載均衡就是指在集群環(huán)境下,利用某種手段和策略,保證各個服務(wù)節(jié)點上的負載與其本身性能相適應(yīng),將一個問題分解成多個子任務(wù)并把每個子任務(wù)分配到合適的服務(wù)器節(jié)點上,從而提高整體任務(wù)的完成效率[13]。

在利用集群系統(tǒng)實現(xiàn)機場噪聲等值線三維動態(tài)繪制過程中,為了提高實時性和集群系統(tǒng)資源利用率,集群中的每個服務(wù)器處理與自身計算能力相當?shù)娜蝿?wù)量。由于各服務(wù)器的計算能力隨它的資源使用率變化,故機場噪聲等值線三維動態(tài)繪制任務(wù)分配應(yīng)是動態(tài)的。另一方面,機場周圍建筑物分布情況影響各區(qū)域的計算任務(wù)大小,故機場周圍區(qū)域環(huán)境結(jié)構(gòu)是該任務(wù)分配過程中不可忽視的關(guān)鍵因素之一。若某一劃分區(qū)域內(nèi)的建筑物分布過多而另一劃分區(qū)域內(nèi)的建筑物過少,則會出現(xiàn)計算負載不平衡現(xiàn)象,導(dǎo)致總計算時間變長,降低集群系統(tǒng)資源利用率。

3　機場噪聲等值線三維動態(tài)繪制的任務(wù)分配方法

3.1服務(wù)器節(jié)點噪聲計算能力與負載之間的關(guān)系

在機場噪聲等值線三維動態(tài)繪制問題中,將一個網(wǎng)格點在某一時刻的噪聲計算定義為單元任務(wù),這個單元任務(wù)非常小,只需要很少的內(nèi)存和CPU能力就可執(zhí)行。將若干個單元任務(wù)聚集成一個任務(wù)集合,稱為任務(wù)量。通過集群系統(tǒng)將不同任務(wù)量的任務(wù)集合根據(jù)各服務(wù)器節(jié)點的負載情況分配給服務(wù)器節(jié)點來完成噪聲計算操作。把一個服務(wù)器節(jié)點在某種負載情況下能夠計算的任務(wù)量,稱為服務(wù)器節(jié)點在該負載下的噪聲計算能力,記第i個服務(wù)器節(jié)點的計算能力為wi。

在CPU主頻和內(nèi)存分別為3.1GHz和4GB的服務(wù)器節(jié)點上通過對資源設(shè)置不同負載得出服務(wù)器節(jié)點噪聲計算能力與CPU負載和內(nèi)存容量之間的關(guān)系。

1) 服務(wù)器節(jié)點噪聲計算能力與CPU負載之間的關(guān)系

采用最小二乘法擬合得出服務(wù)器節(jié)點噪聲計算能力wi與CPU負載兩者之間的函數(shù)關(guān)系(如圖4所示),其擬合公式如下:

wi=-2.198×104×Li(CPU)+2.245×104

(1)

其中,Li(CPU)表示第i個服務(wù)器節(jié)點CPU負載,用百分比表示。

圖4　服務(wù)器節(jié)點噪聲計算能力與CPU負載之間的關(guān)系

2) 服務(wù)器節(jié)點噪聲計算能力與內(nèi)存容量之間的關(guān)系

同樣采用最小二乘法擬合可獲得服務(wù)器節(jié)點噪聲計算能力wi與內(nèi)存容量兩者之間的函數(shù)關(guān)系(如圖5所示),其擬合公式如下:

wi=5.858×103×Li(Mem)+1095

(2)

其中,Li(Mem)表示第i個服務(wù)器節(jié)點內(nèi)存容量,單位為Mb。

3.2任務(wù)分配目標

設(shè)集群系統(tǒng)由m個負載情況不同的服務(wù)器節(jié)點構(gòu)成,用S=(s1,s2,…,sm)表示節(jié)點集合,用W=(w1,w2,…,wm)表示S所對應(yīng)的每個服務(wù)器節(jié)點的噪聲計算能力。機場噪聲等值線三維動態(tài)繪制任務(wù)分配是將受航空器噪聲影響的機場周圍區(qū)域劃分成m個區(qū)域,每個區(qū)域的噪聲計算任務(wù)單獨分配到一個服務(wù)器節(jié)點。這種任務(wù)劃分方法可歸類于基于區(qū)域分割的任務(wù)劃分方法。

圖5　服務(wù)器節(jié)點噪聲計算能力與內(nèi)存容量之間的關(guān)系

圖6　機場噪聲等值線三維動態(tài)繪制中噪聲計算任務(wù)與服務(wù)器間映射關(guān)系示意圖

另一方面,由于機場周圍區(qū)域?qū)娇掌髟肼暤拿舾谐潭炔煌?所以對各區(qū)域網(wǎng)格化時,網(wǎng)格點的間距也不同。噪聲不敏感區(qū)域的網(wǎng)格間距可相對較大,而噪聲敏感區(qū)域的網(wǎng)格間距盡可能小。網(wǎng)格點越密,噪聲等值線繪制精度越高。記dk表示噪聲敏感類型為k(1≤k≤4)的區(qū)域中的網(wǎng)格間距,其中,1表示不敏感,2表示較不敏感,3表示較敏感,4表示敏感。同時,對任務(wù)集合T中子任務(wù)ti的任務(wù)量ωi與ti對應(yīng)區(qū)域內(nèi)四種噪聲敏感區(qū)域的面積Aik(1≤k≤4)和對應(yīng)的dk相關(guān)。對于服務(wù)器節(jié)點i,它當前的噪聲計算能力wi制約著分配給此節(jié)點的子任務(wù)ti中的dk的大小;而dk的取值又決定了該任務(wù)ti的噪聲計算量ωi。

3.2.1負載均衡目標

假設(shè)將子任務(wù)ti分配給某個服務(wù)器節(jié)點si,其任務(wù)量ωi為

(3)

dk的值取決于子任務(wù)ti對應(yīng)區(qū)域內(nèi)的Aik和與之被分配到的服務(wù)器節(jié)點的性能wi。而在計算能力不同的服務(wù)器節(jié)點組成的集群系統(tǒng)中,需要根據(jù)各節(jié)點的計算能力進行任務(wù)調(diào)度。本文將總?cè)蝿?wù)劃分成m個子任務(wù)分配到m個服務(wù)器節(jié)點上,子任務(wù)ti分配到節(jié)點si上,則節(jié)點si的負載程度表示為

(4)

理想情況下被分配到節(jié)點si的任務(wù)量ωi與節(jié)點si當前的噪聲計算能力wi相當,且0

(5)

這里0

3.2.2網(wǎng)格間距目標

在不超過服務(wù)器節(jié)點噪聲計算能力的情況下,網(wǎng)格間距dk的取值越小,噪聲等值線繪制精度越高。另外,在同等計算能力條件下,噪聲敏感區(qū)域的網(wǎng)格間距d4比噪聲較敏感區(qū)域的網(wǎng)格間距d3小更符合實際需求。

采用對dk劃分等級并打分的策略表示dk的優(yōu)劣程度。設(shè)dk共有q個間距等級,其對應(yīng)的網(wǎng)格間距用Dis=(dis1,dis2,…,disq)表示,等級越大其網(wǎng)格間距越大,即有dis1f2>…>fq。設(shè)X中網(wǎng)格間距dk所對應(yīng)得分為f(dk),則此任務(wù)劃分方法下的總得分Score為

(6)

其中,λk為噪聲敏感類型為k的區(qū)域網(wǎng)格間距得分權(quán)重。dk的取值滿足Score越大越好。

3.3機場噪聲等值線三維動態(tài)繪制任務(wù)分配模型

由上述機場噪聲等值線動態(tài)繪制中任務(wù)分配問題分析和任務(wù)分配目標可得機場噪聲等值線三維動態(tài)繪制任務(wù)分配模型如下:

(7)

(8)

(9)

模型中有兩個目標函數(shù):集群系統(tǒng)負載均衡程度LB最大化和網(wǎng)格間距得分Score最大化;X={x1,x2,…,xm-1}和dk(1≤k≤4)為決策變量,決定分配給每個服務(wù)器節(jié)點的任務(wù)量。并且X的序列滿足式(9)中的約束條件,它決定每個區(qū)域中的Aik,dk∈Dis。任務(wù)量和節(jié)點噪聲計算能力滿足式(9)中的大小關(guān)系,節(jié)點的噪聲計算能力由該節(jié)點的CPU工作負載和內(nèi)存容量決定。因此,機場噪聲等值線三維動態(tài)繪制任務(wù)分配問題是一個多目標優(yōu)化問題[14]。

4　實驗仿真

4.1機場噪聲等值線三維動態(tài)繪制任務(wù)分配模型求解

本文用遺傳算法[15]求解機場噪聲等值三維動態(tài)繪制的任務(wù)分配模型。遺傳算法在生成初始種群后,采用適者生存原則,對環(huán)境適應(yīng)度較高的個體將有更大的幾率遺傳到下一代,經(jīng)過個體之間的交叉和一定概率的變異產(chǎn)生新的種群,在逐代的進化過程中不斷接近最優(yōu)解。

1) 染色體編碼與種群初始化

將劃分序列X={x1,x2,…,xm-1}和四類敏感區(qū)域網(wǎng)格間距d={d1,d2,d3,d4}對應(yīng)的等級序列用自然數(shù)編碼構(gòu)成染色體,一個染色體為問題的一種解。從群體中隨機選取規(guī)模G(G為偶數(shù))的個體集合作為初始種群。

2) 確定適應(yīng)度函數(shù)

(10)

以集群的負載均衡程度和網(wǎng)格間距優(yōu)劣程度加權(quán)之和作為適應(yīng)度函數(shù)fitness,于是:

(11)

其中,μ和η滿足μ+η=1。

3) 選擇策略

采用輪盤賭方法選擇個體,在計算個體i的適應(yīng)度值fitnessi后個體i被選中的概率Pi為[16]

(12)

4) 交叉操作

采用單點交叉方式,即隨機產(chǎn)生一個交叉點,以交叉概率Pc將該位置的基因進行交換。若交叉位置發(fā)生在X的序列里,判斷交叉后新生成的兩個個體中的X序列是否滿足約束條件;若滿足,則將兩個新的個體遺傳到下一代;否則,放棄該交叉操作。

5) 變異操作

4.2實驗環(huán)境與參數(shù)

采用HPC集群平臺進行仿真。集群系統(tǒng)結(jié)構(gòu)如圖7所示,系統(tǒng)主要由一個頭節(jié)點和多個計算節(jié)點組成,頭節(jié)點負責(zé)與用戶交互并根據(jù)用戶請求從數(shù)據(jù)庫中提取相關(guān)數(shù)據(jù),并根據(jù)計算節(jié)點的負載情況為計算節(jié)點分配任務(wù);計算節(jié)點定期將負載信息發(fā)送給頭節(jié)點,并且完成從頭節(jié)點接收到的噪聲計算任務(wù),最后將計算結(jié)果存儲到存儲器上。頭節(jié)點和計算節(jié)點之間用內(nèi)部網(wǎng)絡(luò)連接,通過MPI(消息傳遞機制)進行消息傳遞。

由五個服務(wù)器搭建的HPC集群系統(tǒng),其服務(wù)器的物理機參數(shù)如表1所示。其中,一個服務(wù)器作為頭節(jié)點與用戶交互,另外四個服務(wù)器作為計算節(jié)點完成頭節(jié)點分配的任務(wù)。

表1　物理機參數(shù)

圖7　集群系統(tǒng)結(jié)構(gòu)示意圖

為驗證算法有效性,反復(fù)進行了多組實驗。從中隨機給出五組實驗展示實驗結(jié)果,這五組實驗中集群系統(tǒng)四個計算節(jié)點的負載信息如表2所示。

表2　各計算節(jié)點負載情況

由于噪聲敏感程度不同區(qū)域?qū)υ肼暤戎稻€繪制的精度要求不同,設(shè)置各區(qū)域網(wǎng)格間距得分權(quán)重如下:

λ1=1,λ2=4,λ3=9,λ4=16

經(jīng)過多次試驗測試,可得適應(yīng)度函數(shù)中μ=0.8,η=0.2。

對于算法中交叉和變異算子,通過多次調(diào)試參數(shù)得到如圖9和圖10所示的相應(yīng)目標函數(shù)隨之變化的趨勢。從圖8和圖9中可以看出,當Pc=0.8、Pm=0.03時負載均衡程度和網(wǎng)格間距優(yōu)劣程度均最高,同時適應(yīng)度函數(shù)也在此情況下最高。

4.3實驗結(jié)果與分析

以國內(nèi)某大型機場為例,以機場跑道為中心將機場周圍24km×20km的區(qū)域空間矢量數(shù)據(jù)存儲到數(shù)據(jù)庫中。以400m的寬度將機場周圍區(qū)域沿跑道方向分成60個條形區(qū)域,根據(jù)航空器當前位置判斷受其噪聲影響的條形區(qū)域,根據(jù)集群系統(tǒng)各節(jié)點的負載情況對該噪聲影響區(qū)域的噪聲計算任務(wù)進行任務(wù)分配。

1) 圖10給出在機場噪聲等值線三維動態(tài)繪制任務(wù)分配生成的噪聲計算量與系統(tǒng)實際計算能力之間的對比。由表2給出的各計算節(jié)點負載情況可知,第1組實驗中的集群系統(tǒng)總噪聲計算能力為66141(計算噪聲的網(wǎng)格點數(shù)),而生成的總?cè)蝿?wù)量為61990,集群系統(tǒng)負載程度為93.724%。另外四組實驗中集群系統(tǒng)負載程度分別為93.534%、95.797%、93.492%、94.9687%,五組實驗的集群系統(tǒng)負載程度均大于90%。生成的任務(wù)量越多,表明網(wǎng)格間距越小。

圖8　Pc=0.8時負載均衡程度、網(wǎng)格間距優(yōu)劣程度、適應(yīng)度隨Pm的變化

圖9　Pm=0.03時時負載均衡程度、網(wǎng)格間距優(yōu)劣程度、適應(yīng)度隨Pc的變化

圖10　任務(wù)生成量與系統(tǒng)計算能力比較圖

實驗結(jié)果表明,本文中的任務(wù)分配方法能夠較好地利用系統(tǒng)資源,使得集群內(nèi)各計算節(jié)點在單位時間內(nèi)分配到的任務(wù)量最大化,從而有利于提高機場噪聲等值線三維動態(tài)繪制的精度和速度。

2) 將每組實驗中生成的任務(wù)按以下兩種方法分配給計算節(jié)點:

方法1:將總?cè)蝿?wù)量均等分成m份,分別分配給各計算節(jié)點;

方法2:按本文任務(wù)分配方法,根據(jù)各計算節(jié)點負載情況將任務(wù)負載均衡地分配給每個節(jié)點。

圖11表示在相同任務(wù)量下在集群系統(tǒng)中按方法1和方法2分配任務(wù)時計算噪聲所消耗時間大小對比。任務(wù)若按方法1分配給集群系統(tǒng)中負載情況各異的計算節(jié)點,則總?cè)蝿?wù)完成時間由負載最大的節(jié)點決定。比如實驗1中,若將生成任務(wù)量平均分配給集群中的計算節(jié)點,則負載最小的計算節(jié)點1和負載最大的計算節(jié)點3任務(wù)量均為15497,而計算節(jié)點1的當前噪聲計算能力為21336,計算節(jié)點3的當前計算能力為10346;此時實驗1中的集群任務(wù)響應(yīng)時間由計算節(jié)點3決定,約1.5s,而計算節(jié)點1完成平均分配到的任務(wù)約只需0.5s的時間,對于計算節(jié)點1來說,大約有1s的時間處于空閑狀態(tài),從而降低了集群系統(tǒng)資源利用率。而通過方法2分配給各節(jié)點的任務(wù)量與其當前噪聲計算能力相當,完成各自任務(wù)量的時間相差最大不過0.1s,計算節(jié)點不會長時間處于空閑狀態(tài),能夠充分利用系統(tǒng)資源,而且總?cè)蝿?wù)完成時間也能控制在單位時間(1s)內(nèi),可以滿足機場噪聲實時繪制要求。

圖11　兩種任務(wù)分配方法的任務(wù)響應(yīng)時間對比圖

特別是各節(jié)點負載相差較大時,如實驗3中計算節(jié)點1的負載為0%,而計算節(jié)點4的負載為80%,若平均分配任務(wù)則總?cè)蝿?wù)完成需要約3s的時間,而這個時間也是計算節(jié)點4完成自己分配到的任務(wù)的時間。而計算節(jié)點1早在約0.2s的時間內(nèi)完成了自己的噪聲計算任務(wù),新的任務(wù)又未到,計算節(jié)點1在將近2.8s的時間等待新任務(wù),處于空閑狀態(tài)。通過負載均衡的分配任務(wù),可以大幅度縮小節(jié)點1的等待時間,四個計算節(jié)點完成任務(wù)的時間相當,能夠有效縮短總?cè)蝿?wù)響應(yīng)時間,同時又能充分利用集群系統(tǒng)資源。

5　結(jié)語

本文針對機場噪聲等值線三維動態(tài)繪制問題,分析機場噪聲特性,尋找任務(wù)與服務(wù)器負載之間的關(guān)系,建立機場噪聲等值線三維動態(tài)繪制任務(wù)分配模型?？紤]各服務(wù)器節(jié)點的負載情況,用遺傳算法求解任務(wù)分配模型,實現(xiàn)集群系統(tǒng)中負載均衡和資源的有效利用,從而有利于提高機場噪聲等值線三維動態(tài)繪制的精度和速度。實驗結(jié)果證明,使用本文模型分配任務(wù)能夠縮短任務(wù)響應(yīng)時間,在滿足實時計算需求的同時能有效解決任務(wù)分配不均衡問題,并提高系統(tǒng)資源利用率和機場噪聲等值線三維動態(tài)繪制精度。

[1] 徐濤,曹枝東.基于路徑柵格的機場噪聲等值線追蹤算法[J].電子科技大學(xué)學(xué)報,2013,42(2):254-259.

XU Tao, CAO Zhidong. Airport Noise Isoline Tracking Algorithm Based on Route Grid[J]. Journal of University of Electronic Science and Technology of China,2013,42(2):254-259.

[2] 程國勇,王巍.單次飛行事件等值線計算方法的研究[J].噪聲與振動控制,2011,31(1):161-165.

CHENG Guoyong, WANG Wei. The Study on New Method of Single Flight Contour Calculation[J]. Noise and Vibration Control,2011,31(1):161-165.

[3] 計文斌,王建東,楊國慶.單航班噪聲動態(tài)等值線的繪制算法[J].噪聲與振動控制,2012,33(4):153-157.

JI Wenbin, WANG Jiandong, YANG Guoqing. Study on Calculation and Plotting of Dynamic Noise Contour of Single Flight Based on Equivalent Point Swing[J]. Noise and Vibration Control,2013,33(4):153-157.

[4] 黃寶香.基于VRGIS的城市噪聲三維分析模型及可視化評價研究[D].青島:中國海洋大學(xué),2011.

HUANG Baoxiang. Research on Urban Environmental Three Dimensional Noise Analysis Model and Visual Assessment Based on VRGIS[D]. Qingdao: Ocean University of China,2011.

[5] 徐言坤.基于VR-GIS的城市交通噪聲環(huán)境的三維可視化研究[D].青島:中國海洋大學(xué),2013.

XU Yankun. Research on 3D Visualization of Urban Traffic Noise Based on the VR-GIS[D]. Qingdao: Ocean University of China,2013.

[6] 莊敏.城市交通噪聲三維預(yù)測模型及其應(yīng)用研究[D].青島:中國海洋大學(xué),2013.

ZHUANG Min. Three-Dimensional Urban Traffic Noise Prediction Model and Its Application Research[D]. Qingdao: Ocean University of China,2013.

[7] 周文平,唐好選,季振洲.一種環(huán)境理解的分布式群體仿真任務(wù)劃分方法[J].電子學(xué)報,2014,42(12):2448-2456.

ZHOU Wenping, TANG Haoxuan, JI Zhenzhou. An Environment Structure Understanding Task Partition Method for Distributed Crowd Simulation[J]. Acta Electronica Sinica,2014,42(12):2448-2456.

[8] Zhou B, Zhou S. Parallel Simulation of Group Behaviors[C]//Proceedings of Winter Simulation Conference. IEEE,2004:193-211.

[9] 楊越,阮雅端,陳啟美.基于優(yōu)化遺傳算法的負載均衡策略研究[J].電子測量技術(shù),2014,37(6):26-29.

YANG Yue, RUAN Yaduan, CHEN Qimei. Load Balancing Strategy Based on Improved Genetic Algorithm[J]. Electronic Measurement Technology,2014,37(6):26-29.

[10] Shahapure N H, Jayarekha P. Load Balancing with Optimal Cost Scheduling Algorithm[C]//Proceedings of Computation of Power, Energy, Information and Communication(ICCPEIC). IEEE,2014:24-31.

[11] Bosque J L, Toharia P, Robles O D, et al. A Load Index and Load Balancing Algorithm for Heterogeneous Clusters[J]. Journal of Supercomputing,2013,65(3):1104-1113.

[12] Li W, Shi H. Novel Algorithm for Load Balancing in Cluster Systems[C]//Proceedings of Computer Supported Cooperative Work in Design(CSCWD). IEEE,2010:413-416.

[13] Su R, Wang Y. Immune Genetic Algorithm-based Load Balancing in Web Cluster[C]//Proceedings of the Fourth International Conference on Genetic and Evolutionary Computing. IEEE,2010:321-324.

[14] Huafeng D, Linhui Z, Maosheng Y. An Efficient Load Balancing Algorithm in Distributed Systems[C]//Proceedings of International Forum on Information Technology and Applications. IEEE,2010:397-400.

[15] 邊霞,米良.遺傳算法理論及其應(yīng)用研究進展[J].計算機應(yīng)用研究,2010,27(7):2425-2429.

BIAN Xia, MI Liang. Development on Genetic Algorithm Theory and Its Applications[J]. Application Research of Computers,2010,27(7):2425-2429.

[16] 楊錦,李肯立,吳帆.異構(gòu)分布式系統(tǒng)的負載均衡調(diào)度算法[J].計算機工程,2012,38(2):166-168.

YANG Jin, LI Kenli, WU Fan. Load Balance Schedule Algorithm for Heterogeneous Distributed System[J]. Computer Engineering,2012,38(2):166-168.

[17] 許海成,傅錦偉.服務(wù)器集群負載均衡的建模與仿真研究[J].計算機仿真,2012,29(3):180-183.

XU Haicheng, FU Jinwei. Research on Model and Simulation of Load Balancing for Server Cluster[J]. Computer Simulation,2012,29(3):180-183.

A Task Allocation Method for Dynamic Three-dimensional Drawing of Airport Noise Isoline
XU Tao1,2Huhemuqiri1
(1. College of Computer Science and Technology, Civil Aviation University of China, Tianjin300300)(2. Information Technology Research Base of Civil Aviation Administration of China, Tianjin300300)

Task allocation is one of the key factors to influence performance of cluster system,which affects load balancing and resources utilization of cluster system.In dynamic three-dimensional drawing of airport noise isoline, the drawing accuracy and noise computational complexity depends on grid spacing size.In this process, how to allocate the noise computing tasks for the dynamic three-dimensional drawing of airport noise isoline to different server nodes in the cluster system and dynamically control the grid spacing size is the important steps to increase the resources utilization of cluster system, shorten the average response time and improve the accuracy of drawing noise isoline. In order to achieve these purposes, this paper analyzes the environmental factors of area around the airport and distribution character of airport noise, establishes relationship between the noise computation and the load of server node, and then a task allocation model for dynamic three-dimensional drawing of airport noise isoline is proposed. The model is solved by genetic algorithm.The simulation results show that the proposed method allocates tasks balanced and makes full use of system resources,shorten response time, and finally achieve the real-time computing requirements for dynamic three-dimensional drawing of airport noise isoline.

airport noise isoline drawing, cluster system, taskallocation, genetic algorithm

2016年2月6日,

2016年3月18日

國家科技支撐計劃項目(編號:2014BAJ04B02);中央高校基本科研業(yè)務(wù)費專項資金(編號:3122013P013)資助。

徐濤,男,教授,博士生導(dǎo)師,研究方向:智能信息處理,智慧機場理論與方法。呼和木其日,女,碩士研究生,研究方向:智能信息處理。

TP391

10.3969/j.issn.1672-9722.2016.08.013