李洪亮 王 倩 李運(yùn)華

1.北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院，北京 100191 2. 北京空間飛行器總體設(shè)計(jì)部，北京 100094

?

遙感衛(wèi)星覆蓋任意區(qū)域快速仿真算法研究

李洪亮1王 倩2李運(yùn)華1

1.北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院，北京 100191 2. 北京空間飛行器總體設(shè)計(jì)部，北京 100094

在軌衛(wèi)星對(duì)地觀測(cè)體系效能仿真涉及的衛(wèi)星資源數(shù)量眾多，任務(wù)范圍大，以致仿真分析時(shí)的計(jì)算規(guī)模較大。在研究多星對(duì)指定區(qū)域的覆蓋效能時(shí)，需要從體系仿真的角度構(gòu)建合適的覆蓋模型以及優(yōu)化的仿真算法。首先分析了光學(xué)遙感衛(wèi)星的幾何定位原理，建立了遙感衛(wèi)星的覆蓋視場(chǎng)，提出簡(jiǎn)單有效的判定方法實(shí)現(xiàn)任意不規(guī)則區(qū)域網(wǎng)格點(diǎn)的劃分，最后利用Multimap優(yōu)化算法和K近鄰搜索算法實(shí)現(xiàn)區(qū)域網(wǎng)格點(diǎn)的快速搜索統(tǒng)計(jì)。通過(guò)與傳統(tǒng)搜索方法的對(duì)比實(shí)驗(yàn)表明這兩種優(yōu)化算法可以極大地提高網(wǎng)格點(diǎn)統(tǒng)計(jì)效率。 關(guān)鍵詞 在軌衛(wèi)星；覆蓋效能；覆蓋視場(chǎng)；Multimap優(yōu)化算法；K近鄰；網(wǎng)格點(diǎn)

衛(wèi)星對(duì)區(qū)域的覆蓋分析，一般利用網(wǎng)格點(diǎn)分析法，首先將地球表面某一區(qū)域進(jìn)行網(wǎng)格點(diǎn)劃分，仿真特定時(shí)間，統(tǒng)計(jì)被星載傳感器覆蓋到的網(wǎng)格點(diǎn)作為覆蓋特性評(píng)估的依據(jù)。網(wǎng)格點(diǎn)分析法具有較高的仿真精度，而且對(duì)于任意軌道和任意形狀的覆蓋視場(chǎng)都能適用，已成為覆蓋求解的最主要方法。

國(guó)內(nèi)外在衛(wèi)星對(duì)地覆蓋以及網(wǎng)格點(diǎn)分析法方面做了大量研究工作。1970年，J.C.Walkery研究了圓軌道衛(wèi)星星座構(gòu)成的全球覆蓋模型，在該領(lǐng)域做出了開(kāi)創(chuàng)性的工作[1]。Morrison在1973年研究多重覆蓋時(shí)首先提出了網(wǎng)格方法[2]。1989年，J.Middour給出了一種基于多邊形視場(chǎng)技術(shù)的衛(wèi)星對(duì)地覆蓋計(jì)算方法[3]。Sandau R等對(duì)小衛(wèi)星群全球覆蓋問(wèn)題做了大量研究工作，探究了覆蓋問(wèn)題新的領(lǐng)域[4]。

在衛(wèi)星覆蓋建模和分析方面，曹平等給出了遙感衛(wèi)星成像模型的精確建模方式，并對(duì)誤差作了對(duì)比分析[5]。羅盛茂、范麗等研究了基于覆蓋分析的軌道調(diào)整和星座設(shè)計(jì)[6-7]。簡(jiǎn)平、鄧勇、王博等分別對(duì)低軌凝視傳感器和天基光學(xué)跟蹤傳感器，利用網(wǎng)格點(diǎn)分析法分析了星座覆蓋性能[8-10]。

在衛(wèi)星覆蓋仿真優(yōu)化方面，賀勇軍等研究了非規(guī)則覆蓋區(qū)域網(wǎng)格點(diǎn)求解的幾個(gè)通用算法[11]。宋志明等采用了不同于網(wǎng)格點(diǎn)分析法的經(jīng)度條帶法來(lái)提高星座覆蓋仿真效率[12]。秦睿杰等則提出了基于抽樣的網(wǎng)格點(diǎn)統(tǒng)計(jì)算法[13]。沈夏炯等對(duì)任意區(qū)域優(yōu)化了衛(wèi)星過(guò)境覆蓋分析的計(jì)算方法[14]。

