传感器网络能源有效任务分配算法  

An Energy-Efficient Task Assignment Algorithm of Wireless Sensor Network

作　　者：李志刚[1] 周兴社[1] 李士宁[1] 马峻岩[1] 

机构地区：[1]西北工业大学计算机学院,西安710072

出　　处：《计算机研究与发展》2009年第12期1994-2002,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60573161);国家科技支撑计划基金项目(2007BAD79B0);陕西省自然科学基金项目(SJ08-2T06)~~

摘　　要：为了延长网络生命期,传感器网络在设计过程中,通常利用节点本身的处理能力,进行网内处理,以减少通信量,节省能量.在传感器网络内引入处理或计算后,应用可以描述为一个任务集及任务之间的数据依赖关系.不同的任务分配方案导致应用执行所需的通信量和计算量不同,从而影响应用执行的能量消耗.在使用任务图对传感器网络应用描述的基础上,提出了传感器网络任务分配模型.由于应用的任务可划分为感知任务集和处理任务集,因而传感器网络中的任务分配可分成感知任务分配和处理任务分配两个阶段.针对处理任务分配,将其建模为二次0-1规划问题,并提出了分布式逐层优化分配算法OALL.仿真实验验证了分布式算法OALL的有效性.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 （direeted aeyelic 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.

关 键 词：无线传感器网络 任务图 任务分配 二次0-1规划 分布式算法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]