TWI326180B - Two-tier call admission control algorithm in ieee 802.11 wlan - Google Patents

Description

1326180 九、發明說明： 【發明所屬之技術領域】 本發明係關於一種兩段式通話允諾控制演算法，且更 特別地有關於一種用於IEEE 8 02.1 1無線區域網路之兩段 式通話允諾控制演算法。 【先前技術】 近年來，使用無線寬頻的人口與日倶增，因此，使各 種資料傳輸（例：語音、數據或多媒體）能隨時隨地維持一 定的服務品質，已變得更爲重要。爲因應此需求，整合各 種不同的無線式通訊系統逐漸演變成現今科技發展的潮 流。在眾多整合技術中，IEEE 802.1 1無線區域網路被廣泛 地採用爲整合的系統之一，此無線區域網路運用正交分頻 多工的調變方法，因而提供了很高的傳輸速率（6Mbps〜 5 4Mbps)。然而’ IEEE 802.1 1無線區域網路所涵蓋的範圍 非常有限，所以只設置在一些使用者較爲眾多的地方，例 如辦公室' 校園或機場；除此之外，IEEE 802.11無線區 域網路存在最大缺點爲，當使用者稍有一點移動速率時， 系統的傳輸效能往往也跟著大幅降低。 美國專利公告第US6,2 1 6,006號揭示一種用於無線式 資料網路之允諾控制的方法，此方法需設定一使用者所界 定的數値，而頻寬估計器的表現很容易受到此數値影響， 然而無法得到一最佳値來配合網路負載及網路狀況。 美國專利公告第US6,3 77,549號揭示一種用於無線式 自動櫃員機（ATM)網路之通話允諾控制系統，此方法並未 1326180 考慮到行動端之 SINR(Signal-to-Interference & Noise Ratio ，信號雜訊千擾比）之變化，在行動傳輸速率方面造成非常 大的不良影響。

Wing Fai Fan, Deyun Gao, Danny H.K. Tsang, Brahim Bensaou在2004年的APCC/MDMC(亞太平洋通訊會議及多 維行動通訊會議聯合大會）中，揭示一種在IEEE 802.lie無 線區域網路中用於可變位元速率通訊流量之允諾控制，此 控制方式對於TXOP(Transmission Opportunity，傳輸機會） 效應的計算過於複雜，因此，即使此複雜計算可被克服， 但由於未考慮到實體層之狀況，仍面臨可靠度偏低的問題 e 【發明內容】 本發明之目的在於提供一種用於IEEE 8 0 2. 1 1無線區 域網路之兩段式通話允諾控制演算法，可用以改善整個系 統之傳輸流量及保證每一使用者之服務品質。 根據以上目的，將針對IEEE 802.1 1無線區域網路的 實體層及媒介存取層進行分析，並檢視IEEE 802.11無線 區域網的每一個模式在不同的頻道下所能達到的最大傳輸 流量’且利用馬可夫鍊來導出連線速率自動調節演算法的 數學模型。本發明提出一種用於IEEE 802.11無線區域網 路之兩段式通話允諾控制演算法，該兩段式通話允諾演算 法在IEEE 802.1 1無線區域網路中係用以允諾提供具有高 品質服務要件之服務請求，此演算法包含以下步驟：使單 一使用者及整個系統各自對應於一第一層測試及一第二層 -6- 1326180 測試。 由於本發明採用兩段式來處理使用者及系統之演算 法’因此可改善整個系統之傳輸流量及保證每一使用者之 服務品質。 爲讓本發明之上述和其他目的、特徵及優點能更明顯 易懂’下文特舉較佳實施例，並配合所附圖式，作詳細說 明如下。 【實施方式】 下文中將參照附圖來說明本發明之較佳實施例，其中 相同編號表示相同元件。 第1圖係描繪本發明實施例之用於IEEE 802.1 1無線 區域網路之兩段式通話允諾控制演算法之流程圖。於此圖 中’將採用兩獨立觀點來分析呼叫允諾控制問題，首先， 從單一使用者觀點來說，因爲站台之通道狀況並非一直適 合於無線區域網路（WLAN)系統，所以此站台必須對其通道 響應進行部分測試，及測試其對於無線區域網路之連接容 量’首先’在步驟sioi中’進行媒介存取控制層（Media Access Control, MAC)層及實體層（Physicai，PHY)的測量 及測試’也就是對應於此演算法之第—層，在步驟Sl〇3 中’右適合此無線區域網路，則進入步驟Sl〇5，判斷是否 爲即時通訊量，若不適合此無線區域網路。則進入步驟 S107，進入另一系統。 然後’從整個系統觀點來說，亦即，對應於此發明演 算法之第—層。因爲不同的MAC演算法被設計以調整不同 1326180 有 即 [1 5 制 槪 態 之 ate 臨 之 臨 如 先 爲 輸 2C 。P 之 之 失 態 流量的變化特性’所以在步驟s 1 ο 9及s 1 1 1中，必須具 獨立的呼叫允諾控制單元’本發明實施例將流量分類爲 時通訊量及非即時通訊量’所以在步驟S113中及步驟S】 中具有個別矩陣來決定是否已接受需求站台， 一緩衝時間爲基礎之用於即時通訊量的呼叫允諾控 演算法被介紹於步驟s 1 0 9中。在此演算法中另一相關 念，三維AARF馬可夫鍊亦在此提出。 速率調整是一動態切換傳輸速率來配合變化通道狀 之過程，站台調整其傳輸速率以達到最佳通訊量於給定 通道狀況。AARF(調整自動速率回落 Adaptive auto r fall back)係一種適應性速率之演算法，使用一指數遞增 界値來處理速率，此臨限値係用以決定何時該增加目前 速率，惟此臨限値並不爲固定値。在AARF中，例如此 限値可爲10、20、40及50 (最大界限）。該AARF之處理 下，首先，當探測封包之傳輸失敗時，不但速率切換爲 前較低速率，且使臨限値乘以二倍（但最大界限設定 5 〇) ’此外，當兩次連續傳輸失敗而降低或探測封包的傳 成功時，使此臨限値重設起始値1 0。 此AARF之馬可夫鍊係爲三維形式，第2A圖至第 圖係描繪本發明實施例之 AARF的馬可夫鍊之運算圖丨 表示此站台已完成連續10次傳輸且正要傳輸探測封包 參數，D表示傳輸速率因爲兩次的連續傳輸失敗而減少 參數’實線及虛線各自表示封包傳輸成功及封包傳輸 敗。當使用AARF之馬可夫可鍊時，可確實計算每一狀 1326180 之穩態機率，使用此狀態機率，可計算在不同SNR値之下 每一模式之傳輸下降機率（Pd(>Wn)及傳輸上升機率（Pup)，當 設計即時流量之呼叫允諾控制塽算法時，此兩機率參數將 扮演關鍵角色，各相關計算請參考下列方程式： 尸 P(m -1 n m)

