Search

The purpose of this article is to propose Stability-based Energy-Efficient Link-State Hybrid Routing (S-ELHR), a low latency routing protocol that aims to provide a stable mechanism for routing in unmanned aerial vehicles (UAV). The S-ELHR protocol selects a number of network nodes to create a Connected Dominating Set (CDS) using a parameter known as the StabilityMetric (SM). The SMconsiders the node's energy usage, connectivity time, and node's degree. Only the highest SMnodes are chosen to form CDS. Each node declares a Willingness to indicate that it is prepared to serve as a relay for its neighbors, by employing its own energy state. S-ELHR is a hybrid protocol that stores only partial topological information and routing tables on CDSnodes. Instead of relying on the routing information at each intermediary node, it uses source routing, in which a route is generated on-demand, and data packets contain the addresses of the nodes the packet will transit. A route recovery technique is additionally utilized, which first locates a new route to the destination before forwarding packets along it. Through simulation for various network sizes andmobility speeds, the efficiency of S-ELHR is shown. The findings demonstrate that S-ELHR performs better than Optimized Link State Routing (OLSR) and Energy Enhanced OLSR (EE-OLSR) in terms of packet delivery ratio, end-to-end delay, and energy consumption. [ABSTRACT FROM AUTHOR]

Given a graph G = (V , E) , a dominating set is a subset D ⊆ V such that every vertex in V \ D is adjacent with at least one vertex in D. The domination number of G, denoted by γ (G) , is the minimum cardinality of a dominating set in G. Assuming that the graph G = (V , E) is connected, a subset D ⊆ V is said to be a connected dominating set if it is a dominating set and the subgraph G[D] induced by D is connected. The minimum cardinality of a connected dominating set is termed the connected domination number, denoted by γ c (G) . Comparing γ (G) and γ c (G) for a random graph with constant edge probability p, we obtain that the two parameters are asymptotically equal with probability tending to 1 as the number of vertices gets large. We also consider nonconstant edge probability p n tending to zero (where n is the number of vertices). Among other results, we extend an asymptotic formula of Gilbert on the probability of connectivity. [ABSTRACT FROM AUTHOR]

The Minimum connected dominating set problem (MinCDS) is a classical combinatorial optimization problem and has attached a lot of attention due to its application in wireless sensor networks (WSNs). Although the minimumk-connectedm-fold dominating set problem (Min(k, m)-CDS), which takes vertex fault tolerance into consideration, has been extensively studied in recent years, studies on edge fault tolerant CDS only start very recently. In this paper, we study the edge analog of Min(k, m)-CDS, denoted as Min(k, m)-ECDS, which aims to find S ⊆ V (G) such that the subgraph of G induced by S is k-edge connected and for any v ∈ V \ S , there are at least m edges between v and S. We give a greedy algorithm for Min(k, m)-ECDS on a general graph, with a theoretically guaranteed approximation ratio at most (2 k - 1) ln Δ + O (1) , where Δ is the maximum degree of G. When applied on an unit disk graph (UDG), the approximation ratio is at most 10 k - 5 k + O (1) when m ≤ 5 and 14 k + O (1) when m > 5 . In particular, our algorithm on Min(2, 2)-ECDS has approximation ratio at most 23.5, which improves the ratio 30.51 obtained in Liang et al. (Wirel Commun Mob Comput, 2021). [ABSTRACT FROM AUTHOR]

For a connected graph G, let γ (G) and γ c (G) denote the domination number and the connected domination number, respectively. Let H be a graph obtained from a triangle abc by adding a pendant edge at a and a pendant path of length 3 at each of b and c. In 2014, Camby and Schaudt conjectured that for any connected { P 9 , C 9 , H } -free graph G, γ c (G) ≤ 2 γ (G) . In this paper, we settle the conjecture in the affirmative. [ABSTRACT FROM AUTHOR]

