A transform approach to linear network coding for acyclic networks with delay

The algebraic formulation for linear network coding in acyclic networks with each link having an integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes at any given time instant is a Fq-linear combination of the input symbols across different generations, where Fq denotes the field over which the network operates. We use finite-field discrete Fourier transform (DFT) to convert the output symbols at the sink nodes at any given time instant into a Fq-linear combination of the input symbols generated during the same generation. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (non-transform) approach if and only if there exists a network code satisfying sink demands in the transform approach. Furthermore, assuming time invariant local encoding kernels, we show that the transform method can be employed to achieve half the rate corresponding to the individual source-destination mincut (which are assumed to be equal to 1) for some classes of three-source three-destination multiple unicast network with delays using alignment strategies when the zero-interference condition is not satisfied.

Precoding-Based Network Alignment Using Transform Approach for Acyclic Networks With Delay

The algebraic formulation for linear network coding in acyclic networks with the links having integer delay is well known. Based on this formulation, for a given set of connections over an arbitrary acyclic network with integer delay assumed for the links, the output symbols at the sink nodes, at any given time instant, is a F(p)m-linear combination of the input symbols across different generations, where F(p)m denotes the field over which the network operates (p is prime and m is a positive integer). We use finite-field discrete Fourier transform to convert the output symbols at the sink nodes, at any given time instant, into a F(p)m-linear combination of the input symbols generated during the same generation without making use of memory at the intermediate nodes. We call this as transforming the acyclic network with delay into n-instantaneous networks (n is sufficiently large). We show that under certain conditions, there exists a network code satisfying sink demands in the usual (nontransform) approach if and only if there exists a network code satisfying sink demands in the transform approach. When the zero-interference conditions are not satisfied, we propose three precoding-based network alignment (PBNA) schemes for three-source three-destination multiple unicast network with delays (3-S 3-D MUN-D) termed as PBNA using transform approach and time-invariant local encoding coefficients (LECs), PBNA using time-varying LECs, and PBNA using transform approach and block time-varying LECs. We derive sets of necessary and sufficient conditions under which throughputs close to n' + 1/2n' + 1, n'/2n' + 1, and n'/2n' + 1 are achieved for the three source-destination pairs in a 3-S 3-D MUN-D employing PBNA using transform approach and time-invariant LECs, and PBNA using transform approach and block time-varying LECs, where n' is a positive integer. For PBNA using time-varying LECs, we obtain a sufficient condition under which a throughput demand of n(1)/n, n(2)/n, and n(3)/n can be met for the three source-destination pairs in a 3-S 3-D MUN-D, where n(1), n(2), and n(3) are positive integers less than or equal to the positive integer n. This condition is also necessary when n(1) + n(3) = n(1) + n(2) = n where n(1) >= n(2) >= n(3).

Tunable Locally-Optimal Geographical Forwarding in Wireless Sensor Networks with Sleep-Wake Cycling Nodes

We consider a wireless sensor network whose main function is to detect certain infrequent alarm events, and to forward alarm packets to a base station, using geographical forwarding. The nodes know their locations, and they sleep-wake cycle, waking up periodically but not synchronously. In this situation, when a node has a packet to forward to the sink, there is a trade-off between how long this node waits for a suitable neighbor to wake up and the progress the packet makes towards the sink once it is forwarded to this neighbor. Hence, in choosing a relay node, we consider the problem of minimizing average delay subject to a constraint on the average progress. By constraint relaxation, we formulate this next hop relay selection problem as a Markov decision process (MDP). The exact optimal solution (BF (Best Forward)) can be found, but is computationally intensive. Next, we consider a mathematically simplified model for which the optimal policy (SF (Simplified Forward)) turns out to be a simple one-step-look-ahead rule. Simulations show that SF is very close in performance to BF, even for reasonably small node density. We then study the end-to-end performance of SF in comparison with two extremal policies: Max Forward (MF) and First Forward (FF), and an end-to-end delay minimising policy proposed by Kim et al. 1]. We find that, with appropriate choice of one hop average progress constraint, SF can be tuned to provide a favorable trade-off between end-to-end packet delay and the number of hops in the forwarding path.

