在無線網狀網絡中的擁塞管理方法
2023-09-17 22:47:20
專利名稱：在無線網狀網絡中的擁塞管理方法
技術領域：
本發明涉及無線網狀網絡領域，更特別地，涉及在使用CSMA/CA算法 來接入無線介質的無線網狀網絡中的擁塞管理方法。
背景技術：
在無線網絡中，站共享無線介質。這導致了對無線介質的竟爭，因為 同時的消息將沖突。為了使得能夠公平共享，IEEE 802. ll標準引入了 DCF 和EDCA機制，其中站執行著名的CSMA或CSMA/CA算法以接入介質。這些 機制在某種程度上避免了衝突，並且使得能夠相對有效地使用介質。然而， 在V.Vishnevsky和A. I. Lyakhov， Cluster computing 5,133—144， 2002中 顯示，由於搶佔效應(seizing effect)這些機制導致不公平。在發送消 息之前，站通過CSMA或CSMA/CA檢測介質，以獲知介質是否可獲得，並且 預訂介質用於隨後發送消息。該操作由站在被稱為竟爭窗口的時間窗口內 實行。剛結束其傳輸的站具有贏得下一次傳輸的竟爭的優勢。實際上，在 成功的傳輸後，CSMA或CSMA/CA算法規定竟爭窗口的大小被重置為最小 窗口大小。因此，剛剛已成功的站使用小窗口大小接入介質，並比其他最 近沒有成功贏得竟爭的站具有優勢。這反過來可導致不希望的情形積壓 的(backlogged)站可壟斷信道，因為它可獲得對信道的獨佔接入一段延 長的時間。
這種在標準WLAN中發生的情形在網狀網絡中程度甚至更高，這是由 於在這樣的網狀中涉及的無線站密度增加。並且，該效應的後果在網狀網 絡中比在標準WLAN中甚至更嚴重，可導致顯著的吞吐量降級，正如S.Xu 和T. Sadaawi在IEEE Communications Magazine 2001年6月第130-137 頁的"Does the IEEE 802.11 MAC protocol work well in multihop wireless ad hoc networks " 中所示。
例如，假設由於搶佔效應，積壓的站搶佔了信道。則它能向它的下遊 鄰站發送很多消息。然而，鄰站很大程度上不能接入介質，因為它的上遊 鄰居(積壓的站)已搶佔了該信道。最終，由於鄰站的隊列開始溢出，它 除了丟棄進入的分組而外別無選擇。該情形導致了性能降級。在2006年11月草擬的標準IEEE P802. lls/Dl. 00 "Draft Amendment to Standard for Information Technology — Telecommunications and Information Exchange Between Systems — LAN/MAN Specific Requirements — Part 11: Wireless Medium Access Control (MAC) and physical layer (PHY) specifications: Amendment: ESS Mesh Networking."中，通過在MAC層廣播"鄰域擁塞通知(Neighbourhood Congestion Announcement)"和/或單播"擁塞控制請求(Congestion Control Request )"的建立來預先考慮到擁塞管理問題。這些消息使用在 該草案7.2.4.3節定義的網狀網管理幀格式，並在網狀網管理動作域
(Mesh Management Action field,該草案7. 4和7. 3節)中進行定義。 然而，該草案沒有詳細說明"擁塞等級"欄位或該消息必須被用於管 理網狀網絡中擁塞的方式。在IIA. 7節中，該草案描述了一些可由站用來 檢測擁塞的可能規則監視發送和接收速率及這兩個聚合速率
(aggregated rate)之間的差，或者監一見隊列大小，或者兩者的混合。 一旦接收到"鄰域擁塞通知"或"擁塞控制請求"消息，接收節點需 要通過本地限制它的流量從而減少它的有效MAC發送速率。本地速率控制 機制可基於動態調整EDCA參數，例如AIFSN、 CWmin或兩者。
發明內容
在使用CSMA/CA算法來接入無線介質的無線網狀網絡中，實現限制或 避免不公平在它對網絡吞吐量影響中的效果的擁塞管理方法將是有益的。
為了更好的解決一個或多個問題，在本發明的第一方面， 一種在無線 網狀網絡中擁塞管理的方法，在該無線網狀網絡中CSMA/CA算法被用來接 入無線介質，所述網絡包括第一站和至少一個能夠與第一站直接通信的鄰 站，該方法包括
-當第一站在它的環境中經歷擁塞時，由第一站向至少一個鄰站廣 播通知消息，所述通知消息包括擁塞等級參數，
——旦接收到通知消息，由鄰站激活擁塞狀態，其中在發送消息之 前接入介質的、被稱為竟爭窗口的時間窗口的最小大小嚴格地大於沒有擁 塞時定義的最小大小，在擁塞狀態中的所述最小大小被定義為擁塞等級參 數的函數。
該方法有益地-故應用於管理竟爭窗口大小，從而避免搶佔效應。通過 接收擁塞通知消息，壟斷無線介質的站不得不增加它的竟爭窗口的大小。因此，在它鄰域中的其他站有更好的機會接入無線介質，並能夠傳輸它們 的消息。
在特定實施例中，在激活擁塞狀態後，如果鄰站發送分組失敗，鄰站 在重傳分組之前將竟爭窗口的大小增加一倍。
在另一個實施例中，擁塞等級參數是擁塞時設置的擁塞標記，並且與 在沒有擁塞時定義的最小大小相比，在擁塞狀態中竟爭窗口的大小被加 倍。沒有擁塞時不設置擁塞標記，當鄰站去激活擁塞狀態時，竟爭窗口的 大小減少2。當在發送分組期間沖突數超過預定閾值時，第一站廣播通知 消息。該實施例具有實現簡單的優點。
在另一個實施例中，擁塞等級參數是嚴格地正整數，且鄰站將擁塞狀
態中的竟爭窗口大小設置為2的擁塞等級減1次方。並且，擁塞等級基於 在能夠發送分組之前第一站發送的通知數。該實施例具有更精確調節窗口 大小的值的優點。
在另 一個實施例中，擁塞等級參數包括在擁塞狀態中將被鄰站使用的 竟爭窗口大小。第一站跟蹤激活的鄰站數目，並將竟爭窗口的大小設置為 接近激活的鄰站數目倒數的發送概率。在該實施例中，在以通過通知消息 發送更多信息為代價的情況下，竟爭窗口的大小被非常精確地調節。
在本發明的另一個方面， 一種在無線網狀網絡中的擁塞管理系統，在 無線網狀網絡中CSMA/CA算法被用於接入無線介質，所述網絡包括第一站 和至少一個能夠與第一站直接通信的鄰站，該系統包括
-用於當第一站在其環境中經歷擁塞時，由第一站向至少一個鄰站 廣播通知消息的裝置，所述通知消息包括擁塞等級參數，
-用於一旦接收到通知消息，由鄰站激活擁塞狀態的裝置，其中在 發送消息之前接入介質的、被稱為竟爭窗口的時間窗口的最小大小大於沒 有擁塞時定義的最小大小，在擁塞狀態時的所述最小大小被定義為擁塞等 級參賽的函數。
在本發明的另一方面， 一種在無線網狀網絡中的站，在無線網狀網絡 中CSMA/CA算法被用來接入無線介質，所述站與至少一個鄰站直接通信， 所述站包括用於當它在它的環境中經歷擁塞時向至少一個鄰站廣播通知 消息的裝置，所述通知消息包括擁塞等級參數，所述擁塞等級參數是所述 站經歷的沖突數的函數，或者是在能夠發送分組之前該站發送的通知數的 函數。
在本發明的另一個方面， 一種在無線網狀網絡中的站，在無線網狀網絡中CSMA/CA算法被用來接入無線介質，所述站與至少一個鄰站直接通 信，當所述鄰站在它的環境中經歷擁塞時，所述鄰站適於廣播包括擁塞等 級參數的通知消息，所述站包括用於一旦接收到通知消息、激活擁塞狀 態的裝置，其中在發送消息之前接入介質的、被稱為竟爭窗口的時間窗口 的最小大小大於在沒有擁塞時定義的最小大小，在擁塞狀態中的所述最小 大小被定義為擁塞等級參數的函數。
本發明最後涉及可直接載入站的內部存儲器的電腦程式產品，包括 用於當所述產品在所述站上運行時，執行擁塞管理方法的所有步驟的軟體 代碼部分。
本發明的這些和其他方面將參考這裡描述的實施例得以說明，並根據 這裡描述的實施例變得顯而易見。
本發明的實施例現在將僅作為示例並參考附圖來描述，其中 -圖l是弦拓樸(string topology)示例網狀網絡的示意圖； -圖2是在傳統網絡中作為流量負載函數的吞吐量的圖； -圖3是根據本發明實施例的網絡操作示意圖。
具體實施例方式
參考圖1,簡單網狀網絡具有弦拓樸並包括6個節點或站，標記為A 到F。外部節點A、 F是信息的源和宿。內部節點B、 C、 D、 E是在適當方 向上路由消息的中繼。由於網狀網絡的拓樸，內部節點B、 C、 D、 E具有 2個鄰站，外部節點A、 F僅分別具有一個鄰站B和E。從而，對於內部站 B、 C、 D、 E來說經歷沖突的概率大於外部站A、 F。
在傳統網絡中，由於CSMA/CA算法的搶佔效應，外部節點A、 F有更 多機會搶佔信道，內部節點的路由功能被妨礙。在一定等級的擁塞，由於 內部節點的緩存裝滿了等待被發送的消息並且新的消息持續從外部節點 推入，內部節點—皮迫丟棄分組。
對傳統網絡吞吐量的效應在圖2中得以圖示，當流量負荷增加高於大 約400時，吞吐量急劇下降。
根據本發明的實施例，節點被更改以便當它們經歷擁塞情況時能夠發 送通知消息，以及一旦接收到這樣的通知消息時能夠修改它們的竟爭窗口
7大小。
因此，網絡的操作如下，圖3。
一個節點，例如節點B，在它的領域中經歷擁塞狀態，步驟20。 擁塞狀態的定義基於不同的標準 -沖突數高於預定閾值； -激活站(即發送消息的站)的數目；和/或
-基於諸如由G. Bianchi 2000年3月在IEEE JSAC第18巻第3期 535—547頁的"Performance analysis of the IEEE 802.11 Distributed coordination function"中描述的預測分析這樣的可觀測量的操作模型。
步驟22，節點B向它的鄰近節點A、 C發送通知消息，通知它們它正 經歷擁塞狀態。該通知消息包括擁塞等級參數。
在步驟24，節點A、 C接收該通知消息，並在步驟26增加竟爭窗口 的大小。竟爭窗口新的大小是擁塞等級參數的函數。
在步驟28，如果節點A或節點C需要發送消息，在步驟30它使用新 的竟爭窗口大小獲取信道。並且，典型地，如果無線介質的獲取失敗，在 步驟32該節點在再次嘗試之前將竟爭窗口的大小加倍。
通過增加竟爭窗口的大小，搶佔效應有益地被減少或被抑制。
成功的站不能再壟斷無線介質。由於最小竟爭窗口變得更大，當與其 他站相比時成功的站的優勢被減小了 。
另一個優點是網狀網絡的站的最小竟爭窗口大小的可變性減小，這導 致更加公平。如果最小竟爭窗口大小增加，並且不是太小，使用大竟爭窗 口大小對抗(counteract)小竟爭窗口的需要減小了。
可變性減小的另一個優點是如由Bianchi在上述文件中所示那樣網 絡吞吐量的增加。
通知消息，即擁塞等級參數，的格式改變並取決於所選信令的類型。 在第一實施例中，擁塞狀態僅由一個比特發信號通知。當該比特被設
置時，擁塞的狀態被發信號通知，當該比特沒有被設置時，沒有擁塞狀態。 當擁塞狀態被發信號通知時，所有鄰站將它們的最小竟爭窗口加倍，
類似地，當通知消息的比特沒有設置時，鄰站將它們的最小竟爭窗口大小
除以2。
該實施例的優點是簡單。該信令方法的潛在缺點是站可能接收到不同 數目的通知消息，最後具有不同值的最小竟爭窗口大小，這造成不公平並 限制了該實施例的有效性。
8在第二實施例中，擁塞狀態糹皮發信號通知為定義擁塞等級的整數。對 於非擁塞狀態，該擁塞等級設置為l，並且隨著擁塞而增加。例如，擁塞 等級被定義為激活的鄰站數目。 一旦接收到擁塞等級，站定義竟爭窗口的 最小大小為沒有擁塞時的最小大小乘以2的擁塞等級減1次方，或者其中
CWcong是針對擁塞定義的最小大小，CWmin是沒有擁塞時的最小大小，M 是由通知消息傳送的擁塞等級。
在該實施例中，需要更多的比特來在通知消息中發送擁塞等級。然而， 該實施例具有為所有鄰站維護通用大小的竟爭窗口的優點。從而，網絡更 快地(即使用較少量的擁塞通知消息)遷移到所有站共享期望的最小竟爭 窗口大小的狀態。
在第三個實施例中，通知消息直接包括將由鄰站使用的竟爭窗口的最 小大小。該實施例具有以在通知消息中更多空間發送所述大小為代價，允 許竟爭窗口大小細粒度的控制。該實施例也偏離了當前實踐，在當前實踐 中一旦衝突就將竟爭窗口大小加倍。
雖然在圖和前述描述中詳細地解釋和描述了本發明，這樣的解釋和描 述被認為是說明性的或示例性的，而不是限制性的；本發明不受限於所公 開的實施例。
和附加權利要求書的學習中、在實施要求保護的發明時理解和實現。在權 利要求書中，詞語"包括"並不排除其他元素，不定冠詞"一個"並不排
除複數。
本發明可藉助包括多個不同元件的硬體和藉助適當被編程的計算機 來完成。在設備權利要求中列舉了幾個裝置，這些裝置中的一些裝置可包 含在硬體的同 一個零件中。僅僅某些措施是在相互不同的從屬權利要求中 記載這個事實並不意味著這些措施的結合不能被用來產生良好效果。
權利要求
1.在無線網狀網絡中的擁塞管理方法，在無線網狀網絡中CSMA/CA算法被用於接入無線介質，所述網絡包括第一站和至少一個能夠與第一站直接通信的鄰站，該方法包括-當第一站在它的環境中經歷擁塞時，由第一站向所述至少一個鄰站廣播(22)通知消息，所述通知消息包括擁塞等級參數，-一旦接收到通知消息，由鄰站激活(26)擁塞狀態，其中被稱為競爭窗口的、在發送消息前接入介質的時間窗口的最小大小嚴格地大於沒有擁塞時定義的最小大小(CWmin)，在擁塞狀態中的所述最小大小被定義為擁塞等級參數的函數。
2. 根據權利要求l的方法，其中在已激活擁塞狀態後，如果鄰站發 送分組失敗，則鄰站在重傳分組之前將竟爭窗口的大小加倍。
3. 根據權利要求1的方法，其中擁塞等級參數是在擁塞情況下設置 的擁塞標記，與在沒有擁塞時定義的最小大小相比，在擁塞狀態中竟爭窗 口的大小被加倍。
4. 根據權利要求3的方法，其中如果沒有擁塞，擁塞標誌不被設置， 當鄰站去激活擁塞狀態時，竟爭窗口的大小被減少2。
5. 根據權利要求3的方法，其中當發送分組期間衝突的數目超過預 定閾值時，第一站廣播通知消息。
6. 根據權利要求l的方法，其中擁塞等級參數是嚴格地正整數，且 鄰站將擁塞狀態中的竟爭窗口大小設置為2的擁塞等級減1次方。
7. 根據權利要求6的方法，其中擁塞等級基於在能夠發送分組之前 由第一站發送的通知數目。
8. 根據權利要求1的方法，其中擁塞等級參數包括在擁塞狀態中將 被鄰站使用的竟爭窗口大小。
9. 根據權利要求8的方法，其中第一站追蹤激活的鄰站數目，並將 竟爭窗口的大小設置為接近激活的鄰站數目倒數的發送概率。
10. 在無線網狀網絡中的擁塞管理系統，在無線網狀網絡中CSMA/CA 算法被用於接入無線介質，所述網絡包括第一站和至少一個能夠與第一站 直接通信的鄰站，其特徵在於該系統包括-用於當第一站在它的環境中經歷擁塞時、由第一站向至少一個鄰 站廣播通知消息的裝置，所述通知消息包括擁塞等級參數，_用於一旦接收到通知消息、由鄰站激活擁塞狀態的裝置，其中在 發送消息之前接入介質的、被稱為竟爭窗口的時間窗口的最小大小大於沒 有擁塞時定義的最小大小，在擁塞狀態中的所述最小大小被定義為擁塞等 級參數的函數。
11. 在無線網狀網絡中的站，在無線網狀網絡中CSMA/CA算法被用 於接入無線介質，所述站與至少一個鄰站直接通信，其特徵在於所述站包 括用於當它在它的環境中經歷擁塞時向至少一個鄰站廣播通知消息的裝 置，所述通知消息包括擁塞等級參數，所述擁塞等級參數是所述站經歷的 衝突數目的函數，或者是該站在能夠發送分組之前發送的通知數目的函 數。
12. 在無線網狀網絡中的站，其中在無線網狀網絡中CSMA/CA算法 被用於接入無線介質，所述站與至少一個鄰站直接通信，所述鄰站適於當 所述鄰站在它的環境中經歷擁塞時、廣播包括擁塞等級參數的通知消息， 其特徵在於所述站包括用於一旦接收到通知消息激活擁塞狀態的裝置， 其中在發送消息之前接入介質的、被稱為竟爭窗口的時間窗口的最小大小 大於沒有擁塞時定義的最小大小，在擁塞狀態中的所述最小大小被定義為 擁塞等級參數的函數。
13. —種能直接載入站的內部存儲器中的電腦程式產品，包括用 於當所述產品在所述站上運行時、執行權利要求1的所有步驟的軟體代碼 部分。
全文摘要
一種在無線網狀網絡中的擁塞管理方法，在無線網狀網絡中CSMA/CA算法被用於接入無線介質，所述網絡包括第一站和至少一個能夠與第一站直接通信的鄰站，該方法包括-當第一站在它的環境中經歷擁塞時，由第一站向至少一個鄰站廣播(22)通知消息，所述通知消息包括擁塞等級參數；-一旦接收到通知消息，由鄰站激活(26)擁塞狀態，其中在發送消息前接入介質的、被稱為競爭窗口的時間窗口的最小大小嚴格地大於沒有擁塞時定義的最小大小(CWmin)，在擁塞狀態中的所述最小大小被定義為擁塞等級參數的函數。
文檔編號H04W74/08GK101584234SQ200880002203
公開日2009年11月18日 申請日期2008年1月10日 優先權日2007年1月12日
發明者B·瓦爾克, G·希爾茨, T·登特尼爾 申請人:皇家飛利浦電子股份有限公司