Pf2(m,SNR)、 PH 2 咖，咖，D，cf)

Pf {m, SNR) X [b(m, P,d)+ b(m,0, d)] \Ta^ J j] /)(/77, /c, cf) + b(m, p, d) + /)(m, D, d) I k=0 4 Ps'°(m,SNR)X b(m,P,d)+ PsTd (m, SNR)x [b(m,D, d) + b{m,0,d)]+ & E(0，S/VR)x 咖,M)) ’ =—.Jil____ 21Σ b(m, k, d)+ b(m, P, d) + b(m, D, d)l I /(=0

其中m表示該站台之目前模式，b表示狀態機率，Ps表示 .封包之成功傳輸機率，Pf表示封包之傳輸失敗機率，d表 示相關三維値，Td表示相關臨限値。 各 ΤΧ Ο P ( T r an s m i s s i ο η · 〇 p p 〇 r t u n i t y，傳輸機會）爲一 變動値，介於一站台之兩點期間亦位於改變狀態中，爲了 要實現各通訊量流之延遲界限（delay bound，DB)需求，引 入適應性緩衝時間（buffer time，BT)以補償各TXOP之變 化，一些參數之定義如下，第3圖爲本發明實施例之參數 運算圖。請同時參照第3圖，服務間隔（service interval， -9- 1326180 SI)係如下列方程式所示： S I = m i n (D B ,) Vi 其中si設定爲所有通訊量流之最小延遲界限（DB);各 TXOP之總和浐數G係定義如下列方程式： k G = x OPi 其中G表示在SI區間之所有站台之總和時間，緩衝時間（BT) 係定義如下列方程式： 5Γ = X ^ X X {Pdown t m x 5down i m - Pupi m x ^) + Δ ’其中N及L表示兩通訊浐數’如上所述，bt亦代表一時 間間隔以補償各站台的TXOP的變化，速率適應性技術 AARF可連續地追踪通道狀態以達到最大有效處理量。在 —SNR値下的各站台’各自具有一相關向下傳輸機率値及 一相關向上傳輸機率値’當模式增加或減少時，即使在固

