應用改良型蝙蝠演算法於無線網狀網路中服務有不同權重之客戶端之動態路由器節點配置

Abstract

本研究探討一個動態無線網狀網路中，服務不同權重客戶之動態路由器配置問題。在本文中，動態係指路由器與客戶皆具有行動力，客戶不但可以隨機做小範圍移動，並且能夠自由切換網路服務的開關。過去用來判斷無線網狀網路服務品質的因素有兩點：網路拓樸的連結率與所覆蓋到客戶的數量兩種指標。在原本的假設下，每個客戶都是平等的被對待，所以不管客戶有多麼的重要，他們所得到的網路服務都會是相同的。但是在現實生活中，往往會有很多不同的狀況，像是客戶如果願意花更多的錢，則可以享有更多的服務。也有許多特殊的狀況使得我們必須讓特定的客戶能得到更多的服務。因此本研究假設每個客戶擁有不同的權重值，權重越高的客戶則會越優先擺放路由器來服務該客戶，而重新定義了此兩種指標。不再單純的考慮所服務之客戶總數，而是考慮總權重值，使得問題更加的複雜。因此，我們提出了改良型蝙蝠演算法來求解，蝙蝠演算法所模擬的是蝙蝠的獵食模式，類似於傳統的粒子群演算法。搭配我們所設計的三種不同的區域搜尋方法，再利用動態機率調整機制來做挑選較適當的區域搜尋。最後針對不同大小的網路規模來模擬改良型蝙蝠演算法求解，並與先前研究所使用的粒子群演算法來做比較並分析實驗結果。

This paper considers the problem of the dynamic router node placement (dynRNP) with weighted clients in wireless mesh networks (WMNs), in which both mesh clients and mesh router have mobility, and mesh clients can switch on or off their network access at different times. The main objective of the conventional dynRNP problem is to maximize network connectivity and client coverage, i.e., the size of the greatest subgraph component of the WMN topology and the number of the clients within radio coverage of mesh routers, respectively. This paper considers a more complicated dynRNP problem in WMNs, in which each client is associated with a weighted value (i.e., the mesh clients with higher weights values are served with larger priority), so that the two objective measures are redefined with consideration of clients’ weights. Furthermore, the weighted problem is solved by an improved bat-inspired algorithm (BA) with a dynamic local search selection scheme, which simulates the echolocation of bats to find the optimal solution. Finally, the performance of the proposed BA is compared with the original BA and PSO, and the effects of weights are analyzed.