TDMA自組網的MAC層隊列調度方法與流程

2023-06-26 23:12:06 2

本發明屬於無線通信技術領域,特別涉及一種隊列調度方法,可用於為MAC層數據發送提供一種具有時延和吞吐量保證的調度方式。

背景技術：

MAC層隊列調度決定了MAC層向物理層發送數據分組的實現方法。高效、穩定、健壯的調度可以極大的提高MAC層的性能和通信效率。因此在MAC層的協議設計中，隊列調度方法一直是研究和改善提高的焦點。

在一些傳統的調度算法中，如優先級調度算法，絕對按照優先級從高到低進行調度的方法，但是由於只有在高優先級的隊列沒有數據調度時，才考慮調度次一級優先級的業務，這樣使得調度低優先級業務所體現出的性能不佳，並會導致低優先級業務較長時間沒有得到調度從而發生「餓死」現象。又如在基於輪詢的調度算法中，對於不同的緩存隊列採用循環調度策略，循環調度是指在一定的調度周期內每個隊列得到的調度次數相同，調度機會均等。然而這樣的輪詢調度算法對實時性要求高的業務不能產生較小的時延，沒有優先級的調度可能導致重要信息延時過大，系統輪詢方式造成資源的浪費。因此單純的輪詢算法並不能有良好的性能表現，針對輪詢調度算法的改進大致有加權輪詢WRR，差別輪詢DRR，緊急輪詢URR三種算法，其中：

加權輪詢調度算法WRR，是在傳統輪詢算法的基礎上，為每個緩存隊列增加一個權值，權值的大小根據數據業務的類別以及對時延的要求的因素確定，在調度開始時，每個隊列都會賦予初始權值，之後按照循環輪詢的方式調度數據幀，隊列中每調度一個數據幀，該隊列記錄的權值在數值上減小1，權值數值減到0的隊列不參與相關的輪詢，所有隊列權值為0時為一個輪詢調度周期結束，之後所有隊列權值恢復為初始值進行循環。該方法通過權值的設定，能夠確保每個用戶不會過多的佔用網絡帶寬，同時，也能減小權值較大的數據業務的時延，但是加權輪詢調度算法是以分組為單位進行調度的，所以當數據分組的大小不同時，會對分組較小的隊列帶來不公平性。

差別輪詢調度算法DRR，是以數據分組的長度為評判標準，該方法為每個隊列設定長度允許值，隊列中將要發送數據分組的長度小於該值才會被調度，並在分組被調度出去後，將隊列長度允許值減去調度的分組長度，在一次輪詢之後，為每個隊列的長度允許值再進行增大，以保證有數據可以調度出去，該調度算法主要解決了數據分組長度影響傳統輪詢調度算法公平性的問題，但不能滿足數據業務減小時延的要求。

緊急輪詢調度算法URR，主要通過計算一個緊急參數來提高調度方法對時延要求的適應性，該緊急參數與數據分組對時延的要求有關，每次輪詢開始按照緊急參數依次降低的順序訪問，下一次重新計算緊急參數，通過設計緊急參數的計算方法，可以使對實時性要求較高的數據分組的時延較小，但是該緊急調度算法對公平性沒有性能上的顯著提高。

技術實現要素：

本發明的目的在於針對上述現有技術的不足，提出一種TDMA自組網的MAC層隊列調度方法，以減小調度時延和資源浪費，並為所有鄰節點隊列提供公平性保證。

本發明的技術思路是：通過對本節點i的每個鄰節點按照優先級從高到低分配隊列，存儲不同類型的數據幀，各數據幀在入隊時記錄下入隊時間和隊列長度，在發送時隙到來時，本節點根據數據幀的入隊時間、隊列長度、鄰節點MTU值、隊列優先級四個參數選定一個鄰節點作為當前發送時隙目地地址對應的鄰節點，其實現步驟包括如下：

(1)構建一個時隙表，在每個時隙的起始時刻讀取時隙表中對應位置的值，如果該值為0，則表明該時隙為本節點接收時隙，進行數據接收，如果該值為1，則表明該時隙為本節點的業務時隙，進入步驟(2)進行隊列調度；

(2)選取目地地址對應的鄰節點：

(2a)構建一個入隊時間表和隊列長度表，分別用來存儲各鄰節點隊列最早入隊數據幀的入隊時間和各鄰節點隊列的隊列長度，為每個鄰節點分別構建四個循環隊列用以存儲數據幀，隊列優先級從高到低分別為0級、1級、2級、3級；

(2b)設置一個等待時限值T，查詢入隊時間表，判斷所有鄰節點隊列中入隊最早數據幀的等待時間是否超出等待時限值，若是，則選取該幀所在鄰節點為目地地址對應的鄰節點，進入步驟(3)；若否，則進入步驟(2c)；

(2c)設置一個隊長臨界值S，查詢隊列長度表，按照優先級從高到低的順序判斷是否有隊列長度超出隊長臨界值的隊列，若有，則選取該隊列所在鄰節點為目地地址對應的鄰節點，並選中該隊列隊首指針指向的數據幀，進入步驟(3)；若無，則進入步驟(2d)；

