A New Game Theory-Based Algorithm for Target Coverage in Directional Sensor Networks
Subject Areas : Wireless NetworkElham Golrasan 1 * , marzieh varposhti 2
1 - Faculty of Electrical and Computer Engineering, Malek-Ashtar University of Technology, Iran
2 - Department of Computer Engineering Shahrekord University, Shahrekord, Iran
Keywords: Directional Sensor Networks, Target Coverage, Network Lifetime, Game Theory, Payoff-Based Learning Algorithm.,
Abstract :
One of the challenging problems in directional sensor networks is maximizing target coverage while minimizing the amount of energy consumption. Considering the high redundancy in dense directional sensor networks, it is possible to preserve energy and enhance coverage quality by turning off redundant sensors and adjusting the direction of the active sensor nodes. In this paper, we address the problem of maximizing network lifetime with adjustable ranges (MNLAR) and propose a new game theory-based algorithm in which sensor nodes try to adjust their working direction and sensing range in a distributed manner to achieve the desired coverage. For this purpose, we formulate this problem as a multiplayer repeated game in which each sensor as a player tries to maximize its utility function which is designed to capture the tradeoff between target coverage and energy consumption. To achieve an efficient action profile, we present a distributed payoff-based learning algorithm. The performance of the proposed algorithm is evaluated via simulations and compared to some existing methods. The simulation results demonstrate the performance of the proposed algorithm and its superiority over previous approaches in terms of network lifetime.
[1] B. D. Deebak and F. Al-Turjman, "A hybrid secure routing and monitoring mechanism in IoT-based wireless sensor networks," Ad Hoc Networks, vol. 97, p. 102022, 2020.
[2] K. Evbarunegbe, "Coverage in Wireless Sensor Networks: A Survey," Texas A&M University-Kingsville, 2020.
[3] S. Harizan and P. Kuila, "Evolutionary algorithms for coverage and connectivity problems in wireless sensor networks: a study," in Design Frameworks for Wireless Networks: Springer, 2020, pp. 257-280.
[4] S. Rahili, J. Lu, W. Ren, and U. M. Al-Saggaf, "Distributed Coverage Control of Mobile Sensor Networks in Unknown Environment Using Game Theory: Algorithms and Experiments," IEEE Transactions on Mobile Computing, vol. 17, no. 6, pp. 1303-1313, 2018.
[5] J. R. Marden, H. P. Young, and L. Y. Pao, "Achieving pareto optimality through distributed learning," SIAM Journal on Control and Optimization, vol. 52, no. 5, pp. 2753-2770, 2014.
[6] T. AlSkaif, M. G. Zapata, and B. Bellalta, "Game theory for energy efficiency in wireless sensor networks: Latest trends," Journal of Network and Computer Applications, vol. 54, pp. 33-61, 2015.
[7] E. Golrasan, H. SHIRAZI, and K. Dadashtabar Ahmadi, "Sensing Radius Adjustment in Wireless Sensor Networks: A Game Theoretical Approach," INTERNATIONAL JOURNAL OF INFORMATION AND COMMUNICATION TECHNOLOGY RESEARCH, vol. 11, no. 4, pp. -, 2019.
[8] F. Hajjej, M. Hamdi, R. Ejbali, and M. Zaied, "A distributed coverage hole recovery approach based on reinforcement learning for Wireless Sensor Networks," Ad Hoc Networks, vol. 101, p. 102082, 2020.
[9] J. R. Marden and J. S. Shamma, "Game theory and control," Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, pp. 105-134, 2018.
[10] N. Mehendale, "Game Theory-Based Planning of Nodes in Wireless Sensor Networks for Optimum Coverage With Maximum Battery Life," Available at SSRN 3639170, 2020.
[11] H. Mostafaei, M. U. Chowdhury, and M. S. Obaidat, "Border surveillance with WSN systems in a distributed manner," IEEE Systems Journal, vol. 12, no. 4, pp. 3703-3712, 2018.
[12] N. Li and J. R. Marden, "Designing games for distributed optimization," IEEE Journal of Selected Topics in Signal Processing, vol. 7, no. 2, pp. 230-242, 2013.
[13] B. S. Pradelski and H. P. Young, "Learning efficient Nash equilibria in distributed systems," Games and Economic behavior, vol. 75, no. 2, pp. 882-897, 2012.
[14] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic game theory. Cambridge University Press, 2007.
[15] J. Habibi, H. Mahboubi, and A. G. Aghdam, "A gradient-based coverage optimization strategy for mobile sensor networks," IEEE Transactions on Control of Network Systems, vol. 4, no. 3, pp. 477-488, 2016.
[16] J. Ai and A. A. Abouzeid, "Coverage by directional sensors in randomly deployed wireless sensor networks," Journal of Combinatorial Optimization, vol. 11, no. 1, pp. 21-41, 2006.
[17] H. Mohamadi, S. Salleh, and M. N. Razali, "Heuristic methods to maximize network lifetime in directional sensor networks with adjustable sensing ranges," Journal of Network and Computer Applications, vol. 46, pp. 26-35, 2014.
[18] A. Alibeiki, H. Motameni, and H. Mohamadi, "A new genetic-based approach for maximizing network lifetime in directional sensor networks with adjustable sensing ranges," Pervasive and Mobile Computing, vol. 52, pp. 1-12, 2019.
[19] J. Yu, S. Wan, X. Cheng, and D. Yu, "Coverage contribution area based $ k $-coverage for wireless sensor networks," IEEE Transactions on Vehicular Technology, vol. 66, no. 9, pp. 8510-8523, 2017.
[20] J.-P. Sheu and H.-F. Lin, "Probabilistic coverage preserving protocol with energy efficiency in wireless sensor networks," in Wireless Communications and Networking Conference, 2007. WCNC 2007. IEEE, 2007, pp. 2631-2636: IEEE.
[21] C.-I. Weng, C.-Y. Chang, C.-Y. Hsiao, C.-T. Chang, and H. Chen, "On-supporting energy balanced $ k $-barrier coverage in wireless sensor networks," IEEE Access, vol. 6, pp. 13261-13274, 2018.
[22] L. Jing, W. Ruchuan, H. Huang, and S. Lijuan, "Voronoi-based coverage optimization for directional sensor networks," Wireless Sensor Network, vol. 1, no. 05, p. 417, 2009.
[23] T.-W. Sung and C.-S. Yang, "Distributed Voronoi-based self-redeployment for coverage enhancement in a mobile directional sensor network," International Journal of Distributed Sensor Networks, vol. 9, no. 11, p. 165498, 2013.
[24] J. R. Marden and J. S. Shamma, "Game Theory and Control," Annual Review of Control, Robotics, and Autonomous Systems, no. 0, 2017.
[25] S. Rahili, "Distributed Optimization in Multi-Agent Systems: Game Theory Based Sensor Coverage and Continuous-Time Convex Optimization," UC Riverside, 2016.
[26] M. Movassagh and H. S. Aghdasi, "Game theory based node scheduling as a distributed solution for coverage control in wireless sensor networks," Engineering Applications of Artificial Intelligence, vol. 65, pp. 137-146, 2017.
[27] M. Varposhti, P. Saleh, S. Afzal, and M. Dehghan, "Distributed area coverage in mobile directional sensor networks," in 2016 8th International Symposium on Telecommunications (IST), 2016, pp. 18-23: IEEE.
[28] M. Varposhti, V. Hakami, and M. Dehghan, "Distributed coverage in mobile sensor networks without location information," Autonomous Robots, vol. 44, no. 3, pp. 627-645, 2020.
[29] M. Hasanbeig and L. Pavel, "Distributed Coverage Control by Robot Networks in Unknown Environments Using a Modified EM Algorithm," World Academy of Science, Engineering and Technology, International Journal of Computer, Electrical, Automation, Control and Information Engineering, vol. 11, no. 7, pp. 721-729, 2017.
[30] R. Cerulli, R. De Donato, and A. Raiconi, "Exact and heuristic methods to maximize network lifetime in wireless sensor networks with adjustable sensing ranges," European Journal of Operational Research, vol. 220, no. 1, pp. 58-66, 2012.
[31] J. R. Marden, "Learning in large-scale games and cooperative control," CALIFORNIA UNIV BERKELEY DEPT OF MECHANICAL ENGINEERING2007.
[32] H. P. Young, Individual strategy and social structure: An evolutionary theory of institutions. Princeton University Press, 2001.
[33] D. P. Foster and H. P. Young, "Regret testing: learning to play Nash equilibrium without knowing you have an opponent," Theoretical Economics, vol. 1, no. 3, pp. 341-367, 2006.
[34] I. Ariel and Y. Babichenko, Average testing and the efficient boundary. Center for the study of Rationality, 2011.
[35] D. Fudenberg and E. Maskin, "The folk theorem in repeated games with discounting or with incomplete information," in A Long-Run Collaboration On Long-Run Games: World Scientific, 2009, pp. 209-230.
[36] H. P. Young, "Learning by trial and error," Games and economic behavior, vol. 65, no. 2, pp. 626-643, 2009.
[37] H. P. Young and B. S. Pradelski, "Learning Efficient Nash Equilibria in Distributed Systems," 2010.
[38] A. Menon and J. S. Baras, "Convergence guarantees for a decentralized algorithm achieving Pareto optimality," in 2013 American Control Conference, 2013, pp. 1932-1937: IEEE.