信息物理融合系统中最小延迟数据聚集调度算法综述

数据聚集调度问题研究sink节点如何能够无冲突地获取整个网络的汇总信息,是信息物理融合系统中一个非常重要的服务.在数据聚集调度问题中,聚集延迟是指整个网络中最后一个数据包到达sink节点的时间.最小延迟聚集调度问题则寻求一个快速无冲突的调度来最小化聚集延迟.在节点一直醒着的网络中,考虑到整个网络的大小和数据传输中的干扰问题,最小延迟聚集调度问题被证明为NP-难问题.另外,当网络中的节点采用低占空比模式来节省能耗时,由于节点只能在其处于活动状态时接受数据,最小延迟聚集调度问题变得更加复杂.近年来最小延迟聚集调度问题得到了大量的关注,本文将对该问题研究所取得的进展进行综述.     

最小化延迟的无线传感器网络节点调度算法

如何实现节能和减小延迟一直是无线传感器网络中研究的热点及难点问题。提出一种新的最小化延迟的能量均衡的节点调度（MDS）算法,算法通过对能量以及延迟的分析计算,计算出节点的能量判定阈值,并在选择下一跳的时候,总是选择节点剩余能量在限定范围内且延迟最小的节点,以此实现最小化网络延迟的目的。理论分析及实验结果表明,MDS算法能够较好地把网络的生命周期控制在可接受范围内,同时可以解决在能耗限定条件下的最小化延迟的问题。     

基于多目标的MIMO无线mesh网络信道优化策略

MIMO是一种可有效提高无线网络信道带宽的技术。将MIMO技术应用在无线mesh网络中会遇到信道干扰和无线节点之间无协同策略等问题,导致网络效率降低。基于无线mesh网络中节点的多属性特征,以节点属性和内容分发为约束,提出了基于多目标优化算法与多层分发联合的调度和优化策略。实验结果表明,该算法能有效降低无线mesh网络分发数据过程中的时延,提高网络的吞吐表现和服务质量。     

无线传感器网络的通信调度算法研究综述

通信调度是无线传感器网络中最基础且重要的问题之一,决定了无线传感器网络的可行性及性能,因此引起了国内外学者的广泛关注.通过对网络中传感器节点的调度,使其高效协作地完成网络中的监测、计算等任务.主要包括广播调度问题、数据收集调度问题、以及数据聚集调度问题.本文对现有无线传感器网的通信调度算法进行了性能比较分析.     

无线传感器网络中基于遗传算法的覆盖优化

覆盖控制是廷长无线传感器网络生存期一个有效的方法之一.其方法通过覆盖控制将无线传感网络节点划分成若干不相交最小覆盖连通集(CCS),然后顺序调度不同节点集.然而寻找最小覆盖连通集覆盖为NP问题,文中建立覆盖连通集优化模型,提出一种基于遗传算法(Genetic Algorithm,简称GA)目标覆盖的优化算法,并详细阐述算法实施.仿真结果显示,对于指定目标,该GA优化算法能获得比GIECC算法更好的性能.     

基于无线传感器网络的业务流调度算法

实时性要求是无线传感器网络调度算法性能评价的重要内容。对于实时性要求很高的应用场合,调度算法的首要标准是降低数据包的传输时延。针对无线传感器网络的业务流调度问题,结合传统的加权循环调度算法WRR,着眼于解决无线传感器网络中业务流突发引起的时延性能下降问题,提出了新的调度算法-WSWRR。新算法合理分配传感器节点的数据感知和传输时间,使节点在不需要工作时转入低功耗的休眠模式,且能在满足应用要求服务质量的前提下,高效利用节点能量,延长整个传感器网络的生命周期。通过仿真实验,验证了新算法在调度突发数据包时性能得到了很好的改善,且没有增加网络的整体能耗,证明了WSWRR算法的有效性。     

无线传感器网络高精度时间同步机制

无线传感器网络中,发送节点和接收节点间的延时包括发送延迟、访问延迟、传输延迟、传播延迟、接收延迟和接收处理延迟。传统的泛洪式时间同步算法在传感器节点上实现时一般选择在MAC层打时标来避免发送延迟和接收处理延迟。但是由于CC2530节点在发送消息前会进行空闲信道评估,那么信道的访问延迟是不能忽略的。文中提出了一种基于SFD硬件捕获机制的泛洪式时间同步机制,该同步机制避免了访问延迟对时间同步精度的影响,使同步精度保持在微秒级。     

认知无线传感器网络中基于GSC的协作传输机制

