research-article

Using dynamic programming to solve the Wireless Sensor Network Configuration Problem

Authors:

Enrico Natalizio,

Yacine ChallalAuthors Info & Claims

Journal of Network and Computer Applications, Volume 83, Issue C

Pages 140 - 154

https://doi.org/10.1016/j.jnca.2017.01.022

Published: 01 April 2017 Publication History

Abstract

This work studies the problem of network configuration for Wireless Sensor Networks (WSN), consisting of two interdependent problems: sensor placement and topology control, by taking into consideration both the traffic load and the transmission range assignment. The design objectives are (i) reducing the overall energy consumption and (ii) ensuring node energy consumption fairness between the sensors. First, the problem of placing the sensors in the optimal positions is studied and then a power control scheme is put in place to manage the topology of the network. For both the two sub-problems, we first consider the one dimensional (or linear) network case and next the two-dimensional case. The two sub-problems are considered within a unifying mathematical framework based on dynamic programming, in order to guarantee the optimality of the solution. The method can easily be adapted to solve the problem for discrete values of transmission range. The method presented in this work shows a low computational complexity in comparison to other methods, and, due to its implementation simplicity, it may be of great help to network designers in the planning phase of WSN deployment.

References

[1]

I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless sensor networks, Comput. Netw., 38 (2002) 393-422.

Digital Library

[2]

A.A. Aziz, Y.A. Sekercioglu, P. Fitzpatrick, M. Ivanovich, A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks, IEEE Commun. Surv. Tutor., 15 (2013) 121-144.

[3]

R. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, USA, 1957. http://books.google.com/books?id=fyVtp3EMxasC&pg=PR5&dq=dynamic+programming+richard+e+bellman&client=firefox-a#v=onepage&q=dynamic%20programming%20richard%20e%20bellman&f=false

[4]

C.-Y. Chang, H.-R. Chang, Energy-aware node placement, topology control and mac scheduling for wireless sensor networks, Comput. Netw., 52 (2008) 2189-2204.

Digital Library

[5]

Chelli, A., Bagaa, M., Djenouri, D., Balasingham, I., Taleb, T., 2016. One-step approach for two-tiered constrained relay node placement in wireless sensor networks. In: IEEE Wireless Communications Letters, vol. 5 of 4, pp. 448451

[6]

Y. Chen, C. Chuah, Q. Zhao, Network configuration for optimal utilization efficiency of wireless sensor networks, Ad Hoc Netw., 6 (2008) 92-107.

Digital Library

[7]

Cheng,P., Chuah,C., Liu, X., 2004. Energy-aware node placement in wireless sensor networks. In:IEEE GLOBECOM, vol. 5, pp. 32103214.

[8]

Cristescu, R., Lozano, B.B., Vetterli, M., Wattenhofer, R., Network correlated data gathering with explicit communication: Np-completeness and algorithms. In:Infocom.

[9]

F. D'Andreagiovanni, A. Nardin, Towards the fast and robust optimal design ofwireless body area networks, Appl. Soft Comput., 37 (2015) 971-982.

Digital Library

[10]

D'Andreagiovanni, F., Nardin, A., Natalizio, E., 2017. A fast ILP-based Heuristic for the robust design of Body Wireless Sensor Networks.To appear in: Applications of Evolutionary Computation, LNCS, Springer, Heidelberg.

[11]

Gao, Q., Blow, K., Holding, D., Marshall, I.W., Peng, X., 2006. Radio range adjustment for energy efficient wireless sensor networks, Ad Hoc Netw. 7582.

Digital Library

[12]

A. Gogu, D. Nace, Y. Challal, A note on joint optimal transmission range assignment and deployment for wireless sensor networks, IEEE Netw. (2010) 1-6.

[13]

F. Guerriero, A. Violi, E. Natalizio, V. Loscri, C. Costanzo, Modelling and solving optimal placement problems in wireless sensor networks, Appl. Math. Model., 35 (2011) 230-241.

[14]

