IEEE 802.11/802.16無線網路的MAC機制為儘可能爭取傳輸機會，此機制於壅塞的網狀網路環境中將造成傳輸速率過高及非必要封包碰撞的問題，進而嚴重降低網路傳輸效能。 / 本篇論文的目的旨在改善無線網狀網路環境中，因IEEE 802.11/ 802.16本身的MAC機制所導致的效能低落問題。我們利用賽局理論中零和賽局以強化競爭方式並計算及應用合理傳輸機會(Transmission Opportunities)及傳輸時機(Transmission Timing)，再依此將傳輸速率調降至合理的數值以降低無效封包的傳輸率。同時，此傳輸機會及傳輸時機將作為路徑選擇的重要依據。末了，我們利用網路模擬器NS2 (Network Simulator ver. 2)驗證及評估本論文所提出之方法的效能。 / The MAC mechanism of IEEE 802.11 and 802.16 competes as much transmission opportunities as possible. In a congested wireless mesh network, this greedy competition will result in inappropriate data rates and unintentional packet collision problems, and thus reduce network performance seriously. / The objective of this research is aimed to solve these two problems to enhance the performance of wireless mesh networks. We propose a zero-sum-game based contention-enhancement in MAC mechanism to estimate rational transmission opportunities and transmission timing dynamically. These estimations will then be used in reducing unsuitable packet data rates and selecting better routing paths. At last, we use NS2 (Network Simulator ver.2) to evaluate the system performance of our proposed methods.

近年來興起一個前瞻性無線技術，稱之為無線網狀網路（Wireless Mesh Networks；WMNs） 以所費低廉方式提供無線網路最後一哩存取Internet，同時具備ad hoc網路全部優點。例如自我組織（self-organization）、自我組態（self-configuration）等。而802.11協議已經納入802.11s草案。雖然802.11的實體層支持多元速率，大多數研究為了簡化多假設在單一速率的情況下。但事實上，802.11可以支援的Automatic Rate Fallback (ARF)多元速率演算法；換句話說，由於信號雜訊比和資料錯誤率的不同，資料傳輸速率將自動調整。在這裡，我們假定在WMNs上使用 802.11協定，並且考慮路徑容量，延遲，流量公平及多元速率多跳接的環境。為了設法指出和改善這方面的議題，我們提出了經由改進802.11競爭視窗和加權公平調度機制的跨階層設計。透過一系列的模擬指出問題並找出合適的解決方案。結果顯示，如果增加低速率連結的優先權和考慮流量公平問題，容量及延遲將得到改善。 / A new promising wireless technology has emerged recently, called wireless mesh networks (WMNs). WMNs are an inexpensive way to provide wireless last-mile broadband Internet access and have all the advantages of ad hoc networks, such as self-organization, self-configuration. IEEE 802.11 MAC protocol has been adopted in 802.11s draft. Although IEEE 802.11 physical layer supports multiple rates, most researches assume single rate environment for simplicity. However, in reality, 802.11 adopts automatic rate fallback (ARF) multi-rate algorithm. In other words, the data rate will be automatically adjusted due to its signal-to-noise ratio, or error rate. Here, we assume the fitness of IEEE 802.11 over WMNs, and considering path capacity, delay, flow fairness, in multi-hop multi-rate environments. They all are affected by data rates on the links along the path. In order to address and improve the above issues, we propose a cross layer scheme which is modified by the contention window of IEEE 802.11 DCF MAC and weighted fairness scheduling mechanism. We point out the problem and find out the suitable solution via a series of scenarios simulations. The results show that if increasing the priority of the low data link and taking care about flow fairness problem, the capacity and delay will be improved.