當(dāng)對(duì)指定區(qū)域利用網(wǎng)格點(diǎn)分析法進(jìn)行覆蓋效能指標(biāo)(如重訪時(shí)間、間隙周期，覆蓋百分比等)分析時(shí)，隨著網(wǎng)格點(diǎn)數(shù)目增加，內(nèi)存和時(shí)間消耗會(huì)急劇上升。仿真時(shí)發(fā)現(xiàn)耗時(shí)主要體現(xiàn)在衛(wèi)星視場(chǎng)與區(qū)域網(wǎng)格點(diǎn)的可見(jiàn)性判斷上，因?yàn)樾l(wèi)星載荷要遍歷大量網(wǎng)格點(diǎn)，這造成時(shí)間和空間復(fù)雜度很高。這一問(wèn)題需要從載荷建模、區(qū)域劃分、網(wǎng)格點(diǎn)統(tǒng)計(jì)和可見(jiàn)性解算等方面綜合考慮。

本文給出覆蓋視場(chǎng)建模方式，優(yōu)化了衛(wèi)星視場(chǎng)與任意區(qū)域網(wǎng)格點(diǎn)可見(jiàn)性判斷方法，利用Multimap關(guān)聯(lián)容器和改進(jìn)的K近鄰搜索算法，實(shí)現(xiàn)遙感衛(wèi)星覆蓋視場(chǎng)內(nèi)網(wǎng)格點(diǎn)的快速搜索，仿真實(shí)驗(yàn)給出了3種搜索算法的計(jì)算耗時(shí)對(duì)比。最后將整體仿真模型和STK軟件的覆蓋結(jié)果進(jìn)行了比較，驗(yàn)證了所建立仿真模型的準(zhǔn)確性。

1 遙感衛(wèi)星覆蓋視場(chǎng)建模

1.1 遙感幾何定位

衛(wèi)星在軌道上任意一點(diǎn)對(duì)地形成的覆蓋視場(chǎng)與衛(wèi)星傳感器的視場(chǎng)角、衛(wèi)星姿態(tài)和位置有關(guān)，覆蓋視場(chǎng)可根據(jù)遙感幾何定位建模。圖1是遙感衛(wèi)星幾何定位的示意圖，P是遙感點(diǎn)(被觀察點(diǎn))，S為遙感衛(wèi)星，B為星下點(diǎn)。

圖1 遙感衛(wèi)星幾何定位原理圖

首先由地心慣性系下點(diǎn)S和P，地心O建立矢量三角形

r+ρ=OP

(1)

式中，ρ=ρu，其中，u為像元視線單位矢量，r=OS。

設(shè)慣性系下P點(diǎn)的坐標(biāo)(Px,Py,Pz), 其符合地球橢圓公式：

(2)

式中,ae和be分別為地球半長(zhǎng)軸和半短軸。

將式(2)展開(kāi)得

(3)

(4)

求式(4)的判別式Δ=B2-4AC，根據(jù)Δ判斷遙感衛(wèi)星覆蓋在地球表面的情況。

若Δ<0，則遙感點(diǎn)P不在地球上；Δ=0，視線矢量與地球表面相切；Δ>0，ρ的2個(gè)解為SP和SP′，選擇離S較近的點(diǎn)即可。

利用式(4)和Δ的判別結(jié)果求得ρ，再由衛(wèi)星在慣性坐標(biāo)系下的位置r計(jì)算得到遙感點(diǎn)P在慣性系下的坐標(biāo)(Px,Py,Pz)。

(5)

由地心固連坐標(biāo)系與慣性系的轉(zhuǎn)換矩陣得到地固坐標(biāo)系的坐標(biāo)位置：

(6)

其中，G(t)為格林威治恒星時(shí)角。

設(shè)求得的地固坐標(biāo)系坐標(biāo)為(X,Y,Z)，大地經(jīng)緯高的計(jì)算一般采用迭代法。

(7)

其中，e為地球偏心率。

(8)

一般保證H高度在0.001m精度和B緯度在0.0001″精度的情況下迭代4次。

