Search

Mobile sensor networks (MSNs) have emerged from the interaction between mobile robotics and wireless sensor networks. MSNs can be deployed in harsh environments, where failures in some nodes can partition MSNs into disconnected network segments or reduce the coverage area. A k-connected network can tolerate at least k-1 arbitrary node failures without losing its connectivity. In this study, we present a coverage-aware distributed k-connectivity maintenance (restoration) algorithm that generates minimum-cost movements of active nodes after a node failure to preserve a persistent k value subject to a coverage conservation criterion. The algorithm accepts a coverage conservation ratio (as a trade-off parameter between coverage and movements) and facilitates coverage with the generated movements according to this value. Extensive simulations and testbed experiments reveal that the proposed algorithm restores k-connectivity more efficiently than the existing restoration algorithms. Furthermore, our algorithm can be utilized to maintain k-connectivity without sacrificing the coverage, significantly., TUBITAK (The Scientific and Technological Research Council of Turkey) [113E470], This work was supported by TUBITAK (The Scientific and Technological Research Council of Turkey) under Project 113E470.

Energy efficiency is one of the major issues in wireless sensor networks (WSNs) that lack a fixed infrastructure and centralized control. In order to prolong the network lifetime, a connected dominating set (CDS) has been widely used as a virtual backbone in WSNs. The sensor nodes in WSNs are prone to failure due to a lack of battery, hardware damage, link failure, or environmental interference. Therefore, designing an energy-efficient and fault-tolerant CDS algorithm is quite vital in WSNs. A non-masking fault tolerance method denoted self-stabilizing tolerates any finite number of transient faults. In this paper, we propose a fault-tolerant distributed algorithm for a minimal capacitated CDS (CapCDS) construction in WSNs. To the best of our knowledge, this is the first distributed self-stabilizing CapCDS algorithm. It makes an illegitimate system legitimate at most [Formula presented] moves by using an unfair distributed scheduler where n is the number of nodes. The performance of the algorithm is validated through extensive experimental testbeds and simulations. © 2020 Elsevier B.V., 215E115 Türkiye Bilimsel ve Teknolojik Araştirma Kurumu, TÜBITAK, This work was funded by The Scientific and Technological Research Council of Turkey (TUBITAK) for the 215E115 numbered project.

A minimum vertex cut (MVC) of a graph G is the smallest subset of vertices whose removal creates at least two disconnected group of other vertices. Detecting nodes in MVCs in wireless ad hoc and sensor networks (WASNs) provides valuable information about their robustness and critical parts. There is a wide variety of central algorithms that find or estimate MVCs of graphs, but to the best of our knowledge the existing distributed algorithms can only estimate the cardinality of MVCs, or k, from local neighborhood information. Regardless of the fact that MVCs remain unknown in these algorithms, local estimation of k may produce wrong values, far from the real k. We propose a distributed algorithm, which uses an adapted meta heuristic method, to detect the nodes in MVCs. In the proposed algorithm, all nodes find their available paths to the sink (root node) and determine the minimum subset of nodes that their failure disconnects all detected paths. The smallest detected sets by the nodes will be MVCs of the WASN. Besides finding the union of MVCs with up to 89% average accuracy, the testbed and simulation results show that the correct detection ratio of k in the proposed algorithm is up to 37% more than the existing distributed algorithms.

A k-connected wireless sensor network (WSN) can tolerate failures on k-1 arbitrary nodes without loosing the connectivity between the remaining active nodes. Hence, the k value is one of the useful benchmarks that can help to measure the network reliability. Given that the nodes in a k-connected network has at least k disjoint paths to each other, we propose the path coloring based k-connectivity detection algorithm (PACK) that finds the k by counting the disjoint paths between the sink and all other nodes. The proposed algorithm has two Detection and Notification phases. In the Detection phase, all nodes find their disjoint paths to the sink and in the Notification phase the minimum detected path count, which determines the global k, is sent to the sink node. We theoretically prove that the detection range of our proposed algorithm is better than the existing distributed algorithms and uses fixed length messages with O(n Delta log(2)n) bit complexity and O(n) time complexity where n is the number of nodes and Delta is the maximum node degree. According to the comprehensive simulation results, the average correct detection ratio of proposed algorithm is more than 91% which is at least 2.3 times higher than the existing algorithms. (C) 2017 Elsevier B.V. All rights reserved.