本論文對IEEE 802.16 協調分散式之網狀網路提出一允入控制之演算法。在此類網路中，控制子訊框交換各站台之排程訊息，並預留資料子訊框之時槽作為實際資料傳輸之用。我們利用令牌桶機制來控制網路訊流之流量特徵，如此可簡單的估計各訊流所需之頻寬。我們使用了所提出的頻寬估計方法，並一起考慮各訊流之跳接數與延遲時間之需求，提出的允入控制演算法能夠保證即時性串流之延遲時間需求，且可避免低等級訊流發生飢餓情形。模擬結果顯示，所提出的允入控制方法可以有效的把超過延遲時間需求之即時性訊流封包數目降低，並且低等級訊流在網路負載大時仍然可以存取頻道。 / We propose a routing metric (SWEB: Shortest-Widest Efficient Bandwidth) and an admission control (TAC: Token bucket-based Admission Control) algorithm under IEEE 802.16 coordinated, distributed mesh networks. In such network architectures, all scheduling messages are exchanged in the control subframes to reserve the timeslots in data subframes for the actual data transmissions. The token bucket mechanism is utilized to control the traffic pattern for easily estimating the bandwidth of a connection. We apply the bandwidth estimation and take the hop count and delay requirements into consideration. TAC is designed to guarantee the delay requirements of the real-time traffic flows, and avoid the starvation of the low priority ones. Simulation results show that TAC algorithm can effectively reduce the number of real-time packets that exceed the delay requirements and low priority flows still can access the channel when the network is heavily-loaded.

本研究在減低Wimax mesh mode環境中media access階段會造成的delay現象。我們發現當subscriber station (SS)訊務繁忙時，競爭transmission opportunity (TO)以及3-way handshake的過程容易失敗，造成傳輸效率降低，封包的delay也會增加。同時我們也發現封包的延遲還來自minislot的不良配置。因為原始的Wimax mesh mode對於minislot的配置會造成預約過晚的問題，當預約時間被延長，資料就必須無條件的增加等待時間，因此我們將針對這些問題進行改善，降低在訊務繁忙的狀況下，傳輸效率低落的問題。 我們使用兩種方式來改善上述的問題，其一是由Bayer [4]所提出的動態調整holdoff指數(dynamic holdoff exponent)的方式，藉由調整holdoff指數的大小來縮短holdoff時間，以縮短傳輸延遲；另外，我們也提出一個以節點的臨接區域為配置基準(Neighborhood-Based Minislot Allocation, NBMA) 的方法，透過與其相鄰的節點交換訊息，優化minislot的配置。我們用這兩種方式減少IEEE 802.16中媒體存取階段所造成的傳輸延遲。 實驗結果顯示，在網路負載較輕的情況下，NBMA可以有效的將delay降低為原來的七分之一，改善幅度將近85%，抖動率(jitter)的部分亦有20%的改善，並略為提高傳輸效能8%左右；而當網路負載較重時，delay的改善程度仍有40%左右，jitter部分改善了12%，傳輸效能亦有6%的改善。證明了我們的方法確實可行，並且在改善delay方面有顯著的效果。 / IEEE 802.16 mesh network is a new environment of wireless network. It was designed as a self-organized, distributed scheduling, and multi-hop network. However, it is not robust enough to handle a heavy loading environment for lacking of QoS support. Our research is trying to reduce its media access delay, which comes from both TO (transmission opportunity) competition and improper minislot allocation. TO competition will extend the MSH-DSCH (mesh distributed scheduling) interval and slow down the exchanging speed of control message. Improper minislot allocation comes from the distributed scheduling of minislot. When a subscriber station (SS) allocates too much minislot for low-level traffic, it will defer the allocation of other neighbors’ high-level traffic. We use Bayer’s [4] dynamic exponent to reduce holdoff time of SS, and speed up the exchange of control message. On the other hand, we design an “importance factor” (IM-factor) to score the importance of request. Through the exchange of IM-factor, SS and its neighbors will produce a threshold of IM-factor to filter the unimportant requests, and prevent minislot from being assigned too late. In our experiments, the proposed methods can reduce 85% delay and 20% jitter, and increase bandwidth utility by 7%. It shows that our method in reducing transmission delay is pratical and effective.