1.2 覆蓋視場(chǎng)建模

首先根據(jù)衛(wèi)星載荷橫向和縱向視場(chǎng)角確定儀器坐標(biāo)系下SP1，SP2，SP3，SP4方向的4個(gè)單位視線矢量，即up1,up2,up3,up4。再由儀器在本體上的安裝矩陣M得到衛(wèi)星本體系上的矢量M-1[up1,up2,up3,up4]，然后由姿態(tài)矩陣A得到軌道系矢量A-1M-1[up1,up2,up3,up4]。根據(jù)軌道坐標(biāo)與慣性坐標(biāo)轉(zhuǎn)換矩陣Roi，確定慣性系下視線單位矢量：

(9)

最后根據(jù)前面討論的幾何定位原理，確定4個(gè)視線矢量在大地坐標(biāo)系下的投影點(diǎn)P1，P2，P3，P4，從而確定地球表面產(chǎn)生的四邊形各點(diǎn)經(jīng)緯度，即覆蓋視場(chǎng)P1P2P3P4。

圖2 遙感衛(wèi)星覆蓋視場(chǎng)

這種方式建立的載荷模型在實(shí)際仿真中可用于掃描和框幅成像這2種載荷類型。

2 任意不規(guī)則區(qū)域網(wǎng)格點(diǎn)劃分

網(wǎng)格點(diǎn)分析法即將地球表面或指定區(qū)域進(jìn)行網(wǎng)格劃分，網(wǎng)上的每個(gè)結(jié)點(diǎn)被稱為網(wǎng)格點(diǎn)，對(duì)應(yīng)于地面上相應(yīng)的經(jīng)緯度點(diǎn)，網(wǎng)格點(diǎn)的劃分通?？刹捎玫冉?jīng)緯度法和等面積法[11]。受限于地球的形狀特征，由等經(jīng)緯度劃分出的網(wǎng)格點(diǎn)，不同緯度上的網(wǎng)格點(diǎn)密集程度是不一樣的，每個(gè)網(wǎng)格點(diǎn)所代表的面積大小也是不一樣的。

2.1 經(jīng)緯度及網(wǎng)格點(diǎn)面積

設(shè)有不同經(jīng)緯度上的2點(diǎn):(λ1，φ1)，(λ2，φ2)，經(jīng)緯度距離公式為：

d=

(10)

設(shè)網(wǎng)格點(diǎn)經(jīng)緯度劃分步長(zhǎng)為Δλ和Δφ。由于Δλ和Δφ較小，可將劃分的網(wǎng)格區(qū)域近似看成矩形區(qū)域。

對(duì)應(yīng)的網(wǎng)格點(diǎn)面積：

S≈l1l2=111.1992ΔλΔφcosφ1

(11)

由式(11)可知，若Δλ，Δφ一定，網(wǎng)格點(diǎn)面積近似正比于該點(diǎn)緯度余弦值，所以等面積法可以依據(jù)緯度余弦值進(jìn)行近似等密度網(wǎng)格點(diǎn)劃分。

2.2 兩種劃分算法

首先確定指定區(qū)域的邊界，邊界可以通過(guò)讀邊界文件獲得，也可以粗略地在程序中指定，邊界點(diǎn)越密集則區(qū)域邊界越光滑。然后求取邊界最大最小經(jīng)緯度，再生成網(wǎng)格點(diǎn)，最后由水平/垂直交叉點(diǎn)數(shù)判別法篩選出在區(qū)域邊界內(nèi)的網(wǎng)格點(diǎn)。

圖3 水平/垂直交叉點(diǎn)數(shù)判別法

算法原理：由點(diǎn)Q作水平向右的射線，求出與多邊形交點(diǎn)總個(gè)數(shù)。如果Q在多邊形內(nèi)部，交點(diǎn)必為奇數(shù)；如果Q在多邊形外部，則交點(diǎn)個(gè)數(shù)必為偶數(shù)(包括0)。特殊情況，若射線恰好穿過(guò)多邊形頂點(diǎn)時(shí)，則計(jì)數(shù)方式為：當(dāng)頂點(diǎn)兩邊位于射線同側(cè)，交點(diǎn)數(shù)加2，否則加1。該方法對(duì)包括凹凸多邊形的任意多邊形都適用。