International Symposium on Networks, Computers and Communications (ISNCC) -- JUN 18-20, 2019 -- Istanbul, TURKEY, Arapoglu, Ozkan/0000-0001-7309-7948, WOS: 000520478600097, Maximal independent set (MIS) has significantly important in practical applications for wireless sensor networks (WSNs). A distributed self-stabilizing system can initially start at any illegal state and takes back a legal state as long as there is no external intervention. We propose a novel distributed self-stabilizing MIS algorithm using two-hop information. It stabilizes an unstable system at most n-1 moves under an unfair distributed scheduler where n is the number of nodes in the graph. We use the message passing model as the communication model where this model is very appropriate for WSNs. the communication consumes the most energy in WSNs. So, move count is at least as important as round count where reducing the move count prolongs the lifetime of the network. We analyzed theoretically and tested it on SimPy discrete event simulator on randomly generated connected simple undirected graphs to compare with its counterparts in terms of transmitted bit count and move count against various node degrees and node counts., IEEE, IEEE Commun Soc, TEST, CIS ARGE, AIR

Wireless sensor networks (WSNs) are infrastructureless networks of tiny sensor motes which can sense from the environment and can transmit the sensed data through wireless communication. Generally, the transmission ranges of sensor nodes are limited and obstacles are present in the sensing area, so multi-hop communication by utilizing routing protocols is of utmost importance. Since the wireless transmission is prone to vulnerabilities such as eavesdropping and spoofing, monitoring the network traffic by secure points is a critical mission. In this paper, we propose breadth-first search tree (BFST) based vertex cover (VC) algorithms for routing and link monitoring in WSNs. BFST provides a shortest hop routing tree for WSNs and VC is a set of nodes for covering edges (communication links) of the network where it perfectly fits for network traffic monitoring. Unlike most existing algorithms which find minimal VC in a separate procedure, the proposed algorithms construct VC during the BFST establishment phase which leads to lower energy consumption for routing and link monitoring operations. We analyze the correctness proof of the algorithms along with the time, message, space, and bit complexities. We implement the proposed algorithms with their counterparts on a testbed of IRIS motes to evaluate their performances. We find through extensive evaluations from the IRIS testbed experiments and TinyOS simulations that the proposed algorithms find smaller VC sets with up to 3.1 times lower energy consumption than the existing distributed algorithms., TUBITAK (Scientific and Technical Research Council of Turkey) [215E115], The authors would like to thank TUBITAK (Scientific and Technical Research Council of Turkey) for its support of project number 215E115.

We present the first self-stabilizing algorithm for finding a maximal b-matching in arbitrary networks and under distributed unfair (adversarial) schedulers. The previous self-stabilizing b-matching algorithm presented by Goddard et al. in 2003 assumes central scheduler. We give proof for the correctness of our new algorithm for both unfair and fair schedulers, as well as the synchronous scheduler. Our algorithm stabilizes in O (Bm) steps under unfair scheduler and in O (n) rounds under distributed fair and synchronous schedulers, where n, m and B are the number of processors, the number of edges and the maximum capacity in the graph, respectively. The time complexity of distributed fair version of our algorithm is better than that of the transformation of Goddard et al.'s sequential self-stabilizing algorithm to the distributed fair one with the conflict manager of Gradinariu and Tixeuil (2007). (C) 2018 Elsevier B.V. All rights reserved.

