Energy-efficient topology control algorithm for maximizing network lifetime in wireless sensor networks with mobile sink

Uneven energy consumption is an inherent problem in wireless sensor networks characterized by multi-hop routing and many-to-one traffic pattern. Such unbalanced energy dissipation can significantly reduce network lifetime. In this paper, we study the problem of prolonging network lifetime in large-scale wireless sensor networks where a mobile sink gathers data periodically along the predefined path and each sensor node uploads its data to the mobile sink over a multi-hop communication path. By using greedy policy and dynamic programming, we propose a heuristic topology control algorithm with time complexity O(n(m + n log n)), where n and m are the number of nodes and edges in the network, respectively, and further discuss how to refine our algorithm to satisfy practical requirements such as distributed computing and transmission timeliness. Theoretical analysis and experimental results show that our algorithm is superior to several earlier algorithms for extending network lifetime.     

A fast fault-identification algorithm for bijective connection graphs using the PMC model

Diagnosis of reliability is an important topic for interconnection networks. Under the classical PMC model, Dahura and Masson [5] proposed a polynomial time algorithm with time complexity O(N^2.5) to identify all faulty nodes in an N-node network. This paper addresses the fault diagnosis of so called bijective connection (BC) graphs including hypercubes, twisted cubes, locally twisted cubes, crossed cubes, and Möbius cubes. Utilizing a helpful structure proposed by Hsu and Tan [20] that was called the extending star by Lin et al. [24], and noting the existence of a structured Hamiltonian path within any BC graph, we present a fast diagnostic algorithm to identify all faulty nodes in O(N) time, where N = 2ⁿ, n ? 4, stands for the total number of nodes in the n-dimensional BC graph. As a result, this algorithm is significantly superior to Dahura–Masson’s algorithm when applied to BC graphs.     

Conditional fault-tolerant hamiltonicity of star graphs

The star graph possesses many nice topological properties. In this study, we show that for any n-dimensional star graph (n ⩾ 4) with ⩽2n − 7 edge faults in which each node is incident to at least two non-faulty edges, there exists a fault-free Hamiltonian cycle. Compared with the corresponding study in hypercube, our method is rather succinct. Additionally, we also show the probability that an n dimensional star graph with arbitrary 2n − 7 faulty edges at most is Hamiltonian is very close to one.     

Broadcast in the rendezvous model

In many large, distributed or mobile networks, broadcast algorithms are used to update information stored at the nodes. In this paper, we propose a new model of communication based on rendezvous and analyze a multi-hop distributed algorithm to broadcast a message in a synchronous setting. In the rendezvous model, two neighbors u and v can communicate if and only if u calls v and v calls u simultaneously. Thus nodes u and v obtain a rendezvous at a meeting point. If m is the number of meeting points, the network can be modeled by a graph of n vertices and m edges. At each round, every vertex chooses a random neighbor and there is a rendezvous if an edge has been chosen by its two extremities. Rendezvous enable an exchange of information between the two entities. We get sharp lower and upper bounds on the time complexity in terms of number of rounds to broadcast: we show that, for any graph, the expected number of rounds is between ln n and O (n²). For these two bounds, we prove that there exist some graphs for which the expected number of rounds is either O (ln (n)) or Ω (n²). For specific topologies, additional bounds are given.     

Peri-Watchdog: Hunting for hidden botnets in the periphery of online social networks

In order to evade detection of ever-improving defense techniques, modern botnet masters are constantly looking for new communication platforms for delivering C&C (Command and Control) information. Attracting their attention is the emergence of online social networks such as Twitter, as the information dissemination mechanism provided by these networks can naturally be exploited for spreading botnet C&C information, and the enormous amount of normal communications co-existing in these networks makes it a daunting task to tease out botnet C&C messages.Against this backdrop, we explore graph-theoretic techniques that aid effective monitoring of potential botnet activities in large open online social networks. Our work is based on extensive analysis of a Twitter dataset that contains more than 40 million users and 1.4 billion following relationships, and mine patterns from the Twitter network structure that can be leveraged for improving efficiency of botnet monitoring. Our analysis reveals that the static Twitter topology contains a small-sized core sugraph, after removing which, the Twitter network breaks down into small connected components, each of which can be handily monitored for potential botnet activities. Based on this observation, we propose a method called Peri-Watchdog, which computes the core of a large online social network and derives the set of nodes that are likely to pass botnet C&C information in the periphery of online social network. We analyze the time complexity of Peri-Watchdog under its normal operations. We further apply Peri-Watchdog on the Twitter graph injected with synthetic botnet structures and investigate the effectiveness of Peri-Watchdog in detecting potential C&C information from these botnets.To verify whether patterns observed from the static Twitter graph are common to other online social networks, we analyze another online social network dataset, BrightKite, which contains evolution of social graphs formed by its users in half a year. We show not only that there exists a similarly relatively small core in the BrightKite network, but also this core remains stable over the course of BrightKite evolution. We also find that to accommodate the dynamic growth of BrightKite, the core has to be updated about every 18 days under a constrained monitoring capacity.     

