In this paper, we consider the (N,K,L) multi-access caching network where K users and K caches are connected to a server with N files, each of size F bits, through a shared error-free broadcast channel. Each user has access to L nearby caches, each of size MF bits, in a cyclic wrap-around manner. Even after several previous attempts, the exact characterization of the optimal rate memory tradeoff is still an open problem except in the case where L = K − 1 and L = 1 with large cache $M \in \left[ {\frac{N}{L} \cdot \frac{{K - 1}}{K},\frac{N}{L}} \right]$. This paper determines the optimal rate memory tradeoff for the cache network with L = K − 2 and $M \in \left[ {\frac{N}{{K - 2}} \cdot \frac{{K - 1}}{K},\frac{N}{{K - 2}}} \right]$. This is done by proposing a new caching scheme that operates at the memory rate pair $\left( {\frac{N}{{K - 2}},\frac{{K - 1}}{K},\frac{1}{K}} \right)$ and deriving a set of lower bounds to demonstrate the optimality of the scheme.

The idea of coded caching for content distribution networks was introduced by Maddah-Ali and Niesen, who considered the canonical$(N, K)$cache network in which a server with$N$files satisfies the demands of$K$users (each equipped with an independent cache of size$M$). The optimal rate memory tradeoff for demands where all files are requested by at least one user has been characterized only for small caches where$M\leq \frac {1}{K}$and large caches where$M\geq N-\frac {N}{K}$. For the case$N \leq K \leq 2N-1$, we derive new lower bounds for small and large caches and propose a new coded caching scheme for large caches. Along with the scheme proposed by Gómez-Vilardebó, this leads to a characterization of the optimal rate memory tradeoff for$M\leq \frac {1}{K}+\frac {1}{K(N-1)}$and$M\geq N-\frac {N}{K}-\frac {N-1}{K(K-1)}$. For the case$2N-1\leq K$, we derive a new lower bound for large caches, which proves the optimality of the scheme proposed by Yu et al. and leads to a characterization of the optimal rate memory tradeoff for$M\geq N-\frac {2N}{K}$. We also derive a new lower bound for small caches, which improves upon previously known lower bounds.

The problem of coded caching was introduced by Maddah-Ali and Niesen and has been extensively studied in recent years. The problem is fundamentally a multi-objective optimization problem where the rates achieved for each demand type is of interest and Pareto optimality is a natural framework. Under the constraint that the placement phase is uncoded, Yu et al. introduced the YMA scheme which was shown to be universal for all demand types. Vijith et al. showed that there are no universal schemes when coded placement is permitted and introduced the problem of finding Pareto optimal schemes. In this paper we study the possibility of finding schemes that dominate the YMA scheme and demonstrate, rather surprisingly, that they continue to operate at the Pareto optimal frontier of coded caching for (N, K) cache networks when$K$≤ 3. We introduce new lower bounds which partially characterize the tradeoffs between different demand types.

Vector linear solvability of non-multicast networks depends upon both the characteristic of the finite held and the dimension of the vector linear network code. In the literature, the dependency on the characteristic of the finite held and the dependency on the dimension have been studied separately. In this paper, we show the interdependency between the characteristic of the finite held and the dimension of the vector linear network code that achieves a vector linear network coding (VLNC) solution in non-multicast networks. For any given network Al, we dehne P(N, d) as the set of all characteristics of finite fields over which the network N has a d-dimensional VLNC solution. To the best of our knowledge, for any network N shown in the literature, if P(N, 1) is non-empty, then P(N, 1) = P(N, d) for any positive integer d. We show that, for any two non-empty sets of primes P1and P2, there exists a network N such that P(N, 1) = P1, but P(N, 2) = {P1, P2}. We also show that there are networks exhibiting a similar advantage (the existence of a VLNC solution over a larger set of characteristics) if the dimension is increased from 2 to 3. However, such behaviour is not universal, as there exist networks which admit a VLNC solution over a smaller set of characteristics of finite fields when the dimension is increased. Using the networks constructed in this paper, we further demonstrate that: (i) a network having an m1-dimensional VLNC solution over a finite held of some characteristic and an m2-dimensional VLNC solution over a finite held of some other characteristic may not have an (m1+ m2)-dimensional VLNC solution over any finite held; (ii) there exist a class of networks for which scalar linear network coding (SLNC) over non-commutative rings has some advantage over SLNC over finite fields: the least sized non-commutative ring over which each network in the class has an SLNC solution is significantly lesser in size than the least sized finite held over which it has an SLNC solution.

