Search

One of the design challenges in Wireless sensor network (WSN) is to save limited energy resource to prolong the lifetime of the network without affecting their communication connectivity or sensing coverage . In dense WSN, the sensing areas of sensor node may overlap with each other. In general, the larger the overlap of the sensing range, the more redundant data will be generated with more energy consumption. In WSN, connected dominating set (CDS) has been used for energy efficient topology control, where a virtual backbone is formed, which allows communication between any arbitrary pair of nodes in the network. Nodes which are not in CDS can go to sleep state for energy conservation. Applications related to security and reliability require a certain amount of active nodes to ensure desired level of coverage at all time. These active nodes should be connected to reduce the delay during the communication. Therefore, it is necessary to construct a fault-tolerant CDS that continues to function during node or link failure, for both coverage and connectivity requirements of WSN. In this paper, we propose k-coverage connected dominating set ( k-CCDS) for connected area coverage. We also propose a weight metric named weighted coverage cost (WCC), which consists of energy of sensing neighbors. The proposed protocol selects a CDS based on WCC to ensure that every non-dominating node is connected with the CDS even if $$k-1$$ dominating nodes are dead. This CDS is named k-CCDS, in which every non-dominating node is covered by atleast k dominating nodes. Simulation results show that it performs better when comparing with A3Cov in terms of CDS size, coverage, energy consumption and lifetime of the network. [ABSTRACT FROM AUTHOR]

The Steiner connected dominating set problem is a generalization of the well-known connected dominating set problem, in which only a specified subset of the vertices must be dominated. Finding the Steiner connected dominating set is an NP-hard problem in graph theory, and a new promising approach for multicast routing in wireless ad hoc networks. In this paper, we propose six learning automata-based approximation algorithms for finding a near optimal solution to the minimum Steiner connected dominating set problem. For the first proposed algorithm, it is shown that, by a proper choice of the learning rate of algorithm, the probability of approximating the optimal solution is as close to unity as possible. Moreover, we compute the worst case running time of this algorithm for finding a 1/(1 − ε) optimal solution, and show that, by a proper choice of the learning rate, a trade-off between the running time of algorithm and dominating set size can be made. The last proposed algorithm is compared with the previous well-known algorithms and the results show the superiority of the proposed algorithm both in terms of the dominating set size and running time. [ABSTRACT FROM AUTHOR]

Mobile ad hoc networks (MANETs) are increasingly being employed for expanding the computing capabilities of existing cellular mobile systems and in the implementation of mobile computing grids. However, MANETs are susceptible to various transient as well as permanent failures and a fault tolerance technique is crucial in order to effectively utilize the constituent nodes as viable compute resources. Checkpointing and message logging based rollback recovery is a well established approach to provide fault tolerance in static and cellular mobile distributed systems; yet its use for achieving fault tolerance in MANETs is comparatively less explored. The existing recovery algorithms cannot be applied directly to MANETs due to their insufficiency in handling challenges like absence of static infrastructure, frequent node movement, constrained wireless bandwidth and limited stable storage. In this paper, we propose a checkpointing based rollback recovery protocol for clustered MANETs that determines the checkpointing frequency of a mobile node based on its mobility; thereby avoiding unnecessary checkpoints. The protocol uses a popular graph theoretic construct called connected dominating set to lower the communication overhead due to the recovery procedure. The findings of our scheme have been substantiated by the complexity analysis and simulation under varying network conditions. [ABSTRACT FROM AUTHOR]

Recently, Consensus based Clock Synchronization (CCS) algorithms have gained much attention in wireless sensor networks due to its simplicity, distributed nature and robustness. But, most of the algorithms are “all node based”, i.e., every node iterates the consensus algorithm to reach the synchronized state. This increases the overall message complexity, imposes congestion and delay in the network and high consumption of energy. In an energy constraint environment, it is desirable that a subset of sensors along with a limited number of neighboring sensors should be selected a priori such that the message complexity will be minimized and energy can be saved. Further, the selection of “subset” sensors must ensure connectivity for consensus propagation to achieve network wide synchronization and the neighboring sensors must be assigned in such a way that the delay must be minimized and balanced for faster consensus convergence. The overall problem is formulated as a Connected Dominating Set based Delay Balanced Topology (CDSDBT) problem and is shown to be NP-complete. To make the problem tractable, a Random Weighted Genetic Algorithm (RWGA) based strategy is proposed to handle the trade-off between the objective functions and to select the Pareto optimal solution (topology). Simulation results show that using the proposed strategy, the performance of some state-of-the-art CCS protocols have been improved significantly over their “all node based” counterpart. A comparative analysis is also carried out with recent and state-of-the-art GA based Minimum Connected Dominating Set (GAMCDS) strategy and GA based Load Balanced Connected Dominating Set (GALBCDS) strategy for the test CCS protocols which are used as topological backbone for other protocols and applications. [ABSTRACT FROM AUTHOR]

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 wakeup 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. [ABSTRACT FROM AUTHOR]

