标题: 无线感测网路中低延迟和省电之资料收集方法
Low-Latency and Power-Saving Data Collection Mechanisms for Wireless Sensor Networks
作者: 巫芳璟
Wu, Fang-Jing
曾煜棋
Tseng, Yu-Chee
资讯科学与工程研究所
关键字: 通讯协定;资料收集;资料收集器;电量保存;负载平衡;无线感测网路;communication protocol;data gathering;data mule;energy conservation;load balance;wireless sensor network
公开日期: 2011
摘要: 在无线感测网路中,资料收集是一个很重要的任务。设计一个资料收集机制时,两个重要的议题,低延迟和省电,必需被考虑。前者是要尽快的收集感测资料,后者是节省感测器的电量达到延长网路生命。本论文针对不同通讯协定层,设计感测网路资料收集机制达到以上两个目标。本论文包含三个资料收集机制之研究。第一个研究中,我们针对MAC通讯协定层,设计资料收集机制。透过充分利用可以控制的移动式节点,第二个研究针对一个连通的无线感测网路,设计一个分散式布建移动式节点之通讯协定来协助收集感测器资料;第三个研究考虑一个不连通的无线感测网路,利用移动式节点协助资料收集。

在第一个研究中,我们提出一个新的通讯干扰模型,并另利用此模型设计一个相容于ZigBee的MAC通讯协定。在一个多点跳跃的无线网路中,传统定义通讯干扰的模型是避免一个节点和其两个跳跃内的邻近节点使用相同的通讯时间槽。然而,因为感测网路中资料收集时,通讯的方向只限于由感测节点传送到资料收集中心,我们因此可以重新定义一个精确的通讯干扰模型。基于这样的观察,我们利用此较精确的通讯干扰模型,设计一个有效的分散式之通讯排程机制来达到资料收集之低延迟和省电的目标。

随着感测资料是经由一个静态感测网路收集,感测网路会遭遇电量消耗不均衡的问题,即越靠近资料收集中心的感测器之电量会消耗较快。为了减轻此问题,第二个研究考虑一个双层的感测网路,其中一组电量充沛的移动式节点被用来布建一个主干网路协助静态的感测器传递资料到资料中心。此种双层的感测网路优点是利于大规模布建,且可以有效降低传统多点跳跃通讯时感测器所消耗的电量。然而,布建移动式节点使其具网路连通和布建均衡之特性是相当挑战的,尤其当无法得知网路节点之位置资讯的情形下。网路连通是确保移动式节点彼此可以互相通讯,布建均衡是确保每个移动式节点收集等量的感测资料。在本研究中,我们将此问题建模成一个具连通性且布建均衡之移动式节点位置重置之最佳化问题,并证明此问题为NP-complete。为了达连通性和布建均衡之目标,到我们提出了一套分散式的双模移动式节点位置重置通讯协定,其中主要特点是移动式节点位置重置不需使用位置资讯。经由下层感测网路之拓扑结构和区域性的资讯(称为covering cell),本通讯协定允许每个移动式节点可以自主决定其移动的位置。透过大规模的网路模拟结果显示本研究设计之机制以较少的移动距离和通讯成本同时达到连通性且布建均衡之目标。