4th International Conference on Computer Science and Engineering (UBMK) -- SEP 11-15, 2019 -- Samsun, TURKEY, WOS:000609879900125, Tiny motes running on wireless sensor networks (WSNs) are equipped with limited batteries. Thus, design and implementation of energy-efficient algorithms on WSNs is vital. Problem of finding a capacitated minimum spanning tree (CMST) on a WSN deals with finding a minimum cost tree oriented to a root node (sink) where each subtree of the root node has no more than a predefined capacity value of a nodes. Finding minimum CMST problem is in NP-Hard complexity class and it is very important in terms of energy-efficient routing in WSNs. in this study, we analyze the performances of CMST algorithms on WSNs. To the best of our knowledge, this is the first study which provides an extensive evaluation of CMST algorithms for WSNs. We work on central (i.e. sequential) and distributed algorithms, CENTEW and MCO respectively, and provide performance measurements from these approaches by comparing them through various setups. Although both algorithms are derived from the famous heuristic Esau-Williams algorithm, the computation types of both algorithms are totaly different. According to the gained experimental results from TOSSIM simulator, although CENTEW consumes less time, MCO algorithm uses up to 2.41 times less energy than CENTEW algorithm. This finding shows us that using a localized CMST approach is time-efficient whereas using a distributed CMST approach is energy-efficient., IEEE, IEEE Turkey Sect, TUBITAK (Scientific and Technical Research Council of Turkey)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [215E115], This work was supported by the TUBITAK (Scientific and Technical Research Council of Turkey) [Project number 215E115].

4th International Conference on Computer Science and Engineering (UBMK) -- SEP 11-15, 2019 -- Samsun, TURKEY, WOS:000609879900115, Wireless Sensor Networks (WSN) consist of devices that can communicate with each other without using any fixed infrastructure. These devices can gather necessary information from the environment via their sensors and share collected data with each others. WSNs can be modelled with graphs (G (V, E)) where V is the set of vertices (nodes) and E is the set of edges. Graph theoretical structures such as graph matching can be used to solve various problems such as backup assignment in WSNs. With this aim, we first design a synchronous distributed weighted graph matching algorithm based on Hoepman's algorithm. After this the synchronous algorithm is improved by using overhearing method to design ICO algorithm. Proposed ICO algorithm aims to decrease the transmitted message count for graph matching operation by applying in-network processing. These algorithms are tested on various settings having different node counts and degrees in TOSSIM simulator by comparing with each other. The results of these extensive tests reveal us that ICO is more effective in terms of energy consumption and transmitted bytes., IEEE, IEEE Turkey Sect, TUBITAKTurkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [215E115], Authors would like to thank TUBITAK for the project grant 215E115

27th Signal Processing and Communications Applications Conference (SIU) -- APR 24-26, 2019 -- Sivas Cumhuriyet Univ, Sivas, TURKEY, WOS: 000518994300166, Dominating sets are one of the most important graph theoretic structures used in clustering and routing protocols in wireless sensor networks. For this reason, many distributed dominating set algorithms have been studied by researchers. Since wireless sensor networks are usually composed of battery powered devices, it is important to minimize the resource consumption of dominating set algorithms. in this study, experimental performance of four synchronous distributed dominating set algorithms including 1-hop span-based, 2-hop span-based, random and identity (ID)-based are measured in SimPy environment in terms of time, message, cluster size and energy per node. While performing these tests, the node count and the average node degree in the wireless sensor networks are changed and a large number of measurements are taken to compare the algorithms. As a result of the detailed experiments, 2-hop span-based algorithm has the best results in terms of set size and the ID-based algorithm has the best results in terms of resource utilization., IEEE Turkey Sect, Turkcell, Turkhavacilik Uzaysanayii, Turitak Bilgem, Gebze Teknik Univ, SAP, Detaysoft, NETAS, Havelsan

