無線隨意網路之自我組構機制與具服務品質保證之排程演算法

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

曾志成(Chih-Cheng Tseng)

指導教授 ： 陳光禎

國立臺灣大學/電機資訊學院/電信工程學研究所/博士(2006年)

https://doi.org/10.6342/NTU.2006.00044

摘要

因在無線隨意網路裡的節點其電源主要是由電池來提供的，為延長節點的通訊時間，通常會被要求以最小的功率來傳送資料，藉此降低電池電量的消耗。可是，因為沒有固定的基礎設施，為確保所建構網路之可用性，無線隨意網路中的節點通常又會被要求提高傳送距離來達到網路之連通性。令人遺憾地，這兩項要求彼此是矛盾的。在這篇論文裡，為了以更具功率效率的方法來控制網路拓撲架構，我們探討在無線隨意網路中之最佳傳送距離(或發射功率)、服務範圍的大小以及網路連通性三者彼此之間的關係。藉由推導孤立節點（沒有與其他節點相連接之節點）的機率，我們得到在要維持無線隨意網路的連通性之要求下所需之最佳傳送距離和最大的服務範圍。接著，我們提出一個泛用型之(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.

並列關鍵字

wireless ad hoc networks ； topology control ； distance distribution ； clustering algorithm ； QoS-guaranteed scheduling algorithm

參考文獻

[1] C. Siva Ram Murthy and B. S. Manoj, Ad Hoc Wireless Network: Architectures and Protocols, Prentice Hall, 2004.

[4] C. E. Perkins and P. Bhagwat, “Highly dynamic destination sequenced distance vector Routing (DSDV) for mobile computers,” Proc. ACM SIGCOMM '94, pp.234-244, Oct. 1994.

[5] D. B. Johnson, “Routing in ad hoc networks of mobile hosts,” Proc. ACM Mobicom '94, pp.158-163, Dec. 1994.

[6] B. M. Leiner, R. F. Ruther and A. R. Satry, “Goals and challenges of the DARPA GloMo program [global mobileinformation systems],” IEEE Pers. Common,. vol. 3 no. 6, pp. 34-43, Dec. 1996.

[7] R. Ruppe, S. Griswald, P. Walsh and R. Martin, “Near term digital rtadio (NTDR) sytem,” IEEE MILCOM 97, pp. 1282-1287, Nov. 1997.