TWI277352B

TWI277352B - Method and system for providing fast handoff in a WLAN-like communication system using active neighboring sets

Info

Publication number: TWI277352B
Application number: TW093129597A
Authority: TW
Inventors: Jia-Ching Shen; Yih-Shen Chen; Chung-Ju Chang; Yung-Han Chen; Yi-Ting Wang
Original assignee: Ind Tech Res Inst
Priority date: 2004-06-22
Filing date: 2004-09-30
Publication date: 2007-03-21
Also published as: US20050282546A1; TW200601856A; US7236786B2

Description

1277352 九、發明說明：【發明所屬之技術領域】么本^月係關於一種在類無線區域網路通信系之陕速又遞系統及方法，尤指在類無線區 :路通信系統中之快速交遞系統及方法設計中：次^吏用主動鄰接組來決定用於轉遞行動服務負訊之快取候選組。【先前技術】 ^現今蜂巢式行動電話網路可提供橫跨一廣大車二的行動終端之間的無線連結，料，使用蜂 ^仃動網路之無線網路連結亦隨之增加。然而蜂巢式仃動網路（如：GSM、GPRS)卻缺乏高速料傳輪的能力。、為了提供無線連結更快速的資料傳輸速率，異質網路是需要的。一個異質網路可包含一個或多個大範圍蜂巢式網路以及數個小型無線區域網路（WLAN)。在異質網路中，WLAN聯結大範圍蜂巢式網路而達到了更高速的傳輸速率。 20 WLAN原為IEEE 802.3乙太網路之一無線延伸，然而，在 IEEE 802.11(802.11a、802.11b、或 8 02.1 lg)中並沒有提出任何定義交遞功能的伊、準。行動台的交遞發生在從起始服務接取點# _ 到鄰接接取點時。再聯結（re-association)程序 1277352 遞）開始連結附近的接取點，於再聯結程序或是交遞程序之後，原本的鄰接接取點即變成新的起始服務接取點。一個有關交遞程序的問題在於交遞所需要時 5 間可能過長。造成交遞時間過長之原因包括：探測（一行動台尋找其鄰近接取點之導引信號 (beacon pilot))、以及接取點與身份認證（AAA; Authentication，authorization, accounting)伺服器之間的後端網路信息程序。AAA伺服器處理連結 10 要求以存取網路資源且提供鑑別、授權、以及帳號服務，AAA伺服器係位於後端網路之中由許多接取點共享。一種用以減少該後端網路信息處理時間之解決方法係為接取點間互通協定（IAPP)。IAPP協定 15 之主要元件係為預先主動快取，預先主動快取發生於當起始服務接取點決定一快取候選組、且將起始服務接取點登錄資料預先傳給快取候選組，使得交遞時後端信息處理時間顯著地減少。快取候選組中的成員係包括位於起始服務接取點鄰接 20 地區之多數個接取點。上述接取點間互通協定係為 IEEE 802_ 1 1 f的一部分。圖1顯示了在無線區域網路協定堆疊架構1 〇〇下之一介於一起始服務接取點及一目標接取點之間的通信協定，無線區域網路通訊協定堆疊架構 1277352 1 Ο 0包括一起始服務接取點1 〇 2、一目標接取點 104、一 ΙΑΡΡ106、一 ΙΑΡΡ108、接取點管理實體 (APME)llO及112、媒介存取控制層管理實體 (MLME)114、115(包括 115a)以及 116、一行動台 5 (STA)118(包括118a)、一快取暫存區120、一快取暫存£ 1 2 2、-鄰接圖1 2 4、控制命令126、128、 130 及 132、一 IAPP 快取通知（Cache.Notify)封包 1 3 4、一 IA P P移動通知封包1 3 6、以及信息1 3 8、 140 、 142及 144 ° 10 一般來說，S T A 1 1 8可為一從一起始服務接取點來存取無線負源之亍動台且在起始服務接取點服務範圍内移動。MLME 114、115及116可位於一接取點範圍中。MLME 1 14、1 15及1 16可處理媒介存取控制層之功能，像是傳送一導引訊框、控制 15 訊框的傳送或是接收、以及指示一 STA與一更高層之聯結/再聯結。 IAPP 106及108各自與ΑΡΜΕ 110及112進行通信，ΙΑΡΡ 106透過控制指令126及128與ΑΡΜΕ 1 10 進行通信，IAPP 108透過控制指令130及132與 20 APME1 12進行通信，控制指令126、128、130及132 係定義於IEEE802.1 1之中。 S T A 1 1 8透過傳送一信息至起始服務接取點 1 0 2或是目標接取點1 〇 4以登錄至接取點，例如：信息142及144個別透過MLME 114及MLME 116傳 1277352 至起始服務接取點1 02或是目標接取點丨〇4。ml ME 1 14經由傳送信息138與ΑΡΜΕ 1 1〇進行通信。 MLME 116經由傳送信息140與ΑΡΜΕ 112進行通 5 一般而言，當s T A 1 1 8離開一聯結起始服務接取點1 0 2之服務區域並交遞至鄰近接取點之服務地區（如目標接取點104)時，STA 1 18可藉由信息 1 44來傳送一聯結或再聯結服務控制指令給目標接取點104。當聯結或再聯結程序結束後，對 10 S T A 1 1 8而言，目標接取點1 0 4成為新的起始服務接取點。尤其是在無線區域網路通訊協定堆疊架構 100中，一行動台（例如：STA 1 18)與起始服務接取點102間建立一連線以與另一行動台（未標示）進 15 行通信。當STΑ Π 8離開一聯結起始服務接取點 1 02之服務區域時（如虛線箭號所示指向右邊）， STA 118(在圖1中表示為STA 118a)會企圖與目標接取點104聯結，並且目標接取點1〇4會鑑定此STA 1 1 8且隨後與起始服務接取點1 0 2通信，使其解除 20 與STA 1 18之連結。為進行起始服務接取點1 0 2與目標接取點1 0 4 間的連線交遞，起始服務接取點102可透過從STA 1 1 8接收一聯結或再聯結控制指令（信息1 4 2)來達成。此時，1 0 2尋找一包括鄰接圖1 2 4之資料的快 1277352 取候選組。在快取候選組中，起始服務接取點1 Ο 2 判定哪一個接取點係位於一鄰近區域、並決定一包括鄰近接取點之快取候選列表。此快取候選列表係包括目標接取點1 〇 4。 5 每個接取點之鄰接圖1 24係為一所有行動台可交遞之鄰近接取點之資訊的集合。 ΑΡΜΕ 110與ΙΑΡΡ 106透過控制指令126及128 進行通信，起始服務接取點1 0 2傳送一 I a Ρ Ρ快取通知封包1 3 4給快取候選列表上的每個接取點，I a P P 1〇快取通知封包1 3 4上載有S T A 1 1 8之先前登錄資料。此先前登錄資料對於鑑定或是登錄程序而言是必須的。 15 當目標接取點104被起始服務接取點通知STA 118可能度遊至其服務區域中，一旦STA 118移至目標接取點1 04之服務區域中，目標接取點1 〇4將成為新的起始服務接取點’並能與$ τ A 1 1 §聯結。換句话说，關於STA 1 1 8之登錄資訊預先被送至目標接取點1 04以減少後端鑑定信息處理程序之時間。在新的起始服務接取點γ θ 乃妖％ ^ (目標接取點104)連結至S T A 1 1 8之後，目標接敌Λ 曰榦接取點104可傳送一 ΙΑρρ移動通知封包1 3 6給起始服務垃、服粉接取點102(現在是舊的起始服務接取點）以通知眉 )、夭原始起始服務接取點 1 02進行交遞初始化。在接价仏a ^ 牡按收封包136時，起始服 20 1277352 務接取點102將轉遞ST A 1 18之剩餘資料，並且隨後將之從起始服務接取點1 〇 2之記憶區中移除。一旦STA 118移至另一服務區域，新的起始服務接取點（目標接取點104)將搜索快取暫存區i22以決定 5 鄰近接取點，並預先傳遞關於S T A 1 1 8之登錄資料至其他可能的目標接取點。在通訊協定堆疊架構1 〇〇中，藉由預先主動快取機制，上述S T A 1 1 8之先前登錄資料係在起始服務接取點102實質開始交遞至目標接取點1〇4之前 iO 傳送至目標接取點1 0 4。然而，上述的IA P P是有缺點的。其中一個缺點是信息氾濫。依據IAPP，起始服務接取點之快取候選列表包括曾經與起始服務接取點完成交遞程序之所有接取點，換句話說， 15 當一行動台原本加入起始服務接取點之服務群中，起始服務接取點將分發IAPP快取通知封包給所有屬於鄰接圖（neighboring graph)上的鄰近接取點。然而行動台可能實際上只往單一方向並移動至其中一個接取點。把不必要的IAPP快取通知 20封包發送給所有其他的接取點將造成信息氾濫的現象。另一個缺點是鄰接圖的認知能力。如上所述，起始服務接取點傳送一 IAPP快取通知封包給所有屬於鄰接圖的鄰近接取點，但是以起始服務 10 1277352 接取點觀點之「鄰接圖」係與行動台的觀點不同。依據一 IAPP學習機制，鄰接圖係從IAPP移動封包的歷史記錄來判定的，換句話說，起始服務接取點透過眾多行動台的許多聯結/再聯結程序而判 5 定一網路拓樸。然而，當每一行動台以其各自單一方向及速度移動，以行動台觀點的網路拓樸可能與接取點判定的網路拓樸不同。甚至，行動台可能移至一個在快取候選列表上但卻未被行動台偵測到的接取點。 _ 10 一般而言，在現存的802.Ilf標準中，交遞延遲（L a t e n c y)主要發生後端網路信息處理中。如果預先完成交遞信息處理，則可能減少信息處理的額外負擔，其結果將是能夠改善交遞延遲（尤其是建立一無線鏈結的延遲）、封包轉遞遺失、以及交 15 遞失敗率。 8 0 2.1 If的預先主動快取機制係依據預先快速儲存交遞登錄資料於可能接取點的概念來設計， φ 以節省當下服務的接取點、目標接取點、及一 AAA 伺服器之間的後端網路信息處理時間。然而在上 20 述的IAPP方法中，預先主動快取候選機制應該小心地選擇以減少信息汜濫及封包傳送的額外負擔。【發明内容】 11 1277352 本發明提供一種方法，俾能提供預先主動快取機制。此方法包括建立一交遞矩陣，其包括複數個接取點於一主動鄰接組中。上述方法亦包括用於主動鄰接組之接收信號品質報告、或傳輸期 5 間之其他行動台相關資訊；依據接收報告調整主動鄰接組之加權因子；以及依據加權交遞傾向參數來決定一快取候選組，其包含每個行動台之主動鄰接組；並在行動台接收的通信信號低於一預定的門檻時，傳送行動台之登錄資料給快取候選 10 組。上述加權交遞傾向參數係依據交遞矩陣及加權因子而定。本發明更提供一種系統，俾能提供預先主動快取機制。系統包括一起始服務接取點以接收量測報告並依據量測報告及交遞矩陣建立一快取候 15 選組。上述系統更包括位於上述快取候選組中之多個鄰近接取點。快取候選組係以一加權交遞傾向參數所決定。本發明其他之目的及優點，將在以下描述中提出，並在這些描述中，很明顯的可看出本發明 20 其他之目的及優點，或可由對本發明之學習而達成本發明其他之目的及優點。本發明之目的及優點，可由申請專利範圍中所特別指出之元件及其組合而瞭解到及得到。 12 1277352 需要瞭解的是，前述之一般描述及隨後之詳述，僅為示範性及解釋性之說明，而非對本發明之設限。 5 【實施方式】以下將詳述本發明之實施例，附圖中示出其中之範例。無論在何種可能之情況下，相同的參考數字將在全部圖示中代表相同或相似之元件。圖2說明無線網路之快速交遞演算法的設計 _ 10 概述200，無線網路是由一些擁有小型覆蓋區域之接取點構成，在無線網路中的行動台其停留時間相對於蜂巢式網路而言是相當短暫的。設計概述 200包括設計元件202、204、206° 設計概述200中第一個設計元件202決定系統 15 模型及考慮的環境特性。設計元件202可能包括一行動台進入含有多數個通訊業者及許多網路系統類型的覆蓋範圍之環境。行動台可量測環境之部 _ 分特性，例如由一個或是多個接取點接收之通信信號強度以判定環境的特性。 20 設計概述200之第二設計元件204決定行動台之可能移動目標，該設計元件根據數個關鍵元件以決定一快取候選組。決定快取候選組之關鍵元件包括一交遞矩陣及一主動鄰接組。交遞矩陣係為一適應性矩陣，該矩陣由優先順序或是行動台 13 1277352 交遞至某一個鄰近接取點的傾向所構成。換句話 - 說，此交遞矩陣產生一表示行動台將會從—特定起始服務接取點進入一特定目標接取點之可能性列表。 5 主動鄰接組通常包括鄰近接取點的資訊，例如：一特定接取點的識別、一接收信號強度值 (如：RSSI)、以及其他行動台相關資訊，俾以正確的加權交遞矩陣中的優先順序值。在設計元件206中設計了一套快速交遞程參 10序。一般來說，快速交遞程序的準備包括了預先主動快取及封包轉遞機制，以提高交遞程序的速度。圖3 - 9更詳細說明設計概述2 〇〇之設計元件基本的概念。 15 圖3說明了一系統3〇〇作為我們考慮的系統模型及考慮的系統環境。系統3〇〇包括—行動台 302、通訊業者3〇4、交換節點306、存取服務節二 _ 3 08、一公眾網際網路310、一安全維護伺服器 312、覆蓋範圍314及接取點316(包括服務接取點 20 3 1 6a(sAP)及目標接取點 316b(tAp))。在圖3中行動台302移入一服務區域（如一虛線 :頭所標示的指向右方）中，在服務區域中一個或疋f個通訊業者304佈設一包含有無線及有線存取；|面之網路基礎建設。對於無線存取介面，服 14 1277352 務存取節點308被佈設用以與行動台302連接。對於有線存取介面，交換節點306(如：一路由器或一第三或第四層的交換器）、公眾網際網路3 1 0以及安全維護伺服器3 12(如：一 AAA伺服器）係被 5 安裝以作為資訊交換及提供安全維護功能之用。每個接取點3 1 6可不用被預先規劃設計佈設於系統3 00之位置，甚至可能位於任意的位置。這些接取點佈設的位置可以在相同通訊業者3 04之覆蓋區域中，甚或位於不同通訊業者之服務區 10 域。每個接取點3 1 6透過服務存取節點3 0 8之連結形成一覆蓋區域314，於覆蓋區域之中行動台3 02 可進行通訊。因為接取點3 16可任意分佈，系統300可包含有三種可能之接取點間的覆蓋關係。例如：如果 15 有一高密度覆蓋區域314形成許多相交覆蓋區域 314，則具有一高度重疊的覆蓋區域。如果有一低密度覆蓋區域314，係有一低重疊覆蓋區域。如果沒有覆蓋區域3 1 4存在，則稱為一無重疊性覆蓋區域。 20 接取點3 1 6的服務區域重疊對於無縫交遞是必須要的。然而，由於碰撞及隱藏節點之問題，將使得重疊會造成系統300的效能退化。無重疊性覆蓋區域可導致傳輸終止、延長交遞延遲時間、封包轉遞遺失、以及暫存器滿溢。同樣的，當系 15 1277352 統300中之多重通訊業者304可能發生的情況下，網路拓樸可能會很複雜。因此，對於一健全的交遞程序而言’ 一個精密之網路拓樸學習機制有其必要性。 5 對於後端網路而言，一個或是多個接取點3 1 6 可相互鏈結至其他的接取點3 1 6。甚至在多個通訊業者中’當網路間交互連結運作（inter-0perabiltiy) 可行時，接取點3 1 6可到達其餘的接取點3 1 6。每個接取點316之更高層的功能實體，會透過安全維 10護伺服器3 1 2來執行一 a A A功能以認證行動台 3 02。在接取點3 1 6之間的信息處理係遵照上述 IA P P通訊協定。舉例來說，行動台302在sAP 31 6a覆蓋區域時，可能發生交遞至tAP的需求。依據系統300之 15 環境’如果一鏈結係由sap 316所建立且行動台 3 02處於待機狀態，則低延遲時間的交遞並非急迫的。由於父遞程序可能在傳輸過程中發生，行動台3 02可能持續的量測sAp 3 16a之一接收信號強度才曰k (R S S I) ’並以糸統3 〇〇之一上傳鏈結回應一 20 sAP 3 1 6a之量測報告。儘管頻率很少，行動台3〇2 也可能量測從其他鄰接接取點的RSSI(如·· tAP 3 16b)。當量測無效時，行動台3〇2也可能量測 RSSI。因此每個行動台3〇2可藉由測量來取得鄰近接取點的則置資訊。 16 1277352 對於交遞程序，一行動台控制的交遞可被用於一以無線區域網路為基礎的網路結構，例如系統3 00。其他預先交遞工作（例如預先主動快取及封包轉遞）係按照行動台3 0 2所接收的量測報告而 5 從sAP 316a執行。再次參照圖2，在設計元件202決定系統模型及環境特性之後，在設計元件204中決定一快取候選組之基本元件。一般來說，加權交遞傾向參數係用於判定快 10 取候選組的成員。加權交遞傾向參數之定義為，其中巧是一交遞矩陣之矩陣元素（如下所述）、且κ是一加權因子。a是用來標示起始服務接取點（οΑΡ)與位於鄰接區域第j個接取點 (tAP)之間的交遞發生可能性的關係（在以下的描 15述中，巧以及有著相同的意義）。^係用來標示從第j個接取點送出並由第i個行動台接收之導引信號強度（在以下的描述中，％及 W㈣有著相同的意義）。同樣的，藉由此報告，如：信號品質或其他行動台特別資訊，如速度或是方向，〜 20 能被逐漸的調整。快取候選組係藉由排序加權交遞傾向參數所判定，且選擇前p個有最大的參數值的成員。在此，數字p表示快取候選組的個數。要注意 1277352 的是，快取候選組數目並未在這描述中限制。然而，適當的選擇這數目可以有效的減少信息氾濫。設計元件204主要針對認識網路拓樸以及判定一交遞候選組（快取候選組）。搜索鄰接接取點的 5 演算法已在上面說明了。然而，除了接收的導引信號強度之外，本演算法可以不使用其他如速度、移動方向、以及位置相關資訊等其他行動台相關資訊，以預測可能的目標接取點。為了更精確的估計交遞候選組以減少信息傳 10 輸的額外負擔，一種與本發明一致的方法及系統係使用一普遍、可擴充的交遞候選組判定機制（快取候選組），其係完整的利用行動台相關資訊。包含於決定快取候選組之基本元件係包括一交遞矩陣及一主動鄰接組。一般而言，交遞矩陣 15 係存於起始服務接取點，其係依據交遞記錄而被建立。換句話說，行動台所使用之目標接取點之過去統計記錄係存於起始服務接取點中。交遞矩陣係為一二維陣列，不但儲存鄰接地區之接取點資訊，而且也儲存這些鄰接接取點之 20 間的交遞關係。接取點之間的交遞關係指出一種行動台從一接取點移往另一接取點的可能性。每一接取點維護其自己的交遞矩陣，使得接取點可鑑別局部的網路拓樸。 18 1277352 交遞矩陣是有適應性的、並且有（Ν+1)χ(Ν+1) 個維度，其中Ν代表已經被起始服務接取點認知的鄰近接取點個數。交遞矩陣包含一額外之行與列以表示這特定起始服務接取點與每個接取點之間 5 的行動台移出（行）與移進（列）的交遞關係。交遞矩陣的每一項係儲存了量化的交遞傾向，其係由一優先順序值所表示。上述優先順序值表示行動台來自一特定接取點且移至另一特定接取點之可能性。交遞矩陣的調整係依據一種學習演算 10 法及一退化演算法以收集包括指示當前的網路拓樸及行動台移動方向的可能性之知識。圖4a闡明了一個索引列表400。索引列表400 包括項目401〇、401!、4012直到401N，其中N為與一特定的接取點（包括起始服務接取點與鄰接接 15 取點）有關之索引數目。每個索引列表400之項目 40 1包含每個對應接取點之網路實體位址或是網際網路協定位址。在索引列表400中由零（0)所索引的項目即為起始服務接取點。索引列表400可能藉由一雙鏈結 20 佇列資料結構來實現，以使得刪除或是增加索引列表4 0 0更加容易。隨著鄰近N個接取點被認知並記錄於索引列表400上，於是建構一個（N+l)x(N+l)的交遞矩陣。圖4b闡明了交遞矩陣402的結構。交遞矩陣402 1277352 包括了從啟始交遞之舊接取點的行（column)，而且標號從401 〇至40 lNg對應圖4a所索引的接取點。矩陣402的列（row)包括編號從401 〇至40 In之目標接取點，此編號係對應圖4a所索引的接取點。矩 5 陣402的每個項目其行與列對應至如索引列表400 所記錄的特定接取點。第一行（或第一列）表示索引數字，並表示服務接取點，因此，第一行（401 〇)表明了行動台源於該服務接取點、且並非一交遞的行動台。列的 10 數目係與一行動台可能會移動的預期目標接取點數目有關。矩陣402之每個項目都是一優先順序值，其表明一特定的行動台將從一特定的接取點移至另一接取點之可能性。舉例來說，一行動台從索引編號40 1 〇之接取點 15 移至索引編號40 12之接取點之優先順序值為1 5。注意因為只有發生交遞的接取點被列入考慮，所以第一列（代表發生交遞的目標接取點是目前的服務接取點）將會是空的（N/A)。交遞矩陣之更新方法控制了矩陣成長、學 20 習、以及退化（因應網路拓樸的改變，可以在未來删除）。圖5闡明一更新方法的流程圖。方法500始於步驟S502之更新程序。一般而言，每一次一個觸發事件發生，交遞矩陣將會更新其中每個元素之值或是增加矩陣的維度。 20 1277352 在步驟S5 04中，演算法500首先檢查觸發事件是否為第一觸發事件。當交遞發生時，如一交遞之行動台係源自一有著未知的網路協定位址或未知的網路實體位址之接取點時，則上述第一觸發 5 事件成立。上述第一觸發事件係由接受舊的服務接取點之交遞要求所觸發。網路協定位址的辨識係與索引列表中的網路協定位址記錄做比較，如果網路協定位址辨識與網路協定位址記錄之間並不符合，則交遞矩陣的成長隨即於步驟S 5 0 8發 10 動。如果第一觸發事件並未發生（例如當網路協定位址已知），則演算法500將移至步驟S5 10檢查是否為第二觸發事件。在步驟S 5 1 0，在交遞過程中，如一行動台係移至一有著未知的網路協定位址或未知的網路實 15 體位址之目標接取點時，此時將會啟動第二觸發事件。例如，當行動台移出服務中的接取點之服務範圍時，行動台會送出一交遞要求給目標接取點，上述目標接取點會與舊接取點設定一安全通道，要求剩餘的封包傳輸，並且中斷舊接取點與 20 行動台之間原本的連結。這將透過IAPP協定（IEEE 802.Ilf)中定義並且於上面圖1中描述的IAPP移動通知封包的程序完成。舊的服務接取點根據接收的交遞通知，將目標接取點之網路協定位址於索引列表中比對。在步驟S508中，如果上述網路協 21 1277352 定位址並未與任何索引列表中的網路協定位址相符，則交遞矩陣將會擴充。如果交遞位址確實符合任何一個網路協定位址記錄，隨後方法500將移至步驟S514之交遞矩陣學習。 5 如果觸發事件不屬於第二觸發事件，方法500 繼續到步驟S 5 1 6。在步驟s 5 1 6中，如果觸發事件屬於第三觸發事件（即退化週期結束），方法5〇〇將執行步驟S 5 1 8之退化演算法。退化演算法是設計用來使接取點的知識適應當前的網路拓樸以及交 10遞事件的統計量，俾使接取點認識的網路拓樸不受過久的資訊干擾。一退化計時器之值設定為 Taging，並且只要定時器時間結束，第三觸發事件將使得交遞矩陣執行退化演算法。如果方法500在特定的步驟s完成之後，進行 15到步驟S5 08、S514、或S518(例如：交遞矩陣成長步驟、交遞矩陣學習步驟、或交遞矩陣退化步驟），方法5 0 0將完成於步驟S 5 2 0。另外，在步驟S 5 0 8之交遞矩陣成長演算法中’索引列表（例如：圖4a中索引列表400)將新增 20 新接取點與其網路協定位址或網路實體位址至列表上。如此，索引列表的長度將會是（N + 2)，並且交遞矩陣的維度將擴增為（N + 2)x(N + 2)。項目 (〇，Ν+1)將被設定為空的（N/A)，並且矩陣的其他 (2N)個新增項目將初始化為〇。其中之一的元素將 22 1277352 會是符合行動台切換的項目，將以初始優先順序值pinit初始化。在長期的統計過程中，pinit的影響將逐漸消失，但會影響優先順序值的收斂性，尤其是在沒有主要優先順序值的情形下。 5 另外，當目標接取點之網路協定位址在索引列表上被找到時，步驟S 5 1 4之交遞矩陣的交遞學習演算法係由步驟S 5 1 2之第二觸發事件所觸發。在這情形下，符合的項目應增加Pine，Pine將與退化演算法一同設計並且係依據此服務區域的交遞馨 10 速度。當交遞速度很大時，Pine將被設計為很小。否則，透過一些退化時間，一很小的增加步驟將使優先順序值失去意義。特別關於交遞矩陣退化步驟S 5 1 8，交遞矩陣每一項目都會減少1。一負的優先順序值係表示舊 15 的服務接取點與目標接取點之間相對應的交遞關係不存在。這退化時間應該被適當的設計使得交遞矩陣穩定並收斂，以反映在本地服務區域中的 φ 交遞關係。除了交遞矩陣外，交遞候選組決定機制（快取 20 候選組）之另一元件是個主動鄰接組。相較於交遞矩陣是記錄長期統計之網路拓樸（與鄰近接取點的交遞關係），主動鄰接組是記錄每個正進行傳輸的行動台（稱為主動行動台）附近可能的目標接取點。 23 1277352 舉例來說，在圖3之中，由於交遞在系統3 00 中係由行動台302所控制，目標接取點316b通常屬於主動鄰接組之中，因為此資訊對於供sAP 3 16a 來預先主動快取行動台3 02的資料是有用的。 5 一主動鄰接組600的結構於圖6中闡明，對於每個主動行動台，主動鄰接組6 0 0位在接取點端。主動鄰接組600包括鄰接接取點的資訊，由節點 602〇至節點602κΚ指出，其中K表示行動台302所偵測之除了服務接取點外的接取點個數。節點602 10 之欄位所包含之資訊為例如特定接取點的識別、接收到的接收訊號強度指示（RSSI)值、以及其他定行動台相關資訊，以將交遞矩陣之優先順序值予以加權，其中一資訊加權因子可給予行動台的移動方向更精準的預測。 15 主動鄰接組600可為一鏈狀資料結構，其包括數個代表鄰近接取點的節點602，行動台可接收或探測到訊號並量測列表上鄰近接取點的RS SI值。節點60 2〇代表當前服務中的接取點，且其他節點 6 0 2 i至節點6 0 2 κ係為鄰近接取點。 20 當一行動台與接取點間的連結建立後，行動台回報掃瞄所有鄰接的接取點之量測結果，這些資訊可以包含連結建立前的量測資訊。在傳輸期間，行動台持續的量測並回報服務中的接取點之信號，並且可能的話，偶而量測並回報來自鄰近 24 1277352 接取點的資訊。當創造一節點602時，資訊加權因子是與RSSI值相對應的，例如信號愈強、行動台會在交遞發生時移至上述接取點的可能性就愈南。 5 依據接收自sAP及其他接取點訊號的量測報告，sAP依據以下程序更新資訊加權功能。如果tAP 報導的RSSI值是漸增的，則隨後一資訊加權因子 (W(tAP))也增加Aw。另一方面，如果回報的RSSI 為遞減，則加權因子會減少Aw。馨 10 另外，對於行動台而言，在傳輸期間主動鄰接組的量測報導並非一定可行的。為了避免過舊的資料影響候選快取的判斷，退化機制使資訊加權因子適應行動台當前量測的狀況。每一次退化計數器數到零時，主動鄰接裝置加權因子將由主 15 動鄰接組減少wage，直到加權因子為零為止。如果更多的資訊是需要的，例如位置資訊或是移動方向，上述資訊加權因子將會依據額外的資訊修 φ 正，以利更準確的目標接取點之預測。再次參照圖2，在設計元件204之關鍵元件決 20 定快取候選組後，設計元件206實行一快速交遞程序，使得一例如圖3的系統3 0 0之無線區域網路類型系統能夠讓一行動台從起始服務接取點更有效率地交遞至目標接取點。 25 1277352 圖7為方法7 Ο 0的流程圖，用以從接取點的觀點來進行交遞程序的準備。交遞程序的準備包括預先主動快取機制及封包轉遞以提升交遞程序的速度。 5 在行動台端進行的交遞動作是登錄至目標接取點，但並不包含結束與原始服務接取點的連結。當新的目標接取點從行動台接收交遞要求，目標接取點將會進行交遞程序、建立一無線鏈結、要求舊的服務接取點執行封包轉遞、以及要 10 求舊的接取點結束連結。在步驟S702中，一 sAP接收一量測報告來獲得行動台測量之鄰近接取點（包含服務中的接取點）的RSSI值。在步驟S704中，如果行動台的量測報告顯示 15 與sAP之訊號RSSI值未減小，則與sAP的連結是繼續的，而且方法7 0 0直接執行結束步驟S 7 1 6。如果行動台量測之服務接取點的RSSI值減小，則方法 700將進入步驟S706。在步驟S706中，RSSI值係與一用於預先主動 20 快取機制之第一交遞門檻值（ThprQ)比較。如果 RSSI值低於Thpr。，則方法700繼續到步驟S708。如果RSSI不低於Thpr。，則方法700進入結束步驟 S716 ° 1277352 在步驟S708中，RSSI值係與一用於封包轉遞之第二交遞門檻值（Thf()r)比較，如果RSSI值係低於ThfQr，則方法700繼續到步驟S714，其係為一初始化從SAP到tAP之轉移的封包轉遞程序。如果 5 RSSI不低於ThfQr，則方法700進入步驟S710(方法 7 〇 0選擇一快取候選組）。步驟S704及S706的目的是為了讓RSSI值與第一及第二交遞門檻比較，此二交遞門檻係分別為預先主動快取門檻Thpr。及封包轉遞門檻Thfcr。如 10果R S SI係低於預先主動快取門檻，但卻大於封包轉遞門檻，則將發動預先主動快取機制（步驟 S710)。在步驟S 7 1 0，此預先主動快取機制包含有兩個步驟：一預先主動快取程序及一快取候選組的 15選擇。預先主動快取程序是依據IAPP協定，尤其是 IEEE 802.1 If。在步驟S 7 1 0中，快取候選組的選擇始於一遮罩運作。如同上面所提到的，在預先主動快取機制開始之前，如果源自服務接取點的信號品質持 20續的下降，則接取點將初始化預先主動快取機制。其中一個原因是行動台正在離開接取點且預先主動快取機制是合理的。當RSSI值落入觸發範圍（如低於第一及第二交遞門檻值），遮罩運作選擇了具有良好信號品質的接取點，此等接取點可由 27 1277352 行動台所探測、且由服務接取點確定是在相同的通訊業者中（例如圖3中的通訊業者304)。、遮罩運作在接取點索引列表與行動台的主動鄰接組之間，經由一「聯集」運作取得一交遞候 5選組Ke。遮罩運作可選擇最佳信號品質的接取點’以於一多個通訊業者的環境中提供持續的服務。