圖4 網(wǎng)格點(diǎn)劃分原理圖

等經(jīng)緯度網(wǎng)格點(diǎn)生成算法：

1) 由區(qū)域邊界得到最大及最小經(jīng)緯度λmax,λmin,φmax,φmin；

2) 指定經(jīng)度細(xì)分步長(zhǎng)Δλ，緯度細(xì)分步長(zhǎng)Δφ，再依次生成網(wǎng)格點(diǎn){λmin,φmin}，{λmin+Δλ，φmin+Δφ}，{λmin+2Δλ，φmin+2Δφ}，…，Until {λn，φn} <={λmax，φmax}；

3) 水平/垂直交叉點(diǎn)數(shù)判別法篩選出區(qū)域邊界內(nèi)的所有網(wǎng)格點(diǎn)，得到區(qū)域邊界內(nèi)網(wǎng)格點(diǎn)集合{Pot1，Pot2，Pot3，…，Potn}。

等面積法網(wǎng)格點(diǎn)生成算法：

1) 同等經(jīng)緯度網(wǎng)格點(diǎn)生成算法所述1)；

2) 首先確定低緯度φmin的劃分網(wǎng)格點(diǎn)數(shù)m，確定緯度之間的步長(zhǎng)Δφ，由低緯度φmin到高緯度φmax劃分的網(wǎng)格點(diǎn)數(shù)依次為

3) 篩選出邊界范圍內(nèi)的網(wǎng)格點(diǎn)，得到網(wǎng)格點(diǎn)集合{Pot1，Pot2，Pot3，…，Potn}。

3 覆蓋視場(chǎng)快速解算算法

當(dāng)衛(wèi)星對(duì)指定區(qū)域形成覆蓋視場(chǎng)時(shí)，每步仿真時(shí)只有在覆蓋視場(chǎng)內(nèi)的網(wǎng)格點(diǎn)才作為覆蓋到的目標(biāo)點(diǎn)，即要做目標(biāo)點(diǎn)與衛(wèi)星覆蓋視場(chǎng)的可見(jiàn)性關(guān)系判斷。這種隸屬關(guān)系判斷即是判斷一個(gè)點(diǎn)是否被包含在一個(gè)多邊形區(qū)域內(nèi)。可以用網(wǎng)格點(diǎn)劃分時(shí)采用的水平/垂直交叉點(diǎn)數(shù)判別法。以下算法以等經(jīng)緯度劃分原理圖來(lái)說(shuō)明，對(duì)于等面劃分的網(wǎng)格點(diǎn)也是適用的。

3.1 線性掃描法

每一步仿真中，將所有網(wǎng)格點(diǎn)都代入覆蓋視場(chǎng)中，作隸屬關(guān)系判斷，然后統(tǒng)計(jì)出在四邊形視場(chǎng)內(nèi)的網(wǎng)格點(diǎn)。這種方法對(duì)網(wǎng)格點(diǎn)的存儲(chǔ)要求簡(jiǎn)單，但每個(gè)網(wǎng)格點(diǎn)都要做水平/垂直交叉點(diǎn)數(shù)判別法判斷，運(yùn)算量較大，效率較低。

3.2 Multimap優(yōu)化算法

Multimap 使用紅黑二叉樹(shù)記錄數(shù)據(jù)元素，按元素鍵值的大小自動(dòng)排序，可進(jìn)行最優(yōu)化的快速插入、刪除和檢索等操作。在multimap 中，元素的鍵值key與元素value的映照關(guān)系是多對(duì)多的，即允許存儲(chǔ)具有重復(fù)鍵值的元素，因此，multimap 稱為多重映照容器。

利用multimap< Pot_key，Pot_value> 作為網(wǎng)格點(diǎn)存儲(chǔ)的結(jié)構(gòu)，其中Pot_key可以是結(jié)構(gòu)體只存儲(chǔ)經(jīng)緯度值，而Pot_value 可以是類或結(jié)構(gòu)體存儲(chǔ)全部網(wǎng)格點(diǎn)信息。Multimap中Pot_key作為key值進(jìn)行搜索，而且經(jīng)緯度都是double型，所以在使用時(shí)必須要對(duì)multimap的“<”重載，重載時(shí)按先比較緯度大小，再比較經(jīng)度大小的方式。這樣利用multimap< Pot_key，Pot_value>存儲(chǔ)網(wǎng)格點(diǎn)集合{Pot1，Pot2，Pot3，…，Potn}，將得到緯度和經(jīng)度升序的有序數(shù)據(jù)集。