QoS Constrained Optimal Sink and Relay Placement in Planned Wireless Sensor Networks

We are given a set of sensors at given locations, a set of potential locations for placing base stations (BSs, or sinks), and another set of potential locations for placing wireless relay nodes. There is a cost for placing a BS and a cost for placing a relay. The problem we consider is to select a set of BS locations, a set of relay locations, and an association of sensor nodes with the selected BS locations, so that the number of hops in the path from each sensor to its BS is bounded by h(max), and among all such feasible networks, the cost of the selected network is the minimum. The hop count bound suffices to ensure a certain probability of the data being delivered to the BS within a given maximum delay under a light traffic model. We observe that the problem is NP-Hard, and is hard to even approximate within a constant factor. For this problem, we propose a polynomial time approximation algorithm (SmartSelect) based on a relay placement algorithm proposed in our earlier work, along with a modification of the greedy algorithm for weighted set cover. We have analyzed the worst case approximation guarantee for this algorithm. We have also proposed a polynomial time heuristic to improve upon the solution provided by SmartSelect. Our numerical results demonstrate that the algorithms provide good quality solutions using very little computation time in various randomly generated network scenarios.

Distribution of black nodes at various levels in a linear quadtree

The distribution of black leaf nodes at each level of a linear quadtree is of significant interest in the context of estimation of time and space complexities of linear quadtree based algorithms. The maximum number of black nodes of a given level that can be fitted in a square grid of size 2n × 2n can readily be estimated from the ratio of areas. We show that the actual value of the maximum number of nodes of a level is much less than the maximum obtained from the ratio of the areas. This is due to the fact that the number of nodes possible at a level k, 0≤k≤n − 1, should consider the sum of areas occupied by the actual number of nodes present at levels k + 1, k + 2, …, n − 1.

MHD Flow with Heat and Mass Transfer Due to a Point Sink

The magnetofluid dynamic steady incompressible laminar boundary layer flow for a point sink with an applied magnetic field and mass transfer has been studied. The two-point boundary-value problem governed by self-similar equations has been solved numerically. It is observed that the magnetic field increases the skin friction, but reduces the heat transfer and mass flux diffusion. However, the skin friction, heat transfer and mass flux diffusion increase due to suction and the effect of injection is just opposite. Prandtl and Schmidt numbers affect the temperature and concentration, respectively.

State Dependent Attempt Rate Modeling of Single Cell IEEE 802.11 WLANs with Homogeneous Nodes and Poisson Arrivals

Analytical models of IEEE 802.11-based WLANs are invariably based on approximations, such as the well-known mean-field approximations proposed by Bianchi for saturated nodes. In this paper, we provide a new approach for modeling the situation when the nodes are not saturated. We study a State Dependent Attempt Rate (SDAR) approximation to model M queues (one queue per node) served by the CSMA/CA protocol as standardized in the IEEE 802.11 DCF. The approximation is that, when n of the M queues are non-empty, the attempt probability of the n non-empty nodes is given by the long-term attempt probability of n saturated nodes as provided by Bianchi's model. This yields a coupled queue system. When packets arrive to the M queues according to independent Poisson processes, we provide an exact model for the coupled queue system with SDAR service. The main contribution of this paper is to provide an analysis of the coupled queue process by studying a lower dimensional process and by introducing a certain conditional independence approximation. We show that the numerical results obtained from our finite buffer analysis are in excellent agreement with the corresponding results obtained from ns-2 simulations. We replace the CSMA/CA protocol as implemented in the ns-2 simulator with the SDAR service model to show that the SDAR approximation provides an accurate model for the CSMA/CA protocol. We also report the simulation speed-ups thus obtained by our model-based simulation.

Efficient Energy Management Policies for Networks with Energy Harvesting Sensor Nodes