在步驟S 7 1 2中，在服務接取點決定交遞候選組（He)之後，它經由一最大加權運作來估計最適當 10的目標接取點。最大加權運作藉由以下步驟S而取得快取候選組Ke : 1·藉由(或是等效於妨計算每對（〇Ap、tAp) 的加權交遞傾向係數； 15 2 · 指派可以快取的接取點個數（亦即：p); 3. 計算 ξ = ;

4. 將ξ加入Kc中，並從Hc中移除ξ ; 5 · 將ρ減少1 ;以及 6· 如果Hc仍有接取點存在並且ρ>〇，重複第 20 3步驟繼續尋找ξ。最大加權運作可選擇有最大值的接取點ξ，最大值係為相對應於在交遞矩陣中優先順序值 P(〇AP，new ΑΡ)與資訊加權因子w(tAP)的乘積。 Hc#為一暫時集合，其包括在索引列表4〇1及主動 28 1277352 鄰接組600上的所有鄰近接取點。每次一接取點被找到並加進入Kc中時，則將其從Hc中移除。快取接取點的個數p係為一系統參數，該參數與網路的 "ί吕息處理負擔及封包轉遞效能有關。 5 在決定Ke後，將以Ke為鄰接圖來執行預先主動快取程序。在預先主動快取程序中，IAPP功能實體將行動台的個人資料（profile，或稱為 context )給每個在快取候選組Ke中的接取點。需注意的是，如果p設為1或是對鄰近接取點沒有額 10 外可行的行動台報告時，預設快取機制是經由以來簡單地選擇接取點而執行。這樣的設計可確保本快取候選選擇演算法的可信度。關於步驟S 7 1 4之封包轉遞的初始化，當接收到的RSSI減小且低於封包轉遞門檻Thf()r時，封包 15 轉遞程序將在交遞程序之前先實行。如同上面所提到的，預先執行封包轉遞程序將會大量減少交遞延遲、封包轉遞遺失及暫存器滿溢之機率。關於行動台控制之交遞機制，在無線區域網路為基礎的系統中，行動台控制交遞是預設機 20 制。如果源自服務接取點接收之信號品質過低無法繼續傳輸，則行動台將偵測其他接取點並嘗試與最佳的接取點建立連線。圖8闡明了一交遞程序之流程圖，上述交遞程序係在行動台交遞要求之後於接取點進行。此流 29 1277352 程包括於取符合程序 (cache-hit)(亦即：match)、以及一快取不符合 (mis-matched cache)程序皆包括在内在步驟S802中，一桩敗點你卜雖取點從一仃動台接收一交遞要求。依據從行動台接收之交遞要求，接取點於步驟S804中查詢一快取列表。如果_快取項目符合，則在步驟S806中，與交遞行動台的無線連結將直接建立而無安全維護伺服器3丨2之認

