Spatial Link Scheduling for SCDMA Multihop Cellular Networks: A Cross Layer Framework

Probability of error based Spatial Code Division Multiple Access scheduling algorithm is presented in this paper to systematically reuse the orthogonal CDMA codes in a given cell for Multihop Cellular Network. We assign and reuse the CDMA codes to peer-to-peer links such that the probability of error in all scheduled links are below certain threshold. The proposed scheduling algorithm PoE-LinkSchedule involves two phases. In the first phase we present a scheduling metric “Probability of Error (PoE)” as a function of first and second order statistics of wireless channel coefficients between nodes. The second phase presents a graph theoretical as well as PoE based centralized scheduling algorithm. For a graph of network with n number of nodes, U number of links and θ thickness, the proposed scheduling algorithm has computational complexity of O(Unlogn + Unθ) as opposed to O(U ^U ) in the case of exhaustive search algorithm. The performance of the proposed algorithm is evaluated in terms of spatial reuse and end-to-end throughput. We show that the proposed algorithm has considerably higher end-to-end throughput and higher spatial reuse compared to existing link scheduling algorithms.     

Fault‐tolerant deployment with k‐connectivity and partial k‐connectivity in sensor networks

Wireless sensor networks are prone to failure, so prolonging their lifetime and preventing loss of connectivity are significant. A simple but efficient strategy is to place redundant sensor nodes to establish multi‐connectivity. This paper explores how to add as few as possible nodes (called Steiner nodes) to a sensor network such that the resulting network is k‐connected or partially k‐connected. k‐connectivity means that each pair of the nodes, whether Steiner or original, is connected by at least k node‐disjoint paths, while partial k‐connectivity only requires such connectivity among original nodes. The contribution lies in two aspects. First, the approximation ratio of an existing k‐connectivity repair algorithm is decreased from O(k⁴α) to O(k³α), where α is the approximation ratio of any algorithm that finds a minimum‐weight k‐connected spanning subgraph of a weighted complete graph. This is the best result ever obtained. Second, the first generic partial k‐connectivity repair algorithm is proposed. It is proved that the approximation ratio of this algorithm is at most O(k³α). Copyright © 2008 John Wiley & Sons, Ltd.     

An improved algorithm for multicast topology discovery from end‐to‐end measurements

We present a new multicast topology inference algorithm called binary loss tree classification with hop count (HBLT). HBLT improves the previous algorithm of binary loss tree classification (BLT) not only in time complexity but also in misclassification probability and inference accuracy. The time complexity of HBLT is O(l²) instead of O(l³) required by BLT in the worst case, and O(l · log l) instead of O(l³) by BLT in the expected case, where l is the number of receivers in the multicast network. The misclassification probability of HBLT decreases more quickly than that of BLT as the number of probe packets increases. For correct classification, the inference accuracy of HBLT is always 1, i.e. the inferred tree is identical to the physical tree, whereas that of BLT is dependent on the shape of the physical tree and inversely proportional to the number of internal nodes with single child. We also show through simulation that HBLT requires fewer probe packets to infer the correct topology and hence has a lower misclassification probability and higher inference accuracy than BLT. Copyright © 2006 John Wiley & Sons, Ltd.     

Minimum latency joint scheduling and routing in wireless sensor networks

Wireless sensor networks are expected to be used in a wide range of applications from environment monitoring to event detection. The key challenge is to provide energy efficient communication; however, latency remains an important concern for many applications that require fast response. In this paper, we address the important problem of minimizing average communication latency for the active flows while providing energy-efficiency in wireless sensor networks. As the flows in some wireless sensor network can be long-lived and predictable, it is possible to design schedules for sensor nodes so that nodes can wake up only when it is necessary and asleep during other times. Clearly, the routing layer decision is closely coupled to the wakeup/sleep schedule of the sensor nodes. We formulate a joint scheduling and routing problem with the objective of finding the schedules and routes for current active flows with minimum average latency. By constructing a novel delay graph, the problem can be solved optimally by employing the M node-disjoint paths algorithm under FDMA channel model. We further present extensions of the algorithm to handle dynamic traffic changes and topology changes in wireless sensor networks.     