针对无线传感器网络中单个节点能量和发射功率均受限的特点,在发送端已知信道状态信息(CSI)的条件下提出了一种基于广义选择合并算法(GSC)的协作传输机制。根据GSC算法和节点的功率受限条件来决定具体参与协作传输的节点个数,并结合信道状态和节点的剩余能量来对节点进行调度。理论分析和仿真结果表明该机制能够有效地延长网络寿命。     

基于首要信道的无线认知传感器网络多信道广播协议

针对无线认知传感器网络的资源有限性和频谱动态分配,提出了基于首要信道半双工的无线认知传感器网络广播协议。在没有公共信道和时钟同步的情况下,该协议通过单个收发机的收发状态转换和信道表的交换进行网络的初始化。经过网络初始化,节点由首要信道形成拓扑,节点通过首要信道以半双工数据传送方式进行广播。仿真实验表明,与完全广播相比,该协议降低了广播延迟和开销,更利于应用于无线认知传感器网络。     

基于节点密度的混合式多信道分配算法

为了减小无线传感器网络中的同频干扰和避免网络堵塞问题,文章提出了一种基于节点密度的混合式多信道分配算法。该算法通过考虑链路干扰以及节点密度等因素,来解决局部严重同频干扰问题,实现各信道负载均衡,减少网络阻塞。仿真实验结果分析表明,该算法能有效地解决网络中同频干扰问题,较好地均衡各信道的网络负载,在数据业务较重的情况下,网络性能仍比较良好。     

TDMA scheduling algorithms for wireless sensor networks

Algorithms for scheduling TDMA transmissions in multi-hop networks usually determine the smallest length conflict-free assignment of slots in which each link or node is activated at least once. This is based on the assumption that there are many independent point-to-point flows in the network. In sensor networks however often data are transferred from the sensor nodes to a few central data collectors. The scheduling problem is therefore to determine the smallest length conflict-free assignment of slots during which the packets generated at each node reach their destination. The conflicting node transmissions are determined based on an interference graph, which may be different from connectivity graph due to the broadcast nature of wireless transmissions. We show that this problem is NP-complete. We first propose two centralized heuristic algorithms: one based on direct scheduling of the nodes or node-based scheduling, which is adapted from classical multi-hop scheduling algorithms for general ad hoc networks, and the other based on scheduling the levels in the routing tree before scheduling the nodes or level-based scheduling, which is a novel scheduling algorithm for many-to-one communication in sensor networks. The performance of these algorithms depends on the distribution of the nodes across the levels. We then propose a distributed algorithm based on the distributed coloring of the nodes, that increases the delay by a factor of 10–70 over centralized algorithms for 1000 nodes. We also obtain upper bound for these schedules as a function of the total number of packets generated in the network.     

Data Association Coverage Algorithm Based on Energy Balance and Controlled Parameters in Wireless Sensor Networks

Based on a position-independent and computationally simple node scheduling algorithm, a scheduling algorithm based on energy balance is proposed. The analysis and simulation results showed that the algorithm can extend the lifespan of the entire network whereas ensuring energy balance. Data aggregation was a relatively time-consuming operation in sensor networks, especially in high-density networks. Therefore, minimizing the problem of data aggregation delay had become a hot topic of research. The algorithm adopted a clustering idea of low power in the cluster and high power between clusters, combined with channel allocation to reduce data aggregation delay, and data aggregation between clusters can be performed without collisions. The number of channels used in different network topologies tends to be constant.

     

Efficient sequencing techniques for variable-length messages in WDMnetworks

Message sequencing and channel assignment are two important issues that need to be addressed when scheduling variable-length messages in a wavelength division multiplexing (WDM) network. Channel assignment addresses the problem of choosing an appropriate data channel via which a message is transmitted to a node. This problem has been addressed extensively in the literature. On the other hand, message sequencing which addresses the order in which messages are sent, has rarely been addressed. In this paper, we propose a set of scheduling techniques for single-hop WDM passive star networks, which address both the sequencing aspect and the assignment aspect of the problem. In particular, we develop two priority schemes for sequencing messages in a WDM network in order to increase the overall performance of the network. We evaluate the proposed algorithms, using analytical modeling and extensive discrete event simulations, by comparing their performance with state-of-the-art scheduling algorithms that only address the assignment problem. We find that significant improvement in performance can be achieved using our scheduling algorithms where message sequencing and channel assignment are simultaneously taken into consideration. This suggests that, when scheduling messages in WDM networks, one has to consider message sequencing, as well as channel assignment. As a result, we anticipate that this research will open new directions into the problem of on-line scheduling in WDM networks     

Interference‐aware convergecast scheduling in wireless sensor/actuator networks for active airflow control applications

