Reliable Cluster Construction and QoS-Constrained Routing Assignment in Wireless Mobile Ad Hoc Networks

隨著無線移動網路的發展，且為提供覆蓋式地無線傳輸與應用架構，如何確保網路拓樸的穩定性與效率性儼然成為網路管理的重要議題。然而，無線裝置的移動行為、無線傳輸的限制、脆弱的路由連結與不可預知的網路變動使得網路管理變得複雜與困難。在此分散式環境下，如何建置高度穩定性的網路拓璞與考量相關服務品質的路由指派也因而成為許多專家學者所研究的熱門議題。 本論文針對穩定叢聚網路拓樸與相關服務品質路由問題提出有效率且具彈性的設計方法。在我們提出的架構下，我們假設有一中央決策系統(例如:全球地理定位系統)可以監控整個無線網路並且散佈決策。藉由數學規劃的方式，我們將該問題模式化為一個整數最佳化問題，其目標函數為最大化建構網路與指派路由上的最短連結傳輸時間。如同其他傳統的叢聚問題，我們首先將無線裝置聚集成不同的叢聚，並決定叢聚首與叢聚成員之間的歸屬關係。接著，藉由建置出的叢聚架構，我們決定路由指派並符合相關路由限制，例如:節點容量限制與點對點傳輸延遲限制。相對於其他演算法，不同的地方在於，對於一個過載的網路節點，我們計算它的網路流量總和，重新路由擁塞的傳輸路徑，以達到負載平衡與最佳化網路的效能和穩定性。 由於該問題的複雜性與困難度，我們採用拉格蘭日鬆弛法作為我們的解題方法。藉由該方法優越的特性與我們所提出的演算法，我們可以有效率的解決這複雜的最佳化問題，並且不斷地最佳化我們的決策品質。With the development of Mobile Ad Hoc Networks (MENETs), providing ubiquitous communications and a convenient framework for applications requires network management to guarantee that the network topology is reliable and efficient. However, the mobility of wireless devices, wireless communication limitations, frequent route breakdowns and unpredictable topology changes make the network management complex and difficult. In a distributed environment, how to construct a network topology and QoS constrained routing assignment with high stability has thus become a popular issue. In this thesis, we attempt to solve the problem of reliable cluster construction and the QoS constrained routing assignment. We assume that there exists a central decision system, such as a Geographical Positioning System (GPS), to monitor the entire wireless network and disseminate information. By using a mathematical technique, we model the problem as an integer optimization model, where the objective function is to maximize the minimum link duration of the constructed network topology and routing assignment. Like conventional clustering problems, we first group devices into different clusters and determine the clusterhead/cluster member relationship. Based on the constructed cluster topology, we jointly determine the routing assignment with QoS constraints, such as nodal capacity and end-to-end delay. The difference between our proposed algorithm and other algorithms is that for a heavily-loaded node, we aggregate the traffic demands of all O-D pairs and reroute some congested routing paths to achieve load balance and optimize the utilization and stability of the network. Because of the difficulty and complexity of the optimization problem, we adopt Lagrangean Relaxation and the subgradient method. By applying the latter method’s properties and getting a primal heuristic, we can solve the complicated optimization problem efficiently and improve the solution quality iteration by iteration.Chapter 1 Introduction - 1 - 1.1 Background - 1 - 1.2 Motivation - 4 - 1.3 Literature Survey - 6 - 1.3.1 Cluster Construction - 6 - 1.3.2 Mobility Research - 12 - 1.3.3 Integer Formulation for Clustering - 17 - 1.3.4 Energy Efficient-Multicasting and Wireless Advantage - 21 - Chapter 2 Problem Formulation - 27 - 2.1 Problem Description - 27 - 2.2 Problem notations - 32 - 2.3 Problem Formulation - 34 - 2.4 Extension of the Objective Function - 39 - Chapter 3 Solution Approach - 41 - 3.1 Introduction to Lagrangean Relaxation Method - 41 - 3.2 Lagrangean Relaxation - 43 - 3.2.1 Subproblem 1 (related to decision variable ) - 44 - 3.2.2 Subproblem 2 (related to decision variable and ) - 45 - 3.2.3 Subproblem 3 (related to decision variable ) - 47 - 3.2.4 Subproblem 4 (related to decision variable ) - 48 - 3.3 The Dual Problem and the Subgradient Method - 49 - Chapter 4 Getting Primal Feasible Solution - 51 - 4.1 Lagrangean Relaxation Results - 51 - 4.2 Getting Primal Feasible Heuristics - 52 - 4.2.1 Clusterhead/Cluster Member Relationship Adjustment - 52 - 4.2.2 Inter-Cluster Routing Adjustment - 53 - 4.2.3 Minimum Link Duration Adjustment - 54 - Chapter 5 Computational Experiments - 55 - 5.1 Simple Algorithms - 55 - 5.1.1 Lowest Identifier Based Algorithm (LID) - 56 - 5.1.2 Highest Degree Based Algorithm (HD) - 57 - 5.1.3 MaxMin Algorithm - 57 - 5.1.4 MHMR Algorithm - 58 - 5.2 Lagrangean Relaxation Based Algorithm (LR) - 59 - 5.3 Parameters and Cases of Experiment - 61 - 5.4 Experiment Results - 62 - 5.5 Result Discussion - 73 - 5.6 Computational Time - 74 - Chapter 6 Real-Time Reliable Cluster Construction and QoS-Constrained Routing Assignment - 75 - 6.1 Modified Problem Formulation - 76 - 6.1.1 Problem Description - 76 - 6.1.2 Problem Notation - 78 - 6.1.3 Problem Formulation - 81 - 6.2 Real-time Lagrangean based algorithm - 83 - 6.3 Performance Metrics - 86 - Chapter 7 Summary and Conclusion - 89 - 7.1 Summary - 89 - 7.2 Conclusion - 90 - 7.3 Future work - 90 - Reference - 92