Self-Organizing Mechanisms and QoS-Guaranteed Scheduling Algorithms in Wireless Ad Hoc Networks

因在無線隨意網路裡的節點其電源主要是由電池來提供的，為延長節點的通訊時間，通常會被要求以最小的功率來傳送資料，藉此降低電池電量的消耗。可是，因為沒有固定的基礎設施，為確保所建構網路之可用性，無線隨意網路中的節點通常又會被要求提高傳送距離來達到網路之連通性。令人遺憾地，這兩項要求彼此是矛盾的。在這篇論文裡，為了以更具功率效率的方法來控制網路拓撲架構，我們探討在無線隨意網路中之最佳傳送距離(或發射功率)、服務範圍的大小以及網路連通性三者彼此之間的關係。藉由推導孤立節點（沒有與其他節點相連接之節點）的機率，我們得到在要維持無線隨意網路的連通性之要求下所需之最佳傳送距離和最大的服務範圍。接著，我們提出一個泛用型之(N,B)網路模型，藉此來探討在一個具有N個節點其中有B個邊界節點（只有與一個節點相連接之節點）的無線隨意網路中，此B個邊界節點對於網路連通性、等效的服務範圍和平均節點分支度所造成的影響。 由於無線網路中之節點都是被隨機部署在整個服務範圍內，節點與節點之間的距離也是ㄧ個隨機變數。藉由引進2維歐式空間的觀念，我們推導了三種與節點間之距離有關的機率分佈︰與第k個最接近節點之間的距離機率分佈、兩個隨機選擇節點之間的距離機率分佈以及各個節點與ㄧ隨機選擇參考節點之間距離的結合距離機率分佈。藉由這三種不同的機率分佈，我們研究了在理想環境下部署一個具連通性之無線隨意網路所需之最佳輸送距離、在遮蔽衰退環境下節點分支度的數學描述公式以及分別在理想與遮蔽衰退環境下之網路連通性。 緊接著，我們研究如何設計叢集演算法來組構一個具(N,B)連通性之無線隨意網路，使其不但可以成為一個以叢集為基本單元之網路架構並且可以降低所產生出來的叢集總數。透過分別檢驗身分區別型（ID-Based）和節點分支度型（Degree-Based）之叢集演算法所產生的叢集架構，我們發現大多數的孤立叢集（只具有一名成員之叢集）都是由邊界節點所產生的。這個發現啟發我們可以藉由減少邊界節點所產生的孤立叢集來降低所產生的叢集總數。模擬結果顯示，透過令關鍵節點（邊界節點的唯一鄰居）具有最高優先權來成為叢集控制節點（clusterhead），我們所提出之BFCM型叢集演算法確實可以經由減少由邊界節點所產生的孤立叢集的數量來達到減少叢集總數之目的。為更進一步降低所產生之叢集總數，我們修改了在邏輯設計中原本被用來化簡多個布林變數所使用的Quine-McCluskey （QM）演算法。有別於使用節點之實際分支度來做為權重值，在我們所提出的Modified QM （MQM）演算法中，如果有節點在其一個跳程範圍內之相鄰節點中是具有最高的邏輯節點分支度，則就被選為叢集控制節點。模擬結果顯示，如果與節點分支度型叢集演算法與BFCM叢集演算法相比較，MQM叢集演算法所產生的叢集數量是最少的。這個改進所付出的代價是閘道節點的等級的減少。此外，我們亦探討了遮蔽衰退效應對於網路叢集化之影響。 最後，我們針對在如何在無線隨意網路中提供具服務品質保證之多媒體服務進行研究。我們首先研究如何在單一叢集之情境下達到服務品質保證之傳輸並提出一具服務品質保證之預留式優先輪詢型無線存取通信協定來提供常速率（CBR）與變速率（VBR）訊務源之延遲與延遲變異量的保證。接著，我們將此問題從單一叢集之網路環境下延伸至多叢集之網路架構。為解決在多叢集網路架構下之叢集間同步以及閘道節點與各相連叢集間之會面視窗之問題，我們設計了一個可以同時處理叢集內與叢集間之具服務品質保證的多跳程排程演算法。我們分別針對單一叢集內連線與多叢集間之連線來分析常速率與變速率訊務源在每一跳程以及端點對端點間所遭受之延遲與延遲變異量。接著，我們將上述分析所得到的延遲與延遲變異量用來作為連線允諾控制之標準。我們證明所提出的多跳程排程演算法確實能提供具品質服務保證之多媒體服務。Since nodes in the wireless ad hoc networks are mobile and powered by the bat-teries, for prolonging the communication duration of the nodes, the transmission power is required to be minimized to conserve the limited battery life. In addition, since there is no fixed infrastructure, for the wireless ad hoc networks to be applicable, the wireless ad hoc networks are required to be connected. Unfortunately, these two requirements are against each other. In order to control the network topology in a power-efficient manner, we in-vestigate the relationships between the length of the transmission range, the size of the service area and the connectivity of the wireless ad hoc networks in this thesis. By deriv-ing the probability of isolated node, we obtain the minimum transmission range and the maximum size of the service area that are required to maintain the connectivity of the wireless ad hoc networks. Next, we propose a generalized (N,B) model to investigate the impact of B boundary nodes (i.e. nodes with only one neighbor) on the network connec-tivity, the equivalent service area and the average node degree of a wireless ad hoc net-work with N nodes. Due to nodes are randomly deployed, the distances between nodes are also random. By using the 2-dimensional Euclidean space, we derive three distance related probability distributions: the distribution of the distance to the k-th nearest neighbor, the distribution of the distance between two randomly selected nodes and the joint distribution of the distances between nodes and a randomly selected reference node. With these three probability distributions, the optimal transmission range to deploy a power-efficiently connected wireless ad hoc network in the ideal environment, the formu-lation of the node degree in the shadow fading environment and the network connectivity both in the ideal and shadow fading environments are studied. Next, we study the prob-lem to organize the (N,B) connected wireless ad hoc networks into a cluster-based net-work architecture in which the total number of generated cluster is reduced. By examin-ing the clusters generated by the well known ID-based and Degree-based clustering algo-rithms, we find that most of the clusters that have only one member (i.e. orphan cluster) are generated by boundary nodes. This inspires us to reduce the total number of generated clusters by minimizing the number of orphan clusters that are generated by boundary nodes. By making the only neighbor of a boundary node (i.e. critical node) with the high-est priority to be a clusterhead, the numbers of orphan clusters that are generated by boundary nodes are minimized by the proposed Boundary-First Cluster-Minimized (BFCM) based clustering algorithm. Thus, the total number of generated clusters is also reduced. To further reduce the number of generated cluster, we modify the Quine-McCluskey (QM) algorithm that is originally used in the minimization of a Boolean func-tion with multiple variables in the logic design. Instead of using the physical node degree to be the weighting value, the proposed Modified QM (MQM) clustering algorithm se-lects nodes with the highest logical node degree among its one-hop neighbors to be clus-terheads. The simulation results show that the MQM clustering algorithm generates the minimum number of clusters if compared to the Degree-based and the BFCM-Degree clustering algorithms. The cost for this improvement is the decrease of the order of gate-way node. The impacts of the shadow fading effects on the network clustering are also studied. Finally, we study the problem to provide QoS-guaranteed multimedia services to the wireless ad hoc networks. We first study the single hop scenario and a QoS-guaranteed wireless access protocol, namly the Priority Polling with Reservation (PPR) protocol, is proposed to provide the jitter and delay constraints for CBR and VBR sources. Then, based on multi-cluster network architectures, relative synchronization among clus-ters and the rendezvous windows at the gateway nodes, we design a layer-integrated QoS-guaranteed multihop scheduling algorithm. We analyze the delays and jitters of the CBR and VBR sources suffered at each hop and the end-to-end delays for each intra-cluster and inter-cluster connection. The obtained delays and jitters are then used to be the connection admission control criterion. We show that the proposed multihop schedul-ing algorithm schedules multimedia connections in a preset non-preempted service prior-ity without violating the requested QoS requirements.摘要 i ABSTRACT iv LIST OF TABLES xiii LIST OF FIGURES xv Chapter 1 Introduction 1 1.1 Applications of Wireless Ad Hoc Networks 5 1.1.1 Military Applications 5 1.1.2 Collaborative and Distributed Computing 6 1.1.3 Emergency Operations 7 1.1.4 Wireless Mesh Networks 8 1.1.5 Wireless Sensor Networks 9 1.2 Issues That Are Studied in This Dissertation 10 1.2.1 Self-Organization 10 1.2.2 Quality of Service Provisioning 11 1.3 Organization of The Dissertation 13 Chapter 2 Topology Control in the Wireless Ad Hoc Networks 16 2.1 Overview 16 2.2 Optimum Transmission Range and Network Connectedness 19 2.2.1 Preliminary 19 2.2.2 Probability of Isolated Nodes 20 2.2.3 Connectedness of The Wireless Ad Hoc Networks 21 2.3 Analysis of The (N,B) Connected Wireless Ad Hoc Networks 23 2.4 Simulation and Results 28 2.5 Summaries 32 Chapter 3 On The Distance Distributions in The Wireless Ad Hoc Networks 34 3.1 Overview 35 3.2 The Euclidean Distance Distributions in The Wireless Ad Hoc Networks 38 3.2.1 The Distribution of The Distance to The k-th Nearest Neighbor 38 3.2.2 The Distribution of The Distance Between Two Nodes 40 3.2.3 The Marginal and Joint Distributions of The Distance Between Nodes and A Randomly Selected Reference Node 41 3.3 Applications of The Distance Distributions 47 3.3.1 Optimum Transmission Range 47 3.3.2 Degree Analysis under Ideal Environments 47 3.3.3 Degree Analysis under Shadow Fading Environments 48 3.3.4 Network Connectivity under Ideal Environment 51 3.3.5 Network Connectivity under Shadow Fading Environment 53 3.4 Numerical Results 53 3.5 Summaries 56 Appendix 3.A Derivation of The , and 59 Appendix 3.B Derivation of The , and 61 Chapter 4 Clustering Wireless Ad Hoc Networks with Boundary Nodes 63 4.1 Overview 63 4.2 Related Works 65 4.3 The Cluster Minimization Algorithm 67 4.3.1 Network Model and Definitions 67 4.3.2 Problem Formation 68 4.3.3 Distributed Boundary-First Cluster-Minimized (BFCM) Clustering Algorithm 71 4.4 Simulation and Results 75 4.5 Summaries 77 Chapter 5 Organizing Optimal Cluster-Based Network Architecture by The Modified Quine-McCluskey Algorithm for Wireless Ad Hoc Networks 79 5.1 Overview 79 5.2 Overview of The Qunie-McCluskey Algorithm 81 5.2.1 Stage 1: Obtaining All Prime Implicants (PIs) 81 5.2.2 Stage 2: Choosing The Optimum Set of PIs to Satisfy The Problem Requirement. 82 5.3 The Modified Quine-McCluskey (MQM) Clustering Algorithm 83 5.3.1 Assumptions and Definitions 83 5.3.2 Modifications 85 5.3.3 The Proposed Clustering Algorithm 86 5.4 Analyses of The Cluster Maintenance Overheads 89 5.5 Simulation Results 90 5.6 Summaries 93 Chapter 6 Power-Efficient Clustering Algorithms for Wireless Ad Hoc Networks Under Fading 95 6.1 Overview 95 6.2 Preliminaries 97 6.2.1 Terminologies and Definitions 97 6.2.2 The Shadow Fading Channel Model 98 6.3 The Critical Node First (CNF) Clustering Algorithm 98 6.3.1 Problem Formulation 99 6.3.2 Details of The DCA/CNF 103 6.4 Numerical Results 106 6.5 Summaries 113 Chapter 7 QoS-Guaranteed Scheduling Algorithm for Multimedia Ad Hoc Network---The Single-Cluster Case 115 7.1 Overview 115 7.2 Priority Polling with Reservation Protocol 117 7.2.1 Assumptions 117 7.2.2 The PPR Protocol 118 7.2.3 Priority Polling Scheme (PPS) 119 7.2.4 Randomly Address Polling (RAP) 120 7.3 QoS Constraint Analyses 121 7.3.1 Jitter Analyses for CBR Sources 121 7.3.2 Delay Analyses for VBR Sources 123 7.4 Admission Criterion 125 7.5 Results and Discussions 126 7.6 Summaries 129 Appendix 7.A Computation of 130 Chapter 8 QoS-Guaranteed Scheduling Algorithm for Multimedia Ad Hoc Networks---The Multi-Cluster Case 132 8.1 Overview 132 8.2 Preliminaries 135 8.2.1 Basic Assumptions 135 8.2.2 Traffic Model 136 8.2.3 The System Model 137 8.3 Layer-Integrated QoS-Guaranteed Multihop Scheduling Algorithm 142 8.4 QoS Analysis 146 8.5 Connection Setup and Admission Control 156 8.6 Results and Discussions 163 8.7 Summaries 164 Chapter 9 Conclusions 166 Bibliography 16