基于空間填充曲線(xiàn)的動(dòng)態(tài)負(fù)載均衡算法

張滬寅，何 華，姚化強(qiáng)，葉 剛

（武漢大學(xué) 計(jì)算機(jī)學(xué)院，湖北 武漢430072）

0 引 言

在集群系統(tǒng)中，負(fù)載均衡是影響實(shí)際服務(wù)器并行處理性能的關(guān)鍵因素［1，2］。判斷負(fù)載均衡效果的指標(biāo)，通常為用戶(hù)請(qǐng)求平均響應(yīng)時(shí)間以及系統(tǒng)吞吐量。

目前國(guó)內(nèi)外學(xué)者已對(duì)此問(wèn)題做出了大量的研究工作，提出多種負(fù)載均衡的策略，如輪詢(xún)調(diào)度算法、最小連接調(diào)度算法、響應(yīng)比優(yōu)先調(diào)度算法以及在此基礎(chǔ)上的各種加權(quán)調(diào)度算法等。但是，這些算法有的不能真實(shí)地反映服務(wù)器負(fù)載情況，有的自身會(huì)產(chǎn)生較大開(kāi)銷(xiāo)，以至于無(wú)法達(dá)到理想的負(fù)載均衡效果。在大規(guī)模集群系統(tǒng)中，更加考驗(yàn)著負(fù)載均衡的性能［3，4］。因此，本文以大規(guī)模集群系統(tǒng)為考察對(duì)象，在控制算法本身開(kāi)銷(xiāo)的基礎(chǔ)上，盡可能全面地考慮服務(wù)器各方面的負(fù)載指標(biāo)，以達(dá)到較優(yōu)的均衡效果。

1 研究現(xiàn)狀

目前主流的負(fù)載均衡策略可分為靜態(tài)和動(dòng)態(tài)兩類(lèi)［5－7］。靜態(tài)的負(fù)載均衡策略主要有輪詢(xún)算法、加權(quán)輪詢(xún)算法、目標(biāo)地址散列算法、源地址散列算法等，其基本原理是依據(jù)固定的概率分配任務(wù)［5］。動(dòng)態(tài)負(fù)載均衡會(huì)或多或少地考慮服務(wù)器的性能指標(biāo)和實(shí)時(shí)負(fù)載指標(biāo)，常見(jiàn)的有最小連接數(shù)算法、加權(quán)最小連接數(shù)算法、基于動(dòng)態(tài)反饋的算法等。相對(duì)而言，靜態(tài)的負(fù)載均衡策略實(shí)現(xiàn)簡(jiǎn)單，也不需要額外的系統(tǒng)開(kāi)銷(xiāo)，適用于訪(fǎng)問(wèn)量不大的系統(tǒng)。但數(shù)據(jù)表明通常情況下，動(dòng)態(tài)負(fù)載均衡較靜態(tài)負(fù)載均衡有30%～40%的性能提升［6］。動(dòng)態(tài)負(fù)載均衡更具有實(shí)用價(jià)值，目前該領(lǐng)域國(guó)內(nèi)外研究大都是針對(duì)動(dòng)態(tài)負(fù)載均衡算法的改進(jìn)，以充分利用服務(wù)器資源、及時(shí)響應(yīng)用戶(hù)請(qǐng)求。

實(shí)際應(yīng)用較多的動(dòng)態(tài)負(fù)載均衡策略是加權(quán)的最小連接數(shù)算法，以及在此基礎(chǔ)上改進(jìn)的基于動(dòng)態(tài)反饋算法。假設(shè)一組由N 臺(tái)服務(wù)器節(jié)點(diǎn)組成的集群，用S＝ ｛S0，S1，...，Sn－1｝表示，C（Si）表示第i個(gè)節(jié)點(diǎn)的連接數(shù)，W（Si）表示第i個(gè)節(jié)點(diǎn)的權(quán)值，則接收新請(qǐng)求的服務(wù)器節(jié)點(diǎn)C（Sm）的選擇是基于判定式 （1）

