A Non-cooperative Game Algorithm for Task Scheduling in Wireless Sensor Networks
Keywords:
wireless sensor networks, task scheduling, divisible load theory, game algorithm, mechanism designAbstract
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
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
