Volume 8 Number 1
February 2011
Article Contents
Liang He, Zhi Chen and Jing-Dong Xu. Optimizing Data Collection Path in Sensor Networks with Mobile Elements. International Journal of Automation and Computing, vol. 8, no. 1, pp. 69-77, 2011. doi: 10.1007/s11633-010-0556-y
Cite as: Liang He, Zhi Chen and Jing-Dong Xu. Optimizing Data Collection Path in Sensor Networks with Mobile Elements. International Journal of Automation and Computing, vol. 8, no. 1, pp. 69-77, 2011. doi: 10.1007/s11633-010-0556-y

Optimizing Data Collection Path in Sensor Networks with Mobile Elements

Author Biography:
  • Zhi Chen received the B.Sc.,M.Sc.,and Ph.D.degrees in the Department of Computer Science from Nankai University,Tianjin,PRC in 2003,2006,and 2009,respectively.

  • Corresponding author: Liang He received the B.Sc.degree in the Department of Computer Science from Tianjin University,Tianjin,PRC in 2006.
  • Received: 2009-08-26
Fund Project:

supported by Tianjin Municipal Information Industry Office (No.082044012)

  • Exploiting mobile elements (MEs) to accomplish data collection in wireless sensor networks (WSNs) can improve the energy efficiency of sensor nodes, and prolong network lifetime. However, it will lead to large data collection latency for the network, which is unacceptable for data-critical applications. In this paper, we address this problem by minimizing the traveling length of MEs. Our methods mainly consist of two steps: we first construct a virtual grid network and select the minimal stop point set (SPS) from it; then, we make optimal scheduling for the MEs based on the SPS in order to minimize their traveling length. Different implementations of genetic algorithm (GA) are used to solve the problem. Our methods are evaluated by extensive simulations. The results show that these methods can greatly reduce the traveling length of MEs, and decrease the data collection latency.
  • 加载中
  • [1] A.Bharathidasan,V.Ponduru.Sensor Networks:An Overview,Technical Report,University of California, Davis,USA,2002.
    [2] J.Heo,J.Hong,Y.Cho.EARQ:Energy aware routing for real-time and reliable communication in wireless industrial sensor networks.IEEE Transactions on Industrial Informatics,vol.5,no.1,pp.3-11,2009.
    [3] Y.Wu,X.Li,Y.Liu,W.Lou.Energy-e?cient wake-up scheduling for data collection and aggregation.IEEE Transactions on Parallel and Distributed Systems,vol.21,no.2, pp.275-287,2010.
    [4] Y.Xiao,H.Chen,K.Wu,B.Sun,Y.Zhang,X.Sun,C. Liu.Coverage and detection of a randomized scheduling algorithm in wireless sensor networks.IEEE Transactions on Computers,vol.59,no.4,pp.507-521,2010.
    [5] G.Xing,T.Wang,Z.Xie,W.Jia.Rendezvous planning in mobility-assisted wireless sensor networks.In Proceedings of the 28th IEEE International Real-time Systems Symposium,IEEE,pp.311-320,2007.
    [6] G.Xing,T.Wang,W.Jia,M.Li.Rendezvous design algorithms for wireless sensor networks with a mobile base station.In Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing,ACM, pp.231-240,2008.
    [7] M.Marta,M.Cardei.Using sink mobility to increase wireless sensor network lifetime.In Proceedings of International Symposium on a World of Wireless,Mobile and Multimedia Networks,IEEE,pp.1-10,2008.
    [8] M.Martaa,M.Cardei.Improved sensor network lifetime with multiple mobile sinks.Pervasive and Mobile Computing,vol.5,no.5,pp.542-555,2009.
    [9] R.Shah,S.Roy,S.Jain,W.Brunette.Data MULEs:Modeling a three-tier architecture for sparse sensor networks.In Proceedings of IEEE Workshop on Sensor Network Protocols and Applications,IEEE,pp.30-41,2003.
    [10] R.Saravanan,S.Ramabalan,C.Balamurugan,A.Subash. Evolutionary trajectory planning for an industrial robot.International Journal of Automation and Computing,vol.7, no.2,pp.190-198,2010.
    [11] T.J.Li,G.Q.Chen,G.F.Shao.Action control of soccer robots based on simulated human intelligence.International Journal of Automation and Computing,vol.7,no.1, pp.55-63,2010.
    [12] Neptune Canada,[Online] ,Available: http://www.neptunecanada.ca/,2010.
    [13] L.Yang.Optimising locations of sink nodes in wireless sensor networks using genetic algorithms.Measurement+Control,vol.39,no.7,pp.214-217,2006.
    [14] J.H.Holland.Adaptation in Natural and Artificial System, Ann Arbor,USA:The University of Michigan Press,1975.
    [15] J.Butler.Robotics and Microelectronics:Mobile Robots as Gateways into Wireless Sensor Networks,Technology@Intel Magazine,2003.
    [16] A.LaMarca,W.Brunette,D.Koizumi,M.Lease,S.B.Sigurdsson,K.Sikorski,D.Fox,G.Borriello.Making sensor networks practical with robots.Lecture Notes in Computer Science,Springer,vol.2414,pp.615-622,2002.
    [17] E.Ekici,Y.Gu,D.Bozdag.Mobility-based communication in wireless sensor networks.IEEE Communications Magazine,vol.44,no.6,pp.56-62,2006.
    [18] S.R.Gandham,M.Dawande,R.Prakash,S.Venkatesan.Energy e?cient schemes for wireless sensor networks with multiple mobile base stations.In Proceedings of Global Telecommunications Conference,IEEE,pp.377-381,2003.
    [19] J.Luo,J.Hubaux.Joint mobility and routing for lifetime elongation in wireless sensor networks.In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies,IEEE,pp.1735-1746,2005.
    [20] Z.M.Wang,S.Basagni,E.Melachrinoudis,C.Petrioli. Exploiting sink mobility for maximizing sensor networks lifetime.In Proceedings of the 38th Annual Hawaii International Conference on System Sciences,IEEE,Big Island, Hawaii,USA,vol.9,pp.287,2005.
    [21] A.Chakrabarti,A.Sabharwal,B.Aazhang.Using predictable observer mobility for power e?cient design of sensor networks.In Proceedings of the 2nd International Conference on Information Processing in Sensor Networks, Springer,pp.129-145,2003.
    [22] Markov-model.com,[Online] ,Available:http://www. markov-model.com/.
    [23] E.M.Arkin,R.Hassin.Approximation algorithms for the geometric covering salesman problem.Discrete Applied Mathematics,vol.55,no.3,pp.197-218,1994.
    [24] J.Gudmundsson,C.Levcopoulos.A fast approximation algorithm for TSP with neighborhoods.Nordic Journal of Computing,vol.6,no.4,pp.469-488,1999.
    [25] A.E.Carter,C.T.Ragsdale.A new approach to solving the multiple traveling salesperson problem using genetic algorithms.European Journal of Operational Research,vol.175, no.1,pp.246-257,2006.
    [26] M.Bellmore,S.Hong.Transformation of multisalesman problem to the standard traveling salesman problem.Journal of ACM,vol.21,no.3,pp.500-504,1974.
    [27] J.E.Beasley,P.C.Chu.A genetic algorithm for the set covering problem.European Journal of Operational Research, vol.94,no.2,pp.392-404,1996.
    [28] G.Mao,B.Fidan,B.D.O.Anderson.Wireless sensor network localization techniques.Computer Networks,vol.51, no.10,pp.2529-2553,2007.
    [29] M.V.Marathe,H.Breu,H.B.Hunt III,S.S.Ravi,D.J. Rosenkrantz.Simple heuristics for unit disk graphs.Networks,vol.25,no.2,pp.59-68,1995.
    [30] G.Venkataraman,S.Emmanuel,S.Thambipillai.Energye?cient cluster-based scheme for failure management in sensor networks.IET Communications,vol.2,no.4, pp.528-537,2008.
    [31] C.Weng,M.Li,X.Lu.Data aggregation with multiple spanning trees in wireless sensor networks.In Proceedings of International Conference on Embedded Software and Systems,IEEE,Sichuan,PRC,pp.355-362,2008.
    [32] N.Christofides,P Viola.The optimum location of multicenters on a graph.Operational Research Quarterly,vol.22, no.2,pp.145-154,1971.
    [33] J.Xu,L.He,Z.Chen,G.Huang,T.Yuan.Reducing the path length of a mobile BS in WSNs.In Proceedings of International Seminar on Future BioMedical Information Engineering,IEEE,pp.271-274,2008.
    [34] A.M.Geo?rion.Integer programming by implicit enumeration and Balas method.SIAM Review,vol.9,no.2, pp.178-190,1967.
    [35] M.R.Garey,D.S.Johnson.Computers and Intractability: A Guide to the Theory of NP-completeness,San Francisco, USA:W.H.Freeman,pp.56-60,1979.
    [36] Z.Michalewicz.Genetic Algorithms+Data Structures =Evolution Programs,3rd ed.,Revised and Extended Edition,Berlin Heidelberg,Germany:Springer-Verlag, pp.209-237,1996.
  • 加载中
  • [1] Tian-Yun Shi, Jian Li, Xin-Chun Jia, Wei Bai, Zhong-Ying Wang, Dong Zhou. 

    Low-latency Data Gathering with Reliability Guaranteeing in Heterogeneous Wireless Sensor Networks

    . International Journal of Automation and Computing, 2020, 17(3): 439-452.  doi: 10.1007/s11633-017-1074-y
    [2] Snehasis Banerjee, Tanushyam Chattopadhyay, Utpal Garain. A Wide Learning Approach for Interpretable Feature Recommendation for 1-D Sensor Data in IoT Analytics . International Journal of Automation and Computing, 2019, 16(6): 800-811.  doi: 10.1007/s11633-019-1185-8
    [3] Simone Hantke, Tobias Olenyi, Christoph Hausner, Tobias Appel, Björn Schuller. Large-scale Data Collection and Analysis via a Gamified Intelligent Crowdsourcing Platform . International Journal of Automation and Computing, 2019, 16(4): 427-436.  doi: 10.1007/s11633-019-1180-0
    [4] Tai-Zhi Lv, Chun-Xia Zhao, Hao-Feng Zhang. An Improved FastSLAM Algorithm Based on Revised Genetic Resampling and SR-UPF . International Journal of Automation and Computing, 2018, 15(3): 325-334.  doi: 10.1007/s11633-016-1050-y
    [5] Dong-Jie Li, Yang-Yang Li, Jun-Xiang Li, Yu Fu. Gesture Recognition Based on BP Neural Network Improved by Chaotic Genetic Algorithm . International Journal of Automation and Computing, 2018, 15(3): 267-276.  doi: 10.1007/s11633-017-1107-6
    [6] Liang Xue, Ying Liu, Zhi-Qun Gu, Zhi-Hua Li, Xin-Ping Guan. Joint Design of Clustering and In-cluster Data Route for Heterogeneous Wireless Sensor Networks . International Journal of Automation and Computing, 2017, 14(6): 637-649.  doi: 10.1007/s11633-017-1094-7
    [7] Merras Mostafa, El Hazzat Soulaiman, Saaidi Abderrahim, Satori Khalid, Gadhi Nazih Abderrazak. 3D Face Reconstruction Using Images from Cameras with Varying Parameters . International Journal of Automation and Computing, 2017, 14(6): 661-671.  doi: 10.1007/s11633-016-0999-x
    [8] Wei Hu,  Jie Tang. Study of Model-free Adaptive Data-driven SMC Algorithm . International Journal of Automation and Computing, 2016, 13(2): 183-190.  doi: 10.1007/s11633-015-0922-x
    [9] Shuo Liu,  Wen-Hua Chen,  Jiyin Liu. Robust Assignment of Airport Gates with Operational Safety Constraints . International Journal of Automation and Computing, 2016, 13(1): 31-41.  doi: 10.1007/s11633-015-0914-x
    [10] Sunil Nilkanth Pawar,  Rajankumar Sadashivrao Bichkar. Genetic Algorithm with Variable Length Chromosomes for Network Intrusion Detection . International Journal of Automation and Computing, 2015, 12(3): 337-342.  doi: 10.1007/s11633-014-0870-x
    [11] Zhong-Da Tian,  Xian-Wen Gao,  Kun Li. A Hybrid Time-delay Prediction Method for Networked Control System . International Journal of Automation and Computing, 2014, 11(1): 19-24.  doi: 10.1007/s11633-014-0761-1
    [12] Hong-Bin Wang,  Mian Liu. Design of Robotic Visual Servo Control Based on Neural Network and Genetic Algorithm . International Journal of Automation and Computing, 2012, 9(1): 24-29.  doi: 10.1007/s11633-012-0612-x
    [13] Xin-Min Xu, Yao Chen, Wen-Yao Xu, Fang Gong. An Efficient Algorithm for Mobile Localization in Sensor Networks . International Journal of Automation and Computing, 2012, 9(6): 594-599 .  doi: 10.1007/s11633-012-0684-7
    [14] Li-Jie Zhao, Tian-You Chai, De-Cheng Yuan. Selective Ensemble Extreme Learning Machine Modeling of Effluent Quality in Wastewater Treatment Plants . International Journal of Automation and Computing, 2012, 9(6): 627-633 .  doi: 10.1007/s11633-012-0688-3
    [15] Qi Wang,  Zhong-Wei Ren,  Zhong-Feng Guo. XML-based Data Processing in Network Supported Collaborative Design . International Journal of Automation and Computing, 2010, 7(3): 330-335.  doi: 10.1007/s11633-010-0511-y
    [16] Anna Witkowska,  Roman Smierzchalski. Nonlinear Backstepping Ship Course Controller . International Journal of Automation and Computing, 2009, 6(3): 277-284.  doi: 10.1007/s11633-009-0277-2
    [17] Siva S. Sivatha Sindhu, S. Geetha, M. Marikannan, A. Kannan. A Neuro-genetic Based Short-term Forecasting Framework for Network Intrusion Prediction System . International Journal of Automation and Computing, 2009, 6(4): 406-414.  doi: 10.1007/s11633-009-0406-y
    [18] Kai Leung Yung, Wai Hung Ip, Ding-Wei Wang. Soft Computing Based Procurement Planning of Time-variable Demand in Manufacturing Systems . International Journal of Automation and Computing, 2007, 4(1): 80-87.  doi: 10.1007/s11633-007-0080-x
    [19] Erfu Yang, Hongjun Xiang, Dongbing Gu, Zhenpeng Zhang. A Comparative Study of Genetic Algorithm Parameters for the Inverse Problem-based Fault Diagnosis of Liquid Rocket Propulsion Systems . International Journal of Automation and Computing, 2007, 4(3): 255-261.  doi: 10.1007/s11633-007-0255-5
    [20] Problems Associated with Evacuation from the Ship in Case of an Emergency Situation . International Journal of Automation and Computing, 2006, 3(2): 165-168.  doi: 10.1007/s11633-006-0165-y
