北斗靜止軌道衛(wèi)星信號盲區(qū)快速并行解算方法*

郭甲騰，吳立新，2，楊宜舟，李超嶺，劉善軍(.東北大學(xué)測繪遙感與數(shù)字礦山研究所，遼寧沈陽089；2.中國礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇徐州22008；.中國地質(zhì)調(diào)查局發(fā)展研究中心，北京0007)

北斗靜止軌道衛(wèi)星信號盲區(qū)快速并行解算方法*

郭甲騰1，吳立新1，2，楊宜舟1，李超嶺3，劉善軍1
(1.東北大學(xué)測繪遙感與數(shù)字礦山研究所，遼寧沈陽110819；2.中國礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇徐州221008；3.中國地質(zhì)調(diào)查局發(fā)展研究中心，北京100037)

北斗系統(tǒng)靜止軌道衛(wèi)星信號盲區(qū)解算方法復(fù)雜，串行計算耗費時間長，須在并行環(huán)境下利用更多的計算資源進行北斗盲區(qū)的快速解算。在分析北斗盲區(qū)解算原理與算法并行特征基礎(chǔ)上，提出動態(tài)盲區(qū)影響域的并行解算方法。以柵格單元為并行粒度進行任務(wù)劃分，實現(xiàn)了北斗盲區(qū)的高效并行解算。運用全國范圍59景數(shù)字高程模型數(shù)據(jù)，利用8進程進行盲區(qū)并行解算，耗費時間約為5小時。實驗測試結(jié)果表明:算法的并行效率隨著進程數(shù)的增加有所衰減，但穩(wěn)定在96%以上。其程序中間件已集成應(yīng)用于高性能地理信息平臺，應(yīng)用效果良好。

北斗系統(tǒng)；并行計算；盲區(qū)解算；高性能地理信息系統(tǒng)；數(shù)字高程模型

北斗衛(wèi)星導(dǎo)航系統(tǒng)(簡稱北斗系統(tǒng))的空間段由5顆靜止軌道衛(wèi)星(北斗G4，G1，G3，G6與G5)和30顆非靜止軌道衛(wèi)星(中圓軌道衛(wèi)星和傾斜地球同步軌道衛(wèi)星)組成［1-3］。組成北斗系統(tǒng)的三種衛(wèi)星的功能特點分別為:地球靜止軌道衛(wèi)星具備有源、無源、短報文通信三種服務(wù)功能［1-3］；中圓軌道衛(wèi)星和傾斜地球同步軌道衛(wèi)星只具有無源定位、導(dǎo)航和授時功能［1］。北斗系統(tǒng)中由于有了地球靜止軌道衛(wèi)星，才保證了有源定位、導(dǎo)航和授時服務(wù)以及短報文通信和位置報告功能。北斗靜止軌道衛(wèi)星的短報文通信功能可為采用北斗技術(shù)的戶外移動設(shè)備、監(jiān)測設(shè)備或野外工作人員提供短信播發(fā)服務(wù)，尤其針對手機信號盲區(qū)或無其他通信條件的地區(qū)(如無人區(qū)、高海拔地區(qū)等)，能在生命安全保障、生產(chǎn)物資調(diào)度、人員態(tài)勢管理、日常業(yè)務(wù)溝通等方面發(fā)揮關(guān)鍵作用。目前，北斗衛(wèi)星技術(shù)已正式投入民用，北斗衛(wèi)星信號接收傳感器也已日益普及［4］。由于北斗導(dǎo)航系統(tǒng)的優(yōu)勢，其被交通運輸［5］、基礎(chǔ)測繪［6］、工程勘測［7］等領(lǐng)域積極探索應(yīng)用，尤其體現(xiàn)在應(yīng)急救援［7-8］、物資保障［9］、信息推送［10-11］等方面。然而，北斗靜止軌道衛(wèi)星受地球表面彎曲、山體或障礙物遮擋等因素的影響，衛(wèi)星終端設(shè)備在個別區(qū)域通信報文信號很弱(或稱盲區(qū))，制約著北斗通信的正常進行。因此，預(yù)先解算北斗系統(tǒng)信號盲區(qū)(或可視域)，能為基于北斗衛(wèi)星應(yīng)用技術(shù)的野外應(yīng)用和管理工作提供重要的參考依據(jù)。由于北斗靜止軌道衛(wèi)星信號盲區(qū)解算(下文簡稱盲區(qū)解算)與地形直接相關(guān)，因此采用的基礎(chǔ)數(shù)據(jù)是數(shù)字高程模型(Digital Elevation Model，DEM)數(shù)據(jù)。由于柵格DEM數(shù)據(jù)量龐大并且盲區(qū)解算復(fù)雜，采用串行算法解算效率較低。據(jù)前期經(jīng)驗，僅依據(jù)中國區(qū)域3″(90m)分辨率DEM的盲區(qū)解算就需花費數(shù)月，分辨率更高時則耗時更長，無法滿足應(yīng)急需求。近年計算機計算能力迅速提高，尤其是多核計算機和并行計算機開始普及，如何利用這些新的計算資源來解決更復(fù)雜的實際應(yīng)用，已成為目前科學(xué)計算領(lǐng)域十分關(guān)注的問題［12］。在信息領(lǐng)域，并行計算為協(xié)同利用更多的計算資源提供了新的手段，實現(xiàn)了利用多個計算節(jié)點的計算資源來提高計算能力［13］。因此，郭甲騰等利用北斗靜止軌道衛(wèi)星數(shù)字化尋星原理［14］，引入地面點動態(tài)盲區(qū)影響域，提出了北斗信號盲區(qū)并行化解算方法，開發(fā)了并行計算中間件，將其集成到高性能地理計算平臺(High Performance Geographic Information System，HiGIS)中，并基于SRTM 90m分辨率數(shù)據(jù)對全國范圍北斗靜止軌道衛(wèi)星信號盲區(qū)進行了解算，大幅提高了計算效率。

