research-article

Complexity of scheduling with analog network coding

Authors:

Olga Goussevskaia,

Roger WattenhoferAuthors Info & Claims

FOWANC '08: Proceedings of the 1st ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing

Pages 77 - 84

https://doi.org/10.1145/1374718.1374733

Published: 26 May 2008 Publication History

Abstract

In this paper we analyze the complexity of scheduling wireless links in the physical interference model with analog network coding capability. We study two models with different definitions of network coding. In one model, we assume that a receiver is able to decode several signals simultaneously, provided that these signals differ in strength significantly. In the second model, we assume that routers are able to forward the interfering signal of a pair of nodes that wish to exchange a message, and nodes are able to decode the "collided" message by subtracting their own contribution from the interfered signal. For each network coding definition, we construct an instance of the scheduling problem in the geometric SINR model, in which nodes are distributed in the Euclidean plane. We present NP-completeness proofs for both scenarios.

References

[1]

R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung. Network information flow. IEEE Trans. on Inf. Theory, 46(4):1204--1216, 2000.

Digital Library

[2]

M. Chatterjee, H. Lin, and S. K. Das. Rate Allocation and Admission Control for Differentiated Services in CDMA Data Networks. IEEE Transactions on Mobile Computing, 6(2):179--191, 2007.

Digital Library

[3]

M. R. Garey and D. S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM Journal on Computing, page 397, 1975.

[4]

M. R. Garey and D. S. Johnson. Computers and Intractability : A Guide to the Theory of NP--Completeness. W. H. Freeman, 1979.

Digital Library

[5]

O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer. Complexity in geometric SINR. In MOBIHOC, pages 100--109, 2007.

Digital Library

[6]

P. Gupta and P. R. Kumar. Critical Power for Asymptotic Connectivity in Wireless Networks. Stochastic Analysis, Control, Optimization and Applications, pages 547--566, 1998.

[7]

P. Gupta and P. R. Kumar. The Capacity of Wireless Networks. IEEE Trans. Inf. Theory, 46(2):388--404, 2000.

Digital Library

[8]

J. Hamkins. Joint viterbi algorithm to separate cochannel fm signals. In IEEE Int. Conf. Acoustics, Speech, Signal Processing, 1998.

[9]

J. Hamkins. An analytic technique to separate cochannel fm signals. IEEE Transactions on Communications, 48(4):543--546, 2000.

[10]

T. Ho, M. Medard, R. Koetter, D. R. Karger, M. Effros, J. Shi, and B. Leong. A random linear network coding approach to multicast. IEEE Trans. on Inf. Theory, 52(10):4413--4430, 2006.

Digital Library

[11]

H. Hunt, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, andR. Stearns. NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. Journal of Algorithms, 26, 1998.

Digital Library

[12]

S. Katti, S. Gollakota, and D. Katabi. Embracing wireless interference: analog network coding. In SIGCOMM, pages 397--408. ACM Press, 2007.

Digital Library

[13]

S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft. XORs in the air: practical wireless network coding. In SIGCOMM, pages 243--254, 2006.

Digital Library

[14]

I. T. L. Kozat, U. C. Koutsopoulos. Cross-layer design for power efficiency and qos provisioning in multi-hop wireless networks. IEEE Trans. on Wireless Communications, 5, 2006.

Digital Library

[15]

S. O. Krumke, M. Marathe, and S. Ravi. Models and approximation algorithms for channel assignment in radio networks. Wireless Networks, 6:575--584.

Digital Library

[16]

K. Leung and L. Wang. Integrated link adaptation and power control for wireless ip networks, 2000.

[17]

S. Y. R. Li, R. W. Yeung, and N. Cai. Linear network coding. Information Theory, IEEE Transactions on, 49(2):371--381, 2003.

Digital Library

[18]

T. Moscibroda, R. Wattenhofer, and Y. Weber. Protocol Design Beyond Graph-based Models. In HotNets, 2006.

[19]

P. Sanders, S. Egner, and L. Tolhuizen. Polynomial time algorithms for network information flow. In SPAA, pages 286--294, 2003.

Digital Library

[20]

S. Singh and C. S. Raghavendra. PAMAS - Power Aware Multi-Access Protocol with Signalling for Ad Hoc Networks. SIGCOMM Comput. Commun. Rev., 28(3):5--26, 1998.

Digital Library

[21]

Y. Wu. Broadcasting when receivers know some messages a priori. In IEEE Int. Symp. Inf. Theory, 2007.

[22]

Y. Wu, P. A. Chou, and S.-Y. Kung. Minimum-energy multicast in mobile ad hoc networks using network coding. IEEE Transactions on Communications, 53(11):1906--1918, 2005.

[23]

S. Zhang, S. C. Liew, and P. P. Lam. Hot topic: physical-layer network coding. In MOBICOM, pages 358--365, 2006.

Digital Library

Cited By