通讯作者: 陈斌, bchen63@163.com
  • 1. 

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

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

Metrics

Abstract Views (4027) PDF downloads (3757) Citations (0)

Optimizing Data Collection Path in Sensor Networks with Mobile Elements

  • Corresponding author: Liang He received the B.Sc.degree in the Department of Computer Science from Tianjin University,Tianjin,PRC in 2006.
Fund Project:

supported by Tianjin Municipal Information Industry Office (No.082044012)

Abstract: Exploiting mobile elements (MEs) to accomplish data collection in wireless sensor networks (WSNs) can improve the energy efficiency of sensor nodes, and prolong network lifetime. However, it will lead to large data collection latency for the network, which is unacceptable for data-critical applications. In this paper, we address this problem by minimizing the traveling length of MEs. Our methods mainly consist of two steps: we first construct a virtual grid network and select the minimal stop point set (SPS) from it; then, we make optimal scheduling for the MEs based on the SPS in order to minimize their traveling length. Different implementations of genetic algorithm (GA) are used to solve the problem. Our methods are evaluated by extensive simulations. The results show that these methods can greatly reduce the traveling length of MEs, and decrease the data collection latency.

Liang He, Zhi Chen and Jing-Dong Xu. Optimizing Data Collection Path in Sensor Networks with Mobile Elements. International Journal of Automation and Computing, vol. 8, no. 1, pp. 69-77, 2011. doi: 10.1007/s11633-010-0556-y
Citation: Liang He, Zhi Chen and Jing-Dong Xu. Optimizing Data Collection Path in Sensor Networks with Mobile Elements. International Journal of Automation and Computing, vol. 8, no. 1, pp. 69-77, 2011. doi: 10.1007/s11633-010-0556-y
Reference (36)

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return