Diversity in Large Networks


Guillermo Barrenechea


Sensor networks span a wide spectrum in terms of their functionality (i.e., what they are used for), organization (i.e., how the different components are assembled to form a complete working system), and the technologies used to build them. There are three main elements in sensor networks that pose serious challenges: the large number of nodes, the limited resources and the uncontrolled dynamics. The development of a working network of wireless sensors requires solutions to a number of technical challenges such as routing, flow control, power control, modem design, hardware, etc. Among all these, of particular interest for our research are the routing problem (i.e., moving data among different network locations) and the joint source channel coding (i.e., signal coding for particular networks).

Main contributions

We have studied randomized routing algorithms used to implement multi path routing with certain load distribution properties. We formalized the corresponding routing problem as a problem of constructing suitably constrained random walks on random dynamic graphs.

We analyzed network capacity limits and optimal routing algorithms for regular sensor networks, namely, square and torus grid sensor networks, in both, the static case (no node failures) and the dynamic case (node failures). For the static case, we analyzed also the effect of finite queues in the network capacity and optimal routing for different communication models, such as uniform communication and data gathering.

The diversity provided by sensor networks makes possible the use of specific joint source channel coding techniques capable of providing a required quality even under high degree of unreliability. We have investigated the interaction between routing and source coding techniques and concluded that a more sophisticated scheme combining multi path routing and multiple description source coding performs significantly better that the usual single path single description scheme.

Current and Future Research

In our previous work we analyzed optimal routing algorithms that achieve capacity under the infinite buffer capacity. Each routing algorithm defines a network capacity region that restricts the rate nodes can use to transmit data. The characterization of these network capacity regions is a subject of our future research. Once we translate the routing algorithm into a network capacity region, we can use this network characterization to investigate the optimal source coding of correlated data.

Our current solution for routing in random graphs is limited to particular communication models, namely uniform traffic communication and data-gathering. One line along which this work could proceed further consists of extending the results to other communications models such as data-collection in digital displays.


Baltasar Beferull-Lozano, Martin Vetterli.


September 2001 – ongoing.


Swiss National Competence Center in Research for Mobile Information and Communication Systems.

Major publications

S. D. Servetto, G. Barrenechea, “Constrained Random Walks on Random Graphs: Routing Algorithms for Large Scale Wireless Sensor Networks”, In Proc. of the 1st AC International Workshop on Wireless Sensor Networks and Applications (WSNA), Atlanta, GA, September 2002 (held in conjunction with ACM MobiCom).
G. Barrenechea, B. Beferull-Lozano, A. Verma, P.L. Dragotti, M. Vetterli, “Multiple Description Source Coding and Diversity Routing: A Joint Source Channel Coding Approach to Real-Time Services Over Dense Networks”, In Proc. of the 13th International Packet Video Workshop, Nantes, France, April 2003.
G. Barrenechea, B. Beferull-Lozano and M. Vetterli, “Lattice Sensor Networks: Capacity Limits, Optimal Routing and Robustness to Failures”, In Proc. of Information Processing in Sensor Networks (IPSN), Berkeley, CA, April 2004.