Mine accidents often lead to partial communication link damage and communication network connectivity deterioration. Using residual nodes and limited new nodes, reconstructing coal mine rescue network by constructing local virtual backbone network can reduce the network energy overhead and enhance the connectivity and coverage control ability. A post-disaster reconstruction algorithm of wireless ad hoc network in coal mine based on multi-dimensional virtual backbone network is proposed. Considering the three dimensions of betweenness centrality, node closeness and residual energy screening mechanism of wireless sensor networks, a comprehensive evaluation index of virtual backbone nodes is constructed. The nodes with large comprehensive evaluation index are selected as the dominant nodes so as to enhance the robustness of virtual backbone network and prolong the network lifetime. This paper introduces the construction process of virtual backbone network. In the initial stage, the dominant nodes are generated through multiple rounds of election and the dominating set is updated. In the connecting stage of the dominating set, the relay nodes are elected, and the each dominant node and relay node are connected to form a connected dominating set. First-order radio energy consumption model is used to analyze the energy consumption of virtual backbone network. The Matlab R2017A platform is used to conduct simulation experiments on the network reconstructed based on this algorithm. The results show that the network residual energy, the number of dominant nodes and node coverage are better than the network constructed by sleep and energy balance-based connected dominating set algorithm and energy balance minimum connected dominating set algorithm.

A graph vertex-subset problem defines which subsets of the vertices of an input graph are feasible solutions. We view a feasible solution as a set of tokens placed on the vertices of the graph. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of token slides (along edges of the graph) or token jumps (between arbitrary vertices of the graph) such that each intermediate set remains a feasible solution of size k. Many algorithmic questions present themselves in the form of reconfiguration problems: Given the description of an initial system state and the description of a target state, is it possible to transform the system from its initial state into the target one while preserving certain properties of the system in the process? Such questions have received a substantial amount of attention under the so-called combinatorial reconfiguration framework. We consider reconfiguration variants of three fundamental underlying graph vertex-subset problems, namely Independent Set , Dominating Set , and Connected Dominating Set. We survey both older and more recent work on the parameterized complexity of all three problems when parameterized by the number of tokens k. The emphasis will be on positive results and the most common techniques for the design of fixed-parameter tractable algorithms. [ABSTRACT FROM AUTHOR]

A dominating set of a graph G is a set S ⊆ V (G) such that every vertex in G is either in S or adjacent to a vertex in S. A dominating set S is a connected dominating set if the subgraph of G induced by S is connected. The minimum cardinality of a connected dominating set of G is the connected domination number , denoted by γ c (G). Zhuang showed that γ c (G) of a maximal outerplanar graph G is bounded by min { ⌊ n + k 2 ⌋ − 2 , ⌊ 2 (n − k) 3 ⌋ } (Zhuang, 2020), where k is the number of 2-degree vertices in G. In this paper, we give an algorithm for finding a connected dominating set of maximal outerplanar graphs and get an upper bound γ c (G) ≤ ⌊ n − k + x 2 ⌋ , where x is a counter in the algorithm and x ≤ k − 2. As a corollary, the result that γ c (G) ≤ ⌊ n − 2 2 ⌋ for a maximal outerplanar G is gotten directly. This results is better than the above known bound for 3 < k < n + 6 4 . In addition, we complement some analysis with simulations to evaluate the advantages of our results. [ABSTRACT FROM AUTHOR]

Applications such as collaborative mapping motivate a need for network-wide broadcasting in Mobile Ad Hoc Networks (MANET) with low-rate long-range links. Existing MANET protocols are inadequate in such low-capacity regimes due to their high use of control packets. We present a novel protocol called ECHO that constructs and maintains a broadcast backbone without using any control packets. Instead, using a field in the data packet header, a node transmits and listens for an “echo” of the specific packet to determine its membership in the backbone. ECHO is deterministic, source-independent, fully distributed, accommodates mobility, and balances battery consumption across nodes. We prove ECHO’s correctness and show that its communication complexity is lower than that of Multi-Point Relay (MPR) and Flooding, and comparable to that of Opportunistic Announcement (OA). Simulations over random mobile low-capacity networks show that ECHO provides at least a 30 percent better delivery ratio than Flooding, MPR, and OA for 50-node networks and dramatically reduces the communication load. Experiments on a 12-node testbed of goTenna mobile mesh networking devices show that ECHO reduces transmissions by about 3x and increases battery life by more than 50 percent over Flooding. ECHO’s performance advantages are crucial for scalable broadcast in low-power, low-capacity wireless networks. [ABSTRACT FROM AUTHOR]

