An energy-efficient,self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks

Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau’s algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption.     

A hierarchical approach to real-time activity recognition in body sensor networks

Real-time activity recognition in body sensor networks is an important and challenging task. In this paper, we propose a real-time, hierarchical model to recognize both simple gestures and complex activities using a wireless body sensor network. In this model, we first use a fast and lightweight algorithm to detect gestures at the sensor node level, and then propose a pattern based real-time algorithm to recognize complex, high-level activities at the portable device level. We evaluate our algorithms over a real-world dataset. The results show that the proposed system not only achieves good performance (an average utility of 0.81, an average accuracy of 82.87%, and an average real-time delay of 5.7 seconds), but also significantly reduces the network’s communication cost by 60.2%.     

A Hyper-Heuristic Framework for Lifetime Maximization in Wireless Sensor Networks With A Mobile Sink

Maximizing the lifetime of wireless sensor networks(WSNs) is an important and challenging research problem. Properly scheduling the movements of mobile sinks to balance the energy consumption of wireless sensor network is one of the most effective approaches to prolong the lifetime of wireless sensor networks. However, the existing mobile sink scheduling methods either require a great amount of computational time or lack effectiveness in finding high-quality scheduling solutions. To address the above issues, this paper proposes a novel hyperheuristic framework, which can automatically construct high-level heuristics to schedule the sink movements and prolong the network lifetime. In the proposed framework, a set of low-level heuristics are defined as building blocks to construct high-level heuristics and a set of random networks with different features are designed for training. Further, a genetic programming algorithm is adopted to automatically evolve promising high-level heuristics based on the building blocks and the training networks. By using the genetic programming to evolve more effective heuristics and applying these heuristics in a greedy scheme, our proposed hyper-heuristic framework can prolong the network lifetime competitively with other methods, with small time consumption. A series of comprehensive experiments, including both static and dynamic networks,are designed. The simulation results have demonstrated that the proposed method can offer a very promising performance in terms of network lifetime and response time.     

无线射频RFID识别协议自动验证方法研究

Population Protocols是一种受生物启发的计算模型,能够表示无线网络中数量庞大但计算能力弱的多组件间的交互,它为无线传感器网络提供了一种可计算推理的理论框架。将Population Protocol理论引入到RFID识别协议中,提出了RFID识别协议系统模型验证框架;构建了标签与阅读器交互产生的状态变迁模型;最后用spin模型检测工具和LTL线性时序逻辑验证了弱公平条件下该模型的自稳定性,为分析与验证无线传感器网络中协议的正确性提供了一种行之有效的方法。     

An agent-assisted QoS-based routing algorithm for wireless sensor networks

Existing routing algorithms are not effective in supporting the dynamic characteristics of wireless sensor networks (WSNs) and cannot ensure sufficient quality of service in WSN applications. This paper proposes a novel agent-assisted QoS-based routing algorithm for wireless sensor networks. In the proposed algorithm, the synthetic QoS of WSNs is chosen as the adaptive value of a Particle Swarm Optimization algorithm to improve the overall performance of network. Intelligent software agents are used to monitor changes in network topology, network communication flow, and each node's routing state. These agents can then participate in network routing and network maintenance. Experiment results show that the proposed algorithm can ensure better quality of service in wireless sensor networks compared with traditional algorithms.     

Robust self-stabilizing weight-based clustering algorithm

Ad hoc networks consist of wireless hosts that communicate with each other in the absence of a fixed infrastructure. Such networks cannot rely on centralized and organized network management. The clustering problem consists of partitioning network nodes into non-overlapping groups called clusters. Clusters give a hierarchical organization to the network that facilitates network management and that increases its scalability.In a weight-based clustering algorithm, the clusterheads are selected according to their weight (a node’s parameter). The higher the weight of a node, the more suitable this node is for the role of clusterhead. In ad hoc networks, the amount of bandwidth, memory space or battery power of a node could be used to determine weight values.A self-stabilizing algorithm, regardless of the initial system configuration, converges to legitimate configurations without external intervention. Due to this property, self-stabilizing algorithms tolerate transient faults and they are adaptive to any topology change.In this paper, we present a robust self-stabilizing weight-based clustering algorithm for ad hoc networks. The robustness property guarantees that, starting from an arbitrary configuration, after one asynchronous round, the network is partitioned into clusters. After that, the network stays partitioned during the convergence phase toward a legitimate configuration where the clusters verify the “ad hoc clustering properties”.     

