無線隨意網路中以虛擬骨幹為基礎之路由協定

Routing is an important issue that affects wireless ad hoc networks. The virtual backbone is usually constructed to compute and maintain routes in wireless ad hoc networks due to the scale and the dynamics. Since the wireless sensor network and the mobile ad hoc network are two popular wireless ad hoc networks, I undertake, in this dissertation, the development of virtual-backbone-based routing protocols in these two networks. In the first part of the dissertation, I propose a virtual-backbone-based routing protocol that guarantees packet delivery without the location information and the computation and storage of the global topological features in wireless sensor networks. I first propose a method, ABVCap, to construct axes as the virtual backbone for assigning virtual coordinates in a wireless sensor network. ABVCap assigns each node multiple 5-tuple virtual coordinates. Subsequently, I introduce a protocol, ABVCap routing, to route packets based on the axes and ABVCap virtual coordinate system. ABVCap routing guarantees packet delivery without the computation and storage of the global topological features. Finally, I demonstrate an approach, ABVCap maintenance, to reconstruct the axes and an ABVCap virtual coordinate system in a network with node failures. Simulations show ABVCap routing ensures moderate routing path length, as compared to routing protocols, GLIDER, Hop ID, GLDR, and VCap. In the second part, I propose a virtual-backbone-based routing protocol that reduces the route searching space in mobile ad hoc networks. Since the virtual backbone in mobile ad hoc networks is requested to be connected and as small as possible, a connected $k$-hop dominating set is used as the virtual backbone. A $k$-hop dominating set is a subset of nodes such that each node not in the set can be reached within $k$ hops from at least one node in the set. In mobile ad hoc networks, a connected $k$-hop dominating set may become disconnected due to node mobility or switch-off, necessitating the reformation of the $k$-hop dominating set. Therefore, I identify a sufficient condition that guarantees the connectivity of the virtual backbone. The condition can be verified in a distributed manner by the node only having the link information of its neighbors. With the help of this condition, I propose a distributed algorithm to efficiently construct and maintain connected $k$-hop dominating sets in mobile ad hoc networks. Then the virtual-backbone-based routing protocol that reduces the route search space to a connected $k$-hop dominating set is introduced. Simulations show that our connected $k$-hop dominating set is small and stable and needs little maintenance overhead in the Random-Walk Mobility and Gauss-Markov Mobility Models.

關鍵字

繞徑；虛擬骨幹；無線隨意網路

並列摘要

繞徑是在無線隨意網路當中一項重要的議題。由於無線隨意網路大規模和動態的特性，虛擬骨幹常被用來計算和維護路徑。而無線感測器網路和行動隨意網路則是兩種最受歡迎的無線隨意網路，因此在本篇博士論文中，我將發展以虛擬骨幹為基礎的路由協定在這兩種網路當中。在本篇博士論文的第一部分中，我發展一個以虛擬骨幹為基礎且能保證傳輸而不需要地理位置資訊和計算儲存整個網路拓墣資訊的路由協定。我首先提出一個方法ABVCap建立軸為虛擬骨幹並利用軸來設定無線感測器網路中的虛擬座標，ABVCap 設定多個五維的座標給每一個節點。接下來，我介紹一個利用軸和ABVCap虛擬座標的路由協定，該路由協定保證傳輸且不需要整個網路拓樸的特性。最後，在網路中有壞掉節點的環境下，我發展一套維護的方法來重建軸和虛擬座標。實驗結果顯示此路由協定和GLIDER、Hop ID、GLDR和VCap比較起來，此路由協定需要適度的路由長度。在第二部分當中，我提出一個在行動隨意網路中以虛擬骨幹為基礎的路由協定使得尋找路由的範圍可以減少。因為在行動隨意網路中，虛擬骨幹被要求為相連且盡可能的小，相連的K-中繼點控制集被當作虛擬骨幹。K-中繼點控制集是一群節點的集合使得每一個不是在集合內的節點都可以由一個在集合內的節點經由K節段數到達。在無線隨意網路中，一個相連的K-中繼點控制集可能因為節點的移動或離開網路而成為不相連的K-中繼點控制集，此時就需要重新建立一個K-中繼點控制集。因此我們確認一個充分條件可以保證虛擬骨幹的相連。這個充分條件可以利用分散式的方法來確認是否滿足，每個節點只需要鄰居節點間相連的資訊。藉由這個充分條件，我們提出一個有效率的分散式方法建立和維持一個相連的K-中繼點控制集在行動隨意網路中。然後一個以虛擬骨幹為基礎且能將路徑尋找範圍減少至K-中繼點控制集的路由協定被提出。實驗結果顯示建立的K-中繼點控制集小而穩定，而且在隨意行走移動模組和高斯移動模組的環境下只需要少量的負擔就可以維持。

並列關鍵字

routing ； virtual backbone ； wireless ad hoc networks

參考文獻

Efficient Data Dissemination Protocol for Wireless Sensor Networks,” IEEE

Based Delivery-Guaranteed Routing Protocol in Wireless Sensor Networks,”

[29] S. Lee, B. Bhattacharjee, and S. Banerjee, “Efficient Geographic Routing in

[1] K.M. Alzoubi, P.J. Wan, and O. Frieder, “Distributed Heuristics for Con-

[2] K.M. Alzoubi, P.J. Wan, and O. Frieder, “Message-Optimal Connected

國際替代計量

無線隨意網路中以虛擬骨幹為基礎之路由協定

全文下載

主題瀏覽