Journal of Computer Research and Development (计算机研究与发展) 2009/2009:12 PP.1994-2002

An Energy-Efficient Task Assignment Algorithm of Wireless Sensor Network

In-network processing methods are often adopted in wireless sensor network (WSN) to reduce data communication and prolong the lifetime of network, which enables a WSN application to be described as a set of tasks (sensing, processing) and dependencies among them. Task assignment has become an important problem which needs to be resolved, as different task assignments can cause different communication traffics, and then cause different energy consumption when performing the application. Based on the task graph of WSN described by DAG (directed acyclic graph), an energy-efficient task assignment framework is proposed. As an application can be decomposed into sensing tasks and processing tasks, the task assignment is presented as a process of sensing task assignment and processing task assignment. Sensing task assignment involves sensor selection in WSN and some work has been done for this problem. In this paper, the authors consider the problem of how to assign the processing tasks after the selection of sensors to make the application performed using minimum energy. The processing task assignment is formulated as a quadratic 0-1 programming problem, and a distributed OALL algorithm (optimizing assignment layer by layer) is proposed. With demonstrative example, the proposed algorithm has been evaluated, and the results of experiment has proved its effectiveness.

Key words:WSN,task graph,task assignment,quadratic 0-1 programming,distributed algorithm

ReleaseDate:2014-07-21 15:00:24

[1] Cui Li, Ju Hailing, et al. Overview of wireless sensor network [J]. Journal of Computer Research and Development, 2005, 42(1): 163-174 (in Chinese)(崔莉, 鞠海玲, 等. 无线传感器网络研究进展 [J]. 计算机研究与发展, 2005, 42(1): 163-171)

[2] Estrin D, Govindan R. Next century challenges: Scalable coordination in sensor networks [C]//Proc of MobiCom 1999. New York: ACM, 1999: 263-270

[3] Sohrabi K, Cao J, Ailawadhi V, et al. Protocols for self-organization of a wireless sensor network [J]. IEEE Personal Communications Magazine, 2000, 7(5): 16-27

[4] Park H, Srivastava M. Energy-efficient task assignment framework for wireless sensor network, TR-UCLA-NESL-200309-03[R]. Los Angeles: Center for Embedded Network Sensing, 2003

[5] Jie Wu. Distributed System Design [M]. Boca Raton, Florida, USA: CRC-Press, 1998

[6] Xiong N, Svensson P. Multi-sensor management for information fusion: issues and approaches [J]. Information Fusion, 2002, 3(2): 163-186

[7] Byers J, Nasser G. Utility-based decision-making in wireless sensor network [C]//Proc of MobiHoc 2000. New York: ACM, 2000: 143-144

[8] Tian D, Georganas N. A node scheduling scheme for energy conservation in large wireless sensor network [J]. Journal of Wireless Communications and Mobile Computing, 2003, 3(2): 271-290

[9] Wang Hanbiao, Pottie G, Kung Y, et al. Entropy-based sensor selection heuristic for target localization [C]//Proc of IPSN. New York: ACM, 2004: 36-45

[10] Molnar P, Lockett E, Kaplan L. Self-organized task assignment for distributed sensors [C]//SPIE 4196: Conf on Sensor Fusion and Decentralized Control in Robotic Systems. Bellingham, WA: SPIE, 2003: 189-196

[11] Guestrin C, Bodik P, Thibaux R, et al. Distributed regression: An efficient framework for modeling sensor network data [C]//Proc of IPSN. New York: ACM, 2004: 1-10

[12] Rabbat M, Nowak R. Distributed optimization in sensor networks [C]//Proc of IPSN. New York: ACM, 2004: 2027

[13] Yu Y, Prasanna V. Energy-balanced task allocation for collaborative processing in wireless sensor network [J]. Journal of Mobile Networks and Applications, 2005, 10(1): 115-131

[14] Zhu Jinghua, Gao Hong. An energy efficient algorithm for task allocation in wireless sensor network [J]. Journal of Software, 2007, 18(5): 1198-1207 (in Chinese)(朱敬华, 高宏. 无线传感器网络中能源高效的任务分配算法 [J]. 软件学报, 2007, 18(5): 1198-1207)

[15] Bakshi A, Prasanna V, et al. The abstract task graph: A methodology for architecture-independent programming of networked sensor systems [C]//Proc of Workshop EESR. New York: ACM, 2005: 19-24

[16] Cormen T, Leiserson C, et al. Introduction to Algorithms [M]. Cambridge: The MIT Press, 2001