无线传感器网络中保障生命期和有效延时的数据融合调度方法

In scenarios of real-time data collection of long-term deployed Wireless Sensor Networks (WSNs), low-latency data collection with long network lifetime becomes a key issue. In this paper, we present a data aggregation scheduling with guaranteed lifetime and efficient latency in WSNs. We first construct a Guaranteed Lifetime Minimum Radius Data Aggregation Tree (GLMRDAT) which is conducive to reduce scheduling latency while providing a guaranteed network lifetime, and then design a Greedy Scheduling algorithM (GSM) based on finding the maximum independent set in conflict graph to schedule the transmission of nodes in the aggregation tree. Finally, simulations show that our proposed approach not only outperforms the state-of-the-art solutions in terms of schedule latency, but also provides longer and guaranteed network lifetime.     

Fast Multibit Decision Polar Decoder for Successive-Cancellation List Decoding

Successive-cancellation list (SCL) decoding for polar codes has the disadvantage of high latency owing to serial operations. To improve the latency, several algorithms with additional circuits have been proposed, but the area becomes larger. This paper proposes a fast multibit decision method having-high area efficiency based on the SCL decoding algorithm. First, multiple bits can be determined to reduce clock cycles using new nodes represented by the information bits and frozen bits. We propose the new nodes called the combined nodes and the other node in this paper. The combined nodes that combine redundant operations of the fast-simplified SC (fast-SSC) algorithm can increase area efficiency. The other node with bit patterns other than the node types of the fast-SSC algorithm performs an 8-bit multibit decision to reduce the number of decoding cycles. Latency is further reduced by applying a sphere decoding method to the other node. In addition, a sorter is proposed to reduce the critical path delay. As a large number of path metrics causes sorter delays, the proposed sorter can achieve high throughput with the small area. The proposed (1024, 512) SCL decoder showed negligible performance degradation in the simulation using Matlab and was synthesized using 65 nm CMOS technology. The proposed decoder achieves about 1.3Gbps with the small area. As a result, the area-throughput efficiency is at least 1.4 times higher than the state-of-the-art works over 1 Gbps.

     

Bidiagonalization and symmetric tridiagonalization by systolic arrays

We give a systolic algorithm and array for bidiagonalization of ann × n matrix inO(n logn) time, usingO(n ²) cells. Bandedness of the input matrix may be effectively exploited. If the matrix is banded, withp nonzero subdiagonals andq nonzero superdiagonals, then 4n ln(p+q)+O(n) clocks and 2n(p+q)+O((p+q) ²+n) cells are needed. This is faster than the best previously reported result by the factor log₂ e=1.44.... Moreover, in contrast to earlier systolic designs, which require the matrix to be preloaded into the array and the result matrix extracted after bidiagonalization, the present arrays are pipelined.This work was performed at Rensselaer Polytechnic Institute, Troy, New York 12180-3590. This research was partially supported by the Office of Naval Research under Contract N00014-86-K-0610.     

Interference-aware broadcast scheduling in wireless networks

In this paper, we study the Interference-Aware Broadcast Scheduling problem, where all nodes in the Euclidean plane have a transmission range and an interference range equal to r and α r for α ? 1, respectively. Minimizing latency is known to be NP-Hard even when α = 1. The network radius D, the maximum graph distance from the source to any node, is also known to be a lower bound.We formulate the problem as integer programs (IP) and optimally solve moderate-size instances. We also propose six variations of heuristics, which require no pre-processing of inputs, based on the number of receivers gained by each additional simultaneous transmitting node. The experimental results show that the best heuristics give solutions that exceed the optimal solutions by only 13–20%. Further, an O(αD) schedule is proven to exist yielding an O(α) approximation algorithm.     

Base on the Public Scientific Quality Improvement Research on Risk Early Warning of Online Shopping