圖5 Multimap優(yōu)化算法原理圖

算法思想：

3)Q中的緯度值φ+Δφ，然后multimap::find(Q.φ+Δφ)找到網(wǎng)格點(diǎn)集合中的Q″，獲得迭代器，向右搜索，與2)過(guò)程相同；

4) 重復(fù)循環(huán)過(guò)程3)，依次作行和列搜索，一直搜索到邊界極值點(diǎn)Q′″，停止搜索；

5) 其中2)～4)的每一步找到的網(wǎng)格點(diǎn)都由水平/垂直交叉點(diǎn)數(shù)判別法判別是否在覆蓋視場(chǎng)內(nèi)；

6) 從{Pot1，Pot2，Pot3，…，Potn}網(wǎng)格點(diǎn)集合中利用multimap::erase方式刪除Q點(diǎn)。

3.3 改進(jìn)的K近鄰搜索算法

K近鄰算法在空間海量數(shù)據(jù)搜索中應(yīng)用廣泛[15-18]。該算法首先要構(gòu)造k-d樹(shù)存儲(chǔ)網(wǎng)格點(diǎn)數(shù)據(jù)，選擇網(wǎng)格點(diǎn)集合經(jīng)緯度上的中位數(shù)為切分點(diǎn)。依次選取經(jīng)度和緯度將每一層空間切分為二，循環(huán)往復(fù)。最終每個(gè)節(jié)點(diǎn)對(duì)應(yīng)于劃分中的一個(gè)超矩形區(qū)域。K近鄰算法要使用搜索距離，可采用式(10)經(jīng)緯度的距離公式改進(jìn)方式，

K近鄰搜索第1步通過(guò)比較待查詢點(diǎn)和分裂維的大小開(kāi)始搜索(小于等于就進(jìn)入左子空間，否則就進(jìn)入右子空間)，一直找到與待查詢節(jié)點(diǎn)在同一超矩形區(qū)域的葉子節(jié)點(diǎn)，作為最近鄰相似點(diǎn)。第2步沿搜索路徑反向搜索，并判斷搜索路徑上的節(jié)點(diǎn)的其他子節(jié)點(diǎn)空間中是否有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)，若存在，則進(jìn)入其他子節(jié)點(diǎn)空間中查詢，重復(fù)該過(guò)程至搜索路徑為空。

設(shè)計(jì)的覆蓋視場(chǎng)搜索算法可以利用文獻(xiàn)[16]提出的一種空間球搜索思想，在一個(gè)數(shù)據(jù)中心的超球內(nèi)進(jìn)行查詢，超球半徑由0開(kāi)始逐漸增大，并且根據(jù)查詢結(jié)果更新，直到超球內(nèi)包含K個(gè)近鄰點(diǎn)而停止。由于網(wǎng)格點(diǎn)集合設(shè)計(jì)的是二維區(qū)域，算法的終止條件是搜索到半徑范圍內(nèi)所有網(wǎng)格點(diǎn)。

在搜索過(guò)程中存儲(chǔ)搜索到的網(wǎng)格點(diǎn)數(shù)據(jù)，假設(shè)有k1

圖6 K近鄰搜索算法原理圖

算法思想：

1) 利用k-d樹(shù)存儲(chǔ)網(wǎng)格點(diǎn)集合{Pot1，Pot2，Pot3，…，Potn}；

2) 由覆蓋視場(chǎng)的4個(gè)投影點(diǎn)計(jì)算得到視場(chǎng)中心點(diǎn)Q，并以Q點(diǎn)為中心，四邊形對(duì)角線的一半為搜索半徑D，利用K近鄰進(jìn)行搜索，在搜索過(guò)程中構(gòu)建大頂堆；

3) 當(dāng)搜索的近鄰點(diǎn)到中心Q的距離d≤D時(shí)，按K近鄰的機(jī)制回溯查找，且更新大頂堆；當(dāng)近鄰點(diǎn)到中心點(diǎn)Q的距離d>D時(shí)，搜索結(jié)束，保存搜索到的所有網(wǎng)格點(diǎn)；