有鉴于现存大部分的研究焦点与设计皆针对一个连通的无线感测网路,第三个研究考虑的是一个空间上分割的无线感测网路,其中包含数个彼此距离甚远且不连通的孤立子网路。我们处理利用移动式节点(称为资料收集器)进行感测资料收集之议题。在此种不连通的环境中,资料收集的延迟和网路生命是相当重要的议题。我们针对此问题进行建模为一个具电量限制之资料收集器移动路径问题,称为energy-constrained mule traveling salesman problem (EM-TSP),其目标是找到一条资料收集器之最短移动路径使得每个孤立的子网路至少被资料收集器拜访一次且感测器之最大电量消耗不会超过一个预设的门槛值。值得注意的是本研究建模的问题是一个典型NP-hard问题traveling salesman problem (TSP)的更一般化的模型。以几何性质为基础,我们提出有效的机制来解决EM-TSP问题。此外,本研究亦将此设计延伸到多个资料收集器的环境中。大规模的实验显示直接套用现存TSP近似演算法处理EM-TSP问题是无法达到好的网路效能,而我们的机制是可以有效改善网路效能。
Data collection is an important mission in a wireless sensor networks (WSNs). Two critical issues, low latency and power saving, must be take into consideration while designing a data collection mechanism. The former is to collect sensing data as soon as possible, while the later is to conserve energy of sensors to prolong network lifetime. In this thesis, we consider different protocol layers to design data collection mechanisms for a WSN to achieve the both goals. This thesis is composed of three work. In the first work, we pay attention to the design of communication protocols in MAC layer. By exploiting controllable mobile nodes, the second work designs a distributed relocation protocol of mobile nodes to facilitate data relaying in a connected WSN, while the last work adopts mobile nodes to facilitate data collection in a disconnected WSN.

In the first work, we promote a novel interference model to design a ZigBee-compatible data collection MAC protocol. In a multi-hop wireless network, a conventional way of defining interference neighbors is to prohibit a node from using the same slot/code as those of its 1-hop and 2-hop neighbors. However, for data collection in a wireless sensor network, since the set of communication nodes is limited and the transmission directions are toward the sink, we show that a less strict set of interference neighbors can be defined. Based on this observation, we develop an efficient distributed wake-up scheduling scheme for data collection in a sensor network that achieves both low reporting latency and energy conservation.

As the sensing data is collected via a static WSN, an unbalanced energy consumption problem arises, where sensors closer to the sink are more likely to exhaust their energy faster than other nodes. To mitigate this problem, the second work considers a two-tiered wireless sensor and actor network (WSAN), where a set of resource-rich mobile nodes (termed actors) form a connected backbone to relay sensing data from static sensors to the sink. Such a two-tiered WSAN facilitates scalability and can efficiently reduce the energy consumption and latency incurred by conventional hop-by-hop relaying via only sensors. However, relocating actors from an initial random deployment to achieve both connectivity and load balance is a challenge, especially when there exists no location information of the nodes. Connectivity ensures that the actors are connected, while load balance ensures that actors collect and originate a similar amount of sensory data from the sensors. In this work, we formulate the Connected and Balanced Mobile Actor Relocation (CBMAR) optimization problem to address both connectivity and load balance and prove that the problem is NP-complete. We propose a dual-mode distributed actor relocation protocol that does not rely on any location information of actors or sensor nodes to relocate actors to meet the goals of connectivity and load balance. By maintaining a local view (termed covering cell), the protocol allows each actor to locally determine where it should move by using the lower-tiered topology of the sensors. Simulation results show that the protocol can achieve both objectives of connectivity and load balance with low moving and communication overheads.

While most research efforts focus on a connected WSN, the third work considers a spatially separated wireless sensor network (SS-WSN), which consists of a number of isolated subnetworks that could be far away from each other in distance. We address the issue of using mobile mules to collect data from these sensor nodes. In such an environment, both data collection latency and network lifetime are critical issues. We model this problem as a bi-objective problem, called energy-constrained mule traveling salesman problem (EM-TSP), which aims at minimizing the traversal paths of mobile mules such that at least one node in each subnetwork is visited by a mule and the maximum energy consumption among all sensor nodes does not exceed a pre-defined threshold. Interestingly, the traversal problem turns out to be a generalization of the classical traveling salesman problem (TSP), an NP-hard problem. Based on some geometrical properties of the network, we propose some efficient heuristics for EM-TSP. We then extend our heuristics to multiple mobile mules. Extensive simulation results are conducted to show that directly applying an efficient TSP approximation to EM-TSP does not guarantee good performance, while our proposed solutions give better performance.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT079455821
http://hdl.handle.net/11536/40926
显示于类别:Thesis