范兆煒，李子揚(yáng)，周增光，李傳榮

(1. 中國(guó)科學(xué)院光電研究院中國(guó)科學(xué)院定量遙感信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100094； 2. 中國(guó)科學(xué)院大學(xué)，北京 100049)

對(duì)等網(wǎng)絡(luò)遙感影像瓦片資源遺傳選擇算法

范兆煒1,2，李子揚(yáng)1，周增光1，李傳榮1

(1. 中國(guó)科學(xué)院光電研究院中國(guó)科學(xué)院定量遙感信息技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100094； 2. 中國(guó)科學(xué)院大學(xué)，北京 100049)

對(duì)等網(wǎng)絡(luò)技術(shù)的快速發(fā)展，為遙感影像數(shù)據(jù)的高效共享開辟了新的途徑。對(duì)等節(jié)點(diǎn)終端間互相進(jìn)行數(shù)據(jù)傳輸?shù)姆绞?，有效地降低了?shù)據(jù)共享對(duì)服務(wù)器的依賴程度，極大地提高了數(shù)據(jù)分發(fā)傳輸?shù)男省Ｓ捎趯?duì)等網(wǎng)絡(luò)中各終端可能存儲(chǔ)不同區(qū)域的影像數(shù)據(jù)，因此當(dāng)需要共享某個(gè)影像數(shù)據(jù)時(shí)，選擇從哪些終端傳輸哪些瓦片以提高傳輸效率，是一個(gè)需要解決的重要問題。本文研究對(duì)等終端間瓦片數(shù)據(jù)集的高效共享途徑，提出了一種基于遺傳算法的瓦片資源選擇方法，可以有效地解決對(duì)等網(wǎng)瓦片資源選擇問題。

遙感影像；瓦片；對(duì)等網(wǎng)；數(shù)據(jù)傳輸；組合優(yōu)化；遺傳算法

Abstract： The rapid development of peer-to-peer network technology opens up a new way for the efficient sharing of remote sensing image data. The way of data transmission between peer nodes can effectively reduce the dependence of data sharing on the server, and greatly improve the efficiency of data distribution and transmission. As each terminal in the peer-to-peer network may store image data in different areas, therefore, when you need to share a certain image data, how to choose from which terminals to transmit which tiles to improve the transmission efficiency, is an important problem needed to be solved. This paper studies the efficient way to share the tile data sets between peer-to-peer terminals, and proposes a tile resource selection method based on genetic algorithm, which can effectively solve the problem of tile resource selection in the peer-to-peer network.

Keywords： remote sensing image; tiles; P2P; data transmission; combinatorial optimization; genetic algorithm

瓦片數(shù)據(jù)模型是一種受到廣泛應(yīng)用的影像數(shù)據(jù)模型，其基本思想是將一幅遙感影像按指定的網(wǎng)格大小均勻劃分，從而得到一組瓦片數(shù)據(jù)集[1-3]。通過服務(wù)器來發(fā)布和管理瓦片數(shù)據(jù)，是目前對(duì)海量遙感影像數(shù)據(jù)進(jìn)行組織與管理的主要方式[4-7]。

隨著網(wǎng)絡(luò)技術(shù)的快速發(fā)展，對(duì)等網(wǎng)絡(luò)傳輸技術(shù)利用大量的客戶端資源來分擔(dān)服務(wù)器的壓力，不但有效地降低了系統(tǒng)對(duì)服務(wù)器的依賴程度，提高了系統(tǒng)的穩(wěn)定性，還極大地提高了數(shù)據(jù)分發(fā)傳輸?shù)男省?duì)等網(wǎng)絡(luò)傳輸技術(shù)為海量遙感影像數(shù)據(jù)的高效共享開辟了一條新的途徑。

