遙感衛星覆蓋任意區域快速仿真算法研究

李洪亮 王 倩 李運華

1.北京航空航天大學自動化科學與電氣工程學院，北京 100191 2. 北京空間飛行器總體設計部，北京 100094

?

遙感衛星覆蓋任意區域快速仿真算法研究

李洪亮1王 倩2李運華1

1.北京航空航天大學自動化科學與電氣工程學院，北京 100191 2. 北京空間飛行器總體設計部，北京 100094

在軌衛星對地觀測體系效能仿真涉及的衛星資源數量眾多，任務范圍大，以致仿真分析時的計算規模較大。在研究多星對指定區域的覆蓋效能時，需要從體系仿真的角度構建合適的覆蓋模型以及優化的仿真算法。首先分析了光學遙感衛星的幾何定位原理，建立了遙感衛星的覆蓋視場，提出簡單有效的判定方法實現任意不規則區域網格點的劃分，最后利用Multimap優化算法和K近鄰搜索算法實現區域網格點的快速搜索統計。通過與傳統搜索方法的對比實驗表明這兩種優化算法可以極大地提高網格點統計效率。 關鍵詞 在軌衛星；覆蓋效能；覆蓋視場；Multimap優化算法；K近鄰；網格點

衛星對區域的覆蓋分析，一般利用網格點分析法，首先將地球表面某一區域進行網格點劃分，仿真特定時間，統計被星載傳感器覆蓋到的網格點作為覆蓋特性評估的依據。網格點分析法具有較高的仿真精度，而且對于任意軌道和任意形狀的覆蓋視場都能適用，已成為覆蓋求解的最主要方法。

國內外在衛星對地覆蓋以及網格點分析法方面做了大量研究工作。1970年，J.C.Walkery研究了圓軌道衛星星座構成的全球覆蓋模型，在該領域做出了開創性的工作[1]。Morrison在1973年研究多重覆蓋時首先提出了網格方法[2]。1989年，J.Middour給出了一種基于多邊形視場技術的衛星對地覆蓋計算方法[3]。Sandau R等對小衛星群全球覆蓋問題做了大量研究工作，探究了覆蓋問題新的領域[4]。

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

在衛星覆蓋仿真優化方面，賀勇軍等研究了非規則覆蓋區域網格點求解的幾個通用算法[11]。宋志明等采用了不同于網格點分析法的經度條帶法來提高星座覆蓋仿真效率[12]。秦睿杰等則提出了基于抽樣的網格點統計算法[13]。沈夏炯等對任意區域優化了衛星過境覆蓋分析的計算方法[14]。

當對指定區域利用網格點分析法進行覆蓋效能指標(如重訪時間、間隙周期，覆蓋百分比等)分析時，隨著網格點數目增加，內存和時間消耗會急劇上升。仿真時發現耗時主要體現在衛星視場與區域網格點的可見性判斷上，因為衛星載荷要遍歷大量網格點，這造成時間和空間復雜度很高。這一問題需要從載荷建模、區域劃分、網格點統計和可見性解算等方面綜合考慮。

本文給出覆蓋視場建模方式，優化了衛星視場與任意區域網格點可見性判斷方法，利用Multimap關聯容器和改進的K近鄰搜索算法，實現遙感衛星覆蓋視場內網格點的快速搜索，仿真實驗給出了3種搜索算法的計算耗時對比。最后將整體仿真模型和STK軟件的覆蓋結果進行了比較，驗證了所建立仿真模型的準確性。

1 遙感衛星覆蓋視場建模

1.1 遙感幾何定位

衛星在軌道上任意一點對地形成的覆蓋視場與衛星傳感器的視場角、衛星姿態和位置有關，覆蓋視場可根據遙感幾何定位建模。圖1是遙感衛星幾何定位的示意圖，P是遙感點(被觀察點)，S為遙感衛星，B為星下點。

圖1 遙感衛星幾何定位原理圖

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

r+ρ=OP

(1)

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

設慣性系下P點的坐標(Px,Py,Pz), 其符合地球橢圓公式：

(2)

式中,ae和be分別為地球半長軸和半短軸。

將式(2)展開得

(3)

(4)

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

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

利用式(4)和Δ的判別結果求得ρ，再由衛星在慣性坐標系下的位置r計算得到遙感點P在慣性系下的坐標(Px,Py,Pz)。

(5)

由地心固連坐標系與慣性系的轉換矩陣得到地固坐標系的坐標位置：

(6)

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

設求得的地固坐標系坐標為(X,Y,Z)，大地經緯高的計算一般采用迭代法。

(7)

其中，e為地球偏心率。

(8)

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

1.2 覆蓋視場建模

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

