In recent years, we have seen an increasing interest in developing and designing Wireless Sensor Networks (WSNs). WSNs consist of large number of nodes, with wireless communications and computation abilities that can be used in variety of domains. It has been used in areas that have direct contact with monitoring and gathering data, to name few, health monitoring, military surveillance, geological monitoring (Earthquakes, Volcanoes, Tsunami), agriculture control and many more. However, the design and implementation of WSNs face many challenges, due to the power limitation of sensor nodes, deployment and localization, data routing and data aggregation, data security, limited bandwidth, storage capacity and network management. It is known that Operation Research (OR) has been widely used in different areas to solve optimization problems; such as improving network performance and maximizing lifetime of system. In this survey, we present the most recent OR based techniques applied to solve different WSNs problems: the node scheduling problem, energy management problems, nodes allocating issues and other WSNs related complex problems. Different Operational Research techniques are presented and discussed in details here, including graph theory based techniques, linear programing and mixed integer programming related approaches.
Rawat, P., Singh, K.D., Chaouchi, H. and Bonnin, M. (2013) Wireless Sensor Networks: A Survey on Recent Developments and Potential Synergies. Journal of Supercomputing, 68, 1-48.
Baronti, P., Pillai, P., Chook, V., Chessa, S., Gotta, A. and Hu, Y.F. (2006) Wireless Sensor Networks: A Survey on the State of the Art and the 802.15.4 and ZigBee Standards. Computer Communications, 30, 1655-1695. https://doi.org/10.1016/j.comcom.2006.12.020
Akyildiz, I.F., Wang, X. and Wang, W. (2005) Wireless Mesh Networks: A Survey. Computer Networks, 47, 445-487. https://doi.org/10.1016/j.comnet.2004.12.001
Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422. https://doi.org/10.1016/s1389-1286(01)00302-4
Akkaya, K. and Younis, M. (2005) A Survey on Routing Protocols for Wireless Sensor Networks. Ad Hoc Networks, 3, 325-349.
Tounsi, M. and Mahlous, A.R. (2016) A Multi-Objective Model for Optimizing Network lifetime in Wireless Sensor Network. International Journal of Computer Science and Information Security (IJCSIS), 14, 562-569.
Homayounnejad, S. and Bagheri, A. (2015) An Efficient Distributed Max-Flow Algorithm for Wireless Sensor Networks. Journal of Network and Computer Applications, 54, 20-32.
Goldberg, A.V. and Tarjan, R.E. (1988) A New Approach to the Maximum-Flow Problem. JACM, 35, 921-940.
Pham, T.L., Lavallee, I., Bui, M. and Do, S.H. (2005) A Distributed Algorithm for the Maximum Flow Problem. Proceedings of the 4th International Symposium on Parallel and Distributed Computing, ISPDC, 131-138.
Vinoba, V. and Indhumathi (2015) A Detection of Optimal Path Using Quadratic Assigment Technique in Wireless Sensor Networks. International Journal of Application or Innovation in Engineering & Management (IJAIEM), 4.
Mishra, N. and Kumar, A. (2014) Comparative Analysis: Energy Efficient Multipath Routing in Wireless Sensor Network. International Journal of Computer Science and Mobile Computing, 3, 627-632.
Ye, Z., Krishnamurthy, S.V. and Tripathi, S.K. (2003) A Framework for Reliable Routing in Mobile Ad Hoc Networks. Proceedings of the IEEE INFOCOM, Vol. 1, San Francisco, 30 March-3 April 2003, 270-280. https://doi.org/10.1109/infcom.2003.1208679
Maimour, M. (2008) Maximally Radio-Disjoint Multipath Routing for Wireless Multimedia Sensor Networks. Proceedings of the 4th ACM Workshop on Wireless Multimedia Networking and Performance Modeling, Vancouver, 27-31 October 2008, 26-31.
Radi, M., Dezfouli, B. and Razak, S.A. (2010) LIEMRO: A Low Interference Energy Efficient Multipath Routing Protocol for Improving QoS in Event-Based Wireless Sensor Networks. Proceedings of 4th International Conference on Sensor Technologies and Applications, Venice, 18-25 July 2010, 551-557. https://doi.org/10.1109/sensorcomm.2010.89
Wang, Z., Bulut, E. and Szymanski, B.K. (2009) Energy Efficient Collision Aware Multipath Routing for Wireless Sensor Networks. Proceedings of IEEE International Conference on Communications, Dresden, 14-18 June 2009, 1-5.
Arora, Y. and Pande, H. (2013) Energy Saving Multipath Routing Protocol for Wireless Sensor Networks. International Journal of Engineering Research and Applications, 3, 152-156.
Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J. and Silva, F. (2002) Directed Diffusion for Wireless Sensor Networking. ACM/IEEE Transactions on Networking, 11, 2-16. https://doi.org/10.1109/TNET.2002.808417
Yahya, B. and Ben-Othman, J. (2009) REER: Robust and Energy Efficient Multipath Routing Protocol for Wireless Sensor Networks. Proceedings of IEEE Global Telecommunications Conference, Honolulu, 30 November-4 December 2009, 1-7. https://doi.org/10.1109/glocom.2009.5425587
Agre, J. and Clare, L. (2000) An Integrated Architecture for Cooperative Sensing Networks. Computer, 33, 106-108. https://doi.org/10.1109/2.841788
Heinzelman, W.R., Chandrakasa, A. and Balakrishnan, H. (2000) Energy Efficient Communication Protocol for Wireless Micro Sensor Networks. Proceedings of the 33th Annual Hawaii International Conference on System Sciences, Hawaii, 4-7 January 2000, 10. https://doi.org/10.1109/HICSS.2000.926982
Gandham, S.R., Dawande, M., Prakash, R. and Venkatesan, S. (2003) Energy Efficient Schemes for Wireless Sensor Networks with Multiple Mobile Base Stations. IEEE Global Telecommunications Conference, Vol. 1, San Francisco, 1-5 December 2003, 377-381. https://doi.org/10.1109/glocom.2003.1258265
Cardei, M., Wu, J., Lu, M. and Pervaiz, M.O. (2005) Maximum Network Lifetime in Wireless Sensor Networks with Adjustable Sensing Ranges. IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, Vol. 3, Montreal, 24-22 August 2005, 438-445. https://doi.org/10.1109/wimob.2005.1512935
Jantarasorn, C. and Prommak, C. (2012) Minimizing Energy Consumption in Wireless Sensor Networks Using Binary Integer Linear Programming. International Journal of Electrical, Computer, Energetic, Electronic and Communication Engineering, 6, 124-128.
Cheng, X., Narahari, B., Simha, R., Cheng, M.X. and Liu, D. (2003) Strong Minimum Energy Topology in WSNs: NP-Completeness and Heuristics. IEEE Transactions on Mobile Computing, 2, 248-256.
Wan, P.X.L. and Wang, Y. (2001) Power Efficient and Sparse Spanner for Wireless Ad Hoc Networks. 10th International Conference on Computer Communications and Networks, Scottsdale, 15-17 October 2001, 564-567.
Avril, F., Bernard, T., Bui, A. and Sohier, D. (2014) Clustering and Communications Scheduling in WSNs Using Mixed Integer Linear Programming. Journal of Communications and Networks, 16, 421-429. https://doi.org/10.1109/JCN.2014.000072
Chang, J.H. and Tassiulas, L. (2004) Maximum Lifetime Routing in Wireless Sensor Networks. IEEE/ACM Transactions on Networking, 12, 609-619. https://doi.org/10.1109/TNET.2004.833122
Ben-Othman, J., Bessaoud, K.K., Bui, A. and Pilard, L. (2013) Self-Stabilizing Algorithm for Efficient Topology Control in Wireless Sensor Networks. Journal of Computational Sciences, 4, 199-208. https://doi.org/10.1016/j.jocs.2012.01.003
Gogu, N.D., Dilo, A. And Mertnia, N. (2011) Optimization Problems in Wireless Sensor Networks. International Conference on Complex, Intelligent and Software Intensive Systems, Seoul, 30 June-2 July 2011, 302-309. https://doi.org/10.1109/cisis.2011.50
Efrat, A., Peled, S. and Mitchel, J. (2005) Approximation Algorithms for Two Optimal Location Problems in Sensor Networks. Broadband Networks, 1, 714-723.
Cavalier, T.M., Conner, W., Castillo, E. and Brown, S. (2007) A Heuristic Algorithm for Minimax Sensor Location in the Plane. European Journal of Operational Research, 183, 42-55. https://doi.org/10.1016/j.ejor.2006.10.055
Meguerdichian, S., Koushanfar, F., Potkonjak, M. and Srivastava, M.B. (2001) Coverage Problems in Wireless Ad Hoc Sensor Networks. 20th Annual Joint Conference of the IEEE Computer and Communications Societies, Anchorage, 22-26 April 2001, 1380-1387.
Purohit, G.N. and Sharma, U. (2010) Constructing Minimum Connected Dominating Set: Algorithmic Approach. International Journal on Applications of Graph Theory in Wireless Ad Hoc Networks and Sensor Networks, 2, 59-66. https://doi.org/10.5121/jgraphoc.2010.2305
Clark, B.N., Colbourn, C.J. and Johnson, D.S. (1990) Unit Disk Graphs. Discrete Math, 86, 165-177. https://doi.org/10.1016/0012-365X(90)90358-O
Guha, S. and Khuller, S. (1998) Approximation Algorithms for Connected Dominating Sets. Algorithmica, 20, 374-387. https://doi.org/10.1007/pl00009201
Wu, Y., Stankovic, J.A., He, T., Lu, J. and Lin, S. (2008) Realistic and Efficient Multi-Channel Communications in Wireless Sensor Networks. Proceedings of IEEE INFOCOM, 12, 1193-1201.
Vincze, Z., Vida, R. and Vidacs, A. (2007) Deploying Multiple Sinks in Multi-Hop Wireless Sensor Networks. Proceedings of IEEE International Conference on Pervasive Services, Istanbul, 15-20 July 2007, 55-63. https://doi.org/10.1109/PERSER.2007.4283889
Wang, Z.M., Basagni, S., Melachrinoudis, E. and Petrioli, C. (2005) Exploiting Sink Mobility for Maximizing Sensor Networks Lifetime. Proceedings of the 38th Hawaii International Conference on System Sciences, Hawaii, 3-6 January 2005, 1-9.
Gagnon, J. and Narayanan, L. (2015) Efficient Scheduling for Minimum Latency Aggregation in Wireless Sensor Networks. Proceedings of IEEE Wireless Communications and Networking Conference, New Orleans, 9-12 March 2015, 1024-1029. https://doi.org/10.1109/wcnc.2015.7127610
Wan, P.-J., Huang, S.C.-H., Wang, L., Wan, Z. and Jia, X. (2009) Minimum-Latency Aggregation Scheduling in Multihop Wireless Networks. Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, New Orleans, 18-21 May 2009, 185-194. https://doi.org/10.1145/1530748.1530773
Malhotra, B., Nikolaidis, I. and Nascimento, M.A. (2011) Aggregation Convergecast Scheduling in Wireless Sensor Networks. Wireless Networks, 17, 319-335. https://doi.org/10.1007/s11276-010-0282-y
Zonouz, A.E. and Vokkarane, V.M. (2014) Reliability-Oriented Single-Path Routing Protocols in Wireless Sensor Networks. IEEE Sensors Journal, 14, 4059-4068. https://doi.org/10.1109/JSEN.2014.2332296
Asorey-Cacheda, R., García-Sánchez, A.J., García-Sánchez, F., García-Haro, J. and González-Castano, F.J. (2013) On Maximizing the Lifetime of Wireless Sensor Networks by Optimally Assigning Energy Supplies. Sensors, 13, 10219-10244.
Hou, Y.T., Shi, Y. and Sherali, H.D. (2005) On Energy Provisioning and Relay Node Placement for Wireless Sensor Networks. IEEE Transactions on Wireless Communications, 4, 2579-2590.
Chang, J. and Tassiulas, L. (2004) Maximum Lifetime Routing in Wireless Sensor Networks. IEEE/ACM Transaction on Networking, 12, 609-619. https://doi.org/10.1109/TNET.2004.833122
Luz, Y.M. and Wong, V. (2007) An Energy-Efficient Multipath Routing Protocol for Wireless Sensor Networks. International Journal of Communication Systems, 20, 747-766. https://doi.org/10.1002/dac.843
Guney, E., Aras, N., Altinel, K. and Ersoy, C. (2010) Efficient Integer Programming Formulations for Optimum Sink Location and Routing in Heterogeneous WSN. Computer Networks, 54, 1805-1822. https://doi.org/10.1016/j.comnet.2010.02.009
Nivas, T. and Zaruba, G. (2007) Upper Bound of Sensor Network Lifetime: A Flow Optimization Approach. Proceedings of the ACM GHCCWC.
Rossi, A., Singh, A. and Sevaux, M. (2010) Generation de colonnes dans le reseaux de capteurs sans fil. Proceedings of ROADEF.
Attarde, S.A., Ragha, L.L. and Dhamal, S.K. (2010) An Enhanced Spanning Tree Topology for Wireless Sensor Networks. International Journal of Computer Applications, 1, 46-51.
Ergen, S. and Varaiya, P. (2010) TDMA Scheduling Algorithms for WSN. Wireless Networks, 16, 985-997. https://doi.org/10.1007/s11276-009-0183-0
Jayalakshmi, R., Baranidharan, B. and Santhi, B. (2014) Attribute Based Spanning Tree Construction for Data Aggregation in Heterogeneous Wireless Sensor Networks. Indian Journal of Science and Technology, 7, 76-79.
Lachowski, R., Pellenz, M.E., Penna, M.C., Jamhour, E. and Souza, R.D. (2015) An Efficient Distributed Algorithm for Constructing Spanning Trees in Wireless Sensor Networks. Sensors, 15, 1518-1536. https://doi.org/10.3390/s150101518
Khan, G., Bathla, G. and Ali, W. (2011) Minimum Spanning Tree based Routing Strategy for Homogeneous WSN. International Journal on Cloud Computing: Services and Architecture, 1, 22-29.
Vashist, R. and Dutt, S. (2014) Minimum Spanning Tree based Improved Routing Protocol for Heterogeneous Wireless Sensor Network. International Journal of Computer Applications, 103, 29-33.
Saha, S. and McLauchlan, L. (2015) An Approach to Construct Weighted Minimum Spanning Tree in Wireless Sensor Networks. In: Lee, R., Ed., Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing, Vol. 569, Springer International Publishing, Cham, 69-84.
Vijay, U. and Gupta, N. (2013) Clustering in WSN Based on Minimum Spanning Tree Using Divide and Conquer Approach. International Journal of Computer, Electrical, Automation, Control and Information Engineering, 7, 926-930.
Saravanan, M. and Madheswaran, M. (2014) A Hybrid Optimized Weighted Minimum Spanning Tree for the Shortest Intrapath Selection in Wireless Sensor Network. Mathematical Problems in Engineering, 2014, Article ID: 713427. https://doi.org/10.1155/2014/713427
Suto, K., Nishiyama, H., Kato, N. and Huang, C.W. (2015) An Energy-Efficient and Delay-Aware Wireless Computing System for Industrial Wireless Sensor Networks. IEEE Access, 3, 1026-1035. https://doi.org/10.1109/ACCESS.2015.2443171
Yu, Y., Krishnamachari, B. and Prasanna, V.K. (2004) Energy-Latency Tradeoffs for Data Gathering in Wireless Sensor Networks. Proceedings IEEE International Conference on Computer Communications, Hong Kong, 7-11 March 2004, 244-255.
Dong, M., Ota, K., Liu, A. and Guo, M. (2016) Joint Optimization of Lifetime and Transport Delay under Reliability Constraint Wireless Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, 27, 225-236. https://doi.org/10.1109/TPDS.2015.2388482
Choi, W. and Das, S. (2005) A Novel Framework for Energy-Conserving Data Gathering in Wireless Sensor Networks. Proceedings IEEE International Conference on Computer Communications, Miami, 13-17 March 2005, 1985-1996.
Cheng, C.T., Tse, C.K. and Lau, F.C.M. (2010) A Delay-Aware Data Collection Network Structure for Wireless Sensor Networks. IEEE Sensors Journal, 11, 699-710. https://doi.org/10.1109/JSEN.2010.2063020
Ammari, H.M. and Das, S.K. (2005) Trade-Off between Energy Savings and Source-to-Sink Delay in Data Dissemination for Wireless Sensor Networks. Proceedings of 8th ACM International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems, Montreal, 10-13 October 2005, 126-133. https://doi.org/10.1145/1089444.1089467