FeedNetBack - D02.04 - Communication Network Design (rel.2)

This is a Deliverable Report for the FeedNetBack project (www.feednetback.eu). This report, divided into 4 chapters, we report the final advances on WP2 and in particular on the task 3.2, "Communication network design". Chapter one introduces the developed arguments and presents parts of the literature review. Chapter two is devoted to network topology design, and offers recent studies on the influence of network topologies on the performance of distributed systems, i.e. systems constituted by many interacting units. Concerning this topic, we analyze the performance of the consensus algorithm, which is largely proposed as an efficient and low complexity tool for distributed control, estimation and optimization. The optimal topology for this algorithm, yielding fastest convergence time, is proposed. This topology is described by the de Bruijn graphs. Then, the properties of the Cayley graphs (again in relation with the consensus algorithm) are analyzed. These graphs are often used as a simple paradigm of geometric graphs, namely graphs in which the nodes are deployed in a geometric space. For this kind of graph topologies quadratic type performance indexes are often considered. Those performance indexes come into the picture when applying consensus algorithms to distributed estimation or control and yield completely different evaluation of the possible choices of the network topologies. We extend the result beyond Cayley graphs taking into consideration a special class of geometric graphs, characterized by four purely geometric parameters. The extension is done for the particular class of reversible Markov chains due to the strong analogy they show with resistive electrical networks. Chapter three deals with control applications, and more generally with real-time applications running over wireless sensor networks (WSNs). These systems require the design of dedicated routing protocols and control strategies to cope with the potential random delays and packet losses due to the wireless nature of the WSNs. In this chapter we then address this problem from two points of view. In the first we focus on the design of special routing strategies, namely Unicast Path Diversity (UDP) and Directed Staged Flooding (DSF), that are specifically designed for real-time application: in fact they can trade off lower end-to-end delays with higher packet loss. These two strategies, however, cannot completely remove delays randomness or packet losses. Therefore, for linear dynamical systems, we designed opportune time-varying Kalman filters that compensate both random delays and packet losses. We also address the problem of designing sub-optimal filtering strategies based on the known statistics of the packet arrival process which are computationally efficient and have limited performance degradation as compared with the optimal strategy. We also perform extensive simulations to test and evaluate both the novel routing strategies and the control/estimation strategies. Chapter four finally reports the research activity related to the network coding. It starts treating the problem of data quantization, the first issue to be considered when studying distributed algorithm in which the agents need to communicate through digital channels that are initially considered noiseless. The case of simple uniform quantizer is analyzed, while the more efficient quantizer, called zooming quantizer, is considered The case of noisy digital channels is finally treated, and two possible error correcting coding methods are compared for their employment in the consensus algorithm, the first being more efficient in the exploitation of the communication resource, but more computationally demanding, while the second being less information efficient but much simpler from the computational point of view. We give, in the specific case of the consensus algorithm, a nice view of how to treat complexity, communication and computation resources in a unified way for the solution of distributed estimation problems