A new distributed approximation algorithm for constructing minimum connected dominating set in wireless ad hoc networks

In recent years, constructing a virtual backbone by nodes in a connected dominating set (CDS) has been proposed to improve the performance of ad hoc wireless networks. In general, a dominating set satisfies that every vertex in the graph is either in the set or adjacent to a vertex in the set. A CDS is a dominating set that also induces a connected sub‐graph. However, finding the minimum connected dominating set (MCDS) is a well‐known NP‐hard problem in graph theory. Approximation algorithms for MCDS have been proposed in the literature. Most of these algorithms suffer from a poor approximation ratio, and from high time complexity and message complexity. In this paper, we present a new distributed approximation algorithm that constructs a MCDS for wireless ad hoc networks based on a maximal independent set (MIS). Our algorithm, which is fully localized, has a constant approximation ratio, and O(n) time and O(n) message complexity. In this algorithm, each node only requires the knowledge of its one‐hop neighbours and there is only one shortest path connecting two dominators that are at most three hops away. We not only give theoretical performance analysis for our algorithm, but also conduct extensive simulation to compare our algorithm with other algorithms in the literature. Simulation results and theoretical analysis show that our algorithm has better efficiency and performance than others. Copyright © 2005 John Wiley & Sons, Ltd.     

Greedy construction of load‐balanced virtual backbones in wireless sensor networks

Inspired by the backbone concept in wired networks, a virtual backbone is expected to bring substantial benefits to routing in wireless sensor networks (WSNs). A connected dominating set (CDS) is used as a virtual backbone for efficient routing and broadcasting in WSNs. Most existing works focus on constructing a minimum CDS, a k‐connect m‐dominating CDS, a minimum routing cost CDS, or a bounded‐diameter CDS. However, the load‐balance factor is not considered for CDSs in WSNs. In this paper, a greedy‐based approximation algorithm is proposed to construct load‐balanced CDS in a WSN. More importantly, we propose a new problem: the Load‐balanced Allocate Dominatee problem. Consequently, we propose an optimal centralized algorithm and an efficient probability‐based distributed algorithm to solve the Load‐balanced Allocate Dominatee problem. For a given CDS, the upper and lower bounds of the performance ratio of the distributed algorithm are analyzed in the paper. Through extensive simulations, we demonstrate that our proposed methods extend network lifetime by up to 80% compared with the most recently published CDS construction algorithm. Copyright © 2012 John Wiley & Sons, Ltd.     

An energy‐efficient node‐scheduling scheme for wireless sensor networks based on minimum dominating sets

One of the major requirements for new wireless sensor networks is to extend the lifetime of the network. Node‐scheduling techniques have been used extensively for this purpose. Some existing approaches rely mainly on location information through global positioning system (GPS) devices for designing efficient scheduling strategies. However, integration of GPS devices with sensor nodes is expensive and increases the cost of deployment dramatically. In this paper we present a location‐free solution for node scheduling. Our scheme is based on a graph theoretical approach using minimum dominating sets. We propose a heuristic to extract a collection of dominating sets. Each set consists of a group of working nodes which ensures a high level of network coverage. At each round, one set is responsible for covering the sensor field while the nodes in other sets are in sleep mode. We evaluate our solution through simulations and discuss our future research directions. Copyright © 2008 John Wiley & Sons, Ltd.     

用马尔科夫模型优化分布式最小连通支配集算法

 为了提高无线传感器网络(WSNs)的能量利用效率、延长网络的生存时间,对基于极大独立集的最小连通支配集算法(MISB)进行优化,提出了一种新的算法.本文首先应用离散马尔科夫链为节点建立模型,并且根据模型预测节点的能量消耗;本算法进行多轮选举,每一轮开始时根据节点的度和能量选举支配点,依据模型预测的能量消耗决定本轮的运行时间,本轮运行结束时从新选举支配点,开始新一轮.仿真结果表明,本算法和原算法相比可以更好地平衡网络的能量消耗,提高全网的能量利用率,极大地延长网络的生存时间.     

Energy-Efficient Routing Protocol for Wireless Sensor Networks with Static Clustering and Dynamic Structure

Data gathering is an essential operation in wireless sensor networks. For periodic data gathering applications, each sensor node has data that must be sent to a distant base station in a round of communication. Due to the limited battery power of sensor nodes, each sensor node transmitting its sensed data to the base station directly significantly consumes its energy. This work presents a hierarchical ring-based data gathering (HRDG) scheme for dense wireless sensor networks. A hierarchical grid structure is constructed, and only some sensor nodes are elected as grid heads for gathering data, subsequently reducing the total energy consumption per round. Grid heads are then organized into hierarchical rings to decrease the transmission delay of a round. The proposed HRDG scheme focuses on reducing the energy × delay cost in a round of data gathering. Moreover, the energy × delay cost of HRDG is analyzed. Simulation results indicate that the proposed HRDG scheme outperforms other data gathering schemes in terms of the number of rounds, the energy × delay cost and coverage ratio.     

