【作者】 于博；

【导师】 李建中；

【作者基本信息】 哈尔滨工业大学 ， 计算机软件与理论， 2013， 博士

【摘要】 随着传感器技术、嵌入式计算技术以及无线通信技术的迅速发展，无线传感器网络以其低成本、自组织网络的优点被广泛地应用在环境监测、医疗卫生、国防军事等众多领域。无线传感器网络作为一种全新的信息获取和处理技术，对网络中传感器节点收集到的感知数据进行操作是必不可少的，其中数据聚集就是无线传感器网络上一项最基本的操作，近年来受到学术界的广泛关注。在很多无线传感器网络应用中，管理员或用户通常需要通过基站提出一些关于感知区域中某些物理属性的聚集查询，此时基站需要将网络中所有或部分传感器节点获取的感知数据进行聚集，并将聚集值返回给查询者。为了消除聚集过程中无线通信带来的干扰，需要为网络生成一个无冲突的聚集调度，并最小化聚集时间，该问题称为聚集调度问题。因此，聚集调度方法满足了查询者希望迅速获得聚集结果的需求。无线传感器网络由一组低成本、低功耗的无线传感器节点通过自组织方式形成网络，具有节点能量有限、节点通信能力有限、网络动态变化等特点。这些给无线传感器网络上聚集调度问题的研究带来了很多挑战，包括如何设计能量有效的聚集调度算法、如何设计适用于动态网络拓扑的调度算法、如何提高算法的数据传输率等。针对上述挑战，本文从多方面考虑了无线传感器网络上的聚集调度问题，并提出相应的策略和算法。本文的研究工作及成果包括以下几个方面。首先，本文提出了无线传感器网络的分布式聚集调度算法。现有的聚集调度算法均为集中式算法，不适用于动态变化的网络拓扑，且聚集时间延迟较高。针对上述问题，本文提出了一种两阶段的分布式聚集调度算法。第一阶段利用极大独立集的方法，分布式地构造一棵具有良好性质的聚集树，并将网络中的节点分为不同的角色。在第二阶段网络中的传感器节点首先通过相互通信得到局部的拓扑信息，然后根据获取的信息分布式地完成调度生成。由于无线传感器网络的聚集调度问题已被证明为NP-难问题，本文给出的分布式聚集调度算法为一个近似算法，通过理论分析得出该算法的近似比接近于常数，改进了原有算法的聚集时间上界。本文针对动态变化的网络拓扑进一步提出了一种自适应的分布式聚集调度算法，包括自适应的聚集树结构维护和自适应的聚集调度更新。第二，本文针对多基站无线传感器网络提出了两种聚集调度算法。单基站无线传感器网络中存在节点负载不平衡与能量消耗不平衡的问题，而在网络中布置多个计算和通信能力强大的基站可以有效地缓解该问题，因此多基站无线传感器网络也被广泛关注与应用。本文提出了适用于该类型网络的两种聚集调度算法，两算法均分为三个阶段，第一阶段为网络构造出一个聚集森林作为通信骨干网，第二阶段和第三阶段对聚集森林中的所有节点以自底向上的方式逐层生成聚集调度。第一个调度算法采用维诺图划分的方法构造聚集森林，而第二个调度算法采用网络支配集的思想构造出一个具有良好性质的聚集森林，从而改进了第一个算法。本文通过理论分析给出了两算法聚集时间的上界，并证明第二个算法性能优于第一个算法。模拟实验验证了两算法的有效性。第三，本文提出了适用于周期轮转模式无线传感器网络上的聚集调度算法。针对无线传感器网络节点能量有限的特点，周期轮转的节点工作模式逐渐被采用，即节点在每个工作周期中工作一段时间，在其余的时间进行睡眠。周期轮转模式可以很大程度上节省传感器节点的能量，从而延长网络的生命周期，具有广泛的应用前景。本文考虑了该类型的无线传感器网络上的聚集调度问题，并提出一种聚集调度算法来解决该问题。该算法首先构造出网络的一个分层结构，然后根据该结构进行工作周期调度。理论分析得出该算法的近似比接近于常数，模拟实验也验证了该算法的有效性。第四，本文为无线传感器网络的聚集调度提出了一种新的机会聚集调度机制。已有聚集调度算法未考虑聚集过程中可能发生的传输失败，因此很难适用于链路质量不理想的无线传感器网络。针对此问题，本文利用机会路由的思想提出了一种两阶段的机会聚集调度机制，以提高已有调度算法的数据传输率。该机制可以应用在任一聚集调度算法之上，是对已有聚集调度算法工作的一个有力补充。机会聚集调度机制在第一阶段为已有调度进行机会链路扩展，即为网络添加一些质量较好的机会链路，并提出了两种链路选择策略。该机制在第二阶段依照扩展后的调度执行聚集操作，并设计了适应于机会链路传输的新聚集执行算法。模拟实验验证了该机会聚集调度机制极大提高了数据聚集时的数据传输率，并验证了该机制的能量有效性。更多还原

