大型無線隨意網路中用於拓撲控制之臨界傳輸半徑

Abstract

因無需基礎設施，無線隨意及感測網路可在低成本的限制下靈活地使用於多種的應 用上，這其中包括了緊急的急難救助、戰場上的決策輔助及環境監測等之工作。在無 線隨意網路中，基於硬體上的限制，任何一個設備皆有其最大傳輸範圍（半徑），任倆 個設備如果位於相互的傳輸範圍內，則可建立直接的通訊管道，否則它們必須依賴於 其他位於中間的傳輸設備傳遞信息。 為了有效的運作無線隨意網路系統，通常我們會建立及維護一個虛擬的網路骨幹， 這個虛擬骨幹只是網路拓樸的一部份。我們稱一個網路拓樸的子集為架構圖（spanner） 如果任兩設備在此子集中的總傳輸代價（譬如：距離或傳輸能量等）可控制在只比原 來完整網路中的代價多出有限的倍數。因此架構圖是構成虛擬骨幹的好選擇之一。許 多的幾何結構，如：歐拉最小生成樹(EMST)、相關鄰近圖(relative neighbor graph)、 Gabriel 圖(Gabriel graph)、Delauney 三角化圖(Delauney triangulation)及姚氏圖(Yao』s graph)等皆廣範用於建構架構圖。與建構及維護虛擬骨幹相關的學問則稱為拓樸控制。 一個拓樸控制的演算法如果只需收集及處理局部的資訊則稱為區域化演算法。 在很多的應用中，隨意設備是由電池提供電力，而且一般來說在，更換電池或為電 池充電是不切實際且不可行的。因此提高能源的使用效率可增長無線設備及系統的使 用壽命，其中一個重要的因子即是傳輸耗能的多寡。在這個提案中，我們將研討最小 的傳輸半徑使其所引致的網路拓樸可讓我們設計只需直接相鄰結點訊息的區域化分散 式演算法來建構多種的幾何結構。這最小的傳輸半徑我們稱為臨界傳輸半徑。我們將 針對Gabriel 圖、相關鄰近圖及姚氏圖進行各種分析。另外在理論分析之外，我們亦將 進行大量的模擬以對理論結果進行比對；也計劃購買一套無線感測網路系統以進行系 統實作。