(9)

最后根據前面討論的幾何定位原理，確定4個視線矢量在大地坐標系下的投影點P1，P2，P3，P4，從而確定地球表面產生的四邊形各點經緯度，即覆蓋視場P1P2P3P4。

圖2 遙感衛星覆蓋視場

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

2 任意不規則區域網格點劃分

網格點分析法即將地球表面或指定區域進行網格劃分，網上的每個結點被稱為網格點，對應于地面上相應的經緯度點，網格點的劃分通常可采用等經緯度法和等面積法[11]。受限于地球的形狀特征，由等經緯度劃分出的網格點，不同緯度上的網格點密集程度是不一樣的，每個網格點所代表的面積大小也是不一樣的。

2.1 經緯度及網格點面積

設有不同經緯度上的2點:(λ1，φ1)，(λ2，φ2)，經緯度距離公式為：

d=

(10)

設網格點經緯度劃分步長為Δλ和Δφ。由于Δλ和Δφ較小，可將劃分的網格區域近似看成矩形區域。

對應的網格點面積：

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

(11)

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

2.2 兩種劃分算法

首先確定指定區域的邊界，邊界可以通過讀邊界文件獲得，也可以粗略地在程序中指定，邊界點越密集則區域邊界越光滑。然后求取邊界最大最小經緯度，再生成網格點，最后由水平/垂直交叉點數判別法篩選出在區域邊界內的網格點。

圖3 水平/垂直交叉點數判別法

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

圖4 網格點劃分原理圖

等經緯度網格點生成算法：

1) 由區域邊界得到最大及最小經緯度λmax,λmin,φmax,φmin；

2) 指定經度細分步長Δλ，緯度細分步長Δφ，再依次生成網格點{λmin,φmin}，{λmin+Δλ，φmin+Δφ}，{λmin+2Δλ，φmin+2Δφ}，…，Until {λn，φn} <={λmax，φmax}；

3) 水平/垂直交叉點數判別法篩選出區域邊界內的所有網格點，得到區域邊界內網格點集合{Pot1，Pot2，Pot3，…，Potn}。

等面積法網格點生成算法：

1) 同等經緯度網格點生成算法所述1)；

2) 首先確定低緯度φmin的劃分網格點數m，確定緯度之間的步長Δφ，由低緯度φmin到高緯度φmax劃分的網格點數依次為

3) 篩選出邊界范圍內的網格點，得到網格點集合{Pot1，Pot2，Pot3，…，Potn}。

3 覆蓋視場快速解算算法

當衛星對指定區域形成覆蓋視場時，每步仿真時只有在覆蓋視場內的網格點才作為覆蓋到的目標點，即要做目標點與衛星覆蓋視場的可見性關系判斷。這種隸屬關系判斷即是判斷一個點是否被包含在一個多邊形區域內。可以用網格點劃分時采用的水平/垂直交叉點數判別法。以下算法以等經緯度劃分原理圖來說明，對于等面劃分的網格點也是適用的。

3.1 線性掃描法

每一步仿真中，將所有網格點都代入覆蓋視場中，作隸屬關系判斷，然后統計出在四邊形視場內的網格點。這種方法對網格點的存儲要求簡單，但每個網格點都要做水平/垂直交叉點數判別法判斷，運算量較大，效率較低。

3.2 Multimap優化算法

Multimap 使用紅黑二叉樹記錄數據元素，按元素鍵值的大小自動排序，可進行最優化的快速插入、刪除和檢索等操作。在multimap 中，元素的鍵值key與元素value的映照關系是多對多的，即允許存儲具有重復鍵值的元素，因此，multimap 稱為多重映照容器。

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

圖5 Multimap優化算法原理圖

算法思想：

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

4) 重復循環過程3)，依次作行和列搜索，一直搜索到邊界極值點Q′″，停止搜索；

5) 其中2)～4)的每一步找到的網格點都由水平/垂直交叉點數判別法判別是否在覆蓋視場內；

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

3.3 改進的K近鄰搜索算法

K近鄰算法在空間海量數據搜索中應用廣泛[15-18]。該算法首先要構造k-d樹存儲網格點數據，選擇網格點集合經緯度上的中位數為切分點。依次選取經度和緯度將每一層空間切分為二，循環往復。最終每個節點對應于劃分中的一個超矩形區域。K近鄰算法要使用搜索距離，可采用式(10)經緯度的距離公式改進方式，

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

設計的覆蓋視場搜索算法可以利用文獻[16]提出的一種空間球搜索思想，在一個數據中心的超球內進行查詢，超球半徑由0開始逐漸增大，并且根據查詢結果更新，直到超球內包含K個近鄰點而停止。由于網格點集合設計的是二維區域，算法的終止條件是搜索到半徑范圍內所有網格點。