1 北斗靜止軌道衛(wèi)星尋星原理

盲區(qū)解算中各參數(shù)如圖1［14］所示:地球橢球長半軸a=6 378 137m；地球橢球短半軸b=6 356 752m；衛(wèi)星s距地高度為H；衛(wèi)星s的經(jīng)度為ω；地面任意點p的海拔高度為h；p點經(jīng)度為λ；p點緯度為φ；p點至衛(wèi)星s的視域仰角為β；p點至衛(wèi)星s的方位角為α；選定xoy平面為赤道面；x軸指向起始經(jīng)度；z軸與旋轉(zhuǎn)橢球體自轉(zhuǎn)軸保持一致；e點為p點沿法線方向投影至橢球切平面處的交點；g點為過p點的法線向量與赤道面的交點；r為e點至原點o的距離；過p點的法截面與切平面的交線為ef；過p點且平行于切平面與os相交于q點；t為切平面與過p點的子午面交匯處。

地面任意點到衛(wèi)星的距離為:

其中，gt為g點到t點的長度，et為e點到t點的長度，gs為g點到s點的長度，og為o點到g點的長度。

地面任意點到衛(wèi)星的視域仰角為:

其中，θ為∠pgs，δ為∠psg。

圖1 北斗衛(wèi)星尋星參數(shù)幾何關(guān)系圖［14］Fig.1 Geometric relationship of parameters for finding BeiDou satellites

對于地面任意柵格單元p(下文簡稱目標(biāo)柵格)，首先解算其與衛(wèi)星位置連線的方位角，并計算出在方向上某一區(qū)域z(z為目標(biāo)柵格的信號盲區(qū)影響域)內(nèi)可能遮擋目標(biāo)柵格衛(wèi)星信號的柵格單元集S，并依次解算S中各柵格單元(下文簡稱遮擋柵格)針對目標(biāo)柵格的信號遮擋狀態(tài)。目標(biāo)柵格衛(wèi)星信號的遮擋柵格計算在區(qū)域z內(nèi)均為獨立計算，不同目標(biāo)點的z值不同且互不影響，因此各柵格單元可并行地進行盲區(qū)計算。綜上所述，實現(xiàn)盲區(qū)并行化解算的難點是目標(biāo)柵格單元的盲區(qū)影響域z的計算。