Connected dominating sets (CDSs) can be used as virtual backbones in mobile ad hoc networks (MANETs) to simplify the design of network primitives and improve their performance. An ideal CDS protocol for MANETs should create a small CDS and adapt to nodal mobility. Unfortunately, none of the CDS protocols capable of mobility handling have been shown to create a sub-optimal CDS in the past. In this paper, we first prove that our timer-based CDS protocols create a CDS with a sub-optimal size. Although the approximation factors of our timer-based protocols are not the best known result, our protocols can easily accommodate nodal mobility. In addition, we propose the Extended Mobility Handling (EMH) procedures for timer-based CDS protocols to further enhance CDS maintenance in MANETs. Simulation results show that our protocols incorporating EMH successfully prolong the CDS service time while maintaining a competitive size of CDS in MANETs. [ABSTRACT FROM AUTHOR]

The topology of mobile ad hoc networks (MANETs) change dynamically with time. Connected dominating sets (CDS) are considered to be an effective topology for network-wide broadcasts in MANETs as only the nodes that are part of the CDS need to broadcast the message and the rest of the nodes merely receive the message. However, with node mobility, a CDS does not exist for the entire duration of the network session and has to be regularly refreshed (CDS transition). In an earlier work, we had proposed a benchmarking algorithm to determine a sequence of CDSs (Maximum Stable CDS) such that the number of transitions is the global minimum. In this research, we study the performance (CDS Lifetime and CDS Node Size) of the Maximum Stable CDS when a certain fraction of the nodes in the network are static and compare the performance with that of the degree-based CDSs. We observe the lifetime of the Maximum Stable CDS to only moderately increase (by a factor of 2.3) as we increase the percentage of the static nodes in the network; on the other hand, the lifetime of the degree-based CDS increases significantly (as large as 13 times) as we increase the percentage of static nodes from 0 to 80. [ABSTRACT FROM AUTHOR]

Video dissemination over Vehicular Ad Hoc Networks is an attractive technology that supports many novel applications. The merit of this work lies in the design of an efficient video dissemination protocol that provides high video quality at different data rates for urban scenarios. Our objective is to improve received video quality while meeting delay and packet loss. In this work, we first employ a reliable scheme known as connected dominating set, which is an efficient receiver-based routing scheme for broadcasting video content. To avoid repeated computing of the connected dominating set, we add three statuses to each node. In nonscalable video coding, the distribution of lost frames can cause a major impact on video quality at the receiver's end. Therefore, for the second step, we employ Interleaving to spread out the burst losses and to reduce the influence of loss distributions. Although Interleaving can reduce the influence of cluster frame loss, single packet loss is also a concern due to collisions, and to intermittent disconnection in the topology. In order to fix these single packet losses, we propose a store-carry-forward scheme for the nodes in order to retransmit the local buffer stored packets. The results, when compared to the selected base protocols, show that our proposed protocol is an efficient solution for video dissemination over urban Vehicular Ad Hoc Networks. [ABSTRACT FROM AUTHOR]

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of the crossed cube (ITCC) is presented. The ITCC is to find a maximal independent set (MIS), which is based on building an induced tree of the crossed cube network, and then to connect the MIS nodes to form a CDS. The priority of an induced tree is determined according to a new parameter, the degree of the node in the square of a graph. This paper presents the proof that the ITCC generates a CDS with a lower approximation ratio. Furthermore, it is proved that the cardinality of the induced trees is a Fibonacci sequence, and an upper bound to the number of the dominating set is established. The simulations show that the algorithm provides the smallest CDS size compared with some other traditional algorithms. [ABSTRACT FROM AUTHOR]