EgeUn###, A self-stabilizing distributed system can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilizing systems can automatically recover from faults and they are popular fault tolerant systems. Simulating self-stabilizing systems is a vital task in case of fault-tolerant distributed networks where node and edge updates can be frequent. A discrete-event simulation is a method of simulating the behavior and performance of an algorithm running on a distributed system. To the best of our knowledge, there are few simulators for self-stabilizing distributed algorithms in literature where these simulators are generally outdated and hard to use. In this paper we propose a novel distributed self-stabilizing discrete-event simulator (SELFSIM). SELFSIM is written in C# programming language on.NET Framework and supports up-to-date principles of software development techniques such as separation of concerns. We give the design and implementation of the proposed simulator and compare SELFSIM with its counterparts by considering various parameters such as supported node count (scalability), topological features, daemon (scheduler) types, etc., and show the superiority of our simulator. © 2018 IEEE., National Council for Scientific Research: 215E115, ACKNOWLEDGMENT The authors would like to thank the TUBITAK (Scientific and Technical Research Council of Turkey) for financial support of the project 215E115 which this work belongs to it.

26th IEEE Signal Processing and Communications Applications Conference (SIU) -- MAY 02-05, 2018 -- Izmir, TURKEY, YIGIT, Yasin/0000-0001-5257-9382, WOS:000511448500137, Wireless sensor networks are ad-hoc networks that operate with limited capacity and energy. in wireless sensor networks, it may be desirable to monitor the traffic on the network by checking the links for the security of the system. For such a scenario, the vertex cover problem, which is the well-known problem in the graph theory, can be used. The problem is covering of links on the graph by selecting the minimum number of nodes. Thus, all connections on the network can be controlled using as few devices as possible. Self-stabilizing algorithms are algorithms that stabilize the system without external intervention from a random initial state. At this point, the system guarantees a stabilization after a limited time against possible faults. in this study evaluation of vertex cover algorithms for fault tolerant link monitoring in wireless sensor network is made and it is shown that Kiniwa's algorithm performs better than the other algorithms., IEEE, Huawei, Aselsan, NETAS, IEEE Turkey Sect, IEEE Signal Proc Soc, IEEE Commun Soc, ViSRATEK, Adresgezgini, Rohde & Schwarz, Integrated Syst & Syst Design, Atilim Univ, Havelsan, Izmir Katip Celebi Univ

Energy-efficient backbone construction is one of the most important objective in a wireless sensor network (WSN) and to construct a more robust backbone, weighted connected dominating sets can be used where the energy of the nodes are directly related to their weights. In this study, we propose algorithms for this purpose and classify our algorithms as weighted dominating set algorithms and weighted Steiner tree algorithms where these algorithms are used together to construct a weighted connected dominating set (WCDS). We provide fully distributed algorithms with semi-asynchronous versions. We show the design of the algorithms, analyze their proof of correctness, time, message and space complexities and provide the simulation results in ns2 environment. We show that the approximation ratio of our algorithms is 3ln(S) where S is the total weight of optimum solution. To the best of our knowledge, our algorithms are the first fully distributed and semi-asynchronous WCDS algorithms with 3ln(S) approximation ratio. We compare our proposed algorithms with the related work and show that our algorithms select backbone with lower cost and less number of nodes. We propose weighted connected dominating set algorithms for wireless sensor networks.Proposed algorithms are fully distributed and semi-asynchronous.Algorithms have 3ln(S) approximation ratio (S is the cost of the optimum solution).We provide theoretical analysis for message, time and space complexities.Algorithms are compared with the previous work through extensive simulations.

Self stabilization is an important paradigm for the autonomous recovery of a distributed system from transient failures such as energy depletion of nodes and disrupted connections. It has been used in wireless sensor networks (WSN) as these networks are expected to automatically recover from a transient fault without human intervention. Graph matching is fundamental a graph theory problem which has a broad application range in WSNs and it has been studied extensively in self-stabilizing settings. In this work, we build a simulation model and perform tests to evaluate the fault tolerance properties of self-stabilizing matching algorithms. To the best of our knowledge, this is the first practical evaluation of these algorithms. Considering WSNs, we assume distributed fair and synchronous schedulers. Simulation results have shown that there is a tradeoff between stabilization time of algorithms and the quality of their results. The improvement algorithms which has better lower bounds give better matchings at the cost of longer durations of instability.