2 運用DEM數(shù)據(jù)的北斗靜止軌道衛(wèi)星盲區(qū)并行解算

2.1 北斗信號盲區(qū)影響域分析

與北斗靜止軌道衛(wèi)星連線方位角的地面點呈線狀分布(在DEM數(shù)據(jù)中為一組呈線性的柵格單元集合)，所以求解位置p的北斗信號狀態(tài)(可視或盲區(qū))需要方位角的其他所有柵格單元均參與計算。由于地球?qū)嶋H環(huán)境的影響，如地球曲率、地球高程差臨界值ΔM(地球上海拔最高點與最低點最大相差約為20 000m，在中國區(qū)域內(nèi)約為9200m)，所以目標(biāo)柵格的盲區(qū)影響域應(yīng)位于某一范圍內(nèi)，即不需要所有方位角的DEM柵格單元均參與柵格單元p的信號狀態(tài)解算。p的衛(wèi)星視域仰角與其所在的經(jīng)緯度位置相關(guān)，p的經(jīng)緯度值與衛(wèi)星的經(jīng)緯度值相差越大，則p的β越小［11］，盲區(qū)影響域范圍越大。若d在某區(qū)域內(nèi)的高程較大(如圖2所示)，則其可在離p較遠(yuǎn)的位置對p的信號進行遮擋。若某區(qū)域內(nèi)位置d高程最大，位置p高程最小，則兩點的高程差Δm為該區(qū)域內(nèi)的高程差臨界值。因此，p的影響域范圍大小與衛(wèi)星的視域仰角及地球高程差臨界值Δm相關(guān)，影響域半徑為:

圖2 北斗盲區(qū)影響域Fig.2 Influence scope of BeiDou signals blind area

信號盲區(qū)影響域的選擇結(jié)果會直接影響到盲區(qū)計算的效率。由于中國大部分區(qū)域內(nèi)局部范圍的Δm遠(yuǎn)小于ΔM，若所有局部區(qū)域都采用中國區(qū)域的高差臨界值ΔM來計算影響域范圍z(ΔM)，將擴大局部區(qū)域的盲區(qū)影響域范圍，從而使信號盲區(qū)的計算量急劇增加，特別是對處于北斗靜止衛(wèi)星可視邊緣區(qū)域的影響尤為明顯。因此，需在局部區(qū)域內(nèi)計算位置p更為準(zhǔn)確的盲區(qū)影響域的高程差臨界值Δm(Δm＜ΔM)。所以針對中國范圍，提出了局部區(qū)域內(nèi)信號盲區(qū)影響域的計算方法。

首先采用中國區(qū)域內(nèi)的高差極大值ΔM，根據(jù)式(4)獲取以p為中心的z(ΔM)范圍內(nèi)數(shù)據(jù)(如圖3所示)，遍歷該區(qū)域內(nèi)海拔最高柵格單元與海拔最低柵格單元的高差Δm，再以Δm為高差臨界值，根據(jù)式(4)重新獲取p的影響域z(Δm) (如圖3所示)，通過z(Δm)逼近p實際的盲區(qū)影響域范圍，以達到降低計算量的目的。

圖3 p的盲區(qū)影響域Fig.3 BeiDou signals blind area of p

據(jù)上所述，被遮擋點p的信號影響域范圍隨著經(jīng)緯度位置動態(tài)變化，其盲區(qū)計算量也不一樣。而空間相鄰的被遮擋點影響域大小基本相同，其盲區(qū)計算量差異較小。因此，在基于DEM的北斗盲區(qū)并行解算過程中，為確保各計算節(jié)點負(fù)載均衡，應(yīng)將DEM數(shù)據(jù)中空間相鄰的目標(biāo)柵格分配至不同的計算節(jié)點進行解算。