Motivated by self-similar structures of Sierpiński graphs, we newly introduce the sub-divided-line graph operation Γ and define the n -iterated subdivided-line graph Γ n ( G ) of a graph G . We then study structural properties of subdivided-line graphs such as edge-disjoint Hamilton cycles, hamiltonian-connectivity, hub sets, connected dominating sets, independent spanning trees, completely independent spanning trees, and book-embeddings which can be applied to problems on interconnection networks. From our results, the maximum number of edge-disjoint Hamilton cycles, the minimum cardinality of a hub set, the minimum cardinality of a connected dominating set, the maximum number of independent spanning trees and the maximum number of completely independent spanning trees in Sierpiński graphs, and upper bounds on the pagenumbers of Sierpiński graphs which are at most two times the optimums are obtained as corollaries. In particular, our results for edge-disjoint Hamilton cycles and hub sets on iterated subdivided-line graphs are generalizations of the previously known results on Sierpiński graphs, while our proofs are simpler than those for Sierpiński graphs. [ABSTRACT FROM AUTHOR]

High reliability and low power consumption are among the major requirements in design of wireless sensor networks (WSNs). In this paper, a multi-objective problem is formulated as a Joint Power consumption and data Reliability (JPR) optimization problem. For this purpose, a connected dominating set (CDS)-based topology control approach is proposed. Our objective is to self-organize the network with minimum interference and power consumption. We consider the power changes into a topology with minimum CDS infrastructure subject to connectivity constraints. Since this problem is NP-hard, it cannot be dealt with using polynomial-time exact algorithms. Therefore, we first present a genetic algorithm taking into consideration problem-specific goals and constraints in an approximated manner called JPR Genetic Algorithm ( Jpr- ga). Secondly, a Hierarchical Sub-Chromosome Genetic Algorithm ( Hsc- ga) is proposed to obtain more accurate and faster solutions in the large and dense networks. We evaluate these algorithm over different networks topologies to analyse their efficiency. Comparing Jpr- ga and Hsc- ga with two different scenarios reveal that the proposed algorithms can efficiently balance power consumption and data communication reliability of sensor nodes and also prolong the network lifetime in WSNs. [ABSTRACT FROM AUTHOR]

Disasters create emergency situations and the services provided must be coordinated quickly via a communication network. Mobile adhoc networks (MANETs) are suited for ubiquitous communication during emergency rescue operations, since they do not rely on infrastructure. The route discovery process of on-demand routing protocols consumes too much bandwidth due to high routing overhead. Frequent route changes also results in frequent route computation process. Energy efficiency, quick response time, and scalability are equally important for routing in emergency MANETs. In this paper, we propose an energy efficient reactive protocol named Weighted-CDSR for routing in such situations. This protocol selects a subset of network nodes named Maximum Weighted Minimum Connected Dominating Set ( MWMCDS) based on weight, which consists of link stability, mobility and energy. The MWMCDS provides the overall network control and data forwarding support. In this protocol, for every two nodes u and v in the network there exists a path between u and v such that all intermediate nodes belong to MWMCDS. Incorporating route stability into routing reduces the frequency of route failures and sustains network operations over an extended period of time. With fewer nodes providing overall network control and data forwarding support, the proposed protocol creates less interference and consumes less energy. The simulation results show that the proposed protocol is superior to other protocols in terms of packet delivery ratio, control message overhead, transmission delay and energy consumption. [ABSTRACT FROM AUTHOR]

This paper considers the minimum k-connected d-dominating set problem, which is a fault-tolerant generalization of the minimum connected dominating set (MCDS) problem. Three integer programming formulations based on vertex cuts are proposed (depending on whether d < k, d D k, or d > k) and their integer hulls are studied. The separation problem for the vertex-cut inequalities is a weighted vertex-connectivity problem and is polytime solvable, meaning that the LP relaxation can be solved in polytime despite having exponentially many constraints. A new class of valid inequalities-r-robust vertex-cut inequalities-is introduced and is shown to induce exponentially many facets. Finally, a lazy-constraint approach is shown to compare favorably with existing approaches for the MCDS problem (the case k D d D 1), and is in fact the fastest in literature for standard test instances. A key subroutine is an algorithm for finding an inclusion-wise minimal vertex cut in linear time. Computational results for 4k1 d5D421 151 421 251 431 351 441 45 are provided as well. [ABSTRACT FROM AUTHOR]