We study sensor networks with energy harvesting nodes. The generated energy at a node can be stored in a buffer. A sensor node periodically senses a random field and generates a packet. These packets are stored in a queue and transmitted using the energy available at that time at the node. For such networks we develop efficient energy management policies. First, for a single node, we obtain policies that are throughput optimal, i.e., the data queue stays stable for the largest possible data rate. Next we obtain energy management policies which minimize the mean delay in the queue. We also compare performance of several easily implementable suboptimal policies. A greedy policy is identified which, in low SNR regime, is throughput optimal and also minimizes mean delay. Next using the results for a single node, we develop efficient MAC policies.

Numerical Study of Heat Transfer From Pin-Fin Heat Sink Using Steady and Pulsated Impinging Jets

This paper investigates numerically the heat transfer characteristics of confined slot jet impingement on a pin-fin heat sink. A variety of pin-fin heat sinks is investigated, and the resulting enhancement of heat transfer studied. The distribution of heat transfer coefficient on the top surface of the base plate and that along the fin height are examined. Both steady and pulsated jets are studied. It is observed that for a steady jet impingement on a pin-fin heat sink, the effective heat transfer coefficient increases with fin height, leading to a corresponding decrease in base plate temperature for the same heat flux. In the case of pulsated jets, the influence of pulse frequency and the Reynolds number is examined, and their effect on the effective heat transfer coefficient is studied.

Broadcast in Ad hoc Wireless Networks with Selfish Nodes: A Bayesian Incentive Compatibility Approach

We consider the incentive compatible broadcast (ICB) problem in ad hoc wireless networks with selfish nodes. We design a Bayesian incentive compatible Broadcast (BIC-B) protocol to address this problem. VCG mechanism based schemes have been popularly used in the literature to design dominant strategy incentive compatible (DSIC) protocols for ad hoe wireless networks. VCG based mechanisms have two critical limitations: (i) the network is required to he bi-connected, (ii) the resulting protocol is not budget balanced. Our proposed BIC-B protocol overcomes these difficulties. We also prove the optimality of the proposed scheme.

Diversity and degrees of freedom of cooperative wireless networks

Two key parameters in the outage characterization of a wireless fading network are the diversity and the degrees of freedom (DOF). These two quantities represent the two endpoints of the diversity multiplexing gain tradeoff, In this paper, we present max-flow min-cut type theorems for computing both the diversity and the DOF of arbitrary single-source single-sink networks with nodes possessing multiple antennas. We also show that an amplify-and-forward protocol is sufficient to achieve the same. The DOF characterization is obtained using a conversion to a deterministic wireless network for which the capacity was recently found. This conversion is operational in the sense that a capacity-achieving scheme for the deterministic network can be converted into a DOF-achieving scheme for the fading network. We also show that the diversity result easily extends to multisource multi-sink networks whereas the DOF result extends to a single-source multi-cast network. Along the way, we prove that the zero error capacity of the deterministic network is the same as its c-error capacity.

DMT of Multi-hop Cooperative Networks-Part I: K-Parallel-Path Networks

We consider single-source, single-sink multi-hop relay networks, with slow-fading Rayleigh fading links and single-antenna relay nodes operating under the half-duplex constraint. While two hop relay networks have been studied in great detail in terms of the diversity-multiplexing tradeoff (DMT), few results are available for more general networks. In this two-part paper, we identify two families of networks that are multi-hop generalizations of the two hop network: K-Parallel-Path (KPP) networks and Layered networks. In the first part, we initially consider KPP networks, which can be viewed as the union of K node-disjoint parallel paths, each of length > 1. The results are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the optimal DMT of KPP(D) networks with K >= 4, and KPP(I) networks with K >= 3. Along the way, we derive lower bounds for the DMT of triangular channel matrices, which are useful in DMT computation of various protocols. As a special case, the DMT of two-hop relay network without direct link is obtained. Two key implications of the results in the two-part paper are that the half-duplex constraint does not necessarily entail rate loss by a factor of two, as previously believed and that, simple AF protocols are often sufficient to attain the best possible DMT.