Telsiz duyarga ağları sağlık, ziraat, güvenlik ve eğlence gibi çeşitli alanlarda fayda sağlamaktadır. Bu ağları oluşturan düğümlerin enerji kaynaklarının kısıtlı olmasından dolayı enerjilerini etkin bir şekilde kullanmaya yönelik çeşitli çalışmalar gerçekleştirilmiştir. Bu çalışmalarda genel olarak, düğümlerin nöbetleşe sıra ile çalışması ya da sistemde enerji etkin bir iletişim omurgası kullanılması üzerinde durulmuştur. Telsiz duyarga ağlarında iletişim omurgası olarak genellikle bağlı baskın kümeler kullanılmaktadır. Ayrıca, kendi enerjisini üreten düğümlerin de telsiz duyarga ağı sistemlerinde kullanılarak bu sistemlerin yaşam süresinin arttırılması literatürdeki bazı çalışmalarda düşünülmüştür. Bu çalışmada telsiz duyarga sistemlerinin en büyük problemlerinden olan enerji sorunu incelenerek güneş panellerinden kendi enerjisini üretebilen ve üretemeyen düğümlerin olduğu telsiz duyarga ağlarının yaşam sürelerinin arttırılması için yeniden kullanılabilen yeni bir dağıtık bağlı baskın küme algoritması önerilmiştir. Bir düğümde veya düğümlerin bazılarında enerji tükenmesi gerçekleştiğinde belirli bir miktar beklenerek, çalışan düğümlerde bir kopma gerçekleşmemişse önerilen algoritma tekrar çalıştırılmaktadır. Önerilen algoritma, telsiz duyarga ağ alanında sıklıkla kullanılan Cooja tabanlı SensEH benzetim ortamında uygulanmıştır. Önerilen algoritma ve rakip algoritma oluşturulan bağlı baskın kümelerin kullanıldığı sistemlerdeki yaşam süreleri ile algoritmaların zaman ve enerji tüketim maliyeti kapsamlı benzetim analizleri ile incelenmiştir. Elde edilen sonuçlara göre önerilen algoritmanın toplam yaşam süresini rakip algoritmaya göre yaklaşık olarak iki katına çıkartabildiği görülmüştür.

The aim of this paper is to study the importance of graph theoretical concepts and the applications of distance - 2domination of some graphs. A set D is a distance - 2 dominating set iff or every vertex uV-D, d (u, D)=2andisdenotedby Also we discuss about many bounds and exact values for some standard graphs. [ABSTRACT FROM AUTHOR]

In a reconfiguration version of a decision problem Q the input is an instance of Q and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K d , d as a subgraph, for some constant d ≥ 1 . We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k + ℓ , the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Mine Automation is the property of Industry & Mine Automation Editorial Department and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

In this work, we consider the broadcast mechanisms for both reliable links and unreliable links in the Internet of Things (IoT) networks. Focusing on the minimum transmission broadcast (MTB) problem, we propose an efficient algorithm, termed as the Connected Dominating Set Algorithm based on Coalitional Graph Game (CDSA-CGG), to find the minimum connected dominating set (MCDS). Distinct from related work in the literature which adopts a non-cooperative game approach and assumes the interaction among nodes is limited to neighboring nodes, we formulate the interaction and cooperation among nodes over reliable links and over unreliable links as a connected forwarding graph based on coalitional graph game. We prove that the forwarding graph constructed by CDSA-CGG is a Nash network. In addition, we also prove that the final resulting graph is pairwise stable. The simulation results show that the proposed coalition graph game-based algorithm performs well in terms of the number of transmissions, convergence rate, and lifetime of nodes.