Finding a minimal dominating set (MDS) is a popular problem in wireless sensor networks (WSNs) to provide routing and backbone formation. A self-stabilizing system can tolerate topological changes such as node and edge joining/leaving thus they are very suitable for fault-tolerant and reliable WSNs. In this paper, we provide an extensive performance evaluation of self-stabilizing MDS algorithms for WSNs. To the best of our knowledge, this is the first experimental evaluation study of self-stabilizing MDS algorithms applied in WSN domain. We implemented the algorithms on various node counts and densities, and compared the average energy consumption, wall- clock time, move count and dominator count of the algorithms. The comprehensive simulation results show that the Goddard's algorithm finds the MDS with about 8.8% lower move and 5.8% lower dominator node count while its theoretical move count bound is higher than Chiu's algorithm. Despite of lower move count, the simulation results shows that the energy consumption of Goddard's algorithm is up to 1.5 times higher than Turau's and 2.8 times higher than Chiu's algorithms. The wallclock time, move count and detected dominator count of Turau's algorithm are respectively 84%, 88% and 12% higher than Goddard's algorithm in the networks with 1500 nodes which confirms its 9n move count bound. These measurements reveal that Goddard's algorithm outperforms other algorithms in terms of dominator count and Chiu's algorithm has a better performance for other metrics.

Vertex cover (VC) is one of the most fundamental graph-theoretical problems and has been widely used in wireless sensor networks (WSNs), particularly for the link monitoring problem. It is well known that a solution to the independent set problem (IS), which is another fundamental graph-theoretical problem, is complement of a VC. Self- stabilization is an important concept for designing fault tolerance systems. There have been many self-stabilizing VC and IS algorithms in the field. Even though a self-stabilizing IS algorithm can provide VC solutions, it does not give a theoretical guarantee on approximation ratio. In this work, we focus on practical fault tolerance performance of self- stabilizing IS algorithms in case of a vertex cover problem, particularly link monitoring in WSNs. We implement all existing self-stabilizing VC and IS algorithms and make simulations assuming a WSN in which nodes run synchronously. Results show that self-stabilizing IS algorithms in general are able to find better covers than VC algorithms, as they provide roughly 15% smaller solution sets. Furthermore, IS algorithms that run under distributed scheduler converges to a desired configuration in considerably less number of rounds than VC algorithms.

Devices running on Wireless Sensor Networks (WSNs) generally have limited energy resources, which makes it important to design energy-aware algorithms. Capacitated Minimum Spanning Tree (CMST) algorithms can be designed for finding energy-aware routing paths and for load-balancing among sub-trees connected to the sink device. Despite being studied extensively in central settings, there has not been any energy-efficient algorithm for the WSNs. The bit complexity of applying a central approach in the sink node is O(n2 logn) bits on a network having n nodes. In this work, we present the design of an algorithm which aims to solve CMST problem in WSNs and is based on Esau-Williams (E-W) algorithm. The bit complexity of the proposed algorithm is O(nlogn) bits. We compare the performance of the algorithm with the straightforward implementation of E-W where the problem is solved by the sink node and the result is sent to the other nodes. According to the computational results, our algorithm is more efficient than this version with respect to the energy consumption. Our algorithm (MCO) consumes up to 3 times less energy than central algorithm.

