SIA OpenIR  > 工业信息学研究室
面向数据收集的无线传感器网络节点部署问题研究
Alternative TitleResearch on Node Deployment Problem in Data Collection Oriented Wireless Sensor Networks
刘琳1,2
Department工业信息学研究室
Thesis Advisor于海斌 ; 曾鹏
ClassificationTP212
Keyword无线传感器网络 节点部署 中继节点 簇首节点 网络生命期
Call NumberTP212/L73/2009
Pages131页
Degree Discipline机械电子工程
Degree Name博士
2009-01-19
Degree Grantor中国科学院沈阳自动化研究所
Place of Conferral沈阳
Abstract随着MEMS、无线通信、自动控制和人工智能等技术的快速发展,无线传感器网络引起了学术界的极大关注。它的出现改变了人与自然界的交互方式,其应用领域将会深入到社会生活的各个方面。节点部署问题是无线传感器网络研究的基本问题之一。在无线传感器网络的某些实际应用中,节点部署通常采用人工部署方式,为满足网络的节能性、可靠性、实时性等性能需求,需要额外部署一些节点。为限制网络布设成本,要对这些新增加的节点进行有针对性地部署。基于这种应用环境,论文对面向数据收集的无线传感器网络节点部署问题展开研究工作,主要的研究内容与成果包括以下几个方面。论述了无线传感器网络节点部署问题的研究内容、分类和评价体系,系统地总结了前人的研究成果和不足。为改善网络的连通性和满足网络生命期需求,提出了一种启发式的两阶段中继节点部署策略。第一阶段的部署确保了网络连通性;第二阶段部署,结合负载平衡的路由协议,满足了网络的生命期需求。仿真结果表明该方法在满足上述性能需求的前提下,最大限度地减少了需要部署的中继节点数目。针对网络中簇首选择不合理导致数据收集成本过高的问题,提出了面向数据收集成本最优化的簇首节点选择算法。当网络状态一定时,簇首节点的优化选择问题是一类组合优化问题。论文首先提出了基于小规模网络的全局最优化的簇首节点选择算法(BFM)。针对BFM算法复杂度高的缺点,进而提出了基于大规模网络的启发式的簇首节点选择算法,该算法可以在较短时间内得到问题的次优解。考虑网络簇首的容量限制和最大簇半径限制,把簇首节点的优化部署问题形式化为整数规划问题。提出两种启发式的簇首优化部署策略:基于K-平均的簇首部署策略和基于K-平均与模拟退火混合算法的簇首部署策略。前者适用于网络运行时的动态部署,后者适用于网络投入使用前的规划部署。仿真结果表明,分簇后的网络在满足上述限制的情况下,最大限度地延长了网络生命期。有针对性的节点部署离不开网络状态监测,为使网络状态监测不过多占用网络资源,提出了一种高效的网络状态监测机制。通过对节点编码并在节点间建立起一个逻辑层次簇结构,利用各个子簇状态数据的相似性和编码的连续性,实现了网内无损聚合。该监测机制使得网络状态信息的收集,在不丢失数据细节信息的情况下,数据通信量大大减少。本论文的研究仅为无线传感器网络中的规划部署问题提供了一个框架,尚未形成一个完整可行的网络规划部署系统。各项研究成果可以为无线传感器网络设计者、方案提供者以及无线传感器网络应用的系统集成,提供一些有益的指导。
Other AbstractWith the rapid developments in MEMS, wireless communication, automatic control and artificial intelligence, the Wireless Sensor Network (WSN) gains a great deal of academic attention all over the world. The WSN is changing the way people interacting with the physical world. Its application fields have broadened into every sector of our social life. Node deployment is one of the fundamental issues in the research of WSN. In some WSN applications, network nodes are usually deployed manually. To meet the performance requirements such as energy-efficiency, reliability, and real-time, additional nodes are needed. To keep the network cost within a certain limit, these newly added nodes need to be deployed purposefully. Based on this kind of application mentioned above, the research work in this paper is mainly focused on the study of node deployment strategy for data collection oriented WSN. The main contributions of this thesis are as follows: At first, the paper describes the general research efforts nowadays relating to node deployment problem, discusses their classifications, and indicates their evaluation metrics. Related works are surveyed systematically and the deficiencies of current researches are summarized. In the second part, the paper proposes a heuristic relay node deployment strategy to enhance the connectivity and to satisfy the requirement of network lifetime, in which node deployment is divided into two phases. The first phase deployment aims at ensuring connectivity. The second phase deployment combined with a load balance route protocol meets the requirement of network lifetime. The simulation results show that the strategy minimizes the number of relay nodes for a demanded lifetime. A common problem in data collection oriented WSNs is how to decide cluster-heads. Unreasonable selection of cluster-heads will easily cause high cost for data collection. In the third part, the paper proposes a cluster-head selection algorithm, which is based on optimal data collection cost and successfully solved the problem. Given the network topology, cluster-head selection is a combinatorial optimization problem. For a small-scale network, the globally optimal solution can be achieved by using Brute-Force-Method, which has very high time complexity. In contrast, the heuristic, optimized cluster-head selection algorithm introduced in the paper is more applicable to large networks. The algorithm can get a sub-optimal solution in much shorter time in a large-scale WSN. After that, the optimal problem of cluster-head deployment is formulated as an Integer Programming with the condition of restrictions of cluster-head capacity and the maximal cluster radius. This paper proposes two heuristics strategies to optimize the cluster-head deployment. One is based on the algorithm of K-mean, the other is based on the hybrid algorithm of K-mean and simulated annealing. The former is applicable to deploy cluster-heads when the network is running while the latter is suitable before the network operate in practice. The simulation results show that the clustered network meets restrictions mentioned above while the network lifetime requirement is farthest satisfied. All researches mentioned above are based on network health status monitoring. To avoid too much network resources being used for a long time by the monitoring process, this paper finally proposes, an efficient network status monitoring mechanism is discussed in the last part of this paper. All the nodes in WSN are encoded and a logical multi-level cluster is constructed among the nodes. Making use of the similarity of network status data and continuity of node codes in sub-cluster, in-network lossless aggregation can be realized. Without losing details of network status data, this monitoring mechanism reduces communication cost significantly. The research results may serve as guidelines for WSN designers, solution providers, and system integrators of WSN application. But we need to point out that the paper provides only a framework for WSN planning and deploying. A complete planning and deploying system for WSN is still not available yet. A lot of work is to be done in the future.
Language中文
Contribution Rank1
Document Type学位论文
Identifierhttp://ir.sia.cn/handle/173321/400
Collection工业信息学研究室
Affiliation1.中国科学院沈阳自动化研究所
2.中国科学院研究生院
Recommended Citation
GB/T 7714
刘琳. 面向数据收集的无线传感器网络节点部署问题研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2009.
Files in This Item:
File Name/Size DocType Version Access License
10001_20051801471902(5386KB) 开放获取--Application Full Text
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[刘琳]'s Articles
Baidu academic
Similar articles in Baidu academic
[刘琳]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[刘琳]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.