Journal of Networks, Vol 6, No 11 (2011), 1586-1593, Nov 2011
doi:10.4304/jnw.6.11.1586-1593

A Task Scheduling Strategy in Heterogeneous Multi-sinks Wireless Sensor Networks

Liang Dai, Hongke Xu, Ting Chen

Abstract


Using multiple sinks in a wireless sensor network can significantly decrease the amount of energy spent on communication, so it has been paid much attention in recent years. In this paper, we introduce a new divisible load scheduling strategy to solve the problem how to complete the tasks within the possibly shortest time in multi-sinks wireless sensor network. In this strategy, the tasks are distributed to wireless sensor network based on the processing and communication capacity of each sensors by multiple sinks. After received the sub-tasks, the intra-cluster sensors perform its tasks simultaneously, and send its results to cluster head sequentially. By removing communications interference between each sensor, reduced makespan and improved network resource utilization achieved. Cluster heads send fused data to sinks sequentially after fused the data got from intra-cluster sensors, which could overlap the task-performing and communication phase much better. A unique scheduling strategy that allows one to obtain closed form solutions for the optimal finish time and load allocation for each node in heterogeneous clustered networks is presented. And solutions for an optimal allocation of fractions of task to sensors in the network are also obtained via bi-level programming. Finally, simulation results indicate this strategy reasonably distributes tasks to each node in multi-sinks wireless sensor networks, and effectively reduces the time-consuming of task completion. Compared to the traditional single-sink structure, makespan is reduced by 20%, and the energy-consuming of sensors is more balanced.


Keywords


wireless sensor networks; heterogeneous; divisible load theory; task scheduling; multiple sinks

References


[1] V. Shah-mansouri, A. Mohsenian-rad,“Lexicographically Optimal Routing for Wireless Sensor Networks With Multiple Sinks,” IEEE Transactions on Vehicular Technology, 2009, 58(3): 1490 – 1500.
http://dx.doi.org/10.1109/TVT.2008.928898

[2] K. Yuen, L. Ben, B. C. Li, “A Distributed Framework for Correlated Data Gathering in Sensor Networks,” IEEE Transactions on Vehicular Technology, 2008, 57(1) :578 – 593.
http://dx.doi.org/10.1109/TVT.2007.905243

[3] V. Bharadwaj, D. Ghose, T. G. Robertazzi, “Divisible load theory: A new paradigm for load scheduling in distributed systems,” Cluster Computing, 2003, 6(1), pp.7-18.
http://dx.doi.org/10.1023/A:1020958815308

[4] M. Moges, T. G. Robertazzi, “Wireless sensor networks: scheduling for measurement and data reporting,” IEEE Transactions on Aerospace and Electronic Systems, 2006, 42(1), 327-340.
http://dx.doi.org/10.1109/TAES.2006.1603426

[5] H. Liu, X. Yuan, M. Moges, “An Efficient Task Scheduling Method for Improved Network Delay in Distributed Sensor Networks,” In Proceedings of TridentCom, 2007, (pp.1-8). Orlando, FL, US: IEEE.

[6] H. Liu, J. Shen, X. Yuan, M. Moges, “Performance Analysis of Data Aggregation in Wireless Sensor Mesh Networks,” In Proceedings of Earth & Space 2008, (pp.1-8), Akron, OH, USA: IEEE.

[7] C. Kijeung, T. G. Robertazzi, “Divisible Load Scheduling in Wireless Sensor Networks with Information Utility Performance,” In Proceedings of IPCCC, 2008, (pp.9-17), Austin, Texas, USA: IEEE.

[8] Z. Zeng, A. Liu, D. Li, “A Highly Efficient DAG Task Scheduling Algorithm for Wireless Sensor Networks,” In Proceedings of ICYCS, 2008, (pp.570–575). Zhang Jia Jie, Hunan, China: IEEE.

[9] J. Lin, W. Xiao, F. L. Lewis, et al, “Energy-Efficient Distributed Adaptive Multisensor Scheduling for Target Tracking in Wireless Sensor Networks,” IEEE Transactions on Instrumentation and Measurement, 2009, 58(6), pp.1886 – 1896.
http://dx.doi.org/10.1109/TIM.2008.2005822

[10] W. Heinzelman, A. Chandrakasan, “An application-specifid protocol architecture for wireless microsensor networks,” IEEE Transaction on Wireless Communications, 2002, 1(4), pp. 660-670.
http://dx.doi.org/10.1109/TWC.2002.804190

[11] C. Kijeung, T. G. Robertazzi, “Divisible Load Scheduling in Clustered Wireless Sensor Networks,” Stony brook university, 2009.

[12] X. Li, H. Kang and J. Cao, ”Coordinated Workload Scheduling in Hierarchical Sensor Networks for Data Fusion Applications,” Journal of Computer Science and Technology, vol. 23, 2008, pp. 355-364.
http://dx.doi.org/10.1007/s11390-008-9138-7

[13] X. Li, X. Liu and H. Kang, ”Sensing Workload Scheduling in Sensor Networks Using Divisible Load Theory,” The 50th Annual IEEE Global Telecommunications Conference, Washington DC, 2007, pp. 785-789.

[14] X. Tang, J. Xu, “Optimizing Lifetime for Continuous Data Aggregation With Precision Guarantees in Wireless Sensor Networks,” IEEE/ACM Transactions on Networking, 2008, 16(4), pp. 904 – 917.
http://dx.doi.org/10.1109/TNET.2007.902699


Full Text: PDF


Journal of Networks (JNW, ISSN 1796-2056)

Copyright @ 2006-2012 by ACADEMY PUBLISHER – All rights reserved.