电子人社区网讯：
摘 要：针对无线传感器执行器网络( WSAN) 中的执行器任务分配问题，提出一种基于改进分布式竞拍的任务分配算法。 该算法通过计算完成每个任务的效用以及执行器完成任务的代价 ，得出任务分配方案。算法改进了竞拍过程中响应树 的构造方式，并在执行器效用值的计算过程中引入了匹配度的概念，以此来适应动态变化的网络环境。仿真结果表明， 本方法均衡了网络能耗、减少了数据包的转发数量和任务完成时间。
关键字：无线传感器执行器网络 任务分配 竞拍算法 执行器协作
0 引言
无线传感器执行器网络(WirelessSensorandAc-tuatorNetwork，WSAN)作为自动检测和控制的先进技术，目前已在火灾检测和控制、灾难管理、城市搜索与营救、国土安全、战场监控等领域有广泛应用。该网络由大量静止的传感器节点和少量移动的执行器节点组成，它们通过无线网络互联，用于感知现实世界，处理感知数据，并在事件发生时进行决策和行动。Akyildiz指出，协作性和实时性是WSAN应该满足的2个独特要求，其中执行器和执行器之间协作(ActuatortoActuatorCoordination，AAC)的主要目的是完成任务的有效分配。执行器节点负责处理感知信息并执行当前的任务，因此当WSAN中有任务发生时，选择合适的执行器节点可以减少通信能耗，提高响应速度，对保证网络实时性和能量均衡性，延长网络寿命有重要的意义。
针对WSAN中的任务分配问题，已有的方案主要分为集中式和分布式算法。集中式算法是指由一个中心节点收集所有节点的信息然后进行决策。
其中将任务分配问题等效为整数线性规划问题，并将任务集用树的方法遍历，找到时限条件下能耗最小的任务分配方案。将任务类型，执行器节点距离事件发生的距离、剩余能量作为模糊判断的输入量，利用模糊算法得到任务的分配方案。根据执行器节点的剩余能量和工作状态，利用混合模拟退火的微粒群算法统一安排各个任务。这些方案的优点是可以选出最优的执行器节点，但这类方法计算量大、通信负担重、时延长。
分布式解决方案大都采用竞拍方式利用局部节点信息来进行决策。将任务执行时间不同的任务等效为背包问题，然后利用竞拍算法来实现任务的分配。首先使用iMesh算法交叉查找附近的执行器，然后利用本地化竞拍聚合协议找出最接近的执行器对事件执行相应措施。利用执行器节点重新部署算法将执行器节点部署到其执行区域中间，然后利用密封第一价的拍卖算法对任务进行拍卖和求解。在拍卖过程中引入焦虑度对分配后的任务进行动态调整，以适应动态变化的环境。以上方法可以在时间限制内给出合理的任务分配方案，但大都通过设定固定跳步数来限制竞拍节点的数量，这样会使数据包转发的数量增多。在任务分配过程中，“实时性”并非越快越好，而是在规定的时间内给出一个“较好”的接近最优的分配方案。针对这个要求，本文提出的改进分布式竞拍算法(Im-provedDistributedAuctionAlgorithm，IDAA)，改进了竞拍过程中响应树的构造方式，以此减少数据包的转发数量，并在竞拍节点效用值的计算过程中引入适应度的概念，以此均衡网络能耗，最后通过仿真实验验证本算法的有效性。
1 基于竞拍的任务分配
1.1 竞拍算法模型
本文竞拍算法模型的描述如下：
其中T为需要完成的任务集合，T={t1，…，tn}，每个任务tj都有自己的持续时间du和截止时间dj;A为执行器节点的集合，A={a1，a2，…，an}，执行器节点ai有Ni可用时隙，即每次最多完成Ni个任务;B为参与竞标的节点集合，B={b1，b2，…，bn};U为完成任务时的效用值的集合，U={u1，u2，…，un};C为执行器完成任务时的代价集合，C={c1，c2，…，cj，…，cnt}，表示执行器节点a完成任务tj时的代价值;H为历史任务分配信息，H={hi}用于查询历史任务分配信息，描述拍卖成功后的任务所属关系。本文研究的是单任务分配，即每个任务只能由一个执行器节点执行：hj∈{0，1}，为1时，表示任务t由执行器节点ai执行，反之亦然。为保证完成任务的实时性要满足以下约束条件：
公式(1)保证每个任务最多由一个执行器节点执行。公式(2)保证执行器队列中的每个任务都能在任务截止时间内完成。
1.2 基本竞拍算法框架
由算法模型可知，在拍卖过程中有拍卖执行器和竞拍执行器2类节点。竞拍算法框图如图1所示，执行器节点检测环境中是否有任务发生，首先检测到任务发生的执行器为此任务的代理节点(即拍卖节点)，对此任务发生的地点、执行当前任务所需的能量等进行评估，传统竞拍算法采用生成响应树的方式将任务消息逐级传递，直到传递给k跳邻居执行器节点。为保证整个网络的实时性，设定了拍卖的截止时间，拍卖执行器在截止时间内对收到的投标信息进行分析处理，从而得到任务的分配方案。若拍卖成功，通知胜利者完成任务，拍卖失败，则重新对当前任务进行拍卖。
竞拍执行器收到任务消息后，根据自身状态评估接收到的任务，计算接收任务的效用值和代价值，并由此得到投标价格。
投标价格的定义如下：
![]() （4）
其中，CiTj表示执行器ai完成任务tj时的代价，Uij表示执tj系统的效用值，γ为比例系数。
竞拍执行器从当前任务队列中选取参与竞拍的任务，并向该拍卖执行器节点发送竞标消息，任务选择时满足式(4)，称此次拍卖为一个完美任务分配。若竞拍成功，则该执行器节点完成当前任务。
图1 竞拍算法框架图
2> IDAA改进了响应树的生成方式，通过控制k值来减少数据包的转发，降低网络开销，竞拍节点在效用值计算过程中引入匹配度［12］，以此来均衡网络能耗，延长网络寿命。
2.1 改进响应树的拍卖执行器算法
在响应树生成阶段，拍卖执行器节点要将任务消息转发给所有k跳邻居节点，这种转发有时候是不必要的。比如，计算后得出最佳执行器出现在一跳范围内，则向一跳范围外的其他执行器转发是没有必要的。因此本文在响应树的构造过程中采用令k值由小到大逐步增加的方式来限制参与竞拍的执行器的个数。具体实施过程为：代理任务的拍卖执行器首先判断1跳内的邻居节点(包含其自身)是否有合适的执行器节点出现，若有则不再向下一跳范围的邻居节点转发任务消息;若没有则继续向下一跳节点转发，直到在拍卖截止时间内找到合适的执行器节点为止。
改进响应树的拍卖执行器算法如下：
2.2 引入匹配度的竞拍执行器算法
执行器节点是自利的，即希望自身获得最大的效用，因此当拍卖系统中存在多个拍卖任务时，系统效用值往往达不到最大。而系统的效用值与网络寿命息息相关，在信息量不完全、决策时间受限的分布式竞拍系统中，为使系统的效用值达到最大，本文在效用值计算过程中引入匹配度的概念，匹配度是指完成一件任务时的适合程度。本文中的匹配度是指对当前执行器完成任务期望的能量消耗和实际能量消耗进行评估产生的匹配程度的量化值。
本文执行器节点ai完成任务tj的效用值Uij定义如下：
![]() （5)
其中，vj表示完成任务tj时所需的效用值，sij为执行器节点ai完成任务tj时的匹配度值，ci为ai的理想能量消耗值，j为移动单位长度距离的能量消耗值。
从公式(5)中可以看出匹配度的值与执行器节点ai完成任务的理想能量消耗和实际能量消耗有关。当理想消耗和实际消耗相同时匹配度值为1时，达到最大，当理想消耗和实际消耗不同时匹配度值下降。
竞拍执行器算法如下：
3 仿真分析
本文采用Matlab进行仿真分析。在完成相同任务的情况下，将传统竞拍算法SAAP和本文改进的分布式竞拍算法IDAA在各执行器节点剩余能量的均衡性、任务完成时间、任务分配率以及数据包的转发个数这4个方面进行性能的对比。
实验的仿真场景为：10个执行器节点随机分布在500m×500m的正方形监测区域内，每次实验由100个传感器节点随机产生20个任务，执行器节点对任务进行拍卖和竞拍，从而得出任务的分配方案。
为验证算法的有效性，分别利用传统竞拍算法和本文提出的改进分布式竞拍算法完成200次任务分配实验。其中实验参数的设置如表1所示。
表1 仿真实验参数
图2 任务分配时间对比图
图2所示为2种算法的任务完成时间箱线对比图，从图中可以看出本文提出的IDAA任务分配时间大都集中在280～320之间，而SAAP的大都集中在350～400之间。结果表明本算法相比于传统竞拍算法缩短了任务的分配时间。
图3所示为任务分配率对比图，从图中可以看出IDAA及SAAP在跳步数不同时的任务分配率;由图中数据可得IDAA的任务分配率和SAAP协议在k=5时任务分配率相当，接近于1，说明改进的算法IDAA不影响任务的分配率。
图3 任务分配率对比图
图4所示为IDAA和SAAP数据包转发个数的对比图，综合图3和图4可以看出在k＜3时，IDAA较SAAP可转发更多的数据包，但此时SAAP的任务分配率也较低;当k≥4时IDAAP会转发更少的数据包，当k=5时，任务分配率几乎相同，且数据包的转发量减少。由此得出结论，IDAA在保证任务分配率的条件下会转发更少的数据包，达到了响应树构造阶段改进的目的。
图4 数据包转发个数对比图
设第k次试验中执行器节点ai的剩余能量为rekik，则每轮试验的剩余能量方差计算公式如下：
![]() （6）
图5所示为2种算法的执行器节点剩余能量方差对比图，从图5可以看出和传统竞拍算法SAAP相比，IDAA的剩余能量方差明显减小，经计算，IDAA的200次试验平均剩余能量方差相比于SAAP降低了49%。说明各个执行器节点之间的剩余能量更加均衡，个别执行器节点提前死亡的概率降低，系统的鲁棒性增强。
图5 执行器节点剩余能量的方差对比图
4 结束语
针对WSAN中执行器的任务分配问题，提出了一种改进分布式竞拍算法，改进了竞拍过程中响应树的构造方式，并在执行器效用值的计算过程中引入了匹配度的概念，在规定时间内完成了执行器节点的任务分配。仿真结果表明：此算法均衡了各个执行器节点的剩余能量，提高了系统的鲁棒性;在保证任务分配率高的情况下大大减小了数据包的转发数量，降低了拍卖算法的通信要求，提高了执行器分配的实时性和灵活性。
在后续研究中，笔者将尝试引入其他智能算法到本文算法的研究中，以增加算法的预测能力，从而优化任务的分配方案。
来源：调节阀信息网
转载请注明：电子人社区 | 
发表于 2018-2-12 21:32:11
收藏
分享
赞同
反对
