节点文献
物理干扰模型下的无线链路调度
【作者】 吕玉华；
【导师】 禹继国；
【作者基本信息】 曲阜师范大学 ， 计算机应用技术， 2013， 硕士
【摘要】 无线传感器网络(Wireless Sensor Networks, WSNs)是一种飞速发展的新兴网络，是将传感器节点随机部署在指定区域并自组织成的无线多跳通信网络。WSNs综合了传感、信息处理和嵌入式等多项技术，可以对部署区域内感兴趣的信息进行协作地感知、采集和处理，并采用已经形成的多跳路径将获取到的信息最终传递到基站。基站通过互联网或卫星通信将信息传递给用户进行分析。作为本世纪十大科技之一，WSNs在许多方面都展现了广泛的应用前景，有些方面甚至已经得到大量应用。虽然WSNs在许多领域已经取得了一系列成就，但作为新兴的高科技技术，WSNs领域仍有很多开放性问题需要解决，例如链路调度，拓扑控制，控制集的构造，嵌入和时间同步等。本文就WSNs中的链路调度问题进行了分析与研究。本文对调度问题的已有研究成果进行了详细的描述，并在物理干扰模型下提出了最大权重独立集(Maximum Weighted Independent Set of Links, MWISL)问题的启发式算法、最短链路调度(Shortest Link Scheduling, SLS)问题的常数近似算法和最小延迟数据聚合(Minimum Delay DataAggregation, MDDA)问题的近似算法。对于每个算法，我们都对算法的正确性给予理论分析，并通过仿真对算法的有效性进行了验证。具体研究内容如下：MWISL问题可以描述为给定一组通信链路，每一条链路都有一个权重，根据干扰约束条件选择一个能够同时进行信息传输的链路子集并且使得该集合中所有链路的权重之和最大。MWISL问题的启发式算法每次采用贪婪策略从候选链路集合中选择一个满足条件的最优链路。依次执行，直到所有候选链路处理完成。仿真实验表明，算法具有良好的实际性能。SLS问题的目标是在给定的约束条件下，以最短的时间调度所有链路。在有界线性功率分配方式下，提出了一个SLS问题的常数近似算法。采用网格划分的方法，使得每个时间段所对应的链路集合中的链路都满足SINR(Signal to Interference plus Noise Ratio)阈值约束。通过理论分析，对算法的有效性和近似比进行了论证。仿真实验结果表明，与已有的研究成果相比，算法具有更好的实际性能。MDDA问题是以最短的时间将网络中节点的数据传递到基站。在最短链路调度算法的基础上，提出了解决MDDA问题的一个近似算法。当所划分网格中的最大链路数有界时，算法的近似比为常数。
【Abstract】 Wireless Sensor Networks (WSNs) are rapidly developing emerging network and sensor nodesare randomly deployed in the designated area, making a multi-hops wireless communicationnetwork in self-organized way. WSNs integrate sensor, information processing, embeddedtechnology and so on. It can collaboratively perceive, collect and process information of interestin deployment area and transfer the information to the base station in the formed multi-hop paths.The base station transfers the information to the user via the Internet or satellite communicationsfor analysis. As one of the top ten technologies in this century, WSNs show widely applicationprospects in many ways, and some even have a large number of applications.As an emerging technology, though a series of results have been achieved in many areas ofWSNs, there are still many open questions to be solved such as link scheduling, topology control,the control set, embedded, time synchronization, etc. In this paper, we focus on the problem oflink scheduling.In this paper, we describe the existing research results of link scheduling problem in details.Under the physical interference model, we propose a heuristic algorithm for maximum weightedindependent set of links (MWISL), a constant approximation algorithm for shortest linkscheduling (SLS) and an approximation algorithm for minimum delay data aggregation (MDDA).For each algorithm, we give the theoretical analysis for the correctness of the algorithm and theeffectiveness of the algorithm is verified by simulation. Specific research contents are given asfollows:The problem of MWISL can be described as follows: Given a set of links with each linkhaving a weight, we choose a link subset from the set that can transmit simultaneously and theweight sum of all links in the subset is maximal. The heuristic algorithm for MWISL selects anoptimal link that meets the condition each time with greedy strategy from the candidate links.Loop execution until all the candidate links are processed. Simulation experiments show that thealgorithm has good practical performance.The aim for SLS is that schedule all links in the network in the shortest time under a givenconstraint condition. We propose a constant approximation algorithm for SLS with boundedlinear power assignment. With grid partition, all links of each link set in the corresponding timeslot meet the SINR (Signal to Interference plus Noise Ratio) threshold constraint. Theeffectiveness and the approximate ratio of the algorithm are discussed through theoreticalanalysis. Simulation experiments show that the algorithm has better practical performance thanexisting results.The problem of MDDA is that all the nodes in the network transfer their data to the base station with the shortest time. Base on the algorithm for SLS, we propose an approximationalgorithm for MDDA. When the number of links in the divided grid is bounded, theapproximation ratio of the algorithm is constant.