Two stage decision making approach for Sensor Mission Assignment Problem

Rathi, K.; Balamohan, S.

RAIRO - Operations Research - Recherche Opérationnelle, Tome 50 (2016) no. 4-5, pp. 797-807.

Sensor Mission Assignment (SMA) is the process of assigning sensors to missions in the best way, which may depend on the cost of using individual sensors and the requirements of individual missions. SMA is Np-complete and is a special case of Generalized Assignment Problem. The significant bottlenecks in SMA are energy conservation and uncertainty in the demand of the missions. In order to conserve energy, some sensors are considered to be in sleeping state while others remain active for sensing. In this paper, Sensor Mission Assignment problem is studied in the context of Generalized Assignment Problem combined with decision making approach. Two stage decision making approach is formulated to determine the minimum number of sleeping sensors to be activated so as to assign exactly one sensor to each mission optimally subject to some of the energy resource constraints and environmental constraints imposed on it. The method draws upon the existing generalized assignment problem and the decision making approaches by analyzing trade-offs among desirable value of objective function and the constraints that include all the parameters. The proposed method is applied to the simulation on a small sized wireless sensor network and it is shown that the method is energy efficient. The proposed method provides more holistic point of view on the factors impacting sensor mission assignment.

Classification : 90B50
Mots clés : Sensor Mission Assignment, Generalized Assignment Problem, decision making

U. Aickelin and K.A. Dowsland, An indirect genetic algorithm for a nurse scheduling problem. Comput. Oper. Res. 31 (2004) 761–778. | DOI | Zbl

K.I. Ali, K. Deschinkel, M. Salomon and R. Couturier, Distributed lifetime coverage optimization protocol in wireless sensor networks. J. Supercomput. 71 12 (2015) 4578–4593. | DOI

M. Amini and M. Racer, A hybrid heuristic for the generalized assignment problem. Eur. J. Oper. Res. 87 (1995) 343–348. | DOI | Zbl

N. Bartolini, T. Calamoneri, T. La Porta, C. Petrioli and S. Silvestri, Sensor activation and radius adaptation (SARA) in heterogeneous networks. ACM Trans. Sensor Networks 8 (2012) 24. | DOI

S. Basagni, M. Yousof Naderi, C. Petrioli and D. Spenza, Wireless Sensor Networks with Energy Harvesting, Mobile Ad Hoc Networking: Cutting Edge Directions, chapter 20. John Wiley and Sons, Inc., Hoboken, NJ (2013) 703–736.

G. Bianchi, A.T. Capossele, C. Petrioli and D. Spenza, AGREE: Exploiting energy harvesting to support data-centric access control in WSNs. Ad Hoc Networks 11 (2013) 2625–2636. | DOI

J. Byers and G. Nasser, Utility-Based Decision-Making in Wireless Sensor Networks. Proc. of ACM MOBIHOC (2000).

D.G. Cattrysse and L.N.V. Wassenhove, A survey of algorithms for the generalized assignment problem. Eur. J. Oper. Res. 60 (1992) 260–272. | DOI | Zbl

P.C. Chu and J.E. Beasley, A genetic algorithm for the generalized assignment problem. Comput. Oper. Res. 24 (1997) 17–23. | DOI | MR | Zbl

R. Cohen, L. Katzir and D. Raz, An Efficient Approximation for the Generalized Assignment Problem. Inf. Process. Lett. 100 (2006) 162–166. | DOI | MR | Zbl

J.A. Diaz and E. Fernandez, A tabu search heuristic for the generalized assignment problem. Eur. J. Oper. Res. 132 (2001) 22–38. | DOI | MR | Zbl

L. Fleischer, M.X. Goemans, V.S. Mirrokni and M. Sviridenko, Tight Approximation Algorithms for Maximum General Assignment Problems. Proc. of 17th Ann. ACM-SIAM Symp. Discrete Algorithms (SODA ’06) (2006) 611–620. | MR | Zbl

S. Haddadi and H. Ouzia, Effective algorithm and heuristic for the generalized assignment problem. Eur. J. Oper. Res. 153 (2004) 184–190. | DOI | MR | Zbl

P.R. Harper, V. Senna, I.T. Vieira and A.K. Shahani, A genetic algorithm for the project assignment problem. Comput. Oper. Res. 32 (2005) 1255–1265. | DOI | Zbl

L. Lorena and M.G. Narciso, Relaxation heuristics for a generalized assignment problem. Eur. J. Oper. Res. 91 (1996) 600–610. | DOI | Zbl

L. Bao and T. Suda, Coverage-Aware Sensor Engagement in Dense Sensor Networks. Proc. of Int. Conf. Embedded and Ubiquitous Computing (EUC ’05) (2005).

L. Lulu, X. Liu, Y. Wang, W. Feng and G. Yang, SW-MAC: A low-latency MAC protocol with adaptive sleeping for wireless sensor networks. Wirel. Pers. Commun. 77 (2014) 1191–1211. | DOI

M.P. Johnson, H. Rowaihy, D. Pizzocaro, A. Bar-Noy, S. Chalmers, Th.F. La Porta and A. Preece, Sensor-Mission Assignment in Constrained Environments. IEEE Trans. Parallel Distrib. Syst. 21 (2010) 1692–1705. | DOI

M. Perillo and W. Heinzelman, Optimal Sensor Management under Energy and Reliability Constraints. Proc. of IEEE Wireless Comm. and Networking Conf. (WCNC) (2010).

D. Pizzocaro, M. Johnson, H. Rowaihy, S. Chalmers, A. Preece, A. Bar-Noy and T.L. Porta, A Knapsack Approach to Sensor-Mission Assignment with Uncertain Demands. Vol. 7112 of Proc. of SPIE Unmanned/Unattended Sensors and Sensor Networks V. SPIE Europe Security and Defence (2008) 5−12.

M. Rajani. I. Demirkol, O. Yang and He Ba, S. Ray and W. Heinzelman, Sleeping techniques for reducing energy dissipation. The Art of Wireless Sensor Networks Volume I: Fundamentals Part II. Springer Berlin Heidelberg (2014) 163–197.

G.T. Ross and R.M. Soland, A branch and bound algorithm for the generalized assignment problem. Math. Progr. 8 (1975) 91–103. | DOI | MR | Zbl

H. Rowaihy, S. Eswaran, M.P. Johnson, D. Verma, A. Bar-Noy, T. Brown and T. La Porta, A Survey of Sensor Selection Schemes in Wireless Sensor Networks. Proc. of Defense and Security Symposium on Unattended Ground, Sea. Air Sensor Technologies and applications (DSS 2007). Orlando, FL, USA (2007).

K. Shih, Y. Chen, C. Chiang and B. Liu, A Distributed Active Sensor Selection Scheme for Wireless Sensor Networks. Proc. of 11$th$ IEEE Symposium on Computers and Communications (IEEE ISCC 2006). Washington, DC, USA (2006) 923–928. | DOI

T. La Porta, C. Petrioli, C. Phillips and D. Spenza, Sensor Mission Assignment in Rechargeable Wireless Sensor Networks. ACM Trans. Sensor Netw. 60 (2014) 39.