一种改进的无线传感器网络非测距定位算法

节点定位是实现传感器网络应用的前提,控制节点定位误差成为保证网络正常运行的关键。采用基于测距的定位算法,可以达到良好的精度,但需要测量装置,不适合能量受限的无线传感器网络。本文分析了常用的非测距定位算法,并在此基础上提出了一种改进的基于序列的非测距定位算法,以提高无线传感器网络定位算法的性能。     

无线传感器网络中一种分布式冗余检测算法

无线传感器网络覆盖控制中现有的大部分冗余检测算法都是针对节点感知半径相同的同构网络的,无法应用于异构网络.提出一种保持网络k级覆盖的适应异构传感器网络的分布式冗余检测算法.该算法根据节点的冗余分布特性设计了有效覆盖邻居选取,通过有效覆盖邻居感知半径关系及交点处的覆盖程度判断检测冗余.仿真表明:算法中有效覆盖邻居选取的设计,大大降低了节点执行冗余计算的时间,算法的运行效率较高;算法在异构WSN中性能优异,冗余检测彻底、充分,有益于节省节点能量,延长网络生存时间.     

考虑干扰的无线传感器网络拓扑控制问题研究

无线传感器网络的拓扑控制是一个十分重要的技术问题。干扰对传感器网络应用产生了重要的影响,较大的传输干扰将导致信号的碰撞,增大网络延时间。但是,目前的大多数文献没有把干扰作为传感器网络拓扑控制的设计目标和考虑因素之一。本文研究考虑干扰的拓扑控制机制问题,根据传感器网络通信特点,设计了最优的集中式算法和适合合实际应用的次优分布式算法解决该问题。模拟实验结果表明,提出的算法与传统算法相比能有效减少网络干扰、节省能量消耗和减少网络延时,因此是一种新的高效的拓扑控制机制。     

无线传感器网络中覆盖控制技术综述

覆盖控制是无线传感器网络应用的一个基本问题,反映了网络所能提供的"感知"服务质量,可以使无线传感器网络的空间资源得到优化分配,进而更好地完成环境感知、信息获取和有效传输的任务;立足于无线传感器网络的覆盖控制问题,分析了网络覆盖技术在国内外研究的现状与发展,指出了传感器网络覆盖算法中需要解决的问题,并提出了将多目标进化算法与智能计算技术用于动态覆盖控制技术研究设想。     

一种ZigBee无线传感器网络拓扑发现算法

ZigBee无线传感器网络(WSN)不同于有线网络,由于无法直接观察到其网络结构和设备部署情况,因此不利于对ZigBee WSN进行管理和控制。为解决该问题,提出一种针对ZigBee WSN的拓扑发现算法(ZigBeeTopo),确定网络中的活跃节点以及节点之间的相互关系,设计WSN拓扑管理模块,实现ZigBee网络拓扑的可视化。测试结果表明,该算法能正确发现多种WSN拓扑。     

无线传感器网络连通性研究

为优化无线传感器网络的配置参数,减少网络拓扑结构变化次数,需对其组网算法和连通性问题进行研究。从概率论角度出发研究了网络参数之间的关系,在分析了节点连通度概率分布模型后,推导出了节点通信半径、节点个数、监测区域、连通度之间的关系,并在此基础上给出了一种连通性好且节能的无线传感器网络组网算法。通过仿真实验对算法进行验证,实验结果表明使用该方法组建的无线传感器网络连通性好,有很好的应用前景。     

基于混合量子进化算法的高效节能无线传感器网络路由算法

在无线传感器网络中,层次型路由算法能减少节点能量消耗和延长网络生存周期.因此在LEACH算法和PEGASIS算法的基础上,提出了一种基于混合量子进化算法的高效节能的无线传感器网络路由算法HERA.该算法中把网络分为多个簇,每个簇中的节点连接成为一条多跳通讯链路,并使用混合量子进化算法来得到最优的分簇组链方式,以减少链路...     

无线传感器网络中能量有效自适应路由算法研究

针对无线传感器网络寿命最大化问题,基于无线传感器节点能耗分布特点和数据传输能耗模型,建立无线传感器网络生存周期的数学优化模型,并针对最小能耗路由的能耗不均衡问题和能量均衡路由的能耗开销问题,综合考虑网络中节点的剩余能量和节点间发送数据的能耗,提出一个适合无线多跳传感器网络的自适应路由算法。仿真结果表明,提出的路由算法能充分地利用有限的能量资源,较大地延长网络生存周期。     