即選擇連接數(shù)與權(quán)重比值最小的服務(wù)器節(jié)點(diǎn)［8］。

但節(jié)點(diǎn)的連接數(shù)并不能準(zhǔn)確反應(yīng)服務(wù)器的負(fù)載情況，因此動(dòng)態(tài)反饋算法對(duì)此做出了改進(jìn)，考慮服務(wù)器節(jié)點(diǎn)的CPU 利用率L（Ci）、內(nèi)存利用率L（Mi）、硬盤(pán)I／O 占用率L（Di）、網(wǎng)絡(luò)帶寬占用率L（Ni）。為了使服務(wù)器的負(fù)載情況用一維列表存儲(chǔ)，使用了權(quán)重向量K＝ ｛K1，K2，K3，K4｝，服務(wù)器的負(fù)載量L（Si）由式 （2）得出

對(duì)于不同類(lèi)型的服務(wù)器，服務(wù)器的各個(gè)負(fù)載指標(biāo)對(duì)服務(wù)器的負(fù)載量的影響會(huì)有所不同，因此這里的權(quán)重向量是由管理員設(shè)置的。由此引出一個(gè)問(wèn)題，該權(quán)重向量有時(shí)不能很好地反映服務(wù)器節(jié)點(diǎn)的負(fù)載，那么就需要管理員不斷地調(diào)整這個(gè)權(quán)重向量，直到找到合適的一組為止，顯然會(huì)給管理帶來(lái)了許多麻煩。

2 基于空間填充曲線(xiàn)的負(fù)載均衡算法

2.1 Geohash算法

基于位置的服務(wù) （location based service，LBS）系統(tǒng)中對(duì)于基于地理位置的周邊資源的搜索，目前被廣泛使用且高效的算法就是Geohash算法。該算法通過(guò)空間填充曲線(xiàn)的降維特性，將二維空間中的坐標(biāo)點(diǎn)映射到一維區(qū)間，并且具有很好的可逆性，可以高效地找出當(dāng)前地理位置周邊的資源，大大縮小了搜索范圍，實(shí)現(xiàn)快速準(zhǔn)確定位的目標(biāo)［9］。

Geohash算法原理：

（1）首先將緯度范圍區(qū)間 ［－90，90］二分為 ［－90，0）和 ［0，90］兩個(gè)區(qū)間，分別稱(chēng)為左區(qū)間、右區(qū)間。如果要編碼的緯度位于左區(qū)間，則編碼為0，如果要編碼的緯度位于右區(qū)間，則編碼為1；

（2）遞歸上述過(guò)程，不斷編碼，如圖1 所示。最后總會(huì)確定維度在某個(gè)范圍 （a，b）之間；

（3）同樣的方法對(duì)精度進(jìn)行遞歸，那么精度也會(huì)確定在某個(gè)范圍 （c，d）之間；

（4）偶數(shù)位放經(jīng)度編碼，奇數(shù)位放緯度編碼形成位置信息的交叉組碼；

（5）最后將交叉組碼進(jìn)行Base32編碼；

一個(gè)編碼代表地理位置上的一片區(qū)域，編碼相似則代表著位置相近。如果資源編碼與當(dāng)前位置編碼越相似，代表著資源越近，如此可快速定位當(dāng)前地理位置周邊的資源，提高搜索效率［10］。

圖1 Geohash編碼過(guò)程

2.2 本文算法

針對(duì)動(dòng)態(tài)負(fù)載均衡需要人工設(shè)定權(quán)重以及在大規(guī)模集群系統(tǒng)中無(wú)法快速定位到最優(yōu)服務(wù)器的不足之處，本文在Geohash算法的思想基礎(chǔ)上，將負(fù)載均衡算法做出了改進(jìn)，使用空間填充曲線(xiàn)，將高維數(shù)組映射到一維陣列中，同時(shí)空間填充曲線(xiàn)能保證在高維空間上相鄰的節(jié)點(diǎn)，在一維上的排列也是相鄰的［5］。這樣我們就可以同時(shí)考慮各個(gè)服務(wù)器節(jié)點(diǎn)多個(gè)負(fù)載指標(biāo)了，不會(huì)發(fā)生因?yàn)闄?quán)重的設(shè)置不合理而引起在長(zhǎng)時(shí)間運(yùn)行后出現(xiàn)負(fù)載嚴(yán)重傾斜的情況，使得各個(gè)服務(wù)器節(jié)點(diǎn)各盡其能［11，12］。