Graph energy and domination in graphs are most studied areas of graph theory. In this paper we try to connect these two areas of graph theory by introducing c-dominating energy of a graph G. First, we show the chemical applications of c-dominating energy with the help of well known statistical tools. Next, we obtain mathematical properties of c-dominating energy. Finally, we characterize trees, unicyclic graphs, cubic and block graphs with equal dominating and c-dominating energy.

The way nodes are arranged in a wireless network can significantly influence performance, especially information flow. The construction of disjoint virtual backbone networks (DVBNs) is one of the ways this can be accomplished. In this study, the authors first present a proposal that constructs multiple DVBNs using nodes' locations, in two phases. In the second phase of the proposal, dominator selection is initiated by the sink and then continued by each selected dominator. This occurs in rounds, with each round producing a distinct virtual backbone. The simulations show that multiple DVBNs can be produced with a good approximation ratio. Further, two optimisations are presented, one for a scanty network and the other for data dissemination. These are accomplished by changing the way in which the dominators are selected in the second phase of the algorithm. These optimisations are evaluated and a marked improvement is observed in node connectedness to the backbone and in hop count while keeping approximation ratios almost constant. [ABSTRACT FROM AUTHOR]

Considering post-disaster scenarios for intelligent traffic management and damage assessment where communication infrastructure may not be available, we advocate a swarm-of-drones mesh communication architecture that can sustain in-network connectivity among drones. The connectivity sustenance requirement stems from the fact that drones may move to various locations in response to service requests but they still need to cooperate for data collection and transmissions. To address this need, we propose a fully distributed connectivity maintenance heuristic which enables the swarm to quickly adapt its formation in response to the service requests. To select the moving drone(s) that would bring minimal overhead in terms of time and moving distance, the connected dominating set (CDS) concept from graph theory is utilized. Specifically, a variation of CDS, namely E-CDS, is introduced to address the needs of 3-D mobile swarm-of-drones. We then show that E-CDS is NP-Complete and propose a new distributed heuristic to solve it. Once the E-CDS is determined in advance, drones not part of this E-CDS set are picked for movement tasks. When the movement is to cause any disconnection with the rest of the swarm, other drones are also relocated to restore the connectivity. The proposed heuristics are implemented in ns-3 network simulator as part of the existing IEEE 802.11s mesh standard and the effectiveness is tested in terms of providing undisturbed services under different conditions. The results indicate that the proposed distributed heuristic almost matches the performance of a centralized solution and suits perfectly the needs of post-disaster traffic management. [ABSTRACT FROM AUTHOR]

Using the domination parameters of Cayley graphs constructed out of Zp Ã--Zm, where m ∊ {pα, pαqβ, pαqβrγ}, p, q, r are distinct prime numbers and α, β, γ are positive integers, in this paper we have discussed the total and connected domination number and diameter of these Cayley graphs. [ABSTRACT FROM AUTHOR]

In recent times, congestion in traffic is bit cost effective and several traffic management methods are utilized to balance the traffic as per the capacity of roads. However, many methods fails in pre-analyzing the network events to regulate the traffic flow. Also, the dynamic movement of vehicles fails in adapting the vehicle units to follow the changing topology. Hence, it is necessary for packet forwarding between source and destination nodes in a precise manner, where the packet loss and communication overhead should be in control. In this paper, we utilize the concept of Connected Dominating Set (CDS) approach in traffic management for reducing the flow of traffic streaming in main routes. The CDS approach dynamically adapts itself with the changing topology and acts as a virtual backbone to reduce traffic overhead. It restricts the increased flow of vehicles to the dominators, since traffic congestion in such areas increases. The CDS forwarding (CDSF) finds the dominating or high congestion routes and diverts the traffic to other areas based on the level of traffic in sub-routes. The CDSF method works on an assumption that edges on road segments has multiple vehicles, where it increases the network efficiency. However, we make careful consideration of choosing the other road segments to traverse the required packets from source to destination with reduced packet loss. The construction of a virtual backbone network with series of neighboring backbone nodes traverses efficiently the packets. Further, choosing vehicles with low velocity improves the probability of connectivity in a specific area and increases the network throughput. This improves the re-routing flexibility and makes the packets to reach the destination without traffic congestion in VANETs. The CDSF method and control strategies are tested in NS2 and SUMO simulator under different traffic conditions. The results of simulation show that CDSF traffic management system reduces significantly the traffic congestion and overall traffic cost that includes CDF, average latency, average end-to-end delay, Hop count, packet error rate, percentage delivery ratio, data delivery rate, throughput. The result shows that the proposed method 0.345 times improved packet delivery ratio, 0.35 times improved throughput and 0.7 times reduced delay than the existing methods. Further, the CDSF method controls the traffic density by reducing the maximum queue length and traffic controlling time. [ABSTRACT FROM AUTHOR]

