[發(fā)明專利]一種基于地理位置的背壓鏈路調(diào)度方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410391015.5
• 申請(qǐng)日: 2014-08-08
• 公開（公告）號(hào): CN104202260A
• 公開（公告）日: 2014-12-10
• 發(fā)明（設(shè)計(jì)）人: 官權(quán)升;黎蒙
• 申請(qǐng)（專利權(quán)）人: 華南理工大學(xué)
• 主分類號(hào): H04L12/863
• 分類號(hào): H04L12/863
• 代理公司: 廣州市華學(xué)知識(shí)產(chǎn)權(quán)代理有限公司 44245
• 代理人: 蔡茂略

技術(shù)領(lǐng)域

本發(fā)明涉及通信網(wǎng)絡(luò)的調(diào)度與路由技術(shù)領(lǐng)域，特別涉及一種基于地理位置的背壓鏈路調(diào)度方法。

背景技術(shù)

在排隊(duì)網(wǎng)絡(luò)中，背壓算法能在保證網(wǎng)絡(luò)穩(wěn)定性的前提下使得網(wǎng)絡(luò)吞吐量最大化，并且能有力的解決整體網(wǎng)絡(luò)參數(shù)條件隨時(shí)間不斷變化的情況。

由于近幾年來頻譜帶寬資源的缺乏，背壓算法得到了廣泛的關(guān)注。基于動(dòng)態(tài)的資源配置和路徑選擇，背壓算法能夠通過擁塞梯度實(shí)現(xiàn)在多跳網(wǎng)絡(luò)中的傳輸。

但是傳統(tǒng)的背壓算法很可能導(dǎo)致較大的端到端延遲，尤其是在網(wǎng)絡(luò)負(fù)載比較小的時(shí)候這一弊端體現(xiàn)的更加明顯。因?yàn)樵诰W(wǎng)絡(luò)負(fù)載較小時(shí)，背壓算法需要搜索很多不必要的路徑來保持網(wǎng)絡(luò)的穩(wěn)定性。考慮一種極端條件環(huán)境：只有一個(gè)數(shù)據(jù)包進(jìn)入該網(wǎng)絡(luò)。由于沒有已經(jīng)成型的指向目的節(jié)點(diǎn)壓力梯度，該數(shù)據(jù)包會(huì)隨機(jī)地選擇路徑，在網(wǎng)絡(luò)中漫步，并且極有可能永遠(yuǎn)都到達(dá)不了目的節(jié)點(diǎn)。該算法的另一個(gè)缺點(diǎn)是：背壓算法完全忽視目的節(jié)點(diǎn)信息的特點(diǎn)導(dǎo)致了路徑選擇具有一定的盲目性，可能會(huì)造成路由環(huán)路或選擇了不必要的長路徑等。

因而在后續(xù)的背壓算法的研究過程中，如何在保證最大吞吐量和網(wǎng)絡(luò)穩(wěn)定性的基礎(chǔ)上一直以來都是研究的重點(diǎn)。

目前關(guān)于背壓算法的研究有以下幾點(diǎn)：第一，用后進(jìn)先出隊(duì)列管理算法代替先進(jìn)先出隊(duì)列管理算法來降低時(shí)延；第二，在不影響網(wǎng)絡(luò)容量的條件下，將最短路徑轉(zhuǎn)化為背壓算法中的路徑權(quán)值，從而達(dá)到減少端到端延時(shí)的目標(biāo)；第三，對(duì)每一個(gè)傳輸數(shù)據(jù)流計(jì)算最佳路徑長度，以此來減少平均的端到端延時(shí)，并在背壓算法中使用該值作為路徑上限來調(diào)度數(shù)據(jù)包的傳輸。

這些方法的合理性已經(jīng)被證明，能夠在保證整體網(wǎng)絡(luò)吞吐量最大化并且足夠穩(wěn)定的條件下，減少無線網(wǎng)絡(luò)端到端的平均延時(shí)。但是，隊(duì)列管理的方法并沒有利用目的節(jié)點(diǎn)的信息，還存在路由環(huán)路的問題；對(duì)路徑的計(jì)算需要在網(wǎng)絡(luò)中交換消息，帶來額外開銷。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服現(xiàn)有技術(shù)的缺點(diǎn)與不足，提供一種基于地理位置的背壓鏈路調(diào)度方法。

本發(fā)明的目的通過以下的技術(shù)方案實(shí)現(xiàn)：

一種基于地理位置的背壓鏈路調(diào)度方法，包含以下順序的步驟：

S1.建立隊(duì)列模型：檢測各節(jié)點(diǎn)及個(gè)鏈路的狀態(tài)，網(wǎng)絡(luò)的每個(gè)節(jié)點(diǎn)將不同目的節(jié)點(diǎn)的數(shù)據(jù)包歸為不同的緩存隊(duì)列中，并計(jì)算每個(gè)隊(duì)列的數(shù)據(jù)包累積數(shù)量，即積壓；

S2.選擇每條鏈路的最優(yōu)目的節(jié)點(diǎn)：通過節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離向量加權(quán)的緩存積壓，求出使鏈路加權(quán)積壓差最大的目的節(jié)點(diǎn)，該目的節(jié)點(diǎn)即為最優(yōu)目的節(jié)點(diǎn)；所述節(jié)點(diǎn)到目的節(jié)點(diǎn)的距離向量，首先通過已有定位系統(tǒng)獲取節(jié)點(diǎn)及目的節(jié)點(diǎn)的位置信息，然后計(jì)算得到；

S3.鏈路調(diào)度：基于加權(quán)網(wǎng)絡(luò)吞吐量的最大化的原則計(jì)算最優(yōu)網(wǎng)絡(luò)傳輸速率矩陣；

S4.鏈路傳輸速率的選擇：對(duì)于給定的速率傳輸速率矩陣，在已確定的鏈路上傳輸最優(yōu)目的節(jié)點(diǎn)數(shù)據(jù)包時(shí)，其傳輸速率的值為該鏈路的最大可能的傳輸速率值。

步驟S2中，所述的鏈路加權(quán)積壓差通過以下公式確定：