在對(duì)等網(wǎng)絡(luò)中，當(dāng)需求某一影像數(shù)據(jù)時(shí)，既可以從服務(wù)器端下載影像數(shù)據(jù)，也可以選擇從其他終端中獲取影像數(shù)據(jù)。這種方式既降低了客戶端對(duì)服務(wù)器的依賴性，也提高了數(shù)據(jù)傳輸效率。與服務(wù)器不同，對(duì)等網(wǎng)絡(luò)中各終端存儲(chǔ)的數(shù)據(jù)各不相同，不同的終端可能存儲(chǔ)著不同的瓦片數(shù)據(jù)。在對(duì)等網(wǎng)絡(luò)中，當(dāng)某一終端需要下載某一組瓦片數(shù)據(jù)時(shí)，選擇從哪些終端下載哪些瓦片以提高傳輸效率，是一個(gè)需要解決的重要問題。

在給定的多個(gè)終端及多個(gè)候選影像瓦片資源中，如何選擇從其中的某些終端下載某些瓦片，使得在獲取全部被需求瓦片的條件下，使傳輸耗時(shí)最短，是一個(gè)組合優(yōu)化問題。組合優(yōu)化問題是指在離散的、有限的數(shù)據(jù)結(jié)構(gòu)上及給定的約束條件下尋找目標(biāo)函數(shù)最優(yōu)解的問題，在規(guī)劃調(diào)度、資源分配、決策等問題中有著非常廣泛的應(yīng)用[8-9]。典型的組合優(yōu)化問題有旅行商問題[10-13]、背包問題等。當(dāng)問題規(guī)模較小時(shí)，應(yīng)用枚舉法等常規(guī)方法就可以得到較好的可行解，但當(dāng)問題規(guī)模較大時(shí)，解空間過大，常規(guī)方法已經(jīng)無法適用。為了能夠求解較大規(guī)模問題下的最優(yōu)解，許多智能優(yōu)化算法如蟻群算法、遺傳算法、模擬退火算法等開始逐步應(yīng)用于組合優(yōu)化問題中。

遺傳算法(genetic algorithm)是眾多求解方法中非常有效的一種。遺傳算法是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程、按照適者生存和優(yōu)勝劣汰原理搜索最優(yōu)解的方法[5-15]。遺傳算法的優(yōu)點(diǎn)在于其搜索覆蓋面大，有利于全局擇優(yōu)且具有可擴(kuò)展性，容易與其他算法結(jié)合。

遺傳算法的運(yùn)算對(duì)象是基因型——表示個(gè)體的符號(hào)串，進(jìn)行遺傳算法擇優(yōu)的基礎(chǔ)是進(jìn)行基因設(shè)計(jì)，即實(shí)現(xiàn)表現(xiàn)型到基因型的映射即編解碼工作。遺傳算法的基本運(yùn)算過程如下：

(1) 初始化：設(shè)置終止進(jìn)化的條件，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(0)。

(2) 適應(yīng)度計(jì)算：計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度。

(3) 選擇運(yùn)算：根據(jù)個(gè)體適應(yīng)度，選擇交配雙方，適應(yīng)度越高，被選中的概率也越高，即物競(jìng)天擇。

(4) 交叉運(yùn)算：交配過程中父母雙方基因產(chǎn)生交叉。

(5) 變異運(yùn)算：將子代個(gè)體的某些基因值作變動(dòng)。

(6) 新群體產(chǎn)生：群體P(t)經(jīng)過選擇、交叉、變異運(yùn)算之后得到子群體P(t+1)。

(7) 終止進(jìn)化：觸發(fā)終止條件后終止計(jì)算，種群停止進(jìn)化，以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出。

1 瓦片資源遺傳選擇算法

1.1 基因設(shè)計(jì)

基因的編碼方法必須能夠覆蓋問題的所有可行解，本文采用字符編碼的方式對(duì)表現(xiàn)型進(jìn)行編碼：一個(gè)字符唯一對(duì)應(yīng)一個(gè)瓦片資源，一個(gè)瓦片資源唯一對(duì)應(yīng)一個(gè)字符。表現(xiàn)型與基因型通過編碼方式與解碼方式相互轉(zhuǎn)換。編碼方式詳細(xì)說明如下。