2.2 信號盲區(qū)解算方法分析

運用上文所述盲區(qū)影響域計算方法，先解算DEM數(shù)據(jù)中所有柵格點的盲區(qū)影響域，在此基礎(chǔ)上實現(xiàn)北斗盲區(qū)的解算(如圖4所示)。p在局部范圍內(nèi)衛(wèi)星信號被遮擋的區(qū)域(盲區(qū)影響域)大小為n×n(n=Re為柵格的分辨率)。

圖4 北斗信號盲區(qū)解算Fig.4 Calculation of BeiDou signal blind area

1)計算p與北斗靜止衛(wèi)星連線的方位角α方向上且在z(Δm)內(nèi)可能會對p信號遮擋的柵格單元集s(北斗靜止軌道衛(wèi)星在赤道上方，所以對于北半球，s在p的南方，而對于南半球，s在p的北方)。

2)p高程為h，相鄰柵格點之間的距離為L，p的仰角為β，則距離p有m(1＜m＜n)個柵格單元位置的高程為hm，要遮擋p需滿足的條件為:

若在大區(qū)域范圍內(nèi)則需要顧及地球曲率對高程的影響，表示為Δh=，其中，S為兩點之間的距離，R為地球半徑。

3)重復(fù)步驟2，依次計算s中各柵格單元對p的北斗信號遮擋狀態(tài)，若發(fā)生遮擋，則結(jié)束計算，若不發(fā)生遮擋，則繼續(xù)計算s中下一個目標(biāo)柵格。

2.3 北斗信號盲區(qū)并行解算特點分析

基于DEM數(shù)據(jù)解算北斗信號盲區(qū)的過程，如圖5所示，按照柵格A、B、C、D的順序依次獲取影響域并分別進行計算。北斗盲區(qū)計算屬于計算密集型與數(shù)據(jù)密集型算法，將各柵格點與周圍某一相關(guān)區(qū)域的點集進行計算，根據(jù)地理并行計算算法分類的方法［13］可知該算法屬于區(qū)域計算，通過數(shù)據(jù)并行的方式即可實現(xiàn)盲區(qū)解算的并行化。雖然DEM中柵格單元的盲區(qū)影響域大小隨著其經(jīng)緯度的不同而動態(tài)變化，但空間相鄰的柵格點的影響域范圍大小基本相同，即相鄰柵格單元中參與盲區(qū)計算的柵格點數(shù)目基本相等，所以基于DEM盲區(qū)計算具有以下特點:

1)將空間相鄰的柵格單元分配至不同的計算節(jié)點，則各計算節(jié)點參與計算的柵格單元數(shù)量均衡。

2)由于空間相鄰的柵格單元的盲區(qū)影響域大小基本相同(盲區(qū)影響域中參與計算的柵格數(shù)目基本相等)，將空間相鄰的柵格單元分配至不同的計算節(jié)點，則各計算節(jié)點的計算量均衡。

圖5 北斗信號盲區(qū)解算任務(wù)分布Fig.5 Task distribution for calculation of BeiDou signals blind area

現(xiàn)有并行編程模型可分為三類［15］:消息傳遞模型、共享存儲模型和數(shù)據(jù)并行模型。共享存儲模型屬于線程級細(xì)粒度并行，數(shù)據(jù)共享存儲、操作異步、數(shù)據(jù)隱式分配，程序可擴展性較差；數(shù)據(jù)并行模型屬于進程級細(xì)粒度并行，數(shù)據(jù)共享存儲、操作松散同步、數(shù)據(jù)半隱式分配，程序擴展性一般；而消息傳遞模型是目前使用最為廣泛的并行模型，具有兩大優(yōu)勢:

1)消息傳遞程序具有高度的可移植性與可擴展性，理論上可在任何并行機上執(zhí)行，即不需要特殊的硬件支持。