A Distributed Query Protocol in Wireless Sensor Networks

In wireless sensor networks, query execution over a specific geographical region is an essential function for collecting sensed data. However, sensor nodes deployed in sensor networks have limited battery power. Hence, the minimum number of connected sensor nodes that covers the queried region in a sensor network must be determined. This paper proposes an efficient distributed protocol to find a subset of connected sensor nodes to cover the queried region. Each node determines whether to be a sensing node to sense the queried region according to its priority. The proposed protocol can efficiently construct a subset of connected sensing nodes and respond the query request to the sink node. In addition, the proposed protocol is extended to solve the k-coverage request. Simulation results show that our protocol is more efficient and has a lower communication overhead than the existing protocol.     

Connected dominating sets in disk graphs with bidirectional links

In this paper, we study the connected dominating set (CDS) problem in disk graphs. The CDS problem has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in unit disk graphs, in which each node has the same transmission range. However, in wireless ad hoc networks, the transmission ranges of all nodes are not necessary equal. In this paper, we introduce the CDS problem in disk graphs and present a constant approximation algorithm which can be implemented as a distributed algorithm.     

时延和能耗均衡的强连通支配集构造算法

针对无线传感器网络中链路的非对称性,提出时延约束的强连通支配树(SDTT,strongly connected dominating tree with bounded transmission delay)问题,给出在有向图上构建传输时延和能量消耗均衡的强连通支配集的强连通支配树(SCDT,distributed strongly connected dominating tree)算法。首先在单位圆图(UDG)模型的基础上构建极大独立集(MIS),然后在具有双向权值的有向图上基于最小支撑树和最短路径树实现分布式SCDT算法,同时满足时延和能耗均衡的约束条件要求。理论算例分析和仿真结果表明提出的算法能有效地解决SDTT问题,构造联合约束的强连通支配集,形成时延和能耗均衡的虚拟骨干。     

Rotation of CDS via Connected Domatic Partition in Ad Hoc Sensor Networks

Wireless ad hoc and sensor networks (WSNs) often require a connected dominating set (CDS) as the underlying virtual backbone for efficient routing. Nodes in a CDS have extra computation and communication load for their role as dominator, subjecting them to an early exhaustion of their battery. A simple mechanism to address this problem is to switch from one CDS to another fresh CDS, rotating the active CDS through a disjoint set of CDSs. This gives rise to the connected domatic partition (CDP) problem, which essentially involves partitioning the nodes V(G) of a graph G into node disjoint CDSs. We have developed a distributed algorithm for constructing the CDP using our maximal independent set (MIS)-based proximity heuristics, which depends only on connectivity information and does not rely on geographic or geometric information. We show that the size of a CDP that is identified by our algorithm is at least lfloor{frac{delta+1}{beta(c+1)}}rfloor-f, where delta is the minimum node degree of G, betaleq 2, cleq 11 is a constant for a unit disk graph (UDG), and the expected value of f is epsilondelta|V|, where epsilon ll 1 is a positive constant, and delta geq 48. Results of varied testing of our algorithm are positive even for a network of a large number of sensor nodes. Our scheme also performs better than other related techniques such as the ID-based scheme.     

Network coding over connected dominating set: energy minimal broadcasting in wireless ad hoc networks

Energy efficient broadcast is indispensable for many applications in wireless ad hoc networks. It has been proved that network coding has great potential to improve performance in terms of energy consumption in wireless ad hoc networks. However, the power of network coding depends on the availability of coding opportunities, which in turns depends on how routing paths are established. It is thus beneficial to establish paths in such a way that more coding opportunities are created. By combining network coding and connected dominating set (CDS), we explore energy minimal broadcast protocols in wireless ad hoc networks. The rationale behind this combination is that CDS provides better chances for data flows to intersect, which means more coding opportunities. We design a scheme, named NCDS, that uses network coding over connected dominating set, to reduce energy consumption. Analysis and experimental results show that NCDS outperforms broadcast algorithms that use CDS or network coding alone.     

Approximation Algorithms for the Connected Dominating Set Problem in Unit Disk Graphs

The connected dominating set （CDS） problem, which consists of finding a smallest connected dominating set for graphs is an NP-hard problem in the unit disk graphs （UDGs）. This paper focuses on the CDS problem in wireless networks. Investigation of some properties of independent set （IS） in UDGs shows that geometric features of nodes distribution like angle and area can be used to design efficient heuristics for the approximation algorithms. Several constant factor approximation algorithms are presented for the CDS problem in UDGs. Simulation results show that the proposed algorithms perform better than some known ones.     

