无线传感器网络协同任务分配研究

　　摘要：无线传感器网络的任务协同主要是任务的描述、分解、分配、调度和执行。任务分配是任务协同的主要内容，任务分配的方案直接决定着网络能耗，从而影响网络的生命周期。着重分析了无线传感器网络协同技术以及启发式算法解决任务分配的问题，并给出了无线传感器网络任务分配需要进一步研究的内容和方向。

　　0 引言

　　微机电系统（Microelectromechanical Systems,MEMS）、微处理器以及Ad-hoc网络协议的迅猛发展孕育出了无线传感器网络，无线传感器网络是由大量廉价且资源有限的传感器节点组成。由于每个传感器节点资源有限以及计算和通信能力有限，单个节点无法解决网络规模庞杂的问题，更无法解决网络全局性问题。基于以上原因，WSNs中的传感器节点要相互协同以完成任务。

　　WSNs协同主要包括协同资源的使用，协同任务的分配和执行以及协同信息与信号的处理.任务协同中的主要部分是任务分配，因为任务分配方案直接决定着网络能耗，从而决定了网络的整体寿命。因此，WSNs协同任务分配具有重要的理论和现实意义。

　　1 无线传感器网络任务分配协同技术

　　由于WSNs 具有采用射频通信、能量有限、计算和通信能力较弱以及大规模高密度部署等特点，所以传统分布式系统的协同方法并不能直接应用于WSNs,目前WSNs 协同技术是来自分布式人工智能领域的多智能体理论。基于多智能体的WSNs协同技术有基于协商的方法、基于动态联盟的方法、分布式约束满足法和组织结构设计方法四种。

　　1.1 基于协商的方法

　　基于协商的方法是以多智能体中的协商理论为模型，将协商模型与拍卖方法和合同网相结合而形成，目前用于解决WSNs协同问题的主要是组合拍卖（Combi-natorial Auction）和动态仲裁（Dynamic Arbitration）两种方法[2].组合拍卖和动态仲裁采取的都是集中式的任务分配方法，即存在一个中心节点，该中心节点要和周围节点进行协商终完成对任务的分配过程；组合拍卖对任务的组合由周围节点完成，而动态仲裁任务的组合和分配都是由中心节点完成。相对来说，后者更容易在网络中形成能量空洞。

　　采用基于协商的方法解决任务分配，在CNP（Contract Net Protocol）中引入了推理模型和能量阈值，实现了高效节能的任务分配，减少了网络中的能量空洞，从而延长了网络的寿命。

　　1.2 基于动态联盟的方法

　　动态联盟是基于事件触发的，当节点捕获到事件时会形成一个联盟，并且由该联盟负责任务的处理；当联盟完成任务后，联盟也将随之而解散。其过程主要包括动态联盟初始化、联盟形成和联盟确认三个阶段。在当前的无线传感器网络协同任务分配机制中，动态联盟机制占据了重要的地位；由于其是基于事件触发的，能够针对任务情况动态地协同任务的分配。

　　针对目标跟踪问题，提出了基于拍卖的动态联盟任务分配机制，和基于推理的动态联盟机制相比提高了目标跟踪的准确性并且降低了能耗；基于动态联盟提出了EATA（Effective Adaptive Task Allo-cation），每个节点通过EATA可以自主调整自身参数和状态，实现了资源利用化并延长了网络寿命。

　　1.3 分布式约束满足法

　　分布式满足方法采用的是一种映射的思想，其将传感器节点、传感器节点行为模式以及传感器节点间的关系分别映射为变量、变量的取值以及变量间的约束关系，从而将WSNs中的协同问题转化为分布式约束满足问题进行解决。分布式约束满足法将任务分配问题映射成DCSP问题，采用DCSP方法解决问题，终形成任务分配的方案，Pragnesh J.M 等人给出将传感器网络中追踪问题转化为DCSP问题的方法。

　　1.4 组织结构设计方法

　　组织结构设计方法是根据无线传感器网络大规模部署特点提出的，其包括简单分层和垂直分层。该方法将整个网络划分为不同的区域，通过指派区域管理员负责区域内以及区域间的通信，但是该方法需要事先指定每个传感器节点的角色.由于组织结构设计方法是针对无线传感器大规模特点提出的，所以能够很好地解决大规模无线传感器网络中目标跟踪问题，通常用于区域监视。

　　以上技术都有其应用场景及优缺点。对于小规模网络问题，协商方法和动态联盟方法比较适合，但是对于大规模网络问题则会面临组合爆炸的难题。然而，对于大规模网络问题，组织结构设计方法能够很好的解决，但是，由于节点的通信范围受到了限制，组织结构设计方法会面临边界的问题。由于将无线传感器网络任务分配问题映射成DCSP 问题是个复杂、低效的过程，分布式约束满足法在传感器网络任务分配方面还不成熟。三种协同技术的性能比较见表1.

　　

　　2 启发式算法解决任务分配

　　由于任务分配是一个NP的组合优化问题，目前已经有许多启发式算法来解决该问题。常用启发式算法有遗传算法、粒子群优化等。对于任务分配问题，启发式算法并不是单纯利用某个启发式算法解决问题，其通常与协同技术相结合。

　　采用遗传算法对联盟中的任务进行分配，其优化了遗传算法初始种群的选择和交叉/变异运算并且引入了Metropolis准则，改善了任务分配效率的同时降低了通信开销。文献[8]针对现有任务分配算法无法解决容错问题，其引入了PB（Primary/Backup）机制，采用PSO（Particle Swarm Optimization）进行任务分配，提高了无线传感器网络任务分配的可靠性。引入动态联盟模型，以任务执行时间和能量消耗构建适应度函数，采用改善的粒子群优化算法进行任务优化，降低了网络能耗且缩短了任务的执行时间。

　　WSN任务分配旨在资源和效率以及全局搜索和局部求解之间寻求平衡。为了降低网络能耗，延长网络的寿命，启发式算法适应度函数选取及优化相当重要；由于任务分配是全局寻优问题，一些启发式算法容易陷入局部，所以启发式算法引入了一些算子或者对算法本身已有的算子进行修正。

　　在遗传算法中引入了混杂的适应度函数来进行任务分配，延长了网络的整体寿命。引入动态联盟思想，构造了无线传感器网络的动态联盟模型，提出了一种基于离散粒子群优化的任务分配算法，引入了变异算子，在保持种群多样性的同时提高了算法的全局搜索能力，该算法在局部求解和全局寻优之间取得了较好的平衡并且降低了任务分配的时间和网络的能耗。

　　遗传算法和粒子群优化算法均可用于无线传感器网络任务分配的问题，一般前者可直接应用，而当适应度函数是离散时，后者需重新定义速度及位置更新公式等。由于无线传感器网络本身资源有限性的特点，二者在构造适应度函数时必须考虑无线传感器网络资源；对于有实时性需求的问题，还需考虑任务分配的执行时间，此时建议采用粒子群优化算法进行任务分配。二者优缺点比较见表2.

　　

　　3 结语

　　由于无线传感器网络本身所具有的节点资源有限性、动态拓扑性、数据传输不可靠性等特点，需要从节能性、实时性和可靠性等方面对无线传感器网络的任务分配进行改善。现有研究者主要从节能性的角度对无线传感器网络任务分配和调度进行相应的研究，从而限度地延长整个网络的寿命。但是任务分配的实时性和可靠性以及能源高效性方面的研究比较少，因此，这一部分还需要进一步地研究。（作者：王建，王福豹，段渭军，黄亮）