工业无线传感器网络中继节点部署研究

CORC > 沈阳自动化研究所 > 中国科学院沈阳自动化研究所 > 工业控制网络与系统研究室

题名	工业无线传感器网络中继节点部署研究
作者	马超凡
学位类别	博士
答辩日期	2017-05-27
授予单位	中国科学院沈阳自动化研究所
授予地点	沈阳
导师	梁炜
关键词	无线传感器网络中继节点部署近似算法生命周期约束服务质量约束
其他题名	Research on Relay Node Placement in Industrial Wireless Sensor networks
学位专业	检测技术与自动化装置
中文摘要	无线传感器网络（Wireless Sensor Network, WSN）的出现加速了物理世界与虚拟信息世界融合的实现，并深刻改变着人类感知世界的方式，使其成为继互联网后，又一引领信息产业革命的热点技术。随着WSN大范围的应用，WSN以其低成本、安装方便和易维护等优点，正逐步应用于多种工业场景中。工业无线传感器网络（Industrial Wireless Sensor Network, IWSN）已成为降低测控系统成本，扩展其应用范畴的革命性技术。多数工业应用场景中，传感器节点位置已知且固定，然而这些低成本节点具有通信范围小、能量受限等缺陷，须通过部署额外的中继节点保证网络连通性。虽然近年来各国学者对WSN中继节点部署问题进行了广泛而深入地研究，但特别针对IWSN中继节点部署问题的研究尚处于起步阶段。不同于传统应用，工业应用具有大规模、低功耗、硬实时、高可靠等需求，且工业环境呈现电磁干扰强烈、金属遮挡严重、人员移动频繁等特点。传统中继节点部署问题已是NP-完全问题，而工业应用的新需求和恶劣环境进一步增加了该问题的求解难度。已有部署算法不进行问题拆分而整体求解这使其在进行大规模IWSN部署时遭受算法性能显著衰减、时间复杂度大幅增长等问题。为此，本文提出了“问题拆解”、“子问题求解”和“优化合并”三阶段中继节点部署方案框架。该方案框架借助“分而治之”的思想降低整体问题求解复杂度并通过对局部解的优化合并保证算法性能。该部署方案框架在工业环境中充分考虑了部署成本、生命周期、实时性、可靠性等网络性能约束，形成了一套满足多约束、大规模工业无线网络部署方案。基于该中继节点部署方案框架，本文具体解决了以下四类问题：（1）面向成本的中继节点部署问题：针对工业应用大规模、低成本要求，提出了基于邻居分组的连通敏感中继部署算法。该算法通过迭代依次从未被覆盖传感器节点中按邻居关系选取一组传感器节点，并将针对该组的几何圆盘覆盖问题抽象为集合覆盖问题求解，进一步将局部解合并问题建模为欧式距离优化问题，最终基于解析几何理论求解并采用最小生成树算法构建全局网络连通性。该算法有效克服了已有算法性能随网络规模衰减的缺陷，保证了算法在大规模部署时的性能。（2）面向生命周期的中继节点部署问题：针对工业应用对IWSN长时间稳定、可靠运行要求，提出了基于聚类的容错部署算法。该算法根据能耗约束和地理邻近信息将传感器节点进行聚类分组，即将地理邻近且总能耗满足能耗约束的无线传感器节点划为一个分组，由于每个分组满足能耗约束从而将整体大规模、多约束问题有效降解为若干小规模斯坦纳树问题。最终，基于最小生成树为传感器节点构建至汇聚节点冗余通路，以此满足工业应用对可靠性、容错性要求。已有算法没有考虑工业对可靠性要求且无法保证算法近似比，而该算法在多项式时间下能够保证近似比，可有效保证算法性能。（3）面向实时性的中继节点部署问题：针对工业应用对IWSN的实时传输要求，提出了基于集合覆盖的部署算法。该算法基于邻居关系将大规模、多约束连通性问题进行逐层分解，在分解过程中利用最短路径树剔除不满足实时性约束的部署位置，从而将每层子问题抽象建模为无需考虑实时性约束的小规模集合覆盖问题。在利用贪心算法求解局部集合覆盖问题后，基于剪枝技术合并局部解，从而进一步提高算法性能。该算法能够保证比已有算法更优的近似比。（4）面向实时、可靠的中继部署问题：目前已有算法皆基于理想0-1信道模型，无法适用于恶劣的工业射频环境。为此，提出了基于实时信道质量测量的部署方法。该方法采用自汇聚节点端向传感器端逐跳迭代部署的策略，将每次迭代子问题抽象为集合覆盖问题并基于最短路径树算法删除不满足实时性约束的部署位置，在该子问题求解过程中每部署一个中继节点就通过实际信道质量测量调整中继节点部署位置，以此保证通信可靠性。该方法充分考虑了恶劣工业射频环境等因素对部署的影响，克服了已有算法基于理想0-1信道模型无法保证通信可靠性的问题。综上，论文对IWSN中继节点部署问题进行了较为系统和深入的研究，旨在为IWSN中继节点部署提供一套较为实用的部署方案以及理论支撑。
英文摘要	The emergence of Wireless Sensor Networks (WSNs) expedites the integration of the real-world and the world of information, and highly changes the way people sense the real-world. This makes WSNs an another outstanding technique leading the information revolution. The locations of sensor nodes are predetermined and fixed in most applications. However, these low-cost sensor nodes suffering the limitations of small communication radii and constrained energy supply, which results in the disconnection of whole network. Therefore, additional relay nodes should be deployed to build the global network connectivity. As the first step of building networks, the construction of network topology directly or indirectly impacts the performance of each protocol layer, which highlights the importance of the relay node placement problem. In recent years, numerous research efforts have been dedicated to the relay node placement problem. For its low-cost, convenient installation and easy maintenance, WSNs have been progressively employed in many industrial applications, e.g., industrial automation and smart grid. Different from traditional applications, the industrial applications have the requirements of high-reliability, real-time, large-scale and low-power-consumption. Furthermore, there exist high radio frequency interference and serious metal obstacle in the industrial environment. Although the traditional relay node placement problem is already NP-complete, the new requirements and harsh industrial environment make this problem even harder, and disable the traditional relay node placement algorithms. To this end, this paper proposes a three-step framework for the relay node placement in industrial WSNs. This framework considers the reliability, real-time and lifetime constraints in industrial environment, and forms a series of approaches to swiftly build a large-scale WSNs under multiple constraints. Based on this framework, this paper solves the following four problems: (1) For the large-scale cost-aware relay node placement problem, we present a connectivity-aware neighborhood-grouping-based relay node placement algorithm. This algorithm selects a group of sensor nodes based on the neighborhood in each iteration, and formulates the geometric disc cover problem for this group as the set cover problem. After these iterations, we convert the problem of merging these local solutions as a Euclidean distance optimization problem, and solve this problem by using the analytic geometry theory. Finally, the connectivity of the whole network is built by the minimum spanning tree algorithm. This algorithm overcomes the drawback (the performance degrading with the network scale) of existing algorithms, and guarantees the algorithm performance. (2) For the lifetime constrained relay node placement problem, this paper proposes a cluster-based algorithm. This algorithm groups sensor nodes based on their geographic information and energy consumption, i.e., the sensor nodes whose total energy consumption fulfilling energy constraint and closed to each other are divided into the same group. Thus, the large-scale multi-constraint optimization problem is transformed into several Steiner tree problems with smaller-scale. In the end, the minimum-spanning-tree-based algorithm is adopted to build network connectivity. Comparing with existing algorithms which cannot ensure a definite approximation ratio, this algorithm guarantees an approximation ratio. (3) For the real-time relay node placement problem, this paper proposes a set-covering-based algorithm. This decomposes the whole problem into levels according to their neighborhood. To be specific, in the procedure of decomposition, this algorithm removes the candidate deployment locations which cannot satisfy the delay constraint. As a result, the problem in each level becomes a set covering problem which is not constrained by delay and reliability. This algorithm solves the set covering problem by the greedy algorithm, and then merges the solution to all levels by the pruning technique. To the best of our knowledge, this algorithm has an approximation algorithm better than existing algorithms. (4) For the real-time and reliable relay node placement problem in industrial environment, this paper presents real-time-measurement-based approach. This approach adopts a strategy which iteratively deploys relay nodes from the sensor nodes to the sink node in a hop-by-hop manner. In each iteration, this approach first selects the candidate deployment locations fulfilling delay constraint, and formulates the problem in this iteration as the set covering problem, and finally adjusts the deployment locations according the real-time measurement of packet reception rate so as to improve reliability. This approach fully considers the high radio frequency interference and serious metal obstacle in industrial environment, and overcomes the defect of existing algorithms which cannot accurately estimate the communication quality due to the ideal 0-1 channel model employed by them, and provides an approach to build real-time and reliable industrial WSN. To sum up, this paper provides an extensive and in-depth study for the relay node placement problem in industrial wireless sensor networks. The purpose of this paper is to supply a practical theory framework for relay node placement, and gives a guideline to design a particular relay node placement approach in industrial applications.
语种	中文
产权排序	1
内容类型	学位论文
源URL	[http://ir.sia.cn/handle/173321/20565]
专题	沈阳自动化研究所_工业控制网络与系统研究室
推荐引用方式 GB/T 7714	马超凡. 工业无线传感器网络中继节点部署研究[D]. 沈阳. 中国科学院沈阳自动化研究所. 2017.