定量資料下亦現時閩差。適用IEEE 802.11a之時間差將 列表於下： 0 m =1 1 1 1 1 1 1 =-m =2 6M 9M ' 18M 6M 9M \%M 1 1 1 1 1 1 =-m _^ 9M 12M ' 36M 9M \2M 36M 1 1 1 1 1 --： 1 :-m =4 \2M 18M 3 36M \2M \%M 36M 1 1 1 ^ dawn , m ~ 1 1 —— 一: 1 =-m =55up'~ =18M 24M ' Ί2Μ 18M 24M Ί2Μ 1 1 1 1 1 1 =-m =6 24M 36M 72M 24M 36M Ί2Μ 1 1 1 1 1 — — : 1 =-m =7 36M 48M ' 144 36M 4SM 144M 1 1 1 1 1 —-z 1 =-m =8 4m 54M ' "432Λ/ 48M 54M 432M 0 = -10- 1326180 其中，5dC)wn表示當模式降低時之一位元的時間差，sup則 表示當模式增加時之一位元的時間差，而△表示補償各通訊 量流的不確定特性，特別是在可變位元速率（VBR，variable bit traffic)流量下。雖然流量規格（τ SPEC)提供部分流量統 計[例如使用者優先序 '最大MSDU(MAC服務資料單元， MAC service data unit)尺寸、平均資料速率]，VBR流量通 常不確實遵循此特性。因此，在BT的計算中將加入△以保 留一些額外的週期時間以爲了平衡此不穩定的性質。綜合 上述參數的描述，BT可調節由速率調整及封包尺寸變化以 及封包相互到達時間變化所引起的時間變化量，Deadline (終界）係定義爲以下方程式：

Deadline = SI-BT 終界表示一種設定用以偵測是否系統仍具有能力來補償各 個TXOP擴展之界限，當各TXOP之總和G超過終界時， 意指G在下一 S I間隔可能越過S I ( S I代表最小之延遲界 限）。在意指封包下降會發生，並代表系統表現將劣化，本 發明當可解決此缺點，將於下面詳述，必須注意的是，在 每個SI間隔的一開始，Pdc)wn及Pup必須根據各站台先前的 SNR來更新，再者，緩衝時間BT必須更新爲一新値》— 旦G大於終界時，意指在下一週期，因爲傳輸速率降低之 故，G具有某一機率來超過SI，因而造成封包下降。除了 上述參數之外，將引入一計數値 η。當各TXOP之總和（G) 超過終界時，η應自行加一。另外引入另一個參數，拒絕 密度（RD)定義爲η除以觀察間隔（以秒計），此表示當預算 違反（G大於終界）在某一時間期間之密度。若RD大於預定 1 1326180 値Nrejeet時，進入流量會被拒絕。此設計係爲了防止站台 的SNR(訊雜比）的突然改變’ RD在此演算法分享相同的觀 念且進一步延展其功能以適用不同需求之封包遺失速率 . (PLR)。顯然地，當PLR的需求放鬆時，貝ij Nreject可設定 爲更大且允許更大的拒絕速率，反之亦然。總言之，決定 是否新的通訊量流將被拒絕的準則將以下一方程式來予以 定義： (G>Deadline)门（RD>Nreject) # 綜上所述’在本發明中，因採用兩段式來處理使用者 及系統之演算法，因此可用以改善整個系統之流通量及保 證每一使用者之服務品質。 雖然本發明已以較佳實施例揭露如上，然其並非用以 限定本發明’任何熟習此技藝者，在不脫離本發明之精神 和範圍內’當可作些許之更動與潤飾，因此本發明之保護 範圍當視後附之申請專利範圍所界定者爲準。 【圖式簡單說明】 φ 第1圖係描繪本發明實施例之用於I E E E 8 0 2.1 1無線 區域網路之兩段式通話允諾控制演算法之流程圖。 第2A圖係描繪本發明實施例之AARF的馬可夫鍊之運 算圖。 第2B圖係描繪本發明實施例之AARF的馬可夫鍊之運 算圖β 第2C圖係描繪本發明實施例之AARF的馬可夫鍊之運 算圖。 第3圖爲本發明實施例之參數運算圖。 -12- 1326180 【主要元件符號說明】 S 1 0 1〜S 1 1 7 步驟

-13-

Claims (1)