Dynamic power management in new architecture of wireless sensor networks

Dynamic power management (DPM) technology has been widely used in sensor networks. Though many specific technical challenges remain and deserve much further study, the primary factor currently limiting progress in sensor networks is not these challenges but is instead the lack of an overall sensor network architecture. In this paper, we first develop a new architecture of sensor networks. Then we modify the sleep state policy developed by Sinha and Chandrakasan in (IEEE Design Test Comput. 2001; 18 (2):62–74) and deduce that a new threshold satisfies the sleep‐state transition policy. Under this new architecture, nodes in deeper sleep states consume lower energy while asleep, but require longer delays and higher latency costs to awaken. Implementing DPM with considering the battery status and probability of event generation will reduce the energy consumption and prolong the whole lifetime of the sensor networks. We also propose a new energy‐efficient DPM, which is a modified sleep state policy and combined with optimal geographical density control (OGDC) (Wireless Ad Hoc Sensor Networks 2005; 1 (1–2):89–123) to keep a minimal number of sensor nodes in the active mode in wireless sensor networks. Implementing dynamic power management with considering the battery status, probability of event generation and OGDC will reduce the energy consumption and prolong the whole lifetime of the sensor networks. Copyright © 2008 John Wiley & Sons, Ltd.     

Adaptive Filtering Algorithm in Clock Calibration System

In wireless sensor network (WSN), data transfer from source to the destination needs an optimized network with less energy consumption. However, the optimized network with connected dominating set (CDS) of graph theory plays an important role in WSN for virtual backbone network formation. The connected dominating set is NP-hard problem with larger in size. However, the problem of the size of the network and NP-hard makes the researchers concentrate to improve the algorithms for virtual backbone. In this paper, we propose a semigraph contiguous prevalent set (SCPS) algorithm for semigraph structure to reduce NP-hard and size of the virtual backbone. The virtual back bone with SCPS algorithm applies with various protocols such as AODV, DSR, and DSDV for performance evaluation. From simulation result, we observe the network parameters such as size, diameter, average hoping and waiting time between the nodes are reduced. The proposed SCPS construction method retains the best performance ratio of \((2 + \ln \Delta_{a} )|opt|,\) whereas \(|opt|\) is the size of any optimal adjacent dominating set (ADS) and \(\Delta_{a}\) is the maximum adjacent degree of all nodes of the network and has the low time complexity of O(n ² ), whereas n denotes the network size. Furthermore, the proposed SCPS virtual backbone in hardware implementation proves the network life time increases about 86% of 9 V battery of the node.     

RECA: Referenced energy‐based CDS algorithm in wireless sensor networks

Connected dominating sets (CDS) can be used to form virtual backbones for the hierarchical routing to save energy in the wireless sensor networks. The existing algorithms for CDS can only be used to the topologies that have larger vertex connective degrees. Besides, most of them do not consider the energy characteristics of the virtual backbones constructed by the dominating sets. In this paper, a referenced energy‐based CDS algorithm (RECA) is proposed, which can generate smaller CDS in random topologies without the limitation of vertex connective degrees. At the same time, the algorithm introduces Referenced Energy as a parameter for nodes when making the decision whether they are chosen to be the dominators or not. Therefore, as the experimental results show, the energy characteristic of the dominating set is improved and routing in the virtual backbones constructed by such CDSs will have a better performance. Copyright © 2009 John Wiley & Sons, Ltd.     

监测无线传感器网络休眠调度算法

休眠调度设计是无线传感器网络一种重要的通信节能方法。针对监测典型应用,为了实现长时间的监测应用要求,充分利用冗余部署提供的能量资源,提出了一种能量相关的分布式自适应休眠调度算法。算法利用极大独立集构建思想,结合节点层次级别、实时的能量消耗、连通度等信息动态选择连通支配节点集作为网络骨干,使得网络活跃节点数量最小化。仿真试验分析表明,算法能够有效地利用冗余节点提供的能量资源,扩展了网络的生命周期。     

Energy‐Efficient Quorum‐Based MAC Protocol for Wireless Sensor Networks

The reliability of sensor networks is generally dependent on the battery power of the sensor nodes that it employs; hence it is crucial for the sensor nodes to efficiently use their battery resources. This research paper presents a method to increase the reliability of sensor nodes by constructing a connected dominating tree (CDT), which is a subnetwork of wireless sensor networks. It detects the minimum number of dominatees, dominators, forwarder sensor nodes, and aggregates, as well as transmitting data to the sink. A new medium access control (MAC) protocol, called Homogenous Quorum‐Based Medium Access Control (HQMAC), is also introduced, which is an adaptive, homogenous, asynchronous quorum‐based MAC protocol. In this protocol, certain sensor nodes belonging to a network will be allowed to tune their wake‐up and sleep intervals, based on their own traffic load. A new quorum system, named BiQuorum, is used by HQMAC to provide a low duty cycle, low network sensibility, and a high number of rendezvous points when compared with other quorum systems such as grid and dygrid. Both the theoretical results and the simulation results proved that the proposed HQMAC (when applied to a CDT) facilitates low transmission latency, high delivery ratio, and low energy consumption, thus extending the lifetime of the network it serves.     