空間填充曲線(xiàn)是一種降低空間維度的方法，能將高維空間的點(diǎn)映射為一維區(qū)間中的點(diǎn)。通過(guò)經(jīng)典線(xiàn)性索引結(jié)構(gòu)存儲(chǔ)這些一維區(qū)間中的點(diǎn)，能有效降低索引的復(fù)雜 度［11］。

本文算法首先使用空間填充曲線(xiàn)的降維特性，將由多個(gè)負(fù)載指標(biāo)構(gòu)成的高維空間坐標(biāo)映射為一維區(qū)間編碼，然后在一維編碼中查找具有最優(yōu)負(fù)載指標(biāo)的服務(wù)器編碼，大大加快了服務(wù)器節(jié)點(diǎn)篩選的效率，降低了算法的復(fù)雜度?？臻g填充曲線(xiàn)有多種，常用的有Hilbert曲線(xiàn)、Z 曲線(xiàn)和Gray曲線(xiàn)。由于Z 曲線(xiàn)生成算法簡(jiǎn)單、局部聚類(lèi)特性良好，本文選用Z曲線(xiàn)來(lái)實(shí)現(xiàn)算法。

本文算法主要有兩個(gè)步驟：一是利用Z 曲線(xiàn)降維原理對(duì)負(fù)載指標(biāo)進(jìn)行編碼，二是查找最優(yōu)編碼 （最優(yōu)編碼代表性能最好的服務(wù)器編碼）。

一組服務(wù)器節(jié)點(diǎn)S＝ ｛S0，S1，...，Sn－1｝，用Ci表示各個(gè)節(jié)點(diǎn)的CPU 利用率，Mi表示節(jié)點(diǎn)的內(nèi)存利用率。而Ci和Mi取值都在 ［0，1］之間，即負(fù)載指標(biāo)構(gòu)成的空間范圍為 ［0，0］～ ［1，1］。

對(duì)負(fù)載指標(biāo)進(jìn)行編碼：本文對(duì)服務(wù)器節(jié)點(diǎn)Si的Ci和Mi這兩個(gè)性能指標(biāo)分別進(jìn)行逼近編碼。以Ci為例，步驟如下：

（1）將區(qū)間 ［0，1］二分為 ［0，0.5），［0.5，1］，稱(chēng)為左右區(qū)間，如果Ci落在左區(qū)間 ［0，0.5），則標(biāo)記為0，落在右區(qū)間 ［0.5，1］，則標(biāo)記為1；

（2）繼 續(xù) 將 區(qū) 間 ［0，0.5）二 分 為 ［0，0.25），［0.25，0.5），如果Ci落在左區(qū)間 ［0，0.25），則標(biāo)記為0，落在右區(qū)間 ［0.25，0.5），則標(biāo)記為1；

（3）遞歸上述過(guò)程Ci總是屬于某個(gè)區(qū)間 ［a，b］。隨著每次迭代區(qū)間 ［a，b］不斷縮小，并越來(lái)越逼近Ci。

（4）隨著算法執(zhí)行會(huì)產(chǎn)生一個(gè)二進(jìn)制序列，序列的長(zhǎng)度跟給定的區(qū)間劃分次數(shù)有關(guān)。

同理可得到Mi的編碼序列，然后偶數(shù)位放內(nèi)存利用率編碼，奇數(shù)位放CPU 利用率編碼，進(jìn)行交叉組碼可得到最終編碼Zi。

