【作者】 李志刚；

【导师】 肖侬；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2010， 博士

【摘要】 无线传感器网络集信息获取、处理和传输为一体,为人类研究物理世界、获取物理世界的数据,提供了一种有效的方式,其在环境监测、灾害预报等领域发挥着重要的作用,是目前计算机网络、微电子技术和生态环境科学等多个交叉学科研究中的热点问题。无线传感器网络是以数据为中心的网络,除了基于基站节点的实时数据采集模式,还存在针对非实时数据的分布式网内存储模式。无线传感器网络中分布式网内存储的目的是利用冗余节点来保存数据,以进一步提高数据的发现和查询的效率。它关系到网络的可用性和数据的可靠性,但是因为应用环境的复杂性、节点资源的稀缺性和网络拓扑的动态性等因素,分布式存储策略的研究面临许多限制和挑战。有效的分布式存储策略不仅能够满足数据发现的效率,而且能够达到各个存储节点的数据负载均衡。本课题重点关注节点位置已知的大规模网络和不依赖节点位置的大规模网络中的数据存储和发现技术,以及不依赖节点位置的稀疏网络中基于哈希函数的数据存储和路由技术,同时关注多个数据源节点在网络中如何均衡有效的分配存储节点的问题。本文的具体工作,从以下四个方面展开。传感器网络是一种资源受限的自组织网络,节点的能量和计算能力不足以支持复杂协议的设计。针对大规模网络中存在的对等节点数据交换,即随机产生的数据生产者和数据消费者相互之间如何进行数据发现的难点问题,本文借鉴光学中光的反射原理,提出了基于位置的振荡轨迹存储策略。在该策略中,生产者节点将感知到的数据或者数据摘要信息存储到经过该生产者节点的振荡轨迹上;同时将消费者节点的查询信息也存储到经过该消费者节点的振荡轨迹上。理论上,所有的振荡轨迹满足两两相交的特性,在两条振荡轨迹的相交节点上,消费者节点与数据生产者节点能够完成数据交换和数据发现,保证了数据查询成功率。振荡轨迹同时满足数据查询的距离有界性、存储的负载均衡性以及操作的局部性。模拟实验表明,振荡轨迹在多个性能上优于目前存在的double rulings和rumor路由策略。针对传感器节点在不能获得位置信息的情况下,随机产生的数据生产者和数据消费者节点仍然需要进行数据交换的问题,本文提出了基于连接的C-cast存储路由策略,该策略可以克服已有协议的位置敏感性。C-cast的核心思想是通过选择两个节点作为信标节点,在网络中构建两个独立的轮廓覆盖网络。轮廓是指到相应信标节点具有相同跳步数的所有节点集合,这些集合按照一定的顺序连接起来。对单独一个节点而言,它分别属于两个轮廓覆盖网中的轮廓。利用轮廓覆盖网,数据生产者和消费者可以将数据或者查询沿着轮廓进行分发和存储。在理想模型下,C-cast路由策略可以100%的保证数据消费者和生产者节点能够发现对方;在随机模型下,则能够保证以很大的概率发现对方。在性能上,C-cast可以达到基于位置信息的double rulings策略的性能和效果。贪婪路由是传感器网络中常用的数据转发策略,在分布数据存储的过程中也发挥着重要的作用。本文第一次对贪婪路由进行了总结和分类,将贪婪路由分成强贪婪和弱贪婪两种路由方式。已有的研究工作主要集中在基于地理坐标设计弱路由算法,或者在贪婪嵌入图上设计强路由算法。针对获取地理坐标和贪婪嵌入图都需要较多的能量开销,本文提出了一种轻量级的基于树网络嵌入图方法,在得到的基于树的网络嵌入图(TNEG)上设计了一种弱路由策略TGR。TGR在路径长度和网络负载平衡等性能上具有明显的优势。TGR可以应用于稀疏的无位置网络当中。在TNEG和TGR的基础上,可以设计基于节点标记的哈希函数,以满足轻量级的对等节点的数据存储和发现策略。传感器节点的存储容量是有限的,单独一个节点不能存储过多的数据。针对在基站不存在的情况,如何尽可能多的在网络中存储数据源节点产生的数据的问题,本文提出了网络存储节点的均衡划分方法。假设网络中存在k个数据源节点,n个存储节点,本文研究了以下问题:将n个存储节点划分为k组,分配给k个数据源节点作为各自的存储池节点,尽可能满足所有组具有等量多的节点,同时满足存储节点到相应的数据源节点的路径长度之和最小。本文将该问题规约为完全二部图的加权匹配问题。针对目前的算法不适合在传感器网络中应用,本文提出了随机贪婪划分算法和基于Voronoi单元划分算法。实验表明,基于Voronoi单元划分算法在性能优于随机贪婪划分算法,其存储路径开销也更接近最优值。综上所述,本文针对无线传感器网络中的基于位置,基于连接的数据存储发现策略,以及存储负载平衡等问题进行了研究,并提出了有效的解决方案,对于推动传感器网络的数据管理,实现数据的可靠性具有一定的理论和应用价值。更多还原