如圖1所示，假設(shè)落在需求范圍內(nèi)的瓦片共有9個(gè)，依次編號(hào)為1至9。某終端存儲(chǔ)有編號(hào)為1、3、9的瓦片資源，選擇某一瓦片則對(duì)應(yīng)字符為1，否則為0。如果選擇下載編號(hào)為1、9的瓦片資源、不選擇編號(hào)為3的瓦片資源，那么此終端對(duì)應(yīng)的字符串即基因片段為101?；蛐途幋a示例見表1。

圖1 落在需求范圍內(nèi)的瓦片數(shù)據(jù)

終端A終端B終端C瓦片存儲(chǔ)1、3、92、3、51、5、6、7、8選擇的瓦片1、925、6、8基因片段10110001101完整基因10110001101

1.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度是遺傳算法中最關(guān)鍵的一個(gè)參數(shù)。在生物學(xué)中，適應(yīng)度表示個(gè)體對(duì)環(huán)境的適應(yīng)能力，是用來評(píng)判群體中個(gè)體的優(yōu)劣程度，適應(yīng)度越高，其繁衍后代的能力也越強(qiáng)。適應(yīng)度反映了一個(gè)基因序列被選中的概率，適應(yīng)度越高，其被選中的概率也越高。

瓦片資源選擇目標(biāo)是在保證覆蓋全部需求范圍的條件下使傳輸耗時(shí)盡可能短。本文基于各終端的歷史傳輸速度，以多線程傳輸?shù)姆绞綇母鱾€(gè)終端下載瓦片數(shù)據(jù)，在不考慮帶寬限制的情況下，傳輸總耗時(shí)等于需求終端對(duì)各終端中的最大傳輸耗時(shí)。傳輸總耗時(shí)計(jì)算方法見表2，“…”表示數(shù)據(jù)根據(jù)實(shí)際選擇而變化，其值不唯一；歷史平均傳輸速度通過查詢各終端歷史傳輸速度表數(shù)據(jù)并進(jìn)行計(jì)算得來；各終端傳輸耗時(shí)通過被選瓦片的總數(shù)據(jù)量除以歷史平均傳輸速度而得。

根據(jù)求解目標(biāo)，適應(yīng)度函數(shù)初步設(shè)計(jì)為

F(x)=covRatio·(max[t1,t2,t3,…,tn]-tx)

式中，covRatio表示選擇的不同瓦片個(gè)數(shù)與需求的不同瓦片總數(shù)之間的關(guān)系：當(dāng)選擇的不同瓦片個(gè)數(shù)等于需求的不同瓦片總數(shù)，則covRatio=1，反之covRatio=0，適應(yīng)度也會(huì)等于零，表示此基因個(gè)體被淘汰。covRatio參數(shù)的設(shè)計(jì)主要是為了保證能夠下載所有被需求的不同瓦片資源。

表2 某基因?qū)?yīng)的總傳輸耗時(shí)計(jì)算方法

max[t1,t2,t3,…,tn]-tx中，tx表示種群中第x個(gè)基因?qū)?yīng)的數(shù)據(jù)傳輸時(shí)間，x=1,2,…,n。max[t1,t2,t3,…,tn]-tx表示種群中各基因數(shù)據(jù)傳輸時(shí)間中的最大數(shù)據(jù)傳輸時(shí)間減去每一個(gè)基因個(gè)體對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間。基因個(gè)體對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間越短，此基因個(gè)體的適應(yīng)度越高。顯然此參數(shù)會(huì)直接淘汰掉數(shù)據(jù)傳輸時(shí)間最長(zhǎng)的那個(gè)基因個(gè)體，因此可以加快種群的進(jìn)化速度。