編碼后可以獲得此組服務(wù)器的編碼Z＝ ｛Z0，Z1，…，Zn－1｝，本文將此編碼簡(jiǎn)稱(chēng)為Z－h(huán)ash碼。在圖2中反映了這個(gè)編碼過(guò)程。

圖2 Z－h(huán)ash碼的生成

查找最優(yōu)編碼：可以看出相鄰的負(fù)載指標(biāo)組成的點(diǎn)具有相似Z－h(huán)ash 碼，Z－h(huán)ash 碼與 ［0，0］的Z－h(huán)ash 碼越相近，則代表著具有該編碼的服務(wù)器負(fù)載能力越強(qiáng)。因此通過(guò)查找距離 ［0，0］的Z－h(huán)ash碼最近的Z－h(huán)ash碼，即可找到負(fù)載能力最強(qiáng)的一組服務(wù)器節(jié)點(diǎn)。這里找出的是一組服務(wù)器節(jié)點(diǎn)，主要由于不同的服務(wù)器節(jié)點(diǎn)可能負(fù)載指標(biāo)相同或相近，具有相同的Z－h(huán)ash碼。

從 ［0，0］的編碼出發(fā)，不斷擴(kuò)大搜索范圍，直至有服務(wù)器節(jié)點(diǎn)落入，則找到了最優(yōu)編碼，圖3 為擴(kuò)大搜索范圍這個(gè)過(guò)程的示意。只要存在處于正常狀態(tài)下的服務(wù)器，則一定能找到這個(gè)最優(yōu)編碼，而一個(gè)編碼代表著一個(gè)區(qū)域，即可能多個(gè)服務(wù)器具有相同編碼。如果此編碼區(qū)域只有一臺(tái)服務(wù)器，則此服務(wù)器入選；如包含多臺(tái)服務(wù)器，則使用最小連接數(shù)作進(jìn)一步篩選，找到最合適處理請(qǐng)求的服務(wù)器。

圖3 尋找最優(yōu)編碼

引入空間填充曲線(xiàn)可在使用最小連接數(shù)之前，通過(guò)編碼從大規(guī)模服務(wù)器集群系統(tǒng)中過(guò)濾出性能最優(yōu)的服務(wù)器，有效地提高了負(fù)載均衡算法的效率。

3 算法的具體實(shí)現(xiàn)

3.1 負(fù)載均衡器端

負(fù)載均衡器端主要工作如下：①收集服務(wù)器端發(fā)來(lái)的負(fù)載指標(biāo)；②使用空間填充曲線(xiàn)過(guò)濾出最優(yōu)編碼服務(wù)器；③使用最小連接算法確定目標(biāo)服務(wù)器節(jié)點(diǎn)；④更新目標(biāo)服務(wù)器連接數(shù)，轉(zhuǎn)發(fā)請(qǐng)求。

集群系統(tǒng)中各個(gè)服務(wù)器節(jié)點(diǎn)會(huì)在一個(gè)固定周期T 內(nèi)不同步地向負(fù)載均衡器端發(fā)送服務(wù)器的負(fù)載指標(biāo)，包括CPU利用率、內(nèi)存利用率、連接數(shù)以及Z－h(huán)ash碼等。均衡器端維護(hù)著一個(gè)存儲(chǔ)各服務(wù)器負(fù)載指標(biāo)的負(fù)載指標(biāo)表，某一時(shí)刻的表內(nèi)容如表1所示，每當(dāng)收到服務(wù)器端發(fā)來(lái)的信息會(huì)更新此性能指標(biāo)表。其中服務(wù)器狀態(tài)，主要是由預(yù)設(shè)的性能指標(biāo)閾值來(lái)判斷，當(dāng)指標(biāo)超過(guò)閾值上限，服務(wù)器處于滿(mǎn)負(fù)荷，服務(wù)器狀態(tài)標(biāo)記為0。負(fù)載均衡器端收到請(qǐng)求后，會(huì)在服務(wù)器狀態(tài)為1 （服務(wù)器狀態(tài)良好）的編碼中查找代表最優(yōu)負(fù)載能力的最優(yōu)編碼Z0，然后找出編碼同為Z0的k個(gè)服務(wù)器節(jié)點(diǎn)。當(dāng)k＞1 時(shí)，使用最小連接數(shù)算法確定出目標(biāo)服務(wù)器節(jié)點(diǎn)，將請(qǐng)求轉(zhuǎn)發(fā)到此服務(wù)器；當(dāng)k＝1時(shí)，直接將請(qǐng)求轉(zhuǎn)發(fā)到此服務(wù)器節(jié)點(diǎn)。當(dāng)k＝0 時(shí)，表示集群系統(tǒng)暫時(shí)癱瘓，所有服務(wù)器處于滿(mǎn)載狀態(tài)。每次轉(zhuǎn)發(fā)請(qǐng)求后，都會(huì)更新服務(wù)器性能指標(biāo)表中此服務(wù)器節(jié)點(diǎn)的連接數(shù)，將其增加1，避免將請(qǐng)求不斷發(fā)往此服務(wù)器，導(dǎo)致集群系統(tǒng)傾斜。

