毛騰躍，徐正全 ，朱容波 ，侯 睿

(1．中南民族大學計算機科學學院 武漢430074；2．武漢大學測繪遙感信息工程國家重點實驗室 武漢430079)

1 引言

衛(wèi)星網絡無縫覆蓋的優(yōu)勢可以彌補Internet的不足，使其成為Internet的延伸，為用戶提供各類互聯(lián)網應用、寬帶多媒體數據及個人移動通信等服務。目前的衛(wèi)星網絡存在時延高、帶寬利用率低及通信成本高、服務融合能力差的缺陷，難以滿足用戶廉價和方便的服務需求。下一代衛(wèi)星網絡只有利用地面Internet成熟的IP技術，以IP為核心思想，和地面 Internet無縫對接[1]，實現天地一體化的Internet，才能突破發(fā)展的瓶頸。

衛(wèi)星網絡與地面互聯(lián)網相比，有許多獨特的地方。衛(wèi)星網絡是一種高速移動網絡，網絡拓撲結構頻繁地周期性變化，星間鏈路（inner-satellitelink,ISL）和星地鏈路頻繁切換，而地面的Internet網絡拓撲結構相對穩(wěn)定。還有星上資源和能量受限、信道誤碼率遠大于地面網絡、衛(wèi)星空間分布稀疏、節(jié)點間距離遙遠等，決定了地面Internet的路由協(xié)議不適用于衛(wèi)星網絡。因此，需要結合衛(wèi)星運動的規(guī)律性和周期性等特點，設計與地面Internet不同的路由協(xié)議。

2 路由技術面臨的挑戰(zhàn)

衛(wèi)星網絡是由許多處于不同軌道運行的衛(wèi)星組成，包括各種類型的星座，如GEO(geostationaryearthorbit)、MEO（mediumearthorbit）、LEO(lowearthorbit)，衛(wèi) 星 的 高 速 移動導致星間鏈路和星地鏈路頻繁切換，衛(wèi)星網絡拓撲結構頻繁地周期性變化。而地面Internet網絡拓撲結構相對穩(wěn)定，如采用地面Internet的路由協(xié)議，由于網絡拓撲快速變化，拓撲信息很快過期而且需要經常刷新，會導致處理拓撲信息的開銷過于龐大，衛(wèi)星難以承受IP路由所帶來的計算和存儲開銷，因而地面Internet的路由協(xié)議不適用于衛(wèi)星網絡。網絡拓撲快速變化和鏈路狀態(tài)信息實時變化，要求衛(wèi)星網絡的路由策略具有高穩(wěn)定性和快速收斂的能力。

在衛(wèi)星網絡路由算法的設計中，衛(wèi)星資源的嚴重受限給路由策略帶來了重大挑戰(zhàn)。星載設備的設計不同于地面設備，嚴格受到功率、重量、尺寸的限制，因此導致星上設備的運算能力、存儲容量均受到限制，要求星上可實現的路由算法簡單，對存儲器的容量要求不能過高[2]。由于地面人口密度分布得不均勻，人口密度大的地區(qū)對流量的需求遠大于人口稀少的地區(qū)，需求不對稱和流量動態(tài)變化對路由算法提出了如何平衡流量的挑戰(zhàn)。

星間鏈路、星地上下行鏈路頻繁切換以及衛(wèi)星鏈路的高傳播時延特點，會導致時延增加以及時延抖動，特別是對實時要求較高的多媒體應用來說，嚴重影響QoS。而QoS苛刻的受限條件給QoS路由策略的設計提出了嚴峻的挑戰(zhàn)。

衛(wèi)星網絡拓撲的快速變化和鏈路狀態(tài)信息的實時變化，要求衛(wèi)星網絡的路由策略具有高穩(wěn)定性和快速收斂的能力?？臻g系統(tǒng)的能量供給受限，星上設備維護不便，因此要求路由策略具備低功耗和高可靠性運行的能力[3]。需求不對稱和流量動態(tài)變化要求路由策略具有動態(tài)的平衡性。實時多媒體應用對QoS路由策略的需求等因素導致路由策略極其復雜，作為IP網絡中的核心技術，路由問題面臨巨大的挑戰(zhàn)，路由問題一直得到了極大的關注，成為持續(xù)的研究熱點。