Hao,B., Tang,H., Xue, G., 2004. Fault-tolerant relay node placement in wireless sensor networks. In: HPSR, pp. 246250.

[15]

Heinzelman, W.R., Chandrakasan, A., Balakrishnan, H., 2000. Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Hawaii International Conference on System Sciences, HICSS 00, vol. 8. IEEE Computer Society, Washington, DC, USA, 2000, pp. 80208032.

Digital Library

[16]

O. Hseyin, I. Krpeolu, Power efficient data gathering and aggregation in wireless sensor networks, SIGMOD Rec., 32 (2003) 66-71.

Digital Library

[17]

S.M. Jameii, K. Faez, M. Dehghan, Multiobjective optimization for topology and coverage control in wireless sensor networks, Int. J. Distrib. Sens. Netw. (2015).

[18]

J. Li, P. Mohapatra, Analytical modeling and mitigation techniques for the energy hole problem in sensor networks, Pervasive Mob. Comput. (2007) 233-254.

Digital Library

[19]

M. Li, Z. Li, A.V. Vasilakos, A survey on topology control in wireless sensor networks, Proc. IEEE, 101 (2013) 2538-2557.

[20]

Ma, C., Liang, W., Zheng, M., 2016. Set-covering-based algorithm for delay constrained relay node placement in wireless sensor networks. In: IEEE International Conference on Communications (ICC), pp. 16

[21]

V. Mhatre, C. Rosenberg, D.K.R. Mazmudar, N. Shrof, Design guidelines for wireless sensor networks, Ad Hoc Netw., 2 (2004) 45-63.

[22]

E. Natalizio, V. Loscri, E. Viterbo, Optimal placement of wireless nodes for maximizing path lifetime, IEEE Commun. Lett., 12 (2008) 362-364.

[23]

E. Natalizio, V. Loscri, F. Guerriero, A. Violi, Energy spaced placement for bidirectional data flows in wireless sensor network, IEEE Commun. Lett., 13 (2009) 22-24.

Digital Library

[24]

Olariu, S., Stojmenovi, I., 2006. Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting. In: IEEE INFOCOM, pp. 112.

[25]

A.U. Rahman, A. Alharby, H. Hasbullah, K. Almuzaini, Corona based deployment strategies in wireless sensor network, J. Netw. Comput. Appl., 64 (2016) 176-193.

Digital Library

[26]

P. Santi, Topology control in wireless ad hoc and sensor networks, ACM Comput. Surv., 37 (2005) 164-194.

Digital Library

[27]

S. Sengupta, S. Das, M. Nasir, B. Panigrahi, Multi-objective node deployment in wsns, Eng. Appl. Artif. Intell., 26 (2013) 405-416.

Digital Library

[28]

C. Song, M. Liu, J. Cao, Y. Zheng, H. Gong, G. Chen, Maximizing network lifetime based on transmission range adjustment in wireless sensor networks, Comput. Commun., 32 (2009) 1316-1325.

Digital Library

[29]

Q. Tan, W. An, Y. Han, Y. Liu, S. Ci, F.-M. Shao, H. Tang, Energy harvesting aware topology control with power adaptation in wireless sensor networks, Ad Hoc Netw., 27 (2015) 44-56.

Digital Library

[30]

P. Thulasiraman, K.A. White, Topology control of tactical wireless sensor networks using energy efficient zone routing, Digit. Commun. Netw., 2 (2016) 1-14.

[31]

Y. Tsai, K. Yang, S. Yeh, Non-uniform node deployment for lifetime extension in large-scale randomly distributed wireless sensor networks, AINA Proc. (2008) 517-524.

Digital Library

[32]

Wang, G., Cao, G., Porta, T.L., Zhang, W., 2005. Sensor relocation in mobile sensor networks.In: INFOCOM. Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 4, pp. 23022312.

[33]

Wang,X., Gu,W., Chellappan,S., Schosek,K., Xuan, D., 2005. Lifetime optimization of sensor networks under physical attacks. In: IEEE ICC, vol. 5, pp. 32953301.

[34]