WOS: 000328612800040, PubMed ID: 23845930, Wireless sensor networks (WSNs) are promising technologies for exploring harsh environments, such as oceans, wild forests, volcanic regions and outer space. Since sensor nodes may have limited transmission range, application packets may be transmitted by multi-hop communication. Thus, connectivity is a very important issue. A bridge is a critical edge whose removal breaks the connectivity of the network. Hence, it is crucial to detect bridges and take preventions. Since sensor nodes are battery-powered, services running on nodes should consume low energy. In this paper, we propose energy-efficient and distributed bridge detection algorithms for WSNs. Our algorithms run single phase and they are integrated with the Breadth-First Search (BFS) algorithm, which is a popular routing algorithm. Our first algorithm is an extended version of Milic's algorithm, which is designed to reduce the message length. Our second algorithm is novel and uses ancestral knowledge to detect bridges. We explain the operation of the algorithms, analyze their proof of correctness, message, time, space and computational complexities. To evaluate practical importance, we provide testbed experiments and extensive simulations. We show that our proposed algorithms provide less resource consumption, and the energy savings of our algorithms are up by 5.5-times.

Graph coloring is a widely used technique for allocation of time and frequency slots to nodes, for forming clusters, for constructing independent sets anddominating sets on wireless ad hoc and sensor networks. A good coloring approach should produce low color count as possible. Besides, since the nodes of a wireless ad hoc and sensor network operate with limited bandwidth, energy and computing resources, th should be computed with few message passing and computational steps. In this paper, we provide a performance evaluation of distributed synchronous greedy graph coloring algorithms on ad hoc and sensor networks. We provide both theoretical and pr actical evaluations of distributed largest first and the distributed version of Brelaz’s algorithm. We showed that although distributed version of Brelaz’s algorithm produces less color count, its resource consumption is worse than distributed largest firs t algorithm.

2017 IEEE International Black Sea Conference on Communications and Networking, BlackSeaCom 2017 -- 5 June 2017 through 8 June 2017 -- -- 134510, 2-s2.0-85050716269, Matching problem has been attracting a growing attention in network design, especially in wireless communication networks. Although there is an exact polynomial-time sequential algorithm for the weighted version of the problem, all the related distributed algorithms are approximation algorithms. In this paper we present a distributed heuristic which improves the weight of a given matching in time proportional to the number of nodes. Our algorithm assumes the asynchronous communication model in which the message size is limited to O (log n) bits. To the best of our knowledge, it is the first distributed weighted matching algorithm which benefits from augmentation of alternating paths having size larger than 3 and uses small messages. We also provide results of our simulations on random geometric graphs. Computational results show that our algorithm improves the approximated solutions of other weighted matching algorithms roughly by 1-3% and closes the gap between the approximation ratio and the optimum solution by 9-26%. © 2017 IEEE., 215E115, BIDEB-1001, Authors would like to thank TUBITAK for the project grant (215E115) and the PhD research grant (BIDEB-1001).

WOS: 000323038600001, Distributed mutual exclusion is a fundamental problem which arises in various systems such as grid computing, mobile ad hoc networks (MANETs), and distributed databases. Reducing key metrics like message count per any critical section (CS) and delay between two CS entrances, which is known as synchronization delay, is a great challenge for this problem. Various algorithms use either permission-based or token-based protocols. Token-based algorithms offer better communication costs and synchronization delay. Raymond's and Suzuki-Kasami's algorithms are well-known token-based ones. Raymond's algorithm needs only O(log(2)(N)) messages per CS and Suzuki-Kasami's algorithm needs just one message delivery time between two CS entrances. Nevertheless, both algorithms are weak in the other metric, synchronization delay and message complexity correspondingly. In this work, a new hybrid algorithm is proposed which gains from powerful aspects of both algorithms. Raysuz's algorithm (the proposed algorithm) uses a clustered graph and executes Suzuki-Kasami's algorithm intraclusters and Raymond's algorithm interclusters. This leads to have better message complexity than that of pure Suzuki-Kasami's algorithm and better synchronization delay than that of pure Raymond's algorithm, resulting in an overall efficient DMX algorithm pure algorithm.