Utilize 100% redundancy to offer higher-level multiple fault restoration in WDM networks without wavelength conversion

This study addresses the problem of achieving higher-level multi-fault restoration in wavelength division multiplexing (WDM) networks with no wavelength conversion capability. A heuristic scheme, designated as the Directional Cycle Decomposition Algorithm (DCDA), is developed to maximize the number of tolerable faults utilizing only 100% redundancy in WDM networks without wavelength conversion. The redundancy is calculated as the required spare capacity over the given working capacity. The process of identifying the maximum number of tolerable faults is modeled as a constrained ring cover set problem. DCDA decomposes this problem into three steps and has an overall computational complexity of O(∣E∣∣V∣(C + 1) + ∣E∣(C² + 1)), where ∣V∣, ∣E∣ and C represent the number of vertices, the number of edges in the graph and the number of cycles in the cycle cover, respectively. The evaluation results reveal that the average number of tolerable simultaneous faults increases considerably under DCDA and the maximum number of tolerable simultaneous faults approaches the optimal solution provided by the brute-force method. DCDA facilitates an improved best-effort multi-fault restorability for a variety of planar and non-planar network topologies. An analytical method is proposed to facilitate a rapid estimation of the multi-fault restorability in a network using DCDA without the need for experimental evaluations. In addition, an approximation method is developed to obtain an estimate of the multi-fault restorability directly from DCDA without the requirement for a detailed knowledge of the network topology and restoration routes. The results show that the average errors in the approximated restorability values obtained using this method range from 0.12% (New Jersey) to 1.58% (Cost 239).     

On identifying codes that are robust against edge changes

Assume that G = (V, E) is an undirected graph, and C ⊆ V. For every v ∈ V, denote I_r(G; v) = {u ∈ C: d(u,v) ≤ r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets I_r(G; v) for v ∈ V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r = 1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide.     

Social network site use,mobile personal talk and social capital among teenagers

Social network sites (SNSs) and mobile phones are becoming increasingly important in teenagers’ lives. Using data collected from a nationally representative survey (N = 800), this study explores the variation of social capital by SNS adoption, different SNS activities, and mobile personal talk among teenagers. The results indicate that SNS adoption and mobile personal talk can not only enhance teenagers’ close ties with friends, but also jointly promote teenagers’ civic engagement. Among SNS users, mobile personal talk also increase teens’ network capital. Different SNS activities such as commenting on friend’s Facebook pictures and joining Facebook groups have different relationships with social capital, and such relationships are moderated by mobile personal talk.     

On using forward error correction for loss recovery in optical burst switched networks

An important issue in optical burst switched (OBS) networks is the loss of bursts at intermediate nodes due to contention. Such contention losses, usually do not mean a situation of congestion. In this paper, we propose for the first time, a loss recovery mechanism using Forward Error Correction (FEC) to recover bursts that are lost due to contention. Using FEC, for every K bursts, N − K redundant bursts are also sent to the destination. This redundancy can be used to recover from losses in the K data bursts. Our mechanism can also be used to recover from losses due to network component (link/node) failures. We demonstrate the effectiveness of our mechanism by comparing with no protection and 1 + 1 protection using simulation studies.     

On reliability of the folded hypercubes

In this paper, we explore the 2-extra connectivity and 2-extra-edge-connectivity of the folded hypercube FQ_n. We show that κ₂(FQ_n) = 3n − 2 for n ⩾ 8; and λ₂(FQ_n) = 3n − 1 for n ⩾ 5. That is, for n ⩾ 8 (resp. n ⩾ 5), at least 3n − 2 vertices (resp. 3n − 1 edges) of FQ_n are removed to get a disconnected graph that contains no isolated vertices (resp. edges). When the folded hypercube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.     

An Efficient Algorithm for the k-Pairwise Disjoint Paths Problem in Hypercubes

A graph G(V, E) (|V|⩾2k) satisfies property A_k if, given k pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) of V(G), there are k mutually node-disjoint paths, one connecting s_i and t_i for each i, 1⩽i⩽k. A necessary condition for any graph to satisfy A_k is that it is (2k−1)-connected. Hypercubes are important interconnection topologies for parallel computation and communication networks. It has been known that hypercubes of dimension n (which are n-connected) satisfy A_⌈n/2⌉. In this paper we give an algorithm which, given k=⌈n/2⌉ pairs of distinct nodes (s₁, t₁), …, (s_k, t_k) in the n-dimensional hypercube, finds the k disjoint paths of length at most n+⌈log n⌉+1 in O(n² log* n) time.     

