We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Feng Zeng, Zhi-Gang Chen. Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints[J]. Journal of Computer Science and Technology, 2009, 24(4): 775-785.
Citation: Feng Zeng, Zhi-Gang Chen. Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints[J]. Journal of Computer Science and Technology, 2009, 24(4): 775-785.

Cost-Sensitive and Load-Balancing Gateway Placement in Wireless Mesh Networks with QoS Constraints

Funds: Supported by the National Natural Science Foundation of China under Grant Nos. 60773012 and 60873082.
More Information
  • Author Bio:

    Feng Zeng received his B.Eng. degree in computer science in 2000,M.Eng. degree in computer application in 2005, both fromHunan University, China. He is currently a Ph.D. candidate in computerapplication at Network Computing and Distributed ProcessingLaboratory in School of Information Science and Engineering, CentralSouth University, China. His main research interests include wirelessmesh network, QoS routing and network calculus. He is a student memberof China Computer Federation.

    Zhi-Gang Chen is a professor at School of Information Science andEngineering (ISE), Central South University (CSU), China. His researchinterests are in QoS mechanism for IP network, Web service, andwireless network. He is the supervisor of Network Computing andDistributed Processing Laboratory at School of ISE, CSU. He obtainedhis Ph.D. and M.Sc. degrees in computer science from CSU. He is amember of China Computer Federation.

  • Received Date: November 24, 2008
  • Revised Date: March 10, 2009
  • Published Date: July 04, 2009
  • In wireless mesh networks (WMNs), gateway placement is the key to network performance, QoS and construction cost. This paper focuses on the optimization of the cost and load balance in the gateway placement strategy, ensuring the QoS requirements. Firstly, we define a metric for load balance on the gateways, and address the minimum cost and load balancing gateway placement problem. Secondly, we propose two algorithms for gateway placement. One is a heuristic algorithm, which is sensitive to the cost, selects the gateway candidates according to the capacity/cost ratio of the nodes, and optimizes the load balance on the gateways through scanning and shifting methods. The other is a genetic algorithm, which can find the global optimal solution. The two algorithms differ in their computing complexity and the quality of the generated solutions, and thus provide a trade-off for WMN design. At last, simulation is done, and experimental results show that the two algorithms outperform the others. Compared with OPEN/CLOSE, the average cost of gateway placement generated by our algorithms is decreased by 8%~32%, and the load variance on the gateways decreased by 77%~86%. For the genetic algorithm, the performance improvement is at the price of the increase of the CPU execution time.
  • [1]
    Akyildiz I F, Wang X. A survey on wireless mesh networks. Communications Magazine, IEEE, 2005, 43(9): 23-30.
    [2]
    Wu X, Liu J, Chen G. Analysis of bottleneck delay and throughput in wireless mesh networks. In Proc. IEEE MASS, Vancouver, Canada, October 9-12, 2006, pp.765-770.
    [3]
    Jun J, Sichitiu M L. Fairness and QoS in multihop wireless networks. In Proc. Vehicular Technology Conference, Orlando, Florida, USA, October 4-9, 2003, pp.2936-2940.
    [4]
    Wong J L, Jafari R, Potkonjak M. Gateway placement for latency and energy e±cient data aggregation. In Proc. the 29th Annual IEEE International Conference on Local Computer Networks, Tampa, FL, USA, November 16-18, 2004, pp.490-497.
    [5]
    Youssef W, Younis M. Intelligent gateways placement for reduced data latency in wireless sensor networks. In Proc. ICC, Glasgow, Scotland, June 24-28, 2007, pp.3805-3810.
    [6]
    Chandra R, Qiu L, Jain K et al. Optimizing the placement of integration points in multi-hop wireless networks. In Proc. ICNP, Berlin, Germany, October 5-8, 2004, pp.271-282.
    [7]
    Bejerano Y. E±cient integration of multihop wireless and wired networks with QoS constraints. IEEE/ACM Transactions on Networking, 2004, 12(6): 1064-1078.
    [8]
    Aoun B, Boutaba R, Iraqi Y et al. Gateway placement optimization in wireless mesh networks with QoS constraints. IEEE Journal on Selected Areas in Communications, 2006, 24(11): 2127-2136.
    [9]
    Drabu Y, Peyravi H. Gateway placement with QoS constraints in wireless mesh networks. In Proc. the Seventh International Conference on Networking, Cancun, Mexico, April 13-18, 2008, pp.46-51.
    [10]
    Vanhatupa T, H?annik?ainen M, H?am?al?ainen T D. Performance model for IEEE 802.11s wireless mesh network deployment design. Journal of Parallel and Distributed Computing, 2008, 68(3): 291-305.
    [11]
    He B, Xie B, Agrawal D P. Optimizing the Internet gateway deployment in a wireless mesh network. In Proc. Mobile Adhoc and Sensor Systems, Pisa, Italy, October 8-11, 2007, pp.1-9.
    [12]
    Prasad R, Wu H. Minimum-cost gateway deployment in cellular Wi-Fi networks. In Proc. IEEE Consumer Communications and Networking Conference, Las Vegas, NV,USA, January 7-10, 2006, pp.706-710.
    [13]
    Hsiao P-H, Hwang A, Kung H T et al. Load-balancing routing for wireless access networks. In Proc. 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, USA, April 22-26, 2001, pp.986-995.
    [14]
    Coley D A. An Introduction to Genetic Algorithms for Scientists and Engineers. Singapore: River Edge, NJ World Scientiˉc Publishing Co., 1999, pp.23-24.
  • Related Articles

    [1]Chun-Hui Wang, Zhi Jin, Wei Zhang, Didar Zowghi, Hai-Yan Zhao, Wen-Pin Jiao. Activity Diagram Synthesis Using Labelled Graphs and the Genetic Algorithm[J]. Journal of Computer Science and Technology, 2021, 36(6): 1388-1406. DOI: 10.1007/s11390-020-0293-9
    [2]Concha Bielza, Juan A. Fern&aacutendez del Pozo, Pedro Larra&ntildeaga. Parameter Control of Genetic Algorithms by Learning and Simulation of Bayesian Networks —— A Case Study for the Optimal Ordering of Tables[J]. Journal of Computer Science and Technology, 2013, 28(4): 720-731. DOI: 10.1007/s11390-013-1370-0
    [3]Ji-Bao Lai, Hui-Qiang Wang, Xiao-Wu Liu, Ying Liang, Rui-Juan Zheng, Guo-Sheng Zhao. WNN-Based Network Security Situation Quantitative Prediction Method and Its Optimization[J]. Journal of Computer Science and Technology, 2008, 23(2): 222-230.
    [4]Sheng-Zhi Du, Zeng-Qiang Chen, Zhu-Zhi Yuan. Evolutionary Pseudo-Relaxation Learning Algorithm for Bidirectional Associative Memory[J]. Journal of Computer Science and Technology, 2005, 20(4): 559-566.
    [5]Zhao-Xia Wang, Zeng-Qiang Chen, Zhu-Zhi Yuan. QoS Routing Optimization Strategy Using Genetic Algorithm in Optical Fiber Communication Networks[J]. Journal of Computer Science and Technology, 2004, 19(2).
    [6]YU Nong, WU Hao, WU Chang Yong, LI YuShu. Automatic Target Detection by Optimal Morphological Filters[J]. Journal of Computer Science and Technology, 2003, 18(1).
    [7]XU Shiyi, Tukwasibwe Justaf Frank. Forecasting the Efficiency of Test Generation Algorithms for Combinational Circuits[J]. Journal of Computer Science and Technology, 2000, 15(4): 326-337.
    [8]XU Shiyi, Tukwasibwe Justaf Frank. Forecasting the Efficiency of Test Generation Algorithms for Combinational Circuits[J]. Journal of Computer Science and Technology, 2000, 15(4).
    [9]GU Jing, SHUAI Dianxun. The Faster Higher-Order Cellular Automaton for Hyper-Parallel Undistorted Data Compression[J]. Journal of Computer Science and Technology, 2000, 15(2): 126-135.
    [10]GU Jing, SHUAI Dianxun. A New Parallel-by-Cell Approach to Undistorted DataCompression Based on Cellular Automatonand Genetic Algorithm[J]. Journal of Computer Science and Technology, 1999, 14(6): 572-579.
  • Cited by

    Periodical cited type(1)

    1. Farzaneh Asadzadeh, Akram Reza, Midia Reshadi, et al. Thermal-aware application mapping using genetic and fuzzy logic techniques for minimizing temperature in three-dimensional network-on-chip. The Journal of Supercomputing, 2024. DOI:10.1007/s11227-023-05869-x

    Other cited types(0)

Catalog

    Article views (42) PDF downloads (2437) Cited by(1)
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return