(2d)按照節點號從低到高的順序查詢所有鄰節點的最大傳輸單元MTU，找到最大MTU值，判斷具有該最大MTU值的鄰節點的數量，若只有一個，則該節點為目地地址對應的鄰節點，並選中該鄰節點最高優先級隊列中隊首指針指向的數據幀，進入步驟(3)；若不止一個，則進入步驟(2e)；

(2e)選擇隊列優先級：

(2e1)按照節點號從低到高的順序查詢上述具有最大MTU值的鄰節點，判斷上述鄰節點中有多少個鄰節點的0級隊列不為空：若0級隊列都為空，進入步驟(2e2)，否則，進入步驟(2f)；

(2e2)判斷上述鄰節點中有多少個鄰節點的1級隊列不為空：若都為空，進入步驟(2e3)，否則，進入步驟(2f)；

(2e3)判斷上述鄰節點中有多少個鄰節點的2級隊列不為空：若都為空，則判斷上述鄰節點有多少個鄰節點的3級隊列不為空；

(2f)判斷步驟(2e)中得到的鄰節點數量，若只有一個，則該節點為目地地址對應的鄰節點，紀錄下當前隊列等級，並選中該隊列隊首指針指向的數據幀，進入步驟(3)；若不止一個，則進入步驟(2g)；

(2g)在上述若干個鄰節點中，將各鄰節點與步驟(2f)中紀錄下的隊列等級一樣的隊列進行比較，選取隊列長度最長的隊列所在鄰節點，若存在具有相同最大隊長的隊列則選擇隊列所在鄰節點號較小的那一個，該鄰節點為目地地址對應的鄰節點，並選中該隊列隊首指針指向的數據幀，進入步驟(3)；

(3)根據最大傳輸單元MTU的值決定發送幀數量：

(3a)根據鄰節點的最大傳輸單元MTU值，得到當前時隙允許傳輸的最大數據長度為L，而通過步驟(2)選中幀的幀長為L0，將L與L0進行比較：若L大於L0，將L0設為總幀長，執行步驟(3b)，若L小於L0，則執行步驟(3c)；

(3b)對隊列隊首指針加1，判斷總幀長加上新的隊列隊首指針指向數據幀的幀長是否大於L，若是，則選取結束；若否，則同時選定新的隊列隊首指針指向的數據幀，並將總幀長加上該幀的幀長得到新的總幀長，重複本步驟過程直到最終總幀長大於L為止，再將最終選定的所有數據幀在當前隙全部發送出去；

(3c)將選中的數據幀拆分，當前時隙發送該數據幀長度為L的部分，同時標記步驟(2)中選中的鄰節點，在下一個業務時隙到來時直接選定該鄰節點為目地地址對應的鄰節點。

本發明與現有技術相比具有以下優點：

第一，由於本發明考慮了等待時間參數，當有數據幀在隊列中的等待時間超出門限，就會在當前業務時隙對該幀就行調度，確保所有的數據幀都會得到調度，保證了公平性，同時由於本發明考慮了隊列長度參數，因此當某個鄰節點的業務量較大時，會優先得到調度，這樣會延緩隊列滿的情況，及時處理業務繁忙的鄰節點的數據。

第二，由於本發明引入了最大傳輸單元MTU，優先選擇鏈路狀態好的鄰節點為目地地址對應的鄰節點，同時根據最大傳輸單元MTU值利用幀聚合的方式發送儘可能多的數據幀，提高了時隙的利用效率、傳輸速率和通信質量。

附圖說明

圖1是本發明的使用場景圖；

圖2是本發明的實現流程圖。

具體實施方式

下面結合附圖，對本發明作進一步的詳細描述。

參照圖1，對本發明的使用場景圖作進一步的詳細描述：

按照鄰節點入網的先後順序為所有鄰節點進行從0到n的編號，為每個鄰節點分配四個隊列，用以存儲數據幀，當業務時隙到來時，本節點根據調度方法選擇一個鄰節點作為目地地址對應的鄰節點，進行數據幀的傳輸。

參照圖2，對本發明的實施步驟作進一步的詳細描述：

步驟1.選取本節點業務時隙。

1a)構建時隙表；

通過二維數組構建一個時隙表，用以表徵當前時隙是否為本節點所佔用，表中的值設為0或者1，0表示當前時隙被其他節點所佔用，1表示當前時隙被本節點所佔用；

1b)判定時隙類型：

在每個時隙的起始時刻讀取時隙表中對應位置的值，如果該值為0，則進行數據接收，如果該值為1，則進入步驟2進行調度。

步驟2.判定最早入隊數據幀的等待時間。

2a)構建入隊時間表：

通過二維數組構建一個入隊時間表，用以記錄所有鄰節點的四個隊列中隊首指針指向數據幀入隊時間；

2b)構建循環隊列：

為每個鄰節點構建四個循環隊列，用以存儲不同類型的數據幀，隊列優先級從高到低分別為0級、1級、2級、三級；

2c)計算相關時間參數：

設置一個等待時限T，調用系統函數讀取當前時間，用當前時間減去等待時限，得到差值T0；

2d)判斷是否存在等待時間超出等待時限的數據幀：

查詢入隊時間表，讀取表中入隊時間最早的值記為T1，將T0與T1進行比較，若T0小於T1，則表明等待時間超出等待時限值，選取具有該最小入隊時間值的鄰節點為目地地址對應的鄰節點，進入步驟8；若T0大於T1，則表明等待時間未超出等待門限值，進入步驟3。

步驟3.判定隊列長度。

3a)通過二維數組構建一個隊列長度表，用以記錄所有鄰節點隊列的隊長；

3b)判斷是否存在隊長超出隊長門限值的隊列：

根據網絡性能需求設置一個隊長門限值L，查詢隊列長度表，讀取隊列長度表中的最大值L0，將L與L0進行比較：若L大於L0，選取具有該隊長的隊列所在鄰節點為目地地址對應的鄰節點，進入步驟8；若L小於L0，則進入步驟4。

步驟4.選取具有最大傳輸單元MTU的鄰節點。

最大傳輸單元MTU是指在一個業務時隙時間範圍內，能夠傳輸最長數據幀的長度，按照鄰節點號從小到大的順序查詢所有鄰節點的最大傳輸單元MTU，找到最大傳輸單元MTU值；

判斷具有該最大最大傳輸單元MTU值的鄰節點數量：若只有一個，則選取具有該最大MTU值的鄰節點為目地地址對應的鄰節點，進入步驟8，否則，則進入步驟5。

步驟5.選取隊列優先級。

5a)判斷0級隊列是否為空。

比較步驟4獲得的具有最大傳輸單元MTU值的鄰節點，統計具有最大傳輸單元MTU值的鄰節點中有多少個鄰節點的0級隊列不為空：若0級隊列都為空，則進入步驟5b，否則，則記錄隊列等級為0級，進入步驟6。

5b)判斷1級隊列是否為空。

統計具有最大傳輸單元MTU值的鄰節點中有多少個鄰節點的1級隊列不為空：若1級隊列都為空，進入步驟5c，否則，則記錄隊列等級為1級，進入步驟6。

5c)判斷2級隊列是否為空。

統計具有最大傳輸單元MTU值的鄰節點中有多少個鄰節點的2級隊列不為空：若2級隊列都為空，則統計具有最大傳輸單元MTU值的鄰節點中有多少個鄰節點的3級隊列不為空，並記錄隊列等級為3級，進入步驟6；否則，則統計具有最大傳輸單元MTU值的鄰節點中有多少個鄰節點的2級隊列不為空，並記錄隊列等級對2級，進入步驟6。

步驟6.判斷鄰節點數量。

判斷步驟5中得到的鄰節點數量，若只有一個，選取這個唯一的鄰節點為目地地址對應的鄰節點，進入步驟8，否則，則進入步驟7。

步驟7.隊列長度比較確定目地地址對應的鄰節點。

在具有最大傳輸單元MTU值的鄰節點中，將具有與步驟5中紀錄下的隊列等級一樣的隊列進行比較，選擇隊長最長的隊列所在鄰節點，若存在隊長相同的情況則選擇鄰節點號最小的一個鄰節點，該鄰節點為目地地址對應的鄰節點，並選中該隊列隊首指針指向的數據幀。

步驟8.數據幀總幀長判定。

將上個步驟中選中的數據幀幀長設為總幀長S，判斷該總幀長S是否小於最大傳輸單元MTU：若是，則進入步驟9；否則，則將此數據幀拆分為兩部分，第一部分長度為最大傳輸單元MTU，第二部分長度為這個數據幀的剩餘部分，發送長度為最大傳輸單元MTU的部分至目地鄰節點，同時在下一個業務時隙到來時對該數據幀剩餘部分進行調度。

步驟9.根據最大傳輸單元MTU進行幀聚合。

9a)將隊列隊首指針加1，得到新的隊列隊首指針指向數據幀的長度P，將這個數據幀的長度P與總幀長S相加，得到的值記為S1；

9b)將S1與最大傳輸單元MTU進行比較，若S1大於最大傳輸單元MTU，則進入步驟10，否則，同時選定新的隊列隊首指針指向的數據幀，並用這個數據幀的幀長P加上總幀長S得到新的總幀長；

9c)重複9a)-9b)直到最終總幀長大於最大傳輸單元MTU為止，將所有選定的數據幀發送至目地鄰節點。

以上描述僅是本發明的一個具體實例，不構成對本發明的任何限制，顯然對於本領域的專業人員來說，在了解本發明內容和原理後，都可能在不違背本發明原理、結構的情況下，進行形式和細節上的各種修正和改變，但是這些基於本發明思想的修正和改變仍在本發明的權利要求保護範圍之內。