GAO Zhipeng, CHEN Kan, QIU Xuesong, “Relay Node Placement with Base Stations in Wireless Sensor Networks Fault-Tolerant,” Chinese Journal of Electronics, vol. 23, no. 4, pp. 794-800, 2014,
Citation: GAO Zhipeng, CHEN Kan, QIU Xuesong, “Relay Node Placement with Base Stations in Wireless Sensor Networks Fault-Tolerant,” Chinese Journal of Electronics, vol. 23, no. 4, pp. 794-800, 2014,

Relay Node Placement with Base Stations in Wireless Sensor Networks Fault-Tolerant

Funds:  This work is supported by the National Natural Science Foundation of China (No.61272515, No.61121061), Beijing Higher Education Young Elite Teacher Project (No.YETP0474) and Ph.D. Programs Foundation of Ministry of Education of China (No.20110005110011)
  • Received Date: 2013-03-01
  • Rev Recd Date: 2013-07-01
  • Publish Date: 2014-10-05
  • It has been proposed to deploy relay nodes for the sake of prolonging Wireless sensor networks (WSN) lifetime, such that sensors transmit the sensed data to them which in turn delivers the data to base stations. For survivability requirements, relay placements which considers fault tolerant ability have been noticed and studied. While related works are limited or most existing works don't take factors such as fault tolerance, or base stations into account comprehensively in two tired WSN. We focus on fault tolerant relay node placement in two-tiered heterogeneous WSN with base stations. As far as we know, fault tolerance contains two fundamental aspects, for one is multi-coverage and the second is multi-path. It is a NP-hard problem and figure out an approximation, whose approximation ratio is enhanced to be (18+ε). While a sub-problem approximation is also described as supplementary. Experimental results verify that the number of relay nodes deployed by our algorithm is somewhat superior to existed relay node placement solutions.
  • loading
  • I.F. Akyildiz, W. Su, Y. Sankarasubramaniam and E. Cayirci, Wireless sensor networks: A survey, Computer Networks, Vol.38, No.4, pp.393-422, 2002.
    A. Bari, A. Jaekel, J. Jiang and Y. Xu, Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements, Computer Communications, Vol.35, No.3, pp.320-333, 2012.
    X. Cheng, D-Z Du, L. Wang and B. Xu, Relay sensor placement in wireless sensor networks, Wireless Networks, Vol.14, No.3, pp.347-355, 2008.
    D. Chen, D.Z. Du, X.D. Hu, et al., Approximations for Steiner trees with minimum number of Steiner points, Theoretical Computer Science, Vol.262, No.1, pp.83-99, 2001.
    G.H. Lin and G. Xue, Steiner tree problem with minimum number of Steiner points and bounded edge-length, Information Processing Letters, Vol.69, No.2, pp.53-57, 1999.
    A. Kashyap, S. Khuller and M. Shayman, Relay placement for fault tolerance in wireless networks in higher dimensions, Computational Geometry, Vol.44, No.4, pp.206-215, 2011.
    A. Kashyap, S. Khuller and M. Shayman, Relay Placement for Higher Order Connectivity in Wireless Sensor Networks, INFOCOM 2006 25th IEEE International Conference on Computer Communications Proceedings, pp.1-12, 2006.
    S.Khuller and U. Vishkin, Biconnectivity yapproximations and graph carvings, Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, ACM, pp.759-770. 1992.
    A. Frank and É Tardos, An application of submodular flows, Linear Algebra and its Applications, Vol.114, pp.329-348, 1989.
    S. Khuller and B. Raghavachari, Improved approximation algorithms for uniform connectivity problems, Journal of Algorithms, Vol.21, No.2, pp.434-450, 1996.
    J. Tang, B. Hao and A. Sen, Relay node placement in large scale wireless sensor networks, Computer Communications, Vol.29, No.4, pp.490-501, 2006.
    E.L. Lloyd and G.L. Xue, Relay node placement in wireless sensor networks, IEEE Transactions on Computers, Vol.56, No.1, pp.134-138, 2007.
    W. Zhang, G. Xue and S. Misra, Fault-tolerant relay node placement in wireless sensor networks: Problems and algorithms, INFOCOM 2007, 26th IEEE International Conference on Computer Communications, IEEE, pp.1649-1657, 2007.
    G. Chen and S. Cui, Relay node placement in two-tiered wireless sensor networks with base stations, Journal of Combinatorial Optimization, pp.1-10, 2012.
    D.S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), Vol.32, No.1, pp.130-136, 1985.
    F. Senel and M. Younis, Relay node placement in structurally damaged wireless sensor networks via triangular steiner tree approximation, Computer Communications, Vol.34, No.16, pp.1932-1941, 2011.
    K.A. Xu, H. Hassanein, G. Takahara, Q.H. Wang, Relay node deployment strategies in heterogeneous wireless sensor networks, IEEE Transactions on Mobile Computing, Vol.9, No.2, pp.145-159, 2010.
  • 加载中

Catalog

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

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

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

    Article Metrics

    Article views (565) PDF downloads(1486) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return