TWI327036B - Load balancing apparatus and method in wireless network hotspots - Google Patents

Description

1327036 九、發明說明： 【發明所屬之技術領域】 本發明係關於一種無線網路熱點(wireless network hotspot)中動態負載均衡(l〇ad balancing)之裝置與方法》 【先前技術】 近年來，無線區域網路(wireless local area network， WLAN)之技術的發展或網路的佈建都有相當程度的成 長。因此，無線網路已經成為擷取行動網際網路服務最 重要的技術之一。無線網路設計為乙太網路(Ethernet)的 延伸’適合使用於盡力服務(best-effort)如電子郵件收發 (E-mai〗)以及網頁劉覽等。但隨著更新的即時(reai time) 多媒體應用如網路電話(Voice over IP，VoIP)、影視串流 (video streaming)的興起，為了確保使用者能有一個可接 受的服務品質(quality of service ’ QoS)，因此對於網路的 效能會有強烈的需求。 習知的技術與研發中，多半是針對單一無線網路存 取點(access point，AP)改善其頻寬使用效能，並且提出 了許多無線網路的無線資源管理技術》然而，在一個無 線網路熱點中，存取點間的負載平衡能力及整體容納能 力等相關問題並未被充分探討。 第一圖為習知無線網路熱點系統架構的一個示意 6 1327036 圖。如第一圖所示，此無線網路熱點系統的架構主要分 ·- 成三個部分：網際網路 '分散式系統(distributed system) ’ _ 和無線區域網路熱點。 . 一個無線網路熱點中有多個存取點和用戶(staii〇n，

STA),並且具備有以下三個功能··（1)許可控制單元 (admission control unit)，藉此單元存取點可以判定其是否 有足夠資源來支援用戶的服務品質(Q〇s)連線請求。有許 φ 多許可控制的技術可以來達到這樣的功能，如IEEE 802.1 le協定之參考許可控制機制；(2)無線電測量與管理 能力（radio measurement and management facilities)，存取 點可透過此功能要求與其聯努之無線網路用戶，進行無 線電的測量，並將測量的結果回報給存取點，因此存取 點可以知道其鄰近的存取點資訊。目前有多種關於無線 電測ΐ與管理的技術，如IEEE 802.11k協定；（3)快速 換手(fasthandoff)，用戶和存取點可應用IEEE8〇2丨卜協 • 定之快速換手技術或其他相關的技術。 如第一圖所示，無線網路熱點中其存取點的訊號範 圍(coverage area)通常會相互覆蓋。當一個無線網路用戶 在進入網路(networkentry)的階段’可能會同時偵測到許 多可連線的存取點。無線網路用戶一般會選擇訊號最良 好的存取點來與其聯繫(associate)並建立連線。接著，用 戶會佔據存取點某些資源(如頻寬與存取點的緩衝區)來 7 進行服務。然而，這種以用戶為中心的網路聯繫(network association)及服務要求方式會導致無線網路熱點中的存 取點的負載不均而造成用戶無法有效使用頻寬資源。而 無線多媒體服務’如網路電話(Voice over WLAN， Vo WLAN)，特別需要高服務品質的應用。 用戶可以選擇與存取點建立非服務品質連線或服務 品質服務連線。當用戶建立非服務品質連線，如FTP連 線、收發電子信件(e-mail)、瀏覽網頁等此類盡力 (best-effort ’ BE)和背景(background，BK)等，存取點並 不保證此非服務品質連線的服務品質。而服務品質連 線，如聲音(voice ’ V0)或影像(video，VI)等連線時，則 會向其存取點發出服務品質連線請求。由於存取點對於 服務品質連線通常必須給予服務品質保證（q〇s guarantee)，因此存取點之大部分的頻寬資源分配給服務 品質連線，舉例來說，服務品質連線和非服務品質連線 可能會各佔存取點80%及20%的頻寬資源。 第二圖為一習知無線網路負載之系統示意圖。如第 二圖所示，當一個無線網路用戶如S3，在進入網路階段 時’此用戶S3可能會偵測到多個存取點如Ai與A2的 訊號，並選擇訊號最好的存取點如A1並與其作聯繫。 當另一用戶S9欲建立服務品質連線，如聲音(voice，VO) 或影像(video ’ VI)等連線時’會向其存取點A1發出服務 品質連線請求，接著存取點Ai則透過許可控制單元來 判斷是否能滿足此請求，但是存取點A1服務品質連線 頻寬203已被佔滿’所以無法滿足用戶S9之服務品質連 線請求。 也就是說’習知以用戶為中心的(STA_centric)無線網 路聯繫機制可能發生存取點的負載不均，而發生存取點 無法滿足用戶之服務品質連線，以導致較差的無線網路 頻寬使用效用。 美國專利第6,574,474號揭露一種根據基地台訊號強 度及基地台的負載狀況等兩種評定標準，用戶選擇適當 的基地台與之聯繫以達到無線系統負載平衡之目的。 美國專利第6,574,477號揭露一種單一蜂槽(cen)内兩 個基地台之間負載平衡之方法。美國專利第6,069,871號 揭路一種針對多載波的格網(cellular)無線通訊系統》當其 中一用戶向現役基地台要求建立通話連線時，若此現役 基地台沒有足夠資源來提供用戶進行通話服務時，則提 供一種方式尋找鄰近基地台(neighbor base station)，此鄰 近基地台擁有足夠資源以提供此用戶之通話服務並建立 連線。世界專利公開第WO2004004226號揭露在一無線 網路系統中，當存取點之可用頻寬資源低於門檻 (threshold)時’号找是否有鄰近的存取點，且鄰近存取點 在服務此存取點用戶後，本身的頻寬資源不會低於此門 檻。這些習知技術都是在特殊情況下所啟動之特殊機 制’而非廣泛的解決方案(general solution)。 因此需要一種新的動態負載均衡技術來改善無線網 路系統頻寬資源的使用效用。 【發明内容】 本發明提供一種無線網路熱點中動態負載均衡之裝 置與方法，此裝置包括一資源分配模組扣s〇urces allocation module)和一負載調整單元(1〇ad balancer)。此 無線網路熱點中備有多個存取點與多個用戶。 當有一存取點無法滿足有一用戶發出的一服務品質 連線請求時，此資源分配模組先建立此無線網路熱點中 存取點與用戶間的資源模型和關係，並找出一條負載均 衡轉移路徑(load balance shift path，LBSP)。根據此負載 均衡轉移路fe，負載調整單元重新分配網路資源並動態 調整此無線網路熱點中多個存取點間的負載，進而增加 整體無線通訊系統的頻寬使用效能。 當多於一條負載均衡轉移路徑被發現時，有許多選 擇路徑的方案可以被採用，例如負載調整後對整體無線 網路熱點中花費最少資源的那條路經被採用或是路徑 1327036 長度最財被選擇。也可關時料條負載均衡轉移路 徑的方式來進行-連串的負載調整操作以滿足用戶的服 務品質連線請求。 • 本發明皆適用於集中式(centra丨ized)或分散式 _ (decentralized)無線通訊系統。在集中式(罐如㈣)無線 通訊系統巾储方向獅分g罐，即無線網路熱點 令存取點以及用戶間的關係，找出負載均衡轉移路徑， • 再調整存取點的負載，以達到無線網路之負裁平衡。在 分散式(decentralized)無線通訊系統中，其存取點與用戶 «甙皆分散地儲存在各個存取點中，所以是藉由存取點 間此t'的交換來制，無須透過—巾央词服器來調整存 取點間的負載調整，可降低成本。 茲配合下列圖示、實施例之詳細說明及申請專利範 圍，將上述及本發明之其他目的與優點詳述於後。 【實施方式】 第三圖是根據本發明之無線網路熱點中動態負载均 衡之裝置的一個系統概要圖，其中此無線網路熱點中備 有多個存取點與多個用戶。參考第三圖，此動態負載均 衡裝置300包含一資源分配模組3〇丨與一負載調整單元 303。搭配此動負載均衡之裝置3〇〇，當多個存取點中 有一存取點無法滿足多個用戶中有一用戶發出的一服務 11 1327036 。。質連線請求時’例如當有—存取關可用頻寬低於某 個門檻時、歧有—存取點沒有足觸資源來滿足其用 戶的服務品質連料求時，第_進__步說明其動態負 載均衡的運作流程。 此資源分配模組301首先建立此無線網路熱點中此 多個存取點财細戶間哺源模型和隱，並找出一 條負載均衡轉移路徑，如第四圖之步驟4〇1所示。根據 此負載均衡轉移路徑，負載調整單元3〇3重新分配網路 資源並動態調整此無線網路熱點中多個存取點間的負 載，如第四圖之步驟403所示，進而增加整體無線通訊 系統的頻寬使用效能。 本發明進一步描述如何建立此無線網路熱點中存取 點與用戶間的資源模型。一個無線網路熱點總共有ΛΓ個 存取點，為簡單說明起見，此無線網路熱點下的所有存 取點假設皆為一致，其中為代表此關係模型之第丨個存 取點，C,代表存取點决的頻寬資源效用，且c介於〇和 1之間》C,=l代表存取點冼的資源皆被佔滿，因而存取 點A,沒有足夠的資源來提供給用戶新的服務。 尽代表第j個用戶，並以Z^.Kbps的速度與此無線網 12 1327036 路熱點中的一個存取點為聯繫，例如正EE802.iib提供 用戶1 Mbps、2 Mpbs、5Mbps以及11 Mbps之連線速度。 假設用戶冬需要巧個服務連線，而第&個服務連線要求 以〜的速度進行。當存取點為同意用戶各之％個服務連 線時，則存取點為分配ra巧/兄y的資源支援給這些服 務，而气=Σ!ίΛ。 接下來，本發明描述如何建立無線網路熱點中存取 點及用戶間的兩種關係，一為存取點及用戶間的訊號範 圍關係，另一為存取點與用戶間的服務關係。 當某個用戶5)執行無線網路頻道掃瞄並且搜尋到一 個存取點為，接著冬會將為加入其掃瞄清單(scan iist)。 因此’ Ay定義了存取點及用戶間的訊號範圍關係： |1，當4在&掃描清單中. u U其它. 若尽向為發出進行服務品質請求並獲得允許建立起 連線’如定義了存取點與用戶間的服務關係： q. J 1 4是义現役存取點，且4支援Sj服務品質連線 "1〇,其它. 、 以上兩種關係Αν以及％/可以從現役存取點本身或藉 由定期或非定期地向其聯繫用戶發出訊號測量請求，並 13 1327036 由用戶回應的測量報告得到。 s用戶尽想要更多的資源來進行新的服務，但現役 存取點無法献它時’本㈣之貞躺衡方法便啟動來 調整存取闕負載，並容納此用戶$的服務品質連線要 求。 第五圖為利用本發明之動態負载均衡的一個範例， • 其中，第五A圖和第五B圖分別說明動態負載調整前與 調整後之-個無線網路熱點中用戶與存取點間的關係， 圓圈代表存取點的訊號涵蓋範圍。 參考第五A圖，為了方便說明起見，假設存取點在 其訊號涵蓋範圍提供一致的頻寬，而兩個相鄰存取點佔 用不同的無線網路頻道，且每個存取點最多支援三通無 線網路電話，其中用戶&-¾分別與存取點山、a、為、 • 為、山、4、七以及沁聯繫以進行一通無線網路電話。 當一用戶&向存取點沁要求進行無線網路電話服務時， '過載的存取點為便不能提供用戶&這個服務，即用戶 • 为無法進行無線網路電話服務。應用本發明，就會改變 用戶&的現役存取點從為換成於是存取點（就會 有可用的資源來分配給用戶&。第五B圖即為第五A圖 的範例應用本發明之負載調整後，用戶與存取點間的關 係圖。 14 1327036 本發明皆適用於集中式（centralized)或分散式 (decentralized)無線通訊系統。在集中式無線通訊系統 中’即一中央伺服器擁有所有存取點與用戶之相關資 訊’本發明使用一個描述無線網路熱點中存取點以及用 戶間之關係的方向圖(directed graph)，即有向的資源分配 圖(resource-allocation graph) ’來尋找負載均衡轉移路 徑。然後透過此中央伺服器來調整存取點的負載，而達 到無線網路之負載平衡。 在分散式無線通訊系統中，由於其存取點與用戶資 訊皆分散地儲存在各個存取點中，所以本發明是藉由存 取點間訊息的交換來調整存取點間的負載，而達到無線 網路之負載平衡。不需要藉由中央伺服器，因而可再降 低成本。以下分別說明本發明之應用於集中式與分散式 無線通訊系統。 在集中式無線通§fl系統中，本發明使用有向的資源 分配圖來描述網路熱點中存取點目前負載以及存取點與 用戶間的關係。此有向的資源分配圖包括一點集合和— 邊集合。此點集合表示此多個存取點與此多個用戶，此 邊集合由多個分配邊與多個要求邊所組成。第六A圖為 第五A圖之範例(即負載調整前)的一資源分配圖。以此 第六A圖為例，以下進一步說明此資源分配圖。 15 參考第六A圖，一個從山到&的邊標示為（Α,Α)， 代表存取點禹正服務用戶&並稱為一分配邊 (assignment edge)603。也就是說P/2=l 且 。而一個 從&到山的邊標示為（&，⑹稱之為要求邊(claim edge)605 ’代表七在&的掃瞄清單中但七沒有服務用戶 &，也就是= 1且犯3=0，唯一的例外為從&到山 的邊標示為（¾，為)之要求邊，代表怂為了建立新的服務 品質連線’正向其現役存取點（發出請求。 透過此資源分配圖600便能很容易瞭解存取點與用 戶間的關係。在集中式無線通訊系統中，本發明之資源 分配模組301所建立的無線網路熱點中存取點與用戶間 的資源模型也就是此資源分配圖。 如前所述，當用戶&向存取點為要求進行無線網路 電話服務時，而存取點木卻無法滿足時，即可啟動本發 明之動態負載均衡裝置來找出一負載均衡轉移路徑，並 調整存取點的負載，以容納用戶舄的進行無線網路電話 服務請求》 當多於一條負載均衡轉移路徑被發現時，有許多選 擇路徑的方案(Path selection solution)可以被採用，例如負 載調整後對整體無線網路熱點中花費最少資源的那條路 控(path that spends the minimal resources)被採用，或是路 徑長度最短(shortest path)，也就是最少用戶需要被遷徙 的那條路徑(path that minimizes migration 〇Verhead)合被 選擇。在本發明中’以此資源分配圖600找到三條負載 均衡轉移路徑。此三條負載均衡轉移路徑分別為：{(& Ai\{^i,S4),{S4y A3 &)，（&，烏 (¾七）}。 若採用負載調整後對整體無線網路熱點花費最少資 源的那條路徑，則首先必須給予這三條負载均衡轉移路 徑上的邊一個權重(weight)%.。若為分配邊，則％ = _ ，若為要求邊，則％ =兄7^然後將路徑上所有邊的 權重加總，异出每一條路徑的權重，並以權重最小的路 徑為選擇的路徑》 若採用路徑長度最短的方式，則選擇路徑長度最短 的第三條路徑，㈣，4)，（+，&)，（^2)卜 一旦負載均衡轉移路徑決定之後，在此選擇{(&，山)， (I，&)’（&，4 )}這條負載均衡轉移路徑，此負載均衡 轉移路徑之邊的方向必須被反轉，即路徑上的分配邊6〇3 變成要求邊605 ’而要求邊魏分Siit。也就是反轉負 栽平衡轉移路徑{(知义)，（& )，（ &，的方向，反 轉成（山，&)，（心阜)，（&)，那麼&便被存取點山 1327036 服務了。第六B圖為執行本發明之負載調整後，第五B 圖之存取點與用戶關係的資源分配圖。 上述範例中’係以一負載均衡轉移路徑來滿足用戶 " 的服務品質連線請求。此外，也可以在資源分配圖中尋 ’ 找負載均衡轉移路從子圖（load balancing shift path siib-gmph)。其負載均衡轉移子圖’亦即同時以多條負載 均衡轉移路徑的方絲進行-連㈣貞載破操作以滿 Φ 足用戶的服務品質連線請求。以下以第六B圖之資源分 配圖為例來尋找此負載均衡轉移路徑子圖。 當用戶&向現役存取點為發出服務品質連線請求 時’現役存_ 綱喊得从及&的頻寬資源 後才能滿足私的請求。此時便選擇以多條路徑的方式同 時將&和&遷徙至其相對應的鄰近存取點(ndghb〇r AP) ’七以及冯，以達到滿足&的品質服務連線請求， • 此即負載均衡轉移路徑子圖’如第七A圖所示。 * 帛七B ®為此例之資源分配®。其幅滿足此例之 • 貞綱娜移子圖之貞載均衡赫職為將{(知 (山，句，（知々)，（木，&)，（知4)}反轉成(A &)，（知 ^^(^’^^(^，^/^(々，^，亦即同時將用戶&轉移 至存取點七、用戶&轉移至存取點（。 18 以上兩個範例中係將本發明應用於集中式無線通訊 系統中。即中央飼服器擁有所有存取點以及用戶之相關 資汛，並且在找出負載均衡轉移路徑後也是透過此中央 伺服Is來調整存取點間的負載調整。集中式無線通訊系 統需要額外之中央伺服器的硬體成本。 第八圖是收到服務品質連線要求後，本發明在集中 式無線通訊系統中動態負載均衡的運作流程圖。參考第 八圖，首先，接收一用戶發出的服務品質連線請求，如 步驟801所示。然後判斷該用戶之現役存取點是否可允 許接受該服務品質連線要求，如步驟802所示。是的話， 則回應一成功说息給此用戶，如步驟8〇3所示。不是的 話，則進行步驟401，建立此無線網路熱點中此多個存 取點與多個用戶間的資源模型和關係，並找出一條負載 均衡轉移路徑’以將該用戶納入該現役存取點之服務的 服務頻寬。最後，如步驟403所示，根據此負載均衡轉 移路徑，重新分配網路資源並動態調整此無線網路熱點 中多個存取點間的負載，如IEEE 802.1 lr之快速換手技 術’而提升整體無線通訊系統之頻寬使用效能。 如前所述，當建立此無線網路熱點中此多個存取點 與多個用戶間的資源模型和關係後，先進行尋找可能的 負載均衡轉移路徑，當多於一條負載均衡轉移路徑被發 現時’有許多選擇路徑的方案可以被採用，例如負載調 1327036 整後對整體無線網路熱點中花費最少資源的那條路徑被 採用’或是路技長度最短會被選擇。也可以同時以多條 負載均衡轉轉徑的方式來進行—連串的貞載調整操作 以滿足用戶的服務品質連線請求。 由於集中式無線通訊系統需要額外之中央伺服器的 硬體成本，本發明也提供了應用於分散式無線通訊系統 中動悲負載均衡的方法。無線網路分散式系統其所有的 • 存取點以及用戶資訊皆分散地儲存在各個存取點中，所 以負載均衡轉移路徑的尋找過程是透過存取點間訊息的 父換來達到。此方法是透過泛傳(flooding)的方式，將尋 找負載均衡轉移路徑的請求轉遞給鄰近的存取點，並找 到一負載均衡轉移路徑。 第九圖是收到服務品質連線請求後，本發明在分散 式無線通訊系統中動態負載均衡的運作流程圖。參考第 # 第九圖’繼步驟802之後，若該用戶之現役存取點不允 許接受該服務品質連線要求時，則以步驟904取代步驟 ‘ 401。 在步驟904中，設定限制代價參數一門檻值，並找 出該現役存取點正在服務的用戶中滿足下列兩條件者：（1) 釋放其頻寬資源後，此現役存取點便能服務此請求，（2) 其有鄰近的存取點可聯繫。然後’將尋找負載均衡轉移 20 ”值得—提的是，為了有效解決尋找負載均衡轉移路 控所造成執辦間過長必須奴尋找貞納轉移路徑 之時間我值T。第十圖進—步說明收到—尋找負載均 衡轉移路姆求後，本發明的處理流程。 參考第十®，首S，該鄰近的存取點接㈣尋找負 載均衡轉移路崎求，如轉醜麻。接著，調整限 制代價參數，紐躺雕後的限做價參數是否仍符 合一设定的門檻範疇内，如步驟1002所示◊不是的話， 則捨棄此尋找負載均衡轉移路徑請求，如步驟1003所 不。是的話，則判斷相對應的該鄰近存取點是否可滿足 已追蹤路徑中即將加入的用戶之所有服務，如步驟1004 所不。若可滿足，則發出帶有已追蹤路徑為參數的回應 給發出該路！找尋請求的來源存取點(s〇urce ap)，即已 追蹤路徑中的第一個存取點’如步驟1005所示。若不可 滿足，則進行步驟1006。 在步驟1006中，找出有可聯繫的鄰近存取點之服務 中用戶，且該用戶釋放其頻寬資源後，現役存取點便能 滿足已追蹤路徑中即將加入的用戶之所有服務。接著， 調整路徑尋找請求中除限制代價參數外的所有參數，例 如將存取點本身以及相對應用戶加入已追蹤路徑以及更 替相對應用戶之服務品質連線參數等。然後，泛傳轉遞 此請求訊息給這些相對應用戶的鄰近存取點。 22 1327036 同樣地此負載均衡轉移路徑請求訊息的存取 點會依上翻流雜作。依此赫，—朗朗 衡轉移路徑或_代價參數超出-設定的π播範嘴為 止。以此方式可以有賴決尋找路徑所造成執行時間過 常，並且防止找到過長路徑所造成的調整代價過大等問 題。 。

惟’以上所述者’僅為發明之最佳實施例而已，當不 月t依此限疋本發明實施之範圍。即大凡一本發明申請專 利範圍所作之均等變化與修飾，皆應仍屬本發明專利涵 蓋之範圍内。

23 1327036 【圖式簡單說明】 第-圖為-個習知無線網路熱點系統架構的示意圖。 第二圖為-個習知無線網路負載之系統的示意圖。 第三圖是根據本發明之無線網路熱財動態負載均衡之 裝置的一個系統概要圖。

第四圖說明第三圖之裝置的祕_均衡的運作流程。 第五A圖為類本發明之動態負綱衡的—個範例。 第五B圖為第五a圖 用戶與存取點間的關係圖。 的範例應用本發明之負載調整後， 第六A圖為第五a圖於負_整前的_資源分配圖。 第六B圖為執行本發明之負載調整後，第丑㈣之存取 點與用戶關係的資源分配圖。 第七A圖為本發明之負載調整後之—負載均衡轉移路徑子 圖。 第七B圖為第七A圖之-資源分配圖。

第八圖是收舰務品質連線要求後，本發明在集中式無 線通訊系統中動態負載均衡的運作流程圖。 第九圖是Μ服務品質魏請求後，本發明在分散式無 線通訊系統令動態負載均衡的運作流程圖。 第十圖說日月收到尋找負載均衡轉移路徑請求後，本發明 的處理流程。 【主要元件符號說明】 24 1327036

AP存取點 STA、Si用戶 300動態負載均衡裝置 301資源分配模組 303負載調整單元 401 建立此無線網路熱財衫贿取點與多侧戶間的資 源模型和關係，並找出1錄均衡轉移路徑 403根據此負載均衡轉移路徑，重新分配網路資源並動態調 整此無線網路熱點_多個存取點間的負載 600資源分配圖 603分配邊 605要求邊 801接收一用戶發出的服務品質連線請求 802判斷該用戶之現役存取點是否可允許接受該服務品質連 線要求 803回應一成功訊息給此用戶 904設定一限制代價參數門檻值； 找出該現役存取點正在服務的用戶中滿足下列兩條件 者：⑴釋放其頻寬資源後，此現役存取點便能服務此請 求，（2)其有鄰近的存取點可聯繫； 25 1327036 將寻找負載均衡轉移路徑的請求泛傳至這些鄰近的存取 點； 啟動一計時器τ; 在計時器T的時間内’等待回應以一負載均衡轉移路徑 905在計時器T的時間内是否找到負載均衡轉移路徑？ 906拒絕服務品質連線請求

1001接收該尋找負載均衡轉移路徑請求 1002判斷調整後的限制代價參數是否仍符合設定的門檻範 疇内 1003捨棄此尋找負載均衡轉移路徑請求 1004判斷相對應的該鄰近存取點是否可滿足已追蹤路徑中 即將加入的用戶之所有服務

1005發出帶有已追蹤路徑為參數的回應給發.出該路徑找尋 請求的來源存取點 1〇〇6尋找有可聯繫的鄰近存取點之服務中用戶，且該用戶釋 放其頻寬資源後，現役存取點便能滿足已追蹤路徑中即 將加入的用戶之所有服務； 調整負載均衡轉移路徑尋找請求中除限制代價參數外 的所有參數； 泛傳此請求訊息給這些相對應用戶的鄰近存取點 26

Claims (1)

1327036 ff年f月f(7日修正替換頁 十、申請專利範圍： — 1. 一種無線網路熱點中動態負載均衡裝置，該無線網路 熱點中備有多個存取點與多個用戶，當該多個存取點 t有一存取點無法滿足該多個用戶中有一用戶的服務 品質連線請求時，該裝置包含：

一資源分配模組，以一有向的資源分配圖來建立該無 線網路熱點中該多個存取點與該多個用戶間的資源模 型和關係，並找出至少一條負載均衡轉移路徑；以及 一負載調整單元，根據該至少一條負載均衡轉移路 徑，重新分配網路資源並動態調整該無線網路熱點中 該多個存取點間的負載。 2. 如申請專利範圍第1項所述之無線網路熱點中動態負 載均衡裝置，其中該裝置適用於一集中式無線通訊系 統。 3. 如申請專利範圍第1項所述之無線網路熱點中動態負 載均衡裝置，其中該裝置適用於一分散式之無線通訊 系統。 4. 如申請專利範圍第2項所述之無線網路熱點中動態負 載均衡裝置，其中該資源分配模組更包括一有向的資 源分配圖來描述該無線網路熱點中該多個存取點與該 多個用戶間的資源模型和關係。 5. 如申請專利範圍第4項所述之無線網路熱點中動態負 載均衡裝置，其中該有向的資源分配圖更包括： 一點集合，表示該多個存取點與該多個用戶；以及 27 -邊集合’鶴多個分g&邊射個要求邊所組成，一 分配邊表示-存取點正在服務一用戶，而一要求邊表 示-存取點在-用戶的掃瞎清單中但該存取點沒有在 服務該用戶。 -種無線網路熱財動態負載均衡方法，該無線網路 熱點中備有辣存取點财铜戶，#該多個存取點 中有-存取點無法滿足該多個用戶中有—用戶發出的 —服務品質連線請求時，該方法包含下列步驟： 以-有向的«分_鍵立該無_路熱點中該多 個存取點與多侧戶間的資源模型和關係，並找出至 少一條負载均衡轉移路徑；以及 根據該負載均衡轉移_，麵分_路資源並動態 調整該無線網路熱點中多個存取點間的負載。 如申請專利細第6項所述之無線網路熱點中動離負 載均衡方法，其中該方法適祕—集中式無線舰系 統。 如申4專利範圍第6項所述之無線網路熱點中動態負 =句衡H其巾該方法朝於—分散式無線通訊系 如申吻專利範圍第6項所述之無線網路熱料動態負 載均衡方法，其中該方法以一快速換手技術來進行該 動_整該無線網路熱財鮮個存取闕的負載。 申明專利㈣第6項所述之無線網路熱點中動態負 :衡方法，其中在找出該至少—條負載均衡轉移路 刊年f聊日1’!正赖頁 徑之前’該方法先進行尋找可能的負載均衡轉移路徑。 U.如申凊專利範圍第6項所述之無線網路熱點中動態負 載均衡方法，其中建立的該多個存取點與多個用戶間 的該關係有兩種，一為存取點及用戶間的訊號範圍關 係’另一為存取點與用戶間的服務關係。 12. 如申凊專利範圍第6項所述之無線網路熱點中動態負 載均衡方法，其中該方法有兩種方案來找出該至少一 條負载均衡轉移路徑，一為採用負載調整後對整體無 線網路熱點中花費最少資源的路徑，另一為選擇路徑 長度最短，也就是最少用戶需要被遷徙的路徑。 13. 如申凊專利範圍第6項所述之無線網路熱點中動態負 載均衡方法，其中該方法在建立該無線網路熱點中此 多個存取點與多個用戶間的資源模型和關係，並找出 該至少一條負載均衡轉移路徑之前，更包含下列步驟： 接收該用戶發出的該服務品質連線請求； 判斷该用戶之現役存取點是否可允許接受該服務品質 連線要求;以及 是的話’則回應一成功訊息給此用戶。 14. 如申請專利範圍第7項所述之無線網路熱點中動態負 載均衡方法，其中該方法是透過一令央伺服器來擁有 該夕個存取點與該多個用戶之相關資訊，並且透過該 中央伺服器找出該至少一條負載均衡轉移路徑及動態 調整該多個存取點間的負載平衡。 15. 如申請專利範圍第8項所述之無線網路熱點中動態負 、 ψ 衡方法’其巾該方法是透過-泛傳的方式，轉遞 寻找負躺衡細職崎求卿近的存取點，並 找到°亥至""―條貞躺衡轉移路徑。 16·如申請專職_ 8 述之無線麟熱點中動態負 載句衡方法其中當收到該用戶發出的該服務品質連 線請求後，若_戶之現役存取解允許接受該服務 品質連線要求時，該方法進行下列步驟：

設定一_储錢門贿，如概役存取點正在 服務的用戶巾滿騎放其頻寬資源後 ’該現役存取點 便此服務此4求，並且其有鄰近的存取點可聯繫者； 將,亥尋找貞躺衡轉移路徑的請求泛㈣遞到該找出 之用戶的該可聯繫之鄰近的存取點； 在一計時ϋ τ的時_，等待回應以—負載均衡轉移 路徑;以及

若超過該計時器τ的時間，而沒收到任何回應訊息， 則拒絕該服務品質連線請求。 17‘如申料利細第15姻叙鱗網轉財動態負 载均衡方法’其中該尋找負載均衡轉移路徑的請求中 包括一已追觀徑參數、-_代價參數、-限制代 價參數門健以及相對_戶的服務品質連線相關參 數之訊息。 认如申清專利紅圍第17項所述之無線網路熱點中動態負 載句衡方法其中虽收到該尋找負載均衡轉移路徑的 請求後，該方法進行下列步驟： 30 1327036 行年5~月1'〇曰修正替換頁 若該現役存取點為可滿足該服務品質連線要求之相對 ~ J 應的該鄰近存取點，且該限制代價參數仍符合一設定 的門檻範疇内時，則回應發送該負載均衡轉移路徑找 尋請求的來源存取點；

找出有可聯繫的鄰近存取點之服務中用戶，且該用戶 釋放其頻寬資源後，該現役存取點便能滿足已追蹤路 徑中即將加入的用戶之所有服務;以及 調整該負載均衡轉移路徑尋找請求中包括之所有該參 數，並泛傳該負載均衡轉移路徑尋找請求給該尋找出 之用戶的相對應鄰近存取點。

31