2)允許用戶顯式地控制并行程序中每個進程內(nèi)存的使用，為編程人員實現(xiàn)高性能計算提供便利。

消息傳遞模型的并行程序開發(fā)模式通常有兩種:單程序多數(shù)據(jù)(Single Program Multiple Data，SPMD)模式和多程序多數(shù)據(jù)(Multiple Program Multiple Data，MPMD)模式。根據(jù)北斗盲區(qū)的解算特點，僅通過數(shù)據(jù)劃分即可實現(xiàn)任務(wù)分解，或是通過任務(wù)量的劃分也可實現(xiàn)任務(wù)的分解，且能保持北斗盲區(qū)并行計算過程中的負(fù)載均衡與任務(wù)均衡，即各進程對已分配任務(wù)執(zhí)行相同的算法，對不同的數(shù)據(jù)集協(xié)同進行計算。因此，采用SPMD模式設(shè)計并行算法，實現(xiàn)北斗靜止軌道衛(wèi)星信號盲區(qū)的并行計算。

圖6 北斗盲區(qū)并行解算流程Fig.6 Calculation process of BeiDou signals blind area

2.4 北斗信號盲區(qū)并行解算方法設(shè)計

根據(jù)上文分析可知，北斗盲區(qū)計算屬于計算密集型算法(I/O與計算相比所耗費的時間較少)，算法以柵格點為單位進行解算，若直接通過數(shù)據(jù)劃分(條帶劃分、塊劃分)，可能導(dǎo)致各節(jié)點的計算量不均衡(如6001×6001的DEM數(shù)據(jù)塊分配給8個進程，若以條帶劃分會使其中7個進程計算量為750行，另外1個進程計算量為751行，使進程間差距6001個柵格點的計算量)，而通過以柵格點為粒度的任務(wù)劃分，各進程間最多相差一個柵格點的計算量。由于解算過程中計算時間遠(yuǎn)大于DEM數(shù)據(jù)的I/O時間，因此采用任務(wù)劃分的方法實現(xiàn)盲區(qū)計算的并行化，即各進程的DEM數(shù)據(jù)全冗余，通過任務(wù)量的劃分方式實現(xiàn)并行任務(wù)的分解，如圖6所示，將任務(wù)規(guī)劃分至不同的計算節(jié)點實現(xiàn)北斗盲區(qū)解算的并行化。

針對北斗盲區(qū)計算，任務(wù)劃分的粒度以柵格為單位，以保持各個進程的計算量均衡。任務(wù)劃分的步驟如下:

1)待劃分的DEM柵格數(shù)據(jù)集為Rs，其大小為M×N(DEM數(shù)據(jù)包含的柵格數(shù)目)，其中M為橫向柵格數(shù)目，N為縱向柵格數(shù)目，DEM中每個柵格的位置標(biāo)示為Lmn(lm，ln)；

2)參與柵格盲區(qū)計算的進程總數(shù)P={p1， p2，p3，……，pi}；

3)DEM數(shù)據(jù)是以行為單位組，以柵格單元為單位進行分配，若柵格單元的所在行號n與進程總數(shù)p取余得到pt，則以pt作為計算進程組的第一進程，對所有進程進行排序，排序后的結(jié)果為P= {pt，pt+1，…，pi，p1，…，pt-1}，如圖7所示，通過此方法可將相鄰的柵格單元分配至不同的計算節(jié)點；

4)計算進程組分配順序后，以柵格單元的lm值為參考進行輪轉(zhuǎn)分配；

5)重復(fù)步驟3、步驟4，直到所有的像素點分配完畢。

圖7 任務(wù)劃分Fig.7 Task partitioning

3 實驗

3.1 測試環(huán)境

為測試方法的正確性與計算效率，搭建了一個小型集群的測試環(huán)境。該環(huán)境由2個高性能計算節(jié)點及1個存儲節(jié)點(8T)構(gòu)成，集群中各節(jié)點的CPU為Intel(R)Xeon(R)E5405(2.0GHz，64位)，操作系統(tǒng)為Redhat 6.6(64位)，消息傳遞采用OPENMPI并行庫，節(jié)點間采用高性能交換機進行通信。

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