表1 服務(wù)器性能指標(biāo)

3.2 服務(wù)器節(jié)點(diǎn)端

服務(wù)器節(jié)點(diǎn)端主要工作如下：

（1）設(shè)定CPU 利用的閥值上限為75%，內(nèi)存利用率的閥值上限為90%；

（2）當(dāng)時(shí)鐘周期T 到達(dá)時(shí)獲取各個(gè)負(fù)載指標(biāo)，而當(dāng)CPU 利用率或內(nèi)存利用率指標(biāo)值大于閾值上限時(shí)，將服務(wù)器狀態(tài)標(biāo)記為0 （服務(wù)器滿(mǎn)負(fù)荷）；

（3）將CPU 利用率、內(nèi)存利用率按以上原則編碼為Zhash碼；

（4）將CPU 利用率、內(nèi)存利用率、連接數(shù)、服務(wù)器狀態(tài)以及Z－h(huán)ash碼定期發(fā)往負(fù)載均衡器端；

（5）處理均衡器端轉(zhuǎn)發(fā)來(lái)的請(qǐng)求。

由于Z－h(huán)ash碼的生成需要消耗一定的資源，而為減輕均衡器端的壓力，將Z－h(huán)ash編碼放在服務(wù)器節(jié)點(diǎn)端，避免均衡器端成為系統(tǒng)的瓶頸［13，14］。

4 實(shí)驗(yàn)及分析

為評(píng)估本文算法的效果，搭建一個(gè)Web服務(wù)集群系統(tǒng)進(jìn)行實(shí)驗(yàn)。在均衡策略上，分別實(shí)現(xiàn)了動(dòng)態(tài)反饋算法和本文提出的基于空間填充曲線(xiàn)算法。其中動(dòng)態(tài)反饋算法使用式（2）計(jì)算服務(wù)器負(fù)載量，且權(quán)重系數(shù)使用最常用的K＝｛0.35，0.25，0.2，0.2｝［5］。本次實(shí)驗(yàn)使用一臺(tái)服務(wù)器作為負(fù)載均衡器，12臺(tái)服務(wù)器作為后端服務(wù)器，所有服務(wù)器安裝CentOS 6.x系統(tǒng)，并處于同一局域網(wǎng)中。使用一臺(tái)裝有WAS工具的客戶(hù)機(jī)模擬用戶(hù)發(fā)送請(qǐng)求。

本次實(shí)驗(yàn)分為6組進(jìn)行，集群服務(wù)器數(shù)量分別為2臺(tái)、4臺(tái)、6臺(tái)、8臺(tái)、10臺(tái)、12臺(tái)。服務(wù)器每隔3s向均衡器發(fā)送自己的負(fù)載指標(biāo)。客戶(hù)機(jī)使用WAS工具模擬用戶(hù)不斷發(fā)出請(qǐng)求，持續(xù)時(shí)間為1分鐘、強(qiáng)度為200。本次實(shí)驗(yàn)主要使用任務(wù)平均響應(yīng)時(shí)間和系統(tǒng)吞吐量?jī)蓚€(gè)評(píng)價(jià)指標(biāo)，兩種均衡算法的測(cè)試結(jié)果如圖4、圖5所示。