Maddah-Ali and Niesen, in a seminal paper, introduced the notion of coded caching. The exact nature of the fundamental limits in this context has remained elusive even as several approximate characterizations have been found. A new optimal scheme for the (3, 3) cache network, operating at the memory rate pair (5/3, 1/2) for the demand where all the users request for distinct files, was introduced recently to partially address this issue. In this paper, an extension of this scheme to the general (K, K) cache network, operating at the memory rate pair ((K2-K -1)/K, 1/(K -1), is proposed. A new lower bound is also derived which demonstrates the optimality of the proposed scheme for the demand where all the users request for distinct files.

Maddah-Ali and Niesen, in a seminal work, initiated the study of rate memory tradeoff for a canonical cache network which operates via a placement phase and a delivery phase. While considering the case of placement phase being uncoded, Yu et al. proved the surprising result of the existence of a universal code, a code which is simultaneously optimal for all demand types. In this paper, we prove that universal codes do not exist when coding is permitted in the placement phase. As part of our proof, we introduce new kinds of lower bounds. In these lower bounds, instead of considering one demand type at a time, we consider several demand types simultaneously. These bounds give us better insight into how the performance for one demand type affects the performance for the other demand types. The non-existence of a universal scheme motivates us to introduce the notion of Pareto optimal schemes, and we prove that Chen's scheme is Pareto optimal.

This paper presents yet another instance of the power of vector linear network coding over scalar linear network coding. Previous works have established that the size of the finite field required to achieve a vector linear solution may be smaller than that size of the finite field required to achieve a scalar linear solution. It has been also shown there exist networks which do not have a scalar linear solution but have a vector linear solution. In this paper we show that the set of characteristics over which a network has a vector linear solution may be larger than the set of characteristics over which it has a scalar linear solution. We prove this result by showing a network which has a scalar linear solution if and only if the characteristic of the finite field is 2, but has a 2-dimensional vector linear solution over every finite fields.

We propose a joint routing and medium access control (MAC) protocol, named as JRAM, for reducing transmission delays in a many-to-one communication paradigm for wireless sensor networks (WSNs). Due to the wide variety of WSN applications, there is a need for protocol solutions optimized for specific application classes. JRAM is proposed for WSNs deployed for monitoring multiple events in the same geographic region which require prompt detection and response. In existing contention-based synchronous MAC protocols designed for this, a node gets only one chance to succeed in data transmission scheduling per cycle, and a sink can also only receive data packets from at most one node in a cycle. Therefore, endto-end transmission delay (E2ETD) and packet delivery ratio (PDR) of these protocols drastically degrade with the increase in event occurrence rate (EOR). In contrast, JRAM proposes a novel approach to provide k (k > 1) chances to a node to succeed in data transmission scheduling in a cycle, and also allows a sink to receive data packets from k nodes in the same cycle. This is done, in JRAM, by partitioning the network nodes into k disjoint sets and then using a novel cycle structure. We evaluate JRAM through extensive NS-2.35 simulations and compare its performance with existing pipelined data collection (PDC), adaptive data collection (ADC), and CROPMAC protocols, for different types of traffic loads and traffic patterns. Results suggest that in case of high EOR, JRAM outperforms PDC, ADC and CROPMAC both in terms of the E2ETD and the PDR.

In a distributed storage system (DSS), high data reliability is obtained by dispersing the data over a number of nodes over a network. In an (n, k) erasure code based DSS, a data file is first divided into k packets and then these k packets are encoded into n packets using an MDS code, and finally these n packets are distributed over n nodes so that each node stores one encoded packet. A fixed value of n and k provides certain level of reliability (an (n, k) erasure code based DSS can tolerate n - k node failures) and costs certain storage space. Considering the storage cost and required reliability, we might require to change an existing (n, k) erasure code based DSS to an (n', k') erasure code based DSS. However, for converting an (n, k) erasure code based DSS into an (n', k') erasure code based DSS, a naive way would be to to download the whole data, re-encode, and disperse the encoded data again. In practical situations, where we have huge amount of data, this process requires huge download bandwidth and thus it is not appreciable. In this paper, we present adaptive coding schemes for erasure code based DSS to adapt to another parameters with the minimum amount of data download. We first introduce a repair scheme for the partially failed nodes in a DSS by downloading the minimum amount of data. The concept of repairing partially failed nodes might be of independent interest. In most cases, our adaptive coding schemes view the problem of converting an (n, k) erasure code based DSS into an (n', k') erasure code based DSS with the minimum download as an instance of the repairing scheme of partially failed nodes in a DSS with the minimum download.

We consider directed acyclic networks where each terminal requires sum of all the sources. Such a class of networks has been termed as sum-networks in the literature. A sum-network having m sources and n terminals has been termed as a ms/nt sum-network. There has been previous works on the capacity of sum-networks, specifically, it has been shown that the capacity of a 3s/3t sum-network is either 0,2/3 or ≥ 1. In this paper, we consider some generalizations of 3s/3t sum-networks, namely, ms/3t and 3s/nt sum-networks, where m, n ≥ 3. For ms/3t and 3s/nt sum-networks, where m, n ≥ 3, if the mincut between each source and each terminal is at least 1, the capacity is known to be at least 2/3. In this paper, we show that there exist ms/3t and 3s/nt sum-networks whose capacities lie between 2/3 and 1. Specifically, we show that for any positive integer k ≥ 2, there exists a ms/3t sum-network (and also a 3s/nt sum-network) whose capacity is k/k+1. We conjecture that the capacity of a ms/3t sum-network, where m > 3 (and also of a 3s/nt sum-network, where n > 3) is either 0, ≥ 1 or of the form k/k+1, where k is a positive integer greater than or equal to 2.

Key management, one of the most challenging problems in Wireless Sensor Network (WSN) has been efficiently addressed using Key Predistribution (KPD) schemes. This paper analyzes a localized KPD based on the Transversal Design (TD) design or Reed Solomon (RS) codes schemes; later two shown to be similar. They lack full direct communications among their constituent nodes and so, rely on multi-hop involving other nodes reducing the overall efficiency of the system. The communication issue for TD or RS and hence the localized KPD gets resolved by Deterministic Merging of exactly two nodes. The weakness of `selective node attack' of the merged designs, similar to their original KPDs, is overcome by invoking the novel trick of Sarkar \emph{et al.} Simulation results confirm that the various network parameters of the proposed schemes improves significantly over a random counterpart among other existing schemes.

A directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus for any directed acyclic communication network. It is also shown that there exists a linear solvably equivalent multiple-unicast network for every sum-network. It is shown that for any set of polynomials having integer coefficients, there exists a sum-network which is scalar linear solvable over a finite field F if and only if the polynomials have a common root in F. For any finite or cofinite set of prime numbers, a network is constructed which has a vector linear solution of any length if and only if the characteristic of the alphabet field is in the given set. The insufficiency of linear net- work coding and unachievability of the network coding capacity are proved for sum-networks by using similar known results for communication networks. Under fractional vector linear network coding, a sum-network and its reverse network are shown to be equivalent. However, under nonlinear coding, it is shown that there exists a solvable sum-network whose reverse network is not solvable.

We consider directed acyclic sum-networks with m sources and n terminals where the sources generate symbols from an arbitrary alphabet field F, and the terminals need to recover the sum of the sources over F. We show that for any co-finite set of primes, there is a sum-network which is linearly solvable only over fields of characteristics belonging to that set. We further construct a sum-network where a scalar linear solution exists over all fields other than the binary field F2. We also show that a sum-network is linearly solvable over a field if and only if its reverse network is linearly solvable over the same field.