實驗采用的DEM數(shù)據(jù)為SRTM 90m分辨率(分辨率為3″)數(shù)據(jù)，每景數(shù)據(jù)的大小約為6001× 6001，數(shù)據(jù)量約為68MB。而中國區(qū)域內(nèi)約包含59景數(shù)據(jù)，數(shù)據(jù)量約為4GB。5顆地球靜止軌道衛(wèi)星的參數(shù)見表1。

3.3 測試結(jié)果

為驗證盲區(qū)解算方法的正確性，選擇湖北、四川、陜西地區(qū)的交界處(精度范圍為105°E～110°E，30°N～35°N的區(qū)域，該區(qū)域DEM數(shù)據(jù)大小為6001×6001)進行了信號盲區(qū)的并行解算。實驗區(qū)域位于長江中游地區(qū)，以山區(qū)為主，有少量平原。經(jīng)與中國地質(zhì)調(diào)查局前期開展的信號盲區(qū)串行解算實驗結(jié)果對比發(fā)現(xiàn)，實驗區(qū)信號盲區(qū)基本一致，如圖8所示。

表1 北斗同步軌道衛(wèi)星信息Tab.1 Information of BeiDou geostationary orbit satellites

由北斗盲區(qū)并行解算性能(見表2)，可知:在單進程下解算上述區(qū)域的時間為1 092.69s，在8進程下并行解算的時間為142.65s，并行計算的最大加速比為7.66(并行計算比與進程數(shù)的關(guān)系如圖9所示)，并行效率穩(wěn)定在96%以上(并行效率與進程數(shù)的關(guān)系如圖10所示)。利用8進程對全國范圍內(nèi)的59景DEM數(shù)據(jù)進行北斗衛(wèi)星信號盲區(qū)并行解算，耗費時間約為5h。

圖8 北斗盲區(qū)計算結(jié)果顯示(a.中國北斗盲區(qū)矢量圖；b.北斗盲區(qū)三維顯示) Fig.8 Visualization of result of BeiDou signal blind area (a.Vector display of BeiDou signals blind area of China；b.Three-dimensional display of BeiDou signals blind area)

表2 北斗盲區(qū)并行解算性能Tab.2 Parallel computing performance ofBeiDou signal blind area

圖9 北斗盲區(qū)并行解算加速比Fig.9 Speedup of BeiDou signal blind area calculation

同時，將北斗盲區(qū)并行計算的方法封裝為中間件，并以工具集成應(yīng)用到HiGIS平臺中。在HiGIS平臺中利用此方法進行計算，北斗盲區(qū)的解算結(jié)果與本文環(huán)境下的結(jié)果相同。

4 結(jié)論

針對北斗靜止軌道衛(wèi)星全國信號盲區(qū)并行解算的方法進行了探索與研究，引入了北斗信號盲區(qū)影響域的確定原理，提出了北斗信號盲區(qū)的快速求解方法，并在此基礎(chǔ)上實現(xiàn)了盲區(qū)解算的并行化。由于測試實驗環(huán)境為單機多核，當(dāng)進程數(shù)增加時，并行加速比會隨著進程數(shù)的增加而有所衰減，但基本穩(wěn)定在96%以上，并行加速比達到7.6以上。若在網(wǎng)絡(luò)通信性能較弱的集群上進行測試，則需考慮I/O的影響。實驗結(jié)果表明，北斗靜止軌道衛(wèi)星盲區(qū)并行解算方法可行。同時，基于本文方法實現(xiàn)的程序中間件已集成部署在HiGIS平臺中，有望應(yīng)用于高性能計算環(huán)境下基于更高精度DEM數(shù)據(jù)的北斗靜止軌道衛(wèi)星信號盲區(qū)快速解算。

圖10 北斗盲區(qū)解算并行效率Fig.10 Parallel efficiency of BeiDou signal blind area calculation

