Logo PTI
Polish Information Processing Society
Logo FedCSIS

Annals of Computer Science and Information Systems, Volume 18

Proceedings of the 2019 Federated Conference on Computer Science and Information Systems

Using Relay Nodes in Wireless Sensor Networks: A Review

, ,

DOI: http://dx.doi.org/10.15439/2019F26

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 479–486 ()

Full text

Abstract. To extend the lifetime of wireless sensor networks, recent works suggest the use of relay nodes. This paper surveys and examines representative approaches dealing with relay nodes deployment. It also discusses their shortcomings and presents a comparative study. Additionally, this paper provides a set of remarks and recommendations to improve the usage of relay nodes in wireless sensor networks and highlights open issues that need further investigation.

References

  1. M. R. Senouci and A. Mellouk, Deploying Wireless Sensor Networks: Theory and Practice. Elsevier, 2016.
  2. J. M. Lanza-Gutierrez and J. A. Gomez-Pulido, “A gravitational search algorithm for solving the relay node placement problem in wireless sensor networks,” International Journal of Communication Systems, vol. 30, no. 2, 2015. http://dx.doi.org/10.1002/dac.2957
  3. D. Wu, D. Chatzigeorgiou, K. Youcef-Toumi, S. Mekid, and R. Ben-Mansour, “Channel-Aware Relay Node Placement in Wireless Sensor Networks for Pipeline Inspection,” Transactions on Wireless Communications, vol. 13, no. 7, pp. 3510–3523, 2014. http://dx.doi.org/10.1109/TWC.2014.2314120
  4. D. Yang, S. Misra, X. Fang, G. Xue, and J. Zhang, “Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks: Computational Complexity and Efficient Approximations,” Transactions on Mobile Computing, vol. 11, no. 8, pp. 1–13, 2012. http://dx.doi.org/10.1109/TMC.2011.126
  5. S. Misra, N. E. Majd, and H. Huang, “Approximation Algorithms for Constrained Relay Node Placement in Energy Harvesting Wireless Sensor Networks,” Transactions on Computers, vol. 63, no. 12, pp. 2933–2947, 2013. http://dx.doi.org/10.1109/TC.2013.171
  6. H. Zeng and Z. Kang, “Relay Node Placement to Restore Connectivity in Wireless Sensor Networks,” in 9th International Conference on Communication Software and Networks (ICCSN), Guangzhou, China, Dec. 2017. http://dx.doi.org/10.1109/ICCSN.2017.8230124 pp. 301–305.
  7. G. Xiong, L. Hong, and Y. Guangyou, “Improving Energy Efficiency by Optimizing Relay Nodes Deployment in Wireless Sensor Networks,” in 9th International Conference on Communication Software and Networks (ICCSN), Guangzhou, China, Dec. 2017. http://dx.doi.org/10.1109/ICCSN.2017.8230125 pp. 306–310.
  8. C. Ma, W. Liang, and M. Zheng, “Set-Covering-based Algorithm for Delay Constrained Relay Node Placement in Wireless Sensor Networks,” in International Conference on Communications (ICC), Kuala Lumpur, Malaysia, July 2016. http://dx.doi.org/10.1109/ICC.2016.7510976 pp. 1–6.
  9. C. Ma, W. Liang, M. Zheng, and H. Sharif, “A Connectivity-Aware Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks,” Sensors, vol. 16, no. 2, pp. 515–528, 2015. http://dx.doi.org/10.1109/JSEN.2015.2456931
  10. Q. Chen, Y. Hu, Z. Chen, V. Grout, D. Zhang, H. Wang, and H. Xing, “Improved Relay Node Placement Algorithm for Wireless Sensor Networks Application in Wind Farm,” in International Conference on Smart Energy Grid Engineering (SEGE), Oshawa, Canada, Jan. 2013. http://dx.doi.org/10.1109/SEGE.2013.6707901 pp. 1–6.
  11. D. Djenouri and M. Bagaa, “Energy Harvesting Aware Relay Node Addition for Power-Efficient Coverage in Wireless Sensor Networks,” in International Conference on Communications (ICC). London, UK: IEEE, Sep. 2015. http://dx.doi.org/10.1109/ICC.2015.7248303 pp. 86–91.
  12. A. Chelli, M. Bagaa, D. Djenouri, I. Balasingham, and T. Taleb, “One Step Approach for Two-Tiered Constrained Relay Node Placement in Wireless Sensor Networks,” Wireless Communications Letters, vol. 5, no. 4, pp. 448–451, 2016. http://dx.doi.org/10.1109/LWC.2016.2583426
  13. C. Ma, W. Liang, and M. Zheng, “Delay Constrained Relay Node Placement in Two-tiered Wireless Sensor Networks: A Set-Covering-based Algorithm,” Journal of Network and Computer Applications, vol. 93, pp. 76–90, 2017. http://dx.doi.org/10.1016/j.jnca.2017.05.004
  14. K. Nitesh and P. K. Jana, “Relay Node Placement with Assured Coverage and Connectivity: A Jarvis March Approach,” Wireless Personal Communications, vol. 98, no. 1, pp. 1361–1381, 2017. http://dx.doi.org/10.1007/s11277-017-4922-8
  15. E. L. Lloyd and G. Xue, “Relay Node Placement in Wireless Sensor Networks,” Transactions on Computers, vol. 56, no. 1, pp. 134–138, 2007. http://dx.doi.org/10.1007/s11276-006-0724-8
  16. S. Xu, L. Jiang, C. He, and Q. Xi, “Relay Node Placement in Partitioned Wireless Sensor Networks with Guaranteed Lifetime,” in Global Communications Conference (GLOBECOM), Atlanta, USA, June 2013. http://dx.doi.org/10.1109/GLOCOM.2013.6831078 pp. 243–248.
  17. C. Zhou, A. Mazumder, A. Das, K. Basu, N. Matin-Moghaddam, S. Mehrani, and A. Sen, “Relay Node Placement Under Budget Constraint,” in 19th International Conference on Distributed Computing and Networking, Varanasi, India, Jan. 2018. http://dx.doi.org/10.1145/3154273.3154302 pp. 1–6.
  18. Y.-H. Xu, W.-G. Jiao, YinWu, and J. Song, “Variable-dimension swarm meta-heuristic for the optimal placement of relay nodes in wireless sensor networks,” International Journal of Distributed Sensor Networks, vol. 13, no. 3, pp. 1–15, 2017. http://dx.doi.org/10.1177/1550147717700895
  19. S. Misra, S. D. Hong, G. L. Xue, and J. Tang, “Constrained Relay Node Placement in Wireless Sensor Networks: Formulation and Approximations,” IEEE/ACM Transactions on Networking, vol. 18, no. 2, pp. 434–447, 2010. doi: 10.1109/TNET.2009.2033273
  20. M. Azharuddin and P. K. Jana, “A GA-based approach for fault tolerant relay node placement in wireless sensor networks,” in Third International Conference on Computer, Communication, Control and Information Technology (C3IT), Hooghly, India, March 2015. http://dx.doi.org/10.1109/C3IT.2015.7060111 pp. 1–6.
  21. W. Zhang, G. Xue, and S. Misra, “Fault-Tolerant Relay Node Placement in Wireless Sensor Networks: Problems and Algorithms,” in 26th International Conference on Computer Communications, Barcelona, Spain, May 2007. http://dx.doi.org/10.1109/INF-COM.2007.193 pp. 1649–1657.
  22. M. Bagaa, A. Chelli, D. Djenouri, T. Taleb, I. Balasingham, and K. Kansanen, “Optimal Placement of Relay Nodes Over Limited Positions in Wireless Sensor Networks,” IEEE Transactions on Wireless Communications, vol. 16, no. 4, pp. 2205–2219, 2017. http://dx.doi.org/10.1109/TWC.2017.2658598
  23. W. Zhu, S. Xianhe, L. Cuicui, and C. Jianhui, “Relay Node Placement Algorithm Based on Grid in Wireless Sensor Network,” in Third International Conference on Instrumentation, Measurement, Computer, Communication and Control, Shenyang, China, June 2013. http://dx.doi.org/10.1109/IMCCC.2013.65 pp. 278–283.
  24. M. Shokrnezhad, V. Zolfaghari, and S. Khorsandi, “Relay Node Placement in Mission Critical Smart Grid Networks,” in 7’th International Symposium on Telecommunications, Tehran, Iran, Sept. 2014. http://dx.doi.org/10.1109/ISTEL.2014.7000794 pp. 707–711.
  25. D. Djenouri and M. Bagaa, “Energy-Aware Constrained Relay Node Deployment for Sustainable Wireless Sensor Networks,” Transactions on Sustainable Computing, vol. 2, no. 1, pp. 30–42, 2017. http://dx.doi.org/10.1109/TSUSC.2017.2666844
  26. Z. Zheng, L. X. Cai, R. Zhang, and X. S. Shen, “RNP-SA: Joint Relay Placement and Sub-Carrier Allocation in Wireless Communication Networks with Sustainable Energy,” Transactions on Wireless Communications, vol. 11, no. 10, pp. 3818–3828, 2012. http://dx.doi.org/10.1109/TWC.2012.090312.120461
  27. B. O. Ayinde and H. A. Hashim, “Energy-Efficient Deployment of Relay Nodes in Wireless Sensor Networks Using Evolutionary Techniques,” International Journal of Wireless Information Networks, vol. 25, no. 2, pp. 157–172, 2018. http://dx.doi.org/10.1007/s10776-018-0388-1
  28. M. Nikolov and Z. J. Haas, “Relay Placement in Wireless Networks: Minimizing Communication Cost,” Transactions on Wireless Communications, vol. 15, no. 5, pp. 3587–3602, 2016. http://dx.doi.org/10.1109/TWC.2016.2523984
  29. A. Bhattacharya and A. Kumar, “Delay Constrained Optimal Relay Placement for Planned Wireless Sensor Networks,” in 18th International Workshop on Quality of Service (IWQoS), Beijing, China, Aug. 2010. http://dx.doi.org/10.1109/IWQoS.2010.5542760 pp. 1–9.
  30. R. Liu, I. J. Wassell, and K. Soga, “Relay Node Placement for Wireless Sensor Networks Deployed in Tunnels,” in 6th International Conference on Wireless and Mobile Computing, Networking and Communications, Niagara Falls, Canada, Nov. 2010. http://dx.doi.org/10.1109/WIMOB.2010.5644984 pp. 144–150.
  31. M. Zafer, M. R. Senouci, and M. Aissani, “Terrain Partitioning Based Approach for Realistic Deployment of Wireless Sensor Networks,” in International Conference on Computational Intelligence and Its Applications, May 2018. http://dx.doi.org/10.1007/978-3-319-89743-1 37 pp. 423–435.
  32. F. M. Al-Turjman, A. E. Al-Fagih, W. M. Alsalih, and H. S. Hassanein, “A delay-tolerant Framework for Integrated RSNs in IoT,” Computer Communications, vol. 36, no. 9, pp. 998–1010, 2013. http://dx.doi.org/10.1016/j.comcom.2012.07.001
  33. A. Nigam and Y. K. Agarwal, “Optimal Relay Node Placement in Delay Constrained Wireless Sensor Network Design,” European Journal of Operational Research, vol. 233, no. 1, pp. 220–233, 2014. http://dx.doi.org/10.1016/j.ejor.2013.08.031
  34. L. T. Kou, G. Markowsky, and L. Berman, “A Fast Algorithm for Steiner Trees,” Acta Informatica, vol. 15, no. 2, pp. 141–145, 1981. http://dx.doi.org/10.1007/BF00288961
  35. Z.-X. Yang, X.-Y. Jia, J.-Y. Hao, and Y.-P. Gao, “Geometry experiment algorithm for steiner minimal tree problem,” Journal of Applied Mathematics, vol. 2013, pp. 507–508, 2013. http://dx.doi.org/10.1155/2013/367107
  36. “Ilog cplex: Software for mathematical programming and optimization,” http://www.ilog.com/products/cplex/, 2002.
  37. D. Kim, Z. Zhang, X. Li, W. Wang, W. Wu, and D.-Z. Du, “A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs,” Transactions on Mobile Computing, vol. 9, no. 8, pp. 1108–1118, 2010. http://dx.doi.org/10.1109/TMC.2010.55
  38. homas H. Cormen, C. E. Leiserson, C. L. Rivest, and C. Stein, Introduction to Algorithm. MIT Press and McGraw-Hill, 2009.
  39. M. Zafer, M. R. Senouci, and M. Aissani, “A Practical Data Driven Approach for the Deployment of WSNs on Realistic Terrains,” Transactions on Emerging Telecommunications Technologies, Jan. 2019. http://dx.doi.org/10.1002/ett.3558
  40. C. Ma, W. Liang, M. Zheng, and H. Sharif, “A Novel Local Search Approximation Algorithm for Relay Node Placement in Wireless Sensor Networks,” in Wireless Communications and Networking Conference (WCNC), New Orleans, USA, June 2015. http://dx.doi.org/10.1109/WCNC.2015.7127693 pp. 1536–1541.
  41. F. Al-Turjman, “Optimized Hexagon-based Deployment for Large-Scale Ubiquitous Sensor Networks,” Journal of Network and Systems Management, vol. 26, no. 2, pp. 255–283, 2017. http://dx.doi.org/10.1007/s10922-017-9415-2
  42. C. Zhou, A. Mazumder, A. Das, K. Basu, N. Matin-Moghaddam, S. Mehrani, and A. Sen, “Relay Node Placement Under Budget Constraint,” Pervasive and Mobile Computing, vol. 53, pp. 1–12, 2019. http://dx.doi.org/10.1016/j.pmcj.2018.12.001
  43. A. Bhattacharya and A. Kumar, “A Shortest Path Tree Based Algorithm for Relay Placement in a Wireless Sensor Network and Its Performance Analysis,” Computer Networks, vol. 71, pp. 48–62, 2014. http://dx.doi.org/10.1016/j.comnet.2014.06.011
  44. F. Al-Turjman, “QoS-aware Data Delivery Framework for Safety-inspired Multimedia in Integrated Vehicular-IoT,” Computer Communications, vol. 121, pp. 33–43, May 2018. http://dx.doi.org/10.1016/j.comcom.2018.02.012
  45. M. Zafer, M. R. Senouci, and M. Aissani, “Fault-Tolerant Data Transport Backbone for 3D Wireless Sensor Networks,” Transactions on Emerging Telecommunications Technologies, May 2019. http://dx.doi.org/10.1002/ett.3660
  46. F. Al-Turjman, “Cognitive Routing Protocol for Disaster-inspired Internet of Things,” Future Generation Computer Systems, vol. 42, pp. 317–334, March 2017. http://dx.doi.org/10.1016/j.future.2017.03.014