Nodes in wireless multi-hop networks establish links with their neighbors, which are used for data transmission. In general, in this kind of networks every node has the possibility of acting as a router, forwarding the received packets when they are not the final destination of the carried data. Due to the routing protocol procedures, when the network is quite dense the overload added by the routing management messages can be very high. To reduce the effects of this overload a topology control mechanism can be used, which can be implemented using different techniques. One of these techniques consists of enabling or disabling the routing functionality in every node. Many advantages result from selecting just a subset of nodes for routing tasks: reduction of collisions, protocol overhead, interference and energy consumption, better network organization and scalability. In this paper, a new protocol for topology control in wireless mesh networks is proposed. The protocol is based on the centrality metrics developed by social network analysts. Our target network is a wireless mesh network created by user hand-held devices. For this kind of networks, we aim to construct a connected dominating set that includes the most central nodes. The resulting performance using the three most common centrality measures (degree, closeness and betweenness) is evaluated. As we are working with dynamic and decentralized networks, a distributed implementation is also proposed and evaluated. Some simulations have been carried out to analyze the benefits of the proposed mechanism when reactive or proactive routing protocols are used. The results confirm that the use of the topology control contributes to a better network performance. [ABSTRACT FROM AUTHOR]

Forming a virtual backbone has been always a significant technique for ad hoc networks to achieve high efficiency in various applications, including mobility management, broadcast based information dissemination, etc. This is especially true for Vehicular Ad Hoc Network (VANET), because most of VANET applications rely on broadcasting messages. Among others, constructing the Connected Dominating Set (CDS) is a popular approach to forming virtual backbone in ad hoc networks, including VANETs. Although quite a lot of work has been done on CDS algorithms for ad hoc networks, almost all existing algorithms focus on minimizing the size of CDS, i.e. the number of nodes in CDS. In this paper, the authors consider to improve the stability of CDS, i.e. to reduce the changes of CDS during the runtime of a VANET. By making use of vehicle navigation route, the authors propose a new metric to selecting CDS node with high stability. Then, based on the new metric the authors design a CDS algorithm, which can construct a CDS with higher stability than the CDS by existing algorithms. Such advantage is validated via extensive simulations. [ABSTRACT FROM AUTHOR]

Wireless sensing technology is becoming a new scientific instrument for environmental monitoring under extreme conditions. This class of applications requires reliable, energy-efficient, and self-organizing approaches. Connected dominating sets (CDSs) have been widely used for virtual backbone construction in unstructured wireless sensor networks to control topology, facilitate routing, and extend network lifetime. This paper proposes two distributed algorithms for CDS construction and maintenance in extreme wireless sensor networks. The proposed approaches efficiently construct and maintain a small CDS for challenging environments. Simulation shows that our proposed approaches provide significant energy efficiency without introducing any performance degradation in terms of CDS size. [ABSTRACT FROM PUBLISHER]

Network localization is important for networks with no prefixed positions of network nodes such as sensor networks. We are given a subset of the set of ( n 2 ) pairwise distances among n sensors in some Euclidean space. We want to determine the positions of each sensor from the (partial) distance information. The input can be seen as an edge weighted graph. In this paper, we present some efficient algorithms that solve this problem using the structures of input graphs, which we call their cores . For instance, we present a polynomial-time algorithm solving the network localization problem for graphs with connected dominating sets of bounded size. This algorithm allows us to have fixed-parameter tractable algorithms for some restricted instances such as graphs with connected vertex covers of bounded size. [ABSTRACT FROM AUTHOR]

