complexity of scheduling with analog network coding
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.
complexity scheduling analog network coding physical interference model geometric sinr np-complete wireless ad-hoc networks