范兆煒，李子揚，周增光，李傳榮

(1. 中國科學院光電研究院中國科學院定量遙感信息技術(shù)重點實驗室，北京 100094； 2. 中國科學院大學，北京 100049)

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

范兆煒1,2，李子揚1，周增光1，李傳榮1

(1. 中國科學院光電研究院中國科學院定量遙感信息技術(shù)重點實驗室，北京 100094； 2. 中國科學院大學，北京 100049)

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

遙感影像；瓦片；對等網(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ù)，是目前對海量遙感影像數(shù)據(jù)進行組織與管理的主要方式[4-7]。

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

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

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

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

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

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

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

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

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

(5) 變異運算：將子代個體的某些基因值作變動。

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

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

1 瓦片資源遺傳選擇算法

1.1 基因設(shè)計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

F(x)=covRatio·t

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

1.3 遺傳選擇算法計算過程

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

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

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

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

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

圖2 輪盤賭

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

圖3 交叉運算

(5) 變異運算：對新個體，隨機選取變異點，變異點值為0則變1，為1則變0，變異概率p設(shè)為0.2%。例如，新基因個體1100001，變異點位置5，變異后基因為1100101。

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

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

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

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

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

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

表3 瓦片分布

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

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

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

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

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

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

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

表4 精英主義對比試驗結(jié)果統(tǒng)計表

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

3 結(jié) 語

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

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

[2] 賁進, 童曉沖, 張衡,等. 基于TIFF和XML標準的瓦片金字塔模型[J]. 測繪科學技術(shù)學報, 2005, 22(3):184-186.

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

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

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

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

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

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

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

[10] 高經(jīng)緯, 張煦, 李峰,等. 求解TSP問題的遺傳算法實現(xiàn)[J]. 計算機時代, 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]. 控制與決策, 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] 于海璁, 陸鋒. 一種基于遺傳算法的多模式多標準路徑規(guī)劃方法[J]. 測繪學報, 2014，43(1):89-96.

[15] 任海艷, 陳飛翔. 一種基于遺傳算法的曲線化簡方法[J]. 測繪通報, 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

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

10.13474/j.cnki.11-2246.2017.0285.

2017-01-16;

2017-03-27

國家863計劃(2013AA122904)

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

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