An Angle Partitioning Based Algorithm for the ECFRD Problem in Wireless Sensor Network

Abstract:

Energy-Constrained Ferry Route Design (ECFRD) Problem is an NP-hard problem to minimize the total route length of a message ferry to access all the sensor nodes in a sparse wireless sensor network, while the route length of a tour under a given value due to the energy constraint. In this paper, we propose an angle partitioning based algorithm (APBA) to solve the ECFRD problem. In APBA, the nodes are partitioned into groups according to the tangent angles of their coordinates, and the route length of each group will not exceed the energy constraint. The experimental results show that APBA can greatly reduce the total route length of the ferry. In the best case, 35% of the total route length can be saved, comparing previous nearest neighbor based split and route algorithms.

• Periodical: Applied Mechanics and Materials (Volumes 427-429)
• Pages: 2408-2411
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.427-429.2408
• Online since: September 2013
• Authors: Yong Wang*, Qiang Dou, Wei Peng, Zheng Hu Gong
• Keywords: Angle Partitioning Based Algorithm, ECFRD, Message Ferry, Route Design, Sparse Wireless Sensor Networks

References

[1] P. Juang, H. Oki, Y. Wang, M. Martonosi, L. S. Peh, and D. Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with zebranet, SIGOPS Oper. Syst. Rev., vol. 36, no. 5, p.96–107, (2002).

DOI: 10.1145/635508.605408

[2] W. Zhao and M. Ammar, Message ferrying: Proactive routing in highly-parititioned wireless ad hoc networks, in Proceedings of the 9th IEEE International Workshop on Future Trends of Distributed Computing Systems, (Puerto Rico), p.308–314, (2003).

DOI: 10.1109/ftdcs.2003.1204352

[3] W. Zhao, M. Ammar, and E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, in Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, (Roppongi Hills, Tokyo, Japan), p.187–198, ACM, (2004).

DOI: 10.1145/989459.989483

[4] K. Fall, A delay-tolerant network architecture for challenged internets, in Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, (Karlsruhe, Germany), p.27–34, ACM, (2003).

DOI: 10.1145/863955.863960

[5] W. Yong, P. Wei, D. Qiang, and G. Zhenghu, Energy-constrained ferry route design for sparse wireless sensor networks, Submitted to Publish, (2013).

[6] http: /www. akira. ruc. dk/∼keld/research/LKH.

[7] E. Lawler, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization. Wiley-Interscience series in discrete mathematics, Wiley, (1987).