【作者】 郭文忠；

【导师】 余轮； 陈国龙；

【作者基本信息】 福州大学 ， 通信与信息系统， 2010， 博士

【摘要】 传感器节点互相合作共同完成指定任务是在资源受限的无线传感器网络中获得较高性能的有效途径之一。在无线传感器网络中，任务的执行与资源的使用紧密联系在一起，执行任务要消耗一定的计算和通信带宽等资源，但由于网络资源十分有限，往往需要尽可能高效地利用有限的资源以使任务得以顺利执行，即在能量受限、动态多变的网络环境中，要求有效分配网络内的任务，将特定的任务调度到最合适的节点上执行，并在保证网络负载均衡的同时实现对资源的有效分配，这就迫切要求在无线传感器网络领域开展有关于无线传感器网络任务调度的研究。虽然对于传统网络环境下任务调度算法的研究已经非常的成熟，但在无线传感器网络中的研究还有很大空间。受无线传感器网络本身所具有的动态拓扑性、能耗有限性、节点资源有限性以及数据传感的不可靠性等特点影响，现有算法不能直接应用于无线传感器网络中，从而在无线传感器网络中开展任务调度问题研究是非常迫切和关键的。围绕这一中心问题，本文从多方面展开了综合研究，并作了一些有益的尝试，主要有以下四个方面：(1)为了延长网络生命周期，减少网络能量消耗和均衡网络负载，引入了动态联盟思想，构造了无线传感器网络任务分配的动态联盟模型，继而提出了一种基于离散粒子群优化的任务分配算法。该算法根据任务总完成时间、能量损耗以及网络负载状况，建立代价函数，结合粒子群优化算法，实现优化任务分配策略。引入了变异算子，在很好地保持了种群多样性的同时提高了算法的全局搜索能力。仿真实验结果表明了该分配算法在局部求解与全局探索之间取得了较好的平衡，能有效减少无线传感器网络的计算时间和网络能耗，并有效地均衡网络负载。(2)无线传感器网络所具有的动态拓扑性特点要求要有一种更加优化和高效的拓扑控制机制，使拓扑结构能够根据节点的状况自我调整和自我配置，以保证在部分传感器节点损坏、失效和移动的情况下，不会影响到数据传输和全局任务。为此，本文针对传统方案所获拓扑的连通冗余度过高或结构健壮性较低等弊端，采纳了本地生成树结构的拓扑调整思路，对拓扑需求进行了建模分析并转化为多目标度约束最小生成树问题，继而设计了一个基于目标共享函数的适应度评价函数，给出了求解该问题的新型离散粒子群优化算法，基于种群的随机状态转移过程，理论分析了算法的全局收敛性，最后构建一种基于新型离散粒子群优化的拓扑控制方案，仿真实验结果表明了所提方案所获拓扑具有网络整体功耗低，结构健壮性高和节点间通信干扰可控的折衷特点，并能够有效地延长无线传感器网络的生命周期。(3)无线传感器网络所具有的能耗有限性和节点资源有限性要求在任务调度过程中进行实时数据交换时要尽量减少传感器节点的功耗，而数据融合能有效减少网络内的数据传输量，减少能源的消耗，并尽可能地挖掘传感器节点的处理能力。为此，本文综合运用前向反馈神经网络和粒子群优化算法，建立了一个面向无线传感器网络的多源时域数据融合模型。新模型首先构造了基于粒子群优化的特征选择算法用以简化大量的历史数据源，然后提出了一种基于粒子群优化的新型神经网络预测算法，利用粒子群优化训练前向反馈神经网络，获得全局优化的神经网络权值和阈值，最后依赖于过滤的数据，通过所提预测算法进行数值预测，达到节省能耗的目的，并克服了传统时序算法所无法实现的根据多种不同类型数据进行预测的缺点。(4)无线传感器网络自身的网络状况和所处的外界环境动态多变性等特点要求采取自适应机制使任务管理更加适应于无线传感器网络的实时应用需求。为此，本文引入多Agent系统理论，构建了一种基于多Agent的无线传感器网络系统模型，并在该系统模型基础上，提出了一种基于多Agent的无线传感器网络自适应任务调度策略。该策略有效地将多Agent技术融入到了无线传感器网络的自适应任务调度当中，能够对故障结点上未完成的任务及时地进行自适应调整，以达到用最小的开销恢复网络的正常运作。更多还原