一种移动无线视频传感器节点的覆盖算法

在现有的无线传感器网络覆盖算法的研究中,缺乏对移动节点路径规划的研究,而针对具有视频传感器节点的网络仍使用普通传感器圆形覆盖区域的测量方法来计算覆盖面积,并不完全符合实际情况.基于这两方面的原因,本文提出了一种适用于无线视频传感器节点的最大覆盖算法,并提出一种对于视频传感器节点覆盖面积的计量方法.该算法能够使节点在保证网络连通性的前提下,达到最大的有效监测范围.此外,本文建立了相应的仿真实验模型,对该算法的有效性和覆盖面积进行了实验与分析.结果表明,本算法的节点监测面积大约为使用随机运动算法的节点监测面积的1.5倍左右,并可以保证网络的连通性.     

无线传感器网络中的定位技术研究

传感器网络是综合了传感器、嵌入式计算、网络及无线通信等技术的一种全新信息获取和处理技术。由于许多应用需要精确的定位,因此过去几年无线传感器网络定位技术得到广泛关注。研究了几种典型的定位技术,并根据距离误差、节点密度、anchor节点数量和所需设备等要求对各算法进行了性能分析、比较。最后总结了这些定位技术用于无线传感器网络中存在的问题,并提出了下一步工作的设想,即研究一个公共的三阶段的分布定位算法。     

无线传感器网络的链路稳定成簇与功率控制算法

在能量有限条件下通过降低能耗来延长网络生存时间是无线传感器网络面临的重要挑战之一。在层次体系结构中,MAC层和网络层的能耗是影响系统能量有效性的关键,因此可以将这两层结合起来考虑,从网络跨层优化的角度来分析其能耗。针对现有典型成簇算法理论前提条件多、无法适应网络动态变化、不易在实际环境中实现的不足,结合功率控制理论及算法,基于跨层优化的策略提出了一种易于实现、能动态适应网络变化、能量有效的链路稳定成簇算法。该算法能在降低能耗的同时扩大网络的吞吐量。实验仿真结果表明,与现有的几种典型方案相比,新算法在保证网络稳定性的同时使网络具有了更大的有效吞吐量及更长的生存时间。     

Low-complexity and energy efficient image compression scheme for wireless sensor networks

Currently most energy-constrained wireless sensor networks are designed with the object of minimizing the communication power at the cost of more computation. To achieve high compression efficiency, the main image compression algorithms used in wireless sensor networks are the high-complexity, state-of-the-art image compression standards, such as JPEG2000. These algorithms require complex hardware and make the energy consumption for computation comparable to communication energy dissipation. To reduce the hardware cost and the energy consumption of the sensor network, a low-complexity and energy efficient image compression scheme is proposed. The compression algorithm in the proposed scheme greatly lowers the computational complexity and reduces the required memory, while it still achieves required PSNR. The proposed implementation scheme of the image compression algorithm overcomes the computation and energy limitation of individual nodes by sharing the processing of tasks. And, it applies transmission range adjustment to save communication energy dissipation. Performance of the proposed scheme is investigated with respect to image quality and energy consumption. Simulation results show that it greatly prolongs the lifetime of the network under a specific image quality requirement.     

The minimum positional error incurred by any connectivity-based positioning algorithm for mobile wireless systems

A very important problem in many wireless ad-hoc networks, including wireless sensor networks, is positioning or the determination of geographical locations of the wireless nodes. Positioning is used both in infrastructural aspects of sensor networks, like geographic routing and topology maintenance, and in applications like wildlife tracking. Connectivity-based positioning algorithms in mobile wireless systems are studied in this work. These algorithms compute node positions based only on the connectivity, i.e. the neighborhood information of each node. Many algorithms have been proposed for positioning in stationary node systems and bounds on positional error of algorithms have been derived. The design and analysis of positioning algorithms for mobile node systems is a more challenging problem. Node mobility increases the amount of positional information available to a positioning algorithm. The work in this paper establishes a bound on the positional error for connectivity-based algorithms in mobile systems. The formulation from the analysis is used to investigate the benefit of this additional positional information on reducing positional error. There is a limit to the usefulness of positional information from previous node positions due to movement. This captures an important performance tradeoff: historical positional information can yield reduced positional error but requires more connectivity information from the network which requires greater computational resources.     

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。