3 路由策略研究現狀

由于衛(wèi)星網絡存在諸多的特性，地面Internet中廣泛使用的路由策略不能直接應用到衛(wèi)星網絡中。目前關于衛(wèi)星網絡路由策略的研究非常多，都是結合衛(wèi)星網絡的某個特性或者某些特性而實現的[4]，如利用衛(wèi)星拓撲結構頻繁變化但具有周期性的特性提出的基于星座周期的路由策略,依據流量動態(tài)變化、需求不對稱提出的實現負載均衡的路由策略等，具體分類見表1。

3.1 基于星座周期的路由

預先精確計算每對衛(wèi)星間的路徑，把動態(tài)拓撲結構規(guī)劃成按時間段分隔的一系列連續(xù)的靜態(tài)拓撲結構，在每個相對很短的間隔內，衛(wèi)星的動態(tài)拓撲結構可模型化為固定拓撲，從而在靜態(tài)拓撲結構的基礎上提供優(yōu)化的路由。Chang[5]提出的 FSA（finitestateautomataroute）算法對 LEO衛(wèi)星網絡拓撲結構按固定時間段進行離散處理，把離散化后的LEO衛(wèi)星網絡拓撲結構對應有限狀態(tài)機。FSA算法把LEO衛(wèi)星網絡中ISL鏈路分配問題與路由問題相結合，優(yōu)化目標是ISL利用率，通過動態(tài)規(guī)劃中的退火算法來解決鏈路分配與路由分配的聯(lián)合優(yōu)化問題。其優(yōu)點是對網絡資源的最優(yōu)化使用，但由于不是按最短路徑原則選擇路由，因此所選路由時延指標不能被保證，而且計算復雜性過高。Werner[6]提出的動態(tài)虛拓撲離散狀態(tài)路由（time dynamicvirtualtopologyrouting，T-DVTR）算法根據衛(wèi)星網絡運行的周期性，把衛(wèi)星系統(tǒng)周期劃分為多個時間間隔，時間間隔適度小，在該期間內各個ISL的代價可以認為不變。ISL的連通和斷開僅發(fā)生在離散時間點，經過離散化處理后，動態(tài)變化的LEO衛(wèi)星網絡拓撲結構表示為一系列靜態(tài)拓撲結構周期性重復出現。通過典型最短路由算法計算路由，將鏈路切換次數作為優(yōu)化目標。

表1 路由策略類型

由于基于星座周期的路由策略可以按照星座運行的周期性預先計算出路由，路由計算通常在地面預先集中處理，衛(wèi)星不需要實時計算，衛(wèi)星在時間間隔的分隔點修改路由表。它的優(yōu)點是路由協(xié)議的開銷小，對衛(wèi)星的處理能力要求不高，而其缺點是對通信流量變化、鏈路擁塞以及故障等實時情況的適應性較差。

3.2 基于鏈路切換的路由

衛(wèi)星高速移動導致星間鏈路、星地上下行鏈路頻繁切換，如果每一次鏈路切換需要重建路由的話，會導致時延增加以及時延抖動，直接影響QoS，特別是對實時要求較高的多媒體應用來說，QoS的過度下降是不能容忍的。為避免QoS的下降，一些基于鏈路切換的路由策略在路由選擇中，盡量選擇鏈路切換次數少的路由，通過星間鏈路的切換率或者星地上下行鏈路的切換率來保證QoS。參考文獻[7]中提出的概率路由協(xié)議（probabilisticroutingprotocol）在新連接路徑建立階段，通過去掉在其通信生存期內或衛(wèi)星切換前可能經歷鏈路切換的ISL，在這個新形成的衛(wèi)星網絡拓撲結構的基礎上計算路由。參考文獻[8]中通過收集星間鏈路的生存周期，選擇生存周期最長的星間鏈路作為路由路徑。參考文獻[9]中提出了一個切換次數最少的自適應路由方案，其依據的原則是在保證一定QoS的基礎上，最大限度地減少切換次數。參考文獻[10]中提出了一種鏈路切換的概率路由策略，滿足一定的QoS時延約束。

3.3 基于路徑優(yōu)化的路由

