Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of ω(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of ?(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.     

Sleep scheduling with expected common coverage in wireless sensor networks

Sleep scheduling, which is putting some sensor nodes into sleep mode without harming network functionality, is a common method to reduce energy consumption in dense wireless sensor networks. This paper proposes a distributed and energy efficient sleep scheduling and routing scheme that can be used to extend the lifetime of a sensor network while maintaining a user defined coverage and connectivity. The scheme can activate and deactivate the three basic units of a sensor node (sensing, processing, and communication units) independently. The paper also provides a probabilistic method to estimate how much the sensing area of a node is covered by other active nodes in its neighborhood. The method is utilized by the proposed scheduling and routing scheme to reduce the control message overhead while deciding the next modes (full-active, semi-active, inactive/sleeping) of sensor nodes. We evaluated our estimation method and scheduling scheme via simulation experiments and compared our scheme also with another scheme. The results validate our probabilistic method for coverage estimation and show that our sleep scheduling and routing scheme can significantly increase the network lifetime while keeping the message complexity low and preserving both connectivity and coverage.     

Distributed lifetime optimization in wireless sensor networks using alternating direction method of multipliers

Due to the limited energy of sensor nodes in wireless sensor networks, extending the network lifetime is a major challenge that can be formulated as an optimization problem. In this paper, we propose a distributed iterative algorithm based on alternating direction method of multipliers with the aim of maximizing sensor network lifetime. The features of this algorithm are the use of local information, low overhead of message passing, low computational complexity, fast convergence, and, consequently, reduced energy consumption. In this study, we present the convergence results and the number of iterations required to achieve the stopping criterion. Furthermore, the impact of problem size (number of sensor nodes) on the solution and constraints violation is studied, and, finally, the proposed algorithm is compared with one of the well‐known subgradient‐based algorithms.     

Media Synchronization and QoS Packet Scheduling Algorithms for Wireless Systems

Wireless multimedia synchronization is concerned with distributed multimedia packets such as video, audio, text and graphics being played-out onto the mobile clients via a base station (BS) that services the mobile client with the multimedia packets. Our focus is on improving the Quality of Service (QoS) of the mobile client's on-time-arrival of distributed multimedia packets through network multimedia synchronization. We describe a media synchronization scheme for wireless networks, and we investigate the multimedia packet scheduling algorithms at the base station to accomplish our goal. In this paper, we extend the media synchronization algorithm by investigating four packet scheduling algorithms: First-In-First-Out (FIFO), Highest-Priority-First (PQ), Weighted Fair-Queuing (WFQ) and Round-Robin (RR). We analyze the effect of the four packet scheduling algorithms in terms of multimedia packet delivery time and the delay between concurrent multimedia data streams. We show that the play-out of multimedia units on the mobile clients by the base station plays an important role in enhancing the mobile client's quality of service in terms of intra-stream synchronization and inter-stream synchronization. Our results show that the Round-Robin (RR) packet scheduling algorithm is, by far, the best of the four packet scheduling algorithms in terms of mobile client buffer usage. We analyze the four packet scheduling algorithms and make a correlation between play-out of multimedia packets, by the base station, onto the mobile clients and wireless network multimedia synchronization. We clarify the meaning of buffer usage, buffer overflow, buffer underflow, message complexity and multimedia packet delay in terms of synchronization between distributed multimedia servers, base stations and mobile clients.     

E2DTS: An energy efficiency distributed time synchronization algorithm for underwater acoustic mobile sensor networks

Time synchronization plays an important role in wireless sensor network applications and energy conservation. In this paper, we focus on the need of time synchronization in underwater acoustic mobile sensor networks (UAMSNs). Several time synchronization algorithms have been carried out in this issue. But most of them are proposed for RF-based wireless sensor networks, which assume that the propagation delay is negligible. In UAMSNs, the assumption about rapid communication is incorrect because the communication is primarily via acoustic channel, so the propagation speed is much slower than RF. Furthermore, the propagation delay in underwater environment is time-varying due to the nodes’ mobility. We present an energy efficiency distributed time synchronization algorithm (called “E²DTS”) for those underwater acoustic node mobility networks. In E²DTS, both clock skew and offset are estimated. We investigate the relationship between time-varying propagation delay and nodes mobility, and then estimate the clock skew. At last skew-corrected nodes send local timestamp to beacon node to estimate its clock offset. Through analysis and simulation, we show that it achieves high level time synchronization precision with minimal energy cost.     

分布式声探测无线网络时间同步算法研究

分布式声探测无线网络是一种基于声达时间差(TDOA)进行目标定位的无线传感器网络;而基于TDOA算法的分布式定位需要节点之间严格时间同步,本文正是对节点之间严格时间同步进行了重点研究.文中系统分析了分布式声探测无线网络的应用环境、工作机制和硬件平台,在此基础上提出节点之间的采样同步和全网同步问题,并基于后同步思想和分级同步机制,设计了分布式声探测无线网络节点同步的整体解决方案.该方案已经进行了组网测试,有效解决了分布式身探测的时间同步问题.本文对相关工程实践具有一定的指导意义.     

无线传感器网络二阶一致性时间同步

考虑到在无线传感器网络中,新节点的加入或老节点的死亡均会导致拓扑呈动态变化,该文研究一种完全分布式二阶一致性时间同步(Second-Order Consensus Time Synchronization, SOCTS)算法。将节点的时钟特性建模成二阶状态方程,按照伪同步周期广播节点的本地虚拟时间,根据邻居节点的本地虚拟时间的不一致来构造同步控制输入;通过坐标变换将网络的一致性时间同步问题转化为变换系统的稳定性问题,理论分析了SOCTS算法的收敛性和收敛条件,并研究了影响SOCTS算法收敛速度的因素。通过数值仿真实验验证了所提方法的有效性。     

邻近信息约束下的随机异构无线传感器网络节点调度算法

针对高密度部署的随机异构传感器网络内部存在的覆盖冗余问题,该文提出一种随机异构无线传感器网络的节点调度算法(NSSH)。在网络原型拓扑的支撑下构建Delaunary三角剖分,规划出节点进行本地化调度的局部工作子集。通过折中与邻近节点的空外接圆半径,完成对感知半径的独立配置;引入几何线、面概念,利用重叠面积和有效约束圆弧完成对灰、黑色节点的分类识别,使得节点仅依赖本地及邻居信息进行半径调整和冗余休眠。仿真结果表明,NSSH能以低复杂度的代价,近似追平贪婪算法的去冗余性能,并表现出了对网络规模、异构跨度和参数配置的低敏感性。     

基于无线传感器网络汇聚传输实时性的分布式调度算法

在无线传感器网络多种应用中,各节点需要在短时间内将采集的数据传输至汇聚节点,从而形成多对一的汇聚传输。针对网络汇聚传输的实时性,提出了一种分布式的节点传输调度算法。各节点只需要根据一跳范围内的邻居信息进行传输调度。仿真和分析表明该算法可以有效避免数据碰撞,并使得完成一次全网数据收集所需要的时隙数基本在网络节点总数的1.6到1.8倍左右,比目前其他调度算法在实时性和复杂度方面更具有优势。     

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.     

ZigBee信标同步算法设计与仿真

由于受到时钟准确性和精度要求的影响,传统网络中的时间同步算法已经不能满足无线传感器网络的要求.根据ZigBee郊术的特点,研究了基于CSMA-CA机制的具有针对性的信标同步算法.给出了相应的算法分析、算法流程,以及在NS2平台中的仿真结果与性能分析,同时给出了在信标网络与非信标网络中的效果对比.     

一种低功耗的多跳无线传感网时间同步算法

高精度低功耗的时间同步对于无线传感网络至关重要,文中重点分析了高精度时间同步算法,发现其在多跳网络时间同步过程中由于每跳范围内所有节点均要广播时间同步包,会产生大量的冗余信息。为降低同步功耗,提出了一种新方法,通过调节发射功率,筛选出每一跳范围内的周边节点,使其完成下一跳范围的时间同步,而非周边节点只接受却不发送时间同步包。最后,针对改进的算法在OMNet++上进行了仿真实验,仿真结果表明,改进后的算法能够有效地降低全网能量消耗。     

A Coverage-Based Scheduling Algorithm for WSNs

Node scheduling in wireless sensor networks (WSNs) plays a vital role in conserving energy and lengthening the lifetime of networks, which are considered as prime design challenges. In large-scaled WSNs, especially where sensor nodes are deployed randomly, 100 % coverage is not possible all the times. Additionally, several types of applications of WSNs do not require 100 % coverage. Following these facts, in this paper, we propose a coverage based node scheduling algorithm. The algorithm shows that by sacrificing a little amount of coverage, a huge amount of energy can be saved. This, in turns, helps to increase the lifetime of the network. We provide mathematical analysis, which verifies the correctness of the proposed algorithm. The proposed algorithm ensures balanced energy consumption over the sensor networks. Moreover, simulation results demonstrate that the proposed algorithm almost doubles the lifetime of a wireless sensor network by sacrificing only 5–8 % of coverage.     

Mobility aided localization of wireless sensor networks with inaccurate range measurements

This paper studies the relationship between mobility, navigation and localization in the context of wireless sensor networks with mobile beacons. It is observed that mobility can aid in network node localization and that once localized, the network nodes can localize and track a mobile object and guide its navigation. A distributed kernel-based algorithm is proposed that enables the nodes to establish confident position estimates in the presence of ranging inaccuracies. The proposed approach features robustness with respect to range measurement inaccuracies, low complexity and distributed implementation, using only local information. Simulation validates our approach viable.     

基于ZigBee节点的按需时间同步算法

简要阐述近年来无线传感网络时间同步（TPSN）算法的发展概况和影响无线传感器网络时间同步的因素,结合无线传感网络中路由节点与终端节点的特点,提出一种融合了参考广播同步（RBS）与TPSN算法设计,在保持同步精确度前提下,整个网络的功耗大大降低。通过实验采集到的数据分析了协议的可行性,证明该算法较适合于对节点密度高,终端节点较多的无线网络中,如工业有害气体的检测。     

Coherent acoustic array processing and localization on wireless sensor networks

Advances in microelectronics, array processing, and wireless networking have motivated the analysis and design of low-cost integrated sensing, computing, and communicating nodes capable of performing various demanding collaborative space-time processing tasks. In this paper, we consider the problem of coherent acoustic sensor array processing and localization on distributed wireless sensor networks. We first introduce some basic concepts of beamforming and localization for wide-band acoustic sources. A review of various known localization algorithms based on time-delay followed by least-squares estimations as well as the maximum-likelihood method is given. Issues related to practical implementation of coherent array processing, including the need for fine-grain time synchronization, are discussed. Then we describe the implementation of a Linux-based wireless networked acoustic sensor array testbed, utilizing commercially available iPAQs with built-in microphones, codecs, and microprocessors, plus wireless Ethernet cards, to perform acoustic source localization. Various field-measured results using two localization algorithms show the effectiveness of the proposed testbed. An extensive list of references related to this work is also included.     

Self-coordinating localized fair queueing in wireless ad hoc networks

Distributed fair queueing in a multihop, wireless ad hoc network is challenging for several reasons. First, the wireless channel is shared among multiple contending nodes in a spatial locality. Location-dependent channel contention complicates the fairness notion. Second, the sender of a flow does not have explicit information regarding the contending flows originated from other nodes. Fair queueing over ad hoc networks is a distributed scheduling problem by nature. Finally, the wireless channel capacity is a scarce resource. Spatial channel reuse, i.e., simultaneous transmissions of flows that do not interfere with each other, should be encouraged whenever possible. In this paper, we reexamine the fairness notion in an ad hoc network using a graph-theoretic formulation and extract the fairness requirements that an ad hoc fair queueing algorithm should possess. To meet these requirements, we propose maximize-local-minimum fair queueing (MLM-FQ), a novel distributed packet scheduling algorithm where local schedulers self-coordinate their scheduling decisions and collectively achieve fair bandwidth sharing. We then propose enhanced MLM-FQ (EMLM-FQ) to further improve the spatial channel reuse and limit the impact of inaccurate scheduling information resulted from collisions. EMLM-FQ achieves statistical short-term throughput and delay bounds over the shared wireless channel. Analysis and extensive simulations confirm the effectiveness and efficiency of our self-coordinating localized design in providing global fair channel access in wireless ad hoc networks.     

A Tracking-Based Target Locating Algorithm in Wireless Sensor Networks

1　IntroductionAwirelesssensornetworkisusuallycomposedofhundredsorthousandsofsensorsequippedwithcomputation ,sensingandcommunicationdevices,whicharecoordinatedinadistributedmodeinordertomonitoracertaingeographicalregionandcollectinformationontheirsurroundings[1 ] .Thecollecteddataisthenusedtoanswervariousqueries.RecentadvancesinMEMS ,wirelesscommunications,anddigitalelectronicshavemadepossiblethecheapandfastdeploymentofsensornetworks[2 ] .Suchadhoc,self organizingsensornetworksarereceivingin…     

A Power-Efficient Distributed TDMA Scheduling Algorithm with Distance-Measurement for Wireless Sensor Networks

This paper describes a power-efficient distributed TDMA slot scheduling algorithm which the slot allocation priority is controlled by distance measurement information in details. In our former proposed scheme, L-DRAND+, an extension of Lamport’s bakery algorithm for prioritized slot allocation based on the distance measurement information between nodes and a packet-based transmission power control had been applied. In this paper, we propose its enhanced scheme with a weighted rule control and state machines refinements of L-DRAND+, named L-DRAND++. This aims at the achievement of media access control methods which can construct a local wireless network practically by limiting the scope, and eliminate the redundant power consumption in the network. The proposed scheme can be shown as a possible replacement of DRAND algorithm for Z-MAC scheme in a distance-measurement-oriented manner. In addition, to evaluate the ordered node sequence determined by the algorithm, node sequence metric is proposed. By using the metric, we can evaluate protocol behaviors according to the environmental situation around the node.     

Optimal backpressure routing for wireless networks with multi-receiver diversity

We consider the problem of optimal scheduling and routing in an ad-hoc wireless network with multiple traffic streams and time varying channel reliability. Each packet transmission can be overheard by a subset of receiver nodes, with a transmission success probability that may vary from receiver to receiver and may also vary with time. We develop a simple backpressure routing algorithm that maximizes network throughput and expends an average power that can be pushed arbitrarily close to the minimum average power required for network stability, with a corresponding tradeoff in network delay. When channels are orthogonal, the algorithm can be implemented in a distributed manner using only local link error probability information, and supports a “blind transmission” mode (where error probabilities are not required) in special cases when the power metric is neglected and when there is only a single destination for all traffic streams. For networks with general inter-channel interference, we present a distributed algorithm with constant-factor optimality guarantees.