近年來興起一個前瞻性無線技術，稱之為無線網狀網路（Wireless Mesh Networks），WMNs 以所費低廉方式提供無線網路最後一哩存取Internet，同時具備ad hoc 網路全部優點，例如自我組織（self-organization）、自我組態（self-configuration）等。儘管WMNs 骨幹部分與平面式ad hoc 網路相似，多網卡（multi-radio）的Mesh Routers 節點卻是固定不動且沒有電力限制。有鑑於此，設計於ad hoc 網路上之路由協定並不適合於WMNs。 WCETT（Weighted Cumulated Expected Transmission Time）metric 考量到intra-flow 干擾，卻未捕捉到inter-flow 干擾；而LBAR（Load-Balanced Ad hoc Routing）協定以計算節點之活躍值（nodal activity）與訊務流量干擾選擇路徑，並無支援多網卡路由，LBAR 可以在單一網卡環境表現良好，在多網卡環境卻不一定。因此，我們提出一個WMNs 上考量到Intra/Inter-flow干擾之多網卡路由協定，稱為MiRii。模擬結果顯示出我們路由協定可以改善網路效能，包含了封包成功傳送率及平均點對點延遲。 / A new promising wireless technology has emerged recently, called wireless mesh networks (WMNs). WMNs are inexpensive way to provide wireless last-mile broadband Internet access and have all the advantages of ad hoc network, such as self-organization, self-configuration. Although WMNs backbone is similar to flat ad hoc network, mesh routers with multi-radio are stationary and have no power constraints. As a result, routing protocols designed for ad hoc network may not be appropriate for WMNs. The WCETT (Weighted Cumulated Expected Transmission Time) metric takes intra-flow interference into consideration, but does not capture inter-flow interference. LBAR (Load-Balanced Ad hoc Routing) calculates nodal activity and traffic interference for choosing a path, but does not supporting multi-radio. LBAR may be perform well in single-radio environment, but do not perform as well in multi-radios. Consequently, we incorporate a new Multi-Interface Routing with Intra/Inter-flow Interference in Wireless Mesh Networks, called MiRii. The simulations show that our routing protocol can improve the network performance including the Packet Delivery Ratio and average end-to-end delay.

近年來無線網狀網路(Wireless Mesh Networks)備受矚目，無線網狀網路繼承原有的ad hoc networks的特性並提供階層式及多網卡的網路存取架構。在multi-hop networks下，傳輸功率的控制和網路路由的選擇是重要的議題，因為不同的傳輸功率產生不同的網路拓墣連結性和干擾。此外，在不同網路卡間的路由選擇也會產生不同程度的intra/inter-flow 干擾。這些特性對網路效能有密切的影響，過去相關的路由協定設計也大多未同時考量傳輸功率控制與多網路卡的特性。 在這篇論文中，我們提出了跨網路協定層的路由協定，稱作M2iRi2，同時考量傳輸功率的控制並將Intra/Inter-flow的干擾導入到路由路徑的選擇。節點上的網路卡在物理層(Physical layer) 計算目前對潛在可容忍的新增干擾，並將此訊息送到網路層(Network layer)和鄰居節點作交換。透過此資訊的交換，在路由發現時控制路由請求封包的傳輸功率，當路由建立後，封包根據路由表的記載，選擇所對應的路由路徑和傳輸功率。經由NS-2模擬結果顯示，我們所提出的跨網路協定層路由協定可同時兼顧網路的吞吐量和平均點對點的延遲。 / In recent years, WMNs (Wireless Mesh Networks) technologies have received significant attentions. WMNs not only accede to the advantages of ad hoc networks but also provide hierarchical multi-interface architecture. Transmission power control and routing path selections are critical issues in the past researches of multi-hop networks. Variable transmission power levels lead to different network connectivity and interference. Further, routing path selections among different radio interfaces will also produce different intra/inter-flow interference. These features tightly affect the network performance. Most of the related works on routing protocol design do not consider transmission power control and multi-interface environment simultaneously. In this thesis, we proposed a cross-layer routing protocol called M2iRi2 which coordinates transmission power control and intra/inter-flow interference considerations as routing metrics. Each radio interface calculates the potential tolerable added transmission interference in the physical layer. When the route discovery starts, the M2iRi2 will adopt the appropriate power level to evaluate each interface quality along paths. The simulation results demonstrate that our protocol can enhance both network throughput and end-to-end delay.