同地面互聯(lián)網相比，衛(wèi)星網絡的節(jié)點間距離遠，導致傳輸時延較長，衛(wèi)星網絡的時延主要取決于傳輸時延。因此，選擇路徑較短、跳數較少的路由可以盡可能地縮小傳輸時延。Ekici[11]提出的分布式路由算法以傳輸時延最小化作為約束目標，根據網絡狀況實時計算并選擇新的路由，適應性強，同時存儲空間很小，節(jié)省了星上資源。但該類路由通常要求網絡拓撲結構非常規(guī)則,只適用于衛(wèi)星數目較多且分布十分規(guī)則的衛(wèi)星系統(tǒng)，而且路由計算利用局部狀態(tài)信息，對每個數據分組進行局部最優(yōu)轉發(fā)，路由不一定全局最優(yōu)化。參考文獻[12]中通過Dijkstra算法尋求最小跳數，同時以最大吞吐量作為約束條件。

3.4 基于負載均衡的路由

由于地面人口密度分布的不均勻，導致人口密度大的地區(qū)對流量的需求遠大于人口稀少的地區(qū)，需求不對稱和流量動態(tài)變化對路由算法提出了如何平衡流量的挑戰(zhàn)。參考文獻[13]中提出的流量偏差（flowdeviation，FD）算法從整個網絡中收集信息，通過指定的中央節(jié)點執(zhí)行FD算法，能最大限度地減少傳播時延，流量動態(tài)變化的性能優(yōu)于自適應的Dijkstra算法。參考文獻[14]提出了一個明確的負載平衡（explicitloadbalancing，ELB）路由策略，在多跳的 NGEO衛(wèi)星星座中，能保證流量的有效分配。參考文獻[15]中提出了分布式負載感知路由 （distributedload-awarerouting，DLAR）協(xié)議，采用分布式的方法處理復雜的衛(wèi)星系統(tǒng)，并同時提供了一個逐跳機制分離流量負荷，以解決近極地地區(qū)發(fā)生的流量擁塞問題。

3.5 基于QoS的路由

QoS指標表現在多個方面，如端到端的時延、帶寬、吞吐量、分組丟失率等。許多研究是在某個QoS需求上實現路由策略，或者在不同的QoS指標需求獲得平衡的基礎上實現路由策略。Jianjun[16]提出一個明確的緊湊型多路徑路由算法，基于成本度量的指標，涉及傳播和排隊時延。Akyildiz[17]提出的多播路由算法，從基于端到端時延的QoS需求上進行優(yōu)化。Tasi[18]提出的基于動態(tài)拓撲網絡的成本效益的路由選擇算法從鏈路的利用率上進行優(yōu)化。Taleb[19]提出的NGEO寬帶衛(wèi)星網絡中的IP流量負荷分布算法中，基于流量負載的信息，網絡流量得到了更好的利用和平衡。Cetin[20]將端到端時延和LEO衛(wèi)星網絡的吞吐量再優(yōu)化相結合，但沒有提及如何添加更多的QoS需求。Fei[21]采用啟發(fā)式算法，所有的QoS要求理論上可以在一個計算中，在QoS需求之間的平衡上能夠獲得良好的性能。

3.6 基于多層網絡結構的路由

