A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 7 Issue 1
Jan.  2020

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2020  >  7(1): 223-236
Jinghui Zhong, Zhixing Huang, Liang Feng, Wan Du and Ying Li, "A Hyper-Heuristic Framework for Lifetime Maximization in Wireless Sensor Networks With A Mobile Sink," IEEE/CAA J. Autom. Sinica, vol. 7, no. 1, pp. 223-236, Jan. 2020. doi: 10.1109/JAS.2019.1911846
Citation: Jinghui Zhong, Zhixing Huang, Liang Feng, Wan Du and Ying Li, "A Hyper-Heuristic Framework for Lifetime Maximization in Wireless Sensor Networks With A Mobile Sink," IEEE/CAA J. Autom. Sinica, vol. 7, no. 1, pp. 223-236, Jan. 2020. doi: 10.1109/JAS.2019.1911846
shu

A Hyper-Heuristic Framework for Lifetime Maximization in Wireless Sensor Networks With A Mobile Sink

doi: 10.1109/JAS.2019.1911846
Funds:  This work was supported by the National Natural Science Foundation of China (61602181,61876025), Program for Guangdong Introducing Innovative and Entrepreneurial Teams (2017ZT07X183), Guangdong Natural Science Foundation Research Team (2018B030312003), the Guangdong–Hong Kong Joint Innovation Platform (2018B050502006), and the Fundamental Research Funds for the Central Universities (D2191200)
More Information
    Abstract
  • Maximizing the lifetime of wireless sensor networks (WSNs) is an important and challenging research problem. Properly scheduling the movements of mobile sinks to balance the energy consumption of wireless sensor network is one of the most effective approaches to prolong the lifetime of wireless sensor networks. However, the existing mobile sink scheduling methods either require a great amount of computational time or lack effectiveness in finding high-quality scheduling solutions. To address the above issues, this paper proposes a novel hyperheuristic framework, which can automatically construct high-level heuristics to schedule the sink movements and prolong the network lifetime. In the proposed framework, a set of low-level heuristics are defined as building blocks to construct high-level heuristics and a set of random networks with different features are designed for training. Further, a genetic programming algorithm is adopted to automatically evolve promising high-level heuristics based on the building blocks and the training networks. By using the genetic programming to evolve more effective heuristics and applying these heuristics in a greedy scheme, our proposed hyper-heuristic framework can prolong the network lifetime competitively with other methods, with small time consumption. A series of comprehensive experiments, including both static and dynamic networks, are designed. The simulation results have demonstrated that the proposed method can offer a very promising performance in terms of network lifetime and response time.

     

    • FullText(HTML)
  • loading
    • 1https://www.gnu.org/software/glpk/
    References(49)
  • [1]
    W. Du, Z. K. Xing, M. Li, B. S. He, L. H. C. Chua, and H. Y. Miao, " Sensor placement and measurement of wind for water quality studies in urban reservoirs,” ACM Trans. Sensor Networks, vol. 11, no. 3, pp. 167–178, 2015.
    [2]
    W. Du, Z. J. Li, J. C. Liando, and M. Li, " From rateless to distanceless: Enabling sparse sensor network deployment in large areas,” IEEE/ACM Trans. Networking, vol. 24, no. 4, pp. 2498–2511, 2016. doi: 10.1109/TNET.2015.2476349
    [3]
    A. Alaiad and L. Zhou, " Patients’ adoption of wsn-based smart home healthcare systems: an integrated model of facilitators and barriers,” IEEE Trans. Professional Communication, vol. 60, no. 1, pp. 4–23, 2017. doi: 10.1109/TPC.2016.2632822
    [4]
    Z. G. Sheng, S. Pfersich, A. Eldridge, J. S. Zhou, D. X. Tian, and V. C. M. Leung, " Wireless acoustic sensor networks and edge computing for rapid acoustic monitoring,” IEEE/CAA J. Autom. Sinica, vol. 6, no. 1, pp. 64–74, Jan. 2019. doi: 10.1109/JAS.2019.1911324
    [5]
    H. O. Alemdar and C. Ersoy, " Wireless sensor networks for healthcare: A survey,” Computer Networks, vol. 54, no. 15, pp. 2688–2710, 2010. doi: 10.1016/j.comnet.2010.05.003
    [6]
    F. Ye, H. Y. Luo, J. Cheng, S. W. Lu, and L. X. Zhang, " A two-tier data dissemination model for large-scale wireless sensor networks,” in ACM/IEEE Int. Conf. Mobile Computing and Networking, Ateanta, Georgia, USA: ACM, pp. 148–159, Mar. 2002.
    [7]
    C. Lin, P. Chou, and C. F. Chou, " HCDD: hierarchical cluster-based data dissemination in wireless sensor networks with mobile sink,” in Int. Conf. Wireless Communications and Mobile Computing, Vancouver, Canada, 2006, pp. 1189–1194.
    [8]
    D. Jea, A. Somasundara, and M. Srivastava, " Multiple controlled mobile elements (data mules) for data collection in sensor networks,” vol. 3560, Marina del Rey, CA, United States, 2005, pp. 244–257.
    [9]
    H. Huang, A. V. Savkin, and C. Huang, " I-UMDPC: the improved-unusual message delivery path construction for wireless sensor networks with mobile sinks,” IEEE Internet of Things J., vol. 4, no. 5, pp. 1528–1536, Oct. 2017. doi: 10.1109/JIOT.2017.2707464
    [10]
    I. Dietrich and F. Dressler, " On the lifetime of wireless sensor networks,” ACM Trans. Sensor Networks, vol. 5, no. 1, pp. 5, 2009.
    [11]
    V. L. Hoesel, T. Nieberg, J. Wu, and P. J. M. Havinga, " Prolonging the lifetime of wireless sensor networks by cross-layer interaction,” IEEE Wireless Communications, vol. 11, no. 6, pp. 78–86, 2004. doi: 10.1109/MWC.2004.1368900
    [12]
    N. B. Long, H. Tran-Dang, and D. Kim, " Energy-aware real-time routing for large-scale industrial internet of things,” IEEE Internet of Things J., vol. 5, no. 3, pp. 2190–2199, Jun. 2018. doi: 10.1109/JIOT.2018.2827050
    [13]
    Z. Hong, R. Wang, and X. L. Li, " A clustering-tree topology control based on the energy forecast for heterogeneous wireless sensor networks,” IEEE/CAA J. Autom. Sinica, vol. 3, no. 1, pp. 68–77, Jan. 2016. doi: 10.1109/JAS.2016.7373764
    [14]
    X. Y. Luo, L. Feng, J. Yan, and X. P. Guan, " Dynamic coverage with wireless sensor and actor networks in underwater environment,” IEEE/CAA J. Autom. Sinica, vol. 2, no. 3, pp. 274–281, Jul. 2015. doi: 10.1109/JAS.2015.7152661
    [15]
    C. Q. Xia, W. Liu, and Q. X. Deng, " Cost minimization of wireless sensor networks with unlimited-lifetime energy for monitoring oil pipelines,” IEEE/CAA J. Autom. Sinica, vol. 2, no. 3, pp. 290–295, Jul. 2015. doi: 10.1109/JAS.2015.7152663
    [16]
    E. Fitzgerald, M. Piro, and A. Tomaszewski, " Energy-optimal data aggregation and dissemination for the internet of things,” IEEE Internet of Things J., vol. 5, no. 2, pp. 955–969, Apr. 2018. doi: 10.1109/JIOT.2018.2803792
    [17]
    S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z. M. Wang, " A new milp formulation and distributed protocols for wireless sensor networks lifetime maximization,” in Proc. IEEE Int. Conf. Communications, vol. 8, Jun. 2006, pp. 3517–3524.
    [18]
    J. Luo and J. Hubaux, " Joint sink mobility and routing to maximize the lifetime of wireless sensor networks: the case of constrained mobility,” IEEE/ACM Trans. Networking, vol. 18, no. 3, pp. 871–884, 2010. doi: 10.1109/TNET.2009.2033472
    [19]
    J. Zhong and J. Zhang, " Ant colony optimization algorithm for lifetime maximization in wireless sensor network with mobile sink,” in Proc. 14th Int. Conf. Genetic and Evolutionary Computation, Philadelphia, PA, United States, 2012, pp. 1199–1204.
    [20]
    Y. Li, Z. X. Huang, J. H. Zhong, and L. Feng, " Genetic programming for lifetime maximization in wireless sensor networks with a mobile sink,” in Proc. Asia-pacific Conf. Simulated Evolution and Learning, Springer, Cham, 2017, pp. 774–785.
    [21]
    A. Kansal, A. A. Somasundara, D. D. Jea, M. B. Srivastava, and D. Estrin, " Intelligent fluid infrastructure for embedded networks,” in Proc. 2nd ACM/SIGMOBILE Int. Conf. Mobile Systems, Applications, and Services, MobySys 2004, 2004, pp. 111–124.
    [22]
    A. A. Somasundara, A. Ramamoorthy, and M. B. Srivastava, " Mobile element scheduling for efficient data collection in wireless sensor networks with dynamic deadlines,” in Proc. 25th IEEE Int. RealTime Systems Symposium, Dec 2004, pp. 296–305.
    [23]
    W. Wang, V. Srinivasan, and K. Chua, " Using mobile relays to prolong the lifetime of wireless sensor networks,” in Proc. Annual Int. Conf. Mobile Computing and Networking, MOBICOM, Cologne, Germany, 2005, pp. 270–283.
    [24]
    S. R. Gandham, M. Dawande, R. Prakash, and S. Venkatesan, " Energy efficient schemes for wireless sensor networks with multiple mobile base stations,” in Proc. GLOBECOM ’03. IEEE Global Telecommuni- cations Conf., vol. 1, Dec 2003, pp. 377–381.
    [25]
    Z. Wang, S. Basagni, E. Melachrinoudis, and C. Petrioli, " Exploiting sink mobility for maximizing sensor networks lifetime,” in Proc. 38th Annual Hawaii Int. Conf. System Sciences, Jan 2005, pp. 287a–287a.
    [26]
    J. Luo and J. Hubaux, " Joint mobility and routing for lifetime elongation in wireless sensor networks,” in Proc. IEEE 24th Annual Joint Conf. IEEE Computer and Communications Societies., vol. 3, Mar. 2005, pp. 1735–1746.
    [27]
    X. J. Deng, B. Wang, W. Y. Liu, and L. T. Yang, " Sensor scheduling for multi-modal confident information coverage in sensor networks,” IEEE Tran. Parallel and Distributed Systems, vol. 26, no. 3, pp. 902–913, Mar. 2015. doi: 10.1109/TPDS.2014.2315193
    [28]
    W. F. Liang and J. Luo, " Network lifetime maximization in sensor networks with multiple mobile sinks,” in Proc. IEEE 36th Conf. Local Computer Networks, Oct. 2011, pp. 350–357.
    [29]
    J. N. Al-Karaki, R. Ul-Mustafa, and A. E. Kamal, " Data aggregation and routing in wireless sensor networks: optimal and heuristic algorithms,” Computer Networks, vol. 53, no. 7, pp. 945–960, 2009. doi: 10.1016/j.comnet.2008.12.001
    [30]
    S. Basagni, A. Carosi, E. Melachrinoudis, C. Petrioli, and Z. M. Wang, " Controlled sink mobility for prolonging wireless sensor networks lifetime,” Wireless Networks, vol. 14, no. 6, pp. 831–858, 2008. doi: 10.1007/s11276-007-0017-x
    [31]
    Y. S. Yun, Y. Xia, B. Behdani, and J. C. Smith, " Distributed algorithm for lifetime maximization in a delay-tolerant wireless sensor network with a mobile sink,” IEEE Trans. Mobile Computing, vol. 12, no. 10, pp. 1920–1930, Oct. 2013. doi: 10.1109/TMC.2012.152
    [32]
    F. Carrabs, R. Cerulli, C. D’Ambrosio, and A. Raiconi, " A hybrid exact approach for maximizing lifetime in sensor networks with complete and partial coverage constraints,” J. Network and Computer Applications, vol. 58, pp. 12–22, 2015. doi: 10.1016/j.jnca.2015.08.018
    [33]
    M. Xie and H. C. Shi, " Ant-colony optimization based in-network data aggregation in wireless sensor networks,” in Proc. 12th Int. Symposium on Pervasive Systems, Algorithms and Networks, Dec. 2012, pp. 77–83.
    [34]
    D. P. Kumar, T. Amgoth, and C. S. R. Annavarapu, " Aco-based mobile sink path determination for wireless sensor networks under non-uniform data constraints,” Applied Soft Computing, vol. 69, pp. 528–540, 2018. doi: 10.1016/j.asoc.2018.05.008
    [35]
    N. Primeau, R. Falcon, R. Abielmona, and E. M. Petriu, " A review of computational intelligence techniques in wireless sensor and actuator networks,” IEEE Communications Surveys and Tutorials, vol. 20, no. 4, pp. 2822–2854, 2018. doi: 10.1109/COMST.2018.2850220
    [36]
    C. W. Tsai, T. P. Hong, and G. N. Shiu, " Metaheuristics for the lifetime of wsn: a review,” IEEE Sensors J., vol. 16, no. 9, pp. 2812–2831, 2016. doi: 10.1109/JSEN.2016.2523061
    [37]
    E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Öezcan, and R. Qu, " Hyper-heuristics: a survey of the state of the art,” J. Operational Research Society, vol. 64, no. 12, pp. 1695–1724, 2013. doi: 10.1057/jors.2013.71
    [38]
    F. F. Zhang, Y. Mei, and M. J. Zhang, " Evolving dispatching rules for multi-objective dynamic flexible job shop scheduling via genetic programming hyper-heuristics,” in Proc. IEEE Congress on Evolution- ary Computation, 2019.
    [39]
    S. Nguyen, Y. Mei, and M. J. Zhang, " Genetic programming for production scheduling: a survey with a unified framework,” Complex and Intelligent Systems, vol. 3, no. 1, pp. 41–66, 2017.
    [40]
    N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, " Automatic design of a hyper-heuristic framework with gene expression programming for combinatorial optimization problems,” IEEE Trans. Evolutionary Computation, vol. 19, no. 3, pp. 309–325, 2015. doi: 10.1109/TEVC.2014.2319051
    [41]
    M. A. Ardeh, Y. Mei, and M. J. Zhang, " Transfer learning in genetic programming hyper-heuristic for solving uncertain capacitated arc routing problem,” in Proc. IEEE Congress on Evolutionary Computa- tion, 2019.
    [42]
    N. R. Sabar, M. Ayob, G. Kendall, and R. Qu, " A dynamic multiarmed bandit-gene expression programming hyper-heuristic for combinatorial optimization problems,” IEEE Trans. Cybernetics, vol. 45, no. 2, pp. 217–228, 2015. doi: 10.1109/TCYB.2014.2323936
    [43]
    J. Park, Y. Mei, S. Nguyen, G. Chen, and M. J. Zhang, " An investigation of ensemble combination schemes for genetic programming based hyperheuristic approaches to dynamic job shop scheduling,” Applied Soft Computing, vol. 63, pp. 72–86, 2018. doi: 10.1016/j.asoc.2017.11.020
    [44]
    J. H. Chang and L. Tassiulas, " Maximum lifetime routing in wireless sensor networks,” IEEE/ACM Trans. Networking, vol. 12, no. 4, pp. 609–619, 2004. doi: 10.1109/TNET.2004.833122
    [45]
    J. H. Zhong, Y. S. Ong, and W. T. Cai, " Self-learning gene expression programming,” IEEE Trans. Evolutionary Computation, vol. 20, no. 1, pp. 65–80, Feb. 2016. doi: 10.1109/TEVC.2015.2424410
    [46]
    L. F. Ma, Z. D. Wang, Q.-L. Han, and H.-K. Lam, " Variance-constrained distributed filtering for time-varying systems with multiplicative noises and deception attacks over sensor networks,” IEEE Sensors J., vol. 17, no. 7, pp. 2279–2288, 2017. doi: 10.1109/JSEN.2017.2654325
    [47]
    L. F. Ma, Z. D. Wang, H.-K. Lam, and N. Kyriakoulis, " Distributed eventbased set-membership filtering for a class of nonlinear systems with sensor saturations over sensor networks,” IEEE Trans. Cybernetics, vol. 47, no. 11, pp. 3772–3783, 2017. doi: 10.1109/TCYB.2016.2582081
    [48]
    W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan, " Energyefficient communication protocol for wireless microsensor networks,” in Proc. 33rd Annual Hawaii Int. Conf. System Sciences, Maui, USA: IEEE, vol. 2, Jan. 2000.
    [49]
    Y. Shi and Y. T. Hou, " Theoretical results on base station movement problem for sensor network,” in Proc. IEEE INFOCOM 27th Conf. Computer Communications, Apr. 2008, pp. 1–5.
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(10)  / Tables(6)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (1255) PDF downloads(39) Cited by()

    Highlights

    • A hyper-heuristic framework that designs heuristics to optimize wireless sensor networks is proposed.
    • The computer-designed heuristics are competitive with other algorithms in the term of network lifetime.
    • The heuristics designed by our method have a short response time (even in dynamic networks).

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return