Necessity for quantum mechanical simulation for the future technology nodes

In this paper we present and compare the results obtained from semi-classical and quantum mechanical simulation for a Double Gate MOSFET structure to analyze the electrostatics and carrier dynamics of this device. The geometries like gate length, body, thickness of this device have been chosen according to the ITRS specification for the different technology nodes. We have shown the extent of deviation between the semi-classical and quantum mechanical results and hence the need of quantum simulations for the promising nanoscale devices in the future technology nodes predicted in ITRS.

The GAF Domain of the cGMP-Binding, cGMP-Specific Phosphodiesterase (PDE5) Is a Sensor and a Sink for cGMP

We describe here a novel sensor for cGMP based on the GAF domain of the cGMP-binding, cGMP-specific phosphodiesterase 5 (PDE5) using bioluminescence resonance energy transfer (BRET). The wild type GAFa domain, capable of binding cGMP with high affinity, and a mutant (GAFaF163A) unable to bind cGMP were cloned as fusions between GFP and Rluc for BRET2 assays. BRET2 ratios of the wild type GAFa fusion protein, but not GAFaF163A, increased in the presence of cGMP but not cAMP. Higher basal BRET2 ratios were observed in cells expressing the wild type GAFa domain than in cells expressing GAFaF163A. This was correlated with elevated basal intracellular levels of cGMP, indicating that the GAF domain could act as a sink for cGMP. The tandem GAF domains in full length PDE5 could also sequester cGMP when the catalytic activity of PDE5 was inhibited. Therefore, these results describe a cGMP sensor utilizing BRET2 technology and experimentally demonstrate the reservoir of cGMP that can be present in cells that express cGMP-binding GAF domain-containing proteins. PDE5 is the target for the anti-impotence drug sildenafil citrate; therefore, this GAF-BRET2 sensor could be used for the identification of novel compounds that inhibit cGMP binding to the GAF domain, thereby regulating PDE5 catalytic activity.

Large-scale structures in turbulent and reverse-transitional sink flow boundary layers

Aspects of large-scale organized structures in sink flow turbulent and reverse-transitional boundary layers are studied experimentally using hot-wire anemometry. Each of the present sink flow boundary layers is in a state of 'perfect equilibrium' or 'exact self-preservation' in the sense of Townsend (The Structure of Turbulent Shear Flow, 1st and 2nd edns, 1956, 1976, Cambridge University Press) and Rotta (Progr. Aeronaut. Sci., vol. 2, 1962, pp. 1-220) and conforms to the notion of 'pure wall-flow' (Coles, J. Aerosp. Sci., vol. 24, 1957, pp. 495-506), at least for the turbulent cases. It is found that the characteristic inclination angle of the structure undergoes a systematic decrease with the increase in strength of the streamwise favourable pressure gradient. Detectable wall-normal extent of the structure is found to be typically half of the boundary layer thickness. Streamwise extent of the structure shows marked increase as the favourable pressure gradient is made progressively severe. Proposals for the typical eddy forms in sink flow turbulent and reverse-transitional flows are presented, and the possibility of structural self-organization (i.e. individual hairpin vortices forming streamwise coherent hairpin packets) in these flows is also discussed. It is further indicated that these structural ideas may be used to explain, from a structural viewpoint, the phenomenon of soft relaminarization or reverse transition of turbulent boundary layers when subjected to strong streamwise favourable pressure gradients. Taylor's 'frozen turbulence' hypothesis is experimentally shown to be valid for flows in the present study even though large streamwise accelerations are involved, the flow being even reverse transitional in some cases. Possible conditions, which are required to be satisfied for the safe use of Taylor's hypothesis in pressure-gradient-driven flows, are also outlined. Measured convection velocities are found to be fairly close to the local mean velocities (typically 90% or more) suggesting that the structure gets convected downstream almost along with the mean flow.