Computer Science – Information Theory
Scientific paper
2007-07-05
Computer Science
Information Theory
6 pages
Scientific paper
The advent of network coding presents promising opportunities in many areas of communication and networking. It has been recently shown that network coding technique can significantly increase the overall throughput of wireless networks by taking advantage of their broadcast nature. In wireless networks, each transmitted packet is broadcasted within a certain area and can be overheard by the neighboring nodes. When a node needs to transmit packets, it employs the opportunistic coding approach that uses the knowledge of what the node's neighbors have heard in order to reduce the number of transmissions. With this approach, each transmitted packet is a linear combination of the original packets over a certain finite field. In this paper, we focus on the fundamental problem of finding the optimal encoding for the broadcasted packets that minimizes the overall number of transmissions. We show that this problem is NP-complete over GF(2) and establish several fundamental properties of the optimal solution. We also propose a simple heuristic solution for the problem based on graph coloring and present some empirical results for random settings.
Chaudhry Mohammad Asad R.
El Rouayheb Salim Y.
Sprintson Alex
No associations
LandOfFree
On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Minimum Number of Transmissions in Single-Hop Wireless Coding Networks will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-570027