同時(shí)，max[t1,t2,t3,…,tn]-tx的參數(shù)形式也表明，基因個(gè)體的適應(yīng)度是相對(duì)于種群中其他基因個(gè)體而言的，即此適應(yīng)度是相對(duì)適應(yīng)度，因此隔代基因個(gè)體之間無法通過適應(yīng)度判斷其相對(duì)好壞。在遺傳算法計(jì)算中，系統(tǒng)無法單獨(dú)計(jì)算每一個(gè)基因個(gè)體的適應(yīng)度，必須要以群體為單位進(jìn)行相對(duì)適應(yīng)度計(jì)算，每進(jìn)行一輪交配繁衍，需要重新對(duì)群體中各基因個(gè)體的適應(yīng)度進(jìn)行計(jì)算。

此外，當(dāng)種群中基因個(gè)體對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間全部相同時(shí)，max[t1,t2,t3,…,tn]-tx的值會(huì)變?yōu)榱?，因此適應(yīng)度也會(huì)變?yōu)榱?。由于適應(yīng)度為零的基因個(gè)體不會(huì)被選中去進(jìn)行交配繁殖，因此為了保證種群能夠繼續(xù)進(jìn)化，當(dāng)種群中基因個(gè)體對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間全部相同時(shí)，所有的基因個(gè)體的適應(yīng)度設(shè)為最大數(shù)據(jù)傳輸時(shí)間。

最后，max[t1,t2,t3,…,tn]-tx的參數(shù)形式并不能保證去掉所有的重復(fù)數(shù)據(jù)選擇，因此還需要對(duì)遺傳算法得出的最優(yōu)解繼續(xù)進(jìn)行去重，以保證最終的結(jié)果不會(huì)重復(fù)下載相同的瓦片。

最終，適應(yīng)度函數(shù)設(shè)計(jì)為：

當(dāng)種群中各基因個(gè)體對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間不盡相同時(shí)

F(x)=covRatio·(max[t1,t2,t3,…,tn]-tx)

當(dāng)種群中各基因個(gè)體對(duì)應(yīng)的數(shù)據(jù)傳輸時(shí)間全部相同時(shí)

F(x)=covRatio·t

式中，當(dāng)選擇的不同瓦片個(gè)數(shù)等于需求的不同瓦片總數(shù)時(shí)，則covRatio=1，反之covRatio=0。

1.3 遺傳選擇算法計(jì)算過程

瓦片數(shù)據(jù)選擇的遺傳算法操作過程為：

(1) 初始化：設(shè)置最大進(jìn)化次數(shù)T=20，隨機(jī)生成20個(gè)互不相同的基因個(gè)體作為初始群體P(0)。

(2) 適應(yīng)度計(jì)算：開始繁殖與進(jìn)化，計(jì)算群體中每一個(gè)基因個(gè)體的適應(yīng)度。

(3) 選擇運(yùn)算：首先根據(jù)每個(gè)基因個(gè)體的適應(yīng)度計(jì)算其被選中的概率

然后以輪盤賭的方式選擇交配的雙方，如圖2所示，基因個(gè)體的適應(yīng)度越高，其在輪盤上的面積越大，被選中的概率也就越大。

圖2 輪盤賭

(4) 交叉運(yùn)算：如圖3所示，交配雙方進(jìn)行交配，雙方基因產(chǎn)生交叉，交叉位置隨機(jī)。

圖3 交叉運(yùn)算

(5) 變異運(yùn)算：對(duì)新個(gè)體，隨機(jī)選取變異點(diǎn)，變異點(diǎn)值為0則變1，為1則變0，變異概率p設(shè)為0.2%。例如，新基因個(gè)體1100001，變異點(diǎn)位置5，變異后基因?yàn)?100101。

(6) 產(chǎn)生新群體：對(duì)群體中重復(fù)步驟(3)～(5)，采用精英主義將上一代中適應(yīng)度最高的基因個(gè)體直接保留進(jìn)入下一代。對(duì)群體經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體。

