臺灣博碩士論文加值系統

在動態之無線網狀網路中，由於網狀客戶(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.

摘要 i
Abstract ii
目錄 iii
圖目錄 iv
表目錄 v
第一章 緒論 1
第二章 問題描述 4
2.1. 問題定義 4
2.2. 數學規劃模型 9
第三章 研究方法 11
3.1. 解的表達和適應值 12
3.2. 位置更新 14
3.3. 區域搜尋 15
3.4. 俱區域搜尋選擇機制之粒子群優化法 17
3.5. 啟發式連線演算法 18
第四章 實驗設計和結果 20
4.1. 實驗環境 20
4.2. 靜態實驗結果 22
4.2.1. 敏感度分析 22
4.2.2. 收斂分析 23
4.2.3. 靜態實驗分析 23
4.3. 動態實驗結果 25
4.3.1. 禁止切換網路 26
4.3.2. 自主切換網路 27
第五章 結論 31
參考文獻 32

[1] I. F. Akyildiz, X. Wang, and W. Wang, "Wireless mesh networks: A survey," Computer networks, vol. 47, no. 4, pp. 445-487, 2005.
[2] D. Benyamina, A. Hafid, and M. Gendreau, "Wireless mesh networks design—A survey," IEEE Communications Surveys &; Tutorials, vol. 14, no. 2, pp. 299-310, 2012.
[3] A. Barolli, F. Xhafa, C. S#westeur034#nchez, and M. Takizawa, "A study on the effect of mutation in genetic algorithms for mesh router placement problem in wireless mesh networks," in Proc. of 2011 International Conference on Complex, Intelligent and Software Intensive Systems (CISIS 2011), IEEE Press, 2011, pp. 32-39.
[4] F. Xhafa, C. S#westeur034#nchez, and L. Barolli, "Genetic algorithms for efficient placement of router nodes in wireless mesh networks," in Proc. of 24th IEEE International Conference on Advanced Information Networking and Applications (AINA 2010), 2010, pp. 465-472.
[5] F. Xhafa, A. Barolli, C. S#westeur034#nchez, and L. Barolli, "A simulated annealing algorithm for router nodes placement problem in wireless mesh networks," Simulation Modelling Practice and Theory, vol. 19, no. 10, pp. 2276-2284, 2011.
[6] V. T. Le, N. H. Dinh, and N. G. Nguyen, "A novel PSO-based algorithm for gateway placement in wireless mesh networks," in Proc. of IEEE 3rd International Conference on Communication Software and Networks (ICCSN 2011), 2011, pp. 41-45.
[7] D.-N. Le, N. G. Nguyen, N. H. Dinh, N. D. Le, and V. T. Le, "Optimizing gateway placement in wireless mesh networks based on ACO algorithm," International Journal of Computer and Communication Engineering, vol. 2, no. 2, pp. 143-147, 2013.
[8] M. Seyedzadegan, M. Othman, B. M. Ali, and S. Subramaniam, "Zero-degree algorithm for Internet gateway placement in backbone wireless mesh networks," Journal of Network and Computer Applications, vol. 36, no. 6, pp. 1705-1723, 2013.
[9] Y. Drabu and H. Peyravi, "Gateway Placement with QoS Constraints in Wireless Mesh Networks," in Proc. of 7th International Conference on Networking (ICN 2008), IEEE Press, 2008, pp. 46-51.
[10] C.-C. Lin, "Dynamic router node placement in wireless mesh networks: A PSO approach with constriction coefficient and its convergence analysis," Information Sciences, vol. 232, pp. 294-308, 2013.
[11] B. Aoun, R. Boutaba, Y. Iraqi, and G. Kenward, "Gateway placement optimization in wireless mesh networks with QoS constraints," IEEE Journal on Selected Areas in Communications, vol. 24, no. 11, pp. 2127-2136, 2006.
[12] R. C. Eberhart and J. Kennedy, "A new optimizer using particle swarm theory," in Proceedings of the 6th International Symposium on Micro Machine and Human Science, 1995, pp. 39-43.
[13] R. L. Keeney and H. Raiffa, Decisions with Multiple Objectives: Preferences and Value Trade-offs, Cambridge University Press, 1993.
[14] M. Clerc and J. Kennedy, "The particle swarm-explosion, stability, and convergence in a multidimensional complex space," IEEE Transactions on Evolutionary Computation, vol. 6, no. 1, pp. 58-73, 2002.
[15] J. Kennedy, "Particle swarm optimization," in Encyclopedia of Machine Learning, Springer, 2010, pp. 760-766.
[16] L. Pan, H. XiaoXia, F. Yuguang, and L. Phone, "Optimal placement of gateways in vehicular networks," IEEE Transactions on Vehicular Technology, vol. 56, no. 6, pp. 3421-3430, 2007.
[17] S. P. T. Srinivasan and C. Chellappan, "Semi-randomised propagation for secure routing in Wireless Sensor Networks," in Proc. of International Conference on Recent Trends in Information Technology (ICRTIT 2011), IEEE Press, 2011, pp. 428-432.
[18] F. Li, Y. Wang, X.-Y. Li, A. Nusairat, and Y. Wu, "Gateway placement for throughput optimization in wireless mesh networks," Mobile Networks and Applications, vol. 13, no. 1-2, pp. 198-211, 2008.
[19] J. L. Doob, Stochastic Processes, Wiley, New York, 1953.
[20] H. A. Taha, Operations Research: An Introduction, Pearson/Prentice Hall Press, 2007.
[21] K.-W. Chin, S. Soh, and C. Meng, "A novel scheduler for concurrent Tx/Rx wireless mesh networks with weighted links," IEEE Communications Letters, vol. 16, no. 2, pp. 246-248, 2012.
[22] T. Oda, A. Barolli, E. Spaho, L. Barolli, F. Xhafa, and M. Younas, "Effects of population size for location-aware node placement in WMNs: Evaluation by a genetic algorithm-based approach," Personal and Ubiquitous Computing, vol. 18, no. 2, pp. 261-269, 2014.
[23] B. Wang, X. Huan, L. T. Yang, and Y. Mo, "Hybrid Placement of Internet Gateways and Rechargeable Routers with Guaranteed QoS for Green Wireless Mesh Networks," Mobile Networks and Applications, pp. 1-13, 2015.
[24] S. Mamechaoui, S. Senouci, F. Didi, and G. Pujolle, "Energy Efficient Management for Wireless Mesh Networks with Green Routers," Mobile Networks and Applications, pp. 1-16, 2015.