X. Wu, G. Chen, S.K. Das, On the energy hole problem of nonuniform node distribution in wireless sensor networks, Mob. Adhoc Sens. Syst. (2006) 180-187.

[35]

M. Younis, K. Akkaya, Strategies and techniques for node placement in wireless sensor networks, Ad Hoc Netw., 6 (2008) 621-655.

Digital Library

[36]

Yun, Y.S., Xia, Y., 2013. A method for deciding node densities in non-uniform deployment of wireless sensors.In: 11th International Symposium onModeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt), Tsukuba Science City, pp. 264271.

[37]

H. Zhang, H. Shen, Balancing energy consumption to maximize network lifetime in data-gathering sensor networks, IEEE Trans. Parallel Distrib. Syst., 20 (2009) 1526-1539.

Digital Library

Cited By

Fedorenko VOleinikov DSamoylenko ISamoylenko V(2023)Criteria for the deployment of a heterogeneous linear WSNAd Hoc Networks10.1016/j.adhoc.2023.103202147:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.adhoc.2023.103202
Kirov DNuzzo PPasserone RSangiovanni-Vincentelli A(2018)Optimized selection of wireless network topologies and components via efficient pruning of feasible pathsProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196086(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196086
Kirov DNuzzo PPasserone RSangiovanni-Vincentelli A(2018)Optimized Selection of Wireless Network Topologies and Components via Efficient Pruning of Feasible Paths2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC)10.1109/DAC.2018.8465910(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1109/DAC.2018.8465910

Index Terms

Using dynamic programming to solve the Wireless Sensor Network Configuration Problem
1. Networks
  1. Network types
    1. Mobile networks

Index terms have been assigned to the content through auto-classification.

Recommendations

Network configuration for optimal utilization efficiency of wireless sensor networks

This paper addresses the problem of configuring wireless sensor networks (WSNs). Specifically, we seek answers to the following questions: how many sensors should be deployed, what is the optimal sensor placement, and which transmission structure should ...
A Framework for Solving the Configuration Problem in Wireless Sensor Networks
BWCCA '13: Proceedings of the 2013 Eighth International Conference on Broadband and Wireless Computing, Communication and Applications

Wireless Sensor Network Configuration Problem seeks to dimension a WSN while taking into account both the traffic pattern, data aggregation and the transmission range assignment. Regarding the objectives of the problem, we first intend to minimize the ...
Energy-Aware Network Configuration for Wireless Sensor Networks
NBIS '11: Proceedings of the 2011 14th International Conference on Network-Based Information Systems

This work addresses the problem of designing the optimal network configuration for Wireless Sensor Network (WSNs). Specifically, given a surveying area our goal is to determine the parameters of network configuration such that some objectives are met. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Network and Computer Applications

Journal of Network and Computer Applications Volume 83, Issue C

April 2017

221 pages

ISSN:1084-8045

Issue’s Table of Contents

Copyright © Elsevier Ltd.

Publisher

Academic Press Ltd.

United Kingdom

Publication History

Published: 01 April 2017

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fedorenko VOleinikov DSamoylenko ISamoylenko V(2023)Criteria for the deployment of a heterogeneous linear WSNAd Hoc Networks10.1016/j.adhoc.2023.103202147:COnline publication date: 1-Aug-2023
https://dl.acm.org/doi/10.1016/j.adhoc.2023.103202
Kirov DNuzzo PPasserone RSangiovanni-Vincentelli A(2018)Optimized selection of wireless network topologies and components via efficient pruning of feasible pathsProceedings of the 55th Annual Design Automation Conference10.1145/3195970.3196086(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1145/3195970.3196086
Kirov DNuzzo PPasserone RSangiovanni-Vincentelli A(2018)Optimized Selection of Wireless Network Topologies and Components via Efficient Pruning of Feasible Paths2018 55th ACM/ESDA/IEEE Design Automation Conference (DAC)10.1109/DAC.2018.8465910(1-6)Online publication date: 24-Jun-2018
https://dl.acm.org/doi/10.1109/DAC.2018.8465910

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents