### An Analysis of Finite-Memory Random Linear Coding on Packet Streams

- Research Article in 2nd International ICST Workshop on Network Coding, Theory, and Applications
- Authors:
- Desmond S. Lun, Muriel Medard, Payam Pakzad, Christina Fragouli, Ralf Koetter
- Abstract:
We consider the following packet coding scheme: The coding node has a fixed, finite memory in which it stores packets formed from an incoming packet stream, and it sends packets formed from random linear combinations of its memory contents. We analyze the scheme in two settings: as a self-contained…

more »We consider the following packet coding scheme: The coding node has a fixed, finite memory in which it stores packets formed from an incoming packet stream, and it sends packets formed from random linear combinations of its memory contents. We analyze the scheme in two settings: as a self-contained component in a network providing reliability on a single link, and as a component employed at intermediate nodes in a block-coded end-to-end connection. We believe that the scheme is a good alternative to automatic repeat request when feedback is too slow, too unreliable, or too difficult to implement.

### Coverage In Heterogeneous Sensor Networks

- Research Article in 4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- Authors:
- Loukas Lazos, Radha Poovendran
- Abstract:
In this paper we study the problem of coverage in heterogeneous planar sensor networks. Coverage as a performance metric, quantifies the quality of monitoring provided by the sensor network. We formulate the problem of coverage as a set intersection problem arising in Integral Geometry, and derive …

more »In this paper we study the problem of coverage in heterogeneous planar sensor networks. Coverage as a performance metric, quantifies the quality of monitoring provided by the sensor network. We formulate the problem of coverage as a set intersection problem arising in Integral Geometry, and derive analytical expressions for stochastic coverage. Our formulation allows us to consider a heterogeneous sensing model, where sensors need not have an identical sensing capability. In addition, our approach is applicable to scenarios where the sensing area of each sensor has arbitrary shape and sensors are deployed according to any distribution. We present analytical expressions only for convex sensing areas, however, our results can be generalized to non-convex areas. The validity of our expressions is verified by extensive simulations.

### Coverage by Directional Sensors

- Research Article in 4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- Authors:
- Jing Ai, Alhussein A. Abouzeid
- Abstract:
We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be act…

more »We study a novel “coverage by directional sensors” problem with tunable orientations on a set of discrete targets. We propose a Maximum Coverage with Minimum Sensors (MCMS) problem in which coverage in terms of the number of targets to be covered is maximized whereas the number of sensors to be activated is minimized. We present its exact Integer Linear Programming (ILP) formulation and it is used as a baseline for comparison. Then we provide a distributed greedy algorithm (DGA) solution. By incorporating a measure of the sensors’ residual energy into DGA, we further develop a Sensing Neighborhood Cooperative Sleeping (SNCS) protocol which performs adaptive scheduling on a larger time scale. Finally, we evaluate the properties of the proposed solutions and protocol in terms of providing coverage and maximizing network lifetime through extensive simulations.

### Analysis of Finite Unreliable Sensor Grids

- Research Article in 4th International ICST Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks
- Authors:
- Hossein Pishro-Nik
- Abstract:
Asymptotic analysis of unreliable sensor grides has been studied previously. Some analytic results for sensor grids have been reported for the case where the number of nodes n in the network tends to infinity (large-scale grids). This includes connectivity, coverage, and diameter of the networks. T…

more »Asymptotic analysis of unreliable sensor grides has been studied previously. Some analytic results for sensor grids have been reported for the case where the number of nodes n in the network tends to infinity (large-scale grids). This includes connectivity, coverage, and diameter of the networks. These results have not been extended for small or moderate values of n, although in many practical sensor grids, n might not be very large. In this paper, we first show that previous asymptotic results may provide poor approximations for the finite grids (small-scale grids). We then aim to develop a methodology to analytically study unreliable sensor grids properties without assuming that n is large. We prove some properties of finite sensor grids. We show that a large class of network parameters can be expressed as piecewise constant functions of communication and sensing radii. We obtain simple analytic expressions for connectivity and coverage probabilities of finite sensor grids. Using simulations, we show that the expressions give good estimates of these probabilities.

### Distributed Symmetric Function Computation in Noisy Wireless Sensor Networks with Binary Data

- Authors:
- Lei Ying, R. Srikant, Geir E. Dullerud
- Abstract:
We consider a wireless sensor network consisting of n sensors, each having a recorded bit, the sensor’s measurement, which has been set to either “0” or “1”. The network has a special node called the fusion center whose goal is to compute a symmetric function of these bits; i.e., a function that de…

more »We consider a wireless sensor network consisting of n sensors, each having a recorded bit, the sensor’s measurement, which has been set to either “0” or “1”. The network has a special node called the fusion center whose goal is to compute a symmetric function of these bits; i.e., a function that depends only on the number of sensors that have a “1.” The sensors convey information to the fusion center in a multi-hop fashion to enable the function computation. The problem studied is to minimize the total transmission energy used by the network when computing this function, subject to the constraint that this computation is correct with high probability. We assume the wireless channels are binary symmetric channels with a probability of error p, and that each sensor uses rαunits of energy to transmit each bit, where r is the transmission range of the sensor. The main result in this paper is an algorithm whose energy usage is Θ (n(loglogn)(√logn/n)α), and we also show that any algorithm satisfying the performance constraints must necessarily have energy usage Ω (n(√logn/n)α). Then, we consider the case where the sensor network observes N events, and each node records one bit per event, thus having N bits to convey. The fusion center now wants to compute N symmetric functions, one for each of the events.

### Robust Threshold based Sensor Activation Policies under Spatial Correlation

- Authors:
- Neeraj Jaggi
- Abstract:
We consider a system of rechargeable sensor nodes deployed redundantly in the region of interest. Active sensor nodes are subject to a discharge process which depends on the occurrence of events in the system. All sensor nodes experience a continuous recharge of their battery energies, however at a…

more »We consider a system of rechargeable sensor nodes deployed redundantly in the region of interest. Active sensor nodes are subject to a discharge process which depends on the occurrence of events in the system. All sensor nodes experience a continuous recharge of their battery energies, however at a considerably lower rate than of discharge. The decision problem is to find the optimal activation policy for the sensor nodes which would maximize the aggregate system utility. We model our rechargeable sensor system as a system of finite-buffer queues and show the existence of a simple threshold activation policy that achieves near optimal performance. Our results hold both in presence as well as absence of correlation in the discharge and/or recharge processes, thereby showing the robustness of such policies with respect to the degree of correlation in the system.

### Scheduling Sensor Activity for Point Information Coverage in Wireless Sensor Networks

- Authors:
- Bang Wang, Kee Chaing Chua, Vikram Srinivasan , Wei Wang
- Abstract:
An important application of wireless sensor networks is to perform the monitoring missions, for example, to monitor some targets of interests at all times. Sensors are often equipped with non-rechargeable batteries with limited energy and energy saving is a critical aspect for wireless sensor netwo…

more »An important application of wireless sensor networks is to perform the monitoring missions, for example, to monitor some targets of interests at all times. Sensors are often equipped with non-rechargeable batteries with limited energy and energy saving is a critical aspect for wireless sensor networks. If a target is monitored simultaneously by serval sensors, some of them can be switched off to save energy without causing mission failure and by which their operational times as well as the network lifetime can be prolonged. In this paper, we study the problem of scheduling sensor activity to cover a set of targets with known locations such that all targets can be monitored all the time and the network can operate as long as possible. A solution to this scheduling problem is to partition all sensors into sensor covers such that each cover can monitor all targets and the covers are activated successively. In this paper, we propose to use the notion of information coverage which is based on the estimation theory to exploit the collaborative nature of wireless sensor networks, instead of using the conventional definition of coverage. Due to the use of information coverage, a target that is not within the sensing disk of any single sensor can still be considered to be monitored (information covered) by the cooperation of more than one sensor.

### Optimizing Data Replication for Expanding Ring-based Queries in Wireless Sensor Networks

- Authors:
- Bhaskar Krishnamachari, Joon Ahn
- Abstract:
We consider the problem of optimizing the number of replicas for event information in wireless sensor networks, when queries are disseminated using expanding rings. We obtain closed-form approximations for the expected energy costs of search, as well as replication. Using these expressions we deriv…

more »We consider the problem of optimizing the number of replicas for event information in wireless sensor networks, when queries are disseminated using expanding rings. We obtain closed-form approximations for the expected energy costs of search, as well as replication. Using these expressions we derive the replication strategies that minimize the expected total energy cost consisting of search and replication costs, both with and without storage constraints. In both cases, we find that events should be replicated with a frequency that is proportional to the square root of their query rates. We validate our analysis and optimization through a set of realistic simulations that incorporate non-idealities including deployment boundary effects and lossy wireless links.

### Min-cost Selfish Multicast with Network Coding

- Research Article in 2nd International ICST Workshop on Network Coding, Theory, and Applications
- Authors:
- Sandeep Bhadra , Sanjay Shakkottai, Piyush Gupta
- Abstract:
The single-source min-cost multicast problem is considered, which can be framed as a convex optimization problem with the use of network codes and convex increasing edge costs. A decentralized approach to this problemn is presented by Lun, Ratnakar, et.al. for the case where all users cooperate to …

more »The single-source min-cost multicast problem is considered, which can be framed as a convex optimization problem with the use of network codes and convex increasing edge costs. A decentralized approach to this problemn is presented by Lun, Ratnakar, et.al. for the case where all users cooperate to reach the global minimum. This paper analyzes the cost for the scenario where each of the multicast receivers greedily routes its flows and shows that a Nash equilibrium exists for such a scenario. An allocation rule by which the edge-cost at each edge is allocated to flows through that edge is presented. Under this rule, it is shown that for any (monomial) power-law cost function on each edge, there is a pricing rule such that the flow cost at user equilibrium is the same as the min-cost. This leads to the construction of an autonomous flow-steering algorithm for each receiver, which is also globally optimal. The algorithm is extended for completely distributed flow adaptation at nodes in the network, which also achieves globally minimal cost in steady state. Finally, the framework is generalized to the case of multiple multicast sessions and the results are shown to hold for user equilibrium in this case as well.

### Navigation on Self-Organized Networks

- Research Article in Second Workshop on Spatial Stochastic Models for Wireless Networks
- Authors:
- Charles Bordenave
- Abstract:
On a locally finite point set, a navigation defines a path through the point set from a point to an other. The set of paths leading to a given point defines a tree, the navigation tree. In this article, we analyze the properties of the navigation tree when the point set is a Poisson point process o…

more »On a locally finite point set, a navigation defines a path through the point set from a point to an other. The set of paths leading to a given point defines a tree, the navigation tree. In this article, we analyze the properties of the navigation tree when the point set is a Poisson point process on Rd. We examine the distribution of stable functionals, the local weak convergence of the navigation tree, the asymptotic average of a functional along a path, the shape of the navigation tree and its topological ends. We illustrate our work in the small world graphs, and new results are established. This work is motivated by applications in computational geometry and in self-organizing networks.