[發(fā)明專利]基于多重性能自適應(yīng)配對堆的時間演化圖路由算法

在審

• 申請?zhí)枺?/td>: 201410429748.3
• 申請日: 2014-08-28
• 公開（公告）號: CN104243310A
• 公開（公告）日: 2014-12-24
• 發(fā)明（設(shè)計）人: 劉崇華;姜竹青;何善寶;李振東;王宇鵬;王雪旸;黃承愷;楊玉瑩;劉欣萌;李超
• 申請（專利權(quán)）人: 北京空間飛行器總體設(shè)計部;北京郵電大學(xué)
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04W40/02;H04W84/06
• 代理公司: 天津盛理知識產(chǎn)權(quán)代理有限公司 12209
• 代理人: 王利文

1.一種基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于包括以下步驟：

步驟1、構(gòu)造一個按照通信時隙表分時隙通信的中軌道衛(wèi)星網(wǎng)絡(luò)系統(tǒng)；

步驟2、根據(jù)24顆衛(wèi)星的通信時隙表構(gòu)造中軌道衛(wèi)星網(wǎng)絡(luò)系統(tǒng)的時間演化圖模型；

步驟3、采用多重性能自適應(yīng)配對堆優(yōu)化迪杰斯特拉最短路徑算法的數(shù)據(jù)存儲結(jié)構(gòu)；

步驟4、在時間演化圖模型中應(yīng)用優(yōu)化的迪杰斯特拉最短路徑算法計算最優(yōu)路由。

2.根據(jù)權(quán)利要求1所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述步驟1構(gòu)建方法為：采用STK仿真環(huán)境構(gòu)造Walker星座及其軌道模型，利用STK仿真環(huán)境生成軌道數(shù)據(jù)信息，將軌道數(shù)據(jù)信息導(dǎo)入OPNET應(yīng)用在中軌道衛(wèi)星網(wǎng)絡(luò)系統(tǒng)中，使分時隙通信的中軌道衛(wèi)星網(wǎng)絡(luò)系統(tǒng)中的24顆衛(wèi)星按照其既定軌道正常運轉(zhuǎn)。

3.根據(jù)權(quán)利要求2所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述Walker星座為Walker-24/3/1結(jié)構(gòu)星座群，每個衛(wèi)星節(jié)點內(nèi)配置應(yīng)用層、傳輸層、網(wǎng)絡(luò)層、鏈路層和物理層；每個衛(wèi)星節(jié)點配置一對定向收發(fā)天線，在某一方向上增益為200分貝，在其他方向上增益均為0；每個衛(wèi)星的收發(fā)天線按照通信時隙表自動轉(zhuǎn)換指向并與其他衛(wèi)星建鏈通信。

4.根據(jù)權(quán)利要求1所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述步驟2的時間演化圖模型為一張給定圖的β個子圖的有序序列，每一個子圖對應(yīng)于網(wǎng)絡(luò)中某個時隙的網(wǎng)絡(luò)拓?fù)?；每個衛(wèi)星被視為網(wǎng)絡(luò)節(jié)點，衛(wèi)星之間的連接被視為邊，整個衛(wèi)星網(wǎng)絡(luò)被視為一個圖，在構(gòu)建時，根據(jù)通信時隙表將衛(wèi)星之間連接存在的時間間隔標(biāo)注在相對應(yīng)的邊上即可。

5.根據(jù)權(quán)利要求1所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述配對堆由配對堆節(jié)點構(gòu)成，每一個節(jié)點包含隊列元素和前驅(qū)指針、左孩子指針和右孩子指針；所述配對堆包括合并、插入、減少關(guān)鍵元素和刪除最小元素操作。

6.根據(jù)權(quán)利要求1所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述步驟3的具體處理過程為：

(1)初始化源節(jié)點信息并構(gòu)造一個配對堆節(jié)點作為根節(jié)點，添加根節(jié)點的指針；

(2)根據(jù)根節(jié)點的信息判斷算法是否結(jié)束，如果沒有結(jié)束，遍歷當(dāng)前節(jié)點的相鄰節(jié)點并累積其開銷；如果結(jié)束，則執(zhí)行步驟(5)；

(3)如果相鄰節(jié)點的配對節(jié)點為空，生成一個并從相鄰節(jié)點中添加信息，隨后構(gòu)造該節(jié)點與堆節(jié)點之間的指針關(guān)系；

(4)利用當(dāng)前節(jié)點的最小權(quán)重與相鄰節(jié)點來更新配對堆節(jié)點的信息，并調(diào)整堆結(jié)構(gòu)，返回步驟(2)；

(5)根據(jù)最終節(jié)點的堆節(jié)點信息獲得路徑結(jié)果，并且釋放所有指針內(nèi)存空間。

7.根據(jù)權(quán)利要求6所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述步驟(2)累積開銷按下式計算：

開銷＝Σα·時間+β·跳數(shù)+δ·延遲+γ·其它

其中，α、β、δ、γ分別為時間、跳數(shù)、延遲以及其它所需性能參數(shù)的權(quán)重值；所述的權(quán)重值根據(jù)實際需要進(jìn)行配置，或者根據(jù)衛(wèi)星網(wǎng)絡(luò)運行過程中的吞吐量、擁塞、丟包率、延遲進(jìn)行自適應(yīng)調(diào)整。

8.根據(jù)權(quán)利要求1所述的基于多重性能自適應(yīng)配對堆的時間演化圖路由算法，其特征在于：所述步驟4具體處理過程為：在初始化時，對源點S有最早到達(dá)時間d(s)＝t_now，而對其它所有節(jié)點有d(u)＝∞；此時，源點S是最小堆Q中的唯一根節(jié)點；然后，當(dāng)最小堆Q非空時，其根節(jié)點被取出并被分配給堆Q的根x，并將其刪除；接下來，如果x有一個或者一些鄰節(jié)點，為其每一個鄰居v計算第一個有效邊的時間是否大于等于當(dāng)前時間，如果它不存在于堆Q中，將v插入堆Q；隨后，更新d(v)及其關(guān)鍵元素；當(dāng)x的所有鄰節(jié)點均被遍歷后，更新堆Q，關(guān)閉節(jié)點x；最后，將x插入最先到達(dá)路徑樹T中，如果堆Q中不存在任何節(jié)點，整個算法結(jié)束，從而獲得了從源點S到其它所有節(jié)點的最先到達(dá)路徑樹T。