A Non-cooperative Game Algorithm for Task Scheduling in Wireless Sensor Networks

Authors

  • Liang Dai School of Electronic and Control Engineering Chang’an University Xi’an 710064, China
  • Yilin Chang State Key Laboratory of Integrated Service Networks Xidian University Xi’an 710071, China
  • Zhong Shen State Key Laboratory of Integrated Service Networks Xidian University Xi’an 710071, China

Keywords:

wireless sensor networks, task scheduling, divisible load theory, game algorithm, mechanism design

Abstract

Scheduling tasks in wireless sensor networks is one of the most challenging problems. Sensing tasks should be allocated and processed among sensors in minimum times, so that users can draw prompt and effective conclusions through analyzing sensed data. Furthermore, finishing sensing task faster will benefit energy saving, which is critical in system design of wireless sensor networks. But sensors may refuse to take pains to carry out the tasks due to the limited energy. To solve the potentially selfish problem of the sensors, a non-cooperative game algorithm (NGTSA) for task scheduling in wireless sensor networks is proposed. In the proposed algorithm, according to the divisible load theory, the tasks are distributed reasonably to every node from SINK based on the processing capability and communication capability. By removing the performance degradation caused by communications interference and idle, the reduced task completion time and the improved network resource utilization are achieved. Strategyproof mechanism which provide incentives to the sensors to obey the prescribed algorithms, and to truthfully report their parameters, leading to an effient task scheduling and execution. A utility function related with the total task completion time and tasks allocating scheme is designed. The Nash equilibrium of the game algorithm is proved. The simulation results show that with the mechanism in the algorithm, selfish nodes can be forced to report their true processing capability and endeavor to participate in the measurement, thereby the total time for accomplishing the task is minimized and the energy-consuming of the nodes is balanced.

References

C. Pandana, H. Zhu, L. Ray, Cooperation Enforcement and Learning for Optimizing Packet Forwarding in Autonomous Wireless Networks. IEEE Transactions on Wireless Communications, vol.7, No.8, pp.3150-3163, 2008. http://dx.doi.org/10.1109/TWC.2008.070213

V. Bharadwaj, D. Ghose, T. G.ROBERTAZZI, Divisible Load Theory: A New Paradigm for Load Scheduling in Distributed Systems. Cluster Computing, vol.6, No.1, pp.7-18, 2003. http://dx.doi.org/10.1023/A:1020958815308

M. Moges, T.G. Robertazzi, Wireless Sensor Networks: Scheduling for Measurement and Data Reporting. IEEE Transactions on Aerospace and Electronic Systems, vol.42, No.1, pp.327- 340, 2006. http://dx.doi.org/10.1109/TAES.2006.1603426

H. LIU, X. YUAN, M. Moges, An Efficient Task Scheduling Method for Improved Network Delay in Distributed Sensor Networks. In Proceedings of TridentCom 2007, Orlando, FL, USA, 1-8, 2007.

H. LIU, J. SHEN, X. YUAN, M. Moges, Performance Analysis of Data Aggregation in Wireless Sensor Mesh Networks, In Proceedings of Earth & Space 2008, Akron, OH, USA, 1-8, 2008.

C. Kijeung, T. G. Robertazzi, Divisible Load Scheduling in Wireless Sensor Networks with Information Utility Performance. In Proceedings of IPCCC 2008, Austin, Texas, USA, 9-17, 2008.

Z. ZENG, A. LIU, D. LI, A Highly Efficient DAG Task Scheduling Algorithm for Wireless Sensor Networks, In Proceedings of ICYCS 2008,Zhang Jia Jie, Hunan, China, 570-575, 2008.

J. LIN, W. XIAO, F. L. Lewis, Energy-Efficient Distributed Adaptive Multisensor Scheduling for Target Tracking in Wireless Sensor Networks. IEEE Transactions on Instrumentation and Measurement, vol.58, No.6, pp.1886 - 1896, 2009. http://dx.doi.org/10.1109/TIM.2008.2005822

P. Guo, T. Jiang, K. Zhang, H. Chen, Clustering algorithm in initialization of multi-hop wireless sensor networks. IEEE Transactions on Wireless Communications, vol.8, No.12, pp. 5713-5717, 2009. http://dx.doi.org/10.1109/TWC.2009.12.080042

N. Nisan, A. Ronen. Algorithmic mechanism design, Games and Economic Behavior, vol.35, nos.1-2, pp.166 -196, 2001. http://dx.doi.org/10.1006/game.1999.0790

W. Heinzelman, A. Chandrakasan, An Application-specifid Protocol Architecture for Wireless Microsensor Networks. IEEE Transaction on Wireless Communications, vol.1, No.4, pp. 660-670, 2002. http://dx.doi.org/10.1109/TWC.2002.804190

Published

2011-12-01

Most read articles by the same author(s)

Obs.: This plugin requires at least one statistics/report plugin to be enabled. If your statistics plugins provide more than one metric then please also select a main metric on the admin's site settings page and/or on the journal manager's settings pages.