Emerging wireless sensor/actuator network (WSAN) technology has the potential to enable semi‐autonomous airflow control to improve the aerodynamic performance of aircraft. In this paper, a WSAN comprising of multiple linear sensor clusters terminated by actuators is proposed for active airflow control with the objective of minimizing convergecast latency. Here, the convergecast delay is defined as the time required from the beginning of a sampling period to all all sensor's data of this sampling period is received by the actuator. The objective is achieved by minimizing the separation distance of concurrent data transmission so that the number of nodes sending data in the same time slot is maximized. The problem turns into a scheduling problem with a proper selection of interference separation. However, most existing work on the scheduling in linear networks use the minimum separation of two hops to avoid collisions. This paper examines the relationship between the hop separation, signal‐to‐noise ratio, and the latency to make a selection of interference separation. A new interference aware hybrid line scheduling (HLS) algorithm is proposed and its energy consumption is analyzed. Compared with other line scheduling policies, the analysis and simulation results show that, at moderately high node densities, the proposed HLS with carefully selected hop separation is able to reduce both the delay by up to 15% and the energy consumption somehow. Copyright © 2012 John Wiley & Sons, Ltd.     

Near optimal scheduling of data aggregation in wireless sensor networks

Due to the large-scale ad hoc deployments and wireless interference, data aggregation is a fundamental but time consuming task in wireless sensor networks. This paper focuses on the latency of data aggregation. Previously, it has been proved that the problem of minimizing the latency of data aggregation is NP-hard [1]. Many approximate algorithms have been proposed to address this issue. Using maximum independent set and first-fit algorithms, in this study we design a scheduling algorithm, Peony-tree-based Data Aggregation (PDA), which has a latency bound of 15R + Δ ? 15, where R is the network radius (measured in hops) and Δ is the maximum node degree. We theoretically analyze the performance of PDA based on different network models, and further evaluate it through extensive simulations. Both the analytical and simulation results demonstrate the advantages of PDA over the state-of-art algorithm in [2], which has a latency bound of 23R + Δ ? 18.     

FrogSim: distributed graph coloring in wireless ad hoc networks

Graph coloring, which is at the heart of several problems arising in wireless ad hoc networks, concerns the problem of assigning colors to the nodes of a graph such that adjacent nodes do not share the same color. This paper deals with the problem of generating valid colorings in a distributed way, while minimizing the number of colors used. Examples of related problems in wireless ad hoc networks are TDMA slot assignment, wakeup scheduling, and data collection. The presented algorithm is inspired by the desynchronization observed in the context of the calling behaviour of male Japanese tree frogs. Experimental results indicate that the proposed algorithm is very competitive with current state-of-the-art approaches.     

Distributed Topology Construction in ZigBee Wireless Networks

Topology control is one of the important techniques in wireless multi-hop networks to preserve connectivity and extend the network lifetime. This is more significant in ZigBee, since the address assignment scheme is tightly coupled with topology construction. For example, there can be orphan nodes that cannot receive the network address and isolated from the network due to predefined network configurations. In this paper, we propose a distributed topology construction algorithm that controls the association time of each node in order to solve the orphan node problem in ZigBee as well as construct an efficient routing tree topology. The main idea of the distributed topology construction algorithm is to construct primary backbone nodes by propagating the invitation packets and controlling the association time based on the link quality. Since the dynamically selected primary nodes are spread throughout the network, they can provide backbone to accept the association requests from the remaining secondary nodes which are majority in a network. In the performance evaluation, we show that the proposed topology construction algorithm effectively solves the orphan node problem regardless of network density as well as provides efficient tree routing cost comparable to the approximation algorithm for degree constrained minimum routing cost tree (DC-MRCT) problem.     

Large-Scale Network Topological Optimization

A cost-effective structure for a large network is a multilevel hierarchy consisting of a backbone network and a family of local access networks. The backbone network is generally a distributed network, while the local access networks are typically centralized systems. In special cases, the network may consist primarily of either centralized or distributed portions. This paper discusses topological design problems for such systems, including the concentrator location problem, the terminal assignment problem, the terminal layout problem (the constrained minimum spanning tree problem), the distributed network topological layout problem, and the backbone node location problem. Recent algorithm research, including exact and heuristic problem solutions, are described and computational experience is given. Finally, open problems in large-scale topological design are reported.     

基于二次独立集的数据融合调度算法简

针对无线传感器网络数据融合中服务质量与加权公平性保证问题,提出了一种基于二次独立集的数据融合调度算法MISS。该算法采用时分复用思想,通过2次构造最大独立集实现对加权数据的无冲突调度。首先构建以最大独立集为基础的树型结构,并根据能量消耗预测进行调整形成最终的数据融合平衡树;然后通过优化调度对象集合,利用近似最大加权独立集为允许通信的链路分配传输时隙。实验结果表明,该算法能够在降低融合时延、加权公平性保证以及延长网络生命周期等方面实现性能平衡。