(7) 終止：新群體繼續(xù)產(chǎn)生新群體：對(duì)新群體繼續(xù)執(zhí)行群體進(jìn)化操作。當(dāng)群體進(jìn)化次數(shù)達(dá)到最大進(jìn)化次數(shù)T，則最終群體中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。

(8) 最優(yōu)解去重：由于遺傳算法得出的最優(yōu)解并不能保證去掉所有的重復(fù)數(shù)據(jù)下載，因此還需要對(duì)遺傳算法得出的最優(yōu)解繼續(xù)進(jìn)行去重，以保證最終的結(jié)果不會(huì)重復(fù)下載相同的瓦片。

2 試驗(yàn)與結(jié)果分析

2.1 測(cè)試數(shù)據(jù)

測(cè)試數(shù)據(jù)集為：模擬10個(gè)終端，落在需求范圍內(nèi)的不同瓦片總個(gè)數(shù)為9，每個(gè)瓦片大小為1 MB，種群規(guī)模100，群體進(jìn)化20次。瓦片分布見表3，下載全部不同瓦片的最短傳輸時(shí)間為0.4 s，最長(zhǎng)傳輸時(shí)間為3 s。

表3 瓦片分布

2.2 遺傳選擇算法計(jì)算結(jié)果

重復(fù)進(jìn)行20次試驗(yàn)，結(jié)果如圖4所示：上方虛線表示所有可行解中數(shù)據(jù)傳輸耗時(shí)的最大值(3 s)，下方虛線表示所有可行解中數(shù)據(jù)傳輸耗時(shí)的最小值(0.4 s)。從圖中可以看出，遺傳算法計(jì)算結(jié)果相對(duì)較好，數(shù)據(jù)傳輸耗時(shí)比較接近于0.4 s的最佳結(jié)果，而且結(jié)果波動(dòng)較小，驗(yàn)證了遺傳算法在瓦片資源選擇上的有效性。

2.3 精英主義優(yōu)化

遺傳算法未采取精英主義時(shí)，在種群迭代過程中種群可能會(huì)發(fā)生如圖5所示的退化現(xiàn)象，如同自然界中某些動(dòng)植物群體的退化一樣，而且種群的進(jìn)化速度比較慢，甚至是沒有進(jìn)化。為了避免出現(xiàn)這種情況，在遺傳算法計(jì)算過程中采取精英主義，將上一代中適應(yīng)度最高的基因個(gè)體直接保留進(jìn)入下一代。

圖4 遺傳選擇算法的計(jì)算結(jié)果

圖5 種群退化現(xiàn)象

對(duì)未采用精英主義的遺傳算法與采用精英主義的遺傳算法分別重復(fù)進(jìn)行20次試驗(yàn)，試驗(yàn)結(jié)果對(duì)比見表4及如圖6所示，可以看出，采用精英主義之后，遺傳算法計(jì)算結(jié)果的質(zhì)量有了明顯的提升，均值降低了17.3%左右，方差也有所降低。

表4 精英主義對(duì)比試驗(yàn)結(jié)果統(tǒng)計(jì)表

圖6 采用與未采用精英主義的遺傳算法計(jì)算結(jié)果對(duì)比圖

3 結(jié) 語(yǔ)

本文研究如何提高對(duì)等網(wǎng)絡(luò)環(huán)境中瓦片影像數(shù)據(jù)的共享效率，在有效利用對(duì)等網(wǎng)優(yōu)勢(shì)的基礎(chǔ)上，提出了一種基于遺傳算法的瓦片資源選擇方法。試驗(yàn)結(jié)果表明，這一方法可以有效地解決瓦片資源選擇這類組合優(yōu)化問題，具有一定的實(shí)際應(yīng)用價(jià)值。

[1] 霍亮, 楊耀東, 劉小勇,等. 瓦片金字塔模型技術(shù)的研究與實(shí)踐[J]. 測(cè)繪科學(xué), 2012, 37(6):146-148.

