考慮網路閘道位置和服務品質限制下之動態網狀路由器之最適配置問題之研究

Abstract

在動態之無線網狀網路中，由於網狀客戶(mesh router)會移動且會自主切換其連網之開關，因此如何能動態地調整最適的網狀路由器(mesh router)之地理配置以服務多數的網狀客戶是個挑戰。過去相關研究大多僅考慮網狀路由器和網狀客戶兩類網路節點，鮮少同時考慮網路閘道(Internet gateway)之配置，因此由前兩者所構成之網路僅能達成區域網路之連結。因此本研究考慮包含網路閘道位置之動態無線網狀網路配置問題。為了衡量此網路之品質，過去研究主要是使用網路拓樸連結率(topology connectivity)與客戶覆蓋數(client coverage)兩種指標。當考慮網路閘道時，本研究進一步延伸考量唯有與網路閘道有所連結之子拓樸圖形方予以採記於網路拓樸連結率。此外，本研究於網路連結之過程中更進一步考慮網路閘道的三種服務品質(QoS)限制，包含延遲限制(delay-hop constraint)、中繼限制(relay-load constraint)、容量限制(capacity constraint)。考慮網路閘道位置和網路服務品質限制雖讓本研究更貼近現實環境需求，但也使得此問題更加複雜。因此，本研究提出俱區域搜尋選擇機制之粒子群優化法來解決此問題，當中包含分散機制 (dispersing)、覆蓋機制(cover-more)、隨機機制(random)三種區域搜尋機制。最後，本研究針對不同大小的網路規模來評估所提之演算法，實驗結果得知區域搜尋機制確實能更有效地求解此問題。

This paper presents the router node placement of wireless mesh network (WMN) in a dynamic network scenario. In the dynamic wireless mesh network (dynWMN) consisting of mesh clients, mesh routers and Internet gateways. Both mesh clients and mesh routers have mobility, and mesh clients can switch on or off their network access at different times. In past studies, dynWMN did not consider Internet gateway. Therefore, mesh routers and mesh clients only could communicate in local area networks. The objective of this paper is to maximize the two main network performance measures: network connectivity and client coverage subject to Quality of Service (QoS) constraints. There are three main QoS constraints in the dynWMN: delay, relay load, and Internet gateway capacity in order to make sure that the network is robust. From the visualization result of dynWMM in previous works, we discover two main drawbacks: overlapping and coverless. To solve them, this paper presents a novel method called the particle swarm optimization with local search selection scheme, including three local search schemes, dispersing scheme, covermore scheme, and random scheme. Experimental results show the quality of the proposed approach through statistic charts, as well as the adaptability to the topology changes at different times.