基於信道公平分配的擁塞控制方法
2023-06-06 00:17:16 3
基於信道公平分配的擁塞控制方法
【專利摘要】本發明公開了一種基於信道公平分配的擁塞控制方法。首先，根據已獲取上遊鄰居節點的數據估算其隊列增長速率和數據包的平均傳輸延時。然後，根據估算的隊列增長速率計算其上遊鄰居節點的隊列長度，進一步計算節點本身及其上遊鄰居節點隊列的總長度，並結合數據包的平均傳輸延時來執行擁塞檢測。如果發生擁塞，則將網絡擁塞程度分級(即擁塞度)，並確定擁塞解除周期的長短，給節點公平分配佔用信道時間。最後，根據擁塞度，執行擁塞解除算法，從而解除或緩解擁塞；如果沒有擁塞，則不做處理。本發明提高了信道使用的公平性，並能有效減少碰撞、降低丟包率和增加吞吐量。
【專利說明】基於信道公平分配的擁塞控制方法
【技術領域】
[0001] 本發明涉及通信領域，更具體的涉及一種基於信道公平分配的擁塞控制方法。
【背景技術】
[0002] 在無線傳感器網絡（Wireless Sensor Network, WSN)中，多對一的通信方式、無 線帶寬資源受限和無線鏈路的相互幹擾等特點，導致無線傳感器網絡極易出現擁塞。網絡 擁塞容易引起緩存溢出，導致大量數據分組丟失，增加網絡排隊延遲，並消耗大量的額外能 量。同時，網絡擁塞還會引發訪問衝突，降低鏈路的利用率和網絡的吞吐量。因此，高效實 時地檢測和解除擁塞已成為保證無線傳感器網絡服務質量的熱門話題。
[0003] 擁塞控制可以分為網絡資源管理和業務量控制兩種方法。網絡資源管理是指通過 管理無線傳感器網絡的帶寬資源，即合理分配帶寬來控制擁塞。然而在多跳網絡中如何合 理而精確的分配帶寬，以避免帶寬資源供應不足或供應過量的問題，目前還很難實現。業務 量控制主要是在檢測到網絡擁塞時，節點通過減小發送速率以防止擁塞繼續向下遊節點傳 播，並向上遊節點發送通告消息，以避免加重現有的擁塞程度。現有的業務量擁塞控制方法 主要有 CODA、PCCP、Fusion 等。
[0004] CODA (Congestion Detection andAvoidance)協議基於緩存長度和信道利用率檢 測擁塞，採用開環逐跳背壓機制和閉環多源調節機制進行擁塞控制。開環逐跳背壓機制適 合於解除瞬時擁塞，閉環多源調節機制適合於解除持久擁塞。CODA擁塞檢測機制是根據源 節點是否實時收到sink節點反饋的ACK來判斷網絡的擁塞狀況。若源節點發送的數據量已 超過閾值，仍未收到sink節點反饋的ACK，則認為網絡出現了擁塞。當檢測到網絡擁塞時， 就通過背壓機制向源節點方向傳播消息，接收到消息的節點採用分組丟失或加性增乘性減 (AIMD)方式來抑制節點的發送速率，逐跳反饋至源節點，直至擁塞消除，這種方式容易造成 網絡吞吐量的不穩定性，並且遠離sink節點的信道分配公平性差。
[0005] PCCP (Priority-based Congestion Control Protocol)協議定義節點接受速率 與發送速率的比值為擁塞度，並根據擁塞度檢測網絡擁塞。當子節點偵聽到父節點的擁塞 信息後，通過計算父節點的擁塞度，結合自身的優先權和子節點數等信息，調節自身的發送 速率：當父節點的擁塞度較小時，就增大自身的發送速率；當擁塞度較大時，就減小自身的 發送速率。PCCP能夠保證節點及時準確的調節自身的發送速率，但卻忽略了由於速率的調 整對下一跳節點的擁塞影響。
[0006] Fusion是跨層的擁塞控制解決方案，融合了端到端的流量控制、源節點流量的速 率限制和有優先級的MAC層協議3種技術。採用緩存隊列長度和信道採集兩種方式檢測擁 塞。當父節點檢測到擁塞時，便設置分組包頭的擁塞標識位，向子節點隱式的發送擁塞通告 消息。子節點接收到擁塞通告時就停止向父節點發送數據，賦予擁塞節點高的發送優先級。 節點偵聽父節點的子節點數目，使用令牌桶機制限制節點自身的發送速率，從而保證了所 有節點的相同發送流量。為了及時解除擁塞，擁塞節點縮小回退窗口大小為非擁塞節點的 1/4,加快擁塞節點的數據發送，從而賦予擁塞節點高的發送優先級。Fusion能及時解除擁 塞，但卻缺少保證公平性的措施。
[0007] 綜上可知，現有擁塞檢測方法主要是基於單個節點的緩存長度信息和信道狀態來 實現的。當單個節點長期未競爭到信道，容易導致緩存急劇增加，其在信道中共享的信息並 不能真實的反映實時緩存狀態，若不綜合考慮整個信道內節點狀態，可能導致擁塞的虛檢 和漏檢現象。
[0008] 而現有擁塞控制方案，主要是通過降低源節點的數據發送速率或中間節點的轉發 速率，以及增加丟包率來緩解擁塞，並以犧牲包傳遞率和增加額外開銷為代價來增加吞吐 量。如何通過降低由於過度競爭導致的信道碰撞，確保高效有序的信道資源分配和維持較 高的包傳遞率是緩解擁塞亟需解決的關鍵技術難題，目前尚沒有合適的解決方案。
【發明內容】
[0009] 針對上述問題，本發明的目的在於，提出一種基於信道公平分配的擁塞控制方法。 通過估算節點及其上遊鄰居節點的緩存總長度和數據包的平均傳輸延時，解決無線傳感器 網絡擁塞檢測中存在的虛檢和漏檢問題。本發明通過公平分配節點佔用信道的時間以提高 信道使用的公平性，從而減少碰撞和丟包，並增加吞吐量。
[0010] 本發明，首先根據已獲取上遊鄰居節點的數據量估算其隊列增長速率和數據包的 平均傳輸延時。然後，根據估算的隊列增長速率計算其上遊鄰居節點的隊列長度，進一步計 算節點本身及其上遊鄰居節點隊列的總長度，並結合數據包的平均傳輸延時來執行擁塞檢 測；如果發生擁塞，則將網絡擁塞程度分級（即擁塞度），並確定擁塞解除周期，給節點公平 分配佔用信道時間。最後，根據擁塞度，執行擁塞解除算法，從而解除或緩解擁塞；如果沒有 發生擁塞，則不做處理。
[0011] 本發明的具體步驟如下：
[0012] 步驟一預處理：計算成功發送一個數據包所需的時間?；1 ;計算在理想狀態下，一 個節點在一個虛擬周期TqA內能傳輸的最大數據量0_ ;
[0013] 步驟二具有多個上遊鄰居節點的轉發節點（定義為節點X)在每次成功接收到一 個數據包時進行以下數據處理：（1)估算當前節點及其上遊鄰居節點隊列總長度M max ; (2) 估算數據包的平均傳輸延時TtMns ;
[0014] 步驟三節點X在成功接收到一個數據包後，根據數據包的平均傳輸延時TtMns和隊 列總長度M max執行擁塞檢測算法；若檢測結果表明網絡出現擁塞，則轉步驟四；否則，轉步 驟十；
[0015] 步驟四節點X根據當前隊列大小及其上遊鄰居節點隊列大小情況對網絡擁塞程 度進行分級，即分為不同的擁塞度；
[0016] 步驟五節點X根據擁塞度，確定擁塞解除周期；
[0017] 步驟六節點X根據擁塞度，計算節點發送數據與接收數據之間的優先級關係；若 發送優先，則轉步驟八；否則，轉步驟七；
[0018] 步驟七節點X根據已獲知或估算的上遊鄰居節點隊列長度以及擁塞解除周期，給 每個上遊鄰居節點公平分配信道佔用時間；
[0019] 步驟八執行擁塞解除算法；
[0020] 步驟九擁塞解除周期結束則轉步驟三；
[0021] 步驟十結束。
[0022] 與現有MAC層的擁塞控制方法相比，本發明的優點在於：
[0023] 1、本發明提出的通過預測節點及其上遊鄰居節點的隊列總長度，並結合數據包的 平均傳輸延時的擁塞檢測方法，不僅能夠防止網絡擁塞的虛檢和漏檢問題，還能全面的反 映網絡擁塞程度，避免了現有以單一節點的緩存長度是否溢出為標準的擁塞檢測模型存在 的漏檢和虛檢現象。
[0024] 2、本發明根據擁塞度來執行擁塞解除算法和分配信道佔用時間，提高了信道使用 的公平性，有效減少了碰撞和丟包，並增大吞吐量。
【專利附圖】
【附圖說明】
[0025] 圖1是實現本發明擁塞控制的流程圖。
[0026] 具體實施方法
[0027] 本發明設計了信道公平分配的擁塞控制方法，結合圖1，擁塞控制的具體實施方法 如下：
[0028] 步驟一、預處理：計算成功發送一個數據包所需的時間?；1及在理想狀態一個虛擬 周期Tq&內能傳輸的最大數據量D max，具體步驟如下：
[0029] 1)定義隊列最大值為Qlim、發送速率為DR、帶寬為BW、傳輸延遲為T delay、請求包RTS 長度為Lrts、控制包CTS和ACK的長度分別為Lets和Ladt、數據包長度為L data、退避窗口為CW、 時隙為Tstot、SIFS持續時間為Tsifs、DIFS持續時間為T DIFS、則成功發送一個數據包需要的時 間t為：
[0030]
【權利要求】
1. 一種基於信道公平分配的擁塞控制方法，其特徵在於，在無線傳感器網絡中，對節點 實時隊列長度進行預測，結合數據包的平均傳輸延時檢測擁塞；對擁塞狀況劃分擁塞度，確 定擁塞解除周期，並根據已獲知或估算的上遊鄰居節點隊列大小公平分配信道控制周期， 進行擁塞解除或緩解，所述方法至少包括以下步驟： 步驟一預處理：計算成功發送一個數據包所需的時間Ts1 ;計算在理想狀態下，一個節 點在一個虛擬周期Tct^內能傳輸的最大數據量Dmax ; 步驟二具有多個上遊鄰居節點的轉發節點（定義為節點X)在每次成功接收到一個數 據包時進行以下數據處理：（1)估算當前節點及其上遊鄰居節點隊列總長度Mmax; (2)估算 數據包的平均傳輸延時Ttons ; 步驟三節點X在成功接收到一個數據包後，根據數據包的平均傳輸延時Ttans和隊列總 長度Mmax執行擁塞檢測算法；若檢測結果表明網絡出現擁塞，則轉步驟四；否則，轉步驟十； 步驟四節點X根據當前隊列大小及其上遊鄰居節點隊列大小情況對網絡擁塞程度進 行分級，即分為不同的擁塞度； 步驟五節點X根據擁塞度，確定擁塞解除周期； 步驟六節點X根據擁塞度，計算節點發送數據與接收數據之間的優先級關係；若發送 優先，則轉步驟八；否則，轉步驟七； 步驟七節點X根據已獲知或估算的上遊鄰居節點隊列長度以及擁塞解除周期，給每個 上遊鄰居節點公平分配信道佔用時間； 步驟八執行擁塞解除算法； 步驟九擁塞解除周期結束則轉步驟三； 步驟十結束。
2. 如權利要求1所述的方法，其特徵在於所述預處理，至少還包括： 1) 定義隊列最大值為Qlim、發送速率為DR、帶寬為BW、傳輸延遲為Tdelay、請求包RTS長 度為Lrts、控制包CTS和ACK的長度分別為Lets和Ladt、數據包長度為Ldata、退避窗口為CW、 時隙為Tslt、SIFS持續時間為Tsifs、DIFS持續時間為Tdifs、則成功發送一個數據包需要的時 間Ts1為：
2) 傳輸滿負載隊列大小的數據所需時間為： QiimXTs1⑵ 3) 設置虛擬周期為Tctc^,則虛擬周期時間不大於傳輸滿負載隊列大小的數據所需時 間： O〈Tcycle <QlimXTs (3) 4) 在理想狀態下一個虛擬周期內能傳輸的最大數據量Dmax為： D (4) max
3. 如權利要求1所述的方法，其特徵在於所述估算節點X及其上遊鄰居節點的隊列總 長度Mmax以及數據包的平均傳輸延時Ttrans，至少還包括： 1) 假設節點X的上遊鄰居節點的集合為A集合，1為集合A中任意節點，即V/eA。在 Ti時刻節點X成功收到節點1的數據量為M，節點1剩餘數據量為M,';在L時刻檢測到此 時節點X收到節點1的數據量為Λ7，節點1剩餘數據量為#/。根據已獲取的上遊鄰居節點 1數據的時間和相應隊列的大小，可估算出節點1的近似隊列增長速率R1為： (5) Tj-T, 2) 若節點X最近一次收到某個上遊鄰居節點1的數據是在L時刻，則Tk (Tk >Tp時 刻節點1的隊列長度為： 若節點X獲取節點1數據的時間超過節點1理論競爭到信道的最大時間Tmax，即：Tk-Tj >Tmax，則通過預測方式可估算節點1的隊列實時長度為： =(Tk-Tj)XR^M/(6) 否則，節點1的實時隊列大小為最近一次獲取到的隊列大小： Mf=Mj (7) 其中，理論競爭到信道的最大時間Tmax =(上遊鄰居節點數+當前節點 數）X (Τ>Τ順）； 3) 根據上述估算上遊鄰居節點隊列大小的方式，預測Ti時刻節點X及其上遊鄰居節點 的隊列總長度Mmax為： Mmiai (8) ZeA 4) 假設節點X在Ti時刻成功發送的數據量為& ,且存在Ttl = 0, O，<=O計算節 點X數據包的平均傳輸延時Ttons為： 其ra故出古山mil.
否則，假設上一次擁塞解除的時間為VTi >τρ，則：
4. 如權利要求1所述的方法，其特徵在於所述根據節點X數據包的平均傳輸延時Ttons 和隊列總長度Mmax執行擁塞檢測算法，至少還包括： 1) 節點X在成功接收到一個數據包後，當TtransSTs1Xγ(γ為一比率參數，0<γ 0，▽&▲#,'>0時，表示平均傳輸一個數據包所花的時間少於理論所需的時 間，此時網絡可能出現擁塞；否則，網絡沒有出現擁塞或者擁塞不可解除； 2) 當Mmax >DmaxXη(η為一誤差參數，0 <η< 1)時，表示節點X及其上遊鄰居節 點的數據量在一個虛擬周期內不能傳輸完成，此時網絡出現擁塞；否則，不需要進行擁塞解 除。
5. 如權利要求1所述的方法，其特徵在於所述擁塞度劃分，至少還包括： 1) 當節點X隊列長滿足0 xW(Ο<W<i)，且W大於0. 7時，設定擁塞度為3 ; 2) 節點X當前隊列長度不小於最大消息總量的平均值時，即G 設定擁塞度為 2 ； 3) 節點X當前隊列長度小於最大消息總量的平均值時，即仏(η為上遊鄰居節 w+ 1 點數），此時設定擁塞度為1。
6. 如權利要求1所述的方法，其特徵在於所述根據擁塞度確定擁塞解除周期，至少還 包括： 1) 擁塞度為3時，擁塞解除周期縮短0. 5倍，即0. 5XTctc^ ; 2) 擁塞度為1時，擁塞解除周期縮短0. 4倍，即0. 6XTctc^ ; 3) 其他情況，擁塞解除周期不變。
7. 如權利要求1所述的方法，其特徵在於所述根據擁塞度確定節點X發送數據與接收 數據的優先級關係，至少還包括： 1) 當擁塞度為1時，中間節點X擁塞較輕，此時接收數據的優先級大於發送數據的優先 級，即在信道分配時段，節點X優先接收數據，若節點X沒有數據接收時才發送數據； 2) 當擁塞度為2時，中間節點X負載較大，此時接收和發送數據的優先級相同，即在信 道分配時段，節點X按照正常的信道競爭來發送和接收數據； 3) 當擁塞度為3時，中間節點X負載嚴重，此時發送數據的優先級大於接收數據的優先 級，即在信道分配時段，節點X優先發送數據，若節點X沒有數據發送時才接收數據。
8. 如權利要求1所述的方法，其特徵在於根據已獲知或估算的上遊鄰居節點隊列長度 以及擁塞解除周期，給每個節點公平分配信道佔用時間，至少還包括： 1) 當擁塞度為3時，節點X分配給上遊鄰居節點1的信道佔用時間為O; 2) 當擁塞度為1時，節點X分配給上遊鄰居節點1的信道佔用時間為： r= X0.6XTcycle (11) ΣΜΙ IeA 3) 其他情況，節點X分配給上遊鄰居節點1的信道佔用時間為： T=-^-XTcyde (12) ΣΜΙ IeA
9. 如權利要求1所述的方法，其特徵在於所述根據不同的擁塞度執行不同的擁塞解除 算法，至少還包括： 1) 當擁塞度為3時，中間節點X負載嚴重，禁止接收數據，上遊節點等待中間節點發送 下一次擁塞控制信息後重新決策競爭信道機制； 2) 當擁塞度為2時，中間節點X負載較大，不再優先接收數據，接收和發送數據優先級 相同； 3) 當擁塞度為1時，中間節點X擁塞較輕，優先接收數據，當數據接收完成則發送數據。
【文檔編號】H04W28/02GK104270790SQ201410584191
【公開日】2015年1月7日 申請日期:2014年10月23日 優先權日:2014年10月23日
【發明者】李哲濤, 陳潛, 李玉龍, 王志強, 朱更明 申請人:湘潭大學