Click here for full text:
On the Complexity of Variants of Cooperative Peer-to- peer Repair for Wireless Broadcasting
Cheung, Gene; Li, Danjue; Chuah, Chen-Nee
HPL-2006-90
Keyword(s): multimedia; wireless networks; complexity
Abstract: The well-known NAK implosion problem for wireless broadcast can be addressed by leveraging cooperative peer-to-peer connectivity to repair corrupted data. This paper studies the Cooperative Peer-to-peer Repair (CPR) framework for multimedia broadcast. We show that CPR can be formulated as an optimization problem that minimizes the number of iterations it takes to wirelessly disseminate a desired message from peers 'with' the content to peers 'without' it. Complicating the problem are transmission conflicts, where pre- specified sets of links cannot simultaneously transmit due to interference. In this paper, we formalize CPR as a discrete optimization problem, and prove that CPR and its many variants are NP-hard. Notes:
4 Pages
Back to Index
| 
Printable version
