A joint optimization of data ferry trajectories and communication powers of ground sensors for long-term environmental monitoring

详细信息    查看全文

• 作者：Donghyun Kim ; Wei Wang ; Deying Li ; Joong-Lyul Lee…
• 关键词：Wireless sensor network ; Message ferrying ; Energy ; efficiency ; Communication power control ; Path planning ; Traveling salesman problem
• 刊名：Journal of Combinatorial Optimization
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：31
• 期：4
• 页码：1550-1568
• 全文大小：642 KB
• 参考文献：Anastasi G, Conti M, Francesco MD (2009) Reliable and energy-efficient data collection in sparse sensor networks with mobile elements. J Perform Eval 66:791–810CrossRef
  Anastasi G, Conti M, Francesco MD, Passaarella A (2009) Energy conservation in wireless sensor networks: a survey. Ad Hoc Netw 7:537–568CrossRef
  Boloni L, Turgut D (2008) Should I send now or send later? A decision-theoretic approach to transmission scheduling in sensor networks with mobile sinks. Wirel Commun Mobile Comput 8(3):385–403CrossRef
  Cardei M, Thai MT, Li Y, Wu W (2005) Energy-efficient target coverage in wireless sensor networks. In: Proceedings of the 24st IEEE international conference on computer communications (INFOCOM 2005), Miami, FL, March 13–17
  Christofides N (1976) Worst-case Analysis of a New Heuristic for the Travelling Salesman Problem, Report 388. Graduate School of Industrial Administration, CMU
  Ciullo D, Celik GD, Modiano E (2010) Minimizing transmission energy in sensor networks via trajectory control. In: Proceedings of the 8th international symposium on modeling and optimization in mobile, ad hoc and wireless networks (WiOpt), pp 132–141
  CliffsNotes.com, Mean Value Theorem, June 26, 2013. http://​www.​cliffsnotes.​com/​math/​calculus/​calculus/​applications-of-the-derivative/​mean-value-theorem
  Dumitrescua A, Mitchell JSB (2003) Approximation algorithms for TSP with neighborhoods in the plane. J Algorithms 48(1):135–159MathSciNet CrossRef
  Dumitrescu A, Mitchell JSB (2001) Approximation Algorithms for TSP with Neighborhoods in the Plane. In: Proceedings of the 12th annual ACM-SIAM symposium on discrete algorithms (SODA)
  Even G, Garg N, Konemann J, Ravi R, Sinha A (2004) Min–max tree covers of graphs. Oper Res Lett 32(4):309–315MathSciNet CrossRef MATH
  Frederickson GN, Hecht MS, Kim CE (1978) Approximation algorithms for some routing problems. SIAM J Comput 7:178–193MathSciNet CrossRef
  Henkel D, Brown TX (2008) Towards autonomous data ferry route design through reinforcement learning. In: Proceedings of the 2008 international symposium on a world of wireless, mobile and multimedia networks (WOWMOM), pp 1–6
  Jenkins A, Henkel D, Brown T (2007) Sensor data collection through gateways in a highly mobile mesh network. In: Proceedings of IEEE wireless communications and networking conference (WCNC)
  Jun H, Zhao W, Ammar MH, Zeura EW, Lee C (2007) Trading latency for energy in densely deployed wirless adhoc networks using message ferrying. Ad Hoc Netw 5:441–461CrossRef
  Kim D, Uma RN, Abay BH, Wu W, Wang W, Tokuta AO (2014) Minimum latency multiple data MULE trajectory planning in wireless sensor networks. IEEE Trans Mobile Comput (TMC) 13(4):838–851CrossRef
  Kim D, Abay BH, Uma RN, Wu W, Wang W, Tokuta AO (March 2012) Minimizing data collection latency in wireless sensor network with multiple mobile elements. In: Proceedings of the 31st IEEE international conference on computer communications (INFOCOM 2012), pp 504–512
  Li Y, Cheng MX, Wu W (2005) Optimal topology control for balanced energy consumption in ad hoc wireless networks. J Parallel Distrib Comput (JPDC) 65(2):124–131CrossRef
  Li Y, Guo L, Prasad S (2010) An energy-efficient distributed algorithm for minimum-latency aggregation scheduling in wireless sensor networks. In Proceedings of the 30th international conference on distributed computing systems (ICDCS 2010), Genoa, Italy, June 21–25
  Ma M, Yang Y (2007) SenCar: an energy-efficeint data gathering mechanism for large-scale multihop sensor networks. IEEE Trans Parallel Distrib Syst (TPDS) 18(10):1476–1488MathSciNet CrossRef
  Mitchell JSB (2007) A PTAS for TSP with neighborhoods among fat regions in the plane. In Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 11–18
  Mitchell JSB (2010) A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane. In: Proceedings of the annual symposium on computational geometry (SoCG)
  Muskett RR, Romanovsky VE (2011) Alaskan permafrost groundwater storage changes derived from grace and ground measurements. Remote Sens 3(2):378–397CrossRef
  Papadimitriou CH (1977) The euclidean traveling salesman problem is NP-complete. Theor Comput Sci (TCS) 4(3):237–244MathSciNet CrossRef MATH
  Pearre B, Brown TX (2012) Model-free trajectory optimisation for unmanned aircraft serving as data ferries for widespread sensors. Remote Sens 4:2971–3000CrossRef
  Pearre B, Brown TX (2010) Model-free trajectory optimization for wireless data ferries among multiple sources. In: IEEE globecom 2010 workshop on wireless networking for unmanned aerial vehicles (Wi-UAV 2010)
  Pearre B, Brown TX (2011) Fast, scalable, model-free trajectory optimization for wireless data ferries. In: Proceedings of IEEE international conference on computer communications and networks (ICCCN), pp 370–377
  Pearre B, Brown TX (2012) Energy conservation in sensor network data ferrying: a reinforcement metalearning approach. In: Proceedings of the IEEE global communications conference (GLOBECOM 2012), December 3–7
  Perovich DK, Grenfell TC, Richter-Menge JA, Light B, Tucker WB III, Eicken H (2003) Thin and thinner: sea ice mass balance measurements during sheba. J Geophys Res 108(C3):26.1–26.21CrossRef
  Somasundara AA, Ramamoorthy A, Srivastava MB (2004) Mobile element scheduling for efficient data collection in wireless sensor networks with dynamic deadlines. In: Proceedings of the 25th IEEE international real-time systems symposium (RTSS), pp 296–305
  Somasundara AA, Kansal A, Jea DD, Estrin D, Srivastava MB (2006) Controllably mobile infrastructure for low energy embedded networks. IEEE Trans Mobile Comput 5(8):958–973CrossRef
  Somasundara AA, Ramamoorthy A, Srivastava MB (2007) Mobile element scheduling with dynamic deadlines. IEEE Trans Mobile Comput 6(4):395–410CrossRef
  Sugihara R, Gupta RK (2009) Optimizing energy-latency trade-off in sensor networks with controlled mobility. In: Proceedings of the 28st IEEE international conference on computer communications (INFOCOM 2009), pp 1476–1488
  Tekdas O, Lim J, Terzis A, Isler V (2008) Using mobile robots to harvest data from sensor fields. IEEE Wirel Commun Spec Issue Wirel Commun Netw Robot 16:22–28
  Xue L, Kim D, Zhu Y, Li D, Wang W, Tokuta AO (2014) Multiple heterogeneous data ferry trajectory planning in wireless sensor networks. In: Proceedings of the 33rd IEEE international conference on computer communications (INFOCOM 2014), April 27, 2014–May 2, Toronto, Canada
  Yang Y, Lin M, Xu J, Xie Y (2007) Minimum spanning tree with neighborhoods. In: Proceedings of the 3rd international conference on algorithmic aspects in information and management (AAIM ’07), Portland, OR, USA, June 6–8
  Yuan B, Orlowska M, Sadiq S (2007) On the optimal robot routing problem in wireless sensor networks. IEEE Trans Knowl Data Eng (TKDE) 19(9):1252–1261CrossRef
  
