Energy-constrained ferry route design for sparse wireless sensor networks

Abstract

In recent years, using message ferries as mechanical carriers of data has been shown to be an effective way to collect information in sparse wireless sensor networks. As the sensors are far away from each other in such highly partitioned scenario, a message ferry needs to travel a long route to access all the sensors and carry the data collected from the sensors to the sink. Typically, practical constraints (e.g., the energy) preclude a ferry from visiting all sensors in a single tour. In such case, the ferry can only access part of the sensors in each tour and move back to the sink to get the energy refilled. So, the energy-constrained ferry route design (ECFRD) problem is discussed, which leads to the optimization problem of minimizing the total route length of the ferry, while keeping the route length of each tour below a given constraint. The ECFRD problem is proved to be NP-hard problem, and the integer linear programming (ILP) formulation is given. After that, efficient heuristic algorithms are proposed to solve this problem. The experimental results show that the performances of the proposed algorithms are effective in practice compared to the optimal solution.

Keywords

message ferry / energy-constrained route design / integer linear programming / wireless sensor networks

References

[1] JuangP, OkiH, WangY, MartonosiM, PehL S, RubensteinD. Energy-efficient computing for wildlife tracking: Design tradeoffs and early experiences with ZebraNet[J]. SIGOPS Oper Syst Rev, 2002, 36(5): 96-107

[2] SzewczykR, OsterweilE, PolastreJ, MainwaringA, EstrinD. Habitat monitoring with sensor networks[J]. Commun ACM, 2004, 47(6): 34-40

[3] VahdatA, BeckerDEpidemic Routing for Partially Connected Ad Hoc Networks [R], 2000

[4] ZhaoW-r, AmmarM. Message Ferrying: Proactive routing in highly-parititioned wireless ad hoc networks [C]. Proceedings of the 9th IEEE International Workshop on Future Trends of Distributed Computing Systems, 2003Puerto RicoIEEE Press308-314

[5] ZHAO Wen-rui, AMMAR M, ZEGURA E. A message ferrying approach for data delivery in sparse mobile ad hoc networks [C]// Oeedings of the 5th ACM International Symposium on Mobile ad hoc Networking and Cmputing Roppongi Hills, Tokyo, Japan: ACM, 004: 187–198.

[6] ZhaoW-r, AmmarM, ZeguraEControlling the mobility of multiple data transport ferries in a delay-tolerant network [Z], 2005

[7] FallK. A delay-tolerant network architecture for challenged internets [C]. Proceedings of the 2003 conference on Applications, technologies architectures and protocols for computer communications, Karlsruhe, Germany: ACM, 200327-34

[8] TariqM M B, ZeguraM A, ZeguraEMessage ferry route design for sparse ad hoc networks with mobile nodes [Z], 2006

[9] PengW, ZhaoB-k, YuW-r, YanX-rong. Ferry route design with delay bounds in delay-tolerant networks [C]. Computer and Information Technology (CIT), 2010 IEEE 10th International Conference, 2010Bradford, UKIEEE Press281-288

[10] WuX-y, ChenY-w, XuM, PengWei. TAFR: A TTL-aware message ferry scheme in DTN [C]. Computational and Information Sciences (ICCIS), 2012 Fourth International Conference, 2012Kuala Lumpur, MalaysiaIEEE Press1380-1383

[11] ShahR C, RoyS, JainS, BrunetteW. Data MULEs: modeling a three-tier architecture for sparse sensor networks [C]. Sensor Network Protocols and Applications, 2003. Proceedings of the First IEEE. 2003 IEEE International Workshop on, 2003Anchorag, USAIEEE Press30-41

[12] GuY-y, BozdagD, EkiciE, LeeC G. Partitioning based mobile element scheduling in wireless sensor networks [C]. Proceedings of the Second Annual IEEE Communications Society Conference on Sensor and ad hoc Communications and Networks, 2005Santa Clara, USAIEEE Press386-395

[13] ChpudhuryR R, BandyopadhyayS, PaulK. A distributed mechanism for topology discovery in ad hoc wireless networks using mobile agents [C]. Mobile and Ad Hoc Networking and Computing, 2000. MobiHOC. 2000 First Annual Workshop, 2000Boston, USAIEEE Press145-146

[14] TanC-g, XuK, WangJ-x, ChenS-qiao. A sink moving scheme based on local residual energy of nodes in wireless sensor networks [J]. Journal of Central South University of Technology, 2009, 16(2): 265-268

[15] LongJ, GuiW-hua. Node deployment strategy optimization for wireless sensor network with mobile base station [J]. Journal of Central South University of Technology, 2012, 19(2): 453-458

[16] JeonghwaY, YangC, AmmarM, ChungkeeL. Ferry replacement protocols in sparse MANET message ferrying systems [C]. Wireless Communications and Networking Conference, 2005New OHeans, USAIEEE Press2038-2044

[17] Almi’aniK, ViglasA, LibmanL. Energy-efficient data gathering with tour length-constrained mobile elements in wireless sensor networks [C]. Local Computer Networks (LCN), 2010 IEEE 35th Conference, 2010Denver, USAIEEE Press582-589

[18] EkiciE, GuY-y, BozdagD. Mobility-based communication in wireless sensor networks [J]. Communications Magazine, IEEE, 2006, 44(7): 56-62

[19] AroraS. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems [J]. J. ACM, 1998, 45(5): 753-782

[20] BentleyJ L. Fast algorithms for geometric traveling salesman problems [J]. Informs Journal on Computing, 1992, 4: 387-411

[21] GilbertL. The vehicle routing problem: An overview of exact and approximate algorithms [J]. European Journal of Operational Research, 1992, 59(3): 345-358

[22] TothPVIGO. The vehicle routing problem [M], 2001Philadelphia, PA, USASociety for Industrial and Applied Mathematics

[23] LawlerE LThe traveling salesman problem: A guided tour of combinatorial optimization[M], 1987New YorkJohn-Wiley

[24] MillerC E, TuckerA W, ZemlinR A. Integer programming formulation of traveling salesman problems [J]. J ACM, 1960, 7(4): 326-329

[25] HELSGAUN K. LKH. [EB/OL]. [2013-07-20]. http://www.akira.ruc.dk/~keld/research/LKH/.

[26] IBM. ILOG CPLEX Optimizer [EB/OL]. [2013-07-20]. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/.