陳健輝臺灣大學：資訊工程學研究所邱俊淵Chiu, Chun-YuanChun-YuanChiu2007-11-262018-07-052007-11-262018-07-052006http://ntur.lib.ntu.edu.tw//handle/246246/54155為了在下一代的無線網路上對延遲敏感性應用(delay-sensitive applications)，如聲音和影像，能提供有品質保證的傳輸，隨意網路(MANET)必須能夠提供不同等級傳輸服務品質(quality-of-service)之功能，使得所需要的頻寬和延遲能夠被保證。然而到目前為止，要在隨意網路上提供傳輸服務品質的保證仍然是一個挑戰。這是因為除了要滿足服務品質的需求，還必須要考量到動態的拓樸(dynamic topology)和共享的無線媒介(shared wireless medium)。這兩點特性產生了以下四個需要解決的問題。 (1) 一個在共享無線媒介的環境下能夠精確計算可用頻寬(available bandwidth)的方法。 (2) 一個能找到滿足頻寬需求之路徑的繞徑演算法(routing algorithm)。 (3) 一個能收集最新狀態資訊(up-to-date state information)的方法。 (4) 一個快速且有效的路由回復(route recovery)方法。 本論文之目的在於發展出一系列適用於隨意網路上且能夠支援多媒體傳輸之媒介存取控制層(MAC layer)和網路層(network layer)的協定。首先，我們研究如何計算一個無線連結上的可用頻寬，並且研究在隨意網路上，什麼樣的媒介存取控制層能夠給有服務品質保證的繞徑較好的支援。為了在隨意網路上提供傳輸服務品質的保證，我們必須要謹慎的選擇或設計媒介存取控制協定。這將影響整個網路的頻寬使用效率(bandwidth utilization)和解決有頻寬限制的繞徑問題(BCRP)的難度。它是一個有服務品質保證的基本繞徑問題。 此外，我們將提出一套快速且可靠適用於媒介存取控制層之廣播協定(broadcast protocol)。它可以支援鄰近區域資訊的交換和尋找路由的氾濫式廣播(flooding)。鄰近區域資訊，如區域拓樸、流量和移動性，是計算頻寬不可或缺的資訊。在網路層上，為了快速路由回復的目的，我們將提出一套穩定的兩階層式架構(two-tier infrastructure)。最後，藉由整合上述的成果，我們將設計一套有穩定性感知(stability-aware)能力且有服務品質保證的路由協定。經由本論文所設計的一系列媒介存取控制層和網路層的協定不只克服了上述的四個問題(i.e., 問題(1),(2),(3)與(4))，並且增加了整體頻寬使用效率和減少了控制封包所造成的額外負擔。我們並將進行大量的實驗模擬來評估所設計協定之效能。In order to provide quality delivery to delay-sensitive applications such as voice and video in the next generation wireless networks, it is imperative that mobile ad-hoc networks (MANETs) have to support quality-of-service (QoS) so that bandwidth and delay requirements can be guaranteed. Thus far, providing QoS in MANETs is still a challenge, because dynamic topology and shared wireless medium should be taken into account, in addition to QoS constraints. They will bring about the following problems to be resolved. (P1) An estimation method that can accurately calculate the available bandwidth in a shared wireless medium environment. (P2) A routing algorithm that can find a feasible path to meet the bandwidth requirement. (P3) A method that can gather up-to-date state information. (P4) An effective and efficient route recovery method. The objective of this dissertation is to develop MAC layer and network layer protocols that can support QoS transmissions in MANETs. At first, we investigate how to estimate the available bandwidth of a wireless link and what MAC layer models that can support QoS routing well in MANETs. In order to provide QoS in a MANET, the MAC protocol should be chosen or designed carefully. The choice of the MAC protocol will affect the overall bandwidth utilization of the network and the intractability of bandwidth-constrained routing problem (BCRP), which is a basic QoS routing problem. Besides, we propose an efficient and reliable MAC layer broadcast protocol that can support the exchange of neighborhood information and the flooding of route discovery as well. Neighborhood information concerning local topology, traffic and mobility is crucial to bandwidth estimation. For the network layer, a stable two-tier infrastructure for the purpose of fast route recovery is introduced. Combining all above results, a stability-aware QoS routing protocol is proposed finally. The proposed MAC layer and network layer protocols can enhance the bandwidth utilization and reduce control overheads, while resolving the problems (P1), (P2), (P3) and (P4). To evaluate their performance, extensive experiments are also carried out.Chapter 1 Introduction 1 1.1 Mobile Ad-Hoc Networks 1 1.2 QoS Routing 3 1.3 Effects of MAC on QoS Routing 5 1.4 Effects of Mobility on QoS Routing 9 1.5 Dissertation Overview 11 Chapter 2 Effects of MAC on BCRP 13 2.1 BCRP in CSMA/CA-based MANETs 13 2.1.1 Related Work 16 2.1.2 An Admission Control Scheme 18 2.1.3 Intractability of BCRP 22 2.2 BCRP in CDMA-over-CSMA/CA-based MANETs 27 2.3 A Polynomial-Time Algorithm for BCRP 31 2.4 Bandwidth Utilization 37 2.5 Discussion 39 Chapter 3 Up-to-Date State Information 43 3.1 Problems and Related Work 43 3.2 MAC Layer Broadcast 46 3.2.1 Broadcast for Periodical Beacons 47 3.2.2 A General MAC Layer Broadcast Scheme 54 3.2.3 Experimental Results 58 3.3 A MAC Layer Broadcast Protocol with Busy Tone 60 3.3.1 The Procedure of BPBT 61 3.4 Simulation 64 3.4.1 Periodical Beacons 66 3.4.2 Alarm Signals to All Nodes 68 3.4.3 Multicasting Video Streams 69 3.5 Discussion 71 Chapter 4 A Stability-Aware QoS Routing Protocol 75 4.1 Gravitational Cluster Structure 76 4.1.1 Strategies of GC Structures 78 4.1.2 GC Head Election 79 4.1.3 GC Construction 80 4.1.4 GC Maintenance 85 4.2 GC-based QoS Routing Protocol 89 4.3 Numerical Analysis and Simulation Results 92 Chapter 5 Conclusion 99 5.1 Summary 99 5.2 Future Work 102 References 1051815441 bytesapplication/pdfen-US隨意網路有頻寬限制的繞徑問題媒介存取控制協定移動性有服務品質保證的繞徑Ad-hoc networkbandwidth-constrained routing problemMAC protocolmobilityQoS routingthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/54155/1/ntu-95-F88526056-1.pdf