Scheduling with interference decoding: Complexity and algorithms

O. Goussevskaia, R. Wattenhofer, Scheduling wireless links with successive interference cancelation, in: International Conference on Computer Communication Networks (ICCCN), 2012. O. Goussevskaia, R. Wattenhofer, Complexity of scheduling with analog network coding, in: ACM International Workshop on Foundations of Wireless Ad Hoc and Sensor Networking and Computing (FOWANC), 2008. O. Goussevskaia, Y.A. Oswald, R. Wattenhofer, Complexity in geometric SINR, in: ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), 2007. Hamkins, 2000, An analytic technique to separate cochannel fm signals, IEEE Transactions on Communications, 48, 543, 10.1109/26.843120 Katti, 2007, Embracing wireless interference: analog network coding, 397 Yoon, 2010, Contrabass: concurrent transmissions without coordination, 403 Bölcskei, 2006, Capacity scaling laws in MIMO relay networks, IEEE Transactions on Wireless Communications, 5, 1433, 10.1109/TWC.2006.1638664 Halperin, 2008, Taking the sting out of carrier sense: interference cancelation for wireless LANs, 339 H. Hunt, M. Marathe, V. Radhakrishnan, S. Ravi, D. Rosenkrantz, R. Stearns, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, Journal of Algorithms 26 (1998). Krumke, 2001, Models and approximation algorithms for channel assignment in radio networks, Wireless Networks, 6, 575, 10.1023/A:1012311216333 Chatterjee, 2007, Rate allocation and admission control for differentiated services in CDMA data networks, IEEE Transactions on Mobile Computing, 6, 179, 10.1109/TMC.2007.29 O. Goussevskaia, M. Halldorsson, R. Wattenhofer, E. Welzl, Capacity of arbitrary wireless networks, in: 28th Annual IEEE Conference on Computer Communications (INFOCOM), 2009. T. Kesselheim, A constant-factor approximation for wireless capacity maximization with power control in the SINR model, in: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011. O. Goussevskaia, Y.A. Pignolet, R. Wattenhofer, Efficiency of wireless networks: approximation algorithms for the physical interference model, in: Foundations and Trends in Networking, 2010. J. Hamkins, Joint viterbi algorithm to separate cochannel fm signals, in: IEEE Int. Conf. Acoustics, Speech, Signal Processing, 1998. Verdu, 1998 Andrews, 2005, Interference cancelation for cellular systems: a contemporary overview, Wireless Communications, IEEE, 12, 19, 10.1109/MWC.2005.1421925 Hou, 2006, Implementing interference cancelation to increase the ev-do rev a reverse link capacity, Communications Magazine, IEEE, 44, 58, 10.1109/MCOM.2006.1593551 D. Halperin, J. Ammer, T. Anderson, D. Wetherall, Interference cancelation: better receivers for a new wireless MAC, in: Proceedings of the 6th ACM Workshop on Hot Topics in Networks (Hotnets), 2007. Gollakota, 2009, Interference alignment and cancelation, 159 E. Gelal, K. Pelechrinis, T.-S. Kim, I. Broustis, S.V. Krishnamurthy, B. Rao, Topology control for effective interference cancelation in multi-user mimo networks, in: Proceedings of the 29th Conference on Information Communications, INFOCOM’10, IEEE Press, <http://dl.acm.org/citation.cfm?id=1833515.1833824>. C. Avin, A. Cohen, Y. Haddad, E. Kantor, Z. Lotker, M. Parter, D. Peleg, Sinr diagram with interference cancelation, in: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, SIAM, 2012, pp. 502–515. <http://dl.acm.org/citation.cfm?id=2095116.2095159>. Ahlswede, 2000, Network information flow, IEEE Transactions on Information Theory, 46, 1204, 10.1109/18.850663 S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, J. Crowcroft, XORs in the air: practical wireless network coding, in: Proceedings of the ACM SIGCOMM Conference 2006, pp. 243–254. Y. Wu, Broadcasting when receivers know some messages a priori, in: IEEE Int. Symp. Inf. Theory, 2007. S. Zhang, S.C. Liew, P.P. Lam, Hot topic: physical-layer network coding, in: MOBICOM, 2006, pp. 358–365. Gollakota, 2008, Zigzag decoding: combating hidden terminals in wireless networks, 159 I. Maric, A. Goldsmith, M. Medard, Analog network coding in the high-snr regime, in: Proceedings of the IEEE Wireless Network Coding Workshop (WINC), 2010. Borade, 2007, Amplify-and-forward in wireless relay networks: rate, diversity, and network size, IEEE Transactions on Information Theory, 53, 3302, 10.1109/TIT.2007.904774 S. Agnihotri, S. Jaggi, M. Chen, Analog network coding in general SNR regime, in: ISIT, 2012, pp. 2052–2056. Garey, 1979 Garey, 1975, Complexity results for multiprocessor scheduling under resource constraints, SIAM Journal on Computing, 397, 10.1137/0204035 G. Brar, D. Blough, P. Santi, Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks, in: Proc. of the 12th International Conference on Mobile Computing and Networking (MOBICOM), 2006.