【Abstract】 Collaboration among sensors emerges as a promising solution to achieve highprocessing power in resource-restricted wireless sensor networks (WSNs).Usually in aWSN, the resource usage is highly realated to the execution of tasks, which consumea certain amount of computing resource and communication bandwidth. Since theresources in a specific network are limited, they must be efficiently used to smooththe execution of tasks. Therefore, how to assign a task to its own most appropriatesensor node and simultaneously balance the network load in the context of theuncertain and dynamic network environments becomes an important and urgent issuein WSNsAlthough task scheduling algorithms in traditional network enviroment have beenwell studied in the past, their application to WSNs remains largely unexplored. Due tothe limitations of WSNs, such as dynamic network topology, limited energy, limitedsensor node resources and unreliable sensing data, existing algorithms cannot bedirectly implemented in WSNs and task scheduling problem in WSNs is very urgentand pivotal. Therefore, this thesis endeavors to do an integrated study in some aspectsof task scheduling in WSNs and attempts to improve some key techniques of taskscheduling. It mainly includes the following four aspects:First, in order to prolong the lifetime, reduce the energy consumption and balancethe network load, a task allocation algorithm based on the discrete particle swarmoptimization (PSO), called PSO-DA, is proposed in this thesis. Inspired by theprinciple of dynamic alliance, we build a dynamic alliance model for task allocationin WSNs. In PSO-DA, we design a function taking into account the overall executiontime of tasks, the energy consumption and the network balance. In addition, amutation operator is incorporated into PSO-DA to maintain the population diversityand improve the global searching ability. Experimental results show that the proposedalgorithm achieves a good balance of local solutions and global exploration,effectively reduces the computation time of network and the network energyconsumption, and balances the whole network load.Second, dynamic topology characteristic of WSNs requires a more optimal andefficient topology control mechanism, in which topology can be self-adjusting andself-configuration according to the status of sensor nodes, to ensure that it does notaffect the data transmission and the overall tasks for the damage, failure and mobile ofsome sensor nodes. Therefore, following an analysis of the major disadvantages, suchas higher connectivity redundancy, lower structural robustness etc, in the traditionaltopology control schemes, this thesis presents a novel discrete particle swarmoptimization (NDPSO) based on the local minimum spanning tree (MST). Due to the demand for the optimization of the network lifetime, we transform the topologycontrol problem into a multi-criteria degree-constrained minimum spanning tree(mcd-MST) problem and design a phenotype sharing function of the objective spaceto obtain a better approximation of true Pareto front. The global convergence of thealgorithm is proved using the theorem of Markov chain. Then a topology controlscheme based on NDPSO is put forward. Experimental results indicate that theobtained topology has low overall power consumption, is roust, controls theinter-node communication interference, and prolongs effectively the lifetime of theWSN.Third, the energy and resources constraints of sensor nodes in the WSN requirereducing the power consumption of sensor nodes as little as possible in real-timeexchange of task scheduling. Data aggregation can reduce the number oftransmissions of sensor nodes and energy consumption effectively and it also canexploit sensor node’s processing capabilities as much as possible. Therefore, based onBack-Progagation Neural Network (BPNN) and PSO, we propose an energy-efficientmulti-source temporal data aggregation model for WSNs, termed MSTDA. It consistsof two phases. In the first phase, we present a feature selection algorithm based onPSO to simplify the historical data source. In the second one, we introduce aBPNN-based data prediction algorithm with PSO (PSO-BPNN). Consequrently, thefirst phase reduces the number of input nodes for BPNN and the second one, one ofdata aggregation methods, effectively reduces the energy consumption what WSNsneed in real-time exchange of task scheduling. In addition, MSTDA is able to carry ondata prediction by aggregation multivariable data.Finally, in order to adapt task management to real-time applications of WSNs, wepropose a self-adaptive mechanism taking into consideration the network status ofWSNs in the context of uncertain, dynamic environments. Inspired by the multi-agentsystem (MSA) theory, we design a multi-agent model for WSNs. In this model, wegive an adaptive MAS-based task scheduling strategy, which self adaptively adjuststhe status of unfinished tasks on the fault nodes in order to minimize the cost of thenetwork recovery.更多还原