Fair Scheduling in Multimedia Mobile Ad Hoc Networks

Ad hoc 無線網路是一種由可移動的節點，因其本身的需求，動態組成的一種網路。由於此網路的形成，無須藉由固定之有線基礎網路設備，例如基地台、或access points (APs)等，故ad hoc 無線網路的優點是可以在任意時間任意地點形成；而節點的加入與離開也很具彈性。在這網路中的節點，可以是筆記型電腦、也可以是PDA (personal digital assistant)。由於節點可能需要跟不在它直接傳輸範圍內的節點互傳資料，所以網路中的節點除了擔任傳送接收資料的機器外，也需要負責路由器的工作，在適當時間執行找尋最佳路徑的工作。由於ad hoc 無線網路本身具有的彈性，先前已被廣泛使用於戰場及急救場所；而隨著技術的進步，未來更可運用在研討會議場所或教室等地點，提供多媒體的服務。 這篇論文旨在探討針對mobile ad hoc 多媒體網路，資源管理的課題，特別是著重在同時提供公平排程機制以及服務品質要求。在mobile ad hoc 網路中，我們考慮兩種不同型態的資料流，分別是有特殊服務品質要求和沒有特殊服務品質要求的資料流；我們分別稱之為guaranteed flow以及best effort flow。我們的目標是提出一個公平的排程機制，此機制能滿足每一個有服務品質要求的資料流，並進一步讓所有的資料流公平分享剩餘的頻寬。在本篇論文中，我們提出一分散式之頻寬分享比例計算公式（distributed flow weight calculation scheme），使其能與目前在ad hoc無線網路中已存在之以時間標籤為決策因素的公平排程機制相整合，達到提供服務品質要求以及公平分享頻寬等二目標。我們更進一步地提出一新的公平排程機制，稱之為『以累積信用為主之頻寬分配協定 (Credit-based Slot Allocation Protocol，CSAP)』。『以累積信用為主之頻寬分配協定』為一兩層式架構的公平排程協定。在執行排程、傳送資料前，網路中的節點被虛擬地分成數個群集，每一個群集依所採用的準則，選出一個節點來負責協調者的工作。協調者依第一層排程機制分配頻寬給該群集中的一個節點，再由此節點依第二層排程機制分配頻寬給其中的一個資料流。 由於在ad hoc網路中，每個節點均能自在地移動。所以原先已建立之有效路徑可能會因節點移動而斷掉，進而影響到排程機制的進行。針對節點的移動性之議題，我們進而針對『以累積信用為主之頻寬分配協定』加以擴充修改，使其能在考量節點移動性的情形下，仍能達成保證服務品質要求以及公平分享頻寬。主要之作法是將一個multihop資料流視為多個single-hop資料流，並透過加入一個參數 （Q-size），使得屬於同一個multihop資料流的所有single-hop資料流有一定關係存在。 誠如大家所知，無線網路的錯誤發生機率比有線網路高出釵h。故假設頻道永遠不會有錯誤干擾發生是與事實相違背的。針對頻道會有錯誤干擾情況發生之議題，我們提出兩個不同類型的排程機制，分別是『以累積信用為主之頻道補償機制』以及『以時間標籤為主之頻道補償機制』。此二機制均能在有頻道干擾錯誤情況下，達到滿足每一個有服務品質要求的資料流，並進一步讓所有的資料流公平分享剩餘的頻寬等兩個預期目標。『以累積信用為主之頻道補償機制』與『以時間標籤為主之頻道補償機制』最主要的不同點，其一是決定排程的參數不同；其二是的操作模式為集中與分散式並行，而『以時間標籤為主之頻『以累積信用為主之頻道補償機制』、以及道補償機制』為分散式的方式。 我們透過模擬來評量考慮不同議題而提出之每個機制的效能。為此，我們訂定不同的效能參數來加以比較。模擬結果顯示不管有無提供節點移動性、由無考量頻道干擾錯誤情形、以及資料流是single-hop或是multihop，所提出的機制均能滿足有提出服務品質要求的資料流之需求，讓所有的資料流能公平分享剩餘頻寬，並進而達到改善整體網路傳輸效能的目標。An ad hoc network is a self-organizing wireless network comprised only of mobile nodes. In such a network, there is no need for preexisting fixed infrastructure, and each node plays both roles of a terminal and a router. Therefore, an ad hoc network can be created and used by “anytime, anywhere.” This advantage elicits ad hoc networks been immediate interested among military, police, rescue agencies, especially under disorganized or hostile environments, and home area (e.g., a conference or classroom, single building, convention center). Resource management is essential to provide multimedia application service in ad hoc networks. This dissertation studies resource management for multimedia mobile ad hoc networks. In particular, we focus on providing fair scheduling with Quality of Service (QoS) support for mobile ad hoc networks. We consider two types of flows to be transmitted by nodes: guaranteed and best effort flows. The goal is to satisfy the QoS requirements of guaranteed flows and to provide global fairness among all flows. We propose a distributed flow weight calculation scheme which can be integrated with existing timestamp-based fair scheduling protocols for ad hoc networks to guarantee QoS demands and fairly allocate residual bandwidth to all flows. In addition, we propose a credit-based fair scheduling mechanism, called Credit-based Slot Allocation Protocol (CSAP). In CSAP, nodes are logically grouped into clusters, each with a scheduler. The scheduler assigns time slots to mobiles in its cluster based on the first tier algorithm. The mobile scheduled to send at the next time slot then in turn assigns the time slot to a relayed flow determined by the second tier algorithm. We elaborate CSAP detailed operations. As we know that each node in an ad hoc network is capable of free movement. However, mobility will causes the constructed path to break due to some path nodes move away, and thus definitely has a great impact on the performance of fair scheduling protocol. We use CSAP as an example to illustrate how to deal with node mobility and still can achieve our design goals. Besides, we model each multihop flow as multiple single-hop flow segments. These segments are then correlated such that a downstream segment will not be allocated a slot unless the upstream segments have all been allocated. It is obvious that the error rate of a wireless network is much higher than that of a wireline network. Imaging one situation that a node, say node N, is the channel possessor to transmit packets, however, it incurs channel error. That means it cannot transmit packets successfully, and the overall network throughput degrades. One possible solution is for node N to release the channel to other nodes capable of successful transmissions, and then be compensated later. For this channel error issue, we propose two mechanisms: Credit-Based Compensation Protocol (CBCP), and Timestamp-Based Compensation Protocol (TBCP). The major differences between CBCP and TBCP are twofold: one is the scheduling parameter, and the other is operation characteristic (CBCP is a centralized with distributed mechanism, and in contrast, TBCP is a distributed one). We evaluate the performance of all proposed mechanisms by simulations. The results show that all mechanisms can guarantee QoS flows’ service demands, provides global fairness for best effort flows, and improves overall system throughput.Chapter 1 Introduction 1 1.1 An Introduction to Ad Hoc Networks 1 1.2 Quality of Service 2 1.3 Fairness 3 1.4 An Overview of Fair Scheduling in Ad Hoc Wireless Networks 4 1.5 Mobility and Channel Error Issues 6 1.6 Motivation 7 1.7 Organization of the Dissertation 8 Chapter 2 System Model 9 2.1 System Model for Fair Scheduling in Ad Hoc Networks 9 2.2 Mobility Model 10 2.3 Channel Error Model 11 Chapter 3 Fair Scheduling with QoS Support in Ad Hoc Wireless Networks 12 3.1 Introduction 12 3.2 Related Work 13 3.2.1 Fair Scheduling in Ad Hoc Networks 13 3.2.2 Fair Scheduling with QoS Support 15 3.3 Distributed Flow Weight Calculation Scheme 18 3.4 Credit-based Slot Allocation Protocol (CSAP) 19 3.4.1 Service Registration 20 3.4.2 Credit-based Slot Allocation Protocol 23 3.4.3 Global Fairness in CSAP 28 3.5 Simulation Results 29 3.5.1 Performance Metrics 29 3.5.2 Simulation Results 30 3.6 Summary 55 Chapter 4 Fair Scheduling with Mobility Support 56 4.1 Introduction 56 4.2 Credit-based Slot Allocation Protocol (CSAP) with Mobility Support 57 4.2.1 A Multihop Flow 58 4.2.2 Table Structure 59 4.2.3 Service Registration 59 4.2.4 Two-tier Slot Allocation 62 4.2.5 Bottleneck Consideration 71 4.3 Simulation Results 75 4.3.1 Multihop Flows without Mobility Support 76 4.3.2 Multihop Flows with Mobility Support 84 4.4 Summary 92 Chapter 5 Fair Scheduling in Mobile Ad Hoc Networks with Channel Errors 93 5.1 Introduction 93 5.2 Related Work and Problem Specification 94 5.2.1 Related Work 94 5.2.2 Problem Specification 95 5.3 Credit-Based Compensation Protocol (CBCP) 96 5.3.1 Scheduling Tables 96 5.3.2 Channel Error and Channel Recovery Notifications 96 5.3.3 CBCP Operations 97 5.3.4 An Example 98 5.4 Timestamp-Based Compensation Protocol (TBCP) 101 5.4.1 Normalized Flow Weight 101 5.4.2 TBCP Operations 103 5.5 Simulation Results 106 5.5.1 Simulation Environment and Performance Metrics 106 5.5.2 Simulation Results 108 5.6 Performance Analysis 116 5.6.1 Credit-Based Compensation Protocol (CBCP) 116 5.6.2 Timestamp-Based Compensation Protocol (TBCP) 119 5.7 Summary 122 Chapter 6 Conclusions and Future Work 12