證。同時，在步驟S808中，新的接取點傳送iAfp ίο 15 20 移動通知封包給舊的接取點，請原本服務接取點轉遞剩餘封包必將原本的連結結束。方法隨之進行到結束步驟S 8 1 0。如果沒有快取的個人資料（context)符合，則隨之於步驟S812、S814及S816中，連結將重建為一新速結。在步驟S 8 1 6將連結建立後，方法8 〇〇將進行刻結束步驟S 8 1 0。

圖9係為一符合本發明之方法900的流程圖。所有上述由起始服務接取點完成的動作將列於此流輕圖中，在步驟S902中，一本地橋接器依據儲存其中的交遞記錄建構一交遞矩陣。步驟S904中，當聯結行動台之通訊品質低於一第一預定門檻時，起始服務接取點由一行動台接收所有主動鄰接組中的接取點信號品質的報 30 1277352 告。主動鄰接組可包括那些導引信號被偵測的接取點，行動台把量測結果回報給起始服務接取點。在步驟S906中，起始服務接取點依據接收報告調整加權因子。交遞矩陣之外的加權因子係為 5 一加權交遞傾向參數的元素。上述加權交遞傾向參數係判定一快取候選組。在步驟S908中，如果行動台之通信品質係低於一第二預定門檻時，則起始服務接取點藉由加權交遞傾向參數決定快取候選組。這發生在當起 10 始服務接取點之導引信號的信號品質低於第一門檻時，行動台回報起始服務接取點以初始化預先主動快取機制。在步驟S 9 1 0中，起始服務接取點傳送行動台的登錄資料給所有在快取候選組中的接取點。 15 表1顯示比較IAPP及本專利所提出的方法、系統、及演算法之信息額外負單效能的模擬結果。模擬環境係在曼哈頓街道模型，其中接取點係散佈於轉角處。可以看到的是與本發明一致的系統及方法藉由加權功能（的幫助能夠大量的減 20 少信息處理的額外負擔。所提出的演算法之延遲時間與IAPP之延遲時間幾乎相同，包括當P = 1的情形。與本發明一致的系統及方法藉由加權功能的幫助能準確的找到大部分適合的交遞目標接取 31 1277352 點，所以信息氾濫的問題，與其他專利中所提到的其他相關問題都能被能被改善。 &胃(所提出的演算法/IAPP) P=1 P=2 P=3 P=4 額外負擔％ 25% 50% 75% 100% 延遲(時間） 8.22 3.85 1.19 1 有wB： ^Cifj (βί：堤出的演3 m/iA??) P=1 P=2 P=3 P=4 額外負擔％ 25% 50% 75% 100% 延遲(時間） 1.01 1.01 1 1 5 表1 : IAPP及所提出的演算法之模擬結果另一本發明之實施例係利用一快速交遞演算法之專用短程通信（D S RC)系統。本專利針對用於多通訊業者、以無線區域網路為基礎的系統環 10 境，所提出之快速交遞方案的一般性架構能完整的應用在D S RC系統中。在D S RC系統的環境特性之下，圖3中的接取點與行動台將改成道路單元 (RSU)及車上單元（OBU)。OBU能透過在控制通道中的RST封包掃瞄RSU的RSSI值。 15 一個DSRC系統是一個無線區域網路類型的系統，其設計主要可用以提供公眾區域網路的高速度交遞程序。該系統之實體層與媒介存取控制層與8 0 2.1 1 a標準相容。通道結構被修改以加快掃瞄程序，其中定義有一個總體控制通道與六個服務 32 1277352 通道。一個延申-媒介存取控制層被加在原有的媒介存取控制層上。一個行動台的交遞只發生在當連線傳輸正進行的過程中（在一服務通道）。在這情況下，傳 5 輸中的STA能持續從服務RSU量測RSSI值且於上傳時回應此報告。然而，由於對其他RSU的掃瞄只能在控制通道中執行，從一主動鄰接組中其他成員的RSSI值的報告並非總是可行的、或並不需要日夺常更新。這是藉由依據在交遞矩陣之RSU中 10 的長期交遞關係來預測候選者而予以克服。雙門檻預先主動快取及封包轉遞初始化機制係位於RSU端且完全由服務RSU所控制。另一方面，實質上的交遞動作是由行動台所執行的。這些特徵是完全相容於DSRC系統的。 15 上述實施例僅係為了方便說明而舉例而已，本發明所主張之權利範圍自應以申請專利範圍所述為準，而非僅限於上述實施例。【圖式簡單說明】 20 附圖亦併入本發明中，並組成說明書之一部份，其示出本發明之一些實施例，附圖及其說明，解釋了本發明之原則。於圖式中：圖1說明一無線區域網路通訊協定堆疊架構。 33 1277352 圖2說明實施例的三個設計元件以提供不同環境下的交遞。圖3例舉一與本發明相符的系統。圖4a及4b說明一與本發明相符的索引列表及交遞 5 矩陣。圖5為本發明一實施例之更新交遞矩陣之方法流程圖。圖6為本發明一實施例之主動鄰接組之資料結構圖。 ⑩ 10 圖7係本發明一實施例之判定預先主動快取機制開始之方法與封包轉遞程序流程圖。圖8係本發明一實施例之接取點端交遞程序流程圖，接取點端包含有有快速交遞能力。圖9係本發明一實施例之快速交遞之方法流程 15 圖，能在不同環境下運作。【主要元件符號說明】 φ 無線區域網路協定堆疊架構1 00 起始服務接取點1 02 目標接取點1 04 20 IAPP106、108 行動台（STA)118、118a 接取點管理實體（APME)llO、112 媒介存取控制層管理實體（MLME)114、115、 115a 、 116 34 1277352 快取暫存區120、122 鄰接圖124 控制指令 126、 128、 130、 132 IAPP快取通知封包134 IAPP移動通知封包136 5 信息 138 、 140 、 142 、 144 設計概述2 0 0 設計元件202、204、206 系統3 0 0 行動台3 0 2 通訊業者304 交換節點306 _ 10 存取服務節點3 0 8 公眾網際網路3 1 0 安全維護伺服器3 1 2 覆蓋範圍3 1 4 接取點 316 、 316a 、 316b 索引列表400 項 g 401〇、401 1、4012"·401ν 15 交遞矩陣402 主動鄰接組600 節點 602〇·" 602κ 35