【Abstract】 With rapid development of sensing techniques, embedded computing techniques andwireless communication techniques, wireless sensor networks with the advantage of lowcost and self-organization are widely applied in many fields, such as environmental mon-itoring, medical care and military defense. Wireless sensor network is a novel technologyfor acquiring and processing information. Thus, operations on the sensed data obtainedby wireless sensors are indispensable, and aggregation is one of the most fundamentaloperations, which is widely concerned by academia. In many wireless sensor network ap-plications, administrators or users usually submit an aggregate query on some of the phys-ical attributes of the sensed area. Then, the base station needs to aggregate the sensed datafrom all or a part of the nodes, and provide the aggregate result to the query user. In orderto eliminate the wireless interference during aggregation, aggregation scheduling problemaims in producing a collision-free schedule for the network, minimizing the aggregationtime at the same time. Thus, aggregation scheduling methods satisfy the query users withquick response by eliminating the interference and reducing the aggregation time. A wire-less sensor network is composed of a set of low-cost, low-power sensor nodes and theyorganize themselves to form an ad-hoc wireless network. Wireless sensor networks havethe following characteristics of limited node energy, limited communication capability,dynamic topology, etc. This brings some challenges for solving the aggregation schedul-ing problem in wireless sensor networks, e.g., how to design energy-efcient schedulingalgorithms, how to design scheduling algorithms for dynamic topology, how to increasethe data delivery rate. Facing the challenges, this thesis considers aggregation schedul-ing problem in wireless sensor networks from diferent aspects, and proposes diferentstrategies and algorithms. The research issues and results include the following.First, this thesis proposes a distributed aggregation scheduling algorithm for wirelesssensor networks. The previous aggregation scheduling algorithms are centralized withhigh aggregation time latency, which are not suitable for dynamic topologies. To solvethe problems above, this thesis proposes a two-phase distributed scheduling algorithm.The first phase of the algorithm distributively constructs an aggregation tree with a goodproperty, making use of maximal independent set, and divides the nodes into diferenttypes. In the second phase of the algorithm, sensor nodes first communicate with each other to obtain the local information and then generates the schedule with the obtainedinformation. The proposed algorithm is an approximation algorithm since the aggregationscheduling problem is proved NP-hard. Theoretical analysis show that the approximationratio of the algorithm is close to a constant number, which improves the aggregation timelatency. This thesis also proposes an adaptive strategy for our algorithm to handle thedynamic topologies, including adaptive tree maintenance and aggregation update.Second, this thesis proposes two aggregation scheduling algorithms for multi-sinksensor networks. There exist the problems of imbalanced load and energy cost in single-sink sensor networks. Deploying multiple sinks (base stations) with powerful computa-tion and communication capabilities helps alleviate the problems, thus multi-sink sensornetworks are widely concerned and applied. This thesis proposes two scheduling algo-rithms with two phases, which construct aggregation forests in the first phase and generateschedules in a bottom-up fashion. The diference between the two algorithms lies in theforest construction phase. The first algorithm takes advantages of Voronoi partitions andthe second algorithm constructs an aggregation forest with good properties using dominat-ing sets. This thesis shows the aggregation time of both algorithms and proves the secondalgorithm performs better. Simulation results show the efectiveness of the algorithms.Third, this thesis proposes an aggregation scheduling algorithm for duty-cycledwireless sensor networks. Considering the limited node energy in wireless sensor net-works, duty-cycled working style is adopted, i.e., a node works for a duration of timeduring a cycle and sleeps for the rest time of the cycle. The duty-cycled mechanism helpssave large amounts of energy, thus prolong the network lifetime, which has a wide ap-plication perspective. The proposed algorithm first constructs a layered structure of thenetwork and then schedules the working period. Theoretical analysis shows the approxi-mation ratio of the algorithm is close to a constant number, and simulation results showthe efectiveness of the algorithm.Finally, this thesis proposes a novel opportunistic aggregation scheduling mechanis-m for aggregation scheduling in wireless sensor networks. Existing scheduling algorithm-s do not consider the transmission failure during aggregation, thus are not applicable insensor networks with non-ideal link qualities. This thesis proposes a two-phase mech-anism based on the idea of opportunistic routing in order to increase the delivery rate.The proposed mechanism can be applied in any of the existing scheduling algorithms,which is a complementary for existing work on aggregation scheduling. The mechanismaugments the original schedule by adding opportunistic links with good link qualities in the first phase. Two strategies of opportunistic link selection are proposed in this thesis.The mechanism executes aggregation according to the augmented schedule in the secondphase. A new aggregation execution algorithm is proposed to handle the transmissionby the augmented schedule. Simulation results show that the opportunistic aggregationscheduling mechanism significantly increases the delivery rate, and verify the energy ef-ficiency of the mechanism.更多还原