Title: 無線存活性網狀網路中不同共用風險連結群組的繞徑與頻道配置
SRLG Diverse Routing and Channel Assignment in Survivable Wireless Mesh Networks
Authors: 高游宸
Kao Yu-Chen
陳健
Chen Chien
資訊科學與工程研究所
Keywords: 無線網狀網路;探索式頻道配置與繞徑;存活性;共用風險連結群組;Wireless mesh networks (WMNs);heuristic routing and channel assignment;Survivability;SRLG
Issue Date: 2005
Abstract: 無線網狀網路是可以用來解決最後一哩(Last-mile)寬頻網際網路存取服務的突破性技術。在無線網狀網路中的網狀路由器(Mesh Router)可以裝備多張無線網路介面卡,而將無線網路介面卡調至不重疊的頻道可以讓頻寬大幅增加並有效地降低干擾。然而,我們需要有一種保護的機制,使得在網路介面卡的故障造成傳輸資料的工作路徑損毀的情況下,依然能夠使用備用路徑來傳送資料,提高整體網路的存活性。考慮過去所提出的尋找備用路徑的方法,利用了共享頻寬(Sharing Bandwidth)、頻寬釋放(Capacity Release)以及不同共用風險連結群組的繞徑(SRLG Diverse Routing)的觀念,但都是探討於有線網路的環境下。因此,我們整合這些觀念並應用在無線網狀網路的環境下,本篇文章首先提出一個0-1整數線性規劃(Integer Linear Programming)的公式,此公式根據一個靜態需求流量表(Traffic Profile)計算出最佳的網路效能並且得到一組頻道配置以及每個需求的工作路徑與相對應的備用路徑,除此之外,我們也發展出以攀爬式(Hill-Climbing)為基礎的不同共用風險連結群組繞徑與頻道配置的演算法(HCBSCA)來解決無線網狀網路靜態流量需求的問題。我們所提出的演算法有效率地微調找出局部最佳化,並利用多次重複執行的動作來找出整體最佳化的最理想的網路效能,並且經由實際的模擬並且比較多種不同的流量需求數據表,驗證整體效能的增進。
Wireless Wireless Mesh Networks (WMNs) are a used for solving last-mile Internet access. Nodes in WMNs can be equipped with multiple network interface cards (NICs) which tune to different channels to increase available bandwidth and reduce interference efficiently. Survivability in WMN is an urgent concern. A protection strategy for finding the backup path to protect the working path from NIC failure is required. The protection approaches include bandwidth sharing, bandwidth release and SRLG diverse routing, all of which are applied only to wired networks. No useful method exists in WMNs. Therefore, this work is the first to integrate and apply the above concepts to WMNs. A hill-climbing based heuristic algorithm (HCBSCA) for static traffic is developed. It starts in several configurations to reach a local optimum of throughput and iterate several times to improve performance. The simulation results present the network throughput under different network scenarios to verify the performance improvement.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009323611
http://hdl.handle.net/11536/79142
Appears in Collections:Thesis