與單層LEO網絡相比，多層網絡在路由策略上表現出更大的靈活性，盡管網絡結構復雜，但具有更加對稱的星座結構，星間鏈接更多，路由選擇的余地更大。目前對多層網絡結構的路由研究成為路由策略研究的一個熱點。參考文獻[22]中提出了一個SOS(satellite-over-satellite)網絡，通過LEO和MEO進行雙層組網，低層LEO衛(wèi)星發(fā)送ISL狀態(tài)信息給上層MEO衛(wèi)星，上層MEO衛(wèi)星根據這些信息，向在覆蓋范圍內的低層LEO衛(wèi)星分發(fā)本地路由信息，算法的優(yōu)點是可以減少路由的跳數，資源消耗較小。參考文獻[23]中提出了由GEO、LEO和高空平臺（highaltitude platforms，HAP）組成的3層網絡結構，其中GEO衛(wèi)星充當骨干路由器，鏈路狀態(tài)信息發(fā)送到固定的地面網關處理，網關將成型后的域內路由表上傳到GEO層衛(wèi)星，再由GEO層衛(wèi)星將這些路由信息洪泛發(fā)給LEO和高空平臺。參考文獻[24]中提出的SGRP（satellite grouping and routing protocol）基于LEO/MEO衛(wèi)星網絡，在每個快照期，根據LEO衛(wèi)星覆蓋的區(qū)域將其分組，每一個組有一個MEO管理。MEO衛(wèi)星根據從LEO層收到的鏈路狀態(tài)信息，計算其低軌成員的最小時延路徑。參考文獻[25]在LEO/MEO衛(wèi)星網絡中，基于時隙劃分，提出了分層分布式QoS路由協(xié)議，設計了自適應帶寬受限最小時延路徑算法，滿足時延和帶寬的要求，能有效計算路由。參考文獻[26]中基于GEO/MEO/LEO 3層網絡結構，提出了一種多QoS路由算法，相比SPF（shortest path first）路由算法，它能夠較好地滿足QoS的要求。

3.7 多播路由

與地面網絡相比，衛(wèi)星網絡具有傳播時延長、上下行鏈路不對稱、鏈路誤碼率高、拓撲結構頻繁變化、能量受限的特點。傳統(tǒng)的地面網絡多播算法，如距離向量多播路由協(xié)議(distance vector multicast routing protocol，DVMRP)、開放式多播最短路徑優(yōu)先 (multicast open shortest path first，MOSPF)等只適用于固定或者拓撲緩慢變化的網絡中，而衛(wèi)星高速移動；核基樹(core based tree，CBT)等協(xié)議在高動態(tài)網絡中會產生很大的開銷，而衛(wèi)星能量和處理能力受限。這些決定了傳統(tǒng)的地面網絡多播算法不能應用于衛(wèi)星網絡，因此需要設計高效和專用于衛(wèi)星網絡的多播算法。

由于多播算法具有極大的挑戰(zhàn)性，近年來多播路由成為下一代衛(wèi)星網絡的一個研究熱點。如采用啟發(fā)式算法解決多播-路由、結合多播-路由和QoS問題、結合多播-路由和安全問題、基于多層網絡下多播-路由的研究。參考文獻[27]中的 MRA(multicast routing algorithm)，其源和中間衛(wèi)星節(jié)點采用數據報路由算法為每個目的衛(wèi)星節(jié)點確定下一跳路由方向，端到端傳播時延較小，適合實時多媒體業(yè)務。參考文獻[28]提出了一種基于單向衛(wèi)星鏈路的可靠多播-通信協(xié)議，該協(xié)議命名為Reliable Multicast over Undirectional Satellite Link(RMUS)。RMUS協(xié)議主要針對衛(wèi)星上下行鏈路不對稱的問題，提供了特殊的差錯恢復機制和擁塞控制機制。參考文獻[29]中提出了基于遺傳算法的QoS多播-路由策略，通過將多播-路由策略加入支持QoS的增強版核心樹協(xié)議中，測試遺傳算法的效率。

4 結束語

路由策略是下一代衛(wèi)星網絡的核心問題，目前研究的熱點主要集中在QoS路由、多播-路由以及多層網絡結構下的路由。大量的研究工作基于某種或者某些特定條件，解決了特定條件下的路由問題，但離實際應用可能還存在差距。因此，結合衛(wèi)星的移動性和拓撲結構動態(tài)變化的特點，設計具有通用性的路由策略是未來衛(wèi)星網絡需要解決的關鍵技術。另外，QoS問題在地面Internet始終存在，針對衛(wèi)星網絡更為苛刻的受限條件將QoS問題和路由結合設計QoS路由策略，這將是下一代衛(wèi)星網絡路由技術未來非常重要的研究方向。

1 Taleb T,Hadjadj-Aoul Y,Ahmed T.Challenges,opportunities,and solutions for converged satellite and terrestrial networks.Wireless Communications,2011,18(1):46～52

2 晏堅.低軌衛(wèi)星星座網絡IP路由技術研究.清華大學博士學位論文，2010

3 周云暉.衛(wèi)星網絡QoS路由協(xié)議及其優(yōu)化理論研究.清華大學博士學位論文，2007