【Abstract】 Wireless Sensor Networks can integrate information collection, processing and transmission together to support researching the physical world and retrieving data from it for researchers. It can play a significant role in environment monitoring, disaster forecasting, etc. It is a research hot spot and an interdiscipline of computer networking, microelectronic technology and ecological environment science, etc. Wireless Sensor networks are data centric network. Despite sink-based real time data collection model, distributed in-network storage for non-realtime data is another research issue.Distributed data storage in sensor networks does matter with network availability and data reliability. Because of the environment complexity, node resource scarcity and network topology dynamics, etc, researching on distributed storage strategies are faced with too many limitations and challenges. Effective and efficient distributed storage strategies do not only satisfy data discovery, but also achieve load balance. This thesis focuses on data storage and discovery for both location-aware and location-free large scale sensor networks, and Hash storage and routing protocol for location-free sparse network. The contributions include four aspects as following.Sensor networks are resource limited networks, so the energy and computation of single node cannot support complicated protocols. In sensor networks, random generated data producers and data consumers compose of peer-to-peer networks. In order to address how to make a producer and a consumer discover each other, this thesis borrows the idea of light reflection theory and proposes a bouncing track storage strategy. In this strategy, the producer can disseminate its data along its own bouncing track; meanwhile the consumer can disseminate its query along its own bouncing track. In theory, every two bouncing track can intersect with each other in ideal case. At the intersecting node, consumers and producers can exchange data. The bouncing track strategy satisfies data retrieval distance-bounded, storage load balance and operation locality. The simulation shows that the performance of bouncing track is better than double rulings and rumor routing.In order to make the consumers and producers discovery each other in the case that the sensor nodes cannot obtain their location, this thesis proposes C-cast storage routing strategy. This strategy does not need location information, rather than it needs to select only two beacons to establish two contour overlay networks in the network. A contour includes all the nodes that have same hop number to one beacon. For a single node, it belongs to two contours in the network. By using contour overlay networks, producers and consumers can disseminate data along contours. In ideal model, it can guarantee that any producer and consumer pair can discover each other 100%. In random model, it is high probability. The C-cast can achieve similar performance and result as the double rulings, which is location-based.Greedy routing is significant for the data transmission and distributed storage in sensor networks. This thesis classifies the greedy routing into strong greedy routing and weak greedy routing firstly. The existing works are mainly on designing weak routing on geographic coordinate, or designing strong routing on greedy embedding graph. However, these two approaches need too much energy for obtaining geographic coordinate or greedy embedding graph. This thesis proposes a light weight tree-based network embedding (TNEG) method. Based on TNEG, a new weak routing strategy is designed, called TGR. TGR can achieve good performance on path stretch factor and load balance. TGR can be used in sparse location-free network. Based on TNEG and TGR, label-based Hash function can be designed for light weight peer-to-peer data storage and discovery strategies.The storage capacity of a single sensor node is limited. This thesis proposes a new method for dividing storage nodes into balancing groups for many data resource nodes in order to maintain as much as possible data in the network. It is assumed that there are k data resource nodes and n storage nodes in the network. The objective of this thesis is dividing the n storage nodes into k group, and each group responds for storage data for one data resource node, while the sum path length of storage node to data resource node is minimal. This thesis proves that this problem can be reduced to maximum weight bipartite matching problem. As the existing algorithms are not applicable for sensor networks, this thesis proposes random greedy algorithm and Voronoi-based algorithm. The simulation shows the performance of Voronoi-based algorithm is better than the random greedy algorithm and its storage path cost is near the optimal one.To sum up, this thesis researches location-based, location-free data storage and discovery strategy and load balance storage problems, while proposes solutions for them. This thesis has the theory and application value to improve the data management, data reliability, etc.更多还原