對等網絡遙感影像瓦片資源遺傳選擇算法

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

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

對等網絡遙感影像瓦片資源遺傳選擇算法

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

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

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

遙感影像；瓦片；對等網；數據傳輸；組合優化；遺傳算法

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

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

隨著網絡技術的快速發展，對等網絡傳輸技術利用大量的客戶端資源來分擔服務器的壓力，不但有效地降低了系統對服務器的依賴程度，提高了系統的穩定性，還極大地提高了數據分發傳輸的效率。對等網絡傳輸技術為海量遙感影像數據的高效共享開辟了一條新的途徑。

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

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

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

遺傳算法的運算對象是基因型——表示個體的符號串，進行遺傳算法擇優的基礎是進行基因設計，即實現表現型到基因型的映射即編解碼工作。遺傳算法的基本運算過程如下：

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

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

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

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

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

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

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

1 瓦片資源遺傳選擇算法

1.1 基因設計

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

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

圖1 落在需求范圍內的瓦片數據

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

1.2 適應度函數設計

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

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

根據求解目標，適應度函數初步設計為

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

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

表2 某基因對應的總傳輸耗時計算方法

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

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

此外，當種群中基因個體對應的數據傳輸時間全部相同時，max[t1,t2,t3,…,tn]-tx的值會變為零，因此適應度也會變為零。由于適應度為零的基因個體不會被選中去進行交配繁殖，因此為了保證種群能夠繼續進化，當種群中基因個體對應的數據傳輸時間全部相同時，所有的基因個體的適應度設為最大數據傳輸時間。

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

最終，適應度函數設計為：

當種群中各基因個體對應的數據傳輸時間不盡相同時

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

當種群中各基因個體對應的數據傳輸時間全部相同時

F(x)=covRatio·t

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

1.3 遺傳選擇算法計算過程

瓦片數據選擇的遺傳算法操作過程為：

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

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

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

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

圖2 輪盤賭

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

圖3 交叉運算

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

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

(7) 終止：新群體繼續產生新群體：對新群體繼續執行群體進化操作。當群體進化次數達到最大進化次數T，則最終群體中所得到的具有最大適應度個體作為最優解輸出，終止計算。

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

2 試驗與結果分析

2.1 測試數據

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

表3 瓦片分布

2.2 遺傳選擇算法計算結果

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

2.3 精英主義優化

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

圖4 遺傳選擇算法的計算結果

圖5 種群退化現象

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

表4 精英主義對比試驗結果統計表

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

3 結 語

本文研究如何提高對等網絡環境中瓦片影像數據的共享效率，在有效利用對等網優勢的基礎上，提出了一種基于遺傳算法的瓦片資源選擇方法。試驗結果表明，這一方法可以有效地解決瓦片資源選擇這類組合優化問題，具有一定的實際應用價值。

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

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

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

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

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

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

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

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

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

[10] 高經緯, 張煦, 李峰,等. 求解TSP問題的遺傳算法實現[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] 于海璁, 陸鋒. 一種基于遺傳算法的多模式多標準路徑規劃方法[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

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

10.13474/j.cnki.11-2246.2017.0285.

2017-01-16;

2017-03-27

國家863計劃(2013AA122904)

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

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