• 作者单位：Donghyun Kim (1) (2)
  Wei Wang (3)
  Deying Li (4)
  Joong-Lyul Lee (5)
  Weili Wu (5)
  Alade O. Tokuta (2)
  
  1. Division of Algorithms and Technologies for Networks Analysis, Faculty of Information Technology, Ton Duc Thang University, Ho Chi Minh City, Vietnam
  2. Department of Mathematics and Physics, North Carolina Central University, Durham, NC, 27707, USA
  3. School of Mathematics and Statistics, Xi’an Jiaotong University, Xi’an, China
  4. School of Information, Renmin University of China, Beijing, People’s Republic of China
  5. Department of Computer Science, University of Texas at Dallas, Richardson, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Convex and Discrete Geometry
  Mathematical Modeling and IndustrialMathematics
  Theory of Computation
  Optimization
  Operation Research and Decision Theory
  
• 出版者：Springer Netherlands
• ISSN：1573-2886

文摘

Recently, various hybrid wireless sensor networks which consist of several robotic vehicles and a number of static ground sensors have been investigated. In this kind of system, the main role of the mobile nodes is to deliver the messages produced by the sensor nodes, and naturally their trajectory control becomes a significant issue closely related to the performance of the entire system. Previously, several communication power control strategies such as topology control are investigated to improve energy-efficiency of wireless sensor networks. However, to the best of our knowledge, no communication power control strategy has been investigated in the context of the hybrid wireless sensor networks. This paper introduces a new strategy to utilize the communication power control in multiple data ferry assisted wireless sensor network for long-term environmental monitoring such that the lifetime of the sensor network is maximized. We formally define the problem of our interest and show it is NP-hard. We further prove there exists no approximation algorithm for the problem which can produce a feasible solution for every possible problem instance even though there is a feasible solution. Then, we propose heuristic algorithms along with rigorous theoretical performance analysis for both the single data ferry case and the multiple data ferry case under certain condition.