LTE-A network offers data rates up to 1 Gbps which is 10?×?faster than LTE catering to growing demand of users. LTE improves user experience by reducing latency and increasing bandwidth efficiency. The emerging services and key enhancements such as Further Enhancement of Downlink Multiple-Input Multiple-Output (MIMO), Heterogeneous Networks, and Carrier Aggregation (CA) in LTE-A has improved performance of LTE-A networks. Scheduling optimization still remains one of the biggest challenges in high speed data transmission network. Scheduling in LTE-A networks are performed at various levels; User Equipment (UE), Serving Gateway (SGW), Air Interface and eNodeB. Remote Radio Head (RRH) is an extremely specialized device installed at antenna of eNodeB for optical to electrical signal conversion, amplification of signals and Uplink and Downlink Scheduling. Resource scheduling at Antenna of eNodeB module is constituted as a significant research optimization area. This paper proposes a soft computing based scheduler for RRH. Results of proposed technique are evaluated on Fairness Index, Throughput, Spectral Efficiency and Rank Indicator Distribution. The proposed algorithm aims to improve performance of scheduling. From experimental results, it is observed that proposed model succeeds to achieve significantly better performance as compared to state-of-art algorithms.

     

On the fault-tolerant routing in distributed loop networks

Based on their "Theorem 2", an O(δ)-time algorithm of searching for the shortest path between each pair of nodes in a double loop network was proposed by K.Mukhopadyaya, et al.(1995). While, unfortunately, it will be proved that both "Theorem 2" and its proof are in error. A new and more faster O(△)-time, △≤δ, algorithm will be presented in this paper.     

Cross-layer Routing Design in Cognitive Radio Networks by Colored Multigraph Model

In this paper, the cross-layer design routing in cognitive radio(CR) networks is studied. We propose a colored multigraph based model for the temporarily available spectrum bands, called spectrum holes in this paper. Based on this colored multigraph model, a polynomial time algorithm with complexity O(n ²) is also proposed to develop a routing and interface assignment, where n is the number of nodes in a CR network. Our algorithm optimizes the hop number of routing, meanwhile, the adjacent hop interference (AHI) is also optimized locally.

High‐throughput and low‐area implementation of orthogonal matching pursuit algorithm for compressive sensing reconstruction

Massive computation of the reconstruction algorithm for compressive sensing (CS) has been a major concern for its real‐time application. In this paper, we propose a novel high‐speed architecture for the orthogonal matching pursuit (OMP) algorithm, which is the most frequently used to reconstruct compressively sensed signals. The proposed design offers a very high throughput and includes an innovative pipeline architecture and scheduling algorithm. Least‐squares problem solving, which requires a huge amount of computations in the OMP, is implemented by using systolic arrays with four new processing elements. In addition, a distributed‐arithmetic‐based circuit for matrix multiplication is proposed to counterbalance the area overhead caused by the multi‐stage pipelining. The results of logic synthesis show that the proposed design reconstructs signals nearly 19 times faster while occupying an only 1.06 times larger area than the existing designs for N = 256, M = 64, and m = 16, where N is the number of the original samples, M is the length of the measurement vector, and m is the sparsity level of the signal.     

SDMAC: Selectively Directional MAC protocol for wireless mobile ad hoc networks

Using directional antennas in wireless mobile ad hoc networks can greatly improve the transmission range as well as the spatial reuse. However, it will also cause some problems such as deafness problem and hidden terminal problem, which greatly impair the network performance. This paper first proposes a MAC protocol called Selectively Directional MAC (SDMAC) that can effectively address these problems and significantly improve the network throughput. Then two improvements on SDMAC are proposed. The first one is to improve the network throughput by scheduling the packets in the queue (a scheme called Q-SDMAC), thus the head-of-line (HOL) blocking problem can be addressed. The second one is to relax the assumption that each node knows the relative directions of its neighboring nodes and use caches to buffer those relative directions (a scheme named Q-SDMAC using cache). Extensive simulations show that: (1) SDMAC can achieve much better performance than the existing MAC protocols using directional antennas; (2) The network throughput can be significantly improved by scheduling the packets in the queue; (3) Using caches can still achieve high network throughput when nodes are moving; and (4) Network throughput decreases when directional antennas have side lobe gain.

Optimal Packet Scheduling in Tree-Structured LEO Satellite Clusters