無線網狀網路(WMNs)為目前熱門的廣域無線網路接取技術。使用者可以透過WMNs隨時在各處使用即時影音播放的服務。相較於傳統的主從式架構，低成本且容易建置的點對點架構更適用於影音串流的應用；在進行即時影音播放的時候，影音播放的品質便為相當重要的目標。因為多媒體應用服務對於延遲及網路傳輸效能相當敏感，且WMNs的傳輸過程中常會面臨同頻道干擾的問題而使得傳輸的效能銳減，當每個網路節點都具有多張無線網路卡時，如何善用WMNs多頻道傳輸的特性提升效能更是顯得特別重要。在本篇論文中，我們利用WMNs多頻道傳輸的特性進行多媒體群播傳輸，參考史坦納樹的概念來改善現有的MAODV路由演算法，以傳輸品質較佳的鏈結改良原本尋找最小跳躍數路徑的方式，建立兩棵完全互斥的群播樹作為點對點傳輸的骨幹網路，並以MDC的概念將影像串流編碼成兩份獨立的子串流分別經由不同的群播樹傳輸。經實驗評估，我們的方法在網路負載較高的環境下能有效的降低延遲並提高整體系統的效能。 / In WMNs, users can enjoy the real-time video streaming service anytime and anywhere through the services. Compared to the client/server model, P2P approaches is more suitable for video streaming applications because of its low cost and easy deployment. But when using the real-time multimedia service in WMNs, the multimedia applications are very sensitive to delay time and the performance of packets transmission. And the performance is significantly influenced by the co-channel interference, so that it is important to know how to transmit by multi-channel to enhance the performance. In our approach, we choose the better quality links for routing instead of the minimum hop-count path in MAODV. Then we distribute the video streaming to receivers by multicast in multi-channel WMNs, and refer to the Steiner tree concept to modify the MAODV routing protocol to construct two disjoint multicast trees as the backbone for the P2P structure. Therefore, we can adopt the MDC scheme to encode the video into two independent sub-streams and transmit separately along these trees. Experiment results show that in higher network traffic load environment, our scheme is more effective to reduce the latency and improve overall system performance.

IEEE 802.16 是一支援都會型無線網路的協定，IEEE 802.16支援PMP模式(點對多點)和網狀模式兩種。在網狀模式中，所有節點的構成仿如ad-hoc方式，並依據在控制性子框中的排程資訊來計算下次遞送時間。在資料傳送之前，會有一段設定連線的時間。這段時間，每一個節點都必須跟鄰節點競爭，以取得廣播它的排程資訊給鄰節點的機會。這樣的行為跟它過去的歷史無關。換句話說，它具有”時間同質性”而適合以隨機程序來模擬。在這篇論文中，我們將用排隊程序來建立排程行為的模型，然後以馬可夫鏈來估計它的平均延遲時間，也就是一節點持續地競爭直到贏為止的這段等待時間。 / The IEEE 802.16 standard is a protocol for wireless metropolitan networks. IEEE 802.16 MAC protocol supports both of PMP (point to multipoint) and Mesh mode. In the mesh mode, all nodes are organized in a fashion similar ad-hoc and calculate their next transmission time based on the scheduling information performed in the control subframe. Before data transmission for a certain node, there is a period of time to setup the connection. During this period, each node has to compete with each other for the opportunity to advertise scheduling messages to its neighbors. This behavior does not depend on past history. In other words, it is a “Time Homogeneous” and suitable for being modeled by stochastic process. In this thesis, we will model this scheduling behavior by queuing process, and apply the Markov Chain to estimate its average delay time which a node keep waiting until it win the competition.

為了降低無線網路基地台後端之backhaul成本及解決Ad hoc網路涵蓋面積問題，無線網狀網路WMNs(Wireless Mesh Networks)因此應運而生。WMNs網路上的節點裝置與Ad hoc網路上的行動裝置對電量消耗及負載的需求是非常不同的，所以在Ad hoc網路上可使用之路由協定在WMNs網路上是無法直接適用的。 在Pure Ad hoc網路上考量Power之MMBCR(Min-Max Battery Cost Routing)及考量Loading之CSLAR(Contention Sensitive Load Aware Routing)等路由協定並沒有考量到WMNs網路上不同元件間的不同特性。有鑑於此，我們著重在Hybrid WMNs網路環境上，並提出了在Mesh Clients及Routers上同時考量Power及Loading的路徑演算法，我們稱之為POLAR。實驗結果顯示我們的路由協定能夠提昇整體的網路效能及延長網路存活時間。 / In order to reduce the backhaul cost and solve Ad hoc network coverage problem, WMNs (Wireless Mesh Networks) arise at the historic moment. The requirements on power efficiency and loading are much different between mesh nodes of WMNs and mobile hosts of ad hoc networks. The routing protocol used in Ad hoc networks would be not suitable in WMN networks. The power-aware routing in MMBCR (Min-Max Battery Cost Routing) and load-aware routing in CSLAR (Contention Sensitive Load Aware Routing) used in pure Ad hoc networks don‘t consider the different characteristics of the components in WMNs. In view of this, we focus on the Hybrid WMNs environment, and propose a combined POwer-Aware with Load-Aware Routing algorithm (Called POLAR) along mesh clients and routers. The experimental results show that our routing protocol can enhance the network efficiency and lengthen the network live time.