References)

［1］BDS-OS-PS-1.0.北斗衛(wèi)星導(dǎo)航系統(tǒng)公開服務(wù)性能規(guī)范［S］.北京:中國衛(wèi)星導(dǎo)航系統(tǒng)管理辦公室，2013.BDS-OS-PS-1.0.BeiDou Navigation satellite system open service performance standard［S］.Beijing:China Satellite Navigation Office，2013.(in Chinese)

［2］Yang Y X，Li JL，Wang A B，et al.Preliminary assessment of the navigation and positioning performance of BeiDou regional navigation satellite system［J］.Science China:Earth Sciences，2014，57(1):144-152.

［3］楊元喜，李金龍，徐君毅，等.中國北斗衛(wèi)星導(dǎo)航系統(tǒng)對全球PNT用戶的貢獻［J］.科學(xué)通報，2011，56(21): 1734-1740.YANG Yuanxi，Li Jinlong，Xu Junyi，et al.Contribution of the compass satellite navigation system to global PNT users［J］.Chinese Science Bulletin，2011，56(21):1734-1740.(in Chinese)

［4］唐金元.北斗衛(wèi)星導(dǎo)航區(qū)域系統(tǒng)發(fā)展應(yīng)用綜述［J］.全球定位系統(tǒng)，2013，38(5):47-52.TANG Jinyuan.Developing and applying analysis of BeiDou navigation satellites regional system［J］.GNSS World of China，2013，38(5):47-52.(in Chinese)

［5］萬琪俊.基于北斗導(dǎo)航衛(wèi)星移動定位系統(tǒng)研究與實現(xiàn)［D］.廣州:華南理工大學(xué)，2013.WAN Qijun.Research and implementation ofmobile location system of BeiDou navigation satellite base on android［D］.Guangzhou:South China University of Technology，2013.(in Chinese)

［6］王家耀.測繪導(dǎo)航與地理信息科學(xué)技術(shù)的進展［J］.測繪科學(xué)技術(shù)學(xué)報，2014，31(5):441-449.WANG Jiayao.The progress of geomatics navigation and geographic information science and technology［J］.Journal of Geomatics Science and Technology，2014，31(5):441-449.(in Chinese)

［7］溫靜，汪大明，孟月玥，等.北斗衛(wèi)星導(dǎo)航系統(tǒng)在地質(zhì)調(diào)查領(lǐng)域應(yīng)用綜述［J］.地質(zhì)力學(xué)學(xué)報，2012，18(3): 213-223.WEN Jing，WANG Daming，MENG Yueyue，et al.Application of BeiDou navigation satellite system to geological survey［J］.Journal of Geomechanics，2012，18(3):213-223.(in Chinese)

［8］石小亞，王占昌，伍錦程.北斗衛(wèi)星技術(shù)在青海玉樹地質(zhì)災(zāi)害詳查中的示范應(yīng)用［J］.地質(zhì)力學(xué)學(xué)報，2012，18(3):277-281.SHIXiaoya，WANG Zhanchang，WU Jincheng.Demonstration application of BeiDou satellite technology in detailed geological disaster investigation in Yushu，Qinghai province［J］.Journal of Geomechanics，2012，18(3):277-281.(in Chinese)

［9］李小杰，葉成明，鄭寶鋒.基于北斗的地質(zhì)調(diào)查安全生產(chǎn)保障系統(tǒng)設(shè)計與實現(xiàn)［J］.安全與環(huán)境工程，2015，22(3):136-139.LI Xiaojie，YE Chengming，ZHEN Baofeng.Design and implementation of the guarantee system for geological survey safety production based on BeiDou satellite navigation［J］.Safety and Environmental Engineering，2015，22(3):136-139.(in Chinese)