4) 由圖6可知：搜索過(guò)程①→②→③→④→ …，直到搜索到半徑范圍內(nèi)的所有點(diǎn)；

5) 由水平/垂直交叉點(diǎn)數(shù)判別法篩選出在覆蓋視場(chǎng)內(nèi)的可見(jiàn)網(wǎng)格點(diǎn)。

4 仿真實(shí)驗(yàn)

開(kāi)發(fā)環(huán)境如下：處理器：Intel(R) Xeon(R) CPU E5504 @ 2.00GHz 內(nèi)存：3.23GB 操作系統(tǒng)：Windows XP 編程語(yǔ)言：C++。

這里統(tǒng)計(jì)某一仿真步長(zhǎng)內(nèi)，在覆蓋視場(chǎng)范圍內(nèi)400個(gè)網(wǎng)格點(diǎn)的搜索時(shí)間。

通過(guò)大量實(shí)驗(yàn)發(fā)現(xiàn)效率結(jié)果有相似的規(guī)律，以Multimap優(yōu)化算法和K近鄰搜索算法相對(duì)線性掃描的效率優(yōu)化倍數(shù)為縱坐標(biāo)，網(wǎng)格點(diǎn)數(shù)為橫坐標(biāo)，作圖7和8。

表1 算法運(yùn)行效率表(t/s)

圖7 Multimap優(yōu)化算法效率圖

圖8 K近鄰搜索效率圖

由實(shí)驗(yàn)結(jié)果可知，線性掃描運(yùn)行時(shí)間隨網(wǎng)格點(diǎn)數(shù)的增長(zhǎng)而成線性增長(zhǎng)，Multimap優(yōu)化效率比線性掃描高，當(dāng)網(wǎng)格點(diǎn)數(shù)比較大時(shí)，Multimap優(yōu)化效率的倍數(shù)趨于穩(wěn)定，呈緩慢增長(zhǎng)。而K近鄰搜索耗時(shí)隨網(wǎng)格點(diǎn)數(shù)增多并沒(méi)有顯著增加。

文獻(xiàn)[14]設(shè)計(jì)的任意區(qū)域網(wǎng)格點(diǎn)覆蓋算法的算法復(fù)雜度為O(n)。而本文采用的K近鄰搜索算法有效地解決了隨網(wǎng)格點(diǎn)增加造成仿真時(shí)內(nèi)存和時(shí)間消耗增幅過(guò)快的問(wèn)題，算法復(fù)雜度為O(logn)，而且避免了文獻(xiàn)[13]通過(guò)抽樣方式造成的仿真誤差。

網(wǎng)格點(diǎn)分析法在每個(gè)仿真步長(zhǎng)內(nèi)需要統(tǒng)計(jì)所有網(wǎng)格點(diǎn)的可見(jiàn)性，基于以上覆蓋視場(chǎng)的求解算法可以很快找到在覆蓋視場(chǎng)內(nèi)的網(wǎng)格點(diǎn)，將這些網(wǎng)格點(diǎn)設(shè)置為可見(jiàn)，其余則默認(rèn)設(shè)置為不可見(jiàn)。仿真一段時(shí)間可以得到所有網(wǎng)格點(diǎn)的可見(jiàn)時(shí)刻集合。對(duì)網(wǎng)格點(diǎn)可見(jiàn)時(shí)刻集合進(jìn)行合并和計(jì)算統(tǒng)計(jì)即可得到覆蓋特性指標(biāo)結(jié)果。

圖9是某星座下的空間覆蓋率仿真結(jié)果，軌道采用J2攝動(dòng)模型，網(wǎng)格點(diǎn)分析法采用等面積劃分和K近鄰搜索，將整體仿真模型與STK仿真出的空間覆蓋率進(jìn)行對(duì)比，實(shí)驗(yàn)誤差在1.5%范圍內(nèi)，驗(yàn)證了模型的準(zhǔn)確性，而多星體系仿真效率有了很大提升。

圖9 某星座下的空間覆蓋率

5 結(jié)論

