Design and Analysis of Low Complexity Network Coding Schemes
MetadataShow full item record
In classical network information theory, information packets are treated as commodities, and the nodes of the network are only allowed to duplicate and forward the packets. The new paradigm of network coding, which was introduced by Ahlswede et al., states that if the nodes are permitted to combine the information packets and forward a function of them, the throughput of the network can dramatically increase. In this dissertation we focused on the design and analysis of low complexity network coding schemes for different topologies of wired and wireless networks. In the first part we studied the routing capacity of wired networks. We provided a description of the routing capacity region in terms of a finite set of linear inequalities. We next used this result to study the routing capacity region of undirected ring networks for two multimessage scenarios. Finally, we used new network coding bounds to prove the optimality of routing schemes in these two scenarios. In the second part, we studied node-constrained line and star networks. We derived the multiple multicast capacity region of node-constrained line networks based on a low complexity binary linear coding scheme. For star networks, we examined the multiple unicast problem and offered a linear coding scheme. Then we made a connection between the network coding in a node-constrained star network and the problem of index coding with side information. In the third part, we studied the linear deterministic model of relay networks (LDRN). We focused on a unicast session and derived a simple capacity-achieving transmission scheme. We obtained our scheme by a connection to the submodular flow problem through the application of tools from matroid theory and submodular optimization theory. We also offered polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme. In the final part, we considered the multicasting problem in an LDRN and proposed a new way to construct a coding scheme. Our construction is based on the notion of flow for a unicast session in the third part of this dissertation. We presented randomized and deterministic polynomial-time versions of our algorithm.
undirected ring networks
Tabatabaei-Yazdi, Seyed (2011). Design and Analysis of Low Complexity Network Coding Schemes. Doctoral dissertation, Texas A&M University. Available electronically from
Showing items related by title, author, creator and subject.
The Influence of Friendship Networks on Adolescents' Health-Risk Behaviors: A Social Network Analysis Jeon, Kwon Chan (2014-12-15)Friendships among adolescents can exert significant influence on behaviors that pose risk to their health. However, empirical evidence for friendships’ influence is mixed due to various factors. Among these factors, are ...
Challenges and Solutions for Location-based Routing in Wireless Sensor Networks with Complex Network Topology Won, Myounggyu (2013-07-17)Complex Network Topologies (CNTs)–network holes and cuts–often occur in practical WSN deployments. Many researchers have acknowledged that CNTs adversely affect the performance of location-based routing and proposed various ...
A network transformation procedure for finding minimal-cost flows in networks with variable lower bounds Kim, Seongbae (Texas A&M University, 1991)Not available