4 Alagoz F,Korcak O,Jamalipour A.Exploring the routing strategies in next-generation satellite networks. Wireless Communications,2007,14(3):79～88

5 Chang H S.Performance comparison of optimal routing and dynamic routing in low-earth orbit satellite networks.Atlanta,GA,1996

6 Werner M,Delucchi C,Vogel H.ATM-based routing in LEO satellite networks with inter-satellite links.IEEE Journal on Selected Areas in Communications,1997,15(1):69～81

7 Ercetin O,Krishnamurthy S,Dao S,et al.A predictive QoS routing scheme for broadband LEO satellite networks.IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,2000(2):1064～1074

8 Nguyen H N,Jukan A.An approach to QoS-based routing for LEO satellite networks.Global Telecommunications Conference,2000(2):1114～1118

9 Chen J,Jamalipour A.An adaptive path routing scheme for satellite IP networks.International Journal of Communication Systems,2003,16(1):5～21

10 Chen C.A QoS-based routing algorithm in multimedia satellite networks.IEEE 58th Vehicular Technology Conference,2004(4):2703～2707

11 Ekici E,Akyildiz I F,Bender M D.A distributed routing algorithm for datagram traffic in LEO satellite networks.IEEE/ACM Transactions on Networking,2001,9(2):137～147

12 Sun J,Modiano E.Routing strategies for maximizing throughput in LEO satellite networks.Selected Areas in Communications,2004,22(2):273～286

13 Gragopoulos I,Papapetrou E,Pavlidou F.Perormance study of adaptive routing algorithms for LEO satellite constellations under self-similar and poisson traffic.Space Communications,2000,16(1):15～22

14 Taleb T,Mashimo D,Jamalipour A,et al.ELB:an explicit load balancing routing protocol for multi-hop NGEO satellite constellations.Global Telecommunications Conference,2006,26(8):1～5

15 Papapetrou E.Distributed load-aware routing in LEO satellite networks.Global Telecommunications Conference,2008

16 Jianjun B.Compact explicit multi-path routing for LEO satellite network.High Performance Switching and Routing,2005

17 Akyildiz I F,Ekici E.A novel routing algorithm for multilayered satellite IP networks.Transactions on Networking,2002,10(3):411～424

18 Kuang T,Ma R P.A cost-effective routing alternative for large space based dynamic topology networks.Military Communications Conference,1995(2):682～686

19 Taleb T.IP traffic load distribution in NGEO broadband satellite networks.Computer and Information Science,2005(3733):113～123

20 ErCetin O.Provision of guaranteed service in broadband LEO satellite networks.Computer Networks,2002,39(1):61～77

21 Fei L,Naixue X,Athanasios V,et al.A sustainable heuristic QoS routing algorithm for pervasive multi-layered satellite wireless networks.Wireless Networks,2010,16(6):1657～1673

22 Lee J,Kang S.Satellite over satellite (SOS)network:a novel architecture for satellite network.Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies,Mar 2000

23 Dash D S,Durresi A,Jain R.Routing of VoIP traffic in multilayered satellite networks.Proceedings of SPIE Performance and Control of Next-Generation Communications Networks,2003

24 Chen C,Ekici E.A routing protocol for hierarchical LEO/MEO satellite IP networks.Wireless Networks,2005,11(4):507～523

25 Zhou Y H,Sun F C,Zhang B.A hierarchical and distributed QoS routing protocol for two-layered satellite networks.Computational Engineering in Systems Applications,IMACS Multiconference on Beijing,Oct 2006

26 Fei L.A multi-QoS objective optimization routing for hierarchical satellite networks.Education Technology and Computer Science,2010 Second International Workshop on Wuhan,March 2010

27 Ekici E,Akyildiz I F,Bender M D.A multicast routing algorithm for LEO satellite IP networks.IEEE/ACM Transactions on Networking,2002,10(2):183～192

28 Basu P,Kanchanasut K.A reliable multicast protocol for unidirectional satellite link.IEEE 2003 Symposium on Applications and Internet(SAINT’03),2000

29 Floriano D R.An enhanced QoS CBT multicast routing protocol based on genetic algorithm in a hybrid HAP-satellite system.Computer Communications,2007,30(16):3126～3143