實(shí)現(xiàn)了對(duì)遙感衛(wèi)星覆蓋視場(chǎng)建模和任意區(qū)域網(wǎng)格點(diǎn)的劃分。通過(guò)對(duì)3種覆蓋視場(chǎng)搜索算法的比較可知K近鄰效率較高，并且對(duì)其他網(wǎng)格點(diǎn)劃分方式，以及非四邊形覆蓋視場(chǎng)也可以適用。此外，在確保仿真精度的前提下，為了仿真運(yùn)行的效率可以將一些模型進(jìn)行簡(jiǎn)化，而將GPU引入到網(wǎng)格點(diǎn)算法仿真中也是值得探究的方向。

[1] Walker J G.Circular Orbit Patterns Providing Continuous Whole Earth Coverage[R]. Royal Aircraft Establishment Farnborough (United Kingdom), 1970.

[2] Morrison J J.A System of Sixteen Synchronous Satellites for Worldwide Navigation and Surveillance[M]. Defense Technical Information Center，1973．

[3] Middour J, Washington D C. An Efficient Technique for Computation of Satellite Earth Coverage[C].AIAA.89-0452.27th Aerospace Sciences Metting.January 9-12,1989/Reno, Nevada.

[4] Sandau R, Brieβ K, D’Errico M. Small Satellites for Global Coverage: Potential and Limits[J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2010, 65(6): 492-504.

[5] 曹平, 章文毅, 馬廣彬. 遙感衛(wèi)星成像模型研究及仿真[J]. 遙感信息, 2014, 29(3) : 62-66. (Cao Ping, Zhang Wenyi, Ma Guangbin. Imaging Model of Remote Sensing Satellite and Its Simulation[J]. Remote Sensing Information, 2014, 29(3) : 62-66 .)

[6] 羅盛茂，李紅.低軌衛(wèi)星編隊(duì)飛行的地面覆蓋及軌道調(diào)整[J]. 航天控制， 2006， 23(6): 35-40.(Luo Shengmao, Li Hong. Surface Coverage of Satellites Formation Flying in Low[J]. Aerospace Control, 2006, 23(6): 35-40.)

[7] 范麗, 張育林. 區(qū)域覆蓋混合星座設(shè)計(jì)[J]. 航天控制, 2007, 25(6): 52-55. (Fan Li, Zhang Yuli. Regional Coverage Hybrid Constellation Design[J]. Aerospace Control, 2007, 25(6): 52-55.)

[8] 簡(jiǎn)平, 鄒鵬, 熊偉, 陳治科. 改進(jìn)的低軌凝視傳感器覆蓋性能網(wǎng)格分析方法[J]. 空軍工程大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 13(3):35-39. (Jian Ping, Zou Peng, Xiong Wei, Chen Zhike. Improved Grid Method for Analysis on Coverage Performance of Staring Sensors Based LEO[J].Journal of Air Force Engineering University(Natural Science Edition), 2012, 13(3):35-39.)

[9] 鄧勇, 王春明, 張中兆. 紅外低軌星座凝視傳感器的空間覆蓋性能分析[J]. 宇航學(xué)報(bào),2011, 32(1):123-128. (Deng Yong, Wang Chunming, Zhang Zhongzhao. Analysis on Coverage Performance of Staring Sensors Infrared LEO Constellation[J]. Journal of Astronautics, 2011, 32(1):123-128.)

[10] 王博,安瑋,周一宇. 跟蹤傳感器空域覆蓋性能分析[J]. 航天控制,2009, 27(6):90-95.( Wang Bo,An Wei,Zhou Yiyu. Analysis on Airspace Coverage Performance of Tracking Sensors[J]. Aerospace Control, 2009, 27(6):90-95.)

[11] 賀勇軍, 戴金海. 多衛(wèi)星非規(guī)則覆蓋區(qū)域的通用求解算法[J]. 計(jì)算機(jī)仿真, 2006, 22(12): 24-27. (He Yongjun, Dai Jinhai. General Algorithms for Searching the Irregular Earth Coverage Regions of Multi-Satellite Systems [J]. Computer Simulation, 2005, 22(12): 24-27.)

[12] 宋志明, 戴光明, 王茂才, 彭雷. 衛(wèi)星星座區(qū)域覆蓋問(wèn)題的快速仿真算法[J]. 航天控制, 2014,32(5):65-70,76. (Song Zhiming, Dai Guangming, Wang Maocai, Peng Lei. The Fast Simulation Algorithm for Solvinge Area Coverage Problem of Satellite Constellation[J]. Aerospace Control, 2014,32(5):65-70，76.)

[13] 秦睿杰, 戴光明, 王茂才, 等. 一種計(jì)算星座區(qū)域覆蓋率的高效抽樣網(wǎng)格點(diǎn)法[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(4):1065-1068. (Qin Ruijie, Dai Guangming, Wang Maocai, et al. Efficient Sampling Grid-point Approach for Calculating Regional Coverage of Satellite Constellation[J]. Application Research of Computers, 2015, 32(4): 1065-1068.)

[14] 沈夏炯, 吳曉洋, 王更科, 韓道軍. 面向任意幾何區(qū)域的遙感衛(wèi)星對(duì)地覆蓋法[J]. 計(jì)算機(jī)應(yīng)用研究,2016,33(7):1-6.(Shen Xiajiong, Wu Xiaoyang, Wang Genke, Han Daojun. Remote Sensing Satellite Covering Method Over Ground Facing to Any Geometric Area[J]. Application Research of Computers, 2016, 33(7)：1-6.)

[15] Piegl L A, Tiller W. Algorithm for Finding All K Nearest Neighbors[J]. Computer-aided Design, 2002, 34 (2): 167-172.

[16] 衛(wèi)煒, 張麗艷, 周來(lái)水. 一種快速搜索海量數(shù)據(jù)集K-近鄰空間球算法[J]. 航空學(xué)報(bào), 2006, 27(5): 944-948. (Wei Wei, Zhang Liyan, Zhou Laishui. A Spatial Sphere Algorithm for Searching K-Nearest Neighbors of Massive Scattered Points[J]. Acta Aeronautica et Astronautica Sinica, 2006, 27(5): 944-948.)

[17] Hwang Y, Han B, Ahn H K. A Fast Nearest Neighbor Search Algorithm by Nonlinear Embedding[C]//Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on. IEEE, 2012: 3053-3060.

[18] Garcia V, Debreuve E, Barlaud M. Fast K Nearest Neighbor Search Using GPU[C]//Computer Vision and Pattern Recognition Workshops, 2008. CVPRW′08. IEEE Computer Society Conference on. IEEE, 2008: 1-6. 963.

Research on Fast Simulation Algorithm of the Arbitrary Region Covered by Remote Sensing Satellite

Li Hongliang1, Wang Qian2, Li Yunhua1

1. School of Automation Science and Electrical Engineering, Beihang University, Beijing 100191, China 2. Beijing Institute of Spacecraft System Engineering, Beijing 100094, China

Alotofsatelliteresourcesandalargenumberoftasksareinvolvedinthesystemeffectivenesssimulaitonofsatellitesinorbt,thus,alotoftimeisspendinthesimulationcomputation.Intheresearchofmulti-satellitecoverageperformanceofthedesignatedregions,appropriatecoveragemodelsandoptimizationsimulationalgorithmsarerequiredfromtheperspectiveofsystemsimulation.Thethegeometricpositioningprincipleofopticalremotesensingsatelliteisfirstlydiscussedandsatellitecoveragefieldofviewmodelisbuilt.Then,asimpleandeffectivemethodisproposedtocreategridpointsinarbitrarilyirregularregions.Finally,themulti-mapoptimizationalgorithmandKnearestneighboralgorithmisusedtoachievethefastsearchofirregularregionalgridpoints.Bycomparingwiththetraditionalsearchmethod,thetwooptimizationalgorithmscangreatlyimprovetheefficiencyofgridpointstatistics.

Satellitesinorbit;Coverageperformance;Coveragefieldofview;Multi-mapoptimizationalgorithm; Knearestneighbor;Gridpoint

2016-04-11

李洪亮(1991-)，男，安徽人，碩士研究生，主要研究方向?yàn)楹教炱飨到y(tǒng)仿真；王 倩(1985-)，女，遼寧人，高級(jí)工程師，主要研究方向?yàn)楹教炱飨到y(tǒng)仿真；李運(yùn)華(1963-)，男，河北人，博士，教授，主要研究方向?yàn)榉蔷€性動(dòng)力學(xué)與運(yùn)動(dòng)控制。

V423.4；TP391.9

A

1006-3242(2016)05-0070-07