第一章 緒論 1.1 簡介 無線區域網路可分為基礎式 (Infrastructure) 與隨意型 (Ad hoc) 兩種網路, 基礎式架構的無線網路, 提供無線網路接取點 (Access Point, AP) 通往網際網路 (Internet); 隨意型網路則是因應緊急災難狀況或戰爭通訊發展而成, 因為隨意型網路有自我組態 (self-configuration) 與自我組織 (self-organization) 等特性, 可以在災難發生 缺乏有線網路資源時, 透過各無線節點間自我組織之網路, 達到通訊需求 然而, 基礎式網路裡的每一個 AP, 能提供接取網路的覆蓋範圍有限, 且資料傳輸率隨著距離越遠而降低, 而 Ad hoc 網路正好可以解決有限的傳輸範圍問題, 因此, 一種新的網路技術正在興起, 那就是無線網狀網路 (Wireless Mesh Networks, WMNs), 無線網狀網路利用 Ad hoc 網路的多點跳接 (Multihop) 特性, 將無線 AP 以點對點方式 (Peer-to-peer) 串連起來, 形成無線網路骨幹 (Backbone) 或後端接取線路 (Backhaul), Backbone/Backhaul 上的節點稱之為 Mesh Routers, 一般無線裝置節點則為 Mesh Clients,Mesh Clients 可連接上具有 Gateway/Bridge 功能的 Mesh Routers 節點, 透由 Backbone/Backhaul 多點跳接方式轉送 (Relay) 封包至 Internet, 如此一來, 除了可以延伸 AP 既有的通訊涵蓋範圍之外, 還可以為無線網路服務供應商提供最後一哩 (Last Mile) 解決方案, 如圖 1.1 所示, 無線網狀網路是一種階層式架構, 不同於平面式 (flat) 1
結構的 Ad hoc 網路, 由 Mesh Routers 元件組成的是無線網狀網路的 Backbone 骨幹部分, Mesh Routers 與 Mesh Router Gateway/Bridge 則是形成後端接取線路 (Backhaul), 而 Mesh Clients 的一般無線裝置為 WMNs 最底部的階層, 可以接取 Mesh Routers 連上網際網路或自我形成一般的隨意型網路 Wired Internet Mesh Gateway Mesh Backbone/Backhaul Mesh Routers Mesh Clients Wi-Fi Network Wired Connection Wireless Connection 圖 1.1: 階層式 WMN 示意圖 Microsoft Mesh Networking Summit 2004 提到 WMNs 有四大優點 [14]: 1. 節省安裝成本 以往無線網路服務供應商欲提供無線接取服務時, 必須建置無線網路接取點 AP, 也 就是所謂的無線熱點 (Wireless Hot Spot) 或無線基地台, 基本上, 一個無線基地台所涵 2
蓋的服務範圍, 僅能提供一個或數個無線區域網路使用, 欲保障無線網路能普遍覆蓋住一整個都會區域, 則必須佈建大量的無線基地台, 這對服務供應商來說, 將是一大成本, 因為每一個 AP 都需要有線連接至實體網路, 安裝纜線等基礎設施將增加大量營運成本, 相反地, 建置一個無線網狀網路將可大幅降低安裝及營運成本, 因為無線網狀網路中僅有部分 Gateway 節點連接至有線網路 2. 高傳輸率的大覆蓋範圍 目前無線區域網路技術如 802.11a/b/g 等標準規範, 可利用各種高效率的調變技術 (Modulation Schemes), 支援多種不同資料傳輸率 (Multi-rate), 但是在特定的傳輸功率之下, 要維持高資料傳輸率, 其傳輸範圍會隨之縮小, 因此產生 pico cell 問題, 每一個 AP 所能涵蓋的範圍都是小型的蜂巢式組織, 無法有效擴展無線網路服務範圍, 尤其是戶外的無線網路 而多點跳接的傳輸技術, 能延伸網路傳輸範圍, 加上 WMNs Backbone 中的 Mesh Routers 有著低移動 高電力優點, 所以可以運作在更複雜 資源要求更高的應用技術上, 比起傳統的無線區域網路, 提供距離更遠 資料傳輸率更高的網路 3. 可靠性 無線網路存在許多潛在性問題, 例如, 暫時性因為障礙物或干擾導致節點毀損或路徑斷線, 在單點網路裡, 可能會導致傳輸失敗, 進而中斷網路服務連結, 反觀 WMNs Backbone 在點對點之間提供多重路徑, 一旦發生節點故障或損壞, 可以跳接方式進行修復, 尋找可用之網路節點, 如此一來便可減少單點錯誤與潛在瓶頸鏈結等問題, 大大提高網路傳輸可靠度 4. 自我管理 3
WMNs 擷取 Ad hoc 網路自我管理 (Self-management) 自我修復(Self-healing) 等點對點建立無線分散式網路優點, 因此, 網路設定是自動並且對於使用者是通透的 (trasparent) 例如, 一個新進入 WMNs 網路的節點, 會藉由 Mesh 功能中的自動發現拓樸機制, 尋找其他 Mesh 節點, 加入連結並更新最新路由, 因此, 這樣的網路是容易擴展延伸的 基於以上 WMNs 諸多優勢, 不論學術界或商業團體都競相投入 WMNs 相關研究, 如 MIT 的 Roofnet 是一個 802.11b 的實驗性無線網狀網路 北電網路 (Nortel) 的 Wi-Mesh 商業 WMNs 解決方案, 以及英特爾 (Intel) 思科(Cisco) 主導的 SEE-Mesh(Simple Efficient Extensible Mesh), 目前正由 IEEE 802.11 Task Group S 工作小組制訂 802.11s 標準, 結合 Wi-Mesh 與 SEE-Mesh 兩大陣營所提出的建議書為基礎, 稱為 ESS(Extended Service Set) Mesh Networking 計畫書內容主要在規範以 IEEE 802.11 標準為主的 MAC 協定, 期望提供高速率 支援 QoS 快速換手機制等能力, 建立一個 IEEE 802.11 無線分散式系統 Wireless Distribution System (WDS), 提供之 Mesh 服務內容包括發現與形成拓樸 (Topology) 銜接既有 802.11 網路之網路互連 (Interworking) 安全性 加強延伸 MAC 協定和建議的路由繞送協定等 [23], 工作小組預計 2007 年 7 月發表規格草案, 2008 年 7 月公佈最終標準規格 在 2006 年 1 月 9 日由 802.11 TGs 發佈之 SEE-Mesh 建議規格書的草案內容中, 一 個 WLAN Mesh 的網路拓樸裡, 主要包含以下幾種節點 ( 圖 1.2): Mesh Point MP (MP): 任何提供 WLAN Mesh 服務之節點, 並且能與其他 MP 節點建立鏈結線路 Mesh Access Point (MAP): 除了完整的 MP 功能外, 還加上 BSS 功能, 提供與 STA 節點進行通訊 4
Mesh Portal (MPP): 讓 MSDUs(Mac Service Data Unit) 進出一個 WLAN Mesh 網 路之節點, 可能扮演 802.11b/g 與乙太網路間 (Ethernet) 的閘道 (Gateway) 橋樑 Station (STA): 在 WLAN Mesh 網路之外的節點, 透過 MAP 連上 Mesh 網路 Mesh Portal Bridge or Router MP MAP Mesh Point (MP) Mesh Access Point (MAP) MP MAP STA STA Station (STA) MAP STA MP 圖 1.2:802.11s 網路架構圖 雖然 802.11s 主要在制訂 MAC 與 PHY 層協定標準, 為了讓不同廠商間的產品可以提供最基本網路互通,802.11s 對於路由選擇協定上, 規範一個預設路由協定 (Default path Selection Protocol) 與選擇性路由協定 (Optional Path Selection Protocol) 預設路由協定為 Hybrid Wireless Mesh Protocol(HWMP),HWMP 是一個結合 on-demand 路由與 proactive 主動式路由演算法的 Mesh 路由協定, 其中 on-demand 路由演算法是根據 AODV (RFC 3561)[5] 為主要延伸對象, 除了 AODV 基本路由功能外, 使用 radio-aware path selection metric 作為路徑選擇成本 (RA-AODV), 以尋找最佳路徑 ; 主動式路由則是根據 spanning tree 路由演算法, 以 Mesh Portal 為 tree root 建立一個距離向量 (distance vector) 之路由樹, 對於階層式的 Mesh 網路來說,Tree-based 路由演算法是很有效率, 並且對於拓樸發現與拓樸修復可以減少不必要之路由封包氾濫 5
選擇性路由協定是由各家廠商自行決定是否實作, 該協定是一個 link state 的主動式路由演算法, 結合 Optimized Link State Routing(OLSR)[21] 與 Fisheye State Routing(FSR) [12] 兩種協定, 與 HWMP 一樣使用 radio-aware path selection metric 作為路徑選擇成本, 因此, 稱之為 RA-OLSR 上述提到的 radio-aware path selection metric 在 802.11s 中, 有規範一個預設的 path selection metric 為 Airtime Cost, 其公式如下 : c a = O ca + O p Bt 1 + r 1 e pt (1) 其中 O ca O p 與 B t 為常數, 如表 1.1 所示 輸入參數 r 與 e pt 分別代表在一個 B t 大小 的 test frame 下, 其位元傳輸率 (Mbs -1 ) 與框架錯誤率 表 1.1:Airtime Cost 常數 參數 數值 數值 描述 (802.11a) (802.11b) O ca 75 s 335 s Channel access overhead O p 110 s 364 s Protocol overhead B t 8224 8224 Number of bits in test frame 1.2 研究動機與目的 6
傳統的 Ad hoc 路由演算法中, 有許多是從有線網路的路由演算法改良而成的, 如主動式路由演算法 DSDV(Destination Sequenced Distance Vector) OLSR(Optimal Link State Routing) 等, 這類路由演算法又稱為表格驅動演算法 (Table-driven), 節點週期性的交換彼此之間的路由資訊, 氾濫的廣播資訊, 造成嚴重的 Overhead 問題, 不適合頻寬有限的無線網路環境 ; 因此, 為了解決效能不彰問題, 有了被動式路由演算法 (Reactive), 又稱為需求式路由演算法 (On-demand), 如 DSR(Dynamic Souce Routing) AODV(Ad hoc On-demand Distance Vector) 等, 此類演算法不會定期廣播路由資訊, 只在有傳輸需求時, 廣播封包尋找路徑, 可以有效解決主動式路由的 Overhead 問題, 並提升網路頻寬效能 然而 WMNs 結合了基礎架構 (Infrastructure) 與隨意型 (Ad hoc) 兩種無線網路, 同時也是各種不同接取網路 ( 如 :802.11b/g 802.16 3G) 所組合的異質網路 (Heterogeneous Network), 傳統的無線路由演算法並不適合在無線網狀網路上, 論文 [9] 提到 WMNs 的路由協定必須符合幾項特點, 第一 傳統路由演算法的路由成本 (Routing Metrics) 不適用於 WMNs 的各種網路, 應該使用 Multiple performance metrics, 整合多種衡量單位, 才能找出最佳路徑 ; 第二,WMNs 旨在共享網路資源, 提供一個寬頻骨幹 (Broadband Backbone) 給使用者, 假如 WMNs 網路發生壅塞時, 一個新進入的網路流量可以繞過壅塞路徑, 如此可以達到負載平衡 (Load Balancing), 讓網路資源發揮最大效用 目前 Ad hoc 網路的路由演算法仍使用與有線網路一樣的 Routing Metric, 也就是最小跳躍數 (Minumum Hop Count), 可是最小跳躍數路徑上的鏈結, 有些可以感測到小封包, 卻無法正確傳送資料封包, 或者路徑的部分鏈結其封包遺失率極高, 這是因為無線網路的鏈結品質 (Link Quality) 隨不同的無線電特性 (fading multi-path LOS interference), 而有不同的 Link Quality 因此出現許多取代或改良最小跳躍數方法之論 7
文, 如 [7] [10] 等都是強調無線網路鏈結品質的重要性, 分別提出 ETX(Expected Transmission Count) 與 WCETT(Weighted Cumulation Expected Transmission Time) 兩 種替代傳統最小跳躍數的路由成本計算方法 (Routing Metric) 然而, 論文 [7] 只能在單一網卡 (Single-radio) 的同質網路 (Homogeneous Network) 上找到最佳路徑, 沒有考量到 WMNs 上多網卡 (Multi-radio) 多頻道(Multi-channel) 特性, 在多網卡的無線網路架構下, 由於可設定非重疊頻率之頻道, 這種不互相干擾的特性, 使節點可以同時傳送與接收封包, 當節點的頻道差異值 (Channel Diversity Index,CDI) 越大, 則以該節點為下一個跳躍點的路徑, 效能最好 論文 [10] 改良自 [7] 所提出的 WCETT Routing Metric 可支援多網卡 多頻道的無線網路, 同時還考慮到封包延遲 (Delay) 與效能瓶頸 (Throughput bottleneck) 儘管 Routing Metric 可以找到一條鏈結品質最佳之路徑, 但是 ETX 與 WCETT 卻無法反應 WMNs 網路的壅塞狀況, 以 ETX 或 WCETT 找到的路徑, 因為其鏈結品質最佳, 因此, 當所有流量都傾向於繞送在該路徑上, 就會造成網路壅塞, 產生瓶頸, 導致最後整體網路效能低落, 流量集中在某些鏈結上, 造成其他鏈結過份閒置, 產生公平性問題 (Fairness Problem) 關於 Ad hoc 網路上的負載平衡繞送演算法 (Load-balancing Routing Algorithm) 有很多, 如 LBAR(Load-balanced Ad hoc Routing)[8] DLAR(Dynamic Load-Aware Routing)[17] 等, 但是這些演算法沒有將 WMNs 特性考量進去, 論文 [10] 的 MR-LQSR(Multi-Radio Link-Quality Source Routing) 協定雖然是基於 WMNs 的路由協定, 但是卻只考量到 Intra-flow 流量, 有關 Inter-flow 的訊務流量並未衡量進去, 如圖 1.3,A 至 C 候選路徑有 Route 1 與 Route 2, 其中 Route 2 的中繼點 B 有 Flow 1 和 Flow 2 經過, 可能與 A-B-C Flow 產生 Inter-flow 干擾, 至於 Route 1 僅有本身路徑鏈結干擾 8
圖 1.3:Intra/Inter-flow Interference 示意圖 因此, 以 WMNs 的多網卡 多頻道網路環境之下, 一改傳統最小跳躍數尋找最佳路徑方法, 並以鏈結品質作為新的路由成本, 改良路由演算法, 同時為反應 WMNs 的流量壅塞狀況, 加入 LBAR 的 Inter-flow 概念, 將正在傳送資料的鄰居節點流量考慮進去, 透過 Little s result 排隊理論, 得到一個新的 Routing Metric, 論文最後修改 AODV 路由協定, 透過我們提出的路由成本計算方法, 讓 WMNs 網路可以同時考慮到流量負載與網路鏈結品質, 提高無線網狀網路效能 1.3 章節提要 第二章為相關路由演算法之文獻探討, 包含關於 Link Quality Routing Metric Loading-Aware WMNs 等相關論文研究 ; 第三章介紹我們提出的 MiRii 方法, 一個考量 Intra/Inter-flow 間干擾的新 Routing Metric, 為解決路徑飄移 (Route flaps) 問題, 我們延伸 MiRii 方法為 Flow-based MiRii(F-MiRii), 然後根據我們的設計目標完成修改 AODV 程式 ; 第四章為模擬結果和分析, 我們使用 ns2[22] 為模擬器, 設計三種不同實例, 並與 AODV ETX WCETT 進行比較與分析 ; 最後是結論與未來展望 9