[2] 賁進(jìn), 童曉沖, 張衡,等. 基于TIFF和XML標(biāo)準(zhǔn)的瓦片金字塔模型[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 2005, 22(3):184-186.

[3] 周強(qiáng), 宋志峰, 劉易鑫,等. 一種適用于多移動(dòng)終端的地圖瓦片格式的研究與應(yīng)用[J]. 測(cè)繪與空間地理信息, 2013(S1):70-76.

[4] 郭明強(qiáng), 黃穎, 謝忠. 分布式環(huán)境下海量瓦片數(shù)據(jù)實(shí)時(shí)組織與調(diào)度策略研究[J]. 測(cè)繪通報(bào), 2013(4):25-28.

[5] 李治慶, 馬照亭, 李成名,等. 3DGIS海量瓦片數(shù)據(jù)管理與調(diào)度[J]. 測(cè)繪科學(xué), 2013, 38(6):109-110.

[6] 商秀玉. WebGIS海量瓦片數(shù)據(jù)管理引擎的設(shè)計(jì)與實(shí)現(xiàn)[D]. 金華：浙江師范大學(xué), 2012.

[7] 劉小生, 吳征, 王永生. 一種海量遙感影像實(shí)時(shí)切割與高效調(diào)度新方法[J]. 測(cè)繪科學(xué)技術(shù)學(xué)報(bào), 2013, 30(1):51-53.

[8] 馬立肖, 王江晴, XIAO Mali,等. 遺傳算法在組合優(yōu)化問題中的應(yīng)用[J]. 計(jì)算機(jī)工程與科學(xué), 2005, 27(7):72-73.

[9] 汪松泉. 遺傳算法在組合優(yōu)化中的應(yīng)用研究[D].合肥：安徽大學(xué), 2010.

[10] 高經(jīng)緯, 張煦, 李峰,等. 求解TSP問題的遺傳算法實(shí)現(xiàn)[J]. 計(jì)算機(jī)時(shí)代, 2004(2):19-21.

[11] NOZARIAN S, DEHGHAN Y, JAHAN M V. Solving TSP on the Basis of Grid and Genetic Algorithm[J]. International Proceedings of Computer Science & Information Tech, 2012，34:61-66.

[12] 于瑩瑩, 陳燕, 李桃迎. 改進(jìn)的遺傳算法求解旅行商問題[J]. 控制與決策, 2014(8):1483-1488.

[13] SUN L. Genetic Algorithm for TSP Problem[C]∥International Industrial Informatics and Computer Engineering Conference.[S.l.]：ACM 2015.

[14] 于海璁, 陸鋒. 一種基于遺傳算法的多模式多標(biāo)準(zhǔn)路徑規(guī)劃方法[J]. 測(cè)繪學(xué)報(bào), 2014，43(1):89-96.

[15] 任海艷, 陳飛翔. 一種基于遺傳算法的曲線化簡(jiǎn)方法[J]. 測(cè)繪通報(bào), 2012(10):32-35.

TileResourceSelectionAlgorithmforRemoteSensingImageBasedonPeer-to-PeerNetwork

FAN Zhaowei1,2,LI Ziyang1,ZHOU Zengguang1,LI Chuanrong1

(1. Key Laboratory of Quantitative Remote Sensing Information Technology, Academy of Opto-Electronics, Chinese Academy of Sciences, Beijing 100094,China; 2. University of Chinese Academy of Sciences,Beijing 100049,China)

P237

A

0494-0911(2017)09-0046-05

范兆煒，李子揚(yáng)，周增光,等.對(duì)等網(wǎng)絡(luò)遙感影像瓦片資源遺傳選擇算法[J].測(cè)繪通報(bào)，2017(9)：46-50.

10.13474/j.cnki.11-2246.2017.0285.

2017-01-16;

2017-03-27

國(guó)家863計(jì)劃(2013AA122904)

范兆煒(1991—)，男，碩士生，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用技術(shù)。E-mail:18401698369@163.com

李傳榮。E-mail:crli@aoe.ac.cn