Clusters of mobile (LEO) satellites, flying at a non-geostationary orbit, have been recently proposed, designed and made operational for achieving a global coverage of roaming users. An example of these is Teledesic. The satellites of these clusters are equipped with a radio frequency switch and connected via intersatellite links to form a specific topology. Uncoordinated packet transmission in these systems may result in collisions. Collided packets must be retransmitted, with an obvious degradation in performance, in terms of both bandwidth usage and delay. This performance degradation can be overcome by a proper scheduling of the packets. In this paper, we consider optimal (namely minimum length) packet scheduling in LEO satellite clusters. We present a preprocessing algorithm which, together with the optimal, polynomial time, packet scheduling algorithm for isolated satellites, produces an optimal schedule in tree-connected clusters. The overall algorithm inherit the time complexity of the optimal one for isolated systems, and is O(N ⁴) for a cluster serving N roaming users.     

Spanning tree based algorithms for low latency and energy efficient data aggregation enhanced convergecast (DAC) in wireless sensor networks

Many wireless sensor networks (WSNs) employ battery-powered sensor nodes. Communication in such networks is very taxing on its scarce energy resources. Convergecast – process of routing data from many sources to a sink – is commonly performed operation in WSNs. Data aggregation is a frequently used energy-conversing technique in WSNs. The rationale is to reduce volume of communicated data by using in-network processing capability at sensor nodes. In this paper, we address the problem of performing the operation of data aggregation enhanced convergecast (DAC) in an energy and latency efficient manner. We assume that all the nodes in the network have a data item and there is an a priori known application dependent data compression factor (or compression factor), γ, that approximates the useful fraction of the total data collected.The paper first presents two DAC tree construction algorithms. One is a variant of the Minimum Spanning Tree (MST) algorithm and the other is a variant of the Single Source Shortest Path Spanning Tree (SPT) algorithm. These two algorithms serve as a motivation for our Combined algorithm (COM) which generalized the SPT and MST based algorithm. The COM algorithm tries to construct an energy optimal DAC tree for any fixed value of α (= 1 − γ), the data growth factor. The nodes of these trees are scheduled for collision-free communication using a channel allocation algorithm. To achieve low latency, these algorithms use the β-constraint, which puts a soft limit on the maximum number of children a node can have in a DAC tree. The DAC tree obtained from energy minimizing phase of tree construction algorithms is re-structured using the β-constraint (in the latency minimizing phase) to reduce latency (at the expense of increasing energy cost). The effectiveness of these algorithms is evaluated by using energy efficiency, latency and network lifetime as metrics. With these metrics, the algorithms’ performance is compared with an existing data aggregation technique. From the experimental results, for a given network density and data compression factor γ at intermediate nodes, one can choose an appropriate algorithm depending upon whether the primary goal is to minimize the latency or the energy consumption.     

Golden codeword–based modulation schemes for single‐input multiple‐output systems

The Golden code has full rate and full diversity. The Golden codeword matrix contains two pairs of super symbols. Based on one pair of super symbols, two modulation schemes, Golden codeword–based M‐ary quadrature amplitude modulation (GC‐MQAM) and component‐interleaved GC‐MQAM (CI‐GC‐MQAM), are proposed for single‐input multiple‐output (SIMO) systems. Since the complexities of the maximum likelihood detection for the proposed GC‐MQAM and CI‐GC‐MQAM are proportional to O(M²) and O(M⁴), respectively, low complexity detection schemes for the proposed GC‐MQAM and CI‐GC‐MQAM are further proposed. In addition, the theoretical average bit error probabilities (ABEPs) for the proposed GC‐MQAM and CI‐GC‐MQAM are derived. The derived ABEPs are validated through Monte Carlo simulations. Simulation and theoretical results show that the proposed GC‐MQAM can achieve the error performance of signal space diversity. Simulation and theoretical results further show that the proposed CI‐GC‐16QAM, ‐64QAM, and ‐256QAM with three receive antennas can achieve approximately 2.2, 2.0, and 2.1 dB gain at a bit error rate of 4 × 10^?6 compared with GC‐16QAM, ‐64QAM, and ‐256QAM, respectively.     

A slot‐based BS scheduling with maximum latency guarantee and capacity first in 802.16e networks