Claims

1277352 十、申請專利範圍： 1 . 一種在一通信系統中提供預先主動快取之方法，該方法包括：建構一交遞矩陣，其包括一主動鄰接組紀錄多 5 個鄰近接取點；接收主動鄰接組所列接取點之信號品質報告；依據接收之訊號品質報告而調整該主動鄰接組之加權因子；依據一加權交遞傾向係數與主動鄰接組以決 · 10 定一快取候選組；當該行動台接收之信號強度係低於第一門檻時，服務接取點將傳送行動台之登錄資料至決定之快取候選組；以及當該行動台接收之該信號強度低於第二門檻 15 時，轉遞行動台之剩餘資料至該快取候選組；其中該加權交遞傾向係數乃依據該交遞矩陣及對應之加權因子所建立。籲 2.如申請專利範圍第1項所述之方法，其中，該交遞矩陣更包括一更新演算法。 20 3 .如申請專利範圍第2項所述之方法，其中，該更新演算法包括使交遞矩陣成長、交遞矩陣學習、交遞矩陣退化之功能。 4 ·如申請專利範圍第1項所述之方法，其中，該交遞矩陣係為一二維陣列，該二維陣列儲存接 36 1277352 取點之間的關係，包括主動鄰接組中接取點之間的關係。 5 .如申請專利範圍第4項所述之方法，其中，該交遞矩陣係使用一索引列表，該索引表包括起 5 始服務接取點之鄰近多個接取點的位址訊息。 6. 如申請專利範圍第1項所述之方法，其中，該交遞矩陣係依據交遞記錄而進行更新。 7. 如申請專利範圍第1項所述之方法，其中，該加權交遞傾向係數為，當中C為一交馨 10 遞矩陣之元素且化為一加權因子。 8 .如申請專利範圍第7項所述之方法，其中， C係用於表明一起始服務接取點與一位於索引列表第y·接取點之間的關係。 9 ·如申請專利範圍第8項所述之方法，其中， 15 I的取得係依據行動台相關資訊，其包括一由第）接取點傳送，並由第/行動台接收之導引信號強度。籲 1 〇.如申請專利範圍第9項所述之方法，其中，〜係依據該接收信號強度或其他行動台相關 20 資訊而逐漸調整。 1 1.如申請專利範圍第1項所述之方法，其中，該第一門檻係與一預先快取門檻有關，該第二門檻係與一封包轉遞門檻有關。 37 1277352 1 2.如申請專利範圍第1項所述之方法，其中，該方法適用於一專用短程通信（DSRC)系統。 1 3 . —種在一通信系統中提供預先主動快取之方法，該方法包括： 5 一服務接取點（serving AP)接收由一行動台量測多個鄰近接取點之信號強度特性；依據該信號強度決定一快取候選組，其係為多個鄰近接取點之加權列表；以及傳送關於該行動台之登錄訊息至列於該快取 10 候選組之該接取點。 1 4 .如申請專利範圍第1 3項所述之方法，更包括依據該快取候選組、一行動台交遞至其中一個鄰近接取點的過程。 1 5 .如申請專利範圍第1 4項所述之方法，其 15 中，預先主動快取步驟S發生於當該行動台與起始服務接取點之連結訊號強度低於第一門檻。 1 6.如申請專利範圍第1 5項所述之方法，其中，轉遞步驟S發生於當該行動台與起始服務接取點之連結訊號強度低於第二門檻。 20 1 7.如申請專利範圍第1 6項所述之方法，其中，該第一門檻係與預先主動快取機制有關，第二門檻則與封包轉遞有關。 38 1277352 1 8 .如申請專利範圍第1 7項所述之方法，其中，決定該快取候選組係根據一加權交遞傾向係數。 1 9.如申請專利範圍第1 8項所述之方法，其 5 中，該加權交遞傾向係數係依據一交遞矩陣及加權因子。 2 0.如申請專利範圍第19項所述之方法，其中，該交遞矩陣包括一主動鄰接組並使用一索引列表。 ⑩ 10 2 1 .如申請專利範圍第20項所述之方法，其中，該加權傾向係數為，當中巧為該交遞矩陣之一元素且仏為該加權因子。 22. 如申請專利範圍第2 1項所述之方法，其中，巧係用於表明一起始服務接取點（oAP)與一位 15 於一鄰接地區之第尽#接取點（tAP)之間的交遞關係。 23. 如申請專利範圍第22項所述之方法，其馨中，K係用於表明一由第y·接取點傳送且由第ί行動台接收之導引信號強度。 20 24.如申請專利範圍第23項所述之方法，其中，扎係依據該接收信號強度而逐漸調整。 2 5 . —種提供預先主動快取機制之系統，包括： 39 1277352 一起始服務接取點，係接收量測報告並依據該量測報告及一交遞矩陣而建立一快取候選組；以及多個鄰近接取點，係包含在該快取候選組之 5中；其中該快取候選組係依據一加權交遞傾向係數來決定。 2 6.如申請專利範圍第25項所述之系統，其中，該加權交遞傾向係數係依據一交遞矩陣及加 10 權因子。 2 7.如申請專利範圍第26項所述之系統，其中，該加權交遞傾向係數為，當中巧為該交遞矩陣之一元素且％為該加權因子。 2 8.如申請專利範圍第27項所述之系統，其 15 中，巧係用於表明一起始服務接取點（〇 A P)與一位於一鄰接地區之第y·沒#接取點（tAP)之間的交遞關係。 2 9 .如申請專利範圍第2 8項所述之系統，其中，〜係用於表明由第y·接取點傳送且由第/行動台 20 接收之導引信號的強度、或第/行動台之其他行動台相關資訊。 30.如申請專利範圍第29項所述之系統，其中，仏係依據該量測報告而逐漸調整，當中該量 1277352 測報告包括接收表明之信號強度或其他行動台相關資訊。

41