Adaptive Filtering Algorithm in Clock Calibration System

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

Connected Dominating Sets in Wireless Networks with Different Transmission Ranges

Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed to serve as a virtual backbone. The CDS of a graph representing a network has a significant impact on the efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which all nodes have the same transmission ranges. However, in practice, the transmission ranges of all nodes are not necessarily equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present two efficient approximation algorithms to obtain a minimum CDS. The performance ratio of these algorithms is constant if the ratio of the maximum transmission range over the minimum transmission range in the network is bounded. These algorithms can be implemented as distributed algorithms. Furthermore, we show a size relationship between a maximal independent set and a CDS as well as a bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.     

Zone-based virtual backbone formation in wireless ad hoc networks

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

Construction and maintenance of virtual backbone in wireless networks

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

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

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

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

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

On Construction of Virtual Backbone in Wireless Ad Hoc Networks with Unidirectional Links

Since there is no fixed infrastructure in wireless ad hoc networks , virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem. The virtual backbone construction has been studied extensively in {em undirected} graphs, especially in unit disk graphs, in which each node has the same transmission range. In practice, however, transmission ranges of all nodes are not necessarily equal. In this paper, we model such a network as a disk graph, where unidirectional links are considered. To study the virtual backbone construction in disk graphs, we consider two problems: Strongly Connected Dominating Set (SCDS) and Strongly Connected Dominating and Absorbing Set (SCDAS). We propose a constant approximation algorithm and discuss its improvements for the SCDS problem . We also propose a heuristic for the SCDAS problem. Through extensive simulations, we verify our theoretical analysis and also demonstrate that the SCDS can be extended to form an SCDAS with marginal extra overhead.     

Ultra-low power incremental delta-sigma ADC for energy harvesting sensor applications

This paper presents an ultra-low power incremental \({\varDelta {\Sigma }}\) ADC with flexible sampling frequency, accuracy, and operational duty-cycle. The flexibility and low leakage power enable efficient scaling of average power together with performance. This allows simultaneous optimization of the sensor system (1) for various multiplexed, both on-chip and off-chip sensor interfaces, and (2) for a wide range of available harvested energy. The architecture allows further flexibility as it can be used in regular continuous \({\varDelta {\Sigma }}\) mode as well, without trading off accuracy. The ADC was implemented in a 180 nm CMOS process, on the same ASIC with a temperature sensor, pressure sensor and energy harvesting functionalities. The ADC has a nominal power consumption of \(1.3\,\upmu\)W, SNDR of 68 dB and BW of 200 Hz, denoting a \(FOM_w =1.58\) pJ/conv.     

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

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

Link scheduling for throughput maximization in multihop wireless networks under physical interference

We consider the problem of link scheduling for throughput maximization in multihop wireless networks. Majority of previous methods are restricted to graph-based interference models. In this paper we study the link scheduling problem using a more realistic physical interference model. Through some key observations about this model, we develop efficient link scheduling algorithms by exploiting the intrinsic connections between the physical interference model and the graph-based interference model. For one variant of the problem where each node can dynamically adjust its transmission power, we design a scheduling method with O(g(E)) approximation to the optimal throughput capacity where g(E) denotes length diversity. For the other variant where each node has a fixed but possible different transmission powers for different nodes, we design a method with O(g(E))-approximation ratio when the transmission powers of all nodes are within a constant factor of each other, and in general with an approximation ratio of \(O(g(E)\log \rho )\) where \(\log \rho\) is power diversity. We further prove that our algorithm for fixed transmission power case retains O(g(E)) approximation for any length-monotone, sub-linear fixed power setting. Furthermore, all these approximation factors are independent of network size .     

Secret-Sharing Schemes for Very Dense Graphs

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph “hard” for secret-sharing schemes (that is, they require large shares), we study very dense graphs, that is, graphs whose complement contains few edges. We show that if a graph with \(n\) vertices contains \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges for some constant \(0 \le \beta <1\), then there is a scheme realizing the graph with total share size of \(\tilde{O}(n^{5/4+3\beta /4})\). This should be compared to \(O(n^2/\log (n))\), the best upper bound known for the total share size in general graphs. Thus, if a graph is “hard,” then the graph and its complement should have many edges. We generalize these results to nearly complete \(k\)-homogeneous access structures for a constant \(k\). To complement our results, we prove lower bounds on the total share size for secret-sharing schemes realizing very dense graphs, e.g., for linear secret-sharing schemes, we prove a lower bound of \(\Omega (n^{1+\beta /2})\) for a graph with \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges.     

An Accurate Performance Analysis for Regenerative Multi-hop Relaying in Wireless Networks Over Composite Multipath/Shadowed Fading

This paper presents and evaluates the performance of wireless networks that utilize the decode-and-forward relay. This multi-hop relaying scheme communicates over Extended Generalized-\({\mathcal {K}}\) (\(\hbox {EG}{\mathcal {K}}\)) composite fading channels to create performance evaluation. To this effect, new exact and easy to compute formulas for several performance metrics are derived. More specifically, new and exact-form mathematical formulas are derived for the cumulative distribution function, the generalized moments of the overall end-to-end signal-to-noise ratio, the outage probability (\({\hbox {P}}_{\text{out}}\)), the ergodic capacity (\({\mathcal {C}}_{\text{Ergodic}}\)), the moment generating function, and the average error probability (\({\hbox {Pr(e)}}\)) for different modulation schemes. Moreover, we carried out a series of computer simulation experiments in order to testify the accuracy of the derived framework. Finally, we discussed the impact of different parameters including fading/shadowing parameters, transmitted power and the number of hops on the derived expressions.     

High-Accuracy Time-Mode Duty-Cycle-Modulation-Based Temperature Sensor for Energy-Efficient System Applications

This paper presents a new time-mode duty-cycle-modulation-based high-accuracy temperature sensor. Different from the well-known \({\varSigma }{\varDelta }\) ADC-based readout structure, this temperature sensor utilizes a temperature-dependent oscillator to convert the temperature information into temperature-related time-mode parameter values. The useful output information of the oscillator is the duty cycle, not the absolute frequency. In this way, this time-mode duty-cycle-modulation-based temperature sensor has superior performance over the conventional inverter-chain-based time domain types. With a linear formula, the duty-cycle output streams can be converted into temperature values. The design is verified in 65nm standard digital CMOS process. The verification results show that the worst temperature inaccuracy is kept within 1\(\,^{\circ }\mathrm{C}\) with a one-point calibration from \(-\)55 to 125 \(^{\circ }\mathrm{C}\). At room temperature, the average current consumption is only 0.8 \(\upmu \)A (1.1\(\,\upmu \)A in one phase and 0.5 \(\upmu \)A in the other) with 1.2 V supply voltage, and the total energy consumption for a complete measurement is only 0.384 \({\hbox {nJ}}\).     

Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks

Connected dominating set (CDS) has been proposed as virtual backbone or spine of wireless ad hoc networks. Three distributed approximation algorithms have been proposed in the literature for minimum CDS. In this paper, we first reinvestigate their performances. None of these algorithms have constant approximation factors. Thus these algorithms cannot guarantee to generate a CDS of small size. Their message complexities can be as high as O(n ²), and their time complexities may also be as large as O(n ²) and O(n ³). We then present our own distributed algorithm that outperforms the existing algorithms. This algorithm has an approximation factor of at most 8, O(n) time complexity and O(nlogn) message complexity. By establishing the (nlogn) lower bound on the message complexity of any distributed algorithm for nontrivial CDS, our algorithm is thus message-optimal.     

A pruning ensemble model of extreme learning machine with $$L_{1/2}$$ regularizer

Extreme learning machine (ELM) as an emerging branch of machine learning has shown its good generalization performance at a very fast learning speed. Nevertheless, the preliminary ELM and other evolutional versions based on ELM cannot provide the optimal solution of parameters between the hidden and output layer and cannot determine the suitable number of hidden nodes automatically. In this paper, a pruning ensemble model of ELM with \(L_{1/2} \) regularizer (PE-ELMR) is proposed to solve above problems. It involves two stages. First, we replace the original solving method of the output parameter in ELM to a minimum squared-error problem with sparse solution by combining ELM with \(L_{1/2}\) regularizer. Second, in order to get the required minimum number for good performance, we prune the nodes in hidden layer with the ensemble model, which reflects the superiority in searching the reasonable hidden nodes. Experimental results present the good performance of our method PE-ELMR, compared with ELM, OP-ELM and PE-ELMR (L1), for regression and classification problems under a variety of benchmark datasets.     

Connected dominating sets in disk graphs with bidirectional links

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

An Investigation of Massive Gain in Hybrid Configurable Cylindrical Dielectric Resonator Antenna

Delay Tolerant Networks (DTNs) have attracted various interests these days. Since DTNs are subject to high loss rate, large delay, intermittent connection, and even no end-to-end connectivity, relay nodes, such as throwboxes, are deployed to enhance network performance. Internet-based systems have contemporaneous connectivity between location-distributed nodes, and this does not apply to DTNs. Thus, the traditional relay node deployment strategies are no longer suitable for DTNs. In this paper, we propose a novel strategy, named Connection-2 (\(CO_2\)), to deploy throwboxes to enhance the fault tolerance of DTNs. \(CO_2\) constructs a 2-connected DTN using an approximation algorithm. Every mobile node in the 2-connected DTN can reach another mobile node via two or more node-disjoint paths within its mobility range. While enhancing fault tolerance, the number of throwboxes that \(CO_2\) requires is small. We conduct various experiments based on the simulation of the real Tuscaloosa bus transit system and compare its performance with two popular strategies. Experimental results show that \(CO_2\) is effective.     

Capacity and Channel Coding for Wireless Point-to-Point <Emphasis Type="Italic">Z</Emphasis><Superscript>2</Superscript> Channel

In this paper, we derive the capacity of the asymmetric \({\text{Z}}^{2}\)-channel, which has been presented for the first time as an optimization problem. Similar to the Z-Channel, the proposed \({\text{Z}}^{2}\)-channel can be modelled as a practical interference wireless channel. In addition, the capacity behavior of \({\text{Z}}^{2}\)-channel is discussed and some examples and simulation results for the capacity is presented. Also a code plan has been applied for \({\text{Z}}^{2}\)-channel, based on repetition code to simulate its performance and compare it with the original Z-channel. In conclusion, simulation results show that the \({\text{Z}}^{2}\)-channel can be used widely for different operating points.     

无线传感器网络中一种能量均衡的基于连通支配集的数据收集算法

采用连通支配集来构建虚拟骨干可以减轻无线传感器网络的广播风暴问题.目前已有大量工作通过构造最小连通支配集形成网络虚拟骨干来进行高效数据收集.然而,最小连通支配集并不能有效均衡节点的能量耗费,导致网络生命周期较短.提出了一种能量均衡的基于连通支配集的分布式算法EBCDS来进行数据收集,通过选择能量水平和度均比较大的节点组成连通支配集,支配集中的节点组成一个规模不大但具有较高能量水平的网络骨干.网络中的所有数据沿骨干在较小的寻路空间中转发,能够节省节点能量,使骨干节点不会因为能量不足而过早死亡.理论分析表明,EBCDS能以O(nlogn)的消息复杂度构造连通支配集,仿真实验表明,EBCDS能有效节省节点能耗并延长网络生命周期.     

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

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