Zone-based virtual backbone formation in wireless ad hoc networks

Efficient protocol for clustering and backbone formation is one of the most important issues in wireless ad hoc networks. Connected dominating set (CDS) formation is a promising approach for constructing virtual backbone. However, finding the minimum CDS in an arbitrary graph is a NP-Hard problem. In this paper, we present a novel zone-based distributed algorithm for CDS formation in wireless ad hoc networks. In this Zone algorithm, we combine the zone and level concepts to sparsify the CDS constructed by previous well-known approaches. Therefore, this proposed algorithm can significantly reduce the CDS size. Particularly, we partition the wireless network into different zones, construct a dominating tree for each zone and connect adjacent zones by inserting additional connectors into the final CDS (at the zone borders). Our comprehensive simulation study using a custom simulator shows that this zone-based algorithm is more effective than previous approaches. The number of nodes in the CDS formed by this Zone algorithm is up to around 66% less than that constructed by others. Moreover, we also compare the performance of Zone algorithm with some recently proposed CDS formation protocols in ns2 simulator.     

Sleep and Wakeup Strategies in Solar-Powered Wireless Sensor/Mesh Networks: Performance Analysis and Optimization

A queuing analytical model is presented to investigate the performances of different sleep and wakeup strategies in a solar-powered wireless sensor/mesh network where a solar cell is used to charge the battery in a sensor/mesh node. While the solar radiation process (and, hence, the energy generation process in a solar cell) is modeled by a stochastic process (i.e., a Markov chain), a linear battery model with relaxation effect is used to model the battery capacity recovery process. Developed based on a multidimensional discrete-time Markov chain, the presented model is used to analyze the performances of different sleep and wakeup strategies in a sensor/mesh node. The packet dropping and packet blocking probabilities at a node are the major performance metrics. The numerical results obtained from the analytical model are validated by extensive simulations. In addition, using the queuing model, based on a game-theoretic formulation, we demonstrate how to obtain the optimal parameters for a particular sleep and wakeup strategy. In this case, we formulate a bargaining game by exploiting the trade-off between packet blocking and packet dropping probabilities due to the sleep and wakeup dynamics in a sensor/mesh node. The Nash solution is obtained for the equilibrium point of sleep and wakeup probabilities. The presented queuing model, along with the game-theoretic formulation, would be useful for the design and optimization of energy-efficient protocols for solar-powered wireless sensor/mesh networks under quality-of-service (QoS) constraints     

基于极大独立集的最小连通支配集的分布式算法

全网范围的广播在无线传感器网络和移动自组织网络中有着广泛的应用.为节省网络资源,减少冗余转发节点成为广播中需解决的关键问题.广播过程中最小化参与转发节点数问题与图论中求解最小连通支配集问题等价,而在任意图中求解最小连通支配集是NP完全问题.本文基于极大独立集,提出了一种求解最小连通支配集的分布式算法(MISB),并证明了算法的正确性.仿真结果表明,使用该算法能得到较小的连通支配集,从而有效减少网络广播过程中的转发节点数,大大节省了网络资源.     

Construction and maintenance of virtual backbone in wireless networks

In ad hoc wireless networks, there is no predefined infrastructure and nodes communicate with each other via peer communications. In order to make routing efficient in such networks the connected dominating set (CDS) can act as virtual backbone for the network. A smaller virtual backbone suffers less from the interference problem and incurs less maintenance overhead. Computing minimum CDS backbone is proven to be NP-Hard, it is therefore desirable to use efficient heuristic algorithms to find a virtual backbone of small size. Diameter and average backbone path length (ABPL) are other major criteria for evaluation of the backbone produced by an algorithm. In this paper, after giving a brief survey of classical CDS algorithms, two new centralized algorithms are described for the construction of the virtual backbone and their performance has been compared with five recent algorithms (two centralized and three distributed) along the parameters: size, diameter, and ABPL. The new algorithms perform better on most of the criteria. The re-construction of entire CDS upon movement or failure of a few nodes is very costly in terms of processing power, battery utilization, bandwidth utilization etc., as compared to maintaining the CDS for the affected nodes, since the re-construction of the CDS is to be performed for the whole network while maintenance involves the affected nodes and their neighbours only. A new distributed algorithm is described that maintains the virtual backbone on movement or failure of a single node. The overhead of CDS maintenance with this algorithm compares very favourably against that of re-construction.