Named data networking (NDN) has emerged as a new architecture derived from the strength and limitations of current Internet architecture to cope with today's Internet usage. Several NDN features bring potential advantages in routing method over any Content Delivery Network (CDN). But the name based forwarding poses unique challenges to scale huge number of complex name structures and unbounded name spaces in limited amount of memory. Additionally, high look-up time is required while searching a data from a massive amount of database and huge number of communications are occurred for the real-life applications which require intensive updates (e.g., archival data, Internet banking). In this paper, we propose changes in current NDN architecture and forwarding method with an aim to develop a lightweight solution to the said problems. Instead of storing the database in all routers according to link state routing, we store them in selected nodes, called special nodes, using a compact data structure like binary Patricia trie. We exploit the concept of connected dominating set (CDS) to select such special nodes and develop modified algorithms for update dissemination and interest/data forwarding accordingly. Finally, the performance of the proposed scheme is analyzed through extensive experiments in real-world graphs with real dataset in terms of update, storage, and look-up time overheads. Then the same are compared with the existing routing method used in NDN. The results show a reduction of 70–80% in both the storage and update overheads and more than 60% reduction in FIB look-up time in the proposed method. [ABSTRACT FROM AUTHOR]

In wireless sensor networks (WSNs), energy efficiency and low delay are two pivotal issues for data collection. Wireless sensor networks are composed of energy-constrained sensor nodes. While sensing the environment, the rapid transmission of data to the sink is critical for many applications. In order to save energy, the duty cycle based mode is adopted in most studies, but this method increases the data transmission delay. Thus, an Adding Duty Cycle Only in Connected Dominating Sets (ADCOCDS) approach is proposed in this paper, which can effectively reduce network energy consumption and delay. The main innovations of the ADCOCDS scheme are as follows: (1) Unlike the mode of the duty cycle for all nodes in the previous WSNs, in ADCOCDS scheme, we choose a part of nodes to construct as a connected dominating set, and these nodes adopt the mode of duty cycle. For other nodes in the network, the radio transmitter is turned off to save energy when there is no data to transmit, and when these nodes have data to send, they turn on the radio transmitter and send the data to nodes in the dominating set, then nodes in the dominating set transfer the data to sink. In ADCOCDS scheme, since only a small number of nodes adopt the duty cycle mode, the energy efficiency of the network is high; (2) In WSNs, we observed that the energy consumption of nodes in the near-sink area is higher than that in the far-sink area. Therefore, in the ADCOCDS scheme, we increase the duty cycle of nodes according to their energy consumption to reduce the delay. Through theoretical analysis and experimental results, the ADCOCDS scheme can effectively reduce energy consumption and delay by 12.09%-43.17% and 21.85%-57.96%, respectively, while improving network lifetime by 10.71%-24.13% compared with previous strategies.

Let G = (V,E) be a graph and S ⊆ V. We say that S is a dominating set of G, if each vertex in V \ S has a neighbor in S. Moreover, we say that S is a connected (respectively, 2-edge connected or 2-connected) dominating set of G if G[S] is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2- edge connected domination, or 2-connected domination) number of G is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of G, and is denoted γ(G) (respectively γ1(G), or γ′ 2(G), or γ2(G)). A well-known result of Duchet and Meyniel states that γ1(G) ≤ 3γ(G) − 2 for any connected graph G. We show that if γ(G) ≥ 2, then γ′ 2(G) ≤ 5γ(G) − 4 when G is a 2-edge connected graph and γ2(G) ≤ 11γ(G) − 13 when G is a 2-connected triangle-free graph.