An Algorithm for the Quillen–Suslin Theorem for Quotients of Polynomial Rings by Monomial Ideals

This paper presents an algorithm for the Quillen–Suslin Theorem for quotients of polynomial rings by monomial ideals, that is, quotients of the form A = k [ x₀, . . . ,x_n ] / I, with I a monomial ideal and k a field. Vorst proved that finitely generated projective modules over such algebras are free. Given a finitely generated module P, described by generators and relations, the algorithm tests whether P is projective, in which case it computes a free basis forP .     

Posting,commenting, and tagging: Effects of sharing news stories on Facebook

Social networking sites such as Facebook provide new ways of sharing news stories that allow users to act as opinion leaders in their networks, encourage discussion, and potentially increase their involvement in current events. This study identifies the particular features of Facebook that facilitate the discussion of news and tests their effects on involvement and feelings of influence. Participants (N = 265) in a 3 (Broadcast level: news feed vs. wall post vs. direct message) × 3 (Elaboration: opinion vs. question vs. no comment) × 2 (Involving-friends: tag vs. no tag) between-subjects factorial experiment were randomly assigned to share a story from a news website on Facebook. Results show that user involvement in the news content depends on the social affordances of the site, particularly those that allow for audience customization and those that drive network feedback. Asking the network’s opinions and targeting specific friends led to greater involvement in the news content. Discussion through comments led to a greater sense of influence and greater involvement for those sharing the news story. These findings highlight the importance of encouraging individuals to act as sources of information in their networks to drive engagement in current events in the changing news landscape.     

Gröbner Bases Applied to Finitely Generated Field Extensions

Using a constructive field-ideal correspondence it is shown how to compute the transcendence degree and a (separating) transcendence basis of finitely generated field extensionsk (x) / k(g), resp. how to determine the (separable) degree if k(x) / k(g) is algebraic. Moreover, this correspondence is used to derive a method for computing minimal polynomials and deciding field membership. Finally, a connection between certain intermediate fields of k(x) / k(g) and a minimal primary decomposition of a suitable ideal is described. For Galois extensions the field-ideal correspondence can also be used to determine the elements of the Galois group.     

EEMC: An energy-efficient multi-level clustering algorithm for large-scale wireless sensor networks

Wireless sensor networks can be used to collect environmental data from the interested area using multi-hop communication. As sensor networks have limited and non-rechargeable energy resources, energy efficiency is a very important issue in designing the topology, which affects the lifetime of sensor networks greatly. In this paper, the energy consumption is modeled and compared under the flat scheme and the clustering scheme, respectively. Motivated by the analysis, we propose an energy-efficient multi-level clustering algorithm called EEMC, which is designed to achieve minimum energy consumption in sensor networks. The cluster head election scheme is also considered in EEMC. EEMC terminates in O(log log N) iterations given N nodes. When the path loss exponent is 2, EEMC also achieves minimum latency. We focus on the case where sink node is remotely located and sensor nodes are stationary. Simulation results demonstrate that our proposed algorithm is effective in prolonging the network lifetime of a large-scale network, as well as low latency and moderate overhead across the network.     

Taylor approximation for hybrid systems

We propose a new approximation technique for Hybrid Automata. Given any Hybrid Automaton H, we call Approx(H, k) the Polynomial Hybrid Automaton obtained by approximating each formula ϕ in H with the formulae ϕ_k obtained by replacing the functions in ϕ with their Taylor polynomial of degree k. We prove that Approx(H, k) is an over-approximation of H. We study the conditions ensuring that, given any ϵ > 0, some k₀ exists such that, for all k > k₀, the “distance” between any vector satisfying ϕ_k and at least one vector satisfying ϕ is less than ϵ. We study also conditions ensuring that, given any ϵ > 0, some k₀ exists such that, for all k > k₀, the “distance” between any configuration reached by Approx(H, k) in n steps and at least one configuration reached by H in n steps is less than ϵ.     