Naves RKhalife HJakllari GConan VBeylot A(2019)A Framework for Evaluating Physical-Layer Network Coding Gains in Multi-Hop Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2018.288342918:12(2725-2739)Online publication date: 1-Dec-2019
https://doi.org/10.1109/TMC.2018.2883429
Halldórsson MWattenhofer R(2019)Wireless Network AlgorithmicsComputing and Software Science10.1007/978-3-319-91908-9_9(141-160)Online publication date: 2019
https://doi.org/10.1007/978-3-319-91908-9_9
Naves RKhalife HJakllari GConan VBeylot A(2017)A framework for evaluating physical-layer network coding gains in multi-hop wireless networksIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057187(1-9)Online publication date: May-2017
https://doi.org/10.1109/INFOCOM.2017.8057187
Show More Cited By

Index Terms

Complexity of scheduling with analog network coding
1. Mathematics of computing
  1. Information theory
2. Theory of computation

Recommendations

Complexity of Scheduling Shops with No Wait in Process

We show that obtaining minimum finish time schedules with no wait in process is NP-Hard for flow shops, job shops and open shops. Specifically, it is shown that the two processor job and open shop problems are NP-Hard even when jobs are restricted to ...
Time and power scheduling in an ad hoc network with bidirectional relaying and network coding

Network coding NC is a technique that allows intermediate nodes to combine the received packets from multiple links and forwarded to subsequent nodes. Compared with pure relaying, using NC in a wireless network, one can potentially improve the network ...
Cooperative protocol for analog network coding in distributed wireless networks

The concept of analog network coding (ANC) considers the concurrent transmission of signals over the wireless medium so that they intentionally interfere. Higher network throughput can be achieved with ANC when an intended transmission that a receiver ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

FOWANC '08: Proceedings of the 1st ACM international workshop on Foundations of wireless ad hoc and sensor networking and computing

May 2008

106 pages

ISBN:9781605581491

DOI:10.1145/1374718

Program Chairs:
Xiang-Yang Li
Illinois Institute of Technology, USA
,
Yu Wang
University of North Carolina at Charlotte, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 May 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

MobiHoc08

Sponsor:

MobiHoc08: The Ninth ACM International Symposium on Mobile Ad Hoc Networking and Computing

May 26, 2008

Hong Kong, Hong Kong, China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
309
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Naves RKhalife HJakllari GConan VBeylot A(2019)A Framework for Evaluating Physical-Layer Network Coding Gains in Multi-Hop Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2018.288342918:12(2725-2739)Online publication date: 1-Dec-2019
https://doi.org/10.1109/TMC.2018.2883429
Halldórsson MWattenhofer R(2019)Wireless Network AlgorithmicsComputing and Software Science10.1007/978-3-319-91908-9_9(141-160)Online publication date: 2019
https://doi.org/10.1007/978-3-319-91908-9_9
Naves RKhalife HJakllari GConan VBeylot A(2017)A framework for evaluating physical-layer network coding gains in multi-hop wireless networksIEEE INFOCOM 2017 - IEEE Conference on Computer Communications10.1109/INFOCOM.2017.8057187(1-9)Online publication date: May-2017
https://doi.org/10.1109/INFOCOM.2017.8057187
Qiu CShen H(2017)Fading-Resistant Link Scheduling in Wireless Networks2017 46th International Conference on Parallel Processing (ICPP)10.1109/ICPP.2017.40(312-321)Online publication date: Aug-2017
https://doi.org/10.1109/ICPP.2017.40
Mao WWang XTang AQian H(2016)ANC-ERA: Random Access for Analog Network Coding in Wireless NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2015.240212215:1(45-59)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1109/TMC.2015.2402122
Qiu CShen H(2016)Link Scheduling in Cooperative Communication with SINR-Based Interference2016 25th International Conference on Computer Communication and Networks (ICCCN)10.1109/ICCCN.2016.7568540(1-9)Online publication date: Aug-2016
https://doi.org/10.1109/ICCCN.2016.7568540
Liew SLu LZhang S(2015)A Primer on Physical-Layer Network CodingSynthesis Lectures on Communication Networks10.2200/S00646ED1V01Y201505CNT0168:1(1-218)Online publication date: 28-Jun-2015
https://doi.org/10.2200/S00646ED1V01Y201505CNT016
Sgora AVergados DVergados D(2015)A Survey of TDMA Scheduling Schemes in Wireless Multihop NetworksACM Computing Surveys10.1145/267795547:3(1-39)Online publication date: 16-Apr-2015
https://dl.acm.org/doi/10.1145/2677955
Goussevskaia OHalldórsson MWattenhofer R(2014)Algorithms for wireless capacityIEEE/ACM Transactions on Networking10.1109/TNET.2013.225803622:3(745-755)Online publication date: 1-Jun-2014
https://dl.acm.org/doi/10.1109/TNET.2013.2258036
Halldórsson MHolzer SMitra PWattenhofer RKhanna S(2013)The power of non-uniform wireless powerProceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms10.5555/2627817.2627931(1595-1606)Online publication date: 6-Jan-2013
https://dl.acm.org/doi/10.5555/2627817.2627931
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten