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

Description

200818945 九、發明說明： 【發明所屬之技術領域】 本發明係關於一種無線網路熱點(wireless network hotspot)中動態負載均衡(load balancing)之裝置與方法。 【先前技術】 近年來’無線區域網路(wireless local area network， WLAN)之技術的發展或網路的佈建都有相當程度的成 長。因此，無線網路已經成為擷取行動網際網路服務最 重要的技術之一。無線網路設計為乙太網路(Ethernet)的 延伸’適合使用於盡力服務(best-effort)如電子郵件收發 (E-mail)以及網頁瀏覽等。但隨著更新的即時(real time) 多媒體應用如網路電話(Voice over IP，VoIP)、影視串流 (videcxstreaming)的興起，為了確保使用者能有一個可接 受的服務品質(quality of service，QoS)，因此對於網路的 效能會有強烈的需求。 習知的技術與研發中，多半是針對單一無線網路存 取點(access point，AP)改善其頻寬使用效能，並且提出 了許多無線網路的無線資源管理技術。然而，在一個無 線網路熱點中，存取點間的負載平衡能力及整體容納能 力等相關問題並未被充分探討。 第一圖為習知無線網路熱點系統架構的一個示意 6 圖。如第一圖所示，此無線網路熱點系統的架構主要分 成一個4刀·網際網路、分散式系統(distributed system) 和無線區域網路熱點。 一個無線網路熱點中有多個存取點和用戶(stati〇n， STA)，並且具備有以下三個功能：（丨）許可控制單元 (admission control unit)，藉此單元存取點可以判定其是否 有足夠資源來支援用戶的服務品質咖幻連線請求。有許 多許可控制的技術可以來達到這樣的功能，如IEEE 802.11e協定之參考許可控制機制；(2)無線電測量與管理 能力（radio measurement and management facilities)，存取 點可透過此功能要求與其聯繫之無線網路用戶，進行無 線電的測量，並將測夏的結果回報給存取點，因此存取 點可以知道其鄰近的存取點資訊。目前有多種關於無線 電測量與管理的技術，如IEEE 802.11k協定；（3)快速 換手(fast handoff)，用戶和存取點可應用IEEE 8〇211r協 定之快速換手技術或其他相關的技術。 如第一圖所示，無線網路熱點中其存取點的訊號範 圍(coverage area)通常會相互覆蓋。當一個無線網路用戶 在進入網路(network entry)的階段，可能會同時偵測到許 多可連線的存取點。無線網路用戶一般會選擇訊號最良 好的存取點來與其聯繫(associate)並建立連線。接著，用 戶會佔據存取點某些資源(如頻寬與存取點的緩衝區)來 進行服務。然而，這種以用戶為中心的網路聯繫(network association)及服務要求方式會導致無線網路熱點中的存 取點的負載不均而造成用戶無法有效使用頻寬資源。而 無線多媒體服務，如網路電話(Voice over WLAN， VoWLAN)，特別需要高服務品質的應用。 用戶可以選擇與存取點建立非服務品質連線或服務 品質服務連線。當用戶建立非服務品質連線，如FTP連 線、收發電子信件(e-mail)、瀏覽網頁等此類盡力 (best-effort ’ BE)和背景(background，BK)等，存取點並 不保證此非服務品質連線的服務品質。而服務品質連 線，如聲音(voice，V0)或影像(video，VI)等連線時，則 會向其存取點發出服務品質連線請求。由於存取點對於 服務品質連線通常必須給予服務品質保證（q〇s guarantee)，因此存取點之大部分的頻寬資源分配給服務 品質連線，舉例來說，服務品質連線和非服務品質連線 可能會各佔存取點80%及20%的頻寬資源。 第二圖為一習知無線網路負載之系統示意圖。如第 二圖所示，當一個無線網路用戶如S3，在進入網路階段 時’此用戶S3可能會偵測到多個存取點如Ai與A2的 訊號，並選擇訊號最好的存取點如A1並與其作聯繫。 當另一用戶S9欲建立服務品質連線，如聲音(v〇ice，v〇) 或影像(video，VI)等連線時，會向其存取點A1發出服務 。口質連線請求，接著存取點A1則透過許可控制單元來 判斷是否能滿足此請求，但是存取點A1服務品質連線 頻覓203已被佔滿，所以無法滿足用戶S9之服務品質連 線請求。 也就是說，習知以用戶為中心的(STA-centric)無線網 路聯繫機制可能發生存取點的負載不均，而發生存取點 無法滿划戶之服務品質連線，轉致較差的無線網路 頻寬使用效用。 吴國專利第6,574,474號揭露一種根據基地台訊號強 度及基地台的負載狀況等兩種評定標準，用戶選擇適當 的基地台與之聯繫以達到無線系統負載平衡之目的。 美國專利第6,574,477號揭露一種單一蜂槽(ce⑴内兩 個基地台之間負載平衡之方法。美國專利第6,069,871號 揭露一種針對多載波的格網(cellular)無線通訊系統。當其 中一用戶向現役基地台要求建立通話連線時，若此現役 基地台沒有足夠資源來提供用戶進行通話服務時，則提 供種方式哥找鄰近基地台(neighbor base station)，此鄰 近基地台擁有足夠資源以提供此用戶之通話服務並建立 連線。世界專利公開第W02004004226號揭露在一無線 網路系統中，當存取點之可用頻寬資源低於門檻 (threshold)時’尋找是否有鄰近的存取點，且鄰近存取點 200818945 在服務此存取點用戶後，本身的頻寬資源不會低於此門 檻。這些習知技術都是在特殊情況下所啟動之特殊機 制’而非廣泛的解決方案(general⑽祕⑽。 :因此需要一種新的動態負載均衡技術來改善無線網 , 路系統頻寬資源的使用效用。

L 【發明内容】 • 本發明提供一種無線網路熱點中動態負載均衡之裝 置與方法，Λ裝置包括-資源分配模組(Γ_· allocation m〇dule)和一負载調整單元(1〇ad —咖十 無線網路熱點中備有多個存取點與多個用戶。 當有一存取點無法滿足有一用戶發出的一服務品質 連線明求時’此資源分配模組先建立此無線網路熱點中 存取點與用戶間的資源模型和關係，並找出一條負載均 _ 補移路徑(load bal_ shift path，LBSP)。根據此負載 均衡轉移路，貞細整單元重新分輯路資源並動態 _ 調整此無線網路熱點中多個存取點間的負載，進而增加 . 整體無線通訊系統的頻寬使用效能。 δ多於一條負載均衡轉移路徑被發現時，有許多選 擇路徑的方案可以被採用，例如負載調整後對整體無線 、鹏熱點巾花費最少資源卿條路徑被採用，或是路徑 10 200818945 長度最短會被選擇。也可以同時以多條負載均衡轉移路 徑的方式來進行一連串的負載調整操作以滿足用戶的服 務品質連線請求。 : 本發明皆適用於集中式(centralized)或分散式 【 （decentralized)無線通訊系統。在集中式(centralized)無線 通訊系統中係藉由一方向資源分配圖，即無線網路熱點 中存取點以及用戶間的關係，找出負載均衡轉移路徑， 春 再調整存取點的負載，以達到無線網路之負載平衡。在 分散式(decentralized)無線通訊系統中，其存取點與用戶 資訊皆分散地儲存在各個存取點中，所以是藉由存取點 間訊息的交換來達到，無織過_中央伺服器來調整存 取點間的負載調整，可降低成本。 兹配合下順示、實補之詳細說明及中請專利範 圍，將上述及本發明之其他目的與優點詳述於後。 【實施方式】 第二圖是娜本發m網路熱財動態負載均 衡之裝置的-個系統概要圖，其中此無線網路熱點中傷 有多個存取點與多個用戶。參考第三圖，此動態負載均 衡裝置300包含-資源分配模組3〇1與一負載調整單元 3〇3。搭配此動態負載均衡之裝置·，當多個存取點中 有-存取點無法滿足多個用戶中有__用戶發出的一服務 200818945 ⑽胃連線請求時，例如當有—存取點的可雜寬低於某 個門禮時、或是有_存取點沒有足觸資絲滿足其用 戶的服務口口貝連線請求時，第四圖進一步說明其動態負 : 載均衡的運作流程。 此貝源分配模組3〇1首先建立此無線網路熱點中此 多個存取點與多铜戶W的資賴型和關係 ’並找出一 • 條負載均衡轉移路徑，如第四圖之步驟4G1所示。根據 此負載均衡轉移路徑，負載調整單元3〇3重新分配網路 資源並動態調整此無線網路熱點中多個存取點間的負 載，如第四圖之步驟4〇3所示，進而增加整體無線通訊 系統的頻寬使用效能。 本發明進一步描述如何建立此無線網路熱點中存取 φ 點與用戶間的資源模型。-個無線網路熱點總共有ΑΓ個 存取點，為簡單綱起見，此無線網路熱點下的所有存 -取點假設皆為一致，其中為代表此關係模型之第i個存 ^ 取點’C/代表存取點為的頻寬資源效用，且<^·介於〇和 1之間。CH代表存取點4·的資源皆被佔滿，因而存取 點A;沒有足夠的資源來提供給用戶新的服務。 尽代表第j侧戶，並以疋⑽^的速度與此無線網 12 200818945 路熱點中的一個存取點為聯繫，例如ffiEE 8〇211b提供 用戶1 Mbps、2 Mpbs、5Mbps以及11 Mbps之連線速度。 假没用戶冬需要巧個服務連線，而第A個服務連線要求 , 以q的速度進行。當存取點為同意用戶尽之巧個服務連 ，線時，則存取點為分配⑺崎/及彡的資源支援給這些服 務，而 rate』= 。 φ 接下來，本發明描述如何建立無線網路熱點中存取 點及用戶間的兩種關係，一為存取點及用戶間的訊號範 圍關係，另一為存取點與用戶間的服務關係。 當某個用戶尽執行無線網路頻道掃瞄並且搜尋到一 個存取點為，接著5)會將冼加入其掃瞄清單(scan list)。 因此，Ay定義了存取點及用戶間的訊號範圍關係： 當4在义掃描清單中. _ ^ 1〇，其它. - 若冬向為發出進行服務品質請求並獲得允許建立起 . 連線’知定義了存取點與用戶間的服務關係： q =11, 4是A現役存取點，且4支援Sj服務品質連線 "U其它· 、… 以上兩種關係p/y•以及如可以從現役存取點本身或藉 由定期或非定期地向其聯繫用戶發出訊號測量請求，並 13 由用戶回應的測量報告得到。 當用戶$想要更多的資源來進行新的服務，但現役 存取點無法滿足树，本發明之貞辆衡綠便啟動來 調整存取點的負載，並容納此用戶糾服務品f連線要 求。 第五圖為制本發明之動態負載均衡的—個範例， 其中，第五A圖和第五β圖分別說明動態負載調整前與 調整後之一個無線網路熱點中用戶與存取點間的關係， 圓圈代表存取點的訊號涵蓋範圍。 茶考第五Α圖，為了方便說明起見，假設存取點在 其訊號涵蓋範圍提供一致的頻寬，而兩個相鄰存取點佔 用不同的無線網路頻道，且每個存取點最多支援三通無 線網路電話，其中用戶分別與存取點、（、山、 為、々以及木聯繫以進行一通無線網路電話。 當一用戶&向存取點為要求進行無線網路電話服務時， 過載的存取點為便不能提供用戶&這個服務，即用戶 &無法進行無線網路電話服務。應用本發明，就會改變 用戶舄的現役存取點從禹換成，於是存取點為就會 有可用的資源來分配給用戶&。第五B圖即為第五A圖 的範例應用本發明之負載調整後，用戶與存取點間的關 200818945 本發明皆適用於集中式（centralized)或分散式 (decentralized)無線通訊系統。在集中式無線通訊系統 中，即一中央伺服器擁有所有存取點與用戶之相關資 訊’本發明使用一個描述無線網路熱點中存取點以及用 戶間之關係的方向圖(directed graph)，即有向的資源分配 圖(resource-allocation graph)，來尋找負載均衡轉移路 徑。然後透過此中央伺服器來調整存取點的負載，而達 到無線網路之負載平衡。 在分散式無線通訊系統中，由於其存取點與用戶資 汛皆分散地儲存在各個存取點中，所以本發明是藉由存 取點間訊息的交換來調整存取點間的負載，而達到無線 網路之負載平衡。不需要藉由中央伺服器，因而可再降 低成本。以下分別說明本發明之應用於集中式與分散式 無線通訊系統。 在集中式無線通訊系統中，本發明使用有向的資源 分配圖來描述網賴財存取點目前貞載以及存取點與 用戶間_係。此有向贿源分g罐包括—點集合和一 邊集合。此點集合表示此多個存取點與此多個用戶，此 邊集合由多個分配邊與多個要求邊所組成。第六A圖為 第五A圖之範例(即負载調整前)的一資源分配圖。以此 第六A圖為例，以下進一步說明此資源分配圖。 15 參考第六A圖，一個從為到&的邊標示為（為,¾)， 代表存取點為正服務用戶&並稱為一分配邊 (assignment edge)603。也就是說凡2=1 且 ％,2=1。而一個 從$3到』2的邊標示為（5^，d2)稱之為要求邊(claim edge)605，代表次在&的掃瞄清單中但沁沒有服務用戶 &，也就是Pu = 1且似尸0，唯一的例外為從&到為 的邊標示為（¾ 4)之要求邊，代表&為了建立新的服務 品質連線，正向其現役存取點為發出請求。 透過此資源分配圖600便能很容易瞭解存取點與用 戶間的關係。在集中式無線通訊系統中，本發明之資源 分配模組301所建立的無線網路熱點中存取點與用戶間 的資源模型也就是此資源分配圖。 如前所述，當用戶&向存取點為要求進行無線網路 電話服務時，而存取點為卻無法滿足時，即可啟動本發 明之動悲負載均衡裝置來找出一負載均衡轉移路徑，並 調整存取點的負載，以容納用戶&的進行無線網路電話 服務請求。 ‘夕於條負載均衡轉移路徑被發現時，有許多選 擇路徑的方案(path selection solution)可以被採用，例如負 載調整後對整體無線網路熱點中花費最少資源的那條路 徑(path that spends the minimal resources)被採用，或是路 杈長度最短(shortest path)，也就是最少用戶需要被遷徙 的那條路徑(path that minimizes migration overhead)會被 選擇。在本發明中，以此資源分配圖6〇〇找到三條負裁 岣衡轉移路徑。此三條負載均衡轉移路徑分別為：{(& )> (AIy S4), ( S4y A3), ( A3y S6 \ ( A4)} ^ {( S9y Aj )y (4} & )，)，（4 & )，(S7, ^ )}、以及&，為)，（為，& )， (心)}。 若採用負載調整後對整體無線網路熱點花費最少資 源、的那條路徑，先必紐予這三條貞躺衡轉移路 徑上的邊一個權重(weight)%。若為分配邊，則％ = · 尺V，若為要求邊，則％ =足；。然後將路徑上所有邊的 權重加總，算出每一條路徑的權重，並以權重最小的路 從為選擇的路控。 若採用路徑長度最短的方式，則選擇路徑長度最短 的第三條路徑，⑽，為)，（為4)，（知為）}。 一旦負載均衡轉移路徑決定之後，在此選擇{(¾，為)， (為，& )，，冯）}這條負載均衡轉移路徑，此負載均衡 轉移路徑之邊的方向必須被反轉，即路徑上的分配邊 變成要求邊6G5，岭求邊魏分配邊。也就是反轉負 載平娜移路經队為)，（4从（&，々)}的方向，反 轉成（4⑹，)，（木，⑹，那㈣便被存取點為 200818945 服務了。第六B圖為執行本發明之負載調整後，第五b 圖之存取點與用戶關係的資源分配圖。 上述範例中’係以一負載均衡轉移路徑來滿足用戶 的服務品質連線請求。此外，也可以在資源分配圖中尋 找負載均衡轉移路控子圖（load balancing shift path sub-graph)。其負載均衡轉移子圖，亦即同時以多條負載 均衡轉移路徑的方式來進行一連串的負載調整操作以滿 φ 足用戶的服務品質連線請求。以下以第六B圖之資源分 配圖為例來尋找此負載均衡轉移路徑子圖。 當用戶&向現役存取點為發出服務品質連線請求 k，現役存取點次必須同時獲得&以及&的頻寬資源 後才能滿足&的請求。此時便選擇以多條路徑的方式同 時將&和&遷徙至其相對應的鄰近存取點(ndghb沉 AP) 4以及4 ’以達到滿足&的品質服務連線請求， _ 11匕即負載均衡轉移路徑子圖，如第七A圖所示。 屬 第七B圖為此例之資源分配圖。其中為滿足此例之 貞躺轉料®之貞辆轉移路㈣將{(知义）， (為，句，（5^2)，（為，从（知4)}反轉成(為，句，（知 為)（〜為），⑷別，亦即同時將用戶&轉移 至存取點馬、用戶&轉移至存取點糸。 18 200818945 以上兩個範射係將本發明制於針式無線通訊 系統中。即中央伺服器擁有所有存取點以及用戶之相關 貧訊，並且在找出負載均衡轉移路徑後也是透過此中央 伺服器來調整存取點間的負載調整。集中式無線通訊系 :統需要額外之中央伺服器的硬體成本。 第八圖是收到服務品質連線要求後，本發明在集中 式無線通訊系統中動態負載均衡的運作流程圖。參考第 _ 八圖’首先，接收一用戶發出的服務品質連線請求，如 步驟801所示。然後判斷該用戶之現役存取點是否可允 許接X該服務品質連線要求，如步驟8〇2所示。是的話， 則回應一成功訊息給此用戶，如步驟8〇3所示。不是的 話，則進行步驟401，建立此無線網路熱點中此多個存 取點與多個用戶間的資源模型和關係，並找出一條負載 均衡轉移路徑，以將該用戶納入該現役存取點之服務的 服務頻寬。最後，如步驟403所示，根據此負載均衡轉 • 移路锃，重新分配網路資源並動態調整此無線網路熱點 中多個存取點間的負載，如IEEE 802.11r之快速換手技 • 術，而提升整體無線通訊系統之頻寬使用效能。 如前所述，當建立此無線網路熱點中此多個存取點 與多個用戶間的資源模型和關係後，先進行尋找可能的 負載均衡轉移路徑，當多於一條負載均衡轉移路徑被發 現時’有許多選擇路徑的方案可以被採用，例如負載調 19 200818945 整後對整體無& ☆ …、、…、點中化費最少資源的那條路徑被 知用或禮碎度最短會被選擇。也可關時以多條 負載均衡轉移路徑的方式來進行一連串的負載調整操作 以滿足用戶的服務品質連線請求。 ; 由於集中式無線通訊系統需要額外之中央伺服器的 硬體成本，本發明也提供了應用於分散式無線通訊系統 中動態負載均衡的方法。無線網路分散式系統其所有的 • 存祕以藉戶f訊冑分散猶存在各鱗取點中，所 以負載均_料彳i的尋找财是透鱗取闕訊息的 交換來達到。此方法是透過泛傳(flGQding)的方式，將尋 找負載均衡轉移路徑的請求轉遞給鄰近的存取點，並找 到一負載均衡轉移路徑。 第九圖是收到服務品質連線請求後，本發明在分散 式無線通訊系統中動態負載均衡的運作流程圖。參考第 9 第九圖，繼步驟⑹2之後，若該用戶之現役存取點不允 許接受該服務品質連線要求時，則以步驟904取代步驟 40卜 在步驟904中，設定限制代價參數一門檻值，並找 出該現役存取點正在服務的用戶中滿足下列兩條件者： 釋放其頻寬資源後，此現役存取點便能服務此請求，（2) 其有鄰近的存取點可聯繫。然後，將尋找負載均衡轉移 20 200818945 路徑的請求(find LB SP request)泛傳至這些鄰近的存取 點。再啟動一計時器T。最後，在計時器T的時間内， 等待回應以一負載均衡轉移路徑。 :根據本發明，此尋找負載均衡轉移路徑的請求中帶 有已追蹤路徑(traced path)、限制代價參數(iimited overhead parameter)、該限制代價參數門檻值、以及相對 應用戶的服務品質連線相關參數(Q〇g parameter)等訊 φ 息。已追蹤路徑帶有此路徑上用戶以及存取點的身份識 別(ID)資訊。此限制代價參數可以是增加額外頻寬限制或 是找尋路徑存取點數限制等。 在汁器T计數完畢後，若這些鄰近的存取點存取 點有收到回應訊息，則選擇此訊息所含的追蹤路徑，若 收到夕個Λ息回應則依其選擇路徑的政策來選擇這些訊 息中追蹤路徑最適合的路徑。依此路經並進行步驟4〇3。 如步驟905所示，若在計時器τ的時間内找到負載 • 均衡轉移路徑’此路徑之最後一個存取點會發出帶有追 • 縱路技的回應訊息。並進行步驟403，於此不再重述。 若尋找時間超過計時ϋ Τ值，而存取點没㈣任何回應 =、、，則回給該發出服務品質連線請求的用戶拒絕服務 σ口質連線請求，如步驟906所示。 21 200818945 值得-提岐’為了有效解決尋找負载均衡轉移路 造成執神麵細微频錄觸轉移路徑 2間錢值Τβ第十圖進—步說明收到—尋找負載均 衡轉移路赠錢，本發_處理流程。 : >考第十圖，首先，該鄰近的存取點接收該尋找負 躺瓣糊绮求，如麵腿麻。接著，調整限 制代價參數，然後判斷調整後的限制代價參數是否仍符 • 合—設定的門捏範嘴内’如步驟1〇〇2所示。不是的話， 則捨棄此尋找負載均衡轉移路徑請求，如步驟麵所 不。是的話，則判斷相對應的該鄰近存取點是否可滿足 已追蹤路徑中即將加入的用戶之所有服務，如步驟 1004 所不。若可滿足，則發出帶有已追蹤路徑為參數的回應 出該路位找哥请求的來源存取點(s〇urce Αρ)，即已 追蹤路徑中的第一個存取點，如步驟1〇〇5所示。若不可 滿足，則進行步驟1006。 在步驟1006中，找出有可聯繫的鄰近存取點之服務 , 中用戶，且該用戶釋放其頻寬資源後，現役存取點便能 滿足已追蹤路徑中即將加入的用戶之所有服務。接著， 調整路徑尋找請求中除限制代價參數外的所有參數，例 如將存取點本身以及相對應用戶加入已追蹤路徑以及更 替相對應用戶之服務品質連線參數等。然後，泛傳轉遞 此請求訊息給這些相對應用戶的鄰近存取點。 22 200818945 同樣地’收到此負载均衡轉移路徑請求訊息的存取 點會依上述的流程操作。依此類推，一直到找到負載均 衡轉移路徑或限制代價參數超出一設定的門檻範疇為 止。以此方式可以有效解決尋找路徑所造成執行時間過 常，並且防止找到過長路徑所造成的調整代價過大等問 題。 惟’以上所述者，僅為發明之最佳實施例而已，當不 能依此限定本發明實施之範圍。即大凡一本發明申請專 利範圍所作之均等變化與修飾，皆應仍屬本發明專利涵 蓋之範圍内。

23 200818945 【圖式簡單說明】 第一圖為一個習知無線網路熱點系統架構的示意圖。 第二圖為一個習知無線網路負載之系統的示意圖。 第三圖是板據本發明之無線網路熱點中動態負載均衡之 * 裝置的一個系統概要圖。 : 第四圖說明第三圖之裝置的動態負載均衡的運作流程。 第五A圖為利用本發明之動態負載均衡的一個範例。 第五B圖為第五A圖的範例應用本發明之負載調整後， # 用戶與存取點間的關係圖。 第/、A圖為第五a圖於負載調整前的一資源分配圖。 第六B圖為執行本發明之負載調整後，第五B圖之存取 點與用戶關係的資源分配圖。 第七A _本發明之貞_紐之—貞柄衡轉移路徑子 圖。 第七B圖為第七A圖之―資源分配圖。 “圖是_服務^躲要錢，本發明在集中式無 線通訊系統中祕貞躺衡的運作流程圖。 第九圖是㈣服務品質魏請求後，本發明在分散式無 線通訊系統中動態負裁均衡的運作流程圖。 第十圖說明收到尋找負載均衡轉移路徑請求後，本發明 的處理流程。 【主要元件符號說明】 24 200818945 STA、Si用戶 -—--- 301資源分配模組 AP存取點 300動態負載均衡裝置 ---—— 3〇3負載調整單元 401建立此無線網路熱點巾此多個存取點與多個用戶間的資 源模型和關係，域出—條«均衡轉移路徑 4〇3根據此貞載均鋪_移路徑’麵分配網路資源並動態調 整此無線網路熱點中多個存取點間的負載 603分配邊 600資源分配圖 605要求邊 801接收一用戶發出的服務品質連線請求 802判斷該用戶之現役存取點是否可允許接受該服務品質連 線要求 803回應一成功訊息給此用戶 904設定一限制代價參數門檻值； 找出該現役存取點正在服務的用戶中滿足下列兩條件 者：（1)釋放其頻寬資源後，此現役存取點便能服務此請. 求，（2)其有鄰近的存取點可聯繫； 25 200818945 將尋找負载^ 點; 啟動一計時器τ; 在計時器Τ的時間内，笼 -~—--一負載均衡轉移路徑 找到負載均衡轉移路徑？ 906拒絕服務品質連線請求

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

Claims (1)

1. 200818945 十、申請專利範圍： 1· -種無線網路熱點中動態負載均衡裝置，該無線網路 熱點中備有多個存取點與多個用戶，當該多個存取點 中有一存取點無法滿足該多個用戶中有一用戶的服務 品質連線請求時，該裝置包含： 一資源分配模組，建立該無線網路熱點中該多個存取 點與該多個用戶間的資源模型和關係，並找出一條負 載均衡轉移路徑；以及 一負載調整單元，根據該負載均衡轉移路徑，重新分 配網路資源並動態調整該無線網路熱點中該多個存取 點間的負載。 2·如申請專利範圍第1項所述之無線網路熱點中動斧負 載均衡裝置’其中該裝置適用於一集中式無線通訊系 統。 3·如申請專利範圍第1項所述之無線網路熱點中動雜負 載均衡裝置，其中該裝置適用於一分散式之無線通訊 系統。 4，如申請專利範圍第2項所述之無線網路熱點中動態負 載均衡裝置，其中該資源分配模組更包括一有向的資 源分配圖來描述該無線網路熱點中該多個存取點與該 多個用戶間的資源模型和關係。 5·如申請專利範圍第4項所述之無線網路熱點中動態負 載均衡裝置，其中該有向的資源分配圖更包括： 一點集合，表示該多個存取點與該多個用戶；以及 27 200818945 一邊集合，係由多個分配邊與多個要求邊所組成，一 分配邊表示一存取點正在服務一用戶，而一要求邊表 示一存取點在一用戶的掃瞄清單中但該存取點沒有在 服務該用戶。 : 6·—種無線網路熱財雜負躺衡方法，該無線網路 : 熱點中備有多個存取點與多個用戶，當該多個存取點 中有一存取點無法滿足該多個用戶令有一用戶發出的 一服務品質連線請求時，該方法包含下列步驟： • 粒該無_路熱财此多個存取點與多個用戶間的 資源模型和_，織出—負__移路徑；以及 根據《載均讎移賴，麵分_職源並動態 調整此無線網路熱點中多個存取點間的負載。 7·如申請專利範圍第6項所述之無線網路熱點中動態負 载均衡方法’其中該方法_於_針式無線通訊系 統。 • 8.如申請專利範圍第6項所述之無線網路熱點中動態負 载均衡方法，其中該方法適用於_分散式無線通 統。 I 9·如申請專利範圍第6項所述之無線網路熱點中動態負 载均衡方法，其中該方法以—快速換手技術來進行該 動_整該無線網路熱點中該多個存取點間的負載。 1〇·如申請專利範圍第6項所述之無線網路熱點中動離負 载均衡方法，其中在找出該負栽均衡轉移路徑之 該方法先進行顧可能的貞_轉移路徑。 28 項所述之無線網路熱點中動態負 立的該多個存取點與多個用戶間 為存取點及用戶間的訊號範圍關 •如申請專利範圍第6 載均衡方法，其中建 的該關係有兩種，一 係另為存取點與用戶間的服務關係。 如申明專概目第6項所述之鱗鱗熱財動態負 載均衡方法’其帽方法有兩種方絲找丨該負載均 衡轉移路，_為採用貞載調整後對整體無線網路熱 點中花費最少魏_條路徑，另—為獅路徑長度 最短’也就是最知戶需要被遷徙的那條路徑。 如申明專利細第6項所述之無線網路熱點中動態負 均衡方法，其中該方法在建立該無線網路熱點中此 多個存取點與多個用戶_資源模型和關係，並找出 該負載均衡轉移路徑之前，更包含下列步驟： 接收該用戶發出的該服務品質連線請求； 判斷該用戶之現役存賴是否可允許接受該服務品質 連線要求;以及 是的話，則回應一成功訊息給此用戶。 如申凊專利範圍第7項所述之無線網路熱點中動態負 載均衡方法，其中該方法是透過一中央伺服器來擁有 該多個存取點與該多個用戶之相關資訊，並且透過該 中央伺服器找出該負載均衡轉移路徑及動態調整該多 個存取點間的負載平衡。 如申請專利範圍第8項所述之無線網路熱點中動態負 栽均衡方法，其中該方法是透過一泛傳的方式，轉遞 200818945 -尋找負载均衡轉移路#的請求到鄰近的存取點，並 找到該負載均衡轉移路徑。 如申明專利範圍第8項所述之無線網路熱點中動態負 載句衡方法，其巾當收到該用戶發出的該服務品質連 ••線請求後，若_戶之赌存取點不鱗接受該服務 > 品質連線要求時，該方法進行下列步驟·· 設定-限制代價參數門播值，找出該現役存取點正在 服務的用戶中滿足釋放其頻寬f源後，該現役存取點 籲便能服務此請求’並且其有鄰近的存取點可聯繫者； 雜尋找貞載均衡娜路徑的請求泛傳轉遞到該找出 之用戶的該可聯繫之鄰近的存取點； 在-計時H T的時_，等細應以—㈣均轉移 路徑;以及 若超過該計時器T的時間，而沒收到任何回應訊息， 則拒絕該服務品質連線請求。 17.如申請專利範圍帛IS項所述之無線網路熱點中動態負 # 載均衡方法’其中該尋找負載均衡轉移路徑的請求中 包括一已追蹤路徑參數、一限制代價參數、一限制代 ( 價參數門檻值以及相對應用戶的服務品質連線相關參 數之訊息。 18·如申請專利範圍第17項所述之無線網路熱點中動態負 載均衡方法，其中當收到該尋找負載均衡轉移路徑的 請求後，該方法進行下列步驟： 若該現役存取點為可滿足該服務品質連線要求之相對 30 200818945 應的該鄰近存取點，且該限制代價參數仍符合一設定 的門檻範疇内時，則回應發送該負載均衡轉移路徑找 尋請求的來源存取點； 找出有可聯繫的鄰近存取點之服務中用戶，且該用戶 釋放其頻寬資源後，該現役存取點便能滿足已追縱路 徑中即將加入的用戶之所有月良務;以及 調整該負載均衡轉移路徑尋找請求中包括之所有該參 • 數’並泛傳該負載均衡轉移路徑尋找請求給該尋找出 之用戶的相對應鄰近存取點。