On Computations in Kummer Extensions

Let k be an algebraic number field containing a primitive m th root of unity. An extension K = k([m ] μ) of k with μ ∈ k is called a Kummer extension. These extensions have been studied extensively in the past and they play an important role in class field theory. Recently many new algorithms dealing with Kummer extensions emerged. In this paper we will give algorithms to solve two problems, which are of particular interest; the computation of the relative discriminant dK / k and the computation of Hilbert norm symbols.     

Conditional diagnosability of hypercubes under the comparison diagnosis model

Processor fault diagnosis plays an important role in multiprocessor systems for reliable computing, and the diagnosability of many well-known networks has been explored. Lai et al. proposed a novel measure of diagnosability, called conditional diagnosability, by adding an additional condition that any faulty set cannot contain all the neighbors of any vertex in a system. We make a contribution to the evaluation of diagnosability for hypercube networks under the comparison model and prove that the conditional diagnosability of n-dimensional Hypercube Q_n is 3(n ? 2) + 1 for n ? 5. The conditional diagnosability of Q_n is about three times larger than the classical diagnosability of Q_n.     

Modal analysis and modified cascade neural networks in identification of geometrical parameters of circular arches

A hybrid computational system, composed of the finite element method (FEM) and cascade neural network system (CNNs), is applied to the identification of three geometrical parameters of elastic arches, i.e. span l, height f and cross-sectional thickness h. FEM is used in the direct (forward) analysis, which corresponds to the mapping α = {l, f, h} → {ω_j}, where: α – vector of control parameters, ω_j – arch eigenfrequencies. The reverse analysis is related to the identification procedure in which the reverse mapping is performed {ω_j} → {α_i}. For the identification purposes a recurrent, three level CNNs of structure (D^k-H^k-1)_s was formulated, where: k – recurrence step, s = I, II, III-levels of cascade system. The Semi-Bayesian approach is introduced for the design of CNNs applying the MML Maximum Marginal Likelihood) criterion. The computation of hyperparameters is performed by means of the Bayesian procedure evidence. The numerical analysis proves a great numerical efficiency of the proposed hybrid approach for both the perfect (noiseless) values of eigenfrequencies and noisy ones simulated by an added artificial noise.     

Dielectric and piezoelectric properties of [0 0 1] and [0 1 1]-poled relaxor ferroelectric PZN–PT and PMN–PT single crystals

The properties of PZN–PT and PMN–PT single crystals of varying compositions and orientations have been investigated. Among the various compositions studied, [0 0 1]-optimally poled PZN-(6–7)%PT and PMN-30%PT exhibit superior dielectric and piezoelectric properties, with K^T ≈ 6800–8000, d₃₃ ≈ 2800 pC/N, d₃₁ ≈ −(1200–1800) pC/N for PZN-(6–7)%PT; and K^T = 7500–9000, d₃₃ = 2200–2500 pC/N and d₃₁ = −(1100–1400) pC/N for PMN-30%PT. These two compositions are also fairly resistant to over-poling. The [0 0 1]-poled electromechanical coupling factors (k₃₃, k₃₁ and k_t) are relatively insensitive to crystal composition. [0 1 1]-optimally poled PZN-7%PT single crystal also exhibits extremely high d₃₁ values of up to −4000 pC/N with k₃₁ ≈ 0.90–0.96. While [0 1 1]-poled PZN-7%PT single crystal becomes over-poled with much degraded properties when poled at and above 0.6 kV/mm, PZN-6%PT crystal shows no signs of over-poling even when poled to 2.0 kV/mm. The presence of a certain amount (i.e., 10–15%) of orthorhombic phase in a rhombohedral matrix has been found to be responsible for the superior transverse piezoelectric properties of [0 1 1]-optimally poled PZN-(6–7)%PT. The present work shows that flux-grown PZN–PT crystals exhibit superior and consistent properties and improved over-poling resistance to flux-grown PMN–PT crystals and that, for or a given crystal composition, flux-grown PMN–PT crystals exhibit superior over-poling resistance to their melt-grown counterparts.