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