圖4 平均響應(yīng)時(shí)間比較

圖5 系統(tǒng)吞吐量比較

從圖4和圖5可以看出，隨著集群規(guī)模的擴(kuò)大，本文算法的均衡效果逐漸提升。當(dāng)集群服務(wù)器節(jié)點(diǎn)數(shù)只有2臺(tái)、4臺(tái)、6臺(tái)時(shí)，本文算法均衡效果無(wú)論從平均響應(yīng)時(shí)間或系統(tǒng)吞吐量來(lái)看，相對(duì)于動(dòng)態(tài)反饋算法較弱，但當(dāng)服務(wù)器節(jié)點(diǎn)數(shù)量達(dá)到8臺(tái)、10臺(tái)、12臺(tái)時(shí)本文算法均衡效果明顯優(yōu)于動(dòng)態(tài)反饋算法。

出現(xiàn)此結(jié)果主要緣于本文算法首輪篩選效率很高，能快速?gòu)拇罅繑?shù)據(jù)中定位到最優(yōu)編碼，而動(dòng)態(tài)反饋算法每次都是從所有服務(wù)器節(jié)點(diǎn)做出篩選，這將造成額外開(kāi)銷(xiāo)，隨著集群規(guī)模增大則效率降低。而在集群規(guī)模很小時(shí)，本文算法多出的一個(gè)編碼過(guò)程會(huì)稍稍影響均衡效果，因此在服務(wù)器只有2臺(tái)、4臺(tái)、6臺(tái)時(shí)，均衡效果較動(dòng)態(tài)反饋弱。

通過(guò)具體的實(shí)驗(yàn)數(shù)據(jù)可知，與動(dòng)態(tài)反饋算法相比，當(dāng)服務(wù)器數(shù)量較小時(shí)本文算法均衡效果一般，而當(dāng)集群規(guī)模擴(kuò)大時(shí)，本文算法負(fù)載均衡效果明顯改善。

5 結(jié)束語(yǔ)

本文針對(duì)一種動(dòng)態(tài)反饋負(fù)載均衡算法進(jìn)行了改進(jìn)，提出應(yīng)用空間填充曲線(xiàn)快速篩選負(fù)載性能最優(yōu)服務(wù)器的編碼，并使用最小連接數(shù)確定當(dāng)前最適合處理請(qǐng)求的服務(wù)器節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，相對(duì)于動(dòng)態(tài)反饋算法，本文算法在集群規(guī)模較大時(shí)具有較好的負(fù)載效果。

本文為了控制算法開(kāi)銷(xiāo)，未考慮服務(wù)器的硬盤(pán)I／O 占用率和響應(yīng)比等相關(guān)性能指標(biāo)，未來(lái)研究工作中會(huì)合理加入考慮，以實(shí)現(xiàn)更完善的均衡方案。同時(shí)考慮服務(wù)器3個(gè)或者4個(gè)性能指標(biāo)因子的時(shí)，可以嘗試使用Hilbert填充曲線(xiàn)，在高維降維算法上或許可以取得較優(yōu)效果。

［1］LIU Xu，MO Zeyao，CHAO Xiaolin.A one－dimensional load balancing method based on memory constraint and its application［J］.Chinese Journal of Computational Physics，2009，26（2）：184－190 （in Chinese）.［劉旭，莫?jiǎng)t堯，曹小林.基于內(nèi)存約束的一維負(fù)載平衡方法及其應(yīng)用 ［J］.計(jì)算物理，2009，26 （2）：184－190.］

［2］Zhang Lin，Li Xiaoping，Su Yuan.A content－based dynamic load－balancing algorithm for heterogeneous Web server cluster［J］.Computer Science and Information Systems／ComSIS，2010，7 （1）：153－162.