1326180 99. 3. l 〇 第95135077號「用於IEEE8 02.1 1無線區域網路之兩段式通 話允諾控制演算法」專利 (2010年3月10日修正) 十、申請專利範圍： 1. 一種用於IEEE 802.1 1無線區域網路之兩段式通話允諾 控制演算法，該兩段式通話允諾演算法在IEEE 8 02.1 1 無線區域網路係用以允諾提供具有高品質服務要件之服 務請求，包含以下步驟： # 使單一使用者及整個系統各自對應於一第一層測試 及一第二層測試。 2. 如申請專利範圍第1項之兩段式通話允諾控制演算法， 其中該第一層測試之控制包括實體層之測量及該實體層 之測試來當作第一層檢查' 3. 如申請專利範圍第1項之兩段式通話允諾控制演算法， 其中僅通過該第一層測試之多個站台被允許發出相關聯 之請求至該整個系統，且進入該第二層測試。 ® 4.如申請專利範圍第3項之兩段式通話允諾控制演算法， 其中該第二層測試係引入緩衝時間以補償一實體層改變 狀態所導致之該等站台之TXOP(Transmission Opportunity， 傳輸機會）變化》 5.如申請專利範圍第4項之兩段式通話允諾控制演算法， 其中當作緩衝時間計算中所使用之參數的各模式間之傳 輸機率係以一如以下方程式所示之三維AARF(調整自動 速率回落）馬可夫錬來計算： 1326180 °d〇wnm = P(m -11 m)= P(m -1 n m) ~~PH~ ll\pf2(m,SNR)x ^b(m,k,d)+b(m,D,d) + Pf (m, SNR) x[b(m,P,d)+ b(m,0,d)]\ d*1 l/c»0 艺泛 Jb(m，/c，d) + t>(m，p，c〇 +D，c〇 Σ Ps10 (m, SNR) x b(m, P, d) + PsTd (m, SNR) χ [b(m, D, d) + b(m,0, c/)]-^{psT,l'k(m,SNR)x b(m,k,d)) rd-i ^}^ό(ηΊ,^ό)+ b(m, P, d)+b(m,D,d)\ I/c=0 其中巧_爲傳輸下降機率’ &爲傳輸上升機率’ p表示該 站台已完成連續1〇次傳輸且正要傳輸探測封包之參數’ D表示傳輸速率因爲兩次連續傳輸失敗而減少之參數，k 表不 '-正整數，SNR表示站台的訊雜比，m表示該站台 之目前模式，b表示狀態機率，Ps表示封包之傳輸成功機 率’ Pf表示封包之傳輸失敗機率，d表示相關三維値，Td 表示相關臨限値》 6.如申請專利範圍第4項之兩段式通話允諾控制演算法， 更包含一參數SI(service interval，服務間隔），以下列方 程式來定義： Sl = min(DB i) V i 其中，DB表示延遲界限，i表示一正整數^ 1326180 7. 如申請專利範圍第4項之兩段式通話允諾控制演算法’ 更包含一參數G，G表示各ΤΧΟΡ的和’以下列方程式來 定義： G = ^TXOPi |S=1 其中，k表示一正整數。 8. 如申請專利範圍第4項之兩段式通話允諾控制演算法’ 更包含—參數BT(buffer time，緩衝時間），以下列方程 式來定義： ΒΤ^Ν,χΣ,χ {Pdawn t m x 5dow„ (m - Pup/ m x Supi m) + Δ /=1 其中，爲傳輸下降機率’心爲傳輸上升機率、 表示當模式降低時之一位元的時間差，5up則表示當模式 增加時之一位元的時間差’而4表示補償各通訊量流的不 確定特性’ k爲一正整數，N、L爲兩通訊參數。 9. 如申請專利範圍第4項之兩段式通話允諾控制演算法， 更包含一參數終界（Deadline)，以下列方程式來定義： Deadl <ne = SI-BT , 其中，SI爲所有通訊量流之最小延遲界限以及BT爲緩衝 時間。 1〇·如申請專利範圍第9項之兩段式通話允諾控制演算法， 更包含一決定準則，以下列方程式來定義： (G>Deadline)H (RD>Nreject) 1326180 其中，G表示在SI 表示一種設定用以1 TXOP擴展之界限， 設値，當該方程式J 求，當該方程式不J 之請求。 區間之所有站台的總和時間，D e a d Π n e :測是否系統仍具有能力來補償各個 RD表示拒絕密度，Nr eje<:t表示一預 ，立時，該整個系統拒絕新的連接請 ，立時，該整個系統同意新的相關聯

1326180 98.12. Η*一、圖式 年月日修正替技頁j (2009年]2月21日修正) • ·