Cross-layer Design of Optimal Resource Allocation in Multihop Wireless Networks

由於無線多重跳躍網路具有容易佈建，低維護成本，以及強固連結的優點，已經成為未來網際網路最後一哩接取技術的重要解決方案。在這種型態的網路中，每一個節點同時具有主機與路由器的角色，因此，封包可以在沒有任何有線設備佈建的情況下，透過無線的方式傳遞至多個跳躍之外的節點。網路上的每一個資料流，除了會在其經過的路徑上競爭每個節點的資源，也會與其他的資料流競爭共用無線媒體資源。由於這些特殊的性質，使得欲在無線多重跳躍網路上提供資源分配與頻寬分配給這些資料流產生了許多的挑戰。 在這篇論文中，首先定義了一個新的無線干擾模型來描述媒體接取控制層以及實體層無線干擾的行為，稱為以節點為基礎的干擾模型。這個模型可將無線干擾、鏈結資料速率，以及媒體接取控制層的行為加以特徵化，使得每個節點可以透過能量量測的方式辨識出實體層的干擾與媒體接取控制層的碰撞。 根據以節點為基礎的干擾模型，我們將資料流資源分配的問題規劃成跨階層式的網路效用最大化的問題，這個問題同時考慮了傳輸層、媒體接取控制層，和實體層的互動關係。目標是使聚集的網路流量最大化，同時維持每個資料流的公平性。我們提出了以斜度為基礎的流量分配演算法，並對其收斂性質作分析。從模擬的結果來看，我們所提出的方法可以很快的收斂到最佳解，且可以很快的適應網路拓樸及路徑的變化。 由於在眾多的資料流當中，每個資料流需要的服務品質不同，所以需要進一步提供服務品質差異化的機制。我們提出了一個跨階層式的架構來提供流通量及排隊延遲的差異化，使得不同優先權的資料流得到不同的服務品質。這個架構是由兩個主要的元件所構成的，一個是優先權資料流排程器以及具干擾感知的頻寬分配器。優先權資料流排程器會根據不同的優先權區分資料封包的排程時間，使得具有高優先權的資料流可以在每個中間節點取得較短的延遲。為了最佳地使用無線資源，我們將頻寬分配的問題規劃成一個凸型最佳化問題。這個問題可以用斜度為基礎的演算法以分散式的方式來求解。根據這個演算法，我們設計了分散式的通訊協定。由模擬的結果我們可以發現，我們提出的方法可以在有限的計算次數中區分出不同優先權資料流的頻寬分配。而且這個演算法本身是具有擴充性的，無論網路上的資料流的個數以及接收節點有多少個，演算法都可以在數十次的計算中收斂到最佳解。結合了優先權資料流排程器與干擾感知的頻寬分配器，我們可以有效的區分出不同優先權的資料流之流通量與延遲。Multi-hop wireless networks are a promising solution for last mile access to the Internet due to their characteristics of easy deployment, low maintenance cost, and robust connectivity. In such a network, each node plays both roles of a host and a router, and packets are forwarded in a hop-by-hop manner without the assistance of a pre-deployed infrastructure. Each flow, in addition to contending for local resources at each intermediate node on its routing path, i.e., local interference, must compete for the shared wireless medium with those flows located within its interference range, i.e., location-dependent interference. These unique characteristics spawn many research challenges on providing end-to-end resource or bandwidth allocation in multi-hop wireless networks. In this dissertation, we first define and formulate a new interference model, referred to as Node-based Interference Model, to better capture the behavior of medium access control protocols and physical layer interference issue. This model characterizes the relationship among the interference, data rate at the physical layer and the contentions at medium access layer and enables each node to locally identify the interference at the physical layer and contentions at the medium access layer through signal power measurement. Next, we address the flow allocation problem in multihop wireless networks. Based on Node-based Interference Model, we formulate the problem as a cross-layer network utility maximization problem that considers the interaction of transport, MAC, and physical layers. The objective of this problem is to maximize the aggregate network throughput while maintaining the fairness among concurrent end-to-end sessions. We then propose a gradient-based flow allocation algorithm and analyze the convergence to the optimum for the proposed algorithm. The simulation results show that the proposed algorithm can rapidly converge to the optimum, and also rapidly adapt to the changes of the network topology and routing paths in different flow scenarios. Then, we address the service differentiation with interference consideration for traffic of different priorities in multi-hop wireless networks. Specifically, we propose a cross-layer framework which supports different service levels in terms of throughput and queuing delays for concurrent sessions of different priorities. The system architecture is composed of two major components: a priority-based flow scheduler and an interference-aware bandwidth allocation unit. The priority-based flow scheduler differentiates the queueing delay for data packets being relayed to the next hop. As a result, the sessions of higher priority are guaranteed to have lower queueing delay at each intermediate node on the path to the receiver while the starvation of the lower priority session can be avoided. To utilize wireless resources optimally, we formulate the bandwidth allocation problem with interference consideration as a convex optimization problem. The problem can be solved by a sub-gradient algorithm in a distributed fashion. We then develop a distributed protocol for our proposed algorithm. The simulation results show that the proposed algorithm can achieve different levels of bandwidth allocation efficiently with a limited number of iterations. In addition, our algorithm scales well when the number of sessions and the size of the session increase. Moreover, together with the priority-based flow scheduler, the end-to-end throughput and delay can be effectively differentiated based on different levels of bandwidth allocation.致 謝 i 摘 要 ii Abstract iv Contents vi List of Figures ix List of Tables xi Chapter 1 Introduction 1 Chapter 2 Interference Model 7 2.1 Existing Interference Models 7 2.1.1 Protocol Model 8 2.1.2 Physical Model 11 2.2 Interference in Wireless Networks 12 2.3 Node-based Interference Model 15 2.4 Summary 18 Chapter 3 Optimal Flow Allocation in Multihop Wireless Networks 20 3.1 Problem Formulation 20 3.1.1 Primal problem 20 3.1.2 Dual problem 22 3.2 Flow Allocation Algorithm 24 3.2.1 Gradient-based Algorithm 24 3.2.2 Convergence Analysis 26 3.3 Distributed Protocols 30 3.4 Simulation Results 32 3.4.1 Simulation Settings 32 3.4.2 Tandem Networks 33 3.4.3 Random Networks 39 3.4.4 Comparison Study 42 3.5 Summary 44 Chapter 4 Service Differentiation in Multihop Wireless Networks 46 4.1 Problem Statement 47 4.2 Service Differentiation Framework 48 4.2.1 System Architecture 49 4.2.2 Optimal Bandwidth Allocation Algorithm 51 4.3 Distributed Protocols 58 4.3.1 Information Exchange Protocols 58 4.3.2 Control Messages and Operation Procedures 60 4.4 Simulation Results 63 4.4.1 Simulation Environment 63 4.4.2 Convergence Rate 66 4.4.3 Service Differentiation 67 4.5 Summary 70 Chapter 5 Concluding Remarks and Future Works 72 Bibliography 7