The IEEE 802.16e standard specifies the QoS support at the MAC level for wireless broadband access network. To meet the QoS requirements, an efficient scheduling algorithm at base station (BS), which is not defined in the standard, is necessary for slots allocation. In this paper, a Slot‐based BS scheduling algorithm with Maximum Latency Guarantee and Capacity First (SMLG‐CF) is proposed. With SMLG‐CF, the connection request is satisfied with highest slot capacity first. Together with the use of dynamic sub‐frame adjustment, the overall system transmission can be efficiently improved. Through the finer slots calculation and accurate transmission time scheduling, the maximum latency guarantee can be better achieved for urgent requests. In the simulation, we compare the proposed mechanism with the deficit fair priority queue scheduling algorithm and the Highest Urgency First scheduling algorithm. The simulation results reveal that SMLG‐CF outperforms both algorithms from the aspect of maximum latency violation rate and average transmission rate. Copyright © 2011 John Wiley & Sons, Ltd.     

A distributed battery recovery aware topology control algorithm for wireless sensor networks

Battery recovery effect is a phenomenon that the available capacity of a battery could increase if the battery can sleep for a certain period of time since its last discharging. Accordingly, the battery can work for a longer time when it takes some rests between consecutive discharging processes than when it works all the time. However, this effect has not been considered in the design of energy‐efficient topology control algorithms for wireless sensor networks. In this paper, we propose a distributed battery recovery effect aware connected dominating set constructing algorithm (BRE‐CDS) for wireless sensor networks. In BRE‐CDS, each network node periodically decides to join the connected dominating set or not. Nodes that have slept in the preceding round have priority to join the connected dominating set in the current round while nodes that have worked in the preceding round are encouraged to take sleep in the current round for battery recovery. Detailed algorithm design is presented. The computational complexity of BRE‐CDS is deduced to be O(D²), where D is node degree. Simulation results show that BRE‐CDS can significantly prolong the network lifetime as compared with existing work. Copyright © 2016 John Wiley & Sons, Ltd.     

SYNC‐NET: distributed time synchronization in clustered sensor networks

Time synchronization is essential for several ad‐hoc network protocols and applications, such as TDMA scheduling and data aggregation. In this paper, we propose a time synchronization framework for clustered, multi‐hop sensor networks. We assume that relative node synchronization is sufficient, that is, consensus on one time value is not required. Our goal is to divide the network into connected synchronization regions (nodes within two‐hops) and perform inter‐regional synchronization in O(LLSync) × N_iter time, where O(LLSync) denotes the complexity of the underlying low‐level synchronization technique (used for single‐hop synchronization), and N_iter denotes the number of iterations where the low‐level synchronization protocol is invoked. Thus, our main objective is rapid convergence. We propose novel fully distributed protocols, SYNC‐IN and SYNC‐NET, for regional and network synchronization, respectively, and prove that N_iter is O(1) for all protocols. Our framework does not require any special node capabilities (e.g., being global positioning systems (GPS)‐enabled), or the presence of reference nodes in the network. Our framework is also independent of the particular clustering, inter‐cluster routing, and low‐level synchronization protocols. We formulate a density model for analyzing inter‐regional synchronization, and evaluate our protocols via extensive simulations. Copyright © 2007 John Wiley & Sons, Ltd.     

An Isochronous Testing Strategy for Hierarchical Adaptive Distributed System-Level Diagnosis

Distributed System-level diagnosis allows the fault-free components of a fault-tolerant distributed system to determine which components of the system are faulty and which are fault-free. The time it takes for nodes running the algorithm to diagnose a new event is called the algorithm's latency. In this paper we present a new distributed system-level diagnosis algorithm which presents a latency of O(log N) testing rounds, for a system of N nodes. A previous hierarchical distributed system-level diagnosis algorithm, Hi-ADSD, presents a latency of O(log ² N) testing rounds. Nodes are grouped in progressively larger logical clusters for the purpose of testing. The algorithm employs an isochronous testing strategy that forces all fault-free nodes to execute tests on clusters of the same size each testing round. This strategy is based on two main principles: a tested node must test its tester in the same round; a node only accepts tests according to a lexical priority order. We present formal proofs that the algorithm's latency is at most 2log N – 1 testing rounds and that the testing strategy of the algorithm leads to the execution of isochronous tests. Simulation results are shown for systems of up to 64 nodes.