［10］何凱濤，李志忠，汪大明.基于遙感衛(wèi)星和北斗衛(wèi)星的野外地質(zhì)調(diào)查服務(wù)與管理系統(tǒng)設(shè)計綜述［J］.地質(zhì)力學(xué)學(xué)報，2012，18(3):203-212. HE Kaitao，LI Zhizhong，WANG Daming.Overview on the design of the service and management system for field geological survey based on the remote sensing and BeiDou satellites［J］.Journal of Geomechanics，2012，18(3): 203-212.(in Chinese)

［11］伍錦程，王占昌，石小亞.西北區(qū)野外地質(zhì)調(diào)查中北斗衛(wèi)星通訊與定位技術(shù)應(yīng)用研究［J］.地質(zhì)力學(xué)學(xué)報，2012，18(3):282-287.WU Jincheng，WANG Zhanchang，SHIXiaoya.Application of BeiDou satellite communication and positioning technology to the field geological survey in northwestern china［J］.Journal of Geomechanics，2012，18(3):282-287.(in Chinese)

［12］趙春宇.高性能并行GIS中矢量空間數(shù)據(jù)存取與處理關(guān)鍵技術(shù)研究［D］.武漢:武漢大學(xué)，2006.ZHAO chunyu.Studying on the technologies of storage and processing of spatial vector data in high-performance parallel GIS［D］.Wuhan:Wuhan University，2006.(in Chinese)

［13］吳立新，楊宜舟，秦承志，等.面向新型硬件構(gòu)架的新一代GIS基礎(chǔ)并行算法研究［J］.地理與地理信息科學(xué)，2013，29(4):1-8.WU Lixin，YANG Yizhou，QIN Chengzhi，et al.On basic geographic algorithms of new generation GIS for new hardware architectures［J］.Geography and Geo-Information Science，2013，29(4):1-8.(in Chinese)

［14］王占昌，王飛，伍錦程，等.一種靜止軌道地球同步衛(wèi)星數(shù)字尋星方法:中國，CN201410020373［P］.2014-01-06.WANG Zhanchang，WANG Fei，WU Jincheng，et al.A method of digital finding satellite for geosynchronous satellites:China，CN201410020373［P］.2014-01-06.(in Chinese)

［15］Xavier C，Iyengar SS.Introduction to parallel algorithms［M］.USA:John Wiley＆Sons，Inc.，2004.

Parallel signal blind area computing of BeiDou geostationary orbit satellite

GUO Jiateng1，WU Lixin1，2，YANG Yizhou1，LIChaoling3，LIU Shanjun1
(1.Institute of Geo-informatics＆Digital Mine，Northeastern University，Shenyang 110819，China；2.IoT/Perception Mine Research Center，China University of Mining＆Technology，Xuzhou 221008，China；3.Development and Research Center，China Geological Survey，Beijing 100037，China)

In order to improve the computing efficiency of signal blind area for BeiDou geostationary orbit satellites，it requiresmore computing resources in parallel computing environment.According to the analysis on parallel characteristics of the existing resolving principle and algorithm，a novelalgorithm was designed for computing signal blind area of BeiDou geostationary orbitsatellitesbased on elevation angle related dynamic blind influence scope.Based on this algorithm，the parallel computing tasks of signal blind area was divided and arranged by raster data partition.An experimentwas taken for computing the blind area in china based on 59 scene digital elevation model data and 8 processes，and spent about 5 hours.The result shows that the parallel efficiency of the algorithm decreaseswith the increasing process count，but stablymaintains atmore than 96%.Themethod has been integrated as a tool in high performance geographic information system and can obtain good application effect.

BeiDou system；parallel computing；blind area calculation；high performance geographic information system；digital elevation model

TP391

A

1001-2486(2015)05-047-07

10.11887/j.cn.201505008

http://journal.nudt.edu.cn

2015-06-29

國家863計劃資助項目(2011AA120302)；國家自然科學(xué)基金資助項目(41001228)；中央高?；究蒲袠I(yè)務(wù)費資助項目(N140104002)；遼寧省自然科學(xué)基金資助項目(2015020581)

郭甲騰(1980—)，男，安徽桐城人，講師，博士，E-mail:guojiateng@mail.neu.edu.cn