Graph matching is a fundamental graph theory problem which has a broad application range including information retrieval, pattern recognition, graph partitioning, chemical structure analysis, protein function prediction, backup placement and cellular coverage. This problem has gained attention in distributed computing as there are distributed matching algorithms with asymptotically guaranteed time bounds and approximation ratios. On the other side, we do not know the practical performance of these algorithms. In this paper, we provide a detailed performance evaluation of asynchronous distributed maximum weighted matching (MWM) algorithms. We assume a message-passing system in CONGEST model in which the message size is limited to O(log n) where n is the number of nodes. This model is popular for energy-efficient networks such as wireless sensor networks. We used a discrete event simulator, SimPy, to model the assumed network structures. We provide the implementations of Watthenhofer and Wattenhofer's algorithm, Hoepman's algorithm, Lotker et al.'s algorithm and Lotker et al.'s improvement algorithm. The results show that the greedy algorithm of Hoepman performed best in approximating the optimum result in all types of networks, even achieving an approximation ratio of 0.99 in some instances. To the best of our knowledge this is the first study which provides an extensive performance evaluation of distributed MWM algorithms.

We propose a distributed mutual exclusion algorithm for mobile ad hoc networks. This algorithm requires a ring of cluster coordinators as the underlying topology. The topology is built by first providing clusters of mobile nodes in the first step and then forming a backbone consisting of the cluster heads in a ring as the second step. The modified version of the Ricart-Agrawala Algorithm on top of this topology provides analytically and experimentally an order of decrease in message complexity with respect to the original algorithm. We analyze the algorithm, provide performance results of the implementation, discuss the fault tolerance and the other algorithmic extensions, and show that this architecture can be used for other middleware functions in mobile networks.

In wireless ad hoc and sensor networks, energy is a scarce resource and a considerable amount of energy is dissipated due to interference. Therefore, interference is one of the major challenges in wireless ad hoc and sensor networks. It alters or disrupts a message as it is being transmitted along a channel between source and destination. Since the messages are disrupted when the interference occurs, they have to be detected and the interfered messages have to be retransmitted. In this paper, we propose central and distributed heuristic algorithms for reducing average interference in a receiver-centric interference model. In the literature, the minimum spanning tree (MST) algorithm is generally used through the interference coverage graph directly or indirectly in order to generate minimum average interference topology. Our algorithm, dynamic average interference (DAI), however, generates lower average interference as well as more sparse topology than MST. We realized that if the transmission ranges of nodes are taken into consideration at each stage of the topology control algorithm, the interference of links are changed dynamically. This interference changing enables up to 22% more energy saving than the MST algorithm. Thus, DAI provides energy saving by reducing the interference as far as possible in generated topology.

Clustering is a widely used technique to manage the essential operations such as routing and data aggregation in wireless sensor networks (WSNs). We propose two new graph-theoretic distributed clustering algorithms for WSNs that use a weighted matching method for selecting strong links. To the best of our knowledge, our algorithms are the first attempts that use graph matching for clustering. The first algorithm is divided into rounds; extended weighted matching operation is executed by nodes in each round; thus the clusters are constructed synchronously. The second algorithm is the enhanced version of the first algorithm, which provides not only clustering but also backbone formation in an energy-efficient and asynchronous manner. We show the operation of the algorithms, analyze them, provide the simulation results in an ns2 environment. We compare our proposed algorithms with the other graph-theoretic clustering algorithms and show that our algorithms select strong communication links and create a controllable number of balanced clusters while providing low-energy consumptions. We also discuss possible applications that may use the structure provided by these algorithms and the extensions to the algorithms. © The Author 2009. Published by Oxford University Press on behalf of The British Computer Society. All rights reserved.

Vertex covering has important applications for wireless sensor networks such as monitoring link failures, facility location, clustering, and data aggregation. In this study, we designed three algorithms for constructing vertex cover in wireless sensor networks. The first algorithm, which is an adaption of the Parnas & Ron's algorithm, is a greedy approach that finds a vertex cover by using the degrees of the nodes. The second algorithm finds a vertex cover from graph matching where Hoepman's weighted matching algorithm is used. The third algorithm firstly forms a breadth-first search tree and then constructs a vertex cover by selecting nodes with predefined levels from breadth-first tree. We show the operation of the designed algorithms, analyze them, and provide the simulation results in the TOSSIM environment. Finally we have implemented, compared and assessed all these approaches. The transmitted message count of the first algorithm is smallest among other algorithms where the third algorithm has turned out to be presenting the best results in vertex cover approximation ratio.

WOS: 000318921600001, A bridge is a critical edge whose fault disables the data delivery of a WSN component. Because of this, it is important to detect bridges and take preventions before they are corrupted. Since WSNs are battery powered, protocols running on WSN should be energy efficient. In this paper, we propose two distributed energy-efficient bridge detection algorithms for WSNs. The first algorithm is the improved version of Pritchard's algorithm where two phases are merged into a single phase and radio broadcast communication is used instead of unicast in order to remove a downcast operation and remove extra message headers. The second algorithm runs proposed rules on 2-hop neighborhoods of each node and tries to detect all bridges in a breadth-first search (BFS) execution session using O(N) messages with O(Delta(log(2)(N))) bits where N is the node count and Delta is the maximum node degree. Since BFS is a natural routing algorithm for WSNs, the second algorithm achieves both routing and bridge detections. If the second proposed algorithm is not able to to classify all edges within the BFS phase, improved version of Turau's algorithm is executed as the second phase. We show the operation of the algorithms, analyze them, and provide extensive simulation results on TOSSIM environment. We compare our proposed algorithms with the other bridge detection algorithms and show that our proposed algorithms provide less resource consumption. The energy saving of our algorithms is up to 4.3 times, while it takes less time in most of the situations.

4th International Symposium on Parallel and Distributed Processing and Applications, ISPA 2006; Sorrento; Italy; 4 December 2006 through 6 December 2006, Construction of a backbone architecture is an important issue in mobile ad hoc networks(MANET)s to ease routing and resource management. We propose a new fully distributed algorithm for backbone formation in MANETs that constructs a directed ring architecture. We show the operation of the algorithm, analyze its message complexity and provide results in the simulation environment of ns2. Our results conform that the algorithm is scalable in terms of its running time and roundtrip delay against mobility, surface area, number of nodes and number of clusterheads.

ICCS 2006: 6th International Conference on Computational Science; Reading; United Kingdom; 28 May 2006 through 31 May 2006, We propose a new Connected Dominating Set (CDS) based algorithm for clustering in Mobile Ad hoc Networks (MANETs). Our algorithm is based on Wu and Li's [14] algorithm, however we provide significant modifications by considering the degrees of the nodes during marking process and also provide further heuristics to determine the color of a node in the initial phase. We describe, analyze and measure performance of this new algorithm by simulation and show that it performs better than Wu and Li's [14] algorithm especially in the case of dense networks.

EgeUn###, A critical node (cut vertex or articulation point) in wireless sensor networks, is a node which its failure breaks the connectivity of the network. Therefore, it is crucial that critical nodes be detected and treated with caution. This paper provides two localized distributed algorithms for determining the states of nodes (critical or noncritical). The first proposed algorithm identifies most of the critical and noncritical dominator nodes from two-hop local subgraph and connected dominating set (CDS) information that limits the computational complexity to O(Delta(2)) and bit complexity to O(clog(2) n) where Delta is the maximum node degree, c is the critical node count, and n is the node count. The testbed experiments and simulation results show that this algorithm detects up to 93% of critical nodes and achieves up to 91% of state determination with low energy consumption. The second proposed algorithm, which is based on the first one, finds the states of all nodes by running a limited distributed depth-first search algorithm in unrecognized parts of the network without traversing the whole network. Comprehensive testbed experiments and simulation results reveal that, in the presence of a CDS, this algorithm finds all critical nodes with lower energy consumption than all existing algorithms., TUBITAK (Scientific and Technical Research Council of Turkey)Turkiye Bilimsel ve Teknolojik Arastirma Kurumu (TUBITAK) [113E470], This work was supported by TUBITAK (Scientific and Technical Research Council of Turkey) under grant 113E470.