摘要：CEMR（Compact Explicit Multi-path Routing）路由算法即緊湊顯式多路徑路由算法，與MPLS比較，CEMR采用PathID編碼方案，具有較小的信令開銷，并能保證分組轉(zhuǎn)發(fā)不形成環(huán)路。分析表明，該算法支持衛(wèi)星網(wǎng)絡(luò)中的流量負(fù)載平衡，在延時(shí)和丟包性能上具有優(yōu)勢(shì)，適合于高流量負(fù)載衛(wèi)星網(wǎng)絡(luò)。

關(guān)鍵詞：虛擬拓?fù)?；單層衛(wèi)星網(wǎng)；CEMR

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）02-0365-02

基于虛擬拓?fù)涞膯螌有l(wèi)星網(wǎng)路由算法就是根據(jù)衛(wèi)星網(wǎng)運(yùn)行周期性特點(diǎn)，將衛(wèi)星網(wǎng)系統(tǒng)周期劃分為一系列的時(shí)間片段，在每個(gè)時(shí)間片段內(nèi)，衛(wèi)星網(wǎng)拓?fù)涫枪潭ú蛔兊?，衛(wèi)星網(wǎng)拓?fù)涞淖兓话l(fā)生在時(shí)間片切換點(diǎn)上，這樣就可以采用最短路徑算法找到最優(yōu)路徑和備選路徑。

基于虛擬拓?fù)涞膯螌有l(wèi)星網(wǎng)路由算法有很多種，比較成熟的有DT-DVTR算法、FSA算法、CEMR算法、ELB路由算法等，在端到端延時(shí)和分組丟失率方面，CEMR算法具有明顯的性能優(yōu)勢(shì)。

1 CEMR路由算法簡(jiǎn)介

CEMR路由算法是研究移動(dòng)衛(wèi)星網(wǎng)絡(luò)中多路徑路由問題的一種算法。它以單層類銥星（Iridium-like）極軌衛(wèi)星星座為場(chǎng)景，該星座由6個(gè)傾角接近90°的軌道平面組成，每個(gè)軌道平面均勻分布有11顆衛(wèi)星。同一軌道平面內(nèi)的星間雙向鏈路稱為軌內(nèi)星間鏈路（Inter-plane ISL），軌內(nèi)星間鏈路可以一直保持著，其傳播延時(shí)總是固定的。軌間星間鏈路的長(zhǎng)度隨著衛(wèi)星的運(yùn)動(dòng)是變化的，所以隨著衛(wèi)星的運(yùn)動(dòng)，軌間星間鏈路的傳播延時(shí)始終在變化。

CEMR算法通過動(dòng)態(tài)虛擬拓?fù)溲芯客負(fù)鋭?dòng)態(tài)性問題，衛(wèi)星網(wǎng)絡(luò)建模在一個(gè)系統(tǒng)周期T上，時(shí)間離散的衛(wèi)星位置的快照。系統(tǒng)周期T可以分成n個(gè)時(shí)間間隔Δt [t0，t1]，[t1，t2]，…，[tn-1，tn]。在一個(gè)時(shí)間間隔Δt內(nèi)，拓?fù)淇梢赃M(jìn)一步用圖G描述。鏈路狀態(tài)改變僅發(fā)生在離散時(shí)間點(diǎn)t0，t1，t2，…，tn。時(shí)間間隔Δt足夠小，以考慮每條星間鏈路的代價(jià)在整個(gè)時(shí)間間隔內(nèi)是恒定的。

2 CEMR路由算法原理

CEMR路由算法分成3個(gè)部分：路由發(fā)現(xiàn)、路由維護(hù)以及流量分配。

與傳統(tǒng)路由算法僅將傳播延時(shí)作為路由代價(jià)度量不同，CEMR路由算法采用星間鏈路長(zhǎng)度和流量負(fù)載兩個(gè)因素影響的延時(shí)作為代價(jià)度量，而這兩個(gè)對(duì)路由性能有重要影響的參數(shù)是動(dòng)態(tài)改變的。第一個(gè)參數(shù)是傳播延時(shí)Tp。第二個(gè)參數(shù)是排隊(duì)延時(shí)Tq。假設(shè)在時(shí)刻t一個(gè)分組進(jìn)入一個(gè)給定的鏈路隊(duì)列，其期望隊(duì)列延時(shí)Texp能夠通過下面的公式計(jì)算得到：

4 CEMR路由算法總結(jié)

CEMR路由算法使用PathID全局路徑標(biāo)識(shí)實(shí)現(xiàn)衛(wèi)星網(wǎng)絡(luò)的多路徑路由，流量分配到多個(gè)可行路徑，降低了衛(wèi)星網(wǎng)絡(luò)延時(shí)，提高了吞吐量，實(shí)現(xiàn)了負(fù)載均衡功能。PathID驗(yàn)證算法確保了分組轉(zhuǎn)發(fā)一致性，分析結(jié)果表明，CEMR路由算法提出的時(shí)間早，技術(shù)成熟，性能比較完善，在延時(shí)和丟包率方面相對(duì)于其他傳統(tǒng)算法具有更好的性能。

參考文獻(xiàn)：

[1] 王汝傳，饒?jiān)?，鄭彥，?衛(wèi)星通信網(wǎng)路由技術(shù)及其模擬[M].北京：人民郵電出版社，2010（4）：61-65.

[2] 陳建州，王路，劉立祥，等.雙層星座中負(fù)載均衡路由協(xié)議研究[J].宇航學(xué)報(bào)，2012（6）：746-753.

[3] 朱軍，饒?jiān)?，李紹穩(wěn)，等.面向LEO衛(wèi)星網(wǎng)的輕量級(jí)按需QoS源路由算法[J].計(jì)算機(jī)科學(xué)，2012（7）：64-68.

[4] 楊力，楊校春，潘成勝.一種GEO/LEO雙層衛(wèi)星網(wǎng)絡(luò)路由算法及仿真研究[J].宇航學(xué)報(bào)，2012（10）：1445-1452.

[5] 朱軍，饒?jiān)?，傅雷揚(yáng)，等.基于移動(dòng)代理的衛(wèi)星網(wǎng)路由性能研究[J].計(jì)算機(jī)工程與應(yīng)用，2012（3）：69-72.