Reducing transmission redundancy is key to efficient broadcast in wireless networks. A standard approach to achieving this goal is to create a network backbone consisting of a subset of nodes that are responsible for data forwarding, while other nodes act as passive receivers. On top of this, network coding (NC) is often used to further reduce unnecessary transmissions. The main problem with existing backbone and NC combinations is that the backbone construction process is blind of what is needed by NC, thus may produce a structure that limits the power of NC algorithms. To address this problem, we propose Coding Opportunity Aware Backbone (COAB) metrics, which seek to maximize coding opportunities when selecting backbone forwarders. We show that the backbone construction process guided by our metrics leads to significantly increased coding frequency, at the cost of minimal localized information exchange. The highlight of our work is COAB's broad applicability and effectiveness. We integrate the COAB metrics with ten state-of-the-art broadcast algorithms specified in eight publications [1]-[8], and evaluate COAB with a running testbed of 30 MICAz nodes and extensively simulations. The experimental results show that our design outperforms the existing schemes substantially. [ABSTRACT FROM PUBLISHER]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper we study the problem of building a constant-degree connected dominating set (CCDS), a network structure that can be used as a communication backbone, in the dual graph radio network model (Clementi et al. in J Parallel Distrib Comput 64:89-96, ; Kuhn et al. in Proceedings of the international symposium on principles of distributed computing , Distrib Comput 24(3-4):187-206 , Proceedings of the international symposium on principles of distributed computing ). This model includes two types of links: reliable, which always deliver messages, and unreliable, which sometimes fail to deliver messages. Real networks compensate for this differing quality by deploying low-layer detection protocols to filter unreliable from reliable links. With this in mind, we begin by presenting an algorithm that solves the CCDS problem in the dual graph model under the assumption that every process $$u$$ is provided with a local link detector set consisting of every neighbor connected to $$u$$ by a reliable link. The algorithm solves the CCDS problem in $$O\left( \frac{\varDelta \log ^2{n}}{b} + \log ^3{n}\right) $$ rounds, with high probability, where $$\varDelta $$ is the maximum degree in the reliable link graph, $$n$$ is the network size, and $$b$$ is an upper bound in bits on the message size. The algorithm works by first building a Maximal Independent Set (MIS) in $$\log ^3{n}$$ time, and then leveraging the local topology knowledge to efficiently connect nearby MIS processes. A natural follow-up question is whether the link detector must be perfectly reliable to solve the CCDS problem. With this in mind, we first describe an algorithm that builds a CCDS in $$O(\varDelta $$ polylog $$(n))$$ time under the assumption of $$O(1)$$ unreliable links included in each link detector set. We then prove this algorithm to be (almost) tight by showing that the possible inclusion of only a single unreliable link in each process's local link detector set is sufficient to require $$\varOmega (\varDelta )$$ rounds to solve the CCDS problem, regardless of message size. We conclude by discussing how to apply our algorithm in the setting where the topology of reliable and unreliable links can change over time. [ABSTRACT FROM AUTHOR]

In the Parameterized Connected Dominating Set problem the input consists of a graph G and a positive integer k, and the question is whether there is a set S of at most k vertices in G-a connected dominating set of G-such that (i) S is a dominating set of G, and (ii) the subgraph G[ S] induced by S is connected; the parameter is k. The underlying decision problem is a basic connectivity problem which is long known to be NP-complete, and it has been extensively studied using several algorithmic approaches. Parameterized Connected Dominating Set is W[2]-hard, and therefore it is unlikely (Downey and Fellows, Parameterized Complexity, Springer, ) that the problem has fixed-parameter tractable (FPT) algorithms or polynomial kernels in graphs in general. We investigate the effect of excluding short cycles, as subgraphs, on the kernelization complexity of Parameterized Connected Dominating Set. The girth of a graph G is the length of a shortest cycle in G. It turns out that the Parameterized Connected Dominating Set problem is hard on graphs with small cycles, and becomes progressively easier as the girth increases. More precisely, we obtain the following kernelization landscape: Parameterized Connected Dominating Set While there is a large and growing collection of parameterized complexity results available for problems on graph classes characterized by excluded minors, our results add to the very few known in the field for graph classes characterized by excluded subgraphs. [ABSTRACT FROM AUTHOR]

Topology control is a technique used in wireless sensor networks to maximize energy efficiency and network lifetime. In previous literature, many tree based techniques have been proposed to save energy and increase the network lifetime. In tree based algorithms, the most promising solution is the formation of a network backbone, which serves on behalf of rest of the nodes in the network and therefore leading towards Connected Dominating Set (CDS) formulation. However, one imminent problem with all tree based solution is a compromise on network reliability. Therefore, to address reliability issues in tree based solutions, in this paper, we propose Poly3 which maintains cliques of size three in order to achieve network reliability on top of the CDS algorithm. This makes the network more robust to link removal. Our empirical and mathematical analysis reveals that Poly3 provides better reliability than algorithms of the same kind. [ABSTRACT FROM AUTHOR]