［3］Khayyat Z，Awara K，Alonazi A，et al.Mizan：A system for dynamic load balancing in large－scale graph processing ［C］／／Proceedings of the 8th ACM European Conference on Computer Systems.ACM，2013：169－182.

［4］Clarke D，Lastovetsky A，Rychkov V.Dynamic load balancing of parallel computational iterative routines on platforms with memory heterogeneity ［C］／／Euro－Par Parallel Processing Workshops.Berlin：Springer Berlin Heidelberg，2011：41－50.

［5］ZHOU Songqun.An improved dynamic load－balancing algorithm for cluster ［J］.Computer and Modernization，2012（1）：135－139 （in Chinese）. ［周松泉.一種改進(jìn)的集群動(dòng)態(tài)負(fù)載均衡算法 ［J］.計(jì)算機(jī)與現(xiàn)代化，2012 （1）：135－139.］

［6］MAI Jingjing，GONG Hongyan，SONG Chunhe.Dynamic feedback load balancing strategy in cluster system ［J］.Computer Engineering，2008，34 （16）：114－118 （in Chinese）.［買(mǎi)京京，龔紅艷，宋純賀.集群系統(tǒng)中的動(dòng)態(tài)反饋負(fù)載均衡策略 ［J］.計(jì)算機(jī)工程，2008，34 （16）：114－118］.

［7］WANG Hongbin.Research on adaptive load balancing scheduling strategy in Web cluster system ［D］.Changchun：Jilin University，2013 （in Chinese）.［王紅斌.Web服務(wù)器集群系統(tǒng)的自適應(yīng)負(fù)載均衡調(diào)度策略研究 ［D］.長(zhǎng)春：吉林大學(xué)，2013.］

［8］LIU Shaofeng，DONG Jian，WU Zhibo.A dynamic－feedback scheduling algorithm for cluster load balancing based on priority queue［J］.Intelligent Computer and Applications，2012，2（4）：78－80 （in Chinese）. ［柳少鋒，董劍，吳智博.一種基于優(yōu)先級(jí)隊(duì)列的集群動(dòng)態(tài)反饋調(diào)度算法 ［J］.智能計(jì)算機(jī)與應(yīng)用，2012，2 （4）：78－80.］

［9］YE Xiaorong，SHAO Qing.Mobile advertising system based on augmented reality and location－based services［J］.Science＆ Technology Review，2013，31 （4）：67－73 （in Chinese）.［葉小榕，邵晴.基于增強(qiáng)現(xiàn)實(shí)和位置服務(wù)的手機(jī)廣告系統(tǒng)［J］.科技導(dǎo)報(bào)，2013，31 （4）：67－73.］

［10］JIN An，CHENG Chengqi，SONG Shushua.Regional query of area data based on Geohash ［J］.Geography and Geo－Information Science，2013，29 （5）：31－35 （in Chinese）.［金安，程承旗，宋樹(shù)華，等.基于Geohash的面數(shù)據(jù)區(qū)域查詢(xún) ［J］.地理與地理信息科學(xué)，2013，29 （5）：31－35.］

［11］Harlacher DF，Klimach H，Roller S，et al.Dynamic load balancing for unstructured meshes on space－filling curves［C］／／IEEE 26th International Parallel and Distributed Processing Symposium Workshops ＆ PhD Forum，2012：1661－1669.

［12］Deng Y，Lau RWH.On delay adjustment for dynamic load balancing in distributed virtual environments ［J］.IEEE Transactions on Visualization and Computer Graphics，2012，18 （4）：529－537.

［13］Gawande DS，Dharmik RC，Panse C.A load balancing in grid environment ［J］.International Journal of Engineering Research and Application，2012，2 （2）：445－450.

［14］Li R，Zhang Y，Xu Z，et al.A Load－balancing method for network GISs in a heterogeneous cluster－based system using access density ［J］.Future Generation Computer Systems，2013，29 （2）：528－535.