在搜索過程中存儲搜索到的網格點數據，假設有k1

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

算法思想：

1) 利用k-d樹存儲網格點集合{Pot1，Pot2，Pot3，…，Potn}；

2) 由覆蓋視場的4個投影點計算得到視場中心點Q，并以Q點為中心，四邊形對角線的一半為搜索半徑D，利用K近鄰進行搜索，在搜索過程中構建大頂堆；

3) 當搜索的近鄰點到中心Q的距離d≤D時，按K近鄰的機制回溯查找，且更新大頂堆；當近鄰點到中心點Q的距離d>D時，搜索結束，保存搜索到的所有網格點；

4) 由圖6可知：搜索過程①→②→③→④→ …，直到搜索到半徑范圍內的所有點；

5) 由水平/垂直交叉點數判別法篩選出在覆蓋視場內的可見網格點。

4 仿真實驗

開發環境如下：處理器：Intel(R) Xeon(R) CPU E5504 @ 2.00GHz 內存：3.23GB 操作系統：Windows XP 編程語言：C++。

這里統計某一仿真步長內，在覆蓋視場范圍內400個網格點的搜索時間。

通過大量實驗發現效率結果有相似的規律，以Multimap優化算法和K近鄰搜索算法相對線性掃描的效率優化倍數為縱坐標，網格點數為橫坐標，作圖7和8。

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

圖7 Multimap優化算法效率圖

圖8 K近鄰搜索效率圖

由實驗結果可知，線性掃描運行時間隨網格點數的增長而成線性增長，Multimap優化效率比線性掃描高，當網格點數比較大時，Multimap優化效率的倍數趨于穩定，呈緩慢增長。而K近鄰搜索耗時隨網格點數增多并沒有顯著增加。

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

網格點分析法在每個仿真步長內需要統計所有網格點的可見性，基于以上覆蓋視場的求解算法可以很快找到在覆蓋視場內的網格點，將這些網格點設置為可見，其余則默認設置為不可見。仿真一段時間可以得到所有網格點的可見時刻集合。對網格點可見時刻集合進行合并和計算統計即可得到覆蓋特性指標結果。

圖9是某星座下的空間覆蓋率仿真結果，軌道采用J2攝動模型，網格點分析法采用等面積劃分和K近鄰搜索，將整體仿真模型與STK仿真出的空間覆蓋率進行對比，實驗誤差在1.5%范圍內，驗證了模型的準確性，而多星體系仿真效率有了很大提升。

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

5 結論

實現了對遙感衛星覆蓋視場建模和任意區域網格點的劃分。通過對3種覆蓋視場搜索算法的比較可知K近鄰效率較高，并且對其他網格點劃分方式，以及非四邊形覆蓋視場也可以適用。此外，在確保仿真精度的前提下，為了仿真運行的效率可以將一些模型進行簡化，而將GPU引入到網格點算法仿真中也是值得探究的方向。

[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] 曹平, 章文毅, 馬廣彬. 遙感衛星成像模型研究及仿真[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] 羅盛茂，李紅.低軌衛星編隊飛行的地面覆蓋及軌道調整[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] 范麗, 張育林. 區域覆蓋混合星座設計[J]. 航天控制, 2007, 25(6): 52-55. (Fan Li, Zhang Yuli. Regional Coverage Hybrid Constellation Design[J]. Aerospace Control, 2007, 25(6): 52-55.)

[8] 簡平, 鄒鵬, 熊偉, 陳治科. 改進的低軌凝視傳感器覆蓋性能網格分析方法[J]. 空軍工程大學學報(自然科學版), 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]. 宇航學報,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] 賀勇軍, 戴金海. 多衛星非規則覆蓋區域的通用求解算法[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] 宋志明, 戴光明, 王茂才, 彭雷. 衛星星座區域覆蓋問題的快速仿真算法[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]. 計算機應用研究, 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] 沈夏炯, 吳曉洋, 王更科, 韓道軍. 面向任意幾何區域的遙感衛星對地覆蓋法[J]. 計算機應用研究,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] 衛煒, 張麗艷, 周來水. 一種快速搜索海量數據集K-近鄰空間球算法[J]. 航空學報, 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-)，男，安徽人，碩士研究生，主要研究方向為航天器系統仿真；王 倩(1985-)，女，遼寧人，高級工程師，主要研究方向為航天器系統仿真；李運華(1963-)，男，河北人，博士，教授，主要研究方向為非線性動力學與運動控制。

V423.4；TP391.9

A

1006-3242(2016)05-0070-07