Efficient routing and broadcasting among a set of nodes play a critical role in wireless adhoc networks. for energy efficient routing, a connected dominating set (CDS) based virtual backbone is a promising approach. In the network, one-hop neighbors are selected as multi point relay (MPR) by each node to cover all its two-hop neighbors for the purpose of broadcasting and 2-hop repair. To improve the network lifetime, energy efficient MPR based CDS construction has been proposed by considering the node degree, energy level, node ID and velocity of the node. We also propose a route discovery protocol to relay route request messages, which makes use of the CDS nodes to obtain a stable routing path; 2-hop repair for route maintenance, which reduces the path damage (reduced control packets with lesser consumption of bandwidth) and broadcast storm problem. The simulation results show that the proposed protocol increases the network lifetime up to 30% than other works and effectively repair damaged routes by reducing control packets. [ABSTRACT FROM AUTHOR]

Given a connected graph G = (V , E) . A subset C ⊆ V is a dominating set if every vertex of V is either in C or adjacent to a vertex in C. Further, C is a connected dominating set if C is a dominating set and the induced subgraph G[C] is connected. The Minimum Connected Dominating Set (Min-CDS) problem asks to find a connected dominating set with the minimum size, which finds applications in communication networks, in particular, as a virtual backbone in wireless sensor networks. This paper focuses on a variant of the classic Min-CDS problem, called Minimum Connected Dominating Set with Labeling (Min-CDSL), in which we are given a connected graph with vertex labels, and are required to find a connected dominating set C such that the number of labels in C (instead of |C|) is minimized. Min-CDSL is apparently a generalization of Min-CDS, and is undoubtedly NP - complete . We give an approximation algorithm for Min-CDSL within performance ratio bounded by ln | V (G) | + span (G) + 1 , where span (G) refers to the maximum span of the input labeled graph (i.e., the number of connected components of the induced subgraph by a single label). In general, span (G) ≪ | V (G) | and for a series of labeled graphs span (G) = O (1) . For a random graph G ∈ G n , p , span (G) = O (ln | V (G) |) almost surely, and thus our approximation ratio is O (ln | V (G) |) which is reasonable comparing with the best known approximation ratio ln | V (G) | + 1 for Min-CDS. [ABSTRACT FROM AUTHOR]

Wireless sensor networks are utilized in many different areas such as health, agriculture, security, and entertainment. Since the nodes that constitute wireless sensor networks have limited energy resources, many studies have been carried out on use of their resources in an energy efficient manner. These studies generally focused on duty cycle techniques or constructing energy efficient communication backbones. In wireless sensor systems, the connected dominating sets are generally considered to be used as a backbone. In addition, the deployment of the nodes that harvest their own energy in wireless sensor networks has also been considered in recent studies. In this study, a new distributed algorithm is proposed to construct reusable connected dominating set for wireless networks that possess energy harvester nodes and ordinary nodes which could not harvest its energy. Whenever an energy depletion problem in a node or in more than one node occurs, after a specific interval, the proposed algorithm is re-employed on the alive nodes unless wireless sensor network is disconnected. The proposed algorithm was implemented on SensEH simulation environment based on Cooja which is one of the most commonly used tools in the wireless sensor network area. The new algorithm and the rival algorithm in the area are analyzed with respect to the lifetime of the systems together with the time and the energy consumptions required by the algorithms. According to the results, it is observed that the proposed algorithm can double the total lifetime compared to the rival algorithm. [ABSTRACT FROM AUTHOR]

A connected dominating set (CDS) can act as a virtual backbone (VB) in a wireless sensor network (WSN). The overhead in a WSN is usually determined by the size of the corresponding VB. However, the construction of minimum CDSs (MCDSs) has been proven to be an NP-hard problem. Thus, most researchers use approximation algorithms to find smaller CDSs. In certain applications, the transmission radii of some nodes in the network are unstable due to certain environmental factors such as obstacles, signal interference and node movement. Thus, the robustness of VBs in WSNs should be considered. In this paper, we propose the concept of a $d $ -robust CDS and corresponding algorithms to construct $d $ -robust CDSs in WSNs with unstable transmission ranges. We propose algorithms for a $d $ -robust CDS that is bounded by $[{40.68/(1-d)^{2}+10.17}]\cdot opt+[{31.32/(1-d)^{2}+7.83}] $ , where $opt $ is the size of the MCDS and $d \in [0,1$). Through simulations, we show the relationship between the size of the $d$ -robust CDS and the value of $d$ and compare our algorithms with existing algorithms in terms of the robustness degree of the CDS. The results show that the CDSs produced by our algorithms exhibit better robustness. [ABSTRACT FROM AUTHOR]

In a connected graph G = (V,E), a set D ⊂ V is a connected dominating set if for every vertex v ∈ V \ D, there exists u ∈ D such that u and v are adjacent, and the subgraph〈D〉induced by D in G is connected. A connected dominating set of minimum cardinality is called a γc-set of G. For each vertex v ∈ V, we define the connected domination value of v to be the number of γc-sets of G to which v belongs. In this paper, we study the properties of connected domination value of a connected graph G and its relation to other parameters of a connected graph. Finally, we compute the connected domination value and number of γc-sets for a few well-known family of graphs. [ABSTRACT FROM AUTHOR]

The positive influence dominating set(PIDS) problem is a well-known APX-hard problem and there exists a greedy approximation algorithm with an approximation ratio of H (δ). However, the PIDS which is formed by this algorithm is not connected. This paper proposes an algorithm with an approximation ratio of H (12) to find the connected PIDS in a cubic graph. Furthermore, this paper also proposes an algorithm with an approximation ratio of H (9) to find the partial positive influence dominating set(PPIDS). Both of these two algorithms have a time complexity of O (n 3). In addition, we prove that for every node in the PIDS(or PPIDS) which is formed by our algorithms, there exists at least one node in the PIDS(or PPIDS) that is its two-hop neighbor. We also proved that in a cubic graph, the subgraph induced by PIDS is connected. These conclusions are also true in k-regular graphs. [ABSTRACT FROM AUTHOR]

Abstract Finding the minimum connected dominating set (MCDS) is a key problem in wireless sensor networks, which is crucial for efficient routing and broadcasting. However, the MCDS problem is NP-hard. In this paper, a new approximation algorithm with approximation ratio H(Δ)+3 in time O(n 2) is proposed to approach the MCDS problem. The key idea is to divide the sensors in CDS into core sensors and supporting sensors. The core sensors dominate the supporting sensors in CDS, while the supporting sensors dominate other sensors that are not in CDS. To minimize the number of both the cores and the supporters, a three-phased algorithm is proposed. (1) Finding the base-core sensors by constructing independent set (denoted as S 1), in which the sensors who have the largest |N2(v)||N(v)| $\frac {|N^{2}(v)|}{|N(v)|}$ (number of two-hop neighbors over the number of one-hop neighbors) will be selected greedily into S 1; (2) Connecting all base-core sensors in S 1 to form a connected subgraph, the sensors in the subgraph are called cores; (3) Adding the one-hop neighbors of the core sensors to the supporter set S 2. This guarantees a small number of sensors can be added into CDS, which is a novel scheme for MCDS construction. Extensive simulation results are shown to validate the performance of our algorithm.

Connected dominating set (CDS) is a subset of vertices in a graph which dominates all vertices and induces a connected subgraph. This paper proposes a game theoretic approach to find a CDS, and proves that starting from a non-trivial initial state, every non-trivial Nash equilibrium is a minimal CDS and reaching a non-trivial Nash equilibrium needs O (n) rounds in the worst case. [ABSTRACT FROM AUTHOR]