- 學位論文
Construction and Maintenance of Overlays in Wireless Ad Hoc and Sensor Networks
摘要
無線傳輸技術與許多創新應用的快速發展，讓無線隨意式感測網路(wireless ad hoc and sensor networks, WASN)成為一門熱門的研究領域。本論文探討建構與維護WASN之疊加(overlay)結構的相關研究問題。所謂的疊加結構是在真實網路系統之上的一種邏輯上的網路拓墣，其使用某些架構來連接網路內的一群結點。這些在疊加結構內的邏輯性網路連線，可以通過數個網路中的中介節點。在WASN中，研究者需探討各種疊加結構(例如tree，mesh或cluster)於不同應用的情境(如flooding，gathering, multicasting與lookup等)之下的各種表現與狀況。疊加結構將應用軟體之下的實際網路架構做簡化，將實際網路架構之複雜性、不規則性與一些不穩定的特性，做隱藏、簡化性的描述。關於overlay的建構，我們探討研究在靜態性的WASN上建構ring形式的疊加結構。所謂的ring形式的疊加結構是將網路內的節點用ring將其串起，如同Hamiltonian cycle一樣。在隨意圖形上建構Hamiltonian cycle是非常困難的。我們研究實際的問題，例如可靠性的檔案傳輸，互斥問題與時間同步問題，結果顯示ring架構確實有辦法可以解決上述問題。 我們所提出的ring形式的疊加結構有支援multiple nodes appearance (overlay的路徑可以通過同一節點一次以上。)，同時架構內允許side-path與loop。Ring形式的overlay可以讓節點進行雙向且無碰撞的訊息傳輸，進行節點排序，且提供進行網路操作之後的節點狀況回報，而且這些回報資訊是不需額外訊息成本的。我們探討各種不同的ring形式overlay的分散式建構演算法與其最佳化的相關問題。於overlay的維護上，我們探討於叢集式行動隨意型網路(Cluster-based Mobile ad hoc network, cluster-based MANET)的資源維護相關問題。我們考量使用cluster-head來進行資源管理，我們稱為Cluster-Based With Head Overlay (CWHO)。 使用head node這種方法所會衍生出之某些問題，例如節點失效與hotspot(少數節點流量過高)、資源消耗過高等情況，我們提出了一種完全分散性的資源管理機制，稱為Cluster-Based WithOut Head Overlay (CWOHO)。在CWOHO，我們將所有節點的資源分散到cluster之中，使得每一個節點都可以變成cluster head。CWHO與CWOHO都是進行全面性維護(total maintenance)，每個cluster都可以維護在網路中所有cluster的資訊。此種全面性維護之要求，對於某些訊息傳輸延遲有要求與限制的應用情境，例如多媒體的應用，是種不可或缺的特性。除了此兩種極端性的策略，我們討論第三種維護策略，稱為Clusters with Neighbor Information (CNI)。以上三種策略的表現都有進行評估與比較。
並列摘要
The advancement of wireless technologies and range of innovative applications made wireless ad hoc and sensor networks (WASN) a very popular research area. This dissertation considers an interesting research problem of construction and maintenance of an overlay structure in WASN. An overlay is a logical topology built on top of a physical network to connect a set of nodes in a certain structure. The logical links of an overlay structure can pass through number of intermediate nodes in the network. In WASN, researchers have studied various overlay structures, such as tree, mesh, clusters overlay, for performing applications such as flooding, gathering, multicasting and lookups. An overlay acts as an abstraction to hide the complexity, irregularity, and dynamics in the underlying network from the applications running on top of it. In overlay construction, we study an innovative technique for constructing ringlike overlays on static wireless ad hoc and sensor networks. A ring-like overlay is a ring structure that connects a group of nodes in the network, as in Hamiltonian cycle. Building a Hamiltonian cycle over a random graph is very difficult. We consider practical problems such as reliable file transfer, mutual exclusion, and clock synchronization, and find that a relaxed ring structure is sufficient to solve these problems. Our proposed ring-like overlay supports multiple nodes appearances, i.e., the overlay path can pass through a node more than once. It also allows side-paths and loops in its structure. A ring-like overlay allows conflict-free two-way communications, supports node ordering, and provides cost-free status feedbacks of operations. We discuss a number of distributed construction algorithms for ring-like overlays, which optimizes a different aspect of the overlay. In overlay maintenance, we consider the design space of the resources maintenance problem in a cluster-based mobile ad hoc network (MANET). On one end, we consider the strategy of using cluster heads for maintaining resources of the clusters, referred as Cluster-Based With Head Overlay (CWHO). To address the problem associated with the head nodes, such as single point failure, hot-spot, excess power consumption, we investigate the other extreme of the design space and propose a fully distributed strategy for resource maintenance, referred as Cluster-Based WithOut Head Overlay (CWOHO). In CWOHO, we distribute the resources to all nodes in the cluster, so that every node can play the role of the cluster heads. Both CWHO and CWOHO deals with total maintenance, i.e., every cluster maintains the resource information of all other clusters in the network, which can be essential for the delay constrained or multimedia applications. In the middle of the two extremes, we investigate a third maintenance strategy